Simple RSA Algorithm implement in C

rsa.c

/*see https://github.com/LeeReindeer/netwink/blob/master/dbg.h*/
#include "../lib/dbg.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_DATA 1024
#define LL long long
#define rsa_key_free free

typedef struct _key {
  LL N;
  LL x;
} key;

LL cal_d(LL e, LL ph_n);
void keygen(key *pri_key, key *pub_key);
size_t encrypt(key *pub_key, char *msg, int size, char **en_msg);
size_t decrypt(key *pub_key, char *msg, int size, char **de_msg);

// a，b 的最大公因数
LL gcd(LL a, LL b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

int check_prim(LL a) {
  int flag = 1;
  for (int i = 2; (i * i) <= a; i++) {
    if (a % i == 0) {
      flag = 0;
      break;
    }
  }
  return flag;
}

//计算 d
LL cal_d(LL e, LL ph_n) {
  LL d = 1;
  while ((e * d) % ph_n != 1) {
    d++;
  }
  return d;
}

/**
 * @brief  keys must has been alloc mem
 */
void keygen(key *pri_key, key *pub_key) {
  LL p, q, N, ph_n, e, d;

enter:
  printf("输入两个素数：\n");
  scanf("%lld %lld", &p, &q);
  if (!check_prim(p) || !check_prim(q)) {
    printf("不是素数， 请重新输入\n");
    goto enter;
  }

  N = p * q;
  ph_n = (p - 1) * (q - 1);

enter_e:
  printf("输入一个小于 %lld 并且与其互质的数：\n", ph_n);
  scanf("%lld", &e);
  if (gcd(e, ph_n) != 1) {
    printf("不互质， 请重新输入\n");
    goto enter_e;
  }

cal_d:
  d = cal_d(e, ph_n);

  pri_key->N = N;
  pri_key->x = d;

  pub_key->N = N;
  pub_key->x = e;
}

/**
 * @brief  use public key to encrypt message, assume msg has alloced, and *en_msg
 * is not alloced.
 * memory and must free by caller.
 * @param  *pub_key: public key in rsa
 * @param  *msg: message to encrypt
 * @param  *en_msg: message reciver to get encrypted message.
 * @retval size of encrypted message
 */
size_t encrypt(key *pub_key, char *msg, int size, char **en_msg) {
  *en_msg = (char *)calloc(MAX_DATA, sizeof(char));
  int t = -1;

  while (++t < size) {
    LL power = 1;
    // e = pub_key->x
    for (LL i = 0; i < pub_key->x; i++) {
      power *= ((int)msg[t] - 96); //减去 96 防止溢出
      power %= pub_key->N;         //利用同余的传递性
    }
    (*en_msg)[t] = (char)power;
  }
  (*en_msg)[t] = '\0';
  return strlen(*en_msg);
}

/**
 * @brief  use private key to get decrypted message
 * @param  *pri_key: private key in rsa
 * @param  *msg: encrypted message
 * @param  *de_msg: reciver to get decrypted message
 * @retval size of decrypted message
 */
size_t decrypt(key *pri_key, char *msg, int size, char **de_msg) {
  *de_msg = (char *)calloc(MAX_DATA, sizeof(char));
  int t = -1;
  while (++t < size) {
    LL power = 1;
    // d = pri_key->x
    for (LL i = 0; i < pri_key->x; i++) {
      power *= ((int)msg[t]);
      power %= pri_key->N;
    }
    (*de_msg)[t] = (char)power + 96; //加回 96
  }
  (*de_msg)[t] = '\0';
  return strlen(*de_msg);
}

void printf_msg(char *msg, int size) {
  printf("%s\n", msg);

  printf("(");
  for (int i = 0; i < size; i++) {
    printf("%3d", msg[i]);
    if (i != size - 1) {
      printf(",");
    }
  }
  printf(")\n");
}

/**
 * @retval return user selection 1 or 2
 */
int user_ops() {
re:
  printf("1.使用默认的私钥和密钥\n2.使用自定义私钥和密钥\n(input 1 or 2)");
  int op = 0;
  scanf("%d", &op);
  if (op != 1 && op != 2) {
    log_e("%d 输入错误", op);
    goto re;
  }
  return op;
}

int main() {
  key *pri_key = calloc(1, sizeof(key));
  key *pub_key = calloc(1, sizeof(key));

  if (user_ops() == 1) {
    pub_key->N = 85;
    pub_key->x = 7;
    pri_key->N = 85;
    pri_key->x = 55;
  } else {
    keygen(pri_key, pub_key);
  }

  printf("private key: <%lld, %lld>\n", pri_key->N, pri_key->x);
  printf("public key: <%lld, %lld>\n", pub_key->N, pub_key->x);

  char send_msg[MAX_DATA];
  char *encrypted_msg = NULL;
  char *decrypted_msg = NULL;

  printf(">");
  while (scanf("%s", send_msg) && strcmp(send_msg, "q")) {
    int send_size = strlen(send_msg);

    printf("send message:");
    printf_msg(send_msg, send_size);

    size_t en_size = encrypt(pub_key, send_msg, send_size, &encrypted_msg);
    printf("encrypted message:");
    printf_msg(encrypted_msg, en_size);

    size_t de_size = decrypt(pri_key, encrypted_msg, en_size, &decrypted_msg);
    printf("decrypted message:");
    printf_msg(decrypted_msg, de_size);

    printf(">");
    free(encrypted_msg);
    free(decrypted_msg);
  }

  rsa_key_free(pri_key);
  rsa_key_free(pub_key);
}