Poly1305

Poly1305 és una família de hash universal dissenyada per Daniel J. Bernstein per utilitzar-la en criptografia.^[1]

Com amb qualsevol família de hash universal, Poly1305 es pot utilitzar com a codi d'autenticació de missatges d'una sola vegada per autenticar un missatge únic mitjançant una clau secreta compartida entre remitent i destinatari, ^[2] de manera similar a com es pot utilitzar un bloc d'un sol ús. per ocultar el contingut d'un sol missatge mitjançant una clau secreta compartida entre remitent i destinatari.

Originalment, Poly1305 es va proposar com a part de Poly1305-AES, un autenticador Carter – Wegman ^[3][4][5] que combina el hash Poly1305 amb AES-128 per autenticar molts missatges mitjançant una única clau curta i números de missatge diferents. Poly1305 es va aplicar posteriorment amb una clau d'un sol ús generada per a cada missatge mitjançant XSalsa20 al xifratge autenticat NaCl crypto_secretbox_xsalsa20poly1305, i després utilitzant ChaCha al xifratge autenticat ChaCha20-Poly1305 ^[5] desplegat en TLS. l'internet.

Poly1305 pren una clau secreta de 16 bytes ${\displaystyle r}$ i un ${\displaystyle L}$ missatge -byte ${\displaystyle m}$ i retorna un hash de 16 bytes ${\displaystyle \operatorname {Poly1305} _{r}(m)}$. Per fer-ho, Poly1305: ^[6]

1. Interpreta com un nombre enter de 16 bytes little-endian.
2. Trenca el missatge en fragments consecutius de 16 bytes.
3. Interpreta els fragments de 16 bytes com a nombres enters little-endians de 17 bytes afegint un 1 byte a cada fragment de 16 bytes, per utilitzar-los com a coeficients d'un polinomi.
4. Avalua el polinomi en el punt mòdul el primer.
5. Redueix el mòdul del resultat codificat en little-endian retorna un hash de 16 bytes.

Els coeficients ${\displaystyle c_{i}}$ del polinomi ${\displaystyle c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r}$, on ${\displaystyle q=\lceil L/16\rceil }$, són:$${\displaystyle c_{i}=m[16i-16]+2^{8}m[16i-15]+2^{16}m[16i-14]+\cdots +2^{120}m[16i-1]+2^{128},}$$amb l'excepció que, si ${\displaystyle L\not \equiv 0{\pmod {16}}}$, llavors:

$${\displaystyle c_{q}=m[16q-16]+2^{8}m[16q-15]+\cdots +2^{8(L{\bmod {1}}6)-8}m[L-1]+2^{8(L{\bmod {1}}6)}.}$$

La clau secreta ${\displaystyle r=(r[0],r[1],r[2],\dotsc ,r[15])}$ està restringit a tenir els bytes ${\displaystyle r[3],r[7],r[11],r[15]\in \{0,1,2,\dotsc ,15\}}$, és a dir, tenir els seus quatre bits principals clars; i tenir els bytes ${\displaystyle r[4],r[8],r[12]\in \{0,4,8,\dotsc ,252\}}$, és a dir, per tenir els seus dos bits inferiors clars. Així n'hi ha ${\displaystyle 2^{106}}$ diferents valors possibles de ${\displaystyle r}$.

La seguretat de Poly1305 i els seus derivats contra la falsificació es deu a la seva probabilitat de diferència limitada com a família hash universal : si ${\displaystyle m_{1}}$ i ${\displaystyle m_{2}}$ són missatges de fins a ${\displaystyle L}$ bytes cadascun, i ${\displaystyle d}$ és qualsevol cadena de 16 bytes interpretada com un nombre enter little-endian, doncs$${\displaystyle \Pr[\operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2})\equiv d{\pmod {2^{128}}}]\leq {\frac {8\lceil L/16\rceil }{2^{106}}},}$$on ${\displaystyle r}$ és una clau aleatòria Poly1305 uniforme.  : Teorema 3.3, pàg. 8 

Aquesta propietat de vegades s'anomena ${\displaystyle \epsilon }$ -quasi-Δ-universalitat acabada ${\displaystyle \mathbb {Z} /2^{128}\mathbb {Z} }$, o ${\displaystyle \epsilon }$ -AΔU, on ${\displaystyle \epsilon =8\lceil L/16\rceil /2^{106}}$ en aquest cas.