RSA VÀ CÁC HÌNH THỨC TẤN CÔNG

Hệ mã RSA được giới thiệu vào năm 1977 bởi 3 nhà khoa học Ron Rivest, Adi Shamir, Len Adlerman. Đây là một trong những hệ mã được sử dụng phổ biến nhất hiện nay, ứng dụng cho truyền dữ liệu an toàn qua internet, email. RSA còn là nền tảng mật mã cho các giao thức SSL/TLS, SET, SSH, PGP, … RSA cũng được ứng dụng trong chữ ký số Digial Signature.

Mã hóa và giải mã

RSA thuộc nhóm hệ mã khóa công khai, dựa vào độ khó của bài toán phân tích 1 số ra thừa số nguyên tố (factoring problem). Để tạo cặp khóa Public key và Private key, Alice cần:

• Chọn 2 số nguyên tố lớn p, q với p ≠ q
• Tính n = p.q
• Tính giá trị của phi hàm Euler: φ(n) = (p-1)(q-1)
• Chọn 1 số tự nhiên e trong khoảng (1, φ(n)) sao cho gcd(e, φ(n)) = 1
• Tính d = e^(-1) (mod φ(n)) hay e.d = 1 (mod φ(n))

Public key sẽ là bộ số (n, e)

Private key sẽ là bộ số (n, d)

Chúng ta cần giữ private key thật cẩn thận cũng như các số nguyên tố p và q vì từ đó có thể tính toán các khóa rất dễ dàng.

Khi Bob muốn gửi một tin nhắn M cho Alice, Bob chuyển M thành một số m < n theo 1 cách thỏa thuận trước. Bob sẽ tính ra bản mã c từ bản rõ m theo công thức: c = m^e (mod n)

Để giải mã, Alice dùng Private Key của mình để tính ngược lại: m = c^d (mod n)

Qúa trình giải mã có thể thu được m ban đầu là do

	c^d = (m^e)^d = m^(ed) = m (mod n)

Hệ mã RSA nếu được thiết kế một cách đúng đắn với việc chọn các tham số n, p, q, e hợp lý thì sẽ rất an toàn.

Attacking RSA

1. Factorizing the public key

Độ mạnh của hệ mã RSA dựa trên việc bạn cần phân tích được n ra thừa số nguyên tố để tính d nếu muốn phá mã, và đến nay chưa có giải thuật nào hiệu quả trong thời gian đa thức giúp ta phân tích thừa số nguyên tố đối với các số lớn.

Ta đã biết d.e = 1(mod φ(n)) và cách duy nhất để tính được φ(n) là biết p và q.

Có thể sử dụng Bruteforce attack để xác định một p khả thi. Cách này chỉ sử dụng được khi n nhỏ (nhỏ hơn 256 bit). Khuyến nghị là dùng n ít nhất 2048 bit.

Nếu bạn cần phân tích một n lớn hơn, đôi khi có thể tìm thấy hoặc phân tích ở http://factordb.com/

Ví dụ:

n = 9567648541342714273618397561214215397959

ta dùng http://factordb.com/ và được kết quả:

p = 70636931
q = 135448247905089679980836052478189

Nhưng thông thường ta sẽ không phân tích được thừa số nguyên tố của n nên cần khai thác các yếu tố khác của mật mã RSA

2. Common modulus

External attack

Đặt bối cảnh trong mạng nội bộ sử dụng RSA làm phương thức truyền tin và quản trị viên không muốn tạo ra n khác nhau cho mỗi người nên sử dụng cùng một n cho toàn mạng lưới và e sẽ được chọn ngẫu nhiên.

Như vậy mỗi nhân viên i sẽ có một bộ khóa công khai (n, ei) và một bộ khóa bí mật (n, di)

Gỉa sử, bạn trong vai trò của attacker không phải là thành viên của hệ thống mạng. Tuy nhiên, bằng cách nào đó bạn biết được bộ số (e, n) giữa các thành viên. Việc cần làm là gửi cùng 1 tin nhắn cho 2 máy A, B và thu được bản mã (C1, C2).

Vì gcd(e1, e2) = 1 (e1, e2 nguyên tố cùng nhau) nên ta sẽ tìm được cặp số u và v sao cho:

u.e1 + v.e2 = 1 (Extended Euclidean Algorithm)

Ta sẽ tính m như sau:

m^(u.e1) * m^(v.e2) = m^(u.e1 + v.e2) = m^1 = m

internal attacker

Gỉa sử bạn là thành viên của hệ thống mạng nói trên và được cấp (n, e) và (n, d) và từ (n, e, d) của mình sẽ dễ dàng tìm được φ(n) theo cách sau.

Vì ed = 1 (mod φ(n)) nên tồn tại 1 số k sao cho

ed = k.φ(n) + 1

⇒ k = (ed-1)/φ(n)

khi n rất lớn φ(n) và n sẽ tương đối gần nhau vậy nên ta có thể viết như sau
⇒ k = (ed-1)/n

sau đó làm tròn số nguyên k và tính φ(n):

φ(n) = (ed - 1) / k

nếu φ(n) tính được không phải số nguyên thì tăng k cho đến khi thu được kết quả.

Có được φ(n) ta dễ dàng tìm được private key của victim dựa trên công thức:

d = e^-1 (mode φ(n))

3. Small public exponent

Trong sử dụng RSA làm phương thức truyền tin. Khi chúng ta chọn p và q là số nguyên tố lớn và mạnh ⇒ n là số rất lớn. Nhưng ta chọn 1 số e nhỏ vd như e = 3. Và gửi một đoạn tin nhắn nhỏ (small m)

Chúng ta sẽ tính được bản mã như sau:

c = m^e (mod n)

Nhưng bởi vì e và m rất nhỏ ⇒ m^e < n nên bản mã không bị ảnh hưởng bởi modulo.

⇒ c = m^e

Vậy ta chỉ cần căn bậc e bản mã thì sẽ thu được bản rõ.

4. Hastad’s Broadcast Attack

Cách tấn công này dựa trên cơ sở của Small public exponent nhưng lần này là một đoạn tin nhắn dài nên không thể dùng cách tương tự ở trên. Tuy nhiên, nạn nhân gửi cho nhiều người cùng một tin nhắn và sử dụng e như nhau.

Để attack thành công, bạn cần thu thập được nhiều bản mã khác nhau tương ứng với 1 bản rõ.

Gỉa sử e = 3 ⇒ M = m ^ 3. Ta sẽ phải giải quyết hệ phương trình:

M = c1 mod n1

M = c2 mod n2

M = c3 mod n3

Dựa vào chinese remainder theorem để giải quyết và tính được M.

5. Fermat’s attack

Trong thực tế và phải có cùng độ dài bit để tạo khóa RSA mạnh nhưng việc chọn các số nguyên tố quá gần cũng có thể làm hỏng hoàn toàn tính bảo mật.

Trong thực tế nếu: p - q < n^(1/4) thì Fermat’s factoring algorithm có thể phân tích n 1 cách hiệu quả.

$$n=pq=((p-q)/2{)}^2-((p+q)/2{)}^2=x^2-y^2=(x-y)(x+y)$$

Với

x = (p - q)/2

y = (p + q)/2

Giaỉ thuật giúp tìm ra p, q

6. Wiener’s attack (Low Private Exponent)

Đôi khi chúng ta sẽ gặp trường hợp khóa công khai e tương đối lớn so với modulo. Mục đích của việc này là làm cho d nhỏ để thuận tiện cho việc giải mã. Nhưng đó là lỗ hổng để Wiener’s attack khai thác

Các điều kiện để thực hiện được là:

• d < 1/3 n^(1/4)
• q < p < 2q
• e’ < n^(3/2) với e’ = e mod φ(n) (Public key không quá lớn)

Nếu thỏa mãn các điều kiện trên (nhận biết thông qua việc đề cho e rất lớn), ta có thể dễ dàng tìm được d và phá vỡ toàn bộ hệ thống mã hóa.

Chứng minh:

Phép chứng minh sử dụng tính chất của liên phân số. Vì ed ≡ 1 (mod φ(n))
 nên tồn tại một số nguyên k sao cho ed - kφ(n) = 1. Vì vậy:

Do đó k/d ≈ e/φ(n). Ta không biết φ(n) nhưng có thể dùng n để xấp xỉ. Thật vậy, φ(n) = n-p-q+1 và p+q-1 < 3√n nên n-φ(n) < 3√n. Sử dụng n thay cho φ(n)ta thu được:

Vì k < d < 1/3 n^¼ nên ta được:

Từ đó, áp dụng định lý về dãy hội tụ liên phân số, ta tìm trong dãy hội tụ của khai triển liên phân số e/n sẽ tìm được k/d. Bằng cách thử từng cặp k/d này, ta tính φ(n) = (ed - 1)/k. Lúc này ta có:

p+q = n-φ(n)+1 và pq = n

Dùng định lý Vi-et đảo tính được p, q. Xác nhận lại pq = n để tìm ra cặp k/d đúng. Tìm được p, q sẽ tính được d ⇒ done

7. Blinding attack

Chữ kí số sử dụng RSA:

Chữ ký số được sử dụng để xác thực dữ liệu điện tử. Giả sử Alice và Bob là hai bên chung mong muốn liên lạc với nhau và Marvin là kẻ nghe lén, cố gắng giả mạo việc truyền dữ liệu giữa hai bên. Kịch bản ở đây như sau: Alice đang cố lấy chữ ký của Bob qua tin nhắn ‘M‘. Để có chữ ký, Alice gửi tin nhắn 'M' trong đó Bob ký tin nhắn M như sau:

$S=M^d(modN)$
Ở đây S trở thành chữ ký của tin nhắn M. Trong bước trên, Bob áp dụng khóa riêng của mình cho tin nhắn và nhận được chữ ký S. Sau đó, Bob gửi S này cho Alice hoặc bất kỳ bên xác thực nào khác cần chữ ký của Bob trên M. Vì khóa công khai của Bob, như tên gợi ý, được các bên biết, nên chữ ký có thể dễ dàng xác minh xem nó có được tạo từ Bob hay không bằng cách tính toán đơn giản:

$S^e=M(modN)$

Blinding attack:

Hãy xem xét kịch bản tương tự ở đây, ngoại trừ thực tế là lần này Marvin muốn có chữ ký của Bob qua một tin nhắn M (Vd: “send me $1 million”) mà Bob từ chối, không phải là kẻ ngốc khi biết tầm quan trọng của Chữ ký số. Vì vậy, thay vì chữ ký trên M, Marvin yêu cầu chữ ký của M' được tính như sau:

$M^{\prime }=(r^e)M(modN)$
Bob đồng ý ký vào tin nhắn này M’. Đặt S’ là chữ ký được tạo trong trường hợp của M’. Chúng ta có thể viết S' là:

$S^{\prime }=(M^{\prime }{)}^d(modN)=(r^{e}M{)}^d(modN)=r{M}^d(modN)$
Khi nhận được chữ ký S’, Marvin có thể dễ dàng giả mạo chữ ký để lấy chữ ký cho thông điệp M như sau:

$S^{\prime }/r=M^d(modN)$ => chữ kí cho thông điệp M