Xem mẫu
- 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: ntdung@uneti.edu.vn
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 khoá 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 khoá 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 Hình 1: Đồ thị biểu diễn đường cong elliptic dạng
dài hoặc cho phép một người sử dụng tính khoá công 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏
khai từ một chuỗi bất kỳ. Bài báo đề xuất mã hóa và Hệ mật định danh lần đầu tiên được công bố bởi Shamir
giải mã dùng hệ mật định danh dựa trên đường vào năm 1984 [1], ưu điểm chính của hệ mật định
cong Elliptic. danhlà không cần phải xác thực khóa công khai, khóa
Keywords- Hệ mật định danh , mã hóa và giải mã, này được dẫn xuất từ địa chỉ ID, địa chỉ email hay số
đường cong Elliptic. chứng minh thư của người sử dụng. Đã có nhiều lược đồ
I. GIỚI THIỆU 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
Mật mã đường cong Eliptic (ECC) là mã hóa khóa đề xuất mã hóa và giải mã dùng hệ mật định danhdựa
công khai dựa trên cấu trúc đại số của các đường cong trên đường cong Elliptic.
Ellip trên trường hữu hạn. Độ an toàn của ECC dựa vào
bài toán logarit rời rạc trên nhóm các điểm của đường II. CƠ SỞ TOÁN HỌC
cong elliptic (ECDLP). Hiện nay, đối với bài toán 2.1 Đường cong Elliptic trên trường hữu hạn
ECDLP cho đến nay vẫn chưa tìm được thuật toán dưới 2.1.1 Trường hữu hạn 𝐹𝑞 với 𝑞 là số nguyên tố
hàm mũ để giải.
Đường cong elliptic trên trường Fq (p là số nguyên tố).
Đường cong elliptic có tính an toàn tương đương với
các hệ mật khóa công khai truyền thống, trong khi độ dài Cho p là số nguyên tố (p > 3), cho a, b Fp sao cho
khóa nhỏ hơn nhiều lần. Ví dụ cỡ khoá 3248 bit của hệ 4a3 + 27b 2 ≠ 0 trong trường Fp .
mật RSA cho cùng một độ an toàn như 256 bit của hệ Một đường cong elliptic E trên 𝔽q (được định nghĩa bởi
mật ECC. Cho nên mật mã đường cong Eliptic ECC sử các tham số a và b) là một tập hợp các cặp giá trị (x, y)
dụng ít tài nguyên hệ thống hơn, năng lượng tiêu thụ nhỏ (x, y 𝔽q ) thỏa mãn công thức:
hơn.... Với ưu thế về độ dài khóa nhỏ, ECC đang được y 2 = x 3 + ax + b
ứng dụng rộng rãi trong nhiều lĩnh vực. cùng với điểm O đặc biệt gọi là điểm vô cực và có thể
Đường cong elliptic là tập hợp các điểm thỏa mãn biểu diễn dưới dạng:
một phương trình toán học cụ thể. Phương trình cho một O = (x, ∞). (2)
đường cong elliptic: Số lượng điểm của E (𝔽q ) (là ≠ E(𝔽q ) thỏa mãn định lý
𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏 (1) Hasse.
Đồ thị được biểu diễn như sau: Độ phức tạp của thuật toá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
ISBN 978-604-80-5958-3 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 𝐶 = (𝑟𝑃, 𝑀 ⊕ 𝐻2 (𝑒(𝑟𝑄𝐼𝐷 , 𝑠𝑃)) = (𝐶1 , 𝐶2 ) (10)
các tham số a, b 𝔽2m (với b ≠ 0) là tập các điểm Thực hiện những bước sau:
P(x, y) với x, y ∈ 𝔽2m ; thỏa mãn công thức: 1. Tính
y 2 + xy = x 3 + ax 2 + b (4) 𝐾 = 𝐻2 (𝑒(𝑠𝑄𝐼𝐷 , 𝐶1 )) (11)
Cùng với điểm O là điểm tại vô cực. từ thành phần bản mã 𝐶1 và khóa riêng 𝑠𝑄𝐼𝐷
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 ) ≤ 2. Tính M = C2 ⊕ K (12)
3. Ta thay C1 vào tính K ta có:
q + 1 + 2 √q trong đó p = 2m . rs
K = H2 (e(rQ ID , sP)) = H2 (e(Q ID , sP))
Ngoài ra, E( 𝔽2m )là số chẵn. = H2 (e(rQ ID , C1 )) = H2 (e(Q ID , P))rs (13)
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. 3.2 Chứng minh tính đúng đắn của lược đồ đề xuất
(x, y) + O = (x, y), (x, y) E( 𝔽2m ) 3.2.1 Chứng minh luôn tồn tại 1 điểm p trên đường cong
(x, y) + (x , − y) = O, (x, y) E( 𝔽2m ) Elliptic
Khi đó, (x, − y) là điểm đối của (x, y) trên E( 𝔽2m ). Giả sử E là đường cong Elliptic E(𝔽q ), với dạng:
y2 = x3 + 1
III. LƯỢC ĐỒ ĐỀ XUẤT Với q là 1 số nguyên tố: q ≡ 11(mod 12) và G1 là
3.1. Lược đồ mã hóa và giải mã nhóm nhỏ của p ∈ E(𝔽q ).
3.1.1. Sinh số Ta dùng hàm băm:
Gọi G1 là nhóm cộng cyclic có bậc là số nguyên tố q và H1 ∶ {0,1}∗ → G1
phần tử sinh là P. GT là nhóm nhân cyclic có cùng bậc Bước 1: Lấy Q ∈ E(𝔽q ) và lấy tọa độ x, y trên đường
q. e là cặp song ánh: cong Elliptic thỏa mãn:
e: G1 × G1 → GT (5) 1
x = (y 2 − 1) ⁄3 (14)
Với k là khóa bí mật, thỏa mãn điều kiện p là 1 số Áp dụng định lý Euler ta có:
nguyên tố. aq−1 ≡ 1 (mod q) (15)
p|# E(𝔽q ) a2q−1 ≡ a (mod q)
p2 χ ≠ E(𝔽q ) (2q−1)
⁄3 1
a ≡ a ⁄3 (mod q)
Trong đó: p ∈ G1 và GT ∈ 𝔽∗qk
Ta có: 3|(2q − 1)khi q ≡ 11(mod 12)
Chọn 1 điểm bất kỳ trên đường cong Elliptic Từ đây tính tọa độ x của điểm Q:
P ∈ E(𝔽q )[p] ; Q ID ∈ E(𝔽q )[p]
G1 = 〈P〉 Sau đó nhân với 1 hằng số ta có:
GT = 〈e(P, P)〉 (6) ≠E(𝔽q )
Chọn số nguyên ngẫu nhiên thỏa mãn: Q ID = .Q (16)
p
s ∈ ℤp∗ (Dùng để tính sP) q+1
Q ID = .Q
Ánh xạ ID đến một điểm Q ID , ở đây dùng hàm băm. p
H1 , H2 là các hàm băm được sử dụng cho mục đích bảo Vì:
mật và được định nghĩa như sau: H1 ∶ {0,1}∗ → p|# E(𝔽q )
G1 ; H2 ∶ GT → {0,1}n p2 χ ≠ E(𝔽q )
Công bố tham số của hệ thống là: Cho nên luôn tồn tại:
Params = (n, e, q, G1 , GT , H1 , H2 , sP) p ∈ E(𝔽q )
Khi:
3.1.2. Mã hóa Q ID ∈ G1
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.2.2 Ví dụ
3. Tạo 1 số nguyên ngẫu nhiên thỏa mãn: Giả sử E là đường cong Elliptic: E/(𝔽131 ) với dạng:
r ∈ ℤ∗p và tính rP y2 = x3 + 1
4. Tính K ta có Q ID = H1 (ID) Và:
Nên: K = H2 (e(rQ ID , sP)) (8) P = (98,58) ∈ E(𝔽131 ) [11]
Đặt bản mã tương ứng với cặp C ta có: G1 = 〈P〉
C = (C1 , C2 ) (9) GT = 〈e(P, P)〉
Trong đó: C1 = rP ; C2 = M ⊕ K 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
3.1.3 Giải mã q. e là cặp song ánh:
Khi người nhận được bản mã:
ISBN 978-604-80-5958-3 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: (18)
K = H2 (e(rQ ID , sP)) = H2 (e(98,73), ( 33,100)) (1) Chuỗi 𝑙 = 𝑙(𝑘) văn bản 𝑚1 , . . . , 𝑚𝑙 được chọn một
= H2 (49 + 58i) cách ngẫu nhiên trong không gian 𝑀𝑘
Mà: (2) Thực hiện các thuật toán trong lược đồ để tạo ra
C1 = rP ; chữ ký 𝛼𝑝𝑢𝑏 𝑖 .
𝑚
Cho nên:
(3) Thuật toán 𝓐 với đầu vào là 𝑃𝐾𝑝𝑢𝑏 ,
K = H2 (e(sQ ID , C1 ))
{𝑚𝑖𝑚 , 𝛼𝑝𝑢𝑏 𝑖 )} sẽ cho ra (𝑚, 𝛼𝑝𝑢𝑏 ).
= H2 (e(113,8), ( 34,23)) 𝑚
= H2 (49 + 58i) (4) Thực nghiệm tấn công thành công nếu 1 ←
Khi đó: C2 = M ⊕ K = (M ⊕ K) ⊕ K = M 𝑽𝒆𝒓𝒊𝒇𝒚𝑷𝒖𝒃(𝑃𝐾𝑝𝑢𝑏 , 𝑚, 𝛼𝑝𝑢𝑏 , 𝑣 )ﬠà 𝑚 ≠ 𝑚𝑖𝑚 .
C, Tấn công ACMA - Adaptive Chosen Message
Attacks
Lược đồ đề xuất chống lại được các loại hình tấn Đây là loại hình tấn công mạnh nhất, người tấn công có
công chữ ký số tập thể đa thành phần cụ thể là: thể được lựa chọn văn bản để ký phụ thuộc vào khóa
A, Tấn công RMA - Random Message Attacks công khai cũng như những chữ ký số có từ trước đó. Có
Lược đồ đề xuất được coi là không thể giả mạo nếu thể biểu diễn việc này thông qua khả năng truy cập đến
với mọi đa thức 𝑙(·) và với mọi thuật toán thời gian đa hàm Oracle, ký hiệu là 𝑆𝑖𝑔𝑛(·)𝑠𝑘 .
thức của người tấn công 𝓐 , xác suất thành công là Lược đồ đề xuất được cho là không thể giả mạo với tấn
một hàm nhỏ không đáng kể: 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ể:
(19)
(17)
(1) Chuỗi 𝑙 = 𝑙(𝑘) văn bản 𝑚1 , . . . , 𝑚𝑙 được chọn một
(1) Chuỗi 𝑙 = 𝑙(𝑘) văn bản 𝑚1 , . . . , 𝑚𝑙 được chọn một
cách ngẫu nhiên trong không gian 𝑀𝑘
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
(2) Thực hiện các thuật toán trong lược đồ để tạo ra
chữ ký 𝛼𝑝𝑢𝑏 𝑖 .
chữ ký 𝛼𝑝𝑢𝑏 𝑖 . 𝑚
𝑚
(3) Thuật toán 𝓐 với đầu vào là 𝑃𝐾𝑝𝑢𝑏 và có thể truy
(3) Thuật toán 𝓐 với đầu vào là 𝑃𝐾𝑝𝑢𝑏 ,
cập đến 𝑆𝑖𝑔𝑛(·)𝑠𝑘 với một số văn bản bất kỳ và sẽ cho
{𝑚𝑖𝑚 , 𝛼𝑝𝑢𝑏 𝑖 )} sẽ cho ra (𝑚, 𝛼𝑝𝑢𝑏 ).
𝑚 ra chữ ký số (𝑚, 𝛼𝑝𝑢𝑏 ). Không gian các văn bản truy
(4) Thực nghiệm tấn công thành công nếu vấn này gọi là 𝑀.
1 ← 𝑽𝒆𝒓𝒊𝒇𝒚𝑷𝒖𝒃(𝑃𝐾𝑝𝑢𝑏 , 𝑚, 𝛼𝑝𝑢𝑏 , 𝑣 )ﬠà 𝑚 ≠ 𝑚𝑖𝑚 . (4) Thực nghiệm tấn công thành công nếu
B, Tấn công KMA - Known Message Attacks 1 ← 𝑽𝒆𝒓𝒊𝒇𝒚𝑷𝒖𝒃(𝑃𝐾𝑝𝑢𝑏 , 𝑚, 𝛼𝑝𝑢𝑏 , 𝑣 )ﬠà 𝑚 ≠ 𝑀 (20)
Lược đồ đề xuất được cho là không thể giả mạo với Kịch bản tấn công 1
tấn công 𝐾𝑀𝐴 khi với mọi thuật toán thời gian đa thức Để tấn công giả mạo được chữ ký số tập thể ủy nhiệm
của người tấn công 𝓐, xác suất thành công của thực thì người tấn công phải tìm được cửa sập của hàm 1
nghiệm dưới đây là một hàm nhỏ không đáng kể: 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ể.
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ÀI LIỆU THAM KHẢO
tấn công bắt buộc phải giải bài toán Logarithm trên [1] Nguyễn Đức Toàn, Đặng Minh Tuấn“Về một lược đồ chữ ký số
đường cong Elliptic và đây là bài toán khó không giải tập thể ủy nhiệm dựa trên hệ mật ID-Based”, Hội thảo Khoa học
được trong thời gian đa thức. và công nghệ CEST, tr193-198, NXB Thông tin và Truyền
thông, ISBN 978-604-80-2642-4, 2017.
Kịch bản tấn công 2
[2] Đặng Minh Tuấn, “Lược đồ chữ ký số tập thể đa thành phần dựa
Người tấn công giả mạo giá trị ℎ3 trong thành phần chữ trên cặp song tuyến tính”, Tạp chí nghiên cứu khoa học và công
ký, xác suất thành công là 1⁄𝑞, nếu 𝑞 đủ lớn thì xác suất nghệ quân sự, Đặc san 5-2012, pp.10-5. 2012.
này sẽ là nhỏ không đáng kể. [3] A. Shamir, “Identity-based Cryptosystems and Signatures
Schemes,” Proc. of Crpto’84,(1984), pp. 48–53.
Kịch bản tấn công 3
[4] A. Boldyreva, “Efficient threshold signature , multisignature and
Người tấn công giả mạo chữ ký số bằng cách giả mạo blind signature schemes based on the Gap-Diffie-Hellman-
các giá trị 𝑈𝑝𝑖 = 𝑥𝑖 𝑃 và 𝜎𝑝𝑖 = ℎ3 𝑆𝑝𝑘𝑖 + 𝑥𝑖 𝑃𝑝𝑢𝑏 tuy group signature scheme,” Public-Key Cryptography – PKC
nhiên để làm việc đó cần phải tìm được giá trị 𝑥𝑖 và để 2003, pp. 31–46, 2002.
tìm được giá trị này người tấn công buộc phải giir bài [5] X. Li and K. Chen, “ định danhmulti-proxy signature, proxy
multi-signature and multi-proxy multi-signature schemes from
toán logarithm rời rạc trên đường cong elliptic và đây bilinear pairings,” Applied Mathematics and Computation, vol
là bài toán chưa giải được cho đến thời điểm hiện nay. 169, no. 1, pp. 437–450, 2005.
[ 6] R. A. Sahu and S. Padhye, “An định danhMulti-Proxy Multi-
IV. KẾT LUẬN Signature Scheme,” Int’l Conf. on Computer &
Communication Technology, pp. 60–63, 2010.
Trong bài báo này, tác giả đã đưa ra mã hóa và giải mã
[7] R. A. Sahu and S. Padhye, “Identity-based multi-proxy multi-
dùng hệ mật định danh dựa trên đường cong Elliptic. signature scheme provably secure in random oracle model,”
Dựa vào độ an toàn của ECC trên bài toán logarit rời rạc European Transactions on Telecommunications, vol. 25, no. 3,
đến nay vẫn chưa tìm được thuật toán giải dưới hàm mũ. pp. 294–307, 2014.
Cho nên độ an toàn cao và trong bài báo này tác giả dùng [8] R. Dutta, R. Barua, P. Sarkar, and B. T. Road, “Pairing-
các phép toán đơn giản, dễ cài đặt, tốc độ tính toán BasedCryptographic Protocols : A Survey Introduction
Preliminaries Key Agreement Schemes Conclusion,” IACR
nhanh. Chứng minh bằng toán học cho thấy tính đúng Eprint archive, 2004
đắ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
nguon tai.lieu . vn
