Fiat-Shamir heuristic là một phương pháp chung để xây dựng sơ đồ bằng chứng (hoặc chữ ký) không tương tác từ sơ đồ bằng chứng tri thức tương tác. Một ví dụ sơ đồ tương tác có thể tuân theo heuristic Fiat-Shamir là nhận dạng schnorr giao thức trong một nhóm Schnorr. Đó là cách tôi sẽ diễn giải câu hỏi (câu trả lời khác thảo luận về quan điểm tổng quát hơn của kinh nghiệm Fiat-Shamir).
Nhóm Schnorr là nhóm con của bậc nguyên tố $q$, và máy phát điện $g$, sau đó nhóm nhân modulo một số nguyên tố $p$. Nhóm chính đó $\mathbb Z_p^*$ có đơn đặt hàng $\varphi(p)=p-1$. Vì thứ tự của một nhóm con phân chia thứ tự nhóm, $q$ phải là một phép chia nguyên tố $p-1$. Từ $g$ là một máy phát điện, nó phải sao cho $g^q\equiv1\pmod p$ và $g\not\equiv1\pmod p$. Nhóm Schnorr thường được phát biểu là ba số nguyên $(p,q,g)$.
Số nguyên tố phải lớn như thế nào $p$ thì là ở? Làm thế nào để chọn $p$ để chẳng hạn như thuật toán PohligâHellman hoặc các thuật toán đã biết khác không thể phá vỡ nó?
Để nhóm Schnorr được quan tâm về mật mã, Bài toán logarit rời rạc phải khó trong nhóm Schnorr. Điều này ngụ ý chống lại các thuật toán DLP đã biết. Thuật toán thực tế xác định kích thước yêu cầu của $p$ trong một nhóm Schnorr là biến thể DLP của GNFS, đó là phép tính chỉ số chuyên để $\mathbb Z_p^*$. Các kỷ lục hiện tại là bit 795 bit $p$và kích thước tối thiểu được đề xuất cho các ứng dụng hiện tại là 2048-bit hoặc 3072-bit cho "2030 và hơn thế nữa".
Nó cũng cần thiết mà $q$ đủ lớn để Pollard's rho cho DLP là không khả thi. Đó là chi phí khoảng $\Theta(\sqrt q)$ phép nhân nhóm. Do đó, khuyến nghị tối thiểu là 224-bit hoặc 256-bit $q$.
Những yêu cầu này là đủ để đảm bảo Pohlig-Hellman thuật toán là không sợ hãi. Đó là bởi vì Pohlig-Hellman yêu cầu giải một DLP trong mỗi nhóm con của thứ tự $q^k$ với $k\ge 1$, $q$ số nguyên tố và $q^k$ phân chia thứ tự của nhóm cơ sở; và $k=1$ là trường hợp dễ nhất.
Cách chọn gốc nguyên thủy $g$?
Thuật toán thời gian đa thức xác suất này sẽ làm:
- chọn số nguyên tố ngẫu nhiên $q$ có kích thước mong muốn
- chọn ngẫu nhiên chẵn $r$ cho số nguyên tố $p=qr+1$ có kích thước mong muốn
- chọn ngẫu nhiên $s$ Trong $[2,p-2]$và tính toán $g=s^{(p-1)/q}\bmod p$, cho đến khi $g\ne1$ (gần như chắc chắn)
- như một kiểm tra tính nhất quán, xác minh $g^q\bmod p=1$ (được giữ trừ khi có lỗi).
Có an toàn không khi sử dụng cùng các giá trị của $p$ và $g$ cho một vài thử thách?
Đúng. Việc biết giải pháp cho một DLP cụ thể trong nhóm Schnorr rõ ràng không giúp giải quyết các DLP ngẫu nhiên không liên quan khác trên cùng một nhóm Schnorr (vẫn có khả năng một số tính toán trước có thể được phân bổ giữa một số DLP, nhưng đó là biên).
Tại sao nên sử dụng nhóm Schnorr thay vì số nguyên tố an toàn $p$?
Một số nguyên tố an toàn $p$ tương ứng với $p-1=2q$, hoặc $r=2$ ở trên. Mặc dù về mặt kỹ thuật vẫn phù hợp với định nghĩa của nhóm Schnorr, nhưng nó không đáp ứng động lực chính của nhóm Schnorr: có trật tự $q$ có kích thước nhỏ hơn nhiều so với $p$. Điều này thật thú vị vì số mũ nằm trong $\mathbb Z_q$, do đó ngắn hơn $q$ dẫn đến lũy thừa nhanh hơn, bí mật ngắn hơn và (trong một biến thể phổ biến của phương pháp phỏng đoán Fiat-Shamir) chữ ký ngắn hơn. Ngoài ra, việc tìm kiếm của $p$ có liên quan nhiều hơn một chút. Theo như chúng tôi biết, sử dụng một nhóm Schnorr với kích thước đủ lớn $q$ và $p$ an toàn như sử dụng số nguyên tố an toàn $p$ có kích thước tương đương.
