Các hệ mật mã

Lời Nói Đầu Thế giới của chúng ta luôn sôi sục trong muôn vàn biến động được tạo ra bởi con người. Và trong thế kỷ 20 này, máy tính là một trong những sản phẩm vĩ đại nhất. Cùng với thời gian, người ta không muốn sử dụng một máy tính đơn lẻ nữa mà sẽ kết nối các máy này lại thành một mạng máy tính nhằm tăng khả năng làm việc, hiểu biết, trao đổi, cập nhật các thông tin … Mạng Internet là xu hướng phát triển của thế giới ngày nay. Hiện nay, Internet đã trở nên rất phổ biến trên toàn thế giới. Thông qua mạng Internet mọi người có thể trao đổi thông tin với nhau một cách nhanh chóng thuận tiện. Những công ty phát triển và kinh doanh trên môi trường Intranet/Internet họ phải đối diện với khó khăn lớn là làm thế nào để bảo vệ những dữ liệu quan trọng, ngăn chặn những hình thức tấn công, truy xuất dữ liệu bất hợp pháp từ bên trong (Intranet), lẫn cả bên ngoài (Internet). Khi một người muốn trao đổi thông tin với một người hay một tổ chức nào đó thông qua mạng máy tính thì yêu cầu quan trọng là làm sao để đảm bảo thông tin không bị sai lệch hoặc bị lộ do sự xâm nhập của kẻ thứ ba. Trước các yêu cầu cần thiết đó, một số giải thuật mã hóa đã dược xây dựng nhằm đảm bảo tính an toàn dữ liệu tại nơi lưu trữ cũng như khi dữ liệu được truyền trên mạng, như các giải thuật mã hóa đối xứng (DES), giải thuật mã hóa công khai, ... Việc tìm hiểu và xây dựng chương trình các giải thuật này cũng không nằm ngoài mục đích của bản luận văn này. Luận văn có nhiệm vụ tìm hiểu lý thuyết về mật mã hoá thông tin, xây dựng server tạo khóa cho user trong vấn đề bảo mật dữ liệu. Do thời gian và khả năng có hạn, trong khi phạm vi đề tài lại rộng, những người thực hiện chỉ có thể tìm hiểu được một số giải thuật chính như : DES, ECB, CBC, RSA, MD5 và qua đó đưa ra mô hình server tạo khóa cho các user, cụ thể là làm thế nào để quản lý và phân phối khóa một cách an toàn, hiệu quả. Chắc chắn rằng tập thuyết minh này sẽ không tránh khỏi những thiếu sót, người thực hiện mong nhận được sự góp ý, chỉ dẫn thêm của các Thầy Cô, bạn bè để bản thuyết minh được hoàn thiện hơn. Chúng tôi xin chân thành cảm ơn Thầy hướng dẫn, các Thầy Cô trong khoa đã tạo điều kiện thuận lợi để bản thuyết minh này có thể hoàn thành đúng thời hạn. Chương 1: Các hệ mật mã Hệ mật mã đối xứng: 1.1. Giới thiệu: Các giải thuật mật mã đối xứng là các giải thuật sử dụng cùng một khóa bí mật cho tác vụ mã hóa và tác vụ giải mã. Ví du ïnhư các giải thuật thay thế và hoán vị, giải thuật DES,…. Ở đây ta chỉ tìm hiểu giải thuật DES (Data Encryption Standard) là giải thuật mật mã đối xứng được sử dụng phổ biến nhất. 1.2. Giải thuật DES (Data Encryption Standard) : Vào năm 1977, "National Bureau of standard" đã đưa ra chuẩn DES để sử dụng cho các ứng dụng ở Mỹ. DES mã hóa các khối data 64 bits với khóa 56 bits. Giải thuật dùng để mã hóa lẫn giải mã được mô tả tóm tắt như hình 1. Trước tiên 64 bit input T được hoán vị bởi phép hoán vị hoán vị khởi động IP, với To = IP(T). Sau khi qua 16 vòng lặp (mỗi vòng sử dụng một khóa 48 bit được tạo ra từ khóa input 56 bits) với tác động của hàm F, nó được hoán vị bằng phép hoán vị đảo IP-1 để tạo ra 64 bit output cuối cùng. IP và IP-1 được cho trong các bảng (bảng 1a và bảng 1b). Các bảng này được đọc từ trái sang phải, từ trên xuống dưới theo dạng: T = t1t2…..t64 à T0 = t58t50…….t7 Đầu tiên khối T được tách thành hai khối trái và phải (mỗi khối 32 bits): T = L0R0 với L0 = t1…..t32 , R0 = t33…..t64. Ở vòng lặp thứ i (0 < i < 16) : Li = Ri-1 , Ri = Li-1 Å F(Ri-1, Ki) trong đó Å là phép cộng exclusive_or và Ki là khóa 48 bits. Ở vòng lặp cuối cùng các nhánh trái và phải không đổi chỗ cho nhau vì vậy input của IP-1 là R16L16 . Hàm F và S_boxes: (hình 3) Trước tiên Ri-1 được mở rộng thành khối 48 bits E(Ri-1) với E là bảng lựa chọn bit được cho trong bảng 2. Sau đó thực hiện phép XOR E(Ri-1) với Ki và kết quả được tách thành 8 khối 6 bit từ B1 tới B8 : E(Ri-1) Å Ki = B1B2...B8 Mỗi khối Bj sau đó được đưa vào một hàm Sj (S - box) : Sj (Bj) trả về một khối 4 bit (bảng 4). Các khối này được nối lại và khối kết quả 32 bit được hoán vị bằng phép P (bảng 3). F(Ri-1 , Ki) = P(S1(B1) …. S8(B8)) Hoạt động của S-box: số nguyên tương ứng với b1b6 sẽ chọn Row trong bảng, còn số nguyên tương ứng với b3b4b5b6 sẽ chọn Column. Giá trị của Sj(Bj) được chọn sẽ là một số nguyên 4 bit ở vị trí Row và Column đó. Tính khóa: (hình 2) DES tạo ra 16 khóa, mỗi khóa chiều dài 48 bit từ một khóa input 56 bit, dùng cho 16 vòng lặp. Lưu đồ tính toán khóa được cho trong hình 2: Khóa input là một khối 64 bit, với 8bit parity tại các vị trí 8, 16,.…, 64. Permutation PC-1 sẽ loại bỏ các bit parity và sẽ hoán vị 56 bit còn lại theo bảng 5. Kết quả, PC-1(K) sau đó được chia thành hai phần C0 và D0 mỗi phần 28 bit. Khóa Ki dùng trong vòng thứ i được tạo ra từ Ci-1 và Di-1 theo quy tắc như sau: trong các vòng 1, 2, 9 và 16, Ci-1 và Di-1 được quay vòng một bít qua trái, trong các vòng còn lại thì được quay vòng hai bít qua trái. Qua phép quay vòng này Ci-1 và Di-1 sẽ được biến đổi thành Ci và Di . Hoán vị Ci và Di theo bảng 6. Sau khi hoán vị Ci bỏ qua các bít 9, 18, 22, 25 tạo thành nữa trái của Ki (24 bít), còn Di bỏ đi các bít 35, 38, 43, 54 tạo ra nữa phải của Ki (24 bít). Ghép nữa trái và nữa phải tạo ra khóa Ki 48 bít. Giải mã: Quá trình giải mã được thực hiện theo cùng giải thuật này theo thứ tự ngược lại như sau: IP-1 là đảo của IP và ở vòng lặp thứ i sử dụng khóa K17-i (K16 ở vòng lặp đầu tiên, K1 ở vòng lặp cuối cùng) và: Ri-1 = Li Li-1 = Ri Å F(Li, Ki) 8 48 16 56 24 64 32 7 47 15 55 23 63 31 6 46 14 54 22 62 30 5 45 13 53 21 61 29 4 44 12 52 20 60 28 3 43 11 51 19 59 27 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 54 46 38 30 22 14 6 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Bảng 1a: Bảng hoán vị đầu tiên IP Bảng 1b: Bảng hoán vị cuối cùng IP-1 7 20 21 12 28 17 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 32 1 2 3 4 5 4 5 6 7 8 9 9 10 11 12 13 13 14 15 16 17 17 18 19 20 21 21 22 23 24 25 25 26 27 28 29 28 29 30 31 32 1 Bảng 2: Bảng chọn bít E Bảng 3: Bảng hoán vị P 57 49 41 33 25 17 9 1 58 50 42 34 26 18 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 14 17 11 24 1 5 3 8 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 52 31 37 47 55 40 51 45 33 48 49 39 56 34 53 46 42 50 36 29 32 Bảng 5: Bảng hoán vị khóa PC-1 Bảng 6: Bảng hoán vị khóa PC-2 Column Row 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Box 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 14 0 4 15 15 3 0 13 10 13 13 1 7 13 10 3 2 14 4 11 12 10 9 4 4 13 1 6 13 1 7 2 4 15 1 12 1 13 14 8 0 7 6 10 13 8 6 15 12 11 2 8 1 15 14 3 11 0 4 11 2 15 11 1 13 7 14 8 8 4 7 10 9 0 4 13 14 11 9 0 4 2 1 12 10 4 15 2 2 11 11 13 8 13 4 14 1 4 8 2 14 7 11 1 14 9 9 0 3 5 0 6 1 12 11 7 15 2 5 12 14 7 13 8 4 8 1 7 2 14 13 4 6 15 10 3 6 3 8 6 0 6 12 10 7 4 10 1 9 7 2 9 15 4 12 1 6 10 9 4 15 2 6 9 11 2 4 15 3 4 15 9 6 15 11 1 10 7 13 14 2 12 8 5 0 9 3 4 15 3 12 10 11 13 2 1 3 8 13 4 15 6 3 8 9 0 7 13 11 13 7 2 6 9 12 15 8 1 7 10 11 7 14 8 8 1 11 7 4 14 1 2 5 10 0 7 10 3 13 8 6 1 8 13 8 5 3 10 13 10 14 7 1 4 2 13 3 10 15 5 9 12 5 11 1 2 11 4 1 4 15 9 8 5 15 6 0 6 7 11 3 14 10 9 10 12 0 15 10 6 12 11 7 0 8 6 13 8 1 15 2 7 1 4 5 0 9 15 13 1 0 14 12 3 15 5 9 5 6 12 6 12 9 3 2 1 12 7 12 5 2 14 8 2 3 5 3 15 12 0 3 13 4 1 9 5 6 0 3 6 0 9 12 11 7 14 13 10 6 12 7 14 12 3 5 12 14 11 15 10 5 9 4 14 10 7 7 12 8 15 14 11 13 0 5 9 3 10 12 6 9 0 11 12 5 11 11 1 5 12 13 3 6 10 14 0 1 6 5 2 0 14 5 0 15 3 9 5 10 0 0 9 3 5 4 11 10 5 12 10 2 7 0 9 3 4 7 11 13 0 10 15 5 2 0 14 3 6 0 3 5 6 5 11 2 14 2 15 14 2 4 14 8 2 14 8 0 5 5 3 11 8 6 8 9 3 12 9 5 5 7 8 0 13 10 5 15 9 8 1 7 12 15 9 4 14 9 6 14 3 11 8 6 13 1 6 2 12 7 2 8 11 S1 S2 S3 S4 S5 S6 S7 S8 Bảng 4: Bảng chọn (S-boxex) 1.2.1. DES In Electronic CodeBook Mode (ECB) : Ở mode này, các khối data dưới dạng rỏ (clear text) được đưa vào input của DES. Các khối kết quả dưới dạng mật mã (ciphertext) có thể được sử dụng cho các ứng dụng khác. Quá trình biến đổi diễn ra như sau: (hình 4) Clear text à Input block à DES à Output block à Ciphertext. ECB encryption ECB decription Clear text (D1, D2, ... D64) Cipher text (C1, C2, … C64) Input block (I1, I2, … I64) Input block (I1, I2, … I64) DES encrypt DES decrypt Output block (O1, O2, … O64) Output block (O1, O2, … O64) Cipher text (C1, C2, … C64) Clear text (D1, D2, ... D64) Hình 4: Electronic Codebook Mode (ECB) 1.2.2. DES In Cipher Block Chaining Mode (CBC) : Khối data cần mã hóa được chia thành các khối B1, B2, … Bn với kích thước mỗi khối là 64 bits. Vectơ khởi tạo IV (64 bits) được chọn. Sơ đồ mật mã đưọc cho trong hình 5: + Quá trình mã hóa: Mã hóa (1) IV Å B1 C1 (2) C1 Å B2 C2 . . (n) Cn-1 Å Bn Cn + Quá trình giải mã: Giải mã C1 IV Å B1 , (IV Å B1) Å IV = B1 C2 C1 Å B2 , (C1 Å B2) Å C1 = B2 . . Cn Cn-1 Å Bn , (Cn-1 Å Bn) Å Cn-1 = Bn Time = 1 Time = 2 ..................... Time = n Bn B2 B1 IV + + + Mã hóa I I I DES encry DES encry DES encry ........ Cn C2 C1 ......... IV I I I DES decry DES decry DES decry Giải mã + + + Bn B2 B1 Hình 5: Cipher Block Chaining (CBC) mode 2. Hệ mật mã bất đối xứng 2.1. Giới thiệu: - Sự phát triển của mật mã khóa công khai là rất lớn và có lẽ chính nó tạo ra cuộc cách mạng trong toàn bộ lịch sử của mật mã khóa. - Những giải thuật khóa công khai đều dựa trên những hàm toán học hơn là những phép thay thế và hoán vị trong mật mã khóa cổ điển. Quan trọng hơn mật mã khóa công khai có tính chất bất đối xứng, bao gồm việc sử dụng 2 khóa riêng biệt tương phản với mã hóa qui ước có tính đối xứng mà chỉ sự dụng 1 khóa. Việc sử dụng 2 khóa có tầm quan trọng sâu sắc trong lĩnh vực cần tính bí mật, phân bố khóa và sự chứng thực. - Một số quan niệm sai liên quan đến mã hóa khóa công khai : + Mã hóa khóa công khai thì bảo mật đối với nhà phân tích mật mã hơn là mã hóa qui ước. Thật ra, tính bảo mật của bất kỳ sơ đồ mã hóa nào đều phụ thuộc vào chiều dài của khóa và việc tính toán để giải quyết việc bẻ khóa. + Mã hóa khóa công khai có mục tiêu chung, kỹ thuật được thực hiện bằng mã hóa qui ước lỗi thời. Ngược lại, bời vì việc tính toán được đặt hàng đầu trong sơ đồ mã hóa khóa công khai, cho nên dường như không thể thấy trước khả năng xảy ra rằng mã hóa qui ước sẽ bị bỏ rơi. Một trong những người đã khám phá ra mã hóa khóa công khai đã phát biểu : “Hạn chế của mật mã khóa công khai để quản lý khóa và sử dụng chữ ký là hầu như được chấp nhận phổ biến”. + Có cảm giác rằng sự phân bố khóa thì không quan trọng trong khi sử dụng mã hóa khóa công khai, so sánh thì cơ chế bắt tay trở ngại hơn, bao gồm những trung tâm phân bố khóa cho mã hóa qui ước. Thật ra, 1 vài khuôn dạng giao thức là cần thiết, nói chung bao gồm 1 tác nhân trung tâm và những thủ tục liên quan thì không đơn giản mà cũng không hiệu quả hơn yêu cầu cho việc mã hóa khóa công khai này. 2.2. Lý thuyết về mật mã khóa công khai: - Khái niệm mật mã khóa công khai đã tạo ra sự cố gắng để giải quyết 2 vấn đề khó khăn nhất trong mã khóa qui ước, đó là sự phân bố khóa và chữ ký số: + Trong mã hóa qui ước sự phân bố khóa yêu cầu hoặc là hai người truyền thông cùng (share) tham gia một khóa mà bằng cách nào đó đã được phân bố tới họ hoặc là sử dụng chung một trung tâm phân bố khóa. Whitfield Diffie, một trong những người khám phá ra mật mã khóa công khai (cùng với Martin Hellman) đã giải thích rằng yêu cầu này đã phủ định bản chất của mật mã: khả năng bảo vệ tính bí mật hoàn hảo qua việc truyền thông riêng của bạn: “Nó sẽ làm tốt như thế nào sau mọi sự phát triển, hệ thống không thể xuyên qua được nếu các user bị bắt buộc tham gia (share) các khóa của nó với một KDC mà có thể được thỏa hiệp bởi kẻ trộm?”. + Nếu việc sử dụng mật mã đã trở nên phổ biến, không chỉ trong quân đội mà còn trong thương mại và những mục đích cá nhân thì những đoạn tin và tài liệu điện tử sẽ cần những chữ ký tương đương đã sử dụng trong các tài liệu giấy. Tức là, một phương pháp có thể được nghĩ ra có quy định làm hài lòng tất cả những người tham gia khi mà một đoạn tin số được gởi bởi một cá nhân đặc biệt hay không?. - Trong sơ đồ mã hóa quy ước, các khóa được dùng cho mã hóa và giải mã một đoạn tin là giống nhau. Đây là một điều kiện không cần thiết. Thay vì nó có thể phát triển giải thuật mã hóa dựa trên một khóa cho mã hóa và một khóa khác (có quan hệ với khóa trên) cho giải mã. Hơn nữa các giải thuật này có những đặc điểm quan trọng sau: + Đó là việc tính toán một cách không khả thi để xác định khóa giải mã trong khi chỉ biết giải thuật mật mã và khóa mã hóa. + Trong giải thuật RSA còn có đặc điểm hoặc một trong hai khóa quan hệ có thể được sử dụng cho mã hóa còn khóa kia được dùng cho giải mã. - Các bước cần thiết trong quá trình mã hóa khóa công khai: + Mỗi hệ thống cuối trong mạng tạo ra một cặp khóa để dùng cho mã hóa và giải mã đoạn tin mà nó sẽ nhận. + Mỗi hệ thống công bố rộng rãi khóa mã hóa bằng cách đặt khóa vào một thanh ghi hay một file công khai. Đây là khóa công khai, khóa còn lại được giữ riêng. + Nếu A muốn gởi một đoạn tin tới B thì A mã hóa đoạn tin bằng khóa công khai của B. + Khi B nhận đoạn tin mã hóa, nó giải mã bằng khóa bí mật của mình. Không một người nào khác có thể giải mã đoạn tin mã này bởi vì chỉ có mình B biết khóa bí mật đó thôi. Khóa công khai của B User A User B Giải thuật giải mã Giải thuật mã hóa khóa bí mật của B đoạn tin mật mã đoạn tin Với cách tiếp cận này, tất cả những người tham gia có thể truy xuất khóa công khai. Khóa bí mật được tạo ra bởi từng cá nhân, vì vậy không bao giờ được phân bố. Ở bất kỳ thời điểm nào, hệ thống cũng có thể chuyển đổi cặp khóa để đảm bảo tính bảo mật. - Bảng sau tóm tắt một số khía cạnh quan trọng về mã hóa quy ước và mã hóa công khai: để phân biệt giữa hai loại, chúng ta sẽ tổng quát hóa liên hệ khóa sử dụng trong mã hóa quy ước là khóa bí mật, hai khóa sử dụng trong mã hóa công khai là khóa công khai và khóa bí mật. Mã hóa quy ước Mã hóa công khai * Yêu cầu: - Giải thuật tương tự cho mã hóa và giải mã. - Người gởi và người nhận phải tham gia cùng giải thuật và cùng khóa. * Tính bảo mật: - Khóa phải được giữ bí mật. - Không thể hay ít nhất không có tính thực tế để giải mã đoạn tin nếu thông tin khác không có sẵn. - Kiến thức về giải thuật cộng với các mẫu về mật mã không đủ để xác định khóa. * Yêu cầu: - Một giải thuật cho mã hóa và một giải thuật cho giải mã. - Người gởi và người nhận , mỗi người phải có cặp khóa cho riêng mình. * Tính bảo mật: - Một trong hai khóa phải được giữ bí mật. - Không thể hay ít nhất không có tính thực tế để giải mã đoạn tin nếu thông tin khác không có sẵn. - Kiến thức về giải thuật cộng với một trong các khóa, cộng với các mẫu về mật mã không đủ để xác định khóa kia. - Các sơ đồ mật mã quy ước và mật mã khóa công khai: xem sơ đồ bên 2.3. Ứng dụng của mật mã khóa công khai: - Tùy thuộc vào ứng dụng, người gởi sử dụng hoặc khóa bí mật của người gởi hoặc khóa công khai của người nhận hoặc cả hai mà hình thành một số kiểu chức năng của mật mã khóa. Có 3 chiến lược sau: + Mã hóa/giải mã: người gởi mã hóa đoạn tin bằng khóa công khai của người nhận, người nhận giải mã bằng khóa bí mật của mình. + Chữ ký số: người gởi mã hóa đoạn tin (ký tên) bằng khóa bí mật của mình, người nhận giải mã bằng khóa công khai của người gởi. Chữ ký được áp dụng tới đoạn tin hay tới một khối dữ liệu nhỏ mà được liên kết trong một số phương thức tới đoạn tin. + Chuyển đổi khóa: người gởi mã hóa đoạn tin hai lần, lần 1 sử dụng khóa bí mật của bản thân, lần 2 sử dụng khóa công khai của người nhận. Người nhận giải mã đoạn tin nhận được bằng khóa bí mật của bản thân và khóa công khai của người gởi. - Một số giải thuật cho mật mã khóa công khai: RSA, ECC, LUC, DSS, Diffie_Hellman…. Trong đồ án này, chỉ trình bày giải thuật RSA. 2.4. Các yêu cầu của mật mã khóa công khai: - Công việc tính toán thì dễ dàng cho người nhận B à tạo cặp khóa: khóa công khai KU và khóa bí mật KR. - Công việc tính toán thì dễ dàng cho người gởi A à biết khóa công khai và đoạn tin cần mã hóa M, để tạo mật mã tương ứng: C=EKUb (M). - Công việc tính toán thì dễ dàng cho người nhận B à sử dụng khóa bí mật để giải mã đoạn tin mã hóa C, khôi phục lại đoạn tin đầu: M= DKRb (C)= DKRb [EKUb (M)] - Công việc tính toán không thể thấy trước đối với địch thủ biết khóa công khai KUb, để xác định khóa bí mật KRb. - Công việc tính toán không thể thấy trước đối với địch thủ biết khóa công khai KUb và một mật mã C, để khôi phục đoạn tin ban đầu M. - Chức năng mã hóa và giải mã có thể được áp dụng theo thứ tự: M= DKRb [EKUb (M)] M= EKUb [DKRb (M)] Có thể nhận thấy rằng việc tính Y=f(X) thì dễ dàng trong khi tính X=f –1(Y) là không thể thấy trước. Nói chung từ “dễ dàng” được xác định bởi 1 bài toán là nó có thể được giải quyết trong thời gian nhất định (hàm của chiều dài input). Nếu chiều dài input là n bít thì thời gian để tính hàm đó tỉ lệ với na (a=const). Để đảm bảo tính bảo mật, phải sử dụng khóa có kích thước đủ lớn (thường trên 100 chữ số thập phân). Ví dụ kích thước khóa và thời gian bẻ khóa (MIPS năm) trong các giải thuật RSA/DSS và ECC như sau: RSA (bít) ECC (bít) MIPS năm 512 768 1024 106 132 160 104 108 1012 2.5. Giải thuật RSA (Rivest, Shamir và Adleman – 1977): 2.5.1. Mô tả giải thuật: - Sơ đồ RSA là sơ đồ mã hóa khối: đoạn tin được mã hóa từng khối, với mỗi khối có giá trị nhỏ hơn n. Việc mã hóa và giải mã theo hình thức sau, cho khối văn bản M và khối bảo mật C: C = Me mod n M = Cd mod n = (Me)d mod n = Mde mod n - Cả hai người gởi và nhận phải biết giá trị n, người gởi biết e và chỉ có người nhận biết d. Cho nên đây là giải thuật mã hóa với khóa công khai KU=[e,n] và khóa bí mật KR=[d,n]. Vì giải thuật này thỏa giải thuật mật mã khóa công khai nên các yêu cầu sau phải được đáp ứng: + Có thể tìm thấy giá trị d,e,n để M=Mde mod n với mọi M<n hay không? + Một cách tương đối dễ dàng tính Me và Cd với mọi M<n hay không? + Không thể xác định d khi biết e và n. - Theo lí thuyết của Euler: cho 2 số nguyên tố p và q, 2 số nguyên n và m (n=p*q , 0<m<n) và số nguyên k. Ta có: mk0 (n) + 1 = mk (p-1) (q-1) + 1 = m mod n 0(n) = 0(pq) = (p-1)(q-1) Do đó: nếu: de = k0(n) +1 và gcd(0(n),e) = 1 (gcd: ước số chung) thì : de mod 0(n) = 1 và d mod 0(n) = e-1 - Sơ đồ RSA: + Giả sử user A đã công bố khóa công khai e của nó và user B muốn gởi đoạn tin M tới A. Khi đó B tính C = Me mod n và truyền C. Khi nhận được đoạn tin C này, user A giải mã bằng cách tính Cd mod n. Có thể thấy rằng M = Cd mod n vì: de mod 0(n) = 1 hay de = k0(n) + 1 à Mk0 (n) + 1 = Mk (p-1) (q-1) + 1 = M mod n = (Mde mod n) mod n = Mde mod n Cd mod n = (Me)d mod n = Mde mod n = M + Có thể tóm tắt giải thuật RSA như bảng sau: Tạo khóa Độ phức tạp Tạo 2 số nguyên tố lớn p và q Tính n = p*q, 0(n) = (p-1)*(q-1) Chọn 1 số ngẫu nhiên 1<e<0(n): gcd(0(n), e) = 1 Tính d: d = e-1 mod 0(n) (giải thuật Extended Euclidean) Khóa công khai KU = [e, n] Khóa bí mật KR = [d, n] 0((logn)2) 0((log(0(n))2) 0((logn)3) Mã hóa Đoạn tin : M < n Mã hóa : C = Me mod n Giải mã Đoạn tin mã: C Giải mã : M = Cd mod n - Độ phức tạp: + Cộng 2 số k bít: 0(k) + Nhân 2 số k bít: 0(k2) + 2 k bít mod n : 0(k2) + xc mod n : 0(k3) Để tính xc mod n cần c-1 phép nhân modulus à không hiệu quả (do c lớn) à sử dụng giải thuật square_multiply để giảm số phép nhân mod nhiều nhất 2l (l là số bít nhị phân của c, l<=k với k là số bít nhị phân của x) - Tốc độ mã hóa trong RSA: Tốc độ và hiệu quả của nhiều phần mềm thương mại có sẵn và công cụ phần cứng của RSA đang gia tăng 1 cách nhanh chóng. Với pentium 90Mhz, bộ toolkit BSAFE 3.0 của cơ quan bảo mật dữ liệu RSA đạt tốc độ tính khóa bí mật là 21,6Kbps với khóa 512 bít và 7,4Kbps với khóa 1024 bít. Phần cứng RSA nhanh nhất đạt hơn 300 Kbps với khóa 512 bít, nếu được xử lý song song thì đạt 600 Kbps với khóa 512 bít và 185Kbps với khóa 970 bít. Người ta mong đợi rằng tốc độ RSA sẽ đạt 1Mbps vào cuối năm1999. So sánh với giải thuật DES và các giải thuật mã khối khác thì RSA chậm hơn: về phần mềm DES nhanh hơn RSA 100 lần, về phần cứng DES nhanh hơn RSA từ 1000 tới 10000 lần tùy thuộc công cụ (implementation) sử dụng (thông tin này được lấy từ - Kích thước khóa trong RSA: Tùy thuộc vào tính bảo mật cần thiết của mỗi người và thời gian sống của khóa mà khóa có chiều dài thích hợp: + Loại Export : 512 bít + Loại Personnal : 768 bít + Loại Commercial: 1024 bít + Loại Militery : 2048 bít - Chu kỳ sống của khóa phụ thuộc: + Việc đăng ký và tạo khóa. + Việc phân bố khóa. + Việc kích hoạt hoặc không kích hoạt khóa. + Việc thay thế hoặc cập nhập khóa. + Việc hủy bỏ khóa. + Việc kết thúc khóa bao gồm sự phá hoại hoặc sự lưu trữ. 2.5.2. Tính bảo mật của giải thuật RSA: - Vì khóa là công khai, nên người giải mã thường dựa vào cặp khóa này để tìm cặp khóa bí mật. Điều quan trọng là dựa vào n để tính hai thừa số p, q của n từ đó tính được d. Có nhiều giải thuật như thế, đầu tiên ta xét trường hợp đơn giản nhất là người giải mã biết được F(n) . Khi đó tính p, q đưa về việc giải hai phương trình sau: n = p.q F(n) = (p-1)(q-1) Thay q=n/p ta được phương trình bậc hai: p2 – (n - F(n) + 1)p + n = 0 Hai nghiệm của phương trình bậc hai này sẽ là p, q. Tuy nhiên vấn đề có được F(n) còn khó hơn tính hai thừa số của n nhiều. 2.5.2.1. Phương pháp p-1: Chúng