Xây dựng lược đồ chữ ký số dựa trên tính khó của việc giải hệ phương trình phi tuyến trên Zp

4174638419711719558730285244 
- Giá trị của S tính được: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
c) Kiểm tra chữ ký (Thuật toán 3): 
Input: p,y1,y2,(R,S),M. 
+ Trường hợp 1: 
- Bản tin: M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
- Giá trị của R: 
2578978040546995360931057356885224501796548859040273140196191758320843166213664
239378150901806465978336262717423570863122966304174638419711719558730285244 
- Giá trị của S: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
- Giá trị của E tính được: 
765446923420569464858869279161340593924873951250 
- Giá trị của Z tính được: 
2365275623359255232876702232858324517036687506731193281049014835102728749249307
140783514760198811210087113971222711956968797566427029467752619495993833742 
- Giá trị của A tính được: 
5009182436092899969432922977146621404462547823386495213041663626091080070784452
500719758764653871289777747917389887273902468251921618658597941797697356682 
- Giá trị của B tính được: 
5009182436092899969432922977146621404462547823386495213041663626091080070784452
500719758764653871289777747917389887273902468251921618658597941797697356682 
Output: (R,S) = true. 
+ Trường hợp 2: Bản tin M bị giả mạo. 
- Bản tin: M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM ” 
- Giá trị của R: 
2578978040546995360931057356885224501796548859040273140196191758320843166213664
239378150901806465978336262717423570863122966304174638419711719558730285244 
- Giá trị của S: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
- Giá trị của E tính được: 
74094010598378196819556769036091466548756606187 
- Giá trị của Z tính được: 
2365275623359255232876702232858324517036687506731193281049014835102728749249307
140783514760198811210087113971222711956968797566427029467752619495993833742 
- Giá trị của A tính được: 
5009182436092899969432922977146621404462547823386495213041663626091080070784452
500719758764653871289777747917389887273902468251921618658597941797697356682 
- Giá trị của B tính được: 
1488359126273936813243632434469538093103616224220548588334028888150119304738618
467211912505689489579585662805761050860949693472937075275922757676168457192 
Output:(R,S) = false. 
+ Trường hợp 3: Thành phần R của chữ ký bị giả mạo. 
- Bản tin: M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
Công nghệ thông tin 
L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số  phi tuyến trên Zp.” 110 
- Giá trị của R: 
2578978040546995360931057356885224501796548859040273140196191758320843166213664
239378150901806465978336262717423570863122966304174638419711719558730285240 
- Giá trị của S: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
- Giá trị của E tính được: 
765446923420569464858869279161340593924873951250 
- Giá trị của Z tính được: 
3706949422319326956672681291321349052240993067883915856505868721353629235602927
997700748541436755638639645527554573697759394138289176543317958307715193512 
- Giá trị của A tính được: 
2103122925751575293927695945461415162983886316746280267035526289513905507273974
454583000897168494366134213430890824367120283956832755497130820091415965038 
- Giá trị của B tính được: 
1985222396844154533147613443758246007006163638474614219703118890277777325994538
876375304639811775582256510153550569528863364399572239755832733993950686404 
Output:(R,S) = false. 
2.2.6. Mức độ an toàn của thuật toán được đề xuất 
Mức độ an toàn của lược đồ mới đề xuất có thể đánh giá qua khả năng chống 
một số dạng tấn công như: 
+ Tấn công khóa bí mật 
Ở thuật toán mới đề xuất, cặp tham số x1, x2 cùng được sử dụng làm khóa bí 
mật để hình thành chữ k ý. Vì thế, thuật toán chỉ bị phá vỡ nếu cả 2 tham số này 
cùng bị lộ, nói cách khác là kẻ tấn công phải giải được hệ phương trình phi tuyến 
trên Zp. Do đó, mức độ an toàn của thuật toán mới đề xuất xét theo khả năng chống 
tấn công làm lộ khóa mật được đánh giá bằng mức độ khó của việc giải được hệ 
phương trình nói trên. Cần chú ý, đây là một dạng bài toán khó mới, mà ngay cả 
khi có các giải thuật thời gian đa thức cho RP và DLP cũng không có nghĩa là sẽ 
giải được bài toán này. Ngoài ra, tham số q cũng được sử dụng với vai trò khóa bí 
mật trong thuật toán ký. Như vậy, để phá vỡ tính an toàn của thuật toán, kẻ tấn 
công còn phải giải được bài toán tìm bậc của 1x , 2x .Tuy nhiên, việc tìm bậc của 
1x , 2x là không thể thực hiện được, vì 1x , 2x ở đây là đều là các tham số bí mật. 
+ Tấn công giả mạo chữ ký 
Từ thuật toán kiểm tra (Thuật toán 3) của thuật toán mới đề xuất cho thấy, một 
cặp (R,S) giả mạo sẽ được công nhận là chữ ký hợp lệ với một bản tin M nếu thỏa 
mãn điều kiện: 
         1 2
mod
1 2 mod
y y E R S p
R S y y p

   (18) 
Từ (18), nếu chọn trước R rồi tính S thì khi đó điều kiện (18) sẽ có dạng: 
     2
mod
2 mod
y R S p
S a y p

  (19) 
Còn nếu chọn trước S rồi tính R thì khi đó điều kiện (18) sẽ trở thành: 
     1
mod
2 mod
y R S p
R b y p

  (20) 
