1

TRƯỜNG………………………
KHOA……………………………
LUẬN VĂN TỐT NGHIỆP

NGHIÊN CỨU, TÌM HIỂU VÀ TRÌNH BÀY VỀ CHỮ KÝ SỐ TRÊN
ĐƯỜNG CONG Elliptic, ỨNG DỤNG CỦA ĐƯỜNG CONG Elliptic TRONG
HỆ THỐNG BỎ PHIẾU ĐIỆN TỬ VÀ HỆ THỐNG TIỀN ĐIỆN TỬ.
2

Nguyễn Minh Hải
3 TÓM TẮT NỘI DUNG KHÓA LUẬN

Khóa luận là sự nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường
cong Elliptic, ứng dụng của đường cong Elliptic trong Hệ thống bỏ phiếu điện tử và
Hệ thống tiền điện tử. Khóa luận được trình bày thành bốn chương với nội dung
như sau:
Chương 1 : Tóm tắt các khái niệm cơ bản trong số học và trong đại số học.
Chương 2 : Trình bày về khái niệm đường cong Elliptic, các dạng đường cong
và các phép toán trên đường cong Elliptic.
Chương 3 : Trình bày một số chữ ký số trên đường cong Elliptic và phương
pháp tấn công hệ mã hóa đường cong Elliptic.
Chương 4 : Trình bày ứng dụng của đường cong Elliptic trong Hệ thống bỏ
phiếu điện tử và Hệ thống tiền điện tử.
4 CÁC KÝ HIỆU VIẾT TẮT

Tom Người gửi tin hoặc người thực hiện việc ký
BĐK Ban đăng ký
BKP Ban kiểm phiếu
Jerry Người nhận tin hoặc người yêu cầu ký
EC Đường cong Elliptic (Elliptic Curve)
ECC Mã hóa đường cong Elliptic (Elliptic Curve Cryptosystem)
ECDSA Thuật toán ký trên EC
EDLP Bài toán Logarith rời rạc trên EC

F
q
Trường hữu hạn với q phần tử
G Điểm cơ sở của E
K Không gian các khóa
O Phần tử trung hòa của E
sig
K
Thuật toán ký số
ver
K
Thuật toán kiểm tra chữ ký
Z
p
Vành các số nguyên dương p
φ(n) Hàm phi Euler các số nguyên trong Z
n
nguyên tố cùng nhau với n.

6

DANH MỤC CÁC HÌNH VẼ TRONG KHÓA LUẬN Hình 1: Một ví dụ về đường cong Elliptic Error! Bookmark not defined.
Hình 2: Điểm ở vô cực Error! Bookmark not defined.
Hình 3: Phép cộng trên đường cong elliptic Error! Bookmark not defined.
Hình 4: Phép nhân đôi trên đường cong elliptic Error! Bookmark not defined.
30
2.3.3. Các phép toán trên đường cong elliptic trong hệ tọa độ Affine 30
2.3.4. Các phép toán trên đường cong elliptic trong hệ tọa độ chiếu 32
2.3.5. Chuyển đổi giữa hệ tọa độ Affine và hệ tọa độ chiếu 33
2.3.6. Các phép toán đường cong trong hệ tọa độ chiếu 33
2.3.6. Phép nhân đường cong 34
2.4 BÀI TOÁN LOGARIT RỜI RẠC TRÊN ĐƯỜNG CONG ELLIPTIC 36
Chương 3. CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTC 37
3.1. CHỮ KÝ SỐ 37
3.1.1. Khái niệm chữ ký số 37
3.1.2. Sơ đồ chữ ký số 38
3.2. MỘT SỐ SƠ ĐỒ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC 41
3.2.1. Sơ đồ chữ ký ECDSA 41
3.2.2. Sơ đồ chữ ký Nyberg- Rueppel 43
3.2.3. Sơ đồ chữ ký mù Harn trên EC 44
8

3.2.4. Sơ đồ đa chữ ký mù của Harn trên EC 47
3.3. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG HỆ ECC 49
3.3.1. Phương pháp tấn công “baby - step giant - step” 49
3.3.2. Phương pháp tấn công MOV 50
Chương 4 . ỨNG DỤNG CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC 53
4.1.ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ 54
4.1.1. Quy trình bỏ phiếu điện tử 54
4.1.2. Sử dụng ECC trong bỏ phiếu điện tử 55
4.2. ỨNG DỤNG TRONG HỆ THỐNG TIỀN ĐIỆN TỬ 57
4.2.1. Tạo tiền ecash 57
4.2.2 Tiêu tiền ecash 58
4.2.3 Đổi tiền 58
4.2.4 Kết thúc giao dịch 58

Tom)và người nhận (Jerry) cùng thỏa thuận một khóa bí mật, bằng cách gặp mặt
nhau trực tiếp hoặc nhờ một trung tâm tin cậy phân phối khóa. Nếu Tom muốn gửi
cho Jerry một thông điệp
Mm

, cô ấy sẽ gửi bản mã )(mec
k
 cho Jerry. Jerry sẽ
khôi phục bản rõ m bằng việc dùng hàm giải mã
k
d . Hệ mật mã khóa bí mật phải
đảm bảo rằng các hàm
k
e và
k
d phải dễ áp dụng nhưng vẫn an toàn trước kẻ tấn
công, khi có bản mã c vẫn khó tính được m (hoặc khóa k). Dù hệ mật mã khóa bí
mật vẫn đang được dùng trong nhiều ứng dụng, nhưng vẫn còn một số nhược điểm
như vấn đề phân phối khóa, vấn đề quản lý khóa và nó không hỗ trợ việc tạo chữ ký
điện tử.
Ý tưởng chính của các thuật toán khóa công khai là sử dụng 2 khóa khác nhau
cho 2 quá trình mã hóa và giải mã. Ý tưởng này được phát minh bởi Whitfield
Diffie và Martin Hellman (1976), độc lập với Ralph Merkle (1978). Từ đó, nhiều hệ
mật mã khóa công khai được đưa ra, nhưng hầu hết chúng đều hoặc không an toàn
hoặc không khả thi. Các thuật toán khóa công khai đều chậm hơn rất nhiều so với
các thuật toán khóa bí mật.
Thuật toán RSA chậm hơn 1000 lần so với các thuật toán khóa bí mật phổ
biến như DES khi triển khai trong các thiết bị phần cứng; và chậm hơn 100 lần
trong các phần mềm mã hóa khi mã hóa cùng một khối lượng dữ liệu như nhau. Tuy
nhiên, hệ mật mã khóa công khai có một ưu điểm nổi trội là cho phép tạo chữ ký


Chương 1. CÁC KHÁI NIỆM CƠ BẢN
1.1. KHÁI NIỆM TRONG SỐ HỌC
1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất
a. Khái niệm
Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, thì
ta nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a và a là bội của b.
Số nguyên d được gọi là ước chung của các số nguyên a
1
, a
2
, …, a
n
, nếu nó
là ước của tất cả các số đó.
Số nguyên m được gọi là bội chung của các số nguyên a
1
, a
2
, …, a
n
, nếu nó
là bội của tất cả các số đó.
Một ước chung d >0 của các số nguyên a
1
, a
2
, …, a
n
, trong đó mọi ước

, …, a
n
) = 1,thì a
1
, a
2
, …, a
n
được gọi là nguyên tố cùng nhau.
Một bội chung m >0 của các số nguyên a
1
, a
2
, …, a
n
, trong đó mọi bội
chung của a
1
, a
2
, …, a
n
đều là bội của m, thì m được goi là bội chung nhỏ nhất
của a
1
, a
2
, …, a
n
. Ký hiệu m = lcm(a

sao cho: d = a
1
x
1
+a
2
x
2
+…+a
n
x
n
a1,a2, an nguyên tố cùng nhautồn tại x1,x2, xn sao cho: 1 = a
1
x
1
+a
2
x
2
+…+a
n
x
n

2. d = gcd(a
1
, a
2
, …, a

2
, …, a
n
) (với m ≠ 0).
5. Nếu gcd(a, b) =1 thì lcm(a, b) = a * b
6. Nếu b>0, a = bq+r thì gcd(a,b) = gcd(b, r).
12

1.1.2. Quan hệ đồng dư
a. Khái niệm
Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với
nhau theo modulo m, nếu chia a và b cho m, ta nhận được cùng một số dư.
Ký hiệu: a ≡ b (mod m).
b. Ví dụ
17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, được cùng số dư là 2.
c. Tính chất
1. Quan hệ “đồng dư” là quan hệ tương đương trong Z:
Với mọi số nguyên dương m ta có:
a ≡ a (mod m) với mọi a

Z; (tính chất phản xạ).
a ≡ b (mod m) thì b ≡ a (mod m); (tính chất đối xứng).
a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m); (tính chất bắc cầu).
2. Tổng hay hiệu các “đồng dư ”:
(a+b) (mod n)

