backup del Post

numeri primi illegali

Fino alla seconda guerra mondiale, i governi avevano un sano approccio alla crittografia: le tecniche usate erano più o meno note, e bisognava semplicemente trovare un modo per craccare i codici militari. I codici per uso civile erano molto meno sofisticati, e non costituivano certo un problema per un esperto decrittatore. Poi sono arrivati i computer, e si è visto come la complessità di un codice cresceva molto più rapidamente della potenza di calcolo necessaria per decrittarlo. In pratica, soprattutto gli Stati Uniti si trovarono tra le mani codici relativamente facili da usare ma praticamente impossibili da decifrare, e si preoccuparono parecchio, tanto che diedero in appalto la cosa a un’apposita agenzia, la National Security Agency. Il lavoro della NSA è sempre stato avvolto dalla segretezza, tanto che era affezionatamente chiamata No Such Agency; su di essa fiorirono leggende, da quella secondo cui possedeva i computer più potenti del pianeta al loro intervento che fece modificare le specifiche originali dello standard DES in modo da poterlo craccare alla bisogna. Sicuramente l’agenzia era un ottimo datore di lavoro per i matematici statunitensi!

Ma come fare a evitare che quegli algoritmi finissero in cattive mani? Semplice, secondo i politici americani: bastava promulgare una legge al riguardo. Così gli algoritmi crittografici furono equiparati alle munizioni, con relativo divieto di esportazione a vari livelli. Gli stati amici potevano avere una cifratura “leggera”, con una chiave fino a 40 bit, mentre gli stati canaglia non avrebbero potuto avere nemmeno quello. Inutile dire che la soluzione non poté durare a lungo: i veri problemi cominciarono a sorgere quando i matematici svilupparono nuovi algoritmi di crittografazione, come per esempio quelli a chiave pubblica. Qui non si trattava semplicemente di gloria: gli inventori degli algoritmi volevano anche farci i soldi, e quindi per loro rendere noti gli algoritmi era necessario. Andò a finire che la legge venne presa sempre più in giro, tanto che si stamparono persino magliette equiparate a munizioni perché avevano il codice sorgente di qualche algoritmo; d’altra parte, le aziende statunitensi si trovavano svantaggiate perché loro non potevano vendere all’estero software con quegli algoritmi; alla fine così il governo americano decise di rilassare le regole relative alla crittografia.

Spostare il controllo della crittografia dal ministero della difesa a quello del commercio portò però a guai di un nuovo tipo. Le aziende infatti spinsero fortemente per una regolamentazione del diritto (o meglio, della mancanza di diritto) di copia digitale, tanto che venne pubblicato il famigerato Digital Millennium Copyright Act (DMCA) che rese illegali la produzione e la divulgazione di tutto quanto permettesse di bypassere i controlli di accesso ai lavori protetti dal copyright, anche se il diritto d’autore non veniva violato. Il DMCA valeva anche all’interno degli USA, a differenza del blocco alla crittografia (che – essendo equiparata alle armi – era soggetta al Secondo Emendamento. In pratica, se un bravo cittadino americano aveva il diritto di comprarsi un fucile a ripetizione, aveva anche il diritto di crittografare quello che voleva). Quando il programmatore norvegese Jon Lech Johansen finì a giudizio (in Norvegia… tutto il mondo è paese per certe cose) per aver reso pubblico il software DeCSS per sproteggere i DVD, ci furono alcune persone che pensarono a quali possibilità ci fossero per aggirare i divieti del DMCA. Nel 2001, il matematico e programmatore Phil Carmody trovò una soluzione elegante – dal punto di vista matematico – al dilemma teorico.

Dovete sapere che esiste un risultato, il Teorema di Dirichlet, che afferma che dati due numeri interi positivi a e b senza divisori in comune (tranne 1) allora la successione an+b, per n intero positivo, contiene un numero infinito di numeri primi. Carmody lavorò alla rovescia: come n prese il numero ottenuto comprimendo con gzip il codice sorgente dell’algoritmo, considerando il testo ricavato come un numero esadecimale, e convertendolo in formato decimale. I file in formato gzip terminano con un byte nullo; tutto quello che si trova dopo questo byte viene ignorato dall’algoritmo di codifica. Se quindi si sceglie a prendendo una potenza di 256, e b un numero minore di a/256, il numero an+b scritto in esadecimale e visto come file sarebbe stato indistinguibile da n per il programma di decompressione, fornendo sempre il codice sorgente originale. Carmody poteva così giostrare con i valori per trovare un numero primo abbastanza grande da essere considerato “interessante”. Come si può leggere su Wikipedia, dopo una serie di tentativi scoprì che il numero

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

era primo, e dunque una volta convertito in esadecimae e decompresso permetteva di avere il codice sorgente di DeCSS. Purtroppo quel numero non era abbastanza grande per essere inserito nelle Prime Pages tra i maggiori numeri primi senza una struttura specifica (come per esempio i primi di Mersenne, per cui è relativamente più facile verificare la primalità), e così continuò a cercare finché ne trovò uno di 1905 cifre che ai tempi era decimo in classifica e – pur essendo illegale secondo il DMCA – aveva pieno diritto di pubblicazione. In seguito si riuscirono a creare anche altri numeri primi illegali, partendo dal codice eseguibile in formato ELF per Linux e addirittura dal codice ASCII del programma; in questo caso si sfruttarono i commenti per tarare il numero corrispondente al testo quando letto come valore esadecimale fino a trovarne uno primo.

Lasciamo da parte la legalità o meno di una procedura “fatta la legge, trovato l’inganno” (e se volete, anche la legalità o meno dei divieti imposti dal DMCA), e limitiamoci alla matematica. La soluzione ideata da Carmody ricorda un poco, almeno a me, il trucco usato da Kurt Gödel per dimostrare il suo teorema di indecidibilità: un numero può voler dire anche qualcosa di diverso dal numero stesso, e a seconda di come lo si guarda un file può anche essere un numero. Non è divertente?