To simulate the RSA algorithm in C using a robust command-line application written in C.
Taking values of e=7, p=3 and q=11 works fine when encrypting and decrypting. However, when I veer slightly off to use other values for e, p and q there is a high degree of inconsistency for the generated cipher and when I decode it. There was an instance where the cipher was a negative value. :-(
#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);
}
I have been pondering on this for a week but each time I look up for research and improve the implementation, it always fails.
I recently looked at www.cs.drexel.edu and made an adjustment to struct RSACfg so that long d can be coded at runtime.
Compilation:
~$ gcc mod.c -lm
Running: Case encrypting plain 28
~$ ./a.out -E 28
is the same as (default)
~$ ./a.out -e7 -p3 -q11 -E 28
and produces the output:
Encrypting with pub key(33,7)
Encryption
m: 28
Result(M): 19
When we replace -E (encryption) with -D (decryption) and the argument 28 with 19, we get
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
Note that setting -d X requires that -p, -q and -e are passed on (which are should all be set when any of them is set)
~$ ./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 # This should be 4 and not -1156009
Overflow
((long)pow(m, r->e)) % (r->p * r->q) risks integer overflow with r->p * r->q, (long)pow(m, r->e) risks precision lost and converting a double that is out-of-range for a long.
(long)pow(M, d)) % (*p * (*q) is likewise at risk.
Various places where code uses * also risk overflow.
To solve:
For *, use a 2x as wide math. e.g. r->p * r->q --> 1LL * r->p * r->q.
If long is 32-bits, long long, which is at least 64-bit, will suffice.
ab mod c is trickier and may need advanced code like this.