Ebook nhập môn phân tích thông tin có bảo mật phần 2 - ts. hồ văn canh, ts. nguyễn viết thế

  • Số trang: 175 |
  • Loại file: PDF |
  • Lượt xem: 20 |
  • Lượt tải: 0
hoangtuavartar

Đã đăng 24838 tài liệu

Mô tả:

Chirơng 5 MỘT SỐ PHưONG PHẤP THAM mã dữ liệ u DES 5.1. THÁM MÃ VI SAI ĐỐI VỚI DES VÀ CÁC HỆ MÃ KHỐI LẶP GIỐNG OES 5.1.1. Mô tẳmã M ột sự mô tả đầy đủ về D E S đước nêu trong Công báo v ề ch u ẩn xử lý th ông tin Láên bang sô' 46 n g à y 15 th á n g 01 năm 1977. D E S mã hoá m ột dòng bit rõ X có độ d à i 64 với khoá K là dòng 56bit, đưa ra bản m ã y cũng là m ột dăy bit có độ dài 64. DES -Ịr- Hình 5.1. Mô tả DES = 64;|y| = 64;|k| = 56; Tiìuật toán mã/dịch DES gồm 3 phần: A: T h u â t to á n m ã/dỉch B: Lược đồ x â y dự ng hàm f(Rị, kị) C: Lược đồ tạo khóa {kj i = 1,16 B ản rõ R được ch ia th à n h các bỉock,m ỗi bỉock gồm 6 4b ỉt (8bjrte) m à ta k í h iệu là X và cũ n g được gọi là bản rõ X. 154 Nhập môn Phân tích thông tin có bào mật A. Thuật toán mã hoá gồm 3 giai đoạn 1. C h o b ả n rõ X, ta tín h được Xo q u a v iệ c h o á n v ị các b it c ủ a X th e o h o á n v ị đ ầ u IP. X o=IP(x) = LoRo L q ỉà 32bit đầu tiê n của Xq còn Ro là 32bit còn lạ i và IP là hoán vỊ đầu cố định. 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 2. Lặp 16 vòng Hình 5.2. Một vòng DES 155 Chương 5: M ột số phương pháp thám mã dữ liệu D E S i-l R i= L i_ ,© f ( R i_ „ k i) D ấu "©" th ể h iệ n phép toán “hoặc loại trừ” h ai dãy bit, f là m ột hàm m à c h ú n g ta sẽ để cập đến sau , kj là nhữ ng dãy d à i 48 b it được tạo từ khoá k bỏi th u ậ t toán riêng. 3. B ản m ã y được tín h bỏi hoán vỊ IP ’ cùa RieLie, chú ý đảo ngược vỊ trí củ a Lie và Rig. if ’ // 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 13 53 21 61 29 36 35 4 45 44 52 20 60 3 43 12 11 51 19 59 28 27 34 2 1 42 10 50 41 9 49 18 17 58 57 33 26 25 Hình 5.3 B • Hàm f(A,J) Đ ầu vào của h à m f là đối s ố A, m ột dây 32bit, đối sô' th ứ h a i là J gồm 48bit, v à đầu ra của f là m ột dãy 32bit. Các bưốc sa u đây được thực hiện: 1. Mỏ rộn g A từ 32bit th à n h 48bit: Đ ôl rộng th àn h 4 8 b it nh ò toán tử E số A được mỏ 156 Nhập môn Phân tích thông tin có hào mật 2. T ính B = E ( A ) 0 J : K ết quả B được tách th àn h 8 khối, m ỗi B khối gồm 6b it liê n tiếp từ B 1B2....BX cụ th ể là — 3. Sử d ụ n g 8 hộp S: S |,S 2,...,S8 M ỗi hộp Sị là m ột m ả n g h a i chiều 4x16, m ỗi dòng chứa các giá trị từ 0 đến 15. T a có đầu vào Bj là một dãy 6bit Bj = bibababíbgbg. H ai b it bịbe 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à 4bit b2b3b4bs xác định b iểu diễn n h ị p h ân c ù a c là ch ỉ s ố cột củ a Sj (0 < c < 15). S au đó Sj(Bj) là sô' n ằm ỏ tọ a độ (r,c) gồm 4bit. T heo cách này, ta k ý h iệu Cj = Sj(Bj), (1 ^ ^ 8). 4. Dòng bit c = C,C2C3C4C5C6C7C8 với độ dài 32bit được đổi chỗ th eo h o á n v ị p . K ết quả dăy P(C) ch ín h là f(A,J). Cụ th ể f(A,J) = P(C). Hàm f được thể hiện trong hình 5.4 dưối đây: Chương 5: M ột sổ phương pháp thảm mã dừ liệ u D E S 157 Nhập môn Phăn tich thông tin có bảo mật 158 8 hộp s và hoán vị P: Si 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 16 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 7 2 13 12 0 5 10 15 1 8 14 6 11 3 S2 4 9 3 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 13 14 7 11 10 4 1 5 8 9 3 2 15 8 10 1 3 15 2 11 6 12 7 6 13 13 4 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 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 14 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 8 5 3 15 13 0 14 9 5 0 15 10 3 9 8 6 Ss 2 12 4 1 7 10 11 14 11 2 12 4 7 13 6 1 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 159 Chương 5: M ột sổ phương pháp thám mà dừ liệ u D E S Se 12 1 10 15 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 Se 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 12 14 2 0 6 10 13 15 3 5 2 1 14 7 9 4 10 8 13 15 12 9 0 3 5 6 8 11 H oán vị 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 c - Lược đồ tạo hệ thỂmg ktìoá Khoá K là m ột dãy 64bit trong đó các bit th ứ 8, 16, 24, 32,40, 48, 56, 64 là các bit k iểm tra. Các b it kiểm tra n ày sẽ 160 Nhập môn Phân tích thông tin cô bảo một được bỏ qu a trong qu á trìn h tạo khoá, như vậy ta còn lại 56bit đầu vào. Cho 5 6 b it này hoán vị như theo bảng PC-1 ta sẽ tìm được CqD q với Co là 28bit đầu tiê n của PC -1, Do là 28bit còn lại. P C -l(K ) = CoDo Với i = 1 ^ 16 ta tính: Q = L S ì(C m ) Di = LS ì(D m ) LSị th ể h iện p h ép dịch trái quay vòng m ột hoặc hai bit, phụ thuộc vào g iá trị của i, dịch một bit n ếu i = 1, 2, 9, 16 và dịch h ai b it vổi các g iá trị còn lạ i của i. Kj được tính theo CịDị qua bảng h oán vỊ P C -2. Ki = PC-2(CiDi) PC-2 PC-1 57 49 41 33 25 17 9 14 17 11 24 1 5 1 58 50 42 34 26 18 3 28 15 6 21 10 10 2 59 51 43 35 27 23 19 12 4 26 98 19 11 60 52 44 36 16 7 27 20 13 2 63 55 3 47 39 31 23 15 41 52 31 37 47 55 7 62 54 46 38 22 S3 51 48 61 40 46 6 30 33 14 45 30 37 13 5 28 20 12 4 49 39 56 34 21 44 53 46 42 50 36 29 32 29 Từ P C -1 ch u y ển s a n g P C -2 bỏ đi 8 sô" (8 vị trí): 54, 57,58, 59, 60, 61, 62, 63. Chương 5: M ột số phương pháp thám mã dữ liệ u D E S 161 Co: 28bit đầu; Do: 28bit cuối; i = 1 . 2 , 9 . 16 thi La dịch trải vòng Ibit (bit) Hình 5.5. Lược đồ tạo hệ thông khóa é N h ư vậy ta đã có m ột th u ậ t to á n h o à n ch ỉn h v ề m ã hoá dữ liệ u theo tiê u ch u ẩn D E S. 162 Nhập môn Phân tích thông tin có bào mật Hừih 5.6. Sơ đồ thuật toán mã hóa DES Chương 5: M ột số phương pháp thảm mã dừ liệu D E S 163 5 .1 .2 . G iải m â DES Tương tự nh ư m ă hoá, đ ể giải m ă m ột dăy ký tự đâ được m ã hoá ta cũ n g thực h iệ n th eo trìn h tự các bưdc như trên , tu y n h iên h ệ th ổ h g kh oá lú c n ày đã được tạo th eo ch iều ngước lại. /. Thuật toán Mã hoắ Cho bản rõ X Xo = IP(x) = LqRo i = 1,2,..., 16 L i = R j.j Yo ~ y = iP -‘(yo) Giải mã Cho b ản m ã y Yo = IP(y) = RieLie = L’oR 0 i = 1,2,...,16 L’ = R V i Xq ~ ( R 16^ le) X = IP-*(Xo) 164_______________ Nhập môn Phân rích thông tin có báo một 2. Chúhg minh thuật toán Có bản m ã y yo = IP(y) = IP(IP-*(R,eL,6)) = R ,e L ,6 = L ’oR’o V ậ y L ’o = R ,6 ;R ’o = L,e; Với i = 1 L \ = R ’o = L,e = R,s; R ’, = L ’o^f(R’o.Ki6) ~ ~ Li5^f(Ri5KỊg)^f(Ri5KỊg) = Ljs; Tóm lại: ♦ L 1= Risỉ 1~ L j5; Tương tự như vậy cho đến khi i = 16 ta sẽ có: L 1 6 ~ R 1 5 ~ = R q ; R’,e = L’,s''f(R’,5.K,) = R,'^f(L„K,) = LoAf(R^,K,)Af(R„,K,) = Lo; L’i6 “ ~ X = IP-‘(R\6, L’,6) = IP-’(Ro Lo) = IP-‘(Xo) Từ đó ta th ấ y th u ậ t toán giải mâ ch ỉ k h á c với th u ậ t toán m ã hoá ỗ chỗ tạo h ệ th ốh g khoá. N ếu m ã hoá tạo khoá từ k ],k2,.~.kj6 th i giải m ă tạo h ệ th ốhg khoá từ kje,k,g,..,ki. 165 Chương 5: M ộ i 5Óphương pháp thám mã dữ liệu D E S 5.1.3. Thám mã vi sai dối với các khôi mã lặp T hông thường các h ệ m ã khôi khóa bí m ật được th iế t k ế dự a trên cơ sò lặp m ột hàm tương đối yếu v ề m ặt m ật m ã nào đó (để có tốc độ cao, th iế t k ế đdn giản...). M ỗi phép lặp được gọỉ là m ột vòng. Đ ầu vào của mỗi vòng là hàm của đầu ra của vòn g trước và m ột k h óa con đưỢc th iết k ế từ khóa bí m ật ban đ ầ u theo lược • đồ tạo • khóa. M ột • m ã khối khóa bí m ật • vdi r p h ép lặp như th ế được gọi là m ột m ã lặp r vòng. Các h ệ D E S h a y ID EA đều là m à k h ổ ì lặp theo quan niệm trên. P h ần này ta sẽ xem x é t n g u y ên lý tấ n công vi sa i đôì với m ã lặp có d ạ n g tổng q u á t nh ư trên h ìn h 5.7. H ìn h 5.7. Phép mả hóa một cặp bản rõ vói mã lặp r vòng Với các ký h iệu n h ư trong h ìn h 5.7, ta có Y = f(X, Z) là m ột hàm vòng sao ch o với m ỗi khóa con z, hàm f(., Z) th iế t lập m ột tưdng ứ ng 1-1 giữ a đầu vào X và đầu ra Y. Vi sai AX giữ a h a i b ản rõ (hay h ai bản mà) X và X* được xác đ ịn h bỏi: Àx = X ® X*-‘ ỏ đây ® ký h iệu ỉà phép toán nhóm đă xác định nào đó tr ên tập các bản rõ (= tập các bản mã), và x*‘*là ngh ịch đảo c ủ a các phần tử X* tron g nhóm đó. H àm vòn g f(X, Z) được gọi 166 Nhập môn Phân tich thông tin có bảo mật là yếu n ếu cho trước m ột vài bộ ba (AX, Y, Y*) là có thể xác đ ịn h được khóa z . Từ cặp các phép m ã hóa ch ú n g ta có th ể xác định được m ột dãy các vi sa i AY(0), AY(1),..., AY(r), ở đây Y(0) = X, và ¥^(0) = X* là cặp bản rõ, cũ n g vậy AY(0) = AX, còn Y(i) và Y*(i) là đầu ra của vòng th ứ i, chún g cũng là đầu vào của vòng thứ (i+1). Khóa con cho vòng th ứ i ký hiệu là z®. T rong các lập lu ậ n sa u này ta luôn giả thiết X * X*. Thấm mã vi sai dựa trên yếu tô'là hàm vồng f trong một mả khôi lặp là một hàm yếu về mật mà. Cạ thể nếu cập bản mẵ được biết và bằng cách nào đó có thể đạt được vi sai của cặp đấu vào tại vòng cuối cùng cùa mã khôĩ lặp đó, thì tốn công vi sai có thể áp dụng dể đạt dược hoặc xác định được khóa hay một phần khóa con tại vòng cuối cùng. Trong thám mã vi sai điều đó dược thực hiện bằng cách chọn cặp bản rỗ (X, X“) có vi sai ìà a sao cho VI sai AY(r-l) của cặp đầu vào tại vòng cuối cùng sẽ lấy giá trị cạ th ểp với một xác suất cao. Vì có xác suất cao nên các khóa con tại vòng cuổì được giải từ bộ ba (AY(r-l), Y(r), Yir)) sẽ thường tập trung vào một sô'phần tử có khả nàng nhất, thám mã sê quyết định để tim ra khóa con đúng tại vồng cuôĩ cùng. Từ khóa con của vòng cuôĩ này, tã có thểxảc định được lại khóa bí mật ban đầu (nếu lược đồ tạo khóa là đơn giản). Định nghĩa 1: M ột v ỉ sa i i vòng là m ột cặp (a , P), ỏ đây a là vi sa i của m ột cặp b ản rõ khác n h au X v à x \ và p là m ột vi s a i có th ể đôi với k ết quả đầu ra vòng th ứ i là Y(i) và Y*(i). Xác su ấ t củ a v i sa i i vòng (a, P) là xác su ấ t có điều kiện sao cho p là vi sa i AY(Ì) củ a cặp bản mă sa u i vòng với điều kiện Chương 5: M ột sổ phương pháp thám mã dừ liệu D E S 167 cho trưốc cặp bản rõ (X, X*) có vi sa i AX = a khi bản rõ X và các khóa con là ngẫu nh iên độc lập phân bô' đều. Ta ký hiệu xác su ấ t củ a vi sai này là P(AY(i) = p IAX = a). Thủ tục cơ bản của tân công vi sai đối váf một mã khối lặp * r vòng: 1. T ìm m ột vi sa i (r-1) vòng (a, P) sao cho xác suất: P(A Y (i-l) = P|AX = a ) là cực đại hoặc gần cực đại. 2. Lấy bản rõ X m ột cách ngẫu n h iên đều và tín h toán X* sa o cho vi sa i AX giữ a X và X* là a . T iến h àn h m ã hóa X và X* dưới m ột khóa bí m ật cụ th ể cần tìm z (m à đôl phương đang sử dụng). Từ các bản m ã k ết quả Y(r) và Y*(r), tìm mỗi m ột giá trị có th ể cù a kh óa con của vòng cuối cùng tướng ứng vối vi sa i đâ đ ịn h trước A Y (i-l) = p (tức là sử dụng bộ ba AY(ì-1) đặt b ằn g p, Y(r), Y*(r) để tín h toán tìm vào bộ đếm T hêm 1 số lần x u ấ t h iện cùa mỗi giá trị có th ể có cùa khóa con 3. Lặp lạ i bước 2 cho tới khi m ột hoặc n h iều giá t i ị của khóa con là được đếm n h iều hơn hẳn các giá trị khác. Lấy ra khóa con đưỢc đếm n h iều n h ất hoặc m ột tập nhỏ các khóa có sô' đếm lón nhất. S a u đó việc quyết định khóa đúng thuộc v ề ngưòi thám mã. C hú ý rằn g trong tấ n công vi sai, tấ t cả các khóa con là n gẫu n h iên , độc lập v à có phân b ố đều. T uy n h iên trong tín h toán xác su ấ t vi sai, ta luôn giả th iết bản rõ và tấ t cả các kh óa con là độc lập n g ẫ u n h iên đều. D o đó chún g ta cần tạo m ột g iả th iết sau: 168_______________ Nhập môn Phân tich thông tin có bảo mật * Giả thiết về tính tương đương ngẫu nhiên (Stocbastic Equivalence) Đ ối với m ột vi sa i (r-1) vòng (a, P), ta có: P(AY(i-l) = p IAX = a ) « P(AY(i-l) = p IAX = a, z<» = 0)i.... 2^-^^ với h ầu h ế t tập giá trị khóa con (0)i, 0 >2 , . . . , Do có 2™ - 1 giá trị cùa A Y (i-l), nên ch ú n g ta có th ể rút ra k ết lu ậ n sau: Giả sù giẳ thiết về tính tương đương là đúng, khi đó một mả lặp r vòng với tập khóa con độc lập sẽ có thể bị tổn thương đôì với tấn công vi sai nếu và chỉ nếu hàm vòng là yếu và tồn tại một vi sai (r-1) vòng (a, P), sao cho P(ÁY(i-l) - ậỊÁX = a) » 2’”', ở đây m là độ dài của khôi mã. Ký h iệu Comp(r) là độ phức tạp của m ột tấ n công thám m ã với m ã ỉặp r vòng, xem như là sô' phép m ã hóa cần sử dụng trong tấn công. Khi đó ta có th ể chứ ng m inh kết quả sau: Định lý 1: (Cận dưối v ề độ phức tạp của tấ n công v i sai đôi với m ột m ã ỉặp r vòng) G iả sử giả th iết v ề tín h tương đưdng n gẫu n h iên ỉà đúng, k h i đó độ phức tạp của tấn công vi sa i sẽ thỏa m ãn đánh giá: p. 1 ^ T -\) Ồ đầy = maxainaxp P(A Y (i-l) = p IAX = a), trong đó m là độ dài ỉdiôl mã. Thực t ế nếu th à n h công. « 1/(2“ - 1), th ì tấ n công vi sai là không Chương 5: M ột số phương pháp thảm mã dừ liệ u D ES 169 Chứng minh: Chú ý rằ n g giá trị tín h trước p cùa vi sa i AY(ì-1> ít n h ất phải lấ y n h iều hơn m ột lầ n so vói giá trị khi chọn tru n g bình ngẫu n h iên p', nếu nh ư tấn công vi sai th àn h công. N hư vậy, ta có T P „ „ > (T/(2"‘ - 1)) + 1 là điều k iện c ầ n cho sự th à n h công sa u T phép thử, ỏ đây m ỗi phép thử gồm phép chọn m ột cặp b ản rõ có vi sa i a cho trước. T ừ đó ta có: 2.T .(P „„ - 1/(2'" - 1)) > 2, m à Comp(r) = 2.T (m ỗi phép thử có 2 phép m ã cho cặp bản rõ), nên: Comp(r) = 2.T > 2/(Pmax - - 1)) (đpcm). 5 .1 .4 . Sơ bộ về phương pháp tân công vi sai trên DES Phương pháp tấ n công v i sa i (DC) trên D E S do B iham và S h am ir đề x u ấ t là m ột tron g nhữ ng phưdng pháp tấ n công nổi tiế n g n h ấ t đối với hệ D E S. Đ ây là phép tấn công với bản rõ chọn lọc, và nó đã khai th á c triệt để điểm yếu của D E S tại các hộp nén. B ây giò ta sẽ mô tả ý tư ỏng cơ bản dùng trong tấ n công này. Trước h ế t ta sẽ bỏ qua p h ép h o á n vỊ đ ầu IP và h oán v ị ngưỢc củ a nó (k hông ản h h ư ỏ n g tới k ế t quả p h â n tích m ã), k h i đó có th ể xem LộRo là b ả n rõ và L „R „ là bản m ă D E S m vòn g. Phương pháp th á m m ã m ã vi sa i xoay quanh việc so sá n h k ết quả của phép XOR giữa 2 bản rõ vối k ết quả của p h ép XOR giữa 2 bản m ã tương úng. Với giả th iết rằng các b ản rõ được lấy ngẫu n h iên đểu trên không gian các đầu vào có th ể, ta quan sá t p h ân bô' củ a các k ết quả phép XOR đầu ra Nhập môn Phân tích thông tin có bảo mật 170 có tu ân theo phân bố n gẫu nhiên đểu hay không. N ếu bảng phân b ố là không đều, th ì thám m ă sẻ lợi dụng để xây dựng phương pháp tấn công bản rõ chọn lọc. Định nghĩa 2: G iả sử Sj là một hộp nén (1 < j < 8). Xét 1 cặp đã sắp xếp của các xâu bit độ dài 6 (ký hiệu là Ta nói rằng XOR vào của Sj là Bj 0 Bj và XOR ra của Sj là Sj(Bi)eSj(B‘). VB' € z ị, ta đặt: à (B ;) = { ( B j ,B j e B ') : B ; € Z 5 ì Định nghĩa 3 Với 1 < j < 8, B' € zị,c' 6 z ị , ta định nghĩa: IN j(B ',C j) = {(Bj 6 z ị :S^(Bj)®Sj(Bj e B ' ) = C '} V à N j(B ',C ') = ||lN j(B ',C ') N hư vậy, N j(B j,C ' ) là s ố các cặp có XOR vào là B' và có XOR ra là C ;. Nhớ lạ i rằng, đầu vào của các hộp n én ỏ vòng thứ i là B = E©J, trong đó E = E(Rị.i) là giá trị cùa hàm mồ rộng E tác động vào Rj.i và J = Kj là các bit khóa vòng thứ i. Khi đó XOR vào của tấ t cả 8 hộp nén có th ể được tín h như sau: B0 B* = (E 0 J )e (E*®J) = E©E* Đ ến đây ta th ấ y m ột điều rất quan trọng là XOR vào không phụ thuộc vào các bit khóa J, như ng XOR ra chắc Chương 5: M ột số phương pháp thám mã dừ liệu D E S 171 ch ắn phụ thuộc vào các bit khóa này, và các XOR vào của các hộp nén sẽ được tín h qua giá trị của hàm mỏ rộng E đã được b iết công khai. Bây giờ ta viết B, E và J là m ột dây liên tiếp 8 xâu 6 bit: B = B 1B2B3B4B5B6B7B8 E = E,E2E3E4E5E6E7Eg J=J,J2J3J4J5W7J8 và B*, E' th eo cách tương tự. Khi đó nếu b iết các giá trị Ej, E* và giá trị XOR ra của Sj là C j , th ì chắc ch ắn rằng: E j0 J j€ lN j(E ',C j) Từ đó ta định n gh ĩa các tập TEST cho đoạn khóa con Jj như sau: Định nghĩa 4 Vối các ký hiệu đã nêu ta xác định; TESTj(EjE;,C'j) = {Bj © E j : Bj e INj(E',Cj)} trong đó: Ej = Ej 0 Ej Từ định nghĩa này ta có ngay k ết quả sa u đây: Định lý 2 Giả sử Ej và E* là h a i xâu vào của hộp nén Sj còn XOR ra của Sj là Cj. Khi đó các bit khóa Jj sẽ nằm trong tập TESTj(EjE’ ,C ')- Nhập môn Phân tich thông tin có bảo mật 172 B ây giò ta áp d ụ ng các ý tưỏng trên đây để mô tả phương pháp tấ n công vi sa i trên D ES. Với DES 3 vòng. Ta có th ể viết: R3=L2©F(R2, K3) = R, © F(R2, K3) = Lo © F (R o,K ,)© F (R 2 ,K 3 ) B iểu diễn R3 m ột cách tương tự, ta có: R*3 = L Í,eF (R o ,K ,) 0 F(R;,K,)®F(R 2 ,K 3 )® F (R ;,K 3 ) N ếu ta chọn R q= 00...0, thì: R ;= L 'o e F (R 2 ,K 3 )e F (R ;,K 3 ) B ây giò, do R3,Lq đã biết nên có th ể tín h được: F (R 2 , K 3 ) © F(R 2 , K 3 ) = R'3 © Ló M ặt khác, ta CÓF(R2,K 3) = P(C), F(R2,K 3>= P ( c ‘ ) và do tín h đồng cấu tu y ến tín h của phép h oán vị p n ên ta tín h được: c =cec = p - '( R 3 0LÓ ). Đ ây là XOR ra cùa 8 hộp n én ỏ vòng th ứ ba. Còn R2 = L3 và R 2 = L*3 cũng được b iết (chúng là m ột ph ần của các bản m ã), nên cố th ể tín h được các dữ ỉỉệu ỉiên quan đến đầu vào của các hộp nén là E = EíLg) và E*= E(L*3). N hư vậy ta đă b iết E, E* và C' củ a vòng thứ ba và từ đó có th ể x â y dựng các tập TESTi...TESTg chứ a các g iá trị có th ể củ a các bit khóa J iJ 2...Jg.
- Xem thêm -