RSA: es fácil encontrar la clave pública de la clave secreta?

Question

Por favor, conteste a mi pregunta acerca de RSA, criptosistema de clave pública.

Sé que no es fácil encontrar la clave secreta de la clave pública . Es relativamente fácil encontrar la clave pública de la clave secreta por los científicos en el campo?

Si la respuesta es sí, entonces es que hay algún sistema de criptografía de tal manera que sólo una persona en particular puede codificar y uno en público puede decodificar? Para un escenario de ejemplo , un rey escribe a su fin y codifica usando su (secreto) de clave pública . Entonces sus soldados decodificar el código usando la (abierto) clave secreta para comprobar si realmente fue escrito por el rey.

Muchas gracias.

Answer 1

Para los usos habituales de RSA, la clave secreta es difícil de encontrar, y la clave pública es trivial. Esto es porque la mayoría de las implementaciones de uso 65537 como la clave pública (la razón tiene que ver con su primalidad y la eficiencia de repetirse el cuadrado de $e=65537=2^{16}+1$).

Muchos sistemas rechoose $p$ $q$ si $\phi(pq)$ no es coprime a 65537, lo que significa que el público exponente es nunca otra cosa.

Varias otras respuestas tenga en cuenta que $e$ $d$ son intercambiables, pero esto ignora tanto la práctica y varios de los principales resultados del criptoanálisis. En particular, incluso si aceptamos $e$ a variar, todavía se puede encontrar determinado $d$ si es lo suficientemente pequeño. Esto es debido al hecho de que Calderero del algoritmo pueden encontrar pequeñas raíces de polinomios modulo de un compuesto desconocido el uso de la factorización de la liga de la leche y algunos agregado ingenio. El límite sigue aumentando, pero (de memoria) creo que si $e < n^{.33}$ se puede encontrar desde $n$ $d$ (aquí se $n=pq$). Así diciendo $e$ $d$ son equivalentes es falso (y peligroso). No es una conjetura de que el "verdadero" bound es $n^{.5}$, lo que significa que por seguridad el secreto exponente tendría que estar por encima de $\sqrt{n}$.

Nota: Para aquellos que realmente están interesados, Boneh tiene un agradable encuesta de estos resultados (y muchos otros). Y es bastante fácil de leer por no criptógrafos que tienen una moderadamente formación sólida en matemáticas.

Answer 2

No, encontrar la clave secreta de la clave pública es tan duro, en abstracto, como la búsqueda de la clave secreta de la clave pública.

Lo que sugiero es en realidad la forma estándar en que RSA se utiliza para la "firma de los mensajes". Con el fin de autenticar un mensaje (para asegurarse de que el mensaje fue enviado por mí), me codificar con mi privado clave, lo que significa que cualquiera puede usar la clave pública para descifrar y saber que fue realmente enviado por mí (porque, presumiblemente, nadie sabe mi clave privada, excepto yo).

Pero esto no tiene nada que ver con si se puede obtener la clave pública de la clave secreta; tiene que ver con la forma en RSA funciona (el papel de la clave pública y privada son simétricas).

Answer 3

No, ellos son igualmente difíciles de encontrar. En particular, la clave de cifrado y la clave de descifrado son modulares inversos. La dificultad en encontrar la clave de descifrado de la clave pública que se encuentra en el hecho de que son inversos... mod $\varphi (n)$, y por lo tanto uno debe factor o ser muy ingenioso para hallar la inversa.

Si uno eligió hacia atrás, y se distribuye el "descifrado" en lugar y se mantiene la "codificación" clave para uno mismo, la seguridad sería exactamente el mismo. (Pongo entre comillas para mostrar que ellos eran los originales de descifrado y claves de cifrado).

Pero a su segunda pregunta, no hay un método similar al de RSA llamado firmas digitales, donde sólo la persona que conoce la clave secreta puede distribuir un mensaje de que todos en público puede decodificar. Se llama una firma porque garantiza la autenticidad

Answer 4

Depende de lo que quieres decir con "clave privada". Si las claves públicas y privadas se $(n,d)$$(n,e)$,$ed=1 \mod \varphi(n)$, luego las otras respuestas son correctas - es igual de duro para conseguir $d$$e$$e$$d$. Pero la clave fue generado como $n=pq$ para los dos primos $p$$q$, y en la práctica los números de $p,q$ se guardan junto con la clave privada. (Esto permite mucho más rápido cálculos utilizando el Teorema del Resto Chino.) Y si usted sabe de $p$$q$, entonces se puede calcular el $d$ $e$ (o $e$$d$) fácilmente-es sólo un modular inversa.

Answer 5

No, las dos son simétricos (o equivalentes). Así que si es difícil obtener la clave secreta del público, es igual de duro para conseguir que el público de lo privado.