পাঠ ২৮ · ৪৪-এর মধ্যে · মডিউল ৫
Home / Courses / Discrete Mathematics / RSA এনক্রিপশন

RSA এনক্রিপশন — নাম্বার থিওরির বাস্তব প্রয়োগ

RSA encryption — number theory in practice
১০ মিনিট পড়া মাঝারি · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এই পাঠে যা শিখবেন

  • RSA-এর key generation, encryption, decryption ধাপগুলো — একটি সম্পূর্ণ সংখ্যাগত উদাহরণে
  • Public key ও private key কী ভূমিকা পালন করে
  • Euler's Theorem (L27) কীভাবে গ্যারান্টি দেয় যে ডিক্রিপশন সবসময় সঠিক মেসেজ ফেরত দেবে
  • কেন RSA-এর নিরাপত্তা "factoring hardness"-এর উপর সম্পূর্ণভাবে নির্ভরশীল
  • Python দিয়ে সম্পূর্ণ key generation + encrypt + decrypt চক্র বাস্তবায়ন

১ · RSA কী — এক নজরে

RSARSA (Rivest–Shamir–Adleman)১৯৭৭ সালে আবিষ্কৃত একটি public-key cryptography অ্যালগরিদম — Fermat's Little Theorem, Euler's Theorem ও প্রাইম ফ্যাক্টরাইজেশনের কঠিনতার উপর ভিত্তি করে তৈরি। হলো একটি asymmetric (public-key) এনক্রিপশন সিস্টেম — অর্থাৎ এনক্রিপশন ও ডিক্রিপশনে দুটি ভিন্ন চাবি ব্যবহৃত হয়। Public key $(n, e)$ যে কাউকে দেওয়া যায়, এমনকি প্রকাশ্যেও — এটি দিয়ে যে কেউ মেসেজ এনক্রিপ্ট করতে পারে। কিন্তু ডিক্রিপ্ট করতে দরকার private key $(n, d)$, যা শুধু প্রাপকের কাছে গোপন থাকে।

২ · কী-জেনারেশন — ধাপে ধাপে

ওয়ার্কড উদাহরণ — শিক্ষামূলক ছোট প্রাইম দিয়ে (বাস্তব নিরাপত্তার জন্য নয়)
  1. দুটি প্রাইম বেছে নিন: $p = 61$, $q = 53$।
  2. $n = p \times q$ গণনা করুন: $n = 61 \times 53 = 3233$। এটাই মডুলাস — public ও private উভয় key-এর অংশ।
  3. $\varphi(n)$ গণনা করুন (L27): $\varphi(n) = (p-1)(q-1) = 60 \times 52 = 3120$।
  4. $e$ বেছে নিন: এমন একটি সংখ্যা যেন $1 < e < \varphi(n)$ এবং $\gcd(e, \varphi(n)) = 1$। এখানে $e = 17$ — যাচাই: $\gcd(17, 3120) = 1$ (ইউক্লিডিয়ান অ্যালগরিদম, L25, দিয়ে সহজেই যাচাইযোগ্য)।
  5. $d$ গণনা করুন: $d$ হলো $e$-এর মডুলার ইনভার্স মডুলো $\varphi(n)$ (L26 + L25-এর Extended Euclidean Algorithm দিয়ে বের করা হয়) — অর্থাৎ $ed \equiv 1 \pmod{\varphi(n)}$। এখানে $d = 2753$। যাচাই: $17 \times 2753 = 46801$, এবং $46801 = 15 \times 3120 + 1$ — তাই $17 \times 2753 \equiv 1 \pmod{3120}$ ✓।

Public key: $(n, e) = (3233, 17)$ — সবাইকে দেওয়া যায়।
Private key: $(n, d) = (3233, 2753)$ — শুধু গোপন রাখা হয়।

৩ · এনক্রিপশন ও ডিক্রিপশন

