Đề tài Chuẩn chữ ký số và ứng dụng

Lời mở đầu. Trong sự phát triển của xã hội loài người, kể từ khi có sự trao đổi thông tin, an toàn thông tin trở thành một nhu cầu gắn liền với nó như hình với bóng. Đặc biệt trong thời đại mà thương mại điện tử đang lên ngôi thì việc có được các công cụ đầy đủ để đảm bảo cho sự an toàn trao đổi thông tin liên lạc là vô cùng cần thiết. Chính vì vậy mà chữ ký số đã ra đời với nhiều tính năng ưu việt. Bằng việc sử dụng chữ ký số mà những giao dịch liên quan đến lĩnh vực kinh tế (như giao dịch tài chính –ngân hàng, thuế, hải quan, bảo hiểm…) và những giao dịch yêu cầu tính pháp lý cao (các dịch vụ hành chính công, đào tạo từ xa) có thể thực hiện qua mạng máy tính. Ngày nay, chữ ký số đóng một vai trò quan trọng trong kế hoạch phát triển Thương mại điện tử và Chính phủ điện tử ở nước ta. Chính vì vậy em đã chọn lĩnh vực “chuẩn chữ ký số” làm đề tài nghiên cứu cho bài luận văn tốt nghiệp của mình. Nội dung của bài báo cáo tóm tắt này em xin trình bày hai phần chính: Chương 1 – Chuẩn hàm băm an toàn. Mục đích của chương này là trang bị cho người đọc các kiến thức cần thiết về hàm băm cũng như giới thiệu các hàm băm an toàn được sử dụng trong giải thuật tạo và xác nhận chữ ký số được trình bày trong chương 3. Chương 2 – Chuẩn chữ ký số. Đây là nội dung trọng tâm của bài luận văn trong đó trình bày chi tiết về chuẩn chữ ký số, giải thuật tạo và xác nhận chữ ký số DSA, các giải thuật tạo và xác nhận các tham số cần thiết được sử dụng trong giải thuật tạo và xác nhận chữ ký số DSA đó. Do hạn chế về kiến thức cũng như về thời gian nghiên cứu, bài luận văn này chắc chắn không tránh khỏi những sai sót. Em rất mong nhận được ý kiến đóng góp của các thầy cô giáo và bạn bè. Cuối cùng em xin chân thành cảm ơn sự hỗ trợ của các thầy cô trong khoa, đặc biệt tới thầy giáo TS. Lê Phê Đô, người đã luôn tận tình hướng dẫn, theo dõi em trong quá trình thực hiện đề tài. Sinh viên thực hiện: Nguyễn Đình Lượng Danh sách các từ viết tắt DSA: Digital Signature Standard. DSS: Digital Signature Algorithm. FIPS: PUB Federal Information Processing Standards Publication. NIST: the National Institute of Standards and Technology. SHS: Secure Hash Standard SHA: Secure Hash Algorithm. Các ký hiệu toán học Phép toán và theo bít. Phép toán hoặc theo bít . Phép toán XOR theo bít. Trả về số nguyên nhỏ nhất thỏa mãn ≥ a. Ví dụ: =5, = 6, = -2. ROTLn(x) Phép quay trái từ x đi n bít, được thực hiện bằng cách bỏ đi n bít trái nhất của từ x và sau đó lại thêm đúng n bít trái nhất vừa bỏ đi đó vào phía bên phải của x. ROTRn(x) Phép quay phải từ x đi n bít, được thực hiện bằng cách bỏ đi n bít phải nhất của từ x và sau đó lại thêm đúng n bít phải nhất vừa bỏ đi đó vào phía bên trái của x. Chương 1 CHUẨN HÀM BĂM AN TOÀN (SHS - FIPS PUB 180-2) 1.1 Giới thiệu về NIST. Viện chuẩn và công nghệ quốc gia NIST (the National Institute of Standards and Technology), được thành lập năm 1901, là một cơ quan quản trị công nghệ của bộ thương mại Hoa Kì. Nhiệm vụ của Viện này là thúc đẩy các đổi mới và nâng cao tính cạnh tranh công nghệ bằng cách đưa ra khoa học đo lường, các chuẩn và công nghệ tiên tiến theo cách làm tăng tính an toàn kinh tế và cải thiện chất lượng cuộc sống. Với một phần nhiệm vụ này, các nhà khoa học và kỹ sư của NIST đã không ngừng cải tiến khoa học đo lường, làm cho công nghệ và chế tạo siêu chính xác, cái mà rất cần thiết cho các công nghệ tiên tiến nhất ngày nay, trở nên có thể thực hiện được. Họ còn quan tâm trực tiếp đến việc nghiên cứu và phát triển các chuẩn, được thực hiện bởi các cơ quan của chính phủ Mỹ và của tư nhân. Sự đổi mới và các tiến bộ về công nghệ phụ thuộc vào các kỹ năng và khả năng độc nhất của NIST, đặc biệt trong 4 lĩnh vực trọng yếu là: công nghệ sinh học, công nghệ nano, công nghệ thông tin và chế tạo tiên tiến. NIST thực hiện nhiệm vụ của mình trong 4 chương trình hợp tác sau: Thư Viện NIST: thực hiện các nghiên cứu có vai trò thúc đẩy cơ sở công nghệ của quốc gia và điều này là cần thiết cho nền công nghiệp của nước Mỹ để có thể cải tiến liên tục các sản phẩm và dịch vụ. Chương trình chất lượng quốc gia Baldrige: thúc đẩy hoạt động của các nhà sản xuất, công ty dịch vụ, Viện giáo dục và các cơ sở y tế chăm sóc sức khỏe; chỉ đạo thực hiện các chương trình lớn và quản lý giải thưởng chất lượng quốc gia Malcolm Baldrige hàng năm để ghi nhận các kết quả hoạt động xuất sắc và chất lượng đã đạt được. Đối tác sản xuất mở rộng Hollings: là một mạng bao gồm các trung tâm địa phương nhằm hỗ trợ về mặt kỹ thuật và kinh doanh cho các nhà sản xuất nhỏ. Chương trình công nghệ nâng cao: nhằm tạo ra sự phát triển của các công nghệ mới để mang lại lợi nhuận lớn cho quốc gia bằng cách cùng với các khu vực tư nhân đồng tài trợ cho đối tác R&D (Reseach and Development). NIST đã có một quỹ hoạt động trị giá khoảng 930 triệu USD cho năm tài chính 2006 của mình. NIST sở hữu khoảng 2800 các nhà khoa học, kỹ sư, kỹ thuật viên, hỗ trợ viên và nhân viên hành chính. Ngoài ra NIST còn có khoảng 1800 công tác viên (là những người tìm kiếm khách hàng và các kỹ sư của các công ty ở Mỹ và ở nước ngoài). Hơn nữa, NIST còn có đội ngũ hội viên đông đảo với khoảng 1400 chuyên gia và nhân viên sản xuất của gần 350 trung tâm chi nhánh trên toàn quốc. Một số tài liệu công nghệ mà NIST đã công bố là: FIPS 113 Tháng 3 năm 1985, xác thực dữ liệu máy tính. FIPS 140-1 Tháng 1 năm 1994, Các yêu cầu bảo mật cho các module mã hóa.  FIPS 140-2 Tháng 3 năm 2001, Các yêu cầu bảo mật cho các module mã hóa. FIPS 140-3 Tháng 7 năm 2007, Các yêu cầu bảo mật cho các module mã hóa. FIPS 140-3 là một phiên bản sửa đổi của FIPS 140-2. Nó đưa ra 5 mức độ bảo mật thay vì là 4 như trong FIPS 140-2 và có một phần giành riêng cho bảo mật phần mềm.  FIPS 180-2 Ngày 1 tháng 8 năm 2002, chuẩn hàm băm an toàn SHS. FIPS 186-2 Tháng 1 năm 2000, chuẩn chữ ký số DSS.   FIPS 188 Tháng 9 năm 1994, chuẩn các mức độ bảo mật cho truyền tin.  FIPS 190 Tháng 9 năm1994, nguyên tắc sử dụng các lựa chọn công nghệ mật mã tiên tiến.  FIPS 196 Tháng 2 năm 1997, thực thể xác nhận sử dụng mật mã khóa công khai. FIPS 197 Tháng 11 năm 2001, chuẩn mật mã tiên tiến. FIPS 199 Tháng 2 năm 2004, các chuẩn về phân loại mức an toàn của các hệ thống thông tin liên bang. FIPS 31 Tháng 6 năm1974, các nguyên tắc về tính bảo mật của việc xử lý dữ liệu tự động và quản lý rủi ro. FIPS 41 Tháng 5 năm 1975, các nguyên tắc bảo mật máy tính cho việc thực hiện các hoạt động riêng tư. FIPS 46-3 Tháng 10 năm1999, chuẩn mã hóa dữ liệu DES.  FIPS 73 Tháng 6 năm 1980, các nguyên tắc bảo mật cho các ứng dụng máy tính.  FIPS 74 Tháng 8 năm 1981, các nguyên tắc thực thi và sử dụng chuẩn mật mã dữ liệu NBS.  FIPS 102 Tháng 9 năm 1983, các nguyên tắc cấp chứng thực và xác nhận sự an toàn của máy tính.  FIPS 171 Tháng 8 năm 1992, quản lý khóa có sử dụng ANSI X9.17. 1.2. Sơ lược về hàm băm 1.2.1. Giới thiệu Theo các sơ đồ chữ ký ở trên thì chữ ký của thông điệp cũng có độ dài bằng độ dài của thông điệp, đó là một điều bất tiện. Ta mong muốn như trong trường hợp chữ ký viết tay, chữ ký có độ dài ngắn và hạn chế cho dù văn bản có độ dài bằng bao nhiêu. Vì chữ ký số được ký cho từng bit của thông điệp, nếu muốn chữ ký có độ dài hạn chế trên thông điệp có độ dài tùy ý thì ta phải tìm cách rút gọn độ dài thông điệp. Nhưng bản thân thông điệp không thể rút ngắn được, nên chỉ còn cách là tìm cho mỗi thông điệp một thông điệp thu gọn có độ dài hạn chế và thay việc ký trên thông điệp, ta ký trên thông điệp thu gọn. Để giải quyết vấn đề này ta sử dụng hàm băm, chấp nhận một thông điệp có độ dài tuỳ ý làm đầu vào. Hàm băm sẽ biến đổi thông điệp này thành một thông điệp rút gọn và sau đó sẽ dùng lược đồ ký để ký lên thông điệp rút gọn đó. 1.2.2. Định nghĩa hàm băm Hàm băm là một hàm h có ít nhất hai tính chất sau: Tính chất nén: h sẽ ánh xạ một đầu vào x có độ dài bit hữu hạn tùy ý tới một đầu ra h(x) có độ dài n bit hữu hạn. Tính chất dễ dàng tính toán: Với h cho trước và một đầu vào x, có thể dễ dàng tính được h(x). Hàm băm yếu: Hàm băm h được gọi là yếu nếu: Với y cho trước và không có biến đầu vào tương ứng thì không có khả năng tính toán để tìm thông điệp x sao cho: h(x) = y Cho một thông điệp x thì về mặt tính toán không tìm ra được thông điệp x’ khác x sao cho: h(x’) = h(x) Hàm băm mạnh: Hàm băm h được gọi là mạnh nếu: Cho một thông điệp x thì về mặt tính toán không tìm ra được thông điệp x’ khác x sao cho: h(x’) = h(x) Không có khả năng về mặt tính toán để tìm hai thông điệp khác nhau bất kỳ x và x’ sao cho: h(x) = h(x’) 1.3 Chuẩn hàm băm an toàn 1.3.1. Giới thiệu Chuẩn hàm băm an toàn SHS-FIPS PUB 180 (Secure Hash Standard) được NIST đưa ra lần đầu vào 11/5/1993. Nội dung chỉ có một giải thuật hàm băm được đưa ra là SHA-1. Và phiên bản thứ 2 của chuẩn hàm băm an toàn là FIPS PUB 180-2, được đưa ra vào ngày 1/8/2002. Trong FIPS PUB 180-2 chỉ rõ 4 giải thuật hàm băm an toàn là SHA-1, SHA-256, SHA-384, and SHA-512. Cả 4 giải thuật này đều là các hàm băm một chiều có thể xử lý thông điệp để tạo ra một thông điệp thu gọn của thông điệp ban đầu. Các giải thuật này đều đảm bảo được tính toàn vẹn của thông điệp: bất cứ sự thay đổi nào với thông điệp M thì đều dẫn tới sự thay đổi của thông điệp rút gọn H(M)- với một xác suất là rất lớn. Đặc điểm này rất có ích trong việc tạo và xác nhận chữ ký số cũng như trong việc tạo ra các số ngẫu nhiên. Mỗi một giải thuật đều gồm 2 bước: bước tiền xử lý và bước tính toán băm. Bước tiền xử lý bao gồm các công việc như độn tin, chia khối, thiết lập giá tri khởi tạo dùng cho tính toán băm. Bước tính toán băm sẽ tạo ra một danh sách thông định sẵn từ bản tin độn và sử dụng cơ chế đó với các hàm, hằng và các phép toán để tạo ra một chuỗi các giá trị băm. Giá trị băm cuối cùng được tạo bởi bước tính toán băm sẽ chính là thông điệp rút gọn. Bốn giải thuật này khác nhau chủ yếu ở số bít bảo mật. Số bít bảo mật có liên quan trực tiếp tới độ dài của thông điệp rút gọn. Khi một giải thuật hàm băm được sử dụng cùng với một giải thuật khác thì ta cần phải chỉ ra hàm băm cần sử dụng có số bít bảo mật là bao nhiêu. Ví dụ, nếu một thông điệp được ký bằng giải thuật chữ ký số với 128 bít bảo mật thì giải thuật chữ ký số đó có thể yêu cầu sử dụng một hàm băm an toàn có 128 bít bảo mật (ví dụ SHA-256). Ngoài ra, 4 giải thuật khác nhau ở kích thước của khối và từ dữ liệu được dùng trong quá trình băm. Bảng dưới đây sẽ trình bày các đặc điểm cơ bản của 4 giải thuật hàm băm an toàn. Giải thuật Kích thước thông điệp (bits) Kích thước khối (bits) Kích thước từ (bits) Kích thước thông điệp thu gọn (bits) Bit an toàn (bits) SHA-1 < 264 512 32 160 80 SHA-256 < 264 512 32 256 128 SHA-384 < 2128 1024 64 384 192 SHA-512 < 2128 1024 64 512 256 Bảng 2.1. Đặc điểm của các giải thuật hàm băm an toàn. 1.3.2. Các hàm sử dụng trong SHA Trong quá trình tính toán băm thì mỗi một giải thuật hàm băm sẽ sử dụng các hàm được định sẵn cho từng giải thật như sau: Các hàm của SHA-1: SHA-1 sử dụng một danh sách các hàm logic f0, f1,…, f79. Mỗi hàm toán học ft, trong đó 0 ≤ t ≤ 79 đều được thực hiện trên các từ dữ liệu 32 bít x, y, z và đầu ra của nó cũng là một từ có kích thước 32 bít. Hàm ft(x, y, z) được định nghĩa như sau: ft (x, y, z) = (2.1) Các hàm của SHA-256: SHA-256 sử dụng 6 hàm logic, trong đó mỗi hàm đều thực hiện trên các từ 32 bít được biểu diễn bởi x, y, z. Kết quả đầu ra của các hàm cũng đều là từ nhớ 32 bít. Ch( x, y, z) = ( x y) (x z) (2.2) Maj( x, y, z) = ( x y) ( x z) ( y z) (2.3) (2.4) (2.5) (2.6) (2.7) Các hàm của SHA-384 và SHA-512: SHA-384 và SHA-512 đều sử dụng 6 hàm logic, trong đó mỗi hàm đều thực hiện trên các từ 64 bít x, y, z. Kết quả đầu ra của các hàm này cũng đều là một từ 64 bít. Ch( x, y, z) = ( x y) (x z) (2.8) Maj( x, y, z) = ( x y) ( x z) ( y z) (2.9) (2.10) (2.11) (2.12) (2.13) 1.3.3 Các hằng được sử dụng trong SHA Các hằng của SHA-1: SHA-1 sử dụng một dãy 80 hằng 32 bít K0, K1,…, K79. Công thức tính chúng như sau: (2.14) Các hằng của SHA-256: SHA-256 sử dụng 64 hằng số 32 bít như sau: K0{256}, K1{256},… , K63{256} . Dưới đây là 64 hằng số của SHA-256 biểu diễn ở dạng hexa: 428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5 d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174 e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da 983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967 27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85 a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070 19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3 748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2 Các hằng của SHA-384 và SHA-512: SHA-384 và SHA-512 cùng sử dụng một dãy 80 hằng số 64 bít K0{512}, K1{512},…, K79{512}. Dưới đây là 80 hằng số của SHA-384 và SHA-512 biểu diễn ở dạng hexa: 428a2f98d728ae22 7137449123ef65cd b5c0fbcfec4d3b2f e9b5dba58189dbbc 3956c25bf348b538 59f111f1b605d019 923f82a4af194f9b ab1c5ed5da6d8118 d807aa98a3030242 12835b0145706fbe 243185be4ee4b28c 550c7dc3d5ffb4e2 72be5d74f27b896f 80deb1fe3b1696b1 9bdc06a725c71235 c19bf174cf692694 e49b69c19ef14ad2 efbe4786384f25e3 0fc19dc68b8cd5b5 240ca1cc77ac9c65 2de92c6f592b0275 4a7484aa6ea6e483 5cb0a9dcbd41fbd4 76f988da831153b5 983e5152ee66dfab a831c66d2db43210 b00327c898fb213f bf597fc7beef0ee4 c6e00bf33da88fc2 d5a79147930aa725 06ca6351e003826f 142929670a0e6e70 27b70a8546d22ffc 2e1b21385c26c926 4d2c6dfc5ac42aed 53380d139d95b3df 650a73548baf63de 766a0abb3c77b2a8 81c2c92e47edaee6 92722c851482353b a2bfe8a14cf10364 a81a664bbc423001 c24b8b70d0f89791 c76c51a30654be30 d192e819d6ef5218 d69906245565a910 f40e35855771202a 106aa07032bbd1b8 19a4c116b8d2d0c8 1e376c085141ab53 2748774cdf8eeb99 34b0bcb5e19b48a8 391c0cb3c5c95a63 4ed8aa4ae3418acb 5b9cca4f7763e373 682e6ff3d6b2b8a3 748f82ee5defb2fc 78a5636f43172f60 84c87814a1f0ab72 8cc702081a6439ec 90befffa23631e28 a4506cebde82bde9 bef9a3f7b2c67915 c67178f2e372532b ca273eceea26619c d186b8c721c0c207 eada7dd6cde0eb1e f57d4f7fee6ed178 06f067aa72176fba 0a637dc5a2c898a6 113f9804bef90dae 1b710b35131c471b 28db77f523047d84 32caab7b40c72493 3c9ebe0a15c9bebc 431d67c49c100d4c 4cc5d4becb3e42b6 597f299cfc657e2a 5fcb6fab3ad6faec 6c44198c4a475817 1.3.4 Tiền xử lý Bước tiền xử lý được thực hiện trước khi tính toán băm được bắt đầu. Tiền xử lý bao gồm 3 bước: độn tin, phân khối bản tin độn và cuối cùng là thiết lập giá trị băm khởi tạo H(0). a. Độn bản tin Một bản tin hay thông điệp M trước khi tính toán băm sẽ được độn thêm bít nhằm đảm bảo bản tin sau khi độn (bản tin độn) có kích thước là một bội số của 512 hoặc 1024 bit (kích thước này phụ thuộc vào giải thuật được sử dụng). Với SHA-1 và SHA-256 Giả thiết rằng chiều dài của bản tin M ban đầu là l bít. Cách độn bản tin sẽ được tiến hành như sau: đầu tiên, ta thêm một bít “1” vào cuối bản tin và ngay tiếp sau bít “1” vừa được thêm vào này, ta thêm k bít “0” liên tiếp, trong đó k là số nguyên nhỏ nhất thỏa mãn l + 1 +k ≡ 448 mod 512. Sở dĩ l +1+k ≡ 448 mod 512 là vì khối 64 bít cuối cùng đã được dành ra để lưu thông tin về kích thước l của bản tin ban đầu. Ví dụ với bản tin hệ mã ASCII-8 bít có nội dung là “abc” thì chiều dài của bản tin này sẽ là l = 8.3 = 24 bít. Vì bản tin được độn thêm một bít “1” nên số bít “0” cần độn thêm vào bản tin sẽ là 448 - (24 +1) = 423. Như vậy từ một bản tin M ban đầu có kích thước là 24 bít, bằng việc độn thêm bít như này, ta thu được một bản tin độn có kích thước là 512 bít, thỏa mãn là bội số của 512. Với SHA-384 và SHA-512. Giả sử rằng chiều dài của bản tin M ban đầu là l bít. Các độn bản tin sẽ được tiến hành như sau: đầu tiên, ta thêm một bít “1” vào cuối bản tin và ngay tiếp sau bít “1” vừa được thêm vào này, ta thêm k bít “0” liên tiếp, trong đó k là số nguyên nhỏ nhất thỏa mãn l + 1+ k ≡ 896 mod 1024. Sở dĩ l+1+ k ≡ 896 mod 1024 là vì khối 128 bít cuối cùng đã được dành ra để lưu thông tin về kích thước l của bản tin ban đầu. Ví dụ với bản tin hệ mã ASCII-8 bít có nội dung là “abc” thì chiều dài của bản tin này sẽ là l = 8.3 = 24 bít. Vì bản tin được độn thêm một bít “1” nên số bít “0” cần độn thêm vào bản tin sẽ là 896 - (24 + 1) = 871. Như vậy từ một bản tin M ban đầu có kích thước là 24 bít, bằng việc độn thêm bít như này, ta thu được một bản tin độn có kích thước là 1024 bít, thỏa mãn là bội số của 1024. b. Phân phối bản tin độn Sau khi bản tin được độn thêm bít, nó cần phải được phân ra thành N khối m-bít trước khi quá trình tính toán băm được bắt đầu. SHA-1 và SHA-256. Với SHA-1 and SHA-256, bản tin độn sẽ được phân ra thành N khối 512 bít: M(1), M(2),…, M(N). Mỗi khối tin M(i) biểu diễn 16 từ-32 bít: M0(i), M1(i),…, M15(i). SHA-384 và SHA-512. Với SHA-384 và SHA-512, bản tin độn được phân ra thành N khối 1024 bít. M(1), M(2),…, M(N). Mỗi khối tin M(i) có độ lớn 1024 bít có thể biểu diễn thánh 16 từ-64 bít M0(i), M1(i),…, M15(i). c. Thiết lập giá trị băm khởi tạo-H(0) Trước khi thực hiện tính toán băm cho mỗi một giải thuật băm, giá trị băm khởi tạo-H(0) cần phải được khởi tạo. Kích thước và số lượng từ của H(0) phụ thuộc vào kích thước của thông điệp rút gọn. SHA-1. Với SHA-1, giá trị băm khởi tạo H(0) bao gồm 5 từ 32 bít sau: SHA-256. Với SHA-256, giá trị băm khởi tạo H(0) bao gồm 8 từ 32 bít sau: H= 6a09e667 H= bb67ae85 H= 3c6ef372 H= a54ff53a H= 510e527f H= 9b05688c H= 1f83d9ab H= 5be0cd19 SHA-384. Với SHA-384, giá trị băm khởi tạo H(0) bao gồm 8 từ-64 bít sau: SHA-512. Với SHA-512, giá trị băm khởi tạo H(0) bao gồm 8 từ-64 bít sau: 1.3.5. Các giải thuật hàm băm an toàn Trong phần này, em xin trình bày giải thuật SHA-512 trước giải thuật SHA-384 bởi vì giải thuật SHA-384 giống hệt giải thuật SHA-512, chỉ có giá trị băm khởi tạo là khác và giá trị băm cuối cùng được cắt lấy 384 bít chứ không phải lấy toàn bộ 512 bít như giải thuật SHA-512 để tạo ra thông điệp rút gọn. Mỗi giải thuật băm an toàn đều có các phương pháp tính luân phiên để tạo ra kết quả. a. SHA-1 SHA-1 có thể được dùng để tính băm cho các thông điệp M có độ dài là l bít với 0 ≤ l < 264 . Giải thuật sử dụng: Một danh sách thông định sẵn gồm 80 từ-32 bít. Năm biến làm việc có độ dài 32 bít. Một giá trị băm bao gồm 5 từ-32 bít. Kết quả cuối cùng của giải thuật SHA-1 là một thông điệp rút gọn 160 bít. Các từ của danh sách thông định sẵn được đánh nhãn là W0, W1,…, W79. Năm biến làm việc là a, b, c, d và e. Các từ của giá trị băm được gán nhãn là H0(i), H1(i), …, H4(i) trong đó giá trị băm khởi tạo H(0) liên tiếp được thay thế bởi các giá trị băm trung gian H(i) cho đến giá trị băm cuối cùng H(N). Ngoài ra SHA-1 còn sử dụng một biến trung gian T có kích thước bằng một từ 32 bít. Qui trình tiền xử lý của SHA-1. 1. Độn tin cho bản tin M. 2. Phân bản tin M ra thành N khối 512 bít M(1), M(2), …, M(N). 3. Thiết lập giá trị khởi tạo H(0). Qui trình tính toán băm của SHA-1. Để tính toán băm, giải thuật SHA-1 sử dụng các hàm và các hằng số được cho trong mục 2.3.2 và 2.3.3. Phép cộng (+) được thực hiện trên modulo 232. Sau khi tiền xử lý, mỗi khối tin M(1), M(2), …, M(N) được xử lý lần lượt theo các bước sau: For i = 1 to N: { Chuẩn bị danh sách thông định sẵn {Wt}: Khởi tạo 5 biến hoạt động a, b, c, d và e ứng với giá trị băm thứ (i-1). a = H0(i-1) b = H1(i-1) c = H2(i-1) d = H3(i-1) e = H4(i-1) For t = 0 to 79: { T = ROTL5(a) + ft(b, c, d) +e + Kt + Wt e = d d = c c = ROTL30(b) b = a a = T } Tính giá trị băm trung gian thứ i - H(i) H0(i) = a + H0(i-1) H1(i) = b + H1(i-1) H2(i) = c + H2(i-1) H3(i) = d + H3(i-1) H4(i) = e + H4(i-1) } Sau khi lặp lại các bước từ (1) tới (4) là N lần, thông điệp rút gọn 160 bít của M sẽ là H0(N) || H1(N) || … || H4(N) b. SHA-256. SHA-256 có thể được dùng để tính băm cho các thông điệp M có độ dài là l bít với 1 ≤ l ≤ 264. Giải thuật SHA-256 sử dụng 1. Một danh sách thông định sẵn gồm 64 từ-32 bít.: 2. Tám biến hoạt động có độ dài 32 bít. 3. Một giá trị băm gồm 8 từ-32 bít. Kết quả cuối cùng của giải thuật SHA-256 là thông điệp rút gọn dài 256 Các từ của danh sách thông định sẵn được gán nhãn là W0, W1,…, W63. Tám biến hoạt động đặt tên là a, b, c, d, e, f, g và h. Các từ của giá trị băm được gán nhãn là H0(i), H1(i), …, H7(i) trong đó giá trị băm khởi tạo H(0) sẽ được thay thế liên tiếp bằng các giá trị băm trung gian H(i) cho đến giá trị băm cuối cùng là H(N). SHA-256 còn sử dụng hai biến trung gian T1 và T2 có độ lớn là 32 bít. Qui trình tiền xử lý của SHA-256. 1. Độn tin cho bản tin M. 2. Phân bản tin M ra thành N khối 512 bít M(1), M(2), …, M(N). 3. Thiết lập giá trị khởi tạo H(0). Qui trình tính toán băm của SHA-256. SHA-256 sử dụng các hàm và các hằng số được mô tả trong phần 2.3.2 và 2.3.3 để tính toán băm. Phép toán cộng (+) được thực hiện theo modulo 232. Sau bước tiền xử lý, từng khối tin M(1), M(2), …, M(N) sẽ được xử lý tuần tự theo các bước sau: For i = 1 to N: { Chuẩn bị danh sách thông định sẵn, {Wt}: Khởi tạo 8 biến hoạt động a, b, c, d, e, f, g và h với giá trị băm thứ (i-1) a = H0(i-1) b = H1(i-1) c = H2(i-1) d = H3(i-1) e = H4(i-1) f = H5(i-1) g = H6(i-1) h = H7(i-1) For t = 0 to 63: { T1 = h + T2 = + Ch(e, f, g) + Kt{256} + Wt h = g g = f f = e e = d + T1 d = c c = b a = T1+ T2 } Tính toán giá trị băm trung gian thứ i (H(i)) H0(i) = a + H0(i-1) H1(i) = b + H1(i-1) H2(i) = c + H2(i-1) H3(i) = d + H3(i-1) H4(i) = e + H4(i-1) H5(i) = g + H5(i-1) H6(i) = f + H6(i-1) H7(i) = h + H7(i-1) } Sau khi lặp lại N lần các bước từ (1) tới (4) thì ta thu được thông điệp rút gọn 256 bít của thông điệp M là: H0(N) || H1(N) || H2(N) || H3(N) || H4(N) || H5(N) || H6(N) || H7(N) c. SHA-512. SHA-512 có thể được dùng để tính băm cho các thông điệp M có độ dài là l bít với 1 ≤ l ≤ 2128. Giải thuật SHA-512 sử dụng: 1. Một danh sách thông định sẵn gồm 80 từ-64 bít. 2. Tám biến hoạt động có độ dài 64 bít. 3. Một giá trị băm gồm 8 từ-64 bít. Kết quả cuối cùng của giải thuật SHA-512 là thông điệp rút gọn dài 512 bít. Các từ của danh sách thông định sẵn được gán nhãn là W0, W1,…, W79. Tám biến hoạt động đặt tên là a, b, c, d, e, f, g và h. Các từ của giá trị băm được gán nhãn là H0(i), H1(i), …, H7(i) trong đó giá trị băm khởi tạo H(0) sẽ được thay thế liên tiếp bằng các giá trị băm trung gian H(i) cho đến giá trị băm cuối cùng là H(N). SHA-512 cũng sử dụng hai biến trung gian T1 và T2 nhưng có độ lớn là 64 bít. Qui trình tiền xử lý của SHA-512. 1. Độn tin cho bản tin M. 2. Phân bản tin M ra thành N khối 1024 bít M(1), M(2), …, M(N). 3. Thiết lập giá trị khởi tạo H(0). Qui trình tính toán băm của SHA-512. SHA-512 sử dụng các hàm và các hằng số được mô tả trong phần 2.3.2 và 2.3.3 để tính toán băm. Phép toán cộng (+) được thực hiện theo modulo 264. Sau bước tiền xử lý, từng khối tin M(1), M(2), …, M(N) sẽ được xử lý tuần tự theo các bước sau: For i = 1 to N: { Chuẩn bị danh sách thông định sẵn, {Wt}: Khởi tạo 8 biến hoạt động a, b, c, d, e, f, g và h với giá trị băm thứ (i-1) a = H0(i-1) b = H1(i-1) c = H2(i-1) d = H3(i-1) e = H4(i-1) f = H5(i-1) g = H6(i-1) h = H7(i-1) For t = 0 to 79: { T1 = h + + Ch(e, f, g) + Kt{512} + Wt T2 = h + + Ch(e, f, g) + Kt{512} + Wt h = g g = f f = e e = d + T1 d = c c = b b = a a = T1 + T2 } Tính toán giá trị băm trung gian thứ i (H(i)) H0(i) = a + H0(i-1) H1(i) = b + H1(i-1) H2(i) = c + H2(i-1) H3(i) = d + H3(i-1) H4(i) = e + H4(i-1) H5(i) = g + H5(i-1) H6(i) = f + H6(i-1) H7(i) = h + H7(i-1) } Sau khi lặp lại N lần các bước từ (1) tới (4) thì ta thu được thông điệp rút gọn 512 bít của thông điệp M là: H0(N) || H1(N) || H2(N) || H3(N) || H4(N) || H5(N) || H6(N) || H7(N). d. SHA-384 SHA-384 có thể được dùng để tính băm cho các thông điệp M có độ dài l bít với 0 ≤ l ≤ 2128. Giải thuật này được định nghĩa giống y hệt với giải thuật SHA-512 trừ hai điểm khác biệt duy nhất sau: 1. Giá trị băm khởi tạo H(0) của SHA-384 khác với giá trị khởi tạo H(0) của SHA-512. 2. Thông điệp rút gọn của SHA-384 có độ dài là 384-bít chứ không phải là 512 bít như của SHA-512. Bởi vì ở khâu cuối cùng, nó chặt bớt 128 bít bên phải của giá trị băm cuối cùng H(N), và chỉ giữ lại 384 bít trái nhất của giá trị băm cuối cùng đó để tạo ra thông điệp rút gọn là: H0(N) || H1(N) || H2(N) || H3(N) || H4(N) || H5(N) thay vì là giữ nguyên toàn bộ tất cả các bít (hay các từ) của H(N) như SHA-512. Chương 2 CHUẨN CHỮ KÝ SỐ (DSS – FIPS PUB 186-3) 2.1. Giới thiệu Để nâng cấp việc sử dụng thương mại điện tử của quốc gia và trong việc giao dịch, Viện tiêu chuẩn và công nghệ quốc gia Hoa kỳ (NIST) đã đưa ra chuẩn xử lý thông tin FIPS 186 là chuẩn chữ ký số (DSS- Digital Signature Standard) vào ngày 19/5/1994 và được chấp nhận từ ngày 1/12/1994. Phiên bản đầu tiên của chuẩn chữ ký số là FIPS PUB 186, phiên bản tiếp theo là FIPS PUB 186-1 được đưa ra vào ngày 15/12/1998, phiên bản thứ 3 là FIPS PUB 186-2 đưa ra vào ngày 27/1/2000 và phiên bản mới nhất hiện nay là FIPS PUB 186-3 được công bố vào tháng 3/2006. Bảng dưới đây so sánh sự khác nhau giữa các phiên bản đã có của DSS. Phiên bản Giá trị cặp (L,N) (bits) Nội dung Chuẩn hàm băm sử dụng FIPS PUB 186 L [512,1024] N [159,160] Giải thuật DSA Chưa có FIPS PUB 186-1 L [512,1024] N [159,160] Giải thuật DSA FIPS 180-1 FIPS PUB 186-2 L [512,1024] N [159,160] Giải thuật DSA Giải thuật ECDSA FIPS 180-1 FIPS PUB 186-3 L = 1024, N = 160 L = 2048, N = 224 L = 3072, N = 256 Giải thuật DSA Giải thuật RSA Giải thuật ECDSA FIPS 180-2 Bảng 3.1 Sự khác nhau giữa các phiên bản DSS Trong phần tiếp theo em xin trình bày về giải thuật DSA trong phiên bản FIPS PUB 186-3. Một hàm băm sẽ được sử dụng tương ứng trong giải thuật tạo và xác thực chữ ký, nhằm giảm bớt độ dài thông điệp ký. Sơ đồ sau thể hiện việc sử dụng hàm băm trong giải thuật tạo và xác nhận chữ ký số. Khóa bí mật Hàm băm Thông điệp Thông điệp rút gọn Thuật toán tạo chữ ký số Chữ ký số Tạo chữ ký số Hàm băm Thông điệp Thông điệp rút gọn Khóa công khai Thuật toán xác nhận chữ ký số Hợp lệ / không hợp lệ Xác nhận chữ ký số Hình 3.1. Sơ đồ sử dụng giải thuật hàm băm trong giải thật chữ ký số 2.3. Giải thuật chữ ký số 2.3.1. Các tham số của DSA Chữ ký số DSA được tính toán dựa trên một tập các tham số miền, khóa bí mật, số bí mật của mỗi thông điệp, dữ liệu để ký và một hàm băm. Việc xác nhận chữ ký số cũng dựa trên tập các tham số miền và khóa công khai này, dựa trên dữ liệu dùng để xác nhận và hàm băm đã dùng để tạo ra chữ ký. Các tham số này là: p: là một số nguyên tố trong đó 2L-1 < p < 2L với L là độ dài bit của biến p. q: là một ước số nguyên tố của p-1 trong đó 2N-1< p < 2N với N là chiều dài của biến q(tính theo bít). g: là căm bậc q của 1 theo modulo p. Dễ dàng tính được g như sau: g = h(p-1)/q mod p. Với 1< h < p-1 x: là khóa bí mật. x là một số nguyên dương được tạo ra một cách ngẫu nhiên sao cho 0< x < q-1. y: là khóa công khai, trong đó y = gx mod p. k: là số bí mật và là duy nhất với mỗi một tin nhắn. k là số nguyên được tạo ra ngẫu nhiên sao cho 0 < k < q. 2.3.2. Lựa chọn kích thước tham số và hàm băm cho DSA Chuẩn này có đưa ra một số các lựa chọn cho cặp (L, N) như sau: (L = 1024, N = 160), (L = 2048, N = 224) và (L = 3072, N = 256) Quá trình tạo chữ ký số sẽ sử dụng tới một hàm băm. Độ an toàn của hàm băm này phải bằng hoặc lớn hơn độ an toàn của cặp (L,N). Người ta khuyến cáo rằng độ an toàn của cặp (L, N) và của hàm băm là như nhau trừ khi có một sự thỏa thuận giữa các bên tham gia nhằm sử dụng một hàm băm mạnh. Những hàm băm có độ an toàn nhỏ hơn độ an toàn của cặp (L, N) sẽ không được sử dụng. Nếu đầu ra của hàm băm có chiều dài là T > N bít thì N bít trái nhất của nó sẽ được sử dụng (thay cho T bít đầu ra như thường lệ) trong mọi tính toán của qui trình tạo và xác nhận chữ ký số. Mỗi cặp (L, N) được lựa chọn sao cho nó có thể bảo vệ được thông tin trong toàn bộ quãng thời gian sống của thông tin. Ví dụ nếu chữ ký số được tạo ra năm 2007 cho thông tin cần được bảo vệ trong 5 năm thì cặp (L, N) được chọn phải đủ lớn để có thể bảo vệ được thông tin trong suốt 5 năm đó. Sau đây là bảng lựa chọn hàm băm cho từng cặp (L, N) Cặp L, N (bits) Bit an toàn (bits) Hàm băm L = 1024 N = 160 80 SHA-1 SHA-256 SHA-384 SHA-512 L = 2048 N = 224 112 SHA-256 SHA-384 SHA-512 L = 3072 N = 256 128 SHA-256 SHA-384 SHA-512 Bảng 3.1. Lựa chọn hàm băm cho cặp (L, N) 2.3.3. Các tham số miền của DSA Giải thuật DSA qui định cặp khóa được sử dụng cho quá trình tạo và xác nhận chữ ký số phải được tạo ra dựa trên tập các tham số miền của DSA. Các tham số miền này có thể được một nhóm người hoặc cả cộng đồng biết tới. Người sử dụng tập tham số này sẽ phải đảm bảo tính hợp lệ của chúng trước khi sử dụng chúng. Mặc dù các tham số này có thể là công khai nhưng chúng vẫn cần phải được quản lý nhằm bảo vệ sự phù hợp tương ứng giữa cặp khóa và các tham số miền cho tất cả các bên sử dụng cặp khóa. Với chuẩn DSA, tham số miền gồm có các số nguyên p, q, g và domain_parameter_seed - tham số gốc, counter - bộ đếm (nếu có yêu cầu) đã sử dụng để tạo ra p, q. Như vậy bộ tham số miền đầy đủ sẽ là (p, q, g { domain_parameter_seed, counter}). Tạo các tham số miền Các tham số miền có thể do một bên ủy nhiệm thứ 3 hoặc do một thực thể nào đó tạo ra. Việc xác nhận đảm bảo tính hợp lệ của chúng sẽ được tiến hành trước khi tạo khóa cũng như trước khi tạo và xác chữ ký số. Việc tạo p, q sẽ được trình bày chi tiết trong mục 3.4. Qui trình tạo p, q có đầu vào là các giá trị L, N - là độ dài tương ứng của các số p, q cần tạo ra và có đầu ra là giá trị của p, q cũng như các biến domain_parameter_seed, counter (nếu cần). Trong mục 3.4 em cũng trình bày chi tiết qui trình tạo tham số g. Quản lý các tham số miền Bởi vì cặp khóa được tạo ra dựa trên tập các tham số miền nên giữa chúng có một sự gắn kết chặt chẽ. Chính vì vậy các tham số miền sau khi được tạo ra cần phải được quản lý để tránh việc chỉnh sửa bất hợp pháp cho đến khi chúng không còn được sử dụng nữa. 2.3.4. Cặp khóa Mỗi một người ký đều sở hữu một cặp khóa bao gồm khóa bí mật x và khóa công khai y, và chúng có quan hệ toán học qua lại lẫn nhau. Trong đó khóa bí mật chỉ sử dụng khi tạo chữ ký số còn khóa công khai vẫn tiếp tục được sử dụng khi chữ ký số vẫn còn cần xác nhận. Tạo cặp khóa. Cặp khóa (x, y) được tạo ra dựa trên tập các tham số miền (p, q, g { domain_parameter_seed, counter}) và giải thuật tạo khóa được trình bày cụ thể trong mục 3.5. Quản lý cặp khóa. Quản lý cặp khóa là một công việc thiết yếu và quan trọng. Việc sử dụng chữ ký số có được an toàn hay không là phụ thuộc vào việc quản lý cặp khóa, cụ thể như sau: Các tham số miền cần phải đuợc đảm bảo trước khi tạo cặp khóa cũng như trước khi xác nhận và kiểm chứng chữ ký số. Mỗi cặp khóa cần phải được gắn liền với một tập các tham số miền nhất định mà dựa trên đó, cặp khóa được tạo ra. Cặp khóa chỉ đuợc sử dụng để tạo và xác nhận chữ ký số bằng cách sử dụng các tham số miền gắn kết với nó. Khóa bí mật chỉ được sử dụng để tạo ra chữ ký số và sau đó, nó phải được giữ bí mật. Còn khóa công khai chỉ được sử dụng để xác nhận chữ ký số và được công khai cho mọi người biết. Bên định ký cần phải chắc chắn sở hữu khóa bí mật trước hoặc lúc dùng nó để tạo ra chữ ký số. Khóa bí mật cần phải được bảo vệ tránh các truy cập, giả mạo và chỉnh sửa bất hợp pháp. Khóa công khai cần phải được bảo về tránh việc chỉnh sửa bất hợp pháp (bao gồm cả trường hợp thay thế). Người xác nhận cần phải chắc chắn về quan hệ ràng buộc giữa khóa công khai, các tham số miền của nó và người sở hữu cặp khóa. Người xác nhận cần phải có được khóa công khai theo một cách thức đáng tin cậy. Người xác nhận cũng cần phải đảm bảo được rằng người tuyên bố là mình đã ký lên thông điệp phải là người sở hữu cặp khóa và rằng người sở hữu này phải nắm giữ khóa bí mật đã được dùng để tạo ra chữ ký số vào thời điểm chữ ký được tạo ra (khóa bí mật phải gắn chặt với khóa công khai mà sẽ được dùng để xác nhận chữ ký số). Người ký và người xác nhận cần phải đảm bảo chắc chắc về tính hợp lệ của khóa công khai. 2.3.5. Số bí mật cho mỗi thông điệp Trước khi ký lên một thông điệp thì bên ký sẽ cần phải tạo ra một số nguyên k một cách ngẫu nhiên. Số k này sẽ được dùng để tạo ra chữ ký cho thông điệp đó và nó sẽ được giữ bí mật. Ngoài ra, qui trình tạo tạo chữ ký số còn sử dụng phần tử nghịch đảo k-1 của k (theo modulo q). Cả k và k-1 đều có thể được tính trước khi người ký biết mình cần ký lên thông điệp nào, bởi vì k và k-1 được tạo ra một cách ngẫu nhiên, độc lập với thông điệp cần ký. Phương pháp tạo ra số bí mật k này được trình bày cụ thể trong mục 3.5. 2.3.6. Tạo chữ ký số DSA Trước khi tạo ra chữ ký cho thông điệp, bên định ký sẽ phải thực hiện thủ tục cài đặt ban đầu để thu được các tham số cần thiết cũng như đảm bảo tính hợp lệ của chúng để tạo ra được chữ ký. Chữ ký trên thông điệp M là một cặp số (r, s) được tính toán như sau: r = (gk mod p) mod q. Với p, q là nguyên tố, gq ≡ 1 mod q và k là số bí mật được tạo ngẫu nhiên cho thông điệp. s = k-1(z + x.r) mod q. z = N bít trái nhất của hàm Hash(M). Trong bước tính s, kết quả đầu ra của hàm Hash(M) sẽ được chuyển từ dạng chuỗi sang dạng số nguyên tương ứng. Sau đó giá trị của r và s sẽ được kiểm tra để xem chúng có bằng 0 hay không. Nếu một trong hai giá trị này bằng không thì bên ký sẽ phải tạo ra một giá trị k khác và chữ ký số sẽ phải được tính toán loại. Tuy nhiên rất hiếm khi r và s bằng 0 nếu như qui trình tạo chữ ký được thực hiện một cách đúng đắn. Chữ ký số (r,s) này có thể sẽ được truyền đi kèm với thông điệp cho người xác nhận. 2.3.7. Kiểm tra và xác thực chữ ký DSA Bất kỳ ai cũng có thể xác nhận được chữ ký điện tử bằng cách sử dụng khóa công khai của người ký. Bên ký có thể tiến hành xác nhận lại chữ ký của mình trước khi gửi thông điệp cho người nhận và sau đó bên nhận sẽ xác nhận chữ ký trên thông điệp để đảm bảo tính xác thực của chữ ký. Trước khi xác nhận chữ ký trên thông điệp thì các tham số miền, khóa công khai của người đã tạo ra chữ ký đó cũng như các đặc điểm nhận dạng của người tự nhận này phải sẵn dùng và có hiệu lực cho người xác nhận chữ ký. Đặt M’, r’, s’ là thông điệp và chữ ký cần đi xác nhận. Đặt y là khóa công khai của người tuyên bố đã tạo ra chữ ký, N là chiều dài của q. Qui trình xác nhận chữ ký được thực hiện như sau: Kiểm tra xem 0 < r’< q và 0 < s’ < q không. Nếu một trong hai điều kiện này không thỏa mãn thì chữ ký số bị coi là không hợp lệ. Nếu cả hai điều kiện trong bước 1 đều thỏa mãn thì người xác nhận sẽ đi thực hiện tiếp như sau: w = (s’)-1 mod q. z = N bít trái nhất của Hash(M’). u1 = z.w mod q. u2 = r’.w mod q. v = (g. y mod p) mod q. Nếu v = r’ thì chữ ký số được xác nhận. Bởi vì v = r’ chỉ khi M = M’, r’ = r và s’= s. Nếu v khác r’ thì có thể là do thông điệp hoặc chữ ký số đã bị chỉnh sữa, hoặc là qui trình tạo chữ ký số đã mắc lỗi, hoặc cũng có thể là bởi vì một kẻ giả danh đã cố gắng giả mạo chữ ký trong khi lại không biết khóa bí mật của người ký. Tuy nhiên, dù là nguyên nhân nào thì chữ ký số đều bị coi là không hợp lệ. Trước khi xác nhận là chữ ký hợp lệ thì người xác nhận cần phải thực hiện các đảm bảo cần thiết như đã nói trong mục 3.3. 2.3.8. Chứng minh giải thuật DSA. Ta có: v = (g. y mod p) mod q = (gz.w mod q. yr’.w mod q mod p) mod q = (gz.w mod q. gx.r’.w mod q mod p) mod q = (g(z+x.r’)w mod q mod p) mod q Mà s = k-1(z + x.r) mod q s-1 = k(z + x.r)-1 mod q Vậy nếu s = s’, r = r’, M = M’ thì v = (g(z+x.r’).k.(z + x.r)mod q mod p) mod q = (gk mod q mod p) mod q = r = r’ 2.3.9. Đánh giá giải thuật DSA DSA dựa vào sơ đồ chữ ký ElGamal, với một vài sửa đổi. Vì vậy tính bảo mật của DSA cũng dựa trên độ khó của bài toán logarit rời rạc. Để bảo đảm an toàn, số nguyên tố p cần phải đủ lớn, trong phiên bản này thì p nhỏ nhất có độ dài biểu diễn nhị phân là 1024 bit. Nếu p có độ lớn 1024 bit thì với sơ đồ ký RSA hoặc ElGamal đã trình bày trong chương 1 thì chữ ký sẽ có độ dài là 1024 bit và 2048 bit, nhưng thực tế nhiều ứng dụng lại cần có chữ ký ngắn hơn vì thế DSA với một vài sửa đổi so với sơ đồ ký ElGamal thì chữ ký chỉ còn độ dài là 320 bit. Việc xác thực chữ ký của DSA chậm hơn so với quá trình tạo chữ ký. Nhưng lại có nhiều ứng dụng chỉ cần tạo chữ ký một lần sau đó việc xác thực lại được dùng nhiều lần và với một thời gian dài như vậy sử dụng DSA cho những ứng dụng này không phải là một lợi thế. Ví dụ nếu dùng giải thuật RSA làm sơ đồ chữ ký và với số mũ bé thì việc xác thực sẽ nhanh hơn rất nhiều so với việc tạo chữ ký. 2.4. Tạo và xác nhận tham số miền 2.4.1. Tạo các số nguyên tố p và q a. Tạo số nguyên tố p và q bằng việc sử dụng hàm băm Phương pháp này sử dụng một hàm băm phải có độ an toàn bằng hoặc lớn hơn độ an toàn của cặp (L, N). Tuy nhiên người ta khuyến cáo rằng độ an toàn của hàm băm và của cặp (L, N) sẽ là như nhau trừ khi có một sự thỏa thuận giữa các bên tham gia nhằm sử dụng một hàm băm mạnh. Tham số gốc domain_parameter_seed có độ dài là seedlen bit, trong đó seedlen ≥ N. Qui trình này sẽ trả về cặp 2 số nguyên p và q có xác suất là nguyên tố rất cao. Để giúp cho người xác nhận có thể xác nhận được chính xác chúng thì giá trị của tham số domain_parameter_seed và counter sử dụng trong quá trình tạo p, q sẽ được trả về trong đó domain_parameter_seed và counter không cần thiết phải giữ bí mật. Đặt Hash() là hàm băm được lựa chọn phù hợp với cặp (L, N) và outlen là chiều dài đầu ra của hàm băm trong đó outlen ≥ N. Qui trình tạo p, q như sau: Đầu vào: 1. L Chiều dài mong muốn của số nguyên tố p. 2. N Chiều dài mong muốn của số nguyên tố q. 3. seedlen Chiều dài mong muốn của tham số gốc trong đó seedlen ≥ N. Đầu ra: 1. status Trạng thái trả về của hàm tạo, trong đó status có thể là VALID hoặc INVALID. Nếu status = INVALID được trả về thì có nghĩa là không có giá trị nào của các tham số đầu ra được trả về hoặc là giá trị của chúng không hợp lệ. 2. p,q Các số nguyên tố tạo được p, q. 3. domain_parameter_seed (tùy chọn). Là một giá trị khởi tạo được sử dụng để tạo ra p và q 4. counter Bộ đếm(tùy chọn). Là giá trị đếm được tạo ra trong quá trình tạo p, q. Qui trình: 1. Kiểm tra cặp (L, N) có thuộc danh sách các cặp (L, N) được chấp nhận (nêu trong phần 4.2) không. Nếu không thuộc thì trả về giá trị INVALID. 2. If (seedlen < N), then return INVALID. 3. n = L / outlen - 1. 4. b = L - 1 - (n * outlen). 5. Gán một chuỗi bất kì có độ dài seedlen bít cho tham số gốc. 6. U = Hash (domain_parameter_seed) mod 2N. 7. q = U 2N-11. /* Mục đích của bước này là gán bít đầu tiên (bít thứ N) và bít cuối cùng (bít 0) của U thành 1 */ 8. p is prime? /* Kiểm tra xem p có là nguyên tố không bằng cách sử dụng thuật toán kiểm tra tính nguyên tố mạnh nêu trong mục c. */ 9. If q is not a prime, then go to step 5. /* Nếu q không là nguyên tố thì quay lại bước 5 để gán cho tham số gốc một giá trị mới nhằm thu được một số q mới có thể là nguyên tố */ 10. offset = 1. /*tạo được q là nguyên tố rồi, bắt đầu tạo p*/ 11. For counter = 0 to 4095 do /*thử tối đa 4095 lần*/ 11.1 For j = 0 to n do Vj = Hash ((domain_parameter_seed + offset + j) mod 2seedlen). 11.2 W = V0 + (V1 * 2outlen) + ... + (Vn-1 * 2(n-1) * outlen) + ((Vn mod 2b) * 2n * outlen). /* Mục đích của bước này là tạo ra một số W gồm đúng L bít. W có dạng như sau: W =Vn’ Vn-1 Vn-2…V1V0 trong đó Vn’ = Vn mod 2b có độ dài là b bít, Vn-1, …, V0 đều có độ dài là outlen bít. Có thể hiểu là ta ghép liên tiếp các chuỗi V0,…, Vn-1, Vn’ để tạo ra W */ 11.3 X = W + 2L-1. /* Vì W được tạo như trên nên chắc chắn W có độ dài là L bít, do đó số W sẽ thỏa mãn 0 ≤ W < 2 L-1 nên ta có 2L-1 ≤ X < 2L Mục đích của bước này là bước đầu tạo ra số L bít thỏa mãn điều kiện nằm trong khoảng [2L-1 ,2L -1] giống như p */ 11.4 c = X mod 2q. 11.5 p = X - (c - 1). /* Cách tạo c và p như trên dẫn tới p 1 (mod 2q). Tức là ta có p-1 chia hết cho 2q hay p-1 chia hết cho q. Đây chính là một mối quan hệ giữa hai số nguyên tố p và q. */ 11.6 If (p < 2L-1), then go to step 11.9. /*nếu p không thỏa điều kiện ràng buộc là p ≥ 2L-1 thì phải quay lại bước 11.9 để thay đổi giá trị của offset nhằm tạo ra một giá trị W mới ở bước lặp tiếp theo nhằm mong muốn tạo ra được số một số p mới là nguyên tố thỏa mãn các điều kiện ràng buộc */ 11.7 Sử dụng thuật toán kiểm tra tính nguyên tố mạnh để kiểm tra q. 11.8 Nếu p là nguyên tố thì trả về giá trị VALID và giá trị của p, q, domain_parameter_seed và counter. 11.9 offset = offset + n + 1. /* Khi p không là nguyên tố hoặc p không thỏa mãn điều kiện ràng buộc của nó thì thay đổi offset và bắt đầu vòng lặp mới từ 11.1 đến 11.8 nếu bộ đếm vẫn còn nhỏ hơn 4096 */ 12. Go to step 5. /* Sau 4096 bước thử mà vẫn không tìm được p nào thì quay lại bước 5 để tạo lại từ đầu một số q nguyên tố mới và sau đó là tạo p */ b. Kiểm tra số nguyên tố p và q băng việc sử dụng hàm băm Thuật toán kiểm chứng này được sử dụng để kiểm chứng các số nguyên p, q được tạo ra từ thuật toán tạo các số nguyên tố nêu trong mục trên. Đầu vào của thuật toán là các giá trị p, q cần kiểm chứng, domain_parameter_seed và counter. Hàm băm sử dụng chính là hàm băm đã dùng để tạo ra p,q và đặt outlen là kích thước khối đầu ra. Đầu vào: 1. p, q Là 2 số cần kiểm chứng tính nguyên tố. 3. domain_parameter_seed Là tham số gốc đã được dùng để tạo ra p và q. 4. counter Là bộ đếm được xác định trong quá trình tạo p, q. Đầu ra: 1. status Trạng thái trả về của hàm trong đó nó có thể nhận 1 trong 2 giá trị là VALID hoặc INVALID. Qui trình: 1. L = len (p). 2. N = len (q). 3. Kiểm tra cặp (L,N) có thuộc danh sách các cặp (L, N) được chấp nhận (nêu trong phần c) không. Nếu không thuộc thì trả về giá trị INVALID 4. If (counter > 4095), then return INVALID. /Vì giá trị của bộ đếm counter sử dụng trong hàm tạo p, q là ≤ 4095/ 5. seedlen = len (domain_parameter_seed). 6. If (seedlen < (N)), then return INVALID. 7. U = Hash (domain_parameter_seed) mod 2N. /Tạo U theo công thức đã sử dụng trong giải thuật tạo p, q/ 8. computed_q = U 2N-11. /Tạo ra computed_q theo công thức đã dùng để tạo q/ 9. If (computed_q ≠ q) or (computed_q không là nguyên tố), then return INVALID. /* Sử dụng hàm kiểm tra tính nguyên tố mạnh để kiểm tra xem computed_q có là nguyên tố không. Nếu computed_q không phải là nguyên tố hoặc computed_q ≠ q thì chứng tỏ đã hoặc q không phải là nguyên tố hoặc dữ liệu đã có lỗi */ 10. n = L / outlen - 1. 11. b = L - 1 - (n * outlen). 12. offset = 1. 13. For i = 0 to counter do /vòng lặp for giống hệt trong giải thuật tạo/ 13.1 For j = 0 to n do Vj = Hash ((domain_parameter_seed + offset + j) mod 2seedlen). 13.2 W = V0 + (V1 * 2outlen) + ... + (Vn-1 * 2(n-1) * outlen) + ((Vn mod 2b) * 2n*outlen). 13.3 X = W + 2L-1. 13.4 c = X mod 2q. 13.5 computed_p = X - (c - 1). 13.6 If (computed_p < 2L-1), then go to step 13.9 13.7 Kiểm tra computed_p có là nguyên tố không. 13.8 If computed_p là nguyên tố, then go to step 15. 13.9 offset = offset + n + 1. 14. If ((i ≠ counter) or (computed_p ≠ p) or (computed_p is not a prime)), then return INVALID 15. Return VALID. c. Thuật toán xác suất Miller-Rabin kiểm tra tính nguyên tố Đây là một thuật toán kiểm tra tính nguyên tố mạnh, được sử dụng trong quá trình tạo và kiểm chứng các số p, q được tạo ra bằng giải thuật tạo như ở trên. Một thuật toán kiểm tra tính nguyên tố mạnh được lựa chọn sao cho khả năng kết luận nhầm một số không phải là nguyên tố thành nguyên tố là vô cùng thấp, không vượt quá 2-100. Thuật toán xác suất kiểm tra tính nguyên tố Miller-Rabin được xây dựng dựa trên chuẩn Miller-Rabin như sau: cho n là số nguyên lẻ thỏa mãn n-1 = 2e.u, với u là số nguyên tố. Nếu n là số nguyên tố, thì với mọi số nguyên dương a với 0 ≤ a ≤ n -1: (au ≡ 1 mod n) hoặc $ k < e sao cho a ≡ -1 mod n (*) Nếu n là hợp số thì {a: 1 ≤ a ≤ n-1, au ≡ 1 mod n hoặc $k < e(a ≡ -1 mod n)} ≤ Tức là khi số nguyên lẻ n có dạng thỏa mãn n-1 = 2e.u với u là số nguyên tố thì nếu n là số nguyên tố, nó luôn thỏa mãn tính chất(*) còn khi n là hợp số thì chỉ có thể tìm được tối đa là số nguyên a để thỏa mãn tính chất(*). Tính chất(*) đó là hoặc au ≡ 1 mod n, nếu không thì sẽ tồn tại một số k thỏa mãn a ≡ -1 mod n. Dựa trên tiêu chuẩn Miller-Rabin, thuật toán xác suất kiểm tra tính nguyên tố Miller-Rabin được xây dựng như sau: Đầu vào: 1. w Số nguyên (lẻ) cần kiểm tra tính nguyên tố. Đây chính là số p hoặc q. Đầu ra: 1. status Trạng thái trả về của thủ tục kiểm chứng, trong đó status có thể nhận 1 trong 2 giá trị là PROBABLY PRIME(có thể nguyên tố) hoặc COMPOSITE (hợp). Qui trình: Đặt a là số nguyên lớn nhất thỏa mãn: w-1 = 2a. / Như vậy, w có dạng w-1 = 2a.m, trong đó m là một số lẻ. / m = (w-1) / 2a. wlen = len(w). For i = 1 to iteration do Gán một chuỗi wlen bít bất kì cho b. If (b ≤ 1) or (b ≥ w-1), then go to step 4.1. /*Nếu b không thỏa mãn 1 < b < w-1 thì quay lại bước 4.1 để sinh lại chuỗi b khác*/ z = bm mod w. If (z =1) or (z = w -1) then go to step 4.7 /*Theo tiêu chuẩn Miller-Rabin thì vẫn chữa thể kết luận được w là nguyên tố hay phức. Do đó cần quay lại bước 4.7 để thử với vòng lặp tiếp tiếp của for */ For j = 1 to a -1 do z = z2 mod w. /z =z2 mod w ↔ z2 = bmod w trong đó j <a / If (z= w -1), then goto step 4.7. If (z = 1) then goto step 4.6 /* Ta đi chứng minh w là số phức bằng phương pháp phản chứng. Xét chuỗi bm, bm.2, …, bm., …, ba-1. Ta có: - bm ≠ 1 mod w. (1) - bm.2, …, bm.đều ≠ -1 mod w (theo kết quả của vòng lặp) (2) - Mà bm. = -1 mod w, nên mọi phần tử còn lại của dãy từ bm.,…, bm.đều = 1 mod w. (3) - Từ (2) và (3) không tồn tại một số j < a-1 nào thỏa mãn bm.=-1 mod(w) (4) - Giả sử w là nguyên tố. Vậy theo định lý Miller-Rabin, với mọi số nguyên b bất kỳ ta luôn có bm ≡ 1 mod w (ngược với tính chất 1), hoặc nếu không thì cũng luôn tồn tại một số nguyên j < a -1 sao cho bm.=-1 mod w (ngược với tính chất 4). Như vậy điều giả sử là vô lý, tức là w là số phức.*/ Return composite. /kết quả là hợp số/ Continue. 5. Return PROBABLY PRIME 2.4.2. Tạo số g a. Tạo số g Số g được tạo ra dựa trên các giá trị của p, q và tham số domain_parameter_seed trả về từ thủ tục tạo p, q tương ứng. Số g ở đây có thể kiểm chứng được bằng thủ tục kiểm chứng nêu trong phần b. Phương pháp này có thể giúp tạo ra nhiều giá trị g cho cùng một cặp (p, q) xác định. Việc sử dụng các giá trị khác nhau của g có thể hỗ trợ cho việc phân biệt khóa. Ví dụ: ta sử dụng số g được tạo ra với index =1 cho chữ ký số và với index = 2 cho việc thiết lập khóa. Đặt Hash() là hàm băm được lựa chọn cho cặp (L, N). Qui trình tạo g sẽ như sau: Đầu vào: 1. p, q Là các số nguyên tố. 2. domain_parameter_seed Là tham số gốc được sử dụng trong thủ tục tạo p, q. 3. index Chỉ số được sử dụng để tạo g. Chỉ số index biểu diễn bởi một số nguyên 8 bít không dấu. Đầu ra: 1. status Trạng thái trả về của hàm tạo, trong đó status có thể nhận 1 trong 2 giá trị VALID và INVALID. 2. g Giá trị của số g tạo được. Qui trình: If (index is incorrect) then return INVALID. N = len(q); e = (p-1) / q; count = 0; count = count+1; If count = 0 then return INVALID. U = domain_parameter_seed || “ggen” || index || count. W = Hash(U). g = We mod p. /* Ta có: g = We mod p g = Hash(U)(p-1)/q gq =Hash(U)p-1 (1) Mà 0 < Hash(U) < p và p nguyên tố (Hash(U), p) =1. Theo Ferma tao có được (Hash(U))p-1 ≡ 1(mod p) (2) Từ (1) và (2) ta có gq ≡ 1 mod p Như vậy số g thỏa mãn tính chất là căn bậc q của 1 theo modulo p. */ If (g < 2) then goto step 5. Return VALID and the value of g. b. Kiểm tra số g Thuật toán này được dùng để kiểm chứng giá trị g với g được tạo ra bởi thủ tục tạo trong phần a dựa trên các giá trị p, q, tham số domain_parameter_seed và chỉ số index thích hợp. Giả thiết rằng p và q đã được kiểm chứng trước đó rồi. Các tham số gốc sẽ được lấy từ đầu ra của thủ tục tạo p, q. Đặt Hash() là hàm băm được chọn phù hợp với cặp (L, N). Qui trình kiểm chứng sẽ như sau: Đầu vào: 1. p, q Các số nguyên tố. 2. domain_parameter_seed Tham số gốc được dùng để tạo p và q. 3. index Chỉ số được dùng để tạo ra số g trong đó index được biểu diễn bởi số nguyên không dấu 8 bít. Đầu ra: 1. status Trạng thái trả về của thủ tục, trong đó status nhận 1 trong 2 giá trị là VALID và INVALID. Qui trình: If (index is incorect) then return INVALID. If not (2 ≤ g ≤ (p-1)) then return INVALID. If (gq ≠ 1 mod p) then return INVALID. N = len(q). e = (p-1) / q. count = 0. count = count + 1. If count = 0 then return INVALID. U = domain_parameter_seed || “ggen” || index || count. W = Hash(U). computed_g = We mod p. If (computed_g < 2) then goto step 7. 13.If (computed_g = g) than return VALID, else return INVALID. 2.5. Tạo cặp khóa 2.5.1. Tạo cặp khóa Trong phương pháp này, một số ngẫu nhiên N bít sẽ được tạo ra (bằng với số bít của khóa x cần tạo) và sau đó, số ngẫu nhiên này sẽ được kiểm tra để xác định xem liệu nó có thể tạo ra một giá trị x nằm trong khoảng xác định của nó hay không. Nếu x nằm ngoài khoảng xác định thì một số ngẫu nhiên khác sẽ lại được sinh ra và qui trình sẽ được lặp đi lặp lại cho đến khi tìm được một giá trị x chấp nhận được. Qui trình tạo khóa sẽ như sau: Đầu vào: 1. (p, q, g) Tập con của tập các tham số miền được dùng trong qui trình tạo khóa. Trong đó p, q, g ở dạng số nguyên khi đưa vào hoặc được chuyển đổi sang dạng số nguyên trước khi sử dụng. Đầu ra: 1. status Giá trị trả về của giải thuật tạo, trong đó status sẽ nhận 1 trong 2 giá trị là thành công – SUCCESS và thất bại – ERROR. 2. (x,y) Cặp khóa tạo được với x là khóa bí mật, y là khóa công khai. Nếu có một lỗi xảy ra trong quá trình tạo khóa thì các giá trị trả về của x và y là ở dạng không hợp lệ Invalid_x và Invalid_y. Nếu không, x và y được trả về là các số nguyên, trong đó x [1,q-1] và y [1, p-1]. Qui trình: N = len(q); L = len(p). If (L, N) is invalid then return ERROR, Invalid_x, Invalid_y. Tạo một chuỗi bit ngẫu nhiên có độ lớn N bit. Chuyển đổi chuỗi bít vừa tạo được thành số nguyên c. If (c > q-1), then goto step 4. x = (c mod (q-1)) + 1. y = gx mod p. Return SUCCESS, x, y. 2.5.2. Tạo số bí mật cho mỗi thông điệp Trong phương pháp này, một số ngẫu nhiên sau khi được tạo ra sẽ được kiểm tra để xem liệu nó có thể tạo ra một giá trị k thỏa mãn nằm trong khoảng xác định của nó hay không. Nếu k nằm ngoài khoảng xác định thì một số ngẫu nhiên khác sẽ lại được sinh ra và qui trình sẽ được lặp đi lặp lại cho đến khi tìm được một giá trị k chấp nhận được. Qui trình tạo k sẽ như sau: Đầu vào: 1. (p, q, g) Các tham số miền của DSA . Đầu ra: status Trạng thái trả về của thủ tục tạo số ngẫu nhiên trong đó status có thể nhận 1 trong 2 giá trị SUCCESS hoặc ERROR. (k, k1) Cặp số ngẫu nhiên k và thành phần nghịch đảo k-1 của nó với k và k-1 [1, q-1]. Nếu có lỗi xảy ra trong quá trình tạo thì giá trị trả về của k, k1 sẽ có dạng là không hợp lệ Invalid_k và Invalid_k_inverse. Qui trình: N = len(q); L = len(p). If (L, N) is invalid then return ERROR, Invalid_k, Invalid_k_inverse. Tạo một chuỗi bit ngẫu nhiên có độ lớn N bit. Chuyển đổi chuỗi bít vừa tạo được thành số nguyên c. If (c > q-2) then goto step 4. k = c + 1. (status, k-1) = inverse(k, q)./* inverse(k, q) hàm tính nghịch đảo của k trong Zq*/ Return status, k, k-1.  Kết luận Như vậy chúng ta đã đi qua toàn bộ các chương viết của bài luận văn với chủ đề chuẩn ký số - một phương tiện quan trọng được sử dụng trong thương mại điện tử. Qua đó ta có thể chốt lại một số vấn đề sau: Chữ ký điện tử về mặt hình thức cũng tương tự như chữ ký bằng tay được dùng để đảm bảo ai là người đã ký lên thông tin. Ngoài ra, chữ ký điện tử còn đảm bảo được tính toàn vẹn của dữ liệu hay nói cách khác chữ ký điện tử đảm bảo được sự tin cậy về nội dung của thông điệp bởi vì nếu văn bản bị thay đổi trong quá trình truyền thì hàm băm cũng sẽ bị thay đổi theo và lập tức bị phát hiện. Cũng như chữ ký bằng tay, chữ ký điện tử đảm bảo tính không thể phủ nhận được. Trong giao dịch, nếu một bên nào đó từ chối nhận văn bản nào đó là do mình gửi thì bên nhận có thể đưa chữ ký điện tử mà bên gửi đã gửi kèm cùng văn bản như là một chứng cứ để giải quyết tranh chấp. Để cài đặt được chữ ký điện tử và đưa nó vào trong cuộc sống, Viện chuẩn và công nghệ quốc gia của Mỹ - NIST- đã đưa ra chuẩn chữ ký số trong đó trình bày các giải thuật khác nhau để tạo và xác nhận chữ ký số. Trong đồ án của mình, em đã tìm hiểu và trình bày cụ thể, chi tiết giải thuật chữ ký số DSA bao gồm các tiêu chuẩn cho việc tạo và xác nhận các tham số miền, cặp khóa cũng như việc tạo và xác nhận chữ ký số. Về mặt triển khai thực hiện, em đã cài đặt chương trình tạo và xác nhận chữ ký số và bước đầu đã thu được một số kết quả nhất định. Tuy nhiên do đặc thù của giải thuật là làm việc với dữ liệu có kích thước rất lớn ( cặp số nguyên tố p, q có độ dài tối thiểu là 1024 và 160 bít kéo theo các phép toán làm việc với chúng sẽ mất nhiều thời gian, đặc biệt là phép tính mũ modunlo) và số vòng lặp thử được dùng trong giải thuật là rất lớn khiến cho thời gian tạo và xác nhận chữ ký số bị tăng lên rất nhiều. Như vậy chi phí về mặt thời gian là khó khăn chính khi triển khai cài đặt chương trình. Vì vậy vấn đề đặt ra là làm sao để cải thiện được hiệu năng tính toán, giảm thiểu thời gian cũng như phải có sự đầu tư về mặt cơ sở hạ tầng, nâng cấp thiết bị mà hơn hết là tiến hành thực hiện chương trình trên các máy tính chuyên dụng có cấu hình mạnh. Nếu điều kiện cho phép đây sẽ là những mục tiêu hướng tới trong tương lai của chương trình. Cuối cùng em xin chân thành cảm ơn thầy giáo TS. Lê Phê Đô, người đã giúp em hoàn thành đồ án này. Tài liệu tham khảo Lý thuyết mật mã & An toàn thông tin – Phan Đình Diệu – NXB Đại hoc Quốc gia – Hà nội 2002. Mật mã học – PGS.TS Nguyễn Bình – Học Viện Công nghệ Bưu chính Viễn thông – Hà nội 2002. Secure Hash Standard (FIPS PUB 180-1) – NIST – 1993 May 11. Secure Hash Standard (FIPS PUB 180-2) – NIST – 2002 August 1. Digital Signature Standard (FIPS PUB 186) – NIST – 1994 May 19. Digital Signature Standard (FIPS PUB 186-1) – NIST – 1998 December 15. Digital Signature Standard (FIPS PUB 186-2) – NIST – 2000 January 27. Digital Signature Standard (FIPS PUB 186-3) – NIST – 2006 March. Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S.Vanstone, CRC Press, 1996