Câu trả lời này giới hạn cho các nhóm trong phép toán nhân modulo một số nguyên tố lớn $p$, bởi vì câu hỏi có (các nhóm khác ngày càng phổ biến trong mật mã, bao gồm cả Nhóm đường cong Elliptic).
Vì vậy, chúng tôi sẽ làm việc trong nhóm $\mathbb Z_p^*$, ký hiệu cho tập con của vành $\mathbb Z/p\mathbb Z$ được hình thành bởi các phần tử có nghịch đảo nhân, có thể được hiển thị để tạo thành một nhóm. Từ $p$ là nguyên tố, $\mathbb Z/p\mathbb Z$ là một trường và $\mathbb Z_p^*$ là lĩnh vực ít trung tính cho bổ sung. $\mathbb Z_p^*$ có thể được đồng hóa với số nguyên $\{1,2,\ldots,p-2,p-1\}$. Nó có $p-1$ phần tử. Quy luật nội tại của nhóm này là phép nhân modulo $p$.
Chúng tôi muốn một nhóm $\mathbb Z_p^*$ (hoặc một nhóm con của chúng) trong đó việc tính logarit rời rạc là khó khăn. Các điều kiện cho điều này (cả hai đều cần thiết và được phỏng đoán đủ khi cả hai đều được đáp ứng):
- Thứ tự của nhóm (nghĩa là số phần tử) phải có thừa số nguyên tố đủ lớn $q$ để ngăn chặn Pohlig-Hellman kết hợp với Pollard's rho, có thể tính logarit dễ dàng $\mathcal O\,\left(\sqrt q(\ln n)^3\right)$ và bộ nhớ vừa phải, một lần $p$ và $q$ được biêt đên. Vì vậy, chúng tôi muốn $q$ ít nhất 256-bit bảo mật 128-bit.
- $p$ phải đủ lớn để chặn các thuật toán của gia đình phép tính chỉ số. Điều đó sẽ yêu cầu $p$ từ 2048 đến 4096 bit (tùy thuộc vào tính bảo thủ, giả thuyết và nguồn) để bảo mật 128 bit, giả sử thêm $p$ không quá gần với lũy thừa của một số nguyên nhỏ.
Hệ thống logarit rời rạc thực tế được thiết lập như thế nào?
Điều đầu tiên là quyết định loại khung logarit rời rạc mà chúng tôi muốn thiết lập và điều đó phụ thuộc vào việc chúng tôi dự định sử dụng nó cho mục đích gì. Có ba loại thường được sử dụng:
- nhóm đầy đủ $\mathbb Z_p^*$, với đơn hàng $2q=p-1$ và $q$ nguyên tố. Cái đó được sử dụng khi một cái gì đó bắt buộc một trình tạo của nhóm đầy đủ (như "trình tạo nhóm nhân" của câu hỏi $\mathbb Z/p\mathbb Z$" đưa đến bức thư nào).
- Nhóm con của dư lượng bậc hai, với thứ tự nguyên tố $q=(p-1)/2$. Các yếu tố của nó là $y$ Trong $\mathbb Z_p^*$ có thể được viết như $y=u^2$ cho một số yếu tố $u$ của $\mathbb Z_p^*$ (và sau đó cũng cho $u'=p-u$, Đương nhiên). Có những nhóm tiêu chuẩn như vậy với máy phát điện $g=2$, xem RFC 3526. Chúng có thể được sử dụng cho hầu hết các mục đích sử dụng không yêu cầu trình tạo của nhóm đầy đủ.
- Một tập con nhỏ hơn của tập con các dư bậc hai, với thứ tự nguyên tố $q=(p-1)/r$ đối với một số (thậm chí) $r$. Chúng được gọi là nhóm Schnorr. Chúng được sử dụng trong chữ ký gốc của Schnorr và DSA.
Thường có lý do để không sử dụng (1.): nếu $g$ là một trình tạo (nghĩa là bất kỳ phần tử nào của nhóm có thể được biểu thị dưới dạng $g^x$ ) thì từ giá trị của $g^x$ thật dễ dàng để nói nếu $x$ là chẵn hay lẻ (bằng cách tính biểu tượng huyền thoại). Điều đó đi ngược lại giả thuyết mong muốn đối với các bằng chứng bảo mật đơn giản, chống lại các mục tiêu trong bằng chứng không có kiến thức và có thể cho phép các cuộc tấn công (ví dụ: mã hóa ElGamal không thành công CPA).
Đôi khi có lý do để không sử dụng (2.) và thích (3.): ít nhất trong các ứng dụng chữ ký, một trong các thành phần của chữ ký có cùng kích thước bit như $q$, cần phải lớn nhưng có thể nhỏ hơn nhiều so với $p$. Vì vậy sử dụng một nhỏ $q$ cho phép chữ ký ngắn hơn. Đó là lý do các nhóm Schnorr đã được giới thiệu.
Đối với (1.) và (2.), tạo $p$ và $q$ sôi xuống để tạo số nguyên tố $q$ với $p=2q+1$ cũng nguyên tố. Thật hiệu quả khi thực hiện một bài kiểm tra tương đối nhanh $q$ không phải là hợp số (ví dụ: phép thử Fermat đối với cơ sở 2: kiểm tra xem $2^{q-1}\bmod q=1$), sau đó kiểm tra kỹ lưỡng $p=2q+1$ là số nguyên tố; sau đó kiểm tra kỹ lưỡng $q$ là nguyên tố. Hơn nữa, đối với một số nguyên tố nhỏ $s$, nó giữ $q\bmod s\not\in\{0,(s-1)/2\}$. Như vậy $q\bmod3=2$, $q\bmod5\in\{1,3,4\}$, do đó $q\bmod30\in\{11,23,29\}$, thu hẹp phạm vi tìm kiếm. Xem xét lớn hơn một chút $s$ có thể được đưa vào sử dụng cho một cái sàng hoặc tăng tốc khác.
Ngoài ra, có thể chỉ ra rằng đối với $p$ và $q$ đối với (1.) hoặc (2.), $g=2$ là một trình tạo cho (1.) khi và chỉ khi $q\bmod4=1$ (tương đương $p\bmod8=3$ ); và một trình tạo cho (2.) nếu không. Như vậy để sử dụng $g=2$ (trình tạo nhỏ nhất có thể và một trình tạo hơi đơn giản hóa một số tính toán), chúng tôi muốn $q\bmod60\in\{29,41,53\}$ cho (1.) và $q\bmod60\in\{11,23,59\}$ dành cho 2.).
Đối với (3.), chúng ta có thể chọn số nguyên tố ngẫu nhiên $q$ có kích thước mong muốn, sau đó ngẫu nhiên thậm chí $r$ đủ kích thước để có $p=q\,r+1$ nguyên tố. một máy phát điện là $g=2^r$ (trừ khi đó là $1$, điều này ít nhất là khó xảy ra; Tôi tự hỏi nếu nó thậm chí có thể):
Nếu chúng tôi muốn một trình tạo ngẫu nhiên, chúng tôi có thể chọn một bí mật ngẫu nhiên $x$ Trong $[1,q-1]$ Và sử dụng $g$ như sau:
- cho (1.) và $p\bmod8=3$: $g\gets2^{2x+1}$
- cho (1.) và $p\bmod8=7$: bằng cách thử và sai, chúng tôi tìm thấy $y$ với $y^{(p-1)/2}\bmod p\ne 1$ (tương đương với $y^{(p-1)/2}\bmod p=p-1$ ); số lần thử dự kiến là khoảng hai lần nếu chúng ta khám phá số lẻ liên tiếp $u$ bắt đầu $u=3$; sau đó $g\được u^{2x+1}$.
- dành cho 2.), $g\gets2^{2x}$
- cho 3.), $g\gets2^{((p-1)/q)\,x}$
Không có thuật toán đã biết để tìm $g$ trong thời gian đa thức.
Điều đó đúng nếu hệ số hóa của thứ tự nhóm không được biết hoặc nếu chúng tôi giới hạn ở xác định thuật toán. Nhưng trong thực tế, thứ tự đã biết, đôi khi chúng ta có thể dự đoán một trình tạo và các thuật toán xác suất đơn giản sẽ nhanh chóng đưa ra một thứ khác.
Có gói số lớn nào không?
Python có hỗ trợ riêng cho các số lớn và đó là một bài tập đơn giản để xây dựng các tham số $(p,g)$ bằng Python thuần túy. Những khó khăn nhẹ duy nhất là thử nghiệm số nguyên tố và tạo số nguyên tố ngẫu nhiên. Nhưng chúng có thể được thực hiện bằng Python thuần túy và có hỗ trợ cho những điều này trong một số gói bao gồm SymPy. Từ $(p,g)$ thường công khai, các kênh phụ không phải là vấn đề.
