Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)

Xây dựng lược đồ dùng hệ mật định danh
dựa trên đường cong Elliptic
Nguyễn Thùy Dung
Khoa Công nghệ Thông tin,
Trường Đại học kinh tế- kỹ thuật công nghiệp
Email:
Abstract— Hệ mật định danh hiện nay đang được
xem là hệ mật mã mới có nhiều thuận lợi so với các
hệ mật mã khác. Hệ mật định danh dùng khóa cơng
khai và được sử dụng rộng rãi, hệ mật này cho phép
một người sử dụng tính khố cơng khai từ một chuỗi
bất kỳ. Chuỗi này như là biểu diễn định danh và
được sử dụng để tính khố cơng khai, có thể chứa
thơng tin về thời hạn hợp lệ của khoá để tránh cho
một người sử dụng dùng một khoá trong thời gian
dài hoặc cho phép một người sử dụng tính khố cơng
khai từ một chuỗi bất kỳ. Bài báo đề xuất mã hóa và
giải mã dùng hệ mật định danh dựa trên đường
cong Elliptic.
Keywords- Hệ mật định danh , mã hóa và giải mã,
đường cong Elliptic.
I.

Hình 1: Đồ thị biểu diễn đường cong elliptic dạng
𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏
Hệ mật định danh lần đầu tiên được công bố bởi Shamir
vào năm 1984 [1], ưu điểm chính của hệ mật định
danhlà khơng cần phải xác thực khóa cơng khai, khóa
này được dẫn xuất từ địa chỉ ID, địa chỉ email hay số

chứng minh thư của người sử dụng. Đã có nhiều lược đồ
chữ ký số tập thể hoặc tương đương được đề xuất dựa
trên hệ mật định danh[2], [3] hoặc [4], [5]. Bài báo này
đề xuất mã hóa và giải mã dùng hệ mật định danhdựa
trên đường cong Elliptic.

GIỚI THIỆU

Mật mã đường cong Eliptic (ECC) là mã hóa khóa
cơng khai dựa trên cấu trúc đại số của các đường cong
Ellip trên trường hữu hạn. Độ an tồn của ECC dựa vào
bài tốn logarit rời rạc trên nhóm các điểm của đường
cong elliptic (ECDLP). Hiện nay, đối với bài toán
ECDLP cho đến nay vẫn chưa tìm được thuật tốn dưới
hàm mũ để giải.
Đường cong elliptic có tính an tồn tương đương với
các hệ mật khóa cơng khai truyền thống, trong khi độ dài
khóa nhỏ hơn nhiều lần. Ví dụ cỡ khố 3248 bit của hệ
mật RSA cho cùng một độ an toàn như 256 bit của hệ
mật ECC. Cho nên mật mã đường cong Eliptic ECC sử
dụng ít tài nguyên hệ thống hơn, năng lượng tiêu thụ nhỏ
hơn.... Với ưu thế về độ dài khóa nhỏ, ECC đang được
ứng dụng rộng rãi trong nhiều lĩnh vực.
Đường cong elliptic là tập hợp các điểm thỏa mãn
một phương trình tốn học cụ thể. Phương trình cho một
đường cong elliptic:
𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏
(1)
Đồ thị được biểu diễn như sau:


ISBN 978-604-80-5958-3

II.

CƠ SỞ TOÁN HỌC

2.1 Đường cong Elliptic trên trường hữu hạn
2.1.1 Trường hữu hạn 𝐹𝑞 với 𝑞 là số nguyên tố
Đường cong elliptic trên trường Fq (p là số nguyên tố).
Cho p là số nguyên tố (p > 3), cho a, b  Fp sao cho
4a3 + 27b 2 ≠ 0 trong trường Fp .
Một đường cong elliptic E trên 𝔽q (được định nghĩa bởi
các tham số a và b) là một tập hợp các cặp giá trị (x, y)
(x, y  𝔽q ) thỏa mãn công thức:
y 2 = x 3 + ax + b
cùng với điểm O đặc biệt gọi là điểm vơ cực và có thể
biểu diễn dưới dạng:
O = (x, ∞).
(2)
Số lượng điểm của E (𝔽q ) (là ≠ E(𝔽q ) thỏa mãn định lý
Hasse.
Độ phức tạp của thuật tốn xây dựng trên nhóm đường
cong Elliptic phụ thuộc vào số điểm trên đường cong đó.
Bậc của điểm : Cho điểm P(x, y) thuộc đường cong
Elliptic. Bậc n của điểm P(x, y) là số nguyên dương thỏa
mãn biểu thức:
nP = O.
(3)
2.1.2 Đường cong elliptic trên trường 𝔽m
2


32


Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2021)

Một đường cong elliptic E( 𝔽2m ) được định nghĩa bởi
các tham số a, b  𝔽2m (với b ≠ 0) là tập các điểm
P(x, y) với x, y ∈ 𝔽2m ; thỏa mãn công thức:
y 2 + xy = x 3 + ax 2 + b
(4)
Cùng với điểm O là điểm tại vô cực.
Số lượng các điểm thuộc E( m 𝔽 2 ) ký hiệu ≠ E( m 𝔽 2 )
thoả mãn định lý Hasse: q + 1 2 √q ≤ #E(𝔽 q ) ≤
q + 1 + 2 √q trong đó p = 2m .

𝐶 = (𝑟𝑃, 𝑀 ⊕ 𝐻2 (𝑒(𝑟𝑄𝐼𝐷 , 𝑠𝑃)) = (𝐶1 , 𝐶2 ) (10)
Thực hiện những bước sau:
1. Tính
𝐾 = 𝐻2 (𝑒(𝑠𝑄𝐼𝐷 , 𝐶1 ))
(11)
từ thành phần bản mã 𝐶1 và khóa riêng 𝑠𝑄𝐼𝐷
2.
3.

Ngồi ra, E( 𝔽2m )là số chẵn.
Tập hợp các điểm trên E( 𝔽2m )tạo thành một nhóm thỏa
mãn các tính chất sau: O + O = O.
(x, y) + O = (x, y), (x, y)  E( 𝔽2m )
(x, y) + (x , − y) = O, (x, y)  E( 𝔽2m )

Khi đó, (x, − y) là điểm đối của (x, y) trên E( 𝔽2m ).
III.

3.2 Chứng minh tính đúng đắn của lược đồ đề xuất
3.2.1 Chứng minh luôn tồn tại 1 điểm p trên đường cong
Elliptic
Giả sử E là đường cong Elliptic E(𝔽q ), với dạng:
y2 = x3 + 1
Với q là 1 số nguyên tố: q ≡ 11(mod 12) và G1 là
nhóm nhỏ của p ∈ E(𝔽q ).
Ta dùng hàm băm:
H1 ∶ {0,1}∗ → G1
Bước 1: Lấy Q ∈ E(𝔽q ) và lấy tọa độ x, y trên đường
cong Elliptic thỏa mãn:
1
x = (y 2 − 1) ⁄3
(14)
Áp dụng định lý Euler ta có:
aq−1 ≡ 1 (mod q)
(15)
a2q−1 ≡ a (mod q)

LƯỢC ĐỒ ĐỀ XUẤT

3.1. Lược đồ mã hóa và giải mã
3.1.1. Sinh số
Gọi G1 là nhóm cộng cyclic có bậc là số nguyên tố q và
phần tử sinh là P. GT là nhóm nhân cyclic có cùng bậc
q. e là cặp song ánh:
e: G1 × G1 → GT

(5)
Với k là khóa bí mật, thỏa mãn điều kiện p là 1 số
nguyên tố.
p|# E(𝔽q )
p2 χ ≠ E(𝔽q )
Trong đó: p ∈ G1 và GT ∈ 𝔽∗qk
Chọn 1 điểm bất kỳ trên đường cong Elliptic
P ∈ E(𝔽q )[p] ;
G1 = 〈P〉
GT = 〈e(P, P)〉
(6)
Chọn số nguyên ngẫu nhiên thỏa mãn:
s ∈ ℤp∗ (Dùng để tính sP)
Ánh xạ ID đến một điểm Q ID , ở đây dùng hàm băm.
H1 , H2 là các hàm băm được sử dụng cho mục đích bảo
mật và được định nghĩa như sau: H1 ∶ {0,1}∗ →
G1 ; H2 ∶ GT → {0,1}n
Công bố tham số của hệ thống là:
Params = (n, e, q, G1 , GT , H1 , H2 , sP)

(2q−1)

1

⁄3
a
≡ a ⁄3 (mod q)
Ta có: 3|(2q − 1)khi q ≡ 11(mod 12)
Từ đây tính tọa độ x của điểm Q:
Q ID ∈ E(𝔽q )[p]

Sau đó nhân với 1 hằng số ta có:

Q ID =
Q ID =

≠E(𝔽q )
p

.Q

(16)

q+1
.Q
p

Vì:
p|# E(𝔽q )
p2 χ ≠ E(𝔽q )
Cho nên luôn tồn tại:
p ∈ E(𝔽q )
Khi:
Q ID ∈ G1

3.1.2. Mã hóa
1. Q ID = H1 (ID)
(7)
2. Tính khóa riêng bằng cách lấy Q ID × s ta
được: sQ ID
3. Tạo 1 số nguyên ngẫu nhiên thỏa mãn:

r ∈ ℤ∗p và tính rP
4. Tính K ta có Q ID = H1 (ID)
Nên: K = H2 (e(rQ ID , sP))
(8)
Đặt bản mã tương ứng với cặp C ta có:
C = (C1 , C2 )
(9)
Trong đó: C1 = rP ; C2 = M ⊕ K

3.2.2 Ví dụ
Giả sử E là đường cong Elliptic: E/(𝔽131 ) với dạng:
y2 = x3 + 1
Và:
P = (98,58) ∈ E(𝔽131 ) [11]
G1 = 〈P〉
GT = 〈e(P, P)〉
Gọi G1 là nhóm cộng cyclic có bậc là số nguyên tố q và
phần tử sinh là P. GT là nhóm nhân cyclic có cùng bậc
q. e là cặp song ánh:

3.1.3 Giải mã
Khi người nhận được bản mã:

ISBN 978-604-80-5958-3

Tính M = C2 ⊕ K
(12)
Ta thay C1 vào tính K ta có:
rs
K = H2 (e(rQ ID , sP)) = H2 (e(Q ID , sP))

= H2 (e(rQ ID , C1 )) = H2 (e(Q ID , P))rs (13)

33


Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thơng và Cơng nghệ Thơng tin (REV-ECIT2021)

e: G1 × G1 → GT = e(P, ∅Q)1560
Khi ∅ (x, y) = (ξx, y) với ξ = 65 + 112i
Chọn: s = 7; sP = (33,100)
Q ID = H2 (IDB ) = (128,57)
sQ ID = (113,8)
Mã hóa với: s = 7;
rQ ID = (5)(128,57) = (98,73)
∗
Và: r = 5 ∈ ℤ11
cho nên : rP = 5P = (34,23)
Tính:
K = H2 (e(rQ ID , sP)) = H2 (e(98,73), ( 33,100))
= H2 (49 + 58i)
Mà:
C1 = rP ;
Cho nên:
K = H2 (e(sQ ID , C1 ))
= H2 (e(113,8), ( 34,23))
= H2 (49 + 58i)
Khi đó: C2 = M ⊕ K = (M ⊕ K) ⊕ K = M

(18)
(1) Chuỗi 𝑙 = 𝑙(𝑘) văn bản 𝑚1 , . . . , 𝑚𝑙 được chọn một

cách ngẫu nhiên trong không gian 𝑀𝑘
(2) Thực hiện các thuật toán trong lược đồ để tạo ra
chữ ký 𝛼𝑝𝑢𝑏 𝑖 .
𝑚

(3) Thuật toán 𝓐 với đầu vào là 𝑃𝐾𝑝𝑢𝑏 ,
{𝑚𝑖𝑚 , 𝛼𝑝𝑢𝑏 𝑖 )} sẽ cho ra (𝑚, 𝛼𝑝𝑢𝑏 ).
𝑚

(4) Thực nghiệm tấn công thành công nếu 1 ←
𝑽𝒆𝒓𝒊𝒇𝒚𝑷𝒖𝒃(𝑃𝐾𝑝𝑢𝑏 , 𝑚, 𝛼𝑝𝑢𝑏 , ‫𝑣 )ﬠ‬à 𝑚 ≠ 𝑚𝑖𝑚 .
C, Tấn cơng ACMA - Adaptive Chosen Message
Attacks
Đây là loại hình tấn cơng mạnh nhất, người tấn cơng có
thể được lựa chọn văn bản để ký phụ thuộc vào khóa
cơng khai cũng như những chữ ký số có từ trước đó. Có
thể biểu diễn việc này thông qua khả năng truy cập đến
hàm Oracle, ký hiệu là 𝑆𝑖𝑔𝑛(·)𝑠𝑘 .
Lược đồ đề xuất được cho là không thể giả mạo với tấn
công 𝐴𝐶𝑀𝐴 khi với mọi thuật toán thời gian đa thức
của người tấn công 𝓐, xác suất thành công của thực
nghiệm dưới đây là một hàm nhỏ không đáng kể:

Lược đồ đề xuất chống lại được các loại hình tấn
cơng chữ ký số tập thể đa thành phần cụ thể là:
A, Tấn công RMA - Random Message Attacks
Lược đồ đề xuất được coi là không thể giả mạo nếu
với mọi đa thức 𝑙(·) và với mọi thuật toán thời gian đa
thức của người tấn công 𝓐 , xác suất thành công là
một hàm nhỏ không đáng kể:


