RSA

RSA This algorithm is used in cryptography Technique in that RSA is added along with it. These are procedures followed

Key generation
RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way:

1. Choose two distinct prime numbers p and q.
* For security purposes, the integers p and q should be chosen uniformly at random and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
2. Compute n = pq.
* n is used as the modulus for both the public and private keys
3. Compute φ(pq) = (p − 1)(q − 1). (φ is Euler's totient function).
4. Choose an integer e such that 1 < e < φ(pq), and e and φ(pq) share no divisors other than 1 (i.e., e and φ(pq) are coprime).
* e is released as the public key exponent.
* e having a short bit-length and small Hamming weight results in more efficient encryption. However, small values of e (such as e = 3) have been shown to be less secure in some settings.[4]
5. Determine d (using modular arithmetic) which satisfies the congruence relation d e \equiv 1\pmod{\varphi(pq)}.
* Stated differently, ed − 1 can be evenly divided by the totient (p − 1)(q − 1).
* This is often computed using the extended Euclidean algorithm.
* d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the private (or decryption) exponent d which must be kept secret.

Note:

* An alternative, used by PKCS#1, is to choose d matching e d ≡ 1 (mod λ) with λ = lcm(p-1,q-1), where lcm is the least common multiple. Using λ instead of φ(n) allows more choices for d. λ can also be defined using the Carmichael function λ(n).
* For efficiency the following values may be precomputed and stored as part of the private key:
o p and q: the primes from the key generation,
o d\mod (p - 1) and d\mod(q - 1),
o q^{-1} \mod(p).

[edit] Encryption

Alice transmits her public key (n,e) to Bob and keeps the private key secret. Bob then wishes to send message M to Alice.

He first turns M into an integer 0 < m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to:

c = m^e\,\bmod\,n

This can be done quickly using the method of exponentiation by squaring. Bob then transmits c to Alice.
[edit] Decryption

Alice can recover m from c by using her private key exponent d by the following computation:

m = c^d\,\bmod{\,n}.

Given m, she can recover the original message M by reversing the padding scheme.

(In practice, there are more efficient methods of calculating cd using the pre computed values above.)
[edit] A worked example

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.

1. Choose two prime numbers

p = 61 and q = 53 Make sure that these prime numbers are distinct.

2. Compute n = pq

n=61\cdot53=3233

3. Compute the totients of product. For primes the totient is maximal and equals the prime minus one. Therefore \varphi(pq) = (p-1)(q-1) \,

\varphi(61\cdot53) = (61 - 1)\cdot(53 - 1) = 3120\,

4. Choose any number e > 1 that is coprime to 3120. Choosing a prime number for e leaves you with a single check: that e is not a divisor of 3120.

e = 17

5. Compute d such that d e \equiv 1\pmod{\varphi(pq)}\, e.g., by computing the modular multiplicative inverse of e modulo \varphi(pq)\,:

d = 2753
since 17 · 2753 = 46801 and 46801 mod 3120 = 1, this is the correct answer.
(iterating finds (15 times 3120)+1 divided by 17 is 2753, an integer, whereas other values in place of 15 do not produce an integer. The extended euclidean algorithm finds the solution to Bézout's identity of 3120x2 + 17x-367=1, and -367 mod 3120 is 2753)

The public key is (n = 3233, e = 17). For a padded message m the encryption function is m^{17} \mod {3233} or abstractly:

c = m^e\mod {n}

The private key is (n = 3233, d = 2753). The decryption function is c^{2753} \mod {3233} or in its general form:

m = c^d\mod {n}

For instance, in order to encrypt m = 65, we calculate

c = 2790 = 65^{17}\mod {3233}

To decrypt c = 2790, we tap

m = 65 = 2790^{2753}\mod {3233}.

Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real life situations the primes selected would be much larger; in our example it would be relatively trivial to factor n, 3233, obtained from the freely available public key back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.