1 BỘ GIÁO DỤC VÀ ĐÀO TẠO
BỘ QUỐC PHÒNG
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ĐINH QUỐC TIẾN
NGHIÊN CỨU PHƯƠNG PHÁP SÀNG TRƯỜNG SỐ
ỨNG DỤNG TRONG PHÂN TÍCH MÃ Chuyên ngành:
Cơ sở toán học cho tin học
Mã số:
62 46 01 10
TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC



Phản biện 1: PGS.TS Hoàng Văn Tảo
Ban Cơ yếu Chính Phủ.
Phản biện 2: PGS.TS Nguyễn Duy Bảo
Học viện Kỹ thuật Quân sự.
Phản biện 3: TS Thái Danh Hậu
Viện Khoa học và Công nghệ quân sự.

Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp
Viện họp tại Viện Khoa học và Công nghệ quân sự vào hồi
… ngày … tháng … năm 2014. Có thể tìm hiểu luận án tại thư viện:
- Thư viện Viện Khoa học và Công nghệ quân sự
- Thư viện Quốc gia Việt nam 1 MỞ ĐẦU

1. Tình hình nghiên cứu trong và ngoài nước

 Phạm vi nghiên cứu của Luận án:
- Nghiên cứu cơ sở lý thuyết và xây dựng các thuật toán chọn
đa thức sàng cho phương pháp sàng trường số.
- Nghiên cứu và cải tiến các thuật toán sàng áp dụng cho
phương pháp sàng trường số.
4. Mục tiêu nghiên cứu
 Nghiên cứu cở lý thuyết và xây dựng các thuật toán chọn cặp đa
thức sàng cho phương pháp sàng trường số.
 Nghiên cứu cải tiến và đánh giá hiệu quả của các thuật toán sàng
áp dụng cho phương pháp sàng trường số.
5. Phương pháp nghiên cứu
 Dựa trên cơ sở lý thuyết của phương pháp sàng trường số.
 Dựa trên cơ sở lý thuyết của các thuật toán chọn đa thức sàng và
các thuật toán sàng.
 Dựa trên phương pháp tích hợp, công nghệ lập trình song song.
6. Ý nghĩa khoa học và thực tiễn
 Ý nghĩa khoa học: Góp phần vào việc phân tích đánh giá và xây
dựng tiêu chuẩn cho hệ mật khóa công khai RSA.
 Ý nghĩa thực tiễn: Đáp ứng nhu cầu đảm bảo an toàn mật mã
trong các lĩnh vực kinh tế xã hội và an ninh quốc phòng.
7. Bố cục của luận án
Luận án gồm 03 chương cùng với các phần mở đầu, kết luận,
danh mục các công trình, bài báo khoa học đã được công bố của tác giả
và 02 phần phụ lục.
3 CHƯƠNG 1
TỔNG QUAN VỀ HỆ MẬT RSA VÀ BÀI TOÁN PHÂN TÍCH SỐ





,
2
( , )
()
a b U
a bm y



,
với
 


và
y
. Sau đó, áp dụng kết quả đối với vành các số
nguyên đại số:
4 2 2 2
( , ) ( , )
( ) ( ) ( ) ( )
a b U a b U
x a b a b
       


.
1.2.3. Tm số chính phương đại số
Phương pháp NFS dựa vào việc tìm các số chính phương trong
và
 

, nên sẽ cần phải tìm tập U các cặp quan hệ (a, b) trơn trong
các cơ sở phân tích hữu t RFB, cơ sở phân tích đại số AFB, và cơ sở đặc
trưng bậc hai QCB.
1.2.4. Chọn đa thức sàng
1.2.4.1. Bài toán chọn đa thức sàng
Bài toán. (Chọn đa thức sàng của Montgomery). Tìm các đa thức sàng
bậc d>2 sao cho hệ số của chúng bằng O(N
1/2d
).
1.2.4.2. Phương pháp chọn đa thức sàng tuyến tính
Phương pháp base-m
Cho


1/( 1) 1/
dd
N m N
và

  

0
(0 )



log
1
1
p
pB
p
fq
p
với B là cận trơn cho trước và q
p
là số
nghiệm của
   
 0 mod
f x p
. Nếu
 
f

càng nhỏ thì đa thức
 
fx

càng tốt cho phương pháp NFS.
Phương pháp của Kleinjung
Kleinjung đề xuất một cải tiến cho phương pháp của Murphy đối
với đa thức không monic g: chọn một số nguyên dương a
d

22
( 2)
()
dd
d d d
ON
. Koo và cộng sự đã tổng quát hóa các phương pháp xây
dựng cấp số nhân mod N độ dài d+1 để chọn đa thức bậc bất kỳ có các
hệ số cỡ

2
( 1)/
()
dd
ON
.
1.2.5. Sàng tm quan hệ
Chọn các cặp số nguyên (a, b) có các tính chất sau:
 gcd(a, b)=1.
 Chuẩn hữu t
 

a bm
= a+bm là trơn trên RFB.
 Chuẩn đại số
 


ab
= (-b)

cho phương pháp sàng trường số để phân tích thành công hợp số
RSA; và đánh giá hiệu quả về mặt lý thuyết và thực hành của các
thuật toán sàng áp dụng cho phương pháp sàng trường số được
giải quyết trong Chương 3.
7 CHƯƠNG 2
CHỌN CẶP ĐA THỨC SÀNG CHO PHƯƠNG PHÁP
SÀNG TRƯỜNG SỐ

2.1. Chọn cặp đa thức sàng bậc hai
2.1.1. Thuật toán sinh các cặp đa thức sàng bậc hai
Sử dụng thuật toán của Montgomery (Thuật toán 5) để sinh các
cặp đa thức sàng bậc hai với các hệ số cỡ O(N
1/4
).
2.1.2. Chọn cặp đa thức sàng bậc hai và tâm sàng
Giả sử cặp đa thức sàng bậc hai f
1
(x) và f
2
(x) có 2 nghiệm tương
ứng là x
11
, x
12
, x
21
, x

Thực nghiệm 2.1. So sánh số quan hệ trung bình khi tâm miền sàng trục
x tại điểm 0 và tại điểm x
0
của các cặp đa thức sàng loại 1 (cặp đa thức
sàng đồng thời có 2 nghiệm) và loại 2 (cặp đa thức sàng còn lại). Đối với
các cặp đa thức loại 1 còn so sánh số quan hệ trung bình của các cặp đa
thức sàng có giá trị ρ(f
1
, f
2
) nhỏ (đa thức loại 1a) và lớn (đa thức loại 1b).
Bảng 2.1: Kết quả thực nghiệm 1.

Đa thức
loại 2
Đa thức
loại 1a
Đa thức
loại 1b
Số quan hệ trung bình với tâm
min sàng trục x tại đim 0
153
255
234
Số quan hệ trung bình với tâm
min sàng trục x tại đim x
0

-
836

1
, f
2
) =

(f
1
) +

(f
2
) nhỏ hơn.
Thực nghiệm 2.2. So sánh số quan hệ khi tâm miền sàng trục x tại điểm
0 và tại điểm x
0
của các cặp đa thức có ρ
max
, ρ
min
,

max
,

min
.
Bảng 2.2: Kết quả thực nghiệm 2.

ρ
max

mặc dù cặp đa thức này có giá trị ρ lớn hơn.
Thuật toán 6: Thuật toán chọn cặp đa thức sàng bậc hai theo

min
và
tâm sàng.
Input: hợp số N.
Output: cặp đa thức sàng bậc hai f
i
(x) và tâm sàng.
Bước 1: Sinh tập các cặp đa thức sàng bậc hai theo phương pháp
Montgomery.
Bước 2: Chọn ra tập T các cặp đa thức sàng bậc hai đồng thời có 2
nghiệm.
Bước 3: Tìm

min
và tâm sàng x
0
của cặp đa thức sàng trong tập T.
Với mi cặp đa thức sàng ta ký hiệu:

(f
1
, f
2
) =
 
 
''

.
Bảng 2.3: Kết quả thực nghiệm 3.
Giá tr


lớn nhất

max
Giá tr


na cao

H
Giá tr


na thấp

L
Giá tr


nh nhất

min
67
426
889
1183

2.1.3. Một số nhận xét
Kết quả của các thực nghiệm trên đã đưa ra được 2 thuật toán
lựa chọn cặp đa thức sàng bậc hai và tâm sàng của chúng cho NFS.
Trong đó, khi phân tích số nguyên lớn thì Thuật toán 7 sẽ nhanh hơn
đáng kể so với Thuật toán 6 mà vẫn đảm bảo chọn ra được cặp đa thức
sàng tốt gần tương đương. Kết quả này thực sự quan trọng khi thực hiện
việc chọn cặp đa thức sàng để phân tích các số nguyên lớn.
10 2.2. Chọn cặp đa thức sàng bậc ba
2.2.1. Xây dng cơ s lý thuyết chọn cặp đa thức sàng bậc ba
2.2.1.1 Một số khái niệm
Khái niệm về không gian Euclid trên
ℝ
m
.
Định nghĩa về tích có hướng của 3 véc tơ trong
ℝ
4
.
Đnh nghĩa 2.1. (tích có hướng của 3 véc tơ) Cho 3 véc tơ

=
 
0 1 2 3
, , ,a a a a
,

=

.
Từ định nghĩa trên ta xây dựng các tính chất cơ bản sau.
2.2.1.2 Các tính chất cơ bản
Tính chất 2.1. Nếu

=





thì



,



và



.
Tính chất 2.2. Tích có hướng của 3 véc tơ là tuyến tính với mỗi véc tơ
của tích, chẳng hạn với
,kh
thì
(k


' ' '
' ' '
' ' '
u u u
v v v
w w w
   
   
   
  


  


  

, với
,,
i i i
u v w 
, i = 1, 2,
3 ta có:
 
det( A) ' ' '
     
    

trong đó A =
1 2 3

4
, ta có:

=

khi và chỉ khi span(

,

,

) = {

}

.
Định lý 2.2 dưới đây đưa ra công thức cho phép xác định chuẩn
của véc tơ tích có hướng của 3 véc tơ trên không gian
ℤ
4
.
Định lý 2.2. Ký hiệu A, B, C là các góc giữa

và

, giữa

và

, giữa

và số các góc tù là chẵn thì
  




1
2
  
.
2.2.2. Thuật toán chọn cặp đa thức sàng bậc ba
Thuật toán 8: Thuật toán chọn cặp đa thức sàng bậc ba.
Input: hợp số N.
12 Output: cặp đa thức sàng bậc ba f
i
(x) có các hệ số cỡ
2/9
()ON
.
Bước 1: Tìm


4
có tọa độ là cấp số nhân theo modulo N.
Bước 2: Tìm cơ sở ban đầu {

’,

Chọn số nguyên tố p = O(N
1/3
) sao cho p = 3r +1 và
r
N
 1
(mod p), a =
3
bN
p

và b = O(N
1/3
). Ta tìm được

= (a,b
2
,bp,p
2
), thỏa
mãn ||

|| = O(N
2/3
).
2.2.2.2. Tìm cơ sở ban đầu cho L = {

}

.


= (v, -u, 0, 1), với u ≡ s
2
(mod a) và v =
22
b u p
a

.
2.2.2.3. Thuật toán rút gọn cơ sở lưới.
Thuật toán 9: Thuật toán rút gọn cơ s lưới.
Input: {

’,

’,

’} là 3 véc tơ độc lập tuyến tính trong ℤ
4
.
Output: {

,

,

} thoả mãn các điều kiện sau:
  

=
While (Continue = 1) {
Continue = 0;
InOrder{

,

,

}; //sắp xếp giảm dần
q 
,
,






;
if (q>0) {



q

; Continue = 1;}
else {
q 

q

; Continue = 1; }
}
Return {

,

,

}.

Nhận xt 2.3. Vòng lặp 2 sẽ dừng chỉ khi tất cả các giá trị q tính được
trong đó đều bằng 0 và cũng giống như thuật toán của Montgomegy ta có
tất cả các góc giữa các cặp véc tơ đầu ra đều nằm trong đoạn
2
33
,




.
Hệ quả 2.1 của định lý 2.2 cho phép đánh giá trong trường hợp số góc tù
chẵn là:
  


2


0
, b
1
,
b
2
, b
3
) và

=(c
0
, c
1
, c
2
, c
3
). Ký hiệu
14 23
0 1 2 3
A( x) a a x a x a x   
.
23
0 1 2 3
B( x) b b x b x b x   
.

 
f

của Murphy.

2.3. Chọn cặp đa thức sàng bậc tổng quát
2.3.1. Chọn cặp đa thức sàng da vào cấp số nhân
2.3.1.1 Một số khái niệm cơ bản
 Rút gọn lưới và chuẩn của véc tơ.
 Kết quả đã biết về tích chập.
15 2.3.1.2 Chọn cặp đa thức dựa vào cấp số nhân
Mệnh đ 2.1. Cho trước số nguyên N và cấp số nhân
01
, , ,
d
c c c
có d+1
số hạng công bội m và thỏa mãn
0
(mod )
i
i
c c m N
, thì có thể sinh ra d
đa thức bậc tối đa d có nghiệm chung m modulo N có hệ số cỡ
1/d
c


và tích chập cỡ
2( 1)/
()
dd
ON

.
Xây dựng ma trận có dạng như sau:
1 2 1
1 0 0 0
0 1 0 0
0 0 0 0
0 0 1 0
0 0 0 1
dd
L
c c c c













.
(2). Tạo cấp số nhân
1, , ,
d
m m N
.
(3). Sử dụng thuật toán LLL đối với ma trận L để tìm các véc tơ ngắn
1
( , , )
d
bb
.
(4). Biểu diễn
,0 ,
( , , )
t
i i i d
aab
và tính
,0 ,
1
mod
d
j
i i j
j
a a m N




(1). Sử dụng Thuật toán 10 sinh cặp đa thức phi tuyến (f
1
, f
2
) bậc d có
nghiệm chung m modulo N.
(2). Kiểm tra các hệ số đầu và cuối là bội của 60.
(3). Tính
()
i
f

và ghi vào tệp “Alphas.txt”.
(4). Thực hiện phép xoay đa thức với
1 2 3
, , (0, ]j j j J
:
(4).1
1 2 3
, , 1 1 2 2 3
( ) ( ) ( ) ( )
j j j
f x j f x j f x j x m   
.
(4).2 Tính
1 2 3
,,
()
j j j
f

. Kết quả này
trùng với phương pháp luận án đã xây dựng.
 Có thể sinh ra cặp đa thức bậc d = 4 có nghiệm chung m modulo N
với các hệ số cỡ
3/16
()ON
và tích chập cỡ
3/ 2
()ON
. Kết quả này
tốt hơn phương pháp của Prest và Zimmermann sinh ra các đa thức
có hệ số cỡ
5/14
()ON
và tích chập cỡ
10/ 7
()ON
.
2.4. Kết luận chương 2
Các kết quả của chương này bao gồm:
(1). Đưa ra các Thuật toán 6 và Thuật toán 7 để chọn cặp đa thức sàng
bậc hai và tâm sàng của chúng cho phương pháp sàng trường số.
Thuật toán 7 thực hiện nhanh hơn Thuật toán 6; việc sàng tìm quan
hệ tại tâm sàng sẽ giúp cho phương pháp NFS thực hiện nhanh hơn.
(2). Xây dựng phương pháp và cơ sở lý thuyết (bao gồm: Định lý 2.1,
Định lý 2.2, và Hệ quả 2.1) cho thuật toán chọn cặp đa thức sàng phi
tuyến bậc ba cho phương pháp sàng trường số. Kết quả thu được
Thuật toán 8, dùng để tìm các cặp đa thức sàng phi tuyến bậc 3 có
các hệ số cỡ O(N
2/9

 Các phần tử (a, b) có chuẩn đại số chia hết cho (p, r) trong
AFB thì a có dạng a = -br+kp với k

.
3.2.2. Song song hóa thuật toán sàng tuyến tính
Giả sử thực hiện thuật toán trên M tiến trình, tiến trình t thực
hiện sàng với các giá trị b trong khoảng WS*(t-1) đến WS*t. Sau khi tất
cả các tiến trình kết thúc việc sàng trong khoảng WS đã xác định thì lặp
lại công việc sàng của các tiến trình như trên với giá trị b mới bắt đầu từ
WS*M. Công việc này được thực hiện lặp lại đối với các tiến trình đến
19 khi nhận đủ các quan hệ cần tìm. Khi đó bước sàng tìm quan hệ sẽ kết
thúc.
Thuật toán 14: Thuật toán sàng tuyến tính phiên bản song song cho
tiến trnh thứ t.
Input: - Các cơ sở phân tích RFB, AFB;
- Đa thức f(x), nghiệm m của f(x) mod N;
- Khoảng sàng C;
- WS, t, b
0
: trong đó b
0
là giá trị đầu tiên của b cho tiến trình
thứ t với số lượng giá trị cần sàng WS.
Output: - Tập quan hệ rels = {(a
0
, b
0

j

C.
(d) e[i]=(-b)
deg(
f
)
f(-i/b) với i

[-C;C]
(e) với mi (p, r)

AFB
Chia e[j] cho p tối đa số mũ có thể với j=-br+kp
với k

thỏa mãn –C

j

C.
(f) for i

[-C;C]
if a[i]=e[i]=1 và gcd(i, b)=1 thêm (i, b) vào rels
4. return rels.
20 3.2.3. Kết quả phân tích số 135 chữ số

thực hiện:
 Xác định lưới của (a, b) tương ứng với
 
mod a bs q
.
 Xây dựng các trục tọa độ (c, d) cỡ C cho lưới này.
 Với mi
 
,p r P
chuyển
 
mod a br p
về mặt phẳng (c, d).
 Với mi miền sàng của mặt phẳng (c, d) kiểm tra tính trơn của
cặp (c, d).
3.3.2. Kết quả quan trọng về lý thuyết lưới
Bổ đ 3.1.
m

là một lưới khi và chỉ khi là một tập rời rạc,
nhóm con cộng tính của
m
.
Luận án phát biểu mệnh đề tổng quát với lưới n chiều như sau.
21 Mệnh đ 3.1. Giả sử
 
12

n
và thỏa mãn:
,
12
det
gcd( , , , , )
q
n
q
q

  


3.3.3. Hiệu quả của thuật toán sàng lưới
3.3.3.1. Khẳng định của Pollard
Các quan hệ
 
,ab
sẽ tạo thành một lưới con
,q

trong
2
với
 
2
1, m



113.290
4.000.000
2,832.10
-2
3000x3000
220.345
9.000.000
2,448.10
-2

4000x4000
353.298
16.000.000
2,208.10
-2

5000x5000
508.540
25.000.000
2,034.10
-2

Kết quả thực hiện thuật toán sàng lưới thay đổi theo k
i
, với k
1
=
0,447, k
2
= 0,269, k

2000x2000
47.338
71.285
112.403
607.285
1.010.887
1.774.362
3000x3000
96.426
144.494
196.896
1.365.960
2.273.003
3.318.761
4000x4000
159.065
237.819
323.660
2.428.342
4.043.587
5.902.669
5000x5000
233.919
349.359
475.143
3.794.283
6.320.513
9.225.408
Bảng 3.3. Hiệu suất của thuật toán sàng lưới.
Khoảng sàng

6,550.10
-2

5,881.10
-2

5,483.10
-2

5000x5000
6,165.10
-2

5,527.10
-2

5,150.10
-20
1
2
3
4
5
6
7
8
9

(1). Đã cải tiến song song thuật toán sàng tuyến tính (Thuật toán 14) trên
một hệ thống tính toán cụ thể để phân tích hợp số RSA cỡ 135 chữ
số thập phân. Kết quả phân tích là một minh chứng cho việc cải tiến
thành công về mặt thực hành phương pháp sàng trường số và có thể
triển khai cài đặt trên các hệ thống tính toán lớn để đánh giá, phân
tích độ an toàn của hệ mật khóa công khai RSA.
(2). Đã đánh giá hiệu quả của thuật toán sàng lưới của Pollard: Sử dụng
lý thuyết lưới để phát biểu và chứng minh Mệnh đề 3.1 đối với
trường hợp số chiều tổng quát n chiều, áp dụng kết quả này để chứng
minh phát biểu của Pollard với trường hợp 2 chiều. Thực hành cài
đặt so sánh hiệu suất giữa hai phương pháp sàng, đã thu được các kết
quả chính xác phù hợp với lý thuyết.
Các kết quả nêu trên đã được tác giả công bố trên các bài báo số [3]
và [5] (Danh mục các công trình khoa học đã công bố).