МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Омский государственный педагогический университет»

(ФГБОУ ВО «ОмГПУ»)

Факультет математики информатики физики и технологии

Кафедра Прикладной информатики и математики

Помехоустойчивые шифры

Курсовая работа

Направление педагогическое образование

Направленность (профиль) Информатика и Технология

Дисциплина  Теоретические Основы Информатики

Выполнила: студентка

32 группы

Карастилёва Александра Григорьевна

                                                                                                          _______________________

(подпись)

Научный руководитель:

Курганова Наталья Александровна

к.п.н.

Оценка  ________________

«__» _______________ 2015 г.

_______________________

(подпись)

Омск, 2015

Оглавление

Введение        

Глава 1. Теоретические основы использования помехоустойчивых шифров в криптографии        

1.1Основные понятия криптографии, связанные с помехоустойчивым шифрованием        

1.2. Характеристика помехоустойчивых шифров        

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

Вывод по главе        

Глава 2. Практические основы использования помехоустойчивых шифров в криптографии        

2.1.Пример шифрования и дешифрования на основе использования шифра перестановки« Магический квадрат»        

2.2.Пример шифрования и дешифрования на основе использования шифра Цезаря        

2.3. Пример шифрования и дешифрования на основе использования шифра «криптосистема RSA»        

Вывод по главе        

Заключение        

Список литературы        

Введение

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

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

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

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

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

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

Задачи:

• Изучить основные понятия и термины криптографии и помехоустойчивого шифрования;
• Проанализировать характеристики помехоустойчивых шифров;
• Изучение и применение на практике алгоритмов шифрования и дешифрования.

Предмет  – основные понятия помехоустойчивых шифров и криптографии.

Объект – алгоритм шифрования и дешифрования информации .

Структура работы:

Титульный лист;

Оглавление;

Введение;

Основная часть:

Глава 1. Теоретические основы использования помехоустойчивых шифров в криптографии:

Глава 2. Практические основы использования помехоустойчивых шифров в криптографии:

Заключение;

Список литературы;

Глава 1. Теоретические основы использования помехоустойчивых шифров в криптографии

1. Основные понятия криптографии, связанные с помехоустойчивым шифрованием

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

Код – совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков.[3]

Кодовое слово – любой ряд допустимых знаков.[1]

Шифр(cipher) – семейство обратимых отображений множества последовательностей блоков открытых текстов (сообщений) в множество последовательностей блоков шифровальных текстов (сообщений) и обратно.  Каждое из отображений определяется некоторым параметром, называемым ключом, и описывается некоторым алгоритмом шифрования, реализующим  один из режимов шифрования. В зависимости от способа представления открытых текстов(сообщений) и используемых ключей различают блочные, поточные и другие шифры. Основными требованиями, определяющими качество шифров являются: криптографическая стойкость, имитостойкость, помехоустойчивость шифра.[7]

Имитостойкость – способность противостоять активным атакам со стороны противника, целью которых является навязывание ложного или подмена передаваемого сообщения или хранимых данных.[8]

Помехоустойчивость шифра(noise stability of a cipher) –  способность шифра противостоять действию случайных помех (в отличие от целенаправленных действий противника), возникающих при передаче шифрованного сообщения по каналу связи.[8]  

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

Схема шифрования, шифрсистема (crypyosystem,cipher) –криптографическая система, предназначенная для защиты информации от лиц, не имеющих права доступа к ней. Защита обеспечивается путем зашифрования информации.[8]

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

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

Шифр перестановки(permutation cipher) – шифр, в котором шифрованный текст(сообщение) получается из открытого текста(сообщения) перестановкой блоков открытого текста(сообщения).[6]

Шифр гаммирования (keystream cipher) – шифр, в котором функция зашифрования осуществляет гаммирования.[7]

Шифр простой замены( substitution cipher) – шифр, в котором функция зашифрования состоит в замене блоков открытого текста(сообщения) блоками шифрованного текста( сообщения) в соответствии с ключом, представляющим собой подстановку на множестве блоков текста.[8]

Совершенный шифр(perfect cipher) – шифр, при использовании которого шифрованный текст не дает противнику, не знающему секретного ключа, никакой информации об открытом тексте, т.е. условное распределение на множестве открытых текстов при заданном шифрованном тексте совпадет с безусловным распределение на множестве открытых текстов.[2]

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

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

Коды Хемминга являются самоконтролирующимися кодами, то есть кодами, позволяющими автоматически обнаруживать наиболее вероятные ошибки при передачи данных. Для их построения достаточно приписать к каждому слову один добавочный( контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, чётным. Одиночная ошибка в каком – либо разряде передаваемого слова( в том числе, может быть и в контрольном разряде) изменит чётность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок. Не имеем возможности исправить её. Остаются незамеченными ошибки, возникающие одновременно в чётных количествах разрядов( маловероятны). Код Хемминга используется в некоторых прикладных программах в области хранения данных, позволяет легко исправлять однократные ошибки и обнаруживать двукратные ошибки.[17]

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

Например, кодовые слова 101 и 111 – соседние, так как отличаются только средним разрядом, а слова 101 и 110 – не соседние, так как у них отличаются два последних разряда. Изобразим все трехразрядные двоичные комбинации и соединим линией соседние кодовые слова. Тогда мы получим схему, как на рисунке 1. Минимальное кодовое расстояние между словами обычного, не помехоустойчивого кода равно единице.

Рисунок 1. Трехразрядные двоичные кодовые слова

В случае использования всех трехразрядных двоичных слов для передачи сообщений все они будут считаться допустимыми. Применим контроль по условию четности. Тогда допустимыми будут только выделенные рамками слова с четным числом единиц ( рисунок 2).

Рисунок 2. Допустимые трехразрядные кодовые слова при контроле по четности

Минимальное расстояние между допустимыми словами кода с контролем по четности равно двум (из рисунка 2 видно, что никакие два кодовых слова в рамочках не соединены линиями, то есть не являются соседними). Именно по этой причине одиночная ошибка в кодовом слове превращает это слово в недопустимое.

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

где n – общее число двоичных разрядов в блоке, а k – число контрольных разрядов.

Например, избыточность рассмотренного трехразрядного кода с контролем по четности составляет:

Избыточность является важной характеристикой кода, причем чрезмерное увеличение избыточности нежелательно. Важной задачей теории информации является синтез кодов с минимальной избыточностью, обеспечивающих заданную обнаруживающую и корректирующую способность. В качестве примера рассмотрим  код Хэмминга. Кодовое слово длиной n содержит k информационных и m контрольных разрядов. Коррекция искаженного i – го разряда заключается в сложении (по модулю 2) принятого кодового слова с вектором вида 0…010…0, содержащем единицу в i – ом разряде. Для n – разрядного кодового слова существует n таких векторов, соответствующих однократным ошибкам, и один нулевой вектор, соответствующий случаю приема слова без ошибок. Таким образом, m контрольных разрядов должны обеспечивать формирование n + 1 вектора ошибки, то есть должно выполняться неравенство . В результате получается (2m – 1, 2m – 1 – m)код, называемый кодом Хэмминга. Простейший нетривиальный случай, соответствующий m=3, образует (7,4) – код, который можно синтезировать следующим образом. Сопоставим каждому вектору ошибки порядковый номер – синдром ( таблица 1). При этом нулевому вектору ошибки соответствует нулевой синдром.

Рассчитаем избыточность (7,4) – кода Хэмминга:

Это очень большое значение. На практике часто применяются существенно более сложные коды, обеспечивающие лучшие характеристики помехоустойчивости при меньшей избыточности.[3]

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

Результат не изменится, если искажения будут выражаться в появлении лишних знаков в шифрованном тексте. Таким образом, сложные шифры (отличные от указанных выше простых шифров) распространяют искажения типа пропуска – вставки знаков в канале связи.[5]

1.2. Характеристика помехоустойчивых шифров

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

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

Помехоустойчивый код характеризуется тройкой чисел ( n, k, d0 ), где n – общее число разрядов в передаваемом сообщении, включая проверочные ( r ), k=n-r – число информационных разрядов, d0 – минимальное кодовое расстояние между разрешенными кодовыми комбинациями, определяемое как минимальное число различающихся бит в этих комбинациях. Число обнаруживаемых ( tо ) и (или) исправляемых ( tи ) ошибок (разрядов) связано с параметром d0 соотношениями:

,

,

.

Иногда используются дополнительные показатели избыточности, производные от приведенных выше характеристик n, k:  – относительная избыточность, – относительная скорость передачи.[16]

Систематические (линейные) коды имеют общее свойство – любая разрешенная комбинация может быть получена в результате линейных операций над линейно – независимыми векторами. Это способствует упрощению аппаратной и программной реализации данных кодов, повышает скорость выполнения необходимых операций. Простейшими систематическими кодами являются биты четности/нечетности. Они не позволяют обнаружить ошибки четной кратности  и поэтому используются при невысоких требованиях к верности принимаемых данных (или при малой вероятности ошибок в линии передачи). Примером может служить бит Parity (соответствие) в установках режимов работы последовательного порта с помощью команды MODE (MS DOS). Несмотря на ограниченные возможности обнаружения ошибок, биты четности / нечетности имеют большое значение в теории помехоустойчивого кодирования. Одни из первых математически обоснованных и практически использованных ранее для защиты информации в запоминающих устройствах помехоустойчивых кодов – коды Хэмминга представляют собой простую совокупность перекрестных проверок на четность/нечетность. Циклические коды могут рассматриваться как обобщенные проверки на четность/ нечетность.

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

Основные свойства и название циклических кодов связаны с тем, что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвига некоторого исходного кодового слова.[15]

Циклические коды задаются с помощью многочленов g(x) или их корней. Многочлен имеет вид:

,

где gi={0,1}, x=2. Кроме того, вводятся полином исходного сообщения:

,

и кодированного сообщения:

.

Для этих полиномов, представляющих собой по существу альтернативную запись чисел в двоичной системе счисления, определяются операции сложения, умножения и деления, необходимые для организации кодирования и декодирования сообщения. Все операции выполняются по модулю 2.[16]

Структура обратных связей полностью определяется ненулевыми коэффициентами порождающего полинома g(x). Для временного хранения информационной части сообщения с целью последующей ее передачи вместе с проверочными разрядами кодер, очевидно, должен быть дополнен сдвиговым регистром длиной в k разрядов, ключами и соответствующими цепями управления. Однако в целом аппаратурные затраты при реализации кодеров в случае циклических кодов невелики – общее число триггеров и элементов М2 (исключая регистр временного хранения информационной части сообщения) не превышает 2r и не зависит от длины информационной части сообщения. Двухвходовый элемент М2, на один из входов которого подается в последовательной форме сообщение, на выходе формирует бит четности или нечетности для этого сообщения. В результате циклический код, формируемый кодером – совокупностью обобщенных бит четности и нечетности, тип которых (четность или нечетность) не определен заранее и может динамически меняться от такта к такту.[17]

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

Перспективными с точки зрения аппаратурной реализации представляются коды БЧХ (коды Боуза – Чаудхури – Хоквингема), так же, как и коды Хэмминга, входящие в семейство циклических кодов. Коды БЧХ не слишком большой длины (примерно до n=1023) оптимальны или близки к оптимальным кодам, то есть обеспечивают максимальное значение d0 при минимальной избыточности. Эти коды уже нашли практическое применение в цифровых системах записи звука (речи, музыки), причем в варианте, предусматривающем исправление обнаруженных ошибок. Относительно невысокие частоты дискретизации звуковых сигналов (48 или 96 кГц) не препятствуют проведению дополнительных вычислений так жестко, как в случае высокоскоростных сетей.[16]

Модель шифра А= (X, II(K,f)) со следующими уравнениями зашифрования, расшифрования  у – тгх, х = я"1 у, ' хеХ, уеУ.

Здесь у – шифрованный текст; в последующем будет использовано обозначение Y для множества шифрованных текстов (Y = X); это делается для удобства различения открытых и шифрованных текстов.

Множество X – это множество текстов одной и той же длины L в некотором алфавите Q, X = QL.

Под искажением сообщения при его передаче по каналу связи понимается замена шифрованного сообщения у еУ на некоторое другое - у*, у*еУ*.  

Характер замены уеУ на у*е У* определяется физическим состоянием как самого канала связи, так и окружающей его среды, У< У*.

Примером искажений являются искажения типа замены. Передаваемое по каналу связи сообщение y=bi,b2,...,bL заменяется на сообщение у*=B\,B*29...9B\. Исказиться может любая буква bj сообщения у, при этом искажении она заменится на букву b'j.

Примерами других искажений являются искажения типа «пропуск», «вставка». Искажение типа пропуска букв состоит в том, что из сообщения y=bi,b2,b3,.:.,bL пропадут одна или несколько букв, стоящих на некоторых местах. Так при пропадании второй буквы B2 из канала связи на расшифрование придет сообщение у=BьBз,...,Bb длины L – 1. Искажение типа вставки состоит в добавлении одной или нескольких букв алфавита Q в сообщение у=BbB2,Bз,...,Bb.

При рассмотрении шенноновской модели шифра для указанных искажений может оказаться, что при некоторых п из n(K,f) и выражение я"1 у* может быть не определено. Это означает, что на приемной стороне сообщение у* не будет расшифровываться. В дальнейшем будем рассматривать лишь такие шифры и искажения, при которых для любого уeY преобразование 7c_1y* определено при всех 7cen(K,f).

Пусть на множестве X=Y задана некоторая метрика D.

По определению, это функция на ХхХ со свойствами:

1. D(x, xf) = 0 в том и только в том случае, когда х = х',х,х'еХ;
2. D(x,x') = D(x',x) для любых х,х'еХ; 
3.  £>(jt,jt') + D(x\x") > D(x,x") для любых х,х',х"еХ.

Примером метрики на X может служить расстояние Хэмминга .

Лемма 1. Если для любых у', у"е Y, п е П(К, f) справедливо:

D(7i-1yf;7i-1y^D(yf,y'f), то в(к-1у\к-1у")=и{у'У)для любых у', у" е Y, к е n(K,f).

ДОКАЗАТЕЛЬСТВО следует из очевидного равенства

X D^-y.ic-y)» X D(y',y"),У',У*€У        y',y'€Y или X [D^ – y^-y)-D(y',y")J=0

y'.y'Ey при любом л en(K,f).

Теорема (А.А. Марков). Любой шифр, не размножающий искажений в метрике Хэмминга, представим в виде композиции шифров многозначной замены и перестановки.[8]

Теорема. Взаимно однозначное преобразование X=fiL, не размножающее искажений типа замены в метрике Хэмминга, представляется в виде композиции перестановки (п^ j2#..jL ) и многозначной замены R на fiL.

Шифры, не размножающие искажений типа «пропуск»

Пусть множество открытых текстов в модели эндоморфного шифра A=(X,K,y,f), Х=У имеет следующий вид:X = (Jftk=QL,k=i то есть включает все слова над Алфавитом Q длины от 1 до L. Тогда искажение типа «пропуск» приводит к тому, что искаженный текст у* принадлежит У=Х (при естественном условии, что искажение не приводит к полному «уничтожению» слова, то есть к слову длины 0).

Шифры, не размножающие искажений типа «замены» в метрике р при X=QL, сохраняют это свойство и при X = QL (имея в виду использование указанных в теореме своих преобразований множества Qk при каждом к).[9]

Лемма 2. Содержание произвольного слова длины к > 3 однозначно определяет само слово.

Доказательство проводится индукцией по длине слова. При к=3 данное утверждение проверяется непосредственно. Оно справедливо для слов длины к < £. Пусть а = (а1...,а^+1) – произвольное слово длины £ +1. Если aj = а2 =... = , то справедливость утверждения очевидна. В противном случае, пусть j – наименьший номер, при котором aj F a j. Тогда, положив aj = а , слово а можно представить в виде (a,...,aj_1aj,aj+1,...,a^+1} aj F а. Во введенных обозначениях имеем c(a,...,a,aj,aJ+1,...,a^+1)= (a,...,a)c(aj,...,a^+1] [J((a,...,a) aj,...,a^+1), j>2.

Возможны три случая. Если j < £ –1, то по содержанию в 1 соответствии с допущением однозначно восстанавливается слово (aj,...,a^+1).

Для этого собираем все слова из множества C\a9a,...,a,aj,aj+1        j с началом а,а,...,а; нетрудно заметить, что «хвосты» у этих слов – одинаковы, и V        ' j–2 равны слову (aj,...,a^+1). Добавляем к этому слову j–1 раз букву а (в его начало), однозначно получаем слово (a,...,a,ajaj+1,...,a^+1). Лемма доказана.

Произвольное бинарное отношение 5 на множестве QL коммутирует с отношением 8, если для любых слов а, а', а", а" из QL из asaf,a5a",af5aw вытекает a"eaw. Любое отображение f: QL — QL может рассматриваться как некоторое отношение ф на QL, именно: аfа', а,а' е QL тогда и только тогда, когда f(а) = а'. В связи с этим можно говорить о коммутирумости отображения f : QL —> f2L с отношением 8, если f коммутирует с 8. Отображение не размножает искажений типа пропуск, если для любых у,у* е Y = ClL из условия уе^у*>

следует (fу)е^(fу ).[3]

3. Алгоритмы шифрования и дешифрования на основе помехоустойчивых шифров

Алгоритм шифрования и дешифрования на основе использования шифра Перестановки

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

Алгоритм - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.[4]

         Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи. (Холмогоров). [5]

Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату. (Марков).[6]

Различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований:

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

Другие формальные определения понятия алгоритма связаны с введением специальных математических конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча) и постулированием тезиса об эквивалентности такого формализма и понятия «алгоритм».

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий, при любом наборе исходных данных.[10]

Криптография — это наука о способах преобразования информации с целью ее защиты от незаконных пользователей. Методы решения противоположной задачи (взлом криптографической защиты) составляют предмет другой науки — криптоанализа. Вместе с тем, было бы неправильным разделять криптографию и криптоанализ. И криптография, и криптоанализ изучают одни и те же объекты, но с разных точек зрения. Поэтому они скорее являются двумя частями одной и той же науки (она называется «криптология»), а не независимыми дисциплинами. Изучать их тоже надо совместно, потому что невозможно серьезно заниматься криптографией (например, разрабатывать шифры), не изучив криптоанализ.[11]

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

 ПРИМЕР. Запишем фразу «это маршрутная перестановка» в прямоугольную таблицу размером 3×9, двигаясь по строкам, слева направо и пропуская пробелы (см. таблица 1).

Пример маршрутной перестановки

Таблица 1

Для зашифрования текста выпишем из этой таблицы буквы, двигаясь по столбцам сверху вниз: этттнаоанмяоапврекршареус. Из–за своей низкой стойкости, в современных криптографических системах шифры перестановки используются только как составная часть композиционных шифров.[6]

Алгоритм шифрования и дешифрования на основе использования шифра Замены

Простейшим из шифров замены является одно алфавитная подстановка, называемая также шифром простой замены. Ключом такого шифра является взаимно однозначное отображение (подстановка) F алфавита открытого текста (X) в алфавит шифр текста (Y): F: X↔Y. Зафиксируем нумерацию символов в алфавитах X и Y: X = {x1, x2, … xn}, Y = {y1, y2, … yn}. Тогда отображение F фактически задается перестановкой π порядка n = |X| = |Y|: при шифровании символ xi открытого текста заменяется на символ yπ(i) шифр текста. Эта перестановка может быть задана либо таблицей, либо с помощью формулы. При задании с помощью формулы значение π(i) представляется в виде выражения, зависящего от i.

 ПРИМЕР. Типичным примером шифра замены является шифр Цезаря. Этот шифр реализует следующее преобразование текста, записанного с помощью латинского алфавита: каждая буква открытого текста заменяется буквой, стоящей на три позиции позже нее в алфавите (при этом алфавит считается 15 записанным по кругу, то есть после буквы ‘z’ идет буква ‘a’). Например, открытый текст ‘secret’ будет преобразован в ‘vhfuhw’. Ключ для шифра Цезаря можно задать в виде следующей таблицы (см. таблица 2). В первой строке записаны буквы открытого текста, во второй — соответствующие им буквы шифртекста. 

Ключ для шифра Цезаря

Таблица 2

Шифр Цезаря можно описать и в виде формулы. Для этого пронумеруем буквы латинского алфавита числами от 0 до 25: a = 0, b = 1, …, z = 25. Тогда правило замены можно описать следующим образом: буква с номером i заменяется на букву с номером i+3 (mod 26), где операция ‘mod 26’ означает вычисление остатка от деления на 26. Разумеется, возможен обобщенный вариант шифра Цезаря, при котором буква с номером i заменяется на букву с номером i+k (mod 26). В этом случае ключом шифра является число k. Еще больше обобщив этот метод, мы придем к семейству аффинных шифров. Для алфавита из n символов {a1, a2, …, an} аффинным шифром называется процедура, заменяющая входной символ ai на символ aj, где j = k⋅i+l (mod n). Шифры простой замены в настоящее время не используются, поскольку их стойкость невелика. Методы взлома таких шифров основаны на анализе частотности отдельных символов и их комбинаций. Дело в том, что в любом языке различные буквы и комбинации из двух, трех или большего количества букв имеют характерные частоты повторений в текстах. Например, в текстах на русском языке чаще всего встречается буква ‘О’, затем, в порядке убывания частоты, идут 16 буквы ‘Е’ (считая, что ‘Е’ и ‘Ё’ — одна и та же буква), ‘А’, ‘И’, ‘Т’ и т.д. Для английского языка аналогичная последовательность самых частых букв: ‘E’, ‘T’, ‘A’, ‘I’, ‘N’. Самым частым символом в текстах является, однако, не буква, а символ пробела. При использовании шифра простой замены частота повторений зашифрованных символов в шифртексте совпадает с частотой повторений соответствующих исходных символов в открытом тексте. Это позволяет достаточно легко вскрыть такой шифр. Более тонкие характеристики (учет сочетаемости различных букв) позволяют даже автоматизировать процесс взлома. Для того чтобы увеличить стойкость шифров замены, применяют многоалфавитную замену. Процедура шифрования для многоалфавитной замены включает набор подстановок {π1, π2, …, πm} и функцию-распределитель ψ(k,i), задающую последовательность применения подстановок πi. При шифровании i – го символа открытого текста применяется подстановка с номером ψ(k,i), где k — ключ шифрования. Частным случаем многоалфавитной замены является шифр Виженера. Формально этот шифр можно описать следующим образом. В качестве ключа шифрования выберем набор из m целых чисел: k = (k1, k2, …, km). Процедуру преобразования открытого текста t = (t1, t2, …) в шифртекст c = (c1, c2, …) построим на основе обобщенного шифра Цезаря: c1 = t1 + k1 (mod 26), c2 = t2 + k2 (mod 26), и т.д. Когда будут использованы все m компонент ключа k, для шифрования (m+1) – й буквы снова возьмем k1, и т.д. Фактически, в качестве ключа шифрования используется бесконечная последовательность, образованная периодическим повторением исходного набора: k1, k2, …, km, k1, k2, …, km, k1, k2, … Такую последовательность принято называть гаммой. 17 Взломать шифр многоалфавитной замены немного сложнее, чем шифры простой замены, но тоже достаточно легко. Такой шифр на самом деле представляет собой одновременное применение m шифров простой замены (обобщенный шифр Цезаря), причем часть исходного текста, состоящая из букв ti, tm+i, t2m+i, … шифруются с использованием «ключа» ki (i=1, …, m). Если известен период гаммы (т.е. число m), то к каждой такой части можно применить любой из методов взлома шифров простой замены. Если период гаммы не известен, то задача усложняется. Но и для этих случаев разработаны эффективные методы взлома. Эти методы позволяют с достаточной вероятностью определить период гаммы, после чего задача сводится к взлому шифра гаммирования с известным периодом. Как было указано выше, основой для атак на шифры замены является анализ частот вхождений символов в шифртекст. Для того чтобы затруднить взлом шифра замены, можно попытаться скрыть частотные свойства исходного текста. Для этого надо, чтобы частоты появления разных символов в зашифрованном тексте совпадали. Такие шифры замены называются гомофоническими. Простейшим вариантом гомофонического шифра является следующий. Предположим, что нам известны частоты вхождений символов в открытый текст. Пусть fi — частота появления i –го символа в открытом текста (i — номер буквы в алфавите). Каждой букве ti исходного алфавита (т.е. алфавита, с помощью которого записывается открытое сообщение) сопоставим подмножество Fi, содержащее fi символов выходного алфавита (т.е. алфавита, с помощью которого записывается шифртекст), причем никакие два подмножества Fi и Fj не пересекаются. При шифровании будем заменять каждое вхождение символа ti на случайный символ из множества Fi. Ясно, что средняя частота появления в шифртексте 18 любого из символов выходного алфавита одинакова, что существенно затрудняет криптоанализ.[2]

Вывод по главе

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

Глава 2. Практические основы использования помехоустойчивых шифров в криптографии

2.1.Пример шифрования и дешифрования на основе использования шифра перестановки« Магический квадрат»

Изначально криптография изучала методы шифрования информации — обратимого преобразования открытого (исходного) текста на основе секретного алгоритма и/или ключа в шифрованный текст. Традиционная криптография образует раздел симметричных криптосистем, в которых зашифрование и расшифрование проводится с использованием одного и того же секретного ключа. Криптография включает в себя асимметричные криптосистемы, системы электронной цифровой подписи, хеш-функции, управление ключами, получение скрытой информации, квантовую криптографию, разные виды шифров. 

Шифр перестано́вки — это метод симметричного шифрования, в котором элементы исходного открытого текста меняют местами. Элементами текста могут быть отдельные символы, буквы и так далее. В классической криптографии шифры перестановки можно разделить на два класса:

• Шифры одинарной (простой) перестановки — при шифровании символы открытого текста перемещаются с исходных позиций в новые один раз.
• Шифры множественной (сложной) перестановки — при шифровании символы открытого текста перемещаются с исходных позиций в новые несколько раз.[15]

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

Шифрование по магическому квадрату производиться следующим образом. Буквы открытого текста вписываются последовательно в квадрат, причём позиция буквы в предложении соответствует номеру ячейки, в которую она ставится.[12]

Пример 1:

Зашифрованное: ЕОРАРРОМИАМВГИНП

Ответ: программирование

Пример 2:

Зашифрованное: ЫРНОАМАФРРОТТС

Ответ: трансформатор

Пример 3:

Зашифрованное: ИОРКНОИВЕАД

Ответ: кодирование

2.2.Пример шифрования и дешифрования на основе использования шифра Цезаря

Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами. [13]

Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом вправо на 3, А была бы заменена на Г, Б станет Д, и так далее.

Шифрование с использованием ключа . Буква «Е» «сдвигается» на три буквы вперёд и становится буквой «З». Твёрдый знак, перемещённый на три буквы вперёд, становится буквой «Э», буква «Я», перемещённая на три буквы вперёд, становится буквой «В», и так далее. 

Пример 1:

Исходный алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Шифрованный:

ГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВ

Оригинальный текст:

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

Шифрованный текст получается путём замены каждой буквы оригинального текста соответствующей буквой шифрованного алфавита:

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

Пример 2:

k= 7

Исходный алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Шифрованный:

ЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁ

Оригинальный текст:

« Как хорошо на улице зимой»

Шифрованный текст:

Сжс ьхчхях фж ътпэл опухр

Пример 3:

k= 11

Исходный алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Шифрованный:

КЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙ

Оригинальный текст:

«Скоро наступит лето и будут у нас каникулы»

Шифрованный текст:

Шсхчх фжшщъцпщ тлщх п зъкъщ ъ фжш сжфпсътв

2.3. Пример шифрования и дешифрования на основе использования шифра «криптосистема RSA»

Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложение, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других. [14]

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

Пример 1:

Алгоритм шифрования:

Исходное слово: пример

1. Два случайных числа p, q на выбор;

2. Найдите  n, перемножив числа p и q;

3. Найдите f(N);

4. Определите число e и число d;

5.Посчитайте по модулю и возведите в степень.

Алгоритм дешифрования:

Закодированное сообщение: пример

1. С помощью открытого ключа ( e, n= 9,85) возводите в 9 степень по модулю 85;

2. Каждой получившейся цифре( ее порядковому номеру) соответствует буква русского алфавита.

Пример 2:

Закодированное сообщение: лид

Дополнительные сведения:

n=15     e=7  µ(n)=8

2. Алгоритм шифрования.

Исходное слово: гид

1.Запишем алфавит и номер каждой буквы

 Номер буквы не должен быть больше n.

2.Начинаем вычислять по формуле слово ГИД
     p-номер буквы

• Буква Г

2187 mod 15  =12 (12-Номер буквы Л)

• Буква И

4782969  mod 15 =9 (9-Номер буквы И)

• Буква Д

16384 mod 15 = 4 (4-Номер буквы Д)

3.Записываем получившееся зашифрованное слово: ЛИД.

3. Алгоритм дешифрования.

Закодированное сообщение: ЛИД

1.Запишем алфавит и номер каждой буквы

2.Начинаем вычислять по формуле d
 e·d mod µ(n)=1

7d mod 8 = 1

D=7

3.Начинаем дешифровать слово ЛИД по каждой букве по формуле

• Буква Л

35831808 mod 15 = 3 (3-Номер буквы Г )

• Буква И

4782969  mod 15 =9 (9-Номер буквы И)

• Буква Д

16384 mod 15 = 4 (4-Номер буквы Д)

4.Записывем дешифрованное слово:ГИД

Пример 3:

Даны простые числа:

Р= 3

q= 5

Модуль:

n= p*q= 2*5=10

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

f=(p–1)*(q–1)=(2–1)*(5–1)=1*4=4

e=3, d=7

(d*e–f*q=1)

Секретный ключ:

{d, n}={7, 10}

Шифрование:

Ваше сообщение- число 7, P=7

Открытый ключ: {e, n}= {3, 10}

Закодированные данные:

E=3

Дешифрование:

Получено E=3, имеется закрытый ключ {d, n}={7, 10}

Открытый ключ не может расшифровать сообщение.

–  зашифрованное сообщение.

Вывод по главе

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

Заключение

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

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

Шифрование - это способ изменения сообщения или другого документа обеспечивающее искажение (сокрытие) его содержимого.

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

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

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

Список литературы

1. Информатика: Учеб. Пособие для студ. Пед.. вузов/А. В. Могилёв, Н. И. Пак, Е. К. Хеннер; Под ред. Е. К. Хеннера.- 2-е изд., стер.- М.: Изд. Центр «Академия», 2001.
2. Криптография Бабаш А. В., Шанкин Г.П., 2007
3. Теория кодирования и теория информации, Р. В. Хемминг
4. Информатика: Учебник/ Под ред. Проф. Макаровой. 3- е изд., М.: Финансы и статистика, 2001.
5. Информатика. Базовый курс/ С. В. Симонович и др. СПб.: Питер 2001.
6. Проблематика и методы криптографии / Н.А. Молдовян. - СПб. : Изд-во С.-Петерб. ун-та, 1998.
7. Криптография [Text] / Молдовян А.А. - СПб. : Лань, 2001. - 224 с.
8. Муттер В. М. « Основы помехоустойчивой телепередачи информации»
9. Туркин А. И. « Реккурентный приём сложных сигналов
10.  Аверченков, В. И Криптографические методы защиты информации/ В. В. Аверченков, М. Ю. Рытов, С. А. Шпичак,– Брянск БГТУ, 2010–( Серия « Организация и технология защиты информации»).
11.  Мафтин С. Механизмы защиты в сетях ЭВМ. – М.: Мир, 1993.
12. https://goo.gl/DcZ8eJ
13. https://goo.gl/EovI27
14. https://goo.gl/0i2KaJ
15. https://goo.gl/wVVrRR
16. http://goo.gl/niRLzR
17. http://goo.gl/9eKKJl