problemas computacionales en criptografía · pdf fileproyecto fin de carrera problemas...

PROYECTO FIN DE CARRERA

PROBLEMAS COMPUTACIONALES EN CRIPTOGRAFÍA

AUTOR: D. Lorenzo José Herrero Blanco Madrid Junio de 2007

UNIVERSIDAD PONTIFICIA COMILLAS

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA (ICAI)

INGENIERO EN INFORMÁTICA

Autorizada la entrega del proyecto del alumno:

D. Lorenzo José Herrero Blanco

Madrid, 13 de junio de 2007

EL DIRECTOR DEL PROYECTO

Fdo.: Dr. D. Francisco Javier Rodríguez Gómez

Vº Bº del Coordinador de Proyectos

Fdo.: D. David Contreras Bárcena Fecha: ……/ ……/ ……

PROYECTO FIN DE CARRERA

PROBLEMAS COMPUTACIONALES EN CRIPTOGRAFÍA

AUTOR: D. Lorenzo José Herrero Blanco

DIRECTOR: Dr. D. Francisco Javier Rodríguez Gómez

UNIVERSIDAD PONTIFICIA COMILLAS

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA (ICAI)

INGENIERO EN INFORMÁTICA

Problemas Computacionales enCriptografía

Agradecimientos

A mi Director de Proyecto, Francisco Javier Rodríguez Gómez, ya que sin su ayuda,

dedicación y paciencia, no habría sido posible la realización de este Proyecto.

A mi familia, por haberme animado y ayudado durante el transcurso de la carrera.

I

Resumen

La Criptografía ha existido desde que el ser humano ha necesitado de métodos con los que

poder transmitir y ocultar información de posibles escuchas interesadas en interceptarla. Como no

podía ser de otra manera, ha evolucionado a lo largo de los siglos y su mayor auge coincidió con la

aparición de cada vez más avanzados y especializados recursos computacionales. Así,

prácticamente todas las aplicaciones criptográficas de hoy en día se ejecutan bajo aplicaciones

informáticas, con las ventajas y limitaciones que ello conlleva.

A diferencia de lo que sucede en la criptografía clásica y en la simétrica, en la que todas

las claves son secretas, en la criptografía de clave pública cada individuo posee dos claves, una

secreta y otra pública, de forma que los cifrados realizados con una de las claves se descifran con

la otra, siendo el cifrado como el descifrado operaciones matemáticas realizables en un tiempo

real. Las claves están relacionadas matemáticamente de tal forma que el conocimiento de la clave

pública y la matemática que sustenta su relación con la secreta no es suficiente para el cálculo de

ésta última. Para su cálculo se necesita el conocimiento de la trampa, que es secreta. De otra

manera, el cálculo de la clave secreta es tan complejo que no existe capacidad de cálculo

suficiente en el universo para realizarlo.

Por tanto, la seguridad de muchos de los criptosistemas en clave pública se basa en la

aparente incorruptibilidad de los problemas computacionales descritos en este Proyecto. Si los

parámetros de cada método son elegidos cuidadosamente la resolución del problema resulta

intratable, esto es, el tiempo de resolución resulta exponencial.

Proyecto Fin de Carrera Problemas Computacionales en Criptografía

II

Se define como función de una sola dirección o función trampa aquella función

matemática cuyo cálculo directo es sencillo, pero en la que el cálculo de la función inversa es muy

complejo, es decir, involucra un elevado número de operaciones. Un clásico ejemplo al respecto es

el caso de la factorización de un número entero N grande en dos números primos. Conociendo los

dos números primos resulta sencillo calcular su resultado, pero conociendo tan solo el resultado

del producto será muy difícil, y hasta imposible, poder calcular los dos números primos primitivos.

En la misma idea está basado el problema del logaritmo discreto y del residuo cuadrático.

Calcular el resultado de un logaritmo de un número en base a otro número resulta sencillo, sin

embargo realizar su función inversa, es decir, la exponencial, no resulta tan sencillo y mucho

menos cuando se estén manejando números grandes.

Siguiendo la estela del concepto de problemas computacionalmente inviables, se hablará

de la complejidad algorítmica y se demostrará por qué el problema de la suma de un subconjunto

es considerado como un NP-completo.

La aritmética modular es una parte de las Matemáticas extremadamente útil en

Criptografía, ya que permite realizar cálculos complejos y plantear problemas interesantes,

manteniendo siempre una representación numérica compacta y definida, puesto que sólo maneja

un conjunto finito de números enteros. Es por ello por lo que se hará un uso permanente de ella a

la hora de resolver los problemas propuestos, así como de potentes herramientas matemáticas

basadas en la aritmética modular como el Teorema Chino del Resto, el Símbolo de Jacobi y la

Inversa.

Cada algoritmo ha sido desarrollado mediante una explicación e indicando su

pseudocódigo, su codificación en el paquete de cálculo numérico, simbólico y gráfico


III

Mathematica®, con la resolución práctica de ejemplos y problemas planteados.

En primer lugar, se realiza el análisis y estudio de algoritmos que realizan de modo

eficiente la operación de factorización: factorización rho de Pollard, factorización Hp - 1L de

Pollard y la criba cuadrática correspondiente a los métodos de factorización cuadráticos

aleatorios. También se estudia el sistema de cifrado asimétrico de clave pública RSA por basarse

en gran parte en el problema de la factorización.

A continuación, se procede al desarrollo de técnicas y algoritmos que se basan en el

problema del residuo cuadrático, así como del método raíz cuadrada módulo n, con las

modalidades de n primo y n compuesto.

Para explicar y abarcar de la manera más completa posible el problema del logaritmo

discreto, se plantea el algoritmo baby-step giant-step, el algoritmo rho de Pollard para logaritmos

y el algoritmo de Pohlig-Hellman. También se somete a estudio el método de intercambio de

claves en criptografía simétrica de Diffie-Hellman, por estar también fundamentado en la base del

problema del logaritmo discreto.

A continuación, se desarrolla el algoritmo de la suma de un subconjunto en representación

del conjunto de problemas de la decisión, de los cuales además se deduce una clase de

complejidad concreta.

En todos los algoritmos planteados, con datos de entrada significativamente grandes, el

tiempo de ejecución se torna computacionalmente intratable. Por ello resulta muy interesante

realizar un pequeño y sencillo estudio (dado que no se dispone ni de software especializado ni de

recursos extraordinariamente potentes) para comprobar, a nivel práctico, cómo se cumplen los

tiempos de ejecución exponenciales mostrados en la teoría. Dicho estudio se plantea en el


IV

Proyecto.

Finalmente, para obtener una mejor comprensión de los algoritmos desarrollados, este

Proyecto se complementa con el diseño de una interfaz de usuario que presenta estos algoritmos,

permitiendo realizar de forma práctica su ejecución.


V

Abstract

Cryptography has existed since humans started to communicate through unsafe channels,

in the way that the information transmitted could be easily intercepted. Obviously, it has

developed throghout the years, finding its greatest development with the appearance of modern

computers. Thus, many crytographic applications are oriented to computer protocols, with the

advantages and disadvantages that it envolves.

In contrast to classic and simetric crytography, where all keys are kept in secret, when

using public-key cryptography each of the transmitters possess two keys; one is secret and the

other is public, being possible to encrypt and decrypt a message applying mathematical operations

that operate within real time. Even in the case that the algoritm applied for such purpose was

known, it would not be possible to calculate the secret key from the public key even if all the

computational resources in the universe were applied.

Therefore, the security of many public-key cryptosystems relies on the apparent

intractability of the computational problems studied in this Project. This means that if the

instances of a problem are carefully chosen, the running time of the algorithm turns into

exponential.

A one-way function is a function that is easy to compute but hard to invert. "Easy to

compute" means that some algorithm can compute the function in polynomial time. However,

"hard to invert" means that no probabilistic polynomial-time algorithm can compute the problem.

A clear example of this type of functions is the integer factorization problem. Considering as


VI

input data two integers, it is easy to mutiplicate them, but inverting this function requires solving

the factoring problem which is believed to be hard to solve.

The discrete logarithm problem and the quadratic residuosity problem are based on the

same idea. Given a base of a logarithm and a postive integer, it is easy to calculate the result of

the operation. However, the inverse function, which is the exponentiation, is widely believed to

be intractable when using high values of numbers.

Following the path of intractable problems, it is also studied in this Project the

computational complexity of some algorithms, and why the subset sum problem is considered as a

NP-complete problem.

Modular arithmetic is an extremely useful part of Mathematics in Cryptography, because

it allows to make complex calculations and poses interesting problems, supporting always a

compact and defined numerical representation, since it just uses a finite set of entire numbers.

That is the reason why some of the most important problems based on modular arithmetic are an

indispensable topic and will be used throughout this Project. These are, for example, the Chinese

Remainder Theorem for integers, Jacobi Symbol and the Inverse, all of them considered as a

powerful mathematical tool, with interesting cryptographic applications.

Each algorithm has been developed by an explanation and indicating its pseudocode and

codification in the package of numerical, symbolic and graphical language Mathematica, with the

practical resolution of examples and posed problems.

The first part of the Project consists of an analysis and explanation of some of the

algoritms used for factoring integer numbers. The algorithms proposed are the Pollard´s rho

factoring algorithm, the Pollard´s Hp - 1L factoring algorithm and the quadratic sieve factoring.


VII

The RSA algorithm is also proposed, although it is not a factoring algorithm itself, but it is based

on this idea.

To continue with, the quadratic residuosity problem is sifted, as well as the algorithms for

the calculation of modular square roots (prime module and compound module).

The Project continues with the problems related to the discrete logarithm problem, such as

the baby-step giant-step algorithm, the Pollards´s rho algorithm for logarithms and the

Polling-Hellman algorithms. The Diffie-Hellman key exchange protocol to jointly establish a

shared secret key over an insecure communications channel is also explained, so the discrete

logarithm problem takes an important role in it.

Later on, the subset sum problem is reviwed to make a good introduction to the

NP-complete class of problems. It is the simplest and most known of all decision problems,

whose main characteristic is that all algorithms that can solve them do it in time exponential, and

so they all are intractable.

Finally, in order to have a practical view of all the algorithms proposed, it is included in

the Project different graphs that show the increments of time that are experienced when the size of

the input data turns bigger. This experiment has been done with the sources available while the

Project was developed and, even though they were not the most powerful and modern, the

intention of the test is to put in practise all that it is studied in the Project.

For a better comprehension of the developed algorithms, this Project is completed with the

design of a user's interface that shows these algorithms, allowing their execution in a practical

way.


VIII

Índice

Índice... IX......................................................................................................................................

1. Introducción y objetivos... 2..................................................................................................... 1.1. Objetivos 6.................................................................................................................. 2. El problema de la factorización entera... 8............................................................................... 2.1. El algoritmo de factorización rho de Pollard... 10........................................................ 2.2. El algoritmo de factorización (p-1) de Pollard... 13..................................................... 2.3. Métodos de factorización cuadrático aleatorio... 15..................................................... 2.4. Criba cuadrática 17....................................................................................................... 3. El problema RSA o inversión RSA (RSAP) 27.......................................................................

4. El problema del residuo cuadrático... 35....................................................................................

5. Raíz cuadrada módulo n (SQROOT) 38.................................................................................... 5.1. Raíces cuadradas módulo n con n primo 46................................................................. 5.2. Raíces cuadradas módulo n con n compuesto 46......................................................... 6. El problema del logaritmo discreto (DLP). 73........................................................................... 6.1. Algoritmo baby-step giant-step... 74............................................................................ 6.2. Algoritmo rho de Pollard para logaritmos... 81............................................................ 6.3. Algoritmo Polig-Hellman 86........................................................................................ 7. El problema de Diffie-Hellman (DHP) 96.................................................................................

8. El problema de la suma de un subconjunto (SUBSET-SUM) 102..............................................

9. Estudio de tiempos de ejecución... 106........................................................................................ 10.1. Introducción teórica 106............................................................................................... 10.2. El problema de la factorización 107............................................................................. 10.3. El problema RSA 110................................................................................................. 10.4. El problema de la suma de un subconjunto 114........................................................... 10. Conclusiones y líneas futuras 116.............................................................................................

11 Desarrollo de la Aplicación 120...................................................................................... 11.1. Ciclo de vida... 120....................................................................................................... 11.2. Identificación de necesidades 127................................................................................ 11.3. Análisis de requisitos... 128.......................................................................................... 11.4. Arquitectura técnica 131...............................................................................................


IX

11.5. Diseño de la interfaz de usuario 132............................................................................

12. Valoración económica y planificación... 136............................................................................. 121. Introducción... 136......................................................................................................... 12.2. Técnicas de estimación de costes... 136....................................................................... 12.3. Costes del Proyecto... 139............................................................................................ 12.4. Planificación temporal del Proyecto... 139...................................................................

Bibliografía... 142.............................................................................................................................

CD-ROM con el código de los algoritmos y problemas de los Problemas Computacionales enCritografía realizados con Mathematica.


X

Problemas Computacionales en Criptografía


1

1. Introducción y objetivos

La Criptografía moderna nace al mismo tiempo que las computadoras. Durante la

Segunda Guerra Mundial, en un lugar llamado Bletchley Park, un grupo de científicos

entre los que se encontraba Alan Turing, trabajaba en el proyecto ULTRA tratando de

descifrar los mensajes enviados por el ejército alemán con los más sofisticados ingenios

de codificación ideados hasta entonces: la máquina ENIGMA y el cifrado Lorenz . Este

grupo de científicos diseñó y utilizó el primer computador de la Historia, denominado

Colossus —aunque esta información permaneció en secreto hasta mediados de los 70—.

Desde entonces hasta hoy ha habido un crecimiento espectacular de la tecnología

criptográfica, si bien la mayor parte de estos avances se mantenían —y se siguen

manteniendo, según algunos— en secreto. Financiadas fundamentalmente por la NSA

(Agencia Nacional de Seguridad de los EE.UU.), la mayor parte de las investigaciones,

hasta hace relativamente poco tiempo, han sido tratadas como secretos militares. Sin

embargo, en los últimos años, investigaciones serias llevadas a cabo en universidades de

todo el mundo han logrado que la Criptografía sea una ciencia al alcance de todos, y que

se convierta en la piedra angular de asuntos tan importantes como el comercio electrónico,

la telefonía móvil, o las nuevas plataformas de distribución de contenidos multimedia.

Esta dualidad civil—militar ha dado lugar a una curiosa doble historia de la Criptografía,

en la que los mismos algoritmos eran descubiertos, con pocos años de diferencia, por

equipos de anónimos militares y posteriormente por matemáticos civiles, alcanzando

únicamente estos últimos el reconocimiento público por sus trabajos.


2

Conviene hacer notar que la palabra Criptografía sólo hace referencia al uso de

códigos, por lo que no engloba a las técnicas que se usan para romper dichos códigos,

conocidas en su conjunto como Criptoanálisis. En cualquier caso ambas disciplinas están

íntimamente ligadas; debe tenerse en cuenta que cuando se diseña un sistema para cifrar

información, hay que tener muy presente su posible criptoanálisis, ya que en caso

contrario podríamos llevar a desagradables sorpresas. Finalmente, el término Criptología,

aunque no está recogido aún en el Diccionario, se emplea habitualmente para agrupar

Criptografía y Criptoanálisis.

Existen dos tipos fundamentales de criptosistemas:

Criptosistemas simétricos o de clave privada: Son aquéllos que emplean la misma clave k

tanto para cifrar como para descifrar. Presentan el inconveniente de que, para ser

empleados en comunicaciones, la clave k debe estar tanto en el emisor como en el

receptor, lo cual plantea la situación de elegir cómo transmitir la clave de forma segura.

Criptosistemas asimétricos o de clave pública: Estos emplean una doble clave Hkp, kPL. kpse conoce como clave privada y kP se conoce como clave pública. Una de ellas sirve para

la transformación E de cifrado y la otra para la transformación D de descifrado. En

muchos casos son intercambiables, esto es, si se emplea una para cifrar la otra sirve para

descifrar y viceversa. Estos criptosistemas deben cumplir además que el conocimiento de

la clave pública kp no permita calcular la clave privada kP Ofrecen un abanico superior de

posibilidades, pudiendo emplearse para establecer comunicaciones seguras por canales

inseguros — puesto que únicamente viaja por el canal la clave pública—, o para llevar a

cabo autentificaciones.


3

En la práctica se emplea una combinación de estos dos tipos de criptosistemas,

puesto que los segundos presentan el inconveniente de ser computacionalmente mucho

más costosos que los primeros. En el mundo real se codifican los mensajes (largos)

mediante algoritmos simétricos, que suelen ser muy eficientes, y luego se hace uso de la

criptografía asimétrica para codificar las claves simétricas (cortas).

Muchos de los sistemas criptográficos de clave pública basan su aparente

irrompibilidad en el problema de la factorización, una de las funciones de una sola

dirección más importantes conocidas como funciones trampa. A modo de ejemplo, si se

consideran p y q dos números primos, es muy fácil calcular el valor de su multiplicación

denotado por m. El tiempo de ejecución es además polinómico. Sin embargo, hallar p y q

a partir de m es, en general, de complejidad exponencial en la longitud de m, lo que hace

inviable su cálculo. Se presentan más adelante los métodos más interesantes para afrontar

la factorización de un número entero. Sin embargo, el éxito de la factorización de un

número entero, hoy por hoy, reside en su tamaño, y será imposible de factorizar cuando

sea demasiado grande para los recursos computacionales disponibles. Estos métodos son

el rho de Pollard, el Hp - 1L de Pollard y el de la criba cuadrática, dentro de los métodos

de factorización cuadráticos aleatorios. También se incluye la explicación y consecuente

programación del sistema de sifrado de clave pública asimético RSA.

El problema de los logaritmos discretos está íntimamente relacionado con el de la

factorización, de hecho está demostrado que si se puede calcular un logaritmo, entonces se

puede factorizar fácilmente (el recíproco no se ha podido demostrar). Sobre esta

afirmación se sustentan otros problemas como el Diffie-Hellman y el de ElGamal, en los


4

que aparece el término generador, cuya condición a cumplir consiste en debe existir un

entero i para todo b perteneciente al conjunto �p* , con p primo, que cumpla que el

generador elevado a i sea igual a b. Se proponen como métodos de más utilizados para

determinar logaritmos discretos el algoritmo baby-step giant-step, el algoritmo rho de

Pollard para logaritmos y el algoritmo Pohling-Hellman.

En la misma dirección que los métodos comentados que utilizan la factorización

en números de primos de N se basa el problema del carácter residual. El conocimiento del

carácter residual r-ésimo del valor entero a módulo N requiere el conocimiento de los

factores primos de N, lo cual no siempre es viable cuando se trabaja con números enteros

grandes. Éste es el conocido como problema del carácter residual, utilizado como

operador en muchos protocolos criptográficos de clave pública. Su función inversa es

conocida como la raíz cuadrada modular, y también se estudiará en los métodos raíz

cuadrada módulo n, con n primo y n compuesto.

En relación a todo lo anterior, se debe resaltar la importancia de los números

primos en la mayoría de los métodos de cifrado en clave pública. Sin su aplicación, los

métodos comentados serían fácilmente descifrados, con la consecuente pérdida de interés

de aplicación para técnicas de intercambio de información. Esta importancia reside en la

característica única de que dos números primos pueden llegar a ser los factores de un

número muy grande. En la criptografía en clave pública esta propiedad es de enorme

interés, ya que siempre se procurará que el número n a transmitir sólo sea posible de

factorizar en números grandes con muy pocos factores (factores que se conocen de

antemano y que deben ser elegidos cuidadosamente).


5

Finalmente, se pretende realizar una pequeña incursión en los problemas de

decisión, es decir, aquellos que consideran un algoritmo como mecanismo que permite

obtener una respuesta sí o no a un problema concreto. Con esta intención se incluye el

problema de la suma de un subconjunto, problema NP-completo que, dado un conjunto A

de enteros positivo y un número s, el problema consiste en determinar si existe o no un

subconjunto de A cuya suma de sus términos sea s.

