Whether for breaking codes in WWII, keeping your credit card info safe, or just cracking codes for fun, cryptography is a confluence of computer science and math that encrypts our most important data.
Exploit this knowledge to factor the (hexadecimal) keys below, and enter your answer as the last six digits of the largest factor you find (in decimal).
Key 1: 1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d Key 2: 2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f
However, not using large enough key sizes can be a problem.
Given below is a generator \(g\), a prime \(p\) and a public key \(B\) such that \[g^b \equiv B \pmod p \] for some private key \(b\).
1 2 3
There is reason to believe that this text was not encrypted with the sophisticated German Enigma machine but instead used a Vigenère cipher with a simple pass phrase. Thus, it is vulnerable to frequency analysis.
Decode this message and find out where the Germans are sending their bombers so we can evacuate the civilians. You will enter the number of the district (as shown in this list) to submit your answer.
Details and assumptions
A Vigenère cipher is a more complicated shift cipher. For example, rather than shifting every character in a word by two letters like this:
SECRET -> UGETGV
you would instead choose a pass phrase (e.g., "CAT"), which would then tell you to shift each of the letters in your plain text by the letter in the passphrase ("C" is a shift of 2 character, "A" is a shift of none, etc. ) :
C A T C A T (passphrase) S E C R E T (plain text) U E V T E M (cipher text)
Note: This problem is loosely based on cryptographic methods used around the time of the invasion of Normandy in 1944.