Indonesi
an
Journa
l
of El
ect
ri
cal Engineer
ing
an
d
Comp
ut
er
Scie
nce
Vo
l.
13
,
No.
3
,
Ma
rch
201
9
, p
p.
910
~
918
IS
S
N: 25
0
2
-
4752, DO
I: 10
.11
591/ijeecs
.v1
3
.i
3
.pp
910
-
918
910
Journ
al h
om
e
page
:
http:
//
ia
es
core.c
om/j
ourn
als/i
ndex.
ph
p/ij
eecs
A compa
riso
n b
etween th
e secp2
56
r1
and t
he
kobli
t
z secp2
56k1
bitcoin
cu
rves
Az
ine Hou
ri
a
1
, Bencheri
f
Moh
amed Ab
de
lkader
2
,
Gues
so
um
Abderez
z
ak
3
1
Instit
ute of
A
er
onaut
i
cs
and
Spa
ce
Stud
ie
s
,
La
bo
ra
tor
y
of
Aeron
a
uti
c
al
Sc
ie
n
ce
s
,
Bli
da1
Univer
sit
y
A
lge
ri
a
,
Al
ger
i
a
2
Coll
ege of
Com
pute
r and
Inform
at
ion
Scie
n
ce
s
,
Cent
er
of
Sm
art
Roboti
cs
R
ese
ar
chKing
,
Saud
U
nive
rsit
y
,
Arab
Saudi
3
Depa
rtment of
El
e
ct
roni
cs
,
LATSI
Signal Proc
essing
and
Im
ag
i
ng
La
bor
at
or
y
,
Bli
da1
Univer
sit
y
A
lge
ri
a
,
Alger
i
a
Art
ic
le
In
f
o
ABSTR
A
CT
Art
ic
le
history:
Re
cei
ved
Sep
18, 201
8
Re
vised
N
ov 23, 2
018
Accepte
d
Dec
11, 201
8
Bit
coi
n
uses
elli
pti
c
cur
v
e
cr
y
pt
ogra
ph
y
for
it
s
ke
y
s
and
signa
t
ure
s,
but
th
e
spec
ific
sec
p256
k1
cur
ve
us
ed
is
rat
h
er
unusual
.
The
ECDSA
ke
y
s
used
to
gene
ra
te
Bit
coin
addr
esses
and
sign
tra
nsac
tions
are
der
ive
d
from
som
e
spec
ific
par
amet
ers.
Due
to
thi
s
cha
racte
r
isti
c
,
seve
ral
quest
ion
s
come
up
conc
ern
ing
Sat
o
shi’s
choi
ce
of
thi
s
cur
ve
rather
tha
n
that
of
the
NIS
T
standa
rd
se
cp25
6r1
cur
ve
.
Form
er
Presiden
t
Dan
Brown’s
addr
ess
to
Bit
coi
n
users
on
the
Bit
coi
n
t
al
k.
org
onl
ine
forum
conce
rning
the
use
of
sec
p256k1
in
Bit
coi
n
of
SECG
show
ed
his
surprise
t
o
see
som
e
one
uses
SEC
G
sec
p256k1
instead
of
sec
p256r1
of
NIS
T.
In
thi
s
art
i
cl
e
,
we
will
ana
l
y
z
e
th
e
ran
dom
sec
p25
6r1
cur
ve
and
the
Kobl
it
z
Sec
p256k1
cur
ve
(
par
amete
rs
,
equa
t
ion,
aut
om
orphism
…),
b
y
givi
ng
th
e
stren
gths
and
wea
kn
e
ss
es
of
ea
ch
one
of
th
em,
in
orde
r
to
just
if
y
t
he
choice
of
Bit
coi
n’s
creat
or
,
a
nd
the
n
w
e
will
t
ac
k
le t
he
m
ini
ng
using
the n
ew
gra
phi
c ca
rds
.
Ke
yw
or
ds:
Bi
tc
oin
ECC
Mi
nin
g
Secp
256k1
Secp
256r1
Copyright
©
201
9
Instit
ut
e
o
f Ad
vanc
ed
Engi
n
ee
r
ing
and
S
cienc
e
.
Al
l
rights re
serv
ed.
Corres
po
nd
in
g
Aut
h
or
:
Azine
H
ouria
,
In
sti
tute
of A
e
r
on
a
utics a
nd S
pace St
ud
ie
s
.
Lab
or
at
ory
of
Aero
nau
ti
cal
S
ci
ences.
Bl
ida1 Un
i
ver
s
it
y Algeria ,
A
l
ger
ia
Em
a
il
:
azi
neh
ou@ya
hoo.fr
1.
INTROD
U
CTIO
Ell
ipti
cal
Curve
Crypto
gr
a
phy
(ECC)
intr
oduce
d
by
Nea
l
Koblit
z
and
V
ic
tor
Mi
ll
er
al
lows
the
achievem
ent
of
asy
m
m
et
ri
c
crypt
ogra
phy
and
fa
ste
r
sign
at
ur
e
tha
n
in
RS
A
f
or
a
sim
il
ar
lev
el
of
secur
it
y
[
1],
[
2]
.
In
a
ddit
ion
,
co
m
par
ed
to
RSA,
ECC
al
lo
ws
the
c
om
pu
t
at
ion
o
f
pairin
gs
that
c
urre
ntly
al
lows
bu
il
di
ng of
ne
w
c
rypto
gr
a
p
hic pro
t
oco
ls,
wh
ic
h
can
b
e
a
n
a
dv
a
ntage
for s
om
e app
li
cat
ion
s.
Tw
o
orga
nism
s
are
know
n
to
pate
nt
m
os
t
of
the
el
li
ptic
curve
al
gori
thm
ic
pr
operti
es,
nam
el
y
NI
S
T
[3
]
an
d
Ce
rtic
om
[4
]
.T
hey
bo
t
h
pro
pose
the
us
e
of
W
ei
e
rstrass
-
ba
sed
cu
rv
e
s
th
at
util
iz
e
a,
b
a
nd
p
par
am
et
ers.
Th
e tun
i
ng choice
s of the
se
par
a
m
et
ers
rem
ai
n
in m
any stud
ie
s a c
om
plete
secret.
nam
ely
the
NI
ST
[3
]
an
d
Ce
r
ti
co
m
[4
]
.
The
y
bo
th
propose
to
us
e
W
ei
erst
rass
-
base
d
cu
r
ves
that
use
the
Sec
p256r
1
and
sec
p256k1
Curves
a
re
t
w
o
e
xam
ples
of
two
el
l
ipti
c
c
urves
us
e
d
i
n
va
rio
us
c
rypto
gr
a
ph
ic
protoc
ols s
uc
h as TLS
, SSH,
ECDS
A,
ECD
HE, EC
D
H
a
nd EC
DLP.
In
fact
the
cal
c
ulati
on
s
on
the
el
li
ptic
cur
ve
s
,
are
gove
rn
e
d
by
so
m
e
sp
eci
al
m
at
he
m
atical
group
la
w
op
e
rati
ons
(a
ddit
ion
o
f
po
i
nts
in
a
Finit
e
fiel
d)
p
art
ic
ula
rly
gr
ee
dy
in
te
rm
s
of
m
od
ula
r
operati
ons o
f
a
ddit
ion
,
m
ul
ti
plica
ti
on
an
d
in
versi
on.
T
he
c
os
t
of
the
operati
ons
dep
e
nds
on
the
el
li
ptic
scal
ar
m
ulti
plica
ti
on
op
e
rati
on. T
he im
ple
m
entat
io
n
of ell
ipti
c cur
ve
ci
phe
rs
re
quires a f
i
ne
arc
hitec
tural stu
dy
a
nd
desig
n,
i
n
orde
r
to f
i
nd the
best
co
m
pr
om
ise
b
et
ween
c
om
plexity
an
d s
peed
com
pu
ta
ti
on
.
The
tw
o
m
ajo
r
prop
e
rtie
s
for
the
data
com
m
un
ic
at
ion
are
Con
fi
den
ti
al
it
y
and
Secrecy
.
Ther
e
fore,
the
sec
ur
it
y
of
the
c
urves
rel
ie
s
on
se
ver
al
m
at
he
m
at
ic
a
l
crit
eria,
w
h
ic
h
are
c
urre
ntly
m
ai
nly
sh
ared
by
the
crypto
gr
a
phy
c
omm
un
it
y.
The
m
ai
n
te
ns
ion,
ar
ound
t
he
se
le
ct
ion
of
t
he
curves
t
o
be
norm
al
iz
ed,
is
r
unni
ng
Evaluation Warning : The document was created with Spire.PDF for Python.
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci
IS
S
N:
25
02
-
4752
A com
pa
ris
on
betwe
en
t
he
se
cp25
6r1an
d
th
e ko
blit
z secp2
56
k
1 bit
coi
n
c
ur
ves
.
..
(
Azi
ne Houria
)
911
on
t
he
evalua
ti
on
of
the
a
dv
a
ntage
s
an
d
disad
van
ta
ge
s
of
eac
h
cu
r
ve
(the
e
quat
ion,
ch
oice
of
curve
par
am
et
ers,
pe
rfor
m
ance
an
d
resist
ance
to
at
ta
cks
by
a
ux
il
ia
ry
c
hann
el
s,
sim
plicity
of
im
ple
m
ent
at
ion,
eff
ic
ie
ncy,
r
igi
dity
, b
ac
k doo
r
s and sa
fety
).
2.
CUR
VES S
E
CP
256R1
/
NIST
P
-
256 OVE
R
THE
FINIT
E FIE
LDS
The
m
os
t
us
ed
el
li
ptic
cur
ves
are
tho
se
pr
opose
d
by
the
NI
S
T
on
(
p
)
intr
oduce
d
in
F
IP
S
[
5].
They
us
e
s
pecial
num
ber
s.
The
cu
rv
e
par
am
et
ers
m
us
t
be
caref
ully
cho
se
n
to
avo
i
d
us
i
ng
a
weak
c
urve,
a
nd
t
ha
t
can
with
sta
nd
al
l
kn
ow
n
at
ta
cks.
T
he
re
m
a
y
al
so
be
oth
er
const
raints
f
or
secur
it
y
or
im
plem
entat
ion
reasons.
Fo
ll
owin
g
S
E
C
2
[
6],
the
do
m
ai
n
par
am
et
e
rs
of
the
el
li
ptic
on
Fp
a
re
a
s
ix
-
f
old
T
=
(
p,
a,
b,
G,
n,
h).
Do
m
ai
n
p
aram
et
ers
as s
how
n
in
Ta
ble
1.
Table
1.
D
om
a
in
P
a
ram
et
ers
P
The o
rder of
the p
r
i
m
e f
ield
Fp
Seed
The
seed
sele
cted
to
rand
o
m
l
y
g
en
e
rate,
th
e
co
ef
f
icien
t
s
o
f
th
e
ellip
tic
cu
rve.
The
1
6
0
-
b
it
SE
ED
in
p
u
t seed
to th
e SHA
-
1
bas
ed
on
algo
rith
m
(
th
e s
eed p
ara
m
e
ter
do
m
ain
)
r
The o
u
tp
u
t of
SHA
-
1
a,b
The coef
f
icien
ts o
f
th
e elliptic cu
rve
y
2
=
x
3
+ax
+b sati
sf
y
in
g
r
b2
≡
a3
(
m
o
d
p)
.
n
th
e (
p
ri
m
e
)
o
rde
r
o
f
the b
ase
p
o
in
t P.
h
The cof
acteur
x
,y
The x
and
y
co
o
rdin
ates o
f
P.
2.1.
Mathem
at
ic
al appr
oa
c
h
2.1.1
The
pri
me num
ber p
The
p
of
t
he
P
-
256
c
urve
is
a
pr
im
e
nu
m
ber
of
ge
ner
al
iz
ed
Me
rsien.
It
is
r
ecom
m
end
e
d
to
work
on
a
fiel
d
w
hose
siz
e
is
256
bits.
This
pri
m
e
n
um
ber
has
the
prop
e
rty
that
it
can
be
wr
i
tt
en
as
the
sum
or
diff
e
re
nce
o
f a
sm
a
ll
n
um
ber
of powe
rs o
f 2:
The
powe
rs
a
pp
ea
rin
g
i
n
thi
s
ex
pr
e
ssio
n
a
re
al
l
m
ulti
ple
s
of
32.
T
hese
pro
per
ti
es
give
re
du
ct
i
on
al
gorithm
s
that
are
par
ti
cula
rly
rap
id
on
m
a
chines
with
w
ordize
of
32
[
7].
This
op
ti
m
iz
at
ion
is
par
ti
cularly
eff
ic
ie
nt
on CP
U.
Let
t =
23
2
t
hen
(
1) b
ec
ome
s:
p256 =
2
256
-
2
224
+ 2
192
+ 2
96
–
1
(1)
We ca
n
th
en
r
e
du
ce
the
powe
r
s h
i
gh
e
r
tha
n 2
b
y
us
in
g
t
he
c
ongrue
nce
for
(2)
s
o
t
he
c
ongrue
nce
relat
ion i
s:
P
=
t
8
-
t
7
+ t
6
+
t
3
–
1
(2)
t
4
≡ t
2
+ t (m
od p), 2
256
≡
2
128
+2
64
(m
od
p)
(3)
This
P
-
25
6
pr
i
m
e
nu
m
ber
is
chosen
f
or
e
ff
i
ci
ency
(m
od
ul
ar
m
ulti
plica
t
i
on
can
be
pe
rfor
m
ed
m
or
e
ef
fici
ently
than
i
n
general
).
Al
gorithm
2.1
s
hows
the
fa
st
reducti
on
by
p256.
Ra
pi
d
r
edu
ct
io
n
m
odul
o
p2
56
as
s
ho
w
n
in
Figure
1.
Algorit
hm
[7]
:Ra
pid
r
educ
t
ion
m
odulo
p
256
= 2
256
−2
224
+2
192
+2
96
−1
INP
UT:
An i
nteger
c
=
(c
15
,
.
.
.
,
c
2
, c
1
,
c
0
) in b
ase
2
32
with
0
≤ c
<
p
2
256
.
OU
TPUT:
c
m
od
p
256
.
1.
Defi
ne
256
-
b
it i
nte
ger
s:
s
1
=
(c
7
, c
6
,
c
5
,
c
4
, c
3
,
c
2
,
c
1
,
c
0
),
s
2
=
(c
15
, c
14
,
c
13
, c
12
,
c
11
,
0
,
0,
0)
,
s
3
=
(0, c
15
, c
14
,
c
13
,
c
12
,
0
,
0,
0)
,
s
4
=
(
c
15
,
c
14
,
0
,
0,
0,
c
10
,
c
9
,
c
8
)
,
s
5
=
(
c
8
,
c
13
,
c
15
,
c
14
,
c
13
,
c
11
,
c
10
, c
9
),
s
6
=
(c
10
, c
8
,
0,
0
,
0,
c
13
,
c
12
,
c
11
)
,
s
7
=
(
c
11
,
c
9
,
0
,
0,
c
15
,
c
14
,
c
13
,
c
12
),
s
8
=
(c
12
,
0,
c
10
,
c
9
,
c
8
,
c
15
,
c
14
,
c
13
)
,
s
9
=
(
c
13
,
0
,
c
11
,
c
10
, c
9
,
0,
c
15
,
c
14
).
2.
2.
Re
turn
(s1
+2
s2 +
2s3 +
s4
+s5
−s6
−s7
−s8
−s9
m
od
p256)
Figure
1.
Ra
pi
d red
uctio
n
m
od
ul
o p25
6
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2502
-
4752
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci,
Vo
l.
13
, N
o.
3
,
Ma
rc
h
2019
:
910
–
918
912
2.1.2
El
li
pt
ic
c
urve
E
qu
at
io
n
The
el
li
ptic cu
r
ve
is i
s
om
or
ph
ic
to
a c
urve
w
it
h
a re
duced
Weierstras
s e
quat
ion o
f
t
he fo
rm
(
(p
)
):
2
=
3
+
∙
+ b
m
o
d
if
≠ 2.
(4)
a)
The Disc
rim
inant and
J
-
in
va
r
ia
nt
Δ = 4a
3
+
27
b and j
(
E
)
=
(
-
48a)
3
/Δ
[
8]
(5)
1)
if Δ =
0
the
n
e
qu
at
io
n (
4)
is
not an
ell
ipti
c curve,
it
is a sin
gu
la
r
c
ub
ic
.
2)
If
Δ
<
0
then
t
he
grap
h
of
the
el
li
ptic
cur
ve
has
only
on
e
c
om
po
ne
nt.
The
cub
ic
poly
no
m
ia
l
x
3
+
ax
+
b
has
a
sin
gle
root
that
corres
ponds
to
the
a
bsc
issa
of
the
int
ersecti
on
point
of
the
c
urve
w
it
h
the
abscissa
axis.
3)
If
Δ>
0 the
n
th
e grap
h of t
he e
ll
ipti
c cur
ve
has t
w
o
c
om
po
ne
nts.
T
he
c
ubic
poly
no
m
ia
l
x
3
+ax+
b
ha
s
3
roots,
wh
ic
h
c
or
res
pond
to
th
e
abscissa
of
th
e
three
points
of
inte
rsecti
on
of
the
c
urve
wi
th
the
abscissa
axis.
J
-
in
var
ia
nt
≠
0
and
K
is
a
fiel
d
of
cha
racter
ist
ic
≠
2,
3
then
the
orde
r
of
the
autom
or
ph
is
m
is
equ
al
t
o 2.
b)
Com
plexity
In
gen
e
ral,
the
group
of
poin
ts
of
an
e
ll
ipti
cal
cur
ve
beh
a
ves
li
ke
a
"Ge
ner
ic
gro
up",
the
discret
e
log
a
rithm
has
an
ex
pone
ntial
com
plexity
[9
]
.
The
group
of
reg
ula
r
points
is
then
isom
or
ph
ic
to
an
ad
di
ti
ve
or
m
ul
ti
plica
ti
ve
gro
up,
an
d
the
discrete
lo
gar
it
hm
is
su
b
-
e
xponentia
l,
eve
n
poly
no
m
ia
l.
It
is
i
m
per
at
ive
that
Δ
≠
0
(
wh
at
happe
ns
with
P
≈
1)
.
More
pr
eci
se
ly
,
the
com
ple
xity
of
a
disc
r
et
e
log
arit
hm
i
s
do
m
inate
d
by
√q
,
wh
e
re
q
is
the
utm
os
t
pr
i
m
e
div
is
or
of
the
nu
m
ber
of
points
of
the
c
urv
e
so
to
increas
e
the
com
plexi
ty
i
t
is
necessa
ry
to
ha
v
e
a
num
ber
of
points
(alm
os
t)
first.
T
here
are
ge
ner
ic
a
tt
acks
of
c
om
plexity
O
(√q),
wh
e
re
q
is t
he utm
os
t pr
im
e d
ivisor
of N
.
A safe
cur
ve
m
us
t t
her
ef
ore ha
ve q
≈ N; i
deall
y, q
=
N.
The
pro
bab
il
it
y
that
a
rand
om
cur
ve
has
a
pr
im
ary
order
is
appr
ox
im
ately
the
sam
e
a
s
a
ra
ndom
nu
m
ber
of
t
he
siz
e
of
p
is
pri
m
e,
P
≈
1/lo
g
p
[
9].
Com
plexity
of
g
ene
r
ic
a
tt
acks
as
s
how
n
in
Table
2
a
nd
Figure
2.
Table
2.
C
om
plexity
o
f
G
e
neri
c
A
tt
acks
Metho
d
Fastes
t kn
o
wn
attack th
e f
astes
t kn
o
wn
attack
RSA
Nu
m
b
e
r
Fi
eld
Siev
e e
x
p
(1/2
(log
N)1/3
(log
lo
g
N)2/3
)
ECC
Po
llard
-
rho
√
r
=
e
x
p
(1/2
log
r
)
Alg
o
rith
m
2 Po
in
t
Do
u
b
lin
g
(
y
2
= x
3
−3
x
+b, Jacob
ian
coo
rdin
ates)
INPU
T:
P
= (
X1
:
Y1
:
Z1)
in
Jaco
b
ian
coo
rdin
ates o
n
E
/K :
y
2
=
x
3
−3
x
+b.
OUTPU
T:
2
P
= (
X
3
:
Y3
:
Z3
)
in
Jac
o
b
ian
coo
r
d
in
ates.
1
.
If
P
=
∞ th
en
r
et
u
rn (∞)
.
2
.
T
1
←Z
2
1
.{
T
1
←Z
2
1
}
3
.
T
2
← X
1
− T
1
.
{
T
2
← X
1
−
Z
2
1
}
4
.
T
1
← X
1
+ T
1
.
{
T
1
← X
1
+
Z
2
1
}
5
.
T
2
←T
2
· T
1
.
{T
2
← X
2
1
−
Z
4
1
}
6
.
T
2
←3
T
2
.
{
T
2
←
A =
3
(X1
− Z
2
1
)
(X
1
+ Z
2
1
)}
7
.
Y
3
←2
Y
1
.
{Y
3
←
B =
2
Y1
}
8
.
Z
3
←Y
3
·
Z
1
.
{Z
3
← B Z
1
}
9
.
Y
3
←Y
2
3
.{Y
3
←
C = B
2
}
1
0
.
T
3
←Y
3
·
X
1
.{T
3
← D
= C
X
1
}
1
1
.
Y
3
←Y
2
3
.
{Y
3
←C
2
}
1
2
.
Y
3
←Y
3
/2
.
{Y
3
←C
2
/2
}
1
3
.
X
3
←T
2
2
.
{X
3
← A
2
}
1
4
.
T
1
←2
T
3
.
{T
1
←2
D}
1
5
.
X
3
← X
3
−
T
1
.
{X
3
← A
2
−2
D}
1
6
.
T
1
←T
3
−
X
3
.
{
T
1
← D
− X
3
}
1
7
.
T
1
←T
1
·
T
2
.
{
T
1
← (
D
−
X
3
)A}
1
8
.
Y
3
←T
1
−Y
3
.
{
Y
3
← (
D
−
X
3
)A−
C
2
/2
}
1
9
.
Retu
rn(X
3
: Y
3
: Z
3
).
Figure
2.
P
oin
t
doubli
ng
Evaluation Warning : The document was created with Spire.PDF for Python.
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci
IS
S
N:
25
02
-
4752
A com
pa
ris
on
betwe
en
t
he
se
cp25
6r1an
d
th
e ko
blit
z secp2
56
k
1 bit
coi
n
c
ur
ves
.
..
(
Azi
ne Houria
)
913
c)
Sele
ct
ion
of th
e p
a
ram
et
er a
=
-
3
Most
sta
ndar
ds
see
the
IE
EE
1363
-
20
00
sta
nd
a
r
d
[
10]
,
c
hoose
a
=
-
3
be
cause
pr
act
ic
al
ly
al
l
cur
ve
s
hav
e
l
ow
orde
r
iso
gen
ie
s
a
nd
this
f
or
reas
on
s
of
e
ff
ic
ie
nc
y
so
this
ch
oice
do
es
not
af
fect
safety
.
Ch
oo
si
ng
sm
a
ll
values
fo
r
a
a
nd
b
pa
r
a
m
et
ers
m
akes
it
po
ssible
to
acce
le
rate
the
arit
hm
etic
of
the
cu
rv
e
.
Sim
i
la
rly
,
Brai
npool [
11]
u
ses
this e
qu
at
ion
for
it
s a
dv
a
ntages
. T
his c
hoic
e sa
ves 2
of the
10 m
ulti
pli
ca
ti
on
s
require
d
f
or
add
i
ng
points.
A
ra
ndom
curve
on
Fp
is
is
om
or
ph
ic
with
a
curve
a
=
-
3
with
pr
ob
a
bili
ty
:
P
=
1/4
if
p
≡
+1
(m
od
4)
a
nd
P
=
1/2
if
p
≡
-
1
(m
od
4).
And
fi
nally
“a”
the
sel
ect
io
n
=
-
3
f
or
t
he
c
oeffici
ent
in
th
e
e
ll
ipti
c
curve
e
quat
ion
has
be
e
n
m
ade
so
t
hat
the
points
of
the
el
l
ipti
c
curve
represente
d
in
the
j
ac
ob
ia
n
pro
j
e
ct
ive
coor
din
at
es c
ould
be
a
dded
usi
ng a f
ie
ld
m
ulti
plica
ti
on
o
f
less. T
he Fi
gure
2
desc
ribes
th
e Po
i
nt Do
ub
li
ng .
The
or
der
of
th
e
el
li
ptic
cur
ve
s
us
ed
i
n
crypt
ogra
ph
y
m
us
t
resp
ect
so
m
e
con
strai
nts
in
ord
er
to
av
oi
d
known
at
ta
cks
.
F
or
e
xam
ple,
this
orde
r
m
us
t
be
a
pr
im
e
nu
m
ber
of
la
r
ge
siz
e
or
t
he
Product
of
a
pr
im
e
nu
m
ber
a
nd a s
m
al
l i
nteger
or
cof
act
or
,
whic
h
is
1
i
n
the
ca
se of a
pri
m
e o
rd
e
r
c
urve.
d)
Cofacto
r
NI
S
T take
s th
e
cofact
or as sm
al
l as p
os
sible
for
e
ff
ic
ie
ncy
r
easo
ns
:
h
=
c
a
rd
(
E
(
F
)
)
n
(6)
W
it
h
h
t
he
co
f
act
or
=
the
ord
er
of
the
el
li
ptic
curve
/n;
with
n
orde
r
of
the
po
i
nt
w
hich
is
the
sm
allest
int
eger
su
c
h
that
(n.G)
= 0 (
0: elem
ent iden
ti
ty
o
f
the
f
init
e
group
)
a
nd G m
us
t be c
ho
s
en
so that
n i
s a lar
ge
inte
ge
r.
So
so
m
e
sta
ndard
s
cry
ptogra
ph
ic
,
s
uch
as
F
IP
S
-
186
-
4
[
5],
advocate
the
use
of
cu
rv
e
s
with
a
"s
m
all"
cof
act
or
h. I
n p
racti
ce, the c
on
strai
nts m
ay
d
iffe
r
f
r
om
o
ne
s
ta
nd
a
rd to a
nother
.
Fo
r
exam
ple,
the
fi
rs
t
ve
rsion
of
SEC
1
(
2000)
im
po
se
d
a
c
of
act
or
h
≤
4
wh
e
reas
t
he
fi
r
st
ver
si
on
of
2009
reco
m
m
e
nd
s
r
at
her h
≤
2α and α
f
or
a
higher
level
of
secur
it
y.
The
c
hoic
e of t
he
c
of
act
or
val
ue depe
nds t
he
refor
e
on its
va
lue b
eca
us
e:
{
si
h
≤
1
F
or
eff
cie
ncy
reas
ons
si
h
>
Impro
ve
perform
ances
Ci
ti
ng
as
exam
ples
the
Mo
ntgom
ery
cur
ves
us
e
d
by
A
pple
wh
ic
h
ha
ve
a
cof
act
or
h
>
4
and
t
hat
t
o
i
m
pr
ove
the
pe
rfor
m
ance
of
the
cu
rv
e
.
T
he
Table
3
su
m
m
arizes
the
f
orm
s
of
el
li
ptic
curves
on
F
p
us
a
bl
e
accor
ding t
o
th
e
co
factor.
Table
3
.
Form
s
o
f
Ell
ipti
c Cu
r
ves
o
n
F
p Usa
ble A
cc
ordi
ng
t
o
t
he
C
of
act
or
[
11
]
Co
f
acto
r
h
Fo
r
m
1
W
eie
rstrass
2
Exten
d
ed
Jaco
b
i Quartic fo
r
m
3
Gen
eralize
d
Hess
i
en
4
Jaco
b
i Quartic
f
o
r
m
o
r
Edwards
f
o
r
m
e)
Param
et
er b
Fo
r
the
p
a
ram
e
te
r
b o
f
t
he
P
-
256 cu
r
ve,
t
he
f
ollow
i
ng for
m
ula is
us
ed
to g
ener
at
e it
:
b
=
√
(
−
27
SHA1
(
s
)
)
(7)
W
it
h:s=c4
9d3608
86
e
7049
36a667
8e11
39d2
6b7819
f7
e
90 [1
2
]
.
This
proc
ed
ure
gen
e
rates
ra
ndom
data
by
feed
i
ng
th
e
seed
int
o
SH1
[
13
]
.
Ver
i
fiable
ra
ndom
par
am
et
ers
off
er
a
dd
it
io
nal
c
on
s
er
vative
c
ha
racteri
sti
cs
[
1
].
These
pa
ram
et
ers
are
sel
ect
ed
f
r
om
a
seed
us
in
g
SHA
-
1
as
sp
ec
ifie
d
in
A
NSI
X9.62
[
1
4
]
.
Th
is
pr
oce
ss
ens
ures
that
the
pa
r
a
m
et
ers
cannot
be
red
et
e
rm
in
ed.
I
t
is
so
ext
rem
ely
i
m
pr
ob
a
blethat
the
par
am
et
ers
will
be
s
usc
eptible
to
fut
ur
e
s
pecial
-
pu
rpose
at
ta
cks
a
nd
no
traps
c
ould
be plac
ed
i
n
t
he p
ar
am
et
e
rs
du
ri
ng their
g
e
nera
ti
on
.
2.2.
Algebric
a
p
proach
a)
Group
la
w
: f
or
E/K: y
2
=
x
3
+
ax
+
b, c
har (
K)
≠ 2,
3
b)
Id
e
ntit
y
:
P
+
∞
=
∞
+ P =
P
for
al
l P
∈
E (K
).
c)
Neg
at
ive:
If
P
=
(x,
y)
∈
E
(
K)
,
the
n
(
x,
y
)
+
(x,
-
y)
=
∞
.
Th
e
po
i
nt
(
x,
-
y)
i
s
de
no
te
d
by
-
P
and
is
cal
le
d
the n
e
gative
of
P; note t
hat
-
P
is in
deed a
po
i
nt in E (
K
).
Al
so
,
-
∞
=
+
∞
d)
Additi
on:
Let
P = (x
1, y1)
∈
E (K)
and
Q
=
(x2, y
2)
∈
E
(K), w
he
re P =
± Q.
The
n
P
+
Q
=
(
x3, y3),
where:
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2502
-
4752
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci,
Vo
l.
13
, N
o.
3
,
Ma
rc
h
2019
:
910
–
918
914
3
=
(
2
−
1
2
−
1
)
2
−
2
1
−
2
and
3
=
(
2
−
1
2
−
1
)
2
−
(
1
−
3
)
−
1
(8)
e)
Po
int
D
oublin
g
Let
P
=
(x1,
y
1)
∈
E
(K)
, wh
ere P
=
-
P.
The
n 2P
=
(x3,
y3), whe
re:
3
=
(
3
2
+
2
1
)
2
−
2
1
an
d
3
=
(
3
2
+
2
1
)
2
−
(
1
−
2
)
−
1
(9)
The
c
of
act
or is
alway
s
h
=
1.
2.3.
Sele
c
tion o
f
t
he p
ar
am
eters
of t
he
cu
rve
The
sel
ect
ion
of
the
cu
rve
is
conditi
on
e
d
by
the
fo
ll
ow
i
ng
par
am
et
ers.
Th
e
p
and
n
inte
ge
rsar
e
gi
ven
in d
eci
m
al
f
orm
; bit
string
s
a
nd f
ie
ld
elem
e
nts ar
e
g
i
ven in
h
e
xad
eci
m
al
.
y2=x
3
-
3x +
41
058363
725152
142129
326129
780047
268409
114441
015993
725554
835256
314039
467401
291
Table
4.
NIST
-
Re
com
m
end
ed
Ran
do
m
Ell
ipti
c Curves
O
ver Pr
im
e Fiel
ds
[6]
Para
m
eters
Valu
e
p
2
^
2
5
6
-
2
^
22
4
+
2
^
19
2
+
2
^
9
6
-
1
f
ff
ff
f
ff
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
ff
ff
ff
f
ff
ff
ff
ff
ff
f
ff
ff
f
f
b
5
ac63
5
d
8
aa3a9
3
e
7
b3
eb
b
d
5
5
7
6
9
8
8
6
b
c 65
1
d
0
6
b
0
cc53
b
0
f
6
3b
ce3c3
e 2
7
d
2
6
0
4
b
n
f
ff
ff
f
ff
00
0
0
0
0
0
0
f
f
ff
ff
f
ff
ff
f
ff
ff
bce6f
aad a7
1
7
9
e8
4
f
3
b
9
cac2f
c6
3
2
5
5
1
Seed
c4
9
d
3
6
0
8
8
6
e7
0
4
9
3
6a6
6
7
8
e1
13
9
d
2
6
b
7
819f7
e9
0
c
7
ef
b
a1
6
6
2985
b
e9
4
03
cb
0
5
5
c 75
d
4
f7e0
ce8d
8
4
a9
c5114
ab
c af3
1
7
7
6
8
0104
f
a0
d
Gx
6
b
1
7
d
1
f
2
e12
c4
2
4
7
f
8
b
ce6e5
6
3
a4
4
0
f
2
7703
7
d
8
1
2
d
eb
3
3
a0
f
4
a
1
3
9
4
5
d898
c2
9
6
Gy
4
f
e3
4
2
e2
f
e1
a
7
f
9
b
8ee7
eb
4
a 7c0
f
9
e
1
6
2b
ce33
5
7
6b
3
1
5
ece
cb
b
6
4
0
6
8
3
7
b
f51
f5
3.
CUR
VES OF
KOBL
ITZ
SECP
256K1
Secp
256k1
re
f
ers
to
EC
DSA
par
am
et
ers
of
t
he
c
urve
use
d
i
n
Bi
tc
oin
a
nd
is
def
i
ne
d
in
St
and
a
r
ds
f
or
Eff
ic
ie
ncy
Cry
ptogra
phy
(S
E
C)
[6
]
.
Sec
p2
56k1
has
al
m
os
t
nev
e
r
bee
n
use
d
be
fore
Bi
tc
oin
becam
e
po
pu
la
r,
bu
t
it
is
gaini
ng
popula
rity
du
e
t
o
it
s
m
any
pr
ope
rtie
s.
T
his
has
bee
n
ge
ner
at
e
d
by
C
erti
com
(a
Can
adia
n
com
pan
y) a
nd
no
t
by the
NIS
T li
ke
the
Sec
p256
r1 cu
rv
e
.
3.1.
Mathem
at
ic
al
A
ppr
oach
3.1.1
The
pri
me num
ber p
The
Weierstra
ss
coe
ff
ic
ie
nts
def
i
ning
(a
,
b)
of
t
he
c
urve
a
re
(
0,
7).
SEC
2
[
6]
sta
te
s
in
Sect
ion
2.1
that
the
reco
m
m
end
ed
par
am
et
ers
associat
ed
with
a
Koblit
z
cur
ve
hav
e
be
en
sel
ect
ed
by
rep
eat
edly
sel
ect
ing
par
am
et
ers
that
adm
it
an
eff
ec
ti
vely
calc
ulable en
do
m
orph
is
m
u
ntil
a f
irst
order cu
r
ve ha
s b
ee
n fou
nd.
The
siz
e
of the
f
ie
ld
def
i
ning
p
seem
s to
be
a
256
-
bit b
oo
t
of the
sp
eci
al
form
:
p
=
2
^
256
-
s
wh
e
re s i
s sm
all w
it
h
the
for
m
s
=
2
^
32 + t,
wh
e
re t <
210
, a
nd t =
2
9+
28
+ 27+
26
+
24+
1
.
So
P
is
the
see
d
num
ber
us
e
d
in
secp
256k1,
Bi
tc
oin
us
es
it
as
the
high
li
m
it
fo
r
valid
pri
va
te
keys.
If
a
pr
ivate
key
is
rando
m
ly
ge
ner
at
e
d
la
rg
e
r
than
n,
it
is
rej
ect
ed
and
a
ne
w
key
is
reg
enera
te
d.
The
pr
obabili
ty
of
su
c
h
occ
urr
en
ce
is
l
ow
be
cause
P
is
"al
m
os
t"
as
la
rg
e
as
2256
-
1
(25
6
bits
al
l
set
to
1).
Algorith
m
of
the
rand
om
g
ener
a
tor of p
rivate
ke
y
as sho
wn in
Fig
ur
e
3.
Figure
3
.
Al
gorithm
o
f
the
r
a
ndom
g
ene
rato
r of
pri
vate
key
Evaluation Warning : The document was created with Spire.PDF for Python.
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci
IS
S
N:
25
02
-
4752
A com
pa
ris
on
betwe
en
t
he
se
cp25
6r1an
d
th
e ko
blit
z secp2
56
k
1 bit
coi
n
c
ur
ves
.
..
(
Azi
ne Houria
)
915
3.1.2
El
li
pt
ic
c
urve
e
qu
at
i
on
It
has
a
fi
rst
or
der
of
256
bits.
In
te
resti
ngly
,
this
cho
ic
e
de
viate
s
from
tho
se
m
ade
in
FIPS
18
6
-
4
in
that t
he
c
oeffic
ie
nts of th
e
c
urve a
re a
=
0 an
d b = 7.
The
el
li
ptic cu
r
ve
is i
s
om
or
ph
ic
to
a c
urve
w
it
h
a re
duced
Weierstras
s e
quat
ion o
f
t
he fo
rm
(
(
)):
2
=
3
+
b
m
od
i
f
≠ 2.
3
(10)
As
a
co
ns
ta
nt
i
s
zero,
the
te
r
m
ax
of
the
e
quat
ion
of
t
he
c
urve
is
al
ways
zero,
he
nce
the
equ
at
io
n
of
th
e
curve
beco
m
es y
2
= x
3
+ 7.
a)
The Disc
rim
inant and
J
-
in
va
r
ia
nt
Δ = 4a
3
+
27
b
2
≠ 0 a
nd j(E) =
(
-
48
a
)
3
/ Δ
=
0 becau
se a =
0
This
m
eans
th
at
secp
256k1
ha
s
j
-
in
var
ia
nt
0
so
t
his
c
urve
i
s
sai
d
t
o
be
s
uper
-
sin
gula
r
a
nd
the
refo
re
has
a
ver
y
s
pe
ci
al
structu
re
a
nd
cal
cula
ble
e
ndom
or
phism
t
hat
ca
n
be
us
e
d
t
o
acce
le
rate
i
m
ple
m
entat
io
ns
,
f
or
exam
ple
by
us
ing
the
G
LV
dec
om
po
sit
io
n
for
scal
ar
m
ul
ti
plica
ti
on
[15].
This
ide
a
was
introd
uc
ed
by
Gall
ant,
Lam
ber
t
an
d
Van
st
one
(
GL
V).Ell
ipti
c
curves
ha
ving
ef
fici
ently
-
com
pu
ta
blee
ndom
or
phism
s
shou
l
d
be
re
garde
d
as
“special
”
el
lip
ti
c
curves.
U
sing
“s
pecial
”
instances
of
cr
yptogra
ph
i
c
sc
hem
es
is
so
m
e
tim
es
done f
or
e
ff
ic
i
ency reas
ons
[
15
]
.
b)
Com
plexity
This
c
ou
l
d
le
a
d
to
a
m
or
e
se
r
iou
s
at
ta
ck
on
secp
256k1
bec
ause
a
n
at
ta
ck
e
r
c
ou
l
d
get
scal
ar
m
ulti
ples
with
one
-
po
i
nt
scal
ars
on
a
ny
curve
on
F
p
with
c
oeffic
ie
nt
a
=
0,
th
at
is,
on
the
on
e
of
t
he
t
w
ist
s
of
secp
256k1.
3.2.
Algebr
ai
c
A
p
proach
3.2.1
Au
t
om
or
phism
Ell
ipti
c
curves
with
e
ff
ect
ivel
y
cal
culable
e
ndom
orph
ism
sare
c
onsidere
d
a
s
"special
"
el
li
ptic
cu
rv
e
s,
with
a
sm
all
c
oeffici
ent.
But
eff
ic
ie
nt
en
do
m
or
ph
ism
s
acc
el
erate
scal
ar
m
ul
ti
pli
cat
ion
,
bu
t
al
so
P
ollard'
s
rho
al
gorithm
]
fo
r
cal
culat
ing
lo
ga
rithm
s
discreet.
For
this
s
pe
ci
al
cl
ass
of
cu
rv
es
,
the
acce
l
erati
on
ca
n
rea
ch
up
to
50%
com
par
ed
to
the
best
gen
e
ral
m
e
thods
of
point
m
ulti
plica
ti
on
[1
6]
.
If
J
-
in
var
ia
nt
=
0
and
K
is
a
fiel
d
of
cha
racteri
sti
c ≠ 2,
3 the
n
th
e orde
r of t
he
a
uto
m
or
phism
i
s equal t
o 6
.
3.2.2
F
ast Sc
al
ar Mu
ltipl
ic
at
ion "GL
V
dec
ompositi
on
"
Ther
e
a
re
tw
o
m
et
ho
ds
for
acce
le
rati
ng
th
e
com
pu
ta
ti
on
of
the
scal
a
r
m
ul
ti
plica
ti
on
Q
=
kP
on
el
li
ptic curv
e
s
hav
i
ng a
non
-
tr
ivial
char
act
e
r e
ff
ect
ively
calc
ulable e
ndom
or
phism
that are:
a)
The
So
li
nas
m
et
hod
[
15
]
:
Th
is
m
et
ho
d
co
ul
d
on
ly
be
ap
pl
ie
d
fo
r
a
n
el
lip
ti
c
curve
def
i
ned
on
bin
a
ry
fiel
ds
, t
he
e
ndom
or
ph
ism
co
nsi
der
e
d
to
b
e
th
eFr
ob
e
niu
s
.
b)
The
Gall
a
nt
-
L
a
m
ber
t
-
Va
ns
t
one
(
GL
V)
m
eth
od
[
15]
:
it
s
m
et
ho
d
of
el
li
ptic
curves
defi
ned
is
ap
plied
on
pr
im
ary fiel
ds
Fp
,
the
dec
ompo
sit
io
n
is t
he basis
of the c
om
pu
ta
ti
on
acce
le
rati
on
.
Anothe
r
co
ns
e
qu
e
nce
of
the
la
rg
e
r
autom
orph
ism
gr
oup
is
the
existe
nce
of
six
twist
s
(i
nclu
ding
the
curve
it
sel
f
a
nd
the
sta
ndar
d
qu
a
drat
ic
twist
).
T
he
a
uto
m
orph
ism
group
of
E
has
the
ord
er
6
a
nd
is
ge
ne
rate
d
by
the
m
ap
ψ.
The
c
urve
sec
p256
k1
:
≡
1
(m
od
6),
t
her
e
e
xists
a
6th
p
rim
itive
root
of
the unit
∈
Fp,
ζ
∈
,
and
a
corres
pondin
g autom
or
phism
of cu
rv
e
s
uch that ζ6
=
1
[15].
Ψ:
→
, (
,
)
→ (ζ
,
-
)
(11)
Fast
scal
ar
m
ul
ti
plica
ti
on
ψ
=
λ
for
an
integer
λ
6≡1
(m
od
n).
The
m
ai
n
adv
a
ntage
of
these
cu
rve
s
is t
hat dot m
ult
ipli
cat
ion
alg
ori
th
m
s can be
de
sign
e
d
t
hat do
es not
us
e
do
t
dubbin
g.
3.2.3
Sele
c
tion o
f
p
ar
ame
ter
s of the s
peci
al
Ko
bli
tz
cur
ve
The
el
li
ptic
cu
rv
e
par
am
et
ers
of
t
he
dom
ai
n
on
Fp
as
so
ci
a
te
d
with
a
Koblit
z
curve
Sec
p256k1
a
re
def
i
ned
by
the
sixfo
l
d
T
=
(
p,
a,
b,
G,
n,
h)
w
her
e
the
fi
ni
te
fiel
d
Fp
.
P
aram
et
er
of
Secp25
6k1
as
s
hown
in
Table
5
[
6]
.
The
c
urve
of S
ecp25
6k1
is
in t
he
f
or
m
:
E: y
2
= x3 +
7 m
od
p on F
p
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2502
-
4752
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci,
Vo
l.
13
, N
o.
3
,
Ma
rc
h
2019
:
910
–
918
916
Table
5
.
Param
et
er of
Sec
p256k1
[6
]
Para
m
eters
Valu
e
p
2
^
2
5
6
-
2
^
32
-
2
^
9
-
2
^
8
-
2
^
7
-
2
^
6
-
2
^
4
-
1
f
ff
ff
f
ff
ff
f
ff
ff
f
ff
ff
f
ff
f
ff
ff
f
ff
ff
f
ff
ff
f
ff
ff
f
ff
f
ff
ff
f
ff
f
e
a
0
0
0
0
0
0
0
0
00
0
0
0
0
0
0
00
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0000
0
0
0
0
0000
0
0
0
0
0
0
0
0
0
0
0
0
b
0
0
0
0
0
0
0
0
00
0
0
0
0
0
0
00
0
0
0
0
0
0
000000
0
0
0
0
0
0
0
0
0
0
0000
0
0
0
0
0000
0
0
0
0
0
0
0
0
0
0
0
7
G
0
4
7
9
b
e6
6
7
e
f
9
d
cb
b
ac
5
5
a0
6
2
9
5
ce87
0
b
0
7
0
2
9
b
f
c
d
b
2
d
ce28
d
9
5
9
f28
1
5
b
1
6
f81
7
9
8
4
8
3
ad
a7
7
2
6
a3
c4
6
5
5d
a4
f
b
fc
0
e1
1
0
8
a8
f
d
1
7
b
4
4
8
a68
5
5
4
1
9
9c4
7
d
0
8
f
f
b
1
0
d
4
b
8
n
f
ff
ff
f
ff
ff
f
ff
ff
f
ff
ff
f
ff
f
ff
ff
f
ff
e baaed
ce6 af
4
8
a0
3
b
b
f
d
2
5
e8
c d0
3
6
4
1
4
1
h
1
The param
et
ers
a,
b
a
nd
p
m
us
t correct
ly
be
c
ho
s
en
in or
de
r t
o
resist
t
he
m
a
them
a
ti
cal
att
a
cks
.
4.
COMP
AR
I
S
ON
OF
SECP
256R1
AN
D
S
ECP25
6K1
C
URVES
Af
te
r
stu
dyin
g
the
t
w
o
c
urv
es,
we
m
ention
t
he
m
ai
n
di
ff
e
ren
ces
in
T
able
5
.
The
S
afeCu
rv
es
web
sit
e
[
17
]
presents
secu
rity
assessm
ents
o
f
var
i
ou
s
.
The
com
par
ison
be
tween
secp
256r1
an
d
secp
25
6k1
as
sh
ow
n
in
Ta
ble 6
.
Table
6.
T
he
c
om
par
ison bet
ween sec
p256r
1
a
nd sec
p256
k1
cu
rve
Secp
2
5
6
r1
Secp
2
5
6
k
1
secu
rity
2
√
256
1
4
=
127
.
83
2
√
256
1
2
=
127
.
03
Au
to
m
o
rph
is
m
Or
d
er
2
6
Para
m
eters
“
a”
3
are
clai
m
s
o
f
ef
f
ectiv
en
ess
,
n
o
t saf
ety
clai
m
s
a
=
0
th
e
t
er
m
ax
o
f
th
e
eq
u
atio
n
o
f
th
e
cu
rve is alwa
y
s z
er
o
Co
st f
o
r
a co
m
b
in
e
attak[
1
7
]
2
^
12
0
,3
2
^
1
0
9
,5
Koblit
z
cu
rv
es
are
ge
ner
al
ly
known
to
be
a
few
bits
weak
e
r
tha
n
first
-
ord
er
fiel
d
cu
r
ves,
but
w
he
n
it
com
es
to
256
-
bit
curves
,
it
ha
s
li
tt
le
i
m
pac
t
.
Bi
tc
oin
works
with
a
fixe
d
curve
a
nd
ge
ne
rates
only
pri
va
te
an
d
public
keys,
ac
cordin
g
t
o
Saf
ecurve
s
[
17
]
t
he
el
li
ptic
c
urve
sec
p256
k1
can
be
c
onside
red
so
m
ewh
at
"rigid
"
wh
ic
h
m
eans
t
hat
alm
os
t
al
l
par
am
et
ers
are
transp
a
re
nt
to
the
pu
blic
and
ca
n
there
f
ore
be
sup
pose
d
not
gen
e
rated
t
o
be
weak.
T
he
r
ho
m
et
ho
d
br
ea
ks
the
ECDL
P
usi
ng
o
n
a
ve
rag
e
add
it
io
ns
o
f
a
bout
0.8
86
√l
s
o
t
he
safety
is com
par
able
for b
oth
curves.
The
c
os
t
f
or
a
com
bin
ed
at
ta
ck
is
al
m
os
t
the
sam
e
fo
r
bot
h
cu
r
ves.
Ce
rtai
nly
the
Secp
256k1
cu
rve
has
c
om
par
abl
e
secu
rity
as
th
e
cu
rv
e
but
it
has
a
ddit
ion
al
twist
s
[
16
]
,
w
hi
ch
le
ad
t
o
m
or
e
po
ssi
b
il
it
ie
s
for
a
n
at
ta
ck.
On
the
oth
er
hand,
a
n
el
li
ptic
cur
ve
with
j
-
i
nv
a
riant
diff
e
re
nt
from
0
and
1728
as
the
case
of
th
e
curve
sec
p256
r1
only
has
a
gro
up
a
uto
m
orp
hism
of
order
2,
so
t
hat
the
acce
le
rati
on
of
the
Po
ll
ard
r
ho
al
gorithm
[
16
]
is a co
ns
ta
nt
fa
ct
or
up to
√3
on s
uc
h
a c
urve.
Secp
256k1
is
of
te
n
m
or
e
tha
n
30%
faster
t
han
the
ot
her
c
urves
i
f
the
im
plem
entat
ion
is
suffici
e
ntly
op
ti
m
iz
ed
and
the
crit
erion
of
s
peed
is
a
ver
y
i
m
po
rta
nt
crit
erion
f
or
the
Bi
tc
oin
s
be
cause
a
paym
e
nt
with
Bi
tc
oin
is
al
m
os
t
insta
ntane
ous.
H
oweve
r,
s
ecp25
6r1
us
es
the
ve
ry
s
uspic
iou
s
seed
"c4
9d3608
86
e
704936a
6
678e
1139d2
6b7819f
7e
90
"
which is
stra
ng
el
y sim
il
ar to
the
b
ac
kdoor
in D
ual_EC
_D
RB
G
[
18]
.
The
el
li
ptic
cu
rv
e
Bi
tc
oi
n
has
the
lo
west
|D|
of
al
l
kn
own
st
and
a
r
dized
el
li
ptic
cu
r
ves
,
an
d
the
refo
r
e
is p
otentia
ll
y less s
ec
ur
e.
5.
THE
MI
NI
N
G
OF
BITCO
IN
The
m
ino
rs
of
the
Bi
tc
oin
prot
oco
l
us
e
s
pe
ci
al
so
ftwa
re
and
ha
rdwa
re
to
so
l
ve
the
pro
blem
of
discrete
lo
gar
it
hm
or
has
h
f
unct
ions
(
Hash2
56).
Has
h
rate
s
are
an
im
po
r
ta
nt
factor
t
hat
m
in
ers
m
us
t
us
e
to
determ
ine
profi
ts.
Seve
ral
pa
r
a
m
et
ers
are
ta
ken
into
co
ns
i
der
at
io
n
durin
g
the
m
ining
,
su
c
h
as
t
he
dif
ficult
y,
the
rate
of
has
hing,
t
he
co
st
of
el
ect
rici
ty
and
of
c
ourse,
without
f
orgett
ing
t
he
com
plexity
,
the
slo
w
ne
ss
an
d
the
cost
of
th
e
eq
ui
pm
ent,
t
he
re
new
al
of
the
equ
i
pm
ent
wh
ic
h
qu
ic
kly
beco
m
es
obso
le
te
and
t
he
heat
release
d by th
e
Bi
tc
oin
s m
ining eq
uip
m
ent tends t
o ea
sil
y ov
e
r
heat,
wh
ic
h
ca
n
inte
rrup
t
it
s o
pe
rati
on.
To
ove
rco
m
e
a
ll
these
par
am
e
te
rs,
m
iners
wo
r
k
in
pools
to
reduce
the
co
s
t
of
m
ining
by
poolin
g
th
e
com
pu
ti
ng
po
wer o
f
thei
r
c
om
pu
te
rs
an
d
in
crease thei
r blo
ck resol
ution c
apacit
y.
Mi
nin
g
wit
h
a
pr
oc
esso
r
(
CPU)
was
the
on
ly
way
to
m
ine
bitcoins.
Gr
a
phic
s
card
s
(
GPUs
)
even
t
ually
rep
l
aced
CP
Us
bec
ause o
f
t
heir
na
ture,
which
al
lo
we
d
a
n
inc
re
ase
betwee
n
50
x
to 100x
[18] in
the
com
pu
ti
ng
po
wer
i
n
us
in
g
le
ss
el
ect
rici
ty
per
m
egah
ash
c
om
par
ed
t
o
a
CPU.
The
m
in
ing
w
or
l
d
has
evo
l
ve
d
Evaluation Warning : The document was created with Spire.PDF for Python.
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci
IS
S
N:
25
02
-
4752
A com
pa
ris
on
betwe
en
t
he
se
cp25
6r1an
d
th
e ko
blit
z secp2
56
k
1 bit
coi
n
c
ur
ves
.
..
(
Azi
ne Houria
)
917
into
the
us
e
of
Fiel
d
Pro
gr
a
m
m
able
Gate
Arrays
(FPG
A
s)
as
a
m
ining
platfo
rm
.
Althou
gh
FP
GAs
did
not
offer
a
50x
to
100x
incr
ease
in
com
pu
ti
ng
s
peed
as
t
he
tra
ns
it
ion
from
C
PU
to
GPU
[
19]
,
they
offe
re
d
bette
r
energy
eff
ic
ie
ncy.
The
w
or
l
d
of
bitcoi
n
m
ining
is
now
m
igrati
ng
to
the
A
pp
li
cat
io
n
Spec
ific
In
t
egr
at
e
d
Ci
rcu
it
(A
S
IC)
.
The
ri
gid
it
y
of
an
AS
IC
al
lo
ws
it
to
offer
a
n
increa
se
in
c
om
pu
ti
ng
pow
er
of
100x
[
19]
wh
il
e
reducin
g p
ow
e
r
c
on
s
um
ption
com
par
ed
t
o
al
l othe
r
te
ch
nolog
ie
s
.
We
fin
d
that
t
he
m
ining
po
wer
is
hi
gh
a
nd
bec
om
es
hig
he
r,
tha
nk
s
t
o
the
de
vel
opm
ent
of
ne
w
m
ining
equipm
ent. Th
e
requir
ed
num
ber
o
f
z
e
ro
s at the b
e
gi
nn
i
ng
of
a
has
h
is change
d
twic
e a w
eek to adjust
the d
if
ficult
y o
f
creati
ng a
b
l
oc
k
a
nd m
or
e zero
s
m
eans
m
ore dif
ficult
y. T
he
Bi
tc
oin
pr
otoc
ol adds t
hese
zero
s
to
m
a
intai
n
the
sp
eed
at
wh
ic
h
bl
ock
s
a
re
a
dded
t
o
a
ne
w
bl
ock
e
ver
y
10
m
inu
te
s.
The
i
dea
is
to
com
pen
sat
e
for
t
he
m
ining
equ
i
pm
ent
bec
om
ing
m
or
e
an
d
m
or
e
powe
rful.
When
the
ha
sh
is
ha
r
der
,
m
or
e
cal
culat
ion
s
a
re
need
e
d
t
o
crea
te
a
blo
c
k
a
nd
thu
s
m
or
e
effor
t
to
gai
n
ne
w
bitcoins,
w
hich
a
re
the
n
add
e
d
t
o
the
t
raffic
.
Transi
ti
on
of
Mi
nin
g
Tec
hn
ology
as
show
n
in
Fig
ure
4
and
C
om
par
ison
of
c
om
pu
ti
ng
powe
r
as
s
how
n
in
Figure
5.
Figure
4.
T
ra
nsi
ti
on
of Mini
ng Tech
nolo
gy
Figure
5.
C
om
par
iso
n of com
pu
ti
ng po
wer
6.
CONCL
US
I
O
N
Con
sta
nt
tim
e
cal
culat
ion
s
he
lp
pr
e
ve
nt
inf
orm
ation
le
aks
on
t
he
secret
ke
y
by
m
easur
ing
how
lo
ng
it
ta
kes
to
create
the
sign
a
ture.
As
a
res
ult,
besides
si
m
pl
ic
it
y
and
eff
ic
ie
ncy,
Se
cp25
6k1
co
ul
d
le
ak
inf
or
m
at
ion
for si
de
c
ha
nn
el
a
tt
acks b
eca
us
e
the tim
e for
s
om
e cal
culat
ions i
s not c
onsta
nt
.
W
it
h
the
ne
w
boos
t
that
Bi
tc
oin
crypt
ocurr
e
ncy
is
hav
i
ng,
the
resea
r
ch
com
m
un
it
y
will
turn
it
s
at
te
ntion
t
o
tw
o
as
pects,
t
he
crypto
gr
a
phy
beh
i
nd
the
Bi
coin
a
nd
t
he
possible
at
ta
cks.The
m
ajor
pro
blem
is
the
disam
big
uity
of
the
po
ssi
ble
backd
oor,
excep
t
f
or
m
ath
em
atical
ind
ic
at
ion
,
an
d
the
var
io
us
ch
oice
s
in
the
par
am
et
ers
are
no
t
cl
ear
or
are
no
t
com
plete
ly
sp
eci
fied.
SafeCu
rv
e
s
argues
that
at
ta
cker
s
c
ou
l
d
hav
e
m
anipu
la
te
d
t
he
ch
oice
of
sta
nd
a
r
d
cu
rv
e
s to
be v
uln
e
rab
l
e to a
secret at
ta
ck
that ap
plie
s to
a sm
all f
racti
on
of
curves.
T
he
m
at
hem
atics
beh
ind
Bi
tc
oin
an
d
ECC
are
bas
ed
on
the
so
lu
ti
on
of
ver
y
di
ff
ic
ult
pro
ble
m
s
of
discrete
lo
gar
it
hm
ic
pr
ob
le
m
s
,
that
is
to
say
,
it
is
a
co
m
pu
ta
ti
on
al
ly
com
p
le
x
pro
blem
.
W
it
h
the
intr
oducti
on
and
ad
va
nce
m
ent
of
grap
hics
pr
ocessin
g
un
it
s
a
nd
cl
oud
c
om
pu
ta
ti
on
s,
N
IS
T
sta
nd
a
r
ds
a
nd
oth
er
orga
nizat
ion
s
nee
d
to
b
e
up
dat
ed.
The
ne
w
era
of
com
pu
ti
ng
a
nd
the
s
pee
d
of
ne
w
GPUs
that
can
af
fect
the
cryptoa
nal
ysi
s
m
ark
et
m
igh
t be a
se
riou
s
pr
ob
le
m
f
or Bi
tc
oin
ci
phe
rin
g,
es
pecial
ly
if it re
pr
ese
nts
the
new
possi
blecu
rr
e
ncy.
REFERE
NCE
S
[
1
]
htt
ps://
b
it
co
int
a
l
k.
org/i
nd
ex.
php
,
18
sept
embre
2
013
[2]
SECG “
the
Stan
dar
ds for Effi
c
ient
Cr
y
ptogr
aph
y
Group”, 1998.
[3]
Draft
NIS
T
Spe
c
ia
l
Publicati
on
8
00
-
57,
Re
comm
enda
t
ions f
or
Ke
y
-
Man
age
m
ent, 2012.
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2502
-
4752
Ind
on
esi
a
n
J
E
le
c Eng &
Co
m
p
Sci,
Vo
l.
13
, N
o.
3
,
Ma
rc
h
2019
:
910
–
918
91
8
[4]
htt
ps://
ww
w.cert
ic
om
.
com/
[5]
NIS
T,
FIP
S Public
a
ti
on
186
-
4
,
Di
git
al Signa
ture Sta
ndar
d
(DS
S),
2
000
and cha
ng
e noti
c
e
1
,
2001
.
[6]
SEC2”Sta
ndar
ds
for
Eff
icient
C
r
y
ptogr
aph
y
Gr
oup”:
Re
comm
ende
d
El
l
ipt
i
c
cu
rve
Dom
ai
n
Para
m
et
ers.
Versio
n
1.
0,
2000.
[7]
Marie
-
Angel
a
C
ORN
EL
IE
«
Impl
antati
ons
et
pr
ote
c
t
ions
de
m
écani
sm
es
cr
y
ptog
rap
hique
s
logici
el
s
et
m
at
ér
ie
ls
»
,
Doctor
Of
The Com
m
unit
y
Unive
rsit
y
Grenobl
e
A
lps,
2016.
[8]
Youns
ung
Choi
“
Cry
p
ta
n
aly
sis
on
Privacy
-
a
ware
Two
-
fa
ct
o
r
Authent
i
ca
t
io
n
Protocol
for
W
ire
le
ss
Sensor
Networks “TELK
OM
NI
KA
”
Vol.
8
,
No
.
1
,
Febr
uar
y
2018,
pp
.
6
05
-
610.
[9]
Jea
n
-
Pierre
Flor
i
,
Jérôm
e
Plût,
J
ea
n
-
Ren
é
Rei
nh
ard
,
Mart
in
Eker
å
«
Diver
sité
et
tra
nspare
n
ce
:
c
hoix
des
cour
be
s
el
li
p
ti
ques
»
NSSI/SD
E/
ST/L
CR,
2015
.
[10]
IEE
E
1363
-
200
0
“
IEE
E
Standa
rd
Speci
fi
catio
ns
for
Public
-
Ke
y
Cr
y
p
togra
ph
y
”
Spon
sor
Micropr
oce
ss
or
an
d
Microc
om
pute
r
Standa
rds
Comm
it
te
e
of
the
I
EE
E
Com
pute
r
Socie
t
y
Appro
ved
30
Janua
r
y
2000
IEE
E
-
SA
Standa
rds Boa
rd
.
[11]
htt
ps://
saf
ec
urv
e
s.c
r.y
p
.
to/
r
efs.
ht
m
l
#2005/bra
inp
ool
.
[12]
Rogel
L.
Qui
lala
,
Ariel
M.
Sis
o
n,
Ruji
P.
Med
ina
“
Modifie
d
SH
A
-
1
A
lgori
thm”
TE
LKOM
N
IKA
(Indone
sian
Journal
of El
ec
tr
ic
a
l
Eng
ineeri
ng
and
Com
puter S
ci
en
ce
)
Vol.
11,
No.,
pp
.
1027
-
10
34,
2018
.
[13]
AN
SI “
A
MERICAN
NA
TION
AL
STAN
DA
R
D”
X9.62
-
1998.
[14]
R.
P.
Gall
an
t,
R.
J.
La
m
ber
t
,
and
S.
A.
Vanstone.
”
Fast
er
poi
nt
m
ult
ipl
icat
ion
on
el
li
pt
ic
cur
v
es
with
eff
icient
endomorphism
s
”
In
J
.
Kil
ia
n
,
ed
it
or, CRYP
TO,
volume
2139
of
LNCS,
page
s
19
0
-
200.
Springe
r,
2001.
[15]
htt
p://
safe
cur
ves
.
cr.y
p
.
to
/i
ndex
.
h
tml.
[16]
htt
ps://
sl
ashdot.
o
rg/stor
y
/13/
09/1
1/1224252/
ar
e
-
t
he
-
nist
-
stand
ard
-
el
li
p
ti
c
-
cur
ves
-
b
ac
kDoo
red
.
[17]
htt
ps://
spe
ct
rum
.
ie
e
e.
org/
ene
rg
y
/
poli
c
y
/
th
e
-
ridic
ulous
-
amount
-
of
-
ene
rg
y
-
it
-
ta
k
es
-
to
-
run
-
bitcoin
.
Evaluation Warning : The document was created with Spire.PDF for Python.