> Попробуй сделать то-же самое если p и q имеют размер > порядка 256-4096 бит. > > Удачи.
нда... придётся что-то придумывать с хранением данных...... но это решаемо - остаётся вопрос имеет ли уравнение приемлимое время решения при таких порядках чисел - мне кажется если хорошо написать код операций умонжения, сложения и т.д. (придётся похоже вспоминать ассемблер...) то дело будет максимум нескольких часов на P3, поправьте если не прав.
привет люди, прибило намедни (несовсем случайно конечно) разобраться с 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 на два множителя, за несколько месяцев.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
