Uma análise do sistema de criptografia GGH-YK
Charles F. de Barros∗,
L. Menasché Schechter,
Programa de Pós-Graduação em Informática, DCC, IM/iNCE, UFRJ,
21941-916, Rio de Janeiro, RJ
E-mail: [email protected], [email protected],
Resumo: Em 1997, Goldreich, Goldwasser e Halevi apresentaram ao mundo um sistema de
criptografia assimétrica baseado em reticulados. O sistema, que ficou conhecido como GGH, foi
dado como morto alguns anos depois, quando Nguyen apontou vulnerabilidades que comprometiam sua segurança. No entanto, em 2012, Yoshino e Kunihiro propuseram modificações que
trouxeram o GGH de volta à vida. Neste trabalho, discutiremos diversos aspectos da segurança
deste novo GGH, que chamaremos de GGH-YK, e também algumas possíveis melhorias que o
tornariam ainda mais seguro e eficiente.
Palavras-chave: Criptografia de Chave Pública, Reticulados
1
Problemas matemáticos, computadores quânticos e o futuro da
criptografia
A segurança dos sistemas de criptografia atuais é sustentada pela intratabilidade de dois problemas computacionais: a fatoração de inteiros no caso do RSA [8], e o cálculo de logaritmos
discretos no caso de sistemas baseados em curvas elípticas [6]. Nenhum dos dois pode ser eficientemente resolvido através de algoritmos clássicos conhecidos. Existe, contudo, uma ameaça
latente a todos esses sistemas: o computador quântico.
Diferente do computador clássico, cuja unidade fundamental de informação é o bit, o computador quântico opera com qubits (abreviação para quantum bits). Enquanto um bit só pode
assumir um valor, 0 ou 1, de cada vez, um qubit pode literalmente ser 0 e 1 ao mesmo tempo,
colapsando para um dos dois estados quando é medido. Não vamos entrar nos detalhes de como
os computadores quânticos funcionam, mas o fato é que eles são capazes de realizar certas tarefas
muito mais rapidamente do que os computadores clássicos, graças aos surpreendentes fenômenos
da Mecânica Quântica, como superposição e emaranhamento.
Apesar de estarmos longe de um computador quântico de uso geral (já existem protótipos de
uso restrito, como o DWave [2]), é bastante razoável esperar que dentro de algum tempo, décadas
talvez, possamos nos deparar com computadores quânticos em nossas casas. Se isto acontecer,
os sistemas atuais de criptografia deverão ser substituídos, porque existem algoritmos quânticos
que resolvem os problemas subjacentes a eles, como por exemplo o algoritmo de Shor [9].
O cenário, contudo, não é desesperador. Já existe um número razoável de alternativas,
incluindo sistemas baseados em códigos corretores de erros, funções hash e reticulados. Apesar
de serem clássicos (não empregam computação quântica em sua estrutura), tais sistemas são
considerados pós-quânticos, porque nem mesmo os computadores quânticos ofereceriam melhorias
nas tentativas de quebrá-los (pelo menos até onde se sabe) utilizando algoritmos conhecidos.
O primeiro sistema pós-quântico foi concebido mais ou menos na mesma época da criação
do RSA, no final da década de 70. Proposto por R. McEliece [5], o sistema utiliza como chaves
as matrizes geradoras de um código linear com uma estrutura especial. Essa estrutura, contida
∗
Bolsista da CAPES.
138
em uma matriz G que atua como chave secreta, é escondida entre duas matrizes, gerando a
chave pública W = SGP . Para encriptar uma mensagem m, deve-se codificá-la em um vetor
do código e acrescentar uma chave efêmera r, de norma relativamente pequena, gerando o vetor
c = mW + r.
A segurança do sistema depende da dificuldade computacional de recuperar o vetor mW
sem o conhecimento da estrutura do código, isto é, sem o conhecimento da matriz G. Por
outro lado, conhecendo-se a chave secreta, pode-se eliminar o vetor r (processo conhecido como
decodificação) e recuperar a mensagem original.
2
O sistema GGH: nascimento e "morte"
O sistema McEliece foi o primeiro a empregar chaves efêmeras, que introduzem aleatoriedade no
processo de encriptação. Inspirados por essa ideia, Goldreich, Goldwasser e Halevi conceberam
o GGH [4], em que a chave secreta é uma matriz B, que forma uma base de um reticulado com
razão de Hadamard alta (o que implica em vetores relativamente curtos e quase ortogonais). A
chave pública é uma outra base W para o mesmo reticulado, porém com razão de Hadamard
muito pequena. A matriz W pode ser obtida de duas maneiras: multiplicando-se B por uma
matriz unimodular U aleatória (ou por várias matrizes unimodulares), ou calculando-se a Forma
Hermitiana Normal (FHN) de B. A FHN é uma matriz triangular inferior, de entradas não
negativas, tal que a maior entrada de cada coluna situa-se na diagonal principal.
Uma mensagem m ∈ Zn é encriptada calculando-se o vetor c = mW + r, em que r é uma
perturbação aleatória (uma chave efêmera) de norma suficientemente pequena. Para decriptar c,
aplica-se o algoritmo de arredondamento de Babai [1] com a chave secreta, recuperando-se o vetor
mW e consequentemente a mensagem m. No entanto, se a norma de r não for pequena o bastante,
podem ocorrer erros na decriptação, impedindo que a mensagem original seja recuperada. A fim
de tornar a probabilidade de ocorrência de erros desprezível, deve-se estabelecer um parâmetro
σ suficientemente pequeno, de modo que |ri | ≤ σ para todo i = 1, · · · , n. Pode-se escolher
ri ∈ {−σ, σ} ou ri ∈ {−σ, · · · , σ}.
A segurança do GGH reside na intratabilidade do problema do vetor mais próximo (ou CVP,
abreviação para closest vector problem) quando não se conhece uma base boa (com razão de
Hadamard alta) do reticulado. Como a norma de r é pequena, mW é o vetor do reticulado
mais próximo de c, mas só é possível recuperá-lo com o conhecimento de B. A fim de resolver
o CVP conhecendo-se uma base ruim, deve-se resolver outro problema, que é o da redução de
base, que consiste na transformação de uma base ruim em uma base boa. Ambos os problemas
são considerados computacionalmente difíceis em dimensões arbitrárias.
A ideia empregada no GGH é essencialmente a mesma do sistema McEliece, adaptada a um
contexto diferente. Sem o conhecimento de uma certa estrutura especial do reticulado, expressa
na base boa B, é muito difícil recuperar o vetor mW a partir de c e W .
O GGH sofreu um duro golpe em 1999, quando Nguyen [7] apontou falhas graves no sistema.
Chegou-se ao ponto de um dos autores afirmar que o sistema estava morto [3]. Em primeiro
lugar, Nguyen ressaltou que, como a norma de r é sempre muito menor do que a norma de mW ,
a instância do CVP que se deve resolver para quebrar o sistema é mais fácil do que o CVP no
caso geral. Além disso, toda mensagem encriptada deixa vazar uma parte da mensagem original
se as entradas de r estiverem no conjunto {−σ, σ}.
Para atestar a validade de seus resultados, Nguyen resolveu quase todos os desafios do GGH
disponíveis na Internet. Cada desafio era composto de uma chave pública e uma mensagem
encriptada, e o objetivo era que esta mensagem fosse decriptada sem o conhecimento a priori da
chave secreta. O único desafio que resistiu ao ataque de Nguyen foi em dimensão 400, mas ainda
assim foi possível recuperar bits parciais da mensagem original.
Diante desses resultados, Nguyen argumentou que o sistema somente se tornaria seguro em
dimensões demasiadamente altas, mas isto também o tornaria inviável, porque as chaves exce-
139
deriam 2 MB de tamanho em dimensões maiores do que 4001 .
3
Melhorias recentes
Em 2012, Yoshino e Kunihiro [10] propuseram modificações que aparentemente eliminam as
vulnerabilidades apontadas por Nguyen. Neste novo GGH, que vamos chamar de GGH-YK,
o CVP deixa de ocupar posição central, dando lugar a um problema que, segundo os autores,
espera-se que seja mais difícil.
Para gerar a chave secreta no GGH-YK, são escolhidos dois parâmetros α e β, e então
calcula-se a matriz de ordem n
B = γI + P,
em que γ = αnβ e P é uma matriz aleatória tal que pi,j ∈ {−1, 0, 1}. É possível verificar que
as bases geradas desta forma possuem alta Razão de Hadamard. A chave pública W é obtida
calculando-se a FHN da matriz secreta.
O sistema conta com quatro parâmetros (σ, h, l, k) publicamente conhecidos, tais que σ < h
e
2nσ
l=d
c.
2σ + 1
Antes da encriptação, dois subconjuntos disjuntos de índices S e T são escolhidos aleatoriamente,
de modo que #T = n − l e #S = k. Uma mensagem m de l bits é codificada em um vetor
r ∈ Zn , tal que:
• bits 0 são codificados com entradas negativas, e bits 1 com entradas positivas;
• as entradas indexadas em T são nulas, ou seja, não codificam nenhum bit de m;
• as entradas indexadas em S recebem ±h;
• as demais entradas recebem valores aleatórios do conjunto {−σ, · · · , −1} ∪ {1, · · · , σ}.
O vetor r é encriptado calculando-se c = r − xW , em que x = brW −1 c. Diferente do esquema
original, o vetor r não possui norma tão pequena (devido às entradas ±h), por isso o vetor c não
é necessariamente o mais próximo de −xW .
Na decriptação, calcula-se o vetor u = cB −1 − dcB −1 c = rB −1 − drB −1 c. Multiplicando por
B, obtém-se a primeira aproximação para o vetor r, que vamos denotar por
r0 = uB = r − drB −1 cB.
A etapa final consiste em determinar o vetor erro e = drB −1 c. Os parâmetros do sistema são
escolhidos de tal forma que ej = 0 para todo j ∈
/ S, e ej ∈ {−1, 0, 1} para j ∈ S. É possível
mostrar a seguinte proposição, que estabelece o valor das entradas do vetor e, em função das
entradas correspondentes de r0 .
Proposição 3.1 Se rj0 < −h − k, então ej = 1; se rj0 > h + k, então ej = −1. Caso contrário,
ej = 0.
Uma vez determinado o vetor e, pode-se recuperar a codificação r da mensagem original, pois
r = r0 + eB.
1
Vale lembrar que o artigo de Nguyen foi escrito no final da década de 90. Com a atual tecnologia de
armazenamento de dados, 2 MB não podem ser considerados inviáveis, já que mesmo um cartão de memória
utilizado em aparelhos de celular pode facilmente exceder 2 GB de capacidade.
140
4
Resultados e discussões
A primeira observação que fazemos é em relação aos cálculos de matrizes inversas no GGH-YK,
mostrando que é possível realizar todas as operações com aritmética de números inteiros. Em
primeiro lugar, o vetor x = brW −1 c corresponde à parte inteira da solução do sistema yW = r.
Este sistema pode ser resolvido de forma direta, pois W é diagonal inferior. Assim, temos
P
rj − i>j wi,j ri
c,
xj = b
wj,j
para j = n, · · · , 1. Além disso, na decriptação, a inversa da chave secreta é calculada resolvendose o sistema XB = dI, em que d é o determinante de B. Pela Regra de Cramer, todas as
entradas de X são inteiras. Assim, calcula-se o vetor
r0 = d(cB −1 − dcB −1 c)B = d(r − drB −1 c)B.
As entradas de e = drB −1 c são determinadas comparando-se as entradas de r0 com d(h + k) e
d(−h − k), de modo similar à proposição 3.1. Uma vez determinado o vetor e, faz-se r0 + eB e o
resultado é dividido por d, obtendo-se o vetor r.
A segunda observação diz respeito aos parâmetros do sistema. Para que a decriptação funcione, os autores estabelecem algumas condições que devem ser satisfeitas pelas entradas da matriz
A = B −1 e pelos parâmetros (n, σ, h, k, γ). Mais especificamente, exige-se que
1
γ
2
|ai,j | < 2
γ
σ 2kh 2nσ
1
+ 2 + 2 <
γ
γ
γ
2
|ai,i | ≤
(1)
(2)
(3)
Constatamos que a condição (1) falha com frequência, mas isto não impede que a decriptação
funcione corretamente, porque a condição (3) é justa demais. De fato, a condição (3) pode ser
substituída por
1 2σ(k + 1)
σ 2kh 2nσ
+ 2 + 2 < +
(4)
γ
γ
γ
2
γ2
Em geral, escolhe-se um valor pequeno para o parâmetro σ. No entanto, a equação (4) nos diz
que valores consideravelmente maiores são permitidos, tanto para σ quanto para h. Na verdade,
nem mesmo é necessário que σ seja pequeno, podendo ser até da mesma magnitude que h. Em
nossos testes, conseguimos decriptar com sucesso utilizando parâmetros n = 400, σ = 512 e
h = 513. Tais valores são consideravelmente grandes em comparação com a sugestão dos autores
de utilizar σ = 3 e h = 27 na mesma dimensão.
A utilização de parâmetros maiores torna ainda mais difícil um ataque por força bruta, pois
aumenta o número de codificações possíveis para uma mesma mensagem, que é dado por
n
l l−k
N=
σ .
n−l k
Com os parâmetros que testamos, o valor de N obtido é da ordem de 23205 , enquanto os parâmetros sugeridos pelos autores resultam em N da ordem de 21165 .
Com a norma do vetor r podendo assumir valores consideravelmente grandes, a segurança do
GGH-YK deixa de ter qualquer relação com a intratabilidade do CVP. Ainda assim, a redução
de base continua desempenhando um papel central, porque recuperar a chave secreta é tão difícil
quanto reduzir a chave pública.
141
Além disso, conseguimos introduzir um pouco mais de aleatoriedade na codificação das mensagens, atribuindo às entradas de r indexadas no conjunto S valores no conjunto
{−h, · · · , −σ − 1} ∪ {σ + 1, · · · , h}
em vez de {−h, h}. Com esta escolha, o número de codificações possíveis para uma mesma
mensagem aumenta para
n
l
N=
(h − σ)k σ l−k .
n−l k
Uma peculiaridade foi observada durante a execução de nossos testes. A chave pública, que
é obtida pelo cálculo da FHN da chave secreta, assume na maioria das vezes a forma abaixo:


w1 0 0 · · · 0
 w2 1 0 · · · 0 




W =  w3 0 1 · · · 0 
 ..
.. .. . .
. 
 .
. .. 
. .
wn 0 0 · · · 1
com entradas grandes na primeira coluna, diagonal principal unitária e demais entradas nulas.
Com isto, a mensagem encriptada tem apenas a primeira entrada não nula, pois
P
r1 − j>1 wj rj
−1
x = brW c = b
c, r2 , · · · , rn ,
w1
e consequentemente
xW = (hx, wi, r2 , · · · , rn ),
em que w = (w1 , · · · , wn ). Portanto,
c = r − xW = (r1 − hx, wi, 0, · · · , 0).
Não sabemos se esta peculiaridade compromete a segurança do sistema, mas em caso negativo
ela poderia ser explorada para otimizar a encriptação, substituindo o cálculo de matrizes pelo
cálculo de vetores. Teríamos ainda a vantagem de poder armazenar a chave pública como um
vetor, contendo apenas as entradas da primeira coluna, e enviar a mensagem encriptada como
um número em vez de um vetor.
Referências
[1] L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica,
v. 6, n. 1, p. 1–13, 1986.
[2] DWave - The Quantum Computing Company. <http://www.dwavesys.com>
[3] O. Goldreich, Private communication. Jan, 1999.
[4] O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction
problems. Advances in Cryptology—CRYPTO ’97 (Santa Barbara, CA, 1997), Lecture Notes
in Computer Science, v.1294, p. 112–131, Springer, Berlin, 1997.
[5] R. J. McEliece, A public-key cryptosystem based on algebraic number theory. Technical
report, Jet Propulsion Laboratory, DSN Progress Report, p. 42-44, 1978.
[6] V. S. Miller, Use of ellyptic curves in cryptography. Lecture Notes in Computer Sciences,
218, Advances in cryptology - CRYPTO 85, p. 417-426, 1986.
142
[7] P. Nguyen, Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto
’97. Proceedings of Crypto ’99. Lecture Notes in Computer Science, v. 1666, p. 288–304,
IACR, Springer-Verlag, 1999.
[8] R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key
cryptosystems. Communications of the ACM, v. 21, p. 120-126, 1978.
[9] P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms
on a Quantum Computer, SIAM Journal on Computing, v. 26, n. 5, p. 1484–1509, 1997
[10] M. Yoshino, N. Kunihiro, Improving GGH Cryptosystem for Large Error Vector. International Symposium on Information Theory and its Applications, 2012.
143