RSA c implementation

Question

This is my first attempt to implement a crypto algorithm.

I am using C and gmp to interact with big numbers.

I am basing my implementation of the RSA algorithm from the book "A handbook of applied cryptography" (chapter 8.2) :

• Take two distinct, large primes p and q
  • Ideally these have a similar byte-length
• Multiply p and q and store the result in n
• Find the totient for n using the formula $$\varphi(n)=(p-1)(q-1)$$
• Take an e coprime that is greater, than 1 and less than n
• Find d using the formula $$d\cdot e\equiv1\mod\varphi(n)$$

At this point, the pair (e, n) is the public key and the private key (d, n) is the private key.

Here is my code; you can run it after having linked with the -lgmp parameter:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <math.h>
#include <sys/types.h>
#include "gmp.h"



void generatePrimes(mpz_t* p, mpz_t* q);
void computeNandF(mpz_t* q, mpz_t* p, mpz_t *phi, mpz_t* n);
void generateE(mpz_t* phi, mpz_t* e);
void enc(mpz_t* e, mpz_t* n, mpz_t* d, mpz_t* c, char[]);
void dec(mpz_t* m, mpz_t* c, mpz_t* d, mpz_t* n);
void makeKeys(mpz_t n, mpz_t e, mpz_t d, mpz_t p, mpz_t q);
void encrFile(mpz_t e, mpz_t n, mpz_t d, mpz_t c);

gmp_randstate_t stat;

int main() {


 mpz_t p, q, phi, e, n, d, c, dc;
 char msg[40] = "welcome to cryptoworld";
 int *mes;
 int len = strlen(msg);
 mpz_init(p);
 mpz_init(q);
 mpz_init(phi);
 mpz_init(e);
 mpz_init(n);
 mpz_init(d);
 mpz_init(c);
 mpz_init(dc);

 // RSA algorithm
 generatePrimes(&p, &q);
 computeNandF(&q, &p, &phi, &n);
 generateE(&phi, &e);
 // extended Euclidean
 mpz_invert(d, e, phi);
 printf("d = ");
 mpz_out_str(stdout, 10, d);
 printf("\n------------------------------------------------------------------------------------------\n");


 enc(&e, &n, &d, &c, msg);

 dec(&dc, &c, &d, &n);

 printf("\n------------------------------------------------------------------------------------------\n");
 printf("encrypt message  = ");
 mpz_out_str(stdout, 10, c);
 printf("\n");
 printf("\n------------------------------------------------------------------------------------------\n");
 printf("message as int after decr  = ");
 mpz_out_str(stdout, 10, dc);
 printf("\n");


 mpz_export(mes, (size_t*) malloc(sizeof (size_t)), 1, sizeof (mes[0]), 0, 0, dc);
 char r[40];
 printf("message as string after decr  = ");
 for (int i = 0; i < len; i++) {
     r[i] = (char) mes[i];
     printf("%c", r[i]);
 }
 printf("\n");

 encrFile(e, n, d, c);

 mpz_clear(p);
 mpz_clear(q);
 mpz_clear(phi);
 mpz_clear(n);
 mpz_clear(e);
 mpz_clear(c);
 mpz_clear(d);
 mpz_clear(dc);
 return 0;
}

void generatePrimes(mpz_t* p, mpz_t* q) {

 int primetest;
 long sd = 0;
 mpz_t seed;
 gmp_randinit(stat, GMP_RAND_ALG_LC, 120);
 mpz_init(seed);
 srand((unsigned) getpid());
 sd = rand();
 mpz_set_ui(seed, sd);
 gmp_randseed(stat, seed);


 mpz_urandomb(*p, stat, 512);
 primetest = mpz_probab_prime_p(*p, 10);
 if (primetest != 0) {
    printf("p is prime\n");
 } else {
    //printf("p wasnt prime,choose next prime\n");
    mpz_nextprime(*p, *p);
 }

 mpz_urandomb(*q, stat, 512);
 primetest = mpz_probab_prime_p(*q, 10);
 if (primetest != 0) {
    // printf("q is prime\n");
 } else {
    // printf("p wasnt prime,choose next prime\n");
    mpz_nextprime(*q, *q);
 }


 printf("p and q generated!!\n");
 printf("p = ");
 mpz_out_str(stdout, 10, *p);
 printf("q = ");
 mpz_out_str(stdout, 10, *q);
 printf("\n------------------------------------------------------------------------------------------\n");
 mpz_clear(seed);
 return;
}

void computeNandF(mpz_t* q, mpz_t* p, mpz_t *phi, mpz_t* n) {

 mpz_t temp1, temp2;
 mpz_init(temp1);
 mpz_init(temp2);
 //n=p*q
 mpz_mul(*n, *q, *p);
 mpz_sub_ui(temp1, *q, 1); //temp1=q-1
 mpz_sub_ui(temp2, *p, 1); //temp2=p-1
 //φ=(p-1)(q-1)
 mpz_mul(*phi, temp1, temp2);
 printf("phi and n generated!!\n");
 printf(" n= ");
 mpz_out_str(stdout, 10, *n);
 printf("phi = ");
 mpz_out_str(stdout, 10, *phi);
 printf("\n------------------------------------------------------------------------------------------\n");
}

void generateE(mpz_t* phi, mpz_t* e) {

 mpz_t temp, seed;
 mpz_init(seed);
 mpz_init(temp);
 long sd = 0;
 gmp_randinit(stat, GMP_RAND_ALG_LC, 120);
 srand((unsigned) getpid());
 sd = rand();
 mpz_set_ui(seed, sd);
 gmp_randseed(stat, seed);

 do {
    mpz_urandomm(*e, stat, *phi + 1);
    mpz_gcd(temp, *phi, *e); //temp=gcd(e,φ)
 } while (mpz_cmp_ui(temp, 1) != 0); //while gcd!=1
 printf("e generated \n e = ");
 mpz_out_str(stdout, 10, *e);
 printf("\n------------------------------------------------------------------------------------------\n");

 }

void enc(mpz_t* e, mpz_t* n, mpz_t* d, mpz_t* c, char msg[]) {

 int r[40];
 for (int i = 0; i < strlen(msg); i++) {
    r[i] = (int) msg[i];
 }

 int *m = r;
 mpz_t M;
 mpz_init(M);
 mpz_import(M, strlen(msg), 1, sizeof (m[0]), 0, 0, m);
 printf("message as int before encryption  = ");
 mpz_out_str(stdout, 10, M);
 printf("\n");

 mpz_powm(*c, M, *e, *n);

}

void dec(mpz_t* m, mpz_t* c, mpz_t* d, mpz_t* n) {

  mpz_powm(*m, *c, *d, *n);

}

void encrFile(mpz_t e, mpz_t n, mpz_t d, mpz_t c) {

  char text[80];
  FILE *file;
  file = fopen("text.txt", "r");
  int i = 0;
  if (file) {
     while ((x = getc(file)) != EOF) {
         i++;
         putchar(x);
         text[i] = (char) x;
     }
   
    int r[40];
    for (int i = 0; i < strlen(text); i++) {
        r[i] = (int) text[i];
    }

    int *m = r;
    mpz_t M;
    mpz_init(M);
    mpz_import(M, strlen(text), 1, sizeof (m[0]), 0, 0, m);
    printf("message as int before encryption  = ");
    mpz_out_str(stdout, 10, M);
    printf("\n");
  
    mpz_powm(c, M, e, n);
    printf("encrypt txt  = ");
    mpz_out_str(stdout, 10, c);
    printf("\n");
 
    fclose(file);
    file = fopen("text.txt", "w");
  
    mpz_out_raw(file, c);
    fclose(file);

  }

}

Any comments and improvements in my implementation will be appreciated.

Answer 1

Indicate your locals

Since all of your functions are in the same translation unit, make them static.

Passing by reference

Some of your mpz_t are explicitly passed by reference, i.e.

void generatePrimes(mpz_t* p, mpz_t* q);

and some appear initially to be passed by value:

void encrFile(mpz_t e, mpz_t n, mpz_t d, mpz_t c);

These structures are defined here:

typedef struct
{
  int _mp_alloc;        /* Number of *limbs* allocated and pointed
                   to by the _mp_d field.  */
  int _mp_size;         /* abs(_mp_size) is the number of limbs the
                   last field points to.  If _mp_size is
                   negative this is a negative number.  */
  mp_limb_t *_mp_d;     /* Pointer to the limbs.  */
} __mpz_struct;

typedef __mpz_struct mpz_t[1];

Confusingly, even if you don't add a *, you will be passing by reference, because mpz_t is defined as an array. As such, you should be dropping the pointer notation everywhere.

You really do need to mark const the pointer arguments that you don't change, especially since everything is being passed by reference.

Naming arguments

Function prototypes aren't just to predeclare a function to sort out order dependency. They're also documentation for developers. As such, your unnamed char[] argument here:

void enc(mpz_t* e, mpz_t* n, mpz_t* d, mpz_t* c, char[]);

needs to be named.

Variable names

I realize that many of these variable names are defined by your book, but that doesn't help other developers (or you in the future). At the absolute least, write a comment beside every variable that you declare describing what it is and how it's used. If possible, upgrade variable names from cryptic single letters to actual words.

Error checking

All system calls, e.g. to fopen, might fail and need to be checked. This:

FILE *file;
file = fopen("text.txt", "r");
if (file) {

silently ignores failures to open the file, which is bad. You need to do something meaningful - in this case, perhaps perror("Failed to open crypto file"); exit(1);

Combine declaration and initialization

This:

FILE *file;
file = fopen("text.txt", "r");

should be

FILE *file = fopen("text.txt", "r");

Avoid overflows

This segment of code:

char text[80];
FILE *file;
file = fopen("text.txt", "r");
int i = 0;
if (file) {
    while ((x = getc(file)) != EOF) {
        i++;
        putchar(x);
        text[i] = (char) x;
    }

    int r[40];
    for (int i = 0; i < strlen(text); i++) {
        r[i] = (int) text[i];
    }

is begging for an overflow error in a handful of ways. You have a fixed-length text array to which you write file contents with no length check other than EOF. You also have an r array whose initialization loop ignores its length and relies on strlen - but you haven't null-terminated your text string!

Instead,

1. Get the length of the file.
2. Don't even bother with initializing a character array; skip to initializing your int array.
3. Dynamically allocate the array with malloc based on the size of the file.
4. Read into the array until it's full.

Don't use printf unless you have to

This:

printf("message as int before encryption  = ");

doesn't do any formatting, so use puts instead, which is more efficient.

Make your file I/O functions more flexible

Don't hardcode the file name text.txt. Instead, accept that as an argument to the function. Get it from user input or a command-line argument.

Answer 2

Invalid code

In while ((x = getc(file)) != EOF), where is x defined? ¹

error: 'x' undeclared (first use in this function)

Use of uninitialized object

The pointer mes is passed to mpz_export() without initialization/assignment.

int *mes;
...
// Garbage value pass to  `mpz_export(void *rop, ...)`
mpz_export(mes, (size_t*) malloc(sizeof(size_t)), 1, sizeof(mes[0]), 0, 0,
...
r[i] = (char) mes[i];

The compiler warning hinted to this problem. This implies code is not using a good compiler will all warnings enabled. Save time. Enable then all.

warning: 'mes' may be used uninitialized in this function [-Wmaybe-uninitialized]

I suspect the following will fix

//int *mes;
//int len = strlen(msg);
int len = strlen(msg);
int mes[len + !len]; // Insure VLA is at least size 1

// Unsure about mpz_export() repair needs.
// mpz_export(mes, (size_t*) malloc(sizeof(size_t)), 1, sizeof(mes[0]), 0, 0, dc);
mpz_export(   mes,           malloc(sizeof(size_t)), 1, sizeof mes    , 0, 0, dc);

Passing by reference cheat

The mpz library cheats.

typedef __mpz_struct mpz_t[1]; defines mpz_t as an array of 1.

Consider the following:

extern void foo(mpz_t arg1);
mpz_t a;
foo(a);

In common C, one would not expect a to be modified by foo() as C is pass by value . Yet since a is an array of __mpz_struct, a is converted from its value as an array to the addresses of a[0]. It is that address that is passed by value to foo. Now foo() can change the caller's a.

To prevent/allow changing mpz_t augments, the mpz library uses const.

//       can change,     can't change,    can't change,    can't change
mpz_powm (mpz_t rop, const mpz_t base, const mpz_t exp, const mpz_t mod)

But what should OP's function do? Take advantage of the hidden "call-by-reference"?

Consider OP's dec()

void dec(mpz_t* m, mpz_t* c, mpz_t* d, mpz_t* n) {
  mpz_powm(*m, *c, *d, *n);
}

This should use const to indicate which may change.

void dec_alt1(mpz_t* m, const mpz_t* c, const mpz_t* d, const mpz_t* n) {
  mpz_powm(*m, *c, *d, *n);
}

It is quite unnecessary to pass 4 mpz_t* pointers. Code could have been the following which is also passing 4 pointers.

void dec_alt2(mpz_t m, const mpz_t c, const mpz_t d, const mpz_t n) {
  mpz_powm(m, c, d, n);
}

Alternatively, code could avoided the hidden "pass-by-reference":

void dec_alt3(mpz_t *m, const mpz_t c, const mpz_t d, const mpz_t n) {
  mpz_powm(*m, c, d, n);
}

Avoid casual sign changes

Code could have easily called mpz_set_si (mpz_t rop, signed long int op) rather than mpz_set_ui (mpz_t rop, unsigned long int op) and avoided a warning:

warning: 
conversion to 'long unsigned int' from 'long int' may change the sign of the result [-Wsign-conversion]

This implies the compilation was not done with -Wsign-conversion or its equivalent.

Casual sign-ness changes are a source of bugs. Save time and enable the warning to help weed code of causal changes. There are at least 4 in OP's code.

long sd = 0;
sd = rand();
// mpz_set_ui(seed, sd);
mpz_set_si(seed, sd);

---

¹ This error makes code not compilable, one of the reasons for closing the question. Let us count this as a copy/paste error. Still, better to be certain that the code posted compiles, not just the code on your computer.