DC10004 - Editorial
PROBLEM
Link to the Practice Question can be found: CodeChef: Practical coding for everyone
PREREQUISITE
Cryptography
DIFFICULTY
Moderate
PROBLEM
Assume Eve has captured a few ciphertexts. You need to write the decryption program such that with given cipher text, eve can recover the plaintext.
EXPLANATION
- This cryptography problem is a mixture of Diffie Hellman and RSA algorithm.
- Here the public key is used to encrypt the plaintext and private key helps to decrypt the ciphertext to get back the plaintext.
- Here some public information is given. Now you need to write a program for the given public information (f,g,qn,α,Ya). We also have the private key Xb.
- From the given f, we can easily calculate the ‘e’ by using the formula: f=(e×3)−1
- Calculate k; as k=Ya^Xb mod qn
- Calculate n by using the following formula; i.e. g=(k−n)
- From the n, find the value of p and q; as n=p*q
- From the value of p,q calculate the value of f(n)= (p−1)*(q−1)
- Now calculate the private key, d such that (e*d) mod f(n)=1
- Find the paint text (P) by using formula P = c^d mod (k-g); where ‘c’ is the cipher text.
- Convert the plaintext value into its corresponding letter as A=0,B=1,…,Z=25
Solution:
https://drive.google.com/file/d/1WEwBcXfVLIc9xmAsS4xXob3-ReNFWHBX/view?usp=sharing