Đề tài Tìm hiểu thuật toán MD5 và ứng dụng trong chữ ký điện tử

MỤC LỤC Lời cảm ơn Lời cam đoan PHẦN I: GIỚI THIỆU VỀ ĐỀ TÀI 5 1.1.Mục đích 5 1.2 Đối tượng nghiên cứu 5 1.2 Phạm vi nghiện cứu 5 1.4 Ý nghĩa đề tài 5 PHẦN II: NỘI DUNG 6 CHƯƠNG 1 :TỔNG QUAN VỀ MẬT MÃ HÓA 6 2.1.1 Khái niệm về mã hóa 6 2.1.2 Các thuật toán mã hóa 7 2.1.2.1 Mã hóa đối xứng 7 2.1.2.2 Mã hoá bất đối xứng 8 2.1.4 Phương pháp RSA 9 2.1.4.1 Khái niệm hệ mật mã RSA 9 2.1.4.2. Độ an toàn của hệ RSA 11 2.1.4.3. Một số tính chất của hệ RSA 12 2.1.4.4 Một số phương pháp tấn công giải thuật RSA 13 CHƯƠNG 2 CHỮ KÝ ĐIỆN TỬ 15 2.2.1Giới thiệu 15 2.2.2 Khái niệm về chữ ký điện tử 15 2.2.3 Thuật toán chữ ký điện tử 17 2.2.4 Chứng nhận chữ ký điện tử 19 2.2.5 Chuẩn chữ ký điện tử (Digital Signature Standard) 19 2.2.6 Giải pháp ứng dụng chữ ký điện tử 22 2.2.6.1 Quá trình ký và gửi các tệp văn bản 22 2.2.6.2 Quá trình nhận các tệp văn bản 23 2.2.7 Vận dụng vào hệ thống 24 2.2.8 Kết luận 25 CHƯƠNG 3 : TỔNG QUAN VỀ HÀM BĂM VÀ THUẬT TOÁN HÀM BĂM MD5 26 2.3.1 Đăt vấn đề 26 2.3.2 giới thiệu về hàm băm mật mã 26 2.3.2.1 Tính chất 27 2.3.2.2 Ứng dụng 28 2.3.3 Hàm băm dựa trên mã khối 29 2.3.4 Cấu trúc Merkle-Damgård 29 2.3.5 Birthday attack 30 Hàm băm mật mã 31 Cấu trúc của hàm băm 32 2.3.8 Tính an toàn của hàm băm đối với hiện tượng đụng độ 32 2.3.9 Tính một chiều 33 2.3.10. Sử dụng cho các nguyên thủy mật mã khác 33 2.3.11 Ghép các hàm băm mật mã 342.3.12 Thuật toán băm mật mã 34 2.3.13 Phương pháp Secure Hash Standard (SHS) 35 2.3.14 Một số hàm băm nổi tiếng 35 2.3.15 Hàm băm MD5 35 2.3.15.1 Giới thiệu 35 2.3.15.2 Khái niệm 36 2.3.15.3 Ứng dụng 36 2.3.15.4 Thuật giải 36 2.3.16 MD5 (Message Digest) 37 2.3.16.1 Mô tả 37 2.3.16.2 Cách thực hiện 40 2.3.17 Sự khác nhau giữa MD4 và MD5 42 CHƯƠNG 4: XÂY DỰNG CHƯƠNG TRÌNH MÔ PHỎNG THUẬT TOÁN MD5 43 2.4.1 Nhiệm vụ của chương trình 43 2.4.2 Thuật toán MD5 và sơ đồ khối 43 2.4.2.1 Thuật toán 43 2.4.2.2 Sơ đồ khối thuật toán MD5 46 2.4.3 Kết quả chương trình mô phỏng thuật toán băm MD5 49 2.4.3.1 Giao diện chương trình mô phỏng .49 2.4.3.2 Các bước thực hiện chương trình 49 2.4.3.3 Kết quả thực nghiệm 50 PHẦN III: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 53 Danh mục tài liệu tham khảo .54 DANH MỤC HÌNH VẼ: Hình 1.1 Mô hình hệ thống mã hóa quy ước 7 Hình 1.2 Nguyên lý của hệ thống mã hoá đối xứng 7 Hình 1.3 Kênh nguyên lý trong hệ thống mã hoá đối xứng 8 Hình 1.4 Nguyên lý cơ bản của mã hoá khoá công khai và thuật toán RSA 9 Hình 1.5 Sơ đồ các bước thực hiện mã hoá theo thuật toán RSA 11 Hình 2.1 Kiểm tra chữ ký điện tử 17 Hình 2.2 Thủ tục ký và kiểm tra chữ ký 19 Hình 2.3 Sơ đồ mô tả quá trình ký và gửi các tệp văn bản 24 Hình 2.4 Sơ đồ mô tả quá trình nhận các tệp văn bản 25 Hình 3.1 Cấu trúc băm Merkle-Damgård .30 Hình 3.2 Sơ đồ vòng lặp chính của MD5 38 Hình 3.3 Sơ đồ 1 vòng lặp của MD5 39 LỜI MỞ ĐẦU Ngày nay, các ứng dụng Công nghệ thông tin đã và đang ngày càng phổ biến rộng rãi đã ảnh hưởng rất lớn đến diện mạo của đời sống, kinh tế, xã hội. Mọi công việc hàng ngày của chúng ta đều có thể thực hiện được từ xa với sự hổ trợ của máy vi tính và mạng internet (từ việc học tập, giao dịch,… đến việc gửi thư). Tất cả thông tin liên quan đến những công việc này đều do máy vi tính quản lý và truyền đi trên hệ thống mạng. Đối với những thông tin bình thường thì không có ai chú ý đến, nhưng đối với những thông tin mang tính chất sống còn đối với một số cá nhân (hay tổ chức) thì vấn đề bảo mật thật sự rất quan trọng, vấn đề khó khăn đặt ra là làm sao giữ được thông tin bí mật và giữ cho đến đúng được địa chỉ cần đến. Nhiều tổ chức, cá nhân đã tìm kiếm và đưa ra nhiều giải pháp bảo mật phương pháp mã hóa khóa công khai được xem là phương pháp có tính an toàn khá cao. Như vậy việc đảm bảo an toàn thông tin, tránh mọi nguy cơ bị thay đổi, sao chép hoặc mất mát dữ liệu trong các ứng dụng trên mạng luôn là vấn đề bức xúc, được nhiều người quan tâm. Trong bài báo cáo này, em trình bày những vấn đề liên quan về mã hóa thông tin, thuật toán băm MD5, thuật toán mã hóa RSA và chữ ký điện tử. Từ đó, ứng dụng thuật toán MD5 và RSA để phân tích quá trình hoạt động của chữ ký điện tử. Trên cở sở đó, em xin được đề ra giải pháp ứng dụng chữ ký điện tử trên cơ sở kết hợp giữa thuật toán băm MD5 và thuật toán mã hóa RSA trong quá trình gửi và nhận các văn bản. PHẦN I GIỚI THIỆU ĐỀ TÀI 1.1 MỤC ĐÍCH Tìm hiểu chung về kỹ thuật nhận thực (chữ ký điện tử) Chữ ký điện tử không được sử dụng nhằm bảo mật thông tin mà nhằm bảo vệ thông tin không bị người khác cố tình thay đổi để tạo ra thông tin sai lệch. Nói cách khác, chữ ký điện tử giúp xác định được người đã tạo ra hay chịu trách nhiệm đối với một thông điệp. Tìm hiểu hàm băm, đi sâu vào thuật toán MD5 Hàm băm (Hash Function): Cho đầu vào là một thông báo có kích thước thay đổi, đầu ra là một mã băm có kích thước cố định. Giải thuật băm MD5 (Message Digest 5): được sử dụng để kiểm tra tính toàn vẹn của khối dữ liệu lớn. Thuật toán nhận đầu vào là một đoạn tin có chiều dài bất kỳ, băm nó thành các khối 512 bit và tạo đầu ra là một đoạn tin 128 bit. Xây dựng chương trình mô phỏng hàm băm MD5 Đưa ra kết quả chương trình mô phỏng và các kết quả thu được đúng với các tài liệu tiêu chuẩn về thuật toán MD5 ĐỐI TƯỢNG NGHIÊN CỨU - các phương pháp mật mã hóa - Chữ ký điện tử và ứng dụng - Thuật toán RSA - Các thuật toán hàm băm 1.3 PHẠM VI NGHIÊN CỨU Bài báo cáo này tập trung nghiên cứu các thuật toán băm MD5 và ứng dụng hàm băm trong chữ ký điện tử 1.4 Ý NGHĨA ĐỀ TÀI Chữ ký điện tử là lĩnh vực được sử dụng rộng rải trong thực tế, nhận thực các bản tin, file văn bản trong vấn đề truyền thông tin trên mạng, xây dụng các giải pháp về giao dịch điện tử và chính phủ điện tử. Nghiên cứu về chữ ký điện tử và tìm hiểu những lĩnh vực ứng dụng của nó có ý nghĩa rất quan trọng trong thực tế PHẦN II NỘI DUNG CHƯƠNG 1 TỔNG QUAN VỀ MẬT MÃ HÓA 2.1.1 KHÁI NIỆM VỀ MÃ HÓA Mã hoá là một tiến trình biến đổi thông tin, sử dụng các thuật toán nhằm mục đích không cho người khác có thể nắm bắt được nếu thiếu một vốn thông số nhất định (key) để dịch ngược. Đi kèm với mã hoá là giải mã. Có rất nhiều loại thuật toán mã hoá cho dữ liệu máy tính, chúng được gọi tên theo thuật toán và có thể so sánh trực tiếp với nhau, ví dụ mã hoá 128-bit, Triple-DES, 2048-bit RSA. Trong cùng một loại, dĩ nhiên một phép mã hoá 2048-bit RSA sẽ mạnh mẽ hơn phép mã hoá 1024-bit RSA.Nhưng như vậy không có nghĩa là một phép mã hoá với độ dài dãy bit lớn được xem là an toàn. Thử liên tưởng đến ngôi biệt thự của bạn, với chiếc cổng được khoá bằng ổ khoá 4 chân, mỗi chân như vậy có thể nằm trong 10 vị trí, ổ khoá chỉ mở được khi 4 chân được sắp theo mã khoá của chủ nhà, và để vượt qua, 1 tên trộm cần phải dùng tối đa 10.000 phép thử (brute-force attack). Nhưng nếu tăng ổ khoá lên 10 chân, sẽ tạo nên 10 triệu khe cắm khoá hợp lệ, thì không ai đủ sự thông minh (hay sự ngu dốt) để mở chiếc khoá bằng cách tấn công thuật toán này. Họ có thể phá cửa sổ, hay thậm chí là phá chiếc cổng, giả danh chính quyền, thợ nước… để đột nhập vào căn nhà của bạn. Một ổ khoá tốt không thể chống lại những kiểu tấn công như thế được. Điều đó cho thấy một thuật toán mã hoá cực mạnh sẽ chỉ hữu ít nếu được sử dụng ở đúng những nơi cần thiết, không phải lúc nào cũng là tối ưu. Cái cần bảo vệ ở trên chính là ngôi nhà của bạn chứ không phải là đặt một hàng rào bẫy và hi vọng kẻ trộm sẽ dính vào cái bẫy đó. Với sự phát triển mạnh mẽ của mình, hầu hết các kênh thông tin đều lấy Internet làm nền tảng để phát triển. Điều tất yếu sẽ nảy sinh là vấn đề An toàn thông tin, một ngày nào đó, bạn bỗng nhận ra rằng, thông tin của bạn đang bị theo dõi. Để vừa đảm bảo thông tin luôn kết nối, vừa đảm bảo yếu tố bảo mật của thông tin thì phương pháp tốt nhất là mã hoá thông tin. Ngày nay việc mã hoá đã trở nên phổ cập, các quốc gia hay là các công ty lớn đều có chính sách phát triển công cụ mã hoá riêng biệt để bảo vệ cho chính thông tin của họ. Trên thế giới hiện có rất nhiều các loại thuật toán, trong khuôn khổ bài báo cáo, chúng ta chỉ tìm hiểu về các thuật toán được ứng dụng phổ biển trong Internet. Hình 1.1 Mô hình hệ thống mã hóa quy ước Mật mã hóa được sử dụng phổ biến để đảm bảo an toàn cho thông tin liên lạc. Các thuộc tính được yêu cầu là: Bí mật: Chỉ có người nhận đã xác thực có thể lấy ra được nội dung của thông tin chứa đựng trong dạng đã mật mã hóa của nó. Nói khác đi, nó không thể cho phép thu lượm được bất kỳ thông tin đáng kể nào về nội dung của thông điệp. Nguyên vẹn: Người nhận cần có khả năng xác định được thông tin có bị thay đổi trong quá trình truyền thông hay không. Xác thực: Người nhận cần có khả năng xác định người gửi và kiểm tra xem người gửi đó có thực sự gửi thông tin đi hay không. 2.1.2 CÁC THUẬT TOÁN MÃ HÓA 2.1.2.1 Mã hóa đối xứng
Hình 1.2: Nguyên lý của hệ thống mã hoá đối xứng. Nguyên lý cơ bản của hệ thống mã hoá khoá đối xứng được chỉ ra trong (hình 1.2) Có thể thấy rằng bản chất của mã hoá đối xứng là cả phía thu và phía phát đều sử dụng cùng một khoá bí mật (SK), và thuật toán ở cả hai phía cũng đều giống nhau. Mã hoá đối xứng như trên dựa vào việc phân phối khoá một cách bảo mật giữa cả hai phía. Nhưng thực tế là khoá chung đó lại phân phối tới tất cả mọi người trong mạng, và vấn đề “kênh bảo mật” đã làm đau đầu những nhà quản trị mạng. Điều nguy hiểm nhất là bất cứ ai chiếm được khoá trong quá trình phân phối cũng có toàn quyền truy nhập tới dữ liệu do khoá đó bảo vệ. Do đó, quá trình phân phối khoá phải trên “kênh bảo mật”, bất kể là kênh logic hay kênh vật lý (hình 1.4).
Hình 1.3: Kênh nguyên lý trong hệ thống mã hoá đối xứng. 2.1.2.2 Mã hoá bất đối xứng Ngược lại với mã hoá đối xứng, thuật toán bất đối xứng hoạt động theo ít nhất là hai khoá, hay chính xác hơn là một cặp khoá (hình 1.2). Khoá sử dụng được biết đến như là khoá bí mật và khoá công khai và do đó có khái niệm mã hoá khoá công khai. Mỗi khoá được sử dụng để mã hoá hay giải mã, nhưng khác với thuật toán đối xứng, giá trị của khoá ở mỗi phía là khác nhau. Trong hệ thống RSA, dữ liệu được mã hoá bằng khoá bí mật (KXu) và chỉ có thể giải mã được bằng khoá công khai của cặp khoá đó. Cặp khoá này được tạo ra cùng nhau và do đó có liên quan trực tiếp với nhau. Mặc dù có quan hệ với nhau nhưng nếu biết hay truy nhập được khoá công khai thì cũng không thể tính toán được giá trị của khoá bí mật. Do đó, công khai khoá mã cũng không làm ảnh hưởng tới tính bảo mật của hệ thống, nó cũng chỉ như một địa chỉ thư tín còn khoá bí mật vẫn luôn được giữ kín. Bản chất của mã hoá khoá công khai RSA là bất cứ bản tin mật mã nào đều có thể được nhận thực nếu như nó được mã hoá bằng khoá bí mật còn giải mã bằng khoá công khai. Từ đó, phía thu còn xác định được cả nguồn gốc của bản tin. Bất cứ người nào giữ khoá công khai đều có thể nghe trộm bản tin mật mã bằng cách tính toán với kho bí mật, không chỉ đảm bảo tính tin cậy của bản tin (trong một nhóm) mà còn được nhận thực, hay còn gọi là không thể từ chối, ví dụ như người gửi không thể từ chối rằng chính họ là tác giả của bản tin đó. Nó hoàn toàn trái ngược với hoạt động của khoá đối xứng, trong đó bản tin mật mã được đảm bảo tính toàn vẹn giữa phía mã hoá và giải mã, nhưng bất kỳ ai có được khoá chung đều có thể phát bản tin và từ chối rằng chính mình đã phát nó, còn phía thu thì không thể biết được đâu là tác giả của bản tin đó. Thuật toán đối xứng yêu cầu khả năng tính toán lớn hơn và do đó, tốc độ quá trình mã hoá chậm hơn so với mã hoá đối xứng. Đó cũng là trở ngại chính trong các hệ thống cho phép tỷ lệ lỗi lớn như trong truyền thông thoại. Do đó, mã hoá khoá công khai không phù hợp với các bản tin có chiều dài thông thường, tuy nhiên khi kết hợp cả hai chế độ với nhau lại có thể đảm bảo tính nhận thực, tin cậy và toàn vẹn của bản tin. Nói chung, các ứng dụng sử dụng thuật toán bất đối xứng là: Sử dụng một giá trị “băm” nhỏ làm chữ ký điện tử. Mã hoá các khoá bí mật được sử dụng trong thuật toán đối xứng. Thỏa thuận khóa mã bí mật giữa các phía trong truyền thông.
Hình 1.4: Nguyên lý cơ bản của mã hoá khoá công khai và thuật toán RSA. 2.1.3 HỆ MÃ HÓA RSA 2.1.3.1 Khái niệm hệ mật mã RSA Khái niệm hệ mật mã RSA đã được ra đời năm 1976 bởi các tác giả R.Rivets, A.Shamir, và L.Adleman. Hệ mã hoá này dựa trên cơ sở của hai bài toán + Bài toán Logarithm rời rạc (Discrete logarith) + Bài toán phân tích thành thừa số. Trong hệ mã hoá RSA các bản rõ, các bản mã và các khoá (public key và private key) là thuộc tập số nguyên ZN = {1, . . . , N-1}.Trong đó tập ZN với N=p×q là các số nguyên tố khác nhau cùng với phép cộng và phép nhân Modulo N tạo ra modulo số học N. Khoá mã hoá EKB là cặp số nguyên (N,KB) và khoá giải mã D kb là cặp số nguyên (N,kB), các số là rất lớn, số N có thể lên tới hàng trăm chữ số. Các phương pháp mã hoá và giải mã là rất dễ dàng. Công việc mã hoá là sự biến đổi bản rõ P(Plaintext) thành bản mã C (Ciphertext) dựa trên cặp khoá công khai KB và bản rõ P theo công thức sau đây : C = EKB(P) = EB(P) = PKB(mod N) . (1.1) Công việc giải mã là sự biến đổi ngược lại bản mã C thành bản rõ P dựa trên cặp khoá bí mật kB , modulo N theo công thức sau : P = DKB(C) = DB(C) = CKB(mod N) . (1.2) Dễ thấy rằng, bản rõ ban đầu cần được biến đổi một cách thích hợp thành bản mã, sau đó để có thể tái tạo lại bản rõ ban đầu từ chính bản mã đó : P = DB(EB(P)) (1.3) Thay thế (1.1) vào (1.2) ta có : (PKB)KB = P (mod N ) (1.4) Trong toán học đã chứng minh được rằng, nếu N là số nguyên tố thì công thức (4) sẽ có lời giải khi và chỉ khi KB.kB = (mod N-1), áp dụng thuật toán ta thấy N=p×q với p, q là số nguyên tố, do vậy (4) sẽ có lời giải khi và chỉ khi : KB.kB≡ 1 (mod γ(N)) (1.5) trong đó γ(N) = LCM(p-1,q-1) . LCM (Lest Common Multiple) là bội số chung nhỏ nhất. Nói một cách khác, đầu tiên người nhận B lựa chọn một khoá công khai KB một cách ngẫu nhiên. Khi đó khoá bí mật kB được tính ra bằng công thức (1.5). Điều này hoàn toàn tính được vì khi B biết được cặp số nguyên tố (p,q) thì sẽ tính được γ(N). kB Bản mã C kB Bản rõ gốc P . Hình 1.5 Sơ đồ các bước thực hiện mã hoá theo thuật toán RSA 2.1.3.2. Độ an toàn của hệ RSA Một nhận định chung là tất cả các cuộc tấn công giải mã đều mang mục đích không tốt. Trong phần độ an toàn của hệ mã hoá RSA sẽ đề cập đến một vài phương thức tấn công điển hình của kẻ địch nhằm giải mã trong thuật toán này. Chúng ta xét đến trường hợp khi kẻ địch nào đó biết được modulo N, khoá công khai KB và bản tin mã hoá C, khi đó kẻ địch sẽ tìm ra bản tin gốc (Plaintext) như thế nào. Để làm được điều đó kẻ địch thường tấn vào hệ thống mật mã bằng hai phương thức sau đây: Phương thức thứ nhất : Trước tiên dựa vào phân tích thừa số modulo N. Tiếp theo sau chúng sẽ tìm cách tính toán ra hai số nguyên tố p và q, và có khả năng thành công khi đó sẽ tính được λ(N) và khoá bí mật k B. Ta thấy N cần phải là tích của hai số nguyên tố, vì nếu N là tích của hai số nguyên tố thì thuật toán phân tích thừa số đơn giản cần tối đa N bước, bởi vì có một số nguyên tố nhỏ hơn N . Mặt khác, nếu N là tích của n số nguyên tố, thì thuật toán phân tích thừa số đơn giản cần tối đa N1/n bước. Một thuật toán phân tích thừa số có thể thành phức tạp hơn, cho phép phân tích một số N ra thành thừa số trong O( P )bước, trong đó p là số chia nhỏ nhất của N, việc chọn hai số nguyên tố là cho thuật toán tăng hiệu quả. Phương thức thứ hai : Phương thức tấn công thứ hai vào hệ mã hoá RSA là có thể khởi đầu bằng cách giải quyết trường hợp thích hợp của bài toán logarit rời rạc. Trường hợp này kẻ địch đã có trong tay bản mã C và khoá công khai KB tức là có cặp (KB,C) Cả hai phương thức tấn công đều cần một số bước cơ bản, đó là : O(exp √ lnNln(lnN)), trong đó N là số modulo. 2.1.3.3. Một số tính chất của hệ RSA Trong các hệ mật mã RSA, một bản tin có thể được mã hoá trong thời gian tuyến tính. Đối với các bản tin dài, độ dài của các số được dùng cho các khoá có thể được coi như là hằng. Tương tự như vậy, nâng một số lên luỹ thừa được thực hiện trong thời gian hằng, các số không được phép dài hơn một độ dài hằng. Thực ra tham số này che dấu nhiều chi tiết cài đặt có liên quan đến việc tính toán với các con số dài, chi phí của các phép toán thực sự là một yếu tố ngăn cản sự phổ biến ứng dụng của phương pháp này. Phần quan trọng nhất của việc tính toán có liên quan đến việc mã hoá bản tin. Nhưng chắc chắn là sẽ không có hệ mã hoá nào hết nếu không tính ra được các khoá của chúng là các số lớn. Các khoá cho hệ mã hoá RSA có thể được tạo ra mà không phải tính toán quá nhiều. Một lần nữa, ta lại nói đến các phương pháp kiểm tra số nguyên tố. Mỗi số nguyên tố lớn có thể được phát sinh bằng cách đầu tiên tạo ra một số ngẫu nhiên lớn, sau đó kiểm tra các số kế tiếp cho tới khi tìm được một số nguyên tố.Một phương pháp đơn giản thực hiện một phép tính trên một con số ngấu nhiên, với xác suất 1/2 sẽ chứng minh rằng số được kiểm tra không phải nguyên tố. Bước cuối cùng là tính p dựa vào thuật toán Euclid. Như phần trên đã trình bày trong hệ mã hoá công khai thì khoá giải mã (private key) kB và các thừa số p,q là được giữ bí mật và sự thành công của phương pháp là tuỳ thuộc vào kẻ địch có khả năng tìm ra được giá trị của kB hay không nếu cho trước N và KB. Rất khó có thể tìm ra được kB từ KB cần biết về p và q, như vậy cần phân tích N ra thành thừa số để tính p và q. Nhưng việc phân tích ra thừa số là một việc làm tốn rất nhiều thời gian, với kỹ thuật hiện đại ngày nay thì cần tới hàng triệu năm để phân tích một số có 200 chữ số ra thừa số. Độ an toàn của thuật toán RSA dựa trên cơ sở những khó khăn của việc xác định các thừa số nguyên tố của một số lớn. Bảng dưới đây cho biết các thời gian dự đoán, giả sử rằng mỗi phép toán thực hiện trong một micro giây. Số các chữ số trong số được phân tích  Thời gian phân tích   50  4 giờ   75  104 giờ   100  74 năm   200  4.000.000 năm   300  5×1015 năm   500  4×1025 năm   2.1.4 MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG GIẢI THUẬT RSA Tính chất an toàn của phương pháp RSA dựa trên cơ sở chi phí cho việc giải mã bất hợp lệ thông tin đã được mã hóa sẽ quá lớn nên xem như không thể thực hiện được. Vì khóa là công cộng nên việc tấn công bẻ khóa phương pháp RSA thường dựa vào khóa công cộng để xác định được khóa riêng tương ứng. Điều quan trọng là dựa vào n để tính p, q của n, từ đó tính được d. 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 φ (n) = (p-1 )(q-1 ) (1.6) Thay q = n/p, ta được phương trình bậc hai: p (n- φ(n)+1)p+n=0 (1.7) 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. Sự che dấu thông tin trong hệ thống RSA Hệ thống RSA có đặc điểm là thông tin không phải luôn được che dấu. Giả sử người gởi có e = 17, n = 35. Nếu anh ta muốn gởi bất cứ dữ liệu nào thuộc tập sau: {1, 6, 7, 8, 13, 14, 15, 20, 21, 22, 27, 28, 29, 34} thì kết quả của việc mã hóa lại chính là dữ liệu ban đầu. Nghĩa là, M = Me mod n. Còn khi p = 109, q = 97, e = 865 thì hệ thống hoàn toàn không có sự che dấu thông tin, bởi vì: ∀M, M = M865 mod (109*97), Với mỗi giá trị n, có ít nhất 9 trường hợp kết quả mã hóa chính là dữ liệu nguồn ban đầu. Thật vậy, M = Me mod n (1.8) hay: M = Me mod p và M = Me modq (1.9) Với mỗi e, có ít nhất ba giải pháp thuộc tập {0, 1, -1}. Để xác định chính xác số thông điệp không được che dấu (không bị thay đổi sau khi mã hóa) ta sử dụng định lý sau: “Nếu các thông điệp được mã hóa trong hệ thống RSA được xác định bởi số modulus n = p.q (p,q là số nguyên tố) và khóa công cộng e thì có: m = [1+gcd(e-1, p-1)][1+gcd(e-1),