Mô tả:
BẢO MẬT THÔNG TIN
BÀI 4:
MÃ HÓA CÔNG KHAI
Nguyễn Hữu Thể
1
Nội dung
Lý thuyết số học
Mã hóa công khai
Mã hóa RSA
Demo giải thuật RSA
2
Lý thuyết số học
Phép chia modulo
Ước số
Số nguyên tố
Số nguyên tố cùng nhau
Phần tử nghịch đảo của phép chia modulo
Ước chung lớn nhất
3
Phép chia modulo
4
Ước số, số nguyên tố, số nguyên tố cùng nhau
5
Phần tử nghịch đảo của phép chia modulo
6
Ước chung lớn nhất - Thuật toán Euclid
7
Mã hóa khóa công khai
Mã hóa khóa công khai (public key cryptography)
Còn gọi là mã hóa bất đối xứng (asymetric cryptography).
Whitfield Diffie và Martin Hellman đã đề xuất 1976
Bước đột phá quan trọng trong lĩnh vực mã hóa.
8
Mã hóa khóa công khai
Sử dụng hai loại khóa trong cùng một cặp khóa:
Khóa công khai (public key) được công bố rộng rãi => dùng
mã hóa thông tin.
Khóa riêng (private key) => dùng giải mã thông tin đã được
mã hóa bằng khóa công khai.
9
Mã hóa khóa công khai
10
RSA
Là phương pháp mã hóa khóa công khai.
Ron Rivest, Adi Shamir và Len Adleman tại học viện MIT đề
xuất năm 1977.
Hiện nay đang được sử dụng rộng rãi.
11
RSA
Giải thuật RSA thao tác trên các khối (blocks) trong đó bản rõ
(plaintext) và bản mã (ciphertext) được chia ra thành nhiều
khối, mỗi khối là một số nguyên trong khoảng từ 0 đến n– 1.
Để tăng tính bảo mật, n thường được chọn khá lớn.
n càng lớn thời gian để mã hóa và giải mã càng lớn.
Kích thước của n thường là 1024 bits hay 309 chữ số trong
hệ thập phân
12
Mô tả giải thuật RSA
Bản rõ được chia thành từng khối để mã hóa, mỗi khối có giá
trị nhỏ hơn n.
Kích thước các khối phải nhỏ hơn hoặc bằng log2(n); trong thực
tế mỗi khối có kích thước k bits, với 2k< n ≤2k+1
Với một khối M của bản rõ, khối C của bản mã (tương ứng với
khối M) được tính như sau:
và để giải mã khối C, ta sử dụng công thức:
13
Mô tả giải thuật RSA
Cả người gởi và người nhận đều phải biết n.
Người gởi (có nhiệm vụ mã hóa bản rõ) biết giá trị của e, và chỉ
có người nhận mới biết giá trị của d.
Khóa công khai (public key) KU={e, n}
Khóa bí mật (private key) KR = {d, n}
14
Giải thuật RSA
15
Giải thuật RSA
Giả sử người dùng A đã công bố khóa công khai của mình và
người dùng B muốn gởi cho A thông điệp M. B sẽ dùng khóa
công khai của A (gồm 2 số e và n) để mã hóa thông điệp M theo
công thức:
Sau đó B gởi bản mã C cho A. Khi A nhận được C, A sẽ dùng
khóa cá nhân của mình (gồm 2 số d và n) để giải mã:
Như thế A sẽ nhận được bản rõ của thông điệp M mà B muốn
gởi cho anh ta. Vì d được giữ bí mật và chỉ có mình A biết d
nên ngoài A ra không ai có thể giải mã được C.
16
Giải thuật RSA - Ví dụ 1
Sinh khóa: kích thước bit là 3 bit. Chọn 23 < p.q =<23+1
1. Chọn hai số nguyên tố: p= 5, q= 3.
2. Tính n = pq= 5 x 3 = 15
3. Tính hàm Euler ϕ(n) = (p – 1)(q – 1) = 4 × 2 = 8
Chọn e sao cho 1 < e < ϕ(n) và nguyên tố cùng nhau với ϕ(n) = 8;
ta chọn e = 3.
4. Tính d sao cho 1 < d < ϕ(n) và ed ≡ 1 mod ϕ(n).
- Tính được d = 3, vì 3 × 3 mod 8 = 1.
5. Nhận được khóa công khai KU = {e, n} = {3, 15}
6. Khóa bí mật KR = {d, n} = {3, 15}.
Mã hóa: M = 2. Tính: C=M^e mod n = 2^3 mod 15 = 8
Giải mã: M = C^d mod n = 8^3 mod 15 = ((8^2 mod 15)(8 mod 15))mod 15 =
(64 mod 15)(8 mod 16) mod 15 = 4 * 8 mod 15 = 2
17
Giải thuật RSA - Ví dụ 2
Sinh khóa: kích thước bit là 4 bit. Chọn 24 < p.q =<24+1
1. Chọn hai số nguyên tố: p= 7, q= 3.
2. Tính n = pq= 7 x 3 = 21
3. Tính hàm Euler ϕ(n) = (p – 1)(q – 1) = 6 × 2 = 12
Chọn e sao cho 1 < e < ϕ(n) và nguyên tố cùng nhau với ϕ(n) = 12;
ta chọn e = 5.
4. Tính d sao cho 1 < d < ϕ(n) và e.d ≡ 1 mod ϕ(n) hay e.d mod ϕ(n) = 1
- Tính được d = 5, vì 5 × 5 mod 12 = 1
5. Nhận được khóa công khai KU = {e, n} = {5, 21}
6. Khóa bí mật KR = {d, n} = {5, 21}.
Mã hóa: M = 2. Tính: C=Me mod n = 25 mod 21 = 11
Giải mã: M = Cd mod n = 115 mod 21 = ((112 mod 21)(112 mod 21) (111 mod
21))mod 21 = ((121 mod 21) (121 mod 21)11) mod 21 = 16x16x11 mod 21 = 2
18
Demo RSA
Số nguyên rất nhỏ
19
Demo RSA – Số nguyên rất nhỏ
int[] sinhKhoaRSA(){
//Chọn 2 số nguyên tố p, q. Có thể viết hàm phát sinh ngẫu
nhiên SNT
int p = 3, q = 5;
int n, e, d, phi;
int a[] = new int[3];
n = p*q;
phi = (p-1)*(q-1);
e = timSNTCungNhau(phi);
d = timNghichDaoModulo(e, phi);
a[0] = n;
a[1] = e;
a[2] = d;
return a; //trả về mảng lưu các khóa n, e, d
}
- Xem thêm -