О спецификации и криптографическом хэшировании. Часть 2

[mns2012]

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

• Энтропия Шеннона и сжатие данных. Часть 1 (теория)


• Энтропия Шеннона и сжатие данных. Часть 2 (пример)


• Колмогоровские структуры (теория)


• Понятие воспроизводимого кода (теория)


• О спецификации и криптографическом хэшировании. Часть 1 (теория)

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

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

Ассистировать нам будут Google Gemini, ChatGpt и Claude Sonnet. Возьмём всё тот же графический файл в качестве примера:

Брызги чёрной краски на белой бумаге.
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей

1. Введение

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

Примерами дизайнов являются:

• Операционная система Windows, инсталлированная на персональном компьютере;


• Авторучка;


• Лист бумаги;


• Макет Солнечной системы;


• Вымощенная дорожка;


• Подстриженный газон;


• Магнитное поле в установке по изучению плазмы.

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

• Форма и размеры камней на берегу моря;


• Геометрия береговой линии;


• Туманность М31;


• Кристаллическая решётка с дислокациями и т.д.

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

Вопрос о том, можем ли мы распознать, является ли та или иная конфигурация материи интеллектуально созданной, — интересная научная проблема. Оказывается, что в некоторых случаях по самой конфигурации материи, не привлекая дополнительных данных, можно с достаточной на практике уверенностью заключить, что она появилась интеллектуально. Условием для возможности сделать подобный вывод как раз и является комбинация сложности конфигурации и краткости её описания [см. Bill Dembski: Specified Complexity Made Simple]. Об этой комбинации характеристик мы будем говорить в дальнейшем как об эвристике распознавания дизайна или как о бинарном классификаторе наблюдаемой конфигурации материи (дизайн/не дизайн).

По предыдущим записям мы помним, что наше изображение клякс не является сложным по Шеннону, так как значение энтропии для него составляет всего около 1.3 бит на пиксель, что много меньше максимума (глубина изображения равна 8 бит на пиксель). Это выражается в относительно большом коэффициенте сжатия (размер файла до сжатия больше размера после сжатия примерно в 6 раз). Вполне понятно, почему можно сильно сжать данное изображение без потерь: изображение содержит много избыточности — большие области белого цвета, поэтому высока вероятность того, что случайно взятый пиксель будет иметь белый цвет, что можно использовать при сжатии данных без потерь. Всё это мы уже обсуждали.

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

2. Анализ специфичности: колмогоровская сложность K(x)

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

В теории информации показывается, что объекты окружающего мира могут быть представлены строками их описания (формализованной модели), причём отдельный объект допускает множество описаний (моделей), тогда как фиксированное описание однозначно соответствует объекту. В силу этого анализ сложности объекта осуществляется как анализ сложности строк его описания. Поэтому далее без потери общности под объектом мы будем понимать строку его описания. Представление объектов реального мира в виде строк, составленных из символов фиксированного алфавита, должно быть хорошо обоснованным, не вносящим избыточной сложности (англ. reasonable encoding), то есть таким, чтобы переход от одного представления к другому мог быть осуществлён математически эффективно (за полиномиальное время).

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

K(x) = min_P { L(P) : P выводит x и останавливается }.

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

Известным теоретическим результатом является невычислимость колмогоровской сложности: её можно только оценивать, вычислить нельзя.

Объект считается колмогоровски случайным, если его сложность K(x) приблизительно равна его длине L(x), то есть его невозможно существенно сжать или описать короче, чем он есть. Объект, который можно описать программой, значительно короче его длины, имеет низкую колмогоровскую сложность и не является колмогоровски случайным.

В определённом смысле, отличие информационной энтропии Шеннона от колмогоровской сложности — это отличие локальной оптимальности от глобальной (Табл.1).

Характеристика	Шенноновская эффективность (беспрефиксный код)	Колмогоровская оптимальность
Основа	Вероятностное распределение символов	Индивидуальная структура объекта
Метод	Сжатие данных на основе частоты символов (локальные паттерны)	Сжатие данных на основе любого алгоритмического паттерна (глобальные паттерны)
Оптимальность	Локальная для данного набора символов	Глобально минимальная длина программы, которая может воспроизвести x

Таблица 1. Энтропийная эффективность и колмогоровская оптимальность

Связь между колмогоровской сложностью строки данных x, её длиной L(x) и энтропией H(x) как средней информацией на символ текста такова:

K(x) ≤ L(x) * H(x).

L(x) * H(x) является верхней границей, основанной на статистическом распределении данных, в то время как колмогоровская сложность — это глобальный минимум длины программы, вычисляющей x, базирующийся на учёте структуры алгоритмов (энтропия не учитывает алгоритмические паттерны, засчёт которых может быть осуществлена дальнейшая оптимизация кода по длине).

3. Что мы пытаемся продемонстрировать

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

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

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

4. Понятие спецификации

Спецификация — это формальное описание. Например, описание того, как осуществить процесс аутентификации:

1. Берём аутентификационный ключ (хэш);


2. Берём данные (файл изображения);


3. Берём алгоритм SHA-256 и подаём эти данные ему на вход;


4. Получаем хэш на выходе;


5. Смотрим, совпадает ли полученный хэш с аутентификационным ключом:
   
   
   • Если да, то аутентификация прошла успешно;
   
   
   • В противном случае аутентичность данных установленой считаться не может.
   
   

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

5. Спецификация данных на примере изображения клякс

Капли чернил в нашем изображении клякс являются результатом случайного процесса разбрызгивания и растекания. Однако если бы изображение было колмогоровски случайным так, что вероятность цвета для каждого пикселя была бы одинаковой и структурные паттерны отсутствовали бы совсем, его нельзя было бы сжать, и его сложность K(x) была бы близка к его длине L(x) ≈ 146,095 байт. Такое тоже возможно, подобные изображения являются информационным шумом, ниже мы также рассмотрим пример этого.

Изображение клякс:

• Длина файла L(x) (до сжатия): 146,095 байт.


• Длина файла после PNG-сжатия: 24,279 байт.

Поскольку алгоритм PNG-сжатия (LZ77, Хаффман-кодирование) по сути является универсальной программой для генерации исходных данных из сжатой версии, длина сжатого файла является оценкой сверху колмогоровской сложности: K(x) ≤ Размер сжатого файла (PNG) = 24,279 байт.

В данном случае спецификация данных (сжатый без потерь информации файл данных) — это фактически инструкция для действия над данными, чтобы их распаковать. Эта инструкция в виде PNG файла существенно короче самого исходного файла данных: размер сжатого файла примерно в 6.1 раз меньше, чем несжатого (cм. Табл.2).

6. Спецификация данных на примере графического шума

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

Пример изображения со значением энтропии, близким к максимуму (цифровой шум).
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей.
Сгенерировано Gemini

Я специально сделал так, файл с графическим шумом имел тот же формат и те же размеры, что и исходное изображение клякс. Поэтому и размер файла до сжатия такой же, как и у исходного изображения: 146,095 байт (см. Табл. 2).

	Данные		Комментарии
	Кляксы	Шум
Энтропия Шеннона	≈ 1.3 бит/пиксель (очень низкая, максимум 8.0 бит/пиксель)	≈ 7.1 бит/пиксель (очень высокая, максимум 8.0 бит/пиксель)	Средняя информация на символ
Колмогоровская сложность K(x)	≤ 24,279 байт (относительно мала)	≤ 129,040 байт (относительно велика)	Длина кратчайшей программы, воспроизводящей данные
Выводы	Изображение сильно избыточно, так как содержит много белого фона	Изображение не содержит избыточности и очень плохо сжимаемо	Изображение клякс не является колмогоровски случайным; колмогоровскую сложность можно оценить сверху размером сжатого файла, который гораздо короче исходного. Графический шум, напротив, близко к колмогоровски случайному; файл очень плохо сжимаем, а его колмогоровская сложность, оцениваемая размером файла после сжатия, относительно высока.

Таблица 2. Метрики исследуемых файлов данных

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

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

Отдельную запись я отвёл для колмогоровских структур. Аппарат колмогоровских структур позволяет понять, почему случайный процесс может иметь простую структуру, но его конкретный результат является сложным (трудно описываемым короче, чем он есть).

7. Спецификация функции

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

• Мы уже видели, что аутентификацией с использованием случайности занимались испокон веков.

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

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

Спецификация функции в данном случае — формальное представление алгоритма генерации аутентификационного ключа. Популярным алгоритмом хэширования, устойчивым к коллизиям, является SHA-256:

изображение → алгоритм SHA-256 → 256-битовый хэш.

По данным Google Gemini, эффективная реализация этого алгоритма на языке С занимает порядка 20-30 килобайт. Это значительно (примерно в пять раз) меньше исходного размера файлов данных до сжатия (146,095 байт).

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

8. Анализ программного кода SHA-256

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

Как таковые, данные (в нашем случае изображение клякс) вне информационного контекста (например, вне контекста аутентификации) не несут никакой функции. Мы пытаемся показать, что программный код функции аутентификации, выводящей практически уникальное значение 256-битовой хэш-функции, вычисленное для исходных данных, имеет классифицируется как дизайн, тогда как относительно самих данных мы этого утверждать не можем. Вот для чего нам и нужно оценить энтропию программного кода, реализующего алгоритм хэширования SHA-256.

Согласно Gemini, энтропия программного кода на языке C (язык среднего уровня) составляет 4.0-5.5 бит на символ текста, значение энтропии того же программного кода, но реализованного на языке машинных инструкций, значительно выше (примерно 6.5-7.5 бит на символ) при максимуме в 8 бит/символ (при использовании стандартной кодировки клавиатуры). Отсюда видно, что даже энтропия программного кода на языке С значительно выше значения энтропии исходного изображения (1.3 бит на пиксель), уже не говоря о машинном коде.

Вынесем результаты наших расчётов в Таблицу 3. Характеристики исходных данных были нами подсчитаны. Характеристики алгоритма SHA-256 предоставлены Google Gemini.

Характеристика	Данные х: чёрно-белое изображение клякс	Данные х: чёрно-белый графический шум	Код P: программа SHA-256
			Язык С	Машинный код
Размер файла до сжатия, Кб	146,095		≈5-20	≈10-100
Энтропия H, бит/пиксель	≈1.3	≈7.1	≈4.0-5.5	≈6.5-7.5
	Очень низкая	Очень высокая	Средняя	Высокая
Коэффициент сжатия Cr	≈6.1	≈1.13	≈1.45-2.0	≈1.07-1.23
	Высокий	Низкий	Средний	Низкий
Размер сжатого файла, Кб	10.5	126.0	≈1-7	≈5-50
Верхняя оценка колмогоровской сложности K, Кб	≤10.5	≤126.0	≤20	≤20 + Cк
	Относительно низкая	Относительно очень высокая	Относительно низкая
	Данные легко сжимаются	Данные практически не сжимаются	Короткий и воспроизводимый код
Класс	Не дизайн		Дизайн

Таблица 3. Характеристики исходных данных и программного кода SHA-256

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

В Таблице 3 используется понятие воспроизводимого кода, которому отведена отдельная запись.

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