Cryptography
 Computer Science Computer Catlog Cryptography Catlog

 Caesar Cipher Digital Signature Public key cryptography Symmetric vs. public-key Key Management Stream Ciphers Self-Synchronizing Ciphers Feedback Shift Registers Modes of Operation Multiple Encryption Transposition Ciphers Substitution Ciphers Poly-alpha Substitutions Poly-alpha Cipher Machine Cryptanalysis Ciphers Data Encryption Standard DES Algorithm IDEA Algorithm RC5 Algorithm RSA Encryption Rabin Encryption ElGamal Encryption MD4 & MD5 Secure Hash Algorithm Kerberos Authentication Diffie-Hellman protocols Key Management Life Cycle

## RSA public-key encryption

The RSA cryptosystem, named after its inventors R. Rivest, A. Shamir, and L. Adleman, is the most widely used public-key cryptosystem. It may be used to provide both secrecy and digital signatures and its security is based on the intractability of the integer factorization problem. This section describes the RSA encryption scheme, its security, and some implementation issues. The integers e and d in RSA key generation are called the encryption exponent and the decryption exponent, respectively, while n is called the modulus. Proof that decryption works: Since ed = 1 (mod Ø), there exists an integer k such that ed = 1+kØ. Now, if gcd(m, p) = 1 then by Fermat's theorem,

mp-1 = 1 (mod p).

Raising both sides of this congruence to the power k(q-1) and then multiplying both sides by m yields

m1+k(p-1)(q-1) = m (mod p).

On the other hand, if gcd (m, p) = p, then this last congruence is again valid since each side is congruent to 0 modulo p. Hence, in all cases

med = m (mod p).

By the same argument,

med = m (mod q).

Finally, since p and q are distinct primes, it follows that

med = m (mod n),

and, hence,

cd = (me)d = m (mod n).

RSA encryption with artificially small parameters: Key generation. Entity A chooses the primes p = 2357, q = 2551, and computes n = pq = 6012707 and
Ø = (p-1)(q-1) = 6007800. A chooses e = 3674911 and, using the extended Euclidean algorithm, finds d = 422191 such that ed = 1 (mod Ø). A's public key is the pair
(n = 6012707; e = 3674911), while A's private key is d = 422191. Encryption. To encrypt a message m = 5234673, B uses an algorithm for modular exponentiation to compute

c = me mod n = 52346733674911 mod 6012707 = 3650502,

and sends this to A.

Decryption. To decrypt c, A computes

cd mod n = 3650502422191 mod 6012707 = 5234673.

Universal exponent: The number = lcm(p-1; q -1), sometimes called the universal exponent of n, may be used instead of Ø = (p - 1)(q - 1) in RSA key generation. Observe that is a proper divisor of Ø. Using can result in a smaller decryption exponent d, which may result in faster decryption. However, if p and q are chosen at random, then gcd(p-1; q-1) is expected to be small, and consequently Ø and will be roughly of the same size.