Tạo khóa RSA như thế nào?

Giả sử Alice và Bob cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, Alice đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau:

1. Chọn 2 số nguyên tố lớn p và q với , lựa chọn ngẫu nhiên và độc lập.
2. Tính: n = pq.
3. Tính: giá trị hàm số Ơle .
4. Chọn một số tự nhiên e sao cho và là số nguyên tố cùng nhau với .
5. Tính: d sao cho .

Một số lưu ý:

* Các số nguyên tố thường được chọn bằng phương pháp thử xác suất.
* Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun).
* Bước 5 có thể viết cách khác: Tìm số tự nhiên x sao cho
cũng là số tự nhiên. Khi đó sử dụng giá trị .
* Từ bước 3, PKCS#1 v2.1 sử dụng thay cho ).

Khóa công khai bao gồm:

* n, môđun, và
* e, số mũ công khai (cũng gọi là số mũ mã hóa).

Khóa bí mật bao gồm:

* n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và
* d, số mũ bí mật (cũng gọi là số mũ giải mã).

Một dạng khác của khóa bí mật bao gồm:
* p and q, hai số nguyên tố chọn ban đầu,
* d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1),
* (1/q) mod p (thường được gọi là iqmp)

Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem - CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật.

Alice gửi khóa công khai cho Bob, và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa.