Discrete logarithm আর Diffie–Hellman key exchange

১ · খোলা পথে একই গোপন চাবি — বাজারঘরের সমস্যা

কাল্পনিক অনলাইন দোকান বাজারঘরের ঢাকা অফিসে কাজ করেন রিনা, আর চট্টগ্রামের গুদামে সুমন। প্রতিদিন রিনা গুদামে কিছু গোপন অর্ডার কোড পাঠান। পর্ব ২৭ “Classical cipher — shift, affine আর frequency analysis”-এর মতো যেকোনো symmetric cipher-এ দুজনের হাতে একই গোপন key লাগে। সমস্যা হলো, দুজনের যোগাযোগের একমাত্র পথ ইন্টারনেট, আর ধরে নিতে হবে সেই পথে যা যায় তা সবাই পড়তে পারে। পথের এই শ্রোতার নাম দেওয়া যাক ইভা (ইংরেজিতে eavesdropper, অর্থাৎ আড়ি পেতে শোনা লোক)।

১৯৭০-এর দশকের আগে এর একটাই উত্তর জানা ছিল: বিশ্বস্ত বাহক দিয়ে key হাতে হাতে পাঠানো, অনেকটা সিলমোহর করা খামে চাবি পাঠানোর মতো। হাজার হাজার গ্রাহক আর সার্ভারের যুগে এটি অচল। প্রশ্নটি তাই এমন দাঁড়ায়: দুজন মানুষ, যারা আগে কখনো কিছু ভাগ করেননি, শুধু খোলা পথে কথা বলে কি একই গোপন সংখ্যায় পৌঁছাতে পারেন, যাতে সব কথা শুনেও ইভা সেই সংখ্যা না পান?

এই পর্বের মূল যন্ত্র একটি one-way function, অর্থাৎ এমন ফাংশন যা এক দিকে হিসাব করা সহজ কিন্তু উল্টো দিকে কঠিন বলে বিশ্বাস করা হয়। এখানে ফাংশনটি হলো k ↦ g^k mod p. পর্ব ২২-এর repeated squaring (Modular arithmetic) দিয়ে এটি দ্রুত, আর পর্ব ২৪-এ primitive root আর discrete logarithm-এর যে নাম শুধু উল্লেখ করা হয়েছিল, এখানে তার পূর্ণ গণিত আসবে। Inverse আর CRT আসবে পর্ব ২৩ থেকে, আর √n ধাপের ভাবনা পর্ব ২৫ থেকে।

২ · Cyclic group — mod p-এর গুণের চক্র

ঘড়ির কাঁটা বারো ঘর ঘুরে আবার শুরুতে ফেরে। mod p-এ একটি সংখ্যাকে বারবার নিজের সঙ্গে গুণ করলেও একই ঘটনা ঘটে: ঘাতগুলো একটি চক্রে ঘোরে। এই চক্রের ভাষা হলো group.

মৌলিক p-এর জন্য লিখি ℤ_p^* = {1, 2, …, p − 1}, অপারেশন গুণ mod p. এটি একটি group: দুটি সংখ্যা p দিয়ে বিভাজ্য না হলে Euclid-এর lemma অনুযায়ী তাদের গুণফলও বিভাজ্য নয় (বদ্ধতা); সাধারণ গুণের সংযোজন নিয়ম mod p-এও খাটে (পর্ব ২২); একক 1; আর gcd(a, p) = 1 বলে Bézout থেকে modular inverse আছে (পর্ব ২১). এর order p − 1 = φ(p). বিস্তারিত group তত্ত্ব আসবে পর্ব ৭০ “Group — symmetry, cyclic group আর Lagrange-এর উপপাদ্য”-এ; এখানে শুধু এই একটি group লাগবে।

পর্ব ২৪-এর উপপাদ্য ৫.৩(ক) বলে প্রতিটি মৌলিক p-এ অন্তত একটি primitive root আছে (সেখানে প্রমাণ বাদ রাখা হয়েছিল, পাঠ্যবইয়ের সূত্রসহ)। তাই ℤ_p^* সবসময় cyclic. নিচের ছবিতে p = 11, g = 2: প্রতিটি তীর মানে “2 দিয়ে গুণ করে mod 11”, আর দশ ধাপে সব দশটি ঘর ঘুরে 1-এ ফেরা।

প্রমাণ:

1. ধরুন i ≥ j. gⁱ ≡ g^j ⇔ g^j(g^i−j − 1) ≡ 0 ⇔ g^i−j ≡ 1, কারণ g^j-এর inverse আছে বলে তাকে কেটে দেওয়া যায়। — inverse দিয়ে গুণ, পর্ব ২৩
2. পর্ব ২৪-এর উপপাদ্য ৫.২ অনুযায়ী g^t ≡ 1 ⇔ ord_p(g) ∣ t. এখানে ord_p(g) = p − 1, তাই g^i−j ≡ 1 ⇔ (p − 1) ∣ (i − j). — order-এর ধর্ম
3. অর্থাৎ gⁱ ≡ g^j ⇔ i ≡ j (mod p − 1). — ধাপ ১–২
4. বিশেষ করে 0 থেকে p − 2-এর p − 1টি ঘাত সব আলাদা মান দেয় (one-to-one). ℤ_p^*-এরও ঠিক p − 1টি উপাদান, তাই সসীম সেটে one-to-one মানেই onto (পর্ব ১৬). ∎ — pigeonhole-এর যুক্তি

কোন g generator, তা চেনার জন্য সব ঘাত গোনার দরকার নেই। p − 1-এর মৌলিক উৎপাদক জানা থাকলে কয়েকটি ঘাতই যথেষ্ট।

প্রমাণ: d = ord_p(g) লিখি; পর্ব ২৪ অনুযায়ী d ∣ p − 1.

1. (⇒) g generator হলে d = p − 1. প্রতিটি q-এ (p − 1)/q < p − 1, আর d-এর চেয়ে ছোট কোনো ধনাত্মক ঘাতে g^t ≡ 1 হতে পারে না। তাই g^(p−1)/q ≢ 1. — order-এর সংজ্ঞা
2. (⇐) contrapositive দেখাই: g generator না হলে কোনো q-তে শর্ত ভাঙে। g generator না হলে d একটি প্রকৃত ভাজক, d < p − 1, তাই (p − 1)/d > 1. — contrapositive, পর্ব ৮
3. (p − 1)/d > 1-এর একটি মৌলিক উৎপাদক q নিন। তাহলে d ∣ (p − 1)/q, কারণ (p − 1)/q = d · ((p − 1)/d)/q আর ((p − 1)/d)/q একটি পূর্ণসংখ্যা। — বিভাজ্যতা
4. d ∣ (p − 1)/q, তাই উপপাদ্য ৫.২ (পর্ব ২৪) অনুযায়ী g^(p−1)/q ≡ 1, অর্থাৎ এই q-তে শর্ত ভাঙে। ∎ — order-এর ধর্ম

উদাহরণ: p = 23, p − 1 = 22 = 2 · 11. g = 5-এর জন্য 5¹¹ ≡ 22 ≡ −1 আর 5² ≡ 2, কোনোটিই 1 নয়, তাই 5 একটি generator. g = 2-এর জন্য 2¹¹ = 2048 = 23 · 89 + 1 ≡ 1, তাই 2 generator নয়; আসলে ord₂₃(2) = 11. পর্ব ২৪-এর উপপাদ্য ৫.৩(গ) থেকে mod 23-এ generator ঠিক φ(22) = 10টি: 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 (scratch-এ গুনে মেলানো)। বাস্তবে p − 1-এর উৎপাদক জানা না থাকলে এই পরীক্ষা চালানো যায় না; তাই নিরাপদ parameter এমনভাবে বানানো হয় যাতে p − 1-এর গঠন আগে থেকেই জানা থাকে (§৭-এর safe prime).

৩ · Discrete logarithm — সহজ দিক আর কঠিন দিক

সাধারণ লগারিদমে 10^x = 1000 হলে x = log₁₀ 1000 = 3. mod p-এর জগতেও একই প্রশ্ন করা যায়, শুধু উত্তর একটি পূর্ণসংখ্যা আর হিসাব ভাগশেষে।

ছবির চক্র থেকে mod 11-এ log₂ 9 = 6 (কারণ 2⁶ = 64 = 55 + 9), log₂ 3 = 8, log₂ 10 = 5. সাধারণ লগারিদমের মতো এখানেও গুণ যোগে পরিণত হয়, শুধু ঘাতের হিসাব mod p − 1-এ।

প্রমাণ:

1. x₁ = log_g h₁, x₂ = log_g h₂ লিখি। তাহলে g^{x₁ + x₂} = g^x₁g^x₂ ≡ h₁h₂. — ঘাতের নিয়ম
2. log_g(h₁h₂)-এর সংজ্ঞায় g^{log(h₁h₂)} ≡ h₁h₂. দুই ঘাত একই মান দেয়, তাই উপপাদ্য ২.৩-এ তারা mod p − 1-এ সমান। — উপপাদ্য ২.৩
3. দ্বিতীয় নিয়ম: g^k·x = (g^x)^k ≡ h^k, আর একই যুক্তি। ∎ — ঘাতের নিয়ম

উদাহরণ mod 11: 9 · 3 = 27 ≡ 5. log 9 + log 3 = 6 + 8 = 14 ≡ 4 (mod 10), আর সত্যিই 2⁴ = 16 ≡ 5 ✓. লক্ষ করুন, mod p নয়, mod p − 1: ঘাতের চক্রের দৈর্ঘ্য p − 1.

সহজ দিক: x থেকে g^x

Repeated squaring (পর্ব ২২) দিয়ে g^x mod p বের করতে x-এর bit-সংখ্যার প্রায় দ্বিগুণের বেশি গুণ লাগে না। x যদি 2048 bit-এর হয়, তাহলে বড়জোর প্রায় ৪,০০০ গুণ, আধুনিক যন্ত্রে এক সেকেন্ডের ক্ষুদ্র ভগ্নাংশ। Python-এ এটি একটি লাইন: pow(g, x, p). DSA কোর্সের পর্ব ৬২-এ এর কোড আর জটিলতা আছে।

কঠিন দিক: g^x থেকে x

উল্টো দিকে সবচেয়ে সরল পথ হলো brute force: g⁰, g¹, g², … একটি একটি করে বানিয়ে h-এর সঙ্গে মেলানো, যাতে খারাপ ক্ষেত্রে p − 1টি গুণ লাগে। 2048 bit-এর p-তে সেটি প্রায় 2²⁰⁴⁸ ধাপ, যা মহাবিশ্বের পরমাণুর আনুমানিক সংখ্যার চেয়েও বহু গুণ বেশি। আর সাধারণ লগারিদমের কৌশলও এখানে খাটে না। বাস্তব সংখ্যায় 2^x x বাড়লে বাড়ে, তাই অনুমান করে ছোট-বড় দেখে বাইনারি সার্চ করা যায়। কিন্তু mod 11-এ 2-এর ঘাত 1, 2, 4, 8, 5, 10, 9, 7, 3, 6: মান লাফিয়ে বেড়ায়, কোনো ক্রম নেই, তাই “আরেকটু বড় x নিন” বলার উপায় নেই।

এর মানে এই নয় যে brute force-এর চেয়ে ভালো কিছু নেই। §৬-এ আমরা √(p − 1) মাপের একটি পদ্ধতি দেখব, আর ℤ_p^*-এর জন্য আরও শক্তিশালী index calculus আর number field sieve পদ্ধতি আছে, যাদের সময় exponential-এর চেয়ে কম কিন্তু polynomial-এর চেয়ে বেশি; এদের বলে sub-exponential পদ্ধতি। তবু যথেষ্ট বড় আর সঠিকভাবে বাছা p-তে কোনো জানা algorithm-ই সাধারণ কম্পিউটারে যুক্তিসংগত সময়ে উত্তর দেয় না। গুরুত্বপূর্ণ কথা হলো, এটি একটি বিশ্বাস, প্রমাণ নয়। factoring-এর মতোই (পর্ব ২৫), DLP যে কঠিন তা কেউ প্রমাণ করেননি; প্রমাণ করতে পারলে P ≠ NP-এর চেয়েও শক্তিশালী একটি ফল প্রমাণ হতো।

৪ · Diffie–Hellman key exchange — প্রোটোকল আর প্রমাণ

এবার রঙ মেশানোর উপমাটি গণিতে লেখা যাক। Diffie–Hellman একটি key exchange প্রোটোকল: দুই পক্ষ খোলা পথে কয়েকটি সংখ্যা বিনিময় করে একই গোপন সংখ্যায় পৌঁছান। এটি public-key cryptography-র প্রথম প্রকাশিত উদাহরণ।

প্রমাণ:

1. B ≡ g^b, আর congruence-এর দুই পাশকে একই ঘাতে তোলা যায় (পর্ব ২২-এর গুণের নিয়ম বারবার), তাই B^a ≡ (g^b)^a. — congruence-এ ঘাত
2. (g^b)^a = g^ba = g^ab, পূর্ণসংখ্যার ঘাতের সাধারণ নিয়ম আর গুণের বিনিময় নিয়ম। — ঘাতের নিয়ম
3. একইভাবে A^b ≡ (g^a)^b = g^ab. দুটিই g^ab-এর সঙ্গে congruent আর দুটিই 0 থেকে p − 1-এর মধ্যে, তাই K = K′. ∎ — transitivity

প্রমাণটি এত ছোট যে প্রশ্ন জাগে, এর জোর কোথায়? জোর গণিতে নয়, অসমতায়: রিনা আর সুমন প্রত্যেকে দুটি দ্রুত ঘাত তোলেন, কিন্তু ইভাকে a বা b বের করতে একটি discrete logarithm সমাধান করতে হয়। নিচের stepper ক্লাসিক ছোট উদাহরণটি হাতে করে দেখায়: p = 23, g = 5, a = 6, b = 15.

1সর্বজনীন: p = 23, g = 52রিনা: a = 6 (গোপন)3A = 5^6 mod 23 = 84সুমন: b = 15 (গোপন)5B = 5^15 mod 23 = 196ইভা দেখেন: 23, 5, 8, 197রিনা: K = 19^6 mod 23 = 28সুমন: K = 8^15 mod 23 = 2

ইভা কী জানেন আর কী জানেন না, তা টেবিলে:

ইভার আসল প্রশ্নকে বলে computational Diffie–Hellman (CDH) সমস্যা: g, g^a আর g^b জেনে g^ab বের করা। DLP সমাধান করতে পারলে CDH-ও হয়: A থেকে a বের করে B^a নিলেই হলো। উল্টোটা, অর্থাৎ CDH সমাধান করতে পারলে DLP-ও পারা যায় কি না, সাধারণভাবে প্রমাণিত নয়। তাই Diffie–Hellman-এর নিরাপত্তা আসলে CDH (এবং বাস্তবে আরও শক্ত একটি অনুমান) কঠিন হওয়ার বিশ্বাসের ওপর দাঁড়িয়ে।

একটি লোভনীয় ভুল ধারণা: “ইভা A আর B গুণ করলেই তো key পান।” A · B ≡ g^a · g^b = g^a+b, যা g^ab নয়। ঘাতে যোগ আর গুণ গুলিয়ে ফেলা এই ভুলটিই রঙের উপমায় দুটি মিশ্রণ একসঙ্গে মেশানো। উপরের উদাহরণে A · B = 152 ≡ 14, অথচ K = 2. নিচের ব্লক একটু বড় মৌলিক p = 1000003-এ পুরো বিনিময় চালায়, generator নিজে খুঁজে নেয় (উপপাদ্য ২.৪ দিয়ে), আর stepper-এর সংখ্যাগুলো মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
random.seed(29)                       # fixed seed: same run every time
p = 1_000_003                         # prime; fine for learning, useless for security

def prime_factors(n):
    fs, d = [], 2
    while d * d <= n:
        if n % d == 0:
            fs.append(d)
            while n % d == 0: n //= d
        d += 1
    return fs + ([n] if n > 1 else [])

