Bài 4 -Mã hóa công khai

Chia sẻ: Mvnc Bgfhf | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

102
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mật mã hóa khóa công khai là một dạng mật mã hóa cho phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trước đó

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài 4 -Mã hóa công khai

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 =
Giải thuật RSA - Ví dụ 2 Sinh khóa: kích thước bit là 4 bit. Chọn 24 < p.q =
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 }