Transformação Afim na Criptografia

Uma transformação afim é uma transformação entre dois espaços afins $A$ e $B$. Essa transformação, ou mapeamento, consiste numa transformação lineal em $A$ somado de um vetor $b \in B$. Ou seja: $$S(x)=Tx + b.$$ No campo da criptografia post-quântica as transformações afins são usadas para ocultar a chave pública dos sistemas de cifração baseados em multivariados.

Para os envolvidos na área é de importância saber lidar com as diferentes representações de uma transformação afim. Neste post apresentarei essas representações e mostrarei como converter uma para a outra. Seja $\mathbb{F}$ um corpo finito com $q$ elementos e $\mathbb{E}$ uma extensão de grau $n$ do corpo $\mathbb{F}$. Seja $S:\mathbb{F}^n\rightarrow \mathbb{F}^n$ uma transformação afim.

Definição 1: Seja $0\leq i < n$ e $A,B_i \in \mathbb{E}$. Então nós chamamos o polinômio $S(X)=\sum_{i=0}^{n-1}B_i X^{{q}^i}+A$ a representação de uma só variável da transformação afim $S$.

Definição 2: Seja $M_S \in \mathbb{F}^{n\times n}$ uma matriz e $v_s \in \mathbb{F}^n$ um vetor. Então nos chamamos $S(x):=M_Sx+v_s$, a representação matricial da transformação afim $S$ .

Definição 3: Seja o espaço vetorial $\mathbb{F}^n$. Então nós chamamos $\phi:\mathbb{E}\rightarrow \mathbb{F}^n$ com $\phi(a):=b$ e $b_i=a_{i-1}$ de bijeção canônica.

Teorema: Uma transformação afim, com $v=0$ na representação de uma só variável pode ser transformada eficientemente na sua representação matricial.

Prova: Definamos $e_i \in \mathbb{F}^n$ com $1\leq i \leq n$, com um $1$ no seu i-th coeficiente e zero no restante. Vamos a mostrar que a coluna $k$ dessa matriz é dada pela seguinte fórmula: $M_k=\phi(S(\phi^{-1}(e_k))).$ Vamos a definir $P(X):=\sum_{i=0}^{n-1}B_i X^{{q}^i}$. Da álgebra conhecemos que o corpo $\mathbb{F}^n$ é também um espaço vetorial sobre o corpo $\mathbb{F}$. Esse espaço vetorial tem a base $V=\{t^0, t^1, t^2,\ldots,t^{{n-1}}\}.$ Vamos a representar os coeficiente de $P(X)$ como  $B_i =\sum_{j=0}^{n-1}b_{ij} t^j$ e a variável $X=\sum_{k=0}^{n-1}X_{k}t^k$. Substituindo esses valores em $P(X)$ temos $$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} t^j(\sum_{k=0}^{n-1}X_{k}t^k)^{{q}^i},$$
Usando o teorema binomial e reduzindo temos
$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}t^{j+k{{q}^i}},$$

Escrevendo $t^{j+k{{q}^i}}$ usando a base $V$ temos $t^{j+k{{q}^i}} = \sum_{m=0}^{n-1}c_{ijkm}t^m$. Por tanto:

$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k} \sum_{m=0}^{n-1}c_{ijkm}t^m$$
$$P(X) =  \sum_{m=0}^{n-1}\underline{\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}c_{ijkm}}_{E}t^m$$
Por outro lado, escrevendo  $\phi(S(\phi^{-1}(e_k)))$ usando a base $V$ temos que esta é igual a: $\phi(S(\phi^{-1}(e_k)))=(\sum_{i,j}^{n-1}b_{i,j}c_{ijk0}, \cdots, \sum_{i,j}^{n-1}b_{i,j}c_{ijk(n-1)})$. Por fim, veja que $E_m = (\phi(S(\phi^{-1}(e_1)))[m],\cdots,\phi(S(\phi^{-1}(e_{n-1})))[m])^{T}*(X_1,\cdots, X_{n-1}).$

No caso de transformação afim com $v \neq 0$ então se tem que v:=$M_k=\phi(S(\phi^{-1}(0)))$ e as colunas de $M$ são $M_k=\phi(S(\phi^{-1}(e_k)))-v.$

Esquema de Firma Digital Pos Cuántico Lamport-Diffie

Este esquema de firma digital fue propuesto en el año de 1979. Es uno de los primeros en ser estudiados dentro de los esquemas de firma digital que se consideran resistentes ataques cuánticos dada su simplicidad para entender. A continuación describiré los algoritmos usados tanto para la generación de llaves como para el proceso de firma y verificación.

Generación de Llaves:
Escoger dos funciones

1. Una función de Mano Única: $$f:\{0,1\}^n \rightarrow \{0,1\}^n$$
2. Una función Hash $$g:\{0,1\}^{*}\rightarrow \{0,1\}^n$$

La llave  de firma, X, consiste de $2n$ cadenas de bits de tamaño $n$ elegidas de forma aleatoria uniformemente.
$$X=(x_{n-1}[0], x_{n-1}[1],\cdots,x_0[0],x_0[1])\in \{0,1\}^{n,2n}$$
La llave de verificación, Y, es:
$$Y=(y_{n-1}[0], y_{n-1}[1],\cdots,y_0[0],y_0[1])\in \{0,1\}^{n,2n},$$
donde $$y_i[j] = f(x_i[j]).$$

Firma:
Un documento $$M\in \{0,1\}^{*}$$ es firmado usando la llave X, usando $$d=g(M)=(d_{n-1},\cdots,d_0)$$ como $$\sigma = (x_{n-1}[d_{n-1}],\cdots,x_{0}[d_0])\in \{0,1\}^{n,n}$$
Verificación:
Para verificar $\sigma$ el verificador calcula g(M) y verifica si
$$(f(\sigma_{n-1}),\cdots,f(\sigma_0))=(y_{n-1}[d_{n-1}],\cdots,y_0[d_0]).$$

La seguridad de este esquema esta basada en dos nociones de seguridad: resistencia a pre-Imagen que presentan las funciones de mano única y la resistencia a colisiones que presenta una función hash criptográfica. Como ya vimos justamente el esquema Diffie-Lamport usa una función de mano única y una función hash. Funciones hash y funciones de mano única solo admiten ataques genéricos contra las dos nociones de seguridad mencionada. Para ataques contra la noción de resistencia a colisiones, usando un computador clásico, se usa Ataque de Cumpleaños el cual tiene complejidad O(2^{n/2}) de encontrar colisiones con probabilidad 1/2. Para ataques contra la noción de resistencia a pre-imagen, usando un computador clásico, se usa fuerza bruta, la cual en este caso, tiene complejidad de O(2^{n/2})  de encontrar pre-imagen con probabilidad 1/{2^{n/2}}. En el caso de uso de computadores cuánticos para crear ataques contra estas nociones de seguridad lo mejor que se pueda usar es el algoritmo de Groover. Este algoritmo, adaptado para estos ataques, tiene complejidad de O(2^{n/3}) con probabilidad 1/2 de encontrar colisiones y complejidad O(2^{n/3}) de encontrar pre-imágenes con probabilidad  1/{2^{n/3}}, [1,pag 90]. Es por eso que se dice que este esquema de firma digital, con sus limitaciones, es una alternativa para esquemas basados en problemas de la teoría de números como factorización de números grandes y el problema de logaritmo discreto.

[1] Johannes; Dahmen, Erik, eds. (2009). Post-quantum cryptography. Springer

Sistema Demostrablemente Seguro

Hace ya algunos dias que estoy queriendo dejar en claro algunos conceptos de seguridad que ya había aprendido y que por el paso del tiempo estaban confusos. Esos conceptos por ejemplo son nociones de seguridad, modelos de ataque, seguridad demostrable etc. Como siempre, lo que entiendo después de la lectura intentó escribirlo como se puede ver en mis entradas Propiedad de la Indistinguibilidad en Criptosistemas, Modelos de Ataque.

Siguiendo con la recordación, en esta entrada escribo un resumen acerca del concepto sistema demostrablemente seguro (provably secure).

Dado un criptosistema como podemos probar su seguridad?

• Tratando de montar un ataque
• Si el ataque fue encontrado entonces el criptosistema no es seguro.
• Si el ataque no fue encontrado no se puede decir nada acerca de la seguridad del criptosistema.
• Probando que no existe ataque bajo algunas asunciones.
• Publicar la verificabilidad de la prueba
• Ataque encontrado, entonces las asunciones fueron falsas

Como hacer esa prueba bajo asunciones?

• Describir  un criptosistema y sus modos operacionales,
• Formalmente definir la noción de seguridad a lograr = (objetivo que el atacante atacaria + modelo de ataque ). Ejm: IND-CCA2, IND objetivo e CCA2 modelo de ataque.
• Realizar asunciones computaciones, (problema factoración, problema logaritmo discreto, dureza de la decodificación de Códigos de Goppa Binário, etc).
• Exhibir una reducción entre un algoritmo que rompe la noción de seguridad y uno que rompe la asunción computacional. Ejemplo (RSA is reducible para OW-CCA2(S)).

¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!

Propiedad de la Indistinguibilidad en Criptosistemas

Actualmente esta propiedad la poseen la mayoría de criptosistemas. Un criptosistema es denominado seguro en términos de indistinguibilidad si, dado el par de textos planos M0, M1 y el texto cifrado C, no existe atacante que tenga probabilidad mayor al que tendría un atacante con la probabilidad 1/2, para poder afirmar si el texto cifrado C pertenece al cifrado de M0 o M1.

Indistinguibilidad bajo CPA (IND-CPA):

Para criptosistemas asimétricos esta propiedad es definida como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:

1. El desafiador crea sus claves publica PK y privada SK;
2. El atacante puede usar PK para cifrar los mensajes de texto plano que el desee;
3. El atacante envía para el desafiador los textos planos M0 y M1;
4. El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);
5. El atacante es libre de hacer nuevas cifraciones. Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).

Un sistema es dicho IND-CPA seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.

Indistinguibilidad bajo CCA (IND-CCA/IND-CCA2):

Al igual que en la propiedad anterior, esta es definida como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:

1. El desafiador crea sus claves publica PK y privada SK;
2. Dado que el atacante tiene acceso a PK entonces puede hacer cualquier número de cifraciones, así como también puede descifrar texto cifrados usando un oracle de deciframiento.
3. El atacante envía para el desafiador los textos planos M0 y M1;
4. El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);
5. El atacante puede realizar mas cifraciones si lo desea. Si el modelo de ataque del desafiador es:
1. CCA entonces el atacante no puede realizar mas decifraciones de textos cifrados, usando el oracle.
2. CCA2 entonces el atacante puede realizar mas decifraciones de textos cifrados, usando el oracle, excepto C.
6. Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).

Un sistema es dicho IND-CCA/CCA2 seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.

La indistinguibilidad bajo CPA (IND-CPA) es una propiedad que la poseen los sistemas denominados probadamente seguros. IND-CPA es equivalente a la propiedad de seguridad semántica en criptosistemas, por lo cual muchas veces esta equivalencia  es usado para pruebas criptográficas. Algunos sistemas criptográficos también ofrecen la indistinguibilidad bajo CCA (IND-CCA).

La indistinguibilidad contra ataques adaptativos para sistemas criptográficos de llave pública fue introducida por Rackoff and Simon.

Livraria LibMC

Introdução

Dentro dos sistemas criptográficos de chave pública existem alguns que, atualmente, têm se destacado devido ao fato de, aparentemente, resistirem aos ataques que são provenientes do uso dos computadores quânticos, formando, assim, uma família denominada de post-quantum cryptosystems. Estes sistemas criptográficos, em sua grande maioria, têm suporte matemático nos códigos códigos de Goppa binário, como apresentado por McEliece e Niederreiter. Neste post, apresento uma livraria para implementar os algoritmos de decodificação algébrica para códigos de Goppa binário com parâmetros $[n,k,d]$ suficientemente grandes. Para conseguir isto, desenvolvemos uma implementação híbrida, usando o CAS(computer algebra system) SAGE para os algoritmos de decodificação e algumas funções modificadas do software HyMES (feito em C) para a geração do polinômio síndrome (de forma randômica), que é uma das entradas para os algoritmos de decodificação. Caso a livraria não fosse usado para gerar o polinômio síndrome, randomicamente, a implementação apenas no SAGE ficaria, obviamente, muito limitada em tempo de decodificação, devido ao carácter simbólico do mesmo. 

Como usar

A livraria esta feita para ser usada em SAGE versão para 32 bits. Para instalar a livraria segue os passos:

1. Descarregar de aqui.
2. Descomprimir o arquivo zipeado.
3. Copiar o arquivo na pasta: local/lib/python/site-packages.
4. Reiniciar o SAGE.

Exemplo de uso

Veja que as entradas do gerador são: $m$ é o grau do polinômio $p(X)$ tal que $F = K/p(X)$, com $K = \mathbb{F}$$_2$, $n$ é o comprimento de cada palavra chave e delta é o grau do polinômio de Goppa. As saídas são: o Polinômio de Goppa, a matriz de teste de paridade do código gerado e o vetor codificado, ou seja $mG+e$.

Este trabalho foi desenvolvido no LNCC, sendo meus orientadores Renato Portugal e Nolmar Melo.