RSA-এর গণিত — key, encryption আর কেন কাজ করে

১ · গোপন বার্তা, খোলা রাস্তা — public key-এর ধারণা

কাল্পনিক অনলাইন দোকান বাজারঘর প্রতিদিন রাজশাহীর গুদামে একটি গোপন অর্ডার কোড পাঠায়। বার্তা যায় ইন্টারনেটের খোলা রাস্তা দিয়ে, যেখানে পথের যেকোনো যন্ত্র তা পড়তে পারে। পর্ব ২৭ “Classical cipher — shift, affine আর frequency analysis”-এর সব cipher-এ একটি সমস্যা আছে: প্রেরক আর প্রাপকের কাছে একই গোপন key থাকতে হয়। সেই key প্রথমবার পৌঁছাবে কীভাবে? খোলা রাস্তায় পাঠালে তো সেটিও চুরি হয়ে যায়। এটিকে বলে key বণ্টনের সমস্যা।

একটি দৈনন্দিন উপমা ভাবুন। গুদামের ম্যানেজার শতখানেক খোলা তালা বানিয়ে সবাইকে বিলিয়ে দিলেন, কিন্তু চাবি রাখলেন নিজের পকেটে। বাজারঘর একটি বাক্সে কাগজ রেখে একটি খোলা তালা “খট” করে লাগিয়ে দিল। তালা লাগাতে চাবি লাগে না, কিন্তু খুলতে লাগে। এখন বাক্সটি খোলা রাস্তায় পাঠানো যায়; পথে কেউ তালা দেখলেও খুলতে পারবেন না, এমনকি বাজারঘর নিজেও না। আগে থেকে কোনো গোপন কথা ভাগ না করেই গোপনীয়তা পাওয়া গেল। এটিই public-key cryptography-র মূল ধারণা: খোলা তালাটি public key, আর চাবিটি private key, দুটি মিলে একটি key pair.

শব্দভান্ডার আর ফাংশনের ভাষা

মূল বার্তাকে বলে plaintext, আর লুকানো রূপকে ciphertext. গণিতের ভাষায় encryption একটি ফাংশন E: M → C, আর decryption একটি ফাংশন D: C → M, যাতে প্রতিটি বার্তা m-এ D(E(m)) = m. অর্থাৎ E অবশ্যই one-to-one হতে হবে, নইলে দুটি ভিন্ন বার্তা একই ciphertext দিত আর প্রাপক বুঝতেন না কোনটি পাঠানো হয়েছিল (পর্ব ১৬-এর bijection আর inverse function). RSA-তে M = C = {0, 1, …, n − 1}, আর আমরা প্রমাণ করব E এই সেটের একটি permutation.

সতর্কতা: কোনো ফাংশন সত্যিই one-way কি না, তা আজও প্রমাণিত নয়; প্রমাণ হলে P ≠ NP প্রমাণ হয়ে যেত (DSA কোর্সের পর্ব ৬৪). আমরা যা ব্যবহার করি, তা হলো কয়েক দশকের চেষ্টার পরও যাদের উল্টো দিক দ্রুত করার উপায় পাওয়া যায়নি, এমন ফাংশন। RSA-র প্রার্থী হলো m ↦ m^e mod n: পর্ব ২২-এর repeated squaring-এ এটি সহজ, কিন্তু n-এর উৎপাদক না জেনে উল্টো দিকে (e-তম মূল mod n) যাওয়ার কোনো দ্রুত পদ্ধতি জানা নেই। trapdoor হলো n-এর উৎপাদক p আর q.

পুরো পর্বে একটিই ছোট উদাহরণ চলবে, নিচের ছবিতে যার সারসংক্ষেপ: গুদাম নিজের key বানায়, public অংশ প্রকাশ করে, বাজারঘর তা দিয়ে অর্ডার কোড m = 65 লুকায়, আর খোলা রাস্তায় শুধু ciphertext যায়।

২ · Key তৈরি — p, q থেকে (n, e) আর d

প্রতিটি ধাপের কারণ আছে। ধাপ ৪-এর শর্ত gcd(e, φ(n)) = 1 না থাকলে ধাপ ৫-এর modular inverse থাকতই না: পর্ব ২১-এর Bézout অনুযায়ী ax ≡ 1 (mod m)-এর সমাধান আছে ঠিক তখন, যখন gcd(a, m) = 1, আর extended Euclid সেটি বের করে। আর ধাপ ৩-এর সূত্রটি দুটি ভিন্ন মৌলিকের জন্যই সত্য।

প্রমাণ:

1. 1 থেকে pq পর্যন্ত একটি সংখ্যা x, pq-এর সঙ্গে সহমৌলিক নয় ⇔ p ∣ x বা q ∣ x, কারণ pq-এর মৌলিক উৎপাদক শুধু p আর q. — মৌলিক উৎপাদকে বিশ্লেষণ
2. p-এর গুণিতক আছে q-টি (p, 2p, …, qp), আর q-এর গুণিতক p-টি। দুটোরই গুণিতক মানে lcm(p, q) = pq-এর গুণিতক, এই সীমায় শুধু pq নিজে। — গণনা
3. অন্তর্ভুক্তি-বর্জনে সহমৌলিক নয় এমন সংখ্যা q + p − 1টি, তাই φ(pq) = pq − p − q + 1 = (p − 1)(q − 1). ∎ — বীজগণিত

এবার হাতে একটি key বানানো যাক। বইয়ে বহুল প্রচলিত উদাহরণ p = 61, q = 53, e = 17; নিচের stepper প্রতিটি সংখ্যা দেখায়, আর d বের করে extended Euclid দিয়ে।

1p = 61, q = 532n = 61 · 53 = 32333φ = 60 · 52 = 312043120 = 17 · 183 + 9517 = 9 · 1 + 869 = 8 · 1 + 171 = 2 · 3120 − 367 · 178d = −367 + 3120 = 2753

