Sulitnya Membuat Bilangan Prima 1024-bit

• Ini adalah eksperimen untuk membuat langsung dua bilangan prima sekitar 1024-bit yang dibutuhkan untuk kunci RSA 2048-bit, dengan implementasi dari pembangkitan bilangan acak hingga operasi bilangan bulat besar langsung di Rust tanpa dependensi eksternal
• Trial division sederhana cukup memadai pada 16-bit dengan waktu sekitar 40ms, tetapi bahkan pada 64-bit masih memerlukan 6,4 detik setelah optimasi, sehingga sulit diperluas ke 1024-bit
• Uji Fermat cepat, tetapi bisa gagal menyaring pseudoprime, sehingga penentuan akhir memakai uji Miller-Rabin dengan k=10
• Untuk melampaui batas tipe integer bawaan, dibuat BigInt sendiri, lalu waktu pembuatan bilangan prima 1024-bit turun dari sekitar 32 menit menjadi 60~90 detik saat struktur diubah dari array bool ke array byte lalu ke chunk u64
• Implementasi akhir menggabungkan BigInt chunk u64, pembagian cepat, trial division dengan bilangan prima kecil, peningkatan kandidat dengan +2, dan eksekusi paralel 16 thread, sehingga dapat menemukan bilangan prima 1024-bit rata-rata dalam sekitar 40ms, tetapi ini bukan pustaka kriptografi yang telah tervalidasi

---

Membuat sendiri bilangan prima 1024-bit untuk RSA

• Tujuannya adalah membuat sendiri bilangan prima yang bisa dipakai untuk pembuatan kunci RSA
  • Kunci RSA 2048-bit dibuat dari hasil kali dua bilangan prima, jadi masing-masing membutuhkan bilangan prima berukuran sekitar 1024-bit
  • Tantangannya pun secara alami menyempit menjadi pembuatan bilangan prima 1024-bit
• Eksperimen ini diberi tiga batasan
  • Kode ditulis dari nol dan tidak memakai dependensi eksternal
  • Menggunakan laptop dengan CPU AMD Ryzen 7 dan RAM 16GB tanpa perangkat keras eksternal atau cloud
  • Bilangan prima harus dihasilkan dalam “waktu yang masuk akal”
• Bahasa yang dipilih adalah Rust yang baru dipelajari belakangan ini
  • Bahasa ini dianggap cukup dekat ke konsep tingkat rendah, sekaligus cukup tingkat tinggi untuk memahami potongan kode

Batas trial division yang terlihat pada 16-bit dan 64-bit

• Alur dasarnya adalah membuat bilangan acak N-bit berulang kali, lalu berhenti jika lolos uji primalitas
• Bilangan acak dibuat dengan membaca langsung /dev/urandom di Linux alih-alih memakai crate rand milik Rust
  • /dev/urandom adalah berkas perangkat semu yang memberi akses ke CSPRNG milik kernel Linux
  • Kernel mengumpulkan entropi dari lingkungan pengguna dan melakukan seed berkala pada stream cipher deterministik berbasis ChaCha20
• Untuk bilangan acak 16-bit, bit pertama dan bit terakhir diatur menjadi 1
  • Bit terakhir 1 dipakai untuk memastikan angkanya ganjil
  • Bit pertama 1 dipakai agar seluruh rentang bit yang dibutuhkan benar-benar terpakai
• Pada 16-bit, hanya dengan trial division membagi dari 3 sampai sqrt(num) pun sudah bisa menemukan bilangan prima dalam sekitar 40ms
  • Contoh eksekusi menghasilkan Prime found: 44809, dan total waktunya sekitar 0,038 detik
• Saat diperluas ke 64-bit, trial division sederhana memerlukan sekitar 30 detik
  • Setelah itu diperbaiki dengan hanya memeriksa kandidat berbentuk 6k±1 dan lebih dulu membagi dengan daftar bilangan prima kecil
  • Setelah perbaikan, waktu pembuatan bilangan prima 64-bit menjadi sekitar 6,414 detik
