Mật khẩu Lattice NTRU

Ưu điểm

Hệ thống mật khẩu NTRU có khả năng chống lại các cuộc tấn công từ máy tính lượng tử, với thuật toán được thiết kế đơn giản, tốc độ mã hóa và giải mã nhanh, đồng thời yêu cầu không gian lưu trữ nhỏ. Điểm an toàn cốt lõi của nó phụ thuộc vào bài toán tìm vector ngắn nhất trong lattice (SVP).

Tạo khóa

Alice cần chọn bốn tham số số nguyên $(N, p, q, d)$ và bốn tập hợp đa thức hệ số nguyên bậc $N-1$ là $L_f, L_g, L_φ, L_m$, trong đó $N$ là số nguyên tố, $p, q$ không nhất thiết là số nguyên tố nhưng $\gcd(p, q) = 1$, và $q > (6d + 1)p$.

Định nghĩa $L(d_1, d_2) = { F(x) \in R }$, trong đó $F(x)$ có $d_1$ hệ số bằng $1$, $d_2$ hệ số bằng $-1$, và các hệ số còn lại là $0$. Alice sau đó chọn hai đa thức $f \in L(d+1, d)$ và $g \in L(d, d)$, đồng thời tính đa thức nghịch đảo của $f$ trong $R_p, R_q$ là $F_p(x), F_q(x)$. Nếu không tồn tại nghịch đảo, Alice cần chọn $f$ mới.

Tiếp theo, Alice tính $h = F_q * g$ trong $R_p$, và sử dụng $(N, p, q, d, h)$ làm khóa công khai, trong khi $(f, g)$ được giữ làm khóa bí mật.

Mã hóa

Bob có bản rõ $m \in R_p$, chọn một đa thức ngẫu nhiên $r \in L(d, d)$, và tính $e \equiv pr * h + m \pmod{q}$ để tạo ra bản mã.

Giải mã

Khi nhận được bản mã $e$, Alice tính $a \equiv f * e \equiv pg * r + f * m \pmod{q}$, sau đó chuyển $a$ về $R$ và tính $m \equiv F_p * a \pmod{p}$ để khôi phục lại bản rõ.

Lattice

NTRU có thể được biểu diễn dưới dạng lattice.

Chúng ta xây dựng ma trận $M = \begin{bmatrix} 1 & h \ 0 & q \end{bmatrix}$ làm lattice. Ta sẽ chứng minh rằng vector $(f, g)$ nằm trên lattice này.

Đầu tiên, chúng ta có thể viết lại đồng thức $f * h \equiv g \pmod{p}$ thành phương trình $f * h = g + k * p$, và biến đổi thành $f * h - k * p = g.

Ta có thể thấy rằng $(f, -u)M = (f, -u)\begin{bmatrix} 1 & h \ 0 & q \end{bmatrix} = (f + (-u)0, fh + (-u)p) = (f, fh - u*p) = (f, g)$.

Do đó, $(f, g)$ có thể biểu diễn bằng tổ hợp tuyến tính với hệ số nguyên $(f, -u)$ của hai vector cơ sở $M$, chứng tỏ $(f, g)$ thực sự nằm trên lattice này.

Ví dụ minh họa

Mã nguồn:

from Crypto.Util.number import *
import gmpy2
from flag import flag


def tham_so_bao_mat():
    p = getStrongPrime(2048)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        return (p, f, g, h)


def ma_hoa(ban_ro, p, h):
    m = bytes_to_long(ban_ro)
    r = getRandomNBitInteger(1024)
    c = (r * h + m) % p
    return c


p, f, g, h = tham_so_bao_mat()
c = ma_hoa(flag, p, h)
with open("ban_ma.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")

Hàm tham_so_bao_mat tạo ra 4 tham số:

$p$: Một số nguyên tố mạnh 2048 bit

$f$: Một số ngẫu nhiên 1024 bit

$g$: Một số nguyên tố mạnh 768 bit

$h$: $h \equiv f^{-1} * g \pmod{p}$

Hàm ma_hoa tạo ra một số ngẫu nhiên $r$ 1024 bit, và tính $c \equiv r * h + m \pmod{p}$

Giả sử chúng ta biết $f, g$, cùng với $h \equiv f^{-1} * g \pmod{p}$ và $c \equiv r * h + m \pmod{p}$, ta có:

$c \equiv r * (f^{-1} * g) + m \pmod{p}$

$c * f \equiv r * f^{-1} * g * f + m * f \pmod{p}$

$c * f \equiv r * g + m * f \pmod{p}$

Quan sát vế phải, ta thấy $r * g + m * f$ (khoảng 1800 bit) không lớn hơn $p$ (2048 bit), do đó chúng ta có thể chuyển đồng thức thành phương trình:

Đặt $a = c * f \pmod{p}$, ta có $a = r * g + m * f$

Lấy modulo $g$ của phương trình:

$a \equiv m * f \pmod{g}$

$m \equiv a * f^{-1} \pmod{g}$

Một điểm cần lưu ý

Chúng ta biết $g$ là số nguyên tố mạnh 768 bit, dù $f$ là 1024 bit, nhưng khi lấy modulo $g$, nghịch đảo của $f$ luôn tồn tại.

Giải pháp

Tiếp theo, chúng ta cần tìm $f, g$. Như đã chứng minh trước đó, $(f, g)$ nằm trên lattice.

$|(1, h)| \approx 2^{2000}$

$|(0, p)| \approx 2^{2048}$

$|(f, g)| \approx 2^{1024}$

Theo định lý Gaussian heuristic, vector ngắn nhất trong lattice này có độ dài khoảng $\sqrt{2^{2048}} = 2^{1024}$. Do đó, khả năng cao $(f, g)$ chính là vector ngắn nhất trong lattice này.

Làm thế nào để tìm vector ngắn nhất trên lattice?

Mặc dù SVP là bài toán NP-hard, nhưng ở đây số chiều thấp nên không khó giải quyết. Hiện tại, thuật toán LLL và các biến thể của nó là các thuật toán tốt nhất để giải SVP trong lattice số chiều thấp, nhưng hiệu quả giảm khi số chiều tăng.

h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757

# Xây dựng lattice.
vector1 = vector(ZZ, [1, h])
vector2 = vector(ZZ, [0, p])
ma_tran_lattice = matrix([vector1, vector2]);

# Giải SVP.
vector_ngan_nhat = ma_tran_lattice.LLL()[0]
f, g = vector_ngan_nhat
print(f, g)

# Giải mã.
a = f * c % p % g
m = a * inverse_mod(f, g) % g
print(hex(m).decode('hex'))

Tổng kết

Đây chỉ là một bài toán ứng dụng NTRU ở số chiều thấp. Do kiến thức hạn chế, tác giả chưa nghiên cứu sâu về NTRU ở số chiều cao.