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

Keccak là hàm băm đã chiến thắng

trong cuộc thi SHA-3. Nghiên cứu này sẽ tập

trung phân tích và chi tiết một số tính chất mật

mã của các biến đổi thành phần cấu thành nên

hoán vị Keccak-p trong hàm băm Keccak. Cụ thể

sẽ đưa ra lập luận chi tiết cho số nhánh của biến

đổi tuyến tính trong hàm vòng của hoán vị

Keccak-p và xem xét sự phụ thuộc giữa các bit

đầu vào và đầu ra trong hàm vòng này. Mặt khác

cũng đưa ra một vài phân tích về khả năng cài

đặt của Keccak dựa trên những biến đổi thành

phần này

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

Trang 1

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

Trang 2

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

Trang 3

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

Trang 4

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

Trang 5

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

Trang 6

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

Trang 7

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

Trang 8

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

Trang 9

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

Trang 10

Tải về để xem bản đầy đủ

pdf 11 trang minhkhanh 8700
Bạn đang xem 10 trang mẫu của tài liệu "Phân tích các thành phần mật mã trong hoán vị Keccak - P", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Phân tích các thành phần mật mã trong hoán vị Keccak - P

Phân tích các thành phần mật mã trong hoán vị Keccak - P
Journal of Science and Technology on Information Security 
34 Số 2.CS (08) 2018 
Nguyễn Văn Long 
Tóm tắt— Keccak là hàm băm đã chiến thắng 
trong cuộc thi SHA-3. Nghiên cứu này sẽ tập 
trung phân tích và chi tiết một số tính chất mật 
mã của các biến đổi thành phần cấu thành nên 
hoán vị Keccak-p trong hàm băm Keccak. Cụ thể 
sẽ đưa ra lập luận chi tiết cho số nhánh của biến 
đổi tuyến tính trong hàm vòng của hoán vị 
Keccak-p và xem xét sự phụ thuộc giữa các bit 
đầu vào và đầu ra trong hàm vòng này. Mặt khác 
cũng đưa ra một vài phân tích về khả năng cài 
đặt của Keccak dựa trên những biến đổi thành 
phần này. 
Abstract— Keccak is a winning hash function 
in the SHA-3 competition. This study will focus 
on analyzing and detailing some of the 
cryptographic properties of the constituent 
composition changes, permutating Keccak-p in 
the hash function Keccak. Specifically, a detailed 
argument will be given for the number of 
branches of linear transformation in the loop 
function of Keccak-p permutation and 
considering the dependency between input and 
output bits in this loop function. On the other 
hand, also gives some analysis of Keccak's 
installation ability based on these component 
changes. 
Từ khóa— Hàm băm Keccak; hoán vị Keccak; 
SHA-3. 
Keywords—Keccak hash function; Keccak 
hash function; SHA-3. 
I. GIỚI THIỆU 
Hàm băm mật mã là một thành phần quan 
trọng trong mật mã hiện đại. Có hai nguyên lý 
thiết kế điển hình hiện nay cho các hàm băm là 
dựa trên cấu trúc lặp Merkle-Damgärd [1, 2] và 
cấu trúc Sponge [3]. Trong khi ở cấu trúc thứ 
nhất, các mã khối đƣợc sử dụng để thiết kế các 
hàm nén theo những cấu trúc nhất định, thì ở 
cấu trúc thứ 2 lại sử dụng các hoán vị lặp. Tuy 
Bài báo đƣợc nhận ngày 1/12/2018. Bài báo đƣợc nhận 
xét bởi phản biện thứ nhất vào ngày 5/12/2018 và đƣợc chấp 
nhận đăng vào ngày 21/12/2018. Bài báo đƣợc nhận xét bởi 
phản biện thứ hai vào ngày 10/12/2018 và đƣợc chấp nhận 
đăng vào ngày 20/12/2018. 
nhiên, các hàm băm có đƣợc thiết kế theo 
nguyên lý nào đi nữa thì vẫn có thể thấy rằng 
nhân mật mã của chúng đƣợc xây dựng dựa trên 
nguyên lý lặp đi lặp lại các biến đổi tuyến tính 
và phi tuyến đơn giản (nguyên lý của Shannon). 
Theo đó, biến đổi phi tuyến cung cấp tính xáo 
trộn cho các bit đƣợc xử lý qua hàm vòng, còn 
biến đổi tuyến tính sẽ đảm đƣơng nhiệm vụ 
khuếch tán rộng hơn tính xáo trộn này. Trong 
tài liệu [4] nói rằng: Việc sử dụng đơn lẻ hai 
tính chất này sẽ không mang lại hiệu quả trong 
các thiết kế mật mã. Chúng chỉ mang lại hiệu 
quả khi đƣợc kết hợp với nhau. 
Keccak là hàm băm đã chiến thắng trong cuộc 
thi tuyển chọn hàm băm SHA-3 do NIST tổ 
chức. Nguyên lý thiết kế của nó cũng dựa trên 
nguyên tắc trên. Hàm vòng của nó có dạng [5]: 
 ( ) ( ( . ( ( ))/) ). 
Trong đó, tầng tuyến tính của nó là kết hợp 
bởi một số thành phần tuyến tính nhƣ biến đổi 
theta (phép ), biến đổi pi (phép ), biến đổi 
rho (phép ) và biến đổi iota (phép ). Còn biến 
đổi phi tuyến đƣợc đảm bảo bởi biến đổi . 
Trong [6], các tác giả đƣa ra số nhánh của 
biến đổi tuyến tính bằng 4. Mặt khác, khi kết 
hợp các biến đổi tuyến tính và phi tuyến thì 1 
bit đầu vào có khả năng ảnh hƣởng tới 31 bit 
đầu ra và ngƣợc lại. Tuy nhiên, những số liệu 
này không đƣợc các tác giả trình bày chi tiết 
trong [6]. 
Đóng góp của chúng tôi. Trên cơ sở phân 
tích biến đổi tuyến tính , chúng tôi chứng minh 
chi tiết cho đại lƣợng số nhánh của biến đổi này. 
Còn khi kết hợp với biến đổi phi tuyến, chúng 
tôi cũng giải thích chi tiết cho sự phụ thuộc của 
các biến bit vào và đầu ra trong hàm vòng của 
hoán vị Keccak-p. Ngoài ra, đối với mỗi biến 
đổi thành phần nói trên, chúng tôi đƣa ra những 
Phân tích các thành phần mật mã trong 
hoán vị Keccak-p
Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (08) 2018 35 
phân tích về khả năng cài đặt của chúng trên các 
môi trƣờng phần mềm. 
Trong phạm vi nghiên cứu của bài báo này 
chúng tôi sẽ chỉ tập trung phân tích cho hoán vị 
Keccak-p của hàm băm Keccak trong chuẩn 
SHA-3. Có nghĩa là thực hiện phân tích đối với 
tham số w = 64. Các trƣờng hợp khác phụ thuộc 
vào giá trị của tham số này đƣợc thực hiện 
tƣơng tự. 
Bố cục phần còn lại bài báo gồm: Mục II sẽ 
trình bày về quy ƣớc mảng trạng thái của hoán 
vị Keccak-p. Mô tả các biến đổi thành phần 
cùng với một vài phân tích về khả năng cài đặt 
của chúng sẽ đƣợc đƣa ra ở Mục III. Trong Mục 
IV sẽ xem xét làm tƣờng minh một số tính chất 
mật mã của các biến đổi thành phần này. Cuối 
cùng là Mục Kết luận. 
II. QUY ƢỚC MẢNG TRẠNG THÁI 
 Trạng thái là một mảng các bit đƣợc liên tục 
cập nhập trong quá trình xử lý. Đối với một phép 
hoán vị Keccak- , trạng thái đƣợc biểu diễn bằng 
một chuỗi hoặc một mảng ba chiều [5]. 
Trạng thái cho phép hoán vị Keccak- , ] 
bao gồm bit và vòng của hoán vị. Bản đặc 
tả thông số kỹ thuật trong bộ tiêu chuẩn SHA-3 
bao gồm hai đại lƣợng khác liên quan đến là 
 ⁄ và ( ⁄ ), lần lƣợt ký hiệu là và 
 , trong đó * +. 
