RSA-xifrat. Descripció i aplicació de l'algorisme RSA

RSA-xifrat és un dels primers sistemes de xifrat de clau pública pràctics que s'utilitza àmpliament per a la transmissió segura de dades. La seva principal diferència respecte als serveis similars és que la clau de xifrat està obert i diferent de la clau de desxifrat, que es manté en secret. La tecnologia RSA , aquesta asimetria es basa en la dificultat pràctica de factoritzar la reproducció de dos nombres primers grans (el problema de la factorització).

Història de la creació

RSA El nom es compon de les lletres inicials dels cognoms Rivest, Shamir i Adleman - els científics que va descriure per primera vegada públicament aquests algoritmes de xifrat en 1977. Klifford Koks, un matemàtic anglès, que treballava per als serveis d'intel·ligència britànics, els primers a desenvolupar un sistema equivalent en l'any 1973, però no va ser desclassificat fins al 1997

RSA usuari crea i publica la clau pública basat en dos nombres primers grans juntament amb el valor auxiliar. Els nombres primers han de ser mantinguts en secret. Qualsevol pot fer servir la clau pública per xifrar un missatge, però si és prou gran, llavors només algú amb el coneixement dels nombres primers pot descodificar el missatge. divulgació de xifrat RSA és conegut com el principal problema avui dia és una discussió oberta sobre com un mecanisme fiable.

algoritme RSA és relativament lent, de manera que no és tan àmpliament utilitzat per directament xifrar l'usuari. En la majoria dels casos, aquest mètode s'utilitza per a la transmissió en la clau compartida xifrada per a una clau de xifrat simètrica, que al seu torn pot portar a terme operacions de xifrat i desxifrat a granel a una velocitat molt més gran.

Quan hi havia un sistema de xifrat en la seva forma actual?

La idea de la clau criptogràfica asimètrica atribueix a Diffie i Hellman, que va publicar el concepte el 1976, la introducció de la signatura digital, i tractant d'aplicar la teoria dels nombres. La seva formulació utilitza una clau secreta compartida generada a partir d'un cert nombre de exponenciació mòdul un nombre primer. No obstant això, van deixar oberta la qüestió de la realització d'aquesta funció, ja que els principis de la factorització no s'entenen bé en el moment.

Rivest, Adi Shamir i Adleman al MIT han fet diversos intents en els últims anys per crear una funció d'un sol sentit que és difícil de desxifrar. Rivest i Shamir (com els informàtics) han proposat moltes funcions potencials, mentre que Adleman (com les matemàtiques) per buscar "punts febles" de l'algoritme. Ells utilitzen una gran quantitat d'enfocaments i, finalment, desenvolupar un sistema final, ara conegut com RSA a l'abril de 1977.

signatura electrònica i la clau pública

signatura digital o signatura electrònica, és una part integral dels tipus de documents electrònics. Es forma en un cert canvis de dades criptogràfics. Amb aquest atribut possible comprovar la integritat del document, la seva confidencialitat, així com per determinar qui és el propietari. De fet, una alternativa a la signatura estàndard comú.

Aquest sistema de xifrat (RSA-encriptat) ofereix la clau pública, a diferència simètrica. El seu principi de funcionament és que s'utilitzen les dues claus diferents - tancat (xifrada) ia l'aire lliure. El primer s'utilitza per generar la signatura digital i després ser capaç de desxifrar el text. En segon lloc - per al xifrat real i la signatura electrònica.

L'ús de signatures per a comprendre millor el xifrat RSA, un exemple que es pot reduir com un secret normal "tancat de mirades indiscretes," el document.

Quin és l'algoritme?

algoritme RSA consisteix en quatre passos: la generació de claus, distribució, xifrat i desxifrat. Com ja s'ha esmentat, RSA-xifrat inclou una clau pública i una clau privada. A l'aire lliure pot ser coneguda per tots i serà utilitzat per xifrar missatges. La seva essència rau en el fet que els missatges xifrats amb la clau pública només poden ser desxifrats en un període determinat de temps usant una clau secreta.

Per raons de seguretat, els números enters a ser elegits a l'atzar i siguin idèntics en grandària, però difereixen en longitud per uns números per fer la factorització més difícil. mateix nombre mateixa es pot trobar de manera efectiva mitjançant una prova en la seva simplicitat, de manera que el xifrat de la informació ha de necessàriament ser complicat.

La clau pública consisteix en el mòdul i exponent públic. unitat interior i consisteix en una figura privada, que s'ha de mantenir en secret.

xifrat RSA d'arxius i debilitats

No obstant això, hi ha una sèrie de simples mecanismes RSA pirateria. A l'xifrar amb valors baixos i petits de nombres de codi es pot obrir fàcilment, si el text xifrat arran de la selecció sobre els nombres enters.

Atès que el RSA-xifrat és un algoritme determinista (és a dir, no té component aleatori), un atacant pot llançar amb èxit el text atac obert seleccionat contra el criptosistema mitjançant l'encriptació de textos plans probables sota la clau pública i els controls de si són iguals text xifrat. Semànticament sistema criptogràfic segur és cridat en el cas que un atacant no pot distingir entre els dos xifrat entre si, fins i tot si ell coneix els textos pertinents en la forma expandida. Com es va descriure anteriorment, RSA altres serveis sense farciment no és semànticament segur.

algoritmes addicionals per al xifrat i la protecció

Per evitar els problemes anteriors, en l'aplicació pràctica d'RSA són en general s'insereix en algun tipus de farciment estructurat, aleatoritzat abans del xifrat. Això assegura que el contingut no es troba dins de la gamma de textos plans insegurs, i que aquest missatge no pot ser resolt per la selecció a l'atzar.

Criptosistema RSA Security i el xifrat basat en dos problemes matemàtics: el problema de factoritzar nombres grans i el problema real RSA. La revelació completa del text xifrat i signatura en el RSA es considera inadmissible en el cas que tots dos d'aquests problemes no es poden resoldre de manera col·lectiva.

No obstant això, amb la possibilitat de recuperar els factors primers, un atacant pot calcular l'exponent secret de la clau pública i després desxifrar el text utilitzant el procediment estàndard. Tot i que avui en dia cap mètode existent per a factoritzar sencers grans en un equip clàssic no es pot trobar, no s'ha demostrat que no existeix.

automatització

L'eina, anomenada Yafu, es pot utilitzar per optimitzar el procés. Automatització en YAFU és una funció avançada que combina algoritmes de factorització en la metodologia intel·lectual i adaptatiu que redueix al mínim el temps per trobar els factors d'ingrés de nombres arbitraris. La majoria de les implementacions de multiprocés algoritme que permet Yafu ple ús de multi o molts processadors de múltiples nuclis (incloent SNFS, SIQS i ECM). En primer lloc, es controla mitjançant l'eina de línia d'ordres. El temps de recerca de factor d'Yafu xifrat usant un ordinador convencional, pot reduir-se a segons 103.1746. L'eina processa el binari capacitat de 320 bits o més. Aquest és un programari molt complex que requereix una certa quantitat de coneixements tècnics per a instal·lar i configurar. Per tant, RSA-xifrat pot ser vulnerable C.

Els intents de hacking en els últims temps

El 2009, Bendzhamin Mudi utilitzant la clau RSA-512 bits estava treballant en desxifrar kriptoteksta durant 73 dies, utilitzant el programari només és ben conegut (GGNFS) i la mitjana d'escriptori (de doble nucli Athlon 64 a 1900 MHz). Com es mostra per l'experiència, es requereix una mica menys de 5 GB de disc i al voltant de 2,5 gigabytes de memòria per al procés de "tamisar."

A partir del 2010, el nombre més gran es factoritza RSA 768 bits de llarg (232 dígits decimals, o RSA-768). La seva divulgació va durar dos anys en diversos centenars d'ordinadors alhora.

A la pràctica, les claus RSA són llargs - en general de 1024-4096 bits. Alguns experts creuen que les claus de 1024 bits pot no ser fiable en un futur pròxim o fins i tot més temps pot ser violada atacants molt ben finançats. No obstant això, pocs podrien argumentar que les claus de 4096 bits també poden ser revelats en un futur pròxim.

perspectives

Per tant, per regla general, s'assumeix que RSA és segur si els números són prou grans. Si el nombre de la base de 300 bits o més curt, i la signatura digital de text xifrat es pot descompondre en unes poques hores en un ordinador personal utilitzant el programari ja està disponible en el domini públic. Una clau de longitud 512 bits, com es mostra, es poden obrir ja el 1999, amb l'ús d'uns pocs centenars d'ordinadors. Avui dia és possible en unes poques setmanes utilitzant un maquinari disponible públicament. Així, és possible que en buduschembudet fàcilment revelada RSA-encriptada en els dits, i el sistema es convertirà irremeiablement obsolet.

Oficialment el 2003, va ser posat en dubte la seguretat de les claus de 1024 bits. Actualment, es recomana tenir una longitud mínima de 2048 bits.