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 tốn RSA cũng cĩ độ khĩ tƣơng tự nhƣ bài tố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 khố, mã hố 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 tố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 tố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à khố 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 khố, mã hố, giải mã của Hệ RSA Tạo khố: 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 tố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 tố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ã hố 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ã hố: 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 tồ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 tồn Hệ RSA đƣợc thiết kế dựa trên độ khĩ giải bài tố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 tố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 tốn phân tích tốt nhất hiện nay (Bảng 2.3). Ở đây chi phí tính tốn đƣợc tính bằng đơn vị MIPS-Years (đĩ là số các phép tính đã hồ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 tố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 đã hồ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 tố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 tố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 tồ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 tồ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 tồ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 tốn hạng là những số nguyên cực lớn ( thơng thƣờng các phép tố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ã khố 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 tố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 tố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 tố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 tố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 tố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 tố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 tốn Garner Thuật tốn Garner là một cải tiến hơn nữa về tốc độ giải mã so với thuật tố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 tốn này cũng tìm số nguyên M từ các số Mp = M mod p và Mq = M mod q. Ngồi ra thuật tốn cịn cĩ tham số đầu vào: p’ = p-1 mod q đƣợc tính tốn trƣớc. Thuật tốn 2.3: Thuật tố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 tố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 tố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 tốn là: 5n2/2 + o(n2). Ví dụ 2.3: Minh họa các bước thực hiện thuật tố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 tố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 khố, mã hố 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 tố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ì hồn tồn giống với hệ RSA chuẩn. 2.3.3.1 Mơ tả các quá trình tạo khố và giải mã a) Tạo khố: 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 khố cơng khai, cịn (p, q, dp, dq, p’) làm khố 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 tốn Garner. Thuật tố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 tố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 tố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 tố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 tố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 tố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 tố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 tồ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 tồ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 tố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à khố 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 tố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 tồ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 tồ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 tồ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 tố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 tố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 tốn mã hĩa là an tồ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 tố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. Ngồ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 tố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 tồ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. Ngồ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ở tố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 tồ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 tồn là cấp thiết. 2.5.2 Độ an tồn của hệ mã RSA. Độ an tồn của hệ thống RSA dựa trên 2 vấn đề của tốn học: bài tốn phân tích ra thừa số nguyên tố các số nguyên lớn và bài tốn RSA. Nếu 2 bài tốn trên là khĩ (khơng tìm đƣợc thuật tố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ã tồ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 tồn. Bài tố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 tố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 tố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 tố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 tố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 tồ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 tốn Shor chỉ ra rằng: máy tính lƣợng tử (trên lý thuyết) cĩ thể giải bài tố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 tồ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ã khố cơng khai ElGamal đƣợc giới thiệu bởi T. ElGamal. Độ an tồn của hệ này phụ thuộc vào độ khĩ giải bài tố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 tốn logarithm là khĩ tính tố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 tố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 Độ dài mã khó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 tố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 khố 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 khố, mã hố, giải mã a) Tạo khố:  Tạo số nguyên tố p lớn sao cho bài tố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 khố cơng khai, cịn số nguyên x đƣợc giữ bí mật làm khĩa riêng. b) Mã hố: 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 tố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ã hố 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 khố, mã hố, 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 tồ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 tồn Để đảm bảo độ an tồn cho hệ ElGamal ngƣời thiết kế phải tạo số nguyên tố Mã hố: Mã hố 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 khố: * Tạo số nguyên tố p lớn, sao cho bài tố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). Khố 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. Ngồ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ã hố 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 tố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 tố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Ý TỐ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 tốn phân tích thật sự là khĩ giải. Nhƣ vậy, để đảm bảo an tồ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 tố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 tốn trong quá trình ta cần thực hiện đƣợc các phép tố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 tố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 tồ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 tố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ý tốn học này ta hồn tồ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 tố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 tố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 tố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 tố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 tố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 tố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 tố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 tố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 tốn FFT và DFT Mơ phỏng thuật tố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 tố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 tố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 tố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 tố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 TỐN VỚI SỐ LỚN Từ các kết quả phân tích, các thuật tố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 tố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 tố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 tốn với số lớn: Minh họa các thuật tố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 tố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 tốn số học với số lớn trong các hệ mã cơng khai dựa trên cơ sở tốn học và tính tốn độ an tồ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 tố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 hồ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 tồ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 tồ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 Khối (2003), Mã hĩa thơng tin Cơ sở tốn học & ứng dụng, Viện tốn học Hà Nội, Hà Nội. [4]. Bùi Dỗ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 tồ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.