RSA

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. května 2021; ověření vyžaduje 31 úprav .

RSA
Datum založení / vytvoření / výskytu	1977 [1]
Pojmenoval podle	Rivest, Ronald Lynn , Adi Shamir a Leonard Max Adleman
Vzorec popisující zákon nebo větu	$\left(m^{e}\right)^{d}\equiv m{\pmod {n}}$ [2]

RSA (zkratka pro Rivest, Shamir a Adleman) je kryptografický algoritmus s veřejným klíčem založený na výpočetní složitosti problému faktorizace velkých celých čísel .

Kryptosystém RSA byl prvním systémem vhodným pro šifrování i digitální podpis . Algoritmus se používá ve velkém množství kryptografických aplikací, včetně PGP , S/MIME , TLS / SSL , IPSEC / IKE a dalších [3] .

Historie

Myšlenka asymetrického kryptosystému veřejného/soukromého klíče je připisována Whitfieldovi Diffiemu a Martinu Hellmanovi , kteří tento koncept zveřejnili v roce 1976. Zavedli také digitální podpisy a pokusili se aplikovat teorii čísel. Jejich formulace používala sdílený tajný klíč vytvořený exponencializací nějakého čísla modulo prvočíslo. Problém implementace jednosměrné funkce však nechali otevřený, možná proto, že složitost faktorizace nebyla v té době dobře pochopena.

Ron Rivest, Adi Shamir a Leonard Adleman z MIT se v průběhu roku několikrát pokusili vytvořit jednosměrnou funkci, kterou by bylo obtížné invertovat. Rivest a Shamir jako počítačoví vědci navrhli mnoho potenciálních funkcí a Adleman jako matematik byl zodpovědný za nalezení jejich slabin. Vyzkoušeli mnoho přístupů, včetně „batohu“ a „permutačních polynomů“. Chvíli si mysleli, že to, čeho chtějí dosáhnout, je nemožné kvůli protichůdným požadavkům. V dubnu 1977 strávili Pesach v domě jednoho studenta a vypili hodně vína Manishevitz, než se kolem půlnoci vrátili domů. Rivest, který nemohl usnout, si lehl na pohovku se svou učebnicí matematiky a začal přemýšlet o své jednosměrné funkci. Zbytek noci strávil formalizací svého nápadu a za svítání byla většina článku hotová. Algoritmus je nyní známý jako RSA - iniciály jejich příjmení, ve stejném pořadí jako v jejich příspěvku.

Clifford Cox, anglický matematik pracující pro britskou zpravodajskou službu Government Communications Headquarters (GCHQ), popsal ekvivalentní systém v interním dokumentu v roce 1973. Vzhledem k relativně drahým počítačům, které byly v té době nutné k jeho implementaci, byl však většinou považován za zvědavost a, pokud je známo, nebyla uplatněna. Jeho objev byl ale odhalen až v roce 1997 kvůli jeho přísně tajnému zařazení.

V srpnu 1977 se se svolením Ronalda Rivesta [4 ] objevil první popis kryptosystému RSA [5] ve sloupku Martina Gardnera „Mathematical Games“ ve Scientific American . Čtenáři byli také požádáni, aby rozluštili anglickou frázi zašifrovanou popsaným algoritmem:

9686 1477 8829 7431 0816 3569 8962 1829

9613 1409 0575 9874 2982 3147 8013 9451

7546 2225 9991 6951 2514 6622 3919 5781

2206 4355 1245 2093 5708 8839 9055 5154

Čísla n= 1143816...6879541 (129 desetinných míst, 425 bitů , také známá jako RSA-129 ) a e=9007 byla použita jako parametry otevřeného systému. Za dešifrování byla vypsána odměna 100 $. Podle Rivesta by rozklad čísla trvalo více než 40 kvadrilionů let [6] [3] . Avšak o něco více než 15 let později, 3. září 1993, bylo oznámeno spuštění projektu distribuovaných počítačů s koordinací prostřednictvím e-mailu s cílem nalézt faktory čísla RSA-129 a vyřešit hádanku. Během šesti měsíců více než 600 dobrovolníků z 20 zemí věnovalo CPU čas 1 600 strojům (z toho tři faxy). ). V důsledku toho byly nalezeny prvočinitele a rozluštěna původní zpráva, kterou je fráze " THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE " ("Magic words are a squeamish lamb ") [7] [8] . Vítězové věnovali cenu, kterou obdrželi, nadaci Free Software Foundation .

Po zveřejnění Martina Gardnera mohl kdokoli získat úplný popis nového kryptosystému zasláním žádosti poštou Ronaldu Rivestovi s přiloženou obálkou se zpáteční adresou a známkami za 35 centů. [5] Úplný popis nového kryptosystému byl zveřejněn v Communications of ACM v únoru 1978 [9] .

Patentová přihláška byla podána 14. prosince 1977, přičemž vlastníkem je MIT. Patent 4405829 byl vydán 20. září 1983 a jeho platnost vypršela 21. září 2000 [10] . Mimo USA však vynálezci neměli na algoritmus patent, protože ve většině zemí bylo nutné jej získat před prvním zveřejněním [11] .

V roce 1982 založili Rivest, Shamir a Adleman RSA Data Security EMC . V roce 1989 je RSA spolu se symetrickou šifrou DES zmíněna v RFC 1115 , čímž se začíná používat algoritmus v rodícím se internetu [12] a v roce 1990 začíná algoritmus používat Ministerstvo obrany USA [13] .

V listopadu 1993 je otevřeně zveřejněna verze 1.5 standardu PKCS1 , která popisuje použití RSA pro šifrování a vytváření elektronického podpisu. Nejnovější verze standardu jsou k dispozici také jako RFC ( RFC 2313 - 1.5, 1993; RFC 2437 - 2.0, 1998; RFC 3447 - 2.1, 2002).

V prosinci 1997 byla zveřejněna informace, podle které britský matematik Clifford Cocks, který pracoval v UK Government Communications Center ( GCHQ ) , popsal v roce 1973 kryptosystém podobný RSA [14] .

Popis algoritmu

Úvod

Kryptografické systémy s veřejným klíčem používají takzvané jednosměrné funkce , které mají následující vlastnosti:

pokud je známo , pak je poměrně snadné vypočítat; $X$ $f(x)$
pokud je známo , pak neexistuje jednoduchý (efektivní) způsob výpočtu . $y=f(x)$ $X$

Jednostrannost není chápána jako matematicky prokázaná jednosměrnost, ale praktická nemožnost spočítat reciproční hodnotu pomocí moderních výpočetních prostředků v dohledném časovém intervalu.

Kryptografický systém veřejného klíče RSA je založen na složitosti problému faktorizace součinu dvou velkých prvočísel. Pro šifrování se používá velký počet operací umocňování modulo . K dešifrování (reverzní operaci) v rozumném čase musíte umět vypočítat Eulerovu funkci daného velkého čísla, k čemuž potřebujete znát rozklad čísla na prvočinitele.

V kryptografickém systému s veřejným klíčem má každý účastník jak veřejný klíč ( anglicky public key ), tak soukromý klíč ( anglicky private key ). V kryptografickém systému RSA se každý klíč skládá z dvojice celých čísel. Každý účastník si vytváří svůj vlastní veřejný a soukromý klíč sám. Každý z nich uchovává soukromý klíč v tajnosti a veřejné klíče mohou být sdíleny s kýmkoli nebo dokonce zveřejněny. Veřejné a soukromé klíče každého účastníka zasílání zpráv v kryptosystému RSA tvoří „spárovaný pár“ v tom smyslu, že jsou vzájemně inverzní , tj.:

\pro všechny

platné páry veřejného a soukromého klíče

(p,s)

\exists

odpovídající šifrovací a dešifrovací funkce tak, že

E_{p} (x)

D_{s} (x)

\pro všechny

zprávy , kde je množina přípustných zpráv,

m\in M

M

m=D_{s}(E_{p}(m))=E_{p}(D_{s}(m)).

Algoritmus pro generování veřejných a soukromých klíčů

Klíče RSA se generují následovně [15] :

1) jsou vybrána dvě různá náhodná prvočísla a daná velikost (například každé 1024 bitů );

p

q

2) vypočítá se jejich součin , který se nazývá modul ;

n=p\cdot q

3) hodnota Eulerovy funkce se vypočítá z čísla :

n

\varphi (n)=(p-1)\cdot (q-1)

; 4) je vybráno celé číslo ( ), které odpovídá hodnotě funkce ;

E

1<e<\varphi(n)

\varphi (n)

číslo se nazývá veřejný exponent ; _

E

obvykle berou jako prvočísla obsahující malý počet jednotlivých bitů v binárním zápisu , například prvočísla z Fermatových čísel : 17, 257 nebo 65537, protože v tomto případě bude čas potřebný pro šifrování pomocí rychlého umocňování kratší;

E

hodnoty, které jsou příliš malé , jako například 3, mohou potenciálně oslabit zabezpečení schématu RSA. [16] ;

E

5) vypočítá se číslo , které je multiplikativně inverzní k číslu modulo , tedy číslo, které vyhovuje srovnání :

d

E

\varphi (n)

d\cdot e\equiv 1{\pmod {\varphi (n)))

(číslo se nazývá tajný exponent ; obvykle se počítá pomocí rozšířeného Euklidova algoritmu );

d

6) pár je zveřejněn jako veřejný klíč RSA ( veřejný klíč RSA );

(e,n)

7) dvojice hraje roli soukromého klíče RSA a je držena v tajnosti .

(d,n)

Šifrování a dešifrování

Předpokládejme, že Bob chce poslat zprávu Alici . $m$

Zprávy jsou celá čísla v rozsahu od do , coprime až n, tzn. . $0$ $n-1$ $m\in \mathbb {Z} _{n},\gcd(m,n)=1$

Šifrovací algoritmus [15] :

Získejte Alicin veřejný klíč $(e,n)$
Vezměte prostý text $m$
Zašifrujte zprávu pomocí veřejného klíče Alice: $c=E(m)=m^{e}\mod n~~~~(1)$

Algoritmus dešifrování :

Příjem zašifrované zprávy $C$
Vezměte si svůj soukromý klíč $(d,n)$
Použijte soukromý klíč k dešifrování zprávy: $m=D(c)=c^{d}\mod n~~~~(2)$

Toto schéma se v praxi nepoužívá z důvodu, že není prakticky spolehlivé (sémanticky zabezpečeno). Jednosměrná funkce E(m) je skutečně deterministická — se stejnými hodnotami vstupních parametrů (klíč a zpráva) produkuje stejný výsledek. To znamená, že není splněna nezbytná podmínka pro praktickou (sémantickou) spolehlivost šifry.

Algoritmus šifrování klíče relace

V současnosti nejpoužívanější[ kdy? ] je smíšený šifrovací algoritmus, ve kterém je klíč relace nejprve zašifrován a poté jej účastníci používají k šifrování svých zpráv pomocí symetrických systémů. Po ukončení relace je klíč relace obvykle zničen.

Algoritmus šifrování klíče relace je následující [17] :

Algoritmus :

Získejte Alicin veřejný klíč $(e,n)$
Vygenerujte náhodný klíč relace $m$
Zašifrujte klíč relace pomocí veřejného klíče Alice: $c=E(m)=m^{e}\mod n$
Zašifrujte zprávu pomocí klíče relace pomocí symetrického algoritmu: $M_{A}$ $C=E_{m}(M_{A})$

Algoritmus :

Přijměte Bobův šifrovaný klíč relace $C$
Vezměte si svůj soukromý klíč $(d,n)$
Použijte soukromý klíč k dešifrování klíče relace: $m=D(c)=c^{d}\mod n$
Dešifrujte zprávu pomocí klíče relace pomocí symetrického algoritmu: $C$ $M_{A}=D_{m}(C)$

V případě, že je klíč relace větší než modul , je klíč relace rozdělen do bloků požadované délky (v případě potřeby doplněn nulami) a každý blok je zašifrován. $n$

Správnost schématu RSA

Rovnice a , na kterých je schéma RSA založeno, definují vzájemně inverzní transformace množiny

(jeden)

(2)

\mathbb {Z} _{n}

Důkaz [15] [18]

Opravdu, pro $\forall m\in \mathbb {Z} _{n}$

D\left({E\left(m\right)}\right)=E\left({D\left(m\right)}\right)=m^{ed}\mod n

Ukažme, že:

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod p

Jsou možné dva případy:

$m\ne \equiv 0\mod p$ .

Protože čísla a jsou vzájemně inverzní vzhledem k násobení modulo , tj $E$ $d$ $\varphi (n)=(p-1)(q-1)$

ed=1+k(p-1)(q-1)

pro nějaké celé číslo ,

k

pak:

{\begin{aligned}m^{ed}&\equiv m^{1+k\left({p-1}\right)\left({q-1}\right)}&\equiv &\mod p \\&\equiv m\left({m^{p-1}}\right)^{k\left({q-1}\right)}&\equiv &\mod p\\&\equiv m\ left(1\right)^{k\left({q-1}\right)}&\ekviv m&\mod p\end{aligned}}

kde druhá identita vyplývá z Fermatovy věty .

Zvažte druhý případ:

m\ekviv 0\mod p

pak

m^{ed}\equiv 0\equiv m\mod p

Tedy pro všechny rovnost $m$

m^{ed}\equiv m\mod str

Podobně lze ukázat, že:

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod q

Potom z čínské věty o zbytku

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod n

Příklad

Etapa	Popis operace	Výsledek operace
Generování klíčů	Vyberte dvě různá prvočísla	$p=3557$ , $q=2579$
	Vypočítat produkt	$n=p\cdot q=3557\cdot 2579=9173503$
	Vypočítejte Eulerovu funkci	$\varphi (n)=(p-1)(q-1)=9167368$
	Vyberte otevřeného vystavovatele	$e=3$
	Vypočítejte tajný exponent	${\begin{aligned}d&=(k\cdot \varphi (n)+1)/e\\&=(2\cdot 9167368+1)/3\\&=6111579\end{aligned))$
	Publikovat veřejný klíč	$\{e,n\}=\{3.9173503\}$
	Uložit soukromý klíč	$\{d,n\}=\{6111579,9173503\}$
Šifrování	Vyberte text, který chcete zašifrovat	$m=111111$
Šifrování	Vypočítejte šifrový text	${\begin{aligned}c&=E(m)\\&=m^{e}\mod n\\&=111111^{3}\mod 9173503\\&=4051753\end{aligned}}$
Dešifrování	Vypočítejte původní zprávu	${\begin{aligned}m&=D(c)=\\&=c^{d}\mod n\\&=4051753^{6111579}\mod 9173503\\&=111111\end{aligned}}$

Digitální podpis

Systém RSA lze použít nejen pro šifrování, ale také pro digitální podpis .

Předpokládejme, že Alice (strana ) potřebuje poslat Bobovi (strana ) zprávu potvrzenou elektronickým digitálním podpisem . $A$ $B$ $m$

Algoritmus :

Vezměte prostý text $m$
Vytvořte digitální podpis pomocí svého soukromého klíče : $s$ $\left\{d,n\right\}$

s=S_{A}\left(m\right)=m^{d}\mod n

Pošlete pár sestávající ze zprávy a podpisu. $\left\{m,s\right\}$

Algoritmus :

Přijměte pár $\left\{m,s\right\}$
Získejte Alicin veřejný klíč $\left\{e,n\right\}$
Vypočítejte předobraz zprávy z podpisu:

m'=P_{A}\left(s\right)=s^{e}\mod n

Ověřte pravost podpisu (a neměnnost zprávy) porovnáním a $m$ $m'$

Protože digitální podpis poskytuje jak ověření autora zprávy, tak důkaz integrity obsahu podepsané zprávy, je analogický s vlastnoručním podpisem na konci ručně psaného dokumentu.

Důležitou vlastností digitálního podpisu je, že jej může ověřit každý, kdo má přístup k veřejnému klíči jeho autora. Jeden z účastníků výměny zpráv může po ověření pravosti digitálního podpisu přenést podepsanou zprávu někomu jinému, kdo je také schopen tento podpis ověřit. Strana může například straně zaslat elektronický šek. Poté, co strana zkontroluje podpis strany na šeku, může jej převést do své banky, jejíž zaměstnanci mají rovněž možnost podpis zkontrolovat a provést odpovídající peněžní transakci. $A$ $B$ $B$ $A$

Všimněte si, že podepsaná zpráva není zašifrována . Je zasílán v původní podobě a jeho obsah není chráněn před porušením soukromí. Kombinací výše uvedených schémat šifrování a digitálního podpisu může RSA vytvářet zprávy, které jsou šifrované i digitálně podepsané. K tomu musí autor ke zprávě nejprve přidat svůj digitální podpis a poté výsledný pár (skládající se ze samotné zprávy a podpisu k ní) zašifrovat pomocí veřejného klíče patřícího příjemci. Příjemce přijatou zprávu dešifruje pomocí svého soukromého klíče [17] . Nakreslíme-li analogii se zasíláním běžných papírových dokumentů, pak je tento proces podobný, jako kdyby pod něj autor dokumentu vložil pečeť a následně ji vložil do papírové obálky a zalepil tak, aby obálku otevřel pouze osoba, které byla zpráva určena. $m$

Rychlost algoritmu RSA

Protože ke generování klíčů dochází mnohem méně často než k operacím, které implementují šifrování, dešifrování a také vytváření a ověřování digitálního podpisu, představuje výpočetní úloha hlavní výpočetní složitost. Tento problém lze vyřešit pomocí rychlého umocňovacího algoritmu . Pomocí tohoto algoritmu vyžaduje výpočet operace násobení modulo [19] . $a=b^{c}{\bmod {n))$ $m^{e}{\bmod {n))$ $O\left(\ln e\vpravo)$

Více

reprezentovat ve dvojkové soustavě: $E$

e=e_{k}\cdot 2^{k}+e_{k-1}\cdot 2^{k-1}+\tečky +e_{1}\cdot 2+e_{0}

, kde

e_{k}=1,e_{i}\v \left\{0,1\right\}

nastavit a poté vypočítat pro $m_{0}=m$ $i=1,\tečky,k$

m_{i}=\left(m_{i-1}^{2}\cdot m^{e_{ki}}\right){\bmod {n}}

nalezen a bude mít požadovanou hodnotu $m_{k}$ $m^{e}{\bmod {n))$

Protože každý výpočet v kroku 2 nevyžaduje více než tři modulonásobení a tento krok se provádí jednou, složitost algoritmu lze odhadnout hodnotou . $n$ $k\leq \log _{2}e$ $O(\ln e)$

Chcete-li analyzovat dobu provádění operací s veřejnými a soukromými klíči, předpokládejme, že veřejný klíč a soukromý klíč splňují vztahy , . Poté se v procesech jejich aplikace provádějí i modulonásobení , resp. $\left\{e,n\right\}$ $\left\{d,n\right\}$ $\log _{2}e=O(1)$ $\log _{2}d\leq \beta$ $O\levý (1\vpravo)$ $O\left(\beta\vpravo)$

Doba provádění operací tedy roste s nárůstem počtu nenulových bitů v binární reprezentaci otevřeného exponentu e . Pro zvýšení rychlosti šifrování se často volí hodnota e rovna 17, 257 nebo 65537 - prvočísla , jejichž binární reprezentace obsahuje pouze dvě jednotky :

Podle heuristických odhadů se délka tajného exponentu , která závisí netriviálním způsobem na otevřeném exponentu a modulu , s vysokou pravděpodobností blíží délce . Proto je dešifrování dat pomalejší než šifrování a ověřování podpisu je rychlejší než jeho vytváření. $d$ $E$ $n$ $n$

Algoritmus RSA je mnohem pomalejší než AES a další algoritmy, které používají symetrické blokové šifry .

Použití čínské věty o zbytku k urychlení dešifrování

Při dešifrování nebo podepisování zprávy v algoritmu RSA bude vypočítaný exponent poměrně velký počet (řádově 1000 bitů). Proto je vyžadován algoritmus, který snižuje počet operací. Protože čísla a v rozkladu jsou vlastníkovi soukromého klíče známy, můžeme vypočítat: $p$ $q$ $N=pq$

m_{p}=C^{d}{\bmod {p}}=C^{d{\bmod {p-1}}}{\bmod {p}},

m_{q}=C^{d}{\bmod {q}}=C^{d{\bmod {q-1}}}{\bmod {q}}.

Vzhledem k tomu , a jsou čísla pořadí , budou tyto operace vyžadovat dvě zvýšení čísla na 512bitové výkonové modulo a 512bitové číslo. To je výrazně (pro 1024bitové testování ukázalo 3x) rychlejší než jedno zvýšení na 1024bitový modul napájení 1024bitového čísla. Dále zbývá obnovit a co lze udělat pomocí čínské věty o zbytku [20] . $p$ $q$ $2^{512},$ $m$ $m_{p}$ $m_{q},$

RSA kryptoanalýza

Síla algoritmu je založena na složitosti výpočtu inverzní funkce k šifrovací funkci [21]

c=E(m)=m^{e}\mod n

Chcete-li vypočítat ze známých , musíte najít takové , že $m$ $c,e,n$ $d$

e\cdot d\equiv 1{\pmod {\varphi (n))),

to znamená najít inverzní prvek k v multiplikativní skupině zbytků modulo $E$ $\varphi(n).$

Výpočet inverzního modulu není obtížný, ale útočník nezná hodnotu . K výpočtu Eulerovy funkce známého čísla potřebujete znát rozklad tohoto čísla na prvočinitele. Najít takové faktory je obtížný úkol a znalost těchto faktorů je „tajné dveře“ ( anglicky backdoor ), které používá pro výpočet majitel klíče. Existuje mnoho algoritmů pro hledání prvočinitelů, tzv. faktorizace , z nichž nejrychlejší je dnes metoda obecného číselného pole síta , jejíž rychlost pro k-bitové celé číslo je $\varphi (n)$ $n$ $d$

\exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k)

pro některé .

c<2

V roce 2010 skupina vědců ze Švýcarska, Japonska, Francie, Nizozemska, Německa a Spojených států úspěšně vypočítala data zašifrovaná pomocí 768bitového kryptografického klíče RSA. Zjištění prvočinitelů bylo provedeno obecnou metodou číselného pole síta [22] . Podle vědců lze po jejich práci považovat za spolehlivý šifrovací systém pouze klíče RSA s délkou 1024 bitů a více. Navíc by mělo být v příštích třech až čtyřech letech opuštěno šifrování s klíčem 1024 bitů [23] . Od 31. prosince 2013 již prohlížeče Mozilla nepodporují certifikáty CA s klíči RSA menšími než 2048 bitů [24] .

Navíc, když je algoritmus nesprávně nebo neoptimálně implementován nebo používán, jsou možné speciální kryptografické útoky, jako jsou útoky na schémata s malým tajným exponentem nebo schémata se společnou zvolenou hodnotou modulu.

Útoky na algoritmus RSA

Wienerův útok na RSA

Některé aplikace potřebují urychlit proces dešifrování v algoritmu RSA. Proto je zvolen malý dešifrovací exponent. V případě, kdy lze dešifrovací exponent určit v polynomiálním čase pomocí Wienerova útoku [20] na základě spojitých zlomků . $d<N^{\frac {1}{4}}$ $d$

Více Vzhledem k reálnému číslu definujeme posloupnosti:

\alpha \in \mathbb {R}

$\alpha _{0}=\alpha ,p_{0}=q_{0}=1,p_{1}=a_{0}a_{1}+1,q_{1}=a_{1},$
$\alpha _{i}=\lpatro \alpha _{i}\rpatro ,\alpha _{i+1}={\frac {1}{\alpha _{i}-a_{i}}},$
$p_{i}=a_{i}p_{i-1}+p_{i-1}$ v $i\geq 2,$

q_{i}=a_{i}q_{i-1}+q_{i-1}

i\geq 2.

Celá čísla se nazývají pokračující zlomky , které představují racionální čísla jako konvergenty. Každý z vhodných zlomků je neredukovatelný a rychlost růstu jejich jmenovatelů je srovnatelná s exponenciální. Jeden z důležitých výsledků teorie spojitých zlomků : $a_{0},a_{1},a_{2},...$ $\alpha ,$ ${\frac {p_{i}}{q_{i}}}-$

Pokud neredukovatelný zlomek splňuje nerovnost:

{\frac {p}{q))

\left|\alpha -{\frac {p}{q}}\right|\leq {\frac {1}{2q^{2}}},

pak jeden z konvergentů v expanzi pokračujícího zlomku . ${\frac {p}{q}}-$ $\alpha$

Předpokládejme, že máme modul a dáme útočníkovi vědět exponent šifrování E, který má tuto vlastnost

N=pq,

q<p<2q.

Ed=1\mod \varphi,

