Finite field আর elliptic curve-এর পরিচয়

১ · বড় সংখ্যার বোঝা — বাজারঘরের নতুন প্রশ্ন

এই মডিউলে আমরা দেখেছি, সংখ্যাতত্ত্ব কীভাবে গোপনীয়তার কাজে লাগে। পর্ব ২৭ “Classical cipher — shift, affine আর frequency analysis”-এ পুরোনো cipher আর তাদের দুর্বলতা, পর্ব ২৮ “RSA-এর গণিত — key, encryption আর কেন কাজ করে”-এ factoring-এর কঠিনতার ওপর দাঁড়ানো RSA, আর পর্ব ২৯ “Discrete logarithm আর Diffie–Hellman key exchange”-এ mod p-তে ঘাতের উল্টো সমস্যা। তিনটির পেছনেই মডিউল ৪-এর যন্ত্রপাতি: modular inverse (পর্ব ২৩), Euler আর primitive root (পর্ব ২৪), আর factoring-এর কঠিনতা (পর্ব ২৫).

বাজারঘরের দুই কর্মী, রিনা (ঢাকা অফিস) আর সুমন (চট্টগ্রাম গুদাম), খোলা ইন্টারনেটে একটি গোপন key-তে একমত হতে চান। পর্ব ২৯-এর Diffie–Hellman এ কাজ করে, কিন্তু নিরাপদ থাকতে mod p-এর p-কে কয়েক হাজার bit লম্বা হতে হয়। মোবাইল ফোনে, ছোট সেন্সরে বা প্রতি সেকেন্ডে হাজার হাজার সংযোগ সামলানো সার্ভারে এই আকার একটি বোঝা। প্রশ্নটি তাই এমন: এমন কোনো “সংখ্যার জগৎ” কি আছে, যেখানে ঘাতের উল্টো সমস্যা আরও কঠিন, ফলে ছোট সংখ্যাতেই একই নিরাপত্তা মেলে?

উত্তর আসে দুটি ধারণা থেকে, যা এই পর্বের বিষয়। প্রথমটি finite field: সসীম একটি সেট, যেখানে সাধারণ সংখ্যার মতো যোগ, বিয়োগ, গুণ, ভাগ সব চলে। দ্বিতীয়টি elliptic curve: একটি finite field-এর ওপর আঁকা একটি বক্ররেখার বিন্দুগুলো, যাদের “যোগ” করা যায়। প্রথমটি দিয়ে আজকের প্রায় সব symmetric encryption-এর ভেতরের byte-হিসাব চলে (AES), আর দ্বিতীয়টি দিয়ে বেশিরভাগ HTTPS সংযোগের key exchange. এই পর্ব একটি পরিচয়; ring আর field-এর পূর্ণ বীজগণিত আসবে পর্ব ৭১ “Ring আর field — modular ring, polynomial আর GF(2ⁿ)”-এ, আর group-এর তত্ত্ব পর্ব ৭০ “Group — symmetry, cyclic group আর Lagrange-এর উপপাদ্য”-এ।

২ · Field — যেখানে চার নিয়মই চলে

বাজারের হিসাবে আমরা যোগ, বিয়োগ, গুণ, ভাগ নির্ভাবনায় করি, কারণ মূলদ (ℚ) বা বাস্তব (ℝ) সংখ্যায় এই চার কাজ “স্বাভাবিক” নিয়ম মানে। পূর্ণসংখ্যা ℤ-এ কিন্তু ভাগ সবসময় চলে না: 1 ÷ 2 পূর্ণসংখ্যা নয়। এই “নিয়মগুলো”কে সংক্ষেপে লিখলে একটি field-এর সংজ্ঞা পাওয়া যায়।

ℚ, ℝ আর ℂ field; ℤ নয়, কারণ 2-এর গুণের inverse ℤ-এ নেই। কম্পিউটারের জন্য আকর্ষণীয় হলো সসীম field, কারণ সেখানে প্রতিটি উপাদান নির্দিষ্ট কয়েকটি bit-এ ধরে, কোনো rounding নেই, আর হিসাব নির্ভুল। প্রথম প্রার্থী পর্ব ২২-এর ℤ_n = {0, 1, …, n − 1}, যেখানে প্রতিটি যোগ আর গুণের পরে mod n নেওয়া হয়। যোগের নিয়মগুলো সবসময় খাটে; প্রশ্ন শুধু গুণের inverse নিয়ে।

প্রমাণ: দুই দিক আলাদা করে।

1. (⇐) n = p মৌলিক, আর a ∈ {1, …, p − 1}. p-এর একমাত্র ধনাত্মক ভাজক 1 আর p, আর p ∤ a, তাই gcd(a, p) = 1. — মৌলিকের সংজ্ঞা
2. Bézout-এর অভেদে (পর্ব ২১) এমন পূর্ণসংখ্যা s, t আছে যাতে sa + tp = 1. mod p নিলে sa ≡ 1, তাই s mod p হলো a⁻¹. — Bézout
3. বাকি সব নিয়ম (associative, commutative, বণ্টন) ℤ-এ সত্য আর mod p নিলেও টিকে থাকে, কারণ congruence যোগ আর গুণ মানে (পর্ব ২২). তাই ℤ_p একটি field. — congruence-এর ধর্ম
4. (⇒) n মৌলিক নয়, তাই n = rs, যেখানে 1 < r, s < n. তখন r ≢ 0, s ≢ 0, কিন্তু r · s ≡ 0 (mod n). — যৌগিকের সংজ্ঞা
5. ধরা যাক r-এর inverse u আছে। তাহলে s ≡ (u · r) · s = u · (r · s) ≡ u · 0 = 0 (mod n), যা s ≢ 0-এর বিরোধী। তাই r-এর inverse নেই, আর ℤ_n field নয়। ∎ — associativity, contradiction

ধাপ ৪-এর r আর s-এর মতো উপাদানকে zero divisor বলে: দুটি অশূন্য সংখ্যার গুণফল শূন্য। ℤ₁₅-এ 3 · 5 ≡ 0 আর 6 · 10 = 60 ≡ 0. ধাপ ৫ আসলে একটি সাধারণ সত্য দেখায়: কোনো field-এ zero divisor থাকতে পারে না (অনুশীলন ১). বাস্তবে এর মানে, ℤ₁₅-এ “3x ≡ 1”-এর মতো সমীকরণের কোনো সমাধান নেই, আর পর্ব ২৩-এর linear congruence তখন হয় একাধিক সমাধান দেয়, নয়তো কোনোটিই না।

তাহলে কি finite field মানেই ℤ_p? না। নিচের উপপাদ্যটি পুরো ছবি দেয়; এর প্রমাণ এখানে বাদ, পর্ব ৭১-এর বিষয়।

GF মানে “Galois field”, ফরাসি তরুণ গণিতবিদ Évariste Galois-এর নামে, যিনি ১৮৩০ সালের দিকে এমন জগতের ধারণা দেন আর ২০ বছর বয়সে মারা যান (১৮৩২)। সব finite field যে এই তালিকাতেই পড়ে, তার পূর্ণ প্রমাণ সাধারণত E. H. Moore-এর ১৮৯৩ সালের কাজের সঙ্গে যুক্ত করা হয়। ফলে 6, 10 বা 12টি উপাদানের কোনো field নেই, কিন্তু 4, 8, 9, 256টির আছে। n = 1 হলে GF(p) = ℤ_p; কিন্তু GF(4) ≠ ℤ₄, কারণ ℤ₄-এ 2 · 2 ≡ 0. GF(4) বানাতে নতুন একটি কৌশল লাগে, যা পরের অংশে।

৩ · GF(2ⁿ) — bit-এর polynomial আর AES-এর byte

কম্পিউটারের স্বাভাবিক একক byte, অর্থাৎ 8টি bit, 256টি মান। 256 = 2⁸, তাই উপপাদ্য ২.৩ অনুযায়ী 256টি উপাদানের একটি field আছে। কিন্তু ℤ₂₅₆ সেই field নয় (2 · 128 ≡ 0). কৌশলটি হলো byte-কে সংখ্যা না ভেবে polynomial ভাবা।

ধাপ ১: GF(2)-এর ওপর polynomial

GF(2) = ℤ₂ = {0, 1}, যেখানে 1 + 1 = 0. একটি byte b₇b₆…b₀-কে পড়া হয় b₇x⁷ + ⋯ + b₁x + b₀ হিসেবে। যেমন hex {57} = 0101 0111 = x⁶ + x⁴ + x² + x + 1. দুটি polynomial যোগ করতে একই ঘাতের সহগ mod 2-এ যোগ হয়, অর্থাৎ bit-ধরে XOR: {57} + {83} = 0101 0111 ⊕ 1000 0011 = {d4}. কোনো “হাতে রাখা” (carry) নেই। লক্ষ করুন, এখানে a + a = 0, তাই বিয়োগ আর যোগ একই কাজ।

ধাপ ২: গুণ, তারপর একটি irreducible polynomial দিয়ে ভাগশেষ

দুটি 7 ঘাতের polynomial গুণ করলে 14 পর্যন্ত ঘাত আসতে পারে, যা আর এক byte-এ ধরে না। সমাধান পূর্ণসংখ্যার mod p-এর মতো: একটি নির্দিষ্ট 8 ঘাতের polynomial m(x) দিয়ে ভাগ করে ভাগশেষ রাখা। কিন্তু m(x) যেকোনো হলে চলবে না। ℤ_n-এ n-কে মৌলিক হতে হয়েছিল; এখানে m(x)-কে হতে হবে irreducible: GF(2)-এর ওপর তাকে দুটি ছোট ঘাতের (ঘাত ≥ 1) polynomial-এর গুণফল হিসেবে লেখা যায় না। কারণটি হুবহু উপপাদ্য ২.২-এর: m = f · g হলে f আর g zero divisor হয়ে যায়, আর m irreducible হলে Bézout-এর polynomial রূপ (polynomial-এর Euclid) প্রতিটি অশূন্য উপাদানের inverse দেয়।

সবচেয়ে ছোট উদাহরণ GF(4): m(x) = x² + x + 1 (GF(2)-এ এর root নেই, আর ঘাত 2 বলে root না থাকলেই irreducible). উপাদান 0, 1, x, x + 1, আর x · x = x² ≡ x + 1, x · (x + 1) = x² + x ≡ 1. অর্থাৎ x আর x + 1 পরস্পরের inverse: চারটি উপাদানের একটি সত্যিকারের field, যা ℤ₄ থেকে আলাদা।

AES (Advanced Encryption Standard) হলো বেলজিয়ামের Joan Daemen আর Vincent Rijmen-এর Rijndael নকশা, যা মার্কিন NIST ২০০১ সালে FIPS 197 হিসেবে প্রকাশ করে। মানপত্রটিতে উদাহরণ হিসেবে {57} · {83} = {c1} দেওয়া আছে। নিচের stepper সেই গুণটি হাতে করে, যেমন পরীক্ষার খাতায় করবেন।

1{57} = x⁶+x⁴+x²+x+12{83} = x⁷+x+1357·x⁷ ⊕ 57·x ⊕ 57·14= x¹³+x¹¹+x⁹+x⁸+x⁶5  +x⁵+x⁴+x³+16⊕ x⁵·m(x)7⊕ x³·m(x) → x⁷+x⁶+1

এখানে “ভাগশেষ নেওয়া” মানে বারবার m(x)-এর উপযুক্ত x-ঘাতের গুণিতক XOR করে সর্বোচ্চ পদটি মুছে ফেলা, ঠিক পর্ব ২৬-এর CRC-এর লম্বা ভাগের মতো। কম্পিউটারে আরও সহজ একটি পথ আছে: b-এর bit ধরে ধরে a-কে বারবার x দিয়ে গুণ করা (এক bit বাঁয়ে সরানো), আর ঘাত 8 হলেই সঙ্গে সঙ্গে {11B} XOR করা। নিচের ব্লক সেভাবে গুণ করে, তারপর তিনটি দাবি পরীক্ষা করে: প্রতিটি অশূন্য byte-এর ঠিক একটি inverse আছে, AES-এর m(x)-এর কোনো ছোট উৎপাদক নেই, আর irreducible নয় এমন x⁸ + 1 নিলে zero divisor দেখা দেয়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

AES_MOD = 0x11B                       # x^8 + x^4 + x^3 + x + 1

def gf_mul(a, b, mod=AES_MOD):        # multiply two bytes in GF(2^8)
    r = 0
    while b:
        if b & 1:
            r ^= a                    # add (XOR) this partial product
        a <<= 1; b >>= 1
        if a & 0x100:
            a ^= mod                  # reduce as soon as degree 8 appears
    return r

print("57 * 83 =", hex(gf_mul(0x57, 0x83)), "  57 * 13 =", hex(gf_mul(0x57, 0x13)))
print("57 + 83 =", hex(0x57 ^ 0x83), "(addition is XOR)")

inv = {a: [b for b in range(1, 256) if gf_mul(a, b) == 1] for a in range(1, 256)}
print("every nonzero byte has exactly one inverse:",
      all(len(v) == 1 for v in inv.values()), "  inverse of 53:", hex(inv[0x53][0]))

def poly_mod(f, g):                   # remainder of f / g, coefficients mod 2
    while f.bit_length() >= g.bit_length():
        f ^= g << (f.bit_length() - g.bit_length())
    return f
print("AES modulus has a factor of degree 1..4:",
      any(poly_mod(AES_MOD, g) == 0 for g in range(2, 32)))

bad = 0x101                           # x^8 + 1 = (x + 1)^8 is reducible
zd = [(a, b) for a in range(1, 256) for b in range(a, 256) if gf_mul(a, b, bad) == 0]
print("mod x^8 + 1: zero-divisor pairs", len(zd), " e.g.", [hex(t) for t in zd[0]])

def is_field(n):                      # Z_n: does every nonzero a have an inverse?
    return all(any(a * b % n == 1 for b in range(1, n)) for a in range(1, n))
print("n < 30 where Z_n is a field:", [n for n in range(2, 30) if is_field(n)])

57 * 83 = 0xc1   57 * 13 = 0xfe
57 + 83 = 0xd4 (addition is XOR)
every nonzero byte has exactly one inverse: True   inverse of 53: 0xca
AES modulus has a factor of degree 1..4: False
mod x^8 + 1: zero-divisor pairs 392  e.g. ['0x3', '0xff']
n < 30 where Z_n is a field: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

AES-এর S-box, অর্থাৎ যে টেবিল প্রতিটি byte বদলে দেয়, এই field-এর inverse (x ↦ x⁻¹, আর 0 ↦ 0) নিয়ে তার ওপর একটি নির্দিষ্ট affine রূপান্তর চালিয়ে বানানো। inverse ফাংশনটি অত্যন্ত “অ-linear”, আর এই গুণই AES-কে নির্দিষ্ট কিছু গাণিতিক আক্রমণ থেকে রক্ষা করে বলে নকশাকারীরা যুক্তি দেন। AES কীভাবে ব্যবহার করতে হয় (mode, nonce, authenticated encryption), তা Cybersecurity কোর্সের পর্ব ০৮-এর বিষয়।

৪ · বাস্তব সংখ্যায় elliptic curve — chord আর tangent

নাম শুনে উপবৃত্ত (ellipse) মনে হলেও elliptic curve উপবৃত্ত নয়; নামটি এসেছে উপবৃত্তের পরিধি মাপার একটি পুরোনো integral থেকে। আমাদের জন্য একটি elliptic curve হলো এমন সমীকরণের সব বিন্দু:

y² = x³ + ax + b, যেখানে 4a³ + 27b² ≠ 0

একে Weierstrass রূপ বলে। দ্বিতীয় শর্তটি বলে, ডান পাশের ঘন polynomial-এর কোনো পুনরাবৃত্ত root নেই, ফলে curve-এ কোনো সূচালো কোণ বা নিজেকে কাটা বিন্দু নেই, আর প্রতিটি বিন্দুতে একটি নির্দিষ্ট স্পর্শক (tangent) আছে। নিচের ছবিতে a = −1, b = 1: 4(−1)³ + 27 = 23 ≠ 0. y-এর জায়গায় −y বসালে সমীকরণ বদলায় না, তাই curve x-অক্ষের সাপেক্ষে প্রতিসম।

যোগের নিয়ম

দুটি বিন্দু P আর Q দেওয়া থাকলে তাদের মধ্য দিয়ে একটি সরলরেখা (chord) টানুন। ঘন সমীকরণের রেখা curve-কে সাধারণত ঠিক তিনটি বিন্দুতে কাটে; তৃতীয়টিকে x-অক্ষে প্রতিফলন করলে যা পাওয়া যায়, তাকেই বলা হয় P + Q. P = Q হলে chord-এর বদলে P-বিন্দুতে স্পর্শক (tangent) টানা হয়, তাই একে “chord-and-tangent” নিয়ম বলে। আর P ও Q একই খাড়া রেখায় হলে (x সমান, y বিপরীত) রেখাটি আর কোথাও curve কাটে না। তখন তৃতীয় বিন্দু হিসেবে একটি বিশেষ বিন্দু যোগ করা হয়: অসীমের বিন্দু O, যাকে কল্পনা করা যায় সব খাড়া রেখার “শেষে”, ওপরে-নিচে অসীমে। O-ই এই যোগের শূন্য: P + O = P, আর (x, y)-এর বিপরীত −(x, y) = (x, −y).

প্রমাণ (P ≠ Q, x₁ ≠ x₂; স্পর্শকের ক্ষেত্র একইভাবে, শুধু λ আসে implicit derivative 2y·y′ = 3x² + a থেকে):

1. P আর Q-এর মধ্য দিয়ে রেখা y = λ(x − x₁) + y₁, যেখানে λ দুই বিন্দুর ঢাল। — সরলরেখার সমীকরণ
2. এটি curve-এ বসালে (λ(x − x₁) + y₁)² = x³ + ax + b, অর্থাৎ x³ − λ²x² + (নিচের ঘাতের পদ) = 0. ছেদবিন্দুর x-গুলো এই ঘন সমীকরণের root. — বদলে বসানো
3. x₁ আর x₂ দুটি root, তাই তৃতীয় root x₃ও আছে, আর monic ঘন সমীকরণে root-এর যোগফল = −(x²-এর সহগ) = λ². তাই x₁ + x₂ + x₃ = λ². — root আর সহগের সম্পর্ক (Vieta)
4. তৃতীয় ছেদবিন্দু রেখার ওপর: (x₃, λ(x₃ − x₁) + y₁). এর প্রতিফলনের y = −λ(x₃ − x₁) − y₁ = λ(x₁ − x₃) − y₁. ∎ — প্রতিফলন মানে y ↦ −y

ছবির উদাহরণে λ = 0, তাই x₃ = 0 − (−1) − 0 = 1 আর y₃ = 0 − 1 = −1: ঠিক (1, −1). লক্ষ করুন সূত্রে শুধু যোগ, বিয়োগ, গুণ আর ভাগ আছে, কোনো বর্গমূল বা দশমিক নেই। তাই একই সূত্র যেকোনো field-এ চলে, যেখানে 2 ≠ 0 আর 3 ≠ 0 (অর্থাৎ field-এর উপাদান-সংখ্যা 2 বা 3-এর ঘাত নয়; GF(2ⁿ)-এ curve-এর সমীকরণ একটু আলাদা রূপ নেয়)। এটিই পরের অংশের চাবি।

প্রথম চারটি সূত্র থেকে সরাসরি আসে: Q আর P অদলবদল করলে λ আর x₃ বদলায় না। কঠিন অংশ associativity; সূত্র দিয়ে সরাসরি যাচাই করা যায়, কিন্তু হাতে কয়েক পাতার বীজগণিত লাগে, আর সুন্দর প্রমাণগুলো projective geometry বা algebraic geometry ব্যবহার করে। তাই এখানে প্রমাণ বাদ; বদলে পরের অংশে কম্পিউটারে হাজার হাজার ক্ষেত্রে পরীক্ষা করা হবে।

৫ · GF(p)-এর ওপর curve — বিন্দুর তালিকা আর group

এবার x আর y বাস্তব সংখ্যা নয়, ℤ_p-এর উপাদান, আর সব হিসাব mod p. “ভাগ” মানে modular inverse দিয়ে গুণ, যা উপপাদ্য ২.২ নিশ্চিত করে। ছবিটি আর বক্ররেখা থাকে না, একটি ছড়ানো বিন্দুর ঝাঁক হয়ে যায়, কিন্তু উপপাদ্য ৪.১-এর সূত্র হুবহু একই, আর group law-ও টিকে থাকে। আমাদের খেলনা curve:

E: y² ≡ x³ + 2x + 2 (mod 17)

4 · 8 + 27 · 4 = 140 ≡ 4 ≢ 0 (mod 17), তাই curve মসৃণ। x = 0 থেকে 16 প্রতিটির জন্য x³ + 2x + 2 mod 17 একটি বর্গ কি না দেখে বিন্দুগুলো গোনা যায়: মোট 18টি বিন্দু, আর O মিলিয়ে N = 19. G = (5, 1) নিয়ে বারবার যোগ করলে পাওয়া যায় 2G = (6, 3), 3G = (10, 6), 4G = (3, 1), …, 18G = (5, 16) = −G, আর 19G = O. 19 মৌলিক, তাই G থেকে সব বিন্দু আসে: group-টি cyclic, আর G একটি generator (পর্ব ২৪-এর primitive root-এর মতো)। নিচের stepper এই curve-এ 3G আর 4G যোগ করে।

1A = (10, 6), B = (3, 1)2λ = (1 − 6)/(3 − 10)3  = 12 · 10⁻¹ = 12 · 12 ≡ 84x₃ = 8² − 10 − 3 = 51 ≡ 05y₃ = 8(10 − 0) − 6 = 74 ≡ 66A + B = (0, 6) = 7G

বিন্দুর সংখ্যা N কত বড় হতে পারে? প্রতিটি x-এর জন্য y বড়জোর দুটি, তাই N ≤ 2p + 1. মোটামুটি অর্ধেক অশূন্য ভাগশেষ বর্গ (পর্ব ২৪-এর Euler-এর criterion), তাই গড়ে প্রতিটি x একটি বিন্দু দেয় আর N ≈ p + 1 আশা করা যায়। আশ্চর্যের কথা, বিচ্যুতিও খুব ছোট।

Helmut Hasse ১৯৩০-এর দশকে এটি প্রমাণ করেন; প্রমাণ এই কোর্সের বাইরে। আমাদের curve-এ p + 1 = 18, 2√17 ≈ 8.25, আর N = 19 সীমার ভেতরে। বাস্তবে N হুবহু জানা জরুরি, কারণ নিরাপত্তার জন্য N-এর একটি বড় মৌলিক উৎপাদক থাকতে হয় (পর্ব ২৯-এর Pohlig–Hellman-এর যুক্তি)। বড় p-এ N গোনার জন্য Schoof-এর ১৯৮৫ সালের polynomial-সময়ের algorithm আর তার উন্নত রূপ ব্যবহৃত হয়।

এখন group law-কে কম্পিউটারে পরীক্ষা করা যাক। নিচের ব্লক আরেকটি curve, y² = x³ + 2x + 3 (mod 97)-এর সব বিন্দু তালিকা করে, Hasse-এর সীমা মেলায়, আর সব জোড়ায় closure ও commutativity, প্রতিটি বিন্দুর বিপরীত, আর ৩,০০০টি এলোমেলো তিন-বিন্দুতে associativity পরীক্ষা করে। pow(d, -1, p) হলো Python-এর modular inverse.

import random
random.seed(30)
p, a, b = 97, 2, 3                    # y^2 = x^3 + 2x + 3 over GF(97)
O = None                              # the point at infinity

def add(P, Q):
    if P is O: return Q
    if Q is O: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O                      # P + (-P) = O: a vertical line
    if P == Q:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p   # tangent slope
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p          # chord slope
    x3 = (lam * lam - x1 - x2) % p
    return (x3, (lam * (x1 - x3) - y1) % p)

print("4a^3 + 27b^2 mod p =", (4 * a**3 + 27 * b**2) % p, "(nonzero: a smooth curve)")
pts = [(x, y) for x in range(p) for y in range(p) if (y * y - x**3 - a * x - b) % p == 0]
E = pts + [O]
print("points:", len(pts), "+ O =", len(E), "  first five:", pts[:5])
print("Hasse: |N - (p + 1)| =", abs(len(E) - (p + 1)),
      "<= 2*sqrt(p) =", round(2 * p ** 0.5, 2))
on = set(E)
print("closure, all", len(E) ** 2, "pairs:", all(add(P, Q) in on for P in E for Q in E))
print("commutative:", all(add(P, Q) == add(Q, P) for P in E for Q in E))
print("every point has an inverse:", all(add(P, (P[0], -P[1] % p)) is O for P in pts))
trip = [random.sample(E, 3) for _ in range(3000)]
print("associative on 3000 random triples:",
      all(add(add(P, Q), R) == add(P, add(Q, R)) for P, Q, R in trip))

4a^3 + 27b^2 mod p = 81 (nonzero: a smooth curve)
points: 99 + O = 100   first five: [(0, 10), (0, 87), (1, 43), (1, 54), (3, 6)]
Hasse: |N - (p + 1)| = 2 <= 2*sqrt(p) = 19.7
closure, all 10000 pairs: True
commutative: True
every point has an inverse: True
associative on 3000 random triples: True

৬ · Scalar multiplication — double-and-add

পূর্ণসংখ্যা k ≥ 1 আর বিন্দু P-এর জন্য kP = P + P + ⋯ + P (k বার), আর 0P = O. একে scalar multiplication বলে। mod p-তে g^k-এর মতো এখানেও k কয়েকশো bit লম্বা হতে পারে, তাই k − 1 বার যোগ অসম্ভব। পর্ব ২২-এর বারবার বর্গ করার কৌশলটি হুবহু এখানে খাটে, শুধু “বর্গ” হয় “দ্বিগুণ” আর “গুণ” হয় “যোগ”।

সঠিকতার প্রমাণ (loop invariant, পর্ব ১৩-এর পদ্ধতিতে):

1. k-এর প্রথম j-টি bit দিয়ে তৈরি সংখ্যাকে k_j বলি (k₁ = 1, আর k_t+1 = k). দাবি: প্রতিটি পুনরাবৃত্তির শুরুতে R = k_jP. শুরুতে j = 1, R = P = 1 · P ✓. — ভিত্তি
2. পরের bit b যোগ করলে k_j+1 = 2k_j + b, কারণ binary-তে একটি অঙ্ক যোগ মানে আগের মান দ্বিগুণ করে নতুন অঙ্ক যোগ। — binary রূপ
3. loop R-কে করে 2(k_jP) + bP = (2k_j + b)P = k_j+1P. এখানে group-এর associativity লাগে, যাতে k_jP-কে দুবার যোগ করা আর 2k_j বার P যোগ করা একই হয়। — উপপাদ্য ৪.২
4. শেষ bit-এর পরে R = k_t+1P = kP. ধাপের সংখ্যা: t = ⌊log₂ k⌋টি দ্বিগুণ, আর (k-এর binary-তে 1-এর সংখ্যা − 1)টি যোগ, মোট ≤ 2 log₂ k. ∎ — গণনা

নিচের stepper আমাদের mod 17 curve-এ G = (5, 1)-এর জন্য 13G বের করে। 13 = 1101₂, তাই ধাপগুলো: 1 → 3 → 6 → 13 (bit ধরে k_j: 1, 11, 110, 1101).

113 = 1101₂ ; R = G = (5, 1)2bit 1: R = 2R = (6, 3)3       R = R + G = (10, 6)4bit 0: R = 2R = (16, 13)5bit 1: R = 2R = (0, 11)6       R = R + G = (16, 4)

৭ · ECDLP আর ECDH — খোলা পথে একটি গোপন বিন্দু

Double-and-add দেখায়, k আর P জানা থাকলে Q = kP বের করা দ্রুত। উল্টোটা?

এটি পর্ব ২৯-এর discrete logarithm-এরই রূপ, শুধু “ঘাত” এখানে “গুণিতক”। সহজতম আক্রমণ G, 2G, 3G, … একে একে দেখা, যাতে গড়ে n/2 ধাপ লাগে। পর্ব ২৯-এর baby-step giant-step বা Pollard-এর rho পদ্ধতি এটিকে প্রায় √n ধাপে নামায়। ভালোভাবে বাছা curve-এ এর চেয়ে মূলগতভাবে দ্রুত কোনো সাধারণ পদ্ধতি জানা নেই; কিন্তু এটি একটি বিশ্বাস, প্রমাণ নয়। ECDLP কঠিন, এমন কোনো গাণিতিক প্রমাণ নেই।

ECDH: রিনা আর সুমনের key

পর্ব ২৯-এর Diffie–Hellman-এর হুবহু অনুবাদ হলো ECDH:

1. সবাই জানে: curve, মৌলিক p, একটি বিন্দু G আর তার মৌলিক order n.
2. রিনা গোপনে a ∈ {2, …, n − 1} বাছেন, আর খোলা পথে পাঠান A = aG. সুমন গোপনে b বাছেন, পাঠান B = bG.
3. রিনা হিসাব করেন aB, সুমন হিসাব করেন bA.

প্রমাণ: (১) aB = a(bG). (২) a(bG) মানে bG-কে a বার যোগ, অর্থাৎ G-কে ab বার যোগ (associativity, উপপাদ্য ৪.২), তাই a(bG) = (ab)G. (৩) একইভাবে bA = b(aG) = (ba)G, আর ab = ba. ∎

খোলা পথে শোনা একজন দেখেন G, A আর B. তাঁকে (ab)G বের করতে হবে, যা ECDLP সমাধান করলে সম্ভব; এর চেয়ে সহজ পথ জানা নেই বলে বিশ্বাস করা হয়। তবে পর্ব ২৯-এর সতর্কবাণী এখানেও খাটে: মাঝখানে বসে কেউ নিজের বিন্দু পাঠালে (man-in-the-middle) রিনা টেরই পাবেন না, যদি না পাঠানো বিন্দুগুলো signature বা certificate দিয়ে প্রমাণিত হয়। গণিত শুধু শোনা ঠেকায়; পরিচয় যাচাই আলাদা কাজ। বাস্তবে ভাগ করা বিন্দুটিও সরাসরি key হিসেবে ব্যবহৃত হয় না, একটি key derivation function দিয়ে key বানানো হয়।

নিচের ব্লক আগে stepper-এর 13G আর 19G = O মেলায়, তারপর একটি খেলনা curve (p = 10007, N = 10091, একটি মৌলিক) নিয়ে রিনা আর সুমনের ECDH চালায়।

import random
random.seed(2026)
O = None
def add(P, Q):                        # group law; reads the curve p, a below
    if P is O: return Q
    if Q is O: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0: return O
    if P == Q: lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:      lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (lam * lam - x1 - x2) % p
    return (x3, (lam * (x1 - x3) - y1) % p)

def mul(k, P):                        # double-and-add, bits of k from the left
    R, ops = P, 0                     # the leading bit 1 gives R = P
    for bit in bin(k)[3:]:
        R = add(R, R); ops += 1       # double
        if bit == "1":
            R = add(R, P); ops += 1   # add
    return R, ops
p, a = 17, 2                          # tiny curve y^2 = x^3 + 2x + 2 (mod 17)
print("13G on the mod-17 curve:", mul(13, (5, 1)), "  19G:", mul(19, (5, 1))[0])

