Алгоритм RSA

[Mikle1990]

Задание из методички:
Выполнить шифрование и дешифрование (с помощью алгоритма RSA) при следующих условиях:
$ p=7; q=11; d=17; M=3; $
Моё решение начинается так:
1. $n=pq=77$
$z=(p-1)(q-1)=60$
2. Для нахождения открытого ключа $e$, воспользуемся формулой $de\pmod{z}=1$:
$17e\pmod{60}=1$

Я не могу найти $e$

Посмотрел остальные варианты заданий (их 28 штук) и в больше чем половине из них у меня возникает таже проблема.

(Оффтоп)

Хотел вот ещё спросить немного по теории. У отправителя и получателя всегда одинаковые ключи? Сорри за вопрос, но я что-то уже совсем запутался. Я думаю, что да. Но на всякий случай спросил.

[chessar]

Mikle1990 в сообщении #630200 писал(а):

Для нахождения открытого ключа $e$, воспользуемся формулой $de\pmod{z}=1$:
$17e\pmod{60}=1$

При рассмотрении таких уравнений, Вы получаете линейные Диофантовы уравнения с 2-мя переменными (в Вашем случае: $-60x+17y=1$, $y=e$). Ну а далее теория, например из Википедии. Наименьшее положительное решение $e=53$.

[Mikle1990]

chessar, раньше не сталкивался с Диофантовыми И ни в методичке, ни в учебнике о них не написано.
А по поводу того, что Вы написали...
$de\pmod{z}=1$
$17e\pmod{60}=1$
Если $e=53$, то остаток от деления получается $15,016$, а ведь должна единица получаться.

[nnosipov]

Mikle1990 в сообщении #630314 писал(а):

а ведь должна единица получаться

Она и получается. Просто делить с остатком надо уметь.

[Xaositect]

Mikle1990 в сообщении #630200 писал(а):

Хотел вот ещё спросить немного по теории. У отправителя и получателя всегда одинаковые ключи? Сорри за вопрос, но я что-то уже совсем запутался. Я думаю, что да. Но на всякий случай спросил.

Вся суть как раз в том, что ключи разные.

[chessar]

Mikle1990 в сообщении #630314 писал(а):

Если $e=53$, то остаток от деления получается $15,016$, а ведь должна единица получаться.

$17\cdot53=60\cdot15+1$, т.е. $17\cdot53\equiv1\!\pmod{60}$.

[Mikle1990]

Вы правы, $e$ подходит

Только я не понимаю, как из $17e\pmod{60}=1$ получили $-60x+17y=1$, $y=e$ и нашли, что $e=53$

Я почитал теорию, но разобраться не смог

[chessar]

Mikle1990 в сообщении #630441 писал(а):

Только я не понимаю, как из получили

Что означает запись $a\equiv b\!\pmod c$ Вы знаете?

[Mikle1990]

chessar в сообщении #630446 писал(а):

Mikle1990 в сообщении #630441 писал(а):

Только я не понимаю, как из получили

Что означает запись $a\equiv b\!\pmod c$ Вы знаете?

Означает, что $a$ это число, при делении которого на $c$, должен остаться остаток $b$

[chessar]

Mikle1990 в сообщении #630452 писал(а):

Означает, что это число, при делении которого на , должен остаться остаток

Не совсем так, это означает, что $a-b$ делится на $c$, т.е. $a-b=cd$ или $a=cd+b$ - $b$ здесь не обязан быть остатком, т.е. что $b$ не обязан быть от $0$ до $c-1$ включительно. Вам необходимо решить сравнение $17e\equiv 1\!\pmod{60}$. Это означает, что $17e-1=60f$ или $-60f+17e=1$. (Далее я обозначил $x=f$ и $y=e$.) Т.е. Вам необходимо решить уравнение $-60x+17y=1$ в целых числах $x,y$. Это Диофантово уравнение.

[Mikle1990]

chessar, всё хорошо, разобрался, получил тоже, что и ты. Даже задачу дальше решил

Но одно смутило: когда шифрование проводил, то уж очень большие числа выходят - приходилось считать на инженерном калькуляторе в компьютере (мой навороченый CITIZEN точно с таким не справится)
Шифрование сообщения $M=3$
$C=3^{53}\pmod{77}=5$

Дешифрования сообщения $M=5$
$M=5^{17}\pmod{77}=3$

[chessar]

Mikle1990 в сообщении #630712 писал(а):

то уж очень большие числа выходят

Так и должно быть в шифровании! Не смущайтесь.

[Mikle1990]

chessar, большое спасибо за помощь!

Мне вот что интересно. У меня в книге написано, что:
Надёжность метода(RSA) обеспечивается сложностью нахождения множителей больших чисел. Если бы криптоаналитик мог разложить на множители(открытое) число $n$, он мог бы тогда найти значения $p$ и $q$, а следовательно и число $z$. После этого числа $e$ и $d$ можно найти при помощи алгоритма Евклида.
К счастью ... ... ... проблема чрезвычайна трудна.

Допустим, я человек, который хочет отправить сообщение Алисе. Получается у меня есть $n$ и $e$. Разложив на множители $n=77=7\cdot11$, я получил $p=7$, $q=11$. А далее я получаю $z=60$. Зная $e$, я могу найти $d$ по формуле:
$53d\pmod{60}=1$

Получается, что в моей задаче такие маленькие $p$ и $q$, что такой шифр очень легко взламывается?

[chessar]

Mikle1990 в сообщении #630726 писал(а):

Получается, что в моей задаче такие маленькие и , что такой шифр очень легко взламывается?

Ну эти задачи ведь из методички для понимания сути, а не для реального практического использования.

[Mikle1990]

chessar,
Получается, что в моей задаче такие маленькие $p$ и $q$, что такой шифр очень легко взламывается? И если я задам большие $p$ и $q$, то уже никто не сможет разложить $n$ на множители? Правильно я понимаю?