RSA非对称加密算法c语言实现

RSA算法是一种非对称加密算法，可以用于加密和解密数据。下面是使用C语言实现RSA算法的示例代码：

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

// 求最大公约数
int gcd(int a, int b) {
    int temp;
    while (b) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// 求扩展欧几里得算法，用于求私钥d
int exgcd(int a, int b, int *x, int *y) {
    int r, temp;
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    r = exgcd(b, a % b, x, y);
    temp = *x;
    *x = *y;
    *y = temp - (a / b) * (*y);
    return r;
}

// 判断是否为素数
int is_prime(int n) {
    int i, m;
    if (n == 2) {
        return 1;
    }
    if (n < 2 || n % 2 == 0) {
        return 0;
    }
    m = sqrt(n);
    for (i = 3; i <= m; i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

// 生成公钥和私钥
void gen_key(int *p, int *q, int *n, int *e, int *d) {
    int phi, x, y;
    while (1) {
        // 生成两个素数p和q
        *p = rand() % 100 + 1;
        while (!is_prime(*p)) {
            *p = rand() % 100 + 1;
        }
        *q = rand() % 100 + 1;
        while (!is_prime(*q) || *q == *p) {
            *q = rand() % 100 + 1;
        }
        // 计算n和phi
        *n = *p * *q;
        phi = (*p - 1) * (*q - 1);
        // 选择公钥e，要求e与phi的最大公约数为1
        *e = rand() % (phi - 2) + 2;
        while (gcd(*e, phi) != 1) {
            *e = rand() % (phi - 2) + 2;
        }
        // 计算私钥d，使用扩展欧几里得算法
        exgcd(*e, phi, &x, &y);
        if (x < 0) {
            x += phi;
        }
        *d = x;
        if (*d > 0) {
            break;
        }
    }
}

// 加密
void encrypt(int m, int e, int n, int *c) {
    int i;
    c[0] = m;
    for (i = 1; i <= e - 1; i++) {
        c[i] = (c[i - 1] * m) % n;
    }
}

// 解密
int decrypt(int *c, int d, int n, int len) {
    int i, m;
    m = c[len - 1];
    for (i = len - 2; i >= 0; i--) {
        m = (m * c[i]) % n;
    }
    return m;
}

int main() {
    int p, q, n, e, d, m, len, i;
    int c[100];
    srand(time(NULL));
    // 生成公钥和私钥
    gen_key(&p, &q, &n, &e, &d);
    printf("p = %d, q = %d, n = %d, e = %d, d = %d\n", p, q, n, e, d);
    // 输入明文
    printf("请输入明文: ");
    scanf("%d", &m);
    // 加密
    encrypt(m, e, n, c);
    printf("密文: ");
    len = sizeof(c) / sizeof(int);
    for (i = 0; i < len && c[i] != 0; i++) {
        printf("%d ", c[i]);
    }
    // 解密
    m = decrypt(c, d, n, i);
    printf("\n解密后的明文: %d\n", m);
    return 0;
}

在这个示例代码中，我们使用了随机数生成两个素数p和q，并计算出n和phi。然后，我们选择公钥e，并使用扩展欧几里得算法计算出私钥d。在加密时，我们将明文m进行加密，并保存到数组c中。在解密时，我们使用私钥d和数组c中的元素，计算出明文m。