a few words about RSA

Symmetric Key Cryptography is used to transfer a message securely between two endpoints using a shared secret key. The message is encrypted using a shared secret key in one endpoint and transferred to the other endpoint. Then the message is decrypted using the same shared secret in the other endpoint. This shared secret key should be exchanged in a secure fashion from one endpoint to the other before the transfer. For example, the secret key can be delivered personally using a USB storage. Due to the prior exchange requirement, the use of the symmetric key cryptography has some limitation.

Asymmetric Key Cryptography is another way of transferring a message securely. Unlike symmetric key cryptography, asymmetric key cryptography has two keys, one called public key and the other called private key. The public key can be distributed publicly, but the private key must be kept secret. One endpoint can use the public key to encrypt a message, while the other endpoint can use the private key to decrypt the message. This way eliminates the secure exchange of the shared secret key. However, the public key encryption costs a lot of compute resource, and is less efficient than the symmetric key. So a hybrid cryptography is usually used. Use the public key to encrypt the symmetric key and deliver the encrypted symmetric key to the other endpoint, which then can decrypt the symmetric key using the private key. Later communication then can be based on the symmetric key.

RSA is the most widely used asymmetric key cryptography. It can be used to encrypt or sign a message. The algorithm is as below:

  1. Generate two large random primes, p and q, such that their product n=pq is of the required bit length, e.g. 1024 bits.
  2. Compute n=pq and ϕ=(p−1)(q−1).
  3. Choose an integer e, 1<e<ϕ, such that gcd(e,ϕ) = 1.
  4. Compute the secret exponent d, 1<d<ϕ, such that ed ≡ 1 mod ϕ.
  5. The public key is (n,e) and the private key (d,p,q). Keep all the values d, p, q and ϕ secret.

n is known as the modulus.
e is known as the public exponent or encryption exponent .
d is known as the secret exponent or decryption exponent.