Luận văn Ánh xạ nhóm hoán vị và ứng dụng trong mã hóa

8Chương 1: Mở đầu 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à/hoặc 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 tôi 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ố hoặc 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án mã khối phụ thuộc vào kích thước khối n và kích thước khóa k. 1.3. Lý thuyết nhóm 1. Logarithm Signature (LS) 1.3.1.1. Định nghĩa Cho nhóm hoán vị hữu hạn G (cấp n) a gọi là Logarithm Signature (LS) Û a={Bi; i=1, …, s} là một tập có thứ tự với Bi = {B(i,1), …, B(i, ri)} thoả: (i) Chiều dài của logarithm signature bị chặn (ii) B(i,j) Î G ,"1 £ j £ ri ; 1 £ i £ s (iii) "g Î G, g được biểu diễn dưới dạng g = b1b2…bS là duy nhất, trong đó bi Î Bi Ta gọi: Bi là khối (block) (r1, r2, …, rn) là bộ (type) 15 Ví dụ: LS của nhóm A5, gồm 5! phần tử Bộ của LS a là r = (r1, r2, r3) = (5, 4, 3) với các khối B = {B1, B2, B3} Chiều dài của LS a là l = r1 + r2 + r3 = 5 + 4 + 3 = 12 Với g = (3 4 1 2 5) Î A5, ta có : g = b1,2.b2,0.b3,1 = (1 3 5 2 4) . (1)(2)(3)(4)(5) . (1)(2)(3 4 5) 1.3.1.2. Phân loại LS a gọi là nontrivial (không tầm thường) nếu s ³ 2 và ri ³ 2. Ngoài ra gọi a là trivial (tầm thường). a gọi là Tame Û "g, có thể phân tích g với thời gian đa thức O(n) a gọi là SuperTame Û "g, có thể phân tích g với O(n2) a gọi là wild Û a không là tame (1)(2 (1)(2 (1)(2a B1 = B2 = B3 = 16 1.3.1.3. Các phép biến đổi LS Gọi B là một LS, từ một LS phát sinh ra một LS khác dùng các phép biến đổi sau : Phép biến đổi 1 (T1) Là cách hoán đổi vị trí các khối (Shuffle Transformation) trong một LS Cho nhóm G. Gọi a là LS trên G. Ta có: a = [A1, A2, ..., Ai, …, Aj, …, An] LS mới a’ được sinh ra từ a sau khi chuyển đổi 2 vị trí a’ = [A1, A2, ..., Aj, …, Ai, …, An] Phép biến đổi 2 (T2) Còn gọi là trộn khối (Fusion Transformation) trong một LS Cho a = [B1, B2, …, Bi, B(i+1), …, Bs] Vector chiều dài khối r = (r1, …, ri, ri+1, ri+2, …, rw) Chọn ngẫu nhiên 2 khối Bi và Bi+1, với: Bi = { } Bi+1= { } 17 à Khối mới sau khi trộn B’i = Bi Ä Bi+1 = (bim*b(i+1)n : mÎ , n Î ) LS sau khi trộnà a = [B1, B2, …Bi-1, B’i, B(i+2), …, Bs] Vector chiều dài khối r = (r1, …, ri.ri+1, ri+2, …, rw) Phép biến đổi 3 (T3) Ngẫu nhiên thay thế mỗi bij với i = 1, …, w-1, jÎ bằng với lkÎ được chọn ngẫu nhiên Phép biến đổi 4 (T4) Hoán đổi vị trí phần tử trong khối Cho LS a = [A1, A2, ..., Ai, …, An] Chọn ngẫu nhiên 2 vị trí bất kì n, m A[i,j] = { } với i Î {1, 2, …, s}; j Î {1, 2, …, ri} A’[i,j] = { } 18 Phép biến đổi 5 (T5) Thay tất cả các phần tử bij với iÎZw, jÎ , bằng b’ij = g-1*bij*g với g là một phần tử hoán vị được chọn ngẫu nhiên từ G Phép biến đổi 6 (T6) Cho a = [B1, B2, …, Bs] t = (t0, t1, t2, …, ts) Î T = aT = [B1t, ..., Bst] Bit = [t0-1, t0-1, ..., ts-1-1, ts-1-1] Bi [t1-1, t1-1, ..., ts-1, ts-1] · Nếu t0 = ts = 1 : sandwich transformation · Nếu t0 = t1 = ... = ts-1 = 1 : right transformation · Nếu t1 = t2 = ... = ts = 1 : left transformation 1.3.3.4. Cách phát sinh Logarithm Signature Đối với nhóm giải được (solvable group) G = G0 > G1 > G2 > … > GS = {1} 19 Tạo ra 1 LS từ các biểu diễn lớp ghép trái (left coset) / lớp ghép phải (right coset) đầy đủ cho Gi trong Gi-1 Ví dụ G = G0 > G1 > G2 > G3 > G4 > G5 = {1} G0 = G = G1B1 (ghép phải) = (B2G2)B1 (ghép trái) = B2(B3G3)B1 = B2B3(G4B4)B1 = B2B3B5B4B1 a = {B2, B3, B5, B4, B1}: LS à a được tạo ra như trên gọi là một exact mixed transformation LS Nếu tiến trình trên được thức hiện chỉ bằng cách ghép trái (phải) thì ta có exact left (right) transformation LS. Đối với nhóm không giải được G: nhóm đối xứng (symmetric group) Sk (k ³ 5) Giả sử đã dùng cách tạo LS đối với nhóm giải được để tạo LS a với k=5, dùng Sk xây dựng LS cho Gk 20 ak-1 = [B1k-1, …, Bmk-1]: LS cho Sk-1 Sk = , gi Î Sk [B1k-1, …, Bmk-1, B1, …, Br ] = ak : LS Bi: Block mới ta sẽ xây dựng |Bi| = pi với k = p1…pr B1 = {1, (1, k), (2, k), …, (p1-1, k)} 2. Ánh xạ nhóm hoán vị Ánh xạ nhóm hoán vị (Permutation Group Mapping - PGM) được đề xuất bởi S. Magliveras vào cuối những thập niên 1970. PGM dựa trên độ khó phân tích các logarithm signature. Cho các ánh xạ hoán vị sau : 21 Hình 1.4 Ánh xạ nhóm hoán vị V ớ i vector bộ (type) của l o g a r i t h m signature a là r = (r1, r2, ..., rs), ta định nghĩa mi (i = 1..s) với Gọi song ánh l: Zr1 x Zr2 x … x Zrs ® Z|G| với piÎZri Cho 1 nhóm G và 1 logarithm signature a={a[i,j] ; i=1..s, j=0, .., ri-1}, ta gọi song ánh Qa: Zr1 x Zr2 x … x Zrs ® G Qa(p1, ..., ps) = a(p1, ..., ps) = a[s ;ps]. ... . a[2,p2]. a[1,p1] Suy ra, ánh xạ a~ : Z|G|® G a~ (p1, ..., ps) = l-1Qa (p1, ..., ps) Z|G Zr1 x Zr2 x … x G a~ = la-1Qa Qa la- 22 Từ các ánh xạ hoán vị trên ta có thể ánh xạ một giá trị từ một không gian Z|G| sang không gian G theo ánh xạ a~ Ví dụ: Ta có 2 logsig a, b với các khối như sau: a n b (1)(2)(3)(4)(5) (1 2 3 4 5) (1 3 5 2 4) (1 4 2 5 3) (1 5 4 3 2) 0 1 2 3 4 (1 4 2 3 5) (1)(2)(3 5 4) (1 2 5 4 3) (1 3)(2 4)(5) (1 5 3 4 2) (1)(2)(3)(4)(5) (1)(2 3)(4 5) (1)(2 4 3)(5) (1)(2 5 3)(4) 0 5 10 15 (1)(2 3)(4 5) (1)(2 5 3)(4) (1)(2 4 3)(5) (1)(2)(3)(4)(5) (1)(2)(3)(4)(5) (1)(2)(3 4 5) (1)(2)(3 5 4) 0 20 40 (1)(2)(3)(4)(5) (1)(2)(3 5 4) (1)(2)(3 4 5) Ta có r = {5, 4, 3} Tính mi được mi = {1, 5, 20}, suy ra n như trên Với m = 49, phân tích m thành m = 40 + 5 + 4 Dựa theo bảng trên, suy ra p = l-1(49) = (4, 1, 2) 23 Qa (4,1,2) = a [3;2] a[2;1] a[1;4] = (1 5 4)(2)(3) 3. Giới thiệu một số hệ mã trên nhóm 1.3.3.1. PGM Cho 1 cặp LS a, b là các tame LS. Hàm mã hóa : Ea, b: Z|G| ® Z|G| với Ea, b = Pa, b = (a~)(b~)-1 Hàm giải mã là hàm nghịch đảo của hàm mã hóa : Da, b = (Ea, b)-1 = (b~)(a~)-1 1.3.3.2. MST1 Cho nhóm G và cặp khóa gồm 2 LS (α,β) với α là wild và β là tame, sao cho tích thừa số α~β~-1 = θ~1…θ~k (*) được biết trước, với θi là tame và k (nhỏ) ³ 2. G và (α,β) là khóa công khai, còn tích (*) được giữ bí mật (khóa bí mật) Hàm mã hóa : Eα,β = (α~)(β~)-1 Hàm giải mã : Dα,β = Eα,β 1.3.3.3. MST2 Định nghĩa Cover Cho G là một nhóm hữu hạn cấp n 25 Hệ mã công khai MST2 Chọn H và G là 2 nhóm hoán vị. Hệ thống MST2 dùng 2 lưới [r,s] là α và b, không dùng LS. Hệ thống này dựa trên giả thuyết các lưới [r,s] khó phân tích. Gọi α = (αij) là một lưới [r,s] của nhóm hoán vị G. Cho một toàn ánh f: G®H. Hàm f có thể thực hiện bằng một số phương pháp chuyển thể như trong [1][3]. Gọi b = (bij) thì bij = f(aij) là một lưới [r,s] cho H Định nghĩa một toàn ánh: α~: Zrs → G (cách thực hiện giống PGM), vì |G|≠rs nên ánh xạ này không nhất thiết là một song ánh a) Giao thức thực hiện trong hệ thống MST2 Khi B muốn gửi cho A một thông điệp mà chỉ có A đọc được, thì A và B sẽ làm theo các bước sau đây 26 Hìn h 1.5 các bướ c thực hiện hệ thốn g mã hóa khóa công MST2 b) Các vấn đề trong hệ mã MST2 Hệ thống MST2 sử dụng lưới [r,s]. Như vậy để kiểm tra một α có phủ G hay không, ta xét các vấn đề phát sinh và các hướng giải quyết được đề xuất sau: 1. Tính lmax chính xác của g? Cần vét cạn G để tìm các phần tử αij thỏa tích (1). Việc này không khả thi khi G lớn. 2. Xét α có là phủ của G không? Ta xét tất cả các αijÎG và với từng αij, tính lmax, lmin, l(α). Nếu G lớn thì việc tìm này không khả thi - Chọn 2 nhóm H, G lớn - Chọn f: G → H - Chọn 1 [r,s]-mesh a - Tính b = f(a) = (bij) = (f(a ij)) - Công bố (a, b), giữ f bí mậtA: - Chọn 1 số nguyên R Î Zrs - Tính y1=a~(R), y2=b~(R), y3=h.y2 - Gửi y=(y1, y3) cho A B mã hoá thông điệp H và gửi cho A nhận thông điệp đã mã hoá và giải - Tính y2=b~(R) =f(a~(R)) = f(y1) - Tính h = y3.y2-1 27 3. Để tránh trường hợp không thể thực thi khi vét cạn trên một nhóm hữu hạn lớn. Ý tưởng sử dụng thuật giải di truyền và thuật giải tham lam, rút ngắn được thời gian tính toán và cho kết quả chọn lọc tương đối tốt, cách này khả thi. 24 Gọi cover α = [A1, …, As], Ai là tập con có thứ tự và "iÎ[1,s] Ai=[αi1, αi2, …, αiri] Ì G và "gÎG, g được biểu diễn như sau: , α ijÎ Ai (1) Gọi lg là cách biểu diễn g như (1) lmin: số cách tối thiểu biểu diễn g lmin = min{lg: gÎG} lmax: số cách tối đa biểu diễn g lmax = max{lg: gÎG} Độ đồng nhất của α (uniform) là · Phủ α được gọi là đồng nhất nếu l£2 (2) · Phủ α gọi là [s,r]-mesh nếu phủ α đồng nhất và "iÎ[1,s], ri = r (3) Ai gọi là khối Vector (r1,…, rs) gọi là lọai của α gọi là chiều dài của α Chúng ta biểu diễn [r,s]-mesh là một (s x r) ma trận α = (αij) với αijÎG, i=1..s, j=1..r