MỤC LỤC
MỤC LỤC ..............................................................................................................1
MỞ ĐẦU ................................................................................................................4
CHƯƠNG I. CÁC KHÁI NIỆM CƠ BẢN ..............................................................6
1.1. Một số khái niệm toán học.............................................................................6
1.1.1. Số nguyên tố và số nguyên tố cùng nhau .................................................6
1.1.2. Đồng dư thức ..........................................................................................8
1.1.3. Không gian Zn và Zn*...........................................................................10
1.1.4. Phần tử nghịch đảo................................................................................10
1.1.5. Khái niệm nhóm, nhóm con, nhóm Cyclic.............................................11
1.1.6. Hàm Ф Euler .........................................................................................11
1.1.7. Các phép toán cơ bản trong không gian modulo ....................................12
1.1.8. Hàm một phía và hàm một phía có cửa sập............................................13
1.1.9. Hàm Euler, định lý Euler và định lý Fermat ..........................................14
1.1.10. Bậc và căn nguyên thủy.......................................................................15
CHƯƠNG II. HỆ MẬT MÃ KHÓA CÔNG KHAI ...............................................17
2.1. Tổng quan về các hệ mật mã .......................................................................17
2.1.1. Hệ mã hóa đối xứng ..............................................................................17
2.1.2. Hệ mật khóa công khai ..........................................................................26
2.2. Hệ mật khóa công khai RSA........................................................................33
2.2.1. Giới thiệu ..............................................................................................33
2.2.2. Phương pháp lập mã và giải mã của hệ mật RSA ..................................34
2.2.3. Độ an toàn của RSA ..............................................................................35
2.2.4. Quản lý khóa của hệ mật RSA...............................................................38
CHƯƠNG III. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG RSA ..............................50
1
3.1. Thám mã RSA.............................................................................................50
3.1.1. Một số giả thiết ngầm định .......................................................................52
3.1.2. Phân tích các số nguyên lớn......................................................................53
3.2. Các tấn công cơ bản ....................................................................................54
3.2.1. Modul chung .........................................................................................54
3.2.2. Mù (Blinding) .......................................................................................55
3.3. Số mũ riêng bé (Low private Exponent) ......................................................56
3.3.1. Độ lớn e ................................................................................................57
3.3.2. Sử dụng CRT ........................................................................................58
3.4. Số mũ công khai bé (Low public Exponent) ................................................58
3.4.1. Hastad's Broadcast Attack .....................................................................59
3.4.2. Franklin-Reiter Related Message Attack ...............................................59
3.5. Thành phần công khai bé.............................................................................60
3.5.1. Coppersmith's Short Pad Attack ............................................................60
3.5.2. Tấn công bằng khóa riêng .....................................................................61
3.6. Một số tấn công bằng nhân tử hóa số N với số N lớn ...................................63
3.6.1. Tìm nhân tử lớn nhất thứ nhất ≤ N .....................................................63
3.6.2. Phân tích thứ hai ...................................................................................64
3.6.3. Phân tích thứ ba.....................................................................................65
3.6.4. Thuật toán Pollard (p-1) ........................................................................66
3.7. Một số phương pháp gài bẫy mới trong RSA...............................................68
3.7.1. Phương pháp gài bẫy cặp bí mật (SP) ....................................................68
3.7.2. Phương pháp gài bẫy nhân độc lập (IS) .................................................70
3.8. Cài đặt các tấn công.....................................................................................73
3.8.1. Tấn công dựa trên thời gian...................................................................73
3.8.2. Tấn công dựa trên các lỗi ngẫu nhiên ....................................................75
3.9. Phương pháp tấn công bằng nhân tử hóa số N sử dụng định lý Fermat ........76
3.9.1. Bổ đề 1..................................................................................................76
2
3.9.2. Định lý Fermat ......................................................................................77
3.9.3. Xây dựng chương trình..........................................................................79
KẾT LUẬN...........................................................................................................81
TÀI LIỆU THAM KHẢO .....................................................................................82
3
MỞ ĐẦU
Ngày nay, thuật ngữ “thời đại thông tin” đã tr ở nên quá phổ biến đối với
nhiều người. Có thể nói, chưa bao giờ công nghệ thông tin lại phát triển bùng nổ
như hiện nay. Tin học có mặt tại hầu hết trong các lĩnh vực của đời sống xã hội, đã,
đang và sẽ còn tiếp tục đem lại những ứng dụng và lợi ích vô cùng to lớn cho con
người. Tại hầu khắp các nước trên thế giới, tin học phát triển vượt bậc. Những hệ
thống tin học không còn nhỏ lẻ, cục bộ, mà trái lại, chúng không ngừng phát triển
trở thành những hệ thống kiến trúc tin học lớn, đồ sộ và mang tính toàn cầu, đặc
biệt là các hệ thống mạng truyền tin và các hệ thống thương mại điện tử. Các hệ
thống này ngày càng đóng vai trò thiết yếu trong mọi lĩnh vực, mọi hoạt động của
toàn xã hội. Điều này cũng đ ồng nghĩa với việc, nhu cầu đảm bảo an toàn và bảo
mật thông tin phải được đặt lên hàng đầu và có tầm quan trọng thời sự. Cũng chính
vì vậy mà công nghệ mã hóa thông tin ngay từ khi ra đời đã phát tri ển nhanh chóng
vượt bậc và đạt được rất nhiều kết quả ứng dụng sâu sắc. Một trong những công
nghệ mã hoá hiện đại và có ứng dụng phong phú là công nghệ mã hóa khóa công
khai, mà đại diện là hệ mật mã RSA.
Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir và Len Adleman,
công bố lần đầu vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ. Hệ mật được sử
dụng trong lĩnh v ực đảm bảo tính riêng tư và cung cấp cơ chế xác thực dữ liệu số.
Ngày nay, RSA đã đư ợc phát triển ứng dụng rộng rãi trong thương m ại điện tử. Nó
được sử dụng trên Web servers và trên các Browsers nhằm đảm bảo an ninh đường
truyền, được sử dụng trong việc tạo khóa và xác thực của mail, trong truy cập từ
xa…. Tóm lại, RSA được ứng dụng trong các lĩnh v ực nơi mà an ninh an toàn thông
tin được đòi hỏi.
Ngay từ khi được công bố, hệ RSA đã đư ợc phân tích hệ số an toàn bởi
nhiều nhà nghiên cứu. Thực tế, vấn đề thám mã đối với hệ mật RSA hiện tại đang
được các nhà nghiên cứu tập trung khai thác các sơ hở của RSA như: tấn công vào
4
số mũ công khai hoặc số mũ bí mật thấp, tấn công vào các tham số nguyên tố p, q
bé hoặc cách xa nhau lớn, hoặc họ tập trung vào việc phân tích nhân tử số n (modul
của RSA).
Từ những vấn đề trên, tôi chọn đề tài nghiên cứu “Tìm hiểu một số kỹ
thuật tấn công hệ mật RSA”. Đề tài cung cấp các kiến thức về phương pháp bảo
vệ an toàn thông tin dữ liệu có tính an toàn cao nhất hiện nay là dùng hệ mã khoá
công khai RSA, các kiến thức cơ bản về các hệ mật mã. Đồng thời trình bày một số
phương pháp tấn công RSA .
Luận văn gồm 3 chương với các nội dung sau:
Chương I: Trình bày một số cơ sở toán học được dùng để xây dựng hệ mật
mã công khai RSA và là công cụ để mô tả, phân tích các điểm yếu, phương pháp tấn
công hệ mật RSA được đề cập ở các chương tiếp theo.
Chương II: Giới thiệu về một số hệ mật đang được ứng dụng gồm các hệ mật
cổ điển và hệ mật khóa công khai. Nghiên cứu các vấn đề về hệ mật khóa công khai
và đi sâu tìm hiểu hệ mật RSA: Phương pháp mã hóa và giải mã, độ an toàn của
RSA, vấn đề quản lý khóa.
Chương III: Trình bày về một số phương pháp tấn công hệ mật RSA. Cài đặt
ứng dụng về phương pháp tấn công RSA bằng nhân tử hóa số N sử dụng định lý
Fermat.
Luận văn đã được kiểm tra kỹ nhưng cũng không tránh khỏi những sai sót,
rất mong nhận được sự đóng góp ý kiến của quý thầy cô, bạn bè và các đồng nghiệp
để hoàn thiện hơn nữa.
5
CHƯƠNG I. CÁC KHÁI NIỆM CƠ BẢN
Chương này trình bày một số khái niệm cơ sở toán học, lý thuyết số liên
quan được dùng để xây dựng hệ mật mã công khai RSA và là công cụ để mô tả,
phân tích các điểm yếu, phương pháp tấn công hệ mật RSA.
1.1. Một số khái niệm toán học
1.1.1. Số nguyên tố và số nguyên tố cùng nhau
1.1.1.1. Các ước số
Nói rằng, b (một số khác 0) là ước số của a nếu a=mb, với một giá trị m nào
đó. Ở đây a, b, m là các số nguyên. Như vậy, b là ước số của a, nếu như chia a cho
b không còn lại số dư. Để ký hiệu b là ước số của a thường sử dụng cách viết ba.
Có các quan hệ sau:
o
Nếu a1, thì a = 1.
o
Nếu ba và ab, thì a = ±b.
o
Số b bất kỳ khác 0 là ước số của 0.
o
Nếu bg và bh, thì b(mg + nh) đối với bất kì số nguyên m, n.
Để chứng minh khẳng định cuối cùng, cần chú ý như sau:
nếu bg thì g có dạng g = b * g1, đối với số nguyên g1 nào đó,
nếu bh thì h có dạng h = b * h1, đối với giá trị nguyên h1 nào đó,
Vì vậy: mg + nh = mbg1 + nbh1 = b * (mg1+ nh1)
Cuối cùng, b là ước số của mg + nh.
Ví dụ: Các số 1, 2, 3, 4, 6, 8, 12 và 24 là các ước số của 24.
1.1.1.2. Các số nguyên tố
Số nguyên dương p lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có các ước
số dương là 1 và p.
6
Ví dụ: 2, 3, 5, 7, 11, 13, …
Một số nguyên bất kỳ a > 1 có thể phân tích thành các thừa số và được trình
bày dưới dạng:
a = p11 p2 2 ... pt t ,
ở đây: p1
0.
Ví dụ: 91 = 7 * 13; 11011 = 7 * 112 * 13.
Nếu P là kí hiệu tập hợp tất cả các số nguyên tố, thì đối với một số nguyên
dương bất kì được viết duy nhất dưới dạng:
a = ∏ p p,
a
ở đây tất cả các ap ≥ 0
P
Ví dụ: 3600 = 24 * 32 * 52.
1.1.1.3. Các số nguyên tố cùng nhau
Chúng ta sẽ sử dụng ký hiệu gcd( a, b) để chỉ ước số chung lớn nhất (UCLN)
của số a và b. Nói rằng, một số nguyên dương c là UCLN của a và b, nếu:
o
c là ước số của a và b.
o
Ước số bất kỳ của a và b đều là ước số của c.
Có thể định nghĩa tương đương như sau:
gcd(a, b) = max [k, khi ka và kb].
Bởi vì, đòi hỏi rằng UCLN là một số dương, chúng ta có
gcd(a, b) = gcd(a, –b ) = gcd(–a, b) = gcd(–a, –b ).
Nói chung, gcd(a, b) = gcd(|a|, |b|).
Ví dụ: gcd(60, 24 ) = gcd(60, –24 ) = 12.
7
Bởi vì tất cả các số nguyên khác không đều là ước số của số 0, chúng ta luôn
luôn có: gcd(a, 0 ) = |a|.
Dễ dàng xác định được UCLN của hai số nguyên dương, nếu các số này được
trình bày dưới dạng tích của các thừa số nguyên tố.
Ví dụ:
300 = 22 * 31 * 52,
18 = 21 * 32.
gcd(18, 300) = 21× 31× 50 = 6.
Trong trường hợp chung:
k = gcd(a, b) kp = min (ap, bp), đối với tất cả các p.
Các số nguyên a và b là nguyên tố cùng nhau, nếu chúng không có ước số
nguyên tố chung, hay ước số chung duy nhất của chúng là 1. Nói một cách khác a
và b là hai số nguyên tố cùng nhau nếu gcd(a, b) = 1.
Ví dụ: Số 8 và số 15 là các số nguyên tố cùng nhau, bởi vì ư ớc số của 8 là 1,
2, 4 và 8, còn các ư ớc số của 15 là 1, 3, 5 và 15. Như vậy, 1 là ước số chung duy
nhất của hai số này.
1.1.2. Đồng dư thức
Định nghĩa 1: Cho a là một số nguyên và m là một số nguyên dương. Khi đó ta ký
hiệu a mod m là số dư khi chia a cho m.
Từ định nghĩa số dư, ta suy ra rằng a mod m là số nguyên r sao cho: a=qm +
r và 0≤ r < m.
Ví dụ: Ta thấy:
17 mod 5 =2, -133 mod 9 =2 và 2001 mod 101 = 82.
8
Định nghĩa 2 (Đồng dư): Nếu a và b là hai số nguyên và m là một số nguyên
dương, thì a được gọi là đồng dư với b theo modulo m nếu a-b chia hết cho m và
được ký hiệu a≡b (mod m).
Chú ý rằng a ≡ b (mod m) nếu và chỉ nếu a mod m = b mod m.
Ví dụ: 5≡7 (mod 2) vì 5 mod 2 =1 và 7 mod 2 =1.
Một số tính chất quan trọng của đồng dư:
Tính chất 1: Nếu a1 ≡ b1 mod m và a 2 ≡ b2 mod m thì a1 + a 2 ≡ b1 + b2 mod m
Chứng minh: Từ giả thuyết ta có a1 = mt1 + b1 và a 2 = mt 2 + b2 , suy ra
a1 + a 2 =b1 +b2 + (t1 + t 2 )m , điều này có nghĩa là a1 + a 2 ≡ b1 + b2 mod m .
Tính chất 2: Nếu a1 ≡ b1 mod m và a 2 ≡ b2 mod m thì a1 *a 2 ≡ b1 * b2 mod m
Chứng minh: Từ giả thuyết ta có a1 = mt1 + b1 và a 2 = mt 2 + b2 , suy ra
a1 * a 2 =b1 * b2 + (b1t 2 + b2 t1 + mt1t 2 )n , điều này có nghĩa là a1 *a 2 ≡ b1 * b2 mod m
Tính
chất
3:
Nếu
như gcd(d , m) = 1, a ≡ b mod m, a = a1d , b = b1d ,
thì
a1 ≡ b1 mod m
Chứng minh: Từ giả thuyết ta có (a1 − b1 )d | n , mà gcd( d , m) = 1 , nên suy ra
(a1 − b1 ) | m , hay a1 ≡ b1 mod m .
Ví dụ: Chứng minh rằng 37n+2+16n+1+23n chia hết cho 7.
Giải: Rõ ràng chúng ta thấy rằng 37 ≡ 2 mod 7 , 16 ≡ 2 mod 7 và 23 ≡ 7 mod 7 , từ tính
chất 2 có: 37 n+ 2 ≡ 2 n+ 2 mod 7 , 16 n+1 ≡ 2 n+1 mod 7 , 23 n ≡ 7 n mod 7 .
Từ tính chất 1 có: 37n+2+16n+1+23n ≡ 7.2 n mod 7 , và từ tính chất 3 suy ra điều phải
chứng minh.
9
1.1.3. Không gian Zn và Zn*
Không gian Zn (các số nguyên theo modulo n)
Không gian các số nguyên theo modulon là tập hợp các số nguyên {0, 1,…,
n-1} bao gồm hai phép toán cộng và nhân. Việc cộng và nhân trong Zn được thực
hiện như trong phép cộng và nhân các số nguyên, ngoại trừ một điểm là các kết quả
sẽ được rút gọn theo modulon.
Ví dụ: Tính 11 * 13 trong Z16 . Tương tự như với các số nguyên ta có
11 * 13 = 143 . Để rút gọn 143 theo modulo 16, ta thực hiện phép chia bình thường:
143 = 8 × 16 + 15 ,
bởi vậy 143 mod16 = 15 . Do đó 11 × 13 = 15 trong Z16 .
Không gian Zn*: Là tập hợp các số nguyên p ϵ Zn, nguyên tố cùng nhau.
Tức là Zn* ={ p ϵ Zn | gcd(n, p)=1}, Ф(n) là số phần tử của Zn*.
Nếu n là một số nguyên tố thì Zn* ={ p ϵ Zn | 1≤ p ≤ n -1}
Ví dụ: Z2 = {0, 1} thì Z2* = {1} vì gcd(1, 2) =1.
1.1.4. Phần tử nghịch đảo
Định nghĩa: Cho a ∈ Z n . Phần tử nghịch đảo của a là phần tử b ∈ Z n sao cho
a * b ≡ b * a ≡ 1 mod n . Kí hiệu phần tử nghịch đảo của a là a-1.
Tính chất:
• Cho a, b ϵ Zn. Phép chia a cho b theo modulo n là tích của a và b theo
modulo n, và chỉ được xác định khi b có nghịch đảo theo modulo n.
• Cho a ϵ Zn, a là khả nghịch khi và chỉ khi gcd(a, n) =1.
• Giả sử d=gcd(a, n). Phương trình đ ồng dư ax≡b mod n có nghiệm x nếu và
chỉ nếu d chia hết cho b, trong trường hợp các nghiệm d nằm trong khoảng 0
đến n-1 thì các nghiệm đồng dư theo modulo n/d.
Ví dụ: 4-1 ≡ 7 (mod 9) vì 4×7 ≡ 1 ( mod 9)
10
1.1.5. Khái niệm nhóm, nhóm con, nhóm Cyclic
Định nghĩa: Nhóm là bộ đôi (G, * ), trong đó G là tập khác Ф, và * là một
phép toán hai ngôi trong G thỏa mãn ba tiên đ ề sau:
1. Phép toán nhóm kết hợp
a * (b * c) = (a * b) * c
∀a, b, c ϵ G
2. Có một phần tử 0 ϵ G được gọi là phần tử đơn vị thỏa mãn
∀a ϵ G
a*0=0*a
3. Với mỗi a ϵ G, tồn tại một phần tử a-1 ϵ G được gọi là nghịch đảo
a * a-1 = a-1 * a =0
Nhóm con: Bộ đôi (S, *) được gọi là nhóm con của (G, *) nếu:
1. S ⊂ G, phần tử trung gian e ϵ S
2. x, y ϵ S ⇒ x * y ϵ S.
Nhóm Cyclic: Nhóm G được gọi là nhóm Cyclic nếu tồn tại một phần tử α ϵ
G sao cho với mỗi b ϵ G có một số nguyên i sao cho b = αi . Phần tử α như v ậy
được gọi là phần tử sinh của G.
Nếu G là một nhóm và a ϵ G thì tập tất cả các lũy thừa của a sẽ tạo nên một
nhóm con Cyclic của G. Nhóm này được gọi là nhóm con sinh bởi a và được ký
hiệu là
.
Ví dụ: (Z+, *) là một nhóm Cyclic có phần tử sinh là 1.
1.1.6. Hàm Ф Euler
Định nghĩa: Với n ≥ 1 chúng ta gọi φ(n) là tập các số nguyên tố cùng nhau
với n nằm trong khoảng [1, n].
Tính chất:
1. Nếu p là số nguyên t ố → φ(p) = p-1
2. Nếu p = m.n, gcd(m, n) =1 → φ(p) = φ(m). φ(n)
11
3. Nếu n =
là thừa số nguyên tố của n thì
→ φ(n) = n
…
1.1.7. Các phép toán cơ bản trong không gian modulo
Cho n là một số nguyên dương. Các phần tử của Zn sẽ được biểu thị bởi các
số nguyên { 0, 1, 2, …, n-1}.
Ta thấy rằng, nếu a, b ϵ Zn thì
(a+b)modn=
Vì vậy, phép cộng (và trừ) theo modulo có thể thực hiện được mà không
cần thực hiện các phép chia.
Phép nhân modulo của a và b có thể được thực hiện bằng cách nhân các số
nguyên thông thường rồi lấy phần dư của kết quả sau khi chia cho n.
Các phần tử nghịch đảo trong Zn có thể được tính bằng cách dùng thuật toán
Euclie mở rộng được mô tả dưới đây:
Thuật toán (Tính các nghịch đảo trong Zn)
VÀO:
a ϵ Zn
RA:
a-1 mod n (nếu tồn tại)
1. Dùng thuật toán Euclide mở rộng để tìm các số nguyên x và
y sao cho ax + ny = d 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).
Phép lũy thừa theo modulo có thể được thực hiện có hiệu quả bằng thuật toán
nhân và bình phương có lặp. Đây là một thuật toán rất quan trọng trong nhiều thủ
tục mật mã.
12
Cho biểu diễn nhị phân của a là:
trong đó mỗi ki ϵ {0, 1} khi đó
Thuật toán nhân và bình phương có lặp để lấy lũy thừa trong Zn
VÀO:
a ϵ Zn và số nguyên k, ( 0 ≤ k < n) có biểu diễn nhị phân:
k=
RA:
ak mod n
1. Đặt b ← l. Nếu k = 0 thì return (b)
2. Đặt A ← a
3. Nếu k0 = 1 thì đặt b ← a
4. For i from l to t do
1. Đặt A ← A2 mod n
2. Nếu ki = l thì đặt b ← A*b mod n
5. Return (b).
1.1.8. Hàm một phía và hàm một phía có cửa sập
Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng
rất khó để tính ngược lại.
Ví dụ: Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhưng nếu biết f(x) thì
rất khó tính ra được x. Trong trường hợp này khó có nghĩa là để tính ra được kết quả
thì phải mất rất nhiều thời gian để tính toán.
f(x) được gọi là hàm một phía có cửa sập nếu tính xuôi y = f(x) thì dễ nhưng
tính ngược x = f-1(y) thì khó tuy nhiên nếu có “cửa sập” thì vấn đề tính ngược trở
nên dễ dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính
ngược.
13
Ví dụ: y = f(x) = xb mod n, tính xuôi thì dễ nhưng tính ngược x=ya mod n thì
khó vì phải biết a với a*b ≡ 1 (mod (φ(n))) trong đó φ(n) = (p-1)(q-1). Nhưng nếu
biết cửa sập p, q thì việc tính n = p*q và tính a trở nên dễ dàng.
Hộp thư là một ví dụ về hàm một phía có cửa sập. Bất kỳ ai cũng có thể bỏ
thư vào thùng. Bỏ thư vào thùng là một hành động công cộng. Mở thùng thư không
phải là hành động công cộng. Nó là việc khó khăn, bạn sẽ cần đến mỏ hàn để phá
hoặc những công cụ khác. Tuy nhiên nếu bạn có “cửa sập” (Trong trường hợp này
là chìa khóa của hòm thư) thì công việc mở hòm thư thật dễ dàng.
1.1.9. Hàm Euler, định lý Euler và định lý Fermat
Định nghĩa (Hàm Euler)
Cho n là số nguyên dương, đặt (n) là số các phần tử của tập hợp, mà tập này là
các số nguyên trong khoảng [1, n] và nguyên tố cùng nhau với n, thì (n) gọi là hàm
Euler.
Ta công nhận một số tính chất quan trọng của hàm Euler:
1. (1) = 1
2. Nếu p là số nguyên tố thì ( p) = p − 1
3. Nếu như p và q là hai số nguyên tố cùng nhau thì ( pq) = ( p) * (q)
4. ( p s ) = p s −1 ( p − 1)
5. Nếu như n = p1e p2e ... pke , ở đây p1 , p 2 , …, pk là số nguyên tố, thì
1
(n) = n1 −
1
p1
2
k
1
1
1 −
...1 −
p2
pk
Định lý Euler: Cho n > 1, gcd(a, n) = 1 và (n) là hàm Euler. Khi đó ta có:
a ( n ) ≡ 1 mod n
Ví dụ: a = 3, n = 10, (10) = 4, 34 = 81 ≡ 1 mod 10,
14
a = 2, n = 11, (11) = 10, 210 = 1024 ≡ 1 mod 11.
Các hệ quả của định lý Euler:
Hệ quả 1: nếu gcd(c, n)=1 và a≡b (mod (n) ) với a, b là 2 số tự nhiên, thì
Hệ quả 2: nếu e, d là các số nguyên thỏa mãn
thì với mọi số c
nguyên tố cùng nhau với n, ta có
Định lý Fermat (bé): Cho p là số nguyên tố, a là số nguyên dương không
chia hết cho p. Khi đó ta có:
Từ định lý Fermat chúng ta có các hệ quả quan trọng sau:
Hệ quả 1: Cho a ∈ Z , p là số nguyên tố, thì ta có:
Hệ quả 2: Cho a, b ∈ Z , p là số nguyên tố (a + b) n ≡ a n + b n mod p
Ví dụ: Chứng mình rằng 118 +218 +318 +418 +518 +618 ≡ –1 mod 7
Giải: Các số 1, 2, 3, 4, 5, 6 là số nguyên tố cùng nhau với 7. Nên theo định lý
Fermat chúng ta có các phương trình sau:
16 ≡ 1 mod 7 ; 2 6 ≡ 1 mod 7 ; 36 ≡ 1 mod 7 ; 4 6 ≡ 1 mod 7 ; 56 ≡ 1 mod 7 ; 6 6 ≡ 1 mod 7
Lấy bậc ba hai vế từng phương trình và cộng lại ta được:
118 +218 +318 +418 +518 +618 ≡ 6 mod 7 = −1 mod 7
1.1.10. Bậc và căn nguyên thủy
Định nghĩa 1 (Bậc)
15
Cho gcd(a, n) = 1. Bậc a mod n là số nguyên dương nhỏ nhất thỏa mãn
phương trình đ ồng dư thức:
a ≡ 1 mod n ,
Kí hiệu bậc là Ordn(a).
Ví dụ: Tìm bậc của 2 mod 5
Giải: 21 mod 5 = 2; 22 mod 5 = 4; 23 mod 5 = 3; 24 mod 5 = 1; vậy Ord5(2) = 4.
Định nghĩa 2 (Căn nguyên thủy)
Nếu như bậc của a modulo n bằng giá trị của hàm Euler của n. Thì a gọi là căn
nguyên thủy của n.
Ví dụ: Số 2 là căn nguyên thủy của 5. Vì Ord5(2) = (5) = 4.
16
CHƯƠNG II. HỆ MẬT MÃ KHÓA CÔNG KHAI
Chương này giới thiệu và phân biệt các hệ mật mã khóa bí mật và hệ mật mã
khóa công khai. Tiếp theo, ta trình bày về hệ mật khóa công khai RSA: phương
pháp mã hóa và giải mã, độ an toàn của RSA, vấn đề quản lý khóa.
2.1. Tổng quan về các hệ mật mã
2.1.1. Hệ mã hóa đối xứng
Định nghĩa:
Hệ mã hóa khóa đối xứng là hệ mã hóa mà biết được khóa lập mã thì có thể
“dễ” tính được khóa giải mã và ngược lại. Đặc biệt một số hệ mã hóa có khóa lập
mã và khóa giải mã trùng nhau (ke=kd), như hệ mã hóa “dịch chuyển” hay DES. Hệ
mã hóa khóa đối xứng còn gọi là Hệ mã hóa khóa bí mật, hay khóa riêng, vì phải
giữ bí mật cả 2 khóa. Trước khi dùng hệ mã hóa khóa đối xứng, người gửi và người
nhận phải thỏa thuận thuật toán mã hóa và khóa chung (lập mã hay giải mã), khóa
phải được bí mật.
Độ an toàn của hệ mã hóa loại này phụ thuộc vào khóa, nếu để lộ ra khóa này
nghĩa là b ất kỳ người nào cũng có thể mã hóa và giải mã thông báo trong hệ thống
mã hóa. Sự mã hóa và giải mã của hệ thống mã hóa khóa đối xứng biểu thị bởi:
và
.
Hình 2.1: Mô hình hệ thống mã hóa đối xứng
17
Hệ mã hóa khóa đối xứng thường được sử dụng trong môi trường mà khóa
chung có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ.
Hệ mã hóa khóa đối xứng thường dùng để mã hóa nh ững bản tin lớn, vì tốc độ mã
hóa và giải mã nhanh hơn hệ mã hóa công khai.
2.1.1.1. Mã dịch
Hãy xét R = C = K = Z26; x, y ϵ Z26. Với mỗi 0 ≤ K ≤ 26, ta định nghĩa:
Và
Hệ mật sử dụng Z26 vì trong bảng chữ cái tiếng Anh có 26 chữ cái. Chúng ta
có thể sử dụng mã dịch để mã hóa văn bản tiếng Anh bằng cách thiết lập tương ứng
giữa các ký tự trong bảng chữ cái với thặng dư 26 như sau: A↔0, B↔1,…, Z↔25 .
Cụ thể như sau:
A
0
B
1
C
2
D
3
E
4
F
5
G
6
H
7
I
8
J
9
K
10
L
11
M
12
N
13
O
14
P
15
Q
16
R
17
S
18
T
19
U
20
V
21
W
22
X
23
Y
24
Z
25
Ví dụ: Với K=11. Chúng ta cần mã hóa bản rõ sau:
BACHKHOAHANOI
Chúng ta sẽ chuyển bản rõ thành một chuỗi số nguyên dựa vào bảng chuyển
đổi ở trên thu được chuỗi:
1
0
2
7
10
7
Sau đó áp dụng hàm mã hóa
14
0
7
0
13
được chuỗi số nguyên sau:
18
14
8
12
11
13
18
21
18
25
11
18
11
24
25
19
Sau đó ta chuyển chuỗi số nguyên này trở lại các ký tự, ta được:
MLNSVSZLSLYZT
Để giải mã bản đã mã hóa, đầu tiên chúng ta phải chuyển bản mã thành chuỗi
số nguyên, sau đó trừ mỗi số đi 11 (rút gọn mod 26), và cuối cùng chuyển chuỗi số
nguyên về thành các ký tự.
Chú ý: Chúng ta có thể thấy hệ mật mã dịch (modulo 26) là không an toàn do
nó có thể bị giải mã bằng phương pháp vét cạn khóa. Do không gian khóa chỉ có 26
cho tới khi thu được một bản rõ có
giá trị nên rất dễ dàng để kiểm thử các giá trị
ý nghĩa xác định.
Ví dụ: Giả sử có xâu bản mã sau:
XKEXKURZKMZYQURKS
Chúng ta lần lượt thử các giá trị khóa
sau:
VIDVJTQYJLYXPTQJR
UICUISPXIKXVOSPIQ
THBTHROVHJVUNROHP
SGASGQNUGIUTMQNGO
RFZRFPMTFHTSLPMFN
QEYQEOLSEGSRKOLEM
PDXPDNKRDFRQJNKDL
OCVOCMJQCEQPIMJCK
19
,
,… thu được các bản rõ có thể có
NBUNBLIPBDOHLIBJ
MATMAKHOACONGKHAI
Tại điểm này ta xác định được bản rõ và có thể dừng lại. Khóa tìm được là
K=9.
Trung bình có thể tìm ra bản rõ sau khi thử 26/2 = 13 quy tắc giải mã.
Như vậy, để đảm bảo một hệ mật có độ an toàn thì không thể xảy ra việc vét
cạn khóa. Có thể khắc phục bằng cách chọn không gian khóa lớn hơn. Tuy nhiên,
không gian khóa lớn cũng chưa đủ để đảm bảo độ an toàn của hệ mật.
2.1.1.2. Hệ mật mã thay thế
Cho R = C = Z26. K gồm tất cả các hoán vị có thể có của 26 ký tự: 0, 1, 2,
…, 25. Với mỗi hoán vị π ϵ K ta định nghĩa:
, với
Và
là hàm ngược của π.
Trong hệ mã này, R và C tương ứng với 26 chữ cái trong bảng chữ cái tiếng
Anh.
Ví dụ một hoán vị ngẫu nhiên π sau (các ký tự của bản rõ viết bằng chữ
thường, bản mã viết bằng chữ hoa):
a
b
c
d
e
f
g
h
i
j
k
l
m
X
N
Y
A
H
P
O
G
Z
Q
W
B
T
n
o
p
q
r
s
t
u
v
w
x
y
z
S
F
L
R
C
V
M
U
E
K
J
D
I
20