Algoritem šifriranja rsa 3072. Elektronski digitalni podpis, algoritem RSA

elektronski digitalni podpis(EDS) je atribut elektronskega dokumenta, ki je namenjen potrditvi vira podatkov in zaščiti tega elektronskega dokumenta pred ponarejanjem.

Splošna shema

Shema elektronskega podpisa običajno vključuje:

• algoritem za generiranje parov uporabniških ključev;
• funkcija izračuna podpisa;
• funkcija preverjanja podpisa.

Funkcija izračuna podpisa na podlagi dokumenta in skrivnega ključa uporabnika izračuna dejanski podpis. Funkcija izračuna podpisa je lahko deterministična ali verjetnostna, odvisno od algoritma. Deterministične funkcije vedno izračunajo isti podpis z enakim vhodom. Verjetnostne funkcije uvajajo element naključnosti v podpis, kar poveča kriptografsko moč algoritmov EDS. Vendar verjetnostne sheme zahtevajo zanesljiv vir naključnosti (bodisi generator strojne opreme ali kriptografsko zanesljiv generator psevdo-naključnih bitov), ​​kar otežuje izvedbo.

Trenutno se deterministične sheme praktično ne uporabljajo.

Funkcija preverjanja podpisa preveri, ali se podani podpis ujema ta dokument in uporabnikov javni ključ. Uporabnikov javni ključ je javno dostopen, tako da lahko vsakdo preveri podpis na dokumentu.

Ker so dokumenti, ki jih je treba podpisati, spremenljive (in precej velike) dolžine, se v shemah EDS podpis pogosto ne postavi na sam dokument, temveč na njegovo razpršilo. Kriptografske zgoščevalne funkcije se uporabljajo za izračun razpršitve, ki zagotavlja, da so spremembe dokumenta zaznane, ko je podpis preverjen. Hash funkcije niso del algoritma EDS, zato je v shemi mogoče uporabiti katero koli zanesljivo hash funkcijo.

Varnost

Digitalni podpis zagotavlja:

• Identiteta vira dokumenta. Glede na podrobnosti definicije dokumenta se lahko podpišejo polja, kot so »avtor«, »izvedene spremembe«, »časovni žig« itd.
• Zaščita pred spremembami dokumenta. Vsaka sprememba dokumenta (ali podpisa) naključno ali namerno bo spremenila razpršitev in tako razveljavila podpis.
• Nemožnost odrekanja avtorstvu. Ker je pravilen podpis mogoče izdelati le, če je zasebni ključ znan in je znan le lastniku, lastnik njegovega podpisa na dokumentu ne more zavrniti.

Možne so naslednje grožnje z digitalnim podpisom:

• Napadalec lahko poskusi ponarediti podpis za dokument po svoji izbiri.
• Napadalec lahko poskuša uskladiti dokument z danim podpisom, tako da se podpis ujema z njim.
• Napadalec lahko poskuša ponarediti podpis za kakšen dokument.

Pri uporabi zanesljive zgoščevalne funkcije je računsko težko ustvariti ponarejen dokument z enakim zgoščevanjem kot pristni. Vendar pa se te grožnje lahko uresničijo zaradi slabosti v specifičnih algoritmih zgoščevanja, podpisov ali hroščev v njihovih izvedbah.

Vendar pa so še vedno možne naslednje grožnje za sisteme digitalnega podpisa:

• Napadalec, ki ukrade zasebni ključ, lahko podpiše kateri koli dokument v imenu lastnika ključa.
• Napadalec lahko zavede lastnika, da podpiše dokument, na primer z uporabo protokola slepega podpisa.
• Napadalec lahko lastnikov javni ključ (glej upravljanje ključev) zamenja s svojim lastnim in se predstavlja kot on.

Algoritmi EDS

• Ameriški standardi digitalnega podpisa: DSA, ECDSA

• Ruski standardi digitalnega podpisa: GOST R 34.10-94 (trenutno ni veljaven), GOST R 34.10-2001
• Ukrajinski standard za elektronski digitalni podpis: DSTU 4145-2002
• Standard PKCS#1 opisuje zlasti shemo elektronskega digitalnega podpisa, ki temelji na algoritmu RSA

Upravljanje s ključi

Pomemben problem vse kriptografije z javnimi ključi, vključno s sistemi EDS, je upravljanje javnih ključev. Zagotoviti je treba, da ima vsak uporabnik dostop do pristnega javnega ključa katerega koli drugega uporabnika, zaščititi te ključe pred zamenjavo s strani napadalca in poskrbeti za preklic ključa, če je ogrožen.

