M“t m¢ và kỹ thu“t hØn lo⁄n trong b£o m“t thông tin
B£o m“t là mºt kỹ thu“t thi‚t y‚u trong h» thŁng thông tin. Xu hướng
ph¡t tri”n công ngh» thông tin là người dùng có th” chia s· và sß dụng
chung tài nguy¶n m⁄ng tł nhœng vị tr‰ địa lý kh¡c nhau trong c¡c thời
đi”m kh¡c nhau, d¤n đ‚n sự ph¥n t¡n tài nguy¶n và h“u qu£ là t«ng nguy
cơ m§t m¡t dœ li»u và c¡c thông tin có gi¡ trị. Càng mở rºng c¡c k‚t nŁi
th… xu§t hi»n càng nhi•u lØ hŒng b£o m“t, tài nguy¶n càng d„ bị t§n công
và x¥m ph⁄m.
M“t m¢ là mºt trong nhœng bi»n ph¡p an toàn và đ¡ng tin c“y đ” b£o
m“t dœ li»u hi»u qu£. Do đó, øng dụng kỹ thu“t m“t m¢ là xu hướng t§t
y‚u trong truy•n tin b£o m“t. Do v“y nhœng thay đŒi trong c¡ch đ¡nh gi¡
đº an toàn cıa m“t m¢ hi»n đ⁄i đ¢ mở ra nhi•u hướng nghi¶n cøu mới cıa
m“t m¢ như: B£o m“t trong đi»n to¡n đ¡m m¥y; Mở rºng mô h…nh m¢ hóa
cho nhóm đŁi tưæng và cho vi»c gi£i m¢ tłng phƒn; An toàn trước c¡c t§n
công v“t lý; An toàn trước sự t§n công cıa m¡y t‰nh lưæng tß và B£o m“t
trong m⁄ng lưới IoTs.
C¡c hàm hØn lo⁄n rời r⁄c đưæc chøng minh là k‚ thła đưæc c¡c t‰nh
ch§t cıa c¡c hàm hØn lo⁄n li¶n tục như t‰nh ch§t nh⁄y c£m với đi•u ki»n
đƒu, nh⁄y c£m với sự thay đŒi gi¡ trị cıa c¡c tham sŁ và không th” dự b¡o
dài h⁄n. Ưu đi”m cıa m“t m¢ hØn lo⁄n đưæc xem như mô h…nh ph¡t tri”n
m“t m¢ hi»n đ⁄i [25, 31]. V• nguy¶n lý, c¡c phương ph¡p b£o m“t øng dụng
hØn lo⁄n là læi dụng sự phøc t⁄p cıa c¡c đặc t‰nh đºng học cıa h» thŁng
hØn lo⁄n cũng như đặc trưng cıa h» thŁng hØn lo⁄n đ” che gi§u thông tin
dựa tr¶n c¡c gi£i thu“t thực hi»n kh¡c nhau. Do đó, m“t m¢ hØn lo⁄n là
mºt hướng nghi¶n cøu mới, an toàn và đ¡ng tin c“y đ” b£o m“t dœ li»u
1hi»u qu£.
M“t m¢ h⁄ng nhẹ và m“t m¢ hØn lo⁄n có th” thay th‚ m“t m¢ chu'n là
hai hướng nghi¶n cøu đưæc quan t¥m trong nhœng n«m gƒn đ¥y. Ưu nhưæc
đi”m cıa m“t m¢ hØn lo⁄n đ¢ đưæc nghi¶n cøu chi ti‚t. Dựa tr¶n nhœng
t‰nh ch§t này, lu“n ¡n đ• xu§t dùng hàm hØn lo⁄n cho m“t m¢ h⁄ng nhẹ
đ” c£i thi»n c¡c nhưæc đi”m v• b£o m“t cıa m“t m¢ h⁄ng nhẹ. Bài to¡n
thi‚t k‚ m“t m¢ h⁄ng nhẹ sß dụng hàm hØn lo⁄n rời r⁄c như là mºt hướng
đi mới đ” c£i thi»n thời gian thực thi và kh£ n«ng b£o m“t cho m“t m¢
h⁄ng nhẹ.
C¡c thu“t to¡n m“t m¢ đưæc đ• xu§t trong [30], [16] và thu“t to¡n 'n
tin (steganography) [21] d„ dàng bị ph¥n t‰ch khi chu kỳ cıa hàm hØn lo⁄n
rời r⁄c qu¡ ng›n [7]. C¡c t¡c gi£ trong [8] đ¢ gi£i th‰ch sự phụ thuºc cıa
chu kỳ vào c¡c tham sŁ đi•u khi”n. T¡c gi£ trong [8] b…nh lu“n r‹ng chu kỳ
cıa hàm hØn lo⁄n càng dài th… càng tŁt v• mặt b£o m“t khi ¡p dụng hàm
hØn lo⁄n đó vào h» m“t m¢. Do đó, chu kỳ cıa h» hØn lo⁄n rời r⁄c cũng là
mºt trong nhưng tham sŁ quan trọng trong bài to¡n thi‚t k‚ m“t m¢ hØn
lo⁄n nói chung.
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
TẠ THỊ KIM HUỆ
NGHIÊN CỨU HỆ MẬT MÃ KHỐI
DỰA TRÊN HỖN LOẠN RỜI RẠC
Chuyên ngành: Kỹ thuật viễn thông
Mã số: 62520208
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG
HÀ NỘI - 2017
Công trình này được hoàn thành tại
Trường Đại học Bách khoa Hà Nội
Người hướng dẫn khoa học: PGS.TS.Hoàng Mạnh Thắng
Phản biện 1: GS.TS. Nguyễn Bình
Phản biện 2: PGS.TS. Bạch Nhật Hồng
Phản biện 3: PGS.TS. Phạm Ngọc Thắng
Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp trường
họp tại Trường Đại học Bách khoa Hà Nội
vào hồi 9 giờ, ngày 15 tháng 03 năm 2017
Có thể tìm hiểu luận án tại:
1. Thư viện Tạ Quang Bửu, Trường ĐHBK Hà Nội
2. Thư viện Quốc gia Việt Nam
MỞ ĐẦU
1. Mật mã và kỹ thuật hỗn loạn trong bảo mật thông tin
Bảo mật là một kỹ thuật thiết yếu trong hệ thống thông tin. Xu hướng
phát triển công nghệ thông tin là người dùng có thể chia sẻ và sử dụng
chung tài nguyên mạng từ những vị trí địa lý khác nhau trong các thời
điểm khác nhau, dẫn đến sự phân tán tài nguyên và hậu quả là tăng nguy
cơ mất mát dữ liệu và các thông tin có giá trị. Càng mở rộng các kết nối
thì xuất hiện càng nhiều lỗ hổng bảo mật, tài nguyên càng dễ bị tấn công
và xâm phạm.
Mật mã là một trong những biện pháp an toàn và đáng tin cậy để bảo
mật dữ liệu hiệu quả. Do đó, ứng dụng kỹ thuật mật mã là xu hướng tất
yếu trong truyền tin bảo mật. Do vậy những thay đổi trong cách đánh giá
độ an toàn của mật mã hiện đại đã mở ra nhiều hướng nghiên cứu mới của
mật mã như: Bảo mật trong điện toán đám mây; Mở rộng mô hình mã hóa
cho nhóm đối tượng và cho việc giải mã từng phần; An toàn trước các tấn
công vật lý; An toàn trước sự tấn công của máy tính lượng tử và Bảo mật
trong mạng lưới IoTs.
Các hàm hỗn loạn rời rạc được chứng minh là kế thừa được các tính
chất của các hàm hỗn loạn liên tục như tính chất nhạy cảm với điều kiện
đầu, nhạy cảm với sự thay đổi giá trị của các tham số và không thể dự báo
dài hạn. Ưu điểm của mật mã hỗn loạn được xem như mô hình phát triển
mật mã hiện đại [25, 31]. Về nguyên lý, các phương pháp bảo mật ứng dụng
hỗn loạn là lợi dụng sự phức tạp của các đặc tính động học của hệ thống
hỗn loạn cũng như đặc trưng của hệ thống hỗn loạn để che giấu thông tin
dựa trên các giải thuật thực hiện khác nhau. Do đó, mật mã hỗn loạn là
một hướng nghiên cứu mới, an toàn và đáng tin cậy để bảo mật dữ liệu
1
hiệu quả.
Mật mã hạng nhẹ và mật mã hỗn loạn có thể thay thế mật mã chuẩn là
hai hướng nghiên cứu được quan tâm trong những năm gần đây. Ưu nhược
điểm của mật mã hỗn loạn đã được nghiên cứu chi tiết. Dựa trên những
tính chất này, luận án đề xuất dùng hàm hỗn loạn cho mật mã hạng nhẹ
để cải thiện các nhược điểm về bảo mật của mật mã hạng nhẹ. Bài toán
thiết kế mật mã hạng nhẹ sử dụng hàm hỗn loạn rời rạc như là một hướng
đi mới để cải thiện thời gian thực thi và khả năng bảo mật cho mật mã
hạng nhẹ.
Các thuật toán mật mã được đề xuất trong [30], [16] và thuật toán ẩn
tin (steganography) [21] dễ dàng bị phân tích khi chu kỳ của hàm hỗn loạn
rời rạc quá ngắn [7]. Các tác giả trong [8] đã giải thích sự phụ thuộc của
chu kỳ vào các tham số điều khiển. Tác giả trong [8] bình luận rằng chu kỳ
của hàm hỗn loạn càng dài thì càng tốt về mặt bảo mật khi áp dụng hàm
hỗn loạn đó vào hệ mật mã. Do đó, chu kỳ của hệ hỗn loạn rời rạc cũng là
một trong nhưng tham số quan trọng trong bài toán thiết kế mật mã hỗn
loạn nói chung.
2. Những vấn đề còn tồn tại
Tính chất phức tạp của hệ hỗn loạn tạo ra tính ưu việt trong bảo mật
thông tin như là khả năng chịu đựng các tấn công phân tích mã, tăng tốc
độ xử lý, tăng độ phức tạp thuật toán. Điều này đã được khẳng định trong
các nghiên cứu của Kocarev [24], Masuda [31] và Fridrich [16]. Tìm ra các
bài toán thiết kế hệ mật mã dựa trên hỗn loạn phù hợp với xu hướng phát
triển của mật mã hiện đại.
Mật mã hạng nhẹ hướng tới việc tìm ra điểm cân bằng của ba yếu tố:
Giảm tài nguyên thực thi, giảm thời gian xử lý, tăng mức độ bảo mật [14].
Do đó, hướng phát triển của mật mã hạng nhẹ được quan tâm nhiều hiện
nay là cải tiến các hệ mã thông qua việc đề xuất các hàm mã hóa mới [32].
Phân bố chu kỳ của hàm Cat hai chiều (Arnold’s Cat map) đã được
phân tích bởi Chen và các cộng sự trong [7, 8, 9], tuy nhiên phương pháp
này chỉ áp dụng cho hàm Cat hai chiều và cho các trường hợp giá trị tham
số hoàn toàn xác định. Khi áp dụng cho hàm Cat đa chiều phương pháp
2
này trở nên phức tạp rắc rối, và việc đánh giá chu kỳ của hàm Cat mở rộng
vẫn là một vấn đề mở cần tìm hiểu.
3. Mục tiêu, đối tượng và phạm vi nghiên cứu
Bài toán thiết kế thuật toán hệ mật mã sử dụng các ánh xạ hỗn loạn đã
được nghiên cứu rất nhiều trong thời gian gần đây. Có thể khẳng định rằng
đây là một hướng nghiên cứu mới trong việc tạo ra những bộ mã mật có
thể tương đương những bộ mã truyền thống về khả năng bảo mật, dễ dàng
thực hiện trên phần cứng, giảm thời gian xử lý, giảm chi phí thiết kế.
Luận án nghiên cứu một số hướng phát triển của mật mã hiện đại từ
đó dẫn dắt các ra vấn đề trong mật mã hỗn loạn. Dựa trên những vấn đề
đã phân tích, luận án đề xuất thuật toán tạo mật mã khối hỗn loạn theo
cấu trúc mạng hoán vị thay thế (SPN). Khả năng bảo mật của hệ thống
cũng được đánh giá qua các hệ số đặc trưng cho các tấn công bảo mật.
Luận án đề xuất hai hàm hỗn loạn rời rạc là Skew Tent và Standard
cho mô hình thiết kế hệ mật mã hỗn loạn hạng nhẹ.
Luận án đề xuất phương pháp mở rộng hàm Arnold Cat rời rạc dựa
trên biến đổi giả Hadamard nhanh gọi là hàm Cat-Hadamard. Kết quả đạt
được là hàm Cat-Hadamard kế thừa hoàn toàn các đặc tính hỗn loạn của
hàm Cat hai chiều, do đó có thể thay thế hàm Cat bởi Cat-Hadamard trong
các ứng dụng mật mã.
4. Phương pháp nghiên cứu
Luận án nghiên cứu gồm lý thuyết, mô phỏng và thực nghiệm. Phân tích
lý thuyết cho các ý tưởng đề xuất để giải quyết vấn đề thông qua công cụ
là toán học với các chứng minh rõ ràng. Các phân tích đánh giá về mặt lý
thuyết được kiểm chứng qua mô phỏng trên máy tính bằng Matlab hoặc
ngôn ngữ C/C++. Một phần trong các nghiên cứu được thực hiện trên
phần cứng và phần mềm cho thấy khả năng ứng dụng thực tế của ý tưởng
đề xuất.
5. Ý nghĩa khoa học và những đóng góp của luận án
3
Luận án nghiên cứu tính chất của các hàm hỗn loạn khi được biểu diễn
trong miền hữu hạn chính xác. Ảnh hưởng của các tham số đến tính chất
đầu ra và chu kỳ của hàm hỗn loạn một chiều, hai chiều hoặc nhiều chiều.
Từ đó đề xuất thuật toán mật mã khối theo cấu trúc mạng lưới hoán vị
thay thế với các cấu trúc lớp thay thế S-box và lớp hoán vị dựa trên hỗn
loạn.
Mở rộng hàm CAT rời rạc trong miền số nguyên hữu hạn và trong
trường Galois, so sánh với các phương pháp hiện có thông qua việc tính
toán Kolmogorov-Sinai (KS) entropy, hoặc phân bố xác suất Chi- bình
phương với giả thiết phân bố của chuỗi giả ngẫu nhiên được tạo ra là một
phân bố đều.
Đánh giá các trạng thái trung gian được tạo ra theo các bước lặp hàm
Cat map mở rộng, lựa chọn tham số thay đổi. Chứng minh các tính chất
của hàm CAT mở rộng có sự kế thừa từ hàm CAT hai chiều, thông qua
biến đổi Hadamard nhanh, số chiều của CAT được tăng lên nhanh chóng
trở thành một hàm đa biến đầu vào. Hai ứng dụng hàm Cat mở rộng là
thiết kế bộ tạo đa ma trận MDS cho hệ mật mã khối và bộ tạo chuỗi số
giả ngẫu nhiên.
6. Cấu trúc nội dung của luận án
Chương 1, luận án trình bày các nguyên tắc thiết kế hệ mật mã hỗn loạn
và các vấn đề còn tồn tại trong hệ mật mã hỗn loạn, từ đó đề xuất một mô
hình thiết kế hệ mật mã khối hỗn loạn dựa trên cấu trúc lưới hoán vị thay
thế cho ứng dụng mã hóa ảnh. Chương 2, luận án đề xuất hai biến thể cho
thuật toán mật mã khối hạng nhẹ theo cấu trúc mạng hoán vị thay thế
(SPN) dựa trên hỗn loạn. Các thiết kế hướng tới tiêu chí tăng độ bảo mật
nhưng vẫn thỏa mãn yêu cầu cài đặt, tài nguyên sử dụng và thời gian xử lý
phù hợp với yêu cầu của thuật toán mật mã hạng nhẹ. Chương 3 đề xuất
một dạng thức mở rộng hàm Cat dựa trên biến đổi giả Hadamard nhanh,
được gọi là hàm Cat-Hadamard. Đề xuất hai ứng dụng hàm Cat mở rộng
là thiết kế bộ tạo đa ma trận MDS cho hệ mật mã khối và bộ tạo chuỗi số
giả ngẫu nhiên.
4
Chương 1
MẬT MÃ HỖN LOẠN
1.1. Nguyên lý thiết kế mật mã hỗn loạn
Hỗn loạn được nghiên cứu trong bảo mật về cơ bản chia làm hai nhánh
nghiên cứu chính, là bảo mật cho luồng bit ngay trong quá trình truyền tin
và bảo mật cho cả một đơn vị dữ liệu, thường được tính theo khối bit/byte
dữ liệu [24].
Nghiên cứu về hệ mật mã hỗn loạn trong [25], [24] và [43], các tác giả
đã đề xuất 10 nguyên tắc thiết kế hệ mã mật dựa trên hỗn loạn là:
1. Định nghĩa đầy đủ và nghiêm ngặt các nguyên lý thiết kế.
2. Định nghĩa đầy đủ và nghiêm ngặt về khóa và không gian khóa.
3. Lựa chọn các hàm hỗn loạn (ánh xạ hỗn loạn) có độ nhạy cao để điều
khiển các tham số không phù hợp.
4. Lựa chọn hàm hỗn loạn không nên làm lộ toàn bộ đặc tính động lực
học của hệ thống: Điều này có thể làm cho kẻ tấn công dự đoán thông
tin về các tham số điều khiển hoặc điều kiện khởi tạo.
5. Phân tích hiệu năng của các quỹ đạo hỗn loạn như nguồn Entropy.
6. Nên sử dụng các hàm (ánh xạ) hỗn loạn có hàm mật độ phân bố đều
và sự đo lường tập bất biến không phụ thuộc vào các tham số điều
khiển.
5
Kj
Input
data
Encryptor
Key generator
Control _ Block
Buffer
Output
data
Decryptor
Kr-j-1
control
Hình 1.1: Sơ đồ khối thiết kế phần cứng
7. Không gian bản mã phải được xác định theo cách mà sự khôi phục
lại đặc tính động học của các hàm hỗn loạn là không khả thi.
8. Thời gian mã hóa/giải mã không phụ thuộc vào giá trị của khóa bí
mật của một hệ mật mã hỗn loạn.
9. Hệ mật mã hỗn loạn có khả năng chống lại các kiểu tấn công cổ điển
[39, 43].
10. Chống được các tấn công tương ứng với các ứng dụng cụ thể.
1.2. Đề xuất hệ mật mã khối hỗn loạn rời rạc dựa
trên cấu trúc mạng hoán vị - thay thế
Luận án đề xuất sơ đồ khối phần cứng cho hệ mật mã khối hỗn loạn, thiết
kế này đề xuất việc tích hợp cả phần giải mã và phần tạo mã trên cùng một
khối. Do đó, phần cứng có thể thực hiện chức năng của một bộ mã hoặc
một bộ giải mã đồng thời, phù hợp với các mô hình lưu trữ hoặc truyền
thông tin trong thời gian thực như Hình 1.1.
Bản rõ là ảnh số RGB, kích thước cho mỗi lớp mầu là là H × W trong
đó H là kích thước ảnh theo chiều dọc cũng là số lượng điểm ảnh đếm được
theo chiều dọc và W là kích thước ảnh theo chiều ngang cũng là số lượng
điểm ảnh đếm được theo chiều ngang, được biểu diễn dưới dạng chuỗi các
byte liên tiếp một chiều.
6
Bộ tạo khóa
Bộ tạo khóa
Kj={Ksj; Kpj}
Kr-j-1={Ksr-j-1; Kpr-j-1}
Bản rõ
Bản rõ
rs
Khối thay thế byte
Hàm SkewTent
Ksr-j-1
Ksj
Khối thay thế byte
Hàm SkewTent ngược
rs
r
r
rp
Khối hoán vị bit
Hàm Standard
Bản mã
Kpr-j-1
Kpj
Kênh truyền
Khối hoán vị bit ngược
Hàm Standard
rp
Bản mã
Hình 1.2: Thuật toán mã hóa ảnh RGB
Thuật toán lập mã
Hình 1.2 mô tả thuật toán lập mã với khóa bí mật Kj được tạo ra từ bộ
tạo khóa. Kj đóng vai trò là tham số điều khiển và tạo ra hai khóa con cho
khối thay thế và hoán vị là Ksj và Kpj , ta có Kj = {Ksj ; Kpj }.
Ảnh RGB-8bit có 3 lớp mầu và mỗi điểm ảnh được mã hóa bằng 8-bit,
ảnh đầu vào được biến đổi thành một chuỗi một chiều gồm các byte là
P = [p1 p2 ...pm ...], trong đó pm ∈ {0, 1, ..., 255}. Chuỗi P được phần chia
thành các khối có kích thước cố định là Tblock = 2 byte. Khối thứ b là B(b)
sẽ chứa byte thứ i và byte thứ (i + 1)th của chuỗi P . Ta có, B(b) = [pi pi+1 ]
là một khối gồm hai byte pi và pi+1 .
Mỗi byte trong khối B(b) được thay thế giá trị bằng việc áp dụng hàm
Skew Tent rời rạc [15, 31]. Ksj là tập các tham số điều khiển tại vòng thứ
j, ta có Ksj = [ksj1 ; ...; ksji ; ...; ksjrs ]. Trong đó, ksji là tham số điều khiển
tại vòng thứ i của quá trình thay thế và tại vòng thứ j của toàn bộ thuật
toán. Sau đó, mỗi khối B(b) thu được sau tiến trình thay thế được sắp xếp
lại trong ma trận bit hai chiều để thực hiện quá trình hoán vị, với kích
thước ma trận hai chiều là M × M . Trong quá trình hoán vị, vị trí các bit
trong ma trận hai chiều được hoán đổi bằng hàm Standard [26]. Quá trình
thay thế giá trị byte được lặp lại rs lần, sau đó đầu ra của khối thay thế
sẽ là đầu vào của khối hoán vị. Quá trình hoán vị vị trí các bit trong ma
trận hai chiều được lặp lại rp lần, và cả hai quá trình này được lặp thêm r
7
LFSR1
Qk1(n)
X1(0)
f(X1(n-1))
Bộ tạo các giá
trị khởi tạo
ngẫu nhiên
Xi(0)
LFSR2
Qk2(n)
X2(0)
f(X2(n-1))
LFSR3
Qk3(n)
X3(0)
X1(n)
X2(n)
X3(n)
Tạo ra các
tham số điều
khiển
Ksj
Kpj
f(X3(n-1))
Hình 1.3: Bộ tạo khóa hỗn loạn
lần cho toàn bộ thuật toán.
Thuật toán giải mã
Thuật toán giải mã là các tiến trình thực thi ngược lại so với thuật toán mã
hóa. Tham số của quá trình thay thế ngược hay còn được gọi là giải thay
thế là ksji sẽ được đồng bộ với các giá trị tương ứng ở thuật toán mã hóa.
Toàn bộ các đầu ra của thuật toán giải mã sẽ thu được sau r vòng lặp. Về
mặt thực thi tham số Kr−j−1 cho lần lặp thứ (r − j − 1) ở quá trình giải mã
có giá trị tương đương với tham số Kj tại vòng lặp thứ j của quá trình mã
hóa. Khối điều khiển trong sơ đồ Hình 1.1 sẽ đồng bộ hai tập khóa tương
ứng Kj and Kr−j−1 cho cả bộ mã hóa và giải mã, ta có Kj = {Ksj ; Kpj }
và Kr−j−1 = {Ksr−j−1 ; Kpr−j−1 }.
Bộ tạo khóa hỗn loạn
Kiến trúc bộ tạo khóa hỗn loạn trong thiết kế này dựa trên mô hình được
trình bày trong [15]. Bộ tạo khóa gồm hàm Logistic được kết nôi song song
như Hình 1.3. Trong đó, X1 (0) , X2 (0) và X3 (0) nằm trong khoảng từ 1
đến 2N − 1.
8
(a) Hình ảnh của bản rõ 1 và bản mã 1
(b) Hình ảnh của bản rõ 2 và bản mã 2
Hình 1.4: Hình ảnh của bản rõ và bản mã tương ứng với thuật toán đề xuất
Phân tích bảo mật
Đánh giá mức độ bảo mật của hệ mật mã khối hỗn loạn đề xuất, luận án
lựa chọn các thông số NPCR và UACI [45]. Để xác định độ nhạy cảm của
hệ mật mã đề xuất với khóa mật, xét hệ số CDR [27], hệ số này chỉ rõ sự
thay đổi nhỏ của khóa bí mật, sẽ làm thay đổi rất lớn giá trị đầu ra của
bản mã. Điều này rất có ý nghĩa trong việc chống tấn công vét cạn và tấn
công thống kê, giả sử kẻ thù có năng lực tính toán siêu việt có thể tiến
hành được bất cứ phép tìm kiếm vét cạn không gian khóa hữu hạn, khi chỉ
số CDR tiến đến 100% thì thời gian cần cho thực hiện tấn công vét cạn là
gần như vô hạn.
Bảng 1.1, lưu các giá trị của các hệ số CDR, NPCR, UACI, các tác giả
trong [45] chỉ ra rằng nếu các giá trị NPCR >99.56%, UACI >33.22%, thì
hệ mật mã không bị phân tích bởi các loại tấn công bảo mật như tấn công
vét cạn, tấn công vi sai và tấn công chỉ biết bản mã [45]. Các giá trị cho
thấy khả năng chống tấn công của hệ mã đề xuất hoàn toàn tương đương
với các bộ mã kinh điển AES.
9
Bảng 1.1: So sánh các hệ số NPCR, UACI và CDR của bản mã thu được từ thuật
toán đề xuất và AES
Ảnh 1
Thuật toán
NPCR
UACI
CDR
Mật mã khối hỗn loạn [C1]
99.63%
33.39%
94.65%
AES - Chế độ CBC [41]
99.60%
33.41%
96.66%
Thuật toán
Ảnh 2
NPCR
UACI
CDR
Mật mã khối hỗn loạn [C1]
99.72%
33.56%
95.12%
AES - Chế độ CBC [41]
99.85%
33.31%
98.54%
Bảng 1.2: So sánh tài nguyên phần cứng thực thi trên kit phát triển Altera FPGA
DE2
Thuật toán
Mật mã khối
Tổng số
Tổng số
Pin
Thời gian
cổng Logic
thanh ghi
12%
4%
8%
181.174 ms
7%
4%
82%
196.608 ms
36%
28%
82%
4 ms
mã hóa
hỗn loạn [C1]
AES - Chế độ ECB [41]
nối tiếp
AES - Chế độ ECB [41]
song song
Tài nguyên thực thi
Các mô tả thiết kế phần cứng của thuật toán được trình bày trong các bài
báo đã công bố [C1] và [C3]. Kết quả thực nghiệm chỉ ra rằng thuật toán
mật mã khối hỗn loạn theo cấu trúc SPN phù hợp với các tiêu chí thiết kế
và giải quyết các vấn đề đã phân tích ở trên. Tài nguyên của hệ mật mã
khi thực thi trên kit phát triển Altera FPGA DE2 là rất nhỏ ≤ 15% so với
tài nguyên của toàn hệ thống.
10
Chương 2
ĐỀ XUẤT HỆ MẬT KHỐI HẠNG NHẸ DỰA VÀO
CÁC ĐẶC TÍNH HỖN LOẠN CỦA HÀM SKEW TENT
VÀ STANDARD RỜI RẠC
2.1. Thiết kế lớp S-box 4×4 móc xích dựa trên tính
chất hàm Skew Tent rời rạc
Hàm Skew Tent
(
xn =
xn−1 /r nếu xn−1 ∈ [0, r]
,
(1 − xn−1 ) / (1 − r) nếu xn−1 ∈ (r, 1]
(2.1)
với 0 < r ≤ 1. Đồ thị hàm Skew Tent được mô tả trong Hình 2.1.
Hàm Skew Tent rời rạc [30] là FA : [0, M ] → [0, M ] với tham số 0 <
A < M là tham số điều khiển, được định nghĩa như sau.
(
xn−1 /A nếu 0 ≤ xn−1 ≤ A
FA (xn−1 ) =
.
(2.2)
(M − xn−1 ) / (M − A) nếu A < xn−1 ≤ M
Hàm Skew tent lượng tử hóa được mô tả như sau:
(
X
ceil M
×K
nếu1 ≤ X ≤ K
1
.
FK (X) =
M −X
f loor M × M −K + 1 nếu K < X ≤ M
(2.3)
1 là một ánh xạ song ánh, M là số nguyên dương
Dễ dàng nhận thấy, FK
và M ≥ 2. Trong mật mã học, ánh xạ đảo ngược có vai trò quan trọng
11
SKEW TENT MAP
1
0.8
x(n)
0.6
0.4
0.2
0
0
1000
2000
3000
n
4000
5000
6000
(a) Đồ thị biên độ
(b) Đồ thị pha
Hình 2.1: Đồ thị biên độ và pha của hàm Skew Tent
trong thuật toán giải mã. Gọi
được tính như sau:
X1 ,
−1
FK (Y ) =
X2 ,
X1 ,
−1
−1
là hàm ngược của hàm Skew Tent, FK
FK
nếu m(Y ) = Y và XK1 >
nếu m(Y ) = Y và XK1 ≤
nếu m(Y ) = Y + 1
M −X2
M −K
M −X2
M −K
,
(2.4)
trong đó
X1 = M −1 KY ; X2 = (M −1 K − 1)Y + M
m (Y ) = Y + M −1 KY − M −1 KY + 1.
(2.5)
(2.6)
Trong trường hợp tổng quát, để thiết kế S-box u × v bit, có nghĩa là với
u bit đầu vào sẽ tạo ra v bit đầu ra. Do vậy các giá trị đầu vào của S-box
sẽ là các số dương X nằm trong khoảng X = [0, 1, 2, ..., 2u − 1] và đầu ra
nằm trong khoảng (0, 1, 2, ..., 2v − 1), như vậy không gian giá trị đầu ra của
hàm Skew Tent khi thiết kế S-box là Y = [0, 1, 2, ..., M − 1] và M = 2v − 1.
Khi đó, S-box được tạo ra sau khi lặp hàm Skew Tent rời rạc k lần theo
phương trình (2.8).
12
X0
X1
S-box 4x4
hỗn loạn
S-box 4x4
hỗn loạn
Y0
Y1
X15
Lớp S – boxes
C0=IV
…
…
S-box 4x4
hỗn loạn
Y15
Hình 2.2: Lược đồ lớp S-box hỗn loạn móc xích
k
SK (X) = FK
(X + 1) − 1,
(2.7)
hàm chuyển đổi S-box ngược trong thuật toán giải mã có dạng sau
−k
−1
(X + 1) − 1.
(X) = FK
SK
(2.8)
k : Gu → G v .
với FK
2
2
Lớp S-box hỗn loạn móc xích được mô tả Hình 2.2, chế độ móc xích
(Chaining block mode) là mô hình bảo mật chống tấn công lựa chọn bản
rõ [41]. Trong lược đồ lớp S-box hỗn loạn móc xích, định nghĩa khối đầu
vào là 64 bit X = x63 x62 ...xb ...x1 x0 , với xb ∈ {0, 1} là các bit độc lập nhau,
chia thành 16 khối con Xi mỗi khối 4 bit Xi = x4×i+3 ||x4×i+2 ||x4×i+1 ||x4×i
với i = {0, 1, 2...15}. Các khối Xi là đầu vào của lớp S-box 4 × 4-bit nối
móc xích với nhau, các S-box được tạo ra trong Phần 2.1.2 phụ thuộc vào
tham số điều khiển K và số vòng lặp rp.
Đầu vào mỗi S-box thu được khi cộng đảo bit (XOR) khối Xi và đầu ra
của S-box trước đó Yi−1 trong chuỗi móc xích. Tại S-box đầu tiên khối X0
cộng với véc-tơ khởi tạo (Initialization vector-IV) là C0 như phương trình
(2.9- 2.10), do đó sẽ làm tăng độ ảnh hưởng lẫn nhau của các S-box trong
chuỗi.
Y0 = SK (K, [X0 ⊕ IV ]).
(2.9)
Ym = SK (K, [Xm ⊕ Ym−1 ]); m = 1, 3...15,
(2.10)
trong đó, SK là các S-box phụ thuộc tham số K. Khả năng chống tấn công
phân tích thống kê tuyến tính hoặc vi phân phụ thuộc vào số lượng S-box
hoạt động ở đầu ra. Một S-box được gọi là S-box hoạt động nếu và chỉ nếu
S-box đó khác không. Ta có định lý sau
13
x 0 x1 x 2 x 3
x4 x5 x6 x7
S1
S2
x60x61x62x63
………………….
Lớp xáo
trộn
………………….
S16
Lớp trộn byte (MixBytes)
Lớp khuếch
tán
…………………………
Lớp hoán vị bit (PerBits)
……………………………
y60y61y62y63
y 0 y1 y 2 y 3
Hình 2.3: Lớp khuếch tán hỗn loạn
Gọi M số bit của một khối đầu vào, xét Sj : G42 → G42 và Sj+1 : G42 → G42
là hai S-box hoạt động, trong đó Sj là S-box thứ j t h trong chuỗi móc
xích. Gọi Xj , Xj+1 ∈ G42 là hai khối con đầu vào 4 bit. Do đó đầu ra
Yj = Sj (Xj ⊕ Yj−1 ) và Yj+1 = Sj+1 (Xj+1 ⊕ Yj ) có thể viết lại như sau
Yj+1 = Sj+1 (Xj+1 ⊕ Sj (Xj ⊕ Yj−1 )). Có thể thấy rằng, M bit đầu vào
chia thành M
4 khối con Xj mỗi khối 4 bit, các S-box móc xích với nhau
nên mỗi khối con đầu ra được tạo ra sẽ chứa ít nhất 1 S-box hoạt động, và
M
tương ứng với M
4 đầu ra sẽ có ít nhất 4 S-box hoạt động.
2.2. Thiết kế lớp khuếch tán dựa trên hỗn loạn
Lớp khuếch tán hỗn loạn được mô tả như Hình 2.3. Bao gồm hai lớp con
(lớp phụ) là Lớp trộn các byte (MixBytes), lớp thứ hai là lớp hoán vị
phi tuyến (PerBits) theo các bit. Đối với thiết kế mật mã hạng nhẹ hiện
đại [4, 17, 18, 23, 35, 42], độ dài một khối bản rõ là 2m bit, lớp thay
thế có 2m−2 S-box kích thước 4 × 4 − bit, số byte được tính tương ứng
là tByte = 2m−3 . Ví dụ, một khối bản rõ kích thước là 2m = 64 bit, thì
tByte = 2m−3 = 8 byte. Đầu ra của lớp S-box được sắp xếp lại thành các
byte để đưa vào lớp MixBytes. Gọi Si và Si+1 là hai S-box lân cận, và
X = Si Si+1 là byte được ghép bởi hai lân cận nhau, do đó Si là 4 bit trọng
số cao và Si+1 là 4 bit trọng số thấp của X.
Hàm Standard có đặc tính hỗn loạn tốt hơn các hàm hỗn loạn hai chiều
14
khác khi sử dụng các đại lượng đo tính trộn, entropy hoặc phân bố thông kê
Chi-bình phương, ngoài ra quỹ đạo hỗn loạn của hàm Standard cũng được
phân tích chi tiết trong [1] thể hiện rằng hàm Standard hoàn toàn phù hợp
với thiết kế hệ mã mật hỗn loạn, ví dụ trong [26] tác giả đề xuất sử dụng
hàm Standard để thiết kế hệ mật mã khối, hàm Standard cũng được sử
dụng nhiều trong các thuật toán mã hóa ảnh như trong [27, 33, 44]. Trong
phần này, luận án sử dụng hàm Standard cho ứng dụng tạo ra lớp hoán
vị bit (Perbits) cho khối khuếch tán. Hàm Standard rời rạc được biểu diễn
như sau
(
xi+1 = mod
(xi + yi , N )
,
(2.11)
yi+1 = mod yi + K × sin xi+1N×2π , N
với (xi , yi ) ∈ [0, N ]. Giả sử khối đầu vào lớp hoán vị có kích thước 22×m
bit nối tiếp, sắp xếp các bit vào ma trận bit hai chiều kích thước N = 2m .
Gọi bit i có vị trí thứ i trong chuỗi bản rõ ban đầu i ∈ {0, 1, ..., 22×m } và
(xi , yi ) là tọa độ của bit i trong ma trận bit hai chiều, (xi+1 , yi+1 ) là tọa
độ bit i + 1 và i + 1 là vị trí của bit i sau khi được hoán vị thông qua hàm
Standard. Khi đó, i = xi × N + yi và i + 1 = xi+1 × N + yi+1 . Tọa độ
(xi+1 , yi+1 ) được tính như phương trình (2.12)
"
#
"
#
xi+1
x
i
= F rp
,
(2.12)
yi
yi+1
Để đánh giá hiệu quả của lớp khuếch tán đề xuất, luận án dựa trên chiến
thuật vết rộng theo [11, 12, 13] từ đó tìm ra phân phối vết về mặt lý thuyết
trong mỗi véc-tơ đầu vào và đầu ra tương ứng. Xét véc-tơ hSXi là một tập
các trạng thái đầu vào chứa Ms S-box với hSXi = h0, 0, ..., Sm , ..., 0i, và chỉ
có một S-box hoạt động là Sm 6= 0 do đó ||S|| = 1.
Thực hiện lớp khuếch tán qua năm bước lặp, số nhánh của véc-tơ trạng
thái đầu ra hSY i được tính trong Bảng 2.1. Kết quả thu được trong Bảng
2.1 cho thấy số nhánh của lớp khuếch tán đề xuất thu được sau 3 bước lặp
lớn hơn so với các thuật toán mật mã khối hạng nhẹ cấu trúc SPN.
Chiến thuật vết rộng của họ mật mã khối giống AES (AES-like) [12]
tuân theo nguyên tắc sau, các mẫu hoạt động trong một vòng được xác
đinh bởi các S-box khác không trong các trạng thái khác nhau tại đầu vào
15
Bảng 2.1: So sánh số lượng S-box hoạt động
Số vòng
Số nhánh
LED/ PHOTON/ KLEIN
Lớp khuếch tán hỗn loạn.
1
5
3
2
6
6
3
8
13
4
9
16
5
9
16
mỗi vòng. Chúng ta có thể so sánh một cách ngắn ngọn lớp khuếch tán của
LED và lớp khuếch tán đề xuất theo mẫu hoạt động như Hình 2.4. Các
bước SubByte và AddRoundKey sẽ bỏ qua vì cả hai không đóng vai trò
lan truyền mẫu hoạt động. Mẫu hoạt động tại mỗi vòng lặp và véc-tơ hSi
và có ít nhất một S-box hoạt động, các S-box khác không được quy ước là
các ô mầu xám (grey box).
Các mẫu hoạt động
Các mẫu hoạt động
Dịch
hàng
Trộn
Byte
Trộn
cột
(a) Lớp khuếch tán của LED
Hoán
vị bit
(b) Lớp khuếch tán hỗn loạn đề xuất
Hình 2.4: So sánh sự lan truyền của các mẫu hoạt động trong một vòng lặp của
lớp khuếch tán hỗn loạn và của LED/PHOTON/KLEIN/mCrypton
16
Chương 3
MỞ RỘNG HÀM ARNOLD CAT VÀ CÁC ỨNG DỤNG
3.1. Mở rộng hàm Arnol Cat hai chiều dựa trên
biến đổi giả Hadamard nhanh
Hàm Cat được giới thiệu bởi Arnold [34] là hàm kiểu tuyến tính phân đoạn
theo từng chiều. Dạng thức toán học của hàm Cat rời rạc được định nghĩa
như phương trình (3.1), khi đó Cat được coi như là một ánh xạ F : S 2 → S 2 ,
và S = [0, N − 1] là miền số hữu hạn khi N là một số dương. Hàm Cat hai
chiều rời rạc được định nghĩa như sau
#
"
#
!
"
x1 (n)
x1 (n − 1)
= mod A (a, b)2×2 ×
,N ,
(3.1)
x2 (n)
x2 (n − 1)
"
#
1a
khi đó, A (a, b)2×2 =
được gọi là ma trận hai chiều và n
b a×b+1
là số bước lặp hàm và N được gọi là toán hạng của phép chia Modulo với
N > 1.
Biến đổi giả Hadamard nhanh (FPHT) [40] được định nghĩa bởi quan
hệ sau
"
# "
#
2 × Hk−1 Hk−1
21
Hk =
=
⊗ Hk−1 ,
(3.2)
Hk−1
Hk−1
11
trong đó, k ≥ 1, H0 = 1, Hk là ma trận kích thước 2k × 2k và ⊗ được quy
ước là phép nhân Kronecker [19]. Trong trường hợp đặc biệt a = b = 1,
17
hàm Arnold Cat trong phương trình (3.1) được coi là biến đổi FPHT với
H1 = AT (1, 1)2×2 .
Xem xét mở rộng của hàm Cat hai chiều từ phương trình (3.1) thành
ma trận 2k -chiều sử dụng FPHT. Ma trận đầu tiên của biến đổi FPHT
trong phương trình (3.2) được lựa chọn như sau H1 = AT (a, b)2×2 . Do đó
hàm đề xuất được gọi là Cat-Hadamard 2k - chiều được định nghĩa dưới đây
x1 (n)
x1 (n − 1)
x (n)
x (n − 1)
2
2
(3.3)
= mod Hk ×
, N
...
...
x2k (n)
x2k (n − 1)
trong "
đó, Hk được tạo#ra bởi phương trình (3.2), với k ≥ 2, H0 = 1, và
a×b+1 b
. Luôn quy ước m = 2k trong suốt nội dung dưới
H1 =
a
1
đây. Hàm Cat-Hadamard được định nghĩa trong phương trình (3.3) là một
ánh xạ một-một
" hay
# còn gọi là một song ánh.
21
Gọi C =
, và phương trình (3.2) được viết lại theo dạng đệ quy
11
như sau
Hk = (C ⊗ Hk−1 )
= C ⊗ (C ⊗ ...(C ⊗H1 ))
{z
}
|
(3.4)
(k−1) times
= C ⊗(k−1) ⊗ H1 ,
với H1 = AT (a, b)2×2 . Phương trình (3.3) được viết lại theo dạng đệ quy
sau n bước lặp như sau
x1 (n)
x1 (0)
x (n)
x (0)
2
2
= mod Hk × (Hk × (...(Hk ×
)...)), N
{z
} ...
|
...
n times
x2k (n)
= mod Hkn ×
x1 (0)
x2 (0)
...
x2k (0)
18
x2k (0)
,
N
.
(3.5)
- Xem thêm -