Comments 41
Только одна мысль — «как они это делают?»
+8
Это также просто, как сидеть в контакте. Нужно только захотеть.
+19
В своё время мы обсуждали это с Димой Скляровым из элкомсофта и пришли к следующему мнению. Есть три функции — XOR, ADD и циклические сдвиги (wtf you name it), комбинация любых двух-трёх из которых вроде как не может быть обращена быстрее чем брутфорсом. Ну, попробуйте вычислить A, обратив формулу Y = ( (A ADD B) XOR C ) (n раз) по известным n, Y, B и C.
Суть всех современных гражданских алгоритмов в том, что пихаем побольше циклов над этими функциями и местами размазываем глубокомудрыми константами, и вот он — профит! Главное — нигде не облажаться (такое на самом деле очень часто бывает).
Однако, есть мнение (с), что всё-таки существует на порядки более эффективный, чем полный перебор, обратный алгоритм. Он не настолько эффективен, чтобы подделывать хэши и расшифровывать криптосообщения на обычном компе, но достаточно быстр, чтобы местная гэбня могла всё это сделать за почти-реальное время на топовом суперкомпьютере. Остюда, кстати, происходит и рост «разрядности» всех гражданских алгоритмов с относительно недавних 56 битов DES до вот уже 512 бит последних стандартов. Хотя полный перебор что 256, что тем более 2256 вариантов на обычном компьютере всё ещё в области фантастики.
Серьезные же организации (типа военных) используют алгоритмы на эллиптических кривых (здесь три раза «Ку» товарищу Колмогорову и его последователям). Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.
Суть всех современных гражданских алгоритмов в том, что пихаем побольше циклов над этими функциями и местами размазываем глубокомудрыми константами, и вот он — профит! Главное — нигде не облажаться (такое на самом деле очень часто бывает).
Однако, есть мнение (с), что всё-таки существует на порядки более эффективный, чем полный перебор, обратный алгоритм. Он не настолько эффективен, чтобы подделывать хэши и расшифровывать криптосообщения на обычном компе, но достаточно быстр, чтобы местная гэбня могла всё это сделать за почти-реальное время на топовом суперкомпьютере. Остюда, кстати, происходит и рост «разрядности» всех гражданских алгоритмов с относительно недавних 56 битов DES до вот уже 512 бит последних стандартов. Хотя полный перебор что 256, что тем более 2256 вариантов на обычном компьютере всё ещё в области фантастики.
Серьезные же организации (типа военных) используют алгоритмы на эллиптических кривых (здесь три раза «Ку» товарищу Колмогорову и его последователям). Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.
+25
Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.
Поясните, что именно, откуда и куда запрещено экспортировать.
А то вот я тут в SSH ключик ecdsa уже года полтора успешно использую.
+5
А, простите, в какой «серьезной» организации используется ecdsa?
То, что маркетологи от ИТ проехались по мозгам людей-не-в-теме и рассказали им про преимущества эллиптических кривых еще не значит, что эти самые маркетологи способны/им позволено эту самую эллиптику грамотно реализовать. Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.
По первой части вопроса — ну попробуйте «экспортировать» военную эллиптику из России или там США :) Ну ладно, даже не экспортировать, просто оформить форму допуска, чтобы узнать детали.
Ну или хотя бы импортировать циску с криптомодулем.
То, что маркетологи от ИТ проехались по мозгам людей-не-в-теме и рассказали им про преимущества эллиптических кривых еще не значит, что эти самые маркетологи способны/им позволено эту самую эллиптику грамотно реализовать. Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.
По первой части вопроса — ну попробуйте «экспортировать» военную эллиптику из России или там США :) Ну ладно, даже не экспортировать, просто оформить форму допуска, чтобы узнать детали.
Ну или хотя бы импортировать циску с криптомодулем.
0
Теория заговора? Я такое люблю!
Как объясните то, что на каждом углу нынче вон ЭЦП внедряется, вполне себе гражданское и очень даже на эллиптических кривых?
Как объясните то, что на каждом углу нынче вон ЭЦП внедряется, вполне себе гражданское и очень даже на эллиптических кривых?
+5
Циску нет, но товарищ вам правильно указал на ecdsa. То что вы не доверяете реализации вполне нормально, но это не делает ее автоматически хуже мифической «военной».
+5
Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.
А как насчет нелюбителей?
0
То-то фбр позорится и у любителей помощи просит в расшифровке винчестеров преступников, а в Англиях законы принимают об обязанности сообщить пароль к своей зашифрованной информацией, это все чтоб к военным и к гэбне не ходить вестимо.
+4
Что значит «экспорт алгоритмов»? В современном мире это понятие осталось в закостенелых умах генералов и законописцев. Нет больше никакого экспорта алгоритмов. Алгоритм либо общеизвестен (информация доступна), либо засекречен (информация недоступна). Передать сейчас информацию через границу в любое государство минуя все надзорные органы не проблема. Что запрещаем тогда?
А запрещаем экспорт/импорт устройств, реализующих алгоритмы, которые реализовывать нельзя (но они при этом общеизвестны). Это ограничение появилось в до-ЭВМ эпоху, когда шифровальные системы представляли из себя законченное аппаратное решение и только в этом смысле формулировка целесообразна.
Когда же появились вычислительные машины общего назначения, это ограничение попытались завязать и на них — это лишь вопрос идиотизма соответствующих ведомств, но никак не реального положения дел.
А запрещаем экспорт/импорт устройств, реализующих алгоритмы, которые реализовывать нельзя (но они при этом общеизвестны). Это ограничение появилось в до-ЭВМ эпоху, когда шифровальные системы представляли из себя законченное аппаратное решение и только в этом смысле формулировка целесообразна.
Когда же появились вычислительные машины общего назначения, это ограничение попытались завязать и на них — это лишь вопрос идиотизма соответствующих ведомств, но никак не реального положения дел.
+9
UFO just landed and posted this here
Код на C# присутствует. Не Паскаль, но тоже вполне читаемый. Правда настораживает обилие конвертаций строка-число (в код не вчитывался, просто настораживает).
+2
Я псевдокод слизал с сайта Keccak. Сейчас немного подправил, надеюсь стало понятнее.
0
UFO just landed and posted this here
Ещё бы количество операций над строками уменьшить. Некошерно это. Почему паддинг идёт до преобразования строки в байты, а не после? Да ещё и не через StringBuilder, память замусоривается.
0
>Или говоря по-русски, к сообщению дописывается единичный байт, необходимое количество нулей и весь этот ансамбль завершает байт со значением 0x80.
Если 2х байт не хватает, то дописать надо 0x01 и 0x80, верно?
А если одного байта не хватает, 0x01 или 0x80?
Если 2х байт не хватает, то дописать надо 0x01 и 0x80, верно?
А если одного байта не хватает, 0x01 или 0x80?
+3
Видимо дополняется ещё 500 там с чем то (искать лень вверху) — 1 нулём. Т.е. 5xx-1
0
Судя по коду на C#
Всегда дописывается 0x01 к сообщению. А затем необходимое количество 0x00, чтобы (сообщение+1) стало кратным r и затем дописывается 0x80.
Таким образом, если не хватает одного байта, дописаны будут (r/8)+1 байт, если 2х то (r/8)+2 байт, а если сообщение уже кратно r то дописаны будут r/8 байт.
Всегда дописывается 0x01 к сообщению. А затем необходимое количество 0x00, чтобы (сообщение+1) стало кратным r и затем дописывается 0x80.
Таким образом, если не хватает одного байта, дописаны будут (r/8)+1 байт, если 2х то (r/8)+2 байт, а если сообщение уже кратно r то дописаны будут r/8 байт.
0
Минимальное количество добавляемых байт-2. Максимальное r+8. Т.е. если не хватает 2-ух байт будут добавлены 01 и 80.
Если не хватает одного байта будут дописаны 01, r-8 нулей и 80.
Если не хватает одного байта будут дописаны 01, r-8 нулей и 80.
+1
надеюсь воскресный вечер у Вас будет более удачным ))
+7
Статья то интересная. Но где инфа о равномерности распределения? Криптостойкости? Чем эта функция так хороша, что её приняли в качестве нового стандарта? Длинна хеша не удивила, значит вкусность в другом.
+1
Да это несомненно интересно. Но я не ставил перед собой цель сделать полный анализ хеш-функции. Я просто хотел разобраться как она реализована.
Так что всех подробностей я не знаю, но если кратко основная вкусность в том, что Keccak не использует функцию сжатия, в отличие от Sha-2 или Sha-1. Вместо функции сжатия используется псевдослучайная перестановка, собственно Sponge.
Это позволяет свести скойкость Keccak к модели случайного оракула.Т.е. создателям удалось постоить даказательство неразличимости Keccak от случайного оракула. И это в свою очередь позволяет говорить о Keccak, не просто как о хеш-функции, но как об универсальном криптопримитиве. Т.е. Без всяких дополнительных костылей Keccak можно использовать и для генерации псевдослучайного потока, и для вычисления MAC и для генерации ключей.
Так что всех подробностей я не знаю, но если кратко основная вкусность в том, что Keccak не использует функцию сжатия, в отличие от Sha-2 или Sha-1. Вместо функции сжатия используется псевдослучайная перестановка, собственно Sponge.
Это позволяет свести скойкость Keccak к модели случайного оракула.Т.е. создателям удалось постоить даказательство неразличимости Keccak от случайного оракула. И это в свою очередь позволяет говорить о Keccak, не просто как о хеш-функции, но как об универсальном криптопримитиве. Т.е. Без всяких дополнительных костылей Keccak можно использовать и для генерации псевдослучайного потока, и для вычисления MAC и для генерации ключей.
+5
Можно вот эту ссылку добавить.
+1
А как это произносится?
+6
UFO just landed and posted this here
UFO just landed and posted this here
«Кечак» читается. Некоторые умудряются писать «кетчак», не осознавая, что [tʃ] — это [ч], и никакого «т» там в помине нет.
0
Это не вполне так. Русское «ч» произносится как [t͡ɕ], то есть глухая переднеязычная аффриката, а [t͡ʃ] является глухой постальвеолярной аффрикатой, так что «т» там в помине, но есть, по крайней мере в русской транскрипции.
«Cc» в данном случае восходит к итальянскому орфо-фонетическому менталитету создателей алгоритма, а это как раз [t͡ʃ], и на русский долгое итальянское «ч» передаётся традиционно как «чч» (Мартуччи, Феруччо, Пуччини, Уччелини), так что было бы верно писать либо как «Кеччак», в пользу итальянской традиции, или «Кетчак», в пользу английской (Бутч, матч, скотч, и протч.)
«Cc» в данном случае восходит к итальянскому орфо-фонетическому менталитету создателей алгоритма, а это как раз [t͡ʃ], и на русский долгое итальянское «ч» передаётся традиционно как «чч» (Мартуччи, Феруччо, Пуччини, Уччелини), так что было бы верно писать либо как «Кеччак», в пользу итальянской традиции, или «Кетчак», в пользу английской (Бутч, матч, скотч, и протч.)
+2
на РНР, я так понял, никто еще не написал реализацию? Даже на Питоне на сайте лежит реализация 3.0, хотя описана версия 3.2. Чё-то медленно взлетает.
-3
Кто мешает? Деразайте!
+1
Для php есть расширение: github.com/archwisp/php-keccak-hash
+1
Sign up to leave a comment.
Keccak, новый стандарт хеширования данных