The Illegal Prime Number

An illegal number is a number that represents information whose possession, publication or distribution is restricted by law in some jurisdiction. Because any digital file can be read as a single large integer, a restriction on a file is in effect a restriction on a number. An illegal prime is such a number that is also prime. The best known examples were produced in 2001 by Phil Carmody, a British programmer living near Helsinki, and encode DeCSS, a program that decrypts the copy protection used on commercial DVDs.

Background: CSS and DeCSS

Commercial Digital Versatile Discs, introduced in the late 1990s, protect their video with the Content Scramble System (CSS), a stream cipher using 40-bit keys. Licensed player manufacturers received the keys needed to decrypt a disc, and no licensed player existed for Linux.

In October 1999 a program called DeCSS was posted to the LiViD mailing list, a Linux video project. It was the work of three people, of whom only the Norwegian programmer Jon Lech Johansen, then aged 15, was publicly identified. Johansen later testified that he had written the program's user interface and that the decryption code came from an anonymous collaborator who had reverse-engineered a licensed software player whose key was poorly protected. Separately, the cryptographer Frank Stevenson published an analysis showing that the 40-bit cipher was weak enough to break by brute force in seconds.

Litigation

Two separate lines of litigation followed, and they rested on different laws. Member studios of the Motion Picture Association of America sued in New York under Section 1201 of the DMCA, which prohibits trafficking in circumvention technology. In Universal City Studios v. Reimerdes the court enjoined the magazine 2600 from posting DeCSS or even linking to it. On appeal, decided in 2001 as Universal City Studios v. Corley, the Second Circuit accepted that source code is speech protected by the First Amendment, but held that the injunction was a content-neutral restriction on its functional aspect and therefore permissible.

The DVD Copy Control Association sued separately in California, in DVD CCA v. Bunner, as a trade secret matter under state law rather than under the DMCA. That case ended in 2004 when the California Court of Appeal held that CSS had been so widely published that it was no longer a secret. Johansen himself was prosecuted in Norway under a computer misuse statute and acquitted in 2003, an acquittal upheld on appeal later the same year.

Protest encodings

David Touretzky, a computer scientist at Carnegie Mellon University, responded to the Reimerdes ruling by assembling a Gallery of CSS Descramblers, collecting representations of the algorithm that occupied the range between executable code and plain expression. Contributors produced the algorithm in C, Perl, Standard ML and Verilog, as a 456-stanza haiku by Seth Schoen, as songs and a dramatic reading, as a MIDI file, on greeting cards and T-shirts, and hidden steganographically inside GIF, JPEG and PNG images. Keith Winstein and Marc Horowitz reduced a working descrambler to a six-line Perl program called qrpff, short enough to print on a shirt. The gallery's argument was that no line drawn around executable code could avoid enclosing ordinary expression as well.

Carmody's first illegal prime

Carmody's aim was to place the data somewhere that could not readily be removed. Large primes are archived on the PrimePages for reasons of size and method alone, and a number's primality does not depend on any legal definition, so a prime encoding of the program would be difficult to purge from the mathematical record.

He began with a compact C implementation of the algorithm, compressed with gzip. Because gunzip stops at the end of the compressed stream and ignores whatever follows, extra bytes can be appended to the file without changing what it decompresses to. Reading the file as a big-endian integer, appending n bytes to a file whose value is g produces the number g · 256ⁿ + x, where x ranges over the values of the appended bytes. Searching that range for a prime leaves the compressed program intact. Carmody first tried a single appended byte, which yielded nothing, then two bytes, which succeeded. This construction is often compared to Dirichlet's theorem on arithmetic progressions, which states that for coprime a and b the progression a · k + b contains infinitely many primes. The comparison is an analogy rather than the operative guarantee, since the search here runs over a bounded interval; what makes it work in practice is that primes near this size remain about one in every few thousand odd numbers.

Candidates were screened with OpenPFGW, which trial divides and then applies a probable prime test, and survivors were certified with elliptic curve primality proving (ECPP) using Marcel Martin's program Titanix. The result, announced in March 2001, was a 1,401-digit prime that decompresses to the C source of the program.

Carmody has pointed out that this widely reported number was not the one that met his original goal, because at 1,401 digits it was too small to qualify for the PrimePages archive. For that he produced a second prime of 1,905 digits, sharing the same compressed prefix but followed by 210 zero bytes and a final byte with the value 99 (hexadecimal 63). Equivalently, the number has the form k × 256²¹¹ + 99, where k is the compressed-file prefix. At the time it was the tenth largest number ever proven prime by ECPP, and it entered the archive on that basis rather than for its contents.

The executable prime

Chris Caldwell, who maintains the PrimePages, later asked Carmody how hard it would be to build a prime that was itself a working program. Carmody answered in September 2001. Starting from efdtt.c, a very short implementation of the algorithm written by Charles Hannum, he compiled a Linux x86 ELF executable and stripped it down to 752 bytes by discarding the C entry mechanism, the C runtime library, unnecessary ELF sections and the section header. A file of that length corresponds to a number of 1,811 digits.

The file ended in a zero byte and was therefore even. The trailing bytes turned out to belong to Hannum's string constants, terminated by zeros that the stripped program no longer needed, so Carmody was free to change them. Varying two of those bytes gave 32,768 candidates, of which a probable prime was found and then certified by ECPP using Primo, Martin's successor to Titanix. The resulting 1,811-digit prime is not a compressed archive: written out in binary it is the executable itself, and requires no compiler and no decompression step.

Two related results came out of the same period. Asked also for the shortest possible executable prime, Carmody settled on 9923, a two-byte MS-DOS .COM file that does nothing but return. Hannum subsequently constructed an illegal prime without compression at all, by renaming variables in a short C source file until the file's byte sequence was prime.

Significance

• Numbers are jurisdiction-independent. Primality is a property of an integer and does not depend on where the integer is written down, which sits awkwardly with statutory definitions of a circumvention device.
• Code and expression. The Corley court held that source code is speech while allowing the restriction to stand on functional grounds. The executable prime collapses that distinction, since the same object is at once a number, a proof subject and a running program.
• Everything is a number. All digital media, text and software are stored as binary sequences, so any file can be read as one integer. The same reasoning reappeared in 2007, when a 128-bit AACS decryption key for HD DVD and Blu-ray was the subject of takedown notices and was republished in thousands of forms.

Explore More Prime Number Topics

• Different Types of Prime Numbers: Mersenne, Fermat, twin and Sophie Germain primes.
• A Very Large Prime Number: record primes with tens of millions of digits.
• Prime Number Money Prizes: cash awards for record prime discoveries.
• How to Check Whether a Number Is Prime: an overview of primality tests and an explanation of the methods used by this site's browser-based checker.
• The First 1,000 Prime Numbers: complete table of the first 1,000 primes.
• Prime Number Check: test an integer of up to 20,000 digits with our online checker.