## Sunday, 20 March 2016

### RSA Alogorithm

The RSA algorithm is an example of asymmetric cryptography, which is widely used in worldwide for securing sensitive while sending insecure medium like the internet.

RSA was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. Two types of keys are used, public and private. Private is secrete key used by the owner or receiver. Data can be encrypted using a public or private key, but decryption can be done only with the private key.

The RSA algorithm is fully based on mathematical process, steps are followed

1. Represent the message as an integer between 0 and (n-1). Large messages can be broken up into a number of blocks. Each block would then be represented by an integer in the same range.
2. Encrypt the message by raising it to the eth power modulo n. The result is a ciphertext message C.
3. To decrypt ciphertext message C, raise it to another power d modulo n

The encryption key (e,n) is made public. The decryption key (d,n) is kept private by the user.

#### How to Determine Appropriate Values for e, d, and n

• Choose two very large (100+ digit) prime numbers. Denote these numbers as p and q.
• Set n equal to p * q.
• Choose any large integer, d, such that GCD(d, ((p-1) * (q-1))) = 1
• Find e such that e * d = 1 (mod ((p-1) * (q-1)))

## Example :

Choose p = 7 and q = 13
Compute n = p * q = 7* 13 = 91
Compute φ(n) = (p - 1) * (q - 1) = 6* 12 = 72
Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 11
Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 7 [(7 * 11) % 72 = 4]
Public key is (e, n) => (11, 91)
Private key is (d, n) => (7, 91)
The encryption of m = 2 is c = 37 % 91 = 37
The decryption of c = 37 is m = 377 % 91 = 2