Sulla sinistra, una macchina che si auto-istruisce e impara a giocare esapedone, appena uscita di fabbrica. In alto le scatole di giochi saccheggiate per raccogliere gli elementi necessari.
giovedì 27 maggio 2010
Intelligenza artificiale
Sulla sinistra, una macchina che si auto-istruisce e impara a giocare esapedone, appena uscita di fabbrica. In alto le scatole di giochi saccheggiate per raccogliere gli elementi necessari.
domenica 23 maggio 2010
sabato 22 maggio 2010
Speriamo che porti bene
Il 24 novembre 1948 venne pubblicata una storia di Carl Barks dal titolo The Sunken Yacht (L'eredità di Paperino in italiano). Paperino e i nipotini hanno una impresa di recuperi marini, e propongono allo zio Paperone di recuperare un suo yacht. Sembra una impresa impossibile, ma i nipotini hanno la geniale idea di riempire la nave di palline da ping-pong per farla tornare a galla.
Nel dicembre del 1964 un inventore danese, di nome Karl Krøyer, utilizzò lo stesso principio per recuperare una nave affondata vicino al porto del Kuwait utilizzando schiuma di polistirolo espanso al posto delle palline da ping-pong. Si dice che Kroyer non sia riuscito a brevettare questo sistema perché secondo l'ufficio brevetti esisteva già una descrizione preliminare della sua tecnica: proprio in questa storia di Barks.
Il 17 marzo 1974 venne pubblicata, su Topolino, la prima parte di una storia in due puntate (la seconda sarebbe stata pubblicata la settimana dopo, il 24 marzo) dal titolo Zio Paperone e la raffineria galleggiante, scritta da Giorgio Pezzin e disegnata da Giorgio Cavazzano. Zio Paperone costruisce una nave gigantesca in grado di aspirare il petrolio disperso in mare e raffinarlo immediatamente.
Il petrolio raffinato viene immagazzinato all'interno di un serbatoio galleggiante.
Naturalmente Rockerduck non ci sta, e si accorda con i Bassotti per sabotare la nave. La nave affonda, i paperi trovano rifugio sul serbatoio galleggiante, il quale è però in balia delle correnti, e viene trasportato verso nord, in zone sempre più fredde. Dopo alcuni giorni, i paperi vengono salvati da un eschimese, che li riscalda con un fuoco alimentato da uno strano ghiaccio. Ecco una delle ultime pagine della storia:
Ecco, non so, con le palline da ping-pong è andata bene, magari qualche inventore dei giorni nostri può farsi venire l'ispirazione per rimediare a quello che sta succedendo in questo periodo.
[Update: ecco qualche tavola dell'edizione italiana della storia di Barks, grazie a Corax]
Nel dicembre del 1964 un inventore danese, di nome Karl Krøyer, utilizzò lo stesso principio per recuperare una nave affondata vicino al porto del Kuwait utilizzando schiuma di polistirolo espanso al posto delle palline da ping-pong. Si dice che Kroyer non sia riuscito a brevettare questo sistema perché secondo l'ufficio brevetti esisteva già una descrizione preliminare della sua tecnica: proprio in questa storia di Barks.
Il 17 marzo 1974 venne pubblicata, su Topolino, la prima parte di una storia in due puntate (la seconda sarebbe stata pubblicata la settimana dopo, il 24 marzo) dal titolo Zio Paperone e la raffineria galleggiante, scritta da Giorgio Pezzin e disegnata da Giorgio Cavazzano. Zio Paperone costruisce una nave gigantesca in grado di aspirare il petrolio disperso in mare e raffinarlo immediatamente.
Il petrolio raffinato viene immagazzinato all'interno di un serbatoio galleggiante.
Naturalmente Rockerduck non ci sta, e si accorda con i Bassotti per sabotare la nave. La nave affonda, i paperi trovano rifugio sul serbatoio galleggiante, il quale è però in balia delle correnti, e viene trasportato verso nord, in zone sempre più fredde. Dopo alcuni giorni, i paperi vengono salvati da un eschimese, che li riscalda con un fuoco alimentato da uno strano ghiaccio. Ecco una delle ultime pagine della storia:
Ecco, non so, con le palline da ping-pong è andata bene, magari qualche inventore dei giorni nostri può farsi venire l'ispirazione per rimediare a quello che sta succedendo in questo periodo.
[Update: ecco qualche tavola dell'edizione italiana della storia di Barks, grazie a Corax]
Femmina cercasi
Una prof. di lettere collega di mia moglie vorrebbe preparare un percorso di lettura per i suoi studenti, incentrato sulla donna (non so bene i termini della questione, quindi perdonate il pressapochismo). Le piacerebbe proporre anche qualcosa di fantascienza, ma sull'argomento non è molto preparata.
Dunque la domanda è: quale romanzo o racconto di fantascienza, con protagonista femminile, pensate sia adatto a studenti di scuola superiore?
Io non ne conosco molti, ecco quelli che mi sono venuti in mente.
Operazione domani, di Heinlein. La quarta di copertina di Urania descrive così il romanzo:
È uno dei romanzi dell'ultimo periodo di Heinlein, uno di quelli in cui il sesso entra dappertutto (oops, scusate, il gioco di parolenon era voluto). L'ho letto tempo fa e me lo ricordo poco, ricordo che non mi piacque un gran che. Secondo me uno studente medio non lo leggerà mai fino in fondo, magari si guarda il riassunto sulla pagina di wikipedia (occhio agli spoiler, non andateci se volete leggere il libro) e tutto finisce lì. Heinlein ha scritto storie migliori.
Non temerò alcun male, di Heinlein. Copio un commento da aNobii:
Commento sul quale sono d'accordo: il libro è eccessivamente lungo (542 pagine nell'edizione che ho segnalato) e, facendo parte dell'ultima produzione di Heinlein, morboso fino all'eccesso. Eunice è bellissima, intelligentissima, giovanissima, freschissima, piena di curve, emancipatissima, praticamente una dea e, mentre la sua mente comunica con quella del novantacinquenne, fa sesso una pagina sì e una no. Probabilmente gli studenti leggerebbero il testo una pagina sì e una no. Non consiglierei nemmeno questo.
La luna è una severa maestra, ancora di Heinlein. La quarta di copertina di Classici Urania dice:
In questo romanzo non c'è una vera e propria protagonista femminile (anche se uno dei personaggi principali è una donna), però lo consiglierei ugualmente per come viene presentata la figura della donna: siamo sulla Luna, che è diventata una colonia penale della terra. La vita è difficile, gli uomini vivono in gallerie, nulla è dovuto (è in questo romanzo che nasce l'acronimo TANSTAAFL — There ain't no such thing as a free lunch, cioè non esistono cose come i pasti gratis). Non vengono fatti molti controlli: se sopravvivi, bene, altrimenti muori perché non sei in grado di cavartela. Dopo alcune generazioni nasce, nei lunari, una coscienza nazionale: essi vogliono dichiararsi indipendenti e non sottostare più al controllo terrestre.
La legge lunare è molto individualista, ognuno è responsabile delle proprie azioni, ma su un punto tutti i lunari sono d'accordo: uno dei crimini più grandi, punibile con la morte, è fare del male a una donna. All'inizio della colonizzazione della Luna, il rapporto uomini/donne era 10 a 1. Nel periodo in cui è ambientato il romanzo è sceso a 2 a 1: in ogni caso le donne sono molto poche. Per questo nella società lunare sono permesse relazioni poliandriche; anzi, direi che sono praticamente la norma. Le famiglie sono molto allargate, una donna ha molti mariti, ma i mariti possono avere altre mogli. Quando si accetta un nuovo elemento nella famiglia, tutti devono essere d'accordo: mogli e mariti votano se accettare o meno una nuova moglie, o un nuovo marito.
Provate a pensare a una società in cui toccare una donna senza il suo consenso può portare alla morte (e in cui tutti gli uomini si danno da fare per cercare, e uccidere senza troppi processi, chi ha toccato una donna senza chiederle il permesso).
Questo romanzo è stato pubblicato tra il 1965 e il 1966, ed ha fruttato all'autore accuse di comunismo. Nel 1956 aveva pubblicato Fanteria dello spazio, romanzo che gli fruttò accuse di fascismo. Quelli sì che erano romanzi di fantascienza.
Io questo lo consiglierei agli studenti: se anche qualcuno si legge il riassunto su wikipedia, pazienza. Il libro è comunque molto lungo, non tutti arriveranno in fondo, comunque. Ma vale la pena.
I racconti dei robot, di Asimov. Qui sto pensando a Susan Calvin, la robopsicologa della US Robots and Mechanical Men, Inc., l'azienda terrestre che produce robot. Una donna completamente diversa dalle protagoniste femminili di Heinlein: quelle sprizzano femminilità da tutti i pori e si accoppiano in continuazione, questa invece ama più i robot del genere umano. Il personaggio, però, non è analizzato a fondo: è "solo" un co-protagonista di molti racconti. Ma è molto amato da Asimov che, in Tutti i miei Robot, la descrive così:
Una citazione da La prova, che fa capire che tipo è la dottoressa:
— […] Siete la dottoressa Susan Calvin o mi sbaglio?
— Non vi sbagliate, signor Byerley.
— Siete la psicologa della U.S. Robots, vero?
— Non psicologa, ma robopsicologa.
— Oh, perché, i robot sono così diversi dagli uomini, dal punto di vista mentale?
— Diversissimi. — La Calvin si concesse un sorriso gelido. — I robot sono fondamentalmente onesti.
Il rischio, a parlare di Susan Calvin, è che gli studenti si guardino il film Io, Robot. Bisogna proibirglielo con ogni mezzo, lecito o illecito.
Ma la mia protagonista femminile preferita, o temuta, è Janet, che compare in un breve racconto di circa quattordici pagine di Shekley, intitolato La settima vittima. Non so se dire di più, rischiando di rovinare la lettura a chi non conoscesse ancora il racconto che compare nella antologia di fantascienza Le meraviglie del possibile (consigliatissima, da leggere assolutamente). In un mondo in cui sono state combattute quattro guerre mondiali (sei secondo alcuni storici) e in cui tutti si sono resi conto che una nuova guerra sarebbe stata l'ultima, perché avrebbe sicuramente cancellato l'uomo dall'esistenza, la pace deve durare per sempre. Ma come incanalare la naturale violenza dell'uomo? La competizione, la lotta, il coraggio di fronte all'imprevisto, sono garanzie di perpetuazione della specie, non possono essere eliminate: è per questo che l'assassinio viene legalizzato, su basi strettamente individuali e per coloro che lo richiedono. Ogni individuo può commettere tutti gli omicidi che desidera, ma tra uno e l'altro deve fare la parte della Vittima. Su queste basi si sviluppa un racconto del quale non dico altro.
Se qualcuno ha altre idee, ogni commento è bene accetto, grazie.
Dunque la domanda è: quale romanzo o racconto di fantascienza, con protagonista femminile, pensate sia adatto a studenti di scuola superiore?
Io non ne conosco molti, ecco quelli che mi sono venuti in mente.
Operazione domani, di Heinlein. La quarta di copertina di Urania descrive così il romanzo:
Friday è una splendida figliola, moderna e disponibile, ma possiede due caratteristiche peculiari: è un corriere segreto ed è anche una PA, ossia una Persona Artificiale, uguale in tutto e per tutto a un comune essere umano salvo per il fatto di essere stata creata in laboratorio. Il suo capo, Boss, l'ha reclutata e addestrata quando per lei la vita non era certo facile ma ora Friday è un agente in grado di sopportare all'occasione stupri multipli e torture.
Ma la sua vita non manca di lati piacevoli e distensivi, almeno fino al giorno che sarà ricordato dai libri di storia come il Giovedì Rosso.
Chi si nasconde dietro l'ondata di delitti politici e di sabotaggio che dilagano sulla terra e nello spazio, minacciando il tranquillo caos che da secoli regna sull'Umanità?
È uno dei romanzi dell'ultimo periodo di Heinlein, uno di quelli in cui il sesso entra dappertutto (oops, scusate, il gioco di parole
Non temerò alcun male, di Heinlein. Copio un commento da aNobii:
Grande libro che di fantascientifico non ha nulla salvo l'idea iniziale: il cervello di un ricco 95enne trapiantato nel corpo di una giovane e bellissima donna che, da viva, era la sua segretaria. Ma - sorpresa! - nel corpo della donna persiste la sua mente e le due entità possono comunicare. Da qui Heinlein prende lo spunto per considerazioni sull'essere uomini, l'essere donne e l'essere entrambi, sulla vita e sulla morale. Uno splendido romanzo in cui l'autore denota una grande sensibilità nei lunghi dialoghi tra l'uomo e la donna. Un libro crudo e delicato che ha il solo difetto di una eccessiva verbosità.
Commento sul quale sono d'accordo: il libro è eccessivamente lungo (542 pagine nell'edizione che ho segnalato) e, facendo parte dell'ultima produzione di Heinlein, morboso fino all'eccesso. Eunice è bellissima, intelligentissima, giovanissima, freschissima, piena di curve, emancipatissima, praticamente una dea e, mentre la sua mente comunica con quella del novantacinquenne, fa sesso una pagina sì e una no. Probabilmente gli studenti leggerebbero il testo una pagina sì e una no. Non consiglierei nemmeno questo.
La luna è una severa maestra, ancora di Heinlein. La quarta di copertina di Classici Urania dice:
Le colonie della Luna lottano per la loro indipendenza contro lo strapotere del governo terrestre: gli uomini che hanno attraversato lo spazio per aprire una nuova frontiera non sono disposti a tollerare il dispotismo di un giogo sempre più opprimente. Su questo tema classico, di grande respiro avventuroso, Heinlein costruisce uno dei suoi romanzi più memorabili, una trama di lotte e libertà che riscrive in chiave fantascientifica l'epopea della Rivoluzione americana.
In questo romanzo non c'è una vera e propria protagonista femminile (anche se uno dei personaggi principali è una donna), però lo consiglierei ugualmente per come viene presentata la figura della donna: siamo sulla Luna, che è diventata una colonia penale della terra. La vita è difficile, gli uomini vivono in gallerie, nulla è dovuto (è in questo romanzo che nasce l'acronimo TANSTAAFL — There ain't no such thing as a free lunch, cioè non esistono cose come i pasti gratis). Non vengono fatti molti controlli: se sopravvivi, bene, altrimenti muori perché non sei in grado di cavartela. Dopo alcune generazioni nasce, nei lunari, una coscienza nazionale: essi vogliono dichiararsi indipendenti e non sottostare più al controllo terrestre.
La legge lunare è molto individualista, ognuno è responsabile delle proprie azioni, ma su un punto tutti i lunari sono d'accordo: uno dei crimini più grandi, punibile con la morte, è fare del male a una donna. All'inizio della colonizzazione della Luna, il rapporto uomini/donne era 10 a 1. Nel periodo in cui è ambientato il romanzo è sceso a 2 a 1: in ogni caso le donne sono molto poche. Per questo nella società lunare sono permesse relazioni poliandriche; anzi, direi che sono praticamente la norma. Le famiglie sono molto allargate, una donna ha molti mariti, ma i mariti possono avere altre mogli. Quando si accetta un nuovo elemento nella famiglia, tutti devono essere d'accordo: mogli e mariti votano se accettare o meno una nuova moglie, o un nuovo marito.
Provate a pensare a una società in cui toccare una donna senza il suo consenso può portare alla morte (e in cui tutti gli uomini si danno da fare per cercare, e uccidere senza troppi processi, chi ha toccato una donna senza chiederle il permesso).
Questo romanzo è stato pubblicato tra il 1965 e il 1966, ed ha fruttato all'autore accuse di comunismo. Nel 1956 aveva pubblicato Fanteria dello spazio, romanzo che gli fruttò accuse di fascismo. Quelli sì che erano romanzi di fantascienza.
Io questo lo consiglierei agli studenti: se anche qualcuno si legge il riassunto su wikipedia, pazienza. Il libro è comunque molto lungo, non tutti arriveranno in fondo, comunque. Ma vale la pena.
I racconti dei robot, di Asimov. Qui sto pensando a Susan Calvin, la robopsicologa della US Robots and Mechanical Men, Inc., l'azienda terrestre che produce robot. Una donna completamente diversa dalle protagoniste femminili di Heinlein: quelle sprizzano femminilità da tutti i pori e si accoppiano in continuazione, questa invece ama più i robot del genere umano. Il personaggio, però, non è analizzato a fondo: è "solo" un co-protagonista di molti racconti. Ma è molto amato da Asimov che, in Tutti i miei Robot, la descrive così:
In Bugiardo!, la terza storia di robot che ho scritto, introducevo il personaggio di Susan Calvin, un personaggio di cui mi innamorai immediatamente. Da allora in poi Susan dominò a tal punto i miei pensieri, che a poco a poco spodestò del tutto Powell e Donovan. Questi ultimi apparvero solo nei tre racconti inclusi nella sezione precedente, e anche in un quarto, Evasione, in cui li affiancavo a Susan Calvin.
Ripensando alla mia carriera di autore ho in qualche modo l'impressione di avere incluso la cara Susan in innumerevoli storie, ma in realtà i racconti in cui compare sono solo dieci, tutti quanti compresi in questa sezione. Nel decimo, Intuito femminile, è una vecchia signora già da tempo in pensione, che però non ha perso un grammo del suo fascino acido.
A proposito, noterete che se anche la maggior parte dei racconti che hanno a protagonista Susan Calvin fu scritta in un'epoca in cui lo sciovinismo maschile era la regola nella letteratura fantascientifica, Susan non chiede mai favori e batte gli uomini sul loro stesso terreno. Certo, resta una donna sessualmente insoddisfatta, ma non si può avere tutto.
Una citazione da La prova, che fa capire che tipo è la dottoressa:
— […] Siete la dottoressa Susan Calvin o mi sbaglio?
— Non vi sbagliate, signor Byerley.
— Siete la psicologa della U.S. Robots, vero?
— Non psicologa, ma robopsicologa.
— Oh, perché, i robot sono così diversi dagli uomini, dal punto di vista mentale?
— Diversissimi. — La Calvin si concesse un sorriso gelido. — I robot sono fondamentalmente onesti.
Il rischio, a parlare di Susan Calvin, è che gli studenti si guardino il film Io, Robot. Bisogna proibirglielo con ogni mezzo, lecito o illecito.
Ma la mia protagonista femminile preferita, o temuta, è Janet, che compare in un breve racconto di circa quattordici pagine di Shekley, intitolato La settima vittima. Non so se dire di più, rischiando di rovinare la lettura a chi non conoscesse ancora il racconto che compare nella antologia di fantascienza Le meraviglie del possibile (consigliatissima, da leggere assolutamente). In un mondo in cui sono state combattute quattro guerre mondiali (sei secondo alcuni storici) e in cui tutti si sono resi conto che una nuova guerra sarebbe stata l'ultima, perché avrebbe sicuramente cancellato l'uomo dall'esistenza, la pace deve durare per sempre. Ma come incanalare la naturale violenza dell'uomo? La competizione, la lotta, il coraggio di fronte all'imprevisto, sono garanzie di perpetuazione della specie, non possono essere eliminate: è per questo che l'assassinio viene legalizzato, su basi strettamente individuali e per coloro che lo richiedono. Ogni individuo può commettere tutti gli omicidi che desidera, ma tra uno e l'altro deve fare la parte della Vittima. Su queste basi si sviluppa un racconto del quale non dico altro.
Se qualcuno ha altre idee, ogni commento è bene accetto, grazie.
venerdì 21 maggio 2010
Omaggio a Bertrand Russell
(E a Aristotele, e a Hofstadter)
Tutti i sillogismi non validi non rispettano almeno una regola.
Questo sillogismo non rispetta almeno una regola.
Quindi questo sillogismo non è valido.
Tutti i sillogismi non validi non rispettano almeno una regola.
Questo sillogismo non rispetta almeno una regola.
Quindi questo sillogismo non è valido.
domenica 16 maggio 2010
venerdì 14 maggio 2010
martedì 11 maggio 2010
Fisica Sognante
Sono appena tornato da una due-giorni a Cervia e Mirabilandia, dove ho accompagnato uno studente alla finale dei giochi matematici del Kangourou.
La premiazione è stata preceduta da una lezione, o da una conferenza, o da uno spettacolo…
Ricomincio. È stato invitato a parlare un professore di matematica e fisica di Bologna. Il quale è anche un giocoliere professionista: mentre gioca, spiega la fisica.
È quel soggetto qua:
Si chiama Federico Benuzzi, il suo sito è Fisica Sognante, dategli un'occhiata. C'è anche un filmato, tratto da un telegiornale, in cui si vede una parte del suo show.
Durante le parti buffe e le gag dello spettacolo, i bambini ridevano come dei matti. Nel momento in cui ha parlato della sua attività, dell'impegno che ci mette, della soddisfazione che si prova quando si riesce a fare una cosa per la quale si è lavorato duramente, i professori gongolavano e annuivano. Alla fine, c'è stato un gigantesco applauso con tutto il pubblico in piedi.
Bravo.
La premiazione è stata preceduta da una lezione, o da una conferenza, o da uno spettacolo…
Ricomincio. È stato invitato a parlare un professore di matematica e fisica di Bologna. Il quale è anche un giocoliere professionista: mentre gioca, spiega la fisica.
È quel soggetto qua:
Si chiama Federico Benuzzi, il suo sito è Fisica Sognante, dategli un'occhiata. C'è anche un filmato, tratto da un telegiornale, in cui si vede una parte del suo show.
Durante le parti buffe e le gag dello spettacolo, i bambini ridevano come dei matti. Nel momento in cui ha parlato della sua attività, dell'impegno che ci mette, della soddisfazione che si prova quando si riesce a fare una cosa per la quale si è lavorato duramente, i professori gongolavano e annuivano. Alla fine, c'è stato un gigantesco applauso con tutto il pubblico in piedi.
Bravo.
Alice, Bob e Eva — Come si può giocare a mental poker
“Ora che abbiamo dimostrato matematicamente l'impossibilità di giocare a mental poker, vediamo come si può negare l'evidenza, dire che la matematica sbaglia, e giocare”.
“Voglio proprio vedere”.
“Una premessa: anche se noi abbiamo sempre visto RSA come sistema di crittografia a chiave pubblica, esso può essere usato anche come sistema classico, in cui io mi tengo segrete entrambe le chiavi, quella pubblica e quella privata, e ne uso una per crittare e l'altra per decrittare”.
“Ah, sì, questo è vero: una chiave chiude e l'altra apre. Mi avevi fatto l'esempio dei lucchetti”.
“Esatto. Inoltre l'esempio dei lucchetti è particolarmente adatto, perché consente di capire un'altra proprietà che useremo per giocare: la proprietà commutativa”.
“Cioè?”.
“Cioè io posso applicare al mio messaggio prima il lucchetto 1, poi il lucchetto 2, in sequenza, poi togliere il lucchetto 1 e, solo alla fine, il 2”.
“Non capisco cosa c'entri la proprietà commutativa”.
“Immagina che io prenda il messaggio, lo inserisca in una busta sigillata, numerata con 1. Poi prendo quella busta e la inserisco in una seconda busta, numerata con 2. Cosa devo fare per leggere il messaggio?”.
“Devi aprire la busta 2 e, poi, la 1”.
“Ecco, grazie alla proprietà commutativa io posso anche aprire prima la 1 e poi la 2. L'esempio delle buste non funziona, ma quello dei lucchetti sì: io metto il mio messaggio in una scatola, e sulla serratura posso applicare quanti lucchetti voglio. Poco importa se applico prima il numero 1 e poi il 2, o viceversa. Allo stesso modo non importa l'ordine che seguo per aprirli”.
“Ah, ho capito. E RSA funziona così?”.
“Sì, perché la codifica tramite RSA prevede che tu elevi il tuo messaggio a un certo esponente. Se vuoi codificare due volte con due chiavi diverse, devi elevare due volte. Questo significa che devi moltiplicare gli esponenti, e la moltiplicazione gode della proprietà commutativa”.
“Giusto”.
“Allora vado con il protocollo per giocare. Prima di tutto Bob prende il mazzo di carte, composto da 52 messaggi e li critta tutti utilizzando la sua chiave B”.
“Una sola chiave?”.
“Sì, non facciamo distinzione tra chiave pubblica e privata: Bob tiene la sua coppia di chiavi segreta, una parte viene usata per crittare e l'altra per decrittare. Invece di parlare di coppia di chiavi, chiamiamo il tutto chiave e rendiamo più lineare tutto il discorso”.
“Ok”.
“Poi, naturalmente, Bob mescola il mazzo, cioè permuta tutti i messaggi come vuole”.
“Ma così non sbircia?”.
“Sì, lui sa l'ordine delle carte, ma vedrai che non importa. Dopo aver mescolato il mazzo, lo invia ad Alice”.
“Quindi a questo punto Alice si trova con 52 messaggi che non riesce a decodificare, mentre Bob sa tutto”.
“Esatto. Ora Alice seleziona cinque carte a caso e le trasmette a Bob. Bob le decritta e ottiene la sua mano”.
“Ah, ok. Alice non può decrittare le carte, quindi non sa cosa ha in mano Bob”.
“Proprio così. Ora Alice seleziona altre cinque carte a caso, e le critta con la sua chiave A, poi le invia a Bob”.
“E Bob non può leggerle, perché Alice le ha crittate!”.
“Esatto. Bob può però togliere il suo lucchetto, grazie alla proprietà commutativa del sistema RSA. Lui decodifica i cinque messaggi inviatigli da Alice, ma non può leggerli perché Alice ha messo su di essi anche la sua chiave”.
“E cosa se ne fa di questi cinque messaggi mezzi decrittati?”.
“Li rispedisce ad Alice, la quale può ora togliere la sua chiave e, finalmente, leggerli: ecco la mano di Alice”.
“Ma è geniale”.
“Se è necessario distribuire altre carte, si ripete la procedura. Alla fine della mano i due giocatori rivelano le loro chiavi, in modo che entrambi possano controllare che l'altro non abbia barato”.
“Bellissimo. Ma, allora, com'è la storia? La dimostrazione di impossibilità è sbagliata?”.
“Ti faccio rispondere dai tre matematici:”.
“Voglio proprio vedere”.
“Una premessa: anche se noi abbiamo sempre visto RSA come sistema di crittografia a chiave pubblica, esso può essere usato anche come sistema classico, in cui io mi tengo segrete entrambe le chiavi, quella pubblica e quella privata, e ne uso una per crittare e l'altra per decrittare”.
“Ah, sì, questo è vero: una chiave chiude e l'altra apre. Mi avevi fatto l'esempio dei lucchetti”.
“Esatto. Inoltre l'esempio dei lucchetti è particolarmente adatto, perché consente di capire un'altra proprietà che useremo per giocare: la proprietà commutativa”.
“Cioè?”.
“Cioè io posso applicare al mio messaggio prima il lucchetto 1, poi il lucchetto 2, in sequenza, poi togliere il lucchetto 1 e, solo alla fine, il 2”.
“Non capisco cosa c'entri la proprietà commutativa”.
“Immagina che io prenda il messaggio, lo inserisca in una busta sigillata, numerata con 1. Poi prendo quella busta e la inserisco in una seconda busta, numerata con 2. Cosa devo fare per leggere il messaggio?”.
“Devi aprire la busta 2 e, poi, la 1”.
“Ecco, grazie alla proprietà commutativa io posso anche aprire prima la 1 e poi la 2. L'esempio delle buste non funziona, ma quello dei lucchetti sì: io metto il mio messaggio in una scatola, e sulla serratura posso applicare quanti lucchetti voglio. Poco importa se applico prima il numero 1 e poi il 2, o viceversa. Allo stesso modo non importa l'ordine che seguo per aprirli”.
“Ah, ho capito. E RSA funziona così?”.
“Sì, perché la codifica tramite RSA prevede che tu elevi il tuo messaggio a un certo esponente. Se vuoi codificare due volte con due chiavi diverse, devi elevare due volte. Questo significa che devi moltiplicare gli esponenti, e la moltiplicazione gode della proprietà commutativa”.
“Giusto”.
“Allora vado con il protocollo per giocare. Prima di tutto Bob prende il mazzo di carte, composto da 52 messaggi e li critta tutti utilizzando la sua chiave B”.
“Una sola chiave?”.
“Sì, non facciamo distinzione tra chiave pubblica e privata: Bob tiene la sua coppia di chiavi segreta, una parte viene usata per crittare e l'altra per decrittare. Invece di parlare di coppia di chiavi, chiamiamo il tutto chiave e rendiamo più lineare tutto il discorso”.
“Ok”.
“Poi, naturalmente, Bob mescola il mazzo, cioè permuta tutti i messaggi come vuole”.
“Ma così non sbircia?”.
“Sì, lui sa l'ordine delle carte, ma vedrai che non importa. Dopo aver mescolato il mazzo, lo invia ad Alice”.
“Quindi a questo punto Alice si trova con 52 messaggi che non riesce a decodificare, mentre Bob sa tutto”.
“Esatto. Ora Alice seleziona cinque carte a caso e le trasmette a Bob. Bob le decritta e ottiene la sua mano”.
“Ah, ok. Alice non può decrittare le carte, quindi non sa cosa ha in mano Bob”.
“Proprio così. Ora Alice seleziona altre cinque carte a caso, e le critta con la sua chiave A, poi le invia a Bob”.
“E Bob non può leggerle, perché Alice le ha crittate!”.
“Esatto. Bob può però togliere il suo lucchetto, grazie alla proprietà commutativa del sistema RSA. Lui decodifica i cinque messaggi inviatigli da Alice, ma non può leggerli perché Alice ha messo su di essi anche la sua chiave”.
“E cosa se ne fa di questi cinque messaggi mezzi decrittati?”.
“Li rispedisce ad Alice, la quale può ora togliere la sua chiave e, finalmente, leggerli: ecco la mano di Alice”.
“Ma è geniale”.
“Se è necessario distribuire altre carte, si ripete la procedura. Alla fine della mano i due giocatori rivelano le loro chiavi, in modo che entrambi possano controllare che l'altro non abbia barato”.
“Bellissimo. Ma, allora, com'è la storia? La dimostrazione di impossibilità è sbagliata?”.
“Ti faccio rispondere dai tre matematici:”.
Initially we proved that the card-dealing problem is insoluble, and then we presented a working solution to the problem. We leave it to you, the reader, the puzzle of reconciling these results. (Hint: each player would in fact be able to determine the other player's hand from the available information, if it were not for the enormous computational difficulty of doing so by “breaking” the code.)
lunedì 10 maggio 2010
Alice, Bob e Eva — Perché non si può giocare a mental poker
“Non posso credere che una dimostrazione matematica sia sbagliata”.
“Ma non lo è”.
“Allora non è vero che si riesce a giocare a poker via telefono”.
“E invece lo è. Ti riporto le parole degli autori:”.
“Enjoyable task? Questi sono matti”.
“Te l'ho detto che si sono divertiti un sacco, no?”.
“Ma com'è la faccenda, allora? Dice che i due risultati sono apparentemente contraddittori”.
“Sì, vediamo la prima parte, per adesso”.
“Ok”.
“Per semplicità, supponiamo che ci siano solo due giocatori, i soliti Alice e Bob, e un mazzo di tre carte, X, Y e Z”.
“Solo tre?”.
“Ce ne devono essere almeno tre, in modo che sia Alice che Bob non possano conoscere la carta dell'altro”.
“Va bene”.
“Allora, supponiamo che esista un sistema per giocare a poker via telefono. Esso prevederà che vengano scambiati alcuni messaggi lungo la linea telefonica”.
“Quali messaggi?”.
“Non lo sappiamo, non sappiamo ancora se esiste questo sistema, né come è fatto. Immaginiamo che esista, e proviamo a vedere che succede. Supponiamo che alla fine Alice ottenga la carta X e Bob la carta Y: per arrivare a questa situazione si sono prima parlati”.
“Mh, ok, per giocare Alice e Bob devono certamente parlarsi, è l'unica cosa che possono fare col telefono”.
“Bene. Quindi il sistema è composto da un certo numero di messaggi, M1, M2, …, Mn. Ora indichiamo con SA l'insieme delle carte che Alice potrebbe aver ottenuto in seguito allo scambio di quei messaggi”.
“Ma come, non abbiamo detto che ne ottengono una per uno? Alice avrà una carta sola, no?”.
“Sì, certo, una sola. L'insieme SA contiene però tutte le carte permesse da quell'insieme di messaggi. Magari il protocollo prevede che i due giocatori possano fare scelte casuali, e quindi uno stesso scambio di messaggi potrebbe anche dare luogo a carte diverse”.
“Mh, non mi viene in mente nessun metodo che funzioni così, però capisco che in linea teorica non possiamo dare niente per scontato”.
“Proviamo ad andare avanti: se SA contiene solo X, allora non è vero che Bob non ha informazioni riguardanti le carte di Alice: in questo caso la sequenza di messaggi determina univocamente le carte di Alice, e quindi Bob sa”.
“Mi pare giusto”.
“Quindi SA non può contenere soltanto X (che è la carta effettivamente presa da Alice), ma deve contenerne anche qualcun altra: ecco perché dicevo che la sequenza di messaggi deve essere compatibile con più assegnazioni di carte. Se la sequenza di messaggi fosse solo associabile alla carta X, Bob potrebbe scoprire la mano di Alice analizzando proprio tutti i messaggi”.
“Va bene. Quindi?”.
“D'altra parte, se SA contiene tutte e tre le carte, allora Bob non può avere nessuna carta: qualunque carta egli scelga, potrebbe averla già Alice”.
“Anche questo è vero. Quindi SA deve contenere due elementi?”.
“Proprio così. Ma anche l'insieme di carte che può ottenere Bob dovrà, per simmetria, avere due elementi. I ruoli di Alice e Bob sono perfettamente simmetrici, se SA contiene due carte, anche SB (l'insieme di carte che potrebbero essere assegnate a Bob) ne conterrà due”.
“Ma le carte sono in tutto tre”.
“Esattamente, quindi SA e SB devono avere un elemento in comune. Nel nostro esempio è Z, che potrebbe essere assegnata a Alice o a Bob”.
“E questo è un problema?”.
“Eh, questo significa che la sequenza di messaggi M1, …, Mn è compatibile sia col fatto che Alice ottenga la carta Z, sia che Bob ottenga la stessa carta. Quindi il protocollo non garantisce che Bob e Alice ottengano carte diverse. E dunque il mental poker non è realizzabile. C.V.D.”.
“Ah”.
“La prossima volta vediamo come si può giocare a mental poker”.
“Grrr”.
“Ma non lo è”.
“Allora non è vero che si riesce a giocare a poker via telefono”.
“E invece lo è. Ti riporto le parole degli autori:”.
We will present two solutions to the problem of playing Mental Poker:
1. A rigorous proof that it is theoretically impossible to deal the cards in a way which simultaneously ensures that the two hands are disjoint and that neither player has any knowledge of the other player's hand (other than that the opponent's hand is disjoint from his).
2. An elegant protocol for dealing the cards that permits one to play a fair game of Mental Poker as desired.
The blatant contradiction between our two results is not due to any tricks or faults in either result. In fact, we will leave to the reader the enjoyable task of puzzling out the differences in the underlying assumptions that account for our seemingly contradictory results.
“Enjoyable task? Questi sono matti”.
“Te l'ho detto che si sono divertiti un sacco, no?”.
“Ma com'è la faccenda, allora? Dice che i due risultati sono apparentemente contraddittori”.
“Sì, vediamo la prima parte, per adesso”.
“Ok”.
“Per semplicità, supponiamo che ci siano solo due giocatori, i soliti Alice e Bob, e un mazzo di tre carte, X, Y e Z”.
“Solo tre?”.
“Ce ne devono essere almeno tre, in modo che sia Alice che Bob non possano conoscere la carta dell'altro”.
“Va bene”.
“Allora, supponiamo che esista un sistema per giocare a poker via telefono. Esso prevederà che vengano scambiati alcuni messaggi lungo la linea telefonica”.
“Quali messaggi?”.
“Non lo sappiamo, non sappiamo ancora se esiste questo sistema, né come è fatto. Immaginiamo che esista, e proviamo a vedere che succede. Supponiamo che alla fine Alice ottenga la carta X e Bob la carta Y: per arrivare a questa situazione si sono prima parlati”.
“Mh, ok, per giocare Alice e Bob devono certamente parlarsi, è l'unica cosa che possono fare col telefono”.
“Bene. Quindi il sistema è composto da un certo numero di messaggi, M1, M2, …, Mn. Ora indichiamo con SA l'insieme delle carte che Alice potrebbe aver ottenuto in seguito allo scambio di quei messaggi”.
“Ma come, non abbiamo detto che ne ottengono una per uno? Alice avrà una carta sola, no?”.
“Sì, certo, una sola. L'insieme SA contiene però tutte le carte permesse da quell'insieme di messaggi. Magari il protocollo prevede che i due giocatori possano fare scelte casuali, e quindi uno stesso scambio di messaggi potrebbe anche dare luogo a carte diverse”.
“Mh, non mi viene in mente nessun metodo che funzioni così, però capisco che in linea teorica non possiamo dare niente per scontato”.
“Proviamo ad andare avanti: se SA contiene solo X, allora non è vero che Bob non ha informazioni riguardanti le carte di Alice: in questo caso la sequenza di messaggi determina univocamente le carte di Alice, e quindi Bob sa”.
“Mi pare giusto”.
“Quindi SA non può contenere soltanto X (che è la carta effettivamente presa da Alice), ma deve contenerne anche qualcun altra: ecco perché dicevo che la sequenza di messaggi deve essere compatibile con più assegnazioni di carte. Se la sequenza di messaggi fosse solo associabile alla carta X, Bob potrebbe scoprire la mano di Alice analizzando proprio tutti i messaggi”.
“Va bene. Quindi?”.
“D'altra parte, se SA contiene tutte e tre le carte, allora Bob non può avere nessuna carta: qualunque carta egli scelga, potrebbe averla già Alice”.
“Anche questo è vero. Quindi SA deve contenere due elementi?”.
“Proprio così. Ma anche l'insieme di carte che può ottenere Bob dovrà, per simmetria, avere due elementi. I ruoli di Alice e Bob sono perfettamente simmetrici, se SA contiene due carte, anche SB (l'insieme di carte che potrebbero essere assegnate a Bob) ne conterrà due”.
“Ma le carte sono in tutto tre”.
“Esattamente, quindi SA e SB devono avere un elemento in comune. Nel nostro esempio è Z, che potrebbe essere assegnata a Alice o a Bob”.
“E questo è un problema?”.
“Eh, questo significa che la sequenza di messaggi M1, …, Mn è compatibile sia col fatto che Alice ottenga la carta Z, sia che Bob ottenga la stessa carta. Quindi il protocollo non garantisce che Bob e Alice ottengano carte diverse. E dunque il mental poker non è realizzabile. C.V.D.”.
“Ah”.
“La prossima volta vediamo come si può giocare a mental poker”.
“Grrr”.
venerdì 7 maggio 2010
Alice, Bob e Eva — Zero Knowledge
“Conoscenza zero?”.
“Sì”.
“E cosa significa?”.
“Significa che io so un segreto, ti dimostro che lo conosco, ma non ti dico qual è”.
“Ma dai. E come è possibile?”.
“Con le conoscenze che possediamo ora, è possibile. Ti faccio un esempio facile, che semplifica un po' le cose, ma che fa capire come funziona il tutto. Si tratta di giocare a testa o croce”.
“Dici il gioco con la moneta?”.
“Sì, si scommette sull'esito del lancio di una moneta. Però ci giochiamo via telefono. Tu sei a un capo del telefono, io all'altro, e naturalmente non ci possiamo vedere. Quindi se io lancio la moneta tu non vedi il risultato”.
“E dovrei fidarmi di quello che mi dici tu?”.
“Sì”.
“Figuriamoci”.
“Ma io devo fare in modo che tu ti possa fidare al di sopra di ogni ragionevole dubbio. Questo significa che io ti devo dimostrare di conoscere il segreto (cioè l'esito del lancio) senza però rivelartelo subito, perché altrimenti tu non puoi scommettere”.
“Ma come fai?”.
“Ci accordiamo su questa procedura: io lancio la moneta, se viene testa genero due numeri primi grandi e congruenti a 1 modulo 4. Se viene croce genero due numeri primi grandi e congruenti a 3 modulo 4”.
“Uhm, perchè?”.
“Ora li moltiplico. Supponi che sia uscita testa: se calcolo il resto della divisione per 4 del prodotto cosa ottengo?”.
“Dunque, hai due numeri congruenti a 1, se li moltiplichi tra loro ottieni due numeri congruenti a 12, cioè ancora 1”.
“Perfetto. Ora supponi che sia uscita croce. Se moltiplichi i due numeri cosa ottieni, questa volta?”.
“Questa volta ottengo un numero congruente a 32, cioè 9. Un momento, 9 è congruente a 1 modulo 4”.
“Esatto. Quindi, sia in un caso che nell'altro il numerone che ottengo è congruente a 1. Te lo trasmetto via telefono”.
“Forse comincio a capire”.
“Appena tu ricevi il numero devi scommettere: testa o croce? Naturalmente analizzando il numero non puoi sapere se è uscita testa o croce, perché puoi, in modo veloce, solo calcolare la sua congruenza modulo 4, ma non fattorizzarlo”.
“Ah, di nuovo il problema della fattorizzazione… Quindi io ricevo il numero, scommetto, e poi tu mi dici quello che è uscito? Come faccio a fidarmi?”.
“Io non ti comunico quello che è uscito, ma ti comunico i due numeri. Tu puoi moltiplicarli e vedere se il loro prodotto è uguale al numerone oppure no. Dopo aver fatto la verifica, puoi calcolare la congruenza modulo 4 dei due numeri: se è uguale a 1 è uscita testa, se invece è 3 allora è uscita croce”.
“Bella roba: ci si riesce, non l'avrei mai detto. Certo che testa o croce è proprio il gioco più facile che ci sia”.
“Se vuoi, si può giocare anche a poker via telefono”.
“Poker? Vuoi dire che si riesce a gestire un mazzo di carte senza poterle vedere?”.
“Certo. Per essere precisi: in un articolo i nostri amici Shamir, Rivest e Adleman prima dimostrano che è matematicamente impossibile giocare a poker via telefono, poi mostrano un protocollo corretto, completo e funzionante per farlo”.
“Cosa? Ma così cadono tutte le mie certezze nei confronti della matematica!”.
“Già. Shamir, Rivest e Adleman devono essersi divertiti un sacco a scriverlo”.
“Sì”.
“E cosa significa?”.
“Significa che io so un segreto, ti dimostro che lo conosco, ma non ti dico qual è”.
“Ma dai. E come è possibile?”.
“Con le conoscenze che possediamo ora, è possibile. Ti faccio un esempio facile, che semplifica un po' le cose, ma che fa capire come funziona il tutto. Si tratta di giocare a testa o croce”.
“Dici il gioco con la moneta?”.
“Sì, si scommette sull'esito del lancio di una moneta. Però ci giochiamo via telefono. Tu sei a un capo del telefono, io all'altro, e naturalmente non ci possiamo vedere. Quindi se io lancio la moneta tu non vedi il risultato”.
“E dovrei fidarmi di quello che mi dici tu?”.
“Sì”.
“Figuriamoci”.
“Ma io devo fare in modo che tu ti possa fidare al di sopra di ogni ragionevole dubbio. Questo significa che io ti devo dimostrare di conoscere il segreto (cioè l'esito del lancio) senza però rivelartelo subito, perché altrimenti tu non puoi scommettere”.
“Ma come fai?”.
“Ci accordiamo su questa procedura: io lancio la moneta, se viene testa genero due numeri primi grandi e congruenti a 1 modulo 4. Se viene croce genero due numeri primi grandi e congruenti a 3 modulo 4”.
“Uhm, perchè?”.
“Ora li moltiplico. Supponi che sia uscita testa: se calcolo il resto della divisione per 4 del prodotto cosa ottengo?”.
“Dunque, hai due numeri congruenti a 1, se li moltiplichi tra loro ottieni due numeri congruenti a 12, cioè ancora 1”.
“Perfetto. Ora supponi che sia uscita croce. Se moltiplichi i due numeri cosa ottieni, questa volta?”.
“Questa volta ottengo un numero congruente a 32, cioè 9. Un momento, 9 è congruente a 1 modulo 4”.
“Esatto. Quindi, sia in un caso che nell'altro il numerone che ottengo è congruente a 1. Te lo trasmetto via telefono”.
“Forse comincio a capire”.
“Appena tu ricevi il numero devi scommettere: testa o croce? Naturalmente analizzando il numero non puoi sapere se è uscita testa o croce, perché puoi, in modo veloce, solo calcolare la sua congruenza modulo 4, ma non fattorizzarlo”.
“Ah, di nuovo il problema della fattorizzazione… Quindi io ricevo il numero, scommetto, e poi tu mi dici quello che è uscito? Come faccio a fidarmi?”.
“Io non ti comunico quello che è uscito, ma ti comunico i due numeri. Tu puoi moltiplicarli e vedere se il loro prodotto è uguale al numerone oppure no. Dopo aver fatto la verifica, puoi calcolare la congruenza modulo 4 dei due numeri: se è uguale a 1 è uscita testa, se invece è 3 allora è uscita croce”.
“Bella roba: ci si riesce, non l'avrei mai detto. Certo che testa o croce è proprio il gioco più facile che ci sia”.
“Se vuoi, si può giocare anche a poker via telefono”.
“Poker? Vuoi dire che si riesce a gestire un mazzo di carte senza poterle vedere?”.
“Certo. Per essere precisi: in un articolo i nostri amici Shamir, Rivest e Adleman prima dimostrano che è matematicamente impossibile giocare a poker via telefono, poi mostrano un protocollo corretto, completo e funzionante per farlo”.
“Cosa? Ma così cadono tutte le mie certezze nei confronti della matematica!”.
“Già. Shamir, Rivest e Adleman devono essersi divertiti un sacco a scriverlo”.
giovedì 6 maggio 2010
Alice, Bob e Eva — THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
Nel numero di Agosto 1977 di Scientific American, la rubrica Mathematical Games di Martin Gardner aveva il seguente titolo: A new kind of cipher that would take millions of years to break. In essa, Gardner aveva scritto una delle prime descrizioni del sistema di crittografia a chiave pubblica RSA.
Gli inventori di RSA avevano anche preparato una sfida per i lettori: dato il sistema di codifica secondo il quale A = 01, B = 02, e così via fino a Z = 26 e spazio = 00; data la seguente chiave pubblica (n,e):
dato il testo cifrato
ricavare il testo in chiaro.
Già nel 1976 il matematico Richard Guy scrisse:
Nel 1977 Rivest, in una lettera a Martin Gardner, stimò che il tempo necessario per fattorizzare un numero di 125 cifre che è il prodotto di due numeri primi di 63 cifre dovesse essere almeno di 40 quadrilioni di anni (qualunque significato diamo alla parola quadrilione, è comunque un sacco di tempo). Tempo calcolato sulla base del miglior algoritmo di fattorizzazione noto all'epoca, e supponendo che un singolo prodotto ab modulo c potesse essere calcolato in un nanosecondo (e questo era fantascienza).
Sicuri del fatto che il loro codice non sarebbe mai stato decrittato, gli inventori di RSA offrirono un premio di 100 dollari al primo che fosse riuscito a trovare il testo del messaggio in chiaro.
Nel 1993 un gruppo di matematici, composto da Atkins, Graff, Lenstra e Leyland, cominciarono a pensare al modo di fattorizzare il numero n in tempi umani. Per prima cosa ricalcolarono la stima fatta da Rivest nel 1977, e trovarono un errore. Probabilmente Rivest aveva contato male il numero degli zeri, perché il tempo stimato dal gruppo era di soli 4 quadrilioni di anni, e non 40, per un totale di circa 1.3·1032 moltiplicazioni modulari.
Successivamente al 1977, però, la ricerca aveva compiuto grossi passi avanti nella fattorizzazione dei numeri interi, e allo stesso tempo la velocità dei computer era aumentata enormemente. Con hardware costruito ad hoc e tecniche di pipelining, con ritardi di gate di circa 10 picosecondi, si sarebbe forse riusciti ad arrivare al record di una moltiplicazione modulare ogni nanosecondo. In questo caso, utilizzando il nuovo metodo di fattorizzazione che utilizza le curve ellittiche (scoperto da uno dei quattro matematici, Lenstra), il gruppo stimò un tempo di circa due mesi: 240 quadrilioni di volte più veloce rispetto alla stima di Rivest, per un totale di circa 5·1015 moltiplicazioni modulari. E tutto grazie al progresso nelle tecniche di fattorizzazione.
Su un computer normale, però, il tempo di calcolo era ancora proibitivo: la stima era di circa 15000 anni su una workstation Sparc 10.
Stime fatte utilizzando un altro metodo di fattorizzazione, il crivello quadratico, abbassarono ulteriormente il tempo di calcolo: circa 120 anni su una workstation Sparc 10. Per rendere i calcoli indipendenti dalla macchina, si usa un'unità di misura diversa, il mips·anno. Un mips corrisponde a un milione di operazioni elementari per secondo, e quindi un mips·anno corrisponde al numero di operazioni elementari che una macchina con potenza uguale a 1 mips può effettuare in un anno. La stima per fattorizzare n era di circa 4200 mips·anno. Ce la potevano fare.
Non da soli, naturalmente, ma con l'aiuto di uno dei più grandi gruppi di ricerca dell'epoca: il calcolo distribuito su internet.
Le stime erano le seguenti: servivano circa 8 milioni di relazioni, ognuna delle quali occupava circa 350 byte. Il programma doveva tenere in memoria un numero di fattori compreso tra 400000 e 600000, per un totale di 8 MByte. In tutto, il programma utilizzava 10.5 MByte di memoria. All'epoca molti computer affacciati a internet erano dotati di meno di 16 MByte, e molti ne avevano meno di 8.
Atkins e Leyland compilarono il loro programma per il maggior numero possibile di workstation e PC. Il gruppo ottenne in prestito un file server del MIT per la durata del progetto: era un DEC 5000/240 con 32 MByte di RAM e due dischi da 985 MByte. Il terzo disco fu aggiunto poco tempo dopo.
Il 19 agosto 1993 il progetto pubblicò la sua prima richiesta di aiuto nella number theory net, il 23 agosto scrisse ai cypherpunk e al PGP development group, e infine il 24 agosto nei newgroup alt.hackers, alt.security, alt.security.pgp, alt.security.ripem, comp.arch, comp.security.misc, sci.crypt, sci.math (questo, almeno, è quanto riporta l'articolo scritto dal gruppo, ma google groups riporta un'alta data).
Il codice venne fatto girare su macchine molto diverse tra loro: c'erano degli 80386sx a 16MHz e dei Cray C90. Non si riuscì a compilare il codice per una Thinking Machine CM-5, mentre una azienda americana riuscì a farlo girare su due fax (sì, non è sbagliato, due fax).
Per poter fare girare il codice sul maggior numero di macchine possibile, venne ridotto lo spazio di memoria necessario al programma per girare: si passò da 10.5 a 6.5Mbyte, ma il programma dimezzò la sua velocità. Nonostante questo rallentamento, il bilancio fu positivo, perché poterono partecipare molti computer che altrimenti non avrebbero avuto le caratteristiche necessarie.
Parteciparono 600 persone e 1600 computer, una piccola frazione di tutte la capacità di calcolo disponibile. Se tutta la potenza di internet fosse stata disponibile, n sarebbe stato fattorizzato in sole tre ore. L'ottanta per cento del lavoro fu svolto dai volontari, il restante venti per cento da alcuni computer MasPar gestiti da Lenstra e collaboratori.
Il 21 marzo 1994 il coordinamento del progetto aveva raccolto il numero necessario di relazioni, e il 22 marzo venne spedito a tutti i contributori il messaggio di cease and desist. Dopo 220 giorni di setacciamento, il 26 marzo fu fatto il conteggio finale: c'erano 8424486 relazioni da analizzare. Una parte di queste relazioni fu salvata su nastro magnetico e spedita da Atkins a Lenstra mediante il normale servizio postale notturno. Un'altra parte fu trasferita via ftp.
I dati vennero analizzati da un computer MasPar MP-1: dopo 45 ore, alle 18:15 UT del 2 aprile 1994, venne trovata la fattorizzazione di n:
Ecco l'annuncio.
Il messaggio cifrato da Rivest venne quindi decifrato. Il testo in chiaro era:
che, tradotto secondo la codifica utilizzata da Rivest, diventa:
Vennero usati dai 4000 ai 6000 mips·anno.
(Tutta la storia è raccontata qui)
Gli inventori di RSA avevano anche preparato una sfida per i lettori: dato il sistema di codifica secondo il quale A = 01, B = 02, e così via fino a Z = 26 e spazio = 00; data la seguente chiave pubblica (n,e):
n = 11438162575788886766923577997614661201021829672124236256256184293
5706935245733897830597123563958705058989075147599290026879543541,e = 9007;
dato il testo cifrato
c = 9686961375462206147714092225435588290575999112457431987469512093
0816298225145708356931476622883989628013391990551829945157815154;ricavare il testo in chiaro.
Già nel 1976 il matematico Richard Guy scrisse:
“Sarei molto sorpreso se qualcuno riuscisse a fattorizzare numeri delle dimensioni di 1080, senza utilizzare forme particolari, nel presente secolo”.
Nel 1977 Rivest, in una lettera a Martin Gardner, stimò che il tempo necessario per fattorizzare un numero di 125 cifre che è il prodotto di due numeri primi di 63 cifre dovesse essere almeno di 40 quadrilioni di anni (qualunque significato diamo alla parola quadrilione, è comunque un sacco di tempo). Tempo calcolato sulla base del miglior algoritmo di fattorizzazione noto all'epoca, e supponendo che un singolo prodotto ab modulo c potesse essere calcolato in un nanosecondo (e questo era fantascienza).
Sicuri del fatto che il loro codice non sarebbe mai stato decrittato, gli inventori di RSA offrirono un premio di 100 dollari al primo che fosse riuscito a trovare il testo del messaggio in chiaro.
Nel 1993 un gruppo di matematici, composto da Atkins, Graff, Lenstra e Leyland, cominciarono a pensare al modo di fattorizzare il numero n in tempi umani. Per prima cosa ricalcolarono la stima fatta da Rivest nel 1977, e trovarono un errore. Probabilmente Rivest aveva contato male il numero degli zeri, perché il tempo stimato dal gruppo era di soli 4 quadrilioni di anni, e non 40, per un totale di circa 1.3·1032 moltiplicazioni modulari.
Successivamente al 1977, però, la ricerca aveva compiuto grossi passi avanti nella fattorizzazione dei numeri interi, e allo stesso tempo la velocità dei computer era aumentata enormemente. Con hardware costruito ad hoc e tecniche di pipelining, con ritardi di gate di circa 10 picosecondi, si sarebbe forse riusciti ad arrivare al record di una moltiplicazione modulare ogni nanosecondo. In questo caso, utilizzando il nuovo metodo di fattorizzazione che utilizza le curve ellittiche (scoperto da uno dei quattro matematici, Lenstra), il gruppo stimò un tempo di circa due mesi: 240 quadrilioni di volte più veloce rispetto alla stima di Rivest, per un totale di circa 5·1015 moltiplicazioni modulari. E tutto grazie al progresso nelle tecniche di fattorizzazione.
Su un computer normale, però, il tempo di calcolo era ancora proibitivo: la stima era di circa 15000 anni su una workstation Sparc 10.
Stime fatte utilizzando un altro metodo di fattorizzazione, il crivello quadratico, abbassarono ulteriormente il tempo di calcolo: circa 120 anni su una workstation Sparc 10. Per rendere i calcoli indipendenti dalla macchina, si usa un'unità di misura diversa, il mips·anno. Un mips corrisponde a un milione di operazioni elementari per secondo, e quindi un mips·anno corrisponde al numero di operazioni elementari che una macchina con potenza uguale a 1 mips può effettuare in un anno. La stima per fattorizzare n era di circa 4200 mips·anno. Ce la potevano fare.
Non da soli, naturalmente, ma con l'aiuto di uno dei più grandi gruppi di ricerca dell'epoca: il calcolo distribuito su internet.
Le stime erano le seguenti: servivano circa 8 milioni di relazioni, ognuna delle quali occupava circa 350 byte. Il programma doveva tenere in memoria un numero di fattori compreso tra 400000 e 600000, per un totale di 8 MByte. In tutto, il programma utilizzava 10.5 MByte di memoria. All'epoca molti computer affacciati a internet erano dotati di meno di 16 MByte, e molti ne avevano meno di 8.
Atkins e Leyland compilarono il loro programma per il maggior numero possibile di workstation e PC. Il gruppo ottenne in prestito un file server del MIT per la durata del progetto: era un DEC 5000/240 con 32 MByte di RAM e due dischi da 985 MByte. Il terzo disco fu aggiunto poco tempo dopo.
Il 19 agosto 1993 il progetto pubblicò la sua prima richiesta di aiuto nella number theory net, il 23 agosto scrisse ai cypherpunk e al PGP development group, e infine il 24 agosto nei newgroup alt.hackers, alt.security, alt.security.pgp, alt.security.ripem, comp.arch, comp.security.misc, sci.crypt, sci.math (questo, almeno, è quanto riporta l'articolo scritto dal gruppo, ma google groups riporta un'alta data).
Il codice venne fatto girare su macchine molto diverse tra loro: c'erano degli 80386sx a 16MHz e dei Cray C90. Non si riuscì a compilare il codice per una Thinking Machine CM-5, mentre una azienda americana riuscì a farlo girare su due fax (sì, non è sbagliato, due fax).
Per poter fare girare il codice sul maggior numero di macchine possibile, venne ridotto lo spazio di memoria necessario al programma per girare: si passò da 10.5 a 6.5Mbyte, ma il programma dimezzò la sua velocità. Nonostante questo rallentamento, il bilancio fu positivo, perché poterono partecipare molti computer che altrimenti non avrebbero avuto le caratteristiche necessarie.
Parteciparono 600 persone e 1600 computer, una piccola frazione di tutte la capacità di calcolo disponibile. Se tutta la potenza di internet fosse stata disponibile, n sarebbe stato fattorizzato in sole tre ore. L'ottanta per cento del lavoro fu svolto dai volontari, il restante venti per cento da alcuni computer MasPar gestiti da Lenstra e collaboratori.
Il 21 marzo 1994 il coordinamento del progetto aveva raccolto il numero necessario di relazioni, e il 22 marzo venne spedito a tutti i contributori il messaggio di cease and desist. Dopo 220 giorni di setacciamento, il 26 marzo fu fatto il conteggio finale: c'erano 8424486 relazioni da analizzare. Una parte di queste relazioni fu salvata su nastro magnetico e spedita da Atkins a Lenstra mediante il normale servizio postale notturno. Un'altra parte fu trasferita via ftp.
I dati vennero analizzati da un computer MasPar MP-1: dopo 45 ore, alle 18:15 UT del 2 aprile 1994, venne trovata la fattorizzazione di n:
n = 3490529510847650949147849619903898133417764638493387843990820577 ·
32769132993266709549961988190834461413177642967992942539798288533
Ecco l'annuncio.
Il messaggio cifrato da Rivest venne quindi decifrato. Il testo in chiaro era:
200805001301070903002315180419000118050019172105011309190800151919090618010705
che, tradotto secondo la codifica utilizzata da Rivest, diventa:
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
Vennero usati dai 4000 ai 6000 mips·anno.
(Tutta la storia è raccontata qui)
mercoledì 5 maggio 2010
Alice, Bob e Eva — modpow
“Senti, ma secondo te era facile decrittare quel codice che mi hai dato da studiare?”.
“Eh, no”.
“E poi, con dei numeri così, come si fa anche solo a calcolare la potenza e il modulo? Sono numeri giganteschi”.
“Quello non è un problema, si fa in un attimo con qualunque linguaggio. Vanno benissimo anche i linguaggi ad alto livello, che supportano gli interi a qualunque precisione. Anche se sono linguaggi interpretati, non c'è problema”.
“Davvero?”.
“Sì, guarda, ti faccio vedere una funzione pyhton che fa il calcolo rapidamente”.
“Mh, non capisco mica bene”.
“Eh, perché è stato scritto tenendo presente le proprietà della notazione binaria, ma potrebbe essere scritto anche in maniera più chiara”.
“E non potevi scriverlo in maniera più chiara subito?”.
“Certo che no, è come quando i medici scrivono le diagnosi o le ricette. Meno gente capisce, più si sentono superiori”.
“Andiamo avanti, per piacere”.
“Ok, ok. Comunque la notazione che ho usato è anche didattica, eh”.
“Eh, va bene, sentiamo la scusa”.
“Per esempio, la riga if d & 1 si domanda se d AND 1 è vera, cioè se d, scritto in binario, finisce con 1, cioè se d è congruente a 1 modulo 2. È un modo rapido per controllare se d è dispari”.
“Ah, bello”.
“E la riga che trasforma d in d>>1 sta a significare che i bit di d vengono tutti spostati di uno verso destra. In pratica è la divisione di d per 2, gettando via il resto”.
“E questa serie di operazioni è proprio la potenza cd mod n?”.
“Sì. Funziona in questo modo: si prende l'esponente d in forma binaria e lo si esamina una cifra alla volta, a partire dal fondo. Se c'è una cifra zero, significa che l'esponente è pari. Allora faccio il quadrato di c e divido l'esponente 2. Se invece c'è una cifra uno, l'esponente è dispari. Allora, prima moltiplico m per c, e poi faccio come prima. Poi getto via l'ultima cifra binaria di d e ricomincio. Ecco le formule:”.
cd = (c2)d/2, se d è pari;
cd = c(c2)d/2, se d è dispari (e d/2 è la divisione in cui getto via il resto).
“Ah, e quindi non devo fare un'infinità di moltiplicazioni”.
“Eh, no, devi fare tante operazioni quante sono le cifre binarie di d: questo algoritmo ha quindi bisogno di un numero di operazioni proporzionale al logaritmo in base 2 di d. In questo caso il ciclo viene eseguito solo 426 volte”.
“Sembra quasi miracoloso”.
“Ora che hai capito, ti scrivo la funzione in maniera più comprensibile:”.
“Ah, grazie, serve a molto adesso… Comunque, rimane il problema di fattorizzare quell'n enorme. Da quanto ho capito fino ad ora, non esiste un modo veloce per farlo”.
“Eh, no. La storia di come è stato fattorizzato n la raccontiamo la prossima volta”.
“Eh, no”.
“E poi, con dei numeri così, come si fa anche solo a calcolare la potenza e il modulo? Sono numeri giganteschi”.
“Quello non è un problema, si fa in un attimo con qualunque linguaggio. Vanno benissimo anche i linguaggi ad alto livello, che supportano gli interi a qualunque precisione. Anche se sono linguaggi interpretati, non c'è problema”.
“Davvero?”.
“Sì, guarda, ti faccio vedere una funzione pyhton che fa il calcolo rapidamente”.
def modpow(c,d,n):
m=1
while d >= 1:
if d & 1:
m=c*m % n
c=c*c % n
d = d >> 1
return m
“Mh, non capisco mica bene”.
“Eh, perché è stato scritto tenendo presente le proprietà della notazione binaria, ma potrebbe essere scritto anche in maniera più chiara”.
“E non potevi scriverlo in maniera più chiara subito?”.
“Certo che no, è come quando i medici scrivono le diagnosi o le ricette. Meno gente capisce, più si sentono superiori”.
“Andiamo avanti, per piacere”.
“Ok, ok. Comunque la notazione che ho usato è anche didattica, eh”.
“Eh, va bene, sentiamo la scusa”.
“Per esempio, la riga if d & 1 si domanda se d AND 1 è vera, cioè se d, scritto in binario, finisce con 1, cioè se d è congruente a 1 modulo 2. È un modo rapido per controllare se d è dispari”.
“Ah, bello”.
“E la riga che trasforma d in d>>1 sta a significare che i bit di d vengono tutti spostati di uno verso destra. In pratica è la divisione di d per 2, gettando via il resto”.
“E questa serie di operazioni è proprio la potenza cd mod n?”.
“Sì. Funziona in questo modo: si prende l'esponente d in forma binaria e lo si esamina una cifra alla volta, a partire dal fondo. Se c'è una cifra zero, significa che l'esponente è pari. Allora faccio il quadrato di c e divido l'esponente 2. Se invece c'è una cifra uno, l'esponente è dispari. Allora, prima moltiplico m per c, e poi faccio come prima. Poi getto via l'ultima cifra binaria di d e ricomincio. Ecco le formule:”.
cd = (c2)d/2, se d è pari;
cd = c(c2)d/2, se d è dispari (e d/2 è la divisione in cui getto via il resto).
“Ah, e quindi non devo fare un'infinità di moltiplicazioni”.
“Eh, no, devi fare tante operazioni quante sono le cifre binarie di d: questo algoritmo ha quindi bisogno di un numero di operazioni proporzionale al logaritmo in base 2 di d. In questo caso il ciclo viene eseguito solo 426 volte”.
“Sembra quasi miracoloso”.
“Ora che hai capito, ti scrivo la funzione in maniera più comprensibile:”.
def modpow(c,d,n):
m=1
while d>=1:
if d % 2 == 1:
m=c*m % n
c=c*c % n
d = d/2
return m
“Ah, grazie, serve a molto adesso… Comunque, rimane il problema di fattorizzare quell'n enorme. Da quanto ho capito fino ad ora, non esiste un modo veloce per farlo”.
“Eh, no. La storia di come è stato fattorizzato n la raccontiamo la prossima volta”.
martedì 4 maggio 2010
Alice, Bob e Eva — La radice discreta
“Un altro sistema che potrebbe avere Alice per decrittare la codifica RSA senza conoscere φ(n) è quello di calcolare la radice discreta”.
“Cosa sarebbe?”.
“Bob, per codificare m, ha usato la formula c ≡ me mod n. Potremmo dire che m è la radice discreta e-esima di c, in analogia a quanto si fa con i numeri reali”.
“Ah”.
“Ad oggi non è noto alcun metodo per calcolare la radice discreta in modo veloce. Come al solito, però, non si sa se in futuro questo metodo verrà trovato oppure no. Tra l'altro, questo problema potrebbe essere anche più semplice del problema della fattorizzazione”.
“Perché?”.
“Perché mediante la fattorizzazione si può calcolare la chiave privata di Alice e, quindi, decrittare ogni messaggio destinato ad Alice. Estraendo la radice discreta del messaggio, invece, si può decrittare solo quel singolo messaggio. E, forse, decrittare un unico messaggio può essere più semplice che decrittare ogni messaggio”.
“Insomma, non si sa niente e si spera che le cose vadano bene”.
“Esattamente. Un'altra cosa carina alla quale bisogna stare attenti, ma che non capita molto spesso, è quella dei messaggi che rimangono fissi”.
“Eh?”.
“Ti faccio un esempio. Ricordi quando abbiamo fatto una prova con RSA utilizzando la chiave pubblica (n,e) = (16637,11)?”.
“Sì”.
“Prova a crittare questo messaggio: m = 2793”.
“Ecco: 279311 mod 16637 = 2793. Ehi, come è possibile?”.
“Eh, succede. Nei casi reali, con numeri giganteschi, succede rarissimamente, ma bisogna stare comunque attenti. In questo caso, con numeri piccoli, succede 32 volte. Ti lascio come esercizio il calcolo”.
“Mamma mia, mi sembra che questa crittografia sia un sistema sempre meno sicuro”.
“Eh, in genere il sistema è sicuro, ma ci possono essere tanti piccoli casi particolari che lo rendono facilmente attaccabile. Ma, a volte, può essere colpa dell'utente”.
“In che senso?”.
“Supponi che due utenti utilizzino due esponenti diversi, ma lo stesso n. Avrebbero, in pratica, due chiavi di questo tipo: (n,e1), (n,e2). Bob invia lo stesso messaggio m ai due utenti: esso verrà crittato in due modi diversi, naturalmente”.
“Sì, si fanno due calcoli diversi: c1 = me1 mod n, c2 = me2 mod n”.
“Bene. Eva li intercetta tutti e due, e calcola preventivamente due numeri a e b in modo tale che ae1 + be2 = 1”.
“Ah, una equazione diofantea. Queste ho imparato a risolverle”.
“Perfetto. Allora calcola anche c1a c2b”.
“Vediamo: c1a c2b = mae1 mbe2 = mae1 + be2 = m1 = m. Ehi, Eva decritta il messaggio!”.
“Eh, sì. Quindi è imperativo usare n diversi. Ma con 150 cifre a disposizione, c'è abbondanza di numeri primi”.
“Ci sono altri problemi?”.
“Ce ne sono di complicati, casi particolari in cui la fattorizzazione è veloce, e cose del genere. Quelli li lascerei perdere, mentre vorrei raccontarti un'ultima situazione critica che potrebbe compromettere la sicurezza”.
“Quale?”.
“Supponi di essere in guerra, per fare un esempio. Tu devi spedire con regolarità dei messaggi in cui trasmetti le coordinate per una ricognizione, o un bombardamento, o che so io. I tuoi messaggi potrebbero essere creati automaticamente, potrebbero avere una struttura standard ed essere diversi solo nel punto in cui scrivi le coordinate”.
“Sì, giusto”.
“Allora Eva potrebbe semplicemente creare tutti i possibili messaggi che tu puoi spedire, crittarli tutti quanti con la chiave pubblica di Alice, e confrontare il suo dizionario di messaggi con il messaggio che ha appena intercettato”.
“Oh cavolo, così riuscirebbe a decrittare quello che scrive Bob senza rompere RSA”.
“Esatto. Per evitare questi problemi si usa una tecnica chiamata padding”.
“In cosa consiste?”.
“Consiste nell'inserire dei caratteri casuali qua e là all'interno del messaggio, in modo da non avere mai due messaggi che sono diversi per pochi caratteri”.
“Caratteri casuali?”.
“Sì, se io volessi spedirti il messaggio Ci vediamo domani potrei, prima di crittarlo, modificarlo in Topolino Ci Pippo vediamo Pluto domani. Noi siamo già d'accordo che i personaggi dei fumetti devono essere cancellati dal messaggio, naturalmente”.
“Ah. E se Eva intercetta questo nostro accordo?”.
“Nessun problema: anche se lei è a conoscenza di questa modifica, non sa quali siano i nomi dei personaggi che io voglio usare, e non sa dove li inserisco. Quindi il suo attacco basato sullo schema fisso dei messaggi non funziona più. Il sistema usato nella realtà si chiama Optimal Asymmetric Encryption Padding”.
“Peccato, mi sarebbe piaciuto un Comics and Cartoons Encryption Padding”.
“Eh, vabbé, non si può avere tutto. Ti lascio un esempio reale di codice crittato con RSA. Il messaggio è un testo codificato in questo modo: A = 01, B = 02, …, Z = 26, e lo spazio è uguale a 00”.
“Ok”.
“Vado a capo perché non ci sto:”.
“Cosa sarebbe?”.
“Bob, per codificare m, ha usato la formula c ≡ me mod n. Potremmo dire che m è la radice discreta e-esima di c, in analogia a quanto si fa con i numeri reali”.
“Ah”.
“Ad oggi non è noto alcun metodo per calcolare la radice discreta in modo veloce. Come al solito, però, non si sa se in futuro questo metodo verrà trovato oppure no. Tra l'altro, questo problema potrebbe essere anche più semplice del problema della fattorizzazione”.
“Perché?”.
“Perché mediante la fattorizzazione si può calcolare la chiave privata di Alice e, quindi, decrittare ogni messaggio destinato ad Alice. Estraendo la radice discreta del messaggio, invece, si può decrittare solo quel singolo messaggio. E, forse, decrittare un unico messaggio può essere più semplice che decrittare ogni messaggio”.
“Insomma, non si sa niente e si spera che le cose vadano bene”.
“Esattamente. Un'altra cosa carina alla quale bisogna stare attenti, ma che non capita molto spesso, è quella dei messaggi che rimangono fissi”.
“Eh?”.
“Ti faccio un esempio. Ricordi quando abbiamo fatto una prova con RSA utilizzando la chiave pubblica (n,e) = (16637,11)?”.
“Sì”.
“Prova a crittare questo messaggio: m = 2793”.
“Ecco: 279311 mod 16637 = 2793. Ehi, come è possibile?”.
“Eh, succede. Nei casi reali, con numeri giganteschi, succede rarissimamente, ma bisogna stare comunque attenti. In questo caso, con numeri piccoli, succede 32 volte. Ti lascio come esercizio il calcolo”.
“Mamma mia, mi sembra che questa crittografia sia un sistema sempre meno sicuro”.
“Eh, in genere il sistema è sicuro, ma ci possono essere tanti piccoli casi particolari che lo rendono facilmente attaccabile. Ma, a volte, può essere colpa dell'utente”.
“In che senso?”.
“Supponi che due utenti utilizzino due esponenti diversi, ma lo stesso n. Avrebbero, in pratica, due chiavi di questo tipo: (n,e1), (n,e2). Bob invia lo stesso messaggio m ai due utenti: esso verrà crittato in due modi diversi, naturalmente”.
“Sì, si fanno due calcoli diversi: c1 = me1 mod n, c2 = me2 mod n”.
“Bene. Eva li intercetta tutti e due, e calcola preventivamente due numeri a e b in modo tale che ae1 + be2 = 1”.
“Ah, una equazione diofantea. Queste ho imparato a risolverle”.
“Perfetto. Allora calcola anche c1a c2b”.
“Vediamo: c1a c2b = mae1 mbe2 = mae1 + be2 = m1 = m. Ehi, Eva decritta il messaggio!”.
“Eh, sì. Quindi è imperativo usare n diversi. Ma con 150 cifre a disposizione, c'è abbondanza di numeri primi”.
“Ci sono altri problemi?”.
“Ce ne sono di complicati, casi particolari in cui la fattorizzazione è veloce, e cose del genere. Quelli li lascerei perdere, mentre vorrei raccontarti un'ultima situazione critica che potrebbe compromettere la sicurezza”.
“Quale?”.
“Supponi di essere in guerra, per fare un esempio. Tu devi spedire con regolarità dei messaggi in cui trasmetti le coordinate per una ricognizione, o un bombardamento, o che so io. I tuoi messaggi potrebbero essere creati automaticamente, potrebbero avere una struttura standard ed essere diversi solo nel punto in cui scrivi le coordinate”.
“Sì, giusto”.
“Allora Eva potrebbe semplicemente creare tutti i possibili messaggi che tu puoi spedire, crittarli tutti quanti con la chiave pubblica di Alice, e confrontare il suo dizionario di messaggi con il messaggio che ha appena intercettato”.
“Oh cavolo, così riuscirebbe a decrittare quello che scrive Bob senza rompere RSA”.
“Esatto. Per evitare questi problemi si usa una tecnica chiamata padding”.
“In cosa consiste?”.
“Consiste nell'inserire dei caratteri casuali qua e là all'interno del messaggio, in modo da non avere mai due messaggi che sono diversi per pochi caratteri”.
“Caratteri casuali?”.
“Sì, se io volessi spedirti il messaggio Ci vediamo domani potrei, prima di crittarlo, modificarlo in Topolino Ci Pippo vediamo Pluto domani. Noi siamo già d'accordo che i personaggi dei fumetti devono essere cancellati dal messaggio, naturalmente”.
“Ah. E se Eva intercetta questo nostro accordo?”.
“Nessun problema: anche se lei è a conoscenza di questa modifica, non sa quali siano i nomi dei personaggi che io voglio usare, e non sa dove li inserisco. Quindi il suo attacco basato sullo schema fisso dei messaggi non funziona più. Il sistema usato nella realtà si chiama Optimal Asymmetric Encryption Padding”.
“Peccato, mi sarebbe piaciuto un Comics and Cartoons Encryption Padding”.
“Eh, vabbé, non si può avere tutto. Ti lascio un esempio reale di codice crittato con RSA. Il messaggio è un testo codificato in questo modo: A = 01, B = 02, …, Z = 26, e lo spazio è uguale a 00”.
“Ok”.
“Vado a capo perché non ci sto:”.
n = 11438162575788886766923577997614661201021829672124236256256184293
5706935245733897830597123563958705058989075147599290026879543541
e = 9007
c = 9686961375462206147714092225435588290575999112457431987469512093
0816298225145708356931476622883989628013391990551829945157815154lunedì 3 maggio 2010
Alice, Bob e Eva — Perché Eva non riesce a decrittare
Chiave pubblica (n,e) = (9017,251),
Messaggio cifrato c = 6543.
Eva vuole decrittare il messaggio senza conoscere la chiave privata. Per prima cosa scompone n:
n = 71·127.
Di conseguenza può calcolare φ(n) = 70·126 = 8820.
Grazie a φ(n) può dare inizio alla procedura per calcolare d, che deve essere tale per cui ed ≡ 1 mod 8820. L'equazione diofantea da risolvere è la seguente:
251d - 8820k = 1.
Si esegue la divisione con resto 8820/251:
8820 = 251·35 + 35.
Si sostituisce 8820 e si raccoglie:
251d - (251·35 + 35)k = 1,
251(d - 35k) - 35k = 1.
Indichiamo con A l'espressione tra parentesi d-35k:
251A - 35k = 1
Ora si può ripetere il procedimento. Si esegue la divisione con resto 251/35:
251 = 35·7 + 6.
Si sostituisce 251 e si raccoglie:
(35·7 + 6)A - 35k = 1,
35(7A - k) + 6A = 1.
Indichiamo con B l'espressione tra parentesi 7A - k, e ricominciamo (anche se si vede già il risultato: B = -1, A = 6).
35B + 6A = 1.
Si esegue la divisione con resto 35/6:
35 = 6·5 + 5.
Si sostituisce 35 e si raccoglie:
(6·5 + 5)B + 6A = 1,
6(5B + A) + 5B = 1.
Indichiamo con C l'espressione tra parentesi 5B + A, e ricominciamo (anche se si vede già il risultato: C = 1, B = -1).
6C + 5B = 1.
Si esegue la divisione con resto 6/5:
6 = 5·1 + 1.
Si sostituisce 6 e si raccoglie:
(5·1 + 1)C + 5B = 1,
5(C + B) + C = 1.
A questo punto C ha coefficiente 1 e tutti (compresi i calcolatori) vedono la soluzione: C + B = 0, C = 1.
Ora si eseguono le sostituzioni all'indietro:
C = 1,
C + B = 0, B = -C, B = -1,
5B + A = C, A = C - 5B, A = 1 + 5, A=6,
7A - k = B, k = 7A - B, k = 42 + 1, k = 43,
d - 35k = A, d = 35k + A, d = 35·43 + 6, d = 1511.
Finalmente è stato trovato d, ora si può decrittare il messaggio:
m ≡ cd mod n = 65431511 mod 9017 = 102.
“Quanti calcoli!”.
“Bè, ma li fanno i calcolatori, mica si fanno a mano”.
“E non è facile per Eva, con calcolatore alla mano, decrittare il messaggio? Perché in questo esempio ci siamo riusciti, mentre nella realtà non ci si riesce?”.
“Ti rispondo con una domanda: hai notato su cosa si basa la ricerca di d?”.
“Sulla definizione di d, suppongo: d è tale per cui ed è congruente a 1 modulo φ(n)”.
“Quindi, dato che e è pubblico, riesci a calcolare il valore di d se conosci φ(n)”.
“Giusto”.
“Supponi allora che esista un metodo veloce per calcolare φ(n) a partire da n. Sapendo che n è il prodotto di due numeri primi p e q (che Eva non conosce), si possono fare i calcoli seguenti:”.
φ(n) = (p - 1)(q - 1) = pq - (p + q) + 1 = n - (p + q) + 1.
“Ok, ma a cosa mi serve?”.
“Ricordati che le incognite sono p e q. Dall'equazione che abbiamo appena scritto possiamo ricavare p + q:”.
p + q = n - φ(n) + 1.
“E quindi?”.
“Dato che già conosciamo il prodotto pq = n, ora siamo in possesso di due dati: la somma di due numeri e il loro prodotto. Un problema che sanno risolvere gli studenti di seconda superiore è proprio quello della ricerca di due numeri conoscendone la somma e il prodotto”.
“Ah, è vero, basta risolvere un'equazione di secondo grado. Se indichiamo con S la somma e con P il prodotto dei due numeri da trovare, l'equazione da risolvere è x2 - Sx + P = 0”.
“Esatto. Quindi potremmo trovare facilmente p e q, cioè potremmo fattorizzare n. Riassumendo: se Eva fosse in grado di calcolare in modo veloce φ(n), allora sarebbe anche in grado di fattorizzare velocemente n. Dato che ad oggi non è noto un metodo veloce per fattorizzare, allora non è noto nemmeno un metodo veloce per trovare φ(n)”.
“Mh, una specie di dimostrazione per assurdo”.
“Sì, una specie, perché non è un teorema. Il fatto che ad oggi non sia noto un metodo per fattorizzare, o per trovare φ(n), non significa che in futuro non lo si possa trovare”.
“O che qualche organizzazione di controspionaggio non lo conosca già, ma lo tenga segreto”.
“Se è così, è un segreto molto ben custodito”.
Messaggio cifrato c = 6543.
Eva vuole decrittare il messaggio senza conoscere la chiave privata. Per prima cosa scompone n:
n = 71·127.
Di conseguenza può calcolare φ(n) = 70·126 = 8820.
Grazie a φ(n) può dare inizio alla procedura per calcolare d, che deve essere tale per cui ed ≡ 1 mod 8820. L'equazione diofantea da risolvere è la seguente:
251d - 8820k = 1.
Si esegue la divisione con resto 8820/251:
8820 = 251·35 + 35.
Si sostituisce 8820 e si raccoglie:
251d - (251·35 + 35)k = 1,
251(d - 35k) - 35k = 1.
Indichiamo con A l'espressione tra parentesi d-35k:
251A - 35k = 1
Ora si può ripetere il procedimento. Si esegue la divisione con resto 251/35:
251 = 35·7 + 6.
Si sostituisce 251 e si raccoglie:
(35·7 + 6)A - 35k = 1,
35(7A - k) + 6A = 1.
Indichiamo con B l'espressione tra parentesi 7A - k, e ricominciamo (anche se si vede già il risultato: B = -1, A = 6).
35B + 6A = 1.
Si esegue la divisione con resto 35/6:
35 = 6·5 + 5.
Si sostituisce 35 e si raccoglie:
(6·5 + 5)B + 6A = 1,
6(5B + A) + 5B = 1.
Indichiamo con C l'espressione tra parentesi 5B + A, e ricominciamo (anche se si vede già il risultato: C = 1, B = -1).
6C + 5B = 1.
Si esegue la divisione con resto 6/5:
6 = 5·1 + 1.
Si sostituisce 6 e si raccoglie:
(5·1 + 1)C + 5B = 1,
5(C + B) + C = 1.
A questo punto C ha coefficiente 1 e tutti (compresi i calcolatori) vedono la soluzione: C + B = 0, C = 1.
Ora si eseguono le sostituzioni all'indietro:
C = 1,
C + B = 0, B = -C, B = -1,
5B + A = C, A = C - 5B, A = 1 + 5, A=6,
7A - k = B, k = 7A - B, k = 42 + 1, k = 43,
d - 35k = A, d = 35k + A, d = 35·43 + 6, d = 1511.
Finalmente è stato trovato d, ora si può decrittare il messaggio:
m ≡ cd mod n = 65431511 mod 9017 = 102.
“Quanti calcoli!”.
“Bè, ma li fanno i calcolatori, mica si fanno a mano”.
“E non è facile per Eva, con calcolatore alla mano, decrittare il messaggio? Perché in questo esempio ci siamo riusciti, mentre nella realtà non ci si riesce?”.
“Ti rispondo con una domanda: hai notato su cosa si basa la ricerca di d?”.
“Sulla definizione di d, suppongo: d è tale per cui ed è congruente a 1 modulo φ(n)”.
“Quindi, dato che e è pubblico, riesci a calcolare il valore di d se conosci φ(n)”.
“Giusto”.
“Supponi allora che esista un metodo veloce per calcolare φ(n) a partire da n. Sapendo che n è il prodotto di due numeri primi p e q (che Eva non conosce), si possono fare i calcoli seguenti:”.
φ(n) = (p - 1)(q - 1) = pq - (p + q) + 1 = n - (p + q) + 1.
“Ok, ma a cosa mi serve?”.
“Ricordati che le incognite sono p e q. Dall'equazione che abbiamo appena scritto possiamo ricavare p + q:”.
p + q = n - φ(n) + 1.
“E quindi?”.
“Dato che già conosciamo il prodotto pq = n, ora siamo in possesso di due dati: la somma di due numeri e il loro prodotto. Un problema che sanno risolvere gli studenti di seconda superiore è proprio quello della ricerca di due numeri conoscendone la somma e il prodotto”.
“Ah, è vero, basta risolvere un'equazione di secondo grado. Se indichiamo con S la somma e con P il prodotto dei due numeri da trovare, l'equazione da risolvere è x2 - Sx + P = 0”.
“Esatto. Quindi potremmo trovare facilmente p e q, cioè potremmo fattorizzare n. Riassumendo: se Eva fosse in grado di calcolare in modo veloce φ(n), allora sarebbe anche in grado di fattorizzare velocemente n. Dato che ad oggi non è noto un metodo veloce per fattorizzare, allora non è noto nemmeno un metodo veloce per trovare φ(n)”.
“Mh, una specie di dimostrazione per assurdo”.
“Sì, una specie, perché non è un teorema. Il fatto che ad oggi non sia noto un metodo per fattorizzare, o per trovare φ(n), non significa che in futuro non lo si possa trovare”.
“O che qualche organizzazione di controspionaggio non lo conosca già, ma lo tenga segreto”.
“Se è così, è un segreto molto ben custodito”.
Iscriviti a:
Post (Atom)