(1)
Introdução
A Criptografia consiste na ciência (e arte) da transformação de texto simples em texto ilegível, de tal modo que apenas quem saiba qual o processo de reverter a transformação possa recuperar o texto original.
Naturalmente que técnicas deste tipo já existem há muito tempo, nomeadamente, com utilização em mensagens militares e diplomáticas. Sabe-se que os antigos espartanos cifravam as suas mensagens militares, e uma das cifras mais antigas, que se conhece, é a cifra César, cujo nome advém da sua utilização por Júlio César.
Atualmente, com a utilização generalizada de computadores e de redes de comunicação de dados, a necessidade de utilizar criptografia estende-se a diversos domínios, desde a autenticação de utilizadores, à privacidade de comunicações pessoais, ou difundidas, em canais de comunicação pouco seguros, ou de acesso livre (por exemplo canais de comunicação via satélite).
Refira-se ainda a distinção entre a criptografia, que consiste numa transformação de seqüências de caracteres (ou de bits), e a codificação de unidades lingüísticas, que não é mais do que a atribuição a determinadas palavras, ou frases, de uma outra palavra. Neste último caso terá de haver, no emissor e no receptor uma tabela do código usado. A criptografia, sendo muito mais flexível, visto que permite codificar qualquer seqüência de caracteres independentemente do contexto, é muito mais utilizada e constitui, em exclusivo, o foco de atenção deste texto.
Este pequeno texto de apoio à disciplina de Teoria da Informação, tem como objetivo apresentar as principais técnicas utilizadas em criptografia e alguns dos sistemas usados atualmente. Desenvolve-se com algum cuidado a aplicação dos conceitos de Teoria de Informação à criptografia.
Terminologia
Em geral, considera-se a necessidade de transmitir uma mensagem (M), entre um emissor e um receptor. A mensagem designa-se por texto simples. Na realidade, esta designação não significará texto propriamente dito, corresponderá antes a qualquer seqüência de bits que se pretenda transmitir em segurança. O processo de disfarçar a mensagem chama-se cifragem e transforma o texto simples num criptograma (C). O processo de recuperar o texto simples original a partir do criptograma denomina-se decifragem.
Por seu turno, a criptoanálise é a ciência (e arte) de quebrar criptogramas, ou seja, descobrir como fazer a decifragem de um criptograma, sem saber, à partida, como ele foi cifrado. Há um ramo da matemática, a criptologia, que engloba a criptografia e a criptoanálise.
Os algoritmos de criptografia, também denominados cifras, são as funções matemáticas que fazem a cifragem e a decifragem, tendo, portanto, em geral, dois componentes, respectivamente, o algoritmo ou função de cifragem (E)
e o algoritmo ou função de decifragem (D)
(2)
devendo, naturalmente, verificar-se
(3)
Se a segurança de um algoritmo é baseada no seu secretismo, classifica-se como restrito. Atualmente são pouco utilizados porque, quanto maior é o número de utilizadores, maior é a probabilidade de algum deles revelar o segredo, quebrando a segurança de todo o sistema. A sua utilização restringe-se a aplicações de baixa segurança (codificadores de vídeo, por exemplo).
Todos os atuais algoritmos seguros são conhecidos e usam, no seu funcionamento, uma chave. Basicamente a chave é um número k
em que K é o espaço finito das chaves, que interessa ser de grande dimensão, para uma maior segurança.
Em algoritmos com chave, as três primeiras equações, podem reescrever-se na forma
(4, 5, 6)
As chaves devem definir univocamente o criptograma, ou seja
Com maior generalidade, considera-se a utilização de duas chaves diferentes, uma de cifragem e outra de decifragem vindo
(7, 8, 9)
Nos algoritmos simétricos, a chave de cifragem pode ser obtida a partir da chave de decifragem, e vice-versa, sendo as duas chaves, normalmente, idênticas. Em qualquer caso, é necessário, que o emissor e o receptor acordem numa chave, antes de poderem usar o sistema.
Nestes algoritmos, a segurança reside no secretismo da chave. Visto que o funcionamento do algoritmo é conhecido, sabendo a chave, é possível cifrar e decifrar qualquer mensagem.
De modo a obviar a este problema surgiram os algoritmos assimétricos ou de chave pública, em que as duas chaves são obrigatoriamente diferentes, com a condicionante de a chave de decifragem ser impossível de obter a partir da chave de cifragem (pelo menos num tempo aceitável).
Chamam-se de chave pública, porque a chave de cifragem pode ser divulgada, permitindo a qualquer emissor enviar mensagens cifradas para um destinatário que, só ele, conhece a chave de decifragem. O sistema inverso também é possível, isto é, publicar a chave de decifragem e manter secreta a chave de cifragem, e designa-se por sistema de assinatura. Permite garantir a autenticidade das mensagens do emissor.
Os algoritmos de cifragem podem também dividir-se em duas categorias conforme a maneira como subdividem as mensagens a cifrar. Os algoritmos de cifra corrida (stream cipher) fazem um tratamento bit a bit do texto original. Os algoritmos de blocos, tratam um determinado número de bits simultaneamente. Em implementações usando computador a dimensão do bloco é, normalmente, 64 bits - um valor suficientemente grande para afastar a criptoanálise e suficientemente pequeno para ser tratável.
Caracterização das funções de cifragem
Seja
No caso geral, se Z* for um conjunto de todas as palavras obtidas a partir de um conjunto de caracteres Z, temos
Zn Õ Z* designa o conjunto de todas as palavras de comprimento nZ(n) é o conjunto de todas as palavras de comprimento ¾ n incluindo e.
Define-se então uma cifragem como uma relação
X: V* -> W* com v a w
Para que o receptor seja capaz de reconstituir a mensagem sem ambigüidades uma cifragem é injetiva, i.e. não ambígua da direita para a esquerda: (x a z) Ÿ (y a z) Þ x=y
No entanto uma mesma letra do texto simples pode dar origem a várias outras que se denominam as suas homófonas. Se a relação X for bijetiva, é uma função e a cifragem é determinística, relacionando de 1 para 1 todos os elementos de V* com os de W*.
Seja então um sistema de cifragem definido do seguinte modo:
cada ci é denominado um passo de cifragem e q=|M| é a cardinalidade do sistema, ni é a largura (máxima) de cifragem do texto simples, e mi é a largura (máxima) cifrada do passo de cifragem (relação) ci.
Um passo de cifragem em que V=W denomina-se endomórfico.
Uma cifragem X=[ci1,ci2,ci3,…] gerada por M é monoalfabética se só tem um passo de cifragem (um alfabeto). De outro modo é polialfabética.
Uma cifragem é monográfica se todos os ni forem iguais a 1, e poligráfica nos outros casos.
No caso mais restrito em que 
- se m=1, 2, 3, … temos grupos de caracteres no criptograma, denominados, respectivamente, unipartidos, bipartidos, tripartidos,…
Freqüentemente neste caso (palavras de comprimento fixo) escolhe-se V=W e m=n, o que dá origem a um sistema de cifragem em blocos, no sentido estrito.
Criptoanálise
A criptoanálise é o que faz quem quer tentar descobrir o conteúdo de uma mensagem cifrada. Sendo uma atividade associada a alguém que pretende "atacar" uma cifra, é também o processo que permite avaliar a qualidade de uma cifra - se não for possível, ou for extremamente demorado, por criptoanálise, decifrar um criptograma, então o algoritmo de cifra é garantidamente seguro. Como tal, qualquer novo algoritmo de criptografia só é considerado seguro depois de resistir, com êxito, à criptoanálise de outros investigadores.
Os principais tipos de criptoanálise que existem são:
Como já foi referido, os algoritmos de cifragem considerados seguros são aqueles de que se conhece o funcionamento, sendo secreta apenas a chave. Na realidade, os algoritmos restritos são quebráveis, dependendo isso apenas do tempo e dinheiro disponíveis pelo criptoanalista (normalmente é necessário muito menos do que seria de esperar...):
Os ataques a um sistema de comunicações seguro, isto é, um sistema em que as mensagens são cifradas, podem ter um dos seguintes três objetivos:
Nem sempre é necessário que o sistema garanta, simultaneamente, defesas contra estes três tipos de ataques, de modo que as técnicas criptográficas a aplicar dependem do objetivo da proteção pretendida.
Medidas de Segurança
Um algoritmo é considerado seguro se não puder ser quebrado com os recursos computacionais existentes, actualmente ou no futuro. É de realçar que, dada a evolução da velocidade de processamento dos computadores, é necessário prever uma margem de complexidade do algoritmo, de modo a não poder ser quebrado em tempo útil nas próximas décadas.
A segurança do algoritmo de criptografia é, portanto, a dificuldade associada à inversão dos algoritmos de cifragem do sistema. Uma das maneiras de avaliar a segurança do algoritmo é através da incerteza associada ao espaço das chaves K, e que, sendo as chaves todas equiprováveis de serem usadas, é H(K) = log#K.
A definição de segurança perfeita foi apresentada por Shannon, e é a seguinte:
Sendo P(m|c) a probabilidade de uma mensagem m ter sido enviada dado ter sido recebido o criptograma c, com c=E(m), então o algoritmo com segurança perfeita tem:
P(m|c) = P(m) (10)
o que significa que M e C são independentes.
Por outro lado, se P(c|m) for a probabilidade de receber o criptograma c dado ter sido enviada m, então
(11)
sendo P(k) a probabilidade da chave k. Normalmente sucede que existe um e um só k que satisfaz Ek(m) = c.
Assim, uma condição necessária e suficiente para a segurança perfeita é:
P(c|m) = P(c) (12)
o que é apenas uma outra forma de apresentar a igualdade 10, e significa que a recepção de um criptograma c é independente da mensagem m, de que constitui a cifra.
Donde, para a segurança perfeita é necessário que o comprimento da cifra seja tão longo quanto o da mensagem enviada e a cardinalidade do espaço das chaves seja a mesma da do espaço de mensagens.
Daqui decorre que, num algoritmo ideal, deve existir uma distribuição uniforme de todas as propriedades estatísticas da cifra, incluindo as características redundantes da língua terem sido mascaradas.
Embora estas características sejam as de um algoritmo ideal, existe um algoritmo criptográfico perfeito implementável na prática, que é o one time pad (cuja tradução mais próxima é "bloco descartável"). Neste algoritmo, a mensagem é codificada por uma sequência não repetida de bits aleatórios, que é sempre diferente para cada mensagem a cifrar (com chaves idênticas podem correlacionar-se mensagens).
Equivocação
A equivocação de um algoritmo criptográfico é definida como a entropia condicional da mensagem M dado o criptograma C, ou seja:
(13)
e constitui uma medida de segurança da cifra. Quanto maior é a equivocação maior é a segurança do algoritmo.
Shannon propôs como alternativa uma medida de equivocação da chave:
(14)
Se H(K|C) é zero, significa que não há incerteza na chave, dado um criptograma e, como tal, a cifra é quebrável. Naturalmente que o maior valor da equivocação da chave se obtém quando a chave for independente do criptograma e terá, nesse caso, o valor da entropia da chave, H(K). Donde, em geral, quanto maior for a incerteza da chave, maior é a segurança do algoritmo.
Redundância de uma linguagem
As linguagens, como língua falada ou escrita, são, como se sabe, bastante redundantes e a sua redundância depende da língua particular em causa, podendo ser medida de maneira aproximada.
Para tal define-se razão da linguagem, para mensagens de comprimento n, como:
(15)
em que X representa o alfabeto da linguagem. Esta razão não é mais do que a incerteza média por caráter, ou seja (em log2), o nº médio de bits de informação em cada caráter. Em inglês estima-se que, para n grande, r se situa entre 1,0 bit/letra e 1,5 bit/letra (Shannon estimou esse valor em 1,2).
Define-se também a razão absoluta de uma linguagem (R), como o máximo de informação por caráter, possível de obter com o alfabeto usado. Naturalmente que tal sucede quando todas as letras são equiprováveis, vindo, para um alfabeto de N letras:
(16)
Na realidade, o que sucede é que, em qualquer linguagem, as letras nunca são equiprováveis, de modo que a incerteza por caráter é menor, resultando daí a redundância da linguagem. Define-se como a diferença entre a razão absoluta e a razão da linguagem:
D = R - r
Num alfabeto de 26 letras tem-se R = 4,7 bits/letra, de modo que, em inglês existe uma redundância D ‰ 4,7 - 1,2 = 3,5 bits/letra, ou, medindo a razão D/R, cerca de 74% de redundância.
Em português, com n = 1, obtém-se r = 3,92 bits/letra (segundo uma tabela de freqüências de caracteres, apresentada em Seberry, J., & Pieprzyk, J., 1989 - Apêndice A) e, considerando um alfabeto de 23 letras, R = 4,52 bits/letra, o que dá uma redundância D = 0,6 ou seja, D/R = 13,2%.
Note-se que a razão da linguagem agora utilizada, considera apenas a probabilidade de seqüências de 1 letra. Mas sabe-se bem que numa linguagem existem muitas seqüências de caracteres repetidas e isso significa que as letras não são independentes entre si. Portanto, para o cálculo da razão da linguagem real, deverá ser usada a fórmula:
(17)
em que Hn(X) corresponde à entropia de seqüências de n caracteres do alfabeto X. Note-se que r• corresponde, na realidade, ao ritmo de entropia da linguagem. O cálculo deste valor cresce exponencialmente com n, de modo que a razão real de uma linguagem é apenas estimada, a partir dos resultados obtidos para valores de n pequenos.
O valor apresentado acima para a razão do inglês é o rƒ estimado. Calculando essa mesma razão para n = 1 obtém-se r = 4,17 bits/letra, um valor bastante maior do que o anterior, o que diminui a redundância para cerca de 11%, comparável à encontrada acima para o português.
Distância de Unicidade
Shannon definiu distância de unicidade como o valor aproximado da quantidade de criptograma que faça com que a soma da entropia do texto simples associado e da entropia da chave seja igual ao número de bits do criptograma. Ou, de outro modo, a distância de unicidade é o comprimento mínimo de mensagem que torna H(K|C) ‰ 0. Shannon mostrou também que criptogramas maiores do que esta distância têm uma probabilidade elevada de ter uma única decifragem entendível, enquanto que criptogramas significativamente menores do que a distância de unicidade têm, provavelmente, várias decifragens igualmente válidas. Ou seja, a distância de unicidade corresponde à quantidade de criptograma necessário para determinar univocamente uma chave possível. À medida que aumenta o comprimento do criptograma diminui a distância de unicidade (e portanto a equivocação da cifra).
Distância de Unicidade só com criptograma disponível
Pelas propriedades da entropia, tem-se
H(M, K, C) = H(M|K, C) + H(K, C) = H(C|K, M) + H(K, M) (18)
Note-se ainda que
H(M|K, C) = H(C|K, M) = 0
ou seja, quando temos, a chave e o criptograma, sabemos qual a mensagem e portanto a incerteza é nula. Do mesmo modo, quando sabemos a chave e a mensagem, sabemos qual o criptograma.
Utilizando estas igualdades em (18) obtém-se
H(K, C) = H(K, M) (19)
mas tendo em conta que
H(K, C) = H(K|C) + H(C)
e que as chaves são escolhidas independentemente das mensagens, isto é, a probabilidade conjunta da mensagem e da chave é P(k, m) = P(k)P(m), vem
H(K, M) = H(K) + H(M)
e portanto a igualdade (19) toma a forma
H(K|C) + H(C) = H(K) + H(M)
Daqui decorre que
H(K|C) = H(K) + H(M) - H(C) (20)
e conseqüentemente, a distância de unicidade de uma cifra da qual só se conhece o criptograma é o valor N do comprimento do criptograma para o qual
H(K) + H(M) - H(C) = 0 (21)
se esse valor existir.
Por vezes podem usar-se aproximações úteis para a equação (20), considerando que o criptoanalista não tem qualquer informação acerca das chaves e das mensagens. Assim, considera-se que as chaves são escolhidas equiprovavelmente, donde vem H(K) = log n, sendo n o número total de chaves possíveis, ou #K. Pode considerar-se também que H(M) = log s, em que s representa o número de mensagens com sentido, que é significativamente menor do que a cardinalidade do espaço de mensagens, e uma estimativa bastante mais aproximada da incerteza que o criptoanalista tem acerca da mensagem. Finalmente, considerando que os criptogramas são todos equiprováveis (esta aproximação não é sempre legítima; depende da cifra em causa) vem H(C) = log r, em que r é o número de criptogramas possíveis. Com estas assunções a equação (20) toma a forma:
(22)
em que l = ns/r.
O valor da distância de unicidade é obtido quando H(K|C) = 0, neste caso quando l = 1, isto é, quando ns = r.
Distância de Unicidade com mensagem e criptograma disponíveis
Utilizando as propriedades da entropia em H(M, K, C) vem
H(K|M, C) + H(M, C) = H(C|M, K) + H(M, K) (23)
mas como H(M, C) = H(C|M) + H(M) e de igual modo H(M, K) = H(K|M) + H(M), a igualdade (23) fica
H(K|M, C) + H(C|M) = H(C|M, K) + H(K|M)
ora como se sabe que H(C|K, M) = 0 e que sendo as chaves selecionadas independentemente das mensagens H(K|M) = H(K) obtém-se
H(K|M, C) = H(K) - H(C|M)
e a distância de unicidade é o valor N (comprimento do criptograma) para o qual
H(K) - H(C|M) = 0 (24)
Por outro lado, tendo em atenção a definição de Shannon, a distância de unicidade é o valor N para o qual l = 1 (com l = ns/r). Quando se sabe a mensagem e o criptograma correspondente, o conjunto de mensagens com sentido contem um só elemento, donde s =1. Então, neste caso a distância de unicidade obtém-se quando
Aplicando logaritmos e substituindo log n por H(K), vem:
H(K) - log r = 0
o que, comparando com a equação (24) mostra que esta é uma aproximação, pois nem sempre se obtém H(C|M) ‰ log r, nomeadamente isso não acontece quando n/r está próximo de 1.
Comentários finais à Distância de Unicidade
Numa mensagem de comprimento N, o número de chaves redundantes diferentes que transformam um criptograma num texto simples inteligível é dado pela fórmula:
(25)
Assim, a distância de unicidade é definida, para a maioria dos algoritmos simétricos, como a razão entre a entropia da chave e a redundância da linguagem:
(26)
que torna a expressão (25) igual a zero (i.e. só há uma chave - não há redundantes).
Esta igualdade pode ser deduzida a partir da equação (21). A entropia da mensagem será H(M) = rN, em que r é a razão da linguagem e N é o número de letras da mensagem (e do criptograma). A entropia do criptograma é H(C) = RN, em que R é a razão absoluta da linguagem, para a dimensão em bits em que cada letra é representada (normalmente 8 bits). Donde a igualdade (21) vem:
H(K) + rN - RN = 0
e resolvendo em ordem a N obtém-se
N = H(K)/D
Note-se que a distância de unicidade é inversamente proporcional à redundância da linguagem e quando esta tende para zero, mesmo uma cifragem trivial pode tornar-se inquebrável.
Supondo que existem Z chaves possíveis, todas equiprováveis, a distância de unicidade é
N = log Z /D
Se limitarmos a análise a letras simples, obtemos uma razão da linguagem, para monogramas, de 4.17 bits, que é semelhante em Inglês, Francês e Alemão e outras línguas européias. Donde, neste caso a distância de unicidade é
N (1)= log Z /(4.7 - 4.17) = log Z / .53
para bigramas é
N (2)= log Z /(4.7 - 3.5) = log Z / 1.2
e para trigramas
N (3)= log Z /(4.7 - 3.2) = log Z / 1.5
No caso de considerarmos palavras da linguagem (em Inglês) obtém-se
N (w)= log Z /(4.7 - 2.6) = log Z / 2.1
e considerando a razão da linguagem (ou ritmo de entropia) do Inglês acima referido teremos
N (*)= log Z /(4.7 - 1.2) = log Z / 3.5
No caso de uma cifra de substituição monográfica, tem-se Z = 26! e
log Z=88.38bits
pelo que as distâncias de unicidade acima indicadas tomam os valores
N (1) ‰ 167 bits N (2) ‰ 74 bits
N (3) ‰ 59 bits
N (w) ‰ 42 bits
N (*) ‰ 25 bits ou seja, aproximadamente 3 letras
Porém, a distância de unicidade é uma medida estatística e, portanto, não fornece resultados determinísticos, mas sim probabilísticos. Dá apenas uma ideia da quantidade de criptograma necessária para que haja uma única solução razoável para a criptoanálise. Quando é pequena indica que o algoritmo é pouco seguro, porém não garante segurança mesmo com um valor elevado.
Acrescente-se ainda que a distância de unicidade é dificilmente calculável em grande parte dos algoritmos e como tal a idéia mais importante a reter é que em cifras inquebráveis ou ideais a distância de unicidade é infinita.
Complexidade
Face ao que foi exposto não é difícil concluir que a segurança de um algoritmo tem muito a ver com a sua complexidade, seja para a cifragem e decifragem, seja para a criptoanálise.
Refira-se apenas que as soluções para os problemas mais habituais da criptologia (fatorização, multiplicação, primalidade, logaritmos discretos, etc.) podem ser avaliadas e classificadas recorrendo à Teoria da Complexidade. Para tal há que ter em atenção que essas soluções devem ser implementadas, e portanto devem considerar-se os seguintes aspectos que têm a ver com os recursos necessários à implementação:
- O número de operações básicas a efetuar na execução do algoritmo
- O tempo de duração da execução do algoritmo
- A quantidade de memória necessária à execução do algoritmo
- A quantidade de equipamento necessária à execução do algoritmo
Assim, no que respeita à avaliação da segurança do algoritmo, qualquer avanço teórico importante dos algoritmos, da velocidade dos computadores que tratam o problema, da sua capacidade de armazenamento ou da arquitetura de sistemas multi-processador, é susceptível de tornar uma criptoanálise anteriormente inviável numa tarefa possível. Nesse sentido, há que ter em conta, ao avaliar a segurança de um algoritmo, as margens de progressão em qualquer dos quatro aspectos acima referidos, de modo a que não seja posta em causa a segurança do algoritmo.
Cifras Clássicas
As cifras utilizadas antes dos aparecimento dos computadores tinham como unidade de manipulação o caráter. E os algoritmos utilizavam essencialmente duas operações básicas: a substituição e a transposição.
Atualmente, sendo os algoritmos de criptografia implementados em computadores, a unidade de manipulação passou a ser o bit, mantendo-se todavia as duas operações básicas acima referidas.
Não abordaremos aqui o estudo aprofundado de cifras e algoritmos, pois o objetivo deste trabalho é dar uma visão geral nos vários sistemas de segurança existentes. Porém, pode-se achar muita informação no seguinte link:
http://ssdi.di.fct.unl.pt/~jmp/ti-M-99-00/Docs/criptografia/Criptografia.html
