ЭльГамаль, сообщение > p

Предположим, что у нас есть:

р = 89
г = 5
открытый ключ: 17
закрытый ключ: 73

Если мы попытаемся зашифровать сообщение M = 53 (M < p), то получим (c1, c2) == (55, 67) и далее сообщение хорошо расшифровывается.

Однако, если мы попытаемся зашифровать сообщение M = 91 (M > p), то получим (c1, c2) == (44, 57) и дальнейшая расшифровка сообщения не удалась (получили «2» в результате).

Есть 3 вопроса:

• Почему это происходит?
• Можно ли восстановить исходное сообщение M, если мы знаем тот факт, что (m > p) используется, p, g, открытый ключ и есть (c1, c2)?
• Можно ли восстановить исходное сообщение M, если мы знаем факт что (m > p) используется, p, g, открытый ключ и есть несколько зашифрованных сообщений (c1, c2)?

Почему это происходит?

Это происходит потому, что с точки зрения арифметики по модулю 89 числа $2$ и $91$ эквивалентны: 91$ \bmod 89 = 2$. Обычно вы увидите, что это обозначается как $91 \экв 2 \pmod{89}$.

Если вы новичок в модульной арифметике - это так же, как часы $0$ и $12$ на традиционных часах эквивалентны - они "закручиваются".

Можно ли восстановить исходное сообщение M, если мы знаем, что (m > p) используется, p, g, открытый ключ и есть (c1, c2)?

В целом нет, но при этом разрешена расшифровка сообщений. $м <р$.

В конкретный случай, когда у вас был зашифрованный текст и вы знали, что исходное сообщение было, например, в $[2п, 3п - 1]$, вы можете восстановить его, просто добавив соответствующее смещение после расшифровки.

На практике это не особенно полезно, поэтому, как упоминалось в комментариях выше, сообщение разбивается. $м$ в $m_1, \ldots, m_n$ такой, что $m_i < р$. Затем каждое частичное сообщение шифруется отдельно.