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