BAN CƠ YẾU CHÍNH PHỦ
HỌC VIỆN KỸ THUẬT MẬT MÃ

ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC
ĐỀ TÀI
NGHIÊN CỨU CÁC TẤN CÔNG LÊN HỆ MẬT RSA

Học viên thực hiện:
Khóa: 09
Chuyên ngành: An toàn thông tin
Người hướng dẫn: ThS Đinh Tiến Thành

Hà Nội, 2017

1


LỜI CẢM ƠN
Để thực hiện hoàn thành đồ án “ Nghiên cứu các tấn công lên hệ mật
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 giám đốc cùng
quý thầy cô trong khoa An toàn thông tin – Học viện kỹ thuật mật mã đã 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 ThS Đinh
Tiến Thành, 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

tháng

2017
Học viên thực hiện

2

năm


LỜI CAM ĐOAN
Em xin cam đoan bản đồ án này do em tự nghiên cứu dưới sự hướng dẫn
của thầy giáo ThS Đinh Tiến Thành.
Để hoàn thành đồ án này, em chỉ sử dụng những tài liệu đã ghi trong mục
tài liệu tham khảo, ngoài ra không sử dụng bất cứ tài liệu nào khác mà không
được ghi.
Nếu sai, em xin chịu mọi hình thức kỷ luật theo quy định của Học viện.
Hà Nội, ngày

tháng

2017
Học viên thực hiện

3

năm



MỤC LỤC
LỜI

CẢM

ƠN………………………………………………..

…………………...i
LỜI CAM ĐOAN……………………………………………..…………………ii
MỤC LỤC…………………………………………………….………………...iii

.…….48
TÀI

LIỆU

KHẢO……………………………………………………....49

4

THAM


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

5


CHƯƠNG I: HỆ MẬT MÃ CÔNG KHAI
1.1

1.2
1.2.1.1

1.2.1.2

Mục tiêu
Nghiên cứu tổng quan về hệ mật mã khóa công khai từ đó có thể hiểu
được và có cái nhìn tổng quan về hệ mật mã khóa công khai.
Các nội dung chính
1.2.1
Cơ sở toán học của hệ mật mã khóa công khai
Số nguyên tố
Số nguyên tố:

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước là 1 và chính nó.
Số p là số nguyên tố nếu nó không chia hết cho số nào trong đoạn [2, p1]
Một số ví dụ về số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, …
Số nguyên tố cùng nhau:
Hai số nguyên a, b được gọi là nguyên tố cùng nhau nếu ước chung lớn
nhất của chúng là 1.
a và b nguyên tố cùng nhau  gcd(a, b) = 1
Số nguyên tố an toàn:
Số nguyên tố an toàn là số nguyên tố có dạng 2p+1, với p cũng là số
nguyên tố. Các số nguyên tố an toàn (trừ số 7) đều có dạng 6k-1.
Đồng dư modulo
Cho số nguyên dương n, 2 số nguyên a và b được gọi là đồng dư modulo
n nếu chúng có cùng số dư khi chia cho n. Phép đồng dư là một quan hệ tương
đương (bao gồm các tính chất phản xạ, đối xứng, bắc cầu). Tập hợp các số
nguyên trong không gian modulo n tạo thành một vành với Abel với hai phép
toán cộng và nhân. Nếu n là số nguyên tố thì tập hợp đó là một trường.
Kí hiệu:
Ví dụ:
Một số tính chất:
Cho số nguyên dương n và 2 số nguyên a, b ta có một số tính chất sau:
•
•
•
•

Nghịch đảo modulo:
Một số nguyên x được gọi là nghịch đảo của số nguyên a trong không
gian modulo n nếu:
Hay


6


Ví dụ:
a

1
1

2
6

a

1
1

2
x

3
4
3
x

4
3
4
x


5
9
5
5

6
2
6
x

7
8
7
7

8
7
8
x

9
5
9
x

10
x

10
10

11
11

Số nguyên a chỉ tồn tại nghịch đảo modulo khi và chỉ khi a nguyên tố
cùng nhau với n.
Định lý fermat nhỏ:
Nếu p là số nguyên tố thì với số nguyên a bất kỳ ta sẽ có:
Hay:
Ví dụ:

1.2.1.3

Phi hàm Euler
Phi hàm euler của 1 số nguyên dương được định nghĩa là số các số
nguyên dương nhỏ hơn hoặc bằng n nguyên tố cùng nhau với n.
Ký hiệu:
Công thức:
Một số ví dụ:
n

7
6

8
4

9
6

10 11 12 15 20 27 30 40 50 64 81 100

4 10 4 8 8 18 8 16 29 32 54 40

Định lý euler:
Cho trước số nguyên dương n, với mọi số nguyên dương a nguyên tố
cùng nhau với n ta có:

1.2.1.4

Thặng dư bậc hai
Thặng dư bậc hai:
y được gọi là thặng dư bậc hai modulo n nếu tồn tại số nguyên dương x
sao cho:
7


Ví dụ:
Các giá trị thặng dư bậc 2 modulo 11
1
2
3
4
5
1
4
9
5
3

x


Các giá trị thặng dư bậc hai modulo 9
1
2
3
4
5
6
1
4
9
4
1
0

x

6
3

7
5
7
1

8
9
8
4

9

4
9
9

10
1
10
4

11
1

Các giá trị thặng dư bậc hai của một số modulo n
N
10
11
12
13
14
15
16
17
18
19
20

Thăng dư bậc 2 modulo n
1, 4, 5, 6, 9
1, 3, 4, 5, 9
1, 4, 9

1, 3, 4, 9, 10, 12
1, 2, 4, 7, 8, 9, 11
1, 4, 6, 9, 10
1, 4, 9
1, 2, 4, 8, 9, 13, 15, 16
1, 4, 7, 9, 10, 13, 16
1, 4, 5, 6, 7, 9, 11, 16, 17
1, 4, 5, 9, 16

Các giá trị trong đoạn [1,n-1] không phải là thặng dư bậc 2 modulo n
được gọi là các số bất thặng dư bậc hai hay không thặng dư bậc hai modulo n.
Ký hiệu Legendre:
Nếu p là số nguyên tố lẻ và số a nguyên tố cùng nhau với p ta có ký hiệu
legendre như sau:
Ký hiệu legengre có thể mang 1 trong 3 giá trị:

•
•
•

Trong đó ký hiệu legendre mang giá trị:
0 nếu
1 nếu a là thặng dư bậc 2 mod p và
-1 nếu a không thặng dư bậc 2 mod p
Theo tiêu chuẩn Euler, ký hiệu Lengendre có thể được tính bằng công

thức:
Tính chất:
8



Ký hiệu legendre có một số tính chất sau:
• Nếu thì ta có
•
•
Ví dụ:
a
p
3
5
7
11
13

•
•

1

2

3

4

5

6

7


8

9

10

11

12

1
1
1
1
1

-1
-1
1
-1
-1

0
-1
-1
1
1

1

1
1
1
1

-1
0
-1
1
-1

0
1
-1
-1
-1

1
-1
0
-1
-1

-1
-1
1
-1
-1

0

1
1
1
1

1
0
-1
-1
1

-1
1
1
0
-1

0
-1
-1
1
1

Ký hiệu Jacobi:
Ký hiệu Jacobi là khái niệm tổng quát của ký hiệu Legendre:
Với các số nguyên tố lẻ p ký hiệu Jacobi cũng chính là ký hiệu Legendre.
Với các số hợp số lẻ n, ký hiệu Jacobi được định nghĩa bằng tích các ký
hiệu Legendre tương ứng với các thừa số nguyên tố của n.
Nếu
thì

Ký hiệu Jacobi có thể mang 1 trong 3 giá trị:

•
•
•

Trong đó ký hiệu Legendre mang giá trị:
0 nếu
-1 nếu và a không thặng dư bậc hai modulo n.
1 nếu và a có thể thặng dư bậc hai modulo n hoặc không thặng dư bậc
hai modulo n.
Ví dụ:
1
2
3
4
5
6
7
8
9
10

1
4
9
16
25
36
49

64
81
100

1
1
0
1
0
0
-1
1
0
0

1
4
9
1
10
6
4
4
6
10
9


11
12

13
14

121
144
169
196

-1
0
-1
-1

1
9
4
1

Ta có:
•
nhưng 2 không thặng dư bậc hai modulo 15
•
và 4 là thặng dư bậc hai modulo 15
Do đó, khi Ký hiệu Jacobi mang giá trị 1 ta chỉ có thể kết luận
gcd(a, n) = 1, ngoài ra ta không thể kết luận được a có phải là thặng dư bậc hai
modulo n hay không.
1.2.1.5

Số dễ vỡ (B-smooth)
Số dễ vỡ là số nguyên mà có thể phân tích thành tích của các số nguyên

tố nhỏ.
Một số N được gọi là B-smooth nếu tất cả các thừa số nguyên tố của N
đều nhỏ hơn hoặc bằng B.
Ví dụ:
Ta có:
Nên 1620 là một số 5-smooth.

1.2.1.6

Nhóm, vành, trường
Nhóm
Nhóm là một tập hợp G cùng với phép toán 2 ngôi dùng kể kết hợp 2
phần tử bất kỳ thành một phần từ mới ký hiệu là ab. Một tập hợp (G,) muốn
được gọi là một nhóm khi thỏa mãn các điều kiện sau:
• Tính đóng:
o Với mọi a, b thuộc G thì ab cũng thuộc G
o
• Tính kết hợp:
o Với mọi a,b,c thuộc G thì (ab)c=a(bc)
o
• Phần tử đơn vị:
o Tồn tại duy nhất một phần tử sao cho đối với mỗi phần tử ,
phương trình được thỏa mãn.
o
• Phần tử nghịch đảo:
o Đối với mỗi phần tử , tồn tại một phần tử sao cho với e là phần
tử đơn vị.
o
Một nhóm được gọi là nhóm Abel nếu có thêm tính chất sau đây:
• Tính giao hoán:

o
Ví dụ:
10


Nhóm số nguyên hay tập hợp là một nhóm Abel với phép toán +. Khi
cộng 2 số nguyên với nhau ta luôn thu được số nguyên, do đó () có tính đóng.
Ngoài ra, ta còn có các tính chất:
Vành
Vành là một tập R với 2 phép toán 2 ngôi cộng và nhân. Một tập hợp (R,
+,*) được gọi là vành nếu thỏa các điều kiện sau:
• R là một nhóm Abel với phép toán cộng
o Tính đóng
o Tính kết hợp
o Phần tử đơn vị
o Phần tử nghịch đảo
o Tính giao hoán
• Phép nhân có tính phân phối với phép cộng
o
• Phép nhân có tính kết hợp
o
• Phép nhân có phần tử đơn vị:
o
Một vành được gọi là vành Abel nếu có them tính chất sau đây:
• Tính giao hoán đối với phép toán nhân.
o
Một vành được gọi là miền nguyên nếu nó là vành giao hoán và có thêm
tính chất sau:
• Liên quan giữa phép nhân và phần tử đơn vị phép cộng:
o Nếu

Ví dụ:
Tập hợp các số nguyên là vành Abel với phép toán cộng và phép toán
nhân. Như đã bàn ở trên, tập hợp các số nguyên là một nhóm Abel với phép
toán cộng. Ngoài ra, còn có các tính chất:
Tập hợp các số nguyên trong modulo N là vành Abel với phép toán
cộng và nhân. Với mọi số a,b,c thuộc thuộc ta có những tính chất sau:
• Tính đóng, khi cộng 2 số bất kỳ trong không gian modulo N, ta luôn
thu được 1 số trong không gian modulo N
• Tính kết hợp với phép cộng:
•

Phần tử đơn vị:

•

Tính nghịch đảo với phép cộng:

•

Tính giao hoán của phép cộng:

•

Phép nhân có tính phân phối với phép cộng:
11


•

Phép nhân có tính kết hợp:


•

Phép nhân có phần tử đơn vị:

•

Tính giao hoán với phép nhân:

Trường
Trường là một tập hơp F với 2 phép toán 2 ngôi cộng và nhân. Một tập
hợp (F,+,*) được gọi là trường nếu thỏa các điều kiện sau:
• F là một nhóm Abel với phép cộng
• F là một nhóm Abel với phép nhân
• Trên F, phép nhân phân phối với phép cộng
Ví dụ:
Tập hợp các số thực là một trường với 2 phép toán cộng và nhân. Khi
cộng hoặc nhân 2 số thực với nhau ta luôn được một số thực, do đó (F,+,*) có
tính đóng. Ngoài ra, còn có các tính chất:
Ví dụ:
Tập hợp các số nguyên trong modulo số nguyên tố p , là một trường với
2 phép toán cộng và nhân.Ta có các tính chất sau:
•
là một vành Abel với 2 phép toán cộng và nhân.
• Phép nhân có phần tử nghịch đảo: với số p nguyên tố ta có nên với
mọi a thuộc đều tồn tại phần tử thuộc sao cho
1.2.1.7

Hàm một chiều và cửa sập
Hàm số y = f(x) được gọi là hàm một chiều khi ta dễ dàng tính được y

với một số x cho trước, nhưng khi cho trước giá trị y rất khó để tìm được x.
“Khó” ở đây có nghĩa là bài toán không giải được trong thời gian tuyến tính, cần
phải tốn rất nhiều thời gian để giải được với khả năng tính toán cũng như mức
độ phát triển của công nghệ, toán học hiện tại.
Cho hai không gian S và T:
Hàm một chiều f được định nghĩa:
Với thì:
Cho x, ta dễ dàng tính được y trong thời gian tuyến tính
• Hàm là hàm ngược của hàm f rất khó tính được hay cho y, rất khó để
tìm được x thỏa .
Hàm một chiều có cửa sập: tương tự như hàm một chiều và có thêm một
tính chất:
• Hàm dễ dàng tính được khi chúng ta biết được một giá trị bí mật nào
đó (cửa sập)
Ví dụ:
•

12


Hàm là hàm một chiều, hàm f có thể tính được dễ dàng trong thời gian
tuyến tính bằng cách áp dụng thuật toán bình phương và nhân. Tuy nhiên, hàm
rất khó tính được (bài toán logarit rời rạc)
Hàm là hàm một chiều, hàm f có thể tính được dễ dàng trong thời gian
đa thức với thuật toán bình phương và nhân. Hàm được tính trong thời gian đa
thức, rất khó tính được trong thời gian tuyến tính. Tuy nhiên, nếu ta biết được số
ta dễ dàng tính được hàm bởi vì:
và có thể tính được trong thời gian tuyến tính.
1.2.2


Một số bài toán liên quan đến hệ mã công khai
Một số bài toán lý thuyết số liên quan tới hệ mã công khai
Các bài toán dễ
-

Các bài toán khó

Số học đồng dư
Lũy thừa đồng dư với thuật
toán bình phương và nhân
Tính ước chung lớn nhất với
giải thuật Euclid
Tính nghịch đảo modulo với
giải thuật Euclid mở rộng
Sàng nguyên tố Eratosthenes
Định lý số dư Trung Hoa
….

-

Bài toán phân tích nhân tử
Bài toán phân tích thừa số
nguyên tố
Bài toán thặng dư bậc hai
Bài toán logarit rời rạc
Bài toán Deffie-Hellman
Bài toán căn bậc hai modulo
n
….


Thuật toán Euclid
Thuật toán Euclid là thuật toán vô cùng quan trọng và hiệu quả trong lý
mật mã học. Thuật toán Euclid được dung để tính ước chung lớn nhất của hai số
nguyên khác 0.
Thuật toán có thể được mô tả như sau: Cho 2 số tự nhiên a và b khác 0,
kiểm tra nếu b bằng 0 thì a là ước chung lớn nhất cần tìm. Nếu không lặp lại xử
lý cho với cặp số là b và a mod b.
Giả sử a=bq +r với a, b, q, r là các số nguyên ta có:
1.2.2.1

Mã giả theo phương pháp đệ quy:
gcd(a,b)
{
//Neu b = 0
if (b==0):
// thi tra ve a
return a
//Ngược lại
else:
13


//thì trả về giá trị của hàm gcd (b,a mod b)
return gcd(b, a%b)
}
Ví dụ:
gcd(100, 170) = gcd(170, 100)
= gcd(100, 70)
= gcd(70, 30)
= gcd(30, 10)

= gcd(10, 0)
= 10
1.2.2.2 Thuật toán Euclid mở rộng
Giải thuật Euclid không chỉ được dung để tính ước chung lớn nhất của
hai số mà còn được dung để giải hệ phương trình nghiệm nguyên:
hoặc:
với d là ước chung lớn nhất của a và b.
Xét hai số tự nhiên a, b thỏa , ta có:

…

…

…

Trong đó số dư chính là gcd(a, b) và ta đã tìm thấy phương trình
Hay
Để tìm được các hệ số x, y chúng ta chỉ cần dùng công thức truy hồi để
tìm ra các cặp với i chạy từ 0 đến n.
Mã giả:
egcd(a,b)
{
x0, x1 = 1, 0
y0, y1 = 0, 1
while n != 0
{
q, a, b = a//b, b, a%b
x0, x1 = x1, x0 – q*x1
y0, y1 = y1, y0 – q*y1
}

return a, x0, y0
14


}
Ví dụ:
Giải phương trình
Phương trình đồng dư trên có thể chuyển thành:
i
1
2
3
4
5

q
x
5
4
1
2

x
1
0
1
-4
5

y

0
1
-5
21
26

a
803
154
33
22
11

b
154
33
22
11
0

Ta thu được d =11 và phương trình 803*(-4) +21*154 = 22.
Vậy x cần tìm có giá trị là 22.
1.2.2.3 Liên phân số
Liên phân số là một dạng biểu diễn của các số thực, số hữu tỉ hoặc vô tỉ,… dưới
dạng phân số nhiều tầng:
Các liên phân số còn có thể được biểu diễn dưới dạng
Trong giải thuật Euclid mở rộng thì chuỗi q chính là giá trị liên phân số của phân
số a/b
Mã giả:
Continue_fraction(a,b) //phân số

{
while ()
{
i=0
q[i] = a//b
a, b = b, a//b
}
return q
}
Thuật toán bình phương và nhân
Thuật toán bình phương và nhân là thuật toán tính nhanh lũy thừa tự
nhiên của một số. Thuật toán trở nên hiệu quả khi tính toán với số mũ tự nhiên
lớn.
Khi tính toán trong không gian modulo n, kết quả quá trình tính toán sẽ
không vượt quá
Thuật toán được xây dựng dựa trên tính chất:
1.2.2.4

15


Ví dụ:

Mã giả:
pow(x, e, n)
{
//Khoi tao gia tri trả về bằng 1
res=1
// vòng lặp để duyệt hết các bit của e
while e>0 //kiểm tra điều kiện dừng

{
// kiểm tra bit cuối của e, nếu giá trị bằng 1 thì trả về kết quả
//bằng x nhân với kết quả trước đó
If e%2==1 then
res=res*x (mod n)
//e = e div 2, duyệt bit tiếp theo của e
e = e >>1
//thay x bởi
x = x*x (mod n)
}
return res
}
I
1
2
3
4
5
6
7
8

Bit thứ i
0
0
0
1
0
0
1

1

e
100
50
25
12
6
3
1
0

res

X
1
1
1

Định lý số dư Trung Hoa
Định lý số dư Trung Hoa hay còn được gọi là bài toán Hàn Tín điểm
binh là một định lý để nói về cách giải hệ phương trình đồng dư bậc nhất.
1.2.2.5

16


Bài toán được định nghĩa như sau: cho số tự nhiên x và k số tự nhiên m
đôi một nguyên tố cùng nhau, dễ dàng tính được phần dư khi chia x cho tích
của k số m nếu chúng ta biết được phần dư khi chia x cho từng số m nêu trên

Cho
Dễ dàng tính được:
Với x là số tự nhiên cần tính, k số tự nhiên đôi một nguyên tố cùng nhau
và
Đặt
Hệ phương trình đồng dư trên có nghiệm duy nhất:
Ví dụ:
Bài toán Hàn Tín điểm binh.
Cho hệ phương trình đồng dư:
Ta có:
Từ đó tính được:
Ta thu được x hay x có dạng 68+105k ()
Bài toán phân tích nhân tử
Bài toán: cho số nguyên dương n lớn hơn 1, tìm một số a sao cho a là
ước của n
1.2.2.6

Bài toán phân tích thừa số nguyên tố
Bài toán: cho số nguyên dương n lớn hơn 1, tìm tất cả các ước số nguyên
tố của n
1.2.2.7

Bài toán logarit rời rạc
Bài toán: cho các số nguyên dương x, y, n, tìm số tự nhiên k sao cho
1.2.2.8

Bài toán RSA
Bài toán: cho các số nguyên dương x,y,n, tìm số tự nhiên x sao cho
1.2.2.9


Bài toán thặng dư bậc hai
Bài toán: cho 2 số nguyên dương y và n, kiểm tra xem y có phải là thặng
dư bậc hai modulo n hay không.
1.2.2.11 Bài toán căn bậc hai modulo n
Bài toán: cho số y là thặng dư bậc 2 modulo n, tìm số tự nhiên x sao cho
hay
1.2.2.10

1.2.2.12

Bài toán Deffie-Hellman
17


Bài toán: cho số nguyên tố , phần tử sinh , hai giá trị , tính
Sơ lược về mã hóa RSA
1.2.3.1 Giới thiệu
RSA là thuật toán mã hóa công khai được phát minh bởi Ron Rivest, Adi
Shamir và Len Adlemen, công bố lần đầu vào tháng 8 năm 1977 và được sử
dụng rộng rãi cho đến ngày nay. Đây là thuật toán mã hóa khóa công khai đầu
tiên được đưa vào sử dụng để mã hóa cũng như tạo chữ kí điện tử.
1.2.3.2 Khóa
a. Tạo khóa
Chọn 2 số nguyên tố p và q (để an toàn nên chọn 2 số nguyên tố lớn một
cách ngẫu nhiên không quá gần nhau và là số nguyên tố an toàn)
Tính:

1.2.3

n được gọi là modulus là không gian của mã hóa, bản rõ và bản mã của

mã hóa sẽ nằm trong khoảng từ 1 đến n-1
Tính phi hàm Euler của n:
Do với p và q là 2 số nguyên tố nên:
Chọn số e trong khoảng từ 1 đến sao cho e và nguyên tố cùng nhau hay
gcd(e,)=1
e được gọi là số mũ công khai
Tính số d với hay với
d được gọi là số mũ bí mật.
b. Khóa công khai
Khóa công khai bao gồm:
n được gọi là modulus
e được gọi là số mũ công khai hay số mũ mã hóa
c. Khóa bí mật
Khóa bí mật bao gồm:
n (n xuất hiện trong cả khóa công khai lẫn khóa bí mật)
d được gọi là số mũ bí mật hay số mũ giải mã
1.2.3.3

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

Mã hóa
Giả sử Alice muốn gửi cho Bob một văn bản, Alice cần phải:
• Biết khóa công khai của Bob: (n, e)
• Chuyển đoạn văn bản cần gửi thành 1 số nguyên m sao cho
và
gcd(m, n) = 1 (Nếu không gcd(m, n) sẽ tiết lộ q và p dẫn đến mã hóa
hoàn toàn không an toàn)
• Sau đó, Alice sử dụng số mũ công khai để tính:

•


Alice thu được bản mã c và gửi cho Bob
18


Giải mã
Sau khi nhận được bản mã c, Bob có thể dễ dàng tính lại được số nguyên
m bằng công thức:
và từ m chuyển thành đoạn văn bản ban đầu
Tính đúng đắn
Ta có bản rõ m cặp khóa công khai (e, n) và khóa bí mật (d, n)
Alice mã hóa bản rõ m thu được:
1.2.3.4

Bob nhận được bản mã c và giải mã:
Từ (1) và (2) ta được:
Theo định lý Euler ta có
Từ (3) và (4) ta được:
Ví dụ
Chọn p=131, q=173, e=17.
Tính
1.2.3.5

Tính

Tính

e*d = 17*13153
=223601
Mã hóa:

Chọn m = 97 được dùng để mã hóa
Giải mã

19


CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG LÊN HỆ MẬT RSA
2.1
Mục tiêu
Nghiên cứu một số phương pháp tấn công lên hệ mật RSA nhằm có cái
nhìn tổng quan về các phương thức tấn công.
2.2
Nội dung chính
2.2.1
Một số giả thuyết ngầm định
N: RSA modulus, là tích của hai số nguyên tố p, q

: phi hàm Euler của modulus N

p,q: 2 số nguyên tố lẻ khác nhau
e: số mũ công khai thỏa

d: số mũ bí mật (số mũ riêng) thỏa

(N,e) khóa công khai
(N,d) khóa bí mật
M: không gian bản rõ, bao gồm tất cả các bản rõ có thể có
m: bản rõ,
C: không gian bản mã, bao gồm tất cả các bản mã có thể có
c: bản mã,

f: hàm mã hóa
hàm giải mã
Alice: người gửi
Bob: người nhận
Trudy: kẻ xấu
2.2.2
Hàm một chiều có cửa sập RSA
20


Hàm số là một hàm một chiều có cửa sập.
• Hàm f được tính dễ dàng thông qua thuật toán bình phương và nhân
• Hàm số rất khó tính trong thời gian tuyến tính.
• Hàm số dễ dàng tính được khi chúng ta biết một trong các của sập.
• Các cửa sập của hàm RSA bao gồm:
Quan hệ giữa các cửa sập:
Giả sử nếu chúng ta biết được 1 trong các cửa sập của hàm số RSA:
Số nguyên tố p (hoặc q)
Khi một trong hai số nguyên tố tạo nên modulus N bị lộ, ta có thể dễ
dàng tính tìm được số nguyên tố còn lại bằng cách lấy N chia cho số nguyên tố
đã biết.
Phi hàm Euler(N) cũng dễ dàng tìm được công thức
Số mũ bí mật d cũng có thể tìm được, ta có:
Phương trình (1) dễ dàng tính được bằng giải thuật Euclid mở rộng.
Phi hàm Euler
Khi có phi hàm Euler , chúng ta có thể tím được các cửa sập còn lại.
Ta có:
Đặt S = p + q vừa tìm được ta có phương trình:
Mà p và q chính là nghiệm của phương trình đó.
Số mũ công khai d có thể được tính bằng giải thuật Euclid mở rộng với d

là nghiệm của phương trình:
Ví dụ:
Giả sử ta có:
Khi đó:
Ta được phương trình
Giải phương trình bậc hai ta được:

Số mũ bí mật d
Biết được số mũ bí mật d, ta có thể dễ dàng tính được các cửa sập còn
lại.
21


Ta có:
Chọn một số ngẫu nhiên
Ta có:
Ta lại có:

Mà p, q là hai số nguyên tố lẻ, nên là một số chẵn, dẫn đến (e*d-1) cũng
là một số chẵn nên là một số nguyên.
Tính:
Từ (1)(2) suy ra
Khi đó (p, q)=gcd()
Tuy nhiên, ta chỉ tìm được các số nguyên tố p, q khi , ta có 3 trường hợp:
• , khi khác 1 và -1 thì trả về (p, q) = gcd()
• , quay lại bước đầu tiên và chọn số x khác.
• , tính rồi tiếp tục cho đến khi tìm được p,q
Độ phức tạp của thuật toán , ở trường hợp đặc biệt, nếu p, q cùng độ lớn
về số bit và thì độ phức tạp của thuật toán là
Ví dụ:

Giả sử ta có:
Chọn m=53,

Ta thu được (p, q) = gcd() = (316798337, 568334519)
Các cửa sập có quan hệ mật thiết với nhau, nếu một trong các cửa sập bị
lộ thì tất cả các cửa sập có thể được tìm ra dễ dàng trong thời gian tuyến tính. Và
từ đó ta có thể tính được hàm .
2.2.3
Phân tích các số nguyên lớn
Độ an toàn của thuật toán RSA phụ thuộc rất lớn vào việc phân tích thừa
số nguyên tố của số modulus N. Nếu việc phân tích N ra thừa số nguyên tố có
thể thực hiện trong thời gian ngắn thì hệ thống mã hóa RSA cũng sẽ không còn
giá trị.
2.2.3.1
Phương pháp chia thử
Đây là phương pháp phân tích thừa số nguyên tố “thô sơ” nhất và chỉ
thích hợp khi N tồn tại thừa số nguyên tố nhỏ.
Bước 1:
x=3
22


Bước 2:
Nếu N chia hết cho x thì chuyển tới bước 4
Bước 3:
Tính x=x+2 và quay lại bước 2
Bước 4:
Trả về x, N/x và kết thúc thuật toán
2.2.3.2
Phương pháp Fermat

Như ta đã biết bài toán phân tích N thành nhân tử là 1 bài toán khó nếu p
và q đủ lớn. Tuy nhiên nếu p, q được chọn quá gần nhau thì phương pháp
Fermat có thể dung để phân tích N một cách hiệu quả
Không mất tính tổng quát, giả sử q>p.
Đặt
p, q là 2 số nguyên tố lẻ nên x,y đều là số nguyên
Ta có:

Nếu p, q quá gần nhau dẫn đến y sẽ khá nhỏ, ta có thể tìm được một
cách hiệu quả bằng cách thử lần lượt các giá trị của x,y
Bước 1:
Đặt x=, y2=x2 –N
Bước 2:
Tính y=
Bước 3:
Nếu y là số nguyên thì chuyển tới bước 5 và kết thúc thuật toán
Bước 4:
Tính x = x + 1, y2=x2 –N và quay lại bước 2
Bước 5:
Trả về x-y và x+y và kết thúc thuật toán
Lưu ý: thuật toán này chỉ thích hợp cho số N được tạo thành từ 2 số
nguyên tố gần nhau, nếu không thuật toán này có thể còn lâu hơn cả thuật toán
chia thử
Nếu thì thuật toán Fermat có thể được dung để phân tích N hiệu quả
Phương pháp Pollard “p - 1”
Giả sử, ta có số tự nhiên và số k lớn thỏa hay nói cách khác . Khi đó ta
2.2.3.3

có:
Theo định lý Fermat nhỏ ta lại có :

Từ (1) và (2) ta có:

23


Tính gcd() ta sẽ thu được p, đây chính là nguyên lý cơ bản của thuật toán
Pollard p-1.
Lưu ý:
Khi tính gcd() ta có thể thu được n. Khi đó:
hay
Thuật toán:
Bước 1:
Chọn một số B, tính
Bước 2:
Chọn ngẫu nhiên
Bước 3:
Tính . Nếu x>1 thì trả về x và N/x và kết thúc thuật toán.
Bước 4:
Tính
Bước 5:
Nếu , thì d là ước của N. Trả về d, N/d và kết thúc thuật toán
Nếu d = N, quay lại bước 2 chọn số a chưa từng sử dụng
Nếu d =1, quay lại bước 1 và chọn B lớn hơn hoặc trả về fail và kết
thúc thuật toán.
Độ phức tạp của thuật toán
Số B ảnh hưởng lớn đến thuật toán, số B càng lớn thì sác xuất tìm được
nhân tử của N càng lớn nhưng thuật toán chạy càng chậm.
2.2.3.4
Phương pháp William “p + 1”
Chuỗi Lucas:

Cho 2 số P và Q thỏa , khi đó phương trình bậc 2 có 2 nghiệm
Ta có:
Chuỗi Lucas được định nghĩa:

Với và
U(1,-1) chính là chuỗi Fibonacci
Tính chất đệ quy:

Trong thuật toán William p+1, chúng ta sẽ sử dụng chuỗi V(A,1).
Để phân tích số N, đầu tiên ta chọn số A>2, ta có chuỗi:

24


Khi đó:
Với
Ta có:
chia hết cho p
Do p là số nguyên tố nên cũng chính là ký hiệu Legendre.
Nếu = 1 thì thuật toán trở thành thuật toán Pollard “p-1”
Do đó, chúng ta cần = -1 hay D không phải là thặng dư bậc hai modulo
p.
Để áp dụng thuật toán William p+1 để phân tích nhân tử số N, đầu tiên ta
chọn ngẫu nhiên số A>2 (do ta không biết giá trị nên bước này có thể lặp lại cho
đến khi tìm ra). Chọn số B rồi tính . Tính gcd(N, -2 ), nếu giá trị tìm được khác
1 và N thì ta tìm được ước của N và kết thúc thuật toán. Nếu gcd(N, ) = 1 hoặc
N thì ta quay lại và chọn số B hoặc A khác.
của chuỗi V(A, 1) = của chuỗi V()
Ví dụ:
Phân tích nhân tử của N = 112729

Chọn A=5
i
1
2
3
4
5
6
7

M
1
2
6
24
120
720
5040

của chuỗi V()
5
23
12098
87680
53242
27666
110229

gcd(N,)
1

1
1
1
1
1
139

Ta tìm được p = 139 là một nghiệm của N. Ta thấy:
Trong trường hợp này số n có ước là số nguyên tố p với p+1 là một số 7smooth nên chỉ cần với M=7! ta có thể tìm được ước của N.
2.2.3.5
Phương pháp ECM
ECM là thuật toán phân tích nhân tử dựa trên đường cong elliptic và là
một biến thể của phương pháp Pollard “p-1”.
Thuật toán:
Bước 1:
Chọn ngẫu nhiên một đường cong Elliptic E và một điểm P có tọa
độ nguyên
Trong đó đường cong E là:
và điểm P(x, y) với P E và x, y.
Để chọn được đường cong E và điểm P thỏa mãn điều kiện như vậy,
ta có thể chọn ngẫu nhiên 3 số a, x, y rồi tính .
25