PDF de programación - Bases matemáticas de la criptografía de clave asimétrica: la aritmética modular y la clave RSA

Bases matemáticas de la criptografía de clave asimétrica:

la aritmética modular y la clave RSA

Barco G., Carlos

Resumen

El presente artículo tiene un propósito didáctico, a saber, mostrar los fundamentos matemáticos de la
criptografía en lo que se refi ere a la aritmética modular y sus aplicaciones: por un lado, el cálculo del
dígito de verifi cación en los números de identifi cación; y por el otro, la aritmética modular aplicada a
la criptografía de clave pública RSA. Para lograr este propósito, se desarrollarán los siguientes temas:
relaciones de congruencia módulo n, aritmética modular y propiedades de las congruencias módulo n
y las aplicaciones ya mencionadas.

Palabras clave: criptografía, asimétrica, RSA, clave pública, aritmética modular.

Mathematical bases of cryptography of the asymmetric key:

modular arithmetic and the RSA key

Abstract

The didactic purpose of this paper is centered on showing the mathematical foundations of cryptography,
in regards to modular arithmetic and its applications. On one side, the calculation of the verifi cation
digit in identifi cation numbers, and on the other side, modular arithmetic applied to the public key RSA
cryptography. To achieve said purpose, the following subjects will be developed: congruence n-modular
relations, modular arithmetic and the properties of n-modular relations and the above-mentioned
applications.

Key words: cryptography, asymmetric, RSA, public clue, modular arithmetic.

* Departamento de Matemática, Universidad de Caldas. AA275 Manizales, Colombia. e-mail: [email protected]

Vector, Volumen 2, Enero - Diciembre 2007, págs 59 - 69

Recibido 12 Septiembre 2007, Aprobado 16 Noviembre 2007

Barco G., Carlos

Relaciones de congruencia módulo n.

Sea Z el conjunto de números enteros y R la relación sobre Z definida por la siguiente expresión:

R = {(x, y) ∈ X × X / x – y es múltiplo de 2}

La relación entre x y y, x R y se escribe con el símbolo:

x ≡ y (mod 2)

Que se lee “x es congruente con y módulo 2”. La relación así definida es una relación de equivalencia
sobre el conjunto de los números enteros porque:

a) Para todo x ∈ X, se cumple que x ≡ x (mod 2), ya que a – a = 0 = 2 × 0 que es múltiplo de 2 y

por tanto, la relación es reflexiva.

b) Sea x ≡ y (mod 2), entonces x – y = 2k, ∀k ∈ Z, entonces, y –x = 2(-k) y por lo tanto, y – x
también es un múltiplo de 2, es decir: y ≡ x (mod 2) y por tanto, la relación es simétrica.

c) Si x ≡ y(mod 2) y y ≡ z(mod 2), entonces:

x – y = 2k1
y – z = 2k2

Donde k1 y k2 son números enteros. Sumando miembro a miembro las dos ecuaciones anteriores se
obtiene: x – z = 2(k1 + k2), lo que significa que x ≡ z (mod 2) y por tanto, x ≡ y (mod 2) ∧ y ≡ z (mod 2),
entonces, x ≡ z (mod 2) y la relación es transitiva.

Esta relación de congruencia módulo 2 determina una partición del conjunto de los enteros Z en dos
clases de equivalencia: la clase de equivalencia con representante cero (0), la clase del Cl (0), o también
[0] constituida por los números cuya diferencia sea par (los números pares) y la clase de equivalencia
con representante uno (1), la clase del uno Cl (1), o también [1] constituida por los números impares,
simbólicamente se expresa:

Cl (0) = [0] = {x ∈ Z / (x, 0) ∈ R}
donde R: = x – 0 = 2k (pares)
Cl (1) = [1] = {x ∈ Z / (x, 1) ∈ R}
donde R: = x – 1 = 2k (impares)

El conjunto cociente de los enteros por la relación Z / R tiene dos elementos: la clase de los pares y la
clase de los impares.

La partición o conjunto cociente se escribe:

Z / R = {[0], [1]}

La relación de congruencia módulo 3 se puede definir de la siguiente forma: dado un elemento x ∈ Z,
se determina una partición de números enteros así:

[0] = {x ∈ Z /xI3 tiene residuo 0}
[1] = {x ∈ Z /x I3 tiene residuo 1}
[2] = {x ∈ Z /x I 3 tiene residuo 2}

El conjunto cociente o partición de los enteros por la relación de congruencia módulo 3 es:

Z / R = {[0], [1], [2]}

[ 60 ]

Bases matemáticas de la criptografía de clave asimétrica: la aritmética modular y la clave RSA

Lo anterior se cumple cualquiera que sea n ∈ N, si Z es el conjunto de números enteros, en general la
relación R de congruencia módulo n se puede escribir:

y la relación x R y se escribe:

Aritmética modular

R = {(x, y) ∈ Z2 / x –y es múltiplo de n}

x ≡ y (mod n)

Dos números a y b son congruentes módulo m, cuando los residuos de su división por el número m son
iguales.

Simbólicamente:

a≡b (mod. m)

que se lee: “a es congruente con b, módulo m”

De la definición anterior se derivan las dos consecuencias siguientes:

1) Si r es el residuo de la división de a por b se tiene la relación de congruencia

a ≡ r (mod b)

2) Si a es divisible por b, el residuo es cero y por tanto, la divisibilidad de a por b se escribe:

a ≡ 0 (mod b)

Propiedades de las congruencias del mismo módulo.

Estas propiedades son las consecuencias inmediatas de las igualdades de la división:

1) Dos números congruentes con un tercero, respecto de un mismo módulo, son congruentes entre

si respecto de dicho módulo.

Si a ≡ b (mod d) ∧ b ≡ c (mod. d),

Entonces, a ≡ c (mod d)

Demostración

a- b = Km.
a- c = k’m restando miembro a miembro se obtiene:
-b-(-c) = km-k’m
c – b = (k-k’) m
∴cLb (mod m)

2) Sumando miembro a miembro dos congruencias, respecto del mismo módulo, resulta otra

congruencia respecto de ese mismo módulo.

Si a ≡ b (mod m) ∧ c ≡ d (mod. m),
Entonces, a + c L b + d (mod. m)

Vector, Volumen 2, Enero - Diciembre 2007, págs. 59 - 69

[ 61 ]

Barco G., Carlos

Demostración

a- b = km
a- c = k’m sumando miembro a miembro se obtiene:
(a-b)+(c-d) = (k+k’) m
(a+c)- (b+d) = (k+k’) m
∴ (a+b) L (b+d) (mod m)

3) Restando miembro a miembro dos congruencias del mismo módulo, resulta otra congruencia

de dicho módulo.

Si a ≡ b (mod m) ∧ c ≡ d (mod. m),
Entonces, a – c L b – d (mod. m)

Demostración

a- b = km
a- c = k’m restando miembro a miembro se obtiene:
(a-b)-(c-d)= (k-k’) m
(a-c)-(b-d)= (k-k’) m
∴(a-c) L (b-d) (mod m)

Esta última igualdad supone que las substracciones son posibles: En las aplicaciones prácticas se añade, si
fuera necesario, múltiplos del módulo. La consecuencia de esta última igualdad es que en una congruencia
puede cambiarse un término de miembro, cambiando de signo. Las dos congruencias a ≡ b (mod m) y a
– b ≡ 0 (mod. m) son consecuencias una de la otra. Esto se enuncia en el siguiente teorema.

Teorema: La condición necesaria y suficiente para que dos números a y b den el mismo residuo al
dividirlos por un mismo número m, es que su diferencia sea divisible por m.

Demostración:

aL b (mod m)
a-b L (b-b) (mod m)
∴a-bL 0(mod m)

4) Multiplicando miembro a miembro dos congruencias de un mismo módulo, se obtiene otra

congruencia de dicho módulo.

Si a ≡ b (mod. m) ∧ c ≡ d (mod.m)
Entonces, a × c ≡ b × d (mod. m)

Demostración

a-b = km ∴a=km+b
c-d=k’m ∴c=k’m+d multiplicando miembro a miembro se obtiene:
a×c= (km+b) (k’m+d)
a×c= (kk’m2+kmd+k’mb+bd)
a×c- b×d=m (kk’m+kd+k’b)
∴ a×c≡ b×d (mod m)

[ 62 ]

Bases matemáticas de la criptografía de clave asimétrica: la aritmética modular y la clave RSA

Esta propiedad se extiende al producto de un número finito cualquiera de congruencias del mismo
módulo.

Demostración

a≡ b (mod m)
c≡ d (mod m)
e≡ f (mod m)
∴ a×c×e≡ b×d×f (mod m)
Se deduce de lo anterior que, dada una congruencia, si se elevan los dos miembros de ella a la misma
potencia resulta otra congruencia del mismo módulo.
Si [a ≡ b (mod. m)]n ⇒ [an ≡ bn (mod. m)]

Teorema: si en un producto de varios factores, uno de ellos es divisible por un número, su producto
también lo es.

Sea el producto a × b × c en donde b es, por hipótesis, divisible por m; esto es b ≡ 0 (mod. m); entonces
se puede escribir:
Si a ≡ a (mod. m), b ≡ 0 (mod. m) c ≡ c (mod. m)
Entonces a×b×c = a×0×c (mod. m). De donde se deduce que a×b×c = 0 (mod. m)
Esto demuestra que el producto a×b×c es divisible por m.

Aplicaciones de la aritmética modular: los números de identificación, los códigos de barras y la
transmisión de la información.

Los números de identificación tienen dos funciones principales:

identificar inequívocamente a la persona o cosa

a)
b) autocontrol del número

La transmisión libre de errores, garantiza la eficiencia de los sistemas de información de los bancos, de
los hipermercados, del correo postal, de los tiquetes aéreos, de las tarjetas de crédito, etc. Por esta razón,
se utiliza el último dígito (Low Significant Digit: LSD) como un código detector de error. El último dígito
es un dígito de verificación que es congruente módulo n con cierta suma ponderada de las cifras del
número que se quiere verificar o controlar la ausencia de errores. En los impresos se utilizan códigos de
barras que traducen las cifras decimales en números binarios. En estos impresos también aparecen las
letras (CK) (que simbolizan “check” encima del último dígito del número de identificación.

Por ejemplo, el servicio postal de E. U. utiliza números de identificación de 10 cifras más en dígito de
verificación que se obtiene del residuo de dividir el número entre 9, es decir:

n ≡ CK (mod. 9)

El número es congruente con el residuo CK módulo 9. Si el número es 18384459312-CK, el check se calcula
realizando la división del número por 9, esto es: 1838459312 ÷9= 204273256 y tiene un residuo de 8.

Este residuo es el código de detección de error de tal manera que el número de identificación es
18384593128, también lo escriben: 1838459312-8.

Los cheques viajeros American Express utilizan números de identificación de 9 cifras más el “check”. El
dígito de control CK se obtiene así: se efectúa la suma de sus cifras y se suma el CK, de tal manera que
la suma total sea divisible por 9. Esto se expresa simbólicamente así:

Vector, Volumen 2, Enero - Diciembre 2007, págs. 59 - 69

[ 63 ]





Barco G., Carlos



(mod. )

Así, si