Với a, b là hằng số, dễ thấy rằng (19) và (20) cũng là một dạng bài toán khó 
chưa có cách giải. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 111
3. KẾT LUẬN 
Bài báo đề xuất một lược đồ chữ k ý số mới dựa trên tính khó của việc giải một 
hệ phương trình phi tuyến trên Zp. Do đó, mức độ an toàn của các thuật toán xây 
dựng theo phương pháp này sẽ được đảm bảo bằng mức độ khó của việc giải hệ 
phương trình trên. Trong toán học, đây là một dạng bài toán chưa có phương pháp 
giải. Vì vậy, phương pháp mới đề xuất ở đây có thể sử dụng để phát triển một lớp 
thuật toán chữ ký số cho các ứng dụng yêu cầu có độ an toàn cao trong thực tế. 
TÀI LIỆU THAM KHẢO 
[1]. Q. X. WU, Y. X. Yang and Z. M. HU, “New signature schemes based on 
discrete logarithms and factoring”, Journal of Beijing University of Posts 
and Telecommunications, vol. 24, pp. 61-65, January 2001. 
[2]. Z. Y. Shen and X. Y. Yu, “Digital signature scheme based on discrete 
logarithms and factoring”, Information Technology, vol. 28, pp. 21-22, June 
2004. 
[3]. Shimin Wei, “Digital Signature Scheme Based on Two Hard Problems”, 
IJCSNS International Journal of Computer Science and Network Security, 
VOL.7 No.12, December 2007. 
[4]. Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A New Digital 
Signature Scheme Based on Factoring and Discrete Logarithms”, Journal of 
Mathematics and Statistics, 04/2008; 12(3). DOI: 
10.3844/jmssp.2008.222.225, Source: DOAJ. 
[5]. Qin Yanlin, Wu Xiaoping, “New Digital Signature Scheme Based on both 
ECDLP and IFP”, Computer Science and Information Technology, 2009. 
ICCSIT 2009. 2nd IEEE International Conference on, 8-11 Aug. 2009, E-
ISBN: 978-1-4244-4520-2, pp 348 - 351. 
[6]. Swati Verma1, Birendra Kumar Sharma, “A New Digital Signature Scheme 
Based on Two Hard Problems”, International Journal of Pure and Applied 
Sciences and Technology, ISSN 2229 - 6107, Int. J. Pure Appl. Sci. Technol., 
5(2) (2011), pp. 55-59. 
[7]. Sushila Vishnoi, Vishal Shrivastava, “A new Digital Signature Algorithm 
based on Factorization and Discrete Logarithm problem”, International 
Journal of Computer Trends and Technology, volume 3, Issue 4, 2012. 
[8]. A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, “Cryptoschemes Based 
on Difficulty of Simultaneous Solving Two Different Difficult Problems”, 
Computer Science Journal of Moldova, vol.21, no.2(62), 2013. 
[9]. N.A. Moldovyan, “Digital Signature Scheme Based on a New Hard 
Problem”, Computer Science Journal of Moldova, vol.16, no.2(47), 2008. 
[10]. Phạm Văn Hiệp, Nguyễn Hữu Mộng, Lưu Hồng Dũng, “Một thuật toán chữ 
ký xây dựng dựa trên tính khó của việc giải đồng thời hai bài toán phân tích 
số và logarit rời rạc”, Tạp chí Khoa học và Công nghệ Đại học Đà Nẵng, số 
7(128). 2018, ISSN: 1859 – 1531. 
[11]. Nguyễn Vĩnh Thái, Lưu Hồng Dũng, “Hệ mật khóa công khai dựa trên tính 
khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số/khai 
Công nghệ thông tin 
L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số  phi tuyến trên Zp.” 112 
căn”, Tạp chí Thông tin và Truyền thông, Bộ Thông tin và Truyền thông, 
ISSN: 1859 – 3550, 12/2018. 
[12]. Lưu Hồng Dũng, Tống Minh Đức, Lưu Xuân Văn, “Phương pháp xây dựng 
lược đồ chữ ký số dựa trên tính khóa của việc giải đồng thời bài toán phân 
tích số và bài toán logarit rời rạc kết hợp khai căn trên Zn”, Hội nghị Quốc 
gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công Nghệ thông tin 
(FAIR), Hà Nội, ngày 09-10/08/2018. 
ABSTRACT 
A NEW DIGITAL SIGNATURE SCHEMA BASED ON THE DIFFICULTY OF 
SOLVING A SYSTEM OF NONLINEAR EQUATIONS ON ZP 
This paper presents the proposed method of building a digital signature 
algorithm which is based on the difficulty of solving a system of nonlinear 
equations on Zp. This is a new form of difficult problem without the solution, 
also originally proposed and applied to build digital signature algorithms. 
From this proposed method, it is possible to build a high-security digital 
signature platform for practical applications. 
Keywords: Digital signature; Digital signature algorithm; Digital signature schema; Discrete logarithm 
problem. 
Nhận bài ngày 10 tháng 11 năm 2018 
Hoàn thiện ngày 18 tháng 3 năm 2019 
Chấp nhận đăng ngày 25 tháng 3 năm 2019 
Địa chỉ: 1 Khoa Công nghệ & an ninh thông tin, Học viện An ninh nhân dân; 
 2 Viện Công nghệ thông tin, Viện Khoa học - Công nghệ quân sự; 
 3 Khoa Công nghệ thông tin, Học viện Kỹ thuật quân sự. 
 * Email: vanlx.hvan@gmail.com.