înregistrare Logare
Puncte:6
avatar Crypto

RSA cu exponentul fiind un factor de modul

drapel in
limeeattack

Weekendul acesta am participat la un CTF, dar am dat peste o sarcină pe care nu am reușit să o rezolv. Nu găsesc nicio redacție, așa că sper că mă puteți ajuta.

Dat: $$ n = pq\ c_1\cong m_1^{\hspace{.3em}p} \mod n\ c_2\cong m_2^{\hspace{.3em}q} \mod n $$ Cunoscând valorile $c_1,c_2,n$ și asta $p$ este de 1024 de biți și $q$ este de 1000 de biți, cu $p,q$ fiind prim. Există o modalitate eficientă de recuperare? $m_1,m_2$?

Știu că dacă sunt capabil să-mi revin $p,q$ este banal din cauza teoremei lui Fermat, dar, din nou, această problemă este ceea ce face RSAP greu.

Singura altă informație dată a fost că ambele $m_1,m_2$ au fost de 25 de octeți (200 de biți). Nu exista niciun serviciu care să poată acționa ca un oracol.

489
0 + 0
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Vă rugăm să rețineți că, în calitate de CTF, ar trebui să tratăm aceasta ca pe o sarcină și să oferim doar indicii, de preferință în comentarii.
0
Răspunde
drapel in
limeeattack
CTF s-a încheiat, așa că nu l-aș considera o misiune. Dar și sugestiile sunt mai mult decât binevenite.
0
Răspunde
Puncte:5
avatar Crypto
drapel pe
Samuel Neves

Ideea cheie aici este aceea $m_1$ (sau $m_2$) este foarte mic în raport cu modulul. Acest lucru ne permite să aplicăm tehnici obișnuite de Calămar.

Noi stim aia $c_1 = m_1^p \bmod n$, ceea ce presupune $c_1 \equiv m_1 \bmod p$. Din aceasta știm că $c_1 - m_1 = t\cdot p$, pentru unii $t$. Cu alte cuvinte, $\gcd(c_1 - x, n) = p \ge n^{1/2}$ pentru unii $x = m_1 \le n^{1/4}$. Iată așteptările noastre $x = m_1$ este mult mai mic decât $n^{1/4}$, de fapt, ceea ce face lucrurile mai ușor de calculat.

Acest lucru este ușor de reprodus în Sage:

sage: p = random_prime(2^1024, lbound=2^1023+2^1022)                                                                                                          
sage: q = random_prime(2^1000, lbound=2^999+2^998)                                                                                                            
salvie: n = p*q                                                                                                                                                 
salvie:                                                                                                                                                         
sage: m1 = randint(0, 2^200)                                                                                                                                  
sage: m2 = randint(0, 2^200)                                                                                                                                  
sage: c1 = power_mod(m1, p, n)                                                                                                                                
sage: c2 = power_mod(m2, q, n)                                                                                                                                
salvie:                                                                                                                                                         
sage: P.<x> = Zmod(n)[]                                                                                                                                       
sage: f = (c1 - x).monic()                                                                                                                                    
sage: f.small_roots(beta=0,5)                                                                                                                                 
[1106883791702122199703869965196585780508362129433642126297878]
salvie: m1                                                                                                                                                      
1106883791702122199703869965196585780508362129433642126297878

Recuperarea $m_2$ se poate face în același mod, sau prin recuperarea factorilor o dată $m_1$ este recuperatâ$p = \gcd(c_1 - m_1, n)$âși decriptare $m_2$ în mod normal.

0 + 0
Hagen von Eitzen avatar
drapel rw
Hagen von Eitzen
Nu văd din declarația problemei de ce se așteaptă ca $m_1$, $m_2$ să fie mici?
3
Răspunde
AJM avatar
drapel in
AJM
@HagenvonEitzen Într-un comentariu la un alt răspuns, OP scrie: *"Singura alte informații oferite este că ambii m_1,m_2 au 25 de octeți și, desigur, că p,q sunt primii. Nu a existat niciun serviciu care să poată acționa ca un oracol. „* Deoarece aceasta nu a fost într-o întrebare, bănuiesc că cel care a răspuns fie a văzut acel comentariu, fie a întâlnit acest tip de exercițiu CTF în altă parte.
0
Răspunde
drapel pe
Samuel Neves
Corect, am vazut comentariul. Probabil că acesta este și genul de presupunere pe care de obicei trebuie să ghiciți/încercați CTF-urile.
1
Răspunde
Puncte:1
poncho avatar Crypto
drapel my
poncho

Nu cred că, după cum am spus, acea problemă poate fi rezolvată; în concursul CTF, este posibil să fi existat unele informații suplimentare, sau valorile exacte date pentru $n, c_1, c_2$ poate să fi inclus unele slăbiciuni.

Cred că schema Clifford Cox [1] (unde este textul cifrat $m^n \bmod n$ se crede a fi sigur pentru $n$ a factorizării secrete); dacă puteți rezolva problema de mai sus pentru generare $n, c_1, c_2$, iată cum să rupi acea schemă:

  • Dat $c, n$, invocați Oracolul cu $c_1 = c$, și $c_2$ arbitrar; care iti da o valoare $m_1$

  • Apoi, invocați Oracolul din nou cu $c_2 = m_1$ și $c_1$ arbitrar; valoarea $m_2$ care se întoarce va fi decriptarea criptării Cox, adică valoarea $m$ cu $m^n \equiv c$.

[1] sau Cocoși; Am vazut ambele ortografii...

0 + 0
drapel in
limeeattack
Singura altă informație dată este că ambii $m_1,m_2$ au 25 de octeți și, din cauza asta, $p,q$ sunt primii. Nu exista niciun serviciu care să poată acționa ca un oracol.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.