Šifrovací algoritmus RSA. RSA šifrovací algoritmus Príklad šifrovania RSA

RSA používa dva typy kľúčov – e a d, kde e je verejné a d je tajné. Predpokladajme, že P je otvorený text a C je šifrový text. Alice používa C = P e mod n na vytvorenie šifrového textu C z otvoreného textu P ; Bob používa P = C d mod n na získanie zdrojového textu (súboru), ktorý poslala Alice. Veľmi veľký počet n modulov sa vytvára pomocou procesu generovania kľúča, o ktorom budeme diskutovať neskôr.

Na šifrovanie a dešifrovanie sa používa umocňovanie modulo. Ako sme diskutovali v prednáškach 12-13, pri použití rýchleho algoritmu je modulo exponenciácia možná v polynomiálnom čase. Nájdenie modulárneho logaritmu je však rovnako ťažké ako rozloženie číselného modulu. Neexistuje na to žiadny polynomiálny časový algoritmus. To znamená, že Alice dokáže zašifrovať správu verejným kľúčom (e) v polynomiálnom čase. Bob to vie dešifrovať aj v polynomiálnom čase (pretože pozná d). Ale Eve nemôže rozlúštiť túto správu, pretože by musela vypočítať e-koreň C pomocou modulárnej aritmetiky. Obrázok 14.5 zobrazuje myšlienku RSA.

Ryža. 14.5.

Inými slovami, Alice používa jednosmerná funkcia(exponenciačný modulo) s medzerou, ktorú pozná iba Bob. Eva nepozná medzeru, takže nemôže dešifrovať správu. Ak niekedy nájdu polynomiálny algoritmus pre modul výpočtu e-tej odmocniny n, potom umocňovanie modulo n už nebude jednosmernou funkciou.

Postup

Obrázok 14.6 zobrazuje všeobecnú predstavu o postupe používanom v RSA.

RSA používa modulo umocnenie na šifrovanie/dešifrovanie. Aby mohla zaútočiť na súkromný text, Eva musí počítať

Ryža. 14.6.

Dve algebraické štruktúry

RSA používa dve algebraické štruktúry: kruh a skupinu.

Šifrovacie/dešifrovacie prstene. Šifrovanie a dešifrovanie sa vykonáva pomocou komutatívneho kruhu s dvoma aritmetickými operáciami: sčítanie a násobenie. V RSA je tento kruh verejný, pretože modul n je verejný. Ktokoľvek môže poslať správu Bobovi pomocou tohto šifrovacieho kruhu.

Skupiny generovania kľúčov. RSA používa multiplikatívnu skupinu na generovanie kľúčov. Skupina podporuje iba násobenie a delenie (multiplikatívnu inverziu), ktoré sú potrebné na vytvorenie verejných a súkromných kľúčov. Táto skupina musí byť skrytá, pretože jej modul je tajný. Uvidíme, že ak Eve nájde tento modul, môže ľahko zaútočiť na kryptografický systém.

RSA používa dve algebraické štruktúry: otvorený kruh R =< Z n , +, x > a tajná skupina G =< Z (n)* , x >.

Generovanie kľúčov

Bob používa kroky uvedené v Algoritme 14.2 na vytvorenie svojich verejných a súkromných kľúčov. Po vygenerovaní kľúčov Bob deklaruje n-ticu (e, n) ako svoj verejný prístupový kľúč: Bob ukladá d ako svoj súkromný kľúč. Bob sa môže vzdať p, q a ; nemôžu zmeniť jeho tajný kľúč bez zmeny modulu. Kvôli bezpečnosti je odporúčaná veľkosť každého prvočísla p alebo q 512 bitov (takmer 154 desatinných číslic). Toto definuje veľkosť modulu, n 1024 bitov (309 číslic).

14.2. Generovanie kľúča RSA

V RSA je n-tica (e, n) verejný prístupový kľúč; celé číslo d - tajný kľúč.

Šifrovanie

Ktokoľvek môže poslať správu Bobovi pomocou jeho verejného prístupového kľúča. Šifrovanie v RSA je možné vykonať pomocou algoritmu s polynomiálnou časovou zložitosťou, ako je uvedené v Algoritme 14.3. Rýchly algoritmus umocňovania bol diskutovaný v prednáškach 12-13. Veľkosť zdrojového textu musí byť menšia ako n ; ak je veľkosť zdrojového textu väčšia, potom ho treba rozdeliť na bloky.

Dobrý deň, milí čitatelia.
S najväčšou pravdepodobnosťou väčšina z vás vie, čo je asymetrický šifrovací algoritmus RSA. V skutočnosti existuje toľko článkov venovaných tejto problematike v celom RuNet a najmä o tomto zdroji, že je takmer nemožné povedať o tom niečo nové.
No, preboha, môžete prísť na niečo iné a všetko bolo už dávno jasné. Recept je jednoduchý:
Dve prvočísla P a Q.
Násobte, kým nedostanete číslo N.
Vyberte ľubovoľný E.
Nájsť D=E -1 (mod( P-1)(Q-1)).
Aby sme zašifrovali správu M, povýšime ju na silu E modulo N. Na dešifrovanie kryptotextu C na mocnosť D, modulo N. Celé kryptoprimitívum je pripravené. Vezmime si to a použime, nie? Vlastne nie takto. Ide o to, že toto naozaj nie je nič iné ako krypto-primitív a v reálnom svete je všetko trochu komplikovanejšie.

Trochu teórie

Aby sme pochopili, prečo sa veľmi neodporúča používať RSA v jeho najjednoduchšej forme, najprv si všimneme nasledujúcu požiadavku na asymetrické kryptosystémy.
Požiadavka 1:
Moderný asymetrický kryptosystém možno (ale to ešte nie je skutočnosťou) považovať za bezpečný, ak útočník, ktorý má dva otvorené texty M 1 a M 2, ako aj jeden šifrový text C b, nedokáže s pravdepodobnosťou väčšou ako 0,5 určiť, ktorý z nich dvom otvoreným textom, šifrovému textu C zodpovedá b.
Pozrime sa, či RSA spĺňa túto požiadavku. Predstavte si teda, že útočník Mallory počúva korešpondenciu medzi Alice a Bobom. Jedného nádherného dňa pre seba uvidí, že Bob otvorene položil Alici veľmi dôležitú otázku, ktorej odpoveď obohatí, alebo aspoň nesmierne pobaví Maloryho zvedavosť. Alice odpovedá Bobovi na túto osobnú otázku jednoslabične. Svoju odpoveď zašifruje Bobovým verejným kľúčom a odošle zašifrovaný text. Malory potom zachytí šifrový text a má podozrenie, že obsahuje buď „Áno“ alebo „Nie“. Všetko, čo teraz musí urobiť, aby zistil Alicinu odpoveď, je zašifrovať slovo „Áno“ Bobovým verejným kľúčom a ak sa prijatý kryptotext zhoduje so zachyteným, znamená to, že Alice odpovedala „Áno“, inak to útočník pochopí. že odpoveď bola "nie".

Ako je možné vidieť z tohto, aj keď trochu pritiahnutého, ale stále nie takého utopického príkladu, RSA nie je taká spoľahlivá, ako sa bežne verí. Áno, samozrejme, môžeme povedať, že samotná Alice je blázon a nikto ju nežiadal, aby jej na takú vážnu otázku odpovedala jednoslabične. Tak prečo teraz zakázať používanie jednoslovných odpovedí v kryptografii? Samozrejme, že nie. Všetko nie je také zlé, stačí, aby algoritmus pridal do textu nejaké náhodné informácie, ktoré by nebolo možné predvídať a zákerná Mallory bude bezmocná. Koniec koncov, v skutočnosti nebude môcť predpovedať, že odpoveď „Áno“ po spracovaní algoritmom sa zmení napríklad na „Áno4FE6DA54“, a preto nebude môcť túto správu zašifrovať a nebude mať nič. na porovnanie so zachyteným kryptotextom.

Už teraz teda môžeme povedať, že RSA vo všetkých svojich prejavoch, či už je to PGP alebo SSL, nešifruje iba dáta odoslané na vstup šifrovacej funkcie. Algoritmus najprv k týmto dátam pridá bloky obsahujúce náhodnú množinu bitov. A až potom je výsledný výsledok zašifrovaný. Tie. namiesto bežného
C=M E (mod N)
dostávame sa bližšie k realite
C=(M||Rand) E (mod N),
kde Rand je náhodné číslo.
Táto technika sa nazýva augmentačné schémy. V súčasnosti nie je používanie RSA bez výplňových obvodov ani tak zlé, ako skôr porušenie noriem.

Ale to nie je všetko. Predpokladá sa, že aj keď kryptosystém spĺňa požiadavku formulovanú vyššie, ešte to nepreukazuje jeho vhodnosť na praktické účely. Sformulujme ešte jednu požiadavku na bezpečnosť asymetrického algoritmu.

Požiadavka 2:
Umožnite útočníkovi prístup k dešifrovacej „čiernej skrinke“. Tie. Akýkoľvek kryptotext môže byť dešifrovaný na žiadosť útočníka. Potom útočník vytvorí dva otvorené texty M 1 a M 2 . Jeden z týchto textov je zašifrovaný a výsledný kryptotext C b je vrátený útočníkovi. Úlohou útočníka je uhádnuť s pravdepodobnosťou väčšou ako 0,5, ktorá zo správ M 1 a M 2 zodpovedá kryptotextu C b . Zároveň môže požiadať o rozlúštenie akejkoľvek správy okrem C b (inak hra nemá zmysel). Hovorí sa, že kryptosystém je silný, ak útočník ani v takých pre seba výborných podmienkach nedokáže s pravdepodobnosťou väčšou ako 0,5 uviesť, ktorému zdrojovému textu Cb zodpovedá.

Vo svetle vyššie uvedeného sa pozrime, ako sa to deje v RSA.
Útočník má teda dve správy M 1 a M 2. A tiež kryptotext
Cb = M1E (mod N).
Musí uviesť, ktorý z týchto dvoch textov zodpovedá C b. Za týmto účelom môže urobiť nasledovné. Keď pozná verejný kľúč E, môže vytvoriť správu
C"=2 E *Cb (mod N).
Potom požiada dešifrovaciu „čiernu skrinku“, aby dešifrovala správu C." A potom mu pomôže jednoduchá aritmetika. Máme:
M"=C" D (mod N)=2 ED *M 1 ED (mod N) = 2*M1 (mod N).
Tie. Po vypočítaní M"/2 útočník uvidí M 1. To znamená, že pochopí, že v našom príklade bola správa M 1 zašifrovaná, a preto sme sa opäť presvedčili o neprijateľnosti používania RSA v naivnej podobe v praxi. .

Schémy pridávania pomáhajú eliminovať túto nepríjemnosť. Až teraz sa od nich žiada nielen to, aby dodatočné informácie boli absolútne náhodné a nepredvídateľné. Je však tiež dôležité, aby ďalšie bloky pomohli určiť, či bol šifrovaný text získaný ako výsledok funkcie šifrovania, alebo či ho simuloval útočník. Navyše, ak sa zistí, že namiesto dešifrovaných údajov je simulovaný šifrový text, útočník dostane správu, že údaje nezodpovedajú skutočnému šifrovanému textu.

Zdá sa, že implementácia takejto schémy sčítania je náročná úloha, ale kryptografia už má pripravený nástroj na monitorovanie integrity údajov. Samozrejme, ide o hashovacie funkcie. Všetky moderné schémy pridávania sú založené na myšlienke použitia hašovacej funkcie na kontrolu pravosti dešifrovaných údajov.

RSA používa dve rôzne schémy výplne na podpisovanie a šifrovanie údajov. Schéma implementovaná na podpisovanie dokumentov sa nazýva RSA-PSS (pravdepodobnostná podpisová schéma) resp pravdepodobnostná podpisová schéma. Použitá schéma šifrovania je RSA-OAEP (Optimal asymetrické šifrovanie padding) resp optimalizovaná výplň asymetrického šifrovania, pričom ako príklad použijeme OAEP a pozrime sa, ako sú správy skutočne šifrované v RSA.

