RSA Algorithm

RSA Algorithm

RSA stands for Rivest, Shamir, Adleman. It is a public key encryption technique used for secure data transmission especially over the internet.

It makes use of prime numbers and the factoring problem.
It is a reliable yet slow algorithm for data encryption/ decryption.
It is an Asymmetric Cryptographic Algorithm

Two Keys

  1. Public Key
  2. Private Key

Public key: It comprises two numbers, in which one number is the result of the product of two large prime numbers. This key is provided to all the users.
Private key: It is derived from the two prime numbers involved in public key and it always remains private.

If public key of users is used for encryption then we have to use the private key of same user for decryption. The RSA Scheme is a block cipher in which the plain text and cipher text are integers between 0 and (n-1) for the same value n.

The RSA algorithm involves four steps for data transmission which are as follows:

  1. Key Generation
  2. Key distribution
  3. Encryption
  4. Decryption

Key Generation

  1. Select 2 large prime numbers p & q
  2. Calculate n=p*q
  3. Calculate φ(n) = (p-1)(q-1)
  4. Choose value of e => 1 < e < φ(n) and GCD(e, φ(n))=1
  5. Calculate d = e pow 1 mod φ(n) => ie. ed = 1 * mod φ(n)
  6. Public Key = {e, n}
  7. Private Key = {d, n}

Formula for Finding the Encryption Text

To find cipher text C = (Message)^e mod n

C = M^e mod n

Formula for Finding the Decryption Text

To find the Message M = (Cipher Text)^d mod n

M = C^d mod n

Example 1:

RSA Algorithm is used by choosing 2 prime numbers p=3, q=11 and public key e=7. calculate the value of d. Also find the encryption and decryption key.

Let p=3, q=11, e=7

n=p*q = 3*11 = 33

φ(n)=(p-1)(q-1) = (3-1)(11-1)

= (2)(10)

= 20

so, let e=7, as 1<7<20 and gcd(20,7)=1

Now, ed = 1*mod φ(n)

ed mod φ(n) = 1

7*d mod 20 = 1

if d=3, then 21 mod 20 = 1

e=7, d=3, n=33

Public key = {e, n} = {7,33}

Private Key = {d, n} = {3,33}

FOR ENCRYPTION TEXT

To find cipher text(Encryption Text) C = pow(M,e) mod n

C = M^e mod n Where M is message(raw text/plain text)

Let M=31, e=7 then Encryption Text C = pow(31,7) mod 33

= 31^7 mod 33

(7 times multiplication of 31 => 31*31*31*31*31*31*31)

= 27512614111 mod 33

= 4

FOR DECRYPTION TEXT

To find the Message M = pow(C, d) mod n

M = C^d mod n Where C is Cipher Text(Encrypted)

Let C=4, d=3, then Decryption Text M = pow(4, 3) mod 33

= 4^3 mod 33

= 64 mod 33

Decryption Text M = 31

Advantages of RSA

  • Easy to implement RSA algorithm.
  • Safe and secure for transmitting the sensitive data
  • Sharing public key to users is easy.
  • Cracking RSA algorithm is very difficult as it involves complex mathematics.

Disadvantages of RSA

  • Sometimes a third party is needed to confirm the validity of public keys.
  • For public data encryption, such as electoral voting, RSA cannot be utilized.
  • Decryption requires a large amount of processing power on the receiver’s end.
  • It may fail sometimes because for complete encryption both symmetric and asymmetric encryption is required and RSA uses asymmetric encryption only.
  • It has slow data transfer rate due to large numbers involved.
Leave a Reply 0

Your email address will not be published. Required fields are marked *