Luận án Nghiên cứu và phát triển các phương pháp bảo vệ thông tin dựa trên AES

57 Chương 4 Tính an toàn của XAES dựa trên xác suất sai phân của tập vết sai phân và xác suất tuyến tính của bao tuyến tính Tóm tắt chương: $ Nội dung của chương 4 trình bày hướng tiếp cận xác định chặn trên của xác suất sai phân của tập vết sai phân và chặn trên của xác suất tuyến tính của bao vết tuyến tính: % Trình bày tóm tắt về hướng tiếp cận và các công trình liên quan chứng minh tính an toàn của giải thuật sử bằng cách xác định chặn trên của xác suất sai phân của tập vết sai phân và chặn trên của xác suất tuyến tính của bao tuyến tính % Trình bày kết quả xác định chặn trên tổng quát của xác suất sai phân của tập vết sai phân và chặn trên tổng quát của xác suất tuyến tính của bao tuyến tính đối với XAES: o Khảo sát 2 chu kỳ của XAES để xác định chặn trên của xác suất (sai phân/tuyến tính) của tập vết sai phân/tuyến tính với kết quả trọng tâm là Định lý 4.2 và Định lý 4.5. o Xác định chặn trên tổng quát cho xác suất (sai phân/tuyến tính) của tập vết sai phân/tuyến tính qua 4 chu kỳ của XAES với kết quả trọng tâm được trình bày trong Định lý 4.3 và Định lý 4.6. o Xác định chặn trên tổng quát cho xác suất (sai phân/tuyến tính) của tập vết sai phân/tuyến tính qua r ≥ 4 chu kỳ của XAES với kết quả trọng tâm được trình bày trong Định lý 4.4 và Định lý 4.7. 58 4.1 Hướng tiếp cận sử dụng tập vết sai phân và bao tuyến tính 4.1.1 Giới thiệu về hướng tiếp cận sử dụng tập vết sai phân và bao tuyến tính Ý tưởng sử dụng một vết sai phân hay vết tuyến tính đơn để phân tích mã được áp dụng thành công trong trường hợp thuật toán DES [31]. Chính vì vậy đã dẫn đến phương pháp chứng minh độ an toàn của thuật toán mã hóa theo khối bằng cách chứng minh không tồn tại vết sai phân (hoặc tuyến tính) đơn có tỷ lệ truyền (hoặc độ tưong quan) đủ lớn. Bên cạnh hướng tiếp cận sử dụng vết lan truyền đơn, hướng tiếp cận sử dụng tập hợp các vết lan truyền có cùng chung một số tính chất cũng đã được đề xuất: Định nghĩa 4.1 [56]. Cho vector sai phân Δa và Δb. Tập vết sai phân tương ứng với Δa và Δb, ký hiệu là DIFF(Δa, Δb), là tập hợp tất cả các vết sai phân ( )TT TT Δ⎯⎯ →⎯Δ⎯⎯ →⎯⎯⎯ →⎯Δ⎯⎯ →⎯Δ=Ω −− ρρρρ 110 121 ... lan truyền qua T ≥ 1 chu kỳ có giá trị sai phân ở đầu vào chu kỳ 1 là Δ0 = Δa và giá trị sai phân ở đầu ra chu kỳ T là ΔT = Δb. Định nghĩa 4.2 [70]. Cho vector mặt nạ Γa và Γb. Bao tuyến tính tương ứng với Γa và Γb, ký hiệu là ALH(Γa, Γb), là tập hợp tất cả các vết tuyến tính ( )TT TT Γ⎯⎯ ⎯←Γ⎯⎯ ⎯←⎯⎯ ⎯←Γ⎯⎯←Γ=Ξ −− ρρρρ 110 121 ... lan truyền qua T ≥ 1 chu kỳ có mặt nạ ở đầu vào chu kỳ 1 là Γ0 = Γa và mặt nạ ở đầu ra chu kỳ T là ΓT = Γb. Để chứng minh tính an toàn của thuật toán mã hóa với phương pháp sai phân hoặc tuyến tính sử dụng tập vết sai phân hoặc bao tuyến tính, cần chứng minh là mọi tập vết sai phân/bao tuyến tính lan truyền qua T chu kỳ (thường T = Nr – 2 hay T = Nr – 1) đều có xác suất sai phân/tuyến tính đủ nhỏ. Tuy nhiên, cho đến hiện tại, việc xác định chính xác giá trị tối đa của xác suất sai phân và xác suất tuyến tính của tập hợp vết lan truyền qua các chu kỳ vẫn chưa thể thực hiện trên thực tế được [49]. Vì vậy, nhiều công trình đã tập trung theo hướng xác định chặn trên của giá trị tối đa của xác suất sai phân cũng như xác suất tuyến tính ([12][38][44][46][47][71][72]). 59 Theo hướng tiếp cận này, chúng tôi đã xác định và chứng minh công thức tổng quát giá trị chặn trên của giá trị tối đa của xác suất sai phân và xác suất tuyến tính, từ đó chứng minh tổng quát tính an toàn của XAES đối với phương pháp sai phân và phương pháp tuyến tính trong phân tích mã độc lập với các giá trị cụ thể của các tham số về cấu trúc và tham số về xử lý của XAES. 4.1.2 Một số khái niệm và tính chất cơ bản Định nghĩa 4.3. ([38]) Cho { }nyx 10,, ∈ΔΔ . Xác suất sai phân (DP) của ánh xạ { } { }nnS 1010 ,,: → được định nghĩa là: ( )yxDP S ΔΔ , ( ) ( ){ }yxxSxSx Δ=Δ⊕⊕= Pr ( ) ( ){ } n n yxxSxSx 2 2 Δ=Δ⊕⊕Ζ∈= :# (4.1) Từ định nghĩa của xác suất sai phân, suy ra: ( ) { } ( ) { } 1 1010 =ΔΔ=ΔΔ ∑∑ ∈Δ∈Δ nn u S u S yuDPuxDP ,, ,, (4.2) Định nghĩa 4.4. ([38]) Cho { }nyx 10,, ∈ΓΓ . Xác suất tuyến tính (LP) của ánh xạ { } { }nnS 1010 ,,: → được định nghĩa là: ( )yxLP S ΓΓ , ( ){ }( )212 −•Γ=•Γ⋅= xSyxxxPr ( ){ } 2 1 2 1 2 ⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − •Γ=•ΓΖ∈ = −n n xSyxxx :# (4.3) Từ định lý Parseval [63], suy ra ( ) { } ( ) { } 1 1010 =ΓΓ=ΓΓ ∑∑ ∈Γ∈Γ nn u S u S yuLPuxLP ,, ,, (4.4) Định nghĩa 4.5. ([38]) Xác suất sai phân tối đa p và xác suất tuyến tính tối đa q của S-box Sϕ được xác định như sau: ( )yxDPp S yx ΔΔ= Δ≠Δ ,max , ϕ 0 (4.5) ( )yxLPq S xy ΓΓ= Γ≠Γ ,max , ϕ 0 (4.6) 60 Định nghĩa 4.6. [38] Cho ánh xạ tuyến tính ( ) ( )NwmNwm 22 GFGF →:L . Đặt ( )NwmGFyx 2∈ΔΔ , lần lượt là vector sai phân ở đầu vào và đầu ra của L, ( )NwmGFyx 2∈ΓΓ , lần lượt là mặt nạ ở đầu vào và đầu ra của L. Branch Number (sai phân) của L được định nghĩa như sau: ( ) ( ) ( ){ }ywtxwtxd Δ+Δ= ≠Δ 0minLB (4.7) Branch Number (tuyến tính) của L được định nghĩa như sau: ( ) ( ) ( ){ }ywtxwtyl Γ+Γ= ≠Γ 0minLB (4.8) Định nghĩa 4.7. [38] Cho vector ( ) nnxxx Z∈= ,,…1 . Mẫu các thành phần khác 0 của x, ký hiệu là χx, được định nghĩa là ( ) nnx 21 Z∈= χχχ …, với 0=iχ nếu 0=ix và 1=iχ nếu 0≠ix . &Ví dụ: Với ( )4321 xxxxx ,,,= với 01 ≠x , 02 ≠x , 043 == xx thì ( )0011 ,,,=xχ . 4.2 Các công trình liên quan a) SDS (1 chu kỳ) b) SDS (3 chu kỳ) Hình 4.1. Một số ví dụ về hàm SDS Thao tác cộng khóa vào mỗi chu kỳ mã hóa không có ảnh hưởng trong việc khảo sát sự lan truyền của tập vết sai phân cũng như bao tuyến tính [38][44]. Chính vì vậy, trong [38][44], S. Hong đã đề xuất việc khảo sát xác suất của tập vết sai phân và xác 61 suất của bao tuyến tính lan truyền trong hàm SDS (Substitution – Diffusion – Substitution). Về mặt bản chất, kiến trúc SDS chính là kiến trúc SPN nhưng bỏ qua thao tác cộng khóa trong mỗi chu kỳ. Hàm SDS (1 chu kỳ) bao gồm tầng thay thế, tầng khuếch tán và tầng thay thế (xem Hình 4.1a). Trong hàm SDS (gồm r > 1 chu kỳ), r – 1 chu kỳ đầu tiên gồm tầng thay thế và tầng khuếch tán, riêng chu kỳ cuối cùng chỉ gồm tầng thay thế. Hình 4.1b minh họa hàm SDS gồm 3 chu kỳ. Trong hàm SDS, tầng thay thế gồm n S-box (không nhất thiết phải giống nhau). Gọi p và q lần lượt là xác suất sai phân và xác suất tuyến tính tối đa của S-box trong tầng thay thế. Kết quả quan trọng của công trình [38] và được phân tích chi tiết trong [44] là chứng minh xác suất của tập vết sai phân và xác suất của bao tuyến tính lan truyền qua hàm SDS (gồm 2 chu kỳ) lần lượt được chặn trên bởi pn và qn nếu tầng khuếch tán có branch number (sai phân/tuyến tính) là n + 1 (có khả năng khuếch tán tối đa), và được chặn trên bởi pn – 1 và qn – 1 nếu tầng khuếch tán có branch number (sai phân/khuếch tán) là n (có khả năng khuếch tán gần tối đa). Dựa trên các kết quả đối với hàm SDS, trong [71], S. Park đã khảo sát thuật toán Rijndael (trong trường hợp khối dữ liệu được biểu diễn bằng ma trận 4 × 4) và một số thuật toán có cấu trúc tương tự (Crypton [59], Square[18]) để xác định chặn trên cho xác suất của tập vết sai phân và chặn trên cho xác suất của bao tuyến tính. S. Park giới thiệu 1 tập các thuật toán tựa-Rijndael được tạo ra bằng cách sửa giải thuật Rijndael với một hay một số cách thay đổi sau: • Thay thế S-box (8 × 8) trong Rijndael bằng S-box (8 × 8) bất kỳ có xác suất sai phân tối đa 32−≤p và xác suất tuyến tính tối đa 32−≤q . • Thay thế ánh xạ ShiftRows bằng một ánh xạ π bất kỳ sao cho mỗi cột sau khi biến đổi nhận được byte từ cả 4 cột trước khi biến đổi. • Có thể chọn ánh xạ θi trong tầng khuếch tán (tương ứng MixColumns trong Rijndael) là một ánh xạ bất kỳ trên GF(28)4 có branch number là 5 (khuếch tán tối đa). 62 Điểm khác biệt chính giữa kiến trúc SDS và cấu trúc của các thuật toán tựa- Rijndael được khảo sát trong [71] như sau: • Trong thuật toán tựa-Rijndael có thêm biến đổi tuyến tính π (tương ứng với biến đổi ShiftRows trong Rijndael) trước tầng khuếch tán (xem Hình 4.2). • Trong SDS, tầng khuếch tán là một ánh xạ tuyến tính duy nhất, nhận đầu vào là kết quả của các S-box trong tầng thay thế liền trước. Trong khi đó, đối với thuật toán tựa-Rijndael, tầng khuếch tán θ (tương ứng biến đổi MixColumns trong Rijndael) gồm 4 ánh xạ tuyến tính để xử lý riêng θ1, θ2, θ3, θ4 từng cột trong khối dữ liệu cần mã hóa1 (xem Hình 4.3). Trong [71], S. Park đã chứng minh rằng, đối với thuật toán tựa-Rijndael thuộc tập được xét, xác suất của tập vết sai phân lan truyền qua 4 chu kỳ là 16171819 464 pppp +++ nếu xác suất sai phân tối đa của S-box trong tầng thay thế đủ nhỏ ( 32−≤p ) và xác suất của bao tuyến tính lan truyền qua 4 chu kỳ là 16171819 464 qqqq +++ nếu xác suất tuyến tính tối đa của S-box trong tầng thay thế đủ nhỏ ( 32−≤q ). Như vậy, cơ sở của kết quả trong [71] là xác suất sai phân tối đa và xác suất tuyến tính tối đa của S-box. Kết quả mà S. Park trình bày trong [71] có ưu điểm là được phát biểu tổng quát với tham số (p hoặc q) nên có khả năng áp dụng cho nhiều thuật toán thuộc tập thuật toán tựa-Rijndael được xét trong [71]. Tuy nhiên, kết quả này chưa được tổng quát theo khả năng mở rộng về kích thước của thuật toán tựa-Rijndael. Hình 4.2. Biến đổi π trong Rijndael (trường hợp khối 128 bit) 1 Trong Rijndael sử dụng cùng một ánh xạ tuyến tính để xử lý các cột trong biến đổi MixColumns (θ1 = θ2 = θ3 = θ4) 63 Hình 4.3. Biến đổi θ với 4 biến đổi tuyến tính θ1, θ2, θ3, θ4 trong cấu trúc tựa- Rijndael được S. Park trình bày trong [71] (trường hợp khối 128 bit) Trong [72], S. Park xác định chặn trên chặt hơn cho xác suất của tập vết sai phân và xác suất của bao tuyến tính đối với Rijndael so với kết quả trong [71]. Thay vì dựa trên xác suất (sai phân/tuyến tính) tối đa của S-box, S. Park khảo sát mối quan hệ giữa chặn trên của xác suất sai phân/tuyến tính lan truyền qua 2 chu kỳ của cấu trúc SPN (sử dụng duy nhất một ánh xạ tuyến tính θi)1 với chặn trên của xác suất của tập vết sai phân/bao tuyến tính. Như vậy, trong cách tiếp cận này, thay vì sử dụng giá trị tối đa của xác suất sai phân/tuyến tính của S-box, S. Park đã dùng giá trị và phân bố của xác suất sai phân/tuyến tính của S-box. Nhờ đó, chặn trên của xác suất của tập vết sai phân/bao tuyến tính được xác định chặt hơn. Dựa trên ý tưởng của cách tiếp cận trong [72], chúng tôi đã áp dụng và chứng minh tổng quát công thức cho XAES để xác định chặn trên của xác suất của tập vết sai phân (phần 4.3) và chặn trên của xác suất của bao tuyến tính (phần 4.3.4). Để nội dung trình bày được cô đọng, trong những phần tiếp theo của Chương 4, chúng tôi sử dụng các ký hiệu đã được đề xuất trong phần 2.1.2 để thay thế cho tên gọi của các biến đổi trong XAES, cụ thể như sau: ϕ (biến đổi SubBytes), π (biến đổi ShiftRows), θ (biến đổi MixColumns), σ (biến đổi AddRoundKey). 1 cần lưu ý là tầng khuếch tán trong Rijndael sử dụng Nb = 4, 6, hay 8 ánh xạ tuyến tính giống nhau, trong XAES sử dụng Nb ánh xạ tuyến tính không nhất thiết giống nhau. 64 4.3 Giá trị chặn trên của xác suất sai phân của tập vết sai phân 4.3.1 Xác suất sai phân của tập vết sai phân lan truyền qua 2 chu kỳ của hàm SDS được xây dựng từ XAES Đặt βd là giá trị nhỏ nhất của branch number (sai phân) của các biến đổi tuyến tính được sử dụng trong tầng khuếch tán θ của XAES. ( ){ }id Nbi d θβ B110 −== ,...,,min (4.9) Chu kỳ 1 Chu kỳ 2 Các S-box (S ) i ……… Các S-box (S ) ……… Hình 4.4. Hàm SDS gồm 2 chu kỳ với tầng thay thế là các S-box giống nhau (Sϕ) và tầng khuếch tán gồm 1 ánh xạ tuyến tính θi Định lý 4.1. ([72-Định lý 1]) Xét hàm SDS (gồm 2 chu kỳ) với tầng thay thế sử dụng các S-box giống nhau (Sϕ ) và tầng khuếch tán là ánh xạ tuyến tính θi (xem Hình 4.4). Xác suất sai phân tối đa của tập vết sai phân qua hàm SDS này được chặn trên bởi: ( ) ≤baDP i ,θ2 ( ){ } ( ) ( ){ } ( ) ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ∑∑ − =−≤≤≤≤ − =−≤≤≤≤ 12 11211 12 11211 m id m m id m j S uni j S uni ujDPjuDP θθ ϕϕ BB ,maxmax,,maxmaxmax (4.10) Đặt =Ωd ( ){ } ( ){ } ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ∑∑ − =−≤≤≤≤ − =−≤≤≤≤ 12 11211 12 11211 m d m m d m j S uni j S uni ujDPjuDP ββ ϕϕ ,maxmax,,maxmaxmax . 65 Từ Định lý 4.1, suy ra: Bổ đề 4.1. Xác suất sai phân tối đa của tập vết sai phân qua hàm SDS (gồm 2 chu kỳ) với tầng thay thế sử dụng các S-box giống nhau (Sϕ ) và tầng khuếch tán là ánh xạ tuyến tính θi được chặn trên bởi: ( ) dbaDP i Ω≤,θ2 (4.11) $Chứng minh: Do ( )idd θβ B≤ và ( ) 1≤yxDP S ,ϕ nên Bổ đề 4.1 có thể được suy ra từ Định lý 4.1. & 4.3.2 Xác suất sai phân của tập vết sai phân lan truyền qua 2 chu kỳ của XAES Để khảo sát xác suất sai phân của tập vết sai phân lan truyền qua 2≥r chu kỳ của XAES, ta quy ước: • ( )Nbaaa ΔΔ=Δ ,,…1 : vector sai phân ở đầu vào, trong đó ( )jNwjjj aaaa ΔΔΔ=Δ ,,, …21 với Nbj ≤≤1 . • ( )Nbbbb ΔΔ=Δ ,,…1 : vector sai phân ở đầu ra, trong đó ( )jNwjjj bbbb ΔΔΔ=Δ ,,, …21 với Nbj ≤≤1 . • ( )baDPr ΔΔ , : xác suất sai phân qua r chu kỳ của XAES với vector sai phân ở đầu vào và đầu ra lần lượt là aΔ và bΔ . Tương tự như đối với hàm SDS, chúng tôi bỏ qua vai trò của biến đổi cộng khóa (σ) trong XAES vì không làm ảnh hưởng đến việc khảo sát sự lan truyền của tập vết sai phân và bao tuyến tính. Để có sự tương đồng khi áp dụng các kết quả khảo sát đối với hàm SDS vào XAES, khi khảo sát sự lan truyền của tập sai phân qua 2≥r chu kỳ của XAES, mỗi chu kỳ trong số r – 1 chu kỳ đầu gồm 3 biến đổi ϕ, π, θ , riêng chu kỳ r chi gồm biến đổi ϕ. 66 Định lý 4.2. Nếu ( ) ba ΔΔ = χχπ thì xác suất sai phân tối đa của tập vết sai phân qua 2 chu kỳ của XAES được chặn trên bởi: ( ) ( ) ( )( )awtdbaDP ΔΩ≤ΔΔ π,2 . Nếu ( ) ba ΔΔ ≠ χχπ thì ( ) 02 =ΔΔ baDP , . $Chứng minh: Hình 4.5. Minh họa Định lý 4.1 Trong 2 chu kỳ mã hóa của XAES, việc hoán vị ánh xạ ϕ và π trong chu kỳ 1 không làm thay đổi kết quả mã hóa. Hình 4.5 minh họa 2 chu kỳ mã hóa của XAES sau khi đảo thứ tự ánh xạ ϕ và π trong chu kỳ 1. Khi đó, có thể xem như 2 chu kỳ mã hóa của XAES gồm: • Thực hiện bước tiền xử lý bằng ánh xạ π. • Thực hiện Nb hàm SDS song song: hàm SDS thứ i ( Nbi ≤≤1 ) gồm 2 chu kỳ và có tầng khuếch tán là biến đổi tuyến tính θi. 67 Đặt ( ) ( )*** ,,, Nbaaaa ΔΔΔ=Δ …21π . Ta có: ( ) ( )iiNbi baDPbaDP i ΔΔ=ΔΔ ∏ = ,, *1 22 θ với iDP θ2 là xác suất sai phân qua hàm SDS (gồm 2 chu kỳ) với tầng khuếch tán là biến đổi tuyến tính iθ . Từ Bổ đề 4.1, suy ra giá trị chặn trên của ( )ii baDP i ΔΔ ,*θ2 như sau: ( ) ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ =Δ=Δ ≠Δ≠ΔΩ ≤ΔΔ laïi coøn hôïptröôøng trong neáu neáu , ,, ,, , * * * 0 001 00 2 ii iid ii ba ba baDP iθ (4.12) Nếu ( ) ba ΔΔ = χχπ , tức là * iaΔ và ibΔ cùng tính chất khác 0 hay cùng bằng 0, thì: ( )baDP ΔΔ ,2 [ ] ( )iiaNbi baDPi i ΔΔ= ∏ ≠Δ∧∈ , * , 01 2 θ [ ] ( ) ( )( )awt daNbi di Δ ≠Δ∧∈ Ω=Ω≤ ∏ π01, (4.13) Ngược lại, nếu tồn tại chỉ số [ ]Nbi ,1∈ sao cho *iaΔ và ibΔ không cùng tính chất khác 0 hay bằng 0 thì ( ) 02 =Δ→Δ baDP . & Nhận xét: Do 1≤Ωd và ( )( ) 1≥Δawt π với 0≠Δa nên từ Định lý 4.2 suy ra xác suất sai phân của tập vết sai phân qua 2 chu kỳ của XAES bị chặn trên bởi dΩ : ( )baDP ΔΔ ,2 dΩ≤ (4.14) Bổ đề 4.2. Xác suất sai phân của tập vết sai phân lan truyền qua 2 chu kỳ của XAES được chặn trên bởi ( ) ( )bwtd ΔΩ với bΔ là vector sai phân ở đầu ra. ( ) ( ) ( )bwtdbaDP ΔΩ≤ΔΔ ,2 (4.15) $Chứng minh: & Xét chu kỳ 2: • Sau khi qua các S-box : ( )1 ii z b ΔΔ = χχ , suy ra ( )( ) ( )bwtzwt Δ=Δ 1 , tức là ( )1zΔ có đúng ( )bwt Δ cột khác 0. 68 & Xét chu kỳ 1: • Qua các phép biến đổi θ i, số lượng và vị trí các cột khác 0 được giữ nguyên, suy ra ( )( ) ( )( ) ( )bwtzwtywt Δ=Δ=Δ 11 • Trong phép biến đổi π : ( )( )( ) ( )( ) ( )bwtywtxwt Δ=Δ=Δ 11π . • Khi qua các S-box : ( ) axi ΔΔ = χχ 1 , suy ra: ( )( ) ( )( )( ) ( )bwtxwtawt Δ=Δ=Δ 1ππ Theo Định lý 4.2, ( ) ( ) ( )( ) ( ) ( )bwtdawtdbaDP ΔΔ Ω=Ω≤ΔΔ π,2 & a Chu kỳ 1 Chu kỳ 2 Các S-box 1 Nb……… ……… x(1) y(1) z(1) Các S-box ……… b ( )( ) ( )( )( ) ( )( ) ( )( ) ( )bwtzwtywtxwtawt Δ=Δ=Δ=Δ=Δ 111ππ Hình 4.6. Minh họa Bổ đề 4.2 Bổ đề 4.3. Đặt ( )( )awtk Δ= πχ . Khi đó: ( )( ) ( ) ( ) 122 2 − Δ Ω≤ΔΔ∑ kd x xaDP , (4.16) $Chứng minh: & Xét chu kỳ 1: • ( )( ) ( )( ) kwtawt a ==Δ Δπχπ • Sau khi qua các S-box : ( ) ii ax ΔΔ = χχ 1 , suy ra ( )( )( ) ( )( ) kawtxwt =Δ=Δ ππ 1 69 • Sau khi qua biến đổi π : ( ) ( )( )11 xy Δ=Δ π , suy ra ( )( ) ( )( )( ) kxwtywt =Δ==Δ 11 π • Các biến đổi iθ không làm thay đổi số lượng và vị trí các cột khác 0 trong ( )1yΔ nên ( )( ) ( )( ) kywtzwt =Δ=Δ 11 . & Xét chu kỳ 2: • Sau khi qua các S-box : ( ) ( )12 ii zx ΔΔ = χχ , suy ra ( )( ) ( )( ) kzwtxwt =Δ=Δ 12 , tức là ( )2xΔ có đúng k cột khác 0. ( )( ) ( )( ) ( )( )( ) ( )( ) ( )( ) ( )( ) kxwtzwtywtxwtawtwt a =Δ=Δ=Δ=Δ=Δ=Δ 2111ππχπ Hình 4.7. Minh họa Bổ đề 4.2 Như vậy, sau khi qua biến đổi π ở chu kỳ 1, ( )1yΔ , ( )1zΔ và ( )2xΔ đều có đúng k cột khác 0 và có vị trí các cột này giống nhau. Đặt { } { }Nbvvv k ,...,,,..., 2121 ⊂=υ là tập chỉ số các cột khác 0 trong ( )2xΔ : ( ) ( ) 00 22 1 ≠Δ≠Δ kvv xx ,..., 70 Ta có: ( )( ) ( ) ∑ Δ ΔΔ 2 2 2 x xaDP , ( )( ) ( ) ∑ ∏ Δ = ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ΔΔ= 2 1 2 2 x k i vv ii iv xaDP ,* θ ( )( ) ( )( ) ( ) ∑ ∏ Δ = ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ΔΔΔΔ= 2 11 1 2 2 2 2 2 x k i vvvv ii ivv xaDPxaDP ,, ** θθ Theo Bổ đề 4.1, ( )( ) dvvi iiiv xaDPv Ω≤ΔΔ∈∀ 22 ,, *θυ . Vì vậy, ta có : ( )( ) ( ) ∑ Δ ΔΔ 2 2 2 x xaDP , ( ) ( )( ) ( ) ∑ Δ − ΔΔΩ≤ 2 1 11 1 2 2 1 v v x vv k d xaDP , *θ Do ( )( ) 1 1 11 1 2 2 =ΔΔ∑ Δ v v x vv xaDP , *θ nên suy ra: ( )( ) ( ) ∑ Δ ΔΔ 2 2 2 x xaDP , ( ) 1−Ω≤ kd & 4.3.3 Xác suất sai phân của tập vết sai phân lan truyền qua r ≥ 4 chu kỳ của XAES Hình 4.8 minh họa sự lan truyền sai phân qua 4 chu kỳ trong XAES. Trong Hình 4.8: • ( ) ( ) ( )( )iii Nb xxx ΔΔ=Δ ,,…1 : vector sai phân đầu vào của biến đổi π trong chu kỳ i, trong đó ( ) ( ) ( ) ( )( )ijNwijijij xxxx ΔΔΔ=Δ ,,, …21 với Nbj ≤≤1 . • ( ) ( ) ( )( )iii Nb yyy ΔΔ=Δ ,,…1 : vector sai phân đầu ra của biến đổi π trong chu kỳ i và cũng chính là vector sai phân đầu vào của biến đổi θ trong chu kỳ i, trong đó ( ) ( ) ( ) ( )( )ijNwijijij yyyy ΔΔΔ=Δ ,,, …21 với Nbj ≤≤1 . • ( ) ( ) ( )( )iii Nb zzz ΔΔ=Δ ,,…1 : vector sai phân đầu ra của biến đổi θ trong chu kỳ i, trong đó ( ) ( ) ( ) ( )( )ijNwijijij zzzz ΔΔΔ=Δ ,,, …21 với Nbj ≤≤1 . 71 Hình 4.8. Khảo sát sự lan truyền sai phân qua 4 chu kỳ trong XAES Định lý 4.3. Xác suất sai phân của tập vết sai phân lan truyền qua 4 chu kỳ của XAES được chặn trên bởi ( ) 1−Ω dd β . $Chứng minh: Nếu ( )( ) ( ) da bwtwt βχπ <Δ+Δ thì ( ) 04 =ΔΔ baDP , . Vậy, chỉ xét giá trị chặn trên của ( )baDP ΔΔ ,4 khi ( )( ) ( ) da bwtwt βχπ ≥Δ+Δ . • Trường hợp 1: ( )( ) dawt βχπ ≥Δ . ( )baDP ΔΔ ,4 ( )( ) ( )( ) ( ) ∑ Δ ΔΔΔΔ= 2 2 2 2 2 x bzDPxaDP ,, ( )( ) ( ) ∑ Δ ΔΔ≤ 2 2 2 x xaDP , ( ) ( )( )222 xaDPx ΔΔ≤ Δ ,max Theo Định lý 4.2, ta có: ( ) ( )( )222 xaDPx ,max ( ) ( )( )awt d πΩ≤ Do 1≤Ωd và ( )( ) ( )( ) dawtawt βχπ π ≥=Δ Δ nên ( ) ( )( ) ( ) ddx xaDP βΩ≤ΔΔ Δ 2 22 ,max . Suy ra ( )baDP ΔΔ ,4 ( ) dd βΩ≤ 72 • Trường hợp 2: ( ) dbwt β≥Δ ( )baDP ΔΔ ,4 ( )( ) ( )( ) ( ) ∑ Δ ΔΔΔΔ= 2 2 2 2 2 x bzDPxaDP ,, ( )( ) ( ) ∑ Δ ΔΔ≤ 2 2 2 z bzDP , ( ) ( )( )bzDP z ΔΔ≤ Δ ,max 222 Theo Bổ đề 4.2, ta có: ( ) ( )( )bzDP z ΔΔ Δ ,max 222 ( ) ( )bwt d ΔΩ≤ Do 1≤Ωd và ( ) dbwt β≥Δ nên ( ) ( )( ) ( ) dd z bzDP βΩ≤ΔΔ Δ ,max 222 Suy ra ( )baDP ΔΔ ,4 ( ) dd βΩ≤ • Trường hợp 3: ( )( ) dawt βχπ <≤ Δ1 và ( ) dbwt β<Δ≤1 . Đặt ( )( )awtk Δ= πχ và ( )bwtl Δ= . Ta có dlk β<≤ ,1 và dlk β≥+ . Ta có : ( )baDP ΔΔ ,4 ( )( ) ( )( ) ( ) ∑ Δ ΔΔΔΔ= 2 2 2 2 2 x bzDPxaDP ,, (4.17) Áp dụng Bổ đề 4.2 cho chu kỳ 3 và 4, ta có: ( )( )bzDP ΔΔ ,22 ( ) ( ) ( )ldbwtd Ω=Ω≤ Δ (4.18) Từ (5.17) và (5.18), suy ra : ( )baDP ΔΔ ,4 ( ) ( )( ) ( ) ∑ Δ ΔΔΩ≤ 2 2 2 x l d xaDP , (4.19) Áp dụng Bổ đề 4.3 cho chu kỳ 1 và 2, ta có : ( )( ) ( ) ( ) ( )( ) ( ) 1122 2 −− Δ Ω=Ω≤ΔΔ Δ∑ kdwtd x axaDP πγ, (4.20) Từ ( 5.19) và (5.20), suy ra : ( )baDP ΔΔ ,4 ( ) 1−+Ω≤ kld Do 1≤Ωd và dkl β≥+ nên ta có thể kết luận: ( )baDP ΔΔ ,4 ( ) ( ) 11 −Ω≤Ω≤ −+ ddkld β & 73 Định lý 4.4. Đặt ( )( ) 1≥Δ= awtk π . Xác suất sai phân của tập vết sai phân qua 4≥r chu kỳ của XAES được chặn trên bởi ( ) ( )rd dΦΩ với ( ) ( )12 41 −⎥⎦ ⎥ ⎢⎣ ⎢ −+−=Φ k r r dd β . $Chứng minh: Định lý 4.4 được chứng minh theo phương pháp quy nạp. Đặt ( )( ) 2≥Δ= awtk π . Với 4=r , ( ) 14 −=Φ dd β . Theo Định lý 4.3 : ( )baDP ΔΔ ,4 ( ) ( ) ( )41 dd dd Φ− Ω=Ω≤ β Với 5=r , ( ) dd β=Φ 5 . Ta có : ( )baDP ΔΔ ,5 ( )( ) ( )( ) ( ) ∑ Δ ΔΔΔΔ= 4 4 1 4 4 x bzDPxaDP ,, ( )( ) ( ) ∑ Δ ΔΔ≤ 4 4 4 x xaDP , Theo Định lý 4.3, ( )( ) ( ) 144 −Ω≤ΔΔ ddxaDP β, . Suy ra: ( )baDP ΔΔ ,5 ( ) ( ) ( )51 dd dd Φ− Ω=Ω≤ β Giả sử [ ] ( ) ( ) ( )rdr dbaDPrr ΦΩ≤ΔΔ∈∀ ,,,..., 04 . Ta sẽ chứng minh : ( ) ( )22 +Φ+ Ω≤ΔΔ rr dbaDP , Ta có: ( )baDPr ΔΔ+ ,2 ( )( ) ( )( ) ( ) ∑ Δ ΔΔΔΔ= 2 22 2 x r bzDPxaDP ,, Theo giả thiết quy nạp, ta có : ( )( ) ( ) ( )rdr dbzDP ΦΩ≤ΔΔ ,2 Suy ra: ( )baDPr ΔΔ+ ,2 ( ) ( ) ( )( ) ( ) ∑ Δ Φ ΔΔΩ≤ 2 2 2 x r d xaDP d , (4.21) Theo Bổ đề 4.3, áp dụng vào chu kỳ 1 và 2, ta có: ( )( ) ( ) ( ) 122 2 − Δ Ω≤ΔΔ∑ kd x xaDP , (4.22) 74 Từ (5.21) và (5.22), suy ra: ( )baDPr ΔΔ+ ,2 ( ) ( ) ( ) ( )21 +Φ−+Φ Ω=Ω≤ rdkrd dd Kết luận: ,4≥∀r ( )baDPr ΔΔ , ( ) ( )rd dΦΩ≤ với ( ) ( )12 41 −⎥⎦ ⎥ ⎢⎣ ⎢ −+−=Φ k r r dd β . & 4.3.4 Áp dụng với một số thể hiện cụ thể của XAES Nội dung phần này minh họa việc áp dụng các kết quả tổng quát đã chứng minh trong phần 4.3 vào một số thể hiện cụ thể của XAES. Trong các kết quả đã được trình bày trong phần 4.3, tham số chính dΩ phụ thuộc vào S-box Sϕ và branch number (sai phân) βd của tầng khuếch tán θ. =Ωd ( ){ } ( ){ } ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ∑∑ − =−≤≤≤≤ − =−≤≤≤≤ 12 11211 12 11211 m d m m d m j S uni j S uni ujDPjuDP ββ ϕϕ ,maxmax,,maxmaxmax (4.23) Trong XAES, S-box được xây dựng với ánh xạ nghịch đảo trên GF(2m), phụ thuộc vào tham số cấu trúc m. Tầng khuếch tán θ sử dụng Nb ánh xạ tuyến tính θi trên GF(2m)Nw có branch number (sai phân) nhỏ nhất là βd = Nw hay Nw + 1. Vì vậy, nội dung của phần này trình bày việc áp dụng các kết quả về chặn trên của xác suất sai phân của tập vết sai phân đối với một số thể hiện cụ thể của XAES với các giá trị khác nhau của tham số cấu trúc (m và Nw). Xét trường hợp m = 8. Chọn ( )80 21 GF∈=x và tính bảng phân bố của xác suất sai phân ( )yxDP S ,0ϕ (xem Bảng 4.1). Điều đáng lưu ý là nếu chọn giá trị 0x khác, chúng ta cũng nhận được bảng phân bố xác suất sai phân tương tự. Theo Bảng 4.1, có φi lần xác suất sai phân ( )yxDP S ,ϕ nhận giá pi (với i = 1, 2, 3). Từ đó suy ra: ( )( ) ∑∑ = − = ==Ω 3 1 12 0 0 8 i iiy S d d d pyxDP β β φϕ , (4.24) 75 Áp dụng Định lý 4.3, ta có chặn trên của xác suất sai phân của tập vết sai phân qua 4 chu kỳ của XAES như sau: ( ) ( ) 13 1 1 4 − = − ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ =Ω≤ ∑ d dd i iid pyxDP β ββ φ, (4.25) i 1 2 3 pi 62− 72− 0 φi 1 126 129 Bảng 4.1. Phân bố xác suất sai phân qua S-box trong XAES với m = 8 Với mỗi giá trị của tham số cấu trúc Nw, branch number (sai phân) βd của tầng khuếch tán θ có thể nhận giá trị là Nw hay Nw + 1. Bảng 4.2 thể hiện giá trị chặn trên của xác suất sai phân của tập vết sai phân qua 4 chu kỳ của XAES ( ( ) 1−Ω dd β ) theo giá trị branch number (sai phân) βd. Trong trường hợp Rijndael (tương ứng với m = 8 và βd = 5), xác suất sai phân của tập vết sai phân qua 4 chu kỳ mã hóa có chặn trên là 1.16080 × 2–111. Kết quả này phù hợp với kết quả do S. Park khảo sát riêng cho trường hợp Rijndael được công bố trong [72]. βd dΩ ( ) 1−Ω dd β βd dΩ ( ) 1−Ω dd β 1 1 1 11 1.06152 × 2–66 1.81669 × 2–660 2 1.01563 × 2–7 1.01563 × 2–7 12 1.03076 × 2–72 1.39551 × 2–792 3 1.04688 × 2–14 1.09595 × 2–28 13 1.01538 × 2–78 1.20100 × 2–936 4 1.10938 × 2–21 1.36532 × 2–63 14 1.00769 × 2–84 1.10472 × 2–1092 5 1.23438 × 2–28 1.16080 × 2–111 15 1.00385 × 2–90 1.05527 × 2–1260 6 1.48438 × 2–35 1.80160 × 2–173 16 1.00192 × 2–96 1.02919 × 2–1440 7 1.98438 × 2–42 1.90806× 2–247 17 1.00096 × 2–102 1.01547 × 2–1632 8 1.49219 × 2–48 1.02954× 2–332 18 1.00048 × 2–108 1.00819 × 2–1836 9 1.24609 × 2–54 1.45327 × 2–430 19 1.00024 × 2–114 1.00433 × 2–2052 10 1.12305 × 2–60 1.42089 × 2–539 20 1.00012 × 2–120 1.00228 × 2–2280 Bảng 4.2. Chặn trên của xác suất sai phân của tập vết sai phân qua 2 chu kỳ của hàm SDS và qua 4 chu kỳ của XAES với m = 8 76 4.4 Giá trị chặn trên của xác suất tuyến tính của bao tuyến tính 4.4.1 Các kết quả chính Đặt βl là giá trị nhỏ nhất của branch number (tuyến tính) của các biến đổi tuyến tính được sử dụng trong tầng khuếch tán θ của XAES. ( ){ }il Nbi l θβ B110 −== ,...,,min (4.26) Đặt =Ωl ( ){ } ( ){ } ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ∑∑ − =−≤≤≤≤ − =−≤≤≤≤ 12 11211 12 11211 m l m m l m j S uni j S uni ujLPjuLP ββ ϕϕ ,maxmax,,maxmaxmax Việc khảo sát xác suất tuyến tính của bao tuyến tính tương tự như quá trình khảo sát xác suất sai phân của tập vết sai phân, ngoại trừ một số thay đổi sau trong các kết quả và chứng minh: • thay thế vai trò của giá trị sai phân Δx bằng mặt nạ Γx tương ứng, • thay thế xác suất sai phân (DP) bằng xác suất tuyến tính (LP) tương ứng, • thay thế branch number (sai phân) βd bằng branch number (tuyến tính) βl • thay thế Ωd bằng Ωl Tương tự với các kết quả đối với xác suất sai phân của tập vết sai phân, chúng tôi cũng chứng minh được các kết quả tương tự cho xác suất tuyến tính của bao tuyến tính. Dưới đây là các kết quả chính: Bổ đề 4.4. Xác suất tuyến tính tối đa của bao tuyến tính qua hàm SDS (gồm 2 chu kỳ) với tầng thay thế sử dụng các S-box giống nhau (Sϕ ) và tầng khuếch tán là ánh xạ tuyến tính θi được chặn trên bởi: ( ) lbaLP i Ω≤,θ2 (4.27) Định lý 4.5. Nếu ( ) ba ΓΓ = χχπ thì xác suất tuyến tính tối đa của bao tuyến tính qua 2 chu kỳ của XAES được chặn trên bởi: ( ) ( ) ( )( )awtlbaLP ΓΩ≤ΓΓ π,2 . Nếu ( ) ba ΓΓ ≠ χχπ thì ( ) 02 =ΓΓ baLP , . 77 Bổ đề 4.5. Xác suất tuyến tính của bao tuyến tính qua 2 chu kỳ của XAES được chặn trên bởi ( ) ( )bwtl ΓΩ với bΓ là vector mặt nạ ở đầu ra. ( ) ( ) ( )bwtlbaLP ΓΩ≤ΓΓ ,2 (4.28) Bổ đề 4.6. Đặt ( )( )awtk Γ= πχ . Khi đó: ( )( ) ( ) ( ) 122 2 − Δ Ω≤ΓΓ∑ kl x xaLP , (4.29) Định lý 4.6. Xác suất tuyến tính của bao tuyến tính qua 4 chu kỳ của XAES được chặn trên bởi ( ) 1−Ω ll β . Định lý 4.7. Đặt ( )( ) 1≥Δ= awtk π . Xác suất tuyến tính của bao tuyến tính qua 4≥r chu kỳ của XAES được chặn trên bởi ( ) ( )rl lΦΩ với ( ) ( )1 2 41 −⎥⎦ ⎥ ⎢⎣ ⎢ −+−=Φ k r r ll β . 4.4.2 Áp dụng với một số thể hiện cụ thể của XAES Nội dung phần này minh họa việc áp dụng các kết quả tổng quát đã chứng minh trong phần 4.3 vào một số thể hiện cụ thể của XAES. Xét trường hợp m = 8. Chọn ( )80 21 GF∈=y và tính bảng phân bố của xác suất tuyến tính ( )0yxLP S ,ϕ (xem Bảng 4.3). Khi chọn giá trị 0y khác, chúng ta cũng nhận được bảng phân bố xác suất tuyến tính tương tự. Theo Bảng 4.3, có φi lần xác suất tuyến tính ( )yxLP S ,ϕ nhận giá pi (với i = 1, 2,…, 8). Từ đó suy ra: ( )( ) ∑∑ = − = ==Ω 9 1 12 0 0 8 i iiy S l l l pyxLP β β φϕ , (4.30) Áp dụng Định lý 4.6, ta có chặn trên của xác suất tuyến tính của bao tuyến tính qua 4 chu kỳ của XAES như sau: ( ) ( ) 19 1 1 4 − = − ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ =Ω≤ ∑ l ll i iil pyxLP β ββ φ, (4.31) 78 i 1 2 3 4 5 6 7 8 9 pi 2 64 8 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 2 64 7 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 2 64 6 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 2 64 5 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 2 64 4 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 2 64 3 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 2 64 2 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 2 64 1 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 0 φi 5 16 36 24 34 40 36 48 17 Bảng 4.3. Phân bố xác suất tuyến tính qua S-box trong XAES với m = 8 Với mỗi giá trị của tham số cấu trúc Nw, branch number (tuyến tính) βl của tầng khuếch tán θ có thể nhận giá trị là Nw hay Nw + 1. Bảng 4.4 thể hiện giá trị chặn trên của xác suất tuyến tính của bao tuyến tính qua 4 chu kỳ của XAES ( ( ) 1−Ω ll β ) theo giá trị branch number (tuyến tính) βl. Trong trường hợp Rijndael (tương ứng với m = 8 và βl = 5), xác suất tuyến tính của bao tuyến tính qua 4 chu kỳ mã hóa có chặn trên là 1.06388 × 2–106. Kết quả này phù hợp với kết quả do S. Park khảo sát riêng cho trường hợp Rijndael và được công bố trong [72]. βl lΩ ( ) 1−Ω ll β βl lΩ ( ) 1−Ω ll β 1 1 1 11 1.47820 × 2–64 1.55661 × 2–635 2 1.01563 × 2–7 1.01563 × 2–7 12 1.42138 × 2–70 1.49507 × 2–765 3 1.29187 × 2–14 1.66893 × 2–28 13 1.37935 × 2–76 1.48232 × 2–907 4 1.85120 × 2–21 1.58599 × 2–61 14 1.34799 × 2–82 1.51627 × 2–1061 5 1.43628 × 2–27 1.06388 × 2–106 15 1.32444 × 2–88 1.59698 × 2–1227 6 1.18211 × 2–33 1.15416 × 2–164 16 1.30667 × 2–94 1.72718 × 2–1405 7 1.01803 × 2–39 1.11317 × 2–234 17 1.2932 × 2–100 1.91205 × 2–1595 8 1.81586 × 2–46 1.01716 × 2–316 18 1.28297 × 2–106 1.08019 × 2–1796 9 1.66362 × 2–52 1.83354 × 2–411 19 1.27519 × 2–112 1.24213 × 2–2010 10 1.55588 × 2–58 1.66968 × 2–517 20 1.26925 × 2–118 1.44949 × 2–2236 Bảng 4.4. Chặn trên của xác suất tuyến tính của bao tuyến tính qua 2 chu kỳ của hàm SDS và qua 4 chu kỳ của XAES với m = 8 4.5 Kết luận Chúng tôi đã xác định các công thức tổng quát của giá trị chặn trên của xác suất sai phân của tập vết sai phân và giá trị chặn trên của xác suất tuyến tính của bao tuyến tính lan truyền qua r ≥ 4 chu kỳ của XAES. Các công thức được chúng tôi đề xuất và chứng minh có tính tổng quan hơn các kết quả đã được công bố [38][44][71][72]. Dựa trên các công thức trong Định lý 4.3 và Định lý 4.6 , chúng tôi đã áp dụng để khảo sát cụ thể với các thể hiện của XAES trong trường hợp m = 8 (trên trường 79 Galois của Rijndael), giá trị Nw biến thiên từ 1 đến 19 và giá trị branch number (βd cũng như βl) là Nw hay Nw + 1. Theo [44], chi phí để có thể áp dụng phương pháp sai phân hay phương pháp tuyến tính được xem là tỷ lệ với nghịch đảo giá trị chặn trên của xác suất sai phân hay xác suất tuyến tính. Một số vấn đề mở: • Trong công thức xác định chặn trên của xác suất sai phân và xác suất tuyến tính mà chúng tôi xây dựng sử dụng giá trị và phân bố của xác suất sai phân/tuyến tính của S-box. Việc chọn lựa một giá trị đặc trưng khác của S-box có thể giúp các giá trị chặn trên được xác định chặt hơn. • Có thể đề xuất cách làm trội khác trong quá trình xây dựng công thức chặn trên của xác suất sai phân và xác suất tuyến tính qua 4 chu kỳ mã hóa để kết quả đạt được chặt hơn.