MỤC LỤC

LỜI CAM ĐOAN ii
CÁC KÝ HIỆU VIẾT TẮT iii
CÁC KÝ HIỆU TOÁN HỌC iv
MỞ ĐẦU 1
1 Chƣơng 1 CÁC KHÁI NIỆM CƠ BẢN 5
1.1. Số nguyên 5
1.2. Nhóm 8
1.3. Vành 10
1.4. Ánh xạ 10
1.5. Trường 10
1.6. Không gian vector 12
1.7. Vành tuyến tính 13
1.8. Trường hữu hạn 14
1.9. Không gian chiếu 16
2 Chƣơng 2 ĐƢỜNG CONG ELLIPTIC 17
2.1. Khái niệm đường cong Elliptic 17
2.1.1. Khái niệm 17
2.1.2. Đường cong Elliptic trên trường nguyên tố hữu hạn Fp 17
2.1.3. Đường cong Elliptic trên trường nhị phân hữu hạn GF(2
m
) 18
2.1.4. Các phép toán 19
2.2. Bài toán Logarith rời rạc 20
2.3. Đếm số điểm của đường cong elliptic trên trường Fq. 20
2.4. Tính chất đồng cấu của đường cong elliptic 21
3 Chƣơng 3 CÁC HỆ MẬT TRÊN ĐƢỜNG CONG ELLIPTIC 22
3.1. Lịch sử 22

3.2. Nhúng bản rõ vào các đường cong Elliptic 23
3.2.1. Imbeding 23


3.2.2. Mask 24
3.3. Một số hệ mã hóa trên đường cong elliptic 24
3.3.1. Hệ mã hóa “tựa” Elgamal 24
3.3.2. Hệ mã hóa Menezes-Vanstone 25
3.4. Một số sơ đồ chữ ký trên đường cong elliptic 27
3.4.1. Sơ đồ chữ ký ECDSA 27
3.4.2. Sơ đồ chữ ký Nyberg - Rueppel 28
3.4.3. Sơ đồ chữ ký mù Harn trên EC 29
3.4.4. Sơ đồ đa chữ ký mù Harn trên EC 32
3.5. Một số phương pháp tấn công các hệ ECC 34
3.5.1. Phương pháp tấn công “baby-step giant - step” 34
3.5.2. Phương pháp tấn công MOV 35
3.5.3. Các thuật toán tấn công khác 38
3.6. Lựa chọn đường cong Elliptic phù hợp 38
3.6.1. Trường K 38
3.6.2. Dạng của đường cong elliptic 39
3.6.3. Phương pháp lựa chọn 40
3.7. Một số chuẩn sử dụng hệ mật ECC 41
3.8. So sánh RSA và ECC 43
4 Chƣơng 4 ỨNG DỤNG CỦA ECC TRONG BỎ PHIẾU ĐIỆN TỬ 46
4.1. Khái niệm chung về bỏ phiếu điện tử 46
4.1.1. Các thành phần trong hệ thống bỏ phiếu điện tử 46
4.1.2. Các giai đoạn bỏ phiếu điện tử 47
4.1.3. Tính chất của bỏ phiếu điện tử 47
4.2. Các kỹ thuật bỏ phiếu điện tử 48
4.2.1. Kỹ thuật chữ ký mù 48

4.2.2. Kỹ thuật mã hóa đồng cấu 51
4.2.3. Kỹ thuật trộn phiếu 53
4.3. Quy trình bỏ phiếu điện tử đề xuất 55


4.3.1. Chuẩn bị 56
4.3.2. Cấp quyền bầu cử 57
4.3.3. Bỏ phiếu 59
4.3.4. Kiểm phiếu 61
4.4. Quy trình Bỏ phiếu dựa trên ECC 62
4.4.1. Cấp quyền bầu cử 62
4.4.2. Bỏ phiếu 63
4.4.3. Kiểm phiếu 63
5 KẾT LUẬN 64
DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 66
TÀI LIỆU THAM KHẢO 67



ii
LỜI CAM ĐOAN
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng
cá nhân, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn,
những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều
nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn
hợp pháp.
Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định
cho lời cam đoan của mình.
Hà Nội, ngày 30 tháng 04 năm 2006
Trƣơng Thị Thu Hiền



iii
CÁC KÝ HIỆU VIẾT TẮT
Alice
Người gửi tin hoặc người thực hiện việc ký
Ban ĐK
Ban đăng ký
Ban KP
Ban kiểm phiếu
Ban KT
Ban kiểm tra
Bob
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
E-Voting
Bỏ phiếu điện tử (Electronic Voting)
gcd
Ướ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
Bội số chung nhỏ nhất (Least Common Multiple)
MOV
Phương pháp tấn công Menezes – Okamoto - Vanstone
NIST
National Institute of Standards
RFC
Request For Comments
RIPEMD-160
Hàm băm 160 bit
RSA
Hệ mã hóa khóa công khai Rivest – Shamir – Adleman
TOF
Hàm cửa sập một chiều (Trapdoor One-way Function)



iv
CÁC KÝ HIỆU TOÁN HỌC
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ể

d
K
Thuật toán giải mã
E
Đường cong elliptic
e
K
Thuật toán mã hóa
F*
Nhóm nhân trên trường F
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.







1
MỞ ĐẦU
1. Bỏ phiếu điện tử - Thực trạng.
Trong suốt nhiều thế kỉ gần đây trong lịch sử thế giới, các cuộc bầu cử đã giữ
một vai trò quan trọng trong việc xác lập các thể chế chính trị của các quốc gia từ lớn
đến nhỏ. Trong thế giới hiện đại, việc bỏ phiếu bầu quốc hội (đơn vị tương ứng ở Anh,
Mỹ là Hạ Nghị Viện, ở Nga là Duma quốc gia) là một trong số những sự kiện
quan trọng nhất của đất nước. Từ những năm 1990, khi Internet bùng nổ, một câu hỏi
đã được quan tâm là: liệu một ngày nào đó, có thể thực hiện việc bỏ phiếu qua Internet?
Nhiều nước ở Châu Âu đã chuẩn bị các nghiên cứu với nhiều dự án cùng nhiều
chiến lược khác nhau, dưới nhiều góc độ: Kỹ thuật, Luật, Chính sách, Xã hội. Ngoài ra,
bỏ phiếu điện tử cũng được nghiên cứu và thử nghiệm ở những nước khác như Mỹ,
Braxin, Mêhicô, Nga, Ấn Độ (xem [11]).
Người ta đã bỏ rất nhiều công sức vào việc cải tiến các phương thức bầu cử,
khiến cho các cuộc bầu cử ngày càng trở nên "tốt" hơn. Các phương thức này được
thay đổi theo từng thời kì, theo sự tiến bộ của xã hội. Trong xu thế thực hiện
"chính phủ điện tử" thì việc số hoá cuộc bầu cử để thay thế cho phương thức
truyền thống là điều sẽ phải diễn ra trong tương lai gần.
Trong các ứng dụng an toàn thông tin, thì bỏ phiếu điện tử (E-Voting) là ứng

dụng đòi hỏi tính bảo mật cao nhất. Nó quan trọng vì sự thất bại của nó có những ảnh
hưởng nghiệm trọng đến các lĩnh vực khác. Ngay cả những giải pháp bảo mật tốt nhất
hiện nay cũng chưa giải quyết triệt để bài toán này. Người ta quan tâm tới E-voting
dưới các góc nhìn về luật (các luật đã đủ chưa để có thể cho phép tiến hành E-Voting?),
giải pháp công nghệ (các kỹ thuật hiện có đã đáp ứng đầy đủ các yêu cầu của E-Voting
và có phù hợp với các luật không?) và tâm lý (các cử tri có thực sự mong muốn thực
hiện bỏ phiếu bằng E-Voting? Và nếu có, họ có hài lòng với một hệ thống E-Voting đã
thiết kế và thử nghiệm không?).


2
Như đã nói ở trên, theo thời gian thì các phương thức bỏ phiếu cũng thay đổi,
và phương thức gần đây nhất là bỏ phiếu bằng máy tính điện tử thông qua các mạng
công khai (Internet, LAN,…). Với phương thức này thì mật mã học thực sự là công cụ
đảm bảo an toàn cho các “lá phiếu điện tử”.
2. ECC và những “đột phá” trong mật mã học.
Mục tiêu cơ bản của mật mã học là đảm bảo tính bí mật. Nó cho phép 2 đối tác
trao đổi thông tin với nhau một cách an toàn trên những kênh truyền thông công khai.
Hệ mật mã khóa bí mật có thể định nghĩa như sau: Giả sử ký hiệu M là tập tất cả
các bản rõ có thể. C là tập tất cả các bản mã có thể. K là tập các khóa có thể. Hệ mật
mã khóa bí mật gồm 2 hàm:
CMe
k
:
,
MCd
k
:
,
Kk 

sao cho
mmed
kk
))((

với mọi
Mm
và
Kk 
. Trong hệ mật mã này, người gửi (giả sử là Alice) và
người nhận (Bob) 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 Alice muốn gửi cho Bob một
thông điệp
Mm
, cô ấy sẽ gửi bản mã
)(mec
k

cho Bob. Bob 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.


3
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 trên các kênh công cộng
cho những ai muốn gửi thông tin cho họ hoặc xác minh chữ ký của họ.
Trong lịch sử hơn 20 năm của mật mã khóa công khai, đã có nhiều bài toán
“khó” được đưa ra xem xét để ứng dụng cho các vấn đề mật mã học. Trong đó có 2 bài
toán nổi bật nhất là bài toán logarith rời rạc trên trường hữu hạn và bài toán tìm ước số
nguyên tố. Năm 1985, Neal Koblitz và V.S.Miller đã độc lập nhau cùng đề xuất việc
sử dụng các đường cong elliptic cho các hệ mã hóa khóa công khai. Họ không
phát minh ra thuật toán mã hóa mới với các đường cong elliptic trên trường hữu hạn,
mà họ dùng những thuật toán đã có như Diffie – Hellman, sử dụng các đường cong
elliptic. Các đường cong Elliptic có thể dùng trong nhiều ứng dụng như kiểm thử
số nguyên tố hoặc bài toán tìm ước số nguyên tố. Các hệ mật mã trên đường cong
elliptic (ECC) được dự báo là sẽ phổ biến hơn RSA do khóa nhỏ gọn hơn nhiều

(khoảng 163 bit) so với RSA (1024 bit); vì vậy, tốc độ mã hóa nhanh hơn so với RSA.
Việc thương mại hóa ECC đã được một số nơi thực hiện như công ty Certicom
và công ty RSA đã hỗ trợ mã hóa ECC trong các bộ công cụ phát triển. Tuy nhiên, một
vấn đề có thể ảnh hưởng đến sự chấp nhận ECC rộng rãi như một phần của cơ sở hạ
tầng khóa công khai là các kỹ thuật thực thi đường cong elliptic, thói quen, các thuật
toán, và các giao thức. ECC đòi hỏi các thủ tục toán học phức tạp trong việc khởi tạo
các đường cong. Các chuyên gia công nghệ thông tin vẫn chưa hiểu thấu đáo để thiết
kế các hệ thống bảo mật dựa trên mật mã học, trong khi hệ RSA thì không quá phức
tạp và khó hiểu.


4
3. Bỏ phiếu điện tử và ECC
ECC không phải là một khái niệm mới. Kể từ khi được phát minh độc lập bởi
Miller và Koblitz, nó đã được nghiên cứu rộng rãi về tính an toàn cũng như tính hiệu
quả. Hội nghị quốc tế mới nhất về ECC được tổ chức tại Toronto – Canada (09/2005)
với chủ đề “ECC và ứng dụng” đã là một bằng chứng cho việc ECC thực sự đang được
quan tâm. Cho đến thời điểm hiện tại, 2 hệ mật mã chính là RSA và Elgamal vẫn đang
được sử dụng rộng rãi và chưa hề có một phương pháp tấn công hiệu quả nào để phá
vỡ chúng. Câu hỏi đặt ra là tại sao chúng ta cần một hệ mật mã mới. Đó là vì sự phát
triển nhanh chóng của công nghệ. Có thể thấy các máy tính ngày nay khác rất xa các
máy tính trước đây. Chúng ta sử dụng các thiết bị cầm tay như điện thoại di động,
pocketPC và hiển nhiên sẽ cần những phương pháp truyền tin an toàn cho các thiết bị
này. Tuy nhiên, các thiết bị này lại bị giới hạn về bộ nhớ, năng lực tính toán, băng
thông truyền. Chúng ta cần một hệ mật mã mới có kích thước khóa cũng như độ dài
chữ ký ngắn hơn. ECC đáp ứng các yêu cầu đó.
Bỏ phiếu điện tử muốn được ứng dụng rộng rãi thì cần cho phép thực hiện trên
nhiều thiết bị khác nhau, từ máy tính đến các thiết bị cầm tay. Với mục đích giảm các
yêu cầu về năng lực tính toán (tức là giảm chi phí), tăng độ an toàn, hướng tiếp cận
ECC là một giải pháp hiệu quả.


Trong phạm vi trình bày của luận văn, một số kiến thức sau xem như đã biết trước:
1. Độ phức tạp thuật toán.
2. Phân lớp bài toán.
3. Bài tóan “dễ”, bài toán “khó”, bài toán không giải được.
4. Hàm một chiều, hàm một chiều có cửa sập.
5. Mã hóa, chữ ký điện tử, hàm băm, đại diện thông điệp.


5
1 Chƣơng 1
CÁC KHÁI NIỆM CƠ BẢN
1.1. Số nguyên
Tập các số nguyên được ký hiệu là Z. tập hữu hạn A, số các phần tử của A ký
hiệu #A. Quan hệ tương đương (~) trên tập A là quan hệ 2 ngôi mà với x, y, z

A thì:
1. x ~ x (phản xạ)
2. Nếu x ~ y thì y ~ x (đối xứng)
3. Nếu x ~ y và y ~ z thì x ~ z (bắc cầu)
Với ~ là một quan hệ tương đương trên tập A. Gọi P = {[a] | a

A}, trong đó
[a] = {b

A | a ~ b} là một phân hoạch của A, khi đó:
1. Với mọi S

P, S


ф
2. Nếu S, T

P, thì S = T
3.
AS
PS




Một phần tử S

P là một lớp tương đương trên phân hoạch P.
Định lý 1.1 (Thuật toán tìm ƣớc số chung của Euclid)
Với mọi a, b

Z, b

0, tồn tại duy nhất q, r

Z để: a = bq + r,
||0 br 

Nếu r = 0 thì b|a. Ngược lại thì b a. Với a
1
, …, a
k



Z, nếu b|a
i
(i = 1,…, k) thì
b gọi là ước chung của a
1
,…,

a
k.
Ước chung lớn nhất của a
1
, …, a
k
ký hiệu là
gcd(a
1
, …, a
k
) và a, b

Z là nguyên tố cùng nhau khi và chỉ khi gcd(a, b) = 1.
Định lý 1.2
Nếu a, b

Z và khác 0 thì d = gcd(a, b) là phần tử nhỏ nhất trong tất cả các số
nguyên dương có dạng ax + by (x, y

Z)



6
Chứng minh
Giả sử C = {c

N | c = ax + by, x, y

Z}. C

ф. Đặt
e = ax
0
+ by
0

là phần tử nhỏ nhất của C. Chúng ta cần chỉ ra d = e. Nếu a = eq + r,
er 0
thì:
r = a – eq = a(1 – qx
0
) + b(-qy
0
)
Nếu r

0 thì nó phải thuộc C và điều này mâu thuẫn với lựa chọn e. Vì vậy, e|a.
Tương tự, e|b; do đó e

d. Mặt khác, e = ax
0
+ by

0
và d|a, d|b, suy ra d|e.
Vì vậy, d

e. Kết luận, d = e.
Hệ quả 1.3
Tồn tại x, y

Z thỏa mãn:
ax + by = c
khi và chỉ khi d|c với d = gcd(a, b)
Chứng minh
Nếu a = ed, b = fd, thì rõ ràng d|c. Mặt khác nếu d|c, đặt kd = c.
Vì tồn tại x
0
, y
0


Z để ax
0
+ by
0
= d, nên a(kx
0
) + b(ky
0
) = kd = c
Với mọi a, b, m


Z ta định nghĩa
a

b mod m khi và chỉ khi m|(a - b)
Dễ nhận thấy, với m cố định, đây là một quan hệ tương đương trên Z. Vì vậy, Z được
phân hoạch thành các lớp tương đương: Z
m
= {[a] | a

Z},
với [a] = {b

Z | a

b mod m}. Mỗi lớp tương đương [a] được thể hiện bằng các
phần tử của nó. Ví dụ, Z
m
= {0, 1, 2, …, m – 1}.
Định lý 1.4
Với a, m

Z, tồn tại x

Z thỏa mãn ax

1 mod m khi và chỉ khi gcd(a, m) = 1.


7
Chứng minh

x

Z để ax

1 mod m

có x, y

Z thỏa mãn ax – my = 1.
Theo hệ quả 1.3, định lý hoàn toàn được chứng minh.
p

N được gọi là nguyên tố khi và chỉ khi p > 1 và a p với mọi
a

Z, 1 < a < p. Nói cách khác, p

N, p > 1, p là nguyên tố khi và chỉ khi với mọi
a, b

Z, p|ab

p|a hoặc p|b
Định lý 1.5 (Định lý phần dƣ Trung Quốc)
Giả sử m
1
, …, m
r



N đôi một nguyên tố cùng nhau, gcd(m
i
, m
j
) = 1 với mọi
i

j. Có a
1
, …, a
r


Z. Khi đó, hệ phương trình
x

a
i
(mod m
i
) (
ri 1
)
có một nghiệm duy nhất theo modulo M = m
1
x …xm
r
là
x =



r
i
iii
yMa
1
mod M
trong đó M
i
= M/m
i
và M
i
y
i


1 mod m
i

Chứng minh
Chú ý rằng M
i
là tích của tất cả các m
j
với j

i. Vì vậy, nếu j

i thì

M
i


0 mod m
j
. Chú ý, gcd(M
i
, m
i
) = 1, theo định lý 1.4, M
i
y
i


1 mod m
i

có một nghiệm y
i
. Do đó,
x =


r
i
iii
yMa
1


a
i
M
i
y
i


a
i
mod m
i

với mọi i,
ri 1
. Vì vậy, x là nghiệm của hệ phương trình đồng dư.
Hàm Euler
ф: N

N được định nghĩa là
ф(m) = #{k

N |
mk 1
, gcd(k, m) = 1}


8
Định lý 1.6

ф(m) = #{a

Z
m
| ab

1 mod m với b

Z
m
}
Chứng minh Dựa vào định lý 1.1, ta có điều phải chứng minh.
Ví dụ
Nếu p là một số nguyên tố, ф(p) = p – 1 và với a bất kỳ thuộc Z
p
, p a, tồn tại b

Z
p
để ab

1 mod p.
Giả sử p là số nguyên tố lẻ và x

Z,
11  px
, khi đó x được gọi là thặng dư
bậc 2 theo modul p nếu y
2



x mod p có một nghiệm y

Z
p
. x được gọi là quadratic
non-residue nếu x không là thặng dư bậc 2 theo modulo p và x

0 mod p.
1.2. Nhóm
Nhóm là cấu trúc bao gồm tập G và toán tử hai ngôi * trên G.
Với a, b

G, a * b

G được định nghĩa như sau:
1. a * (b * c) = (a * b) * c với mọi a, b, c

G
2. Tồn tại e

G thỏa mãn e * a = a * e = a với mọi a

G, (e được gọi là phần
tử trung hòa).
3. Với mỗi a

G, tồn tại một phần tử b

G thỏa mãn b * a = a * b = e

(b là duy nhất và được gọi là phần tử nghịch đảo của a)
Ký hiệu
,*G
là nhóm nhân và
,G
là nhóm cộng. Trong nhóm cộng, phần tử
trung hòa là 0 và phần tử nghịch đảo của a là –a. Trong nhóm nhân, phần tử trung hòa
là 1 và phần tử nghịch đảo của a là a
-1
.
,*G
được gọi là nhóm Abel nếu a * b = b * a với mọi a, b thuộc G.
Giả
,*G
là nhóm và H là tập con của G. Cấu trúc
,H
được gọi là nhóm con
của
,*G
nếu

là một thu hẹp của * tới H x H và
,H
là một nhóm.


9
Nếu
,*G
là nhóm hữu hạn thì số các phần tử của

,*G
được gọi là bậc của G
và ký hiệu là |G|. Nếu
,*G
là nhóm nhân hữu hạn, bậc của một phần tử a

G là
số nguyên dương nhỏ nhất m thỏa mãn a
m
= 1. Trong nhóm nhân, với mọi phần tử
thuộc nhóm, m luôn tồn tại.
Định lý 1.7
,*G
là nhóm nhân hữu hạn bậc n. Nếu bậc của phần tử a

G là m thì
a
k


1 khi và chỉ khi m|k
Chứng minh
Nếu k = mq, thì a
k
= (a
m
)
q
=1. Ngược lại, k = mq + r,
mr 0

. Khi đó
a
r
= a
k
. (a
-1
)
mq
= 1. Vì vậy, r phải bằng 0.
Hệ quả 1.8
Nếu
,*G
là nhóm nhân hữu hạn bậc n, thì:
(1) Với mọi a

G, a
n
= 1.
(2) Bậc của mọi phần tử a

G chia hết cho |G|.
Nếu a

G có bậc m thì H = {a
k
| k

Z }là nhóm con của G và có bậc m. Nếu G
có một phần tử a có bậc n = |G| thì G = {a

k
| k

Z} và G được gọi là một nhóm cylic,
a được gọi là phần tử sinh của G. Ví dụ, tập hợp Z
n
= {0, 1, 2,…, n – 1} là một nhóm
cylic bậc n với toán tử cộng modulo n.
Định lý 1.9 (Euler)
Với a, m

Z thỏa mãn gcd(a, m) = 1,
1
)(

 m
a
mod m
Chứng minh
Theo định lý 1.1 G
m
= {a

Z
m
| gcd(a, m) = 1} tạo thành nhóm nhân bậc ф(m).


10
Định lý 1.10 (Fermat)

Cho p là số nguyên tố và a

Z. Khi đó, ta có:
(1) a
p-1


1 mod p, nếu p a.
(2) a
p


a mod p
Chứng minh
(1) Vì ф(p) = p – 1 nên đây là trường hợp đặc biệt của định lý Euler.
(2) Dễ dàng thấy nếu a

0 mod p là hiển nhiên, ngược lại theo (1).
1.3. Vành
Vành là tập R với 2 toán tử cộng (+) và nhân (.) với các điều kiện sau:
1.
,R
là nhóm Abel.
2. a . (b . c) = (a . b) . c với mọi a, b, c

R.
3. a . (b + c) = a . b + a . c và (a + b) . c = a . c + b . c với mọi a, b, c

R.
1.4. Ánh xạ

Với 2 toán tử hai ngôi * và

trên các tập A và B, ta định nghĩa một ánh xạ
f : A

B nếu 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
từ A đến B nếu h có các phép toán giống các phép toán của các toán tử trên nhóm A.
1.5. Trƣờng
Trường F là vành với phần tử đơn vị e

0 và F* = {a

F | a

0 } là một nhóm nhân.



11
Định lý 1.11
Vành Z
p
là một trường khi và chỉ khi p là số nguyên tố.

Chứng minh
Với a, b

Z, ta có: p là số nguyên tố

p|ab tức là p|a hoặc p|b
Nếu Z
p
là trường thì
*
p
Z
tạo thành nhóm nhân. Nếu p a thì a

0 mod p.
Điều này nghĩa là a
*
p
Z
và tồn tại a
-1
. 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à 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)

p|x hoặc p|a – b và
*
p
Zx
tức là p x. Điều này suy ra

xZ
p
= {xa | a

Z
p
} = Z
p
trong đó xa = 1 với a

Z
p
vì luôn tồn tại phần tử 1 trong Z
p
.
Vậy mỗi
*
p
Zx
luôn có phần tử nghịch đảo.
Định nghĩa
Cho F là một trường. 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 nó không có 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. 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


12
Đị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 

p
được gọi

là đặc số của K. (xem [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(p
n
) có đặc số p.
Nếu H là trường con của K thì H và K có cùng đặc số.
F là trường mở rộng của trường K. Ký hiệu F = K(

) nếu F là trường mở rộng
nhỏ nhất của K chứa

. Nếu F là trường hữu hạn đặc số p thì nhóm nhân F* = F \ {0}
là nhóm cylic và F = Z
p
(

) với

là phần tử sinh của nhóm F* và

được gọi là phần
tử nguyên thủy của F.
1.6. Không gian vector
K là trường và V là 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ử ánh xạ từ K x V

V được định nghĩa thỏa mãn các điều
kiện sau:
1. a(u + v) = au + av
2. (a + b)u = au + bu

3. a(bu) = (ab)u
4. 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à 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à tổ hợp tuyến tính của
v
1
, …, v

m
. Tập hợp tất cả các tổ hợp tuyến tính gọi là span của v
1
, …, v
m
và ký hiệu là
span(v
1
, …, v
m
).


13
V là không gian vector trên trường K. Các vector v
1
, …, v
m


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 c
1
,…, c
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 và 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ử của
S. Nếu không gian vector V có cơ sở là một số hữu hạn các vector thì bất kỳ cơ sở nào
của V cũng sẽ có cùng số phần tử. Khi đó nó chính là chiều của V trên K.
Nếu F là trường mở rộng của trường K thì F là một không gian vector trên K.
Chiều của F trên K được gọi là bậc mở rộng của F trên K.

1.7. Vành tuyến tính
Cho 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


F (
ni 0
).
Cho 2 đa thức



n
i
i

i
xaxf
0
)(
và



n
i
i
i
xbxg
0
)(

ta định nghĩa tổng của f(x) và g(x) là



n
i
i
ii
xbaxgxf
0
)()()(

Cho 2 đa thức




n
i
i
i
xaxf
0
)(
và



m
j
j
j
xbxg
0
)(

ta định nghĩa tích của f(x) và g(x) là




nm
k
k
k

xcxgxf
0
)()(
với




mjni
kji
jik
bac
0,0

Vành được tạo thành bởi tất cả các đa thức trên F với toán tử thông thường là cộng và
nhân được gọi là vành đa thức trên F và ký hiệu là F[x].


14
Định lý 1.12 (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à đ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ả
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].
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ả 1.13
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.8. 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ý 1.14
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ử.


15
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

sẽ có dạng
nn
cc


11
trong đó
Kc
i

(i = 1,…, n). Vì mỗi c
i
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à q
n
.

Định lý
Nếu F là trường hữu hạn có đặc số p thì F có p
n
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 Z
p
với p là
đặc số của F.
Định lý 1.15
Trường hữu hạn F =
n
p
F
là một trường mở rộng của Z
p
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

, chúng ta có
1
1


n
p

hay


n
p
. Vì
xx
n

p

có nhiều nhất p
n
nghiệm,
n
p
F
gồm tất cả các nghiệm của
xx
n
p

trên Z
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 đó
r
F
2
được xem là không gian vector trên F
2
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 F
2
. Vì vậy, có 2
d

phần tử trong không gian vector này. Vì d = r,
r
F

2
là không gian vector r chiều.


16

m
q
F
là một mở rộng của F
q
. 2 phần tử
m
q
F

,
là liên hợp trên F
q
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
q
) của
{
12
, ,,,
m
qqq


} gồm
m
q
F

và các liên hợp của nó với F
q
, được gọi là cơ sở
trực giao của
m
q
F
trên F
q
. Mọi trường mở rộng bậc hữu hạn của một trường hữu hạn có
một cơ sở trực giao.
1.9. Không gian chiếu
Xét L = K
n+1
\{0} với K là một trường. Với A = (a
0
, 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

) ~ (X, Y, Z) (
K

). Mỗi lớp tương đương (X, Y, Z) được gọi là một
đ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 =
Z

X
, y =
Z
Y
. 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ẳng affine cộng với các điểm Z = 0.


17
2 Chƣơng 2
ĐƢỜNG CONG ELLIPTIC
2.1. Khái niệm đƣờng cong Elliptic
2.1.1. Khái niệm
Đường cong elliptic E trên trường F biểu diễn bằng phương trình Weierstrass:
Y
2
+ a
1
XY + a
3
Y = X
3
+ a
2
X
2
+ a
4
X + a
6


Fa
i


(2.1)
Ký hiệu E(F) là tập các điểm (x,y)
2
F
thỏa mãn phương trình Weierstrass với điểm
trung hòa O.
Phương trình trên đúng cho các đường cong trong trường bất kỳ. Trong mật mã
học, chúng ta chỉ xét các trường hữu hạn. Hai trường được xét là F
p
với p là số nguyên
tố và
m
q
F
với các phần tử
r
pq 
.
2.1.2. Đƣờng cong Elliptic trên trƣờng nguyên tố hữu hạn Fp
Xét trường F
p
(p nguyên tố, p > 3) với công thức đổi biến như sau:
3
2
a

XX 
,
2
31
aXa
YY



Khi đó phương trình Weierstrass có dạng:
Thay thế cho Y ở vế trái (2.1):
4/2/4/
)2/)(()2/)(()2/)((
2
331
22
1
2
313311
2
31
aXaaXaY
aXaYaaXaYXaaXaY



Cả XY và Y đều triệt tiêu nên các hệ số a
1
và a
3

đều phải bằng 0. Vế trái còn lại Y
2
.
Thay thế cho X ở vế phải (2.1):
642
3
24
23
624
2
22
3
2
3/27/2)9/(
)3/()3/()3/(
aaaaXaaX
aaXaaXaaX





18
Đặt
aaa  )(
4
2
9
1
và

baaaa 
642
3
1
3
2
27
2
, ta có dạng X
3
+ aX + b.
Vậy trong trường F
p
(2.1) trở thành:
Y
2
= X
3
+ aX + b
(2.2)
Xét tập xác định của phương trình này. Xét phương trình y
2
= f(x), với
dx
dy
yxf 2)(' 
. Trong đó
dx
dy
không xác định tại (x

0
, y
0
) khi và chỉ khi
f’(x
0
) = f(x
0
) = y
0
= 0. Nói cách khác hàm f(x) phải có nhiều nghiệm tại điểm x
0
.
Trong trường hợp f(x) = x
3
+ ax + b thì điều này tương đương với
disc(f(x)) = -(4a
3
+ 27b
2
) = 0.
Định nghĩa
Một đường cong Elliptic E trên trường hữu hạn F
p
được cho bởi phương trình dạng:
baXXY 
32
,
p
Fba ,

, và
0)274(
23
 ba

(2.3)
Trong phương trình trên, dấu “=” được hiểu là “

”. Trong toàn bộ luận văn này,
quy ước viết ngắn gọn “

”là “=”.
2.1.3. Đƣờng cong Elliptic trên trƣờng nhị phân hữu hạn GF(2
m
)
Xét trường GF(2
m
) có đặc số khác 2. Có thể thực hiện phép đổi biến như sau:
1
3
2
1
a
a
XaX 
,
3
1
2
34

2
1
3
1
a
aaa
YaY



Định nghĩa
Đường cong elliptic E trên trường hữu hạn
m
F
2
được cho bởi phương trình dạng:
Y
2
+ XY = X
3
+ aX
2
+ b, a, b
m
F
2


(2.4)




19
2.1.4. Các phép toán
Giả sử E là đường cong elliptic trên trường F
p
hoặc
m
F
2
và P, Q là 2 điểm trên E.
Xét các phép toán sau trên E:
1. Phần tử không: Ký hiệu là O. Nếu P là điểm O thì –P cũng là O. Với mọi điểm
Q ta định nghĩa O + Q bằng Q.
2. Phần tử nghịch đảo: Trong F
p
, định nghĩa phần tử nghịch đảo của P = (x, y) là
–P = (x, -y). Nếu Q = -P thì P + Q = O.
Trong trường
m
F
2
ta định nghĩa -P = (x, x+y).
3. P + Q: Nếu P

Q, gọi đường thẳng l =
QP
giao với E tại một điểm R. Khi đó
P + Q bằng –R.
4. 2P: l là tiếp tuyến với E tại P, R là giao điểm của l với E, định nghĩa 2P = -R.

5. kP: kP

E(Z
p
) với k là số nguyên được tính bằng cách cộng P với chính nó k lần
liên tiếp. Để tăng tốc độ tính toán có thể áp dụng thuật toán “nhân đôi và cộng”.

Hình 2.1. Phép cộng 2 điểm P + Q = R