Illegal prime
Encyclopedia
An illegal prime is a prime number
that represents information that it is forbidden to possess or distribute. One of the first illegal primes was discovered in 2001. When interpreted in a particular way, it describes a computer program
that bypasses the digital rights management
scheme used on DVD
s. Distribution of such a program in the United States
is illegal under the Digital Millennium Copyright Act
. An illegal prime is a kind of illegal number
.
One of the earliest illegal prime numbers was generated in March 2001 by Phil Carmody. Its binary
representation corresponds to a compressed
version of the C
source code
of a computer program
implementing the DeCSS
decryption algorithm, which can be used by a computer to circumvent a DVD's copy protection
.
Protests against the indictment of DeCSS author Jon Johansen and legislation prohibiting publication of DeCSS code took many forms. One of them was the representation of the illegal code in a form that had an intrinsically archivable quality. Since the bits making up a computer program also represent a number, the plan was for the number to have some special property that would make it archivable and publishable (one method was to print it on a T-shirt). The primality of a number is a fundamental property of number theory
and is therefore not dependent on legal definitions of any particular jurisdiction.
The large prime database of The Prime Pages
website records the top 20 primes of various special forms; one of them is proof of primality using the elliptic curve primality proving
(ECPP) algorithm
. Thus, if the number were large enough and proved prime using ECPP, it would be published.
compression program ignores bytes after the end of a null terminated
compressed file, a set of candidate primes was generated, each of which would result in the DeCSS C code when unzipped. Of these, several were identified as probable prime
using the open source
program OpenPFGW, and one of them was proved prime using the ECPP algorithm implemented by the Titanix software. Even at the time of discovery in 2001, this 1401-digit number was too small to be mentioned, so Carmody created a 1905-digit prime that was the tenth largest prime found using ECPP.
Following this, Carmody also discovered another prime, this one being directly executable
machine language for Linux
i386
, implementing the same functionality.
gives the 1401-digit number as:
4 85650 78965 73978 29309 84189 46942 86137 70744 20873 51357 92401 96520 73668 69851 34010 47237 44696 87974 39926 11751 09737 77701 02744 75280 49058 83138 40375 49709 98790 96539 55227 01171 21570 25974 66699 32402 26834 59661 96060 34851 74249 77358 46851 88556 74570 25712 54749 99648 21941 84655 71008 41190 86259 71694 79707 99152 00486 67099 75923 59606 13207 25973 79799 36188 60631 69144 73588 30024 53369 72781 81391 47979 55513 39994 93948 82899 84691 78361 00182 59789 01031 60196 18350 34344 89568 70538 45208 53804 58424 15654 82488 93338 04747 58711 28339 59896 85223 25446 08408 97111 97712 76941 20795 86244 05471 61321 00500 64598 20176 96177 18094 78113 62200 27234 48272 24932 32595 47234 68800 29277 76497 90614 81298 40428 34572 01463 48968 54716 90823 54737 83566 19721 86224 96943 16227 16663 93905 54302 41564 73292 48552 48991 22573 94665 48627 14048 21171 38124 38821 77176 02984 12552 44647 44505 58346 28144 88335 63190 27253 19590 43928 38737 64073 91689 12579 24055 01562 08897 87163 37599 91078 87084 90815 90975 48019 28576 84519 88596 30532 38234 90558 09203 29996 03234 47114 07760 19847 16353 11617 13078 57608 48622 36370 28357 01049 61259 56818 46785 96533 31007 70179 91614 67447 25492 72833 48691 60006 47585 91746 27812 12690 07351 83092 41530 10630 28932 95665 84366 20008 00476 77896 79843 82090 79761 98594 93646 30938 05863 36721 46969 59750 27968 77120 57249 96666 98056 14533 82074 12031 59337 70309 94915 27469 18356 59376 21022 20068 12679 82734 45760 93802 03044 79122 77498 09179 55938 38712 10005 88766 68925 84487 00470 77255 24970 60444 65212 71304 04321 18261 01035 91186 47666 29638 58495 08744 84973 73476 86142 08805 29443.
ELF
executable that reads CSS-encrypted data and outputs the decrypted data.
49310 83597 02850 19002 75777 67239 07649 57284 90777 21502 08632 08075 01840 97926 27885 09765 88645 57802 01366 00732 86795 44734 11283 17353 67831 20155 75359 81978 54505 48115 71939 34587 73300 38009 93261 95058 76452 50238 20408 11018 98850 42615 17657 99417 04250 88903 70291 19015 87003 04794 32826 07382 14695 41570 33022 79875 57681 89560 16240 30064 11151 69008 72879 83819 42582 71674 56477 48166 84347 92846 45809 29131 53186 00700 10043 35318 93631 93439 12948 60445 03709 91980 04770 94629 21558 18071 11691 53031 87628 84778 78354 15759 32891 09329 54473 50881 88246 54950 60005 01900 62747 05305 38116 42782 94267 47485 34965 25745 36815 11706 55028 19055 52656 22135 31463 10421 00866 28679 71144 46706 36692 19825 86158 11125 15556 50481 34207 68673 23407 65505 48591 08269 56266 69306 62367 99702 10481 23965 62518 00681 83236 53959 34839 56753 57557 53246 19023 48106 47009 87753 02795 61868 92925 38069 33052 04238 14996 99454 56945 77413 83356 89906 00587 08321 81270 48611 33682 02651 59051 66351 87402 90181 97693 93767 78529 28722 10955 04129 25792 57381 86605 84501 50552 50274 99477 18831 29310 45769 80909 15304 61335 94190 30258 81320 59322 77444 38525 50466 77902 45186 97062 62778 88919 79580 42306 57506 15669 83469 56177 97879 65920 16440 51939 96071 69811 12615 19561 02762 83233 98257 91423 32172 69614 43744 38105 64855 29348 87634 92103 09887 02878 74532 33132 53212 26786 33283 70279 25099 74996 94887 75936 91591 76445 88032 71838 47402 35933 02037 48885 06755 70658 79194 61134 19323 07814 85443 64543 75113 20709 86063 90746 41756 41216 35042 38800 29678 08558 67037 03875 09410 76982 11837 65499 20520 43682 55854 64228 85024 29963 32268 53691 24648 55000 75591 66402 47292 40716 45072 53196 74499 95294 48434 74190 21077 29606 82055 81309 23626 83798 79519 66199 79828 55258 87161 09613 65617 80745 66159 24886 60889 81645 68541 72136 29208 46656 27913 14784 66791 55096 51543 10113 53858 62081 96875 83688 35955 77893 91454 53935 68199 60988 08540 47659 07358 97289 89834 25047 12891 84162 65878 96821 85380 87956 27903 99786 29449 39760 54675 34821 25675 01215 17082 73710 76462 70712 46753 21024 83678 15940 00875 05452 54353 7.
numbers from an electronic publication to a text file will typically result in a stream of byte
s where each character (decimal digit or space) is encoded in one byte using the ASCII
encoding. The particularity of these numbers is that, when written in base 2
, the resulting stream of bit
s can also be interpreted as the content of a gzip
or executable
file. Converting such big numbers to base 2 and writing the resulting stream of bits to a file is a nontrivial process. Below is a go
source code
of a program that takes a number on the command line and writes a binary representation to the standard output
.
package main
import (
"big"
"fmt"
"os"
"strings"
)
func main {
if len(os.Args) != 2 {
fmt.Fprintf(os.Stderr, "Usage: %s\n", os.Args[0])
os.Exit(1)
}
number_str := strings.Replace(os.Args[1], " ", "", -1)
number, ok := new(big.Int).SetString(number_str, 0)
if !ok {
fmt.Fprintf(os.Stderr, "Failed to convert %q to big integer.\n", number_str)
os.Exit(1)
}
os.Stdout.Write(number.Bytes)
}
Given the appropriate numbers, this program will output the gzip and executable files described above.
Or as a VB.NET subroutine:
Sub Write_Binary_File_From_Large_Number(ByVal number As String, ByVal filename As String)
Dim bigint As Numerics.BigInteger = Numerics.BigInteger.Parse(number.Replace(" ", String.Empty))
Dim byteArray As Byte = bigint.ToByteArray
Array.Reverse(byteArray)
File.WriteAllBytes(byteArray, filename);
End Sub
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
that represents information that it is forbidden to possess or distribute. One of the first illegal primes was discovered in 2001. When interpreted in a particular way, it describes a computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
that bypasses the digital rights management
Digital rights management
Digital rights management is a class of access control technologies that are used by hardware manufacturers, publishers, copyright holders and individuals with the intent to limit the use of digital content and devices after sale. DRM is any technology that inhibits uses of digital content that...
scheme used on DVD
DVD
A DVD is an optical disc storage media format, invented and developed by Philips, Sony, Toshiba, and Panasonic in 1995. DVDs offer higher storage capacity than Compact Discs while having the same dimensions....
s. Distribution of such a program in the United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
is illegal under the Digital Millennium Copyright Act
Digital Millennium Copyright Act
The Digital Millennium Copyright Act is a United States copyright law that implements two 1996 treaties of the World Intellectual Property Organization . It criminalizes production and dissemination of technology, devices, or services intended to circumvent measures that control access to...
. An illegal prime is a kind of illegal number
Illegal number
An illegal number is a number that represents information which is illegal to possess, utter or propagate. Any information that can be represented in binary format is representable as a number, and therefore if the information itself is illegal in some way, the pure number itself may be...
.
Background
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
representation corresponds to a compressed
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
version of the C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
of a computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
implementing the DeCSS
DeCSS
DeCSS is a computer program capable of decrypting content on a commercially produced DVD video disc. Before the release of DeCSS, there was no way for computers running a Linux-based operating system to play video DVDs....
decryption algorithm, which can be used by a computer to circumvent a DVD's copy protection
Copy protection
Copy protection, also known as content protection, copy obstruction, copy prevention and copy restriction, refer to techniques used for preventing the reproduction of software, films, music, and other media, usually for copyright reasons.- Terminology :Media corporations have always used the term...
.
Protests against the indictment of DeCSS author Jon Johansen and legislation prohibiting publication of DeCSS code took many forms. One of them was the representation of the illegal code in a form that had an intrinsically archivable quality. Since the bits making up a computer program also represent a number, the plan was for the number to have some special property that would make it archivable and publishable (one method was to print it on a T-shirt). The primality of a number is a fundamental property of number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and is therefore not dependent on legal definitions of any particular jurisdiction.
The large prime database of The Prime Pages
Prime pages
The Prime Pages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" lists for primes of various forms...
website records the top 20 primes of various special forms; one of them is proof of primality using the elliptic curve primality proving
Elliptic curve primality proving
Elliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number . It is a general-purpose algorithm, meaning it does not depend on the number being of a special form...
(ECPP) algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
. Thus, if the number were large enough and proved prime using ECPP, it would be published.
Discovery
By exploitation of the fact that the gzipGzip
Gzip is any of several software applications used for file compression and decompression. The term usually refers to the GNU Project's implementation, "gzip" standing for GNU zip. It is based on the DEFLATE algorithm, which is a combination of Lempel-Ziv and Huffman coding...
compression program ignores bytes after the end of a null terminated
Null character
The null character , abbreviated NUL, is a control character with the value zero.It is present in many character sets, including ISO/IEC 646 , the C0 control code, the Universal Character Set , and EBCDIC...
compressed file, a set of candidate primes was generated, each of which would result in the DeCSS C code when unzipped. Of these, several were identified as probable prime
Probable prime
In number theory, a probable prime is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions...
using the open source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
program OpenPFGW, and one of them was proved prime using the ECPP algorithm implemented by the Titanix software. Even at the time of discovery in 2001, this 1401-digit number was too small to be mentioned, so Carmody created a 1905-digit prime that was the tenth largest prime found using ECPP.
Following this, Carmody also discovered another prime, this one being directly executable
Executable
In computing, an executable file causes a computer "to perform indicated tasks according to encoded instructions," as opposed to a data file that must be parsed by a program to be meaningful. These instructions are traditionally machine code instructions for a physical CPU...
machine language for Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
i386
Intel 80386
The Intel 80386, also known as the i386, or just 386, was a 32-bit microprocessor introduced by Intel in 1985. The first versions had 275,000 transistors and were used as the central processing unit of many workstations and high-end personal computers of the time...
, implementing the same functionality.
The first illegal prime number
The RegisterThe Register
The Register is a British technology news and opinion website. It was founded by John Lettice, Mike Magee and Ross Alderson in 1994 as a newsletter called "Chip Connection", initially as an email service...
gives the 1401-digit number as:
4 85650 78965 73978 29309 84189 46942 86137 70744 20873 51357 92401 96520 73668 69851 34010 47237 44696 87974 39926 11751 09737 77701 02744 75280 49058 83138 40375 49709 98790 96539 55227 01171 21570 25974 66699 32402 26834 59661 96060 34851 74249 77358 46851 88556 74570 25712 54749 99648 21941 84655 71008 41190 86259 71694 79707 99152 00486 67099 75923 59606 13207 25973 79799 36188 60631 69144 73588 30024 53369 72781 81391 47979 55513 39994 93948 82899 84691 78361 00182 59789 01031 60196 18350 34344 89568 70538 45208 53804 58424 15654 82488 93338 04747 58711 28339 59896 85223 25446 08408 97111 97712 76941 20795 86244 05471 61321 00500 64598 20176 96177 18094 78113 62200 27234 48272 24932 32595 47234 68800 29277 76497 90614 81298 40428 34572 01463 48968 54716 90823 54737 83566 19721 86224 96943 16227 16663 93905 54302 41564 73292 48552 48991 22573 94665 48627 14048 21171 38124 38821 77176 02984 12552 44647 44505 58346 28144 88335 63190 27253 19590 43928 38737 64073 91689 12579 24055 01562 08897 87163 37599 91078 87084 90815 90975 48019 28576 84519 88596 30532 38234 90558 09203 29996 03234 47114 07760 19847 16353 11617 13078 57608 48622 36370 28357 01049 61259 56818 46785 96533 31007 70179 91614 67447 25492 72833 48691 60006 47585 91746 27812 12690 07351 83092 41530 10630 28932 95665 84366 20008 00476 77896 79843 82090 79761 98594 93646 30938 05863 36721 46969 59750 27968 77120 57249 96666 98056 14533 82074 12031 59337 70309 94915 27469 18356 59376 21022 20068 12679 82734 45760 93802 03044 79122 77498 09179 55938 38712 10005 88766 68925 84487 00470 77255 24970 60444 65212 71304 04321 18261 01035 91186 47666 29638 58495 08744 84973 73476 86142 08805 29443.
The first illegal executable prime number
The following 1811-digit prime number (discovered by Phil Carmody) can represent a non-compressed i386Intel 80386
The Intel 80386, also known as the i386, or just 386, was a 32-bit microprocessor introduced by Intel in 1985. The first versions had 275,000 transistors and were used as the central processing unit of many workstations and high-end personal computers of the time...
ELF
Executable and Linkable Format
In computing, the Executable and Linkable Format is a common standard file format for executables, object code, shared libraries, and core dumps. First published in the System V Application Binary Interface specification, and later in the Tool Interface Standard, it was quickly accepted among...
executable that reads CSS-encrypted data and outputs the decrypted data.
49310 83597 02850 19002 75777 67239 07649 57284 90777 21502 08632 08075 01840 97926 27885 09765 88645 57802 01366 00732 86795 44734 11283 17353 67831 20155 75359 81978 54505 48115 71939 34587 73300 38009 93261 95058 76452 50238 20408 11018 98850 42615 17657 99417 04250 88903 70291 19015 87003 04794 32826 07382 14695 41570 33022 79875 57681 89560 16240 30064 11151 69008 72879 83819 42582 71674 56477 48166 84347 92846 45809 29131 53186 00700 10043 35318 93631 93439 12948 60445 03709 91980 04770 94629 21558 18071 11691 53031 87628 84778 78354 15759 32891 09329 54473 50881 88246 54950 60005 01900 62747 05305 38116 42782 94267 47485 34965 25745 36815 11706 55028 19055 52656 22135 31463 10421 00866 28679 71144 46706 36692 19825 86158 11125 15556 50481 34207 68673 23407 65505 48591 08269 56266 69306 62367 99702 10481 23965 62518 00681 83236 53959 34839 56753 57557 53246 19023 48106 47009 87753 02795 61868 92925 38069 33052 04238 14996 99454 56945 77413 83356 89906 00587 08321 81270 48611 33682 02651 59051 66351 87402 90181 97693 93767 78529 28722 10955 04129 25792 57381 86605 84501 50552 50274 99477 18831 29310 45769 80909 15304 61335 94190 30258 81320 59322 77444 38525 50466 77902 45186 97062 62778 88919 79580 42306 57506 15669 83469 56177 97879 65920 16440 51939 96071 69811 12615 19561 02762 83233 98257 91423 32172 69614 43744 38105 64855 29348 87634 92103 09887 02878 74532 33132 53212 26786 33283 70279 25099 74996 94887 75936 91591 76445 88032 71838 47402 35933 02037 48885 06755 70658 79194 61134 19323 07814 85443 64543 75113 20709 86063 90746 41756 41216 35042 38800 29678 08558 67037 03875 09410 76982 11837 65499 20520 43682 55854 64228 85024 29963 32268 53691 24648 55000 75591 66402 47292 40716 45072 53196 74499 95294 48434 74190 21077 29606 82055 81309 23626 83798 79519 66199 79828 55258 87161 09613 65617 80745 66159 24886 60889 81645 68541 72136 29208 46656 27913 14784 66791 55096 51543 10113 53858 62081 96875 83688 35955 77893 91454 53935 68199 60988 08540 47659 07358 97289 89834 25047 12891 84162 65878 96821 85380 87956 27903 99786 29449 39760 54675 34821 25675 01215 17082 73710 76462 70712 46753 21024 83678 15940 00875 05452 54353 7.
Using the numbers
Simply copying the decimalDecimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
numbers from an electronic publication to a text file will typically result in a stream of byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
s where each character (decimal digit or space) is encoded in one byte using the ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
encoding. The particularity of these numbers is that, when written in base 2
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
, the resulting stream of bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s can also be interpreted as the content of a gzip
Gzip
Gzip is any of several software applications used for file compression and decompression. The term usually refers to the GNU Project's implementation, "gzip" standing for GNU zip. It is based on the DEFLATE algorithm, which is a combination of Lempel-Ziv and Huffman coding...
or executable
Executable
In computing, an executable file causes a computer "to perform indicated tasks according to encoded instructions," as opposed to a data file that must be parsed by a program to be meaningful. These instructions are traditionally machine code instructions for a physical CPU...
file. Converting such big numbers to base 2 and writing the resulting stream of bits to a file is a nontrivial process. Below is a go
Go (programming language)
Go is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
of a program that takes a number on the command line and writes a binary representation to the standard output
Standard streams
In Unix and Unix-like operating systems , as well as certain programming language interfaces, the standard streams are preconnected input and output channels between a computer program and its environment when it begins execution...
.
package main
import (
"big"
"fmt"
"os"
"strings"
)
func main {
if len(os.Args) != 2 {
fmt.Fprintf(os.Stderr, "Usage: %s
os.Exit(1)
}
number_str := strings.Replace(os.Args[1], " ", "", -1)
number, ok := new(big.Int).SetString(number_str, 0)
if !ok {
fmt.Fprintf(os.Stderr, "Failed to convert %q to big integer.\n", number_str)
os.Exit(1)
}
os.Stdout.Write(number.Bytes)
}
Given the appropriate numbers, this program will output the gzip and executable files described above.
Or as a VB.NET subroutine:
Sub Write_Binary_File_From_Large_Number(ByVal number As String, ByVal filename As String)
Dim bigint As Numerics.BigInteger = Numerics.BigInteger.Parse(number.Replace(" ", String.Empty))
Dim byteArray As Byte = bigint.ToByteArray
Array.Reverse(byteArray)
File.WriteAllBytes(byteArray, filename);
End Sub
See also
- AACS encryption key controversyAACS encryption key controversyA controversy surrounding the AACS cryptographic key arose in April 2007 when the Motion Picture Association of America and the Advanced Access Content System Licensing Administrator, LLC began issuing demand letters to websites publishing a 128-bit number, represented in hexadecimal as 09 F9 11...
- Texas Instruments signing key controversyTexas Instruments signing key controversyThe Texas Instruments signing key controversy refers to the controversy which resulted from Texas Instruments' response to a project to factorize the 512-bit RSA cryptographic keys needed to write custom firmware to TI devices.-Project:...
- Prior artPrior artPrior art , in most systems of patent law, constitutes all information that has been made available to the public in any form before a given date that might be relevant to a patent's claims of originality...