RSA算法模拟实验报告

课程名称

网络安全

实验

成绩

实验

RSA算法模拟

学号

姓名

日期

2024.9.24

一、实验目的

（1）学习RSA基本算法

（2）学习指数求模运算

（3）学习逆元的求法

二、实验原理

1. 生成两个大素数 p 和 q；
2. 计算这两个素数的乘积 n= p * q；
3. 计算小于n并且与n互质的整数的个数，即欧拉函数     φ(n) = (p - 1) * (q - 1)；
4. 随机选择一个加密密钥e，使e满足1< e < φ(n)，并且e和φ(n)互质；
5. 利用欧几里德扩展算法计算e的逆元d，以满足：         e * d ≡ 1 mod φ(n)
6. 公钥PK={e, n}；对应的私钥SK={d}
7. 加密运算：C=Me mod n（如何防止溢出）
8. 解密运算M=Cd mod n （如何防止溢出）

三、实验环境

操作系统：windows

运行环境：VC6.0或DEV C++

四、实验步骤

（1）具体实现

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

using namespace std;

// 模幂运算，防止溢出

long long modularExponentiation(long long base, long long exponent, long long modulus) {

    long long result = 1;

    base %= modulus;

    while (exponent > 0) {

        if (exponent % 2 == 1)

            result = (result * base) % modulus;

        exponent >>= 1;

        base = (base * base) % modulus;

    }

    return result;

}

// 判断素数

bool isPrime(long long num) {

    if (num < 2) return false;

    if (num == 2 || num == 3) return true;

    if (num % 2 == 0 || num % 3 == 0) return false;

    long long i = 5;

    while (i * i <= num) {

        if (num % i == 0 || num % (i + 2) == 0) return false;

        i += 6;

    }

    return true;

}

// Miller-Rabin 素性测试

bool isPrimeMillerRabin(long long n, int iterations = 5) {

    if (n < 2) return false;

    if (n == 2 || n == 3) return true;

    if (n % 2 == 0) return false;

    long long d = n - 1;

    int s = 0;

    while (d % 2 == 0) {

        d /= 2;

        s++;

    }

    for (int i = 0; i < iterations; i++) {

        long long a = rand() % (n - 3) + 2;

        long long x = modularExponentiation(a, d, n);

        if (x == 1 || x == n - 1) continue;

        bool found = false;

        for (int r = 1; r < s; r++) {

            x = (x * x) % n;

            if (x == n - 1) {

                found = true;

                break;

            }

        }

        if (!found) return false;

    }

    return true;

}

// 生成大素数

long long generatePrime() {

    long long prime;

    while (true) {// 增加生成的随机数范围，以获得更大的素数

    prime = rand() % 10000 + 10000;

    if (isPrime(prime)) {

        break;

    }

}

    return prime;

}

// 计算两个数的最大公约数

long long gcd(long long a, long long b) {

    while (b!= 0) {

        long long temp = b;

        b = a % b;

        a = temp;

    }

    return a;

}

// 扩展欧几里得算法

long long extendedEuclidean(long long a, long long b, long long& x, long long& y) {

    if (b == 0) {

        x = 1;

        y = 0;

        return a;

    }

    long long x1, y1;

    long long gcd = extendedEuclidean(b, a % b, x1, y1);

    x = y1;

    y = x1 - (a / b) * y1;

    return gcd;

}

// 计算模逆元

long long modInverse(long long a, long long m) {

    long long x, y;

    long long g = extendedEuclidean(a, m, x, y);

    if (g!= 1) return -1;

    return (x % m + m) % m;

}

int main() {

    long long p, q, n, ol, e, d;

    p = generatePrime();

    q = generatePrime();

    n = p * q;

    ol = (p - 1) * (q - 1);

    while (gcd(e, ol)!= 1){

     e = rand() % ol;

    }

    d = modInverse(e, ol);

    long long message = 123;

    long long ciphertext = modularExponentiation(message, e, n);

    long long decryptedMessage = modularExponentiation(ciphertext, d, n);

    cout << "p：" << p << endl;

    cout << "q：" << q << endl;

    cout << "n：" << n << endl;

    cout << "欧拉：" << ol << endl;

    cout << "加密密匙：" << e << endl;

    cout << "逆元：" << d << endl;

    cout << "原始消息：" << message << endl;

    cout << "加密后的消息：" << ciphertext << endl;

    cout << "解密后的消息（字符形式）：" << decryptedMessage << endl;

    return 0;

}

五、实验结论

【密码学基础】RSA加密算法（图片来自于这一篇文章）

1、了解了一点防溢出（大整数类型和合适的分解计算）

之前也遇到过类似的（好像是二分查找），就是 (l+r)/2  (r+l)>>1，需要写成 (r-l)/2+l  ((r-l)>>1)+l，从数学的角度上来看，这两种写法是一样的，但是第一种是有可能造成溢出的（l+r）

比如说这里的加密：就可以分解成这样：

85×85 = 7225，7225mod143 = 74
74×85 = 6290，6290mod143 = 49
49×85 = 4165，4165mod143 = 104
104×85 = 8840，8840mod143 = 109
109×85 = 9265，9265mod143 = 123

1. 又回忆起了被c++支配的恐惧（写不习惯）

比如函数要在main函数之前才能调用，但是java习惯性的直接调。

1. Miller-Rabin 素性测试

在判断大素数时，可以用Miller-Rabin 素性测试，提高效率（应该跟剪枝差不多）。

报告评分：