Chữ ký số người xác nhận không thể chối bỏ

ểm tra để tin tưởng rằng chúng không bị sửa đổi so với dạng nguyên thuỷ của mình và chúng đúng là của người nhận gửi nó cho ta. Mạng máy tính có đặc điểm nổi bật là có nhiều người sử dụng, nhiều người cùng khai thác một kho tài nguyên, đặc biệt là tài nguyên thông tin và các điểm có người sử dụng thường phân tán về mặt địa lý. Các điểm này thể hiện lợi ích to lớn của mạng thông tin máy tính đồng thời nó cũng là điều kiện thuận lợi cho những người muốn phá hoại an toàn thông tin trên mạng máy tính. Do đó cách tốt nhất để bảo mật thông tin là mã hoá thông tin trước khi gửi đi. Mục tiêu cơ bản của mật mã là cho phép 2 người, thường được đề cập đến như Alice và Bob, liên lạc trên kênh không an toàn theo cách mà đối thủ Orcar không thể hiểu cái gì đang được nói. Kênh này có thể là đường điện thoại hoặc mạng máy tính. Thông tin mà Alice muốn gửi đến Bob sẽ được gọi là “bản rõ” (plaintext), có thể là bất kỳ tài liệu nào có cấu trúc tuỳ ý. Alice mã bản rõ bằng cách dùng khoá xác định trước, và gửi bản rõ thu được trên kênh không an toàn. Orcar dù thu trộm được mã trên kênh song không thể hiểu được bản rõ là gì, nhưng Bob là người biết khoá mã có thể giải mã và thiết lập bản rõ. Có hai loại mật mã là mật mã bí mật và mật mã khoá công khai.Trong mật mã bí mật, 2 người muốn trao đổi thông tin cho nhau phải thoả thuận chọn một cách bí mật khoá k. Từ k suy ra quy tắc mã hoá ek và quy tắc giải mã dk. Trong các hệ mật này, dk hoặc trùng với ek hoặc dễ dàng rút ra từ ek và việc tiết lộ ek sẽ làm cho hệ thống không an toàn. Độ an toàn hệ mật chính là độ an toàn tính toán. Trong thực tế, một hệ mật là “an toàn tính toán” nếu phương pháp tốt nhất đã biết để phá nó yêu cầu một số lớn không hợp lý thời gian tính toán, nghĩa là quá trình thực hiện tính toán cực kỳ phức tạp, phức tạp đến mức ta coi là “không thể được”. Hệ mật khoá công khai đã đáp ứng được những đòi hỏi đó. ý tưởng nằm sau hệ mật khoá công khai là ở chỗ nó có thể tìm ra một hệ mật trong đó không thể tính toán để xác định dk khi biết ek. Quy tắc mã ek có thể công khai. Hàm mã hoá công khai ek phải dễ dàng tính toán nhưng việc giải mã phải khó đối với bất kỳ người nào ngoài người lập mã. Tính chất dễ tính toán và khó đảo ngựơc này thường được gọi là tính chất một chiều. Muốn giải mã các thông báo nhận được một cách hiệu quả ta cần có một cửa sập 1 chiều. Điều này đảm bảo độ bí mật cao. Mặt khác, mã hoá còn bao gồm cả xác thực và chữ ký số. Xác thực có nhược điểm là ở đây 2 bên cùng có chung một khoá nên không thể phân xử được khi 1 trong 2 người chối bỏ thông báo họ đã gửi cho người kia. Hơn nữa, trong mạng có nhiều người sử dụng, nếu mỗi cặp có một khoá thoả thuận như vậy thì mỗi người phải lưu giữ n-1 khoá bí mật. Khi n đủ lớn, đó là một việc phiền phức, phức tạp. Chính vì vậy mà chữ ký số được sử dụng nhiều hơn. Chữ ký số có nhiệm vụ giống chữ ký tay nghĩa là nó dùng để thực hiện các chức năng xác nhận của một người gửi trên một văn bản. Nó phải vừa mang dấu vết không chối cãi được của người gửi, vừa gắn với từng bit của văn bản mà nếu thay đổi dù chỉ một bit của văn bản thì chữ ký cũng không còn được chấp nhận. Nói chung các lược đồ chữ ký thì không cần đối thoại. Nhưng trong một số trường hợp để tăng thêm trách nhiệm trong việc xác nhận, người ta dùng các giao thức hỏi- đáp để xác định độ tin cậy của chữ ký. Trong đồ án này tôi đi sâu tìm hiểu về lược đồ chữ ký chống chối bỏ có người xác nhận. ở đây chữ ký có thể được kiểm tra mà không cần đến sự cộng tác của người ký mà là một người thứ 3- người xác nhận. Chương I TổNG QUAN Về NGÔN NGữ C I.1. Lịch sử hình thành và phát triển Ngôn ngữ C do Brian W.Kernighan và Dennis M.Ritchie phát triển vào đầu những năm 70 tại phòng thí nghiệm BELL ( Hoa Kỳ) với mục đích ban đầu là để phát triển hệ điều hành UNIX. Bối cảnh ra đời xuất phát từ nhu cầu cần phải có một ngôn ngữ lập trình hệ thống thay thế cho hợp ngữ (Assembly) vốn nặng nề, độ tin cậy thấp và khó chuyển đổi giữa các hệ máy tính khác nhau. Ngoài việc C được dùng để viết hệ điều hành UNIX, người ta nhanh chóng nhận ra sức mạnh của C trong việc xử lý các vấn đề hiện đại của tin học: xử lý số, văn bản, cơ sở dữ liệu, lập trình hướng đối tượng. C đã trở thành một chuẩn mặc nhiên. Liên quan đến sự hình thành và phát triển của ngôn ngữ, có thể kể đến một số sự kiện sau: - Năm 1978, cuốn giáo trình dạy lập trình bằng ngôn ngữ C “The C programming langguage” do chính 2 tác giả của ngôn ngữ Brian W.Kernighan và Dennis M.Ritchie biên soạn đã được xuất bản và được phổ biến rộng rãi. - Năm 1983 một tiểu ban của viện tiêu chuẩn quốc gia Mỹ (ANSI) được thành lập nhằm đề xuất ra một chuẩn cho ngôn ngữ C. - Năm 1988 chuẩn ANSI C chính thức được ban hành. Chuẩn này bao gồm các mô tả về ngôn ngữ theo Brian W.Kernighan và Dennis M.Ritchie và quy định các thư viện chuẩn của ngôn ngữ C, nhờ đó tăng tính khả chuyển của chương trình viết bằng C. - Trong thế giới máy vi tính có các hệ chương trình dịch C nổi tiếng như: Turbo C, Borland C của Borland Inc; MSC, VC của Microsoft Corp; Lattice C của Lattice. I. 2. Các tính chất đặc trưng của ngôn ngữ C là một ngôn ngữ lập trình vạn năng được dùng để viết các hệ điều hành như UNIX cũng như các chương trình ứng dụng như quản lý văn bản, cơ sở dữ liệu. C là một ngôn ngữ có mức độ thích nghi cao, gọn và không nhất thiết phải cần tới hợp ngữ. C độc lập với bất kỳ kiến trúc máy đặc thù nào và với một chút thận trọng vẫn dễ dàng viết được các chương trình “khả chuyển” (portability) tức là những chương trình có thể chạy mà không cần phải thay đổi gì khi có sự thay đổi về phần cứng. C được sử dụng rộng rãi trong các lĩnh vực chuyên nghiệp vì đáp ứng được các yêu cầu: hiệu quả cao trong soạn thảo chương trình và dịch ra mã máy; tiếp cận trực tiếp với các thiết bị phần cứng. C không đưa ra các phép toán xử lý trực tiếp các đối tượng hợp thành như là đối tượng toàn vẹn; không xác định bất kỳ một phương tiện cấp phát bộ nhớ nào khác ngoài cấp phát tĩnh, cấp phát động theo nguyên tắc xếp chồng cho các biến cục bộ của hàm; không cung cấp cơ chế I/O, không có phương pháp truy nhập tệp. Tất cả các cơ chế này được thực hiện bằng những lời gọi hàm trong thư viện. C đưa ra các kết cấu điều khiển cơ bản cần cho các chương trình có cấu trúc như: nhóm tuần tự các câu lệnh, chọn quyết định (if); chu trình với phép kiểm tra kết thúc ở đầu (for, while), hoặc ở cuối (do...while); và việc lựa chọn một trong các trường hợp có thể (switch). C cung cấp con trỏ và khả năng định địa chỉ số học. Các đối của hàm được truyền bằng cách sao chép giá trị đối và hàm được gọi không thể thay đổi được giá trị của đối hiện tại. C cho phép hàm được gọi đệ quy và các biến cục bộ của hàm sẽ “tự động” sinh ra hoặc tạo mới với mỗi lần gọi mới. Các định nghĩa hàm không được lồng nhau nhưng các biến có thể được khai báo theo kiểu cấu trúc khối. Các hàm có thể dịch tách biệt. Các biến có thể trong hoặc ngoài hàm. Hàm chỉ biết được các biến ngoài trong cùng một tệp gốc, hoặc biến tổng thể extern. Các biến tự động có thể đặt trong các thanh ghi để tăng hiệu quả, nhưng việc khai báo thanh ghi chỉ là một hướng dẫn cho chương trình dịch và không liên quan gì đến các thanh ghi đặc biệt của máy. C không phải là một ngôn ngữ có kiểu mạnh mẽ theo nghĩa của PASCAL hoặc ALGOL/68. Nó tương đối thoải mái trong chuyển đổi dữ liệu nhưng không tự động chuyển các kiểu dữ liệu một cách phóng túng như của PL/I. Các chương trình dịch hiện có đều không đưa ra cơ chế kiểm tra chỉ số mảng, kiểu đối số… Mặc dù vậy, C vẫn còn tồn tại một số nhược điểm như một số phép toán có thứ tự thực hiện chưa đúng; một số phần cú pháp có thể làm tốt hơn; hiện có nhiều phiên bản của ngôn ngữ, chỉ khác nhau ở một vài chi tiết. Tóm lại, C vẫn tỏ ra là một ngôn ngữ cực kỳ hiệu quả và đầy sức diễn cảm đối với nhiều lĩnh vực ứng dụng lập trình. Hơn nữa, ta biết rằng hệ mật chuẩn hay chữ ký số luôn cần một bộ số rất lớn tức là kích cỡ của không gian khoá rất lớn khoảng trên 300 số thập phân. Do đó, ngôn ngữ C đủ mạnh để có thể đáp ứng được điều đó. Chương II CHữ Ký Số II.1. Giới thiệu chung về chữ ký số Như chúng ta đã biết, chữ ký viết tay “thường lệ” gắn với tài liệu được dùng để chỉ ra người đã ký nó. Chữ ký được sử dụng hàng ngày như để viết thư, ký hợp đồng... ở đây, chúng ta tìm hiểu về chữ ký hoàn toàn khác đó là chữ ký số. Nó là phương pháp ký thông báo được lưu dưới dạng điện tử và thông báo được ký có thể truyền trên mạng máy tính. Chữ ký tay và chữ ký số dù cùng có nhiệm vụ chung là ký nhưng có sự khác nhau cơ bản giữa chúng. Thứ nhất, về việc ký tài liệu: Với chữ ký tay thì chữ ký là bộ phận vật lý của tài liệu được ký. Tuy nhiên, chữ ký số không gắn một cách vật lý với thông báo được ký mà được gắn với thông báo theo logic, do đó thuật toán được dùng phải “trói” chữ ký với thông báo theo một cách nào đó. Thứ hai, về việc kiểm tra: chữ ký tay được kiểm tra bằng cách so sánh nó với những cái khác, những chữ ký đã xác thực. Ví dụ, một người ký trên một tấm séc mua hàng, người bán hàng phải so sánh chữ ký trên tấm séc với chữ ký nằm ở sau thẻ tín dụng để kiểm tra. Tất nhiên, phương pháp này không an toàn lắm vì nó tương đối dễ đánh lừa bởi chữ ký của người khác. Khác với chữ ký tay, chữ ký số có thể được kiểm tra bằng cách dùng thuật toán kiểm tra công khai đã biết. Vì vậy, bất kỳ người nào đó đều có thể kiểm tra chữ ký số. Và việc sử dụng lược đồ ký an toàn sẽ ngăn chặn khả năng đánh lừa. Điều khác nhau cơ bản giữa chữ ký tay và chữ ký số là “bản sao” thông báo số được ký là đồng nhất với bản gốc. Trong khi đó, bản sao chép tài liệu giấy đã ký thường là khác với bản gốc. Điều này nghĩa là phải cẩn thận để ngăn chặn một thông báo đã ký số bị sử dụng lại. Ví dụ, nếu Bob ký thông báo số cho quyền Alice rút $100 từ tài khoản ở nhà băng của mình, anh ta chỉ muốn Alice làm việc đó một lần. Do đó, thông báo tự nó phải chứa thông tin để ngăn chặn Alice làm lại việc đó nhiều lần. Lược đồ chữ ký số gồm 2 thành phần: một thuật toán ký và một thuật toán kiểm tra. Bob có thể ký thông báo x nhờ thuật toán ký (bí mật) Sig. Chữ ký thu được Sig(x) sau đó có thể được kiểm tra nhờ thuật toán kiểm tra công khai Ver. Khi cho cặp (x,y) thuật toán kiểm tra sẽ trả lời “đúng” hoặc “sai” phụ thuộc vào việc chữ ký có đích thực không? II. 2. Định nghĩa lược đồ chữ ký số Lược đồ chữ ký số là một bộ năm phần tử (P, A, K, S, V) thoả mãn các điều kiện sau: P _ là một tập hữu hạn các thông báo. A _tập hữu hạn các chữ ký có thể. K _tập hữu hạn các khoá, không gian khoá. Với mỗi k ẻ K, $ sigk ẻ S và verk ẻV Mỗi sigk: Pđ A, verk: P * 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: Ver(x,y) = *Yêu cầu: - Với mỗi khoá k ẻ K, các hàm sigk và verk là các hàm thời gian đa thức. - Verk là hàm công khai; sigk là hàm bí mật để tránh trường hợp Orcar có thể giả mạo chữ ký của Bob để ký thông báo x. Với mỗi x chỉ duy nhất Bob tính được chữ ký y sao cho: Ver(x, y) = True. Lược đồ chữ ký phải an toàn. Bởi vì Orcar có thể kiểm tra tất cả các khả năng của chữ ký y nhờ thuật toán kiểm tra công khai Ver cho tới khi đạt được yêu cầu tức là tìm được chữ ký đúng. Do đó, nếu có đủ thời gian cần thiết Orcar có thể giả mạo được chữ ký của Bob. Vì vậy mục đích của chúng ta là tìm các lược đồ chữ ký sao cho Orcar không đủ thời gian thực tế để thử như thế. II. 3. Một vài lược đồ chữ ký số II.3. 1. Lược đồ chữ ký số RSA Lược đồ chữ ký RSA được định nghĩa như sau: * Tạo khoá: Cho n = p. q; với p, q là các số nguyên tố lớn khác nhau, f(n) = (p - 1)(q - 1). Cho P = A = Zn và định nghĩa: K = {(n, p, q, a, b): n = p.q; p, q là các số nguyên tố; ab º 1mod f(n)} Các giá trị n và b là công khai; các giá trị p, q, a là bí mật. * Tạo chữ ký: Với K = (n, p, q, a, b) xác định: SigK(x) = xa mod n * Kiểm tra chữ ký: VerK(x, y) = true Û x º yb mod n; x, y ẻZn. Giả sử Bob muốn ký thông báo x, anh ta tính chữ ký y bằng cách: y = sigK(x) = xamodn (aB là tham số bí mật của Bob). Bob gửi cặp (x, y) cho Alice. Nhận được thông báo x và chữ ký số y, Alice tiến hành kiểm tra đẳng thức: x = yb modn (bB là khóa công khai của Bob) Nếu đúng, Alice công nhận y là chữ ký trên x của Bob. Ngược lại, Alice sẽ coi x không phải của Bob gửi cho mình (chữ ký không tin cậy). Người ta có thể giả mạo chữ ký của Bob như sau: chọn y, sau đó tính x = verK(y), khi đó y = sigK(x). Một cách để khắc phục khó khăn này là việc yêu cầu x phải có nghĩa. Do đó chữ ký giả mạo nói trên sẽ thành công với xác suất rất nhỏ. Ta có thể kết hợp chữ ký với mã hoá sẽ làm cho độ an toàn của chữ ký tăng thêm. Giả sử rằng, Alice sẽ tính chữ ký của cô ta là y = sigAlice(x), và sau đó mã hoá cả x và y bằng cách sử dụng mật mã công khai eBob của Bob, khi đó cô ta nhận được z = eBob(x, y). Bản mã z sẽ được truyền tới Bob. Khi nhận được z, việc trước tiên là anh ta giải mã bằng hàm dBob để nhận được (x, y). Sau đó anh ta sử dụng hàm kiểm tra công khai của Alice để kiểm tra xem liệu verAlice(x, y) = true? Nếu Alice mã hoá x trước rồi sau đó mới ký lên bản mã đã được mã hoá thì sao? Khi đó cô ta tính: y = sigAlice(eBob(x)) Alice sẽ truyền cặp (z, y) cho Bob. Bob sẽ giải mã z, nhận được x và kiểm tra chữ ký y trên bằng cách sử dụng verAlice. Một vấn đề tiềm ẩn trong biện pháp này là nếu Orcar có được cặp (z, y) kiểu này, anh ta có thể thay thế chữ ký y của Alice bằng chữ ký của anh ta: y’ = sigOrcar(eBob(x)) Chú ý rằng Orcar có thể ký bản mã ebob(x) ngay cả khi anh ta không biết bản rõ x. Khi đó, nếu Orcar truyền (z, y’ ) tới Bob, chữ ký của Orcar sẽ được kiểm thử vì Bob sử dụng verOrcar, và Bob có thể suy ra rằng bản rõ x xuất phát từ Orcar. Điều này cũng làm cho người sử dụng hiểu rằng nên ký trước rồi sau đó mới tiến hành mã hoá. Ví dụ: Giả sử Bob dùng lược đồ chữ ký số RSA với n = 247 (p = 13, q = 19); f(n) = 12.18 = 216. Khoá công khai của Bob là b = 7 ị a = 7-1mod216 = 31. Bob công khai (n, b) = (247, 7). Bob ký lên thông báo x = 100 với chữ ký: y = xa modn = 10031 mod247 = 74. Bob gửi cặp (x, y) = (100, 74) cho Alice. Alice kiểm tra bằng cách sử dụng khoá công khai của Bob như sau: = yb modn = 747 mod247 = 100 = x. ị Alice chấp nhận y = 74 là chữ ký tin cậy. II.3.2. Lược đồ chữ ký ElGamal Lược đồ chữ ký số ElGamal được giới thiệu năm 1985 và được Viện tiêu chuẩn và Công nghệ quốc gia Mỹ sửa đổi thành chuẩn chữ ký số. Lược đồ ElGamal không tất định cũng giống như hệ thống mã hoá công khai ElGamal. Điều này có nghĩa là có nhiều chữ ký hợp lệ cho một thông báo bất kỳ. Thuật toán kiểm tra phải có khả năng chấp nhận bất kỳ chữ ký hợp lệ nào khi xác minh. Lược đồ chữ ký số ElGamal được định nghĩa như sau: * Tạo khoá: Cho p là số nguyên tố sao cho bài toán lôgarit rời rạc trong Zp là khó và giả sử a ẻZ là phần tử nguyên thủy. Cho P = Z, A = Z´ Zp-1 và định nghĩa: K = {(p, a, a, b): b = aa modp }. Các giá trị p, a, b là công khai, a là bí mật. * Tạo chữ ký: Với K = (p, a, a, b) và với số ngẫu nhiên k ẻZ, định nghĩa:sigk(g, d), trong đó: g = ak modp và d = (x - ag) k -1mod(p - 1). * Kiểm tra chữ ký số: Với x, g ẻ Z và d ẻZp-1, ta định nghĩa: Ver (x, g, d) = True Û bg. gd º ax modp. Chứng minh: Nếu chữ ký được thiết lập đúng thì kiểm tra sẽ thành công vì: ịbg gd º aa.g ar.d modp º ax modp ( vì ag + rd º x mod(p - 1)). Bob tính chữ ký bằng cách dùng cả giá trị bí mật a ( là một phần của khoá) lẫn số ngẫu nhiên bí mật k (dùng để ký trên x). Việc kiểm ta có thể thực hiện duy nhất bằng thông tin công khai. Ví dụ: Giả sử p = 467, a = 2, a = 127 Khi đó: b = aa modp = 2127mod467 = 132 Giả sử Bob có thông báo x = 100 và anh ta chọn ngẫu nhiên k = 213 vì (213, 466) =1 và 213-1 mod466 = 431 Bob ký trên x như sau: g = ak modp = 2213mod467 = 29 và d = (x - ag)k-1 mod(p -1) = (100 – 127. 29).431 mod466 = 51. Chữ ký của Bob trên x = 100 là (29, 51). Bất kỳ người nào đó cũng có thể kiểm tra chữ ký này bằng cách: 13229 . 2951 º 189 mod 467 2100 º 189 mod 467 Do đó chữ ký là tin cậy. Bây giờ, ta xét độ an toàn của lược đồ chữ ký ElGamal. Giả sử Orcar thử giả mạo chữ ký trên thông báo x cho trước mà không biết a. Nếu Orcar chọn giá trị g và thử tìm d tương ứng, anh ta phải tính logarit rời rạc của loggax b-g. Mặt khác, nếu anh ta chọn d trước và sau đó thử tìm g thì anh ta phải giải phương trình bg gd º ax modp, trong đó g là ẩn. Bài toán này chưa có lời giải, tuy nhiên dường như nó liên quan đến bài toán đã nghiên cứu. Vẫn còn có khả năng là tìm d và g đồng thời để (d, g) là chữ ký. Hiện thời không ai tìm được cách giải song cũng không ai khẳng định được là nó không có lời giải. Nếu Orcar chọn g và d, sau đó thử giải để tìm x, anh ta sẽ phải tính bài toán logarit rời rạc, tức phải tính loga bg gd. Vì thế Orcar không thể ký một thông điệp ngẫu nhiên bằng cách này. Tuy nhiên có một cách để Orcar ký lên thông điệp ngẫu nhiên bằng việc chọn g, d, x đồng thời. Giả thiết i và j là các số nguyên 0 Ê i Ê p – 2; 0 Ê j Ê p – 2 và (j, p - 1) =1. Khi đó thực hiện các phép tính: g = ai bj modp d = -g.j-1mod(p - 1) x = - gi.j-1mod(p - 1) = i.d mod(p - 1). Trong đó j-1 được tính theo module (p - 1). Ta thấy rằng (g, d) là chữ ký hợp lệ của x. Điều này được chứng minh qua việc kiểm tra: bg gd º b-g(ai bj )-gj modp º bg a-i.j g b-g º a-g.i.j modp º ax modp. Ví dụ: p = 467; a = 2; b = 132. Giả sử Orcar chọn i = 99; j = 179, khi đó j-1 mod(p -1) = 151. Anh ta tính: g = 299 132179mod467 = 117 d = - 177. 151 mod466 = 41 x = 99. 41 mod 466 = 331 Và (117, 41 ) là chữ ký trên x = 331. Kiểm tra: 132117 11741 º 303mod 467 và 2331 º 303 mod467 Do đó chữ ký là hợp lệ. Orcar có thể giả mạo chữ ký theo kiểu khác là bắt đầu từ thông báo x đã được Bob ký. Giả sử (g, d) là chữ ký hợp lệ trên x. Khi đó Orcar có khả năng ký lên nhiều thông báo khác nhau. Giả sử i, j, h là các số nguyên; 0 Ê h; i, j Ê p – 2 và (hg - jd, p - 1) = 1. Thực hiện các phép tính: l = gh ai bj modp m = dl(hg - jd)-1mod(p - 1) x’ = l(hx + id)(hg - jd)-1 mod(p - 1) Trong đó (hg - jd)-1được tính theo module (p - 1). Kiểm tra: bl lm º a modp ị (l, m) là chữ ký hợp lệ của x’. Cả 2 phương pháp trên đều tạo các chữ ký giả mạo hợp lệ song không xuất hiện khả năng đối phương giả mạo chữ ký trên thông điệp có lựa chọn của chính họ mà không phải giải bài toán logarit rời rạc. Vì thế không có gì nguy hiểm về độ an toàn của lược đồ ElGamal. Chương III Hàm Hash III.1. Giới thiệu Đối với xác thực và chữ ký số ta thấy rằng các thuật toán thường nhận đầu vào là một dòng bít có độ dài rất ngắn( 64,128,160 bit) và tốc độ thực hiện chậm. Mặt khác, các thông báo cần ký thường có độ dài khác nhau và trong nhiều trường hợp chúng có độ dài lớn cỡ vài Kilôbyte hoặc vài Megabyte. Do vậy, muốn ký một chữ ký ngắn trên một thông báo dài ta cần phải cắt thông báo ra nhiều đoạn có độ dài hữu hạn và cố định rồi tiến hành ký độc lập từng đoạn đó và gửi từng đoạn đó đi. Khi đó lại xuất hiện nhiều vấn đề như: - Tốc độ thực hiện sẽ rất chậm vì phải ký trên quá nhiều đoạn. - Dễ xảy ra trường hợp không sắp xếp được thông báo theo đúng trật tự ban đầu. - Có thể bị mất các đoạn riêng biệt trong quá trình truyền tin. Để giải quyết những vấn đề này ta có thể dùng hàm Hash. Hàm Hash chấp nhận một thông báo có độ dài bất kỳ làm đầu vào, hàm Hash sẽ biến đổi thông báo này thành một thông báo rút gọn, sau đó ta sẽ dùng lược đồ chữ ký để ký thông báo rút gọn. Ta có mô hình chung như sau: Thông báo x độ dài tuỳ ý Thông báo rút gọn z = h(x) 160 bit Chữ ký y = sigK(x) 320 bit Nếu không cần bí mật x ta sẽ gửi cặp (x, y) cho người nhận. Nếu cần giữ bí mật x thì ta sẽ mã hoá thông báo x thành x’ và gửi cặp (x’, y). III.2. Định nghĩa Hàm Hash là một hàm tính toán có hiệu quả khi ánh xạ các dòng nhị phân có độ dài tuỳ ý thành các dòng nhị phân có độ dài cố định nào đó. - Hàm Hash yếu: Hàm Hash được gọi là yếu nếu cho một thông báo x thì về mặt tính toán không tìm ra được thông báo x’ khác x sao cho : h(x’) = h(x) - Hàm Hash mạnh: Hàm Hash được gọi là mạnh nếu về mặt tính toán không tìm ra được hai thông báo x và x’ sao cho: x’ ạ x và h(x’) = h(x) Chọn giá trị x ngẫu nhiên, x ẻ X Tính z = h(x) Tính x1= A(z) Nếu x1ạ x thì x1 và x va chạm dưới h( thành công) Ngược lại QUIT( thất bại) - Hàm Hash có tính chất một chiều: Hàm Hash có tính chất một chiều nếu cho trước thông báo rút gọn z thì về mặt tính toán không tìm ra được thông báo x sao cho h(x) = z. Hàm Hash yếu làm cho chữ ký số trở nên tin cậy giống như việc ký trên toàn thông báo. Hàm Hash mạnh có tác dụng chống lại kẻ giả mạo tạo ra hai bản thông báo có nội dung khác nhau, sau đó thu nhận chữ ký hợp pháp cho một bản thông báo dễ được xác nhận rồi lấy nó giả mạo làm chữ ký của thông báo thứ 2. III.3. Một số hàm Hash sử dụng trong chữ ký số III.3.1. Các hàm Hash đơn giản Tất cả các hàm Hash đều được thực hiện theo nguyên tắc chung là: Đầu vào được biểu diễn dạng một dãy các khối có độ dài n bít. Các khối n bit này được xử lý theo cùng một kiểu và lặp đi lặp lại để cuối cùng cho đầu ra có số bit cố định. Hàm Hash đơn giản nhất là thực hiện phép toán XOR từng bit một của mỗi khối. Nó được biểu diễn như sau: Ci = b1i Å b2iÅ …Åbmi Trong đó: Ci: là bit thứ i của mã Hash, i = m: là số các khối đầu vào. bji: là bit thứ i trong khối thứ j Å: là phép cộng modulo 2. Sơ đồ hàm Hash sử dụng phép XOR: Khối 1: b11 b12 … b1n Khối 1: b21 b22 … b2n … … … … … Khối m: bm1 bm2 … bmn Mã Hash: C1 C2 … Cn Ci là bit kiểm tra tính chẵn lẻ cho vị trí thứ i khi ta chia tệp dữ liệu thành từng khối, mỗi khối có n vị trí. Nó có tác dụng như sự kiểm tra tổng thể tính toàn vẹn của dữ liệu. Khi mã hoá một thông báo dài thì ta sử dụng mode CBC (The Cipher Block Chaining), thực hiện như sau: Giả sử thông báo X được phân thành các khối 64 bit liên tiếp: X = X1X2 …XN Khi đó mã Hash C là: C = XNH = X1Å X2 Å…Å Xn. Sau đó mã hoá toàn bộ thông báo nối với mã Hash theo mode CBC để sản sinh ra bản mã: Y1Y2 …YN+1 III.3.2. Kỹ thuật khối xích Người đầu tiên đề xuất kỹ thuật mật mã xích chuỗi nhưng không có khoá bí mật là Rabin. Kỹ thuật này thực hiện như sau: Chia thông báo M thành các khối có cỡ cố định là M1, M2, …,MN. Sử dụng hệ mã thuận tiện như DES để tính mã Hash như sau. Ho= Giá trị ban đầu Hi = EMi(Hi-1), i = G = HN III.3.3. Các hàm Hash mở rộng ở trên, ta đề cập tới hàm Hash có miền đầu vào hữu hạn. Tiếp theo ta sẽ đề cập tới loại hàm Hash mạnh với đầu vào vô hạn thu được do mở rộng một hàm Hash mạnh có đầu vào độ dài hữu hạn. Hàm này sẽ cho phép ký các thông báo có độ dài tuỳ ý. Giả sử h: (Z2 )m đ (Z2 )t là một hàm Hash mạnh, trong đó m ³ t + 1. Ta sẽ xây dựng hàm Hash mạnh: h*: X đ (Z2 )t, trong đó = ẩ(Z2 )i * Xét trường hợp m ³ t + 2 Giả sử x ẻ X, vậy thì tồn tại n để x ẻ(Z2 )n, n ³ m. Ký hiệu: là độ dài của x tính theo bit. Khi đó: = n. Ký hiệu: x ỗỗy là dãy bit thu được do nối x với y. Giả sử = n ³ m. Ta có thể biểu diễn x như sau: x = x1 ữữ x2ữữ …ữữ xk Trong đó = = … = = m – t – 1 và = m – t – 1 – d, 0 Ê d Ê m – t – 2 ị ³ 1 và m – t – 1 ³ 1, k ³ 2. Khi đó: k = + 1 Thuật toán xây dựng h thành h* được mô tả như sau: Cho i = 1 tới k – 1 gán yi = xi; yk = xk ỗỗ 0d ( 0d là dãy có d số 0. Khi đó yk dài m – t - 1) yk+1 là biểu diễn nhị phân của d ( = m – t - 1) g1 = h( 0t+1 ỗỗ y1) ( = t, 0t+1 ỗỗ y1 dài m) Cho i = 1 tới k thực hiên: gi+1 = h( gi ỗỗ1ỗỗyi+1 ) 6. h*(x) = gk+1 Ký hiệu y(x) = y1 ỗỗy2 ỗỗ…ỗỗyk+1 Ta thấy rằng y(x) ạ y( x’ ) nếu x ạ x’ . * Xét trường hợp m = t + 1 Cũng như trên, ta giả sử = n > m Ta xác định hàm f như sau: f(0) = 0; f(1) = 01; Thuật toán xây dựng h* khi m = t + 1 như sau: 1. Cho y = y1 y2 …yk = 11ờờf(x1) ờờf(x2) ờờ …ờờf(xn) (x1 là một bit) 2. g1 = h( 0t ỗỗ y1) ( = m – t ) 3. Cho i = 1 tới k – 1 thực hiện gi+1 = h( gi ỗỗyi+1 ) ( = m – t - 1) h*(x) = gk. III.3.4. Hàm Hash MD4 Năm 1990, RIVEST đữ đề xuất hàm hash MD4, sau đó một phiên bản mạnh hơn MD4 đã ra đời vào năm 1991 đó là MD5. Cùng thời điểm đó SHS (Secure Hash Standard) phức tạp hơn ra đời. Nhưng MD5 và SHS đều dựa trên nền tảng của MD4 và SHS đã được thừa nhận như là một chuẩn hoá vào tháng 5 năm 1993. Thuật toán thực hiện MD4: Bước Mô tả 1 A = 0x67452301 B = 0xefcdab89 C = 0x89badcfe D = 0x10325476 2 For i: = 1 to N/16 do 3 For j: = 0 to 15 do X[j]: = M[16i + j] 4 AA: = A; BB: = B; CC: = C; DD: = D 5 Round1 6 Round2 7 Round3 8 AA: = A +AA; BB: = B + BB; CC: = C + CC; DD: = D + Ddmod2332 Giải thích thuật toán thực hiện MD4: Giả sử x là một thông báo cần hash. Đầu tiên bổ sung số 1 nối vào x, sau đó là dãy các số 0 sao cho độ dài thu được đồng dư với 448mod512. Cuối cùng, gắn thêm 64 bit nữa vào để được thông báo mở rộng. Đây là 64 bit biểu diễn nhị phân độ dài nguyên thuỷ của x. Kết quả ta được thông báo mở rộng M có độ dài chia hết cho 512. Vì vậy khi cắt thành những từ có độ dài 32 bit ta sẽ được số N chia hết cho 16. Biểu diễn M đưới dạng dãy liên tiếp N các từ có độ dài 32 bit: M = M[0] M[1] …M[N – 1] Do ùMù chia hết cho 512 nên N chia hết cho 16. Thuật toán xây dựng M trong MD4 như sau: Bước 1: d = 447 – (ùxùmod512) Bước 2: Cho l biểu diễn nhị phân của ùxùmod264, ùlù= 64 Bước 3: M = xùù1ùù0dùùl Trong khi xây dựng M chúng ta bổ sung l vào x và thêm toàn số 0 sao cho độ dài đồng dư với 448mod512 (độ dài º mod512) và cuối cùng gắn thêm 64 bit biểu diễn nhị phân độ dài nguyên thuỷ của x. Kết quả chuỗi M có độ dài chia hết cho 512. Vì vậy khi cắt thành những từ có độ dài 32bit ta sẽ được số N chia hết cho 16. Chúng ta tiếp tục xây dựng thông báo rút gọn có độ dài 128 bit được mô tả dựa trên thuật toán xây dựng M. Một thông điệp thu gọn được xây dựng như một sự ghép của 4 từ A, B, C, D. Các từ này gần tương tự như 4 thanh ghi trong máy tính. Các thanh ghi có giá trị khởi tạo từ bước 1. Xử lý mảng M[] tại một thời điểm, thực hiện 16 từ của M[] và lưu trữ chúng trong mảng X[] tại bước 3. Tại bước 4 giá trị của A, B, C, D được lưu trữ trong các biến AA, BB, CC, DD. Sau đó chúng ta thực hiện 3 vòng lặp của hashing. Mỗi vòng thực hiện các phép toán số học và logic trên 16 từ của X, các toán hạng này sau khi thực hiện trong 3 vòng sẽ cho giá trị mới bằng cách cộng vào các giá trị được lưu trữ trong bước 4. Đây là phép cộng các số nguyên được rút gọn bằng phép module 232. Khi MD4 thực hiện đầy đủ thì một điều cần thiết phải tính đến đó là cấu trúc của bộ vi xử lý trong máy tính nhằm mục đích thực hiện các phép cộng chính xác nhất. Trong 3 vòng Round1, Round2, Round3 của MD4 thực hiện các phép toán logic sau: + a << s: phép quay vòng dịch trái đại lượng a đi s bit, 1 Ê s Ê 32 +ỉa: phép đảo bit + Ù: phép and + Ú: phép or + Å: phép Xor + “+”: cộng 2 số nguyên theo module 232 Mỗi vòng chỉ sử dụng một trong 3 hàm f, g, h: f(A, B, C) = (AÙB)Ú(AC) g(A, B, C) = (AÙB)Ú(AÙC)Ú(BÙC) h(A, B, C) = A Å B Å C Ta ký hiệu các hằng số: K1 = 0x5a827999 K2 = 0x6ed9eba1 Các biến Xi, i = Bảng chân lý của 3 hàm: A B C f(A, B, C) g(A, B, C) h(A, B, C) 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 3 vòng Round1, Round2, Round3 được mô tả theo bảng sau: Round1: 1 A = (A + f(B, C, D) + Xo)<<3 2 D = (D + f(A, B, C) + X1)<<7 3 C = (C + f(D, A, B) + X2)<<11 4 B = (B + f(C, D, A) + X3)<<19 5 A = (A + f(B, C, D) + X4)<<3 6 D = (D + f(A, B, C) + X5)<<7 7 C = (C + f(D, A, B) + X6)<<11 8 B = (B + f(C, D, A) + X7)<<19 9 A = (A + f(B, C, D) + X8)<<3 10 D = (D + f(A, B, C) + X9)<<7 11 C = (C + f(D, A, B) + X10)<<11 12 B = (B + f(C, D, A) + X11)<<19 13 A = (A + f(B, C, D) + X12)<<3 14 D = (D + f(A, B, C) + X13)<<7 15 C = (C + f(D, A, B) + X14)<<11 16 B = (B + f(C, D, A) + X15)<<19 Round2: 1 A = (A + g(B, C, D) + Xo + K1)<<3 2 D = (D + g(A, B, C) + X4 + K1)<<5 3 C = (C + g(D, A, B) + X8 +K1)<<9 4 B = (B + g(C, D, A) + X12 + K1)<<13 5 A = (A + g(B, C, D) + X1 + K1)<<3 6 D = (D + g(A, B, C) + X5 + K1)<<5 7 C = (C + g(D, A, B) + X8 +K1)<<9 8 B = (B + g(C, D, A) + X13 + K1)<<13 9 A = (A + g(B, C, D) + X2 + K1)<<3 10 D = (D + g(A, B, C) + X6 + K1)<<5 11 C = (C + g(D, A, B) + X10 +K1)<<9 12 B = (B + g(C, D, A) + X14 + K1)<<13 13 A = (A + g(B, C, D) + X3 + K1)<<3 14 D = (D + g(A, B, C) + X7 + K1)<<5 15 C = (C + g(D, A, B) + X11 +K1)<<9 16 B = (B + g(C, D, A) + X15 + K1)<<13 Round3: 1 A = (A + h(B, C, D) +X0 + K2)<<3 2 D = (D + h(A, B, C) + X8 + K2)<<9 3 C = (C + h(D, A, B) + X4 + K2)<<11 4 B = (B + h(C, D, A) + X12 + K2)<<15 5 A = (A + h(B, C, D) +X2 + K2)<<3 6 D = (D + h(A, B, C) + X10 + K2)<<9 7 C = (C + h(D, A, B) + X6 + K2)<<11 8 B = (B + h(C, D, A) + X14 + K2)<<15 9 A = (A + h(B, C, D) +X1 + K2)<<3 10 D = (D + h(A, B, C) + X9 + K2)<<9 11 C = (C + h(D, A, B) + X5 + K2)<<11 12 B = (B + h(C, D, A) + X13 + K2)<<15 13 A = (A + h(B, C, D) +X3 + K2)<<3 14 D = (D + h(A, B, C) + X11 + K2)<<9 15 C = (C + h(D, A, B) + X7 + K2)<<11 16 B = (B + h(C, D, A) + X15 + K2)<<15 Chương IV Chữ Ký Chống Chối Bỏ IV.1. Giới thiệu Chữ ký chống chối bỏ được công bố bởi Chaum và van Antwerpen vào năm 1989. Nó có một số nét riêng mới lạ rất thú vị. Quan trọng nhất trong số đó là chữ ký không thể kiểm tra khi không có sự cộng tác của người ký, Bob. Sự bảo vệ này của Bob đề phòng khả năng chữ ký trong tài liệu của anh ta bị sao chép và phân bố bởi thiết bị điện tử mà không có sự đồng ý của anh ta. Ví dụ, Bob có một phần mềm và chữ ký kèm theo được tạo ra nhờ thuật toán của chữ ký số thông thường. Như vậy, sẽ không tránh khỏi trường hợp phần mềm đó bị sao chép mà Bob không biết. Người mua sẽ kiểm tra chữ ký kèm theo phần mềm nhờ thuật toán kiểm tra công khai Ver và công nhận đ._.