ОСТОРОЖНОСТЬ: В вопросе есть что-то настолько неправильное, что разумно его отклонить, см. второй раздел. Но сначала попробуем ответить на него так, как будто мы и не заметили.
В одном из нескольких немного отличающихся определений учебника RSA,
- закрытый ключ (используемый для расшифровки владельцем ключа) $(д,п)$
- открытый ключ (используемый кем-либо для шифрования) $(е,п)$,
- простой текст $м$ и зашифрованный текст $с$ являются целыми числами в интервале $[0,n-1]$,
- $n$, $д$ и $е$ выбираются таким образом¹, что для всех $м$ в указанном интервале мы можем вычислить
- $c:=m^e\bmod n$ для шифрования, то
- $m':=c^d\bmod n$ для расшифровки, получение $м'=м$.
В приведенном выше$\bmod$— оператор с двумя аргументами, такой, что $х\bмод п$ однозначно определенное целое число $у$ с $0\le y<n$ и $х-у$ кратное $n$. Когда $х\ge0$ и $n>0$, что $у$ остаток от евклидова деления $х$ к $n$. Интервал $[0,n-1]$ в приведенном выше определении RSA потому, что это интервал для остатка в евклидовом делении.
Вопрос требует максимальное целое число $м$ который дает себя при шифровании, а затем расшифровке. Данные ключи показывают, что $n=27$; таким образом, ответ (максимум) $m=n-1=27-1=26$. Имеет смысл убедиться, что это $м$ правильно зашифрован и расшифрован для вопроса $д=5$ и $е=13$ согласно приведенному выше определению RSA. Это доказательство легко: у нас есть $m\equiv-1\pmod n$, и $е$ и $д$ нечетны, поэтому $c\equiv(-1)^e\equiv-1\pmod n$, таким образом $m'\equiv(-1)^d\equiv-1\pmod n$, таким образом $m'=c=m=n-1$ так как это единственное целое число $у$ в $[0,n-1]$ с $y\equiv-1\pmod n$.
Примечание: в приведенном выше $y\экв х\pmod n$ средства: $х-у$ кратно ненулевому $n$. В этом использовании$\bmod$не является оператором с двумя аргументами, на что указывает левая скобка слева от него; скорее,$\pмод п$ квалифицирует $\экв$ знак(и) слева, который является эквивалентностью по модулю $n$.
В вопросе есть как минимум одна серьезная проблема: большинство целых чисел $м$ в интервале $[0,26]$ не будет правильно расшифровывать после шифрования! Если кто-то хочет попробовать, только $0$, $1$ и $26$ делать так (они делают что-то странное $е$ и $д$ выбираются). Далее, все $м$ кратное $3$ зашифровать к тому же $с=0$, таким образом, среди них не более одного можно правильно расшифровать.
Дело не только в том $е$ и $д$ не подходят для этого $n$. Проблема в том, что RSA работает для всех $м$ в диапазоне $[0,n-1]$ необходимо, чтобы $n$ не содержит квадратов, то есть не делится на квадрат любого простого числа; иначе говоря, ни одно простое число не должно встречаться дважды при разложении числа на множители. $n$. Но здесь $27$ делится на $3^2$. Без этого условия отсутствия квадратов для нечетных $n$, еще можно выбрать $е$ и $д$ так что расшифровка работает для большинства $м$. Но в рассматриваемом случае $е$ и $д$ даже не соответствует условию¹ для этого. Одна из возможностей состоит в том, что вопрос изначально задавался $n=51$, что делает $д=5$, $е=13$ за работой; затем небрежно изменился на $n=27$.
Идет хуже, чем $(д,п)$ и $(е,п)$ параметры в вопросе недействительны для RSA: любой параметр RSA аналогичного размера не позволяет тайно поделиться чем-нибудь.
RSA может быть безопасным, только если $n$ трудно разложить на множители, для чего требуется, чтобы оно состояло из сотен десятичных цифр. Поэтому любое упражнение с меньшим $n$ речь идет о небезопасной реализации RSA при столкновении с компетентными противниками с компьютером. Моя точка зрения состоит в том, что в педагогических примерах RSA $n$ должно быть достаточно большим, чтобы его было трудно разложить вручную. Также следует подчеркнуть, что детерминированное шифрование RSA с открытым текстом в небольшом наборе (например, небольшой интервал или имя в списке классов) небезопасно, потому что можно попробовать расшифровать все открытые тексты.
Кроме того, «криптосистема, основанная на RSA» настолько слабо определена, что предположение о том, что RSA в учебнике, как в первой части, является чистой спекуляцией.Эта постановка проблемы просто неверна!
¹ Необходимое и достаточное условие для правильного расшифровки учебника RSA для всех целых чисел открытого текста. $м$ в $[0,n-1]$ когда $n$ является бесквадратным, и по крайней мере для всех таких $м$ совпадать с $n$ в противном случае это: $e\,d\equiv1\pmod{\lambda(n)}$, куда $\лямбда$ это Функция Кармайкла. Его часто учат одному из нескольких немного отличающихся условий, которые достаточны, но не необходимы. Популярные включают $e\,d\equiv1\pmod{\varphi(n)}$, куда $\varphi$ является тотиент Эйлера; $d=e^{-1}\bmod{\varphi(n)}$, что дополнительно означает $0\le d<\varphi(n)$; $e=d^{-1}\bmod{\varphi(n)}$, используется в оригинальная статья RSA; $d=e^{-1}\bmod{\lambda(n)}$, что дает наименьший положительный действительный $д$ для данного $е$.
