Инструменты пользователя

Инструменты сайта


examination:mszki:question43

Тестирование криптографических алгоритмов на основе алгоритмов сжатия

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

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

1. довольно большой по объему ключ (в пересчете на биты это 2048-битовый ключ), который не везде сможет использоваться;

2. к тому же на самом деле используется не все ключевое пространство, например, использование ключа с нулевыми компонентами просто исключено;

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

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

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

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

1. Взять некоторую начальную таблицу вероятностей P0.

2. Текущей моделью P сделать P0.

3. Получить символ C текста.

4. Применить подстановку или перестановку к символу C – получить новый символ C'.

5. Закодировать полученный символ C' текста в соответствии с моделью P.

6. Модифицировать модель P с помощью символа C.

7. Перейти к п.3 или остановиться, если текст закончился.

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

1. Взять некоторую начальную таблицу вероятностей P0.

2. Текущей моделью P сделать P0.

3. Получить символ C текста.

4. Применить подстановку или перестановку к символу C – получить новый символ C'.

5. Закодировать полученный символ C' текста в соответствии с моделью P.

6. Модифицировать модель P с помощью символа C.

7. Перейти к п.3 или остановиться, если текст закончился.

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

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

В процессе кодирования массивы изменяются, символы передвигаются по кодовому пространству, обеспечивая в будущем эффективное по времени декодирование сжатого текста. Но вместе с изменением расположения отрезков, соответствующих символам, в кодовом пространстве изменяются также и представления сжатых символов, то есть в наших терминах – шифробозначения. Например, передвинув символ «В» из конца кодового пространства в начало, кодирующее значение может выглядеть не как запланированное изначально 0.9568894, а 0.002389. Соответственно меняются и биты, кодирующие наше результирующее значение. Вдобавок в адаптивном алгоритме все меняется динамически после изменения каждого символа.

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

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

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

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

#include «p_table.h»
void rotate_key(char *key) {
int z, i, s;
s = z = key[15];
for (i = 15; i > 0; i--) {
	key[i] = key[i-1] ^ ((i*z) & 0xFF);
	if (key[i] & 0x01 != 0) s += (s*i + key[i]) & 0xFF;
}
key[0] = (z + s + 1) & 0xFF;
}

void rotate_index(char *key) {
int i, b, k, q;
for (i = 0; i < 256; i++) {
	b = i >> 4;
	k = i – (b << 4);
	if ((key[b] >> k) & 0x01 != 0) {
		if (key[b] > 128) {
			q = sym2index_aac[P[i]];
			sym2index_aac[P[i]] = sym2index_aac[i];
			sym2index_aac[i] = q;
			q = index2sym_aac[P[i]];
			index2sym_aac[P[i]] = index2sym_aac[i];
			index2sym_aac[i] = q;
		}
		else
			updatemodel_aac(key[b]);
	}
	else {
		updatemodel_aac(key[b]);
	}
}
rotate_key(key);
}
examination/mszki/question43.txt · Последние изменения: 2014/01/15 08:20 (внешнее изменение)