সরাসরি পর্বে যান
পর্ব ৭৬ · ৮৫-এর মধ্যে · মডিউল ১২

Cryptography-র complexity — one-way function আর average-case hardness

The Complexity of Cryptography — Efficient Adversaries, One-Way Functions, Trapdoors, Pseudorandom Generators, Collision Resistance, Impagliazzo's Five Worlds and Lattices

Taught in Bangla, this lesson explains security against efficient adversaries up to negligible probability. It defines one-way functions, proves that their existence implies P ≠ NP and explains why worst-case hardness does not give the converse, then covers trapdoors with toy RSA, collision resistance, Impagliazzo's five worlds and LWE. In-page Python (Pyodide) measures birthday collisions on truncated SHA-256, and a real desktop sympy run times factoring of toy moduli. Safe-practice guidance closes it.

এই পর্বে যা শিখবেন

  • Negligible function, polynomial সময়ের প্রতিপক্ষ আর one-way function-এর নিখুঁত সংজ্ঞা
  • “OWF থাকলে P ≠ NP”-এর পূর্ণ প্রমাণ, আর worst-case বনাম average-case কঠিনতার পার্থক্য
  • Trapdoor function আর toy RSA দিয়ে public-key-এর complexity দিক
  • Pseudorandom generator, indistinguishability আর “PRG থেকে OWF”-এর প্রমাণ
  • Collision resistance, birthday bound, Impagliazzo-র পাঁচ জগৎ আর LWE-র মূল ধারণা

১ · Cryptography কেন complexity-র ওপর দাঁড়িয়ে

বাজারঘর প্রতিদিন হাজারো অর্ডারের তথ্য পাঠায়, গ্রাহককে OTP দেয়, আর delivery partner-এর সঙ্গে চুক্তির ফাইল সই করে। প্রশ্নটি সরল: কোনো গোপন তথ্য কি প্রমাণসহ নিরাপদ রাখা যায়? এই মডিউলের আগের পর্বগুলো কঠিন সমস্যাকে বাধা হিসেবে দেখেছে। এই পর্বে উল্টো দৃষ্টি: কঠিনতাই সম্পদ, কারণ প্রতিপক্ষের জন্য যা কঠিন, তা-ই আমাদের নিরাপত্তা।

মোবাইল ব্যাংকিংয়ের চার অঙ্কের PIN ভাবুন। চোর চাইলে সব ১০,০০০টি চেষ্টা করতে পারে, তাই PIN “অভেদ্য” নয়; নিরাপত্তা আসে তিনবার ভুলে অ্যাকাউন্ট আটকে যাওয়া থেকে। Cryptography-র key-তে এমন পাহারাদার নেই, তাই নিরাপত্তা আসে আকার থেকে: 2128টি সম্ভাব্য key সব চেষ্টা করার সময় কোনো যন্ত্রের নেই। কিন্তু সব চেষ্টা না করে কোনো চতুর শর্টকাট আছে কি না, সেটিই complexity-র প্রশ্ন।

Claude Shannon ১৯৪৯ সালের প্রবন্ধে perfect secrecy সংজ্ঞায়িত করেন: ciphertext দেখে বার্তা সম্পর্কে কোনো তথ্যই পাওয়া যাবে না, প্রতিপক্ষের সময় যত অসীমই হোক। তিনি দেখান, এর জন্য key-এর সম্ভাব্য মানের সংখ্যা অন্তত বার্তার সম্ভাব্য মানের সংখ্যার সমান হতে হয়; one-time pad তাই key হিসেবে বার্তার সমান দৈর্ঘ্যের এলোমেলো বিট চায়। প্রতিটি অর্ডারের জন্য সমান দৈর্ঘ্যের নতুন গোপন key আগেই ভাগ করা অবাস্তব। আধুনিক cryptography তাই দাবি কমায়: শুধু দক্ষ প্রতিপক্ষের বিরুদ্ধে নিরাপত্তা। এর নাম computational security.

সংজ্ঞা ১.১ (প্রতিপক্ষ আর negligible)

একটি security parameter n (মোটামুটি key-এর বিট-দৈর্ঘ্য) সবকিছু মাপে। প্রতিপক্ষ মানে একটি probabilistic polynomial-time (PPT) algorithm: পর্ব ৬৯-এর probabilistic Turing machine, যার সময় n-এর polynomial.

একটি ফাংশন μ: ℕ → [0, 1] negligible, যদি প্রতিটি ধ্রুবক c-এর জন্য এমন N থাকে যাতে সব n > N-এ μ(n) < n−c. অর্থাৎ যেকোনো polynomial-এর উল্টোর চেয়ে দ্রুত শূন্যের দিকে যায়। লেখা হয় negl(n).

উদাহরণ: 2−n, 2−√n আর n−log n negligible; 1/n100 নয়, কারণ c = 101 নিলে শর্ত ভাঙে। মজার কথা, n = 100-এ 2−√n = 2−10 ≈ 0.001, আর n−100 = 10−200; ছোট n-এ “negligible”-টি বড়। সংজ্ঞাটি অসীমের দিকে আচরণ নিয়ে, কোনো নির্দিষ্ট মান নিয়ে নয়।

কেন ঠিক এই জোড়া, polynomial সময় আর negligible সম্ভাবনা? কারণ দুটি একসঙ্গে বন্ধ থাকে। একজন PPT প্রতিপক্ষ তার আক্রমণ polynomial সংখ্যক বার চালালেও সাফল্য negligible থাকে (p(n) · negl(n) এখনো negligible). উল্টোভাবে, সাফল্য যদি 1/p(n)-এর মতো non-negligible হয়, তবে n · p(n) বার চালালে প্রায় নিশ্চিত সাফল্য, ঠিক পর্ব ৬৯-এর amplification-এর মতো। তাই “নিরাপদ” কথাটি যন্ত্রের মডেল বা পুনরাবৃত্তির সংখ্যার ওপর নির্ভর করে না। বাস্তবে অবশ্য নির্দিষ্ট সংখ্যা লাগে (যেমন “128-bit নিরাপত্তা”); তত্ত্বের asymptotic সংজ্ঞা সেই সংখ্যাগুলোর যুক্তি দেয়।

২ · One-way function — সংজ্ঞা আর প্রার্থী

সব cryptography-র সবচেয়ে ছোট উপাদান একটি ফাংশন, যা এক দিকে সহজ আর উল্টো দিকে কঠিন। Diffie আর Hellman ১৯৭৬ সালের প্রবন্ধে ধারণাটি কেন্দ্রে আনেন; আধুনিক সংজ্ঞাটি এমন:

সংজ্ঞা ২.১ (One-way function)

একটি ফাংশন f: {0,1}∗ → {0,1}∗ একটি one-way function, যদি

  1. সহজ দিক: f polynomial সময়ে হিসাবযোগ্য, আর
  2. কঠিন দিক: প্রতিটি PPT algorithm A-এর জন্য

Prx ← {0,1}n [ f(A(1n, f(x))) = f(x) ] ≤ negl(n).

সম্ভাবনা নেওয়া হয় সমান সম্ভাবনায় বাছা x আর A-এর নিজের coin-এর ওপর।

তিনটি খুঁটিনাটি গুরুত্বপূর্ণ। প্রথম, A জেতে যেকোনো preimage x′ পেলেই (f(x′) = f(x)), আসল x না হলেও চলে। দ্বিতীয়, x random: কঠিনতা চাই গড়ে, প্রায় সব x-এ, শুধু কয়েকটি বিশেষ x-এ নয়। তৃতীয়, 1n (n টি 1-এর unary string) A-কে দৈর্ঘ্য জানায়, যাতে f ছোট আউটপুট দিলেও A-এর সময় n-এর polynomial ধরা যায়।

এমন f আছে কি না কেউ জানে না। নিচের প্রার্থীগুলোর ওপর বহু দশকের আক্রমণ ব্যর্থ হয়েছে, এটুকুই ভরসা:

প্রার্থীসহজ দিককঠিন বলে বিশ্বাস
গুণ: f(p, q) = p · q (দুটি random n-bit মৌলিক)গুণFactoring
f(x) = gx mod p (g একটি generator)Modular exponentiationDiscrete logarithm
Subset sum: (a1…an, S) ↦ (a1…an, Σi∈S ai)যোগসঠিক ঘনত্বের random instance (Impagliazzo–Naor ১৯৯৬-এর বিশ্লেষণ)
Lattice: (A, As + e mod q)Matrix গুণLWE (অংশ ৭)

সহজ আর কঠিন দিকের ব্যবধান কত বড়, নিচের ব্লক দেখায়। প্রতিটি আকারের সবচেয়ে বড় মৌলিক p আর তার সবচেয়ে ছোট generator g নিয়ে একটি গোপন x-এর জন্য y = gx mod p হিসাব করা হয় square-and-multiply দিয়ে (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ২২), তারপর x = 0, 1, 2, … চেষ্টা করে উল্টো দিক। সময় নয়, গুণের সংখ্যা গোনা হয়, তাই ফল প্রতিবার একই।

