Hệ mật mã dựa trên đường cong Elliptic

Công nghệ thông tin 
N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 224 
HỆ MẬT MÃ DỰA TRÊN ĐƯỜNG CONG ELLIPTIC 
Nguyễn Ánh Việt1*, Nguyễn Kim Tuấn2 
Tóm tắt: Các ý tưởng về an ninh thông tin dẫn đến sự phát triển của ngành mật 
mã học. Nói cách khác, mật mã học là “khoa học giữ an toàn thông tin”. Nó bao 
gồm việc mã hóa và giải mã các thông điệp. Mã hóa là quá trình chuyển đổi một 
văn bản đơn giản thành văn bản mật mã và giải mã là quá trình lấy lại thông điệp 
ban đầu từ văn bản mã hoá. Về mật mã học ngoài việc mang tính bảo mật, thì mang 
tính xác thực, tính toàn vẹn và tính chống chối bỏ. Mấu chốt của mật mã nằm trong 
khóa công khai và khóa bí mật của các khóa được sử dụng để mã hóa hoặc giải mã. 
Một yếu tố quan trọng khác là là kích thước của khóa sao cho khó có thể thực hiện 
giải mã theo cách thuần túy. 
Đã có nhiều thuật toán mật mã được gợi ý trong một số tài liệu về mật mã học. 
Trong bài báo này, chúng tôi nghiên cứu và phân tích các hệ thống mật mã dựa trên 
đường cong Elliptic (ECC) và đơn giản hóa thành những thuật toán gần với các 
ngôn ngữ đặc tả của chuyên ngành CNTT. Thuật toán mã hóa đường cong Elliptic 
đã được chứng minh là mạnh hơn các thuật toán đã biết như RSA / DSA. 
Từ khóa: Đường cong Elliptic; Hệ mật mã công khai; Elliptic Curve. 
1. MỞ ĐẦU 
Tháng 3 năm 2016, Bộ Ngoại Giao Hoa Kỳ, đứng đầu là bộ trưởng John Kerry, 
đã dẫn một đoàn đại biểu tới các nước ASEAN trong đó có Việt Nam để thảo luận 
về phát triển Fintech và đặc biệt là về công nghệ Blockchain. Tháng 9 năm 2015, 
ủy ban giao dịch hàng hoá tương lai Mỹ công bố, Bitcoin đã chính thức được đưa 
vào danh sách hàng hóa được phép giao dịch tại Mỹ. Công nghệ Blockchain và 
Bitcoin là công nghệ tiền số ra đời năm 2009 và ngày càng có nhiều quốc gia và 
các tổ chức, doanh nghiệp cho phép lưu hành và thanh toán bằng loại tiền số này 
trong không gian mạng Internet toàn cầu. Tháng 4-2016, giá trị thương mại của 
Bitcoin đã lên đến 6.5 tỷ USD. Nền tảng cơ sở của Bitcoin chính là lý thuyết về 
mât mã mà cụ thể ở đây là hàm băm và lý thuyết về chữ ký số dựa trên Hệ mât 
đường cong Elliptic (ECC). 
Bên cạnh việc sử dụng trong tiền số Bitcoin , ECC còn được ứng dụng rất nhiều 
trong thực tiễn ngành Công nghệ thông tin [1]. Các trang Web bảo mât https (http- 
secure) thường được dùng trong thanh toán điện tử hay ứng dụng riêng tư như 
gmail đều sử dụng các giao thức TLS (Transport Layer Security) mà trước đó là 
SSL (Secure Socket Layer). Trong các giao thức này ECC được sử dụng để trao 
đổi khóa phiên. Các giao dịch remote access được sử dụng rất nhiều trong thế 
giới Unix, Linux là SSH (Secure SHell) cũng sử dụng ECC để trao đổi khóa. Ưu 
điểm của hệ mật sử dụng đường cong Elliptic (ECC) là có độ dài khóa nhỏ (160 
bit tương đương với khóa độ dài 1024 Bit trong hệ mật RSA), do sử dụng độ dài 
khóa nhỏ nên tài nguyên phục vụ cho ECC thường nhỏ hơn rất nhiều, bên cạnh 
đó hiệu năng tính toán cũng được nâng cao rõ rệt. Hiện nay, ECC đang là xu thế 
để thay thế RSA. 
Cơ sở toán học của hệ mật ECC là nhóm giao hoán Abel các điểm nằm trên 
đường cong Elliptic. Ngoài việc đường cong Elliptic là cơ sở cho hệ mật ECC, hệ 
mật ID-Based, đường cong Elliptic (EC) còn là công cụ hữu hiệu để phân tích số 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 225
nguyên ra thừa cố nguyên tố [2, 3, 4], hoặc dùng để kiểm tra tính nguyên tố của số 
nguyên [3]. 
2. BÀI TOÁN LOGARITHM RỜI RẠC 
Định nghĩa 2. Bài toán Logarithm rời rạc trên đường cong Elliptic (ECDLP): 
Cho đường cong E trên trường hữu hạn Fq, điểm  ∈ () với bậc ( =  =
∞) và điểm  ∈ (), tìm số nguyên  ∈ [0,  − 1]sao cho Q = kP. Số nguyên k 
được gọi là Logarithm rời rạc của Q với cơ sở P, được viết là k = logP Q. 
Bất kỳ một hệ mật khóa công khai nào cũng phải sử dụng một bài toán khó để 
xây dựng hàm một chiều. Ý nghĩa một chiều ở đây có nghĩa là tính thuận thì dễ 
(thuật toán giải trong thời gian đa thức) và tính ngược thì khó (thuật toán giải với 
thời gian không phải là đa thức - thường là hàm mũ hoặc nửa mũ). Các tham số 
của Hệ mật dựa trên đường cong Elliptic (ECC) cần phải được lựa chọn cẩn thận 
để tránh được các tấn công đối với bài toán ECDLP. Thuật toán vét cạn để giải bài 
toán ECDLP là lần lượt tính thử các điểm P, 2P, 3P,... cho đến khi điểm mới tính 
được đúng bằng điểm Q. Trong trường hợp xấu nhất sẽ phải cần đến n bước thử, 
trung bình thường là n/2 là đạt được điểm Q, do đó cần phải chọn n đủ lớnđể bài 
toán vét cạn là không khả thi (n ≥ 2160). 
Thuật toán tốt nhất hiện nay để tấn công bài toán ECDLP là sự kết hợp của 
thuật toán Pohlih-Hellman và Pollard’s rho, thuật toán này có thời gian tính sẽ là 
(), với p là ước số nguyên tố lớn nhất của n, do đó, phải chọn số n sao cho 
nó chia hết số nguyên tố p lớn nhất có đủ lớn để giải bài toán này là không 
khả thi. 
Trong phần dưới đây, một số phương pháp tấn công bài toán Logarithm rời rạc 
sẽ được đề cập đến, đa số các phương pháp này có thể áp dụng được cho một 
nhóm bất kỳ. Chi tiết có thể tham khảo trong [3, 6, 8]. 
Cho Glà nhóm các điểm trên đường cong , ,  ∈  là các điểm trên đường 
cong E, chúng ta cần giải bài toán kP = Q, N là bậc của G. 
2.1. Phương pháp bước nhỏ, bước lớn 
Phương pháp này do Shanks đề xuất và được H. Cohen mô tả trong [9]. 
Thuật toán 2.1. Phương pháp bước nhỏ, bước lớn 
1. Chọn  ≥ √và tính mP. 
2. Tính và lưu trữ danh sách iP với 0 ≤ 
i < m 
3. Tính Q - jmP với j = 0,1,..., m - 1 
4. ifiP = Q - jmPthen 
5. k = i + jm( mod N) 
6. end if 
7. Quay về bước 3 
Dễ dàng nhận thấy Q = iP + jmPhay Q = (i + jm)P từ đó k = i + jm. Điểm iP 
được tính bằng cách cộng thêm P vào (i - 1)P đây được gọi là bước nhỏ. Q - jmP 
được tính bằng cách cộng thêm mP vào Q - (j - 1)mP và đây được gọi là bước lớn. 
2.2. Phương pháp Pollard’s  và λ 
Công nghệ thông tin 
N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 226 
Phương pháp này do Pollard đề xuất trong [10]. 
Định nghĩa hàm f : G → G một cách ngẫu nhiên Pi+i = f (Pi) với P0 cũng được 
chọn một cách ngẫu nhiên. Bởi vì G là tập hữu hạn do đó sẽ có các chỉ số i0< j0 
mà Pi0 = Pj0, từ đó ta có: 
Pi0 + 1 = f (Pi0 ) = f (Pj0 ) = Pj0 + 1 
Tương tự sẽ có Pi0+1 = Pj0+1 với l ≥ 0, từ đó, chuỗi Pi là chuỗi tuần hoàn với 
chu kỳ là j0- i0. Hàm biểu diễn chuỗi Pi thường giống chữ cái Hi Lạp  và đó là lý 
do tại sao phương pháp này có tên là phương pháp . 
Hàm f được chọn như sau: Chia tập G thành s tập con không trùng nhau Si, 
S2,..., Ss có kích thước tương đương nhau, s thường được chọn là 20, chọn 2s số 
ngẫu nhiên ai,bi mod N. Đặt: 
Mi = aiP + biQ 
Và định nghĩa: 
f(g) = g + Mi, ∈  
Biểu diễn Pj dưới dạng Pj = ujP + vjQ, khi Pi0= Pj0 ta có: 
uj0 P+ vj0 Q = ui0 P + vi0 Q 
(ui0- uj0)P = (vj0- vx’j0)Q 
k = (vj0 – vx’j0 )1(ui0 - uj0) mod N 
Phương pháp này cũng tương tự như phương pháp trên cần√ bước, tuy nhiên, 
không gian lưu trữ sẽ nhỏ hơn. 
2.3. Phương pháp Pohlig-Hellman 
Pohlig và Hellman đề xuất phương pháp này trong [11]. 
Nếu có thể phân tích bậc N của G thành các thừa số nguyên tố thì có thể viết: 
 =  


Ý tưởng của phương pháp này là tìm  ( 
 với mỗi i, sau đó áp dụng định 
lý Đồng dư Trung Hoa để tính k (mod N). Coi q là số nguyên tố và qe là lũy thừa e 
của q được chia hết bởi N, viết k dưới dạng sau: 
k = k0 + k1q + k2q
2 +  , 0 ≤ ki< q 
Lý giải thuật toán 2.3 như sau: 


 = 


 +  + ⋯  
= 


 +  +  + ⋯  = 


 
Bởi vì NP = ∞ và từ đây có thể tìm được k0. Tiếp theo: 
Qi = Q - k0P = (kiq + k2q
2 + ...) P 


 =


 +  + ⋯  
= 


 +  +  + ⋯  = 


 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 227
Từ đó tìm được k1, tương tự như vậy chúng ta sẽ tìm được k2, k3 ... Thuật toán sẽ 
dừng khi e = r + 1, khi đó N/qe+i không còn là số nguyên nữa và chúng ta không 
thể nhân Qe với một số hữu tỷ. 
Thuật toán 2.3. Phương pháp Pohlig-Hellman 
1. Tính  =  


 | 0 ≤  ≤  − 1, 
2. Tính 


, Đó là phần tử  


 của T. 
3. if e = 1 then 
4. Nhảy đến bước 15. 
5. end if 
6. Q1 ← Q ← k0P 
7. Tính 


. Đó là phần tử  


 của T. 
8. if e = 2 then 
9. Nhảy đến bước 15. 
10. end if 
11. Lần lượt tính được các giá trị k0, k1,  , kr-1 và Q0, Q1,  , Qr-1 
12. Qr ← Qr-1 – kr-1 q
r-1 P 
13. Xác định kr sao cho 


 =  


 
14. if e = r + 1 then 
15. k = k0 + k1q
2 + k2q
2 +  + ke-1q
e-1 ( mod qe ) 
16. Stop 
17. end if 
18. Quay về bước 11. 
2.4. Phương pháp tấn công MOV 
Tấn công MOV là tên viết tắt của các tác giả Menezes, Okamoto, và Vanstone 
[12], sử dụng cặp Weil để chuyển đổi bài toán Logarithm rời rạc trong () 
thành bài toán Logarithm rời rạc trong 
 . Bởi vì giải bài toán Logarithm rời rạc 
trong trường hữu hạn sẽ dễ dàng và nhanh hơn giải Logarithm rời rạc trong nhóm 
các điểm trên đường cong Elliptic. Chọn m sao cho: 
[] ⊆ 
 
Bởi vì tất cả các điểm trong E[N] đều có tọa độ trong  =∪ , nên m tồn 
tại. Theo định nghĩa về cặp Weil và các thuộc tính của cặp song tuyến tính: 
 = (, ) = (, ) = (, )
 = 
 
Thuật toán 2.4. Tấn công MOV 
1. Chọn điểm ngẫu nhiên  ∈ . 
2. Tính bậc M của T. 
3. Cho d = gcd(M, N) và cho T1 = (M|d)T có nghĩa là T1 có bậc là d, chia hết 
bởi N, do đó  ∈ []. 
4. Tính các cặp Weil  = (, ) và  = (, ). Cả hai ,  ∈  ⊆
 
× . 
228
như MOV, trong quá tr
đư
Định nghĩa 3.
1.
2.
3.
4.
5.
6.
và ký s
vi
ph
ph
4.1
[15]
X9.63 và IEEE P1363.
khai, hai bên cùng th
gửi giá trị 
gửi lại cho A. Khi đó
KB
tính đư
Đánh giá b
đư
truy
5.
6.
Các tham s
ợc mô tả trong chuẩn [13].
 B
 Phương 
 S là m
 Hai h
 P là m
 Đ
Bài báo s
ệc triển khai ứng dụng ECC. D. Hankerson 
ần mềm. L. Cao 
ần cứng.
. Trao đ
Năm 1998, Laurie và c
. Sau đó giao th
Hai bên 
 = d
ợc cả 2 khóa bí mật 
ền l
ậc c
các ph
cách ng
= x
ồ
B
ợc. Xem s
Giải b
Lặp lại với điểm ngẫu nhi
số 
3 + ax + 
ng h
ố c
dAP
à d
d là 
ủa trư
pháp bi
ần t
ầm đ
ẫu nhi
ệ số
ột đi
ệ
ẽ đề cập đến một số thuật toán ứng dụng trong trao đổi khóa, m
ơ b
ổi khóa Diffie
A 
dA
. D
ảo m
AP
ài toán Logarithm r
N
ố của hệ mật ECC cần đ
Tham s
ử
ư
 a,b
ể
 số
ản. Chuẩn do công ty 
và B c
P cho bên B, ngư
ễ d
 và 
, từ đó xác định đ
ờng
 củ
ợc sử dụng trong tr
∈
b).
m có b
 h = #E(
àng nh
ơ đ
ật
d

ể
a 
ên.

[14]
ức n
ần tạo khóa phi
ồ d
 : Đ
BP, khi bi
3. THAM S
ố h
q là q.
u di
q.
q đư
ậ

ỏa thuận điểm c
, khóa phiên c
ư
ể t
N. A. Vi
ình l
ệ m
ễn trư
ợc dùng đ
c nguyên t
q)/n.
 phân tích th
—
ày đ
ận thấy 
ới đây:
ìm 
dA,d
ựa chọn hệ ECC cần phải đạt đ
ật
Hellman ECDH
ộng sự đề xuất giao thức trao đổi khóa dựa tr
đư
B, trong khi ch
ết 
 D = (q, FR, S, a, b, P, n, h)
ờ
4. TRAO Đ
ã đư
ợc lại b
K
ợc khóa chia sẻ K
P, hacker bu
ệt, N. K. Tuấn, “Hệ mật m
ời rạc 
ên 
ược 
ng FR (field representation) đư
ể
ố
ợc đ
A 
T 
k (mod N)
Ố CỦA HỆ MẬT ECC
ường đ
 đ
 n và g
Certicom 
ực hiện 
ên bí m
ơ s
ủa b
= K

cho đ
ược
ịnh ngh
ưa vào 
ên B t
ên 
B, khóa này ch
=
ến khi bội số chung nhỏ nhất của các 
 l
ư
ọ
ỔI KHÓA
ở P
A 
ỉ có thể bắt đ


ựa chọn kỹ c
ờng cong Elliptic đ
ĩa đ
i là đi
các giao th
ật trao đổi trong một k
 trên 
ạo 
s
ộc phải giải b
 trong 
. 
xây d
[7]
các tiêu chu
khóa bí m
ẽ l
ườ
ểm cơ s
 phân tích tri
E. Bên 
à K
A ho

ng cong E trên
ựng [12] mô t
A = d
ỉ ri
ặc K
ã d

×
àng đ
ở
ức c
êng hai bên 
ư
ài toán Logarithm r
ựa tr
, sẽ tính đ
 là m
 P
ẩn ANSI X9.42, ANSI 
A 
ật 
Ad
B, hacker bu
ợc thông tin tr
ên đư
ể tránh các tấn công 
ư
ộ
 = (x
ơ b
tạo khóa bí mật 
dB
BP, và c
Công ngh
ợc một số ti
t t
ợc s
ược tạo ra một 
P
ển khai ECC bằng 
ản của ECC bằng 
 nhân v
ờng cong Elliptic.
ư
ập h
ử
 
,yP
ả chi tiết trong 
ênh truy
ủa b
ợc 
ợp g
 dụ
q (ngh
) ∈
ới 
A 
ộc phải t
ệ thông tin
k (mod N)
ng cho 
E(
P
ên B s
và B có th
ên đư
êu chí 
ồm:
ĩa l
q).
ên ECC 
ền công 
 sau đó 
à 
ã hóa 
dA 
ẽ l
ờng 
ời rạc 
”
. 
y2 
và 
à 
ể 
ìm 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 229
dA = logP (dAP) và dB = logP (dBP) và đây là bài toán khó không giải được trong 
thời gian đa thức. 
4.2. Tạo khóa bí mật chia sẻ ECMQV 
Tên đầy đủ của giao thức là Elliptic Curve Menezes-Qu-Vanstone. Thuật toán 
đã được đưa vào trong các chuẩn ANSI X9.63, IEEE 1363-2000, và ISO/IEC 
15946-3. Theo các tiêu chuẩn này điểm cơ sở được ký hiệu là G thay vì là P như 
thường gặp. Lược đồ này thường được sử dụng khi bân Avà B có cặp khóa công 
khai và bí mật cố định, tương ứng là (a, aG) và (c, cG). 
Bên A sinh cặp số ngẫu nhiên (b,bG) và bên B tương ứng sinh cặp số ngẫu (d, 
dG), và trao đổi 2 cặp nay cho nhau giá trị bG và dG. Kí hiệu hàm x :E → ℕ, lấy 
giá trị x của điểm trên đường cong E. 
Thuật toán 4.2: Tạo khóa bí mật chia sẻ ECMQV 
INPUT: Các tham số của hệ mật (K, E, q, h, G), các số a, b, aG, bG, cG và dG. 
OUTPUT: Khóa bí mật chia sẻ Q (chia sẻ với với đối tượng có khóa công khai cG) 
1. n ← [log2 (≠k)]/2. 
2. u ← (x(bG)(mod 2n) + 2n. 
3. s ← b + ua((mod q). 
4. v ← (x(dG)(mod 2n) + 2n. 
5. Q ← s(dG + v(cG)). 
6. if Q = ∞ then 
7. Quay lại bước 1. 
8. end if 
9. Trả về khóa Q. 
Bên B có thể tính ra cùng số Q bằng cách thay (a, b, c, d) trong thuật toán trên 
bằng (c, d, a, b). Bên A sẽ có các giá trị uA, vA, sA và bên B sẽ có uB, vB, sB. Dễ dàng 
nhận thấy: 
 uA = vB 
 uB = vA 
 QA= sA(dG + vA(cG)) = sA(d + vAc)G 
 = sA(d + uBc)G = sAsBG 
 QB= sB(bG + vB(aG)) = sB(b + vBa)G 
 = sB(b + uAa)G = sBsAG 
 QA= QB = Q 
Đánh giá bảo mật: Để hack được khóa chia sẻ, Hacker cần phải tính được các 
giá trị a, b, c, d muốn vậy Hacker phải giải các bài toán Logarithm rời rạc a = 
logG(aG), b = logG(bG), c = logG(cG), d = logG(dG). Đây là các bài toán khó 
không thể giải được trong thời gian đa thức tại thời điểm viết bài báo này. 
5. XÁC THỰC – CHỮ KÝ SỐ 
5.1. ECDSA(The Elliptic Curve Digital Signature Algorithm) 
Năm 1999, ECDSA(The Elliptic Curve Digital Signature Algorithm) đã được 
phê duyệt thành tiêu chuẩn của ANSI (ANSI X9.62-1998 ECDSA, phiên bản mới 
nhất là X9.62-2005), năm 2000 ECDSA cũng được IEEE và NIST phê duyệt thành 
tiêu chuẩn FIPS PUB 186-4 (Digital Signature Standard (DSS)), phiên bản mới 
Công nghệ thông tin 
N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 230 
nhất ban hành 7- ECDSA (The Elliptic Curve Digital Signature Algorithm) 2013. 
ISO năm 2002 cũng ban hành tiêu chuẩn ISO/IEC 159462:2002 trong đó có phần 
chuyên về ECDSA. Mô tả chi tiết về ECDSA có thể tìm thấy trong [16]. 
Người ký sẽ chọn số d làm khóa bí mật và tạo ra khóa công khai là Q = dP, sử 
dụng hàm băm H để tạo ra giá trị tóm lược văn bản e của văn bản m. Chữ ký số sẽ 
là cặp (r, s) được tính theo thuật toán 5.1. 
Thuật toán 5.1a: Sinh chữ ký số ECDSA 
INPUT: Tham số D = (q, FR. S, a,b,P,n,h), khóa bí mật d, thông điệp m. 
OUTPUT: Chữ ký số (r,s). 
1. Chọn ngẫu nhiên k ∈ [l,n- 1], 
2. R ← kP = (x1,y1) và chuyển đổi x1 ← 
3. r←(mod n). 
4. if r = 0 then 
Nhảy đến bước 1: 
5. end if 
6. e ← H(m). 
7. s ← k-1(e + dr) (mod n). 
8. if s = 0 then 
Nhảy đến bước 1: 
9. end if 
10. Trả về (r,s) 
Người nhận nhận được văn bản m' và chữ ký số (r, s) của người ký, sẽ tính giá 
trị tóm lược e' của văn bản nhận được là m' và áp dụng thuật toán 5.2 để xác định 
chữ ký số có phù hợp với văn bản nhận được hay không, từ đó, có thể khẳng định 
văn vản có do người ký ký thật hay không hoặc văn bản có bị sửa đổi hay bị lỗi do 
đường truyền hay không. 
Thuật toán 5.1b: Xác thực chữ ký số ECDSA 
INPUT: Tham số D = (q, FR, S, a,b, P, n, h), khóa công khai Q = dP, thông 
điệp nhận được m', chữ ký (r, s). 
OUTPUT: Chữ ký hợp lệ hoặc không hợp lệ. 
1. Kiểm tra r và s có phải là những số nguyên nằm trong khoảng [1,n-1], 
Nếukhông trả về return(“Chữ ký không hợp lệ”). 
2. e'←H (m’). 
3. w← s-1(mod n). 
4. u1← e’w(mod n) và u2← rw(mod n). 
5. R'←u1P + u2Q. 
6. ifR' = ∞then 
7. return(“Chữ ký không hợp lệ”). 
8. end if 
9. Chuyển đổi x1 của R’→ số nguyên  
10. r’←  (mod n). 
11. if r’ = rthen 
12. return (“Chữ ký hợp lệ”). 
13. else 
Thông tin khoa h
Tạp chí Nghi
m
ch
và khóa bí m
Logarithm r
đư
5.2
đã 
FIPS 
và công khai c
nguyên t
Thu
INPUT: Khóa bí m
OUTPUT: Ch
Thu
14.
15.
Ch
 hay 
N
ứng minh.
Đánh giá
ợc trong thời gian đa thức.
. Ch
D
đư
Đ
Có th
ật toán 5.2a: Sinh chữ ký số Elgamal
ật toán 5.2b: Xác thực chữ ký số Elgamal
INPUT: Khóa công khai 
OUTPUT: Ch
Ch
 return(“Ch
 end if
ứ
e = e'
ếu 
ựa tr
ợc đ
186 
ịnh nghĩa h
1. 
2. 
3. 
4. 
1.
2.
3.
4.
5.
6.
7.
ứng minh tính đúng đắn của thuật toán
ng minh tính đúng đ
e = e'
ữ ký số ElGamal
ên lư
ưa vào thành chu
[18]
ể chọn h
ố lớn..
Ch
R 
s = k
Tr
Vi =
ên c
ời rạc 
ọn ng
← Kp.
ả về (
Tính 
Tính 
ifV
return (“Ch
else
return (“Ch
end if
ọc công nghệ 
ứu KH&CN 
thì 
 ta s
bả
ật 
ợc đồ ký số do ElGamal đề xuất năm 1984 
. 
ủa ng
ữ ký số (
-1(m 
1 = V
 f (R)Y + sR = f (R)xP + k
ữ
r' = r
o m
d, đ
k = log
àm 
àm 
ẫu nhiên 
–
R,s
ữ ký hợp lệ hoặc không hợp lệ.
V1 
V2 
 ký
ẽ có 
ật
f như sau:
f (x,y) = x
ư
ật 
 xf 
) 
= f(R)Y + Sr
= m’V
2then
 không h
. Th
: Đ
ể t
ời ký l
x, thông đi
R,s
(R
ữ ký hợp lệ”).
ữ ký không hợp lệ”)
quân s
ực vậy:
R' = k(e + rd)(e + rd)
ể giả mạo đ
ìm 
P 

)).
ắn c
đư
R 
ẩn về chữ ký số DSS (Digital 
à 
). 
∈
Y = xP
ự, 
ợp lệ”).
ủ
ợc 2 giá trị n
và 
, trong đó x là s
(x, Y) | Y = xP. N
 [1
Số Đặc san 
a thu
d = log

ệp 
, 
. Thông đi
ược chữ ký, 
∶ 
m.
−
ật toán
P

1]
-1(m 
 Q 
||
, 
CNTT
 : c
ày 
và đây đ
→
ố nguy
ệp nhận đ
: khi 
— 
ần phải chứng minh rằng nếu 
Hacker 
Hacker 
 ℤ
xf (R))R = mP = m'P = V
, 12
-1P = kP = R
 là b
m'
 - 20
ều l
ên 
ậc của điểm P th
 = m:
17
c
bu
à 2 bài toán khó, chưa gi
Signature 
0 < x < q.
ược 
ần phải t
ộc phải giải 2 b
[17]
m’
, ch
 là đi
, phiên b
ữ ký (
ìm 
Standard) trong 
 Cặp khóa bí mật 
ều cần phải 
được giá trị 
ản sửa đổi 
ường l
R.s
2 
ài toán 
) 
231
m' = 
à s
k
ải 
ố 
232
tính đư
Hacker bu
toán không gi
6.1
[32]
ý ngh
Đánh giá
mA
rời rạc 
th
6.2
Ch
Đánh giá 
do đó
và đây là 
6.3
m
ISO/IEC 15946
Đánh giá b
. Mã hóa Massey
Massey
,m
ời gian đa thức.
. Mã hóa ElGamal
Trên cơ s
ứng minh tính đúng đắn của l
. Mã hóa ECIES (The Elliptic Curve Integrated En
ECIES do Bellare và Rogaway đ
ật ElGamal, sau đó
vào năm 1986. Lư
ĩa về mặt lịch sử.
B đ
m
, Hacker c
ợc 
ể t
A 
b
2
s bu
ộc phải giải b
-Omura là hai tác gi
bảo m
ìm 
= log
ở hệ mật ElGamal 
M = M
ảo m
 bài toán khó.
ả
ộc phải tính đ
ải đ
đư
-
o m
ư
ật
ợc các giá trị n
M M
2
ật: Đ
ần phải giải 2 b
3, IEEE P1363a và 
ật
ợc trong thời gian đa thức.
-
: Đ
1
 —
: Đ
Omura
ợc đồ m
ể phá khóa trong l
 và 
 XB
ể giải m
, thu
N. A. Vi
ể giả mạo chữ ký số, Hacker buộc phải tính đ
ài toán Logarithm r
m
 M
ật toán n
6. MÃ HÓA 
B = log
1 = M + kY
ược 
ả để xuất l
ã hóa này ít 
ày Hacker ph
[17]
ư
ã đư
ài toán Logarithm r
ệt, N. K. Tuấn, “Hệ mật m
k
Ml
, lư
ợc đồ m
ợc văn bản M, Hacker buộc phải t
ày đ
 và khóa bí m
 M
ề xuất v
[13]
ư
2, và đây là 2 bài toán chưa gi
ợc đồ m
B —
ã 
. 
– 
ược đồ m
đư
ợc đồ n
ã hóa
 X
đư
ời rạc 
GI
ợc sử dụng trong thực tế nh
ải lần l
B M
à là m
ợc đ
ẢI M
ã hóa 
: 
1
ưa vào các chu
ật 
k = log
ã hóa 
ày, Hacker ph
 = M + k(x
ời rạc 
ột biến thể của m
x, đ
à 
ượt giải 2 b
đư
ã d
ể tính đ
ợc phát biểu nh
k = log
cryption System)
ựa tr
PR
đư
B
ên đư
 và 
ợc
 P) 
Công ngh
ư
x
 mô t
ải t
ài toán Logarithm 
—
P 
ẩn ANSI X9.63 v
ờng cong Elliptic.
ợc 2 giá trị n
 = log
ìm 
 x
M1
ư
ả trong Patent 
đư
ải đ
ư sau:
B (kP) = M
ìm 
 và = 
ã hóa dùng h
ệ thông tin
ợc s m
P 
ưng nó có 
ợc giá t
ư
đư
Y, là bài 
ợc trong 
ợc 
log
à đ
k 
P Y
”
ể 
ày 
rị 
và
B, 
ệ 
à 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 233
Tham số D = (q, FR, S, a, b, P, n, h) được chọn tương tự như với ECDSA. ở 
đây cần lựa chọn thêm các hàm mã hóa/giải mã đối xứng ký hiệu là Ek (m) và Dk 
(c). Trong đó, m là bản rõ cần mã hóa, c là bản đã được mã. Thuật toán mã hóa đối 
xứng được chọn ở đây để phục vụ quá trình mã hóa/giải mã được dễ dàng hơn và 
nhanh hơn so với các thuật toán bất đối xứng. Ngoài ra, thay vì sử dụng hàm băm 
đơn giản, ECIES sẽ sử dụng hai hàm băm sau: 
• Message authentication code MACk (c): 
MAC : {0,1}n × {0,1}* → {0,1}n 
• Key derivation function KD(T,l): 
KD : E × ℕ → {0,1}* 
l là độ dài khóa (k1||k2). {0,1} là chuỗi bit có giá trị 0,1 có độ dài n hoặc không 
xác định. 
Người nhận có cặp khóa công khai/bí mật là (Y, x) trong đó Y = xP. 
Thuật toán 6.3a: Mã hóa ECIES 
INPUT: Văn bản cần mã hóa m, khóa công khai Y. 
OUTPUT: Văn bản đã được mã hóa (U, c, r). 
1. Chọn k ∈[1, q — 1]. 
2. U ← kP. 
3. T ← kY. 
4. (ki||k2) ← KD(T,l). 
5. Mã hóa văn bản, c ← Ekl (m). 
6. Tính giá trị MAC cho văn bản mã hóa r = MACk2 (C) 
Trả về return (U, c, r). 
Mỗi thành phần trong (U, c, r) đều có ý nghĩa quan trọng: 
• U cần thiết để tính khóa phiên Diffie-Hellman T. 
• c là bản đã được mã hóa. 
• r được dùng để xác thực mã văn bản. 
Thuật toán 6.3b: Giải mã ECIES 
INPUT: Văn bản mã hóa U.c.r. khóa bí mật x. 
OUTPUT: Văn bản đã giải mã m hoặc thông báo “văn bản mã không hợp 
lệ”. 
1. T ← xU. 
2. (k1||k2) ← KD (T,l). 
3. Giãi mã văn bản, m ← Dk1(c). 
4. ifr ≠ MACk2(C) then 
5. xuất thông báo “văn bản mã không hợp lệ” 
6. end if 
7. Trả về văn bản đã được giải mã m. 
Khóa phiên T sau khi được tính trong phần giải mã sẽ có giá trị giống như trong 
phần mã hóa. Thực vậy: 
TDecryption = xU = x(kP
) = k(xP) = kY = TEncryption 
Công nghệ thông tin 
N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 234 
Đánh giá bảo mật: Để phá khóa được lược đồ này Hacker cần phải tìm được khóa 
bí mật x hoặc giá trị k bằng cách giải bài toán x = logP Y hoặc k = logP U, và đây là 
2 bài toán khó chưa giải được trong thời gian đa thức. 
7. KẾT LUẬN 
Đường cong Elliptic là một trường hợp đặc biệt của phương trình Diophant. 
Lý thuyết về đường cong Elliptic (EC) rất phong phú và đồ sộ. Trong [5] tác giả 
Serge Lang đã phát biểu về phương diện học thuật: “Có thể viết vô tận về đường 
cong Elliptic”. 
Phạm vi của bài báo cũng được giới hạn với những khái niệm và lý thuyết đủ 
cho các ứng dụng cơ bản của EC, các phát triển của EC thành hệ mật ID-Based, 
hoặc các ứng dụng về chữ ký số tập thể, chữ ký số nhóm, chữ ký ngưỡng, chứ ký 
ủy nhiệm, chứ ký số mù sẽ không được đề cập đến trong khuôn khổ của bài báo 
này. Bài báo này có thể được sử dụng làm tài liệu tham khảo cho những người 
nghiên cứu về đường cong Elliptic trong lĩnh vực toán học cũng như Công nghệ 
thông tin. 
TÀI LIỆU THAM KHẢO 
[1]. J. W. Bos, J. A. Halderman, N. Heninger, J. Moore, M. Naehrig, and E. 
Wustrow, “Elliptic Curve Cryptography in Practice,” Financial Cryptography 
and Data Security, vol. 8437, pp. 157-175, 2014. 
[2]. J. H. Silverman and J. T. Tate, “Rational Points on Elliptic Curves - Second 
Edition”. Springer, 2015. 
[3]. L. C. Washington, “Elliptic Curves Number Theory and Cryptography, 
Second Edition”. CRC Press, 2008. 
[4]. J. W. S. Cassels, “Lectures on Elliptic Curves”. University of Cambridge, 1991. 
[5]. S. Lang, “Elliptic Curves Diophantine Analysis”. Springer, 1978. 
[6]. J. H. Silverman, “The Arithmetic of Elliptic Curves”. Springer, 2009. 
[7]. D. Hankerson, J. L. Hernandez, and A. Menezes, “Software Implementation 
of Elliptic Curve Cryptography over Binary Fields,” CHES2000, vol. 1965, 
pp. 243-267, 2000. 
[8]. I. Blake, G. Seroussi, and N. Smart, “Elliptic Curves in Cryptography”. 
Cambridge University Press, 1999. 
[9]. H. Cohen, “A Course in Computational Algebraic Number Theory”. Springer 
Verlag, 1993. 
[10]. J. M. Pollard, “Monte Carlo Methods for Index Computations (mod p),” 
Mathematics of Computation, vol. 32, no. 143, pp. 918-924, 1978. 
[11]. S. C. Pohlig and M. E. Hellman, “An Improved Algorithm for Computing 
Log¬arithms over GF(p) and its Cryptographic Significance,” IEEE 
Transactions on Information Theory, vol. 24, pp. 106-110, 1978. 
[12]. A. J. Menezes, T. Okamoto, and S. A. Vanstone, “Reducing elliptic curve 
logarithms to logarithms in a finite field,” IEEE Trans. Inform. Theory, vol. 
39, no. 5, pp. 1639-1646, 1993. 
[13]. C. Research, Standards For Efficient Cryptography, SEC 1: “Elliptic Curve 
Cryptography”. Certicom Corp, 2000. 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 235
[14]. L. Gao, S. Shrivastava, and G. E. Sobelman, “Elliptic Curve Scalar 
Multiplier Design Using FPGAs,” CHES’99, vol. 1717, pp. 257-268, 1999. 
[15]. L. Laurie, M. Alfred, Q. Minghua, S. Jerry, and V. Scott, “An Efficient 
Protocol for Authenticated Key Agreement,” Designs Codes and 
Cryptography, vol. 28, no. 2, 1998. 
[16]. D. Johnson, A. Menezes, and S. Vanstone, “The Elliptic Curve Digital 
Signature Algorithm (ECDSA),” 2001. 
[17]. T. E. Gamal, “A Public Key Cryptosystem and a Signature Scheme Based on 
Discrete Logarithms,” CRYPTO ’84, vol. 196, pp. 10-18, 1985. 
ABSTRACT 
ELLIPTIC CURVE CRYPTOGRAPHY 
The idea of information security lead to the evolution of Cryptography. In 
other words, Cryptography is the science of keeping information secure. It 
involves encryption and decryption of messages. Encryption is the process of 
converting a plain text into cipher text and decryption is the process of 
getting back the original message from the encrypted text. Cryptography, in 
addition to providing confidentiality, also provides Authentication, Integrity 
and Non-repudiation. The crux of cryptography lies in the key involved and 
the secrecy of the keys used to encrypt or decrypt. Another important factor 
is the key strength, i.e. the size of the key so that it is difficult to perform a 
brute force on the plain and cipher text and retrieve the key. There have been 
various cryptographic algorithms suggested. In this project we study and 
analyze the Elliptic Curve cryptosystems. This system has been proven to be 
stronger than known algorithms like RSA/DSA. 
Keywords: Cryptography, Public Key Systems, Elliptic Curve. 
Nhận bài ngày 16 tháng 8 năm 2017 
Hoàn thiện ngày 26 tháng 11 năm 2017 
Chấp nhận đăng ngày 28 tháng 11 năm 2017 
Địa chỉ: 1Viện CNTT – Viện KH&CN quân sự; 
 2Trường Đại học Lạc Hồng. 
 * Email: nguyenanhviet@hcmpreu.edu.vn.