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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: « == Вопрос: Q69-08c765 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…»)
 
 
(не показаны 3 промежуточные версии 1 участника)
Строка 1: Строка 1:
−
 
 
== Вопрос: Q69-08c765 ==
 
== Вопрос: Q69-08c765 ==
  
−
<i>Тут вставьте перевод вопроса.
+
Предположим, что в [https://ru.wikipedia.org/wiki/RSA RSA]-шифровании
−
Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 возможности разметки],
+
* открытым ключом шифрования является пара <m>(e,n) = (3, 55) </m>,
−
включая формулы и т.п, если будут графы — посмотрите как задать их текстом https://wiki.4intra.net/Graphviz .
+
* закрытым ключом дешифрования - пара <m>(d, n) = (d, 55) </m>,
−
Если код — теги «code-pascal», «code-c» или «code-python».
+
* где <m> d < n </m> - положительные целые числа.  
  
−
Старайтесь нетривиальные понятия, особенно незнакомые вам, найти ссылку на википедию и вставить (нейросети лажают!).
+
Каково значение <m>d</m> ?
−
Это важно, чтобы найти корректный перевод (то, что в википедии, или на худой конец — точно массово гуглится).
+
−
 
+
−
Потом конечно сотрите инструкции, которые тут курсивом.</i>
+
  
 
=== Ответы ===
 
=== Ответы ===
−
<i>Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так
 
−
(префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)</i>
 
−
 
−
* Правильный ответ: тут реально правильный ответ
 
−
* неправильный ответ
 
−
* еще какой-то неправильный ответ
 
−
* еще какой-то неправильный ответ
 
−
* еще какой-то неправильный ответ
 
−
 
−
<i>Если ответы длинные, многострочные, или там графы, используйте
 
−
[https://wiki.4intra.net/MediawikiQuizzer/ru#.D0.9E.D1.82.D0.B2.D0.B5.D1.82.D1.8B способ задания ответов разделами],
 
−
Но такое очень редко встречается. </i>
 
  
 +
* Правильный ответ: 27
 +
* 13
 +
* 37
 +
* 39
 +
* 54
  
 
=== Объяснение ===
 
=== Объяснение ===
−
<i>Сначала заполните номер страницы с этим вопросом
 
−
{{cstest-source|2011-gre-cs-practice-book.pdf|тут-номер-страницы-с-вопросом-69|69}}
 
  
−
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.
+
{{cstest-source|2011-gre-cs-practice-book.pdf|48|69}}
  
−
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а [[2004-gre-cs-practice-book.pdf/Q16|неправильные варианты — неправильны]].
+
Чтобы найти значение <m>d</m> в RSA-шифровании, где открытый ключ <m>(e, n) = (3, 55)</m> и <m>n = 55</m> выполним следующие действия:
−
Тут тоже могут быть полезны [[2004-gre-cs-practice-book.pdf/Q03|ссылки на википедию]],  
+
* Найдём простые множители для <m>n</m>: <m>55 = 5 × 11 = p × q</m>
−
решение вами [[2004-gre-cs-practice-book.pdf/Q12|рекуррентных уравнений в sympy]].
+
* Вычислим общую функцию Эйлера: <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>
  
−
</i>
+
{{question-ok|[[Участник:StasFomin|StasFomin]] 14:39, 19 декабря 2024 (UTC)}}
  
−
{{question-ok|}}
+
[[Категория:Криптография]]

Текущая версия на 14:39, 19 декабря 2024

Вопрос: Q69-08c765

Предположим, что в RSA-шифровании

  • открытым ключом шифрования является пара ,
  • закрытым ключом дешифрования - пара ,
  • где - положительные целые числа.

Каково значение  ?

Ответы

  • Правильный ответ: 27
  • 13
  • 37
  • 39
  • 54

Объяснение

Исходники — вопрос 69 на 48 странице книги «2011-gre-cs-practice-book.pdf»

Чтобы найти значение в RSA-шифровании, где открытый ключ и выполним следующие действия:

  • Найдём простые множители для :
  • Вычислим общую функцию Эйлера:
  • Выбираем значение (в нашем случае )
  • Находим , которое является обратным к по модулю (то есть остаток от деления и должен быть равен 1)

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

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q69&oldid=34124»