1

В каком случае закрытая экспонента ключа RSA будет равна открытой экспоненте?

7
  • @alexanderbarakin можете объяснить, почему никогда?
    – user321275
    22 дек 2018 в 8:15
  • Хотя бы потому, что у них длина разная.
    – Rootware
    22 дек 2018 в 8:19
  • @alexanderbarakin разве это следует из (e * d) % phi(n) = 1? Если да, то как?
    – user321275
    22 дек 2018 в 8:21
  • @Rootware разве это следует из (e * d) % phi(n) = 1? Если да, то как?
    – user321275
    22 дек 2018 в 8:22
  • Обозначения с википедии ru.wikipedia.org/wiki/RSA
    – user321275
    22 дек 2018 в 8:22

1 ответ 1

0

Если закрытый ключ - пара чисел (d,N), а открытый ключ - пара чисел (e,N), где N=p*q. функция Эйлера в таком случае Fi(N) = (p-1)(q-1). между ключами существует связь вида: (e * d) mod Fi(N) = 1. Отсюда очевидно, что -1 * -1 = 1, а -1 mod Fi(N) = Fi(N) - 1.

Пример: p=23, q=11 => N = 253, Fi(253)=22*10=220 => если e=-1 mod 220 = 220-1=219 то (219*219) mod 220 = 1. то есть при (d=219, N=253) => (e=219, N=253).

11
  • Можете подробней пояснить, что за -1? Пример подходит, согласен
    – user321275
    22 дек 2018 в 8:30
  • Могу, но краткость моего ответа зависит от глубині Ваших знаний :) Fi(N)-1 всегда будет взаимно простім с функцией Эйлера, это очевидно из алгоритма Эвклида. Чтобы этого избежать надо просто не выбирать значения Fi(N)-1. 22 дек 2018 в 8:32
  • Правильно ли я понимаю, что чтобы они были равны, достаточно чтобы Fi(N)-1 было взаимно простым с Fi(N)? Тогда мы просто полагаем e=d=Fi(N)-1
    – user321275
    22 дек 2018 в 8:34
  • Вы правильно поняли. А -1 это следчтвие цикличности отображения области допустимых значений на числовую ось. -1 = Fi(N) - 1, -2=Fi(N)-2, ... 22 дек 2018 в 8:38
  • И ещё: существуют ли такие p и q, при которых e=d ВСЕГДА (это основной вопрос в принципе, т.к. о существовании я догадывался)?
    – user321275
    22 дек 2018 в 8:39

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.