Pentru un număr întreg fix $n\ge2$, putem defini un relație de echivalență în inel $(\mathbb Z,+,\cdot)$. Această relație este cunoscută sub numele de „modulo de congruență $n$", "modulo de egalitate $n$", sau "modulo de echivalență $n$". Se notează $u\equiv v\pmod n$ când numere întregi $u$ și $v$ sunt în relația respectivă, adică
- $u$ și $v$ sunt astfel încât $v-u$ este un multiplu de $n$
- adică există un număr întreg $k$ astfel încât $v-u=k\,n$.
iar relația de echivalență menționată este utilizată pentru a construi inel clasa reziduurilor $\mathbb Z/nZ$, care (în cripto) este adesea notat $(\mathbb Z_n,+,\cdot)$ sau doar $\mathbb Z_n$.
$v\bmod n$, fără paranteză imediat în stânga lui$\bmod$ nici $\echiv$ semn la același nivel al expresiei, poate fi definit ca cel mai mic membru nenegativ al mulțimii infinite de numere întregi $u$ cu $u\equiv v\pmod n$. Tine $u=v\bmod n$, Unde$\bmod$ este operator.
Notația $y=x^e\bmod n$ implică $0\le y<n$, dar $y\equiv x^e\pmod n$ nu. Prin urmare $y=x^e\bmod n$ definește un întreg unic $y$ ca o funcție a $x$, $e$ și $n$, când $y\equiv x^e\pmod n$ nu.
Ieșirea funcției de criptare RSA (manual/raw). $x\mapsto y=x^e\bmod n$ (cu $x$ un număr întreg și $0\le x<n$, care presupun în toate cele care urmează) este un întreg definit în mod unic $y$, de marime cel mult cea de $n$. În special (pentru $n>2$ și $e>1$) acea funcție nu se poate întoarce pur și simplu $y=x^e$ pentru toți $x$, care $y\equiv x^e\pmod n$ permite.
Diferența contează pentru că $x\mapsto y=x^e$ este o funcție care este ușor de inversat (prin extragerea unui $n^\text{th}$ rădăcină în numere întregi); dar cu $n$ și $e$ aleasă corect pentru RSA, funcția (inversibilă matematic). $x\mapsto y=x^e\bmod n$ se presupune că este greu de inversat din punct de vedere computațional dat $n$, $e$, și aleatoriu $y$ sau $y$ pentru necunoscut aleatoriu $x$, cu excepția cazului în care se poate obține factorizarea lui $n$ sau unele informații echivalente precum $d$.
Calculul modulo este întotdeauna foarte simplu: $(s^e\,y)^d\equiv s^{e\,d}*x^{e\,d}\equiv(s\,x)^{e\,d}\pmod n$
Notă: ecuația modificată clarifică faptul că aici$\bmod$ nu este un operator, ci un calificativ al relației de echivalență $\echiv$
Acesta este un fapt care susține $(n,e,d)$ ca în RSA și toate numerele întregi $x$, $y$, $s$ cu $y\equiv x^e\pmod n$. Nu permite factorizarea $n$, nici să calculeze din $(n,e)$ A $d$ realizarea $y\mapsto x=x^d\bmod n$ functia inversa a $x\mapsto y=x^e\bmod n$, sau altfel inversați acea funcție pentru aleatoriu $y$ sau $y$ pentru necunoscut aleatoriu $x$.
Acest fapt ar permite unele manipulări dacă funcția RSA manuală $x\mapsto y=x^e\bmod n$ a fost folosit direct pentru a cripta $x$, sau dacă este o funcție inversă $y\mapsto x=y^d\bmod n$ a fost folosit direct pentru a semna $y$. Practica comună previne o astfel de manipulare prin alegere $x$ sau $y$ suficient de aproape de aleatoriu.
