Tài liệu Nghiên cứu một số phương pháp bảo mật và xác thực bản quyền ảnh số

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ CHU VĂN HUY NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP BẢO MẬT VÀ XÁC THỰC BẢN QUYỀN ẢNH SỐ LUẬN VĂN THẠC SĨ HẢI PHÒNG - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ CHU VĂN HUY NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP BẢO MẬT VÀ XÁC THỰC BẢN QUYỀN ẢNH SỐ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.48.05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS TS. TRỊNH NHẬT TIẾN HẢI PHÒNG - 2011 2 MỤC LỤC BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT .......................................................................... 5 MỞ ĐẦU ............................................................................................................................... 6 Chương 1. CÁC KHÁI NIỆM CƠ BẢN ............................................................................ 7 1.1. TỔNG QUAN VỀ AN TOÀN THÔNG TIN ....................................................... 7 1.1.1. Khái niệm hệ thống thông tin và tài sản hệ thống thông tin ..................... 7 1.1.2. Các mối đe dọa đối với hệ thống thông tin và biện pháp ngăn chặn ........ 8 1.1.3. Mục tiêu và nguyên tắc chung của an toàn bảo mật thông tin .................. 9 1.1.4. Vấn đề bảo vệ bản quyền sản phẩm số ................................................... 10 1.1.5. Thực trạng vi phạm bảo vệ bản quyền sản phẩm số ............................... 11 1.1.6. Phƣơng pháp bảo vệ bản quyền ảnh số ................................................... 12 1.2. MỘT SỐ KHÁI NIỆM VỀ TOÁN HỌC ............................................................ 13 1.2.1. Ƣớc chung lớn nhất, bội chung nhỏ nhất ................................................ 13 1.2.2. Quan hệ “Đồng dƣ”................................................................................. 16 1.2.3. Số nguyên tố ........................................................................................... 19 1.2.4. Khái niệm Nhóm ..................................................................................... 22 1.2.5. Độ phức tạp thuật toán ............................................................................ 24 1.3. MỘT SỐ KHÁI NIỆM VỀ XỬ LÝ ẢNH .......................................................... 25 1.3.1. Khái niệm ảnh số .................................................................................... 25 1.3.2. Một số miền trong xử lý ảnh ................................................................... 27 Chương 2. MỘT SỐ PHƢƠNG PHÁP BẢO VỆ BẢN QUYỀN ẢNH SỐ ................... 28 2.1. MỘT SỐ TÌNH HUỐNG XUẤT HIỆN TRONG VIỆC BẢO VỆ BẢN QUYỀN ẢNH SỐ ..................................................................................................................... 28 2.1.1. Một số kiểu tấn công và tranh chấp liên quan tới ảnh số ........................ 28 2.1.2. Một số bài toán thƣờng gặp trong thực tế ............................................... 29 2.2. THỦY VÂN SỐ .................................................................................................. 31 2.2.1. Tổng quan về thủy vân số ....................................................................... 31 2.2.2. Mô hình thủy vân số ............................................................................... 41 2.2.3. Một số thuật toán thủy vân số ................................................................. 45 2.3. MÃ XÁC THỰC ................................................................................................. 56 2.3.1. Mã xác thực............................................................................................. 56 2.3.2. Một số loại mã xác thực .......................................................................... 57 2.4. CHỮ KÝ SỐ ....................................................................................................... 60 2.4.1. Tổng quan về chữ ký số .......................................................................... 60 2.4.2. Một số loại chữ ký số .............................................................................. 62 2.5. HÀM BĂM.......................................................................................................... 74 3 Chương 3. THỬ NGHIỆM CHƢƠNG TRÌNH BẢO VỆ BẢN QUYỀN ẢNH SỐ .... 79 3.1. CHƢƠNG TRÌNH THỦY VÂN TRÊN ẢNH SỐ ............................................. 80 3.1.1. Chƣơng trình thủy vân trên các bít LSB ................................................. 80 3.1.2. Chƣơng trình thủy vân dùng phép biến đổi DCT ................................... 85 3.2. CHƢƠNG TRÌNH KÝ SỐ TRÊN ẢNH SỐ ...................................................... 91 3.2.1. Chƣơng trình ký số RSA ......................................................................... 91 3.2.2. Chƣơng trình ký số Elgamal ................................................................... 97 3.3. CHƢƠNG TRÌNH ỨNG DỤNG HÀM BĂM TRÊN ẢNH SỐ ...................... 103 3.3.1. Chƣơng trình ứng dụng hàm băm MD5 ................................................ 103 KẾT LUẬN ....................................................................................................................... 107 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ .............................................................. 108 TÀI LIỆU THAM KHẢO ............................................................................................... 109 4 BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT Ký hiệu Viết đầy đủ Ý nghĩa DCT Discrete Cosine Transform Biến đổi Consine rời rạc DFT Discrete Fourier Transform Biến đổi Fourier rời rạc DWT Discrete Wavelet Transform Biến đổi sóng rời rạc HVS Human Visual System Hệ thống thị giác ngƣời LSB Least Significant Bit Bit ít quan trọng nhất MSE Mean Square Error Là sai số bình phƣơng trung bình NC Normalized Correlation Hệ số tƣơng quan chuẩn PSNR Peak Signal to Noise Ratio Tỷ số của tín hiệu nhọn với nhiễu VPN Virtual Private Networks Mạng riêng ảo 5 MỞ ĐẦU Tƣ̀ tr ƣớc công nguyên con ng ƣời đã phải quan tâm tới việc làm thế nào để đảm bảo an toàn bí mâ ̣t cho các tài liê ̣u quan tro ̣ng , đặc biê ̣t là trong lĩnh vƣ̣c quân sƣ̣, ngoại giao. Ngày nay với sự xu ất hiê ̣n của máy tin ́ h , các tài liệu nhƣ văn bản , hình ảnh, âm thanh, video và các thông tin quan trọng đ ều đƣợc số hóa và xử lý trên máy tính , đƣợc truy ền đi trong mô ̣t môi tr ƣờng mà m ặc đinh ̣ là không an toàn . Ngƣời ta có thể dễ dàng tạo ra những bản sao, dễ dàng sao chép trên quy mô lớn. Từ đó có thể dẫn đến nguy cơ một số ngành công nghiệp nhƣ xuất bản sách, nhạc, phim,… có nguy cơ bị đóng cửa do bị vi phạm bản quyền. Chính vì thế mối quan tâm nghiên cứu bảo vệ bản quyền các sản phẩm số nhằm tìm cách “ẩn quyền tác giả” vào các sản phẩm số đang thực sự nhận đƣợc sự quan tâm sâu sắc. Nhờ đó sau này ngƣời ta có thể xác định vi phạm bản quyền và truy tố những ngƣời vi phạm. Xuất phát từ thực trạng trên, em đã mạnh dạn đề xuất đề tài nghiên cứu “Một số phương pháp bảo mật và xác thực bản quyền ảnh số” nhằm đƣa ra một cái nhìn rõ ràng hơn về việc bảo vệ bản quyền đối với ảnh số - một đối tƣợng cụ thể của các sản phẩm số. Đề tài sẽ tập trung nghiên cứu một số phƣơng pháp bảo vệ bản quyền đối với đối tƣợng ảnh số. Các phƣơng pháp đƣợc đề cập bao gồm thủy vân số, chữ ký số kết hợp cùng với hàm băm và mã xác thực. Em xin chân thành cảm ơn thày PGS. TS Trịnh Nhật Tiến đã hỗ trợ, hƣớng dẫn em hoàn thành đề tài này. Hải Phòng, ngày 01 tháng 11 năm 2011 Học viên Chu Văn Huy 6 Chương 1. CÁC KHÁI NIỆM CƠ BẢN Trong chƣơng đầu tiên ta sẽ tìm hiểu một số nội dung cơ bản liên quan đến vấn đề bảo vệ bản quyền ảnh số để các chƣơng sau có thể sử dụng. 1.1. TỔNG QUAN VỀ AN TOÀN THÔNG TIN 1.1.1. Khái niệm hệ thống thông tin và tài sản hệ thống thông tin Khái niệm: Hệ thống thông tin là một tập hợp các máy tính gồm các thành phần phần cứng, phần mềm và dữ liệu làm việc đƣợc tích lũy qua thời gian. Tài sản của hệ thống thông tin bao gồm:  Phần cứng  Phần mềm  Dữ liệu  Truyền thông giữa các máy tính của hệ thống  Môi trƣờng làm việc  Con ngƣời,… 7 1.1.2. Các mối đe dọa đối với hệ thống thông tin và biện pháp ngăn chặn Có 3 hình thức đe dọa đối với một hệ thống thông tin:  Phá hoại: đối tƣợng tác động sẽ phá hỏng thiết bị phần cứng hoặc phần mềm hoạt động trên hệ thống.  Sửa đổi: Tài sản hệ thống bị sửa đổi trái phép. Điều này thƣờng làm cho hệ thống không làm đúng chức năng của nó. Chẳng hạn nhƣ khi mật khẩu bị thay đổi thì ngƣời dùng trong hệ thống không thể truy cập vào hệ thống để làm việc.  Can thiệp: Tài sản của hệ thống bị truy cập bởi ngƣời không có thẩm quyền. Các đe dọa đối với một hệ thống thông tin có thể đến từ nhiều nguồn và đƣợc thực hiện bởi các đối tƣợng khác nhau. Chúng có thể chia làm 3 loại:  Các đối tượng từ bên trong hệ thống (insider): đây là những đối tƣợng có quyền truy cập hợp pháp đối với hệ thống.  Các đối tượng từ bên ngoài hệ thống (hacker, cracker): thƣờng các đối tƣợng này tấn công qua những đƣờng kết nối với hệ thống nhƣ Internet.  Các phần mềm chạy trên hệ thống: chẳng hạn nhƣ spyware, adware,… Các biện pháp ngăn chặn: thƣờng có 3 biện pháp ngăn chặn:  Điều khiển thông qua phần mềm: dựa vào các cơ chế an toàn và bảo mật của hệ thống nền (hệ điều hành), các thuật toán mật mã học,…  Điều khiển thông qua phần cứng: các cơ chế bảo mật, các thuật toán mật mã học đƣợc cứng hóa để sử dụng.  Điều khiển thông qua các chính sách của tổ chức: ban hành các quy định của tổ chức nhằm đảm bảo tính an toàn bảo mật của hệ thống. 8 1.1.3. Mục tiêu và nguyên tắc chung của an toàn bảo mật thông tin Ba mục tiêu của an toàn bảo mật thông tin:  Tính bí mật: thông tin của hệ thống chỉ đƣợc truy cập bởi những ngƣời có thẩm quyền. Các loại truy cập gồm có: đọc (reading), xem (viewing), in ấn (printing), sử dụng chƣơng trình hoặc hiểu biết về sự tồn tại của một đối tƣợng nào đó trong tổ chức. Tính bí mật có thể đƣợc bảo vệ nhờ việc kiểm soát truy cập (theo nhiều kiểu khác nhau) hoặc nhờ các thuật toán mã hóa dữ liệu. Kiểm soát truy cập chỉ có thể thực hiện đƣợc với các hệ thống phần cứng vật lý. Còn đối với các dữ liệu thì phƣơng pháp bảo mật hiệu quả thƣờng là mật mã học.  Tính toàn vẹn dữ liệu: thông tin của hệ thống chỉ đƣợc thay đổi bởi những ngƣời có thẩm quyền.  Tính sẵn sàng: thông tin luôn sẵn sàng đƣợc sử dụng bởi những ngƣời có thẩm quyền. Hai nguyên tắc của an toàn bảo mật thông tin:  Việc thẩm định về bảo mật phải là khó và cần tới tất cả các tình huống, khả năng tấn công có thể đƣợc thực hiện.  Thông tin đƣợc bảo vệ cho tới khi hết giá trị sử dụng hoặc hết ý nghĩa bí mật. 9 1.1.4. Vấn đề bảo vệ bản quyền sản phẩm số Trải qua nhi ều thế kỷ hàng loa ̣t các giao th ức (protocol) và các cơ chế (mechanism) đã đƣợc tạo ra để đáp ứng nhu cầ u an toàn bảo mâ ̣t thông tin khi mà nó đƣợc truyền tải trên các ph ƣơng tiê ̣n vâ ̣t lý (giấ y, sách, báo,…). Thƣờng thì các mục tiêu của an toàn bảo mật thông tin không thể đạt đ ƣợc nếu chỉ đơn thuần d ựa vào các thuật toán toán học và các giao thức , mà để đạt đ ƣợc điều này đòi h ỏi cầ n có các kỹ thuâ ̣t mang tính thủ tu ̣c và s ự tôn tro ̣ng các điề u luâ ̣t. Chẳ ng ha ̣n sự bí mật của các b ức thƣ tay là do s ự phân phát các lá th ƣ đã có đóng d ấu bởi mô ̣t dich ̣ vu ̣ thƣ tín đã đƣợc chấp nhâ ̣n. Tính an toàn v ề mă ̣t vâ ̣t lý của các lá th ƣ là hạn chế (nó có thể bi ̣xem trô ̣m ) nên để đảm bảo s ự bí mật của bức th ƣ pháp luật đã đ ƣa ra qui đinh: ̣ viê ̣c xem th ƣ mà không đ ƣợc sự đồ ng ý của chủ nhân ho ặc những ngƣời có thẩ m quyền là pha ̣m pháp và sẽ bị trừng phạt. Đôi khi mu ̣c đích của an toàn bảo mâ ̣t thông tin la ̣i đa ̣t đƣợc nhờ chính phƣơng tiê ̣n vâ ̣t lý mang chúng, chẳ ng ha ̣n nhƣ tiề n giấ y đòi hỏi phải đƣợc in bằng loại mực và giấ y tố t để không bi ̣làm giả . Về mă ̣t ý t ƣởng việc lƣu giữ thông tin là không có nhiề u thay đổ i đáng kể qua thời gian. Ngày xƣa thông tin thƣờng đƣợc lƣu và vâ ̣n chuyể n trên gi ấy tờ, trong khi giờ đây chúng đ ƣợc lƣu dƣới dạng số hóa và đ ƣợc vận chuyển bằng các hệ thống viễn thông hoă ̣c các hê ̣ thố ng không dây . Tuy nhiên sự thay đổ i đáng kể đế n ở đây chính là khả năng sao chép và thay đổi thông tin . Ngƣời ta có thể tạo ra hàng ngàn mẩ u tin giố ng nhau và không thể phân biê ̣t đƣợc nó với bản gốc. Theo số liệu của MarkMonitor, mỗi năm có đến 53 tỉ lƣợt truy cập vào các website cung cấp các sản phẩm số vi phạm bản quyền, gây thiệt hại 200 tỉ $ [08] . Chính vì vậy nhu cầu đảm bảo an toàn thông tin cho các sản phẩm số là yêu cầu cấp thiết xuất phát từ thực tiễn. Từ đó, một số công cụ đƣợc rất nhiều nhà khoa học nghiên cứu để có thể giúp hiện thực hóa yêu cầu trên nhƣ mâ ̣t mã (cryptography), giấu tin (steganography), nén tin (compression), tƣờng lửa (firewall), mạng riêng ảo (virtual private networks),.. Các công cụ đó có lịch sử lâu đời d ựa trên nề n tảng các thuật toán toán học, số ho ̣c, xác suất và các môn khoa ho ̣c khác . 10 1.1.5. Thực trạng vi phạm bảo vệ bản quyền sản phẩm số Nhƣ đã trình bày ở phần mở đầu, đối tƣợng sản phẩm số trong luận văn đề cập và tập trung nghiên cứu là ảnh số. Hiện nay, có hàng tỉ bức ảnh đƣợc phân phối trên các kênh truyền công cộng. Do chúng có đặc tính dễ sao chép, dễ chỉnh sửa nên nhiều đối tƣợng lợi dụng cố ý đánh cắp, làm sai lệch, giả mạo bức ảnh gốc. Từ đó có thể gây phƣơng hại đến uy tín, thiệt hại về kinh tế,… cho ngƣời chủ sở hữu bức ảnh đặc biệt trong bối cảnh bùng nổ của mạng Internet. Chính vì thế yêu cầu an toàn bảo mật thông tin ngày một trở nên cấp thiết hơn bao giờ hết. Mục kế tiếp sẽ đề cập một số phƣơng pháp bảo vệ bản quyền đối với ảnh số. 11 1.1.6. Phƣơng pháp bảo vệ bản quyền ảnh số Nhƣ đã phân tích ở trên, đứng trƣớc hiện trạng bản quyền tác giả của các sản phẩm ảnh số bị xâm phạm nghiêm trọng, gần đây một số phƣơng pháp bảo vệ bản quyền ảnh số đƣợc đề xuất nhƣ:  Mã hóa: giấu đi ý nghĩa của thông tin. Nếu kẻ gian không hiểu đƣợc thông tin thì sẽ không ăn cắp, sao chép, giả mạo hay xuyên tạc thông tin ấy đƣợc.  “Đánh dấu” tài liệu số: ghi dấu hiệu nào đó vào tài liệu số, gồm một số phƣơng pháp nhƣ: - Thủy vân số: nhúng một dấu hiệu chứng thực bản quyền vào bức ảnh số. - Chữ ký số: thực hiện việc ký trên từng bit ảnh số. Chỉ cần một thay đổi nhỏ trên ảnh thì ngƣời ký cũng biết đƣợc ảnh đã bị sửa đổi. Nhờ chữ ký số, chủ sở hữu cũng chứng minh đƣợc quyền sở hữu của mình với một bức ảnh số. Đây cũng chính là các giải pháp thƣờng đƣợc đề cập đến trong những bài toán an toàn bảo mật thông tin. Ngoài ra, có thể kết hợp các phƣơng pháp trên để đƣa ra phƣơng pháp mới hiệu quả hơn. Ví dụ: mã hóa thủy vân trước khi nhúng, tạo đại diện rồi ký,… Tuy nhiên, việc “mã hóa và giải mã” chỉ đảm bảo an toàn cho dữ liệu trong quá trình truyền thông, còn sau khi giải mã thì dữ liệu số không còn đƣợc bảo vệ nữa. Do đó phƣơng pháp “đánh dấu” tài liệu số thƣờng nhận đƣợc nhiều sự quan tâm hơn. Chính vì vậy luận văn này sẽ tập trung nghiên cứu việc bảo vệ bản quyền cho ảnh số bằng các phƣơng pháp “đánh dấu” tài liệu số nhƣ: thủy vân số, chữ ký số; kết hợp với mã xác thực và hàm băm. 12 1.2. MỘT SỐ KHÁI NIỆM VỀ TOÁN HỌC Để hiểu đƣợc những thuật toán sử dụng trong các hệ mã mât, trong sơ đồ chữ ký điện tử, cũng nhƣ giao thức mật mã. Chúng ta phải có kiến thức nền tảng cơ bản về toán học, lý thuyết thông tin,… Phần này sẽ hệ thống lại một số khái niệm cơ bản về toán học nhƣ đồng dƣ số học (modulo), số nguyên tố, các thuật toán kiểm tra số nguyên tố,... cũng nhƣ một số lý thuyết thông tin nhƣ độ phức tạp thuật toán,... đƣợc sử dụng trong mật mã và an toàn dữ liệu. 1.2.1. Ƣớc chung lớn nhất, bội chung nhỏ nhất 1/. Ƣớc số và bội số Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, thì ta nói rằng a chia hết cho b (kí hiệu b\a). Khi đó b là ước của a, và a là bội của b. Ví dụ: a = 6, b = 2, ta có 6 = 2*3, ký hiệu 2\6. Ở đây 2 là ƣớc của 6, và 6 là bội của 2. Cho các số nguyên a, b ≠ 0, tồn tại cặp số nguyên (q, r) (0  r < |b|) duy nhất sao cho a = b * q + r. Khi đó q gọi là thương nguyên, r gọi là số dư của phép chia a cho b. Nếu r = 0 thì ta có phép chia hết. Ví dụ: a = 13, b = 5, ta có 12 = 5*2 + 3. Ở đây thƣơng là q = 2, số dƣ là r = 3. 2/. Ƣớc chung lớn nhất, bội chung nhỏ nhất Số nguyên d đƣợc gọi là ước chung của các số nguyên a1, a2, …, an nếu nó là ước của tất cả các số đó. Số nguyên m đƣợc gọi là bội chung của các số nguyên a1, a2, …, an nếu nó là bội của tất cả các số đó. Một ƣớc chung d >0 của các số nguyên a1, a2, …, an trong đó mọi ƣớc chung của a1, a2, …, an đều là ƣớc của d, thì d đƣợc gọi là ước chung lớn nhất (UCLN) của a1, a2, …, an. Ký hiệu d = gcd(a1, a2, …, an) hay d = UCLN(a1, a2, …, an). Nếu gcd(a1, a2, …, an) = 1, thì các số a1, a2, …, an đƣợc gọi là nguyên tố cùng nhau. 13 Một bội chung m >0 của các số nguyên a1, a2, …, an trong đó mọi bội chung của a1, a2, …, an đều là bội của m, thì m đƣợc gọi là bội chung nhỏ nhất (BCNN) của a1, a2, …, an. Ký hiệu m = lcm(a1, a2, …, an) hay m = BCNN(a1, a2, …, an). Ví dụ: Với a = 12, b = 15 thì gcd(12,15) = 3; lcm(12,15) = 60. Hai số 8 và 13 là nguyên tố cùng nhau vì gcd(8, 13) = 1. 3/. Tính chất: d=gcd(a1, a2, …, an)  tồn tại các số x1, x2,…, xn sao cho: d = a1x1 + a2x2 + … + anxn Hệ quả: a1, a2, …, an nguyên tố cùng nhau  tồn tại các số x1, x2,…, xn sao cho: 1 = a1x1+a2x2+…+anxn d = gcd(a1, a2, …, an)  gcd(a1/d, a2/d,…, an/d) = 1. m = lcm(a1, a2, …, an)  gcd(m/a1, m/a2,…, m/an) = 1. gcd(m*a1, m*a2, …, m*an) = m*gcd(a1, a2, …, an) (với m ≠ 0). Nếu gcd(a, b) =1 thì lcm(a, b) = a*b Nếu b>0, a = b*q+r thì gcd(a,b) = gcd(b,r). 4/. Thuật toán Euclide tìm ƣớc chung lớn nhất: a). Bài toán Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. Kết quả: gcd(a,b). b). Thuật toán (Mô phỏng bằng ngôn ngữ Pascal) Readln(a, b); While b>0 do Begin r := a mod b; a := b; b := r ; End; Writeln(a); gcd(a,b) = a; 14 c). Ví dụ: a = 30, b = 18; a b r a = b.q + r 30 18 12 30 = 18 * 1+12 18 12 6 18 = 12 * 1+6 12 6 0 12 = 6 * 2 + 0 gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6. 5/. Thuật toán Euclide mở rộng a). Bài toán Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. Kết quả: d = gcd (a,b) và hai số x, y sao cho: a*x + b*y = d. b). Thuật toán (Mô phỏng bằng ngôn ngữ Pascal) Readln(a, b); If b=0 Then Begin d := a; x := 1; y := 0; writeln(d, x, y); End Else Begin x2 := 1; x1 := 0; y2 := 0; y1 := 1; While b>0 Do Begin a := b; b := r; x2 := x1; x1 := x; y2 := y1; y1 := y; End; d := a; x := x2; y := y2; writeln(d, x1, x2); End; End If; 15 1.2.2. Quan hệ “Đồng dƣ” 1/. Khái niệm Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với nhau theo modulo m, nếu chia a và b cho m, ta nhận đƣợc cùng một số dƣ. Ký hiệu: a ≡ b (mod m). Ví dụ: 17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, đƣợc cùng số dƣ là 2. 2/. Các tính chất của quan hệ “Đồng dƣ” a). Quan hệ “đồng dƣ” là quan hệ tƣơng đƣơng trong Z Với mọi số nguyên dƣơng m ta có: a ≡ a (mod m) với mọi a  Z; (tính chất phản xạ). a ≡ b (mod m) thì b ≡ a (mod m); (tính chất đối xứng). a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m); (tính chất bắc cầu). b). Tổng, hiệu, tích các “đồng dƣ” (a+b) (mod m)  [(a mod m) + (b mod m)] (mod m) (a-b) (mod m)  [(a mod m) - (b mod m)] (mod m) (a*b) (mod m)  [(a mod m) * (b mod m)] (mod m) Tổng quát: Có thể cộng hoặc trừ từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một đồng dƣ thức theo cùng modulo m, tức là: k Nếu ai ≡ bi (mod m), i = 1...k, thì k  t a   t b (mod m) với i 1 i i i 1 i i ti = ± 1. Có thể nhân từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một đồng dƣ thức theo cùng modulo m, tức là: k k i 1 i 1 Nếu ai ≡ bi (mod m) với i = 1...k thì ta có:  a i   bi (mod m) 16 3/. Hệ quả Có thể cộng hoặc trừ cùng một số vào hai vế của một đồng dƣ thức. Có thể chuyển vế các số hạng của đồng dƣ thức bằng cách đổi dấu các số hạng đó. Có thể cộng vào một vế của đồng dƣ thức một bội của modulo: a ≡ b (mod m) → a+km ≡ b (mod m) với mọi k  Z Có thể nhân hai vế của một đồng dƣ thức với cùng một số: a ≡ b (mod m) → ac ≡ bc (mod m) với mọi c  Z Có thể nâng lên lũy thừa bậc nguyên không âm cho 2 vế của một đồng dƣ thức: a ≡ b (mod m) → an ≡ bn (mod m) với mọi n  Z+ Có thể chia 2 vế đồng dƣ thức cho một ƣớc chung nguyên tố với modulo: Nếu c\a, c\b, (c,m) = 1, a ≡ b (mod m)  a/c ≡ b/c (mod m) Có thể nhân 2 vế đồng dƣ thức và modulo với cùng một số nguyên dƣơng Nếu a ≡ b (mod m), c >0  ac ≡ bc (mod mc) Có thể chia 2 vế đồng dƣ thức và modulo cho cùng một số nguyên dƣơng là ƣớc chung của chúng: Nếu c\(a,b,m)  a/c ≡ b/c (mod m/c) a ≡ b (mod m)  a ≡ b (mod k) với k \ m a ≡ b (mod m)  gcd(a, m) = gcd(b, m) 17 4/. Các lớp thặng dƣ Quan hệ “đồng dƣ” theo modulo m trên tập Z (tập các số nguyên) là một quan hệ tƣơng đƣơng (vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên tập Z một phân hoạch gồm các lớp tƣơng đƣơng: hai số nguyên thuộc cùng một lớp tƣơng đƣơng khi và chỉ khi chúng có cùng một số dƣ khi chia cho m. Mỗi lớp tƣơng đƣơng đại diện bởi một số duy nhất trong tập Zm={0,1,…,m-1} là số dƣ khi chia các số trong lớp cho m, ký hiệu một lớp đƣợc đại diện bởi số a là [a]m . Nhƣ vậy: [a]m = [b]m  a ≡ b (mod m). Vì vậy ta có thể đồng nhất Zm với tập các lớp tƣơng đƣơng theo modulo m. Zm = {0, 1, 2,…, m-1} đƣợc gọi là tập các “thặng dư đầy đủ” theo modulo m. Mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Zm một số đồng dƣ với mình theo modulo m. 18 1.2.3. Số nguyên tố 1/. Khái niệm Số nguyên tố: là số tự nhiên lớn hơn 1, chỉ có ƣớc là 1 và chính nó. Ví dụ: Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố. Số 2 là số nguyên tố chẵn duy nhất. Nhận xét: số nguyên tố có vai trò và ý nghĩa to lớn trong số học và lý thuyết mật mã. Bài toán kiểm tra tính nguyên tố của một số nguyên dƣơng n và phân tích một số n ra thừa số nguyên tố là các bài toán rất đƣợc quan tâm. 2/. Định lý về số nguyên tố a). Định lý về số nguyên dƣơng > 1 Mọi số nguyên dƣơng n > 1 đều có thể biểu diễn đƣợc duy nhất dƣới dạng: n  P1n1 .P2n2 ...Pknk Trong đó: k, ni ( i =1, 2, .., k) là các số tự nhiên, Pi là các số nguyên tố, từng đôi một khác nhau. b). Định lý Mersenne Cho p = 2k -1, nếu p là số nguyên tố, thì k phải là số nguyên tố. Chứng minh: Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1< a, b< k. Nhƣ vậy: p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E (trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Niutơn). Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử là sai, hay k là số nguyên tố. 19 c). Hàm Euler Cho số nguyên dƣơng n, số lượng các số nguyên dƣơng bé hơn n và nguyên tố cùng nhau với n đƣợc ký hiệu  (n) và gọi là hàm Euler. Nhận xét: Nếu p là số nguyên tố, thì  (p) = p-1 Ví dụ:  Tập các số nguyên không âm nhỏ hơn 7 là Z 7 = {0, 1, 2, 3, 4, 5, 6, 7}.  Do 7 là số nguyên tố, nên tập các số nguyên dƣơng nhỏ hơn 7 và nguyên tố cùng nhau với 7 là Z 7 ={1, 2, 3, 4, 5, 6, 7}. Khi đó /Z/ =  (p) = p-1 = 8-1 = 7. Định lý về Hàm Euler: Nếu n là tích của hai số nguyên tố n = p.q, thì  (n) =  (p).  (q) = (p-1).(q-1). d). Định lý Fecma Nếu p là số nguyên tố, a là số nguyên, thì ap ≡ a (mod p). Nếu p không chia hết a, thì ap-1 ≡ 1 (mod p). Ví dụ: 47 ≡ 4 (mod 7); 47-1 ≡ 1 (mod 7). e). Định lý Euler Nếu gcd(a, m) = 1 thì a  (m) ≡ 1 (mod m). Trƣờng hợp m là số nguyên tố, ta có định lý Fecma. Ví dụ: m = 10,  (m) =  (2).  (5) = 1 * 4 = 4. Ta có: 74 ≡ 1 (mod 10), 94 ≡ 1 (mod 10), 214 ≡ 1 (mod 10). Hệ quả 1: Nếu gcd(c,m)=1 và a ≡ b (mod  (m)) với a, b là các số tự nhiên, thì ca ≡ cb (mod m) và suy ra ca mod m = ca mod  (m) mod m. Chứng minh: a ≡ b (mod  (n)) nên a = b + k  (m), k  Z và vì vậy ca = cb+k  (m) = cb.(c  (m))k ≡ 1 (mod m), theo theo định lý Euler. Nhận xét: Hệ quả trên giúp giảm nhẹ việc tính toán đồng dƣ của lũy thừa bậc cao. Ví dụ: Ta thấy  (15) =  (5).  (3) = 4.2 = 8 và 1004 ≡ 4 (mod 8). Do đó: 21004 (mod 15) = 24 (mod 15) = 16 (mod 15) = 1. 20