mở đầu một cách tiếp cận mới để mã hoá và thực sự thách thức các nhà lập mã nghiên cứu các thuật toán mã hoá đáp ứng yêu cầu hệ mật khoá công khai. Bằng cách sử dụng khoá lập mã và khoá giải mã khác nhau, hệ mật mã khoá công khai đã cung cấp đồng thời cơ chế truyền các thông báo bí mật không cần trao đổi trước khoá bí mật và sự áp dụng chữ ký điện tử. Một trong số kết quả đầu tiên trả lời thách thức đó là nhóm tác giả Ron Rivest, Adi Shamir và Len Adleman công bố vào năm 1978. Nhóm tác giả đó đã giới thiệu phương pháp đầu tiên thực hiện hệ mật khoá công khai, hệ mật đó gọi là RSA - dựa trên cơ sở tính luỹ thừa trong số học modulo.
Tính mật của hệ dựa trên độ khó của phân tích ra thừa số nguyên tố các số nguyên lớn. Sau này nhiều hệ mật mã công khai đã phát triển, nhưng hệ mật RSA vẫn được người sử dụng tin dùng và có nhiều ưu điểm nổi bật nhất. Thuật toán RSA ([6], [8], [10], [11], [12], [13]) có hai khoá: khóa công khai và khoá riêng. Mỗi khoá là một số cố định sử dụng trong quá trình mã hoá và giải mã.
Khoá công khai được công bố rộng rãi cho mọi người dùng để mã hoá. Những thông tin được mã hoá bằng khoá công khai chỉ có thể được giải mã bằng khoá riêng tương ứng. Nói cách khác, mọi người đều có thể mã hoá nhưng chỉ có người biết khoá riêng mới có thể giải mã được. Bài toán: A muốn gửi cho B một thông tin mật mà A muốn duy nhất B có thể đọc được.
Để làm được điều này, B gửi cho A một chiếc hộp có khoá đã mở và giữ lại chìa khoá. A nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khoá lại (lúc này ngay cả A cũng không thể đọc lại hay sửa thông tin trong thư được nữa). Sau đó A gửi chiếc hộp lại cho B. B mở hộp với chìa khoá của mình và đọc thông tin trong thư.
Trong ví dụ này, chiếc hộp với khoá mở đóng vai trò khoá công khai, chiếc chìa khoá chính là khoá riêng. Độ mật của RSA được dựa trên cơ sở là hầu như không có khả năng khôi phục hai số nguyên tố p và q từ tích n = p.q của chúng ít nhất là theo với các thuật toán phân tích ra thừa số hiện đã biết. Mặt khác, các số nguyên tố lớn ngẫu nhiên có thể được tạo sinh nhanh chóng Hệ mật RSA ngày nay được sử dụng trong rất nhiều sản phẩm phần mềm, có thể dùng trao đổi khoá, chữ ký điện tử, mã hoá các khối nhỏ số liệu. Hệ mật RSA sử dụng các tính toán trong Zn.
Hệ RSA sử dụng khối dữ liệu mã hoá kích thước thay đổi và khoá kích thước thay đổi. Cặp khoá được lấy từ số nguyên rất lớn n = pq là tích của hai số nguyên tố q và q được chọn. Các số nguyên tố p và q có thể dài tới trên 100 chữ số. RSA là mã khối, trong đó bản rõ, bản mã là các số nguyên từ 0 đến n – 1.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Đỗ Thanh Bình 22 Luận văn Thạc sĩ Khoá lập mã công khai dựa trên n, trong khi sự giải mã đòi hỏi biết p và q. Ta sẽ chỉ ra rằng giải mã là dễ dàng, nếu ta có được thông tin cửa sập bí mật. Có nghĩa là số d được gọi là số mũ giải mã. Biết về d có liên quan chặt chẽ với sự hiểu biết về p và q.2 Phƣơng pháp lập mã và giải mã của hệ mật RSA 2.1 Thuật toán a) Tạo khoá Hệ mật RSA dựa trên phép tính luỹ thừa, dó đó để lập mã một thông báo M ta tiến hành như sau: i) Chọn hai số nguyên tố lớn p và q (p q) , sau đó tính tích n = p.q Chú ý: nên chọn p và q đủ lớn (p, q là các số nguyên tố dài cỡ ít nhất 100 chữ số thập phân) để không thể khôi phục p, q từ tích n = pq ii) (n) = (p - 1)(q - 1) ((n) là số lượng các số nguyên nhỏ hơn n và nguyên tố cùng nhau với n) iii) Chọn một số nguyên e đủ lớn nguyên tố cùng (n), có nghĩa: 1< e <(n) và (e, (n) = 1) iv) Tìm số d thoả mãn: e.
Các số nguyên e và d trong sự sinh khoá RSA được gọi là số mũ mã hoá và số mũ giải mã tương ứng, và n được gọi là modulus. b) Lập mã Sau khi đã có khoá công khai và khoá riêng ta thực hiện mã hoá thông điệp như sau: i) Sử dụng khoá công khai của B là (n, e) ii) Biểu diễn thông điệp dưới dạng số, giả sử là số nguyên m sao cho: m [0, n-1] Để mã hoá một thông điệp, trước tiên ta phải số hoá thông điệp và nhóm nó lại thành các khối với độ dài lớn nhất có thể, không vượt quá n–1 và với một số chẵn chữ số. iii) Tính C = me mod n iv) Gửi bản mã C cho B LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Đỗ Thanh Bình 23 Luận văn Thạc sĩ Nên chọn e là số nguyên tố tuỳ ý không quá nhỏ. Số e phải chọn cần thoả mãn 2e >n = p.
Nếu điều kiện này không thoả mãn thì có khả năng xảy ra trường hợp me<n, và như vậy để tìm ra m chỉ cần thực hiện phép “khai căn thông thường” bậc e của C vì khi ấy me mod n = me. c) Giải mã Để được bản rõ P từ C, B phải làm như sau: i) Dùng khoá riêng d của B tính m = Cd mod n ii) Khôi phục thông điệp từ hàm ngược của hàm số hoá để có P. Ta sẽ giải thích rõ để chứng tỏ m = Cd mod n: Từ e.d = k(n) +1, k Z, nên từ (e,d) 1 (mod (n)) và theo định lý Eulor chúng ta có: m(n) 1(mod n) khi (m, n) = 1 với khả năng m và n không nguyên tố cùng nhau là rất nhỏ 2.2 Đặc trƣng của hệ mật RSA Hệ mật RSA có các đặc trưng sau: Không cần phải thiết lập một kênh bảo vệ với những thể thức phức tạp, rườm rà để truyền khoá như trong hệ mã bí mật (hệ mật mã đối xứng). Ta đã biết: nếu có khoá công khai không dễ gì để tìm được khoá riêng d trong thời gian chấp nhận được vì vậy không cần phải dùng một kênh bí mật để truyền khoá.
Cặp khoá công khai được tạo ra theo một phương pháp đặc biệt có quan hệ với nhau và được chọn trong nhiều khoá có thể (trong đó nếu khoá này dùng để mã hoá thì khoá kia dùng để giải mã). Dựa vào khoá công khai (n; e) để tính khoá riêng, khoá riêng d được tính bằng cách giải phương trình đồng dư e. Khoá cùng cặp (n; d) được giữ bí mật còn được gọi là khoá riêng. Vậy ứng với một cặp p, q có thể chọn được nhiều bộ khoá công khai (n; e; d) theo quan hệ chỉ ra và vai LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Đỗ Thanh Bình 24 Luận văn Thạc sĩ trò của e và d có thể xem là tương đương.
Nếu (n; e) là công khai thì (n; d) là khoá riêng và ngược lại nếu (n; d) là công khai thì (n; e) là khoá riêng. Mọi người trong hệ thống nếu nhận được bản mật C thì cũng không thể biết được bản rõ P. Với việc chỉ biết khoá mã hoá ke và căn cứ vào các thông tin về thuật toán thì không thể tìm ra khó giải mã kd trong thời gian chấp nhận được (kể cả dùng hệ thống hiện đại nhất để tính toán). Ta sẽ chứng tỏ rằng, nếu biết số mũ mã hoá e không thể dẫn đến việc tìm được số mũ giải mã d: Thật vậy: Muốn tìm nghịch đảo d của e modulo (n) thì trước hết phải tìm được (n), nhưng việc tìm được (n) không dễ hơn so với việc phân tích số n.
Bởi vì một khi đã biết n và (n) thì dễ dàng tìm được p và q. Ta có: (n) = (p - 1)(q - 1) (n) = pq – p –q + 1 (n) = n – p – q + 1 p + q = n - (n) + 1 (1) Mặt khác p q p q 2 4 pq p q 2 4n (2) Từ (1) và (2) dễ dàng tìm được p và q. Với các ví dụ nêu trên, chúng dễ dàng hiểu được sơ đồ mã hoá khoá công khai RSA như trong hình 2.1: Nguồn cặp khoá của B Khoá công khai Khoá bí mật eb db d e C = P b mod n P = C b mod n Bên gửi A Mã hoá Giải mã Bên nhận B Hình 2.1: Quá trình mã hóa khóa công khai RSA Quá trình gửi và nhận thông điệp (bản tin) được thực hiện như sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Đỗ Thanh Bình 25 Luận văn Thạc sĩ i) Mỗi thành viên sinh một cặp khoá (n; e; d), một khoá dùng để mã hoá và một khoá dùng để giải mã các thông điệp. ii) Mỗi thành viên công bố khoá công khai của mình (n; e) cho các thành viên khác trong hệ thống biết.
Khoá cùng cặp (n; d) được giữ lại làm khoá riêng (dùng để giải mã thông điệp). iii) A gửi thông điệp cho B thì A mã hoá thông điệp bằng khoá công khai (n; eb) của B. iv) Khi B nhận được thông điệp của A gửi, B giải mã thông điệp bằng khoá riêng (n; db) của mình. Không một người nào khác có thể giải mã thông điệp ngoài B, vì chỉ có B mới biết khoá riêng của mình.
Dựa vào thuật toán RSA đã mô tả trên ta thấy, để sinh được cặp khoá và thực hiện được các phép lập mã, giải mã ta phải giải quyết các bài toán sau đây: Tìm các số nguyên lớn để lấy làm các giá trị p và q (mỗi số có độ lớn không ít hơn 100 chữ số thập phân). Thực hiện nhanh các phép toán số học trên các số rất lớn, đặc biệt là phép mũ với số mũ lớn theo modulo n.1 Chọn hai số nguyên tố p = 43, q = 59 Ta có: n = 43.58 = 2436 Chọn e = 13, ta có (e, (n)) = (13, 2436) = 1 Để giải mã thông điệp, chúng ta phải tìm khoá riêng d, đó là nghịch đảo của e = 13 modulo 2436 nghĩa là tìm d sao cho e.