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 5

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

Thêm vào BST

Báo xấu

62
lượt xem 5
download

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

Kết quả sau đây là một hệ quả trực tiếp rút ra từ suy luận ở trên. Định lý 3.1 Giả sử Ej và Ej* là hai xâu vào của hộp Sj còn XOR ra của Sj là Cj. Kí hiệu Ej' = Ej ⊕ Ej* .

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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 5

Vietebooks Nguyễn Hoàng Cương vµ viÕt B*, E*,J* theo c¸ch t−¬ng tù. NÕu biÕt c¸c gi¸ trÞ Ej vµ Ej* víi j nµo ®ã, 1 ≤ j ≤ 8, vµ gi¸ trÞ XOR ra ( cña Sj ) lµ Cj' = Sj(Bj) ⊕ Sj(Bj*). Khi ®ã ch¾c ch¾n r»ng: Ej ⊕ Jj ∈ INj(Ej',Cj' ) trong ®ã E j' = Ej ⊕Ej . * Gi¶ sö ta x¸c ®Þnh tËp testj nh− sau: §Þnh nghÜa 3.4. Gi¶ sö Ej vµ Ej* lµ c¸c x©u bÝt ®é dµi 6 vµ Cj' lµ x©u bÝt ®é dµi 4. Ta ®Þnh nghÜa: testj(Ej , Ej*, Cj' ) = {Bj ⊕ Ej : Bj ∈INj(Ej',Cj')} trong ®ã Ej' = Ej Ej* NghÜa lµ lÊy XOR Ej víi mçi phÇn tö cña tËp INj(Ej',Cj'). KÕt qu¶ sau ®©y lµ mét hÖ qu¶ trùc tiÕp rót ra tõ suy luËn ë trªn. §Þnh lý 3.1 Gi¶ sö Ej vµ Ej* lµ hai x©u vµo cña hép Sj cßn XOR ra cña Sj lµ Cj. KÝ hiÖu Ej' = Ej ⊕ Ej* . Khi ®ã c¸c bÝt kho¸ Jj sÏ n»m trong tËp testj (Ej, Ej* , Cj'). NhËn thÊy r»ng cã ®óng Nj(Ej',Cj' ) x©u bÝt ®é dµi 6 trong tËp testj(Ej,Ej*,Cj'); gi¸ trÞ ®óng cña Jj ph¶i lµ mét trong c¸c kh¶ n¨ng nµy. VÝ dô 3.2. Gi¶ sö E1 = 000001, E1* = 110101 vµ C1' = 1101. V× N1(110100,1101) = 8 nªn cã ®óng 8 x©u bÝt trong tËp test1(000001,110101,1101). Tõ h×nh 3.8 ta thÊy r»ng: IN1(110100,1101) = {000110,010000,010110,011100,100010,100100,101000,110010} Bëi vËy test1(000001,110101,1101) = {000111,010001,010111,011101,100011,100101,101001,110011}. NÕu ta cã mét bé ba E1,E1*,C1' thø hai nh− vËy th× cã thÓ thu ®−îc tËp test1 thø hai chøa c¸c gi¸ trÞ cã thÓ chøa c¸c bÝt kho¸ trong J1. Gi¸ trÞ ®óng cña J1 ph¶i n»m trong phÇn giao cña hai tËp nµy. NÕu ta cã vµi bé ba nh− vËy th× cã thÓ nhanh chãng x¸c ®Þnh ®−îc c¸c bÝt kho¸ trong J1. Ph−¬ng ph¸p ®¬n gi¶n ®Ó lµm ®iÒu nµy lµ t¹o mét d·y 64 bé ®Õm biÓu diÔn 64 kh¶ n¨ng cña 6 bÝt kho¸ trong J1 . Bé ®Õm sÏ ®Õm t¨ng mçi khi c¸c bÝt kho¸ t−¬ng øng xuÊt Trang 25
Vietebooks Nguyễn Hoàng Cương hiÖn trong tËp test1 víi mét bé ba cô thÓ. Víi t bé ba, ta tin r»ng sÏ t×m ®−îc bé ®Õm duy nhÊt cã gi¸ trÞ t t−¬ng øng víi gi¸ trÞ ®óng cña c¸c bÝt kho¸ trong J1. 3.6.1. TÊn c«ng DES 3 vßng B©y giê ta xÐt xem viÖc øng dông c¸c ý t−ëng cña phÇn tr−íc trong phÐp tÊn c«ng b¶n râ chän läc lªn mét hÖ DES 3 vßng. Ta b¾t ®Çu »ng mét cÆp c¸c b¶n râ vµ b¶n m· t−¬ng øng L0R0, L0*R0*,L3R3, vµ L3*R3* . Cã thÓ biÓu thÞ R3 nh− sau: R3 = L2 ⊕ f (R2,K3) = R1 ⊕ f (R2,K3) = L0 ⊕ f (R0,K1) ⊕ f (R2,K3) BiÓu diÔn R3* theo c¸ch t−¬ng tù nh− vËy R3' = L0' ⊕ f (R0,K1) ⊕ f(R0*,K1) ⊕ f (R2,K3) ⊕ f (R2*,K3) B©y giê, gi¶ sö ta ®· chän ®−îc c¸c b¶n râ sao cho R0 = R0* , nghÜa lµ ®Ó R0' = 00. . .0 * Khi ®ã f (R0,K1) = f (R0 ,K1) vµ nh− vËy: R3' = L0' ⊕ f(R2,K3) ⊕ f(R2*,K3). Lóc nµy R3' ®· biÕt v× cã thÓ tÝnh ®−îc nã tõ hai b¶n m·. L0' còng ®· biÕt do cã thÓ tÝnh ®−îc nã tõ hai b¶n râ. §iÒu nµy cã nghi· lµ ta cã thÓ tÝnh f(R2,K3)⊕f(R2*,K3) tõ ph−¬ng tr×nh: f(R2,K3)⊕f(R2*,K3) = R3' ⊕ L0' B©y giê ta cã f(R2,K3) = P(C) vµ f(R2*,K3) = P(C*), trong ®ã C vµ C* ký hiÖu t−¬ng øng 2 d·y ra cña 8 hép S ( h·y nhí l¹i r»ng P lµ mét phÐp ho¸n vÞ cè ®Þnh c«ng khai ). Bëi vËy: P(C) ⊕ P(C*) = R3' ⊕ L0' vµ do ®ã: C' = C ⊕ C* = P-1(R3' ⊕ L0') (3.1) §©y lµ XOR ra cña 8 hép S ë vßng thø 3. Trang 26
Vietebooks Nguyễn Hoàng Cương B©y giê R2 = L3 vµ R2* = L3* còng ®· biÕt ( chóng lµ mét phÇn cña c¸c b¶n m·). Bëi vËy, cã thÓ tÝnh E = E(L3) (3.2) E* = E(L3*) vµ (3.3) b»ng c¸ch dïng hµm më réng E ®−îc biÕt c«ng khai. §©y lµ c¸c mÉu vµo c¸c hét S ë vßng thø 3. Nh− thÕ ta ®· biÕt E vµ E* vµ C ' cña vßng thø 3 vµ cã thÓ thùc hiÖn ( nh− ë phÇn tr−íc) ®Ó x©y dùng c¸c tÖp test1, . .., test8 chøa c¸c gi¸ trÞ cã thÓ cña c¸c bÝt trong J1,. . .,J8 . M« t¶ d¹ng gi¶ m· cña thuËt to¸n nµy ®−îc cho ë h×nh 3.9. H×nh 3.9. C¸ch tÊn c«ng DC lªn DES 3 vßng. §Çu vµo L0R0,L0*R0* , L3R3 vµ L3*R3*, trong ®ã R0 = R0* 1. TÝnh C ' = P-1(R3' ⊕ L0') 2. TÝnh E = E(L3) vµ E* = E(L3*) 3. For j = 1 to 8 do TÝnh testj(Ej, Ej*, Cj') Trong ph−¬ng ph¸p tÊn c«ng nµy sÏ ph¶i dïng mét sè bé ba E, E*,C ' nh− vËy, Ta ph¶i thiÕt lËp 8 d·y bé ®Õm vµ nhê vËy x¸c ®Þnh ®−îc 48 bÝt trong kho¸ K3 ( kho¸ cña vßng thø 3). Sau ®ã tÝnh 56 bÝt trong khãa theo c¸ch t×m kiÕm vÐt c¹n trong 28 = 256 kh¶ n¨ng cho 8 bÝt kho¸ cßn l¹i. Ta sÏ xem xÐt mét vÝ dô ®Ó minh ho¹. VÝ dô 3.3. Gi¶ sö ta cã 3 cÆp c¸c b¶n râ vµ c¸c b¶n m·, trong ®ã c¸c b¶n râ cã c¸c phÐp XOR x¸c ®Þnh, chóng ®−îc m· ho¸ b»ng cïng mét kho¸. §Ó cho gän ta sÏ biÓu thÞ d−íi d¹ng m· Hexa: B¶n râ B¶n m· 748502CD38451097 03C70306D8AO9F10 3874756438451097 78560A960E6D4CB 486911026ACDFF31 45FA285BE5ADC730 375BD31F6ACDFF31 134F7915AC253457 357418DA013FEC86 D8A31B2F28BBC5CF 12549847013FEC86 0F317AC2B23CB944 Trang 27
Vietebooks Nguyễn Hoàng Cương Tõ cÆp ®Çu tiªn, tÝnh c¸c ®Çu vµo cña hép S ( cho vßng 3 ) theo c¸c ph−¬ng tr×nh (3.2) vµ (3.3). Ta cã: E = 000000000111111000001110100000000110100000001100 E* = 101111110000001010101100000001010100000001010010 XOR ra cña c¸c hép S ®−îc tÝnh theo ph−¬ng tr×nh (3.1) lµ: C' = 10010110010111010101101101100111 Tõ cÆp thø hai, ta tÝnh ®−îc c¸c ®Çu vµo cña c¸c hép S lµ: E = 101000001011111111110100000101010000001011110110 E* = 000001011110100110100010101111110101011000000100 vµ XOR ra cña c¸c hép S lµ: C' = 11010101011101011101101100101011 TiÕp theo, lËp b¶ng c¸c gi¸ trÞ trong 8 d·y bé ®Õm cho tõng cÆp. Minh ho¹ thñ tôc nµy víi d·y bé ®Õm cho J1 theo cÆp ®Çu tiªn. Trong cÆp nµy ta cã: E' = 101111 vµ C' = 1001. Khi ®ã tËp: IN1(101111,1001) = {000000,000111,101000,101111} v× E1 = 000000 nª ta cã: J1∈test1(000000,101111,1001) = {000000,000111,101000,101111} Bëi vËy ta sÏ t¨ng c¸c gi¸ trÞ 0,7,40 vµ 47 trong d·y bé ®Õm cho J1. B©y giê sÏ tr×nh bµy c¸c b¶ng cuèi cïng. NÕu coi mét x©u bÝt ®é dµi 6 nh− biÓu diÔn nhÞ ph©n cña mét sè nguyªn n»m gi÷a 0 vµ 63 th× 64 gi¸ trÞ t−¬ng øng lµ 0,1,. . . ,63. C¸c m¶ng bé ®Õm sÏ nh− sau: J1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Trang 28
Vietebooks Nguyễn Hoàng Cương J2 0 0 0 1 0 3 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 2 0 0 0 J3 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 J4 3 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 J5 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 2 0 J6 1 0 0 1 1 0 0 3 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 J7 0 0 2 1 0 3 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 2 0 0 0 2 0 0 0 0 1 2 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 Trang 29
Vietebooks Nguyễn Hoàng Cương J8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 3 0 0 0 0 1 0 0 0 0 0 0 0 0 1 Trong sè 8 m¶ng bé ®Õm ( trong 8 mangt ë trªn) cã duy nhÊt mét bé ®Õm cã gi¸ trÞ 3, c¸c vÞ trÝ cña c¸c bé ®Õm nµy sÏ ®−îc x¸c ®Þnh c¸c bÝt kho¸ trong J1,.. ., J8. C¸c vÞ trÝ nµy t−¬ng øng lµ 47,5,19,0,24,7,7,49. §æi c¸c sè nguyªn sang d¹ng nhÞ ph©n ta nhËn ®−îc J1, . . .,J8: J 1 = 101111 J2 = 000101 J3 = 010011 J4 = 000000 J5 = 011000 J6 = 000111 J7 = 000111 J8 = 110001 B©y giê ta cã thÓ x©y dùng 48 bÝt cña kho¸ b»ng c¸ch nh×n vµo b¶ng kho¸ ®èi víi vßng 3. Khi ®ã K cã d¹ng: 0001101 0110001 01?01?0 1?00100 0101001 0000??0 111?11? ?100011 ë ®©y ta ®· bá qua c¸c bÝt kiÓm tra chÆn lÎ vµ"?" chØ bÝt kho¸ ch−a biÕt. Khãa ®Çy ®ñ ( ë d¹ng hexa gåm c¶ bÝt kiÓm tra chÆn lÎ) lµ: 1A624C89520DEC46 3.6.2. TÊn c«ng DES 6 vßng Trong môc nµy ta sÏ më réng c¸c ý t−ëng ë trªn cho phÐp tÊn c«ng x¸c suÊt ®èi DES 6 vßng. ý t−ëng ë ®©y lµ ph¶i chän cÈn thËn mét acÆp b¶n râ víi mét phÐp XOR chØ ra tr−íc råi x¸c ®Þnh c¸c x¸c suÊt cña mét d·y x¸c ®Þnh c¸c XOR qua c¸c vong m·. B©y giê ta sÏ ®Þnh nghi· mét kh¸i niÖm quan träng. §Þnh nghÜa 3.5. Cho n ≥ 1 lµ mét sè nguyªn. Mét ®Æc tr−ng n vßng lµ mét danh s¸ch cã d¹ng: L0',R0',L1',R1',p1. . . Ln',Rn',pn Trang 30