编辑代码

#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;
}

// 寻找 k 值
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;  // 未找到有效的 k 值
}

// 模幂运算
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() {
  // 生成 RSA 密钥对
  ULL p = 13;
  ULL q = 17;
  ULL e = 7;

  // 计算 n = p * q
  ULL n = p * q;

  // 计算 φ(n) = (p - 1) * (q - 1)
  ULL phi = (p - 1) * (q - 1);

  // 计算 e 的模反元素 d
  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;
}