RSA-kryptering. Beskrivelse og gennemførelse af RSA-algoritmen

RSA-kryptering er et af de første praktiske offentlig-key kryptosystemer der er meget brugt til sikker dataoverførsel. Dets vigtigste forskel fra lignende tjenester er, at krypteringsnøglen er åben og anderledes fra dekryptering nøgle, som holdes hemmelig. RSA-teknologien , denne asymmetri er baseret på de praktiske vanskeligheder ved factoring afspilning af to store primtal (problemet med factoring).

Historien om skabelsen

RSA Navnet består af de første bogstaver i efternavnene Rivest, Shamir og Adleman - de videnskabsmænd, der først offentligt beskrevet disse krypteringsalgoritmer i 1977. Klifford Koks, en engelsk matematiker, der arbejdede for de britiske efterretningstjenester, den første til at udvikle et tilsvarende system i 1973, men det blev ikke nedklassificeret indtil 1997

RSA bruger opretter og udgiver derefter den offentlige nøgle baseret på to store primtal sammen med den ekstra værdi. Primtal skal holdes hemmelige. Alle kan bruge den offentlige nøgle til at kryptere en meddelelse, men hvis det er stort nok, da kun en person med kendskab til primtal kan afkode budskabet. RSA-kryptering offentliggørelse er kendt som det største problem i dag er en åben diskussion om, hvordan en pålidelig mekanisme.

RSA-algoritmen er forholdsvis langsom, hvorfor det ikke er så udbredt at direkte kryptere brugeren. I de fleste tilfælde er denne metode anvendes til transmission i den delte nøgle krypteret for en symmetrisk krypteringsnøgle, som igen kan udføre operationer bulk-kryptering og dekryptering ved en meget højere hastighed.

Da der var en kryptosystem i sin nuværende form?

Ideen med asymmetrisk kryptografisk nøgle tilskrives Diffie og Hellman, der udgav konceptet i 1976, indførelse af digitale signaturer, og forsøger at anvende teorien om tal. Deres formulering bruger en delt hemmelig nøgle genereres fra et bestemt antal eksponentiering modulo et primtal. Men de forlod åbne spørgsmålet om realisering af denne funktion, da principperne for factoring ikke var godt forstået på det tidspunkt.

Rivest, Adi Shamir, og Adleman på MIT har gjort adskillige forsøg på gennem årene for at skabe en envejs-funktion, der er svært at afkode. Rivest og Shamir (som dataloger) har foreslået mange potentielle funktioner, mens Adleman (ligesom matematik) for at søge efter "svage punkter" i algoritmen. De brugte en masse tilgange og i sidste ende udvikle en endelige system, der nu er kendt som RSA i april 1977.

Elektronisk signatur og den offentlige nøgle

Digital signatur eller elektronisk signatur, er en integreret del af de elektroniske dokumenttyper. Det er dannet ved en bestemt kryptografiske dataændringer. Med denne attribut muligt at kontrollere integriteten af dokumentet, at deres fortrolighed, samt bestemme hvem der ejer det. Faktisk et alternativ til almindelig standard signatur.

Denne kryptosystem (RSA-krypteret) giver den offentlige nøgle, i modsætning til symmetrisk. Dens virkemåde er, at de to forskellige taster bruges - lukket (krypteret) og udendørs. Den første bruges til at generere den digitale signatur og derefter være i stand til at dekryptere teksten. For det andet - for den faktiske kryptering og elektronisk signatur.

Brug signaturer til bedre at forstå RSA-kryptering, hvoraf et eksempel kan reduceres som en normal hemmelighed "lukket fra nysgerrige blikke," dokumentet.

Hvad er den algoritme?

RSA-algoritmen består af fire trin: nøglegenerering, distribution, kryptering og dekryptering. Som allerede nævnt, RSA-kryptering indeholder en offentlig nøgle og en privat nøgle. Udendørs kan være kendt af alle og bruges til at kryptere meddelelser. Dens essens ligger i det faktum, at meddelelser krypteret med den offentlige nøgle kun kan dekrypteres i en given periode ved hjælp af en hemmelig nøgle.

Af sikkerhedsmæssige årsager, at de hele tal vælges tilfældigt og være identiske i størrelse, men adskiller sig i længden med et par numre for at gøre factoring vanskeligere. Samme samme nummer effektivt kan findes ved en test i deres enkelhed, så kryptering af oplysninger må nødvendigvis være kompliceret.

Den offentlige nøgle består af modul og offentlige eksponent. Indendørs enhed og består af en privat figur, som skal holdes hemmelige.

RSA-kryptering af filer og svagheder

Men der er en række simple hacking RSA mekanismer. Når kryptering med lave og små værdier af kodenumre let kan åbnes, hvis pick rod ciphertext over heltal.

Da RSA-kryptering er en deterministisk algoritme (dvs. ikke har nogen tilfældig komponent), en hacker kan med held starte den valgte tekst åbent angreb på kryptosystem ved at kryptere sandsynlige plaintexts under den offentlige nøgle og kontrol af, om de er lige ciphertext. Semantisk sikker kryptosystem kaldes i tilfælde af, at en hacker ikke kan skelne mellem de to kryptering fra hinanden, selv om han kender de relevante tekster i udvidet form. Som beskrevet ovenfor, RSA andre tjenester uden polstring er ikke semantisk sikker.

Yderligere algoritmer til kryptering og beskyttelse

At undgå de ovennævnte problemer, i den praktiske gennemførelse af RSA sædvanligvis indsat i en form for struktureret, randomiseret fyldning før kryptering. Dette sikrer, at indholdet ikke falder inden for området af usikre plaintexts, og at dette budskab ikke kan løses ved tilfældig udvælgelse.

Sikkerhed RSA kryptosystem og kryptering baseret på to matematiske problemer: problemet med factoring store tal og den faktiske RSA problemet. Fuld åbenhed af chiffertekst og underskrift i RSA anses afvises med den antagelse, at begge disse problemer ikke kan løses kollektivt.

Men med evnen til at komme sig primfaktorer, kan en hacker beregne den hemmelige eksponent for den offentlige nøgle og derefter dekryptere tekst ved hjælp af standardproceduren. På trods af, at der i dag ingen eksisterende metode til factoring store heltal på en klassisk computer ikke kan findes, er det ikke blevet bevist, at han ikke eksisterer.

automatisering

Værktøjet, kaldet Yafu, kan anvendes til at optimere processen. Automation i YAFU er en avanceret funktion, der kombinerer faktoriseringsmetoder algoritmer i intellektuel og adaptiv metode, der minimerer tid til at finde de faktorer, vilkårlige indtaste tal. De fleste implementeringer flertrådede algoritme tillader Yafu fuld brug af multi- eller mange multi-core processorer (herunder SNFS, SIQS og ECM). Først og fremmest er det styret af kommando-linje værktøj. Den tid søge efter kryptering Yafu faktor anvendelse af en konventionel computer, kan det blive reduceret til sekunder 103.1746. Værktøjet behandler binære kapacitet på 320 bit. Dette er et meget komplekst software, der kræver en vis mængde tekniske færdigheder til at installere og konfigurere. Således kan RSA-kryptering være sårbare C.

Hacking forsøg i nyere tid

I 2009 blev Bendzhamin Mudi hjælp RSA-512 bit nøgle arbejder på at dechifrere kriptoteksta for 73 dage, der kun bruger velkendte software (GGNFS) og den gennemsnitlige desktop (dual-core Athlon64 ved 1900 MHz). Som det fremgår af de erfaringer, der kræves lidt mindre end 5 GB disk og omkring 2,5 gigabyte hukommelse til processen med "sigtning".

Som i 2010, blev det største antal indregnet RSA 768 bits lang (232 decimaltal eller RSA-768). Hans afsløring varede to år på flere hundrede computere på en gang.

I praksis RSA-nøgler er lange - typisk fra 1024 til 4096 bit. Nogle eksperter mener, at de 1024-bit nøgler kan blive upålidelig i den nærmeste fremtid, eller endnu længere, kan være revnet meget vel-finansierede angribere. Men kun få vil hævde, at 4096-bit nøgler også kan offentliggøres i den nærmeste fremtid.

udsigter

som regel, antages det derfor, at RSA er sikker, hvis tallene er store nok. Hvis basen antal på 300 bit eller kortere, og den kodeteksten digitale signatur kan nedbrydes inden for et par timer på en personlig computer ved hjælp af software til rådighed allerede i det offentlige rum. En nøgle længde 512 bit, som vist, kan åbnes så tidligt som 1999, med brug af et par hundrede computere. I dag er det muligt i et par uger ved hjælp af en offentligt tilgængelig hardware. Således er det muligt, i buduschembudet nemt beskrevet RSA-krypteret på fingrene, og systemet vil blive håbløst forældet.

Officielt i 2003 blev sat spørgsmålstegn ved sikkerheden af de 1024-bit nøgler. I øjeblikket, anbefales det at have en længde på mindst 2048 bit.