Chương IV CHỮ KÝ ĐIỆN TỬ CHỮ KÝ

Chương IV CHỮ KÝ ĐIỆN TỬ CHỮ KÝ Скачать презентацию Chương IV CHỮ KÝ ĐIỆN TỬ CHỮ KÝ

af67d209c1d9b8e6373f948bd2bee69f.ppt

• Количество слайдов: 97

Chương IV CHỮ KÝ ĐIỆN TỬ (CHỮ KÝ SỐ) (DIGITAL SIGNATURES) 4

Nội dung chính 1. 2. 3. 4. Khái niệm về chư ky sô (Digital Signature) Ca c di ch vu ba o mâ t cung câ p bơ i chư ky sô Mô t va i chư ky sô thông du ng Mô ta va i ư ng du ng cu a chư ky sô (Cryptography & Network Security. Mc. Graw-Hill, Inc. , 2007. , Chapter 13) 1 -2

Khái niệm về chư ky điện tử • Khái niệm về Digital Signature được để xuất bởi Diffie & Hellman (1976) • “Chữ ký điện tử (còn gọi là chữ ký số) là thông tin được mã hoá bằng Khoá riêng của người gửi, được gửi kèm theo văn bản nhằm đảm bảo cho người nhận định danh, xác thực đúng nguồn gốc và tính toàn vẹn của tài liệu nhận. • Chữ ký điện tử thể hiện văn bản gửi đi là đã được ký bởi chính người sở hữu một Khoá riêng tương ứng với một Chứng chỉ điện tử nào đó. ” • Chữ ký điện tử và chữ ký tay đều có chung đặc điểm là rất khó có thể tìm được hai người có cùng một chữ ký. Chữ ký điện tử được ngườii ký tạo ra bằng Khoá riêng và phần có 1 -3 đặc tính duy nhất của văn bản được ký. ”

Khái niệm về chư ky điện tử • Chữ ký điện tử la mô t trong ư ng du ng quan tro ng nhâ t cu a ma ho a kho a công khai. • Message Authentication chi ba o vê thông điê p trao đô i giư a hai bên tham gia không bi hiệu chi nh hay giả ma o từ bên thứ 3, nhưng no không ba o vê thông điê p bi hiệu chi nh hay giả ma o từ mô t trong 2 bên tham gia, nghi a la : • Bên nhâ n giả ma o thông điê p cu a bên gư i • Bên gư i chô i la đã gư i thông điê p đê n bên nhâ n • Chữ ký điện tử không như ng giu p xa c thư c thông điê p ma co n ba o vê mô i bên kho i bên kia 1 -4

VÍ DỤ CHỮ KÝ SỐ TRONG THỦ TỤC HQĐT Doanh nghiệp nhập tờ khai Hải quan Khai hải quan Ký điện tử Kiểm tra chữ ký điện tử Kiểm tra hiệu lực chữ ký số của DN In tờ khai và làm các quy trình trong thông quan điện tử Trả phản hồi về cho DN Lưu tờ khai và xử lý theo quy trình nghiệp vụ 1 -5

Khái niệm về chư ky điện tử Ví dụ cơ bản: • Mike có hai khóa, một khóa công khai và một khóa riêng. • Mike đưa khóa công khai của mình cho Amanda, nhưng giữ lại khóa riêng cho mình. • Khi muốn chuyển tài liệu cho Amanda, Mike có thể xác nhận (ký) các tài liệu này dùng chính khóa riêng của mình và gửi chúng đến Amanda. • Amanda sau đó sẽ dùng khóa công khai của Mike, để có thể kiểm tra tài liệu mà cô ấy nhận được, thực sự được gửi bởi Mike. 1 -6

Mục tiêu của chư ky điện tử Mục tiêu an toàn • Xác thực (Authentication) • Chống phủ nhận (Non-repudiation) 1 -7

Đặc điểm chư ky sô 1. Đảm bảo tính xác thực • Chứng minh tính hợp pháp của người gửi • Chứng minh tính toàn vẹn của dữ liệu 2. Chữ ký số là hàm của các tham số • Thông báo giao dịch (văn bản gốc) • Thông tin bí mật của người gửi (Khóa riêng của sender) • Thông tin công khai trên mạng (Khóa công khai) • Mã xác thực : Đảm bảo tính toàn vẹn của thông điệp 1 -8

Đặc điểm chư ky sô 1 -9

Nguyên lý ký điện tử trong hệ mật mã công khai 1. Người gởi (chủ nhân văn bản): ký văn bản bằng cách mã hóa nó với khóa bí mật của mình, rồi gởi cho bên nhận. 2. Người nhận tiến hành kiểm tra chữ ký bằng cách sử dụng khóa công khai của người gởi để giải mã văn bản. Nếu giải mã thành công thì văn bản ký là đúng người gởi

Sơ đồ sử dụng chữ ký điện tử 1 -11

Nhận xét • Mô hình ký trên đảm bảo ký tá thông thường hay không? ? ? • Mô hình trên chỉ mang tính nguyên tắc, không khả thi trong thực tiễn.

Hàm băm mật mã • Dùng để chiết xuất đặc trưng của văn bản, đầu ra là một dãy số xác định gọi là mã băm. • Rất “nhạy” đối với các thay đổi trong văn bản. • Có tính kháng xung đột, tính một chiều và tốc độ nhanh.

Hàm băm mật mã Signing the Digest • Ký trên digest cu a thông đê p se ngă n hơn ký trên thông điê p • Ngươ i gư i co thê ký trên cô t thông điê p và ngươ i nhâ n co thê kiê m tra trên cô t thông điê p

Tạo và Kiểm tra chữ ký số 1 -15

Digital Signature Process Tạo và Kiểm tra chữ ký số • Trong mô hình này, Alice sau khi tính giá trị hash HA cho thông điệp M thì sẽ mã hóa HA bằng khóa riêng của Alice để tạo thành chữ ký điện tử DS. Alice gửi kèm DS theo M cho Bob. • Bob dùng khóa công khai của Alice để giải mã chữ ký điện tử DS và có được giá trị hash HA của Alice. • Vì Trudy không có KRA nên không thể sửa được HA. • Ngoài ra, vì Alice là người duy nhất có KRA, nên chỉ có Alice mới có thể tạo DS từ M. Do đó Alice không thể từ chối là đã gửi bản tin. 1 -16

Nhận xét • Chữ ký không phải là nét vẽ ngoằn ngoèo khó bắt chước mà là một dãy số trích từ đặc trưng văn bản đã được mã hóa. • So với chữ ký thông thường, chữ ký số có ưu thế vượt trội hơn chữ ký tay. § Chính xác tuyệt đối § Kiểm định dễ dàng và chính xác “Chữ ký điện tử mở đường cho các dịch vụ có độ tin cậy cao”

Nhược điểm mô hình chữ ký số • Mô hình CKS ở trên chỉ đạt được nếu như mỗi người sở hữu đúng cặp chìa khóa của chính mình. • Có thể xẩy ra hiện tượng “mạo danh” người gởi. Do đó, ta cần có cơ chế để xác định “ai là ai” trên toàn hệ thống. • Giải pháp: chứng minh thư số

Ứng dụng của chữ ký số 1. Xác thực thông điệp (Message Authentication): Người ký được xác nhận là chủ chữ ký. 2. Toàn vẹn thông điệp (Message Integrity): Nội dung chưa bị thay đổi hoặc xa o trô n kê tư khi nó được ký điê n tư. 3. Chống từ chối (Non-repudiation): Chứng minh với tất cả các bên vê nguồn gốc của nội dung đã ký. Tư "thoái thác" dùng để chỉ hành động của một người ký từ chối bất kỳ mối liên kết nào với nội dung đã ký. 4. Bảo mật (Confidentiality)

Nonrepudiation • Nonrepudiation co thê đươ c cung câ p bă ng ca ch du ng mô t trusted Center 1 -20

Confidentiality • Thêm confidentiality va o cơ chê digital signature Một Digital Signature không cung cấp tính bí mật. Nếu cần bảo mật, một lần khác của encryption/decryption được áp dụng 1 -21

Public Notary (công chứng) • Trong trường hợp bên Alice cố cãi rằng cô ta chẳng may làm thất lạc hay vô tình đánh lộ z. A và bị một kẻ thứ ba lợi dụng chứ không có ý định tạo ra văn bản có chữ ký như thế khi đó có thể thêm trọng tài vào hệ thống. • Người trọng tài này cũng còn gọi là công chứng viên (public notary) sẽ ký đè lên chữ ký của Alice để chứng thực, Alice không thể nào chối cãi. 1 -22

Proof of delivery (xác nhận giao hàng - hoá đơn) • Ngược lại, bên gửi cũng cần được bảo vệ để chống lại hiện tượng người nhận có nhận được thông báo nhưng chối là chưa nhận được. • Điều này có thể thực hiện được qua những giao thức có phân xử (adjudicated protocol), tức là những giao thức mà sau đó cho phép người thứ ba có thể kiểm định lại được. 1 -23

Tâ n công trên Digital Signature • Ca c loa i tâ n công trên Digital Signature (Attack Types) • Giả ma o chữ ký (Forgery) 1 -24

Attack Types • Key-Only Attack • Known-Message Attack • Chosen-Message Attack 1 -25

Forgery Types • Existential Forgery • Selective Forgery 1 -26

Vài chữ ký số thông dụng • RSA Digital Signature Scheme • El. Gamal Digital Signature Scheme • Schnorr Digital Signature Scheme • Digital Signature Standard (DSS) • Elliptic Curve Digital Signature Scheme 1 -27

RSA Digital Signature Scheme • Ý tưởng mật mã RSA được dùng cho việc ký và kiểm tra chữ ký, nó được gọi là cơ chế chữ ký số RSA • Người gửi dùng private key của chính mình để ký vào tài liệu; người nhận dùng public key của người gửi để kiểm tra chữ ký • So với chữ ký truyền thống, private key đóng vai trò là chữ ký của chính người gửi, public key của người gửi đóng vài trò là bản sao của chữ ký mà có thể được công khai 1 -28

RSA Digital Signature Scheme • Ý tưởng tổng quát của cơ chế chữ ký RSA 1 -29

RSA Digital Signature Scheme Phát sinh khóa (Key Generation) • Phát sinh khóa trong cơ chế chữ ký RSA là hoàn toàn giống như phát sinh khóa RSA • Trong đó d là bí mật, e và n là công khai 1 -30

RSA Digital Signature Scheme 1) Tạo cặp khóa (bí mật, công khai) (a, b): • Chọn 2 số nguyên tố p, q, xác định n = p * q, n là công khai, đặt P = A = Zn và định nghĩa: • Tính (n) = (p-1). (q-1). • Chọn khóa công khai e < (n), nguyên tố cùng nhau với (n). • Khóa bí mật d là phần tử nghịch đảo của e theo mod (n): e*d 1 (mod (n). • Tập cặp khóa (bí mật, công khai) K = (e, d)/ e, d Zn , e*d 1 (mod (n)). 2) Ký số: Chữ ký trên M P là S = sigk (M) = Md (mod n), S A 3). Kiểm tra chữ ký: verk(M, S) = TRUE M Se (mod n) với M, S Zn. 1 -31

RSA Digital Signature Scheme Tạo và Thẩm tra chữ ký 1 -32

RSA Digital Signature Scheme Ví dụ: Phát sinh khóa: • Alice chọn p = 823 và q = 953, và tính n = 784319. • Giá trị (n) là 782544 • Alice chọn e = 313 và tính d = 160009 Alice muốn ký và gửi thông điệp M=19070 cho Bob • Tạo chữ ký: S=(19070160009) mod 784319 = 210625 mod 784319 • Gửi (M, S) cho Bob • Bob nhận (M, S) và tính M’ M’=210625313 mod 784319 = 19070 mod 784319 • M M’ mod n 1 -33

EXAMPLE Chữ ký trên m = 2 *Tạo cặp khóa (bí mật, công khai) : Chọn 2 số nguyên tố: p=3, q=5 n = p*q = 3*5 = 15(công khai) Đặt P = A = Zn . Tính (n) = (p-1). (q-1) = 2 * 4 = 8. Chọn khóa công khai e = 3 < (n), nguyên tố với (n) = 8. =>Tìm d: là phần tử nghịch đảo của e theo mod (n): e*d 1 (mod (n)). Bước i N b Ri+1 Qi+1 Xi Xi+1 Xi+2 0 8 3 2 2 0 1 -2 1 3 2 1 1 1 -2 3 2 2 1 0 1 -2 3 -5 Vậy khóa bí mật a = 3

EXAMPLE * Ký số: Chữ ký trên M = 2 P là: S = sigk (M) = Md (mod n) = 23 (mod 15) = 8, S A. * Kiểm tra chữ ký: verk(M, S) = TRUE M Se (mod n) 2 83 (mod 15).

BÀI TẬP Sử dụng cơ chế chữ ký RSA cho các bài toán sau: 1) Cho p=5, q=11, e=7. Tạo và kiểm tra chữ ký điện tử với bản tin M=5 D=23, S =15 1) Cho p=7, q=11, e=17. Tạo và kiểm tra chữ ký điện tử với bản tin M=3 D=53, s=5

ĐỘ AN TOÀN CỦA CHỮ KÝ RSA Bài toán căn bảo đảm độ an toàn của Sơ đồ chữ ký RSA: a) Ký trước, Mã hóa sau: • T ký trước vào x bằng chữ ký S = sigk(M), sau đó mã hoá x và y nhận được z = e. T(M, S). T gửi z cho N. • Nhận được z, N giải mã z để được M, S. • Tiếp theo kiểm tra chữ ký ver. N(M, S) = true ? b) Mã hóa trước, Ký sau: • • T mã hoá trước M bằng u = e. T (M), sau đó ký vào u bằng chữ ký v = sig. T(u). T gửi (u, v) cho N. Nhận được (u, v), N giải mã u được M. Tiếp theo kiểm tra chữ ký ver. N(u, v) = true ?

Chữ ký RSA trên Message Digest 1 -38

Chữ ký RSA trên Message Digest Lưu ý: • Khi cốt thông điệp được ký thay cho thông điệp của nó, thì độ nhạy cảm của chữ ký số RSA tùy thuộc vào sức mạnh của hàm băm 1 -39

El. Gamal Digital Signature Scheme • Ý tưởng tổng quát của chữ ký El. Gamal 1 -40

El. Gamal Digital Signature Scheme Phát sinh khóa (Key Generation) • Phát sinh khóa trong cơ chế chữ ký El. Gamal là hoàn toàn giống như phát sinh khóa mật mã El. Gamal • Trong đó (e 1, e 2, p) là public key; d là private key 1 -41

El. Gamal Digital Signature Scheme Tạo chữ ký • • Chọn ngẫu nhiên r, 1 r p-1, gcd(r, p-1)=1 Tính S 1 = e 1 k mod p Tính S 2 = (M-d x S 1) x r-1 mod (p-1), với r-1 là nghịch đảo nhân của r modulo n Chữ ký là (S 1, S 2) Thẩm tra chữ ký • • Kiểm tra 1 S 1 p; 1 S 2 p-1; Tính v 1 = e 1 M mod p Tính v 2= e 2 S 1 x S 1 S 2 mod p Chữ ký hợp lệ v 1=v 2 1 -42

El. Gamal Digital Signature Scheme Tạo và Thẩm tra chữ ký 1 -43

El. Gamal Digital Signature Scheme Một số vấn đề • Giá trị r phải phân biệt cho mỗi thông điệp được ký • (S 1 -S 2)r = (h(m 1)-h(m 2))mod (p-1) • Nếu gcd((S 1 -S 2), p-1)=1 thì có thể dễ dàng xác đinh giá trị r, từ đó có được private key a • Nếu không dùng hàm băm thì có thể bị tình trạng existential forgery 1 -44

HỆ CHỮ KÝ ELGAMMAL 1) Tạo cặp khóa (bí mật, công khai) (a, k) : • Chọn phần tử nguyên tử α Zp*. Đặt P = Z p*, A = Z p* x Z p-1. • Chọn khóa bí mật là a Zp*. Tính khóa công khai β α a mod p. • Định nghĩa tập khóa: = {(p, α, a, β): β α a mod p}. • Các giá trị p, α, β được công khai, phải giữ bí mật a.

HỆ CHỮ KÝ ELGAMMAL 2) Ký số: • Dùng 2 khóa ký: khóa a và số ngẫu nhiên k Zp-1*. • (Vì k Zp-1* , nên nguyên tố cùng p -1, do đó tồn tại k-1 mod (p -1) ). • Chữ ký trên x P là y = sigk(x, k) = ( , ), y A (E 1) Trong đó Z p*, Zp-1: = α k mod p và = (x – a * ) * k-1 mod (p -1) 3) Kiểm tra chữ ký: verk (x, , ) = TRUE β * α x mod p. (E 2)

EXAMPLE Chữ ký Elgamal trên dữ liệu x = 112. 1) Tạo cặp khóa (bí mật, công khai) (a, β) : • Chọn số nguyên tố p = 463. Đặt P = Z p*, A = Z p* x Z p-1. • Chọn phần tử nguyên tử α = 2 Zp*. • Chọn khóa bí mật là a = 211 Zp*. • Tính khóa công khai β α a mod p = 2211 mod 463 = 249. • Định nghĩa tập khóa: = {(p, α, a, β): β α a mod p}. • Các giá trị p, α, β được công khai, phải giữ bí mật a.

EXAMPLE Tính β α a mod p = 2211 mod 463 = 249. i e[i]= 21110 p=p*p p=p mod 463 p= p*2 p= p mod 463 0 1 2 3 4 5 6 7 1 1 0 0 1 1 1 4 64 392 255 205 356 1 4 64 642 3212 2552 2052 2472 2 8 784 710 712 2 8 64 321 255 205 247 249

EXAMPLE 2) Ký số: Chọn ngẫu nhiên bí mật • k= 235 Zp-1*. Khóa ký là (a, k ). • Vì k Zp-1* nguyên tố cùng p -1, Ǝ k-1 mod (p -1). • Cụ thể: ƯCLN(k, p-1) = ƯCLN(235, 462) = 1, nên k-1 mod (p -1) = 235 -1 mod 462 = 289. • Chữ ký trên dữ liệu x = 112 là ( , ) = (16, 108), trong đó: = α k mod p = 2235 mod 463 = 16 = (x – a* )*k-1 mod (p -1) =(112 - 211*16)*289 mod 462 = 108

EXAMPLE k-1 mod (p-1) = 235 -1 mod 462 = 289. Bước i N b Ri+1 Qi+1 Xi Xi+1 Xi+2 0 1 2 3 4 5 462 235 227 8 3 2 1 0 1 1 28 2 1 1 0 1 -1 2 -57 116 -173 289

EXAMPLE Tính = α k mod p = 2235 mod 463 = 16. i e[i]= 23510 p=p*p p=p mod 463 p= p*2 p= p mod 463 0 1 2 3 4 5 6 7 1 1 1 0 1 1 1 4 64 179 94 156 260 8 1 4 64 1282 1792 1882 1562 572 2 8 128 188 520 16 2 8 128 179 188 156 57 16

EXAMPLE 3) Kiểm tra chữ ký: verk (x, , ) = đúng β * α x mod p. β * = 24916 * 16 108 mod 463 = 132 α x mod p = 2112 mod 463 = 132. Hai giá trị đó bằng nhau, như vậy chữ ký là đúng.

ĐỘ AN TOÀN CỦA HỆ CHỮ KÝ ELGAMAL * Bài toán căn bảo đảm độ an toàn của Sơ đồ chữ ký Elgammal: 1). TH 1: Giả mạo chữ ký cùng với tài liệu được ký. • T có thể ký trên tài liệu ngẫu nhiên bằng cách chọn trước đồng thời x, , . • Chọn x, , thoả mãn điều kiện kiểm thử như sau: • Chọn các số nguyên i, j sao cho 0 i, j p-2, GCD(j, p-1) = 1 và tính: • = α i β j mod p • = - j -1 mod (p -1) • x = - ij -1 mod (p -1). • Chứng minh ( , ) là chữ ký trên x, bằng cách kiểm tra điều kiện kiểm thử: • β * β αi β j( αi β j ) αi β j j -1 mod p α x mod p

EXAMPLE • • • Chọn các tham số của sơ đồ chữ ký Elgammal: Chọn p = 463, phần tử sinh α = 2, Khóa bí mật a = 135. Khóa công khai β = α a mod p = 2 135 mod 463 = 272. Chọn x, , thoả mãn điều kiện kiểm thử như sau: Chọn i = 89, j = 125, 0 i, j p-2, gcd(j, p-1) = 1. Tính j -1 mod (p-1) = 377. = α i * β j mod p = 289 * 272125 mod 463 = 218 = – * j -1 mod (p -1) = -218 * 377 mod 462 = 50 x = - * i * j -1 mod (p -1) = -218 * 89 * 377 mod 462 = 292 • ( , ) = (218, 50) là chữ ký trên x = 292, vì TM Đkiện kiểm

ĐỘ AN TOÀN CỦA HỆ CHỮ KÝ ELGAMAL 2) TH 2: Sử dụng lại chữ ký của bức điện trước đó • Nếu ( , ) là chữ ký trên tài liệu x có từ trước, thì có thể giả mạo chữ ký trên tài liệu x’ khác. • Chọn số nguyên k, i, j thỏa mãn 0 k, i, j p-2, (k – j , p-1) = 1 và tính: = h α i β j mod p = (h – j ) -1 mod (p -1), x’ = (hx + i ) (h – j ) -1 mod (p -1) • ( , ) là chữ ký trên x’, vì thỏa mãn điều kiện kiểm thử: β * α x' mod p.

TÓM LẠI Cả hai cách giả mạo nói trên đều cho chữ ký đúng trên tài liệu tương ứng, nhưng đó không phải là tài liệu được chọn theo ý của người giả mạo. Tài liệu đó đều được tính sau khi tính chữ ký, vì vậy giả mạo loại này trong thực tế cũng không có ý nghĩa nhiều.

Schnorr Digital Signature Scheme • Với chữ ký El. Gamal thì p cần phải rất lớn thì mới đảm bảo bài toán logaric rời rạc là khó thực hiện trong Z*p. Theo khuyến cáo p phải ít nhất 1024 -bit chữ ký là 2048 -bit. • Để giảm kích cỡ của chữ ký, Schnorr đề xuất một cơ chế chữ ký mới dựa trên El. Gamal nhưng với một kích cỡ chữ ký được giảm. 1 -57

Schnorr Digital Signature Scheme Ý tưởng tổng quát của chữ ký Schnorr 1 -58

Schnorr Digital Signature Scheme Phát sinh khóa 1. Chọn một số nguyên tố p, thường chọn p có độ lớn 1024 -bit 2. Chọn số nguyên tố q 3. Alice chọn e 1 sao cho e 1 p = 1 mod p. 4. Chọn 1 số nguyên d, làm private key 5. Tính e 2= e 1 d mod p. 6. Public key là (e 1, e 2, p, q); private key là d 1 -59

Schnorr Digital Signature Scheme Tạo và Thẩm tra chữ ký 1 -60

THUẬT TOÁN CKĐT DSA & CHUẨN CKĐT DSS • Thuật toán CKĐT DSA là thuật toán được đề nghị trong chuẩn chữ ký điện tử DSS (Digital Signature Standard) của NIST. • Nó cung cấp một trình tự để tạo và xác nhận CKĐT • DSA sử dụng 1 cặp khóa công khai – khóa riêng. Trong cả giai đoạn ký và xác nhận văn bản được ký thể hiện dưới dạng thông điệp rút gọn là kết quả của việc áp dụng hàm băm SHA-1 lên văn bản cần ký.

Digital Signature Process Tạo và Kiểm tra chữ ký số 1 -62

THUẬT TOÁN CKĐT DSA & CHUẨN CKĐT DSS 1, Tạo khoá • Chọn p là số nguyên tố L bit, sao cho 2 L-1