intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Giáo trình tin học : Tìm hiễu hệ chuẩn mã dữ liệu và cách tạo ra nó phần 4

Chia sẻ: AFASFAF FSAFASF | Ngày: | Loại File: PDF | Số trang:6

57
lượt xem
3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một đặc điểm của phép tối ưu hoá thời gian - bộ nhớ này là nó không phụ thuộc vào "cấu trúc" của DES trên mọi phương diện.

Chủ đề:
Lưu

Nội dung Text: Giáo trình tin học : Tìm hiễu hệ chuẩn mã dữ liệu và cách tạo ra nó phần 4

  1. Vietebooks Nguyễn Hoàng Cương Mét ®Æc ®iÓm cña phÐp tèi −u ho¸ thêi gian - bé nhí nµy lµ nã kh«ng phô thuéc vµo "cÊu tróc" cña DES trªn mäi ph−¬ng diÖn. KhÝa c¹nh duy nhÊt cña DES cã quan hÖ tíi phÐp tÊn c«ng nµy lµ c¸c b¶n râ vµ c¸c b¶n m· 64 bÝt trong khi c¸c kho¸ cã 56 bÝt. Ta ®· th¶o luËn vÒ ý t−ëng t×m kho¸ b»ng ph−¬ng ph¸p vÐt c¹n: víi mét cÆp râ - m· cho tr−íc, h·y thö tÊt c¶ 256 kho¸ cô thÓ. §iÒu nµy kh«ng yªu cÇu bé nhí, nh−ng trung b×nh ph¶i thö 255 kho¸ tr−íc khi t×m ®−îc kho¸ ®óng. MÆt kh¸c, víi mét b¶n râ x cho tr−íc, Oscar cã thÓ tÝnh tr−íc yK = eK(x) ®èi víi toµn bé 256 kho¸ K vµ x©y dùng mét b¶ng c¸c cÆp (yK,K) ®−îc s¾p xÕp theo c¸c t¹o ®é ®Çu cña chóng. Sau ®ã khi Oscar thu ®−îc b¶n m· y ( lµ kÕt qu¶ cña phÐp m· b¶n râ x), anh ta ph¶i nh×n vµo gi¸ trÞ y trong b¶ng vµ lËp tøc t×m ®−îc kho¸ K. Nh− vËy trong tr−êng hîp nµy viÖc t×m ®−îc kho¸ K chØ yªu c©u mét thêi gian cè ®Þnh nh−ng ta ph¶i cã mét b« nhí cã dung l−îng lín vµ cÇn thêi gian tÝnh to¸n tr−íc lín ( chó ý lµ quan ®iÓm nµy kh«ng cã lîi thÕ vÒ thêi gian tÝnh to¸n tæng céng nÕu chØ cÇn t×m mét kho¸, bëi v× viÖc x©y dùng b¶ng còng mÊt nhiÒu thêi gian nh− viÖc t×m khãa vÐt c¹n. Ph−¬ng ph¸p nµy chØ cã lîi khi cÇn t×m nhiÒu kho¸ trong mét kho¶ng thêi gian v× ta chØ cÊn dïng mét b¶ng cho tÊt c¶ c¸c tr−êng hîp). PhÐp tèi −u ho¸ thêi gian - bé nhí sÏ cã thêi gian tÝnh to¸n nhá h¬n phÐp t×m kiÕm vÐt c¹n vµ cã yªu cÇu bé nhí nhá h¬n viÖc lËp bangr tra cøu. ThuËt to¸n cã thÓ m« t¶ theo hai tham sè m vµ t lµ c¸c sè nguyªn d−¬ng. ThuËt to¸n cÇn mét hµm rót gän R ®Ó rót gän mét x©u bÝt cã ®é dµi 64 thµnh mét x©u bÝt cã ®é dµi 56 ( ch¼ng h¹n R ph¶i vøt bá 8 trong 64 bÝt). Gi¶ sö x lµ mét x©u b¶n râ cè ®Þnh 64 bÝt. H·y x¸c ®Þnh hµm g(K0) =R(eKo(x)) víi mét x©u bÝt K0 cã ®é dµi 56. Chó ý r»ng g lµ mét hµm thùc hiÖn ¸nh x¹ 56 bÝt sab\ng 56 bÝt. Trong giai ®o¹n tiÒn xö lý, Oscar chän m x©u bÝt ngÉu nhiªn cã ®é dµi 56 ®−îc kÝ hiÖu lµ X(i,0), 1≤ i ≤ m. Oscar tÝnh x(i,j) víi 1 ≤ j ≤ t theo quan hÖ truy to¸n sau: X(i,j) = g(X(i,j-1)), 1 ≤ i x ≤ m , 1 ≤ j ≤ t nh− chØ trªn h×nh 3.6. H×nh 3.6. TÝnh X(i,j) X (1,0) ⎯g X (1,1) ⎯g ... ⎯g X (1, t ) ⎯→ ⎯→ ⎯→ X (2,0) ⎯g X (2,1) ⎯g ... ⎯g X (2, t ) ⎯→ ⎯→ ⎯→ . . . X (m,0) ⎯g X (m,1) ⎯g ... ⎯g X (m, t ) ⎯→ ⎯→ ⎯→ Trang 19
  2. Vietebooks Nguyễn Hoàng Cương Sau ®ã Oscar x©y dùng mét b¶ng c¸c cÆp T = (X(i,t), X(i,0) ®−îc s¾p xÕp theo to¹ ®é ®Çu cña chóng( tøc lµ chØ l−u gi÷ cét ®Çu vµ cét cuèi cña X). Sau khi thu ®−îc b¶n m· y ( lµ b¶n m· cña b¶n râ x ®· chän). Oscar cÇn ph¶i x¸c ®Þnh K vµ anh ta sÏ x¸c ®Þnh ®−îc nÕu K n»m trong t cét ®Çu cña b¶ng X, tuy nhiªn anh ta chØ lµm ®iÒu nµy b»ng c¸ch chØ nh×n vµo b¶ng T. Gi¶ sö r»ng K = X(i,t-j) víi j nµo ®ã, 1 ≤ j ≤ t ( tøc gi¶ sö r»ng K n»m ë t cét ®Çu tiªn cña X). Khi ®ã râ rµng lµ gj(K) = x(i,t), trong ®ã gj kÝ hiÖu hµm nhËn ®−îc b»ng c¸ch lÆp g mét sè lÇn b»ng j. B©y giê ta thÊy r»ng: gj(K) = gj-1(g(K)) = gj-1(R(eK(x))) = gj-1(R(y)) Gi¶ sö tÝnh þj,1 ≤ j ≤ t, tõ quan hÖ truy to¸n R(y) nÕu j = 1 yi = nÕu 2 ≤ j ≤ t g(þj-1) Tõ ®ã rót ra r»ng yj = X(i,t-j) nÕu K = X(i,t-j). Tuy nhiªn cÇn chó ý r»ng yj = X(i,t) ch−a ®ñ ®Ó ®¶m b¶o lµ K = X(i,t-j). Së dÜ nh− vËy v× hµm rót gän R kh«ng ph¶i lµ mét ®¬n ¸nh: miÒn x¸c ®Þnh cña R cã lùc l−îng 264 vµ gi¸ trÞ cña R cã lùc l−îng 256, bëi vËy tÝnh trung b×nh cã 28 = 256 nghÞch ¶nh cña mét x©u bÝt bÊt k× cho tr−íc cã ®é dµi 56. Bëi v©y cÇn ph¶i kiÓm tra xem y = eX(i,t-j)(x) hay kh«ng ®Ó biÕt liÖu X(i,t-j) cã thùc sù lµ kho¸ hay kh«ng. Ta kh«ng l−u tr÷ gi¸ trÞ X(i,t-j) nh−ng cã thÓ dÔ dµng tÝnh l¹i nã tõ X(i,0) b»ng c¸ch lÆp t-j lÇn hµm g. Oscar sÏ thùc hiÖn theo thuËt to¸n ®−îc m« t¶ trªn h×nh 3.7. Trang 20
  3. Vietebooks Nguyễn Hoàng Cương H×nh 3.7. PhÐp tèi −u ho¸ bé nhí - thêi gian trong DES. 1. TÝnh y1 = R(y) 2. for j = 1 to t do if yj = X(i,t-j) víi gi¸ trÞ i nµo ®ã then 3. 4. TÝnh X(i,t-j) tõ X(i,0) b»ng c¸ch lÆp t-j lÇn hµm g. if y = eX(i,t-j)(x) then 5. ®Æt K = X(i,t-j) vµ QUIT 6. TÝnh yj+1 = g(yj) B»ng c¸ch ph©n tÝch x¸c suÊt thµnh c«ng cña thuËt to¸n, cã thÓ chøng tá r»ng nÕu mt2 ≈ N = 256 th× x¸c suÊt ®Ó K = X(i,t-j) víi i, j nµo ®ã sÏ vµo kho¶ng 0,8m«i tr−êng/N. Thõa sè 0,8 tÝnh theo ®iÒu kiÖn kh«ng ph¶i tÊt c¶ c¸cX(i,t) ®Òu ph©n biÖt . §iÒu nµy gîi ý cho ta nªn lÊy m ≈ t ≈ N1/3 vµ x©y dùng kho¶ng N1/3 b¶ng, mçi b¶ng dïng mét hµm rót gän R kh¸c nhau. NÕu thùc hiÖn ®−¬c ®iÒu nµy th× yªu cÇu vÒ bé nhí lµ 112×N1/3 bÝt ( v× ta cÇn l−u tr÷ 2×N2/3 sè nguyªn, mçi sè cã 56 bÝt). Thêi gian tiÒn tÝnh to¸n dÔ dµng thÊy lµ cì O(N). ViÖc ph©n tÝch thêi gian ch¹y cña thuËt to¸n cã khã h¬n h¬n mét chót: Tr−íc hÕt ta thÊy r»ng, b−íc 3 cã thÓ ch¹y trong mét thêi gian kh«ng ®æi (sö dông phÐp m· hash) hoÆc trong tr−êng hîp xÊu nhÊt, b−íc 3 cã thÓ ch¹y víi thêi gian O(logm) khi dïng phÐp tmf kiÕm nhÞ ph©n. NÕu b−íc 3 kh«ng tho¶ m·n (tøc lµ phÐp t×m kiÕm kh«ng thµnh c«ng) th× thêi gian ch¹y lµ O(N2/3). C¸c ph©n tÝch chi tiÕt h¬n chøng tá r»ng, ngay c¶ khi tÝnh c¶ thêi gian ch¹y cña c¸c b−íc 4 vµ5 th× thêi gian ch¹y trung b×nh chØ t¨ng mét l−¬ng lµ h»ng sè. 3.6 Th¸m m∙ vi sai (DC). Ph−¬ng ph¸p DC do Biham vµ Shamir ®−a ra lµ mét ph−¬ng ph¸p tÊn c«ng DES rÊt næi tiÕng. §©y lµ mét phÐp tÊn c«ng víi b¶n râ chän läc. MÆc dï ph−¬ng ph¸p nµy kh«ng cho mét ph−¬ng ph¸p thùc tÕ ®Ó ph¸ DES 16 vßng th«ng dông, nh−ng nã cã thÓ thùc hiÖn thµnh c«ng trong viÖc ph¸ DES cã sè vßng m· ho¸ Ýt h¬n. Ch¼ng h¹n DES 8 vßng cã thÓ ph¸ ®−îc trong vßng vµi phót trªn mét m¸y tÝnh c¸ nh©n nhá. B©y giê ta sÏ m« t¶ nh÷ng ý t−ëng c¬ b¶n dïng trong kü thuËt nµy, ta cã thÓ bá qua phÐp ho¸ vÞ ban ®Çu IP vµ phÐp ho¸n vÞ ng−îc cña nã ( kh«ng Trang 21
  4. Vietebooks Nguyễn Hoàng Cương ¶nh h−ëng tíi viÖc ph©n tÝch m·). Nh− ®· nãi ë trªn, ta chØ xÐt h¹n chÕ DES n vßng víi n ≤ 16. Bëi vËy, víi c¸c ®iÒu kiÖn trªn, ta coi L0R0 lµ b¶n râ vµ LnRn lµ b¶n m· trong DES n vßng ( cÇn chó ý r»ng ta kh«ng cÇn ®¶o LnRn ). Ph−¬ng ph¸p DC xoay quanh viÖc so s¸nh kÕt qu¶ phÐp hoÆc - lo¹i trõ cña hai b¶n râ víi kÕt qu¶ cña phÐp hoÆc - lo¹i trõ cña hai b¶n m· t−¬ng øng. §¹i thÓ ta sÏ xÐt hai b¶n râ L0R0 vµL0*R0* víi gi¸ trÞ cña phÐp hoÆc - lo¹i trõ L0'R0' = L0R0 ⊕L0*R0*. Trong phÇn nµy ta sÏ sö dông ký hiÖu ( ' ) ®Ó chØ phÐp hoÆc - lo¹i trõ (XOR) cña hai x©u bÝt. §Þnh nghÜa 3.1 Gi¶ sö Sj lµ mét hép S (1≤ j ≤ 8 ). XÐt mét cÆp ®· s¾p xÕp cña c¸c x©u bÝt ®é dµi 6 ( ký hiÖu lµ Bj, Bj*). Ta nãi r»ng XOR vµo (cña Sj ) lµ Bj ⊕Bj* vµ XOR ra ( cña Sj ) lµ Sj(Bj) ⊕ Sj(Bj*). Chó ý r»ng XOR vµo lµ mét x©u bÝt cã ®é dµi 6 vµ XOR ra lµ mét x©u bÝt cã ®é dµi 4. §Þnh nghÜa 3.2 Víi bÊt kú Bj' ⊕ (Z2)6, ta ®Þnh nghÜa tËp ∇(Bj') gåm c¸c cÆp ®−îc s¾p xÕp (Bj,Bj*) cã XOR vµo lµ Bj'. DÔ dµng thÊy r»ng mét tËp ∇(Bj') bÊt kú ®Òu chøa 26 = 64 cÆp vµ ∇(Bj') = {(Bj,Bj ⊕Bj' ) : Bj ∈(Z2)6} Víi mçi cÆp trong ∇(Bj') ta cã thÓ tÝnh XOR ra cña Sj vµ lËp b¶ng ph©n bè kÕt qu¶. Cã 64 XOR ra ph©n bè trong 24 = 16 gi¸ trÞ cã thÓ. TÝnh kh«ng ®Òu cña c¸c ph©n bè nµy lµ c¬ së cho phÐp tÊn c«ng. VÝ dô 3.1. Gi¶ sö xÐt hép S ®Çu tiªn S1 vµ XOR vµo 110100, khi ®ã: ∇(110100) = {(000000,110100), (000001,110100), . . . ,(111111,110100)} Víi mçi cÆp ®−îc s¾p trong tËp∇(110100) ta tÝnh XOR ra cña S1. VÝ dô S1(000000) = E16 = 1110 vµ S1(110100) = 916 = 1001, bëi vËy XOR ®èi víi cÆp (000000,110100) lµ 0111. NÕu lµm c«ng viÖc nµy cho tÊt c¶ 64 cÆp trong ∇(110100) th× ta sÏ thu ®−îc ph©n bè sau cña c¸c XOR ra: Trang 22
  5. Vietebooks Nguyễn Hoàng Cương 0000 0001 0010 0011 0100 0101 0110 0111 0 8 16 6 2 0 0 12 1000 1001 1010 1011 1100 1101 1110 1111 6 0 0 0 0 8 0 6 Trong vÝ dô 3.1 chØ cã 8 trong 16 XOR ra cã thÓ xuÊt hiÖn trªn thùc tÕ. VÝ dô cô thÓ nµy cã ph©n bè rÊt kh«ng ®Òu. Nãi chung nÕu ta cè ®Þnh mét hép S lµ Sj vµ mét XOR vµo Bj' th× trung b×nh cã kho¶ng 75-80% c¸c XOR ra lµ cã thÓ xuÊt hiÖn. §Ó m« t¶ vµ ®−a ra c¸c ph©n bè nµy, ta cÇn ph¶i cã thªm mät sè kh¸i niÖm thÝch hîp. Sau ®ã lµ mét sè ®Þnh nghÜa. §Þnh nghÜa 3.3 Víi 1 ≤ j ≤ 8 vµ víi c¸c x©u bÝt Bj' cã ®é dµi 6 cßn Cj' cã ®é dµi 4, ta ®Þnh nghÜa: INj(Bj',Cj') = { Bj ∈(Z2)6 : Sj(Bj) ⊕ Sj(Bj ⊕ Bj') = Cj'} vµ Nj(Bj',Cj') = | INj(Bj',Cj' ) |. Nj(Bj',Cj' ) lµ sè c¸c cÆp cã XOR vµo b»ng Bj' vµ cã XOR ra b»ng Cj' víi hép Sj. C¸c cÆp thùc tÕ cã c¸c XOR vµo x¸c ®Þnh vµ t¹o nªn c¸c XOR ra x¸c ®Þnh cã thÓ nhËn ®−îc tõ tËp INj(Bj',Cj' ). Ta thÊy r»ng, tËp nµy cã thÓ ®−îc ph©n thµnh Nj(Bj',Cj' )/2 cÆp, mçi cÆp cã sè XOR vµo b»ng Bj'. Chó ý r»ng ph©n bè ®−îc lËp b¶ng ë trong vÝ dô 3.1 chøa c¸c gi¸ trÞ N1(110100,C1'), C1' ∈(Z2)4. C¸c tËp IN1(110100,C1') ®−îc liÖt kª trªn h×nh 3.8. Víi mçi hép trong 8 hép S cã 64 XOR vµ cã thÓ. Bëi vËy cã thÓ tÝnh ®−îc tÊt c¶ 512 ph©n bè vµ dÔ dµng dïng m¸y tÝnh ®Ó lËp b¶ng c¸c ph©n bè nµy. CÇn nhí l¹i r»ng, ®Çu vµo cña c¸c hép S ë vong thø i lµ B = E ⊕J, trong ®ã E = E(Ri-1) lµ mét hµm më réng cña Ri-1 vµ J = Ki lµ c¸c bÝt kho¸ cña vßng thø i. B©y giê sè XOR vµo (cho tÊt c¶ 8 hép) cã thÓ ®−îc tÝnh nh− sau: B ⊕ B* = (E ⊕ J) ⊕ (E* ⊕ J) = E ⊕ E* Trang 23
  6. Vietebooks Nguyễn Hoàng Cương Cã thÓ thÊy m«t ®iÒu rÊt quan träng lµ XOR vao kh«ng phô thuéc vµo c¸c bÝt kho¸ J ( tuy nhiªn ch¾c ch¾n XOR ra sÏ phô thuéc vµo c¸c bÝt khãa nµy. H×nh 3.8. C¸c x©u vµo cã thÓ víi XOR vµo lµ 110100. C¸c XOR ra C¸c x©u vµo cã thÓ 0000 0001 000011,001111,011110,011111, 101010,101011,110111,111011 0010 000100,000101,001110,010001, 010010,010100,011010,011011, 100000,100101,010110,101110, 101111,110000,110001,111010 0011 000001,000010,010101,100001, 110101,110110 0100 010011,100111 0101 0110 0111 000000,001000,001101,010111 011000,011101,100011,101001 101100,110100,111001,111100 1000 001001,001100,011001,101101 111000,111101 1001 1010 1011 1100 1101 000110,010000,010110,011100 100010,100100,101000,110010 1110 1111 000111,001010,001011,001100 111110,111111 Ta viÕt c¸c E,B, vµ J lµ mét d·y ghÐp kÕ tiÕp 8 x©u 6 bÝt: B = B1 B2 B3 B4 B5 B6 B7 B8 E = E1 E2 E3 E4 E5 E6 E7 E8 J = J1 J2 J3 J4 J5 J6 J7 J8 Trang 24
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2