RSA-OAEP

Ak chcete zašifrovať absolútne akúkoľvek správu v RSA-OAEP, postupujte takto:

1. Dve hašovacie funkcie G(x) a H(x) sú zvolené tak, aby celková dĺžka výsledkov hašovacej funkcie nepresiahla dĺžku kľúča RSA.
2. Vygeneruje sa náhodný bitový reťazec l. Dĺžka reťazca sa musí rovnať dĺžke výsledku hašovacej funkcie H(x).
3. Správa M je rozdelená na bloky k-bitov. Potom sa ku každému prijatému bloku m pridá (n-k) núl. Kde n je dĺžka hašovacej funkcie G(x).
4. Definujte nasledujúcu množinu bitov: (m||0 (n-k) ⊕G(l))||(l⊕H(m||0 (n-k) ⊕G(l)))
5. Výsledné bity sú reprezentované ako celé číslo Mi
6. Kryptotext sa získa pomocou vzorca: C=M 1 E (mod N)

Proces dešifrovania je nasledujúci:

1. Nájdite M 1 pomocou vzorca M 1 = C D (mod N)
2. Vo výslednej sade bitov je ľavá strana odrezaná. V zmysle: ľavá strana je n ľavých bitov čísla M 1, kde n je dĺžka hašovacej funkcie G(x). Označme tieto bity konvenčne ako T. A všimnime si, že T=(m||0 (n-k) ⊕G(l)). Všetky ostatné bity sú na pravej strane.
3. Nájdeme H(T)=H(m||0 (n-k) ⊕G(l))
4. Pri poznaní H(T) dostaneme l, keďže vieme, že l⊕H(T) je pravá strana bloku.
5. Po vypočítaní l nájdeme m z T⊕G(l), pretože T=(m||0 (n-k) ⊕G(l))
6. Ak m končí (n-k)-nulami, potom je správa zašifrovaná správne. Ak nie, znamená to, že šifrový text je nesprávny, a preto ho s najväčšou pravdepodobnosťou sfalšoval útočník.

Záver

Tie. RSA nie je len o umocňovaní veľkého počtu. Ide tiež o pridanie nadbytočných údajov, ktoré umožňujú dodatočnú ochranu vašich informácií. Môžete sa opýtať: prečo je to všetko potrebné? Je naozaj možné, aby takáto situácia nastala, keď útočník získa prístup k dešifrovaciemu algoritmu? Pri úplne inej príležitosti sa raz povedalo: ak sa môže stať nejaký problém, určite sa stane. Iba pri použití schém sčítania to už nebude považované za obťažovanie.

Aktualizácia: presunutá kryptografia na blog.
upd2:
Literatúra a odkazy:
1. N. Fergusson, B. Schneier „Praktická kryptografia“
2. N. Inteligentná „kryptografia“

Úvod 3

Hlavná časť 5

1 História stvorenia 5

2Popis algoritmu 5

2.1Vytvorenie kľúčov 6

2.2 Šifrovanie a dešifrovanie 6

2.3 Použite príklad 7

Záver 9

Zoznam použitých zdrojov 10

Úvod

Kryptografia je špeciálny systém na zmenu bežného písma, ktorý sa používa na to, aby bol text zrozumiteľný len obmedzenému počtu ľudí, ktorí tento systém poznajú.

Kryptografia je veda o ochrane informácií pomocou matematických metód.

Moderná kryptografia zahŕňa:

symetrické kryptosystémy;

asymetrické kryptosystémy;

systémy elektronického digitálneho podpisu (EDS);

hašovacie funkcie;

správa kľúčov;

získavanie skrytých informácií;

kvantová kryptografia.

Symetrické šifrovanie - symetrické algoritmy sú tie, v ktorých sa na šifrovanie a dešifrovanie používa rovnaký tajný kľúč (známy iba odosielateľovi a príjemcovi).

Bežné symetrické šifrovacie algoritmy:

AES (Advanced Encryption Standard) - americký šifrovací štandard;

GOST 28147-89 - domáci štandard šifrovania údajov;

DES (Data Encryption Standard) - štandard šifrovania dát v USA až po AES;

