The illegal prime

A message (harmless text only)

 Make it prime

Read a message back

Paste a prime made above

 Read it

 Use the prime above

Nothing you type here leaves your browser.

An illegal prime is a prime number that, read as a file, is a program or document someone is forbidden to distribute. The first one, found in March 2001 by Phil Carmody, has 1,401 digits, and its binary form is a compressed copy of the source code of DeCSS, a program that decrypts DVDs. It posed a question: if a program is illegal to publish, and a number is that program, is the number illegal? The tool above turns harmless text into a prime so you can see how it's done. This page doesn't reproduce the prime or the program.

Where DeCSS came from

DVDs were encrypted with the Content Scramble System (CSS), a weak cipher built to keep discs from playing on unlicensed players. In late 1999 a group that included a Norwegian teenager, Jon Lech Johansen, wrote DeCSS, which broke CSS so the discs could play on Linux, where no licensed player existed. The film studios and the DVD licensing body sued over its distribution. In Universal City Studios v. Reimerdes, Judge Lewis Kaplan of the federal court in New York ruled in 2000 that posting DeCSS, and knowingly linking to sites that did, violated the Digital Millennium Copyright Act's ban on circumvention tools (111 F. Supp. 2d 346). The Second Circuit affirmed in November 2001, in Universal City Studios v. Corley (273 F.3d 429), while accepting that computer code has First Amendment protection. The case made DeCSS the standard example in arguments over whether code is speech.

Turning a file into a prime

Any file is already a number. Write its bytes one after another and read them as one big base-256 number: the text "Hi" is 72 × 256 + 105 = 18,537. That number usually isn't prime, but you can make it prime without changing what the file means, by using some slack. Many formats ignore a few extra bytes at the end. The gzip format used for DeCSS, for instance, can be followed by extra bytes that the decompressor ignores. So the recipe is:

1. Take the file and put two (or more) free bytes after it.
2. Try the possible values of the free bytes, one after another, testing each resulting number for primality with Miller–Rabin.
3. Stop at the first prime. The prime number is the file, plus two harmless bytes.

It works because primes are so common. A number of 1,401 digits is prime with probability about 1 in ln(10¹⁴⁰¹) = 3,226, or 1 in 1,613 among odd numbers, so a few thousand attempts are enough, and the chance of failing with 65,536 free values is vanishingly small (the same density the RSA key-size page uses to find key primes). The tool above does exactly this to your text, with two free bytes at the end, and reads it back by dropping them. Carmody's prime was found the same way, with the added step of certifying it with a primality proof instead of a probabilistic test. A prime of 1,401 digits is about 4,654 bits, or 582 bytes, and a compressed C program is that small. Carmody later made one that's also an executable: the number, written in binary, runs on an x86 Linux machine as a DeCSS program.

Is a number illegal?

The stunt was built to ask exactly that, and no court has ruled on it. The legal argument is about distributing a circumvention tool, and the prime is the tool under an encoding, as much as a zip file is. But a number isn't a communication the way a file is, and every number is "a file" under some encoding: 18,537 is the text "Hi" under one reading and something else under another. The deeper point is the one the prime makes by being prime. Whether a number is prime depends on nothing but arithmetic, and on no law. David Touretzky of Carnegie Mellon made the same point differently, in his Gallery of DeCSS Descramblers, which presents the algorithm as poems, songs and art. Similar fights came back in 2007, when demands were made to remove a 128-bit key for another disc encryption standard, AACS, from websites. Read these as stories about the limits of regulating information. Nothing on this page is legal advice.

How this relates to cipher.ink

It doesn't decrypt anything, and the prime above isn't encrypted: anyone can read the message back, as the tool shows. That makes it an encoding, not a cipher, like base64. The story is still useful for anyone thinking about encryption, because it shows that to the law and to mathematics, a secret and a number are different things. cipher.ink's design assumes the opposite of what DeCSS's creators assumed: the cipher is public (Kerckhoffs's principle) and only the key is secret. CSS broke because it was a weak, secret-by-obscurity design with a 40-bit key.

Common questions