En 1985, ElGamal diseñó un sistema cuya seguridad se basa en la dificultad de calcular logaritmos discretos.
Este sistema no encaja perfectamente con la definición de un criptosistema de llave pública, ya que el conjunto de posibles textos planos (enteros mod p) no es el mismo que el conjunto de posibles textos cifrados (pares de enteros (r, t) mod p).
Cifrado
Alice quiere enviarle un mensaje a Bob.
Bob selecciona un número primo grande y un generador o raíz primitiva tal que .
Bob elige un entero secreto y calcula .
La información se hace pública y es la llave pública de Bob.
Alice descarga .
Alice convierte el mensaje en un entero tal que . Si es mayor, se divide en bloques más pequeños. Se utiliza cualquier método para la conversión.
Alice elige un entero aleatorio secreto y calcula .
Alice calcula .
Alice envía el texto cifrado a Bob.
Descifrado
Bob recibe el texto cifrado de Alice.
Bob realiza el cálculo .
Bob realiza la conversión de a texto.
Referencias
Trappe, W., Washington, L. (2006). Discrete Logarithms. En Introduction to Cryptography with Coding Theory(212-214). United States of America: Prentice Hall.
Aritmética modular es una forma simple de realizar aritmética en un conjunto finito de enteros.
Sea , , ∈ (donde es un conjunto de todos los enteros) y . Se escribe:
a ≡ r mod m
si divide .
Donde:
es llamado el módulo
es llamado el residuo
La línea se lee como "a es congruente con r módulo m"
Se supone que se divide y por , obteniendo cocientes y residuos enteros, donde los residuos están entre 0 y m - 1. Es decir, y , donde y .
Entonces no es difícil ver que si y solo si .
OBSERVACIÓN: Para propósito de la criptografía siempre se define como un número no-negativo.
Ahora se puede definir el módulo aritmético : se define como el conjunto , equipado con dos operaciones, y . La suma y la multiplicación modular son exactamente como la suma y multiplicación aritmética, excepto que los resultados se reducen módulo .
Por ejemplo, supongamos que queremos calcular 11 × 13 en . Como números enteros, tenemos 11 × 13 = 143. Para reducir 143 módulo 16, simplemente realizamos una división larga ordinaria: 143 = 8 × 16 + 15, por lo que 143 mod 16 = 15 y, por lo tanto, 11 × 13 = 15 en .
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
Douglas Stinson. (1995). Cryptography: Theory and Practice. United States: CRC Press.
El inverso aditivo en la aritmética modular se puede definir como el complemento del número original, de tal forma que la suma de ambos (complemento y original) sea igual al módulo.
En otras palabras, el inverso aditivo de cualquier ∈ es , es decir, para cualquier ∈ .
Por ejemplo:
a = 5 en Z26
-a = 26 - 5
Entonces:
-a = 21
Referencias
Douglas Stinson. (1995). Cryptography: Theory and Practice. United States: CRC Press.
En aritmética modular el inverso multiplicativo se define de la siguiente manera.
Sea
a * a-1 ≡ 1 mod m
El inverso multiplicativo existe solo para algunos, pero no para todos, elementos.
Un elemento tiene un inverso multiplicativo si y solo si , donde mcd es el máximo común divisor, es decir, el entero más grande que divide ambos números y . El hecho de que dos números tengan un mcd de 1 es de gran importancia y hay un nombre especial para eso: si , entonces y se dice que son primos relativos o coprimos.
Por ejemplo:
Veamos si el inverso multiplicativo de 14 existe en .
Porque
el inverso debe existir. Por otro lado,
el inverso multiplicativo de 15 no existe en .
Encontrar un inverso multiplicativo
Lo primero que se hace es aplicar el algoritmo de Euclides para verificar que donde es el número del que queremos obtener su inverso multiplicativo y es el número de elementos del conjunto (alfabeto) con el que estemos trabajando.
Ejemplo: Vamos a calcular el inverso de 7 y consideremos que estamos trabajando con el alfabeto español que tiene 27 letras, entonces y .
Usando el Algoritmo de Euclides se calcula el máximo común divisor:
.
.
.
.
Utilizando los pasos del Algoritmo de Euclides se procede a calcular el inverso
Del paso 3 se despeja el residuo, .
Del paso 2 se despeja el residuo y si esto lo sustituimos en la ecuación del paso 5 tenemos: .
Del paso 1 se despeja el residuo y si esto lo sustituimos en la ecuación del paso 6 nos queda: .
El número que multiplica a 8 es el inverso multiplicativo, pero como es negativo se debe calcular su inverso aditivo.
El inverso multiplicativo de 8 en es , demostración: .
En el algoritmo anterior los resultados es importante simplificarlos lo más posible y tratar de dejarlos en términos del número del que buscamos el inverso, , así como de .
Una alternativa, aunque poco práctica, es ir multiplicando el número del que queremos saber su inverso por otro número y aplicar al resultado la operación módulo, para el ejemplo anterior , hasta que obtengamos un 1:
. . .
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
Douglas Stinson. (1995). Cryptography: Theory and Practice. United States: CRC Press.
Realizar la operación de elevar un número a una cierta potencia y después aplicarle la operación módulo puede ser algo fácil o difícil de hacer dependiendo tanto del exponente.
Por ejemplo:
Elevar 5 a la potencia 3 en Z27
es algo fácil de calcular porque el exponente es pequeño.
Ahora elevamos 5 a la potencia 21 en Z27
y notamos que se vuelve más difícil de hacer.
El método más simple para realizar una exponenciación modular basa su funcionamiento en el hecho de que no importa que tan grande sea la potencia, el resultado siempre será un número entre y .
Para explicar este método se usará el ejemplo anterior.
Se toma la base y se escribe en forma de multiplicación.
Se toman los dos primeros números, se multiplican entre ellos y se calcula el módulo.
El 25 se coloca en lugar de los 2 primeros números.
*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5
Se vuelven a tomar los dos primeros números, se multiplican entre ellos y se calcula el módulo.
El 25 se coloca en lugar de los 2 primeros números.
*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5
Se repiten los pasos hasta que solo quede un número.
*5
El número final es el resultado de la exponenciación modular.
Realizar la operación de elevar un número a una cierta potencia y después aplicarle la operación módulo puede ser algo fácil o difícil de hacer dependiendo tanto del exponente.
Por ejemplo:
Elevar 5 a la potencia 3 en Z27
es algo fácil de calcular porque el exponente es pequeño.
Ahora elevamos 5 a la potencia 20 en Z27
y notamos que se vuelve más difícil de hacer.
Un método muy eficaz y rápido para realizar una exponenciación modular con exponentes muy grandes es la Exponenciación Modular Binaria
Este algoritmo hace uso de solo dos operaciones:
Elevar al cuadrado (SQ) el resultado actual.
Multiplicar (MUL) el resultado actual por el elemento base.
Este algoritmo está basado en escanear el bit del exponente desde la izquierda (el bit más significativo) a la derecha (el bit menos significativo). En cada iteración, es decir, por cada bit del exponente, el resultado actual se eleva al cuadrado. Si y solo si el bit del exponente escaneado actualmente tiene el valor de 1, una multiplicación del resultado actual por la base es ejecutada después de la elevación al cuadrado. Después de cada paso se aplica la operación módulo para mantener el resultado intermedio pequeño.
Ahora se explicará con el ejemplo anterior.
En primer se mostrará la representación binaria del exponente:
El algoritmo escanea los bits del exponente empezando por la izquierda con y finalizando con el bit más a la derecha .
Paso
Desarrollo
Operaciones
Resultado
#0
5 = 512
Ajuste inicial, bit escaneado: h4 = 1
5 mod 27
#1a
(51)2 = 52 = 5102
SQ, bit scaneado: h3
52 ≡ 25 mod 27
#1b
no MUL, ya que h3 = 0
#2a
(52)2 = 54 = 51002
SQ, bit scaneado: h2
252 ≡ 4 mod 27
#2b
54*5 = 55 = 51012
MUL, ya que: h2 = 1
4 * 5 ≡ 20 mod 27
#3a
(55)2 = 510 = 510102
SQ, bit scaneado: h1
202 ≡ 22 mod 27
#3b
no MUL, ya que h1 = 0
#4a
(510)2 = 520 = 5101002
SQ, bit scaneado: h0
222 ≡ 25 mod 27
#4b
520*5 = 521 = 5101012
MUL, ya que: h0 = 1
25 * 5 ≡ 17 mod 27
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
Realizar la operación de elevar un número a una cierta potencia y después aplicarle la operación módulo puede ser algo fácil o difícil de hacer dependiendo tanto del exponente.
Por ejemplo:
Elevar 5 a la potencia 3 en Z27
es algo fácil de calcular porque el exponente es pequeño.
Ahora elevamos 5 a la potencia 20 en Z27
y notamos que se vuelve más difícil de hacer.
Teorema de Euler
El Teorema de Euler dice: Sean y enteros con , entonces
aφ(m) ≡ 1 mod m
Este teorema sirve para reducir el exponente en una exponenciación modular siempre que:
Para explicar su funcionamiento se usará el ejemplo anterior.
Se calcula φ(27) (Phi de Euler)
Se expresa el exponente en términos de φ(27).
Como mcd(5 , 27) = 1 y φ(27) < 21 se puede aplicar el Teorema de Euler
Se hace la sustitución.
Ahora que el exponente se ha reducido se puede aplicar cualquier otro método de exponenciación modular.
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
y es el número positivo más grande que divide ambos y . Para números pequeños, el mcd es fácil de calcular por la factorización de ambos números y encontrando el factor común más alto.
Para números más grandes a menudo no es posible factorizar, y un algoritmo más eficiente es usado para calcular el mcd, el Algoritmo de Euclides.
La principal observación de este algoritmo es que se puede reducir el problema de encontrar el mcd de dos números dados al mcd de 2 números más pequeños. Este proceso puede ser aplicado recursivamente hasta que finalmente se obtenga
Se explicará el funcionamiento del algoritmo con un ejemplo.
Sea y
Se toma el número mayor y se expresa en términos del menor.
Por lo tanto
Se toma el ahora nuevo número mayor y se expresa en términos del nuevo menor.
Se repiten los pasos hasta que el número menor sea 0.
Una vez que se llegó a la ronda con el número menor igual a 0, el número mayor de esa misma ronda es el mcd de los números originales.
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
Se considera el anillo , es decir, el conjunto de enteros . Se está interesado en el problema de conocer cuántos números en este conjunto con coprimos con . Esta cantidad es dada por la función Phi de Euler, la cual se define como sigue:
El número de enteros en coprimos a es denotado por .
Por ejemplo:
Sea m = 6. El conjunto asociado es .
Ya que hay dos números en el conjunto que son coprimos a 6, sean 1 y 5, la función phi toma el valor de 2, es decir .
Para números pequeños no supone ningún problema, pero para números grandes tomaría mucho tiempo en calcular el mcd entre m y todos los valores de Zm.
Propiedades de Phi de Euler:
Si es primo ⇒ .
Si es primo ⇒ .
Sea . Si ⇒ .
Sea ⇒ .
Por ejemplo:
Propiedad 1.
Sea ⇒
Propiedad 2.
Sea ⇒
Propiedad 3.
Sea ⇒
Propiedad 4.
Sea
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
Cuando p es un primo, una raíz primitiva mod p es un número cuyas potencias producen todos los números mod p con excepción del 0 (1, 2, 3, ... p-1).
Considere las potencias de 3 mod 7:
31 ≡ 3 32 ≡ 2 33 ≡ 6 34 ≡ 4 35 ≡ 5 36 ≡ 1
Obsérvese que se obtienen todos los números mod 7 con excepción del 0 como potencias de 3 (1, 2, 3, 4, 5, 6). Esto significa que 3 es una raíz primitiva mod 7.
Ahora consideramos las potencias de 2 mod 7:
21 ≡ 2 22 ≡ 4 23 ≡ 1 24 ≡ 2 25 ≡ 4 26 ≡ 1
Obsérvese que no se obtienen todos los números mod 7 con excepción del 0 como potencias de 2 (1, 2, 3, 4, 5, 6). Esto significa que 2 NO es una raíz primitiva mod 7.
Referencias
Trappe, W., Washington, L. (2006). Discrete Logarithms. En Introduction to Cryptography with Coding Theory(210-212). United States of America: Prentice Hall.
Dos matrices A y B son multiplicables si el número de columnas de A coincide con el número de filas de B.
El elemento Cik de la matriz producto se obtiene multiplicando cada elemento de la fila i de la matriz A por cada elemento de la columna j de la matriz B y sumándolos.
Referencias
S/A. (S/F). Matrices. Febrero 15, 2017, de KHANACADEMY. Sitio web: KHANACADEMY - Matrices
El determinante se define para matrices cuadradas. Su definición formal es complicada y se basa en el conjunto de permutaciones, pero existen varios métodos para calcularlos según la dimensión de la matriz. Para este apartado se usa una dimensión de 3 dando como resultado la matriz de la forma
Se define su determinante como:
Referencias
S/A. (S/F). Matrices. Febrero 15, 2017, de KHANACADEMY. Sitio web: KHANACADEMY - Matrices
Un campo finito, a veces también llamado campo de Galois, es un conjunto con un número finito de elementos. A grandes rasgos, un campo de Galois es un conjunto finito de elementos en los que podemos sumar, restar, multiplicar e invertir. Antes de introducir la definición de un campo, primero se necesita el concepto de una estructura algebraica más simple, un grupo.
Grupo
Un grupo es un conjunto de elementos G junto con una operación ∘ que combina dos elementos de G. Un grupo tiene las siguientes propiedades:
La operación de grupo ∘ es cerrada. Es decir, para todo a, b, ∈ G, sostiene que a ∘ b = c ∈ G.
La operación de grupo es asociativa. Es decir, a ∘ (b ∘ c) = (a ∘ b) ∘ c para todo a, b, c ∈ G.
Existe un elemento 1 ∈ G, llamado elemento neutro (o elemento de identidad), tal que a ∘ 1 = 1 ∘ a = a para todo a ∈ G.
Para cada a ∈ G existe un elemento a-1 ∈ G, llamado inverso de a, tal que a ∘ a-1 = a-1 ∘ a = 1.
Un grupo G es conmutativo si, además, a ∘ b = b ∘ a para todo a, b ∈ G.
Para tener las cuatro operaciones aritméticas básicas (es decir, suma, resta, multiplicación, división) en una estructura, necesitamos un conjunto que contenga un grupo aditivo y un grupo multiplicativo. Esto es lo que llamamos un campo.
Campo
Un campo F es un conjunto de elementos con las siguientes propiedades:
Todos los elementos de F forman un grupo aditivo con la operación de grupo "+" Y el elemento neutro 0.
Todos los elementos de F excepto 0 forman un grupo multiplicativo con la operación de grupo x y el elemento neutro 1.
Cuando las dos operaciones del grupo están mezcladas, la ley de distributividad se mantiene, es decir, para todos a, b, c ∈ F: a (b + c) = (ab) + (ac).
Por ejemplo. El conjunto E de números reales es un campo con el elemento neutro 0 para el grupo aditivo y el elemento neutro 1 para el grupo multiplicativo. Cada número real a tiene un inverso aditivo, llamado -a, y cada elemento no nulo a tiene un inverso multiplicativo 1/a.
En la criptografía, casi siempre se está interesado en campos con un número finito de elementos, que llamamos campos finitos o campos de Galois. El número de elementos en el campo se denomina orden o cardinalidad del campo. Es de importancia fundamental el siguiente teorema:
Un campo con orden m sólo existe si m es una potencia prima, es decir, m = pn, para algún número entero positivo n y entero primo p. p es llamado característica del campo finito.
Este teorema implica que existen, por ejemplo, campos finitos con 11 elementos, o con 81 elementos (desde 81 = 34) o con 256 elementos (ya que 256 = 28, y 2 es un primo). Sin embargo, no hay campo finito con 12 elementos desde 12 = 22 · 3, y 12 no es, por lo tanto, una potencia prima.
Campos primos
Los ejemplos más intuitivos de campos finitos son campos de orden primo, es decir, campos con n = 1. Los elementos del campo GF(p) pueden ser representados por enteros 0, 1, ... , p-1. Las dos operaciones del campo son la adición entera modular y la multiplicación entera módulo p.
Sea p un primo. El anillo entero Zp se denomina GF(p) y se denomina campo primo, o como campo Galois con un número primo de elementos. Todos los elementos no nulos de GF(p) tienen un inverso. La aritmética en GF(p) se hace módulo p
Para hacer la aritmética en un campo primo, se deben seguir las reglas para los anillos enteros: La adición y la multiplicación se hacen módulo p, el aditivo inverso de cualquier elemento a está dado por a + (-a) = 0 mod p, y el inverso multiplicativo de cualquier elemento no nulo a se define como a · a-1 = 1.
Por ejemplo. Consideramos el campo finito GF(5) = {0, 1, 2, 3, 4}. Las tablas a continuación describen cómo sumar y multiplicar dos elementos cualquiera, así como el inverso aditivo y multiplicativo de los elementos del campo. Utilizando estas tablas, podemos realizar todos los cálculos en este campo sin utilizar explícitamente la reducción modular.
Tablas de las operaciones aritméticas para GF(5)
Un campo primo muy importante es GF(2), que es el campo finito más pequeño que existe. Ahora veamos las tablas de multiplicación y suma para el campo. Ejemplo. Consideremos el campo finito pequeño GF(2) = {0,1}. La aritmética se hace simplemente módulo 2, produciendo las siguientes tablas aritméticas:
Tablas de suma y multiplicación para GF(2)
Campos de extensión GF(2m)
En AES el campo finito contiene 256 elementos y se denomina GF(28). Este campo fue elegido porque cada uno de los elementos de campo puede ser representado por un byte. Para las transformaciones S-Box y MixColumn, AES trata cada byte como un elemento del campo GF(28) y manipula los datos realizando la aritmética en este campo finito.
En el campo GF(28), que se utiliza en AES, cada elemento A ∈ GF(28) se representa así:
A (x) = a7x7 + ··· + a1x + a0, ai ∈ GF(2) = {0,1}
Observe que hay exactamente 256 = 28 tales polinomios. El conjunto de estos 256 polinomios es el campo finito GF(28). También es importante observar que cada polinomio puede ser simplemente almacenado en forma digital como un vector de 8 bits A = (a7, a6, a5, a4, a3, a2, a1, a0). En particular, no tenemos que almacenar los factores x7, x6, etc. Está claro que de las posiciones de los bits, a que potencia xi pertenece cada coeficiente.
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
La inversión en GF(28) es la operación principal de la operación de sustitución de bytes, que contiene la caja S de AES. Para un campo finito dado GF(2m) y el correspondiente polinomio de reducción irreducible P(x), la inversa A-1 de un elemento no nulo A ∈ GF(2m) se define como:
A-1(x)·A(x) = 1 mod P(x)
La tabla siguiente contiene todos los inversos en GF(28) módulo P(x) = x8 + x4 + x3 + x + 1 en notación hexadecimal. Un caso especial es la entrada para el elemento de campo 0, para el que no existe una inversa. Sin embargo, para la S-Box del AES, se necesita una tabla de sustitución que se define para cada posible valor de entrada. Por lo tanto, los diseñadores definieron el S-Box de tal manera que el valor de entrada 0 se asigna al valor de salida 0.
Tablas de los inversos en GF(28)
Por ejemplo:
A partir de la tabla anterior, el inverso de x7 + x6 + x = (11000010)2 = (C2)hex = (xy)
Está dado por el elemento en la fila C, columna 2:
(2F)hex = (00101111)2 = x5 + x3 + x2 + x + 1.
Esto se puede verificar mediante la multiplicación:
(x7 + x6 + x) · (x5 + x3 + x2 + x + 1) ≡ 1 mod P(x).
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
La multiplicación en GF(28) es la operación básica de la operación MixColumn de AES. En un primer paso, se multiplican dos elementos (representados por sus polinomios) de un campo finito GF(2m) usando la regla de multiplicación polinomial estándar:
c’0 = a0b0 mod 2 c’1 = a0b1 + a1b0 mod 2 . . . c’2m-2 = am-1bm-1 mod 2
Se debe tener en cuenta que todos los coeficientes ai, bi y ci son elementos de GF(2), y que el coeficiente aritmético se realiza en GF(2). En general, el polinomio producto C(x) tendrá un grado mayor que m-1 y deberá ser reducido. Esto se hace de la siguiente manera: El producto de la multiplicación será dividido por un cierto polinomio, y se considera solamente el resto después de la división polinomial. Son necesarios polinomios irreducibles para la reducción del módulo.
Definición. Multiplicación de campo de extensión:
Sea A(x), B(x) ∈ GF(2m) y sea
un polinomio irreducible. La multiplicación de los dos elementos A(x), B(x) se realiza como:
C(x) ≡ A(x) · B(x) mod P(x).
Para AES, el polinomio irreducible que se utiliza es P(x) = x8 + x4 + x3 + x + 1. Es parte de la especificación del cifrado AES.
Por ejemplo.
Queremos multiplicar los dos polinomios A(x) = x3 + x2 + 1 y B(x) = x2 + x en el campo GF(24). El polinomio irreducible de este campo se da como:
P(x) = x4 + x + 1.
El producto polinomial se calcula como:
C’(x) = A(x)·B(x) = x5 + x3 + x2 + x.
Ahora podemos reducir C’(x) usando el método de división polinómica que se aprende en la escuela. Sin embargo, a veces es más fácil reducir cada uno de los términos principales x4 y x5 individualmente:
x4 = 1·P(x)+(x+1) x4 ≡ x+1 mod P(x) x5 ≡ x2 +x mod P(x).
Ahora, sólo tenemos que insertar la expresión reducida para x5 en el resultado intermedio C’(x):
Una curva elíptica es un tipo especial de ecuación polinomial. Para el uso criptográfico, debemos considerar la curva no sobre los números reales sino sobre un campo finito. La elección más popular son los campos primos GF(p), donde toda la aritmética se realiza módulo un primo p.
Curva elíptica
La curva elíptica sobre Zp, p > 3, es el conjunto de todos los pares (x, y) ∈ Zp que cumplen:
y2 ≡ x3 + a · x + b mod p
junto con un punto imaginario de infinito O, donde a, b ∈ Zp y la condición 4 · a3 + 27 · b2 ≠ 0 mod p.
La definición de curva elíptica requiere que la curva sea no singular. Geométricamente hablando, esto significa que la gráfica no tiene intersecciones o vértices, lo cual se logra si el discriminante de la curva -16 (4a3 + 27b2) es distinto de cero.
Para uso criptográfico estamos interesados en estudiar la curva sobre un campo primo como en la definición.
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
La suma de puntos se define como R = P + Q donde P != O (punto al infinito). El doblado de puntos se define como R = P + P = 2P, de lo anterior podemos ver que el doblado de puntos sería simplemente una serie de suma de puntos. Por lo tanto existen 2 fórmulas para llevar a cabo estas operaciones.
Para sumar 2 puntos diferentes:
Para sumar 2 puntos iguales:
Ejemplo
Trabajando en el campo pequeño Z23
Sea P = (4,7) y Q = (13, 11), obtener P + Q = (x3 , y3):
Para el uso criptográfico, tenemos que considerar la curva no sobre los números reales sino sobre un campo finito. La opción más popular son los campos primos GF(p), donde toda la aritmética se hace módulo un primo p. Es por esto que se eligió el número 23 ya que es primo. Los coeficientes a y b deben satisfacer que primero pertenezcan al campo primo, en este caso, 23 y que 4a3 + 27b2 != 0 mod p, verificamos lo anterior, a = 1 y b = 4, ambos están en el campo y
E = 4(1)3 + 27(4)2 mod 23 E = 4 + 432 mod 23 E = 436 mod 23 E = 22
por lo tanto tenemos una curva elíptica válida.
Obtener puntos
Como se explica en la teoría, se necesita de un punto que pertenezca a la curva para realizar las operaciones, a este punto se le conoce como punto generador, pero antes de hablar más sobre él, explicaremos como obtener los puntos de la curva.
Obtener los residuos cuadráticos:
Elementos de p(1-22)
mod p
Residuo
12
mod 23
1
22
mod 23
4
32
mod 23
9
42
mod 23
16
52
mod 23
2
62
mod 23
13
72
mod 23
3
82
mod 23
18
92
mod 23
12
102
mod 23
8
112
mod 23
6
122
mod 23
6
132
mod 23
8
142
mod 23
12
152
mod 23
18
162
mod 23
3
172
mod 23
13
182
mod 23
2
192
mod 23
16
202
mod 23
9
212
mod 23
4
222
mod 23
1
Tabla 1
Por lo tanto los residuos cuadráticos para p = 23 son RC(23) = {1, 4, 9, 16, 2, 13, 3, 18, 12, 8, 6}.
Para obtener los puntos, vamos a sustituir en la curva los valores de (0, p-1) o sea (0, 22), buscamos si el resultado se encuentra en los residuos cuadráticos obtenidos, si se encuentra entonces en la siguiente columna tenemos la pareja de números con los que obtuvimos ese residuo y en la columna final anotamos la pareja de puntos que son resultado de la combinación del valor de x con cada número de la pareja:
x
E= y2= x3 + x + 4 mod 23
¿Se encuentra en RC(23)?
Valores con los que se obtuvo el residuo
Puntos
0
4
Sí
(2,21)
(0,2)(0,21)
1
6
Sí
(11,12)
(1,11)(1,12)
2
14
No
()
()()
3
11
No
()
()()
4
3
Sí
(7,16)
(4,7)(4,16)
5
19
No
()
()()
6
19
No
()
()()
7
9
Sí
(3,20)
(7,3)(7,20)
8
18
Sí
(8,15)
(8,8)(8,15)
9
6
Sí
(11,12)
(9,11)(9,12)
10
2
Sí
(5,18)
(10,5)(10,18)
11
12
Sí
(9,14)
(11,9)(11,14)
12
19
No
()
()()
13
6
Sí
(11,12)
(13,11)(13,12)
14
2
Sí
(5,18)
(14,5)(14,18)
15
13
Sí
(6,17)
(15,6)(15,17)
16
22
No
()
()()
17
12
Sí
(9,14)
(17,9)(17,14)
18
12
Sí
(9,14)
(18,9)(18,14)
19
5
No
()
()()
20
20
No
()
()()
21
17
No
()
()()
22
2
Sí
(5,18)
(22,5)(22,18)
Tabla 2
De la tabla se podemos ver que obtuvimos 28 puntos, a estos se les suma un punto que se conoce como punto al infinito, se trata de un elemento neutral que tiene la propiedad: P + O = P, donde O es el punto al infinito.
Otro concepto importante que nace es que se le conoce como orden de la curva al número de puntos que existen, por lo tanto para esta curva decimos que tiene un orden de 29.
Para finalizar es importante hablar sobre el punto generador. El punto generador es un punto con el cual a partir de él se pueden obtener los demás puntos del grupo haciendo uso del doblado y suma de puntos, para ver si un punto es generador o no, lo tomamos y realizamos la operación 2P, si el punto resultado se encuentra dentro de los puntos de la curva, habrá que calcular 3P y así hasta obtener todos los puntos de la curva, si el punto seleccionado nos da un punto que no existe dentro de la curva, habrá que elegir a otro punto y realizar el mismo proceso. Es necesario aclarar que cuando se llegue al último cálculo de estos puntos el resultado se va a indeterminar lo que significa que obtuvimos el punto al infinito(O).
Dado que el orden de la curva (29) con la que estaremos trabajando en la animación es primo, nos dice que el grupo con el que decidimos trabajar (23) es cíclico y cualquier punto es generador de todo el grupo de puntos que calculamos en la tabla 2, para el caso en el que no sea primo habrá que ir probando punto por punto del grupo. El punto seleccionado para trabajar en las animaciones es el (0,2). A continuación en la figura 1 se muestran cómo se obtuvieron todos los puntos de la tabla 2, a partir del (0,2):
Figura 1
Referencias
Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
La suma de puntos se define como R = P + Q donde P != O (punto al infinito). El doblado de puntos se define como R = P + P = 2P, de lo anterior podemos ver que el doblado de puntos sería simplemente una serie de suma de puntos. Por lo tanto existen 2 fórmulas para llevar a cabo estas operaciones.
Para sumar 2 puntos diferentes:
Para sumar 2 puntos iguales:
Ejemplo
Trabajando en el campo pequeño Z23
Sea P = (4,7) y Q = (13, 11), obtener P + Q = (x3 , y3):
Los datos numéricos, los datos de serie y el valor nulo pueden funcionar como datos lógicos. Los datos numéricos y de serie pueden tener el valor lógico verdadero o falso. El valor numérico 0 (cero) es falso; todos los demás valores numéricos son verdaderos. Los datos de serie de caracteres que no son una serie vacía son verdaderos; una serie vacía es falsa. El valor nulo no es verdadero ni falso. Tiene el valor lógico especial nulo.
Los operadores lógicos realizan pruebas en expresiones lógicas. Las expresiones lógicas que se evalúan como cero o una serie vacía son falsas. Las expresiones lógicas que se evalúan como valor nulo son nulas. Las expresiones que se evalúan como cualquier otro valor son verdaderas.
Una forma de desplazamiento de bits es el desplazamiento circular o rotación de bits. En esta operación, los bits de un registro son “rotados” de una manera circular como si los extremos izquierdo y derecho del registro estuvieran conectados. En la rotación hacia la izquierda, el bit que sale por el extremo izquierdo entrará por el extremo derecho, y viceversa con la rotación hacia la derecha.
Desplazamiento o rotación circular hacia la izquierda
Desplazamiento o rotación circular hacia la derecha