Multiplicacion por bloques GCM

[cpu2]

Hola, estado tiempo fuera haciendo otras cosas, y quiero retomar un viejo proyecto, y tengo unas dudas que pueden resultar hasta basicas, pero es lo que tiene abandonar las cosas y luego querer retomarlas. Voy al grano.

Tengo una duda con la funcion de multiplicacion de GCM, mas bien con su sintaxis, aqui pongo una captura del pdf gcm.



Es una funcion simple, la variable Z pasa a ser un bloque de 128 bits de ceros, la variable X obtiene el valo de la variable V

A partir de hay empieza un for de 128 ciclos, depende del valor de los bit de V, en caso de ser 1, se hace un XOR entre las variables Z y V y el valor es reescrito a la variable Z. El ciclo sigue se comprueba el ultimo bit de la variable V, en caso de ser 0 se elimina un bit a la derecha y el valor es reescrito a la variable V, en caso de ser 1 se elimina un bit a la derecha y se hace un XOR al bloque V con la variable R, escrita mas arriba de la funcion lo siento no se puede observar en la captura, (( Se supone que el shift tiene preferencia sobre el XOR y se ejecuta antes, supongo.)) al finalizar se reescribe la variable V, se completaria el ciclo for y tendriamos el resultado final en la variable Z.

Parece que lo entiendo todo bien, esta funcion la he sacado de este paper:

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

Bien el problema lo tengo cuando leo la misma funcion pero en el paper del NIST, aqui la captura:



Bien aqui el problema que le veo es la sintaxis, no entiendo por que en las variables Z, V, tienen la variable i que esta hace de contador para los bits, se hace las operaciones a nivel de bits? En el paper de gcm se hacen a nivel de bloque, no se si me explico. A lo mejor es igual, solo que me esta liando la sintaxis., por otra parte sobre la duda del shift y el xor a la variable R, queda resuelta ya que se puede observar que tiene preferencia el shift.

Bueno esa es mi duda, la maldita variable i, simplemente sintaxis? Aqui documento:

https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf

Un saludo.

P.D: Las capturas me han quedado algo grandes y no he ajustado el tamaño, lo siento.

[kub0x]

Hola,

A lo mejor es igual, solo que me esta liando la sintaxis...

Así es, te has liado con la sintáxis Realmente es lo mismo en ambas descripciones, voy a proceder a explicarlo:

Partiendo del pseudocode siguiente:

if Yi = 1 then
Z <- Z xor V
end if

en cada iteracción se actualiza la Z si el bit/coeficiente Yi del polinomio en GF(2^128) es 1.

En cambio, en la segunda descripción, esta operación de Z xor V se realiza con subíndices dependiendo del número de iteracción.

Es decir, tomando como referencia la i-esima iteración:

si xi = 1 entonces Z_(i+1) <- Z_i xor V_i
si xi = 0 entonces Z_i <- Z_i (se mantiene constante)

Una diferencia notable es que en el primero utiliza el bit i-esimo del poly Y y en la segunda descripcion utiliza el i-esimo bit del poly X.

Resumiendo, en la primera descripción se abstienen de utilizar esos subindices para cada iteracción en las tuplas/polinomios/bloques Z y V y prefieren dejarlo de una manera general. En la segunda, prefieren incluir dichos subíndices. Muchas veces se hace así (personalmente lo hago), para más tarde introducir elementos como el Z_i, Z_i+1, Z_j, Z_k y demás.

De esta forma, al lector le cuesta menos asociar, incluso a nosotros mismos.

Un saludo.

[cpu2]

Una diferencia notable es que en el primero utiliza el bit i-esimo del poly Y y en la segunda descripcion utiliza el i-esimo bit del poly X.

Si, de hay tambien me surgieron las dudas, de que el nist pudiera a ver modificado la funcion y demas. De hay me salio la confusion de la i tambien.

Resumiendo, en la primera descripción se abstienen de utilizar esos subindices para cada iteracción en las tuplas/polinomios/bloques Z y V y prefieren dejarlo de una manera general. En la segunda, prefieren incluir dichos subíndices. Muchas veces se hace así (personalmente lo hago), para más tarde introducir elementos como el Z_i, Z_i+1, Z_j, Z_k y demás.

De esta forma, al lector le cuesta menos asociar, incluso a nosotros mismos.

Un saludo.

Vale, entonces como me temia solo era otro tipo de anotacion, ya decia yo, no es la primera vez que tengo problemas con sintaxis, desde mi punto de vista es mas comoda la primera, ya que no soy matematico, he visto formulas en otros sitios que ni entendia y verlas al programadas las he entendido a la primera.

Entiendo que los desarolladores de dichos algoritmos sean criptografos y matematicos con mucha experiencia, pero estaria mejor adaptar algunas formulas, para que sean mas entendible a un publico mas "informatico" por asi decirlo. Pero bueno esos ya son lloriqueos 

A ver cuando me pongo manos a la obra, con esto, lo bonito va ser optimizar la funcion ya que es muy tediosa de la forma que esta anotada, creo que ya tengo alguna idea, haciendo mascaras de bits y grupos, como hice con el AES en su dia. Pero tengo que verlo.

Con esto de la cuarentana me tiene desanimado  .

Gracias, saludos.

[kub0x]

Para más inri, en el primer esquema hace la rotación si el bit 127 del poly V es 0, sino hace rotacion con XOR.
En el segundo esquema, esto es reflejado en el bloque V_i+1, donde si el LSB (el último bit) es 0 entonces rotamos derecha, y si el LSB es 1 entonces rotamos V_i y Xoreamos con R para obtener V_i+1.

Otra forma sería hacerlo con lenguaje matemático, es decir, un sumatorio dividido en distintos casos. Pero no creo que sea muy útil en papers donde se toca la implementación.

De nada, cpu2. Cualquier duda ya sabes.

Saludos.

[cpu2]

Hola

Estado mirando el tema de la optimizacion, lo que tenia pensado no tiene mucho sentido ahora que lo pienso, por lo que he visto la mejor forma es haciendo tablas ya precomputadas, lo malo es el espacio que estas generan.

La informacion esta en el pdf gcm-spec.pfd apartado 4, lo he estado mirando voy a profundizarlo mejor, seguro que saldran preguntas.

Saludos.