[20 points] Alice is running an anonymous D-H key exchange with Bob and Eve is eavesdropping their communication in order to decipher the exchanged messages. Eve observes that Alice and Bob use g=7 and p=1404693457, and Alice sent the value A=785170121 while Bob sent the value B=413383232. Eve wants to quickly find the shared secret between Alice and Bob. What is the decimal value of this shared secret? Implement a program that recovers the shared secret in less than 30 seconds.
[15 points] Alice and Bob want to convert their shared secret S from the previous part into a residue number representation (RNS) based on the Chinese Remainder Theorem. The CRT base they selected is B=6469693230, which is the product of many small pairwise co-prime moduli. What is the residue of S with respect to each one of these small moduli (i.e., what is the RNS representation of S using B as the base)? Show all your work.
0 comments