Mil razões para conhecer o RSA (1)
14 de novembro de 2000, 0:00Já foram vendidas mais de um bilhão de licenças do RSA. Veja aqui porque.
Por
Num filme de espionagem, um homem de sobretudo e óculos escuros caminha apressadamente pelo saguão de um aeroporto levando uma pasta algemada ao pulso esquerdo.
Quando chega ao destino e abre a tal pasta, uma surpresa: nela não há nenhum documento secreto – que poderia cair em mãos inimigas – mas apenas um pedaço de papel com alguns caracteres datilografados, ou seja, uma chave criptográfica. A partir de agora os mocinhos poderão trocar informações com sigilo "absoluto" (se forem bandidos, o sigilo será apenas "relativo" :–).
Esse procedimento – denominado distribuição de chaves – é a grande pedra no sapato dos algoritmos simétricos (que utilizam uma mesma chave tanto para cifrar como para decifrar). Para embaralhar as coisas um pouco mais, essa operação precisa ser repetida de tempos em tempos para dificultar a eventual descoberta da chave por um oponente (ou para limitar os danos decorrentes da efetiva descoberta da chave).
Durante a Segunda Guerra Mundial, os alemães utilizaram a famosa máquina Enigma para enviar mensagens criptografadas. A marinha alemã distribuía aos comandantes de submarinos, antes de cada missão, um livro com as chaves a serem utilizadas a cada novo dia nas máquinas de bordo.
Para evitar que os Aliados utilizassem em seu proveito a informação ultra–secreta contida nos livros, eles eram escritos com tinta solúvel em água e possuíam capas de chumbo (em cartaz nos cinemas brasileiros, o filme U–571: A Batalha do Atlântico mostra norte–americanos capturando uma máquina Enigma de um submarino alemão; na verdade, o feito heróico parece ter sido obra dos ingleses, mas a produção do filme é norte–americana… :–).
Quando cresce o número de interlocutores, a distribuição de chaves fica muito mais complexa. Imagine, por um instante, que Itamar, Ciro, Malan e Lula – todos de olho nas eleições presidenciais de 2002 – decidam confabular dois a dois de forma sigilosa (até o Lula pensa em fazer uma aliançazinha!): seis chaves distintas serão necessárias, uma para cada par de presidenciáveis. Se, mantida a mesma premissa, Collor, Enéas, Brizola e Arraes se juntarem ao grupo (meu Deus, que país é este!?) – dobrando, portanto, o número de pré–candidatos – o número de chaves necessárias será multiplicado por quatro. Isto é o que se chama de crescimento quadrático.
Num cenário (matemático, não político… :–) desses, uma aplicação como comércio eletrônico não teria nenhuma chance: supondo que qualquer consumidor possa vir a comprar algo – ainda de forma sigilosa – de qualquer fornecedor, mil fornecedores e um milhão de consumidores precisariam de um bilhão de chaves distintas! Como gerar, distribuir e proteger tantas chaves?
Esse problema foi resolvido em 1976 por Diffie, Hellman e Merkle, que provaram a existência dos sistemas criptográficos de chave pública, assim chamados por utilizarem duas chaves, matematicamente relacionadas, de modo que as operações feitas com uma chave possam ser desfeitas com a outra. Além disso – e aqui está o pulo do gato – uma delas pode ser revelada (a chave "pública") sem que a outra (a chave "privada") seja comprometida. Essas propriedades permitem ainda definir o conceito de "assinatura digital", inexistente no mundo dos algoritmos simétricos, já que estes sempre utilizam um segredo compartilhado, cuja posse não identifica uma única entidade (e sim duas).
No ano seguinte, Rivest, Shamir e Adleman, professores do legendário Massachusetts Institute of Technology (MIT), após tomarem conhecimento do trabalho da outra trinca, propuseram um sistema baseado na dificuldade da fatoração de grandes números (é muito mais fácil multiplicar dois números de cem dígitos do que fazer a operação inversa, isto é, obter os fatores primos de um número de duzentos dígitos).
Esse sistema, simples e elegante, foi batizado com as iniciais de seus três inventores: RSA. Uma descrição acessível do algoritmo pode ser consultada no livro que uma garota–prodígio irlandesa de 18 anos, Sarah Flannery, escreveu com o pai, In Code: A Mathematical Journey. Um bom texto em português é o livro de Severino Coutinho, Números Inteiros e Criptografia RSA.
Em agosto de 1977, Martin Gardner desafiou os leitores de sua coluna na revista Scientific American a decifrar um criptograma proposto pelos criadores do RSA. O vencedor levaria um prêmio de cem dólares. Como a solução envolvia a fatoração de um número de 129 dígitos, esse desafio ficou conhecido como RSA–129. Embora Rivest afirmasse na época que seriam necessários quarenta quatrilhões de anos (!) para resolver o problema, isso acabou sendo feito em 1994 (mais detalhes nesta outra coluna.
Uma vez que foram utilizados recursos do governo norte–americano no desenvolvimento do sistema RSA, o MIT viu–se obrigado legalmente a requerer sua patente, o que foi feito em dezembro de 1977. Em 20 de setembro de 1983, a patente 4.405.829 (coincidentemente um número primo!) foi finalmente concedida ao MIT. Como o algoritmo havia sido publicado em abril de 1977, oito meses antes do pedido da patente, criou–se uma situação curiosa: o RSA pode ser patenteado de acordo com a lei norte–americana – que concede um ano de carência ao inventor – mas não na Europa ou no Japão, menos liberais nesse quesito. Isso não fez a menor diferença perante a legislação brasileira, que não reconhece algoritmos matemáticos como entidades patenteáveis (grosso modo, segundo o direito norte–americano, algoritmos são "inventados" e, portanto, patenteáveis; de acordo com a lei brasileira, algoritmos são "descobertos", não sendo, assim, patenteáveis). Em resumo, o RSA acabou sendo patenteado apenas nos EUA pelo período de 17 anos, isto é, até 20 de setembro de 2000.
Esse pequeno detalhe não impediu, entretanto, que mais de um bilhão (!) de licenças do software BSAFE – que incorpora implementações do RSA e de outros algoritmos criptográficos – fossem comercializadas pela empresa RSA Security Inc. até o momento. Prosseguimos na próxima coluna. [web insider]
