Khóa luận Các phương pháp tấn công RSA

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

---------<>---------

Bùi Tuấn Anh

CÁC PHƯƠNG PHÁP TẤN CÔNG RSA

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành : Công Nghệ Thông Tin

HÀ NỘI – 2009

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

---------<>---------

Bùi Tuấn Anh

CÁC PHƯƠNG PHÁP TẤN CÔNG RSA

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành : Công Nghệ Thông Tin

Cán bộ hướng dẫn: TS. Hồ Văn Canh

HÀ NỘI – 2009

LỜI CÁM ƠN

Để thực hiện hoàn thành luận văn “ Các phương pháp tấn công RSA” em đã

nhận được sự hướng dẫn và giúp đỡ nhiệt tình của nhiều tập thể và cá nhân

Trước hết, em xin bày tỏ lòng biết ơn chân thành đến ban lãnh đạo cùng quý

thầy cô trong khoa Công nghệ thông tin - Trường Đại học Công nghệ, Đại học quốc

gia Hà Nội đã tận tình dạy dỗ, truyền đạt kiến thức, kinh nghiệm quý báu và tạo điều

kiện thuận lợi cho em trong suốt thời gian học tập và thực hiện đề tài.

Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn TS. Hồ Văn

Canh, người đã tận tình hướng dẫn, giúp đỡ em trong suốt quá trình thực hiện đề tài.

Xin trân trọng gửi đến gia đình, bạn bè và người thân những tình cảm tốt đẹp

nhất đã giúp đỡ động viên em trong suốt quá trình học tập cũng như thực hiện và

hoàn thành luận văn.

Hà Nội, ngày 15/05/2009

Sinh viên

Bùi Tuấn Anh

TÓM TẮT NỘI DUNG

Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len Adleman,

công bố lần đầu vào tháng 8 năm 1977. Hệ mật sử dụng trong lĩnh vực đảm bảo tính

riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay, RSA đã được phát

triển ứng dụng rộng rãi trong thương mại điện tử và đặc biệt nó là hạt nhân của hệ

thống thanh toán điện tử.

Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ số an toàn bởi

nhiều nhà nghiên cứu. Mặc dù đã trải qua nhiều năm nghiên cứu và đã có một số cuộc

tấn công ấn tượng nhưng không mang lại kết quả là phá huỷ. Đa phần họ mới chỉ ra

được những mối nguy hiểm tiềm ẩn của RSA mà khi sử dụng RSA người dùng cần cải

thiện.

Thực tế vấn đề thám mã đối với hệ mật RSA hiện tại đang được các nhà nghiên

cứu tập trung khai thác các sơ hở của RSA như: tấn công vào số mũ công khai hoặc số

mũ bí mật thấp, tấn công vào các tham số nguyên tố p, q bé hoặc cách xa nhau lớn,

hoặc tập trung vào việc phân tích nhân tử số n(modul của RSA).

Luận văn của em sẽ trình bày các phương pháp tấn công RSA trong vòng 20

năm trở lại đây và lựa chọn môt phương pháp tấn công phổ biến để demo.

Mục lục

MỞ ĐẦU ................................................................................................................. 1

Chương 1. CÁC KHÁI NIỆM CƠ BẢN............................................................. 2

1.1 Một số khái niệm toán học........................................................................ 2

1.1.1 Số nguyên tố và nguyên tố cùng nhau................................................. 2

1.1.2 Đồng dư thức ...................................................................................... 2

*

1.1.3 Không gian Z_nvà Z_n........................................................................... 3

1.1.4 Phần tử nghịch đảo............................................................................. 3

1.1.5 Khái niệm nhóm, nhóm con, nhóm Cyclic .......................................... 4

1.1.6 Hàm Ф Euler....................................................................................... 4

1.1.7 Các phép toán cơ bản trong không gian modulo................................ 5

1.1.8 Độ phức tạp tính toán ......................................................................... 5

1.1.9 Hàm một phía và hàm một phía có cửa sập........................................ 6

1.2 Vấn đề mã hóa............................................................................................ 7

1.2.1 Giới thiệu về mã hóa........................................................................... 7

1.2.2 Hệ mã hóa........................................................................................... 7

1.2.3 Những tính năng của hệ mã hóa......................................................... 8

Chương 2. TỔNG QUAN VỀ MÃ HOÁ CÔNG KHAI MÃ THÁM................ 9

2.1 Mã hoá khoá công khai ............................................................................. 9

2.1.1 Đặc điểm của Hệ mã khoá công khai ................................................. 9

2.1.2 Nơi sử dụng Hệ mã hóa khoá công khai.......................................... 10

2.2 Các bài toán liên quan đến hệ mã hoá khoá công khai...................... 10

2.2.1 Bài toán phân tích số nguyên thành thừa số nguyên tố................... 11

2.2.2 Bài toán RSA (Rivest-Shamir-Adleman).......................................... 11

2.2.3 Bài toán thặng dư bậc hai................................................................ 11

2.2.4 Bài toán tìm căn bậc hai mod n ....................................................... 12

2.2.5 Bài toán lôgarit rời rạc.................................................................... 13

2.2.6 Bài toán lôgarit rời rạc suy rộng..................................................... 13

2.2.7 Bài toán Diffie-Hellman................................................................... 13

2.2.8 Bài toán giải mã đối với mã tuyến tính............................................ 14

2.3 Vấn đề thám mã....................................................................................... 16

Chương 3. TỔNG KẾT NHỮNG KẾT QUẢ TẤN CÔNG VÀO HỆ MẬT RSA

TRONG NHỮNG NĂM QUA ............................................................................ 19

3.1 Một số giả thiết ngầm định ..................................................................... 19

3.2 Phân tích các số nguyên lớn................................................................... 19

3.3 Các tấn công cơ bản ............................................................................... 20

3.3.1 Modul chung ..................................................................................... 20

3.3.2 Mù (Blinding)................................................................................... 21

3.4 Số mũ riêng bé (Low Private Exponnent)............................................ 21

3.4.1 Độ lớn e............................................................................................. 22

3.4.2 Sử dụng CRT .................................................................................... 22

3.5 Số mũ công khai bé (Low public Exponent) ........................................ 23

3.5.1 Hastad's Broadcast Attack............................................................... 23

3.5.2 Franklin-Reiter Related Message Attack......................................... 24

3.6 Thành phần công khai bé....................................................................... 24

3.6.1 Coppersmith's Short Pad Attack. ..................................................... 25

3.6.2 Tấn công bằng khóa riêng. .............................................................. 25

3.7 Cài đặt các tấn công. .............................................................................. 26

3.7.1 Tấn công dựa trên thời gian. ............................................................ 27

3.7.2 Tấn công dựa trên các lỗi ngẫu nhiên. ............................................ 28

3.8 Một số tấn công bằng nhân tử hóa số N với số N lớn.......................... 29

3.8.1 Tìm nhân tử lớn nhất thứ nhất ≤ N ............................................... 29

3.8..2 Phân tích thứ hai............................................................................. 30

3.8.3 Phân tích thứ ba............................................................................... 31

3.8.4 Thuật toán Pollard (p-1)................................................................... 32

3.9 Kết luận ................................................................................................... 33

Chương 4. THƯ VIỆN TÍNH TOÁN SỐ LỚN................................................. 34

4.1 Biểu diễn số lớn........................................................................................ 34

4.2 Các phép toán trong số lớn..................................................................... 35

4.2.1 So sánh hai số ................................................................................... 35

4.2.2 Cộng hai số lớn dương...................................................................... 36

4.2.3 Trừ hai số lớn dương ........................................................................ 36

4.2.4 Phép nhân hai số lớn. ....................................................................... 37

4.2.5 Phép chia hai số lớn dương. ............................................................. 38

4.2.6 Lũy thừa ............................................................................................ 40

4.2.7 Ước chung lớn nhất........................................................................... 41

4.2.8 Phép nhân theo module p.................................................................. 42

4.2.9 Tìm phần từ nghịch đảo theo module p ............................................ 42

4.2.10 Phép cộng có dấu............................................................................ 43

4.2.11 Phép trừ có dấu............................................................................... 44

4.3.12 Phép nhân có dấu............................................................................ 44

Chương 5. PHƯƠNG PHÁP TẤN CÔNG BẰNG............................................ 45

NHÂN TỬ HOÁ SỐ N SỬ DỤNG ĐỊNH LÝ FERMAT................................. 45

5.1 Bổ đề 1....................................................................................................... 45

5.2 Định lý Fermat........................................................................................... 45

KẾT LUẬN........................................................................................................... 48

MỞ ĐẦU

Hệ mật mã khoá công khai RSA được sử dụng phổ biến trong lĩnh vực đảm bảo

tính riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay RSA được phát triển

và ứng dụng rộng rãi trong thương mại điện tử, được sử dụng trong việc tạo khoá và xác

thực của mail, trong truy cập từ xa, và đặc biệt nó là hạt nhân của hệ thống thanh toán

điện tử. RSA được ứng dụng rộng rãi trong các lĩnh vực nơi mà an ninh an toàn thông tin

được đòi hỏi.

Chính vì lý do được sử dụng rộng rãi trong thương mại điện tử cũng như có độ an

toàn cao mà đã có rất nhiều sự nhòm ngó cũng như các cuộc tấn công nhằm phá vỡ sự an

toàn của hệ mật RSA. Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ

số an toàn bởi nhiều nhà nghiên cứu. Mặc dù trải qua nhiều năm nghiên cứu và đã có một

số cuộc tấn công ấn tượng nhưng không mang lại kết quả là phá huỷ. Đa phần họ mới chỉ

ra được những mối nguy hiểm tiềm ẩn của RSA.

Để phục vụ cho việc phân tích các tính chật của hệ mật RSA, em đã trình bày các khái

niệm cơ bản liên quan đến toán học, mật mã và thám mã , trình bày tổng quan về hệ mã

hoá khoá công khai, các bài toán liên quan đến hệ mã hoá khoá công khai

Trên cơ sở hiểu các khái niệm cơ bản, các cơ sở toán học, để có cái nhìn tổng quan

về vấn đề thám mã đối với hệ mật RSA trong những năm qua, em đã tổng kết lại các

phương pháp tấn công vào hệ mật RSA và kết quả thu được trong những năm qua. Trong

chương này em đã trình bày chi tiết các thuật toán tấn công vào hệ mật RSA như: các tấn

công cơ bản - modul chung, mù, tấn công vào số mũ công khai hoặc số mũ bí mật thấp,

tấn công dựa trên thời gian hay dựa vào các lỗi ngẫu nhiên. Ngoài ra, em cũng trình bày

các thuật toán tấn công RSA bằng nhân tử hoá số N với số N lớn như thuật toán Pollard,

tuy nhiên các thuật toán được giới thiệu ở đây mới chỉ giải quyết cho modul N của RSA

có độ dài hạn chế, còn mudul N có độ dài lớn thì cho đến nay chưa có phương pháp khả

thi nào được công bố.

1

Chương 1 - CÁC KHÁI NIỆM CƠ BẢN

1.1 Một số khái niệm toán học

1.1.1 Số nguyên tố và nguyên tố cùng nhau

Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó.

Ví dụ: 2, 3, 5, 7, 11, 17, …

Hệ mật mã thường sử dụng các số nguyên tố ít nhất là lớn hơn 10¹⁵⁰.

Hai số m và n được gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất của chúng

bằng Ký hiệu: gcd (m, n) = 1.

Ví dụ: 9 và 14 là hai số nguyên tố cùng nhau.

1.1.2 Đồng dư thức

Cho a và b là các số nguyên n là số nguyên dương. Khi đó a được gọi là đồng dư với b

theo modulo n, ký hiệu là a ≡ b (mod n), nếu a, b chia cho n có cùng số dư. n được gọi là

modulo của đồng dư.

Kí hiệu: a ≡ b (mod n)

Ví dụ: 5 ≡ 7 mod 2 vì: 5 mod 2 = 1 và 7 mod 2 = 1

Tính chất của đồng dư:

Cho a, a₁, b, b₁, c ∈ Z. Ta có các tính chất sau:

-

a ≡ b mod n nếu và chỉ nếu a và b có cùng số dư khi chia cho n

Tính phản xạ: a ≡ a mod n

Tính đối xứng: Nếu a ≡ b mod n thì b ≡ a mod n

Tính giao hoán: Nếu a ≡ b mod n và b ≡ c mod n thì a ≡ c mod n

Nếu a ≡ a₁mod n, b ≡ b₁mod n

thì a + b ≡ (a₁+b₁) mod n và ab ≡ a₁b₁mod n

Lớp tương đương:

Lớp tương đương của số nguyên a là tập hợp các số nguyên đồng dư với a theo modulo n.

2

Cho n cố định đồng dư với n trong không gian Z vào các lớp tương đương. Nếu a = qn +

r, trong đó 0 ≤ r ≤ n thì a ≡ r mod n. Vì vậy mỗi số nguyên a là đồng dư theo modulo

n với duy nhất một số nguyên trong khoảng từ 0 đến n-1 và được gọi là thặng dư nhỏ

nhất của a theo modulo n. Cũng vì vậy, a và r cùng thuộc một lớp tương đương. Do

đó r có thể đơn giản được sử dụng để thể hiện lớp tương đương.

*

1.1.3 Không gian Z_nvà Z_n

Không gian Z_n(các số nguyên theo modulo n)

Không gian các số nguyên theo modulo n: Z_nlà tập hợp các số nguyên không âm nhỏ hơn

n.

Tức

là:

Z_n

=

{0,

1,

2,

…

n-1}.

Tất cả các phép toán trong Z_nđều được thực hiện theo modulo n.

Ví dụ: Z₁₁= {0, 1, 2, 3, …, 10}

Trong Z₁₁: 6 + 7 = 2, bởi vì 6 + 7 = 13 ≡ 2 (mod 11).

*

Không gian Z_n

Là tập hợp các số nguyên p ∈ Z_n, nguyên tố cùng n.

*

Tức là: Z_n= { p ∈ Z_n| gcd (n, p) = 1}, Ф(n) là số phần tử của Z_n

*

Nếu n là một số nguyên tố thì: Z_n= { p ∈ Z_n| 1 ≤ p ≤ n – 1}

*

Ví dụ: Z₂= {0, 1} thì Z₂= {1} vì gcd (1, 2) = 1.

1.1.4 Phần tử nghịch đảo

Định nghĩa:

Cho a ∈ Z_n. Nghịch đảo của a theo modulo n là số nguyên x ∈ Z_nsao cho ax ≡ 1(mod

n). Nếu x tồn tại thì đó là giá trị duy nhất, và a được gọi là khả nghịch.

Nghịch đảo của a ký hiệu là a^-1.

Tính chất:

• Cho a, b ∈ Z_n. Phép chia a cho b theo modulo n là tích của a và b theo modulo

n, và chỉ được xác định khi b có nghịch đảo theo modulo n.

• Cho a ∈ Z_n, a là khả nghịch khi và chỉ khi gcd (a, n) = 1.

3

• Giả sử d = gcd (a, n). Phương trình đồng dư ax = b mod n có nghiệm x nếu và

chỉ nếu d chia hết cho b, trong trường hợp các nghiệm d nằm trong khoảng 0

đến

n

–

1

thì các nghiệm đồng dư theo modulo n/d.

Ví dụ: 4^-1= 7 (mod 9) vì 4.7 ≡ 1 (mod 9)

1.1.5 Khái niệm nhóm, nhóm con, nhóm Cyclic

Nhóm là bộ các phần tử (G, *) thỏa mãn các tính chất sau:

• Tính chất kết hợp: ( x * y ) * z = x * s ( y * z )

• Tính chất tồn tại phần tử trung gian e ∈ G: e * x = x * e = x , ∀ x ∈ G

• Tính chất tồn tại phần tử nghịch đảo x’ ∈ G: x’ * x = x * x’ = e

Nhóm con là bộ các phần tử (S, *) là nhóm thỏa mãn các tính chất sau:

• S ∈ G, phần tử trung gian e ∈ S

• x, y ∈ S Î x * y ∈ S

Nhóm Cyclic: Là nhóm mà mọi phần tử x của nó được sinh ra từ một phần tử đặc biệt g

∈ G. Phần tử này được gọi là phần tử nguyên thủy, tức là:

Với ∀ x ∈ G: ∃ n ∈ N mà gⁿ= x.

Ví dụ: (Z⁺, *) là một nhóm cyclic có phần tử sinh là 1

1.1.6 Hàm Ф Euler

Định nghĩa: Cho n ≥ 1. Ф (n) được định nghĩa là các số nguyên trong khoảng từ [1, n]

nguyên tố cùng nhau với n. Hàm Ф được gọi là hàm phi Euler.

Tính chất:

- Nếu p là số nguyên tố thì Ф (n) = p - 1.

- Hàm phi Euler là hàm có tính nhân:

- Nếu (m, n) = 1 thì Ф (m*n) = Ф (m) Ф (n).

e1 e2

- Nếu n = p₁p₂…p_k^eklà thừa số nguyên tố của n thì :

⎛

⎞ ⎛

⎞

⎛

⎞

1

⎜

⎟ ⎜

⎟

⎜

⎟

Ф(n) = n 1−

1−

… 1−

⎜

⎝

⎜

⎝

p₁

p₂

p_n

⎠ ⎝

⎠

4

1.1.7 Các phép toán cơ bản trong không gian modulo

Cho n là số nguyên dương. Như trước, các phần tử trong Zn được thể hiện bởi các số

nguyên {0, 1, 2,…, n - 1}. Nhận xét rằng: nếu a, b ∈ Z_nthì:

a + b

if a + b < n

⎧

⎨

⎩

(a + b) mod n =

a + b − n if a + b ≥ n

Vì vậy, phép cộng modulo (và phép trừ modulo) có thể được thực hiện mà không

cần thực hiện các phép chia dài.

Phép nhân modulo của a và b được thực hiện bằng phép nhân thông thường a với b như

các số nguyên bình thường, sau đó lấy phần dư của kết quả sau khi chia cho n.

Phép tính nghịch đảo trong Z_ncó thể được thực hiện nhờ sử dụng thuật toán Euclidean

mở rộng như mô tả sau:

Nếu b=0 thì đặt d: =a; x: =1; y: =0; return (d; x; y) ;

Đặt x₂:=1; x₁:=0 ; y₂: =0 ; y₁: =1 ;

Khi b>0 thực hiện:

q: = [a/b]; r = a-qb; x: = x₂-px₁; y: = y₂- py₁;

a : =b; r: =b; x₁:=x₂; x₁:=x; y₂:=y₁; y₁:=y ;

d:=a ; x:=x₂; y:=y₂; return(d, x, y) ;

1.1.8 Độ phức tạp tính toán

Lý thuyết thuật toán và các hàm tính được ra đời từ những năm 30 của thế kỉ 20 đã

đặt nền móng cho việc nghiên cứu các vấn đề “tính được”, “giải được” trong toán học.

Tuy nhiên từ cái “tính được” đến việc tính toán thực tế là một khoảng cách rất lớn. Có rất

nhiều vấn đề được chứng minh là có thể “tính được” nhưng không tính được trong thực tế

cho dù có sự hỗ trợ của máy tính. Vào những năm 1960, lý thuyết độ phức tạp tính toán

được hình thành và phát triển một cách nhanh chóng, cung cấp nhiều hiểu biết sâu sắc

về bản chất phức tạp của các thuật toán và các bài toán, từ những bài toán thuần túy

lý thuyết đến những bài toán thường gặp trong thực tế.

Độ phức tạp tính toán (về không gian hay thời gian) của một tiến trình tính toán là

số ô nhớ được dùng hay số các phép toán sơ cấp được thực hiện trong tiến trình tính toán

5

đó. Dữ liệu đầu vào đối với một thuật toán thường được biểu diễn qua các từ trong một

bảng ký tự nào đó. Độ dài của một từ là số ký tự trong từ đó.

Cho một thuật toán A trên bảng ký tự Z (tức là có các đầu vào là các từ trong Z).

Độ phức tạp tính toán của thuật toán A được hiểu như một hàm số f_a(n) sao cho với mỗi

số n thì f_a(n) là số ô nhớ, hay số phép toán sơ cấp tối đa mà A cần để thực hiện tiến trình

tính toán của mình trên các dữ liệu vào có độ dài nhỏ hơn hoặc bằng n. Ta nói: thuật toán

A có độ phức tạp thời gian đa thức, nếu có một đa thức P(n) sao cho với mọi n đủ lớn ta

có:

f_a(n) ≤ p(n), trong đó f_a(n) là độ phức tạp tính toán theo thời gian của A.

Bài toán P được gọi là “giải được” nếu tồn tại thuật toán để giải nó, tức là thuật

toán làm việc có kết thúc trên mọi dữ liệu đầu vào của bài toán. Bài toán P được gọi là

“giải được trong thời gian đa thức” nếu có thuật toán giải nó với độ phức tạp thời gian đa

thức.

1.1.9 Hàm một phía và hàm một phía có cửa sập

Hàm một phía:

Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng rất

khó để tính ngược lại. Ví như : Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhưng nếu

biết f(x) thì rất khó tính ra được x. Trong trường hợp này “khó” có nghĩa là để tính ra

được kết quả thì phải mất rất nhiều thời gian để tính toán.

Ví dụ:

Tính y = f(x) = α^xmod p là dễ nhưng tính ngược lại x = log_αy là bài toán “khó”

(bài toán logarit rời rạc)

Hàm một phía có cửa sập:

F(x) được gọi là hàm một phía có cửa sập nếu tính xuôi y = f (x) thì dễ nhưng tính

ngược x = f - 1(y) thì khó tuy nhiên nếu có “cửa sập” thì vấn đề tính ngược trở nên dễ

dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngược.

Ví dụ:

6

y = f (x) = x^bmod n tính xuôi thì dễ nhưng tính ngược x = y^amod n thì khó vì phải biết a

