Bài giảng Mật mã ứng dụng: Chữ ký số - Đại học Bách khoa Hà Nội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

8
lượt xem 5
download

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

Bài giảng "Mật mã ứng dụng: Chữ ký số" trình bày các nội dung chính sau đây: Khái niệm và ứng dụng chữ ký số; Các phương pháp xây dựng chữ ký số; Chữ ký RSA; Chữ ký từ bài toán Logarit rời rạc. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Mật mã ứng dụng: Chữ ký số - Đại học Bách khoa Hà Nội

Mật mã ứng dụng Chữ Ký Số
Nội dung 1. Chữ ký số là gì? 2. Ứng dụng 3. Các phương pháp xây dựng 4. Chữ ký RSA 5. Chữ ký từ bài toán Logarit rời rạc
Physical signatures Physicalbindlý Goal: signatures Chữ ký vật document to author document to author Bob agrees to pay Alice 1$ ay Alice 1$ Bob agrees to Bob agrees to pay Alice 100$ Problem in the digital world: digitalVấn đề với chữ anyone can copy Bob’s signature from one • world: ký số: Ai cũng có thể sao chép chữ ký của Bob ở tài liệu này và mang sang tài liệu ne can copy Bob’s signature from one doc to another khác.
Digital signatures Chữ ký số: Digital signatures n: make signature depend on documentsignatures Chữ ký phụ Digital tài liệu thuộc Signer olution: Solution: make signature depend on document make signature depend on document Verifier Signer Signer Bob agrees to pay Alice 1$ ‘accept’ verifierVerifier orVerifier ‘reject’‘accept’ ‘chấp nhận’ ‘a Bob agrees to pay Alice 1$to pay Alice 1$ Bob agrees hoặc or signature verifier Hàm kiểm tra verifier ‘Bác bỏ’ ‘reject’ ‘ signing signature signature Signature algorithm ning public verification signing Thuật toán ký signing Khoá công khai để kiểm k) algorithm key tra (pk) (pk) algorithm cret signing bí mật để ký secret signing Khoá public verification verification Dan Boneh public key (sk) key (sk) (sk) key (pk) key (pk) Dan Boneh
Một ví dụ thực tế A more realistic example A more realistic example A more Digital signatures realistic example ftware vendor dor Khách hàng clients Kiểm clients Solution: make signature depend on document tra sig, Nhà sản suất phần mềm Software vendor càiclients hợp lệ đặt nếu Signerpk pk pk Verifier ‘acce Bob agrees to pay Alice 1$ sig sig software updateuntrusted oftware update verifier or hosting untrusted hosting pk pk ‘reje Cập nhật site mềm site sig untrusted phần software update sig et signing signature lưu Nơi hosting pk ey (sk) signing signing secret signing sitetrữ verify sig, verify sig, algorithm (sk)algorithm key signing không Thuật toáninstall if valid install if valid signing algorithm tin cậy verify sig, secret signing algorithm ký Dan Boneh public verification Dan Boneh key (sk) install if valid key (pk) Dan Boneh Da
Chữ ký số Định nghĩa: Một sơ đồ chữ ký số (Gen, S, V) là một bộ ba thuật toán: • Gen(): thuật toán ngẫu nhiên output ra cặp khoá (pk, sk) • S(sk, m∈M) output ra chữ ký σ • V(pk, m, σ) output ‘chấp nhận’ hoặc ‘bác bỏ’ Tính đúng đắn: với mọi cặp (pk, sk) output bởi Gen : ∀m∈M: V(pk, m, S(sk, m) ) = ‘chấp nhận’
Tính an toàn Khả năng của kẻ tấn công: tấn công chọn bản rõ • với thông điệp m1,m2,...,mq tuỳ chọn kẻ tấn công có σi ← S(sk, mi) Mục đích của kẻ tấn công: Giả mạo thông điệp • đưa ra cặp thông điệp/chữ ký hợp lệ (m, σ) mà m ∉ { m1 , ... , mq } ⇒ kẻ tấn công không tạo ra chữ ký hợp lệ cho thông điệp một mới
Chữ ký an toàn Với sơ đồ chữ ký (Gen, S,V) và kẻ tấn công A ta định nghĩa trò chơi: pk Chal. Adv. m1 Î M m2 , …, mq (pk, sk)¬Gen σ1 ¬ S(k,m1) σ2 , ..., σq (m,σ) Kẻ tấn công thắng nếu V(pk,m,σ) = ‘chấp nhận’ và m ∉ {m1, ... , mq} • Định nghĩa: SS=(Gen, S,V) là an toàn nếu với mọi thuật toán “hiệu quả” A: AdvSIG[A,SS] = Pr[A thắng] là “nhỏ không
Nội dung 1. Chữ ký số là gì? 2. Ứng dụng 3. Các phương pháp xây dựng 4. Chữ ký RSA 5. Chữ ký từ bài toán Logarit rời rạc
Ký trên phần mềm Applications • Công ty bán phần mềm ký lên phần mềm •Code signing: có khoá công khai pk của công ty Khách hàng • phần mềm. Cài đặtcode mềm nếu chữ ký là hợp Software vendor signs phần Clients have vendor’s pk. Install software if signature verifies. • lệ. software vendor many clients initial software install (pk) pk sk [ software udate #1 , sig ] [ software udate #2 , sig ] Dan Boneh
Ứng dụng quan trọng: Chứng chỉ số • Vấn đề: trình duyệt cần khoá công khai của máy chủ để thiết lập khoá phiên Important application: Certificates • Giải pháp: máy chủ yêu cầu bên thứ ba tin cậy (CA) ký Problem: browser needs server’s public-key to setup a session key lên khoá công khaitrusted 3rd party (CA) to sign its public-key pk Solution: server asks pk Certificate browser Gmail.com Authority (CA) choose pk and verification key (pk, sk) proof “I am Gmail” check pkCA pkCA proof skCA Sign Cert using skCA : verify pk is key cert pk is key for Gmail for Gmail CA signing key CA sig sig Server uses Cert for an extended period (e.g. one year) Dan Boneh
Chứng Certificates: example thư số: Ví dụ Certificates: example Important fields: Important fields: Dan Boneh Dan Boneh
Ký email: DKIM (domain key identified mail) Signing email: DKIM (domain key identified mail) Vấn đề: email giả khẳng định gửi từ someuser@gmail.com Problem:thực tế, mail gửi từ badguy.com nhưng bad email claiming to be from someuser@gmail.com ⇒ Làm gmail.com giống như một nguồn gửi email giả but in reality, mail is coming from domain baguy.com ⇒ Incorrectly makes gmail.com look like a bad source of email Giải pháp: gmail.com (và các trang khác) ký mọi email tạo ra Solution: gmail.com (and other sites) sign every outgoing mail From: bob@gmail.com DNS ry email body que pk body sig ail signing key Recipients Gm verify sig Gmail Gmail.com user badguy.com ?? Dan Boneh
Khi nào sử dụng chữ ký số Nói chung: § Nếu một phía ký và một phía kiểm tra : dùng MAC • Phải tương tác để có khoá chia sẻ • Bên nhận có thể sửa đổi dữ liệu và ký lại nó trước khi chuyển dữ liệu tới bên thứ ba § Nếu một bên ký và nhiều bên kiểm tra: dùng chữ ký số • Bên nhận không thể nào sửa dữ liệu nhận được trước khi chuyển dữ liệu tới bên thứ ba (không chối bỏ được)
Ba cách tiếp cận cho toàn vẹn thông điệp 1. Hàm băm kháng xung đột: cần không gian công khai chỉ đọc 2. Chữ ký số: người bán phải quản lý khoá bí mật dùng lâu dài • Chữ ký trên phần mềm kèm với phần mềm • Phần mềm có thể download từ nơi không tin cậy 3. MACs: người bán phải tính một MAC mới cho phần mềm cho mọi khách hàng • Và phải quản lý một khoá bí mật dùng lâu dài (để sinh MAC key cho mỗi khách hàng)
Nội dung 1. Chữ ký số là gì? 2. Ứng dụng 3. Các phương pháp xây dựng 4. Chữ ký RSA 5. Chữ ký từ bài toán Logarit rời rạc
Nhắc lại: Chữ ký số Định nghĩa: Một sơ đồ chữ ký số (Gen, S, V) là một bộ ba thuật toán: • Gen(): thuật toán ngẫu nhiên output ra cặp khoá (pk, sk) • S(sk, m∈M) output ra chữ ký σ • V(pk, m, σ) output ‘chấp nhận’ hoặc ‘bác bỏ’ Tính an toàn: • Khả năng của kẻ tấn công: tấn công chọn bản rõ • Mục đích của kẻ tấn công: giả mạo thông điệp
Sơ đồ Băm và ký Xét Sig=(Gen, S, V) là sơ đồ ký cho các thông điệp ngắn, ví dụ M = {0,1}256 Xét H: Mbig → M là một hàm băm (vd. SHA-256) Định nghĩa: Sigbig = (Gen, Sbig , Vbig ) cho các thông điệp trong Mbig bởi: Sbig(sk, m) = S(sk,H(m)) ; Vbig(pk, m, σ) = V(pk,H(m),σ) Định lý: Nếu Sig là một sơ đồ ký an toàn cho M và H là một hàm băm kháng xung đột, thì Sigbig là một sơ đồ ký an toàn cho Mbig. ⟹ ta chỉ cần xây dựng sơ đồ ký cho các thông điệp ngắn 256-bit
Chữ ký từ Hàm một chiều Nhắc lại: f: X ⟶Y là một hàm một chiều (OWF) nếu: • dễ: với mọi x∈X tính f(x) • Tính nghịch đảo của f là khó. Ví dụ: f(x) = AES(x, 0) khoá Chữ ký từ hàm một chiều: Lamport-Merkle, Rompel • Chữ ký là dài: • Không trạng thái ⇒ > 40KB • Có trạng thái ⇒ > 4KB
Xây dựng chữ ký từ Hoán vị cửa sập Nhắc lại: f: X ⟶X là một hoán vị cửa sập (TDP) nếu: • dễ: với mọi x∈X tính f(x) • Khó tính hàm ngược của f, trừ khi có cửa sập Ví dụ: RSA Chữ ký từ TDP: rất đơn giản và thực tế • Thường được dùng cho ký trong chứng thư số