Acesta este un răspuns puțin extins;
Mă întrebam dacă există alte modalități de a calcula inversul multiplicativ modular al unui punct pe o curbă eliptică (cum ar fi secp256k1)? Sau poate un motiv pentru care se dovedește imposibil?
Comunitatea bitcoin numește de obicei înmulțirea scalară obișnuită drept înmulțire1. Ceea ce definim ca înmulțire scalară ca
$$[k]G : = \underbrace{G + G + \cdots + G}_{k-time}$$ cu alte cuvinte, adăugarea unui punct în sine $k$ ori.
Există deja o problemă definită pentru aceasta (folosind versiunea EC $r$ este ordinea elementului de bază $G$, curba este de ordin prim și $E(K)$ este mulțimea punctului curbei);
Definiții;
- CDH : dat un triplu $(G,[a]G,[b])$ găsi $[ab]G$.
- Inversa-DH : dat o pereche $(G, [a]G) \in E(K) - \{\mathcal{O}\}$ a elementelor de ordin prim $r$ în $E(K)$ a calcula $[a^{-1}]G$.
- Pătrat-DH: Problema de calcul Square-DH
este dată $(G, [a]G )$ Unde $G \în E(K)$ are ordin primar $r$ a calcula $[a^2]G$.
Reduceri;
$\text{Inverse-DH} \leq_R \text{CDH}$.
Să presupunem că avem un oracol $O$ care rezolvă $\text{CDH}$. Ne este dat $(G,[a]G)$ dupa cum $\text{Inversa-DH}$ exemplu și vrem să găsim $P = [a]G$. Atunci noi avem $$G = [a^{-1}]P = [a^{-1}a]G = G$$
Acum, sună oracolul $O$ cu $O(P,G,G) = O(P,[a^{-1}]P,[a^{-1}]P) $ iar ieșirile oracolului $[a^{-2}]P$. A inlocui $P$ a obține $$[a^{-2}]P = [a^{-2}a]G = [a^{-1}]G$$ Aceasta arată reducerea.
$\text{Pătrat-DH} \leq_R \text{Inverse-DH}$.
Sa presupunem $O$ fii un oracol care rezolvă $\text{Inversa-DH}$ si lasa $(G, P = [a]G )$ să se acorde. Dacă $P = \mathcal{O}$ apoi întoarce-te $\mathcal{O}$ altfel $$O(P, G) = O(P , [a^{-1}]P) = [a]P = [a\cdot a]P = [a^2]P.$$ Aceasta arată reducerea.
Deci avem $\text{Square-DH} \leq_R \text{Inverse-DH} \leq_R \text{CDH}$. Dacă putem arăta asta $\text{CDH} \leq_R \text{Square-DH}$ atunci vom avea echivalența.
$\text{CDH} \leq_R \text{Square-DH}$
lăsa $O$ fi un oracol de rezolvat $\text{Pătrat-DH}$ si ni se dau $(G,[a]G, [b]G)$ ca $\text{CDH}$ instanță.
Apel $O$ de două ori cu $O(G,[a]G)$ și $O(G,[b]G)$ a obține $P= [a^2]G$ și $Q= [b^2]G$, respectiv.
Acum încă un apel $O(G, P+Q) = O(G, [a+b]G)$ si ia $$R = [(a+b)^2]G = [a^2+2ab+b^2]G.$$
Acum, în sfârșit, calculează $$[2^{-1}](R - (P+Q)) = [2^{-1} (a^2+2ab+b^2 -a^2 -b^2)]G = [ ab]G$$ Aceasta arată reducerea.
Prin urmare, avem echivalența. Deci, dacă $\text{CDH}$ e greu atunci $\text{Inversa-DH}$ este si greu. Ei bine, sperăm că acest lucru este pentru adversari non-cuantici.
Există o modalitate (alta decât forța brută) de a găsi un număr întreg care are ca rezultat 1 atunci când cheia publică este înmulțită cu acel număr întreg?
Pot citi asta în două feluri;
$1$ este identitatea curbei pe care o scriem $\mathcal{O}$, atunci avem identitatea $[r]P = \mathcal{O}$ pentru fiecare element al unei curbe prime de ordine $r$. Aceasta este definiția lui ordinea unui element în teoria grupurilor.
$1$ dupa cum $[a\cdot a^{-1}]G = [\color{red}{1}]G = G$ atunci acesta este $\text{Inversa-DH}$ așa cum am discutat.
1Ei bine, se poate (defini | apela) adunarea punctelor ca înmulțire a punctelor, totuși, adunarea este istorică și toate cărțile majore de curbe eliptice folosesc adunarea punctelor; Peste numerele complexe, orice curbă eliptică poate fi realizată ca $\mathbb C/\Gamma$
pentru niște zăbrele $\Gamma$. În acest caz, adunarea vine pur și simplu din adunarea standard a numerelor complexe.