[(a mod n) + (b mod n)] (mod n)
(a- b) (mod n)

[(a mod n) - (b mod n)] (mod n)

i
(mod m) với i=1 k, thì ta có:
1 1
(mod )
k k
i i
i i
a b m
 

 

13

1.1.3. Số nguyên tố
a. Khái niệm
Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó.
b. Ví dụ
10 số nguyên tố lớn đã được tìm thấy :
rank Prime Digits Who when reference
1
2
32582657
-1
9808358 G9 2006 Mersenne 44??
2
2
30402457
-1
9152052 G9 2005 Mersenne 43??

9
28433·2
7830457
+1
2357207 SB7 2004
10
33661·2
7031232
+1
2116617 SB11 2007

c. Định lý
1. Định lý: về số nguyên dương > 1.
Mọi số nguyên dương n > 1 đều có thể biểu diễn được duy nhất dưới dạng:
1 2 k
n n n
1 2 k
.
=P P P
n , trong đó:
k, n
i
( i =1,2, ,k) là các số tự nhiên, P
i
là các số nguyên tố, từng đôi một khác nhau.
2. Định lý Mersenne.
Cho p = 2
k
-1, nếu p là số nguyên tố, thì k phải là số nguyên tố.
14

7

*
={1, 2, 3, 4, 5, 6, 7}. Khi đó /Z/ =

(p) = p-1 =8-1 = 7.
Định lý hàm Euler.
Nếu n là tích của hai số nguyên tố n = p.q, thì

(n) =

(p).

(q) = (p-1).(q-1).
15

1.2. KHÁI NIỆM TRONG ĐẠI SỐ
1.2.1. Nhóm
a. Khái niệm
Nhóm là một bộ (G, *), trong đó G  , * là phép toán hai ngôi trên G
thoả mãn ba tính chất sau:
+ Phép toán có tính kết hợp: (x*y)* z = x*(y*z) với mọi x, y, z  G.
+ Có phần tử phần tử trung lập e  G: x*e = e*x = x với mọi x  G.
+ Với mọi x G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e.
Cấp của nhóm G được hiểu là số phần tử của nhóm, ký hiệu là
G
.
Cấp của nhóm có thể là  nếu G có vô hạn phần tử.
Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán.
Tính chất: Nếu a * b = a * c, thì b = c.

phần tử khác nhau: e, g, g
2
, g
3
, . . . , g
n - 1
. Khi đó G được gọi là nhóm Cyclic
hữu hạn cấp n.
Nếu không tồn tại số tự nhiên n để g
n
= e, thì G có cấp .
c. Nhóm (Z
n
*
, phép nhân mod n)
* Kí hiệu Z
n
= 0, 1, 2, . , n-1 là tập các số nguyên không âm < n.
Z
n
và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, pt trung lập e = 0.
(Z
n
, + ) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n.
* Kí hiệu Z
n
*
= x  Z
n
, x là nguyên tố cùng nhau với n. Tức là x phải  0.

p
Z là nhóm Cyclic.
Nếu b


*
n
Z thì b

(n)

1 (mod n). Nếu p là số nguyên tố thì

(p) = p-1.
Do đó với b 
*
p
Z (tức b nguyên tố với p), thì b

(p)

1 (mod n), hay b
p -1

1(mod n).
d. Phần tử nghịch đảo đối với phép nhân
* Định nghĩa
Cho a  Z
n
, nếu tồn tại b  Z

* Hệ quả: Mọi phần tử trong Z
n
*
đều có phần tử nghịch đảo.
1.2.2. Vành
Vành là một tập R với 2 toán tử + và . với các điều kiện sau:
,R là một nhóm Abel
a . (b . c) = (a . b) . c với mọi a, b, c

R.
a . (b + c) = a . b + a . c và (a + b) . c = a . c + b . c với mọi a, b, c

R.
Vành tuyến tính
F là một vành. Một đa thức bậc n trên F có dạng:



n
i
n
n
i
i
xaxaaxaxf
0
10
)(
với n là số nguyên dương, các hệ số a
i




n
i
i
ii
xbaxgxf
0
)()()(
Cho 2 đa thức



n
i
i
i
xaxf
0
)( và



m
j
j
j
xbxg
0


F[x] thỏa mãn f(x) = g(x) . q(x) + r(x) với bậc của r(x) nhỏ hơn bậc của g(x).
Nếu r(x) là đa thức 0 thì g(x) được gọi là ước của f(x). Đa thức bất định f(x)
trong F[x] là tối giản nếu nó không có ước có bậc thấp hơn f(x) trong F[x]. a

F là
nghiệm của f(x)

F[x] nếu f(a) = 0.
Hệ quả
Một phần tử a

F là nghiệm của đa thức f(x)

F[x] khi và chỉ khi x – a là ước
của f(x) trong F[x].
18

Chứng minh
Vì a là nghiệm nên f(a) = 0. Vì f(x) = (x –a).g(x) + r(x) nên bậc của r(x) nhỏ
hơn 1, tức là r(x) = c

F. Vì vậy, c = f(a) = 0. Ngược lại, nếu f(x) = (x – a). q(x) thì
f(a) = 0.
Hệ quả
Một đa thức khác không f(x)

F[x] bậc n có nhiều nhất n nghiệm trong F.
1.2.3. Trường
Trường F là một vành với phần tử đơn vị e

. Do đó nếu p|ab và p a thì p|(ab)
-1
= b. Vậy
p là số nguyên tố.
Ngược lại, giả sử p là số nguyên tố. Để chỉ ra rằng
*
p
Z là một nhóm nhân ta
chỉ cần chỉ ra rằng với mọi
*
p
Zx sẽ luôn tồn tại nghịch đảo x
-1
. Với a, b

Z
p
và
*
p
Zx , nếu xa

xb mod p thì a

b mod p

a – b

0 mod p.
Vì p|x(a–b)

trường con hợp lệ nào.
Với trường F bất kỳ, giao F
0
của tất cả các trường con hợp lệ là trường tối giản.
19

Trường F được gọi là có đặc số 0 nếu F
0


Q nghĩa là F chứa Q như một
trường con. Trường F được gọi là có đặc số p nếu F
0


Z
p
.
Trường hữu hạn là trường chứa hữu hạn các phần tử. Mọi trường hữu hạn có
một số nguyên tố là đặc số của trường. Một trường F có đặc số thì với mọi a

F,
pa =


p
aa 
= 0
Định nghĩa
Trường K với phần tử đơn vị nhân là 1. Với p thỏa mãn 01 11 

với mọi a, b

A ta có:
f(a * b) = f(a)

f(b)
Giả sử A và B là 2 nhóm (hoặc 2 trường), ta gọi h: A

B là một đẳng cấu
A đến B nếu h đảm bảo các tính chất của toán tử nhóm của A.
Trường hữu hạn
Trường hữu hạn là trường có hữu hạn các phần tử ký hiệu là F
q
hoặc GF(q)
với q là số các phần tử.
Định lý
F là trường mở rộng bậc n trên trường hữu hạn K. Nếu K có q phần tử thì F có
q
n
phần tử.
Chứng minh
Giả sử {
n

, ,
1
}là cơ sở của F như là một không gian vector trên K.
Mọi F



bậc n và mọi phần tử
của
n
p
F là một nghiệm của đa thức
xx
n
p

trên Z
p
.
Chứng minh
Đặc số của
n
p
F là p. Tập hợp F* = F \ {0} tạo thành nhóm nhân bậc
p
n
-1. Với
*F


, bậc của trong nhóm chia hết cho bậc của F*, p
n
– 1. Vì vậy, với
mọi
*F



p
.
Ví dụ
Trường
r
F
2
chứa F
2
(hoặc Z
2
).Nếu viết toán tử cộng trong
r
F
2
như là phép cộng
vector và viết phép nhân k và v(k,v

r
F
2
)là một tích vô hướng của k

F
2
và v
r
F
2
 .Khi đó

nếu

và

là các nghiệm của cùng một đa thức tối giản bậc m trên F
q
.
12
, ,,,
m
qqq

là
các liên hợp của
m
q
F

với F
q
.

m
q
F là một mở rộng của F
q
. Một cơ sở của
m
q
F (không gian vector trên F

, a
1
, …, a
n
), B = {b
0
, b
1
, …,
b
n
}

L, định nghĩa một quan hệ A ~ B gồm A, B và gốc O = (0, 0,…,0) là cộng
tuyến, nghĩa là tồn tại
K


thỏa mãn :
ii
ba 

, (i = 0, 1, …, n).
Quan hệ ~ là quan hệ tương đương và định nghĩa một phân hoạch của L. Tập
thương số là không gian chiếu ký hiệu là P
n
(K).
Mặt phẳng chiếu là tập các lớp tương đương của bộ ba (X, Y, Z) với
( ),,( ZYX


1u = u
Các phần tử của V được gọi là các vector và các phần tử của K được gọi là
các vô hướng. V là một không gian vector trên trường K và các v
1
, …, v
m


V.
Vector trong V có dạng c
1
v
1
+ c
2
v
2
+ …+ c
m
v
m
với c
i


K (i = 1, …, m) là một tổ
hợp tuyến tính của v
1
, …, v
m



K thỏa mãn:
c
1
v
1
+ c
2
v
2
+ …+ c
m
v
m
= 0
Tập S = {u
1
, u
2
,…,u
n
} của các vector tạo thành cơ sở của V khi và chỉ khi
u
1
, u
2
,…,u
n
là độc lập tuyến tính là span của V. Nếu S là một cơ sở của V thì mọi

trường hữu hạn hoặc bài toán phân tích thừa số của số nguyên, bài toán logarit rời
rạc trên đường cong elliptic chưa có thuật toán nào có thời gian thực hiện nhỏ hơn
cấp lũy thừa. Thuật toán tốt nhất được biết đến hôm nay tốn thời gian thực hiện cấp
lũy thừa.
24

2.1. CÔNG THỨC WEIERSTRASSE VÀ ĐƯỜNG CONG
ELLIPTIC
Gọi K là trường hữu hạn hoặc vô hạn. Một đường cong elliptic được định
nghĩa trên trường K bằng công thức Weierstrasse :
y
2
+ a
1
xy + a
3
y = x
3
+ a
2
x
2
+ a
4
x + a
6
(1)
Trong đó a
1
, a

với a
4
, a
6
 R (2)
cùng với một điểm đặc biệt O được gọi là điểm tại vô cực (cũng là phần tử
identify). Cặp giá trị (x,y ) đại diện cho một điểm trên đường cong elliptic và tạo
nên mặt phẳng tọa độ hai chiều (Affine) R x R . Đường cong elliptic E trên R
2

25

được gọi là định nghĩa trên R , ký hiệu là E (R). Đường cong elliptic trên số thực có
thể dùng để thể hiện một nhóm (E(R), +) bao gồm tập hợp các điểm (x ,y) thuộc R x
R với phép công + trên E(R).
2.2.1. Phép cộng

Hình 2: Điểm ở vô cực

Phép cộng điểm (ESUM) được định nghĩa trên tập E(R) của các điểm (x, y).
Điểm tại vô cực 0 là điểm cộng với bất kỳ điểm nào cũng sẽ ra chính điểm đó.
Như vậy,




, ,
P x y E R P O O P P
     