Bài giảng Nhập môn An toàn thông tin: Chương 3 - PGS. Nguyễn Linh Giang
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (323.06 KB, 46 trang )
.c
om
PGS. Nguyễn Linh Giang
Bộ mơn Truyền thơng và
Mạng máy tính
cu
u
du
o
ng
th
an
co
ng
Nhập mơn An tồn thơng tin
CuuDuongThanCong.com
/>
I.
II.
Các hệ mật khóa đối xứng (mã hóa đối xứng)
Các hệ mật khóa cơng khai ( mã hóa bất đối xứng )
an
II.
III.
IV.
ng
II.
Cơ sở bài tốn xác thực
Xác thực thơng điệp
Chữ ký số và các giao thức xác thực
Các cơ chế xác thực trong các hệ phân tán
du
o
I.
th
Bài toán xác thực
III.
co
Nhập mơn An tồn thơng tin
Đảm bảo tính mật
I.
ng
.c
om
Nội dung
An tồn an ninh hệ thống
II.
Phát hiện và ngăn chặn xâm nhập ( IDS, IPS )
Lỗ hổng hệ thống
u
I.
cu
IV.
2
CuuDuongThanCong.com
/>
–
ng
an
cu
u
–
th
–
W. Stallings “Networks and Internetwork security”
W. Stallings “Cryptography and network security”
Introduction to Cryptography – PGP
D. Stinson – Cryptography: Theory and Practice
ng
–
co
Tài liệu môn học:
du
o
l
.c
om
Nội dung
3
CuuDuongThanCong.com
/>
co
an
cu
u
l
th
l
ng
l
Ngun lý hệ mật khố cơng khai
Thuật tốn RSA
Sơ đồ trao đổi khố Diffie-Hellman
Một số hệ mật khóa cơng khai khác
du
o
l
ng
.c
om
Chương III. Các hệ mật khóa cơng khai
4
CuuDuongThanCong.com
/>
Mật mã công khai dựa trên cơ sở của các hàm
tốn học.
Khơng dựa trên phép thay thế và đổi chỗ như
trong phương pháp mã hố đối xứng.
Mã mật cơng khai là bất đối xứng.
du
o
l
l
u
–
Trong cơ chế mã mật khố cơng khai sử dụng hai khố:
khố mật và khố cơng khai.
Các hệ quả của việc sử dụng hai khoá bất đối xứng:
tính tồn vẹn, tính xác thực, phân phối khố.
cu
–
ng
th
–
co
Đặc điểm
an
l
ng
.c
om
Ngun lý hệ mật khố cơng khai
5
CuuDuongThanCong.com
/>
ng
.c
om
Ngun lý hệ mật khố cơng khai
an
Hệ mã mật khố công khai được phát triển nhằm
giải quyết hai vấn đề phức tạp nảy sinh từ
phương pháp mã hoá đối xứng:
cu
u
l
Vấn đề thứ nhất: bài toán phân phối khoá;
Vấn đề thứ hai: chữ ký số.
du
o
l
ng
th
–
co
Xuất xứ:
l
6
CuuDuongThanCong.com
/>
ng
Hệ mật khố cơng khai.
Sơ đồ mã mật khố cơng khai sử dụng một khoá
để mã hoá và một khoá khác có liên quan để giải
mã. Các thuật tốn mã hố và giải mã có một số
đặc điểm quan trọng sau:
u
l
Khơng thể xác định được khố giải mã nếu chỉ biết
thuật toán mã hoá và khoá mã hoá.
Một số hệ mã mật khố cơng khai ( như RSA ) cịn
cung cấp khả năng sử dụng bất kỳ một khoá trong cặp
khố làm khố mã hố thì khố cịn lại sẽ được dùng
làm khố giải mã.
cu
l
du
o
ng
th
an
–
co
l
.c
om
Ngun lý hệ mật khố cơng khai
7
CuuDuongThanCong.com
/>
Sơ đồ mã hố cơng khai:
l
l
co
an
th
l
A và B có các cặp khóa (KRA, KPA), (KRB, KPB). Các khóa này dùng để mã
hố và giải mã các thơng điệp.
A và B cơng bố khố cơng khai KPA, KPB trong cặp khố, khố cịn lại được
giữ mật.
Khi gửi thơng điệp cho B, A sẽ mã hố văn bản bằng khố cơng khai KPB
của B.
Khi nhận được thông điệp, B sẽ giải mã bằng khố mật KRB. Bên thứ ba
khơng giải mã được thơng điệp vì chỉ có B biết khố mật KRB của B.
ng
l
du
o
–
ng
.c
om
Ngun lý hệ mật khố cơng khai
Khóa cơng khai của B
cu
u
Khóa riêng của B
Văn bản rõ
Mã hóa
Mã mật
A
Giải mã
Văn bản rõ
B
Đảm bảo tính mật
8
CuuDuongThanCong.com
/>
Sơ đồ xác thực:
Nếu A muốn gửi thông điệp được xác thực cho B, A sẽ
mã hoá văn bản bằng khố riêng của A.
Khi B nhận được thơng điệp, B sẽ giải mã bằng khố
cơng khai của A. Khơng một bên thứ ba có thể giải mã
được thơng điệp vì chỉ có B biết khố mật của B.
du
o
ng
l
th
an
l
co
–
ng
.c
om
Ngun lý hệ mật khố cơng khai
Khóa riêng của A
cu
u
Khóa cơng khai của A
Văn bản rõ
Mã hóa
Mã mật
Giải mã
A
Văn bản rõ
B
Đảm bảo tính xác thực
9
CuuDuongThanCong.com
/>
.c
om
Ngun lý hệ mật khố cơng khai
–
u
–
cu
–
du
o
ng
–
co
–
Q trình sinh cặp khóa KP, KR là dễ trên phương diện tính tốn;
Q trình mã hóa bản tin bằng khóa cơng khai KP ở bên gửi là dễ:
Y = EKP(M);
Quá trình giải mã ra văn bản rõ khi biết khóa riêng KR và bản tin mật Y
là dễ:
M = DKR(Y);
Đối với thám mã, nếu chỉ biết KP sẽ rất khó trên phương diện tính tốn
để tính ra KR;
Đối với thám mã, nếu chỉ biết KP và bản tin mật Y sẽ rất khó trên
phương diện tính tốn để tính ra bản tin rõ M;
Ngun lý đối xứng: q trình mã hóa – giải mã có thể áp dụng theo
hai chiều: M = DKP[EKR(M)]
an
–
ng
Các u cầu đối với hệ mật khóa cơng khai
th
l
10
CuuDuongThanCong.com
/>
l
l
Bên gửi mã hóa bằng khóa cơng khai của bên nhận;
Bên nhận giải mã bằng khóa riêng.
du
o
Ứng dụng trong phân phối khóa(RSA, Diffie-Helman):
duy trì kênh mật phân phối khóa đối xứng bằng cơ sở
mã mật công khai;
Ứng dụng trong chữ ký số (RSA, DSS):
–
cu
u
–
an
Ứng dụng trong mật mã – mã hóa, giải mã (RSA):
th
–
co
Các ứng dụng của hệ mật khóa cơng khai
ng
l
ng
.c
om
Ngun lý hệ mật khố cơng khai
l
11
l
Bên gửi ký bằng khóa riêng.
Bên nhận xác thực chữ ký bằng khóa công khai của bên gửi.
CuuDuongThanCong.com
/>
an
th
cu
u
l
ng
l
Cơ sở lý thuyết số
Sơ đồ thuật toán
Thám mã RSA
du
o
l
co
ng
.c
om
Thuật tốn mã hố cơng khai RSA
12
CuuDuongThanCong.com
/>
.c
om
Sơ đồ thuật toán RSA
co
an
th
–
RSA do Ron Rivest, Adi Shamir và Len Adlenman
phát minh năm 1977;
Hệ thống mã khố cơng khai phổ biến và đa năng:
l
l
cu
u
l
Được sử dụng trong các ứng dụng mã hóa/giải mã;
Chứng thực;
Phân phối và trao đổi khoá.
ng
–
ng
Xuất xứ
du
o
l
13
CuuDuongThanCong.com
/>
–
–
an
th
ng
–
du
o
–
Phương pháp mã hóa khối;
Văn bản rõ và văn bản mật là các số nguyên có giá trị
từ 0 đến n-1, n – số nguyên lớn;
Mỗi khối có giá trị nhỏ hơn n.
Kích thước của khối (số bít) nhỏ hơn hoặc bằng log2(n).
Thực tế, kích thước của khối là k bit với
2k < n ≤ 2k+1.
u
–
co
Thuật toán RSA:
cu
l
ng
.c
om
Sơ đồ thuật toán RSA
14
CuuDuongThanCong.com
/>
M
u
Giải mã
cu
–
du
o
Mã mật
ng
th
Bản rõ
co
–
Cặp khóa: (e, d)
Mã hoá
an
–
ng
.c
om
Sơ đồ thuật toán RSA
Mã mật
C
Bản rõ
M = Cd mod n =
(Me)d mod n
15
CuuDuongThanCong.com
/>
co
an
th
ng
–
l
l
l
Có thể tìm được các số e, d, n sao cho:
Med = M mod n " M < n.
Thực hiện tính Me và Cd một cách đơn giản " M < n.
Không thể xác định được d nếu biết e và n
du
o
–
u
–
Bên gửi và bên nhận phải biết số n.
Bên gửi biết khóa cơng khai là cặp (e, n).
Bên nhận có khóa riêng là cặp (d, n).
Các yêu cầu:
cu
–
ng
.c
om
Sơ đồ thuật toán RSA
16
CuuDuongThanCong.com
/>
.c
om
Sơ đồ thuật tốn RSA
Tìm các số e, d sao cho:
Med=M mod n
Hệ quả của định lý Euler: cho p và q là số nguyên tố,
n và m là hai số nguyên sao cho: n=pq và 0 < m < n,
k là số nguyên bất kỳ. Đẳng thức sau nghiệm đúng:
mkf(n)+1=mk(p-1)(q-1)+1ºm mod n
Như vậy: ed = kf(n)+1, tức là:
ed º1 mod f(n) hay d ºe-1 mod f(n) có nghĩa là
gcd(f(n), d) = 1 và gcd(f(n), e) = 1
–
cu
–
u
du
o
ng
–
th
an
–
ng
Tạo khoá
co
l
17
CuuDuongThanCong.com
/>
co
Sơ đồ tạo khóa RSA
cu
u
du
o
ng
th
an
–
ng
.c
om
Sơ đồ thuật tốn RSA
18
CuuDuongThanCong.com
/>
.c
om
Sơ đồ thuật toán RSA
l
co
an
th
l
p = 7, q = 17
n = pq = 119; f(n)=(p-1)(q-1)=96
Chọn e nguyên tố cùng nhau với f(n), nhỏ hơn f(n),
–
l
Chọn e = 5;
ng
l
ng
Ví dụ
Tìm d: dºe-1 mod f(n)
d=77 => cặp khóa: e=(5, 119); d=(77, 119)
cu
u
–
du
o
–
19
CuuDuongThanCong.com
/>
–
an
th
ng
–
Vấn đề trong thuật toán mã hoá và giải mã RSA là việc thực hiện phép
toán luỹ thừa và phép toán đồng dư với số nguyên lớn.
Giải quyết dựa trên tính chất của phép tốn mođun:
[(a mod n) x (b mod n)] mod n = (a x b) mod n
Tính am với m lớn.
l
Biểu diễn nhị phân của m =bkbk-1…b0=åbi≠02i
Do ú:
ổ
ử
cu
l
du
o
co
Mó hoỏ v gii mó
u
l
ng
.c
om
S thut toỏn RSA
a =a
m
ồ
ỗ
2i ữ
ỗ
ữ
ố bi ạ0 ứ
= ếa
2i
bi ạ 0
20
(
a mod n = Õ a mod n = Õ a mod n
2i
m
bi ¹ 0
CuuDuongThanCong.com
bi ¹ 0
2i
/>
)
.c
om
Sơ đồ thuật toán RSA
co
Các bước quan trọng trong tạo khóa:
l
l
Xác định 2 số nguyên tố p và q. Để tránh tấn công vét cạn, p và q
phải lớn.
Xác định e và d
an
–
ng
Sinh khoá
th
l
định số nguyên tố p, q (sử dụng thuật toán Miller – Rabin)
1. Chọn một số nguyên lẻ n ngẫu nhiên (sử dụng bộ sinh số
giả ngẫu nhiên).
2. Chọn một số nguyên a < n ngẫu nhiên.
3. Thực hiện thuật toán xác suất để kiểm tra số ngun tố.
Nếu n test thành cơng thì loại bỏ giá trị n và quay lại bước 1.
4. Nếu n test thành công với số lượng test đủ, chấp nhận n;
mặt khác, quay lại bước 2.
- Chọn e và tính d từ e và f(n) (sử dụng thuật toán Euclid)
cu
u
du
o
ng
- Xác
21
CuuDuongThanCong.com
/>
an
Tấn cơng vét cạn: thử vét cạn tồn bộ khơng
gian khóa riêng.
Tấn cơng tốn học: thực hiện bài tốn phân
tích số ngun thành tích hai số ngun tố.
Tấn cơng dựa vào thời gian: dựa vào thời
gian để thực hiện thuật toán giải mã.
cu
l
u
du
o
l
ng
th
l
co
ng
.c
om
Thám mã RSA
22
CuuDuongThanCong.com
/>
Phương pháp: thực hiện vét cạn tồn bộ khơng gian
khố.
Biện pháp đối phó:
th
cu
u
–
Sử dụng khơng gian có khố kích thước lớn, tức là tăng số bít
của d và e.
Khơng gian khóa có kích thước lớn sẽ làm q trình sinh khoá,
mã hoá, giải mã thực hiện chậm đi.
ng
–
du
o
l
an
co
l
ng
.c
om
Thám mã RSA - tấn công vét cạn
23
CuuDuongThanCong.com
/>
th
Phân tích n thành tích hai số nguyên tố p và q;
–
Xác định f(n) trực tiếp không qua p và q;
l
–
ng
l
Sau đó cho phép tính f(n)=(p-1)(q-1);
Từ f(n) có thể tính d=e-1 mod f(n).
du
o
l
u
–
an
co
Các phương pháp tấn cơng tốn học vào
RSA:
Cho phép từ f(n) có thể tính d=e-1 mod f(n).
cu
l
ng
.c
om
Thám mã RSA - Tấn cơng tốn học
Xác định trực tiếp d khơng qua tính f(n).
24
CuuDuongThanCong.com
/>
.c
om
Thám mã RSA - Tấn cơng tốn học
ng
Trường hợp đơn giản nhất là người thám mã biết
được f(n)
Phân tích n thành tích của 2 thừa số ngun tố: Có
nhiều thuật tốn phân tích n thành hai thừa số
ngun tố.
l
l
–
Các thuật tốn được biết đến nhiều trước đây:
l
l
l
25
Thuật tốn sàng bình phương (quadratic sieve),
Đường cong elip (elliptic curve) và
Sàng trường số.
u
l
du
o
Có ba thuật toán hiệu quả trên các số rất lớn:
cu
–
ng
th
l
an
co
l
l
Thuật toán p – 1 của Pollard,
Thuật toán p + 1 của William,
Thuật toán chia nhỏ liên tiếp
Thuật toán chia thử.
CuuDuongThanCong.com
/>
