Giáo trình An toàn bảo mật thông tin - Nguyễn Khánh Văn - Chương 3: Hệ thống mã với khóa công khai Public Key Crystosystems

A: 
+ có tốc độ chậm hơn rất nhiều. 
+ Kích thước của khoá mật lớn hơn rất nhiều. 
Nếu như p và q cần biểu diễn cỡ 300 bits thì n cần 600 bits. Phép nâng lên luỹ thừa là khá 
chậm so với n lớn, đặc biệt là nếu sử dụng phần mềm (chương trình). Người ta thấy rằng 
thực hiện một phép nhân cỡ m + 7 nhịp Clock khi kích thước n là m bit. 
+Tốc độ hiện thời: 
Sử dụng phần cứng đặc chủng: n cỡ 507 bits thì đạt được tốc độ khoảng 220Kb/s 
 Phần mềm: n cỡ 512 bits thì đạt được tốc độ khoảng 11Kb/s 
Về bài toán phân tích ra thừa số nguyên tố 
Giải thuật tốt nhất vẫn là phương pháp sàng số. Một ước lượng về thời gian thực hiện của 
giải thuật là: 
n2log50
17.9
10
+
L(n) ≈ 
Trong đó log2n cho số biết số bit cần để biểu diễn n, số cần phân tích ra thừa số nguyên tố. 
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
n
±
−
2
1
e(a,n) = { }
{ }1,..2,1
,:),(
*
*
−=
∈=
nZ
ZanaeG
n
n 
Ví dụ: Với n=7, ta có 23=1, 33=6, 43=1, 53=6, 63=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 ∈Zn* 
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
Giải thuật tính luỹ thừa nhanh 
Luỹ thừa có thể được tính như thông thường bằng phép nhân liên tục tuy nhiên tốc độ sẽ 
chậm. Luỹ thừa trong trường Zn (modulo n) có thể tính nhanh hơn nhiều bằng giải thuật 
sau đây. Giải thuật này sử dụng hai phép tính là tính bình phương và nhân. 
Để tính Xα (modul n): 
1. Xác định các hệ số αi trong khai triển của α trong hệ nhị phân: 
α = α020 + α121 + α222 + ... + αk2k 
2. Dùng vòng lặp k bước để tính k giá trị ± n, với i=1,k : iX 2
11 222
224
2
...
−− ×=
×=
×=
kkk
XXX
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
⎪⎩
⎪⎨⎧ =
==
1,
0,1
)(
2
2
i
i
i
i
i
X
X α
αα 
Ví dụ: Xét RSA với n=179, e=73. 
Với X= 2 ta có Y= 273 ± 179 
73 = 64+8+1 = 26+23+20. 
Y=264+8+1 = 264 × 28 × 21 
Đ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 = Xe ± 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 
Người ta cho rằng có thể tránh được tình huống này nếu số nguyên tố được chọn là AN 
TOÀN. Một số nguyên tố được gọi là AN TOÀN nếu p=2p’+1 trong đó p’ cũng là số 
nguyên tố. 
Chương III - 11 - 
Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000
Đánh giá về an toàn của thuật toán RSA 
Sự an toàn của thành phần khoá mật (private key) phụ thuộc vào tính khó của việc 
PTTSNT các số lớn. 
Ký hiệu Z= (e,n) là khoá công khai. 
Nếu biết PTTSNT của n là n=p×q thì sẽ tính được m=φ(n) =(p-1)(q-1). Do đó tính được 
d=e-1(mod m) theo thuật toán gcd mở rộng. 
Tuy nhiên nếu không biết trước p,q thì như đã biết không có một thuật toán hiệu quả nào 
để phân tích TSNT được n, tức là tìm được p,q, khi n lớn. Nghĩa là không thể tìm được m 
và do đó không tính được d. 
Chú ý: Độ an toàn của RSA chưa chắc hoàn toàn tương đương với tính khó của bài toán 
PTTSNT, tức là có thể tồn tại phép tấn công phá vỡ được RSA mà không cần phải biết 
PTTSNT của n, chẳng hạn nếu như có kẻ thành công trong các dạng tấn công sau: 
1. Đi tìm thành phần mật: 
Kẻ thù biết X và Y với Y=Dz(X). Để tìm d nó phải giải phương trình: 
X = Yd±n 
Hay là tính d = logYX 
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=Xe 
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 e1,e2,N,Y1,Y2, nó sẽ suy ra 
đồng thời: 
Y1=Xe1 (mod N) 
Y2=Xe2 (mod N) 
Vì (e1,e2)=1 nên nó có thể tìm được a và b sao cho: 
a×e1+b×e2 = 1 
Suy ra kẻ thù có thể tìm được X từ: 
Y1a×Y2b= Xe1×a×Xe2×b=Xe1×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=X2 (mod N) 
còn giải mã là việc tính căn bậc hai: 
YX= (mod N) (*) 
Có thể thấy, nếu biết N=p×q thì dễ dàng tìm được nghiệm cho phương trình này, còn nếu 
không thì việc tìm nghiệm là khó tương đương với bài toán PTTSNT số N. 
2Khi biết N=p×q thì (*) được giải ra có bốn nghiệm , do đó để xác định được đâu là TIN 
gốc phải có mẹo để chọn được đúng 1 trong số 4 nghiệm đó 
Hệ Rabin có một số ưu điểm so với RSA: 
+ Tính an toàn được chứng minh hoàn toàn tương fđương với bài toán PTTSNT, nói cách 
khác tính ATBM của Rabin là có thể chứng minh được (provable) 
+ Ngoại trừ trường hợp RSA hoạt động với e nhỏ còn thuật toán sinh mã của Rabin nhanh 
hơn nhiều so với RSA là hệ đòi hỏi phải tính luỹ thừa. Thời gian giải mã thì tương đương 
nhau 
Nhược điểm: Vì phương trình giải mã cho 4 nghiệm nên làm khó dễ việc giải mã. Thông 
thường, TIN trước khi được mã hoá cần được nối thêm vào đuôi một chuỗi số xác định để 
làm dấu vết nhận dạng (chẳng hạn nối thêm 20 số 0 – như vậy trong số 4 nghiệm giải ra, 
chuỗi nào tận cùng bằng 20 con 0 thì đúng là TIN cần nhận). 
Vì lý do này nên Rabin thường được dùng chủ yếu cho chứng thực (chữ ký điện tử). 
El-Gamal 
Tạo khoá: Alice chọn một số nguyên tố p và hai số nguyên ngẫu nhiên g và u, cả hai đều 
nhỏ hơn p. Sau đó tính 
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 =gu (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=gk (mod p) 
b=ykX (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: 
ua
bX = (mod p) 
Ví dụ: p=11, g=3, u=6. Thế thì y=36=3 (mod 11). Khoá công khai là (p,g,y)=(11,3,3) còn 
khoá bí mật là u=6. 
Để mã hoá cho tin X=6, Bob chọn ngẫu nhiên k=7 và tính 
a=37=9(mod 11), b=37×6 = 10 (mod 11) 
Mã là (a,b) = (9,10) 
Bây giờ Alice nhận được (a,b) sẽ giải mã như sau 
X = b/(au) = 10/(97) = 10 × 5 =6 (mod 11) 
Chương III - 14 -