Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 29.11.2009, 13:57
гость

 
Сообщений: n/a

RSA
Здравствуйте. Объясните, пожалуйста, как найти секретную экспоненту d? Пытаюсь понять алгоритм на примере из Вики. Откуда там d=6111579?
Спасибо.
  #2  
Старый 29.11.2009, 14:01
гость

 
Сообщений: n/a

вик много. ткни пальцем в какую ты смотрел.
  #3  
Старый 29.11.2009, 14:10
гость

 
Сообщений: n/a

http://ru.wikipedia.org/wiki/RSA
пункт 2.4
  #4  
Старый 29.11.2009, 14:53
гость

 
Сообщений: n/a

d - это обратное к e число по модулю phi(n) = phi(p*q), т.е. число, удовлетворяющее условию d*e = 1 (mod phi(n))

Обратные числа по модулю обычно находятся расшаренным алгоритмом Евклида. Вот сюда смотри, я когда-то давно там запостил свой код на Питоне - http://www.algorithmist.com/index.php/Modular_inverse
  #5  
Старый 29.11.2009, 14:55
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
расшаренным алгоритмом Евклида.
*расширенным


И еще - просьба о всех неточностях или недостатках, какие замечаешь в статьях в Википедии сразу писать на страницу обсуждения соответствующей статьи (или даже исправлять самому, если можешь.)
  #6  
Старый 29.11.2009, 15:16
гость

 
Сообщений: n/a

Я всякие маны читаю уже битый час. Не могу я этого понять, к сожалению. Может найдется тот, кто объяснит на пальцах?
Вот пример из книги:
Пусть р = 1
и q = 11. Тогда N = 77, a {р — l){q — 1) = 6 • 10 = 60. В качестве открытой
шифрующей экспоненты возьмем число Е = 37, поскольку
ПОД (37,60) = 1. Применяя расширенный алгоритм Евклида, найдем
d = 13, т. к.
37-13 = 481 = 1 (mod 60).
Вот каким образом d=13?
  #7  
Старый 29.11.2009, 15:26
гость

 
Сообщений: n/a

Потому что d*e = 1 (mod phi(n)). Че непонятного-то? Это называется modular inverse. Что, каждый символ разъяcнить надо?
  #8  
Старый 29.11.2009, 15:30
гость

 
Сообщений: n/a

Я это прекрасно понимаю. Вот как родили д=13? или у нас теперь руками никто не считает? все по исходникам шастают...
Вы сами то можете это без программы вычислить? Вот что меня интересует.
  #9  
Старый 29.11.2009, 15:32
гость

 
Сообщений: n/a

Условие e*d = 1 (mod phi(n)) вытекает из m = (m^e)^d (mod n) <=> m^(e*d) = m^1 (mod n) <=> e*d = 1 (mod phi(n))

Последнее вытекает из теоремы Эйлера.

А ^e и ^d берутся из соображений, что
m^e - зашифровать текст M
(шифротекст)^d - расшифровать его
и здравого смысла что расшифрованный текст должен равняться исходному
  #10  
Старый 29.11.2009, 15:33
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Я это прекрасно понимаю. Вот как родили д=13? или у нас теперь руками никто не считает? все по исходникам шастают...
Вы сами то можете это без программы вычислить? Вот что меня интересует.
Как вариант, тупым перебором.

Как другой вариант - расширенным алгоритмом Евклида. Я уже упомянул его выше.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра