Пример шифрования по алгоритму RSA

Открытое сообщение	символ	А	Б	Р	А	М	О	В
Код символа
Шифрограмма, С = Т5 mod 91
Открытое сообщение, Т = С29 mod 91

 

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

В заключении следует отметить стойкость данного алгоритма. В 2003 г. Ади Шамир и Эран Тромер разработали схему устройства TWIRL, которое при стоимости $ 10 000 может дешифровать 512-битный ключ за 10 минут, а при стоимости $ 10 000 000 – 1024-битный ключ меньше, чем за год. В настоящее время Лаборатория RSA рекомендует использовать ключи размером 2048 битов.

Алгоритм шифрования Эль-Гамаля. Стойкость данного алгоритма базируется на сложности решения задачи дискретного логарифмирования. Порядок создания ключей приводится в следующей таблице.

Таблица 14

Процедура создания ключей

№ п/п	Описание операции	Пример
	Выбираются простое число p и два любых случайных числа g и x меньше p.	p=23, g=3, x=5
	Вычисляется y = gx mod p	y = 35 mod 23 = 243 mod 23 = 13
	Открытый ключ - y, g и p. Причем g и p можно сделать общими для группы пользователей. Закрытый ключ - x.

Перед шифрованием вначале выбирается k взаимно простое с p-1, после чего шифрограмма генерируется по следующим формулам

 

a = g^k mod p, (10)

b = (y^k mod p) Å T, (11)

где a, b – зашифрованное сообщение.

 

Дешифрование сообщения выполняется по следующей формуле

 

T = (a^x mod p) Å b. (12)

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k=7 приведен в таблице. Первая часть шифрованного сообщения - a = 37 mod 23 = 2.

Таблица 15

Пример шифрования по алгоритму Эль-Гамаля

Открытое сообщение, символ	А	Б	Р	А	М	О	В
Код символа
Вторая часть шифрограммы, b = (137 mod 23) Å T = 9 Å T
Открытое сообщение, T = (25 mod 23) Å b = 9 Å b

 

Алгоритм на основе задачи об укладке ранца [1]. Проблема укладки ранца формулируется следующим образом. Дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M₁, M₂,..., М_n и суммарное значение S; требуется вычислить значения b_i такие что

S = b₁М₁+b₂М₂ +... + b_nМ_n, (13)

 

где n – количество предметов;

b_i - бинарный множитель. Значение b_i = 1 означает, что предмет i кладут в рюкзак, b_i = 0 - не кладут.

 

Например, веса предметов имеют значения 1, 5, 6, 11, 14, 20, 32 и 43. При этом можно упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24.

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

 

Таблица 16

Пример шифрования на основе задачи об укладке ранца

Открытый текст	1 1 1 0 0 1 0 0	0 1 0 1 1 0 0 1	0 0 0 0 0 0 0 0
Рюкзак (ключ)	1 5 6 11 14 20 32 43	1 5 6 11 14 20 32 43	1 5 6 11 14 20 32 43
Шифрограмма	32 (1+5+6+20)	73 (5+11+14+43)

 

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

В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность. Сверхвозрастающей называется последовательность, в которой каждый последующий член больше суммы всех предыдущих. Например, последовательность {2, 3, 6, 13, 27, 52, 105, 210} является сверхвозрастающей, а {1, 3, 4, 9, 15, 25, 48, 76} — нет.

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

Например, пусть полный вес рюкзака равен 270, а последовательность весов предметов равна {2, 3, 6, 13, 27, 52, 105, 210}. Самый большой вес – 210. Он меньше 270, поэтому предмет весом 210 кладут в рюкзак. Вычитают 210 из 270 и получают 60. Следующий наибольший вес последовательности равен 105. Он больше 60, поэтому предмет весом 105 в рюкзак не кладут. Следующий самый тяжелый предмет имеет вес 52. Он меньше 60, поэтому предмет весом 52 также кладут в рюкзак. Аналогично проходят процедуру укладки в рюкзак предметы весом 6 и 2. В результате полный вес уменьшится до 0. Если бы этот рюкзак был бы использован для дешифрования, то открытый текст, полученный из значения шифртекста 270, был бы равен 10100101.

Открытый ключ представляет собой не сверхвозрастающую (нормальную) последовательность. Он формируется на основе закрытого ключа и, как принято считать, не позволяет легко решить задачу об укладке ранца. Для его получения все значения закрытого ключа умножаются на число n по модулю m. Значение модуля m должно быть больше суммы всех чисел последовательности, например, 420 (2+3+6+13+27+52+105+210=418). Множитель n должен быть взаимно простым числом с модулем m, например, 31. Результат построения нормальной последовательности (открытого ключа) представлен в следующей таблице.

Таблица 17

Пример получения открытого ключа

Закрытый ключ, ki
Открытый ключ, (ki*n) mod m = (ki*31) mod 420

 

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

В качестве примера возьмем открытое сообщение «АБРАМОВ», символы которого представим в бинарном виде в соответствии с табл. 3. Результат шифрования с помощью открытого ключа {62, 93, 186, 403, 417, 352, 315, 210} представлен в табл.18.

Таблица 18

Пример шифрования

Открытое сообщение	Сумма весов	Шифрограмма (рюкзак), ci
Символ	Bin-код
А	1100 0000	62+93
Б	1100 0001	62+93+210
Р	1101 0000	62+93+403
А	1100 0000	62+93
М	1100 1100	62+93+417+352
О	1100 1110	62+93+417+352+315
В	1100 0010	62+93+315

 

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

В нашем примере сверхвозрастающая последовательность равна {2, 3, 6, 13, 27, 52, 105, 210}, m = 420, n = 31. Значение n^-1 равно 271 (31*271 mod 420 = 1).

Таблица 19

Пример расшифрования

Шифрограмма (рюкзак), ci	(ci*n-1) mod m = (ci*271) mod 420	Сумма весов	Открытое сообщение
Bin-код	Символ
		2+3	1100 0000	А
		2+3+210	1100 0001	Б
		2+3+13	1101 0000	Р
		2+3	1100 0000	А
		2+3+27+52	1100 1100	М
		2+3+27+52+105	1100 1110	О
		2+3+105	1100 0010	В

 

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

⇐ Предыдущая1234

Поделиться:

Воспользуйтесь поиском по сайту: