Phân tích các thành phần mật mã trong hoán vị Keccak-P

 độc lập ở từng sheet theo từng lane. Giá trị 
 Output: Mảng trạng thái A’ dịch bit phụ thuộc vào tọa độ x và y. Do vậy có 
 Các bƣớc biến đổi nhƣ sau: thể cài đặt đơn giản trong môi trƣờng phần cứng 
 1. Với tất cả z với , ta đặt hoặc trên phần mềm đối với phép biến đổi . 
 A’[0,0,z]=A[0,0,z] D. Biến đổi 
 2. Đặt (x, y) = (0, 1) Thuật toán 4 dƣới đây minh họa hoạt động 
 3. Cho t chạy từ 0 tới 23: của biến đổi : 
 a. Với tất cả z thỏa mãn Thuật toán 4: ( ) 
 ta đặt A’[ x, y, z]= A[x, y, (z- 
 (t+1)(t+2)/2) mod w]. Input: Mảng trạng thái A 
 b. Đặt [x, y]=[y, (2x + 3y) mod 5]. Output: Mảng trạng thái A’ 
 4. Return A’. Những bƣớc biến đổi: 
 Tác động của phép biến đổi là để xoay các 1. Với tất cả những bộ 3 (x, y, z) thỏa mãn 
bit của từng lane theo 1 chiều dài gọi là offset, những điều kiện 
với việc phụ thuộc vào các tọa độ cố định của x tính A’[x, y, z]= A[x, y, z] 
và y trong lane. Tƣơng đƣơng với từng bit trong ((A[(x+1) mod 5, y, z] ) A[(x+2) mod 5, 
lane, tọa độ z đƣợc sửa đổi bằng cách cộng y, z]). 
modulo các offset theo kích thƣớc lane. 
 2. Return A’ 
 Bảng 1. Các offset của 
 x = 3 x = 4 x = 0 x = 1 x = 2 
 y = 2 153 231 3 10 171 
 y = 1 55 276 36 300 6 
 y = 0 28 91 0 1 190 
 y = 4 120 78 210 66 253 
 y = 3 21 136 105 45 15 
 Minh họa phép biến đổi với w = 8 đƣợc 
biểu diễn ở Hình 5. Các nhãn chuyển đổi cho 
 Hình 6. Minh họa phép biến đổi 
các tọa độ cố định x, y ở hình 4 đƣợc biểu diễn áp dụng cho từng row riêng lẻ 
tƣơng tự nhƣ nhƣ trong hình 5, tƣơng đƣơg với 
 Trên thực tế, các nhà thiết kế lựa chọn có 
các hàng và các cột trong bảng . Ví dụ lane[0,0] 
 biểu thức đại số đơn giản để thuận tiện cho các 
đƣợc miêu tả ở giữa của sheet giữa, còn 
 cài đặt cứng hóa. Tuy nhiên, có thể ghép các bit 
lane[2,3] đƣợc miêu tả ở dƣới cùng của sheet 
 trên cùng 1 lane để thực hiện. Theo đó: 
ngoài cùng bên phải. 
38 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 , - , - ( ,( 
 ) - ( ) ) ,( Thuật toán 6: (A,ir) 
 ) -, Input: Mảng trạng thái A 
trong đó ( ) ⏟ . Với biểu diễn này, 
 Chỉ số vòng ir 
biến đổi có thể thực hiện trên lane và rất Output: Mảng trạng thái A’ 
thuận tiện trong cài đặt phần mềm. Các bƣớc của thuật toán: 
E. Biến đổi 1. Với tất cả các bộ 3 (x, y, z) thỏa mãn 
 Biến đổi chỉ tác động lên lane gốc, nghĩa là điều kiện và 
lane có tọa độ x = y = 0. Bản chất của nó là , ta đặt: 
cộng vào lane gốc các hằng số phụ thuộc vào A’[x, y, z] = A[x, y, z] 
chỉ số vòng của hoán vị Keccak-p. Do vậy, biến 2. Đặt RC = 
đổi này có thể dễ dàng cài đặt trong phần cứng 
 3. Cho j chạy từ 0 tới , ta đặt 
và phần mềm. 
 RC[2j -1] = rc([j+7i ) 
 Phép ánh xạ đƣợc tham số hóa bởi chỉ số r
 4. Với tất cả z thỏa mãn , ta đặt 
vòng , những giá trị này đƣợc xác định trong 
bƣớc 2 của thuật toán tính hoán vị Keccak–p[b, A’[0,0,z] = A’[0,0,z] [z] 
nr] ở phần sau. Trong phạm vi phép biến đổi ở 5. Return A’. 
thuật toán 6 bên dƣới, tham số này xác định Tác động của phép biến đổi là để biến đổi 
 bit của giá trị lane đƣợc gọi là hằng số một vài bit của lane[0, 0] phụ thuộc vào chỉ số 
vòng, và đƣợc định nghĩa là RC. Mỗi bit của vòng ir. Còn lại 24 lane khác đều không bị ảnh 
 bit đƣợc tạo ra bởi một hàm mà hàm này hƣởng bởi phép biến đổi . 
dựa trên một thanh ghi dịch tuyến tính có phản Ánh xạ bao gồm việc thêm các hằng số 
hồi. Hàm này ký hiệu là rc và đƣợc định nghĩa ở vòng và hƣớng tới phá vỡ tính đối xứng. Các bit 
thuật toán 5. của các hằng số vòng là khác nhau từ vòng này 
 đến vòng kia và đƣợc lấy là đầu ra của LFSR có 
 Thuật toán 5: rc(t) 
 độ dài lớn nhất. Các hằng số này chỉ đƣợc thêm 
 Input: số nguyên t trong một lane của trạng thái. Do đó sự phá vỡ 
 Output: bit rc(t) này sẽ đƣợc lan truyền thông qua và đối với 
 tất cả các lane của trạng thái sau một đơn. 
 Các bƣớc của thuật toán 
 IV. TÍNH CHẤT MẬT MÃ CÁC 
 1. Nếu t mod 255 =0 , return 1 
 BIẾN ĐỔI THÀNH PHẦN 
 2. Đặt R = 10000000 TRONG HOÁN VỊ KECCAK-p 
 3. Cho i chạy từ 1 tới t mod 255, đặt: Trong mục này chúng tôi xem xét hai tính 
 3.1. R= 0 R chất mật mã, gồm số nhánh của biến đổi tuyến 
 tính, và sự ảnh hƣởng của các bit đầu vào (hoặc 
 3.2. R[0]= R[0] R[8] đầu ra) lên các bit đầu ra (hoặc đầu vào) của 
 3.3. R[4]= R[4] R[8] hàm vòng. 
 Đối với biến đổi tuyến tính, chúng ta chỉ 
 3.4. R[5]= R[5] R[8] 
 quan tâm đến sự khuếch tán , bởi vì các biến 
 3.5. R[6]= R[6] R[8] đổi và không làm thay đổi số lƣợng bit tích 
 3.6. R = Trunc8[R] cực mà chỉ thay đổi vị trí của các bit này trong 
 mảng trạng thái. Còn biến đổi thực chất là 
 4. Return R[0] phép cộng với hằng số đối với các bit trong 
 lane[0, 0]. Do vậy, nó không tác động lên số 
 lƣợng bit tích cực trong hàm vòng. 
 Số 2.CS (08) 2018 39 
Journal of Science and Technology on Information Security 
 , ( ) - 
 , - ,( ) ( ) -
Đối với việc xem xét sự hảnh hƣởng của các bit 
đầu vào (hoặc đầu ra) lên các bit đầu ra (hoặc 
đầu vào) của hàm vòng, chúng tôi sẽ thực hiện , ( ) ( ) - 
biểu diễn một bit đầu ra phụ thuộc vào các bit ,( ) ( ) -
đầu vào. { , - 
A. Số nhánh của biến đổi Còn trong các trƣờng hợp còn lại của tọa độ 
 Ánh xạ là tuyến tính và đảm nhiệm vai trò x và z, thì , - . Do vậy, các bit của trạng 
khuếch trong hoán vị Keccak-p. Tác động của thái bằng 1, gồm: 
nó có thể đƣợc mô tả nhƣ sau: Cộng XOR mỗi [ ] [ ] 
bit , -, -, - trong trạng thái với giá trị chẵn/lẻ , - , 
(tổng XOR các bit) của hai cột , -, -, - 
 ,( ) - 
và , -, -, -. Nếu không có biến đổi , 
 ,( ) - 
hoán vị Keccak-f sẽ không có tính khuếch tán. 
 ,( ) - , 
Đối với các trạng thái mà ở đó tổng bit trong tất 
 với , và 
cả các cột của nó là số chẵn, thì là đồng nhất. 
Nhƣ vậy, những trạng thái mà có trọng số ,( ) ( 
Hamming nhỏ nhất là bằng 2, có nghĩa là có ) - 
một cột có 2 bit tích cực, các cột khác đều chứa ,( ) ( 
các bit bằng 0. Khi đó số nhánh của biến đổi ) - ,( ) ( 
chỉ là 4. Trong [6], các tác giả lập luận và đƣa ra ) - , với 
số nhánh nhƣ vậy. Tuy nhiên, để khẳng định . 
điều này ta cần xem xét để chứng tỏ trong 
 Từ đây có ( ) 
những trƣờng hợp khác, số nhánh không thể 
 và ( ) ( ) 
nhỏ hơn 4. Mệnh đề dƣới đây sẽ chi tiết hơn về 
 . 
vấn đề này. 
 Trường hợp 2: ( ) . Xét các khả 
 Mệnh đề 1: Số nhánh của biến đổi trong 
 năng sau: 
hoán vị Keccak-p bằng 4. 
 Nếu hai bit có giá trị bằng 1 trong trạng 
 Chứng minh: Gọi A là mảng trạng thái đầu 
 thái A cùng nằm trên hai cột. Khi đó tất cả 
vào, còn A’ là mảng trạng thái đầu ra qua biến 
 các giá trị , - đều bằng 0, với 
đổi . Khi đó, số nhánh theo bit của biến đổi 
 . Điều này dẫn tới tất cả các 
đƣợc xác định bởi công thức 
 giá trị , - cũng đều bằng 0 với mọi 
 ( ) ( ) ( ) ( ( )). 
 ( ).Vì 
 Xét các trƣờng hợp sau: 
 Trường hợp 1: ( ) . Có nghĩa rằng , - , - , - , -, 
trạng thái A chỉ có một bit có giá trị bằng 1. Giả sử 
 nên ( ) ( ) . 
bit đó có tọa độ là ( ) [ ] . 
 Khi đó, Do vậy . 
 , - Nếu hai bit có giá trị bằng 1 trong trạng 
 { 
 , - thái A nằm ở 2 cột khác nhau. Khi đó lập 
 Từ biểu thức của , -, có luận tƣơng tự nhƣ trong trƣờng hợp 1, có 
 . 
40 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Trường hợp 3: ( ) . Mệnh đề 2. Đối với biến đổi vòng trong 
 Nếu ba bit có giá trị bằng 1 trong A đều hoán vị Keccak-p của hàm băm SHA-3 có: 
 thuộc một cột. Khi đó ta sẽ tính đƣợc 128 bit đầu ra (hoặc đầu vào) phụ thuộc 
 ( ) tƣơng tự nhƣ trong trƣờng hợp vào 32 bit đầu vào (hoặc đầu ra); 
 1. Do vậy, . 
 1472 bit đầu ra (hoặc đầu vào) phụ 
 Nếu ba bit có giá trị bằng 1 trong A thuộc vào 33 bit đầu vào (hoặc đầu ra). 
 không thuộc cùng một cột. Khi đó hoặc Chứng minh. Trong chứng minh này chúng 
 chúng sẽ thuộc ba cột khác nhau, hoặc thuộc tôi sẽ xem xét sự ảnh hƣởng của các bit đầu vào 
 hai cột khác nhau. Lập luận tƣơng tự ta lên 1 bit đầu ra bằng cách biểu diễn biểu thức 
 cũng sẽ có . mỗi lane đầu ra qua các lane đầu vào. Từ đó 
 Ở các trƣờng hợp còn lại, khi mà ( ) cho phép nhận đƣợc các đánh giá về sự phụ 
 , ta sẽ luôn luôn có ( ) ( ) thuộc của các bit đầu ra vào các bit đầu vào. Xét 
 . Do vậy số nhánh của biến đổi tuyến tính là lane có tọa độ ( ) bất kỳ, . Và 
bằng 4. thực hiện biểu diễn nó qua các ánh xạ 
 và trong biến đổi vòng của 
B. Sự phụ thuộc các bit đầu vào và đầu ra của 
hàm vòng trong hoán vị Keccak-p hoán vị Keccak-p. 
 Việc xem xét sự lan truyền giữa các bit đầu , - → , - 
vào/ra, hay nói cách khác sự phụ thuộc lẫn nhau ,( ) - 
của các bit đầu vào và đầu ra là một tính chất ,( ) - 
quan trọng trong thiết kế các nguyên thủy mật ,( ) - 
mã. Trong [6], các tác giả nói rằng, khi kết hợp → ,( ) - 
tầng tuyến tính với biến đổi trong hàm vòng ,( ) ( ) -
của hoán vị Keccak-p, thì mỗi bit tại đầu vào 
của hàm vòng có khả năng ảnh hƣởng tới 31 bit 
 ,( ) ( ) - 
tại đầu ra và mỗi bit tại đầu ra của hàm vòng 
 ,( ) ( ) - 
phụ thuộc vào 31 bit đầu vào của nó. Tuy nhiên, 
khi xây dựng chƣơng trình thực hiện hàm vòng → ⏟( ,( ) - )
của hoán vị Keccak-p, chúng tôi đã tìm ra rất 
 ( ,( ) ( ) - ) 
nhiều trạng thái, mà khi thay đổi 1 bit đầu vào ⏟ 
hoặc đầu ra sẽ làm thay đổi 32 hoặc 33 bit đầu 
 ⏟( , ( ) ( ) - ) 
ra hoặc đầu vào tƣơng ứng. Mặt khác khi biểu 
diễn sự phụ thuộc các bit đầu ra bởi các bit đầu ( ,( ) ( ) -
vào chúng tôi cũng nhận đƣợc các đánh giá ) 
tƣơng tự. Mệnh đề sau đây sẽ chi tiết vấn đề , 
này. Ở đây chúng tôi chỉ chứng minh các kết trong đó a, b, c là các giá trị offset đƣợc quy 
quả cho trƣờng hợp hoán vị Keccak-p trong định bởi biến đổi . Trong trƣờng hợp 
chuẩn hàm băm SHA3, có nghĩa rằng lựa chọn có . 
giá trị w = 64 và . Qua biến đổi , ta có, 
 Đối với biểu thức A: 
 → ( ,( ) - ) 
 ( ,( ) - ) 
 ( ,( ) - ) 
 Số 2.CS (08) 2018 41 
Journal of Science and Technology on Information Security 
 ( ,( ) ) 
 ( ,( ) ) ) Các giá trị dịch trong mỗi lane xác định bởi: 
 ( ,( ) - ) ,( ) - 
 ( ,( ) ) ,( ) ( 
 ( ,( ) ) ( )) ) - 
 ( ,( ) - ) ,( ) ( 
 ) - 
 ∑ ( ,( ) - ) Từ biểu thức của A, B hoặc C thấy rằng mỗi 
 biểu thức tƣơng ứng phụ thuộc vào 11 lane. Mặt 
 khác, theo bảng offset của biến đổi có các 
 ∑(( ,( ) -) trƣờng hợp sau: 
 Trường hợp 1. ( ) ( ): Trong 
 ( )) 
 trƣờng hợp này có và là thỏa 
 mãn điều kiện . 
 Đối với biểu thức B: 
 Trường hợp 2. ( ) ( ): Trong 
 → 
 trƣờng hợp này có và là thỏa 
( ,( ) ( ) -
 mãn điều kiện . 
 ) 
 Trường hợp 3. ( ) ( ) và ( ) 
∑ ( ,( ) - ) ( ): Trong trƣờng hợp này , 
 và . 
∑(( ,( ) -) Xét các trƣờng hợp trên: 
 Trường hợp 1: Với ( ) ( ), có 
 ( )) ( ,( ) ( 
 ) - ) 
 Đối với biểu thức C: 
 ∑ ( ,( ) - ) 
 → 
( ,( ) ( ) - 
 ∑ (( ,( ) -) 
 ) ( )) = 
 ( , - ) ∑ ( , - 
∑ ( ,( ) - ) 
 ) ∑ ( , - )
 . 
 và 
∑(( ,( ) -) ( ,( ) ( 
 ) - ) 
 ( )) 
 Ta thấy rằng phép dịch trong mỗi lane ở mỗi ∑ ( ,( ) - ) 
biểu thức A, B hoặc C cho ta tọa độ z đƣợc dịch 
đi, hay nói cách khác, phép dịch thể hiện xem ∑ (( ,( ) -) 
các tọa độ của trạng thái , - nằm ở ( )) = 
slice nào. ( , - ) ∑ ( , - 
 ) ∑ ( , - ) = 
42 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 ( ) ), vì phép dịch cùng 1 
 ( , - ) ∑ ( , - ) lane đi hai vị trí khác nhau. 
 ( , - ) Hay nói cách khác, biểu thức A, B và C 
 không chứa các lane chung. Từ đây ta có kết 
 ( , - )
 quả rằng bit đầu ra phụ 
 ( , - ) thuộc vào 33 biến đầu vào. Các bit này nằm trên 
 ( , - ) 23 lane có tọa độ ( ) ( ) và ( ) 
 ( , - ). ( ). 
 Nhƣ vậy, biểu thức của B và C có 1 lane V. KẾT LUẬN 
chung (màu đậm trong biểu thức ở trên). Do Trong bài báo này, chúng tôi tập trung 
vậy, biểu thức sẽ có 11 + 11 + nghiên cứu phân tích một số tính chất mật mã 
10 = 32 lane tham gia. Kết quả là sẽ có 64 bit ở của các biến đổi thành phần trong hoán vị 
đầu ra có tọa độ ( ) ( ) Keccak-p của chuẩn hàm băm SHA-3. Đối với 
phụ thuộc vào 32 bit đầu vào (các bit này thuộc biến đổi thành phần ban đầu chúng tôi mô tả 
 , -). hoạt động, sau đó đƣa ra nhận xét về khả năng 
 Trường hợp 2: Với ( ) ( ), ta thực cài đặt hiệu quả trên phần mềm của chúng. 
hiện phân tích tƣơng tự nhƣ trong trƣờng hợp 1. Riêng với đại lƣợng số nhánh của biến đổi 
Khi đó, trong biểu thức của A và B sẽ có 1 lane chúng tôi đã làm tƣờng minh kết quả về số 
chung là , - . Do vậy, cũng sẽ có nhánh bằng 4 của nó. Ngoài ra, khi kết hợp tầng 
64 bit đầu ra trong , - phụ thuộc vào 32 tuyến tính với biến đổi phi tuyến , chúng tôi 
bit đầu vào. cũng chính xác hóa lại về số lƣợng các bit đầu 
 Trường hợp 3. ( ) ( ) và ( ) ra phụ thuộc vào các bit đầu vào đã đƣợc đƣa ra 
( ). Khi đó ta có các kết quả sau: trong [6]. Cụ thể đã tìm ra 128 bit đầu ra ở 
 Các tọa độ z trong ( ,( , - và , - phụ thuộc vào 32 bit 
 ) - ) của A và trong mỗi đầu vào, 1472 bit ở những lane còn lại phụ 
 lane trong tổng ∑ ( ,( thuộc vào 33 bit đầu vào của hàm vòng. 
 ) - ) của C là nằm trên các Từ đây, có thể đƣa ra một hƣớng nghiên cứu 
 slice khác nhau (ở đây xét ), vì phép để tăng số bit phụ thuộc giữa đầu vào và đầu ra 
 dịch cùng 1 lane đi hai vị trí khác nhau. của hàm vòng, đó là sử dụng các S-hộp có bậc 
 đại số lớn hơn so với S-hộp trong ánh xạ của 
 Các tọa độ z trong mỗi lane trong tổng 
 Keccak-p. Tuy nhiên điều này có thể ảnh hƣởng 
 ∑ (( ,( ) -) 
 đến khả năng cài đặt tổng thể của thuật toán, do 
 ( )) của A và trong mỗi lane tƣơng ứng vậy cần phải tiếp tục nghiên cứu khi xem xét 
 trong tổng ∑ ( ,( các đề xuất cụ thể của S-hộp 5 bit. 
 ) - ) của B cũng nằm trên các 
 slice khác nhau, vì phép dịch cùng 1 lane đi 
 hai vị trí khác nhau. 
 Các tọa độ z trong mỗi lane ( ,( 
 ) ( ) - ) của 
 B và trong mỗi lane trong tổng 
 ∑ (( ,( ) -) 
 ( )) của C cũng nằm trên các slice khác 
 nhau (với và ) (ở đây xét 
 Số 2.CS (08) 2018 43 
Journal of Science and Technology on Information Security 
 TÀI LIỆU THAM KHẢO SƠ LƢỢC VỀ TÁC GIẢ 
1. Damgård, I.B. ―A design principle for hash 
 TS. Nguyễn Văn Long 
 functions. in Advances in Cryptology—
 CRYPTO’89 Proceedings”. Springer, 1989. Đơn vị công tác: Viện Khoa học -
 Công nghệ mật mã, Ban Cơ yếu 
2. Merkle, R.C. ―One way hash functions and DES. 
 Chính phủ. 
 in Advances in Cryptology‖—CRYPTO’89 
 Email: longnv@bcy.gov.vn 
 Proceedings, Springer, 1989. 
 Quá trình đào tạo: Nhận bằng Kỹ 
3. Guido, B., et al., ―Cryptographic sponge 
 sƣ chuyên nghành An toàn thông 
 functions‖. 2011. tin các hệ thống viễn thông tại 
4. Зензин, О. and М. ―Иванов, Стардарт Học viện FSO - Liên bang Nga năm 2008. Bảo vệ 
 криптографической защиты-AES‖. Конечные thành công luận án Tiến sĩ tại học viện FSO Liên 
 поля, КУДРИЦ-ОБРАЗ М, 2002. bang Nga theo chuyên ngành Các phƣơng pháp bảo 
5. NIST, SHA-3 Stadard: ―Permutation-Based Hash vệ thông tin năm 2015. 
 And Extendable Output Functions‖. 8/2015. Hƣớng nghiên cứu hiện nay: Nghiên cứu, cài đặt, 
6. Bertoni, G., et al., ―The Keccak reference, thiết kế các thuật toán mã khối. 
 version 3.0‖, 
 URL:
 3.0.pdf. Citations in this document. 4, 2011. 
44 Số 2.CS (08) 2018