RSA -krypteringsalgoritmen är baserad på komplexitet. Rsa -krypteringsalgoritm
RSA -kryptering är ett av de första praktiska offentliga nyckelkryptosystemen som ofta används för säker dataöverföring. Dess huvudsakliga skillnad från liknande tjänster är att krypteringsnyckeln är offentlig och skiljer sig från dekrypteringsnyckeln, som hålls hemlig. RSA -tekniken är baserad på factoringens praktiska komplexitet för att reproducera två stora primtal (factoring -problem).
Skapelsens historia
Namnet RSA består av initialerna till efternamnen Rivest, Shamir och Adleman, forskarna som först offentligt beskrev liknande 1977. Clifford Cox, en engelsk matematiker som arbetar för brittiska underrättelsetjänster, utvecklade först ett likvärdigt system 1973, men det avklassificerades först 1997.
En RSA -användare skapar och publicerar sedan en offentlig nyckel baserad på två stora primtal tillsammans med ett hjälpvärde. måste hållas konfidentiellt. Vem som helst kan använda den offentliga nyckeln för att kryptera ett meddelande, men om det är tillräckligt stort är det bara någon med kunskap om primtal som kan avkoda meddelandet. Avslöjandet av RSA -kryptering är känt som huvudproblemet: idag finns en öppen diskussion om hur tillförlitlig mekanismen är.
RSA är en relativt långsam algoritm, varför den inte används i stor utsträckning för den direkta användaren. Den vanligaste användningen av denna metod är att kryptera delade nycklar för en symmetrisk krypteringsnyckel, som i sin tur kan utföra bulkkryptering och dekrypteringsoperationer med en mycket högre hastighet.
När uppstod kryptosystemet i sin moderna form?
Idén om ett asymmetriskt nyckelkryptosystem tillskrivs Diffie och Hellman, som publicerade konceptet 1976, introducerade digitala signaturer och försökte tillämpa numret teori. Deras formulering använder en delad hemlig nyckel genererad från exponentiering av ett visst tal modulo ett primtal. De lämnade emellertid problemet med att genomföra denna funktion öppet, eftersom principerna för factoring inte var väl förstådda vid den tiden.
Rivest, Adi Shamir och Adleman på MIT har gjort flera försök under året att skapa en enkelriktad funktion som är svår att avkoda. Rivest och Shamir (som datavetare) föreslog många potentiella funktioner, medan Adleman (som matematiker) letade efter svagheter i algoritmen. De tog många tillvägagångssätt och slutligen utvecklade det som nu kallas RSA i april 1977.
EDS och offentlig nyckel
En elektronisk digital signatur, eller EDS, är en integrerad del av elektroniska dokument. Det bildas när en viss kryptografisk förändring av data. Med hjälp av detta attribut är det möjligt att kontrollera dokumentets integritet, dess konfidentialitet och även fastställa vem som är dess ägare. Detta är faktiskt ett alternativ till den vanliga standardsignaturen.
Detta kryptosystem (RSA -kryptering) erbjuder en offentlig nyckel som skiljer sig från symmetriska. Principen för dess funktion är att två olika nycklar används - privata (krypterade) och även offentliga. Den första används för att generera en EDS och därefter för att kunna dekryptera texten. Den andra är för den faktiska krypteringen och verifieringen av den digitala signaturen.
Användningen av en signatur möjliggör en bättre förståelse av RSA -kryptering, ett exempel som kan citeras som ett vanligt klassificerat "ur nyfikna ögon" -dokument.
Vad är kärnan i algoritmen?
RSA -algoritmen består av fyra steg: nyckelgenerering, nyckeldistribution, kryptering och dekryptering. Som redan nämnts inkluderar RSA -kryptering en offentlig nyckel och en privat nyckel. Öppet kan vara känt för alla och används för att kryptera meddelanden. Dess väsen ligger i det faktum att meddelanden som är krypterade med en offentlig nyckel endast kan dekrypteras inom en viss tid med hjälp av en hemlig nyckel.
Av säkerhetsskäl bör heltal slumpmässigt väljas och ha samma storlek, men skilja sig i längd med några siffror för att göra factoring svårare. Identiska nummer kan effektivt hittas med hjälp av ett test för deras enkelhet, så kryptering av information måste nödvändigtvis bli mer komplicerad.
Den offentliga nyckeln består av en modul och en offentlig exponent. Privat består av en modul och en privat indikator, som måste hållas hemlig.
RSA -filkryptering och svagheter
Det finns dock ett antal mekanismer för att knäcka enkel RSA. I kryptering med låga värden och låga värden på siffror kan krypteringen lätt brytas genom att välja roten för chiffertexten framför heltal.
Eftersom RSA -kryptering är en deterministisk algoritm (dvs den har ingen slumpmässig komponent) kan en angripare framgångsrikt starta en vald klartextattack mot ett kryptosystem genom att kryptera den troliga klartexten under den offentliga nyckeln och kontrollera om de är lika med krypteringen. Ett kryptosystem kallas semantiskt säkert om en angripare inte kan skilja mellan två krypteringar från varandra, även om han känner till motsvarande texter i den avslöjade formen. Som beskrivits ovan är RSA inte semantiskt säkert om det inte kompletteras med andra tjänster.
Ytterligare krypterings- och skyddsalgoritmer
För att undvika ovanstående problem är det i praktiska RSA -implementeringar vanligt att bädda in någon form av strukturerad, randomiserad stoppning före kryptering. Detta säkerställer att innehållet inte faller inom området för osäker klartext och att meddelandet inte kan avslöjas genom slumpmässigt urval.
Säkerheten för RSA -kryptosystemet och informationskryptering är baserade på två matematiska problem: problemet med factoring av stora siffror och RSA -problemet i sig. Fullständig avslöjande av chiffertexten och EDS i RSA anses oacceptabelt under antagandet att båda dessa problem inte kan lösas tillsammans.
Men tack vare möjligheten att återställa primära faktorer kan en angripare beräkna den hemliga indikatorn från den offentliga nyckeln och sedan dekryptera texten med standardprocedur. Trots att det idag inte finns någon metod för att faktorisera stora tal på en klassisk dator, har det inte bevisats att den inte existerar.
Automatisering
Ett verktyg som heter Yafu kan användas för att effektivisera denna process. Automation i YAFU är en modern funktion som kombinerar faktoriseringsalgoritmer i en intelligent och adaptiv metodik som minimerar tiden för att hitta faktorer för godtyckliga inmatningsnummer. De flesta implementeringar av algoritmen är flertrådade, vilket gör att Yafu kan dra full nytta av multi- eller multi-threading (inklusive SNFS, SIQS och ECM). Först och främst är det ett hanterat kommandoradsverktyg. Tiden det tar att hitta krypteringsfaktorn med Yafu på en vanlig dator kan reduceras till 103,1746 sekunder. Verktyget bearbetar 320 bitar eller mer. Det är mycket komplex programvara som kräver en viss teknisk skicklighet för att installera och konfigurera. Således kan RSA -kryptering C vara sårbar.
Hackningsförsök i modern tid
År 2009 arbetade Benjamin Moody med en RSA-512-bitarsnyckel med att dekryptera en kryptotext i 73 dagar med endast känd programvara (GGNFS) och en genomsnittlig stationär dator (Athlon64 dual-core vid 1900 MHz). Som framgår av denna erfarenhet tog det lite mindre än 5 gigabyte disk och cirka 2,5 gigabyte RAM -minne för "siktning" -processen.
Från och med 2010 var det största faktoriserade RSA-antalet 768 bitar långt (232 decimaler eller RSA-768). Dess avslöjande varade två år på flera hundra datorer samtidigt.
I praktiken är RSA -nycklar långa, vanligtvis från 1024 till 4096 bitar. Vissa experter tror att 1024-bitars nycklar kan bli opålitliga inom en snar framtid, eller till och med redan äventyras av en ganska välfinansierad angripare. Men få skulle hävda att 4096-bitars nycklar också skulle kunna avslöjas inom överskådlig framtid.
Perspektiv
Därför antas det generellt att RSA är säkert om siffrorna är tillräckligt stora. Om huvudnumret är 300 bitar eller mindre kan chiffertexten och EDS sönderdelas inom några timmar på en persondator med hjälp av programvara som redan är fritt tillgänglig. 512-bitars nycklar visade sig kunna krackas redan 1999 med flera hundra datorer. Detta är möjligt dessa dagar i flera veckor med hjälp av allmänt tillgänglig hårdvara. Således är det fullt möjligt att RSA -kryptering i framtiden lätt bryts på fingrarna och systemet kommer att bli hopplöst föråldrat.
Officiellt 2003 ifrågasattes säkerheten för 1024-bitars nycklar. Det rekommenderas för närvarande att vara minst 2048 bitar långt.
Elektronisk digital signatur (EDS) är ett elektroniskt dokument som krävs för att certifiera datakällan och skydda detta elektroniska dokument från förfalskning.
Allmänt schema
Ett elektroniskt signaturschema innehåller vanligtvis:
- algoritm för att generera användarnyckelpar;
- funktionen att beräkna signaturen;
- signaturverifieringsfunktion.
Funktionen att beräkna signaturen baserat på dokumentet och användarens privata nyckel beräknar den faktiska signaturen. Beroende på algoritmen kan funktionen för beräkning av signaturen vara deterministisk eller sannolik. Deterministiska funktioner beräknar alltid samma signatur från samma ingång. Sannolikhetsfunktioner lägger till ett element av slumpmässighet till signaturen, vilket ökar EDS -algoritmernas kryptografiska styrka. Sannolikhetsscheman kräver emellertid en pålitlig slumpkälla (antingen en hårdvarubrusgenerator eller en kryptografiskt tillförlitlig pseudo-slumpbitgenerator), vilket komplicerar implementeringen.
För närvarande används deterministiska system praktiskt taget inte.
Signaturverifieringsfunktionen kontrollerar om den givna signaturen matchar det givna dokumentet och användarens offentliga nyckel. Användarens offentliga nyckel är tillgänglig för alla, så vem som helst kan verifiera signaturen på detta dokument.
Eftersom dokumenten som ska signeras är av variabel (och ganska lång) längd, i EDS -system, placeras signaturen ofta inte på själva dokumentet, utan på dess hash. Hashen beräknas med kryptografiska hashfunktioner för att säkerställa att dokumentändringar upptäcks när signaturen verifieras. Hashfunktioner är inte en del av EDS -algoritmen, så vilken tillförlitlig hash -funktion som helst kan användas i schemat.
säkerhet
En digital signatur ger:
- Identiteten på dokumentets källa. Beroende på detaljerna i dokumentdefinitionen kan fält som "författare", "ändringar som gjorts", "tidsstämpel", etc. undertecknas.
- Skydd mot dokumentändringar. Varje oavsiktlig eller avsiktlig ändring av dokumentet (eller signaturen) kommer att ändra hash, därför blir signaturen ogiltig.
- Omöjlighet att vägra författarskap. Eftersom du bara kan skapa en korrekt signatur om du känner till den privata nyckeln, och den är endast känd för ägaren, kan ägaren inte vägra sin signatur på dokumentet.
Följande digitala signaturhot är möjliga:
- En angripare kan försöka förfalska en signatur för ett valfritt dokument.
- En angripare kan försöka matcha ett dokument med en given signatur så att signaturen matchar den.
- En angripare kan försöka skapa en signatur för ett dokument.
När du använder en tillförlitlig hash -funktion är det beräknat svårt att skapa ett falskt dokument med samma hash som det äkta. Dessa hot kan dock realiseras på grund av svagheterna hos specifika hashalgoritmer, signaturer eller fel i deras implementering.
Ändå är sådana hot mot digitala signatursystem fortfarande möjliga:
- En angripare som stal en privat nyckel kan underteckna alla dokument för nyckelns ägare.
- En angripare kan lura ägaren att signera ett dokument, till exempel med protokollet för blind signatur.
- En angripare kan ersätta ägarens offentliga nyckel (se nyckelhantering) med sin egen, efterlikna den.
EDS -algoritmer
- Amerikanska standarder för elektronisk digital signatur: DSA, ECDSA
- Ryska standarder för elektronisk digital signatur: GOST R 34.10-94 (för närvarande ej giltig), GOST R 34.10-2001
- Ukrainsk standard för elektronisk digital signatur: DSTU 4145-2002
- PKCS # 1 -standarden beskriver i synnerhet ett elektroniskt digitalt signaturschema baserat på RSA -algoritmen
Nyckelhantering
Ett viktigt problem i all offentlig nyckelkryptografi, inklusive EDS -system, är hanteringen av offentliga nycklar. Det är nödvändigt att säkerställa att alla användare får tillgång till den äkta offentliga nyckeln för någon annan användare, för att skydda dessa nycklar från att ersättas av en inkräktare, och också att organisera återkallelsen av nyckeln vid en kompromiss.
Problemet med att skydda nycklar från substitution löses med hjälp av certifikat. Med certifikatet kan du verifiera uppgifterna om ägaren och hans offentliga nyckel med signaturen av en betrodd person. Centraliserade certifikatsystem (t.ex. PKI) använder certifieringsmyndigheter som stöds av betrodda organisationer. I decentraliserade system (till exempel PGP) byggs ett nätverk av förtroende upp av varje användare genom korssigneringscertifikat för vänner och betrodda människor.
Certifikatdistributionscentra ansvarar för nyckelhantering. Genom att kontakta ett sådant center kan användaren erhålla ett certifikat för vilken användare som helst och även kontrollera om denna eller den offentliga nyckeln har återkallats.
Beskrivning av RSA -algoritmen
RSA- kryptografisk algoritm för offentlig nyckel. RSA var den första i sitt slag, lämplig för både kryptering och digital signatur. Algoritmen används i ett stort antal kryptografiska applikationer.
Historia
Den brittiska matematikern Clifford Cocks, som arbetade vid UK Government Communications Center (GCHQ), beskrev ett liknande system 1973 i centrumets interna dokument, men detta arbete avslöjades inte förrän 1977 och Rivest, Shamir och Adleman utvecklade RSA oberoende av arbetet Cox.
År 1983 beviljades MIT amerikanskt patent 4 405 829, som löpte ut den 21 september 2000.
Algoritm Beskrivning
RSA -algoritmens säkerhet baseras på svårighetsgraden av faktoriseringsproblemet. Algoritmen använder två nycklar - offentliga och privata, tillsammans utgör de offentliga och motsvarande privata nycklar ett tangentbord. Den offentliga nyckeln behöver inte hållas hemlig; den används för att kryptera data. Om meddelandet krypterades med en offentlig nyckel kan det bara dekrypteras med motsvarande hemliga nyckel.
Genererar nycklar
För att generera ett nyckelpar utförs följande åtgärder:
1. Två stora primtal väljs och
2. Deras produkt beräknas
3. Euler -funktionen beräknas
4. Ett heltal väljs så att 
och brottslighet med
5. Med hjälp av den utökade euklidiska algoritmen hittas ett tal så att
Nummer och används som chiffertext. För att dekryptera måste du beräkna
Det är lätt att se till att när vi dekrypterar kommer vi att återställa det ursprungliga meddelandet:
Från villkoret
följer det
för något heltal, därför
Enligt Eulers sats:
Några funktioner i algoritmen
Generera primtal
För att hitta två stora primtal och, när du skapar en nyckel, används vanligtvis probabilistiska enkelhetstest av tal, som gör att du snabbt kan identifiera och kasta sammansatta tal.
· Med ett litet värde på en öppen indikator (till exempel) är en situation möjlig när det visar sig att. Sedan, och inkräktaren kan enkelt återställa det ursprungliga meddelandet genom att beräkna roten till graden från.
· Eftersom RSA är en deterministisk algoritm, dvs. använder inte slumpmässiga värden i processen, då kan angriparen använda attacken med den markerade klartexten.
För att lösa de listade problemen kompletteras meddelandena före varje kryptering med ett slumpmässigt värde - salt. Fyllningen utförs på ett sådant sätt att det säkerställs och. Dessutom, eftersom meddelandet kompletteras med slumpmässig data, kommer vi vid varje kryptering av samma klartext att få ett annat krypteringsvärde varje gång, vilket gör en attack med den valda klartexten omöjlig.
Väljer värdet för en öppen indikator
RSA är betydligt långsammare än symmetriska algoritmer. För att öka krypteringshastigheten väljs den öppna exponenten liten, vanligtvis 3, 17 eller 65537. Dessa siffror i binär form innehåller bara två enor, vilket minskar antalet multiplikationer som krävs vid höjning till en effekt. Till exempel, för att höja ett tal till makt 17 behöver du bara utföra fem multiplikationsoperationer:
ska vara tillräckligt stor. 1990 visade Michael J. Wiener att om man väljer litet så visar det sig vara tillräckligt stort och det är inga problem.
Nyckellängd
siffra n måste vara minst 512 bitar stora. För närvarande anses det RSA-baserade krypteringssystemet vara tillförlitligt från storlek N på 1024 bitar.
RSA -ansökan
RSA används för programvaruskydd och system för digitala signaturer. Det används också i det öppna krypteringssystemet PGP.
På grund av den låga krypteringshastigheten (cirka 30 kbps med en 512-bitars nyckel på en 2 GHz-processor) krypteras meddelanden vanligtvis med effektivare symmetriska algoritmer med en slumpmässig nyckel ( sessionsnyckel), och endast den här nyckeln är krypterad med RSA.
II. Genomförande
Till exempel implementerades ett program för digital signering av filer och verifiering av signaturer. RSA -algoritmen och X.509 -certifikat användes. Användarcertifikatet hämtas från Windows -certifikatlagret.
Digitala signaturer sparas i en xml -fil med namnet<имя исходного файла>.sig.xml
Kodavsnitt
offentlig klass Signatur
privat X509Certificate2 -certifikat;
privat DateTime date;
privat byte signeradHash;
offentligt X509Certificate2 -certifikat
få (returcertifikat;)
set (certifikat = värde;)
public DateTime Date
get (returdatum;)
set (datum = värde;)
public void Sign (stränginmatning, X509Certificate2 cert)
this.certificate = nytt X509Certificate2 (cert);
date = DateTime.Now;
signedHash = ((RSACryptoServiceProvider) cert.PrivateKey) .SignData (Utils.StringToBytes (stringToEncrypt), ny MD5CryptoServiceProvider ());
public bool IsValid (string input)
string stringToEncrypt = input + date.Ticks;
return ((RSACryptoServiceProvider) certificate.PublicKey.Key) .VerifyData (Utils.StringToBytes (stringToEncrypt), new MD5CryptoServiceProvider (), signedHash);
offentlig byte SignedHash
get (retur signeradHash;)
set (signeradHash = värde;)
void DisplaySignatureList ()
FileSignatures fileSignatures = ReadSignatures (GetSignaturesFileName (fileNameTextBox.Text));
signatureListTextBox.Text = "";
foreach (Signatur signatur i fileSignatures.Signaures)
strängrad = "";
rad + = signaure.Certificate.Subject;
rad + = "" + signaure.Date.ToString ();
string hash = GetFileHash (fileNameTextBox.Text);
bool valid = signaure.IsValid (hash);
rad = "v" + rad;
rad = "x" + rad;
signatureListTextBox.Text + = rad + "\ r \ n";
III. Litteratur
- S. Burnet, S. Payne: Kryptografi. RSA Security Official Guide - M. Binom, 2002
- V. Zima: Säkerhet för global nätverksteknik - "BHV -Petersburg", 2003
- Venbo Mao Modern Cryptography: Theory and Practice = Modern Cryptography: Theory and Practice. -M.: "Williams", 2005.-S. 768. ISBN 0-13-066943-1
- Nils Ferguson, Bruce Schneier Praktisk kryptografi: Designa och implementera säkra kryptografiska system. -M.: "Dialektik", 2004.-S. 432. ISBN 0-471-22357-3
- Schneier, Bruce. Tillämpad kryptografi. Protokoll, algoritmer, källtexter på C -språket - M.: Förlag TRIUMPH, 2002 - 816s .: Ill. ISBN 5-89392-055-4
Tänk på arbetet med en asymmetrisk RSA ... Det föreslogs av tre matematiker Ronald Rivest ( R. Rivest), Adi Shamir ( A. Shamir) och Leonard Adlman ( L. Adleman) 1978.
Under primtal vi kommer att förstå ett tal som bara är delbart med 1 och av sig självt. Euklid i sina "Elements" visade att för alla primtal finns det ett större primtal, det vill säga antalet primtal är oändligt.
Bevis. Låt oss säga att det finns ett största primtal sid, definiera produkten av alla primtal P=2∙3∙5∙7∙…∙sid.
Tänk på numret P+1. Det är i sig ett primtal stort sid eller produkten av primtal som är större än P... Vi har kommit till en motsättning, så antalet primtal är oändligt.
2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;
2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.
Ömsesidigt primtal vi kommer att ringa sådana nummer som inte har någon gemensam delare, förutom 1 .
Slutligen, under resultatet av operationen jag mod j vi kommer att överväga resten av heltalet i på j. För att använda RSA -algoritmen måste du först generera de offentliga och privata nycklarna genom att följa stegen nedan.
1. Välj två mycket stora primtal R och q.
2. Definiera n som ett resultat av multiplikation R på q (n = p q).
3. Välj ett stort slumpmässigt nummer, som vi kommer att ringa d... Detta nummer måste vara coprime med resultatet av multiplikation (p - 1) (q - 1).
4. Låt oss definiera ett sådant tal e för vilket följande förhållande är sant (e d) mod ((p - 1) (q - 1)) = 1.
5. Låt oss ringa numren e och n, och den hemliga nyckeln är siffrorna d och n.
Nu, för att kryptera data med en känd nyckel ( e, n) måste du göra följande:
- dela den krypterade texten i block, som alla kan representeras som ett nummer M (i);
- kryptera text som betraktas som en sekvens av siffror M (i) enligt formeln С (i) = (M (i) e) mod n... För att dekryptera dessa data med den hemliga nyckeln (d, n), du måste utföra följande beräkningar: M (i) = (C (i) d) mod n... Resultatet blir en uppsättning siffror M (i), som representerar originaltexten.
Algoritm RSA är baserad på en av de bevisade Euler -satserna, vars specialfall anger att om antalet n representeras som två primtal sid och q, då för valfri x jämlikheten håller
x (p-1) (q-1) mod n = 1.
Låt oss använda denna formel för att dekryptera RSA -meddelanden. För att göra detta höjer vi båda dess delar till makten (- y):
(x (-y) (p-1) (q-1)) mod n= 1 (- y) = 1.
Låt oss nu multiplicera båda sidor med x:
(x (-y) (p-1) (q-1) +1) mod n = 1· x = x.
Låt oss nu komma ihåg hur de offentliga och privata nycklarna skapades. Vi valde d Så att
e d + (p-1) (q-1) y = 1,
e d = (-y) (p-1) (q-1) +1.
Därför kan vi i det sista uttrycket i föregående stycke ersätta exponenten med talet (e d). Vi får (x e d) mod n = x... För att läsa meddelandet c i = ((m i) e) mod n det räcker för att höja det till makten d modulo m:
((c i) d) mod n = ((m i) e d) mod n = m i.
Här är ett enkelt exempel på att använda RSA -metoden för att kryptera ett CAB -meddelande. För enkelhetens skull kommer vi att använda mycket små tal (i praktiken används stora siffror).
1. Låt oss välja p = 3och q = 11.
2. Definiera n = 3· 11=33.
3. Hitta (p - 1) (q - 1) = 20. Som d välj valfritt nummer som är koprime med 20, till exempel d = 3.
4. Välj ett nummer e... Som ett sådant nummer kan valfritt tal tas för vilket förhållandet (e 3) mod 20 =
1,
till exempel 7.
5. Låt oss representera det krypterade meddelandet som en sekvens av heltal i intervallet 0 ... 32. Låt brevet A representeras av siffran 1, bokstaven V- siffran 2 och bokstaven MED- nummer 3. Då kan meddelandet representeras som en sekvens av siffror 312. Låt oss kryptera meddelandet med nyckeln (7, 33):
С (1) = (З 7) mod 33 = 2187 mod 33 = 9,
С (2) = (1 7) mod 33 = 1 mod 33 = 1,
С (З) = (2 7) mod 33 = 128 mod 33 = 29.
6. Låt oss försöka dekryptera meddelandet (9, 1, 29), som erhållits som ett resultat av kryptering med en känd nyckel, baserat på den hemliga nyckeln (3, 33):
M (1) = (9 3) mod 33 = 729 mod 33 = 3,
М (2) = (1 3) mod 33 = 1 mod 33 = 1,
M (Z) = (29 3) mod 33 = 24389 mod 33 = 2.
Som ett resultat av dekryptering av meddelandet tas det ursprungliga "CAB" -meddelandet emot.
RSA -algoritmens kryptografiska styrka är baserad på antagandet att det är extremt svårt att bestämma den hemliga nyckeln från den kända offentliga, eftersom det för detta är nödvändigt att lösa problemet med förekomsten av heltalsdelare. Detta problem medger för närvarande inte en effektiv (polynom) lösning. I detta avseende, för nycklar som består av 200 binära siffror (och det är dessa siffror som rekommenderas att använda), kräver traditionella metoder för att hitta delare ett stort antal operationer (cirka 10 23).
RSA -kryptosystemet används i en mängd olika plattformar och i många branscher. Det är inbäddat i många fler och fler kommersiella produkter. Det används av Microsoft, Apple, Sun och Novell operativsystem. I hårdvara används RSA -algoritmen i säkra telefoner, på Ethernet -nätverkskort, på smartkort och används ofta i kryptografisk utrustning från Zaxus (Rasal). Dessutom ingår algoritmen i alla större protokoll för säker internetkommunikation, inklusive S / MIME, SSL och S / WAN, och används också i många institutioner, till exempel i statliga tjänster, i de flesta företag, i statliga laboratorier och universitet ....
RSA BSAFE -krypteringsteknik används av mer än 500 miljoner användare runt om i världen. Eftersom RSA -algoritmen i de flesta fall används kan den anses vara det vanligaste offentliga nyckelkryptosystemet i världen, och detta antal har en tydlig tendens att öka när Internetanvändare växer.
RSA -kryptosystemet vid varje krypteringscykel transformerar ett binärt block i klartext m med längdstorlek (n), betraktat som ett heltal, i enlighet med formeln: c = m e (mod n).
Dessutom är n = pq , där p och q är slumpmässiga stora siffror som förstörs efter att modulen och nycklarna har genererats. Den offentliga nyckeln består av ett par nummer e och n . Undernyckel e väljs som ett tillräckligt stort antal från intervall 1< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Vidare löser ekvationen xe + yφ (n) = 1 i heltal x, y, d = x, dvs. ed = 1 (j (n)). Dessutom är förhållandet m ed = m (n) för alla m , därför tillåter kunskap om d att dekryptering av kryptogram.
För att säkerställa tillförlitlig informationssäkerhet finns det två krav för offentliga nyckelsystem.
1. Transformationen av originaltexten bör utesluta att den återställs baserat på den offentliga nyckeln.
2. Att bestämma den privata nyckeln utifrån den offentliga nyckeln måste också vara beräknat orealiserbar. I detta fall är en exakt nedre gräns för komplexiteten (antalet operationer) för chifferbeskrivningen önskvärd.
Krypteringsalgoritmer för allmänna nycklar används i stor utsträckning i moderna informationssystem.
Låt oss överväga konstruktionen av ett RSA -kryptosystem med ett enkelt exempel.
1. Välj p = 3 och q = 11.
2. Låt oss definiera n = 3 ∙ 11 = 33.
3. Hitta j (n) = (p - 1) (q - 1) = 20.
5. Välj ett nummer d som uppfyller 7d = 1 (mod 20).
Det är lätt att se att d = 3 (mod 20).
Vi representerar det krypterade meddelandet som en sekvens av heltal med hjälp av korrespondensen: A = 1, B = 2, C = 3, ..., Z = 26. Eftersom storlek (n) = 6 , då kan vårt kryptosystem kryptera bokstäverna i det latinska alfabetet, betraktat som block. Låt oss publicera den offentliga nyckeln (e, n) = (7, 33) och bjuda in andra deltagare i det hemliga kommunikationssystemet att kryptera meddelanden som skickas till adress med den. Låt ett sådant meddelande vara CAB , som i den kodning vi valt har formen (3, 1, 2). Avsändaren måste kryptera varje block och skicka ett krypterat meddelande till vår adress:
RSA (C) = RSA (3) = 37 = 2187 = 9 (mod 33);
RSA (A) = RSA (1) = 17 = 1 (mod 33);
RSA (B) = RSA (1) = 27 = 128 = 29 (mod 33).
Efter att ha mottagit det krypterade meddelandet (9, 1, 29) kan vi dekryptera det baserat på den hemliga nyckeln (d, n) = (3, 33) och höja varje block till effekten d = 3:
9 3 = 729 = 3 (mod 33);
13 = 1 (mod 33);
29 3 = 24389 = 2 (mod 33).
För vårt exempel är det lätt att brute-force den hemliga nyckeln. I praktiken är detta inte möjligt, eftersom För praktisk användning rekommenderas följande värden för närvarande storlek (n) :
· 512-768 bitar - för individer;
· 1024 bitar - för kommersiell information;
2048 bitar - för sekretessbelagd information.
Ett exempel på implementering av RSA -algoritmen visas i listorna 18.1 och 18.2 (kompilatorer - Delphi, FreePascal).
Notering 18.1. Ett exempel på implementering av RSA -algoritm på Pascal -språk
program Rsa;
($ APPTYPE CONSOLE)
($ IFDEF FPC)
($ MODE DELPHI)
($ ENDIF)
använder SysUtils, uBigNumber;
// Slumpgenerator
var t: array av Byte;
var pos: Integer;
var cbox: array av Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);
procedur InicMyRandom;
var i: Integer;
var s: string;
Börja
WriteLn ("Skriv in lite text för att initiera generatorn
slumpmässiga tal (upp till 256 tecken): ");
ReadLn (s);
i: = 1;
medan jag<=255) and (i<=Length(s)) do
RSA använder två typer av nycklar - e och d, där e är offentligt och d är hemligt. Antag att P är originaltexten och C är chiffertexten. Alice använder C = P e mod n för att skapa chiffertext C från originaltexten P; Bob använder P = C d mod n för att extrahera originaltexten (filen) som skickats av Alice. Ett mycket stort antal n -moduler skapas med hjälp av nyckelgenereringsprocessen, som vi kommer att diskutera senare.
För kryptering och dekryptering används exponentieringsmodul. Som vi diskuterade i föreläsningar 12-13 är modulo-exponentiering genomförbar vid polynomtid när man använder den snabba algoritmen. Att hitta den modulära logaritmen är dock lika svårt som att expandera ett tal i modul. Det finns ingen polynomisk tidsalgoritm för det. Det betyder att Alice kan kryptera meddelandet med den offentliga nyckeln (e) vid polynomtid. Bob kan också dekryptera det på polynomtid (eftersom han vet d). Men Eve kan inte dechiffrera detta meddelande eftersom hon skulle behöva beräkna den e: e roten av C med hjälp av modulär aritmetik. Figur 14.5 visar tanken bakom RSA.
Ris. 14.5.
Med andra ord använder Alice enkelriktad funktion(exponentiation modulo) med ett kryphål som Bob bara känner till. Eve känner inte till kryphålet, så hon kan inte dechiffrera budskapet. Om en dag en polynomalgoritm hittas för modulen för beräkning av den e: e roten av n, kommer exponentieringsmodul n inte längre att vara en envägsfunktion.
Procedur
Figur 14.6 visar den allmänna idén om proceduren som används i RSA.
RSA använder exponentiering för kryptering / dekryptering. För att attackera den slutna texten måste Eve beräkna 
Ris. 14.6.
Två algebraiska strukturer
RSA använder två algebraiska strukturer: ring och grupp.
Krypterings- / dekrypteringsringar... Kryptering och dekryptering görs med hjälp av en kommutativ ring 
med två räkneoperationer: addition och multiplikation. I RSA är denna ring allmänt tillgänglig eftersom modul n är allmänt tillgänglig. Vem som helst kan skicka ett meddelande till Bob med denna krypteringsring.
Nyckelgenerationsgrupper... RSA använder multiplikativ grupp 
för att generera nycklar. Gruppen stöder endast multiplikation och division (multiplikativ invers), som är nödvändiga för att skapa offentliga och privata nycklar. Denna grupp måste döljas eftersom dess modul är hemlig. Vi kommer att se att om Eve hittar den här modulen kan hon enkelt attackera det kryptografiska systemet.
RSA använder två algebraiska strukturer: öppen ring R =< Z n , +, x> och den hemliga gruppen G =< Z (n) * , x>.
Genererar nycklar
Bob använder stegen som visas i algoritm 14.2 för att skapa sina offentliga och privata nycklar. Efter att ha genererat nycklarna förklarar Bob tupeln (e, n) som sin offentliga åtkomstnyckel: Bob lagrar d som sin privata nyckel. Bob kan släppa p, q och; de kan inte ändra sin privata nyckel utan att ändra modulen. För säkerhets skull är den rekommenderade storleken för varje prim p eller q 512 bitar (nästan 154 decimaler). Detta definierar enhetens storlek, n 1024 bitar (309 siffror).
I RSA är tupeln (e, n) den allmänna åtkomstnyckeln; heltal d - hemlig nyckel.
Kryptering
Vem som helst kan skicka ett meddelande till Bob med sin offentliga åtkomstnyckel. Kryptering i RSA kan göras med en polynomisk tidskomplexitetsalgoritm, som visas i algoritm 14.3. En snabb exponentieringsalgoritm diskuterades i föreläsningarna 12-13. Storleken på källtexten måste vara mindre än n; om källtextens storlek är större, bör den delas upp i block.