Ejemplo Se desea encriptar la frase “ESTE ES UN EJEMPLO DE CRIPTOGRAFIA SIMETRICA”. Se puede elegir la clave k (n, p), tomando n=6 y p la permutación
Aplicando la permutación obtenemos el criptograma siguiente
ESTE-E S-UN-E JEMPLO -DE-CR IPTOGR AFIA-S IMETRI CA—- El primer paso será dividir el texto plano en bloques de tamaño 6, rellenando los espacios con un guión. Esto es
Este sistema no es difícil de criptoanalizar, simplemente bastaría con tratar de encontrar un patrón y tener en cuenta las leyes del español TE-ESEUS-E-NMJLOEPE-CRD-TIGRPOIA-SFAEIRIMT-C–A-
Está compuesta de los criptosistemas conocidos como sistemas de clave pública.
A diferencia del sistema de clave privada, cada usuario i que participa en la comunicación, posee dos claves (ci ,di), donde
CRIPTOGRAFÍA ASIMÉTRICA
ci es la clave pública, la cual es utilizada por otro usuario j para enviarle un texto plano m a i en forma de criptograma.
di es la clave que sólo conoce el usuario i y le permite desencriptar el mensaje que le ha enviado el usuario j. CRIPTOGRAFÍA ASIMÉTRICA
Esta criptografía nace con el propósito de solucionar el inconveniente que tiene la simétrica, el cual radica en la distribución de la clave.
“Diffie – Hellman” proponen utilizar “funciones de un sentido” y así las claves se podrían dar en canales abiertos. CRIPTOGRAFÍA ASIMÉTRICA
CONDICIONES DE DIFFIE – HELLMAN Deber ser computacionalmente sencillo La obtención de claves y el proceso de encriptación. El proceso de descencriptación conociendo la clave secreta.
Debe ser computacionalmente imposible La obtención de la clave privada a partir de la pública. La obtención del texto plano conociendo el criptograma y la clave pública.
FUNCIONES DE UN SENTIDO Una función f se dice de un sentido si y = f (x) es de fácil cálculo conociendo x, mientras que el cálculo de x = f -1(y) es computacionalmente imposible.
Un ejemplo de una de tales funciones es la conocida como “función exponenciación modular”, la cual se define como sigue donde y p es un número primo lo suficientemente grande con k dígitos.
La complejidad computacional de esta función es
Mientras, que su función inversa conocida como “función logaritmo discreto” tiene complejidad de orden exponencial. El mejor conocido es de orden Esto muestra que cuando p es primo con más de 200 dígitos el cálculo de x es prácticamente imposible.
SISTEMA DE CLAVE PÚBLICA R.S.A Es un sistema criptográfico que cumple con las condiciones de Diffie – Hellman. Su seguridad se basa en la factorización de números compuestos como producto de primos. Además, permite el intercambio de claves secretas y firmar matemáticamente.
CRIPTOSISTEMA RSA Cada usuario i elige dos números primos p, q lo suficientemente grandes que mantiene secretos. La determinación de los números primos puede hacerse utilizando los tests de primalidad. 3. Se calcula n = p ·q y ?(n) = (p-1)(q-1) donde ? es la función de Euler.
A continuación el usuario elige un entero e primo relativo con ?(n) tal que
En la práctica se elige e primo directamente y mayor que p y q.
CRIPTOSISTEMA RSA
Otro método para hallar el mcd, es el algoritmo de Euclides, que evita factorizar ambos números. Dicho algoritmo corre en tiempo polinomial de O (log3?(n)).
Calcular un entero d, tal que y
CRIPTOSISTEMA RSA
Luego, con lo anterior las claves serán
Pública: P (e, n), conocida por todos los usuarios.
Privada: S (d), conocida sólo por quien desea desencriptar el mensaje
CRIPTOSISTEMA RSA
OBTENCIÓN DEL CRIPTOGRAMA Y PROCESO DE DESENCRIPTACIÓN Para encriptar un texto plano M, se utiliza la función
mientras que para desencriptar se utiliza la función
Estos dos procesos se basan en la exponenciación modular, el cual es un algoritmo que se puede implementar en tiempo polinomial de la longitud de la entrada
O(log 3 n)?O(k3),
donde n es la entrada y k es su longitud.
Si algún usuario desea descencriptar el criptograma, necesita conocer la clave privada, porque de no ser así, debe resolver la congruencia lo cual equivale a conocer ?(n) o una factorización de n que es un problema con el mismo grado de complejidad que el algoritmo discreto. SEGURIDAD DEL SISTEMA
SEGURIDAD DEL SISTEMA Además, también es necesario mantener secretos d, p, q ya que
Si se hace público d, cualquiera puede desencriptar.
Si se hace público p o q, entonces se conoce ?(n) y así, de conocemos d.
Tiempos de búsqueda sistemática a un millón de tentativas por segundo
IDENTIFICACIÓN DE MENSAJES Cada usuario posee un entero n tal que
donde N representa el tamaño del alfabeto y k, l representan el número de letras del bloque de entrada y salida respectivamente.
Así, todo mensaje M se puede representar numéricamente de la siguiente forma
De la misma forma C puede considerarse como
IDENTIFICACIÓN DE MENSAJES
Ejemplo Sea ? un alfabeto con N=27 letras, donde se ha identificado A=00, …, Z=26, []=27.
Sean p = 29 y q = 31, de ahí que n = 899 z = ? (n)=(p-1)(q-1)=840 Buscamos 1< e < 840 primo relativo con 840, sea e = 37. Buscamos d tal que e.d = 1 mod z, esto es d = 613
Así, la clave pública P(899,37) la clave privada S(613) 272 < 899 < 273, de ahí que se va a encriptar bloques de dos letras en bloques de tres letras. Sea m : “congreso” el texto plano. Utilizando el alfabeto ? se tiene la siguiente codificación
Los bloques a cifrar son
Expresemos cada bloque como un número en base N=27
Obtenemos el criptograma C con ayuda de la igualdad
Esto es
Expresemos ci en base 27, teniendo en cuenta que se van a tener tres componentes
Luego el criptograma es QIAHOAFIAPJA
Para desencriptar el mensaje utilizamos la igualdad
Haciendo el proceso inverso eligiendo bloques de tres letras se tiene que
Obteniendo así el texto plano m: “CONGRESO”
TESTS DE PRIMALIDAD Test de Solovay – Strassen
Sea n un número impar. n es primo si y sólo si n es pseudoprimo de Euler para todo a con MCD (a, n) =1. Este test tiene una complejidad computacional O (log3 n)
TESTS DE PRIMALIDAD Test de Miller (probabilístico)
Se dice que un número n impar es primo si y sólo si n es pseudoprimo fuerte para todo a con MCD (a, n) =1. Este test tiene una complejidad computacional O (log3 n)
Hasta el momento, no se conocen algoritmos de factorización de enteros que tienen un tiempo de complejidad de orden polinomial.
1. Index Calculus Methods: este da un algoritmo que corre en tiempo FACTORIZACIÓN
Number Sieve Methods: resulta un algoritmo que corre en tiempo
Algoritmo clásico para descomponer un número en factores primos Dado un número natural n, el costo computacional que tiene dicho algoritmo para hacer su descomposición en factores primos es de
EXPONENCIACIÓN MODULAR El problema radica en calcular mn mod z, para n, m enteros suficientemente grandes. La solución se obtiene desarrollando un algoritmo divide y vencerás junto con las siguientes propiedades de aritmética modular
EXPONENCIACIÓN MODULAR Luego el algoritmo divide y vencerás será
Si n es par, hacemos n =2k1, donde k1? N. Así
Si n es impar, hacemos n =2k+1, donde k ? N. Así
REFERENCIAS The discrete log problem. Chris Studholme. Article. Introduction to Cryptography. Victor Shuop. Lecture. Una introducción a la criptografía. Mario Merino Martínez – Monografía. Aritmética modular y criptografía. Artículo. Criptografía – José Ángel de Bustos Pérez. Artículo. Computational Number Theory. Chapter 7.
 Página anterior | Volver al principio del trabajo | Página siguiente  |