›

Chuẩn chữ ký số và ứng dụng

pdf 26 trang yendo 6050
Download
Bạn đang xem 20 trang mẫu của tài liệu "Chuẩn chữ ký số và ứng dụng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfchuan_chu_ky_so_va_ung_dung.pdf

Nội dung text: Chuẩn chữ ký số và ứng dụng

  1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG ISO 9001:2000 Tên đề tài CHUẨN CHỮ KÝ SỐ VÀ ỨNG DỤNG Giáo viên hướng dẫn : TS.Lê Phê Đô Sinh viên thực hiện : Nguyễn Đình Lượng Lớp CT702 HẢI PHÒNG - 2007
  2. MỤC ĐÍCH ĐỀ TÀI Nghiên cứu về lý thuyết mật mã, chữ ký điện tử, Chuẩn hàm băm an toàn và Chuẩn chữ ký số.
  3. NỘI DUNG TRÌNH BÀY Giới thiệu về NIST Sơ lược hàm băm Chuẩn hàm băm an toàn Giới thiệu Tiền xử lý Các hàm sử dụng tính toán Quy trình tính toán Chuẩn chữ ký số Giới thiệu Các tham số của DSA Lựa chọn kich thước các tham số Tạo chữ ký số DSA Xác nhận chữ ký số DSA Giải thuật tạo các số nguyên tố p và q Giải thuật xác suất Miller-Rabin kiểm tra tính nguyên tố
  4. Giới thiệu về NIST Viện chuẩn và công nghệ quốc gia NIST (the National Institute of Standards and Technology), được thành lập năm 1901, là một cơ quan quản trị công nghệ của bộ thương mại Hoa Kì. Nhiệm vụ của Viện này là thúc đẩy các đổi mới và nâng cao tính cạnh tranh công nghệ bằng cách đưa ra khoa học đo lường, các chuẩn và công nghệ tiên tiến theo cách làm tăng tính an toàn kinh tế và cải thiện chất lượng cuộc sống.
  5. Sơ lược hàm băm Định nghĩa: Hàm băm là một hàm h có ít nhất hai tính chất sau: Tính chất nén: h sẽ ánh xạ một đầu vào x có độ dài bit hữu hạn tùy ý tới một đầu ra h(x) có độ dài n bit hữu hạn. Tính chất dễ dàng tính toán: Với h cho trước và một đầu vào x, có thể dễ dàng tính được h(x). Hàm băm yếu: • Với y bất kỳ không thể tìm x sao cho h(x) = y. • Với x bất kỳ không thể tím x’ sao cho h(x’) = h(x). Hàm băm mạnh: • Với x bất kỳ không thể tím x’ sao cho h(x’) = h(x). • Không thể tìm x ≠ x’ sao cho h(x) = h(x’).
  6. Chuẩn hàm băm an toàn (SHS) Giới thiệu: Chuẩn hàm băm an toàn SHS (Secure Hash Standard) được NIST đưa ra lần đầu vào 11/5/1993 với phiên bản đầu là FIPS PUB 180-1. Và phiên bản thứ2 là FIPS PUB 180-2, được đưa ra vào ngày 1/8/2002. Trong FIPS PUB 180-2 có 4 giải thuật hàm băm được đua ra là SHA-1, SHA-256, SHA-384, SHA-512. Bảng 1. Đặc điểm của các giải thuật hàm băm an toàn.
  7. Chuẩn hàm băm an toàn (SHS) Tiền xử lý: Độn bản tin Giải sử thông điệp M có độ dài là l bit - Với SHA-1 và SHA-256 Biểu diễn nhị phân của M 1 00 00 Biểu diễn nhị phân của l l bit k bit 64 bit l +1+k ≡ 448 mod 512 - Với SHA-384 và SHA-512 Biểu diễn nhị phân của M 1 00 00 Biểu diễn nhị phân của l l bit k bit 128 bit l +1+k ≡ 896 mod 512
  8. Chuẩn hàm băm an toàn (SHS) Tiền xử lý: Phân phối bản tin độn - Với SHA-1 và SHA-256 Bản tin độn sẽ được phân ra thành N khối 512 bít: M(1), (2) (N) (i) (i) M , , M . Mỗi khối tin M biểu diễn 16 từ-32 bít: M0 , (i) (i) M1 , , M15 . - Với SHA-384 và SHA-512 Bản tin độn được phân ra thành N khối 1024 bít. M(1), M(2), , M(N). Mỗi khối tin M(i) có độ lớn 1024 bít có thể biểu (i) (i) (i) diễn thánh 16 từ-64 bít M0 , M1 , , M15 .
  9. Chuẩn hàm băm an toàn (SHS) Các hàm sử dụng tính toán SHA-1: Ch(x, y, z) (x  y)  ( x  z ) 0 t 19 Parity(x, y, z) x  y  z 20 t 39 ft (x, y, z) = Maj(x, y, z) (x  y)  (y  z)  (z  x) 40 t 59 Parity(x, y, z) x  y  z 60 t 79 SHA-256 Ch( x, y, z) = ( x y) ( x  z) Maj( x, y, z) = ( x y) ( x  z)  ( y z) 256 256 ROTR2 (x) ROTR13(x)  ROTR22(x) ROTR6 (x) ROTR11(x)  ROTR25(x)  0 và 1 256 7 18 3 256 17 19 10  0 ROTR (x)  ROTR (x) ROTR (x) và 1 ROTR (x)  ROTR (x)  ROTR (x) SHA-348 và 512 Ch( x, y, z) = ( x y) ( x z) Maj( x, y, z) = ( x y) ( x z) ( y z) 512 512 ROTR 28(x) ROTR 34(x)  ROTR39(x ) và ROTR14(x) ROTR18(x)  ROTR41(x) 0 1 512 1 8 7 512 19 61 6  0 ROTR (x)  ROTR (x)  ROTR (x ) và 1 ROTR (x)  ROTR (x)  ROTR (x)
  10. Chuẩn hàm băm an toàn (SHS) Quy trình tính toán 1 SHA-1: t=0 BEGIN t=t+1 M, H(0), K, N T = ROTL5(a) + ft(b, c, d) +e + Kt + Wt; e = d ; d = c; c = ROTL30(b); b = a; a = T i=1 i=i+1 2 Đúng t ≤ 79 i M t 0 t 15 Sai Wt (i) (i-1) (i) (i-1) H0 = a + H0 ; H1 = b + H1 ; ROTL 1(W W W ) 16 t 79 (i) (i-1) (i) (i-1) t 3 t 8 t 16 H2 = c + H2 ; H3 = d + H3 ; (i) (i-1) H4 = e + H4 (i-1) (i-1) (i-1) a = H0 ; b = H1 ; c = H2 ; Đúng d = H (i-1); e = H (i-1) 2 i ≤ N 3 4 Sai In H (N) || || H (N) 1 0 4 END
  11. Chuẩn hàm băm an toàn (SHS) Quy trình tính toán 1 SHA-256: t=0 BEGIN t=t+1 256 (e) {256} T1 = h +  1 + Ch(e, f, g) + Kt + Wt; (0) 256 M, H , K, N (e) {256} T2 =  0 + Ch(e, f, g) + Kt + Wt; h = g; g = f; f = e; e = d + T1; d = c; i=1 c = b; b = a; a = T + T i=i+1 1 2 2 Đúng i t ≤ 79 M t (0 t 15) Sai Wt (i) (i-1) (i) (i-1) H0 = a + H0 ;H1 = b + H1 256 256  (W ) W  (W ) W (16 t 79) (i) (i-1) (i) (i-1) 1 t 2 t 7 0 t 15 t 16 H2 = c + H2 ;H3 = d + H3 (i) (i-1) (i) (i-1) H4 = e + H4 ;H5 = g + H5 (i) (i-1) (i) (i-1) (i-1) (i-1) (i-1) H6 = f + H6 ;H7 = h + H7 a = H0 ; b = H1 ; c = H2 ; (i-1) (i-1) (i-1) d = H3 ; e = H4 ; f = H5 ; Đúng (i-1) (i-1) 2 i ≤ N g = H6 ; h = H7 Sai (N) (N) 1 In H0 || || H7 END
  12. Chuẩn hàm băm an toàn (SHS) Quy trình tính toán 1 SHA-512: t=0 BEGIN t=t+1 512 (e) {512} T1 = h +  1 + Ch(e, f, g) + Kt + Wt; (0) 512 M, H , K, N (e) {512} T2 = h +  0 + Ch(e, f, g) + Kt + Wt; h = g; g = f; f = e; e = d + T1; d = c; i=1 c = b; b = a; a = T + T i=i+1 1 2 2 Đúng i t ≤ 79 M t (0 t 15) Sai Wt (i) (i-1) (i) (i-1) H0 = a + H0 ;H1 = b + H1 512 512  (W ) W  (W ) W (16 t 79) (i) (i-1) (i) (i-1) 1 t 2 t 7 0 t 15 t 16 H2 = c + H2 ;H3 = d + H3 (i) (i-1) (i) (i-1) H4 = e + H4 ;H5 = g + H5 (i) (i-1) (i) (i-1) (i-1) (i-1) (i-1) H6 = f + H6 ;H7 = h + H7 a = H0 ; b = H1 ; c = H2 ; (i-1) (i-1) (i-1) d = H3 ; e = H4 ; f = H5 ; Đúng (i-1) (i-1) 2 i ≤ N g = H6 ; h = H7 Sai (N) (N) 1 In H0 || || H7 END
  13. Chuẩn hàm băm an toàn (SHS) Quy trình tính toán SHA-348: Giải thuật này được định nghĩa giống y hệt với giải thuật SHA- 512 trừ hai điểm khác biệt duy nhất sau: - Giá trị băm khởi tạo H(0) của SHA-384 khác với giá trị khởi tạo H(0) của SHA-512. (N) (N) (N) - Thông điệp rút gọn của SHA-384 là: H0 || H1 || H2 || (N) (N) (N) H3 || H4 || H5 thay vì là giữ nguyên toàn bộ tất cả các bit của H(N) như SHA-512.
  14. Chuẩn chữ ký số (DSS) Giới thiệu Để nâng cấp việc sử dụng thương mại điện tử của quốc gia và trong việc giao dịch, Viện tiêu chuẩn và công nghệ quốc gia Hoa kỳ (NIST) đã đưa ra chuẩn xử lý thông tin FIPS 186 là chuẩn chữ ký số (DSS - Digital Signature Standard) vào ngày 19/5/1994 và được chấp nhận từ ngày 1/12/1994. Phiên bản đầu tiên của chuẩn chữ ký số là FIPS PUB 186, phiên bản tiếp theo là FIPS PUB 186-1 được đưa ra vào ngày 15/12/1998, phiên bản thứ 3 là FIPS PUB 186-2 đưa ra vào ngày 27/1/2000 và phiên bản mới nhất hiện nay là FIPS PUB 186-3 được công bố vào tháng 3/2006.
  15. Chuẩn chữ ký số (DSS) Giới thiệu
  16. Chuẩn chữ ký số (DSS) Giới thiệu
  17. Chuẩn chữ ký số (DSS) Các tham số của DSA • p: là một số nguyên tố trong đó 2L-1 < p < 2L với L là độ dài bit của biến p. • q: là một ước số nguyên tố của p-1 trong đó 2N-1< p < 2N với N là chiều dài của biến q(tính theo bít). • g: là căm bậc q của 1 theo modulo p. Dễ dàng tính được g như sau: g = h(p-1)/q mod p. Với 1< h < p-1 • x: là khóa bí mật. x là một số nguyên dương được tạo ra một cách ngẫu nhiên sao cho 0< x < q-1. • y: là khóa công khai, trong đó y = gx mod p. • k: là số bí mật và là duy nhất với mỗi một tin nhắn. k là số nguyên được tạo ra ngẫu nhiên sao cho 0 < k < q.
  18. Chuẩn chữ ký số (DSS) Lựa chọn kích thước các tham số p và q Chuẩn này đưa ra một số lựa chọn cho cặp (L, N) như sau: (L = 1024, N = 160), (L = 2048, N = 224) và (L = 3072, N = 256)
  19. Chuẩn chữ ký số (DSS) Tạo chữ ký số DSA Chữ ký trên thông điệp M là một cặp số (r, s) được tính toán như sau: r = (gk mod p) mod q. s = k-1(z + x.r) mod q. Với z = N bít trái nhất của hàm Hash(M). Giá trị của r và s sẽ được kiểm tra để xem chúng có bằng 0 hay không. Nếu một trong hai giá trị này bằng không thì bên ký sẽ phải tạo ra một giá trị k khác và chữ ký số sẽ phải được tính toán lại.
  20. Chuẩn chữ ký số (DSS) Xác nhận chữ ký số DSA Đặt M’, r’, s’ là thông điệp và chữ ký cần đi xác nhận. Đặt y là khóa công khai của người tuyên bố đã tạo ra chữ ký. Qui trình xác nhận chữ ký được thực hiện như sau: w = (s’)-1 mod q. z = N bít trái nhất của Hash(M’). u1 = z.w mod q. u2 = r’.w mod q. u v = (g u 1. y 2 mod p) mod q. Nếu v = r’ thì chữ ký số được xác nhận.
  21. Chuẩn chữ ký số (DSS) Giải thuật tạo các số nguyên tố p và q BEGIN L, N, seedlen Không hợp lệ kiểm tra L, N In “Không hợp lệ” Hợp lệ END n = L / outlen - 1; b = L - 1 - (n * outlen) 5 domain_parameter_seed=RBG(seedlen) U = Hash(domain_parameter_seed) mod 2N q = U  2N-1 1 Sai Đúng q ? nguyên tố 1
  22. Chuẩn chữ ký số (DSS) Giải thuật tạo các số nguyên tố p và q X = W + 2L-1 1 c = X mod 2q p = X - (c - 1) offset=1 Đúng p<2L-1 counter=0 3 Sai j=0 Đúng j=j+1 p ? nguyên tố 4 Sai Vj = Hash ((domain_parameter_seed + offset + j) mod 2seedlen) offset=offset+n+1 Sai Đúng j≤n counter≤4095 3 Sai Đúng outlen (n-1) * outlen W = V0 + (V1 * 2 ) + + (Vn-1 * 2 ) 5 n * outlen + ((Vn mod 2b) * 2 )
  23. Chuẩn chữ ký số (DSS) Giải thuật tạo các số nguyên tố p và q 4 In p,q, domain_parameter_seed, counter END
  24. Chuẩn chữ ký số (DSS) Giải thuật xác suất Miller-Rabin kiểm tra tính nguyên tố Chuẩn Miller-Rabin như sau: cho n là số nguyên lẻ thỏa mãn n-1 = 2e.u, với u là số nguyên tố. • Nếu n là số nguyên tố, thì với mọi số nguyên dương a với 0 ≤ a ≤ n -1: (au ≡ 1 mod n) hoặc  k < e sao cho a ≡ -1 mod n (*) • Nếu n là hợp số thì k n 1 {a: 1 ≤ a ≤ n-1, au ≡ 1 mod n hoặc k < e(a 2 . u ≡ -1 mod n)} ≤ 4 Tức là khi số nguyên lẻ n có dạng thỏa mãn n-1 = 2e.u với u là số nguyên tố thì nếu n là số nguyên tố, nó luôn thỏa mãn tính chất(*) còn khi n là hợp số thì chỉ có thể tìm được tối đa là số nguyên a để thỏa mãn tính chất(*). Tính chất(*) đó là hoặc au ≡ 1 mod n, nếu không thì sẽ tồn tại một số k thỏa mãn a ≡ -1 mod n.
  25. Chuẩn chữ ký số (DSS) Giải thuật xác suất Miller-Rabin kiểm tra tính nguyên tố BEGIN j=1 w, iteration z = z2 mod w j=j+1 a là số nguyên lớn nhất thỏa mãn: w-1 = 2a; Đúng  z= w-1 m = (w-1) / 2a; wlen = len(w); i=0 Sai Đúng b=RBG(wlen) z= 1 1 i=i+1 Sai Đúng Đúng j < a b≤ 1 or b≥ w-1 3 2 Sai Sai i< iteration 2 m Đúng z = b mod w Sai In “Nguyên tố” 1 Đúng Sai 3 z=1 or z= w-1 END In “Hợp số”
  26. Do hạn chế về kiến thức cũng như về thời gian nghiên cứu, bài luận văn này chắc chắn không tránh khỏi những sai sót. Em rất mong nhận được ý kiến đóng góp của các thầy cô giáo và bạn bè. Cuối cùng em xin chân thành cảm ơn sự hỗ trợ của các thầy cô trong khoa, đặc biệt tới thầy giáo TS. Lê Phê Đô, người đã luôn tận tình hướng dẫn, theo dõi em trong quá trình thực hiện đề tài.