• Karena pada 64-bit saja sudah butuh 6 detik, menjadi jelas bahwa pendekatan ini sulit mencapai pembuatan bilangan prima 1024-bit

Beralih ke uji primalitas probabilistik

• Algoritme deterministik seperti APR-CL dan ECPP sempat dipelajari, tetapi secara matematis rumit dan sulit dijadikan target implementasi karena minim penjelasan yang mudah diakses
• Setelah melihat kode sumber OpenSSL dan rekomendasi NIST, dipastikan bahwa uji primalitas probabilistik memang luas dipakai dalam penggunaan nyata termasuk RSA
• Setelah itu, algoritmenya berubah dari “membuktikan bahwa bilangan itu prima” menjadi menilai bahwa bilangan tersebut adalah probable prime dengan tingkat akurasi tertentu

• Uji Fermat

  • Teorema kecil Fermat memakai relasi bahwa jika p prima dan a tidak habis dibagi p, maka a^(p-1) = 1 mod p
  • Karena perpangkatan biasa bisa menyebabkan overflow pada u128, dibuatlah modular exponentiation
  • pow() menerima eksponen sebagai u32, dan menaikkan u128 ke eksponen yang lebih besar bisa menimbulkan overflow
  • Perkaliannya sendiri juga bisa melampaui rentang u128, sehingga sementara dipakai pendekatan menyimpan bilangan 64-bit di dalam u128
  • Uji Fermat cepat, tetapi karena adanya Fermat pseudoprime, bilangan komposit bisa salah dinilai sebagai prima
  • Bilangan komposit seperti ini memang jarang, tetapi tetap cukup banyak sehingga uji Fermat saja dianggap kurang andal

• Uji Miller-Rabin

  • Miller-Rabin didasarkan pada prinsip yang sama dengan uji Fermat, tetapi digunakan sebagai algoritme uji primalitas probabilistik yang lebih kuat
  • Implementasinya memisahkan pangkat dua dalam bentuk n-1 = 2^s × d, lalu memeriksa beberapa kondisi
  • a^d = 1 mod n
  • atau untuk suatu 0 <= r < s, a^(2^r × d) = n - 1 mod n
  • Dalam eksperimen 128-bit, bilangan prima ditemukan dalam sekitar 0,042 detik, mirip dengan uji Fermat
  • Batas galat terburuk Miller-Rabin adalah 4^-k, dan untuk n besar rata-ratanya berada di kisaran 8^-k
  • Saat k=10, perhitungan peluang galat rata-ratanya adalah 0.000000000931323%
  • Ini dibandingkan dengan peluang mendapatkan sisi kepala pada 30 lemparan koin berturut-turut, yaitu 2^-30
  • Untuk kriptografi nyata, pemilihan base acak dan kondisi adversarial harus diperlakukan dengan lebih hati-hati

Membuat BigInt sendiri

• Dengan tipe integer bawaan Rust saja, sulit menangani bilangan yang cukup besar di atas 64-bit, sehingga perlu implementasi integer presisi arbitrer (BigInt)
• Karena ada batasan tidak memakai crate bigint eksternal, BigInt juga diimplementasikan sendiri

• Percobaan 1: array digit angka

  • Awalnya dicoba cara menyimpan bilangan besar sebagai array digit desimal
  • Penjumlahan dan perkalian bisa diimplementasikan seperti hitung manual, tetapi implementasi pembagian menjadi hambatan sehingga pendekatan ini ditinggalkan

• Percobaan 2: array biner berbasis bool

  • Pendekatan kedua menyimpan bilangan sebagai array 0 dan 1
  • BigInt memakai array [bool; 2048]
  • Karena mengalikan dua bilangan 1024-bit bisa membutuhkan ruang maksimum 2048-bit, maka disediakan 2048 bit
  • Penjumlahan dan pengurangan diimplementasikan dengan gaya full adder
  • Perkalian diproses dengan metode shift-and-add menggunakan sifat bilangan biner
  • Pembagian diimplementasikan sebagai long division biner
  • Dengan implementasi ini, bilangan prima 1024-bit pertama berhasil ditemukan, tetapi waktu eksekusinya sekitar 32 menit 44,90 detik
  • Secara teknis target tercapai, tetapi tidak memenuhi batasan “waktu yang masuk akal”

• Percobaan 3: chunk byte

  • Lalu disadari bahwa setiap bool dalam array bool bukan memakan 1 bit, melainkan 1 byte
  • [bool; 2048] berarti memakai 2048 byte, bukan 2048 bit
  • Setelah itu, formatnya diubah menjadi penyimpanan 2048 bit dalam array 256 byte
  • Penjumlahan, pengurangan, dan perkalian tetap berjalan tanpa perubahan besar, sementara pembagian disesuaikan agar memperlakukan chunk byte seperti daftar bit
  • Dengan cara ini, waktu pembuatan bilangan prima 1024-bit turun menjadi 4 menit 43 detik

• Percobaan 4: chunk u64

  • Cara chunk byte pada dasarnya adalah BigInt berbasis digit dengan radix lebih tinggi
  • Pada langkah berikutnya, 2048 bit disimpan sebagai 32 chunk u64
  • Setiap chunk bertindak seperti satu “digit”
  • Untuk menampung hasil perkalian dua chunk u64, dipakai u128
  • Dengan struktur ini, bilangan 1024-bit bisa direpresentasikan dengan 16 chunk u64 alih-alih 309 digit desimal
  • Waktu pembuatan bilangan prima 1024-bit membaik menjadi 60~90 detik

Optimasi bottleneck

• Benchmark sederhana menunjukkan perbedaan yang jelas antara implementasi biner dan implementasi chunk u64
  • a + b dan a - b: 5537.35ns → 123.57ns
  • a * b: 1292283.14ns → 842.32ns
  • a / b dan a % b: 733446.76ns → 44440.12ns
  • a < b dan a > b: 2506.02ns → 58.91ns
• Setelah itu, optimasi difokuskan terutama pada pembagian, perkalian, operasi internal Miller-Rabin, dan logika pembangkitan kandidat

• Pembagian

  • Bottleneck terbesar adalah pembagian
  • Bahkan pada struktur chunk u64, pembagian yang lama masih melakukan long division satu bit demi satu bit
  • Dengan merujuk pada algoritme di halaman 598 Handbook of Applied Cryptography, diimplementasikan long division berbasis radix
  • Caranya dengan memperkirakan “digit” quotient saat ini dari 3 “digit” terdepan dividend dan 2 “digit” terdepan divisor
  • Implementasi ini menghemat sekitar 40.000ns per satu kali pembagian
  • Jika divisor hanya terdiri dari satu chunk u64, dilakukan penanganan khusus agar long division bisa dikerjakan lebih langsung dengan u128
  • Kasus seperti ini sering muncul di Miller-Rabin

• Perkalian

  • Perkalian menjadi sekitar 2 kali lebih cepat setelah loop disusun ulang untuk menghilangkan BigInt penyimpanan hasil antara
  • Jumlah chunk yang terisi dihitung agar loop hanya berjalan pada chunk yang tidak nol
  • Karena BigInt kebanyakan menyimpan bilangan di bawah 1024-bit, sering kali separuh dari ruang 2048-bit masih kosong
  • Perkalian berbasis Karatsuba atau FFT juga dipertimbangkan, tetapi dianggap terlalu rumit untuk implementasi manual dan perkalian saat ini dinilai sudah cukup cepat

• Optimasi internal Miller-Rabin

  • Pada implementasi Miller-Rabin, fokusnya adalah mengurangi operasi yang mahal
  • Alih-alih x = mod_exp(x, 2, n), dilakukan langsung x = (x * x) % n
  • mod_exp() pertama diganti dengan versi inline yang disederhanakan untuk mengurangi overhead pemanggilan fungsi
  • Untuk pengecekan genap, ditambahkan num.is_even() agar tak perlu menghitung % 2
  • d / 2 diubah menjadi d >>= 1
  • += 1 dan -= 1 ditangani khusus lewat increase() dan decrease()
  • Khususnya is_even() dan d >>= 1 masing-masing memberi keuntungan sekitar 70.000ns
  • Dalam benchmark akhir, versi chunk u64 yang telah dioptimasi menjadi jauh lebih cepat
  • a * b: 842.32ns → 295.04ns
  • a / b dan a % b: 44440.12ns → 831.77ns
  • a / 2: 75121.58ns → 60.89ns
  • a % 2 == 0: 78400.87ns → 21.65ns
  • a - 1: 103.15ns → 67.54ns

Pembuat bilangan prima 1024-bit final

• Fungsi final pertama-tama membaca bilangan acak 1024-bit dari /dev/urandom
  • Bit paling atas diaktifkan untuk memastikan ukurannya 1024-bit
  • Bit paling bawah diaktifkan untuk memastikan bilangannya ganjil
• Setelah itu, alih-alih membaca bilangan acak baru setiap kali, nilai kandidat dinaikkan 2 untuk berpindah ke kandidat ganjil berikutnya
  • increase_by_2() pada umumnya hanya melakukan penjumlahan pada satu chunk u64
• Sebelum Miller-Rabin, lebih dulu dilakukan trial division dengan daftar bilangan prima kecil
  • Pada kode final, dipakai 1000 bilangan prima kecil pertama
  • Karena bilangan prima kecil ini muat dalam satu chunk u64, penanganan khusus pembagian satu chunk yang cepat bisa dimanfaatkan
• Masalah ini bisa ditangani sebagai bentuk embarrassingly parallel yang tidak memerlukan memori bersama atau sinkronisasi antarthread
  • 16 thread CPU masing-masing mencari bilangan prima, lalu nilai dari thread yang pertama mengirim hasil dipakai
• Contoh eksekusi final mencatat elapsed time sekitar 0,086 detik
  • Penggunaan CPU ditampilkan sebagai 690%
• Rata-rata 100 kali eksekusi adalah 0.04109 ± 0.00307 detik
  • Artinya, bilangan prima 1024-bit ditemukan rata-rata dalam sekitar 40ms
  • Pemanggilan prime_1024bit() tunggal bisa bervariasi dari sekitar 8ms hingga sekitar 800ms karena sifat acak
  • Eksekusi paralel dipakai untuk memilih hasil tercepat dan meredam variasi tersebut

Kode dan keterbatasan

• Seluruh kode dan repositorinya dipublikasikan di github
• Tautan diskusinya ada di hackernews dan reddit
• Implementasi ini sulit dianggap aman secara kriptografis untuk penggunaan nyata, dan tujuannya juga bukan membuat pustaka kriptografi, melainkan lebih dekat ke eksperimen belajar dan implementasi

[GN⁺]

Pendapat Hacker News

• Ada beberapa cryptocurrency yang memakai pencarian bilangan prima besar sebagai bagian dari fungsi proof of work, dan sekitar 8 tahun lalu, sekadar punya implementasi uji primalitas yang sangat cepat saja sudah bisa menghasilkan cukup banyak uang
  Saya sempat menjadi penulis sekaligus pemelihara perangkat lunak penambangan riecoin untuk beberapa waktu; entah kenapa, mungkin karena saya memang suka bilangan prima
  Tulisan ini melewatkan perkalian Montgomery, optimisasi nomor satu untuk uji primalitas cepat: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
  Ini menjadi dasar implementasi eksponensiasi modular berkecepatan tinggi yang praktis
  Niall Emmart, yang seingat saya dulu berada di dunia akademik dan sekarang di Nvidia, merilis library bilangan bulat besar GPU CGBN yang benar-benar sangat cepat: https://github.com/NVlabs/CGBN
  Sampai sekarang itu masih implementasi eksponensiasi modular batch tercepat yang saya tahu, dan kalau boleh sedikit nerd-out, hasilnya sampai membuat takjub
  Suatu hari saya harus menulis cerita tentang bagaimana ini membuat saya mendominasi produksi sebuah cryptocurrency kecil selama sekitar 5 tahun. Dan Python punya eksponensiasi modular yang cukup bagus dalam bentuk tiga argumen pow(x, y, m) untuk menghitung x^y % m
  Dengan itu, kalau ingin membuat sendiri, uji primalitas Fermat atau Miller-Rabin bisa dibuat sangat mudah dan cukup menyenangkan. Kalau tidak ingin membuat sendiri, mpz_probab_prime() dari library gmp juga bagus. gmp tentu lebih cepat, tetapi sulit mengalahkan keseruan uji Fermat dua baris saat bermain-main dengan bilangan prima besar

  • Niall juga terlibat dalam salah satu submission pemenang ZPrize terkait multi-scalar multiplication cepat
    Ini berkaitan erat dengan eksponensiasi modular batch, tetapi bedanya bekerja di atas kurva eliptik, bukan modulo prima. Saya menganggapnya sebagai kelanjutan dari pekerjaan CGBN
    Tahun lalu ia memberi presentasi yang bagus di seminar makan siang kriptografi Stanford, dan slide serta rekamannya juga tersedia online
    https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
    https://www.youtube.com/watch?v=KAWlySN7Hm8
  • Saya penasaran mengapa cryptocurrency semacam itu memakai fungsi proof of work kustom seperti itu
    Apakah karena hanya ada gagasan samar bahwa kriptografi entah bagaimana memakai bilangan prima, tanpa tahu kapan dan mengapa dipakai, atau ada alasan yang lebih dalam?
  • Karena pow(x,e,mod), saya pindah dari Perl ke Python

• Jika ada batas maksimum angka yang diberikan, membuat Miller-Rabin praktis deterministik itu sederhana
  Cukup pilih basis-basis yang terbukti menyaring semua pseudoprime dalam rentang tersebut
  Daftarnya juga tidak panjang. Miller-Rabin benar-benar kuat

  • Saya penasaran basis-basisnya apa untuk rentang bilangan 1024-bit
    Saya tidak menemukan jawabannya secara online
  • Lagi pula, kalau hanya sedang mencari bilangan prima, Anda bisa memilih kandidat yang tampak seperti prima lalu mengonfirmasinya dengan uji deterministik

