TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 KHOA TOÁN
— 0O 0----------------------

KHÓA LUẬN TỐT NGHIỆP

ĐƯỜNG CONG ELLIPTIC VÀ ỨNG DỤNG TRONG MẬT MẢ
CHUYÊN NGÀNH: TOÁN ỨNG DỤNG

Giảng viên hướng dẫn:

Trần

Vĩnh

Đức.

Sinh viên: Lê Thị Thu Lớp: K37-sp Toán

HÀ NỘI, 5/2015


Bài khóa luận này được lioàn thành dưới sự hướng dẫn nhiệt tình của
T.s Trần Vĩnh Đức. Qua đây em xin gửi lời cảm ƠI1 sâu 8ắc tới các thầy cô
trong tổ Toán ứng dụng và các tliầy cô trong khoa Toán trường ĐHSP H à
Nội 2 đã giúp đỡ em trong quá trình học tập để thuận lợi cho việc nghiên
cứu. Đặc biệt, em xin gửi lời cảm ƠI1 cliân thành tới T.s Trần Vĩnh Đức
LỜI CẢM ƠN
người đã dành cho em sự hướng dẫn nhiệt tình, chu đáo và CỈ 1Ỉ bảo cho
em trong suốt quá trình liọc tập nghiên cứu và thực hiện khóa luận.
Dù đã hết sức cố gắng, nhưng do đây là lần đầu tiên làm quen với việc
nghiên cứu khoa liọc và do năng lực CÒI1 liạn cliế nên khó tránh, khỏi

1
0
1

Lenstra.
Kit luan

2
5

2


Tài liệu tham khảo

Khóa luận tốt nghiệp

2

GVHD: T.s Trần Vĩnh Đức


Chương 1 Cơ sở
toán học
1.1

Phép chia và phép chia có dư

Tập hợp cảc số nguyên được kí hiệu bằng kí tự z. Có tliể cộng , trừ, Iihân
các số nguyên theo cácli thông thường, và Ĩ 1Ó đáp ứng tất cả các quy tắc

Định nghĩa 1.1.4. (a) Một số nguyên được gọi là ước chung của nhiều số
ai,a- 2,^ 3,... klii nó là ước của mỗi số đó.
(b) Một ước chung D của các số ai, a 2 , D‘Ầ , CI N sao cho mọi ước chung của
A,Ị , ữ 2j A 3I •■■■> A N đều là ước của d, thì được gọi là ước chung 1ỚI1
nhất(ƯCLN) của ai, a 2 , D‘Ầ, a n . T a ký hiệu là D = (ai, a 2 , аз, A N ).
(c) Nếu 1 là UCLN của ữi, 02, аз, ...,Ữ N thì các số ữi, ữ 2, аз, A N được gọi là
nguyên tố cùng nhau.

1.2

Số học modun

Định nghĩa 1. 2. 1. Cho hai số nguyên A

và ò,
M > 0.
Ta
nói rằng
A ĐỒNG DƯ VỚI B THEO MODUN 772, nếu trong phép cilia A và
B clio M ta
được cùng số dư. Ta ký hiệu là

A = B mod M.
Ví dụ 2. 15 = 7 mod 2, 5 = —3 mod

8.

Đ ị n h l í 1. 2. 2. Cho m > 1 ÌÀ số nguyên. Các mệnh đề so,иỉà tương
đương.
(a) A = B mod RN.

và dư là r (0 < R < m), ngliĩa là A = M.Q A + R.
Thay a bởi A = B + MT ta được
b + mt = m.q a + r
hay

b = m(q a — t)r 0 < r < m.

Hệ tliức này clio ta thấy klii cliia B clio M, ta cũng được cùng một số dư R
như khi chia A cho ra, nghĩa là A = B mod M.
□
Chúng ta viết

Z/MZ = {0,l,2,...,ra — 1}.
và gọi Z/mZ là TẬP CÁC SỐ NGUYÊN MODUN ĨĨI. Lưu ý rằng bất cứ
klii nào chúng ta cũng thực hiện được phép cộng hoặc nhân trong Z/mZ, và
luôn pliải chia clio ĨĨ 1, số dư CÒĨ 1 lại là pliần tử trong Z/mZ.
Hìnli 1.1 Minh họa clio Z/mZ bằng cách thực hiện phép cộng và nhân
modun 5 cho bởi bảng

+

Hình 1.1. Bảng pliép cộng và pliép nliân modun 5

Định nghĩa 1.2.3. Tập hợp thương của tập hợp các số nguyên trên quan
hệ đồng dư theo modun m, được qọi là tập hợp các lớp thặnq dư modun
m, và ký hiệu là z m . Mỗi pỉiần tử của z m được gọi là một lớp thặng dư
modun m.


Định lí 1.2.4. Lớp thặng dư modun ra, A là pliần tử kliả nghịch của vành

..CLf) 5 thì p chia hết cho ít nhất một
trong các dị.

Đ ị n h l í 1 . 3 . 3 . ( D ị n l i l ý c ơ b ả n ) . Mọi số tự nhiên lớn hơn ỉ
đều có thể phân tích được thành một tícìi của các thừa số nguyên tố
và sự pỉiân tích đó là duy nhất kỉiông kề thứ tự các thừa số.
CHỨNG MINH, a) Sự phân tícli được. Giả sử A là một số tự nhiên 1ỚĨ 1
hơn 1. Khi đó, a có ít nhất một số nguyên tố Pi nào đó và ta có: A =
PIAI,A,I E N.
Nếu CIỊ = Ì thì ta được A = PI và đó là sự phân tích A thành tliừa số
nguyên tố.


Nếu CHỊ > 1 thì DỊ có ước nguyên tố P-2 nào đó và ta có: A,Ị = Q>2

tố.

£ N nêll ữ = PÌP2^2Nếu Ü2 = I thì A = P1P2 là pliân tích của A thành tliừa số nguyên
Khóa luận tốt nghiệp
GVHD: T.s Trần Vĩnh Đức

Nếu A 2 > 1 tliì tlieo lý luận trên, A 2 có ước nguyên tố Рз,...
Quá trình này phải kết tliúc, nghĩa là sẽ có N sao cho A N = 1, A N _I =
P là một số nguyên tố, bỏi vì ta có: a,ai,ơ, 2,... là một dãy những số tự
nhiên giảm. Như vậy ta được A = PI.P2---PN là sự phân tích của А
tliànli tích những thừa số nguyên tố.
b) Sự duy Iiliất: Giả sử, ta có: А = P\.P2---PN =
là liai
dạng phân tích của A thành tích của những thừa số nguyên tố. Dẳng thức
trên cliứng tỏ PI là ước của QI.Q2---QM nên PI phải trùng với một QJ

Trường

Định nghĩa 1.5.1. Ta gọi là trường một miền nguyên X trong đó iriọi phần
tử khác không đều có Khóa
một nghịch
luận tốt
đảo nghiệp
hoặc vành giới hạn có ít nhất
GVHD:
hai T.s Trần Vĩnh Đức
pliần tử.
Vành là một trường klii và chỉ klii P là số nguyên tố.

1.6

Trường hữu hạn

Trường gồm hữu hạn các phần tử được gọi là trường hữu hạn. Trường gồm
hữu liạn pliần tử có đặc số kliác không, và đặc số đó là một số nguyên tố
P.
Giả sử FQ là một trường hữu hạn gồm Q phần tử với đặc số P. Vì F Q
chứa pliần tử 1 nên Ĩ 1Ó sẽ cliứa trường F P như một trường con. Do F Q là
trường hữu hạn nên nó là rriở rộng hữu hạn của F P Ì nghĩa là một không
gian vecto R chiều trên F P . Từ đó, suy ra rằng F Q gồm P R phần tử, tức là
Q = PR.
Ngược lại, ta sẽ chứng tỏ rằng với P, R cho trước (P là số nguyên tố và
/ là số nguyên dương), tồn tại trường YỚi P R phần tử. Hơn nữa, các trường
hữu hạn với số phần tử như nhau sẽ đẳng cấu với nhau, nghĩa là có tương
ứng 1 — 1 giữa chúng, và tương ứng này bảo toàn các phép tính cộng và
nhân, phần tử 0 và phần tử nghịch đảo của trường.


