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

Кстати, с практической точки зрения, важен ещё объём памяти в процессе исполнения алгоритма, не только скорость. Безотносительно к объёмам памяти современных компьютеров, он всё равно должен быть минимальным для универсальности. RC4 — один из самых быстрых, но во многих случаях (микроконтроллеры, смарт-карты) неприемлимый по объёмам памяти.

Да, если 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 гиг памяти. Это уже много для сервера на виртуальном хостинге, а ведь ему нужно память ещё подо что-то.

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

русским в силу присущего им коллективизма как то в голову не приходила мысль, что можно что-то требовать за раздачу того, чего от тебя при этом не убывает

Это хорошее качество и позволяет надеяться, что идеи копирайта в России понимания не найдут и умрут так толком и не родившись, несмотря на то, как их активно насаждают.

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

Это не кража, изобретатель не теряет возможность производить своё устройство. Патент получен на разгаданную коммерческую тайну нельзя. Патент даёт защиту от монополии. Если Вы думаете, что бесконечные монопольные права дают пользу, взгляните на десятки умерших стандартов компрессии, просто потому, что способы сжатия были запатентованы и продавались. Вместо этого Вы сейчас пользуетесь бесплатным софтом потому, что бесплатный выгоднее для пользователя, чем платный. Возникает вопрос – как извлечь прибыль? Прекрасный вопрос, зачем миру очередной стандарт шифрования или сжатия если текущие полностью выполняют свою задачу? Никто не даст и цента. Можно изобрести велосипед о пяти колёсах с планетарными передачами. Но продать массово – вряд-ли. Потому что не все изобретатели понимают, что даже лучшее по одному признаку может быть совсем не нужно из-за других, не очевидных изобретателю признаков.

а если я написал роман, у детей и внуков права на гонорар кончаются через 50 лет после моей смерти

Через 70 после смерти или после публикации. Если автор издал роман в 20, прожил до 100, то его роман будет приносить прибыль 150 лет. Впрочем скорее всего он перестанет приносить прибыль через пару лет из-за того, что покупать перестанут. Да и вообще сейчас дети уже не читают, они не будут и даром читать книги в будущем. Писатели должны были следить за рынком сбыта, чтобы он не исчез. Все производители следят же.

а если я изобрел зубной порошок с низкой абразивностью, то меня лишат прав на это изобретение еще при жизни, лет через 17...

ничего подобного, если никто не разгадает( как часто бывает с всякими колами или хейнзом), то хоть тыщу лет можете получать деньги ничего не патентуя. Но защиты от другого ума, который может быть разгадает Ваш секрет у Вас нет(есть защита от кражи коммерческой тайны). Либо получайте защиту государства в обмен на гарантию монополии. Всё честно.

Нет, искусство принадлежит народу! И новая техника является народным достоянием...

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

но кто же их все-таки кормит при таких порядках? Как они при таких жлобских законах с голоду не перемерли?

Не думаю, что Марк Цукерберг умирает с голоду.

Агафон, ну сейчас точно оффтоперы набегут. Все социалистические, антибуржуазные и антикопирайтные идеи тоже придумали на Западе и именно там они и получили максимальное распространение (свободное ПО, добровольный отказ ряда изобретателей интернет-протоколов от их патентования и от миллиардов потенциальной выгоды и пр.). Мы не обсуждаем полит. вопросы в общей ветке.

Виноват, исправлюсь!
По вопросам морали и права больше оффтопить не будем, будем оффтопить только по математике. Но уж от души!
А как иначе? Иначе и неинтересно. Только оффтоп и флуд украшают жизнь на форумах. Ну, еще иногда флейм.

Всего три миллиона букв ... сколько это будет — всех подстрок не длинее 512 символов?

Весьма немного, около полутора миллиардов (длина текста помноженная на максимальную длину подстроки).

Простите, мне кажется, оценка неверная. Вы умножаете там, где надо возводить в степень.

В строке длины N из разных символов есть ровно (N-M)+1 подстрок длины M.
Например в строке длины 3 "abc" есть только (3-2)+1=2 подстроки "ab" и "bc" длины 2.
При некоторых одинаковых символах разных подстрок может быть меньше.
Полюбому меньше чем N. Поэтому подстрок длины не больше чем М будет меньше чем N*M.

Где тут надо возводить в степень?

В котором, кстати, обвиняемого могут привлечь к ответственности за отказ давать показания против себя, поэтому и с паролем у них всё логично.

Для вероятностных процессов понятия априорности/апостериорности/(не)детерминированности давно приняты.

Если я правильно понял, эти понятия априорности-апостериорности как раз то самое, что по-русски называют проще, условными и безусловными вероятностями в модели зависимых случайных событий. Предварительная вероятность того, что при сдаче колоды пиковая дама выйдет в точности восьмым номером, равна 1/36, но потом она меняется в зависимости от уже наступивших событий — потихоньку растет, если среди первых семи карт пиковой дамы не было, либо падает до нуля, если пиковая дама уже вышла.
А я еще о другом говорил — сверх всего этого добавляется понятие отложенной случайности. Колода карт не процесс, а комбинаторный объект, перестановка. И сдача колоды не случайный процесс, а только иллюзия процесса, это перечисление, перебор элементов статического объекта — и только в том порядке, в каком они расположены. Случайный процесс был раньше, когда колоду тасовали, но это отложенная случайность, она актуализируется при сдаче колоды — сдача похожа на настоящую случайную выборку без возврата.

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

Допустим, я утверждаю, что гамма шифра такого-то со стороны статистики описывается в два слова — она имеет статистику идеальной монеты, любой бит с равной вероятностью может быть единицей и нулем. Но я помню, какое лицо было у полковника Т., когда он это утверждение услышал. Много лет прошло, а я помню. Полковник Т. был не совсем военный человек, он был математик, доктор физ-мат наук, лауреат госпремии, а служил он в советские времена... ну, не будем говорить, где он служил. Главное, служил в таком месте, где предмет знали хорошо, а по специальности полковник Т. был как раз не алгебраист, а вероятностник. Вот у него лицо сразу отвердело, он насупился и сказал тихим голосом, что про монетку просит меня забыть, чтобы я больше при нем таких вещей не говорил. Потому что у настоящей монеты настоящие случайные испытания, на каждом броске может выпасть орел или решка, а гамма есть вычислимая функция, там никаких "или", все биты определены заранее — даже самые далекие, те, до которых нам эту гамму вычислять миллиард лет...

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


PS. Да, а насчет количества подстрок в "Войне и мире" я, кажется, наврал... Похоже, прав коллега, кортежей не так много... На бумажке надо проверить!

Вот если противник не может различить объект от процесса, в особенности предсказать биты, определённые заранее, тогда задача и выполнена.

Вопрос об истинной случайности? Этот вопрос по-настоящему не решён никак

А как же квантовая механника? Разве из теоремы Белла не следует существования истинной случайности?

В общем, противник не должен никак различать, снята гамма с шифра или это запись бросков идеальной монеты.

Это виднее тем, кто её использует. Ну вроде как истинная случайность идёт оттуда, да, хотя вот spinore предупреждал, что там всё не так идеально.

Вот если противник не может различить объект от процесса, в особенности предсказать биты, определённые заранее, тогда задача и выполнена.

Вспомнился другой старинный анекдот. Американский астронавт из-за какого-то технического сбоя приземлился не там, где надо, забросило его куда-то в Сибирь. Выбрался он из своей капсулы, отцепился от парашюта, пошел искать людей. Шел по тайге целый день, к вечеру набрел на избушку, из трубы дым... Вошел, там сидит за столом мужик в ватнике, в ушанке, в валенках и лопает тушенку из банки. Астронавт бросается к нему радостно, спрашивает: "Ду ю спик инглиш?" — а тот отвечает невозмутимо: "Йес, ай спик. А что толку?"

Вот-вот, это наш случай... Положим, все цели уже достигнуты, и противник уже ничего не может, функция неотличима от настоящего случайного процесса, ничего предсказать нельзя, ни одного бита. А что толку? Если заранее известно, что это никому не нужно, навалом бесплатных продуктов от известных разработчиков. Понятно почему автор пошел в крановщики в Ашдоде (хотел пойти в водители автобуса, но водители автобусов там все арабы, это их монополия). Правильно, кушать-то надо, это только я могу заниматься пустым делом, потому что пенсионер...
И то подумываю переключиться на что-то другое — или в шахматный кружок запишусь, или стихи писать начну.

Ну если так, то да.

Криптография сейчас прошла пик коммерческо-предпринимательсой активности (патенты и инвестиции) и стала больше научно-исследовательской (оклады и гранты).

А все же мучит меня наивный вопрос...

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

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

Положим, списочек пожеланий скромненький, все это осуществимо (кроме последнего пункта), но ведь вопрос стоит иначе — ребята, вы не шутите, вам это нужно? Или не нужно?

Вот в чем вопрос!

Стойкость существующих потоковых шифров и хэшей недостаточна. А предложить более стойкий, но более ресурсоёмкий вариант легко. Все финалисты SHA-3 и так слишком медленные.