RSA de cifrado. Descrición e implementación do algoritmo RSA

RSA de cifrado é un dos primeiros sistemas de cifrado de clave pública prácticos que é amplamente utilizado para a transmisión segura de datos. A súa principal diferenza con respecto a servizos similares é que a clave de cifrado se abre e diferente da chave de desencriptación, que é mantida en segredo. A tecnoloxía RSA , esta asimetría está baseado na dificultade práctica de factoring reprodución de dous grandes números primos (o problema de factoring).

Historia da creación

RSA O nome está composto polas iniciais dos apelidos Rivest, Shamir e Adleman - os científicos que primeiro describiu publicamente estes algoritmos de cifrado en 1977. Klifford Koks, un matemático inglés, que traballaba para os servizos de intelixencia británicos, a primeira en desenvolver un sistema equivalente en 1973, pero non foi desclasificado ata 1997

user RSA crea e publica a clave pública baseada en dous grandes números primos xunto co valor auxiliar. Os números primos debe ser mantido en segredo. Calquera pode usar a chave pública para cifrar unha mensaxe, pero se é grande de abondo, entón só alguén con coñecemento de números primos pode decodificar a mensaxe. RSA divulgación cifrado é coñecido como o principal problema hoxe é unha discusión aberta sobre como un mecanismo de confianza.

algoritmo RSA é relativamente lenta, polo que non é tan amplamente utilizado para directamente cifrar o usuario. Na maioría dos casos, este método é usado para transmisión en clave compartida cifrada para unha clave de cifrado simétrica, que á súa vez pode realizar operacións de cifrado e descifrado en masa a unha velocidade moito maior.

Cando había un sistema de cifrado na súa forma actual?

A idea de chave criptográfica asimétrica atribuída a Diffie e Hellman, que publicou o concepto en 1976, a introdución de sinaturas dixitais, e tentar aplicar a teoría dos números. A súa formulación utiliza unha clave secreta compartida xera a partir dun certo número de exponenciação módulo un número primo. Sen embargo, deixou aberta a cuestión da realización desta función, xa que os principios de factoring non foi ben comprendida na época.

Rivest, Adi Shamir e Adleman do MIT fixeron varios intentos ó longo dos anos para crear unha función Unha forma que é difícil de descifrar. Rivest e Shamir (como científicos da computación) propuxeron moitas funcións potenciais, mentres Adleman (como a matemática) para buscar "puntos débiles" do algoritmo. Utilizaban unha serie de enfoques e, finalmente, desenvolver un sistema final, agora coñecido como RSA en abril de 1977.

sinatura electrónica ea clave pública

sinatura dixital ou sinatura electrónica, é unha parte integrante dos tipos de documentos electrónicos. El está formado nunha certos cambios de datos criptográficos. Con este atributo pode verificar a integridade do documento, a súa confidencialidade, así como para determinar quen é o dono. De feito, unha alternativa para a sinatura por defecto común.

Este sistema de cifrado (RSA-cifradas) ofrece a chave pública, a diferenza simétrica. O seu principio de funcionamento é que as dúas claves diferentes son usadas - pechado (criptografía) e ao aire libre. A primeira é usado para xerar a sinatura dixital e, a continuación, ser capaz de descifrar o texto. En segundo lugar - para o cifrado real e sinatura electrónica.

Usando sinaturas para entender mellor o cifrado RSA, un exemplo de que pode ser reducido como un segredo normal "pechada de ollos curiosos," o documento.

Cal é o algoritmo?

algoritmo RSA consiste en catro pasos: xeración de chaves, distribución, cifrado e descifrado. Como xa se mencionou, RSA de cifrado inclúe unha chave pública e unha clave privada. Ao aire libre pode ser coñecido por todos e é usado para cifrar mensaxes. A súa esencia reside no feito de que as mensaxes cifradas coa chave pública só pode ser descifrada nun determinado período de tempo usando unha clave secreta.

Por razóns de seguridade, os enteiros a ser elixido ao azar e ser idénticos en tamaño, pero difiren en lonxitude por uns números para facer factoring máis difícil. Mesmo mesmo número pode ser efectivamente encontrado por unha proba na súa sinxeleza, para cifrado de información debe necesariamente ser complicado.

A clave pública consiste no módulo e expoñente público. Unidade interior e consta dunha figura privada, que debe ser mantido en segredo.

cifrado RSA de arquivos e débiles

Con todo, hai unha serie de mecanismos RSA hackers simple. Ao cifrar con valores baixos e pequenas de números de código pode ser facilmente aberto, o texto cifrado elección raíz sobre os enteiros.

Dende o RSA de cifrado é un algoritmo determinista (é dicir, non ten ningún compoñente aleatorio), un atacante pode lanzar con éxito o ataque aberto texto seleccionado contra o sistema de cifrado, cifrado plaintexts probables baixo a clave pública e verifica se son iguais texto cifrado. Semanticamente sistema de cifrado seguro é chamado no caso de que un atacante non pode distinguir entre os dous cifrado do outro, aínda que el coñece os textos pertinentes en forma ampliada. Tal como descrito anteriormente, RSA outros servizos sen estofo non é semanticamente seguro.

algoritmos adicionais para cifrado e protección

Para evitar os problemas enriba, na implantación práctica da RSA son normalmente inseridos algunha forma de estrutura, de recheo aleatorio antes de cifrado. Isto garante que o contido non se enmarca no rango de textos inseguras, e que esta mensaxe non pode ser resolto por sorteo.

Seguridade RSA cryptosystem e cifrado baseada en dous problemas matemáticos: o problema da fatoração de números grandes eo problema RSA. A divulgación completa do texto cifrado e sinatura na RSA é considerado inadmisible no presuposto de que estes dous problemas non poden ser resoltos colectivamente.

Con todo, coa capacidade de recuperar factores primos, un atacante pode calcular o expoñente segredo da chave pública e, a continuación, descifrar texto usando o procedemento estándar. A pesar do feito de que hoxe ningún método existente a factores grandes enteiros nun ordenador clásico non se pode atopar, non se probou que non existe.

automatización

A ferramenta, chamada Yafu, pode ser usado para optimizar o proceso. Automatización en YAFU é un recurso avanzado que combina algoritmos de fatoração na metodoloxía intelectual e adaptable que minimiza o tempo para atopar os factores de números de entrada arbitrarias. A maioría das implementacións de múltiples algoritmo permite Yafu uso completo de multi- ou varios procesadores de núcleos múltiples (incluíndo SNFS, SIQS e ECM). Primeiro de todo, é controlado pola ferramenta de liña de comandos. O tempo gastado na procura de factor de cifrado Yafu usar un ordenador convencional, pode ser reducida a segundos 103.1746. A ferramenta procesa o binario capacidade de 320 bits ou máis. Este é un programa moi complexo que esixe unha certa cantidade de habilidades técnicas para instalar e configurar. Así, a RSA-cifrado pode ser vulnerable C.

Hacking intentos nos últimos tempos

En 2009, Bendzhamin Mudi usar o RSA-512 bits estaba traballando descifrar kriptoteksta para 73 días, usando só software ben coñecido (GGNFS) eo escritorio media (dobre núcleo Athlon 64 a 1900 MHz). Como mostra a experiencia, é necesario un pouco menos de 5 GB de disco e preto de 2,5 gigabytes de memoria para o proceso de "peneirar".

A partir de 2010, o número máis grande foi consignado RSA 768 bits de lonxitude (232 díxitos decimais, ou RSA-768). A súa difusión durou dous anos en varios centos de ordenadores á vez.

Na práctica, as claves RSA son longos - tipicamente de 1024 a 4096 bits. Algúns expertos cren que as claves de 1024 bits pode facer-se non fiable nun futuro próximo ou máis pode ser dobres dianteiros moi ben financiados. Con todo, algúns argumentan que as claves de 4096 bits poden ser divulgadas no futuro próximo.

perspectivas

Polo tanto, como regra xeral, presúmese que RSA é seguro se os números son grandes abondo. Se o número base de 300 bits ou máis curtos, ea sinatura dixital cifrado pode ser descomposto en poucas horas en un ordenador persoal a usar o software xa dispoñibles no dominio público. A clave 512 bits de lonxitude, como se mostra, pode ser aberta, xa en 1999, co uso de algunhas centenas de computadores. Hoxe en día é posible en poucas semanas usando un hardware dispoñibles ao público. Así, é posible que en buduschembudet facilmente facilitados RSA-cifradas nos dedos, eo sistema pode chegar a ser irremediablemente superada.

Oficialmente en 2003, foi posta en dúbida a seguridade das claves de 1024 bits. Actualmente, recoméndase ter unha lonxitude mínima de 2048 bits.