Chương 2
Đường cong Elliptic và ứng dụng
trong mật mã
2.1

Đường cong Elliptic

Một đường cong Elliptic là tập hợp các nghiệm cho từ một phương trình:
Y 2 = X 3 + AX + B
Phương trình loại này được gọi là phương trình Weirerstrass được nghiên
mô tả Ehai
cứu rộng rãi trong thế kỷ tliứ 19. Ví dụ, liình đường cong 2.elliptic
UE2
dưới đây:
Y 2 = X 3 -3X + 3 Y 2 = £i
X 3 - 6X + 5
được thể hiện trên Hình: 2 A

E 2 : V 2 = X 3 - 6X + 5

Hình 2.1: Hai đường cong elliptic

Eị và E‘>


KI ì, ó a luận tốt nghiệp

GVHD: T..H Trần Vĩnh Đức




18

4 A 2 + 27 B Ỷ 0.

Nhận xét 2. 2. 2. Ta gọi A E = 4:A 2 -\-27B 7^ 0 là biệt thức của E.
Diều kiện Ỷ 0 là tương đương với điều kiện là đa tliức X 3 + AX + B không
có nghiệm kép. Nghĩa là,
19

20

X 3 + AX + B = (X -

ei

)(X - e 2 )(X - e 3 ).

trong đó 6i,e 2,e 3 là số, thì Ỷ 0 khi và chỉ klii ei,e 2,e 3 đôi một khác

21

nhau.
22

Vậy A E Ỷ 0 thì đường cong không có điểm kì dị.

Pliép cộng trên E được địnli ngliĩa Iihư sau. Nếu P và Q là liai
điểm trên E. L là đường thẳng Iiối P và ọ, hoặc là tiếp tuyến của E tại P


31

Định lí 2.2.4. (Thuật toán Cộng trên đường cong elliptic). Dể clio

E : Y 2 = X 3 + AX + B
33
ỉà một đường cong ellvptic và đê Pị và P 2 là điểm
trên E. a ) Nếu P\ = o, thì Pị + P 2 = P 2.
32


(b) Cách khấc, nếu P 2 = o, tỉiìPị + P 2 = Pị
(c) Cácỉi kìiấc, viết Pị = (xi, yi) v à P 2 = ( í T -2, 2/ 2)
(d) Nếu Xị = x 2 v à ĩjị = -y 2 , t l i ì Pị + P 2 = o
(e) Cách khấc, định nqìiĩa X bởi
3

34
35

và để cho
36

37

Xs

= A2 —


và
41

x3 - X 2 X 2 + {A- 2Xv)X + (B - V2) = 0 .

Chúng ta biết rằng phương trình này có X ị và X'2 là hai nghiệm của
nó. Nếu chứng ta gọi £3 là nghiệm thứ ba, sau đó nếu như
42

43

X 3 - X 2 X 2 + (A- 2Xv)X + (B- V2) = (X -

Xl

){X - x 2 )(X - x 3 ).

Bây giờ khai triển và nhìn hệ số của X 2 của cả hai vế. Hệ số của X 2 ỏ vế
phải là —X\ — X2 — £ 3, và bằng —À 2 là hệ số của X 2 ở vế trái. Diều Iiày
cho chúng ta tínli £3 = À 2 — XỊ — X2, và sau đó các Y- tọa độ của các
giao điểm thứ ba của E và L được cho bởi XX‘S + V. Cuối cùng, để có
được Pị + P2, cliúng ta pliải chiếu lên trục X có nghĩa là tliay thế các tọa
độ Y của Ĩ 1Ó.
□
2.2.2
Phép nhân
44

Pliép nliân một số nguyên K với một điểm P tliuộc đường cong
elliptic là điểm Q được xác định bằng cách cộng N lần điểm P và Q G E

51
iriột phương trình từ
52

E :Y 2 = X 3 + AX + B với A, B G FP điều kiện 4A 3 + 27 B 2 ^ 0,

53

và các điểm trên E có tọa độ trên FP , mà đươc biểu thị bởi
54

E(Fp) = {(x, y) : x,y e Fp, y 2 = X 3 + Ax + B u o} .

Cho P = (XI,YI) và Q = (# 2, 2/ 2) là liai điểm trên E(FP). Tổng
của PI + p 2 là điểm ( 3, 1/ 3) thu được bằng cách áp dụng các thuật
56
toán Cộng đường cong elliptic(Dịnli lý 2.2.4). Tuy nhiên, không tliể
nói (# 3, 2/ 3) là một điểm trong E(FP).
55

Đ ị n h l í 2 . 3 . 1 . Cho E ỉ,à một đường cong elìÁptìc trên
E(Fp) và cho hai điểm p và Q trên E(Fp).
(a) Các thuật toán Cộng trên đường cong elliptic( Dịnlỉ lý 2.2.4) áp
58
dụng
cho
p và Q mang lại một điểm trong E(Fp). Cỉiúng ta ký hiệu
59
điểm đó bởi p + Q.
(b) Ngoài ra luật này đáp ứng tất cả các thuộc tính E ( F p ) được liệt

70
71
72

x2 —

69

X ị 1 — 9—8

Tiếp tlieo chúng ta tính
V = V ỉ - Xx l = 7 - 8.9 = -65 = 0. X s = X 2 — X ị — x 2 = 64 — 9
— 1 = 54 = 2,
73

2/3 = -(\x 3 + v) =

75

p + Q = ( 1, 8) + (9, 7) = ( 2, 10) trên E(F 1 3).

Tương tự ,tính p + p, ta có
2
76 + A _ 3.9 + 3 _ 246
77

79

-8. 2 = - 16 = 1 0.


16
(
17
(
18
(
19
(
20
(
21
(
2212,2) (
23
(
14
o 15
o 1.5)
1,8)
2,3)
2,10)
9,6)
9,7)
12,2)
12,11)
24
( 25 ( 26 ( 27
( 30
( 31 ( 32
( 33

2,3)
54
( 2,3)
55
( 1,8)
56
( 9,6)
57
( 58 12,11)o 59 ( 6012,2) ( 1,5)
61
( 622,10) ( 9,7)
63
(
2,10)
2,10)
9,7)
1,5)
12,2)
1.8)
12,11)
9,6)
2,3)
64
( 65 ( 66 ( 67 ( 68 ( 69 ( 70
( 71
( 73
(
o 72
9,6)
74

95
( 12,11)
96
( 9,7)
97
( 2,10)
98
( 9,6)
99
( 1001.5) ( 2,3)
101
( 1021.8) ỡ 103 (
12,11) 12,11) 9,6)
12,2)
9,7)
2,3)
2,10)
1,8)
1,5)
80


82

Bảng 2.1 : Bảng phép cộng của E: Y 2 = X 3 + 3X + 8 trên FI3
Y 2 = X s + AX + B Đ ị n h l í 2 . 3 . 2 . ( H a s s e ) . Cho E là đường

83

cong elliptic trên Fp. Thì $ E ( F p ) = p + 1 — tp v ớ i tp t h ỏ a

đã có các thuật toán dưới như thuật toán dùng tính chỉ số và thuật toán
dùng đường cong elliptic của Lenstra, được giới tliiệu năm 1985. Dù clio
những công trình này không làm các liệ mã sụp đổ, nhưng Ĩ 1Ó buộc phép
xây dựng các hệ mã pliải giảm hiệu quả vì phải dùng các klióa dài hơn để
đảm bảo an toàn. Công trình của Lenstra cũng đánh dấu lần đầu tiên lý
thuyết các đường cong elliptic được sử dụng vào mật mã, ở đây có vai trò
như phá mã. Diều thú vị là ngay sau đó thì lý thuyết các đường cong
elliptic đã được sử dụng cho việc lập mã. Koblitz và Miller cùng độc lập
đề nghị tliay tliế việc sử dụng nhóm trong trường hữu hạn bằng nhóm các
điểm trên đường cong elliptic vì ở đó, các thuật toán dưới mũ đã biết để
giải quyết bài toán logarit rời rạc có vẻ như không the áp dụng được. Từ
88


đó việc sử dụng đường cong elliptic dẫn tới dẫn đến những hệ mã hiệu quả
liơri (do không cần phải chọn khóa quá dài để chống lại các thuật toán
dưới 111 ũ).
90 Miller và Kobliz giới thiệu những hệ mật mã elliptic. Họ không


phát minli ra các thuật toán mới nhưng đã đóng góp 1ỚI1 là chỉ
ra viêc áp dụng elliptic cho các hệ khóa công khai. Miller đề xuất mọi
giao tliức trao đổi khóa tựa như Diffie - Heilman vào năm 1985. Kobliz
Khóa luận tốt nghiệp
GVHD: T.s Trần Vĩnh Đức
đưa ra thuật toán rriã hóa tương tự như hệ ElGamal và Massey-Orrmra
vào năm 1987. Sơ đồ đầu tiên tương tự như RSA và liàm một cliiều(có
cửa sập) rriới dựa trên đường cong elliptic được đưa vào năm 1991 bởi
Koyama, Maurer, Okamoto, và Vanstone(thuật toán này tốc độ tliực hiện
nhanh gấp 6 lần so với RSA). Cùng với thời điểrri đó, Kaliski chứng


v à c h ú n g t a g ọ i n l à ỉoqarit rời rạc elliptic của Q đối với p.
Nhận xét 3.2.2. Tương tự với log bình thường ta có

96
97

log P (Qi + Q 2 ) = logp(Qi) + logp(Q 2 ) v ớ i Q i , Q 2 £ E{Fp)- ( 3 - 1 )

Tliực tế logarit rời rạc trong E(F P ) thỏa mãn (3.1) có Iigliĩa là
I1Ó tuân theo luật Cộng khi nliórri E(FP) ánh xạ vào nhóm Z/sZ.
Chúng
99
ta nói ánh xạ LOGP xác định được gọi là đồng cấu Iihóm
98

100

logp : E(Fp) —* Z/sZ.


3.3

Mật mã đường cong elliptic

Dó là tliời gian để áp dụng các đường cong trong mật mã. Cliíing ta bắt
đầu với các ứng dụng đơn
giản luận
nhất, tốt
Diffie-Hellman

Eve không thể suy ra (ĨIATIB)P n ếu không giải bài toán logarit rời rạc
trên E của trường FP.
105

Ví dụ 7. Alice và Bob quyết địnli và sử dụng elliptic Diffie- Heilman với
các số nguyên , đường cong và điểm:
107
P = 3851, EĨ Y 1 = X 3 + 324X + 1287, P = (920,303) e £(F 3851 ). Alice và
Bob chọn các giá trị bí mật tương ứng ĨIA = 1194 và ĨIỊỊ = 1759, và sau đó:
108 Alice tính Q A = 1194P = (2067,2178) e E{F Z № Ì ) T
106

1
Thuật toán ElGamal Elip IĨIỞ rộng thông till 4-1 so
rộng 2-1 của ElGamal khi sử dụng Fp.

với tỉ lệmở