Crittografia asimmetrica

di

Chiave pubblica e chiave privata

  1. X genera una chiave pubblica PK e una chiave privata SK
  2. X rende nota la chiave pubblica a chiunque voglia comunicare con lui
  3. Y scrive il messaggio m, lo cifra tramite la chiave pubblica di X e lo spedisce a X
  4. X riceve il messaggio cifrato c, lo decifra tramite la chiave privata e ottiene m

Osserva

  • Se Z conosce la chiave pubblica PK e intercetta c non può ottenere m perché non conosce la chiave privata SK.
  • Se Z vuole scoprire la chiave privata SK deve risolvere un problema numerico noto ma difficilissimo

RSA

  • Rivest Shamir Adleman
  • il nome è l’acronimo dei cognomi di tre ricercatori del MIT
    • Ronald Rivest
    • Adi Shamir
    • Leonard Adleman
  • presentato nel 1978
  • brevettato nel 1983
  • scaduto nel 2000
  • per forzarlo è necessario fattorizzare un numero enorme come prodotto di due numeri primi
  • oggi viene considerato sicuro (non fattorizzabile) un numero che in base 10 ha almeno 300 cifre, quindi una chiave di 1024 bit e oltre

Generazione delle chiavi

Scelgo due numeri primi a caso (grandi a piacere…)

  • p = 3
  • q = 11

Calcolo

  • (p-1)(q-1)
     2*10 = 20
  • n = p*q
    3*11 = 33

Scelgo

  • e = 7 tale che
    • e < n
    • coprimo con (p-1)(q-1)
  • d = 3 tale che
    • e*d mod (p-1)(q-1) = 1
      3*7 mod 20 = 21 mod 20 = 1

Ottengo

  • PK = (n,e) = (33, 7), chiave pubblica
  • SK = (n,d) = (33, 3), chiave privata

CODIFICA

Sia m = 15 il messaggio in chiaro.

Calcolo: c = me (mod n)

  • 157 (mod 33) = 27
e lo spedisco

DECODIFCA

Ricevo il messaggio cifrato c = 27.

Calcolo: m = cd (mod n)

  • 273 (mod 33) = 15
e ottengo il messaggio in chiaro!

DSA

  • Digital Signature Algorithm
  • Un’alternativa alla difficoltà dell’operazione di fattorizzazione
  • Utilizza il logaritmo discreto

RISORSE ONLINE