Naloga zaščite ključev pred zamenjavo se rešuje s pomočjo certifikatov. Certifikat vam omogoča, da s podpisom zaupanja vredne osebe potrdite vsebovane podatke o lastniku in njegovem javnem ključu. Centralizirani sistemi potrdil (kot je PKI) uporabljajo overitelje potrdil, ki jih vzdržujejo zaupanja vredne organizacije. V decentraliziranih sistemih (na primer PGP) z navzkrižnim podpisovanjem potrdil poznanih in zaupanja vrednih ljudi vsak uporabnik zgradi mrežo zaupanja.

Ključe upravljajo organi za distribucijo potrdil. Če se obrne na tak center, lahko uporabnik pridobi potrdilo katerega koli uporabnika in tudi preveri, ali ta ali oni javni ključ še ni bil preklican.

Opis algoritma RSA

RSA je kriptografski algoritem javnega ključa. RSA je bil prvi tovrstni algoritem, primeren tako za šifriranje kot za digitalni podpis. Algoritem se uporablja v velikem številu kriptografskih aplikacij.

Zgodba

Britanski matematik Clifford Cocks, ki je delal v Centru za komunikacije vlade Združenega kraljestva (GCHQ), je leta 1973 opisal podoben sistem v internih dokumentih centra, vendar to delo ni bilo razkrito šele leta 1977 in Rivest, Shamir in Adleman so razvili RSA neodvisno od dela. Cox.

Leta 1983 je MIT izdal ameriški patent 4,405,829, ki je potekel 21. septembra 2000.

Opis algoritma

Varnost algoritma RSA temelji na težavnosti problema faktorizacije. Algoritem uporablja dva ključa - javni (javni) in tajni (zasebni), skupaj pa javni in pripadajoči skrivni ključi tvorijo par ključev (keypair). Javnega ključa ni treba hraniti v tajnosti, uporablja se za šifriranje podatkov. Če je bilo sporočilo šifrirano z javnim ključem, ga je mogoče dešifrirati le z ustreznim zasebnim ključem.

Generacija ključev

Za ustvarjanje para ključev se izvedejo naslednji koraki:

1. Izbrana sta dva velika praštevila in

2. Njihov produkt je izračunan

3. Izračuna se Eulerjeva funkcija

4. Celo število je izbrano tako, da in sorazmerno z

5. Z uporabo razširjenega evklidskega algoritma najdemo število tako, da

Številka in se uporablja kot šifrirano besedilo. Za dešifriranje morate izračunati

Preprosto je videti, da bomo pri dešifriranju obnovili izvirno sporočilo:

Iz stanja

sledi temu

za neko celo število

Po Eulerjevem izreku:

Nekatere značilnosti algoritma

Generacija praštevil

Za iskanje dveh velikih praštevil in pri generiranju ključa se običajno uporabljajo verjetnostni testi števil za preprostost, ki vam omogočajo hitro prepoznavanje in zavrženje sestavljenih številk.

· z majhno vrednostjo indikatorja odprtosti (na primer) je možna situacija, ko se izkaže, da . Nato lahko storilec zlahka obnovi izvirno sporočilo z izračunom korena stopnje iz .

Ker je RSA deterministični algoritem, t.j. ne uporablja naključnih vrednosti med delovanjem, potem lahko napadalec uporabi izbran napad z odprtim besedilom.

Za reševanje teh težav se sporočila pred vsako šifriranjem dopolnijo z neko naključno vrednostjo - soljo. Oblazinjenje je narejeno tako, da se zagotovi, da in . Poleg tega, ker je sporočilo obloženo z naključnimi podatki, bomo s šifriranjem istega odprtega besedila vsakič dobili drugačno vrednost šifriranega besedila, kar onemogoča napad z izbranim odprtim besedilom.

Izbira vrednosti odprtega indikatorja

RSA je veliko počasnejši od simetričnih algoritmov. Za povečanje hitrosti šifriranja je odprti eksponent izbran majhen, običajno 3, 17 ali 65537. Te številke v binarni obliki vsebujejo samo dve enici, kar zmanjša število potrebnih operacij množenja pri dvigu na potenciju. Na primer, če želite število dvigniti na potenco 17, morate izvesti le 5 množenj:

mora biti dovolj velik. Leta 1990 je Michael J. Wiener pokazal, da če je izbran majhen, se izkaže, da je dovolj velik in ni problema.

Dolžina ključa

Številka n mora biti vsaj 512 bitov. Sistemi šifriranja, ki temeljijo na RSA, trenutno veljajo za varne, začenši z velikostjo N 1024 bitov.

Uporaba RSA

Sistem RSA se uporablja za zaščito programske opreme in v shemah digitalnega podpisovanja. Uporablja se tudi v odprt sistemŠifriranje PGP.

Zaradi nizke hitrosti šifriranja (približno 30 kbps s 512-bitnim ključem na 2 GHz procesorju) se sporočila običajno šifrirajo s hitrejšimi simetričnimi algoritmi z naključnim ključem ( ključ seje), s pomočjo RSA pa je šifriran samo ta ključ.

II. Izvajanje

Na primer, implementiran je bil program za digitalno podpisovanje datotek in preverjanje podpisov. Uporabljen je bil algoritem RSA in potrdila X.509. Uporabniško potrdilo je izbrano iz shrambe potrdil Windows.

Digitalni podpisi so shranjeni v xml datoteko Z imenom<имя исходного файла>.sig.xml

Odrezki kode

javni razred Podpis

zasebno potrdilo X509Certificate2;

zasebni datum DateTime;

zasebni bajt podpisan Hash;

javno potrdilo X509Certificate2

pridobi (potrdilo o vračilu; )

set (certifikat = vrednost; )

javni DateTime Datum

dobi (datum vrnitve;)

nastavljen (datum = vrednost;)

javni znak void (vnos niza, potrdilo X509Certificate2)

this.certificate = novo X509Certificate2(cert);

datum = Datum in čas. Zdaj;

signedHash = ((RSACryptoServiceProvider)cert.PrivateKey).SignData(Utils.StringToBytes(stringToEncrypt),nov MD5CryptoServiceProvider());

javni bool IsValid (vnos niza)

niz stringToEncrypt = vnos + datum.Klipi;

vrni ((RSACryptoServiceProvider)certificate.PublicKey.Key).VerifyData(Utils.StringToBytes(stringToEncrypt),nov MD5CryptoServiceProvider(), signedHash);

javni bajt SignedHash

get (vrni signedHash; )

set ( signedHash = vrednost; )

void DisplaySignatureList()

FileSignatures fileSignatures = ReadSignatures(GetSignaturesFileName(fileNameTextBox.Text));

signatureListTextBox.Text = "";

foreach(podpis podpisa v datotekiSignatures.Signaures)

niz vrstica = "";

vrstica+= podpis.Certificate.Subject;

vrstica+=" "+podpis.Datum.ToString();

niz hash = GetFileHash(fileNameTextBox.Text);

bool veljaven = signaure.IsValid(hash);

vrstica = "v" + vrstica;

vrstica = "x" + vrstica;

signatureListTextBox.Text += vrstica+"\r\n";

III. Literatura

1. S. Burnet, S. Payne: Kriptografija. Uradni vodnik Varnost RSA - M. "Binom", 2002
2. V. Zima: Varnost globalnih omrežnih tehnologij - BHV-Peterburg, 2003
3. Wenbo Mao Modern Cryptography: Theory and Practice = Modern Cryptography: Theory and Practice. - M.: "Williams", 2005. - S. 768. ISBN 0-13-066943-1
4. Niels Ferguson, Bruce Schneier Praktična kriptografija: Praktična kriptografija: načrtovanje in implementacija varnih kriptografskih sistemov. - M .: "Dialektika", 2004. - S. 432. ISBN 0-471-22357-3
5. Schneier, Bruce. Uporabna kriptografija. Protokoli, algoritmi, izvorna besedila v jeziku C - M .: Založba TRIUMPH, 2002 - 816 str.: ilustr. ISBN 5-89392-055-4

Ne vsi uporabniki osebnega računalniška tehnologija vedo in razumejo, kaj je šifriranje RSA, in so presenečeni nad zvokom tega izraza. Toda v tem konceptu ni nič zapletenega. Šifriranje RSA je le kriptosistem, ki omogoča varno uporabo vseh elektronskih podatkov, ustvarjenih v računalniški tehnologiji. To ni dešifriranje podatkov, ko datotek ni mogoče prebrati brez poznavanja določene kode. Šifriranje RSA pomeni, da so ključi odprti.

Šifriranje RSA deluje na principu faktoringa. Všečkaj to? In to je faktoring
predvajanje dveh velikih številskih podatkov.

Kdo je ustvaril šifrirni sistem RSA?

Algoritem za šifriranje RSA je bil ustvarjen že leta 1977, njegovi ustvarjalci so znanstveniki Rivest, Shamir, Adleman, okrajšava iz začetnih črk priimkov sestavlja izraz RSA. Prejšnji algoritem je izdelal Clifford Cox, matematik iz Anglije, ki je delal za obveščevalne službe države. Leta 1973 mu je uspelo ustvariti enakovreden sistem, vendar so jo uporabljale izključno tajne osebe, tehnika pa ni bila razporejena na nivoju navadnih uporabnikov osebna računalniška tehnologija.

Kako deluje šifriranje RSA?

Uporabnik sistema najprej ustvari in nato objavi javni ključ, ki temelji na dveh velikih številkah, le s pomožno vrednostjo. Najpreprostejše številke ostajajo skrivnost. Če želite na primer prebrati elektronsko sporočilo, je treba uporabiti samo javni ključ dokumenta, če pa je ključ dolg, pride do težav pri dostopu do informacij.

