РегистрацияПростой вопрос о скорости работы SHA1 и MD5
Прошу простить мое невежество, вопрос, наверное, не только простой, но даже наивный, но не могу ниггже найти ответа в каких-то ясных, доступных для сравнения цифрах, например так: хэширование методом SHA1 в оптимальной реализации расходует 100 (или сколько там) машинных команд на один байт текста. Либо так: хэширование этим методом производится со скоростью 1 Мб (или сколько там) в секунду на машине AMD Sempron с тактовой частотой 2,3 ГГц. Просто и хорошо!
Но как раз таких понятных цифр я найти не могу, везде только описание алгоритма, а сам получить эти цифры не умею, разве что написать своими руками ассемблерную реализацию этих хэшей на ассемблере, сосчитать операторы… Если кто-то избавит меня от этой нудной работы, подскажет цифру, буду признателен.
комментариев: 9796 документов: 488 редакций: 5664
Насчёт оптимальности реализации думайте сами.
Ходил по Вашей ссылке, видел ихний benchmark-speed, видел цифры, они очень мне пригодились. Надеюсь, что все понял правильно.
(Замечание в скобках: надеюсь, но самому верится с трудом, потому что впечатления странные: по-ихнему выходит, что RC4 быстрее DES всего в 4.75 раз, а мне помнилось, что разница гораздо больше – реализация RC4 на 16-разрядном ассемблере это всего 11 команд на букву текста, она лупит с ужасной скоростью – 16-разрядное приложение запускается под Windows XP и обрабатывает 50 или 60 мегабайт в секунду. Совсем другие цифры! Но это так, в сторону, те цифры, которые опубликованы, лучше тем, что они официальные, это источник, на который можно сослаться…)
комментариев: 9796 документов: 488 редакций: 5664
Наверное, можно подложить в исходник модуль и со своей реализацией, хоть с ассемблерной, если и такая возможность/потребность есть.
Насчет ссылки мудрено понять, конечно, — я уже признался в своем невежестве. Слова, которые Вы написали, я вставил не в командную строку своей операционки, а в окошко поиска Гугл, и меня быстро выкинуло куда надо — по адресу http://www.madboa.com/geek/openssl/#benchmark-speed я нашел сравнительную таблицу скоростей всяких шифров и хэшей. Она мне очень пригодилась, еще раз Вас благодарю, сам бы в жизни не догадался, где искать.
Также не могу себе вообразить, что будет, если эту строку запустить как команду на моей машине — так далеко мои технические познания не простираются, я не только программирования под Windows не знаю, но и пользуюсь этой штукой с трудом, и в Интернете совсем недавно, путаюсь ужасно, тычусь как слепой котенок. Зато я еще немножко помню 16-разрядный ассемблер и голимый язык C в версии Turbo C 2.01 1988 года от Borland — на этом мое техническое образование закончилось, и вообще история прекратила свое течение, я ровно 15 лет к машине не подходил… Ну, за это время многое переменилось, эпоха другая.
Агафон
комментариев: 43 документов: 0 редакций: 7
Вот эти строки:
md5 31024.03k 95228.42k 216469.55k ....
— я понял их так, что алгоритм MD5 при использовании блоков размером 16 байт обрабатывает 31 мегабайт в секунду. Правда, неизвестно, на какой машине, с какой тактовой частотой, в один поток или в несколько потоков (thread of execution) параллельно на разных ядрах, но в любом случае получается что-то очень быстро. К тому же довольно смутно понимаю, что в данном случае значит размер блока 16 байт, — до сих пор я полагал, что распространенные хэши, как правило, работают с блоками текста по 512 байт, при этом все или почти все операции выполняются над 32-разрядными операндами. Или здесь речь о каких-то других блоках?
Вот какого черта я пристаю к людям с вопросами о скорости известных хэш-функций? А это я сочинил парочку своих алгоритмов хэширования и сравниваю, пытаюсь понять, они у меня быстрые или медленные, как они выглядят на фоне остальных. Но выкладывать подробности стесняюсь, потому что автор мужчина не 13 лет, а почти полных 60, то есть дедушка уже старенький, но из ума еще не выжил, не хочет смешить публику. Ну, раньше времени не хочет, пока не огреб эту несметную кучу буржуйских бабосов… Все же у меня эта работа отняла много лет, и конца ей не видно — все работает, хэш от строки из 4 нулей отличается от хэша строки из 5 нулей, но законченной теории нет, похоже, эта теория вообще выше моих возможностей. Чтобы все было хорошо, надо доказать теоремочку об одной хитрой нециклической подгруппе симметрической группы подстановок — является ли подгруппа от данного набора образующих истинной подгруппой или покрывает группу целиком, а у меня от этой теоремы ум за разум заходит. Жуть, тоска… Эх, брошу все, займусь квадратурой круга и трисекцией угла! А как жаль, что Великая теорема Ферма уже доказана! Ведь многим жизнь скрашивала…
Я только про скорость хэшей спросил.
На мой вопрос добросовестно ответили, я искренне поблагодарил, сказал спасибо.
Где здесь повод для драчки?
Знал бы, что народ такой раздражительный, я бы даже насчет теоремы о нециклической подгруппе шутить не стал. Ну, если люди шуток не понимают…
комментариев: 43 документов: 0 редакций: 7
По моему это означает сколько раз вычислится соответствующий хеш за 1000 секунд.
Машина – простаивавший в тот момент сервер amazone aws m1.medium
подробнее:
Еще раз спасибо — на этот раз за подробности.
Жаль, однако же, что остается неясность — что эти цифры в точности означают.
Если это количество итераций — сколько раз хэш вычисляется за 1000 секунд, — то, мне кажется, я знаю местечко, где на этот вопрос могут ответить в точности, там этим предметом занимаются вплотную. Но я, признаться, боюсь к ним соваться, я на это милое местечко набрел случайно, а когда понял, что там делают, был в ужасе: не думал, что такое возможно, это превосходит мои устарелые понятия о границах вычислительных возможностей бытовых машин. Находятся эти ребята по адресу http://forum.insidepro.com/viewforum.php?f=10, а занимаются странным делом, подбирают пароли по известному хэшу. Именно подбирают, как я понял, действуют полным перебором, грубой силой, иногда в ход идут заранее составленные таблицы (радужные таблицы), различия алгоритмов хэширования этих парней не останавливает, они берут любые известные хэши, в том числе MD5 и SHA1, а работает ихняя механика, как ни странно, на видеокартах, графических ускорителях семейства Джифорс — вроде бы эта штука многопроцессорная, подходит для параллельных вычислений. Цифры, которые я видел на том сайте, просто жуткие, волосы дыбом встают, речь идет о переборе миллионов паролей в секунду — именно так, не операций в секунду, а паролей в секунду, и для каждого вычисляется хэш. Положим, пароль не слишком длинная строка, но и алгоритмы хэширования не слишком быстрые, по моим прикидкам должно получаться не меньше сотни команд на букву входного текста, причем это на 32-разрядной машине, где команда исполняется сразу для 32-битового операнда. Жуть! Техника на грани фантастики… Забыл свой пароль на сайте ирригаторов и гидромелиораторов — приходи, тебе его подберут, только не забудь хэш притащить.
Ну, насмотрелся я этих футуристических ужасов, зато стал лучше понимать некоторые подробности программы, которая у меня на руках — не могу объяснить, откуда она взялась, тут чужие секреты, но я начал разбирать ее устройство, в этой связи и заинтересовался хэшами, даже нашел такие таинственные места, где хэши ломают. Похоже, создатель этой маленькой утилиты знал все фокусы с быстрым перебором, она среди прочих функций (поразительно много можно запихать в восемь килобайт машинного кода!) умеет вычислять хэши довольно занятным способом, причем берет плату за вход: сама работа с текстом умеренно медленная, примерно 120 команд на букву, все операции простенькие, над байтами и двухбайтовыми словами, но работе с текстом предшествует функция инициализации, заполняются необходимые для работы таблицы, и вот там, похоже, нарочно накручены лишние расходы — таблицы большие, а процедура их вычисления включает явно ненужные итерации, это редуктор, замедлитель, идет просто пересыпание из пустого в порожнее, некая переменная установлена в 256 — и пошел холостой ход, нехитрая процедура исполняется 256 раз вместо одного раза, в итоге все эти предварительные вычисления требуют, по моим подсчетам, от 15 до 300 миллионов операций, в зависимости от параметра. Это как раз плата за вход, миллионы хэшей в секунду эта штука перебрать не позволит, у любых цифр надо отбросить три или четыре нуля…
Да, и еще у этой штуки есть занятные свойства, не знаю, как их описать на правильном языке. Наверное, можно сказать так: есть различие между физической длиной хэша и эффективной длиной. Полная длина, положим, 32 байта, но я производил пробы, нарочно портил текст и смотрел, как при этом изменяется хэш, — так вот, один испорченный байт текста меняет не все 32 байта хэша, а меньшее количество, от 18 до 25, в среднем набегает 21 ошибка. По мере роста количества ошибок в тексте растет и количество ошибок хэша, но потихоньку, чтобы все 32 байта хэша были неправильными, нужно испортить 10 или 12 байтов текста. Я это отследил эмпирически, но не знаю, что это значит. Может быть, это значит, что хэш-функция поганая, у нее этот самый лавинный эффект, про который пишут умные люди, недостаточно лавинный… А может, ничего, и так сойдет… Главное, что эти свойства не зависят от длины текста, текст коротенький, 4 байта, и порча любого из четырех отзывается в 20 неправильных байтах хэша, и то же самое с романом «Война и мир», в котором три мегабайта.
И еще остался загадкой вопрос, с которого я начал — 120 машинных команд на букву текста это много или мало, это быстрая функция или медленная?
На моей машине (AMD Sempron LE-1300, 2.31 GHz) обрабатывается ровно 10 мегабайт текста в секунду, это на одном ядре, да больше и не нужно, программа написана в старомодном стиле, в те времена о многопоточности и не слыхали…
Мне каждый день приходится смотреть в словарь, вчера искал, что такое дауншифтер, потом поленился смотреть, что такое грамар-наци, но не помогло, вслед посыпались какие-то двачеватели, куны и лоровцы.
Ей-богу, ребята, я в молодости, когда хотел сильно выразиться, просто ругался матом, и это было приличнее, как-то понятнее, вообще больше по-человечески. А если на нашей улице кто-то выражался непонятно, так на него смотрели с недоверием — под блатного косит, по фене ботает...
Сейчас вижу что-то похожее, огорчаюсь. Вот скажите, почему криптограммы в топку? Зачем в топку?