# Easy direction vs hard direction: g^x mod p (fast) vs discrete log (search)
import random
rng = random.Random(76)
def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))
def prim_root(p):                       # smallest generator of Z_p^*
    fs = {d for d in range(2, p) if (p - 1) % d == 0 and is_prime(d)}
    return next(g for g in range(2, p) if all(pow(g, (p - 1) // f, p) != 1 for f in fs))
def fast_pow(g, x, p):                  # square-and-multiply, counting products
    r, mults = 1, 0
    for bit in bin(x)[2:]:
        r = r * r % p; mults += 1
        if bit == "1":
            r = r * g % p; mults += 1
    return r, mults
def brute_log(g, y, p, cap=2_000_000):  # try x = 0, 1, 2, ... until g^x = y
    v = 1
    for x in range(min(p - 1, cap)):
        if v == y:
            return x, x + 1
        v = v * g % p
    return None, cap
print("bits      p        g   x(secret)  fast mults  brute tries")
for bits in (8, 12, 16, 20):
    p = next(n for n in range(2 ** bits - 1, 2, -1) if is_prime(n))
    g = prim_root(p)
    x = rng.randrange(p // 2, p - 1)    # a secret exponent
    y, m = fast_pow(g, x, p)
    found, tries = brute_log(g, y, p)
    assert found == x and y == pow(g, x, p)
    print(f"{bits:4} {p:8} {g:4} {x:10} {m:11} {tries:12}")
print("2048-bit p: fast <= 4096 mults; brute force ~ 2^2047 tries")

আসল আউটপুট (ব্রাউজারের Python):

bits      p        g   x(secret)  fast mults  brute tries
   8      251    6        172          12          173
  12     4093    2       2994          19         2995
  16    65521   17      63895          27        63896
  20  1048573    2     728570          33       728571
2048-bit p: fast <= 4096 mults; brute force ~ 2^2047 tries

সহজ দিকের গুণ বিট-সংখ্যার দ্বিগুণের মধ্যে থাকে (20-bit-এ 33টি), কারণ x-এর প্রতিটি বিটে একটি বর্গ আর বড়জোর একটি গুণ। Brute force-এর চেষ্টা x-এর মানের সমান, অর্থাৎ বিট-সংখ্যার সূচকীয়: প্রতি ৪ বিটে প্রায় ১৬ গুণ। শেষ লাইনটি হিসাব, চালানো নয়।

সাবধান: brute force সেরা আক্রমণ নয়। Shanks-এর baby-step giant-step (১৯৭১) আর Pollard-এর rho প্রায় √p ধাপে discrete log বের করে, আর Zp∗-এ index calculus আরও দ্রুত, sub-exponential. Factoring-এও general number field sieve sub-exponential. তাই বাস্তবের p আর N কয়েক হাজার বিটের। “এর চেয়ে ভালো কোনো পদ্ধতি নেই” কথাটি কেউ প্রমাণ করেননি; শুধু “generic group” নামের সীমিত মডেলে √p-এর নিম্নসীমা প্রমাণিত (Shoup ১৯৯৭-এর কাজ হিসেবে পরিচিত)।

৩ · OWF থাকলে P ≠ NP — আর উল্টোটা কেন জানা নেই

উপপাদ্য ৩.১

One-way function থাকলে P ≠ NP. (আরও শক্তভাবে, NP ⊄ BPP.)

প্রমাণ (contrapositive: P = NP হলে কোনো f one-way নয়):

  1. ধরুন P = NP, আর f যেকোনো polynomial সময়ে হিসাবযোগ্য ফাংশন। এই language নিন: PREf = {⟨y, u, 1n⟩ : এমন x ∈ {0,1}n আছে যা prefix u দিয়ে শুরু আর f(x) = y}. — সংজ্ঞা
  2. PREf ∈ NP: certificate x নিজেই; verifier দেখে |x| = n, x-এর শুরুতে u, আর f(x) = y. সব polynomial সময়ে। — পর্ব ৫৮-এর verifier সংজ্ঞা
  3. P = NP বলে PREf-এর একটি polynomial সময়ের decider D আছে। — ধরে নেওয়া
  4. Inverter A(1n, y): u = ε দিয়ে শুরু; i = 1 থেকে n পর্যন্ত, D যদি ⟨y, u0, 1n⟩ গ্রহণ করে তবে u = u0, নইলে u = u1. শেষে u ফেরত দিন। — পর্ব ৬২-এর self-reducibility
  5. Invariant: “u দিয়ে শুরু এমন একটি preimage আছে।” শুরুতে সত্য, কারণ y = f(x). প্রতিটি ধাপে u0-এর নিচে preimage না থাকলে invariant থেকে u1-এর নিচে আছে। তাই শেষে f(u) = y. — induction
  6. A মোট n বার D ডাকে, তাই polynomial সময়ে চলে, আর প্রতিটি y = f(x)-এ সম্ভাবনা 1-এ জেতে। এটি সংজ্ঞা ২.১-এর কঠিন দিক ভাঙে। ∎

একই যুক্তিতে NP ⊆ BPP হলেও f উল্টানো যায় (decider-এর ভুলের সম্ভাবনা amplification-এ ছোট করে), তাই আরও শক্ত বক্তব্যটি আসে। নিচের stepper ছোট একটি f-এ, f(x) = 3x mod 17 (x চার বিটের, 0 থেকে 15), পুরো ঘটনাটি দেখায়। এখানে PREf-এর প্রশ্নের উত্তর brute force দিয়ে বসানো; P = NP হলে একই উত্তর polynomial সময়ে আসত।

1u = ε, y = f(x) দেওয়া2প্রশ্ন: ⟨y, u0, 1^n⟩ ∈ PRE_f?3হ্যাঁ: u = u0; না: u = u14u ফেরত; f(u) = y যাচাই
inverter-এর অবস্থা
prefix u
প্রশ্ন
সম্ভাব্য x
তাদের f(x)
প্রশ্ন গোনা
  1. শুরু। বাজারঘরের একটি খেলনা “গোপন সংখ্যা” x, আর প্রকাশ্য y = 3x mod 17 = 7. 3 হলো mod 17-এর একটি generator, তাই x ↦ 3x mod 17 শূন্য থেকে পনেরোয় এক-এক। Inverter শুধু y আর n = 4 জানে।
  2. প্রথম প্রশ্ন। “0 দিয়ে শুরু কোনো x আছে, যার f(x) = 7?” 0 থেকে 7-এর f-মান 1, 3, 9, 10, 13, 5, 15, 11; 7 নেই। উত্তর না, তাই x-এর প্রথম বিট 1.
  3. দ্বিতীয় প্রশ্ন। “10 দিয়ে শুরু?” অর্থাৎ x ∈ {8, …, 11}, f-মান 16, 14, 8, 7. 7 আছে, উত্তর হ্যাঁ: u = 10.
  4. তৃতীয় প্রশ্ন। “100 দিয়ে শুরু?” x ∈ {8, 9}, f-মান 16 আর 14; উত্তর না, তাই u = 101. Invariant রক্ষা পায়: preimage 101-এর নিচে আছেই।
  5. চতুর্থ প্রশ্ন। “1010?” x = 10, f-মান 8; না। তাই u = 1011.
  6. যাচাই। x = 1011 = 11, আর 311 mod 17 = 7. মোট n = 4টি প্রশ্ন, প্রতিটি একটি NP প্রশ্ন। 2048 বিটের x-এ 2048টি প্রশ্নই যথেষ্ট; তাই P = NP হলে discrete log, factoring, সব one-way প্রার্থী একসঙ্গে ভেঙে পড়ত।

উল্টো দিক: P ≠ NP থেকে কেন OWF আসে না

P ≠ NP একটি worst-case বক্তব্য: প্রতিটি polynomial algorithm কোনো না কোনো instance-এ ভুল করে। কোন instance-এ, তা algorithm-ভেদে আলাদা, আর সেগুলো অতি বিরল হতে পারে। Cryptography-র দরকার average-case কঠিনতা: key-generator যে instance random ভাবে বানায়, প্রায় সবগুলোতেই প্রতিটি দক্ষ প্রতিপক্ষ ব্যর্থ হবে। আরও একটি শর্ত: instance-টি তার সমাধানসহ বানাতে হবে (আগে x, তারপর f(x)), নইলে মালিক নিজেও গোপনটি জানবেন না। নিচের stepper ছবিটি আঁকে।

Worst-case versus average-case hardness on a grid of instances ? f(x) ২৪টি instance, সবই আকার n লাল: A এখানে ব্যর্থ (worst case) random key: লাল পড়ার সম্ভাবনা 2/24 average case: প্রায় সবই লাল x বেছে f(x) প্রকাশ: OWF
  1. Instance-এর জগৎ। আকার n-এর সব instance, এখানে প্রতীক হিসেবে ২৪টি বর্গ। একটি polynomial algorithm A সবগুলোর সামনে।
  2. Worst-case কঠিনতা। P ≠ NP (আর সমস্যাটি NP-complete) হলে A অন্তত কিছু instance-এ ব্যর্থ, এখানে লাল দুটি। কিন্তু বাকি ২২টিতে A ঠিক উত্তর দেয়, আর ব্যর্থতার জায়গা algorithm বদলালে বদলায়।
  3. Random key দিয়ে কী হয়। Key-generator একটি random বর্গ বাছে (নীল বলয়)। লাল পড়ার সম্ভাবনা মাত্র 2/24; এখানে সবুজ পড়েছে, তাই প্রতিপক্ষ সহজেই ভাঙে। শুধু worst-case কঠিনতা দিয়ে নিরাপদ key বানানো যায় না।
  4. Average-case কঠিনতা। দরকার এমন বণ্টন, যেখানে প্রতিটি দক্ষ A প্রায় সব instance-এ ব্যর্থ: ২৪টির ২০টি লাল। এখন random বাছাই প্রায় সবসময় কঠিন বর্গে পড়ে।
  5. সমাধানসহ instance: OWF. আরও চাই, generator আগে x বাছবে, তারপর f(x) প্রকাশ করবে; তখন মালিক সমাধান জানেন, প্রতিপক্ষ জানে না। Average-case কঠিন সমস্যা আছে অথচ এমন OWF নেই, এমন জগৎও যুক্তিগতভাবে সম্ভব (অংশ ৭-এর Pessiland).

ইতিহাস: ১৯৭৮ সালে Merkle আর Hellman NP-complete subset sum-এর ওপর একটি public-key পদ্ধতি দেন। Adi Shamir ১৯৮২ সালে তার মূল রূপটি polynomial সময়ে ভাঙেন (প্রকাশ ১৯৮৪)। কারণ ঠিক এই পর্বের মূল শিক্ষা: key-generator যে instance বানাত, সেগুলো একটি সহজ বিশেষ রূপের ছদ্মবেশ, worst-case কঠিনতা তাদের রক্ষা করেনি। Leonid Levin ১৯৮৬ সালে average-case complexity-র তত্ত্ব শুরু করেন, আর পরে Feigenbaum–Fortnow (১৯৯৩) ও Bogdanov–Trevisan (২০০৩) দেখান যে কিছু স্বাভাবিক ধরনের reduction দিয়ে NP-hardness থেকে average-case কঠিনতা আনা যায় না, যদি না polynomial hierarchy ধসে পড়ে।

৪ · Trapdoor function আর public-key — toy RSA

একটি OWF থেকে অনেক কিছু বানানো যায়: pseudorandom generator (অংশ ৫), symmetric encryption, message authentication, এমনকি digital signature (Naor–Yung ১৯৮৯ আর Rompel ১৯৯০-এর কাজ হিসেবে পরিচিত)। কিন্তু public-key cryptography-তে, যেখানে আগে কোনো গোপন কথা ভাগ না করেই অপরিচিত গ্রাহক বাজারঘরকে গোপন বার্তা পাঠান, আরও কিছু লাগে: মালিকের হাতে একটি গোপন “পেছনের দরজা”।

সংজ্ঞা ৪.১ (Trapdoor permutation family)

তিনটি PPT algorithm: Gen(1n) একটি জোড়া (pk, td) দেয়; fpk একটি permutation, যা pk জানলে polynomial সময়ে হিসাব হয়; pk আর fpk(x) দেখে random x খোঁজা প্রতিটি PPT প্রতিপক্ষের জন্য negligible সম্ভাবনায় সম্ভব; কিন্তু td জানলে polynomial সময়ে উল্টানো যায়। এমন f-কে বলে trapdoor function.

RSA (Rivest, Shamir, Adleman; ১৯৭৭ সালে প্রস্তাবিত, ১৯৭৮ সালে প্রকাশিত) এর পরিচিত প্রার্থী: pk = (N, e), যেখানে N = pq, আর fN,e(m) = me mod N; trapdoor d = e−1 mod φ(N). গণিত আর সঠিকতার প্রমাণ ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ২৮-এ, আর বাস্তব ব্যবহার cybersecurity কোর্সের পর্ব ১০-এ। এখানে শুধু complexity-র দিকটি দেখুন। নিচের সংখ্যাগুলো ইচ্ছা করেই হাস্যকর রকম ছোট: এটি একটি অনিরাপদ খেলনা, শেখার জন্য।

1N = p·q, φ = (p−1)(q−1)2d = e^(−1) mod φ  (trapdoor)3c = m^e mod N  (সবাই পারে)4m = c^d mod N  (শুধু মালিক)5প্রতিপক্ষ: N factor করে d
খেলনা সংখ্যা
p, q
N, φ
e, d
হিসাব
  1. দুটি মৌলিক। p = 47, q = 59, তাই N = 2773. বাস্তবে p আর q প্রতিটি হাজারখানেক বিটের, আর CSPRNG থেকে বাছা।
  2. φ(N) = (p − 1)(q − 1) = 46 · 58 = 2668. এটি হিসাব করতে p আর q লাগে; শুধু N জানলে φ জানার কোনো দ্রুত পথ জানা নেই।
  3. e আর trapdoor d. e = 17, gcd(17, 2668) = 1. d = 17−1 mod 2668 = 157, কারণ 17 · 157 = 2669 = 2668 + 1. Public key (N, e) = (2773, 17); d গোপন।
  4. Encryption, সবার জন্য সহজ। একটি অর্ডারের পরিমাণ m = 920 টাকা। e = 17-এর binary 10001, তাই square-and-multiply: 920, তারপর তিনটি বর্গে 635, 1140, 1836, শেষে বর্গ আর গুণে 948. শুরুর অর্থহীন 1 · 1 বাদে মাত্র ৬টি গুণ: c = 948.
  5. Decryption, শুধু মালিকের জন্য সহজ। 948157 mod 2773 = 920. Euler-এর উপপাদ্য থেকে med ≡ m (mod N), প্রমাণ DM পর্ব ২৮-এ।
  6. প্রতিপক্ষের পথ। (N, e, c) থেকে N factor করলেই φ আর d. N = 2773 মাত্র 12 বিট, trial division 46টি ভাগে 47 পায়; খেলনা ভেঙে গেল। 2048 বিটের N-এর জন্য কোনো classical algorithm বাস্তব সময়ে এটি পারে বলে জানা নেই, কিন্তু পারে না বলেও প্রমাণ নেই।
# TOY RSA with tiny primes: INSECURE, for learning the complexity idea only
from math import gcd
p, q, e = 47, 59, 17                    # toy primes: anyone can factor N
N, phi = p * q, (p - 1) * (q - 1)
assert gcd(e, phi) == 1
d = pow(e, -1, phi)                     # the trapdoor: needs phi, i.e. p and q
print(f"public key (N, e) = ({N}, {e}); trapdoor d = {d}")
m = 920                                 # an order amount in taka, m < N
c = pow(m, e, N)                        # anyone can do this with (N, e)
print(f"encrypt {m} -> {c}; decrypt with d -> {pow(c, d, N)}")
# Without d: invert by searching all m (exponential in the bit length)
tries = next(t for t in range(N) if pow(t, e, N) == c)
print(f"search without trapdoor finds m = {tries} after {tries + 1} tries")
# With tiny N the trapdoor itself leaks: trial division factors N at once
f = next(k for k in range(2, N) if N % k == 0)
d2 = pow(e, -1, (f - 1) * (N // f - 1))
print(f"trial division: {N} = {f} * {N // f} after {f - 1} divisions; d = {d2}")
# Textbook RSA is deterministic: same amount -> same ciphertext
print("same message twice:", pow(920, e, N), pow(920, e, N))
print("bits of N:", N.bit_length(), "| real keys use 2048+ bits and padding")

আসল আউটপুট (ব্রাউজারের Python):

public key (N, e) = (2773, 17); trapdoor d = 157
encrypt 920 -> 948; decrypt with d -> 920
search without trapdoor finds m = 920 after 921 tries
trial division: 2773 = 47 * 59 after 46 divisions; d = 157
same message twice: 948 948
bits of N: 12 | real keys use 2048+ bits and padding

তিনটি পথ পাশাপাশি: trapdoor দিয়ে ১টি ঘাত, trapdoor ছাড়া 921টি চেষ্টা (N-এর সূচকীয়), আর factoring করে trapdoor নিজেই বের করা। শেষ দুটি লাইন দুটি দুর্বলতা দেখায়। ছোট N খেলনাকে ভাঙে। আর textbook RSA deterministic: একই 920 প্রতিবার একই 948 দেয়, তাই প্রতিপক্ষ সম্ভাব্য পরিমাণগুলো নিজে encrypt করে মেলাতে পারে।

শেষ দুর্বলতাটি তত্ত্বের একটি বড় ধারণায় নিয়ে যায়। Goldwasser আর Micali (১৯৮২) semantic security সংজ্ঞায়িত করেন: ciphertext দেখে বার্তার কোনো ফাংশন অনুমানে PPT প্রতিপক্ষ negligible-এর বেশি সুবিধা পাবে না। কোনো deterministic public-key পদ্ধতি এটি পূরণ করতে পারে না, তাই বাস্তবের RSA random padding (OAEP) যোগ করে। RSA আর factoring-এর সম্পর্কও সূক্ষ্ম:

  • Factoring সহজ হলে RSA ভাঙে (ওপরের ব্লক)।
  • (N, e) থেকে d বের করা factoring-এর সমান কঠিন বলে জানা (randomized reduction থেকে)।
  • কিন্তু d ছাড়া সরাসরি e-তম মূল বের করা, অর্থাৎ “RSA problem”, factoring-এর সমান কঠিন কি না অজানা।
  • Rabin-এর ১৯৭৯ সালের ফাংশন x2 mod N উল্টানো প্রমাণিতভাবে factoring-এর সমান কঠিন।

একটি সত্যিকারের library দিয়ে ব্যবধান মাপা। uv দিয়ে বানানো ছোট প্রকল্পে sympy (BSD licence; network বা usage-reporting অংশ নেই) দিয়ে বাড়তে থাকা আকারের খেলনা N (দুটি প্রায় সমান মৌলিকের গুণফল, seed স্থির) factor করা হলো। পাশে গুণ আর একটি pow(·, 65537, N)-এর সময়।

for bits in (64, 96, 112, 128, 144):
    p = sympy.nextprime(rng.randrange(2 ** (bits // 2 - 1), ...))
    q = sympy.nextprime(rng.randrange(2 ** (bits // 2 - 1), ...))
    t0 = time.perf_counter(); N = p * q; t1 = time.perf_counter()
    t2 = time.perf_counter(); pow(rng.randrange(N), 65537, N); t3 = time.perf_counter()
    t4 = time.perf_counter(); f = sympy.factorint(N); t5 = time.perf_counter()
    assert sorted(f) == sorted({p, q})

সত্যিকারের run (ডেস্কটপ, sympy 1.14.0, Python 3.12.13; পুরো run প্রায় ৪০ সেকেন্ড):

~/bazarghar-toc$ uv run python factor_growth.py
python 3.12.13 | sympy 1.14.0
 bits(N)  multiply(us)  pow(us)   factorint(s)
      64           0.3      3.7         0.029
      95           0.4      4.1         0.113
     111           0.3      4.0         0.134
     127           0.3      4.7         0.911
     144           0.4      4.1        36.484

গুণ আর ঘাত কয়েক microsecond-এই থেকেছে, আকার যা-ই হোক। Factoring 127 বিটে এক সেকেন্ডের কম, অথচ 144 বিটে ৩৬ সেকেন্ড; লাফটি অসমান, কারণ sympy-র পদ্ধতিগুলো (Pollard rho, ECM ইত্যাদি) ভাগ্যের ওপরও নির্ভর করে। এটি একটি চিত্র মাত্র, প্রমাণ নয়: কয়েকটি সময় মেপে কোনো সমস্যার কঠিনতা প্রমাণ হয় না, আর অনেক ভালো factoring প্রোগ্রাম 144 বিট মুহূর্তে ভাঙে। বাস্তবের 2048 বিট এই সারণি থেকে বহু দূরে।

শেষ একটি তাত্ত্বিক বাধা: Impagliazzo আর Rudich (১৯৮৯) দেখান, শুধু একটি OWF-কে “কালো বাক্স” হিসেবে ব্যবহার করে key exchange বানানো যায় না। তাই public-key সম্ভবত OWF-এর চেয়ে শক্ত অনুমান চায়; এই পার্থক্যই অংশ ৭-এর Minicrypt আর Cryptomania-র ভাগ।

৫ · Pseudorandom generator আর indistinguishability

One-time pad-এর সমস্যা ছিল লম্বা key. সমাধানের স্বপ্ন: একটি ছোট এলোমেলো seed থেকে লম্বা বিট-ধারা বানানো, যা কোনো দক্ষ পর্যবেক্ষকের কাছে সত্যিকারের এলোমেলো থেকে আলাদা নয়। পর্ব ৫৬-এর Kolmogorov complexity-র অর্থে এমন ধারা মোটেও এলোমেলো নয়: ছোট seed আর generator-এর code মিলে তার ছোট বর্ণনা। Cryptography এলোমেলোতা মাপে গণনার খরচ দিয়ে।

সংজ্ঞা ৫.১ (PRG)

একটি polynomial সময়ের ফাংশন G: {0,1}n → {0,1}ℓ(n), যেখানে ℓ(n) > n, একটি pseudorandom generator, যদি প্রতিটি PPT distinguisher D-এর জন্য

| Prs ← {0,1}n[D(G(s)) = 1] − Prr ← {0,1}ℓ(n)[D(r) = 1] | ≤ negl(n).

বাঁ দিকের পার্থক্যকে বলে D-এর advantage. দুটি বণ্টনের মধ্যে এই সম্পর্কের নাম computational indistinguishability.

লক্ষ করুন, এটি সাধারণ pseudorandom number generator-এর চেয়ে অনেক শক্ত দাবি: প্রতিটি দক্ষ পরীক্ষায় পাস করতে হবে। নিচের JavaScript ব্লক একটি সরল পরীক্ষা D নেয়: পাশাপাশি দুটি বিট ৬০%-এর বেশি জায়গায় বদলালে D = 1. তিনটি উৎসের ৬৪ বিটের ধারায় D চালানো হয়, ২,০০০ বার করে।

// Distinguisher game: can a simple test D tell a generator from fair coins?
function lcg(seed) {                    // x -> (1103515245 x + 12345) mod 2^31
  let x = seed;
  return () => (x = (Math.imul(1103515245, x) + 12345) & 0x7fffffff);
}
function xorshift(seed) {               // xorshift32: statistically decent
  let x = seed >>> 0;
  return () => { x ^= x << 13; x >>>= 0; x ^= x >>> 17; x ^= x << 5; return (x >>>= 0); };
}
const sources = {
  "LCG low bit ": (s) => { const g = lcg(s); return () => g() & 1; },
  "LCG top bit ": (s) => { const g = lcg(s); return () => (g() >>> 30) & 1; },
  "xorshift bit": (s) => { const g = xorshift(s); return () => g() & 1; },
};
// D: output 1 if the bit changes in more than 60% of neighbouring positions
function D(bits) {
  let flips = 0;
  for (let i = 1; i < bits.length; i++) flips += bits[i] !== bits[i - 1];
  return flips / (bits.length - 1) > 0.6 ? 1 : 0;
}
const L = 64, TRIALS = 2000;
const coin = xorshift(2463534242);      // stand-in for fair coins in this demo
let pRandom = 0;
for (let t = 0; t < TRIALS; t++)
  pRandom += D(Array.from({ length: L }, () => coin() >>> 31));
pRandom /= TRIALS;
console.log(`Pr[D = 1] on fair-looking bits: ${pRandom.toFixed(3)}`);
for (const [name, make] of Object.entries(sources)) {
  let p = 0;
  for (let s = 1; s <= TRIALS; s++) { const g = make(s * 7919); p += D(Array.from({ length: L }, g)); }
  p /= TRIALS;
  console.log(`${name}: Pr[D = 1] = ${p.toFixed(3)}, advantage = ${Math.abs(p - pRandom).toFixed(3)}`);
}

আসল আউটপুট (ব্রাউজারের JavaScript):

Pr[D = 1] on fair-looking bits: 0.054
LCG low bit : Pr[D = 1] = 1.000, advantage = 0.946
LCG top bit : Pr[D = 1] = 0.064, advantage = 0.010
xorshift bit: Pr[D = 1] = 0.060, advantage = 0.006

231 modulus-এর LCG-এর সবচেয়ে নিচের বিট একবার 0, একবার 1 করে চলে, তাই D প্রায় নিশ্চিতভাবে ধরে: advantage 0.946. ওপরের বিট আর xorshift এই পরীক্ষায় পাস করেছে, কিন্তু তাতে তারা PRG হয়ে যায় না। LCG-এর পুরো অবস্থা কয়েকটি আউটপুট থেকেই হিসাব করা যায়, তারপর বাকি সব ভবিষ্যদ্বাণী; xorshift-ও রৈখিক বীজগণিতে ভাঙে। একটি পরীক্ষায় পাস করা মানে কিছুই প্রমাণিত নয়; সংজ্ঞা চায় সব পরীক্ষা। এখানে “fair coin”-ও আসলে একটি xorshift, শুধু তুলনার জন্য।

সাবধান: Python-এর random (Mersenne Twister) আর JavaScript-এর Math.random কোনোটিই cryptographically secure নয়। OTP, token বা key-এর জন্য Python-এ secrets, browser-এ crypto.getRandomValues ব্যবহার করুন। এই পর্বের ব্লকগুলোতে seed স্থির রাখা হয়েছে শুধু ফল মেলানোর জন্য।

উপপাদ্য ৫.২ (PRG থেকে OWF)

G যদি ℓ(n) ≥ 2n দৈর্ঘ্যের একটি PRG হয়, তবে G নিজেই একটি one-way function.

প্রমাণ:

  1. ধরুন একটি PPT A G-কে উল্টায় অ-negligible সম্ভাবনা δ(n)-এ: Prs[G(A(G(s))) = G(s)] = δ(n). — বিরোধের জন্য ধরে নেওয়া
  2. Distinguisher D(y): s′ = A(y) হিসাব করুন; G(s′) = y হলে 1, নইলে 0. D polynomial সময়ের। — নির্মাণ
  3. y = G(s) হলে Pr[D = 1] = δ(n). — ধাপ ১
  4. y সত্যিকারের random, দৈর্ঘ্য 2n হলে D = 1 শুধু তখনই সম্ভব যখন y G-এর image-এ। Image-এ বড়জোর 2nটি string, মোট 22nটির মধ্যে, তাই Pr[D = 1] ≤ 2−n. — গোনা
  5. Advantage ≥ δ(n) − 2−n, যা অ-negligible; PRG-এর সংজ্ঞার বিরোধী। ∎

উল্টো দিকটি অনেক গভীর। Blum–Micali আর Yao (১৯৮২) one-way permutation থেকে PRG বানান; Goldreich আর Levin (১৯৮৯) দেখান যেকোনো OWF-এর একটি hardcore predicate আছে, অর্থাৎ x-এর এমন একটি বিট যা f(x) থেকে অনুমান করা কঠিন। শেষে Håstad, Impagliazzo, Levin আর Luby (১৯৯৯ সালে পূর্ণ প্রকাশ) প্রমাণ করেন: OWF থাকলে PRG আছে। প্রমাণটি দীর্ঘ, এখানে বাদ; Arora–Barak-এর বইয়ের cryptography অধ্যায় আর Goldreich-এর Foundations of Cryptography-তে আছে। এরপর Goldreich–Goldwasser–Micali (১৯৮৬) PRG থেকে pseudorandom function বানান, আর তা থেকে symmetric encryption.

দুটি সংযোগ মনে রাখুন। পর্ব ৬৯-এর derandomization-এও PRG লাগে, তবে সেখানে generator distinguisher-এর চেয়ে বেশি সময় নিতে পারে, তাই দুর্বলতর অনুমানই যথেষ্ট (hardness vs randomness). আর পর্ব ৭০-এর natural proofs বাধা বলে: শক্ত pseudorandom function থাকলে, অর্থাৎ cryptography সফল হলে, circuit lower bound প্রমাণের স্বাভাবিক কৌশলগুলোই ব্যর্থ। নিরাপত্তা আর lower bound প্রমাণ একই কঠিনতার দুই মুখ।

৬ · Hash function আর collision resistance — birthday bound

বাজারঘর প্রতিটি চুক্তির ফাইলের ছোট একটি “আঙুলের ছাপ” রাখে, যাতে পরে কেউ ফাইল বদলালে ধরা পড়ে। এই ছাপ দেয় একটি hash function: যেকোনো দৈর্ঘ্যের input থেকে স্থির ℓ বিটের আউটপুট। Input অসীম, আউটপুট সসীম, তাই pigeonhole principle থেকে দুটি আলাদা input-এর একই ছাপ, অর্থাৎ collision, সবসময় আছে। প্রশ্ন শুধু: খুঁজে পাওয়া কত কঠিন?

সংজ্ঞা ৬.১ (Collision-resistant hash family)

একটি পরিবার {hs}: Gen(1n) একটি key s দেয় (প্রকাশ্য), hs: {0,1}∗ → {0,1}ℓ(n) polynomial সময়ে হিসাবযোগ্য, আর প্রতিটি PPT A-এর জন্য Pr[A(s) এমন x ≠ x′ দেয় যাতে hs(x) = hs(x′)] ≤ negl(n). এই গুণের নাম collision resistance.

Key s কেন? একটি নির্দিষ্ট h-এর জন্য collision (x, x′) কোথাও আছেই, আর পর্ব ৭০-এর non-uniform প্রতিপক্ষ (প্রতিটি n-এর জন্য আলাদা circuit) জোড়াটি নিজের ভেতরে লিখে রাখতে পারে। তাই তত্ত্বে random s-সহ পরিবার; বাস্তবের SHA-256 একটিই স্থির ফাংশন, আর বিশ্বাস হলো কেউ তার collision জানে না। যেকোনো hash-এ একটি সাধারণ আক্রমণ সবসময় খাটে:

উপপাদ্য ৬.২ (Birthday bound)

M = 2ℓটি সম্ভাব্য আউটপুট সমানভাবে আর স্বাধীনভাবে পড়লে, q টি input-এ অন্তত একটি collision-এর সম্ভাবনা

1 − ∏i=1q−1 (1 − i/M) ≥ 1 − e−q(q−1)/2M,   আর ≤ q(q − 1)/2M.

তাই অর্ধেক সম্ভাবনা আসে q ≈ 1.18 · 2ℓ/2-এ, আর প্রথম collision-এর প্রত্যাশিত সময় ≈ √(π/2) · 2ℓ/2 ≈ 1.25 · 2ℓ/2.

প্রমাণের রূপরেখা: i-তম নতুন input আগের i টি মানের কোনোটিতে না পড়ার সম্ভাবনা 1 − i/M; গুণ করলে “কোনো মিল নেই”-এর সম্ভাবনা। 1 − t ≤ e−t বসিয়ে যোগফল Σ i = q(q − 1)/2 পাওয়া যায়, যা নিম্নসীমা দেয়। ঊর্ধ্বসীমা আসে union bound থেকে: q(q − 1)/2টি জোড়ার প্রতিটি 1/M সম্ভাবনায় মেলে। বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৪২-এ। নিচের stepper M = 256 (একটি 8-bit hash)-এ সংখ্যাগুলো দেখায়।

1P(মিল নেই) = ∏ (1 − i/256)2জোড়া = q(q − 1)/23আসন্ন: 1 − e^(−জোড়া/256)
q টি input-এর পরে
q
জোড়া
P(collision)
আসন্ন মান
  1. q = 5. জোড়া মাত্র ১০টি, collision-এর সম্ভাবনা 0.0385. স্বজ্ঞা বলে 256টি ঘরে ৫টি বল প্রায় কখনো মেলে না, আর তা-ই সত্য।
  2. q = 10. Input 256-এর মাত্র ৪%, কিন্তু জোড়া ৪৫টি; সম্ভাবনা 0.1631. জোড়ার সংখ্যা q2-এর মতো বাড়ে, এটিই গোপন কারণ।
  3. q = 16 = √M. জোড়া ১২০, সম্ভাবনা 0.3803. আসন্ন সূত্র 1 − e−120/256 = 0.3742, প্রায় মিলে যায়।
  4. q = 19. জোড়া ১৭১, সম্ভাবনা 0.4957, অর্ধেকের ঠিক নিচে। তত্ত্বের 1.1774 · √256 ≈ 18.8.
  5. q = 20. সম্ভাবনা 0.5332, অর্ধেক পেরোল। তাই 8-bit hash-এ মাত্র ২০টি input-এ collision-এর সম্ভাবনা অর্ধেকের বেশি।
  6. q = 30. সম্ভাবনা 0.8294. সাধারণ নিয়ম: ℓ বিটের hash-এর collision-নিরাপত্তা মাত্র ℓ/2 বিট; তাই 256-bit hash-এ প্রায় 2128 চেষ্টা। জন্মদিনের গল্পে ২৩ জনে অর্ধেক পেরোয়, একই হিসাব M = 365-এ।

এখন একটি আসল hash. নিচের ব্লক SHA-256-এর আউটপুটের প্রথম n বিট রাখে (ইচ্ছা করে দুর্বল করা), আর কাল্পনিক অর্ডার কোড BG-0000001, BG-0000002, … একে একে hash করে প্রথম collision খোঁজে। শেষে n = 20-এ ১০০টি আলাদা “salt” দিয়ে গড়ও নেয়।

# Birthday attack on SHA-256 cut down to n bits: a collision after ~2^(n/2) tries
import hashlib, math
def h(msg, n):                          # first n bits of SHA-256
    full = int.from_bytes(hashlib.sha256(msg.encode()).digest(), "big")
    return full >> (256 - n)
print(" n   tries   2^(n/2)  tries/2^(n/2)  colliding pair")
for n in (16, 20, 24, 28, 32):
    seen = {}
    for i in range(1, 2 ** n + 2):      # pigeonhole: must stop by 2^n + 1
        msg = f"BG-{i:07d}"             # invented order codes
        v = h(msg, n)
        if v in seen:
            break
        seen[v] = msg
    print(f"{n:2} {i:7} {2 ** (n // 2):9} {i / 2 ** (n / 2):13.2f}  "
          f"{seen[v]} / {msg}")
def first_collision(n, salt):
    seen = set()
    for i in range(1, 2 ** n + 2):
        v = h(f"{salt}-{i}", n)
        if v in seen:
            return i
        seen.add(v)
avg = sum(first_collision(20, s) for s in range(100)) / 100
print(f"n = 20, 100 salted runs: mean tries = {avg:.0f} = "
      f"{avg / 2 ** 10:.2f} * 2^10")
print("expected tries ~ sqrt(pi/2) * 2^(n/2) =",
      round(math.sqrt(math.pi / 2), 3), "* 2^(n/2)")
print("full 256 bits: ~2^128 tries; brute-force preimage: ~2^256")

আসল আউটপুট (ব্রাউজারের Python):

 n   tries   2^(n/2)  tries/2^(n/2)  colliding pair
16     264       256          1.03  BG-0000150 / BG-0000264
20     270      1024          0.26  BG-0000050 / BG-0000270
24    1186      4096          0.29  BG-0000185 / BG-0001186
28   23723     16384          1.45  BG-0019095 / BG-0023723
32   97655     65536          1.49  BG-0055665 / BG-0097655
n = 20, 100 salted runs: mean tries = 1235 = 1.21 * 2^10
expected tries ~ sqrt(pi/2) * 2^(n/2) = 1.253 * 2^(n/2)
full 256 bits: ~2^128 tries; brute-force preimage: ~2^256

একটি run-এ অনুপাত 0.26 থেকে 1.49 পর্যন্ত ছড়ানো, কারণ প্রথম collision একটি random ঘটনা। ১০০টি run-এর গড় 1.21 · 210, তত্ত্বের 1.25-এর খুব কাছে। প্রতি ৪ বিটে চেষ্টা প্রায় ৪ গুণ বাড়ে, 16 গুণ নয়: এটিই 2n/2. পুরো 256 বিটে 2128 চেষ্টা কোনো যন্ত্রের নাগালে নেই। Hash-এর বাস্তব নির্বাচন আর HMAC নিয়ে cybersecurity কোর্সের পর্ব ০৯ দেখুন।

Complexity-র দিক থেকে দুটি কথা। প্রথম, একটি সংকোচনকারী collision-resistant পরিবার থেকে OWF পাওয়া যায় (প্রমাণের রূপরেখা: hs সহজে উল্টানো গেলে একটি random x-এর preimage x′ খুঁজুন; সংকোচনের জন্য অধিকাংশ x-এর অনেক preimage, তাই x′ ≠ x উচ্চ সম্ভাবনায়, আর সেটিই collision). দ্বিতীয়, উল্টোটা জানা নেই: Simon (১৯৯৮) দেখান, OWF-কে কালো বাক্স হিসেবে ব্যবহার করে collision-resistant hash বানানো যায় না।

৭ · Impagliazzo-র পাঁচ জগৎ আর post-quantum lattice

এতক্ষণের সব ফল শর্তসাপেক্ষ। Russell Impagliazzo ১৯৯৫ সালের “A Personal View of Average-Case Complexity” প্রবন্ধে সম্ভাবনাগুলোকে পাঁচটি কাল্পনিক জগৎ হিসেবে সাজান (পর্ব ৬৩-এ নাম দুটি এসেছিল)। সংজ্ঞাগুলো এখানে অনানুষ্ঠানিক; মূল প্রবন্ধে খুঁটিনাটি আছে।

জগৎকী সত্যCryptography
AlgorithmicaP = NP (বা কার্যত সমান)নেই; কিন্তু সব search আর optimisation সহজ
HeuristicaNP worst-case-এ কঠিন, কিন্তু স্বাভাবিক বণ্টনের instance-এ গড়ে সহজনেই
Pessilandগড়ে কঠিন সমস্যা আছে, কিন্তু OWF নেইনেই; সবচেয়ে হতাশার জগৎ
MinicryptOWF আছে, public-key নেইPRG, symmetric encryption, signature
CryptomaniaTrapdoor বা public-key আছেপূর্ণ: key exchange, public-key encryption

আমরা কোন জগতে আছি, প্রমাণিত নয়। বেশিরভাগ গবেষক মনে করেন Cryptomania, কারণ factoring আর lattice-এর ওপর দশকের পর দশকের আক্রমণ ব্যর্থ। লক্ষ করুন পাঁচ জগতের ক্রমটি আসলে বাড়তে থাকা অনুমানের সিঁড়ি: P ≠ NP শুধু Algorithmica বাদ দেয়, OWF Minicrypt পর্যন্ত নিয়ে যায়, আর public-key-এর জন্য আরও একটি ধাপ লাগে।

Shor-এর পর: quantum প্রতিপক্ষ আর LWE

Peter Shor ১৯৯৪ সালে দেখান, একটি বড় আর নির্ভুল quantum কম্পিউটার factoring আর discrete log polynomial সময়ে করতে পারে (Shor's algorithm; বিস্তারিত পর্ব ৭৫-এ)। তখন RSA, Diffie–Hellman আর elliptic curve, সবই ভাঙে। Grover-এর search brute force-কে শুধু বর্গমূল গুণ দ্রুত করে, তাই symmetric key লম্বা করলেই চলে। প্রতিপক্ষের সংজ্ঞা তাই বদলায়: PPT-এর জায়গায় quantum polynomial সময়। এমন প্রতিপক্ষের বিরুদ্ধেও নিরাপদ বলে বিশ্বাস করা পদ্ধতির নাম post-quantum cryptography, আর তার প্রধান ভিত্তি lattice.

সংজ্ঞা ৭.১ (Learning With Errors, অনানুষ্ঠানিক)

একটি গোপন s ∈ Zqn. প্রতিপক্ষ পায় অনেক জোড়া (ai, bi), যেখানে ai random আর bi = ⟨ai, s⟩ + ei mod q, ei একটি ছোট random ভুল। Search রূপ: s বের করা। Decision রূপ: জোড়াগুলো এই নিয়মে বানানো, না পুরোপুরি random, তা আলাদা করা।

ভুল ei না থাকলে এটি সাধারণ রৈখিক সমীকরণ, যা Gaussian elimination polynomial সময়ে সমাধান করে। ছোট ভুল যোগ করলেই সমস্যাটি কঠিন বলে মনে হয়। আর এখানে আছে NP-complete সমস্যায় যা নেই: Oded Regev ২০০৫ সালে একটি (quantum) reduction দেন, যা দেখায় average-case LWE অন্তত ততটা কঠিন যতটা কিছু lattice সমস্যার (একটি polynomial গুণক পর্যন্ত approximate shortest vector) worst case. Ajtai ১৯৯৬ সালে একই ধরনের worst-case থেকে average-case সংযোগ প্রথম দেখান। অর্থাৎ random key ভাঙা গেলে lattice সমস্যার প্রতিটি instance-ই ভাঙা যেত। সাবধান: এই approximation গুণকে lattice সমস্যাগুলো NP-hard বলে জানা নেই, আর কোনো দক্ষ quantum algorithm LWE সমাধান করে বলে জানা নেই, কিন্তু অসম্ভব বলেও প্রমাণিত নয়।

বাস্তবে NIST ২০২৪ সালে প্রথম post-quantum মানগুলো প্রকাশ করে: FIPS 203 (ML-KEM, module-lattice-ভিত্তিক key encapsulation), FIPS 204 (ML-DSA, lattice-ভিত্তিক signature) আর FIPS 205 (SLH-DSA, hash-ভিত্তিক signature). একটি প্রতিষ্ঠান কীভাবে ধাপে ধাপে এদিকে যায়, তা cybersecurity কোর্সের পর্ব ১৪-এ।

৮ · তত্ত্ব থেকে নিরাপদ অভ্যাস

এই পর্বের প্রতিটি নিরাপত্তা-দাবি একটি reduction: “এই পদ্ধতি ভাঙতে পারলে ওই কঠিন সমস্যা সমাধান হতো।” এর তিনটি বাস্তব শিক্ষা:

  • প্রমাণ শুধু মডেলের ভেতরে। Reduction ধরে নেয় প্রতিপক্ষ শুধু ইনপুট-আউটপুট দেখে। সময়ের পার্থক্য, বিদ্যুৎ খরচ বা ভুল বার্তা থেকে তথ্য ফাঁস (side channel) মডেলের বাইরে; প্রমাণিত পদ্ধতির ভুল implementation-ও ভাঙে।
  • নিজে বানাবেন না। নিজের বানানো cipher বা protocol-এর দুর্বলতা নির্মাতা নিজে দেখতে পান না, ঠিক Merkle–Hellman-এর মতো। পরীক্ষিত library আর মান ব্যবহার করুন (roll your own crypto-এর বিপদ cybersecurity কোর্সের পর্ব ০৭ আর পর্ব ১৪-এ)।
  • খেলনা খেলনাই থাকুক। এই পর্বের toy RSA, ছোট hash আর xorshift শেখার জন্য; কোনো আসল তথ্য, password বা key-এ নয়। আর পরীক্ষা শুধু নিজের code আর নিজের তৈরি data-য়।

আরও গভীরে: Impagliazzo আর Luby (১৯৮৯) দেখান, OWF না থাকলে যেকোনো polynomial সময়ের ফাংশন “বণ্টনের অর্থে” উল্টানো যায়; ফলে সমাধানসহ বানানো NP instance গড়ে সহজ হয়ে যায়, আর Pessiland-এর কঠিন সমস্যাগুলো সমাধানসহ বানানো যায় না। সাম্প্রতিক কাজে OWF-এর অস্তিত্বকে time-bounded Kolmogorov complexity-র গড় কঠিনতার সঙ্গে সমতুল্য দেখানো হয়েছে (Liu–Pass ২০২০), যা পর্ব ৫৬-এর ধারণাকে cryptography-র কেন্দ্রে আনে। আর indistinguishability obfuscation-এর মতো নতুন ধারণা সত্যিকারের নতুন জগতের প্রশ্ন তোলে; এসব গবেষণার সীমানা, প্রতিষ্ঠিত পাঠ্য নয়।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • One-way function-এর সংজ্ঞা দিন। Polynomial সময়ে হিসাবযোগ্য; প্রতিটি PPT A-এর random x-এর f(x) থেকে কোনো preimage পাওয়ার সম্ভাবনা negligible.
  • OWF থাকলে P ≠ NP কেন? P = NP হলে PREf ∈ P, আর prefix প্রশ্নে n বার জিজ্ঞেস করে x বের হয়।
  • P ≠ NP হলে কি cryptography নিরাপদ? না: P ≠ NP worst-case; OWF-এর জন্য average-case আর সমাধানসহ instance লাগে।
  • n-bit hash-এ collision কত চেষ্টায়? প্রায় 2n/2 (birthday bound); preimage-এর generic খরচ 2n.
  • Trapdoor function কী, উদাহরণ দিন। Trapdoor ছাড়া উল্টানো কঠিন, trapdoor-সহ সহজ; RSA-তে d (বা p, q).

৯ · AI-এর যুগে cryptography-র complexity

AI assistant cryptography নিয়ে খুব আত্মবিশ্বাসী উত্তর দেয়, আর এই বিষয়ে আত্মবিশ্বাসী ভুল সবচেয়ে বিপজ্জনক। কয়েকটি ভুল বারবার দেখা যায়:

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“RSA-র নিরাপত্তা প্রমাণিত” বা “factoring NP-complete”দুটিই অপ্রমাণিত; factoring NP ∩ coNP-তে (পর্ব ৬২)
“P ≠ NP প্রমাণ হলে cryptography নিরাপদ”Worst-case বনাম average-case; দিকটি উল্টো: OWF ⇒ P ≠ NP
OWF-এর সংজ্ঞায় “আসল x খোঁজা” বা “কিছু x-এ কঠিন”যেকোনো preimage, random x-এ, negligible সম্ভাবনা
Token-এর জন্য random বা Math.randomsecrets বা crypto.getRandomValues
Padding ছাড়া textbook RSA-কে “নিরাপদ encryption” বলাDeterministic, তাই semantic security নেই
“Quantum কম্পিউটার সব encryption ভাঙে”Shor শুধু factoring আর discrete log; LWE-র দক্ষ quantum algorithm জানা নেই
বানানো সাল, নাম বা FIPS নম্বরমূল প্রবন্ধ, Goldreich, Katz–Lindell বা NIST-এর নথিতে মেলান

AI-কে কাজে লাগানোর ভালো উপায়: সংজ্ঞা আর reduction-এর দিক আলাদা করে চাওয়া, প্রতিটি দাবির পাশে “প্রমাণিত, না অনুমান” লেখানো, আর ছোট সংখ্যায় code নিজে চালিয়ে মেলানো।

আমি গণনার তত্ত্ব শিখছি, বিষয় cryptography-র complexity. নিচের কাজগুলো করো। ১. One-way function-এর নিখুঁত সংজ্ঞা দাও: কোন সম্ভাবনা, কার ওপর নেওয়া, আর negligible মানে কী। ২. “OWF থাকলে P ≠ NP”-এর প্রমাণ ধাপে ধাপে লেখো। কোন language NP-তে রাখছ আর কেন, স্পষ্ট বলো। ৩. P ≠ NP থেকে OWF কেন আসে না, worst-case আর average-case দিয়ে ব্যাখ্যা করো। ৪. ছোট মৌলিক দিয়ে একটি toy RSA-র Python script লেখো, যা key, encryption আর decryption মেলায়, আর স্পষ্ট লেখে যে এটি অনিরাপদ খেলনা। কোনো আউটপুট নিজে বানিয়ো না। ৫. প্রতিটি বক্তব্যের পাশে লেখো সেটি প্রমাণিত, না অনুমান। কোনো সাল বা নাম নিশ্চিত না হলে বলো, বানিয়ো না।

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

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১হাজারো NP-complete সমস্যা আছে, যাদের কোনোটির polynomial algorithm নেই বলে প্রায় সবাই বিশ্বাস করেন। তাহলে cryptography এদের কোনো একটির ওপর কেন দাঁড়ায় না?

প্রথম বাধা worst-case আর average-case-এর ফারাক। NP-completeness বলে, P ≠ NP হলে প্রতিটি দ্রুত algorithm কোনো না কোনো instance-এ ব্যর্থ। কিন্তু একটি key-generator-কে প্রতিবার এমন instance বানাতে হবে যেটি কঠিন, আর কোন instance কঠিন তা algorithm-ভেদে বদলায়। Random 3SAT সূত্রের বড় অংশ, বিশেষত clause আর variable-এর অনুপাত সংকট-বিন্দু থেকে দূরে থাকলে, বাস্তবের solver দ্রুত মীমাংসা করে। তাই “NP-complete সমস্যার random instance” আপনা-আপনি কঠিন নয়।

দ্বিতীয় বাধা হলো সমাধানসহ instance. মালিককে গোপনটি জানতে হবে, তাই generator আগে সমাধান বাছে, তারপর তার চারপাশে instance বানায়। এমন “লুকানো সমাধান”-এর instance প্রায়ই বিশেষ গঠনের হয়, আর সেই গঠনই দুর্বলতা। Merkle–Hellman-এর knapsack পদ্ধতি ঠিক এভাবে পড়ে: Shamir ১৯৮২ সালে দেখান যে লুকানো superincreasing কাঠামো polynomial সময়ে বের করা যায়।

তৃতীয় বাধা তাত্ত্বিক। Brassard ১৯৭৯ সালে লক্ষ করেন, একটি one-way permutation উল্টানো NP-hard হলে (একটি স্বাভাবিক reduction-এ) NP = coNP হতো, কারণ permutation-এর উল্টো মান নিজেই দুই দিকের certificate দেয়। পরে Feigenbaum–Fortnow আর Bogdanov–Trevisan দেখান, non-adaptive worst-to-average reduction NP-complete সমস্যা থেকে এলে polynomial hierarchy ধসে পড়ত। অর্থাৎ সহজ পথগুলো বন্ধ, অন্তত এই ধরনের reduction দিয়ে।

Lattice-এর গল্প এখানে আকর্ষণীয় ব্যতিক্রম। Ajtai আর Regev worst-case থেকে average-case reduction দিয়েছেন, কিন্তু তা lattice সমস্যার এমন approximation গুণকে, যেখানে সমস্যাটি NP ∩ coNP-তে বলে জানা (Aharonov–Regev). অর্থাৎ worst-case ভিত্তি পাওয়া গেছে, কিন্তু NP-hard সংস্করণের নয়। তাই আজকের cryptography নির্দিষ্ট, গঠনসমৃদ্ধ সমস্যার ওপর দাঁড়িয়ে, যাদের অবস্থান সম্ভবত NP-intermediate-এর কাছাকাছি।

মূল উপলব্ধি: Cryptography-র দরকার সমাধানসহ বানানো যায় এমন average-case কঠিন instance; NP-completeness তা দেয় না, আর কিছু স্বাভাবিক reduction দিয়ে দেওয়া অসম্ভব বলেও প্রমাণিত, যদি না complexity class ধসে পড়ে।

প্র ০২Shannon-এর perfect secrecy প্রমাণসহ নিরাপদ, তবু বাস্তবের প্রায় কেউ one-time pad ব্যবহার করে না। Computational security ঠিক কী হারায় আর কী পায়, আর P = NP হলে কী হতো?

One-time pad-এ বার্তা m-এর সঙ্গে সমান দৈর্ঘ্যের random key k XOR করা হয়। প্রতিটি সম্ভাব্য বার্তা প্রতিটি ciphertext-এর সঙ্গে সমান সম্ভাবনায় মেলে, তাই অসীম ক্ষমতার প্রতিপক্ষও কিছু শেখে না। Shannon ১৯৪৯ সালে দেখান, এই নিশ্চয়তার জন্য key-এর সম্ভাব্য মান অন্তত বার্তার সম্ভাব্য মানের সমান হতে হয়। আর key দুবার ব্যবহার করলে দুটি ciphertext-এর XOR থেকে দুটি বার্তার XOR বেরিয়ে পড়ে।

অর্থাৎ বাজারঘর যদি এক বছরে এক gigabyte গোপন তথ্য পাঠাতে চায়, তাকে আগেই এক gigabyte গোপন key প্রতিটি সঙ্গীর কাছে নিরাপদে পৌঁছাতে হবে। সেটিই যদি পারা যায়, তবে বার্তাটিই সেই পথে পাঠানো যেত। এই চক্র ভাঙে computational security: একটি 128 বা 256 বিটের key থেকে PRG দিয়ে লম্বা pad বানানো (অংশ ৫)। দাম হলো দুটি: নিরাপত্তা এখন শুধু দক্ষ প্রতিপক্ষের বিরুদ্ধে, আর তা একটি অপ্রমাণিত অনুমানের (PRG বা OWF আছে) ওপর।

P = NP হলে এই পথ পুরো বন্ধ হতো। যেকোনো encryption, যার key বার্তার চেয়ে ছোট, তার জন্য প্রশ্নটি “এমন key আছে কি না যা এই ciphertext-কে এই prefix-এর বার্তায় খোলে” একটি NP প্রশ্ন। Shannon-এর যুক্তিতে ছোট key-এ কিছু তথ্য ফাঁস হয়ই, আর P = NP হলে polynomial সময়ে তা কাজে লাগানো যেত। তাই P = NP-এর জগতে নিরাপদ গোপনীয়তার একমাত্র পথ হতো Shannon-এর পথ।

তবে সূক্ষ্মতা আছে। প্রথম, “polynomial” মানেই দ্রুত নয়; n50 সময়ের আক্রমণ বাস্তবে অর্থহীন। দ্বিতীয়, P ≠ NP প্রমাণ হলেও computational security-র ভিত্তি আসত না (অংশ ৩)। তৃতীয়, quantum key distribution-এর মতো পদ্ধতি পদার্থবিদ্যার নিয়মের ওপর দাঁড়ায়, কিন্তু তারও প্রমাণীকরণের জন্য সাধারণত আগে ভাগ করা গোপন কিছু বা classical signature লাগে।

মূল উপলব্ধি: Perfect secrecy নিশ্চিত কিন্তু অবাস্তব; computational security একটি ছোট key দিয়ে অসীম বার্তা রক্ষা করে, বিনিময়ে নির্ভর করে একটি অপ্রমাণিত complexity অনুমানের ওপর, যা P = NP হলে ভেঙে পড়ত।

প্র ০৩“RSA ভাঙা মানে N factor করা” কথাটি প্রায়ই শোনা যায়। এটি কতটা সঠিক, আর Rabin-এর পদ্ধতি এই প্রশ্নে কী যোগ করে?

এক দিক নিশ্চিত: N factor করতে পারলে φ(N) = (p − 1)(q − 1) হিসাব হয়, তা থেকে d, আর সব ciphertext খোলে। তাই RSA অন্তত factoring-এর চেয়ে সহজ বা সমান। প্রশ্ন উল্টো দিকে: RSA ভাঙতে কি factoring লাগবেই?

এখানে দুটি আলাদা প্রশ্ন গুলিয়ে যায়। (N, e) থেকে গোপন d বের করার কাজটি factoring-এর সমান কঠিন বলে জানা: d জানলে ed − 1 হলো φ(N)-এর একটি গুণিতক, আর তা থেকে একটি randomized পদ্ধতিতে N factor করা যায় (পরে এর deterministic রূপও দেখানো হয়েছে বলে জানা যায়)। কিন্তু প্রতিপক্ষের d লাগবেই, এমন নয়। সে হয়তো d না জেনেই প্রতিটি c-এর e-তম মূল বের করতে পারে। এই “RSA problem” factoring-এর সমান কঠিন কি না, তা আজও খোলা। Boneh আর Venkatesan ১৯৯৮ সালে কিছু প্রমাণ দেন যে ছোট e-এর ক্ষেত্রে একটি নির্দিষ্ট ধরনের reduction দিয়ে সমতুল্যতা দেখানো যাবে না, যা ইঙ্গিত দেয় RSA ভাঙা factoring-এর চেয়ে সহজও হতে পারে।

Michael Rabin ১৯৭৯ সালে f(x) = x2 mod N প্রস্তাব করেন। এর প্রতিটি বর্গের সাধারণত চারটি বর্গমূল। কেউ যদি যেকোনো বর্গমূল বের করতে পারে, তবে একটি random x নিয়ে x2 দিন; উত্তর y যদি ±x না হয় (সম্ভাবনা অর্ধেক), তবে gcd(x − y, N) একটি উৎপাদক দেয়। তাই Rabin-এর ফাংশন উল্টানো প্রমাণিতভাবে factoring-এর সমান কঠিন। মজার কথা, এই প্রমাণই একটি দুর্বলতাও দেখায়: যে আক্রমণকারী নিজের পছন্দের ciphertext-এর decryption দেখতে পায়, সে একই কৌশলে N factor করে ফেলে।

বাস্তবে আরও স্তর আছে। RSA padding ছাড়া ব্যবহার করা যায় না, আর padding-এর নিরাপত্তা প্রমাণ সাধারণত “random oracle” নামের আদর্শ মডেলে। তাই বাস্তবের RSA-র নিরাপত্তা একাধিক অনুমানের যোগফল।

মূল উপলব্ধি: Factoring ⇒ RSA ভাঙা প্রমাণিত, উল্টোটা খোলা; d বের করা factoring-এর সমান, কিন্তু e-তম মূল বের করা হয়তো সহজতর; Rabin-এর পদ্ধতিতে সমতা প্রমাণিত, তবে তা chosen-ciphertext আক্রমণের দরজাও খোলে।

প্র ০৪একই ধারণা “pseudorandom” তিনটি জায়গায় এসেছে: Kolmogorov complexity, derandomization আর natural proofs. এরা কীভাবে একে অপরের সঙ্গে জড়িত?

Kolmogorov-এর দৃষ্টিতে একটি string এলোমেলো যদি তার ছোট বর্ণনা না থাকে। একটি PRG-এর আউটপুট এই অর্থে কখনো এলোমেলো নয়: seed আর generator-এর code মিলে n + O(1) দৈর্ঘ্যের বর্ণনা, অথচ আউটপুট 2n বা আরও লম্বা। কিন্তু সেই বর্ণনা খুঁজে পেতে seed খুঁজতে হবে, যা দক্ষ যন্ত্রের সাধ্যের বাইরে। তাই cryptography “বর্ণনার দৈর্ঘ্য” বাদ দিয়ে “দক্ষ পরীক্ষায় ধরা পড়ে কি না” দিয়ে এলোমেলোতা সংজ্ঞায়িত করে। Yao ১৯৮২ সালে দেখান, সব দক্ষ পরীক্ষায় পাস করা আর “আগের বিট দেখে পরের বিট অনুমান করা যায় না” (next-bit test) সমতুল্য।

Derandomization উল্টো দিক থেকে আসে। পর্ব ৬৯-এ BPP algorithm-এর random বিট বদলে PRG-এর বিট বসালে, আর সব seed চেষ্টা করলে, deterministic algorithm পাওয়া যায়, যদি seed ছোট (O(log n)) হয়। এখানে generator-কে distinguisher-এর চেয়ে বেশি সময় নিতে দেওয়া চলে, কারণ কোনো প্রতিপক্ষ নেই; তাই circuit lower bound-এর মতো দুর্বলতর অনুমান যথেষ্ট (Nisan–Wigderson, Impagliazzo–Wigderson). Cryptographic PRG থাকলে BPP-কে subexponential সময়ে deterministic ভাবে চালানো যায় বলেও জানা।

Natural proofs বাধা গল্পটি পূর্ণ করে। Razborov আর Rudich ১৯৯৪ সালে দেখান, যদি শক্ত pseudorandom function থাকে, তবে “সহজে পরীক্ষাযোগ্য, আর বেশিরভাগ random function-এর আছে” এমন ধর্ম দিয়ে P/poly-এর বাইরে প্রমাণ সম্ভব নয়; কারণ সেই ধর্মটি নিজেই একটি distinguisher হতো, যা pseudorandom function-কে সত্যিকারের random function থেকে আলাদা করত। Cryptography যত সফল, lower bound প্রমাণ তত কঠিন।

তিনটি মিলিয়ে একটি বড় ছবি দাঁড়ায়: কঠিনতা আর এলোমেলোতা একই মুদ্রার দুই পিঠ। কঠিন ফাংশন থাকলে এলোমেলোতা বানানো যায় (PRG), এলোমেলোতা দরকার কমে (derandomization), আর সেই একই কঠিনতা আমাদের প্রমাণের কৌশলকে আটকে দেয়। Liu আর Pass ২০২০ সালে OWF-এর অস্তিত্বকে time-bounded Kolmogorov complexity-র গড় কঠিনতার সঙ্গে সমতুল্য দেখিয়ে বৃত্তটি আরও শক্ত করেছেন।

মূল উপলব্ধি: Pseudorandomness মানে দক্ষ পরীক্ষায় অধরা; Kolmogorov-এর অর্থে তা এলোমেলো নয়, derandomization-এ তা randomness বাঁচায়, আর natural proofs-এ তা lower bound প্রমাণকে আটকায়, সবই একই কঠিনতার ফল।

প্র ০৫বড় quantum কম্পিউটার এখনো নেই, তবু আজই post-quantum পদ্ধতিতে যাওয়ার কথা বলা হয় কেন? আর lattice-ভিত্তিক পদ্ধতি কি “প্রমাণিতভাবে” quantum-নিরাপদ?

কারণটি সময়ের হিসাব। আজ পাঠানো একটি encrypted বার্তা কেউ সংরক্ষণ করে রাখতে পারে, আর ভবিষ্যতে বড় quantum কম্পিউটার এলে খুলতে পারে। এর নাম “harvest now, decrypt later”. যে তথ্য বহু বছর গোপন রাখতে হয়, যেমন স্বাস্থ্য বা আইনি নথি, তার জন্য ঝুঁকিটি আজকেরই। তার ওপর বড় একটি প্রতিষ্ঠানের সব system-এ নতুন cryptography বসাতে বহু বছর লাগে। তাই NIST ২০২৪ সালে প্রথম মান প্রকাশ করে, আর অনেক প্রতিষ্ঠান এখন পুরোনো ও নতুন পদ্ধতি একসঙ্গে চালানোর (hybrid) পথে যাচ্ছে।

এখন complexity-র প্রশ্ন: lattice কি প্রমাণিত নিরাপদ? না। প্রমাণিত শুধু একটি reduction: LWE-র random instance ভাঙা গেলে কিছু lattice সমস্যার worst-case-ও ভাঙা যেত (Regev ২০০৫, যার reduction নিজেই quantum). এটি RSA-র চেয়ে শক্ত ধরনের নিশ্চয়তা, কারণ key-generator-এর random instance-এর কঠিনতা সবচেয়ে কঠিন instance-এর সঙ্গে বাঁধা। কিন্তু সেই worst-case lattice সমস্যা যে quantum কম্পিউটারে কঠিন, তা একটি অনুমান; বহু বছরের চেষ্টায় দক্ষ quantum algorithm পাওয়া যায়নি, এটুকুই প্রমাণ।

ইতিহাসও সতর্ক করে। NIST-এর প্রতিযোগিতায় কয়েকটি প্রার্থী শেষ পর্যায়ে এসে classical কম্পিউটারেই ভেঙে পড়ে, যেমন isogeny-ভিত্তিক SIKE ২০২২ সালে। তাই একই সঙ্গে hash-ভিত্তিক signature-ও মান হিসেবে রাখা হয়েছে (FIPS 205), যার নিরাপত্তা শুধু hash function-এর ওপর, ভিন্ন ধরনের অনুমানে।

Impagliazzo-র ভাষায়, আমরা এখন জিজ্ঞেস করছি quantum প্রতিপক্ষের জন্যও Cryptomania টিকে থাকে কি না। Shor দেখিয়েছেন factoring-এর Cryptomania quantum জগতে টেকে না; lattice-এর Cryptomania টেকে বলে আশা, প্রমাণ নয়। Quantum কম্পিউটার NP-complete সমস্যা দক্ষভাবে সমাধান করে বলে জানা নেই, তাই OWF-এর ধারণা নিজে বিপদে নেই।

মূল উপলব্ধি: সংরক্ষিত ciphertext ভবিষ্যতে খোলার ঝুঁকি আর বদলের দীর্ঘ সময়ের জন্য post-quantum আজকের কাজ; lattice-এর নিরাপত্তা worst-case থেকে average-case reduction-এ মজবুত, কিন্তু শেষ পর্যন্ত একটি অনুমান, তাই ভিন্ন ভিত্তির বিকল্পও রাখা হয়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের সংখ্যা বসিয়ে উত্তর যাচাইও করতে পারেন।

  1. নির্মাণ ও প্রমাণ: ধরুন f একটি one-way function, যা দৈর্ঘ্য রক্ষা করে (|f(x)| = |x|)। একটি নতুন ফাংশন নকশা করুন: g(x1, x2) = (f(x1), x2), যেখানে |x1| = |x2|. প্রমাণ করুন g-ও one-way, যদিও তার input-এর অর্ধেক সরাসরি আউটপুটে দেখা যায়। এ থেকে OWF সম্পর্কে কী শিক্ষা পান?

    g polynomial সময়ে হিসাবযোগ্য, কারণ f তাই। ধরুন একটি PPT A g-কে অ-negligible সম্ভাবনা δ(n)-এ উল্টায় (input দৈর্ঘ্য 2n). f-এর inverter B(1n, y): একটি random x2 ∈ {0,1}n বাছুন, A-কে (y, x2) দিন, উত্তর (x1′, x2′)-এর x1′ ফেরত দিন। y = f(x1) আর x2 random হলে A-এর input ঠিক g-এর random আউটপুটের বণ্টন, তাই A সম্ভাবনা δ(n)-এ এমন (x1′, x2′) দেয় যাতে g(x1′, x2′) = (y, x2), অর্থাৎ f(x1′) = y. তাই B-ও δ(n)-এ জেতে, যা f-এর one-way হওয়ার বিরোধী। ∎

    শিক্ষা: OWF মানে শুধু “পুরো input বের করা কঠিন”; input-এর অনেক তথ্য, এমনকি অর্ধেক বিট, ফাঁস হতে পারে। তাই encryption-এর জন্য OWF সরাসরি যথেষ্ট নয়, hardcore predicate আর PRG-এর মতো নির্মাণ লাগে (অংশ ৫)।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: P ≠ NP হলে one-way function আছে। প্রমাণ: f(φ, a) = (φ, φ(a)) নিন, যেখানে φ একটি 3CNF সূত্র আর a একটি assignment. f polynomial সময়ের। (φ, 1) থেকে preimage মানে φ-এর একটি satisfying assignment, যা 3SAT সমাধান। P ≠ NP বলে 3SAT-এর polynomial algorithm নেই, তাই f উল্টানো কঠিন। ∎” ভুলগুলো কোথায়?

    প্রথম ভুল: P ≠ NP শুধু বলে প্রতিটি algorithm কিছু সূত্রে ব্যর্থ। OWF-এর সংজ্ঞা চায় random (φ, a)-এর আউটপুটে প্রায় সবসময় ব্যর্থতা। Random φ আর random a থেকে আসা সূত্রগুলো সহজ হতে পারে; যেমন ছোট সূত্রে বা কম clause-এ satisfying assignment প্রচুর, আর সাধারণ algorithm দ্রুত একটি পায়। Worst-case থেকে average-case-এ লাফ প্রমাণ ছাড়া নেওয়া হয়েছে।

    দ্বিতীয় ভুল: আউটপুট (φ, 0)-এর ক্ষেত্রে preimage মানে শুধু একটি অ-satisfying assignment, যা random a প্রায়ই দেয়; তাই অর্ধেক বা তার বেশি ক্ষেত্রে inversion তুচ্ছ। তৃতীয়, polynomial algorithm নেই মানে deterministic algorithm নেই; সংজ্ঞায় PPT প্রতিপক্ষ, তাই দরকার NP ⊄ BPP-এর মতো শক্ত অনুমানও। “P ≠ NP ⇒ OWF” আজও একটি খোলা প্রশ্ন।

  3. হিসাব (trace): Toy RSA (অনিরাপদ খেলনা): p = 5, q = 11, e = 3. N, φ(N) আর d বের করুন। m = 9 encrypt করুন, তারপর decrypt করে মেলান। Trial division (2 থেকে শুরু) কয়টি ভাগে N factor করে?

    N = 55, φ = 4 · 10 = 40. gcd(3, 40) = 1. d = 3−1 mod 40 = 27, কারণ 3 · 27 = 81 = 2 · 40 + 1. Encryption: 93 = 729 = 13 · 55 + 14, তাই c = 14.

    Decryption: 1427 mod 55 = 9 (Python-এ pow(14, 27, 55) দিয়ে মেলানো)। Trial division 2, 3, 4-এ ভাগ যায় না, 5-এ যায়: ৪টি ভাগে 55 = 5 · 11, আর তা থেকে φ = 40 আর d = 27. খেলনা ভাঙতে এক মুহূর্তও লাগে না।

  4. পূর্বাভাস: বাজারঘর প্রতিটি অর্ডারের জন্য একটি 32-bit hash ছাপ রাখে। মোটামুটি কত অর্ডারে দুটি আলাদা অর্ডারের ছাপ মিলে যাওয়ার সম্ভাবনা অর্ধেক হবে? 64-bit হলে? birthday_sha.py-র n = 32 লাইনের ফলের সঙ্গে আপনার উত্তর কতটা মেলে?

    অর্ধেক সম্ভাবনা আসে q ≈ √(2 ln 2) · 2ℓ/2 ≈ 1.1774 · 2ℓ/2-এ। ℓ = 32: 1.1774 · 65536 ≈ 77,163টি অর্ডার। ℓ = 64: 1.1774 · 232 ≈ 5.06 × 109.

    ব্লকের n = 32 লাইনে প্রথম collision এসেছে 97,655-এ, অর্থাৎ 1.49 · 216. এটি একটি run, আর প্রথম collision-এর প্রত্যাশা 1.25 · 216 ≈ 82,000; মাঝারি পরিসরের মধ্যেই। শিক্ষা: কয়েক লাখ অর্ডারের দোকানে 32-bit ছাপ অনন্য পরিচয় হিসেবে অচল; ছাপ যদি নিরাপত্তার কাজে লাগে, 256-bit hash লাগে।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রম“One-way function থাকলে P ≠ NP” প্রমাণের (contrapositive) ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ধরে নেওয়া হয় P = NP, আর f যেকোনো polynomial সময়ের ফাংশন
  2. PREf = {⟨y, u, 1n⟩ : u দিয়ে শুরু কোনো x-এ f(x) = y} সংজ্ঞায়িত হয়
  3. Certificate x দিয়ে PREf ∈ NP, তাই P = NP থেকে PREf ∈ P
  4. prefix u-কে একটি একটি বিট বাড়িয়ে, n টি প্রশ্নে একটি preimage পাওয়া যায়
  5. প্রতিটি y = f(x)-এ polynomial সময়ে inversion, তাই f one-way নয়

Security parameter n-এর কোন ফাংশনটি negligible?

  • 1/n100
  • 2−√n
  • 1/(n log n)
  • 0.001, সব n-এ

One-way function আর P বনাম NP-এর সম্পর্ক নিয়ে কোনটি জানা সত্য?

  • P ≠ NP হলে one-way function অবশ্যই আছে
  • One-way function থাকলে P = NP
  • One-way function থাকলে P ≠ NP, আর উল্টো দিকটি অজানা
  • RSA থেকে one-way function-এর অস্তিত্ব প্রমাণিত

One-way function-এর সংজ্ঞায় প্রতিপক্ষ A কখন “জেতে”, যখন random x-এর y = f(x) দেওয়া থাকে?

  • A এমন যেকোনো x′ দিলে, যাতে f(x′) = y
  • শুধু আসল x দিলে
  • x-এর প্রথম বিট ঠিক অনুমান করলে
  • কোনো একটি বিশেষ x-এ সবসময় সফল হলে

Toy RSA (অনিরাপদ খেলনা): p = 5, q = 11, e = 3. Trapdoor d কত?

  • 13
  • 27
  • 37
  • 3

একটি hash-এর আউটপুট 40 বিট, আর আউটপুটগুলো প্রায় সমানভাবে ছড়ানো। Generic birthday আক্রমণে মোটামুটি কতগুলো input hash করলে collision-এর ভালো সম্ভাবনা?

  • প্রায় 220
  • প্রায় 240
  • প্রায় 239
  • প্রায় 40

Learning With Errors (LWE) আর post-quantum cryptography সম্পর্কে কোনটি সঠিক?

  • ভুলসহ সমীকরণও Gaussian elimination-এ polynomial সময়ে সমাধান হয়
  • Shor-এর algorithm LWE-ও polynomial সময়ে ভাঙে
  • LWE NP-complete বলে প্রমাণিত, তাই নিরাপত্তা নিশ্চিত
  • Random LWE instance-এর কঠিনতা worst-case lattice সমস্যার কঠিনতা থেকে আসে, তবে সেটিও একটি অনুমান

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Computational security: PPT প্রতিপক্ষ, negligible সাফল্য। Negligible মানে প্রতিটি n−c-এর চেয়ে দ্রুত শূন্যের দিকে; দুটি মিলে polynomial পুনরাবৃত্তিতে বন্ধ।
  2. OWF: সহজে হিসাব, random x-এর f(x) থেকে যেকোনো preimage খোঁজা গড়ে কঠিন। প্রার্থী factoring, discrete log, subset sum, LWE; কোনোটিই প্রমাণিত নয়।
  3. OWF ⇒ P ≠ NP (prefix প্রশ্নে বিট ধরে inversion). উল্টো দিক অজানা: P ≠ NP worst-case, cryptography-র দরকার সমাধানসহ বানানো average-case কঠিন instance.
  4. OWF ⇔ PRG (HILL); PRG থেকে symmetric encryption. Public-key-এর জন্য trapdoor লাগে (RSA-র d); textbook RSA deterministic আর খেলনা সংখ্যায় তুচ্ছভাবে ভাঙে। ℓ-বিট hash-এ collision ≈ 2ℓ/2 চেষ্টায়।
  5. Impagliazzo-র পাঁচ জগৎ: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania; কোনটি সত্য অজানা। Shor RSA আর DH ভাঙে; LWE-র average-case কঠিনতা worst-case lattice থেকে, তবু অনুমান।

পরের পর্বে: নতুন মডিউল, প্রয়োগের দিক। একটি system কি কখনো ভুল অবস্থায় যায় না? সসীম ও অসীম আচরণ যাচাইয়ের automaton আর temporal logic: Model checking, Büchi automaton আর LTL (পর্ব ৭৭)।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান