Better to know some... than all 


RSA publickey encryptionThe RSA cryptosystem, named after its inventors R. Rivest, A. Shamir, and L. Adleman, is the most widely used publickey 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, m^{p1} = 1 (mod p). Raising both sides of this congruence to the power k(q1) and then multiplying both sides by m yields m^{1+k(p1)(q1)} = 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 m^{ed} = m (mod p). By the same argument, m^{ed} = m (mod q). Finally, since p and q are distinct primes, it follows that m^{ed} = m (mod n), and, hence, c^{d} = (m^{e})^{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 Ø = (p1)(q1) = 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 = m^{e} mod n = 5234673^{3674911} mod 6012707 = 3650502, and sends this to A. Decryption. To decrypt c, A computes c^{d} mod n = 3650502^{422191} mod 6012707 = 5234673. Universal exponent: The number = lcm(p1; 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(p1; q1) is expected to be small, and consequently Ø and will be roughly of the same size. 