Đỗ Thanh Bình

1

Tóm tắt luận văn thạc sĩ

Hệ mật RSA và ứng dụng lược đồ chữ
ký số trong xác thực thông tin : Luận
văn ThS. Công nghệ thông tin : 60 48
10 / Đỗ Thanh Bình ; Nghd. : PGS TS
Đoàn Văn Ban
Luận văn với đề tài “Hệ mật RSA và ứng dụng lược đồ chữ ký số
trong xác thực thông tin” nghiên cứu và ứng dụng hệ mật mã RSA trong
mã hóa dữ liệu.
Nội dung được chia thành các chương như sau:
Chương I: Tổng quan về các hệ mật mã
Giới thiệu mô hình một số hệ mật mã đang được ứng dụng như hệ
mã dịch vòng, mã thay thế, hoán vị, hệ mật mã RSA, v.v...
Chương II: Hệ mật mã khoá công khai RSA
Nghiên cứu các vấn đề liên quan đến hệ mật mã khoá công khai
RSA; phương pháp lập mã và giải mã; các đặc điểm và độ an toàn của
hệ mật; vấn đề quản lý khoá, phân phối khoá.
Chương III: Lược đồ chữ ký số RSA
Giới thiệu chữ ký số RSA, các ứng dụng của chữ ký số trong việc
xác thực dữ liệu; lược đồ chữ ký số; v.v...
Chương IV: Chương trình mã hoá dữ liệu
Ứng dụng cơ sở lý thuyết đã nghiên cứu để xây dựng một chương
trình mã hoá ứng dụng các kỹ thuật mã khoá bí mật, mã khoá công khai
và lược đồ chữ ký số.



KE

KD

Nhận tin
(Người nhận)

Thám mã
(Người thám mã)
Kênh an toàn
(truyền khoá)
Nguồn khoá

H1.1: Sơ đồ khối hệ thống truyền tin mật

Định nghĩa 1.1: Một hệ mật là một bộ gồm 5 tham số (R, M, K, E,
D) thoả mãn các điều kiện sau:
1) R là tập hữu hạn các bản rõ có thể
2) M là tập hữu hạn các bản mã có thể
3) K (không gian khoá) là tập hữu hạn các khoá có thể.
4) Đối với mỗi k∈ K có một quy tắc giải mã ek: P → C và một
quy tắc giải mã tương ứng dk ∈ D. Mỗi ek: R → M và dk: M
→ R là những hàm mã: dk(ek(x)) = x với mọi bản rõ x ∈ R
1.1.2 Một số hệ mật mã kinh điển
a) Mã dịch vòng
Hệ mật được xây dựng dựa trên số học modulo. Ký hiệu m là số chữ
cái của bộ chữ xây dựng bản rõ R.
Theo định nghĩa 1.1, cho R = M = K = Zn với 0 ≤ k ≤ (m - 1) và x, y
∈ Zm; Zm là không gian chữ cái, ta định nghĩa:


dạng file chứng chỉ số; cho phép chuyển đổi qua lại giữa các kiểu định
dạng. N goài ra, có thể phát triển thêm một lựa chọn kiểu chương trình là
cho phép cài đặt như một ứng dụng “thêm vào” (add-in), để tích hợp tính
năng mã hoá và xác thực thông tin/dữ liệu ngay từ bên trong một ứng
dụng cụ thể (chẳng hạn, ứng dụng thư điện tử Microsoft Outlook, v.v...).
Qua những hoạt động về mật mã trên thực tiễn cùng với những
nghiên cứu và kết quả của luận văn có thể khẳng định mật mã nói chung
và mật mã RSA nói riêng đóng vai trò rất quan trọng trong mọi lĩnh vực
xã hội. Việc nghiên cứu lý thuyết mật mã RSA và ứng dụng triển khai
kỹ thuật mã hoá này cho phù hợp với những bài toán cụ thể trong hoạt
động thực tiễn là một vấn đề hoàn toàn có thể thực hiện.


Đỗ Thanh Bình

22

Tóm tắt luận văn thạc sĩ

MÃ HOÁ

HASH value

SHA-1

RSA

GIẢI MÃ

Digital

Dữ liệu/
văn bản

CERT A

SHA-1

HASH value

Đỗ Thanh Bình

3

ek(x) = (x + k) mod m và dk(x) = (y - k) mod m
Các hệ mã mật hiện đại về thực chất là sự cải tiến của mã dịch vòng.
Đối với mã hoá một văn bản tiếng Anh thông thường là sự thiết lập
tương ứng giữa các chữ cái với các số theo modulo 26.
Tính bảo mật của hệ mã dịch vòng nói là không cao, thám mã có thể
dùng phương pháp vét cạn để tìm khoá để xác định bản rõ, điều này
càng rút ngắn nếu thực hiện phép tìm khoá theo cách vét cạn từ hai phía.
b) Mã thay thế
Mã thay thế về bản chất xem phép mã hoá và giải mã như là các
hoán vị của các ký tự.
Theo định nghĩa 1.1, cho R = M = Z26, k chứa mọi hoán vị có thể
của m ký hiệu. Với mỗi phép hoán vị π ∈ K, ta định nghĩa: eπ(x) = π(x)
và dπ(y) = π-1(y), trong đó π-1 là hoán vị ngược của π.
Với các văn bản tiếng Anh khi cần mã hoá, mỗi khoá của mã thay
thế là một trong 26! hoán vị. Do vậy, áp dụng phương pháp tìm khoá
bằng phương pháp vét cạn sẽ khó khăn hơn. Mã thay thế có thể dễ dàng
bị thám bằng phương pháp thống kê.


So sánh

Kết quả
xác thực

Tóm tắt luận văn thạc sĩ

)

y π− 1(1 ) ,....., y π− 1( m )
dπ (y1,… , ym) =
d) Các hệ mã dòng
Bản chất của mã này là tạo ra một dòng khoá z = z1 z2 z3… và dùng
nó để mã hoá một xâu bản rõ x = x1 x2 x3… theo quy tắc
y= y1 y2…=ez1(x1)ez2(x2)
Định nghĩa 1.2: Mã mật (mã hoá) dòng là một bộ (R, M, K, L, F, E,
D) thoả mãn các điều kiện sau:
1) R là tập hữu hạn các bản rõ có thể
2) M là tập hữu hạn các bản mã có thể
3) K là tập hữu hạn các khoá có thể (không gian khoá)


Đỗ Thanh Bình

4

Tóm tắt luận văn thạc sĩ

4) L là tập hữu hạn bộ chữ của dòng khoá

là cặp (b, n), gồm số mũ b và mod n. Với n = p.q, trong đó p và q là các
số nguyên tố; còn b được chọn là một số nguyên ngãu nhiên sao cho 1(b,
ϕ(n)) = 1, với ϕ(n) là giá trị hàm Euler của n, và: ϕ(n) = (p - 1)(q - 1)
Đặt R = M = Zn và định nghĩa:
K = {(n, p, q, a, b)} và ab ≡ 1(mod ϕ(n))

Đỗ Thanh Bình

21

Tóm tắt luận văn thạc sĩ

Quá trình giải mã:
7) Giải mã khoá mật: sử dụng khoá riêng của người nhận
(Private Key B) để giải mã khoá mật.
8) Giải mã dữ liệu: sử dụng khoá mật để giải mã toàn bộ dữ
liệu hoặc văn bản điện tử, chữ ký và chứng chỉ số.
9) Tính giá trị “băm” của văn bản: toàn bộ dữ liệu hoặc văn
bản điện tử gốc được đưa qua thuật toán băm 1 chiều để tạo
ra một mã nhận dạng có tính duy nhất (Hash Value)
10) Kiểm tra tính hợp lệ của văn bản: sử dụng khoá công khai
của người gửi (Public Key A) để kiểm tra chữ ký số trên giá
trị “băm” của văn bản để kết luận về tính hợp lệ của dữ liệu
hoặc văn bản:
1. N ếu kết quả kiểm tra đúng, chứng tỏ thông tin là do
người gửi gửi (khoá giải mã cùng cặp khoá với khoá mã
hoá); và nội dung thông tin còn nguyên gốc sau khi ký.
2. N ếu kết quả kiểm tra sai thì chứng tỏ thông tin không
phải do người gửi gửi (khoá giải mã không cùng cặp
khoá với khoá mã hoá); và nội dung thông tin không

(Digital Signature)
3) ChuNn bị dữ liệu mã hoá: Gắn chữ ký số này và chứng chỉ
số của người ký (Certificate A) với dữ liệu hoặc văn bản
điện tử.
4) Mã hoá dữ liệu: toàn bộ dữ liệu hoặc văn bản điện tử, chữ
ký số và chứng chỉ số được mã hoá bằng thuật toán AES bởi
một khoá mã hoá/giải mã (khoá mật) sinh ra ngẫu nhiên cho
mỗi phiên giao dịch.
5) Mã hoá khoá mật: khoá mã hoá/giải mã sau đó được mã hoá
bằng khoá công khai của người nhận (Public Key B). Khoá
công khai này được lấy từ chứng chỉ số của người nhận
(Certificate B)
Quá trình truyền thông tin:
6) Dữ liệu và khoá mật đã được mã hoá được gửi đến người
nhận qua các kênh truyền thông công cộng.

Đỗ Thanh Bình

5

Tóm tắt luận văn thạc sĩ

Với k = (n, p, q, a, b) ta xác định được :
ek(x) = xb mod n ; dk(y) = ya mod n
b) Hệ mật RABI
Định nghĩa 1.3:
Giả sử n là tích của hai số nguyên tố phân biệt p và q; p.q ≡ 3 (mod
4);
Giả sử R = M = Zn và xác định:
K = {(n, p, q, B): 0 ≤ B ≤ n - 1}

*
p

Z *p

là phần tử nguyên

*
p

× Z . Từ đây ta định nghĩa:

K = {(p, α, a, β): β ≡ αa (mod p)}
Các giá trị p, α, β được công khai, còn a giữ bí mật.
Với K = (p, α, a, β) và một số ngẫu nhiên bí mật k ∈ Zp, ta xác định:
ek(x, k) = (y1, y2),
trong đó : y1 = αk mod p ; y2 = x βk mod p
với y1, y2 ∈

Z *p

ta xác định d k ( x , k ) = y 2 ( y 1a

)

−1

mod p

d) Hệ mật xếp balô Merkle – Hellman

e k ( x 1 ,..., x n ) =

n

∑

xiti

i =1

với 0 ≤ y ≤ n(p - 1) ta xác định: Z = a-1 y mod p
và giải mã tập con (S1, .., Sn, Z) ta sẽ nhận được: dk(y) = (x1,..., xn)
e) Hê mật McEliece
Hệ mật McEliece sử dụng nguyên lý tương tự hệ mật Merkle –
Hellman. Phép giải mã là một trường hợp đặc biệt của bài toán N P đầy
đủ nhưng nó được nguỵ trang giống như trường hợp tổng quát của bài
toán. Trong hệ mật này bài toán N P được áp dụng là bài toán giải mã
cho một mã sửa sai (nhị phân) tuyến tính nói chung.
Hệ mật McEliece dùng mã Goppa có các nhược điểm: dung lượng
khoá lớn (512 K); mã hoá và giải mã phức tạp; chưa có thuật toán tìm
mã hữu hiệu.

Đỗ Thanh Bình

19

Tóm tắt luận văn thạc sĩ

iv) Dùng thuật toán Euclidean mở rộng để tính số nguyên d,
1

Tóm tắt luận văn thạc sĩ

Mỗi cá thể tạo một khoá riêng dùng để ký thông điệp và một khoá
công khai tương ứng để các cá thể khác dùng trong xác minh chữ ký.
Mỗi cá thể A chọn một khoá k = (k’; k”) ∈ K, Sigk’ là thuật
toán ký với khoá k.
R là một hàm sao cho R(M) = MR và có nghịch đảo là R-1
Thuật toán Ver k” là một ánh xạ từ Ms đến MR sao cho:
Verk”Sigk’ là ánh xạ đồng nhất trên MR, ∀k ∈ K. Verk” gọi
là thuật toán chứng thực được xây dựng sao cho có thể tính
toán khi không biết khoá riêng của người ký thông điệp.
Cặp khoá k = (k’; k”), trong đó khoá công khai của A là k”;
khoá riêng của A là k’.
Thuật toán sinh chữ ký:
Cá thể A ký một thông điệp P ∈ M với chữ ký s. Một cá thể B bất
kỳ có thể các minh chữ ký và phục hồi thông điệp P từ chữ ký đó. Để
sinh chữ ký, cá thể A thực hiện:
i) Chọn một khoá k = (k’; k”) ∈ K
ii) Tính m = R(P) và s = Sigk’(m) (R là nghịch đảo của nó là R-1
là các hàm được công khai)
iii) Chữ ký của A cho thông điệp P là s, và s được gửi đến B
Thuật toán chứng thực chữ ký
Để xác thực chữ ký, B làm như sau:
i) Xác thực đúng khoá công khai của A là k”
ii) Tính m = Verk”(s)
iii) Xác minh rằng m ∈ MR (nếu m ∉ MR thì từ chối chữ ký)
iv) Phục hồi thông điệp P từ m bằng cách tính R-1(m)
3.5 Lược đồ chữ ký số RSA
3.5.1 Thuật toán sinh khoá cho lược đồ chữ ký số RSA

ii) ϕ(n) = (p - 1)(q - 1)
iii) Chọn một số nguyên e đủ lớn nguyên tố cùng ϕ(n), có
nghĩa: 1< e
Giải mã

Bên nhận B

Hình 2.1: Quá trình mã hóa khóa công khai RSA

Quá trình gửi và nhận thông điệp (bản tin) được thực hiện như sau:
i) Mỗi thành viên sinh một cặp khoá (n; e) và (n; d).
ii) Công khai khoá (n; e); giữ bí mật hoá (n; d).
iii) A gửi thông điệp cho B thì A mã hoá thông điệp bằng khoá
công khai (n; eb) của B.
iv) B giải mã thông điệp bằng khoá riêng (n; db). Không một
người nào khác có thể giải mã thông điệp ngoài B, vì chỉ có
B mới biết khoá riêng của mình.
2.3 Độ an toàn của hệ mật RSA
Độ an toàn của hệ mật RSA thể hiện qua hai yếu tố:

Đỗ Thanh Bình

17

Tóm tắt luận văn thạc sĩ

Thuật toán sinh khoá:
Mỗi cá thể A chọn một khoá k = (k’; k”) ∈ K, Sigk’ là thuật
toán ký với khoá k
Thuật toán Verk” tương ứng là một ánh xạ từ MhxMs đến tập
hợp {True, False} sao cho:
True , nếu y = sigk’(x)
Verk’’(x ;y) =


16

Tóm tắt luận văn thạc sĩ

Trong đó:
Ks gọi là mầm khoá hay còn gọi là khoá khởi thảo được
chọn theo phương pháp ngẫu nhiên.
Hai thuật toán F, G dùng để tính toán các khoá. A dùng hai
thuật toán F và G cùng với mầm khoá ks để tạo ra hai khoá:
khoá giải mã kd là khoá riêng được giữ lại sử dụng riêng cho
mình và khoá ke công khai thông báo cho mọi người.
P là thông điệp gửi đi, S là thông điệp sau khi ký.
E k d : Thuật toán mã hoá với khoá kd.
Dke : Thuật toán giải mã với khoá ke.

3.4.2 Định nghĩa lược đồ chữ ký số
Một lược đồ chữ ký số là một bộ (M, Ms, K, S, V) gồm:
M là tập hợp hữu hạn các văn bản có thể
Ms là tập hợp hữu hạn các chữ ký có thể
K là tập hợp hữu hạn các khoá
S là tập hợp các thuật toán ký
V là tập hợp các thuật toán chứng thực chữ ký.
Mỗi k ∈ K là một cặp (k’; k”) trong đó k’ là khoá bí mật dùng để ký,
k” là khoá công khai dùng để kiểm thử chữ ký.
Với mỗi k = (k’; k”) ∈ K. Có một thuật toán ký Sigk’: M → Ms (Sigk’
∈ S) và một thuật toán kiểm thử Verk”: M x Ms → {True, False}(Verk” ∈
V). Thoả mãn điều kiện sau đây đối với mọi x∈M, y∈Ms:
True , nếu y = sigk’(x)
Verk’’(x ;y) =

a) Phương pháp khai báo công khai
Bất kỳ thành viên nào cũng có thể thông báo khoá công khai của
mình để cho các thành viên khác được biết.
Giải pháp này có nhược điểm là bất kỳ ai cũng có thể giả mạo một
khoá công khai.
b) Phương pháp sử dụng thư mục công khai
Việc duy trì và tổ chức một thư mục công khai thuộc về một tổ chức
được tin cậy nào đó. Một lược đồ như vậy bao gồm các yếu tố sau:
Tổ chức có nhiệm vụ duy trì thư mục, mỗi thành viên có
một entry (định danh, khoá) trong thư mục.
Mỗi thành viên đăng ký một khoá công khai với tổ chức
quản lý thư mục.
Mỗi thành viên có thể thay thế một khoá công khai bất cứ
lúc nào khi cảm thấy khoá riêng bị lộ
Cơ quan quản lý công bố toàn bộ thư mục và có nhiệm vụ
cập nhật thư mục một cách định kỳ.
Mọi thành viên đều có thể truy nhập vào thư mục bất cứ lúc
nào, vì thế việc truyền thông xác thực an toàn (từ cơ quan
quản lý đến các thành viên) phải mang tính bắt buộc.
c) Trung tâm quản lý khoá công khai


Đỗ Thanh Bình

10

Tóm tắt luận văn thạc sĩ

Một cơ quan trung tâm duy trì một thư mục khoá công khai. Mỗi
thành viên đều biết khoá công khai của trung tâm quản lý khoá công

báo khoá công khai của mình cho các thành viên khác thông qua chứng
chỉ.
Đặc trưng quan trọng của chứng chỉ là: “Các chứng chỉ có thể được
phát hành mà không cần phải bảo vệ thông qua các dịch vụ an toàn

Đỗ Thanh Bình

15

Tóm tắt luận văn thạc sĩ

thay đổi (dù chỉ là 1 bit) thì kết quả của dấu vết thông điệp cũng sẽ thay
đổi.
N gười ta thường sử dụng sự hỗ trợ của các hàm băm mật mã trong
quá trình số hoá của các lược đồ ký. Hàm băm mật mã phải có tính chất
sau:
Là hàm một chiều
Không tìm được xung đột: tức là rất khó để tìm hai văn bản
P và P’ có cùng mã băm.
Một dấu vết thông điệp phải có hai thuộc tính thiết yếu sau:
N ếu một bit hoặc một vài bit của dữ liệu bị thay đổi thì dấu
vết thông điệp cũng bị thay đổi.
Một ai đó có muốn giả mạo thì cũng không thể đưa ra một
thông điệp giả cùng với một dấu vết thông điệp tương ứng
giống như bản gốc trong thời gian chấp nhận được.
3.4 Lược đồ chữ ký số dùng mật mã khoá công khai
3.4.1 Hoạt động của chữ ký số
N ếu A gửi cho B một bản tin được mã hoá bằng khoá công khai của
B thì B có thể giải mã bằng khoá riêng của mình để đọc bản tin đó mà
những người khác không làm được. N gược lại, B có thể “ký” vào một

Đỗ Thanh Bình

14

Tóm tắt luận văn thạc sĩ

3.3

Xác thực thông điệp
Xác thực thông điệp là một thủ tục nhằm kiểm tra các thông điệp
nhận được, xem chúng có đến từ một nguồn hợp lệ và có bị sửa đổi hay
không. Xác thực thông điệp cũng có thể kiểm tra trình tự và tính đúng
lúc. Có nhiều kỹ thuật để xác thực thông điệp: N gay trong hệ mã bí mật
người ta cũng đã đề cập đến việc xác thực thông điệp, chữ ký số cũng là
một kỹ thuật xác thực, nó cũng bao gồm nhiều biện pháp để chống lại
việc chối bỏ đã gửi hay nhận thông điệp.
3.3.1 Mã hoá thông điệp
i) Trước tiên A sử dụng khoá riêng của mình mã hoá (ký)
thông điệp P để có s = Ekda (P)
ii) Tiếp tục dùng khoá công khai của B (nhằm đảm bảo tính bí
mật) mã hoá chữ ký s để được bản mã
C = E k e (s ) = E k e E k e (P ) , C được gửi đến B.
b

b

(

b


Lợi ích của chứng chỉ khoá công khai là một người sử dụng có thể
có được một số lượng lớn các khoá công khai của các thành viên khác
một cách tin cậy chỉ cần thông qua khoá công khai CA.
2.4.2 Sử dụng mã hoá khoá công khai để phân phối khoá mật
Lược đồ Merkle: thủ tục A trao đổi thông tin mật với B:
i) A tạo ra một cặp khoá (ea, da) và truyền cho B khoá công
khai ea và tên của A (IDA).
ii) B tạo ra một khoá bí mật Ks và gửi cho A: E e a (K

(

s

).

( )) = K

iii) A tính toán để biết khoá bí mật Ks: D d a E e a K

S

iv) A huỷ bỏ ea, da và B huỷ bỏ ea.
Bây giờ A và B có thể trao đổi với nhau bằng khoá phiên Ks. Sau khi
trao đổi xong cả A và B cùng huỷ bỏ KS, như vậy theo cách này thì việc
đảm bảo bí mật là rất tốt vì trước và sau khi liên lạc không có khoá nào
tồn tại.
2.5 Các tấn công đối với hệ mật mã RSA
2.5.1 Tấn công trong quá trình tạo khóa
Việc tìm ra 2 số nguyên tố đủ lớn p và q thường được thực hiện
bằng cách thử xác suất các số ngẫu nhiên có độ lớn phù hợp và p và q

bằng khóa công khai của Alice và gửi cho Alice. Về nguyên tắc, cả Bob
và Alice đều không phát hiện ra sự can thiệp của người thứ ba. Các
phương pháp chống lại dạng tấn công này thường dựa trên các chứng
thực khóa công khai (digital certificate) hoặc các thành phần của hạ tầng
khóa công khai (public key infrastructure - PKI).
2.5.4 Tấn công dựa trên thời gian
N ếu kẻ tấn công nắm đủ thông tin về phần cứng thực hiện mã hóa và
xác định được thời gian giải mã đối với một số bản mã lựa chọn thì có
thể nhanh chóng tìm ra khóa d. Dạng tấn công này có thể áp dụng đối
với hệ thống chữ ký điện tử sử dụng RSA.
Một dạng tấn công thực tế: phân tích thừa số RSA dùng mạng máy
tính (Máy chủ web dùng SSL). Tấn công đã khai thác thông tin rò rỉ của
việc tối ưu hóa định lý số dư Trung quốc mà nhiều ứng dụng đã thực
hiện.
Để chống lại tấn công dựa trên thời gian là đảm bảo quá trình giải
mã luôn diễn ra trong thời gian không đổi bất kể văn bản mã.
2.5.5 Tấn công lựa chọn thích nghi bản mã
Dạng tấn công lựa chọn thích nghi bản mã (adaptive chosen
ciphertext attack) có thể thực hiện trên thực tế đối với một văn bản mã
hóa bằng RSA. Văn bản này được mã hóa dựa trên tiêu chuNn PKCS #1
v1, một tiêu chuNn chuyển đổi bản rõ có khả năng kiểm tra tính hợp lệ
của văn bản sau khi giải mã. Do những khiếm khuyết của PKCS #1,
Bleichenbacher có thể thực hiện một tấn công lên bản RSA dùng cho
giao thức SSL (tìm được khóa phiên). Do phát hiện này, các mô hình
chuyển đổi an toàn hơn như chuyển đổi mã hóa bất đối xứng tối ưu
(Optimal Asymmetric Encryption Padding) được khuyến cáo sử dụng.
Đồng thời phòng nghiên cứu của RSA cũng đưa ra phiên bản mới của
PKCS #1 có khả năng chống lại dạng tấn công nói trên.

Đỗ Thanh Bình

Các ứng dụng thương mại: thanh toán điện tử, trao đổi thông tin điện
tử, điền vào các bản tin thuế và các tài liệu pháp quy khác, bán hàng trực
tuyến và các giao dịch dùng card.
Bầu cử số: người dân xác minh rõ ràng rằng phiếu bầu thuộc về họ,
tránh việc bầu quá.
Phân phối phần mềm: một chữ ký số được áp dụng cho phần mềm
sau khi nó được hoàn thành và được chấp thuận để phân phát. Trước khi
cài đặt phần mềm trên một máy tính, chữ ký cần được xác minh để chắc
chắn rằng không có sự thay đổi nào ngoài thNm quyền (ví dụ như sự
thêm vào của một viruts). Chữ ký số cũng được xác minh một cách định
kỳ để chắc chắn sự toàn vẹn của phần mềm.