— Гость (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)
>— Гость (28/03/2011 07:53)
Откуда формула? В русской педивикии другая. По твоей получается (я правильно посчитал??)
Метод на вики NFS[link1]. Стойкость RSA[link2] — статья немного устарела, но показывает, насколько сложно давать реальные оценки при переходе от сферических коней к реальным вычсистемам.
И как зависит время легитимных операций (шифрование/дешифрование) от длины открытого ключа?
Вроде бы, экспоненциально :)
Вроде бы меньше – там не тупо брутефорс.
под взломом rsa понимается факторизация большого числа? Если да то количество операций определяется по формуле е^(2*ln(N)^1/3*ln(ln(N))^2/3). N-длина ключа. это примерно 2^80 для N=1024
А количество арифметических операций можно прикинуть?
Ну так это и есть арифметические операции. Ток там описка примерна 2^90, а не 2^80.
Если взять кластер Titan с 2^20 flops, то ему хватит 2^70 секунд или порядка 2^60 часов?
Ну теоретически да. Хотя тут нужно понимать, что сама формула рассчета сложности субэскпоненциальных алгоритмов выводится при помощи ряда предположений и уступоки, да и показывает она сложность ВЕРОЯТНОСТНОГО алгоритма. Так что вот эта приближенная оценка больше из области сферической в вакууме.
Откуда формула? В русской педивикии другая. По твоей получается (я правильно посчитал??)
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.
Не знаю, ты же считал.
Что за формула такая в педивикии которая совсем другая?
вот тут например http://ru.wikipedia.org/wiki/Факторизация_целых_чисел
формула абсолютно такая же.
http://ru.wikipedia.org/wiki/RSA
Посчитай, сколько по твоей формуле получается.
э ну да это я попутал. в формуле выше n это не размер ключа, а сам ключ.
Метод на вики NFS[link1]. Стойкость RSA[link2] — статья немного устарела, но показывает, насколько сложно давать реальные оценки при переходе от сферических коней к реальным вычсистемам.
Ну хоть с точностью до порядка – я здесь http://www.pgpru.com/comment45637 правильно посчитал?
С точностью до порядка: RSA-1024 должно быть эквивалентно 280. Вот например линк, где заодно про мифические MIPSы[link3].
З.Ы. Но по этой формуле — действительно 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 где-то.