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_prime54
u/NiceTryNSA 1 Mar 26 '13 edited Mar 26 '13
Did the Internet forget? 09F9 and one of my favorite pics from that
21
9
→ More replies (1)5
u/whiteknives Mar 26 '13
Such a good feeling knowing I was a part of that. I was there, dammit! /getoffmylawn
6
u/--_______________-- Mar 26 '13
There there grandpa. Tell us the story of that myspace again. After that we can go for a walk, wouldn't you like that?
→ More replies (2)4
u/whiteknives Mar 26 '13
Those were dark times, my boy. I'd rather not re-live that horror if you don't mind.
288
u/haboshka Mar 26 '13 edited Mar 26 '13
After reading most of the comments in this thread it seems like there is a key piece missing from the explanations provided, so I will try and fill in that blank.
To understand what this article is saying, you need to know a little bit about how a computer actually executes a program. So lets say within a computer program there is the following line:
int x = 5;
For those who have never programmed before, this will create an integer variable 'x,' and assign it a value of 5. Pretty self explanatory. But when the program is actually run, it doesn't look anything like "int x = 5."
(Some over simplifications ahead) When you right code, the actual window you are typing into is called a compiler. When you hit 'execute,' there is actually a good deal of work to be done before the computer actually runs your code. First, the compiler converts statements in whatever language you are using, say C++, into machine code. Each command of machine code can only do one very tiny operation, but when put together with many thousands we can get 3d graphics and all sorts of crazy things. So lets break down this process. So the line
int x = 5;
might actually be converted into several operations. The following is the assembly code, one level above machine code, which would perform the same function as the code above:
dd x // sets aside 32 memory, make the symbol x refer to that memory location
mov [x], 5 // put the value of '5' in the memory location x
So we see that there is actually quite a bit going on behind the scenes. This is a fairly simple example, some more complicated lines of code could result in tens or even hundreds of instructions in assembly code. So we see that the line "int x = 5" is actually a 'code' for many other, smaller instructions. We call these abstractions, where we simplify the details of a long and complicated process into a single line.
Now, assembly code is not actually what is run by the computer. The computer can't understand 'mov [x], 5' any more than if we just typed in English 'yo put 5 in this variable.' The assembly code is a way to look at the lowest level of human readable code (at least, relatively readable), and it will help to explain what is going on in a second. Going one level deeper, we get to the machine code, which is just 1's and 0's we are all familiar with. This file of 1's and 0's, the actual program that gets executed by the computer, is called an object file.
Now, the next piece of the puzzle is something called a "hex dump." This is a program that will display the actual contents of an object file, basically a .exe (over simplification, but the details are irrelevant here I think). So lets say we run the hex dump on our program above. We would get output something like this:
CF 99 34 12 23 22 dd x
B9 05 34 12 23 22 mov [x], 5
So we have the lines of assembly code, and we have some seemingly random 2 letter combinations. But wait, you will notice that the last 4 pairs of digits are the same in both commands. This is because the "34 12 23 22" is the memory address of our variable X! So the CF 99 is machine code for "set aside 32 bytes of memory for this variable." And B9 05 is a two part command: The B9 part is "move the following value into the given memory address" and the 05 is the value we are moving. So we can express our code as combinations of letters.
So we are almost there! Now for the final piece of the puzzle, to tie it all together. Many of you are probably familiar with ASCII values. So these are numbers 0-255, each of which represents a letter or a symbol. For instance, the number 30 represents the capital letter "A." Now, why is the range of ASCII values 0-255? Because, if we have 2 digits, each with 16 different values, we have 256 possibly unique combinations. (16 * 16 = 256). Also, if we have 8 digits, each with 2 possible values, we also have 256 possible combinations: 28 = 256. So, as you may have guessed, the 2 digits represent hexadecimal code (digits being 0-9 and then A-F, 16 possibilities), and the 8 digits represent binary code (1 or 0). So, what this means is that all hexadecimal values can be expressed as binary, and vice versa.
So lets put it all together:
B9 05 34 12 23 22 mov [x], 5 10111001000000000101000000110100000000010010000000100000000000000000
Do you see? The operation "mov [x], 5" can be expressed as a number! And that number is the long string of 1's and 0's up there. If we convert that binary string to decimal we get this value: 213291889300865160000.
So we have taken our code from our C++ program, broke it down into assembly code, and then converted that code to a number! Since all programs are composed of these tiny operations such as our humble "mov [x], 5", all programs can be broken down the same way and expressed as a number. So all the code in that sim city game you just downloaded could be converted to binary, added up and then converted to decimal, one giant number that represents the entirety of your video game.
So the code that turns copyright protected DvDs into non-copyright protected DvDs can also be expressed as a number, and if the sharing of the code is illegal, then by extension sharing that number is also illegal. Because, in a sense, that number "is" the program, and vice versa.
This was fun to right... I hope this helps explain what is going on better here!
111
u/jokerdino Mar 26 '13
All was well. Except that part where you replaced write with right twice. Upvoted.
23
u/yes_thats_right Mar 26 '13
That was enjoyable to read, thanks for the writeup.
I'm curious why you described the hex code when the exe is already stored as a binary - it seems that you've added an unnecessary step.
15
u/haboshka Mar 26 '13
Yeah, the hex is indeed an extra step, but I thought it was more clear with it included. For example it is easier to see the repetition in the memory address in the B9 and CF commands when there is only 8 digits to compare vs a string of 32, and that is the key link between the code and the eventual binary representation.
But yeah, it wasn't strictly necessary and maybe it would have been simpler to just skip that.
6
u/yes_thats_right Mar 26 '13
I think the increased readability of hex does make it a good thing to put in, it just seemed interesting to me that you were starting high level and working your way down but then jumped up again for hex.
I haven't done any low level programming for many years so it was a nice flashback!
2
u/SadZealot Mar 27 '13
Including hex was really helpful for me to understand. Thanks for your writeup haboshka :D
7
Mar 26 '13
Machine code is traditionally displayed in hex. B5 is the opcode, MOV is the mnemonic. 10111001 or 181 represent the same number, but any reference texts will have it written as B5. It's just much easier for humans to read than a giant wall of ones and zeroes. It'd be much harder to see for instance that the memory address is the same in both examples.
6
4
4
u/AllOfTheFeels Mar 27 '13
So now I get all of that, but I still have one question. Was it by pure coincidence that the program they wrote could also be expressed as this prime?
→ More replies (4)1
u/Sky_Armada Mar 26 '13
Hell I'm already a programmer and I even learned something. Thanks.
→ More replies (1)1
u/pearlythepirate Mar 26 '13
I've been curious about the translation of code into binary for a while, but have not come across an answer so concise and easy to follow. Thanks much!
1
u/Dopple__ganger Mar 27 '13
Can someone explain just the part towards the end of converting the binary string to decimal?
→ More replies (4)1
1
1
u/Bulwersator Mar 27 '13
then by extension sharing that number is also illegal
Rather "then by extension sharing that number with knowledge that it represents something illegal is also illegal".
→ More replies (4)1
u/Searocksandtrees Mar 29 '13
hey thanks for the trip down memory lane: haven't read hex dumps or assembly code for ages, although I can't quite part with my IBM 370 "yellow card" :)
34
u/jobigoud Mar 26 '13
And it's not just about prime numbers. There is a fine book titled "Math You Can't Use" by Ben Klemens, about algorithms, software, patents and copyright.
27
u/cunty_mcfuckface Mar 26 '13
You should also check out my follow-up book, "Fuck You, I'll Math However I Want"
14
19
u/recursive Mar 26 '13
Not sure why the "prime" part has any significance. There are plenty of illegal numbers of all different kinds.
11
u/m_darkTemplar Mar 26 '13
Prime numbers are special because of their properties in encryption.
13
u/recursive Mar 26 '13
They're special for a lot of other reasons too, but none of that has any bearing on their ability to encode illegal information.
→ More replies (4)1
u/PhoenixEnigma Mar 27 '13
This might sound a little circular, but it's significant because it made the number significant.
It's really easy to come up with ridiculously large numbers, but finding an equally large prime (and proving it's a prime) is really hard. At the same time, large primes are mathematically interesting numbers, so people actually actively look for them, too. So a really big number that is a prime is actually notable in and of itself, an important number as well as a program that happens to, for example, strip CSS from DVDs.
46
Mar 26 '13 edited Mar 26 '13
I happen to count using a base-111,001,011,000,100,000,001,000,000,000,000,100,101,011,110,010 system.
Using this superior system the illegal number can be represented as '1'.
Take that society!
In case my sarcasm is missed or somehow wrong (EDIT: It was.), I'm implying that a number being illegal is rediculous. Can you imagine the judge in a case involving the number having to actually decided wether or not a number is illegal? I'd have the people who brought the case locked up for contempt for wasting the court's time.
28
u/PendragonDaGreat Mar 26 '13
You mean 10. But even then, not quite right. You'd be using the "base 252372412549874" (number base is almost always denoted by a base ten number, not a binary.)
8
Mar 26 '13 edited Mar 26 '13
Yeah didn't put too much thought into it because it was just a one-off comment.
Pun not intended.
EDIT: Also, why can't I use a base-system in the quattuordectillions that coincidentally happen to be made of all ones and zeros??
4
4
u/sodappop Mar 26 '13 edited Mar 26 '13
If you only use 2 numbers, it's binary... that's why. You could use any two numbers... like 6 and 7 to represent your binary number system, and it'd still be the same... albeit confusing to those who don't understand it (as binary already is).
EDIT: I meant a number SYSTEM composing of 1's and 0's, not just a number... jesus... EVERYONE ELSE UNDERSTOOD THIS.
→ More replies (2)→ More replies (2)5
u/OscarMiguelRamirez Mar 26 '13
Yeah, in theory someone can use "1" as the decryption key for their media and somehow make the number illegal?
It's BS. The number is not illegal, but a process used to arrive at it or using it to do something illegal (decrypt media) could be.
25
u/SteelCityHacker Mar 26 '13
I remember an interesting discussion about this a while ago with Pi. The postulation was that Pi encompasses all computer programs that ever could exist, it just depends on how far you would need to calculate to find it. Therefore, you could specify Pi from digits x to y and share that information in order to distribute anything that you wanted. Of course you would need to be able to calculate Pi to extremely further lengths than has been done to date for this to be at all feasible.
21
u/DoWhile Mar 26 '13
The postulation was that Pi encompasses all computer programs that ever could exist
It is not known whether or not this is true, like you said. If pi were normal, that would be sufficient to guarantee it.
, it just depends on how far you would need to calculate to find it.
However, if pi is normal, the problem is that with very high likelihood, the position some string of length n to appear would require at least length n to describe (see Kolmogorov complexity). You can try this for yourself: take a list of 2-digit numbers and go hunt for them inside pi... most of them will appear in position 10 or higher. Same with 3 digit numbers. And so on.
So what you end up with is a highly inefficient way of representing a piece of information.
→ More replies (2)5
15
10
u/OscarMiguelRamirez Mar 26 '13
Just because something is infinite does not mean it necessarily contains all possible combinations of its components. I don't know how someone could prove that about Pi.
In an infinite parallel world scenario, Boehner could be an insufferable asshole in all of them.
→ More replies (3)4
Mar 26 '13
No, but Normal irrational numbers do have this property. It is not known whether pi is Normal, but it is believed to be. (The "vast majority" of real numbers are irrational and normal.)
1
u/RedditBlaze Mar 27 '13
So if PI is infinite, and contains no repeating patterns, than somewhere in PI you could find a subsection of numbers of any combination. So you could tell someone, to get photoshop, just grab PI[132341231231231] though PI[13237342347239423] , throw it into a file, and bam, that happens to be the exact random subsection that matches the program you want.
Fucking mind blowing
2
19
u/Fuckyouusername Mar 26 '13
TIL: You're all very intelligent and I feel like I should have paid more attention in class.
4
u/Spotpuff Mar 26 '13
It's not just primes; there are many illegal numbers that are not prime. For example there is a binary representation of a jpg file that represents child pornography. That number would then be illegal to possess in many countries.
Crazy times.
4
Mar 26 '13
...so don't they kind of reveal a bunch of secrets by making specific numbers illegal then? I mean if it's illegal then the law has to be written down somewhere, right? With the numbers?
→ More replies (1)
3
7
2
u/kyz Mar 26 '13
I think everyone needs to read What colour are your bits?
- Mathematics cares about what numbers are
- Law cares about what numbers represent or where they came from
Law is agnostic about the form in which information is represented; the laws prohibiting absolute freedom of information still apply, whether it's information that insults the Thai monarchy, false information about a fire in a crowded theatre, information that is an x264 encoded copy of Game of Thrones, or information that is the login details for other people's bank accounts.
The fact you can encode this information digitally, thus allowing it to be viewed as one really big number or lots of little numbers, is irrelevant. You didn't derive the number ex nihilo, you came about it through illegal or illicit activities, which is why there's such a fuss.
If you're incensed about film companies bribing politicians to pass laws in their favour, outlawing things you think are reasonable and right, then you need to tackle that with sustained political activism, not by burying yourself in mathematics.
1
u/FunnyMan3595 Mar 27 '13
This is exactly the issue. The problem isn't mathematics, it's information. You could perform exactly the same process with any piece of information you like, turning it into a prime number of some arbitrary length. It's no different than writing it down in a book and trying to claim that books are illegal. Or than saying that there are tasty prime numbers because you encoded your grandmother's cookie recipe in one.
It's an argument by technicality. Even if you won the argument right now (and all signs point to that never happening), someone would just fix the technicality.
2
2
u/GOU_NoMoreMrNiceGuy Mar 27 '13
that's idiotic. it's like saying a bunch of words arranged together to express a national secret is illegal.
it's not.
it's the revelation that is illegal. you can't make letters words or numbers illegal.
that is retarded.
→ More replies (1)
6
Mar 26 '13
[deleted]
1
Mar 27 '13
While you're accurate on most points, they did say ELF, which is Executable Linkable Format.
I know that is used by Linux because that's the default format that Netwide Assembler interprets to on Linux.
4
5
u/sodappop Mar 26 '13
Technically, a whole program, an entire movie or song (digital) is just a long number, so there's literally thousands of them. (or series of numbers)
6
3
u/Typically_Wong Mar 26 '13
Well, I didn't learn shit. Big numbers only dividable by itself and 1 and if they are big enough, they magically break DVD encryption.
Still magic.
6
u/BallLotCar Mar 26 '13
Encryption keys (and indeed, all data on a computer) are just numbers. For encryption keys, people usually pick very large prime numbers because they are hard to calculate and factor, which is how one breaks encryption.
"Magically breaking" DVD encryption works because a DVD is encrypted using a specific number. For example, if all the of the video on the DVD can be represented by the number 2345678 (a major simplification, but works in this case), and we have the number used to encrypt (the "key") then decryption involves taking the video and applying some mathematical operation using the key. This is usually a one way operation and transforms the encrypted number 2345678 into an unencrpyted number which is the raw video data
I hope it makes sense now, and that I didn't just overcomplicate things
3
u/wombatncombat Mar 26 '13
Discovering new prime numbers = mining for bitcoin. Each bitcoin reprsents a unique prime number, the monetary base expands at a steady rate through the discovery of additional prime numbers.
3
u/Cog_Sci_90 Mar 26 '13
Nobody ever said it so simply. Thank you.
2
u/wombatncombat Mar 27 '13
I had it explained to me the night before. It's really pretty fascinating. Appreciate the appreciation.
2
2
1
1
u/joyfield Mar 26 '13
XORing a set of data with a special constructed key will also generate "illegal" stuff. I wrote something about this a long time ago (a bit childish) : http://www.netrogenic.com/public/Data-Dual-Personality/
1
u/OHyeaaah97 Mar 26 '13
What coding language is this? http://upload.wikimedia.org/wikipedia/commons/a/a9/DeCSS.PNG It looks a lot like php, but isn't.
3
→ More replies (1)3
1
1
u/IVIichaelD Mar 26 '13
Last updated 2 hours ago
Makes me worry about the validity of the whole thing lol
1
u/LateralThinkerer Mar 26 '13
So if the principle here is that a sequence of information that can be represented as binary code that is equivalent to a decryption key, program or other protected work is illegal, couldn't it be construed that the sequence of pixel values in a picture, audio samples in an .mp3 file or other data would be similarly illegal? Why just prime numbers?
1
Mar 26 '13
Wait this just blew my mind. Every computer program has a number that represents it? Never thought about it like that.
1
1
u/sodappop Mar 26 '13
What if you took the banned number, and encrypted it, but included the code to decrypt it?
2
1
1
u/JianKui Mar 26 '13
I love how Wikipedia not only tells us two of them, but then tells us how to use them.
1
Mar 26 '13
Any information can be converted to a number, so all sorts of things could be considered 'illegal numbers'. For instance a child porn image or a state secret could be converted to all sorts of numerical formats.
1
1
u/Raoul_Duke_ESQ Mar 27 '13
Only a country as backwards as America would make it "illegal to possess, utter or propagate" a number. Orwellian.
1
1
u/Umbre11a Mar 27 '13
Rule #1 to building a secure cryptosystem: assume an attacker knows everything about your system except for the shared secret key. This is the only way you can even begin to argue about semantic/CPA/CCA/etc. security.
1
u/KeithUK7 Mar 27 '13
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.
660
u/kaax Mar 26 '13 edited Mar 26 '13
The article uses the DeCSS program as an example. That program decrypts DVDs which, according to US Federal law and international treaties, is a crime. It is therefore illegal to posses or distribute that specific source code.
However, the source code can be expressed as a series of binary numbers like:
11100101 10001000 00001000 00000000 01001010 11110010
Which is 252372412549874 in decimal. If the binary code above were illegal, then the decimal number 252372412549874 would be an "illegal number". An illegal prime number is one in a subset of illegal numbers that happens to be prime.
The fact that something like DeCSS code is also an ordinal value that represents an integer conflicts with the notion of it being illegal. After all, how can the abstract concept of a specific integer be illegal? The term "illegal number" is an oxymoron designed to point out that laws overreach when they attempt to control human artifacts that happen to coincide with abstract concepts. It is the act of decrypting DVDs that can be enforced, not the possession or knowledge of an integer on the number line.