1


MỤC LỤC

CHƯƠNG I: TỔNG QUAN VỀ HÀM BĂM MẬT MÃ
1.1. Khái quát về hàm băm mật mã

1.1.1. Định nghĩa hàm băm mật mã
Các hàm băm đóng vai trò cơ bản trong mật mã hiện đại. Hàm băm là một
hàm toán học chuyển đổi các xâu bit có độ dài hữu hạn tùy ý thành các xâu bit
có độ dài cố định. Đầu ra này được gọi là mã băm (hay kết quả băm, giá trị
băm, vết, hay tóm lược thông báo). Hàm băm được đặc trưng bởi hai tính chất
sau:
a) Tính chất nén: sẽ ánh xạ một đầu vào có độ dài bit hữu hạn tùy ý tới một
đầu ra có độ dài bit hữu hạn (tùy vào thuật toán băm được sử dụng).
b) Tính chất dễ dàng tính toán: Với cho trước và một đầu vào , có thể dễ
dàng tính được .
Hàm băm mật mã là hàm băm mà ngoài hai tính chất cơ bản trên còn phải
thỏa mãn ba tính chất an toàn được nêu dưới đây:
a) Tính kháng tiền ảnh (tính một chiều): Đối với hầu hết đầu ra được xác
định trước, không có khả năng tính toán để tìm một đầu vào bất kỳ mà khi băm
sẽ cho ra đầu ra tương ứng (tức là cho trước một giá trị tóm lược , không thể tìm
một tiền ảnh . sao cho ).
b) Tính kháng tiền ảnh thứ hai: Không có khả năng tính toán để tìm một đầu
vào thứ hai bất kỳ mà có cùng đầu ra như với đầu vào đã được xác định trước
(tức là cho trước , không có khả năng tính toán để tìm tiền ảnh thứ hai sao cho
và ).
c) Tính kháng va chạm: Không có khả năng tính toán để tìm hai đầu vào bất
kỳ sao cho và
Kích thước của thông điệp đầu vào là bất kỳ còn kích thước của giá trị băm

của thông điệp là nhỏ vậy nên việc trùng giá trị băm là không thể loại bỏ. Tính
chống trùng của hàm băm là yêu cầu rằng việc tìm ra hai thông điệp đầu vào
như vậy thì phải là rất khó khăn về mặt thời gian và tính toán.
2


Hình 1: Ánh xạ giữa thông điệp và giá trị băm không phải là song ánh
1.1.2. Cấu trúc của hàm băm mật mã
Theo định nghĩa hàm băm mật mã ta thấy rằng bản chất của hàm băm chính
là một hàm nén. Hiện tại hầu hết các hàm băm mật mã áp dụng cấu trúc hàm
băm Merkle- Damrgard (MD5, SHA-1, SHA-2) hoặc cấu trúc Sponge (SHA-3).
Cấu trúc Mekle-Damrgard:

3


Hình 2: Cấu trúc Mekle-Damrgard
Hầu hết các hàm băm không có khóa được thiết kế như các xử lý lặp để
băm các đầu vào có độ dài hữu hạn tùy ý, bằng việc xử lý các khối đầu vào có
độ dài cố định, như chỉ ra trong hình 2.
Đầu vào hàm băm là một thông báo có độ dài hữu hạn tùy ý được chia
thành các khối bằng nhau có độ dài cố định là -bit. Bước tiền xử lý này thường
gồm việc thêm các bit mở rộng (gọi là padding) để thông báo có độ dài bit là
bội của độ dài khối , và (vì các lý do an toàn) thường gồm 1 khối hoặc một phần
khối để chỉ độ dài bit của đầu vào chưa được thêm vào. Mỗi khối được dùng
làm đầu vào có độ dài cố định cho hàm băm bên trong (hàm nén của , thực hiện
tính một kết quả trung gian mới có độ dài bit là ) là một hàm của kết quả trung
gian trước đó có độ dài là bit và khối đầu vào tiếp theo .
Gọi là ký hiệu phần kết quả sau bước thứ , xử lý chung cho hàm băm lặp
với đầu vào có thể được mô tả như sau:

; ,;
được coi như biến chuỗi giữa bước và bước , và là giá trị khởi đầu được
định nghĩa trước hay gọi là giá trị khởi đầu . Biến đổi đầu ra có lựa chọn được
dùng trong bước cuối cùng để ánh xạ biến chuỗi bit thành một kết quả bit (,
thường là ánh xạ đồng nhất .
Cấu trúc Sponge:
Cấu trúc Sponge là một cấu trúc mới, được nghiên cứu và áp dụng trong
hàm SHA-3, cấu trúc này sẽ được trình bày chi tiết ở chương 2.
1.2. Phân loại các hàm băm mật mã

Dựa trên những tham số đầu vào của các hàm băm, các hàm băm được phân
thành hai lớp. Gồm lớp hàm băm có khóa và lớp hàm băm không có khóa.
1.2.1. Lớp các hàm băm không có khóa
Một hàm băm không có khóa là một hàm : , trong đó:
1. là một tập các thông báo có thể
2. là một tập hữu hạn các giá trị tóm lược thông báo hoặc các thẻ xác thực
có thể.
Một số họ hàm băm hiện có thuộc lớp này như: Họ hàm băm MD (MD2,
MD4, MD5), họ hàm băm SHA (SHA-1, SHA-224, SHA-256, SHA-384..,
SHA-3).
4


1.2.2. Lớp các hàm băm có khóa
Các hàm băm có khóa được sử dụng để xác thực thông báo và thường được
gọi là các thuật toán tạo mã xác thực thông báo (MAC)
1.2.2.1 Định nghĩa hàm băm có khóa:
Một họ hàm băm có khóa là một bộ bốn () thỏa mãn các điều kiện sau đây:
1. là một tập các thông báo có thể.
2. là một tập hữu hạn các giá trị tóm lược thông báo hoặc các thẻ xác thực

có thể.
3. là không gian khóa, là một tập hữu hạn các khóa có thể.
4. Đối với mỗi khóa , có một hàm băm . Mỗi : .
Trong định nghĩa ở trên, có thể là một tập hữu hạn hoặc vô hạn; luôn luôn
là một tập hữu hạn. Nếu là một tập hữu hạn, thì hàm băm đôi khi được gọi là
hàm nén (compression function). Trong trường hợp này, chúng ta luôn giả thiết
rằng và thường giả thiết với điều kiện mạnh hơn là . Điều này có nghĩa là không
thể tránh khỏi các va chạm. Nếu hàm là ngẫu nhiên theo nghĩa tất cả các đầu ra
là đồng xác suất thì có khoảng các đầu vào ánh xạ tới mỗi đầu ra (là số bit đầu
vào, là số bit đầu ra, ) và 2 đầu vào được chọn ngẫu nhiên sẽ có cùng đầu ra với
xác suất (không phụ thuộc vào ).
1.2.2.2. Mã xác thực thông báo
Định nghĩa mã xác thực thông báo (MAC-Message Authentication Code)
Thuật toán mã xác thực thông báo là một họ các hàm được tham số hóa bởi
một khóa bí mật , với các tính chất:
a. Tính chất dễ tính toán: với một hàm đã biết, cho trước một giá trị và
một đầu vào , là dễ tính toán. Kết quả này gọi là giá trị MAC hoặc MAC.
b. Tính chất nén: ánh xạ một đầu vào có độ dài bit tùy ý hữu hạn thành
một đầu ra có độ dài bit cố định .
c. Tính chất kháng tính toán: cho trước không hoặc nhiều cặp text-MAC ,
không thể tính toán để tìm một cặp text-MAC bất kỳ cho một đầu vào mới (bao
gồm cả khả năng với nào đó).
Kỹ thuật xác thực bằng thuật toán MAC được mô tả chung như sau: Giả sử
có hai thực thể tham gia liên lạc được gọi là và . Hai thực thể và phải chia sẻ
một khóa bí mật chung . Khi cần gửi một thông báo cho , thì , tính mã xác thực
thông báo như một hàm của thông báo và khóa:
5


Trong đó: là thông điệp đầu vào, là khóa bí mật đã chia sẻ, MAC là mã xác

thực thông báo. Thông báo được nối với giá trị MAC và được truyền cho người
nhận. Người nhận xác thực thông báo này bằng cách tính lại MAC từ thông báo
nhận được bằng khóa bí mật đã chia sẻ, sau đó so sánh với MAC nhận được
kèm theo thông báo. Nếu hai giá trị này giống nhau thì thông báo được xác thực.
Do chỉ có người gửi và người nhận biết khóa bí mật , do đó không ai khác có thể
tạo được MAC hợp lệ. Hơn nữa, bất kỳ việc sửa đổi thông báo ban đầu cũng sẽ
tạo ra một MAC khác và nó sẽ không được xác thực.
Mã xác thực thông báo dựa trên hàm băm (Hash based Message
Authentication Code-HMAC): Một hàm băm (như SHA) không được thiết kế để
sử dụng như một hàm MAC và không thể được sử dụng trực tiếp cho mục đích
xác thực thông báo, vì nó không dựa trên một khóa bí mật. Đã có một số đề xuất
cho sự kết hợp của một khóa bí mật vào một thuật toán băm hiện tại. Cách tiếp
cận này tạo ra một hàm MAC và được ký hiệu là HMAC. HMAC đã được sử
dụng trong một số ứng dụng an toàn như IPSEC, SSL… và HMAC cũng đã
được ban hành như một tiêu chuẩn NIST (FLIP 198).
1.3 Các ứng dụng cơ bản của hàm băm mật mã

Hàm băm mật mã được đánh giá là một thuật toán mật mã linh hoạt nhất. Nó
được sử dụng trong nhiều ứng dụng an toàn và các giao thức Internet. Sau đây là
một số ứng dụng quan trọng của hàm băm mật mã:
Xác thực thông báo: Xác thực thông báo làm một cơ chế được sử dụng để
xác thực tính toàn vẹn của một thông báo. Xác thực thông báo đảm bảo rằng dữ
liệu nhận được là chính xác giống như khi nó được gửi (tức là không bị sửa đổi,
chèn, xóa hay phát lại), và trong nhiều trường hợp định danh của người gửi là
được bảo vệ. Khi một hàm băm được sử dụng để cung cấp cơ chế xác thực
thông báo, giá trị hàm băm thường được gọi là một mã băm. Có một số phương
pháp sử dụng mã băm để cung cấp cơ chế xác thực thông báo như hình 3:
Theo sơ đồ 3 (a): hai thực thể liên lạc và có một khóa bí mật đã chia sẻ.
Khi cần gửi một thông báo cho , thì tính mã băm . Mã băm được nối vào thông
báo và được mã hóa bằng khóa bí mật để tạo bản mã truyền cho . Người nhận

xác thực thông báo này như sau: trước tiên giải mã bản mã nhận được bằng
khóa bí mật đã chia sẻ, sau đó tính lại mã băm từ thông báo và so sánh với mã
băm nhận được kèm theo thông báo. Nếu hai giá trị này giống nhau thì thông
báo được xác thực. Do chỉ có người gửi và người nhận biết khóa bí mật , do đó
thông báo phải đến từ và không bị sửa đổi trái phép. Trong lược đồ này, mã băm
được sử dụng để đảm bảo tính xác thực thông báo, còn hàm mã hóa được sử
dụng để đảm bảo tính bí mật của thông báo.
6


Hình 3: Mô hình sử dụng hàm băm để xác thực thông báo
Theo sơ đồ 3 (b), duy nhất mã băm được mã hóa bằng mật mã khóa bí mật.
Điều này sẽ làm giảm gánh nặng xử lý cho những ứng dụng không cần giữ bí mật
thông báo, mà chỉ cần đảm bảo tính toàn vẹn của thông báo.
Theo sơ đồ 3 (c), duy nhất hàm băm được sử dụng để xác thực thông báo. Kỷ
thuật này yêu cầu hai thực thể liên lạc và phải chia sẻ một tham số bí mật . tính
giá trị băm trên và như sau: và bổ sung vào thông báo gửi cho . Do cũng có tham
số bí mật nên có thể tính lại giá trị băm để xác thực. Hơn nữa, tham số bí mật
không được gửi đi nên đối phương không thể sửa đổi thông báo mà không bị phát
hiện.
7


Theo sơ đồ 3 (d), một hàm mã hóa khóa bí mật được bổ sung vào sơ đồ trên để
đảm bảo thêm tính bí mật của thông báo.
Chữ ký số: Chữ ký số là một chuỗi số, kết quả của phép biến đổi mật mã trên
thông báo nhằm cung cấp một phương tiện để triển khai tính xác thực của nguồn
gốc thông báo, tính toàn vẹn của dữ liệu và tính không thể chối bỏ của người ký.
Khi hàm băm được sử dụng trong lược đồ chữ ký số, giá trị băm của thông báo
được mã hóa bởi một khóa riêng của người gửi. Bất kỳ ai, biết khóa công khai của

người gửi đều có thể xác thực tính toàn vẹn của thông báo. Hình 4 mô tả 2 phương
pháp sử dụng giá trị băm để cung cấp một chữ ký số.

S

Hình 4: Mô hình sử dụng hàm băm trong lược đồ chữ ký số
•

Các ứng dụng khác:
Lưu trữ mật khẩu
Hầu hết các ứng dụng phần mềm ngày nay đều có chứng thực người sử
dụng. Nghĩa là để sử dụng ứng dụng, người sử dụng phải qua một cơ chế chứng
thực tên người sử dụng và mật khẩu.
Giả sử mật khẩu được lưu giữ dưới dạng thông thường, không mã hóa, tại
một nơi nào đó trên máy tính cá nhân hay máy chủ, trong một tập tin dữ liệu hay
trong hệ quản trị cơ sở dữ liệu. Như vậy sẽ xuất hiện một nguy cơ là một người
khác có thể mở được tập tin dữ liệu hoặc cơ sở dữ liệu, và xem trộm được mật
khẩu. Như vậy mật khẩu không thể được giữ bí mật tuyệt đối.
Phương pháp bảo vệ mật khẩu hiệu quả nhất hiện nay là dùng hàm băm. Khi
người sử dụng đăng ký mật khẩu, giá trị băm của mật khẩu được tính bằng một
hàm băm nào đó (SHA-1, SHA-2…) Giá trị băm đươc lưu trữ vào tập tin hay cơ
sở dữ liệu. Vì hàm băm là một chiều, nên dù biết được giá trị băm và loại hàm
băm, kẻ tấn công cũng không thể suy ra được mật khẩu. Khi người sử dụng đăng
nhập, mật khẩu đăng nhập được tính giá trị băm và so sánh với giá trị băm đang
8


lưu trữ. Do tính chống trùng, chỉ có một mật khẩu duy nhất có giá trị băm tương
ứng, nên không ai khác ngoài người sử dụng có mật khẩu đó mới có thể đăng
nhập ứng dụng.

thì

•

Hình 5: Chứng thực mật khẩu, theo tính
chống trùng,
nếu thì
Ứng dụng tải dữ liệu trên mạng
Khi chúng ta tải dữ liệu trên mạng, nếu chất
lượng mạng không tốt thì có thể xảy ra lỗi trong quá
trình tải làm cho tập tin tại máy khách khác với tập tin
trên máy chủ.

Hàm băm có thể giúp chúng ta phát hiện ra những trường hợp lỗi như vậy
bằng cách sau:
Gọi tập tin cần tải xuống trên máy chủ là , và giá trị băm theo MD5 của tập
tin mà máy chủ đã tính sẵn và cung cấp trên trang điện tử là (có thể xem bằng
mắt). Gọi là tập tin mà người sử dụng tải được tại máy tính sử dụng. Người sử
9


dụng sẽ tính giá trị MD5 cho tập tin . Như vậy nếu trùng khớp với thì theo tính
chống trùng của hàm băm, tập tin hoàn toàn giống tập tin và quá trình tải
xuống không xảy ra lỗi.

Internet

1.4 Giới thiệu một số họ hàm băm phổ biến

Đã có rất nhiều hàm băm được công bố và được sử dụng trong thực tế (bao

gồm cả các hàm băm có khóa và các hàm băm không có khóa). Bảng 1 cho
chúng ta một số hàm băm với các thông số tương ứng:
Thuật
toán

Kích
thước đầu
vào (bit)

Kích
thước đầu
ra (bit)

MD4
MD5
SHA-1
SHA-256
SHA-384
SHA-512

<
<
<
<
<
<

128
128
160

256
384
512

Kích
thước
trạng thái
trong (bit)
128
128
160
256
512
512

Kích
thước
khối (bit)

Kích
thước
word (bit)

Độ an
toàn (bit)

512
512
512
512

1024
1024

32
32
32
32
64
64

64
64
80
128
192
256

Bảng 1. Một số hàm băm phổ biến và thông số tương ứng
•
Hàm băm MD5
Ronald Rivest là người đã phát minh ra các hàm băm MD2, MD4 (1990) và
MD5 (1991). Hàm băm MD5 được phát triển lên từ MD4 và trước đó là MD2, là
một cải tiến của MD4 và là hàm băm được sử dụng rất rộng rãi, nguyên tắc thiết
kế của hàm băm MD5 là nguyên tắc chung cho rất nhiều hàm băm khác.
Hàm băm MD5 nhận thông báo đầu vào có độ dài tối đa bit. Thông báo này
được thực hiện đệm sau đó chia thành các khối con với độ dài 512 bit. Các khối
con 512 bit này sẽ là đầu vào của thuật toán băm, bên trong thuật toán mỗi khối
512 bit lại được chia ra 16 khối 32 bit và đi qua bốn vòng lặp của MD5.
Mỗi khối thống báo con 512 bit qua xử lý sẽ cho đầu ra là một khối 128 bit,
chính là giá trị băm của thông báo đầu vào tương ứng. Theo cấu trúc MekleDamrgard giá trị băm này sẽ là đầu vào để xử lý khối thông báo con tiếp theo.

10


Tiếp tục xử lý, đầu ra cuối cùng là một khối 128 bit, là giá trị băm nhận được
của thông báo đầu vào.
Hàm băm MD5 đã được cải tiến để khắc phục những hạn chế và những điểm
mất an toàn trong MD4. Mặc dù năm 1993, Den Boer và Bosselaers đã tìm ra
các va chạm trong việc sử dụng hàm nén của MD5, nhưng tới nay MD5 vẫn
được sử dụng rộng rãi trong các ứng dụng thực tế do độ an toàn nó mang lại vòn
đủ đáp ứng nhu cầu.
•
Họ các Hàm băm SHA
Thuật toán băm an toàn (SHA) đã được NIST và NSA thiết kế xây dựng. Sau
đó được NIST đề xuất làm chuẩn hàm băm an toàn (SHS) bao gồm các thuật toán
băm: SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 và SHA-3.
Các thuật toán hàm băm SHA gồm 2 bước: tiền xử lý và tính toán giá trị
băm.
Bước tiền xử lý bao gồm các thao tác:
- Mở rộng thông báo.
- Phân tích thông báo đã mở rộng thành các khối -bit
- Khởi tạo giá trị băm ban đầu.
Bước tính toán giá trị băm bao gồm các thao tác:
- Làm lần các công việc sau:
+ Tạo bảng phân bố thông báo (message schedule) từ khối thứ .
+ Dùng bảng phân bố thông báo cùng với các hàm, hằng số, các thao
tác trên word để tạo giá trị băm .
- Sử dụng giá trị băm cuối cùng để tạo thông báo rút gọn.
Thông báo được đệm thêm các bit theo quy tắc đệm trước khi thực hiện
băm, nhằm đảm bảo thông báo đầu vào cho thuật toán băm có độ dài là bội số
512 hoặc 1024 bit, tùy thuộc vào thuật toán băm.

Tiếp theo thông báo sẽ được phân tích thành khối bit. Đối với các hàm băm
SHA-1, SHA-256 giá trị là 512 bit, và đối với các hàm băm SHA-384 và SHA256 thì là 1024 bit. Những khối thông báo con này sẽ là đầu vào cho thuật toán
băm.s
1.5. Một số kiểu tấn công lên hàm băm mật mã

1.5.1. Tấn công dựa trên “Nghịch lý ngày sinh”
Giả sử : là một hàm băm; hữu hạn và giả sử . Đặt , . Nếu chọn ngẫu
nhiên phần tử khác nhau từ tập là ,,… rồi tính …, sau đó xác định xem
11


có xảy ra đụng độ hay không, nghĩa là xem có tồn tại , ( thỏa mãn hay
không.
Áp dụng kết quả của bài toán ngày sinh nhật đã biết ta có: Nếu các mã
băm có độ dài 64 bit, tức là và nếu chọn thì xác suất gặp đụng độ sẽ là
50%.
Việc sản sinh ra phần tử ,,… nằm trong khả năng tính toán thực tế nên bài
toán ngày sinh chỉ ra cho ta thấy rằng việc dùng mã băm có độ dài 64 bit là
không an toàn.
Với hàm băm cụ thể như SHA-1, độ dài đầu ra của mã băm là 160 bit, nên
nếu chọn giá trị băm thì xác suất gặp đụng độ là 50%, các nhà mã thám luôn
mong muốn tìm ra một tấn công lên SHA-1 với độ phức tạp dưới phép toán
băm (gọi là giới hạn lý thuyết cho hàm băm độ dài 160 bit), năm 2005 ba nhà
khoa học Trung Quốc Xiaoyun Wang, Yiqun Lisa Yin và Hongbo Yu đã giới
thiệu một phương pháp tìm va chạm của hàm băm SHA-1 với độ phức tạp tính
toán nhỏ hơn phép toán băm.
1.5.2. Phương pháp tấn công gặp nhau ở giữa (meet in the middle attack)
Giả sử chúng ta dùng hàm băm có độ dài giá trị băm là bit.
Kẻ tấn công muốn đưa thông báo để A ký, nhưng A không muốn ký. Trong
khi đó, A sẵn sàng ký thông báo . Kẻ tấn công sản sinh ra biến thể khác nhau

của M (có nội dung thống nhất) và biến thể khác nhau của .
Hai tập thông báo đó được so sánh để tìm ra cặp có cùng mã băm. Xác suất
thành công của phương pháp này đã được chứng minh là khoảng 86%.
Kẻ tấn công sau khi tìm được cặp và có cùng giá trị băm sẽ đưa cho A ký,
và gửi cùng chữ ký này cho người nhận Người nhận chắc chắn tin tưởng vào
chữ ký đó sau khi đã kiểm tra cẩn thận.
Nếu bit thì giá trị này nằm trong khả năng tính toán. Vì vậy kẻ tấn công rất
dễ đạt được mục đích.
Trên đây ta thấy độ dài của mã băm rất quan trọng. Độ dài giá trị băm 64 bit
là không an toàn. Đó là lý do vì sao các hàm băm có ứng dụng thực tế đều có độ
dài đầu ra từ 128 bit trở lên.
1.5.3. Tấn công vét cạn
Trong khoa học máy tính tấn công vét cạn là phương thức tấn công tổng
quát nhất, nội dung chính của kiểu tấn công này trong việc tấn công hàm băm là:
Kẻ tấn công có trong tay giá trị băm của thông điệp với độ dài là bit, thực
hiện chọn ngẫu nhiên một thông điệp và tính xem hay không, nếu chúng bằng
nhau có nghĩa là kể tấn công đã thành công, còn nếu không thì kẻ tấn công tìm
một bức thông điệp khác và tính giá trị băm cho đến khi tìm được va chạm. Giả
12


sử mã băm là một biến ngẫu nhiên có phân phối chuẩn thì xác suất để tìm được
thông điệp thỏa mãn là .
Ta thấy kiểu tấn công này không phụ thuộc vào cấu trúc của hàm băm hay
chiều dài thông điệp đầu vào mà nó chỉ phụ thuộc vào chiều dài đầu ra của hàm
băm, do đó để nâng cao tính bảo mật chúng ta cần cho đầu ra càng lớn thì tính
bảo mật càng cao. Tuy nhiên cách tấn công này không hiệu quả vì không gian
đầu vào quá lớn, trong trường hợp xấu nhất thuật toán duyệt qua tất cả các đầu
vào có thể để tìm được va chạm, điều này là không thể.
Yêu cầu tài nguyên cho việc tấn công này bùng nổ tổ hợp với chiều dài đầu

ra của hàm băm, như vậy có nghĩa là nếu ta tăng chiều dài đầu ra càng lớn thì
khả năng để tấn công thành công càng thấp, gọi chiều dài đầu ra là bit thì có thể
chúng ta cần thử tới lần để tìm được một tấn công thành công.
CHƯƠNG II. TÌM HIỂU HÀM BĂM SHA-3
2.1. Các phép hoán vị Keccak-p

Các phép hoán vị Keccak-p được mô tả với hai tham số:
1) Độ dài cố định của các chuỗi được hoán vị, được gọi là độ rộng của phép
hoán vị.
2) Số lượng các phép lặp của một phép chuyển đổi nội bộ, được gọi là một
vòng.

