BỘ THƠNG TIN VÀ TRUYỀN THƠNG
HỌC VIỆN BƯU CHÍNH VIỄN THƠNG
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

ĐỒ ÁN TỐT NGHIỆP

NGHIÊN CỨU THUẬT TỐN
CHACHA20 - POLY1305

Ngành: Cơng nghệ thông tin
Chuyên ngành:
Mã số:

Sinh viên thực hiện:
TRẦN PHƯƠNG THẢO

Hà Nội, 2022


2


MỤC LỤC
MỤC LỤC.................................................................................................................i
DANH MỤC KÝ HIỆU VIẾT TẮT.......................................................................iii
DANH MỤC HÌNH VẼ............................................................................................v
LỜI CẢM ƠN.........................................................................................................vii
LỜI NĨI ĐẦU.......................................................................................................viii
CHƯƠNG 1. TỔNG QUAN MÃ DỊNG VÀ MÃ XÁC THỰC THÔNG BÁO. . .1
1.1. Tổng quan mã dòng.........................................................................................1
1.1.1. Khái niệm mã dòng...............................................................................1

1.1.2. Đặc trưng mã dòng và ứng dụng trong bảo mật thông tin....................2
1.1.3. Một số mã xác thực thông báo phổ biến hiện nay.................................5
1.2. Tổng quan mã xác thực thông báo.................................................................13
1.2.1. Khái niệm mã xác thực thông báo.......................................................13
1.2.2. Một số mã xác thực thông báo phổ biến.............................................14
1.3. Mã dòng xác thực và ứng dụng......................................................................16
1.4. Tổng kết chương 1.........................................................................................18
CHƯƠNG 2. MÃ DÒNG XÁC THỰC CHACHA20-POLY1305.......................20
2.1. Mã dịng ChaCha20.......................................................................................20
2.2. Mã xác thực thơng báo Poly1305..................................................................25
2.3. Mã dịng xác thực ChaCha20 - Poly1305......................................................29
2.4. Phân tích một số tấn công phổ biến lên ChaCha20-Poly1305.......................32
2.4.1. Tấn công kênh kề................................................................................32
2.4.2. Thám mã lượng sai..............................................................................33
2.4.3. Thám tuyến tính và tấn cơng phân biệt...............................................41
2.4.4. Phân tích phỏng đốn và xác định.......................................................42
2.5. Đánh giá độ an toàn của ChaCha20 – Poly1305...........................................42
2.6. Khả năng ứng dụng AEAD ChaCha20-Poly1305.........................................46
2.7. Tổng kết chương 2.........................................................................................46

1


CHƯƠNG 3. XÂY DỰNG ỨNG DỤNG PHẦN MỀM MÃ HÓA DỮ LIỆU VỚI
CHACHA20-POLY1305........................................................................................48
3.1. Thuyết minh mã nguồn cài đặt ứng dụng......................................................48
3.1.1. Sinh tham số........................................................................................48
3.1.2. Hàm mã hóa........................................................................................49
3.1.3. Hàm giải mã........................................................................................51
3.2. Thử nghiệm chương trình..............................................................................55

3.2.1. Sinh tham số........................................................................................55
3.2.2. Mã hóa và giải mã dữ liệu...................................................................55
3.3. Đánh giá hiệu năng chương trình...................................................................59
KẾT LUẬN.............................................................................................................60
TÀI LIỆU THAM KHẢO......................................................................................61
PHỤ LỤC................................................................................................................63

2


DANH MỤC KÝ HIỆU VIẾT TẮT
Ký hiệu

Thuật ngữ

Ý nghĩa

AE

Authenticated Encryption

Mã hóa xác thực

AEAD

Authenticated Encryption with
Associated Data

Mã hóa xác thực với dữ liệu liên
quan


AES

Advanced Encryption Standard

Tiêu chuẩn mã hóa tiên tiến

BC

Block Counter

Bộ đếm khối

CBC

Cipher Block Chaining

Chế độ mã khối xâu chuỗi

CCD

Column Chaining
Distinguishers

Phân biệt chuỗi cột

CCM

Cipher/Counter Mode


CMAC

Cipher Message Authentication
Code

Mã xác thực thông báo mã hóa

DES

Data Encryption Standard

Tiêu chuẩn mã hóa dữ liệu

DH

Diffie - Hellman

Thỏa thuận khóa Diffie Hellman

