Mô phỏng mã hóa RSA từng bước

Mã hóa RSA là gì?

RSA (Rivest-Shamir-Adleman) là một trong những hệ thống mật mã khóa công khai đầu tiên, được công bố vào năm 1977 bởi Ron Rivest, Adi Shamir và Leonard Adleman. Không giống như mã hóa đối xứng (nơi cùng một khóa được dùng để mã hóa và giải mã), RSA sử dụng một cặp khóa: một khóa công khai mà bất kỳ ai cũng có thể sử dụng để mã hóa dữ liệu và một khóa riêng tư mà chỉ chủ sở hữu mới có thể sử dụng để giải mã.

Tính bảo mật toán học của RSA dựa trên bài toán phân tích thừa số nguyên: việc nhân hai số nguyên tố lớn là rất dễ dàng, nhưng việc phân tích tích của chúng ngược lại thành các số nguyên tố là bất khả thi về mặt tính toán đối với các con số đủ lớn.

Cách tạo khóa RSA hoạt động

Quá trình tạo khóa RSA bao gồm năm bước cơ bản:

• Bước 1 – Chọn số nguyên tố: Chọn hai số nguyên tố phân biệt p và q. Các số nguyên tố này càng lớn thì khóa càng bảo mật.
• Bước 2 – Tính Modulus: Tính n = p × q. Độ dài bit của n xác định kích thước khóa (ví dụ: 2048 bit).
• Bước 3 – Hàm số Phi-Euler: Tính φ(n) = (p−1)(q−1). Giá trị này rất quan trọng để chọn e và tính d.
• Bước 4 – Số mũ công khai: Chọn e sao cho 1 < e < φ(n) và gcd(e, φ(n)) = 1. Lựa chọn tiêu chuẩn thường là 65537.
• Bước 5 – Số mũ riêng tư: Tính d bằng Thuật toán Euclid mở rộng sao cho d × e ≡ 1 (mod φ(n)).

Thuật toán Euclid mở rộng

Việc tính toán số mũ riêng tư d đòi hỏi phải tìm nghịch đảo nhân modulo của e theo modulo φ(n). Thuật toán Euclid mở rộng giải quyết hiệu quả vấn đề này bằng cách mở rộng thuật toán GCD tiêu chuẩn để đồng thời tìm các hệ số x và y sao cho a·x + b·y = gcd(a, b).

Khi gcd(e, φ(n)) = 1, thuật toán sẽ cho kết quả x sao cho e·x ≡ 1 (mod φ(n)), từ đó ta có d = x mod φ(n).

Cân nhắc về bảo mật RSA

• Kích thước khóa: RSA hiện đại sử dụng các khóa 2048 hoặc 4096 bit. Các số nguyên tố nhỏ trong trình mô phỏng này chỉ dành cho mục đích giáo dục và có thể bị phân tích ngay lập tức.
• Sơ đồ đệm (Padding): Các triển khai RSA thực tế sử dụng các sơ đồ đệm (OAEP, PKCS#1) để ngăn chặn các cuộc tấn công toán học vào dữ liệu RSA thô.
• Hiệu năng: RSA chậm hơn nhiều so với mã hóa đối xứng. Trong thực tế, RSA thường mã hóa một khóa đối xứng ngẫu nhiên, sau đó khóa đó sẽ mã hóa dữ liệu thực tế (mã hóa lai).
• Mối đe dọa từ lượng tử: Thuật toán Shor trên một máy tính lượng tử đủ mạnh có thể phân tích các số lớn một cách hiệu quả, đe dọa RSA. Mật mã học hậu lượng tử đang được phát triển như một biện pháp đối phó.

Ứng dụng thực tế của RSA

• TLS/SSL (HTTPS): RSA được sử dụng trong quá trình bắt tay (handshake) để trao đổi các khóa phiên đối xứng một cách an toàn.
• Chữ ký số: RSA ký các tài liệu bằng cách mã hóa một giá trị băm (hash) bằng khóa riêng tư, có thể được xác minh bằng khóa công khai.
• Mã hóa Email: PGP và S/MIME sử dụng RSA để mã hóa thông tin liên lạc qua email.
• Xác thực SSH: Các cặp khóa RSA cung cấp khả năng xác thực không cần mật khẩu để truy cập máy chủ từ xa.
• Ký mã nguồn: Các nhà xuất bản phần mềm ký các tệp thực thi bằng RSA để chứng minh tính xác thực và tính toàn vẹn.

Các câu hỏi thường gặp