ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
........................................
LỤC VŨ KHANH
THIẾT KẾ HỆ THỐNG MÃ KHỐI
BẰNG CÔNG NGHỆ FPGA
LUẬN VĂN THẠC SĨ KỸ THUẬT ĐIỆN TỬ
THÁI NGUYÊN 2010
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
........................................
LUẬN VĂN THẠC SĨ KỸ THUẬT ĐIỆN TỬ
Tên đề tài:
THIẾT KẾ HỆ THỐNG MÃ KHỐI
BẰNG CÔNG NGHỆ FPGA
Ngành: KỸ THUẬT ĐIỆN TỬ
Mã số: 60 52 70
Học viên: Lục Vũ Khanh
Người hướng dẫn Khoa học: PGS.TS. Đỗ Xuân Tiến
THÁI NGUYÊN 2010
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1
MỤC LỤC
Trang
Trang phụ bìa
Lời cam đoan
Lời cảm ơn
MỤC LỤC .............................................................................................................. 1
DANH MỤC CÁC TỪ VIẾT TẮT ......................................................................... 5
DANH MỤC CÁC BẢNG ...................................................................................... 7
DANH MỤC CÁC HÌNH VẼ ................................................................................. 8
MỞ ĐẦU .............................................................................................................. 10
CHƢƠNG 1 HỆ TRUYỀN TIN MẬT VÀ CƠ SỞ LÝ THUYẾT MÃ KHỐI ....... 13
1.1. TỔNG QUAN VỀ HỆ TRUYỀN TIN MẬT. ................................................. 13
1.1.1. Mô hì nh hệ thống truyền tin mật. ................................................................. 13
1.1.2. Các phƣơng pháp mã mật cơ bản. ................................................................ 15
1.1.2.2. Phƣơng pháp thay thế. .............................................................................. 15
1.1.3. Mô hì nh hệ mật. ........................................................................................... 16
1.1.3.1. Hệ mật đối xƣ́ng (Hệ mật khoá bí mật). .................................................... 16
1.1.3.2. Hệ mật không đối xƣ́ng (Hệ mật khoá công khai ). .................................... 17
1.1.4. Phân loại hệ mã............................................................................................ 18
1.1.5. Đánh giá độ mật của hệ thống truyền tin mật. .............................................. 20
1.2. CƠ SỞ LÝ THUYẾT VỀ MÃ KHỐI. ............................................................ 21
1.2.1. Khái niệm về mã khối. ................................................................................. 21
1.2.2. Nguyên lý thiết kế mã khối. ......................................................................... 22
1.2.2.1. Nguyên lý thiết kế chung về độ an toàn..................................................... 22
1.2.2.2. Nguyên lý thiết kế cho ƣ́ng dụng.............................................................. 23
1.2.3. Các tham số của mã khối. ............................................................................ 23
1.2.3.1. Độ dài khối m. .......................................................................................... 23
1.2.3.2. Độ dài khóa k và cỡ khóa đúng k t. ............................................................ 24
1.2.4. Các cấu trúc mã khối cơ bản. ...................................................................... 24
1.2.4.1. Cấu trúc mã Feistel. .................................................................................. 24
1.2.4.2. Cấu trúc cộng - nhân. ................................................................................ 26
1.2.5. Các mã lặp. .................................................................................................. 27
1.2.5.1. Mã lặp và hàm vòng.................................................................................. 27
1.2.6. Độ an toàn của các hệ mã khối. .................................................................... 28
1.3. GIỚI THIỆU MỘT SỐ KỸ THUẬT MÃ KHỐI ............................................ 29
1.3.1. Chuẩn mã dƣ̃ liệu DES ................................................................................ 29
1.3.2. Chuẩn mã dƣ̃ liệu Xô-Viết. .......................................................................... 30
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
1.3.3. Thuật toán mã hoá dƣ̃ liệu IDEA. ................................................................ 32
1.3.3.1. Quá trình mã hoá của IDEA. ..................................................................... 32
1.3.3.3. Quá trình giải mã của IDEA. ..................................................................... 35
1.3.4. Các chế độ ứng dụng của mã khối. ............................................................... 35
1.3.5. Một số giải pháp kỹ thuật thiết kế mã khối. .................................................. 38
1.3.5.1. Thiết kế mã khối bằng chƣơng trình phần mềm. ....................................... 38
1.3.5.2. Thiết kế mã khối bằng công cụ phần cứng. ............................................... 39
1.3.5.3. Lựa chọn giải pháp thiết kế module mã khối ở Việt Nam. ......................... 40
1.4. Kết luận chƣơng. ............................................................................................ 40
CHƢƠNG 2: CÔNG NGHỆ FPGA ....................................................................... 42
2.1. TỔNG QUAN VỀ CÔNG NGHỆ FPGA. ....................................................... 42
2.1.1. Giới thiệu về công nghệ FPGA. ................................................................... 42
2.1.1.1. Sự phát triển của các thiết bị lập trình đƣợc. ............................................. 42
2.1.1.2. Cấu trúc cơ bản của FPGA. ..................................................................... 45
2.1.1.3. Phân loại FPGA. ...................................................................................... 49
2.1.1.4. Ứng dụng của FPGA................................................................................. 52
2.1.2. Quá trình thiết kế cơ bản trên FPGA. ........................................................... 52
2.1.2.1. Giới thiệu về quá trình thiết kế. ................................................................. 52
2.1.2.2. Tối ƣu lô gic. ............................................................................................ 54
2.1.2.3. Ánh xạ công nghệ. ................................................................................... 54
2.1.2.4. Sắp xếp các phần tử (Placement). .............................................................. 55
2.1.2.5. Định tuyến trên FPGA (rounting).............................................................. 56
2.1.2.6. Tải nạp chƣơng trình. ................................................................................ 57
2.1.3. Giới thiệu về FPGA của hãng ALTERA. ..................................................... 57
2.1.3.1. Các loại FPGA trên thị trƣờng. ................................................................. 57
2.1.3.2. Đặc điểm thiết bị FPGA của hãng Altera. ................................................ 58
2.1.3.3. Các họ FPGA của hãng Altera. ................................................................. 59
2.1.4. Các công cụ thiết kế. .................................................................................... 60
2.1.4.1. Giới thiệu về EDA. ................................................................................... 60
2.1.4.2. Giới thiệu công cụ thiết kế Quartus II. ...................................................... 61
2.1.4.3. Giới thiệu công cụ thiết kế MAX + PLUS II. ............................................ 63
2.1.5. Các ngôn ngữ mô tả phần cứng. ................................................................... 65
2.2. NGÔN NGỮ MÔ TẢ PHẦN CỨNG VHDL. ................................................. 66
2.2.1. Giới thiệu chung về ngôn ngữ VHDL. ......................................................... 66
2.2.1.1. Mô tả cấu trúc. ......................................................................................... 66
2.2.1.2. Mô tả hoạt động. ....................................................................................... 67
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
2.2.1.3. Mô hình thời gian theo các sự kiện rời rạc. ............................................... 68
2.2.2. Mô hình tổ chức........................................................................................... 69
2.2.2.1. Thƣ viện thiết kế. ...................................................................................... 69
2.2.2.2. Các cấu hình. ............................................................................................ 70
2.3 Kết luận chƣơng. ............................................................................................. 70
CHƢƠNG 3: THIẾT KẾ HỆ THỐNG MÃ KHỐI................................................ 71
3.1. CẤU TRÚC CỦA MODULE MÃ KHỐI. .................................................... 71
3.1.1. Cấu trúc chung. ........................................................................................... 71
3.1.2. Một số yêu cầu đối với module mã khối...................................................... 71
3.2. LỰA CHỌN THUẬT TOÁN CHO MÔ PHỎNG THIẾT KẾ. ....................... 72
3.2.1. Lựa chọn thuật toán. .................................................................................... 72
3.2.2. Mô tả thuật toán DES. .................................................................................. 72
3.2.2.1. Hàm F trong thuật toán DES. .................................................................... 73
3.2.2.2. Lƣợc đồ tạo khoá mã dịch. ........................................................................ 78
3.3. PHƢƠNG PHÁP THIẾT KẾ MODULE DES TRÊN FPGA. ........................ 80
3.3.1. Quy trình và công cụ thiết kế. ...................................................................... 80
3.3.1.1. Quy trình thiết kế. ..................................................................................... 80
3.3.1.2. Công cụ thiết kế. ....................................................................................... 81
3.3.2. Sơ đồ khối chức năng của module mã khối DES trên FPGA. ....................... 81
3.3.2.1. Sơ đồ khối tổng quát. ................................................................................ 81
3.3.2.3. Sơ đồ khối chức năng của module DES. .................................................. 83
3.3.3. Mô tả hoạt động của các khối trong module DES bằng VHDL. .................. 85
3.3.3.1. Khối các phép hoán vị............................................................................... 86
3.3.3.2. Mô tả khối DES16. ................................................................................... 87
3.3.3.3. Khối deskey (tính toán khoá). ................................................................... 92
3.3.3.4. Khối Control (điều khiển). ........................................................................ 93
3.3.3.5. Khối Converter (lấy dữ liệu vào/ra)........................................................... 94
3.3.3.6. Tổng hợp các khối chức năng của module DES. ....................................... 95
3.3.3.7. Kiểm tra thiết kế. ...................................................................................... 96
3.3.4. Phần cứng mô phỏng module DES............................................................... 96
3.3.4.1. Khối xử lý chính (mã hoá/giải mã). .......................................................... 97
3.3.4.2. Khối cấu hình cho FPGA. ......................................................................... 97
3.3.4.3. Các phần mạch khác. ............................................................................... 99
3.3.5. Kiểm tra sự hoạt động của DES trong module mã khối. ............................... 99
3.4. KẾT QUẢ THIẾT KẾ MODULE MÃ KHỐI DES. ..................................... 101
3.4.1. Kết quả thiết kế. ......................................................................................... 101
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
4
3.4.1.1. Sơ đồ phần cứng của module. ................................................................. 101
3.4.1.2. Kiểm tra kết quả thiết kế. ........................................................................ 104
3.4.2. Đánh giá kết quả thiết kế module mã khối. ................................................ 105
3.5 Kết luận chƣơng. ........................................................................................... 106
3.6 Kết luận chung............................................................................................... 106
TÀI LIỆU THAM KHẢO ................................................................................... 108
PHỤ LỤC 1 ......................................................................................................... 110
PHỤ LỤC 2: CHƢƠNG TRÌNH MÔ TẢ DES BẰNG VHDL ............................ 113
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
DANH MỤC CÁC TỪ VIẾT TẮT
Viết
tắt
APEX
ASIC
Tiếng Anh
Advanced ProgrammablE logic
matriX
Application-Specific Integrated
Circuit
CAE
Computer-Aided Electronics
CBC
Cipher Block Channing mode
Complex Programmable Logic
Devices
CPLD
CDL
Computer Design Language
CFB
ECB
DES
DSP
EDA
Cipher Freed Back
Component & Supplier
Management
Electronic Code Book
Data Encryption Standard
Digital Signal Processing
Electronic Design Automation
FPGA
Field-Programmable Gate Array
FLEX
GOST
Flexible Logic Element MatriX
Gosudarstvennyy Standart
International Data Encryption
Algorithm
Integrated Circuit
Institude of Electrical and
Electronic Engineers
Logic Array Block
Look-Up Table
Logic Block
Logic Cell
CSM
IDEA
IC
IEEE
LAB
LUT
LB
LC
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Tiếng VIệt
Ma trận logic lập trình đƣợc
Vi mạch tích hợp chuyên dụng
Công cụ thiết kế mạch điện tử có
hỗ trợ máy tính
Phƣơng thƣ́c móc xí ch khối mã
Thiết bị lôgíc lập trình phức hợp
Ngôn ngữ mô tả dòng dữ liệu phát
triển trong qúa trình đào tạo
Chế độ phản hồi mã
Hệ thống quản trị nhà cung cấp và
thành phần
Chế độ sách mã điện tử
Chuẩn mã hoá dữ liệu
Xử lý tín hiệu số
Thiết kế điện tử tự động hoá
Vi mạch dùng cấu trúc mảng phần
tử logic mà ngƣời dùng có thể lập
trình đƣợc
Ma trận phần tử logic linh hoạt
Hệ mã dữ liệu Xô Viết
Thuật toán mã hoá dữ liệu quốc tế
Mạch tích hợp
Học Viện kỹ nghệ Điện và Điện Tử
Mảng lớn các Block lập trình đƣợc
Bảng tìm kiếm
Khối Logic
Tế bào Logic
http://www.lrc-tnu.edu.vn
6
Multiple Array matriX
Ma trận chuỗi đa phần tử
Multi-Chip Module
Mô đun đa chip
Mechanical Computer-Aided
Hệ thống thiết kế cơ khí có trợ giúp
MCAD
Design
của máy tính
OFB
Output Freed Back
Chế độ phản hồi đầu ra
OTP
One - Time Programmable
Loại SRAM lập trình một lần
PES
Proposed Encryption Standard
Chuẩn mã hóa dữ liệu
PLD
Programmable Logic Device
Thiết bị logic lập trình đƣợc
PAL
Programmable Array Logic
Mảng logic lập trình đƣợc
PLA
Programmable Logic Array
Mảng logic lập trình đƣợc
PROM Programmable Read Only Memory Chíp bộ nhớ chỉ đọc lập trình đƣợc
RSA là một thuật toán mật mã hóa khóa công khai. Thuật toán đƣợc Ron
Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại
RSA
Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán lấy từ 3
chữ cái đầu của tên 3 tác giả.
RISC
Reduced Instructions Set Computer Máy tính với tập lệnh đơn giản hóa
SRAM Static Random Access Memory
Bộ nhớ truy cập ngẫu nhiên tĩnh
SSI
Small Scale Integrated
Vi mạch tích hợp cỡ nhỏ
VLSI
Very Large-Scale Integration
Vi mạch tích hợp cỡ lớn
Very high speed integrated circuits Ngôn ngữ mô tả các hệ thống điện
VHDL
HDL
tử số
MAX
MCM
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
DANH MỤC CÁC BẢNG
Bảng
Nội dung
2.1
Một số loại FPGA trên thị trƣờng
2.2
Số cổng sử dụng và các chân I/O của các họ FPGA Altera
3.1
Các tham số của phép hoán vị ban đầu IP
3.2
Các tham số của phép hoán vị FP
3.3
Các tham số của hàm mở rộng E
3.4
Tham số của các hộp S-Box
3.5
Các tham số của phép hoán vị P
3.6
Các tham số của phép hoán vị PC-1
3.7
Các tham số của phép hoán vị PC-2
3.8
Mô tả các tín hiệu vào ra của modul DES
3.9
Danh sách các tệp tin của module DES
3.10
Chức năng các tín hiệu vào/ra của EPC2 LC20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
DANH MỤC CÁC HÌNH VẼ
Hình vẽ
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
1.10
1.11
1.12
1.13
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
Nội dung
Mô hì nh hệ thống truyền tin
Mô hì nh hệ thống truyền tin mật
Mô hình hệ mật khoá bí mật
Mô hình hệ mật khoá công khai
Sơ đồ cấu trúc cộng-nhân
Một mã lặp r vòng với hàm vòng f
Mô tả một vòng của DES
Sơ đồ một vòng lặp của GOST
Sơ đồ cấu trúc của IDEA
Chi tiết mỗi vòng đơn của IDEA
Phép biến đổi ra của quá trình mã hoá IDEA
Các chế độ hoạt động của mã khối
Các kỹ thuật thiết kế mã khối
Cấu trúc của PLA
Cấu trúc của PAL
Cấu trúc của CPLD
Mô tả mô hình của một FPGA
Cấu trúc Logic Cell trong FPGA
Cấu trúc của FPGA
Bốn loại FPGA điển hình
Cấu trúc SRAM FPGA (SRAM Logic Cell)
Cấu trúc của OTP FPGA (OTP Logic Cell)
Quá trình thiết kế trên FPGA
Kiến trúc tổng quát của Altera FPGA MAX 7000
Cấu trúc chung của Module mã khối
Lƣợc đồ của thuật toán DES
Một vòng của DES
Hàm F trong thuật toán DES
Sơ đồ tính khoá của thuật toán DES
Sơ đồ khối tổng quát của Module mã khối DES trên FPGA
Quá trình mã hoá/giải mã DES
Mô tả chức năng module mã hoá DES
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
3.9
3.10
3.11
3.12
3.13
3.14
3.15
3.16
3.17
3.18
3.19
3.20
3.21
Cấu trúc I/O của DES trên công cụ Quartus
Sơ đồ thực thể phép hoán vị IP
Mô tả 16 vòng lặp của DES
Sơ đồ thiết kế của một vòng lặp
Sơ đồ thực thể hộp S-BOX
Sơ đồ khối tạo khoá con
Mô tả khối vào/ra dữ liệu
Sơ đồ liên kết giữa các khối trong module DES
Sơ đồ khối phần cứng của module mã khối DES
Sơ đồ ghép nối giữa FPGA và cáp MV
Sơ đồ ghép nối giữa FPGA và linh kiện cấu hình
Sơ đồ khối phần cứng mô phỏng
Hình ảnh module mã khối DES đã đƣợc thiết kế
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
MỞ ĐẦU
Khi nhu cầu trao đổi thông tin dữ liệu ngày càng lớn và đa dạng, các tiến bộ
về điện tử - viễn thông và công nghệ thông tin không ngừng đƣợc phát triển ứng
dụng để nâng cao chất lƣợng và lƣu lƣợng truyền tin thì các quan niệm về ý tƣởng
và biện pháp bảo vệ thông tin dữ liệu cũng đƣợc đổi mới. Bảo vệ an toàn thông tin
dữ liệu là một chủ đề rộng, có liên quan đến nhiều lĩnh vực và trong thực tế có thể
có rất nhiều phƣơng pháp đƣợc thực hiện để bảo vệ an toàn thông tin dữ liệu. Các
phƣơng pháp bảo vệ an toàn thông tin dữ liệu có thể đƣợc quy tụ vào ba nhóm
chính:
- Bảo vệ an toàn thông tin bằng các biện pháp hành chính.
- Bảo vệ an toàn thông tin bằng các biện pháp kỹ thuật (phần cứng).
- Bảo vệ an toàn thông tin bằng các biện pháp thuật toán (phần mềm).
Ba nhóm trên có thể đƣợc ứng dụng riêng rẽ hoặc phối kết hợp. Môi trƣờng
khó bảo vệ an toàn thông tin nhất và cũng là môi trƣờng đối phƣơng dễ xâm nhập
nhất đó là môi trƣờng mạng và truyền tin. Biện pháp hiệu quả nhất và kinh tế nhất
hiện nay trên mạng truyền tin và mạng máy tính là biện pháp thuật toán.
Để bảo mật thông tin trên đƣờng truyền ngƣời ta sử dụng các phƣơng pháp
mã hoá. Dữ liệu đƣợc biến đổi từ dạng nhận thức đƣợc sang dạng không nhận thức
đƣợc theo một thuật toán nào đó và sẽ đƣợc biến đổi ngƣợc lại ở trạm nhận.
Mật mã là một ngành khoa học chuyên nghiên cứu các phƣơng pháp truyền
tin bí mật. Mật mã bao gồm : Lập mã và phá mã. Lập mã bao gồm hai quá trình: mã
hóa và giải mã. Để bảo vệ thông tin trên đƣờng truyền ngƣời ta thƣờng biến đổi nó
từ dạng nhận thức đƣợc sang dạng không nhận thức đƣợc trƣớc khi truyền đi trên
mạng, quá trình này đƣợc gọi là mã hoá thông tin (encryption), ở trạm nhận phải
thực hiện quá trình ngƣợc lại, tức là biến đổi thông tin từ dạng không nhận thức
đƣợc (dữ liệu đã đƣợc mã hoá) về dạng nhận thức đƣợc (dạng gốc), quá trình này
đƣợc gọi là giải mã. Đây là một lớp bảo vệ thông tin rất quan trọng và đƣợc sử dụng
rộng rãi trong môi trƣờng mạng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
Trong kỹ thuật mật mã , hệ mã khối đƣợc đánh giá là hệ mật có nhiều ƣu
điểm, phù hợp cho các hoạt động bảo mật tốc độ cao . Tuy nhiên, tƣ̀ trƣớc đến nay ở
nƣớc ta, việc thƣ̣c hiện mã khối mới chỉ thƣ̣c hiện bằng phần mềm trên máy tí nh PC
và chỉ áp dụng đƣợc cho các hệ truyền tin có tốc độ kh
ông cao , do vậy khả năng
ứng dụng mã khối vào bảo mật cho các luồng thông tin tốc độ cao còn gặp nhiều
khó khăn. Bài toán bảo mật luồng dữ liệu tốc độ cao chỉ có thể giải quyết đƣợc trên
cơ sở “cƣ́ng hoá” đƣợc các thuật toán mã khối , theo nghĩ a việc thƣ̣c hiện các thuật
toán mã khối đƣợc thiết kế bằng phần cứng . Do tí nh chất phƣ́c tạp của các thuật
toán mã khối, việc cƣ́ng hoá mã khối theo phƣơng pháp thiết kế mạch điện tƣ̉ truyền
thống trong điều kiện nền khoa học và công nghệ ở Việt Nam còn hạn chế là rất khó
khăn, trong khi đó hiện nay đã có nhiều công nghệ hiện đại để xƣ̉ lý bài toán này
nhƣ công nghệ ASIC (Application-Specific Integrated Circuit) hay FPGA (FieldProgrammable Gate Array ).
Xuất phát từ các vấn đề trên, tác giả tập trung nghiên cứu “Thiết kế Hệ
thống mã khối bằng công nghệ FPGA” để cứng hoá các thuật toán mã khối. Việc
nghiên cƣ́u để có thể cƣ́ng hoá các thuật toán mã khối trên c ác công cụ phần cứng
nhằm đáp ƣ́ng các yêu cầu về tốc độ xƣ̉ lý dƣ̃ liệu , tính chủ động, chuyên dụng hoá
thiết bị bảo mật cũng nhƣ giá thành là một hƣớng nghiên cƣ́u mới.
Kết quả nghiên cứu của đề tài sẽ góp phần làm rõ tính ƣu việt của công nghệ
FPGA đƣợc ứng dụng trong thiết kế hệ chuyển đổi mã mật tốc độ cao, đáp ƣ́ng
đƣợc yêu cầu về tốc độ xử lý dữ liệu, tính chủ động, chuyên dụng hoá thiết bị bảo
mật là một sƣ̣ vận dụng , nghiên cƣ́u phù hợp với điều kiện thƣ̣c t ế về công nghệ và
yêu cầu sƣ̉ dụng ở Việt Nam .
Nội dung của đề tài “Thiết kế hệ thống mã khối bằng công nghệ FPGA”
bao gồm:
Chƣơng 1: Hệ truyền tin mật và cơ sở lý thuyết mã khối.
Trình bày các vấn đề cơ bản về lý thuyết truyền tin, lý thuyết mã và mã mật
kết hợp với sự phát triển của kỹ thuật vi xử lý hiện đại; Giới thiệu tổng quan về hệ
truyền tin mật và cơ sở lý thuyết mã khối.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
Chƣơng 2: Công nghệ FPGA và ngôn ngƣ̃ mô tả phần cƣ́ng VHDL.
Trình bày các vấn đề liên quan đến công nghệ FPGA, cấu trúc chức năng của
FPGA, phân loại cũng nhƣ các ứng dụng thực tế của công nghệ FPGA. Giới thiệu
FPGA của hãng Altera và các công cụ thiết kế đi kèm của hãng cùng với ngôn ngữ
mô tả phần cứng VHDL.
Chƣơng 3: Thiết kế hệ thống mã khối.
Chƣơng này trình bày về phƣơng pháp thiết kế module mã khối trên công
nghệ FPGA, phần cứng mô phỏng module DES và các kết quả thiết kế module mã
khối DES trên FPGA.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
CHƢƠNG 1
HỆ TRUYỀN TIN MẬT VÀ CƠ SỞ LÝ THUYẾT MÃ KHỐI
1.1. TỔNG QUAN VỀ HỆ TRUYỀN TIN MẬT.
1.1.1. Mô hì nh hệ thống truyền tin mật .
Trong cuộc sống , con ngƣời luôn có nhu cầu trao đổi thông tin với nhau có
nghĩa là có nh u cầu truyền tin cho nhau . Hình 1.1 biểu diễn mô hì nh của hệ thống
truyền tin bao gồm: Nguồn tin, kênh tin và nhận tin.
nguån tin
kªnh tin
nhËn tin
Hình 1.3: Mô hì nh hệ thống truyền tin.
Trong mô hì nh này : Nguồn tin là nơi sản sinh ra các tin tƣ́c cần truyền đi trên
kênh tin dƣới dạng các bản tin . Kênh tin là môi trƣờng vật lý xác đị nh để truyền các
bản tin dƣới các dạng tín hiệu điện , quang …. Nhận tin là cơ cấu khôi phục thông
tin ban đầu tƣ̀ tí n hiệu lấy ở đầu ra của kênh tin.
Do xã hội ngày càng phát triển , nên nhu cầu trao đổi thông tin cũng tăng theo
không ngƣ̀ng. Các nội dung thông tin có liên quan đến lợi ích , quyền lợi của một số
ngƣời hay một giai cấp nào đó cần đƣợ c giƣ̃ kí n, bí mật vì vậy nhu cầu bảo mật nội
dung thông tin đƣợc truyền đi hì nh thành và phát triển ngày càng lớn.
Song song với sƣ̣ phát triển mạnh mẽ của khoa học công nghệ nói chung và
công nghệ thông tin nói riêng thì bảo mật nội dung thông tin đóng một vai trò hết
sƣ́c quan trọng đối với tất cảc các lĩ nh vƣ̣c : Chính trị, quân sƣ̣ , ngoại giao, kinh tế ,
xã hội … và đối với an ninh của mọi quốc gia trên toàn thế giới.
Do vậy hệ thống tru yền tin mật là hệ thống mà trong đó nội dung thông tin
phải đƣợc bảo vệ và giữ bí mật khi truyền trên kênh tin trƣớc sự tấn công , khám phá
bất hợp pháp của mã thám . Hình 1.2 mô tả một cách tổng quát về mô hì nh của một
hệ thống truyền tin mật . Trong đó : Mã hoá là quá trình biến đổi các bản tin rõ R
thành các bản tin mã M bằng thuật toán mã hoá E K và đƣợc xem nhƣ một hàm :
M = E(R,KE)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
14
nhiÔu
m· th¸m
nguån tin
m· ho¸
kªnh tin
gi¶i m·
nhËn tin
kho¸ mËt m·
kho¸ mËt m·
Hình 1.4: Mô hì nh hệ thống truyền tin mật.
Giải mã là quá trình biến đổi ngƣợc của mã hoá có nghĩa là biến đổi các bản
tin mã M tƣ̀ đầu ra của kênh tin thành các bản tin rõ R để đƣa tới nhận tin và cũng
đƣợc xem nhƣ một hàm:
R = D(M,KD)
Các khoá mã K E và khoá dịch K D đƣợc gọi là khoá mã mật tham gia vào các
thuật toán mã hoá E và thuật toán giải mã D.
Mã thám là các đối tƣợng có khả năng chặn bắt , thu nhận cá c bản tin mã M tƣ̀
kênh tin, nhƣng không biết khoá mã K
và khoá giải mã K D nhằm tì m ra bản tin rõ
R (thông thƣờng mã thám sƣ̉ dụng khoá giải mã K 'D để tìm ra bản rõ R' R).
E
Nhiễu là do sƣ̣ tác động của môi trƣờng truyền dẫn.
Đôi khi thƣờng bị đồng nhất hai khái niệm hệ thống truyền tin mật và hệ mật
khi đánh giá độ mật của hệ thống . Theo [1] hệ mật là một bộ 5 (R, M, K, E, D) thoả
mãn các điều kiện sau:
a. R (không gian các bản tin rõ) là một tập hợp hữu hạn các bản rõ có thể có.
b. M (không gian các bản tin mã ) là một tập hợp các bản tin mã có thể có.
c. K (không gian khoá ) là một tập hợp hữu hạn các khoá mật mã có thể có.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
15
d. Đối vớ i mỗi k K có một quy tắc mã hoá e
k E
và một thuật toán giải mã
tƣơng ƣ́ng d k D, mà mỗi e k: R M và d k: M R là những hàm đƣợc thoả mãn
dk(ek(x)) = x với mọi bản tin rõ x R.
Điều kiện (d) là quan trọng nhất có nghĩa là nếu có một bản tin rõ x đƣợc mã
hoá bằng thuật toán E và bản tin mã nhận đƣợc sau đó đƣợc giải mã bằng thuật toán
giải mã D thì phải thu đƣợc bản tin rõ x ban đầu.
1.1.2. Các phƣơng pháp mã mật cơ bản .
Có hai phƣơng pháp mã mật cơ bản là: Chuyển vị (Transportation) và thay thế
(Substitution).
1.1.2.1. Phương pháp chuyển vị .
Chuyển vị là sƣ̣ thay đổi các vị trí các thành phần của bản tin rõ theo một quy
ƣớc nào đó . Sƣ̣ thay đổi vị trí này phụ thuộc vào một khoá xác đị nh dùng cho cả
mã hoá và giải mã.
Nhận thấy rằng hệ mã chuyển vị không có các phép toán đ ại số nào đƣợc thực
hiện khi mã hoá , giải mã và độ dài của bản tin mã bằng với độ dài của bản tin rõ
,
nên mã thám có thể dễ dàng khám phá để tì m ra bản tin rõ ban đầu nhờ việc tì m các
hoán vị có nghĩa từ bản ti n mã. Các thành phần của bản tin bị xáo trộn thay đổi trật
tƣ̣ làm biến đổi về hì nh thƣ́c nhƣng về “chất” thì vẫn tồn tại tần suất xuất hiện của
các phần tử rõ trong bản mã vẫn giữ nguyên . Phƣơng pháp này có độ mật r ất hạn
chế.
1.1.2.2. Phương pháp thay thế.
Thay thế là sƣ̣ thay thế các phần tƣ̉ của bản tin rõ bằng các phần tƣ̉ của bản tin
mã tƣơng ứng theo một quy ƣớc xác định nào đó để nhận đƣợc bản tin mã mong
muốn. Trong phƣơng phá p thay thế có nhiều dạng khác nhau
(Monoalphabetic), thay thế đa biểu
: thay thế đơn biểu
(Polyalphabetic) và thay thế ngẫu nhiên
(Random substitution). Điển hì nh cho phƣơng pháp thay thế đơn biểu là phƣơng
pháp Julius Caesar với mô hình thay thế tƣ̀ng chƣ̃ cái trong bản rõ bằng một chƣ̃ cái
khác tƣơng ứng để tạo thành bản mã . Trong phƣơng pháp này các chƣ̃ cái rõ tƣ̀ A
đến Z nằm trên hai vòng tròn đồng tâm , bƣớc lệch giƣ̃a hai vòng tròn chí nh là bƣớc
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
16
thay thế. Phƣơng pháp này chỉ làm thay đổi bộ mặt của bản rõ bằng việc dị ch
chuyển tần xuất , rất dễ dàng khám phá . Với phƣơng pháp thay thế đa biểu , việc
khám phá trở nên khó khăn hơn , đặc trƣng cho phƣơng pháp này là phƣơng pháp sử
dụng bảng Vigenère . Cuối cùng là phƣơng pháp thay thế ngẫu nhiên . Việc thay thế
càng ngẫu nhiên thì độ mật càng cao , song việc phục hồi lại bản rõ lại càng phƣ́c
tạp. Để thƣ̣c hiện quá trì nh mã hoá và giải mã cầ n phải có khoá mã .
1.1.3. Mô hì nh hệ mật .
Các hệ mật hiện nay đƣợc chia thành hai loại : hệ mật khóa bí mật và hệ mật
khóa công khai . Trong hệ mật khóa bí mật , nhƣ̃ng ngƣời sƣ̉ dụng hợp pháp (ngƣời
gƣ̉i và ngƣời nhận ) phải chia sẻ một khóa bí mật chung và khóa đó không đƣợc biết
đối với thám mã đối phƣơng . Trong hệ mật khóa công khai , ngƣời sƣ̉ dụng hợp
pháp chỉ cần các thông tin trung thực công khai nào đó . Trong luận văn chỉ đề cập
đến việc ƣ́ng dụng các hệ mật khoá bí mật .
1.1.3.1. Hệ mật đối xứng (Hệ mật khoá bí mật).
Theo [2] mô hì nh hệ mật của Shannon đƣợc thể hiện trong hì nh 1.3. Trong mô
hình này, khóa bí mật Z đƣợc phân phối tới ngƣời gửi và n gƣời nhận theo một kênh
an toàn. Khóa này sau đó đƣợc sử dụng để mã hóa bản rõ X thành bản mã Y bởi
ngƣời gƣ̉i và đƣợc dùng để giải mã bản mã Y thành bản rõ X bởi ngƣời nhận . Bản
mã đƣợc truyền trên kênh không an toàn và giả thiết rằng thám mã đối phƣơng luôn
có thể truy nhập để nhận đƣợc các bản mã . Tất nhiên thám mã không thể truy nhập
đƣợc tới khóa bí mật . Hệ mật khóa bí mật nhƣ thế đƣợc gọi là hệ mật đối xƣ́ng để
phân biệt với hệ mật khóa công khai không đối xứng trong đó các khóa khác nhau
đƣợc sƣ̉ dụng bởi ngƣời mã và ngƣời dị ch . Chú ý rằng X , Y, và Z trong mô hình
này là các biến ngẫu nhiên . Trong mô hì nh này , cũng luôn giả thiết bản rõ X
và
khóa Z là độc lập thống kê.
Các hệ mật khóa bí mật thƣờng đƣợc chia thành các hệ mã khối và hệ mã
dòng. Đối với mã khối bản rõ có dạng các khối "lớn" (chẳng hạn 64-bit) và dãy các
khối đều đƣợc mã bởi cùng m ột hàm mã hóa , tƣ́c là bộ mã hóa là một hàm không
nhớ. Trong mã dòng, bản rõ thƣờng là dãy các khối "nhỏ" (thƣờng là 1-bit) và đƣợc
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
17
biến đổi bởi một bộ mã hóa có nhớ.
Các hệ mã khối có ƣu điểm là chúng có thể đƣ ợc chuẩn hóa một cách dễ dàng ,
bởi vì các đơn vị xƣ̉ lý thông tin hiện nay thƣờng có dạng block nhƣ bytes hoặc
words. Ngoài ra trong kỹ thuật đồng bộ , việc mất một block mã cũng không ảnh
hƣởng tới độ chí nh xác của việc giải mã của các khối tiếp sau , đó cũng là một ƣu
điểm khác của mã khối.
Nhƣợc điểm lớn nhất của mã khối là phép mã hóa không che dấu đƣợc các
mẫu dƣ̃ liệu : các khối mã giống nhau sẽ suy ra các khối rõ cũng giống nha
u. Tuy
nhiên nhƣợc điểm này có thể đƣợc khắc phục bằng cách đƣa vào một lƣợng nhỏ có
nhớ trong quá trì nh mã hóa , tƣ́c là bằng cách sƣ̉ dụng cách thƣ́c móc xí ch khối mã
(CBC - Cipher Block Channing mode) trong đó hàm mã hóa không nhớ đƣợc áp vào
tổng XOR của khối rõ và khối mã trƣớc đó . Phép mã lúc này có kiểu cách kỹ thuật
nhƣ mã dòng áp dụng đối với các khối "lớn".
Thám mã
Nguồn rõ
X
X
X
Mã
M·hoá
ho¸
EK (.)
Y
ZZ
Giải mã
DK (.)
Nhận tin
X
Z
Kênh an toàn
Nguồn
khoá
Hình 1.3: Mô hình hệ mật khoá bí mật.
1.1.3.2. Hệ mật không đối xứng (Hệ mật khoá công khai).
Năm 1976, Diffie và Hellman ở trƣờng Đại học tổng hợp Stanford đã đƣa ra
một dạng mới của hệ mật với tên gọi là hệ mật khoá công khai
Cryptosystem). Điểm khác biệt giƣ̃a hệ mật không đối xƣ́ng và
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
(Public-key
hệ mật đối xƣ́ng
http://www.lrc-tnu.edu.vn
18
chính là khoá mã dịch . Trong hệ mật không đối xƣ́ng , khoá mã và khoá dịch khác
nhau, hơn nƣ̃a chúng không chỉ khác nhau mà còn đƣợc tí nh toán trong mối quan hệ
tƣơng tác theo các hàm toán học nào đó . Đây là hệ mật hiện đại dựa trên cơ sở các
thành tựu của toán học và công nghệ thông tin , thể hiện chủ yếu trên độ phƣ́c tạp
tính toán và độ tiện dụng trong quá trình phân phối khoá , điển hì nh cho hệ mật này
là các bài toán khoá công khai nhƣ RSA, Diffie – Hellman…
Bản rõ
(X)
Ngƣời gửi
(A)
Bộ mã hoá
Bản mã
Y=EK1 (X)
Khoá công
khai (K1)
Ngƣời nhận
(B)
Bộ giải mã
X=DK2 (EK1 (X))
Khoá bí
mật (K2)
Hình 1.4: Mô hình hệ mật khoá công khai.
Quá trình mã dịch đƣợc mô tả nhƣ sau:
Y = EK1 (X)
X = DK2(EK1(X))
K1 = f (K2)
K2 = f (K1)
trong đó Y - bản mã; X - bản rõ dịch; K1 - khoá mã; K2 - khoá dịch.
Hệ mật với khoá công khai đƣợc xác đị nh bởi 3 thuật toán để tạo khoá , mã hoá
và dịch mã . Thuật toán tạo khoá đƣợc công khai , có thể cung cấp cho nó đầu vào
dòng ngẫu nhiên r có độ dài cần thiết và nhận đƣợc trên đầu ra cặp khoá (k1,k2). Một
trong hai khoá (chẳng hạn khoá k 1) đƣợc công bố rộng rãi, nó đƣợc gọi là khoá công
khai, còn khoá thứ hai đƣợc giấu kín và đƣợc gọ i là khoá bí mật. Các thuật toán mã
hoá E K1 và dịch mã D
K2
phải đƣợc bảo đảm để với bản rõ bất kỳ
m đều có :
DK2(EK1(m)) = m
1.1.4. Phân loại hệ mã .
Mã khối và mã dòng là hai loại hình mã hoá cơ bản , thƣ̣c hiện chƣ́c năng mã
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -