GCM tablas M

[cpu2]

Hola

La duda que tengo esta en este paper, punto 4.1 Software:

https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/gcm-spec.pdf

Segun lo que puedo entender la variable P es una representacion de un elemento primitivo en gf(2), el modulo f es la variable R.

La x es un byte, tiene unas 256 conbinaciones, las tablas M son de 256 elementos.

Mas o menos todo esto lo llevo bien, si vamos a la pag 9, en (3) se puede observar la variable P que es el polinomio α.

En la pag 14 tenemos el algoritmo numero 3, con este podriamos computar las tablas M, los 65,535 bytes/key si no me equivoco. Doy por sentado de que con el algortimo 3, ya podria crear todas las tablas, cifrando la cadena de de 128 bits de 0s con el codigo.

Pero no acabo de entender del todo la variable P del algritmo 3.

Perdon si no se me entiende bien, estoy algo liado.

Saludos.

[kub0x]

La representacion del finite field GF(p^n) se puede realizar mediante el quotient ring de F_p(x)/f(x) donde f(x) es un polinomio irreducible sobre (over) GF(2) de grado n. Pero resulta, que la definición se puede realizar mediante un elemento primitivo, que es a su vez un cero de un polinomio irreducible.

Y te preguntarás, ¿cómo que un cero de un polinomio irreducible? ¿si un polinomio es irreducible no tiene ceros verdad? Bueno f(x) está over GF(2) y no tiene ceros ahí, cierto, pero y sobre una extensión, es decir, la x que entra a f(x) en vez de estar over GF(2) esté over GF(2^2) si su grado es 2. Puede que tenga un cero llamado alpha, y alpha sería un polinomio over GF(2) en vez de ser un elemento in GF(2). El over y el in lían mucho, over es que los coeficientes del polinomio estan definidos sobre GF e in GF significa que el polinomio esta en GF y sus  coeficientes en la base.

Por lo tanto podemos realizar tablas de multiplicación, exponenciales, aditivas, negativas, bases polinomiales en espacios vectoriales, vamos, muchisimas cosas.

Matemáticamente, digamos que tenemos una extensíon E sobre el campo F, puede ser GF(2^2) sobre GF(2) imaginate. Si yo te doy un poly irred sobre GF(2) que obviamente no tiene ceros en GF(2), encuentro un polinomio alpha en la extensión E tal que f(alpha)=0 entonces decimos que alpha es algebraica sobre el campo F.

Ahora mismo, creo que lo que te diría sobre el algoritmo te liaría aún más. Te recomiendo que cojas lo más parecido al RFC, compares, y postees de nuevo por aquí a ver si lo puedo simplificar para que se entienda desde el punto de vista de la computación. Resumiendo, leyendo las descripciones, por ejemplo V.P, V.P^2 etc quizá haga referencia a que P es un poly en alpha sobre GF(2) y que va tomando los coeficientes alpha^i y multiplicandolos por V (lo que es un shifteo como se ve arriba en el paper).

Si tengo (a^5+a^4+a^2).(a^3+a^2) sería (a^5+a^4+a^2).a^3 + (a^5+a^4+a^2).a^2. La a es alpha. Creo que entiendo eso, por lo que te digo que si me pasas algo más estandar mejor. Esto sería aprovechar la propiedad distributiva tomando alpha como la "x" (con el valor primitivo). Recuerda que estamos en F[ a ]/f(a) en vez de F[ x ]/f(x) debido a las relaciones anteriormente dichas.

Fíjate en este ejemplo utilizando Zech's Logarithms:

https://en.wikipedia.org/wiki/Zech%27s_logarithm#Examples

Métodos generales para aritmética en finite fields:

https://en.wikipedia.org/wiki/Finite_field_arithmetic

En este PDF situate en la página 19 y verás como también referencian el uso de las tablas logaritmicas para computar multiplicaciones, entre otras.

https://web.stanford.edu/class/ee392d/Chap7.pdf

EDIT=Una pena que el foro no tenga mathjax, sería mas fácil de escribir y leer notación.

Saludos.

[cpu2]

Hola

El de metodos generales, me recuerdo que ya lo lei en su dia, por el tema de AES. Voy a leer con calma los dos restantes.

Creo que ya cada vez lo tengo mas claro, tambien me preocupa mucho el peso de 64K que tienen las tablas, y cada vez que quiera cambiar el codigo volver a calcular y el espacio en memoria, pero eso ya es otra historia.

He visto que se pueden hacer tablas de 4-bit, y ocuparia unos 8,192 bytes, y solo consumiria un pelin mas de recursos, pero el espacio baja mucho.

Pero ya tengo bastante lio de momento, gracias por el apoyo.

Saludos.

[kub0x]

Pero ya tengo bastante lio de momento, gracias por el apoyo.

Realmente lo que estás haciendo es díficil, ya que entender un proyecto entero, por fases y algoritmos lleva semanas, pues tienes que entender bien cada parte. No te fustres, sigue el camino. Las dudas estarían bien acumularlas y cuando no puedas avanzar más, estudiar y responder tus propias preguntas. Te puedo decir que hace un año me inicié en una rama de la crypto de la cual no tenía ni idea, y a día de hoy, me veo con un nivel fuertísimo y leyendo lo que los expertos suben sin problema. Si lo tienes por hobby y te gusta, en poco tiempo veras grandes resultados.

En mi rutina utilizo Sage y Wolfram Mathematica. Traen métodos para reducir modulo f(x) y un sinfín más. Si no en C++ utilizo NTL que es una librería que es un All in 1. Trae lo básico de number theory y aritmética en GL(n,p), GL(n,p^e), GF(p), GF(p^n), creo que es incluso mejor utilizar éstas que rollear tus propios métodos aritméticos para la crypto.

Cuando no tengo ordenador, o el ejercicio que me planteo a mi mismo es pequeñito para encontrar contradiciones o simplemente curiosidades para investigar, utilizo las siguientes técnicas para realizar multiplicaciones en finite fields:

Si la función módulo es x^n-1 over F_q entonces dicho finite field es isomorfo al grupo de matrices circulantes over F_q denotado por C_n y multiplicando la matriz del poly p(x) por la 1º columna de la matriz del poly q(x) nos dan p(x).q(x). En este caso C_n  es un group algebra, y su representación como ves nos deja computar en una estructura u otra, al final es lo mismo.

Si la función módulo no es x^n-1 entonces podemos linearizar un polinomio, esto es, coger su representación lineal. Esto es un tema que he descubierto digamos, si quieres hacer muchos productos de p(x), digamos una tupla de  r productos { p(x).q_1(x), ..., p(x).q_r(x) } en vez de invocar el algoritmo convencional r veces, capturamos la transformación lineal de p(x) el cual tendría coeficientes enteros, claro. Entonces nos queda una matriz que representa el producto de p(x) por cualquier polinomio q(x). Sólo tenemos que introducir q(x) como vector (no como polinomio), y multiplicar M_p(x).v_q(x). Es un trucazo, pues calcularía la inversa de p(x) también si haces M^(-1)_p(x). No lo he visto en literatura, pero es algo que cualquiera que conozca los teoremas de representacion lineal de grupos puede llegar a saber.

Otro método típico es el descrito arriba con la propiedad distributiva, cojo p(x)=(a^5+a^4+a^2+1) y q(x)=(a^3+a+1) y p(x).q(x)= p(x)*a^3 + p(x)*a + p(x)*1. ¿Por qué? Bueno, digamos que q(x) es un polinomio, donde a su vez, cada coeficiente se puede tomar como polinomio. Claro está, que nos faltaría reducir dicho producto mod f(x).

Seguramente esto lo encontreís aburrido y/o tedioso de primeras, pero bueno, siempre podeís pedir un ejemplo por aquí.

Saludos.

[cpu2]

Realmente lo que estás haciendo es díficil, ya que entender un proyecto entero, por fases y algoritmos lleva semanas, pues tienes que entender bien cada parte. No te fustres, sigue el camino. Las dudas estarían bien acumularlas y cuando no puedas avanzar más, estudiar y responder tus propias preguntas. Te puedo decir que hace un año me inicié en una rama de la crypto de la cual no tenía ni idea, y a día de hoy, me veo con un nivel fuertísimo y leyendo lo que los expertos suben sin problema. Si lo tienes por hobby y te gusta, en poco tiempo veras grandes resultados.

Tengo que hacer lo que me acabas de decir, una recopilacion de todos los problemas que veo, y de hay sacar una conclusion, ya que no he avanzado mucho desde mi anterior mensaje, he buscado mas informacion tampoco es que haya mucha...

https://crypto.stackexchange.com/questions/57785/gcm-cipher-m0-tables-semantic-questions-on-how-to-implement-gcm?rq=1

https://crypto.stackexchange.com/questions/67642/gcm-optimisation-using-m-0-and-r-tables-calculation-of-r?rq=1

Ya veo que no soy el unico con problemas xD.

Si, todo lo que ago es por hobby pero con un proposito, tengo mas cosas por hacer, cosas que ni siquiera he planteado, y ahora mismo lo que siento es una perdida de tiempo, ya que no puedo estar profundizando tanto en las cosas, cuando te topas con este tipo de problemas te das cuenta de que no sabes nada...

En mi rutina utilizo Sage y Wolfram Mathematica. Traen métodos para reducir modulo f(x) y un sinfín más. Si no en C++ utilizo NTL que es una librería que es un All in 1. Trae lo básico de number theory y aritmética en GL(n,p), GL(n,p^e), GF(p), GF(p^n), creo que es incluso mejor utilizar éstas que rollear tus propios métodos aritméticos para la crypto.

Si, depende de como se mire estoy inventando la rueda de nuevo, seria mucho mas facil usar la libreria de openssl o cualquier otra, y hacer llamadas, pero no me gusta programar de esa forma me gusta crear mis propias funciones (no me gusta que mis programas solo haya call call call call xD), todos sabemos pasar parametros a funciones y llamarlas (no quiero ofender a nadie) a parte para el proposito que tengo es mejor asi.

Ahora mismo tengo esta rutina para hacer las multiplicaciones:

Código (asm) [Seleccionar] Expandir

section .data

_R: .quad 0x0000000000000000,0xe100000000000000

section .text
globl _mulbl

_mulbl:


pushq %rax
movdqa $-127, %rax         ; rax  == i
pxor %xmm0, %xmm0          ; xmm0 == Z


_C.0:

andq $1, 127(%rax,%r10)    ; %r10 == x
jz _C.1
pxor (%r11), %xmm0         ; %r11 == V

_C.1:

movdqa (%r11), %xmm1
andq $1, 127(%r11)
jz _C.2

psrldq $1, %xmm1
pxor _R, %xmm1
movdqa %xmm1, (%r11)
jmp _C.3

_C.2:

psrldq $1, %xmm1
movdqa %xmm1, (%r11)

_C.3:

incq %rax
js _C.0

popq %rax
retq


Bueno haciendo mis calculos a base de los del paper, sale mas o menos a unos 80-90 OPS por byte, sin tablas. En la pag 12 del documento sale la tabla, 119 OPS en la implementacion del paper.

Si miramos la tabla, con el metodo Shoup's, mejora notablemente el rendimiento, comparando mi funcion con el Shoup's de 4-bit, hay mas o menos un 30% de rendimiento superior a la mia.
Pero dudo que mi funcion cause overhead no?

Lo dicho dicho, voy a leer un pelin mas.

Saludos.

[cpu2]

Hola

Parace que voy entendiendo mas el paper, voy a explicarlo:

Cuando tengo que multiplicar por la variable P no es mas que un shift a los indices (creo que eso ya me lo has explicado @kub0x). Arriba de la pag 10 tengo el ejemplo de la multiplicacion por X · P y supongo que le de abajo es para multiplicar dos elementos.

Z ← 0, V ← X
for i =0 to 127 do
if Yi =1 then
Z ← Z ⊕ V
end if
V ← V · P
end for
return Z

Practicamente es lo mismo que el algoritmo 1, que explique en mi anterior duda de la sintaxis, si no me equivoco:

Z ← 0, V ← X
for i =0 to 127 do
if Yi =1 then Z ← Z ⊕ V
end if
if V127 =0
then V ← rightshift(V )
else
V ← rightshift(V ) ⊕ R
end if
end for return Z

Por lo que entiendo:

V ← V · P

Es igual a

if V127 =0 then
V ← rightshift(V )
else
V ← rightshift(V ) ⊕ R

Segun los ejemplos de la pag 9 en las formulas (3) (5), serian lo mismo no?

Bien ya en la pag 11 en el ejemplo de la desconposicion de X (7), xi hace referencia a 1 byte de X, pero mi duda esta en P^8i, en el primer for 8·i daria cero y al final cuando i es 15 daria 120. Esa parte no la entiendo mucho la verdad.

Creo que la respuesta esta en estos parrafos:

Note that i loops from 15 down to zero so that the rightmost byte is associated with the lowest power of P8. In order to use this method, we need an efficient way to compute X · P8 for an arbitrary element X.


The expression x · P8(i+1), for x ∈S and 0 ≤ i< 15, corresponds to a simple bit-rotation of the element x totherightbyeightbits.Thusthefirst15termsonthe right-handsideofEquation 9can be computed with only a rotation. The expression x · P128 is not so simple, but can be computed usinga table,aswedid above.

Pasando al algorimo 3 y a su explicacion arriba, vale creo que entiendo la funcion, en la explicacion cuando dice esto:

The table can be computed using Algorithm 3, which makes a single pass over the data, using only 247 field additions and eight 'mutliply by P' operations

while i> 0 do
M ← M[2i] · P
i ←li/2J

Partiendo de que el valor de i es 64, Ese ciclo multiplicaria por P ocho veces si no me equivoco.

Bien y en la parte de la multiplicacion por P:

M ← M[2i] · P

Es igual a

if  M[2i]127 =0 then
M ← rightshift(M[2i])
else
M ← rightshift(M[2i]) ⊕ R
end if

Y las 247 adiciones seria:

M[i + j]= M ⊕M[j]

Estoy en lo cierto?

Creo que con eso ya bastaria para crear la tabla M0, pero no entiendo lo de las elevacion a P a 8, 128 o i.

Saludos y gracias.

[cpu2]

Voy a dejar mis avances, creo que ya casi lo tengo, el algoritmo numero 3 el de la creacion de la tabla M0 es de la siguiente manera:

while 1
-----------------

M[128] =  H
M[64]  =  M[128]· P
M[32]  =  M[64] · P
M[16]  =  M[32] · P
M[8]   =  M[16] · P
M[4]   =  M[8]  · P
M[2]   =  M[4]  · P
M[1]   =  M[2]  · P

     while 2 and for
-----------------

for i = 2 

M[3]   =  M[2] XOR M[1]

i = 4   

M[5]   =  M[4] XOR M[1]
M[6]   =  M[4] XOR M[2]
M[7]   =  M[4] XOR M[3]

i = 8   

M[9]   =  M[8] XOR M[1]
M[10]  =  M[8] XOR M[2]
M[11]  =  M[8] XOR M[3]
M[12]  =  M[8] XOR M[4]
M[13]  =  M[8] XOR M[5]
M[14]  =  M[8] XOR M[6]
M[15]  =  M[8] XOR M[7]

i = 16   

M[17]  =  M[16] XOR M[1]
M[18]  =  M[16] XOR M[2]


