# RSA Encryption Algorithm

## KryptoPhone uses RSA Encryption Algorithm

#### RSA Encryption Algorithm - Operation

###### Key Generation: Each entity shall select a positive integer e as its public exponent. Each entity shall privately and randomly select two distinct odd primes p and q such that (p-1) and e have no common divisors, and (q-1) and e have no common divisors. The public modulus n shall be the product of the private prime factors p and q: n = pq . The private exponent shall be a positive integer d such that de-1 is divisible by both p-1 and q-1. 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 using the private key. The public key is represented by the integers n and e; and, the private key, by the integer d (although n is also used during the decryption process; so, it might be considered a part of the private key, too). m represents the message. Key Distribution: Lets say Bob wants to send a secret message to Alice, then Bob must know Alice's public key to encrypt the message. Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key (n, e) to Bob via a reliable, but not necessarily secret route. Alice's private key (d), is never distributed. Encryption: After Bob obtains Alice's public key, he can send a message M to Alice. To do it, he first turns M (strictly speaking, the un-padded plaintext) into an integer m (strictly speaking, the padded plaintext), such that 0 ≤ m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c, using Alice's public key e, corresponding to c ≡ m e ( mod n ) This can be done reasonably quickly, even for 500-bit numbers, using modular exponentiation. Bob then transmits c to Alice. Decryption: Alice can recover m from c by using her private key exponent d by computing c d ≡ ( m e ) d ≡ m ( mod n ) Given m, Alice can recover the original message M by reversing the padding scheme. RSA encryption algorithm is considered to be secure to this point in time. 