#include <stdio.h>
#include <stdlib.h>
#define ULL unsigned long long
ULL extendedEuclidean(ULL a, ULL e, ULL* x, ULL* y) {
if (e == 0) {
*x = 1;
*y = 0;
return a;
}
ULL x1, y1;
ULL gcd = extendedEuclidean(e, a % e, &x1, &y1);
*x = y1;
*y = x1 - (a / e) * y1;
return gcd;
}
ULL findK(ULL phiN, ULL e) {
ULL k = 1;
while (1) {
ULL x, y, gcd;
gcd = extendedEuclidean(k * phiN + 1, e, &x, &y);
ULL d = (k * phiN + 1) / e;
if (d > 0 && (k * phiN + 1) % e == 0) {
return k;
}
k++;
}
return -1;
}
ULL modPow(ULL base, ULL exponent, ULL modulus) {
if (modulus == 1) {
return 0;
}
ULL result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
exponent = exponent / 2;
base = (base * base) % modulus;
}
return result;
}
void encrypt(char* message, ULL* encryptedMessage, int messageLength, int publicKeyE, int publicKeyN) {
for (int i = 0; i < messageLength; i++) {
ULL charCode = message[i];
ULL encryptedCharCode = modPow(charCode, publicKeyE, publicKeyN);
encryptedMessage[i] = encryptedCharCode;
}
}
void decrypt(ULL* encryptedMessage, char* decryptedMessage, int messageLength, int privateKeyD, int privateKeyN) {
for (int i = 0; i < messageLength; i++) {
ULL encryptedCharCode = encryptedMessage[i];
ULL decryptedCharCode = modPow(encryptedCharCode, privateKeyD, privateKeyN);
decryptedMessage[i] = decryptedCharCode;
}
}
int main() {
ULL p, q, e;
printf("请输入 p: ");
scanf("%llu", &p);
printf("请输入 q: ");
scanf("%llu", &q);
printf("请输入 e: ");
scanf("%llu", &e);
ULL n = p * q;
ULL phi = (p - 1) * (q - 1);
ULL k = findK(phi, e);
ULL d = (k * phi + 1) / e;
int publicKeyE = e;
int publicKeyN = n;
int privateKeyD = d;
int privateKeyN = n;
printf("公 钥: (%d, %llu)\n", publicKeyE, publicKeyN);
printf("私 钥: (%d, %llu)\n", privateKeyD, privateKeyN);
char message[100];
printf("\n原始信息: \n");
scanf(" %[^\n]s", message);
int messageLength = strlen(message);
ULL encryptedMessage[messageLength];
encrypt(message, encryptedMessage, messageLength, publicKeyE, publicKeyN);
char decryptedMessage[messageLength + 1];
decrypt(encryptedMessage, decryptedMessage, messageLength, privateKeyD, privateKeyN);
decryptedMessage[messageLength] = '\0';
printf("加密密文: \n");
for (int i = 0; i < messageLength; i++) {
printf("%llu ", encryptedMessage[i]);
}
printf("\n解密结果: \n%s\n", decryptedMessage);
return 0;
}