Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000

HỆ THỐNG MÃ VỚI KHÓA CÔNG KHAI
PUBLIC KEY CRYPTOSYSTEMS

1976, Diffie & Hellman.
Khái niệm
Các hệ thống mã đã nghiên cứu trong chương trước có thể gọi là các hệ mã khóa đối xứng
(Symmtric Key Cryptosystems) do hai bên gửi và nhận tin đều thống nhất chung một khoá
bí mật. Các hệ này còn có các tên gọi khác là:
Hệ mã với khóa sở hữu riêng (Private Key Cryptosystems)
Hệ mã với khóa bí mật (Secret Key Cryptosystems)
Hệ mã truyền thống (Conventional Cryptosystems)
tuỳ theo các ngữ cảnh khác nhau.

K
AC

K
BC

K
AB
A
C
B
K
CD

1
Dịch vụ non-repudiation cho phép trong mọi trường hợp của một quá trình giao dịch giữa hai bên Alice (A
và B(Bob), mỗi bên đều có bằng chứng để chứng gian những trường hợp phía bên kia chối bỏ một giao dịch
nào đó, chẳng hạn như Alice có thể cãi lấy cớ là một kẻ nào khác mạo nhận là mình để tiến hành giao dịch x
nào đó với Bob từ trước.
Chương III - 1 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000

Alice và Bob, được gọi là trusted authorty, tức là một người có thẩm quyền mà cả Alice và
Bob đều tin tưởng là trung thực. Người này sẽ làm chứng và trọng tài trong trường hợp xảy
ra tranh cãi giữa hai bên trung thực. Người này sẽ làm chứng và trọng tài trong trường hợp
xảy ra tranh cãi giữa hai bên Alice và Bob. Tuy nhiên theo sơ đồ thì công việc của người
trọng tài này sẽ rất nặng vì phải tham gia vào tất cả các giao dịch của các bên, và sớm
muộn cũng sẽ trở thành điểm quá tải về giao thông truyền tin cũng như tốc độ xử lý -
bottleneck).

Diffie & Hellman trong các công trình của mình (1975-76) đã đề xuất những tư tưởng về
một loại hệ mã với nguyên tắc mới, trong đó hệ mã được gắn với một user (người sử dụng)
nhất định chứ không phải là gắn với một cuộc truyền tin giữa một cặp user.

Trong hệ thống mới này, mỗi user có hai khoá, một được gọi là khoá bí mật (secret key
hay private key) và một được gọi là khoá công khai (public key). Khoá thứ nhất chỉ mình
user biết và giữ bí mật, còn khoá thứ hai thì anh ta có thể tự do phổ biến công khai. Khoá
thứ nhất thường đi liền với thuật toán giải mã, còn khoá thứ hai thường đi liền với thuật
toán sinh mã, tuy nhiên điều đó không phải là bắt buộc. Ta hãy ký hiệu chúng là z (khóa
riêng) và Z (khóa công khai)

Hoạt động của chúng là đối xứng
X = D(z, E(Z, X)) (1)

, p
n
ta có thể dễ dàng tính được N = p
1
* p
2
* * p
n
, tuy
nhiên khi biết N, việc tìm các thừa số nguyên tố của nó là khó khăn hơn rất nhiều, đặc biệt
là khi N lớn và các thừa số nguyên tố của nó cũng lớn.
Chương III - 2 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000

Chúng ta cần một hàm one-way đặc biệt mà có trạng bị một trap door (cửa bẫy), sao cho
nếu biết trap- door này thì việc tính X khi biết f(X)( tức là đi tìm nghịch đào của f) là dễ
dàng, còn ngược lại thì vẫn khó như thường.
Một hàm one-way có trap door như thế có thể dùng để tạo ra một hệ mã PKC. Lấy E
z
(hàm
sinh mã) là hàm one- way có trap-door. Trap- door chính khoá mật, mà nếu biết nó thì có
thể dễ dàng tính được cái nghịch đảo của E
z
tức là biết D
z
, còn nếu không biét thì rất khó
tính được.
Sau đây chúng ta sẽ khảo sát hai ví dụ về việc xây dựng trap-door cho một hàm one-way.
Ví dụ đầu tiên là một cố gắng nhưng thất bại, hệ Trapdoor Knapsack. Ví dụ thứ hai là một

1
, a
2
, , a
n
) - được gọi là vector mang (cargo vector)
Với một khối tin X = (X
1
,X
2
,X
3
, X
n
), ta thực hiện phép mã hoá như sau:
T= ∑ a
i
X
i
(*) i=1,n
Việc giải mã là: Cho mã T, vector mang a, tìm các X
i
sao cho thoả mãn (*).

Trong sơ đồ này thể hiện một hàm one-way với việc sinh mã rất dễ dàng nhưng việc giải
mã là rất khó. Bây giờ ta phải tìm cách xây dựng một trapdoor để việc giải mã có thể làm
được dễ dàng.

1
=T
0
-X
4
=6 Î (X
1
X
2
X
3
1)
X
3
=1 T
2
=T
1
-X
3
=2 Î (X
1
X
2
1 1)
X
2
=1 T
3
=T

Mặc dù ta đã thấy vector siêu tăng cho phép giải mã dễ dàng nhưng tất nhiên nó chưa thể
đem áp dụng thẳng tuột ngay vì phải làm sao để cho chỉ có người chủ mới biết được nó còn
kẻ thù thì không, tức là người chủ phải tìm cách chủ động “nguỵ trang” vector siêu tăng để
chỉ có anh ta mới biết còn người ngoài không thể lần ra được.

Sơ đồ sau đây sẽ trình bày một cơ chế nguỵ trang như vậy.

Tạo khoá:
1. Alice chọn một vector siêu tăng:
a’ = (a
1
’,a
2
’, ,a
n
’)
a’ được giữ bí mật tức là một thành phần của khoá bí mật
2. Sau đó chọn một số nguyên m > ∑ a
i
’, gọi là mo-dul đồng dư và một số nguyên ngẫu
nhiên ω, gọi là nhân tử, sao cho nguyên tố cùng nhau với m.
Khoá công khai của Alice sẽ là vector a là tích của a’ với nhân tử ω:
a = (a
1
,a
2
, ,a
n
)
a

i
X
i
ω
-1
= ∑ a
i
’ωX
i
ω
-1
= ∑ (a
i
’ωω
-1
)X
i
ω
-1
= ∑ a
i
’X
i
= a’.X
Chương III - 4 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000Như vậy chúng ta đã xem xét xong sơ đồ cụ thể của Merkle-Hellman về một hệ PKC dựa

1
, n
2
) = a.n
1
+ b.n
2
.
Từ đó suy ra nếu ta đã biết (n
1
,n
2
)=1 thì thuật toán này sẽ cho ta tìm được a, b thoả mãn
a.n
1
+b.n
2
=1, tức là n
1
chính là nghịch đảo của a theo modulo n
2
(tức là m)

Sau đây là sơ đồ thuật toán và ví dụ bằng số

Start
n1, n2
n1>0
Initialization:
a=1, b1=0
Chương III - 5 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000
Ví dụ tính bằng số: Tìm ngịch đảo của 11 theo modulo 39
Đặt n
1
=39, n
2
=11 ta có bảng tính minh họa các bước như sau:

n
1
n
2
r q a
1

RSA Public key cryptosystems
RSA là hệ PK phổ biến và cũng đa năng nhất trong thực tế, phát sinh bởi Rivest, Shamir
& Adleman. Nó là chuẩn bất thành văn đối với PKC, cung cấp tính secretcy, authentication
và digital signature.

RSA dựa trên tính khó của bài toán phân tích các số lớn ra thừa số nguyên tố: Biết một số
nguyên tố nhân chúng với nhau để thu được một hợp số là dễ còn biết hợp số, phân tích nó
ra thừa số nguyên tố là khó.
Chương III - 6 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000

