Vés al contingut

Funció parany

De la Viquipèdia, l'enciclopèdia lliure
La idea de la funció de la trampa. Un algorisme Gen . f es pot calcular de manera eficient, és a dir, en temps polinomi probabilístic. Tanmateix, el càlcul de la inversa de f és generalment difícil, tret que es doni la trampa t .

Una funció parany és una funció matemàtica el càlcul directe de la qual és senzill, però en la qual el càlcul de la funció inversa és molt complex; és a dir, involucra un elevat nombre d'operacions, per exemple, exponencial. Són especialment utilitzades en criptografia.[1]

A títol d'exemple, es pot considerar el producte de nombres primers: [2]

(p, q) &*rarr; m = p. q

L'operació anterior és molt ràpida, però l'operació inversa, és a dir, donat m trobar p i q, és, en general, de complexitat exponencial en la longitud de m. Per exemple, si m té 100 xifres, el nombre mitjà d'operacions requerides per a factorizar m seria 1050 operacions, de forma que un ordinador que faci 1 milió d'operacions per segon trigaria més de 1036 anys. En aquest cas, m seria utilitzat com a clau pública, mentre que els nombres primers (p,q) serien la clau privada.[3]

Referències

[modifica]
  1. «Cryptography: What Is a Trapdoor? | Baeldung on Computer Science» (en anglès americà), 01-10-2022. [Consulta: 5 desembre 2024].
  2. «Trapdoor function» (en anglès). [Consulta: 5 desembre 2024].
  3. «[https://eprint.iacr.org/2018/529.pdf Trapdoor Functions from the Computational Diffie-Hellman Assumption∗]» (en anglès). [Consulta: 5 desembre 2024].