Giáo trình Mật mã học (Phần 1)

dùng chế độ CBC để tạo các khối bản mã n1 y,,y K theo khóa K. Cuối cùng ta xác định MAC lμ yn. Alice sẽ phát đi dãy các khối bản rõ n1 x,,x K cùng với MAC. Khi Bob thu đ−ợc x1. . .xn anh ta sẽ khôi phục lại n1 y,,y K bằng khóa K bí mật vμ xác minh xem liệu ny có giống với MAC mμ mình đã thu đ−ợc hay không? Nhận thấy Oscar không thể tạo ra một MAC hợp lệ do anh ta không biết khóa K mμ Alice vμ Bob đang dùng. Hơn nữa Oscar thu chặn đ−ợc dãy khối bản rõ n1 x,,x K vμ thay đổi ít nhiều nội dung thì thì chắc chắn lμ Oscar không thể thay đổi MAC để đ−ợc Bob chấp nhận. Thông th−ờng ta muốn kết hợp cả tính xác thực lẫn độ bảo mật. Điều đó có thể thực hiện nh− sau: Tr−ớc tiên Alice dùng khóa K1 để tạo MAC cho n1 x,,x K . Sau đó Alice xác định 1nx + lμ MAC rồi mã hoá dãy 1n1 x,,x +K bằng khóa thứ hai K2 để tạo ra bản Giáo trình Mật mã học 120 mã 1n1 y,,y +K . Khi Bob thu đ−ợc 1n1 y,,y +K , tr−ớc tiên Bob sẽ giải mã (bằng 2K ) vμ kiểm tra xem 1nx + có phải lμ MAC đối với dãy n1 x,,x K dùng K1 hay không. Ng−ợc lại, Alice có thể dùng K1 để mã hoá n1 x,,x K vμ tạo ra đ−ợc n1 y,,y K , sau đó dùng 2K để tạo MAC 1ny + đối với dãy n1 y,,y K . Bob sẽ dùng 2K để xác minh MAC vμ dùng K1 để giải mã n1 y,,y K . 3.9.4.2. Mã nguồn DES (Xem phụ lục 3) Bμi tập 1. Thám mã thu đ−ợc bản mã sau: PSZI QIERW RIZIV LEZMRK XS WEC CSY EVI WSVVC Biết rằng đây lμ bản mã của mật Xeda với khóa k ch−a biết. Hãy dùng ph−ơng pháp tìm khóa vét cạn để tìm đ−ợc bản rõ tiếng Anh t−ơng ứng. Ghi chú: Ph−ơng pháp tìm khóa vét cạn lμ ph−ơng pháp thử giải mã bằng mọi khóa có thể có. 2. D−ới đây lμ 4 bản mã thu đ−ợc từ mã thay thế. Một bản thu đ−ợc từ mã Vigenère, một từ mật mã Affine vμ một bản ch−a xác định. Nhiệm vụ ở đây lμ xác định bản rõ trong mỗi tr−ờng hợp. Hãy mô tả các b−ớc cần thực hiện để giải mã mỗi bản mã (bao gồm tất cả các phân tích thống kê vμ các tính toán cần thực hiện). Hai bản rõ đầu lấy từ cuốn "The Diary of Samuel Marchbanks" của Robertson Davies, Clack Iriwin,1947; bản rõ thứ Ch−ơng 3: Mật mã cổ điển 121 t− lấy từ "Lake Wobegon Days" của Garrison Keillor, Viking Penguin, 1985. a. Mã thay thế EMGLOSUDCGDNCUSWYSFHNSFCYKDPUMLWGYICO| XYSIPJCK QPKUGKMGOUCGINCGACKSNISACYKZSCKXEOCKSH YSXCG OIDPKZCNKSHICGIWYGKKGKGOLDSILKGOIUSIGLED SPWZU GFZCCNDGYYSFUSZCNXEOJNCGYEOWEUPXEZGACG NFGLKNS ACIGOIYCKXOUOUZCFZCCNDGYYSFEUEKUZCSOCFZ CCNC IACZEJNCSHFZEJZEGMXCYHCIUMGKUSY Chỉ dẫn: F sẽ giải mã thμnh w. b. Hệ mã Vigenère KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFĐETDGIL TXRGUD DKOTFMBPVGEGLTGCKQRACQCWDNAWCRXLZAKFTL EWRPTVC QKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJV DAHCTRL SVSKCGCZQọDZXGSFRLSWCWSJTBHAFSLASPRJAHKJ RJUMV Giáo trình Mật mã học 122 GKMITZHFPDLSPZLVLGWTFPLKKEBDPGCEBSHCTJR WXBAFS PEZQNRWXCVYCGAONWDDKACKAWBBIKFTLOVKCG GHJVLNHI FFSQESVYCLACNVRWBBIREPBBVFEXOSCDYGZWPFD TKFQLY CWHJVTNHIQ/BTKH/VNPIST c. Hệ mã Affine KQEREJEBCPPCJCRKIEACUZBKRVPKRBCIBQCARBJC VFCUP KRLOFKPACUZQEPBKRXPEIIEABDKPBCPFCDCCAFIE ABĐKP BCPFEQPKAZBKRHALBKAPCCIBURCCDKDCCJC/DFUI XPAFF ERBICZDFKABICBBENEFCUPLCVKABPCYDCCDPKBC OCPERK IVKSCPICBRKLJPKABL d. Hệ mã ch−a xác định đ−ợc BNVSNSIHQCEELSSKKYERIFJKXUMBGVKAMQLJTYA VFBKVT DVBPVVRJYYLAOKYMPQSCGDLFSRLLPROYGESEBUU ALRWXM MASAZLGLEĐFJBZAVVPXWI CGJXASCBYEHOSNMULKCEAHTQ Ch−ơng 3: Mật mã cổ điển 123 OKMFLEBKFXLRRFDTZXCIWBJSICBGAWDVYDHAVFJ XZIBKC GJIWEAHTTOEWTUHKRQVVRGZBXYIREMMASCSPBN LHJMBLR FFJELHWEYLWISTFVVYFJCMHYUYRUFSFMGESIGRL WALSVVM NUHSIMYYITCCQPZSICEHBCCMZFEGVJYOCDEMMPG HVAAUM ELCMOEHVLTIPSUYILVGFLMVWDVYDBTHFRAYISYS GKVSUU HYHGGCKTMBLRX 3. a. Có bao nhiêu ma trận khả nghịch cấp 2 ì 2 trên Z26. b. Giả sử p lμ số nguyên tố. Hãy chứng tỏ số các ma trận khả nghịch cấp 2 ì 2 trên Zp lμ (p2 – 1)(p2 – p). Chỉ dẫn Vì p lμ số nguyên tố nên pZ lμ một tr−ờng. Hãy sử dụng khẳng định sau: Một ma trận trên một tr−ờng lμ khả nghịch khi vμ chỉ khi các hμng của nó lμ các véc tơ độc lập tuyến tính (tức không tồn tại một tổ hợp tuyến tính các hμng khác 0 mμ tổng của chúng lμ một véc tơ toμn số 0). c. Với p lμ số nguyên tố vμ m lμ một số nguyên m ≥ 2. Hãy tìm công thức tính số các ma trận khả nghịch cấp mìm trên Zp. 4. Giả sử ta đã biết rằng bản rõ "conversation" sẽ tạo nên bản mã "HIARRTNUYTUS" (đ−ợc mã theo hệ mã Hill nh−ng ch−a xác định đ−ợc m). Hãy xác định ma trận mã hoá. Giáo trình Mật mã học 124 5. Hệ mã Affine - Hill lμ hệ mã Hill đ−ợc sửa đổi nh− sau: Giả sử m lμ một số nguyên d−ơng vμ ( )m26=C = ZP . Trong hệ mật nμy, khóa K gồm các cặp (L,b), trong đó L lμ một ma trận khả nghịch cấp mxm trên Z26 vμ ( )m26b Z∈ theo công thức y xL b= + . Bởi vậy, nếu ( )ijL l= vμ ( )1 mb b , ,b= K thì: ( ) ( ) ( ) 1,1 1,2 1,m 2,1 2,2 2,m 1 m 1 m 1 m m,1 m,2 m,m l l l l l l y , ,y x , ,x b , ,b . . . l l l ⎡ ⎤⎢ ⎥⎢ ⎥= +⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦ K KK K KK K Giả sử Oscar đã biết bản rõ 1μ "adisplayedequation" vμ bản mã t−ơng ứng lμ "DSRMSIOPLXLJBZULLM". Oscar cũng biết m = 3. Hãy tính khóa vμ chỉ ra tất cả các tính toán cần thiết. 6. Sau đây lμ cách thám mã hệ mã Hill sử dụng ph−ơng pháp tấn công chỉ với bản mã. Giả sử ta biết m = 2. Chia các bản mã thμnh các khối có độ dμi 2 kí tự (các bộ đôi). Mỗi bộ đôi nμy lμ bản mã của một bộ đôi của bản rõ nhờ dùng một ma trận mã hoá ch−a biết. Hãy nhặt ra các bộ đôi th−ờng gặp nhất trong bản mã vμ coi rằng đó lμ mã của một bộ đôi th−ờng gặp trong danh sách ở bảng 1.1 (ví dụ TH vμ ST). Với mỗi giả định, hãy thực hiện phép tấn công với bản rõ đã biết cho tới khi tìm đ−ợc ma trận giải mã đúng. Sau đây lμ một ví dụ về bản mã để bạn giải mã theo ph−ơng pháp đã nêu: LMQETXYEAGTXCTUIEWNCTXLZEWUAISPZYVAPEWL MGQWVA XFTGMSQCADAGTXLMDXNXSNPJQSYVAPRIQSMHNO CVAXFV. Ch−ơng 3: Mật mã cổ điển 125 7. Ta sẽ mô tả một tr−ờng hợp đặc biệt của mã hoán vị. Giả sử m, n lμ các số nguyên d−ơng. Hãy viết bản rõ theo thμnh từng hμng thμnh một hình chữ nhật m x n. Sau đó tạo ra bản mã bằng cách lấy các cột của hình chữ nhật nμy Ví dụ, nếu m = 4, n = 3 thì ta sẽ mã hoá bản rõ "cryptography" bằng cách xây dựng hình chữ nhật : cryp togr aphy Bản mã sẽ lμ: "CTAROPYGHPRY" a. Hãy mô tả cách Bob giải mã một bản mã (với m, n đã biết). b. Hãy giải mã bản mã sau: (nhận đ−ợc theo ph−ơng pháp đã nêu): MYAMRARUYIQTENCTORAHROYWĐSOYEOUARRGĐE RNOGW 8. Hãy chứng minh rằng phép giải mã DES có thể thực hiện bằng cách áp dụng thuật toán mã hoá DES cho bản rõ với bảng khóa đảo ng−ợc. 9. Cho DES(x,K) lμ phép mã hoá DES của bản rõ x với khóa K. Giả sử ( )y DES x,K= vμ ( ) ( )( )y ' DES c x ,c K= trong đó c(.) kí hiệu lμ phần bù theo các bit của biến. Hãy chứng minh rằng ( )y ' c y= (tức lμ nếu lấy phần bù của bản rõ vμ khóa thì bản mã kết quả cũng lμ phần bù của bản mã ban đầu). Chú ý rằng kết quả trên có thể chứng minh đ−ợc chỉ bằng cách sử dụng mô tả "mức cao" của DES - cấu trúc thực tế của các hộp S vμ các thμnh phần khác của hệ thống không ảnh h−ởng tới kết quả nμy. Giáo trình Mật mã học 126 10. Mã kép lμ một cách để lμm mạnh thêm cho DES: với hai khóa 1K vμ 2K cho tr−ớc, ta xác định y = eK2(eK1(x)) (dĩ nhiên đây chính lμ tích của DES với chính nó). Nếu hμm mã hoá K2e giống nh− hμm giải mã K1d thì 1K vμ 2K đ−ợc gọi lμ các khóa đối ngẫu (đây lμ tr−ờng hợp không mong muốn đối với phép mã kép vì bản mã kết quả lại trùng với bản rõ). Một khóa đ−ợc gọi lμ tự đối ngẫu nếu nó đối ngẫu với chính nó. a. Hãy chứng minh rằng nếu 0C gồm toμn các số 0 hoặc gồm toμn các số 1 vμ 0D cũng vậy thì K lμ tự đối ngẫu. b. Hãy tự chứng minh rằng các khóa sau ( cho ở dạng hexa) lμ tự đối ngẫu; 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 F E E F E F E F E F E F E F E F 1 F 1 F 1 F 1 F 0 F 0 F 0 F 0 F E 0 E 0 E 0 E 0 F 1 F 1 F 1 F 1 c. Hãy chứng tỏ rằng nếu 0C 0101 01= K hoặc 1010 10K (ở dạng nhị phân) thì XOR các xâu bit Ci vμ C17-i lμ 111 11K , với 1 ≤ i ≤ 16 (khẳng định t−ơng tự cũng đúng đối với Di). d. Hãy chứng tỏ các cặp khóa sau lμ đối ngẫu: E0 01E0 01F1 0 1 F1 01 FE1FFE1FF0EFE0E E01FE01FFF1 0 FF1 0 01E001E001 F1 01 F1 1FFE1FFE0EFE0EFE 1FE01FE00EF1 0EF1 mật mã khóa công khai 4.1. gIớI THIệU Về MậT Mã KHóa CÔNG KHAI Trong mô hình mật mã cổ điển tr−ớc đây mμ hiện nay đang đ−ợc nghiên cứu Alice (ng−ời gửi) vμ Bob (ng−ời nhận) chọn một cách bí mật khóa K. Sau đó dùng K để tạo luật mã hóa ek vμ luật giải mã dk. Trong hệ mật nμy dk hoặc giống ek hoặc dễ dμng nhận đ−ợc từ nó (ví dụ trong hệ DES quá trình giải mã hoμn toμn t−ơng tự nh− quá trình mã nh−ng thủ tục khóa ng−ợc lại). Các hệ mật thuộc loại nμy đ−ợc gọi lμ hệ khóa bí mật, nếu để lộ ek thì lμm cho hệ thống mất an toμn. Nh−ợc điểm của hệ mật nμy lμ nó yêu cầu phải có thông tin tr−ớc về khóa K giữa Alice vμ Bob qua một kênh an toμn tr−ớc khi gửi một bản mã bất kỳ. Trên thực tế điều nμy rất khó đảm bảo. Chẳng hạn khi Alice vμ Bob ở cách xa nhau vμ họ chỉ có thể liên lạc với nhau bằng th− tín điện tử (Email). Trong tình huống đó Alice vμ Bob không thể tạo một kênh bảo mật với giá phải chăng. ý t−ởng xây dựng một hệ mật khóa công khai (hay dùng chung) lμ tìm một hệ mật không có khả năng tính toán để xác định kd khi biết ek. Nếu thực hiện đ−ợc nh− vậy thì quy tắc mã ek có thể đ−ợc công khai bằng cách công bố nó trong một danh bạ Giáo trình Mật mã học 128 (bởi vậy nên có thuật ngữ hệ mật khóa công khai). Ưu điểm của hệ mật khóa công khai lμ ở chỗ Alice (hoặc bất kỳ ai) có thể gửi một bản tin đã mã cho Bob (mμ không cần thông tin tr−ớc về khóa mật) bằng cách dùng mật mã công khai ek. Ng−ời nhận A sẽ lμ ng−ời duy nhất có thể giải đ−ợc bản mã nμy bằng sử dụng luật giải bí mật dk của mình. Có thể hình dung hệ mật nμy t−ơng tự nh− sau. Alice đặt một vật vμo một hộp kim loại vμ rồi khóa nó lại bằng một khóa số do Bob để lại. Chỉ có Bob lμ ng−ời duy nhất có thể mở đ−ợc hộp vì chỉ có anh ta mới biết tổ hợp mã của khóa số của mình. ý t−ởng về một hệ mật khóa công khai đ−ợc Diffie vμ Hellman đ−a ra vμo năm 1976. Còn việc hiện thực hoá nó thì do Rivesrt, Shamir vμ Adleman đ−a ra lần đầu tiên vμo năm 1977, họ đã tạo nên hệ mật nổi tiếng RSA (sẽ đ−ợc nghiên cứu trong ch−ơng nμy). Kể từ đó đã công bố một số hệ, độ mật của chúng dựa trên các bμi tính toán khác nhau. Trong đó, quan trọng nhất lμ các hệ mật khóa công khai sau: - Hệ mật RSA: Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số nguyên lớn. Hệ nμy sẽ đ−ợc mô tả trong phần 4.2. - Hệ mật xếp ba lô Merkle - Hellman: Hệ nμy vμ các hệ liên quan dựa trên tính khó giải của bμi toán tổng các tập con (bμi toán nμy lμ bμi toán NP đầy đủ - lμ một lớp khá lớn các bμi toán không có giải thuật đ−ợc biết trong thời gian đa thức). Tuy nhiên tất cả các hệ mật xếp ba lô khác nhau đều đã bị chứng tỏ lμ không mật (ngoại trừ hệ mật Chor-Rivest). Ch−ơng 4: Mật mã khóa công khai 129 - Hệ mật McEliece: Hệ nμy dựa trên lý thuyết mã đại số vμ vẫn còn đ−ợc coi lμ an toμn. Hệ mật McEliece dựa trên bμi toán giải mã cho các mã tuyến tính (cũng lμ một bμi toán NP đầy đủ). Hệ mật McEliece đ−ợc trình bμy ở phần 4.6. - Hệ mật ElGamal: Hệ mật ElGamal dựa trên tính khó giải của bμi toán logarithm rời rạc trên các tr−ờng hữu hạn. - Hệ mật Chor-Rivest: Hệ mật Chor-Rivest cũng đ−ợc xem nh− một hệ mật xếp ba lô. Tuy nhiên nó vẫn đ−ợc coi lμ an toμn. - Hệ mật trên các đ−ờng cong Elliptic: Các hệ mật nμy lμ biến t−ớng của các hệ mật khác (chẳng hạn nh− hệ mật ElGamal), chúng lμm việc trên các đ−ờng cong Elliptic chứ không phải lμ trên các tr−ờng hữu hạn. Hệ mật nμy đảm bảo độ mật với số khóa nhỏ hơn các hệ mật khóa công khai khác. Một chú ý quan trọng lμ một hệ mật khóa công khai không bao giờ có thể đảm bảo đ−ợc độ mật tuyệt đối (an toμn vô điều kiện). Sở dĩ nh− vậy vì đối ph−ơng khi nghiên cứu một bản mã, y có thể mã lần l−ợt các bản tin rõ bằng luật mã hoá công khai ke cho tới khi anh ta tìm đ−ợc bản rõ duy nhất x đảm bảo ( )xey k= . Bản rõ nμy chính lμ kết quả giải mã của y. Bởi vậy, ta chỉ nghiên cứu độ mật về mặt tính toán của các hệ mật nμy. Một khái niệm có ích khi nghiên cứu hệ mật khóa công khai lμ khái niệm về hμm cửa sập một chiều. Ta sẽ định nghĩa khái niệm nμy một cách không hình thức. Giáo trình Mật mã học 130 Hμm mã khóa công khai ke của Bob phải lμ một hμm dễ tính toán. Song việc tìm hμm ng−ợc (hμm giải mã) rất khó khăn (đối với bất kỳ ai không phải lμ Bob). Đặc tính dễ tính toán hμm ng−ợc th−ờng đ−ợc gọi lμ đặc tính một chiều. Bởi vậy điều kiện cần thiết lμ ke phải lμ hμm một chiều. Các hμm một chiều đóng vai trò quan trọng trong mật mã học, chúng rất quan trọng trong các hệ mật khóa công khai vμ trong nhiều lĩnh vực khác. Đáng tiếc lμ mặc dù có rất nhiều hμm đ−ợc coi lμ hμm một chiều nh−ng cho đến nay vẫn không tồn tại một hμm nμo có thể chứng minh đ−ợc lμ hμm một chiều. Sau đây lμ một ví dụ về một hμm đ−ợc coi lμ hμm một chiều. Giả sử n lμ tích của hai số nguyên tố lớn p vμ q, giả sử b lμ một số nguyên d−ơng. Khi đó ta xác định ánh xạ nn ZZ:f → lμ ( ) nmodxxf b= (với b vμ n đã đ−ợc chọn thích hợp thì đây chính lμ hμm mã RSA, sau nμy ta sẽ nói nhiều hơn về nó). Để xây dựng một hệ mật khóa công khai thì việc tìm đ−ợc một hμm một chiều vẫn ch−a đủ. Ta không muốn ke lμ hμm một chiều đối với Bob vì anh ta phải có khả năng giải mã các bản tin nhận đ−ợc một cách hiệu quả. Điều cần thiết lμ Bob phải có một cửa sập chứa thông tin bí mật cho phép dễ dμng tìm hμm của ke . Nh− vậy Bob có thể giải mã một cách hữu hiệu vì anh ta có một hiểu biết tuyệt mật nμo đó về K. Bởi vậy một hμm đ−ợc gọi lμ cửa sập một chiều nếu nó lμ một hμm một chiều vμ nó trở nên dễ tính ng−ợc nếu biết một cửa sập nhất định. 4.2. hệ mật rsa 4.2.1. Thuật toán 1: Tạo khóa Tóm l−ợc: Mỗi đầu cần tạo một khóa công khai vμ một khóa riêng t−ơng ứng theo các b−ớc sau: Ch−ơng 4: Mật mã khóa công khai 131 (1) Tạo 2 số nguyên tố lớn ngẫu nhiên vμ khác nhau p vμ q, p vμ q có độ lớn xấp xỉ nhau. (2) Tính q.pn = vμ ( ) ( )( )1q1pn −−=Φ . (3) Chọn một số nguyên ngẫu nhiên e, Φ<< e1 , sao cho ( ) 1,e =Φ . (4) Sử dụng thuật toán Euclide mở rộng để tính một số nguyên d duy nhất, Φ<< d1 thỏa mãn ( )Φ≡ mod1ed . (5) Khóa công khai lμ cặp số ( )e,n . Khóa riêng bí mật lμ d. 4.2.2. Định nghĩa Các số nguyên d vμ e trong thuật toán tạo khóa RSA đ−ợc gọi lμ số mũ mã hoá vμ số mũ giải mã. Số n đ−ợc gọi lμ modulus. 4.2.3. Thuật toán 2: Mã hóa công khai RSA Tóm l−ợc: B mã hóa một thông báo m để gửi cho A bản mã cần giải. 4.2.3.1. Mã hóa B phải thực hiện: (1) Thu nhận khóa công khai ( )e,n của A. (2) Biểu diễn bản tin d−ới dạng một số nguyên m trong khoảng [ ]1n,0 − (3) Tính nmodmc e= . (4) Gửi bản mã c cho A. 4.2.3.3. Giải mã Khôi phục bản rõ m từ c. A phải thực hiện phép tính sau bằng cách dùng khóa riêng nmodcm d= Giáo trình Mật mã học 132 Chứng minh hoạt động giải mã: Vì ( )Φ≡ mod1ed nên luôn tồn tại một số nguyên k sao cho Φ+= k1ed . Bây giờ nếu ( ) 1p,m = theo định lý Ferma ta có: ( )pmod1m 1p ≡− . Lũy thừa cả hai vế của đồng d− thức trên với số mũ ( )1qk − vμ rồi nhân cả hai vế với m ta có: ( )( ) ( )pmodmm 1p1qk1 ≡−−+ Mặt khác nếu ƯCLN(m, p) = p thì đồng d− thức cuối cùng ở trên vẫn đúng vì mỗi vế đều đồng d− với 0 mod p. Bởi vậy, trong mọi tr−ờng hợp ta đều có: ( )pmodmmed ≡ Bằng lập luận t−ơng tự ta lại có: ( )qmodmmed ≡ Cuối cùng vì p vμ q lμ các số nguyên tố khác nhau nên ( )nmodmmed ≡ vμ bởi vậy ( ) ( )nmodmmc ded ≡≡ . 4.2.4. Ví dụ 4.2.4.1. Tạo khóa A chọn các số nguyên tố 2551q,2357p == vμ tính 6012707q.pn == vμ ( )( ) 60078001q1p =−−=Φ . A chọn e = 3674911 vμ dùng thuật toán Euclide mở rộng để tìm đ−ợc d = 422191 thỏa mãn ( )Φ≡ mod1ed . Khóa công khai của A lμ cặp số (n = 6012707, e = 3674911), khóa bí mật của A lμ d = 422191. 4.2.4.2. Mã hóa Để mã hóa thông báo m = 5234673, B sử dụng thuật toán lấy lũy thừa theo modulo để tính. 36505026012707mod5234673nmodmc 3674911e === rồi gửi c cho A. Ch−ơng 4: Mật mã khóa công khai 133 4.2.4.3. Giải mã Để giải mã bản mã c, A tính: 52346736012707mod3650502nmodc 422191d == 4.2.4.4. Chú ý (Số mũ vạn năng) Số ( )1q,1pBCNN −−=λ đôi khi đ−ợc gọi lμ số mũ vạn năng của n, λ có thể đ−ợc dùng thay cho ( )( )1q1p −−=Φ khi tạo khóa RSA. Cần chú ý rằng λ lμ −ớc thực sự của Φ . Sử dụng λ có thể thu đ−ợc số mũ giải mã d nhỏ hơn (lμm cho giải mã nhanh hơn). Tuy nhiên, nếu p vμ q đ−ợc chọn ngẫu nhiên thì ƯCLN(p - 1, q - 1) sẽ khá nhỏ vμ bởi vậy Φ vμ λ sẽ lμ các số có kích th−ớc xấp xỉ. 4.3. hệ mật rabin 4.3.1. Thuật toán 1: Tạo khóa Tóm l−ợc: Mỗi đầu tạo một khóa công khai vμ một khóa bí mật t−ơng ứng theo các b−ớc sau: (1) Tạo 2 số nguyên tố lớn, ngẫu nhiên vμ phân biệt p vμ q có kích th−ớc xấp xỉ nhau. (2) Tính n = p.q. (3) Khóa công khai lμ n, khóa bí mật lμ các cặp số (p, q). 4.3.2. Thuật toán 2: Mã hóa công khai Rabin 4.3.2.1. Mã hóa B phải thực hiện các b−ớc sau: (1) Nhận khóa công khai của A: n. (2) Biểu thị bản tin d−ới dạng một số nguyên m nằm trong dải [ ]1n,0 − . Giáo trình Mật mã học 134 (3) Tính c = m2 mod n. (4) Gửi bản mã c cho A. 4.3.2.2. Giải mã: Để khôi phục bản rõ m từ c, A phải thực hiện các b−ớc sau: Tìm 4 căn bậc hai của nmodc lμ m1, m2, m3 hoặc m4. (1) Thông báo cho ng−ời gửi lμ một trong 4 giá trị m1, m2, m3 hoặc m4. Bằng một cách nμo đó A sẽ quyết định m lμ giá trị nμo. 4.3.3. Chú ý Tìm các căn bậc 2 của q.pn,nmodc = khi ( )4mod3qp ≡≡ . Trong tr−ờng hợp nμy, việc tìm 4 căn bậc 2 của nmodc đ−ợc thực hiện khá đơn giản nh− sau: (1) Sử dụng thuật toán Euclide mở rộng để tìm các số nguyên a vμ b thoả mãn 1bqap =+ . Chú ý rằng a vμ b có thể đ−ợc tính trong giai đoạn tạo khóa. (2) Tính ( ) pmodcr 4/1p+= . (3) Tính ( ) qmodcs 4/1q+= . (4) Tính ( ) nmodbqrapsx += . (5) Tính ( ) nmodbqrapsy −= . (6) Bốn giá trị căn bậc 2 của nmodc lμ x, nmodx− , y vμ nmody− . 4.3.4. Ví dụ 4.3.4.1. Tạo khóa A chọn các số nguyên tố p = 277 vμ q = 331. A tính n = p.q = 91687. Khóa công khai của A lμ 91687. Khóa bí mật của A lμ cặp số (p = 277, q = 331). Ch−ơng 4: Mật mã khóa công khai 135 4.3.4.2. Mã hóa Giả sử rằng 6 bit cuối cùng của bản tin gốc đ−ợc lặp lại tr−ớc khi thực hiện mã hóa. Việc thêm vμo độ thừa nμy nhằm giúp cho bên giải mã nhận biết đ−ợc bản mã đúng. Để mã hoá bản tin 10 bit 1001111001m = , B sẽ lặp lại 6 bit cuối cùng của m để có đ−ợc bản tin 16 bit sau: m = 1001111001111001, biểu diễn thập phân t−ơng ứng lμ m = 40596. Sau đó B tính 6211191687mod40596nmodmc 22 === rồi gửi c cho A. 4.3.4.3. Giải mã Để giải mã bản mã c, A tính bốn giá trị căn bậc 2 của nmodc : 51118m,40596m,22033m,69654m 4321 ==== Biểu diễn nhị phân t−ơng ứng của các số trên lμ: 1011101100011110m,1110011001111001m 100011010110000m,00101101000100000m 43 21 == == Vì chỉ có m3 mới có độ thừa cần thiết nên A sẽ giải mã c bằng m3 vμ khôi phục lại bản tin gốc lμ .1001111001m = 4.3.4.4. Đánh giá hiệu quả Thuật toán mã hóa Rabin lμ một thuật toán cực nhanh vì nó chỉ cần thực hiện một phép bình ph−ơng modulo đơn giản. Trong khi đó, chẳng hạn với thuật toán RSA có e = 3 phải cần tới một phép nhân modulo vμ một phép bình ph−ơng modulo. Thuật toán giải mã Rabin có chậm hơn thuật toán mã hoá, tuy nhiên về mặt tốc độ nó cũng t−ơng đ−ơng với thuật toán giải mã RSA. Giáo trình Mật mã học 136 4.4. hệ mật elgamal 4.4.1. Thuật toán tạo khóa Tóm l−ợc: Mỗi đầu liên lạc tạo một khóa công khai vμ một khóa bí mật t−ơng ứng: (1) Tạo 1 số nguyên tố p lớn vμ một phần tử sinh α của nhóm nhân *pZ của các số nguyên pmod . (2) Chọn một số nguyên ngẫu nhiên a, 2pa1 −≤≤ vμ tính pmodaα . (3) Khóa công khai lμ bộ 3 số ( )a,,p αα , khóa bí mật lμ a. 4.4.2. Thuật toán mã hóa công khai ElGamal Tóm l−ợc: B mã hóa một thông tin báo m để gửi cho A bản mã cần gửi. 4.4.2.1. Mã hóa B phải thực hiện các b−ớc sau: (1) Nhận khóa công khai ( )a,,p αα của A. (2) Biểu thị bản tin d−ới dạng một số nguyên m trong dải { }1p,,1,0 −K . (3) Chọn số nguyên ngẫu nhiên k, 2pk1 −≤≤ . (4) Tính pmodkα=γ vμ ( ) pmodm kaα=δ . (5) Gửi bản mã ( )δα= ,c cho A. 4.4.2.2. Giải mã Để khôi phục bản rõ m từ c, A phải thực hiện các b−ớc sau: (1) Sử dụng khóa riêng a để tính pmoda1p −−γ (Chú ý akaa1p −−−− γ=γ=γ ) Ch−ơng 4: Mật mã khóa công khai 137 (2) Khôi phục bản rõ bằng cách tính ( ) pmoda δγ− . Chứng minh hoạt động giải mã: Thuật toán trên cho phép A thu đ−ợc bản rõ vì: pmodmm. kakaa ≡αα≡δγ −− . 4.4.3. Ví dụ 4.4.3.1. Tạo khóa A chọn p = 2357 vμ một phần tử sinh 2=α của *2357Z . A chọn khóa bí mật a = 1751 vμ tính 11852357mod2pmod 1751a ==α . Khoá công khai của A lμ ( )1185,2,2357p a =α=α= . 4.4.3.2. Mã hóa Để mã hóa bản tin m = 2035, B sẽ chọn một số nguyên ngẫu nhiên k = 1520 vμ tính: 14302357mod21520 ==γ vμ 6972357mod1185.2035 1520 ==δ Sau đó B gửi ( )697,1430c = cho A. 4.4.3.3. Giải mã Để giải mã A phải tính: 8722357mod1430605a1p ==γ −− Sau đó khôi phục bản rõ m bằng cách tính: .20352357mod697.872m == Giáo trình Mật mã học 138 4.5. hệ mật merkle - hellman 4.5.1. Định nghĩa dãy siêu tăng Định nghĩa: Dãy các số nguyên d−ơng ( )n21 a,,a,a K đ−ợc gọi lμ dãy siêu tăng nếu ∑− = > 1i 1j ji aa với ni2,i ≤≤∀ . 4.5.2. Bμi toán xếp balô Cho một đống các gói có các trọng l−ợng khác nhau, liệu có thể xếp một số gói nμy vμo ba lô để ba lô có một trọng l−ợng cho tr−ớc hay không. Về mặt hình thức ta có thể phát biểu bμi toán trên nh− sau: Cho tập các giá trị n21 M,,M,M K vμ một tổng S. Hãy tính các giá trị bi để: nn2211 MbMbMbS +++= K với { }1,0bi ∈ bi = 1: Có nghĩa lμ gói Mi đ−ợc xếp vμo ba lô. bi = 0: Có nghĩa lμ gói Mi không đ−ợc xếp vμo ba lô. 4.5.3. Giải bμi toán xếp ba lô trong tr−ờng hợp dãy siêu tăng Trong tr−ờng hợp { }n21 M,,M,MM K= lμ một dãy siêu tăng thì việc tìm ( )n21 b,,b,bb K= t−ơng đ−ơng nh− bμi toán tìm biểu diễn nhị phân của một số S. Biểu diễn nμy sẽ tìm đ−ợc sau tối đa lμ n b−ớc. Thuật toán giải: Vμo: dãy siêu tăng { }n21 M,,M,MM K= vμ một số nguyên S lμ tổng của một tập con trong M. Ch−ơng 4: Mật mã khóa công khai 139 Ra : ( )n21 b,,b,b K trong đó { }1,0bi ∈ sao cho: SMb n 1i ii =∑ = (1) ni ← (2) Chừng nμo 1i ≥ hãy thực hiện a. Nếu iMS ≥ thì : 1xi ← vμ iMSS −← ng−ợc lại: 0xi ← b. 1ii −← (3) Return (b) Nếu M không phải lμ dãy siêu tăng thì lời giải của bμi toán lμ một trong 2n ph−ơng án có thể. Đây lμ một bμi toán khó giải nếu n lớn. 4.5.4. Thuật toán tạo khóa Tóm l−ợc: Mỗi đầu liên lạc tạo cho mình một khóa công khai vμ một khóa bí mật t−ơng ứng. Chọn một số nguyên xác định n đ−ợc xem lμ một tham số chung của hệ thống. Mỗi đầu liên lạc phải thực hiện các b−ớc sau: (1) Chọn một dãy siêu tăng ( )n21 M,,M,M K vμ một modulo M sao cho n21 M,,M,MM K> . (2) Chọn một số nguyên ngẫu nhiên W, 1MW1 −≤≤ sao cho ( ) 1M,W = . (3) Chọn một phép hoán vị ngẫu nhiên π của các số nguyên { }n,,2,1 K . (4) Tính ( ) MmodWMa ii π= với n,,2,1i K= . (5) Khóa công khai lμ tập các số ( )n21 a,,a,a K Khóa bí mật lμ ( )( )n21 M,,M,MW,M, Kπ . 4.5.5. Thuật toán mã công khai Merkle-Hellman Tóm l−ợc: B mã hóa bản tin m để gửi cho A bản mã cần giải mã. Giáo trình Mật mã học 140 4.5.5.1. Mã hóa B phải thực hiện các b−ớc sau: (1) Nhận khóa công khai của A: ( )n21 a,,a,a K (2) Biểu thị bản tin m nh− một chuỗi nhị phân có độ dμi n n21 m,,m,mm K= . (3) Tính số nguyên nn2211 amamamc +++= K (4) Gửi bản mã c cho A. 4.5.5.2. Giải mã Để khôi phục bản rõ m từ c, A phải thực hiện các b−ớc sau: (1) Tính MmodcWd 1−= (2) Sử dụng thuật giải xếp ba lô trong tr−ờng hợp dãy siêu tăng để tìm các số nguyên { }1,0r,r,,r,r in21 ∈K sao cho: nn2211 MrMrMrd +++= K (3) Các bit của bản rõ lμ ( ) n,,2,1i,rm ii K== π Chứng minh: Thuật toán trên cho phép A thu đ−ợc bản rõ vì: ( )∑∑ = π = ≡≡≡ n 1i ii n 1i ii 1-1- MmodMmamWcWd Vì ( )∑ = π=<≤ n 1i ii MmodMmd,Md0 , bởi vậy nghiệm của bμi toán xếp ba lô ở b−ớc (b) sẽ cho ta các bit của bản rõ sau khi sử dụng phép hoán vị π . 4.5.6. Ví dụ 4.5.6.1. Tạo khóa Cho n = 6. A chọn dãy siêu tăng sau: (12, 17, 33, 74, 157, 316), M = 737, W = 635 thỏa mãn (W, M) = 1. Ch−ơng 4: Mật mã khóa công khai 141 Phép hoán vị π của {1, 2, 3, 4, 5, 6} đ−ợc xác định nh− sau: ( ) ( ) ( ) ( ) ( ) ( ) 46,55,24,13,62,31 =π=π=π=π=π=π . Khóa công khai của A lμ tập (319, 196, 250, 477, 200, 559). Khóa bí mật của A lμ ( )( )316,157,74,33,17,12W,M,π . 4.5.6.2. Mã hóa Để mã hóa bản tin m = 101101, B tính: c = 319 + 250 + 477 + 559 = 1605 vμ gửi c cho A. 4.5.6.3. Giải mã Để giải mã A phải tính: ( )513224W 1 =−=− 136MmodcWd 1 == − vμ giải bμi toán xếp ba lô trong tr−ờng hợp dãy siêu tăng sau: 654321 r316r157r74r33r17r12136 +++++= vμ nhận đ−ợ