ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THANH BÌNH
NGHIÊN CỨU MỞ RỘNG
PHƯƠNG PHÁP MÃ HÓA SỐ HỌC
ỨNG DỤNG TRONG BẢO MẬT DỮ LIỆU
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. LÊ HỒNG LAN
Hà Nội – 2010
2
MỤC LỤC
LỜI CẢM ƠN ..............................................................................Error! Bookmark not defined.
LỜI CAM ĐOAN ........................................................................Error! Bookmark not defined.
MỤC LỤC .................................................................................................................................. 2
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ................................................................ 4
DANH MỤC CÁC BẢNG .......................................................................................................... 5
DANH MỤC CÁC HÌNH VẼ ..................................................................................................... 5
Chƣơng 1. GIỚI THIỆU CHUNG VỀ MÃ HÓA THÔNG TIN .................................................. 8
1.1. Một số thuật ngữ và khái niệm.......................................................................................... 8
1.1.1. Một số thuật ngữ ........................................................................................................ 8
1.1.2. Vì sao cần mã hóa.................................................................................................... 10
1.2. Vài nét về lịch sử ............................................................................................................ 10
1.3. Khái niệm hệ mã hóa ...................................................................................................... 14
1.4. Phân loại hệ mã hóa........................................................................................................ 15
1.4.1. Hệ mã hóa khóa đối xứng ........................................................................................ 15
1.4.1.1. Đặc điểm của hệ mã hóa khóa đối xứng ............................................................ 16
1.4.1.2. Nơi sử dụng hệ mã hóa khóa đối xứng .............................................................. 16
1.4.2. Hệ mã hóa khóa công khai ....................................................................................... 16
1.4.2.1. Đặc điểm của Hệ mã hóa khóa công khai .......................................................... 17
1.4.2.2. Nơi sử dụng Hệ mã hóa khóa đối xứng ............................................................. 17
1.5. Một số hệ mã hóa khóa đối xứng và mã hóa khóa công khai ........................................... 18
1.5.1. Hệ mã hóa đối xứng cổ điển .................................................................................... 18
1.5.1.1. Hệ mã hóa dịch chuyển ..................................................................................... 19
1.5.1.2. Hệ mã hóa thay thế (Hoán vị toàn cục) .............................................................. 19
1.5.1.3. Hệ mã Affine .................................................................................................... 20
1.5.2. Hệ mã hóa khóa công khai ....................................................................................... 21
1.5.2.1. Sơ đồ chung hệ mã hóa khóa công khai ............................................................. 21
1.5.2.2. Hệ mã hóa RSA (Rivest - Shamir - Adleman) ................................................... 21
1.6. Các bài toán về an toàn thông tin .................................................................................... 22
1.7. Thám mã và tính an toàn của các hệ mật mã ................................................................... 23
1.7.1. Vấn đề thám mã ....................................................................................................... 23
1.7.2. Tính an toàn của một hệ mật mã .............................................................................. 24
Chƣơng 2. CƠ SỞ TOÁN HỌC CỦA PHƢƠNG PHÁP MÃ HÓA SỐ HỌC ............................ 26
2.1. Phép chiếu một điểm lên đoạn thẳng............................................................................... 26
2.1.1. Phép chiếu thu nhỏ đồng dạng ................................................................................. 26
2.1.2. Phép biến đổi ngƣợc ................................................................................................ 26
2.2. Phép chiếu một đoạn thẳng lên một đoạn thẳng .............................................................. 27
2.2.1. Phép chiếu thu nhỏ đồng dạng ................................................................................. 27
2.2.1. Phép biến đổi ngƣợc ................................................................................................ 27
2.2.3. Định lý 1 ................................................................................................................. 27
2.3. Một số tính chất của phép chiếu ...................................................................................... 29
2.3.1. Tính chất kết hợp ..................................................................................................... 29
2.3.2. Tính chất chứa trong ................................................................................................ 30
2.3.3. Tính chất chứa trong của phép chiếu ngƣợc ............................................................. 30
Chƣơng 3. CẢI TIẾN PHƢƠNG PHÁP MÃ HÓA SỐ HỌC .................................................... 31
3.1. Giới thiệu phƣơng pháp mã hóa số học ........................................................................... 31
3.2. Thuật toán mã hóa số học truyền thống........................................................................... 32
3.2.1. Thuật toán mã hóa ................................................................................................... 32
3.2.1.1. Thống kê tần suất và xác định miền phân bố của các ký tự trong bản rõ ............ 32
3
3.2.1.2. Ý tƣởng của thuật toán mã hóa ......................................................................... 33
3.2.1.3. Thuật toán mã hóa............................................................................................ 33
3.2.2. Thuật toán giải mã .................................................................................................. 34
3.2.2.1. Hàm g(x) trên [0,D) ......................................................................................... 34
3.2.2.2. Ý tƣởng của thuật toán giải mã ......................................................................... 34
3.2.2.3. Thuật toán giải mã ........................................................................................... 35
3.2.2.4. Chứng minh tính đúng đắn của thuật toán ........................................................ 35
3.2.2.5. Nhận xét về thuật toán giải mã ......................................................................... 36
3.2.3. Ví dụ ...................................................................................................................... 37
3.3. Thuật toán mã hóa số học cải tiến ................................................................................... 39
3.3.1. Thuật toán mã hóa cải tiến ...................................................................................... 39
3.3.2. Thuật toán giải mã cải tiến ...................................................................................... 41
3.4. So sánh độ phức tạp........................................................................................................ 42
3.4.1. Thuật toán mã hóa số học truyền thống ................................................................... 42
3.4.1.1. Thuật toán mã hóa............................................................................................ 42
3.4.1.2. Thuật toán giải mã ........................................................................................... 42
3.4.2. Thuật toán mã hóa số học cải tiến ........................................................................... 42
3.4.2.1. Thuật toán mã hóa............................................................................................ 42
3.4.2.2. Thuật toán giải mã ........................................................................................... 42
3.4.3. So sánh độ phức tạp của 2 phƣơng pháp.................................................................. 42
3.6. Một thuật toán cải tiến khác ............................................................................................ 43
3.6.1. Xác định miền phân bố ........................................................................................... 43
3.6.2. Thuật toán mã hóa cải tiến ...................................................................................... 44
3.6.3. Thuật toán giải mã cải tiến ...................................................................................... 45
3.7. Nghiên cứu tính bảo mật của phƣơng pháp mã hóa số học .............................................. 45
Chƣơng 4. CÀI ĐẶT VÀ THỬ NGHIỆM................................................................................. 53
4.1. Giới thiệu thƣ viện xử lý số nguyên lớn .......................................................................... 53
4.1.1. Cấu trúc của các lớp................................................................................................. 53
4.1.2. Bảng luỹ thừa 2 (bảng h) ......................................................................................... 54
4.2. Thuật toán chuyển đổi .................................................................................................... 55
4.2.1. Thuật toán từ hệ thập phân sang hệ nhị phân ............................................................ 55
4.2.2. Thuật toán từ hệ nhị phân sang hệ thập phân ............................................................ 56
4.3. Thuât toán chia (div, mod) .............................................................................................. 56
4.4. Thuật toán phân rã nhị phân tính luỹ thừa mod ............................................................... 57
4.5. Phƣơng pháp tính logarit ................................................................................................ 59
4.6. Phƣơng pháp tính căn bậc hai ......................................................................................... 60
4.7. Kết quả thử nghiệm ........................................................................................................ 61
KẾT LUẬN .............................................................................................................................. 63
TÀI LIỆU THAM KHẢO ......................................................................................................... 64
4
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
STT
1
2
3
4
5
6
Ký hiệu / Viết tắt
DES
PKC
RAC
RSA
SKC
UCLN
Diễn giải
Data Encryption Standard
Public Key Cryptosystem
Randomized Arithmetic Coding
Rivest - Shamir – Adleman
Secret Key Ctyptosystem
Ƣớc chung lớn nhất
5
DANH MỤC CÁC BẢNG
Bảng 3.1 Bảng tần suất của các ký tự ....................................................................................... 32
Bảng 3.2 Bảng phân bố với D = 1000 và dựa theo tần suất ....................................................... 32
Bảng 3.3 Miền phân bố của các ký tự với bản rõ CABAB ........................................................ 38
Bảng 3.4 Miền phân bố của các ký tự với bản rõ BAABB ........................................................ 46
Bảng 3.5 Miền phân bố với bản rõ CABAB ............................................................................. 49
Bảng 4.1 Dùng để lƣu trữ giá trị thập phân của 2i ...................................................................... 54
Bảng 4.2. Kết quả thử nghiệm ................................................................................................... 62
DANH MỤC CÁC HÌNH VẼ
Hình 1.1 Mô tả phép mã chuyển vị ........................................................................................... 11
Hình 1.2 Bảng đĩa chữ cái ........................................................................................................ 11
Hình 1.3 Minh họa mã khối...................................................................................................... 12
Hình 1.4 Hệ mã tích hợp .......................................................................................................... 13
Hình 1.5 Ví dụ hệ mã tích hợp ................................................................................................. 13
Hình 2.1 Phép chiếu 1 điểm lên 1 đoạn thẳng ........................................................................... 26
Hình 2.2 Phép chiếu 1 đoạn thẳng lên 1 đoạn thẳng.................................................................. 27
Hình 2.3 Chiếu B1B2 lên A1A2 ................................................................................................. 28
Hình 2.4 Chiếu C1C2 lên X1X2 ................................................................................................. 28
Hình 2.5 Chiếu Z1 Z2 lên A1A2 .................................................................................................. 28
Hình 3.1 Minh họa cách phân tách miền phân bố ...................................................................... 47
Hình 3.2 Sơ đồ khối hệ thống kết hợp hoán vị và mã hóa số học phân tách khoảng .................. 47
6
MỞ ĐẦU
Mã hóa là một trong các phƣơng pháp cơ bản của việc đảm bảo an toàn dữ liệu.
Thời kỳ sơ khai, con ngƣời đã sử dụng nhiều phƣơng pháp để bảo vệ các thông tin bí mật,
nhƣng tất cả các phƣơng pháp đó chỉ mang tính nghệ thuật hơn là khoa học. Ban đầu, mã
hóa đƣợc sử dụng phổ biến cho quân đội, qua nhiều cuộc chiến tranh, vai trò của mã hóa
ngày càng quan trọng và mang lại nhiều thành quả không nhỏ nhƣ các hệ mã cổ điển
Caesar, Playfair…chúng đều là nền tảng cho mật mã học ngày nay.
Khi toán học đƣợc áp dụng cho mã hóa thì lịch sử của mã hóa đã sang trang mới.
Việc ra đời các hệ mã hóa đối xứng không làm mất đi vai trò của các hệ mã cổ điển mà
còn bổ sung cho ngành mật mã nhiều phƣơng pháp mã hóa mới.
Từ năm 1976, khi hệ mã phi đối xứng ra đời, nhiều khái niệm mới gắn với mật mã
học xuất hiện: chữ ký số, hàm băm, mã đại diện, chứng chỉ số...vv. Mật mã học không chỉ
áp dụng cho quân sự mà còn cho các lĩnh vực kinh tế xã hội khác.
Hiện nay có nhiều phƣơng pháp mã hóa, mỗi phƣơng pháp có ƣu, nhƣợc điểm
riêng. Tùy theo yêu cầu của môi trƣờng ứng dụng mà ngƣời ta có thể dùng phƣơng pháp
này hay phƣơng pháp kia. Có những môi trƣờng cần phải an toàn tuyệt đối bất kể thời
gian và chi phí. Có những môi trƣờng lại cần giải pháp dung hòa giữa bảo mật và chi phí.
Trong lĩnh vực bảo mật dữ liệu, phƣơng pháp mã hóa số học đƣợc xem là một
trong những phƣơng pháp hay. Tuy nhiên, việc ứng dụng phƣơng pháp này vào thực tế
gặp phải những khó khăn nhất định, bởi tốc độ thực hiện của thuật toán mã hóa và giải mã
chậm, đồng thời độ bảo mật của phƣơng pháp chƣa cao. Luận văn này tập trung đi sâu
vào nghiên cứu phƣơng pháp mã hóa số học và các vấn đề liên quan. Luận văn đƣa ra một
số cải tiến trong thuật toán mã hóa và giải mã nhằm tăng tốc độ thực hiện và xây dựng mô
hình mã hóa dựa trên ý tƣởng của lƣợc đồ RAC (do Marco Grangetto đề xuất) để nâng
cao độ bảo mật của phƣơng pháp.
Ngoài phần mở đầu và kết luận, kết cấu của luận văn gồm 4 chƣơng:
Chƣơng 1 “Giới thiệu chung về mã hóa thông tin” trình bày những khái
niệm cơ bản về mã hóa thông tin.
7
Chƣơng 2 “Cơ sở toán học của phương pháp mã hóa số học” trình bày cơ
sở toán học cho phƣơng pháp mã hóa số học.
Chƣơng 3 “Cải tiến phương pháp mã hóa số học” trình bày lịch sử ra đời
của phƣơng pháp, thuật toán mã hóa số học truyền thống. Đặc biệt trong
chƣơng này đề xuất một số cải tiến nhằm tăng tốc độ thực hiện của thuật toán
bằng việc thay thế các phép nhân, chia bởi các phép dịch chuyển bít và đƣa ra
một số nhận xét về độ an toàn của phƣơng pháp. Dựa vào mô hình RAC của
Grangetto [15] đƣa ra một mô hình cải tiến nhằm nâng cao tính bảo mật của
phƣơng pháp mã hóa số học.
Chƣơng 4 “Cài đặt và thử nghiệm” giới thiệu thƣ viện xử lý số nguyên lớn,
một số kết quả thử nghiệm trên máy của chƣơng trình mã hóa số học truyền
thống và cải tiến.
8
Chƣơng 1. GIỚI THIỆU CHUNG VỀ MÃ HÓA THÔNG TIN
Tóm tắt chương: Trong chương này luận văn giới thiệu chung về mã hóa thông tin, lịch
sử mật mã, các hệ mã, các bài toàn an toàn thông tin và bài toán thám mã. Đưa ra được
một số khái niệm cơ bản nhất của mã hóa như: bản rõ, bản mã, hệ mã hóa thám mã, khóa
mã, mã hóa khóa công khai, mã hóa khóa đối xứng, mã theo khối, mã theo dòng.v.v….
Các nội dung của chương này được tổng hợp từ các tài liệu [5]-[9].
1.1. Một số thuật ngữ và khái niệm
1.1.1. Một số thuật ngữ
Văn bản (plaintext) là một thông báo gốc cần chuyển, đƣợc ghi bằng hình ảnh, âm
thanh, chữ số, chữ viết,... Về sau, khi đƣa ra các ví dụ, ta thƣờng xem các văn bản đƣợc
viết bằng chữ viết, hoặc bằng chữ số. Tuy nhiên, ngày nay mọi tín hiệu (âm thanh, hình
ảnh...) đều có thể đƣợc số hóa (thành các xâu ký tự số), cho nên việc nghiên cứu trên các
văn bản số không hạn chế các ứng dụng đa dạng của nó.
Mã hóa (encrytion) là việc "ngụy trang" văn bản (thông tin nói chung) sang một
dạng khác để cho những ngƣời "ngoài cuộc" không thể đọc đƣợc, phục vụ cho nhu cầu
trao đổi thông tin, dữ liệu và các giao dịch tài chính, thƣơng mại,... Quá trình "ngụy trang"
văn bản gọi là lập mã còn quá trình "khôi phục" lại văn bản nguồn (từ văn bản ngụy
trang) gọi là giải mã. Nguyên tắc chung của mã hóa là việc giải mã phải rất dễ dàng với
"ngƣời trong cuộc", nhƣng rất khó khăn (thậm chí là không thực hiện đƣợc) đối với
"ngƣời ngoài cuộc". Văn bản gốc (trƣớc khi mã hóa) thƣờng đƣợc ký hiệu là PT (Plain
Text), hay đơn giản là P. Văn bản mã (đã đƣợc cải trang) thƣờng đƣợc ký hiệu là CT
(Ciphertext), hay đơn giản là C.
Hệ mã (Cryptosystem) là một phƣơng pháp ngụy trang văn bản. Nghệ thuật tạo ra
và sử dụng các hệ mã là thuật mã hóa hay mật mã học (Cryptography).
Phân tích mã (Cryptanalysis), hay thám mã, là nghệ thuật phá các hệ mã (nhìn
xuyên qua các phƣơng pháp ngụy trang).
9
Công nghệ mã (Cryptology) là việc nghiên cứu tổng hợp cả cryptography và
cryptanalysis.
Lập mã (encrypt) là việc biến văn bản nguồn thành văn bản mã.
Giải mã (decrypt) là việc đƣa văn bản đã mã hóa trở về dạng văn bản nguồn.
Định mã (encode/decode) là việc định ra phép tƣơng ứng giữa các chữ và số (việc
này không bao giờ đƣợc xem là bí mật, vì máy tính ngày nay dễ dàng tìm ra phép tƣơng
ứng này trong một thời gian ngắn).
Mã dòng (stream cipher) là việc tiến hành mã hóa liên tục trên từng ký tự (hay
từng bit).
Mã khối (block cipher) là việc tiến hành mã hóa trên từng khối văn bản (khi khối
văn bản là một cặp 2 ký tự thì gọi là digraph, còn khi nó là bộ 3 chữ thì gọi là trigraph).
Phép mã chuyển vị (transposition cipher) là việc tráo đổi vị trí giữa các ký tự (các
bit) trong văn bản.
Phép mã thay thế (substitution) là việc thay thế một ký tự này bằng một ký tự khác
(mà không thay đổi vị trí).
Phép mã tích hợp (product cipher) là việc tiến hành xen kẽ 2 phép mã chuyển vị và
thay thế.
Chìa khóa mã (cipher key) là bí quyết lập mã và giải mã. Nếu nhƣ quy trình mã
hóa đƣợc xem nhƣ một hàm y = f(x,k), trong đó x là đầu vào (văn bản nguồn), y là đầu ra
(văn bản mã), f là phương pháp (hay thuật toán) mã hóa, còn k là một tham số điều khiển,
thì bí quyết trƣớc đây thƣờng bao gồm cả phương pháp f, và tham số k. Nhu cầu của thực
tiễn hiện nay đã khiến công nghệ mã hóa hiện đại phải thay đổi quan điểm này. Phương
pháp f là cái thƣờng do không chỉ một ngƣời nắm, nên không thể giữ đƣợc bí mật lâu, và
do đó phải đƣợc xem là công khai. Tham số điều khiển k, có tác dụng làm thay đổi kết quả
mã hóa (tùy thuộc vào giá trị của nó), đƣợc xem là chìa khóa mã. Thông thƣờng, nó là
một xâu bit (hay một con số nào đó) mà ngƣời ta có thể giữ riêng cho mình.
10
Hệ mã bí mật (secret key cryptosystem - SKC) hay hệ mã đối xứng (symmetric
cryptosystem) là hệ mã mà trong đó việc lập mã và giải mã cùng sử dụng chung một chìa
khóa mã (bí mật).
Hệ mã công khai (public key cryptosystem - PKC) hay hệ mã phi đối xứng
(asymmetric cryptosystem) là hệ mã mà trong đó việc lập mã và giải mã sử dụng 2 chìa
khóa mã riêng biệt, từ chìa này không thể tìm ra chìa kia một cách dễ dàng, chìa dùng để
lập mã thƣờng đƣợc thông báo công khai, còn chìa dành cho việc giải mã phải luôn giữ bí
mật, thƣờng đƣợc gọi là chìa khóa riêng..
1.1.2. Vì sao cần mã hóa
Đó là một câu hỏi dễ trả lời, bởi vì trong mọi hoạt động của con ngƣời, nhu cầu
trao đổi thông tin mật giữa những thành viên thuộc một nhóm nào đó với nhau là hết sức
cần thiết. Tuy nhiên, để thực sự thấy rõ yêu cầu cấp bách của mã hóa trong thời đại ngày
nay, cần nhấn mạnh rằng với các phƣơng tiện kỹ thuật hiện đại việc giữ giữ gìn bí mật
ngày càng trở nên hết sức khó khăn. Các hình ảnh trên mặt đất, các cuộc đàm thoại hữu
tuyến và vô tuyến, các thông tin đƣợc truyền qua mạng internet,... tất cả đều có thể dễ
dàng thu đƣợc nhờ các thiết bị điện tử trên mặt đất hoặc từ vệ tinh. Vì thế, phƣơng pháp
thông dụng nhất để giữ gìn bí mật thông tin là mã hóa chúng bằng một hệ mã nào đó
trƣớc khi truyền đi.
Dĩ nhiên, việc mã hóa thông tin trƣớc khi truyền đi và việc giải mã các thông tin
nhận đƣợc sẽ tạo nên một số khó khăn: giảm tốc độ truyền tin, tăng chi phí... Một hệ mã
lý tƣởng là một hệ mã bảo đảm đƣợc các yêu câu: thời gian mã hóa và giải mã nhanh, độ
bảo mật cao (gây khó khăn tối đa cho ngƣời thám mã). Các yêu cầu đó luôn mâu thuẫn
nhau, và ngƣời sử dụng cần hiểu rõ công nghệ mã hóa để có thể lựa chọn hệ mã thích hợp
cho từng việc và mục đích.
1.2. Vài nét về lịch sử
Ngƣời Hi Lạp đã sử dụng phép mã chuyển vị từ 400 năm trƣớc công nguyên.
Ngƣời ta dùng một dải băng dài và mảnh quấn quanh một khối hình trụ tròn xoay rồi viết
chữ lên đó theo cách thức thông thƣờng (từ trái sang phải và từ trên xuống dƣới). Mẩu tin
11
đƣợc chuyển đi dƣới dạng dải băng và chỉ có thể đọc ra đƣợc khi biết đƣợc bán kính của
thiết diện khối trụ (và quấn lại dải băng quanh khối trụ nhƣ khi đã viết lên - hình 1.1).
N
G A Y
M A I
T I E N
V E
P H I A T A Y
Hình 1.1 Mô tả phép mã chuyển vị
Hoàng đế Caesar đã từng sử dụng phép mã thay thế trong quân sự, trong đó mỗi ký
tự đƣợc thay thế bởi ký tự đứng sau nó 3 vị trí trong bảng chữ cái alphabet, nghĩa là chữ
A đƣợc thay thế bởi chữ D, chữ B đƣợc thay bởi chữ E, ... Trong thực tế, việc triển khai
một hệ mã nhƣ vậy là khá đơn giản (và cũng rất thuận tiện cho việc sử dụng), với việc
dùng hai chiếc đĩa đồng tâm có bán kính khác nhau và có các bảng chữ cái alphabet rải
đều trên mỗi vành đĩa (hình 1.2).
Hình 1.2 Bảng đĩa chữ cái
Việc xoay (một trong hai đĩa) sao cho chữ A trên vành đĩa nhỏ nằm trên bán kính
nối tâm đĩa với chữ D trên vành đĩa lớn sẽ xác định phép mã Caesar nói trên, thông qua
phép tƣơng ứng giữa các chữ cái trên vành đĩa nhỏ với các chữ cái trên vành đĩa lớn. Nói
chung, việc xoay đĩa đi một góc bất kỳ (miễn sao các chữ trên vành đĩa nhỏ và trên vành
đĩa lớn đƣợc tƣơng ứng nhau rõ ràng) sẽ mang lại một phép mã theo kiểu Caesar.
12
Mã khối đƣợc xem là xuất hiện vào những năm đầu thế kỷ XX, với sự ra đời của
hệ mã British Playfair vào năm 1910, trong đó mỗi khối là một cặp 2 chữ (digraph). Phép
mã ở đây là thay thế theo chìa. Ngƣời ta viết 26 chữ cái (của tiếng Anh) vào một bảng
hình vuông (5 cột, 5 dòng), trong đó 2 chữ I và J đƣợc viết vào cùng một chỗ. Hai dòng
đầu tiên dành cho chìa khóa (gồm 10 ký tự không trùng lặp), 3 dòng dƣới viết 16 chữ cái
còn lại (không có trong chìa khóa) theo thứ tự thông thƣờng (từ trái sang phải và từ trên
xuống dƣới). Thí dụ, với chìa khóa là PALMERSTON thì bảng đƣợc xếp nhƣ sau:
P
A
L
M
E
R
S
T
O
N
B
C
D
F
G
H
IJ
K
Q
U
V
W
X
Y
Z
Hình 1.3 Minh họa mã khối
Muốn mã hóa một khối (cặp 2 chữ) nào đó, không ở trên cùng một dòng hay một
cột, ta tìm cách thiết lập một hộp (chữ nhật) với 2 đỉnh là 2 chữ trong khối đó, còn 2 đỉnh
còn lại cho ta cặp chữ là kết quả mã của cặp chữ nguồn, thí dụ cặp chữ SF sẽ xác định hộp
chữ nhật 4 đỉnh là SOFC và do đó cặp chữ SF đƣợc mã hóa thành cặp CO.
Muốn mã hóa cặp 2 chữ trên cùng một dòng thì thay thế mỗi chữ bằng chữ kế tiếp
bên phải nó trên cùng dòng đó (nếu là chữ cuối dòng thì thay bằng chữ đầu dòng). Thí dụ,
cặp chữ SO sẽ đƣợc mã hóa thành TN, còn cặp CG sẽ biến thành cặp DB.
Muốn mã hóa cặp 2 chữ nằm trên cùng một cột, ta thay mỗi chữ bằng chữ ngay
bên dƣới nó (nếu chữ nằm ở đáy cột thì đƣợc thay bằng chữ ở đỉnh cột). Thí dụ, SI sẽ biến
thành CW. Các chữ đúp sẽ đƣợc tách ra bằng chữ X trƣớc khi cho mã hóa, thí dụ chữ
BALLOON sẽ đƣợc xử lý thành BALXLOXON.
Hệ mã tích hợp (product cipher) đƣợc sử dụng sớm nhất là của quân đội Đức trong
Đại chiến Thế giới lần thứ I, mang tên là ADFGVX. Cho trƣớc một bảng nhƣ hình 1.4
A
D
F
G
V
X
A
K
Z
W
R
1
F
D
9
B
6
C
L
5
13
F
Q
7
J
P
G
X
G
E
V
Y
3
A
N
V
8
O
D
H
0
2
X
U
4
I
S
T
M
Hình 1.4 Hệ mã tích hợp
Phần thay thế cho phép thay mỗi ký tự bằng một cặp 2 ký tự ứng với "tung độ" và
"hoành độ" của chữ đó trong bảng. Thí dụ chữ P sẽ biến thành cặp FG, chữ R biến thành
AG, và PRODUCTCIPHERS sẽ biến thành
FGAGVVDVFXADGXVDGXFFGVGGAAGXG
Phần chuyển vị đƣợc tiến hành tiếp theo sau và phụ thuộc vào chìa (với các chữ
không trùng lặp), thí dụ là DEUTSCH. Hãy đánh số các chữ trong chìa theo thứ tự nhƣ
trong bảng chữ cái alphabet (thí dụ: chữ C sẽ đƣợc đánh số 1, chữ D sẽ đƣợc đánh số
2,...). Hãy đặt kết quả "mã hóa nửa vời" thu đƣợc ở trên theo từng dòng (nằm dƣới chìa,
nghĩa là
D
E
U
S
C
H
2
3
7
6
1
4
F
G
A
G
D
V
F
X
A
D
X
V
D
G
X
F
G
V
G
G
A
A
X
G
Hình 1.5 Ví dụ hệ mã tích hợp
Viết các chữ cái theo từng cột (với thứ tự xác định theo chỉ số cột). Thí dụ, cột thứ
nhất gồm các chữ DXGF sẽ đƣợc viết đầu tiên, và cột thứ 2 gồm các chữ FFDG sẽ đƣợc
viết tiếp theo, v.v... Tóm lại, ta đƣợc văn bản sau khi mã hóa là
DXGXFFDGGXGGVVVGVGFGGDFAAAXA
Trong Đại chiến Thế giới lần thứ II, ngƣời ta thấy rằng hệ mã tích hợp (luân phiên
giữa thay thế và chuyển vị) là rất an toàn. Tuy nhiên, hệ mã ADFGVX có những điểm yếu
ở chỗ chỉ có một vòng (phép thay thế và chuyển vị chỉ đƣợc thực hiện một lần) và phép
14
thay thế lại không có chìa điều khiển. Chính vì vậy, một hệ mã tích hợp khác, phức tạp
hơn, đã đƣợc sử dụng trong Thế chiến thứ II, đó là ENIGMA.
Tuy nhiên, từ những năm cuối của thập kỷ 60, mối đe dọa về vấn đề "an toàn máy
tính" đã trở thành hiện thực. Ngƣời ta cần đến các chƣơng trình mã hóa mạnh hơn để
chống lại khả năng phá mã của các siêu máy tính với tốc độ ngày càng lớn. Vấn đề này đã
đƣợc quan tâm nghiên cứu tích cực trong các năm 1968-1975 và đƣợc đánh dấu bằng sự
ra đời của hệ mã Lucifer (1974) và sau đó đƣợc cải tiến thành hệ mã dữ liệu tiêu chuẩn
DES (1975), một hệ mã khối đối xứng với chìa khóa dài 56 bits, kết hợp luân phiên 16
phép thay thế với 15 phép hoán vị. Tiếp sau đó, sự ra đời của hệ mã hóa với kháo công
khai, vào cuối những năm 70 của thế kỷ vừa qua, đã khẳng định vai trò then chốt của các
phƣơng pháp Toán học trong lĩnh vực mã hóa hiện đại.
1.3. Khái niệm hệ mã hóa
Để bảo đảm an toàn thông tin lƣu trữ trong máy tính (giữ gìn thông tin cố định)
hay bảo đảm an toàn thông tin trên đƣờng truyền tin (ví dụ trên mạng máy tính), ngƣời ta
phải “Che Giấu” các thông tin này.
“Che” thông tin (dữ liệu) hay “Mã hóa” thông tin là thay đổi hình dạng thông tin
gốc, và ngƣời khác “khó” nhận ra.
Nói cách khác “Mã hóa” thông tin là “che” đi “Ý nghĩa” của thông tin, và ngƣời
khác “khó” hiểu đƣợc (“khó” đọc đƣợc) thông tin đã mã hoá.
“Giấu” thông tin (dữ liệu) là cất giấu thông tin trong bản tin khác, và ngƣời khác
cũng “khó” nhận ra.
Việc mã hoá phải theo quy tắc nhất định, quy tắc đó gọi là Hệ mã hóa.
Hệ mã hóa đƣợc định nghĩa là bộ năm (P, C, K, E, D), trong đó:
P là tập hữu hạn các bản rõ có thể.
C là tập hữu hạn các bản mã có thể.
K là tập hữu hạn các khoá có thể.
E là tập các hàm lập mã.
D là tập các hàm giải mã.
15
Với khóa lập mã ke K, có hàm lập mã eke E, eke: P C
Với khóa giải mã kd K, có hàm giải mã dkd D, dkd: C P
sao cho dkd (eke (T)) = T, T P.
Ở đây T đƣợc gọi là bản rõ, eke (T) đƣợc gọi là bản mã.
Ngƣời gửi G
(có khóa lập mã ke)
eke(T)
Ngƣời nhận N
(có khóa giải mã kd)
Tin tặc có thể trộm bản mã eke (T)
Ngƣời gửi G muốn gửi bản tin T cho ngƣời nhận N. Để bảo đảm bí mật, G mã hoá
bản tin bằng khóa lập mã ke, nhận đƣợc bản mã eke(T), sau đó gửi cho N.
Tin tặc có thể trộm bản mã eke(T), nhƣng cũng “khó” hiểu đƣợc bản tin gốc T nếu
không có khoá giải mã kd.
Ngƣời N nhận đƣợc bản mã, họ dùng khoá giải mã kd, để giải mã eke(T), sẽ nhận
đƣợc bản tin gốc T = dkd (eke(T)).
1.4. Phân loại hệ mã hóa
Hiện có hai loại mã hóa chính: mã hóa khóa đối xứng và mã hóa khoá công khai.
Hệ mã hóa khóa đối xứng có khóa lập mã và khóa giải mã “giống nhau”, theo
nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia. Vì vậy phải giữ bí mật cả 2 khóa.
Hệ mã hóa khóa công khai có khóa lập mã khác khóa giải mã (ke kd), biết đƣợc
khóa này cũng “khó” tính đƣợc khóa kia. Vì vậy chỉ cần bí mật khóa giải mã, còn công
khai khóa lập mã.
1.4.1. Hệ mã hóa khóa đối xứng
Mã hóa khóa đối xứng là Hệ mã hóa mà biết đƣợc khóa lập mã thì có thể "dễ" tính
đƣợc khóa giải mã và ngƣợc lại. Đặc biệt một số Hệ mã hóa có khóa lập mã và khóa giải
mã trùng nhau (ke = kd), nhƣ Hệ mã hóa "dịch chuyển" hay DES (Data Encryption
Standard).
Hệ mã hóa khóa đối xứng còn có tên gọi là Hệ mã hóa khoá bí mật hay khóa riêng,
vì phải giữ bí mật cả 2 khóa. Trƣớc khi dùng Hệ mã hóa khóa đối xứng, ngƣời gửi và
16
ngƣời nhận phải thoả thuận thuật toán mã hóa và một khoá chung (lập mã hay giải mã),
khoá này phải đƣợc giữ bí mật. Độ an toàn của Hệ mã hóa loại này phụ thuộc vào khoá.
1.4.1.1. Đặc điểm của hệ mã hóa khóa đối xứng
Ƣu điểm:
- Hệ mã hóa khóa đối xứng có tốc độ mã hóa và giải mã nhanh hơn Hệ mã hóa
khóa công khai.
Hạn chế:
- Mã hóa khóa đối xứng chƣa thật an toàn với lý do đơn giản sau: ngƣời mã hóa và
ngƣời giải mã phải có "chung" một khóa. Khóa phải đƣợc giữ bí mật tuyệt đối, vì biết
khóa này "dễ" xác định đƣợc khóa kia và ngƣợc lại.
- Vấn đề thỏa thuận khóa và quản lý khóa chung là khó khăn và phức tạp. Ngƣời
gửi và ngƣời nhận phải luôn thống nhất với nhau về khóa. Việc thay đổi khóa là rất khó
và dễ bị lộ. Khóa chung phải đƣợc gửi cho nhau trên kênh an toàn. Mặt khác khi hai
ngƣời (lập mã, giải mã) cùng biết "chung" một bí mật, thì càng khó giữ bí mật.
1.4.1.2. Nơi sử dụng hệ mã hóa khóa đối xứng
Hệ mã hóa khóa đối xứng thƣờng đƣợc sử dụng trong môi trƣờng mà khoá chung
có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ. Hệ mã hóa
khóa đối xứng thƣờng dùng để mã hóa những bản tin lớn, vì tốc độ mã hóa và giải mã
nhanh hơn Hệ mã hóa khóa công khai.
1.4.2. Hệ mã hóa khóa công khai
Hệ mã hóa khóa phi đối xứng là Hệ mã hóa có khóa lập mã và khóa giải mã khác
nhau (ke ≠ kd), biết đƣợc khóa này cũng "khó" tính đƣợc khóa kia. Hệ mã hóa này còn
đƣợc gọi là Hệ mã hóa khóa công khai vì: khóa lập mã cho công khai (gọi là khóa công
khai - public key), khóa giải mã giữ bí mật còn gọi là khóa riêng (private key) hay khóa bí
mật. Một ngƣời bất kỳ có thể dùng khóa công khai để mã hóa bản tin, nhƣng chỉ ngƣời
nào có đúng khóa giải mã thì mới có khả năng đọc đƣợc bản rõ. Hệ mã hóa khóa công
khai hay Hệ mã hóa phi đối xứng do Diffie và Hellman phát minh vào những năm 1970.
17
1.4.2.1. Đặc điểm của Hệ mã hóa khóa công khai
Ƣu điểm:
- Thuật toán đƣợc viết một lần, công khai cho nhiều lần dùng, cho nhiều ngƣời
dùng, họ chỉ cần giữ bí mật khóa riêng của mình.
- Khi biết các tham số ban đầu của hệ mã, việc tính ra cặp khóa công khai và bí
mật phải là "dễ", tức là trong thời gian đa thức. Ngƣời gửi có bản rõ P và khóa công khai,
thì "dễ" tạo ra bản mã C. Ngƣời nhận có bản mã C và khóa bí mật, thì "dễ" giải đƣợc
thành bản rõ P.
- Ngƣời mã hóa dùng khóa công khai, ngƣời giải mã giữ khóa bí mật. Khả năng lộ
khóa bí mật khó hơn vì chỉ có một ngƣời giữ gìn. Nếu thám mã biết khóa công khai, cố
gắng tìm khóa bí mật, thì chúng phải đƣơng đầu với bài toán "khó", số phép thử là vô
cùng lớn, không khả thi.
Hạn chế: Tốc độ mã hóa và giải mã chậm hơn hệ mã hóa khóa đối xứng.
1.4.2.2. Nơi sử dụng Hệ mã hóa khóa đối xứng
Hệ mã hóa khóa công khai thƣờng đƣợc sử dụng chủ yếu trên các mạng công khai
nhƣ internet, khi mà việc trao chuyển khóa bí mật tƣơng đối khó khăn. Đặc trƣng nổi bật
của hệ mã hóa khóa công khai là khóa công khai và bản mã đều có thể gửi đi trên một
kênh truyền tin không an toàn. Có biết cả khóa công khai và bản mã thì thám mã cũng
không dễ khám phá đƣợc bản rõ. Nhƣng vì có tốc độ mã hóa và giải mã chậm, nên hệ mã
hóa khóa công khai chỉ dùng để mã hóa những bản tin ngắn, ví dụ nhƣ mã hóa khóa bí
mật gửi đi. Hệ mã hóa khóa công khai thƣờng đƣợc sử dụng cho cặp ngƣời dùng thỏa
thuận khóa bí mật của Hệ mã hóa khóa riêng.
18
1.5. Một số hệ mã hóa khóa đối xứng và mã hóa khóa công
khai
1.5.1. Hệ mã hóa đối xứng cổ điển
Khái niệm: Hệ mã hóa đối xứng đã đƣợc dùng từ rất sớm, nên còn gọi là Hệ mã
hóa đối xứng - cổ điển (gọi ngắn gọn là Hệ mã hóa đối xứng cổ điển). Bản mã và bản rõ
là dãy các ký tự Latin.
Quá trình lập mã đƣợc thực hiện nhƣ sau:
1. Nhập bản rõ ký tự: Rõ_chữ
2. Chuyển Rõ_chữ thành Rõ_số
3. Chuyển Rõ_số thành Mã_số
4. Chuyển Mã_số thành Mã_chữ
Quá trình giải mã thực hiện theo các bƣớc sau:
1. Nhập bản mã ký tự: Mã_chữ
2. Chuyễn Mã_chữ thành Mã_số
3. Chuyển Mã_số thành Rõ_số
4. Chuyễn Rõ_số thành Rõ_chữ
Để chuyển từ Chữ sang Số hay ngƣợc lại từ Số trở về Chữ, ngƣời ta theo một quy
ƣớc nào đó, ví dụ chữ cái thay bằng số theo modulo 26 nhƣ sau:
A B C D E F G H I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
0 1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Để thực hiện mã hóa hay giải mã với các "số", ngƣời ta dùng các phép toán số học
theo modulo 26.
Các hệ mã hóa cổ điển:
Mã hóa cổ điển gồm nhiều hệ, ví dụ:
Hệ mã hóa dịch chuyển: Khóa có
1 “chìa”. (Thể hiện bằng 1 giá trị).
Hệ mã Affine:
Khóa có
2 “chìa”. (Thể hiện bằng 2 giá trị).
Hệ mã hóa thay thế:
Khóa có 26 “chìa”. (Thể hiện bằng 26 giá trị).
Hệ mã hóa VIGENERE: Khóa có
m “chìa”. (Thể hiện bằng m giá trị).
19
Khóa có ma trận “chìa” (chùm chìa khóa).
Hệ mã hóa HILL:
1.5.1.1. Hệ mã hóa dịch chuyển
Sơ đồ:
Đặt P = C = K = Z26. Bản mã y và bản rõ x Z26.
Với khóa k K, ta định nghĩa:
Hàm mã hóa: y = ek(x) = (x+k) mod 26
Hàm giải mã : x = dk(y) = (y-k) mod 26
Ví dụ:
Bản rõ chữ:
DAIHOCCONGNGHE
Chọn khóa k = 3
Bản rõ số: 3 0 8 7 14 2 2 14 13 6 7 4
Với phép mã hóa y = ek(x) = (x+k) mod 26 = (x+3) mod 26, ta nhận đƣợc:
Bản mã số: 6 3 11 10 17 5 5 17 16 9 10 7
Bản mã chữ: GDLKRFFRQJKH
Giải mã: từ bản mã chữ ở trên ta chuyển về bản mã số và với phép giải mã x =
dk(y) = (y-k) mod 26 = (y-3) mod 26, ta nhận đƣợc lại bản rõ số, sau đó chuyển bản rõ số trở về
bản rõ chữ ban đầu.
Độ an toàn: Độ an toàn của mã dịch chuyển rất thấp. Tập khóa K chỉ có 26 khóa nên việc
phá khóa có thể thực hiện dễ dàng bằng cách thử kiểm tra từng khóa k = 1,2,…,26.
1.5.1.2. Hệ mã hóa thay thế (Hoán vị toàn cục)
Sơ đồ:
Đặt P = C = Z26. Bản mã y và bản rõ x Z26.
Tập khóa K là tập mọi hoán vị trên Z26
Với khóa k = п K, tức là một hoán vị trên Z26 ta định nghĩa
Hàm mã hóa: y = eп(x) = п(x)
Hàm giải mã : x = dп(y) = п-1(y)
Ví dụ:
Bản rõ chữ:
DAIHOCCONGNGHE
Chọn khóa k = п là hoán vị sau:
A B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W X
Y
Z
X N
Y
A
H
P
O
G
Z
Q
W B
T
S
F
L
R
C
V
M U
E
K
D
I
J
20
Mã hóa theo công thức y = eп(x) = п(x) ta đƣợc bản mã chữ
Bản mã chữ: AXZGFYYFSOSOGH
Giải mã theo công thức x = dп(y) = п-1(y) ta nhận lại đƣợc bản rõ ban đầu.
Độ an toàn: Hệ mã hóa thay thế có số khóa có thể bằng số các phép hoán vị trên tập Z26,
tức là 26! khóa, đó là một số rất lớn. Do đó, việc duyệt lần lƣợt tất cả các khóa có thể để thám mã
là không thực tế, ngay cả dùng máy tính. Tuy vậy, có những phƣơng pháp thám mã khác hiệu quả
hơn, làm cho hệ mã hóa thay thế không thể đƣợc xem là an toàn.
1.5.1.3. Hệ mã Affine
Sơ đồ:
Đặt P = C = Z26. Bản mã y và bản rõ x Z26.
Tập khóa K = {(a,b) với a,b Z26, UCLN(a,26) = 1}
Với khóa k = (a,b) K ta định nghĩa:
Hàm mã hóa: y = ek(x) = (ax+b) mod 26
Hàm giải mã : x = dk(y) = a-1(y-b) mod 26
Có điều kiện UCLN(a,26) =1 là để bảo đảm có phần tử nghịch đảo a-1 mod 26 của a, làm
cho thuật toán giải mã dk luôn thực hiện đƣợc. Có tất cả (26) = 12 số a Z26 nguyên tố với 26,
đó là các số: 1,3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 và các số nghịch đảo theo mod26 tƣơng ứng
của chúng là: 1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25.
Ví dụ:
Bản rõ chữ:
DAIHOCCONGNGHE
Chọn khóa k = (a,b) = (3,6)
Bản rõ số: x = 3 0 8 7 14 2 2 14 13 6 7 4
Mã hóa theo công thức y = ek(x) = (ax + b) mod 26 = (3x+6) mod 26
Bản mã số: 14 6 4 1 22 12 12 22 19 24 1 18
Bản mã chữ: OGEBWMMWTYBS
Giải mã theo công thức: x = dk(y) = a-1(y-b) mod 26
= 3-1(y-6) mod 26 = 9(y-6) mod 26
Độ an toàn: Vì có 12 số thuộc Z26 nguyên tố với 26, nên số các khóa có thể có (do đó, số
các hệ mật mã affine) bằng 12×26 = 312, một con số không lớn lắm nếu ta sử dụng máy tính để
thực hiện việc thám mã bằng cách duyệt lần lƣợt tất cả các khóa có thể, nhƣ vậy, mã affine cũng
không đƣợc xem là mã an toàn.
- Xem thêm -