Đề cương luận văn - Phạm Xuân Khánh – 01405310 GVHD : PGS.TS Lê Tiến Thường
_________________________________________________________________________________________
ĐỀ CƯƠNG LUẬN VĂN
Giáo viên hướng dẫn: PGS.TS Lê Tiến Thường
Học viên: Phạm Xuân Khánh, MSHV: 01405310
Tên đề tài:
Phân tích cơ chế bảo mật RSA đa số nguyên tố ( RSA CRT )
và cài đặt thuật toán RSA CRT trên FPGA
MULTI-PRIME RSA CRYPTOSYSTEM
AND ITS FPGA IMPLEMENTATION
MỤC LỤC
1. Giới thiệu
Thuật toán RSA được đề nghị bởi 3 nhà toán học Rivest , Shamir và Adleman, là
một trong những cơ chế bảo mật được sử dụng rộng rãi nhất, đặc biệt trong hạ
tầng khoá công cộng PKI (Public Key Infrastructure). Quá trình mã hoá/giải mã
của cơ chế bảo mật RSA dựa trên phép toán modulo mũ số nguyên rất lớn. Để
có thể đẩy nhanh tốc độ giải mã của cơ chế RSA, cơ chế RSA đa số nguyên tố
(RSA CRT Chinese Remainder Theorem) thường được áp dụng để thay thế cơ
chế RSA thông thường với các tính toán song song modulo mũ số nhỏ hơn. Và
đặc trưng nhất cho cơ chế RSA CRT là trường hợp 2 số nguyên tố.
Hoạt động CRT đối với cơ chế RSA 2 số nguyên tố đơn giản hơn rất nhiều so với
trường hợp nhiều số nguyên tố. Vì thế việc nghiên cứu cơ chế RSA 2 số nguyên
tố rất quan trọng và được sử dụng rất nhiều trong thực tế.
Trước đây đã có một số đề tài thực hiện mã hoá/giải mã RSA thông thường trên
kit FPGA [4]. Trong đề tài này tiếp tục mở rộng module giải mã RSA theo phương
pháp CRT (2 số nguyên tố và có thể phát triển lên nhiều số nguyên tố nếu thời
gian cho phép) và thực hiện module phát sinh cặp khoá public/private key ngay
trên kit VirtexII Pro. Thông qua kết quả mô phỏng chúng ta có thể rút ra một số
_________________________________________________________________________________________
- 1 -
Đề cương luận văn - Phạm Xuân Khánh – 01405310 GVHD : PGS.TS Lê Tiến Thường

=
 Bên nhận B sẽ thu được bản tin gốc m
• Ký điện tử / Kiểm tra chữ ký điện tử
_________________________________________________________________________________________
- 2 -
Đề cương luận văn - Phạm Xuân Khánh – 01405310 GVHD : PGS.TS Lê Tiến Thường
_________________________________________________________________________________________
 Ký điện tử
 Bên gửi A tạo ra một bản tin digest được đặc trưng bởi số
nguyên m, 0<m< n – 1
 Sử dụng private key (n,d) để ký được kết quả
nms
e
mod
=
 Sử chữ ký s qua cho bên nhận B
 Kiểm tra chữ ký điện tử
 Bên nhận B sử dụng public key (n,e) để tính toán số nguyên
nsv
e
mod
=
 Bên B thu được bản tin digest từ số nguyên v
 Tính toán độc lập bản tin digest mà bên gửi đã ký
 Nếu hai bản tin digest này giống nhau thì chữ ký hợp lệ
Để giải quyết bài toán
nxy
e
mod
=

_________________________________________________________________________________________
pháp thay thế hoàn hảo là sử dụng đặc trưng mới cho private key theo phương
pháp CRT (Chinese Remainder Theorem) .
• RSA CRT public key [2]
RSA CRT public key bao gồm 2 thông số, đó là modulus n và public
exponent e. Thông số modulus n là tích của u số nguyên tố
i
r
, i = 1 , … ,
u với
2
≥
u
., và thông số public exponent e là môt số nguyên có giá trị
nằm giữa 3 và n – 1 thoả mãn USCLN(e,
( )
n
λ
) = 1 với
( )
)1, ,1(
1
−−=
u
rrBSCNNn
λ
, với hai số nguyên tố đầu tiên
1
r
và

=−
pdPe
1)1mod()*(
=−
qdQe
và thông số qInv là số nguyên dương nhỏ hơn p thoả mãn:
1mod)*(
=
pqInvq
Nếu u > 2, thì chúng ta sẽ biểu diễn thêm các thành phần triple
( )
iii
tdr ,,
,
i = 3, … , u. Thông số
i
r
là thành phần nhân trong tích tạo ra modulus n .
Mỗi exponent
i
d
( i = 3, … , u ) thoả mãn:
1)1mod()*(
=−
ii
rde
Mỗi thông số
i
t
( I = 3 , … , u ) là một số nguyên dương nhỏ hơn

qcm
dQ
mod
2
=
 Nếu u > 2, tính
r
d
i
rcm
i
mod
=
, I = 3 , … , u
 Tính
pqInvmmh mod)(
21
−=
 Tính
qhmm
+=
2
 Nếu u > 2, đặt
1
rR
=
và for I = 3 to u do
 Tính
1
−

- 5 -
Đề cương luận văn - Phạm Xuân Khánh – 01405310 GVHD : PGS.TS Lê Tiến Thường
_________________________________________________________________________________________
 Hàm kiểm tra số nguyên tố là một phần rất quan trọng trong quá
trình phát sinh cặp khoá RSA, chúng ta sử dụng định luật Fermat phát
biểu rằng “n là số nguyên tố nếu
1mod
1
=
−
na
n
”. Giải thuật Miller-Rabin
kiểm tra số nguyên tố như sau :
TestPrime(n)
Tìm 2 số nguyên k và q với k > 0 , q lẻ để
qn
k
21
=−
Chọn một số nguyên ngẫu nhiên a , 1 < a < n-1
if
1mod
1
=
−
na
n
or n-1 then return “không phải số nguyên tố”
end if

3
3
B
A
Q

( ) ( )
3*3,2*2,1*13,2,1 BQABQABQATTT
−−−<=
( ) ( )
3,2,13,2,1 BBBAAA
<=
( ) ( )
3,2,13,2,1 TTTBBB
<=
goto loop
SEE_USCLN(m.b)
start : ( A2 , A3 ) <= ( 0, m ) ; ( B2 , B3 ) <= (1 , b ) ;
Loop : if B3=0 then
b<=fetch_new_b
goto start
end if
if B3=1 then
return(B2,B3)
end if






1
0
∈=
∑
−
=
i
n
i
i
i
eeE
và Z được tính toán như sau :
1;1
00
==
PZ

for i = 0 to n – 1 do
MPP
ii
mod
2
1
=
+
if
( )
1
=

i
n
i
i
i
aaA
;
{ }
1,0,2
1
0
∈=
∑
−
=
i
n
i
i
i
bbB
;
{ }
1,0,2
1
0
∈=
∑
−
=

−
end for
return
1
−
n
S
Với hàm nhân Montgomery, ta có một phương pháp khác để tính toán
MXZ
E
mod
=
_________________________________________________________________________________________
- 7 -
Đề cương luận văn - Phạm Xuân Khánh – 01405310 GVHD : PGS.TS Lê Tiến Thường
_________________________________________________________________________________________
MontExp(X,E,M)
MNr
n
mod2
2
=
),,1(Pr
0
MNrodMontZ
=
),,(Pr
0
MNrXodMontP
=

return
n
Z
Kiến trúc sơ lược của cơ chế RSA trên kit FPGA [4]
 Module phát sinh số ngẫu nhiên: sử dụng LFSR (Linear
Feedback Shift Register) để phát sinh số giả ngẫu nhiên 512/1024 bit
 Module Random FIFO: đây là một dãy các register có kích thước
cố định để lưu trữ số ngẫu nhiên theo cơ chế FIFO. Nếu FIFO đầy, module
phát số ngẫu nhiên sẽ dừng hoạt động để tiết kiệm năng lượng.
 Module kiểm tra số nguyên tố: có nhiệm vụ nhận số ngẫu nhiên
từ Random FIFO và kiểm tra đó có phải là số nguyên tố hay không. Nếu
không phải thì tiếp tục nhận số ngẫu nhiên khác và kiểm tra lại cho đến khi
đúng thì thôi. Sau đó đặt số nguyên tố vào input của Prime FIFO.
 Module Prime FIFO: đây là một dãy các register có kích thước cố
định để lưu trữ số nguyên tố theo cơ chế FIFO. Nếu FIFO đầy, module
kiểm tra số nguyên tố sẽ dừng hoạt động để tiết kiệm năng lượng. Số
nguyên tố được lưu trữ có thể được sử dụng ngay lập tức cho module
phát sinh cặp khoá public/private key
_________________________________________________________________________________________
- 8 -
Đề cương luận văn - Phạm Xuân Khánh – 01405310 GVHD : PGS.TS Lê Tiến Thường
_________________________________________________________________________________________
 Module
( )
pqpqn
ϕ
,
=
sẽ nhận hai số nguyên tố p và q và tính toán
được n và

• Trình bày cơ sở toán học cho việc phát sinh cặp khoá public/private key,
mã hoá/giải mã với phương pháp RSA thông thường và RSA CRT (nhấn mạnh
cơ chế RSA 2 số nguyên tố)
• Tổng quan về FPGA và lập trình VHDL trên FPGA
• Viết mã VHDL giả lặp giải thuật RSA (CRT) trên kit VirtexII Pro
• Viết chương trình giao tiếp với kit FPGA (Visual C#/Java) để phát và nhận
kết quả mô phỏng
• Đánh giá kết quả, nhận xét, nêu bật lên ưu điểm của phương pháp giải mã
RSA CRT và hướng phát triển đề tài
5. Sơ lược về thời gian thực hiện
• Tuần 1 – 6: Phân tích cơ sở toán học của cơ chế bảo mật RSA, xây dựng
một số thuật toán xử lý toán học (Fermat, Montgomery, Euclide …) để có thể
cài đặt RSA lên kit FPGA. Đánh giá sơ bộ về các giải thuật RSA trên cơ sở lý
thuyết toán học.
• Tuần 7 – 12: Nghiên cứu về cấu trúc kit VirtexII Pro và ngôn ngữ VHDL
_________________________________________________________________________________________
- 9 -
Đề cương luận văn - Phạm Xuân Khánh – 01405310 GVHD : PGS.TS Lê Tiến Thường
_________________________________________________________________________________________
• Tuần 13 – 24: Xây dựng mô hình xử lý cơ chế bảo mật RSA trên kit
VirtexII Pro và viết software để trao đổi dữ liệu với kit FPGA. Đây là phần hạt
nhân của đề tài với thời gian chi tiết như sau:
 Tuần 13 – 15: thiết kế module cộng và phát sinh số ngẫu nhiên
 Tuần 16 – 18: thiết kế module FIFO và modulo mũ
 Tuần 19 – 21: thiết kế một software tính toán RSA trên PC có thể
bằng ngôn ngữ Visual C#/Java
 Tuần 22 – 24: simulate và debug từng module
• Tuần 25 – 27: Mô phỏng, ghi nhận kết quả rút ra các đánh giá, nhận xét và
kết luận
• Tuần 28 – 30: Viết hoàn chỉnh báo cáo, làm slide

Cryptosystems”, R.L. Rivest, A. Shamir, and L. Adleman, MIT Laboratory for
Computer Science and Department of Mathematics
• [7] “FPGA-based Implementation of a serial RSA processor”, A.
Mazzeo, L. Romano, G. P. Saggese - Universita’ degli Studi di Napoli “Federico
II”, N. Mazzocca - Seconda Universita’ degli Studi di Napoli
• [8] “High Speed RSA Implement”, Cetin Kaya Koc, RSA
Laboratories, RSA Data Security, Inc.
High-Speed RSA Implementation
High-Speed RSA Implementation
High-Speed RSA Implementation
High-Speed RSA Implementation
• [9] “Parallel FPGA Implementation of RSA with Residue Number
Systems”, Mathieu Ciet, Michael Neve, Eric Peeters & Jean-Jacques
Quisquater
_________________________________________________________________________________________
- 11 -