• differisce dalla crittografia simmetrica in quanto entrano in gioco ulteriori chiavi, ovvero quelle private
• le chiavi che entrano in gioco nei processi di cifratura e decifratura sono quindi differenti

RSA e Fattorizzazione

• Si considerino due numeri p e q primi molto grandi:

  • Dati p e q, svolgere $p*q=n$ è possibile, neanche tanto difficile
  • Dato invece n, svolgere $p*q=n$ diventa davvero difficile

  <aside> 👉 Questo si chiama di fatto problema della fattorizzazione

  </aside>

• RSA quindi fa utilizzo di una espressione con esponsnti.

Funzionamento

• Il Plaintext M, viene cifrato in blocchi, ogni blocco deve avere un valore binario minore di un numero n.
• Se chiamiamo $i$ la dimensione del blocco:

$$ i \le log_2(n)\\ \equiv\\ 2^i< n \le 2^{i^1} $$

• Encryption e Decryption sono nella seguente forma, dato un plaintext $M$ ed un crittotesto $C$

$$ C = M^e\text{ mod }n \\ M = C^d\text{ mod }n = M^{ed}\text{ mod }n $$

• Essendo un algoritmo a chiave pubblica e privata, una delle caratteristiche piu importanti è la seguente:

  <aside> 💡 è possibile trovare valori di $e,d,n$ tali che $M=M^{ed}\text{ mod }n$

  </aside>

  • necessitiamo quindi di trovare una relazione del tipo $M=M^{ed}\text{ mod }n$

  • questa relazione funziona solamente se $e$ e $d$ sono inversi moltiplicativi modulo $\phi(n)$

  • come visto nella lezione prima, per $p$ e $q$ primi abbiamo che

    $$ \phi(n)=\phi(p*q)=(p-1)(q-1)\\ \text{e quindi la relazione tra p e q deve essere di tipo }\\ ed\text{ mod }\phi(n)=1\\ \equiv\\ ed\equiv1\text{ mod }\phi(n) \\ \equiv\\ d\equiv e^{-1}\text{ mod }\phi(n) $$

• le componenti di RSA sono quindi

  1. $p,q$ : due numeri primi molto grandi —> Privati, Scelti
  2. $n =p*q$ : —> Pubblico, Calcolato
  3. $e \text{ tale che MCD(}\phi(n),e)\text =1$ —> Pubblico, Scelto
  4. $d\equiv e^{-1}(mod(\phi(n))$ —> Privato, Calcolato

<aside> 💡 Si parla quindi di una cifratura asimmetrica a chiave pubblica e privata con $PU=\text{Chiave Pubblica = }\lbrace e,n\rbrace$ $PR=\text{Chiave Privata= }\lbrace d,n\rbrace$

</aside>

• CHI INVIA $\rarr$ deve conoscere $e$
• CHI RICEVE $\rarr$ deve conoscere $d$
• ENTRAMBI $\rarr$ CONOSCONO n

Encryption e Decryption

• per cifrare e decifrare il messaggio ci avvaliamo della seguente relazione, vista prima

  $$

  C = M^e\text{ mod }n\\ M = C^d\text{ mod }n $$

• Esempio:

  • Come prima cosa, generiamo le chiavi pubblica e privata:

    • Si Scelgono due numeri primi $p=17\text{ e } q=11$
    • Si calcola n e si ottiene che $n=p*q=187$
    • calcoliamo $\phi(n)=(p-1)(q-1)=16*10=160$
    • Scegliamo un valore $e \text{ tale che MCD(}\phi(n),e)\text =1$ ovvero che sia relativamente primo a $\phi(n)$ e minore di $\phi(n)$, in questo caso $e=7$
    • di calcola d tale che $de\equiv 1\text{ mod }(\phi(n))\text{ e d<}\phi(n)$. In questo caso va benissimo $d=23$.
      • d può essere calcolato tranquillamente usando il teorema di euclide esteso
    • ora si hanno chiave pubblica e privata:
      • $PU=\lbrace 7,187 \rbrace$
      • $PR=\lbrace 23,187 \rbrace$

  • Ora, dato in input M=88 si può procedere a CIFRARE:

    $$ C = M^e\text{ mod }n\\ C=88^7\text{ mod }187\\ \text{ grazie all'aritmetica modulare abbiamo che} \\ C=88^7\text{ mod }187=11\\ $$

  • Ora, dato in input C=11 è possibile DECIFRARE

    $$ M = C^d\text{ mod }n\\ M=11^{23}\text{ mod }187\\ \text{ grazie all'aritmetica modulare abbiamo che} \\ C=11^{23}\text{ mod }187=88\\ $$

    • ragionando con l’inverso moltiplicativo, è possibile decifrare utilizzando il piccolo teorema di fermat:

      $$ \text{noi sappiamo che }\\ de\equiv 1\text{ mod }\phi(n)\\ \text{ed anche che }\\ C^d=(M^{e})^d=M^{ed}\\ \text{quindi }\\ C^d\equiv M^{1+k\text{ mod }\phi(n)}\\ \equiv\\ C^d\equiv M(M^{\phi(n)})^k \equiv\\ C^d\equiv M*(1)^k \text{ mod }n $$

• Di seguito un riassunto del funzionamento di RSA: