Waarom werd een onschuldig getal illegaal verklaard? En wat hebben films op dvd’s, rechterlijke uitspraken, arrestaties en roofkopieën daarmee te maken? We laten zien hoe je dergelijke priemgetallen zelf kunt genereren.
De computer zoemt, bromt en piept tijdens het opstarten, de monitor in het vertrouwde 4:3-formaat licht op en toont op een zwarte achtergrond de geslaagde geheugentest. Rechtsboven prijkt het logo van Energy Star. Een slok uit het blikje frisdrank en wachten tot Windows 98 opstart.
Voor het toetsenbord ligt een dvd van The Big Lebowski, die afgespeeld moet worden. Het is het jaar 2001. Gebrande dvd’s, beschreven met een foliestift, doen de ronde. Dat wordt mogelijk gemaakt door het programma DeCSS, dat de kopieerbeveiliging van dvd’s omzeilt. Programma’s zoals DeCSS waren in de VS volgens de Digital Millennium Copyright Act (DMCA) verboden, zowel de verspreiding van de code als gedeeltelijk het bezit ervan.
Daardoor kwam het programma op creatieve wijze in omloop, onder andere als een priemgetal. Om te begrijpen waarom het vandaag de dag als het eerste ‘illegale’ priemgetal wordt beschouwd, moeten we helemaal bij het begin beginnen.
Even terugspoelen
Vóór de opkomst van digitale dragers zoals dvd’s ging het kopiëren van media, meestal op magneetbanden, gepaard met kwaliteitsverlies. Tijdens het proces ging er altijd een stukje kwaliteit verloren. Als je dus zonder kwaliteitsverlies van beeld of beeld en geluid wilde genieten, moest je onvermijdelijk het origineel kopen, Dat veranderde pas toen cd’s en dvd’s de markt op zijn kop zetten.
Bestanden (op cd of dvd) konden zonder kwaliteitsverlies gekopieerd worden. In theorie zou iemand een film kunnen kopen en die zo vaak als hij wil kopiëren zonder kwaliteitsverlies. En dat gebeurde ook – het branden van cd’s en dvd’s werd beschouwd als een aardig gebaar voor vrienden, familie en buren.
Als reactie op het kopiëren van video’s – bij muziek sloegen dergelijke maatregelen niet aan – verzette de entertainmentindustrie zich met het door Toshiba en Matsushita ontwikkelde Content Scramble System (CSS). Dat versleutelde de inhoud van dvd’s, zodat onbevoegden die niet konden afspelen en kopiëren.
CSS is een onnodig ingewikkeld proces dat grofweg als volgt werkt: een dvd wordt gecodeerd met een 40-bit sleutel, die speciaal voor de specifieke film is toegekend door de Amerikaanse DVD Copy Control Association (DVD CCA). Die sleutel staat in honderden varianten op de dvd, zodat dvd-spelers van verschillende fabrikanten de dvd kunnen lezen en decoderen. Daarvoor moesten fabrikanten hun dvd-spelers bij de DVD CCA laten registreren.
De methode had verschillende zwakke punten, zoals uit cryptoanalyses bleek. Uiteindelijk was echter een dvd-speler van Xing Corp. de doorslaggevende zwakke plek omdat de fabrikant had nagelaten zijn eigen sleutels te versleutelen. Voor alle analyses en verdere informatie: zie de link aan het eind.
In oktober 1999 publiceerde een anonieme groep een programma met de toepasselijke naam DeCSS (CSSdescramble), dat CSS omzeilt. De enige bekende speler binnen de groep was de 16-jarige Noor Jon Lech Johansen, die kort daarna samen met zijn vader werd gearresteerd, maar jaren later van alle aanklachten vrijgesproken werd.
Zijn idee was eervol: Linux-gebruikers die een dvd kochten, konden die niet op hun computer afspelen omdat de spelers niet bij de DVD CCA geregistreerd waren. Johansen en zijn groep maakten daarom gebruik van de sleutels van de genoemde dvd-speler van Xing Corp.
DeCSS en zijn talrijke afgeleiden verspreidden zich razendsnel op het internet en Amerikaanse rechtbanken oordeelden op aandringen van de Motion Picture Association of America (MPAA) dat DeCSS een omzeiling van de kopieerbeveiliging was, wat volgens de DMCA verboden was.
Die beslissing leidde tot een eindeloze discussie over fair-use, auteursrecht en de vraag of programmacode verboden kan worden. Als protest construeerde Phil Carmody in maart 2001, zo’n 25 jaar geleden, een priemgetal dat, met de juiste methoden, de broncode van DeCSS opleverde.
Priemgetallen
Een natuurlijk getal groter dan 1, dat alleen deelbaar is door zichzelf en 1, wordt een priemgetal genoemd. Bij de eerste tien is het nog eenvoudig: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Maar je kunt je voorstellen dat het zoeken op een gegeven moment lastig wordt. Het duizendste priemgetal is bijvoorbeeld al 7919.
In het kader staat een bijzonder priemgetal. Als je dat gigantische getal (het heeft 1401 cijfers) omzet van het decimale stelsel naar het binaire stelsel (nullen en enen) en die bitreeks vervolgens als bestand opslaat, krijg je een gecomprimeerde versie van de afgebeelde DeCSS-broncode.
Het eerste ‘illegale’ priemgetal
Het bijzondere aan dit 1401-cijferige priemgetal: als je het naar bytes vertaalt en de data dan door gzip haalt, krijg je het originele DeCSS-programma.
485650789657397829309841894694286137707442087351357924019652073668698513401047237446968797439926117510973777701027447528049058831384037549709987909653955227011712157025974666993240226834596619606034851742497735846851885567457025712547499964821941846557100841190862597169479707991520048667099759235960613207259737979936188606316914473588300245336972781813914797955513399949394882899846917836100182597890103160196183503434489568705384520853804584241565482488933380474758711283395989685223254460840897111977127694120795862440547161321005006459820176961771809478113622002723448272249323259547234688002927776497906148129840428345720146348968547169082354737835661972186224969431622716663939055430241564732924855248991225739466548627140482117138124388217717602984125524464744505583462814488335631902725319590439283873764073916891257924055015620889787163375999107887084908159097548019285768451988596305323823490558092032999603234471140776019847163531161713078576084862236370283570104961259568184678596533310077017991614674472549272833486916000647585917462781212690073518309241530106302893295665843662000800476778967984382090797619859493646309380586336721469695975027968771205724996666980561453382074120315933770309949152746918356593762102220068126798273445760938020304479122774980917955938387121000588766689258448700470772552497060444652127130404321182610103591186476662963858495087448497373476861420880529443Carmody speelde met verschillende ideeën om de code van DeCSS te archiveren, zodat hij die legaal kon verspreiden. Als liefhebber van priemgetallen was de keuze van het medium slechts een formaliteit. Een gewoon priemgetal zou Carmody niet ver hebben gebracht, het moest wel een bijzonder priemgetal zijn, zodat er een reden was om het te publiceren.
De ranglijst van de grootste priemgetallen was in ieder geval niet geschikt omdat die wordt gedomineerd door het GIMPS-project (Great Internet Mersenne Prime Search), waarvan de Mersenne-priemgetallen zowel toen als nu de ranglijst aanvoeren.
In oktober 2024 vond het project 2<sup>136279841</sup> –1 (een getal met 41.024.320 cijfers), het momenteel grootste bekende priemgetal. Uiteindelijk koos Carmody de ranglijst van de grootste priemgetallen die met het ECPP-algoritme (Elliptic Curve Primality Proving) waren bevestigd als doel. Op die manier kon het programma – vermomd als priemgetal op de ranglijst – openbaar worden verspreid.
Omdat het dubbelzinnige getal zijn plaats op de ranglijst puur wiskundig verdiend had, kon men de relevantie voor publicatie moeilijk ontkennen. Het zojuist gepresenteerde 1401-cijferige priemgetal, dat als eerste ‘illegale’ priemgetal de annalen is ingegaan, was echter niet groot genoeg voor de ranglijst.
Carmody’s later gecreëerde 1905-cijferige priemgetal voldeed daarentegen voor de tiende plaats.
Zelf genereren
Om te begrijpen hoe Carmody te werk ging bij het genereren van het priemgetal, laten we zien hoe je zelf een priemgetal kunt genereren met het korte Python-programma print("Illegaal priemgetal"). De geproduceerde priemgetallen zijn niet illegaal omdat hun inhoud nergens verboden is, maar het eenvoudige voorbeeld illustreert de werkwijze van Carmody.
Bij de eerste stap zet je het programma om naar een ander formaat. Het helpt daarbij om je voor te stellen dat de code niets anders is dan één enkele tekenreeks. Om die om te zetten hoef je alleen maar in een ASCII-tabel op te zoeken welke bytewaarde voor een teken staat – in ons voorbeeld beginnend met p = 112, r = 114 enzovoort.
Dan is er een beetje wiskunde nodig: elk getal is één byte groot en om een decimaal getal te krijgen dat de code weergeeft, moet je alle bytes van links naar rechts met elkaar vermenigvuldigen. Voor p zou dat 112 · 256<sup>27</sup> zijn, dus 11794976666878404910166819100571088419716250684861500460482829484032. De eerste macht van 27 wordt verkregen uit de lengte van de tekenreeks, dus het aantal bytes, minus één.
Hetzelfde pas je toe op de r met 114 · 25626 en verder voor alle andere getallen, totdat je bij de afsluitende haak ) 41 · 2560 = 41 uitkomt. Als je dan alle resultaten bij elkaar optelt, levert dat het volgende decimale getal op: 11842042968586053159800165264074226145740247819445469274500353499689.
Die berekening hoef je zeker niet handmatig te doen, want er is een klein Python-hulpprogramma beschikbaar dat die taak op zich neemt:
code = b'print("Illegaal priemgetal")'print(int.from_bytes(code, byteorder='big'))Dan zou je meteen het eerstvolgende priemgetal kunnen zoeken, dat zou dan 11842042968586053159800165264074226145740247819445469274500353499747 zijn. Dat verandert echter de eigenlijke inhoud, omdat het 58 groter is dan het gecodeerde getal van het voorbeeldprogramma. Bij het terugvertalen zou daar dus niet de originele code uitkomen, maar print("Illegaal priemgetal"c.
De oplossing van Carmody was eenvoudig en geraffineerd. Hij voegde gewoon een extra byte toe en zocht naar een passend priemgetal in dat bereik. Bij het terugconverteren naar code kon je dan gewoon de laatste byte weglaten, zonder de code te wijzigen.
In zijn woorden:
~big number~ * 256 + Xwaarbij X een getal tussen 1 en 255 is. Als met de extra byte geen priemgetal mogelijk was, breidde hij het decimale getal met twee bytes uit. De variabele X kan dan een getal tussen 1 en 65535 zijn:
~big number~ * 65536 + XMet die methode is de kans om een priemgetal te vinden best groot. Mocht dat echter niet lukken, dan voeg je net zo lang bytes toe totdat er een priemgetal opduikt dat in het programma gebruikt kan worden. Bij het vertalen naar de code verwijder je alle toegevoegde bytes weer.
Om de afzonderlijke getallen als priemgetal te controleren, helpt de functie isprime() uit de Python-bibliotheek sympy:
for x in range(1, 256):candidate = number * 256 + xif sympy.isprime(candidate):print(candidate)breakDe functie filtert eerst alle kleine delers eruit en voert vervolgens de Miller-Rabin-test uit. Dat is een wijdverbreide probabilistische priemgetaltest die met een vrij hoge waarschijnlijkheid een priemgetal detecteert – men gebruikt die test onder andere om grote priemgetallen op te sporen voor het RSA-cryptosysteem.
Voor ons kleine voorbeeldprogramma hebben we op die manier een mogelijk priemgetal gevonden. Maar aangezien geen enkele priemgetaltest honderd procent betrouwbaar is en het getal ook een sterk pseudopriemgetal zou kunnen zijn, dat alleen op het eerste gezicht op een priemgetal lijkt, moet dat getal nog worden bevestigd.
In 2001 gebruikte Carmody het programma PFGW om mogelijke kandidaat-priemgetallen te vinden, en vervolgens het programma Titanix (tegenwoordig Primo) met het ECPP-algoritme om het priemgetal onomstotelijk te bevestigen.
Het valt buiten het bestek van dit artikel om de werking van dat algoritme uit te leggen. Het volstaat te weten dat het tot de snelste methoden behoort om priemgetallen te verifiëren. Als je een getal helemaal zonder programma wilt testen, kun je terecht op de website factordb.com, die een enorme database met getallen en hun factoren herbergt. In een fractie van een seconde keurt die een getal goed als priemgetal.
Om het priemgetal weer in code om te zetten, hoef je alleen maar de reeds uitgevoerde stappen om te keren:
number = <priemgetal>data = number.to_bytes((number.bit_length() + 7) // 8, byteorder='big')print(data[:-1].decode())Phil Carmody heeft het originele C-programma echter niet direct in bytes verwerkt, maar eerst verkleind met de compressiemethode gzip. Als je dus het oorspronkelijke programma css-descramble.c uit het priemgetal in bytes wilt uitpakken:
import zlibnumber = <priemgetal>data = number.to_bytes((number.bit_length() + 7) // 8, byteorder='big')r = zlib.decompress(data, wbits=47)print(r.decode('latin-1'))Als je het uitpakken van dichtbij wilt meemaken, kun je data in plaats daarvan ook naar een gzip-bestand schrijven:
with open('code.gz', 'wb') as f:f.write(data)Het 1905-cijferige priemgetal dat uiteindelijk op de ranglijst terechtkwam, creëerde Carmody op een manier die vergelijkbaar is met wat we hier zojuist beschreven hebben. Hij voegde diverse null-bytes toe aan de code om het getal kunstmatig op te blazen, zodat het groot genoeg was voor de top 20.
De creativiteit kent geen grenzen. Er zijn ook nog andere illegale priemgetallen, zoals het 1045-cijferige priemgetal in het kader hieronder. Daarachter gaat een klein C-programma schuil dat werkt zoals DeCSS. Je kunt het op dezelfde manier decoderen als het voorbeeldprogramma.
Het slimme aan dit priemgetal: het heeft helemaal geen extra bytes nodig, wat betekent dat de code zo is geschreven dat de directe byte-vertaling naar een decimaal getal een priemgetal oplevert.
Naast de illegale priemgetallen waren er nog veel meer, deels zeer creatieve ideeën om de code van DeCSS verborgen te verspreiden. Zo werd de code bijvoorbeeld op T-shirts gedrukt of in afbeeldingen en wiskundige formules verwerkt. Een verzameling van dergelijke verborgen varianten staat bij de link bij dit artikel.
Een kleiner priemgetal
Ook achter dit priemgetal zit DeCSS. Het programma is echter aanzienlijk korter en zo geschreven dat de directe byteconversie dit priemgetal oplevert.
2074016460653017903677472467534344521594245705226432338001975411781880848297473216201225262932642364967423671833349238034937804450308174343015540749132616221164876709167301423560691501322234013075899343301633878712059792711603172962525176515846925948207222370869477358057712621510800257817725569362039652879209586348648777891479133024335680359525895180300803788668225357732609996781121678376911757085304221996481426691599783415283992489372183940144231471165192957812509822052186118800623249134424628063549345471923662791183960016090278575686470595524566085024995619432953790723608275671962207318052579860979376983946673769975192454261954401549379181875464431410391589552490920704301764585945072712446588377165212076532583188993881712951838461103895935581969175481011884584167128360563592085081031890053251455648178213362745828950176675747548461669392657233390752605789842712465330348005899983089777238869001514560416123384524228804496252423675118235464525875971882779289237794224444133041315431003383825729204210277724614216568215235807791512957Conclusie
25 jaar later kunnen we zeggen dat het gebruik van een priemgetal om code te verspreiden ongelooflijk slim is. Het is nu eenmaal moeilijk te rechtvaardigen waarom een wiskundige waarheid in de vorm van een priemgetal niet gepubliceerd zou mogen worden.
Carmody had met het priemgetal dan ook een elegante oplossing gevonden om te protesteren tegen de toenmalige beslissing van de Amerikaanse rechtbanken en een belangrijke discussie over de legaliteit van code op gang te brengen.
De strijd rond het priemgetal is dan wel nooit voor de rechter uitgevochten, maar de ietwat overdreven bijnaam ‘illegaal’ is tot op de dag van vandaag blijven hangen.
Wilhelm Drehling en Noud van Kruysbergen
Praat mee