134 lines
3.6 KiB
Text
134 lines
3.6 KiB
Text
#{
|
|
REFERENCE PYTHON:
|
|
|
|
def scalarmult(P,e):
|
|
if e == 0: return [0,1]
|
|
Q = scalarmult(P,e/2)
|
|
Q = edwards(Q,Q)
|
|
if e & 1: Q = edwards(Q,P)
|
|
return Q
|
|
P (15112221349535400772501151409588531511454012693041857206046113283949847762202 . 46316835694926478169428394003475163141307993866256225615783033603165251855960)
|
|
E 36144925721603087658594284515452164870581325872720374094707712194495455132720
|
|
|
|
Q (38815646466658113194383306759739515082307681141926459231621296960732224964046 . 11903303657706407974989296177215005343713679411332034699907763981919547054807)
|
|
}#
|
|
|
|
(de inv (X)
|
|
(expmod X (- *Q 2) *Q) )
|
|
(de expmod (B E M)
|
|
(if (=0 E)
|
|
1
|
|
(let R
|
|
(%
|
|
(** (expmod B (/ E 2) M) 2)
|
|
M )
|
|
(when (bit? 1 E)
|
|
(setq R (% (* R B) M)) )
|
|
R ) ) )
|
|
(de xrecover (Y)
|
|
(let
|
|
(YY (* Y Y)
|
|
XX (* (dec YY) (inv (inc (* *D YY))))
|
|
X (expmod XX (/ (+ *Q 3) 8) *Q) )
|
|
(and
|
|
(n0 (% (- (* X X) XX) *Q))
|
|
(setq X (% (* *I X) *Q)) )
|
|
(and
|
|
(n0 (% X 2))
|
|
(setq X (- *Q X)) )
|
|
X ) )
|
|
(setq *S (0 -1 -2 -3 -4 -5 -6 -7 .))
|
|
(setq *B 256)
|
|
(setq *Q `(- (** 2 255) 19))
|
|
(setq *L `(+ (** 2 252) 27742317777372353535851937790883648493))
|
|
(setq *D `(* -121665 (inv 121666)))
|
|
(setq *I `(expmod 2 (/ (dec *Q) 4) *Q))
|
|
(setq *By `(* 4 (inv 5)))
|
|
(setq *Bxy
|
|
(cons
|
|
(% (xrecover *By) *Q)
|
|
(% *By *Q) ) )
|
|
(de edwards (P Q)
|
|
(let
|
|
(X1 (car P)
|
|
Y1 (cdr P)
|
|
X2 (car Q)
|
|
Y2 (cdr Q) )
|
|
(cons
|
|
(%
|
|
(*
|
|
(+ (* X1 Y2) (* X2 Y1))
|
|
(inv (inc (* *D X1 X2 Y1 Y2))) )
|
|
*Q )
|
|
(%
|
|
(*
|
|
(+ (* Y1 Y2) (* X1 X2))
|
|
(inv (- 1 (* *D X1 X2 Y1 Y2))) )
|
|
*Q ) ) ) )
|
|
#{
|
|
def scalarmult(P,e):
|
|
if e == 0: return [0,1]
|
|
Q = scalarmult(P,e/2)
|
|
Q = edwards(Q,Q)
|
|
if e & 1: Q = edwards(Q,P)
|
|
return Q
|
|
}#
|
|
(de scalarmult (P E)
|
|
(if (=0 E)
|
|
(cons 0 1)
|
|
(let Q (scalarmult P (/ E 2))
|
|
(setq Q (edwards Q Q))
|
|
(when (bit? 1 E)
|
|
(setq Q (edwards Q P)) )
|
|
Q ) ) )
|
|
(de edwards-OLD (P Q)
|
|
(let
|
|
(X1 (car P)
|
|
Y1 (cdr P)
|
|
X2 (car Q)
|
|
Y2 (cdr Q) )
|
|
(cons
|
|
(%
|
|
(*
|
|
(+ (* X1 Y2) (* X2 Y1))
|
|
(inv (inc (* *D X1 X2 Y1 Y2))) )
|
|
*Q )
|
|
(%
|
|
(*
|
|
(+ (* Y1 Y2) (* X1 X2))
|
|
(inv (- 1 (* *D X1 X2 Y1 Y2))) )
|
|
*Q ) ) ) )
|
|
(de steps (E)
|
|
(flip
|
|
(make
|
|
(while
|
|
(and
|
|
(link (swap 'E (/ E 2)))
|
|
(gt0 E) ) ) ) ) )
|
|
(de scalarmult-OLD (P E)
|
|
(let Q (cons 0 1)
|
|
(for I (steps E)
|
|
(and
|
|
(setq Q (edwards-OLD Q Q))
|
|
(bit? 1 I)
|
|
(setq Q (edwards-OLD Q P)) ) )
|
|
Q ) )
|
|
(test
|
|
25284030307275072399323765781911808870808430628110464498231579031341677944106
|
|
(inv 123456) )
|
|
(test
|
|
(edwards-OLD (cons 0 1) (cons 0 1))
|
|
(edwards (cons 0 1) (cons 0 1)) )
|
|
|
|
|
|
# (trace 'scalarmult)
|
|
(test
|
|
(scalarmult-OLD
|
|
(cons 15112221349535400772501151409588531511454012693041857206046113283949847762202 46316835694926478169428394003475163141307993866256225615783033603165251855960)
|
|
36144925721603087658594284515452164870581325872720374094707712194495455132720 )
|
|
(scalarmult
|
|
(cons 15112221349535400772501151409588531511454012693041857206046113283949847762202 46316835694926478169428394003475163141307993866256225615783033603165251855960)
|
|
36144925721603087658594284515452164870581325872720374094707712194495455132720 ) )
|
|
|
|
(msg 'ok)
|
|
(bye)
|