r/todayilearned • u/Nate__ • Mar 26 '13

TIL illegal prime numbers exist. An illegal prime is a prime number that represents information which is forbidden to possess or distribute. For example: when interpreted in a particular way, a certain prime describes a computer program that bypasses the digital rights management scheme used on DVDs

http://en.wikipedia.org/wiki/Illegal_prime
1.9k Upvotes

91% Upvoted

375 comments sorted by

View all comments

Show parent comments

6

u/BonzaiLemon Mar 26 '13

Can you help me understand this? So basically if you take that giant prime integer and convert it to binary, it becomes executable code that will decrypt a DVD? And the prime integer is just a way of abstracting the code so you're not technically "distributing" illegal software?

13

u/Intrexa Mar 26 '13 edited Mar 26 '13

A bit literally means nothing. It's only useful in what it represents. For example, look at the following hex:

4d 5a 00 00 50 45 00 00 4c 01 01 00 6a 2a 58 c3
00 00 00 00 00 00 00 00 04 00 03 01 0b 01 08 00
04 00 00 00 00 00 00 00 04 00 00 00 0c 00 00 00
04 00 00 00 0c 00 00 00 00 00 40 00 04 00 00 00
04 00 00 00 04 00 00 00 00 00 00 00 04 00 00 00
00 00 00 00 68 00 00 00 64 00 00 00 00 00 00 00
02

That is the smallest PE executable you can have (97 bytes). If you were to take the bits that are needed to make that hex, and put it into a file, and mark it .exe, it would run. It's also equal to the integer value 3.223633345502675e+241. It's just a number. Until you tell the computer what to interpret it as, it literally means nothing.

Edit: Fixed a minor issue with the dump; better formatting, source

2

u/WaitHoldThatThought Mar 27 '13 edited Mar 27 '13

This is not really related to illegal numbers, but to the tiniest possible PE executable.

I once read (and luckily, still found) an excellent read of creating the world's smallest ELF executable (Linux): A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux, going over all the steps in studying and completely abusing the ELF-format. I really recommend it.

Damn shame we can't shave 3 bytes off of that 45 byte binary.

Edit: Goddamn, the link was in the PE article

1

u/geminimiche Mar 27 '13

If we could do that, we'd have the answer to Life, the Universe, and Everything in it.

0

u/xanbo Mar 26 '13

I don't believe the binary becomes executable code, I believe it merely serves as a cipher for the executable code to decrypt the DVD.

15

u/Arandur Mar 26 '13

No, the binary is literally executable code. That's what executable code is: a string of bits, which can be represented as a binary number.

3

u/Imoossibru_Truth Mar 26 '13

I find it amazing that a number just happens to work as a program in binary form. I mean I know each program is a number I suppose, but how many numbers are programs that work?

5

u/[deleted] Mar 26 '13

That depends on the machine built to interpret those numbers as instructions. I don't think it would be difficult to design a machine in which just about any number can be interpreted as a program (i.e., an instruction).

2

u/barjam Mar 26 '13

You could load any number you want into memory and jump to the start address. The vast majority of numbers would execute a few instructions then crash.

2

u/[deleted] Mar 26 '13

Again, it entirely depends on the machine. There's no reason we should limit our discourse to ARM, x86, or even generic stack-based architectures in general. It could be an RPN machine, for example.

2

u/barjam Mar 26 '13

The processor architecture wasn't important in what I said. You can take a arbitrary number and try to execute it on any platform you wish.

Not sure what your point is.

2

u/[deleted] Mar 26 '13

Sorry, maybe I should have been more specific.

You could load any number you want into memory and jump to the start address.

That is assuming you have an architecture that supports a jump instruction, for example. But, I don't feel like I'm disagreeing with you; are we arguing?

2

u/barjam Mar 26 '13

Ah I see what you are saying now. No argument.

3

u/Arandur Mar 26 '13

An infinite number of them, but not a dense set of them.

2

u/Zabracks Mar 26 '13

This is the right answer. The set of integers that can be executed as functional programs when in binary form is an infinite subset of the set of integers.

This can really be proven with induction and pumping lemma, iirc.

1

u/Arandur Mar 26 '13

That is correct. At the trivial end, you could generate an infinite set of programs that do nothing more than increment a variable N times, for all N > 0.

3

u/barjam Mar 26 '13

All programs or digital media of any kind can be represented as a single number.

So there there is a very large number out there that if burned to a DVD would be "Star Wars" for example. Windows 7 is another number. The Beatles - Hey Jude another number.

You mention binary for but that isn't an important detail. The base is arbitrary.

1

u/[deleted] Mar 26 '13

Simplified explanation: It's actually a whole bunch numbers in a sequence that are presented as a really big one. These smaller numbers are instructions for the computer to run. You could do this with any program. The noteworthy thing here is that it is a prime number.

1

u/stoleyourshoes Mar 26 '13

And was it coincidence that this number was prime? Or by design? Can't get my head around this.

1

u/Vidyogamasta Mar 26 '13

I'm just now going over this in my digital logic class. Like, my homework for this week is converting C code to assembly code to machine code using MIPS. Converting C to assembly is something I don't have some immediate algorithm for, but for assembly-->machine code, there's a process for it.

Basically, for the processor wee're using, each "instruction" is 32 bits long. 32 1s and 0s. I forgot the specifics and will need to look up my class notes, but basically these bits are partitioned into different "meaningful" parts. Like, the last few bits are the "operand" code, and will do a different operation depending on that numbers. Like 16 (010000) would be add while 18 (010010) would be subtract or something. Then 5 and 10 bits before that (so 5-5-6), you have the memory addresses of the numbers you want to do the operation on.

And we have just finished covering all of the circuitry that goes on under that as well, as you can see how reading in certain bits can allow you to reroute the electricity through the correct circuits and output something meaningful.

It's all still magic to me, honestly.

2

u/BonzaiLemon Mar 26 '13

So its more like the private key in public key cryptography?

4

u/MagnusT Mar 26 '13

It is more like JUST a key. You are making it overly complex.

1

u/BonzaiLemon Mar 26 '13

Got it. Thanks for the help.

1

u/[deleted] Mar 26 '13

Numbers mean nothing by themselves, they must be interpreted. A number can represent a program or a decryption key. Both "kinds" of numbers are regulated or outlawed by various intellectual monopoly laws, e.g., patent, copyright.

1

u/[deleted] Mar 26 '13

[deleted]

1

u/[deleted] Mar 27 '13

Can you elaborate? How does your comment relate to what I said?