2011-gre-cs-practice-book.pdf/Q69 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 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 * 11 = p * q</m>
+
* Найдём простые множители для <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*e)</m> и <m>phi(N)</m> должен быть равен 1)
+
* Находим <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)}}
{{reserve-task|[[Участник:Evvnes|Evvnes]] 08:40, 19 декабря 2024 (UTC)}}
+
 
{{checkme|[[Участник:Evvnes|Evvnes]] 13:26, 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)

Найти его можно с помощью расширенного алгоритма Евклида по формуле: , где - меньший из результатов расширенного алгоритма Евклида. В нашем случае . А следовательно