Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | |
12-й степени - это был алгоритм проверки на простоту, а не... 14.04.04 14:10 Число просмотров: 2814
Автор: RElf <M> Статус: Member
|
> В прошлом году на багтраке проскакивало
12-й степени - это был алгоритм проверки на простоту, а не факторизации. На сегодняшний день для факторизации ничего лучшего NFS не придумали.
|
|
<theory>
|
оценка времени перебора 13.04.04 13:51
Автор: alex_hammer Статус: Незарегистрированный пользователь
|
Добрый день
Я не специалист в области криптоанализа, просто интересно стало после прочтения материала о подборе rsa 512 bit на www.rsasecurity.com.
Подскажите, пожалуйста, существует ли зависимость, позволяющая оценить временной интервал подбора ключа (при известном алгоритме, скажем, закрытого ключа в rsa) в зависимости от его длины при известной производительности системы (в каких-нибудь единицах, к примеру в FLOPS). А какие методы используются - знаю, что не только прямой перебор. Где можно что-нибудь почитать по тематике? Спасибо.
|
|
Я тоже, просто давно интересуюсь этим как любитель. Стараюсь... 14.04.04 13:57
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 14.04.04 14:05 Количество правок: 2
|
> Добрый день
>
> Я не специалист в области криптоанализа, просто интересно
Я тоже, просто давно интересуюсь этим как любитель. Стараюсь высказываться только по тем вопросам, в которых обладаю достаточными знаниями.
> стало после прочтения материала о подборе rsa 512 bit на
> www.rsasecurity.com.
Приблизительных оценок стойкости ключа везде в интернете навалом. Можно их найти в поисковике и посмотреть для интереса, но я так понимаю, этим не хочется ограничится.
> Подскажите, пожалуйста, существует ли зависимость,
> позволяющая оценить временной интервал подбора ключа (при
> известном алгоритме, скажем, закрытого ключа в rsa) в
> зависимости от его длины при известной производительности
> системы (в каких-нибудь единицах, к примеру в FLOPS). А
RSA - вещь целочисленная, в программных реализациях FPU может не использоваться вообще, поэтому имеет смылс говорить о MIPSах. Связь то есть, причем разная, проще оценить скорость поиска ключа по типу процессора и проинтерполировать ее по частоте с поправками на объем кеша, скорость шины памяти и др. В конце концов взять програмку и эмпирическим методом.
> какие методы используются - знаю, что не только прямой
> перебор. Где можно что-нибудь почитать по тематике?
Не прямой перебор??? Перебор чего? Без какого-либо перебора низя. Еслиб можно было без перебора... Я, конечно, понимаю, ну не перебираем все числа подряд, а только простые. Мало того имеет смысл перебирать только те, которые потенциально используются для формирования ключа, исходя из возможностей генератора.
Сталобыть перебор имеет место быть. Мало того, даже после проверки множества ключей невозможно даже предположить диапазон в котором более вероятно нахождение искомого ключа. Соответственно перемножим время проверки одного ключа на количество потенциальных ключей и сделаем вероятностную поправку. Поскольку должно быть так, что все ключи равновероятны, получаем что наверняка взломаем, когда все переберем T=t*N, если очень повезет и первый же ключ подойдет, то T=t, а приблизительное время подбора T=t*N/2.
> Спасибо.
|
|
Про сложность самого быстрого на данный момент алгоритма... 14.04.04 10:48
Автор: RElf <M> Статус: Member
Отредактировано 14.04.04 14:07 Количество правок: 3
|
> Подскажите, пожалуйста, существует ли зависимость,
> позволяющая оценить временной интервал подбора ключа (при
> известном алгоритме, скажем, закрытого ключа в rsa) в
> зависимости от его длины при известной производительности
> системы (в каких-нибудь единицах, к примеру в FLOPS). А
> какие методы используются - знаю, что не только прямой
> перебор. Где можно что-нибудь почитать по тематике?
Про сложность самого быстрого на данный момент алгоритма факторизации NFS (Number Field Sieve) можно прочитать тут: http://mathworld.wolfram.com/NumberFieldSieve.html
Грубо говоря, сложность факторизации числа n оценивается величиной exp(1.9*(log n)^(1/3)*(log long n)^(2/3)) (битовых) операций. Делим это число на производительность системы (в количестве бит.операций/сек.) и получаем требуемое время в секундах.
|
| |
Я вроде слышал о факторизации за полиномиальное время (полином 12-й степени кажется) 14.04.04 11:02
Автор: amirul <Serge> Статус: The Elderman
|
|
В прошлом году на багтраке проскакивало
|
| | |
12-й степени - это был алгоритм проверки на простоту, а не... 14.04.04 14:10
Автор: RElf <M> Статус: Member
|
> В прошлом году на багтраке проскакивало
12-й степени - это был алгоритм проверки на простоту, а не факторизации. На сегодняшний день для факторизации ничего лучшего NFS не придумали.
|
| | | |
Точно. Извиняюсь за прогон 14.04.04 14:59
Автор: amirul <Serge> Статус: The Elderman
|
|
|
|
|
подробно о проекте
Анализ криптографических сетевых...
