HỆ MÃ RSA

Thuật toán RSA được đưa ra bởi Rivest, Shamir và Adleman [41]. Cho p và q là hai số nguyên tố lớn, ngẫu nhiên và phân biệt. Mô đun n là tích của hai số nguyên tố này: n=pq. Hàm phi Euler (Eulers totient function) của n được xác định bởi:
Nội dung trích xuất từ tài liệu:
HỆ MÃ RSA CHƯƠNG 1 – HỆ MÃ RSA 1. THUẬT TOÁN RSA: Thuật toán RSA được đưa ra bởi Rivest, Shamir và Adleman [41]. Cho p và q làhai số nguyên tố lớn, ngẫu nhiên và phân biệt. Mô đun n là tích của hai số nguyên tốnày: n=pq. Hàm phi Euler (Eulers totient function) của n được xác định bởi: ( ) ( )( ) Chọn một số ( ) sao cho ( ( )) Và tính d với ( ) Sử dụng thuật toán Euclidean mở rộng [19, 31]. Ở đây, e là số mũ công khai(public exponent) và d là số mũ bí mật (private exponent). Thông thường người tachọn số mũ công khai nhỏ, ví dụ . Mô đun n và số mũ công khai e được côngbố. Giá trị d, các số nguyên tố p và p được giữ bí mật. Mã hóa được thực hiện bằng cáchtính ( ) M là bản rõ (Plaintext) sao cho . Số C là bản mã (ciphertext) tươngứng với bản rõ M, được tính bằng cách sử dụng ( ) Tính đúng của thuật toán RSA được chứng minh bằng định lý Euler như sau: Chon và a là các số nguyên dương, nguyên tố cùng nhau (relatively prime). Khi đó ( ) ( ) Do ( ), nghĩa là ( ) với một số nguyên K, chúng ta cóthể viết lại: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Do ( ) . Ngoại lệ (exception) ( ) có thể được xử lý như sau.Theo định lý Carmichael ( ) ( ) Trong đó ( ) là hàm Carmichael có dạng đơn giản là n = pq, cụ thể ( )( ) ( ) ( ) Chú ý rằng ( ) luôn là ước thật sự (proper divisor) của ( ) khi n là tích củacác số nguyên tố chẵn, phân biệt; trong trường hợp này ( ) nhỏ hơn ( ). Xét mốiquan hệ giữa e và d ( ) nếu ( ( )) Thấy rằng n là tích của các số nguyên tố phân biệt với mọi M, do đó đối với ngoạilệ ( ) được đưa ra bên trên trong định lý Euler. Ví dụ, chúng ta xây dựng một hệ mã RSA đơn giản như sau. Chọn p = 11 và q =13, tính ( ) ( )( ) Chúng ta cũng có thể tính hàm Carmichael của n như sau: ( )( ) ( ) ( ) ( ) Số mũ công khai e được chọn sao cho ( ) và ( ( )) ( ) Ví dụ, e = 17 sẽ thỏa ràng buộc này. Số mũ bí mật d được tính bởi ( ( )) ( ) Sử dụng thuật toán Euclidean mở rộng hoặc một thuật toán bất kỳ khác để tínhnghịch đảo mô đun (modular inverse). Do đó, người dùng công bố số mũ công khai vàmô đun: (e, n) = (13, 143) và giữ bí mật: d = 113, p = 11, q = 13. Quy trình mã hóa/giảimã thông thường được thực hiện như sau:+ Bản rõ: M = 50Mã hóa: ( ) ( )+ Bản mã: C = 85Giải mã: ( ) ( ) 2. Trao đổi các thông điệp bí mật Thư mục khóa công khai chứa các cặp (e, n). Người dùng muốn gửi các thôngđiệp bí mật cho một người khác truy cập đến thư mục và thu được các tham số này. Vídụ thư mục được sắp thứ tự như sau: Cặp và tương ứng là mô đun và số mũ công khai của Alice. Như vậy, làmthế nào Alice gửi thông điệp bí mật M của cô ấy đến cho Bob ? Trong giao thức đơn giảncủa tác giả, Alice sẽ thực hiện các bước sau: 1) Alice xác định tên của Bob trong thư mục và lấy số mũ công khai cùng mô đun của anh ấy: ( ). 2) Alice tính: ( ). 3) Alice gửi C đến cho Bob trên mạng. 4) Bob nhận C. 5) Bob sử dụng số mũ bí mật của anh ấy và mô đun tính ( ) để thu được M. 3. Ký các tài liệu số Thuật toán RSA cung cấp một thủ tục để ký tài liệu số và xác minh (verifying)nếu chữ ký thật sự là xác thực (authentic). Ký một tài liệu số có phần khác với ký mộttài liệu giấy (sinh ra cùng một chữ ký). Chữ ký số không thể là một hằng, nó là một hàmof the digital document for which it was produced. Sau khi có được chữ ký (chỉ là mộtphần dữ liệu số) của một tài liệu số, nó được đính kèm vào tài liệu cho những ai có nhucầu xác minh tính xác thực của tài liệu và chữ ký. Ở đây, các tác giả chỉ minh họa tómtắt qui trình ký sử dụng hệ mã RSA. Giả sử ...