ads:
ANDR
´
E GUSTAVO DEGRAF UCH
ˆ
OA
DHA: UM ESQUEMA DE ACORDO DE
CHAVES BASEADO EM MAT RIZES
PARA O PROTOCOLO
DIFFIE-HELLMAN
Disserta¸c˜ao apresentada ao Programa de
P´os-Gradua¸c˜ao em Inform´atica da Pontif´ıcia
Universidade Cat´olica do Paran´a como requi-
sito parcial para obten¸c˜ao do t´ıtulo de Mes-
tre em Inform´atica.
Curitiba
2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ANDR
´
E GUSTAVO DEGRAF UCH
ˆ
OA
DHA: UM ESQU EMA DE
ACORDO DE CHAVES
BASEADO EM MATRIZES
PARA O PROTOCOLO
DIFFIE-HELL MAN
Disserta¸c˜ao apresentada ao Programa de
P´os-Gradua¸c˜ao em Inform´atica da Pontif´ıcia
Universidade Cat´olica do Paran´a como requi-
sito parcial para obten¸c˜ao do t´ıtulo de Mes-
tre em Inform´atica.
´
Area de Concentra¸c˜ao: Ciˆencia da Com-
puta¸c˜ao
Orientador: Marcelo Eduardo Pellenz
Co-orientador: Altair Olivo Santin
Curitiba
2007
ads:
Uchˆoa, Andr´e Gustavo Degraf
DHA: UM ESQUEMA DE ACORDO DE CHAVES BASEADO EM MA-
TRIZES PARA O PROTOCOLO DIFFIE-HELLMAN. Curitiba, 2007.
Disserta¸c˜ao - Pontif´ıcia Universidade Cat´olica do Paran´a. Programa de
P´os-Gradua¸c˜ao em Inform´atica.
1. Criptografia Assim´etrica 2. Protocolo de Acordo de Chaves 3. Matrizes
I.Pontif´ıcia Universidade Cat´olica do Paran´a. Cent ro de Ciˆencias Exatas e
Tecnologia. Programa de P´os-Gradua¸c˜ao em Inform´atica II - t
Dedico a minha disserta¸c˜ao de mestrado a
Deus todo poderoso Pai Eterno e para os
meus pais Sirlei e Raimundo, pela ajuda fi-
nanceira, ajuda moral, ajuda f´ısica, entre ou-
tras.
i
Agradecimentos
Agrade¸co aos meus pais pela paciˆencia, compreens˜ao, respeito, dedica¸c˜ao, conse-
lhos, ajuda financeira, aj uda moral e po r fazer com que eu pudesse realizar este mestrado.
Agrade¸co aos meus colegas de mestrado Tiago, Luis Renato, Jaime, Teig˜ao, Eucli-
des, Edson, entre outros colegas.
Agrade¸co a PUC-PR por ter me concedido a b olsa Marcelino Champagnat que fez
com que eu conseguisse fazer este mestrado.
Agrade¸co aos meus orientadores pela imensa ajuda na jornada do mestrado, pela
paciˆencia e compreens˜ao nos momentos mais cr´ıticos da minha pesquisa. Tamb´em agrade¸co
pelas referˆencias bibliogr´aficas que meus orientadores me passaram, as quais foram de
suma importˆancia na realiza¸c˜ao desta disserta¸c˜ao.
Agrade¸co ao professor doutor Carlos Alberto Maziero pelas aulas de Sistemas Ope-
racionais e o uso da Linguagem C em ambiente UNIX-like e pela imensa ajuda no ensino
do uso do editor de texto LaTex que foi utilizado para fazer esta disserta¸c˜ao.
Tamb´em agrade¸co a equipe de prof essores da academia Via Aventura p or terem me
ajudado a cuidar da sa´ude corporal atrav´es do esporte, http://www.viaaventura.com.br.
Agrade¸co em especial ao software livre LINUX, por ter tornado poss´ıvel o desenvol-
viment o do DHA3 e das an´alises matem´aticas. E tamb´em devo lembrar dos criadores do
compilador para Linguagem C o GNU GCC e as bibliotecas GNU GMP e GNU MPFR.
Com Rela¸c˜ao a MPFR gostaria de agradecer a um dos criadores por ter me auxiliado
durante minha pesquisa que ´e o PHd Vicent Lefevre.
ii
Sum´ario
Agradecimentos ii
Sum´ario iii
Lista de Figuras vi
Lista de Tabelas vii
Lista de S´ımbolos viii
Lista de Abrevia¸c˜oe s x
Resumo xi
Abstract xii
Cap´ıtulo 1
Introdu¸c˜ao 1
1.1 Contextualiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Defini¸c˜ao do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.1 Objetivos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 Objetivos Espec´ıficos . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Contribui¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6 Organiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Cap´ıtulo 2
Fundamentos de Criptografia 6
2.1 Conceitos B´asicos Sobre Seguran¸ca . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Sistemas Criptogr´aficos Cl´assicos . . . . . . . . . . . . . . . . . . . 8
2.1.2 Defini¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Criptoan´alise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.4 Sistemas Criptogr´aficos Sim´etricos . . . . . . . . . . . . . . . . . . 10
iii
2.1.5 Sistemas Criptogr´aficos de Chave P´ublica . . . . . . . . . . . . . . . 12
2.1.6 Fun¸c˜oes de Hash Criptogr´aficas . . . . . . . . . . . . . . . . . . . . 14
2.2 DLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Busca Exaustiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Algoritmo baby-step giant-step . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.1 Exemplo do BSGS . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Algoritmo Pohlig-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.1 Exemplo Pohlig-Hellman . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Algoritmo Index-Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6.1 Exemplo: Index-Calculus em Z
∗
p
. . . . . . . . . . . . . . . . . . . . 21
2.7 Discuss˜ao sobre DLPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8 Matrizes Sobre Z
∗
p
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.9 Conclus˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Cap´ıtulo 3
Protocolos de Acordo de Chave 26
3.1 Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Protocolo MTI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Protocolo Needham-Schroeder . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 CRTDH e G r upos Seguros de Comunica¸c˜ao . . . . . . . . . . . . . . . . . 32
3.6 SPAKE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.7 S-3PAKE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.8 Sistema Criptogr´afico baseado em DLP γ = α
a
β
b
. . . . . . . . . . . . . . 37
3.9 Protocolo Matrix Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.10 Protocolo de Acordo de Chaves Baseado em Matrizes Inversas . . . . . . . 40
3.11 Conclus˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Cap´ıtulo 4
Protocolo de Acordo de Chaves Criptogr´aficas DHA 43
4.1 Contextualiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Protocolo DHA1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 Exemplo Num´erico DHA1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.1 An´alise de Seguran¸ca . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 DHA2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5 Exemplo Num´erico DHA2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
iv
4.5.1 An´alise de Seguran¸ca DHA2 . . . . . . . . . . . . . . . . . . . . . . 48
4.6 Protocolo de Acordo de Chaves DHA3 . . . . . . . . . . . . . . . . . . . . 49
4.7 Exemplo Num´erico DHA3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.8 An´alise de Seguran¸ca DHA3 . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.9 Aspectos da Implementa¸c˜ao do DHA3 . . . . . . . . . . . . . . . . . . . . 53
4.10 An´alise de Desempenho DHA3 . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.11 Considera¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.12 Conclus˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Cap´ıtulo 5
Conclus˜ao 59
Referˆencias Bibliogr´aficas 61
v
Lista de Figu ras
Figura 2.1 Sistema Criptogr´afico Sim´etrico. . . . . . . . . . . . . . . . . . . . . 11
Figura 2.2 Sistema Criptogr´afico Assim´etrico. . . . . . . . . . . . . . . . . . . 14
Figura 2.3 Funcionamento fun¸c˜ao de Hash . . . . . . . . . . . . . . . . . . . . 15
Figura 2.4 Compara¸c˜ao entre os M´etodos BSGS e NFS . . . . . . . . . . . . . 23
Figura 3.1 Protocolo de acordo de chave Diffie-Hellman. . . . . . . . . . . . . . 27
Figura 3.2 Protocolo de acordo de chave El Gamal. . . . . . . . . . . . . . . . 28
Figura 3.3 Protocolo de acordo de chave MTI/A0. . . . . . . . . . . . . . . . . 29
Figura 3.4 Funcionamento do protocolo Needham-Schroeder. . . . . . . . . . . 31
Figura 3.5 Funcionamento do protocolo SPAK E. . . . . . . . . . . . . . . . . . 35
Figura 3.6 Funcionamento do protocolo S-3PAKE. . . . . . . . . . . . . . . . . 36
Figura 3.7 Protocolo de acordo de chave baseado em DLP γ = α
a
β
b
. . . . . . . 38
Figura 3.8 Protocolo Matrix Rings. . . . . . . . . . . . . . . . . . . . . . . . . 39
Figura 3.9 Acordo de Chaves com Matrizes Inversas. . . . . . . . . . . . . . . . 40
Figura 4.1 Protocolo de acordo de chave DHA1. . . . . . . . . . . . . . . . . . 45
Figura 4.2 Protocolo de acordo de chave DHA2. . . . . . . . . . . . . . . . . . 47
Figura 4.3 Protocolo de acordo de chave DHA3. . . . . . . . . . . . . . . . . . 50
vi
Lista de Tabelas
Tabela 2.1 Fun¸c˜oes de hash-especifica¸c˜oes . . . . . . . . . . . . . . . . . . . . . 16
Tabela 2.2 Algoritmos cl´a ssicos para resolver DLP . . . . . . . . . . . . . . . . 23
Tabela 3.1 Variantes do MTI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Tabela 3.2 Compara¸c˜ao dos Protocolos . . . . . . . . . . . . . . . . . . . . . . 41
Tabela 4.1 Compara¸c˜ao dos protocolos DH e DHA3 . . . . . . . . . . . . . . . 57
vii
Lista de S´ımbolos
Γ Gerador base do DHA3
υ Vetor base do DHA3
P Espa¸co de Texto Claro
C Espa¸co de Texto Cifrado
K Espa¸co da Chave
D Espa¸co de Dados Decifrados
ε Fam´ılia de Fun¸c˜oes Criptogr´aficas
e Chave P´ublica
∈ Pertence `a
d Chave Privada
c Contante arbitr´aria
k Contant e arbitr´aria
p N´umero primo
α Gerador DH, ElGamal, MTI
Z
∗
p
Numeros inteiros positivos n˜ao nulos - Campo Finito
x Expoente arbitr´ario
y Expoente arbitr´ario
a Expoente arbitr´ario
k
i
Parˆametro CRTDH
D
p
Parˆametro CRTDH
gcd Greatest Commom Divisor
GK Chave do Grupo do CRTDH
U U novo membro
pw Senha Secreta no SPAKE
G Grupo finito c´ıclico
M, N N´umeros aleat´orios pertencentes a G
h() Fun¸c˜ao de hash
S Servidor Confi´avel
viii
pw1 Senha no S-3PAKE
pw2 Senha no S-3PAKE
X||Y Concatena¸c˜ao entre X e Y
GL
n
Grupo de matrizes sobre campo finito
r Expoente arbitr´a rio
η Magnitude do n´umero primo
t Bit mais significante
I
n
Matriz identidade
A
n×n
Vari´avel matricial
⊕ Opera¸c˜ao bin´a r ia XOR
ix
Lista de Abrevia¸c˜oes
DLP Discrete Logarithm Pro blems
DH Diffie-Hellman
DES Data Encryption Standard
NIST National Institute of Standards and Technology
SSL Secure Socket Layer
3DES Triplo DES
CDC Cifra D ecifra Cifra
IDEA International Data Encryption Algorithm
PGP Pretty Good Privacy
NSA National Security Agency
MIT Instituto Tecnol´ogi co de Massachusetts
PKP Public Key Partners
BSGS Baby-Step Giant-Step
TTP Trusted Third Party
SGC Secure Group of Communication
CRT Chinese Remai nder Theorem
LCM Least Com mom Multiple
SPAKE Simple Password - based Encrypted Key Exchange Protocol
S-3PAKE Simple Three-Party Key Excha nge Protocol
NFS Number Field Sieve
IC Index Calculus
AES Advanced Encryption Standard
x
Resumo
Neste tr abalho ´e proposto um protocolo sem autentica¸c˜ao das partes para acordo de cha-
ves criptogr´aficas de forma segura, baseado no protocolo Diffie-Hellman. Atualmente os
principais protocolos para acordo de chaves como Diffie-Hellman e ElGamal trabalham
com opera¸c˜oes exponenciais modulares e a complexidade de tais protocolos est´a baseada
na dificuldade em resolver problemas de logaritmos discretos DLPs. O protocolo proposto
nesta disserta¸c˜ao se baseia no protocolo Diffie-Hellman, mas utiliza como gerador base
uma matriz e um vetor, fazendo com que a complexidade de quebra de tal prot ocolo seja
baseada na solu¸c˜ao de um DL P e com complexidade de solu¸c˜ao muito maior que a apre-
sentada pelo Diffie-Hellman. Com base na an´alise de complexidade do protocolo DHA1 e
do DHA2, melhorias foram propostas para aumentar a dificuldade de quebra do protocolo
DHA1 gerando assim, uma terceira proposta chamada DHA3. O uso de matrizes, veto-
res e opera¸c˜oes sobre GL(n) ´e respo ns´avel por dificultar a criptoan´alise. Devido ao uso
de matrizes e vetores o m´etodo proposto pode trabalhar com n´umeros primos de menor
magnitude na s opera¸c˜o es modulares, diminuindo assim o custo computacional sem no
entanto diminuir a complexidade de quebra. Um prot´otipo foi desenvolvido como prova
de conceito para mostrar a viabilidade da proposta. Neste prot´otipo constatou-se que o
DHA3 levou cinco vezes menos tempo de processamento que o DH cl´assico, para gerar a
chave de sess˜ao e ainda tr ansmitiu pelo menos metade de informa¸c˜ao que o DH.
Palavras-chave: Criptografia Assim´etrica, Protocolo de Acordo de Chaves, Matrizes
xi
Abstract
In this work is proposed an annonimous cryptographic key agreement protocol by se-
cure way based on Diffie-Hellman protocol. Actually key agreement pro t ocols like Diffie-
Hellman, ElGamal and other work with modular exponentiation operations and the com-
plexity of such protocols are based on apparent difficult to deal DL P (Discrete Logarithm
Problems). The proposed protocol in this master degree thesis is based on Diffie-Hellman,
but uses as base generator a matrix and a vector, doing with the complexity to solve such
protocol be based on DLP solution, but much more complexity than was shown by Diffie-
Hellman. Based on ccomplexity analysis of DHA1 and DHA2, improvements were propo -
sed to difficult the criptanalisys of DHA1 generating thus, a third proposal called DHA3
Protocol. The usage of matrices, vectors and operations under GL(n) are responsable by
difficulting the criptanalisys. Due to using matrices and vectors the propo sed method can
work with prime numbers with small precision under modular operaions, decreesing thus
the computational cost without decreesing the complexity to break. One prototype was
developed as concept proof to show the proposal viability. In this prototype it was cons-
tacted that DHA3 taken about five less computer processing time tha n DH to generate
the session key and also transmited at least half information than DH.
Keywords: Assymetric Cryptography, Key Agreement Protocols, Matrices
xii
1
Cap´ıtulo 1
Introdu¸c˜ao
As primeiras redes de computadores eram baseadas em cabeamento, de forma que
dispositivos m´oveis como Handhelds e Notebooks, tinham que acessar tais redes ou por
acesso discado usando a linha telefˆonica o u ainda em ambientes corporativos atrav´es dos
“cabos de rede”. Em poucos a nos, tornou-se poss´ıvel a comunica¸c˜ao dos computadores
atrav´es de redes baseadas em tecnologias de comunica¸c˜ao sem fio que veio possibilitar uma
maior mobilidade aos dispositivos m´oveis acessarem a rede sem precisar para isto estar
fisicamente conectados a algum tipo de cabeamento. Contudo, com a implementa¸c˜ao de
redes sem fio, problemas de seguran¸ca antes n˜ao existentes nas redes cabeadas tradicionais
tornaram-se poss´ıveis em meios sem fio devido ao meio de acesso ser o ar e a f orma como
os dipositivos s˜ao distribu´ıdos em redes sem fio.
1.1 Contextualiza¸c˜ao
Atualmente, as t´ecnicas criptogr´aficas assumem um papel importante ao proteger
os dados sendo transmitidos entre os n´os de uma rede sem fio. Existem diversas tecno-
logias que proporcionam a comunica¸c˜ao sem fio como: redes sem fio baseadas no padr˜ao
IEEE 802.11, redes de sensores, redes baseadas no padr˜ao Bluetooth, entre outras. O
grande desafio apresentado por essas redes ´e qual algoritmo criptogr´afico dever´a ser uti-
lizado e uma vez escolhido, como distribuir/compartilhar a chave criptogr´afica utilizada
pelo algoritmo. Pois, devido ao meio sem fio utilizar o ar como meio de transporte das
informa¸c˜oes as chaves criptogr´aficas compartilhadas/distribu´ıdas podem ser capturadas
por terceiros que podem ser elementos maliciosos `a rede sem fio implantada.
Um modo espec´ıfico de opera¸c˜a o de r edes sem fio, o modo Ad-hoc, s˜ao redes sem
fio e sem infra-estrutura pr´evia, por exemplo: um grupo de computadores (n´os da rede)
comunicando-se via rede sem fio sem ter acesso a um servidor que realize o interfaceamento
2
entre a rede sem fio e algum tipo de provedor de acesso a Internet. Este modo de opera¸c˜ao
imp˜oe alguns desafios para a ´area de segura¸ca como: realizar a autentica¸c˜ao dos n´os
sem a existˆencia de um servidor centralizado; implementar-se um canal de comunica¸c˜ao
seguro, sem ter a garantia de que os n´os pertencentes `a rede s˜ao confi´aveis, como realizar
a distribui¸c˜a o de chaves criptogr´aficas em tais ambientes sem que terceiros maliciosos
venham a capturar tais chaves; a utiliza¸c˜ao de algoritmos criptogr´aficos que n˜ao causem
alto custo computacional devido ao fat o que geralmente os n´os de uma rede no modo
Ad-hoc po ssuem limita¸c˜ao de consumo de bateria.
Com o aumento do uso de dispositivos com conex˜ao sem fio impˆos-se um desafio
adicional nos protocolos criptogr´aficos, devido `a facilidade para capturar pacotes transmi-
tidos entre dois n´os sobre um canal de r´adio. Em redes sem fio ad-hoc um n´o pode tamb´em
se tornar um roteador para encaminhar pacotes de um n´o para outro n´o qualquer. Al´em
disso, a implementa¸c˜ao de algoritmos criptogr´aficos baseados em chave p´ublica, numa rede
sem fio ad-hoc n˜ao ´e uma tarefa simples de ser executada, uma vez que tal abordagem
necessita de um servidor centralizado para g erenciar as chaves p´ublicas utilizadas pelos
membros de tal rede [1].
Outra t´ecnica para prover seguran¸ca em redes sem fio ad-hoc ´e a t r av´es de algo-
ritmos criptogr´aficos baseados em chave sim´etrica, nos quais a chave secreta dever´a ser
compartilhada entre os n´os participantes. O problema de tal t´ecnica ´e a distribui¸c˜ao das
chaves, porque um n´o deve enviar a chave para outro, sem cifragem. Isto constitui uma
fraqueza, uma vez que a chave pode ser facilmente interceptada num meio sem fio. Um
modo de evitar tal pro blema ´e realizar a pr´e-distribui¸c˜ao da chave. Neste caso, os fa-
bricantes devem previamente instalar as chaves secretas pr´e-definidas nos dispositivos de
hardware [2]. A pr´e-distribui¸c˜ao de chaves restringe a possibilidade da escolha do tipo do
algoritmo de criptografia a ser usado, como tamb´em o tamanho da chave. Adicionalmente,
se um intruso tiver acesso f´ısico ao dispositivo m´ovel, as chaves pr´e- definidas podem ser
comprometidas.
1.2 Defini¸c˜ao do Problema
Os protocolos criptogr´aficos de acordo de chaves s˜ao baseados em sistemas sim´etricos
e/ou assim´etricos, sendo que existem ainda os que s˜ao “sem autentica¸c˜ao das partes” como
´e o caso do Diffie-Hellman-Merkle [3]. Tal protocolo ´e classificado como n˜ao tendo au-
tentica¸c˜ao das partes devido ao fato de que n˜ao h´a qualquer tipo de autentica¸c˜ao das
elemento s participantes da comunica¸c˜ao, ele a penas garante que a chave compartilhada
ser´a entregue com seguran¸ca ponto a ponto. Al´em disso, utiliza opera¸c˜oes exponenciais
3
modulares, que geralmente geram um custo computacional alto, mesmo que para isso
sejam utilizados algoritmos que aumentem a velocidade para calcular as exponencia¸c˜oes
[3].
1.3 Motiva¸c˜ao
No Cap´ıtulo 3 desta disserta¸c˜ao ser˜ao discutidos alguns trabalhos relacionados. O
Diffie - Hellman ´e um protocolo sem autentica¸c˜ao das partes para acordo de chaves que
utiliza opera¸c˜oes exponenciais mo dulares que necessita da gera¸c˜ao de um n´umero primo
com uma alta precis˜ao, em torno de 1024 a 2048 bits, para aumentar o tempo de crip-
toan´alise por DLP. As opera¸c˜oes de exponencia¸c˜ao que trabalham com n´umeros primos de
grande magnitude, geram um alto custo computacional. O protocolo proposto trabalha
com primos de magnitude menor do que a dos pro t ocolos tradicionais [3] [4]. O MTI
´e uma variante do Diffie-Hellman que tenta aumentar a complexidade adicionando dois
parˆametros extras (chaves p´ublicas). No entanto, utiliza o mesmo gerador base α que
permite a criptoan´alise por DLP. Algumas variantes do MTI necessitam do c´alculo da
inversa multiplicativa o que acarreta um custo computacional alto. O protocolo γ ≡ α
a
β
b
[5] tentou a umentar a complexidade da criptoan´alise definindo que seria necess´ario resol-
ver dois DLPs um para cada gerador, α e β. No entant o tal proposi¸c˜ao n˜ao era consistente
como demonstrado por [6]. Al´em disso, o protocolo acarreta no envio e processamento
do dobro de parˆa metros comparado ao DH. O SPAKE [7] utiliza uma senha com um uni-
verso de busca limitado, pois s˜ao caracteres dispo n´ıveis no teclado de um computador e
esta senha ´e previamente compartilhada entre os n´os que desejam estabelecer uma chave
de se¸c˜ao. Al´em de utilizar uma senha pr´e- estabelecida entre os n´os, ´e tamb´em baseado
em criptoan´alise por DL P, pois utiliza o mesmo gerador base, sendo suscept´ıvel a ataque
de “passphrase”, n˜ao t r azendo um aumento significativo para a complexidade de crip-
toan´alise. O protocolo S-3PAKE [7] prop˜oe uma melhoria no protocolo SPAKE ao dizer
que n˜ao necessita de um servidor de chaves p´ublicas, no entanto, tal protocolo requer
um servidor confi´avel que autentique os n´os participantes da comunica¸c˜ao. Tamb´em na
proposta do S-3PAKE cada n´o deve possuir uma senha compartilhada com o servidor
confi´avel, assim pode-se dizer que a melhoria supostamente definida pelos autores n˜ao ´e
de fato uma melhoria, pois simplesmente retirou-se a autoridade de um servidor de chaves
p´ublicas e passou para um servidor confi´avel. Al´em disso, este protocolo realiza muitas
trocas, o que ´e indesej´avel em ambientes com limita¸c˜oes nos canais de comunica¸c˜ao ou
mesmo limita¸c˜ao no consumo das baterias em dispositivos com baixo poder computacio-
nal. O protocolo Matrix Rings [8] foi o primeiro protocolo a propor o uso de matrizes como
4
gerador base para o aumentar a complexidade do DH, mas devido a o tipo da matriz gera-
dora ser n˜ao singular (admite inversa) tal m´etodo pode ser resolvido e sua complexidade
pode ser reduzida conforme descrito em [9].
1.4 Objetivos
1.4.1 Objetivos Gerais
• Estudar os sistemas criptogr´aficos sim´etricos e assim´etricos;
• Estudar e analisar os protocolos de acordo de chaves criptogr´aficas;
• Analisar os algoritmos baseados em problemas de logaritmos discretos (DLP);
• Estudar matrizes sobre campos finitos;
• Comparar e testar os algoritmos que realizam exponencia¸c˜ao;
1.4.2 Objetivos Espec´ıficos
• Criar um prot ocolo que n˜ao requer um servidor de chaves p´ublicas para realizar as
trocas;
• Produzir um protocolo que transmita menos informa¸c˜ao que o Diffie-Hellman;
• Estabelecer um protocolo que diminua o processamento computacional para gerar
os parˆametros pr´e-compartilhados;
• Desenvolver um protocolo que possua complexidade `a criptoanalise em tempo ex-
ponencial;
• Implementar um protocolo que utilize matrizes nos seus procedimentos com o intuito
de dificultar a criptoan´alise;
1.5 Contribui¸c˜ao
Nesta disserta¸c˜ao, ´e proposto um protocolo sem autentica¸c˜ao das partes para o
acordo de chaves criptogr´aficas baseado no prot ocolo cl´assico DH (Diffie-Hellman), sendo
que a complexidade para resolver tal prot ocolo est´a baseada na aparente intratabilidade
para resolver Logar´ıtmos Discretos (DLP). Foram implementadas duas prop ostas o DHA1
5
e o D HA2, mas ambas estas propostas podiam ser reduzidas ao caso do DH, com o objetivo
de realmente criar um protocolo mais robusto que o DH. Foi ent˜ao implementado o DHA3
que ´e a jun¸c˜ao do DHA1 e do DHA2. A modifica¸c˜ao realizada no DH feita pelo DHA3
´e a utiliza¸c˜ao de uma matriz quadrada Γ e um vetor υ como geradores base em vez do
α utilizado p elo DH. Devido a utiliza¸c˜a o deste par de elementos: uma matriz e um vetor
como geradores base, o protocolo DHA3 f az com que seja mais complexo o tempo de
resolu¸c˜a o comparado ao DH e permitindo apenas que o s algoritmos para resolver DLPs
com complexidade de resolu¸c˜ao O(
√
p) possam encontrar uma solu¸c˜ao. O utros m´etodos
ainda necessitam um estudo mais profundo, al´em disso, o DHA3 leva 5 vezes menos tempo
de processamento que o DH e transmite pelo menos 50% menos informa¸c˜ao que o DH a
cada troca de mensagens.
O protocolo apresentado nesta disserta¸c˜ao pode ser utilizado tanto em redes no
modo Ad-hoc como em outras configura¸c˜oes de redes. Este protocolo visa aumentar a
complexidade do DH, visa utilizar n´umeros primos menores, e visa tra nsmitir menos
informa¸c˜ao que o DH, de forma a ser mais eficiente que outros protocolos de acordo de
chaves at´e ent˜ao criados e utilizados. Visa tamb´em garantir a entrega segura da chave
compartilhada e produzir menos custo computacional para os dispositivos ao utiliz´a-lo.
1.6 Organiza¸c˜ao
Esta disserta¸c˜ao est´a organizada da seguinte forma: no Cap´ıtulo 2, s˜ao apresen-
tados a fundamenta¸c˜ao matem´atica e alguns algoritmos para resolver DLPs; no Cap´ıtulo
3, s˜a o apresentados os trabalhos relacionados a o DHA3; no Cap´ıtulo 4, ´e apresentado o
protocolo proposto, o DHA3, bem como ´e tamb´em feita an´alise de quebra e a complexi-
dade de alg oritmos baseados em DLP que serviram de base para criar-se o DHA3, e por
fim; o Cap´ıtulo 5, a conclus˜ao desta disserta¸c˜ao.
6
Cap´ıtulo 2
Fundamentos de Cripto g rafia
Neste cap´ıtulo ser˜ao abo r dados os principais fundamentos que ser˜ao requeridos
para compreens˜ao do protocolo pro posto. Os t´opicos ser˜ao: conceitos b´asicos sobre segu-
ran¸ca e criptografia, DLPs, algoritmos para resolver DLPs, matrizes sobre GL
n
.
2.1 Conceitos B´asicos Sobre Seguran¸ca
Ao longo dos anos, v´arios m´etodos e protocolos foram desenvolvidos para proteger
uma “informa¸c˜ao”, sendo que esta informa¸c˜ao era documento f´ısico como: papel, carta,
contratos. Frequentement e os objetivos de seguran¸ca da informa¸c˜ao n˜a o podem ser al-
can¸cados atrav´es de m´etodos matem´aticos e protocolos apenas, mas requerem t´ecnicas e
procedimentos para poder alcan¸car o objetivo desejado. Com o avan¸co das tecnologias
de transporte e envio de informa¸c˜ao, alcan¸car seguran¸ca da informa¸c˜ao tornou-se mais
complexo devido ao meio utilizado; falsificar um documento como um contrato, ´e mais
complexo do que simplesmente realizar uma c´opia digital de um arquivo que apresentar´a
as mesmas caracter´ısticas do original, tor nando mais complexo o servi¸co dos peritos na
detec¸c˜ao da falsifica¸c˜ao. Alcan¸car seguran¸ca da informa¸c˜ao numa sociedade eletrˆonica
requer um conjunto vasto de t´ecnicas e habilidades legais. Nunca se tem uma garantia
absoluta de que o sistema est´a 100% seguro, mas um meio t´ecnico de prover seguran¸ca a
um sistema ´e atrav´es da criptografia.
A palavra Criptografia etimologicamente vem da palavra grega κρυπτς (oculto) e
graphos (escrita). Esta ´area de estudo mais abrangente engloba as disciplinas da Cripto-
grafia e da Criptoan´alise. Criptologia ´e o estudo de C´odigos e Cifras (n˜ao necessariamente
secretos). Mensagens ocultas que n˜ao s˜ao nem codificadas nem cifradas, s˜ao simples-
mente ocultas. Um c´odigo ´e um sistema pr´e- estabelecido de substitui¸c˜ao de palavras ou
de par´agrafos. Um idioma estrangeiro, por exemplo, ´e como um c´odigo secreto onde cada
7
palavra possui uma equivalente na o utra l´ıngua. Assim, “´agua” em portuguˆes equivale
a “wassar” em alem˜ao ou “water” em inglˆes. A maioria dos c´odigos funciona como se
fosse um dicion´ario, onde apresentam-se as equivalˆencias entre o s termos. J´a a pa lavra
cifra vem do hebraico saphar, que significa “dar n´umero”. A maioria das cifragens s˜ao
freq¨uentemente baseadas em t´ecnicas de sistemas num´ericos.
A Criptoan´alise ´e o estudo de como burlar os algoritmos criptogr´aficos existentes, a
ponto de conseguir-se obter o texto claro. Uma das t´ecnicas cl´assicas ´e o ataque por for¸ca
bruta, onde a t´ecnica ´e baseada em tentativas exaustivas de obter apenas o texto claro de
posse apenas do texto cifrado. A criptografia ´e o estudo de t´ecnicas matem´aticas relacio-
nadas aos a spectos de seguran¸ca da informa¸c˜ao tais como confidencialidade, integridade
dos dados, autentica¸c˜ao das entidades e autentica¸c˜ao dos dados.
Propriedades Criptogr´aficas:
• Confidencialidade: ´e um servi¸co usado para manter o conte´udo da informa¸c˜ao pro-
tegido de todos, autorizando o acesso apenas ao que possui o direito de acessar
tal informa¸c˜ao. Existe um va sto grupo de aplica¸c˜oes para prover confidencialidade,
desde m´etodos f´ısicos de prote¸c˜ao, a algoritmos matem´aticos que fazem com que a
informa¸c˜ao torne-se inintelig´ıvel [3].
• Integridade: ´e o servi¸co que gara nte que uma altera¸c˜ao n˜ao auto rizada seja realizada
sobre uma dada informa¸c˜ao. Para garantir a integridade, o m´etodo dever´a ser capaz
de detectar uma manipula¸c˜ao nos dados por partes n˜ao autorizadas. A manipula¸c˜ao
dos dados inclui inser¸c˜ao, apaga mento e substitui¸c˜ao dos dados por outra informa¸c˜ao
qualquer [3].
• Autentica¸c˜ao: ´e um servi¸co relacionado `a identifica¸c˜ao. Duas entidades que ini-
cializem uma comunica¸c˜ao dever˜ao identificar-se um com o outro. Em suma, a
autentica¸c˜ao ´e utilizada para identificar quem ´e quem numa comunica¸c˜ao segura,
evitando assim que um terceiro fa¸ca o papel de outra entidade.
• N˜ao Repudia¸c˜ao: ´e um m´etodo que previne uma entidade de negar a cordos ou a¸c˜oes
realizadas previamente. Por exemplo, uma entidade pode dizer que acessou um
determinado site e fez algumas altera¸c˜oes no mesmo, e em seguida negar tais a¸c˜oes.
Para isso que serve a n˜ao repudia¸c˜ao, ga r antir que uma entidade n˜ao possa negar
que n˜ao fez determinadas atitudes ou a¸c˜oes [3].
O objetivo principal da criptografia ´e aplicar estas quatro propriedades fundamen-
tais tanto na teoria como na pr´atica. A criptografia ´e um meio pelo qual pode-se evitar
e/ou detectar falsifica¸c˜ao e outros tipos de atividade maliciosas.
8
2.1.1 Sistemas Criptogr´aficos Cl´assicos
A no¸c˜ao de sistema criptogr´afico ´e formalmente definida a seguir. Um sistema
criptogr´afico ´e uma qu´ıntupla (P, C, K, ε, D) tal que [10]:
P, C, K s˜ao conjuntos finitos, onde P ´e o espa¸co de texto claro; C ´e o espa¸co de
texto cifrado; K ´e o espa¸co da chave. Elementos de P s˜ao referidos como texto claro,
elemento s de C s˜ao referidos como textos cifrados e elementos de D s˜ao referidos como
espa¸co de dados decifrados. Uma mensagem ´e um conjunto de s´ımbolos de texto claro.
ε = {E
k
|k ∈ K} ´e uma fam´ılia de fun¸c˜oes E
k
: P → C que s˜ao usadas para
cifragem, e D = {D
k
| k ∈ K} ´e a fam´ılia de fun¸c˜oes D
k
: C → P que s˜ao usadas para
decifragem. Para cada chave (e ∈ K) existe uma chave (d ∈ K) tal que para cada
p ∈ P : D
d
(E
e
(p)) = p.
Um sistema criptogr´afico ´e chamado sim´etrico (ou de ”chave privada”) se d = e,
ou se d pode ao menos ”facilmente”ser obtida a partir de e. Um sistema criptogr´afico ´e
chamado a ssim´etrico (ou de ”chave p´ublica”) se d = e, sendo na pr´atica ”imposs´ıvel”obter
d a partir de e. Assim, d ´e a chave privada, e ´e a chave p´ublica.
`
As vezes, diferentes
tamanhos de chaves s˜ao utilizados para cifragem e para decifragem, o que resulta numa
leve modifica¸c˜a o da defini¸c˜ao feita acima.
2.1.2 Defini¸c ˜oes
Algoritmos de Criptografia em Blocos: Estes algoritmos dividem o texto plano em
blocos de tamanho fixo e estes blocos s˜a o manipulados po r opera¸c˜oes matem´aticas
e/ou l´ogicas um por vez, at´e gerar o texto cifrado, e tamb´em s˜ao conhecidos por
n˜ao possu´ırem mem´oria.
Algoritmos de Criptografia em Fluxo (Stream Ciphers): S˜ao algoritmos que ci-
fram os dados conforme estes s˜ao recebidos. N˜ao cont´em uma fase preparat´oria de
divis˜ao do texto claro em “blocos”, cada cara ctere ´e cifrado um po r vez e o caractere
cifrado pode ou n˜ao possuir correla¸c˜ao com o caractere anterior que j´a fo i cifrado.
2.1.3 Criptoan´alise
A criptoan´alise para analisar a for¸ca de um sistema criptogr´afico depende de v´ario s
fatores: dificuldade de descobrir a chave (chaves criptogr´aficas com tamanho maior, em
bytes, dificultam mais na tentativa de quebra do sistema criptogr´afico, por´em causar˜ao
o aumento do custo computacional para cifrar a informa¸c˜a o ou texto plano), dificuldade
de se quebrar o c´odigo mesmo j´a conhecendo a mensagem cifrada, entre outros. A seguir
9
alguns dos tipos de criptoan´alises realizadas em sistemas criptogr´aficos:
• Ataque do texto cifrado
(cyphertext-only) : Quando se tem `a disposi¸c˜ao uma grande
quantidade de mensagens cifradas, mas desconhece-se o texto claro e as chaves
utilizadas. O objetivo neste tip o de ataque ´e conseguir obter o texto claro (obter as
chaves utilizadas para gerar o texto cifrado).
• Ataque do texto claro conhecido
(known-plaintext): Quando se tem `a disposi¸c˜ao
uma grande quantidade de mensagens cifradas e tamb´em textos claros correspon-
dentes aos textos cifrados. Neste tipo de ataque, tenta-se obter as chaves utilizadas
na cifragem dos textos claros, sendo assim, uma forma de analisar a robustez do
algoritmo no quesito chaves.
• Ataque adaptativo do texto escolhido ( a daptative-choosen-plaintext): Neste m´etodo
se tem `a disp osi¸c˜ao por¸c˜oes de textos claros e cifrados, e a cada passo analisamse
as partes para tentar extrair alguma informa¸c˜ao; ap´os isto, pode se tentar obter
novos textos claros e cifrado s, permitindo que pequenas por¸c˜oes de textos cifrados
e/ou claros sirvam para o ataque. O objetivo ´e deduzir as chaves utilizadas. Alguns
sistemas criptogr´aficos como o RSA [3] [4], s˜ao muito vulner´aveis a este tipo de
ataque.
• Ataque do texto cifrado escolhido
(choosen-cyphertext): Neste tipo de at aque, n˜ao
tem-se apenas uma gama de textos claros e seus equivalentes cifrados, mas pode-se
produzir uma mensagem cifrada espec´ıfica a ser decifrada, e compar´a-la com o texto
claro inserido no algoritmo criptogr´afico em an´alise.
´
E usado quando se tem uma
“caixa-preta” que faz a decifragem autom´atica. Sua tarefa ´e encontrar as chaves
utilizadas.
• Ataque da chave escolhida
(choosen-key): Neste tipo de ataque pode-se testar o
sistema com diversas chaves diferentes, ou pode-se convencer diversos usu´arios
leg´ıtimos do sistema a utilizarem chaves pr´e-determinadas. A finalidade imediata ´e
decifrar as mensag ens cifradas com essas chaves.
• Ataque de fo r ¸ca bruta
(brute force attack ): Resume o que todos os outros ataques
realizaram, ´e um ataque de car´ater geral, mas ´e utilizado apenas para busca do
texto claro.
10
2.1.4 Sistemas Criptogr´aficos Sim´etricos
Sistema sim´etrico ou de chave secreta ´e um sistema criptogr´afico que utiliza uma
mesma chave (o u segredo) para cifrar e decifrar a mensagem. Esta fo r ma tamb´em ´e
conhecida como Criptografia por Chave Secreta ou Chave
´
Unica ou Criptografia Sim´etrica.
A chave pode ser uma palavra, uma frase ou uma seq¨uˆencia aleat´oria de n´umeros e dever´a
ser conhecida por ambas as partes comunicantes (se uma mensagem ´e enviada a um
determinado destinat´ario , este dever´a possuir a chave para poder recuperar a informa¸c˜ao
por ele recebida). Seu tamanho ´e medido em bits e, via de regra, quanto maior a chave,
mais segura ser´a a informa¸c˜ao cifrada. Sua gera¸c˜ao , transmiss˜ao e armazenamento, s˜ao
denominados Gerˆencia de Chaves.
O principal desafio deste sistema ´e garantir que ningu´em mais conhe¸ca a chave al´em
das partes comunicantes. Para tanto, as partes comunicantes devem trocar pessoalmente
ou possuir um sistema de transmiss˜ao confi´avel capaz de garantir a confiabilidade das
chaves transmitidas. Pois, qualquer um que venha, de alguma forma, a ter conhecimento
desta chave, pode mais tarde ler, modificar ou forjar mensagens cifradas ou autenticadas
que utilizem aquela chave. Devido ao fato de ser necess´ario compartilhar a chave secreta,
os sistemas de criptografia por chave sim´etrica apresentam dificuldades em garantir plena
seguran¸ca, especialmente em ambientes distribu´ıdos com um grande n´umero de usu´arios.
Tais m´etodos s˜ao mais utilizados em ambientes com dispositivos limitados compu-
tacionalmente, onde o transmissor e o receptor se preparam antecipadamente para o uso
da chave secreta. Outro fato ´e de que ambos conhecem a chave secreta, com isso pode-se
permitir o rep´udio, dizer que determinada mensagem n˜ao foi enviada pelo participante
’A’ da comunica¸c˜ao, mesmo ele tendo enviado ta l mensagem. A grande vantagem da
criptografia de chave secreta ´e que ela ´e muito r´apida, podendo ser facilmente implemen-
tada em hardwa r e, principalmente em equipamentos de baixo poder computacional. Tal
m´etodo pode ser bem utilizado em aplica¸c˜oes em que o pr´oprio usu´ario cifra e decifra os
dados, como por exemplo, o caso de cifra r os dados do disco r´ıgido para que terceiros n˜ao
tenham acesso `as informa¸c˜oes ali constantes. A Fig ura 2.1 mostra em diagrama de blocos
o funcionamento de um sistema criptogr´afico sim´etrico.
A seguir s˜ao citados alguns dos algor itmos criptogr´aficos sim´etricos mais conhecidos
descritos em [3] [4]:
• Crypt: Sistema de cifragem do UNIX, que utiliza uma chave de tamanho vari´avel.
Alguns programas podem automaticamente decifrar arquivos cifrados sem necessa-
riamente conhecer a chave e/ou mesmo o texto plano. O Crypt n˜ao ´e seguro. O
sistema crypt ´e utilizado pelo UNIX para cifrar senhas.
11
Figura 2.1 : Sistema Criptogr´afico Sim´etrico.
• DES (Data Encryption Standard ):
´
E um padr˜ao de cifragem de dados desenvolvido
na d´ecada de 70, pelo National Bureau of Standards and Technology (atualmente
conhecido como: NIST (National Institute of Standards and Technology)) e a IBM.
O DES utiliza uma chave de 56 bits e opera em blocos de 64 bits. Foi projetado
inicialmente para ser utilizado em componentes de hardware. Nos dias at uais ´e
utilizado na Internet em conex˜oes Web segura, o SSL (Secure Socket Layer) utiliza
o DES dentre outros algoritmos criptogr´aficos. Ele ´e um algoritmo seguro par a uma
grande quantidade de aplica¸c˜oes, entretanto, em aplica¸c˜oes altamente confidenciais,
o DES n˜a o deve ser usado, pois existe o risco de viola¸c˜ao. Existe ainda o 3DES
(Triplo DES ) que opera com trˆes chaves no esquema CDC (Cifra Decifra Cifra),
onde cada uma destas opera¸c˜oes ´e feita com uma chave diferente. Todas estas chaves
s˜ao de 56 bits e trabalham tamb´em com blocos de texto claro de 64 bits.
• IDEA (Internation al Data Encryption Algorithm): f oi desenvolvido, na d´ecada de
80 por Xuejia La i e James Massey da ASCOM Tech AG da Su´ı¸ca, em Zurique.
Ele foi projetado para ser de f´acil implementa¸c˜ao, al´em de ser resistente `a muitas
formas de criptoan´alise. O seu m´etodo baseia-se na utiliza¸c˜ao de uma chave de 128
bits, onde blocos de texto de 64 bits da mensagem de entrada s˜ao alterados em
uma seq¨uˆencia de intera¸c˜oes, produzindo blocos cifrados de informa¸c˜ao na sa´ıda do
processo de cifragem. Sua chave de 128 bits ´e o suficiente para resistir `a maioria dos
ataques. IDEA ´e usado pelo popular programa PGP, para cifrar arquivos e e-mails.
Entretanto, a vasta utiliza¸c˜ao do IDEA ´e impedida po r uma s´erie de pat entes de
software da ASCOM Tech. A ASCOM Tech concedeu apenas, o uso gratuito em
implementa¸c˜oes do PGP (Pretty Good Privacy) fora dos Estados Unidos da Am´erica,
12
mas sendo necess´ario verificar os termos e suas licen¸cas.
• RC2 e RC4: Mais velozes do que os sistemas DES e 3DES, esses c´odigos podem se
tornar mais seguros com o simples aumento do tamanho das chaves. O RC2 pode
substituir perfeitamente o DES com a vantagem de ser 2 vezes mais r´a pido, em
termos de desempenho. O algoritmo RC4 ´e 10 vezes mais r´apido.
• RC5: Um sistema de cifragem desenvolvido po r Ronald Rivest [4] e publicado em
1994. O RC5 permite definir o tamanho da chave, o tamanho dos blocos de dados,
e o n´umero de cifragens realizadas.
• Skipjack: Sistema criptogr´afico desenvolvido pela NSA (Nationa l Security Agency)
utiliza chaves de 80 bits par a cifrar blocos de 64 bits de informa¸c˜a o. At´e 1998 era
classificado como secreto, seu projeto inicial foi concebido em meados de 1980. O
Skipjack foi uma tentativa de substituir o DES devido `as suas vulnerabilidades.
Contudo um dia ap´os o c´odigo do Skipjack ter sido aberto ao p ´ublico (estudio-
sos, cript´o grafos), foram encontrados m´etodos para realizar ataques nas tabelas de
rota¸c˜ao 16 das 32 utilizadas pelo mesmo e em quest˜oes de meses foram encontradas
31 das 32 tabelas de rota¸c˜ao. Por esses e outros motivos realizar seguran¸ca atrav´es
da obscuridade n˜ao traz benef´ıcio algum, uma vez que os estudiosos e cript´ograf os
podem contribuir de forma significativa para a melhoria dos algoritmos sendo re-
postos pelas grandes agˆencias de seguran¸ca.
2.1.5 Sistemas Criptogr´aficos de Chave P´ublica
No presente sistema, cada usu´ario possui um par de chaves, uma que ´e a Chave
P´ublica e outra a Chave Privada. Enquanto a chave p´ublica tem seu conhecimento divul-
gado, a chave privada necessita ficar armazenada seguramente. Assim, a necessidade das
partes comunicantes de trocar informa¸c˜oes sigilosas ´e eliminada porque todas as comu-
nica¸c˜oes ir˜ao envolver somente a chave p´ublica, n˜ao sendo preciso trocar as chaves privadas
por nenhuma das partes. Paralelamente, este sistema n˜ao exige credibilidade dos meios
de transmiss˜ao envolvidos. A ´unica exigˆencia deste sistema ´e que a chave p´ublica esteja
associada aos seus usu´arios ap´os ser feita a autentica¸c˜ao da mesma. Qualquer um do s
possuidores da chave p´ublica pode us´a-la para enviar uma mensagem. Contudo, a mesma
mensagem s´o pode ser decifrada mediante o uso da chave privada a qual ´e de uso restrito
de seu propriet´ario.
Em criptografia de chave p´ublica as implementa¸c˜oes mais conhecidas s˜ao o RSA e o
sistema PG P. Em 1977, Rivest, Shamir e Adelman [3] desenvolveram o RSA e publicaram
13
o algoritmo de cifragem apesar da oposi¸c˜ao do governo norte a mericano, que considera a
criptografia um assunto de seguran¸ca nacional. Mais tarde a patente do RSA ´e dada ao
MIT (Instituto Tecnol´ogico de Massachusetts) que logo a cede a um grupo denominado
PKP (Public Key Partners).
O programador Phil Zimmermann, em 1991, autoriza a publica¸c˜ao em boletins
eletrˆo nicos e grupos de not´ıcias de um programa por ele desenvolvido e batizado como
Pretty Good Privacy ou PGP [11]. O PGP que tem como base os algoritmos do RSA
publicados em 1978. Quando Zimmermann publicou o PGP se viu em problemas com o
Departamento de Estado No rt e Americano que abriu uma investiga¸c˜ao para determinar se
ele havia violado as restri¸c˜oes de exporta¸c˜ao de criptografia ao autorizar a divulga¸c˜ao do
c´odigo fonte do PGP na Internet. Apesar do mesmo t er se comprometido em n˜ao divulgar
seu desenvolvimento, diversos programadores em v´ar ia s partes do mundo continuaram
adiante, po r t ando-o para v´a r ia s plataformas e assegurando sua expans˜ao.
No m´etodo de cifragem por chave p´ublica resolve o problema de transmitir uma
mensagem totalmente segura atrav´es de um canal inseguro. O receptor da mensagem cria
duas chaves que s˜ao relacionadas entre si, uma p´ublica e uma privada. A chave p´ublica
pode e deve ser distribu´ıda livrement e. Quem envia a mensagem tem que utilizar a chave
publica do receptor para cifr´a-la. Uma vez cifrada, esta mensagem s´o pode ser decifrada
pela chave do receptor.
Apesar dos benef´ıcios no quesito seguran¸ca, onde os sistemas de criptografia as-
sim´etrica permitem trafegar informa¸c˜oes sobre um canal inseguro, tais sistemas apresen-
tam uma desvantagem que ´e o fator velocidade de cifragem. Enquanto um alg oritmo de
cifragem sim´etrica pode processar milh˜oes de bytes de texto claro, os algoritmos de cifra-
gem assim´etrica podem apenas cifrar na casa de milhares de bytes de texto claro o que ´e
indesej´avel para aplica¸c˜o es em sistemas embutidos. A Figura 2.2 mostra em diagrama de
blocos o funcionamento de um sistema criptogr´a fico assim´etrico.
A seguir s˜ao descritos alguns dos sistemas criptogr´aficos assim´etricos mais utiliza-
dos descritos em [3] [4]:
• Diffie-Hellman - Um protocolo para trocas de chaves criptogr´aficas entre par-
tes comunicantes, n˜ao ´e um m´etodo de cifragem e decifragem, mas um m´etodo
desenvolvido para o compartilhamento de chaves de Sess˜ao sobre um canal de co-
munica¸c˜ao p´ublico. Ao realizar o protocolo, as duas partes concordam em alguns
valores num´ericos Domain Parameters, e cada parte gerar´a ao final dos procedi-
mentos a mesma chave. Cada parte pode ent˜ao calcular uma outra chave de Sess˜ao
que n˜ao pode facilmente ser derivada por um ataque sem conhecer a mbas as tro-
14
cas r ealizadas entre as partes. Existem v´arias vers˜oes deste protocolo, envolvendo
um diferente n´umero de partes e m´ultiplas transforma¸c˜oes matem´aticas. As chaves
podem apresentar v´arios tamanhos dependendo do tipo de implementa¸c˜ao. Chaves
maiores geralmente s˜ao mais seguras, devido a dificuldade em resolver DLPs.
• R SA - Um sistema criptogr´afico desenvolvido por trˆes pessoas, (Ronald R ivest,
Shamir e Leonard Adleman do MIT), e por este motivo ´e chamado de RSA. O
RSA pode ser usado para cifragem de informa¸c˜oes e assinaturas digitais. As chaves
podem apresentar v´arios tamanhos dependendo do tipo de implementa¸c˜a o.
• ElGamal - Outro protocolo de acordo de chaves que se baseia em opera¸c˜oes ex-
ponenciais e em fun¸c˜oes modulares como o DH, ´e o ElGamal. Ele ´e usado princi-
palmente para cifragem e assinaturas digitais de uma maneira similar ao algoritmo
Diffie-Hellman.
Figura 2.2 : Sistema Criptogr´afico Assim´etrico.
2.1.6 Fun¸c˜oes de Hash Criptogr´aficas
As fun¸c˜oes de hash criptogr´aficas s˜ao utilizadas para realizar uma esp´ecie de “im-
press˜ao digital” de um determinado documento de forma a garantir teoricamente que
dois do cumentos distintos n˜ao resultem no mesmo hash. As fun¸c˜oes de hash podem ser
aplicadas para garantir a integridade dos dados bem como serem usadas para realizar a
autentica¸c˜ao das mensagens utlizando-se para t´ecnicas de assinaturas digitais. As fun¸c˜oes
de hash transformam uma dada entrada (em bits) de qualquer tamanho fixo numa sa´ıda
de tamanho fixo idependentemente de qual seja esta entra da. A Figura 2.3 descreve o
15
funcionamento do simplificado de uma fun¸c˜ao de hash onde os resultados est˜ao na base
hexadecimal, e para este exemplo foi utilizado o hash MD5.
Figura 2.3: Funcionamento fun¸c˜ao de Hash
Algumas defini¸c˜o es e propriedades de algumas fun¸c˜oes de hash s˜ao descritas abaixo,
para fun¸c˜o es de hash h com entradas x, x
′
e sa´ıdas y, y
′
[3]:
1. resistˆencia a pr´e-i magem - para essencialmente todas a s sa´ıdas pr´e-especificadas, ´e
computacionalmente invi´avel encont r ar qualquer entrada dado os hashes, por exem-
plo, encontrar qualquer pr´e-imagem x
′
tal que h(x
′
) = y quando dado qualquer y
para o qual a correspondente entrada n˜ao ´e conhecida.
2. resistˆencia a segunda pr´e-imagem - ´e computacionalmente invi´avel encontrar qual-
quer segunda entrada que tenha a mesma sa´ıda com qualquer entrada especifi-
cada, por exemplo, dado x, encontrar uma segunda pr´e-imagem x
′
= x tal que
h(x) = h(x
′
).
3. resistˆencia a colis˜ao - ´e computacionalmente invi´avel encontrar qualquer duas en-
tradas distintas x, x
′
que o hash tenha a mesma sa´ıda, por exemplo, tal que h(x) =
h(x
′
).
Apesar das fun¸c˜oes de hash primarem por essas propriedades j´a foi demostrado que
a gra nde maioria delas apresentou alguns casos de colis˜ao (duas entradas diferentes geram
o mesmo hash). Para o escopo do protocolo proposto nesta disserta¸c˜ao tais problemas n˜ao
afetariam a seguran¸ca do protocolo D HA3, uma vez que a utiliza¸c˜ao de ta is fun¸c˜oes de
hash s˜ao atualizadas apenas para a deriva¸c˜ao das chaves de sess˜ao geradas pelo protocolo.
Principais aplica¸c˜o es das fun¸c˜oes de hash [3]:
1. I ntegridade dos dados - garante que os dados n˜ao foram a lterados, modificados ou
mesmo substitu´ıdos.
2. Deriva¸c˜ao de chaves - para computar sequˆencias de novas chaves a priori calcula-
das, se a chave sendo utilizada for comprometida esta n˜ao comprometer´a as chaves
utilizadas nas transa¸c˜oes anteriores.
16
3. Gerador de n´umeros pseudo-aleat´orios - em alguns casos muito espec´ıficos pode se
usar fun¸c˜oes de hash para g erar n´umeros pseudo-aleat´orios, mas n˜ao ´e considerado
um m´etodo seguro, pois uma vez determinada a semente geradora dos hashes todo
sistema estar´a comprometido.
A Tabela 2.1 descreve as fun¸c˜oes de hash que s˜ao baseadas em cifradores de bloco
(bloc k ciphers) e ser˜ao discutidas a sua utiliza¸c˜ao no Cap´ıtulo 4 desta disserta¸c˜ao. Na
Tabela 2.1 ´e descrito o tamanho da sa´ıda em bits e o n´umero de o pera¸c˜oes de hash
necess´arias a serem realizadas para gerar uma colis˜ao (dados te´oricos uma vez que foram
encontrados meios de causar colis˜oes em menos opera¸c˜oes).
Tabela 2.1: Fun¸c˜oes de hash-esp ecifica¸c˜oes
Fun¸c˜ao hash Sa´ıda em bits Opera¸c˜oes de hash
MD5 128 2
64
RIPEMD-128 128 2
64
SHA-1, RIPEMD -160 160 2
80
2.2 DLP
A seguran¸ca de muitas t´ecnicas criptogr´aficas depende da intratabilidade de proble-
mas de logaritmo discreto (DLPs). Uma lista parcial de tais m´etodos inclui D iffie-Hellman
e suas variantes, ElGamal e suas variantes. Um problema de logaritmo discreto pode ser
definido como sendo: Da do um α um primo p e um β = α
a
mod p encontrar a; sendo
a, α, β ∈ Z
∗
p
[3]. Supondo p = 97 . Ent˜ao Z
∗
97
´e um grupo c´ıclico de ordem n = 96. Um
gerador de Z
∗
97
pode ser α = 5. Sendo, 5
32
≡ 35 (mod 97), log
5
35 = 32 em Z
∗
97
.
Resolver o DLP num grupo c´ıclico G de ordem n ´e em ensˆencia calcular o iso-
morfismo entre G e Z
n
. Sendo asssim qualquer dois grupos c´ıclicos de mesma ordem
s˜ao isom´orficos (que ´e, eles possuem a mesma estrutura contudo os elementos podem ser
escritos em diferentes representa¸c˜oes), um algoritmo eficiente para calcular um gr upo n˜ao
necessariamente implica ser eficiente para calcular em outro grupo. Para ver sito, con-
sidere que cada grupo c´ıclico de ordem n ´e isom´orfico ao grupo c´ıclico aditivo Z
n
, isto
´e, o conjunto de inteiros {0, 1, 2, ···, n − 1} onde a opera¸c˜ao do grupo ´e adi¸c˜ao m´odulo
n. Al´em disso, o problema de logaritmo discreto neste grupo, nomeadamente, ´e o pro-
blema de encontrar um inteiro x tal que ax ≡ b(mod n) dado a, b ∈ Z
n
. Primeiro notar
que n˜ao existe uma solu¸c˜a o x se d = gcd( a, n) n˜ao divide b. Entretanto, se d divide b
o algoritmo Euclidiano extendido [3] pode ser usado para encontrar inteiros s e t tais
que as + nt = d. Multiplicando ambos os lados desta equa¸c˜ao pelo inteiro b/d tˆem - se
17
a(sb/d) + n(tb/d) = b. Reduzindo esta equa¸c˜ao m´odulo n tˆem - se a(sb/d) ≡ b(mod n) e
da´ı x = (sb/d) (mod n) ´e a solu¸c˜ao desejada [4].
Os algor´ıtmos para resolver DLP podem ser categorizados desta forma [3]:
1. Algoritmos que trabalham em grupos arbitr´arios, po r exemplo, busca exaustiva,
baby - step giant - step, a lg oritmo Pollard’s rho;
2. algoritmos que tra balham em grupo s arbitr´arios mas s˜ao especialmente eficientes se
a ordem do grupo possuir f atores primos pequenos, por exemplo, algoritmos Pohllig
- Hellman; e
3. Os algoritmos index - calculus que s˜ao eficientes apenas em certos grupos.
Nas pr´oximas se¸c˜oes ser˜ao apresentados a lg uns destes algoritmos para resolver
DLPs.
2.3 Busca Exaustiva
O algoritmo mais ´obvio para resolver um DLP ´e calcular sucessivamente α
0
, α
1
,
α
2
, ··· at´e β ser obtido. Este m´etodo levaria O(2
n
) multiplica¸c˜oes, onde n ´e a ordem de
α, e ´e al´em do mais ineficiente se n ´e de uma magnitude grande (que ´e o caso de interesse
da criptografia) [3].
2.4 Algoritmo baby-step giant-step
Sendo m = ⌈
√
n⌉, onde n ´e a ordem de α. O algoritmo BSGS (Baby-Step Giant-
Step) ´e um algoritmo de mem´oria limitado ao m´etodo de busca exaustiva e ´e baseado na
seguinte observa ¸c˜ao. Se β = α
x
, ent˜a o pode-se dizer que x = im + j, onde 0 ≤ i, j < m.
Assim, α
x
= α
im
α
j
, que implica em β(α
−m
)
i
= α
j
. Disto, obtˆem-se o seguinte algoritmo
para calcular x [3]:
18
Algoritmo BSGS Algoritmo Baby-Step Giant-Step
ENTRADA: gerador α de um grupo c´ıclico G de ordem n, e um elemento
β ∈ G
SA
´
IDA: o logaritmo discreto x = lo g
α
β
1. Definir m ← ⌈
√
n⌉
2. Construir uma tabela com a s entradas (j, α
j
) para 0 ≤ j < m. Orde-
nar esta tabela pelo segundo componente.
3. Calcular α
−m
e definir γ ← β.
4. Para i de 0 at´e m −1 fa¸ca o seguinte:
4.1 Verificar se γ ´e o segundo componente de alguma entrada na
tabela.
4.2 Se γ = α
j
ent˜ao retornar (x = im + j).
4.3 Definir γ ← γ · α
−m
.
O tempo de execu¸c˜ao do algoritmo BSGS ´e de O(
√
n) grupos de multiplica¸c˜oes.
2.4.1 Exemplo do BSGS
Considerar o BSGS trabalhando em lo garitmos sobre Z
∗
113
. Sendo p = 113. O
elemento α = 3 ´e o gerador e a o r dem n = 112. considerar β = 57. ent˜ao log
3
57 ´e
calculado como a seguir.
1. Defina m ← ⌈
√
112⌉ = 11.
2. Construa uma ta bela que as entradas s˜ao (j, α
j
mod p) para 0 ≤ j < 11
j 0 1 2 3 4 5 6 7 8 9 10
3
j
mod p 1 3 9 27 81 17 51 40 7 21 63
ordenar a tabela pelo segundo componente:
j 0 1 8 2 5 9 3 7 6 10 4
3
j
mod p 1 3 7 9 1 7 21 27 40 51 63 81
3. Calcular α
−1
= 3
−1
mod 113 = 38 ent˜ao calcular α
−m
= 38
11
mod 113 = 58.
4. Assim, γ = βα
−mi
mod 113 para i = 0, 1, 2, ··· ´e calculado at´e um valor na
segunda linha da tabela ´e obtido. Gerando:
i 0 1 2 3 4 5 6 7 8 9
γ = 57 · 58
i
mod p 57 29 100 37 1 12 55 26 39 2 3
Finalmente, dado βα
−9m
= 3 = α
1
, β = α
100
e, al´em do mais, log
3
57 = 100.
19
2.5 Algoritmo Pohlig-Hellman
Este algoritmo para calcular DLPs leva em considera¸c˜ao o fato da fatoriza¸c˜ao
de ordem n do grupo G. Sendo, n = p
e
1
1
p
e
2
2
···p
e
r
r
seja a fatoriza¸c˜ao dos primos de n.
Se x = log
α
β, ent˜ao o objetivo ´e determinar x
i
= x mod p
e
i
i
para 1 ≤ i ≤ r, ent˜ao
usar o algor itmo de Gauss [3] para recuperar x mod n. Cada inteiro x
i
´e determinado
pelo calculo dos digitos l
0
, l
1
, ···, l
e
i−1
em torno de sua representa¸c˜ao p
i
− ary : x
i
=
l
0
+ l
i
p
i
+ ··· + l
e
i−1
p
e
i−1
i
, onde 0 ≤ l
j
≤ p
i
− 1.
Algoritmo Pohlig-Hellman
ENTRADA: gerador α de um grupo c´ıclico G de ordem n, e um element o
β ∈ G
SA
´
IDA: o logaritmo discreto x = lo g
α
β
1. Encontrar a fatoriza¸c˜ao de n: n = n = p
e
1
1
p
e
2
2
···p
e
r
r
, onde e
i
≥ 1.
2. Para i de 1 at´e r realizar o seguinte:
(Calcular x
i
= l
0
+ l
1
p
i
+ ··· + l
e
i−1
p
e
i−1
i
, onde x
i
= x mod p
e
i
i
)
2.1 (Simplificar a nota¸c˜ao) Definir q ← p
i
e e ← e
i
2.2 Definir γ ← 1 e l
−1
← 0.
2.3 Calcular
α ← α
n
q
.
2.4 (Calcular o l
j
) Para j de 0 at´e e − 1 fa¸ca :
Calcular γ ← γα
l
j−1
q
j−1
e β ← (βγ
−1
)
n
q
j+1
.
Calcular l
j
← log
α
β.
2.5 Definir x
i
← l
0
+ l
1
q + ···+ l
e−1
q
e−1
.
3. Utilizar o algoritmo de Gauss para calcular o inteiro x, 0 ≤ x ≤ n − 1, tal
que x ≡ x
i
(modp
e
i
i
) para 1 ≤ i ≤ r.
4. Retornar (x).
O exemplo a seguir do Algoritmo Pohlig-Hellman utiliza parˆametros de pequena magni-
tude para facilitar a compreens˜ao.
2.5.1 Exemplo Pohlig-Hellman
Dado p = 251. O elemento α = 1 ´e o gerador de Z
∗
251
de ordem n = 250. Considerar
β = 210. ent˜ao x = log
71
210 ´e calculado a seguir [3]:
20
1. A fatoriza¸c˜ao em primos de n ´e 25 0 = 2 · 5
3
.
2. (a) (Calcular x
1
= x mod 2)
Calcular
α = α
n
2
mod p = 250 e
β = β
n
2
mod p = 250. Ent˜ao x
1
=
log
250
250 = 1.
(b) (Calcular x
2
= x mod 5
3
= l
0
+ l
1
5 + l
2
5
2
)
Calcular
α = α
n
5
mod p = 20.
Calcular γ = 1 e
β = (βγ
−1
)
n
5
mod p = 149. Usando busca exaustiva,
calcular l
0
= log
20
149 = 2.
Calcular γ = γα
2
mod p = 21 e
β = (βγ
−1
)
n
25
mod p = 113. Usando
busca exaustiva, calcular l
1
= log
20
113 = 4.
Calcular γ = γα
4·5
mod p = 115 e
β = (βγ
−1
)
p−1
125
mod p = 149. Usando
busca exaustiva, calcular l
2
= log
20
149 = 2.
Assim, x
2
= 2 + 4 · 5 + 2 · 5
2
= 72.
3. Finalmente, resolver o par de congruˆencias x ≡ 1(mod2), x ≡ 72(mod125)
para obter x = log
71
210 = 197.
Devido a fatoriza¸c˜ao de n, o tempo de execu¸c˜ao do Pohlig- Hellman ´e O(
r
i=1
e
i
(lg n +
√
p
i
)) grupos de multiplica¸c˜oes. A eficiˆencia de tal algor itmo depende apenas se
cada primo divisor p
i
de n ´e relativamente pequeno, pois se for de magnitude grande tal
m´etodo n˜ao se to r na mais eficiente [3].
2.6 Algoritmo Index-Calculus
O algoritmo Index-Calculus ´e o mais poderoso m´etodo conhecido para calcular
logaritmos discretos. A t´ecnica empregada n˜ao se aplica a todos os grupos, mas quando
´e aplic´avel, geralmente trabalha sobre tempo sub - exponencial. O algoritmo index-
calculus requer a sele¸c˜ao de um pequeno subconjunto S de elementos de G , chamado
de factor base, de tal modo que uma fra¸c˜ao significante dos elementos de G possa ser
efetivamente expressada como produtos dos elementos de S [3].
21
Algoritmo Index-Calculus
ENTRADA: gerador α de um grupo c´ıclico G de ordem n, e um element o
β ∈ G
SA
´
IDA: o logaritmo discreto y = log
α
β
1. (Selecionar um fator base S) Escolher um sub - conjunto S = {p
1
, p
2
, ···, p
t
}
de G tal que uma “por¸c˜ao significativa” dos elementos em G possam ser efiti-
vamente expressadas como um pro duto de elementos em S.
2. (Coletar rela¸c˜oes lineares envolvendo logaritmos dos elementos em S)
2.1 Selecionar um inteiro aleat´orio k, 0 ≤ k ≤ n − 1, e calcular α
k
.
2.2 Tentar escrever α
k
como um produto dos element os em S:
α
k
=
t
i=1
p
c
i
i
, c
i
≥ 0. (ic.1)
Se obtiver sucesso, pegar os logaritmos de ambos os lados da equa¸c˜ao (ic.1)
para obter uma rela¸c˜ao linear
k ≡
t
i=1
c
i
log
α
p
i
(modn) (ic.2).
2.3 Repetir os passos 2.1 e 2.2 at´e t + c rela¸c˜oes da forma (ic.2) forem
obtidas.
3. (Encontrar os logaritmos dos elementos em S) Trabalhando com m´odulo n,
resolver o sistema linear de t + c equa¸c˜o es (em t inc´ognitas) da fo r ma (ic.2)
obtidas no passo 2 para obter os valores de log
α
p
i
, 1 ≤ i ≤ t.
4.(Calcular y)
4.1 Selecionar um inteiro aleat´orio k, 0 ≤ k ≤ n − 1, e calcular β · α
k
.
4.2 Tentar escrever β · α
k
como um produto dos elementos em S:
β · α
k
=
t
i=1
p
d
i
i
, d
i
≥ 0. (ic.3)
Se a tentativa n˜ao der certo ent˜ao repetir o passo 4.1 . Sen˜ao, pe-
gar os logaritmos de ambos os lados da equa¸c˜ao (ic.3) que geraria log
α
β =
(
t
i=1
d
i
log
α
p
i
− k) mod n; assim, calcular y = (
t
i=1
d
i
log
α
p
i
− k) mod n e
retornar (y).
2.6.1 Exemplo: Index-Calculus em Z
∗
p
Para o campo Z
p
um primo, o fator base S pode ser escolhido como o primeiro
n´umero primo t. Uma rela¸c˜ao (ic.1) ´e gerada pelo c´alculo de α
k
mod p e ent˜ao usando
uma divis˜ao trivial para checar se este inteiro ´e o pro duto dos primos em S. A seguir um
exemplo para o Index-Calculus [3].
Sendo p = 229. O elemento α = 6 ´e a gerador de Z
∗
229
de ordem n = 229.
Considerar β = 13. Ent˜ao log
6
13 ´e calculado como a seguir, usando a t´ecnica do index-
22
calculus [3].
1. O fator base ´e escolhido para ser os 5 primeiros primos: S = {2, 3, 5, 7, 11}.
2. As seguintes seis rela¸c˜oes envolvendo elementos do fator base s˜a o obtidas:
6
100
mod 229 = 180 = 2
2
· 3
2
· 5
6
18
mod 229 = 176 = 2
4
· 11
6
12
mod 229 = 165 = 3 · 5 · 11
6
62
mod 229 = 154 = 3 · 7 · 11
6
143
mod 229 = 198 = 2 · 3
2
· 11
6
206
mod 229 = 210 = 2 · 3 · 5 ·7
Estas rela¸c˜oes geram as seguintes seis equa¸c˜oes envolvendo os logar itmos dos
elemento s no fato r base:
100 ≡ 2 log
6
2 + 2 log
6
3 + log
6
5(mod228)
18 ≡ 4 log
6
2 + log
6
11(mod228)
12 ≡ log
6
3 + log
6
5 + log
6
11(mod228)
62 ≡ log
6
2 + log
6
7 + log
6
11(mod228)
143 ≡ log
6
2 + 2 log
6
3 + log
6
11(mod228)
206 ≡ log
6
2 + log
6
3 + log
6
5 + log
6
7(mod228)
3. Resolvendo o sistema linear das seis equa¸c˜oes com cinco inc´ognitas (o logaritmo
x
i
= log
6
p
i
) gera a solu¸c˜ao log
6
2 = 21, log
6
3 = 208, log
6
5 = 98, l o g
6
7 = 107 e
log
6
11 = 162.
4. Supor que o inteiro k = 77 ´e selecionado. Sendo β · α
k
= 13 · α
77
mod 229 =
147 = 3 · 7
2
, vˆe - se que:
log
6
13 = (log
6
3 + 2 log
6
7 − 77) mo d 228 = 117.
2.7 Discuss˜ao sobre DLPs
Como mostrado anteriormente, existem duas classes principais de algoritmos para
resolver DLP, uma classe cujo tempo de execu¸c˜ao estimado ´e de O(
√
p) e a classe de
algoritmos baseados em L
p
= [k, c] com tempo de execu¸c˜ao sub - exponencial. Os que
s˜ao baseados na complexidade O(
√
p) s˜ao: Baby-Step Giant-Step, Pollard’s rho, Pohlig-
Hellman (somente se a ordem n for um primo) [3]. Quanto aos que s˜ao baseados na
complexidade L
p
= [k, c] para resolver um DLP s˜ao: Index-Calculus, Coppersmith e o
NFS que ´e uma varia¸c˜ao do Index-Calculus sendo este o melhor algoritmo para resolver
DLP [3]. Os algoritmos que solucionam um DLP em tempo de execu¸c˜a o subexponencial
como o NFS [12], a sua complexidade ´e descrita pela equa¸c˜ao 2.1, onde p ´e primo sendo
utilizado, c ´e uma constante e k ´e uma constante satisfazendo 0 ≤ k ≤ 1. A Tabela 2.2
23
apresenta a complexidade que cada algoritmo leva para resolver DLP.
L
p
[k, c] = O(e
(c+O(1))·((ln p)
k
)·((ln ln p)
1−k
)
) (2.1)
O gr´afico apresentado na Figura 2.4 mostra a compara¸c˜ao entre os m´etodos basea-
dos na complexidade O(
√
p) (BSGS) e o NFS [12]. O eixo horizontal mostra a varia¸c˜ao da
magnitude do n´umero primo p em bits e no eixo vertical ´e mostrada em bits a complexi-
dade para resolver um DLP. At´e primos com menos de 80 bits de magnitude, nos m´etodos
baseados em O(
√
p) encontram a solu¸c˜ao em menor tempo de execu¸c˜ao . Contudo, com
primos maiores que 80 bits de magnitude torna-se mais vantajoso o uso do NF S, uma vez
que para primos com 1024 bits o NFS requer apenas O(2
132
) execu¸c˜oes enquanto que os
m´etodos baseados em O(
√
p) requerem O(2
512
), conforme [3].
Tabela 2.2: Algoritmos cl´assicos para resolver DLP
Algoritmo Complexidade
BSGS O(
√
p)
Pollard’s rho O(
√
p)
Pohlig-Hellman O(
r
i=1
e
i
(lg n +
√
p
i
))
Index-Calculus L
p
= [
1
2
, c]
Coppersmith L
p
= [
1
3
, 1.587]
NFS L
p
= [
1
3
, 1.923]
0
64
128
192
256
320
384
448
512
576
0 64 128 192 256 320 384 448 512 576 640 704 768 832 896 960 1024
Complexidade para n bits O(2
n
)
Precisao de p em bits
Comparacao entre o metodo BSGS e o NFS para resolver DLP
BSGS
NFS
Figura 2.4 : Compara¸c˜ao entre os M´etodos BSGS e NFS
24
A pr´oxima se¸c˜ao ir´a discutir sobre grupos de matrizes sobre campos finitos, devido
ao fato do protocolo proposto nesta disserta¸c˜ao utilizar de tais grupos de matrizes e
tamb´em para facilitar a compreens˜ao das opera¸c˜oes matem´aticas apresentadas no Cap´ıtulo
4.
2.8 Matrizes Sobre Z
∗
p
Um campo ´e a menor estrutura matem´atica no qual podem-se realizar todas as
opera¸c˜oes aritm´eticas soma, subtra¸c˜ao , multiplica¸c˜ao e divis˜ao (sendo esta por elementos
n˜ao nulos), em particular todo elemento n˜ao nulo deve po ssuir sua inversa multiplicativa
[13]. A defini¸c˜ao de um campo finito ´e:
1. Um campo ´e uma tripla (F, +, ·) tal que (F, +) ´e um grupo abeliano (chamado sua
identidade 0 ) e (F −{0}, ·) ´e tamb´em um grupo ab eliano, e a seguinte lei distributiva
diz: a · (b + c) = (a · b) + (a · c), para todo a, b, c ∈ F [13].
2. Para qualquer campo F tem F
∗
= F − {0} [13].
Para cada n ∈ Z
+
deixe GL
n
(F ) ser o conjunto de todas n × n matrizes que as
entradas vˆem de F e cujo determinante ´e n˜ao nulo, isto ´e, GL
n
(F ) = {A|A ´e uma n × n
matriz com entradas de F e det(A) = 0 }, onde o determinante de qualquer matriz A com
entradas de F pode ser calculado pela mesmas f´ormulas usadas em F = R (Campo no
dom´ınio dos reais). Para matrizes arbitr´arias n ×n A e B deixe ser AB como o produto
destas matrizes como calculado pelas mesmas regras como quando F = R. Este produto
´e associativo. Tamb´em, desde que det(AB) = det(A) · det(B), segue que se det(A) = 0
e det(B) = 0, ent˜a o det(AB) = 0, log o GL
n
(F ) est´a fechado sobre multiplica¸c˜ao de
matrizes. Al´em do mais, det(A) = 0 se e somente se A po ssui uma matriz inversa, logo
cada A ∈ GL
n
(F ) possui uma inversa, A
−1
, em GL
n
(F ): AA
−1
= A
−
1A = I, onde I ´e
uma matriz identidade n×n. Assim GL
n
(F ) ´e um grupo sobre multiplica¸c˜ao de matrizes,
chamado tamb´em de grupo linear geral de ordem n [13].
2.9 Conclus˜ao
Este cap´ıtulo apresentou uma vis˜ao geral sobre criptografia tradicional bem como
os algoritmos que se utilizam de criptografia assim´etrica e/ou sim´etrica, uma an´alise sobre
DLPs (Problemas de Log aritmo Discreto), os algoritmos utilizados para tentar resolver
um DLP em menor tempo do que por busca exaustiva, uma an´alise comparativa entre
25
os a lgoritmos que resolvem um DLP e suas complexidades, al´em de uma breve descri¸c˜ao
sobre matrizes sobre campos finitos. No pr´oximo cap´ıtulo ser˜ao apresentados os principais
protocolos estudados para a an´alise e o desenvolvimento do DHA3, que s˜ao: Algor´ıtmo
Criptogr´afico Diffie-Hellman, El-Gamal, MTI, SPAKE, S-3PAKE, Needham-Schroeder,
γ = α
a
β
b
e Matrix rings. Sendo que ao final de cada se¸c˜ao algumas an´alises sobre
seguran¸ca de tais prot ocolos ser˜ao feitas.
26
Cap´ıtulo 3
Protocolos de Acordo de Chave
Neste Cap´ıtulo, ser˜ao apresentados os trabalhos relacionados ao DHA3. S˜ao proto-
colos de acordo de chave criptogr´afica que possuem sua complexidade baseada nos (DLPs)
problemas de logaritmo discreto. Os protocolos s˜ao o s seguintes: Diffie-Hellman, ElGa-
mal, MTI, CRTDH, Needham-Schoreder, SPAKE, S-3 PAKE, γ = α
a
β
b
e Matrix Rings.
3.1 Diffie-Hellman
O DH ´e o protocolo de acordo de chaves criptogr´a ficas mais utilizado nas aplica¸c˜oes
e implementa¸c˜oes. Os pro t ocolos de acordo de chave possuem um importante papel no
estabelecimento de um canal seguro de comunica¸c˜ao entre partes comunicantes. O DH
tamb´em pode ser chamado de um protocolo baseado em chave exponencial. A complexi-
dade para resolver tal algoritmo depende da aparente intratabilidade dos DLP’s. O DH
´e um protocolo de acordo de chave sem autentica¸c˜ao das partes baseado em DLP. O DH
[3] usa duas trocas para gerar a chave compartilhada K entre os n´os.
O DH requer um n´umero primo p e um gerador α ∈ Z
∗
p
, onde 2 ≤ α ≤ p − 1,
de forma que estes valores sejam pr´e compartilhados entre os n´os (usando, por exemplo,
um reposit´orio para armazenar e gerenciar tais valores), como mostrado no Passo 1 da
Figura 3.1. Depois destes procedimento s o n´o A realiza ent˜ao as opera¸c˜oes apresentadas
no Passo 2 e a mesma opera¸c˜ao ´e realizada pelo n´o B, como mostrado na Figura 3.1. No
passo 3 ambos os n´os enviam o resultado das opera¸c˜oes realizadas no Passo 2. Ao final
no Passo 4 cada n´o ir´a calcular a chave compartilhada atrav´es das mensagens recebidas
no Passo 2. Este pro tocolo opera com uma troca, com duas mensagens entre os n´os. A
chave gerada pelo DH ter´a a mesma magnitude do primo p utilizado.
Para melhor explana¸c˜ao do Diffie-Hellman, a seguir ´e apresent ado um exemplo
num´erico de tal pro tocolo. Considerando o n´umero primo p = 7, o gerador α = 3, x = 4
27
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo grande p e num gerador α.
2 Escolhe um n´umero
aleat´orio grande
1 ≤ x ≤ p − 2 e cal-
cula z
1
= α
x
mod p
Escolhe um n´umero
aleat´orio gr ande
1 ≤ y ≤ p − 2 e cal-
cula z
2
= α
y
mod p
3 z
1
⇒
⇐ z
2
4 Calcula sua chave K =
(z
2
)
x
mod p = (z
1
)
y
mod
p
Calcula sua chave K =
(z
1
)
y
mod p = (z
2
)
x
mod
p
Figura 3.1 : Protocolo de acordo de chave Diffie-Hellman.
e y = 5, assim as mensagens trocadas entre os n´os A e B s˜ao as equa¸c˜oes (3.1) e (3.2),
sendo (3.3) a chave compartilhada gerada por cada n´o:
z
1
: 3
4
mod 7 = 4 (3.1)
z
2
: 3
5
mod 7 = 5 (3.2)
K = (z
1
)
5
mod 7 = (z
2
)
4
mod 7 = 2 (3.3)
O exemplo apresentado ´e muito f´acil de ser quebrado. Para que isso n˜ao ocorra o
n´umero primo utilizado dever´a ter uma precis˜ao de 1024 bits a 2048 bits, que gera um
n´umero de 300 a 500 digitos decimais. Tal sistema provˆe prote¸c˜ao contra ataques passi-
vos (eavesdroppers), mas n˜ao contra ataques ativos onde o advers´ario pode interceptar,
modificar, ou mesmo injetar mensagens falsas. Nenhuma parte tem certeza da identidade
do outro e nem mesmo da identidade da outra parte a qual est´a se gerando a chave, sem
autentica¸c˜ao qualquer.
De forma gen´erica o DLP pode ser definido como sendo: dado um primo p, um
gerador α sobre Z
∗
p
[3], e α
a
mod p, encontre a.
3.2 ElGamal
O Protocolo ElGamal tamb´em ´e baseado na complexidade de resolver o DLP. A
Figura 3.2 apresenta o funcionamento do ElGamal.
O pro tocolo de acordo de chave ElGamal [3] ´e uma var ia nte do Diffie-Hellman
provendo um protocolo de apenas um passo (troca de apenas uma mensagem) com a
28
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo grande p e num gerador α.
2 Escolhe um n´umero
aleat´orio gr ande
1 ≤ y ≤ p − 2 e cal-
cula z
2
= α
y
mod p e
torna z
2
p´ublico a t r av´es de
certificado.
3 Escolhe um n´umero
aleat´orio grande
1 ≤ x ≤ p − 2 e cal-
cula z
1
= α
x
mod p
4 z
1
⇒
5 Calcula sua chave K =
(z
2
)
x
mod p = (z
1
)
y
mod
p
Calcula sua chave K =
(z
1
)
y
mod p = (z
2
)
x
mod
p
Figura 3.2 : Protocolo de acordo de chave El Gamal.
autentica¸c˜ao de chave unilateral (Do receptor para o originador da troca), provida atrav´es
da chave do receptor que ´e conhecida a priori pelo originador, sendo esta, por exemplo
embutida num certificado podendo assim verificar a sua autenticidade. Ambos os n´os
selecionam o mesmo primo p e um gerador α ∈ Z
∗
p
, passo 1 da Figura 3.2. O n´o B
seleciona um n´umero inteiro y, e realiza o pa sso 2 da Figura 3.2. Ap´os estes procedimentos,
o n´o A pega uma c´opia da chave p´ublica de B (p, α, z
2
), para ent˜ao o n´o A realizar o pa sso
3. No passo 4, envia z
1
para o n´o B. No passo 5, cada n´o computa sua chave, sendo que
a chave gerada em cada n´o ser´a a mesma.
Um exemplo pr´a tico de tal protocolo ´e mostrado a seguir. Tomando como base os
seguintes valores p = 7, α = 3, x = 4, y = 5, a chave p´ublica de B em (3.4), o n´o A envia
para B (3.5), assim cada n´o ir´a gerar a mesma chave K em (3.6).
(p, α, z
2
) = (7, 3, 5) (3.4)
z
1
: 3
4
mod 7 = 4 (3.5)
K = (z
1
)
5
mod 7 = (z
2
)
4
mod 7 = 2 (3.6)
O protocolo ElGamal gera apenas uma mensagem devido ao fato do n´o B previ-
amente colocar os seus dados p´ublicos em um servidor de chaves p´ublicas (por exemplo,
embutido num certificado), de outra maneira este protocolo seria como o Diffie-Hellman,
29
e somente existe a autenticidade dos dados do n´o B para o n´o A devido ao fato novamente
do Servidor de chaves p´ublicas ser requerido por este protocolo. Em termos de comple-
xidade para resolver o ElGamal, enquadra-se no mesmo caso do DH que ´e resolver DLP
[3].
3.3 Protocolo MTI
O Protocolo MTI tamb´em ´e baseado na complexidade para resolver o DLP. O MTI
[3] ´e um protocolo de acordo de chave realizado em uma troca com duas mensagens entre
os n´os participantes. O MTI/A0 ´e uma variante do DH, com a vantagem de garantir a
autenticidade das chaves p´ublicas de cada n´o participante do acordo de chave, devido ao
fato de estas chaves p´ublicas estarem embutidas em certificados, sendo assim poss´ıvel ve-
rificar a autenticidade das mesmas. De maneira semelhante aos dois protocolos discutidos
anteriormente, s˜ao escolhidos um primo p e um gerador α ∈ Z
∗
p
, 1 ≤ α ≤ p − 2. Estes
dados s˜ao armazenados num servidor como mostrado no passo 1 da Figura 3.3.
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo grande p e num gerador α , arma-
zenados em servidor de chaves p´ublicas.
2 Escolhe um n´umero
aleat´orio grande
1 ≤ a ≤ p − 2 e cal-
cula uma chave p´ublica
z
A
= α
a
mod p
Escolhe um n´umero
aleat´orio gr ande
1 ≤ b ≤ p − 2 e cal-
cula uma chave p´ublica
z
B
= α
b
mod p
3 Escolhe 1 ≤ x ≤ p − 2, cal-
cula z
1
= α
x
mod p
Escolhe 1 ≤ y ≤ p − 2, cal-
cula z
2
= α
y
mod p
4 z
1
⇒
⇐ z
2
5 Calcula sua chave K =
(z
2
)
a
(Z
B
)
x
mod p
Calcula sua chave K =
(z
1
)
b
(Z
A
)
y
mod p
6 Os n´os geram a mesma chave K = α
bx+ay
.
Figura 3.3 : Protocolo de acordo de chave MTI/A0.
O n´o A seleciona uma chave privada que ´e um inteiro aleat´orio a, passo 2, Figura
3.3. De forma an´aloga, passo 2, B gera b e Z
B
. Os n´os A e B possuem acesso aos
certificados de cada um dos n´os, sendo assim poss´ıvel obter as chaves p´ublicas autenticadas
de cada um dos n´os. O n´o A escolhe um segredo a leat´orio x e realiza o passo 3, tal que
1 ≤ x ≤ p − 2. N´o B escolhe um segredo aleat´orio y e realiza as opera¸c˜oes descritas no
30
passo 3 da Figura 3.3. No passo 4, os n´os enviam o s resultados das opera¸c˜oes realizadas
no passo 3. O s n´os A e B computam suas respectivas chaves como mostrado no passo 5.
No passo 6, ambos os n´os acabam por compartilhar a mesma chave.
Considere um exemplo num´erico do proto colo MTI/A0 que servir´a de base para a
an´alise e compreens˜ao do seu funcionamento. Sendo primo p = 19, α = 3, a = 5, b = 6,
x = 7 e y = 9. Assim, r esulta-se que z
A
= α
a
mod p = 15 e z
B
= α
b
mod p = 7. D essa
forma o n´o A envia para o n´o B equa¸c˜ao (3.7), em seguida o n´o B envia pra n´o A (3.8).
Ap´os estes procedimentos cada n´o gera sua pr´opria chave que acaba sendo a mesma chave
compartilhada n´o A (3.9) e n´o B (3.10), mostrando que as chaves geradas s˜ao as mesmas.
z
1
= α
x
mod p = 2 (3.7)
z
2
= α
y
mod p = 18 (3.8)
K = (18)
5
(7)
7
mod 19 = 12 (3.9)
K = (2)
6
(15)
9
mod 19 = 12 (3.10)
O MTI possui quatro variantes, a a presentada acima ´e a MTI/A0. As demais se
diferenciam pelas informa¸c˜oes que s˜ao trocadas entre os n´os e os expoentes escolhidos
para as chaves p´ublicas. A Tabela 3.1 apresenta estas varia¸c˜oes, levando em considera¸c˜a o
que z
A
= α
a
mod p e que z
B
= α
b
mod p. Onde K
A
e K
B
denotam as chaves geradas
em cada n´o que representam ao final dos procedimentos a mesma chave K.
Tabela 3.1: Variantes do MTI
Protocolo z
1
z
2
K
A
K
B
Chave K
MTI/A0 α
x
α
y
α
y a
· Z
x
B
α
xb
· Z
y
A
α
bx+ay
MTI/B0 z
x
B
z
y
A
(z
y
A
)
a
−1
· α
x
(z
x
B
)
b
−1
· α
y
α
x+y
MTI/C0 z
x
B
z
y
A
(z
y
A
)
a
−1
x
(z
x
B
)
b
−1
y
α
xy
MTI/C1 z
xa
B
z
y b
A
(z
y b
A
)
x
(z
xa
B
)
y
α
abxy
Apesar dos protocolos MTIs implementarem a autentica¸c˜ao das chaves p´ublicas
(z
A
e z
B
) estes protocolos s˜ao sucept´ıveis a ataques ativos, logo devem ser utilizados
em contextos onde apenas at aques passivos sejam poss´ıveis [3]. Mas mesmo assim ta l
protocolo ainda trabalha com um mesmo gerador α o que permite a solu¸c˜ao por DLP.
Com rela¸c˜ao a complexidade computacional dos protocolos MTI tˆem-se : Os pro t ocolos A0
e B0 requerem 3 expo nencia¸c˜oes por cada n´o, enquanto que o C0 e o C1 requerem apenas
2 exponencia¸c˜oes (A complexidade para resolver uma exponencia¸c˜ao ´e O((log p)
3
)). O C1
apresenta uma vantagem em rela¸c˜ao ao B0 e o C0 que ´e o fato de n˜ao requerer o c´alculo
da inversa multiplicativa (A complexidade para calcular a inversa ´e (O((log p)
2
))) [3].
31
3.4 Protocolo Needham-Schroeder
O protoclo Needham-Schroeder [3] ´e ba seado em criptografia por chave p´ublica e
pode ser usado para um acordo de chave criptogr´afica. Dois n´os desejando estabelecer uma
chave de sess˜ao ir˜a o compartilhar duas chaves secretas sim´etricas, e ao final do protocolo
cada n´o ir´a calcular o hash das chaves compartilhadas para ent˜ao gerar a chave da sess˜ao.
Nota¸c˜ao: P
X
(Y ) representa a cifragem com algoritmo de chave p´ublica do dado Y usando
a chave p´ublica do n´o X; P
X
(Y
1
, Y
2
) representa a cifragem da concatena¸c˜ao dos dados Y
1
e
Y
2
; k
1
e k
2
s˜ao as chaves secretas sim´etricas pertencentes aos n´os A e B, respectivamente.
Neste protocolo assume-se a priori que cada n´o possui a chave p´ublica autˆentica do
outro n´o atrav´es de certificados e/ou outra fo r ma de garantir a autenticidade das chaves
p´ublicas utilizadas. Caso n˜ao po ssuam as chaves p´ublicas autenticadas passos adicionais
ser˜ao necess´arios neste protocolo para a obten¸c˜ao das chaves. A Figura 3.4 apresenta o
funcionamento deste protocolo.
Passo N´o A Trocas N´o B
1 Utiliza a chave p´ublica de B
para gerar z
1
= P
B
(k
1
)
2 z
1
⇒
3 Utiliza a chave p´ublica de A
para gerar z
2
= P
A
(k
1
, k
2
)
4 ⇐ z
2
5 Verifica os dados recebidos e
se estiver correto gera z
3
=
P
B
(k
1
, k
2
)
6 z
3
⇒
7 Caso os dados estejam
em conformidade ge-
rar´a a chave de sess˜a o
K = h(k
1
, k
2
) a tr av´es de
uma fun¸c˜ao de h ash.
Verifica os dados recebidos
e calcula o hash das chaves
para gerar a chave de sess˜a o
K = h(k
1
, k
2
).
Figura 3.4 : Funcionamento do protocolo Needham-Schroeder.
O protocolo ´e realizado com trˆes trocas de mensagens: O n´o A realiza o passo 1
e no passo 2 envia para o n´o B sua chave sim´etrica cifrada. O n´o B ao receber z
1
obt´em
k
1
, e com isso no passo 3 calcula z
2
e no passo 4 envia z
2
para A. O n´o A ao receber
z
2
verifica se a chave k
1
recuperada, ir´a coincidir com a chave enviada no passo 2. Caso
coincida, ele gera z
3
no passo 5 e envia para B no passo 6, caso n˜ao coincida ele termina
32
o protocolo e n˜ao estabelece comunica¸c˜ao com B. O n´o B ao receber z
3
verifica se a chave
k
2
coincide com a chave enviada no passo 4, caso coincida este realizar´a o passo 7 que
´e um hash das chaves k
1
e k
2
para obter a chave de sess˜ao; o mesmo procedimento ser´a
realizado por A para gerar a chave de sess˜ao K.
Contudo, este protocolo requer uma Autoridade Certificadora para garantir que as
chaves p´ublicas utilizadas no protocolo sejam autˆenticas, e apesar de realizar o procedi-
mento para o acordo da chave de sess˜ao em apenas trˆes tro cas, este protocolo poder´a vir
a requisitar passos adicionais caso os n´os n˜ao possuam as chaves p´ublicas um do outro.
O protocolo de acordo de chave proposto nesta disserta¸c˜ao (DHA3) n˜ao autentica as en-
tidades comunicantes sem que haja a interven¸c˜ao de um TTP (Trusted Third Party). O
mesmo ocorre com o prot ocolo do Needham - Schroeder, pois caso os n´os apenas troquem
as chaves p´ublicas n˜ao haver´a como garantir a autenticidade das mesmas.
3.5 CRTDH e Grupos S eguros de Comunica¸c˜ao
Nesta se¸c˜ao ser´a fornecido um embasamento sobre Grupos Seguros de Comunica¸c˜ao
antes de discutir sobre o protocolo CRTDH. Em redes cabeadas, normalmente o s servi¸cos
de seguran¸ca como autentica¸c˜ao, gerenciamento de chaves e autoriza¸c˜a o s˜ao realizados por
um TTP servidor centralizado. Em ambientes ad-hoc ta is tipos de servi¸cos como uma CA
n˜ao s˜a o geralmente dispon´ıveis, de forma que os pr´oprios membros pertencentes a tal rede
dever˜ao prover tais servi¸cos de seguran¸ca po r eles mesmos. Considerando-se um cen´ario
onde um n´umero de n´os m´oveis f orma uma rede ad- h oc sem qualquer conhecimento pr´evio,
pode-se definir o que ´e um SGC (Secure Group of Communica tion) ou Grupo Seguro de
Comunica¸c˜ao.
Um SGC ´e definido como o processo pelo qual membros de um grupo podem segu-
ramente comunicar-se entre si e a informa¸c˜ao sendo transmitida ´e inacess´ıvel a qualquer
elemento que n˜ao perten¸ca ao grupo [14]. No cen´ario citado acima, uma chave de grupo
´e compartilhada pelos membros deste grupo e esta chave ´e utilizada para cifrar todas
as mensagens trafegadas neste grupo. Um SGC deve evitar a serializa¸c˜ao dos membro s,
onde a informa¸c˜ao ´e transmitida de membro a membro numa seq¨uˆencia pr´e-definida para
ent˜ao ser criada a chave do grupo. D evido ao fato da mobilidade e o dinamismo de redes
ad-hoc a serializa¸c˜ao deve ser evitada. Um SGC deve possuir um bom mecanismo para o
compartilhamento da chave do grupo.
O protocolo de acordo de chaves utilizado por SGC deve ser eficiente na quest˜ao
de economizar energia nos c´alculos computacionais e no uso do canal de comunica¸c˜ao. Os
n´os de uma rede ad-hoc geralmente possuem limita¸c˜oes no consumo da bateria. Tamb´em
33
num SGC deve-se levar em conta que usu´arios m´oveis entrar˜ao e sair˜ao do grupo com
um dinamismo alto. Assim um bom SGC deve cuidar destes asp ectos para controlar
corretamente a taxa de atualiza¸c˜ao das chaves de sess˜ao ao ponto de garantir a seguran¸ca
da comunica¸c˜ao e ao mesmo tempo n˜ao inferir num alto consumo computacional dos novos
membros que ir˜ao participar do grupo.
Em [14] ´e proposto um protocolo para acordo de chaves para SGC, que utiliza o DH
e o Teorema do Resto Chinˆes CRT (Chin ese Remainder Theorem), sendo que a propo sta
´e denominada pelos autores como CRTD H. Cada membro do grupo dever´a executar 7
passos, sendo n o n´umero de membros e i = 1, ···, n e i representa o i-´esimo membro,
sendo ⊕ a opera¸c˜a o bin´aria XOR. Estes passos s˜ao descritos a seguir:
Passo 1 : Cada n´o seleciona os seus parˆametros privados do DH os x
i
e cada n´o calcula
os seus parˆametros p´ublicos (3.11).Os parˆametros α e p s˜ao o gerador e primo
usados nas opera¸c˜o es do DH. Estas informa¸c˜o es s˜ao p´ublicas e se os n´os n˜ao as
compartilham, ent˜ao um broadcast de tais informa¸c˜oes se faz necess´ario.
Passo 2 : Realizar o broadcast dos parˆametros p´ublicos y
i
de cada n´os entre todos os
membros do grupo.
Passo 3 : Receber os parˆametros p´ublicos de todos os outros membros do grupo e calcu-
lar a chave DH compartilhada com cada um deles (3.12), onde j = 1, ···, i − 1, i +
1, ···, n.
Passo 4 : Encontrar o M´ınimo M´ultiplo Comum LCM (Least Commom Multiple) de
todas as chaves DH calculadas no Passo 3, denominado de lcm
i
.
Passo 5 : Selecionar um valor aleat´orio k
i
, tal que k
i
< min(m
ij
, ∀j), que ser´a compar-
tilhado com o grupo. Tamb´em selecionar um n´umero arbitr´ario D tal que D = k
i
e
outro n´umero D
p
tal que gcd ( D
p
, l cm
i
) = 1, onde gcd ´e o m´aximo divisor comum.
Passo 6 : Resolver os CRTs (3.14), realizar um broadcast destes valores obtidos para o
grupo.
Passo 7 : Receber os resultados dos c´alculos dos CRT’s de todos os outros membros do
grupo e calcular (3.15) para todos os j = i. Por fim, calcular a GK chave do grupo
que ser´a utilizado pelo grupo para estabelecer um canal seguro de comunica¸c˜ao
(3.16).
y
i
= α
x
i
mod p (3.11)
34
m
ij
= y
x
i
j
mod p (3.12)
gcd(D
p
, l cm
i
) = 1 (3.13)
crt
i
≡ k
i
mod lcm
i
, crt
i
≡ D mod D
p
(3.14)
k
j
= crt
j
mod m
ij
(3.15)
GK = k
1
⊕ k
2
⊕ ··· ⊕ k
n
(3.16)
Caso um novo membro U decida pa rt icipar do SGC este dever´a realizar os passos
de 1 a 6, sendo que no s´etimo passo o novo membro ir´a receber um hash da chave do
grupo para ent˜ao realizar o XOR com o seu k
U
, gerando (3.17).
GK
novo
= h(GK) ⊕ k
U
(3.17)
Se um um dos membros do grupo desejar sair do grupo, o gr upo dever´a escolher
um dos membros restantes (membro 1, por exemplo) e elegˆe-lo para realizar os passos do
acordo de chave (de 1 a 7) novamente e assim calcular a nova chave do grupo (3.18) .
GK
novo
= GK ⊕ k
1
(3.18)
Considerando somente a parte do acordo de chave e da quest˜ao do SGC, vˆe-se
que um SG C nada mais ´e do que um servidor de autentica¸c˜ao visto sob outra ´otica. O
SGC passa a responsabilidade da autentica¸c˜ao e da integridade para o grupo que em
outros modelos de acordos de chave a responsabilidade da autentica¸c˜ao ´e do servidor de
autentica¸c˜ao. Logo, o protocolo DHA3 que ´e um protocolo sem autentica¸c˜ao das partes,
usado para o acordo da chave de sess˜ao, permite que a responsabilidade da autentica¸c˜ao e
da integridade seja feita pelos n´os que desejarem estabelecer o acordo de chave, ou utilizar
um servidor de autentica¸c˜ao para realizar a autentica¸c˜ao onde cada n´o disponibilizar´a seus
parˆametros p´ublicos neste servidor.
3.6 SPAKE
SPAKE (Simple Password-ba s ed Encrypted Key Exchange Protocol) [7] tamb´em
´e considerado como uma pequena varia¸c˜ao do pro tocolo DH, por´em nesta varia¸c˜ao os
n´os compartilham uma senha secreta chamada de pw. Esta senha servir´a de base para
gerar a chave de sess˜ao que ser´a utilizada por ambos os n´os. Este protocolo utiliza alguns
parˆametros p´ublicos que s˜ao: G ´e um grupo finito c´ıclico, α ´e o gerador sobre p onde p ´e o
35
n´umero primo utilizado; M, N s˜ao n´umeros aleat´orios pertencentes a G, e h() representa
uma fun¸c˜ao de h ash. Dessa forma o protocolo ´e realizado com duas trocas. A Figura 3.5
mostra o funcionamento deste protocolo.
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo g r ande p e num gerador α e numa
senha pw.
2 Escolhe um n´umero
aleat´orio grande 1 ≤ x ≤
p − 2 para ent˜ao calcular
z
1
= α
x
· M
pw
mod p.
Escolhe um n´umero
aleat´orio gr ande
1 ≤ y ≤ p−2 para ent˜ao cal-
cular z
2
= α
y
· N
pw
mod p.
3 z
1
⇒
4 ⇐ z
2
5 Calcula K
A
= (
z
2
N
pw
)
x
mod p,
SK
A
= h(A, B, z
1
, z
2
, K
A
)
Calcula K
B
=
(
z
1
M
pw
)
y
mod p, SK
B
=
h(A, B, z
1
, z
2
, K
B
)
6 Ambos os n´os possuem a mesma chave SK
A
= SK
B
.
Figura 3.5 : Funcionamento do protocolo SPAKE.
Primeiramente o n´o A realiza o passo 2, e calcula z
1
e ent˜ao o envia para o n´o B no
passo 3. O n´o B por sua vez, similarmente ao n´o A gera z
2
para ent˜ao enviar para o n´o A
no passo 4. No passo 5, cada n´o calcula a chave de sess˜ao gerada e ainda a a plicam numa
fun¸c˜ao de hash as informa¸c˜oes trocadas, mais os dados gerados das trocas realizadas. Ao
final, no passo 6 os n´os possuir˜ao a mesma chave de Sess˜ao.
Entretanto este protocolo ´e suscept´ıvel a ataque de senha (password), devido a o
fato que uma senha ´e limitada a alguns caracteres e s´ımbolos e n˜ao a todo o universo que
um byte p ode armazenar (2
8
poss´ıveis valo res). Existe neste protocolo uma autentica¸c˜a o
m´utua, devido a o compartilhamento de um segredo o p w, assim ambos devem conhecer
as qualifica¸c˜oes um do outro antes de estabelecer um canal seguro de informa¸c˜ao.
3.7 S-3PAKE
No protocolo S-3PAKE (S i mple Three-Party Key Exchan ge Protocol) os autores
[7] sugerem um m´etodo para troca autenticada de uma chave de sess˜a o sem a presen¸ca
de um servidor de chaves p´ublicas. No entanto ´e necess´ario um servidor confi´avel para
autenticar as partes. Algumas defini¸c˜oes que s˜ao utlizadas por esse protocolo: G:Gr upo
36
finito c´ıclico; α: gerador sobre p; p: primo para campo finito; M, N: n´umeros aleat´orios
sobre o grupo G; S: servidor confi´avel; pw1 : senha compartilhada entre o n´o A e S; pw2:
senha compartilhada entre o n´o B e S; H, H
′
: fun¸c˜oes de hash; X||Y : concatena¸c˜ao das
informa¸c˜oes X e Y.
No S-3PAKE, considerar que dois n´os A e B desejam entrar em acordo numa chave
de sess˜a o. Entretanto, como nenhum dos n´os possui qualquer conhecimento a priori do
outro, n˜a o podem autenticar-se mutuamente e faz-se necess´ario um servidor confi´avel aos
quais ambos os n´os possuem uma senha compartilhada com tal servidor. A Figura 3.6
descreve o funcionamento do S-3PAKE.
Passo N´o A N´o B Servidor S
1 Envia X = α
x
· M
pw1
para n´o A
2 Y = α
y
· N
pw2
3 Envia X||Y para S
4 α
x
=
α
x
M
pw1
; α
y
=
Y
N
pw2
5 α
xz
= (α
x
)
z
; α
y z
= (α
y
)
z
6 X
′
= α
y z
·H(A, S, α
x
)
pw1
Y
′
= α
xz
·H(B, S, α
y
)
pw2
7 Envia para n´o B X
′
||Y
′
8 α
xz
=
Y
′
H(B,S,α
y
)
pw2
α
xyz
= (α
xz
)
y
γ = H(A, B, α
xyz
)
9 Envia X
′
||γ para n´o A
10 α
y z
=
X
′
H(A,S,α
x
)
pw1
α
xyz
= (α
y z
)
x
SK
A
= H
′
(A, B, α
xyz
)
11 Envia para o n´o B:
β = H(B, A, α
xyz
)
12 SK
B
= H
′
(A, B, α
xyz
)
Figura 3.6 : Funcionamento do protocolo S-3PAKE.
No passo 1, o n´o A escolhe um n´umero aleat´orio x ∈ Z
p
, e envia X para B. B
no passo 2, escolhe um n´umero aleat´orio y ∈ Z
p
e computa Y , para ent˜ao envi´a-lo para
o servidor S no passo 3. Ao receber os dados do n´o B, o servidor usa as senhas pw1 e
37
pw2 para calcular os dados do passo 4. Assim, S escolhe outro n´umero aleat´orio z ∈ Z
p
no passo 5, e realiza o passo 6. Finalmente, S envia para B X
′
||Y
′
no passo 7. Quando
B recebe X
′
||Y
′
este usa pw2 para realizar o passo 8 . Por fim, B encaminha X
′
||γ para
A atrav´es do passo 9. No passo 10, A recebe X
′
||γ, ent˜ao A checa se o γ recebido ´e o
mesmo do calculado. Se n˜a o for o mesmo A termina o protocolo e desiste da comunica¸c˜ao
com B. Caso γ seja o mesmo A ´e convencido de que α
xyz
´e v´alido. E neste caso, ele
pode computar a chave de sess˜ao SK
A
apresentada no passo 10 e enviar β para B para
que seja verificado atrav´es do passo 11. B ao receber β verifica se β ´e verdadeiro. Se for
verdadeiro, B calcula a chave de sess˜ao SK
B
atrav´es do passo 12, caso n˜ao seja, desiste da
comunica¸c˜ao com A. Ao final do protocolo ambos os n´os ter˜ao a mesma chave de sess˜ao
(3.19).
SK
A
= SK
B
= H
′
(A, B, α
xyz
) (3.19)
3.8 Sistema Criptogr´afico baseado em DLP γ = α
a
β
b
Neste protocolo criptogr´afico os auto r es [5] prop˜oem o uso de dois gerador es distin-
tos α e β pertencentes a Z
∗
p
, onde os autores consideram que tal protocolo exige que sejam
resolvidos dois DLPs um para cada gerador. No entanto, t al afirma¸c˜ao n˜ao ´e consistente
e ser´a explanada ap´os a explica¸c˜ao do funcionamento de tal protocolo.
Este protocolo requer um n´umero primo p e dois g eradores α e β, onde 2 ≤ α, β ≤
p − 1, de forma que estes valo r es sejam pr´e compartilhados entre os n´o s (usando, por
exemplo, um reposit´orio para armazenar e gerenciar tais valores), como mostrado no
Passo 1 da Figura 3.7. Depois destes procedimentos o n´o A realiza ent˜ao as opera¸c˜oes
apresentadas no Passo 2 e a mesma opera¸c˜a o ´e realizada pelo n´o B, como mostrado na
Figura 3.7. No passo 3, ambo s os n´os enviam o resultado das opera¸c˜oes realizadas no
Passo 2. Ao final no Passo 4, cada n´o ir´a calcular a chave compartilhada atrav´es das
mensagens recebidas no Passo 2. O Passo 5 mostra a chave equivalente gerada em cada
n´o. Este protocolo opera com duas trocas entre os n´os, mas ´e realizado o envio de dois
parˆametros para cada troca.
Segundo [6] apesar dos autores deste protocolo justificarem que ´e necess´ario realizar
dois DLPs tal afirma¸c˜ao n˜ao ´e verdadeira devido ao fato de que o gerador β est´a sobre
Z
∗
p
de forma que pode ser considerado como sendo um fator de α, β = α
m
, logo γ =
α
a
β
b
pode ser reescrito da seguinte maneira γ = α
a
· (α
m
)
b
= α
a
· (α
mb
) = α
a+mb
.
Assim bastar´a resolver apenas um DLP para α
a+mb
. Al´em do protocolo n˜ao aumentar a
complexidade, pois pode ser resolvido atrav´es de apenas um DLP ainda transmite o dobro
de informa¸c˜oes que o protocolo DH transmite. Sendo assim, tal protocolo n˜ao apresenta
38
vantagens criptogr´aficas e nem de desempenho na implementa¸c˜a o real dele.
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo grande p e nos geradores α e β.
2 Escolhe dois n´umeros
aleat´orios grandes
1 ≤ a, b ≤ p − 2 e cal-
cula z
1
= α
a
mod p e
z
2
= β
b
mod p
Escolhe dois n´umeros
aleat´orios grandes
1 ≤ c, d ≤ p − 2 e cal-
cula z
3
= α
c
mod p e
z
4
= β
d
mod p
3 z
1
|z
2
⇒
⇐ z
3
|z
4
4 Calcula sua chave K =
(z
3
)
a
· (z
4
)
b
mod p
Calcula sua chave K =
(z
1
)
c
· (z
2
)
d
mod p
5 Os n´os obtˆem a mesma chave K = α
ac
· β
bd
mod p.
Figura 3.7 : Protocolo de acordo de chave baseado em D L P γ = α
a
β
b
.
3.9 Protocolo Matrix Rings
Em [8] ´e proposto o primeiro protocolo que utiliza uma matrix como gerador base
para o DH numa tentativa de aumentar a complexidade da criptoan´alise. O protocolo
proposto requer que ambos os n´os compartilhem um n´umero primo grande p e uma matriz
geradora A ∈ GL
n
, tal que seja invers´ıvel e ainda admita um expoente r que, ao realizar
A
r
gere-se a matriz identidade A
r
= I (mod p). O parˆametro r deve tamb´em ser compar-
tilhado entre os n´os. Considerando a comunica¸c˜ao entre o n´o A e o n´o B, o n´o A escolhe
o segredo 1 ≤ x < r e o n´o B escolhe 1 ≤ y < r. Assim, cada n´o realiza os passos apresen-
tados na Figura 3.8, que ´e exatamente o pro cedimento realizado no Diffie-Hellman, mas
com a diferen¸ca de que o gerador base ´e uma matriz de ordem r. No entanto a matriz A
requer alguns procedimentos extras para ser criada e al´em disso ´e necess´ario determinar
a magnitude do parˆametro r conforme a seguir:
Dado um po linˆomio irredut´ıvel f(x) de grau m
f(x) = a
0
+ a
1
x + a
2
x
2
+ ··· + a
m−1
x
m−1
a
i
∈ GF (p), (3.20)
39
uma matriz B ´e constru´ıda com os parˆametros do polinˆomio f(x) conforme
B =
0 1 0 ··· ··· 0
0 0 1 ··· ··· 0
.
.
.
−a
m−1
−a
m−2
−a
m−3
··· ··· −a
0
, (3.21)
sendo que a ordem da matriz B ´e p
m
−1, e logo B
p
m
−1
= I. Devem ser escolhidas o utras
matrizes B
i
sobre GL
n
, com ordens m
1
, m
2
, ···, m
i
:
B =
B
1
B
2
.
.
.
B
i
. (3.22)
O expoente r ´e:
LCM{(p
m
1
− 1), (p
m
2
− 1), (p
m
3
− 1), ···, (p
m
i
− 1)}. (3.23)
A matriz A pode ser obtida atrav´es da conjuga¸c˜ao com uma matriz Y :
A = Y · B · Y
−1
, (3.24)
sendo que todas as matrizes utilizadas neste m´etodo devem ser n˜ao singulares, o que
significa matrizes invers´ıveis.
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo p, matriz A e num expoente r.
2 Escolhe um n´umero
aleat´orio grande 1 ≤ x < r
e calcula z
1
= A
x
mod p
Escolhe um n´umero
aleat´orio grande 1 ≤ y < r
e calcula z
2
= r
y
mod p
3 z
1
⇒
⇐ z
2
4 Calcula sua chave K =
(z
2
)
x
mod p = (z
1
)
y
mod p
Calcula sua chave K =
(z
1
)
y
mod p = (z
2
)
x
mod p
1 ambos os n´os obtˆem a mesma chave K = z
x
2
= z
y
1
= A
xy
.
Figura 3.8 : Protocolo Matrix Rings.
40
Em [9] s˜ao apresentados m´etodos para diminuir a complexidade do Matrix Rings.
O primeiro m´etodo ´e o Baby-Step Giant-Step [3 ] que pode ser aplic´avel devido as matrizes
utilizadas serem invers´ıveis e em O(
√
r) no pior caso encontrar-se-ia uma solu¸c˜ao para o
m´etodo Matrix Rings. Outra forma de diminuir a complexidade de tal m´etodo ´e quando
o expoente r n˜ao ´e um n´umero primo, podendo-se utilizar o CRT para encontrar uma
solu¸c˜ao, conforme descrito em [9]. Mas al´em disso, este m´etodo apresenta uma desva nta-
gem que ´e a dimens˜ao da matriz geradora A que pode ser n ×n e como cada elemento de
tal matriz est´a sobre a precis˜ao do primo p, a quantidade de informa¸c˜a o transmitida por
cada n´o em cada troca ´e de aproximadamente n
2
·p. Considere uma matriz A de dimens˜ao
5×5 e um n´umero primo de 1024 bits de precis˜ao . Cada n´o enviaria 5
2
·1024 = 25600 bits
de informa¸c˜ao, 25 vezes mais informa¸c˜ao que o DH. Sendo que em certos cen´arios onde
os dispositivos (n´os) comunicantes possuem limita¸c˜ao de bateria (a transmiss˜ao consome
muito mais que o processamento) n˜ao seria vantajoso utilizar tal m´etodo.
3.10 Protocolo de Acordo de Chaves Baseado em Ma-
trizes Inversas
Passo N´o A Trocas N´o B
1 Escolhe aleatoriamente uma
matriz A de dimens˜ao k ×
n e calcula sua inversa A
−1
,
calcula z
1
= A · A
−1
2 z
1
⇒
3 Escolhe aleatoriamente uma
matriz B de dimens˜ao m ×
m e calcula sua inversa B
−1
,
calcula z
2
= z
1
· B e z
3
=
z
1
· B · B
−1
4 ⇐ z
2
, z
3
5 Calcula z
4
= A ·A
−1
·A ·B ·
B
−1
= A · B ·B
−1
6 z
4
⇒
7 Calcula a chave K como
sendo K = A ·A
−1
·A ·B =
A · B.
Calcula a chave K como
sendo K = A ·B ·B
−1
·B =
A · B.
Figura 3.9 : Acordo de Chaves com Matrizes Inversas.
41
Este protocolo [15] se utiliza de matrizes n˜ao singulares para realizar um acordo
chaves sem autentica¸c˜ao das partes com o intuito de dificultar a criptoan´alise do DH. O
objetivo dos autores [15] ´e utilizar matrizes com valores bin´arios 1 ou 0. A dificuldade
de se resolver tal m´etodo segundo os autor es estaria na resolu¸c˜ao de um sistema de
equa¸c˜oes lineares onde ter-se-ia mais inc´ognitas do que equa¸c˜oes. As matrizes geradas
neste protocolo est˜ao sobre os campo finito Z
∗
2
. O funcionamento do protocolo pode ser
visto na Figura 3.9.
Tabela 3.2: Compara¸c˜ao dos Protocolos
Protocolo Utiliza
Parˆametros
Pr´e -
Comparti-
lhados
Quantidade
de
Parˆametros
Pr´e - Com-
partilhados
N´umero
de
Trocas
Realiza
Auten-
tica¸c˜ao
Precis˜ao
da Chave
Diffie-Hellman X 2 2 Primo p
ElGamal X 3 1 Primo p
MTI X 4 2 Primo p
Needham-
Schroeder
X 2 3 X Hash
CRTDH (n n´os) X 3 · n + 2 3 · n -
SPAKE X 6 2 Hash
S-3PAKE X 7 5 X Hash
DLP γ ≡ α
a
β
b
X 7 2 Primo p
Matrix Rings X Matriz, p e r 2 Primo p
Matriz Inversa X p 3 Primo p
No entanto segundo [16] pode-se reduzir significativamente a complexidade de tal
protocolo devido ao f ato do mesmo apresentar trˆes trocas, se forem capturadas as mensa-
gens z
1
, z
2
e z
3
, pode-se implementar um sistema linear onde seria facilmente encontrada
a matriz B utilizada pelo n´o B, ou mesmo poderia ser feito se fossem utilizadas as mensa-
gens z
2
, z
3
e z
4
afim de montar um sistema linear de equa¸c˜oes para descobrir a matriz A
utilizada pelo n´o A, al´em disso ´e necess´ario multiplicar as trocas dos n´os por outras ma-
trizes auxiliares para facilitar na quebra do protocolo conforme mostrado em [16]. Dessa
42
maneira tal protocolo n˜ao dificultou a criptoan´alise, e com isso n˜ao pode ser considerado
como um protocolo substituto para o DH.
´
E apresenta da uma tabela comparativa dos protocolos de acordo de chaves discuti-
dos ao longos deste cap´ıtulo. A Tabela 3.2 apresenta o nome do protocolo, os parˆametros
pr´e- compartilhados e a quantidade, o n´umero de trocas r ealizadas por cada protocolo, a
autentica¸c˜ao realizada ou n˜a o pelo proto colo e a precis˜ao da chave de sess˜ao gerada.
3.11 Conclus˜ao
Este cap´ıtulo apresentou os principais protocolos que serviram de base para o
estudo e implementa¸c˜ao do DHA3 e mostrou as vantagens e desvantagens de protocolos
com ou sem autentica¸c˜ao e as an´alises das complexidades para resolver tais protocolos.
No pr´oximo cap´ıtulo ser´a apresentado o protocolo proposto o DHA3, onde ser´a mostrado
o tipo de cifrador utilizado, o funcionamento do pro t ocolo, exemplo num´erico, an´alise
de seguran¸ca, aspectos criptogr´aficos inerentes ao protocolo e aspectos da implementa¸c˜ao
pr´atica do protocolo.
43
Cap´ıtulo 4
Protocolo de Acordo de Chaves Crip togr´aficas
DHA
Neste cap´ıtulo ser´a apresentado o protocolo de acordo de chaves DHA e suas mo-
difica¸c˜oes que r esultam na proposta final chamado de DHA3. Ser˜ao feitas an´alises de
implementa¸c˜ao, an´alises de seguran¸ca e an´alise do prot´otipo implementado.
4.1 Contextualiza¸c˜ao
Protocolos de acordo de chaves criptogr´aficas possuem um importante papel no
estabelecimento de canais seguros de comunica¸c˜ao entre n´o s comunicantes. A grande
maioria destes protocolos utiliza-se de criptoan´alise em fun¸c˜oes exponenciais que recaem
em resolver problemas de logaritmos discretos DLPs. No entanto, tais mecanismos neces-
sitam trabalhar com n´umeros primos com uma g r ande magnitude, na ordem de 1024 a
2048 bits de precis˜ao para que os algoritmos que resolvem problemas de DLP levem um
tempo significativo (em termos computacionais) para encontrar uma solu¸c˜ao.
Protocolos que s˜ao baseados em fun¸c˜oes expo nenciais por muitas vezes s˜ao cha-
mados de protocolos de acordo de chaves exponenciais. Dentre eles podemos citar o DH,
ElGamal, MTI e γ ≡ α
a
β
b
e outros. A complexidade para resolver tais protocolos est´a na
aparente intratabilidade dos DLPs. Estes protocolos baseados em fun¸c˜oes exponenciais
podem ser resolvidos atrav´es de busca exaustiva (testar cada um dos poss´ıveis valores que
o expoente pode assumir), sendo que este ficar´a na magnitude do primo p. Em termos de
implementa¸c˜oes reais se trabalha com a magnitude de 1024 bits. Tal modo de encontrar
a solu¸c˜ao n˜ao pode ser considerado eficiente, por isso existem os algoritmos para soluci-
onar o problema de maneira mais r´apida. O melhor algoritmo para solucionar DLP ´e o
NFS (Number Field Sie v e) [12]. Algor itmos que solucionam DLP est˜ao sobre a fun¸c˜ao
de complexidade em tempo subexponencial L
p
[k, c], descrita pela equa¸c˜ao 4.1, onde p ´e
44
primo sendo utilizado, c ´e uma constante e k ´e uma constant e satisfazendo 0 ≤ k ≤ 1. O
algoritmo NFS possui uma complexidade L
p
[
1
3
, 1.923] [1 2].
L
p
[k, c] = O(e
(c+O(1))·((ln p)
k
)·((ln ln p)
1−k
)
) (4.1)
4.2 Protocolo DHA1
No primeiro momento o protocolo DHA1 propˆos substituir o gerador α do DH
por uma matr ix quadrada, Γ, onde os elementos est˜ao sobre Z
∗
p
e cujo determinante ´e
nulo, det(Γ) = 0. Assim, o procedimento para dois n´os estabelecerem uma chave com o
DHA1 s˜ao: Cada n´o compartilha um primo grande p e uma matriz geradora Γ em (4.2) ,
satisfazendo 3 ≤ α
i,j
≤ p−2/i, j = 1, ···, n e α
i,j
= 2
n
/n ≥ 1, como mostrado pela Figura
4.1. Cada n´o g era um valor secreto 1 ≤ x ≤ p − 2 (x para o n´o A), e 1 ≤ y ≤ p − 2 (y
para o n´o B). Depois da gera¸c˜ao destes valores secretos, os n´os A e B realizar˜ao o Passo
2.
Γ =
α
1,1
··· α
1,n
.
.
.
.
.
.
.
.
.
α
n,1
··· α
n,n
(4.2)
No passo 3, o n´o B recebe z
1
= (Γ)
x
e computa a chave compartilhada atrav´es do
passo 4. A chave, K
n×n
, ´e uma matriz quadrada resultante, o nde os elementos est˜ao sob
a magnitude de p. O n´o A recebe z
2
= (Γ)
y
no passo 3 e computa a chave compartilhada
atrav´es do passo 4. Ent˜ao, cada n´o ao final obter´a a mesma chave como mostrado no
passo 5, da Figura 4.1.
4.3 Exemplo Num´erico DHA1
Para facilitar a compreens˜a o do funcionamento do DHA1 ser˜ao definidos a lg uns
valores para os parˆametros. Sendo x = 5, y = 3, p = 257 e matriz geradora com dimens˜ao
2 ×2 dada por (4.3). Assim, o n´o A realiza o c´alculo de z
1
(4.4) e o n´o B realiza o c´alculo
de z
2
(4.5), realizados no Passo 2 da Figura 4.1. Ap´os estes procedimentos os n´os realizam
o Passo 3 da Figura 4.1. Ao receberem os parˆametros p´ublicos cada n´o ir´a calcular a chave
compartilhada K
2×2
, o n´o A calcula (4.6) e o n´o B calcula (4.7) conforme o Passo 4 da
Figura 4.1. Ao final ambos os n´os obter˜ao a mesma chave compartilhada, sendo que a
chave gerada em cada n´o ´e a mesma matriz, Passo 5 da Figura 4.1.
45
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo p e matriz geradora Γ.
2 Escolhe um n´umero
aleat´orio grande
1 ≤ x ≤ p − 2 e cal-
cula z
1
= (Γ)
x
mod p
Escolhe um n´umero
aleat´orio gr ande
1 ≤ y ≤ p − 2 e cal-
cula z
2
= (Γ)
y
mod p
3 z
1
⇒
⇐ z
2
4 Calcula sua chave K
n×n
=
(z
2
)
x
mod p = (z
1
)
y
mod p
Calcula sua chave K
n×n
=
(z
1
)
y
mod p = (z
2
)
x
mod p
5 Ambos os n´os obtˆem a mesma chave K
n×n
= (Γ)
xy
mod p.
Figura 4.1 : Protocolo de acordo de chave DHA1.
Γ =
3 5
3 5
(4.3)
z
1
=
3 5
3 5
5
mod 257 =
209 177
209 177
(4.4)
z
2
=
3 5
3 5
3
mod 257 =
192 63
192 63
(4.5)
K
A
= (z
2
)
x
mod 257 =
245 237
245 237
(4.6)
K
B
= (z
1
)
y
mod 257 =
245 237
245 237
(4.7)
4.3.1 An´alise de Seguran¸ca
Nas defini¸c˜oes do pro t ocolo DHA1, os elemento s da matriz geradora devem ser
maiores que 3 e n˜ao serem potˆencias 2, tal condi¸c˜a o foi estabelecida para evitar que os
elemento s da matriz gerador a possam ser tratados ou visualizados como uma s´erie. Por
exemplo, quando todos os elementos s˜ao 2 encontra-se o n-´esima potˆencia atrav´es da s´erie
2
2·n−1
, sendo poss´ıvel existir outras condi¸c˜oes semelhantes a essas. Assim sendo o DHA1
seria a realiza¸c˜ao de 4 vezes o DH e n˜a o teria vantagens sobre o DH. Para que o DHA1
possua vantagens sobre o DH ´e preciso que o determinante seja nulo, e que os elementos
46
sejam diferentes entre si e que n˜ao sejam potˆencias de 2.
Apesar de todas as considera¸c˜oes feitas anteriormente, tal proposta pode ser redu-
zida ao caso do DH, podendo assim ser resolvido como um DLP comum. Para isto, ba sta
utilizar o exemplo num´erico apresentado na se¸c˜ao anterior, onde as linhas da matriz s˜ao
iguais, mas as colunas s˜ao diferentes. Vale ressaltar que para que se po ssa gerar matrizes
com determinantes nulos independentemente do expoente sendo utilizado, ´e necess´a rio
que as linhas ou as colunas da matriz geradora sejam iguais. No contexto apresenta do no
exemplo num´erico as linhas s˜ao iguais. Para realizar a redu¸c˜ao basta somar os elemen-
tos diferent es, por exemplo, de z
1
gerando um β = (α
1,1
+ α
1,2
) mod p, o resultado seria
β = (209+177) mod 257 = 129, logo se fosse realizado a soma dos elementos diferentes da
matriz geradora (α
1,1
+ α
1,2
) e elev´a-los ao expoente utilizado x = 5 obter-se-ia o mesmo
resultado feito atrav´es da soma do element os distint os de z
1
, dado (3+5)
8
mod 257 = 129.
Tal an´alise foi obtida atrav´es da observa¸c˜ao de que os resultados obtidos em z
1
e z
2
s˜ao
nada mais do que “produtos not´aveis”, e por esse motivo tal proposta n˜ao dificultou a
criptoan´alise do DH. No entanto se fosse poss´ıvel trabalhar de forma que independente-
mente do expoente (segredo de cada n´o) a matriz gerada para a troca (z
1
e z
2
) obtivesse
4 valores distintos de forma a gerar uma matriz com determinante nulo, dessa forma tal
proposta dificultaria a criptoan´alise do DH. Mas, atrav´es dos estudos realizados at´e o
presente momento n˜ao foi poss´ıvel encontrar uma matriz geradora com quatro elementos
diferentes que sempre gerasse, ap´os a exponencia¸c˜ao matricial sobre m´odulo, matrizes
com determinantes nulos.
4.4 DHA2
Com o objetivo de diminuir a quantidade de informa¸c˜ao que est´a sendo transmitida
entre os n´os no acordo de chave e diminuir tamb´em o processamento, sem no entanto
diminuir a complexidade para resolver o DHA1, foi feita uma modifica¸c˜ao no DHA1 para
que operasse com uma matriz Γ com dimens˜ao finita 1×2, logo, a penas dois elementos s˜a o
trasmitidos a cada troca realizada entre os n´os. Esta proposta foi definida como DHA2,
o 2 ´e devido utilizar apenas dois domain parameters. Assim, os procedimentos para dois
n´os estabelecerem uma chave com o DHA2 s˜ao: Cada n´o compartilha um primo grande p
e uma matriz geradora Γ em (4.8), satisfazendo 1 ≤ α
i,j
≤ p −2 para todo i, j = 1, ···, n,
como mostrado pela Figura 4.2. Cada n´o gera um valor secreto 1 ≤ x ≤ p − 2 (x para o
n´o A), e 1 ≤ y ≤ p −2 (y para o n´o B). Depois da gera¸c˜ao destes valores secretos, os n´os
A e B realizar˜ao o passo 2.
47
Γ =
α
1,1
α
1,2
(4.8)
No passo 3, o n´o B recebe z
1
= (Γ)
x
e calcula a chave compartilhada atrav´es do
passo 4. A chave, K
1×2
, onde os elementos est˜ao sobre a precis˜ao de p. O n´o A recebe
z
2
= (Γ)
y
no passo 3 e calcula a chave compartilhada atrav´es do passo 4. Ent˜ao, cada n´o
ao final obter´a a mesma chave como mostrado no passo 5 da Figura 4.2.
No entanto, para o DHA2 a exponencia¸c˜ao da matriz geradora n˜ao segue a mesma
regra que ´e feita pelo DHA1, onde ´e realizada a multiplica¸c˜ao sucessiva da matriz gera-
dora base Γ. No DHA2 ´e realizado um mapeamento para executar a exponencia¸c˜ao. Para
simplificar a explana¸c˜a o deste map eamento ser´a considerado o caso em que a matriz gera-
dora seja elevada `a potˆencia de 2, Γ
2
. Os elementos da matriz geradora ser˜ao renomeados
para a = α
1,1
e b = α
1,2
, sendo que este mapeamento permite um conjunto variado de
possibilidades. Ser˜ao apresentados apenas quatro tipos de mapeamento, sendo que tais
mapeamentos foram baseados nos “pro tuto s not´aveis”, por exemplo: produto das somas,
produto da soma pela diferen¸ca, produto das diferen¸cas, entre outros, conforme mostrado
abaixo:
1. [a, b]
2
mod p =⇒ [a
2
+ a · b, a · b + b
2
] mod p
2. [a, b]
2
mod p =⇒ [a
2
+ b
2
, a · b + a · b] mod p
3. [a, −b]
2
mod p =⇒ [a
2
− a · b, −a · b + b
2
] mod p
4. [a, −b]
2
mod p =⇒ [a
2
+ b
2
, −a · b − a · b] mod p
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo p e matriz geradora Γ.
2 Escolhe um n´umero
aleat´orio grande
1 ≤ x ≤ p − 2 e cal-
cula z
1
= (Γ)
x
mod p
Escolhe um n´umero
aleat´orio gr ande
1 ≤ y ≤ p − 2 e cal-
cula z
2
= (Γ)
y
mod p
3 z
1
⇒
⇐ z
2
4 Calcula sua chave K
1×2
=
(z
2
)
x
mod p = (z
1
)
y
mod p
Calcula sua chave K
1×2
=
(z
1
)
y
mod p = (z
2
)
x
mod p
5 Ambos os n´os obtˆem a mesma chave K
1×2
= (Γ)
xy
mod p.
Figura 4.2 : Protocolo de acordo de chave DHA2.
48
4.5 Exemplo Num´erico DHA2
Para facilitar a compreens˜a o do funcionamento do DHA2 ser˜ao definidos a lg uns
valores par a os parˆametros. Sendo x = 5, y = 4, p = 257, o s elementos da matriz geradora
sendo a = 2 e b = 3, e matr iz g eradora com dimens˜ao 1 × 2 dada por (4.9). Assim, o
n´o A realiza o c´alculo de z
1
(4.10) e o n´o B realiza o c´alculo de z
2
(4.11), realizados no
passo 2 da Figura 4.2. Ap´o s estes procedimentos os n´os realizam o passo 3 da Figura 4.2.
Ao receberem os parˆametros p´ublicos cada n´o ir´a calcular a chave compartilhada K
1×2
,
o n´o A calcula (4.12) e o n´o B calcula (4.13) conforme o passo 4 da Figura 4.2. Ao final,
ambos os n´os obter˜ao a mesma chave compartilhada, sendo que a chave gerada em cada
n´o ´e a mesma matriz, passo 5 Figura 4.2.
Γ =
2 3
(4.9)
z
1
=
2 3
5
mod 257 =
20 21
(4.10)
z
2
=
2 3
4
mod 257 =
56 55
(4.11)
K
A
= (z
2
)
x
mod 257 =
250 249
(4.12)
K
B
= (z
1
)
y
mod 257 =
250 249
(4.13)
4.5.1 An´alise de Seguran¸ca DHA2
De forma semelhante ao que foi discutido sobre a seguran¸ca do DHA1, o mesmo
pode ser a plicado ao DHA2. Tamb´em nesta proposta pode-se reduzir o DHA2 ao DH,
sendo assim necess´ario realizar apenas um DLP, n˜ao dificultando a criptoan´alise do
DH. Da mesma forma utilizando-se do exemplo num´erico apresentado na se¸c˜ao anterior,
considerando a troca z
1
e somando os elementos resultantes (α
1,1
+ α
1,2
) mod p tˆem-se
β = (20 + 21) mo d 257 = 41 que ´e o mesmo resultado que se fosse realizada a seguinte
opera¸c˜ao: β = (2 + 3)
5
mod 257 = 41. Ao observar-se cada uma das propostas de
forma isolada, DHA1 e D HA2, notou-se que n˜ao s˜ao eficientes, pois recaem no DH. A
partir da jun¸c˜ao destas duas propo stas (DHA1 e D HA2) resolveu-se implementar uma
nova proposta chamada DHA3, com algumas diferen¸cas matem´aticas para dificultar a
criptoan´alise em rela¸c˜ao ao DH e ser´a apresentada a partir da pr´oxima se¸c˜ao.
49
4.6 Protocolo de Acordo de Chaves DHA3
Esta proposta une as caracter´ısticas do DHA1 e do DHA2 com o intuito de real-
mente dificultar a criptoan´alise evitando assim, que o DHA3 possa ser reduzido a comple-
xidade do DH. Nesta nova proposta ambos os n´os compartilham um primo p uma matriz
quadrada Γ de dimens˜ao n ×n e um vetor υ com dimens˜ao 1 ×n. Cada n´o gera um valor
secreto 1 ≤ x ≤ p −2 (x para o n´o A), e 1 ≤ y ≤ p −2 (y para o n´o B). Ser´a considerado o
caso onde a matriz Γ possui dimens˜a o 2×2 (4.14) e o vetor υ (4.15 ) p ossui dimens˜ao 1×2.
Os elementos da matriz Γ devem ser diferentes entre si, tal que α
1,1
= α
1,2
= α
2,1
= α
2,2
.
O mesmo vale para os elementos do vetor υ sendo α
1,1
= α
1,2
. Os elementos da matriz e
do vetor devem estar entre 1 ≤ α
ij
≤ p − 2, mas para garantir que tais elementos sejam
diferentes e que n˜ao hajam rela¸c˜o es ´obvias entre os mesmos, tais elementos podem ser
n´umeros primos.
Γ =
α
1,1
α
1,2
α
2,1
α
2,2
(4.14)
υ =
α
1,1
α
1,2
(4.15)
O funcionamento do protocolo DHA3 ´e semelhante ao DH, D HA1 e DHA2 como
descrito abaixo:
Passo 1 : Na Figura 4.3, ambos os n´o s compartilham uma matriz Γ, um vetor υ e um
primo p.
Passo 2 : Neste passo tˆem-se a diferen¸ca em rela¸c˜ao as outras propo stas (DH, DHA1,
DHA2) ´e que cada n´o ir´a realizar apenas uma exponencia¸c˜ao que ´e a gera¸c˜ao da
matriz m
1
e m
2
na Figura 4.3, sendo que tais matrizes s˜ao va lores mantidos em
segredo pelos n´os, al´em disso se a matriz gerada ap´os a exponencia¸c˜ao e a aplica¸c˜ao
do m´odulo gerar uma matriz com valores nulos, dever´a ent˜ao, gerar um novo valor
aleat´orio para o expoente e realizar a opera¸c˜ao novamente (Cada n´o idividualmente
dever´a realizar este teste antes de gerar os domain parameters).
Passo 3 : Os n´os multiplicam as suas matr izes pelo vetor compartilhado υ.
Passo 4 : Os n´os realizam as trocas dos domains parameters z
1
e z
2
que s˜ao vetores de
dimens˜ao 1 × 2.
Passo 5 : Ambos os n´os ao receberem o parˆametro p´ublico do outro n´o, ir˜ao calcular o
vetor chave que ´e a multiplica¸c˜ao dos domain parameters z
1
e z
2
pelas matrizes m
1
50
e m
2
.
Passo 6 : Ao final, ambos os n´o s obtˆem o mesmo vetor chave.
Passo N´o A Trocas N´o B
1 Os n´os concordam num primo p e matriz geradora Γ e num vetor υ.
2 Escolhe um n´umero
aleat´orio grande
1 ≤ x ≤ p − 2 e cal-
cula m
1
= (Γ)
x
mod p
Escolhe um n´umero
aleat´orio gr ande
1 ≤ y ≤ p − 2 e cal-
cula m
2
= (Γ)
y
mod p
3 Calcula z
1
= (υ·m
1
) mod p Calcula z
2
= (υ·m
2
) mod p
4 z
1
⇒
⇐ z
2
5 Calcula sua chave K
1×2
=
(z
2
· m
1
) mod p
Calcula sua chave
K
1×2
= (z
1
· m
2
) mod p =
(z
2
)
x
mod p
6 Ambos os n´os obtˆem a mesma chave K
1×2
= (υ · (Γ)
xy
)mod p.
Figura 4.3 : Protocolo de acordo de chave DHA3.
4.7 Exemplo Num´erico DHA3
Para facilitar a compreens˜a o do funcionamento do DHA3 ser˜ao definidos a lg uns
valores para os parˆametros. Sendo x = 5, y = 4, p = 257 e matriz geradora com dimens˜ao
2 × 2 dada por (4.16), o vetor upsilon dado por (4.17). Assim, o n´o A realiza o c´alculo
de m
1
(4.18) e o n´o B realiza o c´alculo de m
2
(4.19), realizados no passo 2 da Figura 4.3.
Ap´os estes procedimentos os n´os realizam o passo 3 da Figura 4 .3 , onde ´e calculado o z
1
em (4.20) e o z
2
em (4.21). Ao receberem os parˆametros p´ublicos cada n´o ir´a calcular a
chave compartilhada K
2×2
, o n´o A calcula (4.22) e o n´o B calcula (4.23) conforme o passo
5 da Fig ura 4.3. Ao final ambo s os n´os obter˜ao a mesma chave compartilhada, sendo que
a chave gerada em cada n´o ´e o mesmo vetor, passo 6 da Figura 4.3.
P asso 1 ⇒ Γ =
2 3
5 7
(4.16)
P asso 1 ⇒ υ =
11 13
(4.17)
51
P asso 2 ⇒ m
1
=
2 3
3 7
5
mod 257 =
222 122
101 66
(4.18)
P asso 2 ⇒ m
2
=
2 3
5 7
4
mod 257 =
34 185
137 171
(4.19)
P asso 3 ⇒ z
1
= (υ · m
1
) mod 257 =
157 34
(4.20)
P asso 3 ⇒ z
2
= (υ · m
2
) mod 257 =
99 146
(4.21)
P asso 5 ⇒ K
A
= (z
2
· m
1
) mod 257 =
230 164
(4.22)
P asso 5 ⇒ K
B
= (z
1
· m
2
) mod 257 =
230 164
(4.23)
4.8 An´alise de Seguran¸ca DHA3
Nas defini¸c˜oes do pro t ocolo DHA3, os elemento s da matriz geradora devem ser
diferentes entre si para garantir que as matrizes m
1
e m
2
n˜ao apresentem rela¸c˜oes ´obvias
com a matriz Γ, para evitar o que acontecia no DHA1 e no DHA2. A utiliza¸c˜ao do vetor
υ foi feito para que algoritmos que resolvem DLPs com complexidade subexponencial n˜ao
pudessem ser efetivos sobre o DHA3. Como po r exemplo, o algoritmo IC (Index Calculus)
e o NFS [3]. O motivo que faz com que tais algor itmos n˜ao sejam efetivos sobre o DHA3 ´e
o fato de realizar os procedimento s apenas sobre uma ´unica base (seria o caso de trabalhar
apenas com a matriz Γ) , no entanto existem duas bases a matriz Γ e o vetor υ. Outro
ponto ´e realizar a decomposi¸c˜ao dos vetores gerados nos procedimentos do DHA3 em
vetores parciais. Como pode ser visto no Cap´ıtulo 2 desta disserta¸c˜ao, no Passo 4.2 do
algoritmo Index - Calculus, sendo que n˜ao ´e uma opera¸c˜ao t˜ao trivial de ser realizada no
contexto de vetores. De forma semelhante ´e realizado no NFS para resolver o DH, contudo
ainda deve ser investigado a poss´ıvel utiliza¸c˜ao do NFS para reduzir a complexidade do
DHA3, mas n˜ao ´e o escopo deste trabalho investigar tais contextos.
O alg oritmo cl´assico para resolver DLP ´e o algoritmo Baby-Step Giant-Step [3],
que ´e baseado na seguinte observa¸c˜a o: se β = α
a
, ent˜ao pode-se escrever a = im + j,
onde 0 ≤ i, j ≤ m e m =
√
p. Portanto, α
a
= α
im
α
j
, implica em β(α
−m
)
i
= α
j
. Este
m´etodo pode ser aplicado no DHA3 porque bastaria realizar o seguinte procedimento:
52
sendo β = υ · Γ
a
, β · (α
−m
)
i
= υ · α
j
. Os outros m´etodos que p ossuem complexidade de
solu¸c˜ao O(
√
p) tamb´em podem ser adaptados para resolver o DHA3.
A complexidade para resolver o DH por busca exaustiva ´e O(2
η
), onde η ´e a
magnitude do n´umero primo p, que produz no pior caso 2
η
multiplica¸c˜oes para o DH. Com
o intuito de aplicar busca exaustiva no DHA3 s˜ao necess´arias ((n
3
+n
2
)·2
η
) multiplica¸c˜oes
e tamb´em ((n
2
·(n−1)+2)) adi¸c˜oes. O parˆametro, n, define a dimens˜ao da matriz geradora
quadrada (n × n). Assim, considerando apenas as multiplica¸c˜oes, a complexidade para
encontrar uma solu¸c˜ao para o DHA3 ´e O((n
3
+n
2
)·2
η
). O n´umero de parˆametros principais
(domain parameters) trocados por cada n´o pelo DHA3 ´e n, devido ser necess´a rio enviar
todos os elementos do vetor resultant e. Ent˜ao com o objetivo de produzir um menor
overhead no protocolo de acordo de chaves, a dimens˜ao ´otima para a matriz quadrada ´e
2 × 2 e o vetor de 1 × 2, que gera a troca de dois domain parameters.
Apesar de que uma matriz com dimens˜oes maiores cause um aumento na comple-
xidade para resolver o DHA3, ainda assim a magnitude do primo p ´e a mais impactante
na complexidade do protocolo. No entanto se, por exemplo, fosse utilizada uma matriz
com dimens˜a o 3 × 3 e um vetor com 1 × 3 seria necess´ario enviar 3 domain parameters
que por sua vez encontram-se na magnitude do primo p, e 3 vezes a magnitude do primo
acarretaria num overhead muito maior que o DH cl´assico. Uma matriz 2 ×2 e vetor 1 ×2
necessitaria enviar apenas 2 domain parameters a cada troca, e obter-se-ia praticamente
o mesmo n´ıvel de seguran¸ca que uma 3 × 3, pois se substituirmos o va lor das dimens˜oes
nas equa¸c˜oes de complexidade do DHA3, ter´ıamos para n = 2, O(12 · 2
η
) e para n = 3,
ter-se-ia O(36 · 2
η
). Com n = 3 o DHA3 seria 3 vezes mais complexo que para n = 2, no
entanto transmitiria 5 0% a mais de informa¸c˜ao o que n˜a o tornaria o protocolo vantajo so
se comparado com o DH.
Supondo o DHA3 sendo resolvido pelo BSGS que possui tempo de execu¸c˜ao no
pior caso de O(
√
p), se considerarmos o fato do DHA3 estar trabalhando com uma matriz
de dimens˜ao 2 ×2 e um vetor de 1 ×2 e transmitindo a mesma quantidade de informa¸c˜ao
que o DH, o DHA3 precisaria trabalhar com um primo de 512 bits e o DH com um primo
de 1024. Se aplic´assemos o BSGS no DHA3, de forma simplista o DHA3 seria resolvido
no pior caso em O(
√
2
512
) = O(2
256
); se fosse aplicado o IC ou NFS no DH, sendo este
operando com um primo de 1024 bits, seria resolvido em O(2
132
) no pior caso. Assim, o
DHA3 torna-se O(
2
256
2
132
) = O(2
124
) mais complexo que o DH.
O grande desafio do protocolo DHA3 ´e: dado p, Γ, υ e (υ · Γ
a
) mod p encontrar
a. Em termos de algoritmos para resolver DLP o desafio do protocolo DHA3 ´e encontrar
uma forma de ada pta r o NFS ou o IC para que se possa realizar a decomposi¸c˜ao de vetores
geradas pelo protocolo, sendo que baseado nos estudos feitos at´e present e momento ainda
53
n˜ao foi encontr ado nenhum m´etodo que realize tal o pera¸c˜ao de forma satisfat´oria. Assim,
o m´etodo mais eficaz para resolver o DHA3 ´e atrav´es dos m´etodos com resolu¸c˜ao em
O(
√
p). Deste modo, o DH precisa trabalhar com primos com aproximadamente quatro
vezes a magnitude que o DHA3 utiliza, para ga rantir aproxidamente o mesmo grau de
complexidade a solu¸c˜ao po r DLP.
4.9 Aspectos da Implementa¸c˜ao do DHA3
O protocolo DHA3 foi implementado em Linguagem C Posix com o compilador
GNU/GCC [17] atrav´es do uso da biblioteca GNU/GMP [1 8]. Esta biblioteca permite
trabalhar com n´umeros de alta precis˜ao [19]. O elemento crucial na implementa¸c˜ao do
protocolo foi na escolha do melhor m´etodo de exponencia¸c˜ao a ser utilizado levando em
considera¸c˜ao o fato da base a ser exponenciada, n˜ao ser apenas um valor inteiro, mas sim
uma matriz de valores inteiros positivos n˜ao nulos. Devido a o uso de matrizes, o algoritmo
14.79 da p´agina 615 de [3] foi o que melhor se enquadrou ao ser ada pta do para o uso com
matriz.
O algoritmo 14.79 da p´agina 615 de [3] foi modificado para ser aplicado ao DHA3
conforme ´e mostrado no Algoritmo 1. Sendo que o expoente e ´e tratado na sua forma
bin´aria (e
t
e
t−1
···e
1
e
0
)
2
, t ´e o bit mais significante, I
n
´e a matriz identidade de ordem n,
A
n×n
´e matriz que armazena os resultados obtidos ao longo do processo de exponencia¸c˜ao.
Algoritmo 1 Exponencia¸c˜ao Bin´aria da Esquerda para Direita
ENTRADA: Γ e o expoente positivo e inteiro e = (e
t
e
t−1
···e
1
e
0
)
2
SA
´
IDA: Γ
e
1. A
n×n
← I
n
.
2. Para i de t at´e 0 fa¸ca:
2.1 A
n×n
← A
n×n
· A
n×n
.
2.2 Se e
i
= 1, ent˜ao A
n×n
← A
n×n
· Γ.
3. Retorne (A
n×n
)
Existem outros a lg oritmos que realizam a expoenencia¸c˜a o de forma mais r´apida
que o 14.79. No entanto necessitam de mais vari´aveis e opera¸c˜o es de pr´e - c´alculos de
elemento s utilizados ao longo do processo de exponencia¸c˜ao. Devido a estes e outros
motivos adotou-se o algoritmo 14.79 por ser simples de implementa r e requerer apenas
uma va r i´avel de armazenamento (no caso do protocolo DHA3 uma matriz n × n).
Devido aos aspectos de seguran¸ca discutidos na se¸c˜ao anterior mostrarem que a
dimens˜ao ideal para a matriz geradora ser 2 ×2, para garantir o menor ove rh ead poss´ıvel
sem no entanto diminuir a complexidade, ser´a utilizada sempre a dimens˜ao 2 ×2 ao longo
54
das pr´oximas se¸c˜o es. A implementa¸c˜ao em linguagem C do DHA3 ´e apresentada pelo
Algoritmo 2, onde ´e mostrado apenas o procedimento realizado por um n´o, neste caso
o n´o A.
Algoritmo 2 Pseudo-C´odigo do DHA3
1. O s n´os compartilham uma matriz Geradora Γ
2×2
, o vetor υ e um primo p.
2. O n´o A escolhe um valor inteiro x tal que 3 ≤ x ≤ p − 2.
3. N´o A usa o Algoritmo 1 para calcular m
1
= (Γ
2×2
)
x
.
4. O n´o A calcula z
1
= (υ · m
1
) mod p 5. Envia z
1
para o n´o B.
6. Recebe z
2
do n´o B.
7. O N´o A calcula K
1×2
= (z
2
· m
1
) mod p.
8. K
1×2
´e a chave de se¸c˜a o compartilhada entre os n´os.
Devido ao protocolo DHA3 gerar um vetor chave e n˜a o um valor inteiro como chave
de se¸c˜ao, e devido a esta caracter´ıstica intr´ınseca do DHA3, ambos os n´os poder˜ao mani-
pular os elementos resultantes do vetor chave K
1×2
. O DHA3 permite que os elementos
resultantes da chave gerada sejam combinados de trˆes maneiras, sendo ⊕ opera¸c˜ao bin´aria
de XOR:
1. G erar uma chave K que ´e a concatena¸c˜ao dos elementos gerados, dada po r K =
α
1,1
||α
1,2
, ainda pode-se aplicar esta chave gerada numa fun¸c˜ao de hash e obter o
hash dos elementos, afim de obter uma ´unica chave K = h(α
1,1
||α
1,2
).
2. Outra forma seria gerar o hash de cada um dos elementos gerando assim duas chaves
K
1
= h(α
1,1
) e K
2
= h(α
1,2
).
3. A terceira forma seria realizar a opera¸c˜ao bin´ar ia XOR nos elementos resultantes
afim de gerar-se apenas uma chave K = α
1,1
⊕α
1,2
, ou ainda aplicar uma fun¸c˜ao de
hash na chave K, gerando K = h(α
1,1
⊕ α
1,2
).
A utiliza¸c˜ao de fun¸c˜oes de hash na g era¸c˜ao das chaves ´e feita com o intuito de gerar
uma chave no tamanho padr˜ao utilizado pelo AES (Advanced Encryption Standard), que
´e um sistema criptogr´afico sim´etrico e opera com chaves de 128, 192 e 256 bits.
4.10 An´alise de Desempenho DHA3
Foi implementada em Linguagem C uma vers˜ao do DH e do DHA3 usando a
biblioteca GMP e utilizando o Algoritmo 1 como m´etodo de exponencia¸c˜ao para o
DHA3, e foi utilizado o algoritmo 14.79 da p´agina 615 de [3] para o DH para que pudesse
haver um bom n´ıvel de compara¸c˜ao entre o DHA3 e o DH. Considerando o DH trabalhando
55
com um primo de 1024 bits de magnitude e utilizando o NFS para resolver tal DLP,
utilizando (4.1) , logo L
2
1024
[
1
3
, 1.923]
∼
=
O(2
132
). Baseado nisto, bastaria para o DHA3
trabalhar com um primo de 51 2 bits de precis˜ao para que o D HA3 transmita a mesma
quantidade de informa¸c˜ao que o DH. Considere como exemplo a matriz geradora dada
por (4 .24) e o vetor υ dado por (4.25) .
Γ =
2 3
5 7
(4.24)
Γ =
11 13
(4.25)
Com o primo p com 512 bits de magnitude para o DHA3 e 1024 bits para o DH,
o DHA3 levou 2 vezes menos tempo de processamento do que o DH e transmitiu 1024
bits de informa¸c˜ao em cada troca a mesma quantidade que o DH, mas o DHA3 por
ser resolvido pelo BSGS sua complexidade de solu¸c˜ao foi para O(2
256
), j´a o DH sendo
resolvido pelo NFS passou a ter a complexidade de solu¸c˜ao O(2
132
), com isso o DHA3
tornou-se
2
256
2
132
= O(2
124
) mais complexo que o DH.
Agora considerando o DHA3 trabalhando com um primo de 264 bits para que ao
ser resolvido pelo BSGS, apresente a mesma complexidade de resolu¸c˜ao O(2
132
) que a
do DH, sendo resolvido pelo NFS, contudo o DH deve operar com um primo de 1024.
Nestas condi¸c˜oes o DHA3 levou 5 vezes menos tempo de processamento do que o DH e
transmitiu apenas 2 × 264 = 528 bits de informa¸c˜ao a cada troca.
4.11 Considera¸c˜oes
Ao longo do desenvolvimento do DHA1 e do DHA2, observou-se a possibilidade
de implementar-se o DHA3, com o intuito de dificultar a criptoan´alise para que o D HA3
n˜ao pudesse ser reduzido ao DH. A maioria dos protocolos que tentara m aumentar a
complexidade do DH, alg uns destes apresentados no Cap´ıtulo 3 desta disserta¸c˜ao, se
ativeram em manipular os exp oentes “segredos” ou utilizaram de assinatura digital ou
mesmo de certificados para aumentar a seguran¸ca do DH. Mas a propo sta apresentada
nesta disserta¸c˜ao de mestrado trouxe uma nova ´area de estudo que a utiliza¸c˜ao de matrizes
e vetores como geradores para dificultar a criptoan´alise do DH.
O ElGamal [3] nada mais ´e do que o DH e a chave gerada ´e utilizada diretamente
para se fazer a cifragem. O ElGamal utiliza-se da complexidade para resolver um DLP ao
realizar a sua cifragem. O MTI ´e um protocolo que gera dois domain parameters extras
56
que s˜ao armazenados num servidor autenticado, os quais s˜ao utilizados para aumentar a
complexidade dos expoentes, al´em de gerar autent ica¸c˜ao m´utua das chaves.
O protocolo CRTDH [14] faz uma jun¸c˜ao da s caracter´ısticas do DH e do CRT para
aumentar a complexidade do protocolo, no entanto, este necessita realizar muitas trocas
para obter as chaves compartilhadas entre os membros do grupo, uma vez que o objetivo
deste protocolo ´e ser aplicado em redes sem fio no modo Ad-hoc. O protocolo SPAKE [7]
utiliza uma senha pr´e-compartilhada entre os n´os, para ent˜ao realizar os procedimentos
da gera¸c˜ao da chave compartilhada. Esta “senha” ´e aplicada no expoente “segredo”, mas
tal pro t ocolo acaba se tornando vulner´avel ao ataque de “passphrase”. Uma vez que
cada caractere da senha ter´a no m´aximo 102 possibilidades, enquanto que um byte de
uma chave criptogr´afica apresenta o universo de 256 possibilidades. Al´em deste protocolo
necessitar de um servidor para realizar a autentica¸c˜ao dos n´os.
O protocolo S- 3PAKE tamb´em utiliza “senhas” entre o servidor e os n´os [7], e
justifica-se que ´e um protocolo inovador por n˜ao necessitar de um servidor de chaves
p´ublicas, no entanto, tal protocolo necessita de um servidor confi´avel para autenticar as
partes comunicantes. Neste caso haver´a apenas a troca de um servidor por outro (chaves
p´ublicas por um servidor confi´avel) de forma que a proposta n˜ao poderia ser considerada
inovador a. Al´em disso, toda a “seguran¸ca” deste protocolo est´a depositada no servidor
confi´avel, uma vez que este servidor possa vir a ser comprometido, todo o pro t ocolo
estar´a comprometido. Tal condi¸c˜ao n˜ao ocorre com o DHA3 uma vez que n˜ao necessita
de servidor confi´avel nem de servidores de chaves p´ublicas, pois ´e um protocolo de acordo
de chaves criptogr´aficas sem autentica¸c˜ao das partes.
O protocolo Matrix Rings [8] foi a primeira proposta que utilizou uma matriz como
gerador base, no entanto tal proposta apresenta o inconveniente de ser necess´ario gerar
um polinˆomio f(x) n˜ao redut´ıvel, ter mais um parˆametro p´ublico extra que ´e o expoente
r (ordem da matriz g erador a) compartilhado pelos n´os. A principal desvantagem de
tal protocolo ´e que a matriz geradora possui uma dimens˜ao maior que 2 × 2, conforme
mostrado no Cap´ıtulo 3. Trabalhar com matrizes com dimens˜oes maiores que 2 × 2 n˜a o
torna-se vantajoso devido `a quantidade de informa¸c˜ao que ´e necess´ar ia ser tro cada entre
os n´os. Supo ndo uma matriz com dimens˜ao 6×6 e um primo p com 1024 bits de precis˜ao,
em cada troca realizada pelos n´os seriam necess´arios enviar n
2
· p dados que neste caso
seria 36·1024 = 36864 bits, o que seria enviar 36 vezes mais informa¸c˜ao que o DH. Logo tal
proposta em contextos onde os n´os (dispositivos) apresentem limita¸c˜ao de transmiss˜ao de
dados pelo canal de comunica¸c˜ao, n˜ao seriam beneficiados. Contudo, o protocolo DHA3
gera menos dados que o DH e garante um n´ıvel consider´avel de seguran¸ca.
O protocolo que trabalha com matrizes inversas [15] tentou aumentar a complexi-
57
dade de resolu¸c˜ao do DH, mas o mesmo n˜ao atentou para o fato de que o sistema gerado
pelo seu protocolo poderia ser resolvido atrav´es da resolu¸c˜ao de sistemas lineares sobre
campos finitos, como demonstrado em [16]. Al´em da proposta apresenta da em [15] tra-
balhar apenas com matrizes sobre campo bin´ario, logo o universo de busca fica muito
limitado. O mesmo n˜ao ocorre no DHA3, po is este utiliza matrizes e vetores sobre cam-
pos finitos, sendo que o primo utilizado apresenta uma magnitude consider´avel, gerando
assim um universo de busca grande.
O grande desafio desta disserta¸c˜ao foi encontrar um pro t ocolo pelo qual n˜ao pu-
desse ser mais resolvido atrav´es de algoritmos que tem complexidade de resolu¸c˜ao em
tempo subexponencial como o IC e o NFS, por isso ´e que a jun¸c˜ao de matrizes com
vetores tiveram um importante papel na contru¸c˜ao do protocolo DHA3. A seguir, ser´a
apresentada uma tabela comparativa entre o DH e o DHA3, onde ser˜ao comparados a
magnitude do primo utilizado pelos protocolos, a complexidade, o tamanho da chave ge-
rada e a quant idade de informa¸c˜ao transmitida na duas trocas realizadas pelos n´os. Na
Tabela 4.1 a complexidade do DH foi f eita considerando o algoritmo NFS para resolver o
DLP atrav´es da equa¸c˜ao 4.1 e considerando o NFS com L
p
[
1
3
, 1.923], e para o DHA3 foi
considerado que o mesmo seja resolvido pelo algoritmo BSGS.
Tabela 4.1: Compara¸c˜ao dos protocolos DH e DHA3
DH
Primo p (bits) 768 102 4 2048 4096
Chave (bits) 768 1024 2048 4096
Tr´afego (bits) 1536 2048 4096 8192
Complexidade O(2
117
) O(2
132
) O(2
178
) O(2
238
)
DHA3
Primo p (bits) 384 512 1024 2048
Chaves (bits) 2 × 384 = 768 2 × 512 = 1024 2 × 1024 = 2048 2 × 2048 = 4096
Tr´afego (bits) 1536 2048 4096 8192
Complexidade O(2
192
) O(2
256
) O(2
512
) O(2
1024
)
DHA3 Com Menor Tr´afego
Primo p (bits) 234 264 356 476
Chaves (bits) 2 × 234 = 468 2 × 264 = 528 2 × 356 = 712 2 ×4 76 = 952
Tr´afego (bits) 936 105 6 1424 1904
Complexidade O(2
117
) O(2
132
) O(2
178
) O(2
238
)
4.12 Conclus˜ao
Neste Cap´ıtulo foram apresentados o s protocolos propostos DHA1, DHA2 e o
DHA3, bem como os quesitos para sua implementa¸c˜ao, an´alise desempenho, an´alise da
58
complexidade, vantagens sobre o DH, mostrando que apenas o DHA3 trouxe benef´ıcios
em termos criptogr´aficos. A Tabela 4.1 sumariza a compara¸c˜ao entre os protocolos DH
e DHA3 para mostrar que o protocolo proposto nesta disserta¸c˜ao trabalha com primos
menores que o DH e alcan¸ca uma complexidade de resolu¸c˜ao maior. No pr´oximo Cap´ıtulo
ser´a apresentada a conclus˜ao final desta disserta¸c˜ao de mestrado.
59
Cap´ıtulo 5
Conclus˜ao
Esta disserta¸c˜ao de mestrado versou sobre protocolos de acordo de chaves crip-
togr´aficas principalmente nos baseados em problemas de DLP, como DH, ElGamal, MTI,
SPAKE, S-3PAKE, Matrix Rings e outros. Ao longo desta pesquisa e estudo, pode-se
observar que os protocolos de acordo de chaves cl´assicos atinham-se em aumentar a com-
plexidade dos expoentes ao qual o gerador base (no caso do DH α) era elevado, pois tais
valores s˜ao os “segredos” armazenados pelos n´os. Contudo ao longo da an´alise, desen-
volvimento e estudo do protocolo DHA3, pode-se notar que o elemento mais importante
era o gerador base e n˜ao somente os expoentes, e atrav´es desta observa¸c˜ao ´e que pode-se
implementar o DHA3.
A primeira premissa que foi idealizada para o DHA3 foi a de n˜ao precisar de um
servidor de chaves p´ublicas ou mesmo um servidor autˆentico para garantir a seguran¸ca
do protocolo. O S-3PAKE necessita de um servidor autˆentico para garantir a seguran¸ca
do mesmo, contudo se este servidor for invadido toda a seguran¸ca do protocolo estar´a
comprometida. O protocolo DHA3 independe de servidores o que facilitaria a sua apli-
cabilidade em ambientes formados por redes no modo a d-hoc onde a “autentica¸c˜ao” ´e de
responsabilidade dos membros da rede. Esta premissa foi alcan¸cada como pode ser visto
ao longo do Cap´ıtulo 4, desta disserta¸c˜ao.
O segundo objetivo deste protocolo era de transmitir menos informa¸c˜ao que o DH
e mesmo a ssim garantir ao menos a mesma complexidade que o DH cl´assico. Tal objetivo
foi alcan¸cado atrav´es do uso de matrizes e vetores como geradores base. Conforme foi
analisado para o DHA3 pode-se considerar o ataque pelo BSGS como um dos m´etodos
mais eficazes para resolver o protocolo proposto nesta disserta¸c˜ao. Uma vez que o grande
desafio apresentado pelo protocolo propo sto ser´a encontrar um m´etodo eficiente para
realizar a decomposi¸c˜ao de vetores para que possa ent˜ao vir a ser resolvido por algoritmos
mais eficientes que o BSGS. Tal arg umenta¸c˜a o ´e apresentada, pois uma vez encontrado
60
um meio de realizar tal decomposi¸c˜ao este poderia ser adaptado ao m´etodo NFS para
reduzir a complexidade do protocolo DHA3 e com isso evitar que a solu¸c˜ao mais efetiva
seja atr av´es do BSGS, por exemplo.
O terceiro objetivo desta disserta¸c˜ao f oi criar um protocolo que diminu´ısse o pro-
cessamento computacional para gerar os parˆametros pr´e-compartilhados. Conforme visto
no protocolo Matrix Rings apresentado no Cap´ıtulo 3 desta disserta¸c˜ao , este necessita
gerar pelo menos um polinˆomio irredut´ıvel, calcular a matriz geradora A, encontrar um
conjunto de matrizes B
i
afim de poder calcular A e determinar a ordem de A atrav´es do
encontro do expoente r, tal que A
r
mod p = I gere uma matriz identidade. Tais proce-
dimentos geram um consumo computacional significativo para o s n´os comunicantes. O
protocolo DHA3 n˜ao precisa de uma quantidade t˜ao significativa de procedimentos como
no Matrix Rings, basta no caso do DHA3 utilizar uma matriz e um vetor com elementos
distintos entre si, por exemplo, n´umeros primos e com uma dimens˜ao de 2 × 2 e 1 × 2,
que ´e bem menos oneroso que outros protocolos.
Devido ao protocolo DHA3 ser embasado no funcionamento do DH, o protocolo
proposto nesta disserta¸c˜ao tamb´em apresenta caracter´ıstica intr´ınseca de ser ana lisado
numa complexidade em tempo exponencial, conforme visto no Cap´ıtulo 4 sobre An´alise
de Seguran¸ca. Como dito a nteriormente a primeira proposta de se alcan¸car maior com-
plexidade computacional para o DH utilizando-se para isto matrizes, foi a presentada pelo
protocolo Matrix Rings, no entanto a maior contribui¸c˜ao apresentada nesta disserta¸c˜ao ´e
o fato de utilizar matrizes e vetores, diferentemente de outros protocolos que utilizam-se
apenas de matrizes.
Como poss´ıveis aplicabilidades do protocolo proposto nesta disserta¸c˜ao de mes-
trado s˜ao: servir de protocolo de acordo de chaves criptogr´aficas anˆonimo em ambien-
tes que operem no modo ad-hoc; substituir o DH no TLS com o intuito de diminuir o
custo computacional e a quantidade de informa¸c˜ao sendo transmitida pelos n´os; poder
ser aplic´avel aos dispositivos m´oveis que utilizam o TLS para gerar o par de chaves crip-
togr´aficas como ´e o caso do WAP2 utilizado nas redes de telefonia m´ovel; ser aplicado
como pro t ocolo de acordo de chaves em redes sem fio ou mesmo cabeadas de forma geral.
O grande benef´ıcio gerado por essa disserta¸c˜ao foi trazer para a sociedade cient´ıfica
mais uma ´ar ea de estudo e an´alise sobre criptografia, utilizando-se de matrizes e vetores,
uma vez que o protocolo DHA3 diminuiu a quantidade de informa¸c˜ao trocada entre os
n´os, exigiu n´umeros primos menores que o DH e seus correlatos; garantiu um n´ıvel de
seguran¸ca consider´avel em rela¸c˜ao ao DH, ElGamal e MTI; e devido requerer n´umeros pri-
mos de menor magnitude acabou gerando menos custo computacional e sendo facilmente
implement´avel.
61
Referˆencias Bibliogr´aficas
[1] R. Ho usley, W. Ford, W. Polk, and D . Solo. Rfc 3280 - internet x.509 public key
infrastruture certificate and certificate revogation list (crl).
[2] A. Perrig, R. Szewczyk, J. D. Tygar, V. Wen, and D. E. Culler. Spins: Security
protocols for sensor networks. Wireless Networks 8
th
, pages 521–534, 2 002.
[3] Alfred J. Menezes, Paul C. Van Oo rschot, and Scott A. Vanstone. Handbook of
Applied Cryptography - HAC, chapter 2, 3, 12, pages 59–60, 103–114, 515–519. CRC
Press, Inc., 1997.
[4] Bruce Schneier. Applied Cryptography. John Willey and Sons, 2nd edition, 1996.
[5] Sunil Kumar Kashyap, Birendra Kumar Sharma, and Amitabh Banerjee. A cryp-
tosystem based on dlp γ ≡ α
a
β
b
mod p. Internationa l Journal of Network Security,
vol. 3(1):pp. 95–100, July 2006.
[6] Michal Sramka. Cryptanalysis of the cryptosystem based on dlp γ = α
a
β
b
. Interna-
tional Journal of Network Security, vo l. 6(1):80–81 , Januar y 2008 .
[7] R. Lu and C. Z henfu. Simple three-party exchange protocol. In Elsevier, editor,
Computer & Security, number 26, pages 94–97, 2007.
[8] R. W. K. Odoni, V. Varadharajan, and P. W. Sanders. Public key distribution in
matrix rings. Electronic Letters, 20(9):386–387, April 1 984.
[9] V. Varadharaja n and R. W. K. Odoni. Security of public key distribution in matr ix
rings. Electronic Letters, 22(1):46–47, January 1986.
[10] J. Rothe. Some facets of complexity theory and cryptography: A five-lecture tutorial.
In ACM computing surveys, volume 34, pages 504–549. ACM Press, New Yourk,
December 2003.
62
[11] PGP Pretty Good Privacy. The international pgp home page. http://www.pgpi.org/,
May 2007.
[12] Oliver Schirokauer. Discrete logarithms and local units. Philosophi cal Transactions
of the Royal Society of London, vol. A 34 5(1676):409–42 3, November 1993.
[13] David S. Dummit and Richard M. Foote. Abstract Alge bra, volume 1 of ISBN: 0-
13-005562-X. Prentice-Hall International Editions, United States of America, 1st
edition, 199 1.
[14] R. K. Balachandran, B. Ramamurthy, and X. Zou. An efficient key agreement scheme
for secure communications in wireless ad hoc networks. In IEEE International Con-
ference in C ommunications, number 1, pages 1123–112 7, 2005.
[15] E. Dawson and C. Wu. Key agreement scheme based on generalised inverses of
matrices. Electron i c Letters, 33(14):1210–1211, July 1997.
[16] A. M. Youssef and S. E. Tavares. Cryptanalysis os “key agreement scheme based
on generalised inverses of matrices”. Electronic Letters, 33(21):1777–1778, October
1997.
[17] GNU GCC 4.0.2. A compiler for language c, c++, fo r tr an and java.
http://gcc.gnu.org/, July 2007.
[18] GNU GMP. Gnu multiple precision artithmetic library for language c.
http://www.swox.com/gmp/, July 2007.
[19] D. H. Bailay. High-precision floating-point arithmetic in scientific computing. IEEE
Computing in Science & Engeneering, pages 54–61, May/June 2005.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
