Конференции ИВТ СО РАН

Тезисы докладов

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

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

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

Идея АКФС может быть проиллюстирована на следующем примере. Пусть источник порождает буквы из алфавита A={a,b} с вероятностями p(a)=3/5, p(b)=2/5 и пусть размер текущего интервала в арифметическом кодере составляет 7 единиц. Мы должны распределить буквы источника на этом интервале в соответствии с их вероятностями. Но коль скоро мы должны работать с целыми числами мы можем, самое лучшее, выделить 4 единицы для буквы a и 3 единицы для буквы b, округляя таким образом "правильные" доли (4.2 для a и 2.8 для b). Это приводит к кодовой избыточности и, следовательно, к несовершенным статистическим свойствам кодовой последовательности. Мы предлагаем другой путь. Выберем фиктивный символ d с вероятностью 2/7, а символ источника --- с вероятностью 5/7. Мы получим p(a)=3/7, p(b)=2/7 и p(d)=2/7. Теперь эти три символа хорошо распределяются на интервале в 7 единиц, что приводит к генерации безызбыточного арифметического кода с совершенными статистическими свойствами (нули и единицы равновероятны и независимы).

По сравнению с оптимальными побуквенными омофонными кодами описываемый метод дает много меньшее растяжение сообщения и потребление случайных бит. Оптимальные побуквенные коды для каждого символа сообщения добавляют к кодовому слову, в среднем, 2 бита сверх энтропии источника и используют, в среднем, 4 внешних случайных бита. Снижение этих характеристик может быть достигнуто за счет обработки блоков символов, что вызывает экспоненциальный рост сложности алгоритмов. Предлагаемый метод достигает произвольно низкого растяжения сообщения за почти линейное время. Фактически, он требует всего нескольких машинных операций для кодирования и декодирования каждого символа. Как и все арифметические коды, новый метод также имеет преимущество в быстрой адаптации к меняющимся распределениям вероятностей символов источника. Побуквенные же методы должны заново вычислять кодовые таблицы, если вероятности символов источника меняются, что затрудняет их применение в таких ситуациях. Это свойство оказывается актуальным при построении так называемого универсального омофонного кода [2].

[1] Шеннон К. Работы по теории информации и кибернетике. -- М.: ИЛ, 1963. -- С. 333--369 (Теория связи в секретных системах).

[2] Fionov A. Universal homophonic coding // 2001 IEEE International Symposium on Information Theory (ISIT 2001). -- Washington, DC, USA, June 24-29, 2001. -- P. 116.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск