Основы теории информации и криптографии

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Т.А. Гультяева

 

 

Основы

теории информации

и

криптографии

 

Конспект лекций

для студентов III курса ФПМИ по специальностям

“Прикладная математика и информатика” (010500),

“Математическое обеспечение и администрирование

информационных систем” (010503),

“Прикладная информатика в менеджменте” (080801)

 

 

Новосибирск

Рецензенты:

Н.Л. Долозов, канд. техн. наук, доц. кафедры программных систем и баз данных.

В.Е. Хиценко, канд. техн. наук, доц. кафедры защиты информации

 

 

Составитель: Т. А. Гультяева, ассистент кафедры программных систем и баз данных.

 

Работа подготовлена на кафедре программных систем и баз данных

для студентов III курса ФПМИ по специальностям

“Прикладная математика и информатика” (010500),

“Математическое обеспечение и администрирование

информационных систем” (010503),

“Прикладная информатика в менеджменте” (080801)

 

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

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

 

 

Тема №1

Основные аспекты теории информации

 

Введение в теорию информации.

Задачи, решаемые в рамках теории информации

Ниже представлена структурная схема типичной системы передачи или хранения информации (рис. 1).  

Вероятностно-статистические модели сообщений

И их свойства

Источники дискретных сообщений

И их вероятностные модели

Отдельные символы сообщения: – это случайная величина, принимающая всевозможные значения из алфавита сообщений : . Если мощность конечна: , то это источник дискретного сообщения (ИДС). Иначе –… Мы будем использовать модель ИДС как наиболее часто рассматриваемую.

Собственная информация

Собственная информация сообщения , выбираемого из дискретного ансамбля – это:   . (1.1)    

Взаимная информация

Рассмотрим два ансамбля сообщений: . – ансамбль сообщений на входе системы, – на выходе. Естественно, что они зависимы. В результате опыта (приема символа ) апостериорная вероятность появления…   . (1.2)

Энтропия

Пусть ИДС описывается некоторым дискретным ансамблем: . Тогда энтропия ИДС (или энтропия случайного символа ) вычисляется по формуле (5):   . (1.5)  

Условная энтропия

  . (1.6)   Появление символа вызывает появление символа с вероятностью .

Избыточность

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

Тема №2

Основные принципы кодирования

 

Введение в теорию кодирования

 

Рисунок 1 из первой темы можно упростить:

 

Рис. 3. Упрощенная структурная схема типичной системы передачи или

хранения информации

 

Кодирующие устройство, в общем случае, может выполнять следующие операции:

1. Согласование источника с каналом (например, перевод реальных сообщений в электрические сигналы, модуляция непрерывных сигналов, квантование непрерывных сигналов, представление -ичного дискретного сообщения в -ичном коде).

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

Конкретный пример для операции 1-ого типа:

каждой букве русского алфавита ставится в соответствие символ из 2-ого алфавита: ‘A’®00000, ‘B’®00001,…

Конкретный пример для операции 2-ого типа:

представление графической информации с использованием блочного сжатия (JPEG).

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

1. Сжатие без потерь информации (неразрушающие сжатие).

2. Сжатие с потерями информации (разрушающие сжатие).

Далее (пункт 2.3) рассмотрим теоретические основы помехоустойчивого кодирования.

Основы экономного кодирования

Сжатие без потерь информации

  Рис. 4. Схема сжатия без потерь

Сжатие с потерями информации.

  Рис. 5. Схема сжатия с потерями

Кодеры, основанные на системе сжатия

Без потерь информации

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

Основные методы побуквенного кодирования

Код Хаффмана – это двоичный префиксный код без памяти. Далее рассмотрим некоторые теоретические основы этого кода. Префиксным множеством двоичных последовательностей называется конечное… Например, множество двоичных слов является префиксным множеством, а – не является.

Код Хаффмана

Далее приведен алгоритм построения кодового дерева Хаффмана: Инициализация. Список подлежащих обработки узлов состоит из узлов, где –… Каждому из узлов приписывается вероятность появления буквы.

Код Шеннона

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

Код Шеннона-Фано

Инициализации. Все буквы алфавита записываются в порядке убывания вероятностей. Цикл. Всю совокупность букв делят на две примерно равные по сумме вероятностей…

Код Гильбера-Мура

Инициализация. Сопоставим каждой букве кумулятивную вероятность и вычислим . Цикл. Кодовым словом являются первые разрядов после запятой в двоичной записи… Средняя длина кодового слова: .

Помехоустойчивое кодирование

Теорема Шеннона (о кодировании в дискретных каналах с шумом). Пусть пропускная способность канала , скорость создания информации , где –… 1. Прямая теорема.

Коды с обнаружением ошибок

Схема кодирования: , то есть контрольный бит с номером дополняет остальные по четности (, если четна; иначе – 1). Схема декодирования: , если – четно, то есть равно нулю, то четность соблюдена… Для данного кода , значит, кратность гарантированно распознанных ошибок . Однако достоинством этого кода является то,…

Коды с исправлением ошибок

Линейные блоковые коды

Если , то линейный код называется групповым, так как кодовые слова образуют математическую структуру, называемую группой. При формировании данного… Далее рассмотрим один из способов задания линейных блоковых кодов – матричный,… § Порождающая матрица: , где – единичная матрица, – матрица, составленная из проверочных символов.

Коды Хэмминга

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

Циклические коды

Циклический код – это линейный блоковый код , который характеризуется: § свойством цикличности, то есть сдвиг влево на один шаг любого разрешенного… § множество кодовых слов представляет совокупность многочленов степени и менее, делящихся на некоторый многочлен…

Тема №3

Основы криптографии

3.1 Терминология и основные понятия криптологии

Проблемой защиты информации путем ее преобразования занимается криптология. Она делится на два раздела: криптография и криптоанализ.

Основные аспекты криптографии

Основные функции криптографических систем: § обеспечение конфиденциальности § обеспечение аутентичности

Основные аспекты криптоанализа

  Существуют несколько типов криптоаналитического вскрытия: 1. Вскрытие только с использование шифротекста: у криптоаналитика есть несколько зашифрованных одним и тем же…

Шеноновские модели криптографии

  Рис. 12. Схема симметричной криптосистемы

Теоретико-информационные оценки стойкости симметричных криптосистем

Свойство устойчивости криптосистемы к криптоанализу принято называть криптостойкостью. Исходное сообщение К. Шеннон предполагал случайным - вектором с дискретным… Симметричная криптосистема называется совершенно криптостойкой, если апостериорное распределение вероятностей…

Тема №4

Математические основы криптологии

 

Псевдослучайные последовательности

1. Сеансовые и другие ключи для симметричных криптосистем (DES, ГОСТ 28147-89, Blowfish). 2. Стартовые значения для программ генерации ряда математических величин в… 3. Случайные слова, комбинируемые с парольными словами для нарушения «атаки угадывания» пароля криптоаналитиком.

Равномерно распределенная случайная последовательность

1. и произвольных значений индексов случайные величины независимы в совокупности. 2. случайная величина , имеет дискретное равномерное распределение… Из этих базовых свойств вытекают следующие дополнительные свойства, используемые при генерации случайных чисел:

Алгоритмы генерации псевдослучайных

Последовательностей

На рис. 13 приведена классификация алгоритмов генерации псевдослучайных последовательностей.

 

 

Рис. 13. Классификация алгоритмов генерации псевдослучайных последовательностей.

 

Выделяются три основных подхода к построению алгоритмов генерации:

1. Прямые методы построения элементарных рекуррентных последовательностей.

2. Методы «улучшения элементарных последовательностей», заключающиеся в специальных функциональных преобразованиях этих последовательностей для уменьшения отклонения их статистических свойств от свойств РРСП.

3. Комбинирование алгоритмов генерации, построенных с помощью первого или второго подхода.

Различные варианты генераторов рассматриваются в лабораторной работе номер 5.

 

 

Теория чисел

Простые числа

Простым числом будет наименьший, отличный от делитель целого .   Теорема 4.1 (Теорема Евклида)

Тестирование чисел на простоту и построение больших простых чисел

Общая схема для большинства методов получения простых чисел состоит из следующих двух шагов: 1. Выбор большого нечетного числа. 2. Тестирование этого числа на простоту.

Теория сравнения

Арифметика вычетов

  , (4.1)   где для некоторого целого .

Функция Эйлера

Количество классов вычетов в приведенной системе вычетов минус один обозначают как и называют функцией Эйлера (или представляет собой количество…   Свойства функции Эйлера:

Сравнение первой степени

  . (4.2)   Под решением любого сравнения понимается класс вычетов по модулю , один элемент которого (а значит и все)…

Решение сравнения первой степени с использованием алгоритма Евклида

Выполним следующие деление с остатком: Тогда . То есть равен последнему отличному от нуля остатку в алгоритме Евклида.

Решение сравнения первой степени с использованием расширенного алгоритма Евклида

Как мы убедились в обычном алгоритме Евклида чтобы найти надо выражать через друг друга остатки , что не удобно. Данный алгоритм позволяет найти в , . Необходимо работать с системой равенств:

Решение сравнения способ Эйлера

Теорема 4.4

Пусть , . Тогда сравнение (4.2) имеет решение (4.3), где .

 

Пример

Решить сравнение .

Решение

, .

Значит: . ●

 

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

 

 

Первообразные корни

  Свойства данного числа : 1. Числа попарно не сравнимы по модулю .

Дискретные логарифмы в конечном поле

  (4.4)   Обратная задача: для сравнения (4.4) по найти его дискретный логарифм (или индекс) . Наиболее быстрый алгоритм решения…

Примеры систем шифрования, основанные на проблемах теории чисел

Система шифрования RSA

Эта система построена на основе степенной функции: . Блок открытого текста, представленный как целое число из сегмента ,… При расшифровывании используется функция : . Пара называется закрытым ключом (используется при дешифровании).

Система шифрования Диффи-Хеллмана

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

Разложение на множители (факторизация)

Самые лучшие алгоритмы на сегодняшний день: 1. Решето общего числового поля (самый быстрый из известных алгоритмов для… 2. Квадратичное решето для чисел размером (для чисел менее десятичных разрядов; в 1994г. за 8 месяцев на 1600…

Вычисление в поле Галуа

Поле – это множество элементов, на котором определены операции сложения и умножения, обладающие свойствами коммуникативности, ассоциативности и… Пусть – неприводимый многочлен над полем , для него существует конечное… Группа – это непустое множество с алгебраической операцией * на нем, для которой выполняются аксиомы:

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Оглавление Тема №1. 3 Основные аспекты теории информации.. 3