РегистрацияПростой вопрос о скорости работы SHA1 и MD5
Прошу простить мое невежество, вопрос, наверное, не только простой, но даже наивный, но не могу ниггже найти ответа в каких-то ясных, доступных для сравнения цифрах, например так: хэширование методом SHA1 в оптимальной реализации расходует 100 (или сколько там) машинных команд на один байт текста. Либо так: хэширование этим методом производится со скоростью 1 Мб (или сколько там) в секунду на машине AMD Sempron с тактовой частотой 2,3 ГГц. Просто и хорошо!
Но как раз таких понятных цифр я найти не могу, везде только описание алгоритма, а сам получить эти цифры не умею, разве что написать своими руками ассемблерную реализацию этих хэшей на ассемблере, сосчитать операторы… Если кто-то избавит меня от этой нудной работы, подскажет цифру, буду признателен.
Прямо с этого вопроса я и начинал — что считается быстрым, что медленным.
120 команд на букву — это медленный хэш или быстрый?
Про поточные шифры не спрашиваю, имею с чем сравнивать, а в той коллекции, которая у меня на руках, есть разные, от очень быстрого до очень медленного — 36 команд на букву это, пожалуй, слишком много для поточного шифра, хотя он особый, с повышенной прочностью и со встроенным хэшированием (короткий хэш 64 бита). В этой коллекции есть все, кроме блочного шифра — против блочных у автора явное предубеждение. Да, и, разумеется, никакой арифметики, никакой несимметричной криптографии...
Теорию еще не разбирал, в исходники тоже только одним глазом глянул, еще ничего не понял, только заметил, что написано все на самом классическом C без всяких плюсов, а в теории эти славяне что-то очень налегают на классификацию — старательно отделяют класс аморфных квазигрупп, без коммутативности, ассоциативности, единиц, еще чего-то... Ненужная роскошь! Да, и способ построения таблиц умножения громоздкий, запросы к памяти большие. Не-а, не пойдет, у Ривеста проще! Однако ж скорость исполнения неимоверная, впечатляет.
Да, есть такое понятие, как "полное покрытие патентами всех путей развития": куда ни плюнь — уже запатентовали, свободны только заведомо худшие пути. Хрестоматийный пример — h264. На самом деле h264 — лучший, и разработчики кодеков столкнулись с серьезной проблемой: как ни сделай хорошо — получишь запатентованные алгоритмы h264. Это перекрытие направлений для будущего развития кодирования видео. Так сложилось, что существующие реализации используют от силы 60% запатентованных идей.
В opensource-подходе принято считать, что патенты — безусловное зло, наверняка на эту тему уже кто-то написал статью со всеми обоснованиями.
Трудно сделать одновременно быстрое, безопасное и нетребовательное к ресурсам решение.
Им некогда, они
бастуютзаняты накруткой счётчиков на главной странице (см. внизу, что они в топ пытаются вывести).комментариев: 9796 документов: 488 редакций: 5664
"Зонтичное патентование" ещё.
На этом строится вся стойкость практически всего направления криптографии на квазигруппах. Иначе легко будет взломать или не будет выигрыша по сравнению с обычными группами. Это самое главное обоснование. "Shapeless" квазигруппа — это, очень грубо и некорректно в математическом смысле выражаясь, некий приблизительный аналог групп на простом числе, примитивном полиноме, только без таковых в явном виде (теория здесь ещё недостаточно проработана). Если группа не аморфная, то вылезают цикличности, линейности, явные закономерности. Даже на слайдах в других работах видно, что при визуализации операций в неаморфных квазигруппах могут быть вместо картины шума какие-то фракталы и линии. А аморфные всегда дают результаты, неотличимые от шума, по-крайней мере визуально и статистически. Для больших квазигрупп полным перебором аморфность не найти — используют критерии, считают числа Каталана и пр.
Жалко, что Edon-R не прошёл в финал, хотя бы вместо невнятного JH, но раз нашли какую-то атаку, то ничего не поделаешь. Плюс, он идёт особняком, как ультрабыстрый алгоритм. Авторы хотят и асимметричную криптографию изобрести на ультрабыстрых принципах. Но ultrafast и квазигруппы — не мейнстрим и многие относятся к этому со скепсисом.
Пос скоростям алгоритмов, смотрите сами в софте и железе.
Благодаря Вам я за последние дни узнал много нового. Я ведь не ленюсь, по каждой ссылке хожу, читаю, просто у меня пока нет сил разобрать каждый текст обстоятельно. Но все же узнал про Keccak, узнал про Skein, теперь вот и про Edon. Много нового, много интересного, мне нравится, и особенно нравится, что в этих новостях мировой криптографии славянские фамилии пошли густо, прямо косяком: Данило Глигорски, Властимил Клима, Ивица Николич, Ховратович и даже какой-то Матушевич, у которого, кажется, от славянских корней одна фамилия осталась. Да, и еще некий Алекс Бирюков… Но полный восторг — это когда среди соавторов одной из конкурсных работ я увидел Керкгофа. Это да, это от души, самое подходящее для криптографа имя!
Все замечательно, но вот чем меня эти братья-славяне удивить не могут, так это квазигруппами. Заинтересовать могут, а удивить не могут, напротив, забавно видеть, в каком они сами восторге от новинки — в точности господин Журден, который на старости лет стал учиться изящной словесности и обнаружил, что всю жизнь говорил прозой. Да не может быть! Это что же, когда я утром кричу: «Николь, принеси башмаки!» — это тоже проза? Немыслимо, он и не знал за собой таких дарований, что умеет говорить прозой. Слово-то какое умное! Ага, вот и эти славяне от слова «квазигруппы» немножко растерялись, мне кажется, ошалели от радости, а это ведь штука не какая-нибудь экзотическая, этих квазигрупп вокруг видимо-невидимо, куда ни плюнь, везде квазигруппы, под ногами валяются, и за стол обедать не сядешь, пока не смахнешь со стола парочку-троечку квазигрупп, которые там просто случайно оказались. Просто слово знают не все, не догадываются, что вот эта дрянь, которую вместе с крошками на пол смели, это и есть квазигруппы…
Да, квазигрупп много, получаются они легко, у некоторых авторов получаются нечаянно, а некоторые пользуются их свойствами очень ловко, только не поднимают по этому поводу шума. Что-то я не слыхал, чтобы профессор Ривест вышел на какое-нибудь видное место и заорал: «Ребята! Разве вы не видите, что мой поточный шифр RC4, такой с виду простенький, ни на что не похож? Это вам не какой-нибудь генератор на жеваных-пережеваных сдвиговых регистрах с обратной связью, тут новые горизонты алгебры — я, во-первых, насобачился строить случайные квазигруппы и пользоваться ими, во-вторых, насобачился строить комбинаторные объекты второго порядка, перестановки всех перестановок, а в-третьих, разрушил все, чего достиг по первому и второму пунктам, перейдя от алгебры к поганому клеточному автомату! Разве вы не видите? Почему нет цветов, аплодисментов, почему оркестр не играет туш?»
Нет, Ривест скромно молчит. Остальные тоже молчат. Более того, RC4 как-то затерли, задвинули за шкаф, объявили устарелым, ломаным, к тому же инициализация S-блока (ключевое расписание) там в самом деле дрянная, слабенькая… И все, кончено дело, забыто, вроде бы идей таких не было, Глигорски и компания говорят о квазигруппах с таким восторгом, будто о них раньше никто и не слыхал. Ну, как раз они сами, может, и не слыхали, думаю, что они очень молодые люди. То есть нет, слыхали, историю вопроса знают, кто-то из этих славян и по-русски читает, я у них в списке литературы книжку Белоусова видел, так что они о квазигруппах знают, но поняли эту алгебру на экзотический манер, потому и строят свои таблицы как-то весьма замысловато.
А квазигруппы кругом, вот они, далеко ходить не надо! Сложил какие-то A и B по модулю 256 – конечная группа. Заменил сумму по таблице – квазигруппа. Готово дело, вещь самая очевидная, на каждом шагу встречается.
Между прочим, для замены i на S[i] раньше в ассемблере была специальная команда xlat, потому что это операция распространенная, часто бывает нужна, хотя замечу, работала команда xlat погано, лучше было выполнять замену явным образом:
Да, только у квазигрупп, полученных таким ближайшим способом, есть свои особенности. Мы ведь просто перешли от одной таблицы умножения к другой, таблицу умножения конечной группы, образованной операцией ADD на множестве байтов (восьмибитовых беззнаковых целых), которая была латинским квадратом 256×256, заменили тем же латинским квадратом, каждая строка которого умножена на подстановку S. При этом квазигруппа наследует некоторые свойства от группы, которая была ее субстратом: от операций ADD и XOR наследуется коммутативность, а от операции SUB наследуется некоммутативность. Ну и что?
Да, вот тут и приходит время задать этот ужасный вопрос: ну и что?
Конечно, коммутативная квазигруппа это уродец, большая редкость, но чем она отличается от некоммутативной для тех целей, для которых используется? А ничем.
Небольшой я математик, но уж это могу утверждать категорически, много лет с этой абракадаброй возился. Да, там есть важные свойства, которые проводят резкую черту между группами и квазигруппами, различия принципиальные, поэтому Глигорски зря мнется, говоря, что пока, при нынешнем уровне знаний, системы уравнений в квазигруппах не решаются, — мог бы выражаться категоричнее: не решаются и никогда не будут решаться. Причина очевидная: невозможно вычитать одно уравнение из другого. Другое важное свойство – нет никакого подобия теоремы Лагранжа, порядок элемента не является делителем порядка квазигруппы. Есть что-то вроде циклической суб-квази-группы (какое слово противное! один префикс латинский, другой греческий, а корень немецкий, что ли…), но ее размер любой. Из этих свойств следуют многие практические последствия, а вот из наличия единицы ничего особенного не следует. Ну, по крайней мере я ничего такого не знаю, не могу уловить, не замечал до сих пор.
Так что с удивлением читал, что аморфность (бесформенность) квазигрупп так важна, так важна, что стоит от нее отступить хоть чуть-чуть, и это прямо глазами будет видно, в гистограммах полезут какие-то регулярные структуры. Неужели?
Дальше больше – оказывается, эти квазигруппы являются каким-то аналогом групп на простом числе или неприводимом многочлене… Ой, ой, ой! А это точно квазигруппы, эти парни ничего не перепутали? Простые числа и неприводимые многочлены – это совсем другая алгебра, тут фокусы с делимостью, остатки образуют множества, замкнутые относительно какой-то операции… Это теория старая, прямо от Галуа идет, вычеты, невычеты, поля… Очень милая теория, но тесно связана с арифметикой, делимостью, так что здесь можно найти какую-нибудь большую-большую коммутативную группу, вроде той, которая косвенно описана малой теоремой Ферма, и использовать ее для несимметричной криптографии. Правильно, коммутация есть, совершенно все равно, в каком порядке выполняются действия — сначала число T возвести в степень m, а потом в степень n, или наоборот, сначала в степень n, потом в степень m. И то же самое при выполнении операций по модулю (простого числа или даже не слишком простого), но при модульньной арифметике возведение в степень становится даже проще, а извлечение корней и логарифмирование становятся невыносимо трудными. Конечная группа! Это можно понять, но где здесь квазигруппы, каким боком? Пока не понимаю, потому что те, квазигруппы, которые хорошо знакомы, они вообще без арифметики, в чем их прелесть и заключается — алгебры без реляционной части, без отношений «больше-меньше», эти алгебры можно задавать таблицами на множествах любых объектов, имеющих или не имеющих количественное значение: годятся буквы, числа, шахматные фигуры, игральные карты, разноцветные шары, фишки, пуговицы от пиджака…
Может, все же у этого Глигорски и компании не квазигруппы, может, он этим словом что-то другое называет? Или я что-то путаю по невежеству? Вообще надо вчитываться, разбирать теорию, только это не на один день занятие, а у меня сейчас сил нет, нездоров. Ладно, посмотрим еще, вернусь я к этой штуке, если буду жив.
Но за те квазигруппы, которые у нас кругом, везде и получаются самым простым способом, могу поручиться уже сейчас — штука хорошая, с большими возможностями…
комментариев: 9796 документов: 488 редакций: 5664
Можно применить три преобразования: замену и две перестановки столбцов и строк в таблице Кэли, в данном случае — латинском квадрате. Получится квазигруппа, являющаяся изотопом группы. Это описано в самом начале у Белоусова и конечно же учитывается. Таких изотопов избегают, вроде как выяснилось, что они тоже не годятся. Вообще, против квазигрупп какие-то современные методы алгебраического криптоанализа работают, хотя авторам сначала казалось, что это и не так. Если вас интересуют славяне и конкретно русскоязычные, занимающиеся этим вопросом, можете поискать ещё публикации Виктора Щербакова из Молдовы.
Таблицы Кэли, да, в данном случае без разницы, чем их заполнять.
Можно даже написать 2 ◦ 2 = 5
Научиться бы ещё хранить их в компактном виде без полной задающей таблицы, но так чтобы не терялись их ценные свойства.
Но по сравнению с книгой появились нотки, которые указывают что у вас уже нету цели, нету пути...
Спасибо!
Славян я люблю, а русскоязычными авторами интересуюсь вынужденно, потому что по-английски почти не понимаю. С удовольствием заметил, что Щербаков из Молдавии — Белоусов работал в Кишиневе, наверное, это от него ниточка тянется, какая-то школа осталась.
Однако же другой любитель квазигрупп, тот автор, который сейчас крановщиком в Ашкелоне, он не из Молдавии, не из России, вообще не из славян, он родом из Средней Азии, там же и учился, только пишет по-русски. Да, и с израильской школой криптографии никак не связан, там школа другая, наша, старорежимно-советская…
Простите, не верю, аналитики врут, преувеличивают свои возможности. Такие они волшебники! А я в чудеса вообще не верю.
Авторам ничего не казалось, в теории квазигрупп есть утверждения -– по крайней мере частные, отдельные, — которые прекрасно доказываются, а есть такие, которые и доказывать не надо, они принимаются по очевидности. Тупой факт! Плетью обуха не перешибешь. Если сказано, что системы уравнений не решаются, значит, не решаются, невозможно вычитать одно уравнение из другого, невыполнимо вычитание – хоть ты на голову встань!
То же самое и в других случаях: если перестановка (S-блок), которая у нас задает таблицу умножения квазигруппы, была получена путем честной жеребьевки русским способом – билетики с номерами от 0 до 255 тянули из шапки (способ чисто русский, в других странах не понимают, почему для этого нужна именно шапка), то вычислить эту перестановку никак нельзя, она невычислима по определению, она случайная. Ее можно только угадывать – и нет даже способа это гадание сократить, например, нет смысла подставлять какие-то случайные значения в уравнения и потом проверять системы уравнений на совместность, отсеивать негодные… Это пустое дело, перебор получается ЕЩЕ БОЛЬШЕ…
Так что общий принцип такой: что получилось путем гадания на кофейной гуще, можно повторить только бросанием медного пятака!
Случайная перестановка 256 символов – это тупик, глухой тупик. И надо быть каким-то редкостным идиотом, чтобы своими руками открыть из этого тупика выход для любого желающего.
А способы все провалить есть, они тысячу лет известны! Ну, классика жанра: эту самую перестановку, абсолютно случайную, используют как бы по прямому назначению, как таблицу замен, но текст, который таким образом обрабатывается, как раз не совсем случайный, различные символы встречаются в нем с разной частотой, с разной вероятностью… Готово! Взлом требует не больше трех минут, опытные люди даже не вычисляют ничего, прямо глазами читают – ага, «Тучки небесные», стишок Лермонтова…
Так вот, если операция замены по таблице часть операции умножения в квазигруппе и ей предшествует ADD или XOR, умножение в конечной группе, заметим такое свойство модульной арифметики: мы можем почленно складывать любые последовательности, с любыми распределениями, но если хотя бы одна из этих последовательностей распределена равномерно, сумма тоже будет распределена равномерно – иначе говоря, энтропия суммы такая, как у слагаемого с наибольшей энтропией.
Это значит, что я могу побуквенно складывать (в конечной группе, операции ADD или XOR) «Евгения Онегина» с «Мертвыми душами» — и опытный человек моментально разложит сумму на слагаемые. Пожалуй, можно добавить еще «Войну и мир», и в этом случае можно разложить сумму на три романа, хотя метод уже другой и затраты времени побольше. Для четырех романов этот фокус уже невыполним или почти невыполним, для пяти и говорить нечего…
Но для двух и трех выполним и при умножении в конечной группе, и при умножении в квазигруппе. А почему нет? Да, умножение в квазигруппе отличается от ADD тем, что дает сильную нелинейность. Очень сильную! В других случаях это полезнейшее свойство, но статистики-то оно не меняет, мы от одной разрешимой алгебры (у каждого уравнения только одно решение!) перешли к другой разрешимой алгебре. Можно назвать это изотопией, можно изоморфизмом, можно еще каким-нибудь морфизмом – от этих морфизмов и у опытных людей голова кругом идет, — но смысл простой: статистики текста та же, те же свойста частотности по символам, не надо даже переходить к диграммам и триграммам… Ура! Вынимаем кролика ипз шляпы – вот вам «Евгений Онегин», а вот «Мертвые души»! А вы говорили: квазигруппы, квазигруппы!..
Да, на такой дурацкой модели можно сломать и квазигруппу, но зачем брать ошибки реализации? Ошибки реализации на совести автора конкретного алгоритма, но скомпрометировать теорию они не могут. Пользуйтесь квазигруппами правильно, и они вас не подведут. Если с самого начала добавить к «Евгению Онегину» и «Мертвым душам» самую паршивенькую гамму, результат будет другой. Распределение суммы равномерное, частотный анализ невозможен. А какой возможен? Да никакой, если таблица умножения квазигруппы задана настоящей случайной перестановкой 256 символов… Это ничем не прошибешь, бетонная стена.
Ну, хранить в явном виде всю таблицу умножения размером 256×256 байт никому и не предлагается, это пустое дело. Слава богу, операции ADD и XOR умеет выполнять любой процессор, так что субстрат есть, и задающей таблицей оказывается строка 256 символов, какая-то перестановка.
Уже не так много, но этот автор, который крановщиком в Ашдоде, вообще ничего не хранит, таблица размером 20 килобайт вычисляется динамически, на один сеанс. Вообще это феерически много – 80 больших (байтовых) S-блоков, но они созданы не просто так, для красоты, все части этой таблицы функциональны: 48 перестановок, которые зависят только от пароля, к последним двенадцати имеются обратные перестановки, чтобы была выполнима обратная операция – «деление» в квазигруппе, еще для двенадцати делается копия, и эта копия умножается (особая операция!) на строку таймера, иначе nonce, — эти копии не на весь сеанс, а для каждого следующего файла при обработке группой (старинный шаблон *.*), они уникальны, и еще 12 строк копируются перед работой со следующим файлом, потому что эти строки не задают таблиц умножения, а сами являются операндами и меняются в ходе использования, но по особым соображениям они не зависят от таймера, только от пароля… Махина! Пирамида египетская! И при ее вычислении еще нарочно запущены 256 раундов холостого хода, программа переливает из пустого в порожнее…
Ну, эта бредовая конструкция из 80 S-блоков используется целиком только при вычислении длинного хэша 32 или 64 байта, а в других случаях можно обойтись меньшим. Скажем, простейший поточный шифр обходится всего двумя S-блоками и в этом смысле не достигает простоты RC4, которому достаточно одного S-блока, зато укладывается в то же самое или даже меньшее число команд – 11 команд на букву, 9 команд на букву… Но уже это количество никак нельзя уменьшить переходом с 16-разрядной машины на 32-разрядную и 64-разрядную, выигрыша никакого, потому что логика байтовая, все операции над байтами. Наоборот, можно теоретически вообразить 8-разрядный контроллер, на котором RC4 будет исполняться за 8 команд на букву вместо 11, а этот ашкелонский поточный шифр за 7 команд вместо 9. Только кому это надо?
Чудес не бывает, вы доказываете столькость тем что случайная таблица 256х256 это как бы много и непробиваемо. Вопрсос далеко спорный, но мы не о этом.
А ваша псевдо-случайная таблица получится уже далеко не случайной. В том то и беда. И все будет зависит от того как вы ее собираетесь умножать.
Тот же рц4 может использовать такие же таблицы >256. Ривест и предлагал рц4 для 2^n. Он же говорил что берите n какое хотите. Вот в вашем примере 16. И получите то же что и предложили тут. И что? От этого рц4 лучший шифр?)
Очень жаль что выйдя с союза, пройдя такую школу, имея такой багаж знаний, широту взгляда, человек не видит будущего... и топчет те квази группы в ступе.
Я не скажу что все у вас плохо, есть у вас идеи, которые будут испольтзовать в будущем, но вы им не придаете значения.
А вот что касается целей и путей... Не знаю, как у Масленникова, а у меня цели есть, вот только путей к их осуществлению я не знаю. Так это у всех так! Многие знают, чего хотят, только не знают, как это получить..
Не знаю, прилично ли говорить о своих целях в подробностях, но раз уж спросили, признаюсь, что они тоже обыкновенные, простые и естественные, как у всех: у меня на руках оказалась чужая работа, в которой я сначала не мог понять просто ничего, потом начал что-то понимать — значит, первая цель разобраться в этой механике как следует, а вторая цель как-нибудь запустить ее в оборот, пристроить с пользой для правообладателей. По второму пункту у меня есть кое-какие обязанности, кое-какие полномочия, но вот способностей и умения нет.
Так что пока занимаюсь теорией, авось хотя бы с этим удастся справиться. С людьми вот знакомлюсь, вопросы задаю, полезное занятие — года два назад на DXDY был случай потрясающий, сначала все дружно говорили, что мол, то, о чем вы спрашиваете, этого никто в мире не знает, нет результатов, а потом нашелся молодой человек, совсем молодой, аспирант, который ЗНАЛ. Нет, он не само решение знал, но он знал, что результаты есть, и знал, где их найти. Очень образованный парень, великий эрудит! Ну, это вселяет надежды на будущее – авось и по другим вопросам кто-то подскажет, кто-то научит...
Скоролько их уже предлагали...
Ну чтож дерзайте.
Не вы первый, не вы последний.
комментариев: 9796 документов: 488 редакций: 5664
h = H (abcdef) = ((((a ° b ) ° c ) ° d ) ° e ) ° f
Стоит поменять порядок множителей (вот и требование некоммутативности) или поменять значение хоть одного множителя и получим другой результат с равной вероятностью из всего алфавита. Тут вам и лавинный эффект и выравнивание по распределению. Стоит прогнать цикл в виде регистра с обратной связью и получим псевдослучайную последовательность. И при этом нелинейную. Казалось бы, замечательное свойство. Но как правильно заметили, надо с умом его использовать. И как не хотите замечать — недостаточное.
Что если в Q-группе есть единица? Например, a. Тогда a ° a = a, h = H (aaaaaa) = a. Но ведь и b ° a = b (ну в зависимости от того, какая там единица, правая или левая и как умножаем). Тогда и h = H (baaaaa) = b и т.д.
Даже если такая простейшая операция используется не в чистом виде, а только как строительный блок, с дополнительными наворотами, уже нехорошо. Это открывает путь к атакам с подобранными значениями, например для поиска коллизий. Что и было успешно продемонстрировано против первых хэшей на квазигруппах.
Также дело обстоит и с изотопизмом по отношению к группам и с коммутативностью. Нельзя их просто игнорировать. Ну не просто так эти требования появились. А кроме коммутативности и изотопизма по отношению к группам есть ещё более сложные зависимости. Чем меньше зависимостей в группе — тем она аморфнее и оптимальнее для применения в крипто. Есть ещё интересные критерии — когда каждый элемент прогоняют через все умножения — "возведение в степень" — и сравнивают, что получится и таких критериев много. Это теоретики-алгебраисты придумывают, криптографы используют.
Другое дело, что вы можете утверждать, что если нет нужды экономить, то при достаточно большой честно случайной квазигруппе (да уже 256x256) она почти всегда будет достаточно нелинейной с пренебрежимо малой вероятностью выбрать плохую. Скорее всего это так. Вроде бы даже так и есть, это характерно и для простых S-блоков и для Q-групп была статистика. Но тогда никак кроме как в полной таблице её не сохранить.
М.б. вы динамически разворачиваете большую Q-группу из малого ключа, как S-блок в RC-4 или Blowfish? Но это тоже уже не популярно. В Twofish Шнайер отказался от очень больших и медленно разворачиваемых блоков и сделал как-бы большие, компактно собранные из маленьких и разворачиваемые на лету — за несколько коротких проходов, без замедления на старте. А в Treefish отказались и от этого.
А нужен оптимизированный по расходам результат с разумной экономией. иначе вы не потягаетесь с алгоритмами на обычной коммутативной алгебре с их универсальностью и возможностью реализации с разменом скорость-память. Как в AES/Keccak.
И наиболее продвинутые авторы (кажется венгры?) не первые взялись за тему Q-групп в крипто. Она тянется с начала девяностых. И блочные шифры на квазигруппах есть. И асимметричных алгоритмов уже есть целый набор. Какие-то cross-inverted квазигруппы используются. И это всё зонтично патентуют, на всякий случай, без зазрения совести. Вдруг хотя бы один алгоритм будет успешен. Ну пройдут годы и они убедятся, что скорее всего зря потратили деньги на патенты, но у них хотя бы публикации есть.
Не следует думать, что авторы вчера про некоммутативную алгебру узнали и тут же побежали сочинять. Криптографы берут из мат. аппарата то, что им наиболее подходит. Математика эллиптических кривых тоже известна сотни лет. А эллиптическую криптографию изобрели в восьмидесятых XX в. И долго исследовали и не принимали. И не все проблемы решены до сих пор, место исследованиям ещё есть.
Кстати, успешный шифр на квазигруппах, не в чистом виде, это ещё IDEA. Там они задаются как раз не табличным способом, а некоммутативным набором вполне коммутативных операций XOR-ADD-MUL. Это почти единственный шифр эпохи начала девяностых, хорошо обоснованный теоретически. Ну может CAST ещё. Ни RC5, ни Blowfish не содержали в публикациях развёрнутого теоретического обоснования, это только после конкурса AES стало так принято. Про RC4 говорить вообще некорректно — он не публиковался официально, как его проектировал Райвист мы не знаем.
Прошу прощенияя за местами неточные формулировки, безалаберное отношение к терминологии (за фразу "некоммутативный набор коммутативных операций" могут фигурально побить в приличном обществе, как правильно эта структура называется — не помню, но кто знает о чём речь — поймёт, несмотря на всю корявость) и отсутствие точных цифр в утверждениях "насколько" — это надо искать работы с расчётами.
Дифф. анализ блочных шифров на неизвестных аналитику квазигруппах этим занимается. Не могу сказать насколько успешно, но метод такой где-то был заявлен.
Спасибо за обстоятельный комментарий.
Свои пояснения к вопросам, которые там содержатся, помещу завтра. Сейчас просто физически не могу, простите.
В предварительном порядке только одно: блок-схема, последовательность процедур и функций. Ну, опять без начинки, чтобы не выдавать чужих секретов.
Реализация на C начинается с простого объявления:
Это главная таблица, главный рабочий инструмент алгоритма, к этой таблице обращаются все функции без исключения, потому что, вообще говоря, у очень разных функций — поточный шифр (с генератором, разумеется) асинхронный шифр (без генератора, разумеется), два очень разных по свойствам хэша — методы общие, это не разные алгоритмы, а один алгоритм, за всем внешним разнообразием спрятано всего четыре примитива, четыре элементарные операции. И все четыре операции используют S-блоки, только некоторым нужен весь этот огромный массив — 80 строк по 256 байт, а некоторым достаточно двух строк, от силы четырех.
В тех случаях, когда алгоритм использует умножение (байтов) в квазигруппах, таблицу умножения размером полных 64 килобайта не нужно ни создавать, ни хранить, эта таблица как бы предполагается существующей, но физически ее нет, мы используем ее неявно, вместо одной (в строгом смысле одной) алгебраической операции используется последовательность двух операций процессора — сложение и замена:
И этот код на Си строчка в строчку переходит в ассемблерный код:
Итак, мы не храним целиком квазигруппу, которую в настоящем случае задает строка A[2], мы храним только саму строку A[2] — и заодно еще восемьдесят строк…
То есть таблица умножения квазигруппы существует только виртуально, ее ячейки — пересечения столбцов и строк — вычисляются на лету. Но уж главная таблица A[81][256] существует реально, реальнее некуда! Она вычисляется при вызове программы, и вычисляется на совесть – вычисления могут занять от 75 тысяч команд (две строки для простейшего поточного шифра) до 300 миллионов команд (заполнение 80 строк за 80 раундов функции инициализации – после 256 раундов холостого хода, когда вычисления идут, а заполнение строк не происходит). А можно накрутить и больше! Но вот меньше чем за 15 миллионов операций всю таблицу заполнить нельзя, нижний предел расходов жесткий…
Относительно способа создания этих перестановок, которые очень похожи на настоящие случайные (любой байт на любом месте с равной вероятностью, будто из шапки билетики тянули), не могу выкладывать подробности, скажу только, что она довольно нахально имитирует физическую случайность, видимо, поэтому автор назвал эту функцию Dice.
Подробностей не могу, тут ужасные тайны и секреты, а комментарий автора процитировать могу, он не математический, а философский, и называется так: проблема курицы и яйца.
Из любых двух строк главной таблицы можно построить генератор случайных (псевдослучайных) чисел, есть метод, это как раз один из четырех примитивов, которыми составлен алгоритм, а имея генератор, можно создать сколько угодно перестановок, которые будут похожи на случайные – такой метод тоже есть, это еще один из четырех примитивов. Так с чего начать? С курицы или с яйца? Автор разрывает этот круг константой – один S-блок предопределенный, готовый, он задан заранее, без него программа не может стартовать, и относительно этого блока имеется лукавый комментарий автора, что уж он настоящий случайный, билетики таскали из шапки. Но это шутка, у меня есть на руках черновики, из которых видно, что это строка тоже вычислена, причем цена ее неотличимости от случайной не так высока – всего-то 107 тысяч команд… М-да… Не нравится – снимайте шапку, нарезайте билетикип и тяните их сами, потому что годится любая строка, полученная этим способом, даже такая, в которой несколько неподвижных точек (циклов длиной 1).
Но этот предопределенный S-блок константа, а значит, и вся главная таблица константа, а чтобы она стала случайной, она должна стать функцией от случайного аргумента, лучше сразу от двух – пароля и таймера. Пароль, вообще говоря, случайная строка, выбранная из множества возможных (случайная, но не неравновероятная другим – плохих паролей больше!), однако эта случайная строка используется многократно, а нужна еще неповторяющаяся случайная строка – это будут показания системных часов, дополненные счетчиком файлов (счетчик нужен, потому что таймер срабатывает только 18 раз в секунду, а за 1/18 секунды программа обрабатывает десятка два небольших, до 1 мегабайта, файлов). Вот чтобы создать зависимость массива S-блоков от пароля и таймера, определена специальная процедура умножения строк – это ужас настоящий, алгебраический монстр, квазигруппы против него цветочек, потому что эта ашкелонская хреновина перемножает строки разной длины. Не выполняется условие единственности произведения? Есть коллизии? Плевать! Умножили 256 раз подряд – и все в порядке, теперь вероятность коллизий оценивается в точности и выражается таким числом, что его и на бумага написать неприлично. Ну, не то десять в минус шестисотой, не то десять в минус тысячной… Словом, когда рак на горе свистнет – вот это точное выражение вероятности коллизий.
Ну, а когда эта великая и ужасная таблица создана, делать с ней можно что угодно – и жизнь становится легкой и простой. Совсем легкой, если не считать некоторых маленьких теоретических трудностей, пробелов в доказательствах… А так пожалуйста, делай что хочешь, танцуй, пой, веселись!
Что ж касается пробелов в теории, то о них после. Не могу сейчас о грустном, не засну…