Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | |
сомнения в стойкости RSA 03.11.01 03:18 Число просмотров: 1453
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> нда... придётся что-то придумывать с хранением данных......
> но это решаемо - остаётся вопрос имеет ли уравнение
> приемлимое время решения при таких порядках чисел - мне
> кажется если хорошо написать код операций умонжения,
> сложения и т.д. (придётся похоже вспоминать ассемблер...)
> то дело будет максимум нескольких часов на P3, поправьте
> если не прав.
Ну, если честно, то это все давно уже проверенно и испытанно... И тремя часами ну ни как не обойтись :-)...
И прямое решение решаемо, за разумное время, только потому, что там МОДУЛЬНАЯ экспонента, а это значить, что после любого очередного умножения можно взять остаток от деления (модуль) и дальше работать с ним.
Насколько я помню, единственный случай, который знает история, это разложение кажется 2^512 - 1 на два множителя, за несколько месяцев.
Еще раз удачи.
|
|
<theory>
|
сомнения в стойкости RSA 01.11.01 23:52
Автор: Jer Статус: Незарегистрированный пользователь
|
привет люди, прибило намедни (несовсем случайно конечно) разобраться с 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 ищятся за секунду - имея эти числа можно решать выше приведённое уравнение - и это дело от силы нескольких минут - где же стойкость алгоритма??????? расчёт что не каждый знает теорию конечных полей на которой всё это основывается и не сможет написать алгоритм решения такого уранения? по-моему весьма наивное предположение...
|
|
сомнения в стойкости RSA 05.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 ищятся за секунду - имея эти числа можно
> решать выше приведённое уравнение - и это дело от силы
> нескольких минут - где же стойкость алгоритма??????? расчёт
> что не каждый знает теорию конечных полей на которой всё
> это основывается и не сможет написать алгоритм решения
> такого уранения? по-моему весьма наивное предположение...
|
|
сомнения в стойкости RSA 05.11.01 12:54
Автор: qwerty Статус: Незарегистрированный пользователь
|
Не хочется тебя обламывать, но те ребята на "каком-то киевском ресурсе", были совершенно правы, стойкость действительно заключапется только в невозможности на практике разложить ОЧЕНЬ большое число на множители!
Это кстати одна из трех трудноразрешимых задач, на основе которых сейчас держится подавляющее большинство двухключевых алгоритмов. Есть еще задача дискретного логарифмирования и дискретного логарифмирования на эллиптической кривой.
Правда в истории были и другие трудноразрешимые задачи, например известная криптосистема на основе укладки ранца, но на практике они широкого распротранения не получили и широко не используются.
Страно, что в материалах по которым ты разбирался с RSA не было объяснений по поводу стойкости этого алгоритма (или это были исходные тексты? :)) ! Купи какую-нибудь монографию по криптографии, например авторов Чмора, или Романца, или Иванова. Они сейчас продаются во многих магазина. Там вопросы такого уровня очень подробно освещаются.
Успехов
|
|
сомнения в стойкости RSA 02.11.01 11:02
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> привет люди, прибило намедни (несовсем случайно конечно)
> разобраться с RSA - имеем:
>
> берём достаточно большие простые числа p и q, ищем их
> произведение n и называем его модулем (перл на каком-то
> киевском ресурсе: стойкость алгоритма основана на сложности
> задачи факторизации n - то бишь отыскания по нему p и q -
> сколько надо выпить чтоб такое написать?)
[...]
Попробуй сделать то-же самое если p и q имеют размер порядка 256-4096 бит.
Удачи.
|
| |
сомнения в стойкости RSA 02.11.01 23:41
Автор: Jer Статус: Незарегистрированный пользователь
|
> Попробуй сделать то-же самое если p и q имеют размер
> порядка 256-4096 бит.
>
> Удачи.
нда... придётся что-то придумывать с хранением данных...... но это решаемо - остаётся вопрос имеет ли уравнение приемлимое время решения при таких порядках чисел - мне кажется если хорошо написать код операций умонжения, сложения и т.д. (придётся похоже вспоминать ассемблер...) то дело будет максимум нескольких часов на P3, поправьте если не прав.
|
| | |
сомнения в стойкости RSA 03.11.01 03:18
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> нда... придётся что-то придумывать с хранением данных......
> но это решаемо - остаётся вопрос имеет ли уравнение
> приемлимое время решения при таких порядках чисел - мне
> кажется если хорошо написать код операций умонжения,
> сложения и т.д. (придётся похоже вспоминать ассемблер...)
> то дело будет максимум нескольких часов на P3, поправьте
> если не прав.
Ну, если честно, то это все давно уже проверенно и испытанно... И тремя часами ну ни как не обойтись :-)...
И прямое решение решаемо, за разумное время, только потому, что там МОДУЛЬНАЯ экспонента, а это значить, что после любого очередного умножения можно взять остаток от деления (модуль) и дальше работать с ним.
Насколько я помню, единственный случай, который знает история, это разложение кажется 2^512 - 1 на два множителя, за несколько месяцев.
Еще раз удачи.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
