Luận văn Các thuật toán tối ưu hóa trong bảo mật thông tin

, N=p*q với p và q là các số nguyên tố phân biệt, số nguyên e sao cho thỏa mãn gcd(e, (p – 1) * (q – 1)) = 1, và số nguyên c. Tìm một số nguyên m sao cho me  c (mod N). Bài toán RSA cũng có độ khó tƣơng tự nhƣ bài toán phân tích số nguyên, nhƣng nó dễ dàng đƣợc giải nếu nhƣ biết đƣợc hai số nguyên tố p và q. 2.2.2 Định nghĩa các tập làm việc của hệ RSA  Tập các bản rõ (plaintext): P = ZN = {0, 1,…, N-1}.  Tập các bản mã (ciphertext): C = ZN = {0, 1,…, N-1}.  Tập các khóa: K = {(n, p, q, e, d): N = p * q, e * d 1(mod φ(N))} 2.2.3 Quá trình tạo khoá, mã hoá và giải mã a) Tạo khóa:  Tạo hai số nguyên tố phân biệt p và q lớn, sao cho bài toán phân tích thật sự là khó giải (kích cỡ mỗi số khoảng 512 bits  1024 bits).  Tính N = p* q và φ(N) = (p – 1) * (q – 1).  Chọn một số nguyên ngẫu nhiên e sao cho 1 < e < φ(N) và gcd(e, φ(N)) = 1  Sử dụng thuật toán Euclid mở rộng, để tính số nguyên d duy nhất, sao cho 0 < d < φ(N) và e * d  1 mod φ(N) (d là nghịch đảo của e modulo N)  Hai số (e, N) làm khóa công khai, còn (d, N) đƣợc giữ bí mật làm khóa riêng. Các số nguyên tố p, q sẽ bị xóa khi kết thúc quá trình tạo khóa. b) Mã hóa: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 Giả sử để gửi thông điệp M cho ngƣời B. Ngƣời A thực hiện nhƣ sau:  Lấy khóa công khai của ngƣời nhận B: (e, N).  Biến đổi thông điệp M thành những số nguyên Mi tƣơng ứng sao cho Mi < N, (i = 1,…, k). Theo phép biến đổi sau: - Biến đổi các ký tự trong thông điệp M thành các số nguyên tƣơng ứng, thí dụ theo qui tắc: Dấu cách  00, A  01, B  02,..., Z  26. - Chia thông điệp vừa biến đổi thành k nhóm có chiều dài bằng nhau, mỗi nhóm biểu diễn một số nguyên Mi  {0,…, N – 1} (với 1 ≤ i ≤ k).  Thực hiện mã hóa lần lƣợt cho từng số Mi  Ci bằng cách: Ci = Eke(Mi) = Mi e (mod N). Tập các số nguyên {C1, C2,...,Ck} là bản mã để gửi đến ngƣời nhận B. c) Giải mã: Ngƣời nhận B thực hiện các bƣớc sau:  Thực hiện giải mã lần lƣợt từng số nguyên Ci  Mi bằng cách: Mi = D(Ci) = Ci d (mod N) với 0 ≤ Mi < N, (d là khoá bí mật của B).  Thực hiện phép biến đổi ngƣợc lại từ các số Mi thành các chuỗi ký tự tƣơng ứng để khôi phục lại nội dung thông điệp M ban đầu. Bảng 2.2: Tóm tắt các bước tạo khoá, mã hoá, giải mã của Hệ RSA Tạo khoá: Tạo 2 số nguyên tố lớn p và q * Tính N = p * q và Tính φ(N) = (p-1) * (q-1). * Chọn 1< e < φ(N): gcd(φ(N), e) = 1. * Tính d = e-1 mod φ(N) (dùng thuật toán Euclid mở rộng). Khóa công khai: (e, N) Khóa riêng: (d, N) Mã hóa: Khối bản rõ M < N * Tính: C = Me mod N * Gửi khối bản mã (số nguyên) C đến ngƣời nhận Giải mã: Khối bản mã C < N * Tính: M = Cd mod N * Khôi phục lại khối bản rõ (số nguyên) M ban đầu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 2.3.4 Tính đúng của quá trình giải mã Từ: ed 1mod φ(N) φ(N) | (ed – 1).  φ(pq)| (ed – 1)  φ(p) * φ(q) | (ed – 1) (do p, q là các số nguyên tố)  φ(p) | (ed – 1) (1) và φ(q) | (ed – 1) (2) Từ (1)   k  Z: ed -1= k φ(p) = k (p-1) (p là số nguyên tố) (3) Xét trƣờng hợp tổng quát với mọi số M  Zn , khi nâng lũy thừa ed ta có: M ed  M(ed –1) + 1 (mod p) ed (M(ed-1)) * M (mod p) (4) Từ (3) & (4) ed (Mk(p - 1)) * M (mod p) (5) Vì p là số nguyên tố, vậy bất kỳ số M  ZN có hai trƣờng hợp: M nguyên tố cùng nhau với p (nghĩa là gcd(M, p) = 1) hoặc M là bội số của p (nghĩa là gcd(M, p) = p).  Trường hợp 1: gcd (M, p) = 1 Vậy  M p-1  1 (mod p) (định lý Fermat) Từ: (5)  Med  (1)k M (mod p)  Med  M (mod p) (6)  Trường hợp 2: Nếu gcd(M, p) = p  M  0 (mod p). Đồng thời lũy thừa số M lên một số nguyên bất kỳ, thì cũng chia hết cho p. Nghĩa là Med  0 (mod p ). Vậy trƣờng hợp 2 cũng thỏa mãn phƣơng trình (6) Với cách tính tƣơng tự với q, từ (2)  Med  M (mod q) (7) Từ (6) & (7)  Med  M (mod pq) M (mod N). Ví dụ 2.1 : Minh họa của hệ mật mã RSA a) Tạo khóa: Chọn p và q là những số nguyên tố nhỏ với mục đích minh họa  Chọn hai số nguyên tố p = 41, q = 67;  Tính N = 47 * 61 = 2747 và φ(N) = (41- 1) * (67-1) = 2600 ;  Chọn e = 59 thỏa mãn gcd(e, φ(N)) = gcd(2600, 59) = 1; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33  Tìm phần tử nghịch đảo d = 179 (dùng thuật toán Euclid mở rộng) ;  Công bố khóa công khai là cặp số ( e = 49, N = 2747), còn số d = 179 đƣợc giữ làm khóa riêng. b) Mã hóa: Giả sử nội dung cần mã hoá là M = “MA HOA CONG KHAI ”  Biến đổi các ký tự của thông điệp thành các số tƣơng ứng nhƣ sau: M A  H O A  C O N G  K H A I 13 01 00 08 15 01 00 03 15 14 07 00 11 08 01 09  Chia thông điệp thành 8 khối, mỗi khối gồm 4 chữ số biểu diễn một số nguyên Mi < N, với Mi  {1301;0008;1501;0003;1514;0700;1108;0109}.  Mã hóa lần lƣợt từng số Mi : Ci = Mi 59 ( mod 2747) (8) Mã hóa số đầu tiên M1 = 1301 theo cách tính (8) ta có: C1 = M1 59 mod 2747  130159 mod 2747 = 2352. Tiếp tục tính các số C2 ,...,C8 từ các số M2 ,..., M8 theo (8). Ta có đƣợc kết quả ở cột Ci là bản mã để gửi đến ngƣời nhận: Khối 1 2 3 4 5 6 7 8 Mi 1301 0008 1501 0003 1514 0700 1108 0109 Ci=E(Mi) 2352 2537 1745 2733 1203 2651 0534 0454 c) Giải mã:  Thực hiện giải mã lần lƣợt từng số ở cột Ci (1≤ i ≤ 8) Mi = Dkd(Ci)  Ci 179 ( mod 2747) (9) Giải mã số đầu tiên C1 = 2352 theo cách tính (2.9) ta có: M1 = C1 179 mod 2747 = 2352 179 mod 2747 = 1301 Tiếp tục tính các số M2,..., M8 từ các số C2,...,C8 theo (9) ta có bảng minh họa các số Mi đƣợc giải mã từ các số Ci nhƣ sau: Khối 1 2 3 4 5 6 7 8 Ci=E(Mi) 2352 2537 1745 2733 1203 2651 0534 0454 Mi 1301 0008 1501 0003 1514 0700 1108 0109 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34  Thực hiện phép biến đổi ngƣợc từ các số Mi thành các chuỗi ký tự tƣơng ứng để khôi phục lại thông điệp gốc ban đầu M = "MA HOA CONG KHAI". 2.2.4 Chi phí thực hiện trong quá trình mã hóa và giải mã  Chi phí cho quá trình mã hoá: Tính C = Me mod N, với số mũ e thƣờng đƣợc chọn có dạng e = 2x + 1 (với xmax = 16) để phép tính lũy thừa modulo đƣợc thực hiện nhanh. Vì biểu diễn nhị phân của những số dạng này chỉ có hai bít giá trị 1 ở đầu và cuối. Nhƣ vậy quá trình mã hóa có nhiều nhất là 16 phép tính bình phƣơng và 1 phép nhân, do đó tổng chi phí của quá trình mã hóa là: 17(2n2 + 2n) = 34(n2+n).  Chi phí cho quá trình giải mã: Quá trình giải mã của hệ RSA, chỉ thực hiện phép tính M = Cd mod N, với số mũ bí mật d thƣờng rất lớn (d  N) để đảm bảo độ an toàn cho dữ liệu. Vì vậy chi phí thực hiện giải mã của hệ RSA tƣơng đƣơng với chi phí để thực hiện phép tính lũy thừa nhanh là: 3n3 + n2. 2.2.5 Đánh giá hệ mật mã khóa công khai RSA 2.2.5.1 Độ an toàn Hệ RSA đƣợc thiết kế dựa trên độ khó giải bài toán phân tích ra thừa số nguyên tố. Hầu hết các phƣơng pháp thám mã hệ RSA nhƣ tìm các thừa số p và q, tìm φ(n), hay tìm khóa riêng d… đều khó nhƣ bài toán phân tích. Sau đây, ta có bảng chi phí thời gian cần thiết để phân tích những hệ mật mã RSA có kích cỡ số modulo N khác nhau, bằng những thuật toán phân tích tốt nhất hiện nay (Bảng 2.3). Ở đây chi phí tính toán đƣợc tính bằng đơn vị MIPS-Years (đó là số các phép tính đã hoàn thành bởi một máy trong thời gian một năm, với tốc độ khoảng 106 phép tính trên một giây, ta có 1MIPS-Years  245 phép tính). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Bảng 2.3: Bảng chi phí thời gian cần thiết để phân tích các số nguyên N Hệ RSA Số chữ số thập phân Số bits Thuật toán Năm Chi phí phân tích (MIPS-Years) RSA-129 129 426 MPQS 1994 5.000 RSA-130 130 430 GNFS 1996 1.000 RSA-140 140 465 GNFS 1999 2.000 RSA-155 155 512 GNFS 1999 8.000 RSA-576 174 576 GNFS 2003 13.000 Vào ngày 22/8/1999 một nhóm các nhà nghiên cứu đã hoàn thành việc phân tích số N dùng trong hệ RSA-155 có 155 chữ số thập phân (512-bits) bằng thuật toán General Number Field Sieve (GNFS). Sau một thời gian 7 tháng trên mạng máy tính có 300 workstation yêu cầu khoảng 8000 MIPS-Years. Việc phân tích số nguyên N thành các thừa số nguyên tố p, q nhằm mục đích bẻ gãy hệ mật mã RSA là điều khó có thể tính toán nổi, nếu nhƣ trong quá trình thiết kế hệ RSA ta chọn số nguyên N lớn. Tuy nhiên, độ dài của số nguyên N là lớn hay nhỏ còn phụ thuộc vào mối liên hệ giữa tốc độ giải mã và độ an toàn của hệ RSA. Số N sử dụng cho modulo RSA hiện nay phải có ít nhất khoảng 232 chữ số thập phân (768-bits) sẽ cho ta một độ an toàn đủ để chống lại những tấn công sử dụng các kỹ thuật phân tích hiện nay. Trong thực tế, nếu trong quá trình thiết kế sử dụng số N có kích cỡ khoảng 1024-bits là rất an toàn, có thể chống lại các kỹ thuật phân tích hiện tại và các kỹ thuật khác phát triển trong tƣơng lai. 2.2.5.2 Hiệu suất thực hiện và ứng dụng Tốc độ thực hiện của hệ RSA là một trong những điểm yếu so với các hệ mật mã khóa đối xứng. Vì các quá trình mã hóa và giải mã của hệ RSA đều thực hiện các phép tính có các toán hạng là những số nguyên cực lớn ( thông thƣờng các phép toán này đều đƣợc xây dựng hay ”giả lập” lại). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 Theo ƣớc tính, thực hiện mã hóa và giải mã bằng hệ mật mã RSA chậm hơn 100 lần so với hệ mật mã khóa đối xứng DES (bằng phần mềm). Và chậm hơn 1000 lần so với DES (bằng phần cứng). Vì lý do đó mà trên thực tế hệ mã khoá công khai RSA ít đƣợc dùng vào mục đích mã hóa cho khối lƣợng dữ liệu lớn, mà chỉ thƣờng đƣợc ứng dụng để mã hóa khối dữ liệu nhỏ. Nhƣ vậy để khắc phục một phần nào đó cho công việc mã hóa và giải mã bằng hệ mật mã RSA đƣợc nhanh hơn thì chúng ta nghiên cứu thêm hệ mật mã RSA WITH CRT nhƣ sau : 2.3 HỆ MẬT MÃ RSA WITH CRT Ta thấy rằng, quá trình giải mã của hệ mật mã RSA có độ phức tạp (M = Cd mod N) phụ thuộc trực tiếp vào kích cỡ của các số nguyên d và N. Để có thể giảm đƣợc kích cỡ của hai số nguyên d và N và tăng tốc độ giải mã, chúng ta dựa vào định lý đồng dƣ Trung hoa (CRT-Chinese Remainder Theorem) sau: 2.3.1 Định lý đồng dƣ Trung Hoa Định lý đồng dƣ Trung Hoa (CRT) cho phép giảm số lần tính toán của quá trình giải mã ở hệ RSA, bằng cách thiết lập một ánh xạ giữa tập Z N và tích Đề-các   k 1i niZ , với N =   k 1i in và các số ni (1 i  k) nguyên tố cùng nhau. Cho phép thực hiện các phép tính lũy thừa modulo trên các trƣờng số Zni nhỏ hơn, thay vì phải tính trực tiếp trên trƣờng số Z N lớn nhƣ cách tính trong hệ RSA chuẩn. Định lý 2.2:(định lý đồng dƣ Trung Hoa) Giả sử p1, p2,...., pk là các số nguyên dƣơng nguyên tố cùng nhau từng đôi một (gcd(pi, pj) = 1, khi i  j) và cho x1, x2,..., xk là các số nguyên. Khi đó hệ phƣơng trình đồng dƣ sau đây: x  x1 (mod p1) x  x2 (mod p2) x  xk (mod pk) có duy nhất một nghiệm x  ZN, N = p1.p2....pk đƣợc xác định nhƣ sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 x =    k 1i iii Nscx mod (10) Trong đó: i i p N c  và )p (mod i 1 ii cs  , i = 1, 2,…, k Vậy, theo định lý đồng dƣ Trung Hoa, với bất kỳ số nguyên dƣơng x < N đều có thể biểu diễn dƣới dạng một bộ gồm k phần tử duy nhất [x1, x2,…, xk] và ngƣợc lại, ở đây các xi là số dƣ của phép tính x mod pi (i = 1, 2…, k). Sự chuyển đổi số nguyên x thành các số dƣ đƣợc thực hiện bởi phép rút gọn xi = x mod pi. Còn sự chuyển ngƣợc lại khó hơn, đòi hỏi tính toán liên quan đến công thức (10). Hệ quả 2.1: Nếu số nguyên x không chia hết cho p, và n  m mod (p – 1) thì xn  x m mod p. Từ hệ quả trên, khi thực hiện phép toán lũy thừa với modulo là một số nguyên tố p thì số mũ có thể đƣợc rút gọn mod (p – 1). Điều này cho phép thực hiện quá trình giải mã của hệ RSA nhanh hơn, vì các số mũ có kích cỡ nhỏ hơn. Thuật toán 2.1: Định lý đồng dư Trung Hoa tổng quát Input [x1, x2,...., xk], [p1, p2,...., pk] Output x (với x mod pi = xi với i =1, 2,..., k) 1. x = 0; N = p1; 2. For (i = 2; i  k; i++) {N = N * pi;} /* N là tích các số pi */ 3. For (i = 1; i  k; i++) /* tính nghiệm x */ { ci = (N/pi); si = ci -1 mod pi; x = (x + si * ci * xi) mod N; } 4. Return x; Trƣờng hợp đặc biệt của định lý đồng dƣ Trung Hoa đƣợc áp dụng cho quá trình giải mã ở hệ RSA, khi modulo N là tích của hai số nguyên tố p và q (N = p * q). Do đó, mọi số nguyên M < N đều biểu diễn duy nhất qua một bộ gồm hai số Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 [Mp, Mq], thỏa mãn Mp = M mod p và Mq = M mod q. Cho nên ta có thể giải mã thông điệp, bằng cách tính trƣớc hai số Mp và Mq rồi kết hợp chúng với công thức (10). Trong đó Mp, Mq đƣợc tính nhờ vào hệ quả (2.1) nhƣ sau: Mp = M mod p = (C d mod N) mod p = C d mod p (vì N = p * q) = C d mod p – 1 mod p = C dp mod p (với dp = d mod (p – 1). Hơn nữa, dễ dàng thấy rằng bản mã C cũng có thể rút gọn bởi mod p, trƣớc khi tính Mp, Mq. Nhƣ vậy, kích cỡ các toán hạng Cp = C mod p, Cq = C mod q, và dp = d mod (p – 1), dq = d mod (q – 1), đều giảm đi một nữa. Vậy, ta có cách tính Mp = Cp dp mod p và Mq = Cq dq mod q. Thuật toán 2.2: Định lý đồng dư Trung Hoa với modulo N = p* q Input Mp, Mq, p, q, N Output M (sao cho M = Mp mod p và M = Mq mod q) 1. y = q-1 mod p; 2. M = y * q * Mp mod N; 3. y = p-1 mod q; 4. M = (M + y * p * Mq) mod N; 5. Return M; 2.3.2 Thuật toán Garner Thuật toán Garner là một cải tiến hơn nữa về tốc độ giải mã so với thuật toán CRT vừa xét. Ở đây các bƣớc tính phần tử nghịch đảo đã bị loại bỏ, thuật toán này cũng tìm số nguyên M từ các số Mp = M mod p và Mq = M mod q. Ngoài ra thuật toán còn có tham số đầu vào: p’ = p-1 mod q đƣợc tính toán trƣớc. Thuật toán 2.3: Thuật toán Garner Input Mp, Mq, p, q, (p’ = p -1 mod q), N Output M 1. V = (Mq – Mp) mod q; 2. V = V * p’ mod q; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 3. M = V * p mod N; 4. M = M + Mp mod N; 5. Return M;  Phân tích chi phí thực hiện thuật toán Giả sử số N có kích cỡ n-bits, và các số nguyên tố p, q có kích cỡ n/2-bits. Thuật toán thực hiện một phép nhân của các số nguyên có kích cỡ n/2-bits để tính V tại (bƣớc 2) với chi phí 2(n/2)2+2(n/2)  n2/2 + o(n2), và một phép nhân của số nguyên có kích cỡ n-bits để tính M ở (bƣớc 3) với chi phí 2n2 +2n  2n2 + o(n2). Vậy chi phí của thuật toán là: 5n2/2 + o(n2). Ví dụ 2.3: Minh họa các bước thực hiện thuật toán Garner Cho hai số nguyên tố p = 47 và q = 61, các số dƣ Mp = 49 và Mq = 34, sử dụng thuật toán Garner, hãy tìm số nguyên M từ các số Mp và Mq. Tính trƣớc: N = p * q = 2747 và p’ = p -1 mod q = 47 -1 mod 61 = 13 b1: V = (Mq – Mp) mod q = (34 – 12) mod 61 = -12 mod 61 = 49 (vì 12+49  0 mod 61) b2: V = V * p’ mod q = 49 *13 mod 61 = 27 b3: M = V * p mod N = 27 * 47 mod 2747 = 1269 b4:  M = M + Mp mod N =1269 + 46 mod 2747 = 1315 2.3.3 Các quá trình tạo khoá, mã hoá và giải mã Hệ mật mã RSA With CRT có tốc độ thực hiện quá trình giải mã nhanh hơn hệ RSA chuẩn rất nhiều. Trong phần này chỉ trình bày các bƣớc tính toán thêm vào cho quá trình tạo khóa và quá trình giải mã nhờ vào định lý đồng dƣ Trung Hoa, còn quá trình mã hóa thì hoàn toàn giống với hệ RSA chuẩn. 2.3.3.1 Mô tả các quá trình tạo khoá và giải mã a) Tạo khoá: Quá trình tạo khóa cũng giống nhƣ hệ RSA chuẩn, nhƣng thêm các bƣớc sau: - Tính dp = d mod (p – 1) và dq = d mod (q – 1). - Tính phần tử nghịch đảo của p modulo q là: p’ = p-1 mod q. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 - Chọn (e, N) làm khoá công khai, còn (p, q, dp, dq, p’) làm khoá riêng. b) Giải Mã: - Tính các số Mp= Cp dp mod p và Mq= Cq dq mod q với: Cp = C mod p; Cq = C mod q - Giải mã C để tìm M từ các số Mp và Mq nhờ vào thuật toán Garner. Thuật toán 2.4 Input C, N, dp, dq, p, q, p’ = p -1 mod q Output M 1. Cp = C mod p; 2. Cq = C mod q; 3. Mp = Cp dp mod p; 4. Mq = Cq dq M mod q; 5. M = Garner(Mp, Mq, p, q, p’, N); 6. Return M; 2.3.3.2 Phân tích chi phí thuật toán giải mã RSA_CRT Giả sử số N sử dụng cho modulo RSA có kích cỡ n-bits, và các số nguyên tố p, q có kích cỡ n/2-bits. Thuật toán RSA_CRT thực hiện hai phép tính rút gọn modulo tại (b1) và (b2) với số nguyên có kích cỡ n-bits, và modulo có kích cỡ n/2- bits. Chi phí mỗi bƣớc là n2/2, tại (b3) và (b4) thực hiện hai phép tính lũy thừa modulo với số nguyên có kích cỡ n/2-bits, với mỗi bƣớc có chi phí 3n3/8 + n2/4. Tại (b5) thực hiện thuật toán Garner để tìm M từ hai số Mp và Mq với chi phí đã tính là 5n 2/2. Vậy tổng chi phí của thuật toán giải mã là: 3n3/4 + 7n2/2 + o(n2). 2.4 PHÂN TÍCH CƠ CHẾ HOẠT ĐỘNG CỦA HỆ MÃ RSA 2.4.1 Phân tích quá trình tạo khóa:  Tạo hai số nguyên tố phân biệt p và q lớn, sao cho bài toán phân tích thật sự là khó giải  Tính N = p* q và φ(N) = (p – 1) * (q – 1). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41  Chọn một số nguyên ngẫu nhiên e sao cho 1 < e < φ(N) và gcd(e, φ(N)) = 1  Sử dụng thuật toán Euclid mở rộng, để tính số nguyên d duy nhất, sao cho 0 < d < φ(N) và e * d  1 mod φ(N) (d là nghịch đảo của e modulo N)  Hai số (e, N) làm khóa công khai, còn (d, N) đƣợc giữ bí mật làm khóa riêng. Các số nguyên tố p, q sẽ bị xóa khi kết thúc quá trình tạo khóa. Nhƣ vậy, mấu chốt để tăng tính an toàn của hệ mã RSA là ta cần thực hiện đƣợc quá trình mã hóa xuất phát từ các số nguyên tố p, q lớn. 2.4.2 Phân tích quá trình mã hóa: Giả sử để gửi thông điệp M cho ngƣời B. Ngƣời A thực hiện nhƣ sau:  Lấy khóa công khai của ngƣời nhận B: (e, N).  Biến đổi thông điệp M thành những số nguyên Mi tƣơng ứng sao cho Mi < N, (i = 1,…, k). Theo phép biến đổi sau: - Biến đổi các ký tự trong thông điệp M thành các số nguyên tƣơng ứng, thí dụ theo qui tắc: Dấu cách  00, A  01, B  02,..., Z  26. - Chia thông điệp vừa biến đổi thành k nhóm có chiều dài bằng nhau, mỗi nhóm biểu diễn một số nguyên Mi  {0,…, N – 1} (với 1 ≤ i ≤ k).  Thực hiện mã hóa lần lƣợt cho từng số Mi  Ci bằng cách: Ci = Eke(Mi) = Mi e (mod N). Tập các số nguyên {C1, C2,...,Ck} là bản mã để gửi đến ngƣời nhận B. Ta thấy rằng quá trình mã hóa phải thực hiện liên tiếp việc mã hóa các số Mi theo công thức: Ci = Eke(Mi) = Mi e (mod N). Khi p và q lớn thì ta có N = p*q rất lớn. Trên lý thuyết, số e có thể chọn chỉ cần thỏa mãn gcd(e, φ(N)) = 1, tuy nhiên để tăng tính an toàn, số e thƣờng đƣợc sẽ là số lớn hơn Max(p,q) với Max(p,q) trả về số lớn nhất giữa p và q. Do đó, quá trình mã hóa sẽ thực hiện với các số rất lớn nhƣng vẫn phải đảm bảo thời gian thực hiện việc mã hóa là đủ tốt. Xuất phát từ các lí do trên, ta cần tác động vào quá trình mã hóa bằng các thuật toán tốt để có thể thỏa mãn các yêu cầu trên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 2.4.3 Phân tích quá trình giải mã: Ngƣời nhận B thực hiện các bƣớc sau:  Thực hiện giải mã lần lƣợt từng số nguyên Ci  Mi bằng cách: Mi = D(Ci) = Ci d (mod N) với 0 ≤ Mi < N, (d là khoá bí mật của B).  Thực hiện phép biến đổi ngƣợc lại từ các số Mi thành các chuỗi ký tự tƣơng ứng để khôi phục lại nội dung thông điệp M ban đầu. Quá trình giải mã cũng phải thực hiện việc tính toán liên tiếp để tìm Mi theo công thức: Mi = D(Ci) = Ci d (mod N), quá trình này cũng thực hiện trên các số lớn vì ta có d là số lớn. Do đó, quá trình giải mã cũng cần có các tác động để đảm bảo thời gian giải mã là chấp nhận đƣợc. Điều này có ý nghĩa rất quan trọng vì hệ mã RSA có số lƣợng phép tính lớn, bên cạnh đó để có thể thực hiện với các bản rõ có nội dung lớn thì ta phải giải quyết đƣợc vấn đề này. Kết luận: Trong thực tế, tốc độ mã hóa và giải mã của RSA là rất chậm so với các hệ mã khác. Điều này dẫn đến việc RSA chủ yếu đƣợc dùng để mã hóa khóa bí mật hoặc các các bản rõ ngắn. Phần nội dung chính cần gửi sẽ đƣợc mã hóa bằng một phƣơng pháp mã hóa khác có tốc độ thực hiện nhanh hơn (Phƣơng pháp này thƣờng kém an toàn hơn so với RSA). Ngƣời nhận sẽ giải mã bằng RSA để lấy khóa bí mật rồi mới tiến hành giải mã nội dung cần nhận. Điều này đã dẫn đến những bất cập về ứng dụng RSA rộng rãi trong thực tế. Giải quyết đƣợc mâu thuẫn giữa việc tăng tính an toàn và tăng thời gian thực hiện mã hóa là vấn đề cần đƣợc nghiên cứu để giải quyết. 2.5 KHẢ NĂNG BỊ BẺ KHÓA CỦA HỆ MÃ CÔNG KHAI RSA 2.5.1 Một số phƣơng pháp tấn công hệ mã RSA. Bất cứ ai cũng có thể tạo ra một hệ thống thông tin mã hóa cho riêng mình. Nhƣng để có một hệ thống an toàn và hiệu quả đòi hỏi ngƣời thiết kế phải có kiến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 thức toán học sâu sắc, có kinh nghiệm về bảo mật và am hiểu các phƣơng pháp tấn công. • Brute-force attack: phƣơng pháp tấn công bằng cách thử tất cả những chìa khóa có thể có. Đây là phƣơng pháp tấn công thô sơ nhất và cũng khó khăn nhất. Theo lý thuyết, tất cả các thuật toán mã hóa hiện đại đều có thể bị đánh bại bởi brute-force nhƣng trong thực tiễn việc này chỉ có thể thực hiện đƣợc trong thời gian hàng triệu, thậm chí hàng tỉ năm. Vì thế có thể coi một thuật toán mã hóa là an toàn nếu nhƣ không còn cách nào khác để tấn công nó dễ hơn là brute-force. • Frequency analysis: thống kê tần suất, chỉ có thể áp dụng đƣợc đối với các thuật toán cổ điển dùng phƣơng pháp thay thế, ví dụ phƣơng pháp Caesar. Để thực hiện phƣơng pháp này ta cần một lƣợng văn bản đã mã hóa đủ lớn để phép thống kê đƣợc chính xác. Ngoài ra còn phải biết ngôn ngữ sử dụng trong văn bản ban đầu, nếu văn bản ban đầu là tiếng Anh thì nhiều khả năng kí tự xuất hiện nhiều nhất trong văn bản đã mã hóa là do chữ e mã hóa thành. • Differential cryptanalysis: Phƣơng pháp này do Eli Biham và Adi Shamir tìm ra vào khoảng cuối những năm 1980, nó thƣờng đƣợc sử dụng để tấn công các thuật toán khối (block cipher). Phƣơng pháp này dựa trên việc phân tích những biến đổi của hai văn bản gốc có liên quan khi đƣợc mã hóa bởi cùng một chìa. • Tấn công dựa trên thời gian Năm 1995, Paul Kocher mô tả một dạng tấn công mới lên RSA: Khi kẻ tấn công nắm đủ thông tin về phần cứng thực hiện mã hóa và xác định đƣợc thời gian giải mã đối với một số bản mã lựa chọn thì có thể nhanh chóng tìm ra khóa d. Dạng tấn công này có thể áp dụng đối với hệ thống chữ ký điện tử sử dụng RSA. • Tấn công lựa chọn thích nghi bản mã Năm 1981, Daniel Bleichenbacher mô tả dạng tấn công lựa chọn thích nghi bản mã (adaptive chosen ciphertext attack) đầu tiên có thể thực hiện trên thực tế đối với một văn bản mã hóa bằng RSA. Văn bản này đƣợc mã hóa dựa trên tiêu chuẩn Public-Key Cryptography Standards #1 (PKCS #1), một tiêu chuẩn chuyển đổi bản rõ có khả năng kiểm tra tính hợp lệ của văn bản sau khi giải mã. Do những khiếm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 khuyết của PKCS #1, Bleichenbacher có thể thực hiện một tấn công lên bản RSA dùng cho giao thức Secure Sockets Layer (tìm đƣợc khóa phiên). Do phát hiện này, các mô hình chuyển đổi an toàn hơn nhƣ chuyển đổi mã hóa bất đối xứng tối ƣu (Optimal Asymmetric Encryption Padding) đƣợc khuyến cáo sử dụng. Đồng thời phòng nghiên cứu của RSA cũng đƣa ra phiên bản mới của PKCS #1 có khả năng chống lại dạng tấn công nói trên. • Phƣơng pháp sử dụng (n) Giả sử ngƣời tấn công biết đƣợc giá trị (n). Khi đó việc xác định giá trị p, q đƣợc đƣa về việc giải hai phƣơng trình sau n = p  q Thay q = n/p, ta đƣợc phƣơng trình bậc hai p, q chính là hai nghiệm của phƣơng trình bậc hai này. Tuy nhiên vấn đề phát hiện đƣợc giá trị (n) còn khó hơn việc xác định hai thừa số nguyên tố của n. Ngoài ra còn một số phƣơng pháp tấn công khác đƣợc sử dụng để tấn công hệ mã RSA. Tuy nhiên, từ cơ sở toán học của RSA, hầu hết các phƣơng pháp tấn công đều chƣa thực sự hiệu quả. Các cố gắng bẻ khóa RSA thành công đƣợc công bố đều phải dựa trên sức mạnh kết hợp của nhiều máy tính thực và thực hiện trong khoảng thời gian dài. Tuy nhiên, để đảm bảo tính an toàn cao cho hệ mã RSA nói riêng và các hệ mã công khai nói chung. Việc áp dụng các cải tiến nhằm tăng tính an toàn là cấp thiết. 2.5.2 Độ an toàn của hệ mã RSA. Độ an toàn của hệ thống RSA dựa trên 2 vấn đề của toán học: bài toán phân tích ra thừa số nguyên tố các số nguyên lớn và bài toán RSA. Nếu 2 bài toán trên là khó (không tìm đƣợc thuật toán hiệu quả để giải chúng) thì không thể thực hiện     11  qpn    012  npnnp  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 đƣợc việc phá mã toàn bộ đối với RSA. Phá mã một phần phải đƣợc ngăn chặn bằng các phƣơng pháp chuyển đổi bản rõ an toàn. Bài toán RSA: Cho số nguyên dƣơng N là tích của hai số nguyên tố phân biệt p và q (N = p * q), số nguyên e sao cho thỏa mãn gcd(e, (p – 1) * (q – 1)) = 1, và số nguyên c. Tìm một số nguyên m sao cho me  c (mod N). Hiện nay phƣơng pháp triển vọng nhất giải bài toán này là phân tích n ra thừa số nguyên tố. Khi thực hiện đƣợc điều này, kẻ tấn công sẽ tìm ra số mũ bí mật d từ khóa công khai và có thể giải mã theo đúng quy trình của thuật toán. Nếu kẻ tấn công tìm đƣợc 2 số nguyên tố p và q sao cho: n = p*q thì có thể dễ dàng tìm đƣợc giá trị (p-1)*(q-1) và qua đó xác định d từ e. Chƣa có một phƣơng pháp nào đƣợc tìm ra trên máy tính để giải bài toán này trong thời gian đa thức (polynomial-time). Tuy nhiên ngƣời ta cũng chƣa chứng minh đƣợc điều ngƣợc lại (sự không tồn tại của thuật toán). Tại thời điểm năm 2005, số lớn nhất có thể đƣợc phân tích ra thừa số nguyên tố có độ dài 663 bít với phƣơng pháp phân tán trong khi khóa của RSA có độ dài từ 1024 tới 2048 bít. Một số chuyên gia cho rằng khóa 1024 bít có thể sớm bị phá vỡ (cũng có nhiều ngƣời phản đối việc này). Với khóa 4096 bít thì hầu nhƣ không có khả năng bị phá vỡ trong tƣơng lai gần. Do đó, ngƣời ta thƣờng cho rằng RSA đảm bảo an toàn với điều kiện n đƣợc chọn đủ lớn. Nếu n có độ dài 256 bít hoặc ngắn hơn, nó có thể bị phân tích trong vài giờ với máy tính cá nhân dùng các phần mềm có sẵn. Nếu n có độ dài 512 bít, nó có thể bị phân tích bởi vài trăm máy tính tại thời điểm năm 1999. Năm 1993, Peter Shor công bố thuật toán Shor chỉ ra rằng: máy tính lƣợng tử (trên lý thuyết) có thể giải bài toán phân tích ra thừa số trong thời gian đa thức. Tuy nhiên, máy tính lƣợng tử vẫn chƣa thể phát triển đƣợc tới mức độ này trong nhiều năm nữa. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 Nhƣ vậy, tính an toàn của phƣơng pháp RSA dựa trên cơ sở các máy tính tại thời điểm hiện tại chƣa đủ khả năng giải quyết việc phân tích các số nguyên rất lớn ra thừa số nguyên tố. 2.6 HỆ MẬT MÃ KHÓA CÔNG KHAI ELGAMAL Vào năm 1985, Hệ mật mã khoá công khai ElGamal đƣợc giới thiệu bởi T. ElGamal. Độ an toàn của hệ này phụ thuộc vào độ khó giải bài toán logarithm rời rạc trong trƣờng số hữu hạn Zp. Vì vậy, số nguyên tố p cần phải đƣợc chọn sao cho bài toán logarithm là khó tính toán. Trƣờng hợp đặc biệt để ngăn ngừa sự tấn công, thì số nguyên tố p cần phải đƣợc chọn sao cho số (p - 1) có ít nhất một thừa số nguyên tố lớn q. 2.6.1 Bài toán logarithm rời rạc Định nghĩa 2.1: Một trƣờng hữu hạn là một trƣờng F chứa một số hữu hạn các phần tử. Bậc của nhóm F là số các phần tử tồn tại trong F . Hình xxx: Đồ thị so sánh chi phí tấn công khóa bí mật và khóa công khai 6 4 1 2 8 2 5 6 5 1 2 1 K 2 K 4 K Ñoä daøi maõ khoùa (bits) C h i p h í 1 2 1. Khóa bí mật 2. Khóa công khai Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 Định nghĩa 2.2: Cho Fq là một trƣờng hữu hạn, và một phần tử g  Fq, định nghĩa bậc (order) của g là số nguyên dƣơng m nhỏ nhất sao cho: gm  1(mod q), và ký hiệu là: Ordq(g) = m Định nghĩa 2.3: Một phần tử sinh g của trƣờng hữu hạn Fq, nếu g có bậc (q– 1); Phát biểu tương đương: g là phần tử sinh (chính), nếu lũy thừa của g có thể sinh ra tất cả các phần tử khác không của Fq *. Nghĩa là: {g x : 0 ≤ x ≤ q – 2} = Fq * Định lý 2.1: Mỗi trƣờng hữu hạn đều có phần tử sinh. Nếu g là một phần tử sinh của Fq * thì gj là phần tử sinh nếu và chỉ nếu gcd(j, q –1) = 1. Vậy có tổng cộng φ(q – 1) phần tử sinh khác nhau của Fq * . Định nghĩa 2.4: Cho G là một nhóm vòng (cyclic) hữu hạn có bậc n và g là phần tử sinh của G. Logarithm rời rạc của y cơ số g, kí hiệu loggy là một số nguyên duy nhất x, với 0  x  n – 1 sao cho: y = g x . Bài toán 2.1: Cho số nguyên tố p, một phần tử sinh g của Zp *, và một phần tử y  Zp *, tìm số nguyên x , 0  x  p – 2 sao cho: y = g x (mod p), (tìm x = loggy). 2.6.2 Định nghĩa các tập làm việc của hệ mật mã ElGamal  Tập các bản rõ M = Zp * = {1, 2,..., p-1}  Tập các bản mã C = Zp *  Zp *  Tập các khoá công khai Ke = {p}  P  Zp * ( với P là tập các phần tử sinh)  Tập các khóa riêng Kd = Zp - 1 = {1, 2,..., p – 2} 2.6.3 Quá trình tạo khoá, mã hoá, giải mã a) Tạo khoá:  Tạo số nguyên tố p lớn sao cho bài toán logarithm rời rạc trong Zp là khó giải và số p – 1 có ít nhất một thừa số nguyên tố q lớn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48  Chọn số g  Zp * là phần tử sinh. Các giá trị p và gthƣờng đƣợc sử dụng nhƣ những tham số chung trong nhóm.  Ngƣời sử dụng chọn ngẫu nhiên số x sao cho 0 < x < p – 2, và định nghĩa: K = {(p, g, x,y y = gx (mod p)}.  Công bố bộ ba số nguyên (p, g, y) làm khoá công khai, còn số nguyên x đƣợc giữ bí mật làm khóa riêng. b) Mã hoá: Mã hóa thông điệp M gửi cho B, thì ngƣời gửi A thực hiện các bƣớc nhƣ sau:  Dùng thuật toán để chia thông điệp M ra nhiều khối có chiều dài cố định và mỗi khối đƣợc biến đổi thành một số nguyên tƣơng ứng Mi < p, (i =1,.…, k). - Biến đổi các ký tự của thông điệp thành các số tƣơng ứng, thí dụ theo qui tắc: Dấu cách  00, A  01, B  02,..., Z  26. - Chia thông điệp số vừa biến đổi thành r nhóm số có chiều dài bằng nhau, mỗi nhóm biểu diễn một số nguyên Mi < p với (1  i  r).  Lấy khóa công khai của ngƣời nhận B (p, g, y).  Chọn ngẫu nhiên một số nguyên k sao cho 0  k  (p – 2).  Mã hoá lần lƣợt từng số Mi với khóa công khai của ngƣời nhận, bằng cách tính: Ci = Eke(Mi) = (Ci1, Ci2), với Ci1 = g k mod p và Ci2 = Mi *y k mod p Tập số {C1, C2,...,Cr}, với Ci = (Ci1, Ci2), i = 1,…, r là bản mã gửi cho B. c) Giải mã: Để giải mã bản mã {C1, C2,...,Cr }, ngƣời nhận B thực hiện các bƣớc nhƣ sau:  Giải mã lần lƣợt các cặp số Ci = (Ci1, Ci2), với 1  i  r Tính: Mi = DKd(Ci1, Ci2) = Ci2 * (Ci1 x ) -1 mod p.  Kết quả thu đƣợc là tập các số nguyên lớn { M1, M2,..., Mr }. Biến đổi các số nguyên Mi trở lại các chuỗi ký tự tƣơng ứng và khôi phục lại thông điệp M. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 Bảng 2.1: Tóm tắt các bước tạo khoá, mã hoá, giải mã của Hệ ElGamal 2.6.4 Tính đúng của quá trình giải mã Ta có: y = gx (mod p) (định nghĩa) và C1 = g k mod p C2 = M *y k mod p  DKd(C1, C2) = C2 * (C1 x ) -1 mod p = M * y k * ([g k)-x mod p = M * g x ] k * ([g k)-x mod p = M * g kx * g -kx mod p = M mod p mà M < p, vậy DKd(C1, C2) = M mod p = M 2.6.5 Đánh giá độ an toàn và khả năng ứng dụng của hệ mật mã khóa công khai ElGamal 2.6.5.1 Độ an toàn Để đảm bảo độ an toàn cho hệ ElGamal ngƣời thiết kế phải tạo số nguyên tố Mã hoá: Mã hoá bản rõ M * Chọn số ngẫu nhiên k: 1  k  p – 2 * Tính C = Eke(M) = (C1, C2) với C1 = g k (mod p), C2 = M*y k (mod p) Giải mã: Giải mã bản mã C M = D(C) = Dkd(C1, C2) = C2 * (C1 x ) -1 mod p Tạo khoá: * Tạo số nguyên tố p lớn, sao cho bài toán logarithm rời rạc trong Zp * là khó thực hiện. * Chọn g Zp * là phần tử sinh. * Chọn ngẫu nhiên số 0 < x < p – 2. * Tính y = gx (mod p). Khoá công khai: (p, g, y) Khóa riêng: ( x ) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 p lớn (khoảng 1024-bits), sao cho số p – 1 có ít nhất một thừa số nguyên tố q lớn nhằm ngăn ngừa sự tấn công của kỹ thuật Pohlig-Hellman. Ngoài ra số ngẫu nhiên k không đƣợc sử dụng để mã hóa nhiều hơn một thông địêp. Vì nếu sử dụng k để mã hoá cho hai thông điệp M và M’ với kết quả là (C1, C2) và (C1’, C2’) thì ta có C2(C2’)  M(M’) -1(mod p). Vậy nếu biết đƣợc M thì M’ có thể tính toán đƣợc dễ dàng. 2.6.5.2 Khả năng thực hiện và ứng dụng Phƣơng pháp tính toán của hệ mã ElGamal rất phức tạp, vì đòi hỏi nhiều phép tính lũy thừa modulo trong quá trình mã hóa và giải mã, nên có hiệu suất thực hiện kém. Do đó thƣờng không đƣợc ứng dụng trong những trƣờng hợp mã hóa khối lƣợng lớn dữ liệu. Tính chất không thể phủ nhận (non-repudiation) của hệ này là cơ sở của các lƣợc đồ chứng thực và chữ ký điện tử (phiên bản sửa đổi của lƣợc đồ chữ ký ElGamal là chữ ký DSA đƣợc dùng trong chuẩn chữ ký điện tử của NIST ở Mỹ và cả thế giới). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 CHƢƠNG 3 : MỘT SỐ GIẢI THUẬT XỬ LÝ SỐ HỌC ÁP DỤNG ĐỂ TỐI ƢU HÓA QUÁ TRÌNH MÃ HÓA VÀ GIẢI MÃ CỦA HỆ MÃ RSA 3.1 PHÂN TÍCH CÁC PHÉP XỬ LÝ TOÁN HỌC TRONG HỆ MÃ RSA 3.1.1 Xử lý với số nguyên lớn. Trong quá trình tạo khóa ta cần phải tạo ra hai số nguyên tố phân biệt p và q lớn, sao cho bài toán phân tích thật sự là khó giải. Nhƣ vậy, để đảm bảo an toàn cho hệ mã RSA, giải thuật xử lý phải thực hiện đƣợc với các số lớn hàng trăm chữ số. 3.1.2 Xử lý các phép toán với số nguyên lớn. 3.1.2.1 Phép nhân với số nguyên lớn. Để thực hiện đƣợc các phép tính toán trong quá trình ta cần thực hiện đƣợc các phép toán đƣợc sử dụng. Trong quá trình tạo khóa, ta phải tính đƣợc N = p*q và φ(N) = (p–1)*(q–1). Do đó chƣơng trình cần xử lý đƣợc phép nhân hai số p và q với p và q là các số nguyên tố lớn. 3.1.2.2 Phép cộng – trừ số nguyên lớn. Sử dụng trong các quá trình tính toán, việc cài đặt tƣơng đối đơn giản khi đã tổ chức đƣợc dữ liệu lƣu trữ cho các số hạng. 3.1.2.3 Phép tính lũy thừa với số nguyên lớn. Quá trình giải mã của RSA cần tính M = Cd mod N, với số mũ bí mật d thƣờng rất lớn (d  N) để đảm bảo độ an toàn cho dữ liệu. Vì vậy chi phí thực hiện giải mã của hệ RSA tƣơng đƣơng với chi phí để thực hiện phép tính lũy thừa nhanh là: 3n3 + n2. Do đó chƣơng trình cần phải xử lý đƣợc các phép tính lũy thừa nhanh. Kết luận: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 Về bản chất, phép lũy chính là phép nhân liên tiếp, sử dụng các tính chất đồng dƣ, ta có thể đƣa việc xử lý phép lũy thừa về phép nhân. Do đó, trong đề tài này đi sâu vào việc xử lý phép nhân nhanh số nguyên với các số hạng là các số lớn. Kết quả thực hiện sẽ được thử nghiệm với hai chương trình: Chƣơng trình 1: Xử lý các phép toán số học với số lớn Thực hiện các phép tính số học: Cộng, trừ, nhân, lũy thừa với số lớn. Đây là phần kết quả cơ bản của đề tài, về mặt lý thuyết, khi cài đặt thành công các phép xử lý toán học này ta hoàn toàn có thể áp dụng để xây dựng hệ mã RSA. Chƣơng trình 2: Hệ mã RSA thử nghiệm Áp dụng các kết quả đã có đƣợc trong việc xử lý các phép toán số học để bƣớc đầu xây dựng thử nghiệm một hệ mã RSA. Trong điều kiện có hạn của luận văn và sự phức tạp của hệ mã RSA, chƣơng trình chỉ dừng ở mức thực nghiệm. 3.2 ỨNG DỤNG GIẢI THUẬT FAST FOURIER TRANSFORM TRONG XỬ LÝ PHÉP NHÂN SỐ LỚN 3.2.1 Giới thiệu thuật toán FFT Cho hai số lớn X và Y với kích thƣớc lớn nhất là n-1, chúng có thể đƣợc viết ở dạng sau: X = P(B), Y = Q(B) Với B là cơ số (Thông thƣờng B=10 hoặc là lũy thừa của 10). P và Q là hai đa thức P(z) = n-1  j = 0 xj z j , Q(z) = n-1  j = 0 yjz j . Kết quả khi thực hiện nhân P(z) với Q(z) trong R(z), khi đó ta có đƣợc tích X.Y = R(B). Bằng cách sắp xếp lại theo hệ số của R(z) ta thu đƣợc kết quả của phép nhân X với Y. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 Dựa trên lý thuyết này, ta áp dụng để thực hiện việc nhân hai đa thức có bậc nhỏ hơn n. Một đa thức có bậc nhỏ hơn m là duy nhất khi nó đƣợc tạo bởi các giá trị cụ thể tại m điểm. Do đó, để tính tích R(z)= P(z).Q(z) ta cần đi tính các giá trị R(wk) tại 2n điểm phân biệt ứng với mỗi wk, điều này cũng có nghĩa là ta cần tính các giá trị của P(wk) và Q(wk). Thuật toán FFT là một gợi ý phù hợp với việc lựa chọn cho wk căn của đơn vị. wk = exp    2ik 2n    = k,  = exp    2i 2n    Với cách lựa chọn này, các giá trị wk thỏa mãn hai thuộc tính sau:  Tập hợp các giá trị (P(w0),,P(w2n-1)) và (Q(w0),,Q(w2n-1)) có thể tính toán đƣợc trong thời gian O(n logn).  Từ các giá trị R(wk) với i = 0,,2n-1, đa thức R(z) thu đƣợc trong thời gian O(n logn). Khi đó, hệ số thứ k kí hiệu là rk của R(z) thỏa mãn: rk = 1 2n T   wk   , T(z) = 2n-1  j = 0 R(wj) z j , 3.2.2 Biến đổi Fourier Cho dãy A = (a0, a1,, a2n-1), tìm dạng biến đổi Fourier của dãy A. Gọi F2n(A) là dạng biến đổi Fourier của A, khi đó F2n(A) đƣợc biểu diễn nhƣ sau: F2n(A) = (b0, b1, , b2n-1), bk = 2n-1  j = 0 aj  jk . (*) Cuối cùng ta thu đƣợc R(z) bằng dạng biến đổi Fourier ngƣợc với các hệ số R(j) đƣợc thể hiện trong công thức sau: F 2n (F2n(R)) = 2n R, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 F 2n (A) = (b0, b1, , b2n-1), bk = 2n-1  j = 0 aj  -jk . 3.2.3 Biến đổi Fourier nhanh Thuật toán Fast Fourier Transform là phƣơng pháp để tìm ra dạng biến đổi Fourier của dãy số A trong thời gian O(n logn). Cách này nhanh hơn với phƣơng pháp truyền thống cần đến thời gian O(n2) với n là lũy thừa của 2. bk = 2n-1  j = 0 aj  jk = n-1  j = 0 a2j ( 2 ) jk + k n-1  j = 0 a2j+1 ( 2 ) jk . Nói cách khác, để tính toán các hệ số bk của F2n(A), ta thực hiện các bƣớc sau: Định nghĩa 2 dãy con kích thƣớc n, A0 chứa các hệ số chẵn còn A1 chứa các hệ số lẻ. A0 = (a0, a2, , a2n-2), and A1 = (a1,a3,,a2n-1).  Tìm các biến đổi Fourier C = Fn(A0) = (c0,c1,,cn-1) and D = Fn(A1) = (d0,d1,,dn-1).  Từ đó suy ra biểu diễn Fourier của B = (b0,,b2n-1) = F2n(A) theo các công thức sau: bk = ck +  k dk, bn+k = ck -  k dk, 0  k < n. 3.2.3 Phép nhân số lớn áp dụng giải thuật FFT 3.2.3.1 Giải thuật Phần này trình bày thuật toán để thực hiện phép nhân hai số lớn với FFT. Phƣơng pháp này đƣợc Schönhage và Strassen đề xuất năm 1971 và cho tới nay đây vẫn là phƣơng pháp nhân hai số lớn nhanh nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 Cho n là lũy thừa của 2 và hai số nguyên lớn X và Y có ít hơn n hệ số khi biểu diễn ở dạng đa thức cơ số B. X và Y có dạng biểu diễn đa thức nhƣ sau: X = n-1  j = 0 xj B j , Y = n-1  j = 0 yj B j . Để tính Z=XY ta thực hiện các bƣớc sau :  Tìm dạng biến đổi Fourier X* của X với kích thƣớc 2n: X * = (x0 * ,x1 * ,,x2n-1 * )  F2n(x0,x1,,xn-1,0,,0)  Tƣơng tự, ta tìm Y* là dạng biểu diễn Fourier của Y: Y * = (y0 * ,y1 * ,,y2n-1 * )  F2n(y0,y1,,yn-1,0,,0).  Nhân các phần tử tƣơng ứng của X* với Y* rồi lƣu kết quả trong Z* Z * = (z0 * ,z1 * ,,z2n-1 * ), zi *  xi * yi * .  Biến đổi Fourier ngƣợc để tìm Z từ Z* Z = (z0,z1,,z2n-1)  1 2n F 2n (Z * ).  Đa thức Z chính là kết quả cần tìm của tích XY Z = 2n-1  i = 0 zi B i Chú ý rằng X* là dạng biến đổi Fourier của dãy x0,,xn-1 với n số 0 đƣợc thêm vào sau x0,,xn-1 và Y * là dạng biến đổi Fourier của dãy y0,,yn-1 với n số 0 đƣợc thêm vào sau y0,,yn-1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 3.2.3.1 Cài đặt giải thuật nhân nhanh Thực hiện việc nhân nhanh số lớn sử dụng thuật toán FFT áp dụng trong nhân nhanh hai số lớn nhằm biến đổi rời rạc Fourier trong thời gian O(nlogn). Giải thuật Discrete Fourier Transform (DFT) sẽ đƣợc áp dụng trong sơ đồ sau để thực hiện phép nhân: Thêm các số 0 [ a 0 , a 1 , a 2 ,..., a n -1 ] [ b 0 , b 1 , b 2 ,..., b n -1 ] DFT DFT [ a 0 , a 1 , a 2 ,..., a n -1 ,0,0,...,0] [ b 0 , b 1 , b 2 ,..., b n -1 ,0,0,...,0] [ y 0 , y 1 , y 2 ,..., y 2 n -1 ] [ z 0 , z 1 , z 2 ,..., z 2 n -1 ] Khối thực hiện nhân DFT ngƣợc [ y 0 z 0 , y 1 z 1 ,..., y 2 n -1 z 2 n -1 ] [ c 0 , c 1 , c 2 ,..., c 2 n -1 ] Thêm các số 0 Sơ đồ 3.1: Thực hiện giải thuật nhân nhanh sử dụng DFT Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 3.2.3.1 Cài đặt thuật toán FFT và DFT Mô phỏng thuật toán FFT: Cho dãy A có chiều dài là m, w là căn nguyên thủy bậc m của đơn vị. Kết quả đƣợc lƣu trong vector V FFT(A, m, w,V) { if (m==1) return vector V = (a_0) else { A_even = (a_0, a_2, ..., a_{m-2}) A_odd = (a_1, a_3, ..., a_{m-1}) V_even = FFT(A_even, m/2, w^2) //w^2 là căn nguyên thủy bậc m/2 của đơn vị. V_odd = FFT(A_odd, m/2, w^2) for (j=0; j < m/2; ++j) { V[j] = V_even[j] + w^j*V_odd[j] V[j+m/2] = V_even[j] - w^j*V_odd[j] } } Thuật toán Direct fourier transform int DFT(int dir,int m,double *x1,double *y1) { long i,k; double arg; double cosarg,sinarg; double *x2=NULL,*y2=NULL; x2 = malloc(m*sizeof(double)); y2 = malloc(m*sizeof(double)); if (x2 == NULL || y2 == NULL) return(FALSE); for (i=0;i<m;i++) { x2[i] = 0; y2[i] = 0; arg = - dir * 2.0 * 3.141592654 * (double)i / (double)m; for (k=0;k<m;k++) { cosarg = cos(k * arg); sinarg = sin(k * arg); x2[i] += (x1[k] * cosarg - y1[k] * sinarg); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 y2[i] += (x1[k] * sinarg + y1[k] * cosarg); } } /* Copy the data back */ if (dir == 1) { for (i=0;i<m;i++) { x1[i] = x2[i] / (double)m; y1[i] = y2[i] / (double)m; } } else { for (i=0;i<m;i++) { x1[i] = x2[i]; y1[i] = y2[i]; } } free(x2); free(y2); return(TRUE); } Thuật toán Fast Fourier Transform X và Y là hay dãy số gồm 2m phần tử. dir = 1 thực hiện chiều thuận của FFT. dir = -1 thực hiện chiều ngƣợc của FFT. */ short FFT(short int dir,long m,double *x,double *y) { long n,i,i1,j,k,i2,l,l1,l2; double c1,c2,tx,ty,t1,t2,u1,u2,z; n = 1; for (i=0;i<m;i++) n *= 2; i2 = n >> 1; /* Sử dụng phép dịch phải*/ j = 0; for (i=0;i<n-1;i++) { if (i < j) { tx = x[i]; ty = y[i]; x[i] = x[j]; y[i] = y[j]; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 x[j] = tx; y[j] = ty; } k = i2; while (k <= j) { j -= k; k >>= 1; } j += k; } /* Thực hiện FFT */ c1 = -1.0; c2 = 0.0; l2 = 1; for (l=0;l<m;l++) { l1 = l2; l2 <<= 1; /* Sử dụng phép dịch trái*/ u1 = 1.0; u2 = 0.0; for (j=0;j<l1;j++) { for (i=j;i<n;i+=l2) { i1 = i + l1; t1 = u1 * x[i1] - u2 * y[i1]; t2 = u1 * y[i1] + u2 * x[i1]; x[i1] = x[i] - t1; y[i1] = y[i] - t2; x[i] += t1; y[i] += t2; } z = u1 * c1 - u2 * c2; u2 = u1 * c2 + u2 * c1; u1 = z; } c2 = sqrt((1.0 - c1) / 2.0); if (dir == 1) c2 = -c2; c1 = sqrt((1.0 + c1) / 2.0); } /* Thực hiện chiều thuận của FFT */ if (dir == 1) { for (i=0;i<n;i++) { Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 x[i] /= n; y[i] /= n; } } return(TRUE); } Cơ số B đƣợc sử dụng khi áp dụng cài đặt là 2. Ta chọn cơ số này vì máy tính biểu diễn thông tin trong hệ cơ số 2. Việc tối ƣu hóa trong cài đặt sẽ đƣợc thực hiện với các phép dịch bit. Thuật toán sẽ thực hiện rất nhanh do phép dịch bit có tốc độ thực hiện nhanh. Bằng việc sử dụng các phép dịch bit, ta đã tối ƣu hóa việc cài đặt thuật toán nhân nhanh so với cách cài đặt thông thƣờng. 3.3 CÀI ĐẶT THỬ NGHIỆM CÁC PHÉP TOÁN VỚI SỐ LỚN Từ các kết quả phân tích, các thuật toán số học đƣợc cài đặt thành chƣơng trình để chạy thử nghiệm với các số lớn. 3.2.1 Xử lý phép cộng –trừ Giải thuật cộng – trừ hai số nguyên lớn có thể đƣợc thực hiện dễ dàng khi hai số đã đƣợc tổ chức dữ liệu để biểu diễn. Ví dụ 3.1: Giả sử ta cần cộng hai số a, b đã đƣợc biểu diễn ở dạng chuỗi là Sa và Sb. Giải thuật cộng hai số lớn có thể đƣợc thực hiện nhƣ sau: Bước 1: Đƣa hai số a, b về cùng độ dài N (Nếu độ dài của a và b là khác nhau) bằng cách thêm các số 0 vào đầu của số có độ dài nhỏ hơn. Ta đƣợc Sa và Sb có cùng độ dài N với N =Max[Length(Sa), Length(Sb)] Bước 2: Gán giá trị Remem =0 (Remem là biến để nhớ số hàng chục của kết quả (Sa[k] + Sb[k]), đảo ngƣợc Sa và Sb Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 Bước 3: Cộng từng vị trí tƣơng ứng của hai chuỗi Sa và Sb từ trái sang phải. Lƣu kết quả mỗi bƣớc trong chuỗi Sc với Sc[k]= (Sa[k] + Sb[k]+Remem) mod 10, Remem = (Sa[k] + Sb[k]) div 10. Gán Sc[N+1]=Remem Bước 4: Đảo ngƣợc Sc (Chỉ lấy từ vị trí 1 đến vị trí cuối cùng khác 0) ta thu đƣợc kết quả trong Sc. (Chiều dài của Sc có thể từ 0 đến N+1) Giải thuật trên có thể áp dụng tƣơng tự cho phép trừ, bên cạnh cách tổ chức dữ liệu bằng chuỗi (Thƣờng gặp hạn chế vì chiều dài của chuỗi cũng có giới hạn) ta có thể tổ chức dữ liệu sử dụng Stack. Dễ thấy độ phức tạp của thuật toán này luôn là O(n). Cài đặt thử nghiệm: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 3.2.2 Xử lý phép nhân Có nhiều giải thuật để thực hiện nhân nhanh hai số lớn. Ở đây ta sử dụng giải thuật nhân nhanh ứng dụng giải thuật Fast Fourier Transform (FFT). Giải thuật nhân nhanh hai số nguyên lớn với N chữ số có thể thực hiện đƣợc với độ phức tạp O(n ln(n)ln(ln(n))) khi áp dụng thuật toán FFT. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 CHƢƠNG 4: ỨNG DỤNG TRONG XÂY DỰNG HỆ MÃ RSA 4.1 XÂY DỰNG HỆ MÃ RSA THỬ NGHIỆM Giao diện chƣơng trình: File văn bản rõ trƣớc khi mã hóa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 Giao diện thực hiện mã hóa và giải mã file văn bản: (Hình 4.3 và 4.4) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 Văn bản thu đƣợc sau mã hóa: Kết quả khi thực hiện quá trình giải mã: 4.2 ĐÁNH GIÁ VÀ NHẬN XÉT KẾT QUẢ 4.2.1 Chƣơng trình xử lý các phép toán với số lớn: Minh họa các thuật toán cộng, nhân, lũy thừa nhanh với số lớn. Thể hiện đƣợc các thông số khi cần kiểm nghiệm nhân hai số lớn nhƣ: - Tính chính xác của thuật toán. - Thời gian thực hiện (Tính bằng đơn vị thời gian) khi thực hiện với nhiều phép nhân số lớn liên tục. 4.2.1 Chƣơng trình mô phỏng hệ mã RSA: Thực hiện quá trình thử nghiệm mã hóa với các tham số Chƣơng trình thử nghiệm với các bộ số p, q lớn và cho kết quả chính xác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 CHƢƠNG V: KẾT LUẬN CÁC KẾT QUẢ ĐẠT ĐƢỢC: Đề tài bƣớc đầu đƣa ra giải pháp để xử lý các phép toán số học với số lớn trong các hệ mã công khai dựa trên cơ sở toán học và tính toán độ an toàn của các hệ mã công khai. Các kết quả nghiên cứu và ứng dụng bƣớc đầu đã thực hiện đƣợc mục đích của đề tài. Bằng việc tối ƣu hóa các phép xử lý tính toán phức tạp trong hệ mã công khai và minh chứng trong hệ mã cụ thể RSA. Giải thuật đƣợc áp dụng để tối ƣu hóa phép nhân là giải thuật xử lý có độ phức tạp nhỏ nhất đƣợc biết đến cho tới thời điểm hiện nay. Chƣơng trình thử nghiệm đƣợc xây dựng nhằm chứng minh tính khả thi của các kết quả nghiên cứu. Chƣơng trình hoàn thiện cần có sự đầu tƣ nhiều hơn về mặt thời gian và công sức. Đề tài có thể tiếp tục phát triển để đem lại ứng dụng đáp ứng đƣợc yêu cầu thực tế. HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI Các kết quả của đề tài có thể đƣợc áp dụng trong nhiều hệ mã công khai khác nhau và tiếp tục đƣợc cải tiến để có đƣợc tốc độ thực thi tốt hơn. Các kết quả có thể đƣợc áp dụng trên nhiều hệ thống bảo mật, thực hiện trong các giao dịch trên mạng, thực hiện tạo và xác thực chữ ký điện tử. Bên cạnh đó, cần tối ƣu hơn nữa các phép toàn bằng các cài đặt đƣợc thử nghiệm với các ngôn ngữ lập trình mạnh. Tác giả mong muốn có thể tiếp tục phát triển để đƣa các kết quả đã nghiên cứu vào ứng dụng trong thực tế. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 TÀI LIỆU THAM KHẢO Tiếng Việt [1]. Phan Đình Diệu (1999), Lý thuyết mật mã và an toàn thông tin, Nxb Đại Học Quốc Gia Hà Nội, Hà Nội. [2]. Dƣơng Anh Đức, Trần Minh Triết (2005), Mã hóa và ứng dụng, Nxb Đại Học Quốc Gia TP Hồ Chí Minh, TP Hồ Chí Minh. [3]. Phạm Huy Điển, Hà Huy Khoái (2003), Mã hóa thông tin Cơ sở toán học & ứng dụng, Viện toán học Hà Nội, Hà Nội. [4]. Bùi Doãn Khanh, Nguyễn Đình Thúc (2005), Giáo trình mã hóa thông tin Lý thuyết & ứng dụng, Nxb Lao Động Xã Hội, TP Hồ Chí Minh. [5]. PGS Hồ Thuần (2000), Giáo trình Lý thuyết mật mã và an toàn dữ liệu, Đại học Bách Khoa Hà Nội, Hà Nội. Tiếng Anh [6]. Andreas V. Meier (2005), “The ElGamar Cryptosystems” [7]. Deninis Luciano, Gordon Prichett (1978), From Caesar Ciphers To Public Key Cryptosystems. ( [8]. RHUL M.Sc Advanced Cryptography, Week 7: Public Key Cryptography + RSA, Spring 2004. [9]. Dr Andreas Steffen (2000), Secure Network Communication Part II Public Key Cryptography. [10]. Dr Cunsheng Ding, HKUST Hong Kong (September 2004), The ElGamal Public Key Cryptosystem. http:/www.cs.ust.hk/faculty/cding/CSIT571/SLIDES/slide09.pdf [11]. R.Rivest, MIT Laboratory for computer Science and RSA Data Security, Inc. (April 1992), The MD5 Message – Digest Algorithm. [12]. RSA Laboratories’ FAQ, RSA Security Inc.( [13]. Ph.D William. Stallings (1999), Cryptography And Internetwork Security – Principles And Practice, PRENTICE HALL. [14]. Message Authentication, Hash Function, Digital Signature schemes. [15].Tsuyoshi Takagi, Juniorprofessor (2003), Efficiency Comparison Of Several RSA Variants.