Вскрытие одноалфавитных шифров основано на учете частоты появления отдельных букв или их сочетаний (биграмм, триграмм и т.п.) в данном языке.
В осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, при этом относительные частоты букв в разных текстах одного языка близки между собой. Любой естественный язык обладает избыточностью, что позволяет с большойвероятностью угадывать смысл сообщения, даже если часть букв сообщения неизвестна.
Допустим, на доске объявлений некого учреждения появилась следующая надпись:
ТБПО ЩИЧЧЖ ЛНИЬЕЭФЭЕЭВЬ ЭКМНИО ИЩЩСКИЬОЭСФБИТЬЛИЬШ ТБПОЧЩЬП ЛНОЭЧЖ Ь ЧЛЭПЛКПЕПООЭЛЭНЛКИВИЫП ФЭБСТПООЖП ЬН ЩИЧЧЖ ЧЧСУЖЭто не может быть шифр перестановки, так как в шифровке четко проглядываются слова с регулярными окончаниями чж, иыи, оэ. Частоты встречи различных знаков шифровки явно неодинаковы. Знаки ч, и, э встречаются раз по десять, тогда как У, Ю и М лишь по одному разу, что не бывает в многоалфавитных шифрах, имеющих близкие вероятности знаков. Естественно предположить, что применен шифр простой замены. С чего следует начать расшифровывание? Несомненно, с установления отправителя и получателя сообщения. Зачастую, кроме имени получателя сообщения содержат еще и имя отправителя, как это принято в телеграммах: "Приезжаю шестого. Мама." У нашей шифровки была приписка: "Граждане, ознакомившиеся, запомнившие и исполнившие, принимаются ежедневно и без ограничений. Местком." Из нее ясен отправитель - местком. Поэтому шифрованный текст может не содержать его названия. Получатель все же должен быть доуточнен, как обращение: "всем садоводам..." или "члены кружка...". Однако это - слишком легкий путь. и предположим, что не удалось конкретизировать получателя, чтобы, используя его имя, вскрыть шифр.
Предположение 1.
Внимательно просматривая шифровку, можно обнаружить интересное удвоение знака Ч в конце последнего слова и начале последнего: щиччх ЧЧСУХ. Кажется, что этот знак весьма похож на употребление буквы С в русском тексте, как МАССА ССЫЛОК. Например, для буквы В не удается подобрать хороший пример, чтобы она удваивалась в конце слов, а для буквы Н - в начале. Отметим, что удвоение С в конце характерно для заимствованных существительных, где перед ним стоит чаще всего буква А. Значит, буква шифровки Ч соответствует в тексте С, а И соответствует русской букве А.
Предположение 2.
Другое удвоение, знака о, встречается только в конце слов и типично для русской буквы Н. Поэтому сочетания знаков на концах слов шифровки ОЭ и ооэ, скорее всего отвечают русским окончаниям в сообщении НО и ННО. Если это так, то последнее слово шифровки ЧЧСУЖ, начинающееся с СС и состоящее из пяти букв может быть лишь одним из двух слов - ССУДЕ или ССУДЫ, что легко проверить по словарю. Другие варианты прочтения ССУДА, ССОРА и тому подобные отпадают, так как буквы А иО уже разгаданы.
Предположение 3.
Знак шифровки ж, стоящий в конце слова ЧЧСУЖ встречается довольно редко, если учесть, что слово щиччж повторяется, а одинаковое окончание последнего и предпоследнего слов представляет собой обычное согласование слов в предложении. Это означает, что знаку ж скорее отвечает буква Ы, чем более часто встречаемая в русских текстах Е, а последнее слово - ССУДЫ. Окончание сообщения?АССЫССУДЫтеперь нетрудно отгадать как КАССЫССУДЫ, что весьма близко к осмысленному тексту. Из отгаданных букв пятое слово шифровки складывается как АККУ?А?НО, что несомненно означает АККУРАТНО, а седьмое слово??НОСЫиз контекста можно понять как ВЗНОСЫ. Итак, отгадывание идет вроде бы успешно, что подтверждается частичной расшифровкой:
Теперь дальнейшая расшифровка не представляет особого труда и выполняется быстро, угадыванием отдельных слов и подстановкой выясненных букв в шифровку. В итоге получаем сообщение:
ЧЛЕН КАССЫВЗАИМОПОМОЩИ ОБЯЗАНАККУРАТНО УПЛАЧИВАТЬ ЧЛЕНСКИЕВЗНОСЫИ СВОЕВРЕМЕННО ВОЗВРАЩАТЬПОЛУЧЕННЫЕ ИЗ КАССЫССУДЫ9. Поліалфавітні шифри (Гронсфелда, Трітеніуса, Віженера)
Этот шифр сложной замены, называемый шифром Гронсфельда, представляет собой модификацию шифра Цезаря числовым ключом. Для этого под буквами исходного сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Шифртекст получают примерно, как в шифре Цезаря, но отсчитывают по алфавиту не третью букву (как это делается в шифре Цезаря), а выбирают ту букву, которая смещена по алфавиту на соответствующую цифру ключа. Например, применяя в качестве ключа группу из четырех начальных цифр числа e (основания натуральных логарифмов), а именно 2718, получаем для исходного сообщения ВОСТОЧНЫЙ ЭКСПРЕСС следующий шифртекст:
| Сообщение | В | О | С | Т | О | Ч | Н | Ы | Й | Э | К | С | П | Р | Е | С | С | ||
| Ключ | |||||||||||||||||||
| Шифртекст | Д | Х | Т | Ь | Р | Ю | О | Г | Л | Д | Л | Щ | С | Ч | Ж | Щ | У |
Чтобы зашифровать первую букву сообщения В, используя первую цифру ключа 2, нужно отсчитать вторую по порядку букву от В в алфавите
| В | Г | Д |
получается первая буква шифртекста Д.
Следует отметить, что шифр Гронсфельда вскрывается относительно легко, если учесть, что в числовом ключе каждая цифра имеет только десять значений, а значит, имеется лишь десять вариантов прочтения каждой буквы шифртекста. С другой стороны, шифр Гронсфельда допускает дальнейшие модификации, улучшающие его стойкость, в частности двойное шифрование разными числовыми ключами.
Шифр Гронсфельда представляет собой по существу частный случай системы шифрования Вижинера.
Примером многоалфавитного шифра подстановки является система Виженера. Шифрование осуществляется по таблице, представляющей собой вадратную матрицу размерностью N x N, где N – число симолов используемого алфавита.
Выбирается ключ или ключевая фраза. После чего под каждой буквой исходного сообщения последовательно записываются символы ключа. Если ключ оказался короче сообщения, его используют несколько раз. Каждая буква шифротекста находится на пересечении столбца таблицы, определяемого буквой открытого текста и строки, определяемой буквой ключа.
Для расшифровки под буквами шифротекста последовательно записываются буквы ключа. В строке таблицы, соответствующей очередной букве ключа, происходит поиск соответствующей буквы шифртекста. Находящаяся над ней в первой строке таблицы буква является соответствующей буквой исходного текста.
10. Зламування методу Віженера.
11. Криптостійкість ключів.
Любая криптосистема основана на использовании ключевой информации, под которой понимается вся совокупность действующих в АСОД ключей. По своему назначению последние делятся на ключи для шифрования ключей и ключи для шифрования данных. По времени жизни делятся на долговременные и кратковременные. Примером последних являются так называемые сеансовые ключи, действующие в течение только одного сеанса связи. В понятие управление ключами входит совокупность методов решения таких задач, как;
• генерация ключей;
• распределение ключей;
• хранение ключей;
• замена ключей;
• депонирование ключей;
• уничтожение ключей.
Правильное решение всех перечисленных задач имеет огромное значение, так как в большинстве случаев противнику гораздо проще провести атаку на ключевую подсистему или на конкретную реализацию криптоалгоритма, а не на сам этот алгоритм криптографической защиты. Использование стойкого алгоритма шифрования является необходимым, но далеко не достаточным условием построения надежной системы криптографической защиты информации. Используемые в. процессе информационного обмена ключи нуждаются в не менее надежной защите на всех стадиях своего жизненного цикла.
К ключам для симметричных и асимметричных криптосистем предъявляются различные требования. Этот факт следует учитывать при построении гибридных криптосистем. В настоящее время надежными считаются ключи разрядностью не менее 80 бит для систем с секретным ключом и не менее 768 бит для систем с открытым ключом, стойкость которых определяется сложностью решения задачифакторизации больших чисел (например, RSA).
В распоряжении противника* атакующего криптосистему, всегда имеются две возможности: случайное угадывание ключа и полный перебор по всему ключевому пространству. Вероятность успеха ив том и в другом случае зависит от разрядности ключа. В табл. 9.1 приведены длины ключей симметричных и асимметричных систем, обеспечивающие одинаковую стойкость к атаке полного перебора и решению задачи факторизации соответственно.Примечание. На практике в гибридных криптосистемах долговременный ключ для асимметричного алгоритма выбирают более стойким, чем сеансовый ключ для симметричного.
Если противник обладает неограниченными финансовыми и техническими возможностями, для того чтобы узнать ключ, ему необходимо лишь потратить достаточное количество денег. В случае противника с ограниченными возможностями при выборе разрядности ключа учитывают следующие соображения:
• сложность атаки полного перебора;
• требуемое быстродействие криптоалгоритма в тех случаях, когда увеличение размера ключа увеличивает время работы операций шифрования;
• время жизни защищаемой информации и ее ценность;
• возможности противника.
Если технические возможности противника известны, сложность атаки путем полного перебора по всему ключевому пространству оценить достаточно просто. Например, при разрядности ключа симметричной криптосистемы, равной 64 битам, объем ключевого пространства равен 2м. Компьютер, который может перебирать 10б ключей в секунду, потратит на проверку всех возможных ключей более 5 тыс. лет. Современная вычислительная техника позволяет за время порядка нескольких дней при финансовых затратах порядка нескольких сотен тысяч долларов находить методом полного перебора 56-разрядные ключи симметричных криптосистем.
Сообщается, что международной группе исследователей удалось вскрыть шифр RSA с ключом длиной 512 бит. Именно такой ключ используется для защиты Интернет-транзакций, а также в шифрах многих коммерческих банков. Интересно также отметить, что 512 двоичных разрядов - это максимальная длина ключа, которую правительство США разрешает использовать в экспортируемых программных продуктах. Работа по подбору двух простых сомножителей числа, содержащего 155 десятичных цифр, велась в течение 7 месяцев с привлечением ресурсов параллельно работающих 292 компьютеров, находящихся в И различных географических точках.12. Перестановочні шифри. Статистичні властивості криптограм перестановок. Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов. Шифрование простой перестановкой.· выбирается ключевое слово с неповторяющимися символами;· шифруемый текст записывается последовательными строками под символами ключевого слова;· зашифрованный текст выписывается колонками в той последовательности, в которой располагаются в алфавите буквы ключа (или в порядке следования цифр в натураьлном ряду, если он цифровой)
Недостатком шифрования простой перестановкой обуславливается тем, при большой длине шифруемого текста в зашифрованном тексте могут проявиться закономерности символов ключа. Для устранения этого недостатка можно менять ключ после зашифровки определенного количества знаков. При достаточно частой смене ключа стойкость шифрования можно существенно повысить. При этом, однако, усложняется организация процесса шифрования и дешифрования.
Усложненный метод перестановки по таблицам
Усложненный метод перестановки по таблицам заключается в том, что для записи символов шифруемого текста используется специальная таблица, в которую введены некоторые усложняющие элементы. Таблица представляет собой матрицу, размеры которой могут быть выбраны произвольно (например 10 х 10). В нее, как и в случае простой перестановки, записываются знаки шифруемого текста. Усложнение состоит в том, что определенное число клеток таблицы не используется. Количество и расположение неиспользуемых элементов является дополнительным ключом шифрования. Шифруемый текст блоками по m x n - S элементов записывается в таблицу (m x n — размеры таблицы, S — количество неиспользуемых элементов). Далее процедура шифрования аналогична простой перестановке.
Варьируя размерами таблицы, последовательностью символов ключа, количеством и расположением неиспользуемых элементов, можно получить требуемую стойкость зашифрованного текста.
Усложненный метод перестановок по маршрутам
Весьма высокую стойкость шифрованию можно обеспечить, используя усложненный метод перестановок по маршрутам типа гамильтоновских. При этом для записи символов шифруемого текста используются вершины некоторого гиперкуба, а знаки зашифрованного текста считываются по маршрутам Гамильтона, причем используется несколько различных маршрутов.
Следует заметить, что все процедуры шифрования и расшифровки по методу перестановки являются в достаточной степени формализованным и могут быть реализованы алгоритмически.
13.Шифри збивання. Лінійні перетворення.
Суть алгоритма DES заключается в линейном преобразовании:s = l * t, где l – невырожденная матрица случайного линейного преобразования бит. И хотя расшифровывание в этом случае придется осуществлять решением систем линейных уравнений, но каждый бит шифровки начинает уже зависеть от каждого бита текста. Шифры на основе этого преобразования называют скремблерами (взбивателями). Для того, чтобы матрица l была невырожденной, случайной и при расшифровывании не нужно было производить много вычислений, американскими криптографами был предложен оригинальный алгоритм. Входной блок данных делится на левую l’ и правую r’ части. После этого формируется выходной массив так, что его левая часть l” представлена правой частью r’ входного, а правая часть r” формируется как сумма l’ и r’ операцией xor. Далее, выходной массив шифруется перестановкой с заменой. После нескольких таких взбиваний каждый бит выходного блока может зависеть от каждого бита сообщения.
| ||
|
14. Одноразові блокноти. Формування випадкової псевдопослідовності. Одноразовый блокнот представляат собой очень длинную последовательность случайных чисел. Этот блокнот создается в двух экземплярах, один из которых находится у отправителя сообщения. А другой - у его получателя. Отправитель осуществляет сложение кодов символов сообщения и случайной последовательности. Полученный результат он отправляет получателю. Например, в соответствии с кодированием американским стандартным кодом для обмена информацией слово «Узел» представляется четырьмя числами:
147 167 165 171.
Случайная последовательность выдала числа:
342 076 543 132.
В результате сложения по числам первого и второго получен результат:
489 143 708 303.
Этот результат пересылается получателю. Проведя из результата посимвольное вычитание чисел случайной последовательности получатель определяет код посланного слова. К сказанному следует добавить, что для упрощения изложения выше использовались десятичные числа, хотя в реальности программы работают с двоичными числами.
М-последовательности
Широкое распространение получили генераторы на основе сдвигового регистра с линейными обратными связями. Они описываются следующим отношением:
ai= 
Åakai-k, k=0,1,2,..., (2.1)
где k - номер такта; ak 
{0,1} - биты формируемой последовательности; ai {0,1} - постоянные коэффициенты; 
Å - операция суммирования по модулю 2. Генератор, описываемый отношением (2.1), показан на рис. 2.1.
Свойства генерируемой последовательности определяются постоянными коэффициентами ai. Их можно исследовать, анализируя характеристический полином
g(x) = 1 Å a1x Å a2x2Å...Å am-1xm-1Å amxm.
При соответствующем выборе коэффициентов генерируемая последовательность { ai} будет иметь максимально возможный период, равный 2m-1, где m - разрядность сдвигового регистра и одновременно старшая степень порождающего полинома. Последовательность максимально возможного периода называется M-последовательностью. Основная задача синтеза генератора рассматриваемого типа - нахождение характеристического полинома, формирующего М-последовательность.
Полиномы, формирующие последовательность максимального периода, называются примитивными. С ростом m их количество становится очень большим. Среди множества примитивных полиномов степени m можно найти полиномы с наименьшим числом единичных коэффициентов ai. Генераторы, построенные на их основе, имеют наиболее простую техническую реализацию. В табл. 2.1 приведен перечень полиномов с минимальным количеством ненулевых коэффициентов для значений m <=16.
Схема четырехразрядного ГК, описываемого примитивным полиномом g(x)=1Å x3 Å x4, приведена на рис. 2.2; его работа показана в табл. 2.2.
Для формирования M-последовательности наряду с примитивным полиномом g(x) может использоваться и обратный ему полином g-1(x)=xmg(x-1). Полученная в этом случае последовательность максимальной длины будет инверсной по отношению к последовательности, формируемой g(x). Например, для полинома g(x)=1Åx3Åx4 обратным полиномом будет g-1(x) = x4(1Åx-3Åx-4)=1 Å x Å x4.
Главное преимущество описываемого метода формирования псевдослучайных последовательностей - простота его реализации. Генератор M-последовательности содержит лишь m-разрядный регистр сдвига и набор сумматоров по модулю два в цепи обратной связи. Регистр сдвига выполняет функции хранения m бит M-последовательности и сдвига m-разрядного кода на один разряд вправо. Сумматоры по модулю два вычисляют очередное значение младшего разряда сдвигового регистра.
Состояние разрядов регистра на каждом такте можно представить в виде m-мерных векторов A(k)=a1(k)a2(k)a3(k)...am(k), где k=0,1,2,... - номер такта, ai(k) - состояние i-го разряда, i=1,m,
Последовательное применение соотношений (1) или (2) для s = 0 позволяет формировать соответственно одно- или многоразрядные псевдослучайные последовательности, которые характеризуется рядом статических свойств.
Рассмотрим наиболее важные свойства М-последовательностей.
1. Период последовательности, описываемой выражением (1), определяется старшей степенью порождающего полинома g(x) и равен L= 2m -1.
2. Для заданного полинома g(x) существует L различных M-последовательностей, отличающихся фазовым сдвигом. Так, полиному g(x)=1Åx3Åx4 соответствует 15 M-последовательностей.
3. Количество единичных и нулевых символов ak, k=0,1,..., L-1, M-последовательности соответственно равно 2m-1 и 2m-1 -1. Вероятностная оценка частоты их появления определяется следующими выражениями:
p(ak=1)=2m-1 /(2m-1)=1/2 + 1/(2m+1-2),
p(ak=0)=(2m-1-1)/(2m-1) = 1/2-(2m+1 -2)
и при увеличении m достигает значений, сколь угодно близких к 1/2.
4. Вероятности появления серий из r, r {1,2,...,m-1}, одинаковых символов (нулей или единиц) в M-последовательности максимально близки к соответствующим вероятностям для случайной последовательности.
5. Для любого значения s (1 
s<L) существует такое r 
s (1 r<L), что {ak} + {ak-s}={ak-r}. Данное свойство обычно называют свойством сдвига и сложения.
Использование линейных сдвиговых регистров для создания криптосистем предполагает их уязвимость, если взломщик обладает парой: исходный текст - шифротекст длиной не менее 2m бит. Действительно, имея исходный текст M=(m1,m2,...,m2m) и соответствующий шифротекст C=(c1,c2,...,c2m), мы можем получить К=MÅC=(m1Åc1,m2Åc2,...,m2mÅc2m)=(k1,k2,k3,...,k2m). Тогда задача взлома криптосистемы при известном начальном состоянии сводится к решению системы из m линейных уравнений с m неизвестными, где неизвестными являются коэффициенты порождающего полинома.
Данная система имеет вид
1k1 Å 2k2Å 3k3 Å... Å mkm =km+1
1k2Å 2k3Å 3k4 Å... Å mkm+1 =km+2
1k3 Å 2k4Å 3k5 Å... Å mkm+2 =km+3
........
1kmÅ 2km+1Å 3km+2 Å... Å mkm+m-1 =k2m .
DES имеет блоки по 64 бит и основан на 16 кратной перестановке данных, также для зашифрования использует ключ в 56 бит. Существует несколько режимов DES, например Electronic Code Book (ECB) и Cipher Block Chaining (CBC). 56 бит - это 8 семибитовых ASCII символов, т.е. пароль не может быть больше чем 8 букв. Если вдобавок использовать только буквы и цифры, то количество возможных вариантов будет существенно меньше максимально возможных 2^56. Для его применения в различных приложениях были определены 4 режима его работы. ECB - Electronic Codebook (электронная шифровальная книга)
ECB является простейшим режимом шифрования, когда открытый текст обрабатывается блоками по 64 бита, каждый из которых шифруется с одним и тем же ключом (рис. 1). Самой важной особенностью этого режима является то, что одинаковые 64 -битовые блоки открытого текста, если таковые встречаются в исходном сообщении, в шифрованном тексте также будут представлены одинаковыми блоками. Поэтому при передачи достаточно длинных сообщений режим ECB может не обеспечить необходимый уровень защиты информации.
При разбиении исходного сообщения на блоки, к последнему блоку добавляется заполнитель, если его длина не равна 64 бита. CBC - Cipher Block Chaining (сцепление шифрованных блоков)
Режим CBC решает проблему одинаковых шифрованных блоков соответствующих одинаковым блокам открытого текста. Этого добиваются с помощью режима сцепленного шифрования. Входное значение алгоритма шифрования задаётся XOR-суммой текущего блока открытого текста и полученного на предыдущем шаге блока шифрованного текста.
Дешифрование происходит по аналогичной схеме: блок открытого текста получается как XOR-сумма выходного блока алгоритма дешифрования и предыдущего блока шифрованного текста.
Чтобы получить первый блок шифрованного текста, рассматривается XOR-сумма некоторого инициализационного вектора (IV) и первого блока открытого текста. При дешифровании, для восстановления первого блока открытого, необходимо также выполнить операцию XOR по отношению к тому же вектору IV и первому блоку на выходе алгоритма дешифрования. В связи с этим значение IV, также как и ключ шифрования, должно быть известно как отправителю, так и получателю сообщения. CFB - Cipher Feedback (шифрованная обратная связь)
Алгоритм шифрования DES является блочным шифром с размером блока 64 бита. Но его можно преобразовать к потоковому шифру, используя режим CFB или OFB. Это избавляет от необходимости дополнять сообщения до кратности 64 битам, а также позволяет использовать этот алгоритм в системах реального времени, где данные необходимо шифровать и передавать дальше по мере их поступления.
Предпологается, что единицей передачи данных является j битов (обычно это значение равно 8). Как и в режиме CBC, происходит сцепление элементов открытого текста, поэтому шифрованный текст, соответствующий любому элементу открытого текста, будет зависеть от всех предыдущих элементов открытого текста.
Рассмотрим процесс шифрования. На входе функции шифрования размещается 64-битовый регистр сдвига, который изначально содержит некоторое значение инициализационного вектора (IV). После шифрования значения данного регистра, берутся его крайние слева j битов, которые складываются операцией XOR с первыми j битами открытого (P1), что в результате даёт j битов шифрованных данных (C1). Далее значение регистра сдвига смещается влево на j битов, а крайние справа j битов замещаются значением C1. Затем весь процесс повторяется до тех пор, пока не зашифруются все данные.
Для дешифрования используется та же схема, но для получения очередной порции открытого текста с помощью операции XOR складываются шифрованные данные и полученные на выходе функции шифрования данные. OFB - Output Feedback (обратная связь по выходу)
Данный режим во многом подобен режиму CFB, за исключением того, что в регистр сдвига подаются крайние левые j битов результата функции шифрования, а не порция шифрованного текста.
Режим OFB, по сравнению с CFB, обладает тем преимуществом, что влияние возможных искажений битов при передаче данных не распространяется на последующие порции данных. С другой стороны, этот режим обеспечивает меньшую защиту данных, чем CFB.
16. Асиметрічна криптографія.
Асимметричная криптография изначально задумана как средство передачи сообщений от одного объекта к другому (а не для конфиденциального хранения информации, которое обеспечивают только симметричные алгоритмы). Поэтому дальнейшее объяснение мы будем вести в терминах "отправитель" – лицо, шифруюшее, а затем отпраляющее информацию по незащищенному каналу и "получатель" – лицо, принимающее и восстанавливающее информацию в ее исходном виде. Основная идея асимметричных криптоалгоритмов состоит в том, что для шифрования сообщения используется один ключ, а при дешифровании – другой.
Кроме того, процедура шифрования выбрана так, что она необратима даже по известному ключу шифрования – это второе необходимое условие асимметричной криптографии. То есть, зная ключ шифрования и зашифрованный текст, невозможно восстановить исходное сообщение – прочесть его можно только с помощью второго ключа – ключа дешифрования. А раз так, то ключ шифрования для отправки писем какому-либо лицу можно вообще не скрывать – зная его все равно невозможно прочесть зашифрованное сообщение. Поэтому, ключ шифрования называют в асимметричных системах "открытым ключом", а вот ключ дешифрования получателю сообщений необходимо держать в секрете – он называется "закрытым ключом". Напрашивается вопрос: "Почему, зная открытый ключ, нельзя вычислить закрытый ключ?" – это третье необходимое условие асимметричной криптографии – алгоритмы шифрования и дешифрования создаются так, чтобы зная открытый ключ, невозможно вычислить закрытый ключ.
В целом система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей: "открытый" Ej и "закрытый" Dj, где j – номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. Если абонент, скажем под номером 7, собирается передать информацию абоненту под номером 9, он шифрует данные ключом шифрования E9 и отправляет ее абоненту 9. Несмотря на то, что все пользователи сети знают ключ E9 и, возможно, имеют доступ к каналу, по которому идет зашифрованное послание, они не могут прочесть исходный текст, так как процедура шифрования необратима по открытому ключу. И только абонент №9, получив послание, производит над ним преобразование с помощью известного только ему ключа D9 и восстанавливает текст послания. Заметьте, что если сообщение нужно отправить в противоположном направлении (от абонента 9 к абоненту 7), то нужно будет использовать уже другую пару ключей (для шифрования ключ E7, а для дешифрования – ключ D7).
Как мы видим, во-первых, в асимметричных системах количество существующих ключей связано с количеством абонентов линейно (в системе из N пользователей используются 2*N ключей), а не квадратично, как в симметричных системах. Во-вторых, при нарушении конфиденциальности k-ой рабочей станции злоумышленник узнает только ключ Dk: это позволяет ему читать все сообщения, приходящие абоненту k, но не позволяет вывадавать себя за него при отправке писем.
Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.
Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций:
1. Выбираются два простых (!) числа p и q
2. Вычисляется их произведение n(=p*q)
3. Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).
4. Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.
5. Два числа (e,n) – публикуются как открытый ключ.
6. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).
17. Метод Райвеста-Шамира-Адлемана (RSA)
RSA многие годы противостоит интенсивному криптоанализу. Криптостойкость основана на трудоемкости разложения на множители (факторизации) больших чисел. Открытый и секретный ключи являются функциями двух больших (100 ~ 200 двоичных разрядов или даже больше) простых чисел. Предполагается, что задача восстановления открытого текста по шифротексту и открытому ключу эквивалентна задаче факторизации.
Для генерации парных ключей берутся два больших случайных простых числа p и q. В целях максимальной криптостойкости p и q выбираются равной длины. Затем вычисляется их произведение n=pq (n называется модулем). Далее случайным образом выбирается число e (ключ шифрования), удовлетворяющее условию: 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом f(n)=(p-1)*(q-1).
Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрования d, такого, что ed=1 mod f(n). Число d такое, что (ed - 1) делится на (p - 1)(q–1).
| Открытый ключ: (public) | n - произведение друз простых чисел p и q (должны храниться в секрете); e – число, взаимно простое с f(n) |
| Секретный ключ: (private) | d = e-1 mod f(n) |
| Шифрование: | c = me mod n |
| Дешифрование: | m = cd mod n |
Числа d и n - также взаимно простые числа.
Числа e и n – открытый ключ, а d – секретный.
Два простых числа p и q хранятся в секрете.
Для шифрования сообщения m необходимо выполнить его разбивку на блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q - 100 разрядные простые числа, то n будет содержать около 20 разрядов и каждый блок сообщения mi должен иметь такое же число разрядов. Если же нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение с будет состоять из блоков ci той же самой длины. Шифрование сводиться к вычислению
ci =mie mod n.
При дешифровании для каждого зашифрованного блока ci вычисляется
mi = cid mod n
Последнее справедливо, так как
cid = (mie)d = mied = mikf(n)+1 = mi·1 = mi
Все вычисления выполняются по mod n. Сообщение может быть зашифровано с помощью d, а дешифровано с помощью e, возможен любой выбор.
Предполагается, что криптостойкость RSA зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно n разложить на множители. Чтобы восстановить m по с и e. Не исключено, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Также можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения n на множители. При использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрование всего сообщения. Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже менее эффективна, чем попытка разложения n на множители. В 1993 г. был предложен метод криптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соо