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Ử.
1
LỜI CẢM ƠN
Lời đầu tiên, em xin được gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật
Tiến, người thầy đã giúp đỡ em trong suốt quá trình làm khóa luận, đồng thời cũng
là người thầy đã hướng dẫn em những bước đi đầu tiên để khám phá một lĩnh vực
đầy bí ẩn và thách thức – lĩnh vực an toàn và bảo mật dữ liệu.
Em xin được cảm ơn các thầy, các cô đã giảng dạy em trong suốt bốn năm
qua. Những kiến thức mà các thầy, các cô đã dạy sẽ mãi là hành trang giúp em vững
bước trong tương lai .
Em cũng xin được cảm ơn tập thể lớp K50CC, một tập thể lớp đoàn kết với
những người bạn không chỉ học giỏi mà còn luôn nhiệt tình giúp đỡ mọi người,
những người bạn đã giúp đỡ em trong suốt bốn năm học tập trên giảng đường Đại
học.
Cuối cùng, em xin được gửi lời cảm ơn sâu sắc tới gia đình em, những người
luôn kịp thời động viên, khích lệ em, giúp đỡ em vượt qua những khó khăn trong
cuộc sống.
Hà nội, tháng 05 năm 2009
Sinh viên
Nguyễn Minh Hải
2
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

Ước số chung lớn nhất (Greatest Common Divisor)
GF
Trường hữu hạn (Galois Field)
IEEE
Institute of Electrical and Electronics Engineers
IETF
Internet Engineer Task Force
IFP
Bài toán ước số nguyên (Integer Factorization Problem)
lcm
CÁC KÝ HIỆU TOÁN HỌC
5
< g >
Nhóm cyclic được sinh bởi g
#E
Số phần tử của đường cong elliptic
C
Tập các bản mã có thể
dK
Thuật toán giải mã
E
Đường cong elliptic
eK
Thuật toán mã hóa
F*
Nhóm nhân trên trường F
Fq
Trường hữu hạn với q phần tử
G
Điểm cơ sở của E

p
(p là số nguyên tố) 29
2.3.2. Đường cong elliptic trên trường F
2m
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
7
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

m ∈ M
, cô ấy sẽ gửi bản mã c = e
k
(m) cho Jerry. Jerry sẽ
khôi phục bản rõ m bằng việc dùng hàm giải mã d
k
. Hệ mật mã khóa bí mật phải
đảm bảo rằng các hàm e
k
và d
k
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ý
điện tử. Khóa riêng được người sở hữu giữ bí mật và nó được sử dụng để tạo chữ ký
điện tử hoặc để giải mã các thông điệp đã được mã hóa bằng khóa công khai. Khóa
công khai không cần thiết phải giữ bí mật do tính chất “khó tính được khóa riêng từ
khóa công khai” của cặp khóa. Vì vậy, người dùng có thể công bố khóa công khai

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 a1, a2, …, an , 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 a1, a2, …, an , 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 a1, a2, …, an , trong đó mọi ước
chung của a1, a2, …, an đều là ước của d, thì d được gọi là ước chung lớn nhất
của a1, a2, …, an . Ký hiệu d = gcd (a1, a2, …, an) hay d = UCLN(a1, a2, …, an).
Nếu gcd(a1, a2, …, an) = 1,thì a1, a2, …, an được gọi là nguyên tố cùng nhau.
Một bội chung m >0 của các số nguyên a1, a2, …, an , trong đó mọi bội
chung của a1, a2, …, an đều là bội của m, thì m được goi là bội chung nhỏ nhất
của a1, a2, …, an . Ký hiệu m = lcm(a1, a2, …, an) hay m = BCNN(a1, a2, …, an).
b. Ví dụ
Cho a =12, b =15, gcd(12,15) = 3,
lcm(12,15) = 60.
Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) = 1.
c. Tính chất
1. d = gcd(a1, a2, …, an) tồn tại x1, x2,…, xn sao cho: d = a1x1+a2x2+…+anxn
a1,a2, an nguyên tố cùng nhau⇔tồn tại x1,x2, xn sao cho: 1 = a1x1+a2x2+…+anxn
2. d = gcd(a1, a2, …, an) ⇔ gcd(a1/d, a2/d,…, an/d) =1.
3. m = lcm(a1, a2, …, an) ⇔ gcd(m/a1, m/a2,…, m/an) =1.
4. gcd(m a1, m a2, …, m an) = m * gcd(a1, a2, …, an) (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).
11
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

a
i
=
∑
t
i
b
i
(mod m)
i=1
i =1
với ti = ± 1.
3 Tích các “đồng dư”:
(a* b) (mod n)
≡
[(a mod n) * (b mod n)] (mod n)
Tổng quát:
Có thể nhân từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một
đồng dư thức theo cùng modulo m, tức là:
k
k
Nếu ai ≡ bi (mod m) với i=1 k,
thì ta có:
12
∏
a
i
=
∏
b

G9
2006
Mersenne 44??
2
30402457
2 -1
9152052
G9
n
=P1 2 kn
k
, trong đó:
.
P P
.
Chứng minh
Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1< a, b < k.
Như vậy : p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E
(Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Niu-tơn).
Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử sai, hay k là số nguyên tố.
3. Hàm Euler:
Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên
tố cùng nhau với n được ký hiệu
φ
(n)
và gọi là hàm Euler.
Nhận xét: Nếu p là số nguyên tố, thì
φ
(p) = p-1
Ví dụ:

Nếu a * b = a * c, thì b = c.
Nếu a * c = b * c, thì a = b.
* Tập hợp các số nguyên Z cùng với phép cộng (+) thông thường là nhóm giáo
hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên.
* Tập Q* các số hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép
nhân (*) thông thường là nhóm giao hoán. Gọi là nhóm nhân các số hữu tỷ (số
thực) khác 0.
* Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán.
b. Nhóm Cyclic
Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong
các phần tử của nó.
Tức là có phần tử g ∈ G mà với mỗi a ∈ G, đều tồn tại số n ∈ N để
g n = g * g * … * g = a.
(Chú ý g * g * … * g là g * g với n lần).
Khi đó g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm
G. Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g ∈ G sao cho mọi
phần tử trong G đều là một luỹ thừa nguyên nào đó của g.
Nhóm (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1.
15
Cho (G, *) là Nhóm Cyclic với phần tử sinh g. và phần tử trung lập e.
Nếu tồn tại số tự nhiên nhỏ nhất n mà g
n
= e, thì G sẽ chỉ gồm có n
phần tử khác nhau: e, g, g2 , g3 , . . . , 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 (Zn* , phép nhân mod n)
* Kí hiệu Zn = {0, 1, 2, . , n-1} là tập các số nguyên không âm < n.
Zn 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.
(Zn , + ) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n.

φ
(p)
≡
1 (mod n), hay bp -1
≡
1(mod n).
d. Phần tử nghịch đảo đối với phép nhân
* Định nghĩa
Cho a ∈ Zn , nếu tồn tại b ∈ Zn sao cho a b ≡ 1 (mod n), ta nói b là phần
tử nghịch đảo của a trong Zn và ký hiệu a -1.
Một phần tử có phần tử nghịch đảo, gọi là khả nghịch.
* Định lý: UCLN (a, n) = 1 ⇔ Phần tử a ∈ Zn có phần tử nghịch đảo.
Chứng minh
Nếu a a-1 ≡ 1 (mod n) thì a a-1 = 1 + kn ↔ a a-1 - kn = 1 → (a, n) =1.
Nếu (a, n) = 1, ta có a a-1 + kn = 1 → a a-1 = 1+kn, do đó a a-1 ≡ 1 (mod n).
16
* Hệ quả:
Mọi phần tử trong Zn*
đề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

x
i
và
g ( x) =
∑
b
i
x
i
i=0
i =0
n
Ta định nghĩa tổng của f(x) và
g(x) là f ( x) + g ( x) =
∑
(a
i
+ b
i
)
x
i
i
n
m
Cho 2 đa thức f ( x) =
∑
a
i
x

cộng
và nhân được gọi là vành đa thức trên F
và ký hiệu là
F[x].
Định
lý
(Thuật toán
chia cho
F[x])
Giả sử
f(x) và
g(x) ∈
F[x] có
bậc
nguyên
dương,
tồn tại
duy
nhất đa
thức
q(x),
r(x) ∈ 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à

x
]
k
h
i
v
à
c
h
ỉ
k
h
i
x
–
a

l
à
ư
ớ
c
của
f(x)
trong
F[x].
17
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ì

Vì p|x(a–b) ⇒ p|x hoặc p|a – b và
x ∈ Z
*p
tức là p
x. Điều này suy ra
xZp = {xa | a ∈ Zp} = Zp trong đó xa = 1 với a ∈ Zp vì luôn tồn tại phần tử 1 trong Zp.
Vậy mỗi
x ∈ Z
*p
luôn có phần tử nghịch đảo.
Định nghĩa
F là một trường. Một tập con K của F cũng là một trường với các toán tử của
F được gọi là trường con của F. Hay F là một trường mở rộng của K. Nếu K ≠ F
thì K được gọi là một trường con hợp lệ của F. Trường là tối giản nếu không có
trường con hợp lệ nào.
Với trường F bất kỳ, giao F0 của tất cả các trường con hợp lệ là trường tối giản.
18
Trường F được gọi là có đặc số 0 nếu F0 ≅ 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 F0 ≅ Zp.
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,
p
pa = a + + a = 0
Định nghĩa
1 +
p
gọi là đặc số của K. [5]
(Các trường hữu tỷ Q, số thực R, số phức C có đặc số là 0 )
Với p là nguyên tố thì GF(pn) có đặc số p.
Nếu H là trường con của K thì H và K có cùng đặc số.

Giả sử {
α
1
, ,
α
n
}là cơ sở của F như là một không gian vector trên K.
Mọi
β
∈ F sẽ có dạng
β
= c
1
α
1
+ + c
n
α
n
trong đó c
i
∈ K (i = 1,…, n). Vì mỗi ci có
thể là một trong q phần tử của K nên số các tổ hợp tuyến tính là qn.
19

Trường K với phần tử đơn vị nhân là 1. Với p thỏa mãn 01 1 =++ được
Định lý
Nếu F là một trường hữu hạn có đặc số p thì F có pn phần tử với n nguyên dương.
Vì vậy, mọi trường hữu hạn là một mở rộng của trường đẳng cấu Zp với p là
đặc số của F.

r được xem là không gian vector trên F2 với chiều r. Ký hiệu d là
chiều của không gian vector này. Có thể thực hiện ánh xạ 1 – 1 giữa các phần tử
trong không gian vector d chiều và các d-tuple của các phần tử trong F2. Vì
vậy,có2d phần tử trong không gian vector này.Vì d = r,
F
2
r là không gian vector r
chiều.
F
q
m
là một mở rộng của Fq. 2 phần tử
α
,
β
∈ F
q
m
là liên hợp trên Fq nếu
α
và
2 m −1
m
F
q
m
là một mở rộng của Fq. Một cơ sở của F
q
m
(không gian vector trên Fq)

Trường
F
2
chứa F2(hoặc Z2).Nếu viết toán tử cộng trong
F
2
như là phép cộng
vector và viết phép nhân k và v(k,v∈
F
2
)là một tích vô hướng của k∈ F2 và v
các liên hợp của
α
∈ F
q
với Fq.
của {
α
,
α
q
,
α
q
, ,
α
q
} gồm
α
∈ F

điểm chiếu trên mặt phẳng chiếu. Nếu một điểm chiếu có Z ≠ 0, thì (x, y, 1) là một
thể hiện của lớp tương đương với x =
X
Z
, y =
Y
Z
. Mặt phẳng chiếu có thể được
định nghĩa là tập tất cả các điểm(x, y)của mặt phẳngAffine cộng với các điểm Z = 0.
21
1.2.4. Không gian vector
K là một trường và V là một nhóm cộng Abel. V được gọi là không gian vector
trên trường K nếu một toán tử K x V → V được định nghĩa thỏa mãn các điều kiện
sau:
a(u + v) = au + av
(a + b)u = au + bu
a(bu) = (ab)u
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 v1, …, vm ∈ V.
Vector trong V có dạng c1v1 + c2v2 + …+ cmvm với ci ∈ K (i = 1, …, m) là một tổ
hợp tuyến tính của v1, …, vm. Tập hợp tất cả các tổ hợp tuyến tính gọi là span của v1,
…,vmvà ký hiệu là span(v1, …, vm). v1, …, vm được gọi là span nếu của V nếu
V = span(v1, …, vm).
V là không gian vector trên trường K. Các vector v1, …, vm ∈ V được gọi là
độc lập tuyến tính trên K nếu không có các vô hướng c1,…, cm ∈ K thỏa mãn:
c1v1 + c2v2 + …+ cmvm = 0
Tập S = {u1, u2,…,un} của các vector tạo thành cơ sở của V khi và chỉ khi
u1, u2,…,un 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
phần tử của V được biểu diễn duy nhất dưới dạng tổ hợp tuyến tính của các phần tử