Bài giảng An toàn hệ thống thông tin - Chương 2, Phần 2: Mã hóa - Trần Thị Kim Chi

2 
Mã hóa bất đối xứng 
ASYMMETRIC CIPHERS 
Chương II 
MÃ HÓA 
(Cryptography) 
NỘI DUNG 
Mở đầu 
Mã hóa khóa công khai (Public-Key Cryptosystems) 
Thuật toán RSA 
Một số mã hóa khóa công khai khác 
1- 2 
( Cryptography and Network Security: Principles and Practices (3rd Ed.) – Chapter 9, 10) 
Trần Thị Kim Chi 
Đặt vấn đề 
Khuyết điểm của mã hóa đối xứng: 
Vấn đề trao đổi khóa giữa người gửi và người nhận: Cần phải có một kênh an toàn để trao đổi khóa sao cho khóa phải được giữ bí mật chỉ có người gửi và người nhận biết. Điều này tỏ ra không hợp lý khi mà ngày nay, khối lượng thông tin luân chuyển trên khắp thế giới là rất lớn. Việc thiết lập một kênh an toàn như vậy sẽ tốn kém về mặt chi phí và chậm trễ về mặt thời gian. 
Tính bí mật của khóa: không có cơ sở quy trách nhiệm nếu khóa bị tiết lộ. 
3 
Trần Thị Kim Chi 
Ý tưởng 
Vào năm 1976 Whitfield Diffie và Martin Hellman đã tìm ra một phương pháp mã hóa khác mà có thể giải quyết được hai vấn đề trên, đó là mã hóa khóa công khai (public key cryptography) hay còn gọi là mã hóa bất đối xứng (asymetric cryptography). 
Whitfield Diffie và Martin Hellman đưa ra 2 phương án sau: 
4 
Trần Thị Kim Chi 
Ý tưởng 
Phương án 1: người nhận (Bob) giữ bí mật khóa K 2, còn khóa K 1 thì công khai cho tất cả mọi người biết. 
Alice muốn gởi dữ liệu cho Bob thì dùng khóa K 1 để mã hóa. Bob dùng K 2 để giải mã. 
Ở đây Trudy cũng biết khóa K 1, tuy nhiên không thể dùng chính K 1 để giải mã mà phải dùng K 2. Do đó chỉ có duy nhất Bob mới có thể giải mã được. 
Điều này bảo đảm tính bảo mật của quá trình truyền dữ liệu. 
Ưu điểm của phương án này là không cần phải truyền khóa K 1 trên kênh an toàn. 
5 
Trần Thị Kim Chi 
Ý tưởng 
Phương án 2 : người gửi (Alice) giữ bí mật khóa K 1, còn khóa K 2 thì công khai cho tất cả mọi người biết. Alice muốn gởi dữ liệu cho Bob thì dùng khóa K 1 để mã hóa. Bob dùng K 2 để giải mã. 
Ở đây Trudy cũng biết khóa K 2 nên Trudy cũng có thể giải mã được. Do đó phương án này không đảm bảo tính bảo mật . 
Tuy nhiên lại có tính chất quan trọng là đảm bảo tính chứng thực và tính không từ chối . Vì chỉ có duy nhất Alice biết được khóa K 1, nên nếu Bob dùng K 2 để giải mã ra bản tin, thì điều đó có nghĩa là Alice là người gửi bản mã. Nếu Trudy cũng có khóa K 1 để gửi bản mã thì Alice sẽ bị quy trách nhiệm làm lộ khóa K 1. 
Trong phương án này cũng không cần phải truyền K 2 trên kênh an toàn Mã bất đối xứng kết hợp 2 phương án trên 
6 
Trần Thị Kim Chi 
Mã hóa công khai(Public-Key Cryptosystems) 
Mã bất đối xứng là một dạng của hệ thống mật mã mà trong đó mã hóa (encryption) và giải mã (decryption) được thực hiện bằng cách dùng hai khóa (Key) khác nhau 
Một là khóa công khai (Public key) và một là khóa bí mật (Private key). 
Nó cũng được gọi tên là 
MÃ HÓA KHÓA CÔNG KHAI 
(Public-key Encryption) 
Có hai mode làm việc : 
Bảo mật : Mã bằng public key giải mã bằng private key 
Xác thực : Mã bằng private key giải mã bằng public key 
7 
Trần Thị Kim Chi 
Mã hoá bất đối xứng(asymmetric cipher model) 
Key 1 
Plaintext 
Message 
Encryption 
Algorithm 
Decryption 
Algorithm 
Key 2 
Plaintext 
Message 
Transmitted Ciphertext 
Sơ đồ mã hóa bất đối xứng 
Mã hoá bất đối xứng 
“ An intro to PKI and few deploy hints” 
“Py75c%bn&*)9|fDe^bDzjF@g5=&nmdFgegMs” 
“An intro to PKI and few deploy hints” 
Hai khoá khác nhau 
Mã hoá 
Giải mã 
input : văn bản thuần tuý 
Văn bản mật mã 
output : văn bản thuần tuý 
RSA 
RSA 
Mã hóa công khai(Public-Key Cryptosystems) 
Mã đối xứng có thể dùng để bảo mật (Confidentiality), chứng thực (Authentication), hoặc cả hai. 
Hiện nay, mã hóa khóa công khai được ứng dụng rộng rãi trong nhiều lĩnh vực, trong đó bao gồm: trao đổi, phân phối khóa, chữ ký số, bảo mật dữ liệu. 
Một số thuật toán mã hóa đối xứng: Diffie-Hellman, El-Gamal, RSA, ECC  
10 
Trần Thị Kim Chi 
Mã hóa công khai(Public-Key Cryptosystems) 
Mã hóa khóa công khai được dùng rộng rãi nhất là mã RSA. 
Độ khó của việc tấn công được dựa vào độ khó của việc tìm thừa số nguyên tố (Prime factors) của một số composite number (hợp số). 
11 
Trần Thị Kim Chi 
Hai vấn đề của Khóa bí mật 
Hai cơ chế của mã hóa khóa công khai 
12 
Mã hóa công khai(Public-Key Cryptosystems) 
Trần Thị Kim Chi 
Vấn đề phân phối khóa : 
Khó đảm bảo chia sẻ mà không làm lộ khóa bí mật 
Trung tâm phân phối khóa có thể bị tấn công. 
Không thích hợp cho chữ ký số : 
Bên nhận có thể làm giả thông điệp và nói rằng nhận từ bên gửi. 
Mã hóa công khai(Public-Key Cryptosystems) 
Trần Thị Kim Chi 
1- 13 
Mã hóa khóa công khaiPublic-Key Cryptosystems 
Mã hóa khóa công khai ( Public-Key Cryptosystems ) 
Phát minh bởi Whitfield Diffie & Martin Hellman - Stanford Unit, vào năm 1976 
Mục tiêu là khắc phục điểm yếu của mã hóa đối xứng 
Một số ứng dụng cụ thể: SSL, VPN, SSH. 
Phương pháp: dùng hai khóa khác nhau cho quá trình mã hóa và giải mã 
C = E ( P , K 1 ) và P = D ( C , K 2 ) 
14 
Trần Thị Kim Chi 
Tên gọi: 
Mã hóa hóa công khai ( Public-key Cryptosystems ) 
Mã hóa hai khóa ( two-key Cryptosystems ) 
Mã hóa bất đối xứng ( asymmetric Cryptosystems ) 
Hai khóa: 
Một khóa public-key , có thể biết bất cứ ai, và có thể được dùng để mã hóa thông điệp. 
Khóa private-key , chỉ được biết bởi người nhận, dùng để giải mã thông điệp 
Bất đối xứng là bởi vì: 
Người mã hóa thông điệp không thể giải mã thông điệp do chính mình mã hóa 
Người thẩm tra chữ ký không thể tạo ra chữ ký 
Mã hóa công khai(Public-Key Cryptosystems) 
Trần Thị Kim Chi 
1- 15 
Giải thuật khóa công khai gồm 6 thành phần: 
Đầu vào của giải thuật: Bản rõ (thông điệp có thể đọc) 
Giải thuật mật hóa 
Khóa công khai và bí mật: một cặp khóa được chọn sao cho 1 khóa dùng để mã hóa và 1 khóa dùng để giải mã. 
Bản mã: thông điệp đầu ra ở dạng không đọc được , phụ thuộc vào bản r õ và khóa. Nghĩa là với cùng một thông điệp, 2 khóa khác nhau sinh ra 2 bảng mã khác nhau 
Giải thuật giải mã 
Giải thuật Mã hóa công khai(Public-Key Cryptosystems) 
Trần Thị Kim Chi 
1- 16 
Public-key encryption scheme: Encryption 
Trần Thị Kim Chi 
1- 17 
Public-key encryption scheme: Authentication 
Trần Thị Kim Chi 
1- 18 
Đặc điểm Public-Key Cryptosystems 
Không thể tính toán để tìm khóa giải mã (decryption key) khi chỉ biết thuật toán và khóa mã hóa (encryption key) 
Một trong hai khóa có thể dùng cho việc mã hóa (encryption), Khóa còn lại dùng cho giải mã (đối với thuật toán RSA) 
Trần Thị Kim Chi 
1- 19 
So sánh 
Conventional Encryption (Mã hóa thông thường) 
Cùng thuật toán với cùng khóa được dùng cho việc mã hóa và giải mã 
Sender và Receiver phải cùng chia sẻ thuật toán và khóa 
Khóa phải giữ bí mật 
Không thể hoặc ít nhất không thực thế để giải mã một thống điệp nếu những thông tin khác có sẳn. 
Sự hiểu biết về thuật toán cộng với các mẫu ciphertext phải đủ thì mới xác định ra được khóa. 
Public-key Encryption 
Một thuật toán được dùng để mã hóa và giải mã với một cặp khóa, một khóa dành cho mã hóa và một dành do giải mã 
Sender và receiver phải có một trong cặp khóa (không giống nhau) 
Một trong hai khóa phải được giữ bí mật 
Không thể hoặc ít nhất không thực thế để giải mã một thống điệp nếu những thông tin khác có sẳn. 
Sự hiểu biết về thuật toán + một trong hai khóa + các mẫu ciphertext phải đủ thì mới có thể xác định được khóa còn lại. 
Trần Thị Kim Chi 
1- 20 
Public-Key Cryptosystems: Secrecy 
Trần Thị Kim Chi 
1- 21 
Public-Key Cryptosystems: Authentication 
Trần Thị Kim Chi 
1- 22 
Thông điệp mã hóa được coi là một digital signature 
Public-Key Cryptosystems: Secrecy and Authentication 
Trần Thị Kim Chi 
1- 23 
Public-Key Application 
Có thể phân thành 3 loại: 
Mã hóa/giải mã ( Encryption/decryption ) : Sender mã hóa thông điệp bằng khóa public key của người nhận. 
Chữ ký số ( Digital signatures ) – cung cấp chứng thực (authentication): Sender mã hóa thông điệp bằng khóa public key của người nhận. Chữ ký được lưu bằng một thuật toán áp đặt vào message hoặc gắn vào một khối nhỏ dữ liệu mà là một hàm của message 
Trao đổi khóa ( Key exchange ) : Hai bên hợp tác để trao đổi khóa phiên (session key) 
Trần Thị Kim Chi 
1- 24 
Public-Key Application 
Một vài thuật toán thì phù hợp cho tất cả các ứng dụng, loại khác thì chỉ dành riêng cho một loại ứng dụng 
Trần Thị Kim Chi 
1- 25 
Phá mã Public-key 
Tấn công vét cạn (Brute Force attack): Luôn luôn là có thể về mặt lý thuyết 
 Sử dụng khóa đủ lớn (>512 bits) 
 khóa lớn ảnh hưởng đến tốc độ của việc mã hóa và giải mã 
Tìm Private key khi biết Public key: 
 Chưa được chứng minh tính khả thi của phương pháp này 
26 
Trần Thị Kim Chi 
An ninh Public-Key Cryptosystems 
An toán của hệ mã hóa khóa công khai dựa trên dộ khó của việc giải bài toán ngược. 
Tính bền của sự an toàn này còn phụ thuộc vào phương pháp tấn công của các thám mã 
Trần Thị Kim Chi 
1- 27 
Ưu điểm mã hóa khóa công khai 
Đơn giản trong việc lưu chuyển khóa: Chỉ cần đăng ký một khóa công khai mọi người sẽ lấy khóa này để trao đổi thông tin với người đăng ký không cần thêm kênh bí mật truyền khóa. 
Mỗi người chỉ cần một cặp khóa (PR, KU) là có thể trao đổi thông tin với tất cả mọi người. 
Là tiền đề cho sự ra đời của chữ ký số và các phương pháp chứng thực điện tử. 
28 
Trần Thị Kim Chi 
Hạn chế của mã Public keys 
Tốc độ xử lý 
Các giải thuật khóa công khai chủ yếu dùng các phép nhân chậm hơn nhiều so với các giải thuật đối xứng 
Không thích hợp cho mã hóa thông thường 
Thường dùng trao đổi khóa bí mật đầu phiên truyền tin 
Tính xác thực của khóa công khai 
Bất cứ ai cũng có thể tạo ra một khóa công khai 
Chừng nào việc giả mạo chưa bị phát hiện có thể đọc được nội dung các thông báo gửi cho người kia 
Cần đảm bảo những người đăng ký khóa là đáng tin 
29 
Trần Thị Kim Chi 
Nhắc lại lý thuyết số 
1. Phép chia modulo: 
Phép chia modulo là phép chia lấy phần dư. 
Ví dụ: 27 mod 8 = 3, 35 mod 9 = 8. 
Một cách tổng quát : 
Trần Thị Kim Chi 
1- 30 
Nhắc lại lý thuyết số 
1. Phép chia modulo: 
Nếu hai số a , b có cùng số dư trong phép chia cho n thì ta nói rằng a và b là đồng dư trong phép chia modulo cho n , phép so sánh đồng dư được ký hiệu bằng dấu  : 
Ví dụ với n = 4 ta có 4 lớp tương đương sau: 
Trần Thị Kim Chi 
1- 31 
Nhắc lại lý thuyết số 
2. Một số tính chất của phép modulo: 
Cho a , b và n là các số nguyên, phép modulo có các tính chất: 
Trần Thị Kim Chi 
1- 32 
Nhắc lại lý thuyết số 
3. Ước số: 
Nếu a mod n =0 (viết cách khác a 0 mod n ) thì có nghĩa là a chia hết cho n , hay n là ước số của a . 
Ước số chung lớn nhất của hai số: ký hiệu gcd ( a, b ) . Để tìm USCLN của hai số a, b, chúng ta có thể dùng thuật toán Euclid . 
Trần Thị Kim Chi 
1- 33 
Ước số chung lớn nhất(Greatest Common Divisor –gcd) 
Cho hai số a, b ∈ Z \{0}, c ∈ Z là ước số chung (common divisor) của a và b nếu c|a và c|b 
C được gọi là ước số chung lớn nhất (greatest common divisor), ký hiệu gcd(a, b), nếu nó là số nguyên lớn nhất được chia hết bởi cả a và b . 
Ví dụ: gcd(12,18) =6, gcd(-18,27) = 9 
34 
Thuật toán Euclid tìm gcd(a,b) 
35 
Ví dụ: Tìm gcd(2740,1760) 
 gcd (2740, 1760) = 20 
36 
Ví dụ: Tìm gcd(25,60) 
 gcd(25,60)=5 
37 
Nguyên tố cùng nhau (co-prime hay relatively prime ) 
Hai số nguyên a, b ∈ Z \{0} được gọi là nguyên tố cùng nhau nếu gcd(a, b)=1 . 
Ví dụ: (5,8) , (9,14) là các cặp nguyên tố cùng nhau 
38 
Phần tử nghịch đảo của phép nhân modulo: 
Nếu hai số nguyên a và n nguyên tố cùng nhau, thì tồn tại số nguyên w sao cho: 
	a.w  1 mod n 
Ta gọi w là phần tử nghịch đảo của a trong phép modulo cho n và ký hiệu là a -1 
39 
Nghịch đảo nhânmultiplicative inverse 
Nếu tồn tại 1 số b ∈ Z n sao cho 
ab ≡ 1(mod n) 
thì b được gọi là nghịch đảo nhân của a modulo n 
Ký hiệu 
40 
Nghịch đảo nhânmultiplicative inverse 
Điều kiện để số a có nghịch đảo nhân khi và chỉ khi gcd(a, n)=1 
Ví dụ: a=22, n=25 
 Gcd(22,25)= 1 a có nghịch đảo nhân 
 8 = 22 -1 (mod 25) vì 8.22 = 176 = 1 (mod 25) 
 8 là nghịch đảo nhân của 22 modulo 25 
41 
Cách tìm nghịch đảo nhân 
Cách 1: dùng giải thuật Euclid mở rộng 
	 au + pv = 1 với u,v số nguyên 
	u=a -1 mod p 
42 
Thuật toán Euclid mở rộng(extended Euclidean algorithm) 
Cho 2 số nguyên a và b, tìm 2 số nguyên khác s và t sao cho: 
Thực hiện phép mod cả 2 vế 
	 (s x n + t x b) mod n = 1 mod n 
	[(s x n) mod n] + [(txb) mod n] = 1 mod n 
	0 + [(txb) mod n] = 1 
	 ( t x b ) mod n = 1 t chính là nghịch đảo nhân của b 
Thuật toán này vừa có thể tính được gcd(a,b) vừa tính được các giá trị s và t 
43 
Thuật toán Euclid mở rộng(extended Euclidean algorithm) 
44 
Thuật toán Euclid mở rộng(extended Euclidean algorithm) 
45 
Ví dụ: a = 161 và b = 28, tìm gcd (a, b) và giá trị s và t. 
Giải: r = r 1 − q × r 2 ; s = s 1 − q × s 2 ; t = t 1 − q × t 2 
 gcd (161, 28) = 7, s = −1 và t = 6. 
46 
Ví dụ: Tìm nghịch đảo nhân của 23 trong Z 100 . 
t = t 1 − q × t 2 
 gcd(100 , 23) là 1; nghịch đảo nhân của 23 là - 13 hoặc 87. 
47 
Ví dụ: Tìm nghịch đảo nhân của 12 trong Z 26 . 
gcd(26 , 2) là 2; nghịch đảo nhân không tồn tại 
48 
Cách tìm nghịch đảo nhân 
Cách 2: dùng giải thuật tính số mũ nhanh (với p là số nguyên tố) 
	 a 1  a p-2 (mod p) 
49 
Phần tử nghịch đảo của phép nhân modulo: 
Ví dụ: 
Trong bảng trên không tồn tại số a -1 nào sao cho a.a -1  1 mod 10. Vậy không tồn tại phần tử nghịch đảo. 
Để tính chúng ta dùng thuật toán Euclid mở rộng 
50 
a -1 x7 mod 10 
a -1 x2 mod 10 
Bài tập tìm nghịch đảo nhân 
Cho n = 5 và a = 2. Tim nghịch đảo nhân 
Vì gcd(2, 5) = 1, do đó 2 sẽ có nghịch đảo nhân modulo 5 
 3 = 2 -1 (mod) 5 vì 2·3 ≡ 1 (mod 5). 
gcd(4, 15) = 1 vì vậy 4 có nghịch đảo nhân modulo 15. 
Vì 4 · 4 ≡ 1 (mod 15) nên 4 = 4 -1 (mod 15) 
51 
2. Hệ mã hóa RSA 
Đề xuất bởi Rivest, Shamir & Adleman – MIT, 1977 
Là hệ mã hóa khóa công khai phổ biến nhất 
Là cơ chế mã hóa khối, plaintext và ciphertext là các số nguyên từ 0 đến n-1. Kích cỡ n thường là 1024 bits, hoặc 309 chữ số thập phân (nghĩa là n <2 1024 ) 
Dựa trên hàm mũ (exponentiation) trong trường hữu hạn (finite field) 
Bảo mật cao vì chi phí phân tích thừa số c ủa một số nguyên lớn là rất lớn 
Trần Thị Kim Chi 
1- 52 
Mã hóa và Giải mã RSA 
Thuật toán mã hóa và giải mã RSA, RSA dùng phép lũy thừa modulo của lý thuyết số. 
Chọn hai số nguyên tố lớn p và q và tính N = pq . Cần chọn p và q sao cho: 
	M < 2 i-1 < N < 2 i . Với i = 1024 thì N là một số nguyên dài khoảng 309 chữ số. 
2. Tính  ( n) = ( p - 1)( q - 1) 
Tìm một số e sao cho e nguyên tố cùng nhau với n 
4. Tìm một số d sao cho e.d  1 mod n ( d là nghịch đảo của e trong phép modulo n ) 
5. Hủy bỏ n , p và q . Chọn khóa công khai K U là cặp ( e , N ), khóa riêng K R là cặp ( d , N ) 
1- 53 
, 
Mã hóa và Giải mã RSA 
Trần Thị Kim Chi 
1- 54 
Thuật toán RSAPhát sinh khóa 
(The G reatest C ommon D ivisor (GCD)- ước số chung lớn nhất) 
Trần Thị Kim Chi 
1- 55 
Thuật toán RSAThực hiện RSA 
Trần Thị Kim Chi 
1- 56 
Mã hóa và Giải mã RSA 
1- 57 
Quá trình xử lý của RSA và ví dụ minh họa 
Mã hóa và Giải mã RSA 
Ví dụ RSA: Để minh họa ta sẽ thực hiện một ví dụ về mã hóa RSA với kích thước khóa là 6 bít. 
Chọn p = 11 và q = 3, do đó N = pq = 33 (2 5 = 32 < 33 < 64 = 2 6 ) 
( n) = ( p -1 )( q -1 ) = 20 
Chọn e = 3 nguyên tố cùng nhau với n 
Tính nghịch đảo của e trong phép modulo n được d = 7 (3x7 = 21) 
Khóa công khai K U = ( e , N ) = (3, 33). Khóa bí mật K R = ( d , N ) = (7, 33) 
Trần Thị Kim Chi 
1- 58 
Mã hóa và Giải mã RSA 
Theo phương án 1 (mã hóa bảo mật): 
6) Mã hóa bản rõ M = 15: 
7 ) Giải mã bản mã C = 9 : 
Trần Thị Kim Chi 
1- 59 
Mã hóa và Giải mã RSA 
Theo phương án 2 (mã hóa chứng thực ): 
6 ) Mã hóa bản rõ M = 15: 
7 ) Giải mã bản mã C = 9 : 
Trần Thị Kim Chi 
1- 60 
Ví dụ thực hiện RSA 
Trần Thị Kim Chi 
1- 61 
Ghi chú : RSA sử dụng các sô nguyên tố lớn p,q để việc 
phân tích N với (N= pq) là vô cùng khó khăn. 
November 1, 2004 
Introduction to Computer Security 
©2004 Matt Bishop 
Example: Confidentiality 
Take p = 7, q = 11, so n = 77 and  ( n ) = 60 
Alice chooses e = 17, making d = 53 
Bob wants to send Alice secret message HELLO (07 04 11 11 14) 
07 17 mod 77 = 28 
04 17 mod 77 = 16 
11 17 mod 77 = 44 
11 17 mod 77 = 44 
14 17 mod 77 = 42 
Bob sends 28 16 44 44 42 
November 1, 2004 
Introduction to Computer Security 
©2004 Matt Bishop 
Slide #8- 63 
Example 
Alice receives 28 16 44 44 42 
Alice uses private key, d = 53, to decrypt message: 
28 53 mod 77 = 07 
16 53 mod 77 = 04 
44 53 mod 77 = 11 
44 53 mod 77 = 11 
42 53 mod 77 = 14 
Alice translates message to letters to read HELLO 
No one else could read it, as only Alice knows her private key and that is needed for decryption 
November 1, 2004 
Introduction to Computer Security 
©2004 Matt Bishop 
Slide #8- 64 
Example: Integrity/Authentication 
Take p = 7, q = 11, so n = 77 and  ( n ) = 60 
Alice chooses e = 17, making d = 53 
Alice wants to send Bob message HELLO (07 04 11 11 14) so Bob knows it is what Alice sent (no changes in transit, and authenticated) 
07 53 mod 77 = 35 
04 53 mod 77 = 09 
11 53 mod 77 = 44 
11 53 mod 77 = 44 
14 53 mod 77 = 49 
Alice sends 35 09 44 44 49 
November 1, 2004 
Introduction to Computer Security 
©2004 Matt Bishop 
Slide #8- 65 
Example 
Bob receives 35 09 44 44 49 
Bob uses Alice’s public key, e = 17, n = 77, to decrypt message: 
35 17 mod 77 = 07 
09 17 mod 77 = 04 
44 17 mod 77 = 11 
44 17 mod 77 = 11 
49 17 mod 77 = 14 
Bob translates message to letters to read HELLO 
Alice sent it as only she knows her private key, so no one else could have enciphered it 
If (enciphered) message’s blocks (letters) altered in transit, would not decrypt properly 
November 1, 2004 
Introduction to Computer Security 
©2004 Matt Bishop 
Slide #8- 66 
Example: Both 
Alice wants to send Bob message HELLO both enciphered and authenticated (integrity-checked) 
Alice’s keys: public (17, 77); private: 53 
Bob’s keys: public: (37, 77); private: 13 
Alice enciphers HELLO (07 04 11 11 14): 
(07 53 mod 77) 37 mod 77 = 07 
(04 53 mod 77) 37 mod 77 = 37 
(11 53 mod 77) 37 mod 77 = 44 
(11 53 mod 77) 37 mod 77 = 44 
(14 53 mod 77) 37 mod 77 = 14 
Alice sends 07 37 44 44 14 
 Sinh viên suy ra giải mã 
November 1, 2004 
Introduction to Computer Security 
©2004 Matt Bishop 
Slide #8- 67 
Bài tập 
1)Tìm cặp khóa bí mật và công khai với p=7 
 và q=19. Thực hiện mã hóa và giải mã với M=DHKHMT (11,08,24,22,41,05) đảm bảo tính bí mật, tính toàn vẹn/chứng thực và cả hai. 
2) Xây dựng mã giả cho thuật toán RSA 
3) Demo thuật toán RSA 
November 1, 2004 
Introduction to Computer Security 
©2004 Matt Bishop 
Slide #8- 68 
Giải thuật tính a c mod n 
1. c = 0; 
2. d = 1; 
3. for i = k downto 1 do 
6. 	 if bi = 1 then 
4. 	c = c × 2 + 1; 
5. 	d = (d × d × a) mod n; 
6. 	 else 
7. c = c × 2; 
8. d = (d × d) mod n; 
9. return d; 
Phá mã hệ mã hóa RSA 
Bốn hướng có thể để tấn công RSA: 
Vét cạn (Brute force attacks) : Thử tất cả các khóa private key có thể. Điều này phụ thuộc vào độ dài khóa. dùng khóa đủ lớn 
Phân tích toán học (Mathematical attacks) : Có vài hướng, nhưng tất cả đều tập trung vào việc phân tích thừa số tích của hai số nguyên tố. 
Phân tích thời gian (Timing attacks) : Cách này tùy thuộc vào thời chạy của thuật toán giải mã. 
Phân tích bản mã được chọn (Chosen ciphertext attacks) : khám phá các thuộc tính của thuật toán RSA. ngăn ngừa bằng cách làm nhiễu 
Trần Thị Kim Chi 
1- 69 
An ninh của hệ mã hóa RSA 
An ninh của RSA dựa trên độ khó của việc phân tích ra thừa số nguyên tố các số nguyên tố lớn. 
Thời gian cần thiết để phân tích thừa số một số lớn tăng theo hàm mũ với số bit của số đó 
Mất nhiều năm khi số chữ số thập phân của n vượt quá 100 (giả sử làm 1 phép tính nhị phân mất 1 s) 
Kích thước khóa lớn đảm bảo an ninh cho RSA 
Từ 1024 bit trở lên 
Gần đây nhất năm 1999 đã phá mã được 512 bit (155 chữ số thập phân) 
70 
Trần Thị Kim Chi 
An ninh của hệ mã hóa RSA 
Hiện tượng lộ bản rõ: 
Hệ mã RSA có N = p*q = 5*7, e = 17, với m = 6 ta có 
	C = 617 mod N = 6. 
Hệ mã RSA có N = p*q = 109*97, e = 865, với mọi m ta đều có m e mod N = M. 
Với hệ mã RSA có N = p*q và e bất kỳ, số lượng bản rõ bị lộ mã hóa sẽ là (1 + (e-1, p-1))*(1 + (e-1, q-1)). 
Trong thực tế RSA thường được sử dụng với các thông điệp có kích thước nhỏ (secsion key), và thường sử dụng lai ghép với các hệ mật đối xứng (DES,AES) 
71 
Trần Thị Kim Chi 
Ứng dụng của hệ mã hóa RSA 
1. Bảo mật thông điệp : Sử dụng khoá công khai của bên nhận để mã, khoá riêng của bên nhận để giải mã 
72 
Trần Thị Kim Chi 
Ứng dụng của hệ mã hóa RSA 
2. Xác thực thông điệp : Dùng khoá cá nhân của bên gửi để mã , khoá công khai của bên gửi để giải mã 
73 
Trần Thị Kim Chi 
Phạm vi ứng dụng của hệ mã hóa RSA 
Mạng hành chính công, E-Business, E-Government 
Kinh doanh thương mại điện tử : Thanh toán điện tử, bảo mật các dữ liệu điện tử, chứng thực chữ ký điện tử. . . 
Đào tạo, thi cử từ xa,bảo mật dữ liệu tuyển sinh. 
Ngân hàng thương mại: Giao dịch, thanh toán qua mạng. 
Xuất nhập cảnh 
 . . . . . 
74 
Trần Thị Kim Chi 
Bài tập 
Cho p = 5, q = 11, e = 7. Tính khóa riêng ( d, N ) trong phương pháp RSA. 
Thực hiện mã hóa và giải mã bằng phương pháp RSA với p = 3, q = 11, e = 7, M = 5 theo hai trường hợp mã hóa bảo mật và mã hóa chứng thực. 
Alice chọn p = 7, q = 11, e = 17, Bob chọn p = 11, q = 13, e = 11: 
a. Tính khóa riêng KRA của Alice và KRB của Bob 
b. Alice muốn gởi cho Bob bản tin M = 9 vừa áp dụng chứng thực và bảo mật như ở sơ đồ 4-3. Hãy thực hiện quá trình mã hóa và giải mã. 
75 
Trần Thị Kim Chi 
Bài tập 
Cho N = 1517. Hãy tính 131435 mod N. 
Trong hệ mã RSA có N = p * q = 103 * (219 – 1) thì có thể sử dụng tối đa là bao nhiêu gía trị của e để làm khóa mã hóa, giải thích. 
Trong hệ mã RSA có N = p*q = 103 * 113 sẽ có bao nhiêu trƣờng hợp lộ bản rõ. 
Cho hệ RSA có n = 1363, biết phi(n) = 1288 hãy mã hóa bản rõ M = 2007. 
T ư ơng tự Câu 1 với n = 215629 và phi(n) = 214684 hãy giải mã bản mã M = 2007. 
76 
Trần Thị Kim Chi 
Bài tập 
Cho hệ mã RSA có p = 31, q = 41, e = 271. 
a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. 
b) Để mã hóa các thông điệp đƣợc viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi các ký tự thành các số thập phân có hai chữ số nh ư sau: 
Khi đó ví dụ xâu ABC sẽ đƣợc chuyển thành 00 01 02 và sau đó cắt thành các số có 3 chữ số 000 (bằng 0) và 102 để mã hóa. Bản mã thu đƣợc là một tập các số ZN. Hãy thực hiện mã hóa xâu P = ”SERIUS”. 
c) Giả sử bản mã thu đƣợc là C = hãy thực hiện giải mã để tìm ra thông điệp bản rõ ban đầu. 
77 
Trần Thị Kim Chi 
Bài tập 
7. Cho hệ mã RSA có p = 29, q = 43, e = 11. 
a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. 
b) Để mã hóa các thông điệp đƣợc viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi các ký tự thành các số thập phân có hai chữ số nh ư sau: 
Khi đó ví dụ xâu ABC sẽ đƣợc chuyển thành 00 01 02 và sau đó cắt thành các số có 3 chữ số 000 (bằng 0) và 102 để mã hóa. Bản mã thu đƣợc là một tập các số ZN. Hãy thực hiện mã hóa xâu P = ”TAURUS”. 
c) Giả sử bản mã thu đƣợc là C = hãy thực hiện giải mã để tìm ra thông điệp bản rõ ban đầu. 
78 
Trần Thị Kim Chi 
Bài tập 
8 . Cho hệ mã RSA có n = 1363, e = 57. 
a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. 
b) Giả sử bản rõ P = 102 hãy mã hóa và đƣa ra bản mã C. 
c) Giả sử hệ mã trên đƣợc dùng làm hệ chữ ký điện tử, hãy tính chữ ký với thông điệp M = 201 
79 
Trần Thị Kim Chi 
3. Mã khóa công khai khác 
3.1 Trao đổi khóa Diffie-Hellman 
 (Diffie-Hellman Key Exchange) 
3.2 Mật mã Elgamal 
 (Elgamal Cryptographic System) 
3.3 Mật mã ECC 
 (Elliptic Curve Cryptography) 
Trần Thị Kim Chi 
1- 80 
Trao đổi khóa Diffie-Hellman 
Giải thuật mật mã khóa công khai đầu tiên 
Đề xuất bởi Whitfield Diffie và Martin Hellman vào năm 1976 
Chỉ dùng để trao đổi khóa bí mật một cách an ninh trên các kênh thông tin không an ninh 
Khóa bí mật được tính toán bởi cả hai bên 
An ninh phụ thuộc vào độ phức tạp của việc tính log rời rạc 
81 
Trần Thị Kim Chi 
Trao đổi khóa Diffie-Hellman 
82 
Trần Thị Kim Chi 
Trao đổi khóa Diffie-Hellman 
83 
Trần Thị Kim Chi 
Trao đổi khóa Diffie-Hellman 
84 
Trần Thị Kim Chi 
Trao đổi khóa Diffie-Hellman 
85 
Trần Thị Kim Chi 
Mật mã ElGamal 
Được đề xuất năm 1985, dựa vào độ phức tạp của bài toán logarit rời rạc. 
Mã ElGamal được dùng trong số tiêu chuẩn như: Digital Signature Standard (DSS) và S/MIME e-mail standard 
An ninh của ElGamal dựa trên độ khó của việc tính logarit rời rạc 
Trần Thị Kim Chi 
1- 86 
Mật mã ElGamal 
Quá trình tạo khóa của A sử dụng hệ ElGamal gồm các bước chính sau : 
A, B thống nhất số nguyên tố q và phần tử sinh q: 
Bên tạo khóa (A) chọn giá trị bí mật Xa (Xa<q-1) và tính giá trị Ya= X A mod q. Khi đó, bộ khóa K={PU,PR} của A, với khóa công khai PU={q, ,Y A } và khóa cá nhân PR={X A } 
Trần Thị Kim Chi 
1- 87 
: 
Mật mã ElGamal 
Quá trình B sử dụng bộ khóa của A trong việc truyền dữ liệu M (M<q): 
B chọn giá trị k (k<q) và tính toán khóa K =(Y A ) K mod q, C 1 = k mod q, C 2 =KM mod q. Khi đó (C1,C2) là bản mã được truyền đi 
Quá trình bên nhận (A) giải mã: 
Tính khóa K = (C 1 ) XA mod q 
Tìm bản gốc theo công thức: M =(C 2 K -1 )mod q 
Trần Thị Kim Chi 
1- 88 
: 
Mật mã đường cong Elliptic 
ECC- Elliptic Elliptic Curve Cryptography 
Ưu điểm: 
ECC sử dụng khoá có độ dài nhỏ hơn so với RSA. làm tăng tốc độ xử lý một cách đáng kể; với cùng một độ dài khoá thì ECC có nhiều ưu điểm hơn so với các giải thuật khác 
Có thể dụng cả 3 ứng dụng: bảo mật, trao đổi khóa, chữ ký số. 
An ninh ECC dựa trên vấn đề logarit đường cong elliptic 
Tính tin cậy vẫn chưa cao bằng RSA 
Trần Thị Kim Chi 
1- 89 
So sánh chiều dài khóa ứng với an toàn tương đương 
Symmetric scheme 
(key size in bits) 
ECC-based scheme 
(size of n in bits) 
RSA/DSA 
(modulus size in bits) 
56 
112 
512 
80 
160 
1024 
112 
224 
2048 
128 
256 
3072 
192 
384 
7680 
256 
512 
15360 
Trần Thị Kim Chi 
1- 90 
Câu hỏi và bài tập 
Khái niệm mã hóa khóa công khai, cơ chế, các thành phần của hệ mã hóa công khai 
Các đặc điểm và yêu cầu của hệ mã hóa công khai 
Nêu nguyên tắc của mã hóa khóa công khai? Tại sao trong mã hóa khóa công khai không cần dùng đến kênh an toàn để truyền khóa? 
Trong mã hóa khóa công khai, khóa riêng và khóa công khai có phải là 2 khóa tùy ý, không liên quan? Nếu có liên quan, tại sao không thể tính khóa riêng từ khóa công khai? 
91 
Trần Thị Kim Chi 
Câu hỏi và bài tập 
Ngoài vấn đề truyền khóa, mã hóa khóa công khai còn ưu điểm hơn mã hóa đối xứng ở điểm nào? 
Nêu nhược điểm của mã hóa khóa công khai. 
Hãy nêu các vấn đề về RSA 
Cho các cặp số nguyên tố sau: (13,23); (11,19); (23,29). Hãy thực hiện các bước phát sinh khóa để đưa ra khóa công khai, khóa bí mật 
Dùng các cặp khóa trên để mã hóa thông điệp có chiều dài 88 
Thế nào là độ an toàn của một thuật toán mã hóa? 
92 
Trần Thị Kim Chi 
THANKS YOU