Рейтинг:1

Генерация порядка $\lambda$ (который равен lcm((p-1),(q-1))) элементу g в модифицированном пайе, почему $-a^{2n}$?

флаг de

Как говорится в вопросе, в вариантах криптосистемы Пайе, таких как CS01 и DT-PKC, когда им нужен элемент $г$ порядка $\лямбда$, они выбирают случайное число $а$ из группы $Z^*_{n^2}$ и рассчитать $-a^{2n}$ как $г$. Во-первых, на что это умножение $-1$ за? Во-вторых, почему $а^{2n}$ не просто $а^{п}$? Я думаю $-1$ ничего не меняет и $а^{2n}$ придаст нам элемент порядка $\лямбда/2$ скорее всего нет $\лямбда$. Может ли кто-нибудь объяснить это для меня? Спасибо.

Рейтинг:4
флаг ru

Если мы выберем $n$ быть произведением двух сильных простых чисел $p=2r+1$ и $д=2с+1$ с $г$ и $s$ премьер, обратите внимание, что $р$ и $q$ 3 мод 4 и что $\mathrm{LCM}(p-1,q-1)=2rs$. Выбор случайного $а$ и возведение его в степень $2n$ придает элемент порядка $\лямбда/2=rs$ (есть исчезающе малый шанс получить заказ $г$, $s$ или же $1$) и, следовательно, является квадратичным вычетом. Умножение на -1 делает его невычетом и, следовательно, порядком. $\лямбда=2rs$. Это также гарантирует, что символ Якоби равен 1, чтобы через такие символы не происходило утечки информации.

Если бы мы этого не сделали, была бы немалая вероятность того, что $а$ является квадратичным вычетом и, следовательно, что $г$ было бы в порядке $\лямбда/2$ скорее, чем $\лямбда$.

rzxh avatar
флаг de
Думаю, на этот раз я понял, спасибо за объяснение.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.