qs = prime_factors(p - 1)
g = next(c for c in range(2, p) if all(pow(c, (p - 1) // q, p) != 1 for q in qs))
print("primes of p-1:", qs, "| smallest generator g =", g)

a = random.randrange(2, p - 1)        # Rina's secret, never sent
b = random.randrange(2, p - 1)        # Sumon's secret, never sent
A, B = pow(g, a, p), pow(g, b, p)     # these travel over the open channel
print("Eve sees: p =", p, " g =", g, " A =", A, " B =", B)

key_r, key_s = pow(B, a, p), pow(A, b, p)
print("Rina's key =", key_r, " Sumon's key =", key_s, " equal:", key_r == key_s)
print("A*B mod p =", A * B % p, "(this is g^(a+b), not the key)")

mults = (a.bit_length() - 1) + (bin(a).count("1") - 1)
print(f"a = {a}: pow(g, a, p) needed only {mults} multiplications")
print("stepper (p=23, g=5, a=6, b=15):",
      pow(5, 6, 23), pow(5, 15, 23), pow(19, 6, 23), pow(8, 15, 23))

primes of p-1: [2, 3, 166667] | smallest generator g = 2
Eve sees: p = 1000003  g = 2  A = 784466  B = 307332
Rina's key = 496790  Sumon's key = 496790  equal: True
A*B mod p = 781442 (this is g^(a+b), not the key)
a = 574746: pow(g, a, p) needed only 26 multiplications
stepper (p=23, g=5, a=6, b=15): 8 19 2 2

৫ · Man-in-the-middle — গণিত ঠিক, তবু বিপদ

এ পর্যন্ত ইভা শুধু শুনছিলেন। এবার ধরুন তিনি পথের মাঝখানে বসে বার্তা বদলাতেও পারেন, যেমন একটি আপোসকৃত Wi-Fi রাউটার বা মাঝপথের কোনো যন্ত্র। একে বলে man-in-the-middle (মাঝের লোক) পরিস্থিতি। এখানে কোনো গণিত ভাঙা হয় না; শুধু ধারণাটি বোঝা দরকার, কারণ এটিই দেখায় Diffie–Hellman একা কী নিশ্চয়তা দেয় না।

উপপাদ্য ৪.২ ভুল হয়নি: রিনা সত্যিই যার সঙ্গে কথা বলছেন, তার সঙ্গে একই key পেয়েছেন। সমস্যা হলো সেই “কেউ” আসলে কে, তা Diffie–Hellman বলে না। গণিতের ভাষায়, প্রোটোকলটি গোপনীয়তা দেয় শুধু নিষ্ক্রিয় শ্রোতার বিরুদ্ধে; সক্রিয় প্রতিপক্ষের বিরুদ্ধে দরকার authentication, অর্থাৎ প্রমাণ যে A সত্যিই রিনার কাছ থেকে এসেছে।

বাস্তবে এটি করা হয় digital signature দিয়ে: সুমন নিজের দীর্ঘমেয়াদি গোপন key দিয়ে বিনিময়ের বার্তাগুলোয় সই করেন, আর রিনা আগে থেকে জানা বা certificate দিয়ে প্রত্যয়িত public key দিয়ে সই যাচাই করেন। ইভা E পাঠালে তাঁর কাছে সুমনের সই বানানোর key নেই, তাই প্রতারণা ধরা পড়ে। ওয়েবের HTTPS-এ TLS প্রোটোকল ঠিক এভাবে সার্ভারের certificate আর সই দিয়ে Diffie–Hellman-কে বাঁধে; Computer Networks কোর্সের পর্ব ৪৮ আর Cybersecurity কোর্সের পর্ব ১২-এ এর বিস্তারিত আছে। RSA-র সই কীভাবে কাজ করে, তার গণিত পর্ব ২৮ “RSA-এর গণিত — key, encryption আর কেন কাজ করে”-এ।

সই দিয়ে বাঁধা Diffie–Hellman-এর আরেকটি বড় সুবিধা আছে। প্রতিটি সংযোগে নতুন a আর b বানিয়ে কাজ শেষে মুছে ফেললে (ephemeral key), পরে কোনোদিন সার্ভারের দীর্ঘমেয়াদি সই-key চুরি হলেও আগের রেকর্ড করা আলাপ খোলা যায় না, কারণ সেই key দিয়ে শুধু সই হয়েছিল, a বা b বের হয় না। এই গুণের নাম forward secrecy, আর আধুনিক TLS 1.3 (RFC 8446, ২০১৮) certificate-ভিত্তিক সাধারণ সংযোগে শুধু এই ধরনের ephemeral key exchange রেখেছে; পুরোনো RSA key exchange সেখানে বাদ।

৬ · Brute force থেকে baby-step giant-step — √n-এর কৌশল

এখন ইভার দিক থেকে দেখা যাক, তবে শুধু আমাদের নিজের বানানো ছোট group-এ, কেন p বড় হতে হয় তা বুঝতে। ধরুন g-এর order n (ℤ_p^*-এর generator হলে n = p − 1), আর h = g^x, যেখানে 0 ≤ x < n. Brute force n পর্যন্ত গুণ নেয় আর প্রায় কোনো মেমরি নেয় না। Daniel Shanks-এর baby-step giant-step (সাধারণত ১৯৭১ সালের কাজ হিসেবে উল্লেখিত) মেমরির বিনিময়ে সময়কে √n-এ নামায়।

প্রমাণ:

1. Division algorithm-এ x = i₀m + j₀, যেখানে 0 ≤ j₀ < m. যেহেতু x ≤ n − 1 ≤ m² − 1, তাই i₀ = ⌊x/m⌋ ≤ m − 1. — division algorithm, পর্ব ২০
2. i-তম giant step-এ γ = h · g^−im = g^{x − im}. i = i₀-এ γ = g^j₀, যা টেবিলে আছে। তাই algorithm বড়জোর i₀ + 1 ≤ m giant step-এ থামে। — ঘাতের নিয়ম
3. যে প্রথম i-তে থামে, সেখানে γ = g^j, অর্থাৎ g^{x − im} = g^j, তাই g^{im + j} = h: ফেরত দেওয়া y = im + j সত্যিই একটি লগারিদম। — ধাপ ২
4. ফেরত দেওয়া y-ই x: ধাপ ৩-এ g^y = g^x, তাই y ≡ x (mod n) (উপপাদ্য ২.৩-এর যুক্তি, order n দিয়ে)। প্রথম থামা i ≤ i₀. যদি i < i₀ হয়, তবে 0 ≤ y ≤ (i + 1)m − 1 < i₀m ≤ x < n, অর্থাৎ 0 < x − y < n অথচ n ∣ x − y, যা অসম্ভব। তাই i = i₀, আর g^j = g^j₀ যেখানে 0 ≤ j, j₀ < m ≤ n, তাই j = j₀ আর y = x. — contradiction আর উপপাদ্য ২.৩
5. খরচ: টেবিল বানাতে m গুণ, c বের করতে একটি inverse আর একটি ঘাত, আর বড়জোর m giant step, প্রতিটিতে একটি গুণ আর একটি টেবিল-খোঁজ। ∎ — গণনা

নিচের stepper §৪-এর উদাহরণে ইভার ভূমিকা নেয়: p = 23, g = 5 (n = 22), আর সুমনের প্রকাশ্য মান h = 19. লক্ষ্য b = log₅ 19.

1n = 22, m = ⌈√22⌉ = 52baby: 5^j, j = 0..4 → 1, 5, 2, 10, 43c = 5^(−5) = 20^(−1) ≡ 154i = 0: γ = 19 ✗5i = 1: γ = 19·15 ≡ 9 ✗6i = 2: γ = 9·15 ≡ 20 ✗7i = 3: γ = 20·15 ≡ 1 ✓ (j = 0)8x = 3·5 + 0 = 15

এবার একটু বড় group: p = 1000003, g = 2, n = 1000002. নিচের ব্লক একটি গোপন x-এর লগারিদম brute force আর baby-step giant-step, দুই পদ্ধতিতে বের করে, ধাপ গোনে আর সময় মাপে।

import random, time
from math import isqrt
random.seed(6)
p, g = 1_000_003, 2                   # g = 2 generates all p - 1 residues
n = p - 1                             # the order of the group
secret = random.randrange(n)
h = pow(g, secret, p)                 # public: h = g^secret mod p

def brute(g, h, p):                   # try k = 0, 1, 2, ... in turn
    y = 1
    for k in range(p - 1):
        if y == h: return k, k + 1
        y = y * g % p

def bsgs(g, h, p, n):                 # Shanks: baby steps, then giant steps
    m = isqrt(n - 1) + 1              # m = ceil(sqrt(n))
    table, y = {}, 1
    for j in range(m):                # baby steps: store g^j -> j
        table.setdefault(y, j); y = y * g % p
    factor, gamma = pow(g, -m, p), h  # g^(-m) via the modular inverse
    for i in range(m):                # giant steps: h * g^(-i*m)
        if gamma in table: return i * m + table[gamma], m + i + 1
        gamma = gamma * factor % p

for name, solve in [("brute force", lambda: brute(g, h, p)),
                    ("baby-step giant-step", lambda: bsgs(g, h, p, n))]:
    t = time.perf_counter(); x, steps = solve(); t = time.perf_counter() - t
    print(f"{name:21s} x = {x}, steps = {steps:7d}, time = {t:.3f} s")
print("correct:", x == secret, "| sqrt(n) =", isqrt(n))
print("stepper (p=23, g=5, h=19):", bsgs(5, 19, 23, 22))

brute force           x = 831877, steps =  831878, time = 0.048 s
baby-step giant-step  x = 831877, steps =    1833, time = 0.000 s
correct: True | sqrt(n) = 1000
stepper (p=23, g=5, h=19): (15, 9)

Baby-step giant-step-এর দুর্বলতা মেমরি: √n-টি মান মনে রাখতে হয়। John Pollard ১৯৭৮ সালে discrete log-এর জন্যও একটি rho পদ্ধতি দেন, যা পর্ব ২৫-এর factoring-এর rho-এর মতো চক্র খুঁজে প্রায় একই √n সময়ে কিন্তু খুব কম মেমরিতে কাজ করে (এটিও heuristic, প্রমাণিত সীমা নয়)। দুটিই যেকোনো group-এ চলে, তাই এদের বলা হয় “generic” পদ্ধতি।

৭ · Pohlig–Hellman, safe prime আর আসল আকার

√n-এর হিসাব থেকে মনে হতে পারে, p বড় হলেই নিরাপদ। কিন্তু Stephen Pohlig আর Martin Hellman ১৯৭৮ সালে দেখান, group-এর order n-এর গঠনও সমান গুরুত্বপূর্ণ। যদি n = p − 1 অনেকগুলো ছোট মৌলিকের গুণফল হয়, তাহলে DLP ছোট ছোট টুকরোয় ভেঙে যায়, আর Chinese Remainder Theorem (পর্ব ২৩) টুকরোগুলো জোড়া দেয়।

প্রমাণ:

1. (ক) যেকোনো t ≥ 0-এ g′^t = g^kt ≡ 1 ⇔ n ∣ kt (order-এর ধর্ম, পর্ব ২৪) ⇔ q^ek ∣ kt ⇔ q^e ∣ t. তাই সবচেয়ে ছোট ধনাত্মক t হলো q^e. — order-এর ধর্ম
2. (খ) h′ = (g^x)^k = (g^k)^x = g′^x. — ঘাতের নিয়ম
3. g′-এর order q^e, তাই উপপাদ্য ২.৩-এর যুক্তিতে g′^x = g′^y ⇔ x ≡ y (mod q^e). অর্থাৎ order q^e-এর ছোট group-এ লগারিদম বের করলে পাওয়া যায় ঠিক x mod q^e. ∎ — উপপাদ্য ২.৩

Pohlig–Hellman পদ্ধতি তাই এরকম: n = q₁^e₁ ⋯ q_r^e_r লিখে প্রতিটি q_i^e_i-এর ছোট group-এ baby-step giant-step চালানো, আর পাওয়া x mod q_i^e_i-গুলো CRT দিয়ে জুড়ে x mod n বের করা। খরচ মোটামুটি ∑ √(q_i^e_i), আর আরেকটু কৌশলে ∑ e_i√q_i. অর্থাৎ নিরাপত্তা ঠিক করে n-এর সবচেয়ে বড় মৌলিক উৎপাদক, n-এর আকার নয়। যে সংখ্যার সব মৌলিক উৎপাদক ছোট, তাকে smooth বলে, আর p − 1 smooth হলে DLP সহজ।

প্রতিরক্ষা তাই সরল: এমন p নিন যাতে p − 1-এ একটি বিশাল মৌলিক উৎপাদক থাকে। সবচেয়ে পরিচ্ছন্ন বাছাই safe prime: p = 2q + 1, যেখানে q-ও মৌলিক। তখন p − 1 = 2q, আর ℤ_p^*-এর subgroup-গুলোর order শুধু 1, 2, q আর 2q. প্রায়ই g এমনভাবে বাছা হয় যাতে তার order ঠিক q (যেমন একটি বর্গসংখ্যা mod p), যাতে order-2-এর ছোট টুকরো থেকেও কিছু ফাঁস না হয়। মজার তথ্য: প্রোগ্রামিং প্রতিযোগিতার প্রিয় modulus 1000000007 নিজেই একটি safe prime (500000003-ও মৌলিক, scratch-এ যাচাই করা)।

নিচের ব্লক একই আকারের (প্রায় 10⁹) দুটি মৌলিকে একই গোপন x খোঁজে: একটির p − 1 smooth, অন্যটি safe prime.

from math import isqrt
def factor(n):                        # trial division; n is small here
    f, d = {}, 2
    while d * d <= n:
        while n % d == 0: f[d] = f.get(d, 0) + 1; n //= d
        d += 1
    if n > 1: f[n] = f.get(n, 0) + 1
    return f

def bsgs(g, h, p, n):                 # g has order n; returns (x, steps)
    m = isqrt(n - 1) + 1; table, y = {}, 1
    for j in range(m): table.setdefault(y, j); y = y * g % p
    c, gam = pow(g, -m, p), h
    for i in range(m):
        if gam in table: return i * m + table[gam], m + i + 1
        gam = gam * c % p

def pohlig_hellman(g, h, p):
    n, x, M, steps = p - 1, 0, 1, 0
    for q, e in factor(n).items():
        qe = q ** e; k = n // qe      # jump into the subgroup of order q^e
        xi, s = bsgs(pow(g, k, p), pow(h, k, p), p, qe)
        steps += s
        t = (xi - x) * pow(M, -1, qe) % qe   # CRT: x mod M and xi mod qe
        x, M = x + M * t, M * qe
    return x, steps

secret = 123_456_789
for p, g in [(1_000_361_363, 2), (1_000_000_007, 5)]:
    h = pow(g, secret, p)
    x, steps = pohlig_hellman(g, h, p)
    print(f"p = {p}, p - 1 = {factor(p - 1)}")
    print(f"   x = {x}, correct: {pow(g, x, p) == h}, group steps: {steps}")
print("one BSGS on a group of order 10^9 needs up to", 2 * isqrt(10**9), "steps")

p = 1000361363, p - 1 = {2: 1, 7: 2, 11: 1, 13: 2, 17: 2, 19: 1}
   x = 123456789, correct: True, group steps: 68
p = 1000000007, p - 1 = {2: 1, 500000003: 1}
   x = 123456789, correct: True, group steps: 27886
one BSGS on a group of order 10^9 needs up to 63244 steps

বাস্তবের আকার — তারিখসহ, সতর্কভাবে

Generic পদ্ধতির বাইরে ℤ_p^*-এর জন্য index calculus আর number field sieve-এর মতো sub-exponential পদ্ধতি আছে, তাই এখানে p-এর আকার √n-এর হিসাবের চেয়ে অনেক বড় রাখতে হয়। কয়েকটি প্রকাশিত, তারিখযুক্ত তথ্য (নিজে মূল উৎসে মিলিয়ে নিন, কারণ সুপারিশ সময়ের সঙ্গে বদলায়):

• রেকর্ড: ২০১৯ সালের ডিসেম্বরে Boudot, Gaudry, Guillevic, Heninger, Thomé আর Zimmermann-এর দল একটি ২৪০ দশমিক অঙ্কের (প্রায় ৭৯৫ bit) safe prime-এ discrete logarithm সমাধানের ঘোষণা দেন, বিশাল কম্পিউটিং সময় খরচ করে।
• Logjam (২০১৫): Adrian ও সহকর্মীদের গবেষণায় দেখা যায়, পুরোনো “export” মানের ৫১২ bit Diffie–Hellman ব্যবহারিকভাবে ভাঙা যায়, আর অনেক সার্ভার একই কয়েকটি p ভাগ করে ব্যবহার করত বলে একটি p-এর জন্য একবার বড় প্রস্তুতিমূলক হিসাব করলে বহু সংযোগে কাজে লাগে। তাঁদের অনুমান ছিল, ১০২৪ bit-ও বড় রাষ্ট্রীয় সম্পদের নাগালে থাকতে পারে।
• সুপারিশ: NIST SP 800-57 Part 1 (Rev. 5, ২০২০)-এর টেবিলে finite-field Diffie–Hellman-এ ২০৪৮ bit p মোটামুটি ১১২ bit নিরাপত্তার সমান, আর ৩০৭২ bit প্রায় ১২৮ bit-এর। TLS-এর জন্য RFC 7919 (২০১৬) ffdhe2048 থেকে ffdhe8192 নামের নির্দিষ্ট safe-prime group দেয়।
• Quantum: Peter Shor-এর ১৯৯৪ সালের algorithm factoring-এর মতো discrete log-ও polynomial সময়ে সমাধান করে, তবে তার জন্য বড় ও নির্ভুল quantum কম্পিউটার লাগে, যা এখনো তৈরি হয়নি। এ কারণে post-quantum পদ্ধতিতে সরে যাওয়ার কাজ চলছে; Cybersecurity কোর্সের পর্ব ১৪-এ, আর এই কোর্সের পর্ব ৩০-এর শেষে এর উল্লেখ আছে।

৮ · ElGamal encryption — Diffie–Hellman থেকে public-key encryption

Diffie–Hellman শুধু একটি key দেয়, বার্তা পাঠায় না। Taher ElGamal ১৯৮৫ সালে প্রকাশিত কাজে দেখান, একই ভাবনা দিয়ে সরাসরি public-key encryption বানানো যায়: গুদামের একটি স্থায়ী public key থাকে, আর যেকোনো কর্মী সেটি দিয়ে বার্তা বন্ধ করতে পারেন, কিন্তু খুলতে পারে শুধু গুদাম। ভাবনাটি হলো, প্রেরক প্রতিবার নিজে একটি নতুন Diffie–Hellman অর্ধেক বানান, আর পাওয়া key দিয়ে বার্তাকে গুণ করে ঢেকে দেন।

প্রমাণ:

1. s = c₁^x ≡ (g^k)^x = g^kx = (g^x)^k ≡ h^k. — ঘাতের নিয়ম, উপপাদ্য ৪.২-এর মতো
2. h^k ∈ ℤ_p^*, অর্থাৎ p দিয়ে বিভাজ্য নয়, তাই s⁻¹ আছে। — Euclid-এর lemma আর inverse
3. c₂ · s⁻¹ ≡ m · h^k · (h^k)⁻¹ ≡ m. আর 1 ≤ m ≤ p − 1, তাই ভাগশেষটি ঠিক m. ∎ — inverse-এর সংজ্ঞা

একটি ছোট সুবিধা: s⁻¹ আলাদা করে বের না করে Fermat-এর ছোট উপপাদ্য দিয়ে সরাসরি c₁^p−1−x নেওয়া যায়, কারণ c₁^x · c₁^p−1−x = c₁^p−1 ≡ 1. নিচের stepper ধরে নেয় গুদামের গোপন x = 6 (তাই h = 5⁶ ≡ 8, §৪-এর A), আর হাতে এসেছে ciphertext (17, 18).

1গোপন x = 6, c = (c₁, c₂) = (17, 18)217² ≡ 13, 17⁴ ≡ 13² ≡ 83s = 17⁶ = 17⁴·17² ≡ 8·13 ≡ 12412·2 = 24 ≡ 1 ⇒ s⁻¹ = 25m = 18·2 = 36 ≡ 136যাচাই: k = 7, 5⁷ ≡ 17, 13·8⁷ ≡ 18

ElGamal-এর তিনটি বৈশিষ্ট্য মনে রাখার মতো। প্রথমত, এটি randomised: একই m দুবার encrypt করলে আলাদা k-এর কারণে আলাদা ciphertext আসে, তাই ইভা “এই দুটি বার্তা একই” বলতে পারেন না। এর দাম হলো ciphertext বার্তার দ্বিগুণ লম্বা। দ্বিতীয়ত, k-কে প্রতিবার নতুন আর অনুমান-অযোগ্য হতে হয়, অর্থাৎ CSPRNG থেকে আসতে হয় (পর্ব ২৬)। একই k দুবার দিলে দুটি c₂-এর অনুপাত m₂/m₁, তাই একটি বার্তা জানা থাকলে অন্যটি x ছাড়াই বেরিয়ে আসে। তৃতীয়ত, textbook ElGamal malleable: c₂-কে 2 দিয়ে গুণ করলে decrypt হয় 2m, অথচ কেউ টের পায় না। তাই বাস্তবে ElGamal-এর ভাবনাটি সরাসরি বার্তায় নয়, একটি key বানাতে ব্যবহৃত হয়, আর বার্তা যায় authenticated encryption দিয়ে; সাথে বার্তাকে একটি মৌলিক order-এর subgroup-এ বসানোর মতো সূক্ষ্ম শর্তও লাগে। নিচের ব্লক তিনটি বৈশিষ্ট্যই নিজের toy উদাহরণে দেখায়।

import random
random.seed(28)
p, g = 1_000_003, 2                   # toy group: NEVER for real data
x = random.randrange(2, p - 1)        # warehouse's private key
h = pow(g, x, p)                      # public key, published for everyone

def encrypt(m, h):
    k = random.randrange(2, p - 1)    # a fresh ephemeral k for every message
    return pow(g, k, p), m * pow(h, k, p) % p

def decrypt(c1, c2, x):
    s = pow(c1, x, p)                 # shared secret s = g^(xk)
    return c2 * pow(s, -1, p) % p     # m = c2 * s^(-1)

code = 4729                           # toy secret order code, m < p
ca, cb = encrypt(code, h), encrypt(code, h)
print("same message, two ciphertexts:", ca, cb)
print("both decrypt to:", decrypt(*ca, x), decrypt(*cb, x))

c1, c2 = ca                           # malleable: Enc(m) -> Enc(2m)
print("c2 doubled decrypts to:", decrypt(c1, 2 * c2 % p, x))

k = 777                               # mistake: the same k twice
m1, m2 = 1111, 4729                   # m1 is known (say, a public notice)
e1 = (pow(g, k, p), m1 * pow(h, k, p) % p)
e2 = (pow(g, k, p), m2 * pow(h, k, p) % p)
leak = e2[1] * pow(e1[1], -1, p) * m1 % p
print("same c1:", e1[0] == e2[0], "| m2 recovered without x:", leak)
print("stepper (p=23, x=6, c=(17,18)):",
      pow(17, 6, 23), pow(12, -1, 23), 18 * 2 % 23)

same message, two ciphertexts: (931214, 279574) (800037, 398484)
both decrypt to: 4729 4729
c2 doubled decrypts to: 9458
same c1: True | m2 recovered without x: 4729
stepper (p=23, x=6, c=(17,18)): 12 2 13

ElGamal-এর সই-পদ্ধতিও আছে (একই ১৯৮৫ সালের কাজে), আর তার একটি রূপান্তর থেকে NIST-এর Digital Signature Algorithm (DSA) এসেছে বলে সাধারণত বলা হয়।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই বিষয়ের যে ধাঁচের অঙ্ক আসে, তার চারটি পূর্ণ সমাধান। প্রতিটি সংখ্যা scratch-এ Python দিয়ে মেলানো।

অঙ্ক ১: p = 11, g = 2, a = 4, b = 7 হলে Diffie–Hellman-এর A, B আর K কত?

1. A = 2⁴ = 16 ≡ 5 (mod 11). B = 2⁷ = 128 = 11 · 11 + 7 ≡ 7.
2. রিনা: K = B^a = 7⁴. 7² = 49 ≡ 5, তাই 7⁴ ≡ 25 ≡ 3.
3. সুমন: A^b = 5⁷. 5² ≡ 3, 5⁴ ≡ 9, 5⁷ = 5⁴ · 5² · 5 ≡ 9 · 3 · 5 = 135 ≡ 3. দুজনেরই K = 3. যাচাই: ab = 28 ≡ 8 (mod 10), 2⁸ = 256 ≡ 3 ✓.

অঙ্ক ২: 3 আর 2 কি mod 17-এর generator?

1. p − 1 = 16 = 2⁴, মৌলিক উৎপাদক শুধু 2. উপপাদ্য ২.৪ অনুযায়ী শুধু g⁸ দেখলেই চলে।
2. 3² = 9, 3⁴ = 81 ≡ 13, 3⁸ ≡ 169 ≡ 16 ≢ 1, তাই 3 generator.
3. 2⁸ = 256 = 17 · 15 + 1 ≡ 1, তাই 2 generator নয় (ord₁₇(2) = 8). mod 17-এ generator মোট φ(16) = 8টি।

অঙ্ক ৩: baby-step giant-step দিয়ে 2^x ≡ 9 (mod 11) সমাধান করুন

1. n = 10, m = ⌈√10⌉ = 4. Baby step: 2^0..3 = 1, 2, 4, 8.
2. c = 2⁻⁴: 2⁴ = 16 ≡ 5, আর 5 · 9 = 45 ≡ 1, তাই c = 9.
3. i = 0: γ = 9, টেবিলে নেই। i = 1: γ = 9 · 9 = 81 ≡ 4 = 2², তাই j = 2 আর x = 1 · 4 + 2 = 6. যাচাই: 2⁶ = 64 ≡ 9 ✓.

অঙ্ক ৪: ElGamal, p = 11, g = 2, x = 3, বার্তা m = 7, k = 4

1. Public key h = 2³ = 8. c₁ = 2⁴ ≡ 5. h^k = 8⁴ = 4096 ≡ 4, তাই c₂ = 7 · 4 = 28 ≡ 6. Ciphertext (5, 6).
2. Decrypt: s = 5³ = 125 ≡ 4 (encrypt-এর h^k-এর সমান), s⁻¹ = 3 (কারণ 4 · 3 = 12 ≡ 1).
3. m = 6 · 3 = 18 ≡ 7 ✓.

প্রমাণের ভুল ধরুন: “শেয়ার করা key হলো A · B”

একজন লিখলেন: “দাবি: Diffie–Hellman-এ রিনা আর সুমনের key হলো A · B mod p. প্রমাণ: রিনার key B^a = (g^b)^a. ঘাতের নিয়মে (g^b)^a = g^b · g^a = g^a+b. আবার A · B = g^ag^b = g^a+b. তাই key = A · B. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: দ্বিতীয় বাক্যের “ঘাতের নিয়ম” ভুল লেখা: (g^b)^a = g^ab, g^a+b নয়। g^a · g^b = g^a+b হলো গুণের নিয়ম, ঘাতের ঘাতের নয়। দাবিটি সত্য হলে ইভা শুধু শুনে key পেতেন, আর Diffie–Hellman অর্থহীন হতো। Counterexample: §৪-এর উদাহরণে A · B = 8 · 19 = 152 ≡ 14, অথচ key 2. ভুলটি ধরা পড়ে সবচেয়ে ছোট সংখ্যায় দুই দিক হিসাব করলেই।

১০ · AI-এর যুগে — discrete log আর key exchange-এর দাবি যাচাই

AI সহকারী Diffie–Hellman-এর ব্যাখ্যা চমৎকার দেয়, কিন্তু হিসাব আর শর্তে নিয়মিত কিছু ভুল করে। এগুলো চেনা থাকলে ধরতে এক মিনিট লাগে।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি modular ঘাত আর inverse নিজে pow() দিয়ে মিলিয়েছি
• Diffie–Hellman-এ দুই পক্ষের key সত্যিই সমান এসেছে
• Generator দাবি করলে p − 1-এর সব মৌলিক উৎপাদক দিয়ে পরীক্ষা হয়েছে
• প্রমাণে ঘাতের নিয়ম ঠিক আছে ((g^a)^b = g^ab, g^ag^b = g^a+b), আর converse নিঃশব্দে ঢোকেনি
• নিরাপত্তার পরামর্শে authentication, বড় parameter আর যাচাই করা library-র কথা আছে
• রেকর্ড, সাল আর মানপত্রের নম্বর বিশ্বস্ত উৎসে মিলিয়েছি

এই পর্বের প্রায় প্রতিটি দাবি p = 23-এর মতো ছোট মৌলিকে এক সেকেন্ডে brute force করা যায়; AI-এর “সবসময়” বা “কখনো না” দাবি পেলে আগে ছোট ক্ষেত্রে counterexample খুঁজুন।