DHE

Diffie – Hellman Ephemeral

Diffie – Hellman tạm thời

ECDH

Elliptic Curve Diffie - Hellman

Thỏa thuận khóa Diffie-Hellman

trên đường cong Elliptic

DCDHE

Elliptic Curve Diffie – Hellman
Ephemeral

Thỏa thuận khóa Diffie-Hellman
tạm thời trên đường cong
Elliptic

ECDSA

Elliptic Curve Digital Signature
Algorithm

Hệ mật dựa trên đường cong
Elliptic

FIPS

Federal Information Processing
Standards

Tiêu chuẩn xử lý thông tin liên
bang

GCM

Galois/Counter Mode


3


HMAC

Keyed-Hash Messasge
Authentication Code

Mã xác thực thông báo sử dụng
hàm một chiều có khóa

IV

Initialization Vector

Vector khởi tạo

MAC

Message Authenticated Code

Mã xác thực thông báo

NIST

National Institute of Standards
and Technology

Viện tiêu chuẩn và công nghệ

quốc gia của Mỹ

PNV

Probabilistic Neutral Vectors

Vector xác suất trung tính

PRF

Pseudo-Random Function

Hàm giả ngẫu nhiên

PSN

Packet Sequence Number

Số thứ tự gói

PSK

Pre-Shared Key

Khóa chia sẻ trước

RSA

Ron Rivest, Adi Shamir, Len
Adleman


SHA

Secure Hash Algorithm

Thuật toán băm an toàn

SSL

Secure Sockets Layer

Giao thức tầng socket bảo mật

VoIP

Voice over IP

WEP

Wired Equivalent Privacy

Tiêu chuẩn bảo mật tương đương
mạng có dây

4


DANH MỤC HÌNH
Hình 1.1: Sơ đồ mã hóa mật mã dịng.......................................................................2
Hình 1.2: Mơ hình mật mã khóa đối xứng................................................................2

Hình 1. 3: Thông tin Alice gửi Bob bị Oscar bắt được và phát lại............................4
Hình 1. 4: Quá trình sinh dãy A5/1...........................................................................8
Hình 1. 5: Sơ đồ xác thực bằng MAC.....................................................................14
Hình 1. 6: Lược đồ tạo mã xác thự băm HMAC.....................................................15
Hình 1. 7: Lược đồ tạo mã xác thực CMAC...........................................................16
Y
Hình 2.1: Lược đồ hoạt động hàm Quarter Round..................................................21
Hình 2.2: Sơ đồ hoạt động ChaCha20.....................................................................22
Hình 2.3: Sơ đồ hoạt động của Poly1305 – Khởi tạo _r_ và xử lý nhóm 16 byte. .26
Hình 2.4: Sơ đồ tạo thẻ tag - Thêm vào 16 byte cuối của khóa..............................27
Hình 2.5. Sơ đồ tổng qt AEAD ChaCha20-Poly1305.........................................30
Hình 2.6: Sơ đồ hoạt động thời gian thực ChaCha20-Poly1305.............................31
Hình 2.7: Sơ đồ mã hóa Payload.............................................................................31
Hình 2.8: Sơ đồ tính tốn MAC..............................................................................32
Hình 2. 9: Hàm quarter round của Salsa20..............................................................35
Hình 3. 1: Thực hiện sinh tham số...........................................................................55
Hình 3. 2: Test Vector của RFC 7539......................................................................56
Hình 3. 3: Tạo file plain text...................................................................................56
Hình 3. 4: Tạo file secret key..................................................................................56
Hình 3. 5: Tạo file nonce.........................................................................................56
Hình 3. 6: Tạo file Authenticated Data....................................................................57
Hình 3. 7: Tiến hành mã hóa...................................................................................57
Hình 3. 8: File cipher text sau khi mã hóa thành cơng............................................58
Hình 3. 9: Bản mã trong RFC 7539.........................................................................58
Hình 3. 10: Tiến hành giải mã.................................................................................58
Hình 3. 11: Kết quả giải mã.....................................................................................59

5



DANH MỤC BẢ
Bảng 2.1: Bảng thống kê các dạng tấn công...........................................................43
Bảng 2. 2: So sánh AES và ChaCha20....................................................................44
Bảng 2.3: So sánh GHASH và Poly1305................................................................45
Bảng 2.4: So sánh AES-GCM và ChaCha20-Poly1305..........................................45
YBảng 3. 1: So sánh hiệu năng AES-GCM và ChaCha-Poly1305.........................59

6


LỜI NĨI ĐẦU
Trước đây, mật mã đối xứng khó đảm bảo được cả tính bí mật và tính xác
thực trong cùng thuật tốn mã hóa, để đảm bảo tính xác thực, một thuật toán chữ
ký số hoặc MAC được dùng cùng với thuật tốn mã hóa nhưng tính xác thực
nguồn gốc thông điệp được hỗ trợ khá yếu. Để tăng cường tính xác thực này thì
cần một thuật tốn mã hóa có xác thực nhằm cung cấp đồng thời cả tính bí mật,
xác thực và tồn vẹn cho thơng báo trong một thuật tốn duy nhất, loại bỏ những
bước khơng cần thiết của việc sử dụng thuật toán MAC riêng biệt.
Thuật toán AEAD ChaCha20-Poly1305 được giới thiệu vào tháng 5 năm
2015 trong RFC7539. AEAD ChaCha20-Poly1305 là một cấu trúc mã hóa dữ liệu
liên kết (AEAD); là sự kết hợp của thuật tốn mã hóa dịng ChaCha20 và thuật
tốn xác thực một lần Poly1305. Cả hai thuật toán ChaCha20 và Poly1305 đều
được thiết kế bởi D.J Bernstein.
Sự kết hợp của hai thuật tốn ChaCha20 và Poly1305 cung cấp các thuộc
tính an toàn cho cấu trúc AEAD ChaCha20-Poly1305. Mặc dù, các tấn cơng kênh
kề có thể áp dụng đối với ChaCha. Tuy nhiên, có thể dễ dàng khắc phục các tấn
cơng này trong cài đặt thực tế, vì vậy AEAD ChaCha20-Poly 1305 được xem là an
toàn để sử dụng trong hệ thống thông tin hiện nay.
Đồ án này sẽ đi nghiên cứu, tìm hiểu thuật tốn mã dịng xác thực
ChaCha20-Poly1305 bao gồm: sơ đồ hoạt động, thuật toán, cách thức hoạt động và

đánh giá độ an tồn của thuật tốn này.
SINH VIÊN THỰC HIỆN ĐỒ ÁN

TRẦN PHƯƠNG THẢO

7


CHƯƠNG 1
TỔNG QUAN MÃ DỊNG VÀ MÃ XÁC THỰC THƠNG BÁO
1.1. Tổng quan mã dịng
1.1.1. Khái niệm mã dịng
Thuật tốn mã hóa dịng (Stream ciphers): là một dạng mã hóa đối xứng,
trong đó dữ liệu đầu vào được mã hóa từng bit một. Các thuật tốn dịng có tốc độ
nhanh hơn các thuật toán khối, được dùng khi khối lượng dữ liệu cần mã hóa chưa
được biết trước, ví dụ trong kết nối khơng dây. Có thể coi thuật tốn dịng là thuật
tốn khối với kích thước mỗi khối là 1 bit. Một số thuật tốn dịng thơng dụng :
RC4, A5/1, A5/2, Chameleon.
Mã dịng có các đặc tính sau:
 Kích thước một đơn vị mã hóa: gồm k bít. Bản rõ được chia thành các đơn
vị mã hóa: P  …

(: k bit)

 Một bộ sinh dãy số ngẫu nhiên: dùng một khóa K ban đầu để sinh ra các số
ngẫu nhiên có kích thước bằng kích thước đơn vị mã hóa:
StreamCipher(K) 

(: k bit)


 Mỗi số ngẫu nhiên được XOR với đơn vị mã hóa của bản rõ để được
bản mã.
= ⊕ , = ⊕ …; …
Quá trình giải mã được thực hiện ngược lại, bản mã C được XOR với dãy số
ngẫu nhiên S để cho ra lại bản rõ ban đầu: = ⊕ , = ⊕ ...
Đối với mã dòng, các số được sinh ra phải đảm bảo một độ ngẫu nhiên nào
đó (chu kỳ tuần hồn dài):

1


Hình 1.1: Sơ đồ mã hóa mật mã dịng
Như vậy có thể thấy mã hóa dịng tương tự như mã hóa Vigenere và mã hóa
OneTime Pad. Điểm quan trọng nhất của các mã dòng là bộ sinh số ngẫu nhiên.
Nếu chọn khóa có chiều dài ngắn như mã hóa Vigenere thì khơng bảo đảm an tồn,
cịn nếu chọn khóa có chiều dài bằng chiều dài bản tin như One-Time Pad thì lại
khơng thực tế. Bộ sinh số của mã dịng cân bằng giữa hai điểm này, cho phép dùng
một khóa ngắn nhưng dãy số sinh ra bảo đảm một độ ngẫu nhiên cần thiết như
khóa của One-time Pad, dù rằng khơng hồn tồn thực sự ngẫu nhiên.
1.1.2. Đặc trưng mã dịng và ứng dụng trong bảo mật thơng tin
Về cơ bản, mật mã dịng là một dạng mật mã khóa đối xứng, cho nên mã
dòng mang đầy đủ các đặc trưng của mật mã khóa đối xứng. Ưu điểm nổi bật của
mã hóa đối xứng là tốc độ lập mã, giải mã khá nhanh chóng. Hiện nay có nhiều
phần mềm thương mại hỗ trợ thuật tốn mã hóa đối xứng hữu hiệu và rất phổ dụng.

Hình 1.2: Mơ hình mật mã khóa đối xứng
Tuy vậy, nhược điểm lớn nhất của thuật tốn mã hóa đối xứng là vấn đề
chuyển giao khóa bí mật giữa các đối tác, đặc biệt là trong mơi trường mở. Ví dụ:
2



việc trao đổi thông điệp giữa Alice và Bob. Bob nhận được thơng điệp đã mã hóa
của Alice, muốn giải mã được thì Bob phải có chìa khóa mã của Alice. Alice khơng
thể chuyển giao khóa mã đồng thời với thơng điệp vì như vậy thì việc mã hóa trở
thành vơ tác dụng. Vì vậy Alice phải dùng một phương pháp nào đó để chuyển
giao khóa giải mã cho Bob trước khi gửi thông điệp. Mà dù dùng phương thức
thông tin nào trong môi trường mở: gửi thư, E-mail, gọi điện thoại v.v. thì vẫn có
nguy cơ có người thứ ba nắm bắt được khóa mã và kết quả vẫn như thế.
Xét trường hợp giao dịch của 2 đối tác Alice và Bob. Giả sử Alice và Bob
“hoàn toàn tin tưởng vào nhau” và trao cho nhau mã khóa đối xứng bằng một
phương pháp đáng tin cậy nào đó (trao tay trực tiếp hoặc có một phương pháp nào
có thể thay thế cho trao tay trực tiếp mà cũng có giá trị tương đương như thế)
và sau đó hai người sử dụng mã khóa truyền các thơng điệp mã hóa cho nhau, ta
thấy rằng:
- Sử dụng mã đối xứng (trong các điều kiện nói trên) đảm bảo được ngun
lý bí mật/riêng tư vì thơng tin khơng thể bị lộ.
- Đảm bảo tính xác thực, tính khơng chối bỏ và tính nhận dạng, những điều
này chủ yếu được thực hiện khi chuyển giao khóa mã cho nhau chứ khơng phải
trong q trình trao đổi thơng điệp mã hóa về sau. Vì giả sử Alice và Bob trực tiếp
trao khóa bí mật K cho nhau và “tin tưởng nhau” là không làm lộ khóa mã cho
người thứ ba, như vậy khi nhận được thơng điệp được mã hóa bởi K, hai đối tác có
thể nhận dạng ra thơng điệp đó chính là do đối tác của mình gửi. Mặt khác nếu Bob
nhận được thơng điệp của Alice mã hóa bởi K thì Alice khơng thể chối bỏ rằng
khơng phải do mình phát hành thơng điệp đó (vì ngồi Bob chỉ có Alice biết khóa
K). Tuy nhiên khi Bob nhận được mà chối là khơng nhận được thì phải do “tính tin
tưởng” giữa hai đối tác chứ khơng phải do khóa K đảm bảo.
- Mã hóa đối xứng khơng đảm bảo tính tồn vẹn dữ liệu. Giả sử thư của
Alice gửi cho Bob đã lọt vào tay Oscar. Oscar khơng hiểu gì về nội dung thơng
điệp nhưng vẫn có thể thêm bớt dữ liệu làm thay đổi, sai lệch nội dung thông điệp
3



rồi vẫn gửi tiếp cho Bob: Bob không thể biết là thơng điệp đã bị thay đổi nội dung
(Có thể do khơng biết khóa mã nên dữ liệu thêm bớt của Oscar có thể làm cho
thơng điệp khơng giải mã được hay là vô nghĩa nhưng Bob vẫn không thể chắc
chắn là có người can thiệp mà vẫn nghĩ là chính do Alice tạo ra như vậy).

Hình 1. 3: Thơng tin Alice gửi Bob bị Oscar bắt được và phát lại
Vì những lý do trên các thuật tốn mã hóa đối xứng loại này là những
phương pháp mã hóa lý tưởng cho một người sử dụng (single user) với mục đích
mã hóa dữ liệu của cá nhân hay tổ chức đơn lẻ để chống xâm nhập của kẻ xấu.
Không phải chỉ có những bí mật về an ninh quốc phịng mà ngay những thơng tin
bí mật trong cơng nghệ, trong thương mại v.v. đều có thể là mục tiêu xâm nhập của
những gián điệp công nghệ, kinh tế, hoặc xâm nhập trực tiếp hoặc sử dụng các biện
pháp như gửi và cài Spyware, Trojan hay các phần mềm độc. Vì vậy cá nhân hay
tổ chức, trước khi lưu giữ các dữ liệu thơng tin quan trọng có thể và nên mã hóa
bằng những khóa mã tự tạo và giữ bí mật khóa cho riêng mình biết. Mã đối xứng
bộc lộ hạn chế khi thông tin mật cần được chia sẻ với một bên thứ hai vì khi đó cần
phải chuyển giao chìa khóa cho đối tác mà việc chuyển giao chìa khóa trong mơi
trường mở có nhiều nguy cơ bị lộ, như vậy việc mã hóa về sau trở thành vơ nghĩa.
Mã đối xứng chỉ có thể sử dụng cho nhiều đối tác (multiple users) với điều
kiện là có thể “mặt đối mặt” để trực tiếp chuyển giao khóa mã trong môi trường tin
cậy hoặc một biện pháp tin cậy nào đó để chuyển giao khóa một cách an tồn. Nếu
khơng có biện pháp chuyển giao khóa an tồn thì hầu như mã đối xứng không đảm
bảo được yêu cầu nào trong 4 nguyên lý bảo mật thông tin gồm: bí mật, tồn vẹn,
xác thực, chống chối bỏ.
4


1.1.3. Một số mã xác thực thông báo phổ biến hiện nay

1) Hệ mật A5/1
A5/1 được dùng trong mạng điện thoại GSM, để bảo mật dữ liệu trong quá
trình liên lạc giữa máy điện thoại và trạm thu phát sóng vơ tuyến. Đơn vị mã hóa
của A5/1 là một bít. Bộ sinh số mỗi lần sẽ sinh ra hoặc bít 0 hoặc bít 1 để sử dụng
trong phép XOR. Để đơn giản, trước tiên chúng ta sẽ xem xét một mơ hình thu nhỏ
của A5/1 gọi là TinyA5/1.
Tiny A5/1
Cơ chế thực hiện của bộ sinh số TinyA5/1 là như sau: Bộ sinh số gồm 3
thanh ghi X, Y, Z. Thanh ghi X gồm 6 bit, ký hiệu là (x 0, x1, …, x5). Thanh ghi Y
gồm 8 bit (y0, y1, …, y7). Thanh ghi Z lưu 9 bit (z0, z1, …, z8). Khóa K ban đầu có
chiều dài 23 bít và lần lượt được phân bố vào các thanh ghi: K  XYZ . Các thanh
ghi X, Y, Z được biến đổi theo 3 quy tắc:
Quay X gồm các thao tác:


t = x2 ⊕ x4 ⊕ x5



xj = xj-1 với j = 5, 4, 3, 2, 1



x0 = t

Ví dụ: giả sử X là 100101, dẫn đến t = 0 ⊕ 0 ⊕ 1 = 1, vậy sau khi quay giá
trị của X là 110010.

5



Quay Y tương tự quay X, quay Y là như sau:


t = y6 ⊕ y7



yj = yj-1 với j = 7, 6, 5, ..., 1



y0 = t

Quay Z:


t = z2 ⊕ z7 ⊕ z8



zj = zj-1 với j = 8, 7, 6, ..., 1



z0 = t

Cho ba bit x, y, z, ta định nghĩa một hàm maj(x, y, z) là hàm “chiếm đa số”,
nghĩa là nếu trong 3 bít x, y, z có từ hai bít 0 trở lên thì hàm trả về giá trị 0, nếu
không hàm trả về giá trị 1.

Tại bước sinh số thứ i, các phép tính sau được thực hiện:
m = maj(x1, y3, z3)
if x1 = m then thực hiện quay X
if y3 = m then thực hiện quay Y
if z3 = m then thực hiện quay Z
Và bit được sinh ra là:
si = x5 ⊕ y7 ⊕ z8
Thực hiện mã hóa bản rõ:
ci = pi ⊕ si
6


Bít si được XOR với bít thứ i trong bản rõ để có được bít thứ i trong bản mã
theo quy tắc của mã dịng. Ví dụ: mã hóa bản rõ P=111 (chữ h) với khóa K là
100101. 01001110.100110000.
Ban đầu giá trị của các thanh ghi X, Y, Z là:
X = 100101
Y = 01001110
Z = 100110000
Bước 0: x1 = 0, y3 = 0, z3 = 1  m = 0  quay X, quay Y
X = 110010
Y = 10100111

 s0 = 0 ⊕ 1 ⊕ 0 = 1

Z = 100110000
Bước 1: x1 = 1, y3 = 0, z3 = 1  m = 1  quay X, quay Z
X = 111001
Y = 10100111


 s1 = 1 ⊕ 1 ⊕ 0 = 0

Z = 010011000
Bước 2: x1 = 1, y3 = 0, z3 = 0  m = 0  quay Y, quay Z
X = 111001
Y = 01010011

 s2 = 1 ⊕ 1 ⊕ 0 = 0

Z = 001001100
Vậy bản mã là C = 111 ⊕ 100 = 011 (chữ D)
A5/1
Về nguyên tắc bộ sinh số A5/1 hoạt động giống như TinyA5/1. Kích thước
thanh ghi X, Y, Z lần lượt là 19, 22, 23 bit. Các bước quay X, Y, Z cụ thể như sau:

7


Quay X:


t = x13 ⊕ x16 ⊕ x17 ⊕ x18



xj = xj-1 với j = 18, 17, 16, …, 1



x0 = t


Quay Y:


t = y20 ⊕ y21



yj = yj-1 với j = 21, 20, 19, …, 1



y0 = t

Quay Z:


t = z7 ⊕ z20 ⊕ z21 ⊕ z22



zj = zj-1 với j = 22, 21, 20, …, 1



z0 = t

Hàm maj được tính trên 3 bít x8, y10, z10. Sau khi quay xong bít sinh ra là:
si = x18 ⊕ y21 ⊕ z22.


Hình 1. 4: Quá trình sinh dãy A5/1

8


Mã hóa A5/1 có thể được thực hiện dễ dàng bằng các thiết bị phần cứng, tốc
độ nhanh. Do đó A5/1 đã từng được sử dụng để mã hóa các dữ liệu real-time như
các dãy bít audio. Ngày nay A5/1 được sử dụng để mã hóa dữ liệu cuộc gọi trong
mạng điện thoại GSM.
2) Hệ mật RC4
RC4 được dùng trong giao thức SSL/TLS để bảo mật dữ liệu trong quá trình
truyền dữ liệu giữa Web Server và trình duyệt Web của máy trạm. Ngồi ra RC4
cịn được sử dụng trong giao thức WEP của mạng Wireless LAN. Để đơn giản, đồ
án cũng sẽ xem xét một mơ hình thu nhỏ của RC4 gọi là TinyRC4.
TinyRC4
Khác với A5/1, đơn vị mã hóa của TinyRC4 là 3 bit. TinyRC4 dùng 2 mảng
S và T mỗi mảng gồm 8 số nguyên 3 bít (từ 0 đến 7). Khóa là một dãy gồm N số
ngun 3 bít với N có thể lấy giá trị từ 1 đến 8. Bộ sinh số mỗi lần sinh ra 3 bít để
sử dụng trong phép XOR. Q trình sinh số của TinyRC4 gồm hai giai đoạn:
Giai đoạn khởi tạo:
/* Khoi tao day so S va T */
for i = 0 to 7 do
S[i] = i;
T[i] = K[i mod N];
next i
/* Hoan vi day S */
j = 0;
for i = 0 to 7 do
j = (j + S[i] + T[i]) mod 8;
Swap(S[i], S[j]);

next i

9


Trong giai đoạn này, trước tiên dãy S gồm các số nguyên 3 bít từ 0 đến 7
được sắp thứ tự tăng dần. Sau đó dựa trên các phần tử của khóa K, các phần tử của
S được hốn vị lẫn nhau đến một mức độ ngẫu nhiên nào đó.
Ví dụ:
Mã hóa bản rõ P = 001000110 (từ “bag”) với khóa K gồm 3 số 2, 1, 3 (N=3)
• Khởi tạo S và T

• Hốn vị S

Q trình thực hiện đến khi i=7 và lúc đó dãy S là 6 0 7 1 2 3 5 4
10


• Giai đoạn sinh số:
i, j = 0;
while (true)
i = (i + 1) mod 8;
j = (j + S[i]) mod 8;
Swap (S[i], S[j]);
t = (S[i] + S[j]) mod 8;
k = S[t];
end while;

Trong giai đoạn này, các phần tử của S tiếp tục được hoán vị. Tại mỗi bước
sinh số, hai phần tử của dãy S được chọn để tính ra số k 3 bít là số được dùng để

XOR với đơn vị mã hóa của bản rõ.
Tiếp tục ví dụ trên, q trình sinh số mã hóa bản rõ “bag” thực hiện như sau:
Bước 0:

Bước 1:

Bước 2:
11


→ s2 =7 = 111[2]

Thực hiện mã hóa:
C = pi ⊕ si = 001.000.110 ⊕ 101.001.111 = 100.001.001 (từ EBB)
RC4
RC4 là hệ mã dịng với chiều dài khóa biến đổi được nêu ra năm 1987, tác
giả của RC4 là Ronald Rivest. Trong sơ đồ của RC4 có sử dụng 2 thanh ghi 8 bits
(bộ đếm) là i và j và một khối thay thế (S-block) có kích thước 256x8 (256 phần
tử, kích thước mỗi phần tử là 8 bit). Giá trị của khối S là một hốn vị nào đó của
các số từ 0 đến 255.
Cơ chế hoạt động của RC4 cũng tương tự TinyRC4 với các đặc tính sau:
- Đơn vị mã hóa của RC4 là một byte 8 bit.
- Mảng S và T gồm 256 số nguyên 8 bit
- Khóa K là dãy gồm N số nguyên 8 bit với N có thể lấy giá trị từ 1 đến 256.
- Bộ sinh số mỗi lần sinh ra một byte để sử dụng trong phép XOR.
Hai giai đoạn của RC4 là:
• Giai đoạn khởi tạo:
/* Khoi tao day so S va T */
for i = 0 to 255 do
S[i] = i;

T[i] = K[i mod N];
next i
/* Hoan vi day S */
j = 0;
for i = 0 to 7 do
j = (j + S[i] + T[i]) mod 8;
Swap(S[i], S[j]);
next i
 Giai đoạn sinh số:
12


i, j = 0;
while (true)
i = (i + 1) mod 256;
j = (j + S[i]) mod 256;
Swap (S[i], S[j]);
t = (S[i] + S[j]) mod 256;
k = S[t];
end while;
Quá trình sinh số của RC4 cũng sinh ra dãy số giả ngẫu nhiên, khó đốn
trước, vì vậy RC4 đạt được mức độ an tồn chấp nhận theo tinh thần của mã hóa
One-Time Pad. Mã hóa RC4 hồn tồn được thực hiện trên các số nguyên một byte
do đó tối ưu cho việc thiết lập bằng phần mềm và tốc độ thực hiện nhanh hơn so
với mã khối.
Trong quá trình sử dụng, bộ đếm i sẽ làm cho nội dung của khối S thay đổi
chậm, còn bộ đếm j sẽ đảm bảo sự thay đổi này là ngẫu nhiên.
Đánh giá:
Ưu điểm của RC4 là thuật toán đơn giản, ý nghĩa từng bước rõ ràng, logic.
RC4 an toàn đối với cả 2 phương pháp thám cơ bản là thám tuyến tính và thám vi

phân. Số trạng thái mà RC4 có thể có là 256!×256×256  21700 . Tốc độ mã đạt rất
cao, so với DES thì RC4 nhanh gấp 10 lần [2].
1.2. Tổng quan mã xác thực thông báo
1.2.1. Khái niệm mã xác thực thông báo
Trong mật mã học, mã xác thực thông báo (Message Authentication Code)
hay MAC đơi khi cịn được gọi là tag, là một mẩu thông tin ngắn như chữ ký được
gửi kèm để làm bằng chứng xác thực.
13


Mã chứng thực thơng điệp (MAC) có thể coi là một dạng checksum của mã
hóa, được tính theo cơng thức MAC = C(M, K), trong đó:
- M là thơng điệp cần tính MAC.
- K là khóa bí mật được chia sẻ giữa người gửi và người nhận.
- C là hàm tính MAC.
Vì MAC có khóa K bít mật giữa người gởi và người nhận nên chỉ có người
gởi và người nhận mới có thể tính được giá trị MAC tương ứng. Mơ hình ứng dụng
MAC để chứng thực thơng điệp như sau:

Hình 1. 5: Sơ đồ xác thực bằng MAC
1.2.2. Một số mã xác thực thông báo phổ biến
Để giúp các nhà phát triển ứng dụng tích hợp MAC vào các sản phẩm khác
nhau, Viện tiêu chuẩn và công nghệ quốc gia của Mỹ (NIST) đưa ra hai chuẩn về
hàm MAC.
1) HMAC

Tiêu chuẩn thứ nhất là Mã xác thực thông báo sử dụng hàm một chiều có
khóa - HMAC (Keyed-Hash Messasge Authentication Code). Chuẩn này mơ tả
phương pháp an tồn chuyển hàm một chiều kháng va chạm mã băm thành mã
MAC. HMAC nguyên bản được đề nghị sử dụng với SHA-1, nó cũng thích hợp sử

dụng với các thuật tốn băm khác (những chứng minh hiện tại chỉ ra rằng kháng va
14


chạm là khơng cần thiết đối với sự an tồn của NMAC (Nested MAC) - một thuật
tốn mà từ đó HMAC được xây dựng. HMAC được định nghĩa như sau:
HMAC(M) = H[(K ⊕ opad) || H[(k ⊕ ipad) || M]]


M là thơng điệp cần trao đổi



K là một khóa bí mật chỉ được biết bởi bên gửi và bên nhận



opad = 0x36, lặp lại nếu cần thiết



ipad = 0x5C, lặp lại nếu cần thiết



|| là phép toán nối chuỗi

Lược đồ băm có thể được nhìn thấy như bên dưới:

Hình 1. 6: Lược đồ tạo mã xác thự băm HMAC

2) CMAC

Chuẩn thứ hai NIST đưa ra là Mã xác thực thông báo mã hóa (Cipher
Message Authentication Code- CMAC). Khơng giống HMAC, CMAC sử dụng mã
15


khối để thực hiện chức năng MAC, thuật toán này rất phù hợp với các ứng dụng bộ
nhớ hạn chế chỉ đủ để dùng cho mã hóa dữ liệu. CMAC dựa trên mã xác thực
thông báo chế độ mã CBC ba khóa (three-key cipher block chaining MAC). MAC
mã hóa nguyên thủy của NIST là CBC-MAC. Trong đó người gửi chỉ cần chọn
khóa độc lập (khơng có quan hệ nhiều) với khóa mã và sử dụng mã theo chế độ
(mode) CBC. Người gửi bỏ qua mọi bản mã giữa, chỉ quan tâm đến bản mã cuối
cùng là thẻ MAC. Khóa dùng cho CBC-MAC khơng trùng (“quan hệ yếu”) với
khóa mã của bản rõ, khi đó MAC là an tồn .

Hình 1. 7: Lược đồ tạo mã xác thực CMAC
1.3. Mã dòng xác thực và ứng dụng
Mã hóa xác thực (Authenticated Encryption hay AE) là hình thức mã hóa
đồng thời đảm bảo tính bảo mật và tính xác thực của dữ liệu. Một giao diện lập
trình điển hình cho việc triển khai mã hóa xác thực cung cấp những chức năng sau:
Mã hóa:


Input: bản rõ, khóa, một header tùy chọn trong bản rõ sẽ khơng được mã

hóa nhưng vẫn được bảo vệ bởi tính xác thực.


Output: bản mã và thẻ xác thực (MAC).


Giải mã:


Input: bản mã, thẻ xác thực và header (nếu có dùng trong mã hóa).

16