înregistrare Logare
Puncte:1
Marth83 avatar Crypto

RSA: factor comun între M și n

drapel cn
Marth83

Să presupunem că avem o criptare RSA clasică, cu n = p*q. Pentru un anumit C, am văzut pe internet că RSA ar putea fi slab dacă știm că textul simplu M și n au un factor comun. Cu toate acestea, nu am reușit să găsesc o dovadă în acest sens.

Noi stim aia $M=C^e \space mod\;n$, cu e cheia publică. Am încercat să spun asta $M = a + k*n$, cu a și k fiind numere întregi pozitive și să refacem algoritmul. Prin urmare:

$C = M^e\;mod\;n = (a + k*n)^e\;mod\;n = a^e\;mod\;n$

Și

$M = C^d\;mod\;n = a^{d*e}\;mod\;n$

Cu toate acestea, acest lucru sună inutil, deoarece nu cunoaștem un (chiar și cu o forță brutală, am avea prea multe valori de calculat dacă $n$ este mare) și $d$, evident, deoarece este cheia privată. Ma poate ajuta cineva cu aceasta?

83
0 + 0
Puncte:3
poncho avatar Crypto
drapel my
poncho

Pentru un anumit C, am văzut pe internet că RSA ar putea fi slab dacă știm că textul simplu M și n au un factor comun. Cu toate acestea, nu am reușit să găsesc o dovadă în acest sens.

Este destul de simplu; le cunoaștem pe amândouă $C$ și $n$; dacă $M$ are un factor comun cu $n$, la fel $C$. Deci, putem doar să calculăm $\gcd(C, n)$. Din moment ce știm asta $M$ și $n$ au un factor comun, atunci acesta nu este 1; presupunem că $C < n$, deci nu este $n$. Prin urmare, acesta trebuie să fie un factor adecvat $n$; dacă $n$ este un produs de două numere prime, acesta va fi apoi unul dintre ele și, deci, cei doi factori primi ai $n$ sunt atunci $\gcd(C, n)$ și $n / \gcd(C, n)$.

Odată ce avem factorizarea lui $n$ apoi (presupunând că știm valoarea $e$), tehnica de calcul $d$ este direct.

0 + 0
poncho avatar
drapel my
poncho
@Marth83: mai bine?
0
Răspunde
Marth83 avatar
drapel cn
Marth83
Da, asta mă întrebam, mulțumesc!
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.