• Satu baris inline assembly membuat perkalian bilangan bulat besar gaya sekolah dasar menjadi sederhana: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
  Kalau bisa kembali ke masa lalu dan mengubah satu hal saja pada bahasa C, saya ingin memasukkan konsep perkalian melebar. Sayang Rust juga tidak memilikinya. Dukungan hardware ada di mana-mana. Cortex M0 bahkan tidak melakukan pembagian, tetapi punya perkalian melebar
  Ini kode dari implementasi RSA mainan yang sangat jelek yang saya tulis lama sekali: https://github.com/jcalvinowens/toy-rsa
  Alasan saya bisa bertahan hanya dengan uji Fermat adalah karena algoritmanya tidak akan bekerja jika bilangan-bilangan prima itu sebenarnya bukan prima. Uji Fermat cepat, dan satu kali enkripsi/dekripsi menghilangkan kemungkinan yang sangat kecil bahwa salah satunya adalah pembohong Fermat
  Namun saya tidak tahu apakah bisa dibuktikan bahwa tidak ada pasangan kunci RSA yang dapat berhasil mengenkripsi/mendekripsi pesan dengan nilai P/Q yang bukan prima. Dalam implementasi nyata, tentu saja ini bukan cara yang baku, tetapi saya belum pernah menemukan jawabannya

  • Menariknya, C sekarang punya bilangan bulat besar
    C23 menambahkan tipe _BitInt(N), dan misalnya untuk tipe 128 byte Anda bisa memakai _BitInt(1024)
    Namun dukungan compiler masih terbatas. Di Clang, agar N boleh lebih besar dari 128, Anda bisa memberi flag -fexperimental-max-bitint-width=N. Jika N lebih besar dari 128 dan Anda membagi _BitInt(N), compiler akan crash begitu saja, tetapi +, -, * bekerja sesuai harapan
  • Di Zig, hal ini relatif mudah
    Ada built-in @mulWithOverflow yang mengembalikan hasil beserta bit overflow, dan integer tersedia hingga (u|i)65535
    Bergantung pada apa yang dilakukan, setelah mendeteksi overflow Anda bisa menaikkannya ke tipe yang lebih besar, atau menaikkannya lebih dulu lalu memotongnya secara opsional
    Ada juga operator terpisah *| untuk perkalian saturating dan *% untuk perkalian wrapping. Itu bisa dipakai saat semantik seperti ini diperlukan. Overflow lainnya adalah perilaku tak terdefinisi yang termasuk pemeriksaan keselamatan, sehingga pada mode build Debug dan ReleaseSafe akan terjadi panic
  • Jika p dan q adalah bilangan Carmichael yang saling prima, RSA tetap bisa berhasil mengenkripsi dan mendekripsi pesan
    Namun p*q akan memiliki faktor prima yang lebih kecil, sehingga lebih mudah difaktorkan dan keamanannya menurun
  • Sejauh yang saya tahu, pada kebanyakan compiler C dan Rust, jika Anda melakukan cast ke tipe yang lebih besar lalu mengalikan, instruksi machine code yang tepat akan dihasilkan
  • Pretty Good Privacy(PGP) asli karya Philip Zimmermann tahun 1994 hanya memakai sieve dengan membagi oleh semua bilangan prima 16-bit yang diketahui, dan tabel itu dibuat dengan sieve Eratosthenes. Setelah itu diterapkan uji Fermat

• Penasaran berapa lama pekerjaan ini memakan waktu
  Saya pernah mengerjakan perkalian bilangan bulat besar sebagai proyek riset sarjana, dan itu memakan hampir dua semester. Saya mengimplementasikan Karatsuba, Toom-Cook, FFT kompleks, beberapa NTT, dan Schonhage-Strassen
  Bilangan prima hampir seperti sihir matematika. Bagi yang tertarik, A Friendly Introduction to Number Theory karya Silverman adalah buku matematika yang sangat bagus
  Sebagai catatan, tautan di halaman tertulis 4025051, bukan 40250519

• Tulisan yang bagus. Saya juga baru-baru ini menulis sedikit kode big integer sendiri untuk versi awal [0], dan saya ingat betapa menjengkelkannya menerjemahkan penjelasan tingkat tinggi di makalah matematika menjadi operasi nyata
  Namun ada sedikit keberatan
  Jika menggunakan seluruh rentang u64, angkanya bukan berbasis 2^64-1, melainkan berbasis 2^64. Setiap word memiliki rentang dari 0 sampai 2^64-1, sama seperti setiap digit desimal bernilai 0 sampai 9
  [0] https://github.com/LegionMammal978/bigfoot-sim

• Seperti optimasi terakhir, jika saat gagal tidak membuat bilangan acak baru dan hanya menambah angka sebesar 2, keamanannya sedikit melemah
  Karena bilangan prima tidak terdistribusi merata, ini akan bias ke arah bilangan prima yang berada tepat setelah celah prima yang besar

  • Saya membaca tentang hal itu saat melakukan riset
    Ini adalah kompromi antara kecepatan eksekusi dan keacakan bilangan prima, dan saya memilih kecepatan karena menilai bahwa jika 16 thread masing-masing mulai dari bilangan acak lalu berlomba mencari prima, itu menambahkan keacakan yang cukup
    Jika lebih menginginkan keacakan daripada kecepatan, mengganti +=2 dengan panggilan rng() adalah perubahan yang mudah

• Tulisan yang bagus dan ditulis dengan baik
  Sepertinya penulis bermaksud base-256, bukan base-255

• Beberapa angka berukuran 1–2KB cukup muat di cache L1, dan kalaupun tidak, ada cache L2 berukuran lebih dari megabyte dengan waktu akses sekitar 3 ns
  Di tulisan disebutkan bahwa kemungkinan harus menunggu baca/tulis RAM karena cache miss L1, tetapi bagian ini tidak dibahas lagi setelahnya
  Selain itu, ini hanya membahas pembuatan bilangan prima, jadi sebagian besar jebakan RSA terhindari, dan urandom seharusnya aman. Kalau kodenya bekerja dengan benar, tidak banyak hal yang bisa sangat keliru
  RSA punya beberapa isu terkait bilangan prima lemah yang perlu dihindari, tetapi saya tidak tahu apakah itu cukup umum untuk benar-benar menjadi masalah di sini

• Ini mengingatkan saya pada proyek tahun pertama kuliah beberapa dekade lalu
  Rekan proyek sekaligus teman saya, yang kemudian menjadi perwakilan lulusan, mengusulkan ide dan mengimplementasikan matematika intinya: membuat enkripsi RSA 4096-bit
  Saya ingat betapa lambatnya pembuatan bilangan prima pada implementasi akhirnya. Di workstation PA-RISC, pembuatannya memakan sekitar 20 menit
  Teman saya yang penggila matematika terus mengoptimalkan kode bahkan setelah proyek selesai, dan saya ingat ia membaca makalah tentang pengujian primalitas dan implementasi matematika big integer
  Misalnya, ada peningkatan besar ketika pada perkalian komposisi, jika salah satu bilangan adalah 0, perkalian dilewati dan hasilnya langsung dibuat 0

  • Pada perangkat keras yang lambat, jauh lebih baik membuat kunci kurva eliptik
    Kalau tidak, harus menunggu lama, atau mengorbankan keamanan yang tahan hingga masa depan

• Saya paham kenapa bit rendah disetel ke 1. Karena bilangan genap tidak pernah prima. Tentu saja 2 adalah pengecualian
  Tapi saya tidak mengerti kenapa bit tinggi juga disetel ke 1. Saya bukan ahli bilangan prima atau kriptografi, tetapi ini terlihat seperti mengorbankan 1 bit entropi yang tidak perlu. Apa yang saya lewatkan?

  • Jika bit tinggi selalu disetel dan bilangan prima dienkode dengan menyertakan bit itu, bilangan prima selalu dienkode dengan jumlah byte yang sama
    Encoding byte dengan panjang variabel bisa menimbulkan masalah dalam pertukaran data antarperangkat lunak yang berbeda jika spesifikasinya tidak sangat jelas dan pengujiannya tidak matang
    Lihat masalah yang muncul pada DHE berbasis RSA ketika kunci publik server memiliki nol di depan
  • Ini sama seperti membuat angka dua digit
    Jika digit pertamanya 0, itu bukan angka dua digit
  • Menyetel bit pertama ke 1 memang kehilangan 1 bit entropi, tetapi menjamin bahwa bilangan primanya cukup besar
    Tambahan lagi, dalam RSA kita mengalikan dua bilangan prima. Jika salah satunya 1024-bit, kalau ingatan saya benar, yang satunya sekitar 200-bit pun bisa mencapai jumlah bit entropi yang diperlukan untuk kunci
    Jadi jika kedua bilangan prima dibuat 1024-bit, ada sedikit margin tambahan juga
  • Benar, itu mengorbankan 1 bit entropi, tetapi masih tersisa 1022 bit
    Rasanya ini lebih aman daripada diminta bilangan prima 1024-bit lalu bingung apakah bilangan prima 1020-bit juga boleh. Sama seperti biasanya kita tidak menganggap 00042 sebagai angka 5 digit
    Secara teknis, pilihan optimal bisa berbeda tergantung persisnya digunakan untuk apa, tetapi metode dalam tulisan itu tampak sebagai default yang lebih aman
  • Mengorbankan 1 bit entropi agar yakin bilangan primanya tidak berakhir hanya 50-bit jelas tampak sebagai kompromi yang cukup masuk akal