id: Гость   вход   регистрация
текущее время 13:58 29/03/2024
Автор темы: Гость, тема открыта 19/06/2012 01:20 Печать
Категории: криптография, хэширование
http://www.pgpru.com/Форум/Криптография/ПростойВопросОСкоростиРаботыSHA1ИMD5ВКонтекстеАлгоритмаНаКвазигруппах
создать
просмотр
ссылки

Простой вопрос о скорости работы SHA1 и MD5


Прошу простить мое невежество, вопрос, наверное, не только простой, но даже наивный, но не могу ниггже найти ответа в каких-то ясных, доступных для сравнения цифрах, например так: хэширование методом SHA1 в оптимальной реализации расходует 100 (или сколько там) машинных команд на один байт текста. Либо так: хэширование этим методом производится со скоростью 1 Мб (или сколько там) в секунду на машине AMD Sempron с тактовой частотой 2,3 ГГц. Просто и хорошо!


Но как раз таких понятных цифр я найти не могу, везде только описание алгоритма, а сам получить эти цифры не умею, разве что написать своими руками ассемблерную реализацию этих хэшей на ассемблере, сосчитать операторы… Если кто-то избавит меня от этой нудной работы, подскажет цифру, буду признателен.



 
На страницу: 1, 2, 3, 4, 5, 6, 7 След.
Комментарии
— Гость (09/07/2012 23:33)   <#>
это значит, что хэш-функция поганая
Да, т.к. есть отличие от случайного вывода. Ни на один SHA-конкурс такую функцию не взяли бы.

вслед посыпались какие-то двачеватели, куны и лоровцы.
Всё есть в википедии отбросов общества: и "двач", и суффикс "кун", и "лор" (lor). Не обращайте внимания.
— Гость (10/07/2012 00:11)   <#>
Цифры, которые я видел на том сайте, просто жуткие, волосы дыбом встают, речь идет о переборе миллионов паролей в секунду — именно так, не операций в секунду, а паролей в секунду, и для каждого вычисляется хэш

все? все криптопрограммы в топку?

что ж тут непонятного?
— Гость (10/07/2012 00:16)   <#>
ужасная картина!
боюсь к ним соваться

действуют полным перебором, грубой силой, иногда в ход идут заранее составленные таблицы (радужные таблицы), различия алгоритмов хэширования этих парней не останавливает

Жуть!

Забыл свой пароль.....приходи, тебе его подберут
— Agathon (10/07/2012 01:28)   <#>
Да, т.к. есть отличие от случайного вывода. Ни на один SHA-конкурс такую функцию не взяли бы.
Спасибо, наверное, Вы правы, никакой NIST такую функцию не примет. Но вот так хочется хоть кое-что объяснить, сказать словечко в защиту автора, только ведь это будет медвежья услуга, под видом защиты я выболтаю чужие секреты...

Ладно, компромисс, опять обойдемся косвенными описаниями: черный ящик, результаты знаем, а операции за кулисами.

Меня эта программа (старинный COM-файл размером 8 кб) радует тем, что почти все прописанные в ней операции и процедуры имеют теорию. Если хорошенько вдуматься, это свойство неожиданное, потому что распространенные хэши (и близкородственные им блочные шифры) имеют теории ровно столько, сколько взбивание омлета вилкой в большой эмалированной миске: совершенно ясно, что из яиц, взбитых таким образом, цыпленок уже не выведется, но теперь попробуйте перевести эту ясность на язык строгих доказательств. Не выйдет, нечего и пробовать! Хотя это очень ясно и понятно, что если как следует вертеть вилкой в миске, яйца будут взбиты хорошо, белок и желток перемешаются до неразделимости и неразличимости... А тут, понимаете ли, такой алгоритм, где у каждого действия есть теория, то есть почти каждая операция образует алгебру.

О, алгебра — это уже нечто! Тут это вам не там… Это уже теория, можно что-то разбирать и доказывать. Хотя вообще там попадаются странноватые алгебры, иной раз не знаешь, как назвать, хотя опять-таки глазами все видишь, все ясно. Скажем, такая полуразрешимая алгебра, имеет разрешимость только в одну сторону: произведение можно делить на правый множитель, а на левый нельзя, в эту сторону деление не определено, так что правый множитель нельзя заменить неизвестным иксом, уравнение решаться не будет. Вот как эта чертовщина должна называться? Друзья-алгебраисты делают большие глаза...

Так вот, насчет поганого хэша — может быть, он не совсем и поганый, там есть тонкость, не все 32 байта хэша изменяются по одному закону, есть разница между левой и правой стороной, четной и нечетной, это как бы разные разряды, младший и старший, результата операции в некоей алгебре — какого-то «сложения» или «умножения», заданного особым образом, применительно к нуждам алгоритма. Порча хотя бы одного бита текста приводит к тому, что ровно половина строки хэша, 16 байт из 32, изменится обязательно, потому что это хорошая алгебра, где выполняется условие единственности произведения.

Не так уж это мало — 16 байт из 32, не так это плохо, вообще этим можно и ограничиться, а от слабой половины строки, где каждый символ меняется не в точности, а лишь с вероятностью 5/16, можно и вообще отказаться. Или сложить этут строку вчетверо, перегнуть по длине два раза, сложить с собой разок-другой — разок просто так, разок после циклического сдвига, перемешать, взбить вилкой... Но это и будет шарлатанство, нечистая работа, а там везде работа чистая, честная алгебра с честными результатами. Это значит, что порча одного байта текста изменит ровно 16 байт хэша в точности, а порча двух байт текста меняет те же 16 байт хэша уже по вероятности — каждый может совпасть с правильным значением с вероятностью ровно 1/256 — это вероятность случайного совпадения, и уже ее ничем не избежать, закон природы! Коллизии есть обязательно, в силу той причины, что строк длиной 32 байта гораздо меньше, чем строк длиной в «Войну и мир».
То есть у нас есть как бы сильная часть хэша, она хорошо видит маленькие изменения в тексте, но вообще, если в тексте испорчено более одного байта, работает по вероятности, а есть еще слабая часть хэша, она тоже срабатывает только по вероятности, но маленькие изменения текста она видит с меньшей вероятностью, зато для больших различий в текстах вероятность коллизий в сильной и слабой половине хэша уравниваются. Это значит, вообще говоря, что слабость слабого разряда не облегчает поиск коллизий перебором — в любом случае считать длину строки надо не 16 байт, а полных 32. А это это цифра такая, что никакие парадоксы дней рождения не помогут!

Что же касается вычислительных методов поиска коллизий, которые предположительно помогли бы избежать полного перебора, то вот тут, простите, дудки! Обнаруживается польза теории — каждая операция была алгеброй, поэтому свойства операций можно разбирать, можно доказывать, что сократить расходы и избежать полного перебора никак нельзя — вот по таким и таким причинам, потому что мы здесь умножали вон то на вот это, а такие уравнения, пардон, не решаются... Ну, для этого нужна некоторая сноровка, но есть люди, которые теорию любят и находить строгие доказательства умеют.

Беда, однако, в том, что все это вопросы опять же отвлеченные, практического смысла не имеющие, поскольку переделывать чужое изделие нельзя, даже приписывать к нему свою теорию нельзя, это незаконно, алгоритм не опубликован, значит, и теорию публиковать не положено, а отпадут эти тонкие вопросы авторского права лет этак через пятьдесят — тогда пожалуйста, уже и автора в точности нет в живых, и у наследников, если таковые имелись, права истекли. Но кому это нужно через пятьдесят лет? Если призадуматься, то и сейчас никому не нужно…

С уважением, Агафон
— Agathon (10/07/2012 02:16)   <#>
все? все криптопрограммы в топку?

что ж тут непонятного?

ужасная картина!

Виноват, забыл сказать главное — длина пароля, длина, длина!

Эти лихие парни умеют за день-другой отыскивать пароли длиной восемь символов, девять символов, причем иной раз управляются даже с кириллицей. Но против законов природы ничего не могут даже самые лихие люди, пароль из 12 символов невозможно найти при скорости перебора 10 миллиардов паролей в секунду (говорят, реальная цифра), а 16 букв нельзя найти не только видеокартой, но даже воображаемым квантовым компьютером размером с нашу галактику. Ну, разве что пароль паршивенький, который можно найти по словарю...

Но ведь самый паршивенький не тот, который можно найти по словарю в полсекунды, самый паршивенький тот, которого ни в каком словаре найти нельзя! Потому что его и запомнить нельзя. Я его обязательно напишу на бумажке, а бумажку просто случайно на минуту оставлю на столе, когда меня попросят к телефону в соседнюю комнату... Готово!

Значит, настоящий случайный пароль никуда не годится, он хуже осмысленного, из слов естественного языка. Но и осмысленный никуда не годится, его можно держать в голове, но он словарный, его мера неопределенности реально составляет не 96 бит, не 128, а только 10 или 12...

Как же тогда жить? Неужто хороших паролей не бывает вообще? Нет, можно полагать, бывают. Врут авторы книг, что нельзя использовать цитаты из Шекспира и библии. Еще как можно! Все дело в длине цитаты. Ну, немножко в орфографии и пунктуации. Хороший пароль такой: "В сие время заяц выскочил из лесу и побежал полем". Это Пушкин, господа, Пушкин! Строчка есть в собраний сочинений, но строки такой длины пока никто находить не умеет — ни перебором по буквам, ни перебором слов по словарю, ни перебором подстрок во всех строках всех классических сочинений...
Или кто-то уже умеет? Если есть такие умельцы, пусть похвастают, это интересно.
— Гость (10/07/2012 10:16)   <#>
Хороший пароль такой: "В сие время заяц выскочил из лесу и побежал полем"
А ещё неплох такой: "Всиврзавыизлеипопо"
— unknown (10/07/2012 12:11, исправлен 10/07/2012 12:48)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

В тестах openssl прогоняются блоки размером 16, 64, 256, 1024, 8192 байта в течении трёх секунд, а затем выводится результат: сколько обрабатывается байтов за секунду при таких размерах блока.


Это важно, так как многие алгоритмы медленнее работают с более короткими блоками из-за медленных процедур развёртывания.


Свой вклад вносят и особенности железа. При разработке криптоалгоритмов учитывают скорость не только на обычных компьютерах, но и универсальность по отношению к другим типам железа.


но работе с текстом предшествует функция инициализации, заполняются необходимые для работы таблицы, и вот там, похоже, нарочно накручены лишние расходы — таблицы большие, а процедура их вычисления включает явно ненужные итерации, это редуктор, замедлитель, идет просто пересыпание из пустого в порожнее, некая переменная установлена в 256 — и пошел холостой ход, нехитрая процедура исполняется 256 раз вместо одного раза, в итоге все эти предварительные вычисления требуют, по моим подсчетам, от 15 до 300 миллионов операций, в зависимости от параметра.

Если бы функция претендовала на какой-нибудь стандарт, то такой режим должен быть опциональным и полностью отключаемым, так как во многих случаях замедление не нужно и стойкость не повышает, а нужна как можно большая скорость при массовой обработке данных: контроль целостности через коды аутентификации сообщений с общим секретным ключом или электронные подписи.


все прописанные в ней операции и процедуры имеют теорию. Если хорошенько вдуматься, это свойство неожиданное

На конкурсе SHA-3 были полностью алгебраизированные построения — хэши на основе алгебры квазигрупп, соответственно работы очень хорошо обоснованные математически и изначально выгодно смотревшиеся на фоне некоторых других. Там и трудно поддающиеся криптоаналитическим атакам некоммутативные преобразования и гарантированное изменение блоков с определённой вероятностью.


Даже пара кандидатов квазигрупп-хэшей, разработанных солидными коллективами математиков, но увы не самых выдающихся криптографов. Один сильно прокололся в плане стойкости, на второй были найдены слабые атаки и по некоторому мнению из-за перестраховок его оставили только во втором раунде. При том, что до этого у них было много прототипов таких алгебраических хэшей, которые ломались совсем тривиально.


Это только навскидку. Масса исследователей претендует на то, что якобы доказательство стойкости их алгоритма обосновано математически. Само по себе это хорошее и желательное свойство, но оно недостаточно. И часто является иллюзией — многослойную инженерную конструкцию (например Keccak: нелинейный слой с просчитанной алгебраической сложностью, линейный с посчитанными уровнями диффузии) пытаются заменить алгеброй преобразований, полагая, что это более естественным способом обеспечит требуемые свойства. Это правильный подход в перспективе, но само по себе такое заявление ничего не даёт. Примеров взломанных алгоритмов на различных алгебраических подходах, теории графов, конечных автоматов, каких-либо ещё разделах математики — масса.


При этом есть масса неписанных правил: стараются выбирать достаточно изученный раздел математики, не слишком новый и экзотичный, не изобретать свою математику для криптографии (если ваш автор взял готовую известную алгебру — это нормально, а вот если изобретал свою и параллельно применил её в криптографии, то это может иметь чисто теоретический интерес). Другая проблема — сложность доказательства сводимости к некоей трудной проблеме (или её суррогату), слишком большие допуски, зазоры в доказательстве. Ну и т.д., само по себе наличие того, что вы перечислили недостаточно.


Врут авторы книг, что нельзя использовать цитаты из Шекспира и библии. Еще как можно! Все дело в длине цитаты.

Т.е. случай, когда компьютеры гугла и прочих сервисов сливают все сведения человечества напрямую в суперкомпьютеры АНБ, которые смогут перебирать комбинации из всего когда-либо где-либо написанного, подстраиваясь под предположения о ваших индивидуальных предпочтениях в выборе пароля, вам неинтересен?

— neverward (10/07/2012 12:30, исправлен 10/07/2012 12:36)   профиль/связь   <#>
комментариев: 43   документов: 0   редакций: 7
Если это количество итераций — сколько раз хэш вычисляется за 1000 секунд

это типичный сервер, который работает memcache сервером. Он вычислял без дополнительного оборудования, естественно можно подбирать быстрее, но это всё можно свести на нет. Например берём из устройства /dev/urandom некоторое количество данных и записываем соль(salt), а хешировать мы будет слова hello world



в итоге получилось


Теперь радужные таблицы бесполезны. Даже если Вы создали сто миллионов паролей 'hello world' хеш будет разным каждый раз из-за разной соли.
Далее 1 млн раз выполняем hash=sha512(hash) и теперь бесполезен брутфорс, но зато теперь вход по правильному паролю также занимает время


поскольку переделывать чужое изделие нельзя, даже приписывать к нему свою теорию нельзя, это незаконно, алгоритм не опубликован, значит, и теорию публиковать не положено, а отпадут эти тонкие вопросы авторского права лет этак через пятьдесят — тогда пожалуйста, уже и автора в точности нет в живых, и у наследников, если таковые имелись, права истекли. Но кому это нужно через пятьдесят лет? Если призадуматься, то и сейчас никому не нужно…

АП защищает конкретную реализацию. Т.е. написал функцию сам, всё, она твоя.
Патент защищает идёю, но правильный патент раскрывает все внутренности. И патент не запрещает создавать реализацию для себя и поощряет реализовывать устройство с теми же функциями, но другими внутренностями

