Bài giảng Hệ thống thông tin - Chương 3 Quản lý khóa mã công khai

BMHTTT 1 NN CHƯƠNG III Quản lý khóa mã công khai BMHTTT 2 NN III.1 Mã khoá công khai „ III.1.1 giới thiệu „ Mã khoá riêng „ Mã khoá riêng còn được gọi là mã khoá đơn hay mật. „ Ở đây chỉ dùng một khoá, dùng chung cả người nhận và người gửi. „ Khi khoá này được dùng, việc trao đổi thông tin về khoá sẽ được thỏa thuận trước. „ Người ta còn gọi đây là mã đối xứng, vì hai đối tác có vai trò như nhau. „ Không bảo vệ người gửi khỏi việc người nhận giả mạo mẩu tin và tuyên bố là nó được gửi bằng người gửi. BMHTTT 3 NN Giới thiệu „ Khoá công khai ra đời vào đầu những năm 1970. Đây là bước tiến quan trọng nhất trong lịch sử 3000 năm mã hoá. „ Ở đây người ta sử dụng 2 khoá: một khoá riêng để giải mã và một khoá công khai để mã hóa. Hai khoá này khác nhau, mã khoá công khai còn được gọi là mã không đối xứng. „ Người ta đã ứng dụng lý thuyết số về hàm số. „ Khoá công khai ra đời hỗ trợ thêm để giải quyết một số bài toán an toàn, chứ không phải thay thế khoá riêng. Cả hai khoá cùng tồn tại, phát triển và bổ sung cho nhau. BMHTTT 4 NN Sơ đồ mã khoá công khai BMHTTT 5 NN III.1.2 Dùng mã khoá công khai „ Phân phối khoá: làm sao có thể phân phối khóa an toàn „ Chữ ký điện tử: làm sao có thể kiểm chứng được rằng mẩu tin gửi đến nguyên vẹn từ đúng người đứng tên gửi. BMHTTT 6 NN III.1.3 Các đặc trưng của khoá công khai „ Không có khả năng tính toán để tìm khoá giải mã nếu chỉ biết thuật toán mã và khoá dùng để mã. „ Có thể dễ dàng mã hoá hoặc giải mã mẩu tin nếu biết khoá tương ứng „ Trong một số sơ đồ: một khoá bất kỳ trong hai khoá có thể dùng để mã, còn khoá kia dùng để giải mã. Chúng có vai trò đối ngược nhau. BMHTTT 7 NN III.1.4 Tính an toàn của khoá công khai „ Khi biết một trong hai khoá và thuật toán mã hoá về nguyên tắc ta có thể dò tìm khoá thứ hai bằng cách tính toán các giá trị liên quan. „ Nếu khoá sử dụng là rất lớn cỡ hơn 512 bit, thì hầu như bài toán tìm khoá thứ hai là không khả thi „ Bài toán dễ là mã/giải mã khi biết khoá và bài toán khó là thám mã khi không biết khoá tương ứng „ Mã công khai thường chậm hơn khá nhiều so với mã đối xứng, nên nó thường được dùng mã những thông tin nhỏ quan trọng. BMHTTT 8 NN V.2 RSA „ RSA là mã công khai được sáng tạo bởi Rivest, Shamir & Adleman ở MIT (Trường Đại học Công nghệ Massachusetts) vào năm 1977. „ RSA là mã công khai được biết đến nhiều nhất và sử dụng rộng rãi nhất hiện nay BMHTTT 9 NN Giải thuật RSA BMHTTT 10 NN Mã và giải mã theo RSA BMHTTT 11 NN Ví dụ 1. Chọn các số nguyên tố: p=17 & q=11. 2. Tính n = pq, n = 17×11=187 3. Tính Ф(n)=(p–1)(q-1)=16×10=160 4. Chọn e: gcd(e,160)=1; Lấy e=7 5. Xác định d: d=e-1 mod 160 và d < 160 6. Giá trị cần tìm là d=23, vì 23×7=161= 1×160+1 7. Khoá công khai KU={7,187} 8. Giữ khoá riêng bí mật KR={23,187} BMHTTT 12 NN An toàn của RSA „ Tấn công vét cạn (Brute force) „ Tấn công toán học (Mathematical attacks): cố gắng phân tích tích của 2 số nguyên tố „ Tấn công tính toán thời gian (Timing attacks) „ Tấn công bản mã (Chosen ciphertext attacks): Khai thác tính chất của giải thuật BMHTTT 13 NN Tấn công vét cạn (Brute force) „ Để phòng chống dùng kích thước khóa lớn „ Việc thực thi phức tạp làm giảm tốc độ thực hiện BMHTTT 14 NN Tấn công toán học „ 3 cách „ Phân tích N = p.q, sau đó tính Ф(N) và d „ Tìm N trực tiếp, Ф(N) và tính d „ Tìm d trực tiếp „ Đề nghị „ p và q phải khác nhau trong độ dài chỉ vài số „ (p1) và (q1) là số nguyên tố lớn „ gcd(p 1, q 1) phải nhỏ BMHTTT 15 NN Tấn công thời gian „ Phát triển vào giữa năm 1990 „ Paul Kocher chỉ ra rằng kẻ thám mã có thể xác định được khoá riêng nếu theo dõi thời gian máy tính cần để giải mã các bản tin. „ Tấn công thời gian không chỉ áp dụng cho RSA, mà cả với các hệ mã công khai khác. „ Tấn công thời gian giống như kẻ cướp đoán số điện thọai bằng cách quan sát một người nào đó trong bao lâu chuyển quay điện thoại từ số này sang số khác. BMHTTT 16 NN PHÒNG CHỐNG TẤN CÔNG THỜI GIAN „ Bảo đảm các số mũ khác nhau không ảnh hưởng nhiều tới thời gian trả về kết quả (giảm tốc độ thực thi) „ Cộng thêm một trì hoãn ngẫu nhiên (Random delay „ Nhân bản mã với 1 số ngẫu nhiên trước khi mũ hóa (Blinding): tránh phân tích bit theo bit (bit by bit) BMHTTT 17 NN Optimal Assymetric Encryption Padding (OAEP) BMHTTT 18 NN III.3 Quản lý khóa V.3.1 Phân phối khóa „ Dùng mã hóa khóa công khai „ Phân phối khoá công khai „ Sử dụng mã khoá công khai để phân phối khoá mật (còn khoá mật dùng để mã hoá thông tin). „ Phân phối khoá công khai: „ Thông báo công khai khóa của người sử dụng. „ Thư mục truy cập công cộng. „ Phân phối khóa công khai từ tổ chức „ Chứng nhận khoá công khai: khoá công khai của người sử dụng được nơi có thẩm quyền chứng nhận. BMHTTT 19 NN Thông báo công khai „ Người dùng phân phối khoá công khai cho người nhận hoặc thông báo rộng rãi cho cộng đồng. „ Điểm yếu chính của thông báo công khai là sự mạo danh. BMHTTT 20 NN Thư mục cho mọi người „ Người có quyền cho phép mỗi người tham gia một đầu vào (tên, khóa) „ Mỗi người tham gia đăng ký một khóa công khai „ Người tham gia có thể thay đổi khóa „ Người tham gia có thể truy cập vào thư mục một cách an toàn Kẻ xâm nhập có thể đoạt được quyền quản trị thư mục BMHTTT 21 NN Phân phối khoá công khai từ tổ chức „ Chặt chẽ được cộng thêm cho thư mục công cộng „ Tất cả phải biết khóa công khai của tổ chức phân phối „ Giới hạn: bottleness BMHTTT 22 NN Chứng nhận khoá công khai „ Giấy chứng nhận giống như CMND, dựa vào một tổ chức thứ 3 (CA, Certificate Authority) „ Chứng nhận chứa: Khóa công khai, một nhận dạng chủ của khóa, thời gian hiệu lực BMHTTT 23 NN Sử dụng mã khoá công khai để phân phối khoá mật „ Các thuật toán khoá công khai chậm, nên giá để bảo mật thông tin là đắt. „ Dùng khoá đối xứng để mã hoá và giải mã nội dung bản tin, mà còn được gọi là khoá phiên hay khóa kỳ (section key). Phân phối khóa đơn giản: dễ bị tấn công man-in-the-middle BMHTTT 24 NN Phân phối khóa cải tiến BMHTTT 25 NN Hệ thống lai „ Các Mainframe của IBM. Trung tâm phân bổ khóa (Key distribution center - KDC): phân bổ khóa chính bí mật, khóa phiên. Lược đồ khóa công cộng dùng để phân phối khóa chính „ Thuận lợi „ Phân bổ khóa phiên bởi public-key encryption cho phép giảm tải, public-key encryption dùng để cập nhật khóa chính giữa người dùng và KDC „ Dễ dàng dùng lại KDC BMHTTT 26 NN III.4 Trao đổi khoá Diffie Hellman „ Trao đổi khoá Diffie Hellman là sơ đồ khoá công khai đầu tiên được đề xuất bởi Diffie và Hellman năm 1976 cùng với khái niệm khoá công khai. „ Sau này được biết đến bởi James Ellis (Anh), người đã đưa ra mô hình tương tự năm 1970. Đây là phương pháp thực tế trao đổi công khai các khoá mật. Nó thúc đẩy việc nghiên cứu đề xuất các mã khoá công khai. Sơ đồ được sử dụng trong nhiều sản phẩm thương mại. BMHTTT 27 NN Khoá Diffie Hellman „ Không thể dùng để trao đổi mẩu tin bất kỳ. „ Tuy nhiên nó có thể thiết lập khoá chung. „ Chỉ có hai đối tác biết đến. „ Giá trị khoá phụ thuộc vào các đối tác (và các thông tin về khoá công khai và khoá riêng của họ). „ Dựa trên phép toán lũy thừa trong trường hữu hạn (modulo theo số nguyên tố hoặc đa thức) là bài toán dễ. „ Độ an toàn dựa trên độ khó của bài toán tính logarit rời rạc (giống bài toán phân tích ra thừa số) là bài toán khó. BMHTTT 28 NN Trao đổi khoá Diffie Hellman „ α căn nguyên tố của mod q: a mod p, a2 mod p,..., ap1 mod p BMHTTT 29 NN Tạo cặp khóa BMHTTT 30 NN Xác định khóa phiên „ Dựa vào số học modulo BMHTTT 31 NN Ví dụ „ Đồng ý chọn số nguyên tố q=353 và α=3 „ Chọn các khoá mật ngẫu nhiên: A chọn xA=97, B chọn xB=233 „ Tính các khoá công khai: „ YA=397 mod 353 = 40 (A) „ YB=3233 mod 353 = 248 (B) „ Tính khoá phiên chung: „ KAB= YBxA mod 353 = 24897 = 160 (A) „ KAB =YAxB mod 353 = 40233 = 160 (B) BMHTTT 32 NN Tấn công „ q = 353; a = 3; YA = 40; YB = 248 „ Vét cạn để tìm 2 khóa bằng nhau (với số nhỏ) „ Không chống được tấn công Man-in-the-Middle BMHTTT 33 NN III.5 Mã đường cong Elip ECC „ Để đảm bảo tính an toàn đa số mã công khai sử dụng số học số nguyên lớn hoặc đa thức với các số nguyên rất lớn hoặc đa thức bậc cao. Do đó buộc phải tải phần quan trọng vào kho nhớ để xử lý khoá và mẩu tin. Làm như vậy vừa tốn bộ nhớ vừa dễ mất an toàn. „ Để khắc phục điều đó mà vẫn đảm bảo độ an toàn của mã công khai, người ta đã đề xuất cách khác là dùng đường cong Elip. Ở đây các phép toán được thực hiện trên các xâu bitcó kích thước nhỏ hơn. BMHTTT 34 NN Mã đường cong Elip „ Bài toán sau đây trong ECC là bài toán khó tương đương với bài toán logarit rời rạc: „ Giả sử cho Q = k.P, trong đó P, Q là 2 điểm của đường cong Elip „ Dễ dàng tính Q, nếu cho trước P, k „ Rất khó tìm k, nếu cho trước P, Q. Bài toán tìm hệ số k chính là bài toán khó bài toán logarit đường cong Elip. BMHTTT 35 NN Mã đường cong Elip „ Có phép cộng đối với đường cong Elip „ Về hình học tổng của P và Q là điểm đối xứng của giao điểm R „ Điểm O đóng vai trò là đơn vị đối với phép cộng và nó là điểm vô cực BMHTTT 36 NN Mã đường cong Elip BMHTTT 37 NN Tạo khóa BMHTTT 38 NN Xác định khóa phiên „ nA x PB = nA x (nB x G) = nB x (nA x G) = nB x PA BMHTTT 39 NN Ví dụ „ p = 211 (modulo); Ep(0, 4), y2 = x3+4; G = (2, 2). „ N=240, 240G = O. „ Khóa riêng của a là nA = 121, khóa công cộng của b là PA = 121(2, 2) = (115, 48). „ Khóa riêng của b là nB = 203, khóa công cộng của b là PB 203(2, 2) = (130, 203). „ Khoa bí mật chia sẻ là: 121(130, 203) = 203(115, 48) = (161, 69). BMHTTT 40 NN An toàn ECC „ Phụ thuộc vào xác định k dựa vào kP và P „ Phương pháp nhanh nhất giải bài toán trên đã biết là “Pollard rho method” „ Có thể dùng khóa ngắn hơn với độ an toàn tương đương so với RSA „ Người ta chứng minh được rằng với độ dài khoá bằng nhau các tính toán nói chung là tương đương