Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Не врублюсь в RSA  (Прочитано 14770 раз)
0 Пользователей и 1 Гость смотрят эту тему.
AlexLn
Участник

ru
Offline Offline

« : 13-01-2010 13:21 » 

Доброго времени суток.
Нашёл в книге алгоритм RSA.
Как я понимаю, чтоб зашифровать сообщение М возводим его в известную степень Е и берём остаток от деления на N. Чтоб расшивровать шифровку C возводим в секретную степень D и снова берём остаток. Как я знаю, возведение в степень происходит просто перемножением числа до Х раз. Получается, расшивровка и брутфорс занимают одинаковое время? Ни фига не пойму.
Записан
darkelf
Молодой специалист

no
Offline Offline

« Ответ #1 : 13-01-2010 13:27 » 

Вам ещё надо перебирать D, которое должно быть, если не ошибаюсь достаточно большим.
http://ru.wikipedia.org/wiki/RSA
Записан
AlexLn
Участник

ru
Offline Offline

« Ответ #2 : 13-01-2010 13:43 » 

darkelf,  так по моему (полного чайника-ламера в математике и компах) разумению, придётся просто перемножить шифровку D раз. Получился исходный текст - вот оно D, не получился - множим дальше. То есть делать то-же, что и расшифровщик, только сравнивать каждый промежуточный результат. Потому и не врублюсь в чём весь смысл.
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #3 : 13-01-2010 13:55 » 

AlexLn, Возведение в степень не нужно делать D раз умножений. Есть алгоритмы, которые сводят к приемлемому числу умножений. Простой пример нам надо 2 возвести в 4 степень. Есть два пути 2*2*2*2=16 и 2*2=4 4*4=16 В первом варианте 4 умножения. Во втором всего два. А теперь представь, что ты будеш умножать скажем 100 трилионнов раз сверх большие числа. Может быть, через лет 10 получиш результат. Когда эта шифровка и так уже потеряет актуальность.
« Последнее редактирование: 13-01-2010 13:59 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
darkelf
Молодой специалист

no
Offline Offline

« Ответ #4 : 13-01-2010 14:03 » 

darkelf,  так по моему (полного чайника-ламера в математике и компах) разумению, придётся просто перемножить шифровку D раз. Получился исходный текст - вот оно D, не получился - множим дальше. То есть делать то-же, что и расшифровщик, только сравнивать каждый промежуточный результат. Потому и не врублюсь в чём весь смысл.
нет, не так, любой взлом "bruteforce" имеет, безотносительно алгоритма шифрования, следующий вид:

1. берём очередной ключ
2. пытаемся расшифровать сообщение (вот тут у Вас разные умножения/деления)
3. расшифровалось нормально? (текст расшифрованного сообщения осмысленен?) если нет, то переход к шагу 1

таким образом , процедура расшифровки должна повторяться m, нет, m мало - n раз, и это n может быть очень велико.
Записан
AlexLn
Участник

ru
Offline Offline

« Ответ #5 : 13-01-2010 14:20 » 

Cпасибо. Ну, я точно ламер!
А сравнимо с разложением на множители? Или полегче?
Записан
darkelf
Молодой специалист

no
Offline Offline

« Ответ #6 : 13-01-2010 14:45 » 

Сорри, не совсем понятно, что "сравнимо с разложением на множители"?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #7 : 13-01-2010 19:14 » 

AlexLn, Там всего 2 простых, но очень больших числа. Вся сложность этого алгоритма и заключается, в нахождении второй пары для простого числа.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
AlexLn
Участник

ru
Offline Offline

« Ответ #8 : 14-01-2010 13:42 » new

Сорри, не совсем понятно, что "сравнимо с разложением на множители"?
Это я имел в виду что быстрее. Чисто теоритически.
(Сдаётся, что "мой способ" Улыбаюсь
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines