Malc0de CyberNet
Fulfill your daily dose of Security & Tech News.

Understanding RSA Encryption and Algorithm with Example

Learn How RSA Encryption works, its algorithm with example.

0 521

In my last few tutorials, I have written about Cryptography, Types of Cryptography, What are the Security Goals and Different types of Attacks etc. In another article, I gave a detailed Introduction to Public Key Cryptography. Today, we will continue our discussion with RSA encryption and how RSA algorithm works.

But before we proceed further, make sure you’re familiar with the most common cryptography terminology.

Previously, we discussed, PKC depends upon the existence of so-called one-way functions, or mathematical functions that are easy to compute whereas their inverse function is relatively difficult to compute. Public Key is used to Encrypt the data and can be distributed among worldwide but Private Key must be kept secret and it is used to decrypt the cipher text or encrypted data. There are many PKC algorithms, a few notable are as follows:

  1. RSA
  2. Diffie-Hellman
  3. Digital Signature Algorithm(DSA)
  4. Elliptic Curve Cryptography (ECC)
  5. ElGamal

However, we are particularly interested in RSA, which is perhaps the most widely used RSA algorithms and is used in SSL, SSH, Digital Signatures etc.

Understanding RSA Encryption

The first, and still most common, PKC implementation, named for the three MIT mathematicians who developed it — Ronald Rivest, Adi Shamir, and Leonard Adleman. RSA today is used in hundreds of software products and can be used for key exchange, digital signatures, or encryption of small blocks of data.

RSA uses a variable size encryption block and a variable size key. The key-pair is derived from a very large number, n, that is the product of two prime numbers chosen according to special rules; these primes may be 100 or more digits in length each, yielding an n with roughly twice as many digits as the prime factors.

The public key information includes n and a derivative of one of the factors of n; an attacker cannot determine the prime factors of n (and, therefore, the private key) from this information alone and that is what makes the RSA algorithm so secure.

RSA Algorithm

To generate the encryption and decryption keys, we can proceed as follows.

1. Generate randomly two “large” primes ‘p’ and ‘q’.

2. Compute ‘n’ = p * q and ‘φ’ = (p − 1)*(q − 1).

3. Choose a number ‘e’ so that gcd(e, φ) = 1.

4. Find the multiplicative inverse of ‘e’ modulo ‘φ’, i.e., find d so that e * d ≡ 1 (mod φ). This can be done efficiently using Euclid’s Extended Algorithm.

The Encryption Public Key is KE = (n, e) and the Decryption Private Key is KD = (n, d).The encryption function is :- E(M ) = M ^ e mod n. 

The decryption function is :- D(M ) = M ^ d mod n.
These functions satisfy D(E(M )) = M and E(D(M )) = M, for any 0 ≤ M < n. 

Let’s take an example which will clear the facts:

P = 61 <- first prime number (destroy this after computing E and D)
Q = 53 <- second prime number (destroy this after computing E and D)
PQ = 3233 <- modulus (give this to others)
E = 17 <- public exponent (give this to others)
D = 2753 <- private exponent (keep this secret!)
Your public key is (E, PQ). Your private key is D.
The encryption function is: encrypt(T) = (T^E) mod PQ = (T^17) mod 3233
The decryption function is: decrypt(C) = (C^D) mod PQ= (C^2753) mod 3233
To encrypt the plaintext value 123, we do this:
encrypt(123) = (123^17) mod 3233 = 337587917446653715596592958817679803 mod 3233 = 855
To decrypt the ciphertext value 855, we do this:
decrypt(855) = (855^2753) mod 3233 = 123
One way to compute the value of 855^2753 mod 3233 is like this:
2753 = 101011000001 base 2,

Therefore, 2753 = 1 + 2^6 + 2^7 + 2^9 + 2^11= 1 + 64 + 128 + 512 + 2048

Consider this table of powers of 855:

855^1 = 855 (mod 3233)
855^2 = 367 (mod 3233)
855^4 = 367^2 (mod 3233) = 2136 (mod 3233)
855^8 = 2136^2 (mod 3233) = 733 (mod 3233)
855^16 = 733^2 (mod 3233) = 611 (mod 3233)
855^32 = 611^2 (mod 3233) = 1526 (mod 3233)
855^64 = 1526^2 (mod 3233) = 916 (mod 3233)
855^128 = 916^2 (mod 3233) = 1709 (mod 3233)
855^256 = 1709^2 (mod 3233) = 1282 (mod 3233)
855^512 = 1282^2 (mod 3233) = 1160 (mod 3233)
855^1024 = 1160^2 (mod 3233) = 672 (mod 3233)
855^2048 = 672^2 (mod 3233) = 2197 (mod 3233)

Given the above, we can do like this:

855^2753 (mod 3233)
= 855^(1 + 64 + 128 + 512 + 2048) (mod 3233)
= {(855^1) * (855^64) * (855^128) * (855^512) * (855^2048)} (mod 3233)
= 855 * 916 * 1709 * 1160 * 2197 (mod 3233)
= 794 * 1709 * 1160 * 2197 (mod 3233)
= 2319 * 1160 * 2197 (mod 3233)
= 184 * 2197 (mod 3233)
= 123 (mod 3233)
= 123

So, that;s pretty much it. The above Mathematical derivation and example have been taken from this research paper. If you liked this article please subscribe to our Newsletter and share this with others and on social media.

 

Source GaryKessler

Leave A Reply

Your email address will not be published.