Не врублюсь в RSA

[AlexLn]

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

[darkelf]

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

[AlexLn]

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

[Finch]

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

[darkelf]

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

нет, не так, любой взлом "bruteforce" имеет, безотносительно алгоритма шифрования, следующий вид:

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

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

[AlexLn]

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

[darkelf]

Сорри, не совсем понятно, что "сравнимо с разложением на множители"?

[Finch]

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

[AlexLn]

Сорри, не совсем понятно, что "сравнимо с разложением на множители"?

Это я имел в виду что быстрее. Чисто теоритически.
(Сдаётся, что "мой способ"