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

p nguyên tố là 1/354. Mặt khác, do chúng ta chỉ quan tâm đến những số lẻ, nên xác suất để p nguyên tố là 2/354 = 1/177. Vậy thì, trung bình khoảng 177 số lẻ ngẫu nhiên sẽ có 1 số nguyên tố. Ngƣời ta đã cũng chứng minh đƣợc, thuật toán Miller-Rabin dùng kiểm tra tính nguyên tố của một số nguyên dƣơng lẻ với sai số nhiều nhất là 1/4. Nếu thực hiện thuật toán này t lần thì sai số nhiều nhất sẽ là 1/4t, để đảm bảo chắc chắn tính nguyên tố cho số kiểm tra nên chọn số t > 20. Thuật toán này đƣợc sử dụng trong quá trình tạo khóa ở hệ mật mã RSA. Thuật toán Miller-Rabin: Kiểm tra tính nguyên tố của một số dạng 2km+1 Input n > 2, n = 2 k m + 1 Output [True, False] (True: n là số nguyên tố, False: n là hợp số) 1. Giả sử n = 2km + 1; ( với m lẻ) 2. Chọn số ngẫu nhiên a  {2,..., n-1}; 3. Tính b = am (mod n); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 4. if (b  1 and b  (n – 1)) Return True; /* n nguyên tố */ 5. i = 1; 6. while (i < k and b  (n – 1)) { b = b 2 (mod n); if (b = 1) Return False; /* n là hợp số */ i ++; } 7. if (b! = (n – 1)) Return False; /* n hợp số */ 8. Return True; /* n là số nguyên tố */ Thuật toán: Kiểm tra tính nguyên tố của một số dạng 2km+1 với t lần thực hiện (t > 20) Input n > 2, n = 2 k m + 1 Output {True, False} (True: n là số nguyên tố, False: n là hợp số) 1. Giả sử n = 2km + 1; 2. For (j = 1; j  t; j++) { Chọn số ngẫu nhiên a  {2,.....,n-1} Tính b = am mod n; if (b = 1) continue; /* quay lại bƣớc 2*/. i = 1; while ((i < k) and (b  n – 1)) { b = b 2 mod n; If (b = 1) Return False; /* n hợp số */ i = i + 1; } if (b (n –1)) Return False; /* n hợp số */ } 3. Return True; /* n là số nguyên tố */. 4. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 CHƢƠNG 2 - NGHIÊN CỨU CƠ CHẾ HOẠT ĐỘNG CỦA HỆ MẬT KHÓA CÔNG KHAI 2.1 GIỚI THIỆU VỀ HỆ MẬT VỚI KHÓA CÔNG KHAI Vào năm 1976, các nhà khoa học Whitfield Diffie, Martin Hellman và Ralph Merkle tại Đại học Stanford giới thiệu ý tƣởng về hệ thống mật mã khóa công khai, có thể khắc phục các nhƣợc điểm của phƣơng pháp mật mã khoá đối xứng. Các phƣơng pháp Diffie-Hellman của Martin Hellman và Whitfield Diffie đƣợc công bố. Năm 1977 nhóm tác giả Ronald Rivest, Adi Shamir và Leonard Adleman đã công bố phƣơng pháp RSA, phƣơng pháp mã hóa khóa công khai RSA hiện đƣợc sử dụng rất nhiều trong các ứng dụng mã hóa và bảo mật thông tin. RSA nhanh chóng trở thành chuẩn mã hóa khóa công khai trên toàn thế giới do tính an toàn và khả năng ứng dụng của nó. Độ an toàn của hệ thống mật mã mới này, không phải đƣợc đo bằng độ phức tạp của các thuật toán mã hóa, mà nó dựa vào một khám phá mới vô cùng quan trọng trong ngành khoa học máy tính, đó là lý thuyết độ phức tạp tính toán: Chủ yếu đề cập đến sự phân tích các thuật toán và đặc biệt là số các bƣớc tính toán cần thiết để phát hiện khóa bí mật. Từ đó xác định độ an toàn của bất kỳ hệ mật mã khóa công khai nào. Một hệ thống mật mã khóa công khai sử dụng hai loại khóa trong cùng một cặp khóa: Khoá công khai (public key) đƣợc công bố rộng rãi và sử dụng trong mã hóa thông tin, khóa riêng (private key) sử dụng để giải mã thông tin đã đƣợc mã hóa bằng khóa công khai. Các phƣơng pháp mã hóa này khai thác những ánh xạ f mà việc thực hiện ánh xạ ngƣợc f -1 rất khó so với việc thực hiện ánh xạ f. Chỉ khi biết đƣợc khóa riêng thì mới có thể thực hiện đƣợc ánh xạ f -1. 2.1.1 Các quan điểm cơ bản của hệ mật mã khoá công khai - Hệ mật mã khoá công khai dựa trên quan điểm hàm một chiều (one-way function) và khoá công khai, để biến đổi một bản rõ thành bản mã với thời gian tính Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 toán hợp lý. Nhƣng nếu muốn tính ngƣợc lại (inverse function) thì phải mất nhiều thời gian và khó thực hiện đƣợc. Vì vậy, các thám mã rất khó có thể tính toán để thu đƣợc bản rõ từ bản mã chặn đƣợc. - Một quan điểm khác dùng trong hệ mật mã khoá công khai, là thông tin “cửa sập” (trap door) mà hàm một chiều phải có. Thông tin bí mật (khoá riêng) chỉ đƣợc đƣa vào bởi ngƣời sở hữu cặp khóa. Khi có đƣợc thông tin “cửa sập” thì công việc giải mã sẽ trở nên dễ dàng. - Các hệ mật mã khóa công khai đƣợc xây dựng dựa trên những bài toán khó nhƣ: bài toán logarithm rời rạc trong trƣờng hữu hạn Zp (hệ ElGamal) và bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố (hệ RSA). 2.1.2 Hoạt động của hệ mật mã khóa công khai Đối với hệ thống mã hóa khóa công khai: Mỗi ngƣời sử dụng phải tạo riêng cho mình một cặp khóa. Trong đó, một khóa công khai (public key) cùng với thuật toán mã hóa E, đƣợc công bố rộng rãi tại thƣ mục dùng chung cho mọi ngƣời sử dụng. Còn lại là khóa riêng (private key) cùng với thuật toán giải mã D đƣợc giữ bí mật bởi ngƣời sử dụng. Nhƣ vậy, ngƣời A muốn gửi thông điệp R đến cho ngƣời B (Hình 2.1). Giả sử: Khóa công khai của B là: KB , Khóa riêng của B là: MB Khóa công khai của A là: KA , Khóa riêng của A là: MA Thuật toán mã hóa: E , thuật toán giải mã: D Ngƣời A tìm khóa công khai KB của ngƣời B trong thƣ mục dùng chung và tính C = E(KB, R), sau đó gửi bản mã C cho ngƣời B. Khi nhận bản mã C ngƣời B sẽ giải mã dựa vào khóa riêng MB của mình để tính R = D(MB, C). 2.1.3 Các mô hình ứng dụng của hệ mật mã khóa công khai. Thông qua từng lĩnh vực ứng dụng cụ thể mà ngƣời gửi sử dụng khóa bí mật của mình, khóa công khai của ngƣời nhận hoặc cả hai để hình thành một số các ứng dụng phù hợp nhƣ sau: - Tính mật: Ngƣời gửi A thực hiện mã hóa thông điệp R bằng khóa công khai KB của ngƣời nhận B: C = E(KB,R). Còn ngƣời nhận giải mã bằng khóa riêng MB Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 của mình: R = D(MB, C). Vậy, có duy nhất ngƣời B mới giải mã đƣợc thông điệp, điều này gọi là tính mật của hệ. - Tính xác thực: Ngƣời gửi A thực hiện mã hóa một thông điệp R bằng khóa riêng MA: C = E(MA,R). Ngƣời nhận B giải mã bằng khóa công khai KA của ngƣời gửi A: R = D(KA,C). Nhƣ vậy chỉ có duy nhất A là ngƣời có khóa riêng để mã hóa, cho nên thông điệp nhận đƣợc là của A, điều này gọi là tính xác thực của hệ. - Tính mật và xác thực: Ngƣời gửi A thực hiện mã hoá thông điệp hai lần, lần thứ nhất sử dụng khóa bí mật MA của mình E(MA,R), lần thứ hai sử dụng khóa công khai KB của ngƣời nhận B: C = E(KB,(E(MA,R))). Khi nhận bản mã, ngƣời nhận B cũng thực hiện giải mã hai lần, đầu tiên dùng khóa riêng MB của mình D(MB,C), sau đó dùng khóa công khai KA của ngƣời gửi A: R = D(KA,D(MB,C)). Nhƣ vậy chỉ ngƣời gửi mới có khóa riêng để mã hoá và cũng chỉ ngƣời nhận mới có khóa riêng để giải mã, đây chính là tính mật và tính xác thực của hệ. 2.1.4 Các yêu cầu của hệ mật mã khóa công khai - Dễ tính toán đối với các thành viên khi muốn tạo một cặp khóa (khóa công khai và khóa riêng). - Ngƣời gửi dễ tính toán khi biết khóa công khai và thông điệp R cần mã hoá thành một bản mã tƣơng ứng C = E(KB,R). - Ngƣời nhận dễ tính toán khi sử dụng khóa riêng để giải mã bản mã C, khôi phục lại thông điệp ban đầu: R = D(MB, C). - Đối với ngƣời thám mã, khi biết đƣợc khóa công khai KB, muốn xác định khóa bí mật MB hoặc biết đƣợc khóa công khai KB và bản mã C để khôi phục lại thông điệp R ban đầu: Điều này không thể tính toán nổi. 2.2 HỆ MẬT MÃ KHÓA CÔNG KHAI RSA Hệ mật RSA đƣợc xây dựng năm 1978 bởi ba tác giả R.L.Rivest, A.Shamir và L.Adleman. Hệ mật RSA đƣợc thiết kế làm việc trên trƣờng số ZN, dựa trên cơ sở độ khó giải của bài toán phân tích số nguyên N lớn thành các thừa số nguyên tố p và q khác nhau. 2.2.1 Bài toán phân tích số nguyên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 Bài toán 2.1 (Bài toán phân tích số nguyên): Cho một số nguyên dƣơng N, tìm các thừa số nguyên tố pi của N để N = p1 e1 . p2 e2 ...pk ek , với pi là những số nguyên tố phân biệt và ei  1 là các số nguyên (với i = 1,..., k). Ví dụ : Với N=12, ta có N=22.3 1 Bài toán này khó giải khi N là một số nguyên lớn, có nhiều thuật toán để giải bài toán này. Nhƣng hiện nay vẫn chƣa có thuật toán nào hiệu quả để phân tích số nguyên N có khoảng 232 chữ số thập phân (768-bits) trở lên. Bài toán 2.2 (Bài toán RSA): Cho số nguyên dƣơng N, 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 ch