algoritmo para un sistema criptogrÁfico basado … · para autentificar a los dos usuarios que...
TRANSCRIPT
INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE INGENIERÍA
MECÁNICA Y ELÉCTRICA
SECCIÓN DE ESTUDIOS DE POSGRADO E INVESTIGACIÓN
ALGORITMO PARA UN SISTEMA
CRIPTOGRÁFICO BASADO EN MATRICES
SOBRE CURVAS ELÍPTICAS
T E S I S
QUE PARA OBTENER EL GRADO DE MAESTRO EN CIENCIAS EN
INGENIERÍA DE TELECOMUNICACIONES
PRESENTA:
ING. JOSÉ ANTONIO LÓPEZ TOLEDO
DIRECTOR DE TESIS:
DR. HÉCTOR OVIEDO GALDEANO
México D.F. Enero 2011
IPN ESIME-ZACATENCO
i
ÍNDICE
RELACIÓN DE TABLAS Y FIGURAS…………………………………………………...iv
RESUMEN ............................................................................................................................. v
ABSTRACT ........................................................................................................................... v
PLANTEAMIENTO DEL PROBLEMA ............................................................................. vi
OBJETIVO ........................................................................................................................... vii
JUSTIFICACIÓN ................................................................................................................. vii
INTRODUCCIÓN ............................................................................................................... viii
PRÓLOGO ............................................................................................................................. x
CAPÍTULO I
FUNDAMENTOS TEÓRICOS
1.1. CRIPTOGRAFÍA ........................................................................................................ 1
1.1.1. CRIPTOSISTEMA ............................................................................................................ 2
1.1.2. CRIPTOANÁLISIS .......................................................................................................... 4
1.1.3. CRIPTOGRAFÍA CLÁSICA ............................................................................................ 6
1.2. TEORÍA DE NÚMEROS............................................................................................ 7
1.2.1. ARITMÉTICA MÓDULO ................................................................................................ 7
1.2.2. NÚMEROS PRIMOS ....................................................................................................... 9
1.2.3. INVERSO MULTIPLICATIVO DE UN MÓDULO ..................................................... 11
1.2.4. RESIDUOS CUADRÁTICOS ........................................................................................ 13
1.2.5. TEORÍA DE GRUPOS ................................................................................................... 15
1.3. TEOREMA DE CAYLEY-HAMILTON.................................................................. 15
IPN ESIME-ZACATENCO
ii
CAPÍTULO II
CRIPTOGRAFÍA DE CURVAS ELÍPTICAS
2.1. ALGORITOS DE EXPONENCIACIÓN .................................................................. 17
2.2. PROBLEMAS DE LOS LOGARITMOS ................................................................. 17
2.2.1. PROBLEMA DE LOS LOGARITMOS DISCRETOS .................................................. 17
2.2.2. PROBLEMA DE LOS LOGARITMOS DISCRETOS EN CURVAS ELÍPTICAS ...... 18
2.3. CRIPTOGRAFÍA DE CURVAS ELÍPTICAS ......................................................... 18
2.3.1. OPERACIONES SOBRE UNA CURVA ELÍPTICA .................................................... 20
2.3.2 GENERAR PARES DE PUNTOS ................................................................................... 24
2.3.3 ORDEN DE UN PUNTO EN ECC .................................................................................. 32
2.4. PROTOCOLO DIFFIE-HELLMAN ......................................................................... 35
2.5. CRIFRADO DE MENEZES–VANSTONE CON CURVAS ELIPTICAS .............. 35
2.6. CIFRADO DE ELGAMAL CON CURVAS ELÍPTICAS ....................................... 37
CAPÍTULO III
CONSTRUCCIÓN DEL SISTEMA CRIPTOGRÁFICO
3.1. FORMAS PARA AUMENTAR LA SEGURIDAD ................................................. 39
3.2. DESCRIPCIÓN DEL SISTEMA. ............................................................................. 39
3.3. CRIPTOANÁLISIS ................................................................................................... 41
3.4. INTERCAMBIO DE LLAVE DIFFIE-HELLMAN................................................. 43
3.5. CIFRADO DEL MENSAJE ...................................................................................... 44
3.6. NIST. ......................................................................................................................... 45
IPN ESIME-ZACATENCO
iii
CAPÍTULO IV
DESARROLLO DEL ALGORITMO
4.1. FORMACIÓN DE LA LLAVE PRIVADA.............................................................. 46
4.2. CONSTRUCCIÓN DE LOS VECTORES PÚBLICOS A TRANSMITIR .............. 47
4.3. ALGORITMO DIFFIE-HELLMAN ......................................................................... 48
4.4. CIFRADO DEL MENSAJE CON UNA MATRIZ .................................................. 51
CONCLUSIONES ................................................................................................................ 61
TRABAJOS FUTUROS ....................................................................................................... 62
TRABAJOS DERIVADOS DE LA TESIS ......................................................................... 62
BIBLIOGRAFÍA .................................................................................................................. 80
APÉNDICE A. Algoritmo de Menezes-Vastone ................................................................ 82
APÉNDICE B. Obtención de la Matriz Privada A .............................................................. 83
APÉNDICE C. Criptoanálisis del sistema construido ........................................................ 84
APÉNDICE D. Ejemplo de un criptoanálisis para el sistema propuesto. ........................... 88
APÉNDICE E. Recomendaciones de la NIST sobre campos primos ................................. 96
APÉNDICE F. Curva elíptica con a=1, b=1 y p=23 .......................................................... 97
APÉNDICE G. Código ASCII ............................................................................................ 98
APÉNDICE H. Algunos puntos de la curva elíptica donde a=7, b=29 y p=65521 ....... 100
APÉNDICE I. Diagrama del sistema criptográfico propuesto ......................................... 103
APÉNDICE J. Diagramas de flujos del sistema criptográfico......................................... 105
APÉNDICE K. Programa del sistema criptográfico. ........................................................ 121
APÉNDICE L. Detección y corrección de errores ............................................................ 133
IPN ESIME-ZACATENCO
iv
RELACIÓN DE TABLAS Y FIGURAS
Tabla 1.1. Alfabeto de cifrado del César. .............................................................................. 7
Tabla 1.2. Algoritmo de Euclides. ....................................................................................... 10
Tabla 1.3. Algoritmo de Euclides Extendido para encontrar el gcd(4864, 3458). .............. 13
Tabla 1.4. Cuadrados en . ............................................................................................... 14
Tabla 2.1. Construcción de valores de la ECC empleando el criterio de Euler y el símbolo
de Legendre. ......................................................................................................................... 25
Tabla 2.2. Valores de y para el par de puntos de ECC. ....................................................... 26
Tabla 2.3. Pares de puntos de (2.10) [12]. ........................................................................... 27
Tabla 2.4. Puntos generados dado un punto de ECC. .......................................................... 32
Fig. 1.1. Transmisión de mensajes utilizando un criptosistema asimétrico [3]. ..................... 3
Fig. 1.2. Conversación entre dos usuarios [6]. ....................................................................... 4
Fig. 1.3. Valores que intervienen en la descripción del módulo [7]. ...................................... 8
Fig. 2.1. Curva Elíptica. ....................................................................................................... 19
Fig. 2.2. Operaciones de las curvas elípticas a) P + P = …... ........................................ 22
Fig. 2.2. Operaciones de las curvas elípticas ........................................................... 22
Fig. 2.2. Operaciones de las curvas elípticas c) P + ( ) = 0 .............................................. 23
Fig. 2.2. Operaciones de las curvas elípticas d) P + Q = 0. .................................................. 23
Fig. 2.2. Operaciones de las curvas elípticas e) P + Q = R ................................................. 24
Fig 4.1. ................................................................................................. 52
Fig. 4.2. Gráfica de puntos de la curva elíptica a= 9, b = 7 y p =2011…………………..60
IPN ESIME-ZACATENCO
v
RESUMEN
La única constante en el mundo de la seguridad de la información, es la inseguridad,
cualquier sistema de comunicación de red basa su protección de información en algoritmos
planteados matemáticamente. El sistema criptográfico desarrollado en la tesis utiliza
cifrado asimétrico, es decir, que se tienen dos llaves, una pública y la otra privada, este
sistema criptográfico se construye con el uso de la técnica de curvas elípticas junto con
matrices.
La finalidad del sistema criptográfico construido es lograr una comunicación segura entre
dos usuarios. Lo que se hace es generar la llave pública y privada, para obtener la primera
llave se eligen números arbitrarios pertenecientes al campo empleado en el sistema y para
generar la segunda llave se ocupa el teorema de Cayley Hamilton junto con la llave pública.
Para autentificar a los dos usuarios que intercambiaran mensajes se utiliza el algoritmo de
Diffie Hellman, estos mensajes emplean el cifrado de ElGamal, con todas las variantes que
intervinieron en la construcción del sistema y para la verificación de esté. Se programó en
Matlab y se comprobó el correcto funcionamiento del algoritmo así como la comunicación
existente entre los dos usuarios.
ABSTRACT
The only constant in the world of information security is the insecurity; any network
communication system builds the protection of its information on mathematical algorithms.
The cryptographic system developed in this thesis uses asymmetric encryption, that is, it
has two keys, one public and one private, the cryptographic system is constructed using the
technique of elliptic curves with matrices.
The purpose of the cryptographic system is built to achieve a secure communication
between two users. What is done is to generate public and private key to obtain the first key
is chosen arbitrary numbers belonging to the field used in the system and to generate the
IPN ESIME-ZACATENCO
vi
second key concern to the Cayley Hamilton theorem together with the public key. To
authenticate the two users to exchange messages using the Diffie Hellman algorithm, these
messages use the ElGamal encryption with all the variants involved in building the system
and is checking. Was programmed in Matlab and found the proper functioning of the
algorithm and the communication between two users.
PLANTEAMIENTO DEL PROBLEMA
El problema fundamental que enfrentan las redes de comunicaciones es la seguridad de la
información. No existe ningún algoritmo que asegure que la transmisión dentro de un
sistema de comunicaciones sea cien por ciento confiable. A pesar de esto la sociedad
realiza actividades vía internet, por ejemplo el intercambio de información personal desde
imágenes privadas hasta datos financieros. Los mecanismos desarrollados para proteger la
privacidad en las redes se fundamentan en sistemas criptográficos para ocultar la
información ante los intrusos. Sin embargo, al avanzar la tecnología ésta también es usada
por los intrusos para romper la seguridad de los sistemas, por lo que cada vez se desarrollan
sistemas criptográficos basados en matemáticas más complejas. Con la aparición de las
computadoras las técnicas de criptografía clásica para el cifrado de información presentan
vulnerabilidad por lo que el cifrado por flujo y bloques es utilizado para contrarrestar esta
situación, pero otra técnica que se ha empezado a utilizar es la criptografía de curvas
elípticas para el cifrado de mensajes en donde el tamaño de las llaves es pequeña
comparada con otras técnicas y está fue elegida para solucionar problemas de seguridad en
las comunicaciones. El cifrado de las curvas elípticas recae en la solución del problema de
los logaritmos discretos en curvas elípticas.
IPN ESIME-ZACATENCO
vii
OBJETIVO
Propuesta de un algoritmo para un sistema criptográfico basado en matrices sobre curvas
elípticas para el intercambio de información entre dos usuarios.
JUSTIFICACIÓN
El impacto que ha tenido Internet en la vida de las personas es enorme, es un medio global
que permite de una manera fácil la comunicación en todo el mundo. Todas las actividades
que se pueden realizar vía Internet implican privacidad como son: datos personales en una
red social, envío de e-mails o el manejo de dinero (transferencias electrónicas, compras,
etc), estos deben de contar con los mecanismos suficientes para que la información sea
segura, pero esto es difícil ya que siempre habrá interesados en violar esta seguridad, por lo
que la construcción de estos mecanismos es un proceso continuo. No hay un sistema de
comunicación que sea cien por ciento seguro por tiempo indeterminado.
Cualquier tipo de red ya sea alambrada o inalámbrica es propensa a los ataques de intrusos
ya sea para provocar un daño o solamente por diversión. Las redes inalámbricas (celular,
BlueTooth, WiMAX, etc.) presentan mayor vulnerabilidad que las alambradas, entre otras
cosas debido a la movilidad y a que la señal viaja por el espacio libre donde cualquier
intruso tiene acceso a dicha señal.
La aportación en este trabajo consiste en la construcción del sistema criptográfico así como
de la programación para verificar el correcto funcionamiento de éste, los beneficios que
ofrece es lograr una comunicación de información segura entre usuarios con el empleo de
llaves tanto pública como privada éstas comunicaciones pueden ser por ejemplo las
mencionadas en los párrafos anteriores. Otro beneficio es al usar matrices se puede generar
n-tuplas de puntos lo que reduce el tiempo de cálculo puesto que a partir de un punto se
pueden calcular los demás por último el sistema puede utilizar campos primos definidos por
la NIST.
IPN ESIME-ZACATENCO
viii
INTRODUCCIÓN
En la publicación del periódico la Jornada [1], se informa que en México 32.8 millones de
personas tienen acceso a Internet, lo que representa un aumento de 20.6% con relación a lo
registrado en 2009, de acuerdo con la Encuesta en Hogares sobre Disponibilidad y uso de
las Tecnologías de la Información. Respecto a la conectividad, INEGI y COFETEL señalan
que 6.3 millones de hogares cuentan con conexión a Internet, para representar 22.2% del
total en México. Cada vez Internet toma mayor importancia, esto para acercar a los usuarios
a los servicios que ofrece. Sin embargo el 5.0% de los usuarios de Internet, es decir, un
millón 629 mil 150 personas, declaró haber comprado o pagado algo en línea por lo que el
porcentaje de personas que realizan una transferencia electrónica es mínimo, esto debido a
las inseguridad de las redes de comunicaciones.
Son muchos los casos notificados de ataques a las redes cibernéticas por los llamados
hackers. Un ejemplo es el del joven de secundaria entre los 15 y 16 años de edad que logró
ingresar en las computadoras del Pentágono en Washington. Al cuestionar al joven los
agentes de FBI se dieron cuenta que tenía un cómplice, un compañero de clase del colegio
secundario Cloverdale High School, quien lo ayudaba a planear sus incursiones
cibernéticas. Otro caso es el de Gary McKinnon, hacker Británico acusado por los E.U. de
haber perpetrado “el mayor ataque informático militar de todos los tiempos”, quien se
introdujo ilegalmente a 100 redes y más de 300 computadores de la NASA, el Ejército, la
Marina, el Departamento de Defensa y la Fuerza Aérea Estadounidense, dañando la red
informática de defensa que estuvo fuera de servicio por casi una semana, puso en jaque los
sistemas militares, robando cientos de contraseñas, eliminó 1,300 cuentas de usuario. Si es
procesado puede alcanzar hasta 70 años de cárcel.
A principios de Febrero del 2010 John Chipman, director del Instituto Internacional de
Estudios Estratégicos (IISS por sus siglas en inglés) informó que “con el uso de
computadoras, una potencia extranjera puede inutilizar la infraestructura de un país,
atacar la integridad de los datos militares internos de otra nación, intentar confundir sus
transacciones financieras o lograr cualquiera de sus otros posibles objetivos”. Esto es, un
IPN ESIME-ZACATENCO
ix
ataque cibernético coordinado y masivo, y no el clásico lanzamiento de misiles, puede
marcar el comienzo de las guerras en el futuro.
Uno de los sucesos que ha causado gran impacto en el país es el Wikileak. En el periódico
la Jornada [2] se menciona que se han filtrando más de 250 mil comprometedores cables
diplomáticos estadunidenses. A las corporaciones no les conviene la difusión de este tipo de
información puesto que es confidencial para el país, una forma de evitar la difusión es
retirar los apoyos económicos a la organización de libertad de información (Wikileaks).
Hackers cibernéticos anónimos han desestabilizado Wikileaks, pero han surgido sitios para
que se conozcan las filtraciones más recientes. Con todo esto eventos se muestra que las
comunicaciones de redes presentan alguna inseguridad por lo que cada vez se deben
desarrollar sistemas criptográficos basados en matemáticas más complejas.
IPN ESIME-ZACATENCO
x
PRÓLOGO
El presente trabajo tiene como finalidad lograr un intercambio de información segura entre
dos usuarios para esto se propone un sistema criptográfico que emplea matrices y curvas
elípticas.
Esta tesis está conformada por cuatro capítulos:
En el Capítulo I se abordan los fundamentos teóricos necesarios para el desarrollo del
trabajo como son los conceptos de criptografía simétrica y asimétrica, introducción a la
teoría de números, Teorema de Cayley-Hamilton.
En el Capítulo II se explica cómo obtener los puntos de una curva elíptica utilizado la
ecuación de Weierstrass, ya sea a partir de un punto dado o sin conocer ningún punto de la
curva. Con el criterio de Euler y el símbolo de Legendre se distinguen los puntos que son
de la curva de los que no pertenecen a ella. Se establecen las operaciones entre puntos de la
curva elíptica como son la multiplicación, suma, etc. Se explican los procesos de Diffie-
Hellman y de ElGamal.
En el Capítulo III se describe la construcción del sistema criptográfico, que consiste en la
creación de la matriz de clave pública y la construcción de la matriz de clave privada. Se
describe un criptoanálisis. Se establecen los procesos de Diffie-Hellman y de ElGamal con
matrices y curvas elípticas.
En el Capítulo IV se desarrolla el algoritmo del sistema criptográfico en Matlab con un
modelo de números no tan grandes a modo de laboratorio donde se observa el
comportamiento del algoritmo propuesto.
IPN ESIME-ZACATENCO
1
CAPÍTULO I
FUNDAMENTOS TEÓRICOS
1.1. CRIPTOGRAFÍA
La palabra criptografía según el Diccionario de la Real Academia, proviene de la unión de
los términos (del griego kryptos, “ocultar”, y grafos, “escribir”) que es: “Arte de escribir
con clave secreta o de un modo enigmático”. Se ha convertido en una técnica que trata
sobre la protección de la información. Hay dos personajes muy importantes para la
criptografía, uno de ellos fue Claude Shannon quien en su trabajos de “A Mathematical
Theory of Communication” (1948) y “Communication Theory of Secrecy Systems” (1949),
sienta las bases de la Teoría de la Información y de la Criptografía. El segundo personaje en
realidad es la pareja formada por Whitfield Diffie y Martin Hellman quienes en 1976
publicaron “New directions in Cryptography”, donde introdujeron el concepto de
Criptografía Asimétrica, lo que permite revolucionar nuevas investigaciones para lograr
una mayor seguridad y eficiencia para los sistemas criptográficos.
Hay códigos que se encargan de cifrar y descifrar la información con la única finalidad de
proporcionar una eficiencia en cuanto a la seguridad, es decir, garantizar el secreto en la
comunicación entre dos usuarios. Como se citó anteriormente esto es de lo que se encarga
la criptografía. También esta ciencia asegura que la información que se envía es auténtica
en el doble sentido que el remitente sea quien dice ser y que el mensaje cifrado no haya
sufrido modificaciones; las técnicas que se utilizan para romper los códigos de cifrado son
conocidas como criptoanálisis, la agrupación de este término con la criptografía, a pesar de
que no está reconocido en el diccionario es denominado criptología [3], [4].
IPN ESIME-ZACATENCO
2
1.1.1. CRIPTOSISTEMA
Un criptosistema es un sistema que toma información legible para convertirla en
información no legible, o no entendible, y podemos definirlo como una quíntupla (M, C,
K, E, D) [4].
Todo criptosistema para que sea válido debe de cumplir con la siguiente condición:
( ( ))k kD E m m
(1.1)
En donde en la expresión (1.1) se tiene un mensaje m, al cifrarse se emplea una clave k y al
momento de desencriptarlo con la misma clave k, se debe obtener el mensaje original m.
M representa el conjunto de todos los mensajes sin cifrar (lo que se denomina texto
claro, o plaintext).
C representa el conjunto de todos los posibles mensajes cifrados, o criptogramas.
K representa el conjunto de claves que se pueden emplear en el criptosistema.
E es el conjunto de transformaciones de cifrado que se aplica a cada elemento de M
para obtener un elemento de C.
D es el conjunto de transformaciones de descifrado, análogo a E.
Se tienen dos tipos fundamentales de criptosistemas: los simétricos o de clave privada y los
asimétricos o de llave pública. El primero emplea la misma clave k tanto para cifrar como
para descifrar y el criptosistema asimétrico, emplea una doble clave (kp; kP) en donde kp es
la clave privada y kP se conoce como clave pública, las cuales una de ellas sirve para la
transformación E de cifrado y la otra para la transformación D de descifrado (véase
Fig.1.1).
IPN ESIME-ZACATENCO
3
Fig. 1.1. Transmisión de mensajes utilizando un criptosistema asimétrico [3].
En la Fig. 1.1 el usuario B envía al usuario A su clave pública, KP. Después el usuario A
codifica el mensaje y envía al usuario B el criptograma ( )pKE m y por último el usuario B
decodifica el criptograma empleando la clave privada Kp.
Los criptosistemas simétricos se pueden clasificar en dos tipos: cifrados por bloque y
cifrados por flujo.
Cifrado por bloque. En donde el mensaje que se codifica estará dividido en bloques del
mismo tamaño, a cada uno de ellos se le aplicarán operaciones complejas como
sustituciones, transposiciones.
Los cifradores de flujo son algoritmos que convierten el texto en claro en texto cifrado bit
a bit. Este tipo de cifrado funciona bien con datos en tiempo real como voz y video, donde
en un momento sólo se conocen pequeñas partes de los datos.
IPN ESIME-ZACATENCO
4
1.1.2. CRIPTOANÁLISIS
El criptoanálisis es el descifrado de los criptogramas por análisis y deducción, sin poseer
los conocimientos previos de la clave. El descubrimiento de un algoritmo secreto de cifrado
no se considera criptoanálisis ya que los algoritmos siempre son conocidos.
Se puede llevar a cabo el proceso del criptoanálisis estudiando grandes cantidades de pares
(mensaje, criptograma) generados con la misma clave. El mecanismo que se emplee para
obtenerlos es indiferente y puede ser el resultado de escuchar un canal de comunicaciones,
o de la posibilidad de que el objeto del ataque responda con un criptograma cuando se le
envíe un mensaje. Si el sistema presenta una seguridad débil, será de menor complejidad
obtener la clave empleada. Todas las técnicas que buscan exhaustivamente una clave se
denominan de fuerza bruta.
Fig. 1.2. Conversación entre dos usuarios [6].
En la Fig. 1.2 se observa que Bob y Alicia tienen una conversación y Darth es la persona
que intercepta la información, en donde él puede realizar ataques pasivos o activos, un
ataque pasivo es cuando se analiza el tráfico para poder leer y observar el contenido de la
información pero sin alterar la conversación de Bob y Alicia, sin embargo un ataque activo
es capaz de remplazar, modificar el mensaje y hasta de hacerse pasar por la persona.
IPN ESIME-ZACATENCO
5
Con la descripción anterior, para lograr una comunicación segura [7], [8] se debe de tener
en cuenta lo siguiente.
1. Confidencialidad. Es la protección de los datos transmitidos de los ataques pasivos,
es decir, que solamente las personas autorizadas (en nuestro ejemplo de la Fig. 1.2
son Bob y Alicia) verán el mensaje y para el intruso éste será ilegible. Otro aspecto
de la confiablidad es la protección del flujo de tráfico a partir del análisis.
2. Integridad de datos. Nos indica que los datos del mensaje no han sido alterados por
medios no autorizados, es decir, que el flujo del mensaje no ha sido modificado por
Darth, lo que nos dice que el mensaje de Bob es correcto y que puede comunicarse
con Alicia de una forma segura.
3. Autentificación de datos de origen. El usuario Alicia (destino) será capaz de
verificar que los datos de Bob (remitente) fueron emitidos por él.
4. Entidad de autentificación. Corroborará la identidad de una entidad, Alicia debe
estar convencida de la identidad de Bob.
5. No repudio. Permite probar la participación de las partes que intervienen en la
comunicación, así cuando se envía un mensaje el receptor puede probar que es el
supuesto emisor quien envió tal mensaje y viceversa.
Todo sistema que almacene, procese o transmita información debe de cumplir con las
siguientes condiciones.
Debe de preservar la información frente a alteraciones, debidas a fallos en el
software o en el hardware o provocadas por agentes externos (interrupciones en el
suministro eléctrico o por los propios usuarios entre otros).
Debe evitar accesos no autorizados tanto al sistema como a su contenido.
El sistema debe garantizar que la información esté disponible cuando sea necesario.
IPN ESIME-ZACATENCO
6
Estos tres requerimientos están contemplados en los conceptos de integridad,
confidencialidad y disponibilidad de la información respectivamente, y son los que hacen
que podamos considerar seguro a un sistema.
Todo el análisis que se realiza en un criptoanálisis es con por medio de procesos
estocásticos. La Fig. 1.2 puede ser explicado por medio de probabilidades en donde el
Darth es el que trata de filtrarse en la conversación y de que la probabilidad de que pueda
debe de ser mínima, esto garantizará que el sistema utilizado para intercambiar información
es segura.
1.1.3. CRIPTOGRAFÍA CLÁSICA
Los sistemas de cifrado anteriores a la Segunda Guerra Mundial fueron considerados como
clásicos. Con la aparición de las computadoras estos sistemas se hicieron vulnerables,
perdieron su eficiencia.
Los tres principales sistemas criptográficos empleados en ese tiempo fueron transposición,
sustitución y el de ocultación.
Método de transposición. Se modifica el orden natural de las letras, silabas o palabras que
se encuentra en el mensaje. Un ejemplo de este método es la cifra de escítalo que consta de
un rodillo de longitud y grosor determinados en donde el cifrado se basaba en la alteración
del mensaje original introduciendo símbolos innecesarios que desaparecían al enrollar el
mensaje en un rodillo. Si se interceptaba el mensaje era muy difícil descifrarlo si no se
conocía el grosor y la longitud del rodillo.
Método de sustitución. Consiste en remplazar por otros los símbolos del mensaje sin alterar
su orden, en estos se encuentran los cifrados monoalfabéticos y los cifrados polialfabéticos.
Los cifradores monoalfabéticos son los que establecen una única función de sustitución
para todos los símbolos dentro de un mensaje, es decir, si al símbolo A le corresponde el
IPN ESIME-ZACATENCO
7
símbolo D, esta correspondencia se mantiene para todo el mensaje. Un claro ejemplo es el
algoritmo de Cesar [6] el cual aplica un desplazamiento constante de tres caracteres al texto en
claro, de forma que el alfabeto de cifrado es el mismo que el alfabeto del texto en claro pero
desplazado 3 espacios hacia la derecha módulo n.
Tabla 1.1. Alfabeto de cifrado del César.
Alfabeto A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
Cifrado D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z A B C
Utilizando la Tabla 1.1. podríamos cifrar los mensajes. A modo de ejemplo un mensaje
claro “HOLA A TODOS” en donde el texto cifrado es: KRND D WRGRV.
Para los cifradores polialfabéticos, es cuando se implementan múltiples alfabetos. Un
ejemplo es el cifrado de Vigenère [8] en las cartas del 6 de noviembre de 1824 de José M.
Michelena ministro plenipotenciario de México en Inglaterra al ministro de Relaciones
Exteriores de México.
Métodos de ocultación. Incluyen aquellos procedimientos en los que el remitente transmite el
contenido del mensaje de forma oculta o disfrazada. En consecuencia, este sistema abarca todas
las artimañas empleadas a lo largo de la historia para conseguir que un criptograma sea leído
únicamente por el destinatario, impidiendo su comprensión a quien no le ha sido enviado.
1.2. TEORÍA DE NÚMEROS
1.2.1. ARITMÉTICA MÓDULO
La aritmética modular es una parte de las Matemáticas útil en la criptografía. Ésta
permite realizar cálculos complejos, manteniendo siempre una representación numérica
compacta y definida, puesto que sólo maneja un conjunto finito de números enteros. Esta
aritmética es conocida como “aritmética de reloj” debido al parecido que se tiene para
contar el tiempo. Por ejemplo, si son las 03:23:59 y pasa un segundo, decimos que son las
03:24:00, y no las 03:24:60.
IPN ESIME-ZACATENCO
8
Dado cualquier entero n y cualquier entero a, si se divide a entre n, habrá un entero
cociente q y un entero residuo r que obedecen la siguiente expresión:
donde
y donde es el entero el cual corresponde a un menor o igual a x.
Fig. 1.3. Valores que intervienen en la descripción del módulo [7].
La Fig. 1.3 muestra que dados dos enteros a y n positivos, siempre es posible encontrar q y
r que satisfagan la relación (1.2) en donde a puede caer en algún lugar de la recta (en la
figura se muestra que a cae en el lado positivo). En la recta que inicia en cero se procede a
ubicar n, 2n, 3n,…qn tal que . La distancia desde qn hasta a es r,
por lo tanto se han encontrado los valores únicos de q y r.
Para el ejemplo se emplea (1.2):
Un conjunto de números enteros se denota como .
Se define a mod n como el residuo de dividir a entre n, donde . Así que para
cualquier entero a se puede escribir como sigue:
.
IPN ESIME-ZACATENCO
9
Los ejemplos anteriores se pueden escribir de la forma siguiente:
15 mod 8 = 7 -15 mod 8 = 1
Los números enteros módulo n son denotados como , donde el conjunto = {a | 0 ≤ a ≤
n − 1}.
Un grupo bajo adición módulo n con identidad 0 se representa = {a | 1 ≤ a ≤ n − 1}.
Un grupo multiplicativo módulo n con identidad 1 se representa = {a | 1 ≤ a ≤ n − 1 y
(greatest common divisor) gcd(a, n) = 1}.En particular, si n es un primo, .
Dos enteros a y b se dice que son congruentes módulo n si donde
esto se puede escribir como
.
Como ejemplo
1.2.2. NÚMEROS PRIMOS
Un número primo es un entero mayor que 1 cuyos únicos factores son 1 y el mismo
número. En criptografía, especialmente en criptografía de llave pública, se utilizan primos
grandes.
Dos números son primos relativos entre sí cuando no comparten ningún factor en común,
excepto el 1. En otras palabras si el gcd de dos números a y n es igual a 1. Esto se puede
escribir
gcd(a,n) = 1.
Ejemplo: Los números 15 y 28 son primos relativos
Una forma de calcular el máximo común divisor es utilizar el algoritmo de Euclides que es
de la forma siguiente [9]:
IPN ESIME-ZACATENCO
10
gcd(a, b). (1.3)
ALGORITMO 1. El algoritmo de Euclides puede ser escrito:
ENTRADA: Dos números enteros no negativos a y b con a ≥ b.
SALIDA: El máximo común divisor de a y b.
Mientras b 0 va a hacer lo siguiente:
r←a mod b
a←b
b←r.
Regresa a.
Para encontrar el gcd(4864, 3458), se recurre a utilizar el Algoritmo 1.
Tabla 1.2. Algoritmo de Euclides.
r a b
1406
646
114
76
38
0
4864
3458
1406
646
114
76
38
3458
1406
646
114
76
38
0
En la Tabla 1.2. siguiendo el algoritmo se encuentra el gcd(4864, 3458) = 38.
Para una correcta interpretación del Algoritmo 1 el procedimiento fue el siguiente:
Si a ≥ b entonces
1) Se efectúa la división entera a entre b y se obtiene un cociente c1 y un residuo r1
2) Se efectúa la división del divisor b entre el residuo r1 y se obtiene un cociente c2 y
un residuo r2
3) Se divide r1 entre r2 y se obtiene c3 y r3
4) Así reiteradamente hasta llegar a una división exacta, de resto cero.
IPN ESIME-ZACATENCO
11
5) El último divisor empleado es el gcd.
Ejemplo:
gcd(4864, 3458)
1)
2)
3)
4)
5)
6)
gcd(4864, 3458) = 38.
1.2.3. INVERSO MULTIPLICATIVO DE UN MÓDULO
La identidad multiplicativa de un número es uno, tal que el inverso multiplicativo de un
número por ejemplo 4 es ¼ porque 4 * ¼ = 1. En el mundo de módulo esto es más
complicado. El problema es encontrar una x entera tal que
donde el inverso multiplicativo de a módulo n es un entero tal que la expresión
anterior se cumpla, tal que si existe una x esta será única y donde a se dice que es
invertible.
IPN ESIME-ZACATENCO
12
que se puede escribir de la forma
El inverso de un módulo hay veces que sí tiene solución y otras no. Por ejemplo el inverso
de 5 mod (14) = 3. En general la expresión (1.4) tiene una única solución si a y n son
primos relativos, pero si no son no existirá una solución. Para encontrar el inverso módulo
(n) uno de los métodos utilizados es el algoritmo de Euclides Extendido. Este método
obtiene el máximo común divisor d de dos enteros a y b y también enteros x y y donde se
cumple la siguiente condición [9]
ax + by = d (1.5)
Donde a la ecuación (1.5) se le conoce como "Identidad de Bezout”.
ALGORITMO 2. Algoritmo de Euclides Extendido.
ENTRADA: Dos números enteros no negativos a y b donde
SALIDA: d = gcd (a,b) y enteros x,y que satisfacen ax + by = d
x2←1,
x1←0,
y2←0,
y1←1
mientras b > 0 va hacer lo siguiente
regresa (d, x, y)
Si b = 0 entonces
d←a, x←1, y←0
regresa (d, x, y).
IPN ESIME-ZACATENCO
13
Tabla 1.3. Algoritmo de Euclides Extendido para encontrar el gcd(4864, 3458).
q r x y a b x2 x1 y2 y1
-
1
2
2
5
1
2
-
1406
646
114
76
38
0
-
1
-2
5
-27
32
-91
-
-1
3
-7
38
-45
128
4864
3458
1406
646
114
76
38
3458
1406
646
114
76
38
0
1
0
1
-2
5
-27
32
0
1
-2
5
-27
32
-91
0
1
-1
3
-7
38
-45
1
-1
3
-7
38
-45
128
El máximo común divisor gcd(4864,3458) = 38. Donde la expresión (1.5) resulta
(4864)(32) + (3458)(-45) = 38; los valores a y b se toman de la expresión (1.4).
1.2.4. RESIDUOS CUADRÁTICOS
Dada una clase residual módulo p y un entero . Se considera un residuo cuadrático h
si éste tiene una raíz cuadrada módulo p, esto es, si existe un valor de mod(p)
satisfacerá mod (p) de lo contrario h no será un residuo cuadrático.
Dado un primo impar p y un entero cualquiera h, el símbolo de Legendre [9] está definido
como
1 si es un residuo cuadrático mod( )
1 si no es un residuo cuadrático mod( ) (1.6)
0 si es divisible por
h ph
h p
h pp
IPN ESIME-ZACATENCO
14
Ejemplo:
Calcúlese los cuadrados en , para p=5, 7, 1.
Tabla 1.4. Cuadrados en .
1 2 3 4 5 6 7 8 9 10
k2 mod 5 1 4 4 1
k2 mod 7 1 4 2 2 4 1
k2 mod 11 1 4 9 5 3 3 5 9 4 1
Para la obtención de la Tabla 1.4, los valores que toma k serán menores a mod (p) y los
residuos cuadráticos serán los que se repitan más de una vez en la tabla. A continuación se
muestra la lista, donde la mitad de los enteros de p son residuos cuadráticos y no
cuadráticos.
Residuos cuadráticos Residuos no cuadráticos
p = 5
p = 7
p = 11
{1, 4}
{1, 2, 4}
{1, 3, 4, 5, 9}
{2, 3}
{3, 5, 6}
{2, 6, 7, 8, 10}
Se pueden encontrar los residuos cuadráticos también con el criterio de Euler que dice lo
siguiente:
Sea p un número primo impar y h un entero cualquiera coprimo (primo relativo) con p.
Entonces
donde al resolver la ecuación (1.7) se obtendrán valores de 1, -1 y 0 para tomar la decisión
de que si es o no un residuo cuadrático se utiliza la expresión (1.6).
IPN ESIME-ZACATENCO
15
Para que exista un residuo cuadrático se tiene que satisfacer la siguiente congruencia
mod (p). Para todos los enteros , la ecuación anterior se expresa como
mod (p) donde se tendrá cero o dos soluciones, por lo que se puede expresar
mod (p) como ( mod (p).
1.2.5. TEORÍA DE GRUPOS
Los sistemas criptográficos se construyen de las estructuras algebraicas más utilizadas: la
estructura de grupos. Se denomina grupo abeliano a un conjunto no vacío dotado de una
operación binaria * que cumple [3], [4], [10]:
(Existencia de una identidad) la existencia de un elemento tal que
a*e =e*a=a para toda a
(Existencia de inversos) Para cada a existe un elemento b llamado el
inverso de a tal que a*b=b*a =e.
(Conmutativa) a*b=b*a para toda .
1.3. TEOREMA DE CAYLEY-HAMILTON
El teorema de Cayley-Hamilton establece que una matriz cuadrada K satisface la ecuación
característica: si p(λ) = det(K−λΙ) es el polinomio característico de K, por lo tanto p(K) es
una matriz nula.
11 12 1
21 22 2
1 2
( ) det( )
n
n
n n nn
k k k
k k kp K I
k k k
(1.8)
IPN ESIME-ZACATENCO
16
En algunas situaciones el teorema de Cayley-Hamilton es útil para calcular la inversa de
una matriz. Si existe y p(K) = 0, entonces p(K) = 0. Para ilustrar esto, si se efectúa
el determinante (1.8) de forma general se tiene [10]
(1.9)
al sustituir por la matriz K en el polinomio (1.9), el resultado es una matriz nula:
(1.10)
donde sí se multiplica (1.10) por resulta:
(1.11)
(1.12)
IPN ESIME-ZACATENCO
17
CAPÍTULO II
CRIPTOGRAFÍA DE CURVAS ELÍPTICAS
2.1. ALGORITOS DE EXPONENCIACIÓN
Se tienen dos números naturales a y b, se desea calcular ab lo más sencillo es multiplicar a
por si mismo b veces, sin embargo para valores muy grandes de b, se puede hacer lo
siguiente:
Se considera la representación binaria de b
(2.1)
Se expresa la potencia que se desea calcular en función de la representación antes citada
. (2.2)
La variable bi solamente puede valer 0 ó 1, por lo que para calcular ab solo se debe de
multiplicar los correspondientes a los dígitos binarios de b que valgan 1.
2.2. PROBLEMAS DE LOS LOGARITMOS
2.2.1. PROBLEMA DE LOS LOGARITMOS DISCRETOS
El problema inverso de la exponenciación es el cálculo de los logaritmos discretos.
Considérense dos números a y b y el módulo n.
IPN ESIME-ZACATENCO
18
Se define el logaritmo discreto de a en base b módulo n de la siguiente forma:
(2.3)
Si se conoce en (2.4) b y c, computacionalmente es fácil calcular a, sin embargo dados a y
b, se considera intratable (computacionalmente hablando) determinar n.
2.2.2. PROBLEMA DE LOS LOGARITMOS DISCRETOS EN CURVAS
ELÍPTICAS
Para un punto p cualquiera de una curva elíptica (en breve se dejará claro a qué tipos de
curvas nos referimos) en donde pertenece al conjunto , por lo que si se
dispone de un punto , debe existir un número entero k tal que .
El problema de los logaritmos discretos en curvas elípticas consiste precisamente en hallar
el punto k a partir de p y q.
2.3. CRIPTOGRAFÍA DE CURVAS ELÍPTICAS
La Criptografía de Curva Elíptica es una de las disciplinas más prometedoras en el campo
de los cifrados asimétricos. Una de las mejores técnicas es la criptografía de curvas
elípticas ECC (Elliptic curve cryptography) planteada por Koblitz y Miller. Su
implementación suele resultar tanto o más eficiente que la aritmética modular, y además
con claves mucho más cortas.
Una curva elíptica se puede definir [3] por:
2 3 2y x ax b (2.5)
IPN ESIME-ZACATENCO
19
en donde (2.5) es llamada ecuación de Weierstrass, con ésta ecuación las graficas de las
curvas que se obtienen poseen la característica de ser simétricas con respecto al eje x.
Para que las curvas elípticas sean consistente tiene que cumplir con la condición
discriminante:
3 24 27 0a b (2.6)
al cumplir con la condición anterior la gráfica obtenida no tendrá puntos singulares, es
decir, que los factores del polinomio de la ecuación (2.5) no son factores repetidos por lo
consiguiente en el eje de las abscisas no existirán dos raíces idénticas, entonces los puntos
de la gráfica de la curva elíptica no tendrá puntos singulares, constituirá un grupo con la
operación suma, una de las propiedades de las curvas elípticas que más adelante se
menciona.
Fig. 2.1. Curva Elíptica.
Para graficar la Fig. 2.1 se utilizaron (2.5) y (2.6).Los valores que se asignaron en (2.5)
fueron:
1; 1a b
IPN ESIME-ZACATENCO
20
por lo tanto (2.5) resulta
2 3 2
1 sobre y x x (2.7)
La Fig. 2.1 corresponde a la ecuación (2.7) en donde la condición (2.6) se cumple. Existe
un punto especial O, llamado punto al infinito, es decir, es un punto imaginario situado
sobre el eje x a una distancia infinita por lo que no tiene un valor en concreto, con el punto
especial más la operación suma, es lo que se denomina grupo de curva elíptica E(R).
Las curvas elípticas es un grupo finito generado por n, siendo n un número primo impar [4].
Los pares de puntos que se obtendrán estarán definidos sobre este campo, cumpliendo con
la restricción 0,1,..., 1p p donde p es un número primo impar [5]. Por lo tanto la curva
elíptica definida en p es
2 3mod( )y x ax b p (2.8)
en donde para formar las parejas de puntos ( , ) | , px y x y de la curva Elíptica ( )pE se
utilizará la ecuación (2.5) siempre y cuando se cumpla la condición
3 24 27 0(mod ).a b p (2.9)
Al conjunto de los pares de puntos de ( )pE se agrega el punto al infinito.
2.3.1. OPERACIONES SOBRE UNA CURVA ELÍPTICA
Las operaciones que se pueden realizar en una curva elíptica [3], [11] son la suma y la
multiplicación entre puntos de una curva. Se tienen que considerar las siguientes
propiedades:
1.- Identidad
es el elemento neutro.
para toda ( ).P P P P E
IPN ESIME-ZACATENCO
21
2.- Negativos
Si ( , ) ( ), entonces ( , ) ( , ) .
El punto ( , ) es denotado por .
P x y E x y x y
x y P
3.- Adición de puntos
1 1 2 2
3 3
Considérese ( , ) ( ) y ( , ) ( )
donde P Q. Cuando P+Q= ( , ).
P x y E Q x y E
x y
2
2 1 2 13 1 2 3 1 3 1
2 1 2 1
y ( ) .y y y y
x x x y x x yx x x x
4.- Suma de puntos consigo mismos
1 1Considérese ( , ) ( )P x y E y el valor de a de la ecuación (2.5).
22 2
1 13 1 3 1 3 1
1 1
3 32 ( ) .
2 2
x a x ax x y y x x y
y y
Las propiedades de las curvas elípticas se pueden representar gráficamente, esto
considerando dos puntos P(x1, y1) y Q(x2, y2) pertenecientes a la curva.
Si se suma un punto consigo mismo, es decir P+P, entonces la recta que se traza es la
tangente a P (véase Fig. 2.2 a).
Dado un punto P, definimos su opuesto, que se denota como y que se obtiene al trazar
una línea vertical en P donde lo que varía es la ordenada de P (véase Fig. 2.2 b).
El elemento neutro se obtiene de la suma de un punto con su opuesto. La línea que pasa por
ambos puntos se pierde en el infinito, de forma que se agrega este punto a la curva para
obtener el neutro, al que se llama punto al infinito (véase Fig. 2.2 c).
Cuando se desea calcular P más Q y la tangente a la curva es una recta vertical. Esto
ocurrirá cuando la ordenada de P sea 0. En este caso la recta se pierde en el infinito (véase
Fig. 2.2 d).
IPN ESIME-ZACATENCO
22
Dados dos puntos P y Q pertenecientes a la curva, se traza la recta que pasa por ambos y se
obtiene un tercer punto, al trazar la vertical en este punto se obtiene el punto R (véase Fig.
2.2 e).
a) P + P =
b)
x
y
x
y
IPN ESIME-ZACATENCO
23
c) P + ( ) = 0
d) P + Q = 0
x
y
x
y
IPN ESIME-ZACATENCO
24
e) P + Q = R
Fig. 2.2. Operaciones de las curvas elípticas.
2.3.2 GENERAR PARES DE PUNTOS
Para generar los pares de puntos de la curva ( )pE hay dos formas [3]:
Sin conocer ningún punto de la curva
Conociendo un par de puntos de la curva
Lo primero que se hará es generar los puntos sin conocer ningún punto de la curva.
A modo de ejemplo en la ecuación (2.8) se sustituirá por los siguientes valores y se verifica
si la condición (2.9) se cumple:
1, 1 23a b y p
La ecuación resultante es:
2 31 mod(23).z y x x (2.10)
x
y
IPN ESIME-ZACATENCO
25
Una vez que se tiene la ecuación de Weierstrass (2.8) definida en un campo cuyos valores
en nuestro caso serán menores a 23, se procede a calcular las parejas de puntos que
pertenezcan a ( )pE .
Tabla 2.1. Construcción de valores de la ECC empleando el criterio de Euler y el símbolo
de Legendre.
Para realizar el cálculo de los puntos se construye la Tabla 2.1 de la siguiente manera:
En la columna 1 se escriben los valores de x con x p dado que se está
trabajando con aritmética módulo 23.
Se evalúa la ecuación (2.10) con los valores de x, el resultado se asigna a la variable
z.
x z Residuos x z Residuos
0 1 1 12 16 1
1 3 1 13 3 1
2 11 -1 14 22 -1
3 8 1 15 10 -1
4 0 0 16 19 -1
5 16 1 17 9 1
6 16 1 18 9 1
7 6 1 19 2 1
8 15 -1 20 17 -1
9 3 1 21 14 -1
10 22 -1 22 22 -1
11 9 1
IPN ESIME-ZACATENCO
26
Se obtienen los residuos cuadráticos y no cuadráticos, para ello se utiliza el criterio
de Euler (1.6) y el símbolo de Legendre (1.5) en donde la variable h será sustituida
por la variable z.
Para encontrar los puntos de la curva elíptica se utilizó la fórmula siguiente:
* 2
*
* 2
*
* 2
*
(1 23) mod(23)
1;
(2 23) mod(23)
4;
(3 23) mod(23)
9;
y x
h
h
h
h
h
h
y así sucesivamente. En la tabla siguiente se observan los resultados que se obtuvieron.
Tabla 2.2. Valores de y para el par de puntos de ECC.
y h*
y h*
0 0 10 8
1 1 11 6
2 4 15 18
3 9 16 3
5 2 17 13
6 13 19 16
8 18 22 1
9 12
IPN ESIME-ZACATENCO
27
El procedimiento para construir los puntos (x,y) de la ecuación (2.10) es el siguiente:
Considérese el valor de h* obtenido anteriormente y los valores x y z de la tabla 2.1.
p=23
for i = 1 to length (x)
if *( ) ( )h i z i then
point (x(i),mod(y(i),p)) and point (x(i),mod((p-y(i)),p)
end
end
Tabla 2.3. Pares de puntos de (2.10) [12].
Todos los puntos mostrados en la Tabla 2.3.de la primer columna pertenecen a la curva
elíptica definida en la ecuación (2.10), los puntos encontrados son . En la segunda
columna aparece el orden del punto el cual se explica en el tema 2.3.3.
Generar los puntos de la curva elíptica conocido un punto (x, y).
Para que se puedan generar los puntos a partir de uno dado [3], [12], se apoya todo el
cálculo con las operaciones que se emplean en las curvas elípticas; la adición de puntos y
la suma de puntos consigo mismos, en todo este proceso se utiliza el algoritmo de Euclides
extendido.
IPN ESIME-ZACATENCO
28
Por ejemplo, considere el punto P=(x1,y1) = 23(1,7) el cual pertenece a la Tabla 2.3, la
ecuación de ECC utilizada es (2.10), en donde a partir de éste se encontraran los demás
puntos de la curva elíptica. El procedimiento es sumar k veces el punto, es como multiplicar
P por un escalar k.
.
suponiendo que solo se conoce el punto P=(x1,y1) = 23(1,7) , éste punto pertenece a la
ecuación (2.8) donde , lo que se hace primero es emplear la
propiedad 4 de las operaciones de las curvas elípticas que es:
2
3 1 3 1 3 12 y ( ) (2.11)x w x y w x x y
donde 2
1
1
3
2
x aw
y
por ejemplo
El resultado de la ecuación (2.12) es una fracción y puesto que se trabaja con números
23 esto no es posible. Por lo que se debe de encontrar el inverso multiplicativo se optó
en utilizar el algoritmo de Euclides Extendido citado en el capítulo 1, para esto los valores
que toma la entrada del algoritmo son 14 del denominador de la variable w y 23 del módulo
de la curva elíptica, empleando la ecuación (1.5) que es:
IPN ESIME-ZACATENCO
29
ax + by =d
el resultado del algoritmo de Euclides Extendido es:
(23)( )+ (4)(5) = 1. (2.13)
Al obtener un resultado igual a 1, éste nos indica que tiene inversa multiplicativa vista en el
capítulo 1, es conveniente escoger de la ecuación (2.13) el valor positivo de la variable x o
y de lo contrario se tiene que aplicarle al valor de la variable la operación módulo (p), por
tales motivos se escogió el valor de la variable y entonces el resultado de (2.12) es:
Sustituyendo el valor de la variable w encontrada en la ecuación (2.11) para hallar el valor
de la abscisa y la ordenada que pertenece a la curva elíptica.
1 3 1( )x x y
Con el cálculo anterior se encontró el segundo punto generado a partir del punto P= (x1,y1)
= 23(1,7) que es (7,11) esto es 2P, se observa en la Tabla 2.4 que el punto pertenece a
la ECC.
Para calcular los demás puntos se utiliza la propiedad 3 de las operaciones de las curvas
elípticas, esto debido a que se tienen ya dos puntos conocidos, con los puntos ya calculados
se hace lo siguiente:
1 1 2 2
3 3
( , ) ( ) y ( , ) ( )
donde P Q. Cuando P+Q=( , ) por lo tanto
(1,7)
(7,11).
P x y E Q x y E
x y
P
Q
IPN ESIME-ZACATENCO
30
La propiedad 3 de las operaciones de ECC es:
2
3 1 2 3 1 3 1( ) (2.14)x t x x y y t x x y
donde
2 1
2 1
y yt
x x
con los puntos P y Q conocidos t resulta:
El mismo procedimiento que se utilizó para el cálculo de la variable w es el que se aplica la
variable t, entonces el resultado del algoritmo de Euclides Extendido es:
(23)( ) + (6)(4) = 1. (2.16)
Se toma de la ecuación (2.16) el valor que corresponde a la variable y. El resultado de la
ecuación (2.15) es:
Se calcula ahora el puntos (x3, y3) para lo cual se emplea (2.14).
.
Entonces el punto 3 de la curva elíptica a partir del punto (1, 7) es (18, 20).
Ahora se calcula k =4, es decir, el cuarto punto donde se tiene:
IPN ESIME-ZACATENCO
31
1 1 2 2
3 3
( , ) ( ) y ( , ) ( )
donde P Q. Cuando P+Q=( , ) por lo tanto
(1,7)
(18,20).
P x y E Q x y E
x y
P
Q
A partir de las relaciones (2.14), para encontrar (x3, y3) se consideran los puntos P y Q
obtenidos anteriormente, así que se tiene:
2 1
2 1
y y
x x
El resultado de algoritmo de Euclides Extendido es:
(23)(3) + (17)( )= 1.
Continuando resolviendo la ecuación (2.7) donde se toma el valor de y= de la expresión
anterior que corresponde a la solución del algoritmo de Euclides Extendido esto es:
Se calcula ahora el puntos (x3, y3) utilizando (2.14)
El cuarto punto de la curva a partir del punto dado es (17, 20)
El procedimiento continúa sucesivamente hasta que se encuentre el negativo del punto
dado, es decir, el punto (x, y) del primer punto. Esta es la forma de encontrar todos los
puntos que se muestra la Tabla 2.3.
IPN ESIME-ZACATENCO
32
De la Tabla 2.3 el punto que se escogió como punto generador P = 23(1,7) es de orden
28 incluido el punto al infinito, es decir, que se generarán 28 puntos en total como se ve en
la Tabla 2.4.
En la tabla 2.4 se muestran todos los puntos calculados a partir del punto P=(x1,y1) =
23(1,7) . El valor k que se observa en la tabla representa la operación de sumar k veces el
punto dado. Se puede notar que son 27 los puntos encontrados, más el punto especial hacen
en total 28 puntos.
Tabla 2.4. Puntos generados dado un punto de ECC.
2.3.3 ORDEN DE UN PUNTO EN ECC
La adición de un punto consigo mismo genera un nuevo punto como se ha mencionado
anteriormente, sin embargo siempre va existir un momento en el que al añadir el punto así
mismo se generará un punto al infinito. El orden de un punto P es el menor número
positivo k, tal que kP= O.
IPN ESIME-ZACATENCO
33
y
x
En la Tabla 2.3 se observa cuál es el orden de cada punto que pertenece a la curva elíptica,
es decir, que si se escoge un punto de esta Tabla y a partir de éste se realizan los cálculos
que se citaron anteriormente se obtendrá la Tabla 2.4
Fig. 2.3. Puntos graficados de la Tabla 2.3.
En la Fig. 2.3 se observa que los puntos son simétricos si se traza una línea horizontal en
y=11.5, solamente un punto no tiene simetría, todos los puntos que se graficaron están
contenidos en la Tabla 2.3 donde se tienen dos valores idénticos de abscisa y por supuesto
los valores de las ordenadas deben de ser diferentes para que den la simetría, el punto que
solamente tiene un valor de abscisa es (4,0) y por lo tanto es el que no tiene simetría. El
orden de una curva elíptica es denotada es decir, el número de puntos incluyendo
el punto al infinito, esto es:
=
donde
= orden del punto generador
= cofactor que son los factores de .
IPN ESIME-ZACATENCO
34
Como un ejemplo en la Tabla 2.4 el punto conocido fue (1, 7) a partir de éste se generaron
28 puntos incluyendo el punto al infinito entonces
Se sabe que = 28
;
Los parámetros necesarios para que se puedan generar los puntos [13] a partir de un punto
generador son los siguientes:
T= (p, a, b, G, , ) (2.18)
donde
p: es el tamaño del campo definido por el módulo
a, b: son los coeficientes definidos en la curva E
G: es el punto generador
: es el orden del punto generador
: es el cofactor.
Estos parámetros pueden ser públicos, tienen que ser compartidos por las entidades que
utilizan el criptosistema en particular, es necesario decir que la seguridad no depende de
estos parámetros secretos. Para generar la Tabla 2.4 los valores que toma la expresión
(2.18) son:
T= (23, 1, 1, (1, 7), 28, 1).
IPN ESIME-ZACATENCO
35
2.4. PROTOCOLO DIFFIE-HELLMAN
Este protocolo es empleado para el intercambio de llaves [3], [14] con la finalidad de que se
pueda establecer una conversación entre dos usuarios en donde para el caso de un
criptosistema asimétrico solamente la llave pública viaja en el medio.
Al utilizar este protocolo en las curvas elípticas el procedimiento es el siguiente:
considérese que se tienen dos usuarios los cuales son Alicia y Bob.
Cualquiera de los dos escoge un punto x de la curva elíptica (2.8) y lo trasmite a la
otra parte.
Alicia y Bob cada uno de ellos escoge al azar un número enteros e y f.
Alicia calcula ex y se lo transmite a Bob.
Bob calcula fx y se lo transmite a Alicia.
Alicia calcula efx.
Bob calcula fex.
En el procedimiento anterior se nota que lo transmitido es la llave pública x también ex y
fx, los enteros e y f son la llave privada de Alicia y Bob respectivamente por lo que no se
transmiten.
2.5. CRIFRADO DE MENEZES–VANSTONE CON CURVAS ELIPTICAS
Este criptosistema es utilizado para llaves públicas, es una variante del protocolo de
ElGammal.
Como el criptosistema de Menezes-Qu-Vanstone (MQV) [3], [15] es empleado para
transmitir información sobre puntos de una curva elíptica entonces estos se deben de
construir a partir de la ecuación (2.8).
IPN ESIME-ZACATENCO
36
El procedimiento del criptosistema es el siguiente:
Se tienen las siguientes llaves:
Llave privada
Llaves públicas
Para el encriptamiento y el desencriptamiento de un mensaje cuyo texto son dos números
enteros es:
Encriptamiento
Texto plano x1, x2
1. Se escoge una llave de sesión secreta
2. Se resuelve .
3. Se resuelve
4. Se resuelve
5. Se resuelve
Los puntos cifrados son
Desencriptamiento
Se parte de los puntos cifrados
1. Se resuelve
2. Se resuelve
.
3. Se resuelve
Recuperación del texto plano x1, x2 .
Véase el Apéndice A, donde se muestra un ejemplo de este algoritmo.
IPN ESIME-ZACATENCO
37
2.6. CIFRADO DE ELGAMAL CON CURVAS ELÍPTICAS
Los problemas de logaritmos discretos en curvas elípticas basan su seguridad en el cifrado
de ElGamal [3], [16] el cual es utilizado en criptosistemas asimétricos.
Este cifrado consiste en representar un texto claro m como puntos de la curva elíptica, el
proceso es el siguiente:
Se debe de expresar el texto claro m como un número entero.
Para esto se considera un alfabeto de N letras, cada carácter del alfabeto tomará un
valor entero Cuando se forman bloques de texto la longitud de éste se
representa como l, entonces considérese un bloque de texto como
donde es el alfabeto con valores enteros, para realizar la
codificación del bloque del texto se hace de la siguiente manera:
(2.19)
Nota: si el texto solamente tiene un carácter, no es necesario realizar la codificación
anterior entonces .
Para cifrar la expresión (2.19) se hace de la siguiente manera:
Se ponen de acuerdo ambas partes donde se hace el intercambio del mensaje para
elegir una llave de sesión que se denotada como .
El número de bloques del texto será el número de puntos (x, y) a encontrar, el
proceso para colocar sobre los puntos de la curva es el siguiente:
Considérese la ecuación
mod (p) de curvas elípticas donde
{xj=gw+j | posteriormente se procede encontrar el valor de ;
este valor será la coordenada de un punto de la curva elíptica y para localizarlo se
tomará el valor de la y correspondiente que aparece en la tabla construida con los
puntos de la curva. Este punto (x, y) representa el texto claro m.
IPN ESIME-ZACATENCO
38
Para convertir los puntos al mensaje original se hace:
Por último se utiliza el alfabeto N para sustituir los valores enteros encontrados y
tener el mensaje original.
IPN ESIME-ZACATENCO
39
CAPÍTULO III
CONSTRUCCIÓN DEL SISTEMA CRIPTOGRÁFICO
3.1. FORMAS PARA AUMENTAR LA SEGURIDAD
Existen varias opciones para aumentar la seguridad de un sistema criptográfico basado en
curvas elípticas. La más simple es aumentar los valores de la curva elíptica definido por el
problema, pero se necesita un esfuerzo computacional elevado para resolverlo. Sin embargo
si se utiliza la NIST (National Institute of Standards and Technology) [15], [17] se
encuentran definidos los campos primos y binarios en donde se puede trabajar con
cualquiera de estos, así que ésta es una buena alternativa para evitar este problema.
Otra opción es transmitir varios puntos de la curva elíptica de forma independiente, como
se vió en el capítulo anterior en donde estos se calculan aprovechando la información de los
puntos y así reducir la complejidad de los siguientes puntos. Otra forma es definir el
problema de logaritmos discretos con curvas elípticas basadas en matrices, por lo que se
tendrán n-tuplas de puntos.
3.2. DESCRIPCIÓN DEL SISTEMA.
Considere una curva elíptica representada por #E , y n un entero positivo [14]. Se
define:
donde
( )x ( ) ( ) (3.1)n nMat E En p q q
IPN ESIME-ZACATENCO
40
:Matn Es una matriz de tamaño n x n con elementos en y en
p : Campo finito que contiene elementos q=p donde p es un valor primo.
q : Campo finito que contiene q elementos. Para la ANSI X9.62 nos dice que q= p, p > 3 o
de una potencia de 2.
:( )n
E q Es el conjunto de n-tuplas de puntos.
Sea la matriz con elementos elegidos arbitrariamente. Una condición
importante es que tenga inversa. En base a ésta matriz M se construye la matriz A (ver
[10]) de la siguiente manera (véase Apéndice B).
2 1
1 2 1
n
o nA a I a M a M a M
(3.2)
donde I es la matriz identidad, y los coeficientes son números escalares
escogidos arbitrariamente. A esta matriz A se le conoce como llave privada.
Así mismo, se construye el vector columna formado por n puntos de la curva elíptica.
Estos puntos pueden ser tomados también arbitrariamente, pero por facilidad conviene
elegir solamente algún punto (x, y) de la curva y a partir de éste construir los siguientes.
Esto es, el punto seleccionado será el generador de los siguientes n-1 puntos (véase
Capítulo II pág. 24). es un elemento conocido por los dos interlocutores en la
conversación. Entonces se tiene:
0
1[ ] para 0 1 y =,
1
P
Pi, j ni j
Pn
a
Para obtener la llave pública, se multiplica la matriz A por el vector obteniéndose el
vector columna . Obsérvese que la llave pública está constituida por puntos que
pertenecen a la curva elíptica dada
IPN ESIME-ZACATENCO
41
.
0
1
1
A
n
(3.3)
Esto es
2 1
1 2 1 .
0 0
1 1
1 1
( ) =n
o n
P
P
Pn n
a I a M a M a M
(3.4)
3.3. CRIPTOANÁLISIS
Con el sistema criptográfico construido se puede realizar un criptoanálisis, que consiste en
encontrar los valores de ai del sistema (3.4) donde son valores públicos. Observe
que (3.4) es un sistema de n ecuaciones con n incógnitas .
Como un ejemplo de criptoanálisis, consideremos una matriz pequeña M de 3x3.
11 12 13
21 22 23
31 32 33
.
m m m
M m m m
m m m
Entonces la llave privada A tendrá la forma 2
1 2oA a I a M a M y los vectores y
son
0 0
1 1
2 2
y Φ
P
P
P
y M2 es
IPN ESIME-ZACATENCO
42
11 12 13
2
21 22 23
31 32 33
x .M M M
Como todo punto de la curva elíptica es generador de puntos de la misma, entonces
1 0P P y 2 0P P donde y son enteros positivos. Entonces
2 11 1 11 0 2 12 1 12 2 13 1 13 0 0
2 21 1 21 2 22 1 22 0 2 23 1 23 0 1
2 31 1 31 2 32 1 32 2 33 1 33 0 0 2
. (3.5)
a a m a a a m a a m P
a a m a a m a a a m P
a a m a a m a a m a P
Los valores a encontrar en (3.5) son los coeficientes a0, a1, a2. Como 0 , 1 y 2 están en
función de un solo punto igual que en el vector , entonces se realiza lo siguiente:
Existen , y , escalares enteros positivos tales que 0 0 0 1 0 2, y .P P P
Entonces
2 11 1 11 0 2 12 1 12 2 13 1 13 0 0
2 21 1 21 2 22 1 22 0 2 23 1 23 0 0
2 31 1 31 2 32 1 32 2 33 1 33 0 0 0
a a m a a a m a a m P P
a a m a a m a a a m P P
a a m a a m a a m a P P
de aquí se obtiene
2 11 12 13 1 11 12 13 0
2 21 22 23 1 21 22 23 0
2 31 32 33 1 31 32 33 0
( ) ( )
( ) ( )
( ) ( ) .
a a m m m a
a a m m m a
a a m m m a
(3.6)
En el Apéndice C se muestra el desarrollo completo para obtener el sistema (3.6).
Obviamente, en un caso real, el tamaño de la matriz M es mucho mayor y el número de
incógnitas también, por lo que el sistema es mucho más complejo.
IPN ESIME-ZACATENCO
43
Para que un criptoanalista pueda encontrar los coeficientes ai del sistema (3.6), es necesario
que primero encuentre los coeficientes a, b y p de (2.8) (los cuales pueden estar en
constante cambio dependiendo del criterio del administrador), encontrar el punto de la
curva utilizado como generador y finalmente encontrar los coeficientes ai. Como el objetivo
de la tesis no es realizar un criptoanálisis, se trabaja con puros datos conocidos. En el
Apéndice D se tiene un ejemplo de un criptoanálisis considerando lo mencionado en las
líneas anteriores.
3.4. INTERCAMBIO DE LLAVE DIFFIE-HELLMAN
Para que se pueda compartir una llave en secreto entre dos usuarios, se utiliza el protocolo
Diffie-Hellman. Como se mencionó anteriormente, el vector es público, esto es, viaja de
un usuario al otro. Cada usuario construye su propio vector y lo intercambia con su
contraparte.
Con las indicaciones del protocolo Diffie-Hellman dado en el Capítulo II (pág. 35) se hace
el intercambio de llaves entre dos usuarios los cuales denominamos como Alicia y Bob.
Alicia construye su llave privada A para lo cual escoge n escalares y el resultado
queda expresado como la ecuación (3.2) y Bob hace lo mismo para formar su llave privada
B. La matriz al ser pública los dos la utilizan.
Cada quien realiza la operación (3.4) con su respectiva llave privada para obtener la matriz
, es decir, Alicia forma A y Bob forma B , donde A se transmite a Bob y B se
transmite a Alicia.
Alicia calcula .B Bob calcula .A
Para que el intercambio haya sido correcto se debe cumplir que Satisfecha esta
condición ya pueden tener una comunicación secreta.
IPN ESIME-ZACATENCO
44
3.5. CIFRADO DEL MENSAJE
Hasta ahora se ha realizado que los interlocutores logren el intercambio de llaves para tener
una comunicación segura entre ellos. Lo que procede ahora es enviar los mensajes cifrados.
Para poder cifrar los mensajes se utiliza el método de cifrado de ElGamal (véase Capítulo II
pág. 37). Éste se va a implementar con matrices, por lo tanto se debe codificar el mensaje
en n-tuplas de puntos. El mensaje cifrado se representará por , se pudo haber elegido el
cifrado MQV pero siempre y cuando realizando las adecuaciones para la utilización de
matrices.
El intercambio de llaves entre los interlocutores a quienes llamamos Alicia y Bob en el
protocolo de Diffie-Hellman es:
Alicia B
Bob .A
Una vez concluida la etapa del intercambio de llaves, Alicia toma el mensaje , efectúa la
operación , después se envían a Bob las n-tuplas de puntos . El vector , el
cual posee los puntos del mensaje cifrado será el que viaje en el medio. Por último Bob
utiliza su clave privada B para obtener A y como entonces basta con
restarle a el vector para obtener el mensaje encriptado , esto es, .
Bob recibe el vector . Para desencriptarlo se toma el valor x de cada punto del vector el
cual fue obtenido de la forma siguiente , por lo que
para obtener el texto claro se realizan divisiones de x entre cuyo resultado entero se
vuelve a dividir entre y así sucesivamente hasta obtener un cociente cero, los residuos se
ordenan del último al primero. Estos números se asocian a los números decimales del
código ASCII por lo que representan los caracteres del mensaje descifrado.
IPN ESIME-ZACATENCO
45
3.6 NIST.
El NIST [15],[17], es un organismo que proporciona diez cuerpos finitos sobre los que se
definen las curvas elípticas, cinco cuerpos para y cinco cuerpos de característica 2.
Los cinco cuerpos para son:
(3.8)
Cada uno de estos cuerpos soporta n bits de información, mientras mayor sea el número de
bits será más complejo el sistema. Por ejemplo, si se trabaja en una arquitectura de 32 bits,
una palabra estará comprendida de 0 a 31. Para saber el nivel de seguridad que se tiene,
considérese que t es la medida del nivel de seguridad. Empleando (3.8)
Si se tiene una palabra u de 32 bits, donde , para la NIST sobre
campos primos se tiene t = 6, 7, 8, 12 y 17 respectivamente.
Los elementos de son enteros entre escritos en forma binaria como se muestra
en el Apéndice E. Estos pueden ser escogidos de forma aleatoria o pueden estar asociados
por una curva elíptica. La NIST sobre campos primos considera que
IPN ESIME-ZACATENCO
46
CAPÍTULO IV
DESARROLLO DEL ALGORITMO
4.1. FORMACIÓN DE LA LLAVE PRIVADA
El análisis que se realizó en el capítulo anterior para la construcción de las matrices es
considerando n=3 por lo que todas las matrices serán de esta dimensión. Los elementos
que intervienen en la matriz M son escogidos de forma arbitraria y pertenecen a , en
donde p=23 en este caso.
La matriz M arbitraria que se utiliza para el análisis es:
(4.1)
Se comprueba que esta matriz tiene inversa, la cual es
Para crear la llave privada se utiliza (3.5), los coeficientes que se propusieron en forma
arbitraria para a0, a1, a2 son 5, 6 y 2 respectivamente, la única condición es que pertenezcan
a . La llave privada A resulta:
(4.2)
IPN ESIME-ZACATENCO
47
4.2. CONSTRUCCIÓN DE LOS VECTORES PÚBLICOS A TRANSMITIR
Para la construcción del vector , se elige arbitrariamente un punto de la curva elíptica que
en este caso es el punto (0,1). Éste se considera el generador de los otros puntos y le
llamamos P0 (véase la Tabla 2.3). Según la expresión (2.18) se tiene que
T= (23,1, 1, (0, 1), 28, 1)
los puntos generados en T son 27 más el punto al infinito (véase Apéndice F). Ahora, se
escogen otros dos puntos de los 27, por ejemplo los puntos (13,16) y (3,10). El primero es
4P0 y el segundo es 25P0; esto es y . Así,
(4.3)
por lo tanto
A
(4.4)
de donde la llave pública resulta
IPN ESIME-ZACATENCO
48
4.3. ALGORITMO DIFFIE-HELLMAN
Con el algoritmo Diffie-Hellman (véase Capítulo II, pág. 35) se realiza el intercambio de
llaves entre dos usuarios. El sistema construye una llave privada para cada usuario. Uno es
Alicia, quien elige los valores de ai y construye su matriz A. El resultado es (4.2). El otro
usuario es Bob quien elige arbitrariamente los valores de b0, b1, y b2, que son 18, 1 y 4
respectivamente; y forma su llave privada B que es:
(4.5)
Alicia encuentra la matriz que es (4.4) la cual se denominará .A
Bob emplea el mismo procedimiento para encontrar la matriz pero con su llave privada
el resultado fue:
B
B
.
Ahora Alicia calcula B y Bob calcula .A
(4.6)
En la ecuación (4.6) se observa que las dos variables son idénticas. Esto indica que el
intercambio de llaves es correcto entre Alicia y Bob por lo que se garantiza que se tendrá
una comunicación segura entre ellos.
IPN ESIME-ZACATENCO
49
Este proceso realizado en MATLAB R2008a se muestra a continuación:
IPN ESIME-ZACATENCO
50
IPN ESIME-ZACATENCO
51
4.4. CIFRADO DEL MENSAJE CON UNA MATRIZ
Para realizar el cifrado, los valores que toma la ecuación (2.8) (en especial el valor p) deben
ser números grandes, puesto que si se desea encriptar por el método de ElGamal uno o más
caracteres de 8 bits con el código ASCII de 128 bits el cual tiene contiene 96 caracteres
(véase Apéndice G) se realiza lo descrito en el Capítulo II (pág. 37), donde la codificación
se realiza dividiendo el mensaje en bloques, por ejemplo de dos caracteres por bloque.
Entonces la ecuación (2.19) resulta . Éste valor es el
máximo que se puede tener para dos letras, por lo que p debe ser mayor o igual a éste
número. Para determinar el punto de la curva elíptica que se va a asociar al bloque (de dos
caracteres) se considera Para un valor de y de
j = 1 entonces x1=5 x 12222+1=61111, éste es el valor mínimo x para representar el bloque
con dos caracteres. Para obtener un punto sobre la curva cuya coordenada x esté por encima
del valor 61111 seleccionamos una curva elíptica con valor de p no menor a 61111.
Para realizar la encriptación de un mensaje de dos bloques, conociendo ya el valor máximo
necesario, las variables de la ecuación (2.8) a, b y p valdrán 7, 29 y 65521
respectivamente, estos valores pueden ser propuestos pero se optó por utilizar los valores
definidos en la referencia [16]. El mensaje a encriptar por ejemplo es: examen de grado, la
longitud del mensaje es 15 caracteres, se agrega un término más (un espacio) al mensaje
para que se pueda agrupar en bloques de dos y así realizar la codificación de éste explicado
en el Capítulo II (pág. 37) y posteriormente se procede encontrar el valor de x; éste valor
será la coordenada de un punto de la curva elíptica y para localizarlo se tomará el valor de
la y correspondiente que aparece en la tabla construida con los puntos de la curva. Éste
punto (x, y) relaciona un bloque de dos caracteres del mensaje a encriptar. El proceso
anterior se realiza con cada uno de los bloques en que se ha dividido el mensaje. Como se
explicó en el Capítulo III (pág. 44), a los puntos (x, y) de la curva elíptica que asocian
duplas del mensaje se les denomina . Para obtener el mensaje original se sigue el proceso
del Capítulo III (pág. 44).
IPN ESIME-ZACATENCO
52
El proceso de cifrado se realizó en MATLAB R2008a el cual se muestra a continuación:
Fig 4.1.
La Fig. 4.1. muestra la curva elíptica utilizada para generar los 65437 puntos que
pertenecerán a ella (véase en el Apéndice H).
Para el sistema criptográfico propuesto en la tesis se muestran el diagrama a bloques de
cómo está conformado el sistema (véase Apéndice I).
En EL Apéndice J se encuentra los diagramas de flujo para la construcción del sistema
criptográfico y en el Apéndice K se tiene el código fuente que se desarrollo para éste
sistema.
y
x
IPN ESIME-ZACATENCO
53
IPN ESIME-ZACATENCO
54
IPN ESIME-ZACATENCO
55
IPN ESIME-ZACATENCO
56
Los puntos OMEGA que viajan en éste último mensaje se utilizaron para hacer una
detección y corrección de error [18]de forma general se explica en el Apéndice L puesto
que la tesis no está orientada sobre éste tema.
Un ejemplo para el envío de un mensaje dividido en bloques de un carácter, con valores
diferentes para la curva elíptica.
IPN ESIME-ZACATENCO
57
IPN ESIME-ZACATENCO
58
La diferencia que existe entre la lista de puntos encriptados con la lista de puntos OMEGA
es que en la primer lista el mensaje esta encriptado la cual es denotado como y en la
segunda lista , esta operación nos indica una variación de los valores de los
puntos sino se realiza no se garantizará que el mensaje llegue al usuario correcto, esto
porque nos indica con que usuario se realiza la conversación.
IPN ESIME-ZACATENCO
59
IPN ESIME-ZACATENCO
60
En la Fig. 4.2 se tienen todos los puntos que pertenecen a la curva elíptica. Esta gráfica
tiene un eje de simetría, el cual es y=1000 y esto significa que cada punto encontrado
tendrá un punto –P.
Fig. 4.2. Gráfica de puntos de la curva elíptica a= 9, b = 7 y p =2011.
x
y
IPN ESIME-ZACATENCO
61
CONCLUSIONES
Una de las técnicas más modernas y que está en pleno desarrollo para fortalecer la
seguridad en las redes de comunicaciones es la criptografía basada en curvas elípticas. En
este trabajo se utilizaron valores pequeños como ejemplo para analizar el funcionamiento
del algoritmo y como se aprecia en el capítulo IV el algoritmo trabajó satisfactoriamente
utilizando diferentes valores, se logró identificar a los usuarios lo cual es indispensable para
tener una comunicación y se cifraron los mensajes que se intercambian entre ellos. Si se
lleva a la práctica éste algoritmo, una buena alternativa es emplear los valores
recomendados por la NIST (véase Apéndice D) para la ecuación de Weierstrass, lo que
lleva solamente a un aumento en los tiempos de procesamiento.
IPN ESIME-ZACATENCO
62
TRABAJOS FUTUROS
Realizar un criptoanálisis del sistema criptográfico.
Construir la matriz M con polinomios irreducibles para trabajar con campos
binarios.
Desarrollar un programa específico para optimizar el tiempo de procesamiento del
algoritmo.
Trabajar con cuaterniones en la construcción de la matriz M, utilizar matriz de
rotación de cuaterniones para construir las llaves privadas y así plantear el sistema
criptográfico a utilizar.
Comparar el sistema planteado en la tesis con el sistema criptográfico construido
por cuaterniones.
TRABAJOS DERIVADOS DE LA TESIS
Héctor Oviedo Galdeano, José Antonio López Toledo. “Implementación de matrices en
sistemas criptográficos de ECC”. XII Congreso Nacional de Ingeniería Electromecánica y
de Sistemas CNIES, México, D.F, Noviembre 2010.
Héctor Oviedo Galdeano, José Antonio López Toledo. “Curiosidades sobre la Criptografía
en hechos que dejaron marca en el mundo”. RISCE Revista Internacional de Sistemas
Computacionales y Electrónicos. Noviembre 2010, Número 6, Volumen 2, Año 2, pp. 72-
81.
INGENIERÍA EN TELECOMUNICACIONES XII CONGRESO NACIONAL DE INGENIERÍA
ARTÍCULOS ACEPTADOS POR REFEREO ELECTROMECÁNICA Y DE SISTEMAS
MÉXICO D.F. NOVIEMBRE 2010 889
Resumen –– El presente trabajo trata sobre las curvas elípticas,
una de las técnicas utilizados para los sistemas criptográficos,
estás tienen una mejor eficiencia con respecto a la aritmética
módulo, en donde se empleará matrices para construir un
sistema criptográfico en donde desde luego se aumenta la
seguridad con un mínimo de requerimientos ya que los puntos
a transmitir se hace aprovechando la información obtenida de
los puntos ya calculados para reducir la complejidad del
siguiente punto, el cálculo de estos se plantea sin conocer
ningún punto y conociendo un punto que pertenezca a la curva
elíptica. Palabras Clave – curvas elípticas, criptografía.
Abstract –– This paper deals with elliptic curves, one of the
techniques used for cryptographic systems, this have a better
efficiency with respect to arithmetic module, where matrices
used to build a cryptographic system where of course the
security is increased minimum requirements and that points to
convey is using the information obtained from the points
already calculated to reduce the complexity of the next point,
the calculation of these arises without knowing any point and
knowing a point that belongs to the elliptic curve.
Keywords –– elliptic curve, cryptography.
I. INTRODUCCIÓN
Un concepto importante que ha ido crecido de una
manera extraordinaria es la seguridad en la transmisión de
los datos, hay técnicas que se encargan de cifrar y descifrar
la información para poder garantizar una protección
adecuada de los datos, estas se conocen como criptografía.
El vocablo proviene del griego kryptós, “oculto”, y
graphos, “escritura”, es decir: “La criptografía es el arte de
escribir en clave secreta”, donde la criptografía estudia las
técnicas matemáticas relacionadas con aspectos de la
información tales como la confidencialidad, la integridad de
datos, autentificación y no repudio [1],[2].
II. CRIPTOSISTEMA
Todo sistema que toma información legible, para
convertirlo en información no legible, se puede definir como
una quíntupla (M; C; K; E; D) llamado criptosistema, el
cuál debe de satisfacer la siguiente ecuación
( ( ))D E m mk k
(1)
La ecuación (1) nos dice que un mensaje m, lo ciframos
empleando una clave k y luego procedemos a descifrarlo
empleando la misma clave, con lo que se obtendrá de nuevo
el mensaje original m [1],[3].
M representa el conjunto de todos los mensajes sin cifrar
(lo que se denomina texto claro, o plaintext).
C representa el conjunto de todos los posibles mensajes
cifrados, o criptogramas.
K representa el conjunto de claves que se pueden
emplear en el criptosistema.
E es el conjunto de transformaciones de cifrado que se
aplica a cada elemento de M para obtener un elemento
de C.
D es el conjunto de transformaciones de descifrado,
análogo a E.
Tenemos dos tipos de criptosistemas los simétricos ó de
clave privada y los asimétricos ó de llave pública, el primero
emplea la misma clave k tanto para cifrar como para
descifrar y el criptosistema asimétrico, emplea una doble
clave (kp; kP) en donde kp se es la clave privada y kP se
conoce como clave pública las cuales una de ellas sirve para
la transformación E de cifrado y la otra para la
transformación D de descifrado.
Una de las mejores técnicas en el campo de los cifradores
asimétricos es la criptografia de curvas elípticas (ECC)
planteado por Koblitz y Miller [3], [4] la implementación
de estas curvas resulta más eficiente que la aritmética
módulo.
Implementación de matrices en sistemas criptográficos de ECC.
Héctor Oviedo Galdeano1, José Antonio López Toledo
2
1,2Departamento de Telecomunicaciones, SEPI-ESIME, IPN, México D.F., México
Teléfono (55) 57296000 Ext.54782 E-mail: [email protected], [email protected]
63
INGENIERÍA EN TELECOMUNICACIONES XII CONGRESO NACIONAL DE INGENIERÍA
ARTÍCULOS ACEPTADOS POR REFEREO ELECTROMECÁNICA Y DE SISTEMAS
MÉXICO D.F. NOVIEMBRE 2010 890
III. CURVA ELÍPTICA
Una curva elíptica se puede definir como:
2 3 2y x ax b (2)
En donde (2) es llamada ecuación de Weierstrass.
Para que las curvas elípticas presenten una mayor
seguridad tiene que cumplir con la condición discriminante:
3 24 27 0a b (3)
Fig. 1 Curva Elíptica
Para graficar la Fig. 1 se utilizo (2) y (3), los valores
que se asignaron en (2) fueron:
1; 1a b
Donde (2) se evaluó los valores y resulto
2 3 21 sobre y x x (4)
La Fig. 1 corresponde a la evaluación de (4) en donde la
condición (3) si se cumple en (4) por lo tanto en la Fig. 1 no
tiene raíces múltiple, existe un punto especial O, llamado
punto al infinito, es decir, es un punto imaginario situado
por encima del eje x a una distancia infinita por lo que no
tiene un valor en concreto, con el punto especial más la
operación suma, es lo que se denomina grupo de curva
elíptica E(R)[4][5].
Las curvas elípticas en un cuerpo de Galois Gf( n), es un
grupo finito generado por n, siendo n un número primo
impar [3], los pares de puntos que se obtendrán estarán
definidos sobre este campo, cumpliendo con la restricción
0,1, ..., 1p
p donde p es un número primo impar[5],
por lo tanto la curva elíptica definida en p
como:
2 3m od( )y x ax b p (5)
En donde para formar las parejas de puntos
( , ) | ,p
x y x y de la curva Elíptica ( )p
E se utilizará (5)
siempre y cuando se cumpla la condición.
3 24 27 0(m od )a b p (6)
Al conjunto de los pares de puntos de ( )p
E se agrega
el punto al infinito.
Para generar los pares de puntos de la curva ( )p
E
hay dos formas:
Sin conocer ningún punto de la curva
Conociendo un par de puntos de la curva
En la ecuación (5) se asignan valores a las variables y se
comprueba que el valor del discriminante sea diferente de
cero, por ejemplo
1, 1 23a b y p
Al sustituir los valores en (5) se obtiene
2 31 m od(23)y x x (7)
Al sustituir los valores de (7) en la condición (6) esta
se cumple por lo tanto (7) tendrá un grado de seguridad.
Una vez que se tiene la ecuación de Weierstrass (7)
definida en un campo cuyos valores en nuestro caso serán
menores a 23, lo que prosigue es calcular las parejas de
puntos que pertenezcan a ( )p
E
Primero se hará el cálculo de los pares de puntos en la
curva sin conocer ningún punto de ella y después se hará a
partir de un punto.
Sea
2 31 m o d (2 3)z y x x (8)
64
INGENIERÍA EN TELECOMUNICACIONES XII CONGRESO NACIONAL DE INGENIERÍA
ARTÍCULOS ACEPTADOS POR REFEREO ELECTROMECÁNICA Y DE SISTEMAS
MÉXICO D.F. NOVIEMBRE 2010 891
IV. LA LEY DE RECIPROCIDAD CUADRÁTICA
Esta ley relaciona la solubilidad de congruencias de
segundo grado mediante el teorema:
Teorema.- Sea p un primo impar. Un entero h, coprimo
o primo relativo con p, es un residuo cuadrático módulo p, si
existe una x tal que 2x h mod (p), En caso contrario h es
un no-residuo cuadrático modulo p.
Dados un primo impar p y un entero cualquiera h, el
símbolo de Legendre está definido como:
1 si a es un residuo cuadrático m od(p)
1 si a no es un residuo cuadrático m od(p )
0 si h es m ultip lo de p
h
p (9)
El criterio de Euler está dado por
1
2 m od( )
ph
h pp
(10)
Tabla 1.Construccion de valores de la ECC utilizando la ley
de la Reciprocidad cuadrática.
Para realizar el cálculo de los puntos se utiliza la tabla. 1
en donde se explicará cómo es que se obtuvieron esos datos
que aparecen en ella.
El procedimiento es el siguiente:
En la columna 1 se escriben los valores de x
con x p dado que se está trabajando con
aritmética modulo 23.
Se evalúa (8) con los valores de x, el resultado se
asigna a la variable z.
Se obtienen los residuos cuadráticos y no
cuadráticos, para ello se utiliza el criterio de Euler
y el símbolo de Legendre en donde la variable h
será sustituida por la variable z.
Para formar las parejas de punto los residuos no
cuadráticos no se utilizan solamente los cuadráticos.
Se puede observar en la tabla 1 en la columna de
residuos que hay trece valores de unos (+) y por lo tanto, el
conjunto de pares de puntos de la curva elíptica será el doble
de unos esto es 26 debido a que (7) es una ecuación
cuadrática. Se agrega la pareja con residuo cuadrático con
valor cero y el punto al infinito O.
Para poder formar la pareja de puntos de la curva
( , ) | ,p
x y x y , en la tabla 2 se puede observar que solo se
tiene los residuos cuadráticos, por lo tanto ya se conoce los
valores de que tomara p
x , ahora solamente nos falta
conocer los valores de p
y , donde para encontrar y se
utiliza la ley de la reciprocidad cuadrática con la siguiente
modificación:
2
m od( )p y h p (11)
En la ecuación (11) lo valores que tomará p
y los
resultados de evaluar (11) se muestran en la tabla 3, para
sintetizar estos resultados solamente se colocaron en la
tabla los que se utilizará para encontrar los valores de la
ordenada y así ya poder formar la pareja de puntos de la
curva elíptica.
x z Residuos x z Residuos
0 1 1 12 16 1
1 3 1 13 3 1
2 11 -1 14 22 -1
3 8 1 15 10 -1
4 0 0 16 19 -1
5 16 1 17 9 1
6 16 1 18 9 1
7 6 1 19 2 1
8 15 -1 20 17 -1
9 3 1 21 14 -1
10 22 -1 22 22 -1
11 9 1
65
INGENIERÍA EN TELECOMUNICACIONES XII CONGRESO NACIONAL DE INGENIERÍA
ARTÍCULOS ACEPTADOS POR REFEREO ELECTROMECÁNICA Y DE SISTEMAS
MÉXICO D.F. NOVIEMBRE 2010 892
Tabla 2. Residuos Cuadráticos
La interpretación de la Tabla 3 para conseguir los
valores respectivos de las ordenadas es el siguiente:
Donde se considera h de la tabla 3 y x, z de la tabla 2
p=23
for i = 1 to length (x)
if ( ) ( )h i z i then
puntos (x(i),mod(y(i),p)) and
puntos (x(i),mod(y(p-y(i))
end
end
Con este algoritmo se explica cómo se formaron los
puntos que pertenecen a la curva elíptica.
Tabla 3. Valores de y para el par de puntos de ECC
y h y h
0 0 10 8
1 1 11 6
2 4 15 18
3 9 16 3
5 2 17 13
6 13 19 16
8 18 22 1
9 12
Tabla 4. Pares de puntos de (8)
En la tabla 4. Se encuentran las parejas de puntos que
pertenecen ECC (8) los cuales se obtuvieron como se
mencionó anteriormente, en (8) se puede ver que los
resultados obtenidos tendrán dos valores debido a que la
función es cuadrática, esto se refleja en la tabla 4. Donde un
punto P tiene un punto –P que son simétricos a la curva
elíptica, no habrá simetría cuando aparezca en los residuos
cuadráticos el valor cero.
. En la segunda columna de la tabla 4 nos indica el
orden, los cuales a partir de un punto se genera un máximo
número de puntos, por ejemplo el punto 23
(1, 7 ) es
capaz de generar a partir de este, 27 puntos más el punto al
infinito
V. OPERACIONES DE LAS ECC.
Para poder realizar operaciones de adición entre los
puntos de la curva elíptica debemos de considerar las
siguientes condiciones.
1.- Identidad
para toda ( )P P P P E
2.- Negativos
Si ( , ) ( ), entonces ( , ) ( , )
E l punto ( , ) es denotado por
P x y E x y x y
x y P
x z Residuos Cuadráticos x z Residuos Cuadráticos
0 1 1 17 9 1
1 3 1 18 9 1
3 8 1 19 2 1
4 0 0
5 16 1
6 16 1
7 6 1
9 3 1
11 9 1
12 16 1
13 3 1
66
INGENIERÍA EN TELECOMUNICACIONES XII CONGRESO NACIONAL DE INGENIERÍA
ARTÍCULOS ACEPTADOS POR REFEREO ELECTROMECÁNICA Y DE SISTEMAS
MÉXICO D.F. NOVIEMBRE 2010 893
3.- Adición de puntos
1 1 2 2
3 3
C onsiderando ( , ) ( ) ( , ) ( )
donde P Q . C uando P +Q =( , )
P x y E y Q x y E
x y
2
2 1 2 1
3 1 2 3 1 3 1
2 1 2 1
( )y y y y
x x x y y x x yx x x x
4.- Suma de puntos consigo mismo
22 2
1 1
3 1 3 1 3 1
1 1
3 32 ( )
2 2
x a x ax x y y x x y
y y
Para generar una serie de puntos dado un punto
conocido, lo que se hace es utilizar la condición de la suma
de puntos consigo mismo y después la condición de la
adición de puntos, una de las herramientas utilizadas aquí es
el algoritmo de Euclides extendido. Dado el punto
23(1, 7 ) de (8) ver resultados en la Tabla 5
Tabla 5. Generar puntos dado un punto de ECC
Para que se tenga una mayor seguridad en los sistemas
criptográficos, se puede realizar las siguientes
consideraciones:
Aumentar el tamaño de la curva elíptica, pero se
requiere de un esfuerzo computacional elevado para calcular
el número de puntos de la curva. La otra opción es transmitir
varios puntos de la misma curva en forma independiente, el
esfuerzo computacional es diferente, ya que se aprovecha la
información obtenida de los puntos ya calculados para
reducir la complejidad del siguiente.
VI. DESCRIPCIÓN DEL SISTEMA
Considerando una curva elíptica p= #E(Fq), sea n un
entero positivo
Donde es el conjunto de todas las matrices de
tamaño n x n con elementos en Fp y es el conjunto de n-
tuplas de puntos.
Fp: Campo finito que contiene elementos q=p donde p es un
valor primo
Fq: Campo finito que contiene q elementos. Para la ANSI
X9.62, nos dice que (q = p, p > 3) o de una potencia de 2 (q
= 2m).donde m es un entero positivo.
Se trabaja con las siguientes consideraciones para construir
el sistema
(12)
En la ecuación (12) los valores P0, P1, …,Pn-1 son
conocidos.
Se realiza un ejemplo de la construcción de este sistema.
22
61
50
a
a
a
La construcción de A es la siguiente:
( ) ( ) ( )n n
M at F xE F E Fn p q q
( )M at Fn p
S i A = [a ] para 0 i,j n -1 y,
0 0
1 1=
1 1
i j
P Q
P QA
P Qn n
1
,0
nQ a P
i i j jj
1 5 8
10 9 6 m od 23
3 2 4
E n fo rm a aleato ria escogem os elem en tos q ue in teg raran
a A , estos serán elem etos de la llave p rivada
M
67
INGENIERÍA EN TELECOMUNICACIONES XII CONGRESO NACIONAL DE INGENIERÍA
ARTÍCULOS ACEPTADOS POR REFEREO ELECTROMECÁNICA Y DE SISTEMAS
MÉXICO D.F. NOVIEMBRE 2010 894
2 ( ) (13 )
2 1 0
(14 )
A a M a M a I
A
su stitu yen d o en (1 3 )
7 5 6 6 7 0 1 5 8 1 0 0
2 1 1 8 1 4 3 1 5 8 6 1 0 9 6 5 0 1 0
3 5 4 1 5 2 3 2 4 0 0 1
La matriz M es de 3 x 3 por lo tanto
En la tabla 5. Se observa que a partir del punto 23
(1, 7 )
generamos un conjunto de puntos, para hacer de una
manera amigable el ejemplo se tomaron los primeros tres
valores k de la tabla 5
(4 , 0 )11
(3,10 )21
(11, 20 )31
Ahora bien, partiendo de (15) para encontrar los valores de
las llaves privadas de (13) se construirá un sistema de
ecuaciones lineales para encontrar los valores a2, a1, a0 ya
que estos el destinatario no los conoce, teniendo esto ya
podremos intercambiar la llave para poder descifrar los
datos que se envíen, los cuales deben de estar codificados en
ECC.
VII. CONCLUSIONES
La criptografía a tomado gran importancia, al utilizar
matrices lineales, se puede transmitir varios puntos, ahora
bien para aumentar la complejidad del sistema criptográfico
se pretende utilizar el NIST (Instituto Nacional de
Estándares y Tecnología) aplicado sobre campos primos
donde los valores de a, b, p ya se encuentran definidos, en
donde por ser números grandes se tendrá mayor seguridad,
en comparación con sistemas criptográficos que utilizan la
aritmética módulo.
REFERENCIAS
[1] John Talbot “Complexity and Cryptography An Introduction”
Cambridge University
[2] Alfred J. Menezes “Handbook of Applied Cryptography” [3] Darrel Hankerson, Alfred Menezes, Scott Vanstone “Guide to Elliptic
Curve Cryptography” Springer [4] Daniel R. L. Brown “ Elliptic Curve Cryptography”, May 21, 2009 [5] Daniel R. L. Brown “Recommended Elliptic Curve Domain
Parameters”, January 27, 2010
{ , 2 , 3 }
(1, 7 )
P P P
P
lo s valo res de (14 )
0 1 4 (1, 7 )
20 0 7 (7 , 11)
19 2 18 (18, 20 )
S e resuelve la m atriz an terio r
0 * (1, 7 ) 1 * (7 , 11) 4 * (18, 20 )
20 * (1, 7 ) 0 * (7 , 11) 7 * (18, 20 )
19 * (1, 7 ) 2 * (7 , 11) 18 * (18, 20 )
Se sustituye en
A plicando p rop iedades de la sum a de pun tos
E C C , e l resu ltado es e l s igu ien te :
0 (7 , 11) (5 , 19 )
(13, 16 ) 0 (11, 20 )
(9 , 7 ) (17 , 20 ) (7 , 12 )
resu ltad o fin al d e la m atriz es :E l
15
La ecuación (14) con los valo res sustitu idos resu lta
0 1 4 (1, 7 ) ( 4 , 0 )
20 0 7 (7 ,11) (3,10 )
19 2 18 (18, 20 ) (11, 20 )
68
[Añ
A
l
e
j
a
n
d
r
o
[
NOVIEMBRE 2010 Número 6, Volumen 2, Año 2
RISCE Revista Internacional de Sistemas Computacionales y Electrónicos
69
72
Curiosidades sobre la Criptografía en hechos que dejaron marca en el mundo.
Héctor Oviedo Galdeano, José Antonio López Toledo
[email protected] [email protected] Instituto Politécnico Nacional. Unidad Profesional Adolfo López Mateos. Av. Instituto Politécnico Nacional
s/n. Edificio 1, 2do. Piso. 57296000 Ext. 54782
RESUMEN. En el presente artículo de divulgación se hace una semblanza de cómo la criptografía ha ido evolucionando a través del tiempo para ofrecer cada vez una mayor seguridad. Grandes personajes que intervinieron en la revolución mexicana cifraban sus mensajes empleando cada uno de ellos su propio código, entre estos están Porfirio Díaz y Carranza, anterior a ellos, en el siglo XIX, por ejemplo, José Mariano Michelena también recurría a esta técnica. Un caso interesante fue la aparición de la máquina Enigma, que durante la segunda guerra mundial fue usada por los alemanes para cifrar sus mensajes. También se recurrió al cifrado oral, como en el caso de los indios navajos utilizados por el ejército americano en la guerra del pacífico. PALABRAS CLAVES. Criptografía, criptografía clásica, telegrama Zimmerman, Máquina Enigma INTRODUCCIÓN Muchos de nosotros recordamos como nos emocionamos con la película “Juegos de guerra” que se estrenó en 1983. Vimos al jovencito David Lightman interpretado por el actor Matthew Broderick entrar sin saberlo a la red de computadoras del NORD (North American Aerospace Defense Command) y cree que la máquina a la que se ha conectado lo invita a un juego llamado “Guerra termonuclear global” lo que acepta gustoso sin pensar que estaba iniciando realmente una guerra termonuclear contra la URSS de alcances inimaginables. Afortunadamente como sucede en las películas se tuvo un final feliz[1]. Parece increíble, pero el 26 de septiembre de ese mismo año estuvo a punto de iniciarse en la vida real y no en película, una guerra nuclear que pudo haber terminado con los seres humanos en el planeta. Por un error del sistema satelital ruso que detecta los ataques de misiles nucleares americanos se envió la señal de alarma indicando que cinco misiles nucleares americanos se dirigían a territorio soviético. El teniente coronel Stanislav Petrov estaba al frente del búnker Serpujov-15 desde donde se coordinaba la defensa aeroespacial rusa. Por esos días se vivía mucha tensión debido a que una semana antes los cazas soviéticos habían derribado un avión de pasajeros coreano con 269 personas a bordo encontrándose entre ellos varios pasajeros norteamericanos. Para fortuna nuestra, el coronel Petrov utilizó su sentido común y pensó que un ataque nuclear no se inicia con solo cinco misiles y prefirió esperar y ver lo pasaba. ¿Qué hubiera sucedido si reacciona como fue entrenado y dispara a su vez los misiles? Sus jefes se enojaron con él porque no procedió de acuerdo a las órdenes bajándolo de puesto y ocultaron el incidente. Este hombre salvó la vida de millones de seres humanos sino es que de toda la humanidad [2]. Lo anterior nos hace pensar en lo vulnerable que pueden resultar los sistemas tecnológicos por avanzados que sean. Uno de estos sistemas son los de telecomunicaciones que presentan vulnerabilidad en cuanto a la seguridad. Son muchos los casos notificados de ataques a las redes cibernéticas por los llamados hackers. Un ejemplo es el del joven de secundaria entre los 15 y 16 años de edad que logró ingresar en las computadoras del Pentágono en Washington. Al cuestionar al joven los agentes de FBI se dieron cuenta que tenía un cómplice, un compañero de clase del colegio secundario Cloverdale High School, quien lo ayudaba a planear sus incursiones cibernéticas[3]. Otro caso es el de Gary McKinnon hacker Británico acusado por los E.U. de haber perpetrado “el mayor ataque informático militar de todos los tiempos” quien se introdujo ilegalmente a 100 redes y más de 300 computadores de la Nasa, el Ejército, la Marina, el Departamento de Defensa y la Fuerza Aérea estadounidense, dañando la red informática de defensa que estuvo fuera de servicio por casi una semana, puso en jaque los sistemas militares, robando cientos de contraseñas, elimino 1,300 cuentas de usuario. Si es procesado puede alcanzar hasta 70 años de cárcel [4].
70
73
A principios de febrero del 2010 John Chipman, director del Instituto Internacional de Estudios Estratégicos (IISS por sus siglas en inglés) informó que “con el uso de computadoras, una potencia extranjera puede inutilizar la infraestructura de un país, atacar la integridad de los datos militares internos de otra nación, intentar confundir sus transacciones financieras o lograr cualquiera de sus otros posibles objetivos”, esto es, un ataque cibernético coordinado y masivo, y no el clásico lanzamiento de misiles, puede marcar el comienzo de las guerras en el futuro[5]. Como se ve, la seguridad informática y de telecomunicaciones es una gran preocupación a nivel mundial. Existe una lucha diaria entre los responsables de la seguridad de los sistemas y los que tratan de violarla. CRIPTOGRAFÍA CLÁSICA.
Una herramienta utilizada por los expertos en seguridad es la criptografía que es el arte o ciencia de enviar mensajes de manera escondida, de tal manera que sólo un destinatario autorizado, es decir, que cuente con la clave puede conocer el contenido del mensaje, por lo cual puede permitir el intercambio de información entre ellos [6]. Se tienen indicios de mensajes cifrados en jeroglíficos egipcios que datan de más de 4500 años. Los griegos en el siglo V A.C. durante la guerra entre Atenas y Esparta utilizaban el escítalo que consta de un rodillo de longitud y grosor determinado en donde el cifrado se basaba en la alteración del mensaje original introduciendo símbolos innecesarios que desaparecían al enrollar el mensaje en un rodillo. Si se interceptaba el mensaje era muy difícil descifrarlo si no se conocían el grosor y la longitud del rodillo [7], en la (fig. 1) se observa un claro mensaje que es SECRETOS si se rota se podrá identificar el siguiente mensaje y así sucesivamente.
Fig. 1 Escítalo
El académico griego Polybius (203-120 A.C.) usó una tabla para cifrar sus mensajes la cual consiste de cinco filas y cinco columnas. En cada cuadro formado por una fila y una columna se coloca una letra del alfabeto. El mensaje cifrado se envía por medio de las parejas formadas por el número de fila y el número de columna.
71
74
Se sabe de un libro de criptografía militar que desgraciadamente se ha extraviado que se cree utilizaba Julio Cesar. También se dice que usaba un corrimiento de tres lugares del alfabeto para cifrar los mensajes, por ejemplo a la A le correspondía la letra D, a la B le correspondía la letra E y así sucesivamente. Esto se conoce como sustitución simple. CRIPTOGRÁFIA CLÁSICA EMPLEADA POR PERSONAJES NOTABLES EN MÉXICO. Respecto a la criptografía en el nuevo mundo y en particular en México, se sabe que en el año 1500, el gobernador Francisco de Bobadilla remitió a los Reyes Católicos diversas cartas cifradas enviadas por Cristóbal Colón a su hijo Diego, en las que le recomendaba como debía ser su conducta en caso de que el comisionado del rey le encarcelase. Se conoce una carta cifrada que Hernán Cortés envió desde Cuernavaca el 25 de junio de 1532 y que en la actualidad se conserva en el Museo Nacional de Arqueología, Historia y Etnografía de México. En la elaboración de este criptograma, considerado como uno de los más antiguos del Nuevo Mundo, Cortés utiliza sustituciones homofónicas1 monoalfabéticas2, mediante las cuales cada letra era representada por dos o tres símbolos, tanto literales como numéricos. El mismo método aplicó en la carta que escribe desde el Puerto de Santiago el 20 de junio de 1532, y cuyo original obra en los autos seguidos en 1546 por el licenciado Francisco Núñez contra el marqués del Valle, por pago de devengados. En general los virreyes, los miembros de las órdenes religiosas y los particulares usaron durante la Colonia la criptografía por sustitución simple para sus comunicaciones ya sea entre poblaciones del nuevo mundo o con la península. Por ejemplo, se conoce, entre otras la carta que el virrey de Nueva España Luis de Velasco envía desde Cholula el 18 de octubre de 1550 al rey Carlos V la cual contiene caracteres cifrados en diversos fragmentos de la misma. Era tan común el uso de la criptografía entre particulares que hubo intentos de prohibirla por temor a que los inconformes se comunicaran entre ellos e intentaran levantarse sin que la autoridad se percatase por no entender sus mensajes. Ya en 1818 el virrey Ruiz de Apodaca envió cartas a la península encriptadas. Durante la guerra de independencia era conocido que los criollos en diversas ciudades y que estaban dentro de la conspiración usaban la criptografía para sus comunicaciones, desgraciadamente no se han encontrado documentos de Hidalgo o Morelos que estén cifrados pero no es difícil pensar que usaban la criptografía para intercambiar mensajes [8]. Años después, ya en el México independiente, don José Mariano Michelena representando al gobierno mexicano ante la corona inglesa, viajó a Londres en 1824 como agente confidencial para la firma de tratados comerciales. Los informes que presentó al Secretario del Despacho de Relaciones Interiores y Exteriores don Lucas Alamán fueron en forma cifrada, utilizando el llamado método de sustitución poli alfabético, el cual se detalla más adelante. Como un ejemplo, se tiene la carta del 6 de noviembre de 1824 (fig. 2) donde Michelena le reporta los resultados sobre las estrategias seguidas frente a los representantes diplomáticos de Argentina, Colombia y Chile. Un fragmento de la carta contiene el siguiente mensaje cifrado[9]:
72
75
Mm h x e h r h c f u g f s g f r q f u x s r t b i m t b o n m g q r d l z u o d d i c d zd i g j u l d p x l m x t n z x l i m s h i m o f g j q x s q l c e r o y i i u b x h x f q x s e r q f u x s e x q g z x u b x p x l t e m f y j b f z d t d m l g e m i m r o z q d t j b l l m q n s n o m m o l l e s c v h x f i i m i i x l j v i h i y q p a l j a z m j e e y q y h i j v l h y q l g i l l a i m v a y q e z m f q v m o y a a y u v d m i l g e t j l l q r d r a v r p i g h s n x f u x l u y h v f
El texto del fragmento anterior descifrado es el siguiente. “He comunicamo (sic) a los ministros de colombia Y chile y al que dyrige los asuntos de buenos Ayres mis pasos dados con este ministe rio todos los han aprobado y estan de acurdo (sic) Estamos igualmente conveni dos en que si ynglaterra sigue en su sistema De entretenernos urgire hasta obtener una decision positiva” Como se mencionó, el tipo de criptosistema que utilizó Michelena es de sustitución polialfabética3, atribuido a Blaise de Vigenère el cual es un agregado de cifras monoalfabéticas4 del modelo de sustitución inventado por Julio César. En la tabla 1 se muestra la sustitución polialfabética[9] . Supongamos que deseamos enviar por ejemplo, la palabra “SECRETOS” la cual tiene una longitud de 8 letras. Escogemos una palabra clave para que nos indique el orden de selección de los alfabetos de la tabla, esta puede ser de cualquier longitud, en nuestro ejemplos hemos elegido la palabra “HOGAR”.
Fig 2. Carta del 6 de noviembre de 1824[9]
73
76
Tabla 1.- Criptografía diplomática mexicana [9]
Como se aprecia en la tabla 2 el mensaje cifrado resultante es “ZSIRVACY” el cual es ininteligible. Observe que la clave en nuestro ejemplo tiene una longitud de 5 letras, por lo que se tiene que repetir las veces que sean necesarias para cubrir la longitud de cada renglón de texto del mensaje.
Tabla2.- Ejemplo de un mensaje cifrado de Vigenère.
74
77
Se sabe que durante la guerra de Reforma y el imperio de Maximiliano, tanto liberales como conservadores mantenían correspondencia cifrada, pero desgraciadamente no encontramos un ejemplo para mostrar. En el siglo XX, Porfirio Díaz utilizó los métodos de sustitución para comunicarse con gobernadores y jefes militares importantes. Su secretario particular, Don Rafael Chousal, fue el encargado de seleccionar los métodos criptográficos que se deberían usar. El método de sustitución simple, consiste en que cada uno de los caracteres de un alfabeto se sustituye por una cadena de símbolos numéricos, para descifrarlo, cada entero es sustituido por la letra correspondiente, este tipo de sistema criptográfico al ser el más simple tiene gran vulnerabilidad ya que con mucha facilidad se puede deducir cual es la regla de sustitución, como un ejemplo de sustitución directa o simple se tiene la tabla mostrada abajo y es la que usó don Porfirio.[10],[11] Se desea transmitir el texto “HOLA A TODOS”. De acuerdo a la tabla, el mensaje encriptado resulta: 4 18 20 11 11 22 18 12 18 26 . Para hacerlo menos vulnerable, se le puede asignar a cada símbolo varios números como se muestra en la siguiente tabla:
A 11 21 31 N 75 85 95 B 79 89 99 Ñ 70 80 90 C 10 20 30 O 16 26 36 CH 71 81 91 P 49 59 69 D 48 58 68 Q 46 56 66 E 19 29 39 R 43 53 63 F 41 51 61 RR 15 25 35 G 18 28 38 S 72 82 92 H 17 27 37 T 74 84 94 I 13 23 33 U 12 22 32 J 47 57 67 V 77 87 97 K 44 54 64 W 45 55 65 L 14 24 34 X 42 52 62 LL 40 50 60 Y 76 86 96 M 78 88 98 Z 73 83 93
Para el mismo ejemplo, ahora el texto cifrado resulta 27 36 14 22 11 94 16 68 16 92 Al iniciarse la Primera Guerra Mundial, el káiser Guillermo II había prometido una victoria rápida sobre Inglaterra, como no lo estaba logrando recurrió a la llamada “guerra marítima sin restricciones” que consistía en que cualquier barco de guerra o mercantil, enemigo o neutral, encontrados alrededor de las costas de Inglaterra seria hundido. Uno de esos barcos fue el trasatlántico de lujo inglés Lusitania que fue hundido por submarinos alemanes el 26 abril de 1915, lo que provocó que el 6 de abril de 1917 EEUU le declarara la guerra a Alemania. En un intento de evitar que los norteamericanos entraran a la guerra, los alemanes le ofrecieron al presidente mexicano Venustiano Carranza ayudarlo a reconquistar los territorios arrebatados a México durante la guerra de 1848 si México le declaraba la guerra a EEUU. EL TELEGRAMA ZIMMERMAN
El 16 de Enero de 1917, Arthur Zimmerman, Secretario de Relaciones Exteriores Alemán, telegrafió al embajador de su país en los Estados Unidos, Johann von Bernstorff, el ofrecimiento a Carranza descrito anteriormente mediante un mensaje cifrado utilizando (fig. 3) el código conocido como “0075”. El embajador en EEUU lo retransmite a su colega en la Ciudad de México Heinrich Von Eckhardt pero con un código diferente, el “13040”, los criptógrafos descifraron primeramente fragmentos del telegrama que usó el código 0075, pero cuando se retransmitió con el código “13040” lo pudieron descifrar completamente. Se conocía como “cuarto 40” a la sección encargada de descifrar los mensajes. Este grupo de criptógrafos había tenido mucha suerte cuando un pescador ruso atrapó en sus redes un pesado libro que contenía el código secreto criptográfico que les permitía descifrar los mensajes. Este libro procedía del barco de guerra alemán
A B C CH D E F G H I J K L LL M 11 9 10 23 12 19 1 27 4 28 7 16 20 6 17 N Ñ O P Q R RR S T U V W X Y Z 3 30 18 24 15 13 21 26 22 14 8 5 29 25 2
75
78
Magdeburg hundido frente a las costas de Finlandia. El libro contiene listas en donde se relacionan una cifra a un texto[12],[13],[14]
El mensaje desencriptado dice lo siguiente: [14]
Nos proponemos comenzar el primero de febrero la guerra submarina, sin restricción. No obstante, nos esforzaremos para mantener la neutralidad de los Estados Unidos de América. En caso de no tener éxito, proponemos a México una alianza sobre las siguientes bases: hacer juntos la guerra, declarar juntos la paz; aportaremos abundante ayuda financiera; y el entendimiento por nuestra parte de que México ha de reconquistar el territorio perdido en Nuevo México, Texas y Arizona. Los detalles del acuerdo quedan a su discreción [de Von Eckardt]. Queda usted encargado de informar al presidente [de México] de todo lo antedicho, de la forma más secreta posible, tan pronto como el estallido de la guerra con los Estados Unidos de América sea un hecho seguro. Debe además sugerirle que tome la iniciativa de invitar a Japón a adherirse de forma inmediata a este plan, ofreciéndose al mismo tiempo como mediador entre Japón y nosotros. Haga notar al Presidente que el uso despiadado de nuestros submarinos ya hace
previsible que Inglaterra se vea obligada a pedir la paz en los próximos meses.
Fig 3.Telegrama Zimmerman cifrado [14]
Durante la segunda Guerra Mundial los alemanes y las Potencias del Eje utilizaron la máquina Enigma para encriptar sus mensajes (fig. 4), esta era un dispositivo electromecánico cuyo creador fue el alemán Arthur Scherbius quien fundó la empresa Chiffriermaschinen Aktien Gesellschaft en Berlín poniendo a la venta la primera versión comercial, la Enigma-A en 1923, siendo su finalidad facilitar la comunicación de documentos entre comerciantes y hombres de negocios de forma secreta. Hubo tres versiones comerciales y la más importante fue Enigma-D en 1926. [15], [16]
76
79
Fig 5. Maquina enigma [15]
Fig 4. Soldados utilizando la Maquina Enigma [16]
TRANSMISIÓN DE MENSAJES CON LA MÁQUINA ENIGMA.
La máquina Enigma consiste de las teclas que son interruptores eléctricos, un engranaje mecánico y un panel de luces con las letras del alfabeto (Fig. 5). El funcionamiento de esta máquina es similar al de una máquina de escribir mecánica. En el interior de la máquina se podían introducir varios rotores ya que existen ranuras para esto; los rotores cambiaban una letra por otra (fig. 5). Los contactos de salida de un rotor se conectaban a los contactos de entrada del rotor siguiente. Uno de los últimos mensajes codificado por la máquina Enigma fue enviado por un submarino, el cual se logró descifrar hasta el mes de Febrero de 2006 y fue gracias a la ayuda del “Proyecto-M4”. El mensaje decía así [16]: nczwvusx pnyminhz xmqxsfwx wlkjahsh nmcocca kuqpmkcsm hkseinjus blkiosxck ubhmllxcs jusrrdvko hulxwccbg vliyxeoahx rhkkfvd rewezlxo bafgyujqukg rtvukameu rbveksuh hvoyhabcj wmaklfkl myfvnrizrv vrtkofdanj molbgffl eoprgtflvr howopbekv wmuqfmpw parmfhagkxiibg Una vez desencriptado: Señal de radio 1132/19. Contenido: Forzados a sumergirnos durante ataque, cargas de profundidad. Última localización enemiga: 8:30h, cuadrícula AJ 9863, 220 grados, 8 millas náuticas. [Estoy] siguiendo [al enemigo]. [El barómetro] cae 14 milibares. NNO 4, visibilidad 10
Por otro lado, los norteamericanos utilizaron un método de cifrado oral durante la guerra en el pacífico contra los japoneses. Dado que solamente 30 personas en el mundo además de los navajos hablaban su lengua, la que no tiene escritura siendo todos ellos norteamericanos, la marina enlistó a 200 navajos para que sirvieran de encriptadores y desencriptadores de mensajes orales. La idea fue de Philip Johnston que hablaba con fluidez esta lengua dado que era hijo de un misionero que predicaba entre los navajos. [17].
77
80
Después de estos sucesos, la criptografía ya no se consideraba un arte que solo resultaba útil a los políticos y militares, y se empezó a considerar una ciencia. En 1949, C.E. Shannon, padre de la teoría de la información utilizó la criptografía para establecer la base teórica de esta ciencia que estudia la escritura oculta, la criptografía hizo suyo el problema de la transmisión de claves y buscó soluciones para poder transmitir textos cifrados sin tener necesidad de intercambiar claves legibles, existen claves privadas y públicas que ayudan a enfrentar este tipo de problema. Un sistema de clave privada o simétrica es aquel que utiliza la misma clave para el cifrado y el descifrado del mensaje, esto quiere decir que la clave la deben de tener tanto el emisor como el receptor.
Los cifrados asimétricos o de clave pública, consiste en que cada usuario posea un par de claves, una pública y una privada. Si quiero enviar un mensaje por ejemplo a la persona A, el procedimiento sería el siguiente, se encripta el mensaje según la clave de la persona A, que es pública, en el sentido de que cualquiera puede conocerla, pero sólo la persona A, con su clave privada, la puede descifrar. Entre otras, una de las ventajas de este método es que la clave secreta de la persona A, la privada, nunca circula por los medios de comunicación y, por tanto, no es necesario renovarla constantemente.
La criptografía es la disciplina matemática, las matemáticas proporciona la justificación teórica de la fortaleza de un algoritmo o protocolo particular, está disciplina ha ido crecido con los años para enfrentar una mejor fortaleza para la seguridad de la información, aunque no siempre nos permita demostrar la seguridad que presenta los algoritmos, lo que si nos puede proporcionar es un medio para investigar sistemáticamente su seguridad [15],[6].
1Las palabras que se pronuncian igual, pero se escriben de forma diferente se llaman homófonas. 2En la sustitución monoalfabética, también conocida como sustitución simple, se sustituye cada uno de los caracteres del texto original por otro, de acuerdo con una tabla pre-establecida, para obtenerse el texto cifrado. Como consecuencia, la frecuencia de ocurrencia de las letras (números o símbolos) del mensaje cifrado es la misma que la frecuencia de ocurrencia de las letras de la lengua usada en el mensaje original. 3Sustitución polialfabética es cuando se utilizan múltiples alfabetos. 4cifras monoalfabéticas es donde cada letra del texto en claro es sustituida por otra letra en el texto cifrado.
REFERENCIAS. [1] http://es.wikipedia.org/wiki/Juegos_de_guerra
[2]http://noticiasinteresantes.blogcindario.com/2007/10/00906-stanislav-petrov-el-hombre-que-evito-un-holocausto-nuclear.html
[3]http://edant.clarin.com/diario/1998/02/28/i-03401d.htm
[4]http://www.nodo50.org/tortuga/Gary-McKinnon-un-hacker-o-un
[5]http://www.abc.es/hemeroteca/historico-04-02-2010/abc/Internacional/los-proximos-conflictos-empezaran-con-un-ataque-cibernetico-masivo_1133530440627.html
Pino Caballero Gil. “Algunos hitos de la criptografía del siglo XX” [6]http://www.sinewton.org/numeros/numeros/43-44/Articulo82.pdf
[7]http://personal.telefonica.terra.es/web/jms32/Cifra/CodSecretos/Cap01/Cap01.html
Galende Díaz Juan Carlos “Sistemas criptográficos empleados en Hispanoamérica” [8]http://revistas.ucm.es/ghi/11328312/articulos/RCHA0000110057A.PDF Narváez Roberto “La Criptografía Diplomática Mexicana en la Primera Mitad del siglo XIX” [9]http://www.ucm.es/info/documen/articulos/art_sexta/004.pdf José de Jesús Ángel Ángel y Guillermo Morales-Luna “Breve descripción de la Criptografía en la Revolución Mexicana” [10]http://www.revista.unam.mx/vol.9/num3/art18/art18.pdf
78
81
José de Jesús Angel Angel y Guillermo Morales-Luna “Algunos Sistemas Criptográficos durante la Presidencia de Porfirio Díaz” [11]http://computacion.cs.cinvestav.mx/~jjangel/histo/PD.pdf Bernardo Fernández Bef “El telegrama Zimmermann” [12]http://www.bicentenario.gob.mx/bdb/bdbpdf/NBNM/R/22.pdf Juan Ramón Jiménez de León “Telegrama Zimmermann” [13]http://yumka.com/docs/zimmermann.pdf [14] http://es.wikipedia.org/wiki/Telegrama_Zimmermann [15]http://www.ciencias.iesbezmiliana.org/revista/index.php?option=com_content&task=view&id=37&Itemid=26&limit=1&limitstart=1 [16]http://wanlinksniper.blogspot.com/2009/06/alan-matison-turing.html [17] http://es.wikipedia.org/wiki/Navajo
79
IPN ESIME-ZACATENCO
80
BIBLIOGRAFÍA
[1] “Sube 20.6% número de usuarios de Internet en México: Inegi y Cofetel”. Periódico la
Jornada 2010/12/08.
[2] “Cibernautas bloquean consorcios que intentan ahogar a Wikileaks”. Periódico la
Jornada 2010/12/09.
[3] Darrel Hankerson, Alfred Menezes, Scott Vanstone. “Guide to Elliptic Curve
Cryptography”. Springer-Verlag, New York, 2004.
[4] John Talbot, Dominic Welsh “Complexity and Cryptography An Introduction”.
Cambridge University Press, 2006.
[5] Héctor Oviedo Galdeano. “Los cuaterniones y algunas aplicaciones en ingeniería”.
Encuentro Nacional Actualidad de las Matemáticas Aplicadas AMA 2010. Instituto
Tecnológico de Querétaro, Octubre 2010.
[6] Fred Piper, Sean Murphy. “Cryptography: A Very Short Introduction”. Oxford
University Press, 2002.
[7] William Stallings “Cryptography and Network Security Principles and Practices”.
Cuarta edición, Prentice Hall, 2006.
[8] Héctor Oviedo Galdeano, José Antonio López Toledo. “Curiosidades sobre la
Criptografía en hechos que dejaron marca en el mundo”. RISCE Revista Internacional de
Sistemas Computacionales y Electrónicos. Noviembre 2010, Número 6, Volumen 2, Año 2,
pp. 72-81.
[9] A. Menezes, P. van Oorschot, S. Vanstone. “Handbook of Applied Cryptography”.
CRC Press, 1996.
[10] José Francisco Vicent Francés “Propuesta y análisis de criptosistemas de clave pública
basados en matrices triangulares superiores por bloques” Universidad de Alicante, 2007.
[11] Daniel R. L. Brown. “Elliptic Curve Cryptography”. Certicom Corp, 2009.
[12] Rolf Oppliger. “Contemporary Cryptography”. Artech House, 2005.
[13] Daniel R. L. Brown. “Recommended Elliptic Curve Domain Parameters”. Certicom
Corp, 2010.
[14] Francisco Antonio Ferrández Agulló. Sistemas criptográficos de curva elíptica basados
en matrices”. Universidad de Alicante, 2005.
IPN ESIME-ZACATENCO
81
[15] Alexander W. Dent Chris J. Mitchell. “User’s Guide to Cryptography and Standards”.
Artech House, 2005.
[16] Padma Bh, D. Chandravathi y P. Prapoorna Roja. “Encoding And Decoding of a
Message in the Implementation of Elliptic Curve Cryptography using Koblitz’s Method”.
(IJCSE) International Journal on Computer Science and Engineering, Vol. 02, No. 05,
2010.
[17] M. Brown, D. Hankerson, J. López y A. Menezes “Software Implementation of the
NIST Elliptic Curves Over Prime Fields”. Springer-Verlag London UK, 2001.
[18] Todd K. Moon, “Error Correction Coding Mathematical Methods and Algorithms”,
Wiley-Interscience, 2005.
IPN ESIME-ZACATENCO
82
APÉNDICE A. Algoritmo de Menezes-Vastone
IPN ESIME-ZACATENCO
83
APÉNDICE B. Obtención de la Matriz Privada A
Para generar la llave privada se hace uso del teorema de Cayley-Hamilton. Para esto se
utiliza la matriz del sistema , la cual si se trabaja con curvas elípticas de
característica dos, es decir, de una forma binaria, puede construirse con polinomios
irreducibles. En nuestro caso se trabaja con números primos. Se utiliza la ecuación (1.9)
para la construcción de la matriz A:
2 1
0 1 2 1
2 1
0 1 2 1
0
. (*)
n n
n
n n
n
r I r M r M r M M
r I r M r M r M M
2 3 1
0 1 2 1
0
Multiplicando la ecuación anterior por
. (**)
Despejando en (**) y sustituyéndolo en (*)
n n
n
n
M
r M r M r M r M M
M
r M
2 3 2 1 1
1 2 1 0 1 2 1
1 2 1
1 2 1
( ) . (***)
Agrupando los términos en (***)
.
n n
n n
n n
o n
r M r M r r I r M r M r M M
M a I a M a M a M
2 1
1 2 1
La matriz privada es:
. n
o nA a I a M a M a M
IPN ESIME-ZACATENCO
84
APÉNDICE C. Criptoanálisis del sistema construido
11 12 13 11 12 13
2
21 22 23 21 22 23
31 32 33 31 32 33
2
2 1 0
11 12 13 11 12 13
2 21 22 23 1 21 22 23
31 32 33 31 32 33
y
si =a
m m m
M m m m M
m m m
A M a M a I
m m m
A a a m m m
m m m
0
2 11 2 12 2 13 1 11 1 12 1 13 0
2 21 2 22 2 23 1 21 1 22 1 23 0
2 31 2 32 2 33 1 31 1 32 1 33 0
2 11
1 0 0
0 1 0 mod
0 0 1
0 0
0 0
0 0
a p
a a a a m a m a m a
A a a a a m a m a m a
a a a a m a m a m a
a
A
1 11 0 2 12 1 12 2 13 1 13
2 21 1 21 2 22 1 22 0 2 23 1 23
2 31 1 31 2 32 1 32 2 33 1 33 0
0
1
2 11 1 11
.
Se desarrollará la siguiente ecuación:
donde
n
a m a a a m a a m
a a m a a m a a a m
a a m a a m a a m a
P
A P
P
a a m
0 2 12 1 12 2 13 1 13 0
2 21 1 21 2 22 1 22 0 2 23 1 23 1
2 31 1 31 2 32 1 32 2 33 1 33 0 2
a a a m a a m P
a a m a a m a a a m P
a a m a a m a a m a P
IPN ESIME-ZACATENCO
85
0
1
2
2 11 1 11 0 0 2 12 1 12 1 2 13 1 13 2
2 21 1 21 0 2 22 1 22 0 1 2 23 1 23 2
2 3
.
Para que se pueda reducir la matriz se utiliza la regla de suma de puntos en ECC
( ) ( ) ( )
( ) ( ) ( )
(
a a m a P a a m P a a m P
a a m P a a m a P a a m P
a
0
1
1 1 31 0 2 32 1 32 1 2 33 1 33 0 2 2
.
) ( ) ( )
Para realizar el proceso inverso, es decir, encontrar las claves privadas a partir de la ecuación anterior
se tiene el sistema de
a m P a a m P a a m a P
0 1 0 2
2 11 1 11 0 2 12 1 12 2 13 1 13 0 0
2 21 1 21 2 22 1 22 0 2 23 1 23 0 1
2 31 1 31 2 32 1 32 2 33 1 33 0 0 2
ecuación A = donde y .
.
Se determin
P P P P
a a m a a a m a a m P
a a m a a m a a a m P
a a m a a m a a m a P
0 0 0 1 0 2
2 11 1 11 0 2 12 1 12 2 13 1 13 0 0
2 21 1 21 2 22 1 22 0 2 23 1
an los escalares , y tales que , y .
El sistema de ecuaciones será:
[( ) ( ) + ( ) ]
[( ) + ( ) (
P P P
a a m a a a m a a m P P
a a m a a m a a a m
23 0 0
2 31 1 31 2 32 1 32 2 33 1 33 0 0 0
2 11 1 11 0 2 12 1 12 2 13 1 13
2 21 1 21 2 22 1
) ]
[( ) + ( ) + ( ) ] .
Asociaciando terminos de la ecuación anterior
[( ) ( ) + ( ) ]
[( ) + (
P P
a a m a a m a a m a P P
a a m a a a m a a m
a a m a a
22 0 2 23 1 23
2 31 1 31 2 32 1 32 2 33 1 33 0
2 11 12 13 1 11 12 13
) + ( ) ]
[( ) + ( ) + ( ) ]
el sistema de ecuaciones a resolver para encontrar los coeficientes de es:
( ) (
i
m a a a m
a a m a a m a a m a
a
a a m m m
0
2 21 22 23 1 21 22 23 0
2 31 32 33 1 31 32 33 0
)
( ) ( )
( ) ( ) .
a
a a m m m a
a a m m m a
IPN ESIME-ZACATENCO
86
2 1 0
11 12 13 11 12 13
21 22 23 21 22 23
31 32 33 31 32 33
11 12 13 11 12 13
21 22 23
Resolviendo el sistema de ecuaciones para encontrar , , .
( ) ( ) 1
( ) ( )
( ) ( )
( ) ( ) 1
(
a a a
m m m
m m m
D m m m
m m m
21 22 23) ( )m m m
11 12 13 21 22 23 21 22 23 31 32 33
31 32 33 11 12 13
21 22 23 11 12 13 11 12 13 31 32 33
31 32 33 21 22 2
( )*( )* ( )*( )*1
( )*( )*
[( )*( )* ( )*( )*
( )(
D m m m m m m
m m m
m m m m m m
m m m
3 )*1].
11 12 13
21 22 23
21 22 23 31 32 33 11 12 132 31 32 33
11 12 13 11 12 13 31 32 33
21 22 23
( ) 1
( )
( )*( )* ( )*( )*1 ( )*( )*( )
( ) 1 [( )*( )* ( )*( )*
( )
m m m
m m m
m m m m m m m m ma n m m m
m m m m m m m m m
m m m
21 22 23( )*( )*1].m m m
11 12 13
21 22 23
11 12 13 21 22 23 21 22 23 31 32 331 31 32 33
11 12 1331 32 33 11 12 13
21 22 2321 2
( ) 1
( )( )*( )* ( )*( )*1( )
( ) 1 ( )*( )*
( ) [(
m m m m m ma n
m m m
2 23 11 12 13 31 32 33)*( )* ( )*( )* ( )*( )*1].
11 12 13 11 12 13
21 22 23 21 22 23
0 31 32 33 31 32 33
11 12 13 11 12 13
21 22 23 21 22 23
11 12 13 21 22 230
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( )*( )* (
m m m
m m m
a n m m m
m m m
m m m
m m ma n
21 22 23 31 32 33
31 32 33 11 12 13
21 22 23 11 12 13 11 12 13 31 32 33
31 32 33 21 22 23
)*( )*
( )*( )*
[( )*( )* ( )*( )*
( )*( )* ].
m m m
m m m
m m m m m m
m m m
IPN ESIME-ZACATENCO
87
22
11
00 .
a na
D
a na
D
a na
D
IPN ESIME-ZACATENCO
88
APÉNDICE D. Ejemplo de un criptoanálisis para el sistema propuesto.
Se comprueba que esta matriz tiene inversa, la cual es
Para crear la llave privada se utiliza (3.5). Los coeficientes que se propusieron en forma
arbitraria para a0, a1, a2 son 5, 6 y 2 respectivamente, la única condición es que pertenezcan
a . La llave privada 2
2 1 0= A a M a M a I
.
IPN ESIME-ZACATENCO
89
Se construye los puntos del vector
0
1donde
n
P
A P
P
entonces
.
Si P0 es utilizado como generador de los puntos entonces 0 1 0 2 y P P P P por lo tanto
4 y 25 . El vector es:
por lo tanto
A
0 4(0,1) 100(0,1) 104(0,1)
20(0,1) 0 175(0,1) 195(0,1) mod(23),
19(0,1) 8(0,1) 450(0,1) 477(0,1)
23
12(0,1)
11(0,1)
17(0,1)
de donde, la llave pública resulta
.
IPN ESIME-ZACATENCO
90
Criptoanálisis para encontrar los coeficientes de ai
Se conoce el vector , y la matriz M ya que son públicos.
11 12 13 11 12 13
2
21 22 23 21 22 23
31 32 33 31 32 33
y
m m m
M m m m M
m m m
y
Se dan por conocido los valores de la ecuación (2.8) debido a que el objetivo de la tesis no
es realizar un criptoanálisis, estos valores se deben de conocer puesto que son necesarios
para saber el valor k de los puntos de los vectores y , para así poder solucionar el
sistema de ecuaciones obtenido en la ecuación (3.6):
2 11 12 13 1 11 12 13 0
2 21 22 23 1 21 22 23 0
2 31 32 33 1 31 32 33 0
( ) ( )
( ) ( )
( ) ( ) .
a a m m m a
a a m m m a
a a m m m a
El valor k de los puntos del vector es 4 y =25 puesto que 0 1 0 2 y P P P P .
El valor k de los puntos del vector es 12, 11 y 17 esto debido a que
0 0 0 1 0 2, y P P P .
IPN ESIME-ZACATENCO
91
Debido a que se trabaja todo sobre un campo siempre tiene que pertenecer a este por lo que
es necesario aplicar módulo al sistema de ecuación anterior, el módulo utilizado en el
ejemplo es 23.
Nota: Si se utiliza el algoritmo de Euclides
Extendido para resolver las divisiones anteriores.
IPN ESIME-ZACATENCO
92
Si se construye una llave privada 3 2
3 2 1 0= A a M a M a M a I con la misma M y donde
los coeficientes que se propusieron en forma arbitraria para a0, a1, a2, a3 son 5, 6, 2 y 9
respectivamente. La llave privada A es:
Se construye los puntos del vector
0
1donde
n
P
A P
P
entonces
.
IPN ESIME-ZACATENCO
93
Si P0 es utilizado como generador de los puntos entonces 0 1 0 2 y P P P P por lo tanto
4 y 25 . El vector es:
por lo tanto
A
18(0,1) 0 275(0,1) 293(0,1)
2(0,1) 0 450(0,1) 452(0,1) mod(23),
0 60(0,1) 0 60(0,1)
23
17(0,1)
15(0,1)
14(0,1)
de donde, la llave pública resulta
.
Criptoanálisis para encontrar los coeficientes de ai
Se conoce el vector , y la matriz M ya que son públicos.
11 12 13 11 12 13 11 12 13
2 3
21 22 23 21 22 23 21 22 23
31 32 33 31 32 33 31 32 33
, y
m m m
M m m m M M
m m m
,
y
IPN ESIME-ZACATENCO
94
Se dan por conocido los valores de la ecuación (2.8) debido a que el objetivo de la tesis no
es realizar un criptoanálisis, estos valores se deben de conocer puesto que son necesarios
para saber el valor k de los puntos de los vectores y . El valor k de los puntos del vector
es 4 y = 25 puesto que 0 1 0 2 y P P P P . El valor k de los puntos del vector
es 12, 11 y 17 esto debido a que 0 0 0 1 0 2, y P P P . El sistema a
resolver es:
3 11 12 13 2 11 12 13 1 11 12 13 0
3 21 22 23 2 21 22 23 1 21 22 23 0
3 31 32 33 2 31 32 33 1 31 32 33 0
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( ) .
a a a m m m a
a a a m m m a
a a a m m m a
Sustituyendo la ecuación con los valores obtenidos
Debido a que se trabaja todo sobre un campo siempre tiene que pertenecer a este por lo que
es necesario aplicar módulo al sistema de ecuación anterior, el módulo utilizado en el
ejemplo es 23.
IPN ESIME-ZACATENCO
95
El sistema a resolver es de tres ecuaciones con 4 incógnitas por lo que no se podrá
encontrar los coeficientes de ai, con esto se indica que el sistema criptográfico construido
necesita exactamente tres coeficientes de
IPN ESIME-ZACATENCO
96
APÉNDICE E. Recomendaciones de la NIST sobre campos primos
IPN ESIME-ZACATENCO
97
APÉNDICE F. Curva elíptica con a=1, b=1 y p=23
IPN ESIME-ZACATENCO
98
APÉNDICE G. Código ASCII
El código ASCII se utiliza porque cada carácter tiene dos nibbles (cuatro dígitos binarios
bits o medio octeto) lo que facilita su manipulación y empaquetamiento cuando se
transmiten varios bytes. Aunque todos los caracteres del código ASCII se representen con 7
bits, se utilizan los 8 bits, simplemente el MSB (most significant bit, el bit más
significativo) es siempre 0, por lo que el número de caracteres es 128 (28). Si se utilizara el
último bit (MSB) del byte de los códigos ASCII podrían ampliar el número de caracteres a
256 (28) con lo que podrían incluir otros símbolos, lo que se conoce como el código ASCII
Extendido.
Código ASCII.
IPN ESIME-ZACATENCO
99
IPN ESIME-ZACATENCO
100
APÉNDICE H. Algunos puntos de la curva elíptica donde a=7, b=29 y p=65521
IPN ESIME-ZACATENCO
101
IPN ESIME-ZACATENCO
102
IPN ESIME-ZACATENCO
103
BB
APÉNDICE I. Diagrama del sistema criptográfico propuesto
Se tienen dos usuarios y un medio de comunicación como se observa en la siguiente figura:
Los valores públicos son:
Llave privada A Llave privada B
Para lograr un intercambio de llaves entre dos usuarios debe de cumplirse que . Una
vez cumplido la condición se cifra los mensajes con el cifrado de ElGamal, se muestra por
bloques éste proceso.
AA
B
A 2 AB
1 BA
1 2
la Matriz M y el vector
IPN ESIME-ZACATENCO
104
Mensaje claro
de Alicia
Mensaje cifrado
Se efectúa la operación
A
Bob
, por lo
que
Desencriptar
Mensaje claro
IPN ESIME-ZACATENCO
105
APÉNDICE J. Diagramas de flujos del sistema criptográfico
Algoritmo para calcular los puntos de la curva elíptica sin conocer ninguno y conociendo
uno.
IPN ESIME-ZACATENCO
106
IPN ESIME-ZACATENCO
107
Diagrama de flujo para la construcción del sistema.
IPN ESIME-ZACATENCO
108
IPN ESIME-ZACATENCO
109
FUNCIÓN gpuntos
IPN ESIME-ZACATENCO
110
IPN ESIME-ZACATENCO
111
FUNCIÓN gpuntosist1a
IPN ESIME-ZACATENCO
112
IPN ESIME-ZACATENCO
113
FUNCIÓN ECCsolop1aa
IPN ESIME-ZACATENCO
114
IPN ESIME-ZACATENCO
115
FUNCIÓN sumsist1
IPN ESIME-ZACATENCO
116
IPN ESIME-ZACATENCO
117
FUNCIONES intercambioDH y AxPIdaPhi
IPN ESIME-ZACATENCO
118
FUNCIÓN cifraElGamal1
IPN ESIME-ZACATENCO
119
IPN ESIME-ZACATENCO
120
IPN ESIME-ZACATENCO
121
APÉNDICE K. Programa del sistema criptográfico.
Eccorden.m
clear all; clc; fprintf('curva elíptica\n'); fprintf('y^2=x^3+ax+b\n'); a=input('ingrese el valor de a= '); b=input('ingrese el valor de b= '); dd(1,1)=a; dd(2,1)=b; d=(4*(a^3))+(27*(b^2)); if d~=0 modu=input('ingrese el mod= '); p=modu; s=0; q=(p-1)/2; for i=1:modu z=s^3+(a*s)+b; x(1,i)=s; %secuencia de números x(2,i)=mod(z,p); %z solución de la curva elíptica s=s+1; r=x(2,i)^q; z1=mod(r,p);%calculando los residuos cuadráticos y no cuadráticos if z1>1 z1=-1; x(3,i)=z1; end x(3,i)=z1; end c=1; for i=1:modu if x(3,i)~=-1 rc(1,c)=x(2,i); % residuos cuadráticos con repetición ux(1,c)=x(1,i); %ubicación de residuos cuadráticos en x c=c+1; end end lon=length(rc); for i=1:modu h0=(i-p)^2; z1(1,i)=mod(h0,p); % h if i==modu z1(2,i)=0; else z1(2,i)=i; %y end end k=0; fprintf('los puntos son:\n\n'); fprintf('puntos\torden\n'); for i=1:lon for j=1:modu if (rc(1,i)==z1(1,j)) k=k+1; h(1,k)=rc(1,i); %valor de z
IPN ESIME-ZACATENCO
122
h(2,k)=z1(2,j); %y salida h(3,k)=ux(1,i); %valor de x salida [vpuntos]=gpuntos(h(3,k),h(2,k),p,a,lon); fprintf('(%d,%d)\t%d\n',h(3,k),h(2,k),vpuntos); plot(h(3,k),h(2,k),'--
rs','MarkerEdgeColor','k','MarkerSize',3) hold on end end end grid minor fprintf('\nEl número de puntos encontrados fueron: %d\n\n',k+1); x1=input('ingrese el valor del punto G en x= '); y1=input('ingrese el valor del punto G en y= '); %puntos a partir del generado lon=p; [vpuntos]=gpuntosist1(x1,y1,p,a,lon); if vpuntos~=1 fprintf('\nNúmero de puntos generados a partir del dado son:
%d\n',vpuntos); else fprintf('\nA partir de este punto no se genreran ningún otro
¿Escoja otro punto para utilizarlo como generador?'); break end end fprintf('\nEl discriminante es cero')
IPN ESIME-ZACATENCO
123
Sistema.m
clear all clc [h,k1,p,a]=ECCsolop1aa; %matriz pública M=input('ingrese los valores de la matriz M pública '); M=[1 5 8;10 9 6;3 2 4]; MM=det(M); format rational in=inv(M); if MM~=0 t=size(in,1);%tamaño de la matriz fprintf('La matriz M es la siguiente: \n'); disp(M); x1=h(3,1); y1=h(2,1);
%puntos a partir del generado fprintf('puntos\torden\n'); lon=p; [hh,vpuntos]=gpuntosist1a(x1,y1,p,a,lon); %grafica gxy=length(hh); for i=1:gxy plot(hh(1,i),hh(2,i),'--rs','MarkerEdgeColor','k','MarkerSize',3) hold on end grid minor %if vpuntos~=1 fprintf('\nNúmero de puntos generados a partir del dado son:
%d\n',vpuntos); i=1; am=[]; valor_a=[2 1 0]; for h=1:2 fprintf('Ingrese los coeficientes de "a" para formar la
clave privada de la persona %d.\nEl número de coeficientes de "a" son:
%d\n',h,t);
for i=1:t
fprintf('El valor del coeficiente a %d ',valor_a(i)); ax=input('es = '); am(i)=ax;
end
end [A]=intercambioDH(M,am,p,t); if h==1 A1=A; fprintf(' A de la persona 1 es: \n'); disp(A1); else B=A;
IPN ESIME-ZACATENCO
124
fprintf(' A de la persona 2 es: \n'); disp(B); end end pmatriz=[]; almkey=[]; pmatriz(1,1)=x1; pmatriz(2,1)=y1; almkey(1,1)=1; j=2; for i=1:t-1 key=input('ingrese el valor de k = '); [pfinal]=sumsist1(x1,y1,p,key,a); almkey(j,1)=key; pmatriz(:,j)=pfinal(1,:); j=j+1; end fprintf('Los valores de (PI) son: \n'); disp(pmatriz); %intercambio entre dos personas for i=1:2 BXPI=mod(A1*almkey,p); if i==1 AXPI=BXPI; AA=A1; end A1=B; end A=AA; pmat=AxPIdaPhi(x1,y1,p,AXPI,a,t); fprintf('Los valores de (PHI)para la persona 1 son: \n'); disp(pmat); pmat=AxPIdaPhi(x1,y1,p,BXPI,a,t); fprintf('Los valores de (PHI)para la persona 2 son: \n'); disp(pmat);
GamA=mod(A*BXPI,p); [pmatA]=AxPIdaPhi(x1,y1,p,GamA,a,t); GamB=mod(B*AXPI,p); [pmatB]=AxPIdaPhi(x1,y1,p,GamB,a,t); fprintf('Los valores de (GAMMA) para la persona 1 son: \n'); disp(pmatA); fprintf('Los puntos de ECC(GAMMA) para la persona 2 son: \n'); disp(pmatB); opcion='s'; while opcion~=('n') % cifrado eLGamal cifraElGamal1(hh,pmatA,pmatB,t,p) opcion=input('¿desea ingresar otro texto (s/n) ','s'); end end
IPN ESIME-ZACATENCO
125
gpuntos.m
function [vpuntos]=gpuntos(x1,y1,p,a,lon) w(1,1)=x1; w(2,1)=y1; %calculando labda de=(2*y1); if de~=0 [G,C,D]=gcd(de,p); inmul=mod(C,p); li=(3*(x1)^2+a); lp=mod(li,p); l=inmul*lp; l=mod(l,p); x3i=(l^2)-(2*x1); x3=mod(x3i,p); cc(1,1)=x3; y3i=-y1+(l*(x1-x3)); y3=mod(y3i,p); cc(2,1)=y3; l1=lon*2; almac=[]; for i=1:l1-2 lm=(y3-y1); lmnum=mod(lm,p); ln=(x3-x1); [G,C,D]=gcd(ln,p); den=mod(C,p); lg=lmnum*den; lg=mod(lg,p); xr=(lg^2)-x1-x3; pnew(1,i)=mod(xr,p); %x yr=-y1+lg*(x1-pnew(1,i)); pnew(2,i)=mod(yr,p); %y x3=pnew(1,i);%x y3=pnew(2,i); %y if x1==x3 break; end end almac=horzcat(w,cc); almac=horzcat(almac,pnew); [f,c]=size(almac); vpuntos=c+1; else vpuntos=1; end end
IPN ESIME-ZACATENCO
126
gpuntosist1.m
function [almac,vpuntos]=gpuntosist1a(x1,y1,p,a,lon) w(1,1)=x1; w(2,1)=y1; %calculando labda de=(2*y1); if de~=0 [x3,y3,cc]=propsum(p,de,a,x1,y1); %suma de puntos el mismo l1=lon*2; almac=[]; for i=1:l1-2 lm=(y3-y1); lmnum=mod(lm,p); ln=(x3-x1); [G,C,D]=gcd(ln,p); den=mod(C,p); lg=lmnum*den; lg=mod(lg,p); xr=(lg^2)-x1-x3; pnew(1,i)=mod(xr,p); %x yr=-y1+lg*(x1-pnew(1,i)); pnew(2,i)=mod(yr,p); %y x3=pnew(1,i);%x y3=pnew(2,i); %y if x1==x3 break; end end almac=horzcat(w,cc); almac=horzcat(almac,pnew); [f,c]=size(almac); for i=1:c fprintf('%d\t(%d,%d)\n',i,almac(1,i),almac(2,i)); end vpuntos=c+1; else i=1; fprintf('\nlos puntos son:\n'); fprintf('%d\t(%d,%d)\n',i,x1,y1); vpuntos=1; end end
IPN ESIME-ZACATENCO
127
prosum.m
function [x3,y3,cc]=propsum(p,de,a,x1,y1) [G,C,D]=gcd(de,p); inmul=mod(C,p); li=(3*(x1)^2+a); lp=mod(li,p); l=inmul*lp; l=mod(l,p); x3i=(l^2)-(2*x1); x3=mod(x3i,p); cc(1,1)=x3; y3i=-y1+(l*(x1-x3)); y3=mod(y3i,p); cc(2,1)=y3; end
intercambioDH.m function [A]=intercambioDH(M,am,p,t) for i=1:t MG=am(i)*(mod(M^(t-i),p)); MG=mod(MG,p); v(i,:)=reshape(MG',1,[]); %se almacena en vector s=sum(v); A=mod(s,p); end A=vec2mat(A,t); %se convierte a matriz end
sumsist1.m function [pfinal]=sumsist1(x1,y1,p,key,a) if key~=1 w(1,1)=x1; w(2,1)=y1; %calculando labda de=(2*y1); if de~=0
[x3,y3,cc]=propsum(p,de,a,x1,y1); %suma de puntos el mismo if key~=2 almac=[]; for i=1:key-2; lm=(y3-y1); lmnum=mod(lm,p); ln=(x3-x1); [G,C,D]=gcd(ln,p); den=mod(C,p); lg=lmnum*den; lg=mod(lg,p); xr=(lg^2)-x1-x3; pnew(1,i)=mod(xr,p); yr=-y1+lg*(x1-pnew(1,i));
IPN ESIME-ZACATENCO
128
pnew(2,i)=mod(yr,p); x3=pnew(1,i);%x y3=pnew(2,i); %y end almac=horzcat(w,cc); almac=horzcat(almac,pnew); [f,c]=size(almac); for i=1:c pfinal(1,1)=almac(1,i); %x final pfinal(1,2)=almac(2,i); %y final end end end end if (key==2) pfinal(1,1)=x3; pfinal(1,2)=y3; end if (key==1) pfinal(1,1)=x1; pfinal(1,2)=y1; end end
AxPIdaPhi.m
function [pmat]=AxPIdaPhi(x1,y1,p,AXPI,a,t) pmat=[]; pmat1(1,1)=x1; pmat1(1,2)=y1;
for j=1:t if AXPI(j,1)~=0 key=AXPI(j,1); [pfinal]=sumsist1(x1,y1,p,key,a); pmat(:,j)=pfinal(1,:); else pmat(:,j)=pmat1(1,:); end
end end
IPN ESIME-ZACATENCO
129
Sum2p.m
Function [x3,y3]=sum2p(x1,y1,x3,y3,p) lm=(y3-y1); lmnum=mod(lm,p); ln=(x3-x1); [G,C,D]=gcd(ln,p); den=mod(C,p); lg=lmnum*den; lg=mod(lg,p); xr=(lg^2)-x1-x3; pnew(1,1)=mod(xr,p); yr=-y1+lg*(x1-pnew(1,1)); pnew(2,1)=mod(yr,p); x3=pnew(1,1);%x y3=pnew(2,1); %y end
convtex.m
function [m_new]=convtex(xfinal,labc) c=1; i=1; b=xfinal; while(c~=0) c=fix(b/labc); textf(i)=mod(b,labc); b=c; i=i+1; end tfinal=fliplr(textf); m_new=char(tfinal+31); end
CifraElGamal1.m
function cifraElGamal1(hh,pmatA,pmatB,t,p)
c=fopen('entrada.txt', 'r+'); texto=fread(c,'*char')'; fprintf('El texto es:\n'); disp(texto); fclose(c); alfabeto=char(32:126); labc=length(alfabeto)+1; lt=length(texto); blo=input('En cuantos bloques se dividirá el texto = '); r1=mod(lt,blo); if r1~=0 comp=abs(blo-r1); for i=1:comp esp(i)=32;
IPN ESIME-ZACATENCO
130
end texto1=char(esp); texto=[texto1 texto]; end [m,x]=size(texto); [a,b]=size(alfabeto); resul=[]; for i=1:x for j=1:b r= strcmpi(alfabeto(1,j),texto(1,i)); if r==1 resul(1,i)=j; m(1,i)=j; %desplazardor end end end [mat,dif] = vec2mat(m,blo); [fi col]=size(mat'); cc=1; fprintf('\nEl mensaje encriptado por medio de puntos:\n'); for i=1:col m=mat(i,:)'; m=m'; lontext=size(m,2);
xw=0; for i=1:lontext s1=m(1,i)*(labc^(blo-i)); xw=xw+s1; end
k=5; for i=1:k au=k-1; pxw=(xw*k)+i; busc=find(hh(1,:)==pxw); [s1,s2]=size(busc);
if s2==2; break; end end k2=busc(1,1); fprintf('(%d,%d)\n',hh(1,k2),hh(2,k2)); pc(cc)=k2; %puntos de la curva con el mesaje cifrado cc=cc+1; end
%%%%%%%%%%%%%%%% %la persona 1 sumar punto encripatado + gammaA
fprintf('\nLos puntos OMEGA que viajan en el medio son:\n'); lpe=length(pc); %cociente=lpe/t; o3=mod(lpe,t); omegax=[];
IPN ESIME-ZACATENCO
131
omegay=[]; ic=1; for i=1:t:lpe-o3 for j=1:t
xa =pmatA(1,j); ya= pmatA(2,j); xb= hh(1,pc(ic)); yb= hh(2,pc(ic)); [x3,y3]=sum2p(xa,ya,xb,yb,p); omegax(ic)=x3; omegay(ic)=y3; fprintf('(%d,%d)\n',x3,y3); ic=ic+1; end end
if o3~=0 for j=1:o3 xa =pmatA(1,j); ya= pmatA(2,j); xb= hh(1,pc(ic)); yb= hh(2,pc(ic)); [x3,y3]=sum2p(xa,ya,xb,yb,p); omegax(ic)=x3; omegay(ic)=y3; fprintf('(%d,%d)\n',x3,y3); ic=ic+1; end end %la persona 2 realiza la operación OMEGA -GammaB omx=length(omegax); o33=mod(omx,t); fprintf('\nLos puntos recibidos son:\n'); ic=0; cociente=lpe/t; for i=1:cociente for j=1:t ic=ic+1; xa =omegax(ic); ya= omegay(ic); xb= pmatB(1,j); yb= abs(pmatB(2,j)-p); [x3,y3]=sum2p(xa,ya,xb,yb,p); fprintf('(%d,%d)\n',x3,y3);
x_original=(x3)/k; xfinal(ic)=fix(x_original);
end end %residuo if o33~=0 for j=1:o33 ic=ic+1; xa =omegax(ic);
IPN ESIME-ZACATENCO
132
ya= omegay(ic); xb= pmatB(1,j); yb= abs(pmatB(2,j)-p); [x3,y3]=sum2p(xa,ya,xb,yb,p); fprintf('(%d,%d)\n',x3,y3);
x_original=(x3-1)/k; xfinal(ic)=fix(x_original); end end
%%%%%se recupera mensaje original fprintf('\nEl mensaje numerico desencriptado es:\n'); disp(xfinal+31); %se convierte el valor numerico a texto fprintf('\nEl mensaje desencriptado es:\n'); [m_new1]=convtex(xfinal(1),labc); conver=length(xfinal); for i=2:conver [m_new]=convtex(xfinal(i),labc); m_new1=[m_new1 m_new]; end disp(m_new1); sal=fopen('salida.txt', 'w'); fwrite(sal,m_new1, '*char'); fclose(sal); clear all;
end
IPN ESIME-ZACATENCO
133
APÉNDICE L. Detección y corrección de errores
Las partes que conforman un sistema de comunicación digital son codificación de la fuente,
codificación canal y modulación digital en el lado del transmisor, así como los procesos
inversos para el lado del receptor. La detección y corrección de errores en una transmisión
corresponden a la codificación del canal. Puesto que la tesis no se centra en la corrección y
detección de errores de la información que se transmite solamente de modo general se
explica la detección y corrección de errores, para lo cual se utiliza el código hamming (7, 4)
que es un código lineal capaz de detectar y corregir un bit.
El diagrama a bloques de un código hamming (7, 4) es el siguiente:
En el diagrama se observa que el mensaje ingresado son bloques de longitud de cuatro bits
porque se utiliza el código hamming (7, 4) y la salida de éste es de longitud siete bits, estos
mensaje
IPN ESIME-ZACATENCO
134
son obtenidos multiplicando el mensaje con una matriz generadora (G). La diferencia entre
las longitudes de la salida y la entrada es la parte de redundancia, esta sirve para una que se
tenga mayores posibilidades de tener una decodificación adecuada de la secuencia de bits.
Uno de los parámetros importantes que miden el desempeño de un sistema de
comunicación digital es la BER (bit error rate) para un cierto valor de la relación de
energía de bit entre la densidad espectral de ruido (Eb/N0). Para proporcionar éste
parámetro se recurre a los códigos de detección y corrección de errores.
Cuando se transmite una señal siempre va hacer afectada por el ruido n, esta afectación se ve
reflejada en la señal recibida.
La probabilidad condicional de y para los dos casos son los siguientes:
Se necesita un modulador en los códigos hamming, se empleo el más sencillo que es BPSK
(Phase-Shift Keying) solo emplea 2 símbolos, con 1 bit de información cada uno. Es
también la que presenta mayor inmunidad al ruido, puesto que la diferencia entre símbolos
es máxima (180º). La señal de constelación para un BPSK es la siguiente:
La distribución de probabilidad en un BPSK tiene una forma gaussiana alrededor de cada
uno de los valores de símbolo, es presentada a continuación.
0
IPN ESIME-ZACATENCO
135
Supongamos que la señal recibida y, son igualmente probables por lo que de la figura
anterior el umbral de cero forma el límite para tomar una decisión óptima y esto nos
indicará si el símbolo pertenece a o a , lo anterior se puede explicar de la siguiente
manera:
si la señal recibida es mayor que 0, el receptor asume fue transmitida.
si la señal recibida es menor o igual a 0, el receptor asume fue transmitida
es decir,
Para la etapa de la demodulación de BPSK el símbolo recibido estará en base a la ubicación
de la constelación. En el bloque del detector indicará la posición donde ocurrió el error y
utilizando un detector hamming se podrá corregir éste. Para poder utilizar un decodificador
hamming se utiliza una matriz H que es una matriz de comprobación de paridad y así se
obtiene los mensajes que se enviaron en el medio de una forma corregida. Si se repite estos
pasos se obtendrá múltiples errores para distintos valores Eb/N0.
IPN ESIME-ZACATENCO
136
Programación para detectar y corregir un error.
close all clear all clc
n=7; k=4; m1=n-k;
%datos del vector OMEGA de la pág. 56
imbn=[38748 36140 40373 37191 21277 25708 37940 32534 25360 32298,... 13903 57386 40587 5699 53345 13247 49884 54018 500074 36841]; t1=dec2bin(imbn)-48; [ff,cc]=size(t1); fprintf('Los puntos enviados son:\n'); for i=1:cc fprintf('(%d,%d)\n',imbn(i),imbn(i+1)); end a=reshape(t1',1,ff*cc); [mensaje,r]=vec2mat(a,k); code = encode(mensaje,n,k,'hamming/ftm'); [fc,co]=size(code); codef=reshape(code',1,fc*co); N =fc*co; s = 2*codef-1; % modulación BPSK 0 -> -1; 1 -> 0 nr = 1/sqrt(2)*[randn(size(codef)) + j*randn(size(codef))]; % AWGN, 0dB
variance Eb_N0_dB = [0:1:12]; % Valores Eb/N0 Ec_N0_dB = Eb_N0_dB-10*log10(n/k); [h,g]= hammgen(m1); % matrix de paridad y generadora. for yy = 1:length(Eb_N0_dB) % agregando ruido y = s + 10^(-Ec_N0_dB(yy)/20)*nr; %ruido
cipHard = real(y)>0; %toma de decisión
%decodificación hamming%%%%%%%%%%%%%% [fx1,cx1]=size(cipHard); [recd,r]=vec2mat(cipHard,n); trt = syndtable(h); % tabla de decodificación. syndrome = mod(recd*h',2); % buscando síndrome syndrome_de = bi2de(syndrome,'left-msb'); % convertir de decimal. corrvect = trt(1+syndrome_de,:); % vector corregido correctedcode = rem(corrvect+recd,2);%palabra corregida % suma de errores s1=sum(code'); s2=sum(correctedcode'); s1a=sum(s1); s2a=sum(s2); nErr(yy) = abs(s2a-s1a); end fprintf('\nNo.total de Bits enviados: %d\n',N); fprintf('Eb_N0_dB\t\tNo. de Errores\n'); for w=1:length(Eb_N0_dB) fprintf('\t%d\t\t\t\t%d\n',Eb_N0_dB(w),nErr(w)); end
IPN ESIME-ZACATENCO
137
Rmsg=decode(correctedcode,n,k,'hamming/ftm'); [fa,ca]=size(Rmsg); bb=reshape(Rmsg',1,fa*ca); [correctedcodefi,r]=vec2mat(bb,cc); rxse=bi2de(correctedcodefi,'left-msb'); fprintf('\nLos puntos recibidos son:\n'); for i=1:cc fprintf('(%d,%d)\n',rxse(i),rxse(i+1)); end
Resultados de la simulación en Matlab.
IPN ESIME-ZACATENCO
138