тормоза в RSA

bogrus

На цифровую подпись с использованием RSA могут быть более простые атаки, чем разложение на множители. Есть так называемая мультипликативная атака. Пусть есть две подписи: RSA(a) и RSA(b), где a и b - это хеши, а RSA - это результат RSA-шифрования. Тогда справедливо равенство:

RSA(a*b)=RSA(a)*RSA(b). Итак, имея две подписи можно построить и третью. Если есть еще подписи, то можно брать их всякие произведения и попытаться найти требуемый хеш.

masquer

Похоже ты прав: больше всего мне не нравится именно процедура деления, слишком уж какая то громоздкая она получилась. Насчет MMX я думаю так быстрее будет чем через 32-х битные регистры, ведь как-никак 64 бита. А что ты имел в виду, говоря про CRT? (мне в голову только приходит Cathode Ray Tube). Я не пойму как можно было написать без процедуры деления с остатком, ведь это же основная вещь в RSA.

All

Я что то слышал насчет алгоритма быстрого деления, может ли кто-нибудь рассказать про него? А то у меня все в лоб считается. Пытался понять как же винамп мог привести к ускорению работы пограммы. Как включил комп в ДОС-е посмотрел что в регистрах CR0 и CR4. Было CR0=10h, CR4=2000h. В винде когда запустил винамп, то стало: CR0=0, CR4=0. Но моя программа по-прежнему тормозила. Закрыл винамп, вышел из винды, опыть посмотрел регистры и увидел что опять CR0=10h и CR4=2000h. Но при всем при этом моя программа стала работать быстрее. Так что дело похоже не в CR0 и CR4. Здесь кто-то упоминал еще о флаге AC. Посмотрю его. Вот еще думаю: могла ли винда менять какие-нибудь MSR-ы?

 

через rep movsd может быть даже побыстрее будет

Chinese Remainder Theorem



Ты лучше литературу почитай - Handbook of Applied Cryptography, например

 

Я что то слышал насчет алгоритма быстрого деления, может ли кто-нибудь рассказать про него?



Мда... Не любим мы Кнута читать. 2 том. Глава 4.3.1. Алгоритм D (деление неотрицательных целых чисел).

 

volodya

Читал я в свое время и про быстрое деление и про умножение. Но эти алгоритмы эффективны только при аппаратной реализации, а программно будет хуже, чем дедовское "деление углом". Или я не прав ?

 

masquer

Я посмотрел китайскую теорему об остатках. Если я правильно тебя понял с ее помощью можно выполнить более быстрое деление с остатком, я прав?

volodya

Я нашел в электронном виде книжку Кнута, но она какая то урезанная и там как назло нет именно того, что ты упоминаешь. В печатном виде похоже достать его будет еще сложнее. Было бы неплохо, если кто даст ссылку на полный электронный вариант его "Искусства программирования".

 

Было бы неплохо, если кто даст ссылку на полный электронный вариант его "Искусства программирования".



На этом форуме - никто. В противном случае я буду удалять посты. Или вообще закрою ветку. Ищи сам. Только ленивый не найдет. А еще лучше - купи. Эту книгу стоит купить - таких больше нет.

 

А ты сам как думаешь?

 

Icebp

Не так уж и сложно

Хотя если кто из знакомых поедет в Москву, в Санкт-Петербург или в Киев, лучше им поручить. В Петербурге лучше всего покупать на книжной ярмарке около метро Елизаровская. Я там по 265р том покупал, когда в магазинах они по 425 продавались. Правда сейчас сколько они стоят не знаю, но в продаже всё еще есть.

 

volodya

Кто-то давеча книжку по математике искал, всё молчу.. молчу.., тем более что это было на другом форуме



ЗЫ: тот книжный поисковик рулит, нашел вчера старинную книгу по электронике(давно о ней мечтал), 1961 года

ЗЗЫ: кстати полный Кнут есть в сети, на русском

 

кстати полный Кнут есть в сети, на русском

есть, только весит зараза около 150Мб (три тома)



volodya

Было бы неплохо, если кто даст ссылку на полный электронный вариант его "Искусства программирования"

а если челу дать ссылку не на книжку, а на сайт, в сторону которого надо копать, это карается расстрелом или как?

 

Max

Может и поменьше будет, т.к. 3-й том есть в нормальном виде в другом месте, т.е. гораздо поменьше

 

Кто-то давеча книжку по математике искал, всё молчу.. молчу.., тем более что это было на другом форуме





НАХАЛ! Никакого уважения! Никакой субординации! Я тебя научу сапоги чистить с вечера и одевать на свежую голову!



а если челу дать ссылку не на книжку, а на сайт, в сторону которого надо копать, это карается расстрелом или как?



думаю, нет. большинство источников действительно легально. на поисковики линки давать можно:



http://www.poiskknig.ru/

 

> Никакой субординации!



Вроде ж я никакой суббординации и не нарушил, т.к. никакой конкретики в моем посте не было..

 

т.к. никакой конкретики в моем посте не было..



)))

 

Max

> есть, только весит зараза около 150Мб (три тома)



Оказывается ты не прав, 3-и тома в формате djvu на русском весят вместе 18614 Kb!

Если нужно могу ссылки кинуть(в PM на reng.ru

 

Asterix

нашел у себя 1-й (5.8Мб) и 3-й (3.5Мб) том на русском (а я и не знал, что они у меня есть )), 2-й на английском.

так что кинь плиз, вытяну себе 2-й том для комплекта



когда говорил про 150Мб - имел ввиду realcoding.net, там раздел "Е-Книги"

 

> так что кинь плиз



Сделано

 

Буду делать процедуру деления более быстрой. Только вот с прежним вариантом остаются вопросы. Почему то дома на Celeron-е 2.4 ГГц и на компе Pentium 166 МГц скорость генерации ключей практически одинаковая. Ерунда какая то, ничего не пойму в чем тут может быть дело. Посмотрите кому не лень на своих компах какая средняя скорость генерации ключей чтобы набрать какую то статистику, может чего прояснится. Тут кстати читал про быстрое умножение при помощи быстрого преобразования Фурье. Не знаю будет ли оно быстрее обычного умножения "в столбик" для 256-битных чисел или нет. А то может мне и процедуру умножения переделать.

 

Возьми RSATool и померяй

На вряд ли

 

masquer

Я имел в виду скорость генерации ключей моей программой. То есть я хочу понять почему она так странно тормозит (одинаково на разных компах, независимо от их производительности).