Protokol digitálního podpisu s využitím eliptických křivek (The Elliptic Curve Digital Signature Algorithm, ECDSA) je varianta DSA protokolu, která využívá eliptických křivek, používá se k digitálním podpisům.
editovat
Pokud chce Alice poslat zprávu m Bobovi, musí se nejprve domluvit na parametrech (p,a,b,G,n,h), kde p je prvočíslo , kterým definujeme těleso , konstanty a, b z rovnice eliptické křivky , bod G na eliptické křivce , jeho řád n a kofaktor h, který udává podíl počtu prvků grupy bodů na eliptické křivce a řádu bodu G. Alice také musí mít své klíče vhodné pro kryptografii eliptických křivek skládající se ze soukromého klíče dA , veřejného klíče QA , kde dA je náhodně vybrané celé kladné číslo z intervalu [1;n-1],
Q
A
=
d
A
G
{\displaystyle Q_{A}=d_{A}G}
sčítání bodů na eliptické křivce ).
Alice náhodně zvolí k,
k
∈
[
1
;
n
−
1
]
{\displaystyle k\in [1;n-1]}
Následně spočítá
r
≡
x
1
mod
n
{\displaystyle r\equiv x_{1}\mod n}
k
G
=
[
x
1
;
y
1
]
{\displaystyle kG=[x_{1};y_{1}]}
r
=
0
{\displaystyle r=0}
Zjistí hash zprávy h(m), spočítá
s
≡
k
−
1
(
h
(
m
)
+
r
d
A
)
mod
n
{\displaystyle s\equiv k^{-1}(h(m)+rd_{A})\mod n}
Čísla r, s tvoří podpis . Bob musí zjistit veřejný klíč Alice QA . Pokud má pochybnosti ohledně zdroje, musí si ověřit tento klíč.
Ověří, že
Q
A
≠
O
{\displaystyle Q_{A}\neq O}
nekonečnu (viz eliptická křivka ).
Ověří, že bod QA leží na eliptické křivce .
Ověří, že existuje číslo n takové, že
n
Q
A
=
O
{\displaystyle nQ_{A}=O}
Pokud vše platí, může Bob učinit následující kroky:
Ověří, že
r
,
s
∈
[
1
;
n
−
1
]
{\displaystyle r,s\in [1;n-1]}
Bob zjistí hash zprávy h(m).
Spočítá
w
≡
s
−
1
mod
n
{\displaystyle w\equiv s^{-1}\mod n}
Spočítá u1 , u2 , kde
u
1
≡
w
h
(
m
)
mod
n
{\displaystyle u_{1}\equiv wh(m)\mod n}
u
2
≡
r
w
mod
n
{\displaystyle u_{2}\equiv rw\mod n}
Následně spočítá souřadnice
[
x
1
,
y
1
]
=
u
1
G
+
u
2
Q
A
mod
p
{\displaystyle [x_{1},y_{1}]=u_{1}G+u_{2}Q_{A}\mod p}
Podpis je platný, když
r
=
x
1
{\displaystyle r=x_{1}}
Alice zvolí prvočíslo
p
=
23
{\displaystyle p=23}
a
=
1
,
b
=
1
{\displaystyle a=1,b=1}
n
=
7
{\displaystyle n=7}
4
a
3
+
27
b
2
≠
0
{\displaystyle 4a^{3}+27b^{2}\neq 0}
eliptickou křivku .
Zvolí
d
A
=
2
{\displaystyle d_{A}=2}
A [5;19], zvolí číslo
k
=
4
{\displaystyle k=4}
Následně nalezne bod kG[17;3] (
k
G
=
4
G
=
2
(
2
G
)
{\displaystyle kG=4G=2(2G)}
zdvojnásobí tedy bod G, nalezne pomyslný bod R, který zdvojnásobí a získá hledaný bod), spočítá
r
≡
x
1
mod
n
≡
17
mod
7
≡
3
mod
7
{\displaystyle r\equiv x_{1}\mod n\equiv 17\mod 7\equiv 3\mod 7}
k
≠
0
{\displaystyle k\neq 0}
Zjistí hash zprávy h(m),
h
(
m
)
=
5
{\displaystyle h(m)=5}
hash byl náhodně zvolen pro tento příklad), spočítá
s
≡
k
−
1
(
h
(
m
)
+
r
d
A
)
mod
n
≡
4
−
1
(
5
+
3
⋅
2
)
mod
7
≡
2
(
5
+
6
)
mod
7
≡
1
mod
7
{\displaystyle s\equiv k^{-1}(h(m)+rd_{A})\mod n\equiv 4^{-1}(5+3\cdot 2)\mod 7\equiv 2(5+6)\mod 7\equiv 1\mod 7}
Čísla
r
≡
3
mod
7
{\displaystyle r\equiv 3\mod 7}
s
≡
1
mod
7
{\displaystyle s\equiv 1\mod 7}
podpis . Bob ověřil klíč QA .
Nyní ověří, že
r
,
s
∈
[
1
;
n
−
1
]
{\displaystyle r,s\in [1;n-1]}
1
,
3
∈
[
1
;
6
]
{\displaystyle 1,3\in [1;6]}
Bob zjistí hash zprávy h(m),
h
(
m
)
=
5
{\displaystyle h(m)=5}
Spočítá
w
≡
s
−
1
mod
n
≡
1
−
1
mod
7
≡
1
mod
7
{\displaystyle w\equiv s^{-1}\mod n\equiv 1^{-1}\mod 7\equiv 1\mod 7}
Spočítá u1 , u2 , kde
u
1
≡
w
h
(
m
)
mod
n
≡
1
⋅
5
mod
7
≡
5
mod
7
{\displaystyle u_{1}\equiv wh(m)\mod n\equiv 1\cdot 5\mod 7\equiv 5\mod 7}
u
2
≡
r
w
mod
n
≡
3
⋅
1
mod
7
≡
3
mod
7
{\displaystyle u_{2}\equiv rw\mod n\equiv 3\cdot 1\mod 7\equiv 3\mod 7}
Následně spočítá souřadnice
[
x
1
,
y
1
]
=
u
1
G
+
u
2
Q
A
=
5
[
13
;
16
]
+
3
[
5
;
19
]
=
[
5
;
4
]
+
[
13
;
7
]
=
[
17
;
3
]
mod
23
{\displaystyle [x_{1},y_{1}]=u_{1}G+u_{2}Q_{A}=5[13;16]+3[5;19]=[5;4]+[13;7]=[17;3]\mod 23}
Podpis je platný, když
r
mod
7
≡
x
1
mod
7
{\displaystyle r\mod 7\equiv x_{1}\mod 7}
3
mod
7
≡
17
mod
7
{\displaystyle 3\mod 7\equiv 17\mod 7}
3
mod
7
≡
3
mod
7
{\displaystyle 3\mod 7\equiv 3\mod 7}
s
≡
k
−
1
(
h
(
m
)
+
r
d
A
)
mod
n
{\displaystyle s\equiv k^{-1}(h(m)+rd_{A})\mod n}
h
(
m
)
≡
k
s
−
r
d
A
mod
n
{\displaystyle h(m)\equiv ks-rd_{A}\mod n}
vynásobíme-li obě strany kongruence w, získáme
w
h
(
m
)
≡
w
k
s
−
w
r
d
A
mod
n
{\displaystyle wh(m)\equiv wks-wrd_{A}\mod n}
u
1
≡
w
h
(
m
)
mod
n
{\displaystyle u_{1}\equiv wh(m)\mod n}
u
2
≡
r
w
mod
n
{\displaystyle u_{2}\equiv rw\mod n}
u
1
≡
w
k
s
−
u
2
d
A
mod
n
{\displaystyle u_{1}\equiv wks-u_{2}d_{A}\mod n}
w
≡
s
−
1
mod
n
{\displaystyle w\equiv s^{-1}\mod n}
w
s
≡
1
mod
n
{\displaystyle ws\equiv 1\mod n}
u
1
≡
k
−
u
2
d
A
mod
n
{\displaystyle u_{1}\equiv k-u_{2}d_{A}\mod n}
celou kongruenci vynásobíme bodem G, získáme (po drobné ekvivalentní úpravě)
(
k
G
mod
p
)
mod
n
≡
(
u
1
G
+
u
2
d
A
G
mod
p
)
mod
n
{\displaystyle (kG\mod p)\mod n\equiv (u{1}G+u_{2}d_{A}G\mod p)\mod n}
k
G
mod
n
≡
u
1
G
+
u
2
Q
A
mod
n
{\displaystyle kG\mod n\equiv u_{1}G+u_{2}Q_{A}\mod n}
r
≡
x
1
mod
n
{\displaystyle r\equiv x_{1}\mod n}
![{\displaystyle k\in [1;n-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90d58aaa5a29aae17651c8049f013c1539464764)
![{\displaystyle kG=[x_{1};y_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e517ca4a616f4075376e8264cc7fbbf8608ebf3)
![{\displaystyle r,s\in [1;n-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cf95076dad687d19116429d85a35b0b0f712a10)
![{\displaystyle [x_{1},y_{1}]=u_{1}G+u_{2}Q_{A}\mod p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24dea424917063d6d9a5b364bf36224b30b24961)
![{\displaystyle 1,3\in [1;6]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b73de0e203291454daf83642ee51f83a1ed1cd6a)
![{\displaystyle [x_{1},y_{1}]=u_{1}G+u_{2}Q_{A}=5[13;16]+3[5;19]=[5;4]+[13;7]=[17;3]\mod 23}](https://wikimedia.org/api/rest_v1/media/math/render/svg/409a7f88f94260417a3111128967598255b3dcfc)
