Для фиксированного целого числа $n\ge2$, мы можем определить отношение эквивалентности в звенеть $(\mathbb Z,+,\cdot)$. Это отношение известно как «конгруэнтность по модулю». $n$", "равенство по модулю $n$", или "эквивалентность по модулю $n$". Отмечено $u\эквив v\pmod п$ когда целые числа $u$ и $v$ находятся в указанном отношении, что означает
- $u$ и $v$ таковы, что $v-u$ является некоторым кратным $n$
- то есть существует целое число $к$ такой, что $v-u=k\,n$.
и указанное отношение эквивалентности используется для построения кольцо класса остатков $\mathbb Z/nZ$, что (в криптографии) часто отмечается $(\mathbb Z_n,+,\cdot)$ или просто $\mathbb Z_n$.
$v\bмод п$, без скобок сразу слева от$\bmod$ ни $\экв$ знак на том же уровне выражения, может быть определен как наименьший неотрицательный член бесконечного множества целых чисел $u$ с $u\эквив v\pmod п$. Он держит $u=v\bмод п$, куда$\bmod$ является оператором.
Обозначение $y=x^e\bmod n$ подразумевает $0\le y<n$, но $y\эквив х^е\pmod п$ не. Таким образом $y=x^e\bmod n$ определяет уникальное целое число $у$ как функция $х$, $е$ и $n$, когда $y\эквив х^е\pmod п$ не.
Вывод (учебник/сырой) функции шифрования RSA $x\mapsto y=x^e\bmod n$ (с $х$ целое число и $0\le x<n$, что я предполагаю во всем последующем) является однозначно определенным целым числом $у$, размером не более чем $n$. В частности (для $n>2$ и $е>1$) эта функция не может просто вернуть $у=х^е$ для всех $х$, который $y\эквив х^е\pmod п$ позволяет.
Разница имеет значение, потому что $x\mapsto y=x^e$ это функция, которую легко инвертировать (путем извлечения $n^\text{th}$ корень в целых числах); но с $n$ и $е$ правильно выбранная для RSA функция (математически обратимая) $x\mapsto y=x^e\bmod n$ предполагается, что его сложно инвертировать с вычислительной точки зрения, учитывая $n$, $е$, и случайно $у$ или же $у$ для случайного неизвестного $х$, если только нельзя получить факторизацию $n$ или некоторая эквивалентная информация, например $д$.
Расчет по модулю всегда очень прост: $(s^e\,y)^d\equiv s^{e\,d}*x^{e\,d}\equiv(s\,x)^{e\,d}\pmod n$
Примечание: модифицированное уравнение поясняет, что здесь$\bmod$ не оператор, а квалификатор отношения эквивалентности $\экв$
Это факт для $(н,е,д)$ как в RSA, и все целые числа $х$, $у$, $s$ с $y\эквив х^е\pmod п$. Не позволяет учитывать $n$, ни вычислить из $(п,е)$ а $д$ изготовление $y\mapsto x=x^d\bmod n$ обратная функция $x\mapsto y=x^e\bmod n$, или иным образом инвертировать эту функцию для случайного $у$ или же $у$ для случайного неизвестного $х$.
Указанный факт позволит некоторые манипуляции если функция учебника RSA $x\mapsto y=x^e\bmod n$ непосредственно использовался для шифрования $х$, или если это обратная функция $y\mapsto x=y^d\bmod n$ был непосредственно использован для подписи $у$. Обычная практика предотвращает такие манипуляции, выбирая $х$ или же $у$ достаточно близко к случайному.
