Bài giảng An toàn thông tin

An Toàn Thông Tin 3/14/2014 An Ninh Mạng- Bô Môn IT 1 • Mã hóa dữ liệu • Kiểm tra chỉnh sửa dữ liệu Mã hóa công khai RSA RSA: Phương pháp RSA là một phương pháp mã hóa khóa công khai. RSA được xây dựng bởi các tác giả Ron Rivest, Adi Shamir và Len Adleman tại học viện MIT vào năm 1977, và ngày nay đang được sử dụng rộng rãi. Về mặt tổng quát RSA là một phương pháp mã hóa theo khối. Trong đó bản rõ M và bản mã C là các số nguyên từ 0 đến 2i với i số bít của khối. Kích thước thường dùng của i là 1024 bít. RSA sử dụng hàm một chiều là vấn đề phân tích một số thành thừa số nguyên tố. 3/14/2014 An Ninh Mạng- Bô Môn IT 2 Nguyên tắc thực hiện của RSA 3/14/2014 An Ninh Mạng- Bô Môn IT 3 Nguyên tắc thực hiện của RSA 3/14/2014 An Ninh Mạng- Bô Môn IT 4 Nguyên tắc thực hiện của RSA 3/14/2014 An Ninh Mạng- Bô Môn IT 5 Lý thuyết số 3/14/2014 An Ninh Mạng- Bô Môn IT 6 Thuật toán Euclid mở rộng 3/14/2014 An Ninh Mạng- Bô Môn IT 7 Thuật toán Euclid mở rộng 3/14/2014 An Ninh Mạng- Bô Môn IT 8 3/14/2014 An Ninh Mạng- Bô Môn IT 9 Tìm số nghịch đảo Bây giờ ta xét bài toán: nếu GCD(m, b) = 1, thì tìm nghịch đảo của b theo Modulo m. Ta mở rộng thuật toán Ơcơlit vừa tìm ước chung lớn nhất của m và b, vừa tính nghịch đảo trong trường hợp GCD(m, b) = 1. Thuật toán Euclidmở rộng: EXTENDED EUCLID(m, b) 1.(A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b) 2. if B3 = 0 return A3 = gcd(m, b); no inverse 3. if B3 = 1 return B3 = gcd(m, b); B2 = b–1 mod m 4. Q = A3 div B3 5. (T1,T2,T3)=(A1 – Q*B1,A2 – Q*B2, A3 – Q*B3) 6. (A1, A2, A3)=(B1, B2, B3) 7. (B1, B2, B3)=(T1, T2, T3) 8. goto 2 Thực vậy, các quan hệ sau là bất biến: mA1 + bA2 =A3; (1) mB1+ bB2 = B3 (2) mT1 + bT2 = T3; (3) Vì ban đầu: m.1 + b.0 = m; m.0 +b.1 = b, nên ta có (1) và (2) đúng. Và ta chứng minh trongmột bước lặp từ (1) và (2) suy ra (3). Từ thuật toán ta có : T1 =A1 – Q.B1 T2 =A2 – Q.B2 T3 =A3 – Q.B3 Nên ta sẽ chứng minh đẳng thức (3) còn lại mT1 + bT2= m(A1 – Q.B1) + b (A2 – Q.B2) = (mA1 + bA2) - Q(mB1+ bB2) = A3 – Q.B3 = T3 Khi sang bước lặp tiếp theo đổi vai trò B sang A và T sang B, thì các công thức đối (1) và (2) đối với A, B sẽ đúng, và do đó theo chứng minh trên (3) sẽ đúng trong bước lặp tiếp theo. Vậy (1), (2), (3) là các bất biến của vòng lặp. Cuối cùng khi B3 = 1, thì từ các bất biến ta có: mB1+ bB2 = 1 bB2 = 1- mB1 bB2 = 1 mod m Do đó: B2 = b-1 mod m 3/14/2014 An Ninh Mạng- Bô Môn IT 10 Ví dụ. Tìm nghịch đảo của 550 trong GL(1759). Mỗi bước thực hiện thuật toán Ơcơlit mở rộng sẽ được mô tả bởi một hàng trong bảng sau. 3/14/2014 An Ninh Mạng- Bô Môn IT 11 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. 1) Chọn p = 11 và q = 3, do đó N = pq = 33 (25 = 32 < 33 < 64 = 26) 2) n = (p-1)(q-1) = 20 3) Chọn e = 3 nguyên tố cùng nhau với n 4) Tính nghịch đảo của e trong phép modulo n được d = 7 (3x7 = 21) 5) Khóa công khai KU = (e, N) = (3, 33). Khóa bí mật KR = (d, N) = (7, 33) 3/14/2014 An Ninh Mạng- Bô Môn IT 12 Mã hóa bảo mật 3/14/2014 An Ninh Mạng- Bô Môn IT 13 Mã hóa chứng thực 3/14/2014 An Ninh Mạng- Bô Môn IT 14 Phát hiện và chỉnh lỗi trong truyền tin Phát hiện và chỉnh lỗi trong truyền tin Nguyên tắc chung: Trong quá trình truyền dữ liệu có thể gặp sự thay đổi các bit thông tin do nhiễu hoặc do sai hỏng của thiết bị hay module vào ra. Vì vậy, thực tế đặt ra là phải làm sao phát hiện được lỗi và có thể sửa sai được. Một trong phương pháp phát hiện lỗi (EDC: Error Dectecting Code) và sửa lỗi (ECC: Error Correcting Code) là: Giả sử cần kiểm tra m bit thì người ta ghép thêm k bit kiểm tra được mã hoá theo cách nào đó rồi truyền từ ghép m+k bit ( k bit được truyền không mang thông tin nên gọi là bit dư thừa) Trong đó m là số bit cần ghi vào bộ nhớ và k bit là số bit cần tạo ra kiểm tra lỗi trong m bit. 3/14/2014 An Ninh Mạng- Bô Môn IT 15 Khi đọc dữ liệu ra có khả năng sau:  Không phát hiện dữ liệu có lỗi.  Phát hiện thấy dữ liệu lỗi và có thể hiệu chỉnh dữ liệu lỗi thành đúng.  Phát hiện thấy lỗi nhưng không có khả năng chỉ ra lỗi vì thế phát ra tín hiệu báo lỗi.  Sơ đồ phát hiện lỗi và sửa lỗi 3/14/2014 An Ninh Mạng- Bô Môn IT 16 Phát hiện và chỉnh lỗi trong truyền tin 3/14/2014 An Ninh Mạng- Bô Môn IT 17 Phát hiện và chỉnh lỗi trong truyền tin Ví dụ 1: Phát hiện lỗi với bit chẵn lẻ(Party) Mã EDC đơn giản là bit chẵn lẻ được gắn thêm vào các bit dữ liệu. Nếu bit chẵn lẻ =1: nếu số bit 1 trong xâu là lẻ Hoặc sử dụng Nếu bit chẵn lẻ =0: nếu số bit 1 là chẵn Ưu điểm: đơn giản và số bit dư thừa ít. Nhược điểm: không định vị được lỗi, hoặc nếu có sự thay đổi cả hai bit hoặc 1 hoặc 0 thì không phát hiện được. Khắc phục nhược điểm trên xây dựng mã EDC khối. 3/14/2014 An Ninh Mạng- Bô Môn IT 18 Phát hiện và chỉnh lỗi trong truyền tin Ví dụ 2: Phát hiện lỗi bằng mã dư thừa CRC (Cycle Redundary Check). Nguyên tắc: Một xâu nhị phân bất kỳ có thể coi là tập hợp các hệ số của đa thức B(x) trong đó x là hư số. Chọn đa thức G(x) là đa nào đó ta quy định trước gọi đa thức sinh. Ta tiến hành chia module2 đa thức B(x) cho G(x) ta được thương số Q(x) và phần dư R(x).  Đa thức sinh do tổ chức viễn thông quốc tế quy định.  Khi đó ta cần truyền xâu B(x) + R(x) bit  Để kiểm tra lỗi ta cần chia giá trị nhận được cho đa thức sinh nếu phép chia có dư thì có lỗi xuất hiện trong xâu. 3/14/2014 An Ninh Mạng- Bô Môn IT 19 Phát hiện và chỉnh lỗi trong truyền tin 3/14/2014 An Ninh Mạng- Bô Môn IT 20 Phát hiện và chỉnh lỗi trong truyền tin 3/14/2014 An Ninh Mạng- Bô Môn IT 21 Phát hiện và chỉnh lỗi trong truyền tin 3/14/2014 An Ninh Mạng- Bô Môn IT 22 Phát hiện và chỉnh lỗi trong truyền tin 3/14/2014 An Ninh Mạng- Bô Môn IT 23