Методы эффективной рандомизации сообщений, базирующиеся на омофонном и арифметическом кодировании

• Автор: Фионов, Андрей Николаевич
• Шифр специальности: 05.12.13
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Новосибирск
• Количество страниц: 158 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1 РАНДОМИЗАЦИЯ СООБЩЕНИЙ, ОСНОВАННАЯ НА БЛОКОВОМ КОДИРОВАНИИ
1.1. Введение
1.2. Основные идеи омофонного кодирования и обзор известных методов
1.3. Основные понятия и идеи
1.4. Посимвольное омофонное кодирование при двоичнорациональных вероятностях символов
1.4.1. Обозначения
1.4.2. Кодирование
1.4.3. Декодирование
1.4.4. Основные свойства метода
1.5. Блоковое омофонное кодирование при двоично-рациональных вероятностях символов
1.5.1. Определения и обозначения
1.5.2. Кодирование блока
1.5.3. Декодирование блока
1.5.4. Сложность блокового кодирования
1.6. Посимвольное омофонное кодирование при произвольных рациональных вероятностях символов

1.6.1. Кодирование
1.6.2. Декодирование
1.6.3. Основные свойства метода
1.7. Блоковое омофонное кодирование при произвольных рациональных вероятностях символов
1.7.1. Кодирование блока
1.7.2. Декодирование блока
1.7.3. Сложность блокового кодирования
Выводы
2 РАНДОМИЗАЦИЯ СООБЩЕНИЙ, ОСНОВАННАЯ НА АРИФМЕТИЧЕСКОМ КОДЕ
2.1. Введение
2.2. Основные идеи арифметического кодирования с разделением интервала
2.3. Арифметическое кодирование с разделением интервала
2.3.1. Обозначения и определения
2.3.2. Масштабирование интервала
2.3.3. Разделение интервала
2.3.4. Алгоритм кодирования
2.3.5. Алгоритм декодирования
2.3.6. Избыточность и сложность кодирования
2.4. Реализация случайного выбора интервала
Выводы
3 ОБОБЩЕННЫЙ МЕТОД ПОЛНОЙ РАНДОМИЗАЦИИ И ЕГО ОСНОВНЫЕ ПРИЛОЖЕНИЯ
3.1. Введение

3.2. Синтез блокового и арифметического омофонного кодирования
3.3. Приложение омофонного кодирования к задачам криптографии
3.4. Применение омофонного декодирования в задачах генерации случайных чисел
3.4.1. Постановка задачи
3.4.2. Основная идея метода
Выводы
4 АДАПТИВНОЕ АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ ИСТОЧНИКОВ С БОЛЬШИМИ АЛФАВИТАМИ
4.1. Введение
4.2. Обзор методов адаптивного кодирования
4.3. Избыточность арифметического кодирования
4.3.1. Арифметическое кодирование
4.3.2. Арифметическое декодирование
4.3.3. Избыточность и вычислительная сложность арифметического кодирования
4.4. Быстрое адаптивное кодирование с использованием скользящего окна
4.4.1. Определение скользящего окна
4.4.2. Эффективное кодирование источников с большими алфавитами
4.4.3. Избыточность и сложность адаптивного кодирования
Выводы

а условие выхода за пределы интервала
(гк > Я]) или (гк — Я] и щ = 0 для всех г > .?'). (1.9)
Окончательно код символа и определяется следующим образом:
С (и) = Ь1Ь‘2...Ъсгое1е2...е3г1Г2...Гк, с > 0, § > 0, к > 0, (1.10)
где е = е2 = = е8 = 1 - г0.
Рассмотрим пример. Пусть А = {а, 6, с},
р(а) = 93/256, р(6) = 11/256, р(с) = 152/256
(т = 8). Допустим и = Ь. Имеем
0(6) = 93, 0(6) = 93 + 11 = 104.
Графическое представление интервала [0(6), 0(6)) приведено на рис. 1.4.
Как видно из рисунка, буква 6 может быть представлена тремя омофонами, отображаемыми в подынтервалы следующим образом:
щ(6) — [93, 94), и2(6) -> [94, 96), и3(6) -► [96, 104).
Омофон ь{Ъ) кодируется словом С(Ъ) = 01011101 и должен выбираться С вероятностью 1/11, Г2(6) кодируется СЛОВОМ С2(6) = =0101111 с вероятностью выбора 2/11 и 1>з(6) кодируется словом Сз(6) = 01100 с вероятностью выбора 8/11.
Результат применения алгоритма А1 к кодированию символа и — Ъ приведен в табл. 1.6 (в этом примере с = 2, 5 = 2).
Кроме возможных кодовых слов в табл. 1.6 показаны также “пробные” кодовые слова, обозначенные через Т(6), которые возникают в ходе работы алгоритма, но отвергаются, так как выходят за пределы интервала [0(и), 0()).