Math 414: ECC 2010-03-05

700 days ago by wstein

Elliptic Curve Cryptography

  • Independently introduced by Neal Koblitz (here at UW) and Victor Miller (in Princeton) in the mid 1980s. 
  • Uses group of points on an elliptic curve instead of the integers modulo n.
  • Empirical evidence: Discrete log in E(\ZZ/p\ZZ) much harder than in (\ZZ/p\ZZ)^*, hence one can use much smaller key sizes.
  • Application: license keys for Microsoft Windows are shorter to type in
 
       

Diffie-Hellman Key Exchange on an Elliptic Curve

  1. Publically on Q \in E(\ZZ/p\ZZ).
  2. Michael sends mQ with m random (and secret).
  3. Nikita sends nQ with n random (and secret).
  4. The shared secret is mnQ, which both can easily compute, but nobody else can easily compute.
p = next_prime(10^30) E = EllipticCurve(GF(p), [7,1]) Q = E([0,1]) 
       
time E.cardinality().factor() 
        
2 * 3^2 * 5 * 43 * 15913 * 60613577603 * 267896508833
Time: CPU 0.02 s, Wall: 0.02 s
2 * 3^2 * 5 * 43 * 15913 * 60613577603 * 267896508833
Time: CPU 0.02 s, Wall: 0.02 s
Q.additive_order() 
        
66666666666666630906801278646
66666666666666630906801278646
m = ZZ.random_element(2,p); mQ = m*Q; print mQ 
        
(119901751680804203067680342657 : 464458077091323588895285485361 : 1)
(119901751680804203067680342657 : 464458077091323588895285485361 : 1)
n = ZZ.random_element(2,p); nQ = n*Q; print nQ 
        
(997266071707958828539293118613 : 524579529383887053708091174057 : 1)
(997266071707958828539293118613 : 524579529383887053708091174057 : 1)

Shared secret = mnQ:
m*nQ 
        
(725327750899527824758631414965 : 947924444229864748024362125753 : 1)
(725327750899527824758631414965 : 947924444229864748024362125753 : 1)
n*mQ 
        
(725327750899527824758631414965 : 947924444229864748024362125753 : 1)
(725327750899527824758631414965 : 947924444229864748024362125753 : 1)
 
       

There is no direct analogue of RSA on an elliptic curve?!

Recall: RSA involves working in \ZZ/ pq \ZZ and keeping the factorization of pq secret.  It allows one to do things that Diffie-Hellman doesn't, including publishing a public key (an exponent e), getting messages, digital signatures, etc. 

 

However, there is another cryptosystem called ElGamal that has similar good properties to RSA, but works using an elliptic curve group (or even the group (\ZZ/p\ZZ)^*.  It was used by Microsoft in one of their first ever DRM (=digital rights management) schemes a few years ago:

Beale Screamer Link

We define the parameters of Microsoft's DRM cryptosystem:
p=785963102379428822376694789446897396207498568951 
       
len(str(p)) 
        
48
48
p.str(16) 
        
'89abcdef012345672718281831415926141424f7'
'89abcdef012345672718281831415926141424f7'

Question: How could you construct your own "nerdy prime"?
E = EllipticCurve(GF(p), [317689081251325503476317476413827693272746955927, 79052896607878758718120572025718535432100651934]) E 
        
Elliptic Curve defined by y^2 = x^3 +
317689081251325503476317476413827693272746955927*x +
79052896607878758718120572025718535432100651934 over Finite Field of
size 785963102379428822376694789446897396207498568951
Elliptic Curve defined by y^2 = x^3 + 317689081251325503476317476413827693272746955927*x + 79052896607878758718120572025718535432100651934 over Finite Field of size 785963102379428822376694789446897396207498568951
time E.cardinality() 
        
785963102379428822376693024881714957612686157429
Time: CPU 0.00 s, Wall: 0.06 s
785963102379428822376693024881714957612686157429
Time: CPU 0.00 s, Wall: 0.06 s
is_prime(E.cardinality()) 
        
True
True
P = E([771507216262649826170648268565579889907769254176, 390157510246556628525279459266514995562533196655]) 
       
P.order() 
        
785963102379428822376693024881714957612686157429
785963102379428822376693024881714957612686157429

Our heroes Nikita and Michael share
digital music when they are not out fighting terrorists.  When Nikita
installed the DRM software on her computer, it generated a private key


n = 670805031139910513517527207693060456300217054473,

which it hides in bits and pieces of files.  In order for Nikita to
play Juno Reactor's latest hit juno.wma, her web browser contacts a
website that sells music.  After Nikita sends her credit card number,
that website allows Nikita to download a license file that allows
her audio player to unlock and play juno.wma.
# Nikita's private key n = 670805031139910513517527207693060456300217054473 
       

When Nikita shares both juno.wma and the license file with
Michael, he is frustrated because even with the license, his computer
still does not play juno.wma.  This is because Michael's computer
does not know Nikita's computer's private key (the integer n above),
so Michael's computer can not decrypt the license file.
 
       

To illustrate the ElGamal cryptosystem, we
describe how Nikita would set up an ElGamal cryptosystem that anyone
could use to encrypt messages for her.  Nikita chooses a prime p, an
elliptic curve E over \ZZ/p\ZZ, and a point B\in E(\ZZ/p\ZZ), and
publishes p, E, and B.  She also chooses a random integer n,
which she keeps secret, and publishes nB.  Her public key is the
four-tuple (p,E,B, nB).
 
       

Suppose Microsoft wishes to encrypt a message ("you can play this music" -- the license file) for Nikita.
If the message is encoded as an element P\in E(\ZZ/p\ZZ),
Microsoft computes a random integer r and the
points rB and P+r(nB) on E(\ZZ/p\ZZ).  
Then P is encrypted as the pair
(rB, P+r(nB)). To decrypt the encrypted message,
Nikita multiplies rB by her secret key n
to find n(rB) = r(nB), then subtracts this from
P+r(nB) to obtain
 

P = P+r(nB)-r(nB).

 

Returning to our story, Nikita's license file is an encrypted message
to her.  It contains the pair of points (rB,P+r(nB)), where
rB = E([179671003218315746385026655733086044982194424660, 697834385359686368249301282675141830935176314718]) 
       
P_plus_rnB = E([137851038548264467372645158093004000343639118915, 110848589228676224057229230223580815024224875699]) 
       
P_plus_rnB - n*rB 
        
(14489646124220757767 : 669337780373284096274895136618194604469696830074
: 1)
(14489646124220757767 : 669337780373284096274895136618194604469696830074 : 1)

The x-coordinate 14489646124220757767 is the  key that unlocks juno.wma (the music file).

 

If Nikita knew the private key n that her computer generated, she
could compute P herself and unlock juno.wma and share her
music with Michael.  Beale Screamer found a weakness in the
implementation of this system that allows Nikita to detetermine n,
which is not a huge surprise since n is stored on her computer after
all.

Implementing DRM schemes that really work is evidently difficult: Ubisoft DRM cracked in a day

More about elliptic curve cryptography:

See Certicom challenge website: http://www.certicom.com/index.php/the-certicom-ecc-challenge
len(p.str(2)) 
        
160
160