— Agathon (10/07/2012 16:37)   <#>
В тестах openssl прогоняются блоки размером 16, 64, 256, 1024, 8192 байта в течении трёх секунд, а затем выводится результат: сколько обрабатывается байтов за секунду при таких размерах блока.

Наконец-то я понял! Спасибо, Unknown!

Модератор, а кто зачинщика удалять будет?
А за что? Что он такого плохого сделал? Подкинул уже упавший топик, оживил угасший разговор. Разве плохо?

Если бы функция претендовала на какой-нибудь стандарт, то такой режим должен быть опциональным и полностью отключаемым, так как во многих случаях замедление не нужно…

Отключается, отключается, я же говорю, переменная Idling установлена в 256 – а можно установить ее в единицу, а можно установить 65 535 – но вот уже больше нельзя, чтобы больше, надо изменить разрядность переменной, взять dword вместо word, что тоже не очень сложно.
Переменить цифру хитрость небольшая, а там есть большие хитрости – для каждой функции есть альтернатива, параллельный вариант: не одна функция инициализации, а две разных, не одна хэш-функция, а две разных, не один поточный шифр, а два разных, и только асинхронный шифр только один, в этом случае выбор небогатый, выбирать можно только длину сдвигового регистра – либо после обрыва или пропуска будут испорчены пять байт, а дальше наступит синхронизация и все пойдет гладко, либо будут испорчены семь байт, — второй вариант кажется менее приятным, но он надежнее и прочнее. В других случаях альтернативные функции существенно различны – одна функция инициализации чисто алгебраическая, использует разного рода бинарные операции, которые можно назвать умножениями, а другая совсем не алгебраическая, там в двадцати строчках кода реализован довольно замысловатый клеточный автомат, алгебры уже никакой, логика динамическая, с выполнением операций по условию «если»; один хэш дает на выходе строку, похожую на случайную, любой байт на любом месте с равной вероятностью, комбинаторно это размещение с повторениями (выборка с возвратом), а у другого хэша строка тоже похожа на случайную, но это размещение без повторений (выборка без возврата), это тесно связано с используемыми методами, они очень, очень разные,.. Об этом уже тоже говорил – просто удивительно, как много всего можно запихать в 8 килобайт автокода!

На конкурсе SHA-3 были полностью алгебраизированные построения — хэши на основе алгебры квазигрупп, соответственно работы очень хорошо обоснованные математически…

Ах, очень жаль, что я ничего об этих текущих новостях не знаю!
Дело в том, что та штуковина, которую я так усердно разбираю уже несколько лет, тоже широко использует квазигруппы, да это само по себе и не редкость, это алгебра из учебника, сто лет известна, — но по способу, которым квазигруппы используются, есть сходство (отдаленное) только с алгоритмом 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. И что, это законо, это теперь мое изделие, закон защищает мои права? Бред, мне кажется… Хотя все на свете бывает.


С благодарностью всем ответившим в теме, Агафон
— neverward (10/07/2012 17:48)   профиль/связь   <#>
комментариев: 43   документов: 0   редакций: 7
Я разобрал алгоритм Ривеста RC4 – который, заметим, сам автор не публиковал, потому и разбирать его теорию публично, мне кажется, не совсем законно, — но я разобрал, понял, что там вместо генератора комбинаторный объект, перестановка всех перестановок, и быстренько написал клон, свою версию этой функции, но не на восьмибитовый байт, а на семибитовый, получается перестановка 128 символов вместо 256. И что, это законо, это теперь мое изделие, закон защищает мои права? Бред, мне кажется… Хотя все на свете бывает.
Патент в отличии от АП защищает идею изобретения. От смены 256 на 128 символов, или семи бит вместо восьми идея не меняется. Например есть патент page Rank или там map reduce. Там полностью описано, как они работают. Т.е. патент раскрывает всем идею изобретения. Хотите сделать поиск? Ноу проблем, изучайте идею page rank, додумывайте как можно сделать по другому, лучше и делайте, все будут только за. По сути патент как раз и нужен для того, чтобы вывести изобретение из коммерческой тайны и через некоторое количество лет сделать его общественным достоянием, плюс создать конкуренцию в виде других изобретателей, которые придумают то же устройство с другой внутренней реализацией. Это в идеале естественно.
— unknown (10/07/2012 17:58)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
полуразрешимая алгебра, имеет разрешимость только в одну сторону: произведение можно делить на правый множитель, а на левый нельзя, в эту сторону деление не определено, так что правый множитель нельзя заменить неизвестным иксом

По вашим намёкам было понятно, что это что-то наподобие квазигрупп, может ещё какая большая экзотика — неополя, например.
Очень интересно, что там делали с квазигруппами конкурсные авторы на NIST, жаль, что не знаю подробностей! Теперь, наверное, и не узнаю.

Материалы конкурса SHA-3 есть в открытом доступе. Квазигруппы использовали хэши Edon-R и NaSHA.

я разобрал, понял, что там вместо генератора комбинаторный объект, перестановка всех перестановок, и быстренько написал клон, свою версию этой функции

Поскольку RC4 был одновременно и собственностью компании и коммерческой тайной, то после восстановления алгоритма (обратного инженеринга) у компании RSA security (даже не Райвиста лично) осталось право только на оригинальное название. Теперь можно использовать алгоритм без изменений под названием ARC4. Можно делать модификации, наподобие VMPC.
— Agathon (10/07/2012 20:12)   <#>
Опять троллите.
Главный гость pgpru откровенно оффтопит, вызывает дисскусию на оффтопичные темы…
Милый Гость, вот какого черта! Что Вы такое несете?

Оставим в стороне грубости. Рассмотрим только логику и семантику высказываний.
Вижу грубые ошибки.
Что значит — оффтоп? Люди вышли за пределы темы топика? Люди вышли за пределы темы форума? Люди стали говорить о чем-то, неинтересном остальным присуствующим? Да нет, люди собрались и тихонько толкуют о том, что им интересно. Но тут приходит некий сердитый господин и доводит до сведения собравшихся, что им это неинтересно — заткнитесь, сволочи, прекратите оффтопить на оффтопичные темы, остановите срач!
Это как? Гость, автор этого сообщения, лучше меня знает, о чем мне интересно поговорить? И лучше админа знает правила форума? Бред…
Мне кажется, дело в другом, просто человеку хочется подраться. Но ведь если к его желанию снизойдут, то неизвестно, чем дело кончится. Могут того, побить… Тут на кого попадешь, знаете…

По сути патент как раз и нужен для того, чтобы вывести изобретение из коммерческой тайны и через некоторое количество лет сделать его общественным достоянием, плюс создать конкуренцию в виде других изобретателей, которые придумают то же устройство с другой внутренней реализацией.

Это да, это я понимаю, мне очень нравится эта мысль — сделать какую-нибудь вещь общественным достоянием, я сам большой энтузиаст и общественник.
И других энтузиастов люблю, до сих пор пользуюсь ассемблером Arrowsoft 1986 года — эта штука замечательна тем, что генерирует объектный файл в точности того же формата, что MASM, совпадение полнейшее, до байта, но MASM платный продукт, по тем временам даже дорогой, а этот Arrowsoft гордо сообщает о себе: Public domain! Значит, я могу пользоваться этой штукой законно, для любых целей, в том числе и коммерческих, наряду с компилятором Тurbo C++ v.1.01, который я примерно в те же времена, году этак в 1993 или 1994 законно купил в Москве, заплатил деньги из своего кармана, получил коробочку с кучей дискет 360 кб и кучей красно-белых книжечек, полной документацией на русском языке. Эти книжечки и по сей день у меня, я их увез с собой на другой край света, полезнейшая штука, описание языка, описание библиотеки...
Но вот кто бы мне объяснил, на какие шиши живет автор ассемблера Arrowsoft? Что он кушает? Положим, работает он так, только для общественного блага, а его собственных детей кто кормит? А кто кормит остальных энтузиастов и общественников? Никому из них даже в голоу не приходит попросить за свою работу эту «несметную кучу буржуйских бабосов», которая уже упоминалась в теме?

По вашим намёкам было понятно, что это что-то наподобие квазигрупп, может ещё какая большая экзотика — неополя, например.

Ой, квазигруппы — это бы хорошо, это еще цветочки, все же хорошая алгебра, в которой каждое уравнение имеет только одно решение. Ладно, пусть системы уравнений в квазигруппах не решаются, нет ничего похожего на гауссов метод исключения неизвестных, также умножение элемента квазигруппы на себя выполнимо, но результат этого «возведения в степень» ничем не похож на циклическую подгруппу, нет здесь ничего вроде теоремы Лагранжа — и из этого последствия вытекают необозримые. Но все равно квазигруппы это цветочки! А штука, которую я разбираю, вообще выше моего разумения, там твердо проводится такой принцип, что алгебру можно сделать из чего угодно. Условие замкнутости автора стесняет, это неудобное условие, чтобы операнды принадлежали одному множеству. Какого черта! Умножаем что угодно на что угодно! Увидели два каких-то объекта — и мигом определили для них умножение. Ну, получается хромая алгебра, полуразрешимая, но хоть какая-то — лучше чем никакой…

Конечно, хамство, в учебнике алгебры такого рода хамство встречается только один раз и сопровождается множеством оговорок: вектор можно умножать на число, но число нельзя умножать на вектор, в первом случае алгебра выходит плохенькая, но действие имеет смысл, умножение вектора на число просто растягивает его, а умножение числа на вектор смысла не имеет, — а в нашем случае автор не ограничивал себя такими соображениями, он умножает что угодно на что угодно, вектор символов на одиночный символ, один символ на вектор символов (в этом случае получается нечто похожее на многомерное векторное пространство), вообще любую строку на любую, короткую на длинную, длинную на короткую… Конечно, замкнутости нет, операнды из множеств разной мощности, значит, однозначной разрешимости уравнений нет, у каждого уравнения много решений. Ну и плевать! Дуй, Ванька, бога нет! Уравнение не решается относительно левого множителя? И прекрасно, оценили вероятность коллизий и пошли дальше. А для правого множителя уравнение решается? Тоже хорошо, полезная возможность, она тут же пристегнута, пошла в дело: можно умножать символ (короткую строку) на вектор (длинную строку), а можно делить, результат однозначно определенный.

Словом, такая свободная алгебраизация чего угодно. И все идет в дело, все пихаем в суп – унарная операция хороша тем, что имеет инволюцию, это тут же используется, процесс запускается вспять, а клеточный автомат хорош тем, что инволюции не имеет, и это тоже используется – вот вам необратимое преобразование, доказательно необратимое, просто тасуем колоду, вернуться к предыдущему состоянию нельзя, потому что процесс не просто детерминированный, а условно-детерминированный…

Так что про неополя ничего не знаю, но экзотики насмотрелся сам и знакомых алгебраистов помучил изрядно…

И при этом процедурно все просто, до идиотизма просто! Простая до невозможности формулировка «умножаем символ на шесть предшествующих» подвергается редукции, разложению, и оказывается, что она по сути не примитивна, не элементарна, в ней спрятано четыре разных примитива: бинарная операция (умножение символа на вектор), унарная операция (умножение вектора на себя), нециклический сдвиг вправо (понятие «предшествующий» или «следующий» логически примитивно, но в реализации может совпадать с операцией сдвига, отбрасывания левого элемента, приписыванием нового справа), и еще четвертый примитив, касающийся самого способа, которым задано умножение, он в полном смысле примитив, простой как веник, но неожиданный, не могу его здесь описывать… Да, а потом все эти примитивы используются порознь, в разных комбинациях… Цирк!

Материалы конкурса SHA-3 есть в открытом доступе. Квазигруппы использовали хэши Edon-R и NaSHA.

За ссылку спасибо, но я не смогу с этим ознакомиться. Немолод, нездоров, по-английски не читаю, математику понимаю ограниченно, систематической подготовки нет, так что боюсь помереть раньше, чем разберусь с той разработкой, которая уже оказалась у меня на руках, а она для меня представляет не только отвлеченный познавательный интерес, тут есть кое-какие моральные обязательства. Есть люди, некоторые живы, других уже нет… Конечно, хорошо бы ознакомиться с новинками, разобрать, сравнить, но я этого уже не успею.


С уважением, Агафон
— Гость (10/07/2012 22:14)   <#>

Ну тогда
от слабой половины строки … можно и вообще отказаться.


/Черновики/Руководства/ВопросыКандидатывFAQ/КриптографияПрактика. Там же есть и /Библиотека/Основы/ФонетическийПароль. И комментарии к топикам тоже почитайте.
— Agathon (11/07/2012 00:19)   <#>
/Черновики/Руководства/ВопросыКандидатывFAQ/КриптографияПрактика. Там же есть и /Библиотека/Основы/ФонетическийПароль. И комментарии к топикам тоже почитайте.
По ссылке ходил, руководство Эдвина Суоминена по составлению фонетического пароля видел, спасибо.

Занятная выдумка, вроде вычисления числа Пи бросанием иголки на разлинованную бумагу, но мне кажется, что эта фиговина, несмотря на фонетическую упорядоченность (чередование гласных и согласных, имитация слов живых языков), трудно запоминается. Это немногим лучше, чем какой-то пароль или номер лицензии, который сгенерировал автоматически какой-то сайт и прислал мне с умоляющим письмом: вот ваш код — C14454427H1200A0414-64FEKF90 — храните его, не потеряйте, мы не сумеем вам его восстановить в случае утраты!

Вот я его и храню, только забыл, от чего этот ключ. Этот ключ, подобен "ключу от брошенной шкатулки в море..."
Чьи это слова? Пушкина это слова! Правильные слова, хотя в порядке слов есть погрешность, он изменен ради размера. Но Пушкин всегда прав! И Пушкин всегда лучше!

Вот к чему я клоню: стихов Пушкина я могу запомнить сколько угодно, а любые четыре строчки лучше всякого случайного пароля, порожденного автоматически или истинным бросанием жребия, сиречь канцелярской скрепки...
Пушкин лучше!
Но, разумеется, и здесь есть правила: строки "Я помню чудное мгновенье" и "Мороз и солнце день чудесный" в качестве паролей стоят там же, где слова Shadow и Tiger... Нельзя брать первое, что приходит на ум. Тривиальность — враг секретности.


Ну тогда...
...от слабой половины строки … можно и вообще отказаться.
Я думал об этом. Но жаль добро бросать.
Все же вторая половина не совсем лишняя, для хэша 16 байт коллизии второго рода ("дни рождения", пары текстов с одинаковым хэшом) отыскиваются легко, пространство перебора можно ограничить восьми- и девятибайтовыми векторами, а для хэша 32 байта коллизий нельзя найти никак и никаких. И никогда!
Так что слабая половина вроде совсем не лишняя, очень не лишняя... Вроде того, что в жизни называют слабой половиной, — тоже вроде и не годятся никуда, а иногда не лишние...

С уважением, Агафон
— Гость (11/07/2012 00:47)   <#>
По стантадарту хэш должен быть полностью случайный. Это устовяшееся требование к нему.

Что касается фонетического пароля, правильный метод таков: генерируется один пароль, выбираемый случайным образом из пространства 2128, а затем пользователь уже сам придумывает способ его запоминания.
На страницу: 1, 2, 3, 4, 5, 6, 7 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3