b
Độ rộng được ký hiệu là và số lượng vòng được ký hiệu là . Phép hoán vị
Keccak-p với vòng và độ rộng được ký hiệu là keccak-]; phép hoán vị được
∈{25,50,100, 200, 400,800,1600}
nr
định nghĩa cho bất kỳ
và số nguyên dương
bất kỳ.
Rnd
Một vòng của phép hoán vị Keccak-p được ký hiệu là
, bao gồm một
chuỗi năm phép biến đổi được gọi là các ánh xạ bước (step mapping). Tập các
giá trị bit đầu vào của phép hoán vị đi qua các biến đổi liên tiếp của các ánh xạ
bước, cuối cùng thành đầu ra được gọi là trạng thái (state).
2.1.1. Trạng thái và mảng trạng thái
a. Khái niệm trạng thái và mảng trạng thái

13



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.
Trạng thái cho phép hoán vị keccak-] bao gồm bit. Bản đặc tả thông số kỹ
thuật trong bộ tiêu chuẩn này bao gồm hai đại lượng khác liên quan đến: và ,
lần lượt ký hiệu là và . Bảy giá trị có thể của những biến này đối với các phép
hoán vị Keccak-p được cho trong các cột của bảng dưới đây:
b
w
l

25
1
0

50
2
1

100
4
2

200
8
3

400

16
4

800
32
5

1600
64
6

Bảng 2: Độ rộng và số liệu liên quan đến phép hoán vị Keccack-p
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ạ bước là một mảng
5× 5× w
bit
.
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
b −1
đánh số từ 0 đến
, do đó:

S = S [0] || S [1] || ...|| S [b − 2]|| S [b − 1]


Nếu

A

.

5×5× w

là ký hiệu của một mảng bit
biểu diễn trạng thái, thì chỉ số
( x, y , z )
0 ≤ x < 5,0 ≤ y < 5
0≤ zcủa nó là bộ ba số nguyên
sao cho
và
. Bit
( x, y , z )
A[ x, y, z ]
tương ứng với
được ký hiệu là
. 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.
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à .
b. Thành phần của mảng trạng thái
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
b = 200
hơn được minh họa trong hình 7 dưới đây đối với trường hợp

, do đó
14


w=8

. Các mảng con hai chiều được gọi là các sheet, plane và slice, và các
mảng con một chiều được gọi là clumn (cột), row (hàng) và lane trong đó:

b/5

Sheet: là một mảng con gồm
Plane: là một mảng con gồm

bit theo trục tọa độ

b/5

Lane: là một mảng con gồm

cố định.

y
bit theo trục tọa độ

