Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Лекция 2. Модели шифров по К. Шеннону. Способы представления реализаций шифров.

з пропедевтики внутрiшньої медицини

для студентів III курсу медичного факультету № 2

на осiнньо – зимовий семестр 2014/2015 року

(тривалість лекції – 2 академічні години)

Місце проведення лекцій: 1–17, 36–37 групи – фізико-хімічний корпус, аудиторія № 3

18–35 групи – фізико-хімічний корпус, аудиторія № 2

Завідувач кафедри пропедевтики

внутрiшньої медицини №1,

член-кор. НАМН України, професор В.З.Нетяженко

Лекция 2. Модели шифров по К. Шеннону. Способы представления реализаций шифров.

Одним из первых ввел и систематически исследовал простую и естественную математическую модель шифра К. Шеннон в книге «Работы по теории информации и кибернетике», 1963 (раздел «Теория связи в секретных системах»). Он рассматривал так называемые «секретные системы», в которых смысл сообщения скрывается при помощи шифра или кода, но само шифрованное сообщение не скрывается, и предполагается, что противник обладает любым специальным оборудованием, необходимым для перехвата и записи передаваемых сигналов.

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

Ядром секретной системы является собственно шифр.

Алгебраическая модель шифра. Пусть Х, К, У – некоторые конечные множества, которые названы, соответственно, множеством открытых текстов (открытых сообщений), множеством ключей и множеством шифрованных сообщений (криптограмм). На прямом произведении Х´К множеств Х и К задана функция (отображение) f: Х´К®У (f(х,c)=у, хÎХ, cÎК, уÎУ). Функции f соответствует семейство отображений f_c: Х®У, cÎК, каждое отображение задано так: для хÎХ

f_c(х)=f(х,c).

Таким образом, f_c - ограничение f на множестве Х´{c}. Здесь {c} – множество состоящее из одного элемента. Заметим, что задание семейства отображений (f_c)_cÎК, f_c:Х®У однозначно определяет отображение f:Х´К®У, f(х,c)=f_c(х).

Введенная четверка А=(Х,К,У,f) определяет трехосновную универсальную алгебру, сигнатура которой состоит из единственной функциональной операции f.

Определение. Введенная тройка множеств Х,К,У с функцией f:Х´К®У

А=(Х,К,У,f)

называется шифром (алгебраической моделью шифра), если выполнены два условия: 1) функция f – сюрьективна (осуществляет отображение «на» У);

2) для любого cÎК функция f_c инъективна (образы двух различных элементов различны).

Из 2) вытекает, что |Х|£|У|.

Запись f(х,c)=у называется уравнением шифрования. Имеется в виду, что открытое сообщение х зашифровывается шифром на ключе c и получается шифрованный текст у. Уравнением расшифрования называют запись f_c^-1(у)=х (f^-1(у,c)=х), подразумевая, что шифрованный текст у=f(х,c) расшифровывается на ключе c и получается исходное открытое сообщение х. Для краткости, в ряде случаев, используют и более простые обозначения уравнений шифрования и расшифрования, а именно, соответственно: cх=у и c^-1у=х.

Требование инъективности отображений (f_c)_cÎК в определении шифра равносильно требованию возможности однозначного расшифрования криптограммы (однозначного восстановления открытого текста по известным шифрованному тексту и ключу). Требование же сюрьективности отображения f не играет существенной роли и оно обычно вводится для устранения некоторых технических, с точки зрения математики, дополнительных неудобств, то есть для упрощения изложения. В ряде случаев мы будем отказываться от этого требования, если его наличие будет усложнять описание или анализ шифра. Таким образом, наличие или отсутствие сюрьективности отображения f в используемом определении шифра будет следовать из текста.

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