An toàn và an ninh thông tin
- 22 trang
- file .pdf
An toàn và An ninh thông tin
Nguyễn Linh Giang
Bộ môn Truyền thông
và Mạng máy tính
Khoa CNTT, ĐHBK HN
Một số hệ mật khóa công khai
Nội dung
z Trao đổi khóa Diffie-Hellman
z Chữ ký ElGamal
z Hệ mật Knapsack
Khái quát hệ Diffie-Hellman
z Được đề cập trong một hội thảo do Diffie-
Hellman đưa ra vào 1976
z Là sự kết hợp của hai mô hình xác thực và
mật của hệ KCK
z Việc sinh ra các cặp khoá là hoàn toàn khác
nhau đối với người sử dụng
z Sử dụng cơ chế trao đổi khoá trực tiếp không
qua trung gian xác thực
Mục đích ra đời
z Sử dụng để áp dụng cho các ứng dụng có độ
mật cao bằng phương pháp trao đổi khoá
(key exchange)
z Với nguyên tắc hai người sử dụng có thể trao
đổi một khoá an toàn - được dùng để mã hoá
các tin nhắn
z Thuật toán tự giới hạnchỉ dùng cho các ứng
dụng sử dụng kĩ thuật trao đổi khoá
Cơ sở hình thành thuật toán
z Dựa trên nguyên tắc toán học :với m là một số
nguyên tố thì
“Có thể tính toán dễ dàng y=ai mod m nhưng
việc tính ngược lại là rất khó và với m lớn thì
dường như là không thể”
z Dựa trên phép tính logarit rời rạc
Thuật toán logarit rời rạc
z Một số nguyên tố p
z Một gốc nguyên thuỷ a của p : là các số mà
luỹ thừa của nó thuộc (1,p-1)
z Với b bất kì nguyên sẽ luôn ∃i sao cho b= ai
mod p
Đây thuật toán logarit rời rạc .
Được coi là cơ sở để hình thành thuật toán
này .
Mô hình chung của thuật toán
Avaible infor
A B
Kpb
K Generator K
Thuật toán sinh khóa
z Lựa chọn số nguyên tố p và gốc nguyên thuỷ a
z Khoá của người i
– Khóa riêng xi : chọn sao cho xi – Khoá công khai yi : yi= axi mod p
z Khoá của người j
– Khoá riêng xj : chọn sao cho xj – Khoá công khai yj : yj= axj mod p
z Khoá mật chung : K=(yj)ximod p=(yi)xjmod p
Trao đổi khóa Diffie-Hellman
Thuật toán trao đổi khoá
Tính an toàn của hệ mật
z Thám mã có sẵn các thông tin :p,a,Yi,Yj
z Để có thể giải được K ,X bắt buộc thám mã
phải sử dụng thuật toán logarit rời rạc : rất khó
nếu p lớn
z Nếu chọn p lớn: việc tính toán ra X, K dường
như không thể trong thời gian thực
Hệ mật và thám mã
z Thám mã có thể tấn công vào các thông tin : p
,a,Yj,Yj
z Và sử dụng thuật toán rời rạc để tính ra X, sau
đó tính ra K
z Quan trọng nhất là độ phức tạp của thuật toán
logarit phụ thuộc vào chọn số nguyên tố p
Lĩnh vực ứng dụng
z Tự quá trình thuật toán đã hạn chế ứng dụng
chỉ sử dụng cho quá trình trao đổi khoá mật là
chủ yếu
z Sử dụng trong chữ kí điện tử.
z Các ứng dụng đòi hỏi xác thực người sử
dụng.
ElGamal
z Tạo khóa: p, q, α, a, y=αa mod p
z Tạo chữ ký:
– Chọn ngẫu nhiên k, 1 ≤ k ≤ p-1, gcd(k, p-1)=1
– Tính r = αk mod p
– Tính k-1 mod (p-1)
– Tính s = k-1 ∗ (h(m) - ar) mod (p-1)
– Chữ ký là (r,s)
El Gamal (cont)
z Xác minh chữ ký
– Xác minh 1 ≤ r ≤ p-1
– Tính v1 = yrrs mod p
– tính h(m) and v2= αh(m) mod p
– Đồng ý nếu v1=v2
−1
s ≡ k {h(m) − ar} (mod p − 1)
ks ≡ h(m) − ar (mod p − 1)
α h ( m ) ≡ α ar + ks ≡ (α a ) r r s (mod p )
ElGamal (cont)
z Chú ý:
– k phải đơn nhất đối với mỗi bản tin được ký
z (s1-s2)k=(h(m1)-h(m2))mod (p-1)
– Tấn công giả mạo có thể được thiết lập nếu các
hàm băm không được dùng
Nguyễn Linh Giang
Bộ môn Truyền thông
và Mạng máy tính
Khoa CNTT, ĐHBK HN
Một số hệ mật khóa công khai
Nội dung
z Trao đổi khóa Diffie-Hellman
z Chữ ký ElGamal
z Hệ mật Knapsack
Khái quát hệ Diffie-Hellman
z Được đề cập trong một hội thảo do Diffie-
Hellman đưa ra vào 1976
z Là sự kết hợp của hai mô hình xác thực và
mật của hệ KCK
z Việc sinh ra các cặp khoá là hoàn toàn khác
nhau đối với người sử dụng
z Sử dụng cơ chế trao đổi khoá trực tiếp không
qua trung gian xác thực
Mục đích ra đời
z Sử dụng để áp dụng cho các ứng dụng có độ
mật cao bằng phương pháp trao đổi khoá
(key exchange)
z Với nguyên tắc hai người sử dụng có thể trao
đổi một khoá an toàn - được dùng để mã hoá
các tin nhắn
z Thuật toán tự giới hạnchỉ dùng cho các ứng
dụng sử dụng kĩ thuật trao đổi khoá
Cơ sở hình thành thuật toán
z Dựa trên nguyên tắc toán học :với m là một số
nguyên tố thì
“Có thể tính toán dễ dàng y=ai mod m nhưng
việc tính ngược lại là rất khó và với m lớn thì
dường như là không thể”
z Dựa trên phép tính logarit rời rạc
Thuật toán logarit rời rạc
z Một số nguyên tố p
z Một gốc nguyên thuỷ a của p : là các số mà
luỹ thừa của nó thuộc (1,p-1)
z Với b bất kì nguyên sẽ luôn ∃i sao cho b= ai
mod p
Đây thuật toán logarit rời rạc .
Được coi là cơ sở để hình thành thuật toán
này .
Mô hình chung của thuật toán
Avaible infor
A B
Kpb
K Generator K
Thuật toán sinh khóa
z Lựa chọn số nguyên tố p và gốc nguyên thuỷ a
z Khoá của người i
– Khóa riêng xi : chọn sao cho xi
z Khoá của người j
– Khoá riêng xj : chọn sao cho xj
z Khoá mật chung : K=(yj)ximod p=(yi)xjmod p
Trao đổi khóa Diffie-Hellman
Thuật toán trao đổi khoá
Tính an toàn của hệ mật
z Thám mã có sẵn các thông tin :p,a,Yi,Yj
z Để có thể giải được K ,X bắt buộc thám mã
phải sử dụng thuật toán logarit rời rạc : rất khó
nếu p lớn
z Nếu chọn p lớn: việc tính toán ra X, K dường
như không thể trong thời gian thực
Hệ mật và thám mã
z Thám mã có thể tấn công vào các thông tin : p
,a,Yj,Yj
z Và sử dụng thuật toán rời rạc để tính ra X, sau
đó tính ra K
z Quan trọng nhất là độ phức tạp của thuật toán
logarit phụ thuộc vào chọn số nguyên tố p
Lĩnh vực ứng dụng
z Tự quá trình thuật toán đã hạn chế ứng dụng
chỉ sử dụng cho quá trình trao đổi khoá mật là
chủ yếu
z Sử dụng trong chữ kí điện tử.
z Các ứng dụng đòi hỏi xác thực người sử
dụng.
ElGamal
z Tạo khóa: p, q, α, a, y=αa mod p
z Tạo chữ ký:
– Chọn ngẫu nhiên k, 1 ≤ k ≤ p-1, gcd(k, p-1)=1
– Tính r = αk mod p
– Tính k-1 mod (p-1)
– Tính s = k-1 ∗ (h(m) - ar) mod (p-1)
– Chữ ký là (r,s)
El Gamal (cont)
z Xác minh chữ ký
– Xác minh 1 ≤ r ≤ p-1
– Tính v1 = yrrs mod p
– tính h(m) and v2= αh(m) mod p
– Đồng ý nếu v1=v2
−1
s ≡ k {h(m) − ar} (mod p − 1)
ks ≡ h(m) − ar (mod p − 1)
α h ( m ) ≡ α ar + ks ≡ (α a ) r r s (mod p )
ElGamal (cont)
z Chú ý:
– k phải đơn nhất đối với mỗi bản tin được ký
z (s1-s2)k=(h(m1)-h(m2))mod (p-1)
– Tấn công giả mạo có thể được thiết lập nếu các
hàm băm không được dùng