elparaiso.mat.uned.es

¡Pulsa Aquí!

LO DIJO...

Poincaré  
 
Todo saber tiene de ciencia lo que tiene de matemática.
 
El Paraíso de las Matemáticas - Criptotaller ~ Cifrado RSA (II)
.: Criptotaller :.
 
Cifrado RSA (II)

    "Siempre fuisteis enigmático
y epigramático y ático
y retórico y simbólico
y aunque os escucho flemático
sabed que a mi lo hiperbólico
no me resulta simpático"

La venganza de Don Mendo, Pedro Muñoz Seca.

    Para entender porque RSA constituye un sistema útil de clave pública, notemos en primer lugar que cualquier individuo puede encontrar dos grandes primos p y q con, por ejemplo 100 dígitos, en pocos segundos de ordenador. Se pueden elegir simplemente enteros impares de 100 dígitos aleatoriamente y el teorema de distribución de los números primos nos asegura que la probabilidad de que dicho número sea primo es aproximadamente de 2/(log 10 ^100) lo que quiere decir uno de cada 115 en promedio. Un test de tipo probabilístico nos permitirá descartar los compuestos muy rápidamente.

    *Puedes encontrar más cosas sobre primos incluyendo una pequeña calculadora aquí.

    Una vez elegidos los primos p y q necesitamos un exponente e, que verifique mcd(e, fi(pq))=1 como se explico en el artículo anterior. Una forma posible es elegir un primo e mayor que p y q . De cualquier modo debe cumplirse que 2^e>n=pq para que sea imposible obtener el texto en claro P calculando simplemente la raíz de índice e del texto cifrado C=(P^e (mod n). Con la condición antes citada cualquier P (excepto 0 y 1) sufrirá una reducción módulo n.

    La exponenciación modular es también rapidísima incluso cuando el módulo, el exponente y la base tienen 200 dígitos. Con el algoritmo de Euclides encontramos rápidamente el inverso d del exponente e módulo fi(n) cuando p y q son conocidos pues en este caso fi(n)=fi(pq)=(p-1)(q-1).

    Por contra, el conocimiento de la clave de cifrado (e, n) no conduce al de la clave de descifrado. En efecto, para hallar d, un inverso de e módulo fi(n) necesitamos encontrar fi(n) y esto NO es más sencillo que factorizar n, lo que parece ser un problema intrínsecamente costoso computacionalmente hablando (ver mi artículo sobre cifrado exponencial).

    Aunque no se ha probado que sea imposible romper un cifrado RSA sin factorizar n, aún nadie ha descubierto una alternativa pues los métodos existentes son en general equivalentes en complejidad a factorizar un número entero.

    Unas precauciones extras para escoger p y q evitando así métodos de factorización especiales :

  • p-1 y q-1 deben tener grandes factores primos.
  • mcd(p-1, q-1) debe ser "pequeño".
  • p y q deberían tener un número similar de dígitos.

    Los sistemas de clave pública se utilizan también para firmar mensajes. El uso de firmas digitales hace que el receptor de un mensaje esté seguro de que realmente partió del emisor anunciado. Se utilizan en el correo electrónico y en transacciones bancarias. Veamos el proceso matemático involucrado:

    Digamos que i manda un mensaje a j , lo primero que hará será calcular S=Di(P)=P^di(mod ni) donde (di, ni) es la clave privada de i . Entonces si nj>ni se forma C=Ej(S)=S^ej(mod nj) y cuando nj es menor que ni el emisor parte S en bloques de tamaño menor que nj y cifra usando ej.

    Para descifrar j utiliza primero Dj(C)=Dj(Ej(S))=S y a continuación obtiene el texto en claro así Ei(S)=Ei(Di(P))=P donde la última identidad se sigue de que (P^di)^ei=P^(di.ei)=P (mod ni) ya que di.ei=1 (mod fi(ni)).

    La combinación de texto en claro P y la versión firmada S convence a j de que el mensaje proviene de i, y éste no puede negar haberlo enviado. Resumiendo, todo el sistema RSA se basa en lo fácil que es encontrar primos frente a lo difícil que es factorizar un entero.

Area On-Line
  Todo tipo de material, para disfrutar de él completamente On-Line, sin necesidad de descargar archivos ni tener que andar descomprimiendo estos. No te olvides de pasar por el Diccionario, y las secciones Origami y Geointeractiva. Son de lo más interesante.

Criptotaller

Criptografía (clásica y moderna), criptoanálisis (primos, primos de Mersenne, etc.) y otras técnicas.

Material para descargar

Código Fuente C

Método Hill
Método Jefferson
Exponenciación Modular
Cálculo números primos
Test de Lucas-Lehmer
Factores num. Mersenne
Verificación FIPS 140.2
Teorema chino del resto
+ Códigos Fuente C

Código Fuente Python

Generación de claves

Artículos

La máquina Enigma
Criptografía y seguridad
    M. J. Lucena
Seguridad Informática
   y Criptografía PDF PPT
    J. Ramió
Criptografía clásica PDF
    J. Ramió

Programas
Cripto1 ZIP 2391 KB
    J. L. Rubio

Enlaces

Página personal de Jaime Suárez Martínez, colaborador de esta sección.

Munitions, colección de programas para Linux.

Kriptopolis, toda una referencia en castellano.

Ciphersaber

Criptonomicón: la página de Gonzalo Alvarez Marañón.

Página de Chris Caldwell, una página bien elaborada sobre números primos.

Colección de links de Peter Gutmann.

www.gnupg.org es la página original de GPG, un programa libre alternativo a PGP.

Martes, 19 / 11 / 2019
   BUSCADOR
 

   TU CORREO
Usuario
Contraseña

   MATRACAS
Lista de correo gratuita
.: Chismes de Adán y Eva :.
Adios a Elisenda Fo...
WolframAlpha: El mo...
WIRIS para Mac...
Third CEU Summersch...
¡Más y más actualiz...
Cerca de 500 MB de ...
Ha llegado el momen...
WIRIS, matemáticas ...
El Universo Matemát...
Segundas Jornadas d...
Los Elementos de Eu...
VI Semana de la Cie...
Tras varios meses d...
¡Chiflados por los ...
Otro verano más, to...

 

Todos los derechos reservados. El Paraíso de las Matemáticas 2015Información Legal Política de PrivacidadAyudaEmail