1024-बिट prime बनाने की कठिनाई

 (glitchcomet.com)
4 पॉइंट द्वारा GN⁺ 2024-05-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 2048-बिट RSA key के लिए जरूरी लगभग 1024-बिट के दो prime numbers को Rust में सीधे generate करने का यह एक प्रयोग है, जिसमें external dependencies के बिना random number generation से लेकर large integer operations तक implement किए गए
  • साधारण trial division 16-बिट पर करीब 40ms में पर्याप्त था, लेकिन 64-बिट पर भी optimization के बाद 6.4 सेकंड लगे, इसलिए इसे 1024-बिट तक scale करना मुश्किल था
  • Fermat test तेज है, लेकिन pseudoprime को filter नहीं कर सकता, इसलिए अंतिम निर्णय के लिए k=10 वाला Miller-Rabin test इस्तेमाल किया गया
  • built-in integer type की limits से आगे जाने के लिए खुद BigInt बनाया गया; bool array से byte array और फिर u64 chunk structure में बदलने पर 1024-बिट prime generation का समय 32 मिनट के स्तर से घटकर 60~90 सेकंड तक आ गया
  • अंतिम implementation ने u64 chunk BigInt, fast division, छोटे primes पर trial division, candidate value को +2 से बढ़ाना, और 16 threads में parallel execution को जोड़कर औसतन लगभग 40ms में 1024-बिट prime ढूंढ लिया, लेकिन यह verified crypto library नहीं है

RSA के लिए 1024-बिट prime खुद बनाना

  • लक्ष्य था RSA key generation में इस्तेमाल हो सकने वाला prime खुद generate करना
    • 2048-बिट RSA key दो primes के product से बनती है, इसलिए हर एक के लिए करीब 1024-बिट size का prime चाहिए
    • challenge स्वाभाविक रूप से 1024-बिट prime generation तक सीमित हो गया
  • प्रयोग पर तीन constraints रखे गए
    • code शुरुआत से लिखा जाएगा और external dependencies इस्तेमाल नहीं की जाएंगी
    • external hardware या cloud के बिना AMD Ryzen 7 CPU और 16GB RAM वाले laptop का इस्तेमाल होगा
    • prime “reasonable time” के भीतर generate होना चाहिए
  • language के लिए हाल में सीखी जा रही Rust चुनी गई
    • low-level concepts से निपटने के लिए यह पर्याप्त करीब है, और code snippets समझने के लिए पर्याप्त high-level भी है

16-बिट और 64-बिट पर दिखी trial division की सीमा

  • basic flow यह था कि N-बिट random number बार-बार generate किया जाए और primality test pass होते ही रुक जाए
  • random number Rust के rand crate की जगह Linux के /dev/urandom को सीधे पढ़कर बनाया गया
    • /dev/urandom Linux kernel के CSPRNG तक पहुंच देने वाली pseudo device file है
    • kernel user environment से entropy collect करता है और ChaCha20-based deterministic stream cipher को समय-समय पर seed करता है
  • 16-बिट random number में first bit और last bit को 1 set किया गया
    • last bit 1 odd number ensure करने के लिए था
    • first bit 1 जरूरी bit range पूरा इस्तेमाल करने का तरीका था
  • 16-बिट में 3 से sqrt(num) तक divide करके देखने वाला trial division ही करीब 40ms में prime ढूंढने के लिए काफी था
    • example run में Prime found: 44809 था, और कुल समय करीब 0.038 सेकंड था
  • 64-बिट तक बढ़ाने पर simple trial division में करीब 30 सेकंड लगे
    • बाद में सिर्फ 6k±1 form वाले candidates check करने और छोटे primes की list से पहले divide करके देखने की approach से सुधार किया गया
    • सुधार के बाद 64-बिट prime generation time करीब 6.414 सेकंड था
  • 64-बिट पर भी 6 सेकंड लगने से साफ हो गया कि इस method से 1024-बिट prime generation तक पहुंचना मुश्किल है

probabilistic primality testing की ओर switch

  • deterministic algorithms में APR-CL और ECPP देखे गए, लेकिन वे mathematically complex थे और accessible explanations कम थीं, इसलिए उन्हें implement करने लायक target बनाना मुश्किल था
  • OpenSSL source code और NIST recommendations देखने के बाद पुष्टि हुई कि RSA सहित practical use cases में probabilistic primality testing व्यापक रूप से इस्तेमाल होती है
  • इसके बाद algorithm किसी number को “prime साबित” करने के बजाय, उसे एक निश्चित accuracy के साथ probable prime बताने के तरीके में बदल गया

  • Fermat test

    • Fermat's little theorem इस relation का इस्तेमाल करता है कि अगर p prime है और a, p से divisible नहीं है, तो a^(p-1) = 1 mod p होता है
    • simple exponentiation में u128 overflow हो जाता है, इसलिए modular exponentiation implement किया गया
    • pow() exponent को u32 के रूप में लेता है, और u128 को बड़े exponent तक बढ़ाने पर overflow हो सकता है
    • multiplication भी u128 range से बाहर जा सकती है, इसलिए अस्थायी रूप से 64-bit numbers को u128 के अंदर store करके आगे बढ़ा गया
    • Fermat test तेज है, लेकिन Fermat pseudoprime के कारण composite number को गलत तरीके से prime मान सकता है
    • ऐसे composite numbers rare होने के बावजूद पर्याप्त संख्या में मिलते हैं, इसलिए सिर्फ Fermat test भरोसेमंद नहीं लगा

  • Miller-Rabin test

    • Miller-Rabin, Fermat test जैसे ही principles पर आधारित है, लेकिन इसे ज्यादा strong probabilistic primality testing algorithm के रूप में इस्तेमाल किया जाता है
    • implementation में n-1 = 2^s × d form में powers of 2 को अलग किया गया और फिर कई conditions check की गईं
    • a^d = 1 mod n
    • या किसी 0 <= r < s के लिए a^(2^r × d) = n - 1 mod n
    • 128-बिट प्रयोग में Fermat test की तरह ही करीब 0.042 सेकंड में prime मिला
    • Miller-Rabin की worst-case error bound 4^-k है; बड़े n पर average में यह लगभग 8^-k के स्तर की होती है
    • k=10 पर average error probability calculation 0.000000000931323% था
    • इसकी तुलना coin को लगातार 30 बार उछालने पर हर बार heads आने की probability 2^-30 से की गई
    • real cryptographic use में random base selection और adversarial conditions को लेकर और सावधानी चाहिए

खुद BigInt बनाना

  • Rust के built-in integer types से 64-बिट से ज्यादा बड़े numbers संभालना मुश्किल था, इसलिए arbitrary-precision integer (BigInt) implementation जरूरी हो गया
  • external bigint crate न इस्तेमाल करने की constraint के कारण BigInt भी खुद implement किया गया

  • कोशिश 1: digit array

    • शुरुआत में बड़े number को decimal digits array के रूप में store करने का तरीका आजमाया गया
    • addition और multiplication को hand calculation की तरह implement किया जा सकता था, लेकिन division implementation पर अटकने के कारण यह छोड़ दिया गया

  • कोशिश 2: bool-based binary array

    • दूसरा तरीका number को 0 और 1 के array के रूप में store करने वाला structure था
    • BigInt ने [bool; 2048] array इस्तेमाल किया
    • दो 1024-बिट numbers multiply करने पर maximum 2048-bit space चाहिए, इसलिए 2048 bits रखे गए
    • addition और subtraction full adder approach से implement किए गए
    • multiplication binary number की property का इस्तेमाल करके shift-and-add method से handle किया गया
    • division binary long division से implement किया गया
    • इस implementation से पहला 1024-बिट prime ढूंढने में सफलता मिली, लेकिन run time करीब 32 मिनट 44.90 सेकंड था
    • technically लक्ष्य पूरा हुआ, लेकिन यह “reasonable time” वाली constraint पर खरा नहीं उतरा

  • कोशिश 3: byte chunks

    • यह पता चला कि bool array का हर bool 1 bit नहीं बल्कि 1 byte लेता है
    • [bool; 2048] 2048 bits नहीं, बल्कि 2048 bytes इस्तेमाल कर रहा था
    • इसके बाद 2048 bits को 256-byte array में store करने का तरीका अपनाया गया
    • addition, subtraction, multiplication बिना बड़े बदलाव के काम करते रहे, और division को byte chunks को bit list की तरह handle करने के लिए adjust किया गया
    • इस तरीके से 1024-बिट prime generation time घटकर 4 मिनट 43 सेकंड हो गया

  • कोशिश 4: u64 chunks

    • byte chunk approach असल में higher radix digits इस्तेमाल करने वाला digit-based BigInt था
    • अगले step में 2048 bits को 32 u64 chunks में store किया गया
    • हर chunk एक “digit” की तरह behave करता है
    • दो u64 chunks के product को रखने के लिए u128 इस्तेमाल किया गया
    • इस structure में 1024-बिट number को 309 decimal digits के बजाय 16 u64 chunks में represent किया जा सकता है
    • 1024-बिट prime generation time सुधरकर 60~90 सेकंड हो गया

