The ElGamal Cryptosystem and Digital Rights Management

This section is about the ElGamal cryptosystem, which works well on an elliptic curves. This section draws on a paper by a computer hacker named Beale Screamer who cracked a ``Digital Rights Management'' (DRM) system.

The elliptic curve used in the DRM is an elliptic curve over the finite field $k=\mathbb{Z}/p\mathbb{Z}{}$ , where

$$p=785963102379428822376694789446897396207498568951.$$

In base 16 the number $p$ is

89ABCDEF012345672718281831415926141424F7,

which includes counting in hexadecimal, and digits of $e$ , $\pi$ , and $\sqrt{2}$ . The elliptic curve $E$ is

$$y^2 = x^3 + 317689081251325503476317476413827693272746955927x$$

$$\qquad +79052896607878758718120572025718535432100651934.$$

We have

$$\char93 E(k) = 785963102379428822376693024881714957612686157429,$$

and the group $E(k)$ is cyclic with generator

$$B = (771507216262649826170648268565579889907769254176,$$

$$\qquad 390157510246556628525279459266514995562533196655).$$

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 web site that sells music. After Nikita sends her credit card number, that web site allows Nikita to download a license file that allows her audio player to unlock and play juno.wma.

As we will see below, the license file was created using the ElGamal public-key cryptosystem in the group $E(k)$ . Nikita can now use her license file to unlock juno.wma. However, when she 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.

We now describe the ElGamal cryptosystem, which lends itself well to implementation in the group $E(\mathbb{Z}/p\mathbb{Z}{})$ . To illustrate ElGamal, 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 $\mathbb{Z}/p\mathbb{Z}{}$ , and a point $B\in E(\mathbb{Z}/p\mathbb{Z}{})$ , 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 Michael wishes to encrypt a message for Nikita. If the message is encoded as an element $P\in E(\mathbb{Z}/p\mathbb{Z}{})$ , Michael computes a random integer $r$ and the points $rB$ and $P+r(nB)$ on $E(\mathbb{Z}/p\mathbb{Z}{})$ . 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).$$

Remark 6.4   It also make sense to construct an ElGamal cryptosystem in the group $(\mathbb{Z}/p\mathbb{Z}{})^*$ .

Returning out our story, Nikita's license file is an encrypted message to her. It contains the pair of points $(rB, P+r(nB))$ , where

$$rB = (179671003218315746385026655733086044982194424660,$$

$$\qquad\quad 697834385359686368249301282675141830935176314718)$$

and

$$P+r(nB) = (137851038548264467372645158093004000343639118915,$$

$$\qquad\quad 110848589228676224057229230223580815024224875699).$$

When Nikita's computer plays juno.wma, it loads the secret key

$$n = 670805031139910513517527207693060456300217054473$$

into memory and computes

$$n(rB) = (328901393518732637577115650601768681044040715701,$$

$$\qquad 586947838087815993601350565488788846203887988162).$$

It then subtracts this from $P+r(nB)$ to obtain

$$P = (14489646124220757767,$$

$$\quad\qquad 669337780373284096274895136618194604469696830074).$$

The $x$ -coordinate $14489646124220757767$ is the key that unlocks juno.wma.

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.