ỦY BAN NHÂN DÂN TP.HCM
SỞ KHOA HỌC VÀ CÔNG NGHỆ

ĐẠI HỌC QUỐC GIA TP. HCM
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

BÁO CÁO NGHIỆM THU

NGHIÊN CỨU TẤN CÔNG RSA VÀ XÂY DỰNG
CƠNG CỤ PHÂN TÍCH RSA

THÀNH PHỐ HỒ CHÍ MINH
THÁNG 5/ 2015


ỦY BAN NHÂN DÂN TP.HCM
SỞ KHOA HỌC VÀ CÔNG NGHỆ

BÁO CÁO NGHIỆM THU
(Đã chỉnh sửa theo góp ý của Hội đồng nghiệm thu)

NGHIÊN CỨU TẤN CÔNG RSA VÀ XÂY DỰNG
CÔNG CỤ PHÂN TÍCH RSA

CHỦ NHIỆM ĐỀ TÀI

Trần Đan Thư
CƠ QUAN QUẢN LÝ
(Ký tên/đóng dấu xác nhận)

CƠ QUAN CHỦ TRÌ

(Ký tên/đóng dấu xác nhận)

THÀNH PHỐ HỒ CHÍ MINH
THÁNG 5/ 2015


TÓM TẮT NỘI DUNG NGHIÊN CỨU
Hệ mã RSA, đặt theo tên của Ron Rivest, Adi Shamir và Len Adleman, 3 nhà tốn học
phát minh ra nó, được cơng bố lần đầu tiên vào tháng 8 năm 1977. Từ đó đến nay, RSA
là hệ mã được sử dụng phổ biến nhất trong việc bảo vệ tính riêng tư cũng như đảm bảo
tính xác thực của các dữ liệu số. Hiện nay, RSA đã được triển khai trong nhiều hệ thống
thương mại; trong các web servers nhằm đảm bảo truy cập web an ninh; đảm bảo tính
riêng tư cũng như tính xác thực của email; đảm bảo an toàn trong các phiên giao dịch
đăng nhập từ xa; và RSA cũng là trọng tâm của các hệ thống thanh tốn dùng thẻ tín
dụng, thẻ thơng minh.
Bên cạnh tính bảo mật cao, RSA được dùng phổ biến một phần cũng do tính đơn giản, dễ
hiểu của nó. Thực vậy, gọi N là tích của 2 số nguyên tố lớn cùng kích thước, N = pq. Đặt
e và d là 2 số nguyên thỏa ed mod (N) = 1, ký hiệu ed  1 (mod (N)), với (N) = (p –
1)(q – 1). Cặp (N, e) được cơng bố và gọi là khóa cơng khai; d được giữ bí mật và gọi là
khóa cá nhân hay khóa bí mật. Để mã hóa thơng điệp M, 1  M  N, ta tính C = Me mod
N; và để giải mã, ta tính M = Cd mod N. Rõ ràng, bỏ qua việc chứng minh tính đúng đắn,
(mà thực ra cũng không quá phức tạp), công thức mã hóa và giải mã là rất dễ hiểu, ngay
cả với người dùng phổ thơng, vì gần như chỉ cần sử dụng các phép số học phổ thông.
Trong trường hợp dùng khóa cá nhân để tính lũy thừa modulo, S = Md mod N, thì bất kỳ
ai có khóa cơng khai đều có thể xác thực được M = Se mod N chính là thơng điệp của
người cấp khóa cơng khai. Đây chính là ngun tắc tạo chữ ký điện tử. Sau thời gian
nghiên cứu các hệ khóa cơng khai, đặc biệt hệ mã RSA, chúng tôi tập hợp và hệ thống
hóa các kết quả trong tuyển tập này.
Trước hết, các biến thể của RSA sẽ được khảo sát và được giới thiệu trong “Các biến thể
của RSA”. Mục đích là thơng qua các biến thể, tìm ra các đặc trưng cốt lõi của RSA

nhằm tiến tới xây dựng một mơ hình tốn học tổng qt cho RSA.
Từ kết quả việc nghiên cứu các biến thể của RSA, 2 mơ hình tổng qt sẽ được giới thiệu
trong “Hệ thống hóa RSA”. Mơ hình thứ nhất sử dụng các tính chất liên quan đến phép
chia Euclid. Mơ hình này bao quá các biến thể của RSA xây dựng trên vành Euclid. Tuy
nhiên, trên các cấu trúc đại số khác, rất khó để xây dựng được phép chia, và do đó, không
thể áp được vào như một thể hiện của mô hình RSA Euclid này. Mơ hình thứ 2 được xây
dựng trên cấu trúc đại số lỏng hơn, cấu trúc vị nhóm, mà gần như bao quát được các biến
thể RSA hiện được công bố.
Để hiểu tại sao RSA vẫn được sử dụng phổ biến trong việc bảo vệ thông tin, những
nghiên cứu về thám mã được thực hiện. Trước hết, như đã biết, tính an tồn của RSA dựa
trên độ khó bài tốn phân tích ra thừa số. Thực ra, bài tốn đó khơng phải khó vì khơng
có cách giải mà khó ở chỗ thời gian giải là khơng khả thi. Các thuật tốn phân tích thừa
i


số được khảo sát trong “Thám mã RSA – bài tốn phân tích ra thừa số”. Các kết quả
lý thuyết được nghiên cứu và nhằm dẫn đến thuật toán hiện đại nhất là thuật tốn sàng
lưới, do nó sử dụng các kết quả mạnh của toán học trong bài toán phân tích, đồng thời nó
tận dụng sức mạnh phần cứng bằng cách triển khai phân tích trên hệ thống máy tính song
song.
Ngay cả khi sử dụng sức mạnh song song của máy tính, thì bài tốn phân tích vẫn là khó
khi phân tích số lớn. Một ngun tắc đơn giản là nếu máy tính phân tích được số có kích
thước n thì người thiết kế RSA chỉ cần tăng kích thước số cần phân tích lơn hơn n là có
thể sử dụng an tồn. Tuy nhiên, ngay cả khi kích thước n lớn thì nếu sử dụng các khóa
khơng kỹ càng, RSA cũng có thể bị tấn cơng. Một trong nhưng tấn công như thế được
giới thiệu và tổng quát hóa trong “Phân tích khóa yếu” mà tập trung trên tấn công dàn
và tấn công liên phân số. Trong các tấn cơng này, chặn dưới của khóa bí mật an tồn
được thiết lập. Điều này đặc biệt hữu ích cho việc thiết kế RSA an toàn.
Bên cạnh những nghiên cứu về mơ hình cũng như thám mã RSA, việc nghiên cứu các hệ
mã mới cũng được đề cập. Trước hết, một hệ mã dựa trên bài tốn lơ-ga-rít rời rạc được

giới thiệu trong “Hệ mã cơng khai dựa trên 2-nhóm đơn sinh” sử dụng khái niệm đặc
trưng lơ-ga-rít (logarithmic signature) mà có thể được dùng để xây dựng các hệ mã cơng
khai có cấu trúc tốn học rõ ràng và an tồn, hiệu quả nếu chọn được nhóm nền thích
hợp.
Một hệ mã khác cũng được xây dựng trong “RSA không tất định trên vành Bergman”.
Hệ mã này giới thiệu cấu trúc vành Bergman và mở rộng RSA thành hệ mã không tĩnh,
nghĩa là từ một bản rõ, những lần mã hóa khác nhau sẽ cho ra các bản mã khác nhau.
Để hỗ trợ xây dựng RSA an toàn, cũng như hỗ trợ các nghiên cứu về mã công khai, các
công cụ tấn công RSA cổ điển được hiện thực. Trước hết là cơng cụ tấn cơng bằng phân
tích thừa số được giới thiệu trong “Kỹ thuật phân tích thừa số trên nền tính tốn song
song”.
Tấn cơng khóa yếu, tiến tới tấn cơng hồn tồn RSA cũng được cung cấp cơng cụ thám
mã dùng dàn trong “Công cụ tấn công dàn” mà gần như thành cơng tuyệt đối khi khóa
bí mật có kích thước nhỏ hơn hẳn ¼ kích thước của modulus N. Khi phục hồi được khóa
bí mật, một thuật tốn heuristic được sử dụng để phân tích thừa số khi biết thêm thơng tin
về khóa bí mật d.
NGUYỄN ĐÌNH THÚC – TRẦN ĐAN THƯ
Nhóm nghiên cứu Mơ hình và Cấu trúc rời rạc
CSM-group@fit

ii


SUMMARY OF RESEARCH CONTENT
RSA cryptosystem, named after Ron Rivest, Adi Shamir and Len Adleman, the three
mathematicians invented RSA, was first published in August 1977. Since then, the RSA
is the most popular cryptosystem to protect data privacy and authenticity. Currently,
RSAs are the heart of many commercial systems; web services to ensure security web
access, to ensure the privacy and authenticity of the email; to ensure the safety in the
login session remotely. RSA is also the focus of the payment system using credit cards,

smart cards.
Besides high security, RSA is widely used because of its simplicity and understandable.
Indeed, let N be the product of two large primes of the same size, N = pq. Let e and d be
2 integers such that ed mod (N) = 1, denoted by ed  1 (mod (N)), where (N) = (p –
1)(q – 1). The pair (N, e) is published and called the public-key ; d is kept secret and
known as the private key or secret key. To encrypt a message M, 1  M  N, compute C =
Me mod N ; and to decrypt, compute M = Cd mod N. Clearly, ignoring the correctness
proof (which really is not too complicated), the encryption and decryption is very easy to
understand, even for ordinary users, because just the basic operations are used. If the
private key used for modular exponentiation, S = Md mod N, then anyone with the public
key can authenticate whether M = Se mod N is message of public key owner. This is the
principle of creating electronic signatures. We have worked on the public key system,
particularly RSA cryptosystem, and systematize the results in these proceedings.
First of all, the variant of RSA will be considered and introduced in "The variant of the
RSA". The aim is through these variants to find out the characteristics of RSAs, so as to
build a generic mathematical model for RSA.
From the results of the study of the variants of the RSA, 2 generic models will be
introduced in "RSA system". The first model uses the properties related to the Euclid
division. This model covers RSA's variants built on the Euclid division rings. However,
other algebraic structures, it is difficult to have a division, and therefore, can not apply
this model. The second model is built on the looser algebraic structure, the monoid,
which nearly covers known variations of RSA.
To understand why RSA is still widely used in the protection of information, RSA
cryptanalysis have been done. First of all, because the security of RSA relies on the
difficulty of the factorization problem. Actually, how to solve this problem is not difficult
but to get a solution in the polynomial time is not feasible. The factorization algorithms
are presented in "RSA cryptanalisys - the factorization problem". The theoritical results
lead to modern algorithms, called lattice sieves, which exploit power of hardware
deploying algorithms on parallel systems.
Even if using the power of parallel computers, the factorization problem is still difficult

when analysed numbers are large. A simple rule which is applied to design RSA is if
iii


integers of n bits are factored, we should use larger integers. However, even when the
size n is large, if using carelessly, RSA can also be broken. One of the attacks will be
introduced and generalized in the "Analysis of weak keys" which focuses on lattice and
continued fractions attacks. This is very useful for the design of secure RSA.
Besides research on models as well as on RSA cryptanalysis, how to build new
cryptosystem is also mentioned. First, a code based on the discrete logarithmic problem
introduced in "Public-key cryptosystems based on the 2-cyclic group" using the concept
of logarithmic signature.
Other cryptosystem is also proposed in "A non-deterministic RSA based on Bergman
ring". This system exploits algebraic properties of Bergman ring to expand the RSA to a
random cryptosystem.
To support deploying secure RSAs, as well as supporting research on public key
cryptosystems, RSA attack tools are implemented. Firstly tool of factorization are
presented in "Technical factorization on parallel computing"
Weak key attack tools are implemented and introduced in "Lattice attack tools" which are
almost absolute success when the secret keys are smaller than a quarter of the size the
modulus N. Once having recovered secret key, an algorithm heuristic will be used to
factorization problem.
NGUYỄN ĐÌNH THÚC – TRẦN ĐAN THƯ
Concrete Structure and Models-group
CSM-group@fit

iv


MỤC LỤC

TÓM TẮT NỘI DUNG NGHIÊN CỨU _______________________________________ i
SUMMARY OF RESEARCH CONTENT ___________________________________ iii
MỤC LỤC ____________________________________________________________ v
PHẦN MỞ ĐẦU ______________________________________________________ vii
Chương 1. NGHIÊN CỨU TẤN CÔNG RSA VÀ XÂY DỰNG CƠNG CỤ PHÂN TÍCH
RSA ________________________________________________________________ 1
1. Mở đầu _______________________________________________________________ 1
2. Nội dung nghiên cứu ____________________________________________________ 1
3. Mục tiêu đề tài _________________________________________________________ 2
4. Nội dung báo cáo _______________________________________________________ 2
5. Các kết quả chính của đề tài ______________________________________________ 4
5.1. Kết quả lý thuyết ______________________________________________________________ 4
5.2. Kết quả thực nghiệm __________________________________________________________ 7
5.3. Các kết quả khác _____________________________________________________________ 7

6. Những người thực hiện __________________________________________________ 7

Chương 2. CÁC BIẾN THỂ CỦA RSA _____________________________________ 9
1. Hê ̣ mã hóa RSA gố c _____________________________________________________ 9
1.1. Mô tả hệ mã _________________________________________________________________ 9
1.1. Nhận xét về hệ mã ____________________________________________________________ 9

2. Các biến thể của RSA __________________________________________________ 10
2.1. Hệ mã hóa RSA trên vành các ma trận ___________________________________________ 10
2.2. Hệ mã hóa RSA trên nhóm đường cong elliptic _____________________________________ 10
2.3. Hệ mã hóa RSA trên vành thương các đa thức _____________________________________ 12
2.4. Hệ mã hóa RSA trên vành thương cá c sớ ngun Gauss _____________________________ 13

Chương 3. HỆ THỐNG HĨA RSA _______________________________________ 14
1. RSA trên vành thương của vành Euclid ___________________________________ 14

1.1. Mô hình hệ mã hóa RSA trên vành Euclid 𝑿 - Euclid-RSA ____________________________ 16
1.2. Biểu diễn các hệ mã tựa-RSA đã biế t theo Euclid-RSA_______________________________ 16
1.3. Nhận xét về mô hin
̀ h Euclid-RSA ________________________________________________ 17

2. Mô hình tổ ng quát cho RSA – G-RSA ______________________________________ 18
2.1. Mô hình G-RSA _____________________________________________________________ 18
2.2. Biểu diễn các hệ mã tựa RSA theo G-RSA ________________________________________ 19

Chương 4. MỘT BIẾN THỂ MỚI CỦA RSA ________________________________ 23
1. Vành Bergman ________________________________________________________ 23
2. Xây dựng biế n thể cho RSA dựa trên vành Bergman _________________________ 24
2.1. Xây dự ng nửa nhóm cơ sở ____________________________________________________ 24
2.2. Mô hình hệ mã ______________________________________________________________ 26
2.3. So sánh với hệ mã RSA gố c ___________________________________________________ 26

3. Nhâ ̣n xét về hê ̣ mã RSA trên vành Bergman ________________________________ 27

v


Chương 5. KHÁI NIỆM GIẢ NGHỊCH ĐẢO VÀ ỨNG DỤNG XÂY DỰNG HỆ MÃ
CÔNG KHAI _________________________________________________________ 29
1. Mở đầu ______________________________________________________________ 29
2. Các khái niệm toán học _________________________________________________ 29
3. Ma-trận giả khả nghịch trên trường hữu hạn 𝕫p _____________________________ 30
4. Các giao thức đề xuất __________________________________________________ 31
4.1. Giao thức thiết lập khóa _______________________________________________________ 32
4.2. Giao thức cập nhật khóa ______________________________________________________ 33
4.3. Phân tích độ an tồn _________________________________________________________ 34


Chương 6. BÀI TỐN PHÂN TÍCH THỪA SỐ ______________________________ 35
1. Các phương pháp phân tích thừa số ______________________________________ 35
1.1. Phương pháp chia thử ________________________________________________________ 35
1.2. Phương pháp Rho - 𝝆 ________________________________________________________ 35
1.3. Phương pháp 𝒑 − 𝟏 _________________________________________________________ 36
1.4. Phương pháp đường cong Elliptic (ECM – Elliptic Curve Method) ______________________ 38

2. Các phương pháp sàng _________________________________________________ 38
2.1. Phương pháp Fermat _________________________________________________________ 40
2.2. Phương pháp sàng bậc hai ____________________________________________________ 41
2.3. Phương pháp sàng trường số __________________________________________________ 44

Chương 7. TẤN CÔNG DÀN____________________________________________ 52
1. Lý thuyết dàn _________________________________________________________ 52
1.1. Định nghĩa về dàn ___________________________________________________________ 52
1.2. Rút gọn cơ sở dàn ___________________________________________________________ 52

2. Kỹ thuật của Coppersmith _______________________________________________ 58
3. Bài tốn ngược kích cỡ nhỏ _____________________________________________ 60
3.1. Giới thiệu __________________________________________________________________ 60
3.2. Cơ sở lý thuyết ______________________________________________________________ 61
3.3. Tấn công RSA trường hợp tổng quát_____________________________________________ 65

Phụ lục A.
SONG

KỸ THUẬT PHÂN TÍCH THỪA SỐ TRÊN NỀN TÍNH TỐN SONG
66


1. Giới thiệu ____________________________________________________________ 66
2. Sàng lưới ____________________________________________________________ 72
3. Tăng tốc sàng dựa trên tính tốn song song _______________________________ 74

Phụ lục B.

Hệ thống cung cấp dịch vụ RSA trên web _____________________ 75

Phụ lục C.

Phân tích n khi biết khố cá nhân ____________________________ 83

Phụ lục D.

Biên dịch và cấu hình hệ thống MSIEVE, GGNFS _______________ 86

TÀI LIỆU THAM KHẢO ________________________________________________ 89
QUYẾT TOÁN KINH PHÍ GIAI ĐOẠN I _____________________________________ a
DỰ TRÙ KINH PHÍ GIAI ĐOẠN II _________________________________________b
PHỤ LỤC SẢN PHẨM - ẤN PHẨM KHOA HỌC ______________________________ c
PHỤ LỤC SẢN PHẨM – ĐÀO TẠO ________________________________________d
vi


PHẦN MỞ ĐẦU
1. Tên đề tài/dự án:
NGHIÊN CỨU TẤN CÔNG RSA VÀ XÂY DỰNG CƠNG CỤ PHÂN TÍCH
RSA
Chủ nhiệm đề tài/dự án: Trần Đan Thư – Nguyễn Đình Thúc
Cơ quan chủ trì: Trường Đại học Khoa học Tự nhiên, ĐHQG Tp. HCM

Thời gian thực hiện: tháng 9/2013 – tháng 5/ 2015
Kinh phí đƣợc duyệt: 400 triệu đồng
Kinh phí đã cấp: 240 triệu đồng

theo TB số: số 97 ngày 20 tháng 07 năm 2013

2. Mục tiêu:
Đề tài tập trung nghiên cứu 3 nội dung chính sau:
(1) RSA và các biến thể.
Mục tiêu chính trong nội dung này nghiên cứu và hệ thống hóa về RSA và các biến
thể của RSA nhằm trả lời câu hỏi chính: tại sao RSA vành số nguyên, ta sẽ gọi là
RSA-truyền thống, hiện vẫn được sử dụng chính và chưa có biến thể nào thay thế
RSA-truyền thống?
(2) Thám mã RSA và Cài đặt các công cụ tấn công RSA.
Nghiên cứu các trường hợp yếu của RSA. Nghiên cứu này giúp hình thành bộ tiêu chí
đánh giá thế nào là một hệ RSA khơng an tồn từ đó khuyến cáo người dùng tránh các
trường hợp yếu hiển nhiên này khi thiết kế một ứng dụng RSA.
Nghiên cứu lý thuyết tấn công dàn (lattice), cùng các kỹ thuật tấn cơng khác, từ đó
xây dựng bộ cơng cụ đánh giá độ an toàn của một hệ thống RSA cùng các thành phần
(khóa cá nhân hoặc/và khóa cơng khai), các ứng dụng (chữ ký, thiết lập khóa,… dùng
RSA).
Nghiên cứu các thuật tốn hiện đại tấn cơng bài tốn phân tích ra thừa số nguyên tố,
đặc biệt các phương pháp QS (Quadratic Sieve) và NFS (Number Field Sieve). Trong
đề tài này, chúng tôi nghiên cứu các kỹ thuật hiện đại để cải thiện tốc độ và đề xuất
một hiện thực phân bố trên mơi trường tính tốn lưới.
vii


(3) Phát triển một hệ mã cơng khai an tồn.
Qua việc nghiên cứu các biến thể của RSA cùng các phương pháp thám mã RSA, câu

hỏi đặt ra cho nội dung này là có thể phát triển một hệ mã cơng khai khơng dựa trên
bài tốn phân tích ra thừa số cũng như bài toán log rời rạc? Trong đề tài này, chúng
tơi nghiên cứu bài tốn khó liên quan đến bài tốn tổng con và phân tích mà trận, qua
đó bước đầu xây dựng một hệ mã mới

3. Nội dung
(1) Nội dung 1: RSA và các biến thể.
(1.1) Hệ thống hóa RSA.
Bên cạnh RSA truyền thống (RSA trên vành số nguyên là 2 số nguyên tố phân
biệt), rải rác đã có những cơng trình về RSA với các cấu trúc đại số khác vành số
nguyên. Công việc cần thực hiện ở đây là nghiên cứu cấu trúc hay/và các tính chất
đại số của RSA truyền thống, từ đó, xây dựng mơ hình tốn học tổng qt biểu
diễn được RSA và nhiều dạng biến thể của nó. Chúng tơi dự kiến công việc sẽ tập
trung khảo sát sâu về tác động nhóm (group-action) trên các tập hợp có cấu trúc
đại số đặc biệt như vành số nguyên, vành đa thức, vành các số ngun Gauss.
(1.2) Khảo sát các mơ hình thể hiện của mơ hình tổng qt.
Từ mơ hình tốn học tổng quát của RSA, xem xét với điều kiện nào, các biến thể
RSA trên các cấu trúc đại số khác đã được công bố là các thể hiện của RSA tổng
quát? Cụ thể, công việc ở đây là xác định điều kiện có thể biểu diễn RSA số
nguyên Gauss, RSA trên vành đa thức, RSA trên nhóm tuyến tính, và các biến thể
khác có thể tìm thấy trong q trình nghiên cứu.
(1.3) Phân tích độ an tồn của các thể hiện của mơ hình tổng qt.
Việc tìm được mơ hình tốn học RSA tổng qt là đặc biệt quan trọng để có thể
trả lời câu hỏi chính đã nêu: tại sao RSA truyền thống vẫn được sử dụng rộng rãi?
Bằng cách cố định kích thước khóa, cơng việc cần làm là khảo sát độ an toàn của
RSA và các biến thể của nó để trả lời câu hỏi đặt ra.
(2) Nội dung 2: Thám mã RSA và cài đặt công cụ tấn công RSA.
(2.1) Các phương pháp thám mã.
viii



Như đã biết, cài đặt một hệ mã RSA an tồn khơng phải là việc dễ ràng, đặc biệt
với những người khơng chun trong lãnh vực mã hóa-mật mã, ngay cả với nhiều
người làm an ninh thông tin. Công việc ở đây là hệ thống hóa các phương pháp,
các kỹ thuật tấn cơng RSA, từ đó xây dựng bộ tiêu chí hướng dẫn xây dựng một
hệ RSA an tồn và hiểu quả. Chúng tôi xác định đây là công lý thuyết việc khó!
(2.2) Cài đặt sàng trường số nguyên tố.
Bên cạnh các tiêu chí hướng dẫn thực hiện một hệ RSA an tồn, lợi dụng năng lực
tính tốn lưới và/hoặc điện toán đám mây, cần xây dựng một hệ thống tấn cơng
RSA trực tiếp bằng cách giải bài tốn phân tích ra thừa số ngun tố trên mơi
trường tính tốn lưới hoặc/và điện tốn đám mây. Cơng việc này có 2 ý nghĩa
chính: thứ nhất, khẳng định chắc chắn rằng các hệ RSA có kích thước khóa nhỏ
hơn khả năng tấn cơng được của hệ thống là hồn tồn khơng an tồn; thứ 2, giúp
các nhà nghiên cứu mã hóa-mật mã có mơi trường mạnh nghiên cứu thám mã
bằng kỹ thuật máy tính hiện đại.
(2.3) Cài đặt tấn cơng dàn.
Ngồi việc tấn cơng bằng các cơng cụ máy tính mạnh, việc nghiên cứu cài đặt các
tấn công dùng dàn cũng sẽ được thực hiện trên các máy tính cá nhân. Kết quả này
cũng góp phần đánh giá độ an tồn một hệ RSA đồng thời hỗ trợ tích cực các nhà
nghiên cứu thám mã khóa cơng khai.
(2.3) Cài đặt tấn công khác.
Một số tấn công cũng được cài đặt với mục đích chính là bổ túc cho các tấn cơng
trên. Nội dung này được triển khai độc lập và song song với nội dung (2.3).
(3) Nội dung 3: Phát triển hệ mã mới.
(3.1) Nghiên cứu các bài tốn khó.
Bên cạnh hai bài tốn khó đang được sử dụng rộng rãi trong mã hóa-mật mã là
phân tích ra thừa số và logarithm rời rạc, công việc ở đây là khảo sát thêm các
dạng bài tốn khó khác nhằm thiết lập bài tốn khó mới làm nền tảng phát triển
các hệ mã cơng khai mới. Chúng tơi có ý định nghiên cứu phát triển bài toán tổng
tập con và bài toán logarithm rời rạc trên nhóm tuyến tính làm nền tảng phát triển

bài tốn mới. Cơng việc này mang tính lý thuyết nền tảng.
(3.2) Bước đầu xây dựng hệ mã.
Từ bài toán khó xây dựng được, ít nhất là bài tốn tổng con và/hay bài tốn
logarithm rời rạc trên nhóm tuyến tính, cùng với việc biến đổi mơ hình RSA tổng
qt, cơng việc ở đây là nghiên cứu đề xuất một hệ mã mới.
ix


(3.3) Cài đặt thử nghiệm.
Công việc ở đây là cài đặt hệ mã đề xuất và thử nghiệm các tấn cơng có thể xảy ra
cho hệ mã này.
(4) Nội dung 4: Kiểm định hệ thống và hoàn thiện báo cáo
(4.1) Kiểm định báo cáo và hoàn thiện hệ thống
Triển khai và kiểm định (i) hệ thống phân tích ra thừa số ngun tố trên nền tính
tốn lưới hoặc/và trên mơi trường điện tốn đám mây; (ii) chương trình thử
nghiệm tấn cơng dùng dàn; hồn thiện báo cáo và các bài báo khoa học.

4. Sản phẩm của đề tài/dự án
a. Sản phẩm 1: (Mô tả đặc điểm cơ bản của sản phẩm và yêu cầu khoa học,
công nghệ cần phải đạt)
- Mơ hình RSA tổng qt và các tiêu chí hướng dẫn xây dựng và sử dụng
một hệ RSA an toàn, và hệ mã mới (nếu được). Mơ hình RSA phải đủ tổng
quát giúp hệ thống hóa các biến thể của RSA. Bộ tiêu chí đơn giản nhưng
hiệu quả.
- Hệ mã mới an toàn và hiệu quả. Tốc độc so sánh với RSA hay DiffieHellman nhanh hơn. Độ an toàn được phân tích dựa trên bài tốn khó đặt ra
b. Sản phẩm 2:
- Hệ thống giúp đánh giá độ an toàn của một hệ thống cùng các thành phần,
các ứng dụng của RSA. Hệ thống có khả năng triển khai ngay trong thực
tiễn.
- Tấn cơng phân tích ra thừa số các số ngun tố kích thước tối thiểu 128

bit.
- Tấn cơng khóa bí mật với kích thước số ngun tố tối thiểu 256.
c. Sản phẩm 3:
-

Các bài báo khoa học

x


1. Dang Hai Van, Nguyen Dinh Thuc. Pseudoinverse matrix over finite field
and its applications. Information Science and Appplications, LNEE,
Spriger-Verlag Berlin Heidelberg, 2015.
2. D.T. Long, D.T. Thu, D.N. Thuc. A Bergman Ring Based Cryptosystem
Analogue of RSA. 2013 International Conference on IT Convergence and
Security, Macau 2013.
- Đào tạo
1. Vũ Anh Tuấn. Phát triển các công cụ nền tảng phục vụ thám mã và tính tốn
tổ hợp trên mơi trường tính tốn song song. Luận văn Thạc Sĩ, ĐHKHTN,
2014.
2. Nguyen Nhu Huan. RSA Cryptanalysis: Continued fraction and Lattice
attacks. Luận văn Đại học (CT Cử nhân tài năng), 2014.
3. Ngo Xuan Huy. Thám max RSA khi biết khóa riêng. Luận văn Đại học,
2014.

xi


Chƣơng 1. NGHIÊN CỨU TẤN CÔNG RSA VÀ XÂY DỰNG


CÔNG CỤ PHÂN TÍCH RSA
1. Mở đầu
RSA là hệ mã được sử dụng phổ biến nhất trong việc bảo vệ tính riêng tư, tính xác thực
của dữ liệu số. Hiện nay, RSA được triển khai trong nhiều hệ thống thương mại, trong
các server web cũng như các trình duyệt nhằm đảm bảo các giao dịch an toàn, trong các
hệ thống thư điện tử (e-mail) nhằm đảm bảo tính riêng tư cũng như tính xác thực của
email. Ngay từ khi được cơng bố, RSA đã được nhiều nhà nghiên cứu phân tích những
nguy cơ có thể dẫn tới việc sử dụng RSA khơng an tồn.
Rất nhiều phương pháp tấn cơng đã được cơng bố nhưng chưa có phương pháp nào có
thể phá vỡ hồn tồn RSA. Vì thế, cho đến nay, RSA vẫn được tin tưởng sử dụng. Mặc
dù chưa có phương pháp hồn hảo tấn cơng được RSA nhưng từng phương pháp tấn công
cũng minh họa được những nguy hiểm khi thiết kế cũng như sử dụng RSA khơng đúng
cách. Nói cách khác, cài đặt một hệ thống RSA an toàn khơng phải là việc dễ dàng. Vì
thế việc nghiên cứu và mơ tả bằng cơng cụ tốn học một số tấn công hỗ trợ thiết kế và
xây dựng hệ mã RSA an toàn là cần thiết. Các kết quả nghiên cứu góp phần đảm bảo cho
cơng nghệ an ninh thơng tin được thực hiện đúng đắn, tránh các rủi ro cũng như đạt hiệu
quả thực thi cao.
Bên cạnh những nghiên cứu thám mã RSA, việc trả lời câu hỏi « có thể cải tiến RSA
bằng cách sử dụng các cấu trúc tốn học khác thay vì nâng kích thước khóa hay không
? » cũng được đặt ra. Đây là câu hỏi khoa học thú vị và có thể dẫn đến các lý thuyết hoặc
các cơng trình khoa học có giá trị.
Từ khi Peter Shor cơng bố thuật tốn lượng tử cho phép giải bài tốn phân tích ra thừa số
với thời gian đa thức, nhiều nhà toán học, các nhà tin học, đang tập trung nghiên cứu xây
dựng các bài tốn khó khác làm nền tảng cho các hệ mã khóa cơng khai mới khả dĩ chống
lại các tấn cơng dùng máy tính lượng tử.
2. Nội dung nghiên cứu
Đề tài tập trung nghiên cứu 3 nội dung chính sau:
(1) RSA và các biến thể.
Mục tiêu chính trong nội dung này nghiên cứu và hệ thống hóa RSA và các biến
thể của RSA nhằm trả lời câu hỏi chính: tại sao RSA vành số nguyên, ta sẽ gọi là

RSA-truyền thống, hiện vẫn được sử dụng chính và chưa có biến thể nào thay thế
RSA-truyền thống?
1


(2) Thám mã RSA và Cài đặt các công cụ tấn công RSA.
Nghiên cứu các trường hợp yếu của RSA. Nghiên cứu này giúp đánh giá thế nào là
một hệ RSA khơng an tồn từ đó khuyến cáo người dùng tránh các trường hợp yếu
hiển nhiên này khi thiết kế một ứng dụng RSA.
Nghiên cứu lý thuyết tấn công dàn (lattice), cùng các kỹ thuật tấn cơng khác, từ đó
xây dựng bộ cơng cụ đánh giá độ an tồn của một hệ RSA cùng các thành phần
(khóa cá nhân hoặc/và khóa cơng khai) của nó.
Nghiên cứu các thuật tốn hiện đại tấn cơng bài tốn phân tích ra thừa số nguyên
tố, đặc biệt các phương pháp QS (Quadratic Sieve) và NFS (Number Field Sieve).
Trong đề tài này, chúng tôi nghiên cứu các kỹ thuật hiện đại để cải thiện tốc độ và
đề xuất một hiện thực phân bố trên môi trường tính tốn lưới.
(3) Phát triển một hệ mã cơng khai an toàn.
Qua việc nghiên cứu các biến thể của RSA cùng các phương pháp thám mã RSA,
câu hỏi đặt ra cho nội dung này là có thể phát triển một hệ mã cơng khai khơng
dựa trên bài tốn phân tích ra thừa số cũng như bài tốn log rời rạc? Trong đề tài
này, chúng tơi nghiên cứu bài tốn khó liên quan đến bài tốn tổng con và phân
tích ma trận, qua đó bước đầu xây dựng một hệ mã mới.
3. Mục tiêu đề tài
Đề tài nhằm mục đích trả lời 3 câu hỏi quan trọng sau:
(1) Tại sao RSA truyền thống, RSA trên vành số nguyên với 2 số nguyên tố, vẫn được
sử dụng phổ biến trong các hệ thống an tồn-bảo mật thơng tin ?
(2) Khả năng tấn cơng RSA ?
(3) Có thể phát triển một mơ hình mã hóa khác ?
4. Nội dung báo cáo
Để trả lời câu hỏi “tại sao RSA vẫn được sử dụng rộng rãi ?” trước hết, chương 2 sẽ giới

thiệu thiệu lại RSA và thiết lập lại điều kiện cơ bản để đảm bảo ánh xạ 𝑅𝑆𝐴: ℤ𝑛 → ℤ𝑛
biến 𝑥 ⟼ 𝑥 𝑘 là đơn ánh chỉ khi 𝑛 = 𝑟𝑎𝑑 𝑛 . Sau đó, lần lượt 4 biến thể phổ biến của
RSA được giới thiệu. Các biến thể này bao gồm RSA trên vành các ma trận, trên nhóm
các đường cong elliptic, trên vành đa thức, và trên vành các số nguyên Gauss. Trên cơ sở
khảo sát RSA và các biến thể của nó, chương 3 giới thiệu 2 lược đồ/mơ hình RSA tổng
qt. Lược đồ thứ nhất được gọi là lược đồ Euclid-RSA. Lược đồ Euclid-RSA có hạn chế
2


là chỉ biểu diễn được các RSA được định nghĩa trên các cấu trúc đại số mà phép chia
định nghĩa được. Lược đồ thứ 2, dựa trên cấu trúc nửa nhóm, có thể xem như lược đồ
RSA tổng quát, G-RSA, do nó có thể biểu diễn được RSA và tất cả các biến thể của nó
mà chúng tơi đã biết và đã khảo sát.
Câu hỏi “có thể phát triển một hệ mã mới ?” được trả lời trong các chương 4 và 5.
Chương 4 có thể được xem như hệ quả của lược đồ G-RSA. Thực vậy, từ lược đồ GRSA, một biến thể mới của RSA trên một cấu trúc đại số mới rất trừu tượng, vành
Bergman, được phát triển. Về mặt lý thuyết, RSA-Bergman minh họa được tính tổng quát
của lược đồ G-RSA. Về mặt ứng dụng, RSA-Bergman giới thiệu một biến thể RSA
không tĩnh, nghĩa là cùng 1 bản rõ, các lần mã hóa khác nhau với cùng khóa cơng khai, sẽ
cho những bản mã khác nhau, nhưng cùng khóa các nhân tương ứng, giải ra cùng bản rõ
gốc. Song song với việc phát triển hệ mã mới RSA-Bergman, chương 5 phát triển 2 giao
thức mới dạng mã công khai. Giao thức thứ nhất dùng cho thiết lập khóa bí mật cho các
hệ mã quy ước. Giao thức thứ 2 cho phép cập nhật khóa bí mật. Cả hai giao thức được
phát triển dựa trên tính khó của bài tốn phân tích ma trận, là bài tốn “cho ma trận A là
tích của 2 ma trận B và C, việc tìm lại đúng B và C nào là không khả thi”.
Cuối cùng, chương 6 và 7 giải đáp cho câu hỏi “khả năng tấn công thám mã RSA ?”.
Chương 6 trình bài các phương pháp tấn cơng trực diện vào bài toán nên của RSA, bài
toán phân tích ra thừa số. Các phương pháp xác suất được giới thiệu và đều thất bại khi
áp dụng phân tích các số kích thước lớn khơng có tính chất đặc biệt nào. Cuối cùng, các
phương pháp sang, đặc biệt sàng trường số được giới thiệu chi tiết và khả năng cài đặt
trên nền tính tốn song song. Chương 7 giới thiệu chi tiết phương pháp tấn cơng khóa

ngắn. Phương pháp được xây dựng dựa trên lý thuyết dàn 2 chiều. Về mặt lý thuyết, dàn
2 chiều có thể phục hồi chính xác các khóa cá nhân có chiều dài ngắn hơn hẳn phân nửa
chiều dài số nguyên tố. Tuy nhiên, trong thực tế, khi khóa cá nhân xấp xỉ ½ chiều dài số
nguyên tố, phương pháp trở nên không ổn định. Chương 6 thiết lập chặn trên cho phép
phục hồi chính xác khóa cá nhân.
Cuối cùng là các phục lục trình bày kết quả cài đặt tấn cơng sàng trường số và tấn công
dàn. Với tấn công sàng trường số, các số nguyên 100 chữ số, cỡ 330 bit, có thể được
phân tích trong vài giờ. Riêng với trường hợp khóa cá nhân ngắn, khơng những phục hồi
3


được khóa cá nhân mà từ khóa cá nhân, hệ thống có thể phân tích ngược trở lại để xác
định 2 số nguyên tố bí mật của RSA.
5. Các kết quả chính của đề tài
5.1. Kết quả lý thuyết
5.1.1. Tổng quát hóa RSA
Mênh
̣ đề . Giả sử tồn tại số tự nhiên 𝑘 ≠ 1 sao cho ánh xạ
𝐹: ℤ𝑛 → ℤ𝑛
𝑥 ⟼ 𝑥𝑘
là đơn ánh. Khi đó = 𝑟𝑎𝑑 𝑛 = 𝑝1 𝑝2 … 𝑝𝑘 .
Mênh
̣ đề . Trên vành X. Nếu 𝛼, 𝛽 ∈ 𝑋, 𝑔𝑐𝑑 𝛼, 𝛽 = 1 thì 𝜑 𝛼. 𝛽 = 𝜑 𝛼 . 𝜑(𝛽). Với 𝜑
là hàm Phi-Euler.
Kí hiệu [𝑎] đươ ̣c dùng để chỉ phầ n tử chứa 𝑎 trong vành thương 𝑋/< 𝛾 > với 𝑎, 𝛾 ∈ 𝑋.
Mệnh đề sau biểu diễn một mơ hình tổng qt RSA trên các vành Euclid.
Mênh
̣ đề . Giả sử 𝑝, 𝑞 là các phần tử nguyên tố trong vành Euclid
nguyên thỏa mãn 𝑔𝑐𝑑 𝑒, 𝜑 𝑝𝑞


𝑋 và 𝑒, 𝑑 là các số

= 1 và 𝑒𝑑 ≡ 1(𝑚𝑜𝑑 𝜑 𝑝𝑞 ). Khi đó với mỗi 𝑚 ∈ 𝑋,

hê ̣ thức [𝑚]𝑒𝑑 = [𝑚] sẽ đúng trong vành thương 𝑋/< 𝑝𝑞 >.
Mênh
̣ đề . Giả sử 𝑋′ là một tập khác rỗng, trên đó đã xác đi ̣nh một phép toán hai ngôi
′ ∗ ′ sao cho với phép toán này, 𝑋′ là một nửa nhóm
a. Tờ n tại hai nửa nhóm nhân 𝑈, 𝑉 và hai đồng cấu 𝜇: 𝑋 ′ → 𝑈, 𝜂: 𝑋′ → 𝑉.
b. Tồ n tại hai nhóm 𝑈1 ⊂ 𝑈, 𝑈2 ⊂ 𝑈 và hai nhóm 𝑉1 ⊂ 𝑉, 𝑉2 ⊂ 𝑉 sao cho 𝜇 𝑋 ⊂
(𝑈1 ⋃𝑈2 ) và 𝜂 𝑋 ⊂ (𝑉1 ⋃𝑉2 ).
c. Ánh xạ 𝜃: 𝑋′ → 𝑈 × 𝑉 đi ̣nh nghiã bởi 𝜃 𝑥 = (𝜇 𝑥 , 𝜂 𝑥 ) là đơn ánh.
Kí hiệu 𝑁𝑖 = 𝑈𝑖 , 𝑀𝑖 = 𝑉𝑖 𝑖 = 1,2 và 𝐿 = 𝑙𝑐𝑚(𝑁1 , 𝑁2 , 𝑀1 , 𝑀2 ). Khi đó nế u 𝑒, 𝑑 là
hai sớ ngun thỏa mãn 𝑒𝑑 ≡ 1(𝑚𝑜𝑑 𝐿) thì 𝑥 𝑒𝑑 = 𝑥 với mọi 𝑥 ∈ 𝑋.
5.1.2. Một biến thể RSA
Đặt
𝐸𝑛 =

𝑎
𝑛𝑐

𝑏
: 𝑎, 𝑏, 𝑐 ∈ ℤ𝑛 , 𝑑 ∈ ℤ𝑛 2 .
𝑑
4


trong đó 𝑛 = 𝑝𝑞, 𝑝, 𝑞 là hai số nguyên tố phân biệt. Ta định nghĩa phép nhân “.” trên 𝐸𝑛 :
𝑎1
𝑛𝑐1


𝑏1
𝑎
. 2
𝑑1 𝑛𝑐2

𝑎1 𝑎2 𝑚𝑜𝑑 𝑛
𝑏2
=
𝑑2
𝑛 𝑐1 𝑎2 + 𝑑1 𝑐2 𝑚𝑜𝑑 𝑛2

(𝑎1 𝑏2 + 𝑏1 𝑑2 )𝑚𝑜𝑑 𝑛
𝑛𝑐1 𝑏2 + 𝑑1 𝑑2 𝑚𝑜𝑑 𝑛2

Và đinh
̣ nghiã 2 ánh xạ:
 Ánh xa ̣

𝜇: 𝐸𝑛 → 𝐸𝑝
𝑎
𝑝𝑞𝑐

𝑎𝑝
𝑏
↦
𝑑
𝑝𝑐𝑝

𝑏𝑝

𝑑𝑝

trong đó 𝑎𝑝 , 𝑏𝑝 , 𝑐𝑝 ∈ ℤ𝑝 , 𝑑𝑝 ∈ ℤ𝑝 2 , và 𝑎𝑝 ≡ 𝑎 𝑚𝑜𝑑 𝑝 , 𝑏𝑝 ≡ 𝑏 𝑚𝑜𝑑 𝑝 , 𝑐𝑝 ≡
𝑞𝑐 𝑚𝑜𝑑 𝑝 , 𝑑𝑝 ≡ 𝑑(𝑚𝑜𝑑 𝑝2 ); và
 Ánh xa ̣

𝜂: 𝐸𝑛 → 𝐸𝑞
𝑎
𝑝𝑞𝑐

𝑎𝑞
𝑏
↦
𝑑
𝑞𝑐𝑞

𝑏𝑞
𝑑𝑞

trong đó 𝑎𝑞 , 𝑏𝑞 , 𝑐𝑞 ∈ ℤ𝑞 , 𝑑𝑞 ∈ ℤ𝑞 2 , và 𝑎𝑞 ≡ 𝑎 𝑚𝑜𝑑 𝑞 , 𝑏𝑞 ≡ 𝑏 𝑚𝑜𝑑 𝑞 , 𝑐𝑞 ≡
𝑝𝑐 𝑚𝑜𝑑 𝑞 , 𝑑𝑞 ≡ 𝑑(𝑚𝑜𝑑 𝑞2 ).
Mênh
̣ đề . 𝜇 và 𝜂 là các đồng cấu nửa nhóm.
Mênh
̣ đề . Ánh xạ 𝜃 xác định bởi
𝜃: 𝐸𝑛 → 𝐸𝑝 × 𝐸𝑞
𝑀 ↦ 𝜃 𝑀 = (𝜇 𝑀 , 𝜂 𝑀 )
là một đơn ánh.
Kí hiệu bởi 𝐸𝑝∗ và 𝐸𝑞∗ tương ứng là tâ ̣p các phầ n tử khả nghịch trong 𝐸𝑝 và 𝐸𝑞 . Một biến
thể RSA được chứng minh trong kết quả sau:

Mênh
̣ đề 2.3 Nế u 𝑀 ∈ 𝐸𝑛 , 𝜇 𝑀 ∈ 𝐸𝑝∗ , 𝜂(𝑀) ∈ 𝐸𝑞∗ và e,d là các số nguyên thỏa mãn
𝑒𝑑 ≡ 1(𝑚𝑜𝑑 𝐿), 𝐿 = 𝑙𝑐𝑚(𝑝3 (𝑝 − 1)2 , 𝑞3 (𝑞 − 1)2 ) thì 𝑀𝑒𝑑 = 𝑀.
5.1.3. Thám mã RSA
Mệnh đề. Một số nguyên tố lẻ p > 3, có dạng 6𝑘 ± 1 với 𝑘 ∈ ℤ+.
Chặn dưới cho khóa cá nhân
Sử dụng tính chất:
𝑒𝑑 ≡ 1 𝑚𝑜𝑑 𝑙𝑐𝑚 𝑝 − 1, 𝑞 − 1
5


và giả sử 𝑔𝑐𝑑 𝑝 − 1, 𝑞 − 1 = 2, tồn tại k nguyên thỏa:
𝑒𝑑 + 𝑘. 𝐴 + 𝑠 = 1 or 𝑘 𝐴 + 𝑠 ≡ 1 𝑚𝑜𝑑 𝑒
trong đó, 𝐴 =

𝑁+1
2

, 𝑠=−

𝑝+𝑞
2

1

.
𝛿

Từ 𝑁 = 𝑒 𝛼 , 𝑑 < 𝑁 𝛿 = 𝑒 𝛼 và với 𝑝 và 𝑞 đủ lớn thỏa 𝑝 < 𝑞 < 2𝑝, hay 𝑝 < 𝑞 <
2 𝑁, thì,

𝑘 =

𝛿−1
2 𝑒𝑑 − 1
2𝑒𝑑
3𝑒𝑑
<
≤
< 3𝑒 1+ 𝛼
𝜑 𝑁
𝜑 𝑁
𝑁
1

𝑠 < 2𝑁 0.5 = 2𝑒 2𝛼
Trong thực tế, 𝛼 ≈ 1 vì thế ta có thể bỏ qua các hằng số nhỏ, bài tốn trờ thành:
“Tìm 𝑘, 𝑠 ∈ ℤ sao cho 𝑘 𝐴 + 𝑠 ≡ 1 𝑚𝑜𝑑 𝑒 với 𝑠 < 𝑒 0.5 và 𝑘 < 𝑒 𝛿 ”
Và chặn trên cho khóa bí mật là:
𝛿<

7 − 2 1 + 6𝛼
6

5.1.4. Cơ sở toán học phát triển các hệ mã mới
Định nghĩa. Ma-trận (vuông hay chữ nhật) A, trên trường ℝ hay ℂ, gọi là giả khả nghịch
nếu tồn tại ma-trận A+ thỏa đồng thời 4 điều kiện sau:
AA+A = A
A+AA+ = A+
(AA+)T = AA+
(A+A)T = A+A

trong đó, T ký hiệu phép chuyển vị ma-trận. Ma-trận A+ gọi là ma-trận giả nghịch đảo của
A, (và A cũng được gọi là ma-trận giả nghịch đảo của A+ như mệnh đề sau chứng minh.)
Mệnh đề. Cho ma-trận Anxm trên 𝕫p, với p là số nguyên tố. Nếu ma-trận giả nghịch đảo
của A tồn tại thì nó là duy nhất.
Mệnh đề. Trên trường 𝕫p, cho ma-trận Amxn,
(1) Nếu m > n và ATA khả nghịch,
A+ = (ATA)-1AT
(2) Nếu m < n và AAT khả nghịch,
A+ = AT(AAT)-1
Mệnh đề. Cho ma-trận Amxn, m < n, xác định trên 𝕫p, với AAT khả nghịch trên 𝕫p. Ta có
(i)
A+ = AT(AAT)-1
(ii)
AA+ = 𝕀.
(iii) A+A là ma-trận vuông cấp n và là ma-trận chiếu.
6


Mệnh đề. Trên 𝕫p, cho ma-trận khả nghịch Zmxm và ma-trận tự trực giao Vmx(n-m), m < n.
Ma-trận A được tạo bằng cách ghép các cột của Z và V, A = [Z V], thì AAT khả nghịch.
5.2. Kết quả thực nghiệm
Hai kết quả chính:
1. Hệ thống tính tốn song song phân tích số nguyên kích thước lên tới 300 chữ số,
tương ứng với 330 bit.
2. Hệ thống phục hồi được khóa cá nhân có khả năng xác định khóa cá nhân có kích
thước ngắn hơn phân nửa kích thước số ngun tố thành phần, qua đó phân tích
được số ngun là tích 2 số ngun tố có kích thước bất kỳ.
5.3. Các kết quả khác
5.3.1. Các bài báo khoa học
3. Dang Hai Van, Nguyen Dinh Thuc. Pseudoinverse matrix over finite field and its

applications. Information Science and Appplications, LNEE, Spriger-Verlag
Berlin Heidelberg, 2015.
4. D.T. Long, D.T. Thu, D.N. Thuc. A Bergman Ring Based Cryptosystem Analogue
of RSA. 2013 International Conference on IT Convergence and Security, Macau
2013.
5.3.2. Các luận văn
4. Vũ Anh Tuấn. Phát triển các công cụ nền tảng phục vụ thám mã và tính tốn tổ
hợp trên mơi trường tính tốn song song. Luận văn Thạc Sĩ, ĐHKHTN, 2014.
5. Nguyen Nhu Huan. RSA Cryptanalysis: Continued fraction and Lattice attacks.
Luận văn Đại học (CT Cử nhân tài năng), 2014.
6. Bên cạnh đó, luận án cũng góp phần đào tạo 2 NCS: Trần Đình Long và Đặng Hải
Vân, với các kết quả cơng bố trên các tạp chí cũng như các kết quả lý thuyết của
đề tài.
6. Những ngƣời thực hiện
 Trần Đan Thư, CN
 Nguyễn Đình Thúc, Đồng-CN
 Nguyễn Cao Đạt, CTV
 Nguyễn Đức Thân, NCV
 Trần Đình Long, NCS
7


 Đặng Hải Vân, NCS
 Vũ Anh Tuấn, CH
 Nguyễn Như Huân, ĐH
 Ngô Xuân Huy, ĐH
 Trần Ngọc Bảo, CTV

8



Chƣơng 2. CÁC BIẾN THỂ CỦA RSA

1. Hê ̣ mã hóa RSA gớ c
RSA là hệ mã hóa được cơng bố năm 1978 bởi 3 tác giả Ron Rivest, Adi Shamir
và Leonard Adleman. Chúng tơi tóm tắt lại hệ mã này t rong phần sau. Chi tiế t về
hệ mã RSA gố c có thể tham khảo trong nhi

ều tài liệu kinh đi ển như giới thiệu

trong tham khảo.
1.1. Mô tả hê ̣ mã
Sinh khóa
.Chọn hai số nguyên tố phân biệt 𝑝, 𝑞 và tính 𝑛 = 𝑝𝑞.
.Chọn sớ ngun 𝑒 nguyên tố cùng nhau với 𝜑 𝑛 = 𝑝 − 1 (𝑞 − 1).
.Tính 𝑑 = 𝑒 −1 (𝑚𝑜𝑑 𝜑 𝑛 ).
.Công bố 𝑛, 𝑒 như khóa công khai và giữ 𝑑 làm khóa riêng.
Mã hóa
.Mợt văn bản 𝑚 ∈ ℤ𝑛 sẽ được mã hóa thành 𝑐 = 𝑚𝑒 (mod 𝑛).
Giải mã
.𝑐 được giải mã thành 𝑐 𝑑 = 𝑚𝑒𝑑 = 𝑚(mod 𝑛).
1.1. Nhâ ̣n xét về hê ̣ mã
Nế u 𝑛 = 𝑝1 𝑟1 𝑝2 𝑟2 … 𝑝𝑘 𝑟 𝑘 là một số nguyên dương , trong đó 𝑝1 , 𝑝2 , … , 𝑝𝑘 là các số
nguyên tố phân biệt và

𝑟𝑖 ∈ ℤ, 𝑟𝑖 > 0(𝑖 = 1,2, … , 𝑘), ta sẽ dùng kí h iệu thường

đượ c dùng trong số học là rad 𝑛 = 𝑝1 𝑝2 … 𝑝𝑘 . Một kế t quả có ngay sau khi RSA
ra đời là sơ đồ mã hóa và giải mã của RSA vẫn còn hiệu lự c khi


𝑛 = rad(𝑛).

Ngay sau đây , ta sẽ chứng minh rằ ng 𝑛 = rad(𝑛) là dạng duy nhấ t của 𝑛 nế u ta
có thể xây dựng RSA trên ℤ𝑛 .
Mê ̣nh đề 1.1 Giả sử tồn tại số tự nhiên 𝑘 ≠ 1 sao cho ánh xạ
𝐹: ℤ𝑛 → ℤ𝑛
𝑥 ⟼ 𝑥𝑘
9


là đơn ánh. Khi đó 𝑛 = 𝑟𝑎𝑑(𝑛).
Theo Mệnh đề 1.1, để xây dựng hệ mã RSA trên

ℤ𝑛 thì phải chọn 𝑛 sao cho

𝑛 = rad(𝑛) và đây là điều kiện cần và đủ của 𝑛 cầ n phải thỏa mãn.
2. Các biến thể của RSA
2.1. Hê ̣ mã hóa RSA trên vành các ma trâ ̣n
Biế n thể này của RSA do các tác giả Varadharajan V . và Odoni đưa ra vào năm
1985.
Giả sử 𝑝, 𝑞 là hai số nguyên tố , 𝑛 = 𝑝𝑞 và l là một số nguyên dương . Kí hiệu
𝑀𝑙 𝑝 , 𝑀𝑙 (𝑞) và 𝑀𝑙 (𝑛) là các nhóm nhân các ma trận vng cấp 𝑙 × 𝑙 khơng suy
biế n hệ số tương ứng trên ℤ𝑝 , ℤ𝑞 và ℤ𝑛 . Các bậc của các nhóm này tương ứng
là:
𝑁𝑝 = 𝑝𝑙 − 1 𝑝𝑙 − 𝑝 … 𝑝𝑙 − 𝑝𝑙−1 ,

(2.1)

𝑁𝑞 = 𝑞𝑙 − 1 𝑞𝑙 − 𝑞 … 𝑞𝑙 − 𝑞𝑙−1 ,


(2.2)

và
𝑁𝑛 = 𝑁𝑝 . 𝑁𝑞 .

(2.3)

Chọn hai số nguyên 𝑒, 𝑑 thỏa mãn các điều kiện

1 < 𝑒, 𝑑 < 𝑁𝑛 , 𝑒, 𝑁𝑛 = 1 và

𝑒𝑑 ≡ 1(𝑚𝑜𝑑 𝑁𝑛 ). Từ đinh
̣ lý Lagrange trong lý thuyế t nhóm , chúng ta suy ra rằng
𝑚𝑁𝑛 = 𝐼𝑛 ∀𝑚 ∈ 𝑀𝑙 (𝑛) trong đó 𝐼𝑛 là ma trận đơn vị trong

𝑀𝑙 (𝑛). Từ đó 𝑚𝑒𝑑 =

𝑚 với mọi 𝑚 ∈ 𝑀𝑙 (𝑛). Điề u này cho phép chúng ta tiế n hành mã hóa

𝑚 thành

𝑐 ≡ 𝑚𝑒 và giải mã bằng cách tính 𝑐 𝑑 ≡ 𝑚 cho các văn bản 𝑚 ∈ 𝑀𝑙 (𝑛).
2.2. Hê ̣ mã hóa RSA trên nhóm đƣờng cong elliptic
Giả sử rằng 𝑝 > 3 là một số nguyên tố và 𝑎, 𝑏 là các số nguyên được chọn sao
cho 4𝑎3 + 27𝑏2 ≠ 0(𝑚𝑜𝑑 𝑝). Nhóm đường cong elliptic theo modulo 𝑝, đượ c kí
hiệu là 𝐸𝑝 (𝑎, 𝑏), là tập gồ m các cặp (𝑥, 𝑦) ∈ ℤ𝑝 × ℤ𝑝 thỏa mãn 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏
trên ℤ𝑝 , cùng với một phần tử được kí hiệu là
đượ c đinh
̣ nghiã sao cho


. Phép toán cộng „+‟ trên 𝐸𝑝 (𝑎, 𝑏)

là đơn vị của phép toán

10

, và với hai điể m


𝑃 𝑥1 , 𝑦1 , 𝑄(𝑥2 , 𝑦2 ) ∈ 𝐸𝑝 (𝑎, 𝑏), kế t quả 𝑅 = 𝑥3 , 𝑦3 = 𝑃 + 𝑄 đượ c xác đinh
̣ như
sau:
.Nế u 𝑄 là phần tử đơn vị

thì 𝑃 + 𝑄 = 𝑄 + 𝑃 = 𝑃.

.Nế u 𝑥1 = 𝑥2 và 𝑦1 = −𝑦2 thì 𝑃 + 𝑄 = ∞.
2

𝑥 = 𝜆 − 𝑥1 − 𝑥2
.Ngượ c lại, 3
vơi 𝜆 =
𝑦3 = 𝜆 𝑥1 − 𝑥3 − 𝑦1 ́

𝑦1 −𝑦2
𝑥 1 −𝑥 2

3𝑥 12 +𝑎
2𝑦1


if 𝑥1 ≠ 𝑥2 ,
if 𝑥1 = 𝑥2 and 𝑦1 ≠ −𝑦2 .

Nhóm đường cong elliptic bù với nhóm 𝐸𝑝 (𝑎, 𝑏) đượ c kí hiệu là 𝐸𝑝 (𝑎, 𝑏), đó là
tập hợ p các cặp (𝑥, 𝑦) ∈ ℤ𝑝 × ℤ𝑝 thỏa mãn phương trình 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏 trên
ℤ𝑝 , cùng với một phần tử cũng kí hiệu là

; nhưng tọa đợ 𝑦 có dạng 𝑦 = 𝑢 𝑣 với

𝑢, 𝑣 ∈ ℤ𝑝 và 𝑣 không phải là một bin
̀ h phương trong ℤ𝑝 . Phép toán cọng + trên
𝐸𝑝 (𝑎, 𝑏) đượ c đinh
̣ nghiã hoàn toàn tương tự như phép + trên 𝐸𝑝 (𝑎, 𝑏). Bậc của
các nhóm c ộng 𝐸𝑝 (𝑎, 𝑏) và 𝐸𝑝 (𝑎, 𝑏) đượ c kí hiệu tương ứng là |𝐸𝑝 𝑎, 𝑏 | và
|𝐸𝑝 𝑎, 𝑏 |, các số này có thể tính được bằng các thuật tốn thời gian đa thức

,

chẳ ng hạn như thuật toán đượ c đề cập bởi R. Schoof.
Đối với hệ mã RSA trên nhóm đường cong elliptic

, ta chọn hai số

nguyên tố

phân biệt 𝑝, 𝑞 và đặt 𝑛 = 𝑝𝑞. Chọn 𝑎, 𝑏 ∈ ℤ sao cho gcd 4𝑎3 + 27𝑏2 , 𝑛 = 1.
Kí hiệu
𝑁1 = 𝐸𝑝 𝑎, 𝑏 , 𝑁2 = 𝐸𝑝 𝑎, 𝑏 , 𝑀1 = 𝐸𝑞 𝑎, 𝑏 , 𝑀2 = 𝐸𝑞 𝑎, 𝑏 ,
và
𝐿 = 𝑁1 , 𝑁2 , 𝑀1 , 𝑀2 .

Chọn hai số nguyên 𝑒, 𝑑 sao cho 𝑒𝑑 ≡ 1 (mod 𝐿), hệ thức (𝑒𝑑) 𝑥, 𝑦 = (𝑥, 𝑦) sẽ
đúng với mọi 𝑥 ∈ ℤ𝑛 và 𝑦 = 𝑥 3 + 𝑎𝑥 + 𝑏. Điề u này cho phép chúng ta tiế n hành
mã hóa và giải mã như trong RSA gốc.
Có thể chọn bộ gờm

4 thành phần

(𝑑11 , 𝑑12 , 𝑑21 , 𝑑22 ) thay cho khóa riêng

trong đó 𝑑𝑖𝑗 = 𝑒 −1 mod 𝑁𝑖 𝑀𝑗 (𝑖, 𝑗 = 1,2). Để giải mã cặp

𝑠, 𝑡 = 𝑒(𝑥, 𝑦), thành

phầ n 𝑑𝑖𝑗 sẽ được chọn để giải mã bằng cách tính 𝑑𝑖 𝑠, 𝑡 = (𝑥, 𝑦), trong đó

11

𝑑,


1,1 nếu 𝑠, 𝑡 ∈ 𝐸𝑝 𝑎, 𝑏 ∩ 𝐸𝑞 𝑎, 𝑏 ,
𝑖, 𝑗 =

1,2 nếu (𝑠, 𝑡) ∈ 𝐸𝑝 (𝑎, 𝑏) ∩ 𝐸𝑞 𝑎, 𝑏 ,
2,1 nếu 𝑠, 𝑡 ∈ 𝐸𝑝 𝑎, 𝑏 ∩ 𝐸𝑞 𝑎, 𝑏 ,
2,2 nếu (𝑠, 𝑡) ∈ 𝐸𝑝 (𝑎, 𝑏) ∩ 𝐸𝑞 𝑎, 𝑏 .
𝑖𝑗

trên 𝐸𝑛 (𝑖, 𝑗 = 1,2) đượ c đinh
̣ nghiã hoàn toàn tương tự


Do phép toán c ộng

nhau nên tọa độ thứ nhấ t 𝑥𝑘 trong phương trình 𝑥𝑘 , 𝑦𝑘 = 𝑘(𝑥, 𝑦) là như nhau ,
𝑖𝑗

không phụ thuộc vào 𝑖, 𝑗 mà (𝑥, 𝑦) ∈ 𝐸𝑛 .
Demytko đã đưa ra công thứ c tính cho 𝑥𝑘 như sau , bằ ng cách đưa về tọa độ
𝑋

𝑌

𝑍

𝑍

thuầ n nhấ t = , 𝑦 =

:
𝑋2𝑖 = (𝑋𝑖2 − 𝑎𝑍𝑖2 )2 − 8𝑏𝑋𝑖 𝑍𝑖3 𝑚𝑜𝑑 𝑛 ,
𝑍2𝑖 = 4𝑍𝑖 𝑋𝑖3 + 𝑎𝑋𝑖 𝑍𝑖2 + 𝑏𝑍𝑖3 𝑚𝑜𝑑 𝑛 ,

2
𝑋2𝑖+1 = 4𝑏𝑍𝑍𝑖2 𝑍𝑖+1
+ 2𝑍 𝑎𝑍𝑖 𝑍𝑖+1 + 𝑋𝑖 𝑋𝑖+1 𝑋𝑖 𝑍𝑖+1 + 𝑋𝑖+1 𝑍𝑖 )−𝑋(𝑋𝑖 𝑍𝑖+1

− 𝑋𝑖+1 𝑍𝑖 )2 𝑚𝑜𝑑 𝑛 ,
𝑍2𝑖+1 = 𝑍(𝑋𝑖 𝑍𝑖+1 − 𝑋𝑖+1 𝑍𝑖 )2 𝑚𝑜𝑑 𝑛 ,
𝑥𝑘 =


𝑋𝑘
.
𝑍𝑘

2.3. Hê ̣ mã hóa RSA trên vành thƣơng các đa thƣ́c
Biế n thể này của RSA cùng với hệ mã RSA trên vành thương các số nguyên
Gauss do các tác giả El -Kassar A .N., R. Hatary và Y . Awad đưa ra vào năm
2004. Trong biế n thể này , vành đa thức ℤ𝑝 [𝑥] đượ c xé t đế n với 𝑝 là một số
nguyên tố . Chọn hai đa thức bất khả quy 𝑔 𝑥 , 𝑕 𝑥 ∈ ℤ𝑝 [𝑥] có bậc tương ứng là
𝑟, 𝑠 và 𝑓 𝑥 = 𝑔 𝑥 . 𝑕(𝑥) thì số các phần tử khả nghịch trong các vành thương
ℤ𝑝 [𝑥]/<g(x)> , ℤ𝑝 [𝑥]/<h(x)> và
L= 𝑝𝑟 − 1

ℤ𝑝 [𝑥]/<f(x)> lầ n lượ t là

𝑝 𝑠 − 1 . Khi đó hệ thức

𝑝𝑟 − 1, 𝑝 𝑠 − 1 and

𝑚(𝑥)𝑒𝑑 ≡ 𝑚(𝑥) sẽ đúng với mọi

𝑚(𝑥) ∈

ℤ𝑝 [𝑥]/<f(x)>, trong đó 𝑒, 𝑑 là các số nguyên được chọn sao cho 𝑒𝑑 ≡ 1(𝑚𝑜𝑑 𝐿).
Hệ thứ c 𝑚(𝑥)𝑒𝑑 ≡ 𝑚(𝑥) cho phép chúng ta mã hóa văn bản

𝑚 𝑥 ∈ ℤ𝑝 𝑥 /<

𝑓 𝑥 > thành 𝑐 𝑥 = 𝑚𝑒 (𝑥) và sau đó giải mã 𝑐(𝑥)thành 𝑐 𝑑 (𝑥) ≡ 𝑚(𝑥).


12