TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
———————o0o——————–

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


LỜI CẢM ƠN

Bài khóa luận này được hoà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 ơn sâu sắc tới
các thầy cô trong tổ Toán ứng dụng và các thầ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 ơn chân
thành tới T.S Trần Vĩnh Đức người đã dành cho em sự hướng dẫn
nhiệt tình, chu đáo và chỉ bảo cho em trong suốt quá trình họ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 học và do năng lực còn hạn chế nên khó tránh
khỏi những sai sót. Em mong muốn nhận được sự chỉ bảo, đóng góp
của quí thầy cô để cho bài khóa luận được tốt hơn.

Em xin chân thành cảm ơn!
Hà Nội, tháng 05 năm 2015
Sinh viên
Lê Thị Thu


LỜI CAM ĐOAN

Em xin cam đoan bài khóa luận là do bản thân nghiên cứu cùng
với sự hướng dẫn của T.S Trần Vĩnh Đức không hề trùng với bất cứ
đề tài nào.
Hà Nội, tháng 05 năm 2015
Sinh viên
Lê Thị Thu


Mục lục
Lời cảm ơn

1

Lời cam đoan

2

1 Cơ
1.1
1.2
1.3
1.4

1.5
1.6

sở toán học
Phép chia và phép chia
Số học modun . . . . .
Số nguyên tố . . . . . .
Nhóm . . . . . . . . .
Trường . . . . . . . . .
Trường hữu hạn . . . .

có dư
. . . .
. . . .
. . . .
. . . .
. . . .

.
.
.
.
.
.

.
.
.
.
.

.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

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

2.2 Các phép toán trên đường cong elliptic . . . . .
2.2.1 Phép cộng . . . . . . . . . . . . . . . . .
2.2.2 Phép nhân . . . . . . . . . . . . . . . . .
2.3 Đường cong elliptic trên trường hữu hạn . . . . .
3 Hệ
3.1
3.2
3.3

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.

.
.
.
.

.
.
.
.
.
.

5
5
6
8
9
10
10

.
.
.
.
.

12
12
15
15

18
18

mật mã đường cong elliptic
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . .
Logarit rời rạc trên đường cong elliptic(ECDLP) . . .
Mật mã đường cong elliptic . . . . . . . . . . . . . . .
3.3.1 Diffie- Hellman elliptic trao đổi khóa . . . . .
3.3.2 Hệ mật mã ElGamal trên đường cong elliptic .
3.4 Thuật toán tìm nhân tử trên đường cong elliptic của
Lenstra. . . . . . . . . . . . . . . . . . . . . . . . . .

Kết luận

21
21
22
23
23
24
25
28

3


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

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


Tài liệu tham khảo

Lê Thị Thu

29

4

K37C-SPT ĐHSP Hà Nội 2


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ó thể cộng , trừ,
nhân các số nguyên theo cách thông thường, và nó đáp ứng tất cả các
quy tắc thông thường của số học (luật giao hoán, luật kết hợp, luật
phân phối, vv). Nếu a và b là các số nguyên thì ta có thể cộng chúng
a + b và trừ chúng a − b, và nhân chúng a.b. Trong mỗi trường hợp,
ta có kết quả là một số nguyên.
Nhưng nếu ta muốn giữa các số nguyên có phép chia thì không
phải lúc nào cũng có thể chia một số nguyên . Ví dụ, chúng ta không
thể chia 3 cho 2, vì không có số nguyên 32 .Điều này dẫn đến khái niệm
cơ bản của quan hệ chia.
Định nghĩa 1.1.1. Cho a và b là các số nguyên, với b = 0.Nếu có
một số nguyên c sao cho a = bc thì ta nói rằng b chia hết a hay b là
ước của a và kí hiệu là b | a.

Nếu b không chia hết a thì ta kí hiệu b a.
Ví dụ 1. Ta có 847 | 485331, vì 485331 = 847.573. Mặt khác, 355
259943, vì khi chúng ta thử chia 259943 cho 355 ta sẽ được 1 số dư
là 83. Chính xác hơn,259943 = 355.732 + 83 vì vậy 259943 không là
bội của 355.
Mệnh đề 1.1.2. Cho a, b, c ∈ Z là các số nguyên.
(a) Nếu a | b và b | c thì a | c.
(b) a | b và b | a thì a = ±b.
(c) Nếu a | b và a | c thì a | (b + c) và a | (b − c).
5


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

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

Định lí 1.1.3. Cho các số nguyên dương a và b. Khi đó tồn tại và
duy nhất q , r sao cho:

a = b.q + r

với 0 ≤ r < b

.
Định nghĩa 1.1.4. (a) Một số nguyên được gọi là ước chung của
nhiều số a1 , a2 , a3 , ... khi nó là ước của mỗi số đó.
(b) Một ước chung d của các số a1 , a2 , a3 , ..., an sao cho mọi ước chung
của a1 , a2 , a3 , ..., an đều là ước của d, thì được gọi là ước chung lớn
nhất(UCLN) của a1 , a2 , a3 , ..., an .Ta ký hiệu là d = (a1 , a2 , a3 , ..., an ).
(c) Nếu 1 là UCLN của a1 , a2 , a3 , ..., an thì các số a1 , a2 , a3 , ..., an đượ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à b, m > 0. Ta nói rằng
a đồng dư với b theo modun m, nếu trong phép chia a và b cho 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.
Định lí 1.2.2. Cho m ≥ 1 là số nguyên.Các mệnh đề sau là tương
đương.
(a) a ≡ b mod m.
(b) m | a − b.
(c) Có một số nguyên t sao cho a = b + mt.
Chứng minh. (a)=⇒(b). Theo giả thiết, khi chia a và b cho m ta
được cùng một số dư, như vậy có nghĩa là tồn tại một số tự nhiên r,
0 ≤ r < m và các số nguyên qa và qb sao cho ta có

a = m.qa + r
b = m.qb + r,
từ đó ta được

a − b = m(qa − qb ).
Lê Thị Thu


6

K37C-SPT ĐHSP Hà Nội 2


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

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

Đẳng thức này chứng tỏ m | (a − b).
(b)=⇒(c). Vì m | (a − b) nên ta có t ∈ Z sao cho a − b = mt, hay
a = b + mt.
(c)=⇒(a). Lấy a chia cho m, giả sử ta được thương là qa và dư là
r(0 ≤ r < m), nghĩa là a = m.qa + r.
Thay a bởi a = b + mt ta được

b + mt = m.qa + r
hay

b = m(qa − t)r 0 ≤ r < m.
Hệ thức này cho ta thấy khi chia b cho m ta cũng được cùng một số
dư r như khi chia a cho m, nghĩa là a ≡ b mod m.
Chúng ta viết
Z/mZ = {0, 1, 2, ..., m − 1} .
và gọi Z/mZ là tập các số nguyên modun m. Lưu ý rằng bất cứ khi
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 phải chia cho m, số dư còn lại là phần tử trong Z/mZ.
Hình 1.1 Minh họa cho Z/mZ bằng cách thực hiện phép cộng và
nhân modun 5 cho bởi bảng

+
0
1
2
3
4

0
0
1
2
3
4

1
1
2
3
4
0

2
2
3
4
0
1

3
3

4
0
1
2

4
4
0
1
2
3

.
0
1
2
3
4

0
0
0
0
0
0

1
0
1
2

3
4

2
0
2
4
1
3

3
0
3
1
4
2

4
0
4
3
2
1

Hình 1.1. Bảng phép cộng và phép nhâ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 gọi là tập hợp các lớp thặng dư
modun m, và ký hiệu là Zm . Mỗi phần tử của Zm được gọi là một lớp
thặng dư modun m.


Lê Thị Thu

7

K37C-SPT ĐHSP Hà Nội 2


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

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

Định lí 1.2.4. Lớp thặng dư modun m, A là phần tử khả nghịch của
vành Zm khi và chỉ khi A là lớp nguyên tố modun m.
Ta gọi là φ(m), số các phần tử khả nghịch của vành các lớp thặng dư
modun m.
Định lí 1.2.5. (Định lý Euler). Nếu a, m ∈ Z, m < 0, (a, m) = 1 thì
ta có:
aφ (m) ≡ 1 mod m.
Định lí 1.2.6. (Định lí Fermat). Nếu p là một số nguyên tố và a là
một số nguyên không chia hết cho p thì ta có

ap−1 ≡ 1

1.3

mod m.

Số nguyên tố

Định nghĩa 1.3.1. Một số tự nhiên lớn hơn 1 và không có ước nào

khác ngoài 1 và chính nó ( không có ước thực sự) được gọi là số nguyên
tố.
Mệnh đề 1.3.2. Nếu p là số nguyên tố, và p chia hết cho tích a.b
với a, b là hai số nguyên. Thì p chia hết ít nhất cho một trong hai số
a và b.
Tổng quát hơn, nếu p chia hết cho tích của các số nguyên, thì

p | a1 a2 ...an ,
thì p chia hết cho ít nhất một trong các ai .
Định lí 1.3.3. ( Định lý cơ bản ). Mọi số tự nhiên lớn hơn 1 đều có
thể phân tích được thành một tích của các thừa số nguyên tố và sự
phân tích đó là duy nhất không kể thứ tự các thừa số.
Chứng minh. a) Sự phân tích được. Giả sử a là một số tự nhiên lớn
hơn 1. Khi đó, a có ít nhất một số nguyên tố p1 nào đó và ta có:
a = p1 a1 , a1 ∈ N .
Nếu a1 = 1 thì ta được a = p1 và đó là sự phân tích a thành thừa
số nguyên tố.
Lê Thị Thu

8

K37C-SPT ĐHSP Hà Nội 2


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

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

Nếu a1 > 1 thì a1 có ước nguyên tố p2 nào đó và ta có: a1 =
p2 a2 , a2 ∈ N nên a = p1 p2 a2 .

Nếu a2 = 1 thì a = p1 p2 là phân tích của a thành thừa số nguyên
tố.
Nếu a2 > 1 thì theo lý luận trên, a2 có ước nguyên tố p3 ,...
Quá trình này phải kết thúc, nghĩa là sẽ có n sao cho an = 1, an−1 =
p là một số nguyên tố, bởi vì ta có: a, a1 , a2 , ... là một dãy những số
tự nhiên giảm. Như vậy ta được a = p1 .p2 ...pn là sự phân tích của a
thành tích những thừa số nguyên tố.
b) Sự duy nhất: Giả sử, ta có: a = p1 .p2 ...pn = q1 .q2 ...qm là hai
dạng phân tích của a thành tích của những thừa số nguyên tố. Đẳng
thức trên chứng tỏ p1 là ước của q1 .q2 ...qm nên p1 phải trùng với một
qj nào đó (1 ≤ j ≤ m). Vì không kể đến thứ tự của các thừa số nên có
thể coi p1 = q1 . Từ đó, ta có được p2 ...pn = q2 ...qm . Ta lấy p2 và lặp
lại cho đến khi ở một vế không còn thừa số nguyên tố nào. Nhưng lúc
đó ở vế còn lại cũng không còn thừa số nguyên tố nào vì nếu ngược lại
sẽ xảy ra hoặc 1 = qn+1 .qn+2 ...qm hoặc pm+1 pm+2 ...pm = 1 là không
thể được. Vì vậy, ta phải có m = n và pi = qi , i = 1, 2, ..., n.
Tính duy nhất đã được chứng minh.

1.4

Nhóm

Cho X là một tập hợp tùy ý khác ∅, trên X có một phép toán hai
ngôi kí hiệu là . X cùng với phép toán hai ngôi là một nhóm nếu
thỏa mãn các điều kiện :
(a) Tính kết hợp: (a b) c = a (b c) với mọi a, b, c ∈ X.
(b) Phần tử đồng nhất: Tồn tại e ∈ X thỏa mãn a e = e a với
mọi a ∈ X (e được gọi là phần tử trung hòa).
(c) Phần tử nghịch đảo: với mỗi a ∈ X , tồn tại một phần tử b ∈ X
thỏa mãn a b = b a = e ( b là duy nhất và được gọi là phần tử nghịch

đảo của a). Và người ta kí hiệu phần tử nghịch đảo của a là a−1 .
• X gọi là nhóm giao hoán(Able) nếu a b = b a với mọi a, b ∈ X.
• Cấp của nhóm X là số phần tử trong nhóm X . Một nhóm có
cấp hữu hạn được gọi là nhóm hữu hạn.

Lê Thị Thu

9

K37C-SPT ĐHSP Hà Nội 2


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

1.5

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

Trường

Định nghĩa 1.5.1. Ta gọi là trường một miền nguyên X trong đó
mọi phần tử khác không đều có một nghịch đảo hoặc vành giới hạn
có ít nhất hai phần tử.
Vành Zp là một trường khi và chỉ khi 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 hạn phần tử có đặc số khá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ì
Fq chứa phần tử 1 nên nó sẽ chứa trường Fp như một trường con. Do
Fq là trường hữu hạn nên nó là mở rộng hữu hạn của Fp , nghĩa là
một không gian vecto r chiều trên Fp . Từ đó, suy ra rằng Fq gồm pr
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à f là số nguyên dương), tồn tại trường với pr 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.
Định lí 1.6.1. Giả sử Fq là trường hữu hạn với q = pr phần tử. Khi
đó, mọi phần tử của Fq đều thỏa mãn phương trình

Xq − X = 0
và Fq chính là tập hợp các nghiệm của phương trình đó. Ngược lại,
trường nâng của Fp bởi đa thức X q − X là trường hữu hạn có q phần
tử.
Chứng minh 1.6.2. Trường Fq có q = pr phần tử. Khi đó các phần
tử khác 0 của Fq lập thành một nhóm nhân cấp q − 1. Bởi vậy mọi
phần tử của nó đều thỏa mãn phương trình X q−1 = 1. Vì vậy, mọi
phần tử của Fq đều là nghiệm của phương trình X q − X = 0 và Fq
là trường nghiệm của phương trình.
Lê Thị Thu

10

K37C-SPT ĐHSP Hà Nội 2



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

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

Giả sử Fq là một trường có q phần tử. Ta kí hiệu Fq∗ tập hợp các
phần tử khác không của trường Fq . Khi đó, mọi phần tử của Fq∗ đều
có nghịch đảo và Fq∗ lập thành một nhóm Abel. Vì Fq∗ có hữu hạn
phần tử, nên đối với một phần tử tùy ý a ∈ Fq∗ , tồn tại số nguyên
không âm k sao cho ak = 1. Số k bé nhất thỏa mãn tính chất đó được
gọi là bậc của phần tử a.

Lê Thị Thu

11

K37C-SPT ĐHSP Hà Nội 2


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 cứu rộng rãi trong thế kỷ thứ 19. Ví dụ, hình 2.1 mô tả hai
đường cong elliptic E1 , E2 dưới đây:

E1 :
E2 :

Y 2 = X 3 − 3X + 3
Y 2 = X 3 − 6X + 5

được thể hiện trên Hình 2.1.

Hình 2.1: Hai đường cong elliptic E1 và E2

12


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

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

Hình 2.2: Quy tắc cộng trên đường cong elliptic.

Cho P và Q là hai điểm trên đường cong elliptic E như mô tả trên
Hình 2.1. Ta vẽ đường thẳng L qua P và Q. Đường L cắt E tại 3 điểm
P ,Q và R. Từ điểm R, ta lấy đối xứng qua trục x (nghĩa là chúng
ta nhân tọa độ y bởi −1) ta được điểm R mới. Điểm R được gọi là
“tổng của hai điểm P và Q” mặc dù bạn có thể thấy, quá trình này
khác với những phép cộng thông thường. Ta ký hiệu: R = P ⊕ Q.
Ví dụ 3. Cho E là một đường cong elliptic


Y 2 = X 3 − 15X + 18.

(2.1)

Cho P = (7, 16) và Q = (1, 2) thuộc đường cong E . Đường thẳng L
qua P và Q có phương trình

7
1
Y = X− .
(2.2)
3
3
Để tìm những điểm mà E cắt L, chúng ta thế (2.2) vào (2.1) và tìm X .
Như vậy,
7
1 2
X−
= X 3 − 15X + 18,
3
3
Phương trình này tương đương với
49 2 14
1
X − X + = X 3 − 15X + 18,
4
9
9
L:


Lê Thị Thu

13

K37C-SPT ĐHSP Hà Nội 2


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

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

Biến đổi ta được phương trình

0 = X3 −

49 2 121
161
X −
X+
.
4
9
9

tương đương với

X3 −

161

23
49 2 121
X −
X+
= (X − 7).(X − 1).(X + ) = 0
9
9
9
9

Vì vậy, giao điểm thứ ba của L và E có tọa độ

R= −

23 170
,−
.
9
27

Cuối cùng, chúng ta có

P ⊕Q= −

23 170
,−
.
9
27


Hãy tưởng tượng nếu điểm Q chạy dài trên đường cong E và ngày
càng tiến lại gần P hơn. Thì đường L sẽ trở thành tiếp tuyến của E
tại P. Do đó để cộng điểm P với chính nó chúng ta chỉ cần lấy L là
đường tiếp tuyến của E tại P.
Ví dụ 4. Từ đường cong E và điểm P từ ví dụ 3. Chúng ta tính
P ⊕ P . Tiếp tuyến của E tại P được tính bằng đạo hàm phương
trình (2.1). Ta có

2Y

dY
= 3X 2 − 15, vì vậy
dX

dY
3X 2 − 15
=
(2.3)
dX
2Y
Thay tọa độ của P (7, 16) vào (2.3), ta tìm được hệ số góc của tiếp
33
tuyến là λ = , do đó tiếp tuyến của E tại P cho bởi phương trình
8
33
103
L:Y = X−
.
(2.4)
8

8
Thay (2.4) vào (2.1) của E, ta có

33
103
X−
8
8
Lê Thị Thu

2

= X 3 − 15X + 18,
14

K37C-SPT ĐHSP Hà Nội 2


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

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

1089 2 2919
9457
X +
X−
= 0,
64
32
64

193
(X − 7)2 . X −
= 0.
64
193
Ta thay thế X =
vào phương trình (2.4) của L để có được
64
223
Y =−
, nên ta có
512
X3 −

P ⊕P =

193 223
,
.
64 512

Nhận xét 2.1.1. Nếu P (a, b) và P (a, −b) đối xứng nhau qua trục
X thì ta có
P ⊕ P = O.
Ví dụ 5. Tiếp tục với các đường cong E từ ví dụ 3. Ta nhận thấy
rằng điểm T = (3, 0) nằm trên đường cong E và tiếp tuyến của E tại
T là đường thẳng X = 3. Do đó, nếu chúng ta cộng T với chính nó,
thì ta được T ⊕ T = O.

Tính chất của đường cong elliptic

• Nếu hai điểm P1 = (x1 , y1 ) và P2 = (x2 , y2 ) với x1 = x2 cùng
nằm trên đường cong elliptic thì đường thẳng qua hai điểm P1
và P2 sẽ cắt một điểm duy nhất P3 = (x3 , y3 ). Điểm này có thể
xác định thông qua P1 và P2 trên E .
• Tiếp tuyến của đường cong E tại điểm bất kỳ P = (x, y) trên
E cũng cắt E tại một điểm duy nhất. Điểm này có thể xác định
qua P .

2.2
2.2.1

Các phép toán trên đường cong elliptic
Phép cộng

Định nghĩa 2.2.1. Một đường cong Elliptic E là tập hợp các nghiệm
cho một phương trình Weirerstrass

Y 2 = X 3 + AX + B,
Lê Thị Thu

15

K37C-SPT ĐHSP Hà Nội 2


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

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

sao cho A và B thỏa mãn


4A2 + 27B = 0.
Nhận xét 2.2.2. Ta gọi ∆E = 4A2 +27B = 0 là biệt thức của E. Điều
kiện ∆E = 0 là tương đương với điều kiện là đa thức X 3 + AX + B
không có nghiệm kép. Nghĩa là,

X 3 + AX + B = (X − e1 )(X − e2 )(X − e3 ).
trong đó e1 , e2 , e3 là số, thì ∆E = 0 khi và chỉ khi e1 , e2 , e3 đôi một
khác nhau.
Vậy ∆E = 0 thì đường cong không có điểm kì dị.
Phép cộng trên E được định nghĩa như sau. Nếu P và Q là hai
điểm trên E . L là đường thẳng nối P và Q, hoặc là tiếp tuyến của
E tại P nếu P = Q. Thì L cắt L tại ba điểm P , Q và R. Khi đó
tổng của P và Q là điểm R (a, −b) bằng cách lấy đối xứng với điểm
R(a, b) qua trục X .Ta ký hiệu là P ⊕ Q hay P + Q.
Nếu P (a, b) thì chúng ta kí hiệu điểm đối xứng của P là P =
(a, −b), hoặc kí hiệu là −P.
Định lí 2.2.3. Cho E là một đường cong elliptic. Khi đó phép cộng
trên E có các tính chất sau:
(a) P + O = O + P = P với mọi P ∈ E [Tính đồng nhất ].
(b)P + (−P ) = O với mọi P ∈ E [ Tính nghịch đảo].
(c)(P + Q) + R = P + (Q + R) với mọi P, Q, R ∈ E [Tính kết hợp].
(d)P + Q = Q + P với mọi P, Q ∈ E [Tính giao hoán].
Nói cách khác là luật cộng các điểm của E trong nhóm Aben.
Chứng minh. Luật đồng nhất (a) và luật nghịch đảo(b) là đúng bởi
vì O nằm trên tất cả các đường thẳng đứng. Luật giao hoán (d) là dễ
dàng chứng minh, vì một đường thẳng nối P và Q giống như đường
thẳng nối Q và P, vì vậy thứ tự các điểm không quan trọng.
Có rất nhiều cách chứng minh tính kết hợp, nhưng không có cách
chứng minh nào là dễ dàng. Sau khi chúng ta phát triển công thức rõ

ràng cho các luật cộng trên E (Định lý 2.2),chúng ta có thể sử dụng
những công thức để kiểm tra các luật kết hợp bằng trực tiếp.
Định lí 2.2.4. (Thuật toán Cộng trên đường cong elliptic). Để cho

E : Y 2 = X 3 + AX + B
Lê Thị Thu

16

K37C-SPT ĐHSP Hà Nội 2


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

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

là một đường cong elliptic và để P1 và P2 là điểm trên E .
a) Nếu P1 = O, thì P1 + P2 = P2 .
(b) Cách khác, nếu P2 = O, thìP1 + P2 = P1
(c) Cách khác, viết P1 = (x1 , y1 ) và P2 = (x2 , y2 )
(d) Nếu x1 = x2 và y1 = −y2 , thì P1 + P2 = O
(e) Cách khác, định nghĩa λ bởi

λ=

y2 −y1
x2 −x1
3x21 +A
2y1


, P1 = P2
, P1 = P2

và để cho

x3 = λ2 − x1 − x2 và y 3 = λ(x1 − x3 ) − y1 .
Thì P1 + P2 = (x3 , y3 ).
Chứng minh. Phần (a), (b) là hiển nhiên, và (d) là các trường hợp
đường thẳng đi qua P1 và P2 để P1 + P2 = O ( Lưu ý rằng nếu
y1 = y2 = 0 thì đường thẳng là đường tiếp tuyến, vì vậy trường
hợp này là quá nhiều). Để chứng minh (e), chúng ta chú ý rằng nếu
P1 = P2 , thì λ là hệ số góc của đường thẳng đi qua P1 và P2 , và nếu
P1 = P2 , thì λ là hệ số góc của đường tiếp tuyến tại P1 = P2 . Trong
cả hai trường hợp đường L được cho bởi phương trình Y = λX + v
với v = y1 − λx1 . Thay thế phương trình của L vào phương trình của
E
(λX + v)2 = X 3 + AX + B,
và

X3 − λ2 X 2 + (A − 2λv)X + (B − v 2 ) = 0.
Chúng ta biết rằng phương trình này có x1 và x2 là hai nghiệm của
nó. Nếu chúng ta gọi x3 là nghiệm thứ ba, sau đó nếu như

X 3 − λ2 X 2 + (A − 2λv)X + (B − v 2 ) = (X − x1 )(X − x2 )(X − x3 ).
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à −x1 − x2 − x3 , và bằng −λ2 là hệ số của X 2 ở vế trái.
Điều này cho chúng ta tính x3 = λ2 − x1 − 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 λx3 + v . Cuối
cùng, để có được P1 + P2 , chúng ta phải chiếu lên trục x có nghĩa là
thay thế các tọa độ y của nó.

Lê Thị Thu

17

K37C-SPT ĐHSP Hà Nội 2


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

2.2.2

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

Phép nhân

Phép nhân một số nguyên k với một điểm P thuộ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 ∈ E

nP = P + P + P + ... + P .
n số

2.3

Đường cong elliptic trên trường hữu hạn

Chúng ta đã phát triển lý thuyết về đường cong elliptic hình học. Ví
dụ, tổng của hai điểm phân biệt P và Q trên một đường cong elliptic
E được định nghĩa bằng cách vẽ đường thẳng L nối P và Q và tìm
điểm thứ ba mà L và E giao nhau. Tuy nhiên, để áp dụng các lý
thuyết về đường cong elliptic để mật mã, chúng ta cần phải tìm hiểu

những đường cong elliptic có điểm có tọa độ trong một trường hữu
hạn FP . Để đơn giản là xác định một đường cong elliptic trên FP là
một phương trình từ

E : Y2 = X 3 + AX + B

với A, B ∈ FP

điều kiện 4A3 + 27B 2 = 0,

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

E(FP ) = (x, y) : x, y ∈ FP , y 2 = x3 + Ax + B ∪ O .
Cho P = (x1 , y1 ) và Q = (x2 , y2 ) là hai điểm trên E(FP ). Tổng
của P1 + P2 là điểm (x3 , y3 ) thu được bằng cách áp dụng các thuật
toán Cộng đường cong elliptic(Định lý 2.2.4). Tuy nhiên, không thể
nói (x3 , y3 ) là một điểm trong E(FP ).
Định lí 2.3.1. Cho E là một đường cong elliptic 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( Định lý 2.2.4) áp
dụng cho P và Q mang lại một điểm trong E(FP ). Chúng ta ký hiệu
đ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(FP ) được liệt
kê trong định lý 2.2.3. Nói cách khác của luật bổ sung này làm cho
E(FP ) là một nhóm hữu hạn.
Lê Thị Thu

18

K37C-SPT ĐHSP Hà Nội 2



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

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

Ví dụ 6. Cho đường cong elliptic

E : Y 2 = X 3 + 3X + 8 trên F13
chúng ta sử dụng các thuật toán Cộng (Định lý 2.2.4) để cộng điểm
P = (9, 7) và Q = (1, 8) trong E(F13 )
Vì P = Q nên

λ=

1
1
y2 − y1
8−7
=
= = 8,
=
x2 − x1
1 − 9 −8 5

Tiếp theo chúng ta tính

v = y1 − λx1 = 7 − 8.9 = −65 = 0.
x3 = λ2 − x1 − x2 = 64 − 9 − 1 = 54 = 2,
y3 = −(λx3 + v) = −8.2 = −16 = 10.

Vậy

P + Q = (1, 8) + (9, 7) = (2, 10) trên E(F13 ).
Tương tự ,tính P + P , ta có

3x21 + A 3.92 + 3 246
λ=
=
=
= 1 và v = y1 −λx1 = 7−1.9 = 11.
2y1
2.7
14
Sau đó

x3 = λ2 −x1 −x2 = 1−9−9 = 9 và y3 = −(λx3 +v) = −1.9−11 = 6,
Vì P + P = (9, 7) + (9, 7) = (9, 6) trong E(F13 ). Chúng ta có thể
tính tổng của mỗi cặp điểm trong E(F13 ) .Các kết quả được liệt kê
trong bảng 2.1.

Lê Thị Thu

19

K37C-SPT ĐHSP Hà Nội 2


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

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


O
(1,5)
(1,8)
(2,3)
(2,10)
(9,6)
(9,7)
(12,2) (12,11)
O
O
(1,5)
(1,8)
(2,3)
(2,10)
(9,6)
(9,7)
(12,2) (12,11)
(1,5)
(1,5)
(2,10)
O
(1,8)
(9,7)
(2,3)
(12,2) (12,11) (9,6)
(1,8)
(1,8)
O
(2,3)

(9,6)
(1,5) (12,11) (2,10)
(9,7)
(12,2)
(2,3)
(2,3)
(1,8)
(9,6) (12,11)
O
(12,2)
(1,5)
(2,10)
(9,7)
(2,10) (2,10)
(9,7)
(1,5)
O
(12,2)
(1,8) (12,11) (9,6)
(2,3)
(9,6)
(9,6)
(2,3) (12,11) (12,2)
(1,8)
(9,7)
O
(1,5)
(2,10)
(9,7)
(9,7)

(12,2) (2,10)
(1,5) (12,11)
O
(9,6)
(2,3)
(1,8)
(12,2) (12,2) (12,11) (9,7)
(2,10)
(9,6)
(1,5)
(2,3)
(1,8)
O
(12,11) (12,11) (9,6)
(12,2)
(9,7)
(2,3)
(2,10)
(1,8)
O
(1,5)

Bảng 2.1 : Bảng phép cộng của E: Y 2 = X 3 + 3X + 8 trên F13

Y 2 = X 3 + AX + B
Định lí 2.3.2. (Hasse).Cho E là đường cong elliptic trên FP . Thì
√
E(FP ) = p + 1 − tp với tp thỏa mãn|tp | ≤ 2 p.
Số lượng điểm của E(FP ) là E(FP ) phải thỏa mãn định lý Hasse.
Định nghĩa 2.3.3. Bậc của đường cong elliptic là số điểm trên đường

cong đó. Bậc của điểm P ∈ E là số k thỏa mãn kP = O, khi k =
E(FP ) thì P là điểm cơ sở của E .

Lê Thị Thu

20

K37C-SPT ĐHSP Hà Nội 2


Chương 3
Hệ mật mã đường cong elliptic
3.1

Mở đầu

Năm 1976, Diffie và Hellman giới thiệu hệ mật mã hóa công khai đầu
tiên mà sự an toàn của nó dựa trên độ khó của bài toán DLP. Họ
đưa ra khái niệm hàm cửa sập một chiều(TOF). Năm 1985, Lenstra
thành công trong việc sử dụng đường cong elliptic trong các hệ mật
mã công khai.
Sau nhiều công trình nghiên cứu quan trọng thì các bài toán bài
toán phân tích số và bài toán logarit rời rạc tuy chưa giải được trong
thời gian đa thức nhưng cũng không cần đến thời gian hàm mũ để
giải nó, mà đã 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 thiệu
năm 1985. Dù cho những công trình này không làm các hệ mã sụp đổ,
nhưng nó buộc phép xây dựng các hệ mã phải giảm hiệu quả vì phải
dùng các khó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ã. Điề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ị thay thế 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 thể áp dụng được. Từ đó việc sử dụng
đường cong elliptic dẫn tới dẫn đến những hệ mã hiệu quả hơn (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
mũ).
Miller và Kobliz giới thiệu những hệ mật mã elliptic. Họ không
21


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

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

phát minh ra các thuật toán mới nhưng đã đóng góp lớn là chỉ ra viêc
áp dụng elliptic cho các hệ khóa công khai. Miller đề xuất mọi giao
thức trao đổi khóa tựa như Diffie - Hellman vào năm 1985. Kobliz đưa
ra thuật toán mã hóa tương tự như hệ ElGamal và Massey-Omura
vào năm 1987. Sơ đồ đầu tiên tương tự như RSA và hàm một chiều(có
cửa sập) mớ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 độ thực
hiện nhanh gấp 6 lần so với RSA). Cùng với thời điểm đó, Kaliski
chứng minh rằng các hàm cửa sập một chiều đòi hỏi thời gian là
hàm mũ để thực hiện phép tính nghịch đảo. Menezes, Okamoto và
Vanstone đã đưa ra một phương pháp tấn công MOV để giải bài toán
EDLP trong một số trường hợp riêng. Ngay sau đó, Miyaji đã tìm
được các điều kiện để tránh khỏi tấn công MOV và đề xuất một ứng

dụng thực tế của đường cong elliptic.
Năm 1993, Demytko đưa ra một thuật toán mới tương tự như RSA
cho các đường cong elliptic trên vành Zn vượt qua hạn chế của các
phiên bản trước, và Menezens và Vanstone đã đưa ra phương pháp
thực thi trên các thiết bị cứng có thể cải thiện các tính toán trên các
đường cong elliptic trên trường hữu hạn. Năm 1997,1998 việc tìm ra
các hệ mật mã trên đường cong elliptic ngày càng thu hút được nhiều
sự chú ý và một số các thuật toán đã được đưa ra.

3.2

Logarit rời rạc trên đường cong elliptic(ECDLP)

Định nghĩa 3.2.1. Cho E là một đường cong elliptic trên E(Fp ), và
với P và Q là hai điểm trên E(Fp ). Khi đó bài toán logarit rời rạc
trên E(Fp ), là bài toán tìm một số nguyên n sao cho Q = nP . Bằng
cách tương tự với bài toán logarit rời rạc trong FP∗ , chúng ta ký hiệu
số nguyên n bởi
n = logP (Q)
và chúng ta gọi n là logarit 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ó

logP (Q1 + Q2 ) = logP (Q1 ) + logP (Q2 ) với Q1 , Q2 ∈ E(Fp ). (3.1)
Thực tế logarit rời rạc trong E(Fp ) thỏa mãn (3.1) có nghĩa là nó
tuân theo luật Cộng khi nhóm E(Fp ) ánh xạ vào nhóm Z sZ. Chúng
Lê Thị Thu

22

K37C-SPT ĐHSP Hà Nội 2



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

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

ta nói ánh xạ logP xác định được gọi là đồng cấu nhóm

logP : E(Fp ) −→ Z/sZ.

3.3

Mật mã đường cong elliptic

Đó là thời gian để áp dụng các đường cong trong mật mã. Chúng ta
bắt đầu với các ứng dụng đơn giản nhất, Diffie-Hellman trao đổi khóa,
trong đó bao gồm thay thế các bài toán logarit rời rạc cho các trường
hữu hạn Fp bởi bài toán logarit rời rạc cho một đường cong elliptic
E(Fp ). Sau đó chúng tôi mô tả tương tự hệ mật mã hóa ElGamal trên
đường cong elliptic

3.3.1

Diffie- Hellman elliptic trao đổi khóa

Giả sử Alice và Bob muốn thống nhất một khóa chung để liên lạc có
bảo mật giữa hai người bằng mật mã. Trước hết hai bên thống nhất
công khai chọn một trường hữu hạn Fp và một đường cong elliptic E
trên đó khóa chung của họ sẽ được xây dựng từ một điểm ngẫu nhiên
P từ đường cong vừa cho, họ làm cách này bằng cách chọn tọa độ x

của P là ngẫu nhiên trong Fp .
Để tạo khóa, trước hết Alice đã chọn ngẫu nhiên một số nguyên
nA . Số nA được giữ bí mật. Trên cơ sở đó, Alice tính nA P ∈ E , nA P
được công khai. Đến lượt Bob cũng làm như vậy, anh ta chọn ngẫu
nhiên số nguyên nB là bí mật, tính nB P ∈ E và cũng được công khai.
Khóa bí mật mà chỉ có hai người mới có đó là

Q = (nA nB )P ∈ E.
Eve không thể suy ra (nA nB )P nếu không giải bài toán logarit rời rạc
trên E của trường Fp .
Ví dụ 7. Alice và Bob quyết định và sử dụng elliptic Diffie- Hellman
với các số nguyên , đường cong và điểm:
p = 3851, E: Y 2 = X 3 + 324X + 1287, P = (920, 303) ∈ E(F3851 ).
Alice và Bob chọn các giá trị bí mật tương ứng nA = 1194 và nB =
1759, và sau đó:
Alice tính QA = 1194P = (2067, 2178) ∈ E(F3851 ),
Lê Thị Thu

23

K37C-SPT ĐHSP Hà Nội 2


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

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

Bob tính QB = 1759P = (3684, 3125) ∈ E(F3851 ).
Alice gửi QA tới Bob và Bob gửi QB tới Alice. Cuối cùng,
Alice tính nA QB = 1194(3684, 3125) = (3347, 1242) ∈ E(F3851 ),

Bob tính nB QA = 1759(2067, 2178) = (3347, 1242) ∈ E(F3851 ).
Bob và Alice đã trao đổi bí mật điểm (3347, 1242)). Họ phải loại bỏ
các tọa độ y và chỉ có giá trị x = 3347 là một giá trị được chia sẻ bí
mật.
Định nghĩa 3.3.1. Cho E(Fp ) là một đường cong elliptic trên một
trường hữu hạn và để cho P ∈ E(Fp ). Các Bài toán đường cong
elliptic Diffie-Hellman là vấn đề tính toán giá trị của n1 n2 P từ giá
trị của n1 P và n2 P .

3.3.2

Hệ mật mã ElGamal trên đường cong elliptic

Alice và Bob đã thống nhất sử dụng một số nguyên tố p, một đường
cong elliptic E , và một điểm P ∈ E(Fp ). Alice đã chọn một khóa bí
mật nA là một số nguyên và QA = nA P là khóa công khai.
Khi đó hệ mã hóa đường cong elliptic được xây dựng tương tự hệ
mã hóa ElGamal, trong đó thuật toán mã hóa và giải mã được xác
định như sau:
Thuật toán mã hóa
Bod lấy một điểm M ∈ E(Fp ). Sau đó Bob đã chọn một số nguyên k
và gửi thông điệp mã hóa C1 , C2 và được tính như sau:

C1 = kP

và C2 = M + kQA

Thuật toán giải mã Bob đã gửi hai điểm (C1 , C2 ) tới Alice, sau
đó tính


C2 − nA C1 = (M + kQA ) − nA (kP ) = M + k(nA P ) − nA (kP ) = M.
để khôi phuc lại bản gốc.
Về nguyên tắc, các hệ thống mật mã ElGamal elliptic hoạt động
tốt nhưng có một số khó khăn thực tế.
1. Không có cách rõ ràng nào để đính kèm những thông tin của
văn bản gốc tới điểm E(Fp ).
2. Thuật toán ElGamal Elip mở rộng thông tin 4-1 so với tỉ lệ mở
rộng 2-1 của ElGamal khi sử dụng Fp .
Lê Thị Thu

24

K37C-SPT ĐHSP Hà Nội 2