Cryptography
Computer Science
Computer Catlog
Cryptography - TOC

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.


Google