(19)
(1) Chuỗi 𝑙 = 𝑙(𝑘) văn bản 𝑚1 , . . . , 𝑚𝑙 được chọn một
cách ngẫu nhiên trong không gian 𝑀𝑘
(2) Thực hiện các thuật toán trong lược đồ để tạo ra
chữ ký 𝛼𝑝𝑢𝑏 𝑖 .

(17)
(1) Chuỗi 𝑙 = 𝑙(𝑘) văn bản 𝑚1 , . . . , 𝑚𝑙 được chọn một
cách ngẫu nhiên trong khơng gian 𝑀𝑘
(2) Thực hiện các thuật tốn trong lược đồ để tạo ra
chữ ký 𝛼𝑝𝑢𝑏 𝑖 .

𝑚

(3) Thuật tốn 𝓐 với đầu vào là 𝑃𝐾𝑝𝑢𝑏 và có thể truy
cập đến 𝑆𝑖𝑔𝑛(·)𝑠𝑘 với một số văn bản bất kỳ và sẽ cho
ra chữ ký số (𝑚, 𝛼𝑝𝑢𝑏 ). Không gian các văn bản truy
vấn này gọi là 𝑀.
(4) Thực nghiệm tấn công thành công nếu
1 ← 𝑽𝒆𝒓𝒊𝒇𝒚𝑷𝒖𝒃(𝑃𝐾𝑝𝑢𝑏 , 𝑚, 𝛼𝑝𝑢𝑏 , ‫𝑣 )ﬠ‬à 𝑚 ≠ 𝑀 (20)
Kịch bản tấn công 1
Để tấn công giả mạo được chữ ký số tập thể ủy nhiệm
thì người tấn cơng phải tìm được cửa sập của hàm 1
chiều của bài toán Logarithm trên đường cong Elliptic
tức là tìm được các khóa bí mật của các thành viên trong
tập thể.

𝑚


(3) Thuật toán 𝓐 với đầu vào là 𝑃𝐾𝑝𝑢𝑏 ,
{𝑚𝑖𝑚 , 𝛼𝑝𝑢𝑏 𝑖 )} sẽ cho ra (𝑚, 𝛼𝑝𝑢𝑏 ).
𝑚

(4) Thực nghiệm tấn công thành công nếu
1 ← 𝑽𝒆𝒓𝒊𝒇𝒚𝑷𝒖𝒃(𝑃𝐾𝑝𝑢𝑏 , 𝑚, 𝛼𝑝𝑢𝑏 , ‫𝑣 )ﬠ‬à 𝑚 ≠ 𝑚𝑖𝑚 .
B, Tấn công KMA - Known Message Attacks
Lược đồ đề xuất được cho là không thể giả mạo với
tấn cơng 𝐾𝑀𝐴 khi với mọi thuật tốn thời gian đa thức
của người tấn công 𝓐, xác suất thành công của thực
nghiệm dưới đây là một hàm nhỏ không đáng kể:

ISBN 978-604-80-5958-3

34


Hội nghị Quốc gia lần thứ 24 về Điện tử, Truyền thơng và Cơng nghệ Thơng tin (REV-ECIT2021)

Khi biết khóa cơng khai để tìm ra khóa bí mật, người
tấn cơng bắt buộc phải giải bài toán Logarithm trên
đường cong Elliptic và đây là bài tốn khó khơng giải
được trong thời gian đa thức.
Kịch bản tấn công 2
Người tấn công giả mạo giá trị ℎ3 trong thành phần chữ
ký, xác suất thành cơng là 1⁄𝑞, nếu 𝑞 đủ lớn thì xác suất
này sẽ là nhỏ không đáng kể.
Kịch bản tấn công 3
Người tấn công giả mạo chữ ký số bằng cách giả mạo
các giá trị 𝑈𝑝𝑖 = 𝑥𝑖 𝑃 và 𝜎𝑝𝑖 = ℎ3 𝑆𝑝𝑘𝑖 + 𝑥𝑖 𝑃𝑝𝑢𝑏 tuy

nhiên để làm việc đó cần phải tìm được giá trị 𝑥𝑖 và để
tìm được giá trị này người tấn công buộc phải giir bài
toán logarithm rời rạc trên đường cong elliptic và đây
là bài toán chưa giải được cho đến thời điểm hiện nay.
IV.

TÀI LIỆU THAM KHẢO
[1] Nguyễn Đức Toàn, Đặng Minh Tuấn“Về một lược đồ chữ ký số
tập thể ủy nhiệm dựa trên hệ mật ID-Based”, Hội thảo Khoa học
và công nghệ CEST, tr193-198, NXB Thông tin và Truyền
thông, ISBN 978-604-80-2642-4, 2017.
[2] Đặng Minh Tuấn, “Lược đồ chữ ký số tập thể đa thành phần dựa
trên cặp song tuyến tính”, Tạp chí nghiên cứu khoa học và công
nghệ quân sự, Đặc san 5-2012, pp.10-5. 2012.
[3] A. Shamir, “Identity-based Cryptosystems and Signatures
Schemes,” Proc. of Crpto’84,(1984), pp. 48–53.
[4] A. Boldyreva, “Efficient threshold signature , multisignature and
blind signature schemes based on the Gap-Diffie-Hellmangroup signature scheme,” Public-Key Cryptography – PKC
2003, pp. 31–46, 2002.
[5] X. Li and K. Chen, “ định danhmulti-proxy signature, proxy
multi-signature and multi-proxy multi-signature schemes from
bilinear pairings,” Applied Mathematics and Computation, vol
169, no. 1, pp. 437–450, 2005.
[ 6] R. A. Sahu and S. Padhye, “An định danhMulti-Proxy MultiSignature Scheme,” Int’l Conf. on Computer &
Communication Technology, pp. 60–63, 2010.
[7] R. A. Sahu and S. Padhye, “Identity-based multi-proxy multisignature scheme provably secure in random oracle model,”
European Transactions on Telecommunications, vol. 25, no. 3,
pp. 294–307, 2014.
[8] R. Dutta, R. Barua, P. Sarkar, and B. T. Road, “PairingBasedCryptographic Protocols : A Survey Introduction
Preliminaries Key Agreement Schemes Conclusion,” IACR

Eprint archive, 2004

KẾT LUẬN

Trong bài báo này, tác giả đã đưa ra mã hóa và giải mã
dùng hệ mật định danh dựa trên đường cong Elliptic.
Dựa vào độ an toàn của ECC trên bài tốn logarit rời rạc
đến nay vẫn chưa tìm được thuật toán giải dưới hàm mũ.
Cho nên độ an toàn cao và trong bài báo này tác giả dùng
các phép tốn đơn giản, dễ cài đặt, tốc độ tính tốn
nhanh. Chứng minh bằng tốn học cho thấy tính đúng
đắn của phần đề xuất có cơ sở. Tuy nhiên trong bài báo
này mới đề cập đến 1 điểm trên đường cong Elliptic, có
thể mở rộng đến 2 điểm trên đường cong Elliptic.

ISBN 978-604-80-5958-3

35