Embed Size (px)
Citation preview
A MATEMÁTICA DOS CÓDIGOS CRIPTOGRÁFICOS Paloma Barbosa Freire Universidade Católica de Brasília Curso de Matemática e-mail: [email protected] José Eduardo Castilho Universidade Católica de Brasília Curso de Matemática e-mail: [email protected]
RESUMO O presente trabalho apresenta um estudo comparativo da Cifra de César, Cifra de Vigenère, Máquina
Enigma, RSA e Esquema Rafaella, com os seus criptosistemas usados. Para isso foram desenvolvidos os
códigos utilizados em cada um dos tipos de criptografia citado. Nesse artigo foi relatada uma breve
história, detalhado o criptosistemas e em seguida cada criptografia foi desenvolvida. Finalizando com
uma breve citação das cifras expostas.
Palavras Chaves: criptografia, criptosistemas. 1. INTRODUÇÃO
A Criptografia teve indícios pelos chineses para a proteção dos segredos políticos e
militares. A palavra é composta por dois termos gregos kryptos (kyptos - secreto,
escondido, oculto) e grapho (grapho – escrita, grafia). Ela é a ciência (ou arte) de
escrever uma mensagem original em cifras ou códigos, tornando-a incompreensível e
difícil de ser decifrada ou decodificada.
A criptografia é o estudo de técnicas matemáticas, relacionadas com a
confidencialidade, integridade, autenticação de dados, ou seja, consiste na substituição
de dados num código secreto como medida de segurança para que possam existir
comunicações seguras. O mais interessante é que a metodologia da criptografia não
mudou muito até meados do século XX. Somente depois da Segunda Guerra Mundial,
com o aparecimento do computador, a área realmente floresceu utilizando algoritmos
matemáticos mais sofisticados e se tornando difícil a sua resolução necessitando de um
conhecimento mais aprofundado nos conceitos matemáticos. Na verdade, a criptografia
formou a base para a ciência da computação moderna.
O rápido avanço tecnológico exige sistemas de segurança cada vez mais complexos
onde a criptografia deve ser implantada de forma integrada, fornecendo um escudo extra
para proteger dos dados.
2Desde então, técnicas criptográficas têm sido utilizadas nas mais diversas áreas como
operações militares, serviços como e-mail, telefonia celular, acesso seguro à internet,
transações comerciais, autenticação de usuários, uso de serviços bancários e várias
outras operações (KUNST e RIBEIRO, 2004).
O desenvolvimento da matemática, em especial na área de Teoria dos Números, tem
proporcionado um avanço significativo da criptografia (CAVALCANTE, 2005). Novas
técnicas de codificação têm sido desenvolvidas de tal forma que a decodificação por
intermédio de computadores é praticamente inviável. Todo sistema criptográfico pode
ser descrito num modelo matemático, onde, o que difere são as funções de codificação e
decodificação. Neste trabalho, apresentam-se alguns sistemas criptográficos e o
respectivo modelo matemático.
2. UMA BREVE HISTÓRIA DA CRIPTOGRAFIA A escrita por meios de códigos começou a ser conhecida pelo relato feito por Heródoto
um historiador romano, por volta do quinto século antes de Cristo, que relatou os
conflitos ocorridos entre Grécia e Pérsia. Nesta batalha se lutava pela liberdade, onde a
escrita secreta foi fundamental na guerra. A estratégia utilizada pelos Persas foi
organizarem secretamente um exército militar para combater a Grécia, seu plano era o
ataque surpresa. No entanto não contavam que a Grécia usasse uma arma mais forte que
era a arte da escrita secreta. O grego Demarato que morava na Pérsia, escreveu em um
par de tabuletas raspando a cera e escrevendo a mensagem. Depois de escrita a cobria
novamente para assim ser passada pelos guardas sem ser descoberta (SINGH, 2002).
Com isso em 23 de setembro de 480 a.C, Xerxes líder dos Persas atacou a Grécia que o
esperava bem preparada. Assim Xerxes perdeu a batalha pelo fato de não ter realizado o
combate de forma surpresa. Esse tipo de criptografia, ocultação de mensagem, é
conhecido como esteganografia originada da palavra grega steganos (coberto) e
graphein (escrever). (SINGH, 2002).
A criptografia mais conhecida surgiu nas Guerras da Gália de Júlio César, e por este
motivo ficou conhecida como cifra de César. Ele substituía cada letra na mensagem por
outra que estivessem três casas à frente no alfabeto. Este tipo de criptografia por
substituição, que emprega um alfabeto, é chamado de cifras monoalfabéticas. (SINGH,
2002).
3Criptografia por substituição era muito usada, o que tornava conhecido o seu método
de cifrar e decifrar sendo de fácil acesso a descoberta da mensagem criptografada. Com
isso surgiu uma nova forma de criptografia feita por substituição criada por Blaise de
Vigenère em 1563. Baseado não apenas em um, mas sim em 26 alfabetos cifrados.
Utiliza a Cifra de César de forma diferente para cada alfabeto, formando assim uma
tabela, chamada de Quadrado de Vigenère. Esse por sua vez é denominado de cifra
polialfabética, e foi utilizado por muito tempo, sendo quebrada somente em 1854.
Durante muitos outros anos nenhum outro método de criptografia foi desenvolvido com
tanta segurança (SINGH, 2002).
Somente em 1918, o alemão Arthur Scherbius desenvolveu uma nova forma de
criptografar. Ele construiu uma máquina cifrante, chamada Enigma, que era composta
de três elementos: Um teclado para introduzir a mensagem; Um misturador que
permutava o alfabeto: Um mostrador para visualizar a mensagem cifrada (SINGH,
2002). Aqui se inicia a troca das cifras de papel e lápis por uma mais moderna que
utilizava a tecnologia do início do século XX. Em 1926 o Exército Alemão a utilizou
fazendo algumas modificações obtendo a rede de comunicação mais segura da época
(SULZBACH, 2003). Em 1940 Alan Turing e sua equipe da inteligência britânica
construíram o primeiro computador operacional e seu propósito especificamente era
decifrar mensagens alemãs cifradas pela Máquina Enigma. Esta primeira máquina
(computador) foi substituída em 1943, recebendo o nome de Colossus, com a tecnologia
de válvulas era capaz de realizar diversos cálculos capaz de quebrar códigos da
Máquina Enigma.
Após a Segunda Guerra Mundial com o desenvolvimento de computadores e outras
tecnologias a criptografia foi tornando-se mais complexa. Em1977 a equipe Rivest,
Shamir e Adleman desenvolveram um estudo de criptografar usando uma função de
mão única. Composta de duas chaves diferentes, uma delas pública que visa: a
autenticação de destino, que garante que somente o destinatário consiga ler a
mensagem; a autenticação da origem, que evita a falsificação da identidade do emissor;
a detecção de integridade de informação que evita outra pessoa leia e altere a
informação (MONTEIRO, 2002). A outra é a chave privada que é usada para decifrar a
mensagem, assim esse algoritmo é chamado de algoritmo assimétrico. A importância
deste tipo de sistema é que viabiliza a troca de informações, de forma segura, via
4internet. Essa criptografia ficou conhecida como RSA, onde basea-se em função
modular e conhecimento em teoria dos números. Nos tempos de hoje utilizasse sistemas
de criptografia de chave publica, onde as chaves são números com ordem de grandeza
elevado. Este é o ponto chave da segurança destes sistemas, pois, “todos os
computadores do planeta levariam mais tempo do que a idade total do universo para
quebrar a cifra” (SINGH, 2002).
Com essa breve historia da criptografia percebe-se que tanto a matemática quanto a
criptografia estão interligadas, sendo que esse processo é continuo, onde a criptografia
moderna é definida a partir do algoritmo aplicado, que este por sua vez é definido pelo
desenvolvimento ocorrido nas disciplinas aplicadas.
3. CRIPTOSISTEMAS Os criptosistemas correspondem aos fundamentos da criptografia. Nele é definida a
terminologia dos componentes dos mecanismos de codificação e decodificação.
As mensagens são definidas de duas formas, uma corresponde ao texto original (m), ou
seja, a mensagem sem sofrer alterações, já a outra forma é direcionada ao texto cifrado
(c), ou seja, a mensagem cifrada.
Em geral, um criptosistema pode ser representado por um modelo matemático
constituído dos seguintes elementos (SOUZA, 2004):
• Um conjunto finito A chamado de alfabeto de entrada, que pode ser o alfabeto
latino ou sua representação numérica em código ASCII.
• Um conjunto M formado por cadeias finitas de elementos de A, onde cada
elemento corresponde a um texto simples, não cifrado.
• Um conjunto C formado por cadeias finitas de elementos de A, onde cada
elemento de C corresponde a um texto cifrado.
• Um conjunto K de elementos chamados chaves, que são as ferramentas
necessárias para a realização dos processos de codificação de decodificação.
• O espaço E de funções eE : M→C, e ∈K, que codificam a mensagem.
• O espaço D de funções dD :C→M, d ∈K, que decodificam a mensagem.
5Para cada elemento k1 em K defini-se uma única bijeção de M em C, que garante a
existência de k2 em K que determina a função inversa para a decodificação.
Destaca-se que sistemas simétricos são caracterizados por usarem k1 = k 2 , pois no
processo é utilizada a mesma chave tanto para codificar quanto para decodificar. Nos
sistemas assimétricos usa-se k1 ≠ k 2 onde uma das chaves é de conhecimento público
para a codificação e a outra a chave é privada e usa-se para a decodificação. Observa-se
que sistemas simétricos exigem que cada participante do processo tenha conhecimento
da chave e no assimétrico não seria necessário.
Existem várias formas de se considerar o alfabeto de entrada. Uma delas seria
considerar o código ASCII, em que cada letra é representada por um valor inteiro. Nos
modelos apresentados a seguir, deve-se considerar que o alfabeto é composto somente
por letras minúsculas, cujo código ASCII é dado no Quadro 1.
Quadro 1 – Código ASCII Alfabeto original a b c d e f g h i j k l m n o p q r s t u v w x y z
Código ASCII 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
Seguindo este modelo, serão descritos alguns sistemas criptográficos. 4. CIFRA DE CÉSAR Essa criptografia foi proposta por Júlio César com objetivos militares nas Guerras da
Gália. Esta usa o conceito de translação letras do alfabeto, onde cada letra do alfabeto é
relacionada com a letra que está a três casas a frente ocorrendo assim uma substituição
da letra a pela D, b por E e assim por diante (Ver no Quadro 2).
Quadro 2 - Cifra de César
Alfabeto original a b c d e f g h i j k l m n o p q r s t u v w x y z
Alfabeto cifrado D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
De acordo com a descrição do modelo de um criptosistema, dada na seção anterior, a
Cifra de César pode ser descrita pelos seguintes elementos:
6A: alfabeto em código ASCII descrito no Quadro 1.
M = Conjunto das mensagens a serem codificadas.
C = Conjunto das mensagens codificadas.
K = Conjunto das chaves de codificação e decodificação {1,2,...,25}
k 1 ,k 2 chaves de codificação e decodificação.
E : M→ C, f( x , k 1 ) = 97 + (x -97+ k1 ) mod(26)
D : C→ M, g( x , k 2 ) = 97 + (x -97- k2 ) mod(26)
Neste caso tem-se que a Cifra de César é um sistema particular do modelo acima, com
que k1 = k 2 =3, sendo assim um sistema simétrico. Outra observação, é que o uso da
função modular é necessário para que o código gerado permaneça dentro do intervalo de
variação do alfabeto como descrito no Quadro 1.
De acordo com Simon Singh, (2002) “que César deslocava as letras em três casas, fica
claro que, empregando-se qualquer deslocamento entre uma das 25 casas, é possível
criar 25 códigos distintos” (p.27). Esse processo pode ser representado pelo modelo
acima, usando valores diferentes valores de chaves do conjunto K, mas mantendo k1 =
k 2 . Para melhor entendimento, aplicando o criptosistema da Cifra de César como
exemplo, para criptografar a mensagem freire. Utilizando passo a passo como foi
descrito acima. Para transformar a mensagem em números teremos como base o
Quadro 3.
Quadro 3: Exemplo de aplicação da Cifra de César
Criptografia - E : M→ C Decriptografia - D : C→ M
Mensagem Seqüência ( )( )26mod39797 +−+ x Texto Cifrado ( )( )26mod39797 −−+ x Texto Original Mensagem
F 102 ( )( )26mod39710297 +−+ 105 ( )( )26mod39710597 −−+ 102 F
R 114 ( )( )26mod39711497 +−+ 117 ( )( )26mod39711797 −−+ 114 R
E 101 ( )( )26mod39710197 +−+ 104 ( )( )26mod39710497 −−+ 101 E
I 105 ( )( )26mod39710597 +−+ 108 ( )( )26mod39710897 −−+ 105 I
R 114 ( )( )26mod39711497 +−+ 117 ( )( )26mod39711797 −−+ 114 R
E 101 ( )( )26mod39710197 +−+ 104 ( )( )26mod39710497 −−+ 101 E
Para o exemplo acima foi usado os procedimentos implementados no Maple, descritos no Anexo A.
7 5. CIFRA DE VIGENÈRE Vigenère criou uma criptografia que necessitava de uma tabela tanto para criptografar
quanto para decriptografar. Esta consiste de 26 alfabetos, sendo que na primeira linha
está o alfabeto na ordem correta e nas linhas seguintes utiliza-se a Cifra de César
deslocando uma casa em comparação com a linha anterior como é demonstrado no
Quadro 4.
Quadro 4 - Cifra de Vigenère
Alfabeto correto a b c d e f g h i j k l m n o p q r s t u v w x y z
1 B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 2 C D E F G H I J K L M N O P Q R S T U V W X Y Z A B 3 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 4 E F G H I J K L M N O P Q R S T U V W X Y Z A B C D 5 F G H I J K L M N O P Q R S T U V W X Y Z A B C D E 6 G H I J K L M N O P Q R S T U V W X Y Z A B C D E F 7 H I J K L M N O P Q R S T U V W X Y Z A B C D E F G 8 I J K L M N O P Q R S T U V W X Y Z A B C D E F G H 9 J K L M N O P Q R S T U V W X Y Z A B C D E F G H I 10 K L M N O P Q R S T U V W X Y Z A B C D E F G H I J 11 L M N O P Q R S T U V W X Y Z A B C D E F G H I J K 12 M N O P Q R S T U V W X Y Z A B C D E F G H I J K L 13 N O P Q R S T U V W X Y Z A B C D E F G H I J K L M 14 O P Q R S T U V W X Y Z A B C D E F G H I J K L M N 15 P Q R S T U V W X Y Z A B C D E F G H I J K L M N O 16 Q R S T U V W X Y Z A B C D E F G H I J K L M N O P 17 R S T U V W X Y Z A B C D E F G H I J K L M N O P Q 18 S T U V W X Y Z A B C D E F G H I J K L M N O P Q R 19 T U V W X Y Z A B C D E F G H I J K L M N O P Q R S 20 U V W X Y Z A B C D E F G H I J K L M N O P Q R S T 21 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 22 W X Y Z A B C D E F G H I J K L M N O P Q R S T U V 23 X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 24 Y Z A B C D E F G H I J K L M N O P Q R S T U V W X 25 Z A B C D E F G H I J K L M N O P Q R S T U V W X Y 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Para o uso da tabela será necessário uma palavra chave para definir as linhas que vão ser
utilizadas, como por exemplo, a mensagem “Código” tendo a palavra chave freire que
deverá ser associada a frase que vai ser criptografada como mostra no Quadro 6.
A Cifra de Vigenère pode ser vista de uma forma matemática de acordo com o esquema
proposto em Criptosistemas:
A: alfabeto em código ASCII descrito no Quadro 1.
M = Conjunto das mensagens a serem codificadas.
C = Conjunto das mensagens codificadas.
K = Conjunto das chaves de codificação e decodificação {1,2,...,25}
8k 1 , k 2 ,...k n chaves de codificação e decodificação.
E : Mn
→ Cn
, onde n é o número de caracteres da palavra chave
F(x 1 ,x 2 ,... ,xn ) = F( f(x 1 ,k 1 ), f(x 2 ,k 2 ), ... , f(xn ,k n ) )
D : Cn
→ Mn
,
G(x 1 ,x 2 ,... ,xn ) = G( g(x1 ,k 1 ), g(x 2 ,k 2 ), ... , g(xn ,k n ) ),
onde, f(xs ,k s ) e g(xs ,k s ) são as funções de codificação e decodificação do modelo
da Cifra de César. Neste caso, a Cifra de Vigenère também é um sistema simétrico.
Dessa forma se tornam mais fácil o entendimento do processo de cifrar e decifrar para
cada letra do sistema de Cifra de Vigenère.
No Quadro 6 representa todo o processo da codificação e decodificação, com base nos
dados expostos no Quadro 1.
Quadro 6: Exemplo de aplicação da Cifra de Vigenère
Criptografia - E : Mn
→ Cn
Decriptografia - D : C
n→ M
n
Mensagem k n Seqüência 97+(x-97+ k n )(mod26) Texto Cifrado 97+(x-97- k n )(mod26) Seqüência Mensagem
C F 5 99 97+(99-97+5)(mod26) 104 97+(104-97-5)(mod26) 99 C
O R 17 111 97+(111-97+17)(mod26) 102 97+(102-97-17)(mod26) 111 O
D E 4 100 97+(100-97+4)(mod26) 104 97+(104-97-4)(mod26) 100 D
I I 8 105 97+(105-97+8)(mod26) 113 97+(113-97-8)(mod26) 105 I
G R 17 103 97+(103-97+17)(mod26) 120 97+(120-97-17)(mod26) 103 G
O E 4 111 97+(111-97+4)(mod26) 115 97+(115-97-4)(mod26) 111 O
O procedimento da Cifra de Vigenère, pode ser implementado com base na Cifra de César (Veja os códigos descritos no Anexo B).
6. MÁQUINA ENIGMA A Máquina Enigma é um sistema de cifrar mensagens substituindo as letras por outras.
Para que isso aconteça ocorre um tipo de permutação com o alfabeto. Esse sistema foi
uma revolução na época, pelo fato de ser o primeiro sistema que usou recursos
tecnológicos. A peça principal da máquina é o misturador de borracha em um formato
de disco com fios que ligam o teclado ao mostrador. A mensagem é criptografada a
medida em que gira o misturador, pois ele é definido de acordo com a quantidade de
9letras fornecidas na máquina, sendo que em um alfabeto completo de 26 letras é
determinado um vinte e seis avos de um giro completo (SINGH, 2002).
O método de cifragem é mais bem detalhado na figura 1, onde qualquer que seja a
permutação dos rotores nenhuma letra é codificada nela própria.
Figura 1: Máquina Enigma (fonte: http://www.ncc.up.pt/~pbv/enigma/nivel1.html)
Quando são usados três misturadores com um alfabeto de 26 letras, é aumentado a sua
quantidade de troca de 26 para 26x26x26, ou seja 17.576 alfabetos cifrados (SINGH,
2002).
Maquina Enigma é representada por uma permutação no alfabeto, onde cada letra é
substituída por outra (ou seja, bijetiva). Esse processo é contínuo sendo que nesse
esquema os rotores seguem para o refletor, e assim voltando aos rotores. No exemplo
seguinte é visto o sistema de três rotores onde aplicado a permutação:
p = A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C B E I M H R K Q V D L T Z J A G X P U S Y N W O F
q = A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C D X F I M E T L S O P U W G H Q R Z V Y J K N A B
r = A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
E K D J N L W C B M I O A U V T H X S Z R P F Y Q G
Aplicando:
x → p(x) → q(p(x)) → r(q(x)) Transformando:
10
K → (aplicando p) → D → (aplicando q) → F→ (aplicando r) → L
Assim, a letra K é substituída por L.
Já o refletor sua permutação não pode ser aleatória ou arbitrária, é nele que recebe a
corrente dos rotores e a envia novamente para outras modificações. Ele deve seguir duas
regras:
• Não envia nenhuma letra nela própria – corrente não pode circular nos dois
sentidos no mesmo fio.
• Deve ser recíproco – aplicando duas vezes adquirimos a letra original.
Na tabela abaixo é um exemplo de permutação do refletor, definido por u:
u = A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Y R G M O Q C L X S T H D U E Z F B J K N W V I A P
Ao sair do refletor a corrente retorna passando pelos rotores, como é o processo de volta
é aplicado à permutação inversa (é somente trocar a primeira linha pela segunda, e vice-
versa). Portanto ao juntarmos todos os processos aqui detalhados podemos definir as
funções E e D , assim formalizando o sistema da maquina enigma para três rotores:
p → q → r → u → r− 1
→ q− 1
→ p− 1
(rotores) (refletor) (inversa dos rotores) A: alfabeto em código ASCII descrito no Quadro 1.
M = Conjunto das mensagens a serem codificadas.
C = Conjunto das mensagens codificadas.
K = Conjunto das chaves de codificação e decodificação formada pelas permutações de
A.
p, q, r, u chaves de codificação e decodificação.
E : M→ C, f(x) = p(x) . q(x) . r(x) . u(x) . r− 1
(x). q− 1
(x). p− 1
(x)
D : C→ M g(x) = p(x) . q(x) . r(x) . u(x) . r− 1
(x). q− 1
(x). p− 1
(x)
Observe que f(x) = g(x), pois as permutações satisfazem de p.p− 1
se resulta na
identidade. Abaixo é mostrado a inversa de p, denotada como p− 1
:
p 1− = C B E I M H R K Q V D L T Z J A G X P U S Y N W O F
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
11
p.p− 1
= id
id = A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Exemplo de codificação com as permutações acima e considerando que o disco 1 gira a
cada letra, o disco 2 a cada 2 e o disco 3 a cada 3. Com isto temos FREIRE codificado
para MUSFOY decodifica novamente na mensagem FREIRE.
Quadro 7: Exemplo de aplicação da codificação da Enigma
Criptografia - E : M→ C Decriptografia - D : C→ M
Mensagem Seqüência Seqüência Codificada
Texto Cifrado
Seqüência Decodificada Mensagem
F 102 109 M 102 F
R 114 117 U 114 R
E 101 115 S 101 E
I 105 102 F 105 I
R 114 111 O 114 R
E 101 121 Y 101 E
O exemplo acima foi gerado pela implementação da Máquina Enigma descrita no Anexo C 7. CRIPTOGRAFIA RSA O sistema RSA foi criado por Rivest, Shamir e Adleman onde as iniciais dos nomes dos
seus criadores deram o nome RSA. Esse sistema se baseia nos conceitos de Teoria dos
Números onde será demonstrada passo a passo que se baseia a Criptografia RSA:
1º - transformar as mensagens em uma seqüência de números, na regra que desejar.
Como por exemplo: A: alfabeto em código ASCII descrito no Quadro 1.
M = Conjunto das mensagens a serem codificadas.
C = Conjunto das mensagens codificadas.
2º - escolher dois primos muito grandes, denominados p e q .
3º - calcular ( ) ( )( )11 −−= qpnϕ onde qpn .= , que ( )sϕ é o número de inteiros
menores ou iguais a s que são relativamente primos com s (fundamento ϕ de Euler).
12 4º - escolher um número d que satisfaça MDC ( )( ) 1, =nd ϕ , onde d e ( )nϕ sejam co-
primos, utilizando o Algoritmo de Euclides.
5º - em seguida calcula-se ( )( )nde ϕmod1. ≡ , sendo encontrado e utilizando
congruências.
6º - separar a mensagem em pequenas partes.
7º - calcular ( )nmc e mod≡ , para criptografar a mensagem. Sendo definido E , função
para criptografar. Assim: E : M→ C, ( )nmc e mod≡
8º - por último, para decodificar a mensagem calcula-se ( )ncm d mod≡ . Sendo definido
D , função para decodificar. Assim: D : C→ M, ( )ncm d mod≡
Logo o sistema RSA deve seguir todos os passos para que o resultado seja favorável.
Com isso destacam-se duas chaves (estas por sua vez definidas em criptosistemas como
k) para criptografar detalhada como ( )ne, e outra para decriptografar, ( )nd , .
De acordo com a descrição do modelo de um criptosistema, dada na seção anterior, as
chaves desse esquema pede ser descrita pelos seguintes elementos:
K = Conjunto das chaves de codificação e decodificação
k1 ≠ k 2 → ( )ne, ≠ ( )nd , chaves de codificação e decodificação.
Obseva-se que são utilizados duas chaves, sendo uma para criptografar e outra para
decodificar, definidas como chave pública e chave privada. Assim esse esquema é
chamado de Criptografia Assimétrica em que k1 ≠ k 2 , citado no item criptosistema.
Para melhor entendimento, aplicando o sistema RSA para criptografar a mensagem
freire, utilizando passo a passo como foi descrito acima. Para transformar a mensagem
em números teremos como base o Quadro 1.
Logo a mensagem freire é a seqüência de números 102 - 114 - 101 - 105 - 114 - 101.
Em seguida escolheremos 3=p e 11=q , agora podendo calcular:
qpn .= = 3 . 11 = 33
( ) ( )( )11 −−= qpnϕ = ( )( ) 2011113 =−−
O próximo passo a ser representado será descobrir d , onde é encontrado ao resolver a
operação MDC( ) 1,20 =d de acordo com o Algoritmo de Euclides, achando 7=d . Com
isso podemos resolver a equação ( )( )nde ϕmod1. ≡ ( )20mod17. ≡= e , de acordo com
congruências já citado anteriormente chegamos em 3=e .
13 É evidente no momento que as duas chaves necessárias para o sistema são a (3, 33)
para criptografar e (7, 33) para decriptografar. O Quadro 8 representa todo o processo
da codificação e decodificação.
Quadro 8: Exemplo da aplicação do esquema RSA.
Criptografia - E : M→ C Decriptografia - D : C→ M
Mensagem Seqüência ( )33mod3mc ≡ Texto Cifrado ( )33mod7cm ≡ Texto Original Mensagem
F 102 ( ) 2733mod1023 =≡c 27 ( ) 10233mod277 =≡m 102 F
R 114 ( ) 933mod1143 =≡c 9 ( ) 11433mod97 =≡m 114 R
E 101 ( ) 833mod1013 =≡c 8 ( ) 10133mod87 =≡m 101 E
I 105 ( ) 1833mod1053 =≡c 18 ( ) 10533mod187 =≡m 105 I
R 114 ( ) 933mod1143 =≡c 9 ( ) 11433mod97 =≡m 114 R
E 101 ( ) 833mod1013 =≡c 8 ( ) 10133mod87 =≡m 101 E
A implementação do Sistema RSA encontra-se no Anexo D.
8. ESQUEMA RAFAELLA O sistema Rafaella foi desenvolvido em 2004 por Ribeiro e Weber com o objetivo de
criar um sistema de fácil cifra e de difícil decodificação. Esse esquema se baseia em
equações diferencias. sendo diferente de todos os outros que analisamos, pois, nesse
processo ocorre translação de funções. Equações diferenciais não é aplicada diretamente
mais sim dela se conseguiu o surgimento do sistema de criptografia Rafaella, baseando-
se em teoria dos grupos de Lie e simetrias em matemática discreta. (KUNST e
RIBEIRO, 2004).
Esse sistema destaca-se pelo fato de suas chaves privadas serem definidas pelos
componentes do sistema, onde uma deverá ser do emissor da mensagem e a outra do
receptor da mensagem criptografada.
Para que seja um processo de fácil entendimento foi dividida em etapas, que serão
definidas passo a passo:
• Utilizar o código de ASCII para transformar a mensagem em valores numéricos.
Como exemplo:
14 A: alfabeto em código ASCII descrito no Quadro 1.
M = Conjunto das mensagens a serem codificadas.
C = Conjunto das mensagens codificadas.
Mensagem F R E I R E
ASCII 102 114 101 105 114 101
• Escolher uma função real (0f ), contínua e “n” vezes derivável, onde a
quantidade de coeficientes deve ser a mesma da mensagem.
Podendo ser retratada da seguinte forma:
( ) ( ) ( ) ( ) ( ) ( ) ( )xxxxxx eeeeeexf 709,204,9456,045,2456,37564,80 101114105101114102 +++++=
• Criar as chaves privadas e públicas, tanto o emissor quanto o receptor. Os
componentes são responsáveis por essa etapa, por exemplo:
EMISSOR RECEPTOR
chave privada - ca chave pública - cpa chave privada - cb chave pública - cpb ica 927−= ( )2caxcpa −= icb 49+= ( )2cbxcpb −=
De acordo com a descrição do modelo de um criptosistema, dada na seção anterior, as
chaves desse esquema pede ser descrita pelos seguintes elementos:
K = Conjunto das chaves de codificação e decodificação
k1 ≠ k 2 chaves de codificação e decodificação.
São utilizadas duas chaves, sendo uma para criptografar e outra para decodificar,
definidas como chave pública e chave privada. Assim esse esquema é chamado de
Criptografia Assimétrica em que k1 ≠ k 2 , citado no item criptosistema.
• O emissor aplica sua chave privada que é um número complexo, na função
inicial ( 0f ), gerando assim uma nova função (1f ), onde é considerada a
primeira função para criptografar, da seguinte forma:
E 1 : M→ C
( ) ( )caxfxf += 01
15 • O emissor efetuar o argumento de autenticação definida como aa , o produto
das chaves públicas tanto do emissor como do receptor, somado a chave privada
do emissor elevado a uma potência maior que 4 pelo fato de estar trabalhando
com números complexos e ter um grau de dificuldade mais elevado.
kcacpbcpaaa += .
• Emissor envia a função (1f ) e o argumento aa para o receptor.
• O receptor aplica sua chave privada que é um número complexo, na função
inicial ( 1f ), assim gerando uma nova função (2f ), onde é considerada a segunda
função para criptografar, da seguinte forma:
E 2 : M→ C
( ) ( )cbxfxf += 12
• O receptor efetuar o argumento de autenticação definida como ab , o produto
das chaves públicas tanto do emissor como do receptor, somado a chave privada
do receptor elevado a uma potência maior que 4 pelo fato de estar trabalhando
com números complexos e ter um grau de dificuldade mais elevado.
Scbcpbcpaab += .
• Receptor gera outro argumento definido por tb , baseado na aplicação da sua
própria chave privada sobre o argumento aa , da seguinte forma:
( )cbaatb =
• Receptor envia a função (2f ), ab e tb para o emissor.
• Emissor calcula vb que consiste em retirar de tb sua chave privada. Assim
podendo verificar e ter a certeza da identidade de seu receptor, da seguinte
forma:
0=−= tbcavb k
• Emissor calcula o simétrico da sua chave privada em ( 2f ) gerando ( 3f ), onde é
possível definir a primeira função para decriptografar, da seguinte forma:
D 1 : C→ M
( ) ( )caxfxf −= 23
• Emissor gera outro argumento definido por ta , baseado na aplicação da sua
própria chave privada sobre o argumento ab , da seguinte forma:
16 ( )caabta =
• O emissor envia ta e ( 3f ) para o receptor.
• Receptor calcula va que consiste em retirar de ta sua chave privada. Assim
podendo verificar e ter a certeza da identidade de seu emissor.
0=−= tacbva S
• Receptor calcula o simétrico da sua chave privada em ( 3f ) gerando ( 4f ), onde é
possível definir a segunda função para decriptografar. Logo essa função gerada
se trata da função inicial assim (0f ) = ( 4f ), como foi indicado no exemplo na
primeira etapa, ocorrendo da seguinte forma:
D 2 : C→ M
( ) ( )cbxfxf −= 34
( ) ( ) ( ) ( ) ( ) ( ) ( )xxxxxx eeeeeexf 709,204,9456,045,2456,37564,84 101114105101114102 +++++=
04 ff =
( ) ( ) ( ) ( ) ( ) ( ) ( )xxxxxx eeeeeexf 709,204,9456,045,2456,37564,80 101114105101114102 +++++=
Com isso, foi definido todo o processo matemático do Esquema Raffaela que poderá ser
absorvido com mais clareza ao expressarmos no exemplo, gerado pelo código
apresentado no Anexo E.
8. CONCLUÇÃO Diversos são os esquemas para criptografar uma mensagem, assim tendo também as
mais diferentes formas de processos matemáticos tanto para cifrar como decifrar um
texto. Foram enfatizados, no entanto, os esquemas criptográficos de acordo com os
criptosistemas para que com isso a comparação da matemática utilizada em cada
esquema ficasse mais claro e mais fácil quanto à sua utilização.
Ao comparar os criptosistemas dos nos três primeiros códigos, constata-se que todas
devem pertencer ao intervalo correspondente ao alfabeto no processo de codificação e
decodificação, destacando-se a Cifra de César e Vigenère onde as funções de cifrar e
decifrar utiliza-se de função modular (mod 26). Já no RSA e Esquema Rafaella, o
processo não é necessário pertencer ao intervalo do alfabeto.
17 A Cifra de César e a Cifra de Vigenère foram detalhadas de acordo com seu modelo
no criptosistema, duas funções parecidas tanto para codificar quanto para decodificar a
mensagem. Assim esse tipo de criptografia, que faz uso da transposição da ordem das
letras do alfabeto, não se altera muito a forma que se é aplicada. Conclui-se que essas
cifras não são baseadas muito em cálculos matemáticos, e sim no raciocínio lógico
matemático. O mesmo acontece com a Máquina Enigma, onde nela ocorrem várias
permutações para sua codificação e para sua decodificação, com isso a mesma função
aplicada para cifrar é também utilizada para decifrar. Com isso ela também implementa
do raciocínio lógico matemático.
A Cifra RSA utiliza conceitos e métodos da matemática como a Teoria dos Números,
sendo assim um sistema mais complexo comparado com a Cifra de César e Vigenère,
pois necessita de um conhecimento mais avançado de matemática. Nesse processo foi
aplicado o mesmo procedimento que foi a ênfase com o criptosistema. Conclui-se em
um sistema que utiliza de muitos métodos matemáticos, mais de fácil codificação e
difícil decodificação. Já suas chaves públicas e privadas têm um desenvolvimento
seguro tanto na transmissão quanto na utilização.
O Esquema Rafaella é uma criptografia moderna, pois foi desenvolvida em 2004,
utilizando-se de conceitos e métodos mais avançados como equações diferenciais.
Baseia-se na dificuldade de se obter a função original, onde serão aplicadas operações
de translações sobre a função. Destaca-se o fato da sua chave privada ser criada pelo
próprio usuário e sua chave pública é gerada do surgimento de uma função (no exemplo
exposto - ( )2caxcpa −= ) onde a chave privada seja uma das raízes dela. Dependendo
da chave pública gerada, pode-se achar a chave privada, assim achando as raízes da
chave pública. Com isso ela se torna de fácil descoberta de suas chaves, pois temos
computadores tão modernos que esse tipo de informação não seria difícil. Uma forma
de se contornar este problema é modificar a criação da chave pública da seguinte forma:
( )2ycaxcpa −= , onde y passa a fazer parte da chave privada, sendo assim mais difícil
a sua descoberta.
Conclui-se que tanto as criptografias usadas nos tempos mais antigos como as utilizadas
nos tempos modernos têm franquezas e dificuldades. Mas em cada tempo, com seu
desenvolvimento matemático, faz com que sejam criadas criptografias mais complexas
18 e também com a evolução da matemática as cifras podem ser quebradas. Isto
signifique que o processo não é estático, mas sim um processo evolutivo e de constantes
mudanças.
REFERÊNCIAS BIBLIOGRÁFICAS RIBEIRO, V. G. ; WEBER, Raul Fernando . Problemas Computacionais para Esquemas de Criptografia de Chave Pública. In: 22o Simpósio Brasileiro de Redes de Computadores, 2004, Gramado. IV Workshop de Segurança em Sistemas Computacionais. Porto Alegre : II/UFRGS, 2004. p. 101-112. CAVALCANTE, André L.B. Teoria dos Números e Criptografia, 2005, Revista Virtual, Disponível: http://www.upis.br/revistavirtual/Cavalcante_%20Teoria%20dos%20N%FAmeros%20e%20Criptografia_2005_UPIS.pdf WEBER, Raul Fernando. Criptografia Contemporânea. 1995 Disponível: http://www.inf.ufsc.br/~mauro/curso/redes/cripto.doc KUNST, Rafael; RIBEIRO, Vinicius Gadis. Implementação do Esquema de Criptografia de Chave Pública Rafaella. Revista eletrônica de Sistema de Informações, Vol 3, Nº 1, 2004, Disponível: http:http://www.inf.ufsc.br/resi/edicao04/artigo07.pdf. SINGH, Simon. O Livro dos Códigos. Rio de Janeiro: Record, 2002. SOUZA, Raimundo Cândido. Criptografia de Chave Pública: Algoritmos que Possibilitam a Criação de Chave Assimétrica. 2006. SULZBACH, Jaime André. Análise de Viabilidade da Criptografia Quântica. 2003. MONTEIRO, César Alison. Implementação e Análise Comparativa de Quatro Variações do Criptossistema RSA. 2002. SOUZA, Bianca Amoras. Teoria dos Números e o RSA, 2004, Campinas : UNICAMP.2004.
19 ANEXOS Nesta seção são apresentados os códigos que foram implementados no Maple para cada um dos esquemas de criptografia que foram abordados no trabalho. A – Crifra de César # cifra de cesar para um passo k # codifica a mensagem # x: Código ASCII # k: passo do deslocamento cesar_code:=proc(x,k) local cm; cm:=97+(x-97+k mod 26); return cm; end proc;
# cifra de cesar para um passo k # decodifica a mensagem # x: Código ASCII # k: passo do deslocamento cesar_decode:=proc(x,k) local dm; dm:= 97+ (x-97-k mod 26); return dm; end proc;
B – Crifra de Vigenère # Cifra de Vigenere – Usa o procedimento da Cifra d e César. # codifica a mensagem # K: deslocamentos definidos pela palavra chave # n: número de deslocamentos. # m: bloco da mensagem Vige_code:=proc(K,n,m) local i,j,cm; cm:=vector(n); for i from 1 to n do cm[i]:=cesar_code(m[i],K[i]); end do; return cm; end proc;
# Cifra de Vigenere - Usa o procedimento da Cifra d e César. # decodifica a mensagem # K: deslocamentos definidos pela palavra chave
20 # n: número de deslocamentos. # cm: bloco da mensagem Vige_decode:=proc(K,n,cm) local i,j,m; m:=vector(n); for i from 1 to n do m[i]:=cesar_decode(cm[i],K[i]); end do; return m; end proc;
C – Máquina Enigma # Máquina Enigma. # codificação # p1,p2,p2: permutações que representam cada disco # u: permutação que representa o refletor # m: mensagem em código ASCII # n: tamanho da mensagem # v1,v2,v3: relação de voltas de cada disco Enigma_code:=proc(p1,p2,p3,u,m,n,v1,v2,v3) local pos,cm,c1,c2,c3,i,k; cm:=vector(n); c1:=0; c2:=0;c3:=0; for i from 1 to n do pos:=m[i]-97; pos:=((pos+c1) mod 26); pos:=p1[2,pos+1] ; pos:=((pos+c2) mod 26); pos:=p2[2,pos+1]; pos:=((pos+c3) mod 26); pos:=p3[2,pos+1]; pos:=u[2,pos+1]; k:=1; while pos <> p3[2,k] do k:=k+1; end do; pos:=p3[1,k]; k:=1; while pos <> p2[2,k] do k:=k+1; end do; pos:=p2[1,k]; k:=1; while pos <> p1[2,k] do k:=k+1; end do; pos:=p1[1,k]; cm[i]:=pos+97; if (i mod v1) = 0 then c1:= c1+1; end if; if (i mod v2) = 0 then c2:= c2+1; end if; if (i mod v3) = 0 then c3:= c3+1; end if;
21 end do; return cm end proc;
# Máquina Enigma. # decodificação # p1,p2,p2: permutações que representam cada disco # u: permutação que representa o refletor # m: mensagem em código ASCII # n: tamanho da mensagem # v1,v2,v3: relação de voltas de cada disco Enigma_decode:=proc(p1,p2,p3,u,m,n,v1,v2,v3) local pos,cm,c1,c2,c3,i,k; cm:=vector(n); c1:=0; c2:=0;c3:=0; for i from 1 to n do pos:=m[i]-97; pos:=p1[2,pos+1] ; pos:=p2[2,pos+1]; pos:=p3[2,pos+1]; pos:=u[2,pos+1]; k:=1; while pos <> p3[2,k] do k:=k+1; end do; pos:=p3[1,k]; pos:=((pos-c3) mod 26); k:=1; while pos <> p2[2,k] do k:=k+1; end do; pos:=p2[1,k]; pos:=((pos-c2) mod 26); k:=1; while pos <> p1[2,k] do k:=k+1; end do; pos:=p1[1,k]; pos:=((pos-c1) mod 26); cm[i]:=pos+97; if (i mod v1) = 0 then c1:= c1+1; end if; if (i mod v2) = 0 then c2:= c2+1; end if; if (i mod v3) = 0 then c3:= c3+1; end if; end do; return cm end proc; D – Esquema RSA # RSA. # codificação
22 # d,n: chave privada # cm: mensagem codificada RSA_code:=proc(e,n,m) local cm; cm:=(m^e) mod n; return cm; end proc;
# RSA. # decodificação # d,n: chave privada # cm: mensagem codificada RSA_decode:=proc(d,n,cm) local m; m:=(cm^d) mod n; return m; end proc; E – Esquema Rafaella # Rafaella. # decodificação # fo: funçao com coeficientes sendo o código da men sagem # ce: chave privada do emisor Rafaella_code:=proc(fo,ce) local f1; f1:=x->fo(x-ce); return f1; end proc; # Rafaella. # codificação # fo: funçao com coeficientes sendo o código da men sagem # ce: chave privada do emisor Rafaella_code:=proc(fo,ce) local f1; f1:=x->fo(x+ce); return f1; end proc;
