înregistrare Logare
Puncte:3
LeonMSH avatar Crypto

Algoritmul mai bun pentru modular exponentiation pe secp256k1/r1

drapel us
LeonMSH

Cunosc modular exponentiation ($r = b^e \bmod m$) este important pentru RSA și pot găsi un algoritm care, dacă e este exprimat în formă binară (pentru exp: )--într-un astfel de mod pentru un e lung de n biți, ne putem aștepta la operația modulară de multiplicare a ~1,5n runde.

Lucrez la realizarea unei metodologii de recuperare a cheii publice pentru ECC, cum ar fi secp256k1/r1. Există o implementare foarte eficientă în secp256k1 lib, dar aceasta a fost codificată în codul ASM - greu de înțeles. Dar cel puțin știu primul pas - trebuie să-l recuperezi $ry$ de la $rx$ (adică r al semnăturii). Este foarte ușor de obținut $ry^2$ din $rx$, dar în următorul va trebui să fac modular rădăcină pătrată - care poate fi convertit în modular de exponențiere pe teren, adică $e= (p+1)/4.$

OK, deci acum întrebările sunt:

  1. Există un alt algoritm mai bun decât exponentiația modulară obișnuită pentru a calcula ($r = b^e \bmod m$)?
  2. Sau, alternativ, există vreun algoritm de scurtătură special pentru secp256k1 pe care nu am nevoie să rulez deloc Modular Exponentiation și să mai pot recupera $ry$ din $rx$?
101
0 + 0
Puncte:2
fgrieu avatar Crypto
drapel ng
fgrieu

Nu există un substitut pentru multiplicarea modulară în criptosistemele întrebării. Unele limbi precum Python fac acest lucru ușor în scopuri educaționale, numai.

În RSA și DSA și, într-o măsură mai mică, criptomon ECC activat secp256k1 sau secp256r1, trebuie să calculezi $b^e\bmod m$ pentru mari $e$. Cei mai rapizi algoritmi (de ex. exponentiarea ferestrei glisante) efectua despre $\log_2 e$ pătrat modular și asemenea $\aproximativ0,2\,\log_2 e$ înmulțiri modulare. Cu toate acestea, există și alți algoritmi doar marginal mai scumpi (de ex. scara lui Montgomery) care poate fi mai bun din punct de vedere al securității împotriva canalelor laterale.

Fiecare înmulțire modulară sau modul pătrat $m$, pentru cele de mai sus sau (în ECC) adăugarea sau înmulțirea punctelor cu un scalar, are costul de calcul în creștere cel mult ca $(\log m)^2$ la folosirea algoritmilor învățați în școala primară adaptați la cuvinte de calculator în loc de cifre. Asta poate fi coborât la $(\log m)^{\approx1.6}$ cu Karatsuba sau $(\log m)^{\approx1.5}$ cu Toom-3, dar în ECC modulul $m$ nu este suficient de mare încât să plătească mult ($m$ este „doar” câteva sute de biți în ECC, mai degrabă decât câteva mii în RSA/DSA).

Când se dezvoltă semnătură sau criptare folosind secp256k1 sau secp256r1 de la zero în scopuri educaționale, există de obicei faze:

  • Obține ceva care funcționează, construind adunarea și dublarea punctelor în coordonate carteziene pe lângă înmulțirea modulară, apoi multiplicarea punctelor, apoi semnătura sau/și criptarea.
  • Să funcționeze mult mai rapid prin utilizarea unei reprezentări mai bune a punctului, de ex. coordonate proiective (care permite amânarea inversării modulare costisitoare până la sfârșitul înmulțirii punctelor)
  • Faptul ca acesta să funcționeze în siguranță, ceea ce este foarte greu și necesită de obicei rescrierea multor lucruri de la bază.
  • Optimizări de performanță.Acestea pot fi încercate în orice etapă, dar gândiți-vă la zicala „optimizarea prematură este rădăcina tuturor relelor”.

Câteva referințe online despre înmulțirea și exponențiarea modulară (nu ECC):

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.