MAT 338 Day 17 2011

2459 days ago by kcrisman

Notice the generality we can get with some of the things we are now discussing.  For instance, you could solve for which positive integers $a$ the congruence $ax^4\equiv 2$ mod (13) is solvable, not just for one $a$.  Similarly on the theory side, what did you conjecture for the product of all primitive roots modulo $p$?

@interact def _(p=(31,prime_range(100))): a=mod(primitive_root(p),p) L = [(a,n,a^n) for n in range(1,p) if gcd(n,p-1)==1] M = ["%s^{%s}\equiv %s"%(item[0],item[1],item[2]) for item in L] html("One primitive root is $%s$"%a) html("So all of them are the correct powers:") html("$"+",".join(M)+"$") html("And $"+"\cdot".join([str(item[2]) for item in L])+"\equiv %s$"%(prod([item[2] for item in L]))) 
       

Click to the left again to hide and once more to show the dynamic interactive window

This is something you can prove using the pieces of information from before about primitive roots fairly easily.  See the homework.

Today we will introduce cryptography, and over the next few days we will see the prototype for a cool mathematical encryption system and other similar topics.  During the last two days of the quad we will discuss practical issues in implementing these - namely, finding HUGE primes and factoring HUGE composite numbers.  Where by huge, I mean something substantially bigger than this:

next_prime(randrange(2^99));next_prime(randrange(2^300)) 
       
161739973449643440459282364219
369284476538761170583831963880403569823536266419618578320385122441043760\
475692471946128923
161739973449643440459282364219
369284476538761170583831963880403569823536266419618578320385122441043760475692471946128923

Those are peanuts by today's standards.

What is cryptography?

Cryptography is not just the science of making (and breaking) codes, as a dictionary might have it. It is the mathematical analysis of the tools of secrecy, from both the perspective of someone keeping a secret and that of the person trying to figure it out. Sometimes it is also called cryptology, while sometimes that term is reserved for a wider meaning.

There are two kinds of codes.

  • Ones intended to remain secret!
  • Ones encapsulating information in a convenient format. 

Mathematicians use the word code to indicate information is being stored, reserving the term cipher to talk about a way to protect that information. So, what we do when learning about this is a some of each, though mostly about ciphers.

There are many ways to encode a message; the easiest one for us will be to simply represent each letter of the English alphabet by an integer from 1 to 26. It is also easy to represent both upper- and lowercase letters from 1 to 52.

We'll use the following cell to turn messages into numbers and vice versa.  You encode a plaintext message (no spaces, in quotes, for our examples) and decode a positive integer.

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) 
       
encode('q') 
       
17
17
decode(17) 
       
'Q'
'Q'

This should be straightforward.  Notice that I didn't bother separating lower and uppercase letters.  In fact, no matter how complicated you get, with just a one-to-one correspondence, there are only a few possibilities for each letter, and if you know the language you can just start guessing which encrypted number stands for its most common letter.

So in practice we do a few other things.  For instance, one thing that is commonly done is to make longer blocks of letters, and then turn those into numbers.  Presumably there are a lot more three-letter (or longer) possible blocks of letters in English to be able to decrypt things too easily.   Compare the following two encodings of 'The best day of the year' and see which one might be easier to figure out.

[encode(letter) for letter in 'Thebestdayofthisyear'] 
       
[20, 8, 5, 2, 5, 19, 20, 4, 1, 25, 15, 6, 20, 8, 9, 19, 25, 5, 1, 18]
[20, 8, 5, 2, 5, 19, 20, 4, 1, 25, 15, 6, 20, 8, 9, 19, 25, 5, 1, 18]

For pairs, we represent the first letter as a number from 1 to 26, and the second letter as 26 times the letter number (think of it as base 26).  Remember that A=1, B=2, etc.

encode('cb');decode(3+26*2) 
       
55
'CB'
55
'CB'
[encode(pair) for pair in ['th','eb','es','td','ay','of','th','is','ye','ar']] 
       
[228, 57, 499, 124, 651, 171, 228, 503, 155, 469]
[228, 57, 499, 124, 651, 171, 228, 503, 155, 469]

Whereas there are many 5s in the first one, which you could guess were Es, the second one has only one repeat (though knowing English, one might guess it was 'Th').  Notice we haven't really encrypted yet, just encoded.

With three letter blocks, there are then already $26^3=17576$ possibilities.

encode('zab');decode(26+1*26+2*26^2) 
       
1404
'ZAB'
1404
'ZAB'

So, INT HEB EGI NNI GWA STH EWO RDX could be encoded, with an extra X to fill out the space (this is, of course, also done in the middle to confuse things).  We will, however, usually keep our whole message together as one item, since we want to understand the mathematical aspects most.

