tailieunhanh - 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 (Euler's totient function) của n được xác định bởi: | 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 Euler s totient function của n được xác định bởi 0 n p - 1 ợ - 1 Chọn một số 1 e ộ n sao cho g d c e ộ n 1 Và tính d với d e 1mod ộ n 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 ta chọn số mũ công khai nhỏ ví dụ e 2 1 6 1 . Mô đun n và số mũ công khai e được công bố. 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ách tính c Me mod n M là bản rõ Plaintext sao cho 0 M n. 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 M cd mod n Tính đúng của thuật toán RSA được chứng minh bằng định lý Euler như sau Cho n và a là các số nguyên dương nguyên tố cùng nhau relatively prime . Khi đó u n 1 mo d n Do e d 1 m o d ộ n nghĩa là e d 1 Kộ n với một số nguyên K chúng ta có thể viết lại cd Me d mod n Med mod n M1 K w mo d n M. M nrf mod n mod n Do gc d M n 1. Ngoại lệ exception gc d m n 1 có thể được xử lý như sau. Theo định lý Carmichael M Ả n 1 mo d n Trong đó Ả ri là hàm Carmichael có dạng đơn giản là n pq cụ thể p 1 q 1 Ằ pq ư _ -n g c d p 1 q 1 Chú ý rằng Ả ri luôn là ước thật sự proper divisor của ộ ri khi n là tích của các số nguyên tố chẵn phân biệt trong trường hợp này Ả ri nhỏ hơn ộ ri . Xét mối quan hệ giữa e và d Med M mod n nếu ed 1 mod Ả n 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ại lệ gcd M n 1 đượ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 n 143 ộ n p 1 . q 1 1 120 Chúng ta cũng có thể tính hàm Carmichael của n như sau z p 1 q 1 120 Ả pq arddnnA 9 6 0 g cd p 1 q 1 gc d 1 0 12 2 Số mũ công khai e được chọn sao cho 1 e ộ ri và gc d e ộ n gc d e 12 0 1 Ví