Đo độ khếch tán của mã khối AES và Aria dựa trên số điểm bất động

Nghiên cứu khoa học công nghệ<br /> <br /> <br /> ®o §é KHUÕCH T¸N CñA M· KhèI AES vµ ARIA<br /> DùA TR£N Sè §IÓM BÊT §éNG<br /> TrÇn ThÞ L­¬ng*, Vò ®×nh Thu**, TrÇn ®øc sù**<br /> Tóm tắt: Bài báo nêu các phương pháp đo độ khuếch tán của mã khối dựa<br /> trên ảnh hưởng thác đổ, ảnh hưởng thác đổ chặt, thuộc tính đầy đủ, số nhánh và<br /> điểm bất động, trong đó phương pháp dựa trên điểm bất động được tập trung<br /> nghiên cứu. Từ đó, áp dụng các phương pháp dựa trên ảnh hưởng thác đổ, ảnh<br /> hưởng thác đổ chặt, thuộc tính đầy đủ để đo độ khuếch tán của mã khối AES,<br /> DES. Sau đó, độ khuếch tán của mã khối AES và ARIA được đo dựa trên số điểm<br /> bất động. Từ các kết quả thực nghiệm thu được, bài báo đánh giá tính hiệu quả<br /> của sự khuếch tán trong biến đổi tuyến tính của các mã khối AES và ARIA.<br /> Tõ khãa: TÇng khuÕch t¸n, §iÓm bÊt ®éng, ¶nh h­ëng th¸c ®æ, ¶nh h­ëng th¸c ®æ chÆt, Sè nh¸nh.<br /> <br /> 1. Më §ÇU<br /> C¸c m· khèi hiÖn ®¹i ®Òu tu©n thñ hai nguyªn lý thiÕt kÕ do Claude Shannon ®­a ra<br /> n¨m 1949, ®ã lµ nguyªn lý x¸o trén (confusion) vµ nguyªn lý khuÕch t¸n (diffusion). Hai<br /> nguyªn lý nµy nh»m lµm cho qu¸ tr×nh t×m kiÕm mèi quan hÖ thèng kª gi÷a b¶n gèc vµ b¶n<br /> m· trë nªn “kh«ng thÓ”. Bµi b¸o nµy tËp trung vµo viÖc ®¸nh gi¸ tÇng khuÕch t¸n cña m·<br /> khèi trong viÖc ®¶m b¶o ®é khuÕch t¸n cho m· khèi. Cã rÊt nhiÒu ph­¬ng ph¸p nghiªn cøu,<br /> ®¸nh gi¸ ®é khuÕch t¸n cña m· khèi nh­: ph­¬ng ph¸p dùa trªn møc ®é ¶nh h­ëng th¸c ®æ<br /> (AC)[2], møc ®é ¶nh h­ëng th¸c ®æ chÆt (SAC)[2], thuéc tÝnh ®Çy ®ñ[2], ph­¬ng ph¸p dùa<br /> trªn sè nh¸nh[1]. Vµo th¸ng 7 n¨m 2010, tiÕn sÜ Muhammad Reza Z’aba [1] ®· ®Ò xuÊt<br /> mét ph­¬ng ph¸p kh¸c ®Ó ®o ®é khuÕch t¸n cña m· khèi cã tªn lµ “Ph­¬ng ph¸p ®o ®é<br /> khuÕch t¸n b»ng c¸ch ®Õm sè ®iÓm bÊt ®éng”. Tõ ®ã, cã thªm mét ph­¬ng ph¸p kh¸c ®Ó ®o<br /> ®é khuÕch t¸n cña m· khèi, ®ã lµ dùa trªn sè ®iÓm bÊt ®éng cña tÇng khuÕch t¸n.<br /> Bµi b¸o nµy tr×nh bµy c¸c ph­¬ng ph¸p ®o ®é khuÕch t¸n cña m· khèi, trong ®ã tËp<br /> trung vµo ph­¬ng ph¸p dùa trªn ®iÓm bÊt ®éng vµ ¸p dông ph­¬ng ph¸p nµy ®Ó ®o ®é<br /> khuÕch t¸n cña m· khèi AES vµ ARIA.<br /> 2. MéT Sè KH¸I NIÖM, Ký HIÖU<br /> <br /> 2.1. ¶nh h­ëng th¸c ®æ<br /> Sau n¨m 2000, dù ¸n NESSIE (sau khi NIST tuyÓn chän xong AES) ®· ®­a ra<br /> tiªu chuÈn vÒ møc ®é ¶nh h­ëng th¸c ®æ (The avalanche effect - AC) [2] ®Ó ®¸nh<br /> gi¸ c¸c m· khèi. Dù ¸n NESSIE ®¸nh gi¸ thèng kª m· khèi, trong ®ã kiÓm tra møc<br /> ®é của tiêu chuẩn AC, ký hiệu là da. XÐt vect¬ x = (x1,…,xn)  (GF(2))n vµ vect¬<br /> x(i) (GF(2))n ®¹t ®­îc b»ng c¸ch lÊy phÇn bï bit thø i cña vector x (víi i = 1,...,n ).<br /> - Hµm tháa m·n tiÓu chuÈn AC:<br /> Hµm f: (GF (2)) n  (GF (2)) m ®­îc gäi lµ tháa m·n tiªu chuÈn ¶nh h­ëng th¸c<br /> ®æ nÕu trung b×nh cã ½ c¸c bit ra thay ®æi mçi khi mét bit vµo ®¬n ®­îc thay ®æi<br /> hay:<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 97<br />  Kỹ thuật điện tử và Khoa học máy tính<br /> <br /> 1 m<br />  w( f ( x i  f ( x))  (1)<br /> 2n x( GF (2)) n 2<br /> víi i  1  n vµ träng sè Hamming w(x) cña x lµ sè c¸c thµnh phÇn kh¸c 0 cña vect¬<br /> x.<br /> 2.2. ¶nh h­ëng th¸c ®æ chÆt<br /> Dù ¸n NESSIE còng ®· ®­a ra tiªu chuÈn vÒ møc ®é ¶nh h­ëng th¸c ®æ chÆt<br /> (The strict avalanche effect - SAC) ®Ó ®¸nh gi¸ c¸c m· khèi [2]. Dù ¸n NESSIE<br /> ®¸nh gi¸ thèng kª m· khèi, trong ®ã kiÓm tra møc ®é cña tiªu chuÈn SAC, ký hiÖu<br /> lµ dsa. Hµm f: (GF(2))n → (GF(2))m ®­îc gäi lµ tho¶ m·n tiªu chuÈn SAC nÕu mçi<br /> bit ra thay ®æi víi x¸c suÊt 1/2 mçi khi mét bit vµo ®¬n ®­îc thay ®æi, hay víi mäi<br /> i = 1, ..., n vµ j = 1 , ..., m, ta cã:<br /> Pr( ( f (x(i)))j ≠ ( f (x))j ) = ½ (2)<br /> 2.3. Thuéc tÝnh ®Çy ®ñ<br /> Thuéc tÝnh nµy lµ thuéc tÝnh mong muèn cña mçi thuËt to¸n m· hãa. Gi¶ sö<br /> r»ng nÕu chØ cã mét vµi bit ®Çu ra phô thuéc vµo mét bit ®Çu vµo th× b»ng c¸ch<br /> quan s¸t mét sè l­îng ®¸ng kÓ cña c¸c cÆp ®Çu ra, ®Çu vµo, ng­êi th¸m m· cã thÓ<br /> ph¸t hiÖn ®­îc mèi quan hÖ thèng kª vµ sö dông th«ng tin nµy ®Ó t×m ®­îc khãa.<br /> Dù ¸n NESSIE ®· ®­a ra tiªu chuÈn vÒ møc ®é cña thuéc tÝnh ®Çy ®ñ (the<br /> completeness property)[2], ký hiÖu lµ dc. Hµm f: (GF(2))n  (GF(2))m cña n bit<br /> vµo vµ m bit ra ®­îc gäi lµ tháa m·n thuéc tÝnh ®Çy ®ñ nÕu mçi bit ra phô thuéc<br /> vµo mçi bit vµo, hay víi mäi vµ ta ®­îc bit ra thø j phô thuéc<br /> vµo bit vµo thø i tøc lµ: tån t¹i sao cho , ë ®©y cã<br /> nghÜa lµ tån t¹i vect¬ sao cho khi thay ®æi bit vµo thø i th× sÏ lµm<br /> thay ®æi bit ra thø j.<br /> 2.4. Sè nh¸nh cña biÕn ®æi tuyÕn tÝnh<br /> Sè nh¸nh (branch number) cña mét biÕn ®æi tuyÕn tÝnh L ®­îc ký hiÖu lµ B(L),<br /> lµ sè tèi thiÓu cña hép S ho¹t ®éng trong hai vßng liªn tiÕp bÊt kú cña mét m· khèi<br /> cã cÊu tróc SPN [1]. Trong ®ã, mét hép S song ¸nh ®­îc gäi lµ ho¹t ®éng nÕu c¶<br /> hai ®Çu vµo vµ ®Çu ra cña nã ®Òu kh¸c 0 trong mét ®Æc tr­ng tuyÕn tÝnh hoÆc l­îng<br /> sai. Sè nh¸nh ®­îc tÝnh nh­ sau: Gi¶ sö Z=(Z0, Z1,…,Zm-1) lµ mét khèi gåm mb bit<br /> ®­îc t¹o thµnh b»ng c¸ch kÕt hîp m tõ, mçi tõ gåm b bit. Gi¶ sö<br /> Γ Z = Γ Z 0 ,Γ Z 1 ,...,Γ Z m -1 ký hiÖu vect¬ nhÞ ph©n ®é dµi m. Trong ®ã  Z  1 nÕu Zi<br /> i<br /> <br /> <br /> kh¸c kh«ng vµ b»ng 0 nÕu Zi b»ng 0. Gi¶ sö wt ( Z ) ®Þnh nghÜa lµ träng sè Hamming, sè<br /> nh¸nh cña L ký hiÖu bëi B(L) ®­îc m« t¶ nh­ sau:<br /> B(L) = min{ wt ( Z ) + wt ( X ) : Z 0 vµ X = L(Z)} (3)<br /> trong ®ã, B(L)  m+1.<br /> <br /> <br /> <br /> 98 T.T.Lương, V.Đ.Thu, T.Đ.Sự, “ Đo độ khuyếch tán… dựa trên số điểm bất động.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Sè nh¸nh B(L) lµ tèi ­u nÕu B(L)= m+1, m· tuyÕn tÝnh ®­îc g¾n víi L sÏ cã<br /> kho¶ng c¸ch tèi thiÓu cao nhÊt. Trong thùc tÕ, ®Ó ®¹t ®­îc m· tuyÕn tÝnh cã kho¶ng<br /> c¸ch tèi thiÓu cao nhÊt, ng­êi ta x©y dùng m· ®­îc gäi lµ m· MDS (Maximum<br /> Distance Separable) - M· t¸ch cã kho¶ng c¸ch cùc ®¹i.<br /> 2.5. §iÓm bÊt ®éng trong biÕn ®æi tuyÕn tÝnh [1]<br /> XÐt c¸c gi¸ trÞ b - bit nh­ lµ c¸c phÇn tö thuéc tr­êng . Ký hiÖu S lµ tËp tÊt<br /> m<br /> c¶ c¸c vect¬ trong víi ®é dµi lµ m ®­îc ký hiÖu lµ F2 b . §Þnh nghÜa<br /> A= lµ ma trËn kh«ng suy biÕn víi c¸c phÇn tö thuéc , lµ ma trËn biÓu<br /> diÔn cña mét biÕn ®æi tuyÕn tÝnh L trªn c¸c phÇn tö cña S. Tr­êng lµ mét tËp<br /> con cña . BiÕn ®æi tuyÕn tÝnh L ¸nh x¹ mét phÇn tö<br /> tíi mét phÇn tö .<br /> Víi X = AZ ®­îc biÓu diÔn nh­ sau:<br /> <br /> <br /> <br /> = (4)<br /> <br /> <br /> <br /> <br /> trong ®ã, vµ .<br /> Gi¶ sö biÓu diÔn ma trËn cì dùa trªn ma trËn ®¬n vÞ<br /> trong ®ã I(0) = I. C¸c phÇn tö cña ma trËn I(l) ®­îc x¸c ®Þnh bëi tham sè<br /> dÞch vßng , trong ®ã . Ch¼ng h¹n, ma trËn<br /> I(1) vµ I(2) víi m=4 ®­îc biÓu diÔn nh­ sau:<br /> <br /> <br /> <br /> ,<br /> <br /> TËp tÊt c¶ c¸c ®iÓm bÊt ®éng cña mét biÕn ®æi tuyÕn tÝnh L ®­îc biÓu diÔn bëi<br /> mét ma trËn kh«ng suy biÕn A, cã thÓ thu ®­îc b»ng c¸ch gi¶i ph­¬ng tr×nh sau [1]:<br /> (5)<br /> Víi l = 0, ph­¬ng tr×nh trªn trë thµnh (A – I) Z =0. NghiÖm cña ph­¬ng tr×nh nµy<br /> chÝnh lµ c¸c khèi ®Çu vµo mµ khi ®i qua biÕn ®æi tuyÕn tÝnh L sÏ cho khèi ®Çu ra<br /> kh«ng thay ®æi (b»ng chÝnh nã). Víi l > 0, nghiÖm cña ph­¬ng tr×nh trªn chÝnh lµ<br /> tËp c¸c khèi ®Çu vµo tháa m·n: khi ®i qua biÕn ®æi tuyÕn tÝnh L ta chØ cÇn quay<br /> vßng lb bit sang tr¸i cña khèi ®Çu vµo ®ã th× cã thÓ thu ®­îc khèi ®Çu ra. Gi¶ sö<br /> biÓu diÔn c¸c khèi ®Çu vµo tháa m·n ph­¬ng tr×nh (5), khi ®ã ta cã:<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 99<br />  Kỹ thuật điện tử và Khoa học máy tính<br /> <br /> (6)<br /> Sè c¸c khèi ®Çu vµo mµ tháa m·n mèi quan hÖ (5) ®­îc cho bëi:<br /> <br /> (7)<br /> víi . Khi ®ã, ®é khuÕch t¸n ®­îc ®o bëi ph­¬ng ph¸p dùa trªn<br /> sè ®iÓm bÊt ®éng ®­îc ký hiÖu bëi hÖ sè D(A), ®­îc ®Þnh nghÜa nh­ sau:<br /> (8)<br />  mb<br /> trong ®ã, 2  D( A)  1 vµ ma trËn A biÓu diÔn d¹ng ma trËn cña biÕn ®æi tuyÕn<br /> tÝnh L. HÖ sè D(A) biÓu thÞ sè trung b×nh cña c¸c khèi ®Çu vµo cña L mµ cã mèi<br /> quan hÖ tuyÕn tÝnh ®­îc cho bëi ph­¬ng tr×nh (5). Gi¸ trÞ D(A) lín nghÜa lµ cã<br /> nhiÒu khèi ®Çu vµo kh«ng thay ®æi bëi phÐp biÕn ®æi tuyÕn tÝnh L khi t¹o khèi ®Çu<br /> ra t­¬ng øng. T­¬ng tù nh­ vËy, gi¸ trÞ sè D(A) nhá nghÜa lµ cã nhiÒu khèi ®Çu vµo<br /> ®­îc thay ®æi hiÖu qu¶ bëi biÕn ®æi tuyÕn tÝnh L khi t¹o ra c¸c khèi ®Çu ra t­¬ng<br /> øng. Ngoµi ra, hÖ sè D(A) cßn biÓu thÞ møc ®é khuÕch t¸n tèt ®Õn ®©u, nghÜa lµ nã<br /> cã thÓ thÓ hiÖn biÕn ®æi tuyÕn tÝnh L thay ®æi hiÖu qu¶ nh­ thÕ nµo c¸c khèi ®Çu<br /> vµo khi t¹o khèi ®Çu ra t­¬ng øng. Víi ph­¬ng ph¸p ®o ®é khuÕch t¸n nµy, râ rµng<br /> lµ kh«ng cã sù khuÕch t¸n ®èi víi c¸c kiÓm bÊt ®éng.<br /> 3. MéT Sè KÕT QU¶<br /> 3.1. §o hÖ sè dsa, da, dc cña AES vµ DES<br /> - Sinh ngÉu nhiªn 10.000 b¶n râ ®Çu vµo cã ®é dµi khèi 128 bit, khãa cã ®é dµi<br /> 128 bit dùa trªn ng«n ng÷ java.<br /> - Víi mçi b¶n râ ®Çu vµo, ®¶o vÞ trÝ bÝt thø i tõ 0 ®Õn 128. XÐt kÕt qu¶ b¶n m·<br /> thu ®­îc tõ kÕt qu¶ ®¶o bit.<br /> - T×m tÊt c¶ c¸c phÇn tö d¹ng vect¬ x thuéc 10.000 b¶n râ ®Çu vµo sao cho khi<br /> ta cho x vµ x(i) lÇn l­ît lµ ®Çu vµo cña hµm m· hãa th× thu ®­îc ®Çu ra cña x kh¸c<br /> ®Çu ra cña x(i).<br /> - T×m tÊt c¶ c¸c phÇn tö d¹ng vect¬ x thuéc 10.000 b¶n râ ®Çu vµo sao cho khi ta<br /> thay ®æi bit vµo thø i cña vect¬ x thu ®­îc xi vµ cho xi lµ ®Çu vµo cña hµm m· hãa<br /> th× kÕt qu¶ ®Çu ra cã j bit ra kh¸c nhau.<br /> Thu ®­îc kÕt qu¶ cña phÐp ®o ®é khuÕch t¸n ¸p dông cho m· khèi AES vµ DES<br /> b»ng ph­¬ng ph¸p dùa trªn ¶nh h­ëng th¸c ®æ, ¶nh h­ëng th¸c ®æ chÆt, thuéc tÝnh<br /> ®Çy ®ñ nh­ b¶ng 1.<br /> B¶ng 1. B¶ng kÕt qu¶ c¸c hÖ sè dc, da, dsa cña AES vµ DES.<br /> HÖ sè AES DES<br /> HÖ sè dc 1 1<br /> HÖ sè da 0.99724 0.89872<br /> HÖ sè dsa 0.99273 0.88473<br /> <br /> <br /> <br /> 100 T.T.Lương, V.Đ.Thu, T.Đ.Sự, “ Đo độ khuyếch tán… dựa trên số điểm bất động.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> NhËn xÐt r»ng, hÖ sè da vµ dsa cña m· khèi AES lµ rÊt cao , nh­ vËy xÐt ®é<br /> khuÕch t¸n theo ph­¬ng diÖn vÒ ¶nh h­ëng th¸c ®æ vµ th¸c ®æ chÆt th× AES cã ®é<br /> khuÕch t¸n rÊt cao. C¸c hÖ sè nµy cña DES l¹i thÊp h¬n nhiÒu so víi AES, nªn ®é<br /> khuÕch t¸n cña DES theo hai tiªu chuÈn trªn lµ ch­a tháa m·n. Tuy nhiªn, c¶ AES<br /> vµ DES ®Òu tháa m·n thuéc tÝnh ®Çy ®ñ (dc =1).<br /> 3.2. §o ®é khuÕch t¸n cña AES vµ ARIA theo ph­¬ng ph¸p ®iÓm bÊt ®éng<br /> 3.2.1 Ma trËn khuÕch t¸n cña AES, ARIA<br /> §Ó ®o hÖ sè D(A) cÇn x¸c ®Þnh ®­îc ma trËn A trong biÕn ®æi tuyÕn tÝnh L cña<br /> tÇng khuÕch t¸n. Ma trËn A ®­îc x¸c ®Þnh tõ biÓu diÔn cña biÕn ®æi tuyÕn tÝnh L<br /> d­íi d¹ng: X=A.Z. Trong ®ã X lµ khèi ®Çu ra cña phÐp biÕn biÕn ®æi tuyÕn tÝnh qua<br /> tÇng khuÕch t¸n, Z lµ khèi ®Çu vµo cña tÇng khuÕch t¸n. Ma trËn A cña m· khèi<br /> AES qua phÐp biÕn ®æi tuyÕn tÝnh L ®­îc x¸c ®Þnh nh­ sau:<br /> <br />  2 0 0 0 0 3 0 0 0 0 1 0 0 0 0 1 <br />  <br />  1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 1 <br />  1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 <br />  <br />  3 0 0 0 0 2 0 0 0 0 1 0 0 0 0 1 <br />  0 0 0 1 2 0 0 0 0 3 0 0 0 0 1 0 <br />  <br />  0 0 0 1 1 0 0 0 0 2 0 0 0 0 3 0 <br />  <br /> <br /> 0 0 0 3 1 0 0 0 0 1 0 0 0 0 2 0<br />  (9)<br />  0 0 0 2 3 0 0 0 0 1 0 0 0 0 1 0 <br /> A   <br />  0 0 1 0 0 0 0 1 2 0 0 0 0 3 0 0 <br />  0 0 3 0 0 0 0 1 1 0 0 0 0 2 0 0 <br />  <br />  0 0 2 0 0 0 0 3 1 0 0 0 0 1 0 0 <br />  0 0 1 0 0 0 0 2 3 0 0 0 0 1 0 0 <br />  <br />  0 3 0 0 0 0 1 0 0 0 0 1 2 0 0 0 <br />  0 2 0 0 0 0 3 0 0 0 0 1 1 0 0 0 <br />  <br />  0 1 0 0 0 0 2 0 0 0 0 3 1 0 0 0 <br />  0 1 0 0 0 0 1 0 0 0 0 2 3 0 0 0 <br />  <br /> <br /> <br /> <br /> vµ ma trËn A cña m· khèi ARIA qua phÐp biÕn ®æi tuyÕn tÝnh L cña tÇng khuÕch<br /> t¸n lµ:<br />  0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 <br />  <br />  0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 1 <br />  0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 <br />  <br />  1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 <br />  1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 <br />  <br />  0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 1 <br />  1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 <br />   (10)<br />  0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 <br /> A   1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 <br />  <br />  1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 <br />  <br />  0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 <br />  0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 <br />  <br />  0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 <br />  1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0 <br />  <br />  1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 <br />  0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 <br /> <br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 101<br />  Kỹ thuật điện tử và Khoa học máy tính<br /> <br /> 3.2.2 KÕt qu¶ ®é khuÕch t¸n cña m· khèi AES<br /> Sè ®iÓm bÊt ®éng trong m· khèi AES ®­îc tÝnh tõ ma trËn A (9). Trong ®ã, ma<br /> trËn A cã sè chiÒu lµ m =16, phÐp biÕn ®æi tuyÕn tÝnh cña tÇng khuÕch t¸n thùc hiÖn<br /> trªn F28 (b = 8). Sè khèi ®Çu vµo cña m· khèi AES tháa m·n mèi quan hÖ tuyÕn<br /> tÝnh (5) ®­îc tÝnh bëi c«ng thøc (7) nh­ sau: LÇn l­ît tÝnh c¸c ma trËn A  I ( l ) víi l<br /> =0,1,..,15 vµ h¹ng cña chóng rank( A  I ( l ) ). Sau ®ã, ¸p dông c«ng thøc (7), thu<br /> ®­îc c¸c gi¸ trÞ , , …, nh­ trªn h×nh 1.<br /> <br /> <br /> <br /> <br /> H×nh 1. Sè ®iÓm bÊt ®éng cña AES theo gi¸ trÞ l<br /> ¸p dông c«ng thøc (8) thu ®­îc hÖ sè khuÕch t¸n theo ph­¬ng ph¸p ®iÓm bÊt<br /> ®éng cña m· khèi AES nh­ sau:<br /> <br /> <br /> <br /> L­u ý r»ng hÖ sè khuÕch t¸n cña AES tháa m·n: . Nh­<br /> ph©n tÝch trong phÇn 2.5, gi¸ trÞ D(A)AES nµy cµng nhá cµng tèt, gi¸ trÞ D(A)AES cµng<br /> nhá th× ®é khuÕch t¸n cña tÇng khuÕch t¸n trong AES cµng cao, gi¸ trÞ nµy tèt nhÊt<br /> khi nã b»ng 2-128. Gi¸ trÞ D(A)AES = 2-112,9944 lµ t­¬ng ®èi nhá, nªn tÇng khuÕch t¸n<br /> cña AES lµ kh¸ hiÖu qu¶, tuy nhiªn còng ch­a ph¶i tèt nhÊt.<br /> 3.2.3. KÕt qu¶ ®é khuÕch t¸n cña m· khèi ARIA<br /> Sè ®iÓm bÊt ®éng trong m· khèi ARIA ®­îc tÝnh tõ ma trËn A (10). Ma trËn A<br /> nµy còng cã sè chiÒu b»ng m=16, phÐp biÕn ®æi tuyÕn tÝnh cña tÇng khuÕch t¸n<br /> thùc hiÖn trªn F28 (b=8). T­¬ng tù c¸ch tÝnh cña AES, thu ®­îc 16 ma trËn d¹ng<br /> A  I ( l ) víi l =0,1,..,15. ¸p dông c«ng thøc (7), thu ®­îc c¸c gi¸ trÞ , , …,<br /> nh­ h×nh 2.<br /> <br /> <br /> <br /> <br /> 102 T.T.Lương, V.Đ.Thu, T.Đ.Sự, “ Đo độ khuyếch tán… dựa trên số điểm bất động.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> <br /> <br /> <br /> H×nh 2. Sè ®iÓm bÊt ®éng cña ARIA theo gi¸ trÞ l<br /> ¸p dông c«ng thøc (8) thu ®­îc hÖ sè khuÕch t¸n theo ph­¬ng ph¸p ®iÓm bÊt<br /> ®éng cña m· khèi ARIA nh­ sau:<br /> <br /> <br /> L­u ý r»ng, hÖ sè khuÕch t¸n cña ARIA còng tháa m·n:<br /> , gi¸ trÞ nµy tèt nhÊt khi nã b»ng 2-128. Tuy nhiªn, D(A)ARIA =<br /> 2-60 lµ t­¬ng ®èi lín so víi 2-128. §iÒu nµy ph¶n ¸nh r»ng, tÇng khuÕch t¸n cña<br /> ARIA ch­a hiÖu qu¶, vµ kh«ng tèt b»ng tÇng khuÕch t¸n cña AES.<br /> Tõ c¸c kÕt qu¶ trªn, thu ®­îc b¶ng tæng hîp cho c¸c biÕn ®æi tuyÕn tÝnh cña<br /> AES vµ ARIA nh­ b¶ng 2.<br /> B¶ng 2. KÕt qu¶ ®o ®é khuÕch t¸n cña m· khèi AES vµ ARIA<br /> b»ng ph­¬ng ph¸p ®Õm sè ®iÓm bÊt ®éng.<br /> M· khèi Rank(A-I(0)) D(A) FA( 0)<br /> AES 14 2-112.9944 216<br /> ARIA 7 2-60 272<br /> <br /> Tõ b¶ng 2, ta thÊy r»ng trong c¶ hai m· khèi AES vµ ARIA th× ma trËn (A-I)<br /> kh«ng cã h¹ng ®Çy ®ñ. Trong [1] chØ ra r»ng, víi mét biÕn ®æi tuyÕn tÝnh ngÉu<br /> nhiªn vµ q=1 th× rÊt hiÕm khi gi¸ trÞ FA tháa m·n FA>23b (b=8). Tuy nhiªn, biÕn<br /> ®æi tuyÕn tÝnh trong m· khèi ARIA l¹i cã ®iÓm bÊt ®éng. §ång<br /> thêi, víi mét biÕn ®æi tuyÕn tÝnh ngÉu nhiªn vµ q=8 th× rÊt hiÕm khi gi¸ trÞ FA tháa<br /> m·n FA>2b (b=8). Tuy nhiªn, biÕn ®æi tuyÕn tÝnh trong m· khèi AES l¹i cã<br /> ®iÓm bÊt ®éng.<br /> Nh­ vËy cã thÓ thÊy r»ng c¶ hai biÕn ®æi tuyÕn tÝnh cña AES vµ ARIA ®Òu cã sè<br /> l­îng ®iÓm bÊt ®éng v­ît qu¸ giíi h¹n mong ®îi cña mét biÕn ®æi tuyÕn tÝnh ngÉu<br /> nhiªn. Tuy nhiªn, gi¸ trÞ D(A) cña AES lµ t­¬ng ®èi nhá, cßn gi¸ trÞ D(A) cña<br /> ARIA t­¬ng ®èi lín so víi AES.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 103<br />  Kỹ thuật điện tử và Khoa học máy tính<br /> <br /> 4. KÕT LUËN<br /> Tõ c¸c ph­¬ng ph¸p ®o ®é khuÕch t¸n cña m· khèi ®· giíi thiÖu vµ dùa trªn c¸c<br /> kÕt qu¶ thùc nghiÖm, bµi b¸o ®­a ra c¸c hÖ sè vÒ ¶nh h­ëng th¸c ®æ (da), ¶nh h­ëng<br /> th¸c ®æ chÆt (dsa) vµ thuéc tÝnh ®Çy ®ñ (dc) cña hai m· khèi AES vµ DES. KÕt qu¶<br /> cho thÊy m· khèi AES tháa m·n c¸c tiªu chuÈn trªn nh­ng m· khèi DES ch­a tháa<br /> m·n tiªu chuÈn vÒ ¶nh h­ëng th¸c ®æ vµ th¸c ®æ chÆt. Sau ®ã, bµi b¸o tËp trung vµo<br /> ph­¬ng ph¸p dùa trªn sè ®iÓm bÊt ®éng ®Ó ®o ®é khuÕch t¸n cña hai m· khèi AES<br /> vµ ARIA. KÕt qu¶ cho thÊy hÖ sè vÒ sè ®iÓm bÊt ®éng cña AES lµ t­¬ng ®èi nhá vµ<br /> cña ARIA lµ kh¸ lín. §iÒu ®ã còng cã nghÜa lµ tÇng biÕn ®æi tuyÕn tÝnh cña AES<br /> thùc hiÖn sù khuÕch t¸n kh¸ hiÖu qu¶ vµ cña ARIA lµ ch­a hiÖu qu¶. Nh÷ng kÕt<br /> qu¶ thu ®­îc mang tÝnh thùc nghiÖm vµ ®¸nh gi¸ chø kh«ng ®­a ra tÝnh míi vÒ mÆt<br /> ph­¬ng ph¸p.<br /> §Ó thiÕt kÕ mét m· khèi an toµn, ng­êi thiÕt kÕ ph¶i quan t©m ®Õn mäi thµnh<br /> phÇn cña m· khèi, trong ®ã tÇng biÕn ®æi tuyÕn tÝnh v« cïng quan träng quyÕt ®Þnh<br /> ®é an toµn cña m· khèi. §Ó cã thÓ c¶i thiÖn tÇng khuÕch t¸n cña c¸c m· khèi hiÖu<br /> qu¶ h¬n, ®ßi hßi ph¶i x©y dùng ®­îc c¸c biÕn ®æi tuyÕn tÝnh tèt, tháa m·n ®­îc c¸c<br /> tiªu chuÈn vÒ ¶nh h­ëng th¸c ®æ, ¶nh h­ëng th¸c ®æ chÆt, thuéc tÝnh ®Çy ®ñ, ngoµi<br /> ra biÕn ®æi nµy ph¶i cã sè nh¸nh cao vµ hÖ sè vÒ sè ®iÓm bÊt ®éng nhá. Khi ®¸p<br /> øng ®­îc c¸c yªu cÇu nµy th× tÇng khuÕch t¸n sÏ cã ®é khuÕch t¸n cao hay tÝnh<br /> hiÖu qu¶ cña sù khuÕch t¸n lµ tèt, vµ kÐo theo lµ lµm t¨ng ®é an toµn cña m· khèi<br /> chèng l¹i ®­îc nhiÒu tÊn c«ng m¹nh nh­: tÊn c«ng tuyÕn tÝnh, tÊn c«ng l­îng sai,<br /> tÊn c«ng ®¹i sè. Trong thùc tÕ, ®Ó thiÕt kÕ ®­îc c¸c tÇng biÕn ®æi tuyÕn tÝnh ®¸p<br /> øng ®­îc tÊt c¶ nh÷ng tiªu chÝ ®Ò ra lµ mét bµi to¸n khã, vµ ®ang lµ mét vÊn ®Ò më<br /> trong nghiªn cøu vÒ m· khèi hiÖn nay.<br /> <br /> TµI LIÖU THAM KH¶O<br /> <br /> [1]. M.R.Z’aba, “Analysis of Linear Relationships in BlockCiphers,”<br /> Ph.D. Thesis, Queensland University of Technology, Brisbane,<br /> Australia, 2010, pp. 137-160.<br /> [2] Pascale Serf: The degrees of completeness, of avalanche effect, and of strict<br /> avalabche criterion for MARS, RC6, Rijndael,Serpent, and Twofish with<br /> reduced number of rounds. – Siemens AG, ZT IK 3, April 3 – 2000, pp. 1-3.<br /> [3]. Speaker M. Tolga Sakallı, Bora Aslan, “Algebraic Construction of 16 16<br /> Binary Matrices of Branch Number 7 with One Fixed Point, Computer<br /> Engineering Department, Trakya University, Edirne, Turkey. 2012, pp. 1-3.<br /> <br /> <br /> <br /> <br /> 104 T.T.Lương, V.Đ.Thu, T.Đ.Sự, “ Đo độ khuyếch tán… dựa trên số điểm bất động.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> ABSTRACT<br /> THE METHOD OF MEASURING THE DIFFUSION OF BLOCK CIPHER<br /> BASED ON THE NUMBER OF FIXED POINTS<br /> In this paper, methods of measuring the diffusion of block cipher are<br /> introduced, such as avalanche effect, strict avalanche effect, completeness,<br /> branch number, especially the method of measuring based on the number of<br /> fixed points is concentrated on. Then avalanche effect, strict avalanche<br /> effect, completeness are applied to measure the diffusion of AES and DES<br /> block cipher. After that, the diffusion of AES and ARIA block cipher is<br /> measured based on the number of fixed points. From these experimental<br /> results, the effectivity of diffusion of those block ciphers is evaluated.<br /> Keywords: Diffusion layer, fixed points, Avalanche effect, Tightly avalanche effect, Branch number.<br /> <br /> <br /> <br /> <br /> NhËn bµi ngµy 02 th¸ng 11 n¨m 2014<br /> Hoµn thiÖn ngµy 10 th¸ng 01 n¨m 2014<br /> ChÊp nhËn ®¨ng ngµy 10 th¸ng 02 n¨m 2015<br /> <br /> <br /> <br /> <br /> Địa chỉ: *Häc viÖn Kü thuËt MËt m· - Ban C¬ yÕu chÝnh phñ;<br /> **<br /> Trung t©m CNTT vµ Gi¸m s¸t an ninh m¹ng - Ban C¬ yÕu chÝnh phñ.<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 105<br />