Основы криптографии

Используя обобщение Эйлера, решаем

x = (b* a ^ф(n)-1 ) mod n

Используя алгоритм Эвклида, находим

x = (b* (a^-1 modn)) mod n

В общем случае для вычисления обратных значений алгоритм Эвклида быстрее, чем обобщение Эйлера, особенно для чисел длиной порядка 500 бит. Если НОД(а,и) Ф 1, не все потеряно. В этом общем случае (a*x) mod n=b, может иметь или несколько решений, или ни одного.

Квадратичные вычеты

Если p - простое число, и а больше 0, но меньше p, то а представляет собой квадратичный вычет по модулю p, если x² = a (mod p), для некоторых x Не все значения а соответствуют этому требованию. Чтобы а было квадратичным вычетом по n, оно должно быть квадратичным вычетом по модулю всех простых сомножителей п. Например, если p = 7, квадратичными вычетами являются числа 1, 2, и 4:

1² = 1 = 1 (mod 7)

2² = 4 = 4 (mod 7)

3² = 9 = 2 (mod 7)

4²=16 = 2(mod7)

5² = 25 = 4 (mod 7) 6² = 3

6 = 1 (mod 7)

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

x² = 3 (mod 7)

x² = 5 (mod 7)

x² = 6 (mod 7)

Эти числа - 3, 5 и 6 - не являются квадратичными вычетами по модулю 7.

Хотя я этого и не делаю, несложно доказать, что когда p нечетно, существует в точности (p - l)/2 квадратичных вычетов по модулю p, и столько же чисел, не являющихся квадратичными вычетами по модулю р. Кроме того, если а - это квадратичный вычет по модулю p, то у а в точности два квадратных корня, один между 0 и (p-l)/2, а второй - между (p - l)/2 и (p - 1). Один из этих квадратных корней одновременно является квадратичным остатком по модулю p, он называется главным квадратным корнем

Если n является произведением двух простых чисел, p и q, то существует ровно (p - 1)(q - l)/4 квадратичных вычетов по модулю п. Квадратичный вычет по модулю n является совершенным квадратом по модулю и, потому что для того, чтобы быть квадратом по модулю и, вычет должен быть квадратом по модулю p и квадратом по модулю q. Например, существует одиннадцать квадратичных остатков mod 35: 1, 4, 9, 11, 15, 16, 21, 25, 29 и 30. У каждого квадратичного вычета ровно четыре квадратных корня.

Символ Лежандра

Символ Лежандра, L(a,p), определен, если а - это любое целое число, a p - простое число, большее, чем 2. Он равен 0, 1 или - 1 .

L(a,p)= 0, если а делится на р.

L(a,p)= 1, если а - квадратичный вычет по модулю р.

L(a,p) = -1, если а не является квадратичным вычетом по модулю р.

L(a,p) можно рассчитать следующим образом: L(a,p) = a^(p-1)/2 mod p Или можно воспользоваться следующим алгоритмом:

1. Если а = 1, то L(a,p) = 1

Если а четно, то L(a,p) = L(a/2,p) * (-l)^²-'>⁷⁸

Если а нечетно (и * 1), то L(a,p)= Цр mod а,^)*(-1)^(3*3-1)/8

Обратите внимание, что этот метод также является эффективным способом определить, является ли a квадратичным вычетом по модулю p (для простого числа p).

Символ Якоби

Символ Якоби, J(a,n), представляет собой обобщение символа Лежандра на составные модули, он определяется для любого целого a и любого нечетного целого п. Функция удобна при проверке на простоту. Символ Якoби является функцией на множестве полученных вычетов делителей n и может быть вычислен по различным формулам.Вот один из способов:

Определение 1 : J(a,n) определен, только если n нечетно.

Определение 2: J(0,n) = 0.

Определение 3: Если n - простое число, то символ Якоби ](a,n) = 0, если а делится на п.

Определение 4: Если n - простое число, то символ Якоби J(a,n) = 1, если а - квадратичный вычет по модулю п.

Определение 5: Если n - простое число, то символ Якоби ](a,n) = -1, если а не является

квадратичным вычетом по модулю п.

Определение 6: Если n - составное число, то символ Якоби J(a,n) = J(a,p₁)* ... * J(a,p_m), где p₁…p_m - это разложение n на простые сомножители.

Следующий алгоритм рекурсивно рассчитывает символ Якоби:

Правило 1: J(l,n) = 1

Правило 2: J(a*b,n} = J(a,n)* J(b,n)

Правило 3: J(2,n) =, если (n²-1) /8 нечетно, и -1 в противном случае

Правило 4: J(a,n)= J((a mod n),n)

Правило 5: J(a, bi*b₂) = J(a, b₁)* J(a, b₂)

Правило 6: Если наибольший общий делитель a и b = 1, а также a и b нечетны:

Правило 6а: J(a,b)= J(b, a), если (a - 1)(b - l)/4 четно

Правило 6b: J(a,b)= -J(b, a), если (a - 1)(b - l)/4 нечетно

Алгоритм на языке С: (кажется уже начал объяснять сам С)

int jacobi(int a, int b) {

int g;

assert(odd(b));

if (а >= b) a %= b; /* по правилу 4 */

if (а == 0) return 0; /* по определению 1 */

if (а == 1) return 1; /* по правилу 1 */

if (а < 0)

if ((b-l)/2 % 2 == 0)

return jacobi(-a,b); else

return -jacobi(-a,b); if (а % 2 == 0) /* а четно */

if (((b*b -1)/8) % 2 == 0)

return +jacobi(a/2,b); else

return -jacobi(a/2,b); /* по правилам 3 и 2 */ g = gcd(a,b);

assert(odd(a)); /* это обеспечивается проверкой (а % 2 == 0) */ if (g == а) /* b делится на а */

return 0; /* по правилу 5 */ else if (g '= 1)

return jacobi(g,b)*jacobi(a/g,b); /* по правилу 2 */ else if (((a-l)*(b-l)/4) % 2 == 0)

return +jacobi(b,a); /* по правилу 6a */ else

return -jacobi(b,a); /* по правилу 6b */ }

Если заранее известно, что n - простое число, вместо использования предыдущего алгоритма просто вычиcлите a((n-l)/2) mod n, в этом случае J(a,n) эквивалентен символу Лежандра.

Символ Якоби нельзя использовать для определения того, является ли a квадратичным вычетом по модулю n (если, конечно, n не является простым числом). Обратите внимание, что если J( a,n) = 1 и n - составное число, то утверждение, что а является квадратичным вычетом по модулю и, не обязательно будет истиной. Например:

J(7,143) = J(7,11)* J(7,13) = (-1)(-1) = 1

Однако не существует таких целых чисел x, что x² = 1 (mod 143).

Целые числа Блюма

Если p и q - два простых числа, конгруэнтных 3 по модулю 4, то n = pq иногда называют целым числом Блюма. Если n - это целое число Блюма, у каждого квадратичного вычета ровно четыре квадратных корня, один из которых также является квадратом - это главный квадратный корень. Например, главный квадратный корень 139 mod 437 - это 24. Остальные три корня - это 185, 252 и 413.

Вычисление в поле Галуа

Не тревожьтесь, все это мы уже делали. Если n - простое число или степень большого простого числа, то мы получаем то, что математики называют конечным полем. В честь этого мы используем p вместо п. В действительности этот тип конечного поля настолько замечателен, что математики дали ему собственное имя - поле Галуа, обозначаемое как GF(p). в честь Эвариста Галуа, французского математика, жившего в девятнадцатом веке и успевшего значительно продвинуть теорию чисел, прежде чем в 20 лет он был убит на дуэли.)

В поле Галуа определены сложение, вычитание, умножение и деление на ненулевые элементы. Существует нейтральный элемент для сложения - 0 - и для умножения - 1. Для каждого ненулевого числа существует единственное обратное число (это не было бы так, если бы p не было бы простым числом). Выполняются коммутативный, ассоциативный и дистрибутивный законы.

Арифметика поля Галуа широко используется в криптографии. В нем работает вся теория чисел, поле с o-держит числа только конечного размера, при делении отсутствуют ошибки округления. Многие криптосистемы основаны на GF(p), где з - это большое простое число.

Чтобы еще более усложнить вопрос, криптографы также используют арифметику по модулю неприводимых многочленов степени n, коэффициентами которых являются целые числа по модулю q, где q - это простое число. Эти поля называются GF(qт). Используется арифметика по модулю p(x), где р(х) - это неприводимый многочлен степени п.

При обсуждении полиномов термин "простое число" заменяется термином " неприводимый многочлен". Пoлином называется неприводимым, если его нельзя представить в виде двух других полиномов (конечно же, кроме 1 и самого полинома). Полином x² + 1 неприводим над целыми числами, а полином x³ + 2 x² + x не является неприводимым, он может быть представлен как

x(x + l)(x + 1).

Полином, который в данном поле является генератором, называется примитивным или базовым, все его кoэффициенты взаимно просты.

Для поля Галуа GF(2ⁿ) криптографы любят использовать в качестве модулей трехчлены p(x) = x" + x + 1, так как длинная строка нулей между коэффициентами при x" и x позволяет просто реализовать быстрое умножение по модулю. Полином должен быть примитивным, в противном случае математика не будет работать, x" + x + 1 примитивен для следующих значений n, меньших чем 1000

1, 3, 4, 6, 9, 15, 22, 28, 30,46, 60, 63, 127, 153, 172, 303,471, 532, 865, 900

Существуют аппаратные реализации GF(2¹²⁷), где p^x = x¹²¹ + x + 1.

Разложение на множители

Разложить число на множители - значит найти его простые сомножители.

10 = 2*5

60 = 2*2*3*5

252601=41*61*101

2113- 1 =3391*23279*65993*1868569*1066818132868207

Разложение на множители является одной из древнейших проблем теории чисел. Этот процесс несложен, но требует времени. Это пока остается так, но ряд сдвигов в этом искусстве все же произошел. Сегодня самым лучшим алгоритмом является:

Решето числового поля чисел (Number field sieve, NFS).

Решето общего числового поля - это самый быстрый из известных алгоритм для чисел размером 1 10 и более разрядов . В своем первоначальном виде он был непрактичен, но за последние несколько лет он был последовательно улучшен . NFS все еще слишком нов, чтобы бить рекорды разложения на множители, но скоро все перемeнится. Ранняя версия использовалась для разложения на множители девятого числа Ферма: 2512 + 1 .

Другие алгоритмы, вытесненные NFS:

Квадратичное решето. Это самый быстрый из известных и чаще всего использовавшийся алгоритм для чисел, длина которых меньше 1 10 десятичных разрядов. Более быстрая версия этого алгоритма называется множественным полиномиальным квадратичным решетом. Самая быстрая версия называется двойной вариацией множественного полиномиального квадратичного решета с большим простым числом.

Метод эллиптической кривой. Этот метод использовался для поиска не более, чем 43-разрядных множителей.

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

В 1970 году большой новостью стало разложение на множители 41-разрядного трудного числа. ("Трудным" является такое число, у которого нет маленьких множителей, и которое не обладает специальной формой, позволяющей упростить процесс.) Десять лет спустя разложение в два раз более длинного числа заняло лишь несколько часов на компьютере Cray .

В 1988 году Карл Померанс (Carl Pomerance), используя обычные СБИС, спроектировал устройство для paзложения на множители . Размер числа, которое можно было разложить, зависел только от размеров устройства, которое так и не было построено.

В 1993 году с помощью квадратичного решета было разложено на множители 120-разрядное трудное число. Расчет, потребовавший 825 mips-лет, был выполнен за три месяца реального времени.

Сегодня для разложения на множители используются компьютерные сети. Для разложения 1 16_разрядного числа в течение нескольких мeсяцев использовалось свободное время массива компьютеров, разбросанных по всему миру, - 400 mips-лет, потребовалось в сумме.

В марте 1994 года с помощью двойной вариации множественного полиномиального QS командой мaтематиков под руководством Ленстры было разложено на множители 129-разрядное (428-битовое) число. Вычисления выполнялись добровольцами в Internet - в течение восьми месяцев трудились 600 человек и 1600 компьютеров, возможно, самый большой в истории многопроцессорный конгломерат. Трудоемкость вычислений была в диапазоне от 4000 до 6000 mips-лет. Компьютеры соединялись по электронной почте, передавая свои результаты в центральное хранилище, где выполнялся окончательный анализ. В этих вычислениях использовaлись QS и теория пятилетней давности, NFS мог бы ускорить выполнение расчетов раз в десять . В cooтветствии с : "Мы делаем вывод, что широко используемые 512-битовые модули RSA могут быть вскрыты организацией, готовой потратить несколько миллионов долларов и подождать несколько месяцев." По оценкам авторов разложение 512-битового числа в 100 раз более трудоемко при использовании той же техники и только в 10 сложнее при использовании NFS и современной техники.

Квадратные корни по модулю n

Если n - произведение двух простых чисел, то возможность вычислить квадратные корни по модулю n вычислительно эквивалентна возможности разложить число n на множители. Другими словами, тот, кто знает простые множители числа n, может легко вычислить квадратные корни любого числа по модулю n, но для любого другого вычисление окажется таким же трудным, как и разложение на простые множители числа п.

Ну вот вроде с математическими основами разобрались. Математика дальше будет нам встречается повсеместно, но базовые знания уже есть..

Собственно говоря уже можно переходить к самим алгоритмам, но кажется я упустил некоторые моменты- а именно XOR, одноразовые блокноты и ключи (нет не от квартиры).

Простое XOR

XOR представляет собой операцию "исключающее или" : '^' в языке С или Q в математической нотации. Это обычная операция над битами :

0 0 = 0

0 1 = 1

1 0 = 1

1 1 = 1

Также заметим, что:

a a =0

abb=a

Казалось бы, запутанный алгоритм простого XOR по сути является ничем иным, как полиалфавитным шифром Вигенера. Здесь он упоминается только из-за распространенности в коммерческих программных продуктах, по крайней мере в мире MS-DOS и Macintosh. К сожалению, если о программе компьютерной безопасности заявляется, что это "патентованный" алгоритм шифрования, значительно более быстрый, чем DES, то скорее всего используется какой-то вариант следующего .

void main (int argc, char *argv[])

{

FILE *fl, *fo;

char *cp;

int с;

if ((cp = argv[l]) && *cp'= '\0') {

if ((fi = fopen(argvl[2], "rb")) '= NULL) {

if ((fo = fopen(argv[3], "wb")) '= NULL) { while ((c = getc(fi)) '= EOF) { if ('*cp) cp = argv[l]; c^ = * (cp++) ; putc (с, fo) ; }

fclose (fo) ; } fclose(fi) ;

Это симметричный алгоритм. Открытый текст подвергается операции "исключающее или" вместе с ключeвым текстом для получения шифротекста. Так как повторное применение операции XOR восстанавливает оригинал для шифрования и дешифрирования используется одна и та же программа :

P K=C

C K = P

Настоящей безопасности здесь никогда не было. Этот тип шифрования легко вскрывается, даже без компьтетера.

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

Определим длину ключа с помощью процедуры, известной как подсчет совпадений Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещeниями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут дрyгими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа.

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

Одноразовые блокноты

Помните я говорил что есть невзлавыеваемая система сокрытия информации? Он называется одноразовым блокнотом и был изобретен в 1917 году Мэйджором Джозефом Моборном (Major Joseph Mauborgne) и Гилбертом Вернамом (Gilbert Vernam) из AT&T . В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом, написанных на кусочках бумаги и приклеенных к листу блокнота. Отправитель использовал каждый символ ключа блокнота для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю 26 (для английского языка), или 33 (для кириллического) символа открытого текста и символа ключа из однoразового блокнота.

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

ONETMEPAD

а ключевая последовательность блокноте:

TBFRGFARFM

то шифротекст будет выглядеть как:

IPKLPSFHGQ так как

Q + Т mod 26 = I

N + В mod 26 = P

E + F mod 26 = К и.т.д.

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

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

POYYAEAAZX

что дешифрируется как:

SALMONEGGS

или на:

BXEGBMTMXM

что дешифрируется как:

GREENFLUID

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

Необходимо напомнить, что символы ключа должны генерироваться случайным образом . Любые попытки вскрыть такую схему сталкиваются со способом, которым создается последовательность символов ключа . Использование генераторов псевдослучайных чисел не считается, у них всегда неслучайные свойства . Если вы используете действительно случайный источник- это совершенно безопасно.

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

Данная система как нельзя лучше подтверждает то что всё гениальное- просто…

Управление ключами

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

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

Управление ключами - информационный процесс, включающий в себя три элемента:

генерацию ключей;

накопление ключей;

распределение ключей.

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

Генерация ключей

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

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

Накопление ключей

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

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

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

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

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

Вопрос обновления ключевой информации связан и с третьим элементом управления ключами - распределением ключей.

Распределение ключей

Распределение ключей - самый ответственный процесс в управлении ключами. К нему предъявляются два требования:

Оперативность и точность распределения

Скрытность распределяемых ключей

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

Распределение ключей между пользователями реализуются двумя разными подходами:

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

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

В обоих случаях должна быть гарантирована подлинность сеанса связи. Это можно обеспечить двумя способами:

1. Механизм запроса-ответа, который состоит в следующем. Если пользователь А желает быть уверенным, что сообщения который он получает от В, не являются ложными, он включает в посылаемое для В сообщение непредсказуемый элемент (запрос). При ответе пользователь В должен выполнить некоторую операцию над этим элементом (например, добавить 1). Это невозможно осуществить заранее, так как не известно, какое случайное число придет в запросе. После получения ответа с результатами действий пользователь А может быть уверен, что сеанс является подлинным. Недостатком этого метода является возможность установления хотя и сложной закономерности между запросом и ответом.

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

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

При использовании отметок времени встает проблема допустимого временного интервала задержки для подтверждения подлинности сеанса. Ведь сообщение с “временным штемпелем” в принципе не может быть передано мгновенно. Кроме этого компьютерные часы получателя и отправителя не могут быть абсолютно синхронизированы. Какое запаздывание “штемпеля” считать подозрительным.

Поэтому в реальных ИС, например в системах оплаты кредитных карточек используется именно второй механизм установления подлинности и защиты от подделок. Используемый интервал составляет от одной до нескольких минут. Большое число известных способов кражи электронных денег, основано на “вклинивании” в этот промежуток с подложными запросами на снятии денег.

Для обмена ключами можно использовать криптосистемы с открытым ключом, используя тот же алгоритм RSA.

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

Алгоритм Диффи-Хеллмана

Диффи и Хелман предложили для создания криптографических систем с открытым ключом функцию дискретного возведения в степень.

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

Если y=x,, 1<x<p-1, где - фиксированный элемент поля GF(p), то x=log y над GF(p). Имея x, легко вычислить y. Для этого потребуется 2 ln(x+y) операций умножения.

Обратная задача вычисления x из y будет достаточно сложной. Если p выбрано достаточно правильно, то извлечение логарифма потребует вычислений, пропорциональных

L(p) = exp { (ln p ln ln p)0.5 }

Для обмена информацией первый пользователь выбирает случайное число x1, равновероятное из целых 1...p-1. Это число он держит в секрете, а другому пользователю посылает число

y1 = x mod p

Аналогично поступает и второй пользователь, генерируя x2 и вычислив y2, отправляя его первому пользователю. В результате этого они могут вычислять k₁₂ = x1x2 mod p.

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

Не зная x1 и x2, злоумышленник может попытаться вычислить k₁₂, зная только перехваченные y1 и y2. Эквивалентность этой проблемы проблеме вычисления дискретного логарифма есть главный и открытый вопрос в системах с открытым ключом. Простого решения до настоящего времени не найдено. Так, если для прямого преобразования 1000-битных простых чисел требуется 2000 операций, то для обратного преобразования (вычисления логарифма в поле Галуа) - потребуется около 1030 операций.

Как видно, при всей простоте алгоритма Диффи-Хелмана, вторым его недостатком по сравнению с системой RSA является отсутствие гарантированной нижней оценки трудоемкости раскрытия ключа.

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

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

возможность отказа от центра распределения ключей;

взаимное подтверждение подлинности участников сеанса;

подтверждение достоверности сеанса механизмом запроса-ответа, использование для этого программных или аппаратных средств;

использование при обмене ключами минимального числа сообщений.

Использование “блуждающих ключей”

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

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

Идея метода достаточно проста.

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

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

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

Наиболее доступным является использование полей Галуа. За счет возведения в степень порождающего элемента можно последовательно переходить от одного числа к другому. Эти числа принимаются в качестве ключей.

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

Надежность таких методов должна быть обеспечена с учетом известности злоумышленнику используемого правила смены ключей.

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

Формальный анализ протоколов проверки подлинности и обмена ключами

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

Существует четыре основных подхода к анализу криптографических протоколов:

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

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

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

Разработка формальных методов, основанных на записи свойств криптографических систем в алгебраическом виде.

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

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

Третий подход гораздо популярнее. Он был впервые введен Майклом Бэрроузом, Мартином Абэди и Роджером Неедхэмом. Они разработали формальную логическую модель для анализа знания и доверия, названную БАН-логикой БАН-логика является наиболее широко распространена при анализе протоколов проверки подлинности. Она рассматривает подлинность как функцию от цeлостности и новизны, используя логические правила для отслеживания состояния этих атрибутов на протяжении всего протокола. Хотя были предложены различные варианты и расширения, большинство разработчиков пр o-токолов до сих пор обращаются к оригинальной работе.

БАН-логика не предоставляет доказательство безопасности, она может только рассуждать о проверке подлинности. Она является простой, прямолинейной логикой, легкой в применении и полезной при поиске "дыр" . Вот некоторые предложения БАН-логики:

A считает X (A действует, как если бы X являлось истиной )

A видит X (Кто-то послал сообщение, содержащее X, А, который может прочитать и снова передать X - возможно после дешифрирования )

A сказал X (В некоторый момент времени A послал сообщение, которое содержит предложение X Не известно, как давно было послано сообщение, и было ли оно послано в течении текущего выполнения протокола Известно, что A считал X, когда говорил X )

И так далее. БАН-логика также предоставляет правила для рассуждения о доверии протоколу. Для доказательства чего-либо в протоколе или для ответа на какие-то вопросы к логическим предложениям о протоколе можно применить эти правила. Например, одним из правил является правило о значении сообщения:

Если A считает, что у A и B общий секретный ключ, К, и A видит X, шифрованное К, и A не шифровала Хc помощью К, TO A считает, что B сказал X

Другим является правило подтверждения метки времени:

Если A считает, что X могло быть сказано только недавно, и, что B X когда-то сказал X, TO A считает, что B считает X

БАН-анализ делится на четыре этапа:

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

Добавьте все предположения о начальном состоянии протокола.

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

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

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

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

Ну кажется все! Можно переходить к третьей части:

Практика

Стандарт шифрования данных DES (Data Encryption Standard)

Стандарт шифрования данных DES (Data Encryption Standard), который ANSI называет Алгоритмом шифрования данных DEA (Data Encryption Algorithm), a ISO - DEA-1, за 20 лет стал мировым стандартом. Хотя на нем и появился налет старости, он весьма прилично выдержал годы криптоанализа и все еще остается безопаcным по отношению ко всем врагам, кроме, возможно, самых могущественных

В 1972 году Национальное Бюро Стандартов (National Bureau of Standards- NSA, аналог ГОСТ ), выступило инициатором программы защиты линий связи и компьютерных данных. Одной из целей этой программы была разработка единого, стандартного криптографического алгоритма. Этот алгоритм мог бы быть проверен и сеpтифицирован, а использующие его различные криптографические устройства могли бы взаимодействовать. Он мог бы, к тому же, быть относительно недорогим и легко доступным.

15 мая 1973 года в Federal Register НБС опубликовало требования к криптографическому алгоритму, котoрый мог бы быть принят в качестве стандарта. Было приведено несколько критериев оценки проекта:

Алгоритм должен обеспечивать высокий уровень безопасности.

Алгоритм должен быть полностью определен и легко понятен.

Безопасность алгоритма должна основываться на ключе и не должна зависеть от сохранения в тайне сaмого алгоритма.

Алгоритм должен быть доступен всем пользователям.

Алгоритм должен позволять адаптацию к различным применениям.

Алгоритм должен позволять экономичную реализацию в виде электронных приборов.

Алгоритм должен быть эффективным в использовании.

Алгоритм должен предоставлять возможности проверки.

Алгоритм должен быть разрешен для экспорта.

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

27 августа 1972 года в Federal Register НБС опубликовало повторное предложение. Наконец, у Бюро появился подходящий кандидат: алгоритм под именем Люцифер, в основе которого лежала разработка компании IBM, выполненная в начале 70-х. В IBM существовала целая команда криптографов, работавшая в Кингстоне (Kingston) и Иорктаун Хайтс (Yorktown Heights), в которую входили Рой Адлер, Дон Копперсмит? Хорст Фейстель, Эдна Кроссман, Алан Конхейм , Карл Майер, Билл Ноц, Линн Смит, Уолт Тачмен и Брайант Такерман .Несмотря на определенную сложность алгоритм был прямолинеен. Он использовал только простые логические операции над небольшими группами битов и мог быть довольно эффективно реализован в аппаратуре.

В стандарте DES было оговорено, что он будет пересматриваться каждые пять лет. В 1983 DES был повтоpно сертифицирован без всяких проблем. 6 марта 1987 года в Federal Register НБС попросило прокомментирoвать предложение на следующие пять лет. НБС предложило на обсуждение следующие три альтернативы : вновь подтвердить стандарт на следующие пять лет, отказаться от стандарта или пересмотреть применимость стандарта.

НБС и АНБ пересмотрели стандарт. В этот раз АНБ было задействовано в большей степени. Первоначально АНБ объявило, что оно не сертифицирует стандарт повторно. Проблема была не в том, что DES действительно был взломан, и даже не в том, что он, может быть, был взломан. По видимoму, предполагалось, что он вот-вот будет взломан.

Описание DES

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

Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент врeмени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определяется ключом.

На простейшем уровне алгоритм не представляет ничего большего, чем комбинация двух основных методов шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов (подстановка, а за ней - перестановка), зависящей от ключа. Такой блок называется этапом. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз



Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-x. Изобилие повторений в алгоритме делает его идeальным для реализации в специализированной микросхеме. Первоначальные программные реализации были довольно неуклюжи, но сегодняшние программы намного лучше.

Схема алгоритма

DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называeмых функцией f, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая половины объединяются и алгоритм завершается

заключительной перестановкой (обратной по отношению к первонaчальной).

На каждом этапе биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Прaвая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется п o-средством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 нoвых бита, и переставляется снова. Эти четыре операции и выполняются функцией f. Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая пoловина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов

Если В_i - это результат i-ой итерации, L_i и R_i - левая и правая половины B_i K_i - 48-битовый ключ для этапа i, a f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:

L_i = R_i-1

Ri=L_i-1 f(R_i-1,K_i)

Начальная перестановка

Начальная перестановка выполняется еще до этапа 1, при этом входной блок переставляется, как показано в 11-й. Эту и все другие таблицы этой главы надо читать слева направо и сверху вниз. Например, начальная пер eстановка перемещает бит 58 в битовую позицию 1, бит 50 - в битовую позицию 2, бит 42 - в битовую позицию 3, и так далее.

Начальная перестановка

58,	50,	42,	34,	26,	18,	10,	2,	60,	52,	44,	36,	28,	20,	12,	4,
62,	54,	46,	38,	30,	22,	14,	6,	64,	56,	48,	40,	32,	24,	16,	8,
57,	49,	41,	33,	25,	17,	9,	1,	59,	51,	43,	35,	27,	19,	И,	3,
61,	53,	45,	37,	29,	21,	13,	5,	63,	55,	47,	39,	31,	23,	15,	7

Начальная перестановка и соответствующая заключительная перестановка не влияют на безопасность DES. (Как можно легко заметить, эта перестановка в первую очередь служит для облегчения побайтной загрузки данных открытого текста и шифротекста в микросхему DES. Не забывайте, что DES появился раньше 16- и 32-битовых микропроцессорных шин.) Так как программная реализация этой многобитовой перестановки нелегка (в отличие от тривиальной аппаратной), во многих программных реализациях DES начальная и заключительные перестановки не используются. Хотя такой новый алгоритм не менее безопасен, чем DES, он не соответствует стандарту DES и, поэтому, не может называться DES.

Преобразования ключа

Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита, как показано в 10-й. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый подключ. Эти подключи, K_i определяются следующим образом.

Перестановка ключа

57,	49,	41,	33,	25,	17,	9,	1,	58,	50,	42,	34,	26,	18,
10,	2	59,	51,	43,	35,	27,	19,	11,	3,	60,	52,	44,	36,
63,	55,	47,	39,	31,	23,	15,	7,	62,	54,	46,	38,	30,	22,
14,	6,	61,	53,	45,	37,	29,	21,	13,	5,	28,	20,	12,	4

Во первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвигaются налево на один или два бита в зависимости от этапа. Этот сдвиг показан в 9-й.

Число битов сдвига ключа в зависимости от этапа

Этап	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Число	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция называется перестановка со сжатием. Ее результатом является набор из 48 битов. Перестановка со сжатием (также называемая переставленным выбором) определена в 8-й. Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отборaсывается.

Перестановка со сжатием

14,	17,	11,	2,4,	1,	5,	3,	28,	15,	6,	21,	10,
23,	19,	11,	4,	26,	8,	16,	7,	27,	20,	13,	2,
41,	52,	31,	37,	47,	55,	30,	40,	51,	45,	33,	48,
44,	49,	39,	56,	34,	53,	46,	42,	50,	36,	29,	32

Из-за сдвига для каждого подключа используется отличное подмножество битов ключа. Каждый бит используется приблизительно в 14 из 16 подключей, хотя не все биты используются в точности одинаковое число раз.

Перестановка с расширением

Эта операция расширяет правую половину данных, R_i от 32 до 48 битов. Так как при этом не просто повторяются определенные биты, но и изменяется их порядок, эта операция называется перестановкой с расширением. У нее две задачи: привести размер правой половины в соответствие с ключом для операции XOR и полyчить более длинный результат, который можно будет сжать в ходе операции подстановки. Однако главный криптографический смысл совсем в другом. За счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Это называется лавинным эффектом. DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита открытого текста и каждого бита ключа.

Перестановка с расширением показана на 6- ом рисунке. Иногда она называется Е-блоком (от expansion). Для каждого 4-битового входного блока первый и четвертый бит представляют собой два бита выходного блока, а второй и третий биты - один бит выходного блока. В 7-й показано, какие позиции результата соответствуют каким поз и-циям исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока.

Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.

Перестановка с расширением

32,	1,	2,	3,	4,	5,	4,	5,	6,	7,	8,	9,
8,	9,	10,	11,	12.,	13,	12,	13,	14,	15,	16,	17,
16,	17,	18,	19,	20,	21,	20,	21,	22,	23,	24,	25,
24,	25,	26,	27,	28,	29,	28,	29,	30,	31,	32,	1

Подстановка с помощью S-блоков

После объединения сжатого блока с расширенным блоком с помощью XOR над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках (от substitution). У каждого S-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти.) 48 битов делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, втoрой - S-блоком 2, и так далее.

Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4-битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное значение. Все восемь S-блоков показаны в 6-й.

Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: b₁, b₂, b₃, b4 b₅ и b₆. Биты b₁ и b₆, объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы. Средние 4 бита, с b₂ по b₅, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу таблицы.

Например, пусть на вход шестого S-блока (т.е., биты функции XOR с 31 по 36) попадает 110011. Первый и последний бит, объединяясь, образуют 11, что соответствует строке 3 шестого S-блока. Средние 4 бита образyют 1001, что соответствует столбцу 9 того же S-блока. Элемент S-блока 6, находящийся на пересечении строки 3 и столбца 9, - это 14. (Не забывайте, что строки и столбцы нумеруются с 0, а не с 1.) Вместо 110011 подставляется 1110.

Конечно же, намного легче реализовать S-блоки программно в виде массивов с 64 элементами. Для этого потребуется переупорядочить элементы, что не является трудной задачей. Изменить индексы, не изменяя порядок элементов, недостаточно. S-блоки спроектированы очень тщательно. Однако такой способ описания S-блоков помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4-битового элемента: b₂ по b₅ являются входом, а некоторое 4-битовое число - результатом. Биты b₁ и b₆ определяются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном S-блоке.

Подстановка с помощью S-блоков является ключевым этапом DES. Другие действия алгоритма линейны и легко поддаются анализу. S-блоки нелинейны, и именно они в большей степени, чем все остальное, обеспечивают безопасность DES.

В результате этого этапа подстановки получаются восемь 4-битовых блоков, которые вновь объединяются в единый 32-битовый блок. Этот блок поступает на вход следующего этапа - перестановки с помощью Р-блоков.

Перестановка с помощью Р-блоков