RSA implementation in C

Question

I'm trying to implement the RSA algorithm in C for a project.

I can generate the desired encryption/decryption keys, but I can't seem to perform the encryption/decryption correctly. The error seems to lie in how i calculate the encrypted message. The maths for it is m^e mod n where m is the message, e is the encryption exponent and n is the modulus for the public key and the private keys. I calculate m^e using pow() function and calculate mod n using both fmod() function and as %n. neither seem to work(give the correct output).

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

int p1,p2,mod,tot, encExp, decExp, conRelVal;
// Function to check if numbers given are primes
// @param pr: the number being tested
int prime(long int pr){
  int i;
  int j;
  j = sqrt(pr);
  for(i = 2; i <= j; i++){
   if(pr % i == 0)
     return 0;
  }
  return 1;
}

int gcd(int a, int h) 
{ 
    int temp; 
    while (1) 
    { 
        temp = a%h; 
        if (temp == 0) 
          return h; 
        a = h; 
        h = temp; 
    } 
} 

//function to generate encryption key
void encryption_key(){
  p1 = 61;
  p2 = 53;
  conRelVal = 15;
  mod = p1*p2;
  tot = (p1-1)*(p2-1);
  encExp = 12;
  while (encExp < tot){ 
        // e must be co-prime to the totient and 
        // smaller than the totient. 
        if (gcd(encExp,tot)==1) 
            break; 
        else
            encExp++; 
  } 

  decExp = ((1+(conRelVal*tot))/encExp);

printf("p1=%d\np2=%d\nmod=%d\ntot=%d\ne=%d\nd=%d\nconst=%d\n",p1,p2,mod,tot, encExp, decExp, conRelVal);
  printf("Public Key:\t(%d,%d)", mod,encExp);
  printf("\nPrivate Key:\t(%d,%d)", mod,decExp);
}

double encrypt(int msg){
  // Encryption c = (msg ^ e) % n 
  double l;
  l = pow(msg, encExp);
  int j;
  j = ((int)l%mod);
  l = fmod(l, mod);
  printf("\nMessage:\t%d\nEncrypted:\t%lf",msg,l);
  printf("\nMessage:\t%d\nEncrypted:\t%d",msg,j);
  return l;
}

void decrypt(double cyp){
  // Decryption m = (c ^ d) % n 
  double m ;
  m = pow(cyp, decExp);
  int z = ((int)m%mod);     
  m = fmod(m, mod); 
  printf("\nEncrypted:\t%lf\nDecrypted:\t%lf",cyp,m);
  printf("\nEncrypted:\t%lf\nDecrypted:\t%d",cyp,z);
}

int main() { 
  encryption_key();
  int msg = 123;
  double cyp = encrypt(msg);
  decrypt(cyp);
  return 0;
}

Results:  

  $ ./test
p1=61
p2=53
mod=3233
tot=3120
e=17
d=2753
const=15
Public Key:     (3233,17)
Private Key:    (3233,2753)
Message:        123
Encrypted:      992.000000
Message:        123
Encrypted:      -2194
Encrypted:      992.000000
Decrypted:      nan
Encrypted:      992.000000
Decrypted:      -2194

I'd expect Encrypted to be 855 and Decrypted to be 123

Answer 1

As stated above, you can't store large numbers in C datatype. A work around would be to use gmp. Here is the code that will work with your exercice. Discard the first part of the code, it is simply cracking the private exponent assuming modulo factorization was done. Go to /* encryption function */ I guess it is ugly...

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <gmp.h>

int main(void)
{
        /* data */
        int p = 61;
        int q = 53;
        size_t e = 17; /* public exponent */
        size_t d;      /* private exponent not given */
        int msg = 123; /* message to be encrypted */
        printf("==============\n");
        printf("DATA\n");
        printf("==============\n");
        printf("int p = %d\n", p);
        printf("int q = %d\n", q);
        printf("int e = %ld\n", e);
        printf("int msg = %d\n\n", msg);

        /* compute modulo n */
        int n = p*q;
        printf("=========================\n");
        printf("1 - Compute n = p * q\n");
        printf("=========================\n");
        printf("n = %d\n\n", n);

        /* compute totient Euler function */
        printf("==========================================================\n");
        printf("2 - Compute totient Euler function phi(n) = (p-1)(q-1)\n");
        printf("==========================================================\n");
        int phi = (p-1) * (q-1);
        printf("totient = %d\n\n", phi);

        /* compute d private exponent */
        printf("==========================================================\n");
        printf("3 - Compute d private exponent d*e mod(phi(n)) = 1\n");
        printf("==========================================================\n");

        for (d = 1; d < ULONG_MAX; d++) {
                int tmp = (d * e)%phi;
                if (tmp == 1) {
                        printf("d is FOUND: %ld\n\n", d);
                        break;
                }
        }

        /* encryption function */
        printf("==========================================================\n");
        printf("4 - ENCRYPTION of message 123 --> enc_msg = m^e mod(n)\n");
        printf("==========================================================\n");
        printf("modulo n = %d\n", n);

        /* we are using gmp to be able to compute very large numbers */
        mpz_t me;      /* message^pub_exp */
        mpz_t enc_msg; /* encrypted message */
        mpz_t modn;    /* modulo n previously computed "3233" */
        mpz_inits(me, enc_msg, modn);
        mpz_set_str(modn, "3233", 10); /* 10 means decimal number */

        mpz_ui_pow_ui(me, msg, e);  /* compute m^e */
        mpz_mod(enc_msg, me, modn); /* compute m^e mod(n) */

        printf("message^e mod(n) = ");
        mpz_out_str(NULL, 10, enc_msg);
        printf("\n\n");


        /* decryption function */
        printf("=============================================================\n");
        printf("5 - DECRYPTION of enc_msg 855 --> dec_msg = enc_msg^d mod(n)\n");
        printf("=============================================================\n");
        printf("modulo n = %d\n", n);

        int enc_message = 855; /* previously computed */
        mpz_t md;              /* enc_message^priv_exp */
        mpz_t dec_msg;         /* decrypted message */
        mpz_inits(md, dec_msg, modn);
        mpz_set_str(modn, "3233", 10);

        mpz_ui_pow_ui(md, enc_message, d);  /* compute enc_message^d */
        mpz_mod(dec_msg, md, modn); /* compute enc_msg^d mod(n) */

        printf("dec_msg^d mod(n) = ");
        mpz_out_str(NULL, 10, dec_msg);
        printf("\n\n");

        /* free */
        mpz_clear(me);
        mpz_clear(md);
        mpz_clear(modn);
        mpz_clear(enc_msg);
        mpz_clear(dec_msg);

        return 0;
}

Answer 2

usually, programming languages has limit over how much you can store in variables. whenever you try to assign a value larger than it can store, it will wrap/round back to minimum value and start counting again.

it is a little bit hard for me to explain it here. in short what i am trying to say is, your calculations might come out unexpectedly wrong as variables has capacity on how much big value you can store in it. so make sure that there are no overflows and calculations are correct. if calculations come out wrong then your output would be obviously incorrect.