Luận án tiến sĩ: Phát triển lược đồ chữ ký số dựa trên hệ mật RSA-Rabin

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ------------------------ HOÀNG THỊ MAI NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN HỆ MẬT RABIN VÀ RSA LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2019 luan an BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ -------------------------- HOÀNG THỊ MAI NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN HỆ MẬT RABIN VÀ RSA Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 9 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TS Nguyễn Hữu Mộng 2. TS Ngô Trọng Mại Hà Nội – 2019 luan an i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn của các cán bộ hướng dẫn. Các số liệu, kết quả nghiên cứu trình bày trong luận án là hoàn toàn trung thực và chưa từng được công bố trong các công trình trước đây.

Các dữ liệu tham khảo được trích dẫn đầy đủ. Hà Nội, ngày 30 tháng 09 năm 2019 Hoàng Thị Mai luan an ii LỜI CẢM ƠN Luận án này được thực hiện tại Viện Khoa học và Công nghệ quân sự - Bộ Quốc phòng. Nghiên cứu sinh xin bày tỏ lòng biết ơn sâu sắc tới Tiến sĩ Nguyễn Hữu Mộng, Tiến sĩ Ngô Trọng Mại đã tận tình hướng dẫn và giúp đỡ nghiên cứu sinh trong suốt quá trình học tập, nghiên cứu và hoàn thành luận án. Nghiên cứu sinh chân thành cảm ơn các thày cô giáo, các nhà khoa học của Viện Khoa học và Công nghệ quân sự, Viện Công nghệ thông tin, Học viện Kỹ thuật quân sự, Học viện Kỹ thuật Mật mã,.

đã đóng góp nhiều ý quý báu để nghiên cứu sinh hoàn thành bản luận án này. Nghiên cứu sinh chân thành cảm ơn Ban Giám đốc, Phòng Đào tạo, Viện Khoa học và Công nghệ quân sự đã tạo điều kiện thuận lợi để Nghiên cứu sinh hoàn thành nhiệm vụ nghiên cứu. Cuối cùng, nghiên cứu sinh xin bày tỏ lời cảm ơn chân thành tới các đồng nghiệp, gia đình, bạn bè đã luôn động viên, chia sẻ, ủng hộ và giúp đỡ nghiên cứu sinh vượt qua khó khăn để hoàn thành các nội dung nghiên cứu. NCS Hoàng Thị Mai luan an iii MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT.

v DANH MỤC CÁC BẢNG. vii MỞ ĐẦU. Tính cấp thiết của đề tài luận án. Mục tiêu nghiên cứu.

Nội dung nghiên cứu. Đối tượng và phạm vi nghiên cứu. Phương pháp nghiên cứu. Ý nghĩa khoa học và thực tiễn.

Bố cục của luận án. TỔNG QUAN VỀ CHỮ KÝ SỐ VÀ HƯỚNG NGHIÊN CỨU PHÁT TRIỂN. Lược đồ chữ ký số .2 Một số lược đồ chữ ký số .2 Chữ ký số Rabin.3 Chữ ký số Rabin-Williams. Lược đồ chữ ký DSA .3 Chi phí thời gian của các phép tính số học trên Zn .4 Đánh giá chi phí thời gian kiểm tra của một số lược đồ chữ ký .1 Chi phí kiểm tra của lược đồ chữ ký ECDSA .2 Đánh giá chi phí kiểm tra của một số lược đồ chữ ký.

Vấn đề thực tiễn và hướng nghiên cứu của đề tài luận án .6 Kết luận chương 1. CẢI TIẾN VÀ PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ RABIN .2 Cơ sở toán học .1 Thặng dư bậc hai và việc khai căn bậc hai trên trường GF(p) với p nguyên tố .2 Định lý phần dư Trung hoa và khai căn bậc hai trên vành ℤ𝑛. Thuật toán khai căn bậc 3 theo modulo p. Một số kết quả bổ trợ .3 Lược đồ chữ ký RW0 .1 Lược đồ chữ ký RW0.2 Tính đúng đắn của lược đồ RW0 .3 Độ an toàn của lược đồ chữ ký RW0 .4 Tính hiệu quả của lược đồ RW0.

43 luan an iv 2.2 Tính đúng đắn của lược đồ R0 .3 Độ an toàn lược đồ chữ ký R0 .4 Tính hiệu quả của lược đồ chữ ký R0 .5 Lược đồ chữ ký PCRS .1 Lược đồ chữ ký PCRS .2 Tính đúng đắn của lược đồ chữ ký .3 Độ an toàn của lược đồ chữ ký. Chi phí thời gian của lược đồ PCRS.6 Kết luận chương 2. LƯỢC ĐỒ CHỮ KÝ KẾT HỢP RABIN VÀ RSA .1 Đảm bảo toán học của lược đồ chữ ký cho trường hợp e=3 .1 Một số thống nhất và ký hiệu.2 Hàm CR và việc khai căn bậc 3 .4 Quan hệ giữa việc giải phương trình đồng dư bậc 3 trên ℤ𝑛 và việc phân tích n ra thừa số nguyên tố .2 Lược đồ DRSA-RABIN3 .1 Lược đồ DRSA-RABIN3 .2 Tính đúng đắn của lược đồ DRSA-RABIN3 .3 Độ an toàn của lược đồ DRSA-RABIN3 .4 Chi phí thời gian của lược đồ DRSA-RABIN3 .3 Lược đồ PRSA-RABIN3 .1 Lược đồ chữ ký PRSA-RABIN3 .2 Tính đúng đắn của lược đồ chữ ký .3 Độ an toàn của lược đồ chữ ký .4 Chi phí thời gian của lược đồ PRSA-RABIN3 .4 Các lược đồ DRSA-Rabin3 và PRSA-Rabin3 cải tiến .1 Cơ sở toán học của việc cải tiến .2 Lược đồ PRSA-Rabin3 cải tiến .3 Lược đồ DRSA-Rabin3 cải tiến .5 Kết luận chương 3. Các kết quả đã đạt được.

Những đóng góp mới của luận án. Hướng nghiên cứu tiếp theo. 85 CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ. 86 TÀI LIỆU THAM KHẢO.

87 luan an v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 𝑎 Ký hiệu Jacobi ( ) 𝑛 || Toán tử nối xâu 𝐶𝑜𝑑𝑒(𝑠) Hàm đổi xâu bít 𝑠 = 𝑥0 𝑥1 … 𝑥𝑡−1 sang số nguyên NQRp Tập các phần tử không là thặng dư bậc hai modulo p QRp Tập các phần tử là thặng dư bậc hai modulo p 𝑍𝑛 Vành số nguyên với phép cộng và phép nhân rút gọn theo modulo n 𝑍𝑛∗ Nhóm nhân modulo n 𝑔𝑐𝑑(𝑎, 𝑏) Ước số chung lớn nhất của a và b 𝑙𝑒𝑛(𝑥) Độ dài bít của số tự nhiên x. 𝑡𝑓 Chi phí thời gian để tính giá trị hàm f 𝑤𝑡(𝑥) Trọng số của số nguyên x 𝑥 𝑚𝑜𝑑 𝑝 Phần dư khi chia x cho p 𝜙(𝑛) Số các số nguyên a thỏa mãn 0 ≤ 𝑎 < 𝑛 và gcd(𝑎, 𝑛) = 1 CA Thẩm quyền chứng thực (Certificate Authority) DES Chuẩn mã hóa dữ liệu (Data Encryption Standard) DS Chữ ký số (Digital Signature) DSA Thuật toán chữ ký số (Digital Signature Algorithm) DSS Chuẩn chữ ký số (Digital Signature Standard) ECDSA Thuật toán chữ ký số đường cong Eliptic (Elliptic Curve Digital Signature Algorithm) FIPS Tiêu chuẩn xử lý thông tin liên bang (Mỹ) (Ferderal Infomation Processing Standard) Hash Hàm băm (Hash function) luan an vi MD Bản tóm tắt (Message Digest) NCS Nghiên cứu sinh PKCS Các chuẩn mã hoá khoá công khai do hãng RSA đưa ra (Public Key Cryptography Standards) RSA Tên một hệ thống mật mã khoá công khai do các tác giả Ron Rivest, Adi Shamir và Leonard Adleman phát minh SHA Hàm băm mật mã (Secure Hash Algorithm) luan an vii DANH MỤC CÁC BẢNG Trang Bảng 1.1-Chi phí thời gian chạy các phép tính số học trên Zn .2- Chi phí phép nhân đôi điểm, cộng điểm trên đường cong elliptic trên các hệ tọa độ khác nhau.3- Kích thước khóa RSA, DL và EC và mức độ an toàn .4- Thuật toán kiểm tra RSA, Rabin và DSA .5- Chi phí thời gian thuật toán kiểm tra Rabin và ECDSA .1- Thời gian tạo chữ ký lược đồ gốc và lược đồ cải tiến. 78 luan an 1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Hiện nay, việc triển khai ứng dụng chữ ký số trong các giao dịch điện tử ngày càng phát triển tại Việt Nam.

