RSA (cryptosystem) (Português)
usando o algoritmo de resto Chinês
para eficiência muitas bibliotecas de criptografia populares (como OpenSSL, Java e.NET) usam a seguinte otimização para decriptação e assinatura com base no teorema do restante Chinês. Os seguintes valores são pré-computados e armazenados como parte da chave privada:
estes valores permitem ao destinatário calcular a exponenciação m = cd (mod pq) de forma mais eficiente do que a seguinte:
isto é mais eficiente do que a exponenciação computacional, mesmo que duas exponenciações modulares tenham que ser computadas., A razão é que estas duas exponenciações modulares usam um expoente menor e um módulo menor.
fatoração inteira e problema RSA
a segurança do sistema criptográfico RSA é baseada em dois problemas matemáticos: o problema da factoração de números grandes e o problema RSA. Acredita-se que a decriptação completa de um cifrotexto RSA seja inviável na suposição de que ambos os problemas são difíceis, ou seja, nenhum algoritmo eficiente existe para resolvê-los., Fornecer segurança contra a descriptografia parcial pode exigir a adição de um sistema de estofamento seguro.
O problema RSA é definido como a tarefa de tomar as raízes eth modulo a Composto n: recuperar um valor m tal que c ≡ me (mod n), onde (n, e) é uma chave pública RSA e c é um cifrotexto RSA. Atualmente, a abordagem mais promissora para resolver o problema RSA é o fator do módulo N. Com a capacidade de recuperar fatores primos, um atacante pode computar o expoente secreto d a partir de uma chave pública (n, e), em seguida, descriptografar c usando o procedimento padrão. , Para conseguir isso, um atacante fatores n em p E q, e calcula lcm(p − 1, q − 1) que permite a determinação de d de E. nenhum método em tempo polinomial para fatorar inteiros grandes em um computador clássico ainda foi encontrado, mas não foi provado que nenhum existe. Veja fatoração inteira para uma discussão deste problema.
sive quadrático múltiplo polinomial (MPQS) pode ser usado para fator do módulo Público n.,
a primeira factorização RSA-512 em 1999 utilizou centenas de computadores e exigiu o equivalente a 8.400 MIPS anos, durante um tempo decorrido de aproximadamente sete meses. Em 2009, Benjamin Moody poderia fatorar uma chave RSA-512 bit em 73 dias usando apenas software Público (GGNFS) e seu computador desktop (um Athlon64 Dual-core com uma cpu de 1.900 MHz). Apenas menos de cinco gigabytes de armazenamento em disco foram necessários e cerca de 2,5 gigabytes de RAM para o processo de crivagem.,
Rivest, Shamir, and Adleman noted that Miller has shown that – assuming the truth of the Extended Riemann Hypothesis – finding d from N and e is as hard as factoring n into p and q (up to a polynomial time difference). No entanto, Rivest, Shamir e Adleman observaram, na seção IX/D de seu papel, que eles não tinham encontrado uma prova de que inverter a RSA é tão difícil quanto factoring.
A partir de 2020, o maior número de RSA factorred conhecido publicamente era de 829 bits (250 dígitos decimais, RSA-250). Sua fatoração, por uma implementação distribuída de última geração, levou cerca de 2700 anos de CPU., Na prática, as chaves RSA têm normalmente 1024 a 4096 bits de comprimento. Em 2003, a RSA Security estimou que as chaves de 1024 bits provavelmente se tornariam racháveis em 2010. A partir de 2020, não se sabe se essas chaves podem ser rachadas, mas as recomendações mínimas mudaram para pelo menos 2048 bits. Presume-se geralmente que a RSA é Segura se n é suficientemente grande, fora da computação quântica.
Se n for 300 bits ou mais curto, ele pode ser facturado em algumas horas em um computador pessoal, usando software já disponível livremente., Chaves de 512 bits foram mostradas como praticamente quebráveis em 1999, quando o RSA-155 foi facturado usando várias centenas de computadores, e estes são agora factorizados em algumas semanas usando hardware comum. Exploits using 512-bit code-signing certificates that may have been factored were reported in 2011. Um dispositivo de hardware teórico chamado TWIRL, descrito por Shamir e Tromer em 2003, colocou em questão a segurança de 1024 bits chaves.,
in 1994, Peter Shor showed that a quantum computer – if one could ever be practically created for the purpose – would be able to factor in polynomial time, breaking RSA; see Shor”s algorithm.esta secção necessita de citações adicionais para verificação. Por favor, ajude a melhorar este artigo adicionando citações a fontes confiáveis. O material não recolhido pode ser desafiado e removido.,
Encontre fontes: “RSA” criptosistema – notícias · jornais e revistas · livros · bolsista · MEE (outubro de 2017) (Saiba como e quando para remover este modelo de mensagem)
Encontrar o grande primos p e q geralmente é feito por testes de números aleatórios do tamanho correto com probabilística testes de primalidade que rapidamente eliminar virtualmente todos os nonprimes.
os números p E q não devem ser “muito próximos”, para que a fatoração de Fermat para n Seja bem sucedida., Se p-q é inferior a 2n1 / 4 (n = p * q, Que mesmo para pequenos valores de 1024 bits de n é 3×1077) resolver para p E q é trivial. Além disso, se p − 1 ou q − 1 tem apenas pequenos fatores primos, n pode ser facilmente contabilizado pelo algoritmo P − 1 de Pollard, e, portanto, tais valores de P ou q devem ser descartados.é importante que o expoente privado d seja suficientemente grande. Michael J. Wiener mostrou que se p está entre q e 2q (o que é bastante típico) e d < n1/4/3, Então d pode ser computado eficientemente a partir de n e E.,
não há nenhum ataque conhecido contra pequenos expoentes públicos como e = 3, desde que o enchimento adequado é usado. O ataque de Coppersmith tem muitas aplicações em atacar a RSA especificamente se o expoente público e é pequeno e se a mensagem criptografada é curta e não acolchoada. 65537 é um valor comumente usado para e; este valor pode ser considerado como um compromisso entre evitar potenciais pequenos ataques expoentes e ainda permitir criptografias eficientes (ou verificação de assinatura)., A publicação especial NIST sobre Segurança Informática (SP 800-78 Rev 1 de agosto de 2007) não permite expoentes públicos e menores que 65537, mas não indica uma razão para esta restrição.
em outubro de 2017, uma equipe de pesquisadores da Universidade Masaryk anunciou a vulnerabilidade ROCA, que afeta chaves RSA geradas por um algoritmo incorporado em uma biblioteca da Infineon conhecida como RSALib. Um grande número de cartões inteligentes e módulos de plataforma confiável (TPMs) foi mostrado para ser afetado. Chaves RSA vulneráveis são facilmente identificadas usando um programa de teste que a equipe lançou.,
a Importância do forte de números aleatórios generationEdit
Um criptograficamente forte gerador de números aleatórios, que foi devidamente fechada com adequada entropia, deve ser utilizado para gerar os primos p e q. Uma análise comparando milhões de chaves públicas reunidos a partir da Internet, foi realizada no início de 2012 por Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung e Christophe Wachter. Eles foram capazes de fatorar 0,2% das chaves usando apenas o algoritmo de Euclid.
eles exploraram uma fraqueza única para os sistemas de criptografia com base na fatoração de inteiros., Se n = pq é uma chave pública e n’ = p’ Q ‘é outra, então se por acaso p = p’ (mas q não é igual a q’), então uma computação simples de gcd(n, n’) = P fatores n e n’, comprometendo totalmente ambas as chaves. Lenstra et al. note que este problema pode ser minimizado usando uma semente aleatória forte de bit-length duas vezes o nível de segurança pretendido, ou empregando uma função determinística para escolher q dado p, em vez de escolher P E q independentemente.Nadia Heninger fazia parte de um grupo que fez uma experiência semelhante. Usaram uma ideia do Daniel J., Bernstein para calcular o GCD de cada chave RSA n contra o produto de todas as outras chaves n ‘que eles tinham encontrado(um número de 729 milhões de dígitos), em vez de computar cada gcd (n,n’) separadamente, alcançando assim uma velocidade muito significativa desde que após uma grande divisão, o problema GCD é de tamanho normal.
Heninger diz em seu blog que o mau chaves ocorreu quase que inteiramente em aplicações embarcadas, incluindo “firewalls, roteadores, dispositivos VPN, de administração de servidor remoto de dispositivos, impressoras, projetores e telefones VOIP” de mais de 30 fabricantes., Heninger explica que o problema de um-compartilhado-primo descoberto pelos dois grupos resulta de situações em que o gerador de números pseudorandom é mal semeado inicialmente, e então é novamente necessário entre a geração do primeiro e segundo primes. A utilização de sementes de entropia suficientemente elevada obtidas a partir de Temporizadores de traço-chave ou de ruído electrónico de díodos ou de ruído atmosférico de um receptor de rádio sintonizado entre estações deve resolver o problema.
forte geração aleatória de números é importante em todas as fases da criptografia de chave pública., Por exemplo, se um gerador fraco é usado para as chaves simétricas que estão sendo distribuídas pela RSA, então um bisbilhoteiro poderia contornar a RSA e adivinhar as chaves simétricas diretamente.
Timing attacksEdit
Kocher descreveu um novo ataque à RSA em 1995: se a atacante Eve conhece o hardware de Alice com detalhes suficientes e é capaz de medir os tempos de decriptação para vários cifrotextos conhecidos, Eve pode deduzir a chave de decriptação d rapidamente. Este ataque também pode ser aplicado contra o esquema de assinatura RSA., Em 2003, Boneh e Brumley demonstraram um ataque mais prático capaz de recuperar fatorizações RSA sobre uma conexão de rede (por exemplo, a partir de um servidor web Secure Sockets Layer (SSL)-habilitado).
uma maneira de impedir estes ataques é garantir que a operação de decriptação leva uma quantidade constante de tempo para cada cifrotexto. No entanto, esta abordagem pode reduzir significativamente o desempenho., Em vez disso, a maioria das implementações RSA usam uma técnica alternativa conhecida como blindagem criptográfica. RSA blinding faz uso da propriedade multiplicativa da RSA. Em vez de computar cd (mod n), Alice primeiro escolhe um valor aleatório secreto r e calcula (rec)d (mod n). O resultado desta computação, depois de aplicar o teorema de Euler, é rcd (mod n) e assim o efeito de r pode ser removido multiplicando por seu inverso. Um novo valor de r é escolhido para cada cifrotexto. Com blinding aplicado, o tempo de decriptação não está mais correlacionado com o valor do cifrotexto de entrada, e assim o ataque de timing falha.,
Adaptativo de texto cifrado escolhido attacksEdit
Em 1998, Daniel Bleichenbacher descreveu a primeira prática adaptativa de texto cifrado escolhido ataque, contra RSA mensagens criptografadas usando o PKCS #1 v1 preenchimento esquema (um preenchimento em regime de embaralha e adiciona estrutura para um RSA-mensagem criptografada, de modo que é possível determinar se uma mensagem descriptografada é válido). Devido a falhas com o esquema PKCS #1, Bleichenbacher foi capaz de montar um ataque prático contra as implementações RSA do protocolo Secure Socket Layer, e recuperar chaves de sessão., Como resultado deste trabalho, os criptógrafos agora recomendam o uso de esquemas de acolchoamento comprovadamente seguros, como o padrão de criptografia assimétrica ideal, e os Laboratórios RSA lançaram novas versões de Pcs # 1 que não são vulneráveis a esses ataques.
Side-channel analysis attacksEdit
a side-channel attack using branch prediction analysis (BPA) has been described. Muitos processadores usam um predictor de ramo para determinar se um ramo condicional no fluxo de instrução de um programa é provável que seja tomado ou não. Muitas vezes estes processadores também implementam multithreading simultâneo (SMT)., Branch prediction analysis attacks use a spy process to discover (estatisticamente) the private key when processed with these processors.
Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a non-statistical way. Em seu artigo, “On the Power of Simple Branch Prediction Analysis”, os autores de SBPA (Onur Aciicmez e Cetin Kaya Koc) afirmam ter descoberto 508 de 512 bits de uma chave RSA em 10 iterações.
A power fault attack on RSA implementations was described in 2010., O autor recuperou a chave variando a tensão da CPU fora dos limites, o que causou várias falhas de energia no servidor.