Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Método de encriptación basado en el algoritmo R.S.A. (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

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

Monografias.com

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

Monografias.com

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-

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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.

Monografias.com

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

Monografias.com

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.

Monografias.com

Tiempos de búsqueda sistemática a un millón de tentativas por segundo

Monografias.com

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.

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

Los bloques a cifrar son

Expresemos cada bloque como un número en base N=27

Monografias.com

Obtenemos el criptograma C con ayuda de la igualdad

Esto es

Monografias.com

Expresemos ci en base 27, teniendo en cuenta que se van a tener tres componentes

Luego el criptograma es QIAHOAFIAPJA

Monografias.com

Para desencriptar el mensaje utilizamos la igualdad

Haciendo el proceso inverso eligiendo bloques de tres letras se tiene que

Monografias.com

Obteniendo así el texto plano m: “CONGRESO”

Monografias.com

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)

Monografias.com

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)

Monografias.com

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

Monografias.com

Number Sieve Methods: resulta un algoritmo que corre en tiempo

Monografias.com

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

Monografias.com

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

Monografias.com

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í

Monografias.com

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.

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter