1.2. Congruential public key cryptosystem

Thuật toán này mình lấy từ [33].

1.2.1. Tạo khóa

Trong thuật toán này, ta chọn số nguyên tố \(q\) làm public parameter.

Sau đó chọn hai số \(f\) và \(g\) làm private key. Hai số này phải thỏa mãn các điều kiện

\[f < \sqrt{q/2}, \quad \sqrt{q/4} < g < \sqrt{q/2}, \quad \gcd(f, qg) = 1.\]

Tính \(h \equiv f^{-1} g \pmod q\). Khi đó public key là \(h\).

1.2.2. Mã hóa

Để mã hóa thông điệp \(m\), ta chọn số một số ngẫu nhiên \(r\) thỏa mãn

\[0 < m < \sqrt{q/4}, \quad 0 < r < \sqrt{q/2}.\]

Tiếp theo, ta tính \(e \equiv rh + m \pmod q\).

Bản mã \(e\) thỏa mãn \(0 < e < q\).

1.2.3. Giải mã

Từ bản mã \(e\) ta giải mã bằng cách tính

\[a \equiv fe \pmod q, \quad b \equiv f^{-1} a \pmod g.\]

Lưu ý \(f^{-1}\) là nghịch đảo modulo \(g\). Khi đó \(b \equiv m\) là message ban đầu.

Chứng minh

Để chứng minh rằng số \(b\) sau khi tính toán bằng chính xác \(m\) ban đầu ta cần xem xét điều kiện của private key và public key.

Đầu tiên ta có

\[a \equiv fe \equiv f(rh + m) \equiv f(r f^{-1} g + m) \equiv rg + fm \pmod q.\]

Từ điều kiện của \(f\), \(g\), \(r\) và \(m\) ta có

\[rg + fm < \sqrt{\dfrac{q}{2}} \cdot \sqrt{\dfrac{q}{2}} + \sqrt{\dfrac{q}{2}} \cdot \sqrt{\dfrac{q}{4}} < q.\]

Nói cách khác \(rg + fm\) giữ nguyên giá trị trong phép modulo \(q\), hay \(a \equiv rg + fm\).

Ta suy ra

\[b \equiv f^{-1} a \equiv f^{-1} (rg + fm) \equiv m \pmod g,\]

ở đây giá trị \(a\) không thay đổi khi chuyển từ modulo \(q\) sang modulo \(g\).

Do \(0 < m < \sqrt{q/4}\) và \(\sqrt{q/4} < g < \sqrt{q/2}\) nên \(m < g\). Nói cách khác \(b\) bằng đúng \(m\) ban đầu.

1.2.4. Ví dụ mã hóa và giải mã

Ta chọn số nguyên tố \(q = 3973659461\) là public parameter.

Ta chọn \(f = 36624\) và \(g = 33577\) làm private key. Ở đây có thể kiểm tra điều kiện

\[f < \sqrt{q/2}, \quad \sqrt{q/4} < g < \sqrt{q/2}, \quad \gcd(f, qg) = 1.\]

Lúc này public key là

\[h \equiv f^{-1} g \equiv 3540857813 \pmod q.\]

Giả sử ta muốn mã hóa thông điệp \(\boxed{m = 1024}\).

Ta chọn (ngẫu nhiên) giá trị \(r = 21542\). Ta tính được bản mã là

\[e \equiv rh + m \equiv 2765654775 \pmod{q}.\]

Để giải mã bản mã \(e = 2765654775\) với private key \(f = 36624\) và \(g = 33577\), đầu tiên ta tính

\[a \equiv f e \equiv 760818710 \pmod q.\]

Tiếp theo tính

\[b \equiv f^{-1} a \equiv 1024 \pmod g.\]

Như vậy \(b\) bằng chính xác bản rõ \(m = 1024\) ban đầu.

1.2.5. Phá mã

Để tấn công hệ mật mã này ta xây dựng lattice. Để ý rằng \(h = f^{-1} g \pmod q\), hay \(fh + kq = g\) với \(k \in \mathbb{Z}\).

Ta thấy rằng \(f \cdot (h, 1) + k \cdot (q, 0) = (g, f)\). Như vậy cơ sở của lattice gồm hai vector \((h, 1)\) và \((q, 0)\). Thuật toán rút gọn lattice Gauss sẽ hoạt động trong trường hợp này (số chiều bằng \(2\)).