Danes je šifriranje RSA označeno kot premalo zanesljiv način šifriranja podatkov. To je počasen algoritem, zato med navadnimi uporabniki računalnikov ni tako pogost. Zakaj je bil potem ta sistem ustvarjen, če ga navadni računalničarji praktično ne uporabljajo?

Stvar je v tem, da je našel svojo uporabo pri prenosu v šifrirani obliki javnih ključev za simetrični šifrirni ključ, ki je zasnovan za množično šifriranje in dešifriranje pri visoki hitrosti.

Sodobni kriptosistem asimetričnega ključa se je pojavil zahvaljujoč delu Diffieja in Hellmana. Koncept so razvili leta 1976 in ga predstavili javnosti kot digitalne posnetke. Uspelo jim je ustvariti skupni ključ po principu izpostavljanja določenega števila po modulu praštevila. Toda njihov princip je ostal viseti v zraku, saj v tistem času sami principi faktoringa še niso bili popolnoma raziskani.

Rivest, Adim Shamir, Adleman se niso ustavili pri tem, kar so že dosegli, in so temeljito izdelali mehanizem enosmerne funkcije, ki je ni tako enostavno dekodirati. Rivest in Shamir sta neposredno delala na funkcijah, medtem ko je Adleman iskal šibke točke v ustvarjenih algoritmih. Na koncu jim je uspelo ustvariti asimetrični sistem ključev RSA.

Digitalni podpis in komunikacija z javnimi ključi

Trenutno mnoga podjetja pri svojem delu uporabljajo tak elektronski element kot digitalni podpis. Ustvarjeni elektronski dokumenti, ki vsebujejo tako imenovani digitalni podpis, so uradni dokumenti, priznani na pravni ravni. Elektronski digitalni podpis nastane, ko se podatki kriptografsko spremenijo.

Ta alternativa običajnemu podpisu omogoča zaupnost dokumenta, zagotavlja njegovo celovitost in vedno podatke o njegovem ustvarjalcu in lastniku.

Elektronski podpis je tesno povezan z obravnavanim šifriranjem RSA. Ta sistem, kot je navedeno zgoraj, predpostavlja javni ključ. Danes se v praksi uporabljata dva ključa - odprta - vsem znana in zaprta - šifrirana, da se nepooblaščenim osebam prepreči dostop do informacij.

Tako javni ključ omogoča dostop do dokumenta z elektronskim pečatom, zasebni ključ pa dešifriranje in preverjanje podpisa. Z drugimi besedami, šifriranje RSA vam omogoča, da skrijete dokumente radovedne oči, jih razvrstite, vendar z možnostjo dostopa do njih ob pravem času.

Poglejmo, kaj je bistvo izumljenega algoritma?

Šifriranje RSA deluje v štirih fazah:
generacija ključev;
distribucija ključev;
šifriranje s ključi;
dešifriranje ključa.

Načelo šifriranja RSA združuje ustvarjanje odprtih in zasebni ključi. Še enkrat se zadržimo na tem. Odprto - znano vsem, lahko se uporablja za šifriranje sporočil. Te elektronske podatke je mogoče dešifrirati z zasebnim ključem. Pri ustvarjanju javnih ključev so izbrana naključna števila enake velikosti, vendar različna po trajanju, da oteži faktoring.

Identične številke najdemo s testiranjem njihove primarnosti. Tako je šifriranje postopoma postalo bolj zapleteno. Iz česa je sestavljen javni ključ? In je sestavljen iz rednega modula in tako imenovanega javnega razstavljavca. Toda zaprta vključuje modul in zasebni indikator, ki ni na voljo nikomur razen ustvarjalcu.

Slabosti tehnike šifriranja RSA

Kljub premišljenemu principu šifriranja ga je mogoče zlahka zlomiti. To je mogoče storiti, če so bila za ustvarjanje ključev uporabljena majhna števila, ključ pa je mogoče razkriti s preprostim izborom preprostih celih števil.

Samo šifriranje RSA je algoritem, ki izključuje naključne komponente, kar goljufom olajša računalniško omrežje zlomijo deterministični mehanizem tako, da ga primerjajo z odprtim besedilom napada dos, ki preverja, ali so zagnana besedila vztrajno enaka dolžini ustvarjenih ključev.

In to najprej pojasnjuje, da šifriranje RSA ni isti kriptosistem, ki je v vseh pogledih varen za shranjevanje elektronskih podatkov pred napadi nezaželenih oseb. Razen če, ko je dodan v naprednejše strežnike, pridobi takšne lastnosti.

Dodatne komponente, ki zagotavljajo varnost uporabe šifriranja RSA

Da bi preprečili možnost vdora v šifriranje formata RSA, programerji vanj vgradijo obliko strukturiranega, tako imenovanega naključnega polnjenja, to se izvede pred dejanskim šifriranjem elektronskih informacij. Ta trenutek zagotavlja, da vsebina elektronskih dokumentov ne bo predstavljena vsem, ki niso leni, da si zaupnih informacij ne bo mogoče ogledati pri uporabi mehanizma naključnega izbora ključev za dokumente.

Šifriranje RSA razgradi matematične številke na faktorje, vendar mehanizem ni bil doveden do popolnosti. Zato imajo v tem trenutku napadalci še vedno priložnost in številne vrzeli pri izbiri metod za razbijanje šifriranja podatkov. In prav mehanizem okrevanja primarnih dejavnikov jim to uspe.

Goljufi izračunajo tajno vrednost, ki jo vsebuje javni ključ, in po standardni metodi dešifrirajo dokumentacijo. Področje delovanja za tiste, ki res želijo škodovati nekemu podjetju, je torej bistveno veliko. Naj povemo, da je problem varnosti šifriranja RSA še vedno aktualen in odprt, čeprav malokdo o tem javno govori.

Avtomatiziran proces šifriranja elektronskih podatkov

Kljub nizki oceni varnosti je zadevno šifriranje RSA uporabno v številnih panogah. Še posebej je dobrodošel pri veliki nakladi elektronske dokumentacije. Recimo, da se šifriranje RSA uporablja za zaščito dokumentov na srednji ravni odgovornosti.

Programska oprema Yafu vam omogoča samodejno šifriranje elektronskih podatkov. Ta program vam omogoča hitro iskanje podatkov za ustvarjanje asimetričnih ključev ob upoštevanju pravil faktorske zanesljivosti. Kombinira se pri delu s procesorji, kot so SIQS, ECM, SNFS. Zažene se skozi ukazna vrstica. Uvedba tega ukaza v niz vam omogoča, da večkrat zmanjšate čas, potreben za iskanje podatkov za ustvarjanje ključev.

Povprečen uporabnik osebne računalniške opreme s to programsko opremo ne bo kos. Za njegovo namestitev in konfiguracijo je potrebno določeno znanje in to pogosto počnejo IT programerji in strokovnjaki.

Šifriranje RSA je resno ranljivo, kljub dejstvu, da se za ustvarjanje javnih in zasebnih ključev uporablja veliko število, ki znaša nekaj tisoč bitov na diskih.

Benjamin Moody je leta 2009 dokazal, da je proces vdora javnih in zasebnih ključev možen. Čeprav to lahko traja dve leti ali več, ostaja dejstvo, da je lahko veliko svetovnih računalniških sistemov v nevarnosti, da bodo vdrti.

Ta strokovnjak na primer ni potreboval nič posebnega za prebiranje ključnih skriptov - navaden računalnik uporabnik in programsko opremo GGNFS. Tudi praksa več tisoč-bitnih šifrirnih ključev ne ščiti informacij pred tem, da bi polje zapustilo zaupno in nedostopno drugim uporabnikom.

Seveda je za zlom šifriranja RSA potreben čas. Mnogi hekerji potrebujejo leta, da dosežejo pozitiven rezultat. Pogosto so to visoko plačani obeti, ki spodbujajo zanimanje za nadaljnje iskanje pravega ključa. V večini primerov se pokanju dolgih tipk opustijo v korist lažjih možnosti. Vendar to ne pomeni, da nihče ne poskuša ustvariti bolj poenostavljenega mehanizma za razbijanje ključev.

Glavna zaščita pred vsiljivimi napadi goljufov je ustvarjanje velikih in dolgih ključev več kot dva tisoč bitov. Znani so že primeri pokanja ključev z dolžino od sto do petsto bitov. Zato morate imeti ušesa ostra. Če obstaja mehanizem za razbijanje kratkih ključev, potem je verjetno delo v polnem teku nekje na strani slabovoljcev, da bi razbili najdaljše šifrirne kombinacije elektronskih podatkov.

Zaključek

Na podlagi navedenega je šifriranje RSA varna metoda ohranjanja zaupnosti elektronskih podatkov, pod pogojem, da se ustvarijo dolgi in informacijsko obsežni ključi.

Težko jih je izbrati ročno, zato avtomatizirano programsko opremo Yafu. Namestijo in konfigurirajo ga IT strokovnjaki. Samostojno delo lahko privede do zloma operacijski sistem računalnik.
Ta programska oprema je zasnovana za delo v tandemu z današnjimi večjedrnimi računalniškimi procesorji.

Glavni predmeti goljufivih napadov so velika industrijska in finančna podjetja, zato brez šifriranja RSA njihovo elektronsko upravljanje dokumentov ne deluje. Elektronski podpis dokumentov je prav tako predmet šifriranja in zanj veljajo enaki varnostni standardi kot za druge informacijske podatke. Načelo – večji kot je ključ, težje je razbiti dokument – ​​bi moralo veljati za popolnoma vse podatke, ki niso namenjeni javni uporabi.

