Skip to content

Instantly share code, notes, and snippets.

@LeeReindeer
Last active May 20, 2018 08:28
Show Gist options
  • Save LeeReindeer/571c1ca6b0060308f572a58de7eb78d4 to your computer and use it in GitHub Desktop.
Save LeeReindeer/571c1ca6b0060308f572a58de7eb78d4 to your computer and use it in GitHub Desktop.
Simple RSA Algorithm implement in 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment