Bases Matemáticas De La Criptografía

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 refiere a la aritmética modular y sus aplicaciones: por un lado, el cálculo del dígito de verificación en los números de identificación; y por elotro, 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 ofthe 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 verification digit in identification numbers, and on the other side, modular arithmetic applied to the public key RSA cryptography. Toachieve 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: carlosbarco@ucaldas.edu.co
Vector, Volumen2, 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 congruentecon 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 congruenciamó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 seexpresa: 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 lasiguiente 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...