Short PlainText Attack

• tipo di attacco che capita in due casi principlamente
  1. Quando si divide il testo in blocchi, l’ultimo blocco può essere piu piccolo degli altri
  2. quando vengono utilizzate password troppo corte
• Si supponga che si voglia utilizzare una password di 7 caratteri, l’attacco richiederebbe circa $10^{17}$ computazioni
• Conosco il crittotesto $C,n,e$ e quindi posso fare i seguenti conti con $x,y$ casuali

$$ C*x^{-e} \text{ mod } n\\ per\\ x=1\\ x=2\\ x=3\\ ... $$

$$ y^{e} \text{ mod } n\\ per\\ y=1\\ y=2\\ y=3\\ ... $$

• finchè non trovo $x,y$ che danno lo stesso valore da entrambe le colonne, mettiamo per esempio 4, allora facciamo una uguaglianza e otteniamo che:

  $$ Cx^{-e}=4=y^e\text{ mod } n\\ Cx^{-e}=y^e\\ \frac C {x^e} =y^e\\ C=x^ey^e=(xy)^e\\ C=(x*y)^e\text{ mod }n $$

• dove $x*y$ corrisponde al messaggio m perchè

  <aside> 💡 $m^e=C$

  </aside>

• Come si risolve questo problema? Tramite Optimal Asimmetric Encryption Padding ovvero un padding che si aggiunge al’ultimo blocco per evitare che sia troppo piccolo e quindi facilmente attaccabile

Primality Testing

Algoritmo di Fermat

Si considerino

$$ n, x, y \text{ tali che }\\ x^2\equiv y^2 \text{ mod } n\\ allora\\ n \neq \pm y \rarr \text{ n è composto } $$

• in particolar modo

<aside> 💡 $M CD(x − y; n) \text{ fornisce un fattore di n}$

</aside>

• si consideri ora

$$ n\text{ un intero arbitrariamente grande}\\ \text{ ed }\pm a< n-1\\ \text{ se }\\ a^{n-1}\neq d\text{ mod }n\\ \text{ovvero}\\ a^{n-1}\neq1\text{ mod }n\\ \text{ per il piccolo teorema di fermat possiamo dire che n è composto} $$

• se la condizione non si verifica invece non possiamo concludere assolutamente nulla
• questo algoritmo è utile e buono solo per verificare che un numero sia composto