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

(cid:122) Trao đổi khóa Diffie-Hellman (cid:122) Chữ ký ElGamal (cid:122) Hệ mật Knapsack

Khái quát hệ Diffie-Hellman

Hellman đưa ra vào 1976

(cid:122) Được đề cập trong một hội thảo do Diffie-

mật của hệ KCK

(cid:122) Là sự kết hợp của hai mô hình xác thực và

nhau đối với người sử dụng

(cid:122) Việc sinh ra các cặp khoá là hoàn toàn khác

qua trung gian xác thực

(cid:122) Sử dụng cơ chế trao đổi khoá trực tiếp không

Mục đích ra đời

(cid:122) 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)

(cid:122) 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

dụng sử dụng kĩ thuật trao đổi khoá

(cid:122) Thuật toán tự giới hạnchỉ dùng cho các ứng

Cơ sở hình thành thuật toán

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ể”

(cid:122) Dựa trên nguyên tắc toán học :với m là một số

(cid:122) Dựa trên phép tính logarit rời rạc

Thuật toán logarit rời rạc

luỹ thừa của nó thuộc (1,p-1)

(cid:122) Một số nguyên tố p (cid:122) Một gốc nguyên thuỷ a của p : là các số mà

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 .

(cid:122) Với b bất kì nguyên sẽ luôn ∃i sao cho b= ai

Mô hình chung của thuật toán

Avaible infor

A

B

Kpb

K

K

Generator

Thuật toán sinh khóa

– Khóa riêng xi : chọn sao cho xi

(cid:122) Lựa chọn số nguyên tố p và gốc nguyên thuỷ a (cid:122) Khoá của người i

– Khoá riêng xj : chọn sao cho xj

(cid:122) Khoá của người j

(cid:122) 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

phải sử dụng thuật toán logarit rời rạc : rất khó nếu p lớn

(cid:122) Thám mã có sẵn các thông tin :p,a,Yi,Yj (cid:122) Để có thể giải được K ,X bắt buộc thám mã

như không thể trong thời gian thực

(cid:122) Nếu chọn p lớn: việc tính toán ra X, K dường

Hệ mật và thám mã

,a,Yj,Yj

(cid:122) Thám mã có thể tấn công vào các thông tin : p

đó tính ra K

(cid:122) Và sử dụng thuật toán rời rạc để tính ra X, sau

logarit phụ thuộc vào chọn số nguyên tố p

(cid:122) Quan trọng nhất là độ phức tạp của thuật toán

Lĩnh vực ứng dụng

(cid:122) 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

dụng.

(cid:122) Sử dụng trong chữ kí điện tử. (cid:122) Các ứng dụng đòi hỏi xác thực người sử

ElGamal

– 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)

(cid:122) Tạo khóa: p, q, α, a, y=αa mod p (cid:122) Tạo chữ ký:

El Gamal (cont)

tính h(m) and v2= αh(m) mod p

(cid:122) Xác minh chữ ký

)1

−

– Xác minh 1 ≤ r ≤ p-1 – Tính v1 = yrrs mod p – – Đồng ý nếu v1=v2 1 − mh ({ )

k mh (

ar ) } − (mod ar

(mod p

p )1

s ≡ ks ≡

−

−

mh (

)

ar

ks

a

+

r s r)

(mod

p

)

α

α≡

( α≡

ElGamal (cont)

–

k phải đơn nhất đối với mỗi bản tin được ký (cid:122) (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

(cid:122) Chú ý:

ElGamal (cont)

(cid:122) Một module theo hàm mũ (cid:122) Một thuật toán ơclid (cid:122) Cả hai có thể được thực hiện offline

– Xác minh

(cid:122) Three modular exponentiations

(cid:122) Hiệu năng – Tạo chữ ký

toán xác thực, chứng thực

(cid:122) Các chữ ký ElGamal được tạo ra cho các bài

Thuật toán mã hoá công khai Knapsach

(cid:122) Bài toán Subset Sum (cid:122) Mô tả thuật toán Knapsack

Bài toán Subset Sum

(cid:122) Thuật toán Knapsach được xây dựng dựa trên bài toán Subset

Sum

Thuật toán Knapsack

Thuật toán Knapsack

(cid:122) KU = {t} là khoá công khai. (cid:122) KR = {p, a, s} là khoá mật. (cid:122) Hàm mã hoá

(cid:122) Hàm giải mã