RSA

Key generation:

p, q  দুইটা বড় মৌলিক
n = pq
φ(n) = (p−1)(q−1)
e  বেছে নিন যেন gcd(e, φ(n)) = 1        public exponent
d ≡ e⁻¹ (mod φ(n))                       private exponent

Public key (n, e), private key (n, d)।

Encrypt / decrypt:

c = mᵉ mod n
m = cᵈ mod n

কেন কাজ করে: Euler’s theorem অনুযায়ী m^φ(n) ≡ 1 (mod n)। যেহেতু ed ≡ 1 (mod φ(n)), লিখতে পারি ed = 1 + kφ(n), তাই:

cᵈ = m^(ed) = m^(1+kφ(n)) = m · (m^φ(n))ᵏ ≡ m · 1ᵏ ≡ m  (mod n)

নিরাপত্তা কীসের উপর: n থেকে p, q বের করতে পারলে φ(n) পাওয়া যায়, আর তখন d হিসাব করা যায়। তাই RSA ভাঙা মানে factoring — যা বর্তমান classical algorithm-এ অবাস্তব।

গুরুত্বপূর্ণ বাস্তব সতর্কতা: এই “textbook RSA” সরাসরি ব্যবহার করা যায় না — deterministic, তাই একই message একই ciphertext দেয়, আর বহু আক্রমণের মুখে খোলা। বাস্তবে OAEP padding, নিরাপদ প্যারামিটার আর যাচাইকৃত library (OpenSSL, libsodium) ব্যবহার করতে হয়। নিজে crypto implement করবেন না — শেখার জন্য ছাড়া।