title: RSA implementation in C
body: <p>I'm trying to implement the RSA algorithm in C for a project.</p>
  
  <p>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).</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;math.h&gt;
  #include&lt;string.h&gt;
  
  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 &lt;= 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 &lt; 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
  </code></pre>
  
  <p>I'd expect Encrypted to be 855
  and Decrypted to be 123</p>