МУ_МСЗКИ

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

ГП ДУ ОВ ДЛ НУ ПД ДР ЦЫ ГА ЧТ

При расшифровании применяется обратный порядок действий.

Следует отметить, что шифрование биграммами резко повышает стойкость шифров к вскрытию. Хотя книга И.Трисемуса "Полиграфия" была относительно доступной, описанные в ней идеи получили признание лишь спустя три столетия. По всей вероятности, это было обусловлено плохой осведомленностью криптографов о работах богослова и библиофила Трисемуса в области криптографии.

Системаомофонов

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

Данные о распределениях вероятностей букв в русском тексте приведены в таблице. Буквы в таблицах указаны в порядке убывания вероятности их появления в тексте. Например, русская буква Е встречается в 36 раз чаще, чем буква Ф, а английская буква Е встречается в 123 раза чаще, чем буква Z.

Шифруя букву исходного сообщения, выбирают случайным образом одну из ее замен. Замены (часто называемые омофонами) могут быть представлены трехразрядными числами от 000 до 999. Например, в английском алфавите букве Е присваиваются 123 случайных номера, буквам В и G - по 16 номеров, а буквам J и Z - по 1 номеру. Если омофоны (замены) присваиваются случайным образом различные появления одной и той же буквы, тогда каждый омофон появляется в щифртексте равномерно.

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

Распределение вероятностей букв в русских текстах

ШИФРЫ СЛОЖНОЙ ЗАМЕНЫ

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

При r-алфавитной подстановке символ хо исходного сообщения заменяется символом уо из алфавита Во, символ x1 -символом y1 из алфавита B1, и так далее, символ Хг-1 заменяется символом ум из алфавита Вг-1, символ хг заменяется символом уг снова из алфавита Во, и т.д.

Общая схема многоалфавитной подстановки для случая г = 4 показана на рис. 5.7

Схема г-алфавитной подстановки для случая г = 4

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

Многоалфавитные шифры замены предложил и ввел в практику криптографии Леон Батист Альберти, который также был известным архитектором и теоретиком искусства. Его книга "Трактат о шифре", написанная в 1566 г., представляла собой первый в Европе научный труд

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

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

Этот шифр сложной замены, называемый шифром Гронсфельда, представляет собой модификацию шифра Цезаря числовым ключом. Для этого под буквами исходного сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Шифртекст получают примерно, как в шифре Цезаря, но отсчитывают по алфавиту не третью букву (как это делается в шифре Цезаря), а выбирают ту букву, которая смещена по алфавиту на соответствующую цифру ключа. Например, применяя в качестве ключа группу из четырех начальных цифр числа е (основания натуральных логарифмов), а именно 2718, получаем для исходного сообщения ВОСТОЧНЫЙ ЭКСПРЕСС следующий шифртекст:

Чтобы зашифровать первую букву сообщения В, используя первую цифру ключа 2 , нужно отсчитать вторую по порядку букву от В в алфавите В-Г-Д; получается первая буква шифр текста Д.

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

СистемашифрованияВижинера

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

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

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

Таблица Вижинера для английского алфавита

Сообщение ПР ИЛ ЕТ АЮ _Ш ЕС ТО ГО

Шифртекст ПЕ ОБ ЩН ФМ ЕШ РФ БЖ ДЦ

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

Задание, зашифровать всеми методами фразу: «Лысьвенский университетский комплекс»

Лабораторная работа №1

Тема Исследование схем разделения секрета

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

Теоретические пояснения

Рассмотрим случай, когда руководитель банка или какой-либо другой организации не полностью доверяет своим сотрудникам и хочет подстраховаться при использовании секретного ключа. Он может разделить весь секретный ключ (двоичная или десятичная последовательность символов) на отдельные фрагменты и эти фрагменты раздать нескольким сотрудникам так, чтобы при общем числе сотрудников n полный ключ мог быть ими составлен, если соберутся вместе не менее h сотрудников.

1. Наиболее просто поставленная задача решается при h = n, т.е. когда ключ раздается n сотрудникам и требуется наличие всех n фрагментов ключа, чтобы собрать полностью секретный ключ S [ 1 ]. Выберем некоторое простое число p, и пусть секретный ключ представляется в виде набора (s1,s2,s3,…,s k) , где все si являются элементами поля GF(p). Разделим секретный ключ на n фрагментов следующим образом. Будем генерировать произвольные случайные числа:

(an-11,an-12,an-13,…,a n-1k) - фрагмент секретного ключа n-1 – го сотрудника.

А последнему n-му сотруднику вычислим элементы его фрагмента секретного ключа по следующему правилу:

an1 = s1 - a11 - a21 - a31 - … - a n1 mod p.

разделить его на 5 фрагментов для раздачи 5 сотрудникам. Для первых четырех из них генератор случайных чисел по модулю 29 пусть выработал фрагменты:

(26, 0, 13, 11, 23, 25) (2, 7, 15, 12, 27, 6) (1, 3 , 24, 6, 0, 16) (12, 2, 7, 0, 7, 0)

Для последнего, пятого сотрудника вычисленный фрагмент имеет вид: (14, 1, 20, 8, 1, 0).

Легко проверяется, что сложение всех фрагментов (каждый элемент складывается по модулю 29) дает полный секретный ключ (26,13,21,8,0,18).

Следует заметить, что сложность подбора секретного ключа в рассмотренном случае зависит только от значения модуля p и числа элементов k и практически не зависит от количества сотрудников n.

2. Рассмотрим случай, когда h < n. Имеется несколько вариантов решения такой пороговой задачи. Приведем алгоритм, описанный в [2]. Он основан на модульной арифметике и китайской теореме об остатках.

Имеется n участников A1,A2,A3,…,A n. Пусть mi, i = 1,2,…n, целые числа, большие 1,

M/mi. Вычислим значения Ni из условия: MiNi º 1 mod mi. Так как (Mi,mi) = 1, то решение всегда существует, и все Ni будут найдены.

Если имеется n сравнений вида: x º ai mod mi, i = 1,2,…,n, a решение этих сравнений имеет вид:

n

x º S aiMiNi

i = 1

Кроме того, это решение единственное, т.е. любое другое решение y удовлетворяет сравнению: y º x mod M.

Пусть теперь k фиксированный порог, 1 < k £ n. Обозначим через min(k) – наименьшее из k произведений mi, а max(k-1) – наибольшее из k-1 произведений mi. Если выполнены условия:

участникам, то любые k из участников смогут восстановить значение c по его фрагментам, а любые k-1 участников сделать это не смогут (без перебора вариантов). При этом, чем больше в (*) разность, тем труднее k-1 участникам подобрать секретный ключ по своим фрагментам.

Пример. Пусть n = 5 и m1 = 97; m2 = 98, m3 = 99, m4 = 101, m5 = 103. Возьмем k = 3 и вычислим min(3) = (97*98*99) = 941094; max(2) = (101*103) = 10403. Неравенство (*) примет

вид: 941094 – 10403 = 930691 > 3*10403 = 31209.

Секретное число с должно лежать в пределах (**). Пусть оно известно некоторому сотруднику, разделяющему секрет, который вычислил значения ai (i = 1,2,…,5) из условий

ai º c mod mi и раздал фрагменты секрета пяти участникам: a1 = 62, a2 = 4, a3 = 50, a4 = 50, a5 = 38. Пусть теперь трое из пяти участников, например, A2,A3 и A4 пытаются восстановить секретный ключ c по своим фрагментам. Поскольку каждый участник знает только свое значение mi, то они вычисляют: M2’= m3*m4 = 9999; M3’= m2*m4 = 9898; M4’= m2*m3 = 9702,

а затем соответствующие значения Ni: N2 = 33, N3 = 49, N4 = 17. После чего находят значение x = 4*9999*33 + 50*9898*49 + 50*9702*17 = 33816668. Секретный ключ вычисляется из сравнения: c º x mod (m2*m3*m4), т.е. c º 33816668 mod (98*99*101) º 500000 mod 979902.

Если взять любую другую тройку клиентов, например, A1,A4,A5, то они вычислят тот же секретный ключ с = 500000.

Пусть теперь двое клиентов, например, A2 и A5 пытаются найти секретный ключ с.

Они вычисляют значения y = 4*103*59 + 38*98*41 = 176992 º 5394 º с mod 10094. Они