No Image

Шифры с ключевым словом

0 просмотров
22 января 2020

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

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

Суть алгоритма шифрования проста. Шифр Виженера — это последовательность шифров Цезаря с различными значениями сдвига (ROTX — см. Шифр Цезаря). То есть к первой букве текста применяется преобразование, например, ROT5, ко второй, например, ROT17, и так далее. Последовательность применяемых преобразований определяется ключевой фразой, в которой каждая буква слова обозначает требуемый сдвиг, например, фраза ГДЕ ОН задает такую последовательность шифров Цезаря: ROT3-ROT4-ROT5-ROT15-ROT14, которая повторяется, пока не будет зашифрован весь текст сообщения.

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

Еще там можно прочитать про вариант шифра с бегущим ключом (running key), который был когда-то был невзламываемым. Этот вариант заключается в использовании в качестве ключа блока текста, равного по длине исходному тексту. Впрочем, и этот вариант, как оказалось, успешно поддается взлому. Проблема с бегущим ключом шифра Виженера состоит в том, что криптоаналитик имеет статистическую информацию о ключе (учитывая, что блок текста написан на известном языке) и эта информация будет отражаться в шифрованном тексте. Если ключ действительно случайный, его длина равна длине сообщения и он использовался единожды, то шифр Виженера теоретически будет невзламываемым, но такие системы уже относятся к классу систем одноразового кода, или одноразового шифр-блокнота (one-time pad). Они действительно не поддаются взлому, однако их практическое применение довольно затруднительно.

Основные сведения

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

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

Базовым понятием криптографии является шифр [1]. Шифр – совокупность инъективных (обратимых) преобразований множества элементов открытого текста на множество элементов шифротекста, проиндексированных элементами из множества ключей:

где XÎX –кодируемое сообщение из множества открытых текстов;

SÎS –шифротекст из множества возможных закодированных текстов;

k – ключ шифрования;

F – отображение, выполняемое шифром.

Свойство инъективности шифра означает, что существует отображение F -1 такое, что

Процесс преобразования открытого текста (передаваемого сообщения) в шифротекст называется шифрованием. Обратное преобразование шифротекста в открытый текст называется дешифрованием. Классификацию шифров по различным признакам можно посмотреть в [2].

Криптоанализ – наука (и практика ее применения) о методах и способах вскрытия шифров. Под вскрытием понимается задача получения по известному шифротексту соответствующего открытого текста и/или ключа шифрования.

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

Шифр Цезаря.

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

Ck(j)=(j+k)(mod n), где j – порядковый номер буквы в алфавите, Ck(j) – порядковый номер замещающей буквы, n – мощность входного алфавита (количество букв в используемом алфавите).

Таким образом, ключом шифрования здесь является число k, определяющее размер смещения.

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

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

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

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

В данной разновидности шифра Цезаря ключ задается числом k (0 -1 a,b(j)=(j-b+n)*a -1 (mod n)

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

Читайте также:  Сяоми ми нот 3 камера

Шифр Цезаря и аффинная криптосистема относятся к классу одноалфавитных криптосистем, то есть для выбранного ключа некоторая буква исходного открытого текста всегда будет заменяться одной и той же буквой в шифротексте. Поэтому данные шифры могут быть вскрыты методом частотного криптоанализа. Частотный анализ использует то свойство зашифрованного текста, что частота встречаемости символов в нем совпадает с частотой встречаемости соответствующих символов в открытом тексте. Если же учесть, что частоты встречаемости различных символов в текстах соответствующего языка распределены неравномерно (так, например, относительная частота встречаемости буквы «А» в текстах на русском языке составляет 0.069, а буквы «Ф» 0.003), то, подсчитав относительную частоту встречаемости букв в шифротексте, можно предположить, что символ, наиболее часто встречающийся в шифротексте, соответствует символу, наиболее часто встречающемуся в текстах на соответствующем языке, и найти таким образом ключ k для шифра Цезаря. Для вскрытия параметров a и b аффинной криптосистемы потребуется найти соответствие двух букв – наиболее часто встречающейся в шифротексте и второй по частоте. Эффективность частотного анализа шифра Цезаря с ключевым словом во многом зависит от длины используемой ключевой фразы, общее же количество допустимых отражений алфавита равно, как уже упоминалось, n!.

Квадрат Полибия

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

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

В такой прямоугольник записывается алфавит, причем схема записи держится в тайне и составляет ключ шифрования. Для того чтобы получались приближенные к квадрату матрицы (6х6, 5х7, 6х5), в алфавит могут включаться знаки препинания или исключаться редко используемые символы (такие как ‘ё’, ‘й’).

В процессе шифрования каждая буква открытого текста представляется в шифротексте парой букв, указывающих строку и столбец, в которых расположена данная буква. Так представлениями букв В, Г, П, У будут АВ, АГ, ВВ, ГА соответственно. Если использовать приведенный выше квадрат в качестве ключа шифрования, то фраза «ПРИМЕР ШИФРОВАНИЯ» будет зашифрована в

«ВВВГБВБЕАЕВГЕБГЕБВГБВГВБАВААВАБВЕА». В приведенном примере размер шифротекста превышает размер исходного текста в 2 раза, однако при машинной реализации номера строки и столбца таблицы можно задавать в виде цифр, а, учитывая, что получившийся квадрат имеет по 6 строк и столбцов, для кодирования каждой буквы будет достаточно 6 бит (3 для номера строки, 3 для номера столбца).

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

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

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

где mi, ki, Vigd(mi)- порядковые номера в алфавите очередных символов открытого текста, ключа и шифротекста соответственно. Обратное преобразование выглядит следующим образом:

Пример использования шифра Виженера приведен на рис.2 (алфавит дополнен пробелом, порядковый номер которого принят за 34, соответственно, мощность алфавита n=34).

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

В середине XIX века немецкий математик Казиски предложил определять длину парольной фразы по расстоянию между одинаковыми фрагментами шифротекста. Допустим, найдены два одинаковых фрагмента шифротекста, расстояние между которыми составляет 20 символов. Это может означать, что два одинаковых фрагмента открытого текста были зашифрованы с одной и той же позиции ключа. Это позволяет предположить, что парольная фраза имеет длину 4, 5, 10 или 20 символов. Узнав (или угадав) длину парольной фразы l, можно осуществить частотный криптоанализ шифротекста для выборки каждого l –го символа шифротекста.

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

где ki, li, . si – символы различных парольных фраз. Для повышения криптостойкости парольные фразы должны иметь различные взаимно простые периоды dk, dl, . ds. Это существенно затруднит для криптоаналитика поиск величины периода повторения общей парольной фразы, которая будет равна произведению длин всех парольных фраз.

Шифр Гронсфельда.

Идея шифра Виженера (использование многоалфавитной подстановки), используется в шифре Гронсфельда. Он использует в качестве ключа целое число. Каждая цифра в десятичной записи этого числа означает величину сдвига заменяющего алфавита при подстановке соответствующей буква открытого текста. Если K – ключ, d – количество цифр в нем, а Ki – i-я десятичная цифра ключа, то шифрование можно представить следующим образом:

Читайте также:  Упп 2 2с отзывы

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

Шифрование биграммами.

В начале XVI века аббат из Германии Иоганн Трисемус предложил шифровать по две буквы за раз [3]. Шифры, использующие подобный принцип, были названы биграммными. Обычно такие шифры используют таблицы, аналогичные квадрату Полибия, заполненные символами используемого алфавита. Наиболее известный шифр биграммами называется Playfair. Он применялся Великобританией в Первую мировую войну. Открытый текст разбивался на пары букв (биграммы) и текст шифровки строился из него по следующим трём очень простым правилам (рис.3).

1. Если обе буквы биграммы исходного текста принадлежат одной колонке таблицы, то буквами шифра считаются буквы, которые лежат под ними. Так биграмма ИН дает текст шифровки НЗ. Если буква открытого текста находится в нижнем ряду, то для шифра берется соответствующая буква из верхнего ряда и биграмма НЯ дает шифр ЗИ. (Биграмма из одной буквы или пары одинаковых букв тоже подчиняется этому правилу, и текст ОО дает шифр ГГ).
2. Если обе буквы биграммы исходного текста принадлежат одной строке таблицы, то буквами шифра считаются буквы, которые лежат справа от них. Так биграмма АБ дает текст шифровки НГ. Если буква открытого текста находится в крайней правой колонке, то для шифра берется буква из крайней левой колонки той же строки и биграмма АД дает шифр НА.

3. Если обе буквы биграммы открытого текста лежат в разных рядах и колонках, то вместо них берутся такие две буквы, чтобы вся их четверка представляла прямоугольник. Например, биграмма ЕК шифруется как БЙ (КЕ зашифруется ЙБ).

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

Шифрование биграммами с двойным квадратом.

В 1854 году англичанин Чарльз Уитстон разработал новую шифровку биграммами, которую называют двойной квадрат. Шифрование здесь происходит аналогично шифру Playfair, но биграммы шифруются по двум таблицам, случайным образом заполненных алфавитами. Для пары символов из исходного сообщения строится прямоугольник в двух таблицах по правилу – первая буква в левой таблице является одним углом, вторая в правой – другим. Буквы биграммы шифра берутся из двух оставшихся вершин прямоугольника. Если обе буквы лежат в одних и тех же строках, то буквы шифра берут из той же строки, но в следующем столбце таблицы (для последнего столбца – из первого столбца). Пример шифрования методом биграмм с двойным квадратом приведен на рис. 4.

Криптостойкость биграммных методом существенно выше, чем у методов простой замены (метод биграмм с двойным квадратом использовался военными еще во времена Второй мировой войны). Частотный анализ здесь можно применить только для оценки частоты встречаемости тех или иных буквосочетаний. И хотя анализ показывает, что какие-то биграммы встречаются в текстах на заданном языке чаще других, большое количество биграмм (а их насчитывается 1089 только для букв русского языка) не позволяет выявить соответствие биграмм открытого и закрытого текста. Криптоаналитику остается только перебирать все возможные варианты расположения символов в таблице (n! различных вариантов).

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

Рассмотрим алгоритмы перестановочного типа. В XVI веке итальянский математик и философ Дж. Кардано предложил новый тип шифра, основанный на очень простой и в то же время надежной перестановке букв открытого текста. Для шифрования он преложил использовать квадрат с прорезанными в нем несколькими ячейками. Ячейки прорезались таким образом, чтобы при повороте квадрата на 90, 180 и 270 градусов в прорезях поочередно появлялись все позиции исходного квадрата, причем по одному разу. Шифр получил название квадрата Кардано, пример квадратов 4х4 и 5х5 приведен на рис. 5.

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

Для дешифрации сообщения необходимо иметь точную копию квадрата, использовавшегося при шифровании (расположение прорезей на квадрате и составляет ключ). Количество различных вариантов расположения прорезей в квадрате NxN равно , что для квадрата 6х6 дает 262144 варианта (эквивалент 18 битного ключа) [4]. Однако, данный шифр (как впрочем, все перестановочные) ослабляет то, что при криптоанализе можно использовать особенности фонетики национального языка (наиболее часто встречающиеся или недопустимые для данного языка комбинации символов, средняя длина слов и т.п.).

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

Буквы ключевого слова без повторений записываются в первую строку таблицы, определяя таким образом количество ее столбцов. Буквы сообщения записываются в таблицу построчно. Сформированная таким образом таблица сортируется по столбцам, критерием сортировки является порядок следования символа первой строки в алфавите. После сортировки шифрованный текст переписывается по столбцам (рис 7).

Читайте также:  Телефон ксиаоми ми 2 лайт

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

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

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

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

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

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

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

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

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

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

· целостности хранимых и передаваемых данных

· обеспечения подлинности документов

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

Шифры замены

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

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

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

· Простая замена, или одноалфавитный шифр. Каждая буква открытого текста заменяется на один и тот же символ шифртекста.

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

· Блочная замена. Шифрование открытого текста производится блоками. Например, блоку "АБА" может соответствовать "РТК", а блоку "АББ" — "СЛЛ".

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

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

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

Шифр Цезаря

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

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

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

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

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

В данной разновидности шифра Цезаря ключ задается числом k (0

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась – это был конец пары: "Что-то тут концом пахнет". 8526 – | 8113 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Комментировать
0 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock detector