Puesto que usted pide "plain English", permítanme hablar un poco de qué se trata y cómo RSA esperanzas a la dirección de la misma.
Como mencioné en un anterior respuesta el problema de fondo es esta: usted desea comunicarse de forma segura con alguien. Hay dos técnicas: una es la esteganografía, que consiste en tratar de ocultar la existencia misma de la comunicación; que no es generalmente de muy matemático, y es difícil hacerlo. La otra es la criptografía, que consiste en oscurecer el mensaje, de modo que incluso si el mensaje es escuchado, la gente oyendo no entiendan. Un método para hacer esto se llama un "sistema de criptografía."
Criptosistemas normalmente se basan en una clave, una forma para que el altavoz para cifrar su mensaje, y un camino para el oyente para descifrarlo (figura fuera de lo que dice el mensaje). Históricamente, la mayoría de los criptosistemas se utiliza lo que se llama "claves simétricas": la pieza de información que se necesita para cifrar era el mismo que el de la pieza de información que se necesita para descifrar (o al menos, saber que uno era "equivalente" a sabiendas de que el otro). Ambos lados necesitaba saber la clave. Esto conduce a una dificultad: ¿cómo estamos de acuerdo en una clave? Si no podemos comunicarnos sin necesidad de ser escuchado, entonces no podemos estar de acuerdo en una clave sin que todos tengan que averiguar lo que la clave es, lo que hace que el sistema inútil. Y si nos puede comunicarse sin ser escuchado, entonces no hay ningún punto en el que toda la canción y la danza, sólo podemos hablar a través de esa comunicación.
Hay un número de maneras de resolver este problemas: tradicionalmente, había una forma segura de comunicación con un ancho de banda limitado (sólo pequeñas cantidades de información puede ser difundida a través de ella, y sólo en ciertos momentos), por lo que la clave podría ser intercambiado, pero la comunicación era muy difícil (valijas diplomáticas, espías, etc).
Pero hay otro tipo de criptosistemas que fueron descubiertos en la década del 70 (se sabe que en el reino unido GCHQ sabía acerca de ellos antes, y siempre hay rumores de que la NSA sabía acerca de ellos antes de que se "públicamente descubierto"), que no son simétricos, en el siguiente sentido: conocer la clave de cifrado no dan suficiente información para encontrar la clave de descifrado. Ellos son llamados "criptosistemas de clave pública", debido a que usted puede decirle a todo el mundo cómo cifrar los mensajes para usted, pero sabiendo esta información no les da una forma de descifrar los mensajes enviados a usted. Que requiere la "clave de descifrado", que sólo se sabe.
[Lo siento, vamos a tener que tirar un poco de matemática en el ahora, pero había que esperar.] Estos sistemas se basan en lo que se llama trampa funciones. La idea de una tapadera de la función es que tiene una función $f$ esa cifra, pero para los que es difícil encontrar la inversa, $f^{-1}$ (que descifra); así que incluso si usted sabe exactamente lo $f$ es, y usted sabe que la salida de $f$ era, digamos, $D$, todavía es muy difícil encontrar a $f^{-1}(D)$ (lo que sería el mensaje que se envía). Sin embargo, si por casualidad usted conoce una pieza adicional de información, $k$, luego de $f$, $D$, y $k$ usted puede encontrar fácilmente $f^{-1}(D)$ (creo que de $k$ como la palanca que abre la trampilla" y permite a la inversa de la caída a través de). Así que la idea de estos llave pública de sistemas es decirle a todos lo $f$ es, pero ten $k$ secreto. Nadie tiene que saber $k$ a fin de calcular las $f(M)$, lo que se puede hacer en secreto. A continuación, se puede gritar $f(M)$; no importa si la gente escucha $f(M)$, porque es muy difícil encontrar a $M=f^{-1}(f(M))$ (muy difícil de descifrar). Pero ya que usted sabe el secreto de la pieza de información $k$, cuando escuche $f(M)$, puede utilizar $k$ encontrar $M$, y voilá!, usted sabe que el mensaje secreto, pero que nadie más hace.
RSA es uno de estos sistemas. En RSA, los mensajes son números (es sencillo convertir un texto en un número). Quiero comunicar un número secreto, aunque todo el mundo me escucha hablar.
La forma de RSA trabajo es el uso de la exponenciación modular. Selecciona un gran número de $n$, y dos números, $e$$d$, de tal manera que $ed\equiv 1\pmod{\varphi(n)}$ (Euler $\varphi$ función). Usted decirle a todos lo $n$, y decirle a todos lo $e$; estas son las claves públicas, pero que mantenga $d$ secreto. Si quiero enviar un mensaje de $M$, la primera vez que asegúrese de que $\gcd(M,n) = 1$ $1\lt M\lt n$ (si no, puedo modificar el mensaje un poco, por lo que es, o yo que se rompen en pedazos si es demasiado grande). Entonces me compute $R=M^e \bmod n$, que es fácil de hacer con las computadoras, y les digo a todos que estoy enviando el mensaje de $R$. Cuando reciba $R$, usted puede averiguar lo que el mensaje original $M$ era, simplemente mediante el cálculo de $R^d \bmod n$ (que a su vez es fácil de hacer computacionalmente). La razón por la que este le dirá lo $M$ es debido a que el Teorema de Euler.
El Teorema de Euler. Si $n$ es un entero positivo, y $\gcd(a,n)=1$,$a^{\varphi(n)} \equiv 1 \pmod{n}$.
Esta es una generalización de Fermat Poco Teorema (en Ese Pequeño Teorema, ha $n=p$ un primo, por lo $\varphi(n)=\varphi(p)=n-1$, y la ecuación indica que el $a^{p-1}\equiv 1\pmod{p}$ si $\gcd(a,p)=1$).
Desde $ed\equiv 1 \pmod{\varphi(n)}$, podemos escribir $ed = k\varphi(n)+1$ para algunos entero $k$. Entonces tenemos:
$$ R^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{k\varphi(n)+1} = (M^{\varphi(n)})^kM \equiv 1^kM = M \pmod{n}$$
(mediante las reglas de la exponenciación, y debido a $M^{\varphi(n)}\equiv 1\pmod{n}$).
Ahora, esto significa que usted puede averiguar $M$, porque sabes que $d$. Otras personas averiguar $M$ sin saber $d$?
Si usted puede averiguar $\varphi(n)$, luego resulta ser muy fácil de averiguar $d$ desde el conocimiento de $e$: porque sabes que $\gcd(e,\varphi(n))=1$, a continuación, utilizando el Algoritmo de Euclides usted puede encontrar los números enteros $x$ $y$ tal que $ex+\varphi(n)y = 1$; y, a continuación,$d\equiv x\pmod{\varphi(n)}$, y todo esto se puede hacer fácilmente. Así que usted quiere asegurarse de que la computación $\varphi(n)$ no es fácil, incluso si usted sabe $n$.
Si puedes factor de $n$ a de los números primos, aunque, a continuación, $\varphi(n)$ es muy fácil de encontrar. Así que usted desee $n$ a no ser un número primo, pero a muy pocos factores primos (porque cada vez que encontramos un primer factor, se divide, y usted tiene un pequeño problema a la izquierda). Idealmente, queremos que $n$ a de ser sólo un producto de dos muy grandes los números primos, $n=pq$.
Así, la forma en que esto funciona es: en primer lugar encontramos dos muy grande secreto de los números primos (hay maneras de hacer esto), $p$$q$. Luego de calcular $n=pq$. Como usted sabe,$p$$q$, usted también sabe que $\varphi(n) = (p-1)(q-1)$, lo $\varphi(n)$ es fácil para usted. A continuación, elige un $e$, y ya que usted sabe $\varphi(n)$, usted puede encontrar $d$ fácilmente (hay "malas decisiones" de $e$ que va a hacer el descubrimiento de la $d$ no es demasiado difícil, pero son conocidas; evitar; también hay malas decisiones de $p$$q$, por lo que no demasiado, no se preocupe demasiado acerca de esto).
Por lo tanto, ahora que usted sabe $p$, $q$, $d$ y $e$. Informar a todos los $pq$$e$, pero mantiene $d$, $p$, y $q$ secreto.
Si quiere enviar el mensaje $M$, $1\lt M \lt pq$, yo no le digo a nadie lo $M$ es, calculo $M^e\bmod n$, y le digo a todos los $M^e$. Usted puede averiguar $M$ porque sabes que $d$, así como por encima, $(M^e)^d = M^{ed} \equiv M\pmod{n}$ por el Teorema de Euler.
La esperanza es que acabo de conocer $n$, $d$, y $M^d \bmod{n}$, es difícil de averiguar $M$.
La RSA Problema es precisamente el problema: si usted sabe $n$ (y usted sabe que $n$ es el producto de dos números primos, pero no sabes que prepara antes de tiempo), usted sabe $d$, y usted sabe $M^d\bmod{n}$, se puede averiguar $M$? La seguridad del criptosistema RSA depende de lo duro de la RSA Problema a resolver.
Si puedo factor de $n$, entonces yo puedo resolver el Problema RSA: me pueden encontrar $\varphi(n)$, entonces puedo usar $\varphi(n)$ $d$ encontrar $e$, y una vez que he a$e$$M^d$, acabo de averiguar $(M^d)^e \equiv M \pmod{n}$. Así que el RSA Problema es más difícil que el problema de la factorización de un producto de dos números primos. Por suerte, en la medida en que conocemos el problema de la factorización de un producto de dos números primos es bastante duro.
No se sabe, sin embargo, si hay una forma distinta de resolver el problema RSA que no puede depender de factoring $n$. Tal vez, tal vez no.
Espero que esto ayude.
