NTIC Encryption

Section 11.2 Encryption

We will spend most of our time talking about enciphering, or encrypting, messages. Such encryption is the difficult part, after all, the details of which we want to keep secret.

🔗

What is cool about modern ciphers is that we actually expect that any eavesdropper will know how we do the encryption; they just don't know the key, which is the specific numbers we use to perform our mathematical encryption.

🔗

Reversing this process (hopefully only done by the person you want to receive your message!) is called decryption. Sometimes you need a different set of numbers to decrypt, in which case we distinguish between the encryption key and the decryption key.

🔗

Sage note 11.2.1. Reminder to evaluate definitions.

Don't forget to evaluate the first cell of commands so we can use words as messages instead of just numbers.

xxxxxxxxxx
 
def encode(s): # Input must be in quotes!
    s = str(s).upper()
    return sum((ord(s[i])-64)*26^i for i in range(len(s)))
​
def decode(n):
    n = Integer(n)
    list = []
    while n != 0:
        if n%26==0:
            list.append(chr(64+26))
            n -= 1
        else:
            list.append(chr(n%26+64))
        n //=26
    return ''.join(list)

🔗

Subsection 11.2.1 Simple ciphers

🔗

In the past, one would usually assume that both the sender and the receiver keep their keys secret (seems reasonable!), which is called symmetric key cryptography. The symmetry is that both people need to keep it secret. One early example of this supposedly goes back to C. Julius Caesar. To encrypt a message, first convert it to numbers, and then add three to each number (‘wrapping around’ as in modular arithmetic if needed), and convert back to letters.

xxxxxxxxxx
 
message='MathIsCool'
secret=[encode(letter) for letter in message]
secret

🔗

It's pretty clear that 1=A here, for instance. Now let's add three to each. The second letter should get to 4=D, for instance.

xxxxxxxxxx
 
code=[(x+3)%26 for x in secret]
print(code)
print(''.join([decode(m) for m in code]))

🔗

What did I do here? Again, this is just modular arithmetic, modulo 26, so I added 3 mod

$(26)\text{.}$

🔗

Subsection 11.2.2 Decryption and inverses

🔗

How will I decrypt it, if I get this mysterious message? Here is the main point about mathematical ciphers; they need to come from operations that have inverses! So in number theoretic ciphers, they'll need to come from (somehow) invertible operations.

🔗

In this case, the operation is modular addition, which certainly has inverses. If your encoded numerical message is

$x\text{,}$ your key is

$a\text{,}$ and you are working modulo

$(n)\text{,}$ then your encrypted message

$m$ is

$\begin{equation*} m\equiv x+a \text{ mod}(n) \end{equation*}$

🔗

To get

$x$ back, you just use the additive inverse to

$a$ modulo

$n\text{,}$ which is

$-a\text{.}$

🔗

Since

$-3$ is the inverse of

$3\text{,}$ this one is easy to decipher.

xxxxxxxxxx
 
''.join([decode((x-3)%26) for x in code])

🔗

We could list the key here as a pair

$(a,n)\text{,}$ with

$a=3$ and

$n=26\text{.}$

🔗

As noted above, one can do something similar with bigger numbers, in blocks of two. In the next Sage cell, the code requires a message with an even number of letters; can you make it more flexible?

xxxxxxxxxx
 
message='Mathiscool'
secret=[encode(message[2*i:2*i+2]) for i in range(len(message)/2)]
secret

🔗

Subsection 11.2.3 Getting more sophisticated

🔗

Let's do something a little more interesting to encrypt our ‘secret’ about how cool math is. What else has inverses?

🔗

Well, sometimes multiplication mod

$(n)$ does! We could make a cipher that gets

$m$ by performing

$\begin{equation*} m\equiv ax+b \text{ (mod }n)\text{.} \end{equation*}$

🔗

Here, let's choose

$a=5$ and

$b=18\text{;}$ we'll use

$n=677\text{,}$ the next prime after

$26^2\text{,}$ since we have blocks of two letters each.

xxxxxxxxxx
 
n = next_prime(26^2)
code=[(5*x+18)%n for x in secret]
print(code)
print(''.join([decode(m) for m in code]))

🔗

Now the key is listed as a triple,

$(a,b,n)=(5,18,677)\text{.}$ How do we invert this?

🔗

To get from

$ax+b$ back to

$x\text{,}$ ordinarily we would subtract

$b$ and then divide by

$a\text{.}$ Now we are working over

$\mathbb{Z}_{n}\text{,}$ so is that possible? We'll need our first ‘extra’ condition.

🔗

Fact 11.2.2.

To make modular encryption by a linear function workable, we need $\gcd(a,n)=1\text{.}$ In that case there is a number $a'$ such that

$\begin{equation*} a(a')\equiv 1\text{ (mod }n)\text{,} \end{equation*}$

so we can decode via

$\begin{equation*} m\longmapsto a'(m-b)\equiv x\text{ (mod }n)\text{.} \end{equation*}$

🔗

To decode this particular example, then, we need to first subtract 18, then multiply by an inverse to 5 (mod 677) (which turns out to be 271):

xxxxxxxxxx
 
''.join([decode(271*(x-18)%677) for x in code])

🔗

You should get ‘MathIsCool’ or whatever message you originally used.

🔗

The proof of the pudding is in the eating. There's no way I get the original message back unless this works!

🔗

Subsection 11.2.4 Linear algebra and encryption

🔗

There is another way of using blocks of size two or more, which we won't pursue very far, but which is a big piece of how standard encryption works (see here and here). Let's look at our message again.

xxxxxxxxxx
 
message='Mathiscool'
secret=[encode(letter) for letter in message]
secret

🔗

Now, in blocks of two, I will change my numbers by turning the first one into the sum of the numbers modulo 26 and leaving the second one alone. So for the second block

$(20,8)\text{,}$ I will change that block to

$(28,8)\text{,}$ which modulo 26 becomes

$(2,8)\text{.}$

xxxxxxxxxx
 
[(secret[i]+secret[i+1])%26 if i%2==0 else secret[i] for i in range(len(secret))]

🔗

This turns out to be the same thing as multiplying the corresponding list of vectors of length two by a matrix!

$\begin{equation*} \left(\begin{matrix}1& 1\\0& 1\end{matrix}\right) \end{equation*}$

🔗

To invert this cipher, we would need an inverse to this matrix modulo 26. (People don't do something quite so naive, as there aren't too many inverses modulo 26, but for our purposes this suffices.)

🔗

In any case, this is another connection to the rest of mathematics! And it is a huge reason why linear algebra over finite algebraic structures is very important in security.

🔗

Subsection 11.2.5 Asymmetric key cryptography

🔗

Finally there is another type of encryption, which is rather different. There exists the possibility that everybody knows the key to encrypt, while only the legitimate person knows how to decrypt. This is called asymmetric key cryptography.

🔗

This idea may seem odd. But in practice today, people really do just post their encryption keys on the Internet! In the live book, this links the public key of a fairly well-known open-source software advocate, for example.

🔗

In theory, anyone who wants to send Person XYZ a secure message could use this key, but only Person XYZ can decrypt it – convenient! Such an implementation of an asymmetric system is called public-key cryptography, although of course it's only the encryption key that is actually public.

🔗

In this chapter, we will see examples of both symmetric and asymmetric systems, but the main point is to lead up to the mathematics of basic public key systems.