id: Гость   вход   регистрация
текущее время 03:37 22/02/2020
Автор темы: Гость, тема открыта 28/03/2011 00:59 Печать
Категории: разное, личности
создать
просмотр
ссылки

Время взлома RSA


Как зависит время взлома сабжа от длины ключа?


 
Комментарии
— Гость (28/03/2011 01:01)   <#>
И как зависит время легитимных операций (шифрование/дешифрование) от длины открытого ключа?
— Гость (28/03/2011 02:17)   <#>
Вроде бы, экспоненциально :)
— Гость (28/03/2011 03:14)   <#>
Вроде бы меньше – там не тупо брутефорс.
— Гость (28/03/2011 07:53)   <#>
под взломом rsa понимается факторизация большого числа? Если да то количество операций определяется по формуле е^(2*ln(N)^1/3*ln(ln(N))^2/3). N-длина ключа. это примерно 2^80 для N=1024
— Гость (28/03/2011 12:48)   <#>
А количество арифметических операций можно прикинуть?
— Гость (28/03/2011 13:42)   <#>
Ну так это и есть арифметические операции. Ток там описка примерна 2^90, а не 2^80.
— Гость (28/03/2011 14:06)   <#>
Если взять кластер Titan с 2^20 flops, то ему хватит 2^70 секунд или порядка 2^60 часов?
— Гость (28/03/2011 15:49)   <#>
Ну теоретически да. Хотя тут нужно понимать, что сама формула рассчета сложности субэскпоненциальных алгоритмов выводится при помощи ряда предположений и уступоки, да и показывает она сложность ВЕРОЯТНОСТНОГО алгоритма. Так что вот эта приближенная оценка больше из области сферической в вакууме.
— Гость (28/03/2011 19:54)   <#>

Откуда формула? В русской педивикии другая. По твоей получается (я правильно посчитал??)

512: 247,09161495124636309056180409015
1024: 373,75712367668095909617542526152
1024/512 = 1,5126256864298165787303807036973 !!!

По формуле ру педивикии (тут правильно посчитал?):

512: 594128224583,93998548170892287623 = exp(27,110360999316207437473110174884)
1024: 8195617450543863,5353600213353823 = exp(36,642375949056959227045398646681)

1024/512 = 13794 (всего лишь!)
Затраты на взлом 1024 бит ключа в среднем всего в 13794 раз больше, чем для 512.
— Гость (28/03/2011 20:39)   <#>
Не знаю, ты же считал.
Что за формула такая в педивикии которая совсем другая?
вот тут например http://ru.wikipedia.org/wiki/Факторизация_целых_чисел
формула абсолютно такая же.
— Гость (28/03/2011 20:53)   <#>
http://ru.wikipedia.org/wiki/RSA

Посчитай, сколько по твоей формуле получается.
— Гость (29/03/2011 08:02)   <#>
э ну да это я попутал. в формуле выше n это не размер ключа, а сам ключ.
— unknown (29/03/2011 09:54, исправлен 29/03/2011 09:55)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Метод на вики NFS. Стойкость RSA — статья немного устарела, но показывает, насколько сложно давать реальные оценки при переходе от сферических коней к реальным вычсистемам.

— Гость (29/03/2011 19:17)   <#>
Ну хоть с точностью до порядка – я здесь http://www.pgpru.com/comment45637 правильно посчитал?
— unknown (30/03/2011 10:01, исправлен 30/03/2011 10:55)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

С точностью до порядка: RSA-1024 должно быть эквивалентно 280. Вот например линк, fileгде заодно про мифические MIPSы.


З.Ы. Но по этой формуле — действительно 290


exp(c (log n) ^(1/3)) (log log n)^(2/3))


c=1.9


exp(1.9 (710) ^ (1/3)) * (6.6) ^ (2/3))


exp (1.9(8.92) * 3.5) = 46071866343312915426773184428


Даже 294 где-то.


Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3