RSA là một hệ mã khóa công khai, được sử dụng rộng rãi để bảo mật thông tin nhạy cảm, đặc biệt khi truyền qua mạng không an toàn như Internet.
Trong mật mã RSA, cả khóa công khai và khóa riêng đều có thể mã hóa tin nhắn; khóa ngược lại với khóa dùng để mã hóa sẽ được dùng để giải mã. Thuộc tính này là lý do RSA trở thành thuật toán bất đối xứng phổ biến nhất. Nó đảm bảo tính bảo mật, toàn vẹn, xác thực và không thể chối cồi của kết nối và lưu trữ dữ liệu số.
RSA cần một nhóm nhân G =< Zфn,*, X > để sinh khóa. Nhóm này chỉ cung cấp phép nhân và chia, cần thiết cho việc tạo khóa công khai và riêng. Nhóm này được giữ bí mật vì modulus ф(n) bị ẩn khỏi công khai.
Thuật toán sinh khóa công khai và riêng là phần phức tạp nhất của mật mã RSA. Hai số nguyên tố lớn p và q được sinh ra bằng thuật toán kiểm tra nguyên tố Rabin-Miller.
Modulus n được tính bằng nhân p và q. Số này dùng cho cả khóa công khai và riêng, thiết lập liên kết giữa chúng. Độ dài của n (thường tính bằng bit) gọi là độ dài khóa.
Khóa công khai bao gồm modulus n và số mũ công khai e, thường đặt là 65537 vì đây là số nguyên tố không quá lớn. e không bắt buộc phải là số nguyên tố được chọn riêng tư vì khóa công khai được chia sẻ với mọi người.
Khóa riêng bao gồm modulus n và số mũ riêng d, được tính bằng thuật toán Euclid mở rộng để tìm nghịch đảo nhân theo modulo của hàm Euler φ(n).
Xét phép toán modulo n: e là số nguyên nguyên tố cùng nhau với φ(n). d là nghịch đảo nhân của e modulo φ(n). Các ký hiệu tóm tắt:
- n = modulus cho phép toán modulo
- φ(n) = hàm Euler của n
- e = số nguyên nguyên tố cùng nhau với φ(n) [đảm bảo e có nghịch đảo nhân modulo φ(n)]
- d = số nguyên là nghịch đảo nhân của e modulo φ(n)
Các bước tính toán sinh khóa
- Sinh hai số nguyên tố khác nhau p và q.
- Tính modulus n = p × q.
- Tính hàm Euler φ(n) = (p − 1) × (q − 1).
- Chọn số mũ công khai e sao cho 1 < e < φ(n) và gcd(φ(n), e) = 1.
- Tính số mũ riêng d sao cho d = e−1 mod φ(n).
- Khóa công khai = [e, n].
- Khóa riêng = [d, n].