1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

Tô Danh Dũng

NGHIÊN CỨU HỆ MẬT RSA VỚI SỐ MŨ GIẢI
MÃ LỚN VÀ ỨNG DỤNG CHO CHỮ KÝ SỐ

Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60.48.15

TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2013


2

Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Người hướng dẫn khoa học: TS. Nguyễn Khắc Lịch

Phản biện 1: ……………………………………………………………………………
Phản biện 2: …………………………………………………………………………..

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu
chính Viễn thông
Vào lúc:

nhiên p, q là hai số nguyên tố lớn phân biệt; xác định modulus n = p.q ; tính φ(n)= (p-1)(q1) rồi thông qua các tham số đó tính e ( thường là chọn e nhỏ để quá trình mã hóa đơn giản);
sau đó tính d theo công thức de = 1 + k.φ(n)và thường e nhỏ thì d có được cũng nhỏ. Muốn
tìm được d lớn người ta làm ngược lại đó là chọn e, tìm p,q thỏa mãn điều kiện đủ nào đó
sao cho với cách này ta sẽ có được d có kích thước gần bằng modulus n.
Luận văn sẽ nghiên cứu về hệ mật RSA với số mũ giải mã lớn và ứng dụng cho chữ
ký số để chữ ký số an toàn và bảo mật hơn.

2. Mục đích nghiên cứu.
Phân tích tính an toàn của hệ mật RSA. Đưa ra một giải pháp nhằm tăng tính an toàn cho
chữ ký số RSA đó là : chọn số mũ giải mã lớn và ứng dụng vào chữ ký số.


2

3. Đối tượng và phạm vi nhiên cứu.
- Hệ mật RSA là đối tượng nghiên cứu chính của đề tài nhằm phát hiện các phương
pháp tấn công , bẻ gẫy RSA ; qua đó ứng dụng thử nghiệm trên chữ ký số RSA với thuật
toán chọn số mũ giải mã lớn.
- Phạm vi nghiên cứu: đề tài nghiên cứu cách ngăn ngừa một kiểu tấn công trong
trường hợp sử dụng số mũ giải mã d nhỏ. Sau đó xây dựng và cài đặt thật toán thử nghiệm
trên chữ ký số giúp tăng tính an toàn cho chứ ký số RSA.

4. Giả thiết khoa học.
Cài đặt thuật toán thành công sẽ cho ta được số mũ giải mã lớn; điều này có thể
chống lại các cách tấn công của M.Wiener[8] và Boneh Durfee[3] và làm tăng tính an toàn
cho hệ mật RSA và chữ ký số RSA.

5. Phạm vi đề tài.
-


Trong chương này sẽ giới thiệu về chữ ký số và áp dụng lý thuyết đã tìm hiểu ở các
chương trước để xây dựng chữ ký số RSA với số mũ giải mã lớn.
KẾT LUẬN VÀ KIẾN NGHỊ
Tổng kết các kết quả đã đạt được và các mong muốn, kiến nghị để phát triển hệ thống.


4

CHƯƠNG 1: TỔNG QUAN VỀ LÝ THUYẾT MẬT MÃ
1.1. Các khái niệm cơ bản.
Trong lý thuyết mật mã có một số thuật ngữ cơ bản sau:
Bản rõ (PlainText): là nội dung của thông điệp cần gửi đi yêu cầu được đảm bảo an
toàn.
Bản mã (CipherText): là thông điệp gửi đi được mã hóa.
Mã hóa (Encryption): quá trình chuyển đổi thông tin từ bản rõ sang bản mã. Trong
quá trình này thông tin trong bản rõ sẽ được ẩn đi và do đó bất kỹ một người nào đọc thông
điệp này cũng không hiểu được trừ trường hợp người đó có thể giải mã (PlainText →
CipherText)
Giải mã (Decryption): là quá tình giải mã để lấy lại thông tin ban đầu, ngược với quá
trình mã hóa (CipherText → PlainText).
Trong luận văn này có sử dụng thêm các kí hiệu sau:
A, B: Hai người muốn trao đổi thông tin
Mm: Kẻ thù muốn lấy cắp thông tin
Khái niệm hệ mật mã
Một hệ mật là một bộ gồm 5 thành phần (P, C, K, E, D) với:
P (PlainText): Tập hợp hữu hạn các bản rõ.
C (CipherText): Tập hợp hữu hạn các bản mã.
K (Key): Tập hợp các khóa.
E: Tập các quy tắc mã hóa.
D: Tập các quy tắc giải mã.

sử dụng các khóa khác nhau nhưng mối liên hệ giữa chúng dễ dàng tính toán được.

1.2.2. Mã hóa bất đối xứng
Định nghĩa mã hóa bất đối xứng: là hệ mật mã bao gồm một tập hợp các phép biến
đổi mã hóa {Ee} và một tập hợp các phép biến đổi giải mã {Dd} được gọi là mật mã khóa
công khai hoặc mật mã bất đối xứng nếu với mỗi cặp khóa (e, d) trong đó khóa mã hóa e
được gọi là khóa công khai (có giá trị mà ai cũng biết), khóa giải mã d được gọi là khóa
riêng hay khóa bí mật. Hệ mật mã này phải đảm bảo an toàn để không có khả năng tính
được d từ e.
Nguyên tắc hoạt động: Người nhận B sinh ra cặp khóa gồm: khóa công khai Kp và
khóa bí mật Kr. Sau đó B sẽ gửi Kp cho A và khóa này được công khai ai cũng có thể biết. A
sẽ dùng Kp để mã hóa thông điệp và gửi thông điệp đã mã hóa cho B. Lúc này, B sẽ cùng Kr
để giải mã thông điệp mà A gửi.


6

1.3. Một số khái niệm toán học.
Trong phần này luận văn trình bày lại các lý thuyết và kết quả cơ bản nhất của lí
thuyết số có liên quan đến mật mã.
Ký hiệu: Z: Tập hợp các số nguyên.
N: Tập hợp các số tự nhiên {0,1,2……}.

1.3.1. Ước số chung lớn nhất GCD()
Ước số chung lớn nhất của các số nguyên dương a, b được kí hiệu GCD(a,b), là số
nguyên lớn nhất mà cả a, b đều chia hết cho nó.
Và gcd (a,0) = gcd(0,a) = a.
gcd (a,b) = gcd( a , b ).
Ví dụ: gcd (15,9) = 3


3.2 a ← b, b ← r, x2 ← x1, x1 ← x, y2 ← y1, y1 ← y.
4. d ← a, x ← x2, y ← y2, return (d, x, y).
Thuật toán Euclid mở rộng có độ phức tạp là O((lg n)2) phép toán bit.

1.3.5. Các phép toán cơ bản trong không gian Modulo
Toán tử modulo còn được gọi là toán tử mod; a mod n là phần dư của a chia n được
kí hiệu r = a mod n, nói cách khác a = q*n + r trong đó q là một số nguyên, r thuộc tập các
số nguyên {0, 1, 2, ……, n-1}.
Định nghĩa đồng dư:
Cho a và b là các số nguyên, a được gọi là đồng dư với b theo modulo n, ký hiệu là a
≡ b (mod n) nếu a-b = k*n với k là số nguyên bất kỳ (hay a-b chia hết cho n).

1.3.6. Thặng dư bậc hai
Định nghĩa 1: Cho a ∈ Zn*, a được gọi là thặng dư bậc hai modulo n nếu tồn tại một
số x ∈ Zn* thỏa mãn x2 ≡ a (mod n). Nếu không tồn tại một số x như vậy thì a được gọi là
không thặng dư bậc hai modulo n. Tập tất cả các giá trị thặng dư bậc hai modulo n được kí
hiệu Qn và tập tất cả các giá trị không thặng dư bậc hai modulo n được kí hiệu Qn .

1.3.7. Các thuật toán trong Zn
Thuật toán tính nghịch đảo nhân trong Zn [9]:
Input: a ∈ Zn .
Output: a-1 mod n; nếu a khả nghịch.


8

-------------1. Sử dụng thuật toán Euclid mở rộng để tìm x, y thỏa mãn d = ax + ny trong đó d =
gcd (a,n).
2. Nếu d > 1 thì a-1 mod n không tồn tại. Ngược lại, return (x).
Thuật toán bình phương và nhân để tích lũy thừa trong Zn[9]


If k0 = 1 then b ← a.

4.

For i: = 1 to t do
A ← A2 mod n.
If ki = 1 then b ← A . b mod n.

5.

return(b).

1.4. Độ phức tạp tính toán.
1.4.1. Khái niệm cơ bản
Định nghĩa 1: Kích thước đầu vào là số lượng bit cần thiết dùng để biểu diễn dữ liệu đầu
vào.
Định nghĩa 2: Thời gian thực hiện thuật toán trên dữ liệu đầu vào là số lượng các phép toán
cơ bản hoặc “các bước” được thực hiện.

1.4.2. Kí hiệu tiệm cận
Một số định nghĩa:
(i) f(n)= O (g(n)) nếu tồn tại một hằng số c dương và một số nguyên dương n0 thỏa
mãn 0 ≤ f(n) ≤ c.g(n)với mọi n ≥ n0.


9

(ii) Một thuật toán được gọi là có độ phức tạp đa thức, hoặc có thời gian đa thức, nếu
số các phép tính cần thiết khi thực hiện thuật toán không vượt quá O(logkn), trong đó n là độ

khoảng 1 triệu phép tính/giây được mô tả trong [9] như sau:
Số chữ số thập phân

Số phép tính bit

Thời gian

50

1,4.1010

3,9 giờ

75

9,0.1012

104 ngày

100

2,3.1015

74 năm

200

1,2.1023

3,8.109 năm

5. Khi đó căp khóa công khai là(n,e) và khóa bí mật là d
Số nguyên e và d được tạo ra trong thuật toán trên được gọi là số mũ mã hóa và số
mũ giải mã còn n được gọi là modulus của RSA.

2.1.2. Quá trình mã hóa RSA
Bây giờ, giả sử A là người muốn gửi một thông điệp m cho B và B là người phải giải
mã. Sử dụng RSA, người sử dụng A cần làm theo các bước sau:
1. Xác thực khóa công khai(n,e).
2. Biểu diễn thông điệp như là một số nguyên m trong đoạn[0, n-1].
3. Tính c = me mod n(sử dụng thuật toán bình phương và nhân liên tiếp để tính lũy
thừa modulus n).
4. Gửi bản mã hóa c đến B

2.1.3. Quá trình giải mã RSA
Để có được bản rõ m từ c, B làm như sau:
Sử dụng khóa bí mật d để khôi phục m = cd mod n.
Ví dụ : Ở đây ta sử dụng thông điệp A gửi cho B là một số; chúng ta giả thiết rằng giữa A và B
có một cách để chuyển dỗi giữa văn bản và số. Các bước sẽ thực hiện như sau:
1. B sẽ chọn hai số nguyên tố. chúng ta giả sử p = 23 và q = 41. Thực tế B cần phải
chọn hai số lớn hơn rất nhiều.
2. B sẽ tính ra tích của p*q. Ta có p*q = 23*41 = 943 vậy n = 943; giá trị này sẽ
được chuyển đến A.
3. B sẽ chọn một số nguyên e là nguyên tố cùng nhau với (p-1)*(q-1). Trường hợp
này ta có (p-1)*(q-1) = 22.40 = 880, e chọn là 7, e chính là thành phần khóa công khai.
4. A đã có (n,e) =(943,7) do b gửi đến. A sẽ sử dụng cặp khóa này để mã hóa thông
điệp m và gửi cho B. Ta giả sử thông điệp m = 35.
5. A tính giá trị của c: c = me (mod n) = 375 (mod 943) = 545. Giá trị 545 là bản mã
và được A gửi cho B.
6. B muốn giải mã thông điệp 545 thì B phải tìm số d thỏa mãn e*d = 1(mod (p 1)*(q -1)). Trường hợp này, 7d = 1 (mod 880); d = 503.



1

1

1

0

1

1

1

1

1

1

A

545

545

923

400


Vậy B sẽ giải mã thông điệp là m = 35.

2.2. Các khả năng tấn công lên hệ mật RSA
Hệ mật RSA là hệ mật phổ biến nhất hiện nay, nó được triển khai và ứng dụng trong
nhiều hệ thống thương mại nhằm cung cấp tính bảo mật cũng như xác thực của dữ liệu. Từ
khi được công bố, RSA đã được phân tích tính an toàn bởi nhiều nhà khoa học. Và đã có
một số cuộc tấn công lên hệ mật RSA xong chúng chủ yếu là minh họa cho việc sử dụng
RSA không đúng cách. Vấn đề thám mã đối với RSA hiện nay đang được các nhà khoa học
tập trung vào các kẽ hở của RSA và được chia làm 4 loại: tấn công cơ bản, tấn công số mũ
công khai hoặc số mũ bí mật nhỏ và tấn công cài đặt.

2.2.1. Tấn công cơ bản
2.2.1.1. Modul chung
Để tránh việc phân tích modul n= p*q khác nhau cho các người dùng khác nhau,
chúng ta lấy n chung cho tất cả. Cùng một n được sử dung cho tất cả người sử dụng. Trung
tâm xác thực có thể cung cấp cho người sử dụng i với một cặp ei, di và người sử dụng i có
một khóa công khai là (n,ei) và khóa riêng là (n,di).

2.2.1.2. Mù (Blinding)
Marvin chọn ngẫu nhiên một số r ∈ Z*n và đặt m’ = re m mod n. Sau đó anh ta nhờ
Bob ký lên m’. Bob có thể cung cấp chứ ký của mình là s’ lên m’. Nhưng từ cách tính s’=
(m’)d mod n, Marvin có thể đơn giản tính s = s’/r mod n để có được chữ ký của Bob là s
trên m.


13

se = (s’)e/re = (m’)ed/re = m’/re = m/(mod n)




14

2.2.3. Tấn công với số mũ công khai nhỏ
Người sử dụng hệ mật RSA muốn giảm thời gian mã hóa hoặc chứng thực chữ ký họ
thường sử dụng số mũ công khai e nhỏ, thông thường số mũ công khai chọn là 3 hoặc 216 +
1 = 65537. Khi giá trị 216 + 1 được chọn việc chứng thực chữ kí yêu cầu 17 phép nhân và nó
có thể lên đến 1000 nếu giá trị e ngẫu nhiên được sử dụng (e < ϕ (n)).
Và số mũ công khai nhỏ thì bản rõ m là rất ngắn, khi đó hàm RSA dễ dàng tính được
nghịch đảo. Không giống tấn công Wiener, tấn công với e nhỏ sẽ làm cho RSA bị sập hoàn
toàn. Sau đây là một vài minh họa về tấn công kiểu này.

2.2.3.1. Tấn công quảng bá của Hastad
Định lý 2 (Hastad)[2]: Cho n1, . .

,

nk là những số nguyên tố và tập nmin = mini(ni)

từng đôi một. Với gi ∈ ZNi[x], k là đa thức có giá trị nhỏ nhất là d. Tồn tại m < nmin thỏa
mãn: gi(m) = m mod ni với tất cả i = 1,…,k. Giả thiết rằng k > d, có thể tìm m khi cho
(ni,gi(x))ki =1.
Định lý chỉ ra rằng một hệ thống đồng biến với các đa thức nguyên tố hỗn hợp có
thể giải quyết hiệu quả, giả thiết rằng các hàm được cung cấp đầy đủ. Bằng cách cài đặt gi =
fiei – ci mod ni, chúng ta thấy rằng Marvin có thể tìm được M từ bản mã được cho với số
thành viên ít nhất là d, khi đó d là giá trị lơn nhất của eideg(fi) với i = 1,…,k.
Chúng ta lưu ý rằng để chống lại tấn công broadcast ở trên chúng ta sử dụng một cặp
số ngẫu nhiên thay vì gắn cứng vào một giá trị.


và Lipton [10] đã quan sát và thấy rằng có một lỗi nguy hiểm khi sử dụng phương pháp
CRT. Vấn đề là khi sinh chữ ký mà máy tính của Bob hoạt động không đều là nguyên nhân
gây nên lỗi tính toán. Hay nói cách khác trong khi copy giữa các thanh ghi, một bit của dòng
bít bị thất lạc. (Sự hoạt động không đều nguyên nhân có thể do xung đột điện từ hoặc cũng
có thể do sâu phần cứng, các lỗi này đã sớm được tìm thầy trong các phiên bản của chíp
Pentium). Được cung cấp một chữ ký lỗi, kẻ tấn công như Marvin có thể dẽ dàng phân tích
thành nhân tử modul N.

2.3. Hệ mật RSA với số mũ giải mã lớn.
Nếu làm theo các bước của thuật toán RSA :
-

Chọn 2 số nguyên tố lớn phân biệt p, q. Tính n = p*q và ϕ(n)= (p -1)*(q - 1).

-

Chọn e > 2 sao cho gcd(ϕ(n),e ) = 1 ; e thường được chọn nhỏ để quá trình mã

hóa nhanh.
-

d được xác định là duy nhất thỏa mãn e*d = 1 mod e(ϕ(n)).

Thì ta không hy vọng là có được số mũ giải mã d lớn. Do đó, trong [2], nhóm tác giả
Hernández Encinas, J.Munoz MasQué và A.Queiruga Dios đã đề xuất thuật toán để có được
số mũ giải mã d lớn, có kích thước gần bằng modunlus n bằng cách : số mũ công khai e


16



nghịch đảo nhân của e.

∈ Z*e |(r -1) ∈
∈ Z*e |(r(r -1)) ∈

Trong thuật toán này có đưa ra tập T(e) được định nghĩa T(e) = { r
Z*e}. T(e) ở đây chính là một cách định nghĩa khác của tập S(e) = { r
Z*e} điều này đã được chứng minh trong [1].


17

Sau đây là kết quả demo với Input là giá trị cần mã hóa; kết quả Ouput trên màn hình:

Hình 2.1 : Thuật toán có số mũ giải mã d lớn (e nhỏ)

Hình 2.2 : Thuật toán có số mũ giải mã d lớn (e lớn)

2.3.2. Đánh giá thuật toán số mũ giải mã d lớn
Đối với thuật toán RSA thông thường, xác suất cho việc chọn ngẫu nhiên d lớn
là khá cao, nhưng khi đó xác suất có giá trị e tương ứng lớn cũng khá cao. Trong thực tế,
người sử dụng luôn muốn chọn giá trị e nhỏ(một giá trị được xác định trước) ví dụ là 3 hoặc
216 + 1 để cải thiện nâng cao hiệu quả của quá trình mã hóa. Điều thú vị đối với thuật toán
trình bày ở trên là số mũ mã hóa e được chọn tùy ý nhưng ta luôn có giá trị d tương ứng là
lớn(có kích thước bằng kích thước modulus n ). Và khi giá trị e được chọn thì việc chọn p


18



3.1.3. Sơ đồ chữ ký RSA
Sơ đồ chữ ký RSA được cho bởi bộ năm
S = (P , A , K , S , V)
Trong đó :

P = A =Zn , với n =p.q là tích của hai số nguyên tố lớn p,q
K là tập các cặp khoá K =(K’,K''), với K’ = a và K'' = (n,b)
a và b là hai số thuộc Z* n thoả mãn a.b ≡ 1(modφ (n)).


20

3.1.4. Sơ đồ chữ ký Elgamal
Sơ đồ chữ ký ElGamal được đề xuất năm 1985, gần như đồng thời với sơ đồ hệ mật
mã ElGamal, cũng dựa trên độ khó của bài toán lôgarit rời rạc. Sơ đồ được thiết kế đặc biệt
cho mục đích ký trên các văn bản điện tử, được mô tả như một hệ:
S = (P , A , K , S , V)
Trong đó

P = Z*p , A = Z*p x Zp-1, với p là một số nguyên tố sao cho bài toán tính

lôgarit rời rạc trong Z*p là rất khó. Tập hợp K gồm các cặp khoá K=(K’,K''), với K’=a là một
số thuộc Z*p , K'' =(p, α , β), α là một phần tử nguyên thuỷ của Z*p , và β=αamodp. K’ là
khoá bí mật dùng để ký, và K'' là khoá công khai dùng để kiểm thử chữ ký.

3.1.5. Sơ đồ chữ ký DSS
Sơ đồ chữ ký DSS được cho bởi bộ năm
S = (P , A , K , S , V)
Trong đó P = Z*p , A = Z*q x Z*q

có độ dài tuỳ ý thì ta phải tìm cách rút gọn độ dài thông điệp. Nhưng bản thân thông điệp
không thể rút ngắn được, nên chỉ còn cách là tìm cho mỗi thông điệp một thông điệp thu
gọn có độ dài hạn chế và thay việc ký trên thông điệp, ta ký trên thông điệp thu gọn.

3.3.1.2. Định nghĩa hàm Hash
Hàm Hash là một hàm tính toán có hiệu quả khi ánh xạ các dòng nhị phân có độ dài
tuỳ ý thành các dòng nhị phân có độ dài cố định nào đó.

3.3.1.3. Tính chất của hàm băm
3.3.1.4. Thuật toán MD5
Thuật toán MD5 được Ron Rivest đưa ra vào năm 1991. Đầu vào của thuật toán là
các khối có độ dài 512 bit và đầu ra là một bản băm đại diện cho văn bản gốc có độ dài
128bit.

3.4. Xác thực.
Xác thực : Là một thủ tục nhằm kiểm tra các thông báo nhận được xem chúng có đến
từ một người gửi hợp lệ và có bị sửa đổi hay không. Xác thực cũng có thể kiểm tra trình tự
và tính đúng lúc. Chữ ký số là một kỹ thuật xác thực.

3.5. Mô tả hệ thống và cài đặt.
Các bước thực hiện của chương trình.

a. Phát sinh khóa:
Từ số mũ mã hóa e > = 3 là số nguyên dương lẻ bất kỳ ban đầu, chương trình sẽ thực
hiện tính toán để đưa ra cặp khóa công khai (e, n) và khóa bí mật (d, n). Sau đó khóa công
khai được tiết lộ ra công cộng, khóa bí mật được giữ lại.


22