Pod rezom so opisani primeri izbire "slabih" parametrov šifre RSA.

»Poudariti je treba, da je treba paziti pri izbiri modula RSA (številke n) za vsakega dopisnika omrežja. V zvezi s tem je mogoče reči naslednje. Bralec lahko to samostojno preveri, če pozna eno od treh količin str, q oz φ(n), lahko zlahka najdete skrivni ključ RSA ...«.

Dodajmo to besedilo. Če je izbira modula šifriranja RSA neuspešna, kot je to storjeno v spodnjem primeru vadnice, je možno besedilo dešifrirati brez prisotnosti tajnega ključa, t.j. ne da bi poznali katero koli od treh imenovanih količin.

Za to je dovolj, da imamo šifrirano besedilo, ki ga poda šifrirni modul n, javni ključ ešifrirati in izvesti samo tri korake napada "branje brez ključa". Po četrtem napadalnem koraku se ugotovi, da je bilo izvorno besedilo prejeto v prejšnjem koraku, ga je mogoče brati. Pokažimo, kako enostavno je to narediti.

Najprej navedemo sam primer s str. 313-315 iz omenjenega priročnika.

Primer

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

V kolikor –137≡343(mod480), potem d=343.

izpit: 7∙343=2401≡1(mod480).

Besedilno sporočilo je predstavljeno kot zaporedje številk, ki jih vsebuje interval . Za to pismo R, S in A kodirano kot 5-bitna binarna števila. Zaporedne številke teh črk v angleški abecedi se uporabljajo v njihovi binarni predstavitvi:

R=18 10 = (10010) 2, S=19 10 =(10011) 2,
A=1 10 = (00001) 2.

Potem RSA=(100101001100001) 2. Če besedilo razdelite na bloke omejene dolžine, dobite predstavitev dveh blokov: RSA=(100101001), (100001)=(M 1 =297, M 2 =33).

Zaporedno šifrirani bloki izvornega besedila M 1 \u003d 297, M 2 \u003d 33:
y 1 = E k (M 1) = M 1 e ≡297 7 (mod527) \u003d 474.

Tukaj smo uporabili:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 = E k (M 2) \u003d M 2 e ≡33 7 (mod527) = 407.

Šifrirano besedilo, tako kot izvirno, je pridobljeno v obliki dveh blokov: y 1 =474; y 2 =407.

Dešifriranje zdi se zaporedje dejanj D k (y i)=(y i) d =(y i) 343 (mod 527), i=1,2.

Izračuni eksponentacije d bolj priročno je izvesti tako, da eksponent predhodno predstavimo kot vsoto potenk števila 2 , in sicer: 343=256+64+16+4+2+1 .

Uporaba te eksponentne predstavitve d=343, dobimo:

474 2 ≡174 (mod527),
474 4 ≡237 (mod527),
474 8 ≡307 (mod527),
474 16 ≡443 (mod527),
474 32 ≡205 (mod527),
474 64 ≡392 (mod527),
474 128 ≡307 (mod527),
474 256 ≡443 (mod527),
in končno 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Vrednost se izračuna podobno 407 343 (mod527) = 33.

Preklop na dobesedno predstavitev dešifriranega sporočila daje: RSA.

Po preučitvi primera priročnik obravnava moč sistema RSA. Potreba po previdnosti pri izbiri modula šifre RSA (številk n) za vsakega dopisnika omrežja. Opozarja se, da je nesprejemljivo zanemariti zahteve za izbrane značilnosti šifrirnega sistema. Med temi zahtevami žal ni navedena tista, katere kršitev ponazarja dani primer.

Napad na šifro RSA

Neuspeh (nedopustnost) izbranih sistemskih parametrov v tem primeru je enostavno prikazati z izračuni, ki izvajajo napad brez ključa branja izvornega besedila. Bistvo takšnega napada je naslednje. Podan je javni ključ šifre RSA ( e=7, n=527) in šifrirano besedilo. V primeru je šifrirano besedilo predstavljeno z dvema blokoma
y = (y 1 = 474, y 2 = 407).

Vsak šifriran blok je napaden posebej, najprej napademo y 1 =474, potem ko ga dešifriramo, napademo drug blok y 2 =407.

Nato se oblikuje s ponavljajočim se šifriranjem s shranjevanjem rezultatov dveh zaporednih korakov napadnega algoritma in z uporabo javnega ključa zaporedje številskih vrednosti jaz, y 1 = y razpoložljivo šifrirano besedilo.

V algoritmu napada na šifrirano besedilo se določi naslednja številka koraka j, za kar y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. Iz zadnje relacije vidimo, da pri dvigu na poten e vrednote (y i e j–1 (mod n)) izkaže se začetni shifortext y i = y 1.

Toda to pomeni, da je bilo golo besedilo v tem koraku šifrirano. Z neposrednimi izračuni (teh je zelo malo) s pomočjo zaslonskega kalkulatorja najdemo to vrednost j, pri katerem se šifrirni cikel konča z vrednostjo y 1 iz katerega se je cikel začel.

Napad na prvi blok y 1 =474šifrirano besedilo.
Korak 1:  474 7 (mod527)=382;
2. korak:  382 7 (mod527)=423;
3. korak:  423 7 (mod527)=297;
4. korak:   Ta korak šifrira že najdeno izvorno besedilo, vendar ga je treba izvesti, ker napadalec ne pozna izvornega besedila. Znak zaključka napada je naključje začetne vrednosti šifriranega besedila ( 474 ) in rezultat 4. koraka šifriranja. Točno takšno naključje se zgodi.

297 7 (mod527) = 474 prejel začetni (prvi) blok šifriranega besedila. Napad na prvi blok je bil uspešno zaključen y 1 =474. Prejšnji rezultat 3. koraka je golo besedilo M 1 \u003d 297.

n=527 r = 297 modulo n=527. Takole je napisano y i = y 1 = 297. Tvorimo ostanke moči
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Napad na drugi blok y 2 =407šifrirano besedilo.
Korak 1:  407 7 (mod527)=16;
2. korak:  16 7 (mod527)=101;
3. korak:  101 7 (mod527)=33;
4. korak:  33 7 (mod527)=407.

Spet v tretjem koraku dobimo izvorni besedilni blok ( M 2 \u003d 33), vendar napadalec tega ne ve in izvede naslednji (četrti korak), katerega rezultat je ( 407 ) se ujema z začetnim šifriranim besedilom y 2 =407.

V bistvu v obroču ostankov po modulu n=527 izvedla kratek cikel obdelave odbitka r=33 modulo n=527. Takole je napisano y i \u003d y 2 = 33.
Tvorimo ostanke moči ((33 7 (mod527)) 7 (mod527)) 7 (mod527) = 33.

Rezultat napada (izvirno besedilo M 1 \u003d 297, M 2 \u003d 33) se pridobi s trojnim šifriranjem danega šifriranega besedila. Težko si je predstavljati večji uspeh napadajočega šifranta.

V nadaljevanju razprave o izbiri modula in drugih parametrov šifriranja lahko dodamo, da je šifrirni modul ( n=527) nekatera izvorna besedila sploh ne dovoljujejo šifriranja. V tem primeru izbira vrednosti javnega ključa e ne igra velike vloge. Obstajajo vrednosti golega besedila, ki jih z izbrano šifro z modulom sploh ni mogoče šifrirati n=527.

Nobeden od danih e ne more šifrirati golih besedil, predstavljenih s številkami
187 , 341 , 154 in 373 .

Primer (nezmožnost šifriranja vrednosti nekaterih izvornih besedil)

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527) = 154;
154 17 (mod527)=154;
154 111 (mod527) = 154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527) = 187;
187 17 (mod527)=187;
187 111 (mod527) = 187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527) = 341;
341 9 (mod527) = 341;
341 17 (mod527) = 341;
341 111 (mod527) = 341;
373 2 (mod527)=1;
373 4 (mod527) = 373;
373 7 (mod527) = 373;
373 9 (mod527) = 373;
373 17 (mod527) = 373;
373 111 (mod527) = 373.

Iz obravnavanega primera izhaja preprost zaključek. Dejansko je treba k izbiri parametrov šifrirnega procesa pristopiti zelo previdno in opraviti temeljito predhodno analizo takšnih parametrov. Kako to storiti, je ločeno vprašanje in se ne obravnava v okviru tega dela.

V drugem delu si bomo ogledali priljubljen algoritem RSA, kjer se za šifriranje uporablja javni ključ. Toda najprej vas želim ponovno opozoriti. Koda v tem članku je zgolj informativna. Kriptografija je zelo obsežno in zapleteno področje in da ne bi imeli težav, ne priporočam šifriranja podatkov z uporabo moje obrti.

V drugem delu si bomo ogledali priljubljen algoritem RSA, kjer se za šifriranje uporablja javni ključ. Toda najprej vas želim ponovno opozoriti. Koda v tem članku je zgolj informativna. Kriptografija je zelo obsežno in zapleteno področje in da ne bi imeli težav, ne priporočam šifriranja informacij z mojo obrtjo.

algoritem RSA

Šifriranje z javnim ključem

Šifriranje z javnim ključem se uporablja povsod. Če ste kdaj kaj plačali na spletu, ste to metodo že uporabili (upam!). Takoj se pojavi vprašanje, kako deluje ta zaščita. Če vpišem svojo številko kreditno kartico da bi kaj kupil, zakaj, razen naslovnika, nihče ne more pokukati v te podatke? Dal vam bom metaforo. Če želite odpreti sef, potrebujete ključ (ali kladivo, na srečo pa so sefi in ključavnice zaščiteni pred tovrstnimi stvarmi). Pri šifriranju z javnim ključem se zgodi enako. Ključavnico pokažeš, da jo vidijo vsi, a le redki izbranci imajo ključ do te ključavnice in je skoraj nemogoče odpreti vrata na druge načine.

RSA je eden od algoritmov, ki izvajajo zgornjo shemo. Poleg tega lahko ta algoritem uporabimo za preverjanje pristnosti naše identitete. Če uporabite svoj zasebni ključ za pošiljanje šifriranega sporočila nekomu, lahko prejemnik uporabi javni ključ za dešifriranje vašega sporočila. Ta tehnologija vam omogoča podpisovanje sporočil in s tem potrditev pristnosti pošiljatelja.

Demo program, ki temelji na algoritmu RSA

RSA uporablja dve vrsti ključev - e in d , kjer je e javni in d tajni. Recimo, da je P golo besedilo in C šifrirano besedilo. Alice uporablja C = P e mod n, da ustvari šifrirano besedilo C iz golega besedila P; Bob uporablja P = C d mod n za ekstrakcijo izvornega besedila (datoteke), ki jo je zagotovila Alice. Zelo veliko število modulov n je ustvarjeno s postopkom generiranja ključev, o katerem bomo razpravljali kasneje.

Modulo eksponentiranje se uporablja za šifriranje in dešifriranje. Kot smo že razpravljali v predavanjih 12-13, je pri uporabi hitrega algoritma eksponentiranje po modulu izvedljivo v polinomskem času. Vendar pa je iskanje modulo logaritma prav tako težko kot faktorjenje števila po modulu. Za to ni polinomskega časovnega algoritma. To pomeni, da lahko Alice šifrira sporočilo z javnim ključem (e) v polinomskem času. Bob ga lahko dešifrira tudi v polinomskem času (ker pozna d ). Toda Eve ne more dešifrirati tega sporočila, ker bi morala izračunati e-ti koren C z uporabo modularne aritmetike. Slika 14.5 prikazuje idejo RSA.

riž. 14.5.

Z drugimi besedami, Alice uporablja enosmerna funkcija(exponentiation modulo) z vrzeljo, ki jo pozna samo Bob. Eva ne pozna vrzeli, zato ne zna razvozlati sporočila. Če se kdaj najde polinomski algoritem za e-ti korenski modul n, potem eksponentacija po modulu n ne bo več enosmerna funkcija.

Postopek

Slika 14.6 prikazuje splošno predstavo o postopku, ki se uporablja v RSA.

RSA uporablja eksponentni modul za šifriranje/dešifriranje. Da bi napadla zasebno besedilo, mora Eva računati

Dve algebraični strukturi

RSA uporablja dve algebraični strukturi: obroč in skupino.

Obroči za šifriranje/dešifriranje. Šifriranje in dešifriranje se izvede z uporabo komutativnega obroča z dvema računskima operacijama: seštevanjem in množenjem. V RSA je ta obroč javen, ker je modulo n javen. Vsakdo lahko pošlje sporočilo Bobu s tem šifrirnim obročem.

Skupine ključnih generacij. RSA uporablja multiplikativno skupino za generiranje ključev. Skupina podpira samo množenje in deljenje (multiplikativna inverzija), ki sta potrebni za generiranje javnih in zasebnih ključev. Ta skupina mora biti skrita, ker je njen modul skrivni. Videli bomo, da če Eve najde ta modul, lahko zlahka napade kriptografski sistem.

RSA uporablja dve algebraični strukturi: odprt obroč R =< Z n , +, x > in tajna skupina G =< Z (n)* , x >.

Generacija ključev

Bob uporablja korake, prikazane v algoritmu 14.2, da ustvari svoje javne in zasebne ključe. Po generiranju ključev Bob razglasi kortek (e, n) kot svoj javni dostopni ključ: Bob shrani d kot svoj zasebni ključ. Bob lahko zavrne p, q in ; ne morejo spremeniti njegovega zasebnega ključa, ne da bi spremenili modul. Zaradi varnosti je priporočena velikost za vsak preprost p ali q 512 bitov (skoraj 154 decimalnih števk). To določa velikost enote, n je 1024 bitov (309 števk).

V RSA je niz (e, n) javni dostopni ključ; celo število d - skrivni ključ.

Šifriranje

Vsak lahko pošlje sporočilo Bobu z njegovim javnim ključem za dostop. Šifriranje v RSA je mogoče izvesti z algoritmom polinomskega časa, kot je prikazano v algoritmu 14.3. Algoritem hitrega eksponentiranja je bil obravnavan v predavanjih 12-13. Velikost izvornega besedila mora biti manjša od n; če je velikost izvirnega besedila večja, ga je treba razdeliti na bloke.