Ukuran Kunci Pribadi Diffie-Hellman
Saat ini saya sedang menulis implementasi Diffie-Hellma n saya sendiri (Ini bukan untuk penggunaan sebenarnya. Ini secara ketat agar saya mendapatkan pemahaman yang lebih baik tentang DH dengan melakukannya sendiri.)
Untuk prime dan generator, saya menggunakan RFC 3526 , lebih khusus lagi prime 4096-bit.
Pertanyaan saya adalah, apakah ada generasi integer rahasia standar khusus untuk Diffie-Hellman? Karena keamanan bilangan bulat rahasia (Biasanya dua, tetapi DH mendukung lebih dari 1-1 komunikasi) sangat penting untuk keamanan pertukaran kunci.
Jawaban
DHKE
Dalam Diffie-Hellman eksponensial , dilambangkan dengan DHKE, seseorang mengambil sebuah grup$G$ dengan generator $g$ dengan pesanannya $n$.
Alice dan Bob, selama pertukaran kunci, menghasilkan nomor acak $a$ dan $b$ dalam jangkauan $a,b\in (1,n)$ dan mentransmisikan $g^a$ dan $g^b$ dan akhirnya, mereka menetapkan kunci sebagai $g^{ab}$ kemudian gunakan KDF untuk mendapatkan kunci simetris dan IV / nonce.
Ada juga versi Elliptic Curve dari DHKE dan dilambangkan dengan ECDH dan ini lebih banyak digunakan daripada versi eksponensial klasik.
Utama
Di DHKE, kami memilih prime untuk menjadi prime yang aman $p = 2 \cdot q + 1$ dengan $q$juga merupakan bilangan prima. Itu$q$disebut prima Sophie Germain .
Ini adalah tindakan balasan terhadap algoritma Pohlig-Hellman yang diuntungkan dari faktor kecil dari$p-1$. Jika bilangan prima yang aman digunakan daripada faktor-faktornya$2$ dan $q$. Memiliki faktor besar merupakan tindakan balasan terhadap Pohlig-Hellman.
Ada juga grup Schnorr dengan$p = r\,q + 1$. Ini dapat dianggap sebagai generalisasi dari bilangan prima bijak. Sage prime itu optimal.
Pembangkit Utama
Pendekatan naif menghasilkan bilangan prima $q$ kemudian periksa keutamaan $2 \, q +1$( Menezes: Algoritma 4.86 ). Dalam pseudocode;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
Ada metode yang lebih cepat
Generasi Utama Aman Berkecepatan Ganda oleh David Naccache, 2003
seperti judulnya, ini mempercepatnya sekitar faktor dua dengan menguji keduanya $2q + 1$ dan $(q − 1)/2$ untuk keutamaan.
Idenya menggunakan bilangan prima acak $p$ sebagai prime yang aman atau Sophie Germain prime;
do p = randomPrime(k-bit integer) while ((p − 1)/2 and 2p + 1 are composite)Generasi Perdana yang Aman dengan Saringan Gabungan oleh Michael J.Wiener, 2003.
Mereka mengusulkan penyaringan bilangan prima kecil hingga $2^{16}$. Ini memberikan$15x$ lebih cepat dari algoritme naif.
Idenya dimulai dengan observasi ini; kedua$q$ dan $q=2p+1$ harus kongruen dengan $2$ modulo $3$. Oleh karena itu seseorang dapat menghilangkan kandidat yang dengannya$0$ modulo $3$ dan $1$ modulo $3$.
Ini dapat digeneralisasikan untuk setiap bilangan prima ganjil $r$. Menghapuskan$q$yang konguruent untuk $(r-1)/2$ modulo $r$ sejak dalam kasus ini $p$ habis dibagi $r$.
Ambil satu set $S$ semua bilangan prima ganjil $<B$. Kemudian$\prod_{r\in S}(r-2)/r$ calon akan selamat dari saringan.
Jika $B=2^{16}$ diperkirakan bisa berproduksi $\approx \times 15$ mempercepat.
Tabrakan
Sekarang kita akan melihat kemungkinan mendapatkan bilangan acak yang sama jika ada $k$orang yang menggunakan modulus DHKE yang sama. Kami mengasumsikan bahwa file$k$orang-orang yang menggunakan generator nomor acak aman (tidak dapat diprediksi) yang sama untuk menghasilkan kunci acak mereka. Untuk menyederhanakan ini, kita dapat berasumsi bahwa ada satu orang yang menghasilkan bilangan acak. Dalam hal ini, ini benar-benar paradoks ulang tahun dan dalam Kriptografi kita melihat ini adalah serangan ulang tahun untuk menemukan tabrakan dengan 50%. Ini adalah cara umum untuk melihat tumbukan fungsi hash.
Membiarkan $H$ menjadi kisaran generator nomor acak, dan $p$ mewakili probabilitas yang kita inginkan $n(p; H)$ jadilah jumlah nilai terkecil yang harus kita pilih;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
Dalam kasus tabrakan hash klasik, kami menetapkan $p=1/2$ dan pendekatan ini
$$n(0.5;H) \approx 1.1774 \sqrt H$$ dan kami biasanya mewakili sebagai $\mathcal{O}(\sqrt{H})$
Sekarang, mari kita lihat beberapa angka sebenarnya.
Perdana 2048-bit
Asumsikan bahwa $n$ adalah angka 2048-bit, ingat $n$ adalah urutan generator $g$. Kemudian
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
Dengan kemungkinan 50% $$n(0.5;2^{2048})\approx 2^{1204}$$
Akibatnya, Anda perlu menghasilkan $2^{1204}$nomor acak untuk memukul satu lagi dengan 50%. Tidak layak.
4096- bit prima
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
Dengan kemungkinan 50% $$n(0.5;2^{4096})\approx 2^{2048}$$
Akibatnya, Anda perlu menghasilkan $2^{2048}$nomor acak untuk memukul satu lagi dengan 50%. Tidak layak. Pra-Hitung tabel dlog.
Karena modulus telah ditentukan sebelumnya oleh standar, orang dapat berargumen bahwa beberapa organisasi dengan kekuatan super membangun beberapa tabel DLog untuk modulus.
Ini juga tidak berbahaya. Mari kita asumsikan bahwa mereka dapat membangun tabel hingga$2^{64}$ maka kemungkinan klik acak Anda adalah $$\frac{\ell \, 2^{64}}{2^{2048}}$$ dengan $\ell$mencoba. Masukkan kemungkinan nomor generasi kunci grup Anda$\ell$. Jadi, 2048-bit adalah angka yang sangat besar untuk ditangani.