বাস্তবে e প্রায় সবসময় 65537 = 2¹⁶ + 1 নেওয়া হয়: এটি মৌলিক, আর এর binary রূপে মাত্র দুটি 1, তাই encryption আর signature যাচাই দ্রুত। p আর q খোঁজা হয় পর্ব ২৫-এর Miller–Rabin পরীক্ষা দিয়ে এলোমেলো বড় বিজোড় সংখ্যার মধ্যে; প্রায় সমান মাপের দুটি মৌলিকের গুণফল n একটি semiprime. key তৈরির পর φ(n) আর p, q-কে private key-এর অংশ হিসেবে গোপন রাখতে হয়, কারণ যেকোনো একটি ফাঁস হলে d বেরিয়ে আসে (§৬).

৩ · Encryption আর decryption — বিশাল ঘাত, দ্রুত হিসাব

m^e-কে সরাসরি হিসাব করা অসম্ভব: 2048-bit n আর 2048-bit d-তে c^d-এর অঙ্কসংখ্যা মহাবিশ্বের পরমাণুর সংখ্যাকেও ছাড়িয়ে যায়। সমাধান পর্ব ২২-এর binary exponentiation, বা repeated squaring: ঘাতকে binary-তে লিখে বারবার বর্গ করুন আর প্রতি ধাপে mod n নিন, যাতে কোনো মধ্যবর্তী সংখ্যা n²-এর চেয়ে বড় না হয়। k-bit ঘাতে লাগে k − 1টি বর্গ আর বড়জোর k − 1টি গুণ, অর্থাৎ O(log d) গুণ। এই modular exponentiation-ই RSA-র প্রতিটি কাজের ইঞ্জিন। নিচে আমাদের key দিয়ে m = 65 লুকানো আর ফেরত আনা।

1e = 17 = 10001₂265² = 4225 ≡ 992365⁴ ≡ 992² ≡ 1232465⁸ ≡ 1232² ≡ 1547565¹⁶ ≡ 1547² ≡ 7896c ≡ 789 · 65 ≡ 27907d = 2753 = 2¹¹+2⁹+2⁷+2⁶+182790→1295→3177→2195→65

এবার Python-এ পুরো খেলনা RSA. নিচের ব্লক ৩ অঙ্কের দুটি মৌলিক এলোমেলোভাবে (স্থির seed-এ) বেছে key বানায়, একটি অর্ডার কোড encrypt আর decrypt করে, একটি অর্ডারে সই দেয় ও যাচাই করে (§৫-এ বিস্তারিত), আর শেষে stepper-এর key-এ 0 থেকে 3232 পর্যন্ত প্রতিটি বার্তা পরীক্ষা করে। Python-এর pow(a, b, m) নিজেই repeated squaring চালায়, আর pow(e, -1, phi) extended Euclid দিয়ে inverse দেয় (Python 3.8 থেকে)। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random, hashlib
from math import gcd
random.seed(28)                       # toy demo: never generate real keys like this
primes = [x for x in range(100, 1000) if all(x % k for k in range(2, int(x**0.5) + 1))]

p, q = random.sample(primes, 2)       # two different 3-digit primes
n, phi = p * q, (p - 1) * (q - 1)
e = next(k for k in (17, 5, 7, 11, 13, 19, 23) if gcd(k, phi) == 1)
d = pow(e, -1, phi)                   # e*d = 1 (mod phi), extended Euclid inside
print(f"p={p} q={q} n={n} phi={phi} e={e} d={d} (e*d mod phi = {e * d % phi})")

m = 4207                              # Bazarghar's secret order code, 0 <= m < n
c = pow(m, e, n)                      # encrypt with the PUBLIC key (n, e)
print("plaintext", m, "-> ciphertext", c, "-> decrypted", pow(c, d, n))

def digest(text):                     # toy: SHA-256 squeezed into 0..n-1
    return int.from_bytes(hashlib.sha256(text.encode()).digest(), "big") % n

order = "ORDER-42: 3 kg chal to Rajshahi"
s = pow(digest(order), d, n)          # sign with the PRIVATE exponent d
print("signature", s, "valid:", pow(s, e, n) == digest(order))
fake = "ORDER-42: 30 kg chal to Rajshahi"
print("same signature on changed order valid:", pow(s, e, n) == digest(fake))

N, D = 61 * 53, 2753                  # the stepper key: check EVERY message
bad = [x for x in range(N) if pow(pow(x, 17, N), D, N) != x]
shared = sum(gcd(x, N) > 1 for x in range(N))
print(f"n=3233: {N} messages checked, failures {len(bad)}, "
      f"messages sharing a factor with n: {shared}")

p=251 q=277 n=69527 phi=69000 e=17 d=24353 (e*d mod phi = 1)
plaintext 4207 -> ciphertext 15669 -> decrypted 4207
signature 63895 valid: True
same signature on changed order valid: False
n=3233: 3233 messages checked, failures 0, messages sharing a factor with n: 113

৪ · কেন কাজ করে — সঠিকতার প্রমাণ

দাবি করতে হবে D(E(m)) = (m^e)^d mod n = m^ed mod n = m. মূল তথ্য ed ≡ 1 (mod φ(n)), অর্থাৎ কোনো পূর্ণসংখ্যা k ≥ 0-এর জন্য ed = 1 + k·φ(n). (k ≥ 0, কারণ e, d ≥ 1 বলে ed ≥ 1.) প্রথমে সহজ ক্ষেত্র, যেখানে পর্ব ২৪-এর Euler-এর উপপাদ্য সরাসরি খাটে।

প্রমাণ:

1. ed = 1 + kφ(n), k ≥ 0. তাই m^ed = m · (m^φ(n))^k. — ঘাতের নিয়ম
2. gcd(m, n) = 1, তাই Euler-এর উপপাদ্যে m^φ(n) ≡ 1 (mod n). — Euler, পর্ব ২৪
3. অতএব m^ed ≡ m · 1^k = m (mod n). ∎ — congruence-এর গুণ

কিন্তু m যদি p বা q-এর গুণিতক হয়? তখন gcd(m, n) > 1, আর Euler-এর শর্ত ভেঙে যায়। এমন বার্তা বিরল (n = 3233-এ 113টি, বড় n-এ প্রায় শূন্য অনুপাত), তবু একটি এনক্রিপশন পদ্ধতিকে প্রতিটি বার্তায় কাজ করতে হয়; “প্রায় সবসময় ঠিক” পদ্ধতি গণিতে ভুল পদ্ধতি। পূর্ণ প্রমাণে n-এর বদলে আলাদাভাবে p আর q দেখা হয়, তারপর জোড়া লাগানো হয়, ঠিক পর্ব ২৩-এর Chinese Remainder Theorem-এর ভাবনায়।

প্রমাণ: ed = 1 + k(p − 1)(q − 1), k ≥ 0.

1. দাবি: m^ed ≡ m (mod p). ক্ষেত্র (ক) p ∤ m: Fermat-এর ছোট উপপাদ্যে m^p−1 ≡ 1 (mod p), তাই m^ed = m · (m^p−1)^k(q−1) ≡ m · 1 = m (mod p). — Fermat, পর্ব ২৪
2. ক্ষেত্র (খ) p ∣ m: তখন m ≡ 0, আর ed ≥ 1 বলে m^ed ≡ 0 (mod p). দুই পাশই 0, তাই m^ed ≡ m (mod p). — সরাসরি
3. একই যুক্তিতে (p আর q-এর ভূমিকা বদলে) m^ed ≡ m (mod q). — প্রতিসাম্য
4. অর্থাৎ X = m^ed − m-কে p ভাগ করে আর q ভাগ করে। p আর q ভিন্ন মৌলিক, তাই সহমৌলিক, আর তখন pq ∣ X (পর্ব ২১-এর Euclid-এর lemma থেকে; এটিই CRT-এর অনন্যতার অংশ)। — সহমৌলিক ভাজকের গুণফল
5. তাই m^ed ≡ m (mod n). 0 ≤ m < n হলে m নিজেই তার ভাগশেষ, অর্থাৎ D(E(m)) = m. ∎ — least residue-এর অনন্যতা

এখান থেকে একটি সুন্দর ফল আসে: E হলো {0, 1, …, n − 1}-এর একটি permutation, আর D তার inverse function. কারণ D ∘ E = identity, তাই E one-to-one (পর্ব ১৬), আর একটি সসীম সেট থেকে নিজের মধ্যে one-to-one ফাংশন onto-ও (pigeonhole). একই প্রমাণে de = ed, তাই E ∘ D = identity-ও সত্য, যা §৫-এর signature-কে সম্ভব করে।

৫ · Digital signature — d দিয়ে সই, e দিয়ে যাচাই

গোপনীয়তা ছাড়াও খোলা রাস্তায় আরেকটি প্রশ্ন আছে: গুদাম কীভাবে নিশ্চিত হবে যে অর্ডারটি সত্যিই বাজারঘর পাঠিয়েছে, আর পথে কেউ “3 kg” বদলে “30 kg” করেনি? কাগজে এর উত্তর হাতের সই। গণিতে উত্তর digital signature: এমন একটি মান, যা শুধু private key-এর মালিক বানাতে পারেন, কিন্তু public key দিয়ে যে কেউ যাচাই করতে পারেন। এবার বাজারঘরের নিজের key pair (n, e, d) লাগবে, আর সে নিজের d দিয়ে সই করবে।

সঠিকতা উপপাদ্য ৪.২ থেকেই আসে: s^e = h^de = h^ed ≡ h (mod n). কিন্তু সরাসরি M-এ সই না করে আগে hash কেন? তিনটি কারণ। প্রথমত, বার্তা যত লম্বাই হোক, hash ছোট আর n-এর চেয়ে ছোট রাখা যায়। দ্বিতীয়ত, §৭-এ দেখবেন textbook RSA গুণ মানে: দুটি সই s₁, s₂ থেকে s₁s₂ mod n হয় h₁h₂-এর বৈধ সই (প্রমাণ অনুশীলন ১-এ)। h যদি বার্তা নিজেই হতো, তবে দুটি সই দেখে কেউ তৃতীয় একটি বার্তার সই বানিয়ে ফেলতেন। তৃতীয়ত, যে কেউ যেকোনো s নিয়ে h = s^e mod n বানিয়ে “সই-সহ বার্তা” দাবি করতে পারেন; hash থাকলে সেই h-এর পেছনে অর্থপূর্ণ বার্তা খোঁজা কঠিন। এই রীতিকে বলে hash-then-sign. Hash function-এর বাস্তব নিরাপত্তা-শর্ত Cybersecurity কোর্সের পর্ব ০৯-এ আছে।

নিচের stepper আমাদের ছোট key-এ (n = 3233, e = 17, d = 2753) একটি অর্ডারে সই দেয়। খেলনা হিসেবে SHA-256-এর ২৫৬-bit hash-কে mod 3233 নিয়ে ১২ bit-এ নামানো হয়েছে; বাস্তবে এটি কখনো করা হয় না। সই দেওয়া হয়েছে CRT দিয়ে (দুটি ছোট ঘাত, §৮-এ পূর্ণ ব্যাখ্যা), আর যাচাই repeated squaring-এ।

1M = "ORDER-42: 3 kg chal"2h = H(M) mod 3233 = 13003s_p = 19⁵³ mod 61 = 464s_q = 28⁴⁹ mod 53 = 165s = 16 + 53 · 42 = 224262242→2482→1459→1367→15715 · 2242 ≡ 1300 = h ✓8"30 kg": h′ = 72 ≠ 1300 ✗

৬ · নিরাপত্তা কিসের ওপর দাঁড়িয়ে — factoring আর তার চেয়েও বেশি

আড়িপাতা ব্যক্তি জানেন n, e আর c. d পেলেই সব শেষ। d বের করার সবচেয়ে সোজা পথ: n-কে factor করে p, q বের করা, তারপর φ(n) আর একটি inverse. উল্টো দিকেও কিছু সত্য: φ(n) জানা আর factor জানা আসলে সমান।

প্রমাণ:

1. φ(n) = (p − 1)(q − 1) = pq − (p + q) + 1 = n − (p + q) + 1, তাই S = p + q = n − φ(n) + 1 জানা। — Lemma ২.২ খুলে লেখা
2. p আর q হলো x² − Sx + n = 0-এর দুটি মূল, কারণ (x − p)(x − q) = x² − (p + q)x + pq. — Vieta-র সম্পর্ক
3. দ্বিঘাত সূত্রে p, q = (S ± √(S² − 4n)) / 2; এখানে শুধু একটি পূর্ণসংখ্যার বর্গমূল লাগে, যা বড় সংখ্যাতেও দ্রুত। ∎ — দ্বিঘাত সমীকরণ

উদাহরণ: n = 3233, φ = 3120 হলে S = 114, S² − 4n = 12996 − 12932 = 64, √64 = 8, তাই p, q = (114 ± 8)/2 = 61, 53. আরও জানা আছে যে d (e-সহ) জানলেও একটি randomized পদ্ধতিতে n দ্রুত factor করা যায়; প্রমাণটি এখানে বাদ। তাই “d গোপন রাখা” আর “p, q গোপন রাখা” একই দাবি। কিন্তু একটি প্রশ্ন আজও খোলা: d ছাড়াই শুধু c-এর e-তম মূল mod n বের করার (একে RSA problem বলে) কোনো সহজ পথ আছে কি না, যা factoring-এর চেয়ে সহজ। এমন পথ জানা নেই, আবার দুটি সমান কঠিন বলে প্রমাণও নেই।

নিচের ব্লকে আমাদের নিজেদের খেলনা key (ব্লক ১-এর n = 69527) একজন আড়িপাতা ব্যক্তির চোখে ভাঙা হয়েছে: trial division-এ factor, তারপর d, তারপর আটকানো ciphertext-এর বার্তা। তারপর φ(n) থেকে উপপাদ্য ৬.১, আর শেষে n বড় হলে trial division-এর খরচ কীভাবে বাড়ে।

import time
from math import isqrt

def smallest_factor(n):               # trial division: about sqrt(n) steps
    for k in range(3, isqrt(n) + 1, 2):
        if n % k == 0: return k
    return n

# 1) the eavesdropper's view of a toy key: only n, e and one ciphertext
n, e, c = 69527, 17, 15669
p = smallest_factor(n); q = n // p
d = pow(e, -1, (p - 1) * (q - 1))     # with p and q, d is one inverse away
print(f"n = {p} * {q}, recovered d = {d}, order code = {pow(c, d, n)}")

# 2) phi(n) alone also gives p and q: p + q = n - phi + 1
phi = (p - 1) * (q - 1)
s = n - phi + 1; r = isqrt(s * s - 4 * n)
print("from n and phi:", (s - r) // 2, (s + r) // 2)

# 3) cost of trial division as n grows (both primes about half the bits)
def prime_near(x):
    while smallest_factor(x) != x: x += 2
    return x
for bits in (24, 32, 40, 48):
    h = bits // 2
    a, b = prime_near(2**(h - 1) + 2**(h - 3) + 1), prime_near(2**h - 2**(h - 3) + 1)
    t = time.perf_counter(); f = smallest_factor(a * b)
    ms = (time.perf_counter() - t) * 1000
    print(f"{(a * b).bit_length()}-bit n: found {f}, about {f // 2:,} divisions, {ms:.1f} ms")

n = 251 * 277, recovered d = 24353, order code = 4207
from n and phi: 251 277
24-bit n: found 2579, about 1,289 divisions, 0.1 ms
32-bit n: found 40961, about 20,480 divisions, 1.0 ms
40-bit n: found 655373, about 327,686 divisions, 18.5 ms
48-bit n: found 10485767, about 5,242,883 divisions, 289.3 ms

Key-এর মাপ: তারিখসহ নির্দেশনা

পর্ব ২৫-এ দেখেছেন, প্রকাশ্যে factor করা সবচেয়ে বড় RSA challenge সংখ্যা RSA-250 (৮২৯ bit), ২০২০ সালে। key-এর মাপের পরামর্শ তাই সংখ্যা ভাঙার সেরা জানা খরচ থেকে আসে, আর সময়ের সঙ্গে বদলায়। মার্কিন NIST-এর SP 800-57 Part 1 (Rev. 5, ২০২০) নির্দেশিকায় প্রচলিত তুলনা নিচের মতো; নিরাপত্তা “bit”-এ মাপা মানে মোটামুটি এতগুলো bit-এর key সব চেষ্টা করার সমান কাজ।

এর বাইরে একটি বড় অনিশ্চয়তা আছে: পর্ব ২৫-এর Shor-এর algorithm একটি বড়, ত্রুটি-সংশোধিত quantum কম্পিউটারে RSA-কে ভেঙে দেবে। এ কারণে NIST ২০২৪ সালের শেষে একটি খসড়া পরিকল্পনায় (NIST IR 8547) RSA আর elliptic curve থেকে post-quantum পদ্ধতিতে সরার সময়রেখা প্রস্তাব করেছে, যেখানে ২০৩৫ সালের মধ্যে এদের বাদ দেওয়ার কথা বলা হয়েছে; চূড়ান্ত রূপ বদলাতে পারে। পর্ব ৩০ “Finite field আর elliptic curve-এর পরিচয়”-এ এ নিয়ে আরও কথা আছে।

৭ · Textbook RSA-এর তিন ফাঁদ — আর কেন padding

বড় n নিলেই কি textbook RSA নিরাপদ? না। n যত বড়ই হোক, সূত্রটির নিজের কাঠামো থেকে তিনটি দুর্বলতা আসে, আর প্রতিটি একটি সরল গাণিতিক সত্য।

ফাঁদ ১: একই বার্তা, একই ciphertext

E(m) = m^e mod n-এ কোনো এলোমেলো অংশ নেই, তাই এটি deterministic: একই m সবসময় একই c দেয়। আর public key সবার কাছে আছে, তাই যে কেউ নিজে E(m) হিসাব করতে পারেন। বার্তার সম্ভাব্য মান কম হলে (হ্যাঁ/না, ডেলিভারির ঘণ্টা 0–23, একটি ৪ অঙ্কের PIN) আক্রমণকারী সব সম্ভাব্য m encrypt করে আটকানো c-এর সঙ্গে মিলিয়ে নেন, d ছাড়াই। আধুনিক সংজ্ঞায় একটি নিরাপদ encryption-কে semantic security দিতে হয়: ciphertext দেখে বার্তা সম্পর্কে কোনো আংশিক তথ্যও যেন না মেলে। Deterministic কোনো public-key পদ্ধতি তা পারে না, তাই encryption-এ এলোমেলোতা লাগে।

ফাঁদ ২: গুণের সঙ্গে মানিয়ে চলা

প্রমাণ: m₁^e · m₂^e = (m₁m₂)^e, আর mod n-এ গুণ congruence মানে (পর্ব ২২)। ∎

এর অর্থ: বার্তা না জেনেই কেউ ciphertext-কে এমনভাবে বদলাতে পারেন যাতে বার্তা নিয়ন্ত্রিতভাবে বদলায়। ধরুন একটি নিলামে দর 125 টাকা encrypt হয়ে যাচ্ছে; পথে কেউ c-কে E(2) = 2^e mod n দিয়ে গুণ করলেন, আর প্রাপক decrypt করে পেলেন 250. এই ধর্মকে বলে malleability. Encryption শুধু গোপনীয়তা দেয়, অখণ্ডতা নয়; তাই বাস্তব ব্যবস্থায় authenticated encryption লাগে।

ফাঁদ ৩: ছোট e আর ছোট বার্তা

দ্রুততার জন্য কেউ e = 3 নিলেন। বার্তা m যদি এত ছোট হয় যে m³ < n, তবে mod n-এ কোনো “ঘোরা” ঘটে না: c = m³ একটি সাধারণ পূর্ণসংখ্যা। তখন c-এর সাধারণ ঘনমূলই m, আর ঘনমূল বের করতে কোনো key লাগে না, শুধু binary search. একই বার্তা e = 3 দিয়ে তিনজন আলাদা প্রাপককে (আলাদা n) পাঠালে, তিনটি ciphertext পর্ব ২৩-এর CRT দিয়ে জুড়ে m³ mod n₁n₂n₃ পাওয়া যায়, আর m < প্রতিটি n_i বলে m³ < n₁n₂n₃, তাই আবার সাধারণ ঘনমূল যথেষ্ট। এই পর্যবেক্ষণ Johan Håstad-এর ১৯৮০-এর দশকের কাজ থেকে পরিচিত।

নিচের ব্লক তিনটি ফাঁদ আমাদের নিজেদের খেলনা key-এ দেখায়। ঘনমূলের পরীক্ষায় একটি ৬০০-bit n বানানো হয়েছে দুটি মৌলিক থেকে (একাধিক ভিত্তিতে Fermat পরীক্ষা দিয়ে খোঁজা; scratch-এ sympy.isprime দিয়েও দুটিকে মৌলিক নিশ্চিত করা হয়েছে), যাতে দেখা যায় সমস্যাটি n-এর মাপের নয়, কাঠামোর।

n, e, d = 69527, 17, 24353            # toy key (p = 251, q = 277)
enc = lambda m: pow(m, e, n)

# 1) deterministic: equal plaintexts give equal ciphertexts
c = enc(19)                           # secret delivery hour, 0..23
guess = [h for h in range(24) if enc(h) == c]   # try all 24 with the PUBLIC key
print("intercepted", c, "-> delivery hour", guess)

# 2) malleable: E(m1) * E(m2) = E(m1 * m2) (mod n)
m1, m2 = 125, 2                       # a bid of 125 taka, a factor 2
c = enc(m1) * enc(m2) % n             # made WITHOUT knowing m1 or d
print("E(125)*E(2) decrypts to", pow(c, d, n), "| E(250) == c:", enc(250) == c)

# 3) small e and small m: c = m^3 never wraps around n
def is_probable_prime(x):
    return all(pow(a, x - 1, x) == 1 for a in (2, 3, 5, 7, 11, 13))
def prime_2mod3(x):                   # need gcd(3, p - 1) = 1, so p = 2 (mod 3)
    while not (x % 3 == 2 and is_probable_prime(x)): x += 1
    return x
P, Q = prime_2mod3(2**300 + 7), prime_2mod3(3 * 2**298 + 1)
N = P * Q                             # about 600 bits
m = int.from_bytes(b"PIN 4821", "big")  # a short secret, about 64 bits
c3 = pow(m, 3, N)
def icbrt(x):                         # integer cube root by bisection
    lo, hi = 0, 1 << (x.bit_length() // 3 + 2)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        lo, hi = (mid, hi) if mid**3 <= x else (lo, mid - 1)
    return lo
print(N.bit_length(), "bit n; m^3 < n:", m**3 < N)
print("cube root of c, no key used:", icbrt(c3).to_bytes(8, "big"))

intercepted 22324 -> delivery hour [19]
E(125)*E(2) decrypts to 250 | E(250) == c: True
600 bit n; m^3 < n: True
cube root of c, no key used: b'PIN 4821'

প্রতিকার: padding, আর তারপরও লাইব্রেরি

তিনটি ফাঁদের সাধারণ প্রতিকার padding: encrypt করার আগে বার্তার সঙ্গে এলোমেলো byte আর একটি নির্দিষ্ট কাঠামো জুড়ে n-এর প্রায় সমান মাপের একটি সংখ্যা বানানো। এলোমেলো অংশ ciphertext-কে প্রতিবার আলাদা করে (ফাঁদ ১), বড় মাপ ঘনমূলের পথ বন্ধ করে (ফাঁদ ৩), আর কাঠামোটি গুণ করে বানানো ciphertext-কে decryption-এর সময় অবৈধ করে দেয় (ফাঁদ ২). Encryption-এর জন্য প্রচলিত মান OAEP (Mihir Bellare আর Phillip Rogaway, ১৯৯৪), আর signature-এর জন্য RSA-PSS (একই দুজন, ১৯৯৬); দুটিই PKCS #1 মানে আছে, যার বর্তমান সংস্করণ RFC 8017 (২০১৬). পুরোনো PKCS #1 v1.5 encryption padding-এ ১৯৯৮ সালে Daniel Bleichenbacher একটি আক্রমণ দেখান, যেখানে সার্ভারের “padding ঠিক নেই” ধরনের ত্রুটি-বার্তা থেকেই ধীরে ধীরে তথ্য বেরিয়ে আসে; এর রূপভেদ বহু বছর পরেও বাস্তব সার্ভারে পাওয়া গেছে বলে প্রতিবেদন আছে।

শিক্ষাটি পরিষ্কার: সঠিক গণিত আর বড় key থাকলেও ছোট বাস্তবায়ন-ভুলে পুরো ব্যবস্থা ভেঙে যায়। আধুনিক সিস্টেম তাই সাধারণত RSA দিয়ে সরাসরি বার্তা encrypt করে না; RSA (বা key exchange) দিয়ে একটি এলোমেলো symmetric key পাঠায়, আর বার্তা যায় সেই key-এর authenticated encryption-এ, যাকে hybrid encryption বলে। নিজে RSA লিখে কোনো আসল কাজে ব্যবহার করবেন না; Cybersecurity কোর্সের পর্ব ১০ আর পর্ব ১৪-এ এর ব্যবহারিক নিয়ম আছে।

৮ · CRT দিয়ে দ্রুত decryption — আর ডেস্কটপে সত্যিকারের run

Encryption সস্তা, কারণ e = 65537-এ মাত্র ১৭টি গুণ। কিন্তু decryption আর সই ধীর, কারণ d প্রায় n-এর মাপের, অর্থাৎ ২০৪৮ bit-এ প্রায় ২০৪৮টি বর্গ। গুদাম কিন্তু p আর q জানে, আর পর্ব ২৩-এ দেখেছেন, mod n-এর একটি হিসাব mod p আর mod q-এর দুটি ছোট হিসাবে ভাঙা যায়।

কেন ঠিক: d = d_p + j(p − 1) কোনো j ≥ 0-এর জন্য। p ∤ c হলে Fermat-এ c^d = c^d_p(c^p−1)^j ≡ c^d_p (mod p); p ∣ c হলে দুই পাশই 0 (d_p ≥ 1, কারণ gcd(d, p − 1) = 1 বলে d_p ≠ 0). তাই m_p ≡ c^d ≡ m (mod p), একইভাবে m_q ≡ m (mod q). শেষ সূত্রটি পর্ব ২৩-এর back-substitution (Garner-এর রূপ): এটি mod q-তে m_q, আর mod p-তে m_q + (m_p − m_q) = m_p, আর 0 ≤ m < pq. CRT-এর অনন্যতায় এটিই m.

হাতে, আমাদের key-এ: c = 2790, d_p = 2753 mod 60 = 53, d_q = 2753 mod 52 = 49, q_inv = 53⁻¹ mod 61 = 38. c mod 61 = 45 আর c mod 53 = 34; m_p = 45⁵³ mod 61 = 4, m_q = 34⁴⁹ mod 53 = 12. তারপর 38 · (4 − 12) = −304 ≡ 1 (mod 61), আর m = 12 + 53 · 1 = 65 ✓.

কত দ্রুত: p আর q, n-এর অর্ধেক মাপের। স্কুলের পদ্ধতির গুণে অর্ধেক মাপের দুটি সংখ্যা গুণ করতে খরচ প্রায় এক-চতুর্থাংশ, আর ঘাত d_p-ও অর্ধেক bit-এর, তাই একটি অর্ধেক-ঘাত প্রায় এক-অষ্টমাংশ খরচ; দুটি মিলে প্রায় এক-চতুর্থাংশ। তত্ত্বে প্রায় ৪ গুণ দ্রুত; বাস্তবে গুণের algorithm আর অন্যান্য খরচের কারণে সাধারণত একটু কম। নিচের ব্লক ১০২৪-bit একটি খেলনা key বানিয়ে (Miller–Rabin দিয়ে, পর্ব ২৫) দুই পদ্ধতির সময় মাপে। d কখনো ছাপা হয় না।

import random, time
random.seed(2028)                     # toy timing only: NOT a secure key

def is_prime(x, rounds=20):           # Miller-Rabin, as in lesson 25
    if x % 2 == 0 or any(x % s == 0 for s in (3, 5, 7, 11, 13)): return False
    d, s = x - 1, 0
    while d % 2 == 0: d, s = d // 2, s + 1
    for _ in range(rounds):
        y = pow(random.randrange(2, x - 1), d, x)
        if y in (1, x - 1): continue
        for _ in range(s - 1):
            y = y * y % x
            if y == x - 1: break
        else: return False
    return True

def big_prime(bits):
    while True:
        x = random.getrandbits(bits) | (1 << bits - 1) | 1
        if (x - 1) % 65537 and is_prime(x): return x   # need gcd(e, p - 1) = 1

p, q, e = big_prime(512), big_prime(512), 65537
n = p * q; d = pow(e, -1, (p - 1) * (q - 1))
dp, dq, q_inv = d % (p - 1), d % (q - 1), pow(q, -1, p)   # precomputed once
c = pow(123456789, e, n)

def plain(): return pow(c, d, n)
def crt():                            # two half-size powers + Garner's step
    mp, mq = pow(c, dp, p), pow(c, dq, q)
    return mq + q * (q_inv * (mp - mq) % p)

for f in (plain, crt):
    t = time.perf_counter(); r = [f() for _ in range(40)][0]
    print(f"{f.__name__:5}: {(time.perf_counter() - t) / 40 * 1000:.2f} ms per decryption, m = {r}")
print("n has", n.bit_length(), "bits; d has", d.bit_length(), "bits (not printed)")

plain: 2.75 ms per decryption, m = 123456789
crt  : 0.99 ms per decryption, m = 123456789
n has 1024 bits; d has 1022 bits (not printed)

ডেস্কটপে সত্যিকারের run: নিজের key-তৈরি বনাম পেশাদার লাইব্রেরি

ব্রাউজারে বড় key বানানো ধীর, তাই এই পর্ব লেখার সময় একটি সাধারণ Windows ডেস্কটপে সত্যিকারের run করা হয়েছে: Python 3.12.13, cryptography 50.0.2 (Apache-2.0 বা BSD লাইসেন্স; ভেতরে OpenSSL) আর sympy 1.14.0 (BSD), uv দিয়ে বানানো একটি ছোট প্রজেক্টে। ৫১২-bit key শুধু সময় মাপার জন্য; এটি সম্পূর্ণ অনিরাপদ। নিজে চালাতে চাইলে:

cd ~/bazarghar-dm
uv add cryptography sympy
uv run python keygen_timing.py

স্ক্রিপ্টের মূল অংশ নিচে। probably_prime হলো ব্লক ৪-এর is_prime-এর মতো Miller–Rabin (৪০ round), তাই বাদ দেওয়া হলো। প্রতিটি কাজ কয়েকবার চালিয়ে মধ্যমা (median) সময় নেওয়া হয়েছে। লক্ষ করুন, n-এর শুধু প্রথম ১২টি অঙ্ক ছাপা হয়, আর private key কখনো ছাপা হয় না।

import random, time, statistics
from math import gcd
import sympy, cryptography
from cryptography.hazmat.primitives.asymmetric import rsa
rng = random.Random(2026)                    # toy only: NOT a secure random source
# probably_prime(n): Miller-Rabin with 40 rounds, same idea as block 4

def toy_keygen(bits, e=65537):
    while True:
        p, q = (next(c for c in iter(lambda: rng.getrandbits(bits // 2) | (3 << (bits // 2 - 2)) | 1, None)
                     if probably_prime(c)) for _ in range(2))
        phi = (p - 1) * (q - 1)
        if p != q and gcd(e, phi) == 1:
            return p * q, e, pow(e, -1, phi)

def timed(f, k):
    ts = []
    for _ in range(k):
        t = time.perf_counter(); r = f(); ts.append(time.perf_counter() - t)
    return r, statistics.median(ts)

for bits, k in ((512, 10), (2048, 5)):
    (n, e, d), t = timed(lambda: toy_keygen(bits), k)
    # ... print bits, median time and the first 12 digits of n
key, t = timed(lambda: rsa.generate_private_key(public_exponent=65537, key_size=2048), 5)
# ... sympy.randprime(2**1023, 2**1024) timed the same way; four print lines

$ uv run python keygen_timing.py
cryptography 50.0.2 | sympy 1.14.0
own Python keygen   512-bit: median     17.9 ms  n.bit_length()=512  n=113772880175...
own Python keygen  2048-bit: median   2217.2 ms  n.bit_length()=2048  n=199252508797...
sympy.randprime   1024-bit prime: median    160.9 ms
cryptography      2048-bit: median     33.9 ms  e=65537  n=233617329970...
textbook check with the library's numbers: True

আমাদের নিজের Python কোডে ২০৪৮-bit key বানাতে লেগেছে প্রায় ২.২ সেকেন্ড, যেখানে cryptography লাইব্রেরির লেগেছে প্রায় ৩৪ মিলিসেকেন্ড, অর্থাৎ প্রায় ৬৫ গুণ দ্রুত। কারণ লাইব্রেরি C আর assembly-তে লেখা বড়-সংখ্যার গণিত, ছোট মৌলিক দিয়ে আগে ছাঁকা আর সতর্কভাবে বাছা পরীক্ষা ব্যবহার করে। মৌলিক খোঁজায় ভাগ্যও আছে, তাই এই সময়গুলো এক run থেকে আরেক run-এ বেশ ওঠানামা করে। শেষ লাইনে লাইব্রেরির বানানো key-এর সংখ্যা দিয়ে আমাদের textbook সূত্র m = 65-কে ফেরত এনেছে: গণিত একই, পার্থক্য গতি, এলোমেলোতার উৎস, padding আর বাস্তবায়নের যত্নে। লাইব্রেরি key বানায় অপারেটিং সিস্টেমের নিরাপদ এলোমেলো উৎস থেকে; আমাদের random.Random(2026) স্থির seed-এ চলে, তাই কেউ seed জানলে আমাদের key হুবহু আবার বানাতে পারবেন।

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

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

অঙ্ক ১: p = 17, q = 11, e = 7. d বের করুন, আর m = 88 encrypt করুন।

1. n = 17 · 11 = 187, φ(n) = 16 · 10 = 160. gcd(7, 160) = 1, কারণ 160 = 7 · 22 + 6 আর 7 = 6 · 1 + 1.
2. পেছনে বসানো: 1 = 7 − 6 = 7 − (160 − 22 · 7) = 23 · 7 − 160. তাই d = 23. যাচাই: 7 · 23 = 161 = 160 + 1 ✓.
3. 7 = 111₂, তাই 88⁷ = 88⁴ · 88² · 88. 88² = 7744 ≡ 77 (7744 − 41 · 187), 88⁴ ≡ 77² = 5929 ≡ 132 (mod 187).
4. 132 · 77 = 10164 ≡ 66, আর 66 · 88 = 5808 ≡ 11 (mod 187). তাই c = 11. (d = 23 দিয়ে 11²³ mod 187 = 88 ফিরে আসে।)

অঙ্ক ২: public key (n, e) = (143, 7), আটকানো c = 48. বার্তা কী?

1. খেলনা n ছোট, তাই trial division: 143 = 11 · 13. φ = 10 · 12 = 120.
2. 120 = 7 · 17 + 1, তাই 1 = 120 − 17 · 7, আর d ≡ −17 ≡ 103 (mod 120). যাচাই: 7 · 103 = 721 = 6 · 120 + 1 ✓.
3. CRT দিয়ে: d_p = 103 mod 10 = 3, d_q = 103 mod 12 = 7. 48 mod 11 = 4, আর 4³ = 64 ≡ 9 (mod 11). 48 mod 13 = 9; 9² = 81 ≡ 3, 9⁴ ≡ 9, 9⁷ = 9⁴ · 9² · 9 ≡ 9 · 3 · 9 = 243 ≡ 9 (mod 13).
4. m ≡ 9 (mod 11) আর m ≡ 9 (mod 13), তাই m = 9. যাচাই: 9⁷ mod 143 = 48 ✓. শিক্ষা: ছোট n মানে বার্তা উন্মুক্ত।

প্রমাণের ভুল ধরুন: “Euler দিয়েই সব বার্তা”

একজন লিখলেন: “দাবি: n = pq-তে ed ≡ 1 (mod φ(n)) হলে প্রতিটি m-এ m^ed ≡ m (mod n). প্রমাণ: ed = 1 + kφ(n). Euler-এর উপপাদ্যে m^φ(n) ≡ 1 (mod n), তাই m^ed = m · (m^φ(n))^k ≡ m. এটি p = q হলেও খাটে। ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: দ্বিতীয় বাক্যে Euler-এর উপপাদ্য তার শর্ত ছাড়া ব্যবহার হয়েছে: m^φ(n) ≡ 1 শুধু gcd(m, n) = 1 হলে সত্য। Counterexample: n = 3233, m = 61-এ 61³¹²⁰ mod 3233 = 1220 ≠ 1. p ≠ q হলে দাবিটি তবু সত্য, কিন্তু তার জন্য উপপাদ্য ৪.২-এর Fermat-আর-CRT প্রমাণ লাগে; এই “প্রমাণ” অসম্পূর্ণ। আর শেষ বাক্যটি সরাসরি মিথ্যা: p = q = 3, n = 9, φ(9) = 6, e = d = 5 (25 ≡ 1 mod 6) নিলে m = 3-এ 3²⁵ mod 9 = 0 ≠ 3. শর্ত বাদ দেওয়া প্রমাণ শুধু অসম্পূর্ণ নয়, মিথ্যা দাবিকেও “প্রমাণ” করে ফেলতে পারে।

১০ · AI-এর যুগে — RSA-এর হিসাব আর দাবি যাচাই

RSA এমন একটি বিষয়, যেখানে AI সহকারী আত্মবিশ্বাসী আর প্রায়-সঠিক উত্তর দেয়, আর “প্রায়” অংশটিই বিপজ্জনক। কয়েকটি ভুল নিয়মিত দেখা যায়:

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

• e · d mod φ(n) = 1 আর gcd(e, φ(n)) = 1 নিজে Python-এ মিলিয়েছি
• encrypt করে decrypt করলে আসল m ফেরত আসে, আর কয়েকটি এলোমেলো m-এও
• প্রমাণের প্রতিটি উপপাদ্যের শর্ত দেখেছি; gcd(m, n) > 1 ক্ষেত্র বাদ পড়েনি, p ≠ q ব্যবহৃত হয়েছে
• ছোট n-এ সব m brute force করে দাবিটি পরীক্ষা করেছি, আর একটি counterexample খুঁজেছি
• বাস্তব ব্যবহারের পরামর্শে padding, key-এর মাপ আর পরীক্ষিত লাইব্রেরির কথা আছে কি না দেখেছি
• সাল, নাম আর উদ্ধৃত মান (NIST, RFC) বিশ্বস্ত উৎসে মিলিয়েছি

RSA-র প্রায় প্রতিটি দাবি ৪ অঙ্কের n-এ এক সেকেন্ডে brute force করা যায়। AI-এর “সবসময় কাজ করে” বা “প্রমাণিতভাবে নিরাপদ” দাবি পেলে আগে ছোট উদাহরণে চালান, তারপর শর্তগুলো খুঁজুন।