RSA algorithm:
It is a very popular public-key algorithm. It can be used for maintaining confidentiality and authentication. The theory of RSA is based on the factorization problem and Euler theorem.Details of RSA algorithm
Let us suppose there are two-person A and B
Let A has two keys (eA, N) and (dA, N). Where (eA, N) is the public key, and (dA, N) is a private key.
Similarly, B has two keys (eB , N) and (dB, N). Where (eB , N) is the public key, and (dB, N) is the private key.
Let us suppose A want to send a message M to B and want to maintain the confidentiality of the message then he will use B’s public key to encrypt the message and B will use its private key to decrypt the message. If A wants to authenticate himself to B, then A will use its private key and encrypt the message. Since B has A’s public key he can verify the A by decrypting a message from his public key.
RSA algorithm:
Choose two very big prime numbers P and Q (these values are only known to sender and receiver ) and calculate N. N=P*Q (N is known to everybody).
For encrypting a message, A will use the public key of B(Why) and calculate ciphertext by the following equation.
C=(M) eB mod N for decrypting ciphertext B will use its private key which is dB and calculate
(C)dB mod N. To use this algorithm (C)dBmod N =M. Replacing C by (M) eB mod N will give
M=(M)eB*dB mod N.This will be possible if eB and dB will be multiplicative inverse on ɸ(N) because in that case eB*dB=c*ɸ(N)+1 replacing this value will make M=(M)eB*dB mod N true.
Example of the RSA algorithm:
If P and Q are 5 and 7 if the encryption key is 5 find the decryption key. Also, calculate ciphertext if the plaintext is 4.
N=P*Q=5*7=35 ɸ(N) =4*6=24
C=(4)5 mod 35=9 and decryption key will be the inverse of 5 over 24.
That will give 5.
So the encryption key will be (5,35) and the decryption key will also be (5,35).
Similarly, other questions can be attempted.
Diffie hellman algorithm for key exchange:
In symmetric-key cryptography, exchanging key between sender and receiver is a very big problem
For solving this problem, Diffie hellman gave one algorithm for key exchange and this algorithm is based on the difficulty of discrete logarithm problem. The extended version of this algorithm can also be used for encryption. In the upcoming slides, we will discuss these algorithms. Diffie hellman algorithm for key exchange. The idea is very simple to let A and B want to share secret keys .for sharing secret keys they choose a Prime number p and a primitive root α.In addition to it, both A and B have private keys XA and XB.
These private keys are only known to the owner of the keys. Now both of them calculate public keys from their private keys.a Let YA and YB are the public keys and their values are YA =(α)XAmod p and YB ==(α).
XBmod p According to the discrete logarithm problem, nobody can find the private keys from these public keys. Now A send YA to B and B sends YB to A.Now both of them calculate secret key as follows: Secret key =(YB ) XAmod p or (YA )XBmod p both will be the same and will be equal to (α)XAXBmod p.
Example:
Let p be 23 and Primitive root α is 9.If XA and XB are 4 and 3.
Calculate the public key and secret key.
The public key for A=(9)4mod23 and Public key for B=(9)3mod23 so YA and YB will be 6 and 16.
The secret key will be (16)4 mod 23=9.
Elgamal algorithm:
It is the extended version of Diffie Hellman.
Let A and B want to share some messages secretly. Then the following process will be adopted.
Alike Diffie Hellman algorithm they know Prime number p and a primitive root α. A know its private key XA And calculate public key YA =(α)XAmod p. Now let us suppose B wants to send an encrypted version of message M to A.For that B will generate a random number k and Calculate ciphertext in pair (C1 and C2).
Where C1=(α)k mod p and C2 will be (YA)
k mod p*M For decrypting Message A will calculate the inverse of (C1)XAmod p and multiply this with C2 to get M.
Example
Let Prime number p and a primitive root α are 107 and 2.XA is 67.
From XA YA =(α) XAmod p will be calculated and it will be (2)67 mod 107=94
Now if B wants to send ciphertext and plaintext is 66. If he generates random number k as 45.
(C1 and C2) will be (28,9). Please use the equation and calculate it. Now A will receive this ciphertext and calculate (C1)XAmod p and then calculate its inverse. When A multiply this value to
