title: Optimal Asymmetric Encryption Padding
text: # Optimal Asymmetric Encryption Padding
  
  In crittografia, Optimal Asymmetric Encryption Padding (OAEP) è uno schema di padding spesso utilizzato assieme a RSA. OAEP è stato introdotto da Bellare e Rogaway, e successivamente standardizzato in PKCS #1 v2 e RFC 2437.
  
  L'algoritmo OAEP è una sorta di rete di Feistel che utilizza coppie di oracoli random $G$ e $H$ per effettuare un preprocessing su un messaggio da cifrare asimmetricamente. Se usato in combinazione con una funzione botola sicura, questo metodo è considerato semanticamente sicuro all'interno del modello a oracolo random contro attacchi di tipo chosen plaintext. In casi particolari (ad esempio, con RSA), OAEP è stato provato essere sicuro anche contro attacchi di tipo chosen ciphertext. OAEP può essere utilizzato per costruire una trasformazione all-or-nothing ("tutto o niente"), come spiegato in seguito.
  
  OAEP soddisfa i due obiettivi seguenti:
  
  * Aggiunge una componente di casualità che può essere usata per convertire uno schema di crittazione deterministico (come RSA) in uno probabilistico.
  * Fa in modo che un possibile avversario non possa recuperare alcuna porzione del testo in chiaro, anche se fosse in grado di invertire la funzione botola su cui si basa l'algoritmo di crittazione.
  
  ## Funzionamento
  
  Nel diagramma a destra:
  
  * $n$ è il numero di bit nel modulo RSA.
  * $k_{0}$ e $k_{1}$ sono costanti intere fissate nel protocollo.
  * $m$ è il messaggio in chiaro, una stringa lunga $n-k_{0}-k_{1}$ bit
  * $G$ e $H$ sono due funzioni crittografiche di hash fissate nel protocollo.
  * ⊕ è l'operatore XOR.
  
  Per cifrare:
  
  * al messaggio m va applicato un padding di $k_{1}$ zeri per arrivare ad una lunghezza di $n-k_{0}$ bit.
  * $r$ è una stringa casualmente generata lunga $k_{0}$ bit.
  * $G$ espande i $k_{0}$ bit di $r$ a $n-k_{0}$ bit.
  * $X=m00..0\oplus G(r)$
  * $H$ riduce gli $n-k_{0}$ bit di $X$ a $k_{0}$ bit.
  * $Y=r\oplus H(X)$
  * L'output è $X\|Y$, ovvero la concatenazione di $X$ e $Y$.
  
  Per decifrare:
  
  * recuperare $r$ calcolando $Y\oplus H(X)$;
  * recuperare il messaggio $m$ tramite $m00..0=X\oplus G(r)$.
  
  La proprietà all-or-nothing deriva dal fatto che per recuperare il messaggio $m$ si ha bisogno delle intere stringhe $X$ e $Y$. $X$ è richiesto per ottenere $r$ da $Y$, e $r$ è richiesta per ottenere $m$ da $X$. Dato anche una piccolissima modifica all'input di una funzione crittografica di hash cambia completamente il risultato, $X$ e $Y$ devono essere interamente ottenute. Questo garantisce l'integrità del messaggio.
  
  