Ý tưởng(Motivation)
ý tưởng của các nhà phát minh là gắn các thuật toán sinh mã và mã hoá vưói phép toán lấy
luỹ thừa trên trường Z
n
= {0,1,2, n-1}. Chẳng hạn, việc sinh mã cho tin X sẽ được thực
hiện qua:

Y =
nX
e
±
(Ký hiệu a = b + n nghĩa là a = b + k. n mà a ∈ Z
n
còn k = 1,2,3, , ví dụ 7 = 3
3
+ 10) còn
việc giải mã:
X =

(n)
)
d
.X = 1.X =X

φ(n) có thể tính được khi đã biết công thức phân tích thừa số nguyên tố của n, cụ thể là
nếu đã biết n = p.q (p.q là số nguyên tố) thì φ(n) = (p-1) (q=1).
Nói cách khác nếu như cho trước một số e thì nếu đã biết công thức phân tích thừa số
nguyên tố của n ta có thể dễ dàng tìm được d sao cho d = e
-1
(mod φ(n)) hay là X
ed
= X
(mod n), còn nếu không biết thì rất khó.
Vừa rồi là phần trình bày dẫn dắt về cội nguồn của thuật toán, sau đây là thuật toán cụ thể.
Thuật toán RSA

Các tham số
1. Chọn hai số nguyên tố lớn p và q. Tính n = p x q và m = φ(n) = (p = 1) x (q-1).
2. Chọn e, 1≤ e ≤ m -1, sao cho gcd (e, m) = 1.
3. Tìm d sao cho e x d = 1 (mod m), tức là tính d = e
-1
(mod m), giải theo thuật toán gcd
mở rộng đã trình bày ở phần trước.
Khóa công khai (Public key) là (e, n)
Khoá dùng riêng (Private key) là d, p, q)
Giả sử X là một khối tin gốc (plaintext), Y là một khối mã tương ứng của X, và là
các thành phần công khai và riêng của khoá của Alice
),(
AA

< = 142. Do đó u = 7. Mỗi đoạn như vậy sẽ là một con số nằm trong khoản 0 - 127 và ta có
thể tính mã Y theo công thức:
120±=
e
XY

Chẳng hạn với X = (0000010) =2, ta có
14312)(
37
±== XXE
Z
Î Y= (00001100)
Giải mã như sau:
143212)(
13
±=== YDX
z

Để tiện cho việ giao dịch trên mạng có sử dụng truyền tin mật, người ta có thể thành lập
các Public Directory (thư mục khoá công khai), lưu trữ các khoá công khai của các user.
Thư mục này được đặt tại một điểm công cộng trên mạng sao cho ai cũng có thể truy nhập
tới được để lấy khoá công khai của người cần liên lạc.

User (n,e)
Alice (85,23)
Bob (117,5)
Hua (4757,11)
. .
. .
. .

tạo ra được thông báo đó ngoài Alice vì chỉ có duy nhất Alice biết z
A
.
Chú ý 2: Alice có thể ký vào giá trị băm (hast) của X thay vì ký thẳng lên X. Khi đó toàn
bộ mã mà Alice sẽ chuyển cho Bob là . H() là một hàm băm công khai.
)))((,( XHDX
A
z
Phương pháp này là hiệu quả hơn do tiết kiệm (hàm băm luôn cho ra một xâu độ dài cố
định và thông thường nhỏ hơn xâu đầu vào nhiều lần.
c. Kết hợp tính mật và tin cậy.
Chúng ta có thể làm như sau để kết hợp cả hai khả năng a và b như trên.
A gửi cho B
))(( XDEY
AB
zZ
=

B phục hồi x như sau:
))))(((())(( XDEDEYDEX
ABBABA
zZzZzZ
=
=
Để có bằng chứng nhằm đối phó với việc Alice có thể sau này phủ nhận đã gửi thông báo
(non -repudiation) thì Bob phải lưu giữ
)(XD
A
z
Một số vấn đề xung quanh thuật toán RSA

Từ đó rút ra, nếu tăng n lên thêm 50 bit (quãng 15 chữ số thập phân) thì thời gian làm phân
tích ra thừa số nguyên tố tăng lên 10 lần.

Chương III - 9 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000

Người ta đã ước lượng thấy, với n=200, L(n) ≈ 55 ngàn năm. Đối với khả năng thực hiện
bằng xử lý song song, một trong các kết quả tốt nhất về phân tích TSNT với số lớn cho biết
đã phân tích một số có 129 chữ số, phân bố tính toán trên toàn mạng Internet và mất trọn 3
tháng.
Ngày nay, với những ứng dụng có độ đòi hỏi an toàn đặc biệt cao người ta sử dụng đại lượng
modulo của RSA này lên đến 1024 bit và thậm chí 2048 bit.
Vấn đề đi tìm số nguyên tố lớn:
Một thuật toán để tạo ra tất cả các số nguyên tố là không tồn tại, tuy nhiên có những thuật
toán khá hiệu quả để kiểm tra xem một số cho trước có phải là nguyên tố hay không (bài
toán kiểm tra tính nguyên tố). Qua đó việc tìm các số nguyên tố lón cho RSA là một vòng
lặp gồm các bước:
1. Chọn một số ngẫu nhiên p nằm trong một khoảng có độ lớn yêu cầu (tính theo bit)
2. Kiểm tra tính nguyên tố của p, nếu là nguyên tố thì dừng lại, nếu không thì quay lại
bước 1.

Những thuật toán tất định để kiểm tra tính nguyên tố không phải là tầm thường và đòi hỏi
được thực hiện trên máy tính rất khoẻ. Tuy nhiên người ta cũng còn sử dụng các thuật toán
‘đoán’ xem một số có phải nguyên tố không. Các thuật toán đoán này có thể đưa ra lời giải
có tính chính xác cao, phụ thuộc vào thời gian bỏ ra để chạy nó.

Ở đây ta hay xét ví dụ một thuật toán ‘đoán’, dựa trên phương pháp sau đây của Lehman.
P/p Lehman: Giả sử n là một số lẻ, với mỗi số nguyên a ta hãy ký hiệu:
na

=1
Tức là G= {1,6}.
Định lý Lehman: Nếu n là một số lẻ thì G={1,n-1} khi và chỉ khi n là số nguyên tố.
Theo định lý này ta có phép thử sau:

1. Chọn ngẫu nhiên một số a ∈Z
n
*

2. If (gcd(a,n) >1) return (“là hợp số”) else
)1||1(
2
1
2
1
−==
−− nn
aaIf3. If ( return (“ có thể là nguyên tố”)
else return (“là hợp số”)

Nếu như thực hiện phép thử này 100 lần và đều thu được câu trả lời “có thể là nguyên tố”
thì xác xuất n không phải là số nguyên tố (‘đoán nhầm’) sẽ chỉ là 2
-100
.
Bằng phương pháp ‘đoán’ này ta có thể loại bỏ nhanh chóng các hợp số và chỉ thực hiện
phép kiểm tra tất định cuối cùng với các số trả lời dương tính ở bước ‘đoán’.
Chương III - 10 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000


i
X
2
11
222
224
2

−−
×
=
×=
×=
kkk
X
X
X
XXX
XXX

3.
Do công thức nên ta tính được X
α
± n bằng cách đem nhân với nhau các giá trị ± n
đã tính ở bước 2 nếu như α
i
tương ứng của nó là 1:
i
X
2

+2
3
+2
0
.
Y=2
64+8+1
= 2
64
× 2
8
× 2
1

Điểm yếu của giải thuật RSA
Trong hệ RSA, không phải tất cả các thông tin đều được che giấu tốt, tức là mọi khoá đều
tốt và đều làm TIN thay đổi hoàn toàn.
Ví dụ:
n = 35 = 5 x 7, m = 4 x 6
e = 5 (GCD (5,24) = 1)
X = 8
Y = X
e
± 35 = 8 = X!
Đối với bất kỳ khoá nào tồn tại ít nhất 9 TIN bị ‘phơi mặt’, tuy nhiên đối với n ≥ 200 điều
đó không còn quan trọng. Mặc dù vậy phải chú ý là nếu e không được chọn cẩn thẩn thì có
thể gần đến 50% tin bị lộ.
Ví dụ:
Với n = 35, e = 17
{1, 6, 7, 8, 13, 14, 15, 20, 21, 27, 28, 29, 34} không che được

z
(X). Để tìm d nó phải giải phương trình:
X = Y
d
±n
Hay là tính d = log
Y
X
2.
Đi tìm TIN:
Kẻ thù biết Y và e, để tìm được TIN X nó phải tìm cách tính căn thức bậc e theo đồng dư,
để giải phương trình
Y=X
e

Một số dạng tấn công có điều kiện quan trọng: đối với một số hệ cài đặt rơi vào một số
điều kiện đặc biệt có thể bị mất an toàn.
1.
Common modulus attack: Khi một nhóm user sử dụng các khoá công khai Z=(e,n)
khác nhau ở thành phần e nhưng giống nhau ở modul đồng dư n.
Khi đó, nếu kẻ thù tóm được hai đoạn MÃ:
+ của cùng một TIN mà được mã hoá bởi khoá PK khác nhau (từ hai user khác nhau)
+ hai thành phần e tương ứng là nguyên tố cùng nhau
thì nó sẽ có cách để giải được TIN. Cụ thể là nếu kẻ thù biết e
1
,e
2
,N,Y
1
,Y

= X
e1×a
×X
e2×b
=X
e1×a+e2×b
=X
Tóm lại nên tránh sử dụng chung modul đồng dư (common modulus) giữa những user
thuộc về một nhóm làm việc nào đó.
Chương III - 12 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000

2.
Low exponent attack: Tấn công này xảy ra với điều kiện là giá trị e đã được chọn nhỏ
(e mà nhỏ thì thuật toán mã hoá trong truyền tin mật cũng như kiểm định chữ ký sẽ
nhan hơn).
Nếu kẻ thù có thể tìm được e(e+1)/2 MÃ mà được mã hoá từ những TIN phụ thuộc tuyến
tính thì hệ thống sẽ bị nguy hiểm. Tuy nhiên nếu các TIN này là không có quan hệ với
nhau thì không sao. Vì vậy nên ghép thêm vào các TIN những xâu nhị phân ngẫu nhiên để
đảm bảo cho chúng là không bị phụ thuộc.
3.
Low decryption attack:
Nếu thành phần khóa mật d mà nhỏ hơn N/4 và e<N thì n có thể bị kẻ thù tìm thấy được
Một số hệ PKC khác
Rabin
Hệ Rabin cũng xây dựng trên việc lấy N=p×q làm bí mật. N được coi là khoá công khai
(PK) còn (p,q) là khoá bí mật (SK).
Mã hoá là việc thực hiện:
Y=X

2
Do phần này chỉ có mục đích giới thiệu tóm tắt nên ở đây không đi sâu hơn vào công thức tính nghiệm
Chương III - 13 -

Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000

y =g
u
(mod p)
Bây giờ khóa công khai của Alice được lấy là (p,g,y), khoá mật là u.
Sinh mã
:
1.
Nếu Bob muốn mã hoá một tin X để truyền cho Alice thì trước hết anh ta chọn một số
ngẫu nhiên k sao cho (k,p-1) =1
2.
Tính
a=g
k
(mod p)
b=y
k
X (mod p)
Mã là Y=(a,b) và có độ dài gấp đôi TIN.
Giải mã
: Alice nhận được Y= (a,b) và giải ra X theo công thức sau:
u
a
b
X =