Category: it

Category was added automatically. Read all entries about "it".

wall

Верхний пост

Всем привет.

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

Я не пишу под замок. Сейчас "под глазиком" лежит n штук недописанных постов, под замком один пост с оффлайновыми контактами. И может быть ещё что-то случайное из давней древности.

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

Последний пример: lz4

Про lzo писать не стоило. Нужно было два примера, один хорошо сжимающий, второй быстрый. DEFLATE -- единственный естественный кандидат на первый, а на второй надо было брать lz4. Он проще и стройнее lzo, да к тому же ещё и быстрее. И вроде бы уже популярнее, хотя появился совсем недавно -- в 2011-м. И есть не только код (с комментариями!), но и текстовое описание! Я бы, конечно, так и сделал. Но о том, насколько переусложнён lzo я не знал, пока с ним не разобрался, а когда разобрался, было уже жалко выбрасывать :)

С другой стороны, вполне вероятно, что Yann Collet (автор lz4) смотрел на lzo и восклицал: о сумрачный германский гений! ну зачем же так сложно-то?!

Так что будет много похожего, но гораздо проще и понятнее.

Формат блока

Описан автором в блоге (такая современная замена RFC). Помните байку Дейкстры про туалеты в вагонах (рус.)? Ну вот. Блок состоит из последовательности пакетов (автор называет их "sequence"), каждый из которых объединяет в себе строку литералов (возможно пустую) и совпадение (всегда непустое).

Первый байт пакета ("token") состоит из двух 4-битовых полей: старшие четыре бита относятся к длине строки литералов, младшие -- к длине совпадения.

Количество литералов определяется следующим образом:
количество = (токен >> 4) & 0x0f      // старшие 4 бита
если количество == 0xf:               // предположительно не влезло
    ду:
        количество += следующий_байт
    пока следующий_байт == 255        // предположительно, опять не влезло
Если получилось 0, значит литералов нет. Если не 0, то сразу после этого идёт строка литералов.

Потом двухбайтное смещение в little endian, на котором не стали экономить единичку -- смещение 0 невалидно, корректные смещения начинаются с 1 и означают сами себя.

И наконец, если длина совпадения не влезает в 4 бита, дополнительные байты длины. Алгоритм тот же, что и у количества литералов, с той поправкой, что минимальная длина совпадения -- 4.

Итого, формат пакета:
  • первый байт -- токен. Разбивается на два поля по 4 бита. Старшие 4 относятся к длине строки литералов, младшие к длине совпадения.

  • [если старшие четыре бита токена -- 0xf] дополнительные байты для длины строки литералов

  • [если старшие четыре бита токена не 0] литералы, столько сколько получилось

  • два байта смещения, little endian

  • [если четыре младших бита токена -- 0xf] дополнительные байты длины совпадения

Ээ, гм, собственно почти всё. Последняя деталь -- нужно как-то заканчивать блок. Формат не предполагает специального признака конца блока и при декодировании полагается на то, что вовремя кончится строка (т.е. что вызывающий код знает какой длины сжатые данные), при этом последний пакет:
  • может не содержать совпадения, т.е. кончаться сразу после литералов

  • более того, по стандарту должен не содержать совпадения: последние пять байт должны быть литералами (для совместимости с декодером, который настолько быстр, что не проверяет границы буферов)

  • и ещё одно правило -- совпадения не должны начинаться слишком близко к концу строки, не ближе чем 12 символов (для того же)
Вот теперь совсем всё. Декодер помещается на одну страничку:

Collapse )

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

Формат потока

Совсем недавно, уже в этом году, был предложен стандартный формат для потока данных и API для него в библиотеке.

Описание формата: http://fastcompression.blogspot.fr/2013/04/lz4-streaming-format-final.html
И рассуждения об API в трёх частях (о том, чем руководствовался, без кода или даже прототипов функций): 1, 2, 3.

Всё довольно прозрачно, ничего особенно неожиданного. Не знаю, используется ли уже где-либо. python-lz4 ничего такого пока не поддерживает.

Кодер

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

Доб.: А вот и он: http://fat-crocodile.livejournal.com/196593.html



Всё, ура. Про простые LZ-архиваторы я написал всё что хотел, теперь можно заняться чем-то совсем другим.
wall

Пример: lzo1x

Нельзя просто так взять и написать lzo!

Продолжаем тему LZ-алгоритмов и LZ-архиваторов. Совсем другой архиватор.

LZO это библиотека алгоритмов архивирования, написанных с прицелом на максимальную скорость работы. Название расшифровывается как Lempel-Ziv-Oberhumer; Markus Franz Xaver Oberhumer -- автор LZO. Алгоритмов я насчитал 39, форматов в которые они сохраняю данные – 9 (я считал по экспортируемым функциям; вот здесь в середине есть табличка, правда там только 37 алгоритмов). И всё это не описано нигде кроме исходного кода, о котором автор честно пишет:

Be warned: the main source code in the 'src' directory is a real pain to understand as I've experimented with hundreds of slightly different versions. It contains many #if and some gotos, and is *completely optimized for speed* and not for readability. Code sharing of the different algorithms is implemented by stressing the preprocessor - this can be really confusing. Lots of marcos and assertions don't make things better.

Подтверждаю, всё правда, но всё-таки не ужас-ужас-ужас, в чём-то разобраться можно. А из алгоритмов автор советует пользоваться lzo1x-1 либо lzo1x-999, второй сжимает несколько медленнее, но лучше.

Чтобы не возиться с C, можно использовать обёртку python-lzo, она реализована следующим образом.

Collapse )
Т.е. как раз эти два алгоритма.

Декомпрессор

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

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

  • совпадения бывают четырёх разных типов, в зависимости от размера смещения и длины самого совпадения, более короткие кодируются короче.

  • признак конца данных это тоже такое специальное совпадение

  • интересная идея -- после каждого совпадения может быть хвост до трёх байт открытого текста, не нуждающихся в отдельном блоке.

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

И ещё две оптимизации, влияющие на кодирование:
  • поскольку первым блоком совпадение быть не может (это вариант без предустановленного словаря, не с чем пока совпадать), длина первого блока может (но не обязана) кодироваться немного иначе, чем обычно

  • если у совпадения есть хвост, т.е. если после него идёт 1-3 байта открытого текста, то дальше не может быть блок открытого текста, только следующее совпадение.

Немножко запутано. Дальше будет хуже.

Collapse )

Collapse )

Collapse )

Код

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

Collapse )
wall

Пример: DEFLATE

Теория и обзор это здорово, но интересно же посмотреть, как устроен настоящий архиватор. DEFLATE это самая известная в мире реализация идеи LZ77+Huffman. Это zlib, gzip, он же внутри PNG, его использует SSL и http тоже обычно жмётся им же, и ещё много где. В общем, популярная штука.

Кажется, название формата-и-алгоритма правильно писать всеми большими буквами, но мне очень не понравилось, как это выглядит в тексте, поэтому дальше маленькими -- deflate.

Напоминаю общую идея алгоритмов этого класса: данные проходят через LZ77, потом результат кодируется Хаффманом. Формат, в котором сохраняются сжатые данные, и некоторые части рекомендуемого алгоритма, описаны в RFC 1951.

Код для декодирования (нормального) и кодирования (несколько урезанного) я, конечно, написал, но его получилось немного много для поста, так что в этот раз без примеров кода, извините. Может быть придумаю куда его выложить, приведу в порядок и выложу. Когда-нибудь.

Первый этап, LZ77

Максимальное смещение -- 215, максимальная длина совпадения -- 258 байт.
На выходе последовательность из литералов и пар <длина, смещение>, смещения считаются не от начала окна, а от текущего символа. Совпадения короче трёх символов не рассматриваются. Изначально в окне нет ничего и генерируемое смещение не должно выходить за пределы данных.

Это была обязательная часть. Рекомендательная начинается словами (это раздел 4, "Compression algorithm details"):

... since many variations of LZ77 are patented, it is strongly recommended that the implementor of a compressor follow the general algorithm presented here, which is known not to be patented per se. The material in this section is not part of the definition of the specification per se, and a compressor need not follow it in order to be compliant.

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

  • Аргумент хеш-функции -- следующие три символа.

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

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

  • Вместо этого контролируется длина списка, если он стал слишком длинным, конец обрубается (чтобы поиск не превращался в линейный; вероятно имеется ввиду, что граница, по которой обрубается и граница, при пересечении которой обрубается -- это две разные границы).

  • Предлагается использовать "lazy matching". Найдя совпадение длины N, попробовать найти совпадение большей длины, начинающееся со следующего символа. Если получается, то вместо исходного совпадения на выходе литерал для текущего символа и более длинное найдённое. Если N уже и так неплохое, и нам не критично важна степень сжатия, эту логику можно отключать.

  • Если прежде всего важна скорость, хеш-таблица обновляется только тогда, когда найдено короткое совпадение или его не удалось найти совсем.

Когда обновляется хеш-таблица в обычной ситуации не написано: то ли на каждом шаге, то ли на каждый символ (насколько я понял, zlib в стандартном режиме обновляет на каждый символ).
Но в общем всё довольно просто и понятно.

Collapse )

Пример

Вот такие данные:

15 8d 51 0a c0 20 0c 43 ff 3d 45 ae 56 67 dd 8a 5d 0b d5 21 de 7e 0a f9 08 21 2f c9 4a 57 cb 12 05 5d ec de 82 18 c6 c3 28 4c 05 5e 61 72 3f 23 0d 6a 7c e2 ce c8 e1 8d 0d 73 77 3b c8 0a 94 29 36 e3 a8 ba 12 a9 62 f9 17 50 a9 9c b6 c3 e4 60 b8 e9 c2 24 19 e7 a1 7a ec 2d e9 78 fd 65 1b 07 a5 90 ce e9 07

Collapse )

Чтоб два раза не вставать

В природе deflate встречается как составная часть различных форматов и протоколов. Самые простые, не вносящие каких-то дополнительных смыслов это zlib и gzip.

Collapse )
wall

Дао условных переменных

Вчера внезапно познал. До этого использовал только однажды и, как выяснилось, глубоко неверно. А вчера ситуация позволила вернуться к тому случаю, обнаружить ошибку и заодно узнать что-то новое. Я не упустил.

С одной стороны, конечно, все давно в курсе, но с другой стороны в man-е это так описано, что с первого раза я ничего не понял, поэтому не поленюсь (хотя, когда я читаю man сейчас, мне почему-то всё кажется понятным). Вдруг кому пригодится.

Что это вообще
Это такой POSIX-ный объект синхронизации. Тип данных pthread_cond_t. Их можно:
- создавать (pthread_cond_init или PTHREAD_COND_INITIALIZER),
- удалять (pthread_cond_destroy),
- ждать на них (pthread_cond_[timed]wait)
- и активировать (pthread_cond_signal, pthread_cond_broadcast).

Мысль примерно такая:
- сколько-то потоков ждут наступления некоторого события.
- когда это событие наступает, об этом сообщают либо всем (broadcast), либо какому-то произвольному одному (signal; если быть точным в мане написано "at least one of the threads", на мой взгляд могли бы и гарантировать).
- если сейчас никто не ждёт, активация проходит бесследно

В общем, почти всё тривиально. Но не всё.

Collapse )

Collapse )
wall

Доказательная криптография

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

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Я думаю, вы уловили паттерн.

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

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

  • Доказываем, что при определённых ограничениях нас вполне устроит второе.

  • Доказываем надёжность с огромным запасом "на всякий случай".

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

  • Надеемся, что при формулировке первого идеального понятия мы учли все важные для нас свойства (т.е. что не будет атак неучтённого типа, о стойкости к которым ничего не доказано).

Пользу от этого занятия я вижу в следующем:
  • явно формулируются гипотезы и следствия

  • если надеяться достаточно крепко, то дальше можно манипулировать абстрактными кирпичиками, свойства которых известны, и что-то доказывать про их комбинации

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

Криптография на эллиптических кривых для чайников-2: OpenSSL

Предыдущий пост был написан не только красоты математики ради, но и дела для. Без описанной там поп-теории очень сложно понимать конкретную практику. Группы какие-то, точки, кривые – причём тут это? Нам бы ключи и шифры... А оказывается это они и есть.

Текст чуть меньше чем наполовину состоит из копипасты из заголовочных файлов OpenSSL, но важно же расположить их в нужной последовательности и верно поставить акценты! :)

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )



Collapse )
wall

Криптография на эллиптических кривых для чайников

Я, как обычно, пишу не от большого опыта, а для систематизации мозгов. Так что на особо глубокие откровения не рассчитывайте. Откровения будут весьма средненькие.



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

И то и другое -- системы шифрования с открытыми ключами. RSA основана на сложности задачи разложения числа на множители, Эль-Гамаль -- на задаче дискретного логарифма. Оказывается, что зная (p, g, y) очень сложно найти такой x, что: y = gx mod p.

Collapse )

Collapse )

Collapse )

ура, товарищи! Вот она какая, криптография на эллиптических кривых. Будет вторая часть, про OpenSSL.

Collapse )
wall

scrypt: действительно медленная hash-функция

Есть два способа затруднить атаку перебором:
  • увеличить количество вариантов

  • замедлить вычисление каждого варианта

Первый способ всем хорош (и повсеместен: увеличение битности ключей, хешей и блоков), но не применим в важном частном случае: порождение ключа из пароля. К сожалению, редкий пользователь готов запоминать пароль с энтропией хотя бы в 64 бита :( А ведь для ключей уже давно стандарт не ниже 128.

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



Сердцем алгоритма является функция ROMix (я точно не уверен, но предполагаю, что RO это от Random Oracle):

# Параметры:
# - hash -- хеш-функция
# - integerify -- функция, некоторым образом преобразующая блок в число. Что-нибудь типа "взять m каких-нибудь бит"
# - B -- исходные данные
# - N -- количество итераций
def ROMix(hash, integerify, B, N):
    X = B
    V = []
    for i in range(N):  # генерируем цепочку из N блоков
        V.append(X)
        X = hash(X)
    for i in range(N);  # случайным образом по ней проходим
        j = integerify(X) % N     # номер следующего блока
        X = hash(X ^ V[j])        # следующий X   
    return X

Очень просто и наглядно. В статье есть доказательство (которое я не смотрел), что функция годная, т.е. что без использования O(N) памяти на её вычисление понадобится O(N2) действий, а значит враг повержен.

Collapse )



У него на сайте есть эталонная реализация, но она очень странная. Странность заключается в том, что параметры N, p, r невозможно задать непосредственно. Можно указать только максимальный размер памяти, максимальную долю от доступной памяти и максимальное время вычисления. А дальше она сама подберёт, оценивая производительность CPU и установленные лимиты. Понятно что при таком подходе получить от одного пароля одинаковые ключи на разных компьютерах -- исключительно редкое везение, так что как это чудо использовать ясно не вполне. Причём это не интеллектуальная обёртка поверх, эта логика встроена в код на самом нижнем уровне, т.е. у него в коде просто не существует функции принимающей N, p, r напрямую. Но, конечно, оттуда можно выбросить всё лишнее и останется только нужное, после чего оно наверное работает (хотя я ещё не проверял).