this relation also implies RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. The intention is that messages encrypted with the public key can only be decrypted in a reasonable amount of time by using the private key. The public key is represented by the integers and , and the private key by the integer (although is also used during the decryption process, so it might be considered to be a part of the private key too). represents the message (previously prepared with a certain technique explained below). Key generation The keys for the RSA algorithm are generated in the following way: Choose two large prime numbers and . To make factoring harder, and should be chosen at random, be similar in magnitude, but differ in length. Prime integers can be efficiently found using a primality test. and should be kept secret. Compute . is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length. is released as part of the public key. Compute , where is Carmichael's totient function. Since , and since and are prime, , and likewise . Hence . The may be calculated through the Euclidean algorithm, since . is kept secret. Choose an integer such that and ; that is, and are coprime. having a short bit-length and small Hamming weight results in more efficient encryption the most commonly chosen value for is . The smallest (and fastest) possible value for is 3, but such a small value for has been shown to be less secure in some settings. is released as part of the public key. Determine as ; that is, is the modular multiplicative inverse of modulo . This means: solve for the equation ; can be computed efficiently by using the extended Euclidean algorithm, since, thanks to and being coprime, said equation is a form of Bézout's identity, where is one of the coefficients. is kept secret as the private key exponent. The public key consists of the modulus and the public (or encryption) exponent . The private key consists of the private (or decryption) exponent , which must be kept secret. , , and must also be kept secret because they can be used to calculate . In fact, they can all be discarded after has