p, a, b, N = 10007, 2, 30, 10091      # toy curve, N points (a prime)
x = 0
while True:                           # first point: square root, p % 4 == 3
    f = (x**3 + a * x + b) % p; y = pow(f, (p + 1) // 4, p)
    if y * y % p == f: G = (x, y); break
    x += 1
print("G =", G, "  N*G is O:", mul(N, G)[0] is O)
ka, kb = random.randrange(2, N), random.randrange(2, N)   # two secret keys
A, B = mul(ka, G)[0], mul(kb, G)[0]   # public values, sent in the open
print("public A =", A, "  public B =", B)
print("same shared point:", mul(ka, B)[0] == mul(kb, A)[0], mul(ka, B)[0])
print("double-and-add steps for ka:", mul(ka, G)[1], " instead of", ka - 1)

13G on the mod-17 curve: ((16, 4), 5)   19G: None
G = (1, 283)   N*G is O: True
public A = (923, 9604)   public B = (2191, 4645)
same shared point: True (4650, 8090)
double-and-add steps for ka: 15  instead of 1952

কেন খেলনা? কারণ এত ছোট group-এ ECDLP সহজ। নিচের ব্লক আগে ছোট সব p-এর প্রতিটি মসৃণ curve-এ Hasse-এর সীমা মেলায়, তারপর তিনটি নিজের বানানো খেলনা curve-এ G, 2G, 3G, … করে নিজেদের গোপন সংখ্যা খুঁজে বের করে, যাতে দেখা যায় ধাপের সংখ্যা N-এর সঙ্গে কীভাবে বাড়ে।

import random
random.seed(5)
O = None
def add(P, Q, a, p):
    if P is O: return Q
    if Q is O: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0: return O
    if P == Q: lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:      lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (lam * lam - x1 - x2) % p
    return (x3, (lam * (x1 - x3) - y1) % p)

def count(a, b, p):                   # 1 (for O) + points, via Euler's criterion
    n = 1
    for x in range(p):
        f = (x**3 + a * x + b) % p
        n += 1 if f == 0 else (2 if pow(f, (p - 1) // 2, p) == 1 else 0)
    return n

ok = all(abs(count(a, b, p) - (p + 1)) <= 2 * p ** 0.5
         for p in (5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
         for a in range(p) for b in range(p) if (4 * a**3 + 27 * b * b) % p)
print("Hasse bound holds on every smooth curve, p <= 37:", ok)

for p, b in ((1019, 18), (10007, 30), (100003, 5)):     # all with a = 2
    N, x = count(2, b, p), 0
    while pow((x**3 + 2 * x + b) % p, (p - 1) // 2, p) != 1: x += 1
    G = (x, pow((x**3 + 2 * x + b) % p, (p + 1) // 4, p))
    k = random.randrange(N // 2, N)                     # our own toy secret
    A = G
    for _ in range(k - 1): A = add(A, G, 2, p)
    R, t = G, 1
    while R != A: R, t = add(R, G, 2, p), t + 1         # try 1G, 2G, 3G, ...
    print(f"p = {p:>6}  N = {N:>6}  brute force: {t:>6} additions, found k: {t == k}")

Hasse bound holds on every smooth curve, p <= 37: True
p =   1019  N =   1013  brute force:    824 additions, found k: True
p =  10007  N =  10091  brute force:   7137 additions, found k: True
p = 100003  N =  99907  brute force:  98566 additions, found k: True

৮ · কেন ছোট key, মানসম্মত curve আর quantum-এর পরে

mod p-এর discrete log (পর্ব ২৯) আর factoring-এর (পর্ব ২৫) জন্য index calculus আর number field sieve-এর মতো sub-exponential পদ্ধতি আছে: এগুলো সংখ্যার “ভেতরের গঠন” (ছোট মৌলিকে ভেঙে ফেলা) কাজে লাগায়। Elliptic curve-এর বিন্দুর এমন কোনো সাধারণ “ছোট উৎপাদক” নেই, আর ভালো curve-এ সবচেয়ে ভালো জানা আক্রমণ এখনো সাধারণ √N পদ্ধতি। তাই একই নিরাপত্তায় ECC-এর key অনেক ছোট। NIST-এর SP 800-57 Part 1 (Rev. 5, ২০২০)-এর সমতুল্যতার তালিকার সরল রূপ:

“১২৮ bit নিরাপত্তা” মানে মোটামুটি 2¹²⁸টি মৌলিক ধাপের কাজ, আর 256 bit-এর curve-এ √N ≈ 2¹²⁸ ঠিক সেই হিসাব। এই তালিকা একটি নির্দিষ্ট সময়ের মূল্যায়ন; নতুন আক্রমণ বা নতুন নির্দেশিকা এলে সংখ্যা বদলায়, তাই বাস্তবে সবসময় বর্তমান মানপত্র দেখুন। প্রকাশিত রেকর্ডও এই ছবির সঙ্গে মেলে: ২০০৯ সালে একটি গবেষক দল PlayStation 3 যন্ত্রের গুচ্ছে ১১২ bit-এর একটি curve-এ ECDLP সমাধানের কথা প্রকাশ করে, যা 256 bit থেকে বহু দূরে।

মানসম্মত curve: কেন নিজে বানাবেন না

Curve বাছাই সূক্ষ্ম কাজ। কিছু curve-এ বিশেষ গঠনের কারণে ECDLP সহজ হয়ে যায়: যেমন N = p হলে (“anomalous” curve), বা কিছু “supersingular” curve-এ, যেখানে ১৯৯৩ সালের MOV আক্রমণ সমস্যাটিকে একটি finite field-এর সাধারণ discrete log-এ নামিয়ে আনে। তাই বাস্তবে নির্দিষ্ট, বহু বছর ধরে বিশ্লেষিত curve ব্যবহৃত হয়, শুধু নাম ধরে: NIST-এর P-256 (secp256r1 নামেও পরিচিত), আর Daniel J. Bernstein-এর Curve25519 (২০০৫–০৬), যার ওপর key exchange X25519 নামে RFC 7748 (২০১৬)-তে বর্ণিত। এগুলোর নিরাপত্তা নির্ভর করে শুধু curve-এর ওপর নয়, বাস্তবায়নের ওপরও: গোপন সংখ্যার random উৎস (পর্ব ২৬-এর CSPRNG), সময়-নির্ভর তথ্য ফাঁস না হওয়া, আর পাওয়া বিন্দু সত্যিই curve-এ আছে কি না যাচাই। এ কারণে Cybersecurity কোর্সের প্রথম নিয়ম: নিজের cryptography নিজে বানাবেন না, পরীক্ষিত library ব্যবহার করুন।

Quantum computer আর post-quantum পরিবর্তন

পর্ব ২৫-এ দেখেছেন, Peter Shor-এর ১৯৯৪ সালের quantum algorithm যথেষ্ট বড় quantum computer-এ factoring দ্রুত করে। একই algorithm discrete log, আর elliptic curve-এর discrete log-ও দ্রুত সমাধান করে। অর্থাৎ RSA, DH আর ECC, তিনটিই তখন ভাঙবে; এই পর্ব পর্যন্ত (২০২৬) এমন বড় quantum computer তৈরি হয়েছে বলে কোনো প্রকাশ্য প্রমাণ নেই। প্রস্তুতি হিসেবে NIST ২০২৪ সালের আগস্টে তিনটি post-quantum মান প্রকাশ করে: FIPS 203 (ML-KEM, key exchange-এর জন্য), FIPS 204 (ML-DSA) আর FIPS 205 (SLH-DSA), দুটিই signature-এর জন্য। এগুলো elliptic curve নয়, lattice আর hash-ভিত্তিক গণিতে দাঁড়ানো। বাস্তব রূপান্তরে অনেক ব্যবস্থা এখন X25519 আর ML-KEM একসঙ্গে (“hybrid”) ব্যবহার করে, যাতে একটি ভাঙলেও অন্যটি রক্ষা করে। বিস্তারিত Cybersecurity কোর্সের পর্ব ১৪-এ।

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

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

অঙ্ক ১: AES-এর GF(2⁸)-এ {57} · {13} কত?

1. {13} = 0001 0011 = x⁴ + x + 1. আংশিক গুণফল: {57} · x⁴ = x¹⁰ + x⁸ + x⁶ + x⁵ + x⁴, {57} · x = x⁷ + x⁵ + x³ + x² + x, {57} · 1 = x⁶ + x⁴ + x² + x + 1.
2. XOR-এ x⁶, x⁵, x⁴, x², x জোড়ায় বাদ: x¹⁰ + x⁸ + x⁷ + x³ + 1.
3. x² · m(x) = x¹⁰ + x⁶ + x⁵ + x³ + x² XOR করলে x⁸ + x⁷ + x⁶ + x⁵ + x² + 1. তারপর m(x) XOR করলে x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x = 1111 1110 = {fe}. ব্লক ১-এর আউটপুটের সঙ্গে মেলে।

অঙ্ক ২: y² = x³ + 2x + 2 (mod 17)-এ G = (5, 1) হলে 2G কত?

1. P = Q, তাই tangent-এর সূত্র: λ = (3 · 5² + 2)/(2 · 1) = 77/2. mod 17-এ 77 ≡ 9, আর 2⁻¹ ≡ 9 (2 · 9 = 18 ≡ 1). λ ≡ 81 ≡ 13.
2. x₃ = 13² − 2 · 5 = 169 − 10 = 159 ≡ 159 − 153 = 6.
3. y₃ = 13(5 − 6) − 1 = −14 ≡ 3. তাই 2G = (6, 3); যাচাই: 3² = 9, আর 216 + 12 + 2 = 230 ≡ 9 ✓.

অঙ্ক ৩: y² = x³ + x + 1 (mod 5)-এ কয়টি বিন্দু?

1. 4 + 27 = 31 ≡ 1 ≢ 0, তাই curve মসৃণ। mod 5-এ বর্গগুলো: 0, 1, 4 (1² = 1, 2² = 4, 3² ≡ 4, 4² ≡ 1).
2. x = 0: 1, y = 1, 4. x = 1: 3, বর্গ নয়। x = 2: 11 ≡ 1, y = 1, 4. x = 3: 31 ≡ 1, y = 1, 4. x = 4: 69 ≡ 4, y = 2, 3.
3. মোট 8টি বিন্দু আর O, N = 9. Hasse: |9 − 6| = 3 ≤ 2√5 ≈ 4.47 ✓.

প্রমাণের ভুল ধরুন: “root নেই, তাই irreducible”

একজন লিখলেন: “দাবি: x⁴ + x² + 1, GF(2)-এর ওপর irreducible, তাই এটি দিয়ে 16 উপাদানের একটি field GF(16) বানানো যায়। প্রমাণ: x = 0 বসালে মান 1, x = 1 বসালে 1 + 1 + 1 = 1. GF(2)-এ কোনো root নেই, তাই কোনো linear উৎপাদক নেই, তাই polynomial-টি irreducible. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: root না থাকা শুধু ঘাত 1-এর উৎপাদক বাদ দেয়। ঘাত 4-এর polynomial দুটি ঘাত-2 polynomial-এর গুণফলও হতে পারে, যাদের কারোরই root নেই। এখানে ঠিক তা-ই: (x² + x + 1)² = x⁴ + 2x³ + 3x² + 2x + 1 ≡ x⁴ + x² + 1 (mod 2). তাই এই modulus-এ x² + x + 1 একটি zero divisor, আর ফল field নয়। “root নেই ⇒ irreducible” শুধু ঘাত 2 আর 3-এ সঠিক, কারণ তখন যেকোনো উৎপাদনে একটি উৎপাদকের ঘাত 1 হতেই হয়। সঠিক পরীক্ষা: ঘাত ≤ 2-এর সব polynomial দিয়ে ভাগ করে দেখা (ব্লক ১-এর মতো)। GF(16)-এর জন্য একটি সঠিক modulus x⁴ + x + 1.

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

AI সহকারী elliptic curve-এর সূত্র মুখস্থের মতো বলে দেয়, কিন্তু mod p-এর ছোট হিসাবে আর শর্তে নিয়মিত ভুল করে। এগুলো চেনা থাকলে ধরতে এক মিনিট লাগে।

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

• প্রতিটি পাওয়া বিন্দু curve-এর সমীকরণে বসিয়ে নিজে মিলিয়েছি
• প্রতিটি modular inverse গুণ করে 1 পাওয়া যায় কি না দেখেছি
• ব্যবহৃত উপপাদ্যের শর্ত (p মৌলিক, irreducible, 4a³ + 27b² ≠ 0) এই সংখ্যায় মিলিয়েছি
• kP-এর ফল ছোট k-এ সরাসরি বারবার যোগের সঙ্গে মিলিয়েছি
• প্রমাণে “root নেই ⇒ irreducible”-এর মতো লাফ বা বাদ পড়া ক্ষেত্র (P = −Q) নেই
• নিরাপত্তার দাবি, key-আকার আর সাল বিশ্বস্ত উৎসে মিলিয়েছি, আর বাস্তব কাজে পরীক্ষিত library বাছা হয়েছে

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