BÀI TẬP LỚN MÔN HỌC
MẬT MÃ

THUẬT TOÁN RC4

Thực hiện:
1. Nguyễn Xuân Khánh
2. Nguyễn Thị Thanh Hương
3. Nguyễn Thị Hoài Trang


THUẬT TOÁN RC4

ii


THUẬT TOÁN RC4

Ý KIẾN CỦA GIẢNG VIÊN
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................

........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................
........................................................................................................................................................................

i


THUẬT TOÁN RC4

MỤC LỤC
Ý KIẾN CỦA GIẢNG VIÊN.................................................................................I
MỤC LỤC............................................................................................................II

ii



THUẬT TOÁN RC4

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT
Viết tắt
CBC
KSA
PDF
PRGA
RC4
SSL
TLS
WEP
WPA

Giải thích
Cipher Block Chaining
Key scheduling algorithm
Portable Document Format
Pseudo-random generation algorithm
Rivest Cipher 4
Secure Sockets Layer
Transport Layer Security
Wired Equivalent Privacy
Wireless Protected Area

iii


THUẬT TOÁN RC4


DANH MỤC CÁC HÌNH VẼ
Hình 3.4.a. Giao diện chính...............................................................................9
Hình 3.4.b. Giao diện form Input......................................................................9
Form mã hóa....................................................................................................10
Hình 3.4.c. Giao diện form mã hóa.................................................................10
Hình 3.4.d. Giao diện form giải hóa................................................................10
Hình 3.5.a. Kết quả từ website rc4.online-domain-tools.com.........................11
Hình 3.5.b. Kết quả từ chương trình................................................................11

iv


THUẬT TOÁN RC4

LỜI MỞ ĐẦU
Ngày nay, thông tin liên lạc đã trở nên rất phổ biến và vô cùng thuận lợi.
Song song với điều này, nhu cầu bảo mật thông tin ngày càng được đặt ra cấp
thiết hơn. Vì vậy, mật mã được nghiên cứu rộng rãi, được ứng dụng nhiều hơn
và được nói đến nhiều hơn bao giờ hết.
Nhóm đã lựa chọn RC4 trong rất nhiều kiểu mật mã khác để nghiên cứu bởi
vì tốc độ và sự đơn giản của nó, hiệu quả triển khai thực hiện trong cả phần
mềm và phần cứng là rất dễ dàng để phát triển. Mục tiêu đặt ra khi thực hiện đề
tài ngày gồm:
- Tìm hiểu tổng quan về thuật toán RC4.
- Phân tích và làm rõ được tính bảo mật của thuật toán RC4.
- Xây dựng được một chương trình minh họa thuật toán.
Nhóm cũng xin cảm ơn sự hướng dẫn tận tình của thầy giáo bộ môn cả về
chuyên môn cũng như định hướng. Vì kiến thức còn hạn hẹp nên trong quá trình
thực hiện đề tài không thể tránh khỏi thiếu sót. Rất mong nhận được nhận sự góp

ý của thầy cô để đề tài có thể hoàn thiện hơn nữa.

v


MẬT MÃ HỌC NÂNG CAO

THUẬT TOÁN RC4

CHƯƠNG 1. GIỚI THIỆU VỀ THUẬT TOÁN RC4
1.1. Lịch sử RC4
RC4 có tên gọi đầy đủ là Rivest Cipher 4 và được thiết kế bởi Ron Rivest
của hãng bảo mật RSA Security vào năm 1987.
RC4 bước đầu là một bí mật thương mại, nhưng vào tháng 9 năm 1994, một
mô tả của nó được gửi ẩn danh với Cypherpunks. Nó sớm được đăng lên nhóm
tin sci.crypt, và sau đó có mặt trên nhiều trang Web khác. Các mã rò rỉ đã được
xác nhận có kết quả mã hóa giống với RC4 ban đầu. Bởi vì các thuật toán đã bị
rò rỉ cho nên RC4 không còn là một bí mật thương mại. Do cái tên RC4 đã được
đăng ký thương hiệu nên nó đã được gọi tắt là ARCFOUR hoặc ARC4. RC4 là
mã dòng được sử dụng rộng rãi nhất và được dùng trong các giao thức như:
SSL, TLS (để bảo vệ lưu lượng Internet) và WEP, WPA (để đảm bảo an toàn
mạng không dây).
Các yếu tố chính trong thành công của RC4 là do tốc độ và sự đơn giản của
nó. Hiệu quả triển khai thực hiện trong cả phần mềm và phần cứng là rất dễ
dàng để phát triển.
1.2. Mô tả thuật toán
Các thuật toán RC4 là khá đơn giản và dễ dàng để giải thích. Một khóa có
độ dài từ 8 tới 2048 bit được sử dụng để khởi tạo 256 byte trạng thái S, với các
phần tử S[0], S[1],…,S[255]. Vào mọi thời điểm, S chứa một hoán vị của tất cả
các số 8 bit (từ 0 đến 255). Đối với mã hóa và giải mã, l byte K được tạo ra từ S

bằng cách chọn một trong 256 phần tử một cách có hệ thống. Khi mỗi giá trị của
K được tạo ra, các phần tử trong S một lần nữa được hoán vị.
Hoán vị ban đầu sử dụng thuật toán lập lịch khóa (KSA). Sau khi bước này
được hoàn thành, l byte K được sinh ra bởi thuật toán sinh số giả ngẫu nhiên
(PRGA).

1


THUẬT TOÁN RC4

1.2.1. Giai đoạn khởi tạo
Để bắt đầu, các mục của S được thiết lập bằng các giá trị từ 0 đến 255 theo
thứ tự tăng dần, đó là S[0] = 0, S[1] = 1,…, S[255]=255. Một mảng tạm thời T
cũng được tạo ra. Mảng T là mảng được sao chép từ K và sau đó K được lặp đi
lặp lại nhiều lần cho đến khi lấp đủ 256 byte. Các hoạt động sơ bộ có thể được
mô tả với thuật toán như sau:
for i = 0 to 255 do
S[i] = i;
T[i] = K[i mod lengthK];
endfor

Với lengthK là kích thước khóa K.
1.2.2. Thuật toán lập lịch khóa (KSA)
Tiếp theo, chúng ta sử dụng T để lập lịch khóa của S. Điều này liên quan đến
việc bắt đầu với S[0] và đi tới S[255], và ở mỗi S[i], hoán đổi S[i] với một byte
khác trong S được định sẵn theo thuật toán này:
j = 0;
for i = 0 to 255 do
j = (j + S[i] + T[i]) mod 256;

HoanVi(S[i], S[j]);
endfor

Thuật toán được quyết định bởi T[i] nhưng hoạt động duy nhất trên S là
hoán đổi. Vì là phép hoán vị nên S vẫn còn chứa tất cả các số từ 0 đến 255.
1.2.3. Thuật toán sinh số giả ngẫu nhiên (PRGA)
Một khi lập lịch khóa hoàn thành thì khóa K đầu vào không còn được sử
dụng. Sinh số liên quan đến việc xoay vòng qua tất cả các phần tử của S[i], và ở
mỗi S[i], hoán đổi S[i] với một byte khác trong S theo thuật toán được quyết
2


THUẬT TOÁN RC4

định bởi các giá trị hiện tại của S. Sau đó đến S[255], quá trình này tiếp tục, bắt
đầu lại một lần nữa tại S[0].
i, j = 0;
while (true)
i = (i + 1) mod 256;
j = (j + S[i]) mod 256;
HoanVi(S[i], S[j]);
t = (S[i] + S[j]) mod 256;
k = S[t];
end while;

1.2.4. Mã hóa và giải mã
Để mã hóa, XOR giá trị k với các byte tiếp theo của bản gốc P.
Để giải mã, XOR giá trị k với các byte tiếp theo của bản mã C.

3



THUẬT TOÁN RC4

CHƯƠNG 2. TÍNH BẢO MẬT CỦA THUẬT TOÁN RC4
2.1. Độ an toàn
Không giống như mã dòng hiện đại (ví dụ eSTREAM), RC4 không tạo một
giá trị ngẫu nhiên riêng biệt đi cùng với khóa. Điều này có nghĩa là nếu một
khóa dài hạn được sử dụng để mã hóa cho nhiều dòng, thì phải miêu tả cách gắn
giá trị ngẫu nhiên như nào để tạo dòng khóa cho RC4. Một cách tiếp cận để giải
quyết vấn đề này, để “làm tươi” khóa, người ta băm khóa dài hạn cùng với một
giá trị ngẫu nhiên. Tuy nhiên, nhiều ứng dụng sử dụng RC4 chỉ đơn giản là nối
khóa với giá trị ngẫu nhiên. Khóa lập lịch yếu của RC4 đem lại một loạt các vấn
đề nghiêm trọng.
Đáng chú ý là, mã dòng RC4, là một thuật toán mã hóa thông thường, lại
kháng lại được tấn công BEAST (tìm ra vào năm 2011) vào giao thức TLS 1.0,
khai thác điểm yếu được biết đến trong chế độ xích mã khối (CBC), gồm tất cả
các hệ mã khối hỗ trợ bởi TLS 1.0. Trong năm 2013 đã có một kịch bản tấn công
mới được đề xuất bởi AlFardan, Bernstein, Paterson, Poettering và Schuldt sử
dụng sai số thống kê mới trong bảng khóa của RC4, để phục hồi bản rõ với số
lượng lớn lần mã hóa của TLS.
2.2. Độ chệch Roos và việc thiết lập lại khóa từ hoán vị
Trong năm 1995, Andrew Roos đã quan sát thực nghiệm rằng byte đầu tiên
của dòng khóa có quan hệ với 3 byte đầu tiên của khóa và một ít byte đầu tiên
của hoán vị sau KSA có quan hệ với tổ hợp tuyến tính nào đó của các byte khóa.
Nhưng độ chệch này vẫn còn chưa được chứng minh cho đến năm 2007, khi
Gautam Paul, Siddheshwar Rathi và Subhamoy Maitra chứng minh tưng quan
dòng khóa – khóa và trong công trình khác Gautam Paul, Subhamoy Maitra
chứng minh các tương quan hoán vị - khóa. Công trình sau cũng sử dụng các
tương quan hoán vị - khóa để thiết kế thuật toán đầu tiên nhằm thiết lập lại khóa

đầy đủ từ hoán vị cuối cùng sau KSA mà không cần giả thiết nào vào khóa hoặc
véc tơ khởi tạo. Thuật toán này có xác suất thành công không đổi trong một thời
gian là căn bậc hai của độ phức tạp tìm kiếm vét cạn khóa. Sau đó, nhiều công
trình khác đã được thực hiện để thiết lập lại khóa từ các trạng thái bên trong.
4


THUẬT TOÁN RC4

Subhamoy Maitra và Gautam Paul cũng chứng tỏ rằng những độ chệch kiểu
Roos vẫn còn ngay cả khi người ta xét xác chỉ số hoán vị lồng nhau như S[S[i]]
hoặc S[S[S[i]]]. Những kiểu chệch này được dùng trong một vài phương pháp
thiết lập lại khóa sau này nhằm tăng xác suất thành công.
2.3. Những đầu ra chệch của RC4
Dòng khóa được sinh bởi RC4 bị chệch theo nhiều mức độ khác nhau đối
với những dãy nhất định làm cho nó có thể bị tổn thương trước các tấn công
phân biệt. Tấn công tốt nhất loại này thuộc về Itsik Mantin và Adi Shamir,
những người đã chỉ ra rằng byte ra thứ hai của mật mã bị chệch từ 0 với xác suất
1/128 (thay cho 1/256). Nếu byte thứ 3 của trạng thại gốc là 0, và byte thứ 2
không bằng 2 thì byte ra thứ hai luôn luôn là 0. Sự chệch như thế có thể bị phát
hiện bằng cách quan sát chỉ 256 byte.
Souradyuti và Bart Preneel của COSIC đã chứng tỏ rằng các byte thứ nhất
và thứ hai của RC4 cũng bị chệch. Số các mẫu cần thiết để phát hiện chệch này
là 225 byte.
Scott Fluhrer và David McGrew cũng chứng tỏ những tấn công như thế,
chúng đã phân biệt dòng khóa với dòng ngẫu nhiên khi cho a gigabyte đầu ra.
Đặc trưng đầy đủ của bước đơn PRGA của RC4 được thực hiện đầy đủ bởi
nhiều tác giả. Khi xem xét tất cả các hoán vị, họ đã chứng minh rằng phân phối
của các đầu ra là không đều khi cho i và j, và như một hệ quả, thông tin về j luôn
luôn bị rò rỉ vào đầu ra.

2.4. Những hệ mật dựa trên RC4
RC4 được sử dụng khá rộng rãi. Có thể liệt kê ra một số hệ mật như sau:
WEP, WPA (thuật toán mặc định), BitTorrent protocol encryption, Secure
Sockets Layer (tùy chọn), Microsoft Point-to-Point Encryption, Secure Shell
(tùy chọn), Remote Desktop Protocol, Kerberos (tùy chọn), PDF, Skype (ở dạng
đã sửa đổi), trong đó một hệ mật được lưu ý với “tùy chọn” thì RC4 là một trong
một vài mật mã mà hệ thống này có thể được cấu hình để sử dụng.

5


THUẬT TOÁN RC4

CHƯƠNG 3. THIẾT KẾ CHƯƠNG TRÌNH
3.1. Phân tích yêu cầu
- Thiết kế một chương trình mã hóa và giải mã bằng thuật toán RC4
- Chương trình nhận đầu vào từ file “input.txt”, xuất kết quả ra 2 file
“encrypt.txt” và “decrypt.txt”. Tất cả các file này nằm trong cùng thư mục
với file chương trình. Dữ liệu các file được biểu diễn dưới dạng chuỗi HEX
viết thường.
- File “input.txt” gồm 2 dòng:
+ Dòng 1: Khóa.
+ Dòng 2: Khối dữ liệu bản rõ.
- File “encrypt.txt” gồm x dòng:
+ Dòng 1: Khóa.
+ Dòng 2: Dòng khóa mã hóa.
+ Dòng 3: Bản rõ.
+ Dòng 4: Bản mã.
+ Dòng 5..x: Dòng khóa mã hóa được ngắt thành từng đoạn 16 byte, mỗi
đoạn lưu trên một dòng.

- File “decrypt.txt” gồm y dòng:
+ Dòng 1: Khóa
+ Dòng 2: Dòng khóa giải mã.
+ Dòng 3: Bản mã.
+ Dòng 4: Bản rõ.

6


THUẬT TOÁN RC4

+ Dòng 5..y: Dòng khóa giải mã được ngắt thành từng đoạn 16 byte, mỗi
đoạn lưu trên một dòng.
- Có khả năng tạo khóa và bản rõ với các giá trị ngẫu nhiên. Hoặc có thể nhập
đầu vào theo các ký tự ASCII và chuyển đổi qua lại sang HEX.
3.2. Thiết kế chương trình
Chương trình có một Form chính để chứa 3 nút: Tạo file Input, Mã hóa, Giải
mã.
• Form Input:
- Có các Button để tạo ra khóa và bản rõ với các giá trị ngẫu nhiên.
- Có thể chuyển đổi qua lại giữa ASCII và HEX.
- Có Button lưu file để xuất ra file đúng định dạng yêu cầu.
•

Form Mã Hóa:
- Mặc định sẽ tải dữ liệu từ file input hoặc có thể chọn file tùy ý.
- Có Button mã hóa đồng thời xuất ra file “encrypt.txt” đúng định dạng yêu
cầu.
- Hiển thị giá trị của khóa và bản rõ từ dữ liệu đầu vào.
- Hiển thị giá trị vector T, S ban đầu, S sau lập lịch khóa và số giả ngẫu

nhiên dùng để mã hóa.
- Hiển thị được bản mã.

• Form Giải Mã:
- Tương tự với form Mã Hóa nhưng không hiển thị các vector T và S.
3.3. Cài đặt thuật toán
Chương trình được triển khai trên ngôn ngữ .NET và sử dụng bộ công cụ
Visual Studio để lập trình.
7


THUẬT TOÁN RC4

• Khởi tạo 2 mảng T và S:
For i As Integer = 0 To 255
arrKeyT(i) = arrKey(i Mod ((strKey.Length / 2)))
arrKeyS(i) = i
Next

• Thuật toán lập lịch khóa:
Dim j As Integer = 0
For i As Integer = 0 To 255
j = (j + arrKeyS(i) + arrKeyT(i)) Mod 256
Dim bytehoanvi As Byte
bytehoanvi = arrKeyS(i)
arrKeyS(i) = arrKeyS(j)
arrKeyS(j) = bytehoanvi
Next

• Thuật toán sinh số giả ngẫu nhiên:

Dim arrKeyFinal(arrText.Length - 1) As Byte
Dim dem As Integer = 0
Dim ii As Integer = 0
Dim jj As Integer = 0
Dim lenght As Integer = arrText.Length
While lenght > 0
ii = (ii + 1) Mod 256
jj = (jj + arrKeyS(ii)) Mod 256
Dim bytehoanvi As Byte
bytehoanvi = arrKeyS(ii)
arrKeyS(ii) = arrKeyS(jj)
arrKeyS(jj) = bytehoanvi
arrKeyFinal(dem) = arrKeyS((Convert.ToInt16(arrKeyS(ii)) +

8


THUẬT TOÁN RC4
Convert.ToInt16(arrKeyS(jj))) Mod 256)
dem = dem + 1
lenght = lenght - 1
End While

• Mã hóa:
Dim arrEncrypt(arrText.Length - 1) As Byte
For i As Integer = 0 To arrText.Length - 1
arrEncrypt(i) = arrText(i) Xor arrKeyFinal(i)
Next

Do việc mã hóa bản rõ chỉ qua một phép toán XOR nên việc giải mã chúng

ta có thể sử dụng lại các thuật toán cũ của mã hóa.
3.4. Thiết kế giao diện
• Giao diện chính

Hình 3.4.a. Giao diện chính.
• Form tạo file input

Hình 3.4.b. Giao diện form Input.

9


THUẬT TOÁN RC4

• Form mã hóa

Hình 3.4.c. Giao diện form mã hóa.
• Form giải mã

Hình 3.4.d. Giao diện form giải hóa.
3.5. Kiểm tra tính đúng đắn của kết quả mã hóa
Sau khi thiết kế và cài đặt chương trình hoàn tất. Nhóm đã sử dụng những
vector test để kiểm tra tính đúng đắn của kết quả mã hóa. Các khóa và bản rõ ở
dạng mã ASCII, dòng khóa và bản mã trong hệ cơ số 16.
Key
Key
Wiki
Secret

Keystream

EB9F7781B734CA72A719...
6044DB6D41B7...
04D46B053CA87B59...

Plaintext
Plaintext
pedia
Attack at

Ciphertext
BBF316E8D940AF0AD3
1021BF0420
45A01F645FC35B383552544B9BF5

dawn
Nguồn />
10


THUẬT TOÁN RC4

Kết quả mã hóa của chương trình hoàn toàn trùng khớp với 3 vector test
trên. Tuy nhiên nhóm đã sử dụng thêm một công cụ mã hóa RC4 online
() để kiểm thử thêm nhiều trường hợp khác
và nhận được kết quả hoàn toàn trùng khớp.

Hình 3.5.a. Kết quả từ website rc4.online-domain-tools.com.

Hình 3.5.b. Kết quả từ chương trình.


11


THUẬT TOÁN RC4

KẾT LUẬN
Báo cáo này tìm hiểu về thuật toán RC4. Qua đó chúng ta thấy thuật toán
RC4 khá đơn giản, ý nghĩa từng bước rõ ràng, logic và cũng dễ dàng triển khai.
Đồng thời RC4 cũng tỏ ra an toàn với phương pháp thám mã cơ bản bản là thám
mã tuyến tính và thám mã vi phân.
Trong thời gian qua, nhóm em đã tìm hiểu tổng quan được về RC4, phân
tích được tính bảo mật của thuật toán. Thông qua những tìm hiểu trên nhóm em
còn xây dựng được một chương trình minh họa thuật toán đó. Tuy nhiên do thời
gian có hạn, kiến thức chưa được sâu nên bản báo cáo này còn nhiều thiếu sót
mong các bạn và thầy giáo có những nhận xét và ý kiến để giúp cho bản báo cáo
của nhóm chúng em hoàn thiện thêm.

12


THUẬT TOÁN RC4

TÀI LIỆU THAM KHẢO
[1] TS. Nguyễn Ngọc Cương, TS. Nguyễn Tuấn Anh, ThS. Trần Thị Lương,
Giáo trình Mật mã ứng dụng trong an toàn thông tin, Học viện kỹ thuật mật
mã, 2013, trang 13-14 76-81.
[2] RC4 Algorithm, 01/2015
[3] RC4 - Symmetric Ciphers Online, />01/2015
[4] Vishwas Gagrani, Presentation over Cryptographic Primitives (RC4),
01/2015


13