slice: là một mảng con gồm 25 bit theo trục tọa độ

b / 25

x

z

cố định.

cố định.

bit theo các trục tọa độ

y
Row (hàng): là một mảng con gồm 5 bit theo tọa độ

và

Column (cột): là một mảng con gồm 5 bit với trục tọa độ

z
x

x

y
và

cố định.

cố định
và

z

không đổi.

Hình 6: Thành phần của mảng trạng thái tổ chức theo nhiều chiều
15


c. Chuyển từ chuỗi sang mảng trạng thái

b
là ký hiệu của một chuỗi bit biểu diễn cho trạng thái của phép
Keccak − p[b, nr ]
A
hoán vị
. Mảng trạng thái tương ứng ký hiệu là được định
nghĩa như sau:
Cho

S

( x, y , z )
Đối với mọi bộ ba

sao cho

0 ≤ x < 5,0 ≤ y < 5

và

0≤ z

, ta có

A[ x, y, z ] = S [ w(5 y + x) + z ]
.

Ví dụ, nếu

b = 1600

A[0,0,0]=S[0]
A[0,0,1]=S[1]
A[0,0,2]=S[2]

, thì

w = 64

, do đó:

A[1,0,0]=S[64]
A[1,0,1]=S[65]
A[1,0,2]=S[66]

M

A[2,0,0]=S[128]
A[2,0,1]=S[129]
A[2,0,2]=S[130]

M

A[3,0,0]=S[192]
A[3,0,1]=S[193]
A[3,0,2]=S[194]

M

M

A[0,0,62]=S[62]
A[0,0,63]=S[63]

A[1,0,62]=S[126]
A[1,0,63]=S[127]

A[2,0,62]=S[190]
A[2,0,63]=S[191]

A[3,0,62]=S[254]
A[3,0,63]=S[255]

A[4,0,0]=S[256]
A[4,0,1]=S[257]
A[4,0,2]=S[258]

A[0,1,0]=S[320]
A[0,1,1]=S[321]
A[0,1,2]=S[322]

A[1,1,0]=S[384]
A[1,1,1]=S[385]
A[1,1,2]=S[386]

A[2,1,0]=S[448]
A[2,1,1]=S[449]
A[2,1,2]=S[450]

và

M
A[4,0,62]=S[318]
A[4,0,63]=S[319]

M

M

A[0,1,62]=S[382]
A[0,1,63]=S[383]

M

A[1,1,62]=S[446]
A[1,1,63]=S[447]

A[2,1,62]=S[510]
A[2,1,63]=S[511]

…

d. Chuyển từ mảng trạng thái sang chuỗi

A
Cho
là ký hiệu của một mảng trạng thái. Biểu diễn chuỗi tương ứng ký
S
A
hiệu là có thể được cấu trúc từ các lane và plane của như sau:
(i, j )
Đối với mỗi cặp số nguyên
Lane(i, j )
:

sao cho

0≤i<5

và

0≤ j<5

, xác định chuỗi

Lane(i, j ) = A[i, j ,0] || A[i, j,1] || A[i, j ,2] || ...|| A[i, j, w − 2] || A[i, j, w − 1]

.
16


Ví dụ, nếu

b = 1600

, thì

w = 64

do đó:

Lane(0,0) = A[0,0,0] || A[0,0,1] || A[0,0,2] || ...|| A[0,0,62] || A[0,0,63]
Lane(1,0) = A[1,0,0] || A[1,0,1] || A[1,0,2] || ...|| A[1,0,62] || A[1,0,63]
Lane(2,0) = A[2,0,0] || A[2,0,1] || A[2,0,2] || ...|| A[2, 0,62] || A[2,0,63]
…

j
Đối với mọi số nguyên

sao cho

0≤ j<5

Plane( j )
, định nghĩa chuỗi

Plane( j ) = Lane(0, j ) || Lane(1, j ) || Lane(2, j ) || Lane(3, j ) || Lane(4, j )

như sau:
.

Do đó

S = Plane(0) || Plane(1) || Plane(2) || Plane(3) || Plane(4)

Ví dụ, nếu

b = 1600

, thì

w = 64

.

, do đó

S = A[0,0,0] || A[0,0,1]|| A[0,0, 2] || ...|| A[0,0,62] || A[0,0,63]
|| A[1,0,0]|| A[1,0,1]|| A[1,0, 2] || ...|| A[1,0,62] || A[1,0,63]
|| A[2,0,0] || A[2,0,1] || A[2,0,2] || ... || A[2,0,62]|| A[2,0,63]
|| A[3,0,0] || A[3,0,1]|| A[3,0, 2] || ...|| A[3,0,62]|| A[3,0,63]
M
|| A[3, 4,0] || A[3,4,1] || A[3,4,2] || ...|| A[3, 4,62]|| A[3, 4,63]
|| A[4,4,0] || A[4,4,1] || A[4,4,2]|| ...|| A[4, 4,62] || A[4, 4,63].
e. Quy ước nhãn cho mảng trạng thái
Trong sơ đồ trạng thái đi kèm với các thông số kỹ thuật của ánh xạ bước,
lane tương ứng với tọa độ ,, nằm ở trung tâm của slice. Nhãn đầy đủ của các tọa
độ , và trong những hình vẽ này được chỉ ra trong hình 8 ở bên dưới.

17

Hình 7: Các trục x, y và z cho sơ đồ ánh xạ bước
2.1.2. Ánh xạ bước
Năm ánh xạ bước trong một vòng keccak-] được ký hiệu là ,,,χ và.
Thuật toán đối với từng ánh xạ bước có một mảng trạng thái đầu vào ký hiệu
là A và trả lại một mảng trạng thái cập nhật đầu ra ký hiệu là A’. Kích thước của
trạng thái là một tham số bỏ qua ký hiệu, vì b luôn được xác định khi gọi tới ánh
xạ bước.
Ánh xạ có đầu vào thứ hai là : một số nguyên được gọi là chỉ số vòng, ký
hiệu là , Các ánh xạ khác không phụ thuộc vào chỉ số vòng.
a. Mô tả ánh xạ
Thuật toán 1:

θ ( A)

Đầu vào: mảng trạng thái
Đầu ra: mảng trạng thái

A

A'

.

.

Các bước:

( x, z )
1

Đối với tất cả các cặp

sao cho

0≤ x<5

và

0≤ z
, có

C[ x, z ] = A[ x,0, z ] ⊕ A[ x,1, z ] ⊕ A[ x, 2, z ] ⊕ A[ x,3, z ] ⊕ A[ x,4, z ].
( x, z )
2

Đối với tất cả các cặp

sao cho

0≤ x<5

và

0≤ z
có
18

D[ x, z ] = C[( x − 1) mod5, z ] ⊕ C[( x + 1) mod5,( z − 1) mod w].
( x, y , z )
3

Đối với tất cả các cặp
0≤ z , có

sao cho

0 ≤ x < 5,0 ≤ y < 5

và

A '[ x, y , z ] = A[ x, y , z ] ⊕ D[ x, z ].

Hình 8: Minh họa cho
Ánh xạ bước

θ

Tác dụng của

θ

áp dụng cho một bit đơn

được minh họa trong hình 8 ở trên.

θ

là XOR từng bit trong trạng thái với tính chẵn lẻ của hai
A[ x0 , y0 , z0 ]
x
cột trong mảng. Cụ thể, đối với bit
, trục của một trong các cột là
x0 − 1mod5
x0 + 1mod 5
x
z
, với trục giống , trong đó trục của cột khác là
, với
z0 − 1mod w
∑
z
trục là
. Trong hình 8, ký hiệu tổng
chỉ ra tính chẵn lẻ tức là
XOR tổng tất cả các bit trong cột.
b. Mô tả ánh xạ
Thuật toán 2:

ρ ( A)

Đầu vào: mảng trạng thái

A

.
19

A'

Đầu ra: mảng trạng thái

.

Các bước:

A '[0,0, z ] = A[0,0, z ].

0≤ z
z

1. Với mọi sao cho
, có
( x, y ) = (1,0).
2. Cho
t
3. Với từ 0 đến 23:
a. Với mọi sao cho , có
A '[x, y, z ] = A[ x, y,( z − (t + 1)(t + 2) / 2) mod w]

;

b. Cho =
4. Trả lại
Tác dụng của

A'

.

ρ

là xoay một độ dài bit của mỗi lane, được gọi là offset phụ
y
x
thuộc vào các trục tọa độ và cố định của lane. Tương tự, với mỗi bit trong
z
lane, tọa độ được thay đổi bằng cách cộng offset theo mô-đun kích thước của
lane. Offset của mỗi lane là kết quả của phép tính toán trong bước 3a của thuật
toán 2 được liệt kê trong bảng 2.

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

Bảng 3: Offset của

ρ

ρ

w=8
với trường hợp
được cho trong hình 9 bên
y
x
dưới. Quy ước ghi nhãn cho các trục và trong hình 9 được chỉ ra một cách
rõ ràng trong hình 6, tương ứng với các hàng và các cột trong bảng 3. Ví dụ,
Một ví dụ minh họa cho

20


A[0,0]

lane
ở chính giữa của sheet chính giữa và lane
cùng của sheet ngoài cùng bên phải.

Hình 9: Minh họa cho

ρ

đối với

A[2,3]

nằm ở vị trí dưới

b = 200

Đối với mỗi lane trong hình 9, chấm đen biểu thị bit có tọa độ

ρ

z

bằng 0, và

khối màu xám biểu diễn vị trí của bit đó sau khi thực hiện . Các bit khác của
lane dịch offset giống nhau và phép dịch là phép dịch vòng. Ví dụ, offset cho
A[1,0]
z
lane
là 1, nên bit cuối cùng với tọa độ là 7, dịch chuyển sang vị trí
z
trước với tọa độ bằng 0. Do đó, offset có thể giảm theo mô-đun độ lớn của
A[3,2]
lane; ví dụ: lane cho
, tại vị trí trên cùng của sheet ngoài cùng bên trái, có
một offset của 153 mod 8, tức là 1.
c. Mô tả ánh xạ
Thuật toán 3:

π ( A)

Đầu vào: mảng trạng thái
Đầu ra: mảng trạng thái

A

A'

.

.

Các bước:
1. Với mọi bộ ba ,, sao cho , và

0≤ z
, có

A '[x, y, z ] = A[( x + 3 y ) mod5, x, z ].

21


2. Trả lại

A'

.

π
Tác dục của là sắp xếp lại vị trí của các lane như được minh họa cho bất
kỳ slice trong hình 10 bên dưới. Quy ước cho việc dán nhãn các trục tọa độ được
x= y=0

mô tả trong hình 6 ở trên; ví dụ, bit với tọa độ
nằm ở chính giữa của
slice.

Hình 10: Minh họa cho
d. Mô tả ánh xạ

π

áp dụng cho một slice đơn

χ

Thuật toán 4:

χ ( A)

Đầu vào: mảng trạng thái
Đầu ra: mảng trạng thái

A

A'

.

.

Các bước:
1. Với mọi bộ ba ,, sao cho , và

0≤ z
, có

A '[x, y, z ] = A[ x, y, z ] ⊕ (( A[( x + 1) mod 5, y, z ] ⊕ 1) ×A[( x + 2) mod5, y, z ]).

2. Trả lại

A'

.

22


Dấu chấm ở phía bên phải của công thức trong bước 1 chính là phép nhân số
nguyên, mà trong trường hợp này tương đương với phép “AND” cho dữ liệu
dạng Boolean.

χ

Tác dụng của là XOR từng bit với một hàm phi tuyến gồm hai bit khác
trong cột như được minh họa trong hình 11 bên dưới.

Hình 11: Minh họa cho
e. Mô tả ánh xạ

χ

áp dụng cho một hàng đơn

ι

ι

Trong bản đặc tả trong thuật toán 7, ánh xạ bước được tham số bằng chỉ
ir
ι
số vòng . Trong bản đặc tả của thuật toán 6, tham số này được xác định là
l +1
bit của một giá trị lane được gọi là hằng số vòng, ký hiệu là RC. Mỗi bit
l +1
trong
bit này được tạo ra bởi một hàm số dựa trên một thanh ghi dịch tuyến
rc
tính có phản hồi. Hàm này ký hiệu là
được mô tả trong thuật toán 5.

rc(t )
Thuật toán 5:
t
Đầu vào: số nguyên .

rc(t )
Đầu ra: bit

.

Các bước:

1. Nếu

t mod 255 = 0

, trả lại 1.
23


2. Cho

R = 10000000.

i

t mod 255
từ 1 đến
, thực hiện:
R = 0 || R
;
a.
R[0] = R[0] + R[8];
b.
R[4] = R[4] + R[8];
c.
R[5] = R[5] + R[8];
d.
R[6] = R[6] + R[8];
e.
R = Trunc8 [R ].

3. Với

d.
4. Trả lại

R[0]

Thuật toán 6:

.

ι ( A, ir )

Đầu vào: mảng trạng thái
chỉ số vòng
Đầu ra: mảng trạng thái

ir

A

;

.

A'

.

Các bước:

( x, y , z )
1. Với mọi bộ ba

sao cho

A '[x, y , z ] = A[ x, y, z ]

0 ≤ x < 5,0 ≤ y < 5

và

0≤ z
, có

.

RC = 0 .
w

2. Cho

j
3. Với

l

RC[2 j − 1] = rc( j + 7ir ).

từ 0 đến , có
A '[0,0,z] = A '[0,0, z ] ⊕ RC[ z ].
0≤ zz
4. Với mọi sao cho
, có
A'
5. Trả lại .
24


Lane(0,0)

ι

Tác dụng của là thay đổi một số bit của
ir
ι
vòng . 24 lane khác không phụ thuộc vào .

phụ thuộc vào chỉ số

2.1.3. Hoán vị Keccak-p[b,nr]
Cho một mảng trạng thái

A

và chỉ số vòng

ir

, hàm vòng Rnd là phép biến
θ , ρ ,π , χ
ι
đổi lấy kết quả từ việc áp dụng các ánh xạ bước
và theo thứ tự đó,
tức là:
Rnd( A, ir ) = ι ( χ (π ( ρ (θ ( A)))), ir ).
Keccak − p[b, nr ]

Phép hoán vị
thể trong thuật toán 7.
Thuật toán 7:

lần lặp của Rnd được mô tả cụ

Keccak − p[b, nr ](S)

Đầu vào: chuỗi

S

số vòng
Đầu ra: chuỗi

bao gồm

nr

S'

b
có độ dài ;
nr

.

b

có độ dài .

Các bước:

S
A
1. Chuyển thành một mảng trạng thái được mô tả trong mục c của mục
2.1.1
ir
2l + 12 − nr
A = Rnd( A, ir )
2l + 12 − 1
2. Với từ
đến
, có
.
S
'
b
A
3. Chuyển

thành một chuỗi
có độ dài được mô tả trong mục d của
mục 2.1.1
4. Trả lại

S'

25