3DES (Triple-DES, triple DES);

IDEA (International Data Encryption Algorithm);

SEED - kórejský štandard šifrovania údajov;

Camellia je šifra certifikovaná na použitie v Japonsku;

XTEA je najjednoduchší algoritmus na implementáciu.

Asymetrické kryptoalgoritmy sú navrhnuté predovšetkým tak, aby eliminovali hlavnú nevýhodu symetrických kryptosystémov – zložitosť správy a distribúcie kľúčov.

Základom všetkých asymetrických kryptografických algoritmov je vysoká výpočtová zložitosť obnovy otvoreného textu bez znalosti súkromného kľúča.

Príklady asymetrických krypto algoritmov:

Diffie-Hellmann;

RSA - Rivest, Shamir, Adelman - je založená na zložitosti problému faktorizácie veľkých čísel v krátkom čase;

DSA – Algoritmus digitálneho podpisu, americký štandard;

GOST R 34.10 – 94, 2001, normy Ruskej federácie.

V tomto abstrakte sa budeme podrobne zaoberať asymetrickým kryptografickým šifrovacím algoritmom - algoritmom RSA.

Hlavná časť

Algoritmus RSA (skratka pre Rivest, Shamir a Adleman) je kryptografický algoritmus s verejným kľúčom, ktorý využíva výpočtovú zložitosť problému faktorizácie veľkých celých čísel. Kryptosystém RSA bol prvým systémom vhodným na šifrovanie aj digitálne podpisovanie.

História stvorenia

Práca Whitfielda Diffieho a Martina Hellmana „New Directions in Cryptography“, publikovaná v novembri 1976, priniesla revolúciu v chápaní kryptografických systémov tým, že položila základy kryptografie s verejným kľúčom. Následne vyvinutý algoritmus Diffie-Hellman umožnil dvom stranám získať zdieľaný tajný kľúč pomocou nezabezpečeného komunikačného kanála. Tento algoritmus však nevyriešil problém s autentifikáciou. Bez ďalších nástrojov si používatelia nemohli byť istí, s kým vygenerovali zdieľaný tajný kľúč.

Po preštudovaní tohto článku začali traja vedci Ronald Linn Rivest, Adi Shamir a Leonard Adleman z Massachusettského technologického inštitútu (MIT) hľadať matematickú funkciu, ktorá by umožnila implementovať model kryptografického systému s verejným kľúčom, ktorý sformulovali Whitfield Diffie a Martin Hellman. . Po prepracovaní viac ako 40 možností prišli s algoritmom založeným na rozdiele v tom, aké ľahké je nájsť veľké prvočísla a aké ťažké je faktorizovať súčin dvoch veľkých prvočísel, ktoré neskôr nazvali RSA. Systém dostal názov podľa prvých písmen priezvisk jeho tvorcov.

Popis algoritmu

Prvým krokom v akomkoľvek asymetrickom algoritme je vytvorenie páru kľúčov – verejného a súkromného – a distribúcia verejného kľúča „po celom svete“.

Vytváranie kľúčov

V prípade algoritmu RSA fáza vytvorenia kľúča pozostáva z nasledujúcich operácií:

Číslo sa nazýva otvorený exponent

Šifrovanie a dešifrovanie

Povedzme, že odosielateľ chce poslať správu príjemcovi.

Správy sú celé čísla v rozsahu od 0 do , t.j. . Obrázok 1 znázorňuje schému algoritmu RSA.

Obrázok 1 – Schéma algoritmu RSA

Algoritmus odosielateľa:

Algoritmus príjemcu:

Rovnice (1) a (2), na ktorých je schéma RSA založená, určujú vzájomne inverzné transformácie množiny.

Príklad použitia

Tabuľka 1 ukazuje príklad použitia algoritmu RSA. Odosielateľ poslal zašifrovanú správu „111111“ a príjemca ju pomocou svojho súkromného kľúča dešifroval.

Tabuľka 1 – Postupné vykonávanie algoritmu RSA

	Popis operácie	Výsledok operácie
Generovanie kľúčov	Vyberte dve prvočísla
	Vypočítajte modul
	Vypočítajte Eulerovu funkciu
	Vyberte otvorený exponent
	Vypočítajte tajný exponent
Šifrovanie	Vyberte text, ktorý chcete zašifrovať
	Vypočítajte šifrový text
Dekódovanie	Vypočítajte pôvodnú správu

Záver

V tomto abstrakte sa podrobne diskutuje o asymetrickom šifrovacom algoritme RSA. Bola popísaná história jeho vzniku, boli popísané algoritmy na vytváranie kľúčov, šifrovanie a dešifrovanie. Uvedený je aj príklad praktického využitia algoritmu RSA.

Zoznam použitých zdrojov

Semenov Yu.A. Internetové protokoly // M.: Prospekt, 2011. – 114 s.

Beljajev A.V. Metódy a prostriedky informačnej bezpečnosti // Black Branch of St. Petersburg State Technical University, 2010. – 142 s.

Venbo M. Moderná kryptografia. Teória a prax // M.: Williams, 2005. - 768 s.

Schneier B. Aplikovaná kryptografia. Protokoly, algoritmy, zdrojové texty // M.: Triumph, 2002. - 816 s.

Algoritmus RSA // Internetový zdroj: http://ru.wikipedia.org/wiki/Rsa

Pod rezom sú príklady výberu „zlých“ parametrov šifry RSA.

„Treba zdôrazniť, že pri výbere modulu RSA (číslo n) pre každého zo sieťových korešpondentov. V tejto súvislosti možno povedať nasledovné. Čitateľ si to môže nezávisle overiť znalosťou jednej z troch veličín p, q alebo φ(n), môžete ľahko nájsť súkromný kľúč RSA...“.

Pridajme k tomuto textu. Ak je výber šifrovacieho modulu RSA neúspešný, ako sa to stalo v príklade nižšie uvedeného návodu, môžete text dešifrovať bez prítomnosti tajného kľúča, t.j. bez znalosti niektorej z troch menovaných veličín.

Na to stačí mať šifrovaný text špecifikovaný šifrovacím modulom n, verejný kľúč e zašifrovať a vykonať iba tri kroky útoku na čítanie bez kľúča. Po štvrtom kroku útoku sa zistí, že zdrojový text bol získaný v predchádzajúcom kroku a je možné ho prečítať. Ukážme si, aké ľahké je to urobiť.

Najprv uveďme samotný príklad zo str. 313-315 z uvedenej príručky.

Príklad

Šifrovanie krátka úvodná textová správa: RSA.
Príjemca nastaví šifru s charakteristikami n=pq=527, Kde p=17, q = 31 A φ(n)=(R –1)(q – 1)=480. Ako verejný kľúč e vyberie sa číslo, ktoré je prime φ(n), e=7. Celé čísla sa pre toto číslo nájdu pomocou rozšíreného euklidovského algoritmu u A v, uspokojenie vzťahu e∙u+φ(n)∙v=1:

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.

Pretože –137≡343 (mod480), To d = 343.

Vyšetrenie: 7∙343=2401≡1(mod480).

Textová správa je prezentovaná ako postupnosť čísel obsiahnutých v intervale . Listy na toto R, S A A sú zakódované ako päťbitové binárne čísla. Sériové čísla týchto písmen v anglickej abecede sa používajú v ich binárnom vyjadrení:

R=1810=(10010) 2, S=1910=(10011) 2,
A=110=(00001) 2.

Potom RSA=(100101001100001) 2. Rozdelenie textu na bloky s obmedzenou dĺžkou vytvorí prezentáciu v dvoch blokoch: RSA=(100101001), (100001)=(M1=297, M2=33).

Bloky zdrojového textu sú šifrované postupne Mi = 297, M2=33:
y1=Ek(M1)=M1e=2977 (mod527)=474.

Tu sme využili skutočnosť, že:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y2=Ek(M2)=M2e ≡337 (mod527)=407.

Šifrový text, rovnako ako pôvodný, sa získa vo forme dvoch blokov: yi = 474; y2 = 407.

Dekódovanie Zdá sa, že ide o postupnosť akcií D k (y i) = (y i) d = (y i) 343 (mod 527), i = 1,2.

