Criptografia e Protocolo Diffie-Hellman

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (2)  (0)

Uma pequena abordagem de criptografia simetrica e assimetrica e uma abordagem sobre o protocolo de Diffie-Hellman.

Criptografia e Protocolo Diffe-Hellman

Edson Sampaio

 



Criptografia Simétrica

 

Possui apenas uma chave e essa é compartilhada entre as pessoas da conexão. Em geral não são usadas em autenticações porem, em sua maioria são usadas para confidencialidade, ou seja, usadas para transporta informações em sigilo.

O seu funcionamento é bem mais rápido do que um método assimétrico se comparado com um do mesmo nível.

Em geral a chave é única para cifrar e decifrar, podendo ter uma pequena variação, então pra efeito didático a chave é única.

  

Passos

 

1.  Depois de ambos conhecerem a chave k, acontece o seguinte;

2. Alice cifra sua mensagem M1, Y=E(M1,k);

3. Alice envia Y para Bruno;

4. Bruno decifra Y e encontra M1, M1=D(Y,k);

Mas isso só acontece porque k é conhecido pelos os dois.

 

Criptografia Assimétrica

 

É implementada com duas chaves para cada usuário, uma chave pública e uma chave privada. A chave publica é conhecida por todos na conexão, a chave privada é de conhecimento apenas do dono.

Vale salientar computacionalmente intensiva, ou seja, é lenta se comparada com um método simétrico de mesmo nível.Uma boa é que pode ser usada em autenticação e confidencialidade.

 

Passos

 

Passo 1: Cada usuário cria suas chaves tanto a publica quanto a privada.

Passo 2: Alice envia a sua chave publica para Bruno;  

 

Passo 3: Bruno Criptografa a Mensagem com a chave publica de Alice, ela recebe a mensagem cifrada e decifra com sua chave privada.

 
 

Definições de Teoria dos Números

 

1. Sejam a, b e m inteiros com p>0, dizemos que a é congruente a b modulo m se m divide (a-b), ou seja, m|(a - b), e nesse caso denotamos por a≡ b(mod m).

2. O menor numero natural k tal que ak≡ 1(mod m) onde mdc(a,m)=1, é chamado "ordem de a modulo m" e denotado por ordma, ou seja, k=ordma.

3. Se ordma=Φ(m) dizemos que a é uma raiz primitiva modulo m. De modo que Φ(m) é igual a quantidade de números menores que m onde o mdc de cada numero com m é igual a 1 (mdc(m,n)=1, com n).

 

Exemplos

 

a) 4 ≡ 7(mod3);

b) 2 ≡ -1(mod3);

c) 4+2 ≡ 7+(-1)(mod3);

d) 4*2 ≡7*(-1)(mod3)

e) 2n ≡ (-1)n(mod3);

f) Φ(5)=4;

g) 24 ≡ 1(mod 5), portanto 2 é uma raiz primitiva modulo 5.

 

Protocolo de Diffie-Hellman

 

1. É usada para intercambio de chaves entre usuários;

2. É baseado na operação de logaritmos discretos;

3. Logaritmo discreto é baseado na raiz primitiva;

4. Requer autoridade de certificação (chave pública confiável).

 

Passos

 

1. Dados p primo e a uma raiz primitiva modulo p, ambos conhecidos pelos entes da conexão, nesse caso será Alice e Bruno;

2. Bruno e Alice geram números aleatórios Xa e Xb, respectivamente, sendo que Xa e Xb são menores que p, esses números gerados são as chaves privadas se comparado com um método assimétrico;

3. Bruno e Alice calculam as senhas públicas Ya≡ aXa(mod p), Yb≡ aXb(mod p) respectivamente; 

4. Alice e Bruno trocam as senhas (números) publicas;

5. Bruno calcula K≡ YbXa(mod p)

                          K≡ aXbXa(mod p)


    Alice calcula K≡ YaXb(mod p)

                        K≡ aXaXb(mod p)

 

6. E assim eles possuem a mesma chave secreta K, vale ainda salientar que isso acontece para K sendo o menor numero inteiro positivo possível, ou seja, 0

, e isso sempre é possível de acontecer, pois o teorema de Euclides garante que existe K e para 0

ele é único.

 

Exemplo do Protocolo de Diffie-Helman

 

Passo 1: Alice e Bruno concordam com p e a gerados com um PRNG (Pseudo-Random Number Generator).

Suponha p=97 então uma raiz primitiva modulo 97 será a=5. Pois 596≡1 (mod 97).

Paaso 2: Alice e Bruno geram seus números secretos Xa e Xb respectivamente.

Suponha agora que Bruno e Alice geram aleatoriamente com um PRNG Xa=36 e Xb=58 respectivamente.

Passo 3: Alice e Bruno calculam os números públicos Ya e Yb respectivamente.

Bruno calcula Ya≡ aXa(mod p)

                     Ya≡ 536(mod 97) com 536 = 14551915228366851806640625

                     Ya=50, isso acontece pelo fato de que o algoritmo sempre usa o menor Ya positivo, ou seja o resto da divisão de 536 por 97 de modo que 0a<97.

 

Alice calcula Yb≡ aXb(mod p)

                    Yb≡ 558(mod 97) com 558 = 3.4694469519536141888238489627838x1040

                    Yb= 44.

Passo 4: Bruno envia Yb para Alice e Alice envia Ya para Bruno.

Passo 5: Bruno e Alice calculam sua chave simétrica Ka e Kb, onde  Ka= Kb. E chamarei Ka e Kb apenas de K.

Bruno calcula  Ka≡ YbXa(mod p)

                      Ka≡ 4450(mod 97)

com 4450 = 1.4881058511424953988078608769806x1082

                      Ka= 75

 

Alice calcula Kb≡ YaXb(mod p)

                    Kb≡ 5044(mod 97) com 5044 = 5.684341886080801486968994140625x1074

                    Kb= 75.

Como mencionado acima Ka=Kb=K=75. Logo a chave simétrica deles será K=75.

 

Algumas Considerações

 

1. Dado Xa é relativamente fácil calcular;

2. Dado Ya é computacionalmente dificil calcular Xa. Esse é o problema do logaritmo discreto.

Pois teremos p|(Ya-aXa ) e daí exite c inteiro tal que Ya = cp + aXa ou aXa = Ya -cp.

Aplicando o logaritmo na base a (loga) dos dois lados teremos:

loga (aXa) = loga (Ya - cp)

Xa = loga (Ya - cp), onde é computacionalmente difícil encontrar Xa com p suficientemente grande.

 

  

Bibliografia

 

SAMPAIO, J. Edson. Introdução a Criptografia e seu uso no PHP. http://www.devmedia.com.br/articles/viewcomp.asp?comp=10045, acessado em 20/10/2008.

 

D´AVILA, Marcio. Criptografia de Chave Publica. www.mhavila.com.br/aulas/seguranca/material/segredes04.pdf, acessado em 20/10/2008.

 

CAMAPUM, J. F.. criptografia de chave pública.

 http://www.ene.unb.br/~juliana/cursos/teoriainf/aula3-crip-chavepub.pdf, acessado em 20/10/2008.

Viktoria Tkotz, Criptografia - Segredos Embalados para Viagem. Novatec Editora.

 

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?