Hay toda una clase de cifrado/seguridad de los sistemas que se basan en lo que es llamado "trampa de la puerta de funciones". La idea es que se trata de funciones que son generalmente fáciles de calcular, pero para el que encontrar la inversa es muy duro (aquí, "fácil" y "difícil" se refieren a cómo rápidamente sabemos cómo hacerlo), pero de tal forma que si usted tiene una pieza adicional de información, encontrar la inversa es fácil así. Los números primos juegan un papel muy importante en muchos de esos sistemas.
Un ejemplo es la función que toma dos números enteros y que multiplica juntos (algo que podemos hacer muy fácilmente), frente a la "inversa", que es una función que toma un entero y le da adecuada de los factores (dado $n$, dos números $p$ y $q$ tales que $pq=n$ y $1\lt p,q\lt n$). Si $n$ es el producto de dos números primos, entonces existe una y sólo una pareja.
Otro ejemplo es el logaritmo discreto. Para considerar un ejemplo sencillo, mira los enteros modulo, digamos, $7$. Los enteros entre $1$ y $6$, inclusive, forma un grupo bajo la multiplicación, y de hecho cada número entre $1$ y $6$ de $3 dólares. El "problema del logaritmo discreto" sería, dada una cantidad de $x$ entre $1$ y $6$, para encontrar un número $a$ que $3^$ equivale a $x$ modulo $7$. En este caso, puede probar los poderes de $3$ hasta llegar a la respuesta correcta. Pero si el modulo es muy grande, entonces esto podría tomar demasiado tiempo.
Un método para el intercambio de información a través de un canal abierto se basa en el hecho de que no tenemos muy buena métodos de búsqueda de los logaritmos discretos en general, pero ¿ tienen muy buenos métodos para calcular modular de poderes. La idea es: supongamos que usted y yo necesitamos para el intercambio de información. Queremos utilizar algunos muy seguro sistema criptográfico que se basa en una complicada clave. Pero, ¿cómo podemos estar de acuerdo en una clave? Si tenemos alguna forma segura de comunicarse, de modo que cuando estamos de acuerdo en la clave que nadie va a escuchar de nosotros, entonces ¿por qué molestarse con todo el ejercicio? Debemos comunicar que el uso de forma segura. Así que en lugar necesitamos comunicarnos en un lugar donde podamos estar a la sobrecarga. ¿Cómo podemos estar de acuerdo en un secreto clave si todo el mundo puede oírnos? Bueno, Diffie y Hellman propuso el siguiente método:
Elige un gran primer $p$, y un número $r$ de tal forma que cada número entre $1$ y $p-1$ de $r$ modulo $p$ (los números de $de i$ se sabe que existen para cada prime; se les llama raíces primitivas). Todo el mundo sabe que $p$ y todo el mundo sabe $r$. Entonces elijo un número secreto $a$, y elige un número secreto $b$. No puedo decir mi número secreto ( secreto). Pero te diré lo $r^a \mod p$ es. Porque computación modular de poderes es fácil, puedo hacer este cálculo bastante fácil; pero porque no sabemos cómo hacer logaritmos discretos fácilmente, estamos con la esperanza de que nadie va a ser capaz de averiguar $$ solo de saber $r^$... al menos, no muy rápidamente. Asimismo, me puedes decir $r^b \mod p$. Ahora, usted sabe que $r^$, y usted sabe lo que $b$ es, por lo que calcular $(r^a)^b \mod p$. Por las leyes de la exponente, usted ahora sabe que (en secreto!) el número $r^{ab} \mod p$. Yo, por otro lado, se sabe que $r^b$ (porque usted me dijo que ese número) y sé lo que $a$ es. Así que me calcular $(r^b)^a\mod p$. Pero esto es igual a $r^{ab} \mod p$. Así que ahora los dos tenemos una pieza de información, es decir, la cantidad de $r^{ab}\mod p$. Este va a ser nuestro "clave secreta".
Ahora, si alguien puede averiguar $un$ o $b$, a continuación, ya que también se sabe que $r^a$ y $r^b$, que voy a ser capaz de averiguar nuestra clave secreta. Esperamos que esto es duro, pero sin duda tenemos $p$ a ser muy grande: de lo contrario, puede intentarlo de todos los poderes de $r$ hasta que lleguen a la derecha. Necesitamos el "espacio de búsqueda" para ser muy grande, por lo que necesitamos $p$ a ser muy grande. Agregado: Como jarra de puntos, habiendo $p$ grande no es suficiente. Hay algoritmos para calcular logaritmos discretos que son particularmente buenas, con ciertos tipos de números primos, por lo que generalmente también requieren que $p$ satisfacer algunas otras "buenas" propiedades en relación con la aplicación de cifrado. En general, usted quiere $p$ y $(p-1)/2$ a ser ambos números primos, por ejemplo. Por otro lado, en la práctica, no realmente necesitan $r$ a ser una raíz primitiva. En su lugar, es suficiente para que se genere una "gran" subgrupo del grupo multiplicativo, que uno por lo general quiere ser de primer orden.
(Nota: averiguar $un$ o $b$ es sólo una manera en que se podría averiguar nuestra clave secreta $r^{ab}$, ya que todo el mundo sabe que $p$, $r$, $r^a$ y $r^b$. Es que no se sabe si esto es esencialmente la única manera de romper este "intercambio de claves" método; el método realmente se basa en si se puede averiguar $r^{ab}$ saber $r$, $p$, $r^a$ y $r^b$; esto se llama el de Diffie-Hellman problema; el de Diffie-Hellman problema es que en la mayoría de los tan duro como el Problema del Logaritmo Discreto, pero no sabemos si es sólo tan duro (podría ser más fácil); y no sabemos cómo duro el Problema del Logaritmo Discreto es, solo sabemos que no tenemos ningún maneras fáciles de hacer todavía).
Para el intercambio de claves es un lugar donde los grandes números primos son muy importantes. (Diffie-Hellman no es la única manera de hacer intercambios de claves). Otro lugar donde los grandes números primos a jugar un gran papel en RSA que es un criptosistema que también se basa en grandes números primos (esta vez, dos grandes números primos $p$ y $q$, y hacemos aritmética modulo $n=pq$).
Añadido: así se Podría agregar una rápida visión general de RSA y cómo los números primos entran en juego. Aquí, una vez más exponenciación modular es parte del proceso. Esta es una "clave pública" del sistema: voy a decirle a todos cómo me envía mensajes secretos, que esperemos que sólo puedo descifrar. (En Diffie-Hellman, no hemos de intercambio de un mensaje; nos pusimos de acuerdo en una clave secreta que vamos a utilizar con un sistema separado que requiere una clave secreta; por ejemplo, AES). Elijo dos grandes números primos $p$ y $q$, y calcular $n=pq$. Yo también escoger un número que $e$ que es primo relativo a $(p-1)(q-1)$ (puedo hacer eso porque sé que $p$ y $q$). Entonces puedo usar el algoritmo de Euclides, que es bastante rápido, a encontrar $d$ que $ed\equiv 1 \pmod{(p-1)(q-1)}$. Finalmente, quiero decirle a todos lo $n$ y $e$. Si quieres enviarme un mensaje, primero convertir a un número $M$ utilizando algún mecanismo estándar. Luego de calcular $M^e \mod n$, y me dices lo $M^e\mod n$ es. Voy a tomar $M^e$ y calcular $(M^e)^d = M^{ed}\mod n$. Porque $ed\equiv 1 \pmod{(p-1)(q-1)}$, entonces $M^{ed}\equiv M\pmod{n}$, por lo que es ¿cómo puedo recuperar $M$. La seguridad del sistema se basa en la esperanza de que a partir de conocer $n$ y $e$, es difícil de averiguar $d$ (es fácil si sé que $p$ y $q$; por esta razón se cree que esto es una "trampa de la puerta de la función", como se describe en el primer párrafo). El problema es que en la mayoría de los tan duro como el factoring $n$, porque si el factor $$ n, entonces usted puede encontrar $d$ la misma manera que lo hice; no se sabe si el problema de encontrar $M$ de $n$, $M^e$, e $e$ es al menos tan duro como el factoring (se ha demostrado que algunas variantes son al menos tan duro como el factoring), y de nuevo no sabemos cómo duro de factoring es. Pero: porque sabemos que si puedes factor $n$, a continuación, puede leer el mensaje, entonces queremos hacer $n$ difícil factor. Sólo tiene dos factores, pero usted no quiere que ellos sean fáciles de encontrar, así que usted desea $p$ y $q$ a ser grande seguro. (De nuevo, hay otras condiciones que normalmente se pone en $e$, $p$ y $q$ para asegurarse de que ciertos ataques especiales no se logra fácilmente, pero al menos necesitamos $p$ y $q$ a ser muy grande).
