Nghiên cứu và thực hiện 1 số TEST để đánh giá độ an toàn của DES

LỜI MỞ ĐẦU Máy tính được phát minh vào năm 1942, lúc đó nó nằm ngoài tầm tay của các tổ chức, cá nhân vì nó yêu cầu cao về chi phí, kích cỡ, năng lượng Ngày nay, máy tính đã rất phổ biến và người ta không sử dụng một máy tính đơn lẻ nữa mà kết nối các máy tính với nhau nhằm tăng khả năng làm việc, trao đổi và cập nhật thông tin. Các máy tính được kết nối với nhau được gọi là mạng. Trên phạm vi toàn cầu người ta dung mạng Internet, ở mỗi quốc gia đều có những mạng riêng của minh (Intranet) với rất nhiều những mạng mang tính bộ phận( có thể là LAN( Local Area Network- Mạng cục bộ) hoặc WAN( Wide Area Network- Mạng diện rộng) hoặc MAN(Metropolitan Area Network- Mạng vùng Thành phố)). Nhiều dịch vụ của mạng như : thư điện tử, chuyển và nhận tiền, thương mại điện tử đã được sử dụng rộng rãi. Khi tham gia vào mạng, vấn đề quan trọng đặt ra là làm thế nào để bảo mật thông tin, dữ liệu. Thông tin trên mạng dù đang chuyển hay được lưu trữ đều cần được bảo vệ. Hoặc các thông tin đó cần được giữ bí mật hoặc chúng phải cho phép người ta kiể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. Trước yêu cầu đó một số giải pháp kỹ thuật đã được xây dựng nhằm đảm bảo tính an toàn dữ liệu tại nơi lưu trữ cũng như dữ liệu được truyền qua mạng. Các giải pháp đó là người ta sử dụng các hệ mật. Có các hệ mật cổ điển như : mật mã thay thế, mật mã dịch chuyển, mật mã Affine, mật mã Vigenere , và các hệ mật hiện đại như : mật mã khoá công khai RSA, chữ ký số, chuẩn mã dữ liệu DES Nhưng khi sử dụng các hệ mật để mã hoá dữ liệu cần phải quan tâm đến độ an toàn của các hệ mật mà mình đã sử dụng. Trong đề tài này tôi nghiên cứu về cách đánh giá độ an toàn của chuẩn mã dữ liệu DES . Để kiểm tra đánh giá độ an toàn của DES ta có hai cách. Đó là phương pháp tấn công DES và phương pháp đánh giá các tính chất của DES. Sự khác nhau giữa hai phương pháp này là một phương pháp thì tấn công trực tiếp vào DES, nếu phá vỡ DES thì ta có thể nói rằng DES không an toàn và ngược lại; phương pháp đánh giá tính chất thì kiểm tra các tính chất của DES, nếu thoả mãn điều kiện thì có thể nói là an toàn và ngược lại. Và tôi đi sâu nghiên cứu phương pháp đánh giá các tính chất của DES. TÀI LIỆU THAM KHẢO 1. Pascale Serf – Siemens AG, ZT IK 3, April 3 2000 2. Giáo trình An toàn thông tin _ Nguyễn Ngọc Cương 3. Kỹ thuật lập trình C cơ sở và nâng cao _ Gs. Phạm Văn Ât 4. Cryptography theory and practice MỤC LỤC Chương I Tổng quan về ngôn ngữ C Chương II Các hệ mật cổ điển II.1.1. Mật mã dịch chuyển II.1.2. Mật mã thay thế II.1.3. Mật mã Affine II.1.4. Mật mã Vigenere II.1.5. Mật mã hoán vị II.1.6. Mật mã dòng Chương III Chuẩn mã dữ liệu DES ( Data Ecryption Standard ) III.1 Mô tả DES III.1.1 Thuật toán mã hoá III.1.2 Hàm f( A, J ) II.1.3 Lược đồ tạo hệ thống khoá III.2 Giải mã DES III.2.1 Thuật toán giải mã III.2.2 Chứng minh thuật toán III.3 DES trong thực tế III.3.1 ứng dụng III.3.2 Các mẫu hoạt động của DES Chương IV Đánh giá độ an toàn IV.1 Phương pháp lượng sai tấn công DES 3 vòng IV.1.1 Một số khái niệm IV.1.2 Tấn công DES 3 vòng IV.1.3 Thuật toán thám mã DES 3 vòng IV.2 Phương pháp đánh giá tính chất của DES IV.2.1 Các định nghĩa IV.2.2 Tìm các tham số Kết luận Nhận xét của giáo viên hướng dẫn tài liệu tham khảo

doc39 trang | Chia sẻ: lvcdongnoi | Lượt xem: 2463 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Nghiên cứu và thực hiện 1 số TEST để đánh giá độ an toàn của DES, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Lêi më ®Çu M¸y tÝnh ®­îc ph¸t minh vµo n¨m 1942, lóc ®ã nã n»m ngoµi tÇm tay cña c¸c tæ chøc, c¸ nh©n v× nã yªu cÇu cao vÒ chi phÝ, kÝch cì, n¨ng l­îng… Ngµy nay, m¸y tÝnh ®· rÊt phæ biÕn vµ ng­êi ta kh«ng sö dông mét m¸y tÝnh ®¬n lÎ n÷a mµ kÕt nèi c¸c m¸y tÝnh víi nhau nh»m t¨ng kh¶ n¨ng lµm viÖc, trao ®æi vµ cËp nhËt th«ng tin. C¸c m¸y tÝnh ®­îc kÕt nèi víi nhau ®­îc gäi lµ m¹ng. Trªn ph¹m vi toµn cÇu ng­êi ta dung m¹ng Internet, ë mçi quèc gia ®Òu cã nh÷ng m¹ng riªng cña minh (Intranet) víi rÊt nhiÒu nh÷ng m¹ng mang tÝnh bé phËn( cã thÓ lµ LAN( Local Area Network- M¹ng côc bé) hoÆc WAN( Wide Area Network- M¹ng diÖn réng) hoÆc MAN(Metropolitan Area Network- M¹ng vïng Thµnh phè)). NhiÒu dÞch vô cña m¹ng nh­ : th­ ®iÖn tö, chuyÓn vµ nhËn tiÒn, th­¬ng m¹i ®iÖn tö… ®· ®­îc sö dông réng r·i. Khi tham gia vµo m¹ng, vÊn ®Ò quan träng ®Æt ra lµ lµm thÕ nµo ®Ó b¶o mËt th«ng tin, d÷ liÖu. Th«ng tin trªn m¹ng dï ®ang chuyÓn hay ®­îc l­u tr÷ ®Òu cÇn ®­îc b¶o vÖ. HoÆc c¸c th«ng tin ®ã cÇn ®­îc gi÷ bÝ mËt hoÆc chóng ph¶i cho phÐp ng­êi ta kiÓ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. Tr­íc yªu cÇu ®ã mét sè gi¶i ph¸p kü thuËt ®· ®­îc x©y dùng nh»m ®¶m b¶o tÝnh an toµn d÷ liÖu t¹i n¬i l­u tr÷ còng nh­ d÷ liÖu ®­îc truyÒn qua m¹ng. C¸c gi¶i ph¸p ®ã lµ ng­êi ta sö dông c¸c hÖ mËt. Cã c¸c hÖ mËt cæ ®iÓn nh­ : mËt m· thay thÕ, mËt m· dÞch chuyÓn, mËt m· Affine, mËt m· Vigenere…, vµ c¸c hÖ mËt hiÖn ®¹i nh­ : mËt m· kho¸ c«ng khai RSA, ch÷ ký sè, chuÈn m· d÷ liÖu DES… Nh­ng khi sö dông c¸c hÖ mËt ®Ó m· ho¸ d÷ liÖu cÇn ph¶i quan t©m ®Õn ®é an toµn cña c¸c hÖ mËt mµ m×nh ®· sö dông. Trong ®Ò tµi nµy t«i nghiªn cøu vÒ c¸ch ®¸nh gi¸ ®é an toµn cña chuÈn m· d÷ liÖu DES . §Ó kiÓm tra ®¸nh gi¸ ®é an toµn cña DES ta cã hai c¸ch. §ã lµ ph­¬ng ph¸p tÊn c«ng DES vµ ph­¬ng ph¸p ®¸nh gi¸ c¸c tÝnh chÊt cña DES. Sù kh¸c nhau gi÷a hai ph­¬ng ph¸p nµy lµ mét ph­¬ng ph¸p th× tÊn c«ng trùc tiÕp vµo DES, nÕu ph¸ vì DES th× ta cã thÓ nãi r»ng DES kh«ng an toµn vµ ng­îc l¹i; ph­¬ng ph¸p ®¸nh gi¸ tÝnh chÊt th× kiÓm tra c¸c tÝnh chÊt cña DES, nÕu tho¶ m·n ®iÒu kiÖn th× cã thÓ nãi lµ an toµn vµ ng­îc l¹i. Vµ t«i ®i s©u nghiªn cøu ph­¬ng ph¸p ®¸nh gi¸ c¸c tÝnh chÊt cña DES. 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 C¸c hÖ mËt cæ ®iÓn II.1 C¸c hÖ mËt Môc tiªu c¬ b¶n cña mËt m· lµ cho phÐp hai 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ñ nh­ Oscar 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¸y tÝnh ch¼ng h¹n. §Þnh nghÜa : HÖ mËt lµ mét bé n¨m thµnh phÇn (P,C,K,E,D) tho¶ m·n c¸c ®iÒu kiÖn sau: P lµ tËp h÷u h¹n c¸c b¶n râ cã thÓ C lµ tËp h÷u h¹n c¸c b¶n m· cã thÓ K lµ tËp h÷u h¹n c¸c kho¸ cã thÓ Víi mçi k Î K, tån t¹i mét quy t¾c m· ek Î E vµ mét quy t¾c gi¶i m· t­¬ng øng dk Î D. Mçi ek : P ® C vµ dk : C ® P tho¶ m·n : dk(ek(x)) = x víi mçi b¶n râ x Î P §iÒu kiÖn 4 lµ ®iÒu kiÖn chÝnh. Nã cã nghÜa lµ nÕu b¶n râ x ( plaintext ) ®­îc m· ho¸ sö ek vµ sau ®ã b¶n m· ( ciphertext ) kÕt qu¶ ®­îc gi¶i m· sö dông dk thu ®­îc kÕt qu¶ lµ b¶n râ nguyªn b¶n x. Gi¶ sö, Alice muèn göi cho Bob mét th«ng b¸o nµo ®Êy mµ kh«ng cho ng­êi kh¸c xem, th«ng b¸o ®ã cã thÓ lµ bµi tiÕng Anh, d÷ liÖu s« v.v…cã cÊu tróc tuú ý. Th«ng tin ®ã ®­îc gäi lµ b¶n râ. Alice vµ Bob ph¶i thèng nhÊt chän mét hÖ mËt vµ chän kho¸ ngÉu nhiªn kÎ K. Hä lµm ®iÒu nµy mét c¸ch an toµn, ch¼ng h¹n khi hä ë cïng mét chç vµ kh«ng bÞ Oscar quan s¸t hoÆc hä dïng kªnh an toµn khi ë xa nhau. Sau ®ã, gi¶ sö Alice muèn göi th«ng b¸o cho Bob trªn kªnh kh«ng an toµn. Th«ng b¸o ®ã lµ dßng: x = x1, x2,…, xn víi n ³ 1, xi Î P, 1£ i£ n Mçi xi ®­îc m· ho¸ sö dông quy t¾c ek ®­îc ®Þnh râ bëi kho¸ ®Þnh tr­íc K. Tõ ®ã, Alice tÝnh: yi = ek( xi), víi 1£ i£ n, vµ b¶n m· thu ®­îc lµ dßng: y = y1, y2,…, yn Alice göi nã trªn kªnh, Oscar dï thÊy b¶n m· nµy trªn kªnh kh«ng an toµn còng kh«ng thÓ x¸c ®Þnh ®­îc b¶n râ lµ g×. Khi Bob nhËn ®­îc y = y1, y2,…, yn, sÏ sö dông dk ®Ó gi¶ m·, thu ®­îc b¶n râ ban ®Çu x = x1,x2,…,xn. Râ rµng, víi x1 ¹ x2 th× ek(x1) ¹ ek(x2). NÕu y = ek(x1)= ek(x2) khi x1 = x2 th× Bob kh«ng biÕt ®­îc y ph¶i g¶i m· cho x1 hay x2. Chó ý r»ng P = C th× mçi hµm m· ho¸ ek lµ mét phÐp ho¸n vÞ. Cã nghÜa lµ, nÕu tËp c¸c b¶n râ vµ b¶n m· lµ t­¬ng tù th× mçi hµm m· hãa chØ s¾p xÕp ( hay ho¸n vÞ ) l¹i c¸c phÇn tö cña tËp nµy. Oscar Alice Bé m· ho¸ Bé gi¶i m· Bob Kªnh an toµn Nguån kho¸ X y y x k k Sau ®©y lµ c¸c hÖ mËt mµ Alice vµ Bob cã thÓ dïng. II.1.1 MËt m· dÞch chuyÓn §Þnh nghÜa : Cho P = C = K = Z26 Víi 0 £ k £ 25, x¸c ®Þnh : ek(x) = x + k mod 26 vµ dk(y) = y + k mod 26 víi x,y Î Z26 VÝ dô : Gi¶ sö kho¸ k = 11 vµ b¶n râ lµ : WEWILLMEETATMIDNIGHT Tr­íc hÕt, ph¶i sè ho¸ nã thu ®­îc nh­ sau 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 TiÕp theo, céng 11 vµo mçi gi¸ trÞ, rót gän mçi tæng theo modulo 26 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Cuèi cïng chuyÓn d·y sè thµnh d·y ch÷ H P H T W W X T P E L E X T O Y T R S E §Ó gi¶i m·, Bob thùc hiÖn theo tr×nh tù ng­îc l¹i. Tr­íc hÕt chuyÓn b¶n m· thµnh d·y c¸c sè, tiÕp theo trõ mçi gi¸ trÞ cho 11( rót gän cho modulo 26) vµ cuèi cïng chuyÓn d·y sè thµnh d·y ch÷. Mét hÖ mËt ®­îc sö dông trong thùc tÕ, nã ph¶i tho¶ m·n hai tÝnh chÊt sau: ek vµ dk khi t¸c ®éng vµo x hoÆc y lµ cã hiÖu qu¶ tÝnh to¸n Mét ®èi thñ khi cã b¶n m· y, sÏ kh«ng thÓ x¸c ®Þnh kho¸ k ®­îc sö dông hoÆc b¶n râ x II.1.2 MËt m· thay thÕ §Þnh nghÜa : Cho P = C = Z26 , K gåm tÊt c¶ c¸c ho¸n vÞ trªn tËp 26 phÇn tö tõ 0,1,…,25. Víi mçi ho¸n vÞ p Î K, x¸c ®Þnh : ep(x) = p(x) vµ dp(y) = p-1(y) víi p-1 lµ ho¸n vÞ ng­îc cña p VÝ dô : Abcdefghij Klmnopqrst Uvwxyz Xnyahpogzq Wbtsflrcvm Uekjdi p = ep(a) = p(a) = x ep(b) = p(b) = n Abcdefghij Klmnopqrst Uvwxyz Dlryvohezx Wptbgfjqnm Uskaci p-1 = dp(x) = p-1(x) = a vµ dp(n) = p-1(n) = b II.1.3 MËt m· Affine MËt m· dÞch chuyÓ lµ tr­êng hîp ®Æc biÖt cña mËt m· thay thÕ. MËt m· affine còng lµ mét tr­êng hîp cña mËt m· thay thÕ. Trong mËt m· affine, hµm m· cã d¹ng : E(x) = ax + b mod 26 víi a,b Î Z26 Hµm nµy ®­îc gäi lµ hµm affine Khi a = 1 ta ®­îc mËt m· dÞch chuyÓn. §Ó gi¶i m· ®­îc, hµm affine ph¶i song ¸nh, nghÜa lµ víi mäi y Î Z26 , ph­¬ng tr×nh ax + b = y (mod 26) ph¶i cã nghiÖm duy nhÊt. §ång d­ thøc nµy t­¬ng ®èi víi : ax = y – b (mod 26). Ph­¬ng tr×nh nµy cã nghiÖm duy nhÊt khi vµ chØ khi (a,26) = 1. §Ó t×m nghiÖm x, tr­íc tiªn ta t×m sè a-1 Î a26 tho¶ m·n : a.a-1 = 1 mod 26 . Khi ®ã d(y) = a-1(y - b) mod (26) §Þnh nghÜa : Cho P = C = Z26 vµ K = {(a,b) Î Z26 * Z26 : (a,26) = 1} víi k = (a,b) Î K, x¸c ®Þnh : ek(x) = ax + b mod 26 vµ dk(y) = a-1(y - b) mod 26 víi x,y Î Z26 II.1.4 MËt m· Vigenere MËt m· Vigenere lµ mËt m· ®a biÓu, tøc lµ mét ký tù m· cã thÓ ®­îc ¸nh x¹ thµnh nhiÒu ký tù kh¸c. §Þnh nghÜa : Cho m lµ sè nguyªn d­¬ng cè ®Þnh, P = C = K = (Z26)m víi kho¸ K = (k1,k2,….,km), chóng ta x¸c ®Þnh : ek(x1,x2,….,xm) = (x1+k1,x2+k2,….,xm+km) vµ dk(y1,y2,….,ym) = (y1- k1,y2- k2,….,ym- km) tÊt c¶ c¸c ho¹t ®éng ®­îc tiÕn hµnh trong Z26 VÝ dô : m = 6, kho¸ k = CIPHER = (2,8,15,7,4,17) Th«ng b¸o : THISCRIPTOSYSTEMISNOTSECURE Ta chuyÓn thµnh sè : 19 7 8 18 2 17 24 15 19 14 19 18 19 4 2 8 15 7 4 17 2 8 15 7 4 2 8 15 21 15 23 25 6 8 0 23 8 21 23 20 1 19 2 8 18 13 14 19 18 4 20 17 4 7 4 17 2 8 15 7 4 2 8 15 19 12 19 15 22 8 25 8 22 25 19 §­a vÒ ch÷ : V P X Z G I A X I V W P U B T T M J P W I Z I T W Z T II.1.5 MËt m· ho¸n vÞ ý t­ëng cña mËt m· ho¸n vÞ lµ gi÷ c¸c kÝ tù trªn b¶n râ kh«ng thay ®æi, nh­ng thay ®æi vÞ trÝ cña chóng b»ng c¸ch s¾p xÕp l¹i §Þnh nghÜa : Cho m lµ sè nguyªn d­¬ng cè ®Þnh, P = C = (Z26)m vµ K gåm tÊt c¶ c¸c ho¸n vÞ cña {1,2,….,m}. Víi mçi kho¸ p, x¸c ®Þnh ep(x1,….,xm) = (xp(1),….,xp(m)) vµ dp(y1,….,ym) = (yp (1),….,yp (m)) víi p-1 lµ ho¸n vÞ ng­îc cña p VÝ dô : Gi¶ sö m = 6 vµ kho¸ lµ ho¸n vÞ sau: 1 2 3 4 5 6 3 5 1 6 4 2 p = vµ ho¸n vÞ ng­îc cña p 1 2 3 4 5 6 3 6 1 5 2 4 p-1 = Th«ng b¸o : H O O F C H I S M I N H Tr­íc tiªn gom thµnh nhãm 6 phÇn tö : H O O F C H I S M I N H x1 = h, x2 = o, x3 = o, x4 = f, x5 = c, x6 = h khi ®ã nhãm thø nhÊt ®­îc m· thµnh x3 x5 x1 x6 x4 x2 = O C H H F O t­¬ng tù, nhãm thø hai lµ : M N I H I S VËy b¶n m· lµ : O C H H F O M N I H I S II.1.6 MËt m· dßng ý t­ëng c¬ b¶n lµ sinh dßng kho¸ z = z1 z2 … vµ m· dßng râ x = x1 x2 … theo c¸ch : y = y1 y2… = ez1(x1) ez2(x2)… MËt m· dßng ho¹t ®éng nh­ sau : gi¶ sö k lµ kho¸ vµ x1 x2 … lµ dßng râ, fi lµ hµm cña k vµ i lµ mét ®Æc tr­ng râ. zi = fi(k,x1,….,xi-1) (xi ®­îc chon tr­íc cña hai bªn) yi = ezi(xi) i = 2,3,… Do ®ã, ®Ó m· dßng râ x1 x2 … ta tÝnh liªn tiÕp : z1,y1,z2,y2,… ViÖc gi¶i m· ®­îc lµm t­¬ng tù z1,x1,z2,x2,… NÕu zi = k víi mäi i th× ta cã thÓ nghÜ mËt m· khèi nh­ tr­êng hîp ®Æc biÖt cña mËt m· dßng . Sau ®©y lµ mét sè tr­êng hîp ®Æc biÖt quan träng cña mËt m· dßng : MËt m· ®ång bé zi = fi(k) víi i = 1,2,… MËt m· tuÇn hoµn víi chu kú d : zi+d = zi , "i ³ 1 MËt m· dßng ®­îc chó ý nhiÒu h¬n c¶ lµ tr­êng hîp P = C = Z2. Khi ®ã phÐp m· ho¸ vµ gi¶i m· lµ céng theo modulo 2. e2(x) = x+z mod 2 d2(y) = y- z mod 2 MËt m· tù ®éng §Þnh nghÜa : P = C = K = Z26, z1 = k,zi = xi-1 (i³2) víi 0 £ z £ 25, x¸c ®Þnh : ez(x) = x+z mod 26 dz(y) = y- z mod 26 víi x,y Î Z26 VÝ dô : k = 8 , th«ng b¸o lµ : H A I R P H O N G F Tr­íc tiªn, chuyÓn th«ng b¸o râ thµnh d·y sè nguyªn 7 0 8 17 15 7 14 13 6 5 Dßng kho¸ nh­ sau : 8 7 0 8 17 15 7 14 13 6 5 Céng d·y kho¸ vµ d·y râ : yi = xi + zi mod 26, víi i= 1,2,… ta ®­îc 15 7 8 25 6 22 21 1 19 11 vµ chuyÓn thµnh ch÷ : P H I Z G W V B T L Víi b¶n m· nµy vµ k = 8, ta gi¶i m· nh­ sau : ChuyÓn b¶n m· thµnh d·y sè vµ trõ lÇn l­ît 15 7 8 25 6 22 21 1 19 11 8 7 0 8 17 15 7 14 13 6 7 0 8 17 15 7 14 13 6 5 chuyÓn d·y sè thµnh d·y ch÷ : H A I R P H O N G F Trªn ®©y lµ c¸c hÖ mËt cæ ®iÓn th­êng ®­îc dïng ®Ó m· ho¸ th«ng tin khi muèn göi ®i trªn c¸c kªnh kh«ng an toµn hay th«ng tin ®ang ®­îc l­u tr÷ cè ®Þnh. Ch­¬ng III ChuÈn m· d÷ liÖu DES ( Data Ecryption STandard ) ChuÈn m· d÷ liÖu ( Data Ecryption Standard ) ®­îc uû ban tiªu chuÈn quèc gia Hoa Kú ( the National Bureau ß Standard ) chÊp nhËn vµ ®­îc c«ng bè lÇn ®Çu tiªn trªn c«ng b¸o liªn bang ngµy 17 – 03 – 1975. Sau c¸c cuéc th¶o luËn c«ng khai, DES ®­îc chÊp nhËn nh­ cho c¸c øng dông b¶o mËt vµo ngµy 15–01- 1977. DES trë thµnh mét hÖ b¶o mËt ®­îc sö dông réng r·i nhÊt trªn thÕ giíi. III.1 M« t¶ DES DES m· ho¸ mét dßng bit râ x cã ®é dµi 64 víi k lµ dßng 56 bit, ®­a ra b¶n m· y còng lµ mét d·y bit cã ®é dµi 64. ½x½ = 64, ½y½ = 64,½k½ = 56 IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 III.1.1 ThuËt to¸n m· ho¸ Gåm ba giai ®o¹n : Cho b¶n râ x, ta tinh ®­îc x0 qua viÖc ho¸n vÞ c¸c bit cña x theo ho¸n vÞ ®Çu IP : x0 = IP( x ) = L0R0 L0 lµ 32 bit ®Çu tiªn cña x0 cßn R0 lµ 32 bit cßn l¹i, vµ IP lµ ho¸n vÞ ®Çu cè ®Þnh. b. LÆp 16 vßng : Chóng ta tÝnh LiRi víi 1 £ i £ 16, theo quy t¾c sau : Li = Ri-1 Ri = Li-1 ^ f( Ri-1, Ki ) DÊu (^) thÓ hiÖn phÐp to¸n “hoÆc lo¹i trõ” hai d·y bit, f lµ mét hµm mµ chóng ta sÏ ®Ò cËp ®Õn sau, ki lµ nh÷ng d·y dµi 48 bit ®­îc t¹o tõ kho¸ K bëi thuËt to¸n riªng. ¸p dông phÐp ho¸n vÞ ng­îc IP-1 cho L16R16 ta tÝnh ®­îc b¶n m· y : y = IP-1( L16 R16 ) , chó ý ®¶o ng­îc vÞ trÝ cña L16 vµ R16. Li-1 Ri-1 Li Ri f + ki IP-1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 44 13 53 21 60 29 36 4 43 12 52 20 59 28 35 3 42 11 51 19 58 27 34 2 41 10 50 18 57 26 33 1 40 9 49 17 56 25 III.1.2 Hµm f( A, J ) §Çu vµo cña hµm f lµ ®èi sè A, mét d·y 32 bit, vµ ®èi sè thø hai lµ J, lµ d·y 48 bit, kÕt qu¶ thu ®­îc lµ d·y cã ®é dµi 32 bit. C¸c b­íc ®­îc thùc hiÖn : E 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Më réng A tõ 32 bit thµnh 48 bit theo hµm më réng E. E( A ) gåm 32 bit cña A, ®­îc ho¸n vÞ theo c¸ch cô thÓ vµ víi 16 bit cña c¸c bit xuÊt hiÖn hai lÇn. TÝnh B = E( A ) ^ J vµ kÕt qu¶ B ®­îc t¸ch thµnh c¸c khèi 6 bit liªn tiÕp. B = B1 B2 B3 B4 B5 B6 B7 B8 B­íc tiÕp theo sö dông 8 hép S :S1,….,S8. Mçi hép Si lµ mét m¶ng hai chiÒu 4*16, mçi dßng chøa c¸c gi¸ trÞ tõ 0 ¸ 15. Ta cã ®Çu vµo Bj lµ mét d·y 6 bit Bj = b1 b2 b3 b4 b5 b6 b7 b8. hai bit b1 b6 x¸c ®Þnh biÓu diÔn nhÞ ph©n cña r lµ chØ sè dßng cña Sj ( 0 £ r £ 3), vµ 4 bit b2 b3 b4 b5 x¸c ®Þnh biÓu diÔn nhÞ ph©n cña C lµ chØ sè cét cña Sj ( 0 £ c £15 ). Sau ®ã, Si ( Bj ) lµ sè n»m trong to¹ ®é ( r, C ) gåm 4 bÝt. Ta cã kÝ hiÖu : Cj = Sj ( Bj ), víi 1 £ j £ 8 d. Dßng bit C = C1…C8 víi ®é dµi 32 bit ®­îc ®æi chç theo ho¸n vÞ P , kÕt qu¶ d·y P( C ) chÝnh lµ f( A, J ). F( A, J ) = P( C ) Hµm f ®­îc thÓ hiÖn trong h×nh d­íi ®©y : A F(A) J E + B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 P F( A, J ) 8 hép S vµ ho¸n vÞ P : S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 12 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 3 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 7 13 4 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 12 1 10 14 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 3 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Ho¸n vÞ P : III.1.3 L­îc ®å t¹o hÖ thèng kho¸ Cuèi cïng ta cÇn m« t¶ sù tÝnh to¸n l­îc ®å kho¸ tõ kho¸ K. Kho¸ lµ mét d·y 64 bit víi 56 bit ®Çu vµo vµ 8 bit lµ c¸c bit kiÓm tra (lµ c¸c bit ë vÞ trÝ thø 8, 16,24,32, 48, 56, 64). C¸c bit kiÓm tra nµy sÏ ®­îc bá qua trong qu¸ tr×nh t¹o kho¸. Cho 56 bit nµy ho¸n vÞ theo b¶ng PC-1 ta sÏ t×m ®­îc C0D0 víi C0 lµ 28 bit ®Çu tiªn cña PC-1, D0 lµ 28 bit cßn l¹i. PC-1( K ) = C0D0, víi i = 1¸16 ta tÝnh Ci = LSi( Ci- 1) Di = LSi( Di-1 ) LSi thÓ hiÖn phÐp dÞch tr¸i quay vßng mét hoÆc hai bit, phô thuéc vµ gi¸ trÞ cña i, dÞch mét bit nÕu i = 1,2,9,16 vµ dÞch hai bit víi c¸c gi¸ trÞ cßn l¹i cña i. Ki ®­îc tÝnh theo CiDi qua b¶ng ho¸n vÞ PC-2 Ki = PC-2( CiDi ) Ta cã c¸c b¶ng PC-1 vµ PC-2 : PC-1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 PC-2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Nh­ vËy ta ®· cã mét thuËt to¸n hoµn chØnh vÒ m· ho¸ d÷ liÖu theo tiªu chuÈn DES. III.2 Gi¶i m· DES T­¬ng tù nh­ m· ho¸, ®Ó gi¶i m· mét d·y kÝ tù ®· bÞ m· ho¸ ta còng lµm theo tr×nh tù c¸c b­íc nh­ trªn. Tuy nhiªn, hÖ thèng kho¸ lóc nµy ®· ®­îc t¹o theo chiÒu ng­îc l¹i. III.2.1 ThuËt to¸n gi¶i m· Cã b¶n m· y vµ kho¸ K y0 = IP(y) = R0’ L0’ = R16L16 víi i = 1,2,….,16 Thùc hiÖn : Li’ = R’i-1 vµ Ri = L’i-1 ^ f( R’i-1, k17-i ) x0 = ( R’16, L’16 ) x = IP-1( x0 ) III.2.2 Chøng minh thuËt to¸n Cã b¶n m· y: y0 = IP(y) = IP(IP-1(R16L16)) = R16L16 =L’0 R’0 VËy L’0 = R16, R’0 = L16, víi i = 1 L’1 = R’0 = L16 = R15 R’1 = L’0 ^ f(R’0,k16) = R16 ^ f(L16,k16) = L15 ^ f(R15,k16) = L15 Tãm l¹i : L’1 = R15, R’1 = L15 T­¬ng tù nh­ vËy cho ®Õn khi I = 16, ta sÏ cã L’16 = R’15 = L1 = R0 R’16 = L’15 ^ f(R’15,k1) = R’1 ^ f(L1,k1) = L0 ^ f(R0,k1) ^ f(R0,k1) = L0 L’16 = R0, R’16 = L0 x = IP-1(R’16L’16) = IP-1(R0L0) = IP-1(x0) Tõ ®ã ta thÊy, thuËt to¸n gi¶i m· chØ kh¸c víi thuËt to¸n m· ho¸ ë chç t¹o hÖ thèng kho¸. NÕu m· ho¸ t¹o tõ k1,….,k16 th× gi¶i m· t¹o hÖ thèng kho¸ tõ k16,….,k1 III.3 DES trong thùc tÕ III.3.1 øng dông MÆc dï viÖc m« t¶ DES kh¸ dµi th× DES ®­îc thùc hiÖn rÊt hiÖu qu¶ trong c¶ phÇn cøng lÉn phÇn mÒm. Nh÷ng thùc hiÖn phÇn cøng hiÖn thêi cã thÓ ®¹t ®­îc tèc ®é m· ho¸ cù nhanh. H·ng Digital Equipment Corporation th«ng b¸o t¹i CRYTO’92 r»ng hä võa chÕ t¹o ®­îc mét chip víi 50K transistors cã thÓ m· ho¸ víi tèc ®é 1Gb/s nhê sö dông ®ång hå tèc ®é lµ 250MHz. Trong n¨m 1991, cã 45 phÇn cøng vµ ch­¬ng tr×nh cµi s½n thi hµnh DES ®· ®­îc Uû ban tieuu chuÈn quèc gia MÜ ( the National Bureau of Standards ) tin cËy. Mét øng dông quan träng cña DES lµ øng dông cho v¨n b¶n giao dÞch ng©n hµng sö dông c¸c tiªu chuÈn ®­îc hiÖp héi c¸c ng©n hµng MÜ ph¸t triÓn, DES ®­îc sö dông ®Ó m· ho¸ c¸c sè nhËn d¹ng c¸ nh©n ( PINs ) vµ v¨n b¶n vÒ tµI kho¶n ®­îc m¸y thu ng©n thùc hiÖn ( ATMs ). III.3.2 C¸c mÉu ho¹t ®éng cña DES §Çu vµo cña DES chØ cã 8 byte, vËy mµ v¨n b¶n cÇn m· ho¸ l¹i cã thÓ rÊt dµi, cì vµi Kbyte ch¼ng h¹n. §Ó gi¶i quyÕt vÊn ®Ò nµy, ng­êi ta ®É ®Ò ra bèn mÉu ho¹t ®éng cho DES lµ : Electronic CodeBook mode ( ECB ), Cipher FeedBack mode ( CFB ), Cipher Block Chaining mode ( CBC ) vµ Output FeedBack mode ( OFB ). + ECB : §©y lµ viÖc sö dông b×nh th­êng mËt m· khèi. Tr­íc hÕt chia d·y ký tù trong th«ng b¸o thµnh c¸c khèi 8 ký tù liªn tiÕp x1,x2,…, mçi xi ®Òu ®­îc m· bëi cïng kho¸ k, cuèi cïng ®­îc mét d·y c¸c khèi m· 8 bit lµ y1,y2,… ViÖc gi¶i m· ®­îc tiÕn hµnh theo tr×nh tù ng­îc l¹i. + CBC : Ta còng chia th«ng b¸o thµnh nh÷ng khèi 8 byte nh­ trªn ®Ó ®­îc x1,x2,… Cho IV lµ vector khëi ®iÓm dµI 64 bit ( 8 byte ). B¾t ®Çu lµ viÖc g¸n y0 = IV, sau ®ã tÝnh yi = ek(yi-1 ^ xi), víi i = 1,2,… Qu¸ tr×nh gi¶i m· nh­ sau : y0 = IV xi = yi-1 ^ dk(yi), víi i = 1,2,… + OFB vµ CFB : ý t­ëng chÝnh lµ sinh ra mét dßng kho¸, sau ®ã XOR nã víi th«ng b¸o nh­ mËt m· dßng. - §èi víi OFB, cô thÓ nh­ sau : z0 = IV, zi = ek(zi-1), i = 1,2,… yi = xi ^ zi, i = 1,2,… ViÖc gi¶i m· nh­ ®èi víi mËt m· dßng. - §èi víi CFB, cã sù kh¸c nhau nhÊt ®Þnh y0 = IV, zi = ek(y0) yi = xi ^ zi, zi+1 = ek(yi), i= 1,2,… ViÖc gi¶i m· thùc hiÖn nh­ sau : y0 = IV, z1 = ek(y0) xi = yi ^ zi, zi+1 = ek(yi), i= 1,2,… ECB vµ OFB : viÖc thay ®æi mét khèi 64 bit râ xi khiÕn cho khèi m· yi t­¬ng øng còng thay ®æi theo, nh­ng c¸c khèi m· kh¸c kh«ng bÞ ¶nh h­ëng. Trong mét vµi hoµn c¶nh, ®©y lµ mét tÝnh chÊt tèt, ch¼ng h¹n OFB th­êng ®­îc dïng ®Ó m· th«ng tinh truyÒn qua vÖ tinh. CBC vµ CFB : khèi râ xi bÞ thay ®æi th× yi vµ tÊt c¶ c¸c khèi m· tiÕp theo sÏ bÞ ¶nh h­ëng. TÝnh chÊt nµy cã nghÜa lµ CBC, CFB cã Ých cho môc ®Ých x¸c thùc. Ch­¬ng IV §¸nh gi¸ ®é an toµn Khi ta m· ho¸ th«ng tin b»ng c¸c hÖ mËt kh«ng cã nghÜa lµ ta ®· yªn t©m th«ng tin ®ã kh«ng bÞ mÊt m¸t, sai lÖch so víi ban ®Çu khi l­u tr÷ hay truyÒn qua m¹ng. Mµ ta ph¶i cã biÖn ph¸p kiÓm tra xem hÖ mËt ®ã cã an toµn kh«ng. §èi víi m· chuÈn d÷ liÖu DES còng vËy, khi m· ho¸ c¸c th«ng tin ®ång thêi ta còng ph¶i kiÓm tra ®é an toµn cña nã. Cã hai c¸ch ®Ó kiÓm tra ®é an toµn cña DES, ®ã lµ : ph­¬ng ph¸p tÊn c«ng DES vµ ph­¬ng ph¸p ®¸nh gi¸ c¸c tÝnh chÊt cña DES. Tuy nhiªn trong ®Ò tµi nay tËp trung nghiªn cøu ph­¬ng ph¸p ®¸nh gi¸ c¸c tÝnh chÊt cña DES ®Ó kiÓm tra ®é an toµn. IV.1 Ph­¬ng ph¸p l­îng sai tÊn c«ng DES 3 vßng Cã nghÜa lµ ta tÊn c«ng vµo DES, nÕu ph¸ vì DES th× cã nghÜa lµ kh«ng an toµn. Ph­¬ng ph¸p l­îng sai tÊn c«ng DES lµ ph­¬ng ph¸p næi tiÕng do Biham vµ Shamir giíi thiÖu. ®©y lµ sù tÊn c«ng b¶n rç lùa chän. MÆc dï nã cßn ®ßi hái kh¸ nhiÒu cÆp b¶n râ lùa chän trong viÖc ph¸ vì ®ñ 16 vßng DES th«ng th­êng, ph­¬ng ph¸p nµy thµnh c«ng trong viÖc ph· vì DES nÕu sè vßng gi¶m xuèng. VÝ dô 8 vßng DES cã thÓ bÞ ph¸ vì trong vµi phót trªn mét PC nhá víi mét sè kh«ng qu¸ nhiÒu c¸c b¶n râ lùa chän. §Ó hiÓu ph­¬ng ph¸p l­îng sai, chóng ta nghiªn cøu tr­êng hîp ®¬n gi¶n nhÊt lµ tÊn c«ng DES 3 vßng. IV.1.1 Mét sè kh¸i niÖm L­îng sai bao gåm viÖc so s¸nh XOR hai b¶n râ víi XOR hai b¶n m· tu¬ng øng. Chóng ta xem xÐt hai b¶n râ L0R0 vµ L0*R0* víi mét gi¸ trÞ XOR ®Æc biÖt L0’ R0’ = L0R0 ^ L0*R0*. Ta cã c¸c kh¸i niÖm sau: §Þnh nghÜa 1 : Cho Si lµ mét hép S ( 1 ≤ j ≤ 8 ). XÐt cÆp cã thø thù ( Bj,Bj*) víi | Bj | = | Bj* | = 6. Ta nãi r»ng XOR ®Çu vµo cña Sj lµ Bj ^ Bj* vµ XOR ®Çu ra cña Sj lµ Sj (Bj ) ^ Sj (Bj*) Chó ý r»ng XOR ®Çu vµo lµ mét d·y bit cã ®é dµi lµ 6 cßn XOR ®Çu ra lµ d·y cã ®é dµi 4 bit. §Þnh nghÜa 2 : Víi mäi Bj’ € {Z2}6. ta ®Þnh nghÜa Δ(Bj’) = {(Bj, Bj*) : Bj ^ Bj* = Bj’ } Víi mçi cÆp trong Δ(Bj’), cã thÓ tÝnh XOR ®Çu ra cña Sj vµ lËp b¶ng kÕt qu¶ ph©n phèi. §Þnh nghÜa 3 : Víi 1 ≤ j ≤ 8, d·y c¸c Bj’ dµi 6 bit, Cj’ dµi 4 bit, ta ®Þnh nghÜa : INj(Bj’, Cj’ ) = {Bj € {Z2}6 : Sj (Bj ) ^ Sj(Bj ^ Bj’ ) = Cj’ } Vµ INj(Bj’, Cj’ ) = | INj(Bj’, Cj’ ) | Thùc ra, INj(Bj’, Cj’ ) ®Õm sè cÆp XOR ®Çu vµo lµ Bj’ vµ cã XOR ®Çu ra t­¬ng øng Cj’ cho mçi hép Sj. Tõ c¸c tËp INj(Bj’, Cj’ ) ta cã thÓ thu ®­îc c¸c cÆp cã XOR ®Çu vµo ®Æc biÖt g©y ra c¸c XOR ®Çu ra ®Æc biÖt. §Þnh nghÜa 4 : Gi¶ sö Ej , Ej* lµ c¸c d·y 6 bit, Cj’ lµ d·y 4 bit. Ta ®Þnh nghÜa : Testj(Ej, Ej*, Cj’) = { Bj ^ Ej : Bj € INj(Ej’, Cj’ ) } trong ®ã Ej’ = Ej ^ Ej* Hay nãi c¸ch kh¸c : Testj(Ej, Ej*, Cj’) = Ej ^INj(Ej’, Cj’ ) §Þnh lý : Gi¶ sö Ej , Ej* lµ c¸c ®Çu vµo cña Sj vµ XOR ®Çu ra t­¬ng øng cña Sj lµ Cj’, ký hiÖu Ej’ = Ej ^ Ej*. Khi ®ã, c¸c bit kho¸ cña Jj ph¶i xuÊt hiÖn trong tËp Testj(Ej, Ej*, Cj’) IV.1.2 TÊn c«ng DES 3 vßng ViÖc th¸m m· DES 3 vßng b»ng ph­¬ng ph¸p l­îng sai g¾n víi viÖc lùa chän c¸c b¶n râ cho DES. Chóng ta b¾t ®Çu víi mét cÆp b¶n râ vµ b¶n m· L0R0 , L0* R0*, L3R3 vµ L3* R3*. R3 sÏ ®­îc tÝnh nh­ sau : R3 = L2 ^ f(R2, k3) = R1 ^ f(R2, k3) = L0 ^ f(R0, k1) ^ f(R2, k3) T­¬ng tù ta cã : R3* = L0* ^ f(R0*, k1) ^ f(R2*, k3) Do ®ã : R3’ = R3 ^ R3* = L0’ ^ f(R0, k1) ^ f(R0*, k1) ^ f(R2, k3) ^ f(R2*, k3) Ta chän x, x* sao cho R0 = R0* cã nghÜa lµ R0’ = 00…0 Khi ®ã f(R0, k1) = f(R0*, k1) V× thÕ R3’ = L0’ ^ f(R2, k3) ^ f(R2*, k3) MÆt kh¸c, R3’ cã thÓ t×m ra ®­îc tõ hai b¶n m· vµ L0’ t×m ra tõ hai b¶n râ. Tõ ®ã, cã thÓ tÝnh f(R2, k3) ^ f(R2*, k3) nh­ sau : f(R2, k3) ^ f(R2*, k3) = R3’ ^ L0’ Mµ f(R2, k3) = P(C) f(R2*, k3) = P(C*) Víi C vµ C* lµ ®Çu ra cña 8 hép S. → P(C) ^ P(C*) = R3’ ^ L0’ → P(C ^ C*) = R3’ ^ L0’ P(C’) = R3’ ^ L0’ hay C’ = P-1(R3’ ^ L0’) §ã chÝnh lµ XOR ®Çu ra ®èi víi 8 hép trong 3 vßng. Tõ E = E1E2….E8; E = E1 *E2 *….E8 * vµ C’ = C1’C2’….C8’ ta x©y dùng ®­îc c¸c tËp Testj(Ej, Ej*, Cj’), víi j = 1 ÷ 8, chøa c¸c gi¸ trÞ ®óng cña J1J2….J8( chøa 48 bit cña kho¸ DES ë vßng 3 ). Tõ J1J2….J8 ®­a qua b¶ng Round 3 ta sÏ t×m ®­îc vÞ trÝ chÝnh x¸c cña 48 bit kho¸ ban ®Çu. KiÓu tÊn c«ng nµy sÏ dïng mét vµi bé ba E, E*, C’. Ta sÏ thiÕt lËp 8 côm ®Õm vµ do ®ã x¸c ®Þnh ®­îc 48 bit trong kho¸ k3 ( kho¸ cña vßng thø 3 ). Cßn l¹i 8 bit kho¸ ch­a ®­îc x¸c ®Þnh. §Õn ®©y ta sÏ dïng c¸ch thö toµn bé 28 = 256 tr­êng hîp cã thÓ cho c¸c bit cßn l¹i. IV.1.3 ThuËt to¸n th¸m m· DES 3 vßng : §Çu vµo lµ L0R0, L0*R0*, L3R3 vµ L3*R3* B­íc 1 : TÝnh C’ = P-1(R3’ ^ L3’) B­íc 2 : TÝnh E = E(L3) vµ E* = E(L3*) B­íc 3 : j = 1 ÷ 8 tÝnh testj(E, E*, C’) B­íc 4 : i = 1÷255 (gi¸ trÞ cña 8 bit cßn ®Æt dÊu ? ) T×m k (| k | = 56 ) sao cho ek (x) = y vµ ek (x*) = y* Khi ®· t×m ®­îc 56 bit kho¸, ta cÇn t×m nèt 8 bit kiÓm tra cña d·y 64 bit kho¸. Tuy nhiªn, do m· ASCII më réng ®· bá bit kiÓm tra cho nªn trong mét sè tr­êng hîp bÝt kiÓm tra ®ã kh«ng ®óng lµ cña kho¸ cÇn t×m. V× DES kh«ng dïng ®Õn c¸c bit kiÓm tra ®Ó m· ho¸ cho nªn kho¸ t×m ra vÉn lµ ®óng ( ®óng chÝnh x¸c 56 bit ) IV.2 Ph­¬ng ph¸p ®¸nh gi¸ tÝnh chÊt cña DES §Ó ®¸nh gi¸ ®é an toµn cña DES ta cã thÓ kiÓm tra c¸c tÝnh chÊt cña DES, nÕu tho¶ m·n ®iÒu kiÖn th× kÕt luËn lµ an toµn. C¸c tÝnh chÊt ®ã lµ: Sè trung b×nh c¸c bit ra thay ®æi khi thay ®æi mét bit vµo. Møc ®é ®Çy ®ñ Møc ®é hiÖu qu¶ dån nÐn Møc ®é tiªu chuÈn dån nÐn chÆt IV.2.1 C¸c ®Þnh nghÜa Ta xÐt: vector x = (x1,…,xn) € (GF(2))n, vector x(i) € (GF(2))n víi vector x(i) ®¹t ®­îc b»ng c¸ch lÊy phÇn bï bit thø i cña vector x (víi i = 1 ÷ n ) Träng sè Hamming w(x) cña x lµ sè c¸c thµnh phÇn kh¸c 0 cña vector x - Hµm f : (GF(2))n → (GF(2))m cña n bit vµo vµ m bit ra ®­îc gäi lµ ®Çy ®ñ (the degree of completeness ) nÕu mçi bit ra phô thuéc vµo mçi bit vµo: víi mäi i = 1 ÷ n vµ j = 1 ÷ m tån t¹i x € (GF(2))n víi ( f ( x(i) ))j ≠ ( f ( x))j cã nghÜa lµ tån t¹i vector x € (GF(2))n sao cho khi thay ®æi bit vµo thø i th× sÏ lµm thay ®æi bit ra thø j ( bit ra thø j phô thuéc vµo bit vµo thø i ) - Hµm f : (GF(2))n → (GF(2))m cã hiÖu qu¶ dån nÐn ( the avalanche effect ) nÕu trung b×nh cña ½ c¸c bit ra thay ®æi mçi khi mét bit vµo ®¬n ®­îc thay ®æi: víi i = 1÷ n - Hµm f : (GF(2))n → (GF(2))m tho¶ m·n tiªu chuÈn dån nÐn chÆt ( the strict avalanche criterion ) nÕu mçi bit ra thay ®æi víi x¸c su©t ½ mçi khi mét bit vµo ®¬n ®­îc thay ®æi: Víi mäi i = 1 ÷ n vµ j = 1 ÷ m Pr( ( f (x(i)))j ≠ ( f (x))j ) = ½ - Ma trËn phô thuéc cña hµm f : (GF(2))n → (GF(2))m lµ ma trËn A cì n*m mµ phÇn tö ai j biÓu thÞ sè c¸c d÷ liÖu vµo mµ khi thay ®æi bit vµo thø i dÉn ®Õn sù thay ®æi cña bit ra thø j : ai j = # { x € GF(2))n | ( f (x(i)))j ≠ ( f (x))j } víi i = 1 ÷ n vµ j = 1 ÷ m - Ma trËn kho¶ng c¸ch cña hµm f : (GF(2))n → (GF(2))m lµ ma trËn B cì n*(m+1) mµ phÇn tö bi j biÓu thÞ sè c¸c d÷ liÖu vµo mµ khi thay ®æi bit vµo thø i dÉn ®Õn sù thay ®æi j bit ra. bi j = # { x € GF(2))n | w( f (x(i)) - f (x) ) = j } víi i = 1 ÷ n vµ j = 1 ÷ m Tuy nhiªn, viÖc tÝnh to¸n ma trËn kho¶ng c¸ch vµ ma trËn phô thuéc cho tÊt c¶ c¸c d÷ liÖu vµo lµ kh«ng thÓ ®­îc, trõ khi sè c¸c d÷ liÖu vµo nhá . V× thÕ ng­êi ta xÐt mét sè “ thÝch hîp ” d÷ liÖu vµo ®­îc lùa chän ngÉu nhiªn. Gi¶ sö tËp X lµ tËp con ®­îc lùa chän ngÉu nhiªn thÝch hîp cña GF(2))n . Khi ®ã ma trËn kho¶ng c¸ch vµ ma trËn phô thuéc ®­îc ®Þnh nghÜa nh­ sau: - Ma trËn phô thuéc: ai j = # { x € X | ( f (x(i)))j ≠ ( f (x))j } víi i = 1 ÷ n vµ j = 1 ÷ m - Ma trËn kho¶ng c¸ch: bi j = # { x € X | w( f (x(i)) - f (x) ) = j } víi i = 1 ÷ n vµ j = 1 ÷ m IV.2.2 X¸c ®Þnh c¸c tham sè T×m tËp X lµ tËp con cña GF(2))n Râ rµng víi mäi x thuéc X th× x cã d¹ng x=(x1,…,xn), chän ngÉu nhiªn x nh­ sau: Chän ngÉu nhiªn x0 C {0,1} nhê hµm Random Chän ngÉu nhiªn x1 C {0,1} mét c¸ch t­¬ng tù … xn-1 ®­îc chän ngÉu nhiªn t­¬ng tù. §Õn ®©y x ®· ®­îc chän ngÉu nhiªn. Ta chän tiÕp x còng b»ng c¸ch ®ã. Mçi x ®­îc m« t¶ bëi 1 m¶ng, do vËy ta dïng m¶ng 2 chiÒu ®Ó m« t¶ x: x[i][j] víi i=0,…,n vµ j=0,…,n-1. For (i=0;i<N;i++) { for (j=0;j<n;j++) x[i][j]=random(2); } §Ó kiÓm tra c¸c tÝnh chÊt nªu trªn ta cÇn tÝnh ®­îc ma trËn kho¶ng c¸ch vµ ma trËn phô thuéc trªn c¬ së tËp X: - Ma trËn phô thuéc: ai j = # { x € X | ( f (x(i)))j ≠ ( f (x))j } víi i = 1 ÷ n vµ j = 1 ÷ m T×m tÊt c¶ c¸c phÇn tö trong vector x thuéc X sao cho khi ta cho x vµ x(i) lÇn l­ît lµ ®Çu vµo th× ta thu ®­îc ®Çu ra cña x kh¸c ®Çu ra cña x(i) b»ng c¸ch duyÖt tong phÇn tö cña x(i) thuéc X. Gi¶ sö hamf() lµ ch­¬ng tr×nh con thùc hiÖn hµm f ( sau nµy ta sÏ thay nã lµ DES() ), cã ®Çu vµo lµ m¶ng x[i] = ( x[i][0],…,x[i][n-1] ) vµ ®Çu ra lµ y=(y[0],…,y[m-1]). Khi ®ã ai j ®­îc tÝnh nh­ sau: For ( i=0;i<n;i++) for ( j=0;j<m;j++) { a[i][j]=0; for ( k=0;k<N;k++) { x*=(x[k][0],…,x[k][i-1],x[k][i]^1,x[k][i+1],…,x[k][n-1]) hamf(x[k],y); // y=( y[0],…,y[m-1]) hamf(x*,y*); // y*=(y*[0],…,y*[m-1]) if ( y[j] != y*[j] ) a[i][j]++; } } - Ma trËn kho¶ng c¸ch: bi j = # { x € X | w( f (x(i)) - f (x) ) = j } víi i = 1 ÷ n vµ j = 1 ÷ m T×m tÊt c¶ c¸c phÇn tö trong vector x thuéc X sao cho khi ta thay ®æi bit vµo thø i cña vector x vµ cho lÇn l­ìt vµ (i) lµ ®Çu vµo vµ kÕt qu¶ cã j bit ra kh¸c nhau. Ta cã thÓ tÝnh w( f (x(i)) - f (x) ) nh­ sau: Tinhw(z,*w,i) {w=0; x*=(z[0],…,z[i-1],z[i]^1,z[i+1],…,z[n-1]); hamf(z,y); hamf(x*,y*); for ( k=0;k<m;k++) if ( y[i] != y*[i] ) w++; return w; } Khi ®ã bi j ®­îc tÝnh theo thuËt to¸n: For ( i=0;i<n;i++) For ( j=0;j<m;j++) { b[i][j] = 0; for (k=0;k<N;k++) { x*=(x[k][0],…,x[k][i-1],x[k][i]^1,x[k][i+1],…,x[k][n-1]) tinhw(x[k],*w,i); if (w==j) b[i][j] =b[i][j]+1; } Sè trung b×nh c¸c bit ra thay ®æi khi thay ®æi 1 bit vµo Ta cã tËp X, gi¶ sö Ai lµ sè trung b×nh c¸c bit ra thay ®æi khi thay ®æi bit vµo thø i. Khi thay ®æi bit vµo thø i ta cã sè c¸c bit ra thay ®æi: w( f (x(i)) - f (x) ) khi ®ã ta cã: Ai = Vµ khi ta thay ®æi lÇn l­ît c¸c bit tõ 1 ®Õn n ta cã: D= D lµ sè trung b×nh c¸c bit ra thay ®æi khi thay ®æi 1 bit vµo. D ®­îc tÝnh nh­ sau: For (i=0;i<n;i++) { For (j=0;j<m;j++) { for (k=0;k<N;k++) { x*=(x[k][0],…,x[k][i-1],x[k][i]^1,x[k][i+1],…,x[k][n-1]); tinhw(x[k],*w,i); } w++ Ai = w } D= } Møc ®é ®Çy ®ñ - Møc ®é ®Çy ®ñ cña f ®­îc ®Þnh nghÜa nh­ sau : dc = 1 - T×m trong ma trËn phô thuéc tÊt c¶ c¸c cÆp (i,j) sao cho ai j =0. For(i=0;i<n;i++) For(j=0;j<m;j++) {if (a[i][j]=0) {printf(“&d &d”,i,j); …} } vµ tÝnh ®­îc dc theo c«ng thøc ®· cho. d. Møc ®é hiÖu qu¶ dån nÐn cña f lµ : da = 1 - cã thÓ ®­îc tÝnh nh­ sau: for (i=0;i<n;i++) { for(j=0;j<m;j++) { B[i][j] = 2j b[i][j] – m; B1 = sum(B[i][j]); } B2=abs() } vµ cã thÓ tÝnh ®­îc da theo c«ng thøc ®· cho. c. Møc ®é cña tiªu chuÈn tuyÖt ®èi cña f ®­îc ®Þnh nghÜa lµ : dsa = 1 - for (i=0;i<n;i++) for(j=0;j<m;j++) { B[i][j] = abs (); B1 =sum(B[i][j]); } vµ cã thÓ tÝnh ®­îc dsa theo c«ng thøc ®· cho. §Ó hµm f cã møc ®é ®Çy ®ñ, møc ®é hiÖu qu¶ dån nÐn vµ møc ®é tiªu chuÈn dån nÐn chÆt tèt th× c¸c sè dc , da vµ dsa ph¶i tho¶ m·n dc = 1, da ≈ 1, dsa ≈ 1. Theo tµi liÖu Pascale Serf _ SiemÐn AG, ZI IK 3, víi 5 øng cö viªn cña AES lµ Mars, RC6, Rijndael, Serpent vµ Twofish ng­êi ta còng ®· kiÓm tra c¸c tÝnh chÊt : - Sè trung b×nh c¸c bit ra bÞ thay ®æi khi thay ®æi mét bit vµo - Møc ®é ®Çy ®ñ - Møc ®é hiÖu qu¶ dån nÐn - Møc ®é tiªu chuÈn dån nÐn chÆt Víi sè c¸c vßng kh¸c nhau, tõ sè ®Çy ®ñ c¸c vßng ®Õn ®óng mét vßng. KÕt luËn Sau khi nghiªn cøu vÒ viÖc kiÓm tra ®é an toµn cña chuÈn m· d÷ liÖu DES ( Data Encription Standards ) t«i ®· cã ®­îc nh÷ng hiÓu biÕt s©u h¬n vÒ c¸c hÖ mËt cæ ®iÓn, vµ ®Æc biÖt lµ vÒ ChuÈn m· d÷ liÖu DES . Trong b¸o c¸o nµy giíi thiÖu chung vÒ c¸c hÖ mËt, vÒ chuÈn m· d÷ liÖu DES, vµ vÒ thuËt to¸n kiÓm tra ®é an toµn cña DES. Giíi thiÖu vÒ hai ph­¬ng ph¸p kiÓm tra ®é an toµn cña DES ®ã lµ ph­¬ng ph¸p l­îng sai tÊn c«ng DES 3 vßng vµ ph­¬ng ph¸p ®¸nh gi¸ c¸c tÝnh chÊt cña DES . Vµ ®Ò tµi nµy ®i s©u nghiªn cøu ph­¬ng ph¸p ®¸nh gi¸ c¸c tÝnh chÊt cña DES ®ã lµ c¸c tÝnh chÊt: Sè trung b×nh c¸c bit ra thay ®æi khi thay ®æi mét bit vµo. Møc ®é ®Çy ®ñ Møc ®é hiÖu qu¶ dån nÐn Møc ®é tiªu chuÈn dån nÐn chÆt. Giíi thiÖu s¬ l­îc c¸c b­íc tÝnh to¸n c¸c tham sè liªn quan nh»m ®¸nh gi¸ ®é an toµn cña DES. Em xin ch©n thµnh c¶m ¬n thÇy T.S. NguyÔn Ngäc C­¬ng ®· tËn t×nh h­íng dÉn trong qu¸ tr×nh thùc hiªn. §ång thêi c¶m ¬n c¸c thÇy c« trong khoa vµ b¹n bÌ cïng líp ®· t¹o ®iÒu kiÖn thuËn lîi cho em thùc hiÖn ®Ò tµi. Sinh viªn thùc hiÖh NguyÔn N­¬ng Quúnh tµi liÖu tham kh¶o Pascale Serf – Siemens AG, ZT IK 3, April 3 2000 Gi¸o tr×nh An toµn th«ng tin _ NguyÔn Ngäc C­¬ng Kü thuËt lËp tr×nh C c¬ së vµ n©ng cao _ Gs. Ph¹m V¨n ¢t Cryptography theory and practice Môc lôc

Các file đính kèm theo tài liệu này:

  • docNghiên cứu và thực hiện 1 số TEST để đánh giá độ an toàn của DES.DOC