C++-এ RSA অ্যালগরিদম ইমপ্লিমেন্টেশন

RSA (Rivest-Shamir-Adleman) একটি অ্যাসিমেট্রিক ক্রিপ্টোগ্রাফি অ্যালগরিদম (asymmetric cryptography algorithm) যা দুটি কী- পাবলিক কী (public key) এবং প্রাইভেট কী (private key) দিয়ে কাজ করে।

এলগরিদম

Begin
1. দুটি প্রাইম নম্বর p এবং q বেছে নিন।
2. n = p*q ক্যালকুলেট করুন।
3. phi = (p-1) * (q-1) ক্যালকুলেট করুন।
4. একটি ইন্টিজার e বেছে নিন যাতে 1 < e < phi(n) এবং gcd(e, phi(n)) = 1; অর্থাৎ e এবং phi(n) কো-প্রাইম (coprime)।
5. d ক্যালকুলেট করুন যাতে d ≡ e⁻¹ (mod phi(n)); এখানে d হলো e-এর মডুলার মাল্টিপ্লিকেটিভ ইনভার্স মডুলো phi(n)।
6. এনক্রিপশনের জন্য, c = m^e mod n, যেখানে m = মূল মেসেজ।
7. ডিক্রিপশনের জন্য, m = c^d mod n।
End

উদাহরণ

#include <iostream>
#include <math.h>
using namespace std;

// GCD বের করার ফাংশন
int gcd(int a, int b) {
    int t;
    while(1) {
        t = a % b;
        if(t == 0)
            return b;
        a = b;
        b = t;
    }
}

int main() {
    // দুটি র‍্যান্ডম প্রাইম নম্বর
    double p = 13;
    double q = 11;
    double n = p * q; // n ক্যালকুলেট
    double track;
    double phi = (p-1)*(q-1); // phi ক্যালকুলেট

    // পাবলিক কী
    double e = 7; // e stands for encrypt
    // চেক: 1 < e < phi(n) এবং gcd(e, phi(n)) = 1
    while(e < phi) {
        track = gcd(e, phi);
        if(track == 1)
            break;
        else
            e++;
    }

    // প্রাইভেট কী
    double d1 = 1/e;
    double d = fmod(d1, phi); // নোট: এই পদ্ধতিটি বাস্তবে ভুল, সঠিক পদ্ধতি হলো এক্সটেনডেড ইউক্লিডিয়ান অ্যালগরিদম

    double message = 9;
    double c = pow(message, e); // মেসেজ এনক্রিপ্ট
    double m = pow(c, d);
    c = fmod(c, n);
    m = fmod(m, n);

    cout << "Original Message = " << message;
    cout << "\np = " << p;
    cout << "\nq = " << q;
    cout << "\nn = pq = " << n;
    cout << "\nphi = " << phi;
    cout << "\ne = " << e;
    cout << "\nd = " << d;
    cout << "\nEncrypted message = " << c;
    cout << "\nDecrypted message = " << m;
    return 0;
}

আউটপুট

p = 13
q = 11
n = pq = 143
phi = 120
e = 7
d = 0.142857
Original Message = 9
Encrypted message = 48
Decrypted message = 9

দ্রষ্টব্য: প্রদত্ত উদাহরণে `d` ক্যালকুলেট করার পদ্ধতি (`fmod(1/e, phi)`) গাণিতিকভাবে ভুল। বাস্তবে `d` বের করতে এক্সটেনডেড ইউক্লিডিয়ান অ্যালগরিদম (Extended Euclidean Algorithm) ব্যবহার করতে হয় যাতে `d*e ≡ 1 (mod phi)` সত্য হয়।