Illegal prime number
The term illegal prime number is sometimes used in connection with certain prime numbers that are constructed in such a way that they can be converted into protected data in a known manner, for example in the source code of a program that bypasses copy protection mechanisms or encryption . Every digital information can be represented as a number, but the publication should be justified by the construction of special numbers such as large prime numbers. Whether the prime numbers found are actually considered illegal has not yet been negotiated in court.
background
Since 1996, commercial video DVDs have been encrypted with a digital rights management system , the Content Scramble System (CSS), which is supposed to prevent unauthorized playback and copying. On Linux operating systems, playing CSS-encrypted video DVDs was not possible at all. In 1999 a group of hackers developed the DeCSS computer program , with which such video DVDs can be decoded, and made it available as free software . Litigation ensued, in which various judges in the United States ruled that distribution of this program was illegal under the Digital Millennium Copyright Act (DMCA).
This sparked a wave of indignation. The protest against the prosecution of DeCSS co-author Jon Lech Johansen and against the legal prohibition on publishing the DeCSS Code in the US took many forms. Some use steganography to embed the program in other elements such as images or sounds. Another protest reaction was the search for a representation of the illegal code in a form that was intrinsically archivable . Since the bits that make up a computer program also represent a number, the plan was drawn up to put DeCSS in a number that had a special property that made it archivable and publishable.
The primality of a number is a fundamental property that is outside of the realm regulated by law. By Dirichlet's theorem guarantees that a particular method many such numbers can be made infinite. The large prime number database of Prime Pages stores the 20 largest known prime numbers in various forms; one of them is the primality proof using the Elliptic Curve Primality Proving Algorithm (ECPP). If the number found was large enough and proved to be prime with ECPP, it would be published.
discovery
In March 2001, Phil Carmody constructed a 1401-digit prime number that yields the DeCSS C source code when its binary representation is decompressed with gzip . This prime number could thus be viewed as an “illegal prime number” in the USA.
When searching for such a number, one takes advantage of the fact that the gzip program ignores all bytes after a compressed file terminated by zero. The file and the number it represents can therefore be changed by adding additional bytes without affecting the decompressed file. Based on Dirichlet's theorem, a set of possible prime numbers was generated, all of which, when decompressed, yield DeCSS's C code. Of these numbers, several have been identified as “possibly prime” by the open source program OpenPFGW , and one of them has been proven to be prime by the ECPP algorithm implemented in Titanix software . Even when it was discovered, this 1401-digit number was too small to make it into a place worth mentioning in the prime numbers found by ECPP . So Carmody looked for another prime number with 1905 digits using the same scheme. At the time of its discovery, this was the tenth largest prime number found by ECPP.
Shortly afterwards, Phil Carmody also found an 1811-digit prime number that works without the gzip program and is a program that can be executed directly on Linux .
See also
Web links
- Steganographic Gallery and Illegal Prime Numbers
- Info on the illegal prime number
- Prime decrypts DVDs