Program to implement RSA algorithm in C

Today we will write a program to implement RSA algorithm in C programming language, so let’s first understand what is RSA algorithm.

What is RSA Algorithm?

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977.

Example of RSA Algorithm:

  • Choose p = 3 and q = 11
  • Compute n = p * q = 3 * 11 = 33
  • Compute φ(n) = (p – 1) * (q – 1) = 2 * 10 = 20
  • Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
  • Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
  • Public key is (e, n) => (7, 33)
  • Private key is (d, n) => (3, 33)
  • The encryption of m = 2 is c = 27 % 33 = 29
  • The decryption of c = 29 is m = 293 % 33 = 2

 

Program to implement RSA Algorithm in C:

 

Sample Output:

 

Comments

  1. RobbieTheK says:

    gcc rsa4.cpp
    rsa4.cpp: In function ‘int main()’:
    rsa4.cpp:34:18: warning: NULL used in arithmetic [-Wpointer-arith]
    for(i=0;msg[i]!=NULL;i++)
    ^~~~
    /tmp/ccn55de1.o: In function __gnu_cxx::__enable_if<std::__is_integer::__value, double>::__type std::sqrt(long)':
    rsa4.cpp:(.text._ZSt4sqrtIlEN9__gnu_cxx11__enable_ifIXsrSt12__is_integerIT_E7__valueEdE6__typeES3_[_ZSt4sqrtIlEN9__gnu_cxx11__enable_ifIXsrSt12__is_integerIT_E7__valueEdE6__typeES3_]+0x13): undefined reference to
    sqrt’
    collect2: error: ld returned 1 exit status

    • add “using namespace std;” under the includes, or add “std::” before the sqrt function: you need to specify that sqrt is part of the standard (std) library!