Лекция №7 Алгоритмы с открытыми ключами

Концепция криптографии с открытыми ключами была выдвинута Диффе и Хэлменом и независимо от них Мерклом в 1976 году. Их вкладом в криптографию было убеждение, что ключи можно использовать парами(ключ зашифрования и ключ расшифрования), и что может быть не возможно получить один ключ из другого.

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

Алгоритм открытых рюкзаков(укладки ранца)

Первым алгоритмом для обобщенного шифрования с открытым ключом стал “алгоритм рюкзака”, разработанный Мерклом и Хелменом. Проблемы рюкзака состоит в следующем:

Дано n предметов различной массы, можно ли взять только часть предметов из них, таким образом, чтобы суммарная масса была равно некоторому числу S.

Mi – масса предметов, i=1,n

S = b1M1+b2M2+…+bnMn=Summ(от 1 до n)biMi

Bi = 0 или 1

1 : предмет кладут в рюкзак.

0: предмет не кладут в рюкзак.

Например, массы предметов могут иметь значения: 1, 5, 6, 11, 14, 20(2^6).

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

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

M : 111001 010110 011000

K: 156111420 156111420 56111420

C: 32 30 11(делим по 6 числе в блоке верхней строки, затем внизу выбираем из тех, чьими числами является единица и высчитываем число)

Главная идея состоит в том, что существуют 2 различные проблемы рюкзака с одни и тем же решением:

1. Решается за экспоненциальное время.

2. Решается за линейное время.

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

Сверх возрастающие рюкзаки

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

Пример:

Последовательность : 2, 3, 6, 13, 27, 52

S= 70

70>52 =>(берем 52)

70-52=18

18<27=>(НЕ БЕРЕМ 27)

18>13=>(берем 13)

18-13=5

5<6=>(не берем 6)

И т.д. получаем: 2, 3, 6, 13, 27, 52= 1, 1, 0, 1, 0, 1

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

Пример: Зашифрование и Расшифрование.

Этап 1. Создание открытого ключа из закрытого.

Чтобы получить нормальную последовательность рюкзака необходимо взять сверх возрастающую последовательность(например: 2, 3, 6, 13, 27, 52) и умножить по модулю m все значения на число n. Значения модуля должно быть больше суммы всех численных последовательностей(например m=105). Множитель n должен быть взаимно простым числом с модулем(например n=31).

2*31mod105=62

3*31mod105=93

6*31mod105=81

13*31mod105=88

27*31mod105=102

52*31mod105=37

K1: {62, 93, 81, 88, 102, 37}

Этап 2 Шифрование.

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

M=011000 110101 101110

C=174 280 333

Этап 3 Расшифрование.

Законный получатель сообщения C знает закрытый ключ K2, а так же значением m(105) и n(31), использованные для превращения ее в нормальную последовательность рюкзака. Для расшифрования сообщения получатель вначале должен определить значение (n^-1) такое, что (n*n^-1=1(mod105)).

31*n^-1=1(mod105)

31*n^-1=105*k+1(диафантовое уравнение, решаемое в целых числах)

Решается такое уравнение расширенным уравнением Эвклида:

31*n^-1=105*k+1

Прямой ход:

105=31*3+12

31=12*2+7

12=7*1+5

7=5*1+2

5=2*2+1

2=1*2+0

Обратный ход:

1=5-2*2=5-2*(7-5*1)= 5*3-7*2=(12-7*1)*3-7*2=12*3-7*5=12*3-(31-12*3)*5=12*13-31*5=(105-31*3)*13-31*5=105*13-31*44

N^-1=-44=61(mod105)

Значения шифр текста должны быть умножены на n^-1mod105

174*61(mod105)=9 в соответствии с закрытым ключом: 011000

280*61(mod105)=70 в соответствии с закрытым ключом: 110101

333*61(mod105)=48 в соответствии с закрытым ключом: 101110

Для последовательности из 6 элементов не трудно решить задачу рюкзака, даже если она не является сверх возрастающей. Реальные последовательности должны содержать не менее 250 элементов. Длина каждого элемента последовательности должна быть 200 и 400 битами, а длина модуля от 100 до 200 бит. Для получения значений практические реализации используют генератор случайных последовательностей.