Не хочется тебя обламывать, но те ребята на "каком-то киевском ресурсе", были совершенно правы, стойкость действительно заключапется только в невозможности на практике разложить ОЧЕНЬ большое число на множители!
Это кстати одна из трех трудноразрешимых задач, на основе которых сейчас держится подавляющее большинство двухключевых алгоритмов. Есть еще задача дискретного логарифмирования и дискретного логарифмирования на эллиптической кривой.
Правда в истории были и другие трудноразрешимые задачи, например известная криптосистема на основе укладки ранца, но на практике они широкого распротранения не получили и широко не используются.
Страно, что в материалах по которым ты разбирался с RSA не было объяснений по поводу стойкости этого алгоритма (или это были исходные тексты? :)) ! Купи какую-нибудь монографию по криптографии, например авторов Чмора, или Романца, или Иванова. Они сейчас продаются во многих магазина. Там вопросы такого уровня очень подробно освещаются.
привет люди, прибило намедни (несовсем случайно конечно) разобраться с RSA - имеем:
берём достаточно большие простые числа p и q, ищем их произведение n и называем его модулем (перл на каком-то киевском ресурсе: стойкость алгоритма основана на сложности задачи факторизации n - то бишь отыскания по нему p и q - сколько надо выпить чтоб такое написать?)
далее ищем e такое что, наименьший общий делитель e и числа (p-1)(q-1) равен 1, то бишь они взаимно простые и публикуем пару (e,n) как открытый ключ шифрования
далее методом Евклида решается в целых числах уравнение e*d+(p-1)(q-1)*y=1 и находим множество пар (d,y) - при помощи любого из этих d можно прочитать защифрованный текст - разъясните люди, чего я не понимаю?
есть e и n, p и q ищятся за секунду - имея эти числа можно решать выше приведённое уравнение - и это дело от силы нескольких минут - где же стойкость алгоритма??????? расчёт что не каждый знает теорию конечных полей на которой всё это основывается и не сможет написать алгоритм решения такого уранения? по-моему весьма наивное предположение...
сомнения в стойкости RSA05.11.01 13:53 Автор: Ron Rivest Статус: Незарегистрированный пользователь
> привет люди, прибило намедни (несовсем случайно конечно) > разобраться с RSA - имеем: > > берём достаточно большие простые числа p и q, ищем их > произведение n и называем его модулем (перл на каком-то > киевском ресурсе: стойкость алгоритма основана на сложности > задачи факторизации n - то бишь отыскания по нему p и q - > сколько надо выпить чтоб такое написать?) > > далее ищем e такое что, наименьший общий делитель e и числа > (p-1)(q-1) равен 1, то бишь они взаимно простые и публикуем > пару (e,n) как открытый ключ шифрования > !
! Наименьший общий делитель любых двух целых чисел
! всегда равен 1 тут и искать не надо (видимо имелся в виду
! наибольший общий делитель)
!
> > далее методом Евклида решается в целых числах уравнение > e*d+(p-1)(q-1)*y=1 и находим множество пар (d,y) - при > помощи любого из этих d можно прочитать защифрованный текст > - разъясните люди, чего я не понимаю? > ! Похоже d или y но не оба вместе должно быть отрицательным
! иначе в целых числах решить нельзя (частные случаи:
! d=0,p=2,q=2,y=1; d=1,p=1; d=1q=1; d=1,y=0.
> > есть e и n, p и q ищятся за секунду - имея эти числа можно > решать выше приведённое уравнение - и это дело от силы > нескольких минут - где же стойкость алгоритма??????? расчёт > что не каждый знает теорию конечных полей на которой всё > это основывается и не сможет написать алгоритм решения > такого уранения? по-моему весьма наивное предположение...
сомнения в стойкости RSA05.11.01 12:54 Автор: qwerty Статус: Незарегистрированный пользователь
Не хочется тебя обламывать, но те ребята на "каком-то киевском ресурсе", были совершенно правы, стойкость действительно заключапется только в невозможности на практике разложить ОЧЕНЬ большое число на множители!
Это кстати одна из трех трудноразрешимых задач, на основе которых сейчас держится подавляющее большинство двухключевых алгоритмов. Есть еще задача дискретного логарифмирования и дискретного логарифмирования на эллиптической кривой.
Правда в истории были и другие трудноразрешимые задачи, например известная криптосистема на основе укладки ранца, но на практике они широкого распротранения не получили и широко не используются.
Страно, что в материалах по которым ты разбирался с RSA не было объяснений по поводу стойкости этого алгоритма (или это были исходные тексты? :)) ! Купи какую-нибудь монографию по криптографии, например авторов Чмора, или Романца, или Иванова. Они сейчас продаются во многих магазина. Там вопросы такого уровня очень подробно освещаются.
Успехов
сомнения в стойкости RSA02.11.01 11:02 Автор: leo <Леонид Юрьев> Статус: Elderman
> привет люди, прибило намедни (несовсем случайно конечно) > разобраться с RSA - имеем: > > берём достаточно большие простые числа p и q, ищем их > произведение n и называем его модулем (перл на каком-то > киевском ресурсе: стойкость алгоритма основана на сложности > задачи факторизации n - то бишь отыскания по нему p и q - > сколько надо выпить чтоб такое написать?) [...]
Попробуй сделать то-же самое если p и q имеют размер порядка 256-4096 бит.
Удачи.
сомнения в стойкости RSA02.11.01 23:41 Автор: Jer Статус: Незарегистрированный пользователь
> Попробуй сделать то-же самое если p и q имеют размер > порядка 256-4096 бит. > > Удачи.
нда... придётся что-то придумывать с хранением данных...... но это решаемо - остаётся вопрос имеет ли уравнение приемлимое время решения при таких порядках чисел - мне кажется если хорошо написать код операций умонжения, сложения и т.д. (придётся похоже вспоминать ассемблер...) то дело будет максимум нескольких часов на P3, поправьте если не прав.
сомнения в стойкости RSA03.11.01 03:18 Автор: leo <Леонид Юрьев> Статус: Elderman
> нда... придётся что-то придумывать с хранением данных...... > но это решаемо - остаётся вопрос имеет ли уравнение > приемлимое время решения при таких порядках чисел - мне > кажется если хорошо написать код операций умонжения, > сложения и т.д. (придётся похоже вспоминать ассемблер...) > то дело будет максимум нескольких часов на P3, поправьте > если не прав.
Ну, если честно, то это все давно уже проверенно и испытанно... И тремя часами ну ни как не обойтись :-)...
И прямое решение решаемо, за разумное время, только потому, что там МОДУЛЬНАЯ экспонента, а это значить, что после любого очередного умножения можно взять остаток от деления (модуль) и дальше работать с ним.
Насколько я помню, единственный случай, который знает история, это разложение кажется 2^512 - 1 на два множителя, за несколько месяцев.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
