Aritmética modular

Antes de profundizar en los temas sobre criptografía, es necesario tener una base matemática, ya que al fin y al cabo, la criptografía se basa en ellas.

Nos centraremos en la aritmética modular, y cómo operar con ella. La aritmética modular se define del siguiente modo:

\[a \equiv b\pmod n,\]

si \(b - a\) es múltiplo de \(n\) o, dicho de otro modo, \(a\) y \(b\) tienen el mismo resto cuando se dividen por \(n\).

Así, por ejemplo, \(3 \equiv 8 \pmod 5\), ya que \(8 - 3 = 5\), que es un multiplo de 5. También podemos comprobarlo sabiendo que el resto de dividir 3 entre 5 es 3 y el resto de 8 entre 5, también. A partir de ahora expresaremos el resto de dividir un número entre otro como sigue:

\[a\bmod n = r,\]

donde \(r\) es el resto de dividir \(a\) entre \(n\).

Modular Arithmetics

Cálculo de inversos

Sea \(a \in \mathbb Z_n\), se dice que \(a\) tiene inverso, o que es una unidad, si \(\exists b \in \mathbb Z_n\ :\ ba = 1\), y se denota por \(a^{-1}\).

Al conjunto de todas las unidades de \(\mathbb Z_n\) lo llamaremos \(\mathcal{U}(\mathbb Z_n)\) y se define como:

\[\mathcal{U}(\mathbb Z_n) = \{ a \in \mathbb Z_n : \exists a^{-1}\} = \{ a \in \mathbb Z_n : mcd(a, n) = 1\},\]

donde mcd es el máximo común divisor.

Particularmente, si \(p\) es un número primo, todo elemento de \(\mathbb Z_p\), salvo el cero, tiene inverso, y por tanto \(\mathbb Z_p\) es un cuerpo. En criptografía, trabajaremos en cuerpos \(\mathbb Z_p\) con un \(p\) primo.

El número de unidades de \(\mathbb Z_n\), se puede calcular con la función de Euler \(\phi(n)\), y vale lo siguiente:

Por ejemplo, \(\#\mathcal{U}(\mathbb Z_5) = 4\), ya que todos sus elementos tienen inverso (el 1,2,3,4), y \(\phi(5) = 4\), y por tanto, \(\mathbb Z_5\) es un cuerpo. Sin embargo, \(\#\mathcal{U}(\mathbb Z_{15}) = 8\), ya que \(\phi(15) = \phi(3)\phi(5) = 2\cdot 4 = 8\). Las unidades de \(\mathbb Z_{15}\) son 1,2,4,7,8,11,13,14.



Un ejemplo práctico

Veamos ahora cómo calcular el inverso de un número en \(\mathbb Z_n\) mediante el algoritmo Extendido de Euclides implementado en python, el código fuente está disponible en github:

def extMcd(a,b):
    """
    Compute the Greatest Common Divisor d of a and b, and integers x and
    y satisfying ax + by = d.

    :returns: a tuple (d,x,y)
    """

    if b == 0:
        return a,1,0
    x2 = 1
    x1 = 0
    y2 = 0
    y1 = 1

    while b != 0:
        q = a//b
        r = a - q * b
        x = x2 - q * x1
        y = y2 - q * y1
        a = b
        b = r
        x2 = x1
        x1 = x
        y2 = y1
        y1 = y

    if a < 0:
        return map(int, (-a, -x2, -y2))
    return map(int, (a, x2, y2))

Este algoritmo, devuelve una tupla (d, x, y), donde d es el máximo común divisor de los números a,b y x es el inverso de a mod b. Por ejemplo, si ejecutamos mcd(2, 5), nos devolverá [1, -2, 1], donde 1 es el mcd(2, 5), y \(-2\) su inverso, si lo queremos en positivo, basta con sumar 5 a \(-2\), que es 3, luego el inverso de 2 mod 5 es 3, ya que \(2 \cdot 3 = 6\), y 6 mod 5 = 1.

Para facilitar la tarea de calcular el inverso de un número, definiremos el siguiente método, el código fuente está disponible en github:

def moduloInverse(a,n):
    """:returns: the inverse of a modulo b, if it exists"""
    d,x,y = extMcd(a,n)

    if d > 1:
        return u' a inverse does not exist'
    else:
        return x % n

Si lo ejecutamos con los mismos números de antes, 2 y 5, nos devolverá \(2^{-1}\), es decir, 3.

Agradecimientos

Gracias a josealberto4444 por ayudarme con correcciones.

Referencias

Todo el código mostrado en los artículos está disponible en github

Más información

¿Has visto algún error?: Por favor, ayúdame a corregirlo contactando conmigo o comentando abajo.

Quizá también te interese leer...