ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

Đặng Thị Liên

NGHIÊN CỨU PHÁT TRIỂN MÃ HÓA TRÊN ĐƯỜNG CONG ELLIPTIC
DỰA TRÊN CHUỖI CƠ SỐ KÉP TỐI ƯU

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội - 2016


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

Đặng Thị Liên

NGHIÊN CỨU PHÁT TRIỂN MÃ HÓA TRÊN ĐƯỜNG CONG ELLIPTIC
DỰA TRÊN CHUỖI CƠ SỐ KÉP TỐI ƯU

Chuyên ngành: Cơ sở toán cho tin học
Mã số
: 60460110

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Hải Vinh


3
4
5
6
7
8
9

Kí hiệu
DBC
DBNS
EC
ECC
NAF
I
S
M
RSA

10

Ds

Dạng đầy đủ
Double Base Chains
Double Base Number System
Elliptic Curve
Elliptic Curve Cryptography
Non Adjacent Form
Field Inversions

1.1

Sơ lược về mật mã học . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2

Đường cong Elliptic trên trường nguyên tố hữu hạn . . . . . . . . . . . .

10

1.2.1

Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.2.2

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

12

1.2.3

Các phép toán trên đường cong Elliptic . . . . . . . . . . . . . . .

13



24

2.2

Một số phương pháp và chi phí tính phép nhân vô hướng trên đường cong
elliptic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.2.1

Phương pháp Double-and-Add . . . . . . . . . . . . . . . . . . .

24

2.2.2

Phương pháp sử dụng chuỗi hình thức không liền kề (NAF) . . .

27

2.2.3

Phương pháp sử dụng chuỗi cơ số kép tối ưu . . . . . . . . . . . .

30

Chương 3 Áp dụng tính toán thực tế
3.1

Chi phí của phương pháp sử dụng DBC trên miền Ds = {0, 1, −1} 54

3.2

Kết quả dựa trên cơ sở chạy chương trình . . . . . . . . . . . . . . . . . .

58

3.3

Ứng dụng mã hóa và giải mã đường cong Elliptic . . . . . . . . . . . . . .

59

3.3.1

Hệ mật mã khóa công khai ElGamal . . . . . . . . . . . . . . . .

60

3.3.2

Cài đặt chương trình sử dụng phương pháp ElGamal . . . . . . .

60

Kết luận

64


Thời gian tính toán của hệ này phụ thuộc mạnh mẽ vào biểu diễn của vô hướng r, các
biểu diễn thường gặp như là chuỗi nhị phân, chuỗi hình thức không liền kề, chuỗi cơ số
kép, ... Yêu cầu đặt ra đối với hệ mật mã dựa trên đường cong elliptic chính là giảm bớt
khó khăn trong phép tính Q = rS bởi với mỗi vô hướng r có nhiều cách để biểu diễn r
nên ta có được các phương pháp tính nhân vô hướng đặc trưng cho từng biểu diễn đó.
Để làm rõ vai trò của biểu diễn vô hướng r trên hệ ECC cũng như sự phát triển
các phương pháp thực hiện phép nhân vô hướng nhằm giảm chi phí, thời gian tính toán
của quá trình mã hóa, tôi quyết định chọn đề tài: "Nghiên cứu phát triển mã hóa trên
đường cong Elliptic dựa trên chuỗi cơ số kép tối ưu".
Đối tượng nghiên cứu của luận văn bao gồm cơ sở toán học hệ mật dựa trên đường
cong elliptic; các phương pháp và chi phí tính nhân vô hướng, tập trung vào phương pháp
sử dụng chuỗi cơ số kép tối ưu trên các miền Ds khác nhau.

5


Phạm vi nghiên cứu của luận văn: Dựa trên sách và các bài báo khoa học liên quan
đến hệ mật đường cong Elliptic, mà trọng tâm là bài báo "Fast Elliptic curve cryptography using optimal double - Base Chains" của nhóm tác giả Vorapong Suppakitpalsarn,
Masato Edahiro, Hiroshi Imai. Bài báo này đề xuất phương án sử dụng chuỗi cơ số kép
tối ưu để tính nhân vô hướng trên miền các miền Ds = {0, 1} và Ds = {0, 1, −1}
Kết quả của luận văn là nghiên cứu quá trình hoàn thiện mã hóa trên đường cong
Elliptic qua các phương pháp nhân vô hướng khác nhau. So sánh, đối chiếu các phương
pháp và từ đó rút ra được phương pháp nào là hiệu quả và tối ưu hơn. Ứng với mỗi phương
pháp này xây dựng chương trình minh họa cho nó.
Dựa vào mục đích, phạm vi, đối tượng nghiên cứu, luận văn được trình bày bao
gồm 3 chương chính cùng với phần mở đầu, kết luận và phụ lục:
• Chương 1: Cơ sở lý thuyết
• Chương 2: Một số phương pháp và chi phí tính phép nhân vô hướng trên đường cong

