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

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.
Nội dung trích xuất từ tài liệu:
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 4Vietebooks 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«ngphô 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Êtcñ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Ýttrong 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íimét cÆp râ - m· cho tr−íc, h·y thö tÊt c¶ 256 kho¸ cô thÓ. §iÒu nµy kh«ngyª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) ®−îcs¾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ã dungl−îng lín vµ cÇn thêi gian tÝnh to¸n tr−íc lín ( chó ý lµ quan ®iÓm nµykh«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Ðtc¹n. Ph−¬ng ph¸p nµy chØ cã lîi khi cÇn t×m nhiÒu kho¸ trong mét kho¶ngthê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¬nphÐ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µnhmé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ö xlµ 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étx©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Ýtsab g 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µi56 ®−î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 19Vietebooks 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¾pxÕ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). OscarcÇn ph¶i x¸c ®Þnh K vµ anh ta sÏ x¸c ®Þnh ®−îc nÕu K n»m trong t cét ®Çucñ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¶ngT. 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Öuhµ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ótgä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 ¶nhcñ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 xemy = 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. Takh«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»ngc¸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 20Vietebooks Nguyễn Hoàng CươngH×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øngtá 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µokho¶ng 0,8m«i tr−êng/N. Thõa sè 0,8 tÝnh theo ®iÒu kiÖn kh«ng ph¶i ...