====================================
Congruential public key cryptosystem
====================================

Thuật toán này mình lấy từ :cite:`Hoffstein2014`.

--------
Tạo khóa
--------

Trong thuật toán này, ta chọn số nguyên tố :math:`q` làm public parameter.

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

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

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

------
Mã hóa
------

Để mã hóa thông điệp :math:`m`, ta chọn số một số ngẫu nhiên :math:`r` thỏa mãn 
 
.. math:: 0 < m < \sqrt{q/4}, \quad 0 < r < \sqrt{q/2}.

Tiếp theo, ta tính :math:`e \equiv rh + m \pmod q`.

Bản mã :math:`e` thỏa mãn :math:`0 < e < q`.

-------
Giải mã
-------

Từ bản mã :math:`e` ta giải mã bằng cách tính

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

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

.. admonition:: Chứng minh
    :class: danger, dropdown

    Để chứng minh rằng số :math:`b` sau khi tính toán bằng chính xác :math:`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ó 

    .. math:: 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 :math:`f`, :math:`g`, :math:`r` và :math:`m` ta có

    .. math:: 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 :math:`rg + fm` giữ nguyên giá trị trong phép modulo :math:`q`, hay :math:`a \equiv rg + fm`.
        
    Ta suy ra

    .. math:: b \equiv f^{-1} a \equiv f^{-1} (rg + fm) \equiv m \pmod g,

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

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

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

Ta chọn số nguyên tố :math:`q = 3973659461` là public parameter.

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

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

Lúc này public key là

.. math:: h \equiv f^{-1} g \equiv 3540857813 \pmod q.

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

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

.. math:: e \equiv rh + m \equiv 2765654775 \pmod{q}.

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

.. math:: a \equiv f e \equiv 760818710 \pmod q.

Tiếp theo tính

.. math:: b \equiv f^{-1} a \equiv 1024 \pmod g.

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

------
Phá mã
------

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

Ta thấy rằng :math:`f \cdot (h, 1) + k \cdot (q, 0) = (g, f)`. Như vậy cơ sở của lattice gồm hai vector :math:`(h, 1)` và :math:`(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 :math:`2`).