Illegal prime numbers: do they exist? Yes, but they are not legally attackable

What is the least common multiple between prime numbers, a purely mathematical concept, and computer science? For those who do not know it is safety! And it is mainly for this reason that they are particularly fascinating and there are real paid bounties on the new prime numbers that are discovered. But did you know that some of these prime numbers are, legally speaking, "illegal"?

The search for illegal prime numbers, however, is a sort of "game" , a game that aims to interpret in a paradoxical way the laws cited by the Digital Millennium Copyright Act (DMCA). It all started with the American mathematician and programmer Phil Carmody, with the aim of identifying a prime number so large as to be worthy of interest in scientific publications, but which at the same time encodes information whose dissemination is subject to restrictions .

Did you know that everything in the world can be uniquely represented by a number?

It may seem a bit strange to someone outside the digital world, but we computer scientists have developed a certain skill in finding a unique coding for practically everything. In the end, everything lives in the form of bits (1s and 0s), which put together form millions of different numbers .

It is no coincidence that the ASCII encoding, both on 7 and 8 bits, provides for a unique assignment of the character <-> number, or that each pixel is represented by 3 numbers (red, green and blue) with values ​​each from 0 to 255 to indicate its intensity. Putting all these numbers together we get huge lyrics, incredible resolution images, or songs.

ASCII table on 8 bits

However, the same "object" can be represented by different numbers based on the chosen encoding , the trick to understand each other is to choose a priori which encoding we are talking about. This is why the same image can have different formats (jpg, png, gif): the information is the same, but encoded in a different way or better, the data is compressed in a different way, and this means that the numbers inside it are different according to the chosen format. Even the programs themselves, in the end, are a set of low-level instructions but each instruction is a set of bits that all together form a large number.

Now imagine you have written a random number on a piece of paper, and this number, just happen, when converted to binary represents a series of instructions that allows you to decode a protected government data stream , and that consequently this program would be illegal in non-government hands. But we just wrote a number on a piece of paper, we didn't steal any software from anyone. Whose fault is it?

Although the legislation on the protection of copyright protects intellectual works, from a legal point of view it is difficult, if not impossible, to block the dissemination and sharing of a number (especially if of particular interest, such as a prime number) , even if it somehow encodes copyrighted content, because it can admit many different uses. Furthermore, a number is not patentable or subject to copyright as such.

Jon Lech's Story: A Legal Diatribe Over Decoding DRM Protected DVDs

The business of illegal primes began in 2002 with John Lech Johansen. Also known as DVD Jon, he is a Norwegian programmer involved in reverse engineering of proprietary file formats. A member of the Master of Reverse Engineering (MoRE) cracker group, he developed the DeCSS software in 2002, and was prosecuted for publishing the source code of the software on its website.

What is special about this story? DeCSS is a program written in C which allowed to bypass the DRM protections imposed on DVDs. Johansen was tried and then acquitted, but the story was a starting point for many to analyze in various respects the illegality of programs and data on computers or on the interpretation of the Digital Millennium Copyright Act .

DeCSS - Wikipedia
DeCSS code written in C: can be used to bypass the DRM encoding imposed on DVDs.

Illegal Prime Numbers: What Do They Look Like?

Based on the coding discourse made in the preceding paragraphs, a hypothetical method to try to circumvent the restriction and distribute software in principle illegal without problems is to somehow encode the program in an alternative form that had other legitimate uses or even such notable properties. to make it publishable.

In fact, we think of taking the binary code that makes up the program, and let's compress it. By compressing it, other compressed binary code is created which, as such, can be expressed in the form of a number, even a decimal.

Well, in 2001 mathematician and programmer Phil Carmody started looking for some prime number that could encode DeCSS . And since the search for prime numbers is very important for research, both mathematically (for the various properties that prime numbers offer) and computer science (see RSA), this number would have been easily worthy of scientific interest and therefore publishable.

By exploiting some features of gzip encoding and relying on Dirichlet's theorem (which states that given two coprime integers a and b, there are primes of the form a + nb), Carmody first succeeded in proving the at least theoretical existence of primes satisfying these requirements , and subsequently identified some of them in practice.

The first illegal prime to be discovered was relatively small, consisting of only 1041 digits . So Carmody decided to continue with his research, later identifying a number of 1905 digits, at the time the tenth largest first identified and then inserted in some sector publications.

We said that a number can represent several things, and different things can be represented by different numbers. Who therefore forbids us to represent a program as an image? Currently none, here's what the first illegal prime number looks like, as well as illegal software, discovered by Carmody :

illegal prime numbers
Graphic representation of the illegal prime number discovered by Carmody created by associating each bit with a color, gray or black, depending on whether zero or one. The first bit is the most significant, the squares corresponding to the bits are wrapped to have a rectangular image. Credits: wikipedia

Carmody did not stop there, however, and continued his research with a further objective: to find prime numbers that directly encode the program in machine code, without going through any intermediate compression algorithm. With further work he therefore identified a further prime number that represented in a 1: 1 ratio an ELF Linux executable file for i386 architecture, with similar functionality to DeCSS . It is thus the first executable program for which a representation in the form of a prime number has been identified .

Curious to know what an executable represented as a prime number looks like?

illegal prime numbers

Take this number, write it to a binary encoded file and you will have the linux executable of DeCCS. And here is how it is possible to distribute illegal information, legally disguised as prime numbers . Fascinating, isn't it?

The article Illegal Prime Numbers: Do They Exist? Yes, but they are not legally attackable comes from TechCuE .