Рейтинг:0

Кольцо класса остатков RSA rsa

флаг th

Я работаю над методом RSA уже несколько недель и не понимаю, что это за кольцо остаточного класса.

Я понимаю, что если

$ х^е \bмод п$ должно быть $х<n$ из-за ясности результатов

Однако я не понимаю, какие еще преимущества это дает.

Когда я ищу попытки манипулирования в Интернете, расчет по модулю всегда очень прост:

$(s^e y)^d \equiv s^{ed}x^{ed} \equiv (sx)^{ed} \bmod n$

Но почему это работает так просто, не так ли? $y=x^d \bmod n$ ?

fgrieu avatar
флаг ng
При этом последние два уравнения, вероятно, должны быть $(s^e\,y)^d\equiv s^{e\,d}*x^{e\,d} \equiv(s\,x)^ {e\,d} \pmod n$ и один из $y=x^e\bmod n$ или $x=y^d\bmod n$.
Рейтинг:1
флаг ng

Для фиксированного целого числа $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$ был непосредственно использован для подписи $у$. Обычная практика предотвращает такие манипуляции, выбирая $х$ или же $у$ достаточно близко к случайному.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.