rsa实验报告 C语言

RSA算法是一种非对称加密算法，使用公钥进行加密，私钥进行解密。本实验将使用C语言实现RSA算法。

1. 生成公钥和私钥

首先，我们需要生成RSA算法所需的公钥和私钥。生成过程如下：

1.1 选择两个大质数p和q，计算它们的乘积n=p*q。

1.2 计算欧拉函数φ(n)=(p-1)*(q-1)。

1.3 选择一个整数e，满足1<e<φ(n)且e与φ(n)互质。

1.4 计算e关于φ(n)的模反元素d，即满足e*d mod φ(n)=1的整数d。

1.5 公钥为(n,e)，私钥为(n,d)。

C语言代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int is_prime(int n) {
    if (n < 2) {
        return 0;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int mod_inverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;
    if (m == 1) {
        return 0;
    }
    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0) {
        x1 += m0;
    }
    return x1;
}

void generate_key(int *n, int *e, int *d) {
    srand((unsigned int)time(NULL));
    int p, q, phi_n;
    do {
        p = rand() % 100 + 1;
    } while (!is_prime(p));
    do {
        q = rand() % 100 + 1;
    } while (!is_prime(q));
    *n = p * q;
    phi_n = (p - 1) * (q - 1);
    do {
        *e = rand() % phi_n + 1;
    } while (gcd(*e, phi_n) != 1);
    *d = mod_inverse(*e, phi_n);
}

int main() {
    int n, e, d;
    generate_key(&n, &e, &d);
    printf("public key: (%d, %d)\n", n, e);
    printf("private key: (%d, %d)\n", n, d);
    return 0;
}

2. 加密和解密

生成公钥和私钥后，我们可以使用公钥进行加密，使用私钥进行解密。加密和解密的过程如下：

2.1 加密：将明文m进行加密，得到密文c=m^e mod n。

2.2 解密：将密文c进行解密，得到明文m=c^d mod n。

C语言代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int is_prime(int n) {
    if (n < 2) {
        return 0;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int mod_inverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;
    if (m == 1) {
        return 0;
    }
    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0) {
        x1 += m0;
    }
    return x1;
}

void generate_key(int *n, int *e, int *d) {
    srand((unsigned int)time(NULL));
    int p, q, phi_n;
    do {
        p = rand() % 100 + 1;
    } while (!is_prime(p));
    do {
        q = rand() % 100 + 1;
    } while (!is_prime(q));
    *n = p * q;
    phi_n = (p - 1) * (q - 1);
    do {
        *e = rand() % phi_n + 1;
    } while (gcd(*e, phi_n) != 1);
    *d = mod_inverse(*e, phi_n);
}

int mod_pow(int a, int b, int m) {
    int result = 1;
    while (b > 0) {
        if (b & 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return result;
}

int encrypt(int m, int e, int n) {
    return mod_pow(m, e, n);
}

int decrypt(int c, int d, int n) {
    return mod_pow(c, d, n);
}

int main() {
    int n, e, d;
    generate_key(&n, &e, &d);
    printf("public key: (%d, %d)\n", n, e);
    printf("private key: (%d, %d)\n", n, d);
    int m = 1234;
    int c = encrypt(m, e, n);
    printf("encrypted message: %d\n", c);
    int decrypted_m = decrypt(c, d, n);
    printf("decrypted message: %d\n", decrypted_m);
    return 0;
}

以上就是使用C语言实现RSA算法的过程。