Criptografía de clave pública y algoritmo de clave pública RSA
Este artículo presenta brevemente las ideas y características del sistema de criptografía de clave pública, presenta específicamente la base teórica, el principio de funcionamiento y el proceso de implementación específico del algoritmo RSA, y utiliza Un ejemplo sencillo. Explique cómo se implementa el algoritmo. Este artículo finalmente resume algunas deficiencias y soluciones del algoritmo RSA.
Palabras clave: criptosistema de clave pública, clave pública, clave privada, RSA
1 Introducción
Con la realización gradual de las redes de computadoras, las perspectivas de Internet Things están mejorando cada vez más. El desarrollo económico global está entrando en la era de la economía de la información y la economía del conocimiento está comenzando a tomar forma. La seguridad de la información informática es cada vez más importante. Ya sea el intercambio de información personal o el desarrollo del comercio electrónico, existe una necesidad urgente de garantizar la seguridad de la transmisión de información en Internet. La tecnología de seguridad de la información es una disciplina integral que involucra la teoría de la información, la informática y la criptografía. Su tarea principal es estudiar métodos de protección de la información en sistemas informáticos y redes de comunicación para lograr la seguridad, confidencialidad, autenticidad e integridad de la información en el sistema. Entre ellos, el núcleo de la seguridad de la información es la tecnología de criptografía. La criptozoología es una materia interdisciplinaria que integra matemáticas, informática, electrónica y comunicaciones. No sólo garantiza el cifrado de información confidencial, sino que también implementa funciones como firma digital, verificación de identidad y seguridad del sistema. Es una de las ciencias importantes de la modernización. Este artículo presentará brevemente el sistema de criptografía de clave pública y el algoritmo RSA, que actualmente es el más popular en este sistema.
2 Sistema de criptografía de clave pública
Para explicar el sistema de criptografía de clave pública, primero comprendamos las diferencias en los algoritmos de cifrado: Los algoritmos de cifrado actuales se pueden dividir en algoritmos de clave única según el Método de clave: Criptosistemas y criptografía de clave pública.
2.1. Contraseña de una clave
También conocida como contraseña simétrica, es un método de cifrado relativamente tradicional en el que se utiliza la misma clave para las operaciones de cifrado y descifrado. Al transmitir y procesar información, tanto el remitente como el receptor de la información deben tener una contraseña (llamada cifrado simétrico). Por tanto, ambas partes deben obtener la clave y mantenerla en secreto.
La seguridad de un criptosistema de clave única depende de los dos factores siguientes: primero, el algoritmo de cifrado debe ser lo suficientemente fuerte y, en la práctica, es imposible descifrar información basándose en el propio texto cifrado; La seguridad del método de cifrado depende de la confidencialidad de la clave, no de la confidencialidad del algoritmo. Por lo tanto, no necesitamos garantizar la confidencialidad del algoritmo (de hecho, muchos algoritmos de criptosistemas de clave única utilizados en la realidad son públicos), pero debemos garantizar la confidencialidad de la clave.
A partir de estas características de la criptografía de clave única, podemos ver fácilmente que existen dos problemas principales: Primero, el número de claves. En un criptosistema de clave única, cada par de comunicadores requiere un par de claves. Cuando aumenta el número de usuarios, el número de claves inevitablemente aumentará exponencialmente. Por lo tanto, en la comunicación en red, la generación, almacenamiento y distribución de una gran cantidad de claves será un problema difícil. En segundo lugar, está la cuestión de la distribución de claves. En un criptosistema de clave única, la seguridad del cifrado depende completamente de la protección de la clave. Sin embargo, dado que ambas partes utilizan la misma clave, las personas deben intercambiar claves entre sí. Por lo tanto, para garantizar la seguridad, se debe utilizar algún otro canal seguro para distribuir la clave, como utilizar un mensajero especial para transmitir la clave. Esto es bastante costoso e incluso poco realista, especialmente en un entorno de red informática donde las personas usan la red para transmitir archivos cifrados, pero necesitan otro canal seguro.
2.2 Cifrado de clave pública
Son precisamente las deficiencias del sistema de criptografía de clave única las que hacen que sea tan difícil de resolver, por lo que se debe desarrollar una criptografía nueva, más efectiva y más avanzada. El sistema se vuelve más urgente y necesario. En este caso, en un momento histórico surgió un nuevo sistema de criptografía de clave pública que resolvió el problema de distribución de claves que ha preocupado a innumerables científicos. De hecho, en este sistema ni siquiera es necesario distribuir claves que deben mantenerse estrictamente confidenciales. Este avance también se considera el mayor logro en la historia de la criptografía desde la invención de los cifrados de reemplazo de código único en los últimos dos mil años.
Esta nueva idea fue propuesta por dos académicos de la Universidad de Stanford, Diffie y Hellman, en la década de 1970. La mayor diferencia entre este sistema y el cifrado de clave única es:
En un criptosistema de clave pública, se utilizan diferentes claves para el cifrado y descifrado (en comparación con las claves simétricas, la gente las llama claves asimétricas), hay una interdependencia entre las dos claves: es decir, la información cifrada con cualquiera de las claves sólo puede descifrarse con la otra clave. Esto permite que ambas partes se comuniquen de forma segura sin intercambiar claves de antemano. Entre ellos, la clave y el algoritmo de cifrado son públicos y cualquiera puede utilizar esta clave para cifrar el archivo y enviarlo al destinatario. Esta clave de cifrado también se denomina clave pública. Una vez que el destinatario recibe el archivo cifrado, puede utilizar su clave de descifrado para descifrarlo. La clave de descifrado es su responsabilidad personal y no necesita ser distribuida, por lo que también se denomina clave privada, lo que resuelve el problema de la distribución de claves.
Para ilustrar este punto, podemos considerar la siguiente analogía:
Dos personas que se comunican en un canal inseguro, supongamos que Alice (receptor) y Bob (remitente) quieren comunicarse de forma segura. sin ser destruido por su oponente Oscar. Alice pensó en una manera. Utiliza un candado (equivalente a una clave pública). Cualquiera puede bloquear este tipo de candado con un clic, pero solo la clave de Alice (equivalente a una clave privada) puede abrirlo. Luego, Alice emitió numerosos candados de este tipo. Cuando alguien, como Bob, quiere enviarle una carta, sólo necesita encontrar una caja, cerrarla con el candado de Alice y enviársela a Alice.
En este momento, nadie (incluido el propio Bob) puede abrir la caja excepto Alice, que tiene la llave, por lo que incluso si Oscar puede encontrar la cerradura de Alice, incluso si Oscar puede interceptar la caja durante el proceso de comunicación, sin la de Alice, no puede abrir la caja. sin la clave, y no es necesario distribuir la clave de Alice, por lo que Oscar no puede obtener esta "clave privada".
Como se puede ver en la introducción anterior, la idea de la criptografía de clave pública no es complicada. La cuestión clave al implementarla es cómo determinar la clave pública, la clave privada y el algoritmo de cifrado/descifrado. es decir, cómo encontrar la cerradura y la llave de Alice. Suponemos que en este sistema, PK es información pública y se utiliza como clave de cifrado, mientras que SK debe ser mantenido en secreto por el usuario y se utiliza como clave de descifrado. También se describen el algoritmo de cifrado e y el algoritmo de descifrado d. Aunque SK y PK aparecen en pares, SK no se puede calcular a partir de PK. Deben cumplir las siguientes condiciones:
① Después de cifrar el texto sin formato X con la clave de cifrado PK, utilice la clave de descifrado SK para descifrar y recuperar el texto sin formato, o escriba: dsk (epk (x)) = X .
②La clave de cifrado no se puede utilizar para descifrar, es decir, DPK (EPK (x)) ≠ X
③El par PK y SK se puede generar fácilmente en la computadora.
④En realidad, es imposible deducir SK de la PK conocida.
⑤Las operaciones de cifrado y descifrado se pueden revertir, es decir, EPK (DSK (x)) = X
De las condiciones anteriores se puede ver que bajo el sistema de criptografía de clave pública , la clave de cifrado La clave no es igual a la clave de descifrado. La clave de cifrado puede hacerse pública, de modo que cualquier usuario pueda utilizar la clave pública para cifrar un mensaje enviado a ese usuario, mientras que la clave privada única que guarda ese usuario se mantiene en secreto y sólo él puede recuperar y descifrar el texto cifrado. Aunque teóricamente es posible derivar la clave de descifrado a partir de la clave de cifrado, el diseño de este algoritmo es en realidad imposible o, aunque se puede derivar, lleva mucho tiempo y se vuelve inviable. Por lo tanto, hacer pública la clave de cifrado no compromete la seguridad de la clave.
La idea de este sistema es simple, pero cómo encontrar un algoritmo adecuado para implementar este sistema es un verdadero problema para los criptógrafos, porque como Pk y SK son un par de claves interrelacionadas, así es posible deducir uno del otro. Si el oponente Oscar puede deducir SK de PK, entonces el sistema ya no es seguro. Por lo tanto, cómo encontrar un algoritmo adecuado para generar PK y SK adecuados y hacer imposible derivar SK de Pk es un problema urgente que los criptógrafos deben resolver. Este problema incluso paralizó durante mucho tiempo el desarrollo de la criptografía de clave pública.
Para resolver este problema, los criptógrafos consideraron funciones matemáticas unidireccionales de trampilla. A continuación, podemos darle una definición informal:
La función de cifrado público de Alice debería ser fácil de calcular, mientras que su inversa (es decir, la función de descifrado) debería ser difícil de calcular (para otras personas además de Alice). Para muchas funciones de la forma Y=f(x), para un valor dado de la variable independiente x, es fácil calcular el valor de la función Y sin embargo, a partir de un valor dado de y, en muchos casos es difícil; para calcular la relación de función f ( x) Calcula el valor de x. Una función que es fácil de calcular pero difícil de invertir a menudo se denomina función unidireccional. Durante el proceso de cifrado, esperamos que la función de cifrado e sea una función inyectiva monomial para que pueda descifrarse. Aunque no se puede demostrar que ninguna función sea unidireccional, se dice que muchas funciones inyectivas son unidireccionales.
Por ejemplo, hay una función que se considera unidireccional. Supongamos que n es el producto de dos números primos grandes p y q, y b es un entero positivo. Entonces F se define como:
f (x )= x b mod n
(Si gcd(b,φ(n))=1, entonces esta es en realidad la función de cifrado RSA de la que hablaremos a continuación. )
Si desea construir un criptosistema de clave pública, no basta con proporcionar una función inyectiva unidireccional. Desde la perspectiva de Alice, e no necesita ser unidireccional ya que necesita descifrar la información recibida de manera eficiente. Entonces Alice debería tener una trampilla que contenga la información secreta e que su función pueda encontrar fácilmente. En otras palabras, la razón por la cual Alice puede descifrar efectivamente es porque tiene conocimiento secreto adicional, a saber, SK, que puede proporcionarle la función Decrypt d. entonces llamamos a una función función unidireccional de trampilla. Si se trata de una función unidireccional, después de conocer una trampilla específica, es fácil encontrar su función inversa.
Considere la función anterior f (x) =? xb mod n . Podemos saber que su función inversa f -1 tiene una forma similar f(x) = xa? Mod n, el valor apropiado para a. La captura utiliza la factorización de n para calcular eficientemente el exponente a correcto (para una b dada).
Por conveniencia, tomamos algún tipo de función unidireccional de trampilla. . Entonces, ¿elegir aleatoriamente una función f a la que pertenecer? Como función de cifrado pública; su función inversa f-1 es una función de descifrado secreto. Entonces se podrá implementar el criptosistema de clave pública.
Basándose en las ideas mencionadas anteriormente sobre las funciones unidireccionales de trampilla, los académicos han propuesto muchos métodos de cifrado de clave pública, cuya seguridad se basa en problemas matemáticos complejos.
Dependiendo del problema matemático, al menos los siguientes tres sistemas se consideran seguros y eficientes: el sistema de factorización de enteros grandes (RSA), el sistema de logaritmos discretos de curva elíptica (ECC) y el sistema de logaritmos discretos (DSA).
3 Algoritmo RSA
3.1 Introducción
En la actualidad, el sistema de clave pública RSA más famoso y utilizado es desarrollado por Rivest y propuesto por Shamir y Adleman en un artículo titulado "Métodos para obtener firmas digitales y criptosistemas de clave pública" publicado en 1978. Es un criptosistema asimétrico (clave pública) basado en la teoría de números y sistemas de cifrado de bloques. Su nombre proviene de las iniciales de tres inventores. Su seguridad se basa en la dificultad de descomponer números enteros grandes y números primos. La descomposición de números enteros grandes es un problema famoso en matemáticas y no existe una forma eficaz de resolverlo, por lo que se puede garantizar la seguridad del algoritmo RSA. El sistema RSA es el método más típico entre los sistemas de clave pública. La mayoría de los productos y estándares que utilizan criptografía de clave pública para cifrado y firmas digitales utilizan el algoritmo RSA.
El algoritmo RSA es el primer algoritmo que se puede utilizar tanto para cifrado de datos como para firmas digitales, por lo que proporciona un método básico para el cifrado y autenticación de información en redes públicas. Suele ser un par de claves RSA, una de las cuales es la clave secreta, que guarda el usuario, la otra es la clave pública, que puede hacerse pública o incluso registrarse en el servidor de la red. Las personas cifran un archivo usando una clave pública y lo envían a una persona, quien puede descifrar el archivo con la clave privada. Para mejorar la seguridad, la clave RSA debe tener al menos 500 bits de longitud y, generalmente, se recomiendan 1024 bits.
Este algoritmo se basa en los siguientes dos hechos, que garantizan la seguridad y eficacia del algoritmo RSA:
1) Existe un algoritmo rápido para determinar si un número es primo;
2) Aún no se ha encontrado un algoritmo rápido para determinar los factores primos de un número compuesto.
3.2 Principio de funcionamiento
1) Elija dos números primos grandes diferentes pyq arbitrariamente y calcule el producto r = p * q
2) Elija arbitrariamente; Un número entero grande e, e es primo relativo con (p-1)*(q-1), y el número entero e se utiliza como clave de cifrado. Nota: La selección de e es fácil, por ejemplo, todos los números primos mayores que p y q están disponibles.
3) Determine la clave de descifrado D: D * E = 1 moduo(P-1)*(Q-1) Basado en E, P y Q, D se puede calcular fácilmente.
4) Revelar los números enteros r y e, pero no d;
5) Cifrar el texto sin formato p (asumiendo que p es un número entero menor que r) en el texto cifrado c. El método es el siguiente:
C = Pe mod r
6) Descifrar el texto cifrado c en texto plano p. Cd mod r
Sin embargo, es imposible calcular D sólo a partir de R y E (en lugar de P y Q). Por lo tanto, cualquiera puede cifrar el texto sin formato, pero sólo los usuarios autorizados (que conocen D) pueden descifrar el texto cifrado.
3.3 Ejemplo simple
Para ilustrar el proceso de trabajo del algoritmo, demos un ejemplo simple a continuación. Obviamente, aquí solo se puede tomar un número muy pequeño, pero como se mencionó anteriormente, para garantizar la seguridad, el número que usamos en aplicaciones prácticas es mucho mayor.
Ejemplo: Si p = 3, q = 5, entonces r=15, (p-1)*(q-1)=8. Elija e=11 (un número primo mayor que P y Q) y calcule d =3 a partir de D * 11 = 1moduo8.
Supongamos que el texto plano es un número entero de 13. Entonces el texto cifrado c es
C = Pe mod r
= 1311 mod 15
= 1.792.160.394.037 mod 15
= 7
El texto plano recuperado p es:
P = Cd mod r
= 73 mod 15
= 343 módulo 15
= 13
Debido a que E y D son recíprocos, el método de cifrado de clave pública también permite "firmar" la información cifrada de esta manera, de modo que el destinatario puede estar seguro de que la firma no es falsificado.
Supongamos que A y B quieren transmitir datos mediante cifrado de clave pública. A y B revelan respectivamente el algoritmo de cifrado y la clave correspondiente, pero no revelan el algoritmo de descifrado y la clave correspondiente. Los algoritmos de cifrado de A y B son ECA y ECB, los algoritmos de descifrado son DCA y DCB, ECA y DCA son recíprocos y ECB y DCB son recíprocos. Si A quiere enviar texto sin formato P a B, en lugar de simplemente enviar ECB(P), primero aplica su algoritmo de descifrado DCA a P y luego utiliza el algoritmo de cifrado ECB para cifrar el resultado y enviarlo.
El texto cifrado c es:
C = Banco Central Europeo
Después de recibir C, B aplica su algoritmo de descifrado DCB y su algoritmo de cifrado ECA en secuencia para obtener el texto plano P:
ECA
= ECA(DCB(ECB(DCA(P)))
= ECA(DCA(P))/*DCB Y El BCE se cancela mutuamente*/
=
p? /*DCB y el BCE se cancelan mutuamente*/
Para que B pueda confirmar que el mensaje es efectivamente enviado desde A Porque solo si el proceso de cifrado utiliza el algoritmo DCA, ECA puede obtener P. Solo A conoce el algoritmo DCA y nadie, ni siquiera B, puede falsificar la firma de A.
3.4 Ventajas. y desventajas
Ventajas de 3.4.1
El algoritmo RSA es el primer algoritmo que se puede utilizar tanto para cifrado como para firmas digitales. RSA es también el algoritmo de clave pública más estudiado. Han pasado casi veinte años desde que se propuso. Ha sido aceptado gradualmente por la gente después de haber sido probado por varios ataques. Generalmente se considera uno de los mejores esquemas de clave pública y la separación hace que la distribución de claves sea más conveniente. para una gran cantidad de usuarios en Internet, si un usuario desea comunicarse en secreto con otro usuario, puede imprimir la clave de cifrado de la otra parte en el libro de claves públicas y utilizarla para cifrar la transmisión. Después de que la otra parte recibe el mensaje, utiliza la clave de descifrado que solo ella conoce para descifrar el mensaje, de modo que se pueda ver el contenido del mensaje. El algoritmo RSA resuelve el problema de administración de claves de una gran cantidad de redes. usuarios Esta es la ventaja más destacada del sistema de criptografía de clave pública en comparación con el sistema de criptografía simétrica.
Desventajas
1) Generar claves es muy problemático. tecnología, es difícil lograr un cifrado de una sola vez.
2) Seguridad La seguridad de RSA se basa en la factorización de números grandes, pero no se ha demostrado teóricamente que la dificultad de descifrar RSA sea equivalente a la dificultad de factorizar números grandes. La ciencia tiende a pensar que la factorización no es un problema de NPC. En la actualidad, la gente ha podido descomponer números primos decimales por encima de 140, lo que requiere el uso de claves más largas y es más lento. Además, la gente también está buscando activamente formas de atacar RSA, como ataques de texto cifrado seleccionados; En términos generales, un atacante hará una copia oculta de una información y la firmará una entidad con la clave privada. Luego puede calcular la información que desea. De hecho, todos los ataques explotan la misma debilidad, que es el hecho de que la exponenciación preserva la estructura multiplicativa de la entrada:
(XM )d = Xd *Md mod n
As Como se mencionó anteriormente, este problema inherente surge de la característica más útil de la criptografía de clave pública: que todos tienen acceso a la clave pública. Sin embargo, este problema no se puede resolver algorítmicamente. Hay dos medidas principales: una es utilizar un buen protocolo de clave pública para garantizar que las entidades no descifren información generada arbitrariamente por otras entidades y no firmen información de la que no saben nada; Nunca firmar documentos de extraños. Al firmar, primero se aplica un hash al documento mediante una función hash unidireccional o se utilizan diferentes algoritmos de firma simultáneamente. Además de usar el módulo, la gente también ha probado algunos ataques usando el exponente de descifrado o φ(n).
3) La velocidad es demasiado lenta. Dado que la longitud del paquete RSA es demasiado grande, para garantizar la seguridad, n debe ser al menos 600 bitx, lo que hace que el costo de cálculo sea muy alto, especialmente la velocidad, que es varios órdenes de magnitud más lenta que el algoritmo criptográfico simétrico; Con el desarrollo de la tecnología de descomposición de grandes números, esta longitud sigue aumentando, lo que no favorece la estandarización de los formatos de datos. El protocolo Set (transacción electrónica segura) actual requiere que las CA utilicen claves de 2048 bits y que otras entidades utilicen claves de 1024 bits. Para resolver el problema de la velocidad, actualmente la gente utiliza ampliamente un método que combina criptografía de clave única y de clave pública. Las ventajas y desventajas de las dos son complementarias: la criptografía de clave única es rápida y la gente la usa para cifrar archivos largos. y luego use RSA para cifrar la clave del archivo, lo que resuelve bien el problema de distribución de claves de la criptografía de clave única.
4 Conclusión
En la actualidad, la creciente demanda de comercio electrónico y otras aplicaciones de Internet ha popularizado el sistema de clave pública. El sistema de clave pública incluye principalmente el control de acceso a los recursos del servidor y a la electrónica. -protección de transacciones comerciales, así como protección de derechos, privacidad personal, transacciones inalámbricas e integridad del contenido (como garantizar la autenticidad de informes de noticias o cotizaciones de bolsa). Con el desarrollo actual de la tecnología de clave pública, la tendencia de desarrollo obvia en el mercado es la integración de PKI y sistemas operativos. PKI es "pública"
La abreviatura de Key Infrastructure significa "infraestructura de clave pública". Los sistemas de clave pública se utilizan ampliamente en la certificación de CA, firmas digitales e intercambio de claves.
RSA es el algoritmo de cifrado de clave pública más utilizado. La idea original y el objetivo del desarrollo del algoritmo RSA es hacer que Internet sea seguro y confiable, y tiene como objetivo resolver el problema de transmitir y distribuir claves del algoritmo DES a través de canales abiertos. Los resultados reales no solo resuelven bien este problema; RSA también se puede usar para completar la firma digital del mensaje para resistir la negación y la negación del mensaje; al mismo tiempo, el uso de firmas digitales puede detectar fácilmente la manipulación ilegal del atacante; del mensaje, protegiendo así la integridad de la información de los datos.
Hasta ahora, el algoritmo RSA se ha utilizado en muchas tecnologías de cifrado y se ha utilizado ampliamente en muchos aspectos de Internet, incluida la aplicación del estándar Security Interface Layer (SSL), que es necesario para que los navegadores web establezcan conexiones seguras a Internet. . Además, el sistema de cifrado RSA también se puede aplicar a tarjetas IC inteligentes y productos de seguridad de red.
Pero el período actual de patente del algoritmo RSA está a punto de finalizar y será reemplazado por el criptosistema de curva elíptica (algoritmo ECC). En comparación con el algoritmo RSA, ECC tiene ventajas relativas, lo que hace que las características de ECC sean más adecuadas para la tendencia de desarrollo del comercio electrónico que requiere una respuesta rápida. Además, también se está desarrollando una nueva criptografía cuántica.
En cuanto a qué algoritmo de cifrado se debe utilizar en aplicaciones reales, debe combinarse con el entorno y el sistema de la aplicación específicos, y no se puede juzgar simplemente en función de su potencia de cifrado. Porque además del algoritmo de cifrado en sí, en el entorno real se debe considerar la distribución razonable de claves, la combinación de la eficiencia del cifrado con los sistemas existentes, el análisis de entrada y salida, etc. Con el desarrollo y actualización de la red, la tecnología de cifrado producirá algoritmos más seguros y fáciles de implementar, brindando una mayor protección para la seguridad de la información. Esperaremos y veremos hacia dónde llega la tecnología de cifrado en el futuro.
Referencias:
[1] Douglas R. Stinson, "Principios y práctica de la criptografía". Beijing: Electronic Industry Press, 2003, 2: 131-132.
[2] Simón Cantante. Historia de contraseña. Haikou: Editorial Hainan, 2001, 1: 271-272.
[3]Yingzheng Tianxia. El algoritmo de cifrado es el algoritmo RSA. /yumdq/dzsw/a2.htm.
[5] Serie 10 de tutoriales de hacking intermedio.
/jiaocheng/10.html