Расшифруйте сообщение число 13 зашифрованное алгоритмом rsa с открытым ключом 11 35
Обновлено: 04.07.2024
Задача, положенная в основу метода состоит в том, чтобы найти такую функцию y=f(x), чтобы получение обратной функции x=f-1(y) , было бы в общем случае очень сложной задачей (NP-полной задачей), однако, если знать некую секретную информацию, то сделать это существенно проще. Такие функции также называют односторонними функциями с лазейкой или потайным ходом. Например, получить произведение двух чисел n=p*q просто, а разложить n на множители, если p и q достаточно большие простые числа, сложно.
1. Первым шагом в использовании алгоритма RSA является генерация ключей. Для этого нужно:
2. Выбрать два очень больших простых числа p и q.
3. Вычислить произведение n= p*q.
4. Выбрать большое случайное число d, не имеющее общих сомножителей с числом (p-1)*(q-1).
5. Определить число e, чтобы выполнялось (e*d) mod ((p-1)*(q-1))=1.
Тогда открытым ключом будут числа e и n, а секретным ключом - числа d и n.
Теперь, чтобы зашифровать данные по известному ключу , необходимо сделать следующее:
· Разбить шифруемый текст на блоки, где i-й блок может быть представлен в виде числа m(i)=0,1,2. n-1. Их должно быть не более n-1.
· Зашифровать текст, рассматриваемый как последовательность чисел m(i) по формуле c(i)=(m(i)e)mod n.
Чтобы расшифровать эти данные, используя секретный ключ , необходимо вычислить: m(i) = (c(i)d) mod n. В результате будет получено множество чисел m(i), которые представляют собой часть исходного текста.
· Выбираем p=5 и q=11 (числа на самом деле должны быть большими).
· Определяем (p-1)*(q-1) = 40. Тогда d будет равно, например 7.
· Выберем e, исходя из (e*7) mod 40=1. Например, e=3.
· C1 = (13)mod 55 = 1
· C2 = (23)mod 55 = 8
· C3 = (33)mod 55 = 27
Теперь расшифруем эти данные, используя закрытый ключ .
· M1 = (17)mod 55 = 1
· M2 = (87)mod 55 = 2097152mod 55 = 2
· M3 = (277)mod 55 = 10460353203 mod 55 = 3
Таким образом, все, данные расшифрованы.
Компьютер, чьи процессы имеют 1024 страницы в своем адресном пространстве, хранит таблицы страниц в памяти. На чтение слова из таблицы страниц требуется 5 нс. Чтобы уменьшить затраты, в компьютере существует буфер быстрого преобразования адреса (TLB), содержащий 32 пары (виртуальная страница – физический страничный блок), который может выполнять поиск за 1 нс. При какой частоте обращений к памяти, успешно реализуемых в TLB, средние затраты будут ниже 2 нс?
RSA использует разложение больших чисел (несколько сот разрядов) на простые множители, что требует большого объема вычислений и эта особенность определяет стойкость данного шифра.
Первым этапом асимметричного шифрования является создание получателем шифрограмм пары ключей. Процедура создания ключей RSA заключается в следующем.
- Выбирается два простых числа p и q, например p = 7 и q = 13
- Вычисляется произведение n = p*q, в нашем примере n = 7*13 = 91 Вычисляется функция Эйлера φ(n)
В нашем примере φ(n) = (7-1)*(13-1) = 72. Функция Эйлера определяет количество целых положительных чисел, не превосходящих n и взаимно простых с n.
Справка. Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме 1.
Задание на самостоятельное выполнение
| Вариант | p | q | Вариант | p | q |
|---|---|---|---|---|---|
| 1 | 19 | 73 | 14 | 71 | 79 |
| 2 | 29 | 73 | 15 | 19 | 43 |
| 3 | 17 | 29 | 16 | 13 | 61 |
| 4 | 23 | 61 | 17 | 41 | 79 |
| 5 | 13 | 31 | 18 | 13 | 53 |
| 6 | 23 | 31 | 19 | 59 | 61 |
| 7 | 53 | 73 | 20 | 13 | 83 |
| 8 | 31 | 37 | 21 | 13 | 19 |
| 9 | 17 | 37 | 22 | 19 | 29 |
| 10 | 23 | 79 | 23 | 17 | 67 |
| 11 | 13 | 41 | 24 | 13 | 17 |
| 12 | 23 | 41 | 25 | 31 | 73 |
| 13 | 17 | 41 | 26 | 31 | 67 |
Указания. Создайте открытый и закрытый ключи при заданных в вашем варианте p и q. (см. таблицу простых чисел).
| 1 | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 |
| 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 |
| 71 | 73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 |
Для того, чтобы увидеть форму, вам необходимо установить Java плагин для вашего браузера и разрешить выполнение Java-апплетов.
Если Вы пользуетесь браузером IE9 с установленным Java плагином и апплет тем не менее не работает, то возможно, что Java-апплет фильтруется ActiveX Filtering, новой функцией в IE9. Для ее отключения выберите Сервис/Безопасность и снимите галочку с Фильтрация ActiveX.
Задание на самостоятельное выполнение
Задание на самостоятельное выполнение
| Вариант | Криптограмма | Вариант | Криптограмма |
|---|---|---|---|
| 1 | 1127, 1310, 347, 1, 655, 261 | 14 | 2949, 4840, 3887, 4765, 875, 1 |
| 2 | 1, 1423, 1841, 254, 134, 777 | 15 | 190, 522, 439, 497, 447, 1 |
| 3 | 17, 361, 339, 304, 469, 225 | 16 | 466, 543, 472, 269, 163, 437 |
| 4 | 1071, 1, 606, 449, 1215, 472 | 17 | 1701, 199, 384, 2051, 2561, 330 |
| 5 | 379, 1, 396, 46, 1, 14 | 18 | 546, 680, 95, 62, 227, 100 |
| 6 | 219, 40, 468, 545, 1, 82 | 19 | 324, 2414, 615, 718, 2497, 1100 |
| 7 | 481, 1939, 1, 1655, 1123, 2957 | 20 | 1005, 271, 266, 967, 1030, 961 |
| 8 | 219, 205, 738, 894, 205, 1005 | 21 | 76, 227, 148, 177, 174, 4 |
| 9 | 427, 1, 499, 181, 232, 441 | 22 | 89, 474, 187, 113, 1, 474 |
| 10 | 1198, 1592, 591, 1, 1064, 951 | 23 | 322, 811, 573, 99, 1, 38 |
| 11 | 191, 251, 479, 346, 1, 251 | 24 | 76, 86, 152, 58, 142, 130 |
| 12 | 520, 16, 633, 623, 10, 468 | 25 | 445, 1483, 274, 1765, 233, 1154 |
| 13 | 576, 142, 639, 421, 208, 608 | 26 | 1811, 1, 1235, 844, 866, 214 |
Дешифрируйте шифрограмму с помощью закрытого ключа. Для проверки правильности своих расчетов заполните форму
Тест 4.3. Расшифровка криптограммы
Для того, чтобы увидеть форму, вам необходимо установить Java плагин для вашего браузера и разрешить выполнение Java-апплетов.
Если Вы пользуетесь браузером IE9 с установленным Java плагином и апплет тем не менее не работает, то возможно, что Java-апплет фильтруется ActiveX Filtering, новой функцией в IE9. Для ее отключения выберите Сервис/Безопасность и снимите галочку с Фильтрация ActiveX.
Шифрование происходит из текста в hex. Дешифрование - из hex в текст. Ключи предварительно генерируются или вводятся в hex. Возможно, понадобится преобразование из base64 в текст.
RSA (Rivest-Shamir-Adleman) является одной из первых криптосистем с открытым ключом и широко используется для безопасной передачи данных. В такой криптосистеме ключ шифрования является открытым и отличается от ключа расшифровки, который хранится в секрете (private). В RSA эта асимметрия основана на практической сложности факторизации произведения двух больших простых чисел, "проблема факторинга". Аббревиатура RSA состоит из начальных букв фамилий Рона Ривеста, Ади Шамира и Леонарда Адлемана, которые впервые публично описали алгоритм в 1978 году. Клиффорд Кокс, английский математик, работающий в Британском разведывательном управлении правительственной связи (GCHQ), разработал эквивалентную систему в 1973 году, но это не было рассекречено до 1997 года.
RSA является относительно медленным алгоритмом, и из-за этого он реже используется для прямого шифрования пользовательских данных. Чаще всего RSA передает зашифрованные общие ключи для шифрования с симметричным ключом, который, в свою очередь, может выполнять массовые операции шифрования-дешифрования на гораздо более высокой скорости.
Вокруг алгоритмов шифрования с отрытым и закрытым ключом существует множество недопониманий и мистификаций. Здесь я хотел бы предельно коротко и наглядно, с конкретными числами и минимумом формул, показать, как это работает.
Я не вдаюсь в теорию (не очень понятно, на какой уровень подготовки читателя следует рассчитывать), но я уверен, что прочитав эту короткую иллюстрацию, любому человеку будет проще разобраться в формулах и строгих доказательствах.
Итак. Допустим, я хочу получить от вас некие данные. Мы с вам не хотим, чтобы эти данные узнал кто-то, кроме нас. И у нас нет никакой уверенности в надёжности канала передачи данных. Приступим.
Шаг первый. Подготовка ключей
Я должен проделать предварительные действия: сгенерировать публичный и приватный ключ.
- Выбираю два простых числа. Пусть это будет p=3 и q=7 .
- Вычисляем модуль — произведение наших p и q : n=p×q=3×7=21 .
- Вычисляем функцию Эйлера: φ=(p-1)×(q-1)=2×6=12 .
- Выбираем число e , отвечающее следующим критериям: (i) оно должно быть простое, (ii) оно должно быть меньше φ — остаются варианты: 3, 5, 7, 11, (iii) оно должно быть взаимно простое с φ ; остаются варианты 5, 7, 11. Выберем e=5 . Это, так называемая, открытая экспонента.
Мне нужно вычислить число d , обратное е по модулю φ . То есть остаток от деления по модулю φ произведения d×e должен быть равен 1. Запишем это в обозначениях, принятых во многих языках программирования: (d×е)%φ=1 . Или (d×5)%12=1 . d может быть равно 5 ( (5×5)%12=25%12=1 ), но чтобы оно не путалось с e в дальнейшем повествовании, давайте возьмём его равным 17. Можете проверить сами, что (17×5)%12 действительно равно 1 ( 17×5-12×7=1 ). Итак d=17 . Пара — это секретный ключ, его я оставляю у себя. Его нельзя сообщать никому. Только обладатель секретного ключа может расшифровать то, что было зашифровано открытым ключом.
Шаг второй. Шифрование
Полученные данные E=10 , вы отправляете мне.
Шаг третий. Расшифровка
Я получил ваши данные ( E=10 ), и у меня имеется закрытый ключ = .
В чём гарантия надёжности шифрования
Надёжность шифрования обеспечивается тем, что третьему лицу (старающемуся взломать шифр) очень трудно вычислить закрытый ключ по открытому. Оба ключа вычисляются из одной пары простых чисел ( p и q ). То есть ключи связаны между собой. Но установить эту связь очень сложно. Основной загвоздкой является декомпозиция модуля n на простые сомножители p и q . Если число является произведением двух очень больших простых чисел, то его очень трудно разложить на множители.
Постараюсь это показать на примере. Давайте разложим на множители число 360:
- сразу ясно, что оно делится на два (получили 2)
- оставшееся 180 тоже, очевидно чётное (ещё 2)
- 90 — тоже чётное (ещё двойка)
- 45 не делится на 2, но следующая же попытка оказывается успешной — оно делится на три (получили 3)
- 15 тоже делится на 3
- 5 — простое.
Мы на каждом шагу, практически без перебора, получали всё новые и новые множители, легко получив полное разложение 360=2×2×2×3×3×5
Давайте теперь возьмём число 361. Тут нам придётся помучиться.
- оно не чётное
- три — нет, не делится
- пять (допустим, мы поступаем умно и перебираем только простые числа, хотя, на практике, поиск больших простых чисел, сам по себе, является сложной задачей) — не подходит
- семь? — нет.
- …
- и только 19 даст нам ответ: 361=19×19.
При использовании больших чисел, задача становится очень сложной. Это позволяет надеяться, что у взломщика просто не хватит вычислительных ресурсов, чтобы сломать ваши шифр за обозримое время.
А как это всё работает на практике?
Сперва сгенерируем ключи с чуть бо́льшими числами. Они не так наглядны, но позволят нам шифровать не только числа от нуля до 20.
Оттолкнёмся от пары простых чисел = . Пусть наш открытый ключ будет = , а закрытый = .
Мы готовы к шифрованию. Переведём наше слово в цифровое представление. Мы можем взять просто номера букв в алфавите. У нас получится последовательность чисел: 11, 17, 15, 19.
Мы можем зашифровать каждое из этих чисел открытым ключом = и получить шифровку 197, 272, 2, 304. Эти числа можно передать получателю, обладающему закрытым ключом = и он всё расшифрует.
Немного о сложностях
То есть мы можем добавить случайное число в начало и получить (299, 11, 17, 15, 19). После перемешивания получится: 299, 310, 4, 19, 38. После шифрования уже невозможно будет догадаться где была какая буква.
Детали и принципы формирования блоков можно почитать тут. Я же в этой заметке хотел рассказать только про RSA. Надесь, удалось.
Читайте также: