#include <stdio.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, ULL publicKeyE, ULL 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, ULL privateKeyD, ULL 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 = 13;
ULL q = 17;
ULL e = 7;
ULL n = p * q;
ULL phi = (p - 1) * (q - 1);
ULL k = findK(phi, e);
ULL d = (k * phi + 1) / e;
ULL publicKeyE = e;
ULL publicKeyN = n;
ULL privateKeyD = d;
ULL privateKeyN = n;
char message[] = "Hello, RSA! -By.Mr_Fang";
int messageLength = sizeof(message) - 1;
ULL encryptedMessage[messageLength];
encrypt(message, encryptedMessage, messageLength, publicKeyE, publicKeyN);
char decryptedMessage[messageLength + 1];
decrypt(encryptedMessage, decryptedMessage, messageLength, privateKeyD, privateKeyN);
decryptedMessage[messageLength] = '\0';
printf("公 钥: (%llu, %llu)\n", publicKeyE, publicKeyN);
printf("私 钥: (%llu, %llu)\n", privateKeyD, privateKeyN);
printf("原始消息: \n%s\n", message);
printf("加密密文: \n");
for (int i = 0; i < messageLength; i++) {
printf("%llu ", encryptedMessage[i]);
}
printf("\n解密后: \n%s\n", decryptedMessage);
return 0;
}