TellezGonzalezJorgeLuis_RSA

Vista previa del material en texto

Universidad Nacional Autónoma de México
Facultad de Ingeniería
Criptografía
Grupo: 02 - Semestre: 2023-2
Tarea:
Lectura RSA.
Fecha de entrega: 27/03/2023
Profesora:
Dra. Rocío Alejandra Aldeco Pérez
Alumno:
Téllez González Jorge Luis
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Introducción
RSA es un algoritmo de cifrado de clave pública ampliamente utilizado en la seguridad
informática. RSA se basa en la idea de que la factorización de números grandes es difícil y se
utiliza para cifrar y descifrar mensajes. Al emplear el paradigma asimétrico, cada usuario
tiene dos claves: una pública y una privada. La clave pública se utiliza para cifrar un mensaje
que solo puede ser descifrado con la clave privada correspondiente. De esta manera,
cualquier persona puede enviar mensajes cifrados a otra persona sin conocer su clave
privada. Una gran ventaja de RSA es que también puede usarse para el firmado digital
invirtiendo el proceso: cifrando con la clave privada y descifrando con la clave pública.
A continuación se presenta un resumen del artículo A Method for Obtaining
Digital Signatures and Public-Key Cryptosystems (1978) de R.L. Rivest, A. Shamir, and L.
Adleman, en donde se propone un nuevo algoritmo criptográ�co que más tarde sería
conocido como RSA.
Desarrollo
El artículo inicia presentando un método de cifrado que presenta una propiedad novedosa
consistente en poder compartir una clave de cifrado que no es, a su vez, la clave de
descifrado. Esto tiene importantes implicaciones, ya que no se requieren mensajeros u otros
medios seguros para transmitir claves, y un mensaje puede ser cifrado utilizando una clave
de cifrado revelada públicamente por el destinatario previsto. Además, un mensaje puede
ser �rmado mediante el uso de una clave de descifrado mantenida en privado, y cualquier
persona puede veri�car esta �rma utilizando la clave de cifrado correspondiente revelada
públicamente. Las �rmas no pueden ser falsi�cadas, y un �rmante no puede negar
posteriormente la validez de su �rma. Para probar la validez del método, los autores emplean
pruebas matemáticas y teóricas de su implementación en un sistema de correo electrónico.
Criptosistemas de Clave Pública
A continuación, se introduce el concepto de criptosistemas de clave pública descrito por
primera vez por Di�e y Hellman. En un criptosistema de clave pública, cada usuario coloca
en un archivo público un procedimiento de cifrado E. El archivo público es un directorio
que da el procedimiento de cifrado de cada usuario. El usuario mantiene en secreto los
detalles de su correspondiente procedimiento de descifradoD. Estos procedimientos tienen
cuatro propiedades:
2
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
● A)Descifrar la forma cifrada de un mensaje M produce M.
● B) Tanto E como D son fáciles de calcular.
● C)Al revelar públicamente E, el usuario no revela una manera fácil de calcular D;.
● D) Si un mensaje M se descifra primero y luego se cifra, M es el resultado. Un
procedimiento de cifrado (o descifrado) típicamente consiste en un método general
y una clave de cifrado.
Privacidad
El cifrado es el medio estándar para garantizar la privacidad de una comunicación. El
remitente cifra cada mensaje antes de transmitirlo al destinatario. El destinatario (pero
ninguna persona no autorizada) conoce la función de descifrado adecuada que debe aplicar
al mensaje recibido para obtener el mensaje original. Un espía que escucha el mensaje
transmitido solo oye "basura" (el texto cifrado) que no tiene sentido para él ya que no sabe
cómo descifrarlo.
La gran cantidad de información personal y sensible que se encuentra actualmente
en bancos de datos informatizados y se transmite por líneas telefónicas hace que el cifrado
sea cada vez más importante. Todos los métodos de encriptación clásicos sufren del
"problema de distribución de claves". El problema es que antes de que pueda comenzar una
comunicación privada, es necesaria otra transacción privada para distribuir las claves de
cifrado y descifrado correspondientes al remitente y al destinatario, respectivamente. Un
criptosistema de clave pública no necesita mensajeros privados; las claves se pueden
distribuir a través del canal de comunicación inseguro.
Dos usuarios también pueden establecer una comunicación privada a través de un
canal de comunicación inseguro sin consultar un archivo público. Cada usuario envía su
clave de cifrado al otro. Después, todos los mensajes se cifran con la clave de cifrado del
destinatario, como en el sistema de clave pública. Un intruso que escucha el canal no puede
descifrar ningún mensaje, ya que no es posible deducir las claves de descifrado a partir de las
claves de cifrado.
3
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Firmas
Si los sistemas de correo electrónico van a reemplazar al sistema de correo en papel existente
para las transacciones comerciales, debe ser posible "�rmar" un mensaje electrónico. El
destinatario de un mensaje �rmado tiene la prueba de que el mensaje proviene del
remitente.
Para implementar �rmas, debe implementarse el sistema criptográ�co de clave
pública con permutaciones de una sola dirección con puerta trasera (es decir, tener la
propiedadD, ya que el algoritmo de descifrado se aplicará a mensajes sin cifrar.
¿Cómo puede el usuario Bob enviar a Alice un mensaje "�rmado" M en un sistema
criptográ�co de clave pública? Primero calcula su "�rma" S para el mensaje M utilizando
DB:
S = DB(M).
Luego cifra S usando EA (para la privacidad) y envía el resultado EA(S) a Alice. No es
necesario que envíe M también; se puede calcular a partir de S.
Alice primero descifra el cifrado con DA para obtener S. Ella sabe quién es el
supuesto remitente de la �rma (en este caso, Bob); esto se puede proporcionar si es necesario
en texto plano adjunto a S. Luego extrae el mensaje con el procedimiento de cifrado del
remitente, en este caso EB (disponible en el archivo público):
M = EB(S).
Ahora ella posee un par mensaje-�rma (M, S) con propiedades similares a las de un
documento en papel �rmado. Bob no puede negar más tarde haber enviado a Alice este
mensaje, ya que nadie más podría haber creado S = DB(M). Alice puede convencer a un
"juez" de que EB(S) =M, por lo que tiene la prueba de que Bob �rmó el documento.
Método RSA
Para cifrar un mensaje M con el método presentado, utilizando una clave de cifrado pública
(e, n), procedemos de la siguiente manera. (Aquí e y n son un par de enteros positivos.)
4
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
1. Primero, representamos el mensaje como un entero entre 0 y n - 1. El propósito aquí
no es cifrar el mensaje, sino solo ponerlo en la forma numérica necesaria para el
cifrado.
2. Luego, cifre el mensaje elevándolo a la potencia de emódulo n. Es decir, el resultado
(el texto cifrado C) es el resto cuandoMe se divide por n.
3. Para descifrar el texto cifrado, eleve otro número d, nuevamente módulo n. Los
algoritmos de cifrado y descifrado E y D son así:
C ≡ E(M) ≡Me (mod n), para un mensaje M.
D(C) ≡ Cd (mod n), para un texto cifrado C.
.
Por lo tanto, la clave de cifrado es el par de enteros positivos (e, n). De manera similar, la
clave de descifrado es el par de enteros positivos (d, n). Cada usuario hace pública su clave
de cifrado y guarda la clave de descifrado correspondiente en privado. (Estos enteros deben
estar debidamente subíndice como en nA, eA y dA, ya que cada usuario tiene su propio
conjunto.
¿Cómo debe elegir sus claves de cifrado y descifrado si desea utilizar este
método?
1. Primero, calcule n como el producto de dos números primos p y q:
n = p · q
Estos primos sonprimos "aleatorios" muy grandes. Aunque hará que n sea público,
los factores p y q estarán efectivamente ocultos para todos los demás debido a la enorme
di�cultad de factorizar n. Esto también oculta la forma en que se puede derivar d de e.
2. Luego, elija el número entero d como un número aleatorio grande que sea
relativamente primo a (p - 1) · (q - 1). Es decir, veri�que que d satisfaga:
gcd (d, (p - 1) · (q - 1)) = 1
("gcd" significa "máximo común divisor").
3. El número entero e se calcula �nalmente a partir de p, q y d para ser el "inverso
multiplicativo" de d, módulo (p - 1) · (q - 1). Así tenemos
5
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
e · d≡ 1 (mod (p - 1) · (q - 1))
Demostramos en la siguiente sección que esto garantiza que se cumplen (1) y (2), es decir,
que E y D son permutaciones inversas.
Algoritmos
Cifrado y Descifrado e�ciente
El algoritmo descrito para la operación de cifrado (y descifrado) se llama "exponenciación
mediante cuadrados y multiplicaciones repetidas". El procedimiento requiere a lo sumo 2 ·
log2(e) multiplicaciones y 2 · log2(e) divisiones. El algoritmo es simple y se puede
implementar en chips de circuitos integrados especiales. La velocidad de cifrado para un
bloque no aumenta más rápido que el cubo del número de dígitos en n. Un ordenador de
alta velocidad puede cifrar un mensaje de 200 dígitos en unos segundos, mientras que el
hardware especializado sería mucho más rápido.
Cómo encontrar números primos grandes
Cada usuario debe elegir dos números aleatorios grandes, p y q, de forma privada para crear
sus propias claves de cifrado y descifrado. Estos números deben ser grandes para que no sea
factible computacionalmente factorizar n = p · q. Se recomienda usar números primos de
100 dígitos (decimales) para p y q, de modo que n tenga 200 dígitos.
Para encontrar un número primo "aleatorio" de 100 dígitos, se generan números
aleatorios de 100 dígitos (impares) hasta que se encuentre un número primo. Según el
teorema de los números primos, se probarán alrededor de (ln 10^100)/2 = 115 números
antes de encontrar un número primo.
Por último, para probar un número grande b con respecto a si es primo o no, se
recomienda el algoritmo "probabilístico" de Solovay y Strassen. Se debe considerar que este
algoritmo no prueba si un número es primo tratando de factorizarlo.
Para obtener protección adicional contra algoritmos so�sticados de factorización, p
y q deben diferir en longitud por algunos dígitos, tanto (p − 1) como (q − 1) deben contener
factores primos grandes, y gcd(p − 1, q − 1) debe ser pequeño.
6
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Cómo elegir d
Es muy fácil elegir un número d que sea relativamente primo a φ(n). Por ejemplo, cualquier
número primo mayor que max(p, q) servirá. Es importante que d se elija de un conjunto lo
su�cientemente grande para que un criptoanalista no pueda encontrarlo mediante
búsqueda directa.
Cómo calcular e de d y φ(n).
Para calcular e se una variación del algoritmo de Euclides para calcular el mayor común
divisor de φ(n) y d. Si e resulta ser menor que log2(n), comience de nuevo eligiendo otro
valor de d. Esto garantiza que cada mensaje cifrado (excepto M = 0 o M = 1) sufra algún
"envolvimiento" (reducción módulo n).
Seguridad del método: enfoques criptoanalíticos
La seguridad de un esquema de cifrado se prueba únicamente viendo si alguien puede
encontrar una forma de romperlo. El estándar NBS fue "certificado" de esta manera, ya que
IBM intentó durante diecisiete años sin éxito romper el esquema. Una vez que un método
ha resistido un ataque de este tipo, se puede considerar seguro para propósitos prácticos. Sin
embargo, existe controversia sobre la seguridad del método NBS.
Aunque la factorización de números grandes no es indudablemente difícil, es un
problema conocido que ha sido estudiado durante los últimos trescientos años por muchos
matemáticos famosos. Nadie ha encontrado aún un algoritmo que pueda factorizar un
número de 200 dígitos en un tiempo razonable. Se concluye que el sistema ya ha sido
parcialmente "certificado" por estos esfuerzos previos para encontrar algoritmos de
factorización e�cientes. Se exploran, sin embargo, posibles opciones para un plausible
ataque criptográ�co.
Factorizando n
Factorizar n permitiría a un criptoanalista enemigo "romper" el método. Los factores de n le
permiten calcular φ(n) y, por lo tanto, d. Afortunadamente, factorizar un número parece ser
mucho más difícil que determinar si es primo o compuesto. Se recomienda que n tenga
alrededor de 200 dígitos de longitud para una seguridad adecuada. Esta �exibilidad para
elegir la longitud de clave (y, en consecuencia, el nivel de seguridad) para adaptarse a una
aplicación particular es una característica no encontrada en muchos esquemas de cifrado
anteriores.
7
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Calculando φ(n) sin factorizar n
Si un criptoanalista pudiera calcular φ(n), podría descomponer n y, por lo tanto, romper el
sistema. Sin embargo, se concluye que romper el sistema al calcular φ(n) no es más fácil que
la factorización de n y que φ(n) es fácil de calcular solo si n es primo.
Determinar d sin factorizar n o calcular φ(n)
Elegir d de un conjunto lo su�cientemente grande es importante para evitar que un
criptoanalista lo encuentre mediante una búsqueda directa. Además, se argumenta que
encontrar d no es más fácil que factorizar n, ya que si se conoce d, n se puede factorizar
fácilmente. También, encontrar un valor d equivalente al valor secreto no es más fácil que
factorizar n, puesto que todos estos valores di�eren del mínimo común múltiplo de (p - 1) y
(q - 1), y encontrar uno de ellos permite factorizar n.
Calcular D de otra manera
Aunque el problema de "calcular raíces e-ésimas módulo n sin factorizar n" no es tan
conocido como el factorizar, se considera que es computacionalmente intratable. Es posible
que se pueda demostrar que cualquier método general para romper el esquema conduzca a
un algoritmo e�ciente de factorización. Sin embargo, no ha sido posible probar esta
conjetura.
Conclusiones
RSA es uno de los algoritmos criptográ�cos más resistentes con el paso de los años. Debido
a su fundamento matemático que se basa en la escasez de los números primos conforme
aumenta el tamaño de p y q, realizar un ataque criptográ�co a este sistema implicaría
encontrar un método e�ciente de factorización de N. Debido a lo anterior, RSA se
considera como un mecanismo criptográ�co probado y seguro en los sistemas
computacionales actuales. Sin embargo, existen cada vez opiniones más fuertes que
mencionan el riesgo latente que RSA enfrenta con la computación cuántica, la cual podría
proveer por primera vez una solución computacional mínimamente e�ciente al problema
de la factorización, por tanto, RSA podría verse quebrantado en las próximas décadas.
Conocer los fundamentos de este algoritmo resulta interesante debido a que es
posible observar el gran re�namiento que la criptografía tuvo con el pasar de los años. En la
actualidad, existen métodos con fundamentos aún más intrincados (curvas elípticas); y
8
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
aunque personalmente me resulta un tanto complicado poder entender a detalle el aspecto
matemático, observar su aplicación en diversos procesos en línea me ayuda a comprender un
poco más su modo de operación y la seguridad que proveen en la actualidad.
Referencias
Rivest, R.L, Shamir, A, Adleman, L. (1978). AMethod for Obtaining Digital
Signatures and Public-Key Cryptosystems. https://dl.acm.org/doi/10.1145/359340.359342
9
https://dl.acm.org/doi/10.1145/359340.359342