Elliptic

thường không nhất thiết phải giữ bí mật, mà cái luôn cần được giữ bí mật là khoá mật
mã. Trong thực tiễn, có những hoạt động ngược lại với hoạt động bảo mật là khám phá bí
mật từ các bản mã “lấy trộm” được, hoạt động này thường được gọi là mã thám hay phá
khoá [2]. Hiện nay, người ta chia hệ mật mã thành hai loại chính:
• Mật mã khóa đối xứng, hay còn gọi là mật mã khóa bí mật [3]
• Mật mã khóa bất đối xứng, hay còn gọi là mật mã khóa công khai [3]

Nhắc đến hệ mật mã khóa bí mật, ta thấy ưu điểm nổi trội của nó là việc dùng
chung một khóa để lập mã và giải mã được thực hiện nhanh chóng và đơn giản. Mặc dù
mã hóa đối xứng đã phát triển từ cổ điển đến hiện đại nhưng vẫn tồn tại hai điểm yếu
chính sau:
7


• Vấn đề trao đổi khóa giữa người gửi và người nhận: Cần có thêm một kênh an toàn

để trao đổi khóa sao cho khóa được giữ bí mật chỉ có người gửi và người nhận được
biết. Điều này trở nên cực kì khó khăn khi khối lượng thông tin truyền tải trên khắp
thế giới rất lớn. Việc thiết lập một kênh an toàn như vậy sẽ tốn kém về mặt chi phí
và chậm trễ về mặt thời gian.
• Tính bảo mật của khóa: Vì khóa được dùng chung cho cả người gửi và người nhận

nên khi khóa bị lộ không có cơ sở quy trách nhiệm cho người nào.
Để giải quyết vấn đề phân phối và thoả thuận khoá của mật mã khoá đối xứng,
năm 1976 Diffie và Hellman đã đưa ra khái niệm về hệ mật mã khoá công khai và một
phương pháp trao đổi công khai để tạo ra một khoá bí mật chung mà tính an toàn được
bảo đảm bởi độ khó của một bài toán toán học, cụ thể là bài toán tính logarit rời rạc [1].
Hệ mật mã khoá công khai hay còn được gọi là hệ mật mã phi đối xứng sử dụng một cặp
khoá, khoá mã hoá còn gọi là khoá công khai (public key) và khoá giải mã được gọi là
khoá bí mật hay khóa riêng (private key). Trong hệ mật này, khoá mã hoá khác với khoá


mod N

7. Việc giải mã thực hiện theo công thức:
M = D(C, KR ) = C d

mod N

Đối với phương pháp RSA, để đảm bảo an toàn, chúng ta phải chọn số N lớn (1024
bít) nên việc sinh khóa, lập mã và giải mã phức tạp, dẫn đến tốc độ thực hiện chậm. Để
khắc phục nhược điểm này, năm 1985, hai nhà khoa học Neal Koblitz và Victor S. Miller
đã độc lập nghiên cứu và đưa ra đề xuất ứng dụng lý thuyết toán học đường cong elliptic
(elliptic curve) trên trường hữu hạn [3] để xây dựng mã hóa dựa trên đường cong Elliptic.
Mã hóa đường cong elliptic giải quyết vấn đề của mã hóa RSA khi dùng các tham số có
kích thước ngắn hơn (168 bít) tuy nhiên vẫn đảm bảo độ an toàn như RSA 1024 bít. Ưu
điểm nổi bật của ECC là hệ mật mã này sử dụng khoá có độ dài nhỏ hơn so với RSA. Từ
đó làm tăng tốc độ xử lý một cách đáng kể, do số phép toán dùng để mã hoá và giải mã ít
hơn và yêu cầu các thiết bị có khả năng tính toán thấp hơn, nên giúp tăng tốc độ và làm
giảm năng lượng cần sử dụng trong quá trình mã hoá và giải mã. Sau đây, chúng ta sẽ
tìm hiểu chi tiết về lý thuyết toán học đường cong elliptic trên trường nguyên tố hữu hạn
và hệ mật mã dựa trên đường cong elliptic.

9


1.2

Đường cong Elliptic trên trường nguyên tố hữu hạn

Tính bảo mật của hệ thống mã hóa sử dụng đường cong elliptic dựa trên điểm

49 mod 23 = 739 mod 23 = 3

10


Khác với đường cong Elliptic trong trường số thực [1], chúng ta không thể biểu
diễn đường cong Elliptic E(Zp ) bằng đồ thị hàm số liên tục. Bảng bên dưới liệt kê các
điểm (x, y) của đường cong y 2 = x3 + x + 1 trong trường Z23 với a = 1, b = 1 như sau:
Bảng 1: Danh sách các điểm của đường cong y 2 mod 23 = x3 + x + 1 mod 23
(0, 1)

(6, 4)

(12, 19)

(0, 22)

(6, 19)

(13, 7)

(1, 7)

(7, 11)

(13, 16)

(1, 16)

(7, 12)


(19, 18)

Cũng tương tự khái niệm đối xứng qua trục hoành của đường cong Elliptic trên
trường số thực E (R), đường cong Elliptic trên trường nguyên tố hữu hạn E(Zp ) cũng đối
xứng theo nghĩa đối xứng modulo. Thật vậy, giả sử điểm (x, y) thuộc E(Zp ) thỏa mãn
(1.2.1) thì điểm (x, p − y) cũng thuộc (1.2.1) vì:
(p − y)2 mod p = p2 − 2py + y 2 mod p ≡ y 2 mod p

Ví dụ (1, 7) đối xứng với (1, 16) vì 7 + 16 = 0 mod 23 hoặc (3, 10) đối xứng với
(3, 13) vì 10 + 13 = 0 mod 23. Hình vẽ bên dưới minh họa tính đối xứng của các điểm
thuộc đường cong Elliptic trên trường nguyên tố hữu hạn:

11


Hình 1: Minh họa tính đối xứng trong Z23
Các điểm đối xứng với nhau qua đường y = 11.5 . Riêng điểm (4, 0) xem như là
đối xứng với chính nó.
1.2.2

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

• Nếu hai điểm P (x1 , y1 ) và Q(x2 , y2 ) (với x1 = x2 ) nằm trên cùng một đường cong

Elliptic (E), thì đường thẳng đi qua hai điểm P và Q sẽ cắt tại một điểm duy nhất
R(x3 , y3 ) nằm trên đường cong (E) đó, và R có thể xác định thông qua P và Q.
• Tiếp tuyến của đường cong tại một điểm bất kỳ P (x, y) trên đường cong (E) cũng

cắt (E) tại một điểm duy nhất trên (E), điểm này cũng có thể xác định thông qua P .

mod p

xQ − xP
2

 3xP + a mod p
2yP

nếu P = Q
nếu P = Q

Hình 3: Minh họa phép cộng điểm
Chú ý rằng các điểm (xR ; yR ) , (xR ; −yR )cùng nằm trên đường cong Elliptic và xét
về mặt hình học thì các điểm (xP ; yP ), (xQ ; yQ ) và (xR ; yR ) cùng nằm trên một đường
thẳng.
Ngoài ra, ta định nghĩa thêm: P + O = O + P = P
• Tính chất: Dễ thấy rằng: (E(Zp ), +) tạo thành nhóm Abelian:

– Tính đóng: Nếu P, Q ∈ E(Zp ) thì P + Q ∈ E(Zp )
14


– Tính kết hợp: Nếu ∀P, Q, R ∈ E(Zp ) thì P + (Q + R) = (P + Q) + R
– Tồn tại phần tử trung hòa O: ∀P ∈ E(Zp ) thì P + O = O + P = P (theo định
nghĩa)
– Tồn tại phần tử nghịch đảo: với mỗi P (x, y) ∈ E(Zp ) thì luôn tồn tại phần tử
−P (x, p − y) ∈ E(Zp ) , là điểm đối xứng của P để P + (−P ) = O
– Tính chất giao hoán: Nếu P, Q ∈ E(Zp ) thì P + Q = Q + P
Phép nhân điểm
• Phép nhân một số nguyên r với một điểm P ∈ (E) là điểm R ∈ (E) được xác định