একটি সংখ্যাসূচক মেসেজ $m$ (যেখানে $0 \le m < n$) এনক্রিপ্ট করতে —

$$c = m^e \bmod n$$

ধরা যাক $m = 65$। তাহলে —

$$c = 65^{17} \bmod 3233 = 2790$$

ডিক্রিপ্ট করতে প্রাইভেট key ব্যবহার করা হয় —

$$m = c^d \bmod n = 2790^{2753} \bmod 3233 = 65$$

লক্ষ করুন — ডিক্রিপশনের ফলাফল হুবহু আসল মেসেজ $65$-এ ফিরে আসে। এটি কাকতালীয় নয়; এটি L27-এর Euler's Theorem-এর সরাসরি ফলাফল। যেহেতু $ed \equiv 1 \pmod{\varphi(n)}$, তাই $ed = 1 + k\varphi(n)$ কোনো পূর্ণসংখ্যা $k$-এর জন্য। ফলে —

$$c^d = (m^e)^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k \equiv m \pmod n$$

যেখানে মাঝের ধাপে $m^{\varphi(n)} \equiv 1 \pmod n$ ব্যবহার করা হয়েছে — এটাই ঠিক Euler's Theorem (ধরে নিয়ে $\gcd(m,n)=1$, যা প্রায় সবসময় সত্য যেহেতু $n$ মাত্র দুটি বড় প্রাইমের গুণফল)।

মেসেজ m = 65 plaintext c = m^e mod n public key (n,e)=(3233,17) c = 2790 ciphertext c = 2790 পাঠানো হয় m = c^d mod n private key (n,d)=(3233,2753) m = 65 ✓ মূল মেসেজ ফিরে এলো
Public key দিয়ে এনক্রিপ্ট, private key দিয়ে ডিক্রিপ্ট — Euler's Theorem নিশ্চিত করে মূল মেসেজ ঠিকঠাক ফিরে আসবে।

৪ · নিরাপত্তা কোথায় লুকানো?

এই উদাহরণে $n=3233=61\times53$ ফ্যাক্টর করা তুচ্ছ ব্যাপার (এটি নিছক শেখার জন্য, বাস্তব নিরাপত্তার জন্য নয়)। কিন্তু বাস্তব RSA-তে $n$-এর দৈর্ঘ্য হয় ৬০০+ ডিজিট (২০৪৮ বিট বা তার বেশি) — এবং বর্তমান শ্রেষ্ঠ ক্লাসিক্যাল ফ্যাক্টরাইজেশন অ্যালগরিদমগুলোও এত বড় সংখ্যা ফ্যাক্টর করতে মহাবিশ্বের বয়সের চেয়েও বেশি সময় নেবে।

মূল নিরাপত্তা নীতি

RSA-এর গোটা নিরাপত্তা দাঁড়িয়ে আছে একটি একক গাণিতিক অসামঞ্জস্যের (asymmetry) উপর — দুটি বড় প্রাইম গুণ করা সহজ (দ্রুত), কিন্তু গুণফল থেকে মূল প্রাইম দুটি ফিরে বের করা (factoring) কম্পিউটেশনালি প্রায় অসম্ভব কঠিন। Public key $(n,e)$ থেকে $\varphi(n)$ বের করতে হলে $n$-কে ফ্যাক্টর করে $p,q$ বের করতে হবে — এবং সেটাই যথেষ্ট কঠিন যে আক্রমণকারী $\varphi(n)$ পায় না, ফলে $d$-ও বের করতে পারে না। এই একটিমাত্র হার্ডনেস অনুমানের (hardness assumption) উপরই আজকের প্রতিটি নিরাপদ ইন্টারনেট কানেকশনের নিরাপত্তা দাঁড়িয়ে আছে।

Python
# RSA — সম্পূর্ণ ওয়ার্কড উদাহরণ (শিক্ষামূলক ছোট প্রাইম, বাস্তব নিরাপত্তার জন্য নয়)
import math

p, q = 61, 53
n = p * q
phi_n = (p - 1) * (q - 1)
e = 17
d = pow(e, -1, phi_n)  # মডুলার ইনভার্স — Python 3.8+ (L25-এর Extended Euclidean-এর সমতুল্য)

print("n =", n)
print("phi(n) =", phi_n)
print("gcd(e, phi(n)) =", math.gcd(e, phi_n), "(1 হতে হবে coprime হওয়ার জন্য)")
print("d =", d)
print("যাচাই: (e * d) mod phi(n) ==", (e * d) % phi_n, "(1 হওয়া উচিত)")

print()

# এনক্রিপশন
m = 65
c = pow(m, e, n)
print("মূল মেসেজ m =", m)
print("ciphertext c = m^e mod n =", c)

# ডিক্রিপশন
decrypted = pow(c, d, n)
print("ডিক্রিপ্ট করা মেসেজ =", decrypted)
print("মূল মেসেজের সাথে মিলেছে?", decrypted == m)

    


    

      উপরের কোড সেল চালালে c = 2790 এবং ডিক্রিপ্ট করা মেসেজ ঠিক 65-এ ফিরে আসা নিশ্চিত হবে —
      এটাই RSA-এর সম্পূর্ণ চক্র, মাত্র কয়েক লাইনে। বাস্তব লাইব্রেরি (যেমন cryptography বা OpenSSL) একই গণিত
      ব্যবহার করে, শুধু প্রাইমগুলো হয় বিশাল এবং প্যাডিং স্কিম (OAEP) যুক্ত থাকে অতিরিক্ত নিরাপত্তার জন্য।
    


  


  

    
    
  


  

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

    
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।


    

      
        প্র ০১
        যদি কেউ শুধু public key $(n,e)=(3233,17)$ জানে, private key $d$ বের করতে তাকে ঠিক কোন ধাপগুলো পার হতে হবে — এবং কোথায় সে আটকে যাবে?
      
      

        

          প্রথমে তাকে $n=3233$ ফ্যাক্টর করে $p,q$ বের করতে হবে (এই ছোট উদাহরণে সহজ: $3233=61\times53$)। তারপর
          $\varphi(n)=(p-1)(q-1)=3120$ গণনা করে, এবং $e=17$-এর মডুলার ইনভার্স মডুলো $3120$ বের করে $d=2753$ পাবে
          (Extended Euclidean Algorithm, L25)। বাস্তব RSA-তে সমস্যা হলো প্রথম ধাপেই — যখন $n$ ৬০০+ ডিজিট লম্বা হয়, তখন
          এই ফ্যাক্টরাইজেশন ধাপটিই বর্তমান সেরা অ্যালগরিদম দিয়েও ব্যবহারিকভাবে অসম্ভব হয়ে যায়।
        

      

    


    

      
        প্র ০২
        কেন RSA-তে সবসময় দুটি ভিন্ন বড় প্রাইম বেছে নেওয়া হয়, একটি বড় কম্পোজিট সংখ্যা নয়?
      
      

        

          দুটি কারণ। প্রথমত, $\varphi(n)=(p-1)(q-1)$ সূত্রটি শুধুমাত্র তখনই সহজে ও নির্ভুলভাবে কাজ করে যখন $p,q$ ভিন্ন
          প্রাইম (L27-এর প্র ০২ দেখুন) — একটি কম্পোজিট $n$-এর $\varphi(n)$ গণনা করতে হলে তার সম্পূর্ণ প্রাইম ফ্যাক্টরাইজেশন
          লাগবে, যা আরও জটিল করে তুলবে। দ্বিতীয়ত, নিরাপত্তার দৃষ্টিকোণ থেকে — দুটি প্রায় সমান আকারের বড় প্রাইমের গুণফল
          ফ্যাক্টর করা সবচেয়ে কঠিন কেস (একাধিক ছোট ফ্যাক্টরযুক্ত সংখ্যা তুলনামূলক সহজে ফ্যাক্টর করা যায়, যেমন Pollard's
          rho-এর মতো অ্যালগরিদম দিয়ে)।
        

      

    


    

      
        প্র ০৩
        এই পাঠের গণিত ($ed \equiv 1 \pmod{\varphi(n)}$ থেকে ডিক্রিপশন সঠিক হওয়া) কি প্রমাণ করে RSA "নিরাপদ"? পার্থক্যটা ব্যাখ্যা করুন।
      
      

        

          না — এটি শুধু প্রমাণ করে RSA সঠিকভাবে কাজ করে (correctness): যা এনক্রিপ্ট করা হয়েছে, সঠিক private key
          দিয়ে সেটাই ডিক্রিপ্ট হয়ে ফিরে আসবে। কিন্তু "নিরাপদ" (security) মানে ভিন্ন জিনিস — এর অর্থ হলো, private key ছাড়া
          কেউ $c$ থেকে $m$ (অথবা $n$ থেকে $p,q$) বের করতে পারবে না বাস্তবসম্মত সময়ে। Correctness একটি প্রমাণিত গাণিতিক সত্য
          (Euler's Theorem থেকে সরাসরি নেমে আসে), কিন্তু security একটি অনুমান (factoring hardness assumption) —
          এটি প্রমাণিত নয় যে বড় সংখ্যা ফ্যাক্টর করা মৌলিকভাবেই কঠিন, শুধু এখন পর্যন্ত কোনো দ্রুত ক্লাসিক্যাল অ্যালগরিদম
          পাওয়া যায়নি (Quantum computing-এর Shor's Algorithm এই অনুমানকেই ভবিষ্যতে চ্যালেঞ্জ করতে পারে, যা এই কোর্সের
          পরিসরের বাইরে)।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        পরীক্ষা করুন: উপরের কোড সেলে মেসেজ m-এর মান 65 থেকে বদলে 42 করে Run চাপুন। নতুন ciphertext কী হলো, এবং ডিক্রিপশন কি এখনও সঠিক মূল মেসেজ ফেরত দিচ্ছে?
        
    
          
          
    
            
    
              $m=42$ হলে $c = 42^{17} \bmod 3233$ — একটি ভিন্ন ciphertext মান হবে (কোড রান করলে সঠিক মান দেখা যাবে)। যেহেতু
              $\gcd(42,3233)=1$ (৪২-এর ফ্যাক্টর $2,3,7$ — কোনোটিই $61$ বা $53$ নয়), Euler's Theorem-এর শর্ত পূরণ হয়, তাই
              ডিক্রিপশন এখনও সঠিকভাবে $42$-এ ফিরে আসবে।
            
    
          
    
        
    
      
    2. 
      
  2. 
        যুক্তি দিন: $e=17$ কেন coprime হতে হবে $\varphi(n)=3120$-এর সাথে — যদি $\gcd(e,\varphi(n)) \ne 1$ হতো, তাহলে key generation-এর কোন ধাপে সমস্যা হতো?
        
    
          
          
    
            
    
              $d$ হলো $e$-এর মডুলার ইনভার্স মডুলো $\varphi(n)$ — অর্থাৎ $ed \equiv 1 \pmod{\varphi(n)}$ সমাধানকারী $d$।
              L26-এ দেখেছি, মডুলার ইনভার্সের অস্তিত্ব থাকে শুধু তখনই যখন $\gcd(e,\varphi(n))=1$। যদি এই শর্ত ভঙ্গ হতো,
              তাহলে কোনো বৈধ $d$-ই থাকত না — key generation ধাপ ৫-এই আটকে যেত, এবং পুরো RSA সিস্টেমটি তৈরিই করা যেত না।
            
    
          
    
        
    
      
    3. 
    

  


  

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

    
  







  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 পূর্ববর্তী পাঠ

    
পাঠ ২৭ · ফার্মার লিটল থিওরেম ও অয়লার'স থিওরেম