Bài giảng An toàn Hệ thống Thông tin - Bài: Mật mã & Ứng dụng - Chủ đề: Công khai - Trần Đức Khánh
Mật mã & Ứng dụng
Trần Đức Khánh
Bộ môn HTTT – Viện CNTT&TT
ĐH BKHN
Chủ đề
oꢀ Hệ mật mã cổ điển
oꢀ Hệ mật mã khóa bí mật (đối xứng)
oꢀ Hệ mật mã khóa công khai (bất đối
xứng)
oꢀ Hàm băm, chữ ký số
oꢀ Quản lý khóa, giao thức mật mã,…
Tại sao Hệ mật mã khóa công khai
oꢀ Hệ mật mã khóa đối xứng không đáp ứng
được 2 mục tiêu an toàn
nꢀ Xác thực
oꢀ Alice và Bob trao đổi thông tin bí mật
oꢀ Alice cần phải biết thông tin chắc chắn đến từ
Bob, và ngược lại
nꢀ Chống phủ nhận
oꢀ Alice và Bob trao đổi thông tin bí mật
oꢀ Nếu Alice đã gửi thông tin nào đó cho Bob thì
Alice không thể chối bỏ thông tin đó là của mình
Tại sao Hệ mật mã khóa công khai
oꢀ Quản lý khóa đối xứng là một vấn đề
nan giải
nꢀ Trong các hệ khóa đối xứng, mỗi cặp
người dùng phải có khóa riêng
nꢀ N người dùng cần N * (N-1)/2 khóa
nꢀ Việc quản lý khóa trở nên phức tạp khi
số lượng người dùng tăng
Hệ mật mã khóa công khai
oꢀ Mỗi người dùng có 1 khóa riêng và 1
khóa công khai
nꢀ Khóa riêng bí mật
nꢀ Khóa công khai có thể chia xẻ
oꢀ Quản lý khóa
nꢀ N người dùng cần N khóa công khai được
xác thực
nꢀ Hạ tầng khóa công khai PKI
Hệ mật mã khóa công khai
oꢀ Mã hóa dùng khóa công khai k
nꢀ C = E(k,M)
oꢀ Giải mã dùng khóa riêng K
nꢀ M = D(K,C)
Khóa công khai
Mã hóa
Khóa riêng
Giải mã
Mã
Tin ban đầu
Tin
Hệ mật mã khóa công khai
oꢀ Mã hóa dùng khóa riêng K
nꢀ C = E(K,M)
oꢀ Giải mã dùng khóa công khai k
nꢀ M = D(k,C)
Khóa riêng
Mã hóa
Khóa công khai
Giải mã
Mã
Tin ban đầu
Tin
Khóa bí mật vs. Khóa công khai
Khóa bí mật
Khóa công khai
Số khóa
Bảo vệ khóa
Ứng dụng
Tốc độ
1
2
Khóa được giữ bí 1 khóa bí mật
mật
1 khóa công khai
Bí mật và toàn vẹn
dữ liệu
Trao đổi khóa
Xác thực
Nhanh
Chậm
Hệ mật mã khóa công khai
oꢀ Lý thuyết nền tảng
nꢀ Độ phức tạp
nꢀ Số học đồng dư (Modular Arithmetic)
oꢀ Các hệ Mật mã khóa công khai
nꢀ RSA
nꢀ MerkleHellman
nꢀ ElGamal
nꢀ Rabin
nꢀ Đường cong êlip (Elliptic Curve)
nꢀ …
Độ phức tạp
oꢀ Độ phức tạp tính toán (thời gian)
nꢀ Vấn đề “dễ”: lớp P
nꢀ Vấn đề “khó”: lớp NP
oꢀ Giải quyết các vấn đề P
nꢀ Số trường hợp phải xét đến là một hàm đa thức
oꢀ Giải quyết các vấn đề NP
nꢀ Số trường hợp phải xét đến là hàm lũy thừa
Các hệ mật mã khóa công khai dựa trên
độ khó/phức tạp của giải thuật bẻ khóa
Số học đồng dư
oꢀ Số học đồng dư
nꢀ a mod n
nꢀ a op b mod n
oꢀ op = +, -, *, /, ^
oꢀ Ví dụ:
nꢀ 40 mod 6 = 4
nꢀ 5 + 2 mod 6 = 1
nꢀ 9 – 4 mod 3 = 2
nꢀ 5 * 3 mod 6 = 3
nꢀ 4/2 mod 3 = 2
nꢀ 2^4 mod 6 = 4
Số học đồng dư
oꢀ a mod n
nꢀ Số dư của a chia n
oꢀ a + b mod n
nꢀ Số dư của a + b chia n
oꢀ a - b mod n
nꢀ Số dư của a - b chia n
oꢀ a * b mod n
nꢀ Số dư của a * b chia n
oꢀ a ^ b mod n
nꢀ Thủ tục bình phương
oꢀ a / b mod n
nꢀ Giải thuật Euclide mở rộng
Thủ tục bình phương
oꢀ Dựa vào tính chất
nꢀ a*b mod n = ((a mod n)*(b mod n)) mod n
oꢀ Tính a^25
nꢀ a^25 = a^(11001)
nꢀ a^(11001) = a^(10000+1000+1)
nꢀ a^(10000+1000+1) = a^10000 * a^1000 *
a^1
nꢀ a^10000 * a^1000 * a^1 = a^16 * a^8 * a^1
oꢀ Độ phức tạp (O(logb*(logs)^2))
oꢀ Hiệu quả hơn phương pháp tính lũy thừa
bằng phép nhân đồng dư (O(b*(logs)^2))
Thủ tục bình phương
ModExp1(a,b, s)
oꢀ Vào:
nꢀ 3 số nguyên dương a,b,s sao cho a < s
nꢀ bn−1 ···b1b0 là biểu diễn nhị phân của b, n = [logb]
oꢀ Ra: a^b mod s
p[0] = a mod s
for i = 1 to n−1
p[i] = p[i−1]^2 mod s
r = 1
for i = 0 to n−1
if b[i] = 1 then r = r*p[i] mod s
return r
Bài tập
oꢀ Tính 6^73 mod 100
nꢀ 73 = 2^0 + 2^3 + 2^6
nꢀ 6^73 = 6 * 6^(2^3)*6^(2^6)
nꢀ 6 = 6 mod 100
nꢀ 6^(2^3) = 16 mod 100
nꢀ 6^(2^6) = -4 mod 100
nꢀ 6^73 = 6 * (16) * (-4) = 16 mod 100
Giải thuật Euclide mở rộng
oꢀ Giải thuật Euclide
nꢀ Tính ƯSCLN(a,b)
nꢀ Dựa trên tính chất
oꢀ Nếu a > b thì ƯSCLN(a,b) = ƯSCLN(a mod
b,b)
oꢀ Giải thuật Euclide mở rộng
nꢀ Tính 2 số x, y sao cho
oꢀ a*x + b*y = ƯSCLN(a,b)
nꢀ Giải quyết bài toán tìm x sao cho
oꢀ a*x = 1 mod s
Giải thuật Euclide mở rộng
Extended-Euclid(a,b)
oꢀ Vào: 2 số nguyên dương a,b
oꢀ Ra: 3 số nguyên x,y,d sao cho
d = ƯSCLN(a,b) và ax+by = d
1.ꢀ Nếu b = 0 thì trả về (1,0,a)
2.ꢀ Tìm q, r sao cho a = b*q+r
3.ꢀ (x’,y’,d) = Extended-Euclid(b, r)
4.ꢀ Trả về (y’,x’−q*y’,d)
Bài tập
oꢀ Dùng giải thuật Euclide mở rộng để tìm
ƯSCLN(120,23)
a
b
q
r
x
y
d
120 23
5
5
-9
47
1
23
5
5
3
2
1
0
4
1
1
2
_
3
2
1
0
_
2
-1
1
-9
2
1
1
1
1
1
3
-1
1
2
0
1
1
0
Bài tập
oꢀ Dùng giải thuật Euclide mở rộng để tìm
tìm x sao cho 51*x mod 100 = 1
nꢀ Nếu a*x mod n = 1 thì tồn tại k trong đó a*x =
1 + n*k
nꢀ Ta có a*x – n*k = 1
nꢀ Đặt y = -k, ta được a*x + b*y = 1
nꢀ Tìm x,y bằng giải thuật Euclide mở rộng
oꢀ x = -49, y = 25
Hệ Mật mã khóa công khai RSA
oꢀ RSA
nꢀ 1978 Rivest, Shamir và Adlerman phát
minh ra hệ mật mã RSA
nꢀ Hệ mật mã khóa công khai phổ biến và
đa năng nhất trong thực tế
nꢀ Sử dụng các kết quả trong số học đồng
dư
nꢀ Dựa trên độ phức tạp của bài toán
oꢀ phân tích số nguyên ra thừa số nguyên tố
Tải về để xem bản đầy đủ
36 trang
24000
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng An toàn Hệ thống Thông tin - Bài: Mật mã & Ứng dụng - Chủ đề: Công khai - Trần Đức Khánh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_an_toan_he_thong_thong_tin_bai_mat_ma_ung_dung_chu.pdf
