Регистрация Войти
Рейтинг:1
Johny Dow avatar Crypto

Почему прием Шамира для RSA работает

флаг fr
Johny Dow

Я читал, что трюк Шамира может защитить RSA с CRT от атак с ошибкой. Однако мне непонятно, почему следующие уравнения $$ s_{p}^{*}=m^{d \bmod \varphi(p \cdot t)} \bmod p \cdot t \ s_{q}^{*}=m^{d \bmod \varphi(q \cdot t)} \bmod q \cdot t $$ подразумевает, что: $$ s_{p}^{*} = s_{q}^{*} \bmod t $$

172
0 + 0
fgrieu avatar
флаг ng
fgrieu
Насколько мне известно, это не трюк Шамира, который вычисляет $x^a\,y^b\bmod n$ примерно на 60 % дешевле, чем вычисление $(x^a\bmod n)\,y^b\bmod н$. У OTOH у Шамира наверняка много трюков. Кроме того, несмотря на то, что приведенное уравнение выполняется, это не стандартная мера противодействия атакам с ошибкой, которая заключается в проверке $s^e\bmod n=m$.
2
Ответить
Johny Dow avatar
флаг fr
Johny Dow
@fgrieu Это называется «уловка Шамира» в [Темах криптологии — CT-RSA 2009] (https://link.springer.com/book/10.1007/978-3-642-00862-7), и вот куда я попал имя от.
1
Ответить
fgrieu avatar
флаг ng
fgrieu
Да, теперь я вижу это в Matthieu Rivain, [Securing RSA from Fault Analysis by Возведение в степень двойной цепочки сложения] (https://eprint.iacr.org/2009/165.pdf) (обновленная версия), первоначально [в материалах CT-RSA 2009] (https://doi.org/10.1007/978- 3-642-00862-7_31). Тем не менее, [эта ссылка] (https://doi.org/10.1007/978-1-4419-5906-5_1157) делает _Уловку Шамира_ синонимом [_Одновременного возведения в степень_](https://doi.org/10.1007/978-1 -4419-5906-5_45).
1
Ответить
Рейтинг:2
Daniel S avatar Crypto
флаг ru
Daniel S

У нас есть $\varphi(t)|\varphi(pt)$ и $\varphi(t)|\varphi(qt)$ так что если $d_1$ и $d_2$ являются показателями для $s_p^*$ и $s_q^*$ тогда $d=d_1+k_1\varphi(t)$ и $d=d_2+k_2\varphi(t)$ для некоторых целых чисел $k_1$ и $k_2$. Следует, что $d_1=d_2+(k_2-k_1)\varphi(t)$ и, следовательно $$d_1\equiv d_2\pmod{\varphi(t)}.$$

Следует, что $m^{d_1}\эквив m^{d_2}\pmod t$ по теореме Эйлера.

0 + 0
Johny Dow avatar
флаг fr
Johny Dow
Я только что понял, что не совсем понимаю, почему $d_1\equiv d_2\pmod{\phi(t)}$ не могли бы вы объяснить это подробнее? Спасибо!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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