Kích thước khóa riêng Diffie-Hellman
Tôi hiện đang viết bản triển khai Diffie-Hellma n của riêng mình (Đây không phải là mục đích sử dụng thực tế. Điều này hoàn toàn để tôi hiểu rõ hơn về DH bằng cách tự mình thực hiện.)
Đối với số nguyên tố và trình tạo, tôi đang sử dụng RFC 3526 , cụ thể hơn là số nguyên tố 4096-bit.
Câu hỏi của tôi là, có một thế hệ số nguyên bí mật tiêu chuẩn cụ thể cho Diffie-Hellman không? Vì bảo mật của các số nguyên bí mật (Thường là hai, nhưng DH hỗ trợ nhiều hơn giao tiếp 1-1) là khá quan trọng đối với bảo mật của trao đổi khóa.
Trả lời
DHKE
Trong một Diffie-Hellman theo cấp số nhân , được ký hiệu là DHKE, người ta lấy một nhóm$G$ với một máy phát điện $g$ với đơn đặt hàng của nó $n$.
Alice và Bob, trong quá trình trao đổi khóa, tạo ra số ngẫu nhiên $a$ và $b$ trong phạm vi $a,b\in (1,n)$ và truyền $g^a$ và $g^b$ và cuối cùng, họ thiết lập chìa khóa là $g^{ab}$ sau đó sử dụng KDF để lấy khóa đối xứng và IV / nonce.
Ngoài ra còn có phiên bản Đường cong Elliptic của DHKE và nó được ký hiệu là ECDH và nó được sử dụng nhiều hơn phiên bản hàm mũ cổ điển.
nguyên tố
Trong DHKE, chúng tôi chọn số nguyên tố là số nguyên tố an toàn, nghĩa là $p = 2 \cdot q + 1$ với $q$cũng là một số nguyên tố. Các$q$được gọi là số nguyên tố Sophie Germain .
Đây là một biện pháp đối phó với thuật toán Pohlig-Hellman được hưởng lợi từ yếu tố nhỏ của$p-1$. Nếu một số nguyên tố an toàn được sử dụng hơn các hệ số$2$ và $q$. Có một yếu tố lớn là một biện pháp đối phó với Pohlig-Hellman.
Ngoài ra còn có nhóm Schnorr với$p = r\,q + 1$. Đây có thể coi là sự tổng quát của các số nguyên tố hiền triết. Nguyên tố hiền triết là tối ưu.
Tạo chính
Cách tiếp cận ngây thơ tạo ra một số nguyên tố $q$ sau đó kiểm tra tính nguyên thủy của $2 \, q +1$( Menezes: Thuật toán 4.86 ). Trong mã giả;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
Có nhiều phương pháp nhanh hơn
Thế hệ Prime an toàn tốc độ gấp đôi của David Naccache, 2003
như tiêu đề cho thấy, điều này tăng tốc độ này lên khoảng một hệ số hai bằng cách kiểm tra cả hai $2q + 1$ và $(q − 1)/2$ cho tính nguyên thủy.
Ý tưởng đang sử dụng số nguyên tố ngẫu nhiên $p$ như số nguyên tố an toàn hoặc số nguyên tố Sophie Germain;
do p = randomPrime(k-bit integer) while ((p − 1)/2 and 2p + 1 are composite)Thế hệ Prime an toàn với sàng kết hợp của Michael J. Wiener, 2003.
Họ đề xuất sàng lọc các số nguyên tố nhỏ lên đến $2^{16}$. Điều này cung cấp$15x$ tăng tốc hơn so với thuật toán ngây thơ.
Ý tưởng bắt đầu với quan sát này; cả hai$q$ và $q=2p+1$ phải phù hợp với $2$ modulo $3$. Do đó, người ta có thể loại bỏ các ứng cử viên mà$0$ modulo $3$ và $1$ modulo $3$.
Điều này có thể được tổng quát cho bất kỳ số nguyên tố lẻ nào $r$. Loại bỏ$q$đó là đồng ý với $(r-1)/2$ modulo $r$ kể từ trong trường hợp này $p$ có thể chia được $r$.
Chụp một bộ $S$ tất cả các số nguyên tố lẻ $<B$. Sau đó$\prod_{r\in S}(r-2)/r$ trong số các ứng cử viên sẽ sống sót qua sàng.
Nếu $B=2^{16}$ người ta ước tính rằng nó có thể sản xuất $\approx \times 15$ tăng tốc.
Va chạm
Bây giờ chúng ta sẽ xem xét xác suất xuất hiện cùng một số ngẫu nhiên nếu có $k$những người sử dụng cùng một mô đun DHKE. Chúng tôi giả định rằng$k$những người sử dụng cùng một trình tạo số ngẫu nhiên an toàn (không thể đoán trước) để tạo khóa ngẫu nhiên của họ. Để đơn giản hóa điều này, chúng ta có thể giả định rằng có một người tạo ra các số ngẫu nhiên. Trong trường hợp này, đây hoàn toàn là nghịch lý sinh nhật và trong Mật mã học, chúng ta xem đây là cuộc tấn công sinh nhật để tìm ra va chạm với 50%. Đây là một cách phổ biến để xem xét sự va chạm của các hàm băm.
Để cho $H$ là phạm vi của trình tạo số ngẫu nhiên và $p$ đại diện cho xác suất chúng tôi muốn, sau đó $n(p; H)$ là số giá trị nhỏ nhất mà chúng ta phải chọn;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
Trong trường hợp xung đột băm cổ điển, chúng tôi đặt $p=1/2$ và cách tiếp cận này
$$n(0.5;H) \approx 1.1774 \sqrt H$$ và chúng tôi thường đại diện là $\mathcal{O}(\sqrt{H})$
Bây giờ, chúng ta hãy nhìn vào một số con số thực tế.
2048-bit nguyên tố
Giả sử $n$ là số 2048-bit, hãy nhớ $n$ là thứ tự của máy phát điện $g$. Sau đó
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
Với xác suất 50% $$n(0.5;2^{2048})\approx 2^{1204}$$
Do đó, bạn cần tạo $2^{1204}$số ngẫu nhiên để đánh một lần nữa với 50%. Không khả thi.
4096- bit nguyên tố
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
Với xác suất 50% $$n(0.5;2^{4096})\approx 2^{2048}$$
Do đó, bạn cần tạo $2^{2048}$số ngẫu nhiên để đánh một lần nữa với 50%. Không khả thi. Tính toán trước bảng dlog.
Vì mô-đun được xác định trước bởi các tiêu chuẩn, người ta có thể tranh luận rằng một số tổ chức có siêu năng lực đã xây dựng một số bảng DLog cho mô-đun.
Đây không phải là một mối nguy hiểm. Giả sử rằng họ có thể tạo một bảng lên đến$2^{64}$ thì xác suất trúng đích ngẫu nhiên của bạn là $$\frac{\ell \, 2^{64}}{2^{2048}}$$ với $\ell$thử. Đặt số lượng khóa có thể tạo của nhóm của bạn vào$\ell$. Vì vậy, 2048-bit là một con số thực sự lớn để giải quyết.