Tài liệu 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

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 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 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 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 ........................................................................................................... 1 1. Tính cấp thiết của đề tài luận án .............................................................. 1 2. Mục tiêu nghiên cứu ................................................................................ 1 3. Nội dung nghiên cứu................................................................................ 2 4. Đối tượng và phạm vi nghiên cứu ........................................................... 2 5. Phương pháp nghiên cứu ......................................................................... 3 6. Ý nghĩa khoa học và thực tiễn ................................................................. 3 7. Bố cục của luận án ................................................................................... 3 CHƯƠNG 1. TỔNG QUAN VỀ CHỮ KÝ SỐ VÀ HƯỚNG NGHIÊN CỨU PHÁT TRIỂN .................................................................................................... 5 1.1. Lược đồ chữ ký số ................................................................................ 5 1.2 Một số lược đồ chữ ký số ...................................................................... 6 1.2.1 Lược đồ RSA ................................................................................. 7 1.2.2 Chữ ký số Rabin............................................................................. 8 1.2.3 Chữ ký số Rabin-Williams .......................................................... 10 1.2.4. Lược đồ chữ ký DSA .................................................................. 12 1.2.5 Lược đồ ECDSA .......................................................................... 13 1.3 Chi phí thời gian của các phép tính số học trên Zn ............................. 16 1.4 Đánh giá chi phí thời gian kiểm tra của một số lược đồ chữ ký ......... 18 1.4.1 Chi phí kiểm tra của lược đồ chữ ký ECDSA ............................. 18 1.4.2 Đánh giá chi phí kiểm tra của một số lược đồ chữ ký ................. 20 1.5. Vấn đề thực tiễn và hướng nghiên cứu của đề tài luận án .................. 25 1.6 Kết luận chương 1 ................................................................................ 28 CHƯƠNG 2. CẢI TIẾN VÀ PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ RABIN .. 29 2.1 Mở đầu ................................................................................................. 29 2.2 Cơ sở toán học ..................................................................................... 30 2.2.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ố ..................................................................................... 30 2.2.2 Định lý phần dư Trung hoa và khai căn bậc hai trên vành ℤ𝑛 .... 33 2.2.3. Thuật toán khai căn bậc 3 theo modulo p ................................... 33 2.2.4. Một số kết quả bổ trợ .................................................................. 36 2.3 Lược đồ chữ ký RW0 .......................................................................... 38 2.3.1 Lược đồ chữ ký RW0................................................................... 38 2.3.2 Tính đúng đắn của lược đồ RW0 ................................................. 40 2.3.3 Độ an toàn của lược đồ chữ ký RW0 ........................................... 42 2.3.4 Tính hiệu quả của lược đồ RW0 .................................................. 43 iv 2.4 Lược đồ chữ ký R0 .............................................................................. 46 2.4.1 Lược đồ chữ ký R0 ...................................................................... 46 2.4.2 Tính đúng đắn của lược đồ R0 ..................................................... 48 2.4.3 Độ an toàn lược đồ chữ ký R0 ..................................................... 49 2.4.4 Tính hiệu quả của lược đồ chữ ký R0 .......................................... 49 2.5 Lược đồ chữ ký PCRS ......................................................................... 54 2.5.1 Lược đồ chữ ký PCRS ................................................................. 55 2.5.2 Tính đúng đắn của lược đồ chữ ký .............................................. 56 2.5.3 Độ an toàn của lược đồ chữ ký .................................................... 57 2.5.4. Chi phí thời gian của lược đồ PCRS. .......................................... 58 2.6 Kết luận chương 2 ................................................................................ 60 CHƯƠNG 3. LƯỢC ĐỒ CHỮ KÝ KẾT HỢP RABIN VÀ RSA .................. 61 3.1 Đảm bảo toán học của lược đồ chữ ký cho trường hợp e=3 ................ 61 3.1.1 Một số thống nhất và ký hiệu....................................................... 61 3.1.2 Hàm CR và việc khai căn bậc 3 ................................................... 61 3.1.3 Các tập E(β), B(β) ........................................................................ 62 3.1.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ố .......................................................... 64 3.2 Lược đồ DRSA-RABIN3 .................................................................... 65 3.2.1 Lược đồ DRSA-RABIN3 ............................................................ 66 3.2.2 Tính đúng đắn của lược đồ DRSA-RABIN3 ............................... 67 3.2.3 Độ an toàn của lược đồ DRSA-RABIN3 ..................................... 67 3.2.4 Chi phí thời gian của lược đồ DRSA-RABIN3 ........................... 68 3.3 Lược đồ PRSA-RABIN3 ..................................................................... 69 3.3.1 Lược đồ chữ ký PRSA-RABIN3 ................................................. 69 3.3.2 Tính đúng đắn của lược đồ chữ ký .............................................. 70 3.3.3 Độ an toàn của lược đồ chữ ký .................................................... 72 3.3.4 Chi phí thời gian của lược đồ PRSA-RABIN3 ............................ 72 3.4 Các lược đồ DRSA-Rabin3 và PRSA-Rabin3 cải tiến ........................ 73 3.4.1 Cơ sở toán học của việc cải tiến .................................................. 73 3.4.2 Lược đồ PRSA-Rabin3 cải tiến ................................................... 75 3.4.3 Lược đồ DRSA-Rabin3 cải tiến ................................................... 78 3.5 Kết luận chương 3 ................................................................................ 83 KẾT LUẬN...................................................................................................... 84 1. Các kết quả đã đạt được ......................................................................... 84 2. Những đóng góp mới của luận án .......................................................... 85 3. 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 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) 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) 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 ............... 17 Bảng 1.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. ...................................................... 18 Bảng 1.3- Kích thước khóa RSA, DL và EC và mức độ an toàn ........... 20 Bảng 1.4- Thuật toán kiểm tra RSA, Rabin và DSA .............................. 21 Bảng 1.5- Chi phí thời gian thuật toán kiểm tra Rabin và ECDSA ........ 25 Bảng 3.1- Thời gian tạo chữ ký lược đồ gốc và lược đồ cải tiến............ 78 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. 2. 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 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”. 3. 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. • Luận án nghiên cứu cải tiến chữ ký số Rabin để giảm chi phí thời gian của thuật toán ký, đồng thời đề xuất các lược đồ chữ ký phát triển chữ ký số Rabin với số mũ e=3, trong đó thuật toán ký được thực hiện theo hướng cải tiến như lược đồ Rabin. • Luận án nghiên cứu đề xuất lược đồ chữ ký kết hợp nguyên lý thiết kế của chữ ký số Rabin và RSA. Luận án chứng minh rằng các lược đồ chữ ký đề xuất có chi phí thời gian đáp ứng được các yêu cầu triển khai thực tiễn theo mục tiêu luận án đặt ra. 4. Đối tượng và phạm vi nghiên cứu Đối tượng và phạm vi nghiên cứu của luận án là cơ sở toán học lý thuyết số của các hệ mật và hệ chữ ký số cơ bản; các lược đồ chữ số có chi phí kiểm tra thấp: RSA, Rabin, DSA, ECDSA,... 3 5. Phương pháp nghiên cứu • Tham khảo các công bố khoa học, sách, tài liệu chuyên ngành, báo cáo khoa học về lĩnh vực mật mã, đặc biệt nội dung là chữ ký số. • Sử dụng các công cụ toán học của lý thuyết số để xây dựng các giải thuật cho lược đồ chữ ký số đề xuất. • Sử dụng lý thuyết về độ phức tạp thuật toán để đánh giá chi phí thời gian chạy của các lược đồ chữ ký đề xuất. 6. Ý nghĩa khoa học và thực tiễn Về ý nghĩa khoa học, luận án đề xuất một số lược đồ chữ ký số mới trên cơ sở cải tiến và phát triển lược đồ chữ ký Rabin, kết hợp chữ ký số Rabin và RSA. Các lược đồ chữ ký đề xuất đã cải tiến một số điểm hạn chế của lược đồ gốc nhằm tăng hiệu quả thuật toán, đồng thời có độ mật được kế thừa từ lược đồ gố Rabin và RSA. Về ý nghĩa thực tiễn, các lược đồ chữ ký mới được đề xuất trong luận án phù hợp trong các giao dịch mật mã dạng “nhiều-một” của các ứng dụng chữ ký số trong chính phủ điện tử và thương mại điện tử. 7. Bố cục của luận án Luận án có kết cấu gồm: phần mở đầu, 03 chương, phần kết luận, danh mục các công trình khoa học đã công bố và tài liệu tham khảo. Mở đầu: Phần mở đầu trình bày tính cấp thiết của đề tài luận án, những khái quát chung về mục tiêu, đối tượng, nội dung, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễn của luận án. Chương 1: Tổng quan về chữ ký số và hướng nghiên cứu phát triển Chương này trình bày các khái niệm cơ bản liên quan trực tiếp đến vấn đề nghiên cứu của luận án, tổng quan về chữ ký số và hướng nghiên cứu của đề tài luận án. Trên cơ sở phân tích và so sánh thời gian kiểm tra của các lược đồ chữ ký đã được đưa vào một số chuẩn chữ ký số và phân tích tình 4 hình nghiên cứu hiện nay về chữ ký số, chương 1 nêu rõ hướng nghiên cứu của đề tài luận án, là cơ sở cho việc nghiên cứu phát triển một số lược đồ chữ ký số ở chương 2 và chương 3. Chương 2: Cải tiến và phát triển lược đồ chữ ký Rabin Chương này đề xuất lược đồ chữ ký dòng Rabin. Chương này đề xuất 03 lược đồ chữ số mới, bao gồm: • Lược đồ chữ ký cải biên từ lược đồ Rabin • Lược đồ chữ ký cải biên từ lược đồ Rabin-Williams • Phát triển lược đồ chữ ký dòng Rabin với số mũ e=3. Các lược đồ cải biên đều sử dụng kỹ thuật tránh tính toán ký hiệu Jacobi và đảm bảo hiệu quả về chi phí thời gian chạy. Chương 3: Lược đồ chữ ký kết hợp Rabin và RSA Chương này đề xuất lược đồ chữ ký số kết hợp Rabin và RSA với số mũ kiểm tra e=3. Các lược đồ đề xuất bao gồm lược đồ xác suất và lược đồ tất định. Các lược đồ đề xuất đều có độ mật và thời gian chạy đảm bảo yêu cầu theo mục tiêu luận án đặt ra. Kết luận Phần kết luận tóm tắt các kết quả đạt được, những đóng góp mới của luận án và đề xuất một số ý kiến về việc phát triển một lược đồ chữ ký số cũng như ứng dụng của chúng. 5 CHƯƠNG 1. TỔNG QUAN VỀ CHỮ KÝ SỐ VÀ HƯỚNG NGHIÊN CỨU PHÁT TRIỂN 1.1. Lược đồ chữ ký số Định nghĩa 1.1 Một lược đồ chữ ký số là một bộ gồm năm thành phần ( P, K , A, S ,V ) thoả mãn các điều kiện sau đây: 1. P là tập hữu hạn các thông báo. 2. K là tập hữu hạn các khoá bí mật. 3. A là tập hữu hạn các thuật toán ký. 4. S là tập hữu hạn các chữ ký. 5. V là tập hữu hạn các thuật toán kiểm tra. 6. Với mỗi k  K tồn tại một thuật toán ký sigk  A và một thuật toán kiểm tra verk V tương ứng, mỗi sig k : P → S và verk : P  S → {true, false} là những hàm sao cho với mỗi m  P và s  S thoả mãn phương trình sau: true, s = sig k (m) verk ( s, m) =   false, s  sig k (m) Định nghĩa 1.2 Chữ ký số (digital signature) là một chuỗi dữ liệu được sinh ra bởi một lược đồ chữ ký số có chức năng liên kết một thông báo với thực thể tạo ra nó, nhằm đáp ứng các yêu cầu về: tính xác thực về nguồn gốc và tính toàn vẹn về nội dung của thông báo được ký. Định nghĩa 1.3 Thuật toán tạo chữ ký (còn gọi là thuật toán ký - digital signature generation algorithm/signature generation algorithm) là một phương pháp tạo lập chữ ký số. 6 Định nghĩa 1.4 Thuật toán kiểm tra chữ ký (digital signature verification algorithm/ verification algorithm) là phương pháp kiểm tra để khẳng định rằng một chữ ký số là hợp lệ hay ngược lại. Các thuộc tính cần có của một lược đồ chữ ký số Một lược đồ chữ ký cần đảm bảo bốn thuộc tính sau đây: • Tính đầy đủ: đảm bảo mọi thông báo đều ký được. • Tính đúng đắn: Trong một lược đồ chữ ký số, mọi chữ ký được tạo ra bởi thuật toán tạo chữ ký đều được chấp nhận bởi thuật toán kiểm tra chữ ký. • Tính khả thi: Thuật toán tạo chữ ký là dễ dàng đối với người ký (có khóa mật) và thuật toán kiểm tra là dễ dàng đối với mọi người (sử dụng khóa công khai). Thuộc tính này thường được đặc trưng bởi độ phức tạp của thuật toán ký và thuật toán kiểm tra là đa thức đối với các đối tượng tương ứng. • Tính an toàn trước tấn công tìm tham số mật và tấn công giả mạo chữ ký: thuộc tính này thường được đặc trưng bởi một bài toán khó của lý thuyết số. 1.2 Một số lược đồ chữ ký số Trong các lược đồ chữ ký khóa công khai, với mỗi cặp khóa được chọn thì việc tính toán khóa mật từ khóa công khai đều được đảm bảo bằng một bài toán khó của lý thuyết số. Các bài toán cơ bản đó là: • Bài toán phân tích số (FP – Factorization Problem). Độ khó của bài toán này đảm bảo tính an toàn cho hệ mật RSA và chữ ký số RSA. • Bài toán Logarithm rời rạc (DLP- Discrete Logarithm Problem). Độ khó của bài toán DLP đảm bảo tính an toàn cho hệ mật mã khóa công khai và chữ ký số ElGamal cũng như nhiều hệ chữ ký số khác, chẳng hạn DSA (Digital Signature Algorithm). 7 • Bài toán logarithm rời rạc trên đường cong elliptic (ECDLP-Elliptic Curve Discrete Logarithm Problem). Độ khó của bài toán này đảm bảo an toàn cho các lược đồ hệ mật trên đường cong Elliptic. Trong phần này, luận án trình bốn lược đồ chữ ký số cơ bản có ảnh hưởng trực tiếp đến vẫn đề nghiên cứu của luận án là lược đồ RSA, lược đồ Rabin và lược đồ Rabin-Williams, lược đồ DSA và lược đồ ECDSA. 1.2.1 Lược đồ RSA Trong lịch sử phát triển của khoa học mật mã, nếu như Diffie, Hellman và Merkle đã phát minh ra khái niệm mật mã khóa công khai thì Rivest, Shamir và Adleman lại có công lớn lao phát minh ra RSA, một sự thực thi đẹp nhất của hệ mật này. Thuật toán RSA đã được R.L. Rivest, A. Shamir và L.M.Adleman công bố lần đầu tiên vào tháng 8 năm 1977 [2]. Trên vành Zn , thuật toán RSA sử dụng số nguyên dương e là khóa công khai và số nguyên d là khóa bí mật. Số e cần thỏa mãn nguyên tố cùng nhau với 𝜙(𝑛) = (𝑝 − 1) × (𝑞 − 1) và theo đó, số d tìm được bằng các giải phương trình đồng dư 𝑑𝑒 ≡ 1 𝑚𝑜𝑑 𝜙(𝑛). Để xác định khóa bí mật d từ khóa công khai (n,e) cần xác định được hai nhân tử p và q của n, đây chính là bài toán phân tích số (FPFactorization Problem). Thuật toán 1.1 – Thuật toán sinh khóa RSA INPUT: tham số an toàn l OUTPUT: khóa công khai (n,e) và khóa bí mật d 1. Chọn hai số nguyên tố lớn p, q có cùng độ dài 𝑙/2 bit; 2. 𝑛 ← 𝑝 × 𝑞; 3. 𝜙(𝑛) ← (𝑝 − 1) × (𝑞 − 1); 4. Chọn số nguyên e sao cho 1 < 𝑒 < 𝜙(𝑛) và 𝑔𝑐𝑑(𝑒, 𝜙(𝑛)) = 1; 5. Tính d sao cho 1 < 𝑑 < 𝜙(𝑛) và 𝑑𝑒 ≡ 1 𝑚𝑜𝑑 𝜙(𝑛); 6. return (n,e,d). Giả sử h=H(m) là giá trị băm của văn bản m với H(.) là hàm băm mật mã. Khi đó, người ký sử dụng khóa mật d để tạo chữ ký và mọi người sử dụng 8 khóa công khai e để kiểm tra chữ ký. Thuật toán RSA dùng cho ứng dụng xác thực được trình bày như sau: Thuật toán 1.2 – Thuật toán tạo chữ ký RSA INPUT: khóa công khai (n,e), khóa bí mật d, văn bản 𝑚 OUTPUT: chữ ký s 1. ℎ ← 𝐶𝑜𝑑𝑒(𝐻(𝑚)); 2. 𝑠 ← ℎ𝑑 𝑚𝑜𝑑 𝑛; 3. return (s). Thuật toán 1.3 – Thuật toán kiểm tra chữ ký RSA INPUT: khóa công khai (n,e), văn bản m, chữ ký 𝑠 OUTPUT: Chữ ký hợp lệ hoặc không hợp lệ 1. ℎ ← 𝐶𝑜𝑑𝑒(𝐻(𝑚)); 2. ℎ′ ← 𝑠 𝑒 𝑚𝑜𝑑 𝑛; 3. If h=h’ then return(“Chữ ký hợp lệ”) else return(“Chữ ký không hợp lệ”). Chi phí thời gian chạy của hệ RSA chủ yếu là chi phí của phép tính lũy thừa theo modulo n. Chi phí thời gian chạy của hệ RSA sẽ được trình bày chi tiết trong mục 1.4. 1.2.2 Chữ ký số Rabin Ngay sau khi hệ RSA ra đời, năm 1979 M. O. Rabin công bố lược đồ chữ ký số Rabin [3] có độ an toàn cũng được đảm bảo bởi độ khó của bài toán phân tích số. Nếu trong lược đồ chữ ký RSA, tham số e cần thỏa mãn nguyên tố cùng nhau với 𝜙(𝑛), thì trong lược đồ Rabin tham số e=2. Với việc lựa chọn e=2, lược đồ chữ ký Rabin đạt được ưu điểm nổi trội khi chỉ cần thực hiện một phép bình phương modulo n trong thuật toán kiểm tra chữ ký. Tuy nhiên để có được điều này, các tham số hệ thống p, q của lược đồ Rabin cần thỏa mãn là số nguyên tố đồng dư 3 (mod 4). 9 Tham số hệ thống. Số nguyên n = p.q trong đó p, q là hai số nguyên tố khác nhau với p, q ≡ 3 (mod 4) (1.1) và b ∈ ℤn∗ . Các số nguyên n thỏa mãn điều kiện (1.1) còn được gọi là các số “blum”. Khóa bí mật do người ký giữ là bộ (n, p, q, b) và khóa công khai cho người xác thực chữ ký là (n, b). Hàm tóm lược, Hash: {0,1} → {0,1}h . Hàm đổi xâu bít sang số nguyên có biểu diễn nhị phân là xâu bít đó, 𝐶𝑜𝑑𝑒: {0,1} → ℤ. Với xâu bít 𝑥0 𝑥1 … 𝑥𝑡−1 , ta có: 𝐶𝑜𝑑𝑒(𝑥0 𝑥1 … 𝑥𝑡−1 ) = 𝑥0 2𝑡−1 + 𝑥1 2𝑡−2 + ⋯ + 𝑥𝑡−1 Thuật toán 1.4 – Thuật toán tạo chữ ký lược đồ Rabin INPUT: M ∈ {0,1} , (n, p, q, b). Trong đó: M là thông báo cần ký. (n, p, q, b) là khóa bí mật của người ký. OUTPUT: (s,R) ∈ ℤ∗n {0,1}k là chữ ký của người giữ bộ (n, p, q, b) lên thông báo M. 1. Lấy ngẫu nhiên xâu k bít R. 2. u  Code(Hash(M||R)); 3. Giải phương trình x(x + b) = u (mod n) (1.2) Nếu vô nghiệm, quay lại bước 1. Ngược lại lấy s là một nghiệm của phương trình (1.2). 4. return (s,R). Thuật toán 1.5 – Thuật toán kiểm tra chữ ký lược đồ Rabin INPUT: M, (s,R), (n, b). Trong đó: M ∈ {0,1} là thông báo được ký; 10 (s,R) là chữ ký lên M; (n,b) là khóa công khai của người ký. OUTPUT: Sự chấp nhận hay bác bỏ (s,R) là chữ ký lên M của người có khóa công khai (n,b). 1. u  Code(Hash(M||R)); 2. Chấp nhận chữ ký (s,R) lên thông báo M là của người có khóa công khai (n,b) khi và chỉ khi s là nghiệm của (1.2). 1.2.3 Chữ ký số Rabin-Williams Trong lược đồ chữ ký chữ ký Rabin, chữ ký s là một nghiệm của phương trình đồng dư bậc hai (1.2). Với n=p.q, thực tế để giải (1.2) cần giải hai phương trình đồng dư: x(x + b) = u (mod p) và x(x + b) = u (mod q) để tìm được bốn nghiệm 𝑠 = ±𝑥 (𝑚𝑜𝑑 𝑝) và 𝑠 = ±𝑥 (𝑚𝑜𝑑 𝑞). Từ bốn nghiệm này, sử dụng định lý phần dư Trung hoa ta tìm được bốn nghiệm khác nhau của s. Việc lựa chọn giá trị s nào trong bốn giá trị tìm được là một trong những vấn đề cần cải tiến của lược đồ Rabin. Tháng 10 năm 1980 Williams đưa ra một cải biên lược đồ Rabin, lược đồ được viết tắt là RW, bởi tên chung của hai ông [4]. Lược đồ Rabin cần đến 4 phép tính ký hiệu Jacobi trong thuật toán tạo chữ ký, trong khi Williams cải tiến chỉ cần một phép tính ký hiệu Jacobi. Lược đồ RW đã được đưa vào các chuẩn ISO/IEC 9796 [5] Tham số hệ thống. Số blum n = p.q thỏa mãn và p ≠ q (mod 8). (1.3) 𝑐 = 𝑞. (𝑞 −1 𝑚𝑜𝑑 𝑝) (1.4) 11 Khóa bí mật do người ký giữ là bộ (n, p, q, c) và khóa công khai cho các người xác thực chữ ký là n. Hàm tóm lược, Hash: {0,1} → {0,1}ℎ . Hàm định dạng thông báo f: {0,1}h → ℤ∗n sao cho với mọi H ∈ {0,1}h thì f(H) ≡ 12 (mod 16). Thuật toán 1.6 – Thuật toán tạo chữ ký lược đồ Rabin-Williams INPUT: M, (n, p, q, c). Trong đó: 𝑀 ∈ {0,1} là thông báo cần ký. (n, p, q, c) là khóa bí mật của người ký. OUTPUT: 𝑠 ∈ ℤn∗ sao cho 0  s < n/2 là chữ ký của người giữ bộ (n,p,q,c) lên thông báo M. 1. u ← f(Hash(M)); 𝑢 2. if ( ) = 1 then v ← u; 𝑛 else v ← u/2; 3. 𝑗1 ← 𝑣 𝑝+1 4 𝑞+1 4 mod p; 4. 𝑗2 ← 𝑣 5. j ← (c.( 𝑗1 − 𝑗2 ) + 𝑗2 ) mod n; mod q; (1.5) 6. s ← min(j, n – j); 7. return s. Thuật toán 1.7 – Thuật toán kiểm tra chữ ký lược đồ Rabin-Williams INPUT: M, s, n. Trong đó: 𝑀 ∈ {0,1} là thông báo được ký. s là chữ ký lên M. n là khóa công khai của người ký. OUTPUT: Accept ∈ {0,1}. Trong đó sự chấp nhận s là chữ ký lên M của người có khóa công khai n khi và chỉ khi Accept = 1. 12 1. if s ∉ [0, 2. 𝑛−1 2 ] then Accept  0; goto 5; u ← f(Hash(M)); 3. v ← 𝑠 2 mod n; 4. if (v ∈ {u, n – u} then Accept ← 1; else v ← 2.v mod n; if (v ∈ {u, n – u} then Accept ← 1; else Accept ← 0; 5. return Accept. 1.2.4. Lược đồ chữ ký DSA Hệ logarithm rời rạc đầu tiên là giao thức thỏa thuận khóa được Diffie và Hellman đề xuất năm 1976 [6]. Năm 1984, Elgamal đưa ra hệ mật mã và lược đồ chữ ký khóa công khai logaritm rời rạc và kể từ đó, đã có rất nhiều công bố khoa học về hệ mật và lược đồ chữ ký dạng này. Chữ ký số DSA được được công bố năm 1991 bởi viện Tiêu chuẩn và Công nghệ Hoa kỳ (NIST – U.S National Institute of Standard and Technology). Chữ ký DSA là chữ ký số họ Elgamal được đề xuất bởi Kravitz [7] và năm 1994 đã được đưa vào chuẩn FIP 186 [8] với tên gọi chuẩn chữ ký số DSS (Digital Signature Standard). Thuật toán 1.8 – Thuật toán sinh chữ ký DSA INPUT: Các tham số hệ thống (p,q,g), khóa riêng x, văn bản 𝑚 OUTPUT: Chữ ký (r,s) 1. Chọn ngẫu nhiên số nguyên k[1,q-1]; 2. 𝑇 ← 𝑔𝑘 𝑚𝑜𝑑 𝑝; 3. 𝑟 ← 𝑇 𝑚𝑜𝑑 𝑞; If r=0 then go to step 1; 4. ℎ ← 𝐶𝑜𝑑𝑒(𝐻(𝑚)); 5. 𝑠 ← 𝑘 −1 (ℎ + 𝑥𝑟) 𝑚𝑜𝑑 𝑞; If s=0 then go to step 1; 6. return (r,s).