Um pouco de história

Falar besteira não paga imposto. O matemático escritor G. H. Hardy, declarou em 1940: a melhor matemática é em sua maior parte inútil, mas isto não é necessariamente ruim. A verdadeira matemática não tem efeito sobre a guerra. Ninguém até agora descobriu qualquer utilidade bélica para a teoria dos números. Logo, se viu como Hardy estava errado.

Em 1944, Von Neumann escreveu um livro chamado "Teoria dos jogos e comportamento econômico", onde inventou o termo "teoria dos jogos". Esta foi uma das bases da estratégia na guerra fria. Um exemplo simples é dado pelo truelo:

Um truelo é como um duelo, mas envolve 3 pessoas. Aldo, Bento e Carlos decidem resolver suas diferenças num truelo, atirando até que apenas um sobreviva. Aldo é o pior atirador, acertando em média 1 tiro a cada 3. Bento é melhor e acerta 2 tiros a cada 3. Carlos é o bamba, não erra tiro. Para deixar o truelo mais justo, Aldo pode atirar primeiro. Depois, Bento (se ainda vivo) pode atirar e a seguir o Carlos se ainda viver. O processo se repete até que só sobre um. A pergunta é: contra quem deve o Aldo atirar para ter mais chance de sobreviver? Pense e ache uma resposta. Pode comparar com a dada pela Teoria dos Jogos no final deste texto.

Na época da II Grande Guerra, a matemática da quebra de códigos foi ainda mais importante. Os aliados perceberam que a lógica matemática poderia ser usada para decifrar as mensagens alemãs, apenas se os cálculos pudessem ser feitos rapidamente. O desafio foi automatizar a matemática, de modo que uma máquina pudesse fazer o serviço. Quem foi chamado e deu conta brilhantemente foi um inglês, Alan Turing. Convocado em 4 de setembro de 1940, Turing deixou Cambridge para ir para a Escola de Cifras e Códigos do Governo Inglês. Os alemães tinham desenvolvido um sistema superior de codificação, e os lingüistas e filólogos tiveram que dar licença para os matemáticos. Como se diz na gíria, a coisa passou a ser briga de cachorro grande. A invenção alemã era a ENIGMA, uma máquina codificadora. Tinha um teclado e 3 rotores contendo o alfabeto. A posição dos rotores determinava como cada letra ia ser codificada. A complexidade estava em que:

a) Os três rotores eram escolhidos de um grupo de 5;
b) Cada rotor podia ser posicionado de 26 maneiras diferentes;
c) Uma regulagem em um painel permitia 150.000.000.000 de regulagens diferentes.

Para manter os ajustes, a máquina era regulada de maneira diferente a cada dia. Turing, liderando um grupo de matemáticos, construiu máquinas para quebrar o código, chamadas bombas. Eram computadores a relés e o nome veio do barulho que faziam. O problema era o tempo. Não adiantava nada descobrir que um navio britânico ia ser bombardeado, 3 semanas depois que ele havia ido ao fundo. Um grande progresso surgiu quando descobriu-se que a despeito da regulagem que fosse, ENIGMA nunca traduziria uma letra nela mesma. Esse fato simples reduziu o espaço de busca e, conseqüentemente, o tempo necessário. Os alemães retrucaram limitando a 250 caracteres o comprimento das mensagens. Para quebrar o código, Turing tentava adivinhar palavras existentes nas mensagens, num autêntico duelo entre cifrador e decifrador. Quando conseguiam, a regulagem da máquina estava conhecida para aquele dia e todas as mensagens podiam ser decifradas. Turing chegou a ordenar que a RAF bombardeasse uma cidade qualquer, a fim de capturar as mensagens alemãs, dando conta disso e descobrir (pelo nome da cidade que estaria na mensagem) a regulagem da ENIGMA. Em 1º de fevereiro de 1942, os alemães acrescentaram uma quarta roda, mas aí já era tarde. Os ingleses podiam quebrar o código facilmente aumentando a eficiência das bombas. Os alemães tinham tanta certeza da excelência de seu código que nunca cogitaram ter ele sido quebrado. Julgavam que os ingleses tinham espiões infiltrados. Conta-se que vários secretários e assistentes alemães foram fuzilados como supostos espiões ingleses, sem o serem. Devido ao sigilo que cercou esta iniciativa, Turing não chegou a ser reconhecido.

Preliminares

Nas redes distribuídas que interligam computadores (Internet, por exemplo), grande parte dos processos envolve 2 máquinas diferentes. Uma delas (a cliente) solicita, através de um determinado protocolo, um certo serviço a outra máquina (a servidora). Se o serviço é prestado, tem-se o que se chama de transação.

Para que estes serviços possam se dar com confiabilidade e segurança, certas necessidades têm que ser supridas:

a) Identidade dos participantes, após o que cada um terá acesso ou não a certos recursos computacionais;

b) confidencialidade, garantindo que terceiros não tenham acesso aos dados em tráfego;

c) integridade, permitindo detectar quando hou-ve alguma alteração nos dados trocados;

d) unicidade de transação, que impeça a repli-cação indevida;

e) autoria de transação impedindo a qualquer momento o repúdio.

Criptografia

O uso de algoritmos criptográficos atende adequadamente as necessidades acima, e tem sido a solução empregada para a implantação de serviços sensíveis em redes públicas (por exemplo, o e-commerce).

Todos os algoritmos de criptografia residem no conhecimento de uma chave secreta que é utilizada pelos algoritmos para criptografar dados. Em resumo:

Como os algoritmos são conhecidos (e devem sê-lo, pois precisam ser exaustivamente testados e validados), o que garante os serviços é a chave secreta. Deve ter um tamanho suficientemente grande que impeça sua descoberta por busca exaustiva, mas suficientemente pequena para viabilizar o processamento com o mínimo de overhead.

Os algoritmos se dividem em simétricos e assimétricos. Cada um tem suas vantagens e desvantagens e, usualmente, usam-se ambos, buscando aproveitar o que de melhor cada um tem.

Simétrico

A mesma chave é usada tanto para criptografar como para decriptografar mensagens. Precisa, portanto, ser conhecida por ambos os parceiros da transação. Este é o grande problema, pois antes de começar a ser usado, o método exige a entrega da chave a ambos.

Como ambos conhecem a chave, este método permite o repúdio (foi ele, não fui eu...). Se cada par de parceiros tiver que ter a sua chave, o problema de distribuição cresce exponencialmente.

A vantagem é que estes algoritmos são muito rápidos (existem implementados em hardware).

Assimétrico

Utilizam-se 2 chaves diferentes, que pertencem apenas a 1 participante. Elas estão matematicamente relacionadas, mas é computacionalmente impossível obter uma a partir apenas da outra. A primeira é chamada PÚBLICA (CP) e pode ser divulgada à vontade. A segunda é a SECRETA (CS) e deve ser guardada em sigilo.

Trata-se de uma aplicação de números primos. Bolam-se 2 números primos bem grandes (cerca de 100 dígitos cada um) e a seguir eles são multiplicados entre si formando um numerão maior (não primo). Para codificar a mensagem usa-se o numerão não primo, e para decodificá-la são necessários os dois primos que foram multiplicados. Publico o numerão e guardo os numerinhos (de 80 dígitos cada um). Uma dificuldade enorme aguarda quem for tentar fatorar o numerão para achar os dois números originais. O único problema deste algoritmo é o custo computacional de lidar com esses numerões, mas os computadores estão aí para isso.

Eis o funcionamento:

Assinatura Digital

Se, ao criptar uma mensagem, eu usar a minha CS em vez da CP, qualquer pessoa que conheça a minha CP poderá decriptografar a mensagem e ter a certeza de que fui eu que a mandei. Este fato é conhecido como assinatura digital. Ninguém mais (que não conheça a minha CS) poderia mandar uma mensagem em meu nome, pois aplicando a ela a minha CP o resultado seria incoerente.

Os algoritmos assimétricos são muito "caros" computacionalmente e, portanto, quando se quer apenas garantir integridade (não criptografia) utiliza-se encriptar apenas um identificador unívoco do arquivo. Costuma-se usar uma função do tipo hash, que quando aplicada a um conjunto de dados (arquivo) gera um único número (usualmente 100, 200, ou 512). A isto se acresce data/hora/número de seqüência, outros identificadores e este conjunto é encriptado com a chave secreta do remetente. Pronto, um documento está assinado digitalmente.

No destino, qualquer um pode decodificar a assinatura. A associação com a mensagem é garantida recalculando-se o hash do arquivo e comparando o resultado com o resultado do hash que veio na mensagem. Se iguais, garante-se a mensagem original assim como a sua integridade (não adulteração).

Desafio-Resposta

Uma modalidade de dupla certificação é a chamada desafio-resposta. Uma vez estabelecida a conexão, e desejando certificar ambos os participantes, um deles gera uma mensagem aleatória e a envia para o segundo (o desafio). O segundo assina digitalmente a mensagem e a devolve. Na chegada, o primeiro decriptografa a assinatura e compara com o arquivo aleatório original. Havendo coincidência o segundo participante está garantido. Agora o processo se repete para a garantia do primeiro.

Esquema híbrido

Na prática, todos os esquemas atualmente em uso utilizam ambos os enfoques: o processo de dupla identificação é garantido pelo algoritmo assimétrico e, em seguida, uma chave aleatória limitada no tempo e no espaço (para este parceiro e apenas durante esta conexão) é gerada. Esta chave passa a ser a utilizada em um esquema simétrico que é rápido e barato.

Certificação de chave pública

O segredo deste método reside na garantia de que uma chave pública realmente pertença a quem assim o diz. Essa garantia é dada por um certificado que associa a identidade de um participante a uma dada chave pública. A autenticidade do certificado é garantida pela assinatura digital de uma entidade confiável, a AUTORIDADE CERTIFICADORA. Esta assinatura garante o certificado contra adulteração e é uma afirmação confiável de que aquela senha pública é de fato de quem diz ser, tendo sido isto verificado.

O certificado pode ser enviado junto com a mensagem ou estar disponível em um serviço de diretórios, permitindo a autenticação de um participante sem necessidade de manter cadastro do mesmo ou sequer de ter tido um contato prévio com ele. Graças a isto, a certificação é vital para o desenvolvimento do comércio e de transações eletrônicas.

A aceitação de um certificado envolve a conferência da assinatura digital do mesmo, usando-se a chave pública da CA que, por sua vez, pode estar certificada por outra CA, criando-se uma hierarquia de certificação.

Serviço de certificação

Um serviço eletrônico como outro qualquer. Utiliza-se de um conjunto de práticas e procedimentos públicos para emitir, revogar e renovar certificados digitais. Costuma-se adotar políticas diferenciadas em função dos valores envolvidos. Eis um exemplo real de certificação:

Neste caso, um parceiro comercial, ao vender um bem de $300 poderia não aceitar um certificado de classe 1, pois esse valor supera a responsabilidade assumida pela CA para esta classe.

Revogação de certificados

Um certificado pode ser revogado (e ir para uma lista negra de certificados revogados) quando:

a) a chave privada do portador foi comprometida;
b) a CA descobre que o certificado foi emitido pa-ra pessoa ou entidade errada;
c) o sistema de segurança da CA foi compro-metido, permitindo a geração de certificados fraudulentos;
d) o certificado associava uma pessoa física a uma jurídica e esse laço foi desfeito;
e) o nome do detentor do certificado não é mais válido.

Certificação de código ActiveX

A tecnologia Internet também possibilita a execução de código alienígeno. Visitando páginas web compostas com código Java ou ActiveX, pedaços de programa desconhecidos rodam em seu computador. Por ser fonte potencial de vírus e cavalos de Tróia, estes códigos têm a possibilidade de serem assinados digitalmente, com garantia de integridade e autoria. Cabe ao usuário permitir a execução ou não de código não assinado ou certificado por alguém que não goza de confiança. A Microsoft chama isso de "Authenticode" e a Netscape de "Object Signing". Acima um certificado exibido quando um objeto assinado é trazido pela Internet, e abaixo o esquema de validação de objetos dos browsers.

SET

Secure Electronic Transaction. É um protocolo que estabelece pagamento seguro de transações eletrônicas em redes abertas com cartão de crédito. Sua especificação foi feita por Visa, Mastercard, GTE, IBM, Microsoft, Netscape, RSA, SAIC, Terisa e Verisign.

Este protocolo ainda é pouco usado e garante confidencialidade, autenticação e integridade.

A seguir, um esquema de funcionamento da comunicação no SET:

Segue-se uma descrição de cada um dos passos

DES

Data Encription Standard. É o primeiro padrão a ser largamente usado. É simétrico. Durante muitos anos foi sinônimo de "criptografia". Ainda terá uma sobrevida grande, devido à sua larga utilização, principalmente na sua versão extendida, chamada TRIPLO-DES.

