PDF de programación - El Sistema RSA

El Sistema RSA

José de Jesús Ángel Ángel
[email protected]

El Sistema RSA

El Sistema RSA

José de Jesús Ángel Ángel

@seguridata.com.mx

1 Introducción

Desde su aparición en 1978 ([54]) el sistema de llave pública RSA (de Rivest,Shamir y
Adleman) ha ganado gran popularidad, por una parte por la gran seguridad que ofrece al
basar ésta en un problema matemático difícil de resolver que había dejado de tener interés
en la comunidad mundial, cómo lo es el Problema de la Factorización Entera PFE y a causa
del sistema RSA se ha retomado e incrementado su investigación. Por otra parte, aunque
implementar RSA requiere de mucho cuidado en detalles que son necesarios, la idea de su
funcionamiento es muy simple de entender, lo que lo hace muy popular principalmente en
sectores donde no hay abundancia de matemáticas.
Este artículo está dedicado a resumir los últimos resultados paso a paso sobre la
implementación del sistema RSA, principalmente en lo que se refiere a su seguridad y más
concretamente en los puntos de mayor debilidad del sistema, éstos están resumidos en lo
que llamamos resultados, que se reescriben en la última parte del artículo.
Respecto a la implementación de las técnicas de realizar aritmética con números de múltiple
precisión o longitud "grande", se requiere de mayor espacio, aunque se dan las referencias
necesarias para abordar con seriedad el tema.

El algoritmo RSA es usado esencialmente en:
a) Generación de llaves RSA
b) Cifrado del texo original
c) Descifrado del texto cifrado

Algoritmo RSA de llave pública

l.a) Generar dos primos p,q

2.a) Calcular

3.a) Elegir un entero

4.a) Calcular

5.a) La llave pública es

y la llave privada (

)

6.b) El usuario A calcula
7.b) A envía el mensaje cifrado c al destinatario B

con la llave pública

8.c) B recobra el mensaje con la fórmula

con la llave privada

Otra importante aplicación es la "Firma Digital" que consiste en lo siguiente:

José de Jesús Ángle Ángel

1

El Sistema RSA

Algoritmo de Firma Digital

A) Si el usuario B quiere firmar el mensaje

, se procede a calcular

es la llave privada de B

donde
B) Para verificar la firma de B al mensaje

, se procede como sigue: s es la firma de

B

Enseguida revisaremos temas relacionados con cada uno de los anteriores puntos y justifica-
remos de forma simple algunos de ellos, o en caso de que sea de mayor tratamiento, damos
las referencias.

2 El tamaño de la llave pública n

Si podemos factorizar al número , entonces podemos conocer a

, y por lo tanto calcular

a a partir de , es decir, romperemos el sistema.

El problema de calcular a

y factorizar a son computacionalmente equivalentes, la elec-

y debe ser de tal forma que la factorización de

ción de
computacionalmente "imposible". A continuación procedemos a encontrar el tamaño de los
números primos

sea

, , para lograr el objetivo.

entonces esta en el extremo de ser fácilmente factorizable, es decir, esta en

Si
la forma más simple de poder ser factorizable ya que tiene muchos factores y estos son
del menor tamaño posible. Entonces si tiene un mínimo de factores y tales factores son
grandes, posiblemente estará en el otro extremo, el de ser "imposible" su factorización.
y son números primos y de considerable tamaño, enton-
Es decir si
ces la factorización de debe ser difícil.
A continuación veremos que los números producto de dos primos son de los más difíciles de
factorizar.

donde

2.1 Criterios de factorización

Una forma de clasificar a los métodos de factorización es en dos grupos: 1. Los métodos de
"propósito especial", quienes buscan propiedades especiales a los factores de y 2. Los
métodos de "propósito general" que dependen sólo del tamaño de .
Entre los métodos de "propósito especial" están:

- El método del ensaño de divisores pequeños (conocido por la criba de Eratosthenes)

José de Jesús Ángle Ángel

2

El Sistema RSA

- El algoritmo
- El método que usa curvas elípticas (MCE) ([36])
- Criba de campos numéricos especial (CCNE) ([33], [34])

de Pollard ([46])

Entre los métodos de "propósito general" están

- Criba cuadrática ([21], [33], [49])
- Criba de campos numéricos general (CCNG) ([33])

En general no existe una forma eficiente de factorizar a un número entero si no se conoce
nada acerca de él, ya que algunos métodos son más eficientes en algunos casos que en
otros, sin embargo podemos dar una estrategia para poder intentar factorizar un número
entero :

- Aplicar el método de ensañar divisores pequeños, hasta una cota

- Aplicar el algoritmo de Pollard, esperando encontrar un factor , tal que

don-

de es otra cota

- Aplicar el método con curvas elípticas, esperando encontrar un factor tal que

- Aplicar un método de propósito general

Con lo que esperamos optimizar el proceso de factorizar, aplicando el mejor método confor-
me a la forma del número.

Si ya se conoce una estrategia para factorizar al número entero, el parámetro más importan-
te es el tiempo que tomará para lograr el objetivo. Enseguida procedemos a explicar una
forma simple de medir el tiempo.

José de Jesús Ángle Ángel

3

El Sistema RSA

2.2 Cómo medir el tiempo en factorizar números enteros

La práctica ha permitido llegar a medir algunos algoritmos con la siguiente cota:

donde podemos suponer que la función como cota superior a considerar es:

donde es una constante, el tamaño del número,

un número tal que

y deter-

mina la "lentitud" del algoritmo en el sentido de que si

, entonces

se convierte a

comportamientos los podemos apreciar en las siguientes gráficas.

, y si

, entonces

, cuyos

Esta gráfica es de la función:

José de Jesús Ángle Ángel

4

El Sistema RSA

Esta gráfica es de la función:

José de Jesús Ángle Ángel

5

El Sistema RSA

Si tenemos un algoritmo que corre a un tiempo de

diremos que corre en tiempo

polinomial, si el algoritmo tiene una complejidad de

, entonces diremos que corre

a un tiempo exponencial, y si
subexponencial.

, diremos que el algoritmo corre a un tiempo

Ejemplos del tiempo que corren algunos algoritmos conocidos son:

Algoritmo: Criba de campos numéricos general

Tiempo:

Algoritmo: Criba de campos numéricos especial

Tiempo:

Algoritmo: Criba cuadrática

Tiempo:

Algoritmo : Método de fracciones continuas

Tiempo:

, donde

Algoritmo : Método de Factorización con Curvas Elípticas

Tiempo:

, para encontrar el factor

y si

, el tiempo es

2.2.1 Tiempo de factorización en la práctica

Hoy en día, parece ser que el problema de factorización ha progresado enormemente, este
gran impulso lo ha provocado en gran parte la criptografía y más concretamente el sistema
RSA. Enseguida nos proponemos a dar los datos que se tienen del crecimiento sobre la
factorización de números enteros y estimar cual sería el tiempo en que se tardará la humani-
dad en factorizar un número entero considerado hoy imposible de factorizar.
Aunque se muestre que un algoritmo corre a tiempo subexponencial o más aún a tiempo
polinomial, el tiempo de calendario (tiempo real en meses, días o minutos) puede variar
mucho dependiendo de la entrada del algoritmo y del equipo de cómputo con que se cuenta.
Existe una forma de medir el potencial de cómputo y de esta forma determinar cuál sería el
tiempo en calendario que llevaría factorizar un número entero "grande" y cuándo podría llevar-
se a cabo esto.

José de Jesús Ángle Ángel

6

El Sistema RSA

La notación "mips" significa millones de instrucciones por segundo ([43]) y es tomada como
medida estándar para registrar la potencia de cómputo con que se cuenta. Un mips tiene
como origen la potencia de cómputo que realizaba una DEC VAX 11/780. Un mipsy significa
el número de instrucciones que se pueden realizar en un año con un poder de cómputo de un

mips, es decir 31 536 x
Algunos datos interesantes son los mips que han sido utilizados para factorizar algunos
números enteros.

instrucciones.

oñA

4991

4891

4891

yspim

dutignoL

100.0

1.0

0005

Tabla 1

d54

d17

d921

donde nd significa un número entero de d dígitos.

La primera estimación que haremos es sobre el poder de cómputo que se puede conseguir
mipsy, de los cuales un 10%

en todo el mundo, el cual se estima que en 1994 era de 3x
estaba conectado a Internet y como se puede observar en la tabla 1 se utilizo un 0.0033%
total para factorizar un número de 129d. Se estimó poder reunir 100 veces más poder de
cómputo, es decir, usar un 0.33% del total en un trabajo de factorización.
Hagamos una estimación del poder disponible estimado en todo el mundo usando la predic-
ción conocida por "ley de Moore". Gordon Moore co-fundador de Intel, predice en 1965 que
la rapidez con que crecen los microprocesadores se duplica en 18 meses. Es decir, si en

1994 el poder de cómputo en el mundo era de 3x

mips, entonces en 3 años (1997) seria

de 1.2x

mips, lo cual no está muy lejos de la realidad.

José de Jesús Ángle Ángel

7

En la siguiente tabla mostramos la estimación de los próximos años:

oñA

6991

69-59

7991

yspim

1x3

0 8

1x6

0 8

1x2.1

0 9

99-89

1x4.2

0 9

0002

1x8.4

0 9

oñA

yspim

80-70

1x35.1

0 11

9002

1x70.3

0 11

11-01

1x41.6

0 11

2102

1x2.1

0 21

41-31

1x9.4

0 21

8202

4302

8302

20-10

1x6.9

0 9



5102

1x8.9

0 21



3402

3002

1x29.1

0 01

50-40

1x48.3

0 01

6002

1x86.7

0 01

71-61

1x2

0 21

8102

0291

1x2

0 31

1x4

0 31

9402

3502

8502

El Sistema RSA

oñA

1202

yspim

1x8

0 31

32-22

1x6.1

0 41

10 51

10 61

10 71

10 81

10 91

10 02

10 12

Para poder determinar cuándo se podría contar con el poder necesario para factorizar un
número entero de tamaño conocido debemos de saber qué poder de cómputo es necesario
utilizar para tal factorización.
Esto lo estimaremos de la siguiente manera: partimos de que sabemos cuántos mipsy son
utilizados para factorizar un número entero, por ejemplo un número de 129 ~ 42