Tài liệu Nghiên cứu phương pháp bảo vệ bản quyền tài liệu số hóa

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thụy Nghiên cứu phƣơng pháp bảo vệ bản quyền tài liệu số hóa Luận văn ThS Khoa học máy tính (60 48 01) Hà Nội - 2008 1 MỤC LỤC Chương 1: CÁC KHÁI NIỆM CƠ BẢN. ..................................................................... 7 1.1 MÃ HÓA. .................................................................................................... 7 1.1.1 Khái niệm. ............................................................................................... 7 1.1.2 Phân loại các hệ mã hóa. .......................................................................... 7 1.1.3 Một số hệ mã hóa cụ thể. ....................................................................... 10 1.2 HÀM BĂM................................................................................................ 13 1.2.1 Một số tính chất cơ bản của hàm băm .................................................... 14 1.2.2 Cấu trúc cơ bản của các thuật toán băm mật mã. .................................... 15 1.3 CHỮ KÝ SỐ.............................................................................................. 16 1.3.1 Khái niệm. ............................................................................................. 16 1.3.2 Phân loại chữ ký điện tử. ....................................................................... 17 1.3.3 Một số sơ đồ chữ ký cụ thể. ................................................................... 19 1.4 THỦY VÂN SỐ. ....................................................................................... 22 1.4.1 Khái niệm giấu tin. ................................................................................ 22 1.4.2 Khái niệm Thủy vân số. ......................................................................... 23 1.4.3 Phân loại thủy vân số. ............................................................................ 24 1.4.4 Thủy vân số trong dữ liệu đa phƣơng tiện. ............................................. 26 1.5 VẤN ĐỀ BẢO VỆ BẢN QUYỀN TÀI LIỆU SỐ. ..................................... 27 Chương 2: CẤU TRÚC MỘT SỐ TỆP DỮ LIỆU PHỔ BIẾN TRÊN INTERNET................... 28 2.1 ÂM THANH VÀ MỘT SỐ CẤU TRÚC FILE ÂM THANH. ................... 28 2.1.1 Các đặc tính của âm thanh. .................................................................... 28 2.1.2 Số hóa tín hiệu âm thanh tƣơng tự. ........................................................ 30 2.1.3 Mố số cấu trúc file âm thanh số. ............................................................ 32 2.1.3.1 Tệp Wave (*.wav) ......................................................................... 32 2.1.3.2 Tệp Midi. (*.mid) .......................................................................... 37 2.2 ẢNH SỐ VÀ CÁC CẤU TRÚC FILE ẢNH. ............................................. 42 2.2.1 Mầu sắc và các mô hình mầu ................................................................. 42 2.2.1.1 Mô hình mầu RGB ........................................................................ 43 2.2.1.2 Mô hình mầu CMY ....................................................................... 44 2.2.1.3 Mô hình mầu HSV ........................................................................ 45 2.2.2 Một số loại ảnh. ..................................................................................... 45 2.2.2.1 Ảnh GIF ........................................................................................ 45 2.2.2.2 Ảnh BMP (bitmap) ........................................................................ 46 2.2.2.3 Ảnh JPEG ..................................................................................... 48 Chương 3: MỘT SỐ PHƢƠNG PHÁP BẢO VỆ BẢN QUYỀN TÀI LIỆU SỐ.................. 49 3.1 PHƢƠNG PHÁP BẢO MẬT. ................................................................... 49 3.2 PHƢƠNG PHÁP XÁC THỰC. ................................................................. 50 3.2.1 Xác thực đồng nhất (toàn vẹn dữ liệu). .................................................. 50 2 3.2.2 Xác thực thực thể. .................................................................................. 52 3.3 PHƢƠNG PHÁP CHỐNG CHỐI BỎ. ....................................................... 59 3.3.1 Sơ đồ chữ ký chống chối cãi có “trọng tài”. ........................................... 59 3.3.2 Sơ đồ chữ ký chống chối cãi Chaum-van Antverpen. ............................. 61 3.4 PHƢƠNG PHÁP KẾT HỢP CHỮ KÝ SỐ VÀ CHỨNG CHỈ SỐ. ............ 64 3.4.1 Mô hình xác thực bản quyền sử dụng chứng chỉ số. ............................... 64 3.4.2 Sự chứng nhận và kiểm tra chữ ký. ........................................................ 65 3.5 PHƢƠNG PHÁP THỦY VÂN SỐ. ........................................................... 67 3.5.1 Kỹ thuật thủy vân LSB ứng dụng chống xuyên tạc ảnh. ......................... 67 3.5.1.1 Kỹ thuật LSB (Least Signification Bits). ....................................... 67 3.5.1.2 Thuật toán nhúng thủy vân bằng kỹ thuật LSB. ............................. 70 3.5.2 Kỹ thuật thủy vân bền vững trên miền tần số. ........................................ 72 3.5.2.1 Biến đổi Cosin rời rạc – DCT. ....................................................... 72 3.5.2.2 Thuật toán nhúng thủy vân. ........................................................... 73 Chương 4: THỬ NGHIỆM CHƢƠNG TRÌNH ......................................................... 77 4.1 4.2 4.3 CƠ SỞ LÝ THUYẾT................................................................................. 77 MỘT SỐ GIAO DIỆN CỦA CHƢƠNG TRÌNH. ...................................... 78 MỘT SỐ ĐOẠN MÃ NGUỒN QUAN TRỌNG. ...................................... 81 3 DANH MỤC HÌNH VẼ Hình 1.1: Trao đổi mật mã sử dụng Hệ mã hóa khóa công khai .................................... 8 Hình 1.2: Hàm băm mật mã ........................................................................................ 13 Hình 1.3: Qua trình ký của chữ ký số kèm thông điệp ................................................ 17 Hình 1.4: Quá trình kiểm thử của chữ ký kèm thông điệp ........................................... 17 Hình 1.5: Quá trình ký của chữ ký khôi phục thông điệp ............................................ 18 Hình 1.6: Quá trình nhúng thủy vân ............................................................................ 22 Hình 1.7: Quá trình phát hiện thủy vân. ...................................................................... 23 Hình 1.8: Cách phân loại thủy vân theo tính bền vững. ............................................... 24 Hình 1.9: Phân loại thủy vân theo cảm nhận ............................................................... 25 Hình 2.1: Lƣợng tử tín hiệu Analog. ........................................................................... 30 Hình 2.2 Lấy mẫu tín hiệu ......................................................................................... 31 Hình 2.3: Khuôn dạng tệp Wave ................................................................................. 34 Hình 2.4: Độ dài bƣớc sóng của ba mầu đỏ, lục và lam .............................................. 43 Hình 2.5: Mô hình mầu RGB...................................................................................... 44 Hình 2.6: Mô hình mầu CMY ..................................................................................... 44 Hình 2.7: Mô hình mầu HSV ...................................................................................... 45 Hình 2.8: Cấu trúc ảnh Gif ......................................................................................... 46 Hình 3.1: Xác thực đồng nhất. .................................................................................... 52 Hình 3.2: Xác thực thực thể sử dụng mật khẩu. .......................................................... 54 Hình 3.3: Chứng chỉ số. .............................................................................................. 58 Hình 3.4: Sơ đồ chống chối cãi có trọng tài. ............................................................... 60 Hình 3.5: Mô hình Certification Authority đơn giản ................................................... 64 Hình 3.6: Quá trình ký chứng nhận ............................................................................. 65 Hình 3.7: Quá trình kiểm tra chứng nhận .................................................................... 66 Hình 3.8: Biểu diễn ảnh Bitmap không nén ................................................................ 68 Hình 3.9: Mô hình nhúng tin ngẫu nhiên. ................................................................... 69 Hình 3.10 Qúa trình nhúng tin với k‎ỹ‎thuật LSB......................................................... 70 Hình 3.11 Qúa trình tách tin và Xác thực ảnh ............................................................. 71 Hình 3.12: Quá trình nhúng thủy vân. ......................................................................... 74 Hình 3.13: Quá trình rút/trích thủy vân ....................................................................... 75 Hình 4.1 Nhúng thủy vẫn vô hình bằng kỹ thuật LSB ................................................. 78 Hình 4.2: Ảnh đã bị phát hiện sửa đổi ......................................................................... 79 Hình 4.3 Thủy vẫn hữu hình ....................................................................................... 80 Hình 4.4 Kết quả nhúng thủy vẫn hữu hình................................................................. 80 4 MỞ ĐẦU Sự ra đời và phát triển mạnh mẽ của các hệ thống mạng và ngày nay là mạng toàn cầu Internet đã mạng lại sự đột phá trong xã hội. Đƣa thế giới chuyển từ kỷ nguyên Công nghiệp sang kỷ nguyên Thông tin và kinh tế tri thức. Cuộc cách mạng thông tin và kỹ thuật số đã đem lại những thay đổi sâu sắc trong tƣ duy và cách làm việc của con ngƣời. Trong môi trƣờng mạng, con ngƣời có thể sử dụng những sản phẩm tri thức dƣới dạng đã đƣợc số hóa. Mạng Internet toàn cầu, nơi diễn ra quá trình trao đổi thông tin trong mọi lĩnh vực mọi thời điểm, là môi trƣờng hoàn hảo cho việc trao đổi thông tin và hội nhập. Việc triển khai các hệ thống số đã chuyển đổi các cách thức mà trong đó các sản phẩm đã đƣợc taọ ra, sử dụng và phân phối trên thị trƣờng. Số hoá các nội dung đã đặt ra những thách thức chƣa từng có cho tất cả các bên liên quan. Trong khi nó cho phép cá các nhân sử dụng các tài nguyên theo các phƣơng thức mới, thì công nghệ số cũng đã tạo ra khả năng sao chép hoàn hảo, không có bất kỳ khiếm khuyết và phân phối lại những sản phẩm này trên toàn thế giới, có hoặc không có sự cho phép trƣớc của ngƣời sở hữu. Thực tế sau một giai đoạn do dự ban đầu, ngƣời sáng tạo nội dung, các nhà cung cấp dịch vụ Internet và rất nhiều các thành viên khác nhau đang phát triển những phƣơng thức kinh doanh mới cho việc phân phối nội dung số. Internet đã thay đổi mọi thứ trong việc đƣa các nội dung trí tuệ đến với cộng đồng. Những vụ kiện về bản quyền số diễn ra hàng ngày hàng giờ đang khiến nguời ta tự hỏi về tƣơng lai của các sản phẩm trí tuệ trong thế giới mạng. Vấn đề đặt ra cho tất cả các phƣơng thức kinh doanh, phân phối tài nguyên số là làm sao vẫn phải tuân thủ các nguyên tắc về quyền sở hữu trí tuệ, nhƣng không cản trở hay làm phức tạp hóa quá trình phân phối tài nguyên số đó. Hiện nay có rất nhiều kỹ thuật bảo vệ bản quyền tài nguyên số. Các kỹ thuật khác nhau cho phép tác động vào một tập các kiểu tài nguyên số tƣơng ứng. 5 Luận văn nghiên cứu các phƣơng pháp bảo vệ bản quyền tài nguyên số. Các kỹ thuật giữ bản quyền tài nguyên số trong luận văn đƣợc nghiên cứu dựa trên các loại tài liệu đƣợc phân nhóm và từ đó mỗi nhóm tài nguyên số sẽ có các kỹ thuật đặc trƣng riêng. Luận văn gồm 3 chƣơng: Chương 1: Các khái niệm cơ bản. Trong chƣơng này sẽ trình bầy tổng quan về Bản quyền số và các khái niệm cơ bản đƣợc sử dụng trong toàn Luận văn. Bao gồm: Khái niệm toán học, khái niệm Thủy vân số, Chữ ký số, Xác thực điện tử cho việc giữ bản quyền tài liệu số. Chương 2: Cấu trúc của các loại tài nguyên số phổ biến trên Internet Chƣơng này trình bầy về cấu trúc của các nhóm tài nguyên số thƣờng đƣợc trao đổi trên Internet. Bao gồm: Nhóm tài nguyên về Audio (*.wav, *.mp3, *.midi), Nhóm tài nguyên về Image (*.bmp, *.gif, *.jpge) Chương 3: Các kỹ thuật bảo về bản quyền tài liệu số. Trên cơ sở các nhóm tài nguyên số đã đƣợc phân loại và tìm hiểu cấu trúc lƣu trữ trong chƣơng 2. Trong chƣơng này trình bầy các kỹ thuật tƣơng ứng với mỗi nhóm tài nguyên số đó. Các kỹ thuật này phụ thuộc vào cấu trúc lƣu trữ và đặc trƣng dữ liệu của các nhóm tài nguyên số. 6 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN. 1.1 MÃ HÓA. Nhƣ đã biết, việc truyền tin trên mạng rất dễ bị “đánh cắp”, vì vậy để đảm bảo an toàn cho nội dung thông tin đƣợc truyền ngƣời ta thƣờng mã hóa trƣớc khi truyền nó trên mạng, nhằm giấu đi ý nghĩa của nó. Các hệ mã đƣợc chia thành 2 nhóm chính, Mã hóa khóa công khai và mã hóa khóa bí mật. Trong phần này sẽ trình bầy các khái niệm về mật mã và các vấn đề liên quan. 1.1.1 Khái niệm. Một hệ mật mã là một bộ năm (P, C, K, E, D) trong đó: + P: là một tập hữu hạn các bản rõ. + C: là một tập hƣu hạn các bản mã. + K: là một tập hƣu hạn các khoá. + Với mỗi k  K, có một hàm lập mã ek  E, ek: P  C, và một hàm giải mã dk  D, dk: C  P sao cho dk(ek(x)) = x với mọi x  P. 1.1.2 Phân loại các hệ mã hóa. Các hệ mã hóa đƣợc chia thành 2 nhóm chính. “Mã hóa khóa đối xứng” và “Mã hóa khóa công khai”. Mã hóa khóa đối xứng: Là hệ mã mà việc lập mã và giải mã thƣờng dùng chung một khóa, hoặc nếu có dùng hai khóa thì khi khóa lập mã bị lộ ngƣời ta có thể tìm ra khóa giải mã trong thời gian tƣơng đối ngắn. Tuy nhiên do đặc tính mã hóa tƣơng đối nhanh, các hệ mã loại này thƣờng đƣợc dùng để mã hóa các loại tài liệu có kích thƣớc lớn. 7 Các hệ mã loại này nói chung có một điểm yếu rất dễ bị tấn công đó là quá trình chuyển giao khóa giữa các bên liên quan (người nhận). Trong hệ mã hóa khóa đối xứng ngƣời ta còn chia các hệ mã thành 3 nhóm: “Mã hóa cổ điển”, “Mã hóa khối” và “Mã dòng”. Kẻ tấn công k’ (kênh công cộng) Lập mã ek’(x)=y y (kênh công cộng) Bộ khóa (k’, k”) Giải mã dk”(y)=x Bản rõ Kết quả A B Hình 1.1: Trao đổi mật mã sử dụng Hệ mã hóa khóa công khai 8 Mã hóa khóa công khai: Là hệ mã mà việc lập mã và giải mã dùng hai khóa khác nhau. Hai khóa này có mối liên hệ chặt chẽ và có thể suy ra nhau phụ thuộc vào từng hệ mã cụ thể. Trong đó khóa lập mã đƣợc công khai (public) và khóa giải mã đƣợc giữ bí mật (private). Các hệ mã loại này đƣợc xây dựng dựa trên các bài toán “khó” nên quá trình lập mã và giải mã tƣơng đối chậm, nên thƣờng đƣợc dùng để mã hóa các dữ liệu nhỏ. Nhƣ vậy các hệ mã khóa khóa công khai đã khắc phục đƣợc nhƣợc điểm lớn nhất của mã hóa khóa đối xứng là quá trình phải chuyển giao khóa giữa các bên liên quan. Trong các sơ đồ mã hóa khóa công khai ngƣời nhận A tính toán ra cặp khóa sau đó giữ cho mình khóa giải mã (private key) và công khai khóa lập mã (public key). Mọi ngƣời trên mạng muốn gửi thông tin mật cho A sẽ sử dụng khóa công khai lập mã rồi gửi bản mã cho A. Do chỉ duy nhất A có khóa giải mã tƣơng ứng nên chỉ A mới giải mã đƣợc tài liệu đó. 9 1.1.3 Một số hệ mã hóa cụ thể. 1/.Mã hóa RSA Bài toán RSA (RSA Problem): Cho một số nguyên dƣơng n là tích của hai thừa số nguyên tố lẻ p và q. Một số nguyên dƣơng b sao cho gcd(b, (p-1)(q-1)) = 1 và một số nguyên c. Bài toán đặt ra: tìm số nguyên x sao cho xb ≡ c (mod n) Thuật toán Sinh khóa cho mã khóa Công khai RSA 1. Sinh hai số nguyên tố lớn p và q có giá trị xấp xỉ nhau 2. Tính n = p.q, và (n) = (p-1).(q-1) 3. Chọn một số ngẫu nhiên b, 1 < b < (n), sao cho gcd(b, (n)) = 1 4. Sử dụng thuật toán Euclide để tính số a, 1 < a < (n), sao cho a.b ≡ 1 (mod (n)) 5. Khóa công khai là (n, b), Khóa bí mật là (a) Thuật toán Mã hóa RSA (i). Lập mã : a. Lấy khóa công khai (n, b) theo thuật toán trên b. Chọn một bản mã x, trong khoảng [1, n-1] c. Tính : y = xb mod n d. Nhận đƣợc bản mã y (ii). Giải mã : Sử dụng khóa bí mật a để giải mã : x = ya mod n 10 Chứng minh hàm giải mã: Ta có a.b ≡ 1 (mod (n)) vì vậy tồn tại một số nguyên dƣơng k sao cho a.b=1+k.(n) và nếu gcd(x,p)=1 thì theo định lý Fermat ta có: xp-1≡1 (mod p) Thực hiện việc nâng lũy thừa hai vế của đồng dƣ thức trên với số mũ là k(q-1) sau đó nhân cả hai vế với x ta đƣợc: x1+k(p-1)(q-1) ≡x (mod p) Trong trƣờng hợp khác, nếu gcd(x,p)=p thì đồng dƣ thức trên vẫn đúng vì mỗi vế của nó đều có dạng 0 modulo p. Do đó: xa.b ≡ x (mod p) Lập luận tƣơng tự ta có: xa.b ≡ x (mod q) Cuối cùng, vì p, q là hai số nguyên tố khác nhau nên: xa.b ≡ x (mod n) do đó: ya ≡ (xb)a ≡ x (mod n)  11 2/. Mã hóa ElGamal. Bài toán logarit rời rác (Discrete logarithm problem): Cho một số nguyên tố p và một phần tử sinh α của tập Z * p , một phần tử β  Z * p . Bài toán đặt ra: tìm một số nguyên x, 0 ≤ x ≤ (p-2), sao cho αx ≡ β (mod p) Thuật toán Sinh khóa cho mã khóa Công khai ElGamal 1. Sinh ngẫu nhiên một số nguyên tố lớn p và α là phần tử sinh của Z 2. Chọn ngẫu nhiên một số nguyên a, 1 ≤ a ≤ p−2, tính αa mod p 3. Khóa công khai la (p, α, αa). Khóa bí mật (a) * p Thuật toán Mã hóa ElGamal (i). Lập mã : a. Lấy khóa công khai (p, α, αa) theo thuật toán trên b. Chọn một bản mã x, trong khoảng [0, p−1] c. Chọn ngẫu nhiên một số nguyên k, 1 ≤ k ≤ p−2 d. Tính γ = αk mod p và δ = x.(αa)k mod p e. Nhận đƣợc bản mã là (γ, δ) (ii). Giải mã : a. Sử dụng khóa bí mật (a) và tính γp-1-a mod p b. Lấy bản rõ: x = (γ-a).δ mod p Chứng minh hàm giải mã: (γ-a).δ ≡ (α-ak).x.(αak) ≡ x (mod p).  12 1.2 HÀM BĂM. Hàm băm theo nghĩa đơn giản là hàm cho tƣơng ứng một mảng dữ liệu lớn với một mảng dữ liệu nhỏ, đƣợc sử dụng rộng rãi trong nhiều ứng dụng khác nhau của tin học. Trong công nghệ mã, hàm băm cho khả năng đảm bảo toàn vẹn dữ liệu (data integrity). Những hàm băm nhƣ vậy đƣợc gọi là hàm băm mật mã. Các hàm băm nhận một chuỗi bits có chiều dài tùy ý (hữu hạn) làm dữ liệu đầu vào và tạo ra một chuỗi bits có chiều dài cố định n bit (n > 0 là hằng số), gọi là mã băm (hash code hay message digest). Ký hiệu D là miền xác định và R là miền giá trị của hàm băm h(x), ta thƣờng có số lƣợng phần tử của D lớn hơn rất nhiều so với số lƣợng phần tử của R (|D| > |R|), vì vậy hàm băm h(x) không thể là đơn ánh, nghĩa là luôn tồn tại một cặp phần tử đầu vào khác nhau nhƣng có cùng giá trị mã băm. Trong lĩnh vực mã hóa thông tin, mã băm đƣợc xem nhƣ hình ảnh đặc trƣng, thu gọn của một chuỗi bits có độ dài tùy ý (hữu hạn), và đƣợc dụng để nhận diện chuỗi bits đó. Kết hợp với chữ ký số, các hàm băm đƣợc dùng cho việc đảm bảo tính toàn vẹn dữ liệu. Trong sơ đồ truyền tin mã băm của chuỗi bits x đƣợc tính tại thời điểm xác định T1, quá trình truyền chuỗi bits x và mã băm tƣơng ứng đƣợc thực hiện. Tại thời điểm T2 sau đó, để kiểm tra chuỗi bits x có bị thay đổi hay không, ngƣời ta chỉ cần tính mã băm của x tại thời điểm này, sau đó so sánh với mã băm có đƣợc tại thời điểm T1. Nếu hai mã băm này trùng nhau chấp nhận chuổi bits x tại thời điểm T2 trùng khớp với chuỗi bits x tại thời điểm T1, hay nói cách khác chuỗi bits x vẫn chƣa bị thay đổi. Chiều dài cố định (n bit, n > 0) Chiều dài tùy ý Thông điệp (message) (âm thanh, hình ảnh, văn bản…) Hàm băm thông điệp (Hash Function) Văn bản đại diện (message digest) Hình 1.2: Hàm băm mật mã 13 Các hàm băm đƣợc phân thành 2 lớp chính: lớp các hàm băm không có khóa (unkeyed hash functions) và lớp các hàm băm có khóa (keyed hash functions). Các hàm băm không khóa chỉ có duy nhất một đầu vào là thông điệp cần tính giá trị băm. Còn các hàm băm có khóa nhận 2 giá trị đầu vào: thông điệp cần tính giá trị băm và khóa bí mật để tiến hành công việc. Cách phân lớp này dựa vào thành phần tham biến đầu vào của các hàm băm. Ngoài ra, trong thực tế còn có nhiều cách phân loại khác nhau. Tuy nhiên trong phạm vi luận văn chỉ xét loại hàm băm không khóa. 1.2.1 Một số tính chất cơ bản của hàm băm a. Tính kháng tiền ảnh (preimage resistance): Với mọi đầu ra y cho trƣớc không thể tính toán để tìm đƣợc bất kì dữ liệu đầu vào x’ nào sao cho giá trị băm h(x’) của nó bằng giá trị đầu ra y đã cho. b. Tính kháng tiền ảnh thứ hai (2nd preimage resistance): Với mọi dữ liệu đầu vào x1 cho trƣớc, không thể tính toán để tìm ra đƣợc bất kỳ một đầu vòa x2 nào (x1  x2) mà giá trị băm h(x2) của nó bằng với giá trị băm h(x1) của x1. c. Tính kháng xung đột (conllision resistance): Không thể tính toán để tìm đƣợc hai dữ liệu đầu vào x1 và x2 phân biệt sao cho chúng có cùng giá trị băm (tức là h(x1) = h(x2)) Nhận xét 1: Hàm băm h(x) thỏa mãn tính chất (c) thì cũng thỏa mãn tính chất (b). Nhận xét 2: Hàm băm h(x) thỏa mãn tính chất (c) nhƣng có thể không thỏa mãn tính chất (a). Để thấy điều này ta xét ví dụ sau đây. Giả sử g(x) là hàm băm ánh xạ đầu vào có chiều dài tùy ý và đầu đầu ra có chiều dài n cố định, thỏa mãn tính chất (c). Xét hàm h(x) đƣợc định nghĩa nhƣ sau:  1 || x h(x)    0 || g ( x ) |x|  n |x|  n 14 Trong đó || ký hiệu cho phép toán nối các chuỗi bit, |x| ký hiệu độ dài của chuỗi bit x. Khi đó, ta đƣợc h(x) làm hàm băm có dữ liệu đầu ra dài (n+1) bit. Rõ ràng, hàm h(x) thỏa mãn tính chất (c) nhƣng không thỏa mãn tính chất (a). Thật vậy, lấy hai xâu bit x1 và x2 phân biệt. Nếu chiều dài của 2 xâu bit này cũng bằng n thì chúng có cùng giá trị băm khi và chỉ khi chúng trùng nhau. Nếu chỉ có một trong 2 xâu bit có chiều dài bằng n thì giá trị băm của chúng có thể không trùng nhau (vì có bit đầu vào khác nhau). Nếu chiều dài của 2 xâu bit này cũng khác n thì nói chung, do tính chất (c) của hàm g(x), ta luôn có g(x1)  g(x2) và vì vậy h(x1)  h(x2). Rõ ràng hàm h(x) không thỏa mãn tính chất (a) vì chỉ cần lấy giá trị băm có dạng y=1||x, trong đó x là xâu bit có chiều dài bằng n, là ta dễ dàng tìm ra “tiền ảnh” của y là x. 1.2.2 Cấu trúc cơ bản của các thuật toán băm mật mã. Trƣớc tiên, khối dữ liệu đầu vào x có chiều dài hữu hạn tùy ý sẽ đƣợc phân thành các khối con liên tiếp có chiều dài cố định r, giả sử đƣợc đánh số là: x1, x2, …, xn. Tuy nhiên, do chiều dài khối dữ liệu ban đầu là tùy ý, vì vậy, ta có thể phải thêm vào dữ liệu ban đầu một số bit phụ sao cho chiều dài của khối dữ liệu x’ sau khi thêm bit phụ là bội số của r. Ngoài ra, khối bit phụ thêm vào thƣờng chứa một khối bit xác định chiều dài thực của khối bit dữ liệu khi chƣa thêm các bit phụ. Sau đó, lần lƣợt “cắt” từng khối con r bit từ khối mở rộng x’. Mỗi khối con xi lần lƣợt đƣợc đi qua hàm nén f của hàm băm h(x). Tại bƣớc thứ i, hàm nén f nhận dữ liệu đâu vào là xi và kết quả trung gian của bƣớc trƣớc đó (bước (i-1)) để tạo đầu ra là kết quả trung gian bƣớc thứ i, đƣợc ký hiệu là Hi. Kết quả trung gian tại mỗi bƣớc Hi là một chuỗi bit có độ dài cố định bằng n > 0. Nếu giá trị IV là gí trị khởi tạo ban đầu (cho H0) thì quá trình lặp xử lý dãy các khối con x1, x2, …, xn đƣợc mô tả nhƣ sau: H0 = IV Hi = f(Hi-1, xi), (i=1,…,m) H(x) = g(Hm) 15 Trong đó, có thể gọi Hi (kết quả trung gian sau bước thứ i) là các biến dây truyền (chaining variable). Hàm g(Hm) là biến dây truyền cuối cùng để tạo ra mã băm cần tìm. Trong hầu hết các thuật toán, g(x) thƣờng đƣợc chọn là ánh xạ đồng nhất, tức là g(Hm)  Hm. Khâu then chốt trong xây dựng hàm băm thƣờng là thiết kế hàm nén f. 1.3 CHỮ KÝ SỐ. Trong mật mã học một kỹ thuật cơ bản cho vấn đề xác nhận thực thể đƣợc sử dụng nhiều nhất đó là chữ ký số. Mục đích của chữ ký số là cung cấp một cách thức cho phép gắn định danh của một thực thể vào một phần của thông tin. Quá trình ký thực hiện chuyển đổi văn bản và các thông tin mật cần thiết của thực thể vào một đích đƣợc gọi là chữ ký. Với đặc tính của loại kỹ thuật này, chúng ta có thể sử dụng nó cho ứng dụng bảo vệ bản quyền, quyền sở hữu trí tuệ bằng cách gắn thông tin của tác giả vào tác phẩm số của họ. Vì chỉ có tác giả mới có khóa ký nên những tác phẩm đƣợc phân phối từ chính tác giả sẽ đƣợc kiểm thử bởi ngƣời dùng đầu cuối bằng khóa kiểm thử do đó đảm bảo đƣợc tác quyền đối với tác phẩm đƣợc phân phối chính thức. 1.3.1 Khái niệm. Một sơ đồ chữ ký là một bộ 5 (P, A, K, S, V) trong đó: + P: là một tập hữu hạn các thông báo có thể có. + A: là một tập hữu hạn các chữ ký có thể có. + K: là một tập hữu hạn các khóa, mỗi khóa K  K gồm 2 thành phần K(k’, k”), k’ là khóa bí mật dành cho việc ký, k” là khóa công khai dành cho việc kiểm thử. Với mỗi K(k’, k”) trong S có một thuật toán ký sigk’: P → A và trong V có thuật toán kiểm thử verk”: P × A → {true, false} thỏa mãn điều kiện sau đây với mọi thông báo x  P và mọi chữ ký y  A: verk”(x, y) = true  y = sigk’(x) 16 1.3.2 Phân loại chữ ký điện tử. Chữ ký “điện tử” đƣợc chia làm 2 lớp, lớp chữ ký kèm thông điệp (message appendix) và lớp chữ ký khôi phục thông điệp (message recovery). Chữ ký kèm thông điệp: Đòi hỏi thông điệp ban đầu là đầu vào của giải thuật kiểm tra. Ví dụ: chữ ký Elgamal. P S Ph h sigk’ x’=h(x) x y=sigk’(x’) Hình 1.3: Qua trình ký của chữ ký số kèm thông điệp PxS · True verk’’ · False Hình 1.4: Quá trình kiểm thử của chữ ký kèm thông điệp Chữ ký khôi phục thông điệp: Thông điệp ban đầu sinh ra từ bản thân chữ ký. Ví dụ: chữ ký RSA. 17 S P sigk’ x s=sigk’(x) Hình 1.5: Quá trình ký của chữ ký khôi phục thông điệp 18 1.3.3 Một số sơ đồ chữ ký cụ thể. 1/. Sơ đồ chữ ký RSA. Thuật toán Sinh khóa cho chữ ký RSA (do người A thực hiện) 1. Sinh hai số nguyên tố lớn p và q có giá trị xấp xỉ nhau 2. Tính n = p.q, và (n) = (p-1).(q-1) 3. Chọn một số ngẫu nhiên b, 1 < b < (n), sao cho gcd(b, (n)) = 1 4. Sử dụng thuật toán Euclide để tính số a, 1 < a < (n), sao cho a.b ≡ 1 (mod (n)) 5. Khóa kiểm thử là (n, b), Khóa ký là (a) Thuật toán Ký và Kiểm thử chữ ký RSA (i). Ký : (do người A thực hiện) a. Sử dụng khóa ký (a) theo thuật toán trên b. Chọn một bản mã x, trong khoảng [1, n-1] c. Tính : y = xa mod n d. Nhận đƣợc chữ ký y (ii). Kiểm thử : (do người B thực hiện) a. Lấy khóa kiểm thử (n, b). Khóa này đƣợc công khai. b. Nếu x  yb mod n  TRUE, ngƣợc lại  FALSE Việc chứng minh hàm ký và kiểm thử của thuật toán ký số RSA đƣợc thực hiện nhƣ nhứng minh hàm lập mã và giải mã trong sơ đồ mã hóa khóa công khai RSA bên trên. 19 2/. Sơ đồ chữ ký DSS. Phƣơng pháp Digital Signature Standard (DSS) là sự cải tiến của phƣơng pháp ElGamal. Phƣơng pháp này đƣợc công bố trên Federal Register vào ngày 19 tháng 5 năm 1994 và chính thức trở thành phƣơng pháp chuẩn từ ngày 1 tháng 12 năm 1994. Thuật toán Sinh khóa cho chữ ký DSS (do người A thực hiện) 1. Chọn một số nguyên tố q trong khoảng 2159 < q < 2160 2. Chọn một số t (0  t  8), và chọn một số nguyên tố p (2511+64t - Xem thêm -