phép toán số học (I, S, M ) trên trường nguyên tố hữu hạn của từng thuật toán.
• Phép toán trên điểm P + Q, 2P
Nếu P = Q thì chúng ta có phép toán cộng điểm P + Q. Nếu P = Q thì chúng ta có

phép toán nhân đôi điểm 2P .
– Phép cộng điểm: P + Q = R(x3 , y3 ), trong đó:
x3 = α2 − x1 − x2 (mod p)
y3 = (α (x1 − x3 ) − y1 ) (mod p)
y − y1
với α = 2
(mod p) = (y2 − y1 ) (x2 − x1 )−1 (mod p )
x2 − x1

– Phép nhân đôi điểm: 2P = R (x3 , y3 ), trong đó:
x3 = α2 − 2x1 (mod p)
y3 = (α (x1 − x3 ) − y1 ) (mod p)

với α =

3x21 + a
(mod p) =
2y1

3x21 + a (2y1 )−1 (mod p)

Từ tính chất và phân tích trên dẫn đến thuật toán sau [6]:
16


Thuật toán 1 : Cộng, nhân 2 điểm

1I + 2S + 2M
1I + 1S + 2M

P +Q:
• Phép toán trên điểm 2P + Q

– Ta có: P (x1 , y1 ), Q(x2 , y2 ) với x1 = x2 thì tính ∆1 =
với:

y2 − y1
, và P +Q = (x3 , y3 )
x2 − x 1

x3 = ∆21 − x1 − x2 , y3 = ∆1 (x1 − x3 ) − y1

Tính S = 2P + Q = P + (P + Q) = (x4 , y4 )
y3 − y1
(∆1 (x1 − x3 ) − y1 ) − y1
2y1
=
=
− ∆1
x3 − x1
x3 − x1
x1 − x3
x4 = ∆22 − x1 − x3 = ∆22 − x1 − ∆21 + x1 + x2 = ∆22 − ∆21 + x2 =

Ta có: ∆2 =

(∆2 − ∆1 )(∆2 + ∆1 ) + x2

1
= dD−1 = dI
x2 − x1
1
(x2 − x1 )2
(x2 − x1 )3
=
=
= (x2 − x1 )3 I
x1 − x3
d
D

Từ phân tích ở trên ta có được thuật toán sau [6]:
Thuật toán 2: Tính 2P + Q
Input: P (x1 , y1 ), Q(x2 , y2 ) ∈ E(Zp )
Output: S(x4 , y4 ) = 2P + Q
1: if (x1 = x2 ) then
2:
(y1 = y2 ) then return 3P else return P
3: A ← (x2 − x1 )2 (mod p), B ← (y2 − y1 )2 (mod
SS
p)
4: d ← (A (2x1 + x2 ) − B) (mod p)
M
5: if (d = 0) then return O
6: D ← (d (x2 − x1 )) (mod p) ,I ← D−1 (mod p)
MI
7: ∆1 ← (dI (y2 − y1 )) (mod p)
MM

(∆1 (x1 − x3 ) − y1 ) − y1
2y1
=
=
− ∆1
x3 − x1
x3 − x1
x1 − x3

x4 = ∆22 −x1 −x3 = ∆22 −x1 −∆21 +2x1 = ∆22 −∆21 +x1 = (∆2 −∆1 )(∆2 +∆1 )+x1
y4 = (x1 − x4 )∆2 − y1

– Biến đổi,
từ công thức: x4 = (∆2 − ∆1 )(∆2 + ∆1 ) + x2
2y1


− ∆1
∆2 =


x1 − x3

ta thấy: x3 = ∆21 − 2x1


3x2 + a


∆1 = 1

19

SSS
M


5: D ← (d(2y1 )) (mod p), I ← D−1 (mod p)
6: ∆1 ← (dIB) (mod p)
7: ∆2 ← A2 I − ∆1 (mod p)
8: x4 ← ((∆2 − ∆1 )(∆2 + ∆1 ) + x1 ) (mod p)
9: y4 ← ((x1 − x4 )∆2 − y1 ) (mod p)
10: return (x4 , y4 )
Tổng

MI
MM
SM
M
M
1I + 4S + 7M

