$3$ Basic Cryptography

All information we transmit on a computer can be understood at a base level as a sequence of zeros

and ones. Say I want to transmit a message like

$0,1,1,1,0,0,1,0$

to another party$-$Amazon, maybe. How can I do that such that no one other than the intended

recipient can understand what is being sent? This, essentially, is the primary goal of cryptography,

and the answer is what is usually referred to as encryption. $($This kind of exchange happens very

often. For example, some $95\%$ of Internet traffic is encrypted.$)$

Number theory is exceedingly useful for cryptography. Let me show you the most basic reason

why$-$it is quite simple.

If you want to eventually send a message of$,$ say, $8$ bits $($zeros and ones$),$ first choose a random

sequence of $8$ bits$-$this will be something like

$0,1,0,1,1,0,1,0.$

This is what is known as the key. Share this with your intended recipient, but not with others.

Then, when you are finally ready to send your message, simply add the message and the key

together, using modular arithmetic, as follows:

Here, we have used the observation that

$[0{]}_2+[0{]}_2=[0{]}_2$

$[0{]}_2+[1{]}_2=[1{]}_2$

$[1{]}_2+[0{]}_2=[1{]}_2$

$[1{]}_2+[1{]}_2=[0{]}_2.$

This process is known as encryption. $($This particular encryption scheme is known as the one$-$time

pad.$)$ We then send this output to our intended recipient. What we want to know is whether our

intended recipient will be able to read it $($using their key$)$ and whether someone else would be able

to read it $($without the key$).$

Prove that if the intended recipient takes the output and adds the key to it again $($using

modular arithmetic$),$ then they will get the original message again. $($Hint: what happens if

you add the key to itself?$)$ This process is known as decryption.

Why is it not possible to determine what the message is without knowing what the key is$?$

$($Hint: suppose that you are given some output. Show that by changing the key, you can

decrypt this output to any possible message.$)$