Trình tạo công thức tuyến tính, lớp trình tạo ngẫu nhiên giả đó với quy tắc đệ quy
$x_{n+1}\equiv a\cdot x_n +b\ \ (\mod m)$, $a,b,x_n\in Z/mZ$, $m,n\in N$
được coi là không phù hợp để sử dụng trong mật mã, vì các hằng số $a$, $b$ có thể bằng cách suy ra từ một tập hợp nhỏ các kết quả đầu ra $x_n$. Bây giờ, khi bạn chọn $m=p-1$ cho một số nguyên tố lẻ $p$, trình tự $(x_n)_{n\in N}$ có thể sống dưới dạng số mũ của một số trình tạo $g$ của nhóm tuần hoàn nhân $Z/pZ^*$, như $y_n:=g^{x_n}, n\in N$:
$y_{n+1}\equiv g^{x_{n+1}}\equiv g^{a\cdot x_n+b}\equiv (g^{x_n})^a\cdot g^b\equiv y_n ^a\cdot g^b\ (\mod p)$
Đây là một chuỗi lũy thừa tương đương.
Phân phối bình đẳng đi kèm với thời gian tối đa. Điều kiện cho thời gian tối đa $m$ của trình tự $(y_n)_{n\in N}$ được đưa ra bởi Định lý Knuth
- $gcd(m,b)=1$
- Đối với sự phân hủy nguyên tố $m=:\prod p_i^{\alpha_i}$ và tất cả các thừa số nguyên tố $p_i$: $\ \ \ p_i/(a-1)$
- $m\equiv 0\ (\mod 4) \ngụ ý a-1\equiv 0\ (\mod 4)$
Như $m=p-1$ chẵn và có rất ít số nguyên tố đồng dạng $p=2^k+1$, thành phần phổ biến dễ nhất của $p-1$ từ số nguyên tố sẽ là $p-1=2^k\cdot p'$, $k\geq 1$ với $p'$ một số nguyên tố khác.
Theo điều kiện thứ 2 lựa chọn nhỏ nhất của $a$ là bởi $a-1=2\cdot p'$.
Để tránh trường hợp tầm thường $a-1=m$, $k\geq 2$ là cần thiết. Với điều này, chúng tôi chạy vào điều kiện thứ 3, do đó $a-1$ có ít nhất hai lần yếu tố $2$.
Một lần nữa, tránh trường hợp tầm thường đòi hỏi $k\geq 3$.
Bây giờ, một cặp nguyên tố $(p,p')$ phù hợp với phương trình tuyến tính $p=8p'+1$ cho phép lựa chọn không tầm thường $a-1=4p'$ và với điều này, chuỗi sức mạnh $(y_n)$ có thể có thời gian tối đa $m$.
Câu hỏi: Vì chúng ta có 3 tham số ẩn $g, g^a,g^b$ và việc tìm logarit trong các nhóm nhân được coi là khó khăn, phải chăng dãy số ngẫu nhiên $(y_n){n\in N}$ được coi là an toàn để sử dụng trong mật mã; có những lựa chọn tốt hơn cho hằng số $a$?
CHỈNH SỬA $g$ thực sự không quan trọng bằng tham số, khi chúng ta tăng quyền hạn lên $a$, ngoài ra ở đâu $p$ không được biết từ đầu ra, tức là các tham số chưa biết là $(p, a, g^b)$ .