Như vậy, P + Q, 2P , 2P + Q, 3P là một số các phép toán trên điểm cơ bản
của EC. Sau mỗi thuật toán nêu ở trên ta đếm được số phép toán số học của trường
nguyên tố hữu hạn theo (I, S, M ). Mặt khác, các phép toán trên điểm cơ bản nêu trên
được áp dụng để tính nhân vô hướng Q = rP . Muốn biết được đâu là phương pháp
tốt nhất thì ta phải biết được tổng số phép toán trên điểm để tính tổng chi phí tính
toán của mỗi phương pháp. Vì vậy, trong trường nguyên tố hữu hạn ta gọi chi phí
các phép toán trên điểm như sau:
– Phép nghịch đảo - I có chi phí [i]
– Phép bình phương - S có chi phí [s]

Q = P + P + · · · + P = rP

(điểm Q là tổng của r điểm P , r < p )
20


Cho trước r và P , việc tính Q thực hiện rất dễ dàng. Tuy nhiên nếu cho trước P và
Q, việc tìm ra r là công việc khó khăn. Đây chính là hàm logarit rời rạc của đường cong
Elliptic. Ví dụ:
Xét nhóm E23 (9, 17) với phương trình:
y 2 mod 23 = (x2 + 9x + 17) mod 23

a, b, x, y ∈ Z23

Cho điểm P = (16, 5), Q = (4, 5), chúng ta chỉ có cách là vét cạn các giá trị của r
từ 2 đến p − 1 để tìm ra r:
P = (16, 5); 2P = (20, 20); 3P = (14, 14); 4P = (19, 20); 5P = (13, 10); 6P = (7, 3); 7P =
(8, 7); 8P = (12, 17); 9P = (4, 5)

Vì 9P = Q nên ta xác định được r = 9. Trong thực tế chúng ta sẽ sử dụng đường
cong elliptic Zp với giá trị p lớn, sao cho việc vét cạn là bất khả thi. Hiện nay, người ta đã
tìm ra phương pháp tìm r nhanh hơn vét cạn là phương pháp Pollar rho.
Như vậy, ECC thực hiện việc mã hóa và giải mã dựa trên tọa độ của các điểm nằm
trên EC và tính nhân vô hướng Q = rP với P, Q là các điểm trên đường cong E(Zp ), r
là số nguyên dương. Khi đó r được gọi là logarit cơ sở của P và Q. Bài toán tính logarit
rời rạc theo modulo nguyên tố của các điểm trên đường cong đòi hỏi thời gian mũ. Từ
đó, các hệ mã hóa công khai sử dụng đường cong Elliptic dựa trên độ phức tạp của thuật
toán tìm logarit, trong đó: r là khóa bí mật, Q là khóa công khai và P được dùng làm "cơ
sở".
Mô hình mã hóa dữ liệu sử dụng đường cong elliptic (Elliptic Curve Encryption

6. B tính giá trị C = Ø(Y, M ). C chính là thông điệp đã được mã hóa. Thông thường
Ø(Y, M ) = Y

M

7. B gửi cho A thông điệp đã mã hóa C cùng với giá trị (x1 , y1 )
- Giá trị k và (x1 , y1 ) được tạo ra không phải khóa riêng và khóa công khai để giao
dịch của B. Đây là cặp khóa công khai - khóa bí mật được phát sinh nhất thời nhằm
mã hóa thông điệp. Mỗi một thông điệp mã hóa nên sử dụng một cặp khóa công
khai - khóa bí mật được phát sinh ngẫu nhiên.
1.3.2

Quá trình giải mã

Bằng việc sử dụng các tham số quy ước kết hợp với khóa bí mật r của người nhận A và
giá trị (x1 , y1 ), A thực hiện giải mã thông điệp được mã hóa bằng ECES (C) theo trình tự
sau:
1. A nhận giá trị (x1 , y1 )
2. A tính giá trị của điểm (x2 , y2 ) = d · (x1 , y1 ). x2 là giá trị bí mật sẽ được sử dụng để
tạo khóa giải mã thông điệp.
22


3. Sử dụng cùng một hàm tạo mặt nạ (mask function) như đã sử dụng ở giai đoạn mã
hóa, A tạo mặt nạ Y từ giá trị bí mật x2 . Y chính là khóa bí mật để giải mã.
4. A giải mã thông điệp C để lấy thông điệp M ban đầu bằng cách tính giá trị M =
Ø−1 (C, Y ). Thông thường, Ø−1 (C, Y ) = C
Y.
Dựa vào chi phí tính toán để thực hiện tính nhân vô hướng Q = rP thông qua chi
phí của các phép toán trên điểm được trình bày ở phần trên kết hợp với trình tự mã hóa