Sự tăng trưởng này là kết quả của các điều kiện cơ sở hạ tầng và hành lang pháp lý liên quan đến chữ ký số ngày càng hoàn thiện. Về cơ sở hạ tầng, theo sách trắng Công nghệ thông tin và Truyền thông Việt Nam 2017, giá cước dịch vụ Internet băng rộng cố định tại Việt Nam đang ở mức thấp nhất thế giới với vị trí xếp hạng 1/139 nước [1], số người sử dụng Internet năm 2016 đã lên tới hơn 50 triệu người. Về pháp lý, luật giao dịch điện tử có hiệu lực từ năm 2005 đã qui định các giao dịch điện tử hoàn toàn toàn có tính pháp lý như các giao dịch thực hiện bằng văn bản giấy với chữ ký thông thường. Về lĩnh vực chữ ký số, hệ thống văn bản pháp luật ngày càng hoàn thiện, cùng với đó số lượng các đơn vị được cấp phép cung cấp dịch vụ chữ ký số ngày càng tăng.

Sau khi Trung tâm Chứng thực Chữ ký số Quốc gia được thành lập năm 2008 đã có 09 doanh nghiệp được cấp giấy phép cung cấp dịch vụ chứng thực chữ ký số công cộng cho các tổ chức và cá nhân. Số lượng chứng thư số cấp trong năm 2015 tăng 75% so với năm 2014. Mặc dù có sự phát triển nhanh chóng trong thời gian gần đây nhưng khả năng ứng dụng của chữ ký số là rất lớn và chữ ký số đóng vai trò hết sức quan trọng đối với tương lai phát triển của chính phủ điện tử và thương mại điện tử tại Việt Nam. Trong bối cảnh đó, việc nghiên cứu cải tiến hiệu quả của các lược đồ chữ ký số và xây dựng các lược đồ chữ ký số mới là rất cần thiết, có ý nghĩa sâu sắc về học thuật và thực tiễn.

Mục tiêu nghiên cứu Các giao dịch mật mã kiểu “nhiều-một” như các đầu mối tiếp nhận hồ sơ của dịch vụ hành chính công, xác định tính hợp lệ của phiếu bầu cử trong luan an 2 việc bầu cử điện tử,. có dạng nhiều người gửi thông tin đến một người, dẫn đến yêu cầu xác thực danh tính được tiến hành thường xuyên với số lượng lớn. Đặc điểm này cũng dẫn đến yêu cầu đối với chữ ký số mà dịch vụ sử dụng, cụ thể là thuật toán kiểm tra chữ ký số cần có thời gian chạy thấp. Mục tiêu của luận án là xây dựng hệ chữ ký số khóa công khai có chi phí kiểm tra chữ ký thấp cho các ứng dụng sử dụng giao dịch mật mã kiểu “nhiều-một”.

Nội dung nghiên cứu • Nghiên cứu các hệ chữ ký số cơ bản dựa trên các bài toán khó của lý thuyết số: bài toán phân tích số, bài toán logarithm rời rạc, bài toán logarithm rời rạc trên đường cong elliptic. • Trên cơ sở nghiên cứu các hệ chữ ký số cơ bản và các công bố khoa học liên quan trực tiếp tới mục tiêu luận án, luận án lựa chọn lược đồ chữ ký Rabin và RSA là cơ sở cho các cải tiến đề xuất lược đồ chữ ký số mới.