Chương CHỮ KÝ ĐIỆN TỬ & ỨNG DỤNG • Bài tốn xác thực sơ đồ CKĐT • Sơ đồ CK RSA • Sơ đồ CK Elgamal chuẩn CK số • Hàm băm CKĐT • CKĐT thương mại ĐT (Tự học) 4.1 Bài toán xác thực … Khi chuyển sang cách thức truyền tin phương tiện đại, thông báo truyền mạng truyền tin số hoá, thân thơng báo biểu diễn dạng số hố, tức dạng dãy bit nhị phân, “chữ ký” có dạng dãy bit, mối quan hệ tự nhiên kể khơng cịn giữ Chẳng hạn, “chữ ký” người gửi văn khác phải thể gắn kết trách nhiệm người gửi văn tất yếu phải khác đoạn bit giống chữ ký giống văn thơng thường Chữ ký viết tay kiểm thử cách so sánh với nguyên mẫu, “chữ ký” điện tử khơng thể có “ngun mẫu” so sánh, việc kiểm thử phải thực thuật toán đặc biệt Một vấn đề việc chép văn chữ ký Nếu văn chữ ký viết tay dễ phân biệt gốc với sao, khó mà dùng lại văn có chữ ký thật Còn với văn điện tử chữ ký điện tử nhân chép tuỳ thích, khó mà phân biệt gốc với sao, nguy dùng lại nhiều lần có thực, cần có biện pháp để tránh nguy 4.1 Bài tốn xác thực … Định nghĩa Một sơ đồ chữ kí số ( P, A, K, S, V) thoả mãn: P tập hữu hạn điện A tập hữu hạn chữ kí K khơng gian khố tập hữu hạn khố Với K thuộc K tồn thuật tốn kí sigk  S thuật toán xác minh verk V Mỗi sigk : P  A verk: PA true, false hàm cho điện x P chữ kí y A thoả mãn phương trình True y=sig(x) verk = False y sig(x) Với K K hàm sigk verk hàm thời than đa thức Verk hàm công khai sigk mật 4.2 Sơ đồ CKĐT RSA Sơ đồ chữ ký RSA dựa độ khó tốn phân tích số ngun Blum Sơ đồ mô tả sau: S = (P, A, K, S, V), P = A = Z*n , với n = p*q tích số nguyên tố lớn Để xây dựng hệ thống chữ ký theo sơ đồ RSA ta chọn số e khả đảo theo mod φ(n), sau tìm số d = e-1mod(n) Tập hợp K gồm cặp khoá K =(K’,K''), với K’ = d K” =(n, e) K’ khố bí mật dùng để ký, K” khố cơng khai dùng để kiểm thử chữ ký 4.2 Sơ đồ CKĐT RSA Các thuật toán ký kiểm thử chữ ký xác định sau: + Với thông báo x, chữ ký x là: sigK’ (x) = xd modn =:y + Thuật toán kiểm thử định nghĩa bởi: Ver K” (x, sigK’ (x)) =  x = ye (modn) 4.2 Sơ đồ CKĐT RSA Ví dụ: Cho hệ thống chữ ký điện tử RSA có p = 31, q = 41, e = 271 a) Hãy tìm khóa sơ đồ chữ ký b) Hãy tính chữ ký cho thông điệp x = 110 c) Hãy kiểm tra xem s = 32 có chữ ký văn x = 89 hay không Giải: a) n = p*q = 1271, φ(n) = 1200, d = 271-1 mod 1200 = 31 => K’ = 31, K” = (1271, 271) b) Chữ ký: y = 11031 mod 1271 = 978 c) Kiểm thử: Tính 32271 mod 1271 = 993  89 => s=32 chữ ký văn x=89 4.3 Sơ đồ CKĐT Elgamal  Sơ đồ chữ ký Elgamal  Tính an tồn chữ ký Elgamal  Chuẩn chữ ký số DSS Sơ đồ chữ ký Elgamal Sơ đồ chữ ký ElGamal đề xuất năm 1985, gần đồng thời với sơ đồ hệ mật mã ElGamal, dựa độ khó tốn lơgarit rời rạc Sơ đồ thiết kế đặc biệt cho mục đích ký văn điện tử, mô tả hệ S = (P, A, K, S, V), P = Z*p , A = Z*p x Z*p-1 , với p số nguyên tố lớn Tập hợp K gồm cặp khoá K =(K’,K''), với K’ = a số thuộc Z*p , K” =(p, ,  ),  phần tử nguyên thuỷ theo modp,  =  a modp K’ khố bí mật dùng để ký, K” khố cơng khai dùng để kiểm thử chữ ký Sơ đồ chữ ký Elgamal Các thuật toán ký kiểm thử chữ ký xác định sau: + Với thông báo x, để tạo chữ ký x ta chọn thêm môt số ngẫu nhiên k thuộc Z*p-1 tính sigK’ (x,k) = (  ,  ), với  = k modp  = (x-a  ) k-1 mod(p-1) + Thuật toán kiểm thử định nghĩa bởi: Ver K” (x, (, )) =  β  (modp) = x (modp) Sơ đồ chữ ký Elgamal Thí dụ: Giả sử p = 467,  = 2, a = 127 Khi đó:  = 2127mod467=132 Cho x =100; ta chọn ngẫu nhiên k =213 (Z*466) k-1 mod466 =431 Chữ ký văn x =100 với số ngẫu nhiên k =213 (  ,  ), đó:  =2213mod467=29 =(100-127.29).431 mod466 =51 Để kiểm thử ta tính :   modp = 13229.2951 mod 467 = 189, x mod p = 2100 mod 467 =189, hai giá trị đồng dư với theo mod467, chữ ký xác nhận Mở rộng hàm băm Chú ý p có độ dài biểu diễn nhị phân t bit, tức Zp tập D ={0,1}t , q có độ dài t -1 bit, Zq x Zq tập S ={0,1}m với m = 2(t-1) Hàm băm h định nghĩa xem hàm h : S → D Với mục đích chữ ký, ta muốn có hàm băm h :S → D với D tập từ có số bit hạn chế, S lại tập từ có độ dài tuỳ ý Muốn vậy, ta phải mở rộng hàm băm; định lý sau cho ta khả Giả sử h : {0,1}m → {0,1}t hàm băm không va chạm mạnh thoả mãn m ≥ t+1 (hàm băm mục thoả mãn điều kiện đó) Ta xây dựng hàm băm h* : {0,1}* → {0,1}t sau: Mở rộng hàm băm • Giả sử x  {0,1}*, cắt x thành đoạn độ dài l bit, với l = m-t-1, đoạn cuối chưa đủ l bít bổ sung bít ghi nhớ đoạn cách thêm đoạn cuối xk+1 biểu diễn số bít thêm Như x biểu diễn x1x2 xkxk+1, xi Ỵ{0,1}l với i =1,2, , k+1 Ta định nghĩa hàm h* sau: g1 = h(0t+1 x1) gi+1 = h(gi xi +1), i = 1, , k h*(x) = gk+1 Như vậy, giá trị hàm băm h* từ có độ dài t bit • Người ta đã chứng mính định lý sau đây: Nếu hàm băm h có tính chất khơng va chạm mạnh hàm băm mở rộng h* có tính chất khơng va chạm mạnh Xây dựng hàm băm từ hệ mật • Giả sử (P , C , K , E , D ) hệ mật mã khoá đối xứng mà độ an toàn đã thử nghiệm Để tiện trình bày, ta giả thiết P = C = K = Z2n Nên chọn n lớn, cỡ n ≥ 128 để tránh kiểu “tấn cơng ngày sinh” • Từ hàm lập mật mã E ta xác định hàm f : Z2n x Z2n → Z2n cho với (x ,y) thuộc Z2n x Z2n , giá trị f(x, y) tính theo x, y hàm E • Bây giả sử cho x thuộc Z2* Như mục trên, ta viết x dạng ghép nối liên tiếp k đoạn ký tự, đoạn có n bit : x = x1x2 xk Tiếp đó, ta chọn giá trị ban đầu g0thuộc Z2n , xây dựng tiếp g1, g2, ,gk theo qui tắc gi = f (xi , gi -1) với i =1,2, ,k Xây dựng hàm băm từ hệ mật • Và cuối cùng, ta định nghĩa giá trị hàm băm h (x ) = gk Hàm băm h định nghĩa hàm ánh xạ Z2* vào Z2n • Trong trường hợp chung khơng bảo đảm tính an tồn, người ta đã chứng tỏ an tồn trường hợp hàm f chọn sau: f (x, y) = x  E(y,x), f (x, y) = x  y  E(y,x), f (x, y) = x  E(y,x  y), f (x, y) = x  y  E(y,x  y) ,  phép cộng mod2 cặp bit hai từ có số bit Bài tập chương Bài 4.1: Cho hệ chữ ký điện tử RSA có p = 47, q = 71, e= 19 a) Hãy tìm khóa cho sơ đồ CK (d=339) b) Hãy xác định chữ ký thông điệp x = 688 (y = 2031) c) Hỏi y = 2309 có phải chữ ký văn x = 3156? (Chữ ký đúng) Bài tập chương Bài giải 4.1 d = 339 y = 2031 Bài tập chương Bài 4.2: Cho hệ chữ ký điện tử RSA có p = 17, q = 71, e= 43 a) Hãy tìm khóa cho sơ đồ CK (d=547) b) Hãy xác định chữ ký thông điệp x = 327 (y=1067) c) Hỏi y = 2309 có phải chữ ký văn x = 2104? (605 # x => không) Bài tập chương Bài 4.2: Cho hệ chữ ký điện tử RSA có p = 47, q = 71, e= 79 Hãy xác định chữ ký thông điệp x = 688 Giải: n = p*q = 47*71 = 3337, j(n) = (p-1)(q-1) = 3220, d = 79-1 mod 3220 = 1019 => K’ = 1019, K” = (3337, 79) Chữ ký: y = 6881019 mod 3337 = 2441 Bài 4.3: Trong hệ thống chữ ký điện tử ElGamma có p = 43, a = 37 a = phần tử ngun thuỷ Z*p a) Hãy tìm khóa hệ chữ ký b) Để ký lên văn x = 32 người ta chọn k = 11, hãy thực ký đưa chữ ký tương ứng c) Kiểm tra cặp (21, 7) có chữ ký lên văn x = 27 hay không Bài tập chương Bài 4.3: Trong hệ thống chữ ký điện tử ElGamma có p = 43, a = 37 α = phần tử nguyên thuỷ Z*p a) Hãy tìm khóa hệ chữ ký b) Để ký lên văn x = 32 người ta chọn k = 11, hãy thực ký đưa chữ ký tương ứng c) Kiểm tra cặp (21, 7) có chữ ký lên văn x = 27 hay không Bài tập chương Giải: a) β = 537 mod 43 = => K’ = 37, K” = (43, 5, 3) b)  = 511 mod43 = 34 k-1 mod (p-1) = 23  = (32-37.34).23 mod42 = 26 => Chữ ký cặp số (34, 26) c) Để kiểm thử ta tính :     mod p  321.217 mod 43 = 42.1 mod 43 =42, α x mod p = 527 mod 43 = 27 ≠ 42 => (21,7) không chữ ký x = 27 Bài tập chương Bài 4.4: Trong hệ thống chữ ký điện tử ElGamma có p = 1019, a = 37 α=191 phần tử nguyên thuỷ Z*p a) Tìm khóa hệ chữ ký b) Để ký lên rõ x = 102 người ta chọn k = 143, hãy thực ký đưa chữ ký tương ứng c) Kiểm tra cặp (251, 507) có chữ ký lên văn x = 127 hay không? Bài tập chương Giải: a) β = 19137 mod 1019 = 766 => K’ = 37, K” = (1019, 191, 766) b) k-1 mod (p-1) = 299 γ = 191143 mod1019 = 892 δ = (102-37.892).299 mod1018 = 254 => Chữ ký cặp số (892, 254) c) Để kiểm thử ta tính : VT= 766251.251507 mod 1019 = 498, VP = 191127 mod 1019 = =>(251,507) không chữ ký 127 Bài tập chương Bài 4.5: Trong hệ thống chữ ký điện tử DSS có q = 13, p = 13*4+1 = 53, a = 10 α = 42 a) Cho biết khóa hệ chữ ký (β=44) b) Để ký lên văn x = 46 người ta chọn k = 11, hãy tìm chữ ký (  = 7, k-1 =6,  = 7) c) Kiểm tra cặp (9, 5) có chữ ký lên văn x = 27 hay không (-1 =8, e1=8 , e2=7, VT=1   Chữ ký giả mạo) Bài tập chương Giải: a) β = 4210 mod 53 = 44 => K’ = 10, K” = (53,13, 42, 44) b) k-1 mod q = γ = (4211 mod53) mod13 = δ = (46+10.7).6 mod13 = => Chữ ký cặp số (7, 7) c) Để kiểm thử ta tính : δ-1 modq = 8, e1 = x.δ-1 modq = 27.8 mod 13 = e2 = γ.δ-1 modq = 9.8 mod 13 =7 (428 447 mod 53) mod 13 = ≠ =>(9,5) không chữ ký x Bài tập chương Bài 4.6: Cho hàm băm Chaum van-Heijst Pfitzmann có p=107 =2, =5 phần tử nguyên thủy Z*p a) Cho biết giá trị t, m, l b) Tìm tóm lược văn x = 10011010101 Giải: a) Do 26 < p < 27, => t=7, m = 2*(t-1) = 12, l = m-t-1 = (hoặc l = t-3) b) Dãy khối bít x sau thêm khối xk+1: (x1, x2, x3, x4) = (1001, 1010, 1010, 0001) g1 = h(000000 | 001001) = 59 mod 107 = 54 = 0110110 g2 = h(011011 | 011010) = 227 * 526 mod 107 = 73 = 1001001 g3 = h(100100 | 111010) = 236 * 558 mod 107 = 64 = 1000000 g4 = h(100000 | 010001) = 232 * 517 mod 107 = 71 = 1000111 Vậy tóm lược cần tìm là: 1000111 ... đặc biệt Một vấn đề việc chép văn chữ ký Nếu văn chữ ký viết tay dễ phân biệt gốc với sao, khó mà dùng lại văn có chữ ký thật Cịn với văn điện tử chữ ký điện tử nhân chép tuỳ thích, khó mà phân... Khả giả mạo chữ ký văn cho trước 3/ Giả mạo chữ ký với văn ký (Xem [1], tr119-121) Chuẩn chữ ký số DSS Chuẩn chữ ký số (DSS) đề xuất từ năm 1991 chấp nhận vào cuối năm 1994 để sử dụng số lĩnh... Chữ ký: y = 11031 mod 1271 = 978 c) Kiểm thử: Tính 32271 mod 1271 = 993  89 => s=32 chữ ký văn x=89 4.3 Sơ đồ CKĐT Elgamal  Sơ đồ chữ ký Elgamal  Tính an tồn chữ ký Elgamal  Chuẩn chữ ký