Материал: Раздел 2.Криптографические системы с открытым ключом

15

Раздел 2. Криптографические системы с открытым ключом

Криптосистемы, описанные в Разделе 1, имеют очень серьезный недостаток. По алгоритму зашифрования можно найти алгоритм расшифрования. Поэтому ключи должны храниться в строжайшем секрете или передаваться от отправителя к получателю по сверхсекретной почте. Даже в очень сложной системе DES ключи зашифрования и расшифрования совпадают. Часто ключ по длине равен сообщению, поэтому возникает вопрос, а не проще ли вместо передачи ключей передавать по сверхсекретной почте само сообщение? Конечно, это целесообразно далеко не во всех случаях. Например, ключ можно передать заранее, когда сообщение еще не сформировано или воспользоваться одним и тем же ключом несколько раз.

2.1. Идея криптосистем с открытым ключом

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

Идея основана на использовании так называемых односторонних функций. Пусть по аргументу x легко вычисляется функция f(x). А по значениям f(x) аргумент x вычисляется очень трудно. Тогда перехватив сообщение f(x) недоброжелатель не сможет легко найти x - истинное передаваемое сообщение. Однако, эти трудности, казалось бы, будут и для легального получателя сообщения? Но для него предлагается оставить «лазейку» в виде некоторых знаний, которые помогут ему быстро расшифровать полученное сообщение.

Одним из хороших примеров, иллюстрирующих эту идею, является следующий.

Для ловли рыбы в северных странах используются так называемые «морды» - плетеные корзины с конусообразным углублением с одной стороны и меленьким отверстием в центре этого углубления. Рыба легко заходит в эту корзину, а обратный выход из нее найти рыбе трудно. В то же время рыбак открывает заднюю крышку и легко выбирает рыбу.

Другим примером открытого распределения ключей может служить следующий: Отправитель секретного сообщения помещает его в чемодан, вешает открытый замок, ключ от которого есть только у него (такого ключа нет даже у получателя сообщения) и открыто, например, по почте посылает его получателю B. Получатель B, не открывая чемодана, навешивает на него свой замок, ключ от которого имеется только у него и возвращает чемодан с двумя замками отправителю A. Отправитель А снимает свой замок и еще раз отправляет чемодан получателю B (на чемодане теперь есть только один замок, ключ от которого есть у B). Получатель B снимает свой замок и достает из чемодана секретное сообщение. Эта система необычайно проста и остроумна. К сожалению, она защищает только от пассивного перехватчика. Активный же перехватчик, получив чемодан на почте, может замаскироваться под истинного получателя, навесить свой замок и, в конце концов, получить доступ к секретному сообщению.

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

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

Шифруемая буква сообщения	фамилия абонента	телефон абонента
С	Соловьев	5830247
О	Омельченко	1432576
В	Владимиров	3523397
Е	Евдокимов	2355495
Р	Родионов	1152843
Ш	Шапиро	4326567
Е	Емельянов	3768789
Н	Новиков	1754328
Н	Николаев	5377891
О	Осипов	2844390
С	Сасковец	3155639
Е	Есиков	4166720
К	Коновалов	1944267
Р	Ресин	2255129
Е	Елкин	4933221
Т	Тимофеев	2288546
Н	Никитин	2190032
О	Окунев	3811020

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

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

FACTOR (n). Найти разложение большого числа n на множители.

PRIMALITY (n). Решить вопрос о том, является ли n простым числом?

FIND-PRIME (>n). Найти простое число большее n.

SQUAREFREENESS (n). Решить, делит или нет квадрат простого числа число n?

QUAD-RESIDUE (a, n) Решить, выполняется или нет сравнение

x² º a mod n для некоторого x?

SQUAREROOT (a, n). Найти, если возможно, такое число x, что

x² º a mod n.

DISCRETE-LOG (a,b,n). Найти, если возможно, такое x, что a^x º b mod n.

Общий прием, используемый при построении криптосистем с открытым

ключом, состоит в следующем:

1. Выбирается односторонняя функция, такая, что по x легко находится f(x), но по f(x) значение x находится очень трудно. Функция f(x) объявляется открыто.

2. Находится легкая подзадача определения по f(x) значения x.

3. Значения передаваемой функции f(x) перемешиваются («взбиваются») так, чтобы для криптоаналитика она выглядела как труднорешаемая, а для легального получателя открывается способ сведения передаваемых значений функции к легкой подзадаче, что является «лазейкой» для него.

Очень показательными в этом случае являются так называемые «рюкзачные» криптосистемы, к рассмотрению которых мы и переходим.

2.2. Рюкзачные криптосистемы

Рассмотрим вектор A = (a₁ a₂ a₃ ...a_i ... a_n), где a_i - различные целые положительные числа. Пусть, кроме того, задано некоторое положительное число k. Поставим задачу: выбрать числа a_i среди элементов вектора A, такие, чтобы их сумма в точности равнялась k. В этом случае можно говорить, что k определяет размер рюкзака, а выбранные a_i - размеры предметов, которые помещаются в рюкзак.

Пусть вектор A = (43 129 215 473 903 302 561 1165 697 1523), а k = 3231. C помощью перебора можно найти: 3231 = 129 + 473+ 903+ 561+1165.

С другой стороны, если взять вектор столбец вида (0 1 0 1 1 0 1 1 0 0) и умножить вектор строку A на этот вектор столбец:

то получим значение k.

Если каждую букву английского алфавита закодировать двоичным пяти - разрядным кодом и разбить передаваемое сообщение на пары букв, то каждая пара будет кодироваться 10-ю двоичными символами. Будем умножать вектор строку A на векторы столбцы кодов пар букв, при этом будем получать шифрованное сообщение k₁ k₂ k₃ ... Шифрование осуществляется очень просто, а вот для расшифровки полученного сообщения потребуется решать задачу о рюкзаке: по значению k находить двоичный 10-и разрядный вектор столбец, при умножении на который вектора строки A будет получено данное k. Эта задача явно односторонняя: легкое шифрование и очень трудное расшифрование. В принципе можно ее решать с помощью полного перебора (2¹⁰ вариантов). Однако трудности расшифрования будут одинаковыми как для криптоаналитика, так и для легального получателя, что, безусловно, нежелательно. Для того чтобы облегчить легальному получателю расшифровку сообщения нужно предложить ему «лазейку». В данном случае «лазейка» может быть устроена следующим образом. Рассмотрим сверхрастущие векторы A = (a₁ a₂ a₃ ...a_i ... a_n), в которых , т.е. каждый элемент вектора A больше суммы всех предыдущих элементов. Например, A = (25 27 56 112 231 452 916 1803). Нахождение элементов вектора A, сумма которых дает заданное число k, элементарно (если такое решение имеется). Действительно, пусть k = 1449. Поскольку 1449<1803, то последний элемент вектора не входит в решение. Далее, так как 1449>916, то 916 обязательно входит в решение, так как сумма всех предыдущих элементов меньше 916. Рассуждая аналогично, получаем код позиций выбираемых элементов: (1 0 1 0 0 1 1 0). Однако если опубликовать этот сверхрастущий вектор, то и для криптоаналитика задача расшифрования сообщений станет элементарной. Тогда мы преобразуем сверхрастущий вектор A в вектор B по следующему правилу: выберем некоторый модуль m больший суммы всех элементов A, возьмем некоторое t, такое, что (t,m) = 1 и каждый элемент вектора B будем вычислять по правилу:

b_i º a_i *t mod m. Вектор B уже не будет казаться сверхрастущим, и он может быть опубликован в качестве открытого ключа. А в качестве «лазейки» для легального пользователя сообщим ему значения t и m.

Пример использования рюкзачных систем для криптографии с открытым

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

Пусть A - сверхрастущая последовательность чисел: (1 2 4 8 16).

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

пятиразрядные двоичные коды:

w₁ = (1 0 1 1 0); w₂ = ( 0 1 1 0 1); w₃ = ( 1 0 0 0 1).

Выполним сильное модульное преобразование вектора A. Для этого выберем значение модуля m так, чтобы он был больше суммы всех a_i. Одновременно нужно выбрать t так, чтобы (t,m) = 1. При этом желательно, чтобы даже первые значения a_it были бы больше модуля m (чтобы и по ним нельзя было бы сразу определить t). Выбираем t = 40 и m = 37.

Элементы вектора B получаются следующим образом: b_i º a_it mod m. Сам вектор B = (3 6 12 24 11). Он уже не является сверхрастущим вектором, поэтому криптоанализ будет затруднен. Умножая вектор B на матрицу, составленную из двоичных векторов w_i , получаем зашифрованный текст:

где x- вектор шифрованного сообщения

Именно этот шифрованный текст передается по каналу связи и может быть перехвачен криптоаналитиком. Кроме того, считается, что ключ (вектор B) также открыто сообщается всем (как получателю сообщения, так и может быть перехвачен любым пользователем сети). Значения t и m являются «лазейкой» для легального получателя сообщений. Он находит значение u такое, что t*u º 1 mod m. В нашем случае легко находится u = 25, так как 40*25 º 1 mod 37.

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

39*25 º 13 mod 37; 29*25 º 22 mod 37; 14*25 º17 mod 37. Теперь получатель имеет вектор x’= (13 22 17) и ему остается вычислить исходный вектор A, зная вектор B и u:

3*25 º 1 mod 37; 6*25 º 2 mod 37; 12*25 º 4 mod 37; 24*25 º 8 mod 37; 11*25 º 16 mod 37. Исходный вектор A = (1 2 4 8 16) является сверхрастущим, поэтому по вектору A и x’ легко дешифрируется переданное сообщение:

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

Так, для сверхрастущего вектора A = (1 2 4 8 16 32 64) d(A) = 7/6.

Увеличить плотность рюкзачного вектора можно с использованием полей полиномов Галуа GF(p^h), где p - простое, h – целое [ 12, Приложение 2 ].

Конечное поле F(p^h) содержит p^h элементов. Основное поле F(p) , которое является подполем поля F(p^h) содержит p элемента (0,1,2,3,...,p-1) и 2 операции: Å mod p и Ä mod p.

Элемент a называется алгебраическим степени h над полем F(p) если и только если a удовлетворяет в F(p) уравнению: P(x) = 0, где P(x) - многочлен степени h, но не удовлетворяет никакому уравнению с многочленом меньшей степени. Это влечет неприводимость многочлена P(x). Все p^h элементов поля

F(p^h ) могут быть представлены в виде:

å c_jaⁱ , где 0 £ c_j £ p-1; 0 £ aⁱ £ h-1.

При вычислениях степень a^s, где s ³ h заменяется на меньшую в соответствии с уравнением P(a) = 0.

Пусть, например, p = 3 , h = 2 и a удовлетворяет уравнению x² - x - 1 = 0. Элементы поля F(3²) можно выразить как:

0,1,2, a,a + 1, a+ 2, 2a, 2a + 1, 2a + 2.

В вычислениях понижение степеней производится с использованием равенства a² = a + 1. Например, (2a + 1)(a+ 2) = 2a² + a+ 4a+ 2 = 2(a + 1) + 5a + 2 = 7a + 4 = a + 1.

Элемент b ¹ 0 поля F(p^h) называется образующей F^*(p^h) мультипликативной группы ненулевых элементов поля F(p^h), если степени bⁱ , i = 1,2,3,..., p^h - 1 пробегают все ненулевые элементы поля F(p^h). Образующая может рассматриваться как основание log. Такие логарифмы называются дискретными логарифмами. Рассмотрим, например, все 8 степеней корня a в приведенном выше примере и запишем результат в виде таблицы:

i 1 2 3 4 5 6 7 8

aⁱ a a + 1 2a+1 2 2a 2a+ 2 a + 2 1

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

y 1 2 a a + 1 a + 2 2a 2a + 1 2a + 2

log_a y 8 4 1 2 7 5 3 6

Считается, что вычисление дискретных логарифмов является трудной задачей, как и задача факторизации (разложения на множители). Таблица логарифмов может использоваться для выполнения умножения и деления элементов поля. Заметим, что операции выполняются по модулю p^h - 1, в данном примере по модулю 3² - 1 = 8. Для примера:

log ((a + 2)(2a + 1))= log(a + 2) + log(2a + 1) = 7 + 3 = 10 º 2 mod 8. Что соответствует элементу a + 1.

log ((a + 1)/( 2a + 2)) = 2 - 6 = -4 º 4 mod 8, что соответствует элементу 2.

Можно проверить, что кроме элемента a образующими также являются элементы 2a + 1, a + 2 и 2a. Если s = p^h - 1 есть наименьшая положительная степень, удовлетворяющая уравнению b^s = 1, то b является образующей. Поэтому число образующих элементов поля равно j(p^h-1), где j - функция Эйлера. Для нашего примера j (8) = 4.

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

A = (a₁ a₂ a₃ ...a_i ... a_n). Рассмотрим различные суммы элементов, состоящие ровно из h компонент. Задача состоит в том, чтобы для заданных n и h построить вектор A такой, чтобы все суммы из h элементов были бы попарно различны. Для рюкзаков низкой плотности это сделать легко: aⁱ = h^i-1, 1 £ i £ n. Например,

A = (1 2 4 8 16 32 64), h = 2, n = 7;

A = (1 3 9 27 81 243 729 2187 6561), h = 3, n = 9.

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

Такое построение векторов A соответствует рюкзакам низкой плотности, так как они являются сверхрастущими.

Пусть n = p - простое число. Показано, что для простого p и целого h ³ 2 всегда можно построить рюкзачный вектор A = (a₁ a₂ a₃ ...a_i ... a_P), удовлетворяющий следующим условиям:

1. 1 £ a_i £ p^h-1, для 1 £ i £ p.

2. Если x_i и y_i - неотрицательные целые числа, такие, что (x₁,x₂,...x_p) ¹ (y₁,y₂,...,y_p), но åx_i = åy_i = h, тогда

å x_ia_i ¹ å y_ia_{i (*)}

При построении вектора A можно взять a_i = log_g(a + i-1), 1 £ i £ p, где a- корень неприводимого многочлена, g - образующая группы F*(p^h).

Аналогичное построение может быть выполнено для n = p^s , где p - простое, s - целое. Кроме того, неравенство (*) может быть заменено на более сильное: å x_ia_i ¹ å y_ia_i mod (p^h-1).