Мбоу «сош №143» г. Красноярска Метапредметный проект «Криптография: алгоритм rsa»
 Скачать 422.14 Kb.
|
3. Алгоритм RSA3.1. Алгоритм создания открытого и секретного ключей RSA
Пара (e,m) публикуется в качестве открытого ключа RSA. Пара (d,m) играет роль секретного ключа RSA и держится в секрете. Делители p и q можно либо уничтожить либо сохранить вместе с секретным ключом. 3.2. Шифрование и дешифрование: cхема RSA В схеме RSA сообщением являются целые числа лежащие от 0 до m-1. Опишем процесс шифрования. Исходный текст должен быть переведен в числовую форму, этот метод считается известным. В результате этого текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке от 0 до m-1. Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом a. Алгоритм шифрования
Алгоритм дешифрования
3.3. Примеры шифрования по схеме RSA. Пример 1.
Пара (e,m)=(5,85) - открытый ключ RSA.
Найдем НОД: 64=5*12+4 5=4*1+1 4=1*4+0НОД(5,64)=1 Найдем соотношение Безу: 1=5-4*1=5-(64-5*12)=5*13-64*1. Отсюда НОД (5, 64) =1=d*5+c*64 = 13*5+(-1)*64 и d = 13. Пара (d,m)=(13,85) – секретный ключ RSA Алгоритм шифрования
Алгоритм дешифрования
a=bd mod m=6213 mod 85=200028539268669788905472 mod 85=7 Пример 2. Зашифруем фразу «Математика – царица наук». Таблица 2. Квадрат Полибия с русским алфавитом.
Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, — последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из квадрата Полибия. Квадрат Полибия1, изобретенный во II веке до н.э., не вышел из употребления до сих пор. Устроен он так: все (или почти все) буквы алфавита располагаются в квадрате или в прямоугольнике соответствующего размера, для русского 5*6. после этого каждая буква кодируется двумя числами – номером строки и номером столбца, в которых она расположена. Конечно буквы можно (и даже нужно!) располагать не по порядку, тогда шифр становиться гораздо сложнее. В таблице 2 приведен квадрат Полибия с русским алфавитом. Тогда шифруемая фраза будет: 31114116311141232511274511352345111732114225. Теперь зашифруем это число по схеме RSA. Для уменьшения вычислений выпишем все буквы фразы без повторений:
Используя открытый ключ (5,85) из примера 1 зашифруем все числа из второй строки таблицы: 315 mod 85 = 28629151 mod 85 = 46 115 mod 85 = 161051 mod 85 = 61 415 mod 85 = 115856201 mod 85 = 11 165 mod 85 = 1048576 mod 85 = 16 235 mod 85 = 6436343 mod 85 = 58 255 mod 85 = 9765625 mod 85 = 60 455 mod 85 = 184528125 mod 85 = 10 355 mod 85 = 52521875 mod 85 = 35 325 mod 85 = 33554432 mod 85 = 2 425 mod 85 = 130691232 mod 85 = 77 275 mod 85 = 14348907 mod 85 = 57 175 mod 85 = 1419857 mod 85 = 17 В результате получим следующую таблицу.
Теперь можно записать полученную криптограмму: 46611116466111586061571061355810611702617760 Для расшифровки данную криптограмму надо разбить на блоки из двухзначных чисел и применить секретный ключ RSA (13, 85) : 4613 mod 85 = 15441948546310791168 mod 85 = 31 6113 mod 85 = 161915287432152755657581 mod 85 = 11 1113 mod 85 = 34522712143931 mod 85 = 41 1613 mod 85 = 4503599627370496 mod 85 = 16 5813 mod 85 = 84055070416556869132288 mod 85 = 23 6013 mod 85 = 130606940160000000000000 mod 85 = 25 1013 mod 85 = 10000000000000 mod 85 = 45 3513 mod 85 = 118272717781982421875 mod 85 = 35 213 mod 85 = 8192 mod 85 = 32 7713 mod 85 = 3344871416191195940889917 mod 85 = 42 5713 mod 85 = 67046038752496061076057 mod 85 = 27 1713 mod 85 = 9904578032905937 mod 85 = 17 Получим исходное сообщение в виде числа: 31114116311141232511274511352345111732114225, разбив которое на двузначные числа, можно восстановить исходный текст по квадрату Полибия. Пример 3. Зашифруем фразу Дэвида Кана2: «… История криптографии…- это история человечества». Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, — последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из таблицы 3. Таблица 3. Кодирование букв алфавита двузначными числами.
Проделав эту процедуру, мы получим число, возможно очень большое, если сообщение было длинным. В нашем случае мы получим число: 4218272824261841442026182528241326103018184243392824441826282426184144331521241215331527281210. Теперь нам нужно разбить численное представление сообщения на кусочки, каждый из которых — натуральное число, не превосходящее m. Создадим секретный и открытый ключ RSA:
Пара (e,m)=(7,69) - открытый ключ RSA.
Найдем соотношение Безу: 1=7-2*3=7-(44-7*6)*3=7-44*3+7*6*3=19*7+(-3)*44 Отсюда НОД (7, 44) =1=d*7+c*44 = 19*7+(-3)*44 и d = 19. Пара (d,m)=(19,69) – секретный ключ RSA. 187 mod 69 =612220032 mod 69 = 6 277 mod 69 =10460353203 mod 69 = 54 287 mod 69 =13492928512 mod 69 = 40 267 mod 69 =8031810176 mod 69 = 2 247 mod 69 =4586471424 mod 69 = 24 417 mod 69 =194754273881 mod 69 = 29 207 mod 69 =1280000000 mod 69 = 44 257 mod 69 =6103515625 mod 69 = 13 137 mod 69 =62748517 mod 69 = 55 107 mod 69 =10000000 mod 69 = 37 307 mod 69 =21870000000 mod 69 = 51 397 mod 69 =137231006679 mod 69 = 18 337 mod 69 =42618442977 mod 69 = 60 157 mod 69 =170859375 mod 69 = 57 217 mod 69 =1801088541 mod 69 = 33 127 mod 69 =35831808 mod 69 = 39 427 mod 69 =230539333248 mod 69 = 15 437 mod 69 =271818611107 mod 69 = 67 447 mod 69 =319277809664 mod 69 = 56 Полученная криптограмма: 150654402402062956440206444025550237510606156756184024560654402402062956605733243957605754403937 Пример 4. Зашифруем фразу Рене́ Дека́рта: «Мало иметь хороший ум, главное – хорошо его применять». Закодируем буквы согласно таблице №3 . 22 10 21 24 44 18 22 15 28 38 44 31 24 26 24 34 18 19 44 29 22 45 44 13 21 10 12 23 24 15 44 43 44 31 24 26 24 34 24 44 15 13 24 44 25 26 18 22 15 23 41 28 38 46 Создадим секретный и открытый ключ RSA:
Пара (e,m)=(31,1157) - открытый ключ RSA.
1056=31*34+2 31=2*15+1 2=2*1+0 НОД(31,1056)=1.
Отсюда НОД (31, 1056) =1=31*d-c*1056=31*511-15*1056 и d = 511. Пара (d,m)=(511,1157) – секретный ключ RSA. Теперь нам нужно разбить численное представление сообщения на кусочки, каждый из которых — натуральное число, не превосходящее m=1157: 221-021-244-418-221-528-384-431-242-624-341-819-442-922-454-413-211-012-232-415-444-344- 312-426-243-424-441-513-244-425-261-822-152-341-283-846 Для расчетов воспользуемся программой MathCad. Данная программа позволяет вычислять большие степени и находить остаток от целочисленного деления. Я воспользовалась следующей программой. 01231 mod 1157 =675 02131 mod 1157 =1032 15231 mod 1157 =308 21131 mod 1157 =419 22131 mod 1157 =143 23231 mod 1157 =795 24231 mod 1157 =668 24331 mod 1157 =165 24431 mod 1157 =127 24431 mod 1157 =127 26131 mod 1157 =326 28331 mod 1157 =1076 31231 mod 1157 =182 34131 mod 1157 =887 34431 mod 1157 =215 38431 mod 1157 =994 41331 mod 1157 =621 41531 mod 1157 =155 41831 mod 1157 =24 42431 mod 1157 =837 42531 mod 1157 =958 42631 mod 1157 =491 43131 mod 1157 =830 44131 mod 1157 =584 44231 mod 1157 =325 44431 mod 1157 =622 45431 mod 1157 =961 51331 mod 1157 =748 52831 mod 1157 =148 62431 mod 1157 =624 81931 mod 1157 =663 82231 mod 1157 =1121 84631 mod 1157 =716 92231 mod 1157 =714 В результате получим RSA-криптограмму. 143-1032-127-24-143-148-994-830-668-624-887-663-325-714-961-621-419-675-795-155-622-215-182-491-165-837-584-748-127-958-326-1121-308-887-1076-716 Для расшифровки применим секретный ключ RSA: d=511,m=1157. 675511 mod 1157 = 012 1032511 mod 1157 = 021 308511 mod 1157 = 152 419511 mod 1157 = 211 143511 mod 1157 = 221 795511 mod 1157 = 232 668511 mod 1157 = 242 165511 mod 1157 = 243 127511 mod 1157 = 244 127511 mod 1157 = 244 326511 mod 1157 = 261 1076511 mod 1157 = 283 182511 mod 1157 = 312 887511 mod 1157 = 341 215511 mod 1157 = 344 994511 mod 1157 = 384 621511 mod 1157 = 413 155511 mod 1157 = 415 24511 mod 1157 = 418 837511 mod 1157 = 424 958511 mod 1157 = 425 491511 mod 1157 = 426 830511 mod 1157 = 431 584511 mod 1157 = 441 325511 mod 1157 = 442 622511 mod 1157 = 444 961511 mod 1157 = 454 748511 mod 1157 = 513 148511 mod 1157 = 528 624511 mod 1157 = 624 663511 mod 1157 = 819 1121511 mod 1157 = 822 716511 mod 1157 = 846 714511 mod 1157 = 922 В результате расшифровки получим текст: 221-021-244-418-221-528-384-431-242-624-341-819-442-922-454-413-211-012-232-415-444-344- 312-426-243-424-441-513-244-425-261-822-152-341-283-846 , разбив который на двузначные числа, можно восстановить исходный текст по таблице 3. Пример 5. Зашифруем фразу Пьера Гассенди «Если мы действительно что-то знаем, то мы знаем это благодаря изучению математики». Закодируем текст по квадрату Полибия (таб. 2): 1636262311315311151624364113411626573233114641332741331722321116314717413331532232111631175441331226111433151135561723224246163223553111411631114123252337 Создадим секретный и открытый ключ RSA:
Пара (e,m)=(17,123) - открытый ключ RSA.
80=17*4+12 17=12*1+5 12=5*2+2 5=2*2+1 2=2*1+0 НОД(17,80)=1
=-12*2+17*5-12*1*5=17*5-12*7=17*5-(80-17*4)*7=17*5-80*7+17*4*7=-80*7+17*33 Отсюда НОД (17, 80) =1= -80* c+ 17* d=-80*7+17*33 и d =33. Пара (d,m)=(33,123) – секретный ключ RSA. Разобьем текст на блоки двузначных чисел и зашифруем его, использую открытый ключ. 1617mod 123 =10 2617mod 123 =101 3617mod 123 =102 2317mod 123 =86 3117mod 123 =64 5317mod 123 =116 1517mod 123 =63 2417mod 123 =117 4117mod 123 =41 1317mod 123 =70 5717mod 123 =51 3217mod 123 =32 3317mod 123 =84 4617mod 123 =103 2717mod 123 =27 2217mod 123 =106 1717mod 123 =47 5417mod 123 =111 2117mod 123 =90 1117mod 123 =110 1417mod 123 =14 3517mod 123 =56 5617mod 123 =104 4217mod 123 =42 5517mod 123 =55 3717mod 123 =16 4717mod 123 =26 2517mod 123 =31 Получим данную RSA-криптограмму: 10-102-101-86-47-63-116-47-63-10-102-41-70-86-41-10-101-51-32-84-47-103-41-84-27-41-84-47-106-32-110-10-63-26-47-41-84-47-63-116-47-106-32-110-10-63-47-90-101-110-14-84-63-110-56-104-47-86-106-42-103-10-32-86-55-47-63-110-41-10-63-110-41-86-31-86-16 Для расшифровки применим секретный ключ RSA: d=33, m=123 1033 mod 123 = 16 10133 mod 123 = 26 10233 mod 123 = 36 8633 mod 123 = 23 6433 mod 123 = 31 11633 mod 123 = 53 6333 mod 123 = 15 11733 mod 123 = 24 4133 mod 123 = 41 7033 mod 123 = 13 5133 mod 123 = 57 3233 mod 123 = 32 8433 mod 123 = 33 10333 mod 123 = 46 2733 mod 123 = 27 10633 mod 123 = 22 4733 mod 123 = 17 11133 mod 123 = 54 9033 mod 123 = 21 11033 mod 123 = 11 1433 mod 123 = 14 5633 mod 123 = 35 10433 mod 123 = 56 4233 mod 123 = 42 5533 mod 123 = 55 1633 mod 123 = 37 2633 mod 123 = 47 3133 mod 123 = 25 В результате расшифровки получим текст 1636262311315311151624364113411626573233114641332741331722321116314717413331532232111631175441331226111433151135561723224246163223553111411631114123252337, разбив который на двузначные числа можно восстановить его по квадрату Полибия. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||