Các tham số miền trong sơ đồ nhận dạng Schnorr

Gần đây tôi đã nghiên cứu sơ đồ nhận dạng Schnorr. Cuốn sách Cryptography: Theory and Practice của Stinson và Paterson nêu những điều sau đây về các tham số miền trong lược đồ nhận dạng Schnorr:

Lược đồ yêu cầu một cơ quan đáng tin cậy hoặc TA, người chọn một số tham số hệ thống phổ biến (tham số miền) cho lược đồ, như sau:

1. $p$ là một số nguyên tố lớn (tức là, $p\khoảng 2^{2048}$).

2. $q$ là ước nguyên tố lớn của $p-1$ (I E., $q\khoảng 2^{224}$).

3. $\alpha \in \mathbb{Z}_p^*$ có đơn đặt hàng $q$

4. $t$ là một tham số bảo mật sao cho $q>2^t$. (Tham số bảo mật là tham số mà giá trị của nó có thể được chọn để cung cấp mức độ bảo mật mong muốn trong một sơ đồ nhất định. Ở đây, xác suất lừa được Alice hoặc Bob của đối thủ là $2^{-t}$, Vì thế $t=80$ sẽ cung cấp bảo mật đầy đủ cho hầu hết các ứng dụng thực tế.)

Câu hỏi của tôi là, làm thế nào chúng ta có thể tìm thấy như vậy $p$, $q$, $\alpha$ và $t$? Và tại sao nó phải như vậy $p\khoảng 2^{2048}$, $q\khoảng 2^{224}$ và $t=80$?

Chúng tôi sẽ cần một bài kiểm tra tính nguyên tố hiệu quả để tạo ra $p$ và $q$. Nếu bạn hài lòng với các số nguyên tố có thể xảy ra thì Miller-Rabin kiểm tra sẽ đủ cho hầu hết các mục đích thực tế.Viết IsPrime() để kiểm tra.

Đầu tiên chọn $t$ theo các yêu cầu bảo mật của chương trình của bạn. Có một cơ hội của $2^{-t}$ rằng một kẻ lừa dối có thể lật đổ kế hoạch một cách ngẫu nhiên, do đó, việc lựa chọn $t=80$ có nghĩa là ngay cả khi kẻ tấn công của bạn cố gắng giả mạo hệ thống của bạn một cách ngẫu nhiên $2^{80}$ trung bình họ sẽ chỉ thành công một lần. Cho phép đối thủ $2^{80}$ cố gắng giả mạo hệ thống của bạn không chắc là một đề xuất thực tế, vì vậy $t=80$ được coi là tốt trong vấn đề này.

Bây giờ chúng tôi tìm thấy $q$, nó phải đủ lớn để một đối thủ không thể giải các logarit rời rạc trong một nhóm tùy ý $q$ các yếu tố (ví dụ: sử dụng em-bước-khổng lồ-bước method) và cũng lớn hơn $2^t$. Nếu $q\khoảng 2^{224}$ sau đó khoảng $2^{112}$ hoạt động nhóm sẽ được yêu cầu bởi phương pháp và do đó ít nhất $2^{112}$ hoạt động tính toán sẽ là cần thiết cho BS-GS. Để tìm 224-bit $q$ tạo một số 223-bit ngẫu nhiên $n$ và để cho $q_0=2^{223}+n$. Tính IsPrime($q_0$) và nếu thành công hãy để $q=q_0$ mặt khác tăng $q_0$ bằng 1 và lặp lại cho đến khi chúng tôi thành công.

Bây giờ chúng tôi tìm thấy $p$, nó phải đủ lớn để một đối thủ không thể giải được modulo logarit rời rạc $p$ (ví dụ: sử dụng sàng trường số). Nếu $p\khoảng 2^{2048}$ hướng dẫn của NIST đề nghị rằng ít nhất $2^{112}$ các thao tác tính toán sẽ được yêu cầu. Để tìm 2048-bit $p$, tạo một số 1824-bit ngẫu nhiên $m$ và để cho $p_0=q(2^{1824}+m)$. Tính IsPrime($p_0$) và nếu thành công hãy để $p=p_0$ mặt khác tăng $p_0$ qua $q$ và lặp lại cho đến khi chúng tôi thành công.

Bây giờ chúng tôi tìm thấy $\alpha$. Để cho $r=(p-1)/q$ lưu ý rằng $r$ là một số nguyên. Bắt đầu với $g=2$. tính toán $\alpha_0\equiv g^r\pmod p$, nếu $\alpha_0\not\equiv 1\pmod p$ cầm lấy $\alpha=\alpha_0$, nếu không tăng $g$ bằng 1 và lặp lại cho đến khi thành công.

Các tham số được chọn để cung cấp 112 bit bảo mật tính toán cổ điển, các tham số khác sẽ cung cấp các mức bảo mật khác nhau, ví dụ: $q\khoảng 2^{160}$ và $p\khoảng 2^{1024}$ sẽ cung cấp khoảng 80 bit bảo mật tính toán cổ điển và $q\khoảng 2^{256}$ và $p\khoảng 2^{3072}$ sẽ cung cấp khoảng 128 bit bảo mật tính toán cổ điển.