We will spend most of our time talking about enciphering, or encrypting, messages. This 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 do it. 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.

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 encryption.  The symmetry is that both people need to keep it secret.   One supposed early example of this goes back to C. Julius Caesar.  To encrypt a message, first convert it to numbers, and then add three to each number (wrapping around if needed), and convert back to letters.

message='MathIsCool' secret=[encode(letter) for letter in message] secret 
       
[13, 1, 20, 8, 9, 19, 3, 15, 15, 12]
[13, 1, 20, 8, 9, 19, 3, 15, 15, 12]

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.

code=[(x+3)%26 for x in secret] code;''.join([decode(n) for n in code]) 
       
[16, 4, 23, 11, 12, 22, 6, 18, 18, 15]
'PDWKLVFRRO'
[16, 4, 23, 11, 12, 22, 6, 18, 18, 15]
'PDWKLVFRRO'

What did I do here?  Well, this is really just modular arithmetic, modulo 26, so that is what I did.  

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$, your key is $a$, and you are working modulo $(n)$, then your encrypted message $m$ is $$m\equiv x+a \text{ mod}(n)$$ To get $x$ back, you just use the additive inverse to $a$ modulo $n$, which is $-a$.

Since $-3$ is the inverse of $3$, this one is easy to decipher.

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

We could list the key here as a pair $(a,n)$, with $a=3$ and $n=26$.

As noted above, one can do something similar with bigger numbers, in blocks of two.

message='Mathiscool' secret=[encode(message[2*i:2*i+2]) for i in range(len(message)/2)] # Note I need an even number of letters to do this! secret 
       
[39, 228, 503, 393, 327]
[39, 228, 503, 393, 327]

Let's do something a little more interesting to encrypt this.  What else has inverses? 

Well, sometimes multiplication mod $(n)$ does!   We could make a cipher that gets $m$ by performing $$m\equiv ax+b \text{ mod}(n)\; .$$  Here, let's choose $a=5$ and $b=18$; we'll use $n=677$, the next prime after $26^2$, since we have blocks of two letters each.

code=[(5*x+18)%(next_prime(26^2)) for x in secret] code;''.join([decode(n) for n in code]) 
       
[213, 481, 502, 629, 299]
'EHMRHSEXMK'
[213, 481, 502, 629, 299]
'EHMRHSEXMK'

Now the key is listed as a triple, $(a,b,n)=(5,18,677)$.  How do we invert this?  

To get from $ax+b$ back to $x$, ordinarily we would subtract $b$ and then divide by $a$; but now we are working over $\mathbb{Z}_{n}$, so is that possible?  We'll need our first `extra' condition; to make it workable, we need gcd$(a,n)=1$. In that case there is a number

$a'$ such that $$a(a')\equiv 1\text{ mod}(n)\; ,$$ so we can send $$m\to a'(m-b)\equiv x\text{ mod}(n)\; .$$

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):

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

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

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

message='Mathiscool' secret=[encode(letter) for letter in message] secret 
       
[13, 1, 20, 8, 9, 19, 3, 15, 15, 12]
[13, 1, 20, 8, 9, 19, 3, 15, 15, 12]

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), I will change that block to (28,8), which modulo 26 becomes (2,8).

[(secret[i]+secret[i+1])%26 if i%2==0 else secret[i] for i in range(len(secret))] 
       
[14, 1, 2, 8, 2, 19, 18, 15, 1, 12]
[14, 1, 2, 8, 2, 19, 18, 15, 1, 12]

This turns out to be the same thing as multiplying the list of vectors of length two by the matrix $$\left(\begin{matrix}1& 1\\0& 1\end{matrix}\right)\; !$$  To invert this cipher, we would need an inverse to this matrix modulo 26.  Another connection to the rest of mathematics! And a huge reason why linear algebra over finite algebraic structures is VERY important to security types.

Now, 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 may seem odd. But in practice today, people really do just post their encryption keys on the Internet!  Here is one of someone you all know, for instance.

Then, 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 a system is called public-key cryptography, although of course it's only the encryption key that is actually public.

We are not quite ready to talk about this yet.  But we are ready to talk about a (symmetric) system that leads to it - one that really needs yet another invertible number theory procedure, one that we finally should be comfortable with.  That procedure is modular exponentiation.  Now that we can solve modular exponential using (for instance) primitive roots, we have the tools to tackle these far more subtle techniques.  Let's go for it!

In the cell below, we will pick a few things.  (Our secret is still that math is cool.)  We need a prime number $p$, and some legitimate exponent $e$ that won't mess things up too badly.  What do I mean by that?  Remembering that when we solved $$x^{3}\equiv 5 \text{ mod}(17)\text{ as }3^{3i}\equiv 3^{5}\text{ mod}(17)$$ we ended up in the world of $\phi(17)=16$ and solving $$3i\equiv 5 \text{ mod}(16)\, .$$ In order to keep using this idea, we will pick an exponent coprime to $\phi(p)$.

Now, I just take my message and raise it to the $e$ power modulo $p$ - simple as that!

p=29 # a prime number e=9 # a number coprime to euler_phi(p)=p-1=28 code=[mod(x,p)^e for x in secret] code;''.join([decode(n) for n in code]) 
       
[5, 1, 23, 15, 6, 11, 21, 26, 26, 12]
'EAWOFKUZZL'
[5, 1, 23, 15, 6, 11, 21, 26, 26, 12]
'EAWOFKUZZL'

Here I picked $p=29$, useful since it's close to 26, and more or less arbitrarily picked an exponent $e=9$.   I still first had to encode 'MathIsCool' to numbers.  Then I exponentiated each number in the coded version, modulo 29.  To be precise, I sent each number $$a\to a^9\text{ mod }(29)\; .$$  (Notice that decoding the secret message code is not so useful anymore!  So we usually just stick with the numbers.)

Leaving aside for the moment that the letter A will now have the unfortunate property that it always stays 1, and hence basically unencrypted (this is because we are doing a toy example), how on earth would we ever decrypt this?  Do we have a way to invert $$a^9\text{ mod }(29)$$ in any way?

f=mod(e,p-1)^-1 # the multiplicative inverse mod p-1 (!) to our encryption power f;''.join([decode(x^f) for x in code]) 
       
25
'MATHISCOOL'
25
'MATHISCOOL'

Naturally, we do!  We will use exponentiation again to do so.  We just need something that solves $$\left(a^9\right)^f\equiv a\text{ mod }(29)\; ,$$ or more concisely $$a^{9f}\equiv a^1\text{ mod }(29)\; .$$  (We can think of $f$ as a power that inverts the original power $9$.).  From our earlier discussion, this is just a solution to $$9f\equiv 1\text{ mod }(28)$$ and we know we can find this.  

