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

При построении криптосистемы исходный текст должен состоять из p - разрядных блоков, в каждом из которых сумма элементов равняется h. Для того чтобы обеспечить это условие, необходимо после кодирования букв сообщений произвести перекодирование равновесными кодами длины p веса h (следует отметить, что значения элементов равны 0,1,2,...,p-1)

Пример 1.

Путь имеем поле F(3²) и a корень уравнения x² = x +1.Выберем образующую g = 2 a + 1. Так как логарифмы элементов a, a + 1, a + 2 есть соответственно 3,6 и 5, то вектор A = (3 6 5). Исходные тексты есть векторы размерности 3 с суммой компонент равной 2. Возьмем такие векторы исходного текста: (2 0 0), (0 1 1), (0 2 0), (1 0 1). Произведем шифрование исходных текстов:

Это и будет криптотекст.

Напомним, что мы производим вычисления по модулю p^h - 1. В данном случае по модулю 8. Легальный получатель вычисляет:

(2a + 1)⁶ = a + 1,

(2a + 1)³ = a,

(2a + 1)⁴ = 2

(2a + 1)⁸ = 1

Если к полученным степеням прибавлять многочлен a² - a - 1, получим соответственно:

a² , a² - 1 = (a + 1)( a + 2), 2 = (a² - a + 1) = (a + 1)(a + 1); 1 = a² - a = a (a + 2). Откуда получаем исходные коды:

(2 0 0), ( 0 1 1), ( 0 2 0), ( 1 0 1).

Открытым ключом являются A, p, h. Секретной лазейкой являются a и g.

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

Пример 2.

Возьмем конечное поле F(64) = F(2⁶). Здесь p = 2, h = 6. Многочлен x⁶ - x - 1 неприводим над полем F(2), так как ни 0, ни 1 не обращают его в 0. Кстати, при p =2 операции + и - равнозначны. Следовательно, все элементы поля F(2⁶) могут быть представлены через корень a этого многочлена. Более конкретно, все 64 элемента поля F(2⁶) могут быть представлены в виде

x_ia^6-i, где x_i Î {0,1}

Обычно элементы поля при p = 2 представляются как двоичные наборы длины 6. Так, a⁴ + a² + a + 1 представляется набором: 0 1 0 1 1 1. Возьмем образующую поля g = a - корню неприводимого многочлена. Тогда таблица логарифмов может быть представлена следующим образом:

Поскольку log_aa = 1 , а log_a(a + 1) = 6, то вектор A = (1 6). Введем еще шум в виде дополнительного сдвига на d = 60. В результате получим открытый вектор B = (61 3), так как элементы bi вычисляются следующим образом:

b_i º a_i * d mod (2⁶ – 1). Исходными векторами являются векторы (x, y) в которых x + y = 6. Используя открытый ключ зашифрования B и p = 2, h = 6 зашифруем векторы исходного текста:

Легальный получатель вычитает из каждого шифрованного сообщения hd по модулю 63 и получает следующий набор чисел:

51 - 6*60 º 6 mod 63,

13 - 360 º 31 mod 63,

8 - 360 º 26 mod 63,

3 - 360 º 21 mod 63,

61 - 360 º 16 mod 63,

56 - 360 º 11 mod 63,

18 - 360 º 36 mod 63.

Из таблицы логарифмов получаем:

a⁶ = a + 1 = a⁶

a³¹ = a⁵ + a + 1 = a (a + 1)⁵

a²⁶ = a² + a + 1 = a²(a + 1)⁴

a²¹ = a⁵ + a⁴ + a³ + a + 1 = a³(a+ 1)³ (*)

a¹⁶ = a⁴ + a + 1 = a⁴(a + 1)²

a¹¹ = a⁵ + a + 1 = a⁵(a + 1)

a³⁶ = a⁴ + a² + a = (a + 1)⁶.

Для получения значений (*) заметим, что правая часть должна быть представлена в виде: a^k(a + 1)^6-k, где k = 1,2,3,4,5,6. В левой части имеются значения a^x, где x = 6,31,26,21,16,11,36. Таким образом при преобразовании (*) решаются уравнения: a^x = a^k(a + 1)^6-k. Если прологарифмировать его по основанию a, то получим: x = k + (6-k)log_a (a + 1). Из таблицы дискретных логарифмов находим: log_a (a + 1) = 6, следовательно, x = 36 – 5k, откуда получаем k = (36-x)/5. Вычисляем:

a⁶ (x = 6) = a⁶,

a³¹(x =31) = a(a + 1)⁵ ,

a²⁶( x = 26) = a²(a + 1)⁴ и т.д.

После этого сразу же получаем исходный кодовый набор:

Пример 3.

Рассмотрим самый общий случай шифрования с использованием конечных полей Галуа. Пусть p = 5, h = 2. Поле F(5²) содержит 25 элементов. Легко проверяется, что неприводимым полиномом в подполе F(5) основного поля является многочлен X² + 2, так как никаким из 5 элементов (0,1,2,3,4) он не обращается в 0. Пусть a - корень полинома. При вычислениях будем производить замену a² = 3 (поскольку –2 º 3 mod 5). Порождающим элементом является g = a + 1, что легко проверяется. Составим таблицу логарифмов для элементов поля F*(5²), где исключен только элемент равный 0. Так как все элементы поля будут представляться в виде a₁a + a₂, где a₁ и a₂ Î {0,1,2,3,4}, то таблица логарифмов будет выглядеть следующим образом:

Элемент	Лога-рифм	Элемент	Лога-рифм	Элемент	Лога- рифм
00		20	21	40	15
01	24	21	22	41	5
02	18	22	19	42	16
03	6	23	11	43	20
04	12	24	2	44	13
10	3	30	9
11	1	31	14
12	8	32	23
13	4	33	7
14	17	34	10

Составим вектор A по правилу: элемент a_i = (a + i - 1), где i = 1,2,3,4,5.

Тогда получим

a₁ = log_g(a + 0) = 3,

a₂ = log_g(a + 1) = 1,

a₃ = log_g(a + 2) = 8,

a₄ = log_g(a + 3) = 4,

a₅ = log_g(a + 4) =17.

Вектор A = (3 1 8 4 17). Сначала введем преобразование p элементов вектора, например, по такому правилу подстановок:

, тогда получим вектор A’ = pA = (1 17 4 8 3).

Введем шумовую составляющую в виде сдвига d = 20 (по модулю 5²-1 =24) всех элементов вектора A’, в результате получим открытый вектор B:

B = ( 21 13 0 4 23).

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

По каналу связи передается зашифрованное сообщение: 21 12 2 8 0. Кроме того, открытым ключом также являются p = 5 и h = 2. Легальный получатель, кроме того, знает d, g и p. Поэтому он сразу приступает к расшифровыванию сообщения. Он вычитает из полученных чисел шум hd по модулю 24:

21 - 2*20 º 5 mod 24.

12 - 2*20 º 20 mod 24.

2 - 2*20 º 10 mod 24.

8 - 2*20 º 16 mod 24.

0 - 2*20 º 8 mod 24.

Затем легальный получатель по таблице логарифмов находит значения g = (a + 1)^x, где x - степени, выделенные жирным шрифтом в последних вычислениях. Добавляет к полученному выражению a²+ 2 и раскладывает результат на два множителя:

(a + 1)⁵ = 4a + 1 + a² + 2 = a²+ 4a + 3 = (a + 1) (a + 3)

(a + 1)²⁰= 4a + 3 + a² + 2 = a² + 4a = a(a + 4)

(a + 1)¹⁰= 3a + 4 + a² + 2 = a² +3a + 1 = (a + 4)²

(a + 1)¹⁶= 4a + 2+ a² + 2 = a² + 4a + 4 = (a + 2)²

(a + 1)⁸ = a + 2 + a² + 2 = a² + a + 4 = (a + 3)²

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

.

После перестановки получаем исходное сообщение: .

Плотность построенного рюкзачного вектора равна:

2.3. Простейшие криптосистемы с открытым ключом

2.3.1. Двухступенчатая передача сообщений с использованием модульной арифметики [ 2, Приложение 1]

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

Рассмотрим сначала случай, когда по открытому каналу Алиса и Боб договариваются использовать для шифрования своих сообщений некоторое очень большое простое число P. Пусть, например, P имеет 100 десятичных знаков. Тогда Алиса может зашифровать сообщение m возведением в некоторую степень x, известную только ей, и передать Бобу. Боб может возвести полученное сообщение в степень y, известную только ему и возвратить Алисе. Алиса “снимет” свою степень x и передаст сообщение Бобу. Боб “снимет” свою степень y и прочитает сообщение.

Общая схема выглядит следующим образом:

Алиса берет сообщение m, которое хочет передать Бобу, возводит в некоторую степень x, при этом (x, P-1) = 1, т.е. x и P-1 взаимно простые числа:

m^x  S₁ mod P

и передает S₁ Бобу.

Б об возводит S₁ в некоторую степень y, (y, P-1) = 1:  m^xy  S₂ mod P

и возвращает S₂ Алисе.

Алиса должна снять свой ключ x, для этого она должна извлечь корень степени x из S₂. Это можно сделать при учете, что (x, P-1) = 1 следующим образом.

Если возвести S₂ в степень , где t₁- некоторое целое, такое, что числитель дроби k₁ делится на x нацело, то в результате будет получено значение

m ^y  S₃ mod P.

Это значение (S₃) Алиса передает Бобу.

Для того чтобы снять свой ключ, Боб может возвести S₃ в степень

и в результате восстановит исходное сообщение m.

Пример. Пусть P = 103. P-1 = 102 = 2*51. Алиса хочет передать сообщение m = 83. Алиса возводит число 83 в известную только ей степень, например, x = 35, (35,102)=1:

83³⁵  (((((83)²)²)²)²)²*(83)²*83  ((((91)²)²)²)²*91*83  (((41)²)²)²* 34  ((33)²)²* 34  (59)²*34  7 mod 103 и результат (число 7) передает Бобу. Боб полученное число возводит в известную только ему степень, например, y = 41 (это число также взаимно просто с 102):

(7)⁴¹  ((7³)³)³*(7³)³*7³*7²  (34³)³*34*49  61³*61*18  55 mod 103 и результат (55) возвращает Алисе. Алиса “снимает” свою степень x, решая сравнение:

и возводя число 55 в степень 35:

(55)³⁵  (((55³)³)³* (((55²)²)²  (30³)³* (38²)²  14³*2²  58 mod 103. Результат (число 58) Алиса передает Бобу. Боб “снимает” свою степень y, решая сравнение:

и возводя число 58 в степень 5:

(58)⁵  (58²)²*58  68²*58 83 mod 103, получает сообщение, которое было адресовано ему Алисой. Таким образом, Боб расшифровал переданное сообщение, а незаконный перехватчик, получив все числа, которыми обменивались Алиса и Боб, не сумеет расшифровать это сообщение.

2.3.2. Формирование общего ключа по открытому каналу

Для формирования общего ключа по открытому каналу можно воспользоваться идеей Диффи и Хэллмана [2]. Пусть Алиса и Боб договорились использовать некоторое очень большое простое число Р в качестве модуля. Кроме того, Алиса и Боб для этого числа Р выбрали первообразный корень g, т.е. такое число, что для него самое малое число а, удовлетворяющее сравнению: g^а  1 mod Р, равно а = Р-1.

Алиса берет первообразный корень g, возводит его в степень, известную только Алисе, находит остаток по модулю Р:  S₁ mod P и открыто передает остаток S₁ Бобу.

Боб возводит первообразный корень g в известную только ему степень k₂, получает остаток S₂ по модулю Р и передает S₂ Алисе. Далее Алиса возводит S₂ в степень к₂, а Боб возводит S₁ в степень k₂ по модулю Р и оба получают один и тот же ключ K = mod P. Далее Алиса и Боб могут воспользоваться этим общим ключом, например, при применении симметричной криптосистемы DES. При необходимости произвести смену ключа операция обмена повторяется, при этом k₁ и k₂ выбираются заново.

Пример. Пусть P = 103. Первообразным корнем для данного P будет g = 2. Чтобы это проверить, представим P-1 в канонической форме: 102 = 2*51. Так как ни 2², ни 2⁵¹ не сравнимы с 1 по модулю 103, то 102 является самой минимальной степенью, которая обеспечивает сравнение: 2¹⁰²  1 mod 103 (теорема Ферма). Пусть Алиса выбрала к₁ = 7, а Боб выбрал к₂ = 11. Тогда они обменяются следующими данными:

2⁷  25 mod 103

2¹¹  91 mod 103

И оба выработают один и тот же ключ:

Алиса: 91⁷  38 mod 103 Боб: 25¹¹  38 mod 103

Незаконный перехватчик, зная P и g и перехватив S₁ и S₂, не сумеет вычислить значение общего ключа mod P. Эта уверенность исходит из следующих соображений.