înregistrare Logare
Puncte:3
Pazu avatar Crypto

Decriptarea RSA folosind CRT: Cum afectează complexitatea?

drapel vn
Pazu

Există o variantă eficientă a RSA folosind CRT:

\begin{align*} d_p &= d \pmod{p-1}\ d_q &= d \pmod{p-1} \ q_{\operatorname{inv}} &= q^{-1} \pmod{p} \end{align*}

unde decriptarea se face după cum urmează:

\begin{align*} c_p &= c \pmod{p} \ c_q &= c \pmod{q} \ m_p &= c_p^{d_p} \pmod{p} \ m_q &= c_q^{d_q} \pmod{q} \ h &= q_{\operatorname{inv}}(m_p - m_q) \pmod{p} \end{align*}

Prima mea întrebare este mai degrabă generală: Unde folosesc algoritmul CRT (cum este scris acolo)? Adică configurarea RSA mă definește deja $p,q,d,c$ și deci nu am un sistem de congruențe.

A doua întrebare a mea se referă la complexitate. Să presupunem $\log d = \log n = B$ și $\log p = \log q = \frac{B}{2}$ și $d, d_p, d_q$ au la fel de multe $0$s și $1$s. Ce pot spune despre numărul de operații de dimensiune $B$ a acestei variante?

439
0 + 0
Puncte:7
poncho avatar Crypto
drapel my
poncho

Există o variantă eficientă a RSA folosind CRT

De fapt, prin modul în care folosim termenii în general, nu este o „variantă”, ci este o implementare alternativă. Adică, singurele modificări aduse algoritmului RSA sunt făcute cu modul în care se face operația privată (și formatul cheilor private); oricine care face doar operațiuni publice nu trebuie să cunoască ceea ce face implementarea privată (generarea semnăturii sau decriptarea cheii publice).

Unde folosesc algoritmul CRT (cum este scris acolo)?

Ori de câte ori doriți ceva mai multă eficiență (4x) și nu vă deranjează un pic de complexitate suplimentară. De cele mai multe ori, acesta este un compromis util.

Adică configurația RSA mă definește deja p,q,d,c și deci nu am un sistem de congruențe.

De fapt, toți parametrii suplimentari $d_p, d_q, qinv$ sunt ușor de calculat în timpul generarii cheilor și așa facem de obicei.

Să presupunem $\log d = \log n=B$ și $\log p = \log q = B/2$ și $d,d_p,d_q$ au la fel de multe 0 și 1. Ce pot spune despre numărul de operații de dimensiune $B$ a acestei variante?

De fapt, numărul de 0 și 1 sunt în mare parte irelevante, putem efectua o exponențiere modulară a unui $B$ valoarea biților cu $(1 + o(1)) \log_2 B$ multiplicari modulare (independente de greutatea de hamming a exponentului); în intervalul B-urilor luate în considerare, aceasta poate fi $(1 + 1/6) \log_2 B$.

Cu operația privată RSA manual, aceasta implică o singură exponențiere modulară a a $B$ valoarea biților cu a $B$ biți exponent; este vorba despre $(1 + 1/6) \log_2 B$ se inmulteste. Dacă folosim un $O(n^2)$ algoritm de multiplicare modulară (care este aproximativ optim pentru intervalul de B despre care discutăm - există rutine de multiplicare cu complexitate asimptotică mai mică, dar cu constante de proporționalitate mult mai mari), vorbim despre $(1 + 1/6) (\log_2 B)^3$

Acum, cu CRT, există două exponentații modulare a două $B/2$ pic de a $B/2$ biți exponent (plus unele operații atât înainte, cât și după - ambele sunt relativ rapide). Folosind aceeași logică, acest lucru durează aproximativ $2 (1 + 1/6) (\log_2 B/2)^3 = 1/4 (1 + 1/6) (\log_2 B)$, adică de aproximativ 4 ori mai rapid (da, acest lucru înseamnă ignorarea unor factori mici); cu toate acestea, chiar dacă luăm în considerare acești factori mici, CRT este încă considerabil Mai repede

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.