MAT 338 Day 19 2011

2393 days ago by kcrisman

Don't forget to evaluate this so we can use words instead of just numbers.

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) 
       

Cautionary example of RSA - and how to beat the problem!

Lest you think we are now completely secure, let me warn you about one possible problem.  Remember how we said above that it seems not to matter too much what $e$ is?  Well, that is sort of true, and sort of untrue.  

Suppose we chose to send a message using the following primes and randomly (?) chosen exponent $e$.  Notice that if $gcd(e,\phi(pq))\neq 1$, this code wouldn't have worked.

message='hiphop' secret=encode(message) p=197108347 q=591324977 e=52665067560570823 n=p*q phi=(p-1)*(q-1) code=mod(secret,n)^e f=mod(e,phi)^-1 html("My encoded message is $%s$"%secret) html("A big product of primes bigger than that is $pq=%s\cdot%s=%s$"%(p,q,n)) html("(which means my secret $\phi(n)=\phi(%s\cdot %s)=(%s-1)(%s-1)$ is $%s$)"%(p,q,p,q,phi)) html("And I chose exponent $%s$"%e) html("The encrypted message is $%s^{%s}\equiv%s$"%(secret,e,code)) html("The inverse of $%s$ modulo $%s$ is $%s$"%(e,phi,f)) html("And the decrypted message turns out to be:") print ''.join(decode(code^f)) 
       
My encoded message is 197108322
A big product of primes bigger than that is pq=197108347\cdot591324977=116555088756283019
(which means my secret \phi(n)=\phi(197108347\cdot 591324977)=(197108347-1)(591324977-1) is 116555087967849696)
And I chose exponent 52665067560570823
The encrypted message is 197108322^{52665067560570823}\equiv109598935674432155
The inverse of 52665067560570823 modulo 116555087967849696 is 103781564699780695
And the decrypted message turns out to be:
HIPHOP
My encoded message is 197108322
A big product of primes bigger than that is pq=197108347\cdot591324977=116555088756283019
(which means my secret \phi(n)=\phi(197108347\cdot 591324977)=(197108347-1)(591324977-1) is 116555087967849696)
And I chose exponent 52665067560570823
The encrypted message is 197108322^{52665067560570823}\equiv109598935674432155
The inverse of 52665067560570823 modulo 116555087967849696 is 103781564699780695
And the decrypted message turns out to be:
HIPHOP

Suppose Alice has sent Bob this message using Bob's impressive RSA key of $$(n,e)=(116555088756283019,52665067560570823)\; .$$  Now I will be Eve, trying to snoop.  On a hunch (or, as another book puts it, after attending a seminar at a decryption conference), I figure I don't have much to lose, so I'll take $e$th powers of the encrypted text.

trial_decrypt=code for i in [1..25]: trial_decrypt=trial_decrypt^e print ''.join(decode(trial_decrypt)) 
       
UUQUIAHESLLQ
IFTZCXXTCULDA
HREHHYCUZMWQ
TCYJRLNWJIZI
EDZTMVVWZBMQ
QLOUDBJUEOQS
RIDEUQVFIGMH
DNBDDHIMUTSM
HIPHOP
CPTAXZGBUIVCA
UUQUIAHESLLQ
IFTZCXXTCULDA
HREHHYCUZMWQ
TCYJRLNWJIZI
EDZTMVVWZBMQ
QLOUDBJUEOQS
RIDEUQVFIGMH
DNBDDHIMUTSM
HIPHOP
CPTAXZGBUIVCA
UUQUIAHESLLQ
IFTZCXXTCULDA
HREHHYCUZMWQ
TCYJRLNWJIZI
EDZTMVVWZBMQ
UUQUIAHESLLQ
IFTZCXXTCULDA
HREHHYCUZMWQ
TCYJRLNWJIZI
EDZTMVVWZBMQ
QLOUDBJUEOQS
RIDEUQVFIGMH
DNBDDHIMUTSM
HIPHOP
CPTAXZGBUIVCA
UUQUIAHESLLQ
IFTZCXXTCULDA
HREHHYCUZMWQ
TCYJRLNWJIZI
EDZTMVVWZBMQ
QLOUDBJUEOQS
RIDEUQVFIGMH
DNBDDHIMUTSM
HIPHOP
CPTAXZGBUIVCA
UUQUIAHESLLQ
IFTZCXXTCULDA
HREHHYCUZMWQ
TCYJRLNWJIZI
EDZTMVVWZBMQ

What's this?  Eve barely had to do anything to decrypt this!

This may seem mysterious, but it really is related to something we already used a number of times before.  Remember that we could find an inverse for $a$ modulo $n$ by just taking powers of $a$, because $$a^{-1}\equiv a^{\phi(n)-1}\text{ mod }(n)$$  Similarly, for any possible message $m$ and public key $e$, there will always be some power $k$ of $e$ such $$m^{e^k}\equiv m^1\text{ mod }(n)$$ which is the same as $$e^k\equiv 1\text{ mod }(\phi(n))$$  For this to happen, we would have to coincidentally have that not only $gcd(e,n)=1$ (which we always pick), but also that $gcd(e,\phi(n))=1$; but then Euler's theorem says that the order of $e$ modulo $\phi(n)$ is a divisor of $\phi(n)$, so we will sometimes find ones where that order is a small divisor of $\phi(n)$.  

Of course, in real life this would only happen randomly, so you could just protect against it by checking the order of $e$ modulo $\phi(n)$.  Here's how I created this not-quite-random example!

g = 7 # Pick something coprime to n print gcd(g,phi) i = mod(g,phi) # look at it mod phi(n) print i.multiplicative_order() print factor(i.multiplicative_order()) 
       
1
4567854373940
2^2 * 5 * 11 * 13 * 37 * 1879 * 22973
1
4567854373940
2^2 * 5 * 11 * 13 * 37 * 1879 * 22973
j=i^( 11 * 13 * 37 * 1879 * 22973) # take it to as high a power I can to reduce the order print j.multiplicative_order() # make sure this is small print gcd(j,phi) # check we still have the right gcd print j 
       
20
1
52665067560570823
20
1
52665067560570823

What was the problem here?  The issue is that we had a $\phi(n)$ such that its group of units had elements of tiny order in its group of units.  (Two levels deep here!)

More precisely, we had a $\phi(n)$ such that $U_{\phi(n)}$ had elements of very small order in it, so that $$e^{very small order}\equiv 1\text{ mod }(\phi(n))$$ was possible.  How can we avoid this?

When we found elements of big order (primitive roots, in fact) before, we relied on having the original modulus $p$ being prime.  We did not tell the whole story, but we did do enough of what happens with other moduli to know that we should suspect that having a small number of primes to small powers should let us keep finding elements of big order.  (For instance, we saw that $2^n$ had elements pretty close to being primitive roots.)

And we do know something about $\phi(n)$.  Namely, since $n=pq$ is the product of two primes, we know that $\phi(n)=(p-1)(q-1)$ is also the product of two numbers.  It would be too much to hope for those to be prime!  After all, $p-1$ and $q-1$ will both be even, since $p$ and $q$ will be odd primes.

However, it's possible to pick $p$ and $q$ so that $p-1=2p'$ and $q-1=2q'$, where $p'$ and $q'$ are both prime.  In that case $$\phi(n)=\phi(pq)=\phi(p)\phi(q)=2p'2q'=4p'q'$$ so that $\phi(n)$ at least has order four times a product of (still big) prime numbers.

