PRUDENȚĂ: Este ceva atât de greșit în întrebare încât este rezonabil să o respingem, vezi a doua secțiune. Dar mai întâi să încercăm să răspundem de parcă nu am observat.
Într-una dintre mai multe definiții ușor diferite ale manualului RSA,
- cheia privată (folosită pentru decriptare de către deținătorul cheii) este $(d,n)$
- cheia publică (folosită pentru criptare de către oricine) este $(e,n)$,
- text simplu $m$ și text cifrat $c$ sunt numere întregi în interval $[0,n-1]$,
- $n$, $d$ și $e$ sunt aleşi astfel¹ încât pentru toţi $m$ în intervalul respectiv putem calcula
- $c:=m^e\bmod n$ pentru criptare, atunci
- $m':=c^d\bmod n$ pentru decriptare, cedare $m'=m$.
În cele de mai sus$\bmod$este un operator cu două argumente, astfel încât $x\bmod n$ este întregul definit în mod unic $y$ cu $0\le y<n$ și $x-y$ un multiplu de $n$. Când $x\ge0$ și $n>0$, acea $y$ este restul diviziunii euclidiene a $x$ de $n$. Intervalul $[0,n-1]$ în definiția de mai sus a RSA este pentru că este intervalul pentru restul din diviziunea euclidiană.
Întrebarea cere cel mai mare număr întreg $m$ care se produce atunci când este criptat, apoi decriptat. Cheile date arată asta $n=27$; astfel răspunsul (cel mult) este $m=n-1=27-1=26$. Este logic să verificăm că acest lucru $m$ este corect criptat și decriptat pentru întrebările $d=5$ și $e=13$ prin definiția de mai sus a RSA. Această dovadă este ușoară: avem $m\equiv-1\pmod n$, și $e$ și $d$ sunt ciudate, deci $c\equiv(-1)^e\equiv-1\pmod n$, prin urmare $m'\equiv(-1)^d\equiv-1\pmod n$, prin urmare $m'=c=m=n-1$ deoarece acesta este singurul întreg $y$ în $[0,n-1]$ cu $y\equiv-1\pmod n$.
Notă: în cele de mai sus $y\equiv x\pmod n$ mijloace: $x-y$ este un multiplu diferit de zero $n$. În această utilizare$\bmod$nu este un operator cu două argumente, așa cum arată paranteza din stânga imediat din stânga sa; mai degraba,$\pmod n$ califică pe $\echiv$ semn(e) din stânga, care este/sunt modulo de echivalență $n$.
Există cel puțin o problemă serioasă în întrebare: majoritatea numerelor întregi $m$ în interval $[0,26]$ nu va descifra corect după criptare! Dacă cineva îi pasă să încerce, doar $0$, $1$ și $26$ fă așa (ei fac orice ciudat $e$ și $d$ sunt aleși). Mai departe, toate $m$ multiplu de $3$ cifra la aceeași $c=0$, astfel printre acestea cel mult se poate descifra corect.
Problema nu este doar atat $e$ și $d$ nu se potrivesc pentru asta $n$. Problema este că pentru RSA să funcționeze pentru toți $m$ in raza de actiune $[0,n-1]$ este necesar ca $n$ este fără pătrat, adică nu este divizibil cu pătratul oricărui prim; altfel spus, niciun prim nu va apărea de două ori în factorizarea lui $n$. Dar aici $27$ este divizibil cu $3^2$. Fără acea condiție fără pătrat, pentru ciudat $n$, încă se poate alege $e$ și $d$ astfel încât decriptarea funcționează pentru majoritatea $m$. Dar în cazul de față, $e$ și $d$ nici măcar nu se potrivesc cu condiția¹ pentru asta. O posibilitate este ca întrebarea să fi fost pusă inițial $n=51$, care face $d=5$, $e=13$ lucru; apoi nepăsător schimbat în $n=27$.
Merge mai rău decât $(d,n)$ și $(e,n)$ parametrii din întrebare nu sunt validi pentru RSA: orice parametru RSA de dimensiune similară nu permite secret împărtășește orice.
RSA poate fi securizat numai dacă $n$ este greu de factorizat, ceea ce necesită sute de cifre zecimale. Prin urmare, orice exercițiu cu mai mici $n$ este despre o instanțiere nesigură a RSA atunci când se confruntă cu adversari competenți cu un computer. Punctul meu de vedere este că în exemplele pedagogice RSA $n$ ar trebui să fie suficient de mare încât să existe o oarecare dificultate în factorul manual. De asemenea, trebuie subliniat că criptarea deterministă RSA cu text simplu într-un set mic (de exemplu, un interval mic sau un nume pe lista de clasă) este nesigură, deoarece se poate încerca să descifreze toate textele clare.
De asemenea, „criptosistemul bazat pe RSA” este specificat atât de vag încât asumarea RSA de manual ca în prima parte este pură speculație.Acea afirmație a problemei este pur și simplu greșită!
¹ Condiția necesară și suficientă pentru ca manualul RSA să descifreze corect, pentru toate numerele întregi cu text simplu $m$ în $[0,n-1]$ când $n$ este fără pătrat, și cel puțin pentru toate acestea $m$ coprime cu $n$ altfel, este: $e\,d\equiv1\pmod{\lambda(n)}$, Unde $\lambda$ este Funcția Carmichael. Este adesea predat una dintre câteva condiții ușor diferite, care sunt suficiente, dar nu necesare. Printre cele populare se numără $e\,d\equiv1\pmod{\varphi(n)}$, Unde $\varphi$ este Totientul lui Euler; $d=e^{-1}\bmod{\varphi(n)}$, în plus, însemnând $0\le d<\varphi(n)$; $e=d^{-1}\bmod{\varphi(n)}$, folosit în articol original RSA; $d=e^{-1}\bmod{\lambda(n)}$, care dă cel mai mic pozitiv valid $d$ pentru un dat $e$.