This method is known as the Diffie-Hellman, or D-H, method (named after its originators, who proposed it in the mid-70's).  Now we will do a more real example of this.  Notice how important it was that we chose an initial exponent $e$ that was coprime to $\phi(p)=p-1$.

message='heymathiscooleverybody' secret=encode(message) secret 
       
13044594485924740120065295822374
13044594485924740120065295822374

For convenience, I'll just take the next prime bigger than my message.

p=next_prime(secret) p;factor(p-1) 
       
13044594485924740120065295822453
2^2 * 3^2 * 11 * 17 * 8273 * 234219716629408326624607
13044594485924740120065295822453
2^2 * 3^2 * 11 * 17 * 8273 * 234219716629408326624607

I factored $p-1$ so I could find something coprime to it.

e=10103 # a number coprime to p-1; note not all will work! code=mod(secret,p)^e code 
       
9687827625907130820812107474110
9687827625907130820812107474110

The encrypted message is now just one number.  Now we need the decryption key.  Luckily, that's just as easy as taking an inverse modulo $p-1$:

f=mod(e,p-1)^-1 f;''.join(decode(code^f)) 
       
5098792796685815968933767514883
'HEYMATHISCOOLEVERYBODY'
5098792796685815968933767514883
'HEYMATHISCOOLEVERYBODY'

Or a really cool example:

message='mathisreallycoolanditshouldntbeasecret' secret=encode(message) p=next_prime((secret)^5) e=677 # hopefully coprime to p-1 code=mod(secret,p)^e f=mod(e,p-1)^-1 html("My encoded message is $%s$"%secret) html("A big prime bigger than that is $%s$"%p) html("And I chose exponent $%s$"%e) html("The encrypted message is $%s$"%code) html("The inverse of $%s$ is $%s$"%(e,f)) html("And the decrypted message turns out to be:") print ''.join(decode(code^f)) 
       
My encoded message is 456852583124842114039371869486849541361942257940969127
A big prime bigger than that is 19901253152869563309723662610292328389634458107944010604042555563705501076334500415727246558508890126813900283887956436979499141327004021398892610004731269986110529437289385314056563037068659842333714116396838715552272338731683607696792667582648188537035713642154015003
And I chose exponent 677
The encrypted message is 5671429597427784609252296012902402984799130703165480861885236311936909878124253596757140581626041120924645503439427869786950283574272896705647992202949606005119301174919954323984659002526192028827446976232112510529010204454970468780474512088807034775928563914920528081
The inverse of 677 is 17138006777138781993454793651108460046021992728111311938193219931521871680211246295966004052600713358836785621132464701268903987287508632903329972869657799707389126531668702567348561670031061577666994578817366279419460522127875248577887924964082561177388214259048435371
And the decrypted message turns out to be:
MATHISREALLYCOOLANDITSHOULDNTBEASECRET
My encoded message is 456852583124842114039371869486849541361942257940969127
A big prime bigger than that is 19901253152869563309723662610292328389634458107944010604042555563705501076334500415727246558508890126813900283887956436979499141327004021398892610004731269986110529437289385314056563037068659842333714116396838715552272338731683607696792667582648188537035713642154015003
And I chose exponent 677
The encrypted message is 5671429597427784609252296012902402984799130703165480861885236311936909878124253596757140581626041120924645503439427869786950283574272896705647992202949606005119301174919954323984659002526192028827446976232112510529010204454970468780474512088807034775928563914920528081
The inverse of 677 is 17138006777138781993454793651108460046021992728111311938193219931521871680211246295966004052600713358836785621132464701268903987287508632903329972869657799707389126531668702567348561670031061577666994578817366279419460522127875248577887924964082561177388214259048435371
And the decrypted message turns out to be:
MATHISREALLYCOOLANDITSHOULDNTBEASECRET

I'll ask you to do some by hand of this.  Remember, our first awesome encryption scheme does the following:

  • Turn your message into a number $x$.
  • Pick a prime $p$ and an exponent $e$ such that $gcd(e,p-1)=1$.
  • Encrypt to a secret message by taking $$m=x^e\text{ mod }(p)\; .$$

Want to decrypt?

  • First, find an inverse modulo $p-1$ to $e$, called $f$, so that $$ef\equiv 1\text{ mod }(p-1)$$
  • Decrypt (if you want) by taking $$m^f\equiv \left(x^e\right)^f\equiv x^{ef}\equiv x^1\equiv x\text{ mod }(p)$$
  • Celebrate in your opponent's destruction.

Feel free to see what happens with your own short messages.

@interact def _(message='mathiscool'): secret=encode(message) p=next_prime(100*(secret)) e=677 # hopefully coprime to p-1 code=mod(secret,p)^e try: f=mod(e,p-1)^-1 except: html("Looks like $%s$ is not coprime to the prime we chose, $%s$"%(e,p)) html("My encoded message is $%s$"%secret) html("A big prime bigger than that is $%s$"%p) html("And I chose exponent $%s$"%e) html("The encrypted message is $%s$"%code) html("The inverse of $%s$ is $%s$"%(e,f)) html("And the decrypted message turns out to be:") print ''.join(decode(code^f)) 
       

Click to the left again to hide and once more to show the dynamic interactive window

Homework to hand in:

  1. Prove, using your formula for $\phi$, that there are infinitely many $n$ for which $\phi(n)$ ends in zero.
  2. Suppose $p$ is prime and the order of $a$ modulo $p$ is $d$.  Prove that if $b$ and $d$ are coprime, then $a^b$ also has order $d$ modulo $p$. (Hint: actually write down the powers of $a^b$, and figure out which ones could actually be 1.)
  3. Suppose $p$ is prime and $d$ divides $p-1$ (and hence is a possible order of an element of $U_p$).  Prove that at most $\phi(d)$ incongruent integers modulo $p$ have order $d$ modulo $p$.  (Hint: Lagrange's theorem (the polynomial one).)
  4. Find the orders (by hand) of all elements of $U_{23}$ and show that there are the 'right' number of each.  
  5. Find all solutions (if any) of:
    • $x^6\equiv 4$ mod ($23$)
    • $3x^{14}\equiv 2$ mod ($23$)
    • $3^x\equiv 2$ mod ($23$)
  6. Turn $x^6\equiv 4$ mod ($69$) into two congruences with prime power moduli, solve them, and use the CRT to unify their answers to get a solution to this.
  7. If $a$ is a primitive root of $n$, prove that $a^{-1}$ is also a primitive root of $n$.
  8. Prove that the product of all primitive roots modulo $p$ is 1, using the previous problem.
  9. Find two primitive roots of $81$ using the Euler $\phi$ criterion we used before (that is, by hand).
  10. Encrypt your name using an affine method ($ax+b$) with key $(5,6,29)$ (don't worry about letters), and decrypt BXHBI.
  11. Create your own $ax+b$ mod ($n$) system of encryption and bring an encrypted message to class.
  12. Use the Diffie-Hellman method of encryption to encrypt a short (three to five character) message with a $26<p<50$ "by hand" (i.e. without Sage but with a calculator).  Be prepared to explain your choice of $e$ and $p$, and calculate that $ef\equiv 1$ mod ($p-1$) by hand.
  13. Do this two-parter:
    • Suppose you discovered that the message 4363094, where $p=7387543$, actually represented the (numerical) message 2718.  What steps might you take to try to discover $e$?
    • Suppose that you discovered in the previous part by hard work that $e=35$.  Now quickly decrypt the message 6618138.