2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Алгоритм RSA
Сообщение13.10.2012, 08:47 


14/12/09
306
Задание из методички:
Выполнить шифрование и дешифрование (с помощью алгоритма 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 
Аватара пользователя


03/12/08
351
Букачача
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 


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

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 15:02 
Заслуженный участник


20/12/10
5686
Mikle1990 в сообщении #630314 писал(а):
а ведь должна единица получаться
Она и получается. Просто делить с остатком надо уметь.

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 15:05 
Заслуженный участник
Аватара пользователя


06/10/08
6119
Mikle1990 в сообщении #630200 писал(а):
Хотел вот ещё спросить немного по теории. У отправителя и получателя всегда одинаковые ключи? Сорри за вопрос, но я что-то уже совсем запутался. Я думаю, что да. Но на всякий случай спросил.
Вся суть как раз в том, что ключи разные.

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 15:40 
Аватара пользователя


03/12/08
351
Букачача
Mikle1990 в сообщении #630314 писал(а):
Если $e=53$, то остаток от деления получается $15,016$, а ведь должна единица получаться. :!:
$17\cdot53=60\cdot15+1$, т.е. $17\cdot53\equiv1\!\pmod{60}$.

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 18:23 


14/12/09
306
Вы правы, $e$ подходит :oops:

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

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

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 18:45 
Аватара пользователя


03/12/08
351
Букачача
Mikle1990 в сообщении #630441 писал(а):
Только я не понимаю, как из получили
Что означает запись $a\equiv b\!\pmod c$ Вы знаете?

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 19:04 


14/12/09
306
chessar в сообщении #630446 писал(а):
Mikle1990 в сообщении #630441 писал(а):
Только я не понимаю, как из получили
Что означает запись $a\equiv b\!\pmod c$ Вы знаете?

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

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение13.10.2012, 20:45 
Аватара пользователя


03/12/08
351
Букачача
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 


14/12/09
306
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 
Аватара пользователя


03/12/08
351
Букачача
Mikle1990 в сообщении #630712 писал(а):
то уж очень большие числа выходят
Так и должно быть в шифровании! Не смущайтесь.

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение14.10.2012, 12:55 


14/12/09
306
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 
Аватара пользователя


03/12/08
351
Букачача
Mikle1990 в сообщении #630726 писал(а):
Получается, что в моей задаче такие маленькие и , что такой шифр очень легко взламывается?
Ну эти задачи ведь из методички для понимания сути, а не для реального практического использования.

 Профиль  
                  
 
 Re: Алгоритм RSA
Сообщение14.10.2012, 13:00 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу 1, 2  След.

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group