Algoritmos Assimetrica ou chave publica ElGamal, Rabin, e Diffie-Hellman.

Algoritmos Assimetrica ou chave publica ElGamal, Rabin, e Diffie-Hellman.

(Parte 1 de 2)

Algoritmos assimétricos ElGamal, Rabin, e Diffie-Hellman.

Autor: Cristiano Gilberto João

1 Cristiano Gilberto João

1. Siglas e Conceitos2
2. Resumo3
3. Introdução4
4. O Pequeno Teorema de Fermat5
5. Criptografia Assimétrica6
6. Principais Algoritmos De Chave Pública Ou Criptografia Assimétrica7
7.1. ElGamal7
7.1.1. A Geração de Chaves na Criptografia ElGamal7
7.1.2. Etapa de Ciframento [6]:7
7.1.3. Etapa de Deciframento [6]:8
7.1.4. Exemplo 1:8
7.2. A Criptografia Rabin8
7.2.1. Geração das Chaves na Criptografia Rabin [7]8
7.2.2. Etapa de Ciframento8
7.2.3. Etapa de Deciframento9
7.2.4. Exemplo 2:9
7.3. Diffie-Hellman10
7.3.1. Etapas da implementação [9]10
7.3.2. Exemplo 3:1
8. Conclusão13
9. Anexos14

Índice 10. Bibliografia ............................................................................................................................. 15

2 Cristiano Gilberto João

1. Siglas e Conceitos Disponibilidade - garantir que os dados são acessíveis quando e onde forem necessários.

Integridade - garantir que os dados não são alterados acidente ou intencionalmente, de forma maliciosa.

Autenticidade - garantir a identidade de quem está enviando a mensagem. Não-repudiação - prevenir que alguém negue o envio e/ou recebimento de uma mensagem.

Privacidade - impedir que pessoas não autorizadas tenham acesso ao conteúdo da mensagem, garantindo que apenas a origem e o destino tenham conhecimento.

Confidencialidade - garantir que somente quem é suposto ter acesso aos dados é que pode acedêlos.

Problema do logaritmo discreto - Alguns criptos-sistemas, são baseados na dificuldade computacional do problema do logaritmo discreto que é o seguinte: Dado um primo p e inteiros g, t: 0 <g, t <p, calcular um inteiro s tal que t = g s mod p. Quando p é relativamente longo, ninguém até hoje (nem mesmo os pesquisadores especializados) descobriu um algoritmo eficiente, i.e., de tempo polinomial, para resolver este problema. A ideia então é incorporar esta dificuldade de solução em esquema criptográfico

Palavras-chaves: Segurança; Criptografia; Algoritmo; Chave-Publica; Chave-Privada; Assimétrica; Simétrica.

3 Cristiano Gilberto João

2. Resumo

A palavra criptografia provém dos radicais gregos kriptos (oculto) e grapho (escrita) e é o nome dado à ciência ou arte de codificar mensagens usando uma fórmula, que também será utilizada depois para decodificar a mesma mensagem. Na criptografia moderna, esta fórmula é chamada de algoritmo. Usada há milênios pela humanidade, a criptografia se tornou essencial para garantir a privacidade das comunicações no mundo atual, principalmente em redes de computadores públicas como a internet, por onde circulam dados pessoais, comerciais, bancários e outros. Conhecer, difundir e utilizar algoritmos criptográficos é essencial ao profissional de Tecnologia da Informação que no mundo moderno, entre suas atribuições deve proteger e garantir a privacidade das transações comerciais realizadas através de meios eletrônicos, assim é fundamental o entendimento das técnicas, seus algoritmos, protocolos e finalmente a maneira como estes lidam com a informação a ser mantida segura.

Palavras-chaves: Segurança; Criptografia; Algoritmo; Chave-Publica; Chave-Privada; Assimétrica; Simétrica.

4 Cristiano Gilberto João

3. Introdução

Quando falamos de informação e transportamos este conceito para o meio digital, particularmente na utilização das redes públicas de computação como a internet, onde são diversos serviços realizados é relevante ao ser humano à credibilidade nos sistemas computacionais, estes que inseridos nos fundamentos da segurança da informação, são definidos pela disponibilidade, integridade, confidencialidade, autenticidade, não-repudiação e finalmente a privacidade, os quais devem ser de livre compreensão e facilmente percetíveis ao se efetuar transações computacionais.

Assim é fundamental que técnicas computacionais sejam empregadas para que os requisitos de proteção da informação sejam atendidos; com base na implementação da criptografia, seja ela assimétrica ou simétrica. Onde na criptografia assimétrica a chave utilizada para encriptar não é usada para decrepitar, em contra ponto com a criptografia simétrica onde a chave que encripta é a mesma que decrépita.

Ao que concerne ao trabalho, o grupo vai debruçar sobre os algoritmos assimétricos, onde vai destacar: ElGamal, Rabin, e Diffie-Hellman. Pois dos algoritmos assimétricos propostos até hoje, apenas esses e mais alguns como o RSA e ECC é que são seguros e implementáveis, entretanto existe uma família de algoritmos úteis apenas para assinatura, e outros pouco práticos por serem inseguros, muito lentos ou usarem chaves muito longas [3].

5 Cristiano Gilberto João

4. O Pequeno Teorema de Fermat

Um resultado bastante útil durante os procedimentos de criptografia e deciframento de mensagens é o teorema enuciado abaixo.

Pequeno Teorema de Fermat. Se p > 1 é primo e a é um inteiro positivo não divisível por p, então:

Demonstração [8]. Seja a sequência de números inteiros positivos entre 1 até p − 1:

Multiplicando-se cada número dessa sequência por a(modp), obtém-se R = {x1,...,xp−1} um conjunto de resíduos módulo p. Como p não divide a, temos xi 6= 0; i = 1,...,p = 1. Além disso, x1,x2,...,xp−1 são todos distintos [5]. De fato, suponhamos que xi ≡ ia(modp) e xj ≡ ja(modp) são tais que xi = xj e i 6= j. Então, ia ≡ ja(modp), ou seja, i ≡ j (modp). Como 1 ≤ i,j ≤ p − 1, teremos i = j, uma contradição.

Portanto, o conjunto R é formado pelo conjunto de inteiros {1,2,3,...p − 1} em alguma ordem. Multiplicando todas essas congruências encontramos:

ap−1 ≡ 1(mod p), Como queríamos.

Observação [8]. A congruência ap ≡ a(modp) é válida quando a é divisível pelo primo p.

De fato, se mdc(a,p) 6= 1 e, como p é primo, então a = bp para algum inteiro positivo b. Logo, ou seja, p divide ap − a, que é equivalente a ap − a ≡ 0(modp), que significa ap ≡ a(modp). Exemplo 1: Tomando a = 13 e p = 17 temos:

6 Cristiano Gilberto João

5. Criptografia Assimétrica

Modelo de criptografia criado na década de 70, pelo matemático Clifford Cocks; na qual cada parte envolvida na comunicação usa duas chaves diferentes (assimétricas) e complementares, uma privada e outra pública [3]. A chave pública pode ficar disponível para qualquer pessoa que queira se comunicar com outra de modo seguro, mas a chave privada deverá ficar em poder apenas de cada titular. É com a chave privada que o destinatário poderá decodificar uma mensagem que foi criptografada para ele com sua respetiva chave pública; isto é, em um sistema de chave assimétrica cada pessoa tem duas chaves: uma chave pública que pode ser divulgada e outra privada que deve ser mantida em segredo [4]. Mensagens cifradas com a chave pública só podem ser decifradas com a chave secreta e vice-versa. A principal vantagem deste método é a sua segurança, pois não é preciso (nem se deve) compartilhar a chave privada. Por outro lado, o tempo de processamento de mensagens com criptografia assimétrica é muitas vezes maior do que com criptografia simétrica, o que pode limitar seu uso em determinadas situações [3]. O óbice deste sistema é a complexidade empregada no desenvolvimento dos algoritmos que devem ser capazes de reconhecer a dupla de chaves existentes e poder relacionar as mesmas no momento oportuno, o que acarreta num grande poder de processamento computacional [4].

7 Cristiano Gilberto João

6. Principais Algoritmos De Chave Pública Ou Criptografia Assimétrica

7.1. ElGamal

O ElGamal é algoritmo de chave pública utilizado para gerenciamento de chaves. Sua matemática difere da utilizada no RSA, mas também é um sistema comutativo [1]. O algoritmo envolve a manipulação matemática de grandes quantidades numéricas. Sua segurança advém de algo denominado problema do logaritmo discreto. Assim, o ElGamal obtém sua segurança da dificuldade de calcular logaritmos discretos em um corpo finito, o que lembra bastante o problema da factoração [1].

“Este algoritmo incorpora a dificuldade de solução do problema do logaritmo discreto na definição da função criptográfica. Para um primo p> 2 relativamente longo, considera-se um gerador g do conjunto Zp* dos inteiros relativamente primos a p” (Elgamal, 1985).

7.1.1. A Geração de Chaves na Criptografia ElGamal Na geração das chaves da Criptografia ElGamal, temos que [1]:

Escolher um número primo grande p e um gerador α do grupo multiplicativo Zp*. Selecionar ao acaso um número natural a < p − 1 e calcular αa (modp).

A chave pública é (p,α,αa) e a chave privada é a.

7.1.2. Etapa de Ciframento [6]: Nesta etapa o emissor A deverá:

Obter a chave pública (p,α,αa) de B; Converter as letras, números e símbolos da mensagem um números m entre 0 e p−1;

Escolher ao acaso um número natural b, tal que b < p − 1. • Para cada m obtido acima, calcular β ≡ αb (modp) e γ ≡ m(αa)b (modp);

• Enviar o ciframento c = (β,γ) de m para B;

8 Cristiano Gilberto João

7.1.3. Etapa de Deciframento [6]: Uma vez que o recetor B recebe a mensagem cifrada c, então deverá:

Usar a chave privada para calcular βp−1−a (mod p); Decifrar m calculando β−aγ (mod p).

Temos: β−aγ ≡ α−abmαab ≡ m(mod p) devido ao Teorema de Fermat.

7.1.4. Exemplo 1:

Para p = 2579, g = 2, S =765, T = 2765 mod 2579 = 949.

Para criptografar x = 1299 o emissor escolhe k = 853: y = 2853 mod 2579 = 435, e z =1299 x 949853 mod 2579 = 2396.

Para decriptografar (y,z) = (435,2396), o recetor calcula: 2396 (435765 ) mod 2579 = 1299.

7.2. A Criptografia Rabin

Veremos que este algoritmo é seguro e baseia-se na dificuldade computacional de um intruso calcular o texto legível a partir do conhecimento do texto ilegível correspondente. Onde essa dificuldade é equivalente a de fatorizar um inteiro em primos [8].

À semelhança da criptografia RSA, temos que determinar duas chaves para a criptografia Rabin: uma pública e outra privada.

7.2.1. Geração das Chaves na Criptografia Rabin [7] Na geração das chaves pública e privada da Criptografia Rabin, temos que:

Escolher dois números primos p e q distintos e grandes de maneira que p seja próximo de q e p ≡ q ≡ 3(mod4);

Calcular n = pq;

A chave pública (número que deve ser divulgado para o emissor A) é n e a chave privada (números que são mantidos em sigilo pelo recetor B) é (p,q).

7.2.2. Etapa de Ciframento Nesta etapa o emissor A deverá:

Obter a chave pública n do recetor B;

Converter as letras, números e símbolos da mensagem em números m entre 0 e n−1. (exemplo: supondo n > 46, a Tabela 1 pode ser utilizada);

Para cada número m, obtido nas conversões acima, calcular c ≡ m2 (modn);

9 Cristiano Gilberto João

Enviar a mensagem cifrada composta pelos números c dos cálculos acima para o recetor B.

7.2.3. Etapa de Deciframento

Uma vez que o recetor B recebe a mensagem cifrada composta pelos números c, então ele deverá:

Encontrar as quatro raízes quadradas mj com j = 1,2,3,4 de c módulo n. O número m, na mensagem original, é um dos mj.

Nota: O recetor B deve determinar qual das quatro possibilidades para os mj é a mensagem enviada.

Se a mensagem é um texto literário, então a tarefa é fácil, pois apenas um dos mj fará sentido. Entretanto, se o texto não for composto por palavras de um idioma, como por exemplo, uma sequência aleatória de números e letras, então pode não ser tão fácil determinar o mj correto. Uma maneira para superar este problema é acrescentar redundâncias binárias na mensagem original convertida para a base binária. Para isto, basta repetir uma quantidade fixa de dígitos no final da mensagem. Assim, o mj correto irá reproduzir essas redundâncias, enquanto que é altamente improvável que uma das três outras raízes quadradas mj venha a reproduzir essas redundâncias. Portanto, o recetor B pode escolher corretamente a mensagem enviada [6].

7.2.4. Exemplo 2: Vamos supor que o texto legível a ser enviado por um emissor seja “DABAC”, e vamos supor que a redundância consiste em repetir as duas últimas letras, resultando “DABACAC”. Com a representação de cada letra a um número: a letra “A” representa 1, “B” 2, etc. Assim o texto “DABACAC” é representado pelo número m = 4121313. A chave secreta do recetor é q = 1123 e r = 7723. A chave pública do recetor é n = q.r = 1123 x 7723 = 8672929.

O emissor calcula o texto ilegível c = m2 mod n = 41213132 mod8672929 = 577647 e envia C.

O recetor recebe c e efetua os seguintes cálculos:

3. Q mod r = 1123 mod 7723 = 1623; 4. R mod q = 7723 mod1123 = 887;

10 Cristiano Gilberto João

5. (X2 q Q) mod n = (4954 x 1123 x 1623) mod 8672929 = 784977; 6. (X1 r R) mod n = (1026 x 7723 x 887) mod 8672929 = 3336336; 7. X0= (X2 q Q + X1 r R) mod n = (784977 + 3336336) mod 8672929 =4121313; a outra raiz é n – x0; o receptor reconhece que x0 é m, pois contém a redundância estabelecida; 8. X0 = (X2 q Q - X1 r R) mod n = (784977 – 3336336) mod 8672929 =6121570; a outra raiz é n – x0.

7.3. Diffie-Hellman

A troca de chaves de Diffie-Hellman é um método de criptografia específico para troca de chaves desenvolvido por Whitfield Diffie e Martin Hellman e publicado em 1976 [9]. Foi um dos primeiros exemplos práticos de métodos de troca de chaves implementado dentro do campo da criptografia. O método da troca de chaves de Diffie-Hellman permite que duas partes que não possuem conhecimento a prior de cada uma compartilhar uma chave secreta sob um canal de comunicação inseguro. Tal chave pode ser usada para encriptar posteriores mensagens usando uma esquema de cifra de chave simétrica [9].

Antes de 1975 se alguém falasse que seria possível a troca de informações criptografadas entre duas partes sem que houvesse uma troca de chaves secretas entre ambas as partes provavelmente muitos matemáticos diriam ser impossível. Mas em 1976 o algoritmo Diffie-Hellman foi inventado. O maior problema para que isso acontecesse foi a dificuldade de cálculos de logaritmos discretos em um campo infinito [9].

7.3.1. Etapas da implementação [9]

1. A e B acordam em um grupo cíclico finito G e um elemento gerador g em G.( Isto é usualmente feito muito antes do resto do protocolo; assume que g é conhecido por todos os atacantes.) Nós vamos escrever o grupo G de modo multiplicativo.

2. A escolhe um número natural aleatório a e envia ga para B. 3. B também escolhe um número natural aleatório b e envia gb para A. 4. A calcula (gb)a.

1 Cristiano Gilberto João

5. B calcula (ga)b.

Tanto A quanto B estão agora de posse de elemento de grupo gab, que pode servir como a chave secreta compartilhada. Os valores de (gb)a e (ga)b são os mesmos porque os grupos são associativos a potência.

Com o objetivo de decifrar uma mensagem m, enviada como mgab, B (ou A) deve primeiro calcular (gab)-1, da seguinte maneira:

B sabe |G|, b, e ga. Um resultado da teoria de grupos estabelece que a partir da construção de G, x|G| = 1 para todo x em G.

Quando A envia a B a mensagem encriptada, mgab, B aplica (gab)-1 e recupera mgab(gab)-1 = m(1) = m.

A implementação utiliza grupos multiplicativos de inteiros módulo p, onde p é um número primo e g é uma raiz primitiva módulo p.

7.3.2. Exemplo 3: 1. A e B entram em acordo para usar um número primo p=23 e como base g=5.

2. A escolhe um inteiro secreto a=6, e então envia a B A1 = ga mod p A1 = 56 mod 23

A1 = 8 3. B escolhe um inteiro secreto b=15, e então envia a A B1 = gb mod p B1 = 515 mod 23

B1 = 19 4. A calcula s = B1 a mod p s = 196 mod 23

12 Cristiano Gilberto João

s = 2 5. B computes s = A1 b mod p s = 815 mod 23

6. A e B compartilham agora uma chave secreta: s = 2. Isto é possível porque 6*15 é o mesmo que 15*6. Alguém que tenha descoberto estes dois inteiros privados também será capaz de calcular s da seguinte maneira:

13 Cristiano Gilberto João

8. Conclusão

Como pudemos observar ao decorrer do trabalho, a criptografia de chave pública é baseada em dificuldades computacionais. Com a evolução tecnológica cada vez mais acelerada, os computadores têm a capacidade de processamento aumentada periodicamente. É necessário aprimorar constantemente os sistemas criptográficos, prova disso, a segurança em redes de computador é uma das áreas que mais buscam alternativas para um maior desenvolvimento. Outro fator que leva à criptografia de chave pública a ser valorizada é a tendência cada dia maior do crescimento do comércio eletrônico, que sem dúvida seria inviável sem uma criptografia que proporcione total segurança aos usuários.

(Parte 1 de 2)

Comentários