phuchuy3107
New Member
Download Luận văn Ánh xạ nhóm hoán vị và ứng dụng trong mã hóa
MỤC LỤC
CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT2
DANH SÁCH HÌNH5
DANH SÁCH BẢNG6
Chương 1: Mở đầu7
1.1. Giới thiệu7
1.2. Hệ mã9
1.2.1. Mã đối xứng (Symmetric Cryptography)9
1.2.2. Mã bất đối xứng (Asymmetric Cryptography)10
1.2.3. Hệ mã khối (Block Cipher)11
1.3. Lý thuyết nhóm12
1.3.1. Logarithm Signature (LS)12
1.3.1.1. Định nghĩa12
1.3.1.2. Phân loại LS14
1.3.1.3. Các phép biến đổi LS14
1.3.3.4. Cách phát sinh Logarithm Signature16
1.3.2. Ánh xạ nhóm hoán vị17
1.3.3. Giới thiệu một số hệ mã trên nhóm20
1.3.3.1. PGM20
1.3.3.2. MST120
1.3.3.3. MST220
Chương 2: Thiết kế hệ thống mã hóa24
2.1. Nhóm hoán vị nhị phân (binary permutation group)24
2.2. Xây dựng hệ mã đối xứng trên nhóm 26
2.3. Thiết lập một hệ mã đối xứng27
2.4. Các phép biến đổi sơ cấp31
2.5. Phát sinh khóa33
2.6. Khóa yếu35
2.7. Một ví dụ về hệ thống được đề xuất37
2.7.1. Tính các thông số37
2.7.2. Mã hóa39
2.7.3. Giải mã40
Chương 3: Phân tích và thực nghiệm41
3.1. Phân tích hệ mã đề nghị41
3.1.1. Tính an toàn của hệ mã đề nghị41
3.1.1.1. Các khái niệm41
Định nghĩa 1 (Định nghĩa hệ mã đề nghị)41
Định nghĩa 2 (t-transitive)41
3.1.1.2. Hệ mã đề nghị và hệ mã Hill (Hill Cipher)42
3.1.1.3. Hệ mã đề nghị và hệ mã DES43
3.1.2. Khả năng triển khai trên phần cứng43
3.1.3. Một số kết quả thực nghiệm44
Thời gian phát sinh khóa44
Thời gian mã hóa và giải mã trên file (s)45
Tập tin text dung lượng 500KB45
Tập tin nhị phân dung lượng 1125KB45
Chương 4: Kết luận47
Tài liệu tham khảo49
PHỤ LỤC51
A. Hàm băm Whirlpool51
B. Một số định nghĩa cơ sở trong lý thuyết nhóm56
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
1. Giới thiệu
Với các hệ mã dựa trên cơ sở toán học là lý thuyết số (number theory) như các
hệ mã khóa công khai RSA [16][17], ECC [6][16], … và các hệ mã khóa bí mật như
AES [8][17], DES [9], … với các tấn công ngày càng tinh vi và sự phát triển nhanh
chóng của các kỹ thuật phần cứng hỗ trợ cho thời gian phá mã được rút ngắn đi rất
nhiều. Để chống lại các tấn công này, người ta đã tăng dần kích thước khóa lên, dự
kiến đến năm 2010 khóa của RSA phải đạt 1024 bit trở lên, AES 128 bit trở lên và
ECC là 160 bit trở lên [7]. Sau năm 2010 thì RSA phải từ 2048 bit trở lên, ECC từ 224
bit trở lên thì mới đảm bảo tính an toàn cho hệ thống [7]. Kích thước khóa tăng sẽ làm
cho thời gian phát sinh khóa, thời gian mã hóa và giải mã thông điệp tăng theo. Để
khắc phục tình trạng này, các nhà phân tích mã đã nghiên cứu và tìm một cơ sở toán
học khác cho hệ mã hóa, đó là lý thuyết nhóm (group theory). Các hệ mã dựa trên lý
thuyết nhóm còn khá mới mẻ, chỉ được nghiên cứu trên lý thuyết và chưa được triển
khai vào các ứng dụng thực tế là một lợi thế vì chưa có sự đầu tư tấn công vào các hệ
mã này. Tuy nhiên trong quá trình tìm hiểu đưa ra cơ sở toán học cho hệ mã mới này,
các tác giả cũng chú ý đến các khả năng hệ mã bị tấn công [2].
Trong các dạng mã như: mã mũ, mã tuyến tính, các hệ mã bậc hai… [15] thì
luận văn tập trung vào mã khối là một dạng mã tuyến tính. Đối với các hệ mã khối thì
tính bảo mật sẽ phụ thuộc chiều dài khối và chiều dài khóa. Tuy nhiên, một hệ mã
khối gọi là tốt thì không thể chỉ mang tính bảo mật (security) và hiệu quả (efficiency),
mà còn phải có các tính chất khác như tính tổng quát (generality), khả năng dễ mở rộng
(scalability) chiều dài khóa/chiều dài khối và cơ sở toán học (theoretical foundations)
nữa. Với các hệ mã khối thông dụng và nổi tiếng như AES, DES, … vẫn chưa hỗ trợ
9tính mở rộng đối với chiều dài khối và/hay chiều dài khóa. Luận văn đề xuất một
thuật toán xây dựng hệ mã khối đối xứng dựa trên lý thuyết nhóm đảm bảo được các
yêu cầu trên.
Trong giới hạn của luận văn, chúng tui sẽ trình bày sơ nét về lý thuyết nhóm,
thuật toán đề xuất, cũng như phân tích, chứng minh lý thuyết, các thuật toán và nêu kết
quả thực nghiệm cài đặt hệ mã đề xuất. Bố cục luận văn gồm 4 chương và 2 phụ lục:
Chương 1: Mở đầu - giới thiệu sự ra đời của hệ mã hóa đề xuất, cơ sở toán học
cho hệ mã hóa đề xuất, giới thiệu hiện trạng các hệ mã dựa trên lý thuyết nhóm trên thế
giới.
Chương 2: Thiết kế hệ thống mã hóa – trình bày mô hình và thuật toán của hệ
mã đề xuất.
Chương 3: Phân tích và thực nghiệm – Phân tích hệ mã hóa đề xuất, chứng
minh tính an toàn, tính mở rộng kích thước khóa/khối và khả năng triển khai trên phần
cứng cũng như khả năng cài đặt. So sánh với hệ mã Hill và DES.
Chương 4: Kết luận – Tóm tắt lại những gì luận văn đã thực hiện và những
công việc tiếp tục được nghiên cứu trong tương lai
Phụ lục
A. Giới thiệu hàm băm Whirlpool
B. Một số định nghĩa cơ sở trong lý thuyết nhóm
Từ khóa: group theory, cryptography, symmetric group, permutation group,
block cipher, symmetric block cipher, logarithm signature, PGM, Permutation Group
Mapping, scalability, …
2.
10
Hệ mã
Một hệ mật mã V là tập gồm (M, K, C, T) với M, K, C là các tập hữu hạn:
M: tập bản rõ
K: tập khóa
C: tập bản mã
T: tập các ánh xạ biến đổi M thành C, T = {Ek}kÎK, với kÎK, Ek có tính
khả nghịch. Gọi Dk là ánh xạ ngược của Ek. Gọi m là thông điệp cần mã hóa, c là bản
mã của m, ta có:
Mã hóa: c = Ek(m) với kÎK
Giải mã: m = Dk(c) với kÎK
1. Mã đối xứng (Symmetric Cryptography)
Quá trình mã hóa và giải mã của hệ mã đối xứng [15][16] dùng chung một khóa
bí mật (secret key) duy nhất. Khóa này được cả 2 bên nhận và truyền đã trao đổi trước
và chỉ có 2 bên nhận và gửi biết khóa này. Khóa bí mật thường được trao đổi qua kênh
truyền an toàn và được mã hóa bằng các thuật toán mã công khai.
Mã hóa E: M x Kà C
Giải mã D: C x Kà M
Mã đối xứng gồm 2 dạng mã:
· Mã khối (block cipher): mã hóa và giải mã từng khối nhiều kí tự
· Mã chuỗi (stream cipher): mã hóa và giải mã lần lượt từng kí tự
11
Các hệ mã đối xứng như: Caesar, Affine, Vingenere, AES, DES, 3DES, IDEA,
RC5, Blowfish, Twofish, CAST-128, …
Hình 1.1 – Mã đối xứng
2. Mã bất đối xứng (Asymmetric Cryptography)
Hệ mã bất đối xứng [15][16] dùng cặp khóa: khóa công khai (public key) và
khóa bí mật (private key). Khóa công khai được bên nhận công bố rộng rãi và bên gửi
dùng để mã hóa, còn khóa bí mật thì chỉ có bên nhận biết dùng để giải mã. Mỗi cặp
khóa của hệ mã công khai là duy nhất.
Mã hóa E: M x Kpubà C
Giải mã D: C x Kprivà M
Mã đối xứng thực thi nhanh hơn mã bất đối xứng, nên trong các ứng dụng thực
tế người ta thường dùng mã bất đối xứng để truyền khóa do kích thước khóa không
quá lớn. Còn mã đối xứng thường được dùng để mã hóa dữ liệu và truyền đi.
Các hệ mã bất đối xứng như: Rabin, mã xác suất Blum-Goldwasser, RSA, ECC,
mã xích khối (CBC), mã hồi tác (CFB)…
12
Hình 1.2 Mã bất đối xứng
3. Hệ mã khối (Block Cipher)
Mã khối [4][15] là một dạng mã đối xứng (symmetric- key encryption). Các
thuật toán mã khối thực hiện mã hóa và giải mã trên một nhóm các bits gọi là khối
(block). Chúng mã hóa các khối dữ liệu gọi là khối dữ liệu bản rõ
(plaintext/unencrypted text) thành các khối dữ liệu bản mã (cipher text/encrypted text)
có kích thước bằng nhau được qui định trước. Mã khối thao tác trên dữ liệu hoàn toàn
khác với mã chuỗi (stream cipher). Mã khối thao tác lần lượt trên từng khối dữ liệu tại
từng thời điểm, còn mã chuỗi thao tác trên từng kí tự, điều này khiến cho mã chuỗi dễ
bị tấn công theo cách thống kê tần số hay tấn công bản mã.
Gọi hàm mã hóa là E và hàm giải mã là D trong hệ mã khối, ta có:
13
E: P ´ Kà C
Hàm giải mã là hàm ngược của E, ta
có: D = E-1
D: C ´ Kà P
Mã hóa và giải mã dùng cùng một
khóa gọi là khóa bí mật.
Tính chất của một thuật toán mã khối tốt trước các t ấ n
công [17]
1. Tính khuyếch tán (diffusion) (theo Shannon): một thay đổi nhỏ trong bản rõ
sẽ tạo ra thay đổi trong bản mã.
M1 ¹ M2 Û E(M1) ¹ E(M2)
Tính chất này ngăn cản tấn công phân tích sai phân.
2. Tính hỗn loạn (confusion) (theo Shannon): phá vỡ mối quan hệ giữa bản rõ
và bản mã, làm cho tấn công tìm khóa (exclusive key) khó thực hiện được
(tấn công này là một phương pháp tìm khóa trong tất cả các khóa tiềm năng)
3. Tính trọn vẹn (complete): Mỗi bit của bản mã phụ thuộc vào bit của khóa,
ngăn cản tấn công chia để trị (chia bản mã thành từng phần nhỏ, và tấn công
trên từng phần nhỏ này)
Một số thuật toán mã khối : AES, DES, 3DES, ...
Trong mã khối với kích thước khóa cố định, người ta còn gọi là kích thước khối
(block size) và gọi mã khối đó là mã khối thay thế (subsitution block cipher). Dạng mã
khối này dễ bị tấn công vì dễ phục hồi bản rõ từ bản mã theo cách thống kê tần số.
Khối bản mã
Khối bản rõ
Khó
Khối bản rõ
Thuật toán
Thuật toán
Hình 1.3 Mã khối
14
Độ bảo mật của các thuật to...
Download miễn phí Luận văn Ánh xạ nhóm hoán vị và ứng dụng trong mã hóa
MỤC LỤC
CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT2
DANH SÁCH HÌNH5
DANH SÁCH BẢNG6
Chương 1: Mở đầu7
1.1. Giới thiệu7
1.2. Hệ mã9
1.2.1. Mã đối xứng (Symmetric Cryptography)9
1.2.2. Mã bất đối xứng (Asymmetric Cryptography)10
1.2.3. Hệ mã khối (Block Cipher)11
1.3. Lý thuyết nhóm12
1.3.1. Logarithm Signature (LS)12
1.3.1.1. Định nghĩa12
1.3.1.2. Phân loại LS14
1.3.1.3. Các phép biến đổi LS14
1.3.3.4. Cách phát sinh Logarithm Signature16
1.3.2. Ánh xạ nhóm hoán vị17
1.3.3. Giới thiệu một số hệ mã trên nhóm20
1.3.3.1. PGM20
1.3.3.2. MST120
1.3.3.3. MST220
Chương 2: Thiết kế hệ thống mã hóa24
2.1. Nhóm hoán vị nhị phân (binary permutation group)24
2.2. Xây dựng hệ mã đối xứng trên nhóm 26
2.3. Thiết lập một hệ mã đối xứng27
2.4. Các phép biến đổi sơ cấp31
2.5. Phát sinh khóa33
2.6. Khóa yếu35
2.7. Một ví dụ về hệ thống được đề xuất37
2.7.1. Tính các thông số37
2.7.2. Mã hóa39
2.7.3. Giải mã40
Chương 3: Phân tích và thực nghiệm41
3.1. Phân tích hệ mã đề nghị41
3.1.1. Tính an toàn của hệ mã đề nghị41
3.1.1.1. Các khái niệm41
Định nghĩa 1 (Định nghĩa hệ mã đề nghị)41
Định nghĩa 2 (t-transitive)41
3.1.1.2. Hệ mã đề nghị và hệ mã Hill (Hill Cipher)42
3.1.1.3. Hệ mã đề nghị và hệ mã DES43
3.1.2. Khả năng triển khai trên phần cứng43
3.1.3. Một số kết quả thực nghiệm44
Thời gian phát sinh khóa44
Thời gian mã hóa và giải mã trên file (s)45
Tập tin text dung lượng 500KB45
Tập tin nhị phân dung lượng 1125KB45
Chương 4: Kết luận47
Tài liệu tham khảo49
PHỤ LỤC51
A. Hàm băm Whirlpool51
B. Một số định nghĩa cơ sở trong lý thuyết nhóm56
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
8Chương 1: Mở đầu1. Giới thiệu
Với các hệ mã dựa trên cơ sở toán học là lý thuyết số (number theory) như các
hệ mã khóa công khai RSA [16][17], ECC [6][16], … và các hệ mã khóa bí mật như
AES [8][17], DES [9], … với các tấn công ngày càng tinh vi và sự phát triển nhanh
chóng của các kỹ thuật phần cứng hỗ trợ cho thời gian phá mã được rút ngắn đi rất
nhiều. Để chống lại các tấn công này, người ta đã tăng dần kích thước khóa lên, dự
kiến đến năm 2010 khóa của RSA phải đạt 1024 bit trở lên, AES 128 bit trở lên và
ECC là 160 bit trở lên [7]. Sau năm 2010 thì RSA phải từ 2048 bit trở lên, ECC từ 224
bit trở lên thì mới đảm bảo tính an toàn cho hệ thống [7]. Kích thước khóa tăng sẽ làm
cho thời gian phát sinh khóa, thời gian mã hóa và giải mã thông điệp tăng theo. Để
khắc phục tình trạng này, các nhà phân tích mã đã nghiên cứu và tìm một cơ sở toán
học khác cho hệ mã hóa, đó là lý thuyết nhóm (group theory). Các hệ mã dựa trên lý
thuyết nhóm còn khá mới mẻ, chỉ được nghiên cứu trên lý thuyết và chưa được triển
khai vào các ứng dụng thực tế là một lợi thế vì chưa có sự đầu tư tấn công vào các hệ
mã này. Tuy nhiên trong quá trình tìm hiểu đưa ra cơ sở toán học cho hệ mã mới này,
các tác giả cũng chú ý đến các khả năng hệ mã bị tấn công [2].
Trong các dạng mã như: mã mũ, mã tuyến tính, các hệ mã bậc hai… [15] thì
luận văn tập trung vào mã khối là một dạng mã tuyến tính. Đối với các hệ mã khối thì
tính bảo mật sẽ phụ thuộc chiều dài khối và chiều dài khóa. Tuy nhiên, một hệ mã
khối gọi là tốt thì không thể chỉ mang tính bảo mật (security) và hiệu quả (efficiency),
mà còn phải có các tính chất khác như tính tổng quát (generality), khả năng dễ mở rộng
(scalability) chiều dài khóa/chiều dài khối và cơ sở toán học (theoretical foundations)
nữa. Với các hệ mã khối thông dụng và nổi tiếng như AES, DES, … vẫn chưa hỗ trợ
9tính mở rộng đối với chiều dài khối và/hay chiều dài khóa. Luận văn đề xuất một
thuật toán xây dựng hệ mã khối đối xứng dựa trên lý thuyết nhóm đảm bảo được các
yêu cầu trên.
Trong giới hạn của luận văn, chúng tui sẽ trình bày sơ nét về lý thuyết nhóm,
thuật toán đề xuất, cũng như phân tích, chứng minh lý thuyết, các thuật toán và nêu kết
quả thực nghiệm cài đặt hệ mã đề xuất. Bố cục luận văn gồm 4 chương và 2 phụ lục:
Chương 1: Mở đầu - giới thiệu sự ra đời của hệ mã hóa đề xuất, cơ sở toán học
cho hệ mã hóa đề xuất, giới thiệu hiện trạng các hệ mã dựa trên lý thuyết nhóm trên thế
giới.
Chương 2: Thiết kế hệ thống mã hóa – trình bày mô hình và thuật toán của hệ
mã đề xuất.
Chương 3: Phân tích và thực nghiệm – Phân tích hệ mã hóa đề xuất, chứng
minh tính an toàn, tính mở rộng kích thước khóa/khối và khả năng triển khai trên phần
cứng cũng như khả năng cài đặt. So sánh với hệ mã Hill và DES.
Chương 4: Kết luận – Tóm tắt lại những gì luận văn đã thực hiện và những
công việc tiếp tục được nghiên cứu trong tương lai
Phụ lục
A. Giới thiệu hàm băm Whirlpool
B. Một số định nghĩa cơ sở trong lý thuyết nhóm
Từ khóa: group theory, cryptography, symmetric group, permutation group,
block cipher, symmetric block cipher, logarithm signature, PGM, Permutation Group
Mapping, scalability, …
2.
10
Hệ mã
Một hệ mật mã V là tập gồm (M, K, C, T) với M, K, C là các tập hữu hạn:
M: tập bản rõ
K: tập khóa
C: tập bản mã
T: tập các ánh xạ biến đổi M thành C, T = {Ek}kÎK, với kÎK, Ek có tính
khả nghịch. Gọi Dk là ánh xạ ngược của Ek. Gọi m là thông điệp cần mã hóa, c là bản
mã của m, ta có:
Mã hóa: c = Ek(m) với kÎK
Giải mã: m = Dk(c) với kÎK
1. Mã đối xứng (Symmetric Cryptography)
Quá trình mã hóa và giải mã của hệ mã đối xứng [15][16] dùng chung một khóa
bí mật (secret key) duy nhất. Khóa này được cả 2 bên nhận và truyền đã trao đổi trước
và chỉ có 2 bên nhận và gửi biết khóa này. Khóa bí mật thường được trao đổi qua kênh
truyền an toàn và được mã hóa bằng các thuật toán mã công khai.
Mã hóa E: M x Kà C
Giải mã D: C x Kà M
Mã đối xứng gồm 2 dạng mã:
· Mã khối (block cipher): mã hóa và giải mã từng khối nhiều kí tự
· Mã chuỗi (stream cipher): mã hóa và giải mã lần lượt từng kí tự
11
Các hệ mã đối xứng như: Caesar, Affine, Vingenere, AES, DES, 3DES, IDEA,
RC5, Blowfish, Twofish, CAST-128, …
Hình 1.1 – Mã đối xứng
2. Mã bất đối xứng (Asymmetric Cryptography)
Hệ mã bất đối xứng [15][16] dùng cặp khóa: khóa công khai (public key) và
khóa bí mật (private key). Khóa công khai được bên nhận công bố rộng rãi và bên gửi
dùng để mã hóa, còn khóa bí mật thì chỉ có bên nhận biết dùng để giải mã. Mỗi cặp
khóa của hệ mã công khai là duy nhất.
Mã hóa E: M x Kpubà C
Giải mã D: C x Kprivà M
Mã đối xứng thực thi nhanh hơn mã bất đối xứng, nên trong các ứng dụng thực
tế người ta thường dùng mã bất đối xứng để truyền khóa do kích thước khóa không
quá lớn. Còn mã đối xứng thường được dùng để mã hóa dữ liệu và truyền đi.
Các hệ mã bất đối xứng như: Rabin, mã xác suất Blum-Goldwasser, RSA, ECC,
mã xích khối (CBC), mã hồi tác (CFB)…
12
Hình 1.2 Mã bất đối xứng
3. Hệ mã khối (Block Cipher)
Mã khối [4][15] là một dạng mã đối xứng (symmetric- key encryption). Các
thuật toán mã khối thực hiện mã hóa và giải mã trên một nhóm các bits gọi là khối
(block). Chúng mã hóa các khối dữ liệu gọi là khối dữ liệu bản rõ
(plaintext/unencrypted text) thành các khối dữ liệu bản mã (cipher text/encrypted text)
có kích thước bằng nhau được qui định trước. Mã khối thao tác trên dữ liệu hoàn toàn
khác với mã chuỗi (stream cipher). Mã khối thao tác lần lượt trên từng khối dữ liệu tại
từng thời điểm, còn mã chuỗi thao tác trên từng kí tự, điều này khiến cho mã chuỗi dễ
bị tấn công theo cách thống kê tần số hay tấn công bản mã.
Gọi hàm mã hóa là E và hàm giải mã là D trong hệ mã khối, ta có:
13
E: P ´ Kà C
Hàm giải mã là hàm ngược của E, ta
có: D = E-1
D: C ´ Kà P
Mã hóa và giải mã dùng cùng một
khóa gọi là khóa bí mật.
Tính chất của một thuật toán mã khối tốt trước các t ấ n
công [17]
1. Tính khuyếch tán (diffusion) (theo Shannon): một thay đổi nhỏ trong bản rõ
sẽ tạo ra thay đổi trong bản mã.
M1 ¹ M2 Û E(M1) ¹ E(M2)
Tính chất này ngăn cản tấn công phân tích sai phân.
2. Tính hỗn loạn (confusion) (theo Shannon): phá vỡ mối quan hệ giữa bản rõ
và bản mã, làm cho tấn công tìm khóa (exclusive key) khó thực hiện được
(tấn công này là một phương pháp tìm khóa trong tất cả các khóa tiềm năng)
3. Tính trọn vẹn (complete): Mỗi bit của bản mã phụ thuộc vào bit của khóa,
ngăn cản tấn công chia để trị (chia bản mã thành từng phần nhỏ, và tấn công
trên từng phần nhỏ này)
Một số thuật toán mã khối : AES, DES, 3DES, ...
Trong mã khối với kích thước khóa cố định, người ta còn gọi là kích thước khối
(block size) và gọi mã khối đó là mã khối thay thế (subsitution block cipher). Dạng mã
khối này dễ bị tấn công vì dễ phục hồi bản rõ từ bản mã theo cách thống kê tần số.
Khối bản mã
Khối bản rõ
Khó
Khối bản rõ
Thuật toán
Thuật toán
Hình 1.3 Mã khối
14
Độ bảo mật của các thuật to...
Tags: hệ mã hóa hoán vị