🦖 🖼️ 👂🏾 Les accidents ne sont pas aléatoires: qui sont les familles de fonctions pseudo-aléatoires (PRF) 🤸🏻 🧘 🛌🏽

En 1984, Goldreich, Goldwasser et Micali ont formalisé le concept de fonctions pseudo-aléatoires et proposé une implémentation PRF basée sur un générateur pseudo-aléatoire (PRG) doublant la longueur. Depuis lors, les fonctions pseudo-aléatoires se sont avérées être une abstraction extrêmement importante qui a trouvé des applications dans divers domaines, tels que l'authentification de message et la démonstration de théorèmes. Dans cet article, je couvrirai:

Que sont les fonctions aléatoires (RF)
Que sont les fonctions pseudo-aléatoires (PRF)
Qui sont ces familles?
PRF vs. PRG
Qu'est-ce que les chiffrements par blocs ont à voir avec cela?

Aléatoire

Déjà à partir du nom, il devient clair qu'une fonction pseudo-aléatoire est quelque chose qui "ressemble" à une fonction aléatoire. Eh bien, qu'est-ce qu'une fonction aléatoire dans notre cas? Pour commencer, nous limiterons notre champ de considération aux fonctions affichant une chaîne de zéros et de uns avec une longueur d' une chaîne de zéros et de uns de même longueur , c'est-à-dire

$\ underbrace {1110 ... 0010} _ {n} \ rightarrow \ underbrace {0100 ... 0011} _ {n} \ Leftrightarrow \ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n$

Ceci, d'une manière générale, peut être omis, et nous pouvons envisager des mappages de chaînes d'une longueur à des chaînes d'une autre longueur, mais dans ce cas, il faudra faire attention aux différences de dimensions. Ensuite, nous introduisons l'ensemble de toutes les fonctions qui effectuent le mappage $\ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n$ et le dénotons $\ text {Func} _n$ .

Considérez la cardinalité de cet ensemble. C'est évident que $| {\ text {Func} _n} | = 2 ^ {n2 ^ n}$ .

$\ text {Nombre total de chaînes distinctes de longueur} n \ espace - \ espace 2 ^ n.$ $\ text {Pour stocker} 2 ^ n \ text {lignes dont vous avez besoin} n2 ^ n \ text {bits.}$ $\ text {Ces} n2 ^ {n} \ text {bits et définiront le mappage souhaité} 2 ^ n \ text {lignes.}$ $\ text {Et il y aura un total de ces mappages} 2 ^ {n2 ^ n}.$

. – $\ text {Func} _n$ . , 2 ^ n - 2 ^ n . ,