Простой вопрос о скорости работы SHA1 и MD5
Прошу простить мое невежество, вопрос, наверное, не только простой, но даже наивный, но не могу ниггже найти ответа в каких-то ясных, доступных для сравнения цифрах, например так: хэширование методом SHA1 в оптимальной реализации расходует 100 (или сколько там) машинных команд на один байт текста. Либо так: хэширование этим методом производится со скоростью 1 Мб (или сколько там) в секунду на машине AMD Sempron с тактовой частотой 2,3 ГГц. Просто и хорошо!
Но как раз таких понятных цифр я найти не могу, везде только описание алгоритма, а сам получить эти цифры не умею, разве что написать своими руками ассемблерную реализацию этих хэшей на ассемблере, сосчитать операторы… Если кто-то избавит меня от этой нудной работы, подскажет цифру, буду признателен.
Ссылки
[link1] http://www.pgpru.com/proekt/wiki
[link2] http://lurkmore.to
[link3] https://en.wikipedia.org/wiki/Variably_Modified_Permutation_Composition
[link4] http://www.pgpru.com/chernowiki/rukovodstva/voprosykandidatyvfaq/kriptografijapraktika#biblioteka/statji/sovremennajatehnikavzlomaparolejj
[link5] http://www.pgpru.com/biblioteka/osnovy/foneticheskijjparolj
[link6] http://www.pgpru.com/comment53233
[link7] http://www.pgpru.com/biblioteka/statji/keccaksponge
[link8] http://www.pgpru.com/comment52716
[link9] http://www.pgpru.com/novosti/2010/universaljnajaatakanaheshfunkciimdxsha1sha2irjadkandidatovsha3
[link10] http://eprint.iacr.org/2011/023
[link11] http://www.pgpru.com/comment43788
[link12] http://www.pgpru.com/faq/kriptografijaobschievoprosy
[link13] https://www.pgpru.com/comment40654
[link14] http://bench.cr.yp.to/ebash.html
[link15] http://ehash.iaik.tugraz.at/wiki/SHA-3_Hardware_Implementations
[link16] http://ria.ru/tv_science/20120704/691813345.html#riatv/628454950
[link17] http://eprint.iacr.org/cgi-bin/search.pl?last=365&title=1
Насчёт оптимальности реализации думайте сами.
Unknown, спасибо, очень Вам благодарен!
Ходил по Вашей ссылке, видел ихний benchmark-speed, видел цифры, они очень мне пригодились. Надеюсь, что все понял правильно.
(Замечание в скобках: надеюсь, но самому верится с трудом, потому что впечатления странные: по-ихнему выходит, что RC4 быстрее DES всего в 4.75 раз, а мне помнилось, что разница гораздо больше – реализация RC4 на 16-разрядном ассемблере это всего 11 команд на букву текста, она лупит с ужасной скоростью – 16-разрядное приложение запускается под Windows XP и обрабатывает 50 или 60 мегабайт в секунду. Совсем другие цифры! Но это так, в сторону, те цифры, которые опубликованы, лучше тем, что они официальные, это источник, на который можно сослаться…)
Не очень понял про ссылку. Я имел ввиду предложение набрать вам самим на вашем компьютере эту команду и самому посмотреть её вывод.
Наверное, можно подложить в исходник модуль и со своей реализацией, хоть с ассемблерной, если и такая возможность/потребность есть.
Unknoun!
Насчет ссылки мудрено понять, конечно, — я уже признался в своем невежестве. Слова, которые Вы написали, я вставил не в командную строку своей операционки, а в окошко поиска Гугл, и меня быстро выкинуло куда надо — по адресу http://www.madboa.com/geek/openssl/#benchmark-speed я нашел сравнительную таблицу скоростей всяких шифров и хэшей. Она мне очень пригодилась, еще раз Вас благодарю, сам бы в жизни не догадался, где искать.
Также не могу себе вообразить, что будет, если эту строку запустить как команду на моей машине — так далеко мои технические познания не простираются, я не только программирования под Windows не знаю, но и пользуюсь этой штукой с трудом, и в Интернете совсем недавно, путаюсь ужасно, тычусь как слепой котенок. Зато я еще немножко помню 16-разрядный ассемблер и голимый язык C в версии Turbo C 2.01 1988 года от Borland — на этом мое техническое образование закончилось, и вообще история прекратила свое течение, я ровно 15 лет к машине не подходил… Ну, за это время многое переменилось, эпоха другая.
Агафон
Виноват, опять чертовщина из-за моей неумелости. В предыдущем сообщении я, во-первых, переврал Ваше имя, Unknown, а во-вторых, не выставил в надлежащем месте свое, поэтому называюсь там просто Гость... Но я учусь, впредь буду аккуратнее.
Вообще говоря, да, на "общие места" надёжнее давать "ссылку" в виде поискового запроса.
Да, по вам видно :) Вы не только запятые не забываете ставить, но даже знаете про такой знак препинания, как тире, и пользуетесь им по правилам. Прям моральный дауншифтер какой-то! Были бы 15 лет в интернете — скатились бы на общий уровень.
1. Выражаю признательность господину Neverward за предоставленные им данные о работе хэшей MD5 и SHA1. К сожалению, опять не могу похвастать, что все правильно понял, а просить более подробных разъяснений не решаюсь, это будет нахальство. Ну, разве что кто-то снизойдет, не поленится…
Вот эти строки:
md5 31024.03k 95228.42k 216469.55k ....
— я понял их так, что алгоритм MD5 при использовании блоков размером 16 байт обрабатывает 31 мегабайт в секунду. Правда, неизвестно, на какой машине, с какой тактовой частотой, в один поток или в несколько потоков (thread of execution) параллельно на разных ядрах, но в любом случае получается что-то очень быстро. К тому же довольно смутно понимаю, что в данном случае значит размер блока 16 байт, — до сих пор я полагал, что распространенные хэши, как правило, работают с блоками текста по 512 байт, при этом все или почти все операции выполняются над 32-разрядными операндами. Или здесь речь о каких-то других блоках?
Вот какого черта я пристаю к людям с вопросами о скорости известных хэш-функций? А это я сочинил парочку своих алгоритмов хэширования и сравниваю, пытаюсь понять, они у меня быстрые или медленные, как они выглядят на фоне остальных. Но выкладывать подробности стесняюсь, потому что автор мужчина не 13 лет, а почти полных 60, то есть дедушка уже старенький, но из ума еще не выжил, не хочет смешить публику. Ну, раньше времени не хочет, пока не огреб эту несметную кучу буржуйских бабосов… Все же у меня эта работа отняла много лет, и конца ей не видно — все работает, хэш от строки из 4 нулей отличается от хэша строки из 5 нулей, но законченной теории нет, похоже, эта теория вообще выше моих возможностей. Чтобы все было хорошо, надо доказать теоремочку об одной хитрой нециклической подгруппе симметрической группы подстановок — является ли подгруппа от данного набора образующих истинной подгруппой или покрывает группу целиком, а у меня от этой теоремы ум за разум заходит. Жуть, тоска… Эх, брошу все, займусь квадратурой круга и трисекцией угла! А как жаль, что Великая теорема Ферма уже доказана! Ведь многим жизнь скрашивала…
Да, примерно так :) Как оформлять цитаты, описано по ссылкам здесь[link1].
Люди!
Я только про скорость хэшей спросил.
На мой вопрос добросовестно ответили, я искренне поблагодарил, сказал спасибо.
Где здесь повод для драчки?
Знал бы, что народ такой раздражительный, я бы даже насчет теоремы о нециклической подгруппе шутить не стал. Ну, если люди шуток не понимают…
По моему это означает сколько раз вычислится соответствующий хеш за 1000 секунд.
Машина – простаивавший в тот момент сервер amazone aws m1.medium
подробнее:
Neverward!
Еще раз спасибо — на этот раз за подробности.
Жаль, однако же, что остается неясность — что эти цифры в точности означают.
Если это количество итераций — сколько раз хэш вычисляется за 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 мегабайт текста в секунду, это на одном ядре, да больше и не нужно, программа написана в старомодном стиле, в те времена о многопоточности и не слыхали…
все? все криптопрограммы в топку?
Пожалуйста, выражайтесь яснее!
Мне каждый день приходится смотреть в словарь, вчера искал, что такое дауншифтер, потом поленился смотреть, что такое грамар-наци, но не помогло, вслед посыпались какие-то двачеватели, куны и лоровцы.
Ей-богу, ребята, я в молодости, когда хотел сильно выразиться, просто ругался матом, и это было приличнее, как-то понятнее, вообще больше по-человечески. А если на нашей улице кто-то выражался непонятно, так на него смотрели с недоверием — под блатного косит, по фене ботает...
Сейчас вижу что-то похожее, огорчаюсь. Вот скажите, почему криптограммы в топку? Зачем в топку?
Да, т.к. есть отличие от случайного вывода. Ни на один SHA-конкурс такую функцию не взяли бы.
Всё есть в википедии отбросов общества[link2]: и "двач", и суффикс "кун", и "лор" (lor). Не обращайте внимания.
что ж тут непонятного?
ужасная картина!
Спасибо, наверное, Вы правы, никакой NIST такую функцию не примет. Но вот так хочется хоть кое-что объяснить, сказать словечко в защиту автора, только ведь это будет медвежья услуга, под видом защиты я выболтаю чужие секреты...
Ладно, компромисс, опять обойдемся косвенными описаниями: черный ящик, результаты знаем, а операции за кулисами.
Меня эта программа (старинный COM-файл размером 8 кб) радует тем, что почти все прописанные в ней операции и процедуры имеют теорию. Если хорошенько вдуматься, это свойство неожиданное, потому что распространенные хэши (и близкородственные им блочные шифры) имеют теории ровно столько, сколько взбивание омлета вилкой в большой эмалированной миске: совершенно ясно, что из яиц, взбитых таким образом, цыпленок уже не выведется, но теперь попробуйте перевести эту ясность на язык строгих доказательств. Не выйдет, нечего и пробовать! Хотя это очень ясно и понятно, что если как следует вертеть вилкой в миске, яйца будут взбиты хорошо, белок и желток перемешаются до неразделимости и неразличимости... А тут, понимаете ли, такой алгоритм, где у каждого действия есть теория, то есть почти каждая операция образует алгебру.
О, алгебра — это уже нечто! Тут это вам не там… Это уже теория, можно что-то разбирать и доказывать. Хотя вообще там попадаются странноватые алгебры, иной раз не знаешь, как назвать, хотя опять-таки глазами все видишь, все ясно. Скажем, такая полуразрешимая алгебра, имеет разрешимость только в одну сторону: произведение можно делить на правый множитель, а на левый нельзя, в эту сторону деление не определено, так что правый множитель нельзя заменить неизвестным иксом, уравнение решаться не будет. Вот как эта чертовщина должна называться? Друзья-алгебраисты делают большие глаза...
Так вот, насчет поганого хэша — может быть, он не совсем и поганый, там есть тонкость, не все 32 байта хэша изменяются по одному закону, есть разница между левой и правой стороной, четной и нечетной, это как бы разные разряды, младший и старший, результата операции в некоей алгебре — какого-то «сложения» или «умножения», заданного особым образом, применительно к нуждам алгоритма. Порча хотя бы одного бита текста приводит к тому, что ровно половина строки хэша, 16 байт из 32, изменится обязательно, потому что это хорошая алгебра, где выполняется условие единственности произведения.
Не так уж это мало — 16 байт из 32, не так это плохо, вообще этим можно и ограничиться, а от слабой половины строки, где каждый символ меняется не в точности, а лишь с вероятностью 5/16, можно и вообще отказаться. Или сложить этут строку вчетверо, перегнуть по длине два раза, сложить с собой разок-другой — разок просто так, разок после циклического сдвига, перемешать, взбить вилкой... Но это и будет шарлатанство, нечистая работа, а там везде работа чистая, честная алгебра с честными результатами. Это значит, что порча одного байта текста изменит ровно 16 байт хэша в точности, а порча двух байт текста меняет те же 16 байт хэша уже по вероятности — каждый может совпасть с правильным значением с вероятностью ровно 1/256 — это вероятность случайного совпадения, и уже ее ничем не избежать, закон природы! Коллизии есть обязательно, в силу той причины, что строк длиной 32 байта гораздо меньше, чем строк длиной в «Войну и мир».
То есть у нас есть как бы сильная часть хэша, она хорошо видит маленькие изменения в тексте, но вообще, если в тексте испорчено более одного байта, работает по вероятности, а есть еще слабая часть хэша, она тоже срабатывает только по вероятности, но маленькие изменения текста она видит с меньшей вероятностью, зато для больших различий в текстах вероятность коллизий в сильной и слабой половине хэша уравниваются. Это значит, вообще говоря, что слабость слабого разряда не облегчает поиск коллизий перебором — в любом случае считать длину строки надо не 16 байт, а полных 32. А это это цифра такая, что никакие парадоксы дней рождения не помогут!
Что же касается вычислительных методов поиска коллизий, которые предположительно помогли бы избежать полного перебора, то вот тут, простите, дудки! Обнаруживается польза теории — каждая операция была алгеброй, поэтому свойства операций можно разбирать, можно доказывать, что сократить расходы и избежать полного перебора никак нельзя — вот по таким и таким причинам, потому что мы здесь умножали вон то на вот это, а такие уравнения, пардон, не решаются... Ну, для этого нужна некоторая сноровка, но есть люди, которые теорию любят и находить строгие доказательства умеют.
Беда, однако, в том, что все это вопросы опять же отвлеченные, практического смысла не имеющие, поскольку переделывать чужое изделие нельзя, даже приписывать к нему свою теорию нельзя, это незаконно, алгоритм не опубликован, значит, и теорию публиковать не положено, а отпадут эти тонкие вопросы авторского права лет этак через пятьдесят — тогда пожалуйста, уже и автора в точности нет в живых, и у наследников, если таковые имелись, права истекли. Но кому это нужно через пятьдесят лет? Если призадуматься, то и сейчас никому не нужно…
Виноват, забыл сказать главное — длина пароля, длина, длина!
Эти лихие парни умеют за день-другой отыскивать пароли длиной восемь символов, девять символов, причем иной раз управляются даже с кириллицей. Но против законов природы ничего не могут даже самые лихие люди, пароль из 12 символов невозможно найти при скорости перебора 10 миллиардов паролей в секунду (говорят, реальная цифра), а 16 букв нельзя найти не только видеокартой, но даже воображаемым квантовым компьютером размером с нашу галактику. Ну, разве что пароль паршивенький, который можно найти по словарю...
Но ведь самый паршивенький не тот, который можно найти по словарю в полсекунды, самый паршивенький тот, которого ни в каком словаре найти нельзя! Потому что его и запомнить нельзя. Я его обязательно напишу на бумажке, а бумажку просто случайно на минуту оставлю на столе, когда меня попросят к телефону в соседнюю комнату... Готово!
Значит, настоящий случайный пароль никуда не годится, он хуже осмысленного, из слов естественного языка. Но и осмысленный никуда не годится, его можно держать в голове, но он словарный, его мера неопределенности реально составляет не 96 бит, не 128, а только 10 или 12...
Как же тогда жить? Неужто хороших паролей не бывает вообще? Нет, можно полагать, бывают. Врут авторы книг, что нельзя использовать цитаты из Шекспира и библии. Еще как можно! Все дело в длине цитаты. Ну, немножко в орфографии и пунктуации. Хороший пароль такой: "В сие время заяц выскочил из лесу и побежал полем". Это Пушкин, господа, Пушкин! Строчка есть в собраний сочинений, но строки такой длины пока никто находить не умеет — ни перебором по буквам, ни перебором слов по словарю, ни перебором подстрок во всех строках всех классических сочинений...
Или кто-то уже умеет? Если есть такие умельцы, пусть похвастают, это интересно.
А ещё неплох такой: "Всиврзавыизлеипопо"
В тестах openssl прогоняются блоки размером 16, 64, 256, 1024, 8192 байта в течении трёх секунд, а затем выводится результат: сколько обрабатывается байтов за секунду при таких размерах блока.
Это важно, так как многие алгоритмы медленнее работают с более короткими блоками из-за медленных процедур развёртывания.
Свой вклад вносят и особенности железа. При разработке криптоалгоритмов учитывают скорость не только на обычных компьютерах, но и универсальность по отношению к другим типам железа.
Если бы функция претендовала на какой-нибудь стандарт, то такой режим должен быть опциональным и полностью отключаемым, так как во многих случаях замедление не нужно и стойкость не повышает, а нужна как можно большая скорость при массовой обработке данных: контроль целостности через коды аутентификации сообщений с общим секретным ключом или электронные подписи.
На конкурсе SHA-3 были полностью алгебраизированные построения — хэши на основе алгебры квазигрупп, соответственно работы очень хорошо обоснованные математически и изначально выгодно смотревшиеся на фоне некоторых других. Там и трудно поддающиеся криптоаналитическим атакам некоммутативные преобразования и гарантированное изменение блоков с определённой вероятностью.
Даже пара кандидатов квазигрупп-хэшей, разработанных солидными коллективами математиков, но увы не самых выдающихся криптографов. Один сильно прокололся в плане стойкости, на второй были найдены слабые атаки и по некоторому мнению из-за перестраховок его оставили только во втором раунде. При том, что до этого у них было много прототипов таких алгебраических хэшей, которые ломались совсем тривиально.
Это только навскидку. Масса исследователей претендует на то, что якобы доказательство стойкости их алгоритма обосновано математически. Само по себе это хорошее и желательное свойство, но оно недостаточно. И часто является иллюзией — многослойную инженерную конструкцию (например Keccak: нелинейный слой с просчитанной алгебраической сложностью, линейный с посчитанными уровнями диффузии) пытаются заменить алгеброй преобразований, полагая, что это более естественным способом обеспечит требуемые свойства. Это правильный подход в перспективе, но само по себе такое заявление ничего не даёт. Примеров взломанных алгоритмов на различных алгебраических подходах, теории графов, конечных автоматов, каких-либо ещё разделах математики — масса.
При этом есть масса неписанных правил: стараются выбирать достаточно изученный раздел математики, не слишком новый и экзотичный, не изобретать свою математику для криптографии (если ваш автор взял готовую известную алгебру — это нормально, а вот если изобретал свою и параллельно применил её в криптографии, то это может иметь чисто теоретический интерес). Другая проблема — сложность доказательства сводимости к некоей трудной проблеме (или её суррогату), слишком большие допуски, зазоры в доказательстве. Ну и т.д., само по себе наличие того, что вы перечислили недостаточно.
Т.е. случай, когда компьютеры гугла и прочих сервисов сливают все сведения человечества напрямую в суперкомпьютеры АНБ, которые смогут перебирать комбинации из всего когда-либо где-либо написанного, подстраиваясь под предположения о ваших индивидуальных предпочтениях в выборе пароля, вам неинтересен?
это типичный сервер, который работает memcache сервером. Он вычислял без дополнительного оборудования, естественно можно подбирать быстрее, но это всё можно свести на нет. Например берём из устройства /dev/urandom некоторое количество данных и записываем соль(salt), а хешировать мы будет слова hello world
в итоге получилось
Теперь радужные таблицы бесполезны. Даже если Вы создали сто миллионов паролей 'hello world' хеш будет разным каждый раз из-за разной соли.
Далее 1 млн раз выполняем hash=sha512(hash) и теперь бесполезен брутфорс, но зато теперь вход по правильному паролю также занимает время
АП защищает конкретную реализацию. Т.е. написал функцию сам, всё, она твоя.
Патент защищает идёю, но правильный патент раскрывает все внутренности. И патент не запрещает создавать реализацию для себя и поощряет реализовывать устройство с теми же функциями, но другими внутренностями
Наконец-то я понял! Спасибо, Unknown!
А за что? Что он такого плохого сделал? Подкинул уже упавший топик, оживил угасший разговор. Разве плохо?
Отключается, отключается, я же говорю, переменная Idling установлена в 256 – а можно установить ее в единицу, а можно установить 65 535 – но вот уже больше нельзя, чтобы больше, надо изменить разрядность переменной, взять dword вместо word, что тоже не очень сложно.
Переменить цифру хитрость небольшая, а там есть большие хитрости – для каждой функции есть альтернатива, параллельный вариант: не одна функция инициализации, а две разных, не одна хэш-функция, а две разных, не один поточный шифр, а два разных, и только асинхронный шифр только один, в этом случае выбор небогатый, выбирать можно только длину сдвигового регистра – либо после обрыва или пропуска будут испорчены пять байт, а дальше наступит синхронизация и все пойдет гладко, либо будут испорчены семь байт, — второй вариант кажется менее приятным, но он надежнее и прочнее. В других случаях альтернативные функции существенно различны – одна функция инициализации чисто алгебраическая, использует разного рода бинарные операции, которые можно назвать умножениями, а другая совсем не алгебраическая, там в двадцати строчках кода реализован довольно замысловатый клеточный автомат, алгебры уже никакой, логика динамическая, с выполнением операций по условию «если»; один хэш дает на выходе строку, похожую на случайную, любой байт на любом месте с равной вероятностью, комбинаторно это размещение с повторениями (выборка с возвратом), а у другого хэша строка тоже похожа на случайную, но это размещение без повторений (выборка без возврата), это тесно связано с используемыми методами, они очень, очень разные,.. Об этом уже тоже говорил – просто удивительно, как много всего можно запихать в 8 килобайт автокода!
Ах, очень жаль, что я ничего об этих текущих новостях не знаю!
Дело в том, что та штуковина, которую я так усердно разбираю уже несколько лет, тоже широко использует квазигруппы, да это само по себе и не редкость, это алгебра из учебника, сто лет известна, — но по способу, которым квазигруппы используются, есть сходство (отдаленное) только с алгоритмом RC4. Вот это выдумка дьявольской хитрости! Cтрока из 256 байт является как бы выпивкой и закуской в одном флакончике – эта строка задает таблицу умножения квазигруппы (сложение байтов по модулю 256 обычная конечная группа, сложение и последующая замена – квазигруппа, замена означает, строго говоря, умножение каждой строки квадратной матрицы — таблицы умножения конечной группы -– на некую произвольную подстановку, при этом матрица сохраняет свойства латинского квадрата, по этой таблице по-прежнему выполнимо умножение, уравнения разрешимы, однако в этой алгебре нет единицы, обратных элементов – зато есть другие свойства, совершенно волшебные), а затем эта же несчастная строка становится операндом, над которым выполняются действия. Следующее умножение двух элементов строки выполняется уже с некоторой вероятностью в другой квазигруппе, потому что два элемента строки только что поменяли местами… Вот где ужас – ползучее изменение самой используемой алгебры! Это уже не алгебра, а опять-таки нечто вроде клеточного автомата, и его дьявольская сложность, может быть, хороша в смысле усиления шифра и роста прочности, но она сильно запутывает даже ту сторону алгоритма, где изначально была довольно ясная алгебраическая идея: унарная операция над комбинаторным объектом. Тоже грандиозная штука: отображение на множестве перестановок, перестановка всех перестановок! Немыслимого размера объект, с ума сойти можно! Но все чудесно получается, целиком это объект и не нужен, просто профессор Ривест подходит с краю и начинает перебирать элементы по одному – перестановка A перешла в перестановку B, B перешла в C, далее у нас D -– и поехали, попилили по циклу подстановки (перестановки), это опять-таки алгебра из учебника, мы знаем, что ни одна перестановка из уже бывших не повторится, пока снова не выпадет A, а когда она выпадет -– не может не выпасть! – все повторится в том же порядке… Но предстоящую длину цикла оценить невозможно, это немыслимо трудно. Было бы легко, если бы в операциях нижнего уровня, над байтами, профессор Ривест ограничился одной квазигруппой, в таком случае можно рассуждать о том, как распределены циклы по длине на множестве всех подстановок, есть кой-какая теория, но эта теория ничего не стоит в случае, когда алгебра ползет, вместо алгебры какой-то мутный клеточный автомат… Ничего нельзя сказать! Предстоящую длину цикла нельзя оценить даже по вероятности. М-да, вот она цена алгебраической сложности…
Но к чему это я про RC4? Это к тому, что квазигруппы великолепная вещь, их использование открывает возможности необозримые, а если пользоваться аккуратно, то можно сохранить и теоретическую ясность. В той штуке, которую я разбираю, выпивка и закуска все же подаются на стол отдельно: отдельно таблицы умножения квазигрупп, отдельно операнды, так что получается намного проще (хотя по первому впечатлению ничего проще RC4 не бывает), но цели применения этих алгебр другие – не создание сверхбольшого комбинаторного объекта (перестановка всех перестановок), который используется вместо генератора случайных чисел, а хэши, средства обнаружения ошибок… По некоторым признакам видно, что автор двигался от других алгебраических средств, вообще давних, с богатой теорией – алгебраических кодов с исправлением ошибок, примитивных многочленов, — но в конце концов сделал выбор в пользу квазигрупп, похоже, для длинных контрольных кодов случайные функции оказываются надежнее мгогочленов с заранее известным расстоянием Хэмминга…
Очень интересно, что там делали с квазигруппами конкурсные авторы на NIST, жаль, что не знаю подробностей! Теперь, наверное, и не узнаю.
Вот то-то и оно, что там все свое. Ни на что не похоже, говорил уже, только в одном месте есть идейное сходство с RC4. который обладает тем же милым свойством – ни на что не похож.
Зазоры в доказательстве – это да! Я с теорией мучаюсь уже не первый год, причем нет уверенности, что получается та самая теория, которую имел в виду автор. Опасаюсь, что у него теории вообще никакой не было, просто взял и сделал – есть люди, которые без теории всегда заранее знают, что у них получится.
Неинтересен.
Я во все это, простите, не верю.
И в Змей-Грыныча не верю, и в Бабу-Ягу, которая кушает маленьких детей. Положим, я параноик, как это полагается каждому, кто интереcуется криптографией, но я все же не настолько параноик.
Я не верю в интерес АНБ ко всему человечеству, их интерес более избирательный – к отдельным лицам и группам лиц. Я не верю в сверхвозможности – это слишком много, это подмножества из какого-то чудовищно большого, а главное, неопределенного множества, между тем перебором нельзя одолеть все подмножества из множеств вполне определенных и довольно скромного размера.
Чего там гадать о моих индивидуальных предпочтениях, если я сам могу дать подсказку: я выбрал паролем некоторую строку из «Войны и мира». Ну? Что дальше? Всего три миллиона букв. Все подмножества этого множества – это сколько там будет, два в трехмиллионной? Ну, так много у нас не выйдет, мы берем не все подмножества, а кортежи, серии идущих подряд элементов. Но все равно это очень много, не перебрать, в этой вселенной времени не хватит, звезды погаснут раньше. Кстати, что-то сразу не соображу, сколько это будет — всех подстрок не длинее 512 символов? Очень много! И ведь 512 символов это ограничение только техническое, автор по своей прихоти установил для пароля такой буфер, а вообще в принципе длина пароля ничем не ограничена, можно брать «Войну и мир» целиком – и шифровать этим паролем «Евгения Онегина» (я делал такой опыт, в этом случае работа занимает около 6 секунд – 5.65 секунды на обработку пароля и какие-то 0.05 секунд на обработку текста)
Ох, и об этом я ничего не знал! Neverward, у Вас всегда полезные новости…
Я когда-то знал то авторское право, которое касается книг, музыки, спектаклей, фильмов – там все иначе. Я не могу написать сказку, где герой так беден, что очага у него нет, очаг нарисован на обоях, зато за обоями спрятана дверца – найди к ней ключик, и попадешь в волшебную страну… Это плагиат, это чужие сюжетные ходы. Предмет защиты ясен, конкретные случаи разбирают в суде. А что значит – патент защищет идею? Я разобрал алгоритм Ривеста RC4 – который, заметим, сам автор не публиковал, потому и разбирать его теорию публично, мне кажется, не совсем законно, — но я разобрал, понял, что там вместо генератора комбинаторный объект, перестановка всех перестановок, и быстренько написал клон, свою версию этой функции, но не на восьмибитовый байт, а на семибитовый, получается перестановка 128 символов вместо 256. И что, это законо, это теперь мое изделие, закон защищает мои права? Бред, мне кажется… Хотя все на свете бывает.
Патент в отличии от АП защищает идею изобретения. От смены 256 на 128 символов, или семи бит вместо восьми идея не меняется. Например есть патент page Rank или там map reduce. Там полностью описано, как они работают. Т.е. патент раскрывает всем идею изобретения. Хотите сделать поиск? Ноу проблем, изучайте идею page rank, додумывайте как можно сделать по другому, лучше и делайте, все будут только за. По сути патент как раз и нужен для того, чтобы вывести изобретение из коммерческой тайны и через некоторое количество лет сделать его общественным достоянием, плюс создать конкуренцию в виде других изобретателей, которые придумают то же устройство с другой внутренней реализацией. Это в идеале естественно.
По вашим намёкам было понятно, что это что-то наподобие квазигрупп, может ещё какая большая экзотика — неополя, например.
Материалы конкурса SHA-3 есть в открытом доступе. Квазигруппы использовали хэши Edon-R и NaSHA.
Поскольку RC4 был одновременно и собственностью компании и коммерческой тайной, то после восстановления алгоритма (обратного инженеринга) у компании RSA security (даже не Райвиста лично) осталось право только на оригинальное название. Теперь можно использовать алгоритм без изменений под названием ARC4. Можно делать модификации, наподобие VMPC[link3].
Милый Гость, вот какого черта! Что Вы такое несете?
Оставим в стороне грубости. Рассмотрим только логику и семантику высказываний.
Вижу грубые ошибки.
Что значит — оффтоп? Люди вышли за пределы темы топика? Люди вышли за пределы темы форума? Люди стали говорить о чем-то, неинтересном остальным присуствующим? Да нет, люди собрались и тихонько толкуют о том, что им интересно. Но тут приходит некий сердитый господин и доводит до сведения собравшихся, что им это неинтересно — заткнитесь, сволочи, прекратите оффтопить на оффтопичные темы, остановите срач!
Это как? Гость, автор этого сообщения, лучше меня знает, о чем мне интересно поговорить? И лучше админа знает правила форума? Бред…
Мне кажется, дело в другом, просто человеку хочется подраться. Но ведь если к его желанию снизойдут, то неизвестно, чем дело кончится. Могут того, побить… Тут на кого попадешь, знаете…
Это да, это я понимаю, мне очень нравится эта мысль — сделать какую-нибудь вещь общественным достоянием, я сам большой энтузиаст и общественник.
И других энтузиастов люблю, до сих пор пользуюсь ассемблером Arrowsoft 1986 года — эта штука замечательна тем, что генерирует объектный файл в точности того же формата, что MASM, совпадение полнейшее, до байта, но MASM платный продукт, по тем временам даже дорогой, а этот Arrowsoft гордо сообщает о себе: Public domain! Значит, я могу пользоваться этой штукой законно, для любых целей, в том числе и коммерческих, наряду с компилятором Тurbo C++ v.1.01, который я примерно в те же времена, году этак в 1993 или 1994 законно купил в Москве, заплатил деньги из своего кармана, получил коробочку с кучей дискет 360 кб и кучей красно-белых книжечек, полной документацией на русском языке. Эти книжечки и по сей день у меня, я их увез с собой на другой край света, полезнейшая штука, описание языка, описание библиотеки...
Но вот кто бы мне объяснил, на какие шиши живет автор ассемблера Arrowsoft? Что он кушает? Положим, работает он так, только для общественного блага, а его собственных детей кто кормит? А кто кормит остальных энтузиастов и общественников? Никому из них даже в голоу не приходит попросить за свою работу эту «несметную кучу буржуйских бабосов», которая уже упоминалась в теме?
Ой, квазигруппы — это бы хорошо, это еще цветочки, все же хорошая алгебра, в которой каждое уравнение имеет только одно решение. Ладно, пусть системы уравнений в квазигруппах не решаются, нет ничего похожего на гауссов метод исключения неизвестных, также умножение элемента квазигруппы на себя выполнимо, но результат этого «возведения в степень» ничем не похож на циклическую подгруппу, нет здесь ничего вроде теоремы Лагранжа — и из этого последствия вытекают необозримые. Но все равно квазигруппы это цветочки! А штука, которую я разбираю, вообще выше моего разумения, там твердо проводится такой принцип, что алгебру можно сделать из чего угодно. Условие замкнутости автора стесняет, это неудобное условие, чтобы операнды принадлежали одному множеству. Какого черта! Умножаем что угодно на что угодно! Увидели два каких-то объекта — и мигом определили для них умножение. Ну, получается хромая алгебра, полуразрешимая, но хоть какая-то — лучше чем никакой…
Конечно, хамство, в учебнике алгебры такого рода хамство встречается только один раз и сопровождается множеством оговорок: вектор можно умножать на число, но число нельзя умножать на вектор, в первом случае алгебра выходит плохенькая, но действие имеет смысл, умножение вектора на число просто растягивает его, а умножение числа на вектор смысла не имеет, — а в нашем случае автор не ограничивал себя такими соображениями, он умножает что угодно на что угодно, вектор символов на одиночный символ, один символ на вектор символов (в этом случае получается нечто похожее на многомерное векторное пространство), вообще любую строку на любую, короткую на длинную, длинную на короткую… Конечно, замкнутости нет, операнды из множеств разной мощности, значит, однозначной разрешимости уравнений нет, у каждого уравнения много решений. Ну и плевать! Дуй, Ванька, бога нет! Уравнение не решается относительно левого множителя? И прекрасно, оценили вероятность коллизий и пошли дальше. А для правого множителя уравнение решается? Тоже хорошо, полезная возможность, она тут же пристегнута, пошла в дело: можно умножать символ (короткую строку) на вектор (длинную строку), а можно делить, результат однозначно определенный.
Словом, такая свободная алгебраизация чего угодно. И все идет в дело, все пихаем в суп – унарная операция хороша тем, что имеет инволюцию, это тут же используется, процесс запускается вспять, а клеточный автомат хорош тем, что инволюции не имеет, и это тоже используется – вот вам необратимое преобразование, доказательно необратимое, просто тасуем колоду, вернуться к предыдущему состоянию нельзя, потому что процесс не просто детерминированный, а условно-детерминированный…
Так что про неополя ничего не знаю, но экзотики насмотрелся сам и знакомых алгебраистов помучил изрядно…
И при этом процедурно все просто, до идиотизма просто! Простая до невозможности формулировка «умножаем символ на шесть предшествующих» подвергается редукции, разложению, и оказывается, что она по сути не примитивна, не элементарна, в ней спрятано четыре разных примитива: бинарная операция (умножение символа на вектор), унарная операция (умножение вектора на себя), нециклический сдвиг вправо (понятие «предшествующий» или «следующий» логически примитивно, но в реализации может совпадать с операцией сдвига, отбрасывания левого элемента, приписыванием нового справа), и еще четвертый примитив, касающийся самого способа, которым задано умножение, он в полном смысле примитив, простой как веник, но неожиданный, не могу его здесь описывать… Да, а потом все эти примитивы используются порознь, в разных комбинациях… Цирк!
За ссылку спасибо, но я не смогу с этим ознакомиться. Немолод, нездоров, по-английски не читаю, математику понимаю ограниченно, систематической подготовки нет, так что боюсь помереть раньше, чем разберусь с той разработкой, которая уже оказалась у меня на руках, а она для меня представляет не только отвлеченный познавательный интерес, тут есть кое-какие моральные обязательства. Есть люди, некоторые живы, других уже нет… Конечно, хорошо бы ознакомиться с новинками, разобрать, сравнить, но я этого уже не успею.
Ну тогда
/Черновики/Руководства/ВопросыКандидатывFAQ/КриптографияПрактика[link4]. Там же есть и /Библиотека/Основы/ФонетическийПароль[link5]. И комментарии к топикам тоже почитайте.
По ссылке ходил, руководство Эдвина Суоминена по составлению фонетического пароля видел, спасибо.
Занятная выдумка, вроде вычисления числа Пи бросанием иголки на разлинованную бумагу, но мне кажется, что эта фиговина, несмотря на фонетическую упорядоченность (чередование гласных и согласных, имитация слов живых языков), трудно запоминается. Это немногим лучше, чем какой-то пароль или номер лицензии, который сгенерировал автоматически какой-то сайт и прислал мне с умоляющим письмом: вот ваш код — C14454427H1200A0414-64FEKF90 — храните его, не потеряйте, мы не сумеем вам его восстановить в случае утраты!
Вот я его и храню, только забыл, от чего этот ключ. Этот ключ, подобен "ключу от брошенной шкатулки в море..."
Чьи это слова? Пушкина это слова! Правильные слова, хотя в порядке слов есть погрешность, он изменен ради размера. Но Пушкин всегда прав! И Пушкин всегда лучше!
Вот к чему я клоню: стихов Пушкина я могу запомнить сколько угодно, а любые четыре строчки лучше всякого случайного пароля, порожденного автоматически или истинным бросанием жребия, сиречь канцелярской скрепки...
Пушкин лучше!
Но, разумеется, и здесь есть правила: строки "Я помню чудное мгновенье" и "Мороз и солнце день чудесный" в качестве паролей стоят там же, где слова Shadow и Tiger... Нельзя брать первое, что приходит на ум. Тривиальность — враг секретности.
Я думал об этом. Но жаль добро бросать.
Все же вторая половина не совсем лишняя, для хэша 16 байт коллизии второго рода ("дни рождения", пары текстов с одинаковым хэшом) отыскиваются легко, пространство перебора можно ограничить восьми- и девятибайтовыми векторами, а для хэша 32 байта коллизий нельзя найти никак и никаких. И никогда!
Так что слабая половина вроде совсем не лишняя, очень не лишняя... Вроде того, что в жизни называют слабой половиной, — тоже вроде и не годятся никуда, а иногда не лишние...
По стантадарту хэш должен быть полностью случайный. Это устовяшееся требование к нему.
Что касается фонетического пароля, правильный метод таков: генерируется один пароль, выбираемый[link6] случайным образом из пространства 2128, а затем пользователь уже сам придумывает способ его запоминания.
Эх... Вот что Вам сказать, коллега...
Придется признаться, что я с детства отличался болезненной склонностью к теоретизированию, потому и философская подготовка у меня обширнее математической, так что я долго ломал себе голову над тем, что это такое — случайность. Ужасной глубины вопрос, не чета мне люди на нем зубы сломали...
Так вот, даже та случайность, которая полная, все же бывает очень разного сорта — есть независимые случайные события, а есть зависимые. Те и другие случайные, но качество случайности разное, при бросании монетки уже наступившие события не влияют на вероятность последующих, а при сдаче карт из колоды влияют — вероятность того, что следующая карта будет пиковой дамой, растет строго монотонно: 1/17, 1/16, 1/15, 1/14...
Это все из учебника, а углубленный анализ показывает более тонкие различия — сдача карт из колоды и выход шаров из тиражного барабана вроде бы совершенно тождественные процессы, то и другое цепочка зависимых случайных событий, настоящая случайная выборка без возврата, — ан нет, различие есть, чтобы его уловить, приходится ввести понятие отложенной случайности, так и пишем: наступившее событие, но неизвестное, мы считаем актуально ненаступившим! И соответственно вычисляем вероятность его наступления.
Вот оно — мы не знаем, орлом или решкой легла монета, потому что она закатилась под диван, так что для нас это наступившее событие находится в будущем. С колодой карт то же самое — настоящим случайным процессом является не сдача колоды (прометка), а тасование, а сдать карты можно только в том порядке, в каком они лежат в колоде (если не дергать!), так что прометка не случайный процесс, а только раскрытие (развертывание) случайного объекта (комбинаторного) — случайной перестановки 36 карт... Да, и этим сдача карт принципиально отличается от выхода шаров из тиражного барабана лотереи: там тоже любой номер может последовать за любым, но это случайность актуальная, информация о наступлении событий не отстает от событий ни на шаг...
Так вот, к чему вся эта теория? Это к тому, что случайность бывает разная, такая и этакая. Есть случайные объекты, а есть случайные процессы. Хорошая гамма, зависящая от пароля и от nonce, есть в точном смысле случайный объект — в точнейшем смысле, самом строгом, по учебнику: это случайная функция, то есть функция от случайного аргумента. Поэтому даже приставка псевдо- применительно к такой случайности выглядит лишней, это настоящая случайность. Но это не процесс, а объект — уже готовый, вроде стасованной колоды. Зато асинхронный шифр по своей природе не объект, а процесс — у него есть траектория, после замены во входном тексте хотя бы одной точки на запятую шифртекст меняет траекторию, все символы будут другими. Тоже случайность, но другая.
Да, да, и вот это же самое касается хэша, у которого левая и правая половина строки изменяются по разному закону! Обе половины полностью случайны, это строгое утверждение, но при малых искажениях текста левая и правая половины изменяются с неравной вероятностью. Одно другому не противоречит — не все случайные события равновероятны, не все распределения случайных величин равномерны...
Вот относительно гаммы есть это требование — равномерность, равновероятность, есть еще более тонкие условия Голомба. А относительно хэша... ну, не хочется спорить с людьми, которые в текущем положении вопроса осведомлены лучше меня, но все же должен заметить, что если общепринятое требование состоит в том, чтобы все символы хэша были равновероятны — не просто случайны, а именно равновероятны! — это требование несуразное, оно сформулировано с грубой ошибкой. Более точное и резонное условие — чтобы все символы хэша с равной (и очень высокой) вероятностью изменялись при малейших изменениях в тексте, это как раз в просторечии и называют лавинным эффектом, но и в такой формулировке есть теоретический изъян — это требование легко выполнить жульническим образом, схитрить. Очень просто: сделать так, что символы хэша зависят не только от символов текста, но и друг от друга. Истинная разрешающая способность хэша состоит в том, что на одну ошибку в тексте он отзывается ошибками в 21 байте из 32, а мы делаем перемешивание, складываем левую и правую часть — и пожалуйста, 32 ошибки на 32 байта. Только это жульничество и шарлатанство, формально условие соблюдено, но пользы никакой.
А от слабой половины хэша есть польза, причем реальная, даже двоякая: во-первых, для длинного хэша трудно найти коллизию, во-вторых, у нас появляется тонкий признак — по числу ошибок хэша я могу хотя бы приблизительно сказать, что в этом тексте ошибки пошли потоком, а в этом есть только единичные ошибки — одна, две, три, более трех, но менее двенадцати...
Но уж если кому-то сильно не нравится функциональная неоднородность хэша (неравноценость разрядов, несовпадение физической и эффективной длины), тогда другой путь, тяжелый: слабую часть отбрасываем, а сильную удваиваем, доводим до 32 байт, — только вычислительные затраты будут уже не 120 команд на букву текста, а 220 команд.
Это много или мало? Стоит ли овчинка выделки?
Вопрос об истинной случайности? Этот вопрос по-настоящему не решён никак, о чём есть оговорки в работах по криптографии. К нему подходят чисто с утилитарной точки зрения. Обычно требуется создать равномерное случайное распределение и вводится понятие противника, который не сможет воспроизвести результат, не потратив определённого количества вычислительных затрат на восстановление внутреннего состояния.
Необходимое, но недостаточное, скажем так.
Нахождение любого различителя, быстрее чем полный перебор, между хэшем и случайной функцией — взлом хэша. Хэш должен быть неотличим от т.н. "модели случайного оракула" (Random Oracle Model). Все требования к хэшу по (псевдо)случайности (равномерность распределения, неразличимость подмножеств выхода, лавинный эффект, невозможность найти связь между входом и выходом, нахождение первых и вторых прообразов) должны укладываться в ROM.
Можете посмотреть, как вопрос неразличимости в ROM решён для функции KeccaK[link7].
Хэш — это не просто контрольная сумма. Противник не должен уметь угадывать текст по хэшу, не должен уметь угадывать насколько сильно поменялся текст по изменениям хэша. Если это требование несоблюдено, противник может строить атаки на криптографические протоколы.
Что касается просто контрольной суммы без требования случайности (а только различимости на разных текстах), наверное, криптографы долго думали и пришли к выводу, что это не реализуемо без случайности — просто потому, что длина этой контрольной суммы сильно ограничена по сравнению с длиной текста, от которого она берётся. Имеет ли смысл такой узкоспециальный вопрос, как контрольная сумма (не хэш!) от текстов длиной порядка самой контрольной суммы? Не могу сказать. Наверное, такую задачу можно свести с каким-то случайным перестановкам. Напомнило/comment52716[link8].
Всегда есть выбор – не выводить изобретение из коммерческой тайны или выводить и запатентовать. В первом случае Вы получаете монополию до тех пор, пока чья нибудь умная голова не разгадает секрет, во втором Вы получаете монополию на время, теперь секрет Вы сами раскрыли всем и монополию защищает закон. Однако монополию надо ограничивать, чтобы стимулировать конкуренцию. Автор изобретения имеет много времени, чтобы создать новое изобретение и запатентовать его. Таким образом закон стимулирует прогресс и конкуренцию.
чтобы рассматривать что такое случайность надо сперва определить о какой случайности идёт речь. Хеш md5(x) не случаен для одного и того же x. Правильнее сказать про хеш так:
Существует hash=md5(x), но не существует функции x=de_md5(hash) с приемлимой вычислительной сложностью.
Далее – под случайным событием иногда понимают не то, что им является. Например я подкидываю монету. Какова вероятность, что монета лежит орлом вверх? Сейчас она равна 100%, это свершившийся факт, просто никто пока не знает о нём. А вот вероятность, что Вы угадаете как лежит монета будет в идеале равна 50% в случае если нет никакой обратной связи между Вами и монетой. По сути в большинстве случаев под случайным событием имеется в виду такое событие, о котором не было известно, что оно произойдёт. В случае с квантовыми процессами из-за принципа неопределённости получается, что ещё и нельзя получить точную информацию, т.е. по сути из-за физических ограничений нельзя предугадать процесс и он становится в чистом виде случаен. Бритва Окамма удаляет вопрос о том будут ли две системы с полностью одинаковыми исходными данными развиваться одинаково, так как это никак нельзя проверить, т.е. нельзя создать или даже просто пронаблюдать две абсолютно одинаковые системы.
Ссылка очень хорошая, полезная. Смотрел с интересом, но пока не разобрался до конца, только понял, что по-настоящему новых вещей на свете не так уж много, поэтому разные люди не сговариваясь приходят к одному и тому же.
Самым уязвимым для критики местом оказалось, что у хэша есть неоднородность, левая и правая часть строки по-разному отзываются на ошибки в тексте, ну, и за этим вопиющим безобразием как-то незамеченным осталось сообщение, что это только один хэш из двух, а есть второй с другими свойствами, его выходная строка размещение без повторений. Так это просто кусочек более длинной строки, случайной перестановки всех 256 байт, можно вычислять ее полностью, а 24, 32 или 64 байта из 256 берутся просто ради экономии, это сокращает вычисления.
Но как раз у этого алгоритма теория жуткая! Конечно, случайных перестановок не 256, а 256! (примерно 10+e507), но это очень, очень проблемная штука — доказать, что хэширующая функция может порождать любую перестановку из всего множества возможных. Дикая задача! На самом деле она даже не сводится к вопросу, может ли подгруппа от данного набора образующих покрывать всю группу, как раз на этот счет есть известные результаты, почти классические, считается, что два произвольно выбранных элемента (случайных, случайных!) почти наверняка порождают группу целиком, — но это результат, как говорится, без ограничения общности, предполагается, что множители берутся в любом количестве и во всех степенях. А в реальной программе это невозможное условие, никто не может брать множители в ЛЮБОМ количестве, как раз количество ограничено, и тогда для всякого частного случая доказательство того, что среди произведений есть все 256! различных перестановок, становится невыразимо трудным. И от автора не приходится ждать помощи, хотя есть сведения, что он жив, просто по житейским причинам переменил интересы, сейчас работает крановщиком в городе Ашдоде. Или в Ашкелоне, точно никто не знает...
Да, так этот хэш, где случайные перестановки, он с виду красивее, элегантнее, и на порчу одного бита текста отзывается сразу вся строка — все 24 байта из 24 или 32 из 32, но радости в этом мало, потому что нет средства точно оценить вероятность коллизии, когда вся строка случайно совпадет с правильным значение. Очень поганая теория! Хотя в реализации есть какие-то бешеные хитрости, чтобы этот изъян в теории обойти. Ну, усложнения, которые не устраняют трудность, а переносят ее в другое место — нельзя доказать, что все произведения будут различны, так докажем хотя бы, что все множители будут различны: хэширование романа "Война и мир", который содержит три миллиона букв, состоит в том, что перемножаются три миллиона перестановок — и все разные, все различные! Но опять же не доказано, что различающиеся наборы множителей дают различные произведения, наоборот, легко доказывается, что произведения будут совпадать, коллизий сколько угодно, потому различных произведений всего-навсего 256!, а различных наборов множителей длиной в "Войну и мир" гораздо больше, — и не доказано даже более слабое утверждение, что вероятность коллизии будет немногим больше 1/256! Вот в чем загвоздка...
Поэтому красота этого алгоритма меня уже не радует, безумные хитрости реализации тоже не радуют (они еще и дорогостоящие, расходы на вычисления быстро растут), а вот тот алгоритм, где у хэша есть сильная и слабая половина, радует гораздо больше. Теория простая и понятная! Ну, раздражает людей слабая половина строки, откинем ее к черту, но даже и у этой слабой половины теория яснейшая, оценки вероятности элементарнейшие, все выражается аликвотными дробями, уровень математики древнеегипетский и вавилонский...
Для вероятностных процессов понятия априорности/апостериорности/(не)детерминированности давно приняты.
Кстати, с практической точки зрения, важен ещё объём памяти в процессе исполнения алгоритма, не только скорость. Безотносительно к объёмам памяти современных компьютеров, он всё равно должен быть минимальным для универсальности. RC4 — один из самых быстрых, но во многих случаях (микроконтроллеры, смарт-карты) неприемлимый по объёмам памяти.
Вспомнил старинный анекдот. "-- Это такси! — Такси. — А где шашечки? — Так вам нужны шашечки или нужно ехать?"
Вот и у нас то же самое. Что важнее — чтобы по хэшу было трудно найти прообраз (истинный или коллизионный) или чтобы хэш был по свойствам неотличим от этой самой Модели Случайного Оракула? Люблю теорию, но думаю, что первое важнее. А если кто-то скажет, что все, все без исключения условия в этой модели обязательны и рациональны, не поверю. Вам ехать или вам шашечки? Теория штука общая, а теперь объясните мне частный случай, в цифрах — в строке хэша ровно 16 байтов из 32 в ответ на порчу одного бита текста изменяются с вероятностью ровно 5/16 — вот и скажите,
в каком году умерла бабушка швейцараво сколько раз это облегчает подыскание прообраза.Сам сосчитать не могу, но предполагаю, что уменьшение расходов незначительное.
Посмотрю, спасибо. Вот только пойму ли — это вопрос...
Без разницы. В криптографии нельзя понять заранее "поедет такси или нет". Может оно едет, но нас обманывают? Пока кто-то не раскроет нам глаза, показав взлом. При создании алгоритма можно только надеяться, что правильно нарисовали весь чертёж, включая шашечки и тогда оно будет ездить как надо в рамках нашей модели, вдобавок ещё и ограниченной и несовершенной.
Поэтому без теории совсем никак. Например, это[link9] — атака. И это[link10], т.е. это[link11] тоже. Если они будут быстрее брутфорса — то это сертификационный взлом и снятие алгоритмов с конкурса даже при отсутствии практических применимостей.
Если что, у нас есть FAQ по общим вопросам криптографии[link12] и статьи по доказуемой безопасности.
Ах, не нравятся мне ихние буржуазные порядки! Прямо законы джунглей.
Угадал чужой секрет — схватил и бежать. И у них всегда так было, еще папаша Гека Финна говорил так: "Когда тебе подвернется курица, хватай ее, даже если она тебе не нужна, потому что кому-то другому она пригодится, а доброе дело никогда не пропадет." Оцените логику этого утверждения! И его мораль тоже...
Вот и законодательство такое же, в законе прямо просвечивает эта идейка, что чужая курица создана специально для твоего счастья. Сумел украсть — хорошо, а не сумел, жадный собственник спрятал ее под замок — не огорчайся, права этого скупердяя закон ограничивает сроками, подожди немножко, и курица будет твоя...
Да, именно так и выходит — я построил дом, он мой безусловно, целиком и навсегда, и от меня перейдет детям и внукам, а если я написал роман, у детей и внуков права на гонорар кончаются через 50 лет после моей смерти, а если я изобрел зубной порошок с низкой абразивностью, то меня лишат прав на это изобретение еще при жизни, лет через 17...
Это ради прогресса? Нет, тут другая идея, вообще социалистическая — люди с трудом признали, что мои штаны принадлежат только мне, но все же не могут смириться с мыслью, что бумаги в моем столе тоже принадлежат только мне. Нет, искусство принадлежит народу! И новая техника является народным достоянием...
Ладно, это ихняя буржуйская мораль, загнивающий Запад, известное дело, еще в школе проходили, но кто же их все-таки кормит при таких порядках? Как они при таких жлобских законах с голоду не перемерли?
Уму непостижимо...
Весьма немного, около полутора миллиардов (длина текста помноженная на максимальную длину подстроки).
Агафон, ну сейчас точно оффтоперы набегут. Все социалистические, антибуржуазные и антикопирайтные идеи тоже придумали на Западе и именно там они и получили максимальное распространение (свободное ПО, добровольный отказ ряда изобретателей интернет-протоколов от их патентования и от миллиардов потенциальной выгоды и пр.). Мы не обсуждаем полит. вопросы в общей ветке.
Бумаги в столе – вам, а вот если вы их всем показали, по своей воле поделившись информацией (бумаги то остаются при вас) то уже не ваше дело как этои информацией распорядятся другие, потому как это уже и их информация. Ну это если по совести...
Бизнес на "интеллектуальной собственности" противоречит совести. :-)
Вот да, русским в силу присущего им коллективизма как то в голову не приходила мысль, что можно что-то требовать за раздачу того, чего от тебя при этом не убывает, и как следствие придумывать то, что и так всегда было, не было никакой необходимости.
Вот представьте себе, да... Особенно ярко это проявляется в случае "интеллектуальной собственности" на лекарства – от этого люди, которые при ином раскладе могли бы жить, умирают конкретно... Ну а если это чьей-то совести не противоречит, то что ж, для таких свобода совести объявлена... Только вот "есть и высший суд"...
Да, если RC4 по своим запросам к памяти не проходит, тогда плохи наши дела. Я ведь нарочно разбирал RC4, писал минимальные реализации — и не так много памяти ему надо, можно обойтись двумя строками по 256 байт, не считая буфера для входного текста. Неужели это много?
Вообще я уже видел вот здесь – http://csrc.nist.gov/groups/SMA/ispab/documents/minutes/2008-06/HashCompetition-June2008_BBurr-JKelsey.pdf – Келси пишет о случаях, когда у вас, мол, нет в запасе 16 килобайт памяти, но чтобы одного не набиралось — это что-то бедность ужасная...
То изделие, которое у меня на руках, как я уже говорил, включает множество вариантов, там есть реализации на любой вкус — так вот, самый быстрый из поточных шифров расходует всего 9 команд на букву и требует для исполнения таблиц размером в те же 512 байт — то есть по запросам совпадает с RC4, но не совсем, все же режется, не укладывается в такие тесные рамки — для вычисления этих таблиц нужны еще самое меньшее две свободные строки по 256 байт, так что один килобайт это минимум, без этого работу начать нельзя. И это без буфера для текста...
Да, а про максимум и говорить страшно. Тот хэш, который со случайными перестановками, можно кое-как запустить на двух килобайтах памяти — даже на полутора, хотя для этого нужны ухищрения какие-то крохоборские, а тот хэш, где у строки есть сильная и слабая половина, работает с большими таблицами, занимающими 20 килобайт, причем сократить эту цифру можно только до 16, а меньше уже никак...
Да, и я знаю, что эта программа писалась и компилировалась на машине IBM PC XT с тактовой частотой 4.77 мегагерц (первые версии датированы 1997 годом), и прекрасно работала на этом хилом процессоре 8088, а оперативная память 640 кб для нее даже лишняя, ей было достаточно меньшего...
А у современных микроконтроллеров таких ресурсов нет? И у смарт-карт нет?
Странно...
Представьте, что это может быть сверхминиатюрный чип, работающий от радиоволн и наклеиваемый на товар или проездная карточка, или брелок от замка. Там и так сильно экономят.
Или у нас есть сервер (VPN, анонимная сеть), обслуживающий 100000 соединений одновременно, каждому к примеру по 16 хэширований на соединение. При расходе 4 кбайт нам потребуется около 6 гиг памяти. Это уже много для сервера на виртуальном хостинге, а ведь ему нужно память ещё подо что-то.
Да и патентованный алгоритм, даже от ведущих разработчиков, обычно никому не нужен. Даже если есть спрос и деньги, лучше дождаться бесплатного аналога, у которого есть шанс стать стабильным стандартом.
Это хорошее качество и позволяет надеяться, что идеи копирайта в России понимания не найдут и умрут так толком и не родившись, несмотря на то, как их активно насаждают.
Это не кража, изобретатель не теряет возможность производить своё устройство. Патент получен на разгаданную коммерческую тайну нельзя. Патент даёт защиту от монополии. Если Вы думаете, что бесконечные монопольные права дают пользу, взгляните на десятки умерших стандартов компрессии, просто потому, что способы сжатия были запатентованы и продавались. Вместо этого Вы сейчас пользуетесь бесплатным софтом потому, что бесплатный выгоднее для пользователя, чем платный. Возникает вопрос – как извлечь прибыль? Прекрасный вопрос, зачем миру очередной стандарт шифрования или сжатия если текущие полностью выполняют свою задачу? Никто не даст и цента. Можно изобрести велосипед о пяти колёсах с планетарными передачами. Но продать массово – вряд-ли. Потому что не все изобретатели понимают, что даже лучшее по одному признаку может быть совсем не нужно из-за других, не очевидных изобретателю признаков.
Через 70 после смерти или после публикации. Если автор издал роман в 20, прожил до 100, то его роман будет приносить прибыль 150 лет. Впрочем скорее всего он перестанет приносить прибыль через пару лет из-за того, что покупать перестанут. Да и вообще сейчас дети уже не читают, они не будут и даром читать книги в будущем. Писатели должны были следить за рынком сбыта, чтобы он не исчез. Все производители следят же.
ничего подобного, если никто не разгадает( как часто бывает с всякими колами или хейнзом), то хоть тыщу лет можете получать деньги ничего не патентуя. Но защиты от другого ума, который может быть разгадает Ваш секрет у Вас нет(есть защита от кражи коммерческой тайны). Либо получайте защиту государства в обмен на гарантию монополии. Всё честно.
нет, это антимонопольная защита. Если автор желает, он может зашифровать свою книгу и выложить зашифрованную в общий доступ. Никто не вправе заставить автора расшифровать произведение(кроме Английского правосудия конечно)
Не думаю, что Марк Цукерберг умирает с голоду.
Виноват, исправлюсь!
По вопросам морали и права больше оффтопить не будем, будем оффтопить только по математике. Но уж от души!
А как иначе? Иначе и неинтересно. Только оффтоп и флуд украшают жизнь на форумах. Ну, еще иногда флейм.
Простите, мне кажется, оценка неверная. Вы умножаете там, где надо возводить в степень.
В строке длины N из разных символов есть ровно (N-M)+1 подстрок длины M.
Например в строке длины 3 "abc" есть только (3-2)+1=2 подстроки "ab" и "bc" длины 2.
При некоторых одинаковых символах разных подстрок может быть меньше.
Полюбому меньше чем N. Поэтому подстрок длины не больше чем М будет меньше чем N*M.
Где тут надо возводить в степень?
В котором, кстати, обвиняемого могут привлечь к ответственности за отказ давать показания против себя, поэтому и с паролем у них всё логично.
Если я правильно понял, эти понятия априорности-апостериорности как раз то самое, что по-русски называют проще, условными и безусловными вероятностями в модели зависимых случайных событий. Предварительная вероятность того, что при сдаче колоды пиковая дама выйдет в точности восьмым номером, равна 1/36, но потом она меняется в зависимости от уже наступивших событий — потихоньку растет, если среди первых семи карт пиковой дамы не было, либо падает до нуля, если пиковая дама уже вышла.
А я еще о другом говорил — сверх всего этого добавляется понятие отложенной случайности. Колода карт не процесс, а комбинаторный объект, перестановка. И сдача колоды не случайный процесс, а только иллюзия процесса, это перечисление, перебор элементов статического объекта — и только в том порядке, в каком они расположены. Случайный процесс был раньше, когда колоду тасовали, но это отложенная случайность, она актуализируется при сдаче колоды — сдача похожа на настоящую случайную выборку без возврата.
Вообще понятие полезное, мне кажется, потому что позволяет избежать двусмысленных определений во многих важных случаях.
Допустим, я утверждаю, что гамма шифра такого-то со стороны статистики описывается в два слова — она имеет статистику идеальной монеты, любой бит с равной вероятностью может быть единицей и нулем. Но я помню, какое лицо было у полковника Т., когда он это утверждение услышал. Много лет прошло, а я помню. Полковник Т. был не совсем военный человек, он был математик, доктор физ-мат наук, лауреат госпремии, а служил он в советские времена... ну, не будем говорить, где он служил. Главное, служил в таком месте, где предмет знали хорошо, а по специальности полковник Т. был как раз не алгебраист, а вероятностник. Вот у него лицо сразу отвердело, он насупился и сказал тихим голосом, что про монетку просит меня забыть, чтобы я больше при нем таких вещей не говорил. Потому что у настоящей монеты настоящие случайные испытания, на каждом броске может выпасть орел или решка, а гамма есть вычислимая функция, там никаких "или", все биты определены заранее — даже самые далекие, те, до которых нам эту гамму вычислять миллиард лет...
Вот чтобы не спорить в таких случаях, процессы и объекты полезно различать. Гамма не процесс, гамма готовый объект, точно как стасованная колода. Но это случайный объект — и случайность не в том, что единиц и нулей в гамме поровну, а в том, что этот объект наугад выбран из множества других — гамма зависит от пароля и еще от одной строки, которая не повторяется никогда (показания системных часов по полному формату: год – месяц – день – час – минуты – секунды – сотые доли секунд – и еще старший байт года, редко изменяющийся, заменен на счетчик файлов). Да, это случайность настоящая, время идет только в одну сторону, не повторяется... А статистика гаммы со случайностью никак не связана, это статистика монеты (настаиваю на своем!), но причина этих статистических свойств другая, не связанная со случайностью (и равновероятностью) каждого следующего бита, причина в способе вычислений — автору нужно было равномерное распределение, он сделал равномерное, а мог сделать другое, из равномерного любое другое получается с легкостью.
PS. Да, а насчет количества подстрок в "Войне и мире" я, кажется, наврал... Похоже, прав коллега, кортежей не так много... На бумажке надо проверить!
Вот если противник не может различить объект от процесса, в особенности предсказать биты, определённые заранее, тогда задача и выполнена.
А как же квантовая механника? Разве из теоремы Белла[link13] не следует существования истинной случайности?
В общем, противник не должен никак различать, снята гамма с шифра или это запись бросков идеальной монеты.
Это виднее тем, кто её использует. Ну вроде как истинная случайность идёт оттуда, да, хотя вот spinore предупреждал, что там всё не так идеально.
Вспомнился другой старинный анекдот. Американский астронавт из-за какого-то технического сбоя приземлился не там, где надо, забросило его куда-то в Сибирь. Выбрался он из своей капсулы, отцепился от парашюта, пошел искать людей. Шел по тайге целый день, к вечеру набрел на избушку, из трубы дым... Вошел, там сидит за столом мужик в ватнике, в ушанке, в валенках и лопает тушенку из банки. Астронавт бросается к нему радостно, спрашивает: "Ду ю спик инглиш?" — а тот отвечает невозмутимо: "Йес, ай спик. А что толку?"
Вот-вот, это наш случай... Положим, все цели уже достигнуты, и противник уже ничего не может, функция неотличима от настоящего случайного процесса, ничего предсказать нельзя, ни одного бита. А что толку? Если заранее известно, что это никому не нужно, навалом бесплатных продуктов от известных разработчиков. Понятно почему автор пошел в крановщики в Ашдоде (хотел пойти в водители автобуса, но водители автобусов там все арабы, это их монополия). Правильно, кушать-то надо, это только я могу заниматься пустым делом, потому что пенсионер...
И то подумываю переключиться на что-то другое — или в шахматный кружок запишусь, или стихи писать начну.
Ну если так, то да.
Криптография сейчас прошла пик коммерческо-предпринимательсой активности (патенты и инвестиции) и стала больше научно-исследовательской (оклады и гранты).
А все же мучит меня наивный вопрос...
Ну, если никому ничего не надо, у всех все есть, за каким чертом объявляют мировые конкурсы — сначала поточных шифров, потом хэшей?
Собирают народ, тусуются, потом еще ноют, что успехи невелики, новых идей нет, прорывов нет... А им, понимаете ли, хочется, чтобы поточный шифр был быстрее RC4, при этом прочностью превосходил любой блочный, заодно содержал встроенные средства обнаружения ошибок — конечно, без увеличения расходов, все за ту же цену, и еще заодно имел какие-нибудь полезные свойства, скажем, был бы асинхронным, читался с любого места, после обрывов и пропусков. Или уж прямо исправлял ошибки...
Положим, списочек пожеланий скромненький, все это осуществимо (кроме последнего пункта), но ведь вопрос стоит иначе — ребята, вы не шутите, вам это нужно? Или не нужно?
Вот в чем вопрос!
Стойкость существующих потоковых шифров и хэшей недостаточна. А предложить более стойкий, но более ресурсоёмкий вариант легко. Все финалисты SHA-3 и так слишком медленные.
Вот оно!
Прямо с этого вопроса я и начинал — что считается быстрым, что медленным.
120 команд на букву — это медленный хэш или быстрый?
Про поточные шифры не спрашиваю, имею с чем сравнивать, а в той коллекции, которая у меня на руках, есть разные, от очень быстрого до очень медленного — 36 команд на букву это, пожалуй, слишком много для поточного шифра, хотя он особый, с повышенной прочностью и со встроенным хэшированием (короткий хэш 64 бита). В этой коллекции есть все, кроме блочного шифра — против блочных у автора явное предубеждение. Да, и, разумеется, никакой арифметики, никакой несимметричной криптографии...
Ответ уже знаю, скачал себе по наводке Unknown'a документацию по Edon-R и NaSHA — Edon неимоверно быстрый, просто сверхскоростной, по сравнению с ним 120 команд на букву — скорость улитки.
Теорию еще не разбирал, в исходники тоже только одним глазом глянул, еще ничего не понял, только заметил, что написано все на самом классическом C без всяких плюсов, а в теории эти славяне что-то очень налегают на классификацию — старательно отделяют класс аморфных квазигрупп, без коммутативности, ассоциативности, единиц, еще чего-то... Ненужная роскошь! Да, и способ построения таблиц умножения громоздкий, запросы к памяти большие. Не-а, не пойдет, у Ривеста проще! Однако ж скорость исполнения неимоверная, впечатляет.
Разве срок действия патентов ограничен? Можно же бесконечно продлевать права, когда истекают. Пример — авторское право на диснеевских героев и символику, оно существует уже более 90 лет, истекало уже не раз, но каждый раз специально под этот случай принимали новый закон, по которому его продлевают еще на несколько десятилетий. Вообще, имхо, адекватная страна не должна признавать чужих патентов вообще, и адекватный срок на патенты — 5 лет для ИТ, 10 — для техники, 15 — для медицины, причём без возможности продления и без права продажи, т.е. сделать патент неотчуждаемым. Можно будет либо самому им пользоваться, либо ты будешь обязан продавать лицензии по антимонопольным ценам, либо отберут в общественное достояние (если сидишь на патенте как собака на сене) [патентный троллинг]. Ну, или нужна какая-то альтернативная система компенсации труда изобретателей.
Да, есть такое понятие, как "полное покрытие патентами всех путей развития": куда ни плюнь — уже запатентовали, свободны только заведомо худшие пути. Хрестоматийный пример — h264. На самом деле h264 — лучший, и разработчики кодеков столкнулись с серьезной проблемой: как ни сделай хорошо — получишь запатентованные алгоритмы h264. Это перекрытие направлений для будущего развития кодирования видео. Так сложилось, что существующие реализации используют от силы 60% запатентованных идей.
В opensource-подходе принято считать, что патенты — безусловное зло, наверняка на эту тему уже кто-то написал статью со всеми обоснованиями.
Трудно сделать одновременно быстрое, безопасное и нетребовательное к ресурсам решение.
Им некогда, они
бастуютзаняты накруткой счётчиков на главной странице (см. внизу, что они в топ пытаются вывести).Победители конкурсов НИСТ с голоду не умирают. Да и работа для них, пожалуй, сама собой находится. А патенты, хотя и создавались для защиты народных изобретателей, по сути уже давно являются средством расправы между монополиями. Сейчас патенты — тормоз прогресса. И слова про "запатентовать алфавит" именно оттуда идут.
"Зонтичное патентование" ещё.
На этом строится вся стойкость практически всего направления криптографии на квазигруппах. Иначе легко будет взломать или не будет выигрыша по сравнению с обычными группами. Это самое главное обоснование. "Shapeless" квазигруппа — это, очень грубо и некорректно в математическом смысле выражаясь, некий приблизительный аналог групп на простом числе, примитивном полиноме, только без таковых в явном виде (теория здесь ещё недостаточно проработана). Если группа не аморфная, то вылезают цикличности, линейности, явные закономерности. Даже на слайдах в других работах видно, что при визуализации операций в неаморфных квазигруппах могут быть вместо картины шума какие-то фракталы и линии. А аморфные всегда дают результаты, неотличимые от шума, по-крайней мере визуально и статистически. Для больших квазигрупп полным перебором аморфность не найти — используют критерии, считают числа Каталана и пр.
Жалко, что Edon-R не прошёл в финал, хотя бы вместо невнятного JH, но раз нашли какую-то атаку, то ничего не поделаешь. Плюс, он идёт особняком, как ультрабыстрый алгоритм. Авторы хотят и асимметричную криптографию изобрести на ультрабыстрых принципах. Но ultrafast и квазигруппы — не мейнстрим и многие относятся к этому со скепсисом.
Пос скоростям алгоритмов, смотрите сами в софте[link14] и железе[link15].
Уважаемый Unknoun!
Благодаря Вам я за последние дни узнал много нового. Я ведь не ленюсь, по каждой ссылке хожу, читаю, просто у меня пока нет сил разобрать каждый текст обстоятельно. Но все же узнал про 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. И то же самое при выполнении операций по модулю (простого числа или даже не слишком простого), но при модульньной арифметике возведение в степень становится даже проще, а извлечение корней и логарифмирование становятся невыносимо трудными. Конечная группа! Это можно понять, но где здесь квазигруппы, каким боком? Пока не понимаю, потому что те, квазигруппы, которые хорошо знакомы, они вообще без арифметики, в чем их прелесть и заключается — алгебры без реляционной части, без отношений «больше-меньше», эти алгебры можно задавать таблицами на множествах любых объектов, имеющих или не имеющих количественное значение: годятся буквы, числа, шахматные фигуры, игральные карты, разноцветные шары, фишки, пуговицы от пиджака…
Может, все же у этого Глигорски и компании не квазигруппы, может, он этим словом что-то другое называет? Или я что-то путаю по невежеству? Вообще надо вчитываться, разбирать теорию, только это не на один день занятие, а у меня сейчас сил нет, нездоров. Ладно, посмотрим еще, вернусь я к этой штуке, если буду жив.
Но за те квазигруппы, которые у нас кругом, везде и получаются самым простым способом, могу поручиться уже сейчас — штука хорошая, с большими возможностями…
Можно применить три преобразования: замену и две перестановки столбцов и строк в таблице Кэли, в данном случае — латинском квадрате. Получится квазигруппа, являющаяся изотопом группы. Это описано в самом начале у Белоусова и конечно же учитывается. Таких изотопов избегают, вроде как выяснилось, что они тоже не годятся. Вообще, против квазигрупп какие-то современные методы алгебраического криптоанализа работают, хотя авторам сначала казалось, что это и не так. Если вас интересуют славяне и конкретно русскоязычные, занимающиеся этим вопросом, можете поискать ещё публикации Виктора Щербакова из Молдовы.
Таблицы Кэли, да, в данном случае без разницы, чем их заполнять.
Можно даже написать 2 ◦ 2 = 5
Научиться бы ещё хранить их в компактном виде без полной задающей таблицы, но так чтобы не терялись их ценные свойства.
Agathon (12/07/2012 16:38), ваш стиль повествования, и некие другие особенности речи, практически эквивалентны Масленникову Михаилу с его МК-85.
Но по сравнению с книгой появились нотки, которые указывают что у вас уже нету цели, нету пути...
Спасибо!
Славян я люблю, а русскоязычными авторами интересуюсь вынужденно, потому что по-английски почти не понимаю. С удовольствием заметил, что Щербаков из Молдавии — Белоусов работал в Кишиневе, наверное, это от него ниточка тянется, какая-то школа осталась.
Однако же другой любитель квазигрупп, тот автор, который сейчас крановщиком в Ашкелоне, он не из Молдавии, не из России, вообще не из славян, он родом из Средней Азии, там же и учился, только пишет по-русски. Да, и с израильской школой криптографии никак не связан, там школа другая, наша, старорежимно-советская…
Простите, не верю, аналитики врут, преувеличивают свои возможности. Такие они волшебники! А я в чудеса вообще не верю.
Авторам ничего не казалось, в теории квазигрупп есть утверждения -– по крайней мере частные, отдельные, — которые прекрасно доказываются, а есть такие, которые и доказывать не надо, они принимаются по очевидности. Тупой факт! Плетью обуха не перешибешь. Если сказано, что системы уравнений не решаются, значит, не решаются, невозможно вычитать одно уравнение из другого, невыполнимо вычитание – хоть ты на голову встань!
То же самое и в других случаях: если перестановка (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. Только кому это надо?
И что предлагаем? Получать S-box 256х256 умножениями в этих ваших группах?
Чудес не бывает, вы доказываете столькость тем что случайная таблица 256х256 это как бы много и непробиваемо. Вопрсос далеко спорный, но мы не о этом.
А ваша псевдо-случайная таблица получится уже далеко не случайной. В том то и беда. И все будет зависит от того как вы ее собираетесь умножать.
Тот же рц4 может использовать такие же таблицы >256. Ривест и предлагал рц4 для 2^n. Он же говорил что берите n какое хотите. Вот в вашем примере 16. И получите то же что и предложили тут. И что? От этого рц4 лучший шифр?)
Квази не квази, группы не группы, но вы не прыгнете выше головы. Да, теория красивая, да, для своего времни она была ничегошенькой, но паровоз ушел. ОНо хорошо выопнялось на самой большой электронике в мире, но времена другие...
Очень жаль что выйдя с союза, пройдя такую школу, имея такой багаж знаний, широту взгляда, человек не видит будущего... и топчет те квази группы в ступе.
Я не скажу что все у вас плохо, есть у вас идеи, которые будут испольтзовать в будущем, но вы им не придаете значения.
Простите великодушно, но я не знаю, кто такой Михаил Масленников, Ну, поищу в сети, но вообще литературу вопроса я знаю плохо, читаю мало, а уж тем более сам ничего не пишу.
А вот что касается целей и путей... Не знаю, как у Масленникова, а у меня цели есть, вот только путей к их осуществлению я не знаю. Так это у всех так! Многие знают, чего хотят, только не знают, как это получить..
Не знаю, прилично ли говорить о своих целях в подробностях, но раз уж спросили, признаюсь, что они тоже обыкновенные, простые и естественные, как у всех: у меня на руках оказалась чужая работа, в которой я сначала не мог понять просто ничего, потом начал что-то понимать — значит, первая цель разобраться в этой механике как следует, а вторая цель как-нибудь запустить ее в оборот, пристроить с пользой для правообладателей. По второму пункту у меня есть кое-какие обязанности, кое-какие полномочия, но вот способностей и умения нет.
Так что пока занимаюсь теорией, авось хотя бы с этим удастся справиться. С людьми вот знакомлюсь, вопросы задаю, полезное занятие — года два назад на DXDY был случай потрясающий, сначала все дружно говорили, что мол, то, о чем вы спрашиваете, этого никто в мире не знает, нет результатов, а потом нашелся молодой человек, совсем молодой, аспирант, который ЗНАЛ. Нет, он не само решение знал, но он знал, что результаты есть, и знал, где их найти. Очень образованный парень, великий эрудит! Ну, это вселяет надежды на будущее – авось и по другим вопросам кто-то подскажет, кто-то научит...
Направление разговора немного не улавливаю, кому мне доказывать? Михаилу? Он и так прекрасно должен понимать все слабые стороны такой схемы.
Скоролько их уже предлагали...
Ну чтож дерзайте.
Не вы первый, не вы последний.
По поводу требования отсутствия единицы. Первые хэши на квазигруппах были устроены просто как последовательное "умножение", допустим правое, повторяемая абстрактная операция "°" через квазигруппу.
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 говорить вообще некорректно — он не публиковался официально, как его проектировал Райвист мы не знаем.
Прошу прощенияя за местами неточные формулировки, безалаберное отношение к терминологии (за фразу "некоммутативный набор коммутативных операций" могут фигурально побить в приличном обществе, как правильно эта структура называется — не помню, но кто знает о чём речь — поймёт, несмотря на всю корявость) и отсутствие точных цифр в утверждениях "насколько" — это надо искать работы с расчётами.
Дифф. анализ блочных шифров на неизвестных аналитику квазигруппах этим занимается. Не могу сказать насколько успешно, но метод такой где-то был заявлен.
Unknown!
Спасибо за обстоятельный комментарий.
Свои пояснения к вопросам, которые там содержатся, помещу завтра. Сейчас просто физически не могу, простите.
В предварительном порядке только одно: блок-схема, последовательность процедур и функций. Ну, опять без начинки, чтобы не выдавать чужих секретов.
Реализация на 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 раз подряд – и все в порядке, теперь вероятность коллизий оценивается в точности и выражается таким числом, что его и на бумага написать неприлично. Ну, не то десять в минус шестисотой, не то десять в минус тысячной… Словом, когда рак на горе свистнет – вот это точное выражение вероятности коллизий.
Ну, а когда эта великая и ужасная таблица создана, делать с ней можно что угодно – и жизнь становится легкой и простой. Совсем легкой, если не считать некоторых маленьких теоретических трудностей, пробелов в доказательствах… А так пожалуйста, делай что хочешь, танцуй, пой, веселись!
Что ж касается пробелов в теории, то о них после. Не могу сейчас о грустном, не засну…
Кстати, вот как незначительное изменение алгоритма простого "умножения" на квазигруппах вместо хэша даёт блочный шифр (из семейства Edon):
Подключ раунда называется l — лидер
a' = l ° a
b' = a' ° b = ( l ° a ) ° b
c' = b' ° c = (( l ° a ) ° b) ° c
d' = c' ° d = ((( l ° a ) ° b) ° c) ° d
и т.д. Затем обратная перестановка a'b'c'd' → d'c'b'a'.
Вот и весь раунд! Два раунда — гарантированный лавинный эффект. Никакой мороки с анализом смешивания на линейных операциях. Размер блока — любой. Никаких операций, не нужен даже XOR. Достаточно одной табличной замены. Результат гарантированно является псевдослучайной перестановкой. Для расшифровки используется обратная квазигруппа. Квазигруппа открытая (есть варианты с закрытыми и с чередованиями). Но работает только если она аморфная. Иначе м.б. нестойкость к дифф. и пр. криптоанализу., различимость к перестановкам байтов (вот где должна быть некоммутативность) и к порядку операций (неассоциативность, это если порядок скобок меняется чуть более сложным образом, чем в примере, например за счёт чуть более сложной межраундовой перестановки, здесь и морфизмы-изотопизмы вылезают). Возможна бешеная скорость при реализации в специализированном железе, универсальные алгоритмы, даже крипткодинг (ваша шутка про то, что шифр будет сам ошибки исправлять — полезно в стеганографии, связи в шумовых каналах).
А что у вас? Обещали красивую теорию.
Но видится какая-то необоснованная сложность даже не через неясность, а через запутанность. И прибитость гвоздями к какой-то специфичной реализации.
В хэш-функции не может быть ключа-пароля. Там всё должно быть открыто противнику. Вот если она работает в режиме поточного шифра, то пожалуйста, добавляйте ключ в качестве входного значения. Но опять же, без привязки к таймеру, иначе это не потоковый шифр, разворачивающий гамму из ключа, а ГПСЧ с подкачкой энтропии с внешних источников, пусть даже таких плохих, как младшие разряды таймера.
Ну как-то совсем наивно-самонадеянно или непонятно, что хотели сказать. Если это хэш с размером выхода 256 бит, то вероятность коллизии при тупом переборе будет 2-128, даже если эта функция идеальна, как случайный оракул. До каких бы размеров внутреннее состояние не накручивали, внутри него самого коллизий, допустим, будет не найти, а на выходе они будут появляться, тупо по причине конечности всех возможных значений, это же не перестановка. См. второй рисунок[link7].
Опять же, в режиме хэша противник может не только подбирать любые значения на входе, там ведь нет и никакого ключа. Значит он видит все значения на любом раунде. Все ваши "секретные" развёрнутые таблицы, зависящие от текста замены, перестановки, перетасовки и прочие ухищрения с усложнениями бесполезны — они видны и доступны всем, всё внутреннее состояние видно на любом раунде, иначе нельзя посчитать хэш. Поэтому при проектировании универсального алгоритма Skein Шнайеру и Ко пришлось отказаться от такой идеи в шифре Threefish.
А раз разворачивание идёт только из исходного текста, без ключа, то противник будет искать коллизии не перебором, он будет подбирать "плохие" тексты, зная алгоритм и пытаясь получить "плохую" таблицу.
Сильно подозреваю, что у вас на руках в лучшем случае очень специфичный алгоритм, неуниверсальный даже по сравнению с обычными хэшами, заточенный под какое-то узкое применение, сейчас такие возможно просто не нужны. И даже если его переделывать под современные требования, то могут заинтересовать разве что какие-то отдельные решения.
Unknown!
Я не пропал, я усердно пишу ответ.
Извините, я тихоходный, соображаю медленно.
Да, и если я забыл сказать раньше — за беседу спасибо!
В меня не бросают помидорами, со мной обмениваются аргументами, это уже замечательно.
Ох, виноват, опять не сумею сказать все, что хочется и даже то, что уже как бы должен – теперь ведь приходится признать справедливыми такие упреки:
Ну, положим, не обещал выложить все, что знаю, этого не могу, не положено, но хотя бы без частных решений, на уровне общих принципов, которые уже стали предметом разговора…
Тогда первое: насчет единицы сдаюсь, в самом деле, если умножение в квазигруппах использовать вот так напрямую, когда выход хэш-функции есть произведение элементов блока {a, b, c, d, e…}, единица портит дело, на единицу умножай не умножай – толку никакого.
Я об этом не подумал как следует, потому что нужды не было. Во-первых, тот простейший способ порождения квазигрупп, о котором говорилось выше (без усложнений перестановкой строк и столбцов), дает квазигруппы без единицы. Никаких луп! Ассоциативности тоже нет, а коммутативность бывает – это как больше нравится, можно выбрать субстратом абелеву группу, а можно и неабелеву. Во-вторых, как-то не думал, что квазигруппы используются вот так просто, в лоб, – как раз это наивность.
Между тем у знающих людей есть предположения, что гораздо наивнее те методы, которые я расхваливаю, но показывать не хочу, обхожусь какими-то косвенными описаниями, обиняками, околичностями и метафорами (оно на четырех ногах, покрыто шерстью, говорит «мяу» и ловит мышей). Конечно, так и должно быть, когда обсуждается кот в мешке, я могу сколько угодно топать ногами и кричать, что кот очень хороший, но у других людей остается законный повод в этом сомневаться – это вообще закон жизни, закон торговли, а криптографии он касается особо, здесь никто никому но слово верить не обязан.
А что делать? Ну не могу я все выложить в подробностях! Самому хочется, а не могу.
Только в одно прошу поверить на слово: в том ашкелонском изделии, о котором я выдаю сведения по капле, есть разные решения, но наивных нет. Есть решения тихие и аккуратные, вполне корректные и доказательные, есть рискованные, дикие, наглые, как кавалерийская атака, но наивных нет. Я видел архивы, видел всю историю этой разработки, так вот, наивных решений не было уже в версиях 1999 года. Были раньше, но отсеялись.
По этому поводу для начала вот что: композиция (суперпозиция) алгебраических операций из разных групп ADD-XOR-ADD-XOR… действительно некоммутативна, к тому же дает сильную нелинейность выхода, только это не квазигруппа, у этой операции арность другая. Квазигруппа бинарна, у нас какие-то A и B, они могут быть чем угодно, буквами, числами, строками, пуговицами от пиджака, но их всего два, а между ними мы ставим всего один знак, обозначающий операцию, какой-то крестик или бюлетку, и эта бюлетка означает, что действие выполняется по таблице с известными свойствами: если в множестве объектов, которому принадлежат A и B, всего n элементов, таблица имеет размер n×n, при этом каждая ее строка и каждый столбец является перестановкой – всякий элемент множества содержится в ней ровно один раз. Других требований нет, но эти обязательны. Таблицу умножения конечной группы можно рассматривать как частный (и редкий) случай таблицы умножения квазигруппы, потому что она отвечает всем названным условиям, но не наоборот – квазигруппу нельзя представить как случай группы, у квазигруппы общность больше. Да, а многоместные операции это совсем другое дело. Эта замечательная штука ADD-XOR-ADD-XOR… многоместна, тут не то чтобы разных алгебр многовато, тут многовато сомножителей, операндов – она не бинарна, арность у нее другая, по числу сомножителей. И нет никакого способа представить операцию над четырьмя разными объектами операцией над двумя объектами.
Ну, либо я опять чего-то не понял, различающихся операндов всего два, а различных операций над ними производится много – в надежде, что результат будет сложнее (или лучше в каком-то другом смысле):
Только вот это и есть наивность. Всю эту композицию можно навертеть так, что будет выполнима, причем однозначно выполнима обратная операция, а можно навертеть так (с логическими операциями), что обратной операции не существует. Либо алгебра, либо не алгебра, либо уравнения решаются, либо не решаются… А если алгебра, то какая алгебра? Ну, выписываем всю таблицу умножения и смотрим, на что она похожа. Строки таблицы имеют вид A (×) B = C – то есть операция теперь как бы одна, значит, о кольцах и полях толковать нечего, значит, либо группа, либо квазигруппа, второе более вероятно. Но зачем такие сложности, если сделать квазигруппу намного проще? И много разных, горазо больше, чем композиций из других операций (это утверждение требует комментария, но о функционалах рассуждать не будем, не поместится).
Да, а многоместные операции (настоящие многоместные – сколько мест, столько и разных сомножителей) штука хорошая, и я их видел в архивных версиях этого ашкелонского изделия за 1997 и 1998 год. О, там как раз шло развитие всяких экзотических идей – от многоместных операций к многоместным предикатам, условным предикатам, потом венец всего, против восьми строк ассемблерного кода на полях написана дефиниция: многоместный условно-рекурсивный предикат. Так и слышно наглое хихиканье автора!
Конечно, это стеб, но накручена эта дикая смесь алгебры и логики была не по наивности и не из любви к стебу, там причина простая: не было в руках приличного генератора случайных чисел, чем-то готовым автор не хотел воспользоваться из упрямства (у нас все свое!), а сам не мог придумать какую-то простую конструкцию, получались только сложные. Ну, например, векторный арифметический генератор, в нем была сложная система вложенных счетчиков переменной длины, с переменным шагом, с изменением шага и длины по условиям, такая система раскачивающихся маятников – какую-то минимальную устойчивость ей придавали три переменные с фиксированным периодом изменения (у одной цикл 256, у другой 255, у третьей 253) — их сумма имела гарантированный период чуть больше 16 миллионов, распределение, близкое к равномерному, отвратительное по регулярности чередование четных и нечетных (как натуральный ряд не прячь, он лезет наружу!), а еще десятка два переменных нужны были только затем, чтобы замаскировать эту регулярную структуру, внести в нее хаос, удлинить период… Очень причудливая вещь! И эти переменные, изменявшиеся по смутным и таинственным законам, встречались во внутреннем цикле этой машинки – и там связывались такой же смутной и таинственной функцией, в которой были алгебраические операции, логические операции, операции, выполнявшиеся по условию, операции, выполнявшиеся безусловно… Ага, вот этот самый многоместный условно-рекурсивный предикат, хи-хи! По-русски так: функция от неизвестного числа неизвестных величин, над которыми произодится неизвестное число неизвестных операций. Мрак! Генератор неопределенности…
Все это было очень, очень сложно, но потом вся эта ахинея пропадает, уже к 2000 году все авгиевы конюшни вычищены. Потому что появился настоящий генератор. Настоящий, алгебраический – каждый следующий символ порождается ровно одной алгебраической операцией. Положим, операция не совсем простенькая, не такая, которую можно исполнить в один такт процессора, но это уже алгебра, свойства выходной последовательности известны, предсказуемы, поэтому не надо ничего мудрить и накручивать, пытаясь еще как-то от себя повлиять на распределение и длину периода. И вот тут можно полагать окончание наивного и романтического периода – когда большие сложности кончаются, вместо них появляются средства простые и понятные. Но тут же и начинаются большие секреты. Уж очень все просто! Не наивно, а именно просто.
Поэтому этот упрек несправедлив:
Пожалуй, не наивно, не самонадеянно, а именно непонятно, это из дальнейшего видно, что не сумел объяснить, о чем речь, там не хэш 256 бит, там другое.
Там задача простая – функция инициализации, иначе ключевое расписание.
У нас есть некая перестановка – вернее сказать, что нам нужна некая перестановка, потому что шифрующие функции работают с перестановками, генератору для работы нужен по меньше мере один S-блок, асинхронный шифр использует S-блоки, хэши используют S-блоки, S-блоки нужны всем, всегда, везде… Нам нужно, чтобы эта перестановка на алфавите 256 символов была похожа на случайную в некотором очень точном и строгом смысле – любой символ на любом месте с равной вероятностью. Еще нам нужно, чтобы эта перестановка полностью зависела от пароля, предложенного пользователем, — полностью, целиком, сильнейшим образом, чтобы при изменении хоть одного бита в пароле вся эта строка была другой, ни один из 256 символов не остался на месте (ну, это, пожалуй, фигура речи, вроде как не оставить камня на камне – на самом деле хотя бы одна неподвижная точка с вероятностью 1/e останется всегда, при самом честном перетасовывании колоды). Еще нам нужно, чтобы перестановка была случайной или похожей на случайную в некотором другом смысле, тоже точном и строгом – чтобы она никогда, никогда не повторялась, всякий раз была другой – даже при многократном использовании одного и того же пароля. Вот такой списочек условий и требований. А теперь спрашиваем: эти условия совместны или несовместны? Отвечаем не задумываясь, громко и отчетливо: нет, несовместны!
Почему несовместны – это можно объяснить, нужны рассуждения несложные, но строгие, чисто алгебраические по духу. Нам нужно сделать объект A зависимым от объекта B, эту необходимость можно выразить другими словами: сделать A функцией от B, произвести в A преобразование, зависимое от B, поставить паре объектов A и B в соответствие какой-то третий объект C – последняя формулировка содержательнее всех, в самом общем смысле создание зависимости можно обозначить как умножение, мы умножили A на B и получили C. Принцип настолько общий, что его нельзя заменить чем-то другим, это первая страница учебника алгебры… И на той же странице ненавязчиво указаны условия выполнимости этой операции. Первейшее – замкнутость, A и B должны принадлежать одному множеству или одному типу объектов, и их произведение тоже не должно выходить за пределы того же множества. Умножили число на число и получили число, умножили подстановку на подстановку и получили подстановку… Тогда это алгебра, в ней может обнаружиться единственность произведения и, соответственно, разрешимость уравнений. А если левый и правый множитель принадлежат множествам с разным количеством элементов, уже никак не получится алгебра, где у каждого уравнения только одно решение. Левый множитель у нас подстановка (перестановка) 256 символов, одна из всех 256! возможных, правый множитель строка произвольной длины, от 1 до 512 символов, какое-то размещение (с повторениями), а произведение опять перестановка из того же набора 256! различных. Ну? Кажется, все ясно, строк длиной 512 символов больше, чем строк длиной 256 символов (уже неважно, перестановок или размещений), а строк длиной 2 символа гораздо меньше. Можно ли задать умножение так, чтобы деление было выполнимо всегда, чтобы и левый и правый множители можно было заменить неизвестным иксом и уравнения решались? Дудки! Только в одну сторону. Можно задать умножение так, что потом будет выполнимо деление произведения на правый множитель, это вопрос технический, зависит от того, какими процедурами и операциями нижнего уровня (над буквами) составлено это умножение строк, но обеспечить делимость на левый множитель невозможно никак, никакими ухищрениями – результат всегда будет неопределенным, всегда будет множество подходящих решений. Поганая алгебра с коллизиями – и она всегда будет поганой, ее качества можно регулировать только в одном отношении: подбирать процедуру умножения так, чтобы коллизии были насколько возможно редкими. Наихудший результат – произведение принимает всего 256 различных значений, вероятность коллизии 1/256 (но при этом разрешимость уравнений влево сохраняется, деление выполнимо), наилучший результат – 256! различных произведений, возможно любое из них, причем с равной вероятностью.
Вот где задача – добиться хотя бы этого результата!
Научиться умножать перестановку на размещение, строку любой длины, при этом не слишком увеличить количество элементарных операций по сравнению, например, с какой-то более «естественной» алгеброй, обыкновенным умножением подстановок, симметрической группой из учебника. Ну, так экономно не получается, получается что-то вроде половины квадрата этого количества (при умножении на строку той же длины, 256 символов), но главное – вопрос о вероятности коллизий. Здесь в теории не все гладко, причем нет надежды на скорые успехи. Зато эмпирические решения есть! Надежнейшие. Допустим, мы не можем доказать, что умножение заданной перестановки на строку «Пролетарии всех стран, соединяйтесь!» и на строку «В лесу родилась елочка, в лесу она росла» даст совпадение результата с вероятностью немногим более 1/256!. Зато мы можем доказать с точностью, что вероятность совпадения меньше 1/256 – доказательство будет строгим, только его ценность кажется смехотворна. Ну, это только на первый взгляд, потому что мы можем повторять процедуру умножения столько раз, сколько захочется, причем таблицы умножения всякий раз другие. Опять используются те же перестановки, сиречь S-блоки, а их у нас мно-о-ого! Они порождаются быстро и в неограниченном количестве. Дальше понятно, правило умножения вероятностей. Однако результат надо поправить: возведение числа 1/256 в степень 256 дает десять в минус шестисотой, а реально вероятность коллизии не может стать меньше 1/256! – всех различных произведений только 256!, это только десять в пятисотой. Но уж тут пустяки, сотней нулей больше, сотней нулей меньше…
Да, и последнее замечание по поводу поганых алгебр: с самом общем смысле любая криптографическая система в целом представляет собой алгебру именно с этими свойствами – полуразрешимую: шифрование есть умножение объекта на объект, мы умножаем «Войну и мир» (длинную строку) на пароль (короткую строку) и получаем произведение, шифртекст, это опять длинная строка, не короче левого множителя. В буквенной записи все то же самое A × B = C — только теперь этот крестик, знак действия обозначает AES или RC4, или IDEA. Дальше те же свойства: деление на правый множитель выполнимо, а вот деление на левый весьма проблематично само по себе, при самых общих условиях, и его еще всячески стараются затруднить особыми приемами.
На этом с погаными алгебрами покончено, это умножение строк разной длины самое смутное место в ашкелонской разработке (хотя технически все выглядит просто, даже забавно), а вот что касается красивых алгебр и вообще обещанной красивой теории… Ну очень хочется взять и вот так все выложить! Только нельзя. А как бы это противоречие обойти? Ну, опять всякие косвенные описания. Напрямик успел брякнуть только один раз, уже что-то такое было про многомерные векторные пространства. Так что теперь, когда всплывают какие-то несуразные цифры – 48 S-блоков, да еще обратные к ним, да еще чистые копии, да еще копии, параметризованные таймером, — я прошу не смеяться сразу, а просто сделать усилие, пытаться вообразить, что этот инструмент у вас в руках. И что вы с ним сделаете? Пожмете плечами и выкинете за ненадобностью? Сомневаюсь. Любой криптограф, любой алгебраист хотя бы разочек прикинет в уме самую ближайшую, самую очевидную возможность использования этой махины – переход к векторным исчислениям. Да, да, вот эти строки символов { e, f, g, h, i, k …}, которые мы называем векторами условно, для красоты слога, становятся векторами на самом деле, в точном смысле, то есть наборами координат, у нас это теперь адреса, указатели, и используются не они сами, а адресуемые элементы, после разыменования: { A[0][e], A[1][f], A[2][g], A[3][h], A[4][i], A[5][k]…} Ох, не хочу все выкладывать, просто намекаю, что это не просто замена переменной, тут последствия обширнейшие… Как раз тут возможна красивая теория – если кто умеет еее построить. Только вчера обсуждался противоположный случай: если мы побуквенно складываем «Евгения Онегина» с «Мертвыми душами», то нет разницы, какая алгебра при этом используется, группа или квазигруппа, статистика от этого не меняется, сумму можно моментально разложить на слагаемые… А вот в случае перехода даже к такому скромненькому векторному пространству из 48 строк по 256 символов меняется многое, все меняется, последствия обширные. Скажем, есть такое странное следствие: один из хэшей в этой системе не блочный. Вот так – все хэши на свете блочные, только размерами блоков отличаются, а этот не блочный, он поточный, он работает с очередным байтом, ему этого достаточно. Но это не какая-нибудь хилая сумма Флетчера, это довольно мощный хэш разрядностью 32 байта, а можно и больше… Эх, жаль, не могу все показать.
Да, а вот нужны и кому-то эти методы – какие-то из них в отдельности или все вместе, — это вопрос. Мне не кажется, что эти методы очень специфичны и заточены под какой-то особый случай, напротив, при первом ознакомлении меня поразило, как часто в комментариях встречаются слова «любой» и «всякий» — это признак универсальности. Пароль любой длины, гамма любой длины, хэш любой длины, шифры любой скорости, асинхронный еще и читается с любого места… Любой, всякий, какой угодно, на любой вкус – уж хоть что-нибудь из этого набора кому-то пригодится.
Скоро сказка сказывается, да не скоро дело делается. Сказал Ивану Царевичу Агафон Моисеевич. И сказал, что знает как явить чудо-чудное, диво-дивное. Только злая колдунья, обернувшись жабой душащей, наложила чары злодейские и не дала поделиться тайной древнею с добрым молодцем.
Можете не торопиться, рассказывать свою сказку в таком темпе и объёме как вам удобно.
Всё что про алгебры — это справедливо, это всё описано и для криптографии общий подход такой есть: P x K = C — любое шифрование как абстрактная алгебраическая операция.
Смутно что-то вырисовывается, очертания кота в мешке проступают. Или его муляжа.
А вот насчёт исследований по использованию векторных пространств и решёток мало в курсе. Есть и такое направление, развивается себе в сторонке, но в мэйнстрим не попадает.
Много есть экзотических направлений. Многие что-то обещают. Практический выход, как и от любых исследований, маловероятен. Никто не знает точно, что именно окажется востребованным.
Даже если ваш метод стоящий, то рассчитывать можно в лучшем случае на публикации. На патентователей алгоритмов даже их коллеги смотрят как на собак на сене. Те оправдываются, что они не сами, а их работодатель так заставляет и иногда делают исключения для некоммерческого использования. А патентованный алгоритм всё равно и анализируют неохотно — тоже могут сказать, давайте за деньги и по контракту мы вам проанализируем и сделаем публикации, а то чего работать ради ваших прибылей. А уж и использовать патентованные алгоритмы подавно мало кто хочет.
Асимметрику ещё можно патентануть. Сначала Райвист и Ко (но при этом были и бесплатные аналоги на дискретных логарифмах), затем эллиптические кривые (а проф. Бернштейн придумал альтернативный метод генерации кривых специально, чтобы обойти патент и вернуть метод свободному человечеству, АНБ скупило все патенты и попыталось отдать их в свободный доступ), сейчас вот асимметрика на квазигруппах. Ну если вас привлекают спекуляции, можете попробовать выманить у кого-то деньги.
Выманить — это звучит грубо. А главное, это несправедливо по сути. Речь не о том, чтобы у ребенка конфетку хитростью выманить. И даже не о том, чтобы дешево купить и дорого продать.
Речь о работе.
Автор потратил на эту работу восемь лет, потом бросил ее и даже вспоминать не хочет. Через два года она перешла в мои руки, и я уже пять лет с ней разбираюсь, появилась кой-какая теория.
Ладно, я старенький, пенсионер, но что-то мне помнится, что раньше, когда я работал, мне платили за это деньги. Небольшие, но платили. Все остальные люди тоже не видели ничего дурного в том, чтобы брать за свою работу деньги. И только сейчас вдруг узнал, что есть особого рода занятия — если ты не детишек математике учил и не чужие рукописи в издательстве вычитывал, а сам сочинил шифр, написал его реализацию или снабдил теорией, за это просить денег стыдно, это спекуляция...
Ой, пардон, обещал ведь не оффтопить на темы политики, морали и права,
оффтопить только по математике... Просто не сдержался, ну никак не понимаю, почему я что-то кому-то должен дарить, а если не хочу, так меня осудят как собаку на сене. И еще бы свое дарить, а то чужое...
Нет, лучше в шахматный кружок запишусь! И еще в нашем городе есть литобъединение — тоже для пенсионеров, старички и старушки пописывают стихи и прозу, а к праздникам мэрия даже выделяет небольшую суммы на издание этой белиберды...
Так и другим авторам платят. Гранты и зарплату. За то, чтобы они открыто публиковали свои идеи. Ну если они на какое закрытое ведомство работают, то за то, чтобы открыто не публиковали. А затем платят пенсию. Как и большинству обычных наёмных сотрудников.
Может, все эти ашкелонские секреты советского происхождения уже давно имеют аналог в открытых источниках. Ещё сложнее найти открытый аналог по неоправдавшимся и свёрнутым направлениям, которые авторы забрасывают. Бывает и такой аналог находится.
На гранты и научные ставки люди живут. Криптографы ничем не отличаются от математиков или там, астрономов, толку, что наука эта прикладная. Ну впёрлась, простите, вам фикс-идея с патентом :-) Смешно право-слово. Так-то кто ж вам запретит — патентуйте, только деньги потратите. Мало у кого во всём мире есть прибыль от патентов. И то, люди себе сначала создали имя на публикациях. А вам ещё и переуступил идею кто-то, пусть даже она ему и не нужна. Т.е. вы как автор публикаций будете неинтересны и невостребованы, если только не вытащите того крановщика из Ашкелона, но это уже ваше дело, конечно, чем вы заинтересуете. Вот только кого? Где рынок криптоалгоритмов? Его нет. Это хотя и прикладное, но всё бесплатное в большинстве своём, как таблица умножения или способ получения бозонов в ускорителе.
Допустим, оффтоп теперь я первый ввернул. Но уже не столько для морализаторства и тем более не для политики, просто считаю, что с таким подходом шансы были бы крайне малы, даже у молодых и преуспевающих коренных жителей "золотого миллиарда". Скорее их вынудят патент перекупить корпорации, которые заберут всю прибыль или будут использовать в патентных войнах. А автору — гроши, ну в лучшем случае, хороший оклад по контракту, а так — все деньги всё равно уплывут дельцам если будут ещё.
В шахматы играть и стихи писать в пенсионном возрасте конечно хорошо, но покоя вам не даёт мечта о чём то большем, пусть и скромном. Ну хоть и это само по себе хорошо.
А математические байки с удовольствием почитаю. Думаю, не я один. В угадайки могу поиграть ещё по мере знаний и интереса к теме. Но то, что многие активные посетители сайта — противники коммерческого подхода с закрытием идей вас предупредили сразу. Вас в общем-то поняли и приняли. Думаю и вы нас поймёте.
Да, встретили меня хорошо. Я это оценил.
Можно ведь было ждать худшего. Человек, который утверждает, что у него на руках действующая модель
вечного двигате, пардон, нового шифра или хэша, он безумец по определению. Того и гляди набросится и покусает...Ну, обошлось и прекрасно, не знаю, что там выйдет с этим ашкелонским изделием, но новым знакомствам я рад, получил от переписки массу удовольствия, узнал много нового.
Агафон, друг, вот ты где!
Тута я, тута...
Ну, безумец или не безумец. Всякие тут были :-)
Просто так, для справки. Конкурс AES закончился ещё в 2000 году. Уже тогда условием участия был отказ победителя от патентования, любых коммерческих притязаний и полная передача шифра в общественное достояние. Многие участники сразу отказались от патентов, не дожидаясь того, победят или нет. Некоторые вышли в финал патентованными, а раз не победили, то и не стали отзывать патент, но теперь они никому не нужны.
В конкурсе SHA-3 условие ещё жёстче: все участники обязаны отказаться от патентования и от любых коммерческих прав на хэш к моменту подачи заявки на конкурс, неважно, победит их алгоритм или нет.
Мне неизвестно ни одного случая коммерчески успешного патентования симметричного алгоритма после 2000 года. Crypto AG пытались патентовать производные от шифра IDEA, дескать они сами будут поддерживать исследования вокруг своих алгоритмов. Ага — никто с валом публикаций против непатентованного AES не сравнится, а их шифры уже забылись и пылятся где-то. Кто их купил?
SONY пыталась свои шифры изобретать и патентовать, но у них копирайтный маразм, они профукали из-за этого массу изобретений, не только шифры, но и куча их фирменных стандартов никому не нужна. Шифры они предполагали использовать только в DRM-индустрии и т.д.
Даже если вы полностью раскроете устройство шифра, масса шансов, что его завернут: публикация плохо оформлена, ссылки на литературу старые, про современные тенденции автор не в курсе, на известных конференциях автор не засветился (а на поездки нужны время, деньги, здоровье), не заработал себе репутацию на взломе чужих шифров и т.д. Репутация же строится не на изобретении шифра, это может быть уже скорее пик карьеры.
Нужна годами накопленная в разных изданиях масса всяких опубликованных исследований по теории функций таких, функций сяких, видов криптоанализа всякого, по построению протоколов из готовых шифров и прочих алгоритмов. Тогда может скажут, "да знаем такого исследователя. Он делал интересный доклад по бент-функциям, а в позапрошлом году по бранч-критериям, а в этом году публиковался по MDS-матрицам и открыл способ оптимизации построения каких-то векторных отображений. Что-вы говорите, он даже свой шифр опубликовал, да интересно.". Как-то так
А кота в мешке, да не от автора, да с претензией сразу на патент не возьмут изучать даже забесплатно, хоть там всё трижды гениально. Нужна именно куча сил и времени, чтобы раскручивать это самому уже после полного раскрытия. И не ради прибыли, по крайней мере от патента. Может поэтому у малоизвестного пенсионера или крановщика без наработанной публично репутации в этом деле, как это им ни печально, особых шансов нет.
Можно подумать, что кому-то, кроме автора — тролля и графомана, это не было очевидно с самого начала. Развели тут только словоблудие на 6 страниц.
Но unknown, конечно, спасибо, его всегда интересно читать.
Unknown!
Сведения, которые вы сообщаете, полезные, но грустные. Очень грустные.
Ну, так и хочется заняться запрещенным делом — начать жаловаться на жизнь, несправедливость законов, ущербность общественной морали и несовершенство мироздания в целом. Очень тянет в эту сторону, но ведь пустое это дело... Толку никакого, разве что для души польза: "утоли моя печали..."
Хотя, надо сказать, что некоторые обстоятельства такого рода были известны и раньше. Автор, который сейчас крановщиком в Ашкелоне (или Ашдоде, черт его возьми!), в прошлой жизни имел другую специальность, имел по этой специальности приличную репутацию, вообще считался человеком солидным. Поэтому, когда вдруг заинтересовался криптографией, над ним не смеялись, его познакомили с такими же серьезными, солидными людьми средних лет, у которых тоже была приличная репутация по своей специальности — как раз по криптографии. Ну, вообще по те временам редкая специальность, но закон жизни состоит в том, что через трех знакомых можно выйти на английскую королеву, а уж на парочку-троечку полковников из восьмерки и подавно. Приятные люди, очень недурные математики, проявили внимание, не поленились, смотрели... Но интересно не только экспертное заключение по существу вопроса, еще интереснее последовавшее заключение по поводу житейских возможностей и перспектив этого изобретения. Один из экспертов, вежливо улыбаясь, попросил обратить внимание, кто он теперь и чем занимается. Он даже перестал читать лекции на каком-то мутном факультете защиты информации (не помню, в каком это вузе), он купил небольшой цветочный магазин... Ага, голубчик, можешь заметить, что меня эта специальность больше не кормит, а ты надеешься, что тебя она прокормит?
Это было давно, в середине девяностых, после этого автор из упрямства продолжал свои занятия, довел свою систему до какой-то логической завершенности — и бросил. Уехал в другую страну и пошел в крановщики. Даже это далось с трудом, экзамен надо сдавать, язык надо знать, а для каких-то других занятий надо знать язык получше...
Выходит, владелец цветочного магазина был прав, извлечь из своей выдумки какую-то пользу автору не удалось. Но это совсем не расположило его к мысли подарить ее человечеству. Как бы не так! Совершенно наоборот! Подарки можно делать друзьям, знакомым, родственникам, а человечество в целом — это слишком абстрактно, имперсонально. Сам автор заниматься этой выдумкой больше не хочет, его сын тоже не хочет, зато есть Агафон Моисеевич, которому все равно больше делать нечего, в парке с другими старыми дураками в шахматы играет, вот пусть займется, если ему интересно, могу даже в соавторы взять или просто доверенность на представительство выписать... Да, оказалось интересно. Но практические перспективы, похоже, те же самые — уж лучше было сразу купить цветочный магазин, это практичнее!
Так что вообще непонятно, кто еще занимается криптографией, кому это надо — купили бы себе каждый по цветочному магазину, и дело с концом...
Я, конечно, очень извиняюсь, но образование то в СССР – бесплатное было!
Я вот вообще думаю что чем меньше разница между потенциальной (замыслом) и движущей (мотивами) энергиями, тем вероятнее успех. Это типа такое применение принципа наименьшего действия ;) Залог успеха – искренность и непосредственность!
То есть что-то стоящее можно открыть если основной мотив изучения – узнать, а не получить за эти знания какие-то иные блага, и наука много не потеряет если те, кто пошёл туда не за истиной, пойдут торговать цветочками.
[offtop]
На сайте http://kroogi.com цену за скачиваемую музыку определяет сам пользователь. Так вот, ненулевую сумму платят 28 человеке из 100 – в среднем по $3. Видео[link16]
[/offtop]
[offtop]
А причём здесь музыка? Или даже популярное ПО?
Это модели добровольных пожертвований, наподобие Crowdfunding/Donationware.
При самой по себе спорности эффективности такой модели даже для творчества/ПО/небольших проектов, для заявленной цели она совсем не подходит, т.к. завязана на лёгкость оценки результата любым желающим и массовость. Пусть даже нишевую массовость среди своих — "непопсовость".
[/offtop]
[offtop]
Да почему же не подходит? Ведь не нужно милиионов разных шифров, а авторы тех, что действительно нужны, могли бы весьма неплохо жить и на добровольные пожертвования.
[/offtop]
[здесь уже всё off-top]
Пусть лучше исследования идут по типу научных разработок. Вот что из публикаций за последний год[link17] вы считаете важным? То, что с громкими названиями? А может что-то на первый взгляд отвлечённо-теоретическое несёт в перспективе больше пользы. А вы, как конечный потребитель (которому нужен готовый шифр), но не специалист, этого не оцените.
Мало того, что погоня за грантами по распиаренным темам тоже развращает, так нет, предлагается вместо спокойной работы без лишних мыслей о деньгах, гоняться именно за тем, что будет популярно у широкой аудитории, которая не является специалистами в вопросе.
Думаю, что NIST (и любые серьёзные организации с репутацией) принципиально не выделяет никаких денег победителям конкурсов, чтобы он не носил коммерческий характер. Так же как и взлом алгоритмов за деньги практикуется крайне редко.
[/здесь уже всё off-top]
Конечные потребители в соответствии со своими усмотрениями одаривают авторов конечных продуктов, а те в свою очередь точно также одаривают тех, чьи продукты они использовали при производстве этих продуктов, и т.д.
Во всяком случае, удивительный (для меня) факт состоит в том, что ненулевых дарителей – примерно треть. А это значит, что такая система может быть жизнеспособна. (Вот кстати у американских индейцев была "экономика даров" – не такая ли?)
Гоняться "за популярностью" невыгодно, посколку при этом вы создадите не то, что вызовет у потребителя желание вас поддержать. Разумеется, речь идёт о продуктах творчества.
Ну и конечно, совсем хорошо если всем будет гарантированно пособие по безработице на которое можно прожить...
Это даже можно автоматизировать – в благодарностях (аcknowledgments), а также в списке использованных материалов автор распределяет доли.
Я думаю, основное препятствие для микроплатежей – лень регистрироваться в системе. А вот если для доступа нужно будет заплатить 0р. 0к., то уже в дальнейшем заплатить несколько рублей будет не проблема. (А если треть населения земли вам заплатит по рублю, вы станете милиардером ;)
И кстати, что мешает сделать такое НА ЭТОМ САЙТЕ! То есть чтобы любой автор мог сделать доступ к некоторым своим материалам платным, но сумма платежа пусть определяется читателем. ;)
На этом сайте платежи – вряд-ли: тут с творчеством слабовато и анонимность важнее.