{"id":2014,"date":"-0001-11-30T00:00:00","date_gmt":"-0001-11-29T23:10:04","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"2014","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/2014\/","title":{"rendered":"Perch\u00e9 i numeri primi sono intimamente connessi con i metodi di puntamento (dalle testine dei cd-rom ai radar) e con la crittografia?"},"content":{"rendered":"

Breve storia della
\n crittografa<\/b><\/font><\/p>\n

Il problema di
\n codificare o cifrare<\/i> un messaggio \u00e8 stato
\n affrontato, generalmente per usi militari, attraverso
\n tutta la storia della civilt\u00e0 umana. <\/font><\/p>\n

Plutarco descrive la scitala
\n lacedemonica <\/i>come un codice di cifratura in uso dai
\n tempi di Licurgo (IX sec a.C.), circa tremila anni fa. Si
\n trattava di un dispositivo di cifratura costituito da un
\n bastone e da un nastro di cuoio avvolto a spirale
\n cilindrica, su cui il messaggio veniva scritto per
\n colonne. Sul nastro srotolato le lettere risultavano
\n trasposte in modo tale che solo l\u2019adozione di un
\n bastone identico a quello originariamente usato per la
\n scrittura del messaggio consentiva di ricomporre il
\n testo. <\/font><\/p>\n

Il primo trattato di
\n crittografia risale al 400 a.C. circa, ad opera del
\n generale arcadico Enea il Tattico, in cui vengono
\n descritti prevalentemente sistemi di meccanici di
\n cifratura analoghi alla scitala lacedemonica.<\/font><\/p>\n

Con la civilt\u00e0 dei
\n Greci e l\u2019Impero Romano, la cifratura di un
\n messaggio avveniva per semplice sostituzione o
\n traslitterazione. I codici di Cesare e di Augusto erano
\n infatti basati proprio su questa tecnica, adottando
\n l\u2019alfabeto romano. Il codice di Atbash, basato
\n sull\u2019alfabeto ebraico, era una versione ancor pi\u00f9
\n semplificata di codice per sostituzione: la prima lettera
\n dell\u2019alfabeto veniva scambiata con l\u2019ultima, la
\n seconda con la penultima e cos\u00ec via. Polibio con la sua scacchiera<\/i>,
\n ide\u00f2 un metodo per sostituire lettere a coppie di
\n numeri. La scacchiera di Polibio era costruita inserendo
\n le lettere dell\u2019alfabeto in una matrice rettangolare
\n e sostituendo nel messaggio la riga e la colonna
\n corrispondente ad ogni lettera. <\/font><\/p>\n

\"\"\/<\/p>\n

Fig.1 Esempio di
\n scacchiera di Polibio<\/font><\/p>\n

\u00a0<\/p>\n

La figura 1 \u00e8 stata
\n costruita utilizzando il metodo proposto da Polibio. Ad
\n esempio, il termine \"\"\/ <\/i>(amore<\/i>) viene
\n codificato sostituendo il numero di riga e colonna per
\n ogni lettera che lo compone, come in figura 2.<\/font><\/p>\n

\"\"\/ <\/i><\/font>= 1113113421<\/b><\/p>\n

Fig.2 Esempio di
\n codifica di Polibio<\/font><\/p>\n

\u00a0<\/p>\n

A dispetto
\n dell\u2019apparente semplicit\u00e0 della codifica di
\n Polibio, tale metodo suggeriva una interessante soluzione
\n al problema della trasmissione <\/i>del messaggio: una
\n frase poteva venire trasmessa a distanza, infatti,
\n mediante segnali luminosi. <\/font><\/p>\n

Attraverso tutto il
\n medioevo poi, la crittografia veniva utilizzata per scopi
\n militari o diplomatici con varianti del metodo della
\n sostituzione, utilizzando per lo pi\u00f9 abbreviazioni, o nomenclature<\/i>,
\n di nomi, luoghi.<\/font><\/p>\n

Dal XVI secolo, i codici
\n del Della Porta, Bellasio, Alberti e Vigenere
\n introducono, pur se con metodologie diverse, il concetto
\n di chiave, talvolta definita verme letterale<\/i>, per
\n il controllo del processo di cifratura. L\u2019idea \u00e8 di
\n utilizzare una sequenza di caratteri dedicata al fornire
\n informazioni necessarie e sufficienti, unita ad un
\n metodo, senza la quale sarebbe impossibile riottenere il
\n messaggio originale. Ad esempio, l\u2019Alberti
\n utilizzava delle lettere di controllo inserite nel testo
\n cifrato per determinare quale lista di lettere utilizzare
\n per la cifratura locale del brano; Della Porta e Bellasio
\n utilizzano la chiave come strumento di generazione del
\n messaggio codificato; Vigenere unisce il metodo di
\n sostituzione al concetto di chiave, utilizzando una
\n matrice quadrata di sostituzione e la chiave come
\n strumento di selezione della riga da utilizzare.<\/font><\/p>\n

Thomas Jefferson,
\n presidente degli Stati Uniti ed autore della
\n dichiarazione di Indipendenza ide\u00f2 un codice di
\n cifratura meccanico, mediante un cilindro costituito da
\n 36 dischi con le 26 lettere dell\u2019alfabeto in ordine
\n sparso. Il codice \u00e8 considerato ancor oggi sicuro.<\/font><\/p>\n

Ma \u00e8 con l\u2019avvento
\n del XX secolo, della guerra e, quindi, dei calcolatori
\n che la vita dei ideatori di codici si \u00e8 fatta pi\u00f9
\n complessa. Tutti i sistemi ideati fino ad allora avevano
\n l\u2019inconveniente di essere obsoleti non appena il
\n metodo di decifrazione, meccanico o cartaceo che sia,
\n fosse reso pubblico. Ottenuto il bastone originale nella
\n scitala lacedemonica o il cilindro di Jefferson chiunque
\n sarebbe in grado di procedere alla decodifica.<\/font><\/p>\n

Alan Turing, matematico
\n e padre de facto<\/i> dell\u2019informatica, \u00e8 stato
\n al centro di epiche vicende di decrittazione, a colpi di
\n macchine calcolatrici sempre pi\u00f9 potenti ed algoritmi
\n sempre pi\u00f9 efficaci che hanno costellato la storia della
\n crittografia dalla seconda guerra mondiale in poi.<\/font><\/p>\n

La vera sfida del
\n ventesimo secolo era, quindi, l\u2019ideazione di un
\n codice per cui anche il pi\u00f9 potente dei calcolatori
\n impiegasse millenni per la decodifica. Il problema era,
\n infatti, che i metodi ideati non erano in grado di
\n resistere ad una analisi esaustiva<\/i> di un
\n calcolatore sufficientemente potente da tentare tutte le
\n combinazioni possibili. <\/font><\/p>\n

Nel 1975 IBM ha
\n introdotto il Data Encryption System<\/i>, o DES, un
\n codice a chiave basato su una sequenza di sostituzioni e
\n trasposizioni operate in base ad una chiave di 64 bit.
\n Tale metodo fu al centro di un\u2019aspra ed accesa
\n polemica perch\u00e9 il numero di chiavi distinte a 64 bit \u00e8
\n pari a 264<\/sup>, ulteriormente ridotto a 256 <\/sup>considerando
\n che 8 bit della chiave sono destinati al controllo: un
\n numero di combinazioni alla portata di molti computer
\n moderni.<\/font><\/p>\n

Il DES differisce dagli
\n altri metodi per il fatto di non dover essere mantenuto
\n segreto, il fatto che venga reso pubblico non garantisce
\n affatto la possibilit\u00e0 di decodificare i messaggi.
\n All\u2019IBM va riconosciuto, infatti, di aver ideato un
\n algoritmo sufficientemente complesso e caratterizzato da
\n importanti vantaggi quali:<\/font><\/p>\n

    \n
  1. E\u2019 di dominio
    \n pubblico<\/font><\/li>\n
  2. La decodifica \u00e8
    \n interamente legata alla chiave<\/font><\/li>\n
  3. E\u2019
    \n sufficientemente resistente ad un attacco
    \n esaustivo mediante calcolatore<\/font><\/li>\n<\/ol>\n

    La crittografia a
    \n chiave pubblica secondo Rivest, Shamir ed Adlemann<\/b><\/font><\/p>\n

    Nel 1978, R. Rivest, A.
    \n Shamir, L. Adleman, pubblicarono l\u2019articolo “A
    \n Method for Obtaining Digital Signatures and Public-key
    \n Cryptosystems<\/i>“, destinato dare una soluzione al
    \n problema in grado di resistere alla potenza dei
    \n calcolatori per parecchi anni a venire. Il metodo di
    \n cifratura venne codificato in un algoritmo che prese il
    \n nome dalle iniziali dei tre matematici: algoritmo RSA<\/b>.<\/font><\/p>\n

    Gli algoritmi di
    \n crittografia a chiave pubblica<\/i>, come RSA, sono
    \n caratterizzati da una coppia di chiavi dette pubblica<\/i>
    \n e privata<\/i>. La chiave pubblica va distribuita ai
    \n destinatari dei messaggi e la chiave privata va mantenuta
    \n segreta dal mittente. Con la chiave privata vengono
    \n decodificati solo i messaggi codificati da chi possiede
    \n la chiave pubblica corrispondente. Le chiavi sono
    \n generate in modo tale che non sia possibile calcolare la
    \n chiave privata a partire da quella pubblica.<\/font><\/p>\n

    Supponiamo che due
    \n persone, A e B, debbano scambiarsi un messaggio:<\/font><\/p>\n

      \n
    1. B genera due
      \n chiavi, una pubblica e l\u2019altra privata<\/font><\/li>\n
    2. B mantiene la
      \n chiave privata per se e comunica a A la chiave
      \n pubblica<\/font><\/li>\n
    3. A codifica il
      \n messaggio con la chiave pubblica di B e lo invia<\/font><\/li>\n
    4. B riceve il
      \n messaggio da A, e lo decodifica con la propria
      \n chiave privata<\/font><\/li>\n<\/ol>\n

      Prima di descrivere
      \n l\u2019algoritmo RSA \u00e8 necessario un richiamo
      \n sull\u2019Aritmetica Modulare.<\/font><\/p>\n

      Supponiamo di avere a
      \n disposizione solo n <\/i>cifre, diciamo 12, e di
      \n disporle come in un quadrante di orologio. Applichiamo i
      \n concetti di addizione e moltiplicazione usuali, salvo
      \n che, al superare il 11, ricominciamo a contare
      \n circolarmente da 0.<\/font><\/p>\n

      Nell\u2019aritmetica
      \n usuale l\u2019addizione<\/font><\/p>\n

      7 + 8 =
      \n 15<\/font><\/p>\n

      diviene,
      \n nell\u2019aritmetica modulo 12<\/font><\/p>\n

      7 + 8 = 3
      \n (mod 12)<\/font><\/p>\n

      ci si convince
      \n facilmente di ci\u00f2 osservando il proprio orologio ed
      \n assegnando le cifre come da fig. 3<\/font><\/p>\n

      \"\"\/<\/p>\n

      Fig. 3 Aritmetica modulo
      \n 12 sul quadrante di un orologio<\/font><\/p>\n

      \u00a0<\/p>\n

      Cos\u00ec aggiungendo 8 al
      \n 7, si arriva al 3. <\/font><\/p>\n

      Nell\u2019aritmetica
      \n modulo n<\/i> la moltiplicazione \u00e8 definita in modo
      \n analogo all\u2019aritmetica ordinaria come:<\/font><\/p>\n

      a*b (mod
      \n n) = a+a+a+\u2026<b volte>…+a (mod) n<\/font><\/p>\n

      e lo stesso vale per la
      \n potenza<\/font><\/p>\n

      ab<\/sup>
      \n (mod n) = a* <\u2026b volte \u2026>* a (mod n)<\/font><\/p>\n

      \u00a0<\/p>\n

      L\u2019algoritmo RSA \u00e8
      \n quindi definito come segue:<\/font><\/p>\n

      Generazione delle
      \n chiavi pubbliche e private<\/b><\/font><\/p>\n

        \n
      1. Siano p <\/i>e q
        \n <\/i>due numeri primi molto grandi<\/font><\/li>\n
      2. sia m =
        \n (p-1)(q-1)<\/i><\/font><\/li>\n
      3. sia n = pq<\/i><\/font><\/li>\n
      4. si trovi un numero d<\/i>
        \n non necessariamente grande, relativamente primo
        \n ad n<\/i><\/font><\/li>\n
      5. si trovi e<\/i>
        \n tale che de = 1 (mod m)<\/i><\/font><\/li>\n
      6. la chiave pubblica
        \n \u00e8 la coppia (d,n)<\/i><\/font><\/li>\n
      7. la chiave privata
        \n \u00e8 la coppia (e,n)<\/i><\/font><\/li>\n<\/ol>\n

        Codifica di un
        \n messaggio M<\/b><\/font><\/p>\n

        Il messaggio codificato
        \n \u00e8 C(M) = M<\/i>d<\/i><\/sup> (mod n)<\/i><\/font><\/p>\n

        Decodifica di un
        \n messaggio C<\/b><\/font><\/p>\n

        Il messaggio
        \n decodificato \u00e8 M (C) =C<\/i>e<\/i><\/sup>
        \n (mod n)<\/i><\/font><\/p>\n

        Pur conoscendo il
        \n meccanismo di codifica, la decodifica di un messaggio
        \n senza conoscere la chiave privata e<\/i> \u00e8 un
        \n operazione per cui anche il pi\u00f9 potente dei calcolatori
        \n impiegherebbe secoli, riconducendo a noti problemi
        \n intrattabili nella scienza dei calcolatori, infatti:<\/font><\/p>\n

          \n
        1. Ignorando la chiave
          \n pubblica bisognerebbe calcolare la radice di
          \n ordine d<\/i> , in aritmetica modulo n<\/i>
          \n di M<\/i>. Problema intrattabile.<\/font><\/li>\n
        2. Anche conoscendo la
          \n chiave pubblica d<\/i>, il calcolo di e<\/i>
          \n implicherebbe la necessit\u00e0 di trovare i numeri
          \n primi p <\/i>e q<\/i> che, se scelti
          \n nell\u2019ordine di 10200<\/sup>, producono
          \n di nuovo un problema intrattabile.<\/font><\/li>\n<\/ol>\n

          Si noti che un algoritmo
          \n come RSA pu\u00f2 difficilmente divenire obsoleto perch\u00e9
          \n riconduce a problemi la cui tecnica di soluzione \u00e8 nota,
          \n ma coinvolge necessariamente un tempo di calcolo enorme,
          \n allo stato attuale della ricerca. <\/font><\/p>\n","protected":false},"excerpt":{"rendered":"

          […]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"class_list":["post-2014","post","type-post","status-publish","format-standard","hentry","category-domande-varie-informatica-e-telecomunicazioni"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2014","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=2014"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2014\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=2014"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=2014"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=2014"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}