Домашинные методы шифрования

СОДЕРЖАНИЕ

История шифрования 1

Шифры замены 2

Шифр Цезаря 2

Шифр Цезаря с ключевым словом 3

Аффинная криптосистема 3

Шифр Полибия 3

Методы вскрытия одноалфавитных систем 3

Частотный анализ 4

Метод полосок 4

Многоалфавитные системы 4

Шифр Вернама 5

Шифр Виженера 6

Шифр c автоключом 6

Шифры перестановки 6

Простой столбцевой перестановочный шифр 6

Перестановочный шифр с ключевым словом 7

Вывод 7

Комбинированное использование шифра перестановки и замены 7

S’=Pt + g (1.8) 7

Ni+1 = (K Ni + M) mod L (1.12) 7

Шифровальная машина «Энигма» 8

История шифрования

Хотя никто не знает, когда появилась тайнопись, но глиняная табличка, сделанная приблизительно 1500 лет до нашей эры, содержит один из самых ранних ее примеров. Она содержит закодированную формулу изготовления глазури для покрытия сосудов. Греки применяли коды по крайней мере с 475 года до нашей эры, а высшие слои в Риме использовали простые шифры в период царствования Юлия Цезаря. В начале нашей эры интерес к криптографии (также, как и к другим интеллектуальным занятиям) упал; единственными, кто иногда применял ее, были монахи.

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

В ХIX веке два фактора способствовали развитию криптографии. Первым фактором были истории Эдгара Алана По такие, как "Золотой жук", в которых фигурируют закодированные сообщения и которые волновали воображение многих читателей. Вторым фактором явилось изобретение телеграфа и азбуки Морзе. Азбука Морзе была первым двоичным представлением (точка и тире) алфавита, которое получило широкое распространение.

В 1918 году Эдвард Х. Хеберн из Окленда (Калифорния) получил патент на роторную машину, которая была ведущим криптографическим изобретением еще 50 лет.

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

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

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

конфиденциальности передаваемых/хранимых данных
аутентификации
целостности хранимых и передаваемых данных
обеспечения подлинности документов

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

Шифры замены

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

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

В классической криптографии различают 4 разновидности шифров замены:

Простая замена, или одноалфавитный шифр. Каждая буква открытого текста заменяется на один и тот же символ шифртекста.
Омофонная замена. Аналогична простой замене с единственным отличием: каждой букве открытого текста ставятся в соответствие несколько символов шифртекста. Например, буква "А" заменяется на цифру 5, 13, 25 или 57 , а буква "Б" — на 7, 19, 31 или 43 и так далее.
Блочная замена. Шифрование открытого текста производится блоками. Например, блоку "АБА" может соответствовать "РТК", а блоку "АББ" — "СЛЛ".
Многоалфавитная замена. Состоит из нескольких шифров простой замены. Например, могут использоваться пять шифров простой замены, а какой из них конкретно применяется для шифрования данной буквы открытого текста, — зависит от ее положения в тексте.

Примером шифра простой замены может служить программа ROT13, которую обычно можно найти в операционной системе UNIX. С ее помощью буква "А" открытого текста на английском языке заменяется на букву "N", "В" — на "О" и так далее. Таким образом, ROT13 циклически сдвигает каждую букву английского алфавита на 13 позиций вправо. Чтобы получить исходный открытый текст надо применить функцию шифрования ROT 13 дважды:

Р = ROT13(ROT13(P)) (1.1)

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

Шифр Цезаря

Юлий Цезарь повествует о посылке зашифрованного сообщения Цицерону. Используемая при этом система подстановок была одноалфавитной, но не являлась системой Цезаря: латинские буквы заменялись на греческие способом, который не был ясен из рассказа Цезаря. Информация о том, что Цезарь действительно использовал систем у Цезаря, пришла от Светония.

В шифре Цезаря каждая буква замещается на букву, находящуюся k символами правее по модулю равному количеству букв в алфавите. (Согласно Светонию у Цезаря k=3 n=50)

C_k(j)=(j+k)(mod n), n - количество букв в алфавите (1.2)

Очевидно, что обратной подстановкой является:

C_k^-1(j)=С_n-k=(j+n-k)(mod n) (1.3)

Шифр Цезаря с ключевым словом

В данной разновидности шифра Цезаря ключ задается числом k (0<=k<=n-1) и коротким ключевым словом или предложением. Выписывается алфавит, а под ним, начиная с k-й позиции, ключевое слово. Оставшиеся буквы записываются в алфавитном порядке после ключевого слова. В итоге мы получаем подстановку для каждой буквы. Требование, чтобы все буквы ключевого слова были различными не обязательно - можно записывать ключевое слово без повторения одинаковых букв.

Аффинная криптосистема

Обобщением системы Цезаря является аффинная криптосистема. Она определяется двум числами a и b, где 0<=a, b<=n-1. n - как и раньше, является мощностью алфавита. Числа a и n должны быть взаимно просты.

Соответствующими заменами являются:

A_a,b(j)=(a*j+b)(mod n) (1.4)

A^-1_a,b(j)=(j-b)*a^-1(mod n) (1.5)

Обратную замену также можно получить, просто поменяв местами строки в таблице замен.

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

Шифр Полибия

Система Цезаря не является старейшей. Возможно , что наиболее древней из известных является система греческого историка Полибия, умершего за 30 лет до рождения Цезаря. Его суть состоит в следующем: рассмотрим прямоугольник, часто называемый доской Полибия.

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

Каждая буква может быть представлена парой букв, указывающих строку и столбец, в которых расположена данная буква. Так представления букв В, Г, П, У будут АВ, АГ, ВГ, ГБ соответственно.

Методы вскрытия одноалфавитных систем

При своей простоте в реализации одноалфавитные системы легко уязвимы. Определим количество различных систем в аффинной системе. Каждый ключ полностью определен парой целых чисел a и b, задающих отображение ax+b. Для а существует j(n) возможных значений, где j(n) - функция Эйлера, возвращающая количество взаимно простых чисел с n, и n значений для b, которые могут быть использованы независимо от a, за исключением тождественного отображения (a=1 b=0), которое мы рассматривать не будем. Таким образом получается j(n)*n-1 возможных значений, что не так уж и много: при n=33 в качестве a могут быть 20 значений( 1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32), тогда общее число ключей равно 20*33-1=659. Перебор такого количества ключей не составит труда при использовании компьютера. Но существуют методы упрощающие этот поиск и которые могут быть использованы при анализе более сложных шифров.

Частотный анализ

Одним из таких методов является частотный анализ. Распределение букв в криптотексте сравнивается с распределением букв в алфавите исходного сообщения. Буквы с наибольшей частотой в криптотексте заменяются на букву с наибольшей частотой из алфавита. Вероятность успешного вскрытия повышается с увеличением длины криптотекста. Существуют множество различных таблиц о распределении букв в том или ином языке, но ни одна из них не содержит окончательной информации - даже порядок букв может отличаться в различных таблицах. Распределение букв очень сильно зависит от типа теста: проза, разговорный язык, технический язык и т.п. В методических указаниях к лабораторной работе приведены частотные характеристики для различных языков, из которых ясно, что буквы буквы I, N, S, E, A (И, Н, С, Е, А) появляются в высокочастотном классе каждого языка.

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

Метод полосок

Для шифра Цезаря имеется более простой способ расшифровки - так называемый метод полосок. На каждую полоску наносятся по порядку все буквы алфавита. В криптограмме берется некоторое слово. Полоски прикладываются друг к другу так, чтобы образовать данное слово. Двигаясь вдоль полосок находится осмысленное словосочетание, которое и служит расшифровкой данного слова, одновременно находится и величина сдвига (Рис. 1.1).

Рисунок 1.1. – Метод полосок.

Многоалфавитные системы

Полиалфавитные подстановочные шифры были изобретены Лином Баттистой (Lean Battista) в 1568 году. Основная идея многоалфавитных систем состоит в том, что на протяжении всего текста одна и та же буква может быть зашифрована по-разному. Т.е. замены для буквы выбираются из многих алфавитов в зависимости от положения в тексте. Это является хорошей защитой от простого подсчета частот, так как не существует единой маскировки для каждой буквы в криптотексте. В данных шифрах используются множественные однобуквенные ключи, каждый из которых используется для шифрования одного символа открытого текста. Первым ключом шифруется первый символ открытого текста, вторым - второй, и т.д. После использования всех ключей они повторяются циклически.

Шифр Вернама

Шифр Вернама, или одноразовый блокнот, был изобретен в 1917 году Мейджором Джозефом Моборном (Major Joseph Mauborn) и Гильбертом Вернамом (Gilbert Vernam) из AT&T (American Telephone & Telegraph). В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом. Первоначально это была одноразовая лента для телетайпов. Отправитель использовал каждый символ ключа для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю n (мощность алфавита) символа открытого текста и символа ключа из одноразового блокнота. Каждый символ ключа используется только один раз и для единственного сообщения, иначе даже если использовать блокнот размером в несколько гигабайт, при получении криптоаналитиком нескольких текстов с перекрывающимися ключами он сможет восстановить исходный текст. Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции. если шифротексты смещены правильно, соотношение совпадений резко возрастет. С этой точки зрения криптоанализ не составит труда. Если же ключ не повторяется и случаен, то криптоаналитик, перехватывает он тексты или нет, всегда имеет одинаковые знания. Случайная ключевая последовательность, сложенная с неслучайным открытым текстом, дает совершенно случайный криптотекст, и никакие вычислительные мощности не смогут это изменить.

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

Рисунок 1.2. – Схема одноразового блокнота.

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

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

Шифр Виженера

Одной из старейших и наиболее известных многоалфавитных криптосистем является система Виженера, названная в честь французского криптографа Блейза Виженера(Vigenere). Этот метод был впервые опубликован в 1586 году. В данном шифре ключ задается набором из d букв. Такие наборы подписываются с повторением под сообщением, а, затем, полученную последовательность складывают с открытым текстом по модулю n (мощность алфавита). Т.е. получается следующая формула:

Vig_d(m_i)=(m_i+k_{i mod d})(mod n) (1.6)

В обоих случаях обратная подстановка легко определяется из квадрата, или по формулам

Vig_d^-1(m_i)=(m_i-k_{i mod d})(mod n) (1.7)

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

Шифр c автоключом

Дальнейшей модификацией системы Виженера является система шифров с автоключом(auto-key), приписываемая математику XVIв. Дж. Кардано, AUTOCLAVE. Шифрование начинается с помощью "первичного ключа" (который является настоящим ключом в нашем смысле) и продолжается с помощью сообщения или криптограммы, смещенной на длину первичного ключа, затем производится сложение по модулю, равному мощности алфавита. Например:

Сообщение П Р И В Е Т П Р И М А Т У

Первичный ключ В Г Т У

Автоключ П Р И В Е Т П Р И

Шифротекст С У Ъ Х Ф В Ч Т Н Ю П В Ы

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

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

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

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

Простой столбцевой перестановочный шифр

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

Перестановочный шифр с ключевым словом

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

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

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

Вывод

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

Комбинированное использование шифра перестановки и замены

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

1. Перестановка может делаться до наложения на сообщение случайной последовательности g:

S’=Pt + g (1.8)

В случае если текст в сообщении отсутствует, то в канал связи попадет чистый ключ:

t = 0; S' = P 0 + g = g (1.9)

2. Перестановка может делаться после наложения на сообщение случайной последовательности:

S' = P (t + g ) (1.10)

В случае если текст отсутствует, в канал связи поступает ключ, шифрованный перестановкой:

t = 0; S' = P (0 + g ) = P g (1.11)

Обычно предпочтение отдается второй схеме.

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

Существует множество вычислительных способов перестановок. Например, широко применяется перестановка по номерам N от 0 до L-1 на основе рекуррентного соотношения:

Ni+1 = (K Ni + M) mod L (1.12)

при выполнении следующих условий:

1) K и M берутся из интервала [1, L-1];

2) M взаимно просто с L;

3) K-1 делится на любой простой делитель L;

4) K-1 делится на 4, если L делится на 4.

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

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

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

Шифровальная машина «Энигма»

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

Первоначально «Энигма» состояла из 4 барабанов. С каждой стороны барабана находилось по 25 контактов, соответствовавших буквам алфавита и случайным образом соединенных проводами. Электрический импульс, обозначавший букву алфавита, таким образом, проходил через все четыре барабана, что приводило к 8-ми кратной замене. Кроме того, после каждого символа, все барабаны поворачивались что обеспечивало длину ключа гораздо большую длины сообщения. Ключ вводили, устанавливая барабаны в определенном порядке. И если в годы Первой мировой войны, «Энигма» так и не нашла широкого применения, то во Вторую мировую она стала значительным препятствием для союзников, с трудом вскрывавших ее шифры.

Для того, чтобы эффективно взламывать шифры «Энигмы», необходимо было знать распайку проводов внутри каждого барабана (вскрыть шифр «Энигмы» теоретически возможно и без этого, но тогда замен становится не 4, а 8, и шифр уже нельзя вскрыть вручную в течении достаточно короткого времени), поэтому, необходимо было достать образец самой машины. Барабаны в каждой машине были стандартными, для того, чтобы обеспечить дешифровку сообщения, поэтому с началом войны британская разведка развернула настоящую охоту за образцами «Энигмы», не прекращавшуюся до конца войны (так как немцы периодически меняли распайку проводов в барабанах). Первый образец этой машины, вместе с чертежами был похищен польской разведкой еще в 1939 году прямо с завода, и вскоре передан британским спецслужбам. Вторую сняли с борта сбитого над Норвегией немецкого бомбардировщика в 1940. В дальнейшем британские спецслужбы начали настоящую охоту за немецкими подводными лодками с единственной целью снять с них образец этой шифровальной машины.

Но даже имея образец этой машины необходимо было взломать шифр 4-хкратной замены, определявшийся положением барабанов. Это представляло почти непреодолимую трудность до тех пор, пока в 1942 году в Англии не начала функционировать первая ЭВМ «Колосс», специально созданная для взлома немецких шифров и справлявшаяся с «Энигмой» за полтора часа, хотя это относилось лишь к армейским «полевым» шифрам, в то время как большинство дипломатических и наиболее важные военные сообщения шифровались с помощью более сложных моделей «Энигм», имевших по 6 барабанов, и ни одна из них не попала в руки союзников. Следует отметить и тот факт, что сами немцы не считали «Энигму» неуязвимой и многократно ведущие немецкие криптоаналитики, не зная заранее даже расположения проводов в барабанах, вручную взламывали ее шифры.

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

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

Blog