Ele trabalha sobre grupos de 64 bits, formando números que são operados de acordo com o algoritmo. A chave usada também tem 64 bits, embora só sejam realmente usados 56 destes. Por exemplo, o texto plano X'8787878787878787' cifrado com a chave X'0E329232EA6DD0D73' dará o texto cifrado X'0000000000000000'. Quando decifrado usando a mesma chave, trará como texto plano X'8787878787878787'.

Seqüência de etapas:

01. Cada bloco de 64 bits é dividido em dois blocos de 32 (L e R);
02. A cada 8 bits da chave um é desprezado (8, 16, 24, 32, 40, 48, 56 e 64);
03. A chave é permutada (todos os seus 56 bits trocam de lugar);
04. A chave é quebrada em duas (C0 e D0), cada uma com 28 bits;
05. Com C0 e D0 formadas, criam-se Cn e Dn, onde "n" varia entre 1 e 16, fazendo às vezes 1, às vezes 2 deslocamentos de bit à esquerda;
06. Agora cada par Cn Dn devidamente con-catenado sofre uma permuta para gerar Kn;
07. O bloco a criptografar também sofre uma permuta;
08. Aplica-se uma função "f", 16 vezes. "f" opera sobre blocos de dados de 32 bits e uma chave Kn de 48 bits e produz um bloco de 32 bits;
09. A função "f" inicialmente expande o bloco de 32 na entrada para 48, repetindo alguns bits. A seguir, este bloco é dividido em 8 blocos de 6 bits, que são a seguir permutados. Depois faz um XOR entre os dois blocos de 48. Agora, cada grupo de 6 bits é usado como endereço para localizar uma caixa-S que tem dentro 4 bits;
10. Permuta-se o resultado de novo e tem-se o código criptografado.
(Maiores detalhes deste algoritmo, cuja descrição ocupa 14 páginas A4, estão na referência).

Quebra do DES

Em 1998, sob a direção de John Guilmore e usando uma máquina de U$220.000 anunciou-se poder quebrar uma chave de 56 bits em 4.5 dias, através do método da força bruta. Em 17 de julho de 1998, quebrou-se uma chave em 56 horas. Este computador pode testar 90.000.000.000 de chaves por segundo. Entretanto, o sucesso exige uma chave estável e uma mensagem conhecida (ou estimada com boa confiança) devidamente criptografada.

DES triplo

É um DES usado com duas chaves de 56 bits. A partir do texto plano, a primeira chave é usada para encriptar. A segunda chave é usada para decriptar este resultado. Este resultado novamente é cifrado usando a primeira chave. Pode ser usado também com 3 chaves distintas. De qualquer modo, o tamanho do espaço de busca aproxima-se de 2112.

RSA

Este algoritmo é o mais famoso de chave assimétrica. É devido a Rivest, Shamir e Adleman professores do MIT (Massachussets Institute of Technology), publicado em 1977. Siga o roteiro a seguir. Por comodidade, em vez de caracteres usam-se números, mas basta lembrar que qualquer conjunto de bits pode ser encarado como um número.

Outro exemplo:

Resumo da ópera

Para escolher a chave pública faz-se:

n = produto de dois primos quaisquer p e q

c = qualquer número c que seja primo relativo a f = (p-1)x(q-1).
A chave pública é (c,n)

Para escolher a chave secreta:

n = idem acima
d = qualquer desde que (c x d) mod f {=(p-1)x(q-1)} seja igual a 1.
A chave secreta é (d,n)

Para encriptar m (m tem que ser menor do que n):

m^c mod n = y

Para decriptar:

m = yd mod n

Exemplo:

p = 79 e q = 89; n = 7031 f = 6864 c = 977
CP=(977,7031)
CS=(3569,7031)

mensagem x = 769, 500, 759, 453, 201
x⁹⁷⁷ mod 7031 = 3825, 6285, 4174, 744, 758

decriptação
y³⁵⁶⁹ mod 7031 = 769, 500, 759, 453, 201

Para usar este algoritmo há que se ter meios rápidos de fazer grandes exponenciações. Um dos algoritmos consagrados para exponenciação de grandes números é:

Algoritmo Addition Chaining

Calcula x ^y mod n

REFERÊNCIAS BIBLIOGRÁFICAS

1. GRABBE, Orlin. The des algorithm illustrated. Disponível na Internet. www.zolatimes.com/v.2.28/des.htm

2. BRISA. Certificação de chaves criptográficas e assinaturas digitais. /s.l./. 1999.

3. SINGH, Simon. O último teorema de Fermat. Rio de Janeiro: Record, 1997.