# Mission #1

Due Date:  Friday Sep. 2

Rules: You may use any written resources for help and information, but you may not use any technological aids (computer solvers) besides the Sage math tools on this website, or anything you program yourself.  You may not break up the work and assign pieces to everyone.  Everyone must engage in each problem and understand its solution.

Your group must hand in a typed account of what you did to accomplish the tasks below. It must be accompanied by a filled-out GroupWork Report describing your group activities.

You are a spy working for the government of the United Provinces of Americanada in 2156.  Time travel is a thing in your era, and it seems the government of Eviladia has sent a spy codenamed IxNay EaserCay back in time to ancient Rome to mess with history.  You’re not sure what he’s up to, but you suspect he’s trying to stop Caesar from crossing the rubicon.  Caesar is unsure about crossing and has decided to cross only if he has something witty to say as he crosses, to make it look good.  Caesar’s friend Sallust sent him a witty phrase for his crossing, but it was in ciphertext.  However, IxNay has intercepted it and replaced it with a totally stupid thing to say while crossing the Rubicon, enciphered correctly using Sallust and Caesar’s shared key.

You don’t know the key Sallust and Caesar share, but you must go back in time and replace the stupid message with the right ciphertext telling Caesar what to say to restore history to its proper order.  Intercepting the message isn’t hard, since hairstyling and tattooing was part of your spy training.

Anyway, you find that IxNay’s coded message is:

LXFIXKNUBLNUNUB

After having accomplished that, you seem to have saved history for now.

You head back to headquarters and discover that Eviladia has a new plan.  They’re very boastful, so it wasn’t hard to discover that they are extremely excited about their newfound ability to use the Vigenere cipher.  You’ve got to figure out where in history they are planning their next attack.  Fortunately, you are able to intercept one of their coded messages.  It is here:

DBZHVZLWTKMGGYADZZHZYZMGUMVOITQQTJBNHVKABUSMXDBORVOWEOOTZDSKSTGFMOQENHVCHXRDVZRIYVIYVQTDBKIZOHLXLKNNIYLAQLIIFWXGQTJBUZQQLXKGQGKMOVQTWPKDZSBMDFMVWPKKIJDTXHIJBZKWQXHLLUWSWPKDZSBQZLAIRVLXAOQOGQGCDGCHXRDVZROUEIINITGNOJCXHQZRCZDVJDAYDAYLVGWMNLUYRPKFITWKXDKQWPKYQMHVKUMILXNHZOIBNDBOVWQZQZKGUXTKWCYNVUZIRVWCHIXHAKQLOQOZKQYLVBLOKQMXHKOSPKUITGEKWPOQSOWQYSZUEIHOGNDZJHZZRJXHIQLNCHAKQLRRBYRNKABXDVUQAKQAKLVZKMSHAYDOKVWOPOULVMWWWXWZHNXRUYFQKQBOIQIDUKUQIDVUQBNHDOJQTHZKFQVKMXLVTLVKWMKQAKYMTWMKQBNHUKWPUGCYHLLRZZKMVUMVDZGWQUQITGZKDLOQOUIKUGMSHAYDOKVQYVQSSTKLVZKMKABXHUKDVJDBZKMYDUKWQSHQSSWYVQHOMUIBXDVYOIZLWTXVRHAYWPKNMELAQQWCQBNHMGVMCLBNZPOFPZKMQHGSDGHHKNDVMHLOVITRBNHZVRQTWQTIIBRZUIBNHIJRXZLWTRNZKQYFWJHJEWPUVMJHAOUQTJBUWZGQASLBOPXUUBGQBSHAYDOKVEOWPUXBZKMYOQMKBKVBJDVMHZUIBNHQXPMYVIMHAHHQTJZKDLHBXUOQZLKGOWXECYLVKVAXLDGOAKWK

Task 2.  Determine the key and the plaintext.

Phew, now that you knew what they were planning to do, it was a simple matter to go back and foil their plans.  But since you showed up to do that, they’ve decided Vigenere wasn’t as secure as they thought.  They’ve switched to using an affine cipher.  Your own government, never wanting to be seen as lagging technologically, has adopted the affine cipher too.  Unfortunately, they didn’t read the textbook too carefully and they’ve sent you a message modulo $26$ which uses $\alpha=2$ and $\beta=1$.  It looks like this:

NJLNRBNDBJNTDNPJJJ

Task 3.  Explain why their choice was a bad one, and figure out the original plaintext anyway.

Finally, exhausted from trying to explain modular arithmetic to your boss, you head home from the office.  On the way home in your VacuumPod, you come across a message scrawled in the Pod window, signed with Eviladia’s sign.

VELIDAAIAWHSREAELLOYRUABESRABELENOTGUOWSAEERLPNAINGNOTATEKVOREHTWERODLISCNYEUOAHEVONOHEPFOERDANITGIHMSSEASEGEWAMAYWSLEMLNEITNOHTTAUONRXETTRAEGITBSGADHDARAUODNEYRAEWLPNAOTNILFEUCNMEHUMAAMIDNBUMASLAHKAWIRMZNITOOTNIEVTNLAEGRBBACEUAESEWRAGETEITGNITERODHFVANITGLOAENROSUMHCFOTI

Task 4.  Where are they headed next and how do you plan to stop them?

Next day the government calls you back and needs to know more about modular arithmetic.

Task 5. Write them a small Sage routine (using for loops) which will print out a multiplication table modulo $n$ for any $n$.  Hand in your routine, as well as some example output.  Write an explanation as to why you can tell which residues modulo $n$ are not invertible by looking at the table, and illustrate with at least two examples.

Here’s an empty Sage cell for you to play with.