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

ДОМАШИННЫЕ МЕТОДЫ ШИФРОВАНИЯ

 

СОДЕРЖАНИЕ

 

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

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

Шифр Цезаря. 2

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

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

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

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

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

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

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

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

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

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

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

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

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

Вывод. 7

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

 

 

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

Хотя никто не знает, когда появилась тайнопись, но глиняная табличка, сделанная приблизительно 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)

 

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

Обобщением системы Цезаря является аффинная криптосистема. Она определяется двум числами 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 лет до рождения Цезаря. Его суть состоит в следующем: рассмотрим прямоугольник, часто называемый доской Полибия.

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

 

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

 

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

Одним из таких методов является частотный анализ. Распределение букв в криптотексте сравнивается с распределением букв в алфавите исходного сообщения. Буквы с наибольшей частотой в криптотексте заменяются на букву с наибольшей частотой из алфавита. Вероятность успешного вскрытия повышается с увеличением длины криптотекста. Существуют множество различных таблиц о распределении букв в том или ином языке, но ни одна из них не содержит окончательной информации - даже порядок букв может отличаться в различных таблицах. Распределение букв очень сильно зависит от типа теста: проза, разговорный язык, технический язык и т.п. В методических указаниях к лабораторной работе приведены частотные характеристики для различных языков, из которых ясно, что буквы буквы 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. Шифрование начинается с помощью "первичного ключа" (который является настоящим ключом в нашем смысле) и продолжается с помощью сообщения или криптограммы, смещенной на длину первичного ключа, затем производится сложение по модулю, равному мощности алфавита. Например:

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

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

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

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

 

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

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

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

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

 

Вывод

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

 

 

ДОМАШИННЫЕ МЕТОДЫ ШИФРОВАНИЯ

 

СОДЕРЖАНИЕ

 

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

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

Шифр Цезаря. 2

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

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

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

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

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

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

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

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

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

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

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

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

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

Вывод. 7

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

 

 

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

Хотя никто не знает, когда появилась тайнопись, но глиняная табличка, сделанная приблизительно 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)