第三次作业（密码学）

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

// 计算最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

// 计算模幂运算
int mod_pow(int base, int exponent, int modulus) {
    int result = 1;
    base = base % modulus;

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }

        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }

    return result;
}

// 生成密钥
void generate_keys(int p, int q, int *e, int *d, int *n) {
    *n = p * q;
    int phi = (p - 1) * (q - 1);

    // 选择e
    for (*e = 2; *e < phi; (*e)++) {
        if (gcd(*e, phi) == 1) {
            break;
        }
    }

    // 计算d
    for (*d = 2; *d < phi; (*d)++) {
        if ((*e * *d) % phi == 1) {
            break;
        }
    }
}

// 加密
int encrypt(int plaintext, int e, int n) {
    return mod_pow(plaintext, e, n);
}

// 解密
int decrypt(int ciphertext, int d, int n) {
    return mod_pow(ciphertext, d, n);
}

int main() {
    int p = 61;
    int q = 53;
    int e, d, n;

    // 生成密钥
    generate_keys(p, q, &e, &d, &n);

    int plaintext = 65;
    printf("明文: %d\n", plaintext);

    // 加密
    int ciphertext = encrypt(plaintext, e, n);
    printf("密文: %d\n", ciphertext);

    // 解密
    int decrypted = decrypt(ciphertext, d, n);
    printf("解密后的明文: %d\n", decrypted);

    return 0;
}