1.1. Objetivos del proyecto

El proyecto se propuso inicialmente para cumplir con unos objetivos que se han

visto desarrollados en su totalidad. El espíritu que ha guiado todo el proyecto ha sido

predominantemente educativo: la intención era la de conseguir un software y un trabajo de

estudio que desmenuzase los problemas computacionales más comunes a la hora de tratar

con la Criptografía moderna en clave pública.

A continuación, se comentan los objetivos del proyecto y en qué nivel se han visto

satisfechos.

1º Realizar un software sobre Windows que permita realizar cálculos sobre

diferentes algoritmos propuestos inicialmente a estudio. Sin duda este ha sido el trabajo

más costoso, tanto por la búsqueda de los distintos algoritmos como su correcta

implementación.

2º Realizar un estudio detallado de todos los algoritmos propuestos, así como

entender por qué en unos casos es preferible utilizar un algoritmo en lugar de otro, aunque

los dos en principio persigan obtener el mismo resultado. Así, en el caso del estudio de la

aplicabilidad de cada algoritmo se ha podido observar y comprobar como, según los


6

parámetros de entrada, es posible que un algoritmo sea incapaz de alcanzar una solución

mientras que otro la alcance en pocos segundos. Por lo tanto, sí que se encuentran

diferencias en el modo de actuación, por lo que unos algoritmos serán más adecuados para

ciertos problemas en función de la naturaleza de los parámetros de entrada, ya que los

abordarán con métodos específicos para cada tipo de parámetros.

3º Proponer y realizar distintos casos de prueba que servirán como ejemplos de

utilización de los distintos algoritmos. Cada algoritmo dispone de una serie de problemas

resueltos utilizando su método, con una serie de explicaciones de cómo funciona.

4º Desarrollar una interfaz gráfica de usuario para la aplicación. Este objetivo

no se ha visto modificado durante la realización del proyecto. Para ello se ha utilizado el

paquete de generación de interfaz para Mathematica basado en Java llamado SuperWidget

Package. La interfaz permite ejecutar los algoritmos en un ambiente más amigable para el

usuario, ya que se puede utilizar incluso sin tener grandes conocimientos de Mathematica.

Y además se ha conseguido una aplicación de manejo sencillo que se espera que pueda

tener un buen uso didáctico.


7

2. Problema de la factorización entera

La factorización ha sido desde siempre uno de los problemas que más interés ha

suscitado en la Teoría de Números. Es a su vez el tema central de la mayoría de los

procedimientos de criptoanálisis, así como uno de los métodos más utilizados para dotar

de robustez a algunos algoritmos criptográficos, como en el caso del RSA de clave pública.

La factorización es el problema inverso a la multiplicación; dado n, se trata de

encontrar un conjunto de números tales que su producto valga n. Esto es

(1)n = p1e1 µ p2

e2 µ ... ...µ pkek .

Tal y como enuncia el teorema fundamental de la aritmética, todo número entero

positivo se puede descomponer como el producto de dos o más números primos elevados

a una potencia. De esta forma, además, se asegura de que la solución alcanzada sea única.

Por tanto, si se tuviera un algoritmo eficiente que fuese capaz de realizar dicha

factorización se podría aplicar sucesivamente sobre los resultados obtenidos consiguiendo

así reducir el número entero positivo original a sus factores primos más pequeños. No

obstante, se verá que el problema radica en que dicho algoritmo no es eficiente para

números enteros muy grandes.

La eficiencia de un algoritmo ante un problema es directamente proporcional a la

complejidad del problema que trata. Así, una complejidad del problema alta supondrá que

la eficiencia del algoritmo caiga y llegará un punto en que la complejidad será tan elevada

que hará ineficiente el algoritmo frente a ese problema. Por tanto, la medida de este

parámetro debe tan sólo tenerse en cuenta en relación con la dimensión de los números


8

enteros con los que se trabaja y no en términos absolutos. Por ello hay algoritmos que

funcionan mejor con números enteros pequeños mientras que otros muestran un mejor

comportamiento asintótico.

No obstante, todos ellos se transforman en ineficientes cuando los números

enteros a tratar alcanzan un tamaño suficientemente alto. Y precisamente la inviabilidad

de factorizar números enteros para un determinado tamaño hace que utilizar dichos

números en Criptografía sea un método fiable. Pero, ¿qué es lo que dota a un algoritmo de

eficiencia? Principalmente dependerá de dos factores; su diseño y de los recursos

computacionales de que dispongamos. Respecto al primero, una vez alcanzado el diseño

óptimo no se puede elevar la eficiencia del algoritmo. Será el segundo factor, los recursos

computacionales, los que podrán dotar a un algoritmo de una mayor eficiencia. Sin

embargo, y como se ha señalado con anterioridad, cuando los números enteros a

factorizar son muy elevados la complejidad computacional se dispara, lo que se traduce en

unos tiempos de cómputo demasiado elevados. Cuando esto ocurre se dice que el tiempo

de ejecución es exponencial, es decir, su tiempo de ejecución no puede ser acotado por

una función exponencial. Si por el contrario se muestran eficientes ante un número entero

se dice que el tiempo de ejecución es polinomial.

Hasta ahora se ha explicado el problema con el que se puede encontrar durante la

factorización de números enteros. Sin embargo dicho problema surge cuando el número

entero positivo a factorizar es demasiado grande. Cuando su tamaño es razonable se

dispone de una serie de algortimos para factorizarlo. Algunos de ellos son el Método de

Fermat, el Método p - 1 de Pollard y los Métodos Cuadráticos de Factorización, que

son el de la Criba Cuadrática y la Criba del Cuerpo de Números, siendo este último el


9

más eficaz y con el que se ha conseguido por ahora factorizar el mayor de número entero

hasta el momento; un número de 663 bits.

2.1 El algoritmo de factorización rho de Pollard

El algoritmo de factorización rho de Pollard resulta especialmente útil cuando

se quiere encontrar pequeños factores que componen un número entero.

Sea una función aleatoria tal que f: S ö S donde S es un conjunto finito de

números de cardinalidad n. Sea x0 un número aleatorio contenido en S y se considera

además la secuencia x0, x1, x2,.... definida por

(2)xi+1 = f HxiL " i ¥ 0.

Al ser S un número finito, la secuencia de elementos xi debe llegar a un punto en

el que se repite siguiendo por tanto un mismo ciclo. El conjunto de números que se

obtiene desde el comienzo hasta que aparece el ciclo recibe el nombre de cola. Se espera

que dicha cola tenga una longitud de ,Hp n ê8L y que ésta esté seguida como se ha dicho

por un ciclo repetitivo de una longitud esperada de también ,Hp n ê8L. En el campo del

Criptoanálisis resulta especialmente interesante encontrar un par de índices distintos i y j

tal que cumplan que xi = x j, en cuyo caso se dice que ha habido una colisión. Un método

sencillo y básico para encontrar una colisión sería calcular valores de xi para valores de

i = 0, 1, 2, ...., y reparar en aquellos que tengan el mismo valor. El número de valores

xi que hacen falta para que aparezcan los primeros valores duplicados es de ,Hp n ê2L. El

tiempo de ejecución esperado del algoritmo p de Pollard para localizar un factor p de n es

de O(,p) multiplicaciones modulares; es decir, el tiempo esperado para encontrar un

factor no trivial de n es O(n1ÅÅÅÅ4 ) multiplicaciones modulares.


10

è Algoritmo 1. Algoritmo de factorización rho de Pollard.

Descompone el número n en el producto de dos factores no triviales.

Input HnL

a ≠ 2

b ≠ 2

For i = 0, 1, ..., n do

a ≠ (a2+1) mod n

b ≠ (b2+1) mod n

b ≠ (b2+1) mod n

d ≠GCD(a - b,n)

If (1<d<n) Then

Return(d)

Else

If (d = n) Then

Return()

End

End

End

Output

Ejercicios propuestos

à Problema 1. Aplicar el algoritmo rho de Pollard para factorizar el número n = 77.

Algoritmo de factorización rho de Pollard para n = 77.

c d e

5 26 7

Dos factores no triviales de 77 son 7 µ 11.




11

c d e

5 26 1

26 2871 1

677 179685 1

2871 155260 1

44380 416250 1

179685 43670 1

121634 164403 1

155260 247944 1

44567 68343 743

Dos factores no triviales de 455459 son 743*613


8<



c d e

5 26 1

26 2871 1

677 179685 1

2871 155260 1

44380 416250 1

179685 43670 1

121634 164403 1

155260 247944 1

44567 68343 743

Dos factores no triviales de 455459 son 743*613


12

2.2 El algoritmo de factorización p - 1 de Pollard

Este algoritmo se presenta principalmente cuando se quiere encontrar de manera

eficiente cualquier factor primo p de un número compuesto n para el cual p - 1 es

uniforme con respecto a un límite preestablecido denotado por B. Se dice que un número

entero n es uniforme con respecto al límite B si todos sus factores primos son menores o

iguales que B.

La idea principal con respecto al algoritmo de factorización p - 1 de Pollard

reside en la expresión

(3)Q =‰qB

q A ln nÅÅÅÅÅÅÅÅÅÅÅln q E,

donde Q es mínimo común múltiplo de todas las potencias de los factores primos que B

que a su vez son también que n. Si ql n, entonces l * ln q ln n y entonces

(4)l @Hln nL ê Hln qLD.

Si p es un factor primo de n tal que p - 1 es uniforme con respecto a B, entonces

p - 1 » Q. En consecuencia, para cualquier número a cuyo máximo común divisor tenga

tan sólo el factor 1 en común con el máximo común divisor de p, se puede afirmar que

a ª 1 Hmod pL. Por esta razón, un número d = mcd H aQ - 1, nL cumple que p » d. Es

posible que suceda el caso en el que d = n, en cuyo caso el algoritmo de factorización

falla. Sin embargo, es muy poco probable que esto suceda si n está compuesto por al

menos dos factores primos grandes y diferentes.

è Algoritmo 2. Algoritmo (p - 1) de Pollard.


13

A partir de un número compuesto n y una cota B obtenemos algún factor primo p

de n para el cual p-1 es uniforme con respecto a B.

Input Hn, BL

a ≠ RandomHInteger, 2, ..., n - 1Ld ≠ gcd(a, n)

If (d ¥ 2) Then

Return(d)

End

For i = 0, 1, ..., B do

l ≠Hln nL ê Hln iLa ≠ ail mod n

b ≠ (b2+1) mod n

End

d ≠ GCD(a -1, n)

If (d=1 || d=n) Then

Return()

Else

Return(d)

End

Output


à Problema 5. Aplicar el algoritmo p - 1 de Pollard para factorizar el número n = 7485con límite B = 32.

Algoritmo de Pollard p-1 para factorizar el número 7485.

q l a

2 12 5326

3 8 4417

5 5 6337

7 4 6547

11 3 763

13 3 2512

17 3 5197

19 3 6658

23 2 6217

29 2 442

31 2 7


14

Dos factores no triviales del número 7485 son 2495 y 3.

à Problema 6. Aplicar el algoritmo p - 1 de Pollard para factorizar el número n = 919con límite B = 45.

Algoritmo de Pollard p-1 para factorizar el número 919.

q l a

2 9 273

3 6 216

5 4 30

7 3 202

11 2 629

13 2 15

17 2 308

19 2 836

23 2 798

29 2 265

31 1 369

37 1 322

41 1 227

43 1 540

Dos factores no triviales del número 919 son 919 y 1.

2.3 Métodos de factorización cuadrático aleatorio

La idea básica de la familia de algoritmos cuadráticos es la siguiente. Siendo n el

entero a factorizar y suponiendo que x, y son dos enteros, la idea fundamental es que

(5)x2 ª y2 Hmod nL

pero que al mismo tiempo se cumpla la ecuación

(6)x T ≤ y Hmod nL

Teniendo en cuenta dichas condiciones, es obvio que entonces se cumple que

(7)x2 – y2 = Hx+ yL Hx – yL = 0


15

o lo que es lo mismo, que la expresión anterior es divisible entre n. Adicionalmente, puesto

que tanto x como y son menores que n, n no puede ser divisor de (x + y) ni de (x - y). En

consecuencia, n ha de tener factores comunes tanto con (x + y) como con (x - y), por lo que

el resultado de la ecuación

(8)d = mcd Hn, x - yL

debe ser un divisor de n. Se puede demostrar que si n es impar, no potencia de primo y

compuesto, entonces siempre se pueden encontrar x e y.

A continuación se muestra un ejemplo concreto de la idea planteada hasta ahora.

Sea n = 91. Tras una serie de ensayos se deduce que 102 ª 9 Hmod 91L y

32 ª 9 Hmod 91L. Por otro lado, 10 ª 10 Hmod 91L y 3 ª 3 Hmod 91L, luego x = 10 e y = 3.

Como 10 – 3 < 91, se calcula mcd H10 – 3, 91L = 7, que es un factor de 91.

Llegado a este punto, se plantea ahora encontrar de forma eficiente una pareja de

números que cumpla esas condiciones. El método plantea elegir un conjunto formado por t

números primos diferentes S = 8 p1, p2, ..., pt < que recibe el nombre de base de factores

(factor base). Cualquier entero que se factorice usando esta base de factores se considera

uniforme de cota pt o pt - uniforme. Para los problemas desarrollados en el proyecto se

tomará como base de factores S = {-1, 2, 3, 5, 13, 23}, pudiendo modificarse en el código

del algoritmo. Se continúa buscando parejas de enteros (ai, bi) tal que

(9)ai2 ª bi Hmod nL

(10)bi = ‰j=1

t

p jeij , eij ¥ 0.


16

Seguidamente, obtenido un número suficiente de parejas, se busca un subconjunto

de entre los enteros bi tales que su producto sea un cuadrado perfecto. Como se tiene la

factorización de cada bi en la base de factores, bastaría elegirlos de manera que las

potencias eij de los primos p j de la base de factores S en que se factoriza cada bi sean pares.

Este problema equivale a resolver un sistema de ecuaciones lineales con coeficientes en �2,

por lo que esta fase se suele llamar reducción de la matriz. Multiplicando los ai2

correspondientes a los factores de b escogidos, se obtiene una ecuación del tipo

x2 ª y2Hmod nL. Si, además, x T ≤ y Hmod nL, bastará con calcular mcd Hx - y, nL y se

obtendrá el factor buscado.

2.4 Criba cuadrática

El método anterior admite mejoras y una de ellas conduce a la criba cuadrática.

Este método se basa en emplear un polinomio de la forma

(11)qHxL = Hx+mL2 - n

siendo m =è!!!n , donde dxt representa la parte entera de x. Puede comprobarse que

(12)qHxL = x2 + 2 m x +m2 - n º x2 + 2 m x

es un valor pequelo en relación con n, siempre y cuando x en valor absoluto sea pequeño. Si

se escoge ai = x + m y bi = Hx + mL2 - n , se debe comprobar que se cumpla la relación

(9) y que además sea pt - uniforme. Nótese que entonces se puede deducir que

ai2 = H x + m L2 ª bi Hmod nL, por lo que si un primo p divide bi entonces

H x + m L2 ª n Hmod pL, y por tanto n es residuo cuadrático modulo p. Por este motivo la

base de factores sólo necesita estar formada por aquellos primos p para los que el símbolo

de Legendre es 1. Además, como bi puede ser negativo, el -1 se debe incluir también en la


17

base de factores.

Lo único que queda por comprobar es si zi puede descomponerse totalmente con los

elementos de S. Esto se consigue con la fase de criba, pero antes se tendrá en cuenta que si

pi œ S entonces divide a qHxL, y por tanto también dividirá a qHx + k pL. Se procederá

entonces a la solución de la ecuación

(13)q HxL ª 0 Hmod pL

obteniendo una o dos series, dependiendo del número de soluciones que tenga la ecuación,

de valores y tales que p divide a qHyL.

La criba propiamente dicha se lleva a cabo definiendo un vector Q@xD, con

-M x M, cuya x - ésima entrada está inicializada a dlog » qHxL » t . Sean x1, x2 las

soluciones a (13). Entonces se resta el valor dlog HpLt a aquellas entradas Q @xD tales que x

sea igual a algún valor de las series de soluciones obtenidas en el paso anterior. Finalmente,

los valores de Q @xD que se aproximen a cero son los más susceptibles de ser descompuestos

con los elementos de S, propiedad que se puede verificar de forma directa tratando de

resolverlos.

è Algoritmo 3. Factorización por criba cuadrática.

Descompone el número n en el producto de dos factores no triviales por el método

de la criba cuadrática.

Input HnL

S ≠ { p1, p2, ..., pt }

m ≠ eè!!!!!n u

i ≠ 1

While i t + 1 do

b ≠ q (x) = Hx + mL2 - n

If (b = ¤j=1t pjeij ) Then

ai ≠ ( x + m )


18

bi ≠ b

vi ≠ { v i1, v i2, ..., v i t }

i ≠ i + 1

End

End

* T ≠ { 1, 2, ..., t + 1 } tal que ⁄i œT vi = 0

x ≠ ¤i œT ai mod n

For j = 1, ..., t do

l j ≠ (⁄i œT eij) /2

End

y ≠ ‰j=1

tp j

lj mod n

If ( x ª ± y ) Then

T ≠ { 1, 2, ..., t + 1 } tal que ⁄i œ T vi = 0

Go to *

Else

d = GCD ( x - y, n)

End

Return(d)

Output


à Problema 7. Aplicar el algoritmo de factorización por criba cuadrática para factorizarel número n = 24961.

Algoritmo de factorización de criba cuadrática para el número

n = 24961 .

i x qHxL Factorización de qHxL ai vi

1 0 -312 88-1, 1<, 82, 3<, 83, 1<, 813, 1<< 157 81, 1, 1, 0, 1, 0<2 1 3 883, 1<< 158 80, 0, 1, 0, 0, 0<3 -1 -625 88-1, 1<, 85, 4<< 156 81, 0, 0, 0, 0, 0<4 2 320 882, 6<, 85, 1<< 159 80, 0, 0, 1, 0, 0<5 -2 -936 88-1, 1<, 82, 3<, 83, 2<, 813, 1<< 155 81, 1, 0, 0, 1, 0<6 4 960 882, 6<, 83, 1<, 85, 1<< 161 80, 0, 1, 1, 0, 0<7 -6 -2160 88-1, 1<, 82, 4<, 83, 3<, 85, 1<< 151 81, 0, 1, 1, 0, 0<

La base de factores con la que se va a trabajar es

s = 8p1, p2, ..., pt< = 8-1, 2, 3, 5, 13, 23<El tamaño de s es t = 6.


19

El algoritmo requiere identificar aquellas filas que resultan

combinación lineal de otras en la matriz formada por los vi

obtenidos.

A =

i

k

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj

1 1 1 0 1 0

0 0 1 0 0 0

1 0 0 0 0 0

0 0 0 1 0 0

1 1 0 0 1 0

0 0 1 1 0 0

1 0 1 1 0 0

y

{

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

Las filas de la matriz A que cumplen ‚i em

vi = 0 son :

881, 2, 5<, 82, 4, 6<, 83, 6, 7<, 81, 4, 5, 6<, 82, 3, 4, 7<, 81, 3, 4, 5, 7<, 81, 2, 3, 5, 6, 7<<

Se comienza a estudiar cada uno de estos grupos de filas.

Así, T Œ 81, 2, ..., t+1<

Sea T Œ = 81, 2, 5<

x = ‰i eT

ai mod n = 3844930

Para cada j, 1 j t, se calcula l j = H‚i e T

eijLê2.

Así se tienen los siguientes valores:

lH1L = 1

lH2L = 3

lH3L = 2

lH4L = 0

lH5L = 1

lH6L = 0


20

Sea y = ‰j=1

t

p jl j mod n = 24025

Se debe comprobar si x ª ≤ y Hmod nL. Si es así se debe probar

con otro subconjunto T Œ 81,2,...,t+1<.

Se cumple que 936 ª ≤ 24025.

Se debe probar por tanto con el siguiente T .

Sea T Œ = 82, 4, 6<

x = ‰i eT

ai mod n = 4044642


eijLê2.


lH1L = 0

lH2L = 6

lH3L = 1

lH4L = 1

lH5L = 0

lH6L = 0

Sea y = ‰j=1

t

p jl j mod n = 960






21

Sea T Œ = 83, 6, 7<

x = ‰i eT

ai mod n = 3792516


eijLê2.


lH1L = 1

lH2L = 5

lH3L = 2

lH4L = 3

lH5L = 0

lH6L = 0

Sea y = ‰j=1

t

p jl j mod n = 13922



Se cumple que 23405 T ≤ 13922.

Se ha llegado a la solución final.

Dos factores no triviales para factorizar 24961 son 109 µ 229.



n = 7251 .


22


1 0 -26 88-1, 1<, 82, 1<, 813, 1<< 85 81, 1, 0, 0, 1,

2 -1 -195 88-1, 1<, 83, 1<, 85, 1<, 813, 1<< 84 81, 0, 1, 1, 1,

3 -4 -690 88-1, 1<, 82, 1<, 83, 1<, 85, 1<, 823, 1<< 81 81, 1, 1, 1, 0,

4 26 5070 882, 1<, 83, 1<, 85, 1<, 813, 2<< 111 80, 1, 1, 1, 0,

5 39 8125 885, 4<, 813, 1<< 124 80, 0, 0, 0, 1,

6 41 8625 883, 1<, 85, 3<, 823, 1<< 126 80, 0, 0, 1, 1,

7 -166 -690 88-1, 1<, 82, 1<, 83, 1<, 85, 1<, 823, 1<< -81 81, 1, 1, 1, 1,





obtenidos.

A =

i

k


1 1 0 0 1 0

1 0 1 1 1 0

1 1 1 1 0 1

0 1 1 1 0 0

0 0 0 0 1 0

0 0 0 1 1 1

1 1 1 1 1 0

y

{



vi = 0 son :

H 1 2 4 L


Así, T Œ 81, 2, ..., t+1<

Sea T Œ = 81, 2, 4<

x = ‰i eT

ai mod n = 792540


eijLê2.


lH1L = 1


23

lH2L = 1

lH3L = 1

lH4L = 1

lH5L = 2

lH6L = 0

Sea y = ‰j=1

t

p jl j mod n = 2181





Todos los posibles subjuntos Œ T han sido evaluados.

El algoritmo de factorización cuadrática aleatoria no puede

factorizar el número 7251 para la base de factores

S = 8-1, 2, 3, 5, 13, 23<.


El número 54897 no se puede factorizar para la base de

factores dada.

No es posible encontrar t+1 parejas Hai,biL.



n = 45 .


24


1 0 -9 88-1, 1<, 83, 2<< 6 81, 0, 0, 0, 0, 0<2 1 4 882, 2<< 7 80, 0, 0, 0, 0, 0<3 -1 -20 88-1, 1<, 82, 2<, 85, 1<< 5 81, 0, 0, 1, 0, 0<4 3 36 882, 2<, 83, 2<< 9 80, 0, 0, 0, 0, 0<5 -3 -36 88-1, 1<, 82, 2<, 83, 2<< 3 81, 0, 0, 0, 0, 0<6 -6 -45 88-1, 1<, 83, 2<, 85, 1<< 0 81, 0, 0, 1, 0, 0<7 9 180 882, 2<, 83, 2<, 85, 1<< 15 80, 0, 1, 0, 0, 0<





obtenidos.

A =

i

k


1 0 0 0 0 0

0 0 0 0 0 0

1 0 0 1 0 0

0 0 0 0 0 0

1 0 0 0 0 0

1 0 0 1 0 0

0 0 1 0 0 0

y

{



vi = 0 son :

881, 5<, 82, 4<, 83, 6<, 81, 2, 5<, 81, 4, 5<, 82, 3, 6<, 83, 4, 6<, 81, 2, 4, 5<,81, 3, 5, 6<, 82, 3, 4, 6<, 81, 2, 3, 5, 6<, 81, 3, 4, 5, 6<, 81, 2, 3, 4, 5, 6<<


Así, T Œ 81, 2, ..., t+1<

Sea T Œ = 81, 5<

x = ‰i eT

ai mod n = 18


eijLê2.



25

lH1L = 1

lH2L = 1

lH3L = 2

lH4L = 0

lH5L = 0

lH6L = 0

Sea y = ‰j=1

t

p jl j mod n = 27





Sea T Œ = 82, 4<

x = ‰i eT

ai mod n = 63


eijLê2.


lH1L = 0

lH2L = 2

lH3L = 1

lH4L = 0


26

lH5L = 0

lH6L = 0

Sea y = ‰j=1

t

p jl j mod n = 12



Se cumple que 18 T ≤ 12.

Se ha llegado a la solución final.

Dos factores no triviales para factorizar 45 son 3 µ 15.

3. El problema RSA o inversión RSA (RSAP)

El sistema de cifrado asimétrico de clave pública RSA fue propuesto por R. L.

Rivest, A. Shamir y L. Adleman en el año 1977 y posteriormente patentado por el MIT . El

sistema RSA es uno de los métodos de cifrado más utilizados, debido a sus especiales

características y prestaciones que se describen a continuación.

Sean p y q dos números primos grandes (>100 dígitos) y sea N = pq el producto

entre ellos. Sea « (N) la función de Euler de N , indicadora del número de valores enteros

menores que N que son relativamente primos con N . En este caso particular, la función

« (N) viene dada por el producto

(14)« HNL = Hp - 1L Hq - 1L


27

En estas condiciones, sea e un valor entero aleatorio relativamente primo con « (N)

tal que 1 � e � N y sea d otro entero tal que verifica la congruencia

(15)ed ª 1 Hmod« HN LL

es decir, que

(16)ed ª k f HNL + 1

con k valor entero. En estas condiciones, para cualquier valor entero M se verifica que si

C ª M e (mod N) entonces M ª Cd (mod N), es decir que

(17)M ed ª M Hmod NL

Para demostrarlo se utilizará el Teorema Chino de los Restos Congruentes. Dicho

teorema asegura que la congruencia anterior se verifica si y sólo si se verifican a su vez las

dadas por

(18)M ed ª M Hmod pL

(19)M ed ª M Hmod qL

lo cual es trivial teniendo en cuenta el teorema de Fermat

(20)M ed ª M kF HNL+1 ª M k Hp-1L Hq-1L+1 ª M k Hq-1L Hp-1L M ª M Hmod pL

(21)M ed ª M kF HNL+1 ª M k Hp-1L Hq-1L+1 ª M k Hp-1L Hq-1L M ª M Hmod qL

Ha de tenerse en cuenta que en el caso de que M no sea relativamente primo con N ,

entonces debe ser múltiplo de p o múltiplo de q, con lo que las congruencias anteriores se

verifican igualmente de forma trivial. Esta demostración es la base del sistema de cifrado

RSA. Dicho sistema está constituido por la claves N , e y d, respectivamente módulo de


28

trabajo y exponentes de cifrado y descifrado. El valor de N es público, así como el de uno

de los dos exponentes (e o d), mientras que el otro permanece secreto, por ejemplo:

Claves públicas: N , e Clave secreta: d

Para realizar el cifrado C de un mensaje en claro M tal que 1 � M � N , el mensaje

se eleva a la potencia e y el resultado se reduce al módulo N . Es decir, C ª M e (mod N).

Para la recuperación del mensaje en claro M se lleva a cabo elevando el mensaje cifrado C

a la potencia d (clave pareja de e) y reduciendo la exponenciación módulo N de acuerdo

con la congruencia M ª Cd (mod N). La recuperación del mensaje M puede igualmente

llevarse a cabo aplicando el teorema chino de los restos congruentes calculando

(22)M ª 8 Ap@Cpd Hmod pLD + Aq@Cqd Hmod qLD < Hmod NL

donde

(23)Cp ª C Hmod pL

(24)Cq ª C Hmod qL

(25)Ap ª q@q-1 Hmod pLD ª qp-1 Hmod NL

(26)Aq ª p@p-1 Hmod qLD ª pq-1 Hmod NL

La congruencia anteriore es equivalente a

(27)M ª 9 ApACpdp Hmod pLE + AqACqdq Hmod qLE = Hmod NL

donde los valores dp y dq están dados por

(28)dp ª d Hmod p - 1L

(29)dq ª d Hmod q - 1L.


29

Como se ve, en este procedimiento de cálculo, todas las exponenciaciones

modulares se reducen bien (mod p) o bien (mod q), por lo que este método es

considerablemente más rápido que el cómputo de la exponenciación modular

(30)M ª Cd Hmod NL.

Además, los valores de las variables dp, dq, Ap y Aq pueden calcularse previamente.

Sin embargo, este procedimiento de cálculo puede ser tan sólo utilizado por el propietario

de la clave secreta, puesto que él es el único que conoce los factores primos p y q.

Precisamente sobre este hecho se apoya la consistencia del sistema de cifrado RSA. El

cálculo de la clave secreta d es sencillo, conocidos p y q, mientras que sin su conocimiento

el cálculo de la clave secreta es equivalente al cálculo de factorización de la clave pública

N . Aquí es dónde radica la seguridad del método RSA, puesto que el problema de la

factorización de un número compuesto N , producto de dos factores primos, tiene una

complejidad exponencial dada por ‰è!!!!!!!!!!!!!!!!!!!!!!!!!!!!lnHNL lnlnHNL . Por esta razón se requiere la utilización de

factores primos muy grandes. A su vez, aunque el sistema de cifrado RSA funciona para

cualquier valor entero M , es conveniente que M sea relativamente primo con la clave

pública N , puesto que de lo contrario la factorización de N es trivial. Actualmente, se

recomienda utilizar claves públicas N mayores de 1024 bits.

è Algoritmo 4. Algoritmo de cifrado RSA.

Input (p, q)

N ≠ pq

f(N )

e ≠ Random(Integer, 1,..., f(N )-1)

While GCD(e, f(N )) ∫ 1 do

e ≠ Random(Integer,1,..., f(N )-1)

End

d ≠ inversaModular (e, N )


30

M ≠ Random(Integer, 1,..., N )

C ª M e (mod N )

M ª Cd (mod N )

Cp ª C (mod p)

Cq ª C (mod q)

dp ª d (mod p)

dq ª d (mod q)

Ap ª q [q-1(mod p)]

Aq ª p [p-1(mod q)]

M ª 8Ap HCpdp Hmod pLL + Aq HCq

dq Hmod qLL <

Return (M)

Output

El estudio y análisis del sistema de cifrado RSA presenta una cuestión denominada

como El problema RSA (RSAP). Dicho problema plantea la siguiente cuestión: dado un

número entero positivo n que es producto de dos números distintos impares p y q, un

número entero positivo tal que GCDH e, Hp - 1L Hq - 1L L = 1 y un entero c, encontrar un

entero m tal que me ª c Hmod nL.

En otras palabras, se plantea encontrar tantas raíces módulo n como sea el valor de

e, con el objetivo de encontrar así el valor de d. Además, los factores que componen n no se

conocen. Este planteamiento equivale a intentar descifrar la clave privada a partir de la

clave pública. Las condiciones impuestas respecto a los valores que pueden tomar n y e

garantizan que para cada número entero c œ 80, 1, ...., n - 1< haya exactamente un valor

de m œ 80, 1, ..., n - 1< tal queme ª c Hmod nL. Por lo tanto, la función f : �n ö �n

definida como f HmL = me Hmod nL es una permutación.

Los estudios realizados en este ámbito demuestran que, a día de hoy, la técnica más

eficaz para abordar el problema es la de factorizar n y por tanto descubrir así la clave

privada. No obstante, como se ha afirmado en los métodos de factorización anteriormente


31

explicados, esta técnica resulta inviable cuando n es suficientemente grande. No se ha

demostrado, sin embargo que esta técnica sea la única posible a emplear y se plantea, como

se ha mencionado con anterioridad, encontrar raíces cuadradas módulo n como alternativa

para descifrar el valor de d, aunque esta técnica presenta los mismos problemas de tiempo

de ejecución que la factorización de n.


à Problema 11. Sea el sistema de cifrado RSA definido por los parámetros p = 61 yq = 47. Mostrar cada paso necesario para llegar a cifrar y descifrar un mensaje M.

Los parámetros definidos para el sistema RSA son:

p = 61

q = 47

N = pq = 61*47

fHN L = Hp-1LHq-1L = 2760

e = 1073

d ª 1073-1 ª 2297 Hmod 2760L

El cifrado C del mensaje M = 1352 viene dado por:

C ª 13521073 ª 1884 Hmod 2867L

La recuperación del mensaje M se lleva a cabo mediante la

congruencia:

M ª 18842297 ª 1352 Hmod 2867L

Para recuperar el mensaje en claro M mediante el teorema chino

de los restos congruentes se calculan los valores:

Cp ª C61 ª 1884 ª 54 Hmod 61LCq ª C47 ª 1884 ª 4 Hmod 47Ldp ª d60 ª 2297 ª 17 Hmod 60Ldq ª d46 ª 2297 ª 43 Hmod 46L

El valor de Ap es:

A61 ª 47*@47-1 Hmod 61LD ª 47*13 ª 4760 ª 611 Hmod 2867L

El valor de Aq es:

A47 ª 61*@61-1 Hmod 47LD ª 61*37 ª 6146 ª 2257 Hmod 2867L


32

La recuperación del mensaje se lleva a cabo mediante la

congruencia:

M ª 8611*@5417 Hmod 61LD + 2257*@443 Hmod 47LD< ªH611*10 + 2257*36L ª H6110 + 81252L ª 87362 ª

1352 Hmod 2867L


El valor de p no es primo.

El valor de q no es primo.

El algoritmo no puede continuar.


Los parámetros definidos para el sistema RSA son:

p = 3709

q = 10289

N = p µ q = 3709 µ 10289

fHN L = Hp-1L µ Hq-1L = 38147904

e = 37071851

d ª 37071851-1 ª 22679939 Hmod 38147904L

El cifrado C del mensaje M = 1192838 viene dado por:

C ª 119283837071851 ª 4303732 Hmod 38161901L

La recuperación del mensaje M se lleva a cabo mediante la

congruencia:

M ª 430373222679939 ª 1192838 Hmod 38161901L

Para recuperar el mensaje en claro M mediante el teorema chino

de los restos congruentes se calculan los valores:

Cp ª C3709 ª 4303732 ª 1292 Hmod 3709LCq ª C10289 ª 4303732 ª 2930 Hmod 10289Ldp ª d3708 ª 22679939 ª 1811 Hmod 3708Ldq ª d10288 ª 22679939 ª 5187 Hmod 10288L


33

El valor de Ap es:

A3709 ª 10289*@10289-1 Hmod 3709LD ª10289*987 ª 102893708 ª 10155243 Hmod 38161901L

El valor de Aq es:

A10289 ª 3709*@3709-1 Hmod 10289LD ª3709*7551 ª 370910288 ª 28006659 Hmod 38161901L

La recuperación del mensaje se lleva a cabo mediante la

congruencia:

M ª 810155243*@12921811

Hmod 3709LD + 28006659*@29305187 Hmod 10289LD< ªH10155243*2249 + 28006659*9603L ª H22839141507 +

268947946377L ª 291787087884 ª

1192838 Hmod 38161901L


34

4. Problema del residuo cuadrático

La Teoría de Números abarca un campo inmenso de las matemáticas. Dentro de la

reciprocidad cuadrática se encuentra la propiedad residuo cuadrático.

Dados p y q enteros donde p no es divisible por q, si existe un número tal que

x2 ª p Hmod qL se dice que p es un residuo cuadrático de q, y en caso contrario se

considera que p es un no-residuo cuadrático de q. Así pues, el conocimiento del carácter

residual cuadrático del entero p módulo q requiere el conocimiento de los factores primos

de q, lo cual no siempre es posible cuando se trabaja con enteros grandes. Sin embargo, a

diferencia de lo que ocurre en el caso general del problema del carácter residual, el

carácter residual cuadrático (mod q) del valor entero p se puede calcular en tiempo

polinómico, suponiendo conocidos los factores primos de q. Esto último se lleva a cabo

mediante los denominados símbolos de Legendre y Jacobi. Por ejemplo, 13 es residuo

cuadrático de 17, pues la ecuación x2 ª pHmod qL tiene como soluciones x = 8, 25, 42.

Por otro lado, las congruencias entre números pueden manifestarse en dos grados

distintos; de primer grado y de segundo grado.

Respecto a las primeras, dados dos números enteros a y b, si su diferencia Ha - bL

o Hb - aL es exactamente divisible por el número m, se dice que a y b son congruentes

respecto al módulo m. Dicha caraterística se representa como a ª b HmodmL. Así,

100 ª 2 Hmod 7L.

En lo referente a las de segundo grado, se trata de aquéllas que se han definido


35

como residuo cuadrático con anterioridad y que Gauss denominó en su ley de

reciprocidad cuadrática. En ella Gauss afirma que si p y q son primos impares, y ninguno

de ellos pertenece a la sucesión 4 k + 1, entonces p es un residuo módulo q si y sólo si q

es un no residuo módulo p. Si por otro lado cualquiera de los dos, o ambos, pertecen a la

sucesión 4 k + 1 entonces p es un residuo módulo q si y sólo si q es un residuo módulo p.

Dicho más claramente, existe una reciprocidad entre el par de congruencias

x2 ª q Hmod pL. En el caso de que p y q sean primos, ambas congruencias son posibles o

ambas imposibles, a no ser que tanto p como q den el resto 3 cuando se dividen entre 4,

en cuyo caso una de las congruencias es posible y la otra no.

En el estudio de los residuos cuadráticos es preferible limitarse a los casos en los

que el módulo es un primo p, ya que presenta un comportamiento mucho más sencillo.

Para estudiar este caso es muy conveniente el uso de del símbolo de Legendre, y de su

extensión el símbolo de Jacobi.

Uno de los problemas abiertos más importantes sobre residuos cuadráticos es

determinar el orden de magnitud del mínimo no-residuo cuadrático positivo nHpL. El mejor

resultado conocido asegura que la expresión nHpL í p 1ÅÅÅÅÅÅÅÅÅÅÅÅÅÅÅ4 è!!!!‰ está acotada para todos los

primos, y se conjetura que el resultado podría seguir siendo cierto si se sustituye el

denominador por Hlog pL2.è Algoritmo 5. Algoritmo del residuo cuadrático.

Indica si un número entero a es residuo cuadrático respecto de otro entero n.

Input Ha, nL

sol ≠ jacobi2 Ha, nLprimos ≠ FactorInteger(n)

If Hsol = -1L Then


36

Break

Else

If (primos = Null) Then

Return()

Else

For i = 1, ..., primos do

If ( jacobi2(a, primos(i)) = -1)

Break

End

End

End

End

Return()

Output


à Problema 14. Sea a = 13 y n = 17. Comprobar si a es residuo cuadrático de n..

El símbolo de Jacobi de H13ê17L = 1.

Por lo tanto a = 13 es resto cuadrático respecto

de 17.

à Problema 15. Sea a = 13324 y n = 174123. Comprobar si a es residuo cuadrático de n.

El símbolo de Jacobi de H13324ê174123L = 1.

Por lo tanto a = 13324 es resto cuadrático respecto

de 174123.

à Problema 16. Sea a = 674 y n = 3. Comprobar si a es residuo cuadrático de n.

El símbolo de Jacobi de H674ê3L= -1, lo que permite concluir

que a = 674 no es resto cuadrático de 3.


37

5. Raíz cuadrada módulo n. (SQROOT)

La operación del cuadrado modular, en la que se fundamenta el problema del

carácter residual cuadrático, es frecuentemente utilizado en Criptografía. Lo mismo sucede

con su función inversa, la raíz cuadrada modular.

Si se supone que n y a son dos valores enteros, con a resto cuadrático módulo n,

entonces existe otro valor entero x, con 0 < x < n, tal que es solución de la congruencia:

(31)a ª x2Hmod nL.

El cálculo del valor x requiere la obtención de la raíz cuadrada del entero a módulo

n, lo cual se representa mediante la siguiente congruencia:

(32)x ªè!!!!a Hmod nL.

Evidentemente, la raíz cuadrada de un valor entero módulo n existe, si y sólo si,

dicho valor entero es resto cuadrático módulo n. Además, en el caso de que exista, se puede

demostrar que dicha raíz cuadrada no es única. Existen diversos algoritmos para el cálculo

de raíces cuadradas módulo n. Para presentarlos, se distinguirán los dos casos posibles que

se pueden presentar: que el entero n sea un número primo o bien que sea un número

compuesto.

5.1 Raíz cuadrada módulo n, con n primo

En el caso de que n sea un número primo, se puede demostrar que todo valor entero

a, que sea resto cuadrático módulo n, tiene dos raíces cuadradas de la forma ≤r módulo n y

tales que:


38

(33)H≤rL2 ª a Hmod nL .

Existen algoritmos capaces de calcular estas raíces de forma eficiente, aunque

tienen una complejidad computacional bastante elevada. A continuación, se pasa a explicar

uno de ellos, debido a L.M. Adleman, Manders y G.L. Miller.

Se debe tener en cuenta que, n ∫ 2 y el valor entero a tiene que estar comprendido

entre 0 < a < n, siendo a resto cuadrático módulo n.

è Algoritmo 6. Algoritmo para el cálculo de raíces cuadradas módulo primo

Input Ha, nL

(* Lista de valores de b tal que H bÅÅÅÅÅnL = -1 *)

l ≠ 8i ê H iÅÅÅÅÅnL = -1<

i=1

n-1

(* Se elige al azar valores enteros b con 0 < b < n hasta que Hb ênL = -1

*)

b ≠ l HRandom HInteger, 1, ..., Length HlLLLHs, tL ≠ n - 1 = 2s t, t œ Odd

a£ ≠ a-1 Hmod nLc0 ≠ b£ Hmod nLr0 ≠ aHt+1Lê2 Hmod nL

For i = 1, ... , s - 1 do

di ≠ Hci-12 a£L2s-i-1 Hmod nL

If di ª N - 1 Hmod nL then

ri ≠ ri-1 ci-1 Hmod nLci ≠ ci-1

2 Hmod nLEnd

End

Return Hrs-1, -rs-1LOutput

El algoritmo anterior se puede generalizar para el caso de que el valor entero n sea

de la forma n = pm, con p número primo y m > 1.


39


à Problema 17. Calcular la raíz è!!!a Hmod nL para los valores enteros dados:

a) n = 97 y a = 44.b) n = 72 y a = 103.

Cálculo de raíces cuadradas.

Método de Adleman, Manders, G. L. Miller.

8r1, r2< ª è!!!!a Hmod nL 8r1, r2< ª è!!!!!!!

44 Hmod 97L

Como n = 97 es primo y el símbolo de Jacobi H aÅÅÅÅÅn L = H 44ÅÅÅÅÅÅÅÅ

97L = 1

la raíz cuadrada modular existe.

Valores enteros b con 0 < b < n de modo que HbÅÅÅÅÅÅÅnL = -1.

l = 85, 7, 10, 13, 14, 15, 17, 19, 20, 21, 23, 26, 28, 29, 30,

34, 37, 38, 39, 40, 41, 42, 45, 46, 51, 52, 55, 56, 57, 58, 59, 60,

63, 67, 68, 69, 71, 74, 76, 77, 78, 80, 82, 83, 84, 87, 90, 92<Se elige al azar el valor b = 59

n - 1 = 96 = 25 3 fl s = 5, t = 3

Algoritmo para el cálculo de inversos modulares.

d ª a-1 Hmod bL ª 44-1 Hmod 97L

i yi gi ui vi

0 0 97 1 0

1 0 44 0 1

2 2 9 1 -2

3 4 8 -4 9

4 1 1 5 86

5 8 0 -44 97

Inverso modular.

86 ª 44-1 Hmod 97L

a£ ª a-1 Hmod nL = 86 ª 44-1 Hmod 97Lc0 ª bt Hmod nL = 30 ª 593 Hmod 97Lr0 ª aHt+1Lê2 Hmod nL = 93 ª 442 Hmod 97L


40

Tabla del algoritmo.

i di ri ci

0 0 93 30

1 96 74 27

2 1 74 50

3 1 74 75

4 1 74 96

H≤ rL ª ≤ 74 ª 874, 23< ª è!!!!!!!44 Hmod 97L




72 Hmod 103L

Como n = 103 es primo y el símbolo de Jacobi H aÅÅÅÅÅn L = H 72ÅÅÅÅÅÅÅÅÅÅÅ

103L = 1



l = 83, 5, 6, 10, 11, 12, 20, 21, 22, 24, 27, 31, 35, 37, 39, 40, 42,

43, 44, 45, 47, 48, 51, 53, 54, 57, 62, 65, 67, 69, 70, 71, 73, 74,

75, 77, 78, 80, 84, 85, 86, 87, 88, 89, 90, 94, 95, 96, 99, 101, 102<Se elige al azar el valor b = 77

n - 1 = 102 = 21 51 fl s = 1, t = 51



i yi gi ui vi

0 0 103 1 0

1 0 72 0 1

2 1 31 1 -1

3 2 10 -2 3

4 3 1 7 93

5 10 0 -72 103

Inverso modular.

93 ª 72-1 Hmod 103L


41



i di ri ci

0 0 81 102

H≤ rL ª ≤ 81 ª 881, 22< ª è!!!!!!!72 Hmod 103L

La raíces son correctas puesto que

812 ª 72 Hmod 103L222 ª 72 Hmod 103L


a) n = 223 y a = 31.




31 Hmod 223L


223L = 1



l = 83, 5, 6, 10, 11, 12, 13, 20, 21, 22, 23, 24, 26, 27, 35, 40, 42, 44, 45,

46, 48, 51, 52, 54, 57, 59, 61, 67, 70, 71, 75, 77, 79, 80, 84, 85, 87, 88, 90,

91, 92, 93, 95, 96, 97, 99, 102, 103, 104, 107, 108, 111, 113, 114, 117,

118, 122, 123, 125, 129, 134, 137, 140, 141, 142, 145, 147, 149, 150,

151, 154, 155, 157, 158, 159, 160, 161, 163, 165, 167, 168, 170, 173,

174, 176, 180, 182, 184, 185, 186, 187, 189, 190, 191, 192, 193, 194,

195, 198, 204, 205, 206, 207, 208, 209, 214, 215, 216, 219, 221, 222<Se elige al azar el valor b = 194

n - 1 = 222 = 21 111 fl s = 1, t = 111




42

i yi gi ui vi

0 0 223 1 0

1 0 31 0 1

2 7 6 1 -7

3 5 1 -5 36

4 6 0 31 -223

Inverso modular.

36 ª 31-1 Hmod 223L



i di ri ci

0 0 37 222

H≤ rL ª ≤ 37 ª 837, 186< ª è!!!!!!!31 Hmod 223L


372 ª 31 Hmod 223L1862 ª 31 Hmod 223L


a) n = 211 y a = 45.




45 Hmod 211L


211L = 1



43


l = 82, 3, 7, 8, 10, 12, 15, 17, 18, 22, 23, 26, 27, 28, 29, 31, 32, 33, 35,

38, 39, 40, 41, 42, 48, 50, 57, 60, 61, 63, 67, 68, 72, 74, 75, 77, 85,

86, 88, 89, 90, 91, 92, 94, 97, 98, 102, 104, 106, 108, 110, 111, 112,

115, 116, 118, 124, 127, 128, 129, 130, 131, 132, 133, 135, 138,

140, 141, 142, 145, 146, 147, 149, 152, 153, 155, 156, 157, 158,

159, 160, 162, 164, 165, 166, 167, 168, 174, 175, 177, 181, 186,

187, 190, 191, 192, 195, 197, 198, 200, 202, 205, 206, 207, 210<Se elige al azar el valor b = 89

n - 1 = 210 = 21 105 fl s = 1, t = 105



i yi gi ui vi

0 0 211 1 0

1 0 45 0 1

2 4 31 1 -4

3 1 14 -1 5

4 2 3 3 -14

5 4 2 -13 61

6 1 1 16 136

7 2 0 -45 211

Inverso modular.

136 ª 45-1 Hmod 211L



i di ri ci

0 0 16 210

H≤ rL ª ≤ 16 ª 816, 195< ª è!!!!!!!45 Hmod 211L


44


162 ª 45 Hmod 211L1952 ª 45 Hmod 211L


a) n = 223 y a = 923.



8r1, r2< ª è!!!!a Hmod nL 8r1, r2< ª è!!!!!!!!!!

923 Hmod 223L


223L = 1



l = 83, 5, 6, 10, 11, 12, 13, 20, 21, 22, 23, 24, 26, 27, 35, 40, 42, 44, 45,

46, 48, 51, 52, 54, 57, 59, 61, 67, 70, 71, 75, 77, 79, 80, 84, 85, 87, 88, 90,

91, 92, 93, 95, 96, 97, 99, 102, 103, 104, 107, 108, 111, 113, 114, 117,

118, 122, 123, 125, 129, 134, 137, 140, 141, 142, 145, 147, 149, 150,

151, 154, 155, 157, 158, 159, 160, 161, 163, 165, 167, 168, 170, 173,

174, 176, 180, 182, 184, 185, 186, 187, 189, 190, 191, 192, 193, 194,

195, 198, 204, 205, 206, 207, 208, 209, 214, 215, 216, 219, 221, 222<Se elige al azar el valor b = 170

n - 1 = 222 = 21 111 fl s = 1, t = 111



i yi gi ui vi

0 0 223 1 0

1 0 923 0 1

2 0 223 1 0

3 4 31 -4 1

4 7 6 29 -7

5 5 1 -149 36

6 6 0 923 -223

Inverso modular.

36 ª 923-1 Hmod 223L


45



i di ri ci

0 0 37 222

H≤ rL ª ≤ 37 ª 837, 186< ª è!!!!!!!!!!923 Hmod 223L


372 ª 923 Hmod 223L1862 ª 923 Hmod 223L

5.2 Raíz cuadrada módulo n, con n compuesto

En este punto se describe el cálculo de raíces cuadradas módulo n, en el caso de que

n sea un número compuesto de la forma:

(34)n = pµ q

con p y q factores primos de n. En estas condiciones, se puede demostrar que todo valor

entero a, con 0 < a < n que sea resto cuadrático módulo n, tiene cuatro raíces cuadradas

módulo n. Estas, son de la forma ≤x y ≤ y módulo n y tales que:

(35)H≤xL2 ª H≤ yL2 ª a Hmod nL

verificándose que:

(36)≤x T ≤ y Hmod nL.

En estas condiciones, las raíces ≤x Hmod nL se denominan no gemelas, al igual que

las raíces ≤ y Hmod nL. Cualesquiera otras dos raíces se denominan gemelas. Las raíces

cuadradas de a módulo n pueden calcularse de forma eficiente si se suponen conocidos los


46

factores primos p y q de n. Es necesario recordar que cuando n es compuesto, a diferencia

de lo que sucede cuando es primo, el carácter residual del entero a respecto de n no puede

ser determinado de forma directa a partir del valor del símbolo de Jacobi Ha ênL. Así, si

Ha ênL = -1, entonces se puede asegurar que a no es resto cuadrático módulo n. Sin

embargo, si Ha ênL = +1, no es posible garantizar que a sea resto cuadrático módulo n, ya

que para ello debe serlo respecto de cada uno de los factores primos de n, es decir, se debe

verificar que Ha ê pL = Ha êqL = +1. Así pues, en el caso de que Ha ênL = +1, la determinación

del carácter residual de a respecto de n requiere el conocimiento de los factores primos de n.

Hecha esta puntualización, para calcular las raíces cuadradas de a módulo n, se

comienza por calcular las raíces cuadradas de a respecto de los factores primos p y q de n,

lo cual se lleva a cabo aplicando el algoritmo descrito en el apartado anterior. A

continuación, dichas raíces se combinan mediante el teorema chino de los restos

congruentes, obteniendo de esa forma las cuatro raíces cuadradas de a módulo n. Cuando se

trabaja con valores de n muy grandes (>200 dígitos), este procedimiento de cálculo de

raíces es viable únicamente si se conocen los factores primos de n y, aún en este caso, es de

una complejidad computacional bastante elevada. Sin embargo, si los factores primos de n

se descomponen, entonces el cálculo de raíces cuadradas módulo n es totalmente inviable.

è Algoritmo 7. Algoritmo para el cálculo de raíces cuadradas módulo compuesto

Input Ha, n, p, qL

Hr, -rL ≠ sqrootnprimo Ha, pLHs, -sL ≠ sqrootnprimo Ha, qL

Ap ª q @q-1 mod HpLD Hmod nLAq ª p @p-1 mod HqLD Hmod nL

x ª HAp r + Ap sL Hmod nLy ª HAp r - Ap sL Hmod nL


47

Return HH≤ x, ≤ yL Hmod nLLOutput

El algoritmo puede generalizarse para el caso de que el valor entero n sea de la

forma:

(37)n =‰i=1

i=t

piei

con pi factores primos con multiplicidades respectivas ei, para i = 1, ..., t. Sin embargo,

esta generalización no será considerada. Una importante consideración a tener en cuenta es

que la factorización de n puede obtenerse de forma trivial, a partir del conocimiento de una

pareja de raíces cuadradas gemelas de cualquier valor entero que sea resto cuadrático

módulo n, en particular, a partir de las raíces cuadradas x e y de a módulo n. Así, puesto

que dichas raíces verifican que:

(38)x T ≤ y Hmod nL

(39)x2 ª y2 ª a Hmod nL

entonces, uno de los valores del máximo común divisor mcd Hx ≤ y, nL corresponde al

número primo p y el otro al número primo q. Esto es fácil de ver puesto que:

(40)Hx + yL Hx - yL ª Hx2 - y2L ª 0 Hmod nLïHx+ yL Hx - yL = k n

con k entero:

(41)x T ≤ y Hmod nL ï Hx ≤ yL ∫ k£ n

con k£ entero.

Por tanto, se tiene que:


48

(42)Hx + yL Hx - yL = k p qHx ≤ yL ∫ k£ p q

(43)ï mcd Hx ≤ y, nL = p ó q.


à Problema 21. Calcular la raíz è!!!a Hmod nL para los valores enteros dados, sabiendo que

n = p.q es un número compuesto de dos primos enteros.a) n = 17.29 = 423 y a = 132.b) n = 19.23 = 437 y a = 330.

Cálculo de raíces cuadradas módulo compuesto.

8r1, r2, r3, r4< ª è!!!!a Hmod nL n = p.q

8r1, r2, r3, r4< ªè!!!!!!!!!!

132 Hmod 493L 493 = 17.29




132 Hmod 17L


17L = 1



l = 83, 5, 6, 7, 10, 11, 12, 14<Se elige al azar el valor b = 3

n - 1 = 16 = 24 1 fl s = 4, t = 1



i yi gi ui vi

0 0 17 1 0

1 0 132 0 1

2 0 17 1 0

3 7 13 -7 1

4 1 4 8 -1

5 3 1 -31 4

6 4 0 132 -17


49

Inverso modular.

4 ª 132-1 Hmod 17L



i di ri ci

0 0 13 3

1 1 13 9

2 16 15 13

3 16 8 16

H≤ rL ª ≤ 8 ª 88, 9< ª è!!!!!!!!!!132 Hmod 17L




132 Hmod 29L


29L = 1



l = 82, 3, 8, 10, 11, 12, 14, 15, 17, 18, 19, 21, 26, 27<Se elige al azar el valor b = 21

n - 1 = 28 = 22 7 fl s = 2, t = 7




50

i yi gi ui vi

0 0 29 1 0

1 0 132 0 1

2 0 29 1 0

3 4 16 -4 1

4 1 13 5 -1

5 1 3 -9 2

6 4 1 41 20

7 3 0 -132 29

Inverso modular.

20 ª 132-1 Hmod 29L



i di ri ci

0 0 25 12

1 1 25 28

H≤ rL ª ≤ 25 ª 825, 4< ª è!!!!!!!!!!132 Hmod 29L

12 ª p-1 Hmod qL ª 17-1 Hmod 29L

10 ª q-1 Hmod pL ª 29-1 Hmod 17L

Se calculan los valores siguientes:

Ap ª q @q-1 Hmod pLD Hmod nL ª29 @29-1 Hmod 17LD Hmod 493L

Ap ª 29µ10 Hmod 493L = 290 Hmod 493LAq ª p @p-1 Hmod qLD Hmod nL ª

17 @17-1 Hmod 29LD Hmod 493LAq ª 17µ12 Hmod 493L = 204 Hmod 493Lx ª HAp r + Aq sL Hmod nL ª H290µ8 + 204µ4L Hmod 493Lx ª 178 Hmod 493Ly ª HAp r - Aq sL Hmod nL ª H290µ8 + 204µ25L Hmod 493Ly ª 25 Hmod 493L


51

Raíces cuadradas módulo compuesto.

H≤ xL ª ≤ 178 = 8178, 315<H≤ yL ª ≤ 25 = 825, 468<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

8178, 315, 25, 468< ªè!!!!!!!!!!

132 Hmod 493L 493 = 17.29



8r1, r2, r3, r4< ªè!!!!!!!!!!

330 Hmod 437L 437 = 19.23




330 Hmod 19L


19L = 1



l = 82, 3, 8, 10, 12, 13, 14, 15, 18<Se elige al azar el valor b = 3

n - 1 = 18 = 21 9 fl s = 1, t = 9



i yi gi ui vi

0 0 19 1 0

1 0 330 0 1

2 0 19 1 0

3 17 7 -17 1

4 2 5 35 -2

5 1 2 -52 3

6 2 1 139 11

7 2 0 -330 19

Inverso modular.

11 ª 330-1 Hmod 19L


52



i di ri ci

0 0 11 18

H≤ rL ª ≤ 11 ª 811, 8< ª è!!!!!!!!!!330 Hmod 19L




330 Hmod 23L


23L = 1



l = 85, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22<Se elige al azar el valor b = 20

n - 1 = 22 = 21 11 fl s = 1, t = 11



i yi gi ui vi

0 0 23 1 0

1 0 330 0 1

2 0 23 1 0

3 14 8 -14 1

4 2 7 29 -2

5 1 1 -43 3

6 7 0 330 -23

Inverso modular.

3 ª 330-1 Hmod 23L


53



i di ri ci

0 0 13 22

H≤ rL ª ≤ 13 ª 813, 10< ª è!!!!!!!!!!330 Hmod 23L








H≤ xL ª ≤ 217 = 8217, 220<H≤ yL ª ≤ 312 = 8312, 125<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

8217, 220, 312, 125< ªè!!!!!!!!!!

330 Hmod 437L 437 = 19.23


n = p.q es un número compuesto de dos primos enteros.a) n = 13.11 = 143 y a = 48.



8r1, r2, r3, r4< ªè!!!!!!!

48 Hmod 143L 143 = 13.11


54




48 Hmod 13L


13L = 1



l = 82, 5, 6, 7, 8, 11<Se elige al azar el valor b = 8

n - 1 = 12 = 22 3 fl s = 2, t = 3



i yi gi ui vi

0 0 13 1 0

1 0 48 0 1

2 0 13 1 0

3 3 9 -3 1

4 1 4 4 -1

5 2 1 -11 3

6 4 0 48 -13

Inverso modular.

3 ª 48-1 Hmod 13L



i di ri ci

0 0 3 5

1 1 3 12

H≤ rL ª ≤ 3 ª 83, 10< ª è!!!!!!!48 Hmod 13L


55




48 Hmod 11L


11L = 1



l = 82, 6, 7, 8, 10<Se elige al azar el valor b = 6

n - 1 = 10 = 21 5 fl s = 1, t = 5



i yi gi ui vi

0 0 11 1 0

1 0 48 0 1

2 0 11 1 0

3 4 4 -4 1

4 2 3 9 -2

5 1 1 -13 3

6 3 0 48 -11

Inverso modular.

3 ª 48-1 Hmod 11L



i di ri ci

0 0 9 10

H≤ rL ª ≤ 9 ª 89, 2< ª è!!!!!!!48 Hmod 11L



56







H≤ xL ª ≤ 68 = 868, 75<H≤ yL ª ≤ 42 = 842, 101<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

868, 75, 42, 101< ªè!!!!!!!

48 Hmod 143L 143 = 13.11


n = p.q es un número compuesto de dos primos enteros.a) n = 31.29 = 899 y a = 645.



8r1, r2, r3, r4< ªè!!!!!!!!!!

645 Hmod 899L 899 = 31.29




645 Hmod 31L


31L = 1



l = 83, 6, 11, 12, 13, 15, 17, 21, 22, 23, 24, 26, 27, 29, 30<Se elige al azar el valor b = 22


57

n - 1 = 30 = 21 15 fl s = 1, t = 15



i yi gi ui vi

0 0 31 1 0

1 0 645 0 1

2 0 31 1 0

3 20 25 -20 1

4 1 6 21 -1

5 4 1 -104 5

6 6 0 645 -31

Inverso modular.

5 ª 645-1 Hmod 31L



i di ri ci

0 0 5 30

H≤ rL ª ≤ 5 ª 85, 26< ª è!!!!!!!!!!645 Hmod 31L




645 Hmod 29L


29L = 1




n - 1 = 28 = 22 7 fl s = 2, t = 7


58



i yi gi ui vi

0 0 29 1 0

1 0 645 0 1

2 0 29 1 0

3 22 7 -22 1

4 4 1 89 25

5 7 0 -645 29

Inverso modular.

25 ª 645-1 Hmod 29L



i di ri ci

0 0 23 12

1 1 23 28

H≤ rL ª ≤ 23 ª 823, 6< ª è!!!!!!!!!!645 Hmod 29L








59


H≤ xL ª ≤ 470 = 8470, 429<H≤ yL ª ≤ 284 = 8284, 615<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

8470, 429, 284, 615< ªè!!!!!!!!!!

645 Hmod 899L 899 = 31.29

8470, 429, 284, 615<



8r1, r2, r3, r4< ªè!!!!!!!!!!

645 Hmod 899L 899 = 31.29




645 Hmod 31L


31L = 1



l = 83, 6, 11, 12, 13, 15, 17, 21, 22, 23, 24, 26, 27, 29, 30<Se elige al azar el valor b = 17

n - 1 = 30 = 21 15 fl s = 1, t = 15



i yi gi ui vi

0 0 31 1 0

1 0 645 0 1

2 0 31 1 0

3 20 25 -20 1

4 1 6 21 -1

5 4 1 -104 5

6 6 0 645 -31

Inverso modular.

5 ª 645-1 Hmod 31L


60



i di ri ci

0 0 5 30

H≤ rL ª ≤ 5 ª 85, 26< ª è!!!!!!!!!!645 Hmod 31L




645 Hmod 29L


29L = 1




n - 1 = 28 = 22 7 fl s = 2, t = 7



i yi gi ui vi

0 0 29 1 0

1 0 645 0 1

2 0 29 1 0

3 22 7 -22 1

4 4 1 89 25

5 7 0 -645 29

Inverso modular.

25 ª 645-1 Hmod 29L


61



i di ri ci

0 0 23 12

1 1 23 28

H≤ rL ª ≤ 23 ª 823, 6< ª è!!!!!!!!!!645 Hmod 29L








H≤ xL ª ≤ 470 = 8470, 429<H≤ yL ª ≤ 284 = 8284, 615<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

8470, 429, 284, 615< ªè!!!!!!!!!!

645 Hmod 899L 899 = 31.29

8470, 429, 284, 615<


62

à Problema 24. Calcular la raíz è!!!a Hmod nL en los casos indicados, y empleando en el

algoritmo de cálculo el teorema Chino de los restos congruentes.a) n = 17.29 = 423 y a = 132.b) n = 19.23 = 437 y a = 330.



8r1, r2, r3, r4< ªè!!!!!!!!!!

132 Hmod 493L 493 = 17.29




132 Hmod 17L


17L = 1



l = 83, 5, 6, 7, 10, 11, 12, 14<Se elige al azar el valor b = 5

n - 1 = 16 = 24 1 fl s = 4, t = 1



i yi gi ui vi

0 0 17 1 0

1 0 132 0 1

2 0 17 1 0

3 7 13 -7 1

4 1 4 8 -1

5 3 1 -31 4

6 4 0 132 -17

Inverso modular.

4 ª 132-1 Hmod 17L


63



i di ri ci

0 0 13 5

1 1 13 8

2 16 2 13

3 16 9 16

H≤ rL ª ≤ 9 ª 89, 8< ª è!!!!!!!!!!132 Hmod 17L




132 Hmod 29L


29L = 1




n - 1 = 28 = 22 7 fl s = 2, t = 7



i yi gi ui vi

0 0 29 1 0

1 0 132 0 1

2 0 29 1 0

3 4 16 -4 1

4 1 13 5 -1

5 1 3 -9 2

6 4 1 41 20

7 3 0 -132 29


64

Inverso modular.

20 ª 132-1 Hmod 29L



i di ri ci

0 0 25 17

1 1 25 28

H≤ rL ª ≤ 25 ª 825, 4< ª è!!!!!!!!!!132 Hmod 29L

Cálculo del sistema de ecuaciones congruenciales mediante

el teorema Chino de restos congruentes.

x ª 8 Hmod 17Lx ª 4 Hmod 29Ln = H 17 L H 29 L = 493


yi ª HnêpiL-1 Hmod piL

y1 ª H493ê17L-1 ª 29 ª 10 Hmod 17Ly2 ª H493ê29L-1 ª 17 ª 12 Hmod 29L

La solución x ª @‚i=1

r

HnêpiL yi xiD Hmod nL es

x ª H 493ÅÅÅÅÅÅÅÅÅÅÅ17

.10.8 L + H 493ÅÅÅÅÅÅÅÅÅÅÅ29

.12.4 Lx ª 178 Hmod 493L





65





r




.12.25 Lx ª 25 Hmod 493L


H≤ xL ª ≤ 178 = 8178, 315<H≤ yL ª ≤ 25 = 825, 468<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

8178, 315, 25, 468< ªè!!!!!!!!!!

132 Hmod 493L 493 = 17.29



8r1, r2, r3, r4< ªè!!!!!!!!!!

330 Hmod 437L 437 = 19.23




330 Hmod 19L


19L = 1



l = 82, 3, 8, 10, 12, 13, 14, 15, 18<Se elige al azar el valor b = 8

n - 1 = 18 = 21 9 fl s = 1, t = 9




66

i yi gi ui vi

0 0 19 1 0

1 0 330 0 1

2 0 19 1 0

3 17 7 -17 1

4 2 5 35 -2

5 1 2 -52 3

6 2 1 139 11

7 2 0 -330 19

Inverso modular.

11 ª 330-1 Hmod 19L



i di ri ci

0 0 11 18

H≤ rL ª ≤ 11 ª 811, 8< ª è!!!!!!!!!!330 Hmod 19L




330 Hmod 23L


23L = 1




n - 1 = 22 = 21 11 fl s = 1, t = 11




67

i yi gi ui vi

0 0 23 1 0

1 0 330 0 1

2 0 23 1 0

3 14 8 -14 1

4 2 7 29 -2

5 1 1 -43 3

6 7 0 330 -23

Inverso modular.

3 ª 330-1 Hmod 23L



i di ri ci

0 0 13 22

H≤ rL ª ≤ 13 ª 813, 10< ª è!!!!!!!!!!330 Hmod 23L








r




.17.10 Lx ª 217 Hmod 437L


68








r




.17.13 Lx ª 312 Hmod 437L


H≤ xL ª ≤ 217 = 8217, 220<H≤ yL ª ≤ 312 = 8312, 125<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

8217, 220, 312, 125< ªè!!!!!!!!!!

330 Hmod 437L 437 = 19.23

à Problema 25. Calcular la raíz è!!!a Hmod nL en los casos indicados, y empleando en el

algoritmo de cálculo el teorema Chino de los restos congruentes.a) n = 23.29 = 667 y a = 223.



8r1, r2, r3, r4< ªè!!!!!!!!!!

223 Hmod 667L 667 = 23.29




223 Hmod 23L


23L = 1



69



n - 1 = 22 = 21 11 fl s = 1, t = 11



i yi gi ui vi

0 0 23 1 0

1 0 223 0 1

2 0 23 1 0

3 9 16 -9 1

4 1 7 10 -1

5 2 2 -29 3

6 3 1 97 13

7 2 0 -223 23

Inverso modular.

13 ª 223-1 Hmod 23L



i di ri ci

0 0 4 22

H≤ rL ª ≤ 4 ª 84, 19< ª è!!!!!!!!!!223 Hmod 23L




223 Hmod 29L


29L = 1



70



n - 1 = 28 = 22 7 fl s = 2, t = 7



i yi gi ui vi

0 0 29 1 0

1 0 223 0 1

2 0 29 1 0

3 7 20 -7 1

4 1 9 8 -1

5 2 2 -23 3

6 4 1 100 16

7 2 0 -223 29

Inverso modular.

16 ª 223-1 Hmod 29L



i di ri ci

0 0 7 12

1 1 7 28

H≤ rL ª ≤ 7 ª 87, 22< ª è!!!!!!!!!!223 Hmod 29L





71





r




.24.7 Lx ª 326 Hmod 667L








r




.24.22 Lx ª 602 Hmod 667L


H≤ xL ª ≤ 326 = 8326, 341<H≤ yL ª ≤ 602 = 8602, 65<8r1, r2, r3, r4< ª è!!!!

a Hmod nL n = p.q

8326, 341, 602, 65< ªè!!!!!!!!!!

223 Hmod 667L 667 = 23.29


72

6. Problema del logaritmo discreto. (DLP)

El problema inverso de la exponenciación es el cálculo de logaritmos discretos. La

seguridad de muchos protocolos criptográficos de clave pública reside en la dificultad de

resolver el problema del logaritmo discreto. El cálculo de logaritmos discretos es

considerado como el problema inverso de la exponenciación. Un ejemplo es el algoritmo

propuesto por Diffie y Hellman para el intercambio de claves públicas a través de canales

abiertos, y el método de cifrado de clave pública de El Gammal. Antes de comenzar a

definir el problema del logaritmo discreto, se procederá a enunciar la definición de

generador. Dado el conjunto �p, con p primo, se dice que a e �p es un generador de �p si

se cumple " b e �p $ i tal que ai = b. Así, se considera un número primo p, y sea �p el

grupo cíclico finito formado por los valores enteros positivos y menores que p con respecto

de la multiplicación modular (módulo p). En estas condiciones, se suponen dos valores

enteros g, b e �p, siendo n el orden de g en el grupo �p, es decir, el menor valor entero

para el que se verifica que:

(44)gn ª 1 Hmod pL .

El problema del logaritmo discreto consiste en encontrar, si existe, el valor x con

0 b x < n, tal que es solución de la congruencia:

(45)gx ª b Hmod pL .

Así, en el caso de que exista este valor entero, se denomina logaritmo discreto de b

en base g módulo p, es decir:


73

(46)x ª logg b Hmod pL .

El problema del logaritmo discreto tiene solución siempre y cuando el entero b

pertenezca al subgrupo de valores enteros generados por g, es decir, que b œ < g >. Así,

puesto que p es un número primo, lo anterior sucede siempre en el caso de que el entero g

sea un generador de orden n = p - 1, ya que entonces cualquier otro entero w e �p puede

expresarse de la forma:

(47)w ª gs Hmod pL .

para algún valor s tal que 0 b s < p - 1, es decir, que el entero g es un generador de todo el

grupo �p.

A continuación, se procederá a explicar y mostrar con ejemplos los métodos más

utilizados para determinar logaritmos discretos.

6.1 Algoritmo baby-step giant-step

Se trata de un algoritmo basado en el método de búsqueda exhaustiva aunque su

estructura varía ligeramente de dicho método.

Si m =è!!!n , redondeando al número entero superior al obtenido, el algoritmo

paso-gigante paso-enano se basa en la siguiente observación. Si b = ax, o lo que es lo

mismo, x = loga b, entonces se verifica la ecuación

(48)x = i *m + j con 0 i, j � m.

Por tanto, ax = ai*m *a j, lo que significa que b Ha-mLi = a j. El valor de la x se

obtiene fácilmente a partir de la ecuación mencionada.


74

El algoritmo paso-gigante paso-enano requiere una capacidad de almacenamiento

para grupos de elementos de �(è!!!n ). Construir la tabla implica multiplicaciones de

�(è!!!n ). Del mismo orden de ejecución son las operaciones que se desarrollan dentro del

último bucle for por lo que, suponiendo que cada multipicación de cada grupo de ellas

conlleva un tiempo de ejecución mayor que log n comparaciones, se puede afirmar que el

tiempo total de ejecución es de �(è!!!n ) multiplicaciones en el grupo.

è Algoritmo 8. Algoritmo Baby-step giant step.

Input (a, b, p)

m ≠ è!!!!

p

For j = 0, 1, ... m do

h j ≠ a j mod b

End

For j = 0, 1, ..., m do

g j ≠ b * b j mod p

If (h j = a) then

Break

End

End

For i = 0, 1, ..., m - 1 do

g ≠ b * a-m * i mod p

hi ≠ g

If (hi = a) then

Return (i *m + j)

End

If (i = m) then

Return (g*a-m)

End

End

Output


75


à Problema 26. Sea p = 113. �113* es un subgrupo cíclico de orden n = 112 generado por

g = 3. Considerando b = 57, calcúlese el logaritmo discreto x ª logg b Hmod pLempleando el método de baby-step giant-step.

Cálculo del logaritmo discreto.

Algoritmo de Baby-step Giant-step.

x ª loga b Hmod pL

El valor a = 3 es un generador de un grupo cíclico G de

orden n = 112 . Además el valor de b = 57 . Por tanto tenemos la

siguiente ecuación a resolver.

x ª log3 57 Hmod 113L

Así, tenemos la siguiente tabla :

j 3 j Hmod 113L0 1

1 3

2 9

3 27

4 81

5 17

6 51

7 40

8 7

9 21

10 63

Finalmente tenemos la tabla:


76

i 57 µ 58 j Hmod 113L0 57

1 29

2 100

3 37

4 112

5 55

6 26

7 39

8 2

9 3

La solución final es

100 ª log3 57 Hmod 113L





x ª loga b Hmod pL







77

j 5 j Hmod 97L0 1

1 5

2 25

3 28

4 43

5 21

6 8

7 40

8 6

9 30


i 37 µ 11 j Hmod 97L0 37

1 19

2 15

3 68

4 69

5 80

6 7

7 77

8 71

9 5


91 ª log5 37 Hmod 97L


78





x ª loga b Hmod pL






j 2 j Hmod 383L0 1

1 2

2 4

3 8

4 16

5 32

6 64

7 128

8 256

9 129

10 258

11 133

12 266

13 149

14 298

15 213

16 43

17 86

18 172

19 344



79

i 228 µ 54 j Hmod 383L0 228

1 56

2 343

3 138

4 175

5 258

6 144

7 116

8 136

9 67

10 171

11 42

12 353

13 295

14 227

15 2


301 ª log2 228 Hmod 383L


80

6.2 Algoritmo rho de Pollard para logaritmos

Se trata de un tipo de algoritmo dentro de los considerados como aleatorio que, al

igual que el giant-step baby-step , se utiliza para el cálculo de logaritmos discretos. El

tiempo de ejecución esperado es el mismo para ambos, sin embargo el algortimo rho de

Pollard requiere un ingente cantidad de espacio en memoria en comparación con el

giant-step baby-step . Por esta razón es más recomendable utilizar este último a la hora de

resolver ejercicios prácticos.

Se parte de la base considerando G como un grupo cíclico cuyo orden n es primo.

Este grupo G se divide a su vez en tres subgrupos S1, S2 y S3 que deben tener

aproximadamente el mismo tamaño. Así, x pertenecen a S1 si x ª 1 Hmod 3L, a S2 si

x ª 0 Hmod 3L y a S3 si x ª 2 Hmod 3L. De esta manera se consigue distribuir de manera

equitativa todos los elementos de G en los subgrupos mencionados. El algoritmo

comienza definiendo una secuencia de un grupo de elementos x0, x1, x2, ... que se definen

según las ecuaciones

(49)xi+1 = f HxiL = b * xi si xi e S1

(50)xi+1 = f HxiL = xi2 si xi e S2

(51)xi+1 = f HxiL = a* xi si xi e S3,

cumpliéndose para todas ellas que i r 0. Esta secuencia define a su vez otras dos secuencias

de enteros a0, a1, a2, ... y b0, b1, b2, .... satisfaciéndose en todo momento la ecuación xi

= aai*bbi para valores de i t 0. Análogamente al método para hallar cada xi+1, se dispone

de las siguientes ecuaciones para poder avanzar por la secuencia de ai y bi. Estas

ecuaciones son, para ai:


81

(52)ai+1 = ai si xi e S1

(53)ai+1 = 2 *ai mod n si xi e S2

(54)ai+1 = ai + 1mod n si xi e S3

Y para bi:

(55)bi+1 = bi + 1mod n si xi e S1

(56)bi+1 = 2 *bi mod n si xi e S2

(57)bi+1 = bi si xi e S3

Utilizando el algoritmo de Búsqueda Cíclica de Floyd es muy interesante calcular,

para cada i, el valor de x2 i , a2 i y b2 i, ya que cuando xi = x2 i se cumple que

aai * bbi = aa2 i * bb2 i y por tanto que bbi-b2 i = aa2 i-ai . Tomando logaritmos a ambos lados se

llega a la expresión fundamental del algoritmo:

(58)Hbi - b2 iL * loga b ª Ha2 i - aiL Hmod nL

que servirá para obtener el valor del logaritmo discreto propuesto.

El tiempo esperado de ejecución del algoritmo rho de Pollard es de �(è!!!n ), aunque

hay que tener en cuenta como se ha dicho al inicio de la explicación que requiere un

espacio de memoria considerable.

è Algoritmo 9. Algoritmo de rho de Pollard para logaritmos.

Input (a, n, b)

x0 ≠ 1

a0≠ 0

b0≠ 0

For i = 0, 1, 2, ..., n do

xi ≠ xi-1

ai ≠ ai-1

bi ≠ bi-1

x2 i ≠ x2 i-2

a2 i ≠ a2 i-2


82

b2 i ≠ b2 i-2

If (xi = x2 i) then

r ≠ bi - b2 i (mod n)

If (r = 0) then

Return ()

Else

x ≠ r-1(a2 i - ai) (mod n)

Return (x)

End

End

End

Output



g = 3. Considerando b = 57, calcúlese el logaritmo discreto x ª logg b Hmod pLempleando el método de rho de Pollard.


Algoritmo rho de Pollard para logaritmos.

x ª loga b Hmod pL

El valor a = 3 es un generador de un subgrupogrupo G de

orden primo n = 31 . Además el valor de b = 57.

Por tanto tenemos la siguiente ecuación a resolver:



83


i xi ai bi x2 i a2 i b2 i

1 57 0 1 85 0 2

2 85 0 2 83 0 6

3 99 0 3 69 2 6

4 83 0 6 112 8 24

5 23 1 6 55 9 25

6 69 2 6 50 18 21

7 15 4 12 75 19 22

8 112 8 24 44 7 14

9 56 8 25 66 8 15

10 55 9 25 73 17 30

11 84 9 26 61 3 0

12 50 18 21 111 6 2

13 37 19 21 2 12 5

14 75 19 22 36 26 10

15 88 7 13 46 22 20

16 44 7 14 69 23 21

17 19 8 14 112 30 22

18 66 8 15 55 31 23

19 62 16 30 50 0 17

20 73 17 30 75 1 18

21 93 17 31 44 2 6

22 61 3 0 66 3 7

23 87 3 1 73 7 14

24 111 6 2 61 14 30

25 4 12 4 111 28 0

26 2 12 5 2 25 1


11 Hmod 113L ª log3 57



El número n = 96 introducido no es primo.

El orden del subgrupo G de�97* tiene que ser primo.

El algoritmo no puede continuar.


84




Algoritmo rho de Pollard para logaritmos.

x ª loga b Hmod pL

El valor a = 2 es un generador de un subgrupogrupo G de

orden primo n = 191 . Además el valor de b = 228.

Por tanto tenemos la siguiente ecuación a resolver:



i xi ai bi x2 i a2 i b2 i

1 228 0 1 279 0 2

2 279 0 2 184 1 4

3 92 0 4 14 1 6

4 184 1 4 256 2 7

5 205 1 5 304 3 8

6 14 1 6 121 6 18

7 28 2 6 144 12 38

8 256 2 7 235 48 152

9 152 2 8 72 48 154

10 304 3 8 14 96 118

11 372 3 9 256 97 119

12 121 6 18 304 98 120

13 12 6 19 121 5 51

14 144 12 38 144 10 104


110 Hmod 383L ª log2 228


85

6.3 Algoritmo Pohlig - Hellman

A continuación, se describe un posible algoritmo para resolver el problema del

logaritmo discreto (Pohlig y M. E. Hellman). Para ello, el algoritmo supone conocidos los

factores primos del orden n = p - 1 del grupo �p. Se supone que este orden es de la forma:

(59)n = p - 1 =‰i=1

i=t

piei

con 0 b xi < piei - 1 y representando cada valor entero xi para i = 1, ..., t en una base

pi-aria de forma que:

(60)xi = h0 + h1 p1 + ... + hei-1 piei-1

donde h j es tal que 0 b h j < pi. Finalmente, el valor entero x se calcula aplicando el

teorema chino de los restos congruentes. Con todo lo anterior, el algoritmo de

Pohlig-Hellman para el cálculo de logaritmos discretos módulo p se presenta a

continuación:

è Algoritmo 10. Algoritmo para el cálculo del logaritmo discreto de Pohlig-Hellman

Input Hp, g, bL

n = p - 1 ≠¤i=1i=t pi

ei

For i = 1, ..., t do

c ≠ 1

h-1 ≠ 0

g´ ª gp-1êpi Hmod pLFor j = 0, ..., ei - 1 do

c ª c gh j-1 pij-1 Hmod pL

b£ ª Hb c-1LHp-1Lêpij+1 Hmod pL

(* Búsqueda exhaustiva del entero h j con 0 b h j < pi y tal que

b£ ª g£h j Hmod pL *) For k = 0, ..., pi - 1 do

If Hg£hk Hmod pL = b£L Then

Break

End


86

End

h j ≠ k

End

xi ≠ h0 + h1 pi + ... + h1ei-1 pi

ei-1

End

x Hmod pL ≠ Teorema chino restos congruentes

Hx1 Hmod p1e1 L, ..., xt Hmod pt

et LLReturn H xLOutput

Con todo lo anterior, si el problema del logaritmo discreto es resoluble para cada

uno de los factores primos divisores de Hp - 1L, entonces el cálculo del logaritmo discreto

Hmod pL es a su vez viable. Sin embargo, es conveniente hacer notar en este punto que,

cuando se trabaja con números enteros grandes, y p es un primo fuerte, es decir, de la

forma:

(61)p = k p£ + 1

siendo k una constante pequeña y p£ otro número grande, entonces este algoritmo, en

particular la búsqueda exhaustiva, tiene una complejidad computacional tan elevada que la

resolución del problema llega a hacerse inviable. Esto último puede hacerse extensivo a la

mayoría de los algoritmos propuestos para resolver el problema del logaritmo discreto, y es

precisamente lo deseable cuando el logaritmo discreto se utiliza como función de una sola

dirección en criptografía de clave pública. En este caso, es conveniente que el número

primo p sea de la forma antes indicada, es decir, que Hp - 1L contenga a su vez un número

primo grande como factor, puesto que ello permite asegurar la dificultad de resolución del

problema del logaritmo discreto y, de esa forma, garantizar la seguridad de los protocolos

criptográficos de clave pública basados en él. Existen, a su vez, algunos casos particulares

en los que el cálculo del logaritmo discreto módulo p es viable para valores de p grandes,


87

como sucede, por ejemplo, cuando el número primo p tiene una representación polinómica

de la forma:

(62)p = ‚i=0

i=d

pi mi

siendo d, pi y m valores pequeños (d < 10, pi < 50). Esto fue demostrado por D. M.

Gordon. Una posible forma de evitar este problema fue, a su vez, apuntada por Gordon,

quien indicó cómo detectar y evitar que los primos tengan tales características debilitantes.


à Problema 32. Calcúlese el logaritmo discreto x ª logg b Hmod pL empleando el métodode Pohlig-Hellman con los valoresa) p = 251, g = 37, b = 43b) p = 251, g = 71, b = 210.

Cálculo del logaritmo discreto. Algoritmo de Pohlig-Hellman.

x ª logg b Hmod pLx ª log37 43 Hmod 251L

g£ ª gHp-1Lêpi Hmod pLc ª c gh j-1 Hpi L j-1 Hmod pLb£ ª Hb c-1LHp-1LêHpi L j+1 Hmod pLh j ª logg£ Hb£L Hmod pL

Factorización del orden del grupo

n = p - 1 = 250 = H 21 L H 53 L

i = 1 Hc, h-1L = H1, 0Lg£ ª 37H251-1Lê2 Hmod 251L ª 250 Hmod 251L

Hi, jL = H1, 0Lc ª H1L 37H0L H1-2L ª 1 Hmod 251Lb£ ª H43 1-1LH250LêH2L ª 250 Hmod 251Lh0 ª log250 H250L ª 1 Hmod 251L


88

x1 = 1 = 1



Hi, jL = H2, 1Lc ª H1L 37H1L H1L ª 37 Hmod 251Lb£ ª H43 37-1LH250LêH25L ª 113 Hmod 251Lh1 ª log20 H113L ª 4 Hmod 251L


x2 = 1 + 4 H 5 L + 3 H 5 L2 = 96








r




.1.1 Lx ª 221 Hmod 250L


89

Logaritmo discreto.

x ª logg b Hmod pLx ª log37 43 Hmod 251L ª 221 Hmod 251L





n = p - 1 = 250 = H 21 L H 53 L



x1 = 1 = 1





90


x2 = 2 + 4 H 5 L + 2 H 5 L2 = 72








r




.1.1 Lx ª 197 Hmod 250L

Logaritmo discreto.


à Problema 33. Sea p = 229 y el número g = 6 es generador de �229* de orden n = 228.

Considerando b = 13, calcúlese el logaritmo discreto x ª logg b Hmod pL empleando elmétodo de Pohlig-Hellman.




91



n = p - 1 = 228 = H 22 L H 31 L H 191 L




x1 = 1 = 1



x2 = 0 = 0



92

Hi, jL = H3, 0Lc ª H1L 6H0L H1-- 19L ª 1 Hmod 229Lb£ ª H13 1-1LH228LêH19L ª 61 Hmod 229Lh0 ª log165 H61L ª 3 Hmod 229L

x3 = 3 = 3



x ª 1 Hmod 4Lx ª 0 Hmod 3Lx ª 3 Hmod 19Ln = H 19 L H 3 L H 4 L = 228



y1 ª H228ê4L-1 ª 57 ª 1 Hmod 4Ly2 ª H228ê3L-1 ª 76 ª 1 Hmod 3Ly3 ª H228ê19L-1 ª 12 ª 8 Hmod 19L


r





.1.1 Lx ª 117 Hmod 228L

Logaritmo discreto.



g = 5. Considerando b = 35, calcúlese el logaritmo discreto x ª logg b Hmod pLempleando el método de Pohlig-Hellman.




93



n = p - 1 = 96 = H 25 L H 31 L







x1 = 0 = 0



94


x2 = 2 = 2








r


x ª H 96ÅÅÅÅÅÅÅÅ32

.11.0 L + H 96ÅÅÅÅÅÅÅÅ3

.2.2 Lx ª 32 Hmod 96L

Logaritmo discreto.



95

7. El problema de Diffie - Hellman (DHP)

En la criptografía simétrica las claves de cifrado y descifrado son idénticas y deben

mantenerse secretas para garantizar la seguridad del sistema. Esta condición dificulta el

proceso del intercambio de claves entre los comunicantes puesto que los procedimientos

existentes para ello están basados en estructuras jerárquicas, de forma que siempre existe al

menos una clave maestra cuyo eventual cambio ha de comunicarse a los interesados a

través de un canal seguro. En estas condiciones, si el correo no tiene acceso a alguno de los

comunicantes, entonces éste último queda incomunicado. Esta sería, por ejemplo, la

situación en la que se encontraría una unidad militar si su clave secreta de comunicación

fuera interceptada en territorio enemigo.

En 1976 W. Diffie y M. E. Hellman inventaron un método para el intercambio de

claves secretas en canales abiertos. El procedimieno está basado en un sistema de claves

asimétrico en el que cada comunicante posee dos claves, una de ellas secreta y la otra

pública. Este método no sólo resolvió el problema del intercambio de claves, sino que

además fue el origen de la denominada criptografía de clave pública, cuya aplicación tiene

importantes implicaciones en el ámbito de la seguridad de las comunicaciones digitales.

El método propuesto por Diffie y Hellman para el intercambio de claves secretas a

través de canales abiertos está basado en la existencia de funciones de una sola dirección.

Una función de una sola dirección es aquella cuyo cálculo directo es viable, mientras que el

cálculo de la función inversa tiene tal complejidad que resulta imposible. A modo de


96

ejemplo, si y es una función de este tipo, el cálculo y = f(x) es sencillo, pero el cálculo x =

f -1HyL es tan complejo que no puede realizarse con los conocimientos matemáticos

actuales, ni aún disponiendo de las más avanzadas capacidades de cálculo. Una función de

una sola dirección típica es la exponenciación modular dada por la ecuación

(63)y ª gx Hmod pL

con g , x valores enteros y siendo p un número primo grande de 200 o más dígitos. En estas

condiciones, el cálculo de la función y es posible, ya que tiene un orden de complejidad

� (log p), pero el cálculo de la función inversa

(64)y ª logg y Hmod pL

tiene una complejidad tan elevada que es totalmente inviable para números del tamaño

referido. Esta situación se conoce como la función del logaritmo discreto y su cálculo tiene

una complejidad exponencial dad por ‰è!!!!!!!!!!!!!!!!!!!!!!!!!!lnHpL lnlnHpL .

La función de exponenciación modular que se acaba de presentar fue precisamente

la utilizada por Diffie y Hellman en su procedimiento para el intercambio de claves secretas

a través de canales abertos que se describe a continuación. Consideremos para ello un

número primo grande p (>200 dígitos) y sea g un entero generador del grupo multiplicativo

�p tal que sus potencias generan todos los elementos del grupo. Los valores g y p son

públicos. Supongamos ahora que dos comunicantes A y B desean intercambiar una clave

secreta a través de una canal abierto. Para ello, A elige un entero aleatorio secreto xa tal que

1 � xa � p - 1 y envía a B el valor público ya dado por :

(65)ya ª gxa Hmod pL


97

Por su parte, B elige un entero aleatorio secreto xb tal que 1 � xb � p -1 y envía a A

el valor público ya dado por :

(66)yb ª gxb Hmod pL

En estas condiciones, B calcula el valor secreto zab dado por la ecuación

(67)zab ª yaxb ª gxa xb Hmod pL

y A calcula el valor secreto de zba dado por la ecuación

(68)zba ª ybxa ª gxb xa Hmod pL

Obviamente el valor entero zab = zba puede ser utilizado como clave secreta

compartida entre los comunicantes A y B para las posteriores cifradas mediante el sistema

de cifrado simétrico. Las claves públicas ya e yb, así como las claves secretas xa y xb, no se

utilizan propiamente para cifrar y descifrar sino solamente para generar una clave secreta

común que pueda ser utilizada posteriormente en cualquier sistema de cifrado simétrico

(por ejemplo, se pueden seleccionar 64 bits de zab = zba como clave para DES).

è Algoritmo 11. Algoritmo para el cálculo de claves Diffie - Hellman.

Input (p, a)

x ≠ RandomHInteger, 1, ..., p - 1La ≠ a x mod p

y ≠ RandomHInteger, 1, ..., p - 1Lb ≠ a y mod p

K ≠ a xy mod p

Return (K )

Output

En relación a este sistema de generación de claves y propuesto también por sus

creadores, surge el llamado problema de Diffie - Hellman. Está muy relacionado con el


98

problema del Logaritmo Discreto y resulta muy representativo en el ámbito de la

Criptografía en clave pública pues en su aparente irrompibilidad se basan muchos sistema

de cifrado actuales incluyendo el propio Diffie - Hellman o ElGamal.

El problema de Diffie - Hellman plantea lo siguiente: dado un grupo cíclico finito

G, un generador a de G y los términos aa (mod p) y ab (mod p), encontrar el valor de aab

(mod p). Supóngase además que el problema del Logaritmo Discreto se pudiera resolver de

manera eficiente en �p* . Entonces, dados valores de a, p, aa mod p y ab mod p, se podría

primero encontrar el valor de a a partir de a, p y aa mod p y luego calcular HabLa = aab mod

p. Dicha relación establece una relación directa entre el problema de Diffie - Hellman y el

problema del Logaritmo Discreto. La pregunta a si ambos son computacionalmente

equivalentes permanece aún a día de hoy sin respuesta. Sin embargo, recientes estudios en

la materia han demostrado que, a partir de una serie de suposiciones, son

computacionalmente equivalentes.


à Problema 35. Sea el sistema Diffie - Hellman para el intercambio de claves definidopor:

Número primo p = 71Generador g = 21 del grupo �71

*

Realizar los pasos necesarios para que los comunicantes A y B logren intercambiar conéxito un valor secreto.

Inicio del algoritmo Diffie - Hellman para el intercambio de

claves entre dos interlocutores A y B.

Paso 1:

A escoge un número aleatorio a, comprendido entre 1 y 70.

Se tiene que a = 46. Envía entonces a B el valor

a a = 2146 ª 9 Hmod 71L


99

Paso 2:

B escoge un número aleatorio b, comprendido entre 1 y 70.

Se tiene que b = 24. Envía entonces a A el valor

a b = 2124 ª 8 Hmod 71L

Paso 3:

A recibe el valor 9

K = HaaLb Hmod pL = H2146L24 Hmod 71L

y calcula el valor K.

Paso 4:

B recibe el valor 8

K = Ha bLa Hmod pL = H2124L46 Hmod 71L


La clave privada que comparten ahora A y B es K = 18.

Un escucha S puede llegar a conocer los valores a , a x y a y

del protocolo anterior, pero no puede conocer la información

secreta K compartida por A y B.

à Problema 36. Sea el sistema Diffie - Hellman para el intercambio de claves definidopor:

Número primo p = 3943Generador g = 788 del grupo �3943

*

Realizar los pasos necesarios para que los comunicantes A y B logren intercambiar conéxito un valor secreto.

Inicio del algoritmo Diffie - Hellman para el intercambio de

claves entre dos interlocutores A y B.

Paso 1:

A escoge un número aleatorio a, comprendido entre 1 y 3942.

Se tiene que a = 434. Envía entonces a B el valor

a a = 1234434 ª 3206 Hmod 3943L


100

Paso 2:

B escoge un número aleatorio b, comprendido entre 1 y 3942.

Se tiene que b = 797. Envía entonces a A el valor

a b = 1234797 ª 3753 Hmod 3943L

Paso 3:

A recibe el valor 3206

K = HaaLb Hmod pL = H1234434L797 Hmod 3943L


Paso 4:

B recibe el valor 3753

K = Ha bLa Hmod pL = H1234797L434 Hmod 3943L


La clave privada que comparten ahora A y B es K = 2941.

Un escucha S puede llegar a conocer los valores a , a x y a y

del protocolo anterior, pero no puede conocer la información

secreta K compartida por A y B.


101

8. El problema de la suma de un subconjunto. (SUBSET-SUM)

La dificultad de resolver el problema del subconjunto es la base de la presunta

seguridad del primer sistema de cifrado de clave pública, llamado el sistema de la mochila

de Merkle-Hellman.

El problema de la suma de un subconjunto consiste en lo siguiente. Dado un

conjunto de números positivos 8 a1, a2, ..., an <, llamado el conjunto de la mochila, y un

número positivo s, determinar si un subconjunto de a j suma la cifra s. Es equivalente a

plantear si existe o no un xi tal que

(69)xi œ 80, 1< , 1 i n

cumpliéndose que

(70)‚i=1

n

ai xi = s.

Se puede demostrar que el problema es computacionalmente equivalente a su

versión computacional, que es precisamente determinar un xi tal que se cumpla la ecuación

(70), suponiendo que xi existe. Esto significa que no se conoce mejor solución que explorar

todos los 2n - 1 subconjuntos posibles de 8 a1, a2, ..., an < hasta encontrar uno que cumpla

con la condición establecida. Es por ello por lo que el problema de la suma de un

subconjunto se considera un problema NP-completo y por tanto forma parte del

subconjunto de los problemas de decisión en NP. Los problemas NP se caracterizan porque

es fácil verificar si una respuesta propuesta es válida, pero es computacionalmente


102

imposible encontrar una solución válida si el número es muy grande.

El algoritmo propuesto a continuación para resolver el problema de la suma de un

subconjunto es de tiempo de ejecución exponencial, como todos los problemas

NP-completos. Concretamente el orden de ejecución es �(2n) y, por tanto, resulta

inficiente para números muy grandes.

è Algoritmo 12. Algoritmo para el problema de la suma de un subconjunto.

Input ({a1, a2, ..., an }, s)

For Hx1, x2, ..., xnL e H�2L n do

l ≠ ⁄i=1n ai xi

If Hl = sLReturn H Hx1, x2, ..., xnL L

End

End

Return ()

Output


à Problema 37. Sea el conjunto de números enteros positivos a = 8 4, 2, 2, 11, 6 < y elnúmero entero 8. Determinar si existe un subconjunto en a cuyos elementos sumen 8.

Inicio del algoritmo de la suma de un subconjunto.

Dado el conjunto de números enteros positivos

A = 8a1,a2,...,an<se quiere comprobar si existe un subconjunto de A que sume

el valor s. O lo que es lo mismo, se quiere determinar si

existe o no un vector de la forma

Hx1,x2,...,xnLtal que

xi e 80,1< con 1 i n

y se cumpla que

‚i=1

n

aixi = s


103

El vector de entre todos los posibles que cumple con las

condiciones establecidas es 80, 1, 1, 0, 1<.Así, el valor s se puede obtener de la forma :

‚i=1

5

80, 1, 1, 0, 1<84, 2, 2, 11, 6< = 10

à Problema 38. Sea el conjunto de números enteros positivos a = 8 7, 29, 43, 11, 21 < yel número entero 71. Determinar si existe un subconjunto en a cuyos elementos sumen71.








y se cumpla que

‚i=1

n

aixi = s

El vector de entre todos los posibles que cumple con las

condiciones establecidas es 81, 0, 1, 0, 1<.Así, el valor s se puede obtener de la forma :

‚i=1

5

81, 0, 1, 0, 1<87, 29, 43, 11, 21< = 71


104

à Problema 39. Sea el conjunto de números enteros positivosa = 8 2, 45, 55, 5, 6, 32, 67, 12, 23, 47, 34, 1, 8 < y el número entero 132.Determinar si existe un subconjunto en a cuyos elementos sumen 132.








y se cumpla que

‚i=1

n

aixi = s

El valor 345 no se puede obtener sumando elementos de

A = 82, 45, 55, 5, 6, 32, 67, 12, 23, 47, 34, 1, 8<.


105

9. Estudio de los tiempos de ejecución

9.1. Introducción teórica

A lo largo del proyecto, con cada algoritmo analizado y explicado se ha detallado

además su orden de ejecución así como la relevancia que tiene dicho orden a la hora de

aplicar el algoritmo en el ámbito de la Criptografía. Este hecho no tiene más intención que

resaltar la importancia del tiempo de ejecución de los algoritmos, resultando en la mayoría

de los casos lo que verdaderamente marca la diferencia entre unos y otros y lo que, en

definitiva, lo hace más o menos robusto. Con este estudio se pretende contrastar la teoría

con la práctica y comprobar si los tiempos de ejecución de los algoritmos estudiados se

corresponden con lo que los estudios del tema afirman. Lógicamente los recursos

informáticos con los que se disponen no son los idóneos para realizar un estudio de estas

características, pues ni Mathematica es un programa diseñado para soportar largos tiempos

de ejecución ni los ordenadores de que se disponen son, ni mucho menos, de los más

potentes que existen. Sin embargo, dentro de la medida de lo posible, resulta muy

interesante comprobar de manera práctica lo estudiado a lo largo de la realización del

proyecto.

La Teoría de la Complejidad Computacional estudia el tiempo que tarda en

ejecutarse un algoritmo dado, en función del número de operaciones a realizar y en función

de la entrada del algoritmo; es decir, estudia el tiempo de ejecución de un algoritmo para

proporcionar una salida o resultado en función del tamaño de la entrada o del dato. En

general, es difícil dar un tiempo de ejecución exacto, por lo que se recurre a optimizar el


106

peor de los posibles tiempos de ejecución; es decir, determinar el mejor de los peores

tiempos de ejecución.

Se considera que un algoritmo es polinomial si su peor caso de ejecución es de

orden �(nk), donde n es el tamaño de la entrada y k es una constante. Adicionalmente,

cualquier algoritmo que no pueda ser acotado por una función polinomial, se conoce como

exponencial. En general, los algoritmos polinomiales se consideran eficientes, mientras que

los exponenciales se consideran ineficientes.

Para poder observar de manera más sencilla los resultados obtenidos en este

estudio, se mostrará una gráfica que representará los datos de entrada necesarios para cada

algoritmo con respecto a los tiempos de ejecución. Además, para poder disponer de otra

variable que afecta al tiempo de ejecución distinta del tipo de algoritmo, se van a

desarrollar las pruebas sobre dos ordenadores diferentes. El primero, al que se denominará

a partir de ahora como PC1, es un ordenador con un procesador Intel Pentium Mobile

Centrino de 1,60GHz de potencia y 1GB de memoria RAM. El segundo, bastante más

antiguo, es un ordenador con un procesador Intel Pentium 4 de 2.53GHz de potencia y 768

KB de memoria RAM. Para hacer referencia a este último se usará el término PC2.

Lógicamente y para que el estudio tenga sentido, los datos que ambos ordenadores

procesarán serán idénticos.

9.2. El problema de la factorización

El tiempo de ejecución de un algoritmo de factorización de propósito específico

depende de las propiedades de sus factores desconocidos: tamaño, forma especial, etc.

Dichos factores cambian de un algoritmo a otro. Los algoritmos prouestos de factorización


107

propuestos en el proyecto son todos de propósito general y, como se ha explicado en cada

uno de sus apartados, se diferencian efectivamente en los datos de entrada.

Para desarrollar esta sección se ha elegido el algoritmo rho de Pollard, por

depender únicamente del número entero a factorizar como dato de entrada. El

procedimiento seguido ha sido generar aleatoriamente números enteros y factorizar cada

uno de ellos, siendo lógicamente cada vez mayor el tamaño del número a factorizar. En

concreto se han factorizado 190 números, y se ha plasmado el resultado en la siguiente

gráfica.

2.5×1016 5×1016 7.5×1016 1×10171.25×10171.5×1017

2

4

6

8

10

Figura 1

Algoritmo rho de Pollard; PC1


108

2.5×1016 5×1016 7.5×1016 1×10171.25×10171.5×1017

2

4

6

8

10

12

Figura 2

Algoritmo rho de Pollard; PC2

En general, los tiempos de ejecución no son demasiado elevados. El tiempo maximo

de ejecución fue 26.8125 segundos para factorizar el número 144095699816726843. El

menos fue prácticamente 0, dándose para varios números.

En primer lugar, llama la atención como en la gráfica no se identifican intervalos

claros de números para los que el tiempo de ejecución sea siempre mayor que el anterior

intervalo. La teoría afirma que no se conocen con exactitud los órdenes de ejecución de la

factorización pero que, en cualquier caso, se sabe que cuando el número de bits alcanza un

valor muy alto el tiempo se convierte en exponencial. En efecto, la gráfica muestra como,

en general, a mayor tamaño del número mayor es el tiempo de ejecución. Pero, ¿por qué

para ciertos números el tiempo de ejecución disminuye enormemente cuando lo lógico es

que fuese un poco mayor que el anterior? La explicación se encuentra en que los números

tratados han sido generados aleatoriamente y no basándose en unos parámetros iniciales a

comprobar antes de iniciar el proceso de factorización.

Así, el número 81435257807716133 tardó en factorizarse 10.375 segundos ,


109

mientras que el número 84525962415943681 tan sólo tardó 1.375 segundos. Peculiaridades

propias del algoritmo rho de Pollard provocan este tipo de incongruencias, como por

ejemplo el hecho de que este algoritmo trabaja buscando duplicados durante el proceso de

factorización y de hecho, ese es el motivo de que en cierta forma el tiempo de ejecución no

dependa tan sólo de la longitud del número, si no que depende también del tiempo en que

encuentre duplicados aunque, como se ha señalado, lo lógico es que tarde más tiempo

conforme aumente el tamaño del número aunque, como se ha demostrado, hay excepciones.

En cualquier caso queda demostrado que el tiempo de ejecución aumenta con el

tamaño del número a tratar y, llegado a un cierto número de bits, el problema se hace

computacionalmente intratable. El problema de factorizar enteros en tiempo polinómico no

ha sido aún resuelto. Si alguien lo consiguiera, tendría gran interés en el ámbito de la

Criptografía, ya que muchos criptosistemas dependen de su imposibilidad. En medios

académicos, la existencia de tal avance sería una gran noticia; en otros círculos, sería un

gran secreto, por razones obvias.

Para finalizar este apartado, comentar cómo efectivamente los recursos

computacionales afectan al tiempo de ejecución. Para la gráfica correspondiente al PC1, se

observa que éste ha tardado menos en general en desarrollar las tareas propuestas. En

compración con el mayor tiempo registrado en ambos ordenadores, el PC2 tardó más

tiempo en llevar la operación a cabo.

9.3. El problema RSA

El caso del problema RSA resulta de especial interés para el análisis práctico que se

está realizando. El sistema de cifrado asimétrico de clave pública RSA está muy relacinado,


110

como se ha explicado, con el problema de la factorización, si bien es un caso particular ya

que el número entero a factorizar ahora es un número primo. Este detalle lógicamente

complica aún más la tarea de factorizar. Así, el RSA deposita su fuerza sobre el problema de

la factorización siempre y cuando no se conozca la clave privada. La forma en que ha sido

tratado el algoritmo RSA en el proyecto consiste en generar dos números primos al azar que

se multiplican dando lugar a n, generar un mensaje al azar, entre otros parámetros

necesarios para continuar, codificar ese mensaje y descifrarlo factorizarizando n sin hacer

uso de la clave privada. Nuevamente, si la longitud de n es suficientemente grande, el

problema será computacionalmente imposible de resolver.

Esta vez se han realizado 24 ejecuciones para poner en práctica el proceso. En este

caso, los datos manejados por el PC1 y PC2 son similares pero no idénticos, ya que aunque

p y q sean los mismos, el mensaje M es generado aleatoriamente por Mathematica, por lo

que no se puede controlar que M sea igual para cada ordenador en cada ejecución.

Salvando este detalle, la comparación entre ambas gráficas sigue siendo de interés.

Se muestran a continuación las gráficas correspondientes

650 700 750 800 850 900

0.25

0.5

0.75

1

1.25

1.5

1.75

Figura 3

AlgoritmoRSA; PC1


111

650 700 750 800 850 900

0.5

1

1.5

2

Figura 4

AlgoritmoRSA; PC2

Nuevamente, a medida que aumenta el tamaño de los números primos p y q

utilizados, los tiempos de ejecución aumentan. El eje de abscisas muestra tan sólo uno de

los dos valores (el de q concretamente), aunque el método de generación de números

primos que se ha utilizado garantiza que la longitud de ambos es similar.

Las gráficas muestran que se presentan casos en los que el tiempo de ejecución cae

sin motivo aparente, cuando parece que lo lógico hubiera sido que aumentara con respecto

a los valores anteriores. Nuevamente, como ocurría en el caso de la factorización de

números enteros, esto se debe a que los números primos de entrada no cumplen con

criterios básicos a la hora de escoger valores de p y q que garanticen que los parámetros del

RSA sean robustos a la hora de intentar descrifrarlo. Entre varios de los criterios que se

proponen, destaca en importancia que el valor de p y q sea parecido. Así, se muestra a

continuación el aspecto de la gráfica cumpliendo esta condición, estableciendo que p = qÅÅÅÅ2 .


112

500 1000 1500 2000 2500 3000

10

20

30

40

Figura 5

AlgoritmoRSAmejorado; PC1

Se comprueba cómo, efectivamente, la circunstancia de que p y q sean números

muy distintos (aunque siempre es muy recomendable que tengan el mismo número de bits)

contribuye a que los tiempos de ejecución caigan en muchas menos ocasiones y, por regla

general, se observe mejor el carácter exponencial del tiempo de ejecución.

De nuevo, el PC1 ha sido más rápido en ejecutar los algoritmos propuestos que el

PC2, aunque no mucho más.

Actualmente se considera segura una clave RSA con una longitud de n de al menos

768 bits, si bien se recomienda el uso de claves no inferiores a 1024 bits. Hasta hace

relativamente poco se recomendaban 512 bits, pero en mayo de 1999, Adi Shamir presentó

el denominado dispositivo Twinkle, un ingenio capaz de factorizar números de manera muy

rápida, aprovechando los últimos avances en la optimización de algoritmos específicos para

esta tarea. Este dispositivo, aún no construido, podría ser incorporado en ordenadores de


113

bajo coste y pondría en serio peligro los mensajes cifrados con claves de 512 bits o menos.

Teniendo en cuenta los avances de la tecnología, y suponiendo que el algoritmo

RSA no sea roto analíticamente, se deberá escoger la longitud de la clave en función del

tiempo que se desee que la información permanezca en secreto. Efectivamente, una clave

de 1024 bits parece a todas luces demasiado corta como para proteger información por más

de unos pocos años, aunque, como ha quedado claro, todavía no se ha encontrado un

algoritmo de factorización que trabaje en tiempo polinomial.

9.4. El problema de la suma de un subconjunto

Para cerrar el estudio de tiempos de ejecución, se ha creido conveniente tratar en la

práctica con el problema de la suma de un subconjunto. Como se ha afirmado

anteriormente, representa uno de los problemas NP-completo más importantes que se

conocen. Además, los problemas NP-completos representan los problemas más

complicados de resolver computacionalmente.

El problema del subconjunto es también un ejemplo de un problema de la decisión.

Quiere esto decir que la respuesta será un sí o un no, en referencia a si los valores de

entrada cumplen los criterios anteriormente explicados. Por ello, en este tipo de problemas

no surgen picos ni escalones en los tiempos de ejecución. Está demostrado que en todo

caso, conforme aumenta el número de elementos del subconjunto de entrada, el tiempo de

ejecución aumenta de manera exponencial.

Para esta prueba se han introducido subconjuntos de 10 hasta 19 elementos. Los

resultados obtenidos son los siguientes.


114

14 16 18 20

50

100

150

200

Figura 6

Algoritmo de la suma de un subconjunto; PC1

14 16 18 20

25

50

75

100

125

150

175

Figura 7

Algoritmo de la suma de un subconjunto; PC2

En este caso, no hay diferencias significativas entre ambos ordenadores. Sin

embargo, no podemos afirmar que ante subconjuntos más grandes se mantenga la misma

relación entre gráficas, ya que Mathematica no es capaz de manejar subconjuntos mayores.


115

10. Conclusiones y líneas futuras

A lo largo de la realización de este proyecto se ha tratado con numerosos

algoritmos y métodos matemáticos, los cuales se ha demostrado que forman la base

principal de los criptosistemas de utilizados en la actualidad. Las conclusiones que se

obtienen del presenta proyecto son las siguientes:

1ª. Se puede inferir que la Criptografía moderna debe su integridad y eficacia a las

matemáticas. La aritmética modular, las funciones de una sola dirección y los números

primos son sólo algunos ejemplos de los muchos campos matemáticos en los que se

apoyan los algoritmos de codificación y descodificación.

2ª. Los números primos tienen una vital importancia en el desarrolo y ejecución de

los algoritmos en la Criptografía. Para explotar la dificultad de cálculo de logaritmos

discretos, muchos de los algoritmos criptográficos de clave pública se basan en

operaciones de exponenciación en grupos finitos. Dichos conjuntos deben cumplir la

propiedad de que su módulo n sea un número muy grande con pocos factores

—usualmente dos—. Estos algoritmos funcionan si se conoce n y sus factores se

mantienen en secreto. Habitualmente para obtener n se calculan primero dos números

primos muy grandes, que posteriormen se multiplican.

Se necesitan, pues, mecanismos para poder calcular esos números primos grandes.

Normalmente, y para que la solución sea única, se impone la condición de que los factores

de n que se obtengan sean todos primos elevados a alguna potencia. Al igual que para el


116

problema de los logaritmos discretos, no existen algoritmos eficientes para efectuar este

tipo de cálculos. Esto permite confiar en que, en la práctica, será imposible calcular los

factores de n , incluso disponiendo de elevados recursos computacionales.

3ª. En cuanto al cálculo de primos grandes, bastaría con aplicar un algoritmo de

factorización para saber si un número es primo o no. Este mecanismo es inviable puesto

que, como se acaba de decir, no hay algoritmos eficientes de factorización. Por suerte, sí

que existen algoritmos probabilísticos que permiten decir con un grado de certeza bastante

elevado si un número cualquiera es primo o compuesto.

Cabría plantearse que, dado que para los algoritmos asimétricos de cifrado se

necesitan generar muchos números primos, si realmente hay suficientes. De hecho se

puede pensar que, a fuerza de generar números, llegará un momento en el que se repita un

primo generado con anterioridad. Sin embargo, esta situación no se dará nunca, porque si

a cada átomo del universo le asignáramos mil millones de números primos cada

microsegundo desde su origen hasta hoy, harían falta un total de 10109 números primos

diferentes, mientras que el total estimado de números primos de 512 bits o menos es

aproximadamente de 10151.

4ª. La Criptografía ha ido adaptándose a nuestros días, orientándose

fundamentalmente a las aplicaciones informáticas. Los algoritmos desarrollados en este

proyecto, como toda la ciencia de la Criptografía tiene aplicaciones prácticas en diversoas

áreas:

a) La protección de las comunicaciones digitales: Internet, TV digital,


117

comunicaciones móviles, redes de datos y de voz.

b) La transferencia de documentos EDI (Electronic Data Interchange) y el

comercio electrónico EC (Electronic Commerce). Transferencia de dinero por banca,

denominada EFT (Electronic Funds Transfer).

c) Garantizar la seguridad y protección del software.

d) La mensajería militar en la red de mando y control.

e) En la aplicación del DNI digital, con la firma digital, así como en la firma

digital de documentos.

5ª. La Criptografía moderna está fuertemente sustentada en la informática aplicada, y

por tanto se ve directamente afectada por los tiempos de ejecución. Para estudiarlos y

explicarlos se recurre a las clases de complejidad, que clasifica los tipos de problemas en

función de su tiempo de ejecución. Así, todos los algoritmos tratados en el proyecto son

NP, es decir, su tiempo de ejecución es exponencial, si bien si se conoce un dato clave,

llamado certificado y en nuestro caso los datos iniciales de las funciones trampa, el

tiempo de ejecución se convierte en polinomial. Un caso particular de los problemas NP

son los NP-completos, como es el problema de la suma del subconjunto tratado en el

proyecto. Aparte de tener todos un tiempo de ejecución exponencial, se ha demostrado

que si se consigue resolver uno de ellos, entonces de manera directa se podrían resolver el

resto.

6ª. El hecho de que no se conozca un algoritmo eficiente para resolver un problema

no quiere decir que éste no exista, y por eso es tan importante la Teoría de Algoritmos


118

para la Criptografía. Si, por ejemplo, se lograra descubrir un método eficiente capaz de

resolver logaritmos discretos, algunos de los algoritmos asimétricos más populares en la

actualidad dejarían de ser seguros. De hecho, la continua reducción del tiempo de

ejecución necesario para resolver ciertos problemas, propiciada por la aparición de

algoritmos más eficientes, junto con el avance de las prestaciones del hardware

disponible, obliga con relativa frecuencia a actualizar las previsiones sobre la seguridad

de muchos sistemas criptográficos. De hecho, expertos en la materia de seguridad

informática y Criptografía, aseguran que con la futura aparición de los ordenadores

cuánticos los recursos computacionales crecerán de manera gigantesca, obligando una vez

más a la Criptografía a adaptarse y transformarse en lo que ya empieza a conocerse como

Criptografía Cuántica.

Actualmente, lo modelos cuánticos de computación hoy por hoy no pasan de

meras promesas, ya que la tecnología actual no permite confinar partículas individuales de

forma que preserven su estado cuántico. Los más optimistas aseguran que en pocos años

se tendrán los primeros microprocesadores cuánticos en funcionamiento, mientras que la

gran mayoría opina que todavía transcurrirán décadas antes de poder disponer del primer

dispositivo realmente operativo.

Se puede afirmar con rotundidad es que los modelos criptográficos actuales

seguirán siendo válidos durante algunos años más. En cualquier caso, no conviene perder

de vista estas promesas tecnológicas, ya que cuando se conviertan en realidades, obligarán

a replantear muchas cuestiones, y no sólo en el ámbito de la Criptografía.

7ª. Como líneas futuras de análisis e investigación y como mejora posible a


119

introducir al actual Proyecto cabría reseñar:

a) Diseño de algoritmos capaces de calcular las raíces cuadradas módulo

compuesto de un número que sea factor de tres o más factores.

b) Introducción y desarrollo de los algoritimos del problema del logaritmo

discreto, la factorización de números y el problema de RSA mediante las técnicas de la

Criptografía de Curvas Elípticas (CCE), como variante de la Criptografía asimétrica o de

clave pública basada en las matemáticas de las curvas elípticas. Esta metodología puede

ser más rápida y usar claves más cortas que los métodos conocidos, como RSA.

c) Realización de todos estos algoritmos en un lenguaje de programación

estructurado de propósito general, como por ejemplo C, implementando todas las librerías

requeridas para realizar el tratamiento de grandes números, con el fin de estudiar

fehacientemente la optimización de estos algoritmos, con las claves actuales, así como

con futuras claves de mayor magnitud.

11. Desarrollo de la aplicación

11.1 Ciclo de vida

El tipo de paradigma de ciclo de vida que se ha seguido para el desarrollo del

proyecto ha sido el modelo incremental o evolutivo. Así, el desarrollo inicial se comenzó

satisfaciendo un conjunto de requisitos, que se enunciarán más adelante, y las siguientes

versiones proveen de requisitos identificados posteriormente, evolucinando el sistema fase

a fase. Es el tipo de metodología más lógico para aplicar a este proyecto, pues la parte de


120

programación consiste en el diseño de subrutinas que en la mayoría de los casos no

dependen una de otra. De esta forma es posible avanzar más en el desarrollo de unos

métodos que en otros sin ralentizar de manera global el avance del proyecto.

El desarrollo y codificación de los algoritmos se ha ido realizando por bloques. El

orden que se ha seguido para la elaboración de los mismos ha sido: el problema del residuo

cuadrático, raíz cuadrada módulo n, el problema del logaritmo discreto,, el problema de la

factorización de números enteros, el problema RSA, el problema de Diffie-Hellman y,

finalmente, el de la suma de un subconjunto. Como ya se ha mencionado anteriormente, el

orden podría haber sido otro y éste es el que se ha considerado mejor. Mencionar, sin

embargo, que ciertos algoritmos propios de la Aritmética Modular han sido necesarios para

el diseño de algunos algoritmos y, lógicamente, fue necesario su desarrollo anterior. Este es

el caso del Teorema Chino del Resto, la función del Inverso Modular, la función Jacobi y

una subrutina que, a partir de una matriz n × n, devuelve las filas linelamente dependientes.

Para poner en práctica el ciclo de vida incremental se ha optado por recurrir a una

metodología de paquetes. Consiste en definir de antemano una serie de paquetes de trabajo

en cuyo contenido se clasifican los pasos necesarios para poder ir evolucionando a lo largo

del proyecto. Se muestra a continuación un esquema de dichos paquetes de trabajo con su

jerarquía establecida.


121

Figura 8

Paquetes de trabajo.

WP.00 - Gestión

Definición: Lo que se imputará al paquete de gestión no va a realizarse en un

periodo de tiempo continuo y determinado, sino que va a consistir en una serie de reuniones

y entrevistas repartidas a lo largo de todo el proyecto. Estas reuniones tienen por objeto

vigilar la correcta realización del proyecto tanto en contenidos como en correspondencia

con el tiempo estipulado del mismo. Así mismo, se incluye en este paquete todo el trabajo

que tenga que ver con el seguimiento del correcto funcionamiento del proyecto, como por

ejemplo las fases de pruebas finales.

Entradas: Entregables del proyecto en distintas fases de realización así como

distintas revisiones de la planificación temporal y económica.

Salidas: Las entradas revisadas y modificadas si se creyera necesario.


122

WP.01.1 - Búsqueda de documentación

Definición: Antes de entrar en la fase que se llevará el grueso del proyecto será

necesario prepararla convenientemente. Para este fin se han establecido las dos fases del

paquete WP.01. En nuestro paquete concretamente el equipo se ocupará de buscar toda

información que sea de ayuda para llevar a cabo el proyecto, tanto datos puros que ayudarán

directamente, como todo tipo de información anexa que permitirá adquirir un alto grado de

comprensión de la tarea que se va a llevar a cabo.

Esta búsqueda se realizará tanto en bibliotecas, como publicaciones especializadas,

y dado el carácter didáctico o de investigación del proyecto, se hará especial hincapié en

nuevas fuentes de información, como Internet, ya que se las considera, un buen banco de

nuevas investigaciones.

Entradas: No posee entradas propiamente dicho, ya que no se realizará la

conversión de ningún tipo de información sino que el objeto de esta base es buscar

justamente esa información.

Salidas: Como salida se obtendrá una buena colección de documentación

debidamente catalogada y seleccionada por orden de interés y calidad de contenidos.


123

WP.01.2 - Organización de pseudocódigos

Definición: Del paquete anterior se ha obtenido gran cantidad de documentación y

junto a ella los pseudocódigos de los métodos que se implantarán a lo largo del proyecto.

En esta fase se seleccionarán aquellos pseudocódigos más elegantes que se hayan

encontrado o aquéllos que por su estructura sean interesantes desde un punto de vista

original o educativo. En el caso de no disponer de pseudocódigos completos, se diseñarán

por cuenta propia los pasos necesarios para poder alcanzar el resultado fina.

Entradas: Documentación seleccionada en el paquete WP.01.1

Salidas: Grupo de pseudocódigos a implantar.

WP.02 - Codificación de algoritmos

Definición: A partir de este punto se encuentra el grueso del proyecto. Aquí se

pasarán todos los pseudocódigos al lenguaje Mathematica. Estos códigos son la base y

punto central de todo el proyecto, ya que serán los que permitirán explicar el

funcionamiento y la realización de los problemas de los que se hablará a continuación.

Entradas: Pseudocódigos seleccionados.

Salidas: Algoritmos codificados y funcionando.


124

WP.03.1 - Generación de problemas

Definición: Se trata de otro punto fundamental del proyecto que permitirá hacer una

idea de las principales aplicaciones de cada uno de los algoritmos propuestos. En algunos

casos estos problemas se repetirán para varios algoritmos, para que se pueda examinar

cuáles son las similitudes y diferencias entre ellos. En algunas situaciones esto no será

posible dada la distinta naturaleza de cada algoritmo, ya que algunos requieren

características de los datos entrantes que no son compatibles con los otros algoritmos.

Entradas: Los códigos funcionando y una batería de enunciados de problemas

Salidas: Problemas resueltos en los distintos algoritmos.

WP.04 - Creación de interfaz de usuario

Definición: Se considera a la interfaz de usuario uno de los puntos fuertes de este

proyecto, ya que permite a los que no están versados en el lenguaje Mathematica poder

ejecutar los algoritmos con sus propios ejemplos (o los ejercicios previamente codificados a

modo de demostración). De esta forma se intenta que el proyecto y el trabajo realizado no

quede oculto sino que en el futuro sea de utilidad.

Entradas: La propia estructura del proyecto, ya que servirá de base para hacer el

estudio de cómo enfocar la interfaz a los usuarios.

Salidas: Interfaz gráfica para el usuario en funcionamiento.


125

WP.05 - Conclusiones

Definición: En esta fase se redactarán las conclusiones del proyecto, se intentará

que no tengan un nivel muy avanzado y que sean de fácil comprensión con un lenguaje

adaptado a personas que no necesariamente tengan que estar muy preparadas en el campo

de la Criptografía y Teoría de Números. El contenido de estas conclusiones es la

comparación entre los distintos algoritmos así como cualquier anotación que se haya

realizado durante la realización del proyecto que se pueda considerar de interés.

Entradas: Toda la información generada a lo largo del proyecto

Salidas: El apartado de conclusiónes del proyecto


126

11.2. Identificación de necesidades

El objetivo principal de la aplicación desarrollada es la proporcionar una

herramienta que permita al usuario utilizar los algotirmos desarrollados de una manera

rápida y cómoda, como consecuencia de tratarse de una aplicación informática basada en

sistema de ventanas.

En lo referente al alcance del proyecto, la aplicación se limitará a dar un resultado

en función de los datos de entrada. Así, para los métodos de factorización, logaritmo

discreto y los algoritmos raíz cuadrada módulo n, la aplicación proporcionará el resultado

pertinente siempre y cuando los datos de entrada sean correctos. Lo mismo sucede con el

algoritmo RSA y Polling-Hellman, proporcinando además el sistema un resumen de los

principales datos a conocer en el proceso de intercambio y generación de claves. En el caso

de la suma de un subconjunto, la aplicación tan sólo mostrará en pantalla si existe o no un

subconjunto de A que sume s. En ningún caso la aplicación proporcionará alternativas en el

punto de que los datos de entrada propuestos no sean válidos. Además, como se ha

mencionado a lo largo del proyecto, si los datos de entrada son demasiado grandes como

para poder tratarse computacionalmente en la máquina donde se esté ejecutando la

aplicación, el resultado será que el sistema no será capaz de proporcionar una respuesta.

La tipología de usuario final abarca prácticamente todas las posibles. La estructura

sencilla seguida a la hora de desarrollar los algoritmos e incorporarlos a una interfaz de

usuario muy intuitiva, hace que no existan barreras de tipo técnico por las que usuarios no

introducidos en la materia se puedan mostrar reacios a utilizar la herramienta. Además,

muchos de los algoritmos planteados resultan muy interesantes a la hora de obtener un


127

resultado de manera rápida y fiable, como puede ser el caso de conocer la factorización de

un número entero o conocer el resto cuadrático de cierta sentencia. Por ello se espera que el

rango de usuarios finales sea amplio, desde estudiantes y profesores hasta interesados en la

materia.

Respecto a las restricciones que pueden afectar al plan de proyecto, pocas son las

que realmente pueden suponer un problema. En primer se sitúa el periodo de tiempo en el

que debe desarrollarse. Según el diagrama de Gantt mostrado más adelante, el plazo de

ejecución ha sido de nueve meses aproximadamente, si bien esta restricción es académica.

No ha sido necesario ningún elemento de hardware adicional aparte del PC con el que se

trabaja, con lo que no ha exitido restricción alguna en relación a los recursos disponibles.

Tampoco han habido restricciones geográficas.

11.3. Análisis de requisitos

Todos los requisitos identificados para esta aplicación son de carácter funcional,

puesto que atienden a características propias de las funciones de Criptografía.

RF001. Representación de un número entero positivo descompuesto en la

multiplicación de dos factores, según el algoritmo de factorización rho de Pollard.

Dado un número entero positivo n descomponerlo en p µ q.


multiplicación de dos factores, según el algoritmo de factorización ( p -1 ) de Pollard.

Dado un número entero positivo n y un límite entero positivo B, encontrar la


128

descomposición de n en dos factores, siendo al menos uno de ellos un primo p para el cual

p - 1 es uniforme con respecto al límite B.


multiplicación de dos factores, según el algoritmo de factorización de la criba

cuadrática.

Dado un número entero positivo n descomponerlo en p µ q .

RF004. Establecer atributos propios válidos del sistema de cifrado asimétrico en clave

pública RSA, a partir de los parámetros iniciales p y q.

Proponer todos los datos necesarios para cifrar y descifrar un mensaje M.

RF005. Dados dos números enteros, estudiar si uno es residuo cuadrático respecto del

otro.

Se obtiene una respuesta positiva o negativa al respecto.

RF006. Calcular la raíz cuadrada módulo n, con n primo para los valores enteros

dados.

Se calcula la raíz cuadrada de un valor entero módulo n si existe (dicho valor

entero tiene que ser resto cuadrático módulo n).

RF007. Calcular la raíz cuadrada módulo n, con n compuesto para los valores enteros

dados.

Se calcula la raíz cuadrada de un valor entero módulo n, en el caso de que n sea un


129

número compuesto de la forma pµ q , con p y q factores primos de n.

RF008. Calcular el problema del logaritmo discreto, según el algoritmo baby-step

giant-step.

Se calcula el valor para el cual tiene solución la ecuación del logaritmo módulo n

planteada, según un subgrupo cíclico �p* concreto de orden n = p - 1 con generador g,

para un b entero positivo dado.

RF009. Calcular el problema del logaritmo discreto, según el algoritmo

Pohlig-Hellman.




RF010. Calcular el problema del logaritmo discreto, según el algoritmo rho de Pollard

para logaritmos.




RF011. Establecer los parámetros necesarios para establecer una comunicación

segura a través de un canal público mediante el protocolo asimétrico Diffie-Hellman.

Se muestran, paso por paso, las operaciones necesarias para establecer el canal de

comunicación seguro, a partir de un número primo p y un generador g e �p* .


130

RF012. Comprobar si, dado un conjunto ai de números enteros y un número entero s,

existe un subconjunto de ai que sus elementos sumen s.

Se calcula si dicha condición se cumple y se informa del resultado por pantalla.

11.4. Arquitectura técnica

La arquitectura necesaria para esta aplicación no es otra que un PC, sin requerir

características específicas adicinales. Deberá tener instalado el software necesario para la

ejecución de la aplicación (Mathematica® V.5.2) y el paquete gráfico The Super Widget

Package (SWP) para la creación de la interfaz de usuario (GUI).


131

11.5. Diseño de la interfaz de usuario

Como se ha mencionado en la introducción del ciclo de vida, la interfaz de usuario

se desarrolla de forma evolutiva, al igual que todo el desarrollo de este proyecto. Esta

manera de trabajar presenta como ventajas poder obtener resultados parciales a medida que

se completan los algoritmos y, en caso de tener que realizar modificaciones, éstas son más

fáciles de localizar y resolver.

La prioridad que se ha establecido a la hora de desarrollar la interfaz de usuario es

que sobre todo sea sencilla e intuitiva. Como antes se ha indicado, está sobre todo pensado

para el ámbito docente y por tanto el grado de conocimiento del usuario no tiene

necesariamente que ser avanzado.

Una vez arrancado el programa, y desde la ventana inicial del programa, tan sólo

hay que seleccionar uno de los algoritmos e introducir los parámetros de entrada que pide

explícitamente la interfaz. Para una mayor comprensión del usuario, la interfaz debe

mostrar gráficamente qué es cada uno de los parámetros, para que no exista confusión.

A continuación se presentan unos ejemplos del funcionamiento de la interfaz de

usuario.


132

Figura 9

Menú principal

Figura 10

Cálculo de la factorización de un número entero


133

Figura 11

Cálculo del logaritmo discreto

Figura 12

El problemaRSA


134

Figura 13

El problema de la suma de un subconjunto

Figura 14

Problema de la raíz cuadradamódulo primo


135

12. Valoración económica y planificación

12.1. Introducción

En este apartado se detalla la valoración económica o análisis de costes de cada

una de las tareas/actividades que comprenden la realización y puesta en funcionamiento

del presente proyecto.

El proyecto se ha descompuesto en actividades y tareas, indicadas como partidas o

ítems en la valoración económica.

12.2. Técnicas de estimación de costes

Las diferentes partidas o ítems que componen el proyecto y que se han incluido en

este análisis de costes se detallan a continuación.

1. Especificaciones y Desarrollo Software

Esta partida o ítem se ha dividido en dos grandes fases debido a su gran alcance e

importancia.

En primer lugar, aparece la fase de requisitos. Esta fase incluye las fases de

especificación de requisitos, del análisis funcional y del plan de pruebas.

En segundo y último lugar, se indica la fase de desarrollo del software. Esta fase

es sin duda la que ha supuesto más coste, en términos de tiempo, y la que distingue

nuestro presupuesto del de otro proyecto que comprenda el mismo ámbito o sea del

mismo tipo. En esta fase se ha diferenciado del ajuste de curvas lineal y del no lineal.


136

Para cada una de las fases anteriores se reseñan los costes directos, expresados en

meses/hombre (meses completos dedicados para cada actividad), necesarios para

acometer cada una de ellas, indicándose la categoría del realizador: Jefe de Proyecto o

Analista/Programador. La actividad del Jefe de Proyecto se ha estimado en un 17,5%

respecto de la actividad del Analista/Programador.

Por último, cabe destacar que no debe haber confusión con el significado de los

costes unitarios aquí expresados. Estos costes representan la valoración económica que

haría la empresa por poner a cargo de este proyecto a dicho Jefe de Proyecto o Analista en

su caso.

2. Instalación, Pruebas e Integración del Software

En este apartado se recogen los costes directos de las actividades de integración y

de pruebas del software en el entorno de desarrollo y en el de explotación, incluidos los

gastos adicionales, tales como los desplazamientos y las dietas. Estos costes han sido

calculados del mismo modo que en el apartado anterior.

3. Equipamiento y Licencias Software

Costes de todo el equipamiento e infraestructura (PCs, impresoras, RAL,

comunicaciones), si fuera necesario. Así mismo, se han de especificar en este apartado las

licencias necesarias para el entorno de explotación.

Para la implementación de este software sólo es necesario de una licencia del

lenguaje numérico y simbólico de Mathematica®, en concreto de la versión 5.2 aquí

utilizada, y disponer de un PC. Cómo la venta de este software será con toda seguridad a


137

una persona jurídica no se contempla en este presupuesto la adquisición de dicha

plataforma hardware, debido a que en los tiempos presentes cualquier empresa o persona

jurídica dispone de un PC, haciéndose sólo referencia a la licencia del Mathematica®.

4. Apoyo logístico (Formación)

En este concepto se ampara la formación a impartir a los posibles operadores y

administradores del sistema a implantar. Se incluye en la formación la entrega de toda la

documentación necesaria para el curso de formación.

5. Incrementos e IVA

Se parte de la suma de las partidas (1), (2), (3), y (4) formando el Coste Directo

del proyecto. A este Coste Directo se le aplican los Gastos Generales H13%L y el

Beneficio Industrial H6%L. La suma de los conceptos de Coste Directo, Gastos Generales

y Beneficio Industrial constituyen el Total Importe sin IVA.

A este importe se le sumarán los impuestos correspondientes como IVA H16%L,

para la Península y Baleares, IGIC H5%L para las islas Canarias o IPSI H0%L para Ceuta y

Melilla.

Total proyecto

La suma del Total Importe sin IVA más la partida de Incrementos e IVA

determinan el importe total del desarrollo, implantación y puesta en servicio del proyecto.


138

12.3. Planificación temporal del proyecto

En el diagrama de Gantt de actividades siguiente se reflejan las tareas e hitos más

importantes para el desarrollo y ejecución de este proyecto Fin de Carrera, así como la

planificación temporal final dedicada a cada uno de ellos.

12.4. Costes del proyecto

En función de lo explicado en el apartado de técnicas de estimación de costes y de

la planificación vista en el apartado anterior podemos proceder a calcular los costes

estimados del presente proyecto.

El importe total del proyecto asciende a 20.981, 92 € (VEINTE MIL

NOVECIENTOS OCHENTA Y UN EUROS CON NOVENTA Y DOS CÉNTIMOS),

impuestos incluidos.

El detalle de cada una de las partidas vistas en el apartado anterior, se expresa en

la tabla siguente:


139


140


141

Bibliografía

[FUST00] Fúster Sabater, Amparo; de la Guía Martínez, Dolores y otros.

Técnicas Criptográfica de protección de datos. 2ª edición.

Ed. Ra-Ma. Madrid, 2000.

[LUCE0.7.3] Lucena López, Manuel J..

Criptografía y Seguridad en Computadores.

4ª Edición. Versión 0.7.3

[MONT02] Juan Montejo Machicado. Proyecto Fin de Carrera:

Autenticación mediante el Algoritmo MD5 para el Intercambio

de Información.

Dirigido por el Dr. Fco. Javier Rodríguez Gómez.

Universidad Pontificia Comillas. Madrid, 2002

[MART05] Javier Martín Herrera. Proyecto Fin de Carrera.

Firmas Digitales.


Universidad Pontificia Comillas. Madrid, 2005.

[MATE05] Andrés Mateos Salmador. Proyecto Fin de Carrera:

Algoritmos para la Criptografía de Clave Pública.



[MENE96] A. Menezes, P. Van Oorschot, and S. Vanstone,

Handbook of Applied Cryptography, CRC Press, 1996. Cap. 3.

http://www.cacr.math.uwaterloo.ca/hac/


142

[PAST01] Pastor Franco, José; Sarasa López, Miguel Ángel;

Salazar Riaño, José Luis;

Criptografía Digital, Fundamentos y Aplicaciones. 2ª edición.

Universitarias de Zaragoza, 2001.

[ROME04] Rafael Romero Luezas. Proyecto Fin de Carrera:

Criptografía Asimétrica de Clave Pública.



[RODR03] Rodríguez Gómez, Francisco Javier.

Cálculo y Métodos Numéricos. Teoría, Algoritmos y Problemas

Resueltos.


[RODR03] Rodríguez Gómez, Francisco Javier.

Seguridad en Red..

Programa de Postgrado, UNED. Madrid, 2003.

[ROGA98] Rodríguez Gómez, Fco. Javier; García Merayo, Félix.

Fundamentos y Aplicaciones con Mathematica. Paraninfo.

Madrid, 1998.

[WILL99] Stallings, Williams.

Cryptography and Network Security: Principles and Practice.

Second Edition. Prentice Hall, New Jersey, 1999.

URL’s

[1] http://www.williamstallings.com


143

[2] http://www.rsasecurity.com/

[3] http://www.kriptopolis.com/

[4] http://www.rediris.es/rediris/

[5] http://www.cacr.math.uwaterloo.ca/hac/

[6] http://webs.ono.com/usr005/jsuarez/expon2.html

[7] http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_enteros

[8] http://jair.lab.fi.uva.es/~fdelgado/cripto/log_discreto_print.pdf

[9] http://www.sindominio.net/hmbcn00/material/hmRSA-es.htm

[10] http://www.htmlweb.net/seguridad/cripto/cripto_2.html

[11] http://gaussianos.com/criptografia-cifrado-de-clave-publica-i/


144

problemas computacionales en criptografía · pdf fileproyecto fin de carrera problemas...

Documents