Tài liệu Nghiên cứu hệ mật rsa với số mũ giải mã lớn và ứng dụng cho chữ ký số

1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- Tô Danh Dũng NGHIÊN CỨU HỆ MẬT RSA VỚI SỐ MŨ GIẢI MÃ LỚN VÀ ỨNG DỤNG CHO CHỮ KÝ SỐ Chuyên ngành: Truyền dữ liệu và mạng máy tính Mã số: 60.48.15 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013 2 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: TS. Nguyễn Khắc Lịch Phản biện 1: …………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông HÀ NỘI - 2013 1 MỞ ĐẦU 1. Lý do chọn đề tài. Trong mật mã vấn đề bảo mật luôn đi đôi với vấn đề xác thực thông tin, đặc biệt trong hệ thống mã hóa khóa công khai vấn đề xác thực là vô cùng quan trọng. Để giải quyết được vấn đề xác thực người ta đưa ra một cách vừa đơn giản vừa hiệu quả là sử dụng chữ ký số. Việc sử dụng chữ ký số ngày càng có ứng dụng nhiều trong thực tế, không chỉ ứng dụng trong nghành công nghệ thông tin, nghành mật mã mà còn được áp dụng trong một số lĩnh vực khác như trong lĩnh vực ngân hàng để xác thực người gửi, người nhận, lĩnh vực viễn thông để sử dụng các thẻ thông minh. RSA thường được sử dụng trong các ứng dụng mà vấn đề bảo mật được ưu tiên hàng đầu. Bên cạnh đó RSA cũng được các nhóm phân tích nhằm tìm ra các mức không an toàn của nó. Các phân tích này chủ yếu là minh họa cho các mối nguy hiểm của việc sử dụng RSA không đúng cách. Thật vậy an toàn khi sử dụng RSA là một nhiệm vụ không hề tầm thường. Một cách tấn công cổ điển đến RSA là chỉ ra rằng hệ mật không an toàn nếu d < n1/4 (d là số mũ giải mã). Trong nhữ năm gần đây các nhà nghiên cứu đã chỉ ra rằng hệ RSA sẽ không an toàn nếu số mũ giải mã có kích thước ngắn và trong tấn công Boneh-Durffe đã chỉ ra rằng hệ mật thực sự không an toàn nếu số mũ giải mã d < n 0,292. Vậy để RSA an toàn thì ta phải có số mũ giải mã d càng lớn càng tốt mặc dù quá tình giải mã sẽ chậm hơn. Làm thế nào để có được d lớn? ta biết trong RSA để mã hóa người ta sẽ chọn ngẫu nhiên p, q là hai số nguyên tố lớn phân biệt; xác định modulus n = p.q ; tính φ(n)= (p-1)(q1) rồi thông qua các tham số đó tính e ( thường là chọn e nhỏ để quá trình mã hóa đơn giản); sau đó tính d theo công thức de = 1 + k.φ(n)và thường e nhỏ thì d có được cũng nhỏ. Muốn tìm được d lớn người ta làm ngược lại đó là chọn e, tìm p,q thỏa mãn điều kiện đủ nào đó sao cho với cách này ta sẽ có được d có kích thước gần bằng modulus n. Luận văn sẽ nghiên cứu về hệ mật RSA với số mũ giải mã lớn và ứng dụng cho chữ ký số để chữ ký số an toàn và bảo mật hơn. 2. Mục đích nghiên cứu. Phân tích tính an toàn của hệ mật RSA. Đưa ra một giải pháp nhằm tăng tính an toàn cho chữ ký số RSA đó là : chọn số mũ giải mã lớn và ứng dụng vào chữ ký số. 2 3. Đối tượng và phạm vi nhiên cứu. - Hệ mật RSA là đối tượng nghiên cứu chính của đề tài nhằm phát hiện các phương pháp tấn công , bẻ gẫy RSA ; qua đó ứng dụng thử nghiệm trên chữ ký số RSA với thuật toán chọn số mũ giải mã lớn. - Phạm vi nghiên cứu: đề tài nghiên cứu cách ngăn ngừa một kiểu tấn công trong trường hợp sử dụng số mũ giải mã d nhỏ. Sau đó xây dựng và cài đặt thật toán thử nghiệm trên chữ ký số giúp tăng tính an toàn cho chứ ký số RSA. 4. Giả thiết khoa học. Cài đặt thuật toán thành công sẽ cho ta được số mũ giải mã lớn; điều này có thể chống lại các cách tấn công của M.Wiener[8] và Boneh Durfee[3] và làm tăng tính an toàn cho hệ mật RSA và chữ ký số RSA. 5. Phạm vi đề tài. - Nghiên cứu cơ chế hoạt động của hệ mật RSA. - Các cách tấn công bẻ gẫy RSA - Xây dựng, cài đặt thuật toán có số mũ giải mã lớn nhằm nâng cao an toàn cho chữ ký số RSA. 6. Phương pháp nghiên cứu. - Phân tích thuật toán mã hóa RSA. Tìm hiểu các cách tấn công RSA. Từ đó lựa chọn giải pháp nhằm tăng tính an toàn cho chữ ký số RSA. - Kết hợp với toán học và lý thuyết tính toán chỉ ra giải pháp lựa chọn là đúng đắn. - Thu thập các tài liệu, các bài báo trên tạp chí khoa học trong nước, nước ngoài, và các tài liệu trên mạng internet có liên quan đến nội dung nghiên cứu. - Tham khảo, vận dụng và kế thừa các thuật toán, mã đã có. 3 Các nội dung chính trình bày: Chương 1: TỔNG QUAN VỀ LÝ THUYẾT MẬT MÃ Ở chương này luận văn sẽ đi tìm hiểu về khái niệm mật mã, cơ sở toán học của mật mã. Chương 2: HỆ MẬT KHÓA CÔNG KHAI RSA Ở chương này luận văn sẽ tìm hiểu và nghiên cứu hệ mật RSA, các khả năng tấn công và bẻ gẫy RSA, thuật toán RSA với số mũ giải mã lớn. Chương 3: THỬ NGHIỆM CHỮ KÝ SỐ RSA VỚI SỐ MŨ GIẢI MÃ LỚN Trong chương này sẽ giới thiệu về chữ ký số và áp dụng lý thuyết đã tìm hiểu ở các chương trước để xây dựng chữ ký số RSA với số mũ giải mã lớn. KẾT LUẬN VÀ KIẾN NGHỊ Tổng kết các kết quả đã đạt được và các mong muốn, kiến nghị để phát triển hệ thống. 4 CHƯƠNG 1: TỔNG QUAN VỀ LÝ THUYẾT MẬT MÃ 1.1. Các khái niệm cơ bản. Trong lý thuyết mật mã có một số thuật ngữ cơ bản sau: Bản rõ (PlainText): là nội dung của thông điệp cần gửi đi yêu cầu được đảm bảo an toàn. Bản mã (CipherText): là thông điệp gửi đi được mã hóa. Mã hóa (Encryption): quá trình chuyển đổi thông tin từ bản rõ sang bản mã. Trong quá trình này thông tin trong bản rõ sẽ được ẩn đi và do đó bất kỹ một người nào đọc thông điệp này cũng không hiểu được trừ trường hợp người đó có thể giải mã (PlainText → CipherText) Giải mã (Decryption): là quá tình giải mã để lấy lại thông tin ban đầu, ngược với quá trình mã hóa (CipherText → PlainText). Trong luận văn này có sử dụng thêm các kí hiệu sau: A, B: Hai người muốn trao đổi thông tin Mm: Kẻ thù muốn lấy cắp thông tin Khái niệm hệ mật mã Một hệ mật là một bộ gồm 5 thành phần (P, C, K, E, D) với: P (PlainText): Tập hợp hữu hạn các bản rõ. C (CipherText): Tập hợp hữu hạn các bản mã. K (Key): Tập hợp các khóa. E: Tập các quy tắc mã hóa. D: Tập các quy tắc giải mã. Hệ mật hiện đại cần phải đáp ứng được những yêu cầu sau: - Tính bảo mật (Confidentiality): đảm bảo dữ liệu được truyền đi một cách an toàn và không bị lộ nếu như ai đó cố tình muốn có được thông điệp gốc ban đầu. Chỉ những người được phép mới có khả năng đọc được nội dung thông tin ban đầu. - Tính xác thực (Authentication): giúp cho người nhận thông điệp các định được chắc chắn thông điệp mà họ nhận là thông điệp gốc ban đầu. Kẻ giả mạo không thể giả dạng một người khác hay nói cách khác không thể mạo danh để gửi thông điệp. Người nhận có khả năng kiểm tra nguồn gốc thông điệp mà họ nhận được. 5 - Tính toàn vẹn (Integrity): người nhận thông điệp có thể kiểm tra thông điệp không bị thay đổi trong quá trình truyền đi. Kẻ giả mạo không thể có khả năng thay thế dữ liệu ban đầu bằng dữ liệu giả mạo. - Tính không thể chối bỏ (Non – repudation): người gửi, người nhận không thể chối bỏ sau khi đã gửi hoặc nhận thông điệp. 1.2. Phân loại các hệ mật mã. Công nghệ thông tin phát triển, việc sử dụng máy tính gia tăng cùng với tốc độ phát triển mạnh mẽ của Internet càng làm tăng nguy cơ bị đánh cắp các thông tin độc quyền. Với mối đe dọa đó có nhiều biện pháp để đối phó song mã hóa là một phương pháp chính để có thể bảo vệ các giá trị của thông tin điện tử. Có thể nói mã hóa là công cụ tự động, quan trọng nhất cho an ninh mạng và truyền thông. Có hai hình thức mã hóa được sử dụng phổ biến là mã hóa đối xứng (symmetric – key cryptography) và mã hóa bất đối xứng (asymmetric key cryptography). 1.2.1. Mã hóa đối xứng Là phương thức mã hóa mà trong đó cả người gửi và người nhận đều sử dụng chung một khóa để mã hóa và giải mã thông điệp hoặc, ít phổ biến hơn, người gửi và người nhận sử dụng các khóa khác nhau nhưng mối liên hệ giữa chúng dễ dàng tính toán được. 1.2.2. Mã hóa bất đối xứng Định nghĩa mã hóa bất đối xứng: là hệ mật mã bao gồm một tập hợp các phép biến đổi mã hóa {Ee} và một tập hợp các phép biến đổi giải mã {Dd} được gọi là mật mã khóa công khai hoặc mật mã bất đối xứng nếu với mỗi cặp khóa (e, d) trong đó khóa mã hóa e được gọi là khóa công khai (có giá trị mà ai cũng biết), khóa giải mã d được gọi là khóa riêng hay khóa bí mật. Hệ mật mã này phải đảm bảo an toàn để không có khả năng tính được d từ e. Nguyên tắc hoạt động: Người nhận B sinh ra cặp khóa gồm: khóa công khai Kp và khóa bí mật Kr. Sau đó B sẽ gửi Kp cho A và khóa này được công khai ai cũng có thể biết. A sẽ dùng Kp để mã hóa thông điệp và gửi thông điệp đã mã hóa cho B. Lúc này, B sẽ cùng Kr để giải mã thông điệp mà A gửi. 6 1.3. Một số khái niệm toán học. Trong phần này luận văn trình bày lại các lý thuyết và kết quả cơ bản nhất của lí thuyết số có liên quan đến mật mã. Ký hiệu: Z: Tập hợp các số nguyên. N: Tập hợp các số tự nhiên {0,1,2……}. 1.3.1. Ước số chung lớn nhất GCD() Ước số chung lớn nhất của các số nguyên dương a, b được kí hiệu GCD(a,b), là số nguyên lớn nhất mà cả a, b đều chia hết cho nó. Và gcd (a,0) = gcd(0,a) = a. gcd (a,b) = gcd( a , b ). Ví dụ: gcd (15,9) = 3 1.3.2. Số nguyên tố và nguyên tố cùng nhau Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Hệ mật mã thường sử dụng các số nguyên tố ít nhất là lớn hơn 10150. Hai số a và b được gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất của chúng bằng Ký hiệu: gcd (a, b) = 1. 1.3.3. Hàm Ф Euler Định nghĩa: Cho n ≥ 1, Ф (n)là số lượng các số nguyên nằm trong đoạn [1,n] mà nguyên tố cùng nhau với n. Hàm Ф được gọi là hàm Euler. 1.3.4. Thuật toán Euclid và Euclid mở rộng Thuật toán Euclid như sau: Input: 2 số nguyên không âm a và b với a ≥ b. Output: gcd (a, b). ------------1. While b ≠ 0 do r ← a mod b, a ← b, b ← r. 7 2. return (a). Thuật toán Euclid mở rộng Input: 2 số nguyên không âm a và ba với a ≥ b Output: gcd(a,b) và 2 số nguyên x, y thỏa mãn ax + by = d. -----------------1. If b=0 then d ← a, x ← 1, y ← 0. return (d, x, y). 2. x2 ← 1, x1 ← 0, y2 ← 0, y1 ← 1. 3. While b > 0 do 3.1 q ← ⎣a / b⎦ , r ← a- q.b, x ← x2 – q.x1, y ← y2 – q.y1. 3.2 a ← b, b ← r, x2 ← x1, x1 ← x, y2 ← y1, y1 ← y. 4. d ← a, x ← x2, y ← y2, return (d, x, y). Thuật toán Euclid mở rộng có độ phức tạp là O((lg n)2) phép toán bit. 1.3.5. Các phép toán cơ bản trong không gian Modulo Toán tử modulo còn được gọi là toán tử mod; a mod n là phần dư của a chia n được kí hiệu r = a mod n, nói cách khác a = q*n + r trong đó q là một số nguyên, r thuộc tập các số nguyên {0, 1, 2, ……, n-1}. Định nghĩa đồng dư: Cho a và b là các số nguyên, a được gọi là đồng dư với b theo modulo n, ký hiệu là a ≡ b (mod n) nếu a-b = k*n với k là số nguyên bất kỳ (hay a-b chia hết cho n). 1.3.6. Thặng dư bậc hai Định nghĩa 1: Cho a ∈ Zn*, a được gọi là thặng dư bậc hai modulo n nếu tồn tại một số x ∈ Zn* thỏa mãn x2 ≡ a (mod n). Nếu không tồn tại một số x như vậy thì a được gọi là không thặng dư bậc hai modulo n. Tập tất cả các giá trị thặng dư bậc hai modulo n được kí hiệu Qn và tập tất cả các giá trị không thặng dư bậc hai modulo n được kí hiệu Qn . 1.3.7. Các thuật toán trong Zn Thuật toán tính nghịch đảo nhân trong Zn [9]: Input: a ∈ Zn . Output: a-1 mod n; nếu a khả nghịch. 8 -------------1. Sử dụng thuật toán Euclid mở rộng để tìm x, y thỏa mãn d = ax + ny trong đó d = gcd (a,n). 2. Nếu d > 1 thì a-1 mod n không tồn tại. Ngược lại, return (x). Thuật toán bình phương và nhân để tích lũy thừa trong Zn[9] Input: a ∈ Zn và k nguyên 0 ≤ k < n; trong đó biểu diễn nhị phân của k gồm t bít có dạng k t = ∑k 2 t =0 i i 20 k 21 k 2t k và khi đó ak = (a ) 0 (a ) 1 ...(a ) t Output: ak mod n. -------------1. b ← 1. If k = 0 then return(b). 2. A ← a. 3. If k0 = 1 then b ← a. 4. For i: = 1 to t do A ← A2 mod n. If ki = 1 then b ← A . b mod n. 5. return(b). 1.4. Độ phức tạp tính toán. 1.4.1. Khái niệm cơ bản Định nghĩa 1: Kích thước đầu vào là số lượng bit cần thiết dùng để biểu diễn dữ liệu đầu vào. Định nghĩa 2: Thời gian thực hiện thuật toán trên dữ liệu đầu vào là số lượng các phép toán cơ bản hoặc “các bước” được thực hiện. 1.4.2. Kí hiệu tiệm cận Một số định nghĩa: (i) f(n)= O (g(n)) nếu tồn tại một hằng số c dương và một số nguyên dương n0 thỏa mãn 0 ≤ f(n) ≤ c.g(n)với mọi n ≥ n0. 9 (ii) Một thuật toán được gọi là có độ phức tạp đa thức, hoặc có thời gian đa thức, nếu số các phép tính cần thiết khi thực hiện thuật toán không vượt quá O(logkn), trong đó n là độ lớn cảu đầu vào, và k là số nguyên dương nào đó. Nói cách khác, nếu đầu vào là số d-bit thì thời gian thực hiện thuật toán là O(dk), tức là tương đương với một đa thức bậc k. (iii) Các thuật toán với thời gian O(nα) với α > 0 , được gọi là thuật toán với độ phức tạp mũ hoặc thời gian mũ. Cũng có thuật toán có độ phức tạp là trung gian giữa đa thức và mũ ta thường gọi là thuật toán dưới mũ. 10 CHƯƠNG 2: HỆ MẬT MÃ KHÓA CÔNG KHAI RSA 2.1. Hệ mật RSA. Độ an toàn của RSA dựa trên hai bài toán lớn: 1. Bài toán phân tích ra thừa số nguyên tố của các nguyên tố lớn ( The integer Factorization Problem (IFP)): “ Cho trước một nguyên tố n ∈ N, tìm số các nguyên tố Pj, j = 1, 2, …, r ∈ N, với P1 r < P2 <…< Pr thỏa mãn n = ∏p j =1 ej j , trong đó ej ≥ 1”. Bảng sau đây chỉ ra khoảng thời gian cần thiết để phân tích một số nguyên n ra thừa số nguyên tố bằng thuật toán tốt nhất hiện nay; ta xem máy tính được sử dụng tốc độ khoảng 1 triệu phép tính/giây được mô tả trong [9] như sau: Số chữ số thập phân Số phép tính bit Thời gian 50 1,4.1010 3,9 giờ 75 9,0.1012 104 ngày 100 2,3.1015 74 năm 200 1,2.1023 3,8.109 năm 300 1,5.1029 4,9.1015 năm 500 1,3.1039 4,2.1025 năm Bảng 2.1: Bảng thời gian để phân tích số n ra thừa số nguyên tố 2 . Bài toán RSA: cho số nguyên dương n, n = p*q với p, q là các số nguyên tố phân biệt, cho trước một số nguyên c và e sao cho số nguyên e thỏa mãn gcd(e, (p - 1)*(q 1)) = 1 tìm một số nguyên m sao cho me ≡ c ( mod n). 2.1.1. Tạo khóa cho hệ mật RSA Mỗi người sử dụng đều có thể tạo ra một khóa RSA công khai và một khóa bí mật tương ứng theo các bước sau: 1. Tạo 2 số nguyên tố lớn p và q ngẫu nhiên, có kích thước như nhau. 2. Tính n = p*q và φ = (p-1)*(q-1). 3. Chọn ngẫu nhiên một nguyên tố e, 1< e < φ, thỏa mãn gcd(e,φ) = 1. 11 4. Sử dụng thuật toán Euclid mở rộng để tính số nguyên d duy nhất, 1 < d < φ thỏa mãn ed ≡ 1(mod φ). 5. Khi đó căp khóa công khai là(n,e) và khóa bí mật là d Số nguyên e và d được tạo ra trong thuật toán trên được gọi là số mũ mã hóa và số mũ giải mã còn n được gọi là modulus của RSA. 2.1.2. Quá trình mã hóa RSA Bây giờ, giả sử A là người muốn gửi một thông điệp m cho B và B là người phải giải mã. Sử dụng RSA, người sử dụng A cần làm theo các bước sau: 1. Xác thực khóa công khai(n,e). 2. Biểu diễn thông điệp như là một số nguyên m trong đoạn[0, n-1]. 3. Tính c = me mod n(sử dụng thuật toán bình phương và nhân liên tiếp để tính lũy thừa modulus n). 4. Gửi bản mã hóa c đến B 2.1.3. Quá trình giải mã RSA Để có được bản rõ m từ c, B làm như sau: Sử dụng khóa bí mật d để khôi phục m = cd mod n. Ví dụ : Ở đây ta sử dụng thông điệp A gửi cho B là một số; chúng ta giả thiết rằng giữa A và B có một cách để chuyển dỗi giữa văn bản và số. Các bước sẽ thực hiện như sau: 1. B sẽ chọn hai số nguyên tố. chúng ta giả sử p = 23 và q = 41. Thực tế B cần phải chọn hai số lớn hơn rất nhiều. 2. B sẽ tính ra tích của p*q. Ta có p*q = 23*41 = 943 vậy n = 943; giá trị này sẽ được chuyển đến A. 3. B sẽ chọn một số nguyên e là nguyên tố cùng nhau với (p-1)*(q-1). Trường hợp này ta có (p-1)*(q-1) = 22.40 = 880, e chọn là 7, e chính là thành phần khóa công khai. 4. A đã có (n,e) =(943,7) do b gửi đến. A sẽ sử dụng cặp khóa này để mã hóa thông điệp m và gửi cho B. Ta giả sử thông điệp m = 35. 5. A tính giá trị của c: c = me (mod n) = 375 (mod 943) = 545. Giá trị 545 là bản mã và được A gửi cho B. 6. B muốn giải mã thông điệp 545 thì B phải tìm số d thỏa mãn e*d = 1(mod (p 1)*(q -1)). Trường hợp này, 7d = 1 (mod 880); d = 503. 12 7. Sau khi có d, B cần tính cd(mod n) = 545503(mod 943). Sử dụng thuật toán bình phương và nhân liên tiếp để tính lũy thừa modulus n (1.3.7) vào tính 545503 (mod 943) Ta có : k = 50310 = 11111101112. K được viết lại là 11101111112 Bảng 2.2: Minh họa ví dụ giải mã RSA i 0 1 2 3 4 5 6 7 8 9 ki 1 1 1 0 1 1 1 1 1 1 A 545 545 923 400 633 857 795 215 18 324 545 416 432 568 806 721 719 35 B Vậy B sẽ giải mã thông điệp là m = 35. 2.2. Các khả năng tấn công lên hệ mật RSA Hệ mật RSA là hệ mật phổ biến nhất hiện nay, nó được triển khai và ứng dụng trong nhiều hệ thống thương mại nhằm cung cấp tính bảo mật cũng như xác thực của dữ liệu. Từ khi được công bố, RSA đã được phân tích tính an toàn bởi nhiều nhà khoa học. Và đã có một số cuộc tấn công lên hệ mật RSA xong chúng chủ yếu là minh họa cho việc sử dụng RSA không đúng cách. Vấn đề thám mã đối với RSA hiện nay đang được các nhà khoa học tập trung vào các kẽ hở của RSA và được chia làm 4 loại: tấn công cơ bản, tấn công số mũ công khai hoặc số mũ bí mật nhỏ và tấn công cài đặt. 2.2.1. Tấn công cơ bản 2.2.1.1. Modul chung Để tránh việc phân tích modul n= p*q khác nhau cho các người dùng khác nhau, chúng ta lấy n chung cho tất cả. Cùng một n được sử dung cho tất cả người sử dụng. Trung tâm xác thực có thể cung cấp cho người sử dụng i với một cặp ei, di và người sử dụng i có một khóa công khai là (n,ei) và khóa riêng là (n,di). 2.2.1.2. Mù (Blinding) Marvin chọn ngẫu nhiên một số r ∈ Z*n và đặt m’ = re m mod n. Sau đó anh ta nhờ Bob ký lên m’. Bob có thể cung cấp chứ ký của mình là s’ lên m’. Nhưng từ cách tính s’= (m’)d mod n, Marvin có thể đơn giản tính s = s’/r mod n để có được chữ ký của Bob là s trên m. 13 se = (s’)e/re = (m’)ed/re = m’/re = m/(mod n) 2.2.2. Tấn công với số mũ bí mật nhỏ ( Tấn công Wiener) Ta thấy rằng để giảm thời gian giải mã một trong những cách được dùng đó là sử dụng giá trị d nhỏ hơn là chọn giá tri d ngẫu nhiên. Do thời gian tính số mũ modulus mất log2d, nên với d nhỏ có thể cải thiện hiệu suất đáng kể. M. Wiener đã chỉ ra rằng với d nhỏ hệ mật có thể bị phá vỡ. Định lý 1 (M. Wiener)[8]: Cho n = p*q với q < p< 2q. Giả sử d < 1/3N1/4. Cho trước (n,e) với ed = 1 mod ϕ (n), Marvin có thể tìm được d hiệu quả. Kiểu tấn công này rất hiệu quả và thiết thực, nó đáng quan tâm khi mà khóa bí mật d được chọn nhỏ hơn so với giá trị n. Ví dụ, nếu n có kích thước là 1024 bit thì d được chọn ít nhất là 256 bit thì mới có thể tránh được tấn công Wiener. Trong tài liệu [8] Wiener đã chỉ ra kĩ thuật để tránh được tấn công loại này như sau: Kỹ thuật thứ nhất: chọn e lớn Thay vì rút gọn e trong ϕ (n), ta sử dụng (n,e’) cho khóa công khai thỏa mãn e’ = e + t. ϕ (n)trong đó số t lớn. Rõ ràng có thể sử dụng e’ thay thế e để mã hóa thông điệp. Tuy nhiên, khi số e có giá trị lớn, theo chứng minh ở trên thì số k không thể nhỏ hơn. Một tính toán đơn giản chỉ ra rằng nếu e’ > n1.5 [5] thì sẽ không có vấn đề gì xẩy ra mặc dù số d nhỏ và tấn công ở trên không thể thực hiện được. Nhưng điều bất tiện là số e lớn sẽ là tăng thời gian mã hóa. Kỹ thuật thứ hai: sử dụng định lý số dư Trung Hoa ( Chinese Remainder Theorem – (CRT)) Một cách tiếp cận khác là sử dụng định lý đồng dư trung hoa (Chinese Remainder Theorem - CRT). Ta chọn một số d sao cho cả dp = d mod (p - 1) và dp =d mod (q - 1) đều nhỏ 128 bits. Mặt khác ta không thể biết được điều gì xẩy ra đối với vấn đề an ninh này. Chúng ta chỉ biết thông qua tấn công hữu hiệu của Wiener. Định lý 1 gần đây đã được cải thiện bởi Boneh và Durfee [3], họ chỉ ra rằng số với d < n0.292, kẻ tấn công có thể tính được d từ (n,e). Kết quả này chỉ ra ranh giới của Wiener là không rõ ràng. Nó có vẻ như là d< n0.5, đây là một bài toán mở. 14 2.2.3. Tấn công với số mũ công khai nhỏ Người sử dụng hệ mật RSA muốn giảm thời gian mã hóa hoặc chứng thực chữ ký họ thường sử dụng số mũ công khai e nhỏ, thông thường số mũ công khai chọn là 3 hoặc 216 + 1 = 65537. Khi giá trị 216 + 1 được chọn việc chứng thực chữ kí yêu cầu 17 phép nhân và nó có thể lên đến 1000 nếu giá trị e ngẫu nhiên được sử dụng (e < ϕ (n)). Và số mũ công khai nhỏ thì bản rõ m là rất ngắn, khi đó hàm RSA dễ dàng tính được nghịch đảo. Không giống tấn công Wiener, tấn công với e nhỏ sẽ làm cho RSA bị sập hoàn toàn. Sau đây là một vài minh họa về tấn công kiểu này. 2.2.3.1. Tấn công quảng bá của Hastad Định lý 2 (Hastad)[2]: Cho n1, . . , nk là những số nguyên tố và tập nmin = mini(ni) từng đôi một. Với gi ∈ ZNi[x], k là đa thức có giá trị nhỏ nhất là d. Tồn tại m < nmin thỏa mãn: gi(m) = m mod ni với tất cả i = 1,…,k. Giả thiết rằng k > d, có thể tìm m khi cho (ni,gi(x))ki =1. Định lý chỉ ra rằng một hệ thống đồng biến với các đa thức nguyên tố hỗn hợp có thể giải quyết hiệu quả, giả thiết rằng các hàm được cung cấp đầy đủ. Bằng cách cài đặt gi = fiei – ci mod ni, chúng ta thấy rằng Marvin có thể tìm được M từ bản mã được cho với số thành viên ít nhất là d, khi đó d là giá trị lơn nhất của eideg(fi) với i = 1,…,k. Chúng ta lưu ý rằng để chống lại tấn công broadcast ở trên chúng ta sử dụng một cặp số ngẫu nhiên thay vì gắn cứng vào một giá trị. 2.2.3.2. Tấn công các thông điệp có quan hệ tuyến tính với nhau (Franklin Reiter Related Message Attack ) Hệ quả (FR): Giả sử rằng với e =3 và (n,e) là một khóa công khai của RSA. Cho m1 ≠ m2 ∈ Z*n thỏa mãn m1 = f(m2) mod n trong đó f = ax + b ∈ Z*n là đa thức tuyến tính với b ≠ 0. Khi đó cho trước (n, e, c1, c2, f), Marvin có thể tìm được m1, m2 với thời gian là đa thức bậc hai log n. 2.2.3.3. Tấn công với khóa để lộ một phần (Partial Key Exposure Attack) Định lý 3: cho n = p*q là modulus RSA n-bit, với e ≥ 1, d ≤ ϕ(n) thỏa mãn ed ≡ 1 mod ϕ(n). Tồn tại một thuật toán mà cho trước ít nhất n/4 bit có nghĩa nhỏ nhất của d, kẻ tấn công có thể khôi phục được toàn bộ d trong thời gian đa thức bậc n và e. 15 2.2.4. Tấn công cài đặt 2.2.4.1. Tấn công dựa trên thời gian Vào năm 1996, Kocher đã mô tả một kiểu tấn công mới lên RSA đó là kẻ thù có thể xác định khóa bí mật bằng cách theo dõi thời gian máy tính giải mã. Tấn công thông minh của Kocher cho thấy rằng bằng phương pháp lựa chọn thời gian chính xác để giải mã (hoặc ký số) RSA của smartcard, Marvin có thể nhanh chóng tìm ra thành phần giải mã riêng d. Giải pháp khắc phục: 1) Đơn giản nhất là tăng độ trễ nhất định để quá trình mũ hóa luôn mất một thời gian nhất định. 2) Rivest đưa ra dựa trên cơ chế bịt các kẽ hở (blinding). 2.2.4.2. Tấn công dựa trên các lỗi ngẫu nhiên Quá trình cài đặt giải mã và ký số RSA thường sử dụng định lý đồng dư trung hoa ( Chinese Remainder Theorem) nhằm cải thiện tốc độ tính toán md mod n. Boneh, DeMillo, và Lipton [10] đã quan sát và thấy rằng có một lỗi nguy hiểm khi sử dụng phương pháp CRT. Vấn đề là khi sinh chữ ký mà máy tính của Bob hoạt động không đều là nguyên nhân gây nên lỗi tính toán. Hay nói cách khác trong khi copy giữa các thanh ghi, một bit của dòng bít bị thất lạc. (Sự hoạt động không đều nguyên nhân có thể do xung đột điện từ hoặc cũng có thể do sâu phần cứng, các lỗi này đã sớm được tìm thầy trong các phiên bản của chíp Pentium). Được cung cấp một chữ ký lỗi, kẻ tấn công như Marvin có thể dẽ dàng phân tích thành nhân tử modul N. 2.3. Hệ mật RSA với số mũ giải mã lớn. Nếu làm theo các bước của thuật toán RSA : - Chọn 2 số nguyên tố lớn phân biệt p, q. Tính n = p*q và ϕ(n)= (p -1)*(q - 1). - Chọn e > 2 sao cho gcd(ϕ(n),e ) = 1 ; e thường được chọn nhỏ để quá trình mã hóa nhanh. - d được xác định là duy nhất thỏa mãn e*d = 1 mod e(ϕ(n)). Thì ta không hy vọng là có được số mũ giải mã d lớn. Do đó, trong [2], nhóm tác giả Hernández Encinas, J.Munoz MasQué và A.Queiruga Dios đã đề xuất thuật toán để có được số mũ giải mã d lớn, có kích thước gần bằng modunlus n bằng cách : số mũ công khai e 16 được chọn trước ; Chọn hai số nguyên tố p, q thỏa mãn một điều kiện đủ nào đó đảm bảo d có kích thước gần bằng kích thước n, với cách này ta đủ điều kiện để tránh được tấn công trên. 2.3.1. Thuật toán có số mũ giải mã d lớn Thuật toán này đã được các tác giả Vũ Huy Hoàng và Hồ Thuần trong bài báo cáo [1] đưa ra như sau: Bước 1: chọn số mũ mã hóa e ≥ 3, là số nguyên dương lẻ. Bước 2: Chọn ngẫu nhiên r ∈ T(e) với T(e) = { r ∈ Z*e |(r -1) ∈ Z*e}. Tạo sinh một số nguyên tố ngẫu nhiên p đủ lớn sao cho p = cp.e + rp , (tồn tại theo định lý Dirichlet) . Bước 3: Tính một số nguyên tố lớn q = r(r -1)-1(mod e) + k.e; với một k nào đó thuộc N. Bước 4: Tính n = p*q, ϕ(n)= (p - 1)*(q - 1) và kiểm tra điều kiện 1 < e < ϕ(n), và gcd(e, ϕ(n)) = 1. Nếu thỏa mãn chuyển sang Bước 5 ngược lại quay về Bước 2. Bước 5: Tính trực tiếp số mũ giải mã d theo công thức d = ϕ ( n ) − ϕ (n) − 1 e , là nghịch đảo nhân của e. ∈ Z*e |(r -1) ∈ ∈ Z*e |(r(r -1)) ∈ Trong thuật toán này có đưa ra tập T(e) được định nghĩa T(e) = { r Z*e}. T(e) ở đây chính là một cách định nghĩa khác của tập S(e) = { r Z*e} điều này đã được chứng minh trong [1]. 17 Sau đây là kết quả demo với Input là giá trị cần mã hóa; kết quả Ouput trên màn hình: Hình 2.1 : Thuật toán có số mũ giải mã d lớn (e nhỏ) Hình 2.2 : Thuật toán có số mũ giải mã d lớn (e lớn) 2.3.2. Đánh giá thuật toán số mũ giải mã d lớn Đối với thuật toán RSA thông thường, xác suất cho việc chọn ngẫu nhiên d lớn là khá cao, nhưng khi đó xác suất có giá trị e tương ứng lớn cũng khá cao. Trong thực tế, người sử dụng luôn muốn chọn giá trị e nhỏ(một giá trị được xác định trước) ví dụ là 3 hoặc 216 + 1 để cải thiện nâng cao hiệu quả của quá trình mã hóa. Điều thú vị đối với thuật toán trình bày ở trên là số mũ mã hóa e được chọn tùy ý nhưng ta luôn có giá trị d tương ứng là lớn(có kích thước bằng kích thước modulus n ). Và khi giá trị e được chọn thì việc chọn p 18 và q chỉ cần thỏa mãn: rp, rq thuộc T(e) và rq = rp/( rp – 1) trong đó rp, rq là phần dư tương ứng của p và q khi chia cho e. Cuối cùng, thuật toán trên, việc chọn rp, rq thuộc T(e) không làm tăng thời gian của việc sinh khóa.