Có thể biểu diễn trạng thái đầu vào và đầu ra 
của phép hoán vị là các chuỗi b bit và biểu diễn 
trạng thái đầu vào và đầu ra của các ánh xạ con 
là một mảng bit 5×5×w. Nếu S là ký hiệu một 
chuỗi biểu diễn trạng thái, thì các bit của nó 
đƣợc đánh số từ 0 đến 1b , do đó: 
[0]|| [1] || ... || [ 2] || [ 1]S S S S b S b . 
Nếu A là ký hiệu của một mảng bit 5 5 w 
biểu diễn trạng thái, thì chỉ số của nó là bộ ba số 
nguyên ( , , )x y z sao cho 0 5,0 5x y và 
0 z w . Bit tƣơng ứng với ( , , )x y z đƣợc ký 
hiệu là [ , , ]A x y z . Mảng trạng thái biểu diễn cho 
trạng thái bằng một mảng ba chiều với chỉ số 
đƣợc xác định theo cách này. 
A. Thành phần của mảng trạng thái 
Đối với một phép hoán vị Keccak- , một 
mảng bit biểu diễn trạng thái. Các 
chỉ số thỏa mãn: , , và 
 ( ). 
Mảng trạng thái cho một phép hoán vị 
Keccak-p và các mảng con ít chiều hơn (đƣợc 
minh họa trong Hình 1 dƣới đây) ... e. Giá trị 
dịch bit phụ thuộc vào tọa độ x và y. Do vậy có 
thể cài đặt đơn giản trong môi trƣờng phần cứng 
hoặc trên phần mềm đối với phép biến đổi . 
D. Biến đổi 
Thuật toán 4 dƣới đây minh họa hoạt động 
của biến đổi : 
Thuật toán 4: ( ) 
Input: Mảng trạng thái A 
Output: Mảng trạng thái A’ 
Những bƣớc biến đổi: 
1. Với tất cả những bộ 3 (x, y, z) thỏa mãn 
những điều kiện 
 tính A’[x, y, z]= A[x, y, z] 
((A[(x+1) mod 5, y, z] ) A[(x+2) mod 5, 
y, z]). 
2. Return A’ 
Hình 6. Minh họa phép biến đổi 
áp dụng cho từng row riêng lẻ 
Trên thực tế, các nhà thiết kế lựa chọn có 
biểu thức đại số đơn giản để thuận tiện cho các 
cài đặt cứng hóa. Tuy nhiên, có thể ghép các bit 
trên cùng 1 lane để thực hiện. Theo đó: 
Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (08) 2018 39 
 , - , - ( ,( 
 ) - ( ) ) ,( 
 ) -, 
trong đó ( ) ⏟
. Với biểu diễn này, 
biến đổi có thể thực hiện trên lane và rất 
thuận tiện trong cài đặt phần mềm. 
E. Biến đổi 
Biến đổi chỉ tác động lên lane gốc, nghĩa là 
lane có tọa độ x = y = 0. Bản chất của nó là 
cộng vào lane gốc các hằng số phụ thuộc vào 
chỉ số vòng của hoán vị Keccak-p. Do vậy, biến 
đổi này có thể dễ dàng cài đặt trong phần cứng 
và phần mềm. 
Phép ánh xạ đƣợc tham số hóa bởi chỉ số 
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, 
nr] ở phần sau. Trong phạm vi phép biến đổi ở 
thuật toán 6 bên dƣới, tham số này xác định 
 bit của giá trị lane đƣợc gọi là hằng số 
vòng, và đƣợc định nghĩa là RC. Mỗi bit của 
 bit đƣợc tạo ra bởi một hàm mà hàm này 
dựa trên một thanh ghi dịch tuyến tính có phản 
hồi. Hàm này ký hiệu là rc và đƣợc định nghĩa ở 
thuật toán 5. 
Thuật toán 5: rc(t) 
Input: số nguyên t 
Output: bit rc(t) 
Các bƣớc của thuật toán 
1. Nếu t mod 255 =0 , return 1 
2. Đặt R = 10000000 
3. Cho i chạy từ 1 tới t mod 255, đặt: 
3.1. R= 0 R 
3.2. R[0]= R[0] R[8] 
3.3. R[4]= R[4] R[8] 
3.4. R[5]= R[5] R[8] 
3.5. R[6]= R[6] R[8] 
3.6. R = Trunc8[R] 
4. Return R[0] 
Thuật toán 6: (A,ir) 
Input: Mảng trạng thái A 
 Chỉ số vòng ir 
Output: Mảng trạng thái A’ 
Các bƣớc của thuật toán: 
1. Với tất cả các bộ 3 (x, y, z) thỏa mãn 
điều kiện và 
 , ta đặt: 
A’[x, y, z] = A[x, y, z] 
2. Đặt RC = 
3. Cho j chạy từ 0 tới , ta đặt 
RC[2j -1] = rc([j+7ir) 
4. Với tất cả z thỏa mãn , ta đặt 
A’[0,0,z] = A’[0,0,z] [z] 
5. Return A’. 
Tác động của phép biến đổi là để biến đổi 
một vài bit của lane[0, 0] phụ thuộc vào chỉ số 
vòng ir. Còn lại 24 lane khác đều không bị ảnh 
hƣởng bởi phép biến đổi . 
Ánh xạ bao gồm việc thêm các hằng số 
vòng và hƣớng tới phá vỡ tính đối xứng. Các bit 
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ó 
độ dài lớn nhất. Các hằng số này chỉ đƣợc thêm 
trong một lane của trạng thái. Do đó sự phá vỡ 
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. 
IV. TÍNH CHẤT MẬT MÃ CÁC 
BIẾN ĐỔI THÀNH PHẦN 
TRONG HOÁN VỊ KECCAK-p 
Trong mục này chúng tôi xem xét hai tính 
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 
đầu ra) lên các bit đầu ra (hoặc đầu vào) của 
hàm vòng. 
Đối với biến đổi tuyến tính, chúng ta chỉ 
quan tâm đến sự khuếch tán , bởi vì các biến 
đổi và không làm thay đổi số lƣợng bit tích 
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à 
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. 
Journal of Science and Technology on Information Security 
40 Số 2.CS (08) 2018 
Đố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 
Ánh xạ là tuyến tính và đảm nhiệm vai trò 
khuếch trong hoán vị Keccak-p. Tác động của 
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 
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 
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 
những trƣờng hợp khác, số nhánh không thể 
nhỏ hơn 4. Mệnh đề dƣới đây sẽ chi tiết hơn về 
vấn đề này. 
Mệnh đề 1: Số nhánh của biến đổi trong 
hoán vị Keccak-p bằng 4. 
Chứng minh: Gọi A là mảng trạng thái đầu 
vào, còn A’ là mảng trạng thái đầu ra qua biến 
đổi . Khi đó, số nhánh theo bit của biến đổi 
đƣợc xác định bởi công thức 
 ( ) ( 
 ) ( ) ( ( )). 
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ử 
bit đó có tọa độ là ( ) [ ] . 
Khi đó, 
{
 , - 
 , - 
Từ biểu thức của , -, có 
{
 , ( ) - 
 , - ,( ) ( ) -
 , ( ) ( ) - 
 ,( ) ( ) -
 , - 
Còn trong các trƣờng hợp còn lại của tọa độ 
x và z, thì , - . Do vậy, các bit của trạng 
thái bằng 1, gồm: 
 [ ] [ ] 
 , - , 
 ,( ) - 
 ,( ) - 
 ,( ) - , 
với , và 
 ,( ) ( 
 ) - 
 ,( ) ( 
 ) - ,( ) ( 
 ) - , với 
 . 
Từ đây có ( ) 
 và ( ) ( 
 ) 
 . 
Trường hợp 2: ( ) . Xét các khả 
năng sau: 
 Nếu hai bit có giá trị bằng 1 trong trạng 
thái A cùng nằm trên hai cột. Khi đó tất cả 
các giá trị , - đều bằng 0, với 
 . Điều này dẫn tới tất cả các 
giá trị , - cũng đều bằng 0 với mọi 
( ).Vì 
 , - , - , - , -, 
nên ( ) ( ) . 
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 
luận tƣơng tự nhƣ trong trƣờng hợp 1, có 
 . 
Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (08) 2018 41 
Trường hợp 3: ( ) . 
 Nếu ba bit có giá trị bằng 1 trong A đều 
thuộc một cột. Khi đó ta sẽ tính đƣợc 
 ( ) tƣơng tự nhƣ trong trƣờng hợp 
1. Do vậy, . 
 Nếu ba bit có giá trị bằng 1 trong A 
không thuộc cùng một cột. Khi đó hoặc 
chúng sẽ thuộc ba cột khác nhau, hoặc thuộc 
hai cột khác nhau. Lập luận tƣơng tự ta 
cũng sẽ có . 
Ở các trƣờng hợp còn lại, khi mà ( ) 
 , ta sẽ luôn luôn có ( ) ( 
 ) 
 . Do vậy số nhánh của biến đổi tuyến tính là 
bằng 4. 
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 
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 
quả cho trƣờng hợp hoán vị Keccak-p trong 
chuẩn hàm băm SHA3, có nghĩa rằng lựa chọn 
giá trị w = 64 và . 
Mệnh đề 2. Đối với biến đổi vòng trong 
hoán vị Keccak-p của hàm băm SHA-3 có: 
 128 bit đầu ra (hoặc đầu vào) phụ thuộc 
vào 32 bit đầu vào (hoặc đầu ra); 
 1472 bit đầu ra (hoặc đầu vào) phụ 
thuộc vào 33 bit đầu vào (hoặc đầu ra). 
Chứng minh. Trong chứng minh này chúng 
tôi sẽ xem xét sự ảnh hƣởng của các bit đầu vào 
lên 1 bit đầu ra bằng cách biểu diễn biểu thức 
mỗi lane đầu ra qua các lane đầu vào. Từ đó 
cho phép nhận đƣợc các đánh giá về sự phụ 
thuộc của các bit đầu ra vào các bit đầu vào. Xét 
lane có tọa độ ( ) bất kỳ, . Và 
thực hiện biểu diễn nó qua các ánh xạ 
 và trong biến đổi vòng của 
hoán vị Keccak-p. 
 , -
→ , - 
 ,( ) - 
 ,( ) - 
 ,( ) - 
→ ,( ) - 
 ,( ) ( ) -
 ,( ) ( ) - 
 ,( ) ( ) - 
→ ( ,( ) - )⏟ 
 ( ,( ) ( ) - )⏟ 
 ( ,( ) ( ) - ) ⏟ 
 ( ,( ) ( ) -
 ) 
 , 
trong đó a, b, c là các giá trị offset đƣợc quy 
định bởi biến đổi . Trong trƣờng hợp 
có . 
Qua biến đổi , ta có, 
Đối với biểu thức A: 
→ ( ,( ) - ) 
 ( ,( ) - ) 
 ( ,( ) - ) 
Journal of Science and Technology on Information Security 
42 Số 2.CS (08) 2018 
 ( ,( ) ) 
 ( ,( ) ) ) 
 ( ,( ) - ) 
 ( ,( ) ) 
 ( ,( ) ) ( )) 
 ( ,( ) - ) 
∑ ( ,( ) - )
∑(( ,( ) -)
 ( )) 
Đối với biểu thức B: 
→ 
( ,( ) ( ) -
 ) 
∑ ( ,( ) - )
∑(( ,( ) -)
 ( )) 
Đối với biểu thức C: 
→ 
( ,( ) ( ) -
 ) 
∑ ( ,( ) - )
∑(( ,( ) -)
 ( )) 
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. 
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 . 
 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ó 
 ( ,( ) ( 
 ) - ) 
∑ ( ,( ) - )
∑ (( ,( ) -) 
( )) = 
( , - ) ∑ ( , - 
 ) ∑ ( , - ) . 
và 
 ( ,( ) ( 
 ) - ) 
∑ ( ,( ) - )
∑ (( ,( ) -) 
( )) = 
( , - ) ∑ ( , - 
 ) ∑ ( , - ) = 
Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (08) 2018 43 
( , - ) ∑ ( , - )
 ( , - ) 
 ( , - )
 ( , - )
 ( , - ) 
( , - ). 
Nhƣ vậy, biểu thức của B và C có 1 lane 
chung (màu đậm trong biểu thức ở trên). Do 
vậy, biểu thức sẽ có 11 + 11 + 
10 = 32 lane tham gia. Kết quả là sẽ có 64 bit ở 
đầu ra có tọa độ ( ) ( ) 
phụ thuộc vào 32 bit đầu vào (các bit này thuộc 
 , -). 
Trường hợp 2: Với ( ) ( ), ta thực 
hiện phân tích tƣơng tự nhƣ trong trƣờng hợp 1. 
Khi đó, trong biểu thức của A và B sẽ có 1 lane 
chung là , - . Do vậy, cũng sẽ có 
64 bit đầu ra trong , - phụ thuộc vào 32 
bit đầu vào. 
Trường hợp 3. ( ) ( ) và ( ) 
( ). Khi đó ta có các kết quả sau: 
 Các tọa độ z trong ( ,( 
 ) - ) của A và trong mỗi 
lane trong tổng ∑ ( ,( 
 ) - ) của C là nằm trên các 
slice khác nhau (ở đây xét ), 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 trong tổng 
∑ (( ,( ) -) 
( )) của A và trong mỗi lane tƣơng ứng 
trong tổng ∑ ( ,( 
 ) - ) 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 
 ( ) ), 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à ( ) 
( ). 
V. KẾT LUẬN 
Trong bài báo này, chúng tôi tập trung 
nghiên cứu phân tích một số tính chất mật mã 
của các biến đổi thành phần trong hoán vị 
Keccak-p của chuẩn hàm băm SHA-3. Đối với 
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 
cài đặt hiệu quả trên phần mềm của chúng. 
Riêng với đại lƣợng số nhánh của biến đổi 
chúng tôi đã làm tƣờng minh kết quả về số 
nhánh bằng 4 của nó. Ngoài ra, khi kết hợp tầng 
tuyến tính với biến đổi phi tuyến , chúng tôi 
cũng chính xác hóa lại về số lƣợng các bit đầu 
ra phụ thuộc vào các bit đầu vào đã đƣợc đƣa ra 
trong [6]. Cụ thể đã tìm ra 128 bit đầu ra ở 
 , - và , - phụ thuộc vào 32 bit 
đầu vào, 1472 bit ở những lane còn lại phụ 
thuộc vào 33 bit đầu vào của hàm vòng. 
Từ đây, có thể đƣa ra một hƣớng nghiên cứu 
để tăng số bit phụ thuộc giữa đầu vào và đầu ra 
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 
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 
vậy cần phải tiếp tục nghiên cứu khi xem xét 
các đề xuất cụ thể của S-hộp 5 bit. 
Journal of Science and Technology on Information Security 
44 Số 2.CS (08) 2018 
TÀI LIỆU THAM KHẢO 
1. Damgård, I.B. ―A design principle for hash 
functions. in Advances in Cryptology—
CRYPTO’89 Proceedings”. Springer, 1989. 
2. Merkle, R.C. ―One way hash functions and DES. 
in Advances in Cryptology‖—CRYPTO’89 
Proceedings, Springer, 1989. 
3. Guido, B., et al., ―Cryptographic sponge 
functions‖. 2011. 
4. Зензин, О. and М. ―Иванов, Стардарт 
криптографической защиты-AES‖. Конечные 
поля, КУДРИЦ-ОБРАЗ М, 2002. 
5. NIST, SHA-3 Stadard: ―Permutation-Based Hash 
And Extendable Output Functions‖. 8/2015. 
6. Bertoni, G., et al., ―The Keccak reference, 
version 3.0‖, 
URL:
3.0.pdf. Citations in this document. 4, 2011. 
SƠ LƢỢC VỀ TÁC GIẢ 
TS. Nguyễn Văn Long 
Đơn vị công tác: Viện Khoa học -
Công nghệ mật mã, Ban Cơ yếu 
Chính phủ. 
Email: longnv@bcy.gov.vn 
Quá trình đào tạo: Nhận bằng Kỹ 
sƣ chuyên nghành An toàn thông 
tin các hệ thống viễn thông tại 
Học viện FSO - Liên bang Nga năm 2008. Bảo vệ 
thành công luận án Tiến sĩ tại học viện FSO Liên 
bang Nga theo chuyên ngành Các phƣơng pháp bảo 
vệ thông tin năm 2015. 
Hƣớng nghiên cứu hiện nay: Nghiên cứu, cài đặt, 
thiết kế các thuật toán mã khối. 

File đính kèm:

  • pdfphan_tich_cac_thanh_phan_mat_ma_trong_hoan_vi_keccak_p.pdf