2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Алгоритм RSA
Сообщение13.10.2012, 08:47 
Задание из методички:
Выполнить шифрование и дешифрование (с помощью алгоритма 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 штук) и в больше чем половине из них у меня возникает таже проблема.

(Оффтоп)

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

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 11:50 
Аватара пользователя
Mikle1990 в сообщении #630200 писал(а):
Для нахождения открытого ключа $e$, воспользуемся формулой $de\pmod{z}=1$:
$17e\pmod{60}=1$
При рассмотрении таких уравнений, Вы получаете линейные Диофантовы уравнения с 2-мя переменными (в Вашем случае: $-60x+17y=1$, $y=e$). Ну а далее теория, например из Википедии. Наименьшее положительное решение $e=53$.

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

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 15:02 
Mikle1990 в сообщении #630314 писал(а):
а ведь должна единица получаться
Она и получается. Просто делить с остатком надо уметь.

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 15:05 
Аватара пользователя
Mikle1990 в сообщении #630200 писал(а):
Хотел вот ещё спросить немного по теории. У отправителя и получателя всегда одинаковые ключи? Сорри за вопрос, но я что-то уже совсем запутался. Я думаю, что да. Но на всякий случай спросил.
Вся суть как раз в том, что ключи разные.

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 15:40 
Аватара пользователя
Mikle1990 в сообщении #630314 писал(а):
Если $e=53$, то остаток от деления получается $15,016$, а ведь должна единица получаться. :!:
$17\cdot53=60\cdot15+1$, т.е. $17\cdot53\equiv1\!\pmod{60}$.

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 18:23 
Вы правы, $e$ подходит :oops:

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

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

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 18:45 
Аватара пользователя
Mikle1990 в сообщении #630441 писал(а):
Только я не понимаю, как из получили
Что означает запись $a\equiv b\!\pmod c$ Вы знаете?

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 19:04 
chessar в сообщении #630446 писал(а):
Mikle1990 в сообщении #630441 писал(а):
Только я не понимаю, как из получили
Что означает запись $a\equiv b\!\pmod c$ Вы знаете?

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

 
 
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 20:45 
Аватара пользователя
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$. Это Диофантово уравнение.

 
 
 
 Re: Алгоритм RSA
Сообщение14.10.2012, 12:28 
chessar, всё хорошо, разобрался, получил тоже, что и ты. Даже задачу дальше решил :D

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

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

 
 
 
 Re: Алгоритм RSA
Сообщение14.10.2012, 12:35 
Аватара пользователя
Mikle1990 в сообщении #630712 писал(а):
то уж очень большие числа выходят
Так и должно быть в шифровании! Не смущайтесь.

 
 
 
 Re: Алгоритм RSA
Сообщение14.10.2012, 12:55 
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$, что такой шифр очень легко взламывается?

 
 
 
 Re: Алгоритм RSA
Сообщение14.10.2012, 12:57 
Аватара пользователя
Mikle1990 в сообщении #630726 писал(а):
Получается, что в моей задаче такие маленькие и , что такой шифр очень легко взламывается?
Ну эти задачи ведь из методички для понимания сути, а не для реального практического использования.

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

 
 
 [ Сообщений: 30 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group