RSA Algorithm

• RSA (Rivest–Shamir–Adleman) is an asymmetric cryptographic algorithm that is used to encrypt and decrypt messages


• The concept introduces the terms Private Key and Public Key. Public Key is shared publicly and Private Key is kept privately by the participants


• In the next part, an animation will be used to illustrate the concept

Example: Color Keys

• Consider Alice trying to send Bob a message and Eve is intercepting the connection


• For this example, mixing colors is assumed to be a one way function


• Alice randomly selects a color and generates her private key as red

Example: Color Keys

• Assume Alice uses a mechanism to find an exact complement for her color and keeps it secret


• The complement of red is cyan as it changes the color to white when mixed.

Example: Color Keys

• Alice then sends cyan to Bob as it becomes her public key


• Notice Eve has access to cyan as she intercepts the session

Example: Color Keys

• Bob wants to send a message to Alice and its color is yellow


• He mixes it with Alice's public color and obtains a mixture, which is green

Example: Color Keys

• Bob sends his message back to Alice and the information transfering is public


• As the message green is public, Eve can again obtain this color information

Example: Color Keys

• Alice adds her private color to Bob's mixture


• This removes the effect of her own public color and she obtains Bob's secret color, yellow


• Note that Eve has no easy way to obtain the content of Bob's message as she needs Alice's private color red to do so


• This is basically how RSA works. However a mathematical solution is necessary. In the following part, it will be explained.

Operation of RSA

• Let \({p}\) and \({q}\) denote two different large prime numbers


• Modulus for the private and public keys are computed as:\({n=pq}\)


• Next, totient is calculated:\({\phi(n)=(p-1)(q-1)}\)


• A co-prime \({e}\) to \({\phi(n)}\) such that \({1 < e < \phi(n)}\). This exponent is shared as the public key


• After, a \({d}\) value satisfying \({de \equiv 1 (mod(\phi(n)))}\) is to be determined. This exponent is kept as the private key

Operation of RSA

• Message to be sent is first padded and let the result be denoted as \({m}\)


• The encryption function for the message is:\({c=m^e(mod(n))}\)


• The decryption function for the ciphertext \({c}\) is:\({m=c^d(mod(n))}\)

Thank You