Lesson 01: RSA

Rivest–Shamir–Adleman (1977) · Keygen · Encrypt/Decrypt · Extended Euclidean · Attacks

1. RSA Key Generator

Chọn hai số nguyên tố p, q từ danh sách — hệ thống tính n, φ(n), e, d tự động. Xem toàn bộ quá trình Extended Euclidean.

Số nguyên tố p:

p = 11

Số nguyên tố q:

q = 13

Public exponent e:

Nhập message m (0 < m < n). Xem c = m^e mod n và giải mã lại.

Message m:

Tính base^exp mod n bằng bình phương lặp — O(log exp) phép nhân thay vì O(exp).

base:

exp:

mod:

Nếu e=3 và m nhỏ (m³ < n), thì c = m³ chính xác — không có phép mod. Recover m = ∛c đơn giản.

e (= 3):

Cùng n, hai exponent e₁, e₂ với gcd(e₁,e₂)=1, hai ciphertext c₁=m^e₁, c₂=m^e₂ → recover m dùng Extended Euclidean.

Shared n:

e₁:

e₂: