RSA

Statja ne dokončena i ne doděłana do normalnogo stanja!!!

RSA (Rivest, Shamir, Adleman) jest kryptografičny algoritm z otvorenym ključem, čja bezopasnost opiraje sę na trudosť faktorizacije velikih poluprostyh čisel.

2017-08-Ron Rivest Adi Shamir and Len Adleman on CRYPTO 2017 in UCSB

Zamysl otkľučevej kryptografije byl pŕvy raz predstavjeny Vitfieldom Diffijem i Martinom Hellmanom v godě 1976. Jednak ne uspěli rěšiti problemu tvorjenja naděždnoj jednostrannoj funkcije. God potěm grupa z Massachusettskogo Technologičnogo Instituta, sostojųća iz Rona Rivesta, Adi Šamira i Leonarda Adlemana, dělala na tvorjenju takoj funkcije. Prělom stal sę v aprilju goda 1977.

Poslanje šifrųjet sę prědstavljanjem jego kako čislo M, podnesenjem M na vseslavno stepenь e, a potym izvlěčenjem ostatka pri děljenju rezultata na vseslavno izdanje n dvoma velikima tajnyma prostyma čislama p i q. Dešifrácia jest podobna; toliko sę koristaje ina, tajna, stepenь d, gdě e · d ≡ 1 (mod (p − 1) · (q − 1)). Bezopasnost sistema čąstečnosťju osnovana na složnosti razloženija na množitele izdanogo dělitelja n.

- A Method for Obtaining Digital Signatures and Public-Key Cryptosystems R.L. Rivest, A. Shamir, and L. Adleman∗

Abstract

Poljzovanje

RSA — jest prvy široko koristany algoritm nesěmětričnoj kriptografije, kotory do sěgodnja jest populjarny v industriji. RSA jest koristana v KEM tako že, jako e-znak, i prostě šifrovana otvorenym ključem.

Algoritm jest uporabjeny v TLS/SSL i certifikatěh bezopastnosti, děl rynka bazovana na krivyh rastet, česo on vse ješče velmi popularny. Česo mnogo certifikacijnyh centrov koristajųt različnymi algoritmami, jest rjada certifikacijnyh centrov (CA), kotory vydajųt certifikaty toliko s RSA. Let’s Encrypt po umolčanju predlagajet RSA.

GnuPG predlagaje RSA standardno. Algoritm jest populjarny dlja elektroničnyh podpisov i jest v mnogih državah standardom podpisov dlja državnyh portalov.

Vzlomy i zraniteľnosti

Ogółny smysl dokazanogo prołoma RSA pri značenjah 2048/4096 bit ne jest v publicnem pristupu, ale sųt dokazy możnosti prołoma 2048 za korotko vręmę na klasičnem kompjuterě i slědstveno ostalnyh za obzrimo pri dostatočnyh moćnostjah i tako že sųt teoretične prołomy na kvantovyh kompjuterah.

Na klasičnyh kompjuterah: Obščaja numerična sita polja, 2 000 jadro-lět na 768 bitov, 2 700 jadro-lět na 829 bitov, teoretičeski 1 500 000 jadro-lět na 1024 bitov.

Važno je, že jadro-lěta sųt smatrane bez FPGA/GPU/ASIC i podobnogo uskorenja na procesorah približno 2.1 GHz na jadro. Tak že v slučaju sųčnosti neophodnoj skrytoj strukturě, što byvajet dovolno často, sųt kuda bolěje efektivne metody.

QuantumComputing

Dlja Šoroveho algoritma treba približno 2n logičnyh kubitov (gde n jest dlžina ključa). Dlja RSA-2048 to jest okolo 4 100 logičnyh kubitov. 1-10 godin.

Algoritm Regeva (Oded Regev, 2023) pozvoljaje umenšiti količstvo potrebnyh logičnyh kubitov od c 2n do korenj n.

Čisty algoritm i podmnožestva

Napad pri malem ukazatelju e