We will not prove it, but it turns out this is enough to guarantee the existence of elements of orders $p'-1$ and $q'-1$ in $U_{\phi(pq)}$, just like we had elements of order $p-1$ in $U_p$.  To be precise, we get elements of order $$p'-1 = \frac{p-1}{2}-1\text{ and }q'-1=\frac{q-1}{2}-1$$ if $$\frac{p-1}{2}\text{ and }\frac{q-1}{2}$$ are both prime.  Here is an example of this with very small $p$ and $q$.

n = 7*11 phi = euler_phi(n) [mod(i,phi).multiplicative_order() for i in [1..phi] if gcd(i,phi)==1] 
       
[1, 4, 2, 4, 4, 2, 4, 2, 2, 4, 2, 4, 4, 2, 4, 2]
[1, 4, 2, 4, 4, 2, 4, 2, 2, 4, 2, 4, 4, 2, 4, 2]

Going backwards, we are looking for prime numbers $p',q'$ such that $2p'+1,2q'+1$ are also prime, and then we use $p=2p'+1$ and $q=2q'+1$ in RSA, finding an exponent that has big order in $U_{\phi(n)}$.   In this example, $p'=5$ and $q'=3$.

Such primes $p$ and $q$ are called Germain primes, for French mathematician Sophie Germain - the only female number theorist of note before the twentieth century.  We will see her - and them - again.

There are tons of other cryptographic applications one can do.  I just want to share one more.

Application 2 - Secret Sharing:

Suppose that three people work at a company with some trade secret, all of whom have clearance to know about the secret's details.  However, the company wants to avoid one of the three being bought off by a competitor and revealing it in an act of corporate espionage.  

So they need to devise a system where, in order to actually gain access to the details of the trade secret, one needs two of the people involved.  In a movie, you would have an impressive safe with three locks; each person would have a separate key to one of the locks, and the safe would be constructed so that any two of the keys would open it.

But real cryptography is not the movies! For one thing, the data is probably electronic, so it's really something we need to do digitally.  Cryptography provides the perfect way to deal with these issues.

What we will do is indeed give each person a key - a digital encryption key, of course.  Suppose the trade secret is digitally represented as a large number $K$.  Here are steps to create three different keys - any two of which, just like in the movie, will allow access to $K$.

  • Choose some prime $p>K$.
  • Choose three numbers $m_1<m_2<m_3$ which are:
    •  mutually coprime and coprime to $p$, i.e. $gcd(m_i,m_j)=1$ and $gcd(m_i,p)=1$.
    • AND such that $$m_1 m_2>pm_3$$
  • Let $M=m_1 m_2$.  
  • Now choose some $t<M/p$ at random.  Then the keys are as follows:
    • We have a modified secret $$K_0 = K + tp$$
    • Person $i$ gets the key $$k_1=K_0\text{ mod }(m_i)$$

Example:

Obviously, we'll want to see this in action. Suppose your secret was $K=4$.  Let's pick $p=7$, and numbers $11,13,16$.

K=4 p=7 m1,m2,m3=11,13,16 
       

We'll check quickly that $m_1m_2>pm_3$:

m1*m2>p*m3 
       
True
True

So $M=11\cdot 13=143$, and we can pick $t=15$ more or less randomly as being less than $M/p=143/7=20\frac{3}{7}$.

M=m1*m2 t=15 
       

So $$K_0=K+tp=4+15\cdot 7=109$$

K_0=K+t*p 
       

giving keys $k_i$ of $K_0$ modulo $m_i$:

k1,k2,k3 = mod(K_0,m1),mod(K_0,m2),mod(K_0,m3) k1;k2;k3 
       
10
5
13
10
5
13

What good do these do us?  Well, the Chinese Remainder Theorem allows us to reconstruct $K_0$ modulo $m_im_j$ with any two keys $k_i$ and $k_j$.  That may not seem like a lot - that just gives us things to within multiples of $m_im_j$.  

But by our choice of $M=m_1m_2>pm_3$, we know that $M/p>m_3$ (and hence $M/p>m_i$ as well).  So $$K_0=K+tp<p+tp=(t+1)p\leq (M/p)p=M$$  And certainly if $K_0<M$, then $K_0<m_im_j$, since $M$ is the smallest such product. So the CRT allows us to reconstruct $K_0$ uniquely, and then $K=K_0-tp$!  

Finally, note that just one person doesn't have enough information to get $K$, since that just tells that $$K_0\equiv k_i\text{ mod }(m_i)$$, so that $$K_0=k_i+\ell m_i$$ for all $\ell$ modulo $m_i$.  In our example, we can check that by hand, but with industrial-size numbers that would not be possible.

As a final note, we should point out that this doesn't just protect against one person defecting. It also provides protection against one of the three becoming incapacitated somehow. If all three were necessary to unlock the secret, the company is an illness or death or resignation away from its secret being irretrievably lost without a system of this type.

Let's actually reconstruct the secret $K$ in these cases. First, let's see that any two people do have enough information.

CRT(10,5,m1,m2); CRT(10,13,m1,m3);CRT(5,13,m2,m3) 
       
109
109
109
109
109
109
109-t*p 
       
4
4

Great! But even for this very small example, it's not clear to the lone person exactly which of this is right for $K_0$.

[10+i*m1 for i in [0..10]];[5+i*m2 for i in [0..10]];[13+i*m3 for i in [0..10]] 
       
[10, 21, 32, 43, 54, 65, 76, 87, 98, 109, 120]
[5, 18, 31, 44, 57, 70, 83, 96, 109, 122, 135]
[13, 29, 45, 61, 77, 93, 109, 125, 141, 157, 173]
[10, 21, 32, 43, 54, 65, 76, 87, 98, 109, 120]
[5, 18, 31, 44, 57, 70, 83, 96, 109, 122, 135]
[13, 29, 45, 61, 77, 93, 109, 125, 141, 157, 173]

It is not terribly hard to extend this to a system that works with spreading a secret known to $n$ in such a way that $k$ are needed to access it.

Example:

Here is one more example, with somewhat larger numbers! Just to see that it works.

K = encode('mathiscool');K 
       
68408084029415
68408084029415
p = next_prime(2*K);p 
       
136816168058837
136816168058837

So far, random.  Next, I'll choose a power of 2 which is similar in size to $p$, but somewhat bigger, to use as $m_3$.  Then hopefully I can pick $m_1$ and $m_2$ to be just a little bigger than the square root of $pm_3$ and we'll be set.

m3=2^50 m3 
       
1125899906842624
1125899906842624
a=floor(sqrt(p*m3)) m1=next_prime(a);m2=next_prime(next_prime(a)) m1;m2 
       
392480968802347
392480968802393
392480968802347
392480968802393

We check that $m_1m_2>pm_3$.

m1*m2>p*m3 
       
True
True

Now we calculate $M$ and pick $t<M/p$.

M=m1*m2; M 
       
154041310872046933232117616371
154041310872046933232117616371
t = ceil((M/p)/2); t 
       
562949953421450
562949953421450

Then $K_0=K+tp$, and we also get the $k_i$.

K_0 = K+t*p k1,k2,k3 = K_0%m1,K_0%m2,K_0%m3 K_0;k1;k2;k3 
       
77020655436023632821141883065
362445567476053
362445567476076
371690813245625
77020655436023632821141883065
362445567476053
362445567476076
371690813245625

Check that the CRT works:

CRT(k1,k2,m1,m2)-t*p;CRT(k1,k3,m1,m3)-t*p;CRT(k2,k3,m2,m3)-t*p 
       
68408084029415
68408084029415
68408084029415
68408084029415
68408084029415
68408084029415

Which is $K$!

print K 
       
68408084029415
68408084029415

There are lots and lots of other things one can do with these ideas.  Two of my favorites are finding ways to flip a coin over the Internet and how to find out if someone makes more money than you without them revealing their actual salary.  But that is enough for now.