2011-gre-cs-practice-book.pdf/Q69 — различия между версиями
Материал из DISCOPAL
Evvnes (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Вопрос: Q69-08c765 == | == Вопрос: Q69-08c765 == | ||
| − | + | Предположим, что в [https://ru.wikipedia.org/wiki/RSA 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|[[Участник: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)
Найти его можно с помощью расширенного алгоритма Евклида по формуле: , где - меньший из результатов расширенного алгоритма Евклида. В нашем случае . А следовательно