Širokověščatelny napad Hastada (Hastad's Broadcast Attack)

Sųt': Jestli že samyj posyl M šifrųje sę malym ukazatelem e (na primer, e = 3) několiko adresatam s različnymi moduljami N₁, N₂, N₃, to protivnik možet vosstanoviti otkrųty tekst bez znanja zakrųtyh ključev.

Kako dějstvuje napad pri e = 3

Predložim, tri uporabitelja imajųt otkrųte ključe (N₁, 3), (N₂, 3), (N₃, 3) i dobivajųt jediny posyl M:

C₁ ≡ M³ (mod N₁)

C₂ ≡ M³ (mod N₂)

C₃ ≡ M³ (mod N₃)

Protivnik presrětajet vse tri šifroteksty. Po kitajskoj teoremi o ostatkah (CRT) možno najti C takoje, že:

C ≡ M³ (mod N₁ × N₂ × N₃)

Odže M < každygo iz N₁, N₂, N₃, to M³ < N₁ × N₂ × N₃.

Sledovatelno: C = M³ (jako obyčajne cělo čislo, ne po modulu)

Protivnik prosto izčislja M = ∛C — kubičny korěń, i otkryvaje posyl.

Primer s konkretnymi čislami

Nehaj tri modulja:

N₁ = 3233, N₂ = 2737, N₃ = 4087

e = 3 za vse

M = 42

Šifroteksty:

C₁ ≡ 42³ ≡ 74088 ≡ 2587 (mod 3233)

C₂ ≡ 42³ ≡ 74088 ≡ 614 (mod 2737)

C₃ ≡ 42³ ≡ 74088 ≡ 2084 (mod 4087)

Po CRT nahodimo C ≡ 74088 (mod 3233 × 2737 × 4087 ≈ 43 mln)

Odže 74088 < 43 mln, to C = 74088 = 42³.

Izčisljajemo: ∛74088 ≈ 42.00 → M = 42 ✓

Napadi pri slabih p i q

1. Blizki prosti čisla (Fermatova faktorizacija)

Ujazvimość: Jesli p i q sų blizki jedne k drugomu, možno bystro faktorizovati N.

Kako delaje:

Jesli p ≈ q, to N ≈ (p + q)² / 4, značit p + q ≈ 2√N.

Iščemo predstavo: N = x² - y², gde x = (p + q)/2, y = (p - q)/2

Togda: p = x - y, q = x + y

Algoritm Fermata:

Načinajemo s x = ⌈√N⌉

Vypočitajem y² = x² - N

Prověřajem, li jest y² cěly kvadrat

Jesli da, našli p i q; jesli ne, povećajemo x i povtorjajemo

Priměr:

N = 91 = 7 × 13

√91 ≈ 9.54, načinajemo s x = 10

y² = 100 - 91 = 9 = 3² ✓

p = 10 - 3 = 7, q = 10 + 3 = 13

Pri p ≈ q algoritm nahodi rěšenje za několiko iteracij vměsto eksponencialnogo vremene.

2. p - 1 i q - 1 imajų toliko male dělitele (Pollardov p - 1)

Ujazvimość: Jesli vse prosti dělitele (p - 1) ili (q - 1) sų mali, možno faktorizovati N efektivno.

Kako delaje:

Po těoremě Fermata: a^(p-1) ≡ 1 (mod p) za vse a, ne dělajuće sę na p.

Jesli p - 1 = ∏ rᵢ^αᵢ, gde vse rᵢ sų mali, vypočitajem:

B = ∏ rᵢ^(⌊log(limit)/log(rᵢ)⌋)

gde limit — někotoro čislo (na priměr, 10⁶).

Togda: a^B ≡ 1 (mod p), no a^B ≢ 1 (mod q) (věrojatno).

Vypočitajem: gcd(a^B - 1, N) — to dasto dělitelja N.

Priměr:

p = 1000000007 (prosto čislo)

p - 1 = 1000000006 = 2 × 500000003

Jesli 500000003 — takože produkt malyh prostyh, algoritm Pollarda děłaje za O(√(maks. malogo dělitelja)).

SNFS

SNFS jest efektivny toliko za čisla vida $n=r^{e}\pm s$, gdě koeficienty r i s sųt velmi mali. K takim čislam prinadležųt:

*   Mersennovy čisla ($2^{p}-1$).

*   Fermatovy čisla ($2^{2^{n}}+1$).

*   Čisla iz projekta Kanningema (na primer, $10^{211}-1$).

Jestli čislo n ne imaje takų strukturu, SNFS ne jest možno upotrebiti, i nado koristovati se pomalšnym GNFS.

Univerzalne ataki

Napad bazovany na cikličnom povtorjenju šifrovanija

V RSA procesě šifrovanja izgleda tako:

$C=M^{e}{\pmod {n}}$

Ako my načnemo povtorno šifrovati polučenyj šifrovaný tekst С, to my budemo polučati poslědovnosť:

1. $C_{1}=C^{e}{\pmod {n}}$

2. $C_{2}=C_{1}^{e}=C^{e^{2}}{\pmod {n}}$

3. ...

4. $C_{j}=C_{j-1}^{e}=C^{e^{j}}{\pmod {n}}$

Jakože čislo elementov v kolci $\mathbb {Z} _{n}$ je konečno, ta poslědovnosť obavezno zacykli sę. Jak toliko my najdemo takoje $j$, pri ktorom $C_{j}\equiv C{\pmod {n}}$, to bude značiti:

$(C_{j-1})^{e}\equiv C{\pmod {n}}$

Poněže po definiciji RSA $M^{e}\equiv C{\pmod {n}}$, to $M=C_{j-1}$.

1. Zašifrovanje:

$C=M^{e}{\pmod {n}}=123456^{49}{\pmod {553429}}=1603$.

2. Iskanje cikla:

Protivnik vyčislja $C_{j}=C^{e^{j}}{\pmod {n}}$:

$C_{1}=1603^{49}{\pmod {553429}}=\dots$

... (srednje kroky)

$C_{7}=1603^{49^{7}}{\pmod {553429}}=85978$

$C_{8}=85978^{49}{\pmod {553429}}=123456$.

$C_{9}=123456^{49}{\pmod {553429}}=1603$.

3. Rezultat:

V sųčasnyh sistemah RSA koristajų sę ogromny prosty čisla ($p$ i $q$ po 1024-2048 bitov). V tomto pripadě: Dĺžka cikla $j$ čęsto srovniva ję s razměrom dělitelev $\phi (n)$. Za slučajno poslannje $M$ věrojatnosť najti korotky cikl (jako $j=9$ v primerě) je ništožno mala. Vyčislitelna složnosť takogo perebora staje sę vyšja, něž složnosť faktorizacije modula $n$.

Ta metod je opasen toliko pri koristovanju "slabyh" prostyh čisel, u ktoryh značenja $p-1$ i $q-1$ imajų toliko male prosty dělitele (gladky čisla).