Universidade Federal de Pernambuco Centr o de Infor mática Ciências da Computação Criptografia “Utilizando classes das bibliotecas Java na
aplicação de conceitos de segurança” Equipe: Jorge Ferraz (jfof) Marcus Vinicius (mvgs)
Assinaturas digitais Na primeira parte desse projeto, vamos mostrar uma maneira simples de utilizarmos a biblioteca matemática de Java (java.math) na implementação dos algoritmos que foram vistos em sala de aula. 1) A classe BigInteger A classe BigInteger pertence ao pacote java.math. Representa números inteiros grandes. A vantagem da utilização dessa classe na implementação de funções da criptografia é que a) Ela representa os valores na notação de complemento a dois; b) Possui todos os operadores matemáticos básicos sobre inteiros; c) Possui funções complexas já implementadas, tais como aritmética modular, algoritmo de Máximo Divisor Comum e geração de números primos Por essa razão, essa classe foi usada na implementação dos algoritmos utilizados nesse projeto. 2) A classe RSA O RSA, de acordo com a Wikipedia, é “um algoritmo de encriptação de dados, que deve o seu nome a três professores do Instituto MIT (fundadores da actual empresa RSA Data Security, Inc.), Ron Rivest, Adi Shamir e Len Adleman, que inventaram este algoritmo — até à data (2005), a mais bem sucedida implementação de sistemas de chaves assimétricas, e fundamenta­se em Teorias Clássicas dos Números. É considerado dos mais seguros, já que mandou por terra todas as tentativas de quebrá­lo. Foi também o primeiro algoritmo a possibilitar encriptação e assinatura digital, e uma das grandes inovações em criptografia de chave pública.” O seu funcionamento é simples. Baseado na idéia da criptografia assimétrica, consiste na geração de duas chaves, uma pública e uma privada, utilizadas uma para a encriptação e outra para a decriptação. O RSA precisa gerar cinco números: a) b) c) d) e) Um número p, primo; Um número q, igualmente primo; Um número N (módulo), tal que N = p * q; Um número e (expoente); e Um número d (expoente), tais que e * d mod[(p­1)(q­1)] = 1
Esses números são, então, utilizados nos esquemas de segurança baseados em RSA. No escopo específico desse trabalho, serão utilizados para a aplicação de algoritmos de assinatura digital. No geral, a chave pública do algoritmo RSA é o par (N, e) e a chave privada, a tupla (N, p, q, d). Nos algoritmos de encriptação assimétrica, o emitente da mensagem a encripta com a chave pública e somente o destinatário, com a chave privada, é capaz de recuperá­la. Nos algoritmos de assinaturas digitais, ao contrário, o emitente da mensagem é que a assina com a chave privada e, a partir de então, qualquer um pode, de posse da chave pública, verificar a assinatura. A utilização da classe BigInteger, citada acima, torna a implementação do RSA simples e elegante. O construtor da classe gera os números (N, p, q, d, e). RSA.java Segue a implementação do algoritmo RSA. O construtor, responsável pela geração dos números, é como se segue: public RSA(int bitlen) { SecureRandom r = new SecureRandom(); p = new BigInteger(bitlen / 2, 100, r); q = new BigInteger(bitlen / 2, 100, r); n = p.multiply(q); BigInteger m = (p.subtract(BigInteger.ONE)) .multiply(q.subtract(BigInteger.ONE)); e = new BigInteger("3"); while(m.gcd(e).intValue() > 1) e = e.add(new BigInteger("2")); d = e.modInverse(m); } Ele recebe o tamanho (em bits) do módulo N que o usuário deseja. Para tanto, ele gera dois números primos, cada um de cumprimento N / 2. Note que a própria classe BigInteger se encarrega de fazer essa geração. É importante frisar que tal geração é probabilística, contudo apresenta uma probabilidade muito boa: no caso citado, os números p e q têm uma probabilidade de ser primos de pelo menos 1 – 1 / 2 100 , o que é bastante alto. Note também que as funções de Máximo Divisor Comum são utilizadas para gerar os expoentes e e d. Com essas funções já implementadas, a implementação da classe torna­se muito simples.
Dados esses números, é preciso apenas aplicar a definição do algoritmo, isto é, as funções de encriptação e decriptação. Novamente, a classe BigInteger faz com que tais operações sejam feitas de maneira bastante simples: public BigInteger encrypt(BigInteger message) { return message.modPow(e, n); } public BigInteger decrypt(BigInteger message) { return message.modPow(d, n); } Com essas funções simples, é possível combiná­las em blocos para cifrar mensagens maiores do que o limite de um BigInteger. Isso foi o que foi feito na implementação desse projeto (ver anexo). 3) O paradigma TrapDoor A maneira mais imediata de se utilizar RSA para na implementação de algoritmos de assinatura digital é através da utilização direta do algoritmo para encriptar e decriptar. Essa implementação é conhecida como trapdoor, e consiste simplesmente no seguinte: Utilizando­se da classe RSA exposta acima, foram feitos o Signer e o Verifier que utilizar o Trapdoor para produção e verificação de assinaturas digitais. Eles são como se segue: public Signer (BigInteger pD, BigInteger pN) { this.d = pD; this.n = pN; } public BigInteger sign (BigInteger pMensagem) { return pMensagem.modPow(d, n); }
public Verifier(BigInteger pE, BigInteger pN) { this.e = pE; this.n = pN; } public BigInteger verify(BigInteger message) { return message.modPow(e, n); } Com essa implementação simples, conseguimos fazer um esquema de assinatura digital. O mesmo foi verificado e mostrou­se plenamente funcional; as assinaturas foram produzidas e as mensagens foram verificadas com suas respectivas assinaturas, sendo aceitas; o mesmo não acontecendo com assinaturas diferentes das que foram geradas pelo algoritmo de assinatura. 4) Os problemas do TrapDoor Sabe­se que o TrapDoor não apresenta segurança; de fato, devido às próprias características do RSA, é extremamente simples conseguir um par mensagem / assinatura que seja aceito pelo verificador de assinaturas sem ter sido gerado pelo algoritmo de assinatura. Com o intuito de demonstrar essa fraqueza, nós implementamos dois Forgers, que geram, de duas maneiras diferentes, pares que sejam reconhecidos pelo algoritmo verificador como autênticos pares. O primeiro deles é o que simplesmente retorna o par (1, 1). Olhando as características do RSA e as operações que são realizadas, fica óbvio que tal par vai ser reconhecido como verdadeiro: o número 1, elevado a qualquer expoente que seja, vai dar como resultado 1 e, portanto, vai ser aceito pelo verificador. O segundo deles é o que aplica a operação inversa. Ele gera uma assinatura qualquer e, a partir dela, aplica as operações de exponenciação modulares para gerar a mensagem. Também ele, pela definição do RSA, vai gerar um par que vai ser reconhecido como válido pelo verificador. Ambos são como se segue: public class Forger1 { public static void main (String[] args) {
(…) //A mensagem forjada byte[] mensagem = {1}; int tamanho = 1; //A Tag de assinatura BigInteger[] tag = signer.sign(mensagem); //Verificando... boolean autentica = verifier.verify(new String(mensagem), tag, tamanho); if (autentica) System.out.println("A mensagem é autentica!"); else System.out.println("A mensagem não é autentica!"); } } public class Forger2 { public static void main (String[] args) { (...) //A tag forjada Random random = new Random(); int nBytes = random.nextInt(10) +1; //Uma tag de 1 a 10 bytes byte[] tag = new byte[nBytes]; for (int i = 0; i < nBytes; i++) { //Gera a tag aleatoriamente tag[i] = (byte) random.nextInt(255); } BigInteger tagForjada = new BigInteger(tag); BigInteger mensagemForjada = tagForjada.modPow(rsa.getE(), rsa.getN()); byte[] mensagem = mensagemForjada.toByteArray(); int tamanho = mensagem.length; //Verificando... boolean autentica = verifier.verify(
new String(mensagem), new BigInteger[] {tagForjada}, tamanho); if (autentica) System.out.println("A mensagem é autentica!"); else System.out.println("A mensagem não é autentica!"); } } Ambos esses adversários conseguem, de maneira bastante simples, produzir um par mensagem / assinatura que seja reconhecido pelo algoritmo de verificação sem ter sido produzido pelo algoritmo de assinatura. 5) A Solução: Paradigma Hash – Then – Invert Uma solução simples para esse problema é a utilização de uma função Hash. Se encriptarmos, ao invés da mensagem, o hash daquela mensagem, estaremos acrescentando uma dificuldade a mais aos adversários que porventura desejarem encontrar brechas no esquema de segurança. Isso acontece porque, com a utilização de uma função Hash, estaremos obrigando o adversário a quebrar a função Hash ou o RSA, o que é bem mais difícil. Aplicando o RSA não à mensagem pura, mas ao seu hash, no algoritmo de assinatura (e fazendo, evidentemente, o seu correspondente no algoritmo de verificação), nós inutilizamos os dois ataques que foram apresentados logo acima. A idéia por detrás do Hash­Then­Invert é a seguinte: Isso foi implementado no nosso projeto. Como função Hash, utilizamos a SHA1. As novas classes Signer e Verifier ficam como se segue: public Signer (BigInteger pD, BigInteger pN) { this.d = pD; this.n = pN; this.sha1 = new SHA1(); } public BigInteger[] sign(String pMsg) { //Hasheia a mensagem String msg = sha1.doHash(pMsg);
//Transforma a mensagem hasheada num array de bytes byte[] mensagem = msg.getBytes(); //Assina a mensagem BigInteger[] tag = this.sign(mensagem); return tag; } public Verifier(BigInteger pE, BigInteger pN) { this.e = pE; this.n = pN; this.sha1 = new SHA1(); } public boolean verify(String pMsg, BigInteger[] pTag, int pTamanho) { byte[] b = this.verify(pTag, pTamanho); String mensagem = new String(b); //Hasheia a mensagem String msg = this.sha1.doHash(pMsg); return mensagem.equals(msg); } Com esse novo paradigma, nós evitamos os problemas do TrapDoor. Os mesmos Forgers anteriormente utilizados foram aplicados novamente, e eles não conseguiram quebrar esse paradigma de assinaturas digitais. Portanto, nós concluímos que a utilização de uma função Hash é uma estratégia que melhora bastante a segurança de um esquema de assinaturas digitais baseado em RSA. 6) Adicionando propriedades de segurança a uma aplicação usando o pacote java.security A linguagem java oferece uma maneira prática de incluir ferramentas de segurança no seu sistema, o pacote java.security. Nesta seção explicitaremos através de um exemplo de aplicação de assinatura digital, como oferecer propriedades de segurança em uma aplicação java usando o pacote supracitado. No pacote java.security existem classes que definem como usar os algoritmos de segurança em uma aplicação java, porém não oferecem a implementação desses algoritmos. A implementação dos algoritmos pode ser oferecida por qualquer um, através dos chamados Providers. Um Provider é um pacote implementado por terceiros – você
pode construir o seu se quiser ­ que oferece a implementação dos algoritmos de criptografia, seguindo a definição das interfaces e classes do pacote java. security. O pacote oferece uma forma de abstração da implementação dos algoritmos, você pode embutir propriedades de segurança no seu sistema a partir de java.security, e mudar para o Provider que achar mais conveniente, quando achar mais conveniente, sem alterar uma linha de código da sua aplicação. Provider IBM Aplicação java Pacote java.security Provider SUN Provider Bouncy Castle
O primeiro passo a se seguir é dizer ao pacote java.security, que quer usar um determinado Provider na sua aplicação, isso é feito com a seguinte linha de código: Security.addProvider(new rg.bouncycastle.jce.provider.BouncyCastleProvider()); Essa linha inclui o Provider Bouncy Castle no seu sistema, e torna seus algoritmos prontos para o uso. Feito isso, você já pode usar qualquer um dos vários algoritmos oferecidos pelo Bouncy Castle, entre eles: DES, AES, RSA, PKCS, SHA1, MD5 etc. Exemplificaremos o uso do pacote mostrando como se pode incluir um recurso de assinatura digital, do paradigma supracitado Hash­then­Invert ­ usando os algoritmos MD5 e RSA ­, num sistema java de maneira simples. Como segundo passo para utilização da assinatura digital, instanciamos as chaves pública e privada que vamos usar para verificar e gerar as assinaturas. As seguintes linhas de código fazem o trabalho: //KeyPairGenerator é uma classe do pacote java.security que define um gerador de chaves qualquer KeyPairGenerator kpg; //KeyPair é uma classe do pacote que define um par de chaves, uma pública e outra privada KeyPair kp; //O gerador de chaves declarado acima é instanciado para a implementação do gerador de chaves para o algoritmo RSA (primeiro parâmetro) oferecida pelo Provider BC (Bouncy Castle). O primeiro parâmetro poderia se referir a qualquer algoritmo oferecido pelo BC que gere um par de chaves. O segundo poderia se referir a qualquer provider incluído previamente no seu sistema kpg = KeyPairGenerator.getInstance("RSA", "BC"); //Inicializa o gerador de chaves para gerar chaves de 512 bits kpg.initialize(512); //Gera um par de chaves e o atribui ao atributo KeyPair declarado anteriormente kp = kpg.genKeyPair(); Definimos a seguir, um método que gera as assinaturas para qualquer cadeia de caracteres passada como parâmetro: public byte[] Assinatura(String mensagem){ //Declara uma nova assinatura digital, setando­a para a implementação do hash­then­invert MD5 com RSA disponível no Bouncy Castle Signature sig = Signature.getInstance("MD5withRSA", "BC"); //Inicia o processo de assinatura usando a chave privada gerada no bloco de código anterior sig.initSign(kp.getPrivate()); //Inclui a mensagem passada com parâmetro para ser assinada sig.update(mensagem); //Gera uma assinatura para a mensagem usado a chave privada return sig.sign(); } Pronto! Com essas poucas linhas de código temos a capacidade de gerar assinaturas digitais MD5 com RSA no nosso sistema. Note que para modificarmos o algoritmo de assinatura ou o Provider é necessário apenas mudar os parâmetros dos métodos getInstance para o algoritmo e Provider que desejarmos, sem mudar mais nada no código. Para verificar assinaturas, podemos usar o método definido a seguir: public boolean Verificar(String mensagem, String assinatura) { //Declara uma nova assinatura digital, setando­a para a implementação do hash­ then­invert MD5 com RSA disponível no Bouncy Castle. Poderia ser usada a mesma assinatura definida no bloco de código anterior Signature sig = Signature.getInstance("MD5withRSA", "BC"); //Inicia o processo de verificação usando a chave pública gerada no primeiro bloco de código sig.initVerify(kp.getPublic()); //Inclui a mensagem passada como parâmetro para ser verificada sig.update(mensagem); //Verifica a autencidade da mensagem com a assinatura passada com parâmetro return sig.verify(assinatura); }
Com o exemplo acima vemos como o pacote java.security poupa um grande trabalho oferecendo uma maneira muito simples de adicionar propriedades de segurança a um sistema java, pois com essas poucas linhas de código no sistema podemos definir assinaturas e verificá­las usando algoritmos consagrados, como o MD5 e o RSA. O uso de esquemas de encriptação, cifras de bloco etc. é definido de maneira semelhante. Como projeto para exemplificar o usar o prático do pacote, definimos uma aplicação java que gera assinaturas usando os diversos algoritmos oferecidos pelo Bouncy Castle. Um screenshot da aplicação encontra­se na apresentação feita em sala. Algo a se levar em consideração no uso dessa solução é a confiabilidade de quem oferece o Provider . Você deve se assegurar de que os algoritmos estão implementados de forma correta na linguagem, seguindo fielmente a especificação dos mesmos. Só assim você pode assumir e provar as propriedades de segurança asseguradas aos algoritmos pelos modelos matemáticos estudados durante o curso.
Anexos RSA.java /* * Created on 22/08/2005 * * TODO To change the template for this generated file go to * Window ­ Preferences ­ Java ­ Code Style ­ Code Templates */
package rsa; import java.math.BigInteger; import java.security.SecureRandom; /**
* @author jfof * * TODO To change the template for this generated type comment go to * Window ­ Preferences ­ Java ­ Code Style ­ Code Templates */
public class RSA { private BigInteger n, d, e, p, q; /**
* @return Returns the d. */
public BigInteger getD() { return d; } /**
* @return Returns the e. */
public BigInteger getE() { return e; } /**
* @return Returns the n. */
public BigInteger getN() { return n; } /**
* @return Returns the p. */
public BigInteger getP() { return p; } /**
* @return Returns the q. */
public BigInteger getQ() { return q; } public RSA(int bitlen) { SecureRandom r = new SecureRandom(); p = new BigInteger(bitlen / 2, 100, r); q = new BigInteger(bitlen / 2, 100, r); n = p.multiply(q); BigInteger m = (p.subtract(BigInteger.ONE)) .multiply(q.subtract(BigInteger.ONE)); e = new BigInteger("3"); while(m.gcd(e).intValue() > 1) e = e.add(new BigInteger("2")); d = e.modInverse(m); } public BigInteger encrypt(BigInteger message) { return message.modPow(e, n); } public BigInteger decrypt(BigInteger message) { return message.modPow(d, n); } public BigInteger[] encrypt(byte[] pMsg, boolean ds) { BigInteger[] retorno = fromByte(pMsg); for (int i = 0; i < retorno.length; i++) if (!ds) retorno[i] = this.encrypt(retorno[i]); else retorno[i] = this.decrypt(retorno[i]); return retorno; }
public byte[] decrypt(BigInteger[] pCiphertext, int pTam, boolean ds) { for (int i = 0; i < pCiphertext.length; i++) if (!ds) pCiphertext[i] = this.decrypt(pCiphertext[i]); else pCiphertext[i] = this.encrypt(pCiphertext[i]); return fromBigInteger(pCiphertext, pTam); } public static byte[] fromBigInteger(BigInteger[] pBigInteger, int pTam) { byte[] retorno = new byte[pTam]; int inicio = 0; byte[] temp = new byte[10]; for (int i = 0; i < pBigInteger.length; i++) { temp = pBigInteger[i].toByteArray(); for (int j = 0; j < temp.length; j++) if (inicio < pTam) retorno[inicio++] = temp[j]; } return retorno; } public static BigInteger[] fromByte(byte[] pByte) { int tam = pByte.length / 10; if (pByte.length%10 != 0) tam++; //Cria o array de retorno BigInteger[] retorno = new BigInteger[tam]; int inicio = 0; byte[] temp = new byte[10]; for (int i = 0; i < tam; i++) { for (int j = inicio; j < Math.min(inicio+10, pByte.length); j++) { temp[j­inicio] = pByte[j]; } inicio += 10; if (pByte.length < inicio)
temp = trim(temp, inicio ­ pByte.length); retorno[i] = new BigInteger(temp); } return retorno; } public static byte[] trim(byte[] pArg, int pInt) { byte[] retorno = new byte [pArg.length ­ pInt]; for (int i = 0; i < pArg.length ­ pInt; i++) retorno [i] = pArg[i]; return retorno; }
}