# Mission #3

Due: Friday, Sept 16th.

You are at headquarters. Eviladia has decided to drop a certain fixed number of attack hamsters in Manhattan, with the intent of creating chaos. Although you’ve argued to headquarters that knowing the exact number of attack hamsters is not the most important part of preventing the potentially catastrophic event, they seem to be unable to move forward with a defense plan without knowing the exact number. Just for fun, Eviladia has given you a clue: the number of attack hamsters is less than 1000, and in fact, it is the three-digit number formed by the last three digits of $2^{563}$. That doesn’t seem so bad, except the lights went out at headquarters because the mad scientist they keep in the basement just blew a fuse running some sort of new kale-based supercomputer. So you have just a few minutes and a pad of paper.

Task 1. Determine the final three digits of 2^563, using at most 15 multiplications, each of which is involves numbers of at most 3 digits. Hint: Section 3.5 in your book.

Well, that hamster thing didn’t turn out well. You figured out how many hamsters there were, but it didn’t help when the furry little things parachuted in and started eating holes in everyone’s clothing. It was quite a mess. Let’s just move on, shall we.

Ok, back at headquarters. You have a spy planted in Eviladia and he has some important information about the genetic engineering that went into those attack hamsters. Problem is, although you agreed to use a Vigenere cipher, you forgot to set up a shared secret key with your spy friend, so it’s kind of useless. He’s deep behind enemy lines and his every missive is read by the border police. His cover story is that he’s a hamster-clothing salesman, so his letters so far are some really boring stuff about the unsuitability of tiny denim overalls in combat.

Anyway, problem is, how can you two establish a secret key? It would seem to be an impossible problem, since the border guards can read every bit of your communication.

Headquarters has assigned you to internet research, and, feeling you have an impossible assignment, you just start searching for cute cat videos. Your boss walks in and you quickly type “key exchange” in the search bar, and you find this video:

Watch Now

Ok, that seems like a good idea. How can we do this mathematically? Here’s a way:

First, work through the topic “Orders of Elements Modulo n” in the sidebar, if we haven’t done it in class yet. I plan to do this Monday.

Suppose Alice and Bob want to set up a secret key. Alice chooses a key, call it $k$. She wishes to send this to Bob, but Eve is listening in. First, Alice picks a modulus $p$. Let’s assume it’s prime and doesn’t divide $k$, just for kicks. She tells this $p$ to Bob; she doesn’t care if Eve hears it.

Next, Alice chooses some number $a$, and finds an element $A$ such that $k^{aA} \equiv k \pmod p$. If no such $A$ exists, try changing $a$ as needed. She keeps this $a$ and $A$ secret.

Similarly, Bob chooses some number $b$, and finds an element $B$ such that $k^{bB} \equiv k \pmod p$. If no such $B$ exists, try another $b$ as needed. He keeps this $b$ and $B$ secret.

Task 2. Determine, as Alice, how to find $A$ efficiently if you know $k$, $a$ and $p$. Exhaustive search is NOT efficient. Use the Euclidean algorithm somehow, which IS efficient. Hint: the order of $k$ modulo $p$ is $p-1$ (this is a fact we’ll study in class). Exactly which powers of $k$ are $1$ modulo $p$? You’ll need the answer to Task 2 to accomplish Task 3.

Now for the exchange. Alice wants to send the key $k \pmod p$ to Bob.

Alice sends $k^a \pmod p$ to Bob. This is the locked briefcase. Without knowledge of $a$ (Alice’s secret), no one can unlock it to get $k$.

Bob receives $k^a \pmod p$ and returns $k^{ab} \pmod p$ to Alice (just raising whatever he gets to the $b$). This is the doubly-locked briefcase.

Alice receives $k^{ab} \pmod p$ and returns $k^{abA} \pmod p$, which is just $k^b \pmod p$, to Bob. (She just raises what she got to $A$). This is the briefcase with only Bob’s lock on it.

Finally, Bob raises what he receives to $B$ and gets $k \pmod p$. In other words, he unlocks the briefcase.

Eve saw $k^a$, $k^{ab}$ and $k^{b}$ but doesn’t know $a$ and $b$, so she can’t figure out $k$.

Below are some hidden Sage cells which implement the process. Run through them once to watch it happen (you’ll have to cut-and-paste the output of one box into the input of the next, etc.). (If something goes funny later when you’re messing around, you may need to reload the page, since the Sage cells need to be initialized in order.)

Here, $p=10^9+7$, which is prime.

First, this Alice cell will output $k^a \pmod p$:

Next, this Bob cell will take any input $s$ and output $s^b$:

Next, this Alice cell will take any input $s$ and output $s^A$:

Next, given input $s$, this Bob cell will set its key to be $s^B$:

Now, this Alice box will send a message with her secret key $k$:

And, finally, this Bob box will decipher the sent message with his understanding of $k$ (from the key exchange above). Note that this box must be re-initialized if Bob’s key changes above.