Teoría de números

Teoría de números

Matemática discreta y congruencia

La congruencia es la base en la que se sustentan las operaciones de cifra en matemática discreta.

Divisibilidad de los números

En criptografía muchas veces nos interesará encontrar el máximo común denominador mcd entre dos números a y b.

Para la existencia de inversos en un cuerpo n, la base a y el módulo n deberán ser primos entre sí. Þ mcd (a, n) = 1

Sean dos números enteros a y b: se dice que a es congruente con b en el módulo o cuerpo n (Zn) si y sólo si existe algún entero k que divide de forma exacta la diferencia (a - b) .

Inversión de una operación de cifra

En criptografía deberá estar permitido invertir una operación para recuperar un cifrado Þ descifrar.

Aunque la cifra es una función, en lenguaje coloquial la operación de cifrado podría interpretarse como una “multiplicación” y la operación de descifrado como una “división”, si bien hablaremos en este caso de una multiplicación por el inverso

La analogía anterior sólo será válida en el cuerpo de los enteros Zn con inverso

Conjunto reducido de restos CRR

El conjunto reducido de restos, conocido como CRR de n, es el subconjunto {0, 1, ... ni, ... n-1} de restos, primos con el grupo n.

Si n es primo, todos los restos serán primos con él

Utilidad del CRR

El conocimiento del CRR permitirá aplicar un algoritmo para el cálculo del inverso multiplicativo de un número x dentro de un cuerpo n a través de la función f(n), denominada Función de Euler o Indicador de Euler.

Teorema de Euler

Dice que si mcd (a,n) = 1 Þ af(n) mod n = 1

Pequeño teorema de Fermat

Si el cuerpo de trabajo es un primo p:

mcd (a, p) = 1 Þ af(p) mod p = 1

Entonces a * x mod p = 1 y af(n) mod p = 1

Algoritmo Extendido de Euclides AEE

Si mcd (a, n) = 1 y a*x mod n = 1 Þ x = inv (a, n)

Teorema del Resto Chino TRC

Si n = d1*d2*d3* ... *dt con di = piei (p primo)

¿Para qué sirve entonces este algoritmo?

Entre otras cosas, cuando veamos el sistema de cifra RSA y el tema dedicado a Protocolos Criptográficos, encontraremos una interesante aplicación del teorema

La exponenciación en la cifra asimétrica

Una de las aplicaciones más interesantes de la matemática discreta en criptografía es la cifra asimétrica en la que la operación básica es una exponenciación AB mod n, en donde n es un primo grande o un producto de primos grandes.

¿Cuántos números primos hay?

Por el teorema de los números primos, se tiene que la probabilidad de encontrar números primos a medida que éstos se hacen más grandes es menor.

Utilidad de la raíz primitiva en criptografía

La utilidad de este concepto en criptografía lo veremos cuando se estudien los sistemas de clave pública y, en particular, el protocolo de intercambio de claves de Diffie y Hellman.