înregistrare Logare
Puncte:3
Lordi avatar Crypto

Este posibil să se calculeze multiplicarea inversă a unui punct pe curba eliptică?

drapel gp
Lordi

Titlul trebuie să fie confuz. Imaginați-vă că avem această curbă:

$y^2 = x^3 + 9x + 17$ peste $\mathbb F_{23}$

Și știm

[4]P = (19, 20)

[8]P = (12, 17)

Dacă avem doar valoarea de $[8]P$, Este posibil să se calculeze $2^{-1}X$ și $2^{-1}Y$ de $[8]P$ a obține $[4]P$?

124
0 + 0
kelalaka avatar
drapel in
kelalaka
Înjumătățirea punctelor: [Înjumătățirea punctelor pe curbele eliptice de ordine uniformă](https://crypto.stackexchange.com/q/66106/18298) și articol [Înjumătățirea punctelor pe curbele eliptice de ordine uniformă](https://arxiv.org /pdf/0706.4379.pdf). Am corectat notația și chiar și noi spunem $x(P)$ pentru coordonata x a punctului $P$. Această curbă are o ordine uniformă = 32, deci este aplicabilă, dar nu așa cum arăți. Dublarea punctelor nu funcționează în acest fel.
1
Răspunde
kelalaka avatar
drapel in
kelalaka
[Dacă vă uitați la formulele de adunare](https://crypto.stackexchange.com/a/66296/18298) veți vedea că atunci când $P_1 = P_2 = [2]P_1$ nu este înmulțire cu 2. Puteți conecta numerele dvs. și faceți aritmetica din primul link pentru a o găsi fără jurnal discret.
0
Răspunde
Lordi avatar
drapel gp
Lordi
@kelalaka Mulțumesc pentru răspuns. Este posibilă înjumătățirea punctelor pe curbele eliptice de ordin impar?
0
Răspunde
kelalaka avatar
drapel in
kelalaka
Aveți grijă, înjumătățirea în ordine uniformă poate duce la o soluție dublă care împiedică rezolvarea DLOG. În cazul ciudat, fie $n = 2k-1$ ordinul, atunci putem găsi jumătatea ca; $[1/2]G = [k]G$ de ce? Deoarece $[2k-1]G = \mathcal{O}$, atunci $[2k-1]G + G = G$, deci $[k]G = [1/2]G$. Aceasta este o hartă bine definită pentru grupurile abeliene de ordin ciudat.
2
Răspunde
kelalaka avatar
drapel in
kelalaka
Acum, puteți vota și accepta în Cryptography.SE. votează dacă răspunsul este bun, acceptă dacă răspunsul este satisfăcător.
0
Răspunde
Puncte:1
Fractalice avatar Crypto
drapel in
Fractalice

Deoarece 2 împarte ordinea grupului (care este 32), există două preimagini. Ele pot fi găsite ca rădăcini ale polinomului de multiplicare cu 2 minus ținta $x$ (care poate fi calculat din polinoame de diviziune).

Exemplu în Sage:

salvie: E = ElipticCurve(GF(23), [9, 17])                                                                                                                                                                                                      
sage: E.multiplication_by_m(2)                                                                                                                                                                                                                
((x^4 + 5*x^2 + 2*x - 11)/(4*x^3 - 10*x - 1),
 (8*x^6*y - 8*x^4*y + 6*x^3*y + 3*x^2*y + 3*x*y + 6*y)/(-5*x^ 6 + 2*x^4 - 9*x^3 + 9*x^2 + 11*x + 4))

Acestea sunt cele două hărți raționale pentru calcul $x$ și $y$ a punctului $[2](x,y)$. Noi vrem $x$ să fie egal cu 19, deci:

sage: (E.multiplication_by_m(2)[0] - 19)
  .numărător()
  .polinom_univariat()
  .roots(multiplicitități=False)
[20, 10]

Putem verifica asta $[2](20, *) = (19, *)$. Rețineți că semnul de $y$ trebuie ales pentru a se potrivi cu semnul de ieșire.

salvie: P = E.lift_x(20)                                                                                                                                                                                                                        
salvie: 2*P                                                                                                                                                                                                                                     
(19 : 3 : 1)
salvie: 2*(-P)                                                                                                                                                                                                                                  
(19:20:1)

Poate fi repetat de două ori pentru a obține 4-rădăcini sau utilizați direct harta înmulțirii cu 4 (care este puțin mai puțin eficientă).

0 + 0
kelalaka avatar
drapel in
kelalaka
Există o definiție formală a „înmulțirii_cu_m”.
0
Răspunde
Fractalice avatar
drapel in
Fractalice
@kelalaka `multiplication_by_m` este o pereche de funcții $(f(x),y\cdot g(x))$, astfel încât această pereche să fie egală cu $[n]P$ când $P=(x,y)$. Pe pagina wikipedia despre polinoamele de diviziune pe care am legat-o, există formule pentru construirea $f(x)$ și $g(x)$, care sunt funcții raționale.
1
Răspunde
kelalaka avatar
drapel in
kelalaka
Și. puteți edita întrebarea, astfel încât pentru referințe viitoare să poată fi găsită mai ușor.
0
Răspunde
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.