kde Budeme také předpokládat, že protože to platí pro většinu aplikací. Z předpokladů vyplývá, že

\varphi =\varphi (N)=(p-1)(q-1).

E<\varphi,

Ed-k\varphi=1.

Tudíž,

$\left|{\frac {E}{\varphi }}-{\frac {k}{d}}\right|={\frac {1}{d\varphi }}.$

\left|N-\varphi \right|=\left|p+q-1\right|<3N^{\frac {1}{2}}.

To ukazuje, že docela dobrá aproximace pro Indeed,

{\frac {E}{N}}-

{\frac {k}{d}}.

\left|{\frac {E}{N}}-{\frac {k}{d}}\right|=\left|{\frac {Ed-Nk}{dN}}\right|=\left| {\frac {Ed-k\varphi -Nk+k\varphi }{dN}}\right|=\left|{\frac {1-k(N-\varphi )}{dN}}\right|\leq \left|{\frac {3kN^{\frac {1}{2}}}{dN}}\right|={\frac {3k}{dN^{\frac {1}{2}}}}.

Protože je zřejmé , že se také předpokládalo, že znamená, $E<\varphi,$ $,k<d.$ $d<{\frac {1}{4}}N^{\frac {1}{4}}.$

\left|{\frac {E}{N}}-{\frac {k}{d}}\right|<{\frac {1}{2d^{2}}}.

Protože gcd je konvergentní v expanzi zlomku na spojitý . Dekódovací exponent tedy zjistíte střídavým dosazováním jmenovatelů vhodných zlomků do výrazu: $(k,d)=1,$ ${\frac {k}{d}}-$ ${\frac {E}{N}}$

(M^{E})^{d}=M\mod N

pro nějaké náhodné číslo Po získání rovnosti zjistíme, že celkový počet vhodných zlomků, které bude třeba zkontrolovat, se odhaduje jako $M.$ $d.$ $O(logN).$

Generalizovaný Wienerův útok

Výše popsaný Wienerův útok je možný pouze v případě, že si útočník je vědom nerovnosti

d\leq {\frac {1}{3}}N^{\frac {1}{4}},

kde je tajný exponent a je modul RSA. Bonnet a Derfey pomocí dvourozměrné analogie Coppersmithovy věty dokázali zobecnit Wienerův útok [20] na případ, kdy $d$ $N$

d\leq N^{0,292}.

Aplikace RSA

Systém RSA se používá pro ochranu softwaru a ve schématech digitálního podpisu .

Používá se také v otevřeném šifrovacím systému PGP a dalších šifrovacích systémech (například DarkCryptTC a formát xdc) v kombinaci se symetrickými algoritmy .

Kvůli nízké rychlosti šifrování jsou zprávy obvykle šifrovány pomocí efektivnějších symetrických algoritmů s náhodným klíčem relace (například AES , IDEA , Serpent , Twofish ), a pouze tento klíč je šifrován pomocí RSA, je tedy implementován hybridní kryptosystém . Takový mechanismus má potenciální zranitelnost kvůli potřebě použít kryptograficky silný generátor pseudonáhodných čísel pro generování náhodného symetrického šifrovacího klíče relace.

Poznámky

↑ Po letech útoků stále střeží tajemství, RSA získává uznání pro své zakladatele – Společnost pro průmyslovou a aplikovanou matematiku .
↑ Úvod do moderní kryptografie (anglicky) - 2 - CRC Press , 2015. - S. 411. - 583 s. — ISBN 978-1-4665-7026-9
↑ 1 2 Bakhtiari, Maarof, 2012 , str. 175.
↑ Čtvrtletí rekreační matematiky, Martin Gardner (anglicky) (odkaz není k dispozici) . Scientific American. — „Ronald L. Rivest z Massachusettského technologického institutu mi umožnil být prvním, kdo odhalil – ve sloupci ze srpna 1977 – šifrovací systém „publicky“, který spoluvynalezl.“ Získáno 3. března 2012. Archivováno z originálu dne 23. června 2012.
↑ 12 Gardner , 1977 .
↑ Bruce Schneier. Factoring - State of the Art and Predictions (anglicky) (nedostupný odkaz) (12. února 1995). Získáno 3. března 2012. Archivováno z originálu dne 23. června 2012.
↑ Donald T. Davis. Diskuse o aktivitě RSA-129 (anglicky) (odkaz není k dispozici) (25. listopadu 2003). Získáno 3. března 2012. Archivováno z originálu dne 23. června 2012.
↑ Chmora A. L. 4.6.4. Power attack založený na distribuovaných výpočtech // Moderní aplikovaná kryptografie. - 2002. - 2000 výtisků. — ISBN 5-85438-046-3 .
↑ Rivest, Shamir, Adleman, 1978 .
↑ Ronald L. Rivest a kol. Kryptografický komunikační systém a metoda
↑ Adam Zpět. PGP Timeline (anglicky) (downlink) . Získáno 3. března 2012. Archivováno z originálu dne 23. června 2012.
↑ J. Linn. Vylepšení soukromí pro internetovou elektronickou poštu: Část III – Algoritmy, režimy a identifikátory (anglicky) (odkaz není k dispozici) (srpen 1989). Získáno 18. března 2012. Archivováno z originálu dne 23. června 2012.
↑ RSA Security Inc. Historie společnosti (anglicky) (odkaz není k dispozici) . Financování vesmíru. Získáno 18. března 2012. Archivováno z originálu dne 23. června 2012.
↑ CC Cocks A note on "non-secret encryption" Archivováno z originálu 4. srpna 2009. (anglicky) 20. listopadu 1973
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996 , 8.2. Šifrování veřejného klíče RSA.
↑ Boneh, 1999 .
↑ 1 2 Bruce Schneier. Aplikovaná kryptografie 2. vydání C++ protokolů, algoritmů a zdrojů
↑ Rivest, Shamir, Adleman, 1978 , pp. 7-8.
↑ Rivest, Shamir, Adleman, 1978 , str. osm.
↑ 1 2 3 H. SMART Svět programování Kryptografie - ed. Technosféra, Moskva 2006
↑ Yang S. Y. Kryptoanalýza RSA. - M.-Iževsk: Výzkumné centrum "Regulární a chaotická dynamika", Iževský institut počítačového výzkumu, 2011. - 312 s.
↑ Oznámení faktorizace RSA-768 Archivováno 13. dubna 2014 na Wayback Machine
↑ Faktorizace RSA-768 Archivováno 13. prosince 2012 na Wayback Machine
↑ Data pro postupné vyřazování signatur založených na MD5 a 1024bitových modulů . Získáno 2. března 2013. Archivováno z originálu dne 20. listopadu 2012. (neurčitý)

Literatura

Diffie W. , Hellman M. E. Nové směry v kryptografii // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1976. - Sv. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 – doi:10.1109/TIT.1976.1055638
Gardner M. Nový druh šifry, jejíž prolomení by trvalo miliony let // Sci . amer. - NYC : NPG , 1977. - Sv. 237, Iss. 2. - S. 120-124. — ISSN 0036-8733 ; 1946-7087 - doi:10.1038/SCIENTIFICAMERICAN0877-120
Rivest R. , Shamir A. , Adleman L. Metoda pro získávání digitálních podpisů a kryptosystémů s veřejným klíčem (anglicky) // Commun. ACM - [New York] : Association for Computing Machinery , 1978. - Sv. 21, Iss. 2. - S. 120-126. — ISSN 0001-0782 ; 1557-7317 – doi:10.1145/359340.359342
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (anglicky) - CRC Press , 1996. - 816 s. — ( Diskrétní matematika a její aplikace ) — ISBN 978-0-8493-8523-0
Boneh D. Dvacet let útoků na kryptosystém RSA // Notices Amer . Matematika. soc. / F. Morgan - AMS , 1999. - Sv. 46, Iss. 2. - S. 203-213. — ISSN 0002-9920 ; 1088-9477
Bakhtiari M. , Maarof M. A. Vážná bezpečnostní slabina v RSA Cryptosystem (anglicky) // IJCSI - 2012. - Vol. 9, Iss. 1, č. 3. - S. 175-178. — ISSN 1694-0814 ; 1694-0784

Nils Ferguson , Bruce Schneier . Praktická kryptografie = Praktická kryptografie: Navrhování a implementace bezpečných kryptografických systémů. - M . : Dialektika, 2004. - 432 s. - 3000 výtisků. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta