Cum se face o dovadă a corectitudinii formulei de criptare și decriptare RSA pentru $GCD(m_i,n)=1$ și $GCD(m_i,n) \neq1$ unde criptarea este definită ca $c_i = m_{i}^e$ mod n și decriptare $m_i = c_{i}^d$ mod n.
Deci, mulțumesc @poncho pentru sfaturi, am scris următoarea dovadă:
Amintiți-vă că numerele întregi $e > 0$ și $k > 0$ sunt aleși astfel încât
$ ed = 1 + k(p â 1)(q â 1)$
Este suficient să arătăm că cele două congruenţe
$(m^e)^d \equiv m\ \textrm{mod}\ p $ și $(m^e)^d \equiv m\ \textrm{mod}\ q $ tine. p și q sunt numere prime distincte, deci $gcd(p,q) = 1$ iar congruenţele de mai sus implică faptul că
$(m^e)^d \equiv m\ \textrm{mod}\ n $ de teorema chineză a restului. Dacă $m \equiv 0\ \textrm{mod}\ p $, atunci cu siguranță
$(m^e)^d \equiv m\ \textrm{mod}\ p $. Dacă $m \not\equiv 0\ \textrm{mod}\ p $, atunci $m^{p-1} \equiv 1\ \textrm{mod}\ p $ din cauza micii teoreme a lui Fermat ($a^{p-1} \equiv 1\ \textrm{mod}\ p $) prin urmare,
$$ (m^e)^d \equiv m^{1 + k(p - 1)(q - 1)} \equiv m(m^{p-1})^{k(q-1)} \ echiv m 1^{k(q-1)} \equiv m\ \textrm{mod}\ p
$$
Prin urmare $(m^e)^d \equiv m\ \textrm{mod}\ p $ este valabil pentru toate numerele întregi m. Înlocuirea p cu q în argumentul anterior arată că $m \equiv (m^e)^d \textrm{mod}\ q $ este valabil pentru toate numerele întregi m
Orice comentarii despre corectitudinea dovezii mele sunt apreciate!