bottleneck optimization

  • simple benchmark में binary implementation और u64 chunk implementation का फर्क साफ था
    • a + b और a - b: 5537.35ns → 123.57ns
    • a * b: 1292283.14ns → 842.32ns
    • a / b और a % b: 733446.76ns → 44440.12ns
    • a < b और a > b: 2506.02ns → 58.91ns
  • इसके बाद optimization मुख्य रूप से division, multiplication, Miller-Rabin internal operations, और candidate generation logic पर केंद्रित रहा

  • division

    • सबसे बड़ा bottleneck division था
    • u64 chunk structure में भी existing division अब भी एक-एक bit करके long division करता था
    • Handbook of Applied Cryptography के page 598 वाले algorithm का reference लेकर radix-based long division implement किया गया
    • dividend के पहले 3 “digits” और divisor के पहले 2 “digits” से current quotient “digit” estimate करने का तरीका था
    • इस implementation ने division के हर call पर करीब 40,000ns बचाए
    • अगर divisor single u64 chunk हो, तो u128 इस्तेमाल करके ज्यादा direct long division करने के लिए special handling की गई
    • Miller-Rabin में ऐसे cases अक्सर आते हैं

  • multiplication

    • multiplication में intermediate result store करने वाले BigInt को हटाने के लिए loops rearrange किए गए, जिससे यह करीब 2 गुना तेज हो गया
    • occupied chunks की count calculate करके loops सिर्फ non-zero chunks पर चलाए गए
    • BigInt mostly 1024-bit या उससे छोटे numbers store करता है, इसलिए 2048-bit space का आधा हिस्सा अक्सर खाली रहता है
    • Karatsuba या FFT-based multiplication भी consider किया गया, लेकिन उन्हें खुद implement करना complex था और current multiplication पर्याप्त तेज माना गया

  • Miller-Rabin internal optimization

    • Miller-Rabin implementation में costly operations घटाने पर focus किया गया
    • x = mod_exp(x, 2, n) की जगह सीधे x = (x * x) % n किया गया
    • पहले mod_exp() को simplified inline version में बदला गया, ताकि function call overhead घटे
    • even number check के लिए num.is_even() जोड़ा गया, जिससे % 2 calculation से बचा जा सके
    • d / 2 को d >>= 1 से बदला गया
    • += 1, -= 1 को increase() और decrease() से special-case किया गया
    • खास तौर पर is_even() और d >>= 1 से प्रत्येक ने करीब 70,000ns का फायदा दिया
    • final benchmark में u64 chunk optimized version काफी तेज हो गया
    • a * b: 842.32ns → 295.04ns
    • a / b और 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

final 1024-बिट prime generator

  • final function पहले /dev/urandom से 1024-bit random number पढ़ता है
    • most significant bit set करके 1024-bit size ensure किया जाता है
    • least significant bit set करके odd number ensure किया जाता है
  • इसके बाद हर बार नया random number दोबारा पढ़ने के बजाय, candidate value में 2 जोड़कर अगले odd candidate पर move किया जाता है
    • increase_by_2() ज्यादातर सिर्फ एक u64 chunk की addition करता है
  • Miller-Rabin से पहले छोटे primes की list से trial division किया जाता है
    • final code में पहले 1000 छोटे primes इस्तेमाल किए गए
    • छोटे primes single u64 chunk में fit होते हैं, इसलिए fast single-chunk division special handling का लाभ मिल सकता है
  • इस problem को shared memory या threads के बीच synchronization की जरूरत न होने वाले embarrassingly parallel form में handle किया जा सकता है
    • 16 CPU threads हर एक prime ढूंढते हैं, और जो thread सबसे पहले result भेजता है, उसका value इस्तेमाल किया जाता है
  • final run example में करीब 0.086 सेकंड elapsed time दर्ज हुआ
    • CPU usage 690% दिखा
  • 100 runs का average 0.04109 ± 0.00307 सेकंड था
    • average में करीब 40ms में 1024-bit prime मिल गया
    • individual prime_1024bit() call randomness के कारण करीब 8ms से लगभग 800ms तक vary कर सकता है
    • parallel execution से सबसे तेज result चुनकर variation कम किया गया

code और limitations

  • पूरा code और repository github पर public हैं
  • discussion links hackernews और reddit पर हैं
  • यह implementation वास्तविक cryptographic safety के लिहाज से भरोसेमंद नहीं माना जाना चाहिए, और इसका उद्देश्य crypto library बनाना नहीं बल्कि learning और implementation experiment है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-05-05
Hacker News की रायें

  • कुछ cryptocurrencies थीं जो बड़े prime numbers खोजने के काम को proof-of-work function के हिस्से के रूप में इस्तेमाल करती थीं, और करीब 8 साल पहले सिर्फ बहुत तेज़ primality testing implementation से भी काफी पैसा कमाया जा सकता था
    मैं कुछ समय तक riecoin mining software का author और maintainer था; वजह ठीक से नहीं जानता, शायद बस primes पसंद थे
    यह लेख तेज़ primality testing के नंबर-1 optimization, Montgomery multiplication, को छोड़ देता है: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
    यह practical high-speed modular exponentiation implementations की बुनियाद है
    Niall Emmart, जो उस समय academia में थे और जहाँ तक मुझे पता है अब Nvidia में हैं, ने सचमुच बेहद तेज़ GPU big-integer library CGBN रिलीज़ की थी: https://github.com/NVlabs/CGBN
    यह अब भी मेरी जानकारी में सबसे तेज़ batch modular exponentiation implementation है, और अगर थोड़ी देर nerd की तरह तारीफ़ करूँ तो यह सांस रोक देने वाली चीज़ है
    कभी इस बारे में लिखना चाहिए कि इसकी बदौलत मैंने एक छोटी cryptocurrency के production पर करीब 5 साल तक कैसे दबदबा बनाए रखा। और Python में pow(x, y, m) के तीन-argument form के जरिए x^y % m calculate करने वाला काफी अच्छा modular exponentiation मौजूद है
    इसे इस्तेमाल करके, अगर खुद implement करना चाहें तो Fermat या Miller-Rabin primality test बनाना बहुत आसान और काफी मज़ेदार है। खुद नहीं बनाना चाहते तो gmp library का mpz_probab_prime() भी अच्छा है। gmp जाहिर है तेज़ है, लेकिन बड़े prime numbers से खेलते समय दो-line Fermat test के मज़े को मात देना मुश्किल है

    • Niall तेज़ multi-scalar multiplication से जुड़े ZPrize-winning submissions में से एक में भी शामिल थे
      यह batch modular exponentiation से closely related है, फर्क यह है कि यह prime modulo के बजाय elliptic curve पर काम करता है। मैं इसे CGBN work की अगली कड़ी मानता हूँ
      पिछले साल Stanford cryptography lunch seminar में उन्होंने अच्छा talk दिया था, और slides व recording online हैं
      https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
      https://www.youtube.com/watch?v=KAWlySN7Hm8
    • जिज्ञासा है कि ऐसी cryptocurrencies ने ऐसा custom proof-of-work function क्यों इस्तेमाल किया
      क्या उनके पास बस यह धुंधला विचार था कि cryptography किसी तरह primes का उपयोग करती है, लेकिन यह नहीं पता था कि कब और क्यों, या इसके पीछे कोई गहरी वजह थी—यह जानना चाहूँगा
    • pow(x,e,mod) की वजह से मैं Perl से Python पर चला गया

  • अगर किसी दिए गए maximum number range की सीमा हो, तो Miller-Rabin को effectively deterministic बनाना आसान है
    ऐसे bases चुन लें जो उस range के भीतर सभी pseudoprimes को साथ में filter out करने के लिए साबित किए गए हों
    list भी लंबी नहीं होती। Miller-Rabin सचमुच बहुत powerful है

    • 1024-bit numbers की range में वे bases क्या होंगे, यह जानने की जिज्ञासा है
      online जवाब नहीं मिला
    • ऊपर से अगर आप बस primes खोज रहे हैं, तो prime जैसा दिखने वाला candidate चुनकर उसे deterministic test से verify कर सकते हैं

  • inline assembly की एक line से big-integer का grade-school multiplication आसान हो जाता है: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
    अगर अतीत में जाकर C language में सिर्फ एक चीज़ बदल सकता, तो widening multiplication की concept जोड़ना चाहूँगा। अफसोस है कि Rust में भी यह नहीं है। hardware support हर जगह है। Cortex M0 division तक नहीं करता, लेकिन widening multiplication है
    यह code बहुत पहले लिखे मेरे बेहद बदसूरत toy RSA implementation से है: https://github.com/jcalvinowens/toy-rsa
    Fermat test भर से काम चल पाने की वजह यह थी कि अगर primes सच में prime न हों तो algorithm काम ही नहीं करता था। Fermat test तेज़ है, और encryption/decryption का एक round इस बेहद छोटी संभावना को भी हटा देता है कि दोनों में से कोई एक Fermat liar हो
    हालांकि मुझे नहीं पता कि यह prove किया जा सकता है या नहीं कि non-prime P/Q values के साथ भी message को सफलतापूर्वक encrypt/decrypt कर सकने वाली RSA keypair मौजूद नहीं होती। असली implementation में यह जाहिर है standard तरीका नहीं होगा, लेकिन मुझे इसका जवाब कभी नहीं मिला

    • दिलचस्प बात यह है कि C में अब big-integers हैं
      C23 में _BitInt(N) type जोड़ा गया है, और उदाहरण के लिए 128-byte type के रूप में _BitInt(1024) इस्तेमाल कर सकते हैं
      हालांकि compiler support सीमित है। Clang में N को 128 से बड़ा allow कराने के लिए -fexperimental-max-bitint-width=N flag दे सकते हैं। N अगर 128 से बड़ा हो और आप _BitInt(N) को divide करें, तो compiler बस crash कर जाता है, लेकिन +, -, * उम्मीद के मुताबिक काम करते हैं
    • Zig में यह अपेक्षाकृत आसान है
      @mulWithOverflow built-in function है, जो result के साथ overflow bit लौटाता है, और integers (u|i)65535 तक हैं
      आप क्या कर रहे हैं, उसके अनुसार overflow detect करने के बाद बड़े type में promote कर सकते हैं, या पहले promote करके फिर selectively truncate कर सकते हैं
      इसके अलावा अलग operators *| से saturating multiplication और *% से wrapping multiplication support हैं। ऐसी semantics की जरूरत हो तो इस्तेमाल कर सकते हैं। बाकी overflow safety checks के दायरे में आने वाला undefined behavior है, इसलिए Debug और ReleaseSafe build modes में panic होता है
    • अगर p और q coprime Carmichael numbers हों, तो RSA अभी भी message को सफलतापूर्वक encrypt और decrypt कर सकता है
      हालांकि p*q के छोटे prime factors होंगे, इसलिए factorization आसान हो जाएगी और security कम हो जाएगी
    • मेरी समझ में ज्यादातर C compilers और Rust में, बड़े type में cast करके multiply करने पर ठीक वही machine instruction generate होती है जो चाहिए
    • Philip Zimmermann की 1994 की original Pretty Good Privacy(PGP) ने सिर्फ सभी ज्ञात 16-bit primes से divide करने वाली sieve इस्तेमाल की थी, और वह table Sieve of Eratosthenes से बनाई गई थी। उसके बाद Fermat test लगाया गया था

  • यह काम करने में कितना समय लगा, यह जानने की उत्सुकता है
    मैंने undergraduate research project के तौर पर बड़े integer multiplication पर काम किया था, और इसमें लगभग दो semesters लग गए थे। Karatsuba, Toom-Cook, complex FFT, कुछ NTT, और Schonhage-Strassen implement किए थे
    primes तो लगभग mathematical magic जैसे हैं। जिनकी रुचि हो, उनके लिए Silverman की A Friendly Introduction to Number Theory एक बेहतरीन math book है
    वैसे पेज पर link 40250519 की जगह 4025051 है

  • अच्छा लेख है। मैंने भी हाल ही में [0] के शुरुआती version के लिए अपना थोड़ा big integer code लिखा था, और याद है कि math papers की high-level explanations को असली operations में बदलना कितना frustrating होता है
    हालांकि एक छोटी आपत्ति है
    अगर आप u64 की पूरी range इस्तेमाल कर रहे हैं, तो number 2^64-1 base में नहीं बल्कि 2^64 base में है। हर word की range 0 से 2^64-1 तक होती है, ठीक वैसे ही जैसे decimal में हर digit 0 से 9 तक होती है
    [0] https://github.com/LegionMammal978/bigfoot-sim

  • आखिरी optimization की तरह failure होने पर नया random number generate करने के बजाय number को 2 से बढ़ाते रहने से security थोड़ी टूटती है
    primes uniformly distributed नहीं होते, इसलिए bias उन primes की तरफ होता है जो बड़े prime gap के ठीक बाद आते हैं

    • research करते समय मैंने इसके बारे में पढ़ा था
      यह execution speed और prime की randomness के बीच trade-off है, और मैंने speed को चुना क्योंकि लगा कि 16 threads, जो हर एक random number से शुरू करके prime खोजने की race करेंगे, पर्याप्त randomness जोड़ देंगे
      अगर आपको speed से ज्यादा randomness चाहिए, तो +=2 को rng() call से बदलना आसान बदलाव है

  • अच्छा लेख है और अच्छी तरह लिखा गया है
    लगता है लेखक का मतलब base-255 नहीं, बल्कि base-256 था

  • कुछ 1~2KB numbers आसानी से L1 cache में आ जाते हैं, और अगर न भी आएं तो L2 cache megabytes से ज्यादा होता है, जिसका access time लगभग 3ns है
    लेख में कहा गया था कि L1 cache misses की वजह से शायद RAM read/write का इंतजार करना पड़ा होगा, लेकिन बाद में इस हिस्से पर वापस नहीं आया गया
    साथ ही, यह सिर्फ prime generation से जुड़ा है, इसलिए RSA के ज्यादातर pitfalls से बच जाता है, और urandom safe होना चाहिए। अगर code सही से काम करता है तो बहुत ज्यादा चीजें गलत होने की गुंजाइश नहीं है
    RSA में बचने लायक weak primes से जुड़े कुछ issues हैं, लेकिन नहीं पता कि यहां वे सचमुच problem बनने जितने common हैं या नहीं

  • कुछ दशक पहले के अपने first-year college project की याद आ गई
    मेरे project partner और दोस्त, जो बाद में valedictorian बना, ने idea दिया और core math implement किया; goal था 4096-bit RSA encryption बनाना
    final implementation में prime generation कितनी slow थी, यह याद है। PA-RISC workstation पर generate करने में लगभग 20 minutes लगते थे
    मेरा math-nerd दोस्त project खत्म होने के बाद भी code optimize करता रहा, और मुझे याद है वह primality testing और big integer math implementation papers पढ़ता रहता था
    उदाहरण के लिए, constructed multiplication में अगर कोई number 0 हो तो multiplication skip करके result 0 देने से जबरदस्त improvement हुआ था

    • slow hardware पर elliptic-curve keys generate करना कहीं बेहतर है
      वरना या तो लंबा इंतजार करना पड़ेगा, या भविष्य तक टिकने वाली security से समझौता करना होगा

  • low bit को 1 set करना समझ में आता है, क्योंकि even numbers कभी prime नहीं होते। बेशक 2 exception है
    लेकिन high bit भी 1 पर क्यों set किया जाता है, यह समझ नहीं आया। primes या cryptography का expert नहीं हूं, लेकिन यह बेवजह entropy का 1 bit छोड़ने जैसा लगता है। मैं क्या miss कर रहा हूं?

    • अगर high bit हमेशा set हो और prime को उस bit तक include करके encode किया जाए, तो prime हमेशा समान number of bytes में encode होता है
      variable-length byte encoding, अगर specification बहुत clear और tests अच्छे नहीं हों, तो अलग-अलग software के बीच data exchange में problems पैदा कर सकता है
      server public key में leading 0 होने पर RSA-based DHE में होने वाली problem देख लें
    • यह two-digit number generate करने जैसा है
      अगर first digit 0 है, तो वह two-digit number नहीं है
    • first bit को 1 set करने से entropy का 1 bit खोता है, लेकिन यह guarantee मिलती है कि prime पर्याप्त बड़ा है
      एक बात और जोड़ें तो RSA में दो primes को multiply किया जाता है। अगर एक 1024-bit है, तो याद सही हो तो दूसरा लगभग 200-bit होने पर भी key के लिए जरूरी entropy bits तक पहुंच सकता है
      इसलिए दोनों primes को 1024-bit रखने से थोड़ी extra margin भी मिलती है
    • entropy का 1 bit छोड़ना सही है, लेकिन फिर भी 1022 bits बचते हैं
      किसी ने 1024-bit prime मांगा हो और 1020-bit prime भी ठीक है या नहीं, इस पर सोचने से यह ज्यादा safe लगता है। यह वैसा ही है जैसे आम तौर पर 00042 को 5-digit number नहीं माना जाता
      technically, exact use case के हिसाब से optimal choice बदल सकती है, लेकिन लेख का तरीका ज्यादा safe default लगता है
    • पक्का 50-bit तक सीमित न रह जाने वाला prime बनाने के लिए entropy का 1 bit खोना काफी ठीक trade-off लगता है