Výpočty umocňovania d výhodnejšie je to uskutočniť tak, že najprv predstavíte exponent ako súčet mocnin čísla 2 , menovite: 343=256+64+16+4+2+1 .

Použitie tohto exponentného vyjadrenia d = 343, dostaneme:

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),
a nakoniec 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Hodnota sa vypočíta podobne 407 343 (mod527) = 33.

Prepnutie na doslovnú reprezentáciu dešifrovanej správy dáva: RSA.

Po zhliadnutí príkladu sa v príručke hovorí o robustnosti systému RSA. Zdôrazňuje sa potreba opatrnosti pri výbere šifrovacieho modulu (čísla) RSA. n) pre každého zo sieťových korešpondentov. Uvádza sa, že je neprípustné ignorovať požiadavky na vybrané vlastnosti šifrovacieho systému. Medzi týmito požiadavkami, žiaľ, nie je uvedené porušenie ktorých ilustruje uvedený príklad.

Útok na šifru RSA

Pozrime sa na príklad útoku na šifru RSA. Využime údaje z príkladu uvedeného na stranách 313-315 v učebnici „Základy kryptografie“ od A.P. Alferov, A.Yu. Zubov, A.S. Kuzminová, A.V. Cheremushkin, Moskva. "Helios ARV", 2001.

Zlyhanie (neprípustnosť) zvolených parametrov systému v tomto príklade sa dá ľahko ukázať pomocou výpočtov, ktoré implementujú útok na bezkľúčové čítanie zdrojového textu. Podstata takéhoto útoku je nasledovná. Je zadaný verejný kľúč šifry RSA ( e=7, n = 527) a šifrový text. V príklade je šifrový text reprezentovaný v dvoch blokoch
y=(y1=474, y2=407).

Každý zašifrovaný blok je napadnutý individuálne, najskôr zaútočíme yi = 474, po jeho dešifrovaní útočíme na ďalší blok y2 = 407.

Potom sa postupnosť číselných hodnôt vytvorí opakovaným šifrovaním, uložením výsledkov dvoch po sebe nasledujúcich krokov algoritmu útoku a použitím verejného kľúča. y i, y 1 = y dostupný šifrovaný text.

V algoritme útoku na šifrovaný text je určené nasledujúce číslo kroku: j, pre ktoré y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. Z posledného vzťahu vidíme, že keď je povýšený na moc e hodnoty (y i e j–1 (mod n)) získa sa počiatočný šifrový text y i = y 1.

To však znamená, že čistý text bol v tomto kroku zašifrovaný. Priamymi výpočtami (je ich veľmi málo) pomocou kalkulačky na obrazovke zistíme túto hodnotu j, pri ktorej sa šifrovací cyklus končí hodnotou y 1, od ktorej sa začal cyklus.

Útok na prvý blok yi = 474 zašifrovaný text.
Krok 1:  474 7 (mod527)=382;
Krok 2:  382 7 (mod527)=423;
Krok 3:  423 7 (mod527)=297;
Krok 4:   v tomto kroku je už nájdený zdrojový text zašifrovaný, ale musí sa to urobiť, pretože útočník nepozná zdrojový text. Znakom dokončenia útoku je zhoda s počiatočnou hodnotou šifrového textu ( 474 ) a výsledok 4. kroku šifrovania. Presne takáto náhoda sa odohráva.

297 7 (mod527) = 474 prijal počiatočný (prvý) blok šifrovaného textu. Útok na prvý blok bol úspešne dokončený yi = 474. Predchádzajúci výsledok kroku 3 sa rovná otvorenému textu Mi = 297.

n = 527 r = 297 modulo n = 527. Je to napísané takto yi = у 1 = 297. Formovanie zvyškov energie
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Útok na druhý blok y2 = 407 zašifrovaný text.
Krok 1:  407 7 (mod527)=16;
Krok 2:  16 7 (mod527)=101;
Krok 3:  101 7 (mod527)=33;
Krok 4:  33 7 (mod527)=407.

V treťom kroku sa opäť získal blok zdrojového textu ( M2=33), ale útočník o tom nevie a vykoná ďalší (štvrtý krok), ktorého výsledkom je ( 407 ) sa zhoduje s počiatočným šifrovým textom y2 = 407.

V podstate v kruhu modulo zvyškov n = 527 bol implementovaný krátky cyklus spracovania odpočtu r = 33 modulo n = 527. Je to napísané takto yi = y2 = 33.
Formovanie zvyškov energie ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Výsledok útoku (zdrojový text Mi = 297, M2=33) sa získa trojnásobným zašifrovaním daného šifrového textu. Ťažko si predstaviť väčší úspech pre útočníka šifrovaného textu.

Pokračujúc v diskusii o výbere modulu a ďalších parametroch šifry môžeme dodať, že modul šifry ( n = 527) niektoré zdrojové texty sa nedajú zašifrovať vôbec. V tomto prípade nehrá výber hodnoty verejného kľúča veľkú rolu. Existujú hodnoty zdrojového textu, ktoré vo všeobecnosti nie je možné zašifrovať vybranou šifrou s modulom n = 527.

Žiadna z uvedených nevie zašifrovať zdrojové texty reprezentované číslami
187 , 341 , 154 A 373 .

Príklad (neschopnosť zašifrovať hodnoty niektorých zdrojových textov)

Nech sú zdrojové texty reprezentované štyrmi blokmi y=(y1=154, y2=187, y3=341, y4=373). Vystavovateľ e verejným kľúčom šifry môže byť akékoľvek hlavné číslo s funkciou Euler φ(n)=φ(527)=480. V posudzovanom prípade však verejný kľúč e je možné nastaviť ľubovoľne. Skutočne, nech e = 2, 4, 7, 9, 17, 111 potom:

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.

Z uvažovaného príkladu vyplýva jednoduchý záver. K výberu parametrov pre proces šifrovania sa musí pristupovať veľmi opatrne a musí sa vykonať dôkladná predbežná analýza týchto parametrov. Ako to urobiť, je samostatný problém a nie je predmetom tejto práce.

V druhej časti sa pozrieme na populárny algoritmus RSA, kde sa na šifrovanie používa verejný kľúč. Najprv vás však chcem znova varovať. Kód uvedený v tomto článku slúži len na vzdelávacie účely. Kryptografia je veľmi široká a zložitá oblasť a aby sa predišlo problémom, neodporúčam šifrovať informácie pomocou môjho hacku.

V druhej časti sa pozrieme na populárny algoritmus RSA, kde sa na šifrovanie používa verejný kľúč. Najprv vás však chcem znova varovať. Kód uvedený v tomto článku slúži len na vzdelávacie účely. Kryptografia je veľmi široká a zložitá oblasť a aby sa predišlo problémom, neodporúčam šifrovať informácie pomocou môjho hacku.

Algoritmus RSA

Šifrovanie pomocou verejného kľúča

Šifrovanie verejným kľúčom sa používa všade. Ak ste aspoň raz za niečo online zaplatili, už ste túto metódu (dúfam!) použili. Hneď vyvstáva otázka, ako táto ochrana funguje. Ak zadávam číslo svojej kreditnej karty, aby som si niečo kúpila, prečo tieto informácie nemôže vidieť nikto okrem príjemcu? Dovoľte mi uviesť metaforu. Na otvorenie trezoru potrebujete kľúč (alebo kladivo, ale našťastie sú trezory a zámky voči týmto typom aktérov odolné). Pri šifrovaní verejným kľúčom sa deje takmer to isté. Zámok ukážete každému, ale kľúč od tohto zámku má len pár vyvolených a otvoriť dvere inými spôsobmi je takmer nemožné.

RSA je jedným z algoritmov, ktoré implementujú vyššie uvedenú schému. Okrem toho môžeme tento algoritmus použiť na overenie pravosti našej identity. Ak niekomu odošlete zašifrovanú správu pomocou súkromného kľúča, príjemca môže vašu správu dešifrovať pomocou verejného kľúča. Táto technológia umožňuje podpísať správy, čím sa potvrdí pravosť odosielateľa.

Demo program založený na algoritme RSA