为何RSA算法加解密结果不一致？C语言实现问题求助

设计目的 #

使用C语言编写一个健壮的命令行程序，模拟RSA算法。

遇到的问题 #

当使用参数e=7、p=3、q=11时，加解密功能正常。但更换其他e、p、q值后，生成的密文及解密结果出现严重不一致，甚至出现负的密文值。:-(

C语言实现代码 #

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

struct RSACfg {
  long d;
  long e;
  long p;
  long q;
};

long gcd(long a, long b) {
  if (!b)
    return labs(a);
  return gcd(b, a % b);
}
int valid_rsa(const struct RSACfg *c) {
  const long *e = &c->e, *p = &c->p, *q = &c->q, n = *p * (*q),
             m = (*p - 1) * (*q - 1);
  int pass_1 = gcd(*p, *q) == 1, pass_2 = gcd(m, *e) == 1,
      pass_3 = gcd(n, *e) == 1, pass_4 = *e > 0 && *e < (*p * (*q)), pass_5 = 1;

  if (c->d)
    pass_5 = gcd(c->d, m) == 1;

  return pass_1 & pass_2 & pass_3 & pass_4 & pass_5;
}

int make_d(long *d, const struct RSACfg *cfg) {
  if (!valid_rsa(cfg))
    return -1;
  const long p = cfg->p, q = cfg->q, e = cfg->e, n = p * q,
             t = (p - 1) * (q - 1);
#ifdef DEBUG
    printf("info: solving '%ld x d = 1 (mod %ld)' using `make_d(long*, const struct RSACfg*)`\n", e, t);
#endif
  for (long i = 1; i < t; i++){
  
    if ((i * e) % t == 1 && gcd(i, t) == 1) {
      *d = i;
      return 0;
    }
 }
#ifdef DEBUG
  fprintf(stderr,
          "error: %ld could not be used to calculate 'd' with totient %ld\n", e,
          t);
#endif
  return 1; // not invertible
}

int mod_inv(long *inv, const long a, const long n) {
  long t = 0, newt = 1;
  long r = n, newr = a;

  while (newr) {
    long quotient = r / newr, tmp = t;
    t = newt;
    newt = tmp - quotient * newt;
    tmp = r;
    r = newr;
    newr = tmp - quotient * newr;
  }

  if (r > 1)
    return 1;

  if (t < 0)
    t += n;

  *inv = t;
  return 0;
}

int encrypt(long *M, const long m, const struct RSACfg *r) {
  if (!valid_rsa(r))
    return 1;
  *M = ((long)pow(m, r->e)) % (r->p * r->q);
  return 0;
}

int decrypt(long *m, const long M, const struct RSACfg *r) {
  long d = r->d;
  const long *p = &r->p, *q = &r->q, *e = &r->e;
  if (!valid_rsa(r)){
#ifdef DEBUG
      fprintf(stderr, "error: RSACfg is not valid (%s:%d)\n",__FILE__, __LINE__);
#endif
    return 1;
   }
  if (!d) {
    if (mod_inv(&d, *e, (*p - 1) * (*q - 1))) {
#ifdef DEBUG
      fprintf(stderr, "error: 'd' is not invertible '*m' not assigned\n");
#endif
      return 2;
    }
  }
  *m = ((long)pow(M, d)) % (*p * (*q));

  return 0;
}

驱动代码 #

int do_encrypt(long *, const long, const struct RSACfg *);

int do_decrypt(long *, const long, struct RSACfg *);

int main(int argc, char **argv) {
  struct RSACfg cfg = {.e = 7, .p = 3, .q = 11, .d = 0};
  long M, m, e, d, p, q;
  int opt;
  opterr = e = p = q = d = 0;

  while ((opt = getopt(argc, argv, ":hDEe:p:q:m:M:")) != -1) {
    switch (opt) {
    case 'h':
      printf("Usage: %s [-h] [-DE] [-d] [-e x -p y -q z] arg\n", argv[0]);
      return 0;
    case 'D':
      task = Decrypt;
      break;
    case 'E':
      task = Encrypt;
      break;
    case 'e':
      e = atoi(optarg);
      break;
    case 'd':
      d = atoi(optarg);
      break;
    case 'p':
      p = atoi(optarg);
      break;
    case 'q':
      q = atoi(optarg);
      break;
    case ':':
      fprintf(stderr, "'-%c' option missing a value\n", optopt);
      return -1;
    case '?':
      fprintf(stderr, "Unrecognized option '-%c'\n", optopt);
      return 1;
    }
  }

  if (!task) {
    fprintf(stderr, "Specify a task with -E or -D option\n");
    return 3;
  }

  if ((d && task == Decrypt) || (e || p || q)) {
    if (!(p && q && e)) {
      fprintf(stderr, "error: Make sure you set a complete update on p, q and "
                      "e when you set any of the options (e,p,q)\n");
      return 4;
    }
    cfg.e = e;
    cfg.p = p;
    cfg.q = q;
  }
  if (optind < argc) {
    if (task == Decrypt) {
      M = atoi(argv[optind]);
      if (d)
        cfg.d = d;
      do_decrypt(&m, M, &cfg);
      printf("Decryption\nM: %ld\nResult: %ld\n", M, m);
    } else if (task == Encrypt) {
      m = atoi(argv[optind]);
      do_encrypt(&M, m, &cfg);
      printf("Encryption\nm: %ld\nResult: %ld\n", m, M);
    }
  } else {
    fprintf(stderr, "error: An argument was expected\n");
    return 5;
  }
}

int do_encrypt(long *M, const long m, const struct RSACfg *c) {
  printf("Encrypting with pub key(%ld,%ld)\n", c->p * c->q, c->e);
  return encrypt(M, m, c);
}

int do_decrypt(long *m, const long M, struct RSACfg *c) {
  if (!c->d)
    make_d(&c->d, c);

  printf("Decrypting with priv key(%ld, %ld, %ld)\n", c->d, c->p, c->q);
  return decrypt(m, M, c);
}

我已经为此困惑一周，多次查阅资料优化实现，但始终失败。

我最近参考相关资料调整了struct RSACfg，使long d可在运行时计算。

更新（测试示例） #

编译命令：

~$ gcc mod.c -lm

运行示例：加密明文28

~$ ./a.out -E 28

与默认参数运行效果一致：

~$ ./a.out -e7 -p3 -q11 -E 28

输出结果：

Encrypting with pub key(33,7)
Encryption
m: 28
Result(M): 19

将加密参数-E替换为解密参数-D，参数值改为19，得到：

info: solving '7 x d = 1 (mod 20)' using `make_d(long*, const struct RSACfg*)`
Decrypting with priv key (3, 3, 11)
Decryption
M: 19
Result(m): 28

注意：设置-d X时，必须同时传入-p、-q、-e参数（设置其中任意一个时，需全部设置）

问题示例（更换-p、-q、-e值导致不一致） #

~$ ./a.out -e 13 -p17 -q100003 -E 4
Encrypting with pub key(1700051,13)
Encryption
m: 4
Result(M): 806875

~$ ./a.out -e 13 -p17 -q100003 -D 806875
Decrypting with priv key (615397, 17, 100003)
Decryption
M: 806875
Result(m): -1156009  # 此处结果应为4，而非-1156009

内容的提问来源于stack exchange，提问作者thetva