to i =  .......128

M[0]  =  0^128

end
ret M

Eso crearia la tabla M0 de 4096 bytes a partir de H, pero tengo la siguente duda, ya que me quedaria por crear la tabla de R que son 1024 bytes. Supongo que se refiere a esto:

The index 192 (decimal)has a binary decomposition of 11000000, so M0[192] = H ⊕ H · P = M0[64] ⊕ M0[128].

Otra cosa que aun no he entendido es en el algoritmo 2 a la hora de usar las tablas M0, en la directiva byte(X,i), no la he encontrado documentada en el paper, pero supongo que tomara el byte de X segun el valor de i, pero no entiendo lo siguiente, en el caso de ser el valor de X "0xff" se haria un XOR a Z con esa tabla, pero como estan las tablas enumeradas? No se si me explico.

Saludos.

[kub0x]

Hola,

hace un tiempo que no comento en este post. Estudiando el campo de los finite fields, hace un tiempo di con una representación del producto de dos polinomios o elementos de GF(p^e) mediante operaciones en un algebra de matrices. Es decir, GF(p^e) es isomorfo a un algebra matricial, donde cada matriz representa un polinomio p(x) en GF(p^e) o F_q como lo quieras llamar.

Por lo tanto, dado un polinomio irreducible f(x) modulo p, podemos representar el producto p(x)q(x) = r(x) mediante una operacion Ax = b donde A es una matriz cuadrada que siempre tendrá determinante 1, por lo tanto no singular. x es un vector columna, es decir de n y b igual.

La matriz A en columnas quedaría: A = [p(x), p(x)*x,p(x)*x^2,...,p(x)*x^(n-1)]. Entonces al computar A.(y1,...,yn) obtendremos el producto el producto r(x) de ambos polinomios, como vector es decir en F_q^{n} que es un espacio vectorial (imaginate (1,0,1) en vector es 1+x^2.

Un ejemplito, toma el poly irreducible f(x) = y^4+y^3+1. La matriz A queda:

A =



y por lo tanto r(x)=pq(x) se escribe como un sistema de n ecuaciones no lineales en 2n variables:

x1 y1 + x4 y2 + (x3 + x4) y3 + (x2 + x3 + x4) y4,
x2 y1 + x1 y2 + x4 y3 + (x3 + x4) y4,
x3 y1 + x2 y2 + x1 y3 + x4 y4,
x4 y1 + (x3 + x4) y2 + (x2 + x3 + x4) y3 + (x1 + x2 + x3 + x4) y4

Ahora selecciona un p(x) y q(x) en este finite field. Múltiplica y comprueba que el sistema obtiene r(x).

Con este sistema puedes computar incluso las inversas, poli caracteristico, traza, trabajar en extensiones etc

Lo mismo pasa con los linearised polynomials, al final son matrices que definen la misma transformación lineal.

Saludos.

[cpu2]

Hola

Agradezco el apoyo, ya tengo algo terminado, cuando tenga todo listo lo subire, yo tambien hace tiempo que no digo nada por el echo que ahora mismo estoy haciendo otra cosa, como arreglarme la moto xD, no es broma.

A el codigo que subi esta mal, en casi todo, no se que me fumaria aquel dia, ya pondre el bueno.

Saludos.

[kub0x]

Hola

Agradezco el apoyo, ya tengo algo terminado, cuando tenga todo listo lo subire, yo tambien hace tiempo que no digo nada por el echo que ahora mismo estoy haciendo otra cosa, como arreglarme la moto xD, no es broma.

A el codigo que subi esta mal, en casi todo, no se que me fumaria aquel dia, ya pondre el bueno.

Saludos.

Estaría bien que pusieras por aquí el code de multiplicar dos elementos en GF(p^n). Así podemos comparar costes y si resulta mejor te facilito el código de multiplicación, el cual es matricial. Por lo demás, que siga todo bien.

Saludos.