với a * b ≡ 1 (mod (Ф (n)) trong đó Ф(n) = (p-1)(q-1). Nhưng nếu biết cửa sập p, q thì

việc tính n = p * q và tính a trở nên dễ dàng.

Hộp thư là một ví dụ khác về hàm một phía có cửa sập. Bất kỳ ai cũng có thể bỏ

thư vào thùng. Bỏ thư vào thùng là một hành động công cộng. Mở thùng thư không phải

là hành động công cộng. Nó là khó khăn, bạn sẽ cần đến mỏ hàn để phá hoặc những

công cụ khác. Tuy nhiên, nếu bạn có “cửa sập” (trong trường hợp này là chìa khóa của

hòm thư) thì công việc mở hòm thư thật dễ dàng.

1.2 Vấn đề mã hóa

1.2.1 Giới thiệu về mã hóa

Chúng ta biết rằng thông tin truyền đi trên mạng rất dễ bị trộm cắp. Để đảm bảo việc

truyền tin an toàn, người ta thường mã hóa thông tin trước khi truyền đi. Việc mã hóa cần

theo quy tắc nhất định gọi là hệ mật mã. Hiện nay có hai loại mật mã: hệ mật mã khóa bí

mật và hệ mật mã khóa công khai. Hệ mật mã khóa bí mật (còn gọi là hệ mật mã đối

xứng hay hệ mật mã cổ điển) dễ hiểu, dễ thực thi nhưng độ an toàn không cao. Vì giới

hạn tính toán chỉ thực hiện trong phạm vi bảng chữ cái sử dụng văn bản cần mã hóa (ví

dụ Z₂₆nếu dùng các chữ cái tiếng anh, Z₂₅₆nếu dùng chữ cái ASCII…). Với các hệ mã

khóa bí mật, nếu biết khóa lập mã hay thuật toán lập mã, người ta có thể tìm thấy ngay

được bản rõ. Ngược lại, các hệ mật mã khóa công khai (còn gọi là hệ mật mã phi đối

xứng) cho biết khóa lập mã K và hàm lập mã e_k, thì cũng rất khó tìm được cách giải mã.

Và việc thám mã là rất khó khăn do độ phức tạp tính toán lớn.

1.2.2 Hệ mã hóa

Hệ mã hóa là hệ bao gồm 5 thành phần (P, C, K, E, D) thỏa mã các tính chất sau:

P (Plaitext): là tập hợp hữu hạn các bản rõ có thể:

C (Ciphertext): là một tập hữu hạn các bản mã có thể.

K (Key): là một tập hữu hạn các khóa có thể.

E (Encrytion): là tập các hàm lập mã.

D (Decrytion): là tập các hàm giải mã.

7

Chúng ta đã biết một thông báo thường được xem là bản rõ. Người gửi sẽ có nhiệm vụ

mã hóa bản rõ đó, kết quả thu được gọi là bản mã. Và bản mã này sẽ được gửi đi trên

đường truyền tới người nhận. Người nhận giải mã bản mã để tìm hiểu nội dung của bản

rõ.

Với mỗi k ∈ K, có một hàm lập mã e_k∈ E, e_k: P ÆC , và một hàm giải mã

d_k∈D, d_k: C Æ P sao cho: d_x(e_k(x)) = x, ∀ x∈P

1.2.3 Những tính năng của hệ mã hóa

- Cung cấp một mức cao về tính toán bảo mật, toàn vẹn, chống chối bỏ và xác thực.

- Tính bảo mật: Bảo đảm bí mật cho các thông báo và dữ liệu bằng việc che giấu

thông tin nhờ các kỹ thuật mã hóa.

- Tính toàn vẹn: Bảo đảm với các bên rằng bản tin không bị thay đổi trên đường

truyền tin.

- Chống chối bỏ: Có thể xác nhận rằng tài liệu đã đến từ ai đó, ngay cả khi họ cố

gắng từ chối nó.

- Tính xác thực: Cung cấp hai dịch vụ:

o Nhận dạng nguồn gốc của một thông báo, đảm bảo rằng nó là đúng sự thực.

o Kiểm tra định danh của người đang đăng nhập hệ thống, tiếp tục kiểm tra đặc điểm

của họ trong trường hợp ai đó cố gắng kết nối và giả danh là người sử dụng hợp

pháp.

8

Chương 2 - TỔNG QUAN VỀ MÃ HOÁ CÔNG KHAI VÀ MÃ THÁM

2.1 Mã hoá khoá công khai

Hệ mã hóa khóa bất đối xứng( hệ mã hoá khoá công khai) là Hệ mã hóa có khóa lập

mã và khóa giải mã khác nhau (ke ≠ kd), biết được khóa này cũng “khó” tính được khóa

kia.

Hệ mã hóa này còn được gọi là Hệ mã hoá khóa công khai, vì:

Khoá lập mã cho công khai, gọi là khoá công khai (Public key).

Khóa giải mã giữ bí mật, còn gọi là khóa riêng (Private key) hay khóa bí mật.

Một người bất kỳ có thể dùng khoá công khai để mã hoá bản tin, nhưng chỉ người nào có

đúng khoá giải mã thì mới có khả năng đọc được bản rõ.

Hệ mã hóa khoá công khai hay Hệ mã hó bất đối xứng do Diffie và Hellman

minh vào những năm 1970.

phát

2.1.1 Đặc điểm của Hệ mã khoá công khai

Ưu điểm:

1). Hệ mã hóa khóa công khai có ưu điểm chủ yếu sau:

Thuật toán được viết một lần, công khai cho nhiều lần dùng, cho nhiều người dùng,

họ chỉ cần giữ bí mật khóa riêng của mình.

2). Khi biết các tham số ban đầu của hệ mã hóa, việc tính ra cặp khoá công khai

và bí mật phải là “dễ”, tức là trong thời gian đa thức.

Người gửi có bản rõ P và khoá công khai, thì “dễ” tạo ra bản mã C.

Người nhận có bản mã C và khoá bí mật, thì “dễ” giải được thành bản rõ P.

3). Người mã hoá dùng khóa công khai, người giải mã giữ khóa bí mật. Khả

năng lộ khóa bí mật khó hơn vì chỉ có một người giữ gìn.

Nếu thám mã biết khoá công khai, cố gắng tìm khoá bí mật, thì chúng phải

đương đầu với bài toán “khó”.

4). Nếu thám mã biết khoá công khai và bản mã C, thì việc tìm ra bản rõ P cũng

là bài toán “khó”, số phép thử là vô cùng lớn, không khả thi.

9

Hạn chế:

Hệ mã hóa khóa công khai: mã hóa và giải mã chậm hơn hệ mã hóa khóa đối

xứng.

2.1.2 Nơi sử dụng Hệ mã hóa khoá công khai

Hệ mã hóa khóa công khai thường được sử dụng chủ yếu trên các mạng công

khai như Internet, khi mà việc trao chuyển khoá bí mật tương đối khó khăn.

Đặc trưng nổi bật của hệ mã hoá công khai là khoá công khai (public key) và bản

mã (ciphertext) đều có thể gửi đi trên một kênh truyền tin không an toàn.

Có biết cả khóa công khai và bản mã, thì thám mã cũng không dễ khám phá

được bản rõ.

Nhưng vì có tốc độ mã hóa và giải mã chậm, nên hệ mã hóa khóa công khai chỉ

dùng để mã hóa những bản tin ngắn, ví dụ như mã hóa khóa bí mật gửi đi.

Hệ mã hóa khóa công khai thường được sử dụng cho cặp người dùng thỏa thuận

khóa bí mật của Hệ mã hóa khóa riêng.

2.2 Các bài toán liên quan đến hệ mã hoá khoá công khai

Sự ra đời của khái niệm hệ mã bất đối xứng là một tiến bộ có tính chất bước ngoặt trong

lịch sử mật mã nói chung, gắn liền với sự phát triển của khoa học tính toán hiện đại. Mã

hóa bất đối xứng là một dạng mật mã hóa cho phép người sử dụng trao đổi các thông tin

mật mà không cần phải trao đổi các khóa chung bí mật trước đó. Điều này được thực hiện

bằng cách sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa

cá nhân (hay khóa bí mật). Trong mã bất đối xứng, khóa cá nhân phải được giữ bí mật

trong khi khóa công khai được phổ biến công khai. Trong 2 khóa, một dùng để mã hóa và

khóa còn lại dùng để giải mã. Điều quan trọng đối với hệ thống là không thể tìm ra khóa

bí mật nếu chỉ biết khóa công khai. Hệ thống mã bất đối xứng có thể sử dụng với các mục

đích như:

•

Mã hóa: giữ bí mật thông tin và chỉ có người có khóa bí mật mới giải mã được.

Tạo chữ ký số: cho phép kiểm tra một văn bản có phải đã được tạo với một khóa

bí mật nào đó hay không.

10

•

Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin mật giữa 2

bên.

Các kỹ thuật mã bất đối xứng đòi hỏi khối lượng tính toán nhiều hơn các kỹ thuật mã hóa

khóa đối xứng nhưng những lợi điểm mà chúng mang lại khiến cho chúng được áp dụng

trong nhiều ứng dụng. Các hệ mã bất đối xứng dựa trên tính chất của các bài toán cơ bản

như:

2.2.1 Bài toán phân tích số nguyên thành thừa số nguyên tố

Cho số nguyên dương n , tìm tất cả các ước số nguyên tố của nó, hay là tìm dạng

phân tích chính tắc của n = p₁^α¹.p₂^α²...p_k^α^k, trong đó pi là các số nguyên tố từng cặp khác

nhau và các α_i≥ 1.

Bài toán này có liên hệ mật thiết với các bài toán thử tính nguyên tố hay thử tính

hợp số của một số nguyên, nhưng với những gì mà ta biết đến nay, nó dường như khó

hơn nhiều so với hai bài toán thử tính nguyên tố và tính hợp số.

2.2.2 Bài toán RSA (Rivest-Shamir-Adleman)

Cho số nguyên dương n là tích của hai số nguyên tố lẻ khác nhau, một số nguyên

dương e sao cho gcd(e,φ (n)) =1, và một số nguyên c ; tìm một số nguyên m sao cho

m^e≡ c(mod n).

Điều kiện gcd(e,φ (n)) =1 bảo đảm cho việc với mỗi số nguyên c ∈ {0,1,...,n -1}

có đúng một số m ∈ {0,1,...,n -1} sao cho m^e≡ c(mod n).

Dễ thấy rằng nếu biết hai thừa số nguyên tố của n, tức là biết n =p.q thì sẽ biết φ

(n) = (p -1)(q -1), và từ đó, do gcd(e,φ (n)) =1 sẽ tìm được d =e ^-1modφ (n), và do đó sẽ

tìm được m =c ^dmodn. Như vậy, bài toán RSA có thể qui dẫn trong thời gian đa thức về

bài toán phân tích số nguyên.

2.2.3 Bài toán thặng dư bậc hai

Cho một số nguyên lẻ n là hợp số, và một số nguyên a ∈Jn , tập tất cả các số a có

ký hiệu Jacobi. Hãy quyết định xem a có là thặng dư bậc hai theo modn hay không?

Trong lý thuyết mật mã, bài toán này cũng thường được xét với trường hợp n là

số nguyên Blum, tức n là tích của hai số nguyên tố p và q , n =p.q. Ta chú ý rằng trong

11

trường hợp này, nếu a ∈Jn , thì a là thặng dư bậc hai theo modn, điều này có thể thử

được dễ dàng vì nó tương đương với điều kiện a ^{(p -1)/2}≡ 1 (modp). Như vậy, trong trường

hợp này, bài toán thặng dư bậc hai có thể qui dẫn trong thời gian đa thức về bài toán phân

tích số nguyên. Mặt khác, nếu không biết cách phân tích n thành thừa số nguyên tố thì

cho đến nay, không có cách nào giải được bài toán thặng dư bậc hai trong thời gian đa

thức. Điều đó củng cố thêm niềm tin rằng bài toán thặng dư bậc hai và bài toán phân tích

số nguyên là có độ khó tương đương nhau.

2.2.4 Bài toán tìm căn bậc hai mod n

Cho một số nguyên lẻ n là hợp số Blum, và một số a ∈Qn , tức a là một thặng dư

bậc hai theo modn . Hãy tìm một căn bậc hai của a theo modn, tức tìm x sao cho x ²≡ a

(modn).

Nếu biết phân tích n thành thừa số nguyên tố, n =p.q , thì bằng cách giải các

phương trình x ²≡ a theo các modp và modq, rồi sau đó kết hợp các nghiệm của chúng lại

theo định lý số dư Trung quốc ta sẽ được nghiệm theo modn , tức là căn bậc hai của a

2

theo modn cần tìm. Vì mỗi phương trình x ≡ a theo modp và modq có hai nghiệm

(tương ứng theo modp và modq ), nên kết hợp lại ta được bốn nghiệm, tức bốn căn bậc

hai của a theo modn. Người ta đã tìm được một số thuật toán tương đối đơn giản (trong

thời gian đa thức) giải phương trình x ²≡ a (modp) với p là số nguyên tố. Như vậy, bài

toán tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài toán phân tích số

nguyên. Ngược lại, nếu có thuật toán Α giải bài toán tìm căn bậc hai modn thì cũng có

thể xây dựng một thuật toán giải bài toán phân tích số nguyên như sau: Chọn ngẫu nhiên

một số x với gcd(x,n) =1, và tính a =x²modn. Dùng thuật toán Α cho a để tìm một căn bậc

hai modn của a. Gọi căn bậc hai tìm được đó là y. Nếu y ≡ ±x (modn), thì phép thử coi

như thất bại, và ta phải chọn tiếp một số x khác. còn nếu y !≡ ±x (modn), thì gcd(x-y, n)

chắc chắn là một ước số không tầm thường của n, cụ thể là p hay là q. Vì n có 4 căn bậc

hai modn nên xác suất của thành công ở mỗi lần thử là 1/2, và do đó số trung bình (kỳ

vọng toán học) các phép thử để thu được một thừa số p hayq của n là 2, từ đó ta thu được

một thuật toán giải bài toán phân tích số nguyên (Blum) với thời gian trung bình đa thức.

Tóm lại, theo một nghĩa không chặt chẽ lắm, ta có thể xem hai bài toán phân tích số

nguyên và tìm căn bậc hai modn là khó tương đương nhau.

12

2.2.5 Bài toán lôgarit rời rạc

Cho số nguyên tố p, một phần tử nguyên thuỷ α theo modp (hay α là phần tử

nguyên thuỷ của Z^∗_p), và một phần tử β ∈Z^∗_p.Tìm số nguyên x (0≤ x ≤ p - 2) sao cho α ^x≡

β (modp).

Ta đã biết rằng trong trường hợp chung, cho đến nay chưa có một thuật toán nào

giải bài toán này trong thời gian đa thức. Bài toán này cũng được suy rộng cho các nhóm

cyclic hữu hạn như sau:

2.2.6 Bài toán lôgarit rời rạc suy rộng

Cho một nhóm cyclic hữu hạn G cấp n, một phần tử sinh (nguyên thuỷ) α của G,

và một phần tử β ∈G. Tìm số nguyên x (0≤ x ≤ n - 1) sao cho α ^x= β.

Các nhóm được quan tâm nhiều nhất trong lý thuyết mật mã là: nhóm nhân của

trường hữu hạn GF (p) - đẳng cấu với nhóm Z^∗_pcủa trường Zp ,nhóm nhân F₂^∗_mcủa

trường hữu hạn GF (2^m), nhóm nhân:

Z^∗= a :0 ≤ a ≤ n −1,gcd(a,n) =1

{

}

n

của trường Zn với n là hợp số, nhóm gồm các điểm trên một đường cong elliptic xác định

trên một trường hữu hạn, v.v...

2.2.7 Bài toán Diffie-Hellman

Cho số nguyên tố p, một phần tử nguyên thuỷ α theo modp (tức phần tử sinh của Z^∗_p), và

các phần tử α^amod p và α^bmod p .

Hãy tìm giá trị α^abmod p .

Có thể chứng minh được rằng bài toán Diffie-Hellman qui dẫn được về bài toán lôgarit

rời rạc trong thời gian đa thức. Thực vậy, giả sử có thuật toán Α giải bài toán lôgarit rời

rạc. Khi đó, cho một bộ dữ liệu vào của bài toán Diffie-Hellman gồm p, α ,α^amod p và

α^bmod p ; trước hết dùng thuật toán Α cho (p, α ,α^amod p ) ta tìm được a , và sau đó tính

được :

α^abmod p =(α^b)^amod p.

13

Người ta cũng chứng minh được hai bài toán lôgarit rời rạc và Diffie-Hellman là tương

đương về mặt tính toán trong một số trường hợp, ví dụ p -1 là B-mịn với B = O ((lnp)^c),c

là hằng số.

Tương tự như với bài toán lôgarit rời rạc, ta cũng có thể định nghĩa các bài toán Diffie-

Hellman suy rộng cho các nhóm cyclic hữu hạn khác.

2.2.8 Bài toán giải mã đối với mã tuyến tính

Mã tuyến tính là một lớp mã truyền tin có tính chất tự sửa sai được sử dụng trong

kỹ thuật truyền tin số hoá. Ta phát biểu bài toán giải mã đối với mã tuyến tính như sau:

Cho một ma trận cấp n xm A=(aij) gồm các thành phần là 0 hoặc 1, một vectơ y

=(y₁,y₂,...,ym) các giá trị 0 và 1, và một số nguyên dương K. Hỏi: có hay không một vectơ

x =(x₁,x₂,...,xn) gồm các số 0 hoặc 1 và có không nhiều hơn K số 1 sao cho với mọi j (1≤ j

≤ m):

n

x .a ≡ y (mod 2) ?

∑

i

ij

j

i=1

Chú ý rằng ở đây, x là vectơ thông tin, và y là vectơ mã, phép giải mã là tìm lại x

khi nhận được y, bài toán này tiếc thay lại là một bài toán khó; Berlekamp, McEliece và

Tilborg năm 1978 đã chứng minh nó thuộc lớp các bài toán Np đầy đủ !

Dựa trên các bài toán số học nêu trên, nhiều hệ mã bất đối xứng đã ra đời, trong

khuôn khổ luận văn này chúng ta đi sâu nghiên cứu hệ mật RSA. Hệ mật RSA được phát

minh bởi Ron Rivest, Adi Shamir, và Len Adleman [18], được đưa ra công khai lần đầu

tiên vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ. Hệ mật thường sử dụng cho việc

cung cấp sự riêng tư và bảo đảm tính xác thực của dữ liệu số. Sơ đồ chung của hệ mã

khoá công khai được cho bởi :

S = (P , C , K , E , D )

trong đó P là tập ký tự bản rõ, C là tập ký tự bản mã, K là tập các khoá K , mỗi khoá K

gồm có hai phần K =(K’,K''), K' là khoá công khai dành cho việc lập mật mã, còn K'' là

khoá bí mật dành cho việc giải mã. Với mỗi ký tự bản rõ x∈P , thuật toán lập mã E cho

ta ký tự mã tương ứng y =E (K', x) ∈ C , và với ký tự mã y thuật toán giải mã D sẽ cho ta

lại ký tự bản rõ x : D (K'', y) = D (K'', E (K', x)) =x.

14

Để xây dựng một hệ mã khoá công khai RSA, ta chọn trước một số nguyên n

=p.q là tích của hai số nguyên tố lớn, chọn một số e sao cho gcd(e, φ (n)) =1, và tính số d

sao cho

e.d ≡ 1(modφ (n)).

Mỗi cặp K =(K’,K''), với K' =(n,e) và K'' = d sẽ là một cặp khoá của một hệ mật mã RSA

cụ thể cho một người tham gia.

Như vậy, sơ đồ chung của hệ mật mã RSA được định nghĩa bởi danh sách (1), trong đó:

P = C = Zn , trong đó n là một số nguyên Blum, tức là tích

nguyên tố;

của hai số

K = {K =(K’,K''): K' =(n,e) và K'' = d, gcd(e, φ (n)) =1,

e.d ≡ 1(modφ (n))};

E và D được xác định bởi:

E (K', x) = xe modn, với mọi x ∈P ,

D (K'', y) = yd modn, với mọi y ∈C .

Để chứng tỏ định nghĩa trên là hợp thức, ta phải chứng minh rằng với mọi cặp khoá K

=(K' ,K'' ), và mọi x ∈P , ta đều có

D (K'', E (K', x)) = x .

Thực vậy, do e.d ≡ 1(modφ (n)) ta có thể viết e.d = t .φ (n) +1. Nếu x nguyên tố

với n , thì dùng định lý Euler (xem 2.1.3) ta có

D (K'', E (K', x)) = x^ed≡ x^tφ(n)+1≡ x^tφ(n).x(mod n) = x.

Nếu x không nguyên tố với n , thì do n =p.q , hoặc x chia hết cho p và nguyên tố

với q, hoặc x chia hết cho q và nguyên tố với p, và

φ (n) =(p -1).(q -1),trong cả hai trường hợp ta đều có

x^tφ(n)+1≡ x(mod p),

x^tφ(n)+1≡ x(mod q);

từ đó suy ra x^tφ(n)+1≡ x(mod n), tức D (K'', E (K', x)) =x.

15

Tính bảo mật của RSA có độ khó tương đương với bài toán phân tích số

nguyên (Blum) thành thừa số nguyên tố. Do đó, giữ tuyệt mật khoá bí mật d, hay giữ

tuyệt mật các thừa số p,q , là có ý nghĩa rất quyết định đến việc bảo vệ tính an toàn của hệ

mật mã RSA.

2.3 Vấn đề thám mã

Mục tiêu của thám mã (phá mã) là tìm những điểm yếu hoặc không an toàn trong

phương thức mật mã hóa. Thám mã có thể được thực hiện bởi những kẻ tấn công ác ý,

nhằm làm hỏng hệ thống; hoặc bởi những người thiết kế ra hệ thống (hoặc những người

khác) với ý định đánh giá độ an toàn của hệ thống. Có rất nhiều loại hình tấn công thám

mã, và chúng có thể được phân loại theo nhiều cách khác nhau. Một trong những đặc

điểm liên quan là những người tấn công có thể biết và làm những gì để hiểu được thông

tin bí mật. Ví dụ, những người thám mã chỉ truy cập được bản mã hay không? hay anh ta

có biết hay đoán được một phần nào đó của bản rõ? hoặc thậm chí: Anh ta có chọn lựa

các bản rõ ngẫu nhiên để mật mã hóa? Các kịch bản này tương ứng với tấn công bản mã,

tấn công biết bản rõ và tấn công chọn lựa bản rõ.

Trong khi công việc thám mã thuần túy sử dụng các điểm yếu trong các thuật

toán mật mã hóa, những cuộc tấn công khác lại dựa trên sự thi hành, được biết đến như là

các tấn công side-channel. Nếu người thám mã biết lượng thời gian mà thuật toán cần để

mã hóa một lượng bản rõ nào đó, anh ta có thể sử dụng phương thức tấn công thời gian

để phá mật mã. Người tấn công cũng có thể nghiên cứu các mẫu và độ dài của thông điệp

để rút ra các thông tin hữu ích cho việc phá mã; điều này được biết đến như là thám mã

lưu thông

Nếu như hệ thống mã sử dụng khóa xuất phát từ mật khẩu, chúng có nguy cơ bị

tấn công kiểu duyệt toàn bộ (brute force), vì kích thước không đủ lớn cũng như thiếu tính

ngẫu nhiên của các mật khẩu. Thám mã tuyến tính và Thám mã vi phân là các phương

pháp chung cho mã hóa khóa đối xứng. Khi mã hóa dựa vào các vấn đề toán học như độ

khó NP, giống như trong trường hợp của thuật toán khóa bất đối xứng, các thuật toán như

phân tích ra thừa số nguyên tố trở thành công cụ tiềm năng cho thám mã. Ở luận văn này,

ta tập trung nghiên cứu vấn đề thám mã với RSA. Từ khi được công bố lần đầu, hệ RSA

đã được phân tích hệ số an toàn bởi nhiều nhà nghiên cứu. Mặc dầu với nhiều năm

nghiên cứu và đã có một số cuộc tấn công ấn tượng nhưng không mang lai kết quả (phá

16

hủy). Chúng ta chỉ ra những mối nguy hiểm của người sử dụng RSA cần cải thiện. Mục

đích của chúng ta là nghiên cứu, cài đặt tấn công và mô tả các công cụ toán học mà

chúng ta sử dụng.

Quá trình nghiên cứu của chúng ta tuân theo chuẩn ngầm định và sử dụng Alice

và Bob để biểu thị cho hai phía muốn truyền thông lẫn nhau. Chúng ta coi Marvin là kẻ

gian muốn tấn công nghe lén hay lấy trộm trộm thông tin giữa Alice và Bob. Ta bắt đầu

mô tả một phiên bản được đơn giản hóa của hệ mật RSA: Giả sử N=pq là tích của hai số

nguyên tố lớn cùng kích thước (mỗi số n/2 bít). Số N với kích thức 1024 bit, nghĩa là 309

số thập phân. Mỗi một nhân tử là 512 bit. Giả sử e, d là hai số nguyên thỏa mãn ed = 1

mod ϕ (N) với điều kiện ϕ (N) = (p − 1)(q − 1) là cấp của nhóm nhân trên Z^*. Chúng ta

N

gọi N là modul RSA, e là số mũ mã hóa và d là số mũ giải mã. Cặp (N,e) là khóa công

khai. Cặp (N,d) được gọi là khóa bí mật hay còn gọi là khóa riêng và chỉ có người nhận

mới được biết. Khóa bí mật dùng để giải mã bản mã.

Một thông điệp (message) là một số nguyên M ∈ Z^*. Để mã hóa M, một phép

N

tính C=M^emod N. Để giải mã bản mã, cần tính C^dmod N. Tức là:

C^d= M^ed= M (mod N)

Ở đây phương trình cuối cùng được chỉ ra bởi định lý Euler. Người ta xác định

(hay định nghĩa) hàm RSA là một ánh xạ f: x α x^emod N. Nếu d cho trước, hàm đó có

thể dễ dàng nghịch đảo được bằng cách dùng phương trình trên. Chúng ta coi d như là

một cửa sập (trapdoor) để nghịch đảo hàm f. Bản chất của việc tấn công là nghiên cứu độ

khó của hàm ngược (nghịch đảo) RSA khi không cho trước của sập d. Nói chính xác hơn,

cho trước bộ 3 (N,e,C), chúng ta muốn biết được độ khó của việc tìm căn bậc e của C

*

theo mod N (N = p.q) như thế nào khi chưa biết nhân tử của N. Vì Z_Nlà một tập hợp hữu

hạn nên người ta có thể liệt kê (đếm) được tất cả các phần tử của Z^*cho đến khi tìm

N

được đúng số nguyên (bức thông điệp) M cần tìm. Rất tiếc là thời gian thực hiện của

thuật toán để tìm được đúng số M có cấp N, nghĩa là kích cỡ đầu vào có cấp số mũ thì

thời gian chạy có cấp log₂N. Chúng ta quan tâm đến thuật toán có thời gian bé hơn, tính

bậc của n^cđiều kiện n=log₂N và c là một hằng số nhỏ (bé hơn 5), thực tế thuật toán tốt

hay không phụ thuộc vào kích thước đầu vào. Trong luận văn này chúng ta quan tâm đến

thuật toán được coi là có hiệu quả. Chúng ta tập trung chủ yếu vào nghiên cứu hàm

ngược của RSA để tấn công vào RSA. Việc khó khăn của tính hàm ngược RSA chính là

17

từ đầu vào ngẫu nhiên, được cho bởi (N,e,C), một kẻ tấn công không thể tìm ra bản rõ M.

Nếu cho trước (N,e,C), rất khó để tìm ra thông tin về M. Điều này được biết trong lý

thuyết an ninh an toàn. Chúng ta chỉ ra rằng RSA được mô tả ở trên là không an toàn: nếu

cho (N,e,C), chúng ta có thể dẽ dàng suy diễn ra một vài thông tin của bản rõ M (ví dụ,

ký tự Jacobi của M trên N được dễ dàng suy ra từ C). RSA có thể được an toàn ngữ nghĩa

bằng việc thêm các bít ngẫu nhiên vào quá trình xử lý mã hóa. Hàm RSA x α x^emod N

là một ví dụ về hàm của sập một chiều (trapdoor one-way function). Nó có thể được tính

toán dẽ dàng, nhưng như chúng ta đã biết không thể tính ngược hiệu quả nếu không có

(cửa sập) d ngoại trừ một vài trường hợp đặc biệt.

18

Chương 3 - TỔNG KẾT NHỮNG KẾT QUẢ TẤN CÔNG VÀO HỆ MẬT RSA

TRONG NHỮNG NĂM QUA

3.1 Một số giả thiết ngầm định

1) N – RSA modulus

2) e – số mũ mã hóa (encryption exponent)

3) d – số mũ giải mã (decryption exponent)

4) M – Thông điệp số nguyên (message integer), M ∈ Z^*

N

5) Alice, Bob là đại diện hai bên truyền thông điệp cho nhau, Marvin là kẻ

tấn công (attacker)

6) Hàm RSA là một ánh xạ f: x α x^emod N. Nếu d cho trước, hàm đó có

thể dễ dàng nghịch đảo được bằng cách dùng phương trình trên. Chúng ta coi d như là

một cửa sập (trapdoor) để nghịch đảo hàm f.

7) Chúng ta nghiên cứu độ khó của hàm ngược (nghịch đảo) RSA khi

không cho trước của sập d và nghiên cứu phương pháp tấn công RSA trong trường hợp

này.

8) Chúng ta quan tấm đến thuật toán hữu hiệu có thời gian bé, tính bậc của

n^cđiều kiện n=log₂N và c là một hằng số nhỏ (bé hơn 5).

9) Về mặt lý thuyết, nếu cho trước (N,e,C), rất khó để tìm ra thông tin về

M.

10) Tấn công vét cạn (brute-force attack) bằng cách phân tích các modulus,

thời gian chạy với số nguyên n-bít là exp((c + o(1))n^1/3log^2/3n) trong đó c < 2 .

3.2 Phân tích các số nguyên lớn

Vấn đề phân tích một số nguyên tố lớn thành tích các số nguyên tố khác nhau là

bài toán rất hấp dẫn và đã được nhiều nhà toán học quan tâm nghiên cứu; chẳng hạn [1],

[2], [3] tuy nhiên trong phạm vi của một luận văn cao học, em chỉ tập trung nghiên cứu

trong trường hợp N là tích của hai số nguyên tố phân biệt. sau đây là một số mệnh đề

quan trọng phục vụ việc tấn công cơ bản:

Mệnh đề 1:

19

Giả sử N là một số tự nhiên không chính phương (perfect square), tức N không phải là

bình phương đúng của một số nguyên tố, thỏa mãn điều kiện:

N – 1 > ϕ (N) > N – N^2/3

Khi đó N là tích của 2 số nguyên tố phân biệt.

Chứng minh:

Thật vậy, rõ ràng N không phải là số nguyên tố vì nếu N là số nguyên tố thì

ϕ (N) = N-1, trái với giả thiết. Do giả thiết N không phải là bình phương của một số

nguyên tố. Như vậy nếu N không phải là tích của 2 số nguyên tố phân biệt thì nó phải là

tích của nhiều hơn 2 số nguyên tố (không cần phân biệt). Giả sử p là số nguyên tố nhỏ

nhất của tích; Khi đó p ≤ N ^1/3do đó chúng ta có

1

ϕ (N) ≤ N(1- ) ≤ N(1 – N^-1/3) = N – N^2/3

p

Điều này mâu thuẫn với giả thiết. Vậy N = p.q trong đó p,q là 2 số nguyên tố lẻ, phân

biệt.

Chú ý: Mệnh đề đảo của mệnh đề 1 cũng đúng.

Mệnh đề 2:

Với (N,e) là khóa công khai của RSA. Cho trước khóa riêng d, người ta có thể

phân tích thành nhân tử môdul N=pq một cách hiệu quả. Ngược lại cho các thừa số của

N, người ta có thể khôi phục được d một cách có hiệu quả.

Từ các mệnh đề ở trên người ta đã đưa ra một số tấn công vào RSA sau đây:

3.3 Các tấn công cơ bản

3.3.1 Modul chung

Để tránh việc phân tích modul N = pq khác nhau cho các người dùng khác nhau,

chúng ta lấy N chung cho tất cả. Cùng một N được sử dung cho tất cả người sử dụng.

Trung tâm xác thực có thể cung cấp cho người sử dụng i với một cặp e_i, d_ivà người sử

dụng i có một khóa công khai là (N,e_i) và khóa riêng là (N,d_i).

Ban đầu chúng ta có: một bản mã C = M^eamod N cung cấp cho Alice không

được mã hóa bởi Bob, vì Bob không có d_a. Tuy nhiên điều này là nhầm lẫn và kết quả là

20

hệ thống không an toàn. Bằng mệnh đề 1 (ở trên) Bob có thể sử dụng các thành phần e_b

và d_bcủa mình để nhân tử hóa N. N bị nhân tử hóa bởi Bob có thể lấy được khóa riêng d_a

của Alice từ khóa công khai e_acủa cô ấy. Với cách tiếp cận này, theo Simmons chỉ ra

rằng một modul RSA không nên sử dụng quá một thực thể.

3.3.2 Mù (Blinding)

Marvin chọn ngẫu nhiên một số r ∈ Z^*và đặt M’ = r^eM mod N. Sau đó anh ta

N

nhờ Bob ký lên M’. Bob có thể cung cấp chứ ký của mình là S’ lên M’. Nhưng từ cách

tính S’= (M’)^dmod N, Marvin có thể đơn giản tính S = S’/r mod N để có được chữ ký

của Bob là S trên M.

S^e= (S’)^e/r^e= (M’)^ed/r^e= M’/r^e= M/(mod N)

3.4 Số mũ riêng bé (Low Private Exponnent)

Trong thực tế, để giải mã nhanh đòi hỏi số d nhỏ và điều này để lộ lỗ hổng mà kẻ tấn

công có thể thực hiện như sau. Trước hết ta nghiên cứu định lý Wiener

Định lý 1 (M. Wiener): Cho N = pq với q < p< 2q. Giả sử d < 1/3N^1/4. Cho trước (N,e)

với ed = 1 mod ϕ (N), Marvin có thể tìm được d hiệu quả.

Việc chứng minh định lý trên dựa trên xấp xỉ hóa phân số liên tục như sau:

Khi ed = 1 mod ϕ (N), tồn tại một số k thỏa mãn ed - kϕ (N) = 1

Vì thế:

e

k

1

−

=

ϕ(N)

d

dϕ(N)

k

e

Do đó,

là xấp xỉ của

. Mặc dù Marvin không biết ϕ (N), anh ta có thể sử

d

ϕ(N)

dụng N để xấp xỉ nó. Hơn nữa, từ ϕ (N) = N- p- q +1 và p + q-1< 3 N , chúng ta có | N -

ϕ (N) | < 3 N .

Sử dụng N thay vào ϕ (N), chúng ta có:

e

k

ed − kϕ(N) − kN + kϕ(N)

−

=

N

d

Nd

21

1− k(N − ϕ(N)) 3k N

3k

=

≤

=

Nd

d N

1

Bây giờ, kϕ (N) = ed – 1 < ed. Từ e < ϕ (N), chúng ta thấy rằng k < d < N^1/4. Vì thế ta

3

có:

e

k

1

−

≤

<

dN^{1/ 4}2d ²

N

d

k

e

Đây là hệ thức xấp xỉ cổ điển. Phân số

với d < N là xấp xỉ của

nên bị

d

N

chặn tại log₂N. Trong thực tế, tất cả các nhân tử thu được từ phân tích đều hội tụ tại kết

e

triển khai mở rộng phân số

[12, Th, 177]. Tất cả kết quả đó đều thu được từ việc tính

N

e

k

toán logN hội tụ của việc tính toán phân số . Một trong những kết quả đó sẽ là . Khi

N

d

k

đó ed - kϕ (N) = 1, chúng ta có gcd(k,d) = 1, và vì thế

là rút gọn phân số. Thuật toán

d

tìm khóa riêng d là thuật toán có thời gian tuyến tính.

3.4.1 Độ lớn e

Thay vì rút gọn e trong ϕ (N), ta sử dụng (N,e’) cho khóa công khai thỏa mãn e’ = e +

t.ϕ (N) trong đó số t lớn. Rõ ràng có thể sử dụng e’ thay thế e để mã hóa thông điệp. Tuy

nhiên, khi số e có giá trị lớn, theo chứng minh ở trên thì số k không thể nhỏ hơn. Một tính

toán đơn giản chỉ ra rằng nếu e’ > N^1.5thì sẽ không có vấn đề gì xẩy ra mặc dù số d nhỏ

và tấn công ở trên không thể thực hiện được. Nhưng điều bất tiện là số e lớn sẽ là tăng

thời gian mã hóa.

3.4.2 Sử dụng CRT

Một cách tiếp cận khác là sử dụng định lý đồng dư trung hoa (Chinese

Remainder Theorem - CRT). Ta chọn một số d sao cho cả d_p= d mod (p - 1) và d_p=d

mod (q - 1) đều nhỏ 128 bits. Để giải mã nhanh bản C ta có thể tiến hành: Trước hết ta

22

tính M_p= C^dpmod p và M_q= C^dqmod q . Sau đó sử dụng CRT để tính giá trị M ∈ Z_N

thỏa mãn M = M_pmod p và M = M_qmod q. Kết quả M phải thỏa mãn M = C^dmod N là

bắt buộc. Mặc dầu d_pvà d_qlà nhỏ song giá trị d mod ϕ (N) có thể lớn, tùy thuộc vào

ϕ (N). Theo kết quả, sự tấn công của định lý 2 không được áp dụng. Chúng ta lưu ý rằng

nếu (N,e) được biết thì kẻ địch có thể tấn công N trong thời gian O(min( dp , dq )), vì

thể d_pvà d_qkhông thể quá nhỏ.

Mặt khác ta không thể biết được điều gì xẩy ra đối với vấn đề an ninh này.

Chúng ta chỉ biết thông qua tấn công hữu hiệu của Wiener. Định lý 1 gần đây đã được cải

thiện bởi Boneh và Durfee [4], họ chỉ ra rằng số với d < N^0.292, kẻ tấn công có thể tính

được d từ (N,e). Kết quả này chỉ ra ranh giới của Wiener là không rõ ràng. Nó có vẻ như

là d< N^0.5, đây là một bài toán mở.

0.5

Bài toán mở : Cho N = pq và d < N . Nếu Marvin biết (N,e) với ed = 1 mod

ϕ (N) và e < ϕ (N), anh ta có thể tìm được d không ?

3.5 Số mũ công khai bé (Low public Exponent)

Định lý 2 (Coppersmith): Cho N là một số nguyên và f ∈ Z[x] là một đa thức mà có độ

đo là d. Đặt X = N^1/d-echo e ≥ 0. Sau đó biết (N,f) Marvin có thể tìm tất cả số nguyên |x₀|

< X thỏa mãn f(x₀) = 0 mod N. Thời gian chạy phụ thuộc vào thời gian chạy thuật toán

LLL với trên một lưới có khoảng cách là O(ω ) với ω = min(1/e, log₂N).

Định lý cung cấp một thuật toán có thể tìm kiếm hiệu quả tất cả gốc f của N ít

hơn X = N^1/d. Với X nhỏ hơn, thời gian chạy thuật toán cũng giảm. Sức mạnh của thuật

toán là có thể tìm được gốc của N trong thời gian đa thức. Định lý Coppersmith làm việc

rất hiệu quả với một số nguyên tố.

3.5.1 Hastad's Broadcast Attack.

Để đơn giản ta coi e_ilà thành phần công khai bằng 3. Marvin tìm ra M rất đơn giản nếu k

≥ 3. Thực vậy, Marvin có được C₁, C₂, C₃, thỏa mãn:

C₁= M³mod N₁, C2 = M³mod N2, C3 = M³mod N3.

Nên với e = 3, gửi các thông điệp giống nhau đến 3 người nhận là không an toàn. Giải

pháp chống tấn công này chúng ta gắn các thông điệp trước khi mã hóa với đa thức ?

23