Luận văn Tìm hiểu về chữ ký điện tử và cài đặt chương trình minh họa

NP- đầy đủ của bài toán xếp ba lô (knapsack problem), hệ mật mã nổi tiếng ElGamal dựa trên độ khó của bài toán lôgarit rời rạc, hệ này về sau được mở rộng để phát triển nhiều hệ tương tự dựa trên độ khó của các bài toán tương tự lôgarit rời rạc trên các cấu trúc nhóm cyclic hữu hạn, nhóm các điểm nguyên trên đường cong eliptic, v.v... Để tăng độ bảo mật, hệ mật mã ElGamal còn dùng với tư cách đầu vào cho thuật toán lập mật mã của mình, ngoài khoá công khai và bản rõ, một yếu tố ngẫu nhiên được chọn tuỳ ý, điều đó làm cho hệ mật mã trở thành một hệ mật mã xác suất khoá công khai. Một số hệ mật mã xác suất khoá công khai cũng được phát triển sau đó bởi Goldwasser-Micali và Blum-Goldwasser. [1 – tr79] Không phải tất cả các thuật toán mật mã hóa khóa bất đối xứng đều hoạt động giống nhau nhưng phần lớn đều gồm 2 khóa có quan hệ toán học với nhau: một cho mã hóa và một để giải mã. Để thuật toán đảm bảo an toàn thì không thể tìm được khóa giải mã nếu chỉ biết khóa đã dùng mã hóa. Điều này còn được gọi là mã hóa công khai vì khóa dùng để mã hóa có thể công bố công khai mà không ảnh hưởng đến bí mật của văn bản mã hóa. Các thông tin để mở khóa thì chỉ có người sở hữu mới biết. Tồn tại khả năng một người nào đó có thể tìm ra được khóa bí mật. Không giống với hệ thống mật mã sử dụng một lần (one-time pad) hoặc tương đương, chưa có thuật toán mã hóa khóa bất đối xứng nào được chứng minh là an toàn trước các tấn công dựa trên bản chất toán học của thuật toán. Khả năng một mối quan hệ nào đó giữa 2 khóa hay điểm yếu của thuật toán dẫn tới cho phép giải mã không cần tới khóa hay chỉ cần khóa mã hóa vẫn chưa được loại trừ. An toàn của các thuật toán này đều dựa trên các ước lượng về khối lượng tính toán để giải các bài toán gắn với chúng. Các ước lượng này lại luôn thay đổi tùy thuộc khả năng của máy tính và các phát hiện toán học mới.[2- tr18] Mặc dù vậy, độ an toàn của các thuật toán mật mã hóa khóa công khai cũng tương đối đảm bảo. Nếu thời gian để phá một mã (bằng phương pháp duyệt toàn bộ) được ước lượng là 1000 năm thì thuật toán này hoàn toàn có thể dùng để mã hóa các thông tin về thẻ tín dụng - Rõ ràng là thời gian phá mã lớn hơn nhiều lần thời gian tồn tại của thẻ (vài năm). [2 – tr21] c. Mã hóa đối xứng (symmetric). Trong mật mã học, các thuật toán khóa đối xứng (tiếng Anh: symmetric-key algorithms) là một lớp các thuật toán mật mã hóa trong đó các khóa dùng cho việc mật mã hóa và giải mã có quan hệ rõ ràng với nhau (có thể dễ dàng tìm được một khóa nếu biết khóa kia). [8] Khóa dùng để mã hóa có liên hệ một cách rõ ràng với khóa dùng để giải mã có nghĩa chúng có thể hoàn toàn giống nhau, hoặc chỉ khác nhau nhờ một biến đổi đơn giản giữa hai khóa. Trên thực tế, các khóa này đại diện cho một bí mật được phân hưởng bởi hai bên hoặc nhiều hơn và được sử dụng để giữ gìn sự bí mật trong kênh truyền thông tin. Thuật toán đối xứng có thể được chia ra làm hai thể loại, mật mã luồng (stream ciphers) và mật mã khối (block ciphers). Mật mã luồng mã hóa từng bit của thông điệp trong khi mật mã khối gộp một số bit lại và mật mã hóa chúng như một đơn vị. Cỡ khối được dùng thường là các khối 64 bit. Thuật toán tiêu chuẩn mã hóa tân tiến (Advanced Encryption Standard), được NIST công nhận tháng 12 năm 2001, sử dụng các khối gồm 128 bit. [8] Các thuật toán đối xứng thường không được sử dụng độc lập. Trong thiết kế của các hệ thống mật mã hiện đại, cả hai thuật toán bất đối xứng và thuật toán đối xứng được sử dụng phối hợp để tận dụng các ưu điểm của cả hai. Những hệ thống sử dụng cả hai thuật toán bao gồm SSL (Secure Sockets Layer), PGP (Pretty Good Privacy) và GPG (GNU Privacy Guard)... Các thuật toán chìa khóa bất đối xứng được sử dụng để phân phối chìa khóa mật cho thuật toán đối xứng có tốc độ cao hơn. Một số ví dụ các thuật toán đối xứng nổi tiếng bao gồm Twofish, Serpent, AES (còn được gọi là Rijndael), Blowfish, CAST5, RC4, Tam phần DES (Triple DES), và IDEA (International Data Encryption Algorithm - Thuật toán mật mã hóa dữ liệu quốc tế). [8] Các thuật toán đối xứng nói chung đòi hỏi công suất tính toán ít hơn các thuật toán khóa bất đối xứng. Trên thực tế, một thuật toán khóa bất đối xứng có khối lượng tính toán nhiều hơn gấp hằng trăm, hằng ngàn lần một thuật toán khóa đối xứng có chất lượng tương đương. Hạn chế của các thuật toán khóa đối xứng bắt nguồn từ yêu cầu về sự phân hưởng chìa khóa bí mật, mỗi bên phải có một bản sao của chìa. Do khả năng các chìa khóa có thể bị phát hiện bởi đối thủ mật mã, chúng thường phải được bảo an trong khi phân phối và trong khi dùng. Hậu quả của yêu cầu về việc lựa chọn, phân phối và lưu trữ các chìa khóa một cách không có lỗi, không bị mất mát là một việc làm khó khăn, khó có thể đạt được một cách đáng tin cậy. Để đảm bảo giao thông liên lạc an toàn cho tất cả mọi người trong một nhóm gồm n người, tổng số lượng chìa khóa cần phải có là n(n-1)/2. Các thuật toán khóa đối xứng không thể dùng cho mục đích xác thực hay mục đích chống thoái thác. d. Hàm băm (Hashing) - Tổng quan về hàm băm Trong ngành mật mã học, một hàm băm mật mã học (tiếng Anh: Cryptographic hash function) là một hàm băm với một số tính chất bảo mật nhất định để phù hợp việc sử dụng trong nhiều ứng dụng bảo mật thông tin đa dạng, chẳng hạn như chứng thực và kiểm tra tính nguyên vẹn của thông điệp. Một hàm băm nhận đầu vào là một xâu ký tự dài (hay thông điệp) có độ dài tùy ý và tạo ra kết quả là một xâu ký tự có độ dài cố định, đôi khi được gọi là tóm tắt thông điệp (message digest) hoặc chữ ký số (digital fingerprint) [1 – tr109]. Hàm băm là các thuật toán không sử dụng khóa để mã hóa (ở đây ta dùng thuật ngữ “băm” thay cho “mã hóa”), nó có nhiệm vụ “lọc” (băm) thông điệp được đưa vào theo một thuật toán h một chiều nào đó, rồi đưa ra một bản băm gọi là văn bản đại diện có kích thước cố định. Do đó người nhận không biết được nội dung hay độ dài ban đầu của thông điệp đã được băm bằng hàm băm. Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội dung thông điệp từ giá trị băm này. [1 – tr109] - Tính chất của hàm băm Tính đụng độ: Theo nguyên lý Diricle: nếu có (n+1) con thỏ được bỏ vào n cái chuồng thì phải tồn tại ít nhất một cái chuồng mà trong đó có ít nhất là hai con thỏ ở chung. Rõ ràng với không gian giá trị Băm nhỏ hơn rất nhiều so với không gian tin về mặt kích thước thì chắc chắn sẽ tồn tại đụng độ, nghĩa là có hai tin x # x’ mà giá trị Băm của chúng là giống nhau, tức h(x) = h(x’) [1 - 109]. Sau đây chúng ta sẽ xét các dạng tấn công có thể có, từ đó rút ra các tính chất của hàm Băm: Tính chất 1: Hàm băm không va chạm yếu. Hàm băm h là không va chạm yếu nếu khi cho trước một bức điện x, không thể tiến hành về mặt tính toán để tìm ra một bức điện x’ ¹ x mà h(x’) = h(x). [1 - tr110] Ví dụ: Người A gửi cho B (x, y) với y = SigA(h(x)). Nhưng trên đường truyền, tin bị lấy trộm. Tên trộm, bằng cách nào đó tìm được một bản thông điệp x’ có h(x’) = h(x) mà x’ ¹ x. Sau đó, tên trộm đưa x’ thay thế x rồi truyền tiếp cho người B. Người B nhận được và vẫn xác thực được thông tin đúng đắn. Để tránh tấn công trên, hàm băm phải không va chạm yếu. Tính chất 2: Hàm băm không va chạm mạnh Hàm băm h là không va chạm mạnh nếu không có khả năng tính toán để tìm ra hai bức thông điệp x và x’ mà x ¹ x’ và h(x) = h(x’). [1 – tr110] Ví dụ: Đầu tiên, tên giả mạo tìm ra được hai bức thông điệp x’ và x (x’ ¹ x) mà có h(x’) = h(x) (ta coi bức thông điệp x là hợp lệ, còn x’ là giả mạo). Tiếp theo, tên trộm đưa cho ông A và thuyết phục ông này kí vào bản tóm lược h(x) để nhận được y. Khi đó (x’, y) là bức điện giả mạo nhưng hợp lệ. Để tránh kiểu tấn công này, hàm h phải thỏa mãn tính không va chạm mạnh Tính chất 3: Hàm băm một chiều. Hàm băm h là một chiều nếu khi cho trước một bản tóm lược thông báo z, không thể thực hiện về mặt tính toán để tìm bức điện x sao cho h(x) = z. [1 – tr110] Việc giả mạo các chữ kí trên bản tóm lược thông báo z ngẫu nhiên thường xảy ra với sơ đồ chữ kí. Giả sử tên giả mạo tính chữ kí trên bản tóm lược thông báo z ngẫu nhiên như vậy. Sau đó anh ta tìm x sao cho z = h(x). Nếu làm được như vậy thì (x,y) là bức điện giả mạo hợp lệ. Để tránh được tấn công này, h cần thoả mãn tính chất một chiều: - Một số hàm băm nổi tiếng + MD5 (Message Digest) Ronald Rivest là người đã phát minh ra các hàm Băm MD2, MD4 (1990) và MD5 (1991). Do tính chất tương tự của các hàm Băm này, sau đây chúng ta sẽ xem xét hàm Băm MD5, đây là một cải tiến của MD4 và là hàm Băm được sử dung rộng rãi nhất, nguyên tắc thiết kế của hàm băm này cũng là nguyên tắc chung cho rất nhiều các hàm băm khác [1 – tr111]. a. Miêu tả MD5: Đầu vào là những khối 512 bit, được chia cho 16 khối con 32 bit. Đầu ra của thuật toán là một thiết lập của 4 khối 32 bit để tạo thành một hàm Băm 128 bit duy nhất. Đầu tiên, ta chia bức điện thành các khối 512 bit, với khối cuối cùng (đặt là x và x < 512bit) của bức điện, chúng ta cộng thêm một bit 1 vào cuối của x, theo sau đó là các bit 0 để được độ dài cần thiết (512 bit). Kết quả là bức điện vào là một chuỗi M có độ dài chia hết cho 512, vì vậy ta có thể chia M ra thành các N khối con 32 bit (N khối này sẽ chia hết cho 16). Bây giờ, ta bắt đầu tìm cốt của bức điện với 4 khối 32 bit A, B, C và D (được xem như thanh ghi) : A = 0x01234567 B = 0x89abcdef C = 0xfedcba98 D = 0x76543210. Người ta thường gọi A, B, C, D là các chuỗi biến số (chaining variables). Bức điện được chia ra thành nhiều khối 512 bit, mỗi khối 512 bit lại được chia ra 16 khối 32 bit đi vào bốn vòng lặp của MD5. Giả sử ta đặt a, b, c và d thay cho A, B, C và D đối với khối 512 bit đầu tiên của bức điện. Bốn vòng lặp trong MD5 đều có cấu trúc giống nhau. Mỗi vòng thực hiện 16 lần biến đổi: thực hiện với một hàm phi tuyến của 3 trong 4 giá trị a, b, c và d; sau đó nó cộng kết quả đến giá trị thứ 4, tiếp đó cộng với một khối con 32 bit và một hằng số. Sau đó, nó dịch trái một lượng bit thay đổi và cộng kết quả vào một trong 4 giá trị a, b, c hay d. Kết quả cuối cùng là một giá trị mới được thay thế một trong 4 giá trị a, b, c hay d. Khối của bức điện Vòng 1 Vòng 2 Vòng 3 Vòng 4 A B C D A B C D Hình 1.2 sơ đồ vòng lặp chính của MD5 Có bốn hàm phi tuyến, mỗi hàm này được sử dụng cho mỗi vòng: F(X,Y,Z ) = (X and Y) or ((not X) and Z) G(X,Y,Z ) = ((X and Z) or (Y and (not Z))) H(X,Y,Z ) = X xor Y xor Z I(X,Y,Z ) = Y xor (X or (not Z)). Những hàm này được thiết kế sao cho các bit tương ứng của X, Y và Z là độc lập và không ưu tiên, và mỗi bit của kết quả cũng độc lập và ngang bằng nhau. Nếu Mj là một biểu diễn của khối con thứ j (j = 16) và <<<s là phép dịch trái của s bit, thì các vòng lặp có thể biểu diễn như sau: FF(a,b,c,d,Mj,s,ti) được biểu diễn a = b + ((a + F(b,c,d) + Mj + ti) <<< s) GG(a,b,c,d,Mj,s,ti) được biểu diễn a = b + ((a + G(b,c,d) + Mj + ti) <<< s) HH(a,b,c,d,Mj,s,ti) được biểu diễn a = b + ((a + H(b,c,d) + Mj + ti) <<< s) II(a,b,c,d,Mj,s,ti) được biểu diễn a = b + ((a + I(b,c,d) + Mj + ti) <<< s). Bốn vòng (64 bước) sẽ thực hiện như sau: Vòng 1: FF (a, b, c, d, M0, 7, 0x76aa478) FF (d, a, b, c, M1, 12, 0xe8c7b756) FF (c, d, a, b, M2, 17, 0x242070db) FF (b, c, d, a, M3, 22, 0xc1bdceee) FF (a, b, c, d, M4, 7, 0xf57c0faf) FF (d, a, b, c, M5, 12, 0x4787c62a) FF (c, d, a, b, M6, 17, 0xa8304613) FF (b, c, d, a, M7, 22, 0xfd469501) FF (a, b, c, d, M8, 7, 0x698098d8) FF (d, a, b, c, M9, 12, 0x8b44f7af) FF (c, d, a, b, M10, 17, 0xffff5bb1) FF (b, c, d, a, M11, 22, 0x895cd7be) FF (a, b, c, d, M12, 7, 0x6b901122) FF (d, a, b, c, M13, 12, 0xfd987193) FF (c, d, a, b, M14, 17, 0xa679438e) FF (b, c, d, a, M15, 22, 0x49b40821). Vòng 2: GG (a, b, c, d, M1, 5, 0x61e2562) GG (d, a, b, c, M6, 9, 0xc040b340) GG (c, d, a, b, M11, 14, 0x265e5a51) GG (b, c, d, a, M0, 20, 0xe9b6c7aa) GG (a, b, c, d, M5, 5, 0xd62f105d) GG (d, a, b, c, M10, 9, 0x02441453) GG (c, d, a, b, M15, 14, 0xd8a1e681) GG (b, c, d, a, M4, 20, 0xe7d3fbc8) GG (a, b, c, d, M9, 5, 0x21e1cde6) GG (d, a, b, c, M14, 9, 0xc33707d6) GG (c, d, a, b, M3, 14, 0xf4d50d87) GG (b, c, d, a, M8, 20, 0x455a14ed) GG (a, b, c, d, M13, 5, 0xa9e3e905) GG (d, a, b, c, M2, 9, 0xfcefa3f8) GG (c, d, a, b, M7, 14, 0x676f02d9) GG (b, c, d, a, M12, 20, 0x8d2a4c8a). Vòng 3: HH (a, b, c, d, M5, 4, 0xfffa3942) HH (d, a, b, c, M8, 11, 0x8771f681) HH (c, d, a, b, M11, 16, 0x6d9d6122) HH (b, c, d, a, M14, 23, 0xfde5380c) HH (a, b, c, d, M1, 4, 0xa4beea44) HH (d, a, b, c, M4, 11, 0x4bdecfa9) HH (c, d, a, b, M7, 16, 0xf6bb4b60) HH (b, c, d, a, M10, 23, 0xbebfbc70) HH (a, b, c, d, M13, 4, 0x289b7ec6) HH (d, a, b, c, M0, 11, 0xeaa127fa) HH (c, d, a, b, M3, 16, 0xd4ef3085) HH (b, c, d, a, M6, 23, 0x04881d05) HH (a, b, c, d, M9, 4, 0xd9d4d039) HH (d, a, b, c, M12, 11, 0xe6db99e5) HH (c, d, a, b, M15, 16, 0x1fa27cf8) HH (b, c, d, a, M2, 23, 0xc4ac5665). Vòng 4: II (a, b, c, d, M0, 6, 0xf4292244) II (d, a, b, c, M7, 10, 0x432aff97) II (c, d, a, b, M14, 15, 0xab9423a7) II (b, c, d, a, M5, 21, 0xfc93a039) II (a, b, c, d, M12, 6, 0x655b59c3) II (d, a, b, c, M3, 10, 0x8f0ccc92) II (c, d, a, b, M10, 15, 0xffeff47d) II (b, c, d, a, M1, 21, 0x85845dd1) II (a, b, c, d, M8, 6, 0x6fa87e4f) II (d, a, b, c, M15, 10, 0xfe2ce6e0) II (c, d, a, b, M6, 15, 0xa3013414) II (b, c, d, a, M13, 21, 0x4e0811a1) II (a, b, c, d, M4, 6, 0xf7537e82) II (d, a, b, c, M11, 10, 0xbd3af235) II (c, d, a, b, M2, 15, 0x2ad7d2bb) II (b, c, d, a, M9, 21, 0xeb86d391). Những hằng số ti được chọn theo quy luật sau: ở bước thứ i giá trị ti là phần nguyên của 232*abs(sin(i)), trong đó i = [0..63] được tính theo radian. Sau tất cả những bước này a, b, c và d lần lượt được cộng với A, B, C và D để cho kết quả đầu ra, và thuật toán tiếp tục với khối dữ liệu 512 bit tiếp theo cho đến hết bức điện. Đầu ra cuối cùng là một khối 128 bit của A, B, C và D, đây chính là hàm Băm nhận được [1 – tr111 > tr115]. b. Tính bảo mật trong MD5: Ron Rivest đã phác hoạ những cải tiến của MD5 so với MD4 như sau: Vòng thứ 4 được thêm vào (còn MD4 chỉ có 3 vòng). Mỗi bước được cộng thêm một hằng số duy nhất. Hàm G ở vòng 2 thay đổi từ ((X and Y) or (X and Z) or (Y and Z)) thành ((X and Z) or (Y and (not Z))) nhằm giảm tính đối xứng của G (giảm tính tuyến tính). Mỗi bước được cộng kết quả của bước trước nó, làm các quá trình có tính liên kết, phụ thuộc lẫn nhau. Việc các khối con bị thay đổi khi vào vòng 2 và vòng 3 làm cho khuôn dạng cấu trúc vòng lặp thay đổi theo. Số lượng lượng bit dịch trái của mỗi vòng được tối ưu và các bước dịch ở mỗi vòng là khác nhau. Năm 1993, den Boer và Bosselaers đã tìm ra đụng độ trong việc sử dụng hàm nén (vòng 2 và 3) của MD5. Điều này phá vỡ quy luật thiết kế MD5 là chống lại sự đụng độ, nhưng MD5 vẫn là hàm Băm được sử dụng rộng rãi hiện nay [1 – tr115]. + SHA (Secure Hash Algorithm) Năm 1995, tổ chức NIST cùng NSA đã thiết kế ra thuật toán hàm Băm an toàn (SHA) sử dụng cho chuẩn chữ ký điện tử DSS. SHA được thiết kế dựa trên những nguyên tắc của MD4/MD5, tạo ra 160 bit giá trị Băm [1 – tr116]. a. Miêu tả SHA: Cũng giống với MD5, bức điện được cộng thêm một bit 1 và các bit 0 ở cuối bức điện để bức điện có thể chia hết cho 512. SHA sử dụng 5 thanh ghi dịch: A = 0x67452301 B = 0xefcdab89 C = 0x98badcfe D = 0x10325476 E = 0xc3d2e1f0 Bức điện được chia ra thành nhiều khối 512 bit. Ta cũng đặt là a, b, c, d và e thay cho A, B, C, D và E đối với khối 512 bit đầu tiên của bức điện. SHA có bốn vòng lặp chính với mỗi vòng thực hiện 20 lần biến đổi: bao gồm thực hiện với một hàm phi tuyến của 3 trong 5 giá trị a, b, c, d và e; sau đó cũng được cộng và dịch như trong MD5. SHA xác lập bốn hàm phi tuyến như sau: ft(X,Y,Z) = (X and Y) or ((not X) and Z) với 0 ≤ t ≤ 19 ft(X,Y,Z) = X xor Y xor Z với 20 ≤ t ≤ 39 ft(X,Y,Z) = (X and Y) or (X and Z) or (Y and Z) với 40 ≤ t ≤ 59 ft(X,Y,Z) = X xor Y xor Z với 60 ≤ t ≤ 79. Bốn hằng số sử dụng trong thuật toán là: Kt = 21/2 /4 = 0x5a827999 với 0 ≤ t ≤ 19 Kt = 31/2 /4 = 0x6ed9eba1 với 20 ≤ t ≤ 39 Kt = 51/2 /4 = 0x8f1bbcdc với 40 ≤ t ≤ 59 Kt = 101/2 /4 = 0xca62c1d6 với 60 ≤ t ≤ 79. Các khối bức điện được mở rộng từ 16 khối con 32 bit (M0 đến M15) thành 80 khối con 32 bit (W0 đến W79) bằng việc sử dụng thuật toán mở rộng: Wt = Mt với 0 ≤ t ≤ 15 Wt = (Wt-3 xor Wt-8 xor Wt-14 xor Wt-16) với 16 ≤ t ≤ 79. Nếu gọi Wt là biểu diễn của khối con thứ t của bức điện được mở rộng, và <<<s là biểu diễn dịch trái s bit, thì vòng lặp chính của SHA như sau: a = A, b = B, c = C, D = D, e = E, for t = 0 to 79 { TEMP = (a <<< 5) + ft(b, c, d) + e +Wt + Kt, e = d, d = c, c = b <<< 30, b = a, a = TEMP, } A = A + a, B = B + b, C = C + c, D = D + d, E = E + e, Thuật toán tiếp tục với khối 512 bit tiếp theo cho tới khi hết bức điện, và kết quả sau cùng trong 5 thanh ghi A, B, C, D và E chính là hàm Băm SHA 160 bit [1 – tr115 > tr117]. b. Tính bảo mật trong SHA: Để hiểu rõ hơn về tính bảo mật của SHA, ta hãy so sánh SHA với MD5 để có thể tìm ra những điểm khác nhau của hai hàm Băm này: - MD5 và SHA đều cộng thêm các bit “giả” để tạo thành những khối chia hết cho 512 bit, nhưng SHA sử dụng cùng một hàm phi tuyến f cho cả bốn vòng. - MD5 sử dụng mỗi hằng số duy nhất cho mỗi bước biến đổi, SHA sử dụng mỗi hằng số cho mỗi vòng biến đổi, hằng số dịch này là một số nguyên tố đối với độ lớn của từ (giống với MD4). - Trong hàm phi tuyến thứ 2 của MD5 có sự cải tiến so với MD4, SHA thì sử dụng lại hàm phi tuyến của MD4, tức (X and Y) or (X and Z) or (Y and Z). - Trong MD5 với mỗi bước được cộng kết quả của bước trước đó. Sự khác biệt đối với SHA là cột thứ 5 được cộng (không phải b, c hay d như trong MD5), điều này làm cho phương pháp tấn công của Boer-Bosselaers đối với SHA bị thất bại (den Boer và Bosselaers là hai người đã phá thành công 2 vòng cuối trong MD4). Cho đến nay, chưa có một công bố nào được đưa ra trong việc tấn công SHA, bởi vì độ dài của hàm Băm SHA là 160 bit, nó có thể chống lại phương pháp tấn công bằng vét cạn (kể cả birthday attack) tốt hơn so với hàm Băm MD5 128 bit [1 – tr117]. III. Chữ ký điện tử 1. Tổng quan Trong cuộc sống hàng ngày, ta cần dùng chữ ký để xác nhận các văn bản tài liệu nào đó và có thể dùng con dấu với giá trị pháp lý cao hơn đi kèm với chữ ký. Cùng với sự phát triển nhanh chóng của công nghệ thông tin, các văn bản tài liệu được lưu dưới dạng số, dễ dàng được sao chép, sửa đổi. Nếu ta sử dụng hình thức chữ ký truyền thống như trên sẽ rất dễ dàng bị giả mạo chữ ký. Vậy làm sao để có thể ký vào các văn bản, tài liệu số như vậy? Câu trả lời đó là sử dụng chữ ký điện tử! Chữ ký điện tử đi kèm với các thông tin chủ sở hữu và một số thông tin cần thiết khác sẽ trở thành Chứng chỉ điện tử. Chữ ký điện tử (tiếng Anh: electronic signature) là thông tin đi kèm theo dữ liệu (văn bản, hình ảnh, video...) nhằm mục đích xác định người chủ của dữ liệu đó. Một sơ đồ chữ ký điện tử là bộ 5 (P, A, K, S, V) thoả mãn các điều kiện dưới đây: 1) P là tập hữu hạn các bức điện (thông điệp, bản rõ) có thể. 2) A là tập hữu hạn các chữ ký có thể. 3) K là tập không gian khoá (tập hữu hạn các khoá có thể). 4) Với mỗi khoá K € k tồn tại một thuật toán ký SigK € S và một thuật toán xác minh VerK € V. Mỗi Sigk: P → A và verK: P x A → {TRUE, FALSE} là những hàm sao cho mỗi bức điện x € P và mỗi chữ ký y € A thoả mãn phương trình dưới đây: True nếu y = sig(x) Ver (x, y) = False nếu y ≠ sig(x). Với mỗi K € k, hàm SigK và VerK là các hàm đa thức thời gian. Hàm VerK sẽ là hàm công khai còn hàm SigK là bí mật. Không thể dễ dàng tính toán để giả mạo chữ ký của B trên bức điện x, nghĩa là với x cho trước chỉ có B mới có thể tính được y để Ver(x, y) = TRUE. Một sơ đồ chữ ký không thể an toàn vô điều kiện vì một người C nào đó có thể kiểm tra tất cả chữ số y trên bức điện x nhờ dùng thuật toán Ver() công khai cho tới khi anh ta tìm thấy chữ ký đúng. Vì thế, nếu có đủ thời gian, C luôn có thể giả mạo chữ ký của B. Như vậy mục đích của chúng ta là tìm các sơ đồ chữ ký điện tử an toàn về mặt tính toán [1 – tr116]. Chữ ký điện tử được sử dụng trong các giao dịch điện tử. Xuất phát từ thực tế, chữ ký điện tử cũng cần đảm bảo các chức năng: Xác định được người chủ của một dữ liệu nào đó ví dụ văn bản, ảnh, video, ... dữ liệu đó có bị thay đổi hay không. Hai khái niệm chữ ký số (digital signature) và chữ ký điện tử thường được dùng thay thế cho nhau mặc dù chúng không hoàn toàn có cùng nghĩa. Chữ ký số chỉ là một tập con của chữ ký điện tử (chữ ký điện tử bao hàm chữ ký số). Một chữ ký điện tử sẽ là một chữ ký số nếu nó sử dụng một phương pháp mã hóa nào đó để đảm bảo tính toàn vẹn (thông tin) và tính xác thực. Ví dụ như một bản dự thảo hợp đồng soạn bởi bên bán hàng gửi bằng email tới người mua sau khi được ký (điện tử). [1- tr117] Một văn bản được ký có thể được mã hóa khi gửi nhưng điều này không bắt buộc. Việc đảm bảo tính bí mật và tính toàn vẹn của dữ liệu có thể được tiến hành độc lập. 2. Quy trình sử dụng chữ ký điện tử Chữ ký điện tử hoạt động dựa trên hệ thống mã hóa khóa công khai. Hệ thống mã hóa này gồm hai khóa, khóa bí mật và khóa công khai. Mỗi chủ thể có một cặp khóa như vậy, chủ thể đó sẽ giữ khóa bí mật, còn khóa công khai của chủ thể sẽ được đưa ra công cộng để bất kỳ ai cũng có thể biết. Nguyên tắc của hệ thống mã hóa khóa công khai đó là, nếu mã hóa bằng khóa bí mật thì chỉ khóa công khai mới giải mã đúng thông tin được, và ngược lại, nếu mã hóa bằng khóa công khai, thì chỉ có khóa bí mật mới giải mã đúng được. Ngoài ra, chữ ký còn đảm bảo phát giác được bất kỳ sự thay đổi nào trên dữ liệu đã được “ký”. Để ký lên một văn bản, phần mềm ký sẽ nghiền (crunch down) dữ liệu để gói gọn bằng một vài dòng, được gọi là thông báo tóm tắt, bằng một tiến trình được gọi là “kỹ thuật băm”, rồi tạo thành chữ ký điện tử. Cuối cùng, phần mềm ký tên sẽ gắn chữ ký điện tử này vào văn bản. Ví dụ: Giả sử bên A có tài liệu P cần ký. Bên A sẽ thực hiện băm văn bản thành một bản tóm lược X, sau đó dùng khóa bí mật của mình ký lên bản tóm lược X để được văn bản chữ ký điện tử Y, sau đó gửi tài liệu P kèm theo chữ ký Y cho A. Giả sử B muốn xác nhận tài liệu P là của A, với chữ ký là bản mã Y. Bên B sẽ dùng khóa công khai của A để xác nhận chữ ký Y của A ký trên văn bản P gửi có đúng hay không, nếu xác nhận đúng thì chữ ký Y chính là A ký trên văn bản P, ngược lại thì không phải hoặc bản ký đã được thay đổi. Một số trường hợp xảy ra với chữ ký điện tử, cũng giống như các trường hợp xảy ra với chữ ký truyền thống. Ví dụ: Khi tài liệu TL của A bị thay đổi (dù chỉ một ký tự, một dấu chấm, hay một ký hiệu bất kỳ), khi B xác nhận, anh ta sẽ thấy bản giải mã khác với tài liệu TL của anh A. B sẽ kết luận rằng tài liệu đó đã bị thay đổi, không phải là tài liệu anh A đã ký. Trường hợp khác, nếu A để lộ khóa bí mật, nghĩa là văn bản tài liệu của A có thể ký bởi người khác có khóa bí mật của A. Khi một ai đó xác nhận tài liệu được cho là của A ký, chữ ký vẫn là hợp lệ, mặc dù không phải chính A ký. Như vậy, chữ ký của A sẽ không còn giá trị pháp lý nữa. Do đó, việc giữ khóa bí mật là tuyệt đối quan trọng trong hệ thống chữ ký điện tử. Trong trường hợp ví dụ trên, A có một cặp khóa để có thể ký trên văn bản, tài liệu số. Tương tự như vậy, B hay bất cứ ai sử dụng chữ ký điện tử, đều có một cặp khóa như vậy. Khóa bí mật được giữ riêng, còn khóa công khai được đưa ra công cộng. Vậy vấn đề đặt ra là làm thế nào để biết một khóa công khai thuộc về A, B hay một người nào đó? Hơn nữa, giả sử trong môi trường giao dịch trên Internet, cần sự tin cậy cao, A muốn giao dịch với một nhân vật X. X và A cần trao đổi thông tin cá nhân cho nhau, các thông tin đó gồm họ tên, địa chỉ, số điện thoại, email… Vậy làm sao để A có thể chắc chắn rằng mình đang giao dịch với nhân vật X chứ không phải là ai khác giả mạo X? Chứng chỉ số được tạo ra để giải quyết vấn đề này! Chứng chỉ số có cơ chế để xác nhận thông tin chính xác về các đối tượng sử dụng chứng chỉ số. Thông tin giữa A và X sẽ được xác nhận bằng một bên trung gian mà A và X tin tưởng. Bên trung gian đó là nhà cung cấp chứng chỉ số CA (Certificate Authority). CA có một chứng chỉ số của riêng mình, CA sẽ cấp chứng chỉ số cho A và X cũng như những đối tượng khác. Trở lại vấn đề trên, A và X sẽ có cách kiểm tra thông tin của nhau dựa trên chứng chỉ số như sau: khi A giao dịch với X, họ sẽ chuyển chứng chỉ số cho nhau, đồng thời họ cũng có chứng chỉ số của CA, phần mềm tại máy tính của A có cơ chế để kiểm tra chứng chỉ số của X có hợp lệ không, phần mềm sẽ kết hợp chứng chỉ số của nhà cung cấp CA và chứng chỉ của X để thông báo cho A về tính xác thực của đối tượng X. Nếu phần mềm kiểm tra và thấy chứng chỉ của X là phù hợp với chứng chỉ CA, thì A có thể tin tưởng vào X. Cơ chế chữ ký điện tử và chứng chỉ số sử dụng các thuật toán mã hóa đảm bảo không thể giả mạo CA để cấp chứng chỉ không hợp pháp, mọi chứng chỉ giả mạo đều có thể dễ dàng bị phát hiện. Trở lại với việc ký văn bản, tài liệu, khóa bí mật sẽ dùng để ký các văn bản, tài liệu của chủ sở hữu. Như đã đề cập trong ví dụ ở trên, giả sử A muốn gửi một văn bản kèm với chữ ký của mình trên văn bản đó, A sẽ dùng khóa bí mật để mã hóa thu được bản mã văn bản, bản mã đó chính là chữ ký điện tử của A trên văn bản. Khi A gửi văn bản và chữ ký, để người khác có thể xác nhận văn bản của mình với thông tin đầy đủ về chủ sở hữu, A sẽ gửi cả chứng chỉ của mình đi kèm với văn bản. Giả sử X nhận được văn bản A gửi kèm với chứng chỉ, khi đó X có thể dễ dàng xác nhận tính hợp pháp của văn bản đó. 3. Một số sơ đồ CKĐT phổ biến a. Rivest Shamir Adleman (RSA) - Sơ lược về các khái niệm toán học dùng trong RSA. * Số nguyên tố (prime) Số nguyên tố là những số nguyên chỉ chia chẵn được cho 1 và cho chính nó. Ví dụ : 2, 3, 5, 7, 11, 13, 17, 23... * Khái niệm nguyên tố cùng nhau (relatively prime or coprime). Với hai số nguyên dương a và b. Ta ký hiệu UCLN(a,b): Ước chung lớn nhất của a và b. Để đơn giản ta ký hiệu UCLN(a,b) = (a,b) Ví dụ : (4,6)=2 (5,6)=1 Hai số a và b gọi là nguyên tố cùng nhau khi (a,b)=1 Ví dụ : 9 và 10 nguyên tố cùng nhau vì (9,10)=1 * Khái niệm modulo Với m là một số nguyên dương. Ta nói hai số nguyên a và b là đồng dư với nhau + modulo m, nếu m chia hết hiệu (a-b) (viết là m|(a-b) ) Ký hiệu a ≡ b (mod m) [5] Như vậy a ≡ b (mod m ) khi và chỉ khi tồn tại số nguyên k sao cho: a = b + k*m Ví dụ: 13 ≡ 3 (mod 10) vì 13= 3 + 1*10 * Phi – Hàm EULER Định nghĩa: Phi – Hàm Euler Φ(n) có giá trị tại n bằng số các số không vượt quá n và nguyên tố cùng nhau với n. [5] Ví dụ : Φ(5) = 4 , Φ(6) = 2 ,Φ(10) = 4 * Một số định lý cơ bản Định lý Euler: Nếu m là số nguyên dương và P nguyên tố cùng nhau với m thì PΦ(m) ≡ 1 (mod m) [5] Vậy nếu m và p nguyên tố cùng nhau . Ta đặt s = Φ(m) thì Ps ≡ 1 (mod m) Suy ra với: a= 1 + k*s Ta có : Pa ≡ P*(Ps)k ≡ P*1k (mod m) ≡ P (mod m) Với e là số nguyên dương nguyên tố cùng nhau với s ,tức là (e,s)=1. Khi đó tồn tại một nghịch đảo d của e modulo s tức là e*d≡ 1 (mod s) ; e*d = 1 + k*s Đặt E(P) ≡ C ≡ Pe (mod m) Đặt D(C) ≡ Cd (mod m) Ta thấy D(C) ≡ Cd ≡ (Pe (mod m))d (mod m)≡ Pe*d  (mod m) ≡  P(1+k*s) (mod m) ≡  P.(Ps)k (mod m)≡P.(1)k (mod m)≡   P (mod m) Ví dụ : m = 10 , P = 9 ta có (10,9)=1, s = Φ(10) = 4, e = 7, ta có (7,4) = 1. Nghịch đảo của (7 modulo 4) là: d = 3, vì 7*3 =1 + 5*4 Lúc đó ta có: E(P) ≡ C ≡ Pe ≡ 97 ≡ 4.782.969 ≡ 9 (mod 10) => C=9 D(C) ≡ Cd ≡ 93 ≡ 729 ≡ 9 (mod 10) Vậy D chính là hàm ngược của E. Đây là cơ sở cho việc xây dựng thuật toán RSA. Tính Φ(m) khi biết m. Chúng ta có định lý sau đây: Giả sử m = p1a1*p2a2*… *pkak. Khi đó. Φ(m) =( p1a1– p1(a1-1))* … * (pkak – pk(ak-1)) Ví dụ: m= 10 Ta phân tích 10 =2*5=> Φ(10) =( 21 – 20) *(51 – 50) = 1*4 = 4. - Cách tạo khóa: Chúng ta cần tạo ra một cặp khóa Ký và Xác nhận theo các bước sau: Bước1. Chọn 2 số nguyên tố lớn p và q với (p # q), lựa chọn ngẫu nhiên và độc lập. Bước2. Tính số hàm modulo của hệ thống: n= p*q. Bước3. Tính: Giá trị hàm số Ơle: Φ(n)= (p-1)(q-1). Bước4. Chọn một số tự nhiên khóa mã e sao cho (1 <= e <= Φ(n)) và là số nguyên tố cùng nhau với Φ(n). Bước5. Tính khóa giải mã d sao cho: d*e ≡ 1 (mod Φ(n)). Với 0<=d<= Φ(n) Khi đó ta phân phát khóa công khai: KU= {e,n}. Và giữ khóa bí mật: KR= {d,n}. Một số lưu ý: Các số nguyên tố thường được chọn bằng phương pháp thử xác suất. Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng Bước 5 có thể viết cách khác: Tìm số tự nhiên x sao cho d=(x(p-1)(q-1)+1)/e cũng là số tự nhiên. Khi đó sử dụng giá trị: d mod (p-1)(q-1). Từ bước 3 sử dụng: £=BCNN(p-1)(q-1) thay cho Φ(n)=(p-1)(q-1). [5] * Khóa công khai bao gồm: n, môđun. e, số mũ công khai. * Khóa bí mật bao gồm: n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật. d, số mũ bí mật. - Quy trình thực hiện ký và xác nhận văn bản. Dựa vào ưu điểm của hệ mã RSA, nếu thiết lập được sơ đồ chữ ký dựa trên bài toán phân tích ra thừa số nguyên tố thì độ an toàn của chữ ký sẽ rất cao. * Ký (Mã hóa). Phần này đã được cắt bỏ, hãy liên hệ chủ đề tài để nhận được bản chi tiết hơn. Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân). Cuối cùng ta có bản ký c hay bản chữ ký điện tử và gửi cho đối tác. * Xác nhận (Giải mã). Sau khi nhận được bản chữ ký điện tử, người nhận cần phải xác nhận chữ ký trên văn bản là đúng người ký bằng cách xác nhận bản ký với khóa công khai của người ký với công thức sau. VerK(m,c) = TRUE ó m ≡ ce (mod n) với x, y € Zn. Quá trình giải mã hoạt động vì ta có Ce ≡ (md)e ≡ mde (mod n); Do: ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên: Mde ≡ m (mod p); và mde ≡ m (mod q); Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có: Mde ≡ m (mod pq); hay: Ce ≡ m (mod n); Thông thường, chữ ký được kết hợp với hàm mã hoá công khai. Giả sử A muốn gửi một bức điện đã được mã hoá và đã được ký đến cho B. Với bản rõ x cho trước, A sẽ tính toán chữ ký của mình y = SigA(m) và sau đó mã hoá cả x và y sử dụng khoá công khai eB của B, kết quả nhận được là z = eB(m, c). Bản mã z sẽ được gửi tới B, khi B nhận được z, đầu tiên anh ta giải mã với hàm giải mã dB của mình để nhận được (m, c). Sau đó anh ta dùng hàm xác minh công khai của A để kiểm tra xem VerA(m,c) = TRUE hay không [1]. Song nếu đầu tiên A mã hoá m, rồi sau đó mới ký lên bản mã nhận được thì sao? Khi đó, A sẽ tính: c = SigA(eB(m)) A sẽ truyền cặp (z, c) tới B, B sẽ giải mã z và nhận được m, sau đó xác minh chữ ký c trên m nhờ dùng VerA. Một vấn đề nảy sinh nếu A truyền (m, c) kiểu này thì một người thứ ba C có thể thay chữ ký c của A bằng chữ ký của chính mình. c’ = SigC(eB(m)) Chú ý rằng, C có thể ký lên bản mã eB(m) ngay cả khi anh ta không biết bản rõ m. Khi đó nếu C truyền (z, c’) đến B, chữ ký của C được B xác minh bằng VerC và do đó, B cho rằng bản rõ x xuất phát từ C. Do khó khăn này, hầu hết người sử dụng được khuyến nghị “ký trước khi mã” [1 – tr103]. - Tính bảo mật. Bài toán bảo mật của hệ chữ ký RSA là tránh trường hợp người ngoài có thể tính ra giá trị d bí mật (giá trị ký hay mã hóa) khi biết được giá trị xác nhận e (công khai). Độ an toàn của hệ thống ký RSA dựa trên 2 vấn đề của toán học: Bài toán phân tích ra thừa số nguyên tố các số nguyên lớn và bài toán RSA. Nếu 2 bài toán trên là khó (không tìm được thuật toán hiệu quả để giải chúng) thì không thể thực hiện được việc phá mã toàn bộ đối với RSA. Bài toán RSA là bài toán tính căn bậc e môđun n (với n là hợp số): Tìm số m sao cho me=c mod n, trong đó (e, n) chính là khóa công khai và c là bản mã. Hiện nay phương pháp triển vọng nhất giải bài toán này là phân tích n ra thừa số nguyên tố. Khi thực hiện được điều này, kẻ tấn công sẽ tìm ra số mũ bí mật d từ khóa công khai và có thể giải mã theo đúng quy trình của thuật toán. Nếu kẻ tấn công tìm được 2 số nguyên tố p và q sao cho: n = pq thì có thể dễ dàng tìm được giá trị (p-1)(q-1) và qua đó xác định d từ e. Chưa có một phương pháp nào được tìm ra trên máy tính để giải bài toán này trong thời gian đa thức (polynomial-time). Tuy nhiên người ta cũng chưa chứng minh được điều ngược lại (sự không tồn tại của thuật toán). Tại thời điểm năm 2005, số lớn nhất có thể được phân tích ra thừa số nguyên tố có độ dài 663 bit với phương pháp phân tán trong khi khóa của RSA có độ dài từ 1024 tới 2048 bit. Một số chuyên gia cho rằng khóa 1024 bit có thể sớm bị phá vỡ (cũng có nhiều người phản đối việc này). Với khóa 4096 bit thì hầu như không có khả năng bị phá vỡ trong tương lai gần. Do đó, người ta thường cho rằng RSA đảm bảo an toàn với điều kiện n được chọn đủ lớn. Nếu n có độ dài 256 bit hoặc ngắn hơn, nó có thể bị phân tích trong vài giờ với máy tính cá nhân dùng các phần mềm có sẵn. Nếu n có độ dài 512 bit, nó có thể bị phân tích bởi vài trăm máy tính tại thời điểm năm 1999. Một thiết bị lý thuyết có tên là TWIRL do Shamir và Tromer mô tả năm 2003 đã đặt ra câu hỏi về độ an toàn của khóa 1024 bit. Vì vậy hiện nay người ta khuyến cáo sử dụng khóa có độ dài tối thiểu 2048 bit. Năm 1993, Peter Shor công bố thuật toán Shor chỉ ra rằng: Máy tính lượng tử (trên lý thuyết) có thể giải bài toán phân tích ra thừa số trong thời gian đa thức. Tuy nhiên, máy tính lượng tử vẫn chưa thể phát triển được tới mức độ này trong nhiều năm nữa [2 – tr117]. - Các dạng tấn công * Phân phối khóa Cũng giống như các thuật toán mã hóa khác, cách thức phân phối khóa công khai là một trong những yếu tố quyết định đối với độ an toàn của RSA. Quá trình phân phối khóa cần chống lại được tấn công đứng giữa (man-in-the-middle attack). Giả sử kẻ xấu (C) có thể gửi cho Người gửi thông tin(A) một khóa bất kỳ và khiến (A) tin rằng đó là khóa (công khai) của Đối tác(B). Đồng thời (C) có khả năng đọc được thông tin trao đổi giữa (A) và (B). Khi đó, (C) sẽ gửi cho (A) khóa công khai của chính mình (mà (A) nghĩ rằng đó là khóa của (B)). Sau đó, (C) đọc tất cả văn bản mã hóa do (A) gửi, giải mã với khóa bí mật của mình, giữ 1 bản copy đồng thời mã hóa bằng khóa công khai của (B) và gửi cho (B). Về nguyên tắc, cả (A) và (B) đều không phát hiện ra sự can thiệp của người thứ ba. Các phương pháp chống lại dạng tấn công này thường dựa trên các chứng thực khóa công khai (digital certificate) hoặc các thành phần của hạ tầng khóa công khai (public key infrastructure - PKI). [6] * Tấn công dựa trên thời gian Vào năm 1995, Paul Kocher mô tả một dạng tấn công mới lên RSA: Nếu kẻ tấn công nắm đủ thông tin về phần cứng thực hiện mã hóa và xác định được thời gian giải mã đối với một số bản mã lựa chọn thì có thể nhanh chóng tìm ra khóa d. Dạng tấn công này có thể áp dụng đối với hệ thống chữ ký điện tử sử dụng RSA. Năm 2003, Dan Boneh và David Brumley chứng minh một dạng tấn công thực tế hơn: Phân tích thừa số RSA dùng mạng máy tính (Máy chủ web dùng SSL). Tấn công đã khai thác thông tin rò rỉ của việc tối ưu hóa định lý số dư Trung quốc mà nhiều ứng dụng đã thực hiện. Để chống lại tấn công dựa trên thời gian là đảm bảo quá trình giải mã luôn diễn ra trong thời gian không đổi bất kể văn bản mã. Tuy nhiên, cách này có thể làm giảm hiệu suất tính toán. Thay vào đó, hầu hết các ứng dụng RSA sử dụng một kỹ thuật gọi là che mắt. Kỹ thuật này dựa trên tính nhân của RSA: thay vì tính cd mod n, đầu tiên chọn một số ngẫu nhiên r và tính (rec)d mod n. Kết quả của phép tính này là rm mod n và tác động của r sẽ được loại bỏ bằng cách nhân kết quả với nghịch đảo của r. Đối với mỗi văn bản mã, người ta chọn một giá trị của r. Vì vậy, thời gian giải mã sẽ không còn phụ thuộc vào giá trị của văn bản mã. [6] * Tấn công bằng phương pháp lựa chọn thích nghi bản mã. Năm 1981, Daniel Bleichenbacher mô tả dạng tấn công lựa chọn thích nghi bản mã (adaptive chosen ciphertext attack) đầu tiên có thể thực hiện trên thực tế đối với một văn bản mã hóa bằng RSA. Văn bản này được mã hóa dựa trên tiêu chuẩn PKCS #1 v1, một tiêu chuẩn chuyển đổi bản rõ có khả năng kiểm tra tính hợp lệ của văn bản sau khi giải mã. Do những khiếm khuyết của PKCS #1, Bleichenbacher có thể thực hiện một tấn công lên bản RSA dùng cho giao thức SSL (tìm được khóa phiên). Do phát hiện này, các mô hình chuyển đổi an toàn hơn như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding) được khuyến cáo sử dụng. Đồng thời phòng nghiên cứu của RSA cũng đưa ra phiên bản mới của PKCS #1 có khả năng chống lại dạng tấn công nói trên. [6] b. Hệ chữ ký ElGammal Hệ chữ ký ElGammal được đưa ra vào 1985. Một phiên bản sửa đổi hệ này được Học viện Quốc gia tiêu chuẩn và kỹ thuật (NIST) đưa ra như một chuẩn của chữ ký điện tử [1 – tr103]. Hệ chữ ký ElGammal được thiết kế riêng biệt cho mục đích chữ ký, trái ngược với RSA thường được sử dụng cho cả mục đích mã hoá công khai và chữ ký. Hệ chữ ký ElGammal là không xác định, nghĩa là có rất nhiều giá trị chữ ký cho cùng một bức điện cho trước. Thuật toán xác minh phải có khả năng nhận bất kỳ giá trị chữ ký nào như là việc xác thực. Sơ đồ chữ ký ElGammal được miêu tả như sau: Cho p là một số nguyên tố như là bài toán logarit rời rạc trong Zp, α € Zp* là một phần tử nguyên tử và P = Zp*, A = (Zp*)*Zp-1, và định nghĩa: K = {(p, α, a, β) : β ≡ αa (mod p)} trong đó giá trị p, α và β là công khai, còn a là bí mật [1 – tr103]. Với K = (p, α, a, β) và chọn một số ngẫu nhiên k € Zp-1*, định nghĩa: SigK(x, k) = (γ, δ) trong đó: γ = αk mod p δ = (x - a* γ)k-1 mod (p – 1). Với x, γ € Zp* và δ € Zp-1, định nghĩa: Ver(x, γ, δ) = TRUE ó β γ γ δ ≡ αx (mod p). Nếu chữ ký là đúng thì việc xác nhận thành công khi: β γ γ δ ≡ αaγαkδ (mod p) ≡ αx (mod p). trong đó: aγ + kδ ≡ x (mod p -1). B sẽ tính toán chữ ký bằng việc sử dụng cả giá trị bí mật a (một phần của khoá) và số bí mật ngẫu nhiên k (giá trị để ký bức điện). Việc xác minh có thể thực hiện được chỉ với các thông tin được công khai: Ví dụ: Chúng ta chọn p = 467, α = 2, a = 127. Ta tính: β = αa mod p = 2127 mod 467 = 132. Bây giờ B muốn ký lên bức điện x = 100 và anh ta chọn một giá trị ngẫu nhiên k = 213 (chú ý là UCLN(213, 466) = 1 và 213-1 mod 466 = 431). Sau đó tính: γ = 2213 mod 467 = 29 δ = (100 – 127*29)431 mod 466 = 51. Bất cứ ai cũng có thể kiểm tra chữ ký này bằng cách tính: 132292951 ≡ 189 (mod 467) 2100 ≡ 189 (mod 467). Giả sử kẻ thứ ba C muốn giả mạo chữ ký của B trên bức điện x mà không biết số bí mật a. Nếu C chọn một giá trị γ và cố gắng tìm δ, anh ta phải tính một hàm logarit rời rạc logγαxβ-γ. Mặt khác, nếu đầu tiên anh ta chọn δ để cố gắng tìm γ thì anh ta phải tính αxβγ= αx (mod p). Cả hai việc này đều không thể thực hiện được [1]. Tuy nhiên có một lý thuyết mà C có thể ký lên một bức điện ngẫu nhiên bằng cách chọn đồng thời γ, δ và x. Cho i, j là số nguyên với 0 ≤ i, j ≤ p - 2, và UCLN(j, p - 1) = 1. Sau đó tính: γ = αiβj mod p δ = - γj-1 (mod p-1) x = - γij-1 (mod p-1). Như vậy, ta xem (γ, δ) là giá trị chữ ký cho bức điện x. Việc xác minh sẽ thực hiện như sau: Ví dụ: Như ví dụ trên, ta chọn p = 467, α = 2, β = 132. Kể thứ ba C sẽ chọn i = 99 và j = 179. Anh ta sẽ tính: γ = 299132179 mod 467 = 117 δ = -117*151 mod 466 = 41 x= 99*44 mod 466 = 331 Cặp giá trị (117, 41) là giá trị chữ ký cho bức điện 331. Việc xác minh được thực hiện như sau: 13211711741 ≡ 303 (mod 467) 2331 ≡ 303 (mod 467). Một phương pháp thứ hai có thể giả mạo chữ ký là sử dụng lại chữ ký của bức điện trước đó, nghĩa là với cặp (γ, δ) là giá trị chữ ký của bức điện x, nó sẽ được C ký cho nhiều bức điện khác. Cho h, i và j là các số nguyên, trong đó 0≤ i, j, h ≤ p-2 và UCLN(hγ-jδ, p-1) = 1. λ = γhαiβj mod p μ = δλ(hγ - jδ)-1 mod (p-1) x’ = λ(hx + iδ)(hγ - jδ)-1 mod (p-1). Ta có thể kiểm tra: βλλμ = αx’ mod p. Và do đó, (λ, μ) là cặp giá trị chữ ký của bức điện x’. Điều thứ ba là vấn đề sai lầm của người ký khi sử dụng cùng một giá trị k trong việc ký hai bức điện khác nhau. Cho (γ, δ1) là chữ ký trên bức điện x1 và (γ, δ2) là chữ ký trên bức điện x2. Việc kiểm tra sẽ thực hiện: βγγδ1≡ αx1 (mod p) βγγδ2 ≡ αx2 (mod p). Do đó: αx1-x2 ≡ γy1-y2 mod p. Đặt γ = αk, khi đó: x1 - x2 = k(δ1 - δ2) (mod p-1). Bây giờ đặt d = UCLN(δ1 - δ2, p - 1). Vì d | (δ1 - δ2) và d | (p - 1) nên nó cũng chia hết cho (x1 - x2). Ta đặt tiếp: x’ = (x1-x2) /d. δ’ = (δ1- δ2)/d. p’ = (p-1)/d. Cuối cùng, ta được: x’ ≡ kδ’ (mod p’). Vì UCLN(δ’, p’) = 1 nên ta có: ε = (δ’)-1 mod p’ Như vậy, giá trị k sẽ được xác định như sau: k = x’ε (mod p’) = x’ε + ip’ (mod p) Với 0 ≤ i ≤ d-1, ta có thể tìm được giá trị k duy nhất bằng hàm kiểm tra: γ ≡ αk mod p. [1 – tr104 > tr106] c. Chuẩn chữ kí số (DSS) Chuẩn chữ ký điện tử (DSS) được sửa đổi từ hệ chữ ký ElGammal. Nó được công bố tại hội nghị Tiêu chuẩn xử lý thông tin Liên Bang (FIPS) vào 19/05/1994 và trở thành chuẩn vào 01/12/1994. DSS sử dụng một khoá công khai để kiểm tra tính toàn vẹn của dữ liệu nhận được và đồng nhất với dữ liệu của người gửi. DSS cũng có thể sử dụng bởi người thứ ba để xác định tính xác thực của chữ ký và dữ liệu trong nó. Đầu tiên chúng ta hãy tìm hiểu động cơ của sự thay đổi này, sau đó sẽ tìm hiểu thuật toán của DSS [1 – tr106]. Trong rất nhiều trường hợp, một bức điện có thể được mã hoá và giải mã một lần, vì vậy nó đáp ứng cho việc sử dụng của bất kỳ hệ thống bảo mật nào được biết là an toàn lúc bức điện được mã hoá. Nói cách khác, một bức điện được ký đảm nhiệm chức năng như một văn bản hợp pháp, chẳng hạn như các bản hợp đồng, vì vậy nó cũng giống như việc cần thiết để xác minh chữ ký sau rất nhiều năm bức điện được ký. Điều này rất quan trọng cho việc phòng ngừa về độ an toàn của chữ ký được đưa ra bởi một hệ thống bảo mật. Vì hệ chữ ký ElGammal không đảm nhận được điều này, việc thực hiện này cần một giá trị lớn modulo p. Tất nhiên p nên có ít nhất 512 bit, và nhiều người cho rằng độ dài của p nên là 1024 bit nhằm chống lại việc giả mạo trong tương lai [1 – tr107]. Tuy nhiên, ngay cả một thuật toán modulo 512 bit dùng để ký cũng phải thực hiện việc tính toán đến 1024 bit. Cho ứng dụng tiềm năng này, có rất nhiều card thông minh được đưa ra, nhằm thực hiện một chữ ký ngắn hơn như mong muốn. DSS đã sửa đổi hệ chữ ký ElGammal cho phù hợp theo cách này một cách khéo léo, để mỗi 160 bit bức điện được ký sử dụng một chữ ký 320 bit, nhưng việc tính toán được thực hiện với 512 bit modulo p. Cách này được thực hiện nhờ việc chia nhỏ Zp* thành các trường có kích thước 2160. Việc thay đổi này sẽ làm thay đổi giá trị δ: δ = (x + αγ)k-1 mod(p - 1). Điều này cũng làm cho giá trị kiểm tra cũng thay đổi: αxβγ ≡ γδ (mod p). (1.1) Nếu UCLN(x + αγ, p - 1) = 1 thì sẽ tồn tại δ-1 mod (p - 1), do đó (1.1) sẽ biến đổi thành: αxδ-1βγδ-1 ≡ γ (mod p). (1.2) Đây chính là sự đổi mới của DSS. Chúng ta cho q là một số nguyên tố 160 bit sao cho q | (p-1), và α là một số thứ q của 1 mod p, thì β và γ cũng là số thứ q của 1 mod p. Do đó α, β và γ có thể được tối giản trong modulo p mà không ảnh hưởng gì đến việc xác minh chữ ký. Sơ đồ thuật toán như sau: Cho p là một số nguyên tố 512 bit trong trường logarit rời rạc Zp; q là một số nguyên tố 160 bit và q chia hết (p-1). Cho α € Zp*; P = Zp*, A = Zq*Zq, và định nghĩa: K = {(p, q, α, a, β) : β ≡ αa (mod p)} trong đó giá trị p, q, α và β là công khai, còn a là bí mật. Với K = (p, α, a, β) và chọn một số ngẫu nhiên k (1 ≤ k ≤ q-1), định nghĩa: sigK(x, k) = (γ, δ) trong đó: γ = (αk mod p) mod q δ = (x + a*γ)k-1 mod q. Với x € Zp* và γ, δ € Zq, việc xác minh được thực hiên bằng cách tính: e1 = x δ-1 mod q e2 = γ δ-1 mod q Ver(x, γ, δ) = TRUE ó αe1βe2 ( mod p) mod q = γ. Chú ý rằng, với DSS thì δ # 0 (mod q) vì giá trị: δ-1 mod q cần cho việc xác minh chữ ký (điều này cũng tương tự như việc yêu cầu UCLN(δ, p-1) = 1 để (1.1) → (1.2)). Khi B tính một giá trị δ ≡ 0 (mod q) trong thuật toán ký, anh ta nên bỏ nó đi và chọn một số ngẫu nhiên k mới. Ví dụ: Chúng ta chọn q = 101 và p = 78*q + 1 = 7879 và g = 3 là một nguyên tố trong Z7879. Vì vậy , ta có thể tính: α = 378 mod 7879 = 170. Chọn a = 75, do đó: β = αa mod 7879 = 4567. Bây giờ, B muốn ký một bức điện x = 1234, anh ta chọn một số ngẫu nhiên k = 50. Vì vậy : k-1 mod 101 = 99. Tiếp đó: γ = (17050 mod 7879) mod 101 = 2518 mod 101 = 94 δ = (1234 + 75*94)99 mod 101 = 97. Cặp chữ ký (94, 97) cho bức điện 1234 được xác thưc như sau: δ-1 = 97-1 mod 101 = 25 e1 = 1234*25 mod 101 = 45 e2 = 94*25 mod 101 = 27 (17045456727 mod 7879) mod 101 = 2518 mod 101 = 94. Kể từ khi DSS được đề xuất vào năm 1991, đã có nhiều phê bình đưa ra. Chẳng hạn như kích cỡ của moduloe p bị cố định 512 bit, điều mà nhiều người không muốn. Vì vậy, NIST đã thay đổi chuẩn này để có thể thay đổi kích thước moduloe (chia bởi 64) thành một dãy từ 512 đến 1024 bit [1 – tr107 > tr108]. 4. Hàm băm và kết hợp hàm băm vào chữ ký điện tử. Kết hợp hàm băm vào chữ ký điện tử: Từ file cần gửi ban đầu, chúng ta sẽ sử dụng hàm băm để băm (mã hóa) thành chuỗi ký tự có độ dài cố định, với hàm băm MD5 cho ta chuỗi có độ dài 128 bit, hàm băm SHA cho ta chuỗi có độ dài 160 bit gọi là bản tóm lược. Sau đó dùng ký số ký lên bản tóm lược để trở thành bản chữ ký điện tử, tiếp theo gửi cho người nhận hai file là file cần gửi và bản chữ ký điện tử. Khi người nhận nhận được sẽ thực hiện Xác nhận chữ ký để xác nhận người gửi đồng thời dùng hàm băm - băm file gửi kèm sau đó so sánh với bản tóm lược để xác định thông tin có sự thay đổi hay không. IV. Cài đặt minh họa sơ đồ ký số RSA kết hợp băm SHA. + Các bước thực hiện của chương trình. a. Phát sinh khóa: Từ cặp số nguyên tố bất kỳ ban đầu, chương trình sẽ thực hiện tính toán để đưa ra cặp khóa công khai (e, n) và khóa bí mật (d, n). Sau đó khóa công khai được tiết lộ ra công cộng, khóa bí mật được giữ lại. b. Ký chữ ký điện tử: .................................................................... Phần này đã được cắt bỏ, hãy liên hệ chủ đề tài để nhận được bản chi tiết hơn. ............................................................. - Một số hàm sử dụng trong chương trình. // Kt số nguyên tố public Boolean ktnt(long k) { if (k < 2) return false; for (int i = 2; i <= k / 2; i++) if (k % i == 0) return false; return true; } // Tìm số lớn nhất trong 2 số public long max(long a, long b) { long max; if (a >= b) max = a; else max = b; return max; } // Tìm ước chung lớn nhất của 2 số public long ucln(long a, long b) { int ucln, r; while (b != 0) { r = a % b; a = b; b = r; } ucln = a; return ucln; } //Tính nghịch đảo của a trong Zb public long nd(long a, long b) { long kq, i = 1; while ((((i * b) + 1) % a) != 0) { i++; } kq = ((i * b) + 1) / a; return kq; } //Tinh x^y mod N (tính theo dạng số dư) public static long tinh1(long x, long y, long n) { long kq; kq = x % n; for (long f = 1; f < y; f++) { kq = (kq * x ) % n; } return kq; } - Giao diện của chương trình: Ký: Xác nhận chữ ký: Phần 3. Kết luận: + Những phần đã làm được. - Đã tìm hiểu, nghiên cứu cơ sở lý luận về an toàn, chứng thực thông tin. - Đã tìm hiểu về chữ ký điện tử. - Đã tìm hiểu về các phương thức mã hóa dữ liệu cơ bản, tìm hiểu về hàm băm. - Đã tìm hiểu về phương thức mã hóa bất đối xứng sử dụng cho chữ ký điển tử. - Đã tìm hiểu về các hệ chữ ký điện tử cơ bản và hệ chữ ký RSA ứng dụng cho chữ ký điện tử. - Đã cài đặt thành công chương trình minh họa ký số. + Những phần chưa làm được - Do năng lực và thời gian có hạn nên trong quá trình nghiên cứu còn nhiều phần còn chưa thực hiện được như chương trình chưa thực hiện được với số nguyên tố lớn, hàm băm sử dụng trong chương trình chưa được cài đặt bằng thuật toán. - Chương trình cài đặt chưa có tính ứng dụng vào thực tế. + Hướng phát triển của đề tài. - Có thể nghiên cứu sâu hơn các vấn đề đưa ra và thực hiện hoàn thiện các chức năng của chương trình để ứng dụng được vào trong đời sống, phục vụ nhu cầu và mục đích của người sử dụng. + Tài liệu tham khảo + Phụ lục - Cách liên hệ để lấy bài hoàn chỉnh: Để lấy bài hoàn chỉnh. Có thể lấy thêm phần code (nguyên code + phần cài đặt), xin hãy liên hệ mail or số đt trên để liên hệ lấy bài. Phí: bài khóa luận 50.k, Code: 100.k Liên hệ: mail: Hainhat007@gmail.com or 0982.070.520 (có thể sms)