• L'algoritmo RSA

    rsa.jpg

    Presentiamo in questo articolo un primo esempio di algoritmo di crittografia a chiave pubblica: RSA.

    Nel 1978 Ronald Rivest, Adi Shamir e Leonard Adleman, tre giovani professori del MIT, sviluppano la prima applicazione pratica basata sulle tecniche di crittografia a doppia chiave, che prenderà il nome di algoritmo RSA, dalle iniziali dei suoi tre inventori.

    L’idea di RSA è molto semplice e si basa sulla difficoltà di fattorizzare “grandi” numeri (“large numbers”): mentre è molto facile moltiplicare tra di loro due “grandi” numeri primi, risulta difficile fattorizzare il loro prodotto. In questo modo, il prodotto può essere reso pubblico insieme alla chiave di codifica.

    Vediamo ora di presentare l’algoritmo RSA.

    Nota: Le formule matematiche presenti saranno espresse in maniera “estesa”, non potendo essere rappresentate per problemi di formattazione del testo.

    • Si scelgono, in modo casuale, due “grandi” numeri primi p e q;
    • Si calcola n, come prodotto di p e q;
    • Si calcola la funziona di Eulero E di n, ossia il prodotto di (p-1) (q-1);
    • Si sceglie un numero e tale che il massimo comun divisore di ed ed E sia 1. In formula matematica: M.C.D. (e,E) = 1;
    • Si calcola d tale che il prodotto e sia congruo a 1 modulo E.

    I numeri n, e, d vengono solitamente chiamati modulo, esponente di codifica (o pubblico) e esponente di decodifica (o privato).

    La coppia di numeri (n,e) costituiscono la chiave pubblica, mentre d costituisce la chiave privata. I numeri p e q a questo punto possono essere eliminati.

    Va sottolineato comunque che a seconda delle implementazioni dell’algoritmo RSA, la chiave privata può contenere anche altri “elementi”. Quindi è facile trovare in letteratura e nelle varie implementazioni chiavi segrete del tipo (n,d) oppure (p,q, E,d).

    La codifica di un messaggio M nel corrispondente testo cifrato C avviene nel seguente modo:

    C = (M elevato a e) modulo n

    La decodifica invece avviene nel seguente modo:

    (C elevato a D) = M modulo n

    Consideriamo ora un esempio di come generare le chiavi pubbliche e private. Per semplicità, utilizzeremo dei numeri primi piccoli.

    • Siano p = 5, q = 7;
    • Quindi, n = p q = 35, E = 4 * 6 = 24;
    • Si calcola e in modo tale che: M.C.D. (e, E) = 1. Allora e = 7. La nostra chiave pubblica è la coppia (n,e) = (35,7);
    • Si calcola d in modo tale che d sia congruoa (e-1 mod E). Quindi la nostra chiave privata sarà d = 7.

    Supponiamo, sempre per semplicità di calcolo, di dover cifrare il nostro messaggio M = 3. Quindi il nostro testo cifrato sarà C = (3 elevato alla 7) modulo 35 = 17

    Per decifrare il messaggio, dovrò calcolare (17 elevato a 7) modulo 35, riottenendo M = 3.

    Nel corso degli anni, di fatto l’algoritmo RSA ha più volte dimostrato la sua robustezza: di fatto,ancora oggi, a distanza di 30 anni dalla sua nascita, RSA costituisce uno dei sistemi di crittografia più utilizzati, in particolare nella firma digitale.

    Tags:

    Se vuoi aggiornamenti su L'algoritmo RSA inserisci la tua e-mail nel box qui sotto:


    Ho letto e acconsento l'informativa sulla privacy

    Si No

    Acconsento al trattamento dei dati personali di cui al punto 3 dell'informativa sulla privacy

    Si No

    Commenti

    1. realtebo dice:

      potresti approfondire ulteriormente questo algoritmo, magari con un esempio più ‘passo passo’, compresa la codifica e la decodifica.

      qualcosa continua a sfuggirmi…

    2. realtebo dice:

      piccolo errore di stampa: “il massimo comun divisore di ed ed E”

      forse sono ‘e ed E’

    3. Fabrizio dice:

      @realtebo: vedrò nelle prossime settimane se riesco ad approfondire l’argomento con qualche esempio che possa aiutare nella comprensione dell’algoritmo.

      Grazie per il commento: fa molto piacere sapere che certi argomenti destano interesse ;)

    4. realtebo dice:

      non ho mai scritto ma vi leggo da molto, continuate così

    5. ettoriiiino dice:

      grazie per il vostro suggerimento…il prof di info m’ha messo 8 :D:D

    Commenta

    Your email address will not be published. Required fields are marked *