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
39 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2463 | Lượt tải: 0
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 lu 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 lu 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… Nhng 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 trng 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 nhng 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¶, nhng 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 nhng 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 cha ®ó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, nhng 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 trng 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 lu 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, nhng 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 lu 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¸ cha ®î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:
- Nghiên cứu và thực hiện 1 số TEST để đánh giá độ an toàn của DES.DOC