ElGamal, mesaj > p

Să presupunem că avem:

p = 89
g = 5
cheie publică: 17
cheie privată: 73

Dacă încercăm să criptăm mesajul M = 53 (M < p), atunci obținem (c1, c2) == (55, 67) și mesajul ulterior decriptează bine.

Cu toate acestea, dacă încercăm să criptăm mesajul M = 91 (M > p), atunci obținem (c1, c2) == (44, 57) și decriptarea ulterioară a mesajelor nu a reușit (a obținut „2” ca rezultat).

Sunt 3 intrebari:

• De ce se întâmplă?
• Este posibil să recuperați mesajul original M dacă știm faptul că (m > p) a folosit, p, g, cheie publică și au (c1, c2)?
• Este posibil să recuperăm mesajul original M dacă știm faptul că (m > p) a folosit, p, g, cheie publică și au mai multe mesaje criptate (c1, c2)?

De ce se întâmplă?

Acest lucru se întâmplă deoarece, în ceea ce privește modul aritmetic 89, numerele $2$ și $91$ sunt echivalente: $91 \bmod 89 = 2$. Veți vedea de obicei acest lucru notat ca $91 \equiv 2 \pmod{89}$.

Dacă sunteți nou în aritmetica modulară - așa cum sunt orele $0$ și $12$ pe un ceas tradițional sunt echivalente - se „înfășoară”.

Este posibil să recuperăm mesajul original M dacă știm că (m > p) a folosit, p, g, cheie publică și au (c1, c2)?

Nu în general, permițând totuși decriptarea mesajelor $m < p$.

Într-o specific caz, în care aveai un text cifrat și știai că mesajul original fusese în, de ex. [2p, 3p - 1]$, îl puteți recupera prin simpla adăugare a offset-ului corespunzător după decriptare.

În practică, acest lucru nu este deosebit de util, așa că, așa cum sa menționat în comentariile de mai sus, se împarte mesajul $m$ în $m_1, \ldots, m_n$ astfel încât $m_i < p$. Fiecare mesaj parțial este apoi criptat individual.