Criptossistema Cramer – Shoup - Cramer–Shoup cryptosystem
O sistema Cramer – Shoup é um algoritmo de criptografia de chave assimétrica e foi o primeiro esquema eficiente comprovado como seguro contra ataques de texto cifrado escolhido adaptativo usando suposições criptográficas padrão. Sua segurança é baseada na intratabilidade computacional (amplamente assumida, mas não provada) da suposição de decisão Diffie-Hellman. Desenvolvido por Ronald Cramer e Victor Shoup em 1998, é uma extensão do criptossistema ElGamal. Em contraste com o ElGamal, que é extremamente maleável, o Cramer – Shoup adiciona outros elementos para garantir a não maleabilidade, mesmo contra um invasor habilidoso. Esta não maleabilidade é alcançada através do uso de uma função hash unilateral universal e cálculos adicionais, resultando em um texto cifrado que é duas vezes maior que no ElGamal.
Ataques adaptativos de texto cifrado escolhido
A definição de segurança alcançada pelo Cramer – Shoup é formalmente denominada " indistinguibilidade sob ataque de texto cifrado escolhido adaptativo " (IND-CCA2). Esta definição de segurança é atualmente a definição mais forte conhecida para um sistema de criptografia de chave pública: ela assume que o invasor tem acesso a um oráculo de descriptografia que irá descriptografar qualquer texto cifrado usando a chave de descriptografia secreta do esquema. O componente "adaptativo" da definição de segurança significa que o invasor tem acesso a esse oráculo de descriptografia antes e depois de observar um texto cifrado de destino específico para atacar (embora seja proibido de usar o oráculo para simplesmente descriptografar esse texto cifrado de destino). A noção mais fraca de segurança contra ataques de texto cifrado escolhido não adaptativo (IND-CCA1) só permite que o invasor acesse o oráculo de descriptografia antes de observar o texto cifrado alvo.
Embora fosse bem conhecido que muitos criptossistemas amplamente usados eram inseguros contra esse tipo de invasor, por muitos anos os projetistas de sistemas consideraram o ataque impraticável e de grande interesse teórico. Isso começou a mudar no final da década de 1990, principalmente quando Daniel Bleichenbacher demonstrou um ataque prático de texto cifrado escolhido adaptável contra servidores SSL usando uma forma de criptografia RSA .
Cramer – Shoup não foi o primeiro esquema de criptografia a fornecer segurança contra ataques de texto cifrado escolhido adaptável. Naor – Yung, Rackoff – Simon e Dolev – Dwork – Naor propuseram conversões comprovadamente seguras de esquemas padrão (IND-CPA) em esquemas IND-CCA1 e IND-CCA2. Essas técnicas são seguras sob um conjunto padrão de suposições criptográficas (sem oráculos aleatórios), no entanto, elas dependem de técnicas complexas de prova de conhecimento zero e são ineficientes em termos de custo computacional e tamanho do texto cifrado. Uma variedade de outras abordagens, incluindo Bellare / Rogaway 's OAEP e Fujisaki-Okamoto conseguir construções eficientes usando uma abstracção matemática conhecida como a Oracle aleatória . Infelizmente, implementar esses esquemas na prática requer a substituição de alguma função prática (por exemplo, uma função hash criptográfica ) no lugar do oráculo aleatório. Um crescente corpo de evidências sugere a insegurança dessa abordagem, embora nenhum ataque prático tenha sido demonstrado contra os esquemas implantados.
O criptossistema
Cramer – Shoup consiste em três algoritmos: o gerador de chave, o algoritmo de criptografia e o algoritmo de descriptografia.
Geração de chave
- Alice gera uma descrição eficiente de um grupo cíclico de ordem com dois geradores aleatórios distintos .
- Alice escolhe cinco valores aleatórios de .
- Alice calcula .
- Alice publica , junto com a descrição de , como sua chave pública . Alice retém como sua chave secreta . O grupo pode ser compartilhado entre usuários do sistema.
Encriptação
Para criptografar uma mensagem para Alice com sua chave pública ,
- Bob se converte em um elemento de .
- Bob escolhe um aleatório de e calcula:
- , onde H () é uma função hash unilateral universal (ou uma função hash criptográfica resistente a colisões , que é um requisito mais forte).
- Bob envia o texto cifrado para Alice.
Decifrar
Para descriptografar um texto cifrado com a chave secreta de Alice ,
- Alice calcula e verifica isso . Se esse teste falhar, a descriptografia posterior será cancelada e a saída será rejeitada.
- Caso contrário, Alice calcula o texto simples como .
O estágio de descriptografia descriptografa corretamente qualquer texto cifrado devidamente formado, uma vez que
- , e
Se o espaço de mensagens possíveis for maior do que o tamanho de , então o Cramer – Shoup pode ser usado em um criptossistema híbrido para melhorar a eficiência em mensagens longas.
Referências
- ^ Daniel Bleichenbacher. Ataques de texto cifrado escolhidos contra protocolos baseados no padrão de criptografia RSA PKCS # 1. Avanços na Criptologia - CRYPTO '98. [1]
- ^ Ran Canetti, Oded Goldreich , Shai Halevi. The Random Oracle Methodology, Revisited . Journal of the ACM, 51: 4, páginas 557–594, 2004.
- Ronald Cramer e Victor Shoup . "Um criptosistema de chave pública prático comprovadamente seguro contra ataques de texto cifrado escolhido adaptável." no processo da Crypto 1998, LNCS 1462, p. 13ff ( ps , pdf )
- Implementações de brinquedo de Cramer – Shoup em Emacs Lisp e Java
- 1998 a cobertura de notícias do vintage de publicação de Cramer e Shoup na Wired News e em Bruce Schneier 's Crypto-Gram
- Ronald Cramer e Victor Shoup : "Provas de hash universais e um paradigma para a criptografia de chave pública segura do texto cifrado escolhido." nos procedimentos do Eurocrypt 2002, LNCS 2332, pp. 45–64. Versão Completa (pdf)