Bài giảng An toàn và bảo mật dữ liệu trong hệ thống thông tin - Chương 4: Hệ mã hóa khóa công khai PKC - Public Key Cryptosytems - Trương Tấn Khoa
CHƯƠNG 4:
HỆ MÃ HÓA KHÓA CÔNG KHAI PKC –
PUBLIC KEY CRYPTOSYTEMs
1
Chương 4:
Hệ mã hóa khóa công khai
Giới thiệu
⚫ Ý tưởng về hệ thống mã hó a khó a cô ng khai được
Martin Hellman, Ralph Merkle và Whitfield Diffie tại Đại
học Stanford giới thiệu vào năm 1976.
⚫ Sau đó, phương phá p Diffie-Hellman của Martin Hellman
và Whitfield Diffie đã được cô ng bố.
⚫ Năm 1977, trên bá o "The Scientific American", nhó m tá c
giả Ronald Rivest, Adi Shamir và Leonard Adleman đã
cô ng bố phương phá p RSA, phương phá p mã hó a khó a
cô ng khai nổi tiếng và được sử dụng rất nhiều hiện nay
trong cá c ứng dụng mã hó a và bảo vệ thô ng tin
2
Chương 4:
Hệ mã hóa khóa công khai
4.1. Khái niệm hệ mã hóa PKC
Nguyên lý cơ bản của các hệ mã khóa công khai
❖ Hệ mã khóa công khai là hệ mã dùng 2 khóa:
❑ Khóa công khai để mã hóa
❑ Khóa bí mật để giải mã
3
Chương 4:
Hệ mã hóa khóa công khai
Nguyên lý hoạt động
Trong cá c hệ mã hó a khó a cô ng khai, A và B muốn trao
đổi thô ng tin thì sẽ thực hiện theo sơ đồ sau:
❑ Trong đó B sẽ chọn khó a k=(k’, k’’). B sẽ gửi khó a lập mã k’
cho A (được gọi là khó a cô ng khai – public key) qua một kênh
bất kỳ và giữ lại khó a giải mã k’’ (được gọi là khó a bí mật –
private key).
❑ A có thể gửi văn bản M cho B bằng cá ch lập mã theo một
′
hàm ek nào đó với khó a cô ng khai k’ của B trao cho và được
′
bản mã M’ = 푒푘 (M). Sau đó gửi M’ cho B.
❑ Đến lược B nhận được bản mã M’ sẽ sử dụng một hàm giải
′′
mã 푑푘 nào đó với khó a bí mật k’’ để lấy lại bản gốc M=
4
′′
푑푘 (M’)
Chương 4:
Hệ mã hóa khóa công khai
Hì nh vẽ minh họa – Nguyên lý hoạt động
5
Chương 4:
Hệ mã hóa khóa công khai
4.2. Giới thiệu một số giải thuật PKC
❑ Trapdoor Knapsack
❑ RSA
❑ Elgama
6
Chương 4:
Hệ mã hóa khóa công khai
4.2. Giới thiệu một số giải thuật PKC
❑ Trapdoor Knapsack
❑ RSA
❑ Elgama
7
Chương 4:
Hệ mã hóa khóa công khai
4.2.1. Hệ mã Trapdoor Knapsack (Merkle
– Hellman)
Trapdoor Knapsack dựa trên bài toá n đóng thùng. Năm 1978,
hai nhà toá n học Merkle – Hellman đã đề xuất một thuật toá n
mã hó a PKC dựa trên bài toá n ĐÓNG THÙNG như sau:
➢ Cho một tập hợp các số dương 푎푖, 1≤i≤n và 1 số T dương.
σ
Hãy tìm 1 tập hợp chỉ số S ⊂ {1, 2,...,n} sao cho: 푖∈푆 푎푖=T
Bài toá n này là một bài toá n khó , theo nghĩa là chưa tì m được
thuật toá n nào tốt hơn là thuật toá n thử-vé t cạn.
➢ Thời gian xử lý vét cạn có thể tỉ lệ lũy thừa theo kích thước
input n
8
Chương 4:
Hệ mã hóa khóa công khai
TrapdoorKnapsack
VD: (푎1, 푎2, 푎3, 푎4) = (2, 3, 5, 7) và T=7. Hỏi có bao nhiêu
trường hợp nhặt ra trong tập 푎푖 để tổng giá trị bằng T?
Như vậy ta có 2 đáp số:
1. S=(1, 3)
2. S=(4)
9
Chương 4:
Hệ mã hóa khóa công khai
TrapdoorKnapsack
VD: (푎1, 푎2, 푎3, 푎4, 푎5) = (2, 3, 5, 7, 12) và T=12. Hỏi có
bao nhiêu trường hợp nhặt ra trong tập 푎푖 để tổng giá trị
bằng T?
Như vậy ta có 3 đáp số:
1. S = (1, 2, 4)
2. S = (3, 4)
3. S = (5)
10
Chương 4:
Hệ mã hóa khóa công khai
TrapdoorKnapsack
Từ bài toá n đóng thùng này chúng ta sẽ khảo sá t cá c khả năng
vận dụng để tạo ra thuật toá n mã hoá PKC. Sơ đồ đầu tiên như
sau:
o Chọn một vector a = (푎1, 푎2, … , 푎푛) – được gọi là vector mang
(cargo vector)
o Với một khối tin X = (X1, X2, … , X푛) ta thực hiện phé p mã hó a
như sau: T = ∑ 푎푖푋푖 (*)
o Việc giải mã là: Cho mã T, vector mang a, tì m cá c Xi thỏa
mã n (*)
Sơ đồ này thể hiện một hàm one-way với việc sinh mã rất dễ
dàng nhưng việc giải mã là rất khó → cơ sở xâ y dựng một
11
trapdoor
Chương 4:
Hệ mã hóa khóa công khai
TrapdoorKnapsack
• Merkle sử dụng một mẹo là á p dụng một vector mang đặc
biệt là vector siêu tăng (super-increasing).
• Thành phần i+1 là lớn hơn tổng giá trị của cá c thành phần
đứng trước nó (từ 1→ i)
• Việc giải mã có thể diễn ra dễ dàng như ví dụ bằng số sau:
▪ Vector mang siêu tăng: a=(1, 2, 4, 8)
▪ Cho T=11, ta sẽ thấy việc tì m X = (푋1, 푋2, … , 푋푛) sao cho T = ∑푎푖푋푖 là dễ
dàng.
▪ Đặt 푇0= T
▪ 푋4=1
▪ 푋3=0
▪ 푋2=1
▪ 푋1=1
푇 = 푇0-푋4*푎푖=3
푇2 = 푇1 = 3
푇3 = 푇2 - 2 = 1
→ (X1 X2 X3 1)
→ (X1 X2 0 1)
→ (X1 1 0 1)
→ (1 1 0 1)
1
12
Chương 4:
Hệ mã hóa khóa công khai
TrapdoorKnapsack
Bài toá n được giải quyết dần qua cá c bước như sau:
o Ở bước i, tổng đích là T (tức là phải tì m cá c aj để tổng bằng
i
T )
i
o Ta đem so sá nh T với thành phần lớn nhất trong phần cò n lại
i
của vector:
▪ Nếu lớn hơn thì thành phần này được chọn, tức là 푋푖
tương ứng bằng 1
▪ Ngược lại thì 푋푖 tương ứng bằng 0
o Sau đó tiếp tục chuyển sang bước sau với T = T - Xi
i+1
i
Cần chủ động “ngụy trang” vector siêu tăng để chỉ người
13
chủ mới biết cò n người ngoài khô ng thể giải mã được.
Chương 4:
Hệ mã hóa khóa công khai
Hệ PKC Merkle – Hellman: Cơ chế ngụy trang
Tạo khóa
o Alice chọn một vector siêu tăng
a’ = (푎1’, 푎2’, … , 푎푛’)
a’ được giữ bí mật tức là một thành phần của khó a bí mật
Sau đó chọn một số nguyên m > ∑푎푖’, gọi là modulo đồng dư
và một số nguyên ngẫu nhiên ⍵, gọi là nhâ n tử, sao cho
nguyên tố cùng nhau với m (gcd(m, ⍵)=1)
Khó a cô ng khai của Alice sẽ là vector a là tí ch của a’ với nhâ n tử ⍵
a = (푎1, 푎2, … , 푎푛)
ai = ⍵ x ai’ (mod m) với i = 1, 2, 3...n
o Cò n khó a bí mật sẽ là (a’, m, ⍵)
14
Chương 4:
Hệ mã hóa khóa công khai
Mã hó a (sinh mã ):
Khi Bob muốn gửi một thông báo X= {x1, x2, … , x푛} cho Alice, anh ta
tính mã theo công thức:
T = σaixi
Giải mã:
Alice nhận được T và giải mã như sau:
Để bỏ lớp ngụy trang cô ta trước hết tính ⍵−1 (là giá trị
nghịch đảo của ⍵, tức là ⍵.⍵−1= 1 mod m, rồi tính
T’ = T x ⍵−1 (mod m)
Alice biết rằng T’ = a’ . X nên cô ta có thể dễ dàng giải ra được X
theo siêu tăng a’
Chú thí ch: ở đây ta có T’ = T x ⍵−1 = σaiXi⍵−1 = σ ai’⍵Xi⍵−1
15
Chương 4:
Hệ mã hóa khóa công khai
Bài tập:
Cho hệ mã Knapsack có A’ = (2, 3, 6, 12, 25), n=5, m=53, ⍵ =
46, ⍵−1 = 15
a) Hãy tìm các khóa của hệ mã trên
b) Mã hóa và giải mã bản mã tương ứng của bản rõ M = 01001
16
Chương 4:
Hệ mi
Bài giải:
a) Hãy tìm các khóa của hệ mã trên
Khó a cô ng khai
a = (a1, a2, … , a푛) = (2, 3, 6, 12, 25)’ x ⍵
ai = ⍵ x ai’ (mod m) = (39, 32, 11, 22, 37)
Khóa bí mật: (a’, m, ⍵)
b) Mã hóa bản rõ M = 01001
T = ∑푎푖푋푖 = 0*39 + 1*32 + 0*11 + 0*22 + 1*37
= 69 mod 53 = 16
17
Chương 4:
Hệ mã hóa khóa công khai
Bài giải:
Giải mã: với a’=(2, 3, 6, 12, 25), ⍵−1 = 15,
T’ = 16*15 mod 53 = 28
→
X5 = 1
X4 = 0
X3 = 0
X2 = 1
X1 = 0
M = 01001
18
Chương 4:
Hệ mã hóa khóa công khai
Trong trường hợp mã hóa
M = 1 0 1 0 1 0: tự tìm a, a’, m, ⍵, ⍵−1
19
Chương 4:
Hệ mã hóa khóa công khai
Độ an toàn của Trapdoor – Knapsack
Brute Force Attack
⚫ Với những kẻ khô ng biết trapdoor (a’, m, ⍵), giải mã đòi
hỏi phải tì m kiếm vé t cạn qua 2푛 khả năng của X
Sự đổ vỡ của giải phá p dùng Knapsack (1982-1984)
⚫ Shamir – Adleman đã chỉ ra chỗ yếu của giải phá p này
bằng cá ch đi tì m một cặp (⍵’, m’) sao cho nó có thể biến
đổi ngược a về a’ (từ Public key về Private key).
⚫ Năm 1984, Brickell tuyên bố sự đổ vỡ của hệ thống
Knapsack với dung lượng tí nh toá n khoảng 1 giờ má y
Cray -1, với 40 vò ng lặp chí nh và cỡ 100 trọng số.
20
20 trang
30340
Free
Bạn đang xem tài liệu "Bài giảng An toàn và bảo mật dữ liệu trong hệ thống thông tin - Chương 4: Hệ mã hóa khóa công khai PKC - Public Key Cryptosytems - Trương Tấn Khoa", để 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_va_bao_mat_du_lieu_trong_he_thong_thong_ti.pdf
