2011-gre-cs-practice-book.pdf/Q69 — различия между версиями
Материал из DISCOPAL
Evvnes (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Вопрос: Q69-08c765 == | == Вопрос: Q69-08c765 == | ||
| − | Предположим, что в RSA-шифровании открытым ключом шифрования является пара <m>(e,n) = (3, 55) </m> , | + | Предположим, что в [https://ru.wikipedia.org/wiki/RSA RSA]-шифровании |
| − | ключом дешифрования - пара <m>(d, n) = (d, 55) </m>, где <m> d < n </m> - положительные целые числа. Каково значение <m>d</m> ? | + | * открытым ключом шифрования является пара <m>(e,n) = (3, 55) </m>, |
| + | * закрытым ключом дешифрования - пара <m>(d, n) = (d, 55) </m>, | ||
| + | * где <m> d < n </m> - положительные целые числа. | ||
| + | |||
| + | Каково значение <m>d</m> ? | ||
=== Ответы === | === Ответы === | ||
| Строка 17: | Строка 21: | ||
Чтобы найти значение <m>d</m> в RSA-шифровании, где открытый ключ <m>(e, n) = (3, 55)</m> и <m>n = 55</m> выполним следующие действия: | Чтобы найти значение <m>d</m> в RSA-шифровании, где открытый ключ <m>(e, n) = (3, 55)</m> и <m>n = 55</m> выполним следующие действия: | ||
| − | * Найдём простые множители для <m>n</m>: <m>55 = 5 | + | * Найдём простые множители для <m>n</m>: <m>55 = 5 × 11 = p × q</m> |
| − | * Вычислим общую функцию Эйлера: <m>phi = (p-1)(q-1) = (5-1)(11-1) = 40</m> | + | * Вычислим общую функцию Эйлера: <m>\phi = (p-1)(q-1) = (5-1)(11-1) = 40</m> |
* Выбираем значение <m>e</m> (в нашем случае <m>e = 3</m>) | * Выбираем значение <m>e</m> (в нашем случае <m>e = 3</m>) | ||
| − | * Находим <m>d</m> , которое является обратным к <m>e</m> по модулю <m>phi(N)</m> (то есть остаток от деления <m>(d | + | * Находим <m>d</m> , которое является обратным к <m>e</m> по модулю <m>\phi(N)</m> (то есть остаток от деления <m>(d ×e )</m> и <m>\phi(N)</m> должен быть равен 1) |
| − | Найти его можно с помощью расширенного алгоритма Евклида по формуле: <m>d = phi(N) - |x|</m>, где <m>|x|</m> - меньший из результатов расширенного алгоритма Евклида. | + | Найти его можно с помощью расширенного алгоритма Евклида по формуле: <m>d = \phi(N) - |x|</m>, где <m>|x|</m> - меньший из результатов расширенного алгоритма Евклида. |
В нашем случае <m>|x| = 13</m>. А следовательно <m>d = 40 - 13 = 27</m> | В нашем случае <m>|x| = 13</m>. А следовательно <m>d = 40 - 13 = 27</m> | ||
| − | {{question-ok | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 14:39, 19 декабря 2024 (UTC)}} |
| − | + | ||
| + | [[Категория:Криптография]] | ||
Текущая версия на 14:39, 19 декабря 2024
Вопрос: Q69-08c765
Предположим, что в RSA-шифровании
- открытым ключом шифрования является пара ,
- закрытым ключом дешифрования - пара ,
- где - положительные целые числа.
Каково значение ?
Ответы
- Правильный ответ: 27
- 13
- 37
- 39
- 54
Объяснение
Исходники — вопрос 69 на 48 странице книги «2011-gre-cs-practice-book.pdf»
Чтобы найти значение в RSA-шифровании, где открытый ключ и выполним следующие действия:
- Найдём простые множители для :
- Вычислим общую функцию Эйлера:
- Выбираем значение (в нашем случае )
- Находим , которое является обратным к по модулю (то есть остаток от деления и должен быть равен 1)
Найти его можно с помощью расширенного алгоритма Евклида по формуле: , где - меньший из результатов расширенного алгоритма Евклида. В нашем случае . А следовательно