ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
TRẦN ĐÌNH LONG

CÁC TÍNH CHẤT ĐẠI SỐ
CỦA HỆ MÃ CÔNG KHAI RSA
VÀ KHẢ NẰNG MỞ RỘNG

Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số chuyên ngành: 62 48 01 01

Phản biện 1: PGS.TS. Trần Văn Hạo
Phản biện 2: PGS.TS. Đỗ Văn Nhơn
Phản biện 3: PGS.TS. Dương Anh Đức
Phản biện độc lập 1: PGS.TS. Nguyễn Đức Nghĩa
Phản biện độc lập 2: TS. Trần Nam Dũng

NGƯỜI HƯỚNG DẪN KHOA HỌC
1. PGS.TS. Trần Đan Thư
2. PGS.TS. Nguyễn Đình Thúc

Tp. Hồ Chí Minh – 2015


LỜI CÁM ƠN
Kính dâng lên Ba Mẹ, người đã
Thương tặng Châu, Ômai và Alpha,
sinh thành và nuôi dưỡng để con những người đã chia sẻ mọi khó
có ngày hôm nay.
khăn, là chỗ dựa vững chắc về tinh
thần và vật chất trong suốt cả cuộc

MỤC LỤC
Bảng thuật ngữ Anh-Việt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

M

...................................................

2

Chương 1 Tổng quan về RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1 Hệ mã RSA gốc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.1 Mô tả hệ mã. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.1.2 Nhận xét về hệ mã. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.2 RSA trên vành

.........................................

1.5 Thám mã RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.1 Thám mã RSA có khóa riêng nhỏ . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.1.1 Thám mã RSA bằng liên phân số . . . . . . . . . . . . . . . . 17
1.5.1.2 Thám mã RSA bằng cách tìm nghiệm gần đúng
có nghịch đảo nhỏ . . . . .

21

1.5.1.3 Thám mã RSA bằng dàn hai chiều . . . . . . . . . . . . . .

24

1.5.2 Thám mã RSA có khóa chung nhỏ . . . . . . . . . . . . . . . . . . . . . . 24
1.5.2.1 Thám mã khi biết một phần văn bản . . . . . . . . . . . . . . 25
1.5.2.2 Thám mã qua các văn bản có liên quan . . . . . . . . . . . . 25


1.5.2.3 Rò rĩ thông tin từ khóa chung nhỏ . . . . . . . . . . . . . . . 25
1.5.3 Phân tích modulus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

1.6 Nhận xét về Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Chương 2 Xây dựng sơ ồ cho RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.1 RSA trên vành thương của vành Euclid. . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.1 Sơ đồ RSA trên vành thương của vành Euclid. . . . . . . . . . . . 31
2.1.2 So sánh với các hệ mã RSA đã biết. . . . . . . . . . . . . . . . . . . . .



2.3.2.4 Thám mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.3.3 Nhận xét về hệ mã. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Chương 3 Thám mã RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1 Thám mã RSA bằng dàn hai chiều. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.1 Thực nghiệm thám mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.2 Đặt vấn đề. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.1.3 Điều kiện để tấn công dàn hai chiều vào RSA luôn thành công 55
3.1.4 Nhận xét về phương pháp tấn công RSA bằng dàn hai chiều.

59

3.2 Bài toán DLP trên nhóm GL(2,p). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.1 Đặt vấn đề. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

3.2.2 Bài toán DLP trên nhóm GL(2,p). . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.3 Ý tưởng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2.4 Chéo hóa Jordan của ma trận. . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.2.5 Thuật toán đưa bài toán DLP trên nhóm GL(2,p)
về trường cơ sở. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.2.6 Ví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.2.7 Nhận xét. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

Liên phân số

Cryptosystem

Hệ mã hóa

Cryptanalysis

Thám mã

Discrete logarithm problem

Bài toán logarithm rời rạc

Homomorphism

Đồng cấu

Instance

Biến thể hiện

Lattice

Dàn

Lattice reduction algorithm

Thuật toán tìm cơ sở thu gọn của dàn


khóa công khai, một khái niệm có t nh cách mạng trong mã hóa thông tin. Ngày
nay, các hệ mã hóa khóa công khai được d ng rộng rãi trên hầu hết các ĩnh vực có
trao đổi thông tin như đảm bảo an toàn mạng Int rn t, giao dịch trong ngân hàng,…
Là một hệ mã hóa khóa công khai đầu tiên, RSA à một hệ mã hóa nổi tiếng
và được d ng rộng rãi nhất, do 3 tác giả Riv st, Shamir và Ad man giới thiệu vào
năm 1

8 [63]. Năm 2

2, ba tác giả này được Viện Toán Học C ay (M ) trao giải

thưởng cho RSA như à một ứng dụng đơn giản và hiệu quả nhất của Toán học.
Việc không có một hệ mã nào d ng rộng rãi như RSA cho đến bây giờ cho thấy đây
à một hệ mã an toàn, khó bị tấn công. Ch nh vì vậy có rất nhiều công trình iên
quan đến RSA.
Trên thế giới, có thể chia các công trình ý thuyết iên quan đến RSA àm hai
oại: phát triển các biến thể của RSA và thám mã RSA.
Sự phát triển các biến thể của RSA có thể chia àm hai hướng. Trong hướng
thứ nhất, các tác giả tập trung vào hệ mã RSA gốc nhưng cải tiến các thuật toán mã
hóa và giải mã nhằm giảm độ phức tạp tính toán hoặc xây dựng RSA trên vành
với

có dạng phức tạp hơn thay vì à t ch của hai số nguyên tố phân biệt. Công

trình như [11] là ví dụ về RSA được cải tiến thuật toán mã hóa sao cho có thể tạo ra
cùng lúc nhiều chữ ký điện tử. Công trình [33] của D. Pointcheval cải tiến thuật
toán mã hóa của RSA nhằm mục đ ch àm cho văn bản đã mã hóa có t nh ngẫu
nhiên, qua đó tránh được cách tấn công bằng cách chọn văn bản gốc (chosen
plaintext attack). Đối với RSA trên


, với

à t ch của hai số nguyên tố phân biệt. Năm 1

Demytko [59] giới thiệu tại hội nghị
dựng trên nhóm các đường cong

ROCR PT một phiên bản của RSA xây

iptic. Do

à vành thương của vành số nguyên

nên cách xây dựng tự nhiên nhất à xây dựng biến thể của RSA trên vành thương
của các vành có phép chia (vành uc id). Các tác giả
Y. Awad [36] vào 2

- assar A.N., R. Hatary và

xây dựng các biến thể của RSA trên vành thương của vành

số nguyên Gauss và trên vành thương của vành các đa thức có hệ số trên trường
hữu hạn. Việc xây dựng các biến thể mới này của RSA đều dựa trên t nh chất cụ thể
của cấu trúc đại số mà RSA được xây dựng trên đó.
Song song với việc phát triển các biến thể của RSA, bài toán thám mã RSA
cũng thu hút được nhiều tác giả [23-24], [26-27], [35] và [40]. Cách tấn công cổ
điển dựa vào bài toán phân t ch một số nguyên dương

thành các thừa số nguyên


một công cụ rất hiệu quả để tấn công RSA trong các trường hợp khóa riêng

nhỏ,


4

vì vậy có rất nhiều công trình dùng công cụ dàn để thám mã RSA như [12], [19],
[22], [61]. Một điều đáng ngạc nhiên à cho d có rất nhiều công trình thám mã
RSA gốc, có rất t các công trình khảo sát thám mã các biến thể của RSA. Điều này
cho thấy hệ mã RSA gốc vẫn được quan tâm hơn rất nhiều so với các biến thể của
nó. Tuy vậy, các biến thể của RSA ngày càng được quan tâm và khảo sát nhiều hơn.
Có thể kế ra đây các công trình như [1 ] khảo sát thám mã biến thể RSA trong [67],
công trình [55] khảo sát thám mã hệ mã Multi-Power RSA của T. Collins trong [66]
hay công trình [ 2] thám mã RSA trong trường hợp khóa chung lớn và bị lộ một
phần.
Trong nước, các công trình hay uận án iên quan đến RSA còn rất khiêm
tốn. Các uận án thường ch dừng ại ở mức hiện thực RSA có cải tiến các thuật toán
số học trong mã hóa và giải mã [9-10] khảo sát áp dụng chữ ký điện tử của RSA
[2], [7]; iệt kê ại các phương pháp tấn công RSA [1] hay áp dụng RSA trong bảo
mật thông tin [3]. Cuốn sách viết nhiều nhất về RSA như [6] ch tóm tắt lại các
nghiên cứu và thám mã về RSA. Có rất ít các luận án tiến sĩ như [8] đề cập đến các
tiêu chuẩn an toàn cho các tham số trong hệ mã RSA như modu us, các modu i hay
các khóa riêng, khóa chung.
Xuất phát từ những khảo sát trên đây về hệ mã RSA ở trong nước và quốc tế,
uận án này nhằm giải quyết các vấn đề sau:
(1) Nghiên cứu hệ mã RSA gốc, ta gọi là RSA 2 số nguyên tố, và tất cả các
biến thể của nó. Giải th ch vì sao các biến thể của RSA ch xây dựng trên các cấu
trúc đại số khác với


dựng dựa trên vành

rgman và tuân th o sơ đồ vừa đề xuất.

Chương 3 đề cập đến các kết quả đạt được của tác giả trong ĩnh vực thám
mã RSA. Các kết quả này bao gồm việc đưa ra điều kiện cho khóa riêng nhằm đảm
bảo phương pháp tấn công RSA bằng dàn hai chiều luôn thành công và việc đưa bài
toán logarithm rời rạc (DLP – Discrete Logarithm Problem) trên nhóm nhân
về bài toán DLP trên trường cơ sở
hai của

hoặc trên một trường mở rộng bậc

.

Do các thuật toán tìm cơ sở thu gọn trên dàn được dùng nhiều trong việc
trình bày thám mã RSA, các kiến thức cơ sở về dàn sẽ được nhắc lại trong phần phụ
lục.


6

Phần kết uận tóm tắt lại những kết quả mà luận án đã đạt được, đồng thời
nêu ra một số hướng nghiên cứu mở có thể phát triển được trong quá trình thực hiện
uận án.
Được các thầy hướng dẫn giới thiệu hướng nghiên cứu về mã hóa thông tin
lần đầu tiên vào tháng 3/2009, tác giả cảm thấy rất thích thú và phù hợp với hướng
nghiên cứu này. Tác giả mong muốn rằng những kết quả đạt được khi thực hiện
luận án sẽ là những minh chứng cho thấy ứng dụng của toán học vào ngành mã hóa
thông tin


, bao gồm:

-Hệ mã RSA trên vành ma trận.
-Hệ mã RSA trên nhóm đường cong elliptic.
-Hệ mã RSA trên vành thương các đa thức.
-Hệ mã RSA trên vành thương các số nguyên Gauss.
5. Tóm tắt các kết quả đã có về thám mã RSA.
Chúng tôi trình bày trong chương này hệ mã hóa khóa công khai RSA gốc, sau
đó giới thiệu một số biến thể của RSA được xây dựng trên các cấu trúc khác
cũng như một số kết quả đã có về thám mã RSA. Chương này à cơ sở để trình bày
các chương sau. Chúng tôi cũng đưa ra câu giải thích vì sao các biến thể của RSA
được xây dựng trên các cấu trúc đại số khác
1.1

ệ

ãR

.

gốc

RSA à hệ mã hóa được công bố năm 1

8 bởi 3 tác giả Ron Riv st, Adi

Shamir và L onard Ad man [63]. Chúng tôi tóm tắt ại hệ mã này sau đây. Chi tiết
về hệ mã có thể tham khảo tại các tài iệu [4], [5], [63].


-Một văn bản

sẽ được mã hóa thành

.

iải mã
- được giải mã thành
1.1.2 Nhận

t ề hệ

.

ã
à một số nguyên dương, trong đó

Với
các số nguyên tố phân biệt và

, chúng ta sẽ d ng k hiệu

thường được d ng trong số học à

. Một kết quả của T. Collins

et. al. [66] vào 1997 à xây dựng hệ mã RSA trên
ch ra rằng
trên


trong đó

biệt. Giả sử phản chứng rằng

à các số nguyên tố phân

, khi đó tồn tại t nhất một trong các số

ớn hơn . hông mất tổng quát chúng ta có thể giả sử
Xét
. Suy ra

, r ràng

Do

nên

, mâu thuẩn với t nh đơn ánh của . ■

Mệnh đề trên cho thấy rằng để xây dựng hệ mã RSA trên
sao cho

.

và đây à điều kiện cần và đủ của

thì phải chọn

cần phải thỏa mãn. Điều

-Tạo đồng thời nhiều chữ ký điện tử: đó à

atch RSA của tác giả A. Fiat

[11] cho phép tính toán một lúc nhiều chữ k điện tử với độ phức tạp t nh toán t hơn
so với độ phức tạp tính toán của việc tạo ra từng chữ k điện tử một.
-Cho phép thực hiện nhanh quá trình giải mã: cải tiến này làm cho RSA có
thể sử dụng trong các ứng dụng chuyên biệt nào đó, chẳng hạn cần tạo chữ k điện
tử mà sau đó có thể kiểm tra nhanh chóng trên các tổng đài điện thoại. Rebalanced
RSA của tác giả M. Wiener [58] là ví dụ cho cải tiến này, trong đó quá trình giải mã
được thực hiện bằng nhiều khóa riêng thay vì một khóa riêng, sau đó văn bản gốc
được tính dựa vào định lý phần dư Trung Hoa.
Trong hướng thứ hai, các tác giả khảo sát các hệ mã RSA trên vành

với

không còn là tích của hai số nguyên tố phân biệt. Hai kết quả đáng kể trong hướng
này thuộc về T. Collins [66] khảo sát trường hợp n là tích của nhiều số nguyên tố
phân biệt (MultiPrime RSA), và T. Takagi [67] khảo sát khi
trong đó

là hai số nguyên tố phân biệt, còn

có dạng

là số nguyên dương (Mu tiPow r

RSA). Các biến thể này của RSA sau đó được các tác giả khác kết hợp với các k
thuật cải tiến trong hướng thứ nhất, có thể kể ra các công trình sau đây.
-Công trình của C. A ison vào năm 2

à các nhóm nhân các ma trận vuông cấp


11

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 à

và
Chọn hai số nguyên
và

thỏa mãn các điều kiện

. Từ định ý Lagrange trong ý thuyết nhóm, chúng ta suy ra

rằng

trong đó
với mọi

thành
1.3.2

à ma trận đơn vị trong

sao cho
k hiệu à

, à tập gồm các cặp

trên

, c ng với một phần tử được k hiệu à

định nghĩa sao cho

thỏa mãn

.Nếu

và

được

được xác định như

sau:
à phần tử đơn vị

. Phép toán + trên

à đơn vị của phép toán, ngoài ra với hai điểm
, kết quả

.Nếu

với

được k hiệu à

; nhưng tọa độ

có dạng

không phải à một bình phương trong

. Phép toán + trên

được định nghĩa hoàn toàn tương tự như phép + trên

. ậc của các

nhóm

và

được k hiệu tương ứng à

và

,

các số này có thể t nh được bằng các thuật toán thời gian đa thức, chẳng hạn như
thuật toán được đề cập trong [60].
Đối với hệ mã RSA trên nhóm đường cong elliptic, chúng ta chọn hai số
nguyên tố phân biệt

. Để giải mã cặp

sẽ được chọn để giải mã bằng cách t nh

, thành
, trong đó


13

Do phép toán

trên các tập

,
được định nghĩa hoàn toàn tương tự

và
nhau nên tọa độ thứ nhất

trong phương trình

không phụ thuộc vào việc

à như nhau,

thuộc tập nào trong 4 tập trên.

Demytko trong [59] đã đưa ra công thức t nh cho
về tọa độ thuần nhất

có bậc tương ứng à

và đặt

. Số các phần tử khả nghịch trong các vành thương


14

<h(x)> và

<g(x)>,

<f(x)> tương ứng à

; trong đó với
sinh bởi

, kí hiệu

ch ideal của

, tức là

.

hi đó hệ thức
trong đó

và

ss

Vành các số nguyên Gauss à vành con của trường số phức

Chuẩn trên
à

được t nh bởi

. Một phần tử

định nghĩa bởi

. Các ước của đơn vị trong
à nguyên tố khi và ch khi

à t ch của ước

đơn vị với một trong các phần tử có dạng sau:
i.

, khi đó

ii.

với
, khi đó

được gọi à phần tử nguyên tố dạng .
à số nguyên tố thông thường có dạng


và t nh
và

. Văn bản à các phần tử

sẽ được mã hóa thành
.

. Sau đó

sẽ được giải mã


15

1.3.5 Nhận xét về các biến th c a RSA
Bây giờ chúng tôi sẽ so sánh sự an toàn của hệ mã RSA với các biến thể của nó
dưới khía cạnh thám mã bằng cách phân t ch modu us. Để đơn giản cho việc phân
tích, chúng tôi giả sử rằng độ dài của mỗi văn bản là 1024 bit và thuật toán phân
tích modulus

là thuật toán vét cạn.

Trước hết, do có rất nhiều thuật toán hiệu quả phân tích một đa thức cho trước
như thuật toán Berlekamp [52], thuật toán Ben-Or [53], thuật toán
Cantor-Zassenhaus [71]…nên biến thể của RSA trên vành thương các đa thức trong
phần 1.3.3 có thể bị thám mã hoàn toàn nếu áp dụng các thuật toán này.
Đối với hệ mã RSA gốc, do mỗi văn bản


với hệ mã RSA gốc.
Đối với hệ mã RSA trên vành thương các số nguyên Gauss, mỗi văn bản
có độ lớn 1024 bit nên

và

đều có độ lớn 512 bit. Do đó độ lớn của

không thể vượt quá 1025 bit. Do
vượt quá 1025 bit. Nếu
1025 bit, vì vậy

thì

không vượt quá 256 bit. Việc phân tích

nên

không

không vượt quá
bằng thuật toán vét

cạn chưa hẳn đơn giản hơn trong trường hợp phân tích modulus của hệ mã RSA
gốc. Tuy nhiên, mặc dù các tính toán trong quá trình mã hóa và giải mã trong
trường hợp này được thực hiện trong vành thương
trên

và sau đó ấy modulo theo


được d ng đến.
Đối với hệ mã RSA trên nhóm đường cong elliptic, mỗi văn bản là một phần tử
, do đó

sẽ có c ng k ch thước với

là 1024 bit. Việc phân tích modulus

trong trường hợp này hoàn toàn như trong hệ mã RSA gốc. Tuy nhiên độ phức tạp
tính toán trong các quá trình mã hóa và giải mã trong trường hợp này là lớn hơn
nhiều so với hệ mã RSA gốc. Đối với hệ mã RSA gốc, mã hóa
phải thực hiện xấp x

cần

phép nhân theo thuật toán ũy thừa nhanh. Đối với hệ

mã RSA trên nhóm đường cong elliptic, các công thức ở phân 1.3.2 ch ra để tính
trong công thức mã hóa

cần thực hiện ít nhất xấp x

phép

toán.
Các phân t ch trên đây ch ra rằng, với cùng một modulus , việc thiết lập hệ mã
RSA gốc à đơn giản và an toàn hơn các biến thể của nó. Điều này giải thích phần
nào hệ mã RSA gốc được dùng rộng rãi hơn các biến thể của nó.
Trong các biến thể trên của RSA, hệ thức
phép thực hiện mã hóa

trên trường cyclotomic bởi tác giả Uematsu.Y [69]. Tác giả

oyama . sau đó đưa ra sơ đồ cho RSA với hàm mã hóa là một phân thức theo hai
biến trên nhóm elliptic.
1.5 Thám mã RSA
Thật khó để có thể liệt kê ra hết tất cả các công trình nghiên cứu về thám mã
RSA. Ngoài một số phương pháp thám mã hệ mã RSA khi hệ mã này được dùng
một cách máy móc, chúng tôi chia các phương pháp thám mã RSA thành hai oại
sau đây.
1.5.1 Thám mã hệ mã RSA có khóa riêng nhỏ
Tiêu biểu cho thám mã loại này là công trình của M. Wiener và D. Boneh
như sau.
1.5.1.1 Thám mã RSA bằng liên phân số
Cách thám mã RSA bằng liên phân số do M. Wi n r đưa ra năm 1

. Chi

tiết về cách thám mã này có thể đọc ở [57], chúng tôi mô tả một cách tóm tắt lại như
sau.
1.5.1.1.1 Liên phân số
Với

là số nguyên dương và
để ch

…))).

liên phân số

là các số nguyên, Wiener dùng kí hiệu

Tính

do
và

Endfor

Một tính chất có thể thấy ngay của liên phân số là với số

thì

nếu

chẵn,

và
nếu

lẻ.

1.5.1.1.2 Tìm số hữu tỷ bằng liên phân số nếu biết giá trị g n úng


19

Thuật toán thám mã của Wiener dựa trên thuật toán sau đây. Giả sử
là hai phân số dương mà
được

với

Endfor
Thuật toán trên sẽ thành công nếu phân số tìm được

thỏa mãn
nếu

chẵn,

nếu m lẻ,
đồng thời số

thỏa mãn điều kiện sau đây:
nếu

,

nếu

nếu
nếu
Trong đó

,

chẵn,
lẻ,

,
.