All published worksheets from http://sagenb.org
Image: ubuntu2004
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 .
- Empirical evidence: Discrete log in much harder than in , 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
- Publically on .
- Michael sends with random (and secret).
- Nikita sends with random (and secret).
- The shared secret is , which both can easily compute, but nobody else can easily compute.
Shared secret = :
There is no direct analogue of RSA on an elliptic curve?!
Recall: RSA involves working in and keeping the factorization of secret. It allows one to do things that Diffie-Hellman doesn't, including publishing a public key (an exponent ), 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 . 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:
Question: How could you construct your own "nerdy prime"?
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.
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 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 over , and a point , and
publishes , , and . She also chooses a random integer ,
which she keeps secret, and publishes . Her public key is the
four-tuple .
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 ,
Microsoft computes a random integer and the
points and on .
Then is encrypted as the pair
. To decrypt the encrypted message,
Nikita multiplies by her secret key
to find , then subtracts this from
to obtain
Returning to our story, Nikita's license file is an encrypted message
to her. It contains the pair of points , where
The -coordinate is the key that unlocks juno.wma (the music file).
If Nikita knew the private key that her computer generated, she
could compute 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 ,
which is not a huge surprise since 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