Phát triển thuật toán chữ ký số dựa trên hệ mã Poligh - Hellman
Công nghệ thông tin
PHÁT TRIỂN THUẬT TOÁN CHỮ KÝ SỐ DỰA TRÊN
HỆ MÃ POLIGH - HELLMAN
Nguyễn Vĩnh Thái1, Lưu Hồng Dũng2
Tóm tắt: Bài báo đề xuất xây dựng thuật toán chữ ký số trên cơ sở phát
triển hệ mã khóa bí mật Poligh – Hellman. Thuật toán chữ ký mới đề xuất có
nguyên tắc làm việc tương tự thuật toán chữ ký RSA, song cho phép nhiều đối
tượng ký có thể cùng sử dụng chung một modulo p trong các thuật toán ký và
thuật toán kiểm tra chữ ký. Đồng thời, bài báo cũng phân tích mức độ an toàn
của lược đồ mới đề xuất, cho thấy khả năng ứng dụng của nó trong thực tế.
Từ khóa: Chữ ký số, thuật toán chữ ký số, lược đồ chữ ký số, hệ mật khóa bí mật, hệ mã Poligh – Hellman.
1. ĐẶT VẤN ĐỀ
Hệ mã Poligh – Hellman [1] được đề xuất và công bố bởi S. Poligh và M.
Hellman vào năm 1976. Đây là một hệ mã khóa bí mật nhưng được xây dựng theo
phương pháp của các hệ mã lũy thừa RSA [2] , ElGamal [3],... Hệ mã Poligh –
Hellman có phương pháp mã hóa hoàn toàn như hệ mật RSA. Song do hệ mã
Poligh – Hellman sử dụng modulo p là số nguyên tố nên các khóa mã hóa và giải
mã phải được giữ bí mật hoàn toàn, chính vì lý do này mà hệ mã Poligh – Hellman
là một hệ mã khóa bí mật và không thực hiện được chức năng của một hệ chữ ký
số như hệ mật RSA.
Bài báo đề xuất một thuật toán chữ ký số được phát triển từ hệ mã Poligh –
Hellman, lược đồ mới đề xuất có nguyên tắc làm việc tương tự lược đồ RSA, song
lại cho phép các đối tượng ký cùng sử dụng chung một modulo p nguyên tố như
các lược đồ DSA trong chuẩn DSS [4] của Hoa Kỳ hay GOST R34.10 – 94 của
Liên bang Nga [5].
2. PHÁT TRIỂN THUẬT TOÁN CHỮ KÝ SỐ DỰA TRÊN HỆ MÃ
POLIGH – HELLMAN
2.1. Hệ mã Poligh – Hellman
2.1.1. Thuật toán hình thành tham số và khóa
Thuật toán bao gồm các bước như sau:
[1]. Sinh số nguyên tố p lớn, mạnh.
[2]. Tính:
[3]. Ch n khóa mã hóa e là m
gcd(e, (p)) =1
[4]. Tính khóa gi i mã d theo công th
[5]. Khóa bí m t chia s gi đối tượng g
tham s : p, d và e.
2.1.2 Thu t toán mã hóa và gi
a) Thu t toán mã hóa:
Thu t toán bao g m các bước:
[1]. Bi u di n b n tin c n ký M thành m
[0, p – 1]
ϕ( p) = (p −1)
ọ
ộ
t giá tr
ị
ng
ẫ
u nhiên th a mãn: 1< e <
ỏ
ϕ( p) và:
ϕ
ả
ức: d
=
e−1 mod
ϕ(p)
ậ
ẻ
ữ
a
ửi/mã hóa và nhận/giải mã là các
ố
ậ
ải mã
ậ
ậ
ồ
ể
ễ
ả
ầ
ột giá trị m tương ứng trong khoảng
N.V. Thái, L.H. Dũng, “Phát triển thuật toán chữ ký số dựa trên hệ mã Poligh – Hellman.”
180
Công nghệ thông tin
[2]. Người gửi sử dụng khóa mã hóa (e) để mã hóa bản tin:
C = me mod p
Bản mã tương ứng với bản tin M là C.
b) Thuật toán giải mã:
Thuật toán kiểm tra bao gồm các bước:
[1]. Người nhận sử dụng khóa giải mã (d) để giải mã bản tin nhận được:
m = Cd mod p
[2]. Chuyển giá trị m thành bản tin ban đầu.
Nhận xét:
Trong hệ mã Poligh – Hellman, khóa mã hóa (e) và giải mã (d) là 2 giá trị
nghịch đảo nhau theo modul
y, ch n bi t 1 trong 2 giá tr
kia. Vì th , c 2 khóa e và d đều ph
Hellman là m t h mã khóa bí m t. C
th th c hi n vai trò c a m t h ch ký s
2.2. Thuật toán chữ ký mới đề xuất MTA 17.3 – 01
Thu t toán ch ký m đề xu t, ký hi u MTA 17.3 – 01, được xây d
nguyên t c c a h mã Poligh – Hellman bao g m các thu t toán hình thành tham s
và khóa, thu t toán ký và ki m tra ch ký nh sau:
ϕ
( p). Do p là s
e ho c d thì hoàn toàn d
được gi bí m t và do
ng vì lí do ó, h Poligh – Hellman không
nh t RSA.
ố
nguyên t
ố
, nên
dàng tính được giá tr
ó h Poligh –
ϕ( p) = (p −1) . Như
v
ậ
ỉ
c
ầ
ế
ế
ả
ộ
ị
ặ
ả
ũ
ễ
ị
i
ữ
đ
ậ
đ
ệ
ệ
ậ
ữ
ệ
ể
ự
ệ
ủ
ộ
ệ
ố
ư hệ mậ
ậ
ữ
ệ
ớ
i
ấ
ệ
ựng theo
ắ
ủ
ậ
ồ
ậ
ố
ể
ữ
ư
2.2.1 Thuật toán hình thành các tham số hệ thống và khóa
a) Hình thành các tham số hệ thống
Hình thành tham số bao gồm các bước thực hiện như sau:
[1]. Chọn số nguyên tố p lớn sao cho việc giải bài toán logarit rời rạc trên Zp là
khó.
[2]. Lựa chọn hàm băm (hash function) H: {0,1}*
[3]. Công khai: p, H(.).
Zn , với:
.
n < p
Ghi chú: Trong ứng dụng thực tế, p là tham số hệ thống và do nhà cung cấp
dịch vụ chứng thực số tạo ra.
b) Thuật toán hình thành khóa
Mỗi người dùng U hình thành cặp khóa bí mật và công khai của mình theo các
bước như sau:
[1]. Chọn giá trị ex thỏa mãn: 1< ex < p −1 và: gcd(ex , p −1) = 1
[2]. Tính giá trị: dx =
[3]. Chọn một giá trị ngẫu nhiên t thỏa mãn: 1< t < p −1
[4]. Tính giá tr khóa e theo công th c: e = ex mod(p −1)
t mod p
Ki m tra n u: gcd(e, p −1) =1 thì th c hi n l i t ước [3].
[5]. Tính giá tr khóa d1 theo công th c: d1 = dx mod(p −1)
t mod p
Ki m tra n u: gcd(d1, p −1) =1 thì th c hi n l i t ước [3].
[6]. Tính giá tr khóa d2 công th c:
t mod(p −1)× t mod(p −1) −
ex
m tra n u: gcd(d2 , p −1) =1 thì th
(
ex
)
−1 mod(p −1)
ị
ứ
ể
ế
ự
ệ
ạ ừ b
ị
ứ
ể
ế
ự
ệ
ạ ừ b
ị
ứ
d2 =
dx
dx
t mod p ×
ex
n lại từ bước [3].
t mod p
mod(p −1)
Ki
ể
ế
ự
c hi
ệ
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017
181
Công nghệ thông tin
[7]. Công khai: e ; gi
2.2.2 Thu t toán ch ký s
a) Thu t toán ký
Thu t toán bao g
[1]. Tính giá trị đại di
ữ bí mât: d1, d2.
ố
ậ
ữ
ậ
ậ
ồ
m các bước:
n c a b
nh t c
ệ
ủ
ả
n tin c
ần ký (M): m = H (M)
d1
[2]. Hình thành ph
ần th
ứ
ứ
ấ
ủ
a ch
ữ
ký: S1 =
(
m
)
d2
mod p
[3]. Hình thành ph
ần th
hai của ch
ữ
ký: S2 =
(m)
mod p
[4]. Ch
b) Thu t toán ki
Thu t toán ki
[1]. Tính giá trị đại di
[2]. Tính giá tr theo công th
[3]. Ki m tra n = m thì ch
n tin c n th m tra được công nh
2.2.4 Tính úng đắn c a thu t toán MTA 17.3 – 01
Tính úng đắn c a thu t toán ch ký m đề xu
đề và m nh đề sau ây:
Bổ đề 1:
Nếu: p là số nguyên tố, 1< e < p −1, gcd(e, p −1) =1, d
ữ
ký s
m tra
m tra bao g
n c
ố
t
ương
ứ
ng v
ớ
i b n tin M là cặp: S = (S1, S2).
ả
ậ
ậ
ể
ể
ồ
m các bước:
a b n tin c
c:
ký là h
n.
ệ
ủ
ả
ầ
n th
S2
p l
ẩ
m tra (M): m = H(M)
S1
e mod
, ngu n g
ị
m
ứ
m
=
×
ệ
p
ể
ếu
m
ữ
ợ
ồ
ố
c và tính toàn v
ẹ
n c
ủ
a
b
ả
ầ
ẩ
ậ
đ
ủ
ậ
đ
ủ
ậ
ữ
ớ
i
ất
được ch
ứng minh qua các b
ổ
ệ
đ
=
e−1 mod(p
−1) và
0
≤
m
<
p thì: me.d mod p
= m .
Ch
Th
Do
ứ
ng minh:
ật v
ậ
ó s
y, ta có: d
=
e−1 mod(p
−
1) . Nên: d
×
emod(p
−1) =1
đ
ẽ
t
ồ
n tại s
ố
nguyên k sao cho: d
p−1
×
e
=
k
×
( p −1) +1
Theo định lý Euler [6] ta có: m( ) mod p
=1
T
ừ đây suy ra:
me.d mod p = mk. +1 mod p =
(
p−1
)
( p−1
mk. ) mod p
× mmod p
(
p−1
=
(
mk
ổ đề được ch
)
ng minh.
) mod p
× mmod p =1× mmod p = m
B
ứ
Bổ đề 2:
u: p là s
0 ≤ m < p thì: m(e
Ch ng minh: Th
Nế
ố
nguyên t
ố
, 1< e < p −1, gcd(e, p −1) =1, d = e−1 mod(p −1) ,
mod p = m
t v y, theo Bổ đề 1 ta có:
t
)
t
.
(
d
)
.
ứ
ậ
ậ
t−1
t
t
)
t
e.d
)
m(e
mod p = m(e.d mod p =
m
e.d mod p (
mod p
)
.
(
d
)
t−2
)
t−1
t−2
= m(e.d mod p =
(
m
t−3
e.d mod p (
)
mod p = m(e.d mod p
e.d
)
)
t−3
)
e.d
)
=
(
............................................................................................
me.d mod p (
)
mod p = m(e.d mod p
2
3
2
e.d
)
= m(e.d mod p =
(
me.d mod p (
)
mod p = m(e.d mod p
)
)
=
(
me.d mod p
)
e.d mod p = me.d mod p = m
N.V. Thái, L.H. Dũng, “Phát triển thuật toán chữ ký số dựa trên hệ mã Poligh – Hellman.”
182
Công nghệ thông tin
Bổ đề được ch
ứng minh.
Mệnh đề:
Cho p là s
ố
nguyên t
ố
, 1< ex < p −1, gcd(ex , p −1) =1, dx =
1< t < p −1, e = ex
t mod p
mod(p −1)
t mod(p −1)× t mod(p −1) −
ex
mod p , C2 =
ex
−1 mod(p −1)
mod(p −1)
,
,
0 ≤ m < p ,
d1 =
d2 =
dx
t mod p
,
dx
dx
t mod p ×
mod p . N u: m = C2 ×
ex
t mod p
mod(p −1)
,
d1
d2
0 ≤ m < p , C1 =
m = m
Ch
Th
m
m
ế
C1
e mod p thì:
.
ứng minh:
ậ
t v y, do:
ậ
m = C2 ×
C1
e mod p =
md1 mod p e
md2 mod p
)
×
(
)
t
mod p = md × md .e mod p
2
1
=
(
t
t
t
= m((
×
dx
)
mod
(
p−1
)
.
(
ex
)
mod
(
p−1
)
−
(
dx
)
mod p.
(
ex
)
mod p mod( p−1)
)
t
t
dx
)
mod p
)
mod
(
p−1
).
((
ex
)
mod p
)
mod
(
p−1
× m((
) mod p
t
t
t
t
= m(d
) mod p = m(d
mod p
)
.(
ex
)
mod
(
p−1
)
x
.(
ex
)
x
t
t
Theo Bổ đề 2, ta có: m(e
ừ đây suy ra: m = m
nh đề được ch ng minh.
2.2.5 Mức độ an toàn của thuật toán MTA 17.3 – 01
modn = m
) .(dx )
x
T
M
ệ
ứ
Mức độ an toàn của thuật toán mới đề xuất có thể đánh giá qua các khả năng sẽ
được xem xét dưới đây:
a) Khả năng tấn công làm lộ khóa mật
Với thuật toán hình thành khóa ở mục 2.1.1, hoàn toàn có thể chọn giá trị của t
sao cho d1, d2 và e không nghịch đảo với nhau theo cả modulo p và modulo (p-1).
Nghĩa là từ e không thể tính được d1 và d2 bằng phép nghịch đảo theo modulo p và
modulo (p-1). Ngoài ra, việc tính d1, d2 bằng cách giải bài toán logarit rời rạc từ:
d1
d2
)
S1 =
u giá tr
b) Kh
(
m
)
mod p và: S2 =
a tham s được ch
ng t n công thu t toán ch
ng 1 và 2 cho th y các thu
a thu t toán ch ký s RSA có c
các ch ng minh và ánh giá v tính an toàn c
ng đối v i MTA 17.3 – 01.
Bảng 1. Thu t toán ký c a RSA và MTA 17.3 – 01
Thu t toán Thu t toán ký
RSA
(
m
mod p c
đủ
ký s
ũng không khả thi, vì đây là bài toán khó
n
ế
ị
ă
c
ủ
ố
p
ọ
n
ữ
l
ớ
n.
ả
n
ấ
ậ
ố
Bả
ấ
ật toán ký và ki
ể
m tra ch
ữ
ký c
ủ
a MTA 17.3 – 01
nh nhau. Vì v y,
ng hoàn toàn có th áp
và c
ủ
ậ
ữ
đ
ố
ơ
ch làm vi
ế
ệc tương t
ự
ư
ậ
ứ
ề
ủ
a RSA c
ũ
ể
d
ụ
ớ
ậ
ủ
ậ
ậ
S =
S1 =
S2 =
m
d modn
d1
MTA 17.3 – 01
(
m
)
mod p
mod p
d2
( )
m
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017
183
Công nghệ thông tin
Bảng 2. Thuật toán kiểm tra của RSA và MTA 17.3 – 01
Thuật toán Thuật toán kiểm tra
RSA
m =
e modn
S
if m = H(M ) then S = true
S2 S1
e mod
then (S1,S2) = true
MTA 17.3 – 01
m
=
×
p
if m
= H(M )
2.2.6 Hiệu quả thực hiện của thuật toán MTA 17.3 – 01
Hiệu quả thực hiện của các thuật toán có thể được đánh giá thông qua số phép
toán cần thực hiện hay tổng thời gian cần thực hiện các phép toán để hình thành và
kiểm tra chữ ký. Để so sánh hiệu quả thực hiện của thuật toán mới đề xuất với
thuật toán chữ ký số RSA, ở đây qui ước sử dụng các ký hiệu:
Texp : thời gian thực hiện một phép toán mũ modul;
Th : thời gian thực hiện hàm băm (hash function).
Tmul : thời gian thực hiện một phép toán nhân modul;
a) Thời gian thực hiện của thuật toán RSA:
Thời gian hình thành chữ ký là: (Texp + Th)
Thời gian kiểm tra chữ ký là: (Texp + Th)
Tổng thời gian thực hiện:
(2Texp + 2Th )
b) Thời gian thực hiện của thuật toán MTA 17.3 – 01:
Thời gian hình thành chữ ký là: (2Texp + Th)
Thời gian kiểm tra chữ ký là: (Texp + Th + Tmul)
Tổng thời gian thực hiện:
(3Texp + 2Th +Tmul )
Tổng hợp thời gian thực hiện của thuật toán mới đề xuất MTA 17.3 – 01 và
của RSA được chỉ ra trên Bảng 3 như sau:
Bảng 3. Thời gian thực hiện của các thuật toán MTA 17.3 – 01 và RSA
TT
1
Thuật toán
Tổng thời gian thực hiện
2Texp + 2Th
3Texp + 2Th + Tmul
RSA
2
MTA 17. 3 – 01
Nhận xét:
Từ Bảng 3 có thể thấy rằng hiệu quả thực hiện của thuật toán MTA 17.3 – 01
thấp hơn thuật toán RSA.
3. KẾT LUẬN
Bài báo đề xuất một thuật toán chữ ký mới từ việc phát triển hệ mã khóa bí mật
Poligh – Hellman. Thuật toán mới đề xuất có nguyên tắc làm việc cơ bản như lược
đồ chữ ký RSA, song các đối tượng ký có thể sử dụng chung modulo p mà không
ảnh hưởng đến độ an toàn của lược đồ. Một số phân tích sơ bộ về độ an toàn và
hiệu quả thực hiện cho thấy khả năng ứng dụng của thuật toán mới đề xuất là hoàn
toàn thực tế.
TÀI LIỆU THAM KHẢO
N.V. Thái, L.H. Dũng, “Phát triển thuật toán chữ ký số dựa trên hệ mã Poligh – Hellman.”
184
Công nghệ thông tin
[1] Pohlig, S. and Hellman, M., ”An Improved Algorithm for Computing Logarithms over
GF(p) and its Cryptographic Significance,” IEEE Trans. on Info. Theory Vol. IT-
24(1) pp. 106-110 (Jan. 1978).
[2] R. L. Rivest, A. Shamir, L. M. Adleman, “A Method for Obtainỉng Digital Signatures
and Public Key Cryptosystems”, Commun. of the ACM, Voi. 21, No. 2, 1978, pp. 120-
126.
[3] ElGamal T., “ A public key cryptosystem and a signature scheme based on discrete
logarithms”. IEEE Transactions on Information Theory. 1985, Vol. IT-31, No. 4.
pp.469–472.
[4] National Institute of Standards and Technology, NIST FIPS PUB 186-3. Digital
Signature Standard, US Department of Commerce, 1994.
[5] GOST R 34.10-94. Russian Federation Standard. Information Technology.
Cryptographic data Security. Produce and check procedures of Electronic Digital
Signature based on Asymmetric Cryptographic Algorithm. Government Committee of
the Russia for Standards, 1994 (in Russian).
[6] R. Kenneth, “Elementary Number Theory and its Applications”, AT & T Bell
Laboratories, 4th Edition, ISBN: 0-201- 87073-8, 2000.
[7] Mark Stamp, Richard M. Low , “Applied cryptanalysis: Breaking Ciphers in the Real
World”. John Wiley & Sons, Inc., ISBN 978-0-470-1.
[8] D. Boneh, “Twenty Years of Attacks on the RSA Cryptosystem, Notices of the
American Mathematical Society”, 46(2), 1999, pp. 203-213.
DEVELOPING NEW DIGITAL SIGNATURE ALGORITHM BASED ON
POLIGH – HELLMAN EXPONENTIATION CIPHER
ABSTRACT— This paper proposes new digital signature algorithm based on the Poligh – Hellman
exponentiation cipher. The proposed signature algorithm has the same working principle as the RSA signature
algorithm, but allows multiple signatures to share the modulo p in signed algorithms and signature verification
algorithms. In addition to information security capabilities, the new algorithm has the ability to validate the
integrity and origin of the message is confidential.
KEYWORDS — Public - Key Cryptosystem, Secret - Key Cryptosystem, Digital Signature Algorithm, Poligh
– Hellman exponentiation cipher.
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ỉ: 1 Viện CNTT, Viện KH và CN QS
2
Khoa CNTT, Học viện KTQS.
Email: nguyenvinhth[email protected].
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017
185
6 trang
24240
Free
Bạn đang xem tài liệu "Phát triển thuật toán chữ ký số dựa trên hệ mã Poligh - Hellman", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- phat_trien_thuat_toan_chu_ky_so_dua_tren_he_ma_poligh_hellma.pdf
