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.

RSA Key Generation

    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.

RSA Encryption

    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.