# RSA Algorithm in Cryptography

RSA algorithm is asymmetric cryptography algorithm. Asymmetric actually means that it works on two different keys i.e. **Public Key** and **Private Key.** As the name describes that the Public Key is given to everyone and Private key is kept private.

**An example of asymmetric cryptography :**

Attention reader! Don’t stop learning now. Get hold of all the important CS Theory concepts for SDE interviews with the **CS Theory Course** at a student-friendly price and become industry ready.

- A client (for example browser) sends its public key to the server and requests for some data.
- The server encrypts the data using client’s public key and sends the encrypted data.
- Client receives this data and decrypts it.

Since this is asymmetric, nobody else except browser can decrypt the data even if a third party has public key of browser.

**The idea!** The idea of RSA is based on the fact that it is difficult to factorize a large integer. The public key consists of two numbers where one number is multiplication of two large prime numbers. And private key is also derived from the same two prime numbers. So if somebody can factorize the large number, the private key is compromised. Therefore encryption strength totally lies on the key size and if we double or triple the key size, the strength of encryption increases exponentially. RSA keys can be typically 1024 or 2048 bits long, but experts believe that 1024 bit keys could be broken in the near future. But till now it seems to be an infeasible task.

**Let us learn the mechanism behind RSA algorithm :**

**>> Generating Public Key :**

**P = 53 and Q = 59**. Now First part of the Public key :

**n = P*Q = 3127**.

**e**: But e Must be

- An integer.
- Not be a factor of n.
**1 < e < Φ(n)**[Φ(n) is discussed below], Let us now consider it to be equal to 3.

**>> Generating Private Key :**

**Φ(n) = (P-1)(Q-1)**so, Φ(n) = 3016

**d**:

**d = (k*Φ(n) + 1) / e**for some integer k For k = 2, value of d is 2011.

Now we are ready with our – Public Key ( n = 3127 and e = 3) and Private Key(d = 2011)

Now we will encrypt **“HI”** :

**Encrypted Data c = 89**. Thus our Encrypted Data comes out to be 1394 Now we will decrypt

^{e}mod n**1394**:

**Decrypted Data = c**. Thus our Encrypted Data comes out to be 89

^{d}mod n**8 = H and I = 9 i.e. "HI".**

**Below is C implementation of RSA algorithm for small values:**

`// C program for RSA asymmetric cryptographic` `// algorithm. For demonstration values are` `// relatively small compared to practical` `// application` `#include<stdio.h>` `#include<math.h>` ` ` `// Returns gcd of a and b` `int` `gcd(` `int` `a, ` `int` `h)` `{` ` ` `int` `temp;` ` ` `while` `(1)` ` ` `{` ` ` `temp = a%h;` ` ` `if` `(temp == 0)` ` ` `return` `h;` ` ` `a = h;` ` ` `h = temp;` ` ` `}` `}` ` ` `// Code to demonstrate RSA algorithm` `int` `main()` `{` ` ` `// Two random prime numbers` ` ` `double` `p = 3;` ` ` `double` `q = 7;` ` ` ` ` `// First part of public key:` ` ` `double` `n = p*q;` ` ` ` ` `// Finding other part of public key.` ` ` `// e stands for encrypt` ` ` `double` `e = 2;` ` ` `double` `phi = (p-1)*(q-1);` ` ` `while` `(e < phi)` ` ` `{` ` ` `// e must be co-prime to phi and` ` ` `// smaller than phi.` ` ` `if` `(gcd(e, phi)==1)` ` ` `break` `;` ` ` `else` ` ` `e++;` ` ` `}` ` ` ` ` `// Private key (d stands for decrypt)` ` ` `// choosing d such that it satisfies` ` ` `// d*e = 1 + k * totient` ` ` `int` `k = 2; ` `// A constant value` ` ` `double` `d = (1 + (k*phi))/e;` ` ` ` ` `// Message to be encrypted` ` ` `double` `msg = 20;` ` ` ` ` `printf` `(` `"Message data = %lf"` `, msg);` ` ` ` ` `// Encryption c = (msg ^ e) % n` ` ` `double` `c = ` `pow` `(msg, e);` ` ` `c = ` `fmod` `(c, n);` ` ` `printf` `(` `"\nEncrypted data = %lf"` `, c);` ` ` ` ` `// Decryption m = (c ^ d) % n` ` ` `double` `m = ` `pow` `(c, d);` ` ` `m = ` `fmod` `(m, n);` ` ` `printf` `(` `"\nOriginal Message Sent = %lf"` `, m);` ` ` ` ` `return` `0;` `}` `// This code is contributed by Akash Sharan.` |

Output :

Message data = 12.000000 Encrypted data = 3.000000 Original Message Sent = 12.000000

This article is contributed by **Mohit Gupta_OMG 🙂**. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.