Luận văn Thạc sĩ Khoa học máy tính: Tìm hiểu xây dựng thuật toán giấu tin mật và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:76

Thêm vào BST

Báo xấu

40
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài tập trung tìm hiểu và xây dựng một thật toán giấu tin mật vào ảnh kỹ thuật số sao cho lượng thông tin giấu được nhiều và đồng thời có mức độ an toàn cao, tức là ảnh có chứa tin mật và ảnh gốc khác nhau có thể chấp nhận được để ứng dụng được trong nhiều lĩnh vực khác nhau. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Tìm hiểu xây dựng thuật toán giấu tin mật và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG VŨ THỊ TÂM TÌM HIỂU XÂY DỰNG THUẬT TOÁN GIẤU TIN MẬT VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN – 2018
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG VŨ THỊ TÂM TÌM HIỂU XÂY DỰNG THUẬT TOÁN GIẤU TIN MẬT VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 8 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS HỒ VĂN CANH THÁI NGUYÊN - 2018
i LỜI CAM ĐOAN Trong quá trình làm luận văn tôi hoàn toàn sử dụng những kiến thức đã tổng hợp được từ các nguồn tài liệu có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin chịu trách nhiệm về những lời nói trên và nhận mọi hình thức kỷ luật theo quy định nếu như làm sai. Thái Nguyên, tháng 06 năm 2018 Vũ Thị Tâm
ii LỜI CÁM ƠN Để hoàn thành luận văn “Tìm hiểu xây dựng thuật toán giấu tin mật và ứng dụng” em đã nhận được sự hướng dẫn và giúp đỡ nhiệt tình của nhiều tập thể và cá nhân. Trước hết, em xin bày tỏ lòng biết ơn chân thành đến ban lãnh đạo cùng quý thầy cô trong khoa Công nghệ thông tin – Trường Đại học Công nghệ và truyền thông, Đại học Thái Nguyên đã tận tình dạy dỗ, truyền đạt kiến thức, kinh nghiệm và tạo điều kiện thuận lợi cho em trong suốt thời gian học tập và thực hiện đề tài. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn TS. Hồ Văn Canh, người đã gợi cho em những ý tưởng về đề tài, đã tận tình hướng dẫn và giúp đỡ để đề tài được thực hiện và hoàn thành. Xin trân trọng gửi đến gia đình, bạn bè và người thân những tình cảm tốt đẹp nhất đã giúp đỡ động viên trong suốt khóa học và hoàn thành luận văn. Thái Nguyên, tháng 06 năm 2018 Học viên Vũ Thị Tâm
iii DANH MỤC HÌNH Hình 2. 1: Hai lĩnh vực chính của kỹ thuật giấu thông tin ............................. 19 Hình 2. 2: Lược đồ chung cho quá trình giấu tin ........................................... 20 Hình 2. 3: Lược đồ chung cho quá trình giải mã ........................................... 21 Hình 2. 4: Phân loại các kỹ thuật giấu tin ...................................................... 24 Hình 2 .5: Chi tiết khối bytes tiêu đề tập tin BMP. ......................................... 28 Hình 2. 6: Chi tiết khối bytes thông tin tập tin BMP ...................................... 29 Hình 2. 7: Sơ đồ giấu tín SES ......................................................................... 36 Hình 2.8: Minh họa giấu bit b = 0 vào khối nhị phân B ................................ 39 Hình 2. 9: Minh họa giấu dãy bit M = 110 vào 4 khối ảnh nhị phân ............. 44 Hình 3. 1: bảng mã 26 chữ cái latinh ............................................................ 47 Hình 3. 2: Giao diện chính của chương trình ................................................. 62 Hình 3. 3: Giao diện giấu tin .......................................................................... 62 Hình 3. 4: Giao diện giấu file dữ liệu ............................................................. 63 Hình 3. 5: Giao diện tách tin .......................................................................... 63
iv DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 1 BMP Basic Metabolic Panel - Ảnh bipmap 2 GIF Graphics Interchange Format - Ảnh có định dạng GIF 3 JPEG Joint Photographic Experts Group - Ảnh nén JPEG 4 LSB Least Significant Bit - Bit có ý nghĩa thấp nhất 5 PNG Portable Network Graphics - Ảnh nén PNG 6 PoV Pairs of Values - cặp giá trị điểm ảnh chẵn/lẻ 7 HVS Human Vision System - Hệ thống thị giác của con người 8 RGB Red – Green – Blue
v MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CÁM ƠN ................................................................................................... ii DANH MỤC HÌNH ......................................................................................... iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................. iv MỤC LỤC ......................................................................................................... v MỞ ĐẦU ........................................................................................................... 1 1. Đặt vấn đề .................................................................................................. 1 2. Đối tượng nghiên cứu ................................................................................ 1 3. Bố cục của luận văn ................................................................................... 1 CHƯƠNG 1: MỘT SỐ KIẾN THỨC CƠ SỞ .................................................. 3 1.1 Đổi cơ số ................................................................................................. 3 1.2 Độ phức tạp của thuật toán ..................................................................... 5 1.3 Phép chia hết và thuật toán Euclidean ..................................................... 6 1.4 Phần tử nghịch đảo .................................................................................. 8 1.4.1 Định nghĩa ........................................................................................ 8 1.4.2 Thuật toán tìm nghịch đảo của a-1 mod m ........................................ 9 1.5 Đa thức nguyên thủy ............................................................................... 9 1.5.1.Bậc của một phần tử ......................................................................... 9 1.5.2 Hàm – Euler ............................................................................... 10 1.5.3 Phần tử nguyên thủy ....................................................................... 11 1.5.4 Đa thức nguyên thủy....................................................................... 12 1.5.5 Mã Hamming ( The Hamming Codes). ......................................... 14
vi 1.5.6 Mật mã vòng tuyến tính. ................................................................ 15 1.5.7 Đa thức nguyên thủy trong trường hợp GF(2) có cấp từ 2 đến cấp 7 .................................................................................................................. 16 CHƯƠNG 2: TÌM HIỂU TỔNG QUAN VỀ GIẤU TIN VÀ MỘT SỐ THUẬT TOÁN GIẤU TIN MẬT(STEGANOGRAPHY) ............................ 18 2.1 Tổng quan về giấu tin và phân loại ..................................................... 18 2.1.1 Định nghĩa ...................................................................................... 18 2.1.2 Mục đích của giấu tin mật. ............................................................. 19 2.1.3 Mô hình kỹ thuật giấu thông tin cơ bản.......................................... 20 2.1.4. Các đối tượng dùng để giấu tin..................................................... 21 2.2 Giấu tin trong ảnh. ................................................................................. 24 2.3 Tổng quan ảnh BITMAP (BMP). .......................................................... 26 2.3.1 Giới thiệu ảnh BITMAP (BMP). .................................................... 26 2.3.2 Cấu trúc ảnh BITMAP (.BMP). ..................................................... 27 2.4. Một số thuật toán giấu tin trong ảnh và chất lượng ............................ 32 2.4. 1 Kỹ thuật giấu tin LSB. ................................................................... 32 2.4.2 Kỹ thuật giấu tin SES. .................................................................... 34 2.4.3 Kỹ thuật giấu tin theo khối bit ........................................................ 38 2.4.4 Thuật toán Wu-Lee ........................................................................ 41 CHƯƠNG 3: TÌM HIỂU XÂY DỰNG MỘT THUẬT TOÁN GIẤU TIN MẬT TRÊN ẢNH KỸ THUẬT SỐ .............................................................. 46 3.1 Xây dựng ma trận 4 bit. ......................................................................... 46 3.1.1 Chọn đa thức nguyên thủy trong trường GF(2). ............................. 46
vii 3.1.2 Xây dựng không gian các nghiệm của p(x). ................................... 46 3.1.3 Lập bảng mã 26 chữ cái latinh....................................................... 46 3.2 Xây dựng thuật toán nhúng ................................................................... 48 3.2.1 Xây dựng ma trận sinh G ................................................................ 48 3.2.2 Đổi thông điệp m = m1…..mn sang dãy nhị phân theo bảng A .. 48 3. 3 Trích chọn (extraction) ......................................................................... 50 3.4 Đánh giá độ an toàn của hệ thống ......................................................... 53 3.5 So sánh độ an toàn của 2 hệ thống ....................................................... 57 3.6 Nhận xét đánh giá................................................................................... 59 3.7. Chương trình thử nghiệm ..................................................................... 60 3.7.1 Môi trường cài đặt .......................................................................... 60 3.7.2 Mô hình hệ thống ............................................................................ 60 KẾT LUẬN ..................................................................................................... 63 TÀI LIỆU THAM KHẢO ............................................................................... 66
1 MỞ ĐẦU 1. Đặt vấn đề Hiện nay có nhiều thuật toán giấu tin mật và thủy vân đã được công bố [1]. Trong đó cũng có nhiều thuật toán giấu tin mật đã bị phát hiện bằng các kỹ thuật thống kê toán học. Vì vậy một vấn đề đặt ra là: Đánh giá mức độ an toàn của một thuật toán giấu tin như thế nào? Đặc biệt là hệ thống giấu tin mật phục vụ an ninh quốc phòng. Ta biết rằng, lượng thông tin được giấu vào trong một ảnh là rất quan trọng nhưng phải đảm bảo được mức độ an toàn của hệ thống giấu. Đề tài tập trung tìm hiểu và xây dựng một thật toán giấu tin mật vào ảnh kỹ thuật số sao cho lượng thông tin giấu được nhiều và đồng thời có mức độ an toàn cao, tức là ảnh có chứa tin mật và ảnh gốc khác nhau có thể chấp nhận được để ứng dụng được trong nhiều lĩnh vực khác nhau. Đó là mục đích và ý nghĩa của đề tài luận văn: Tìm hiểu xây dựng một thuật toán giấu tin mật và ứng dụng. Trong phạm vi đề tài luận văn có giới thiệu một hệ thống steganography mới và đồng thời đưa ra so sánh về mức độ an toàn giữa hệ thống được đề xuất và hệ thống đã được công bố. 2. Đối tượng nghiên cứu Đề tài tập trung nghiên cứu các đối tượng sau đây: - Tập trung tìm hiểu, đánh giá ưu nhược điểm của một số thuật toán giấu tin mật trong ảnh kỹ thuật số. - Xây dựng thuật toán giấu tin mật mới. 3. Bố cục của luận văn Nội dung của luận văn gồm có: Phần mở đầu, ba chương chính, kết luận, mục lục và tài liệu tham khảo. Nội dung cơ bản của luận văn được trình bày như sau:
2 Phần mở đầu: Nêu lý do chọn đề tài, đối tượng nghiên cứu và bố cục của luận văn Chương 1: MỘT SỐ KIẾN THỨC CƠ SỞ Chương này sẽ trình bày một số kiến thức toán học bổ trợ Chương 2: TỔNG QUA VỀ GIẤU TIN VÀ MỘT SỐ THUẬT TOÁN GIẤU TIN MẬT TRONG ẢNH KỸ THUẬT SỐ Chương này sẽ phân tích, đánh giá một số thuật toán giấu tin mật đã được công bố:Kỹ thuật LSB, Kỹ thuật SES, Kỹ thuật giấu tin theo khối bit, thuật toán Wu-Lee. Chương 3: TÌM HIỂU XÂY DỰNG MỘT SỐ THUẬT TOÁN GIẤU TIN MẬT Chương này sẽ trình bày thuật toán đề xuất và đánh giá độ an toàn của từng thuật toán. Cài đặt thử nghiệm việc giấu tin dựa theo thuật toán đề xuất.
3 CHƯƠNG 1: MỘT SỐ KIẾN THỨC CƠ SỞ 1.1 Đổi cơ số Số mà chúng ta sử dụng hàng ngày (0, 1, 2, 3, …, 7, 8, 9 ) là các số được biểu diễn theo cơ số 10. Ví dụ 1: Tóm lại, một số n tổng quát viết theo cơ số 10 bao giờ cũng có thể được biểu diễn một cách duy nhất dưới dạng: trong đó, , nói cách khác ai є{0,1,2,…,9} với i = 0,1,2,..,k-1; với ak ≠ 0. Ứng với mỗi số n, biểu diễn ở (1) là duy nhất. Do đó, thay vì viết số n, ta viết n dưới dạng: , con số 10 biểu thị cơ số. Trong thực tế ta cần số n biểu thị dưới dạng có số b tùy ý như sau: hay viết ngắn gọn là: , tức là : Nếu b = 2, ta có số n biểu diễn dưới dạng cơ số 2. Khi đó:
4 Trường hợp thì thay là những con số mà người ta có thể dùng các chữ cái Latinh. Ví dụ 2: Ví dụ 3: Khi b = 26, người ta sử dụng các chữ cái từ A đến Z thay cho 0,1,..,25. Ví dụ 4: Hãy đổi các số sang cơ số 26: Ta có : hay Ví dụ 5 : Hãy đổi 106 sang cơ số lần lượt là 2, 7, và 26. Ta có: . Để chứng minh rằng: các biểu diễn trên là duy nhất ứng với mỗi cơ số cụ thể, ta có mệnh đề sau đây: Mệnh đề: Xét không gian các đa thức V, cấp n tùy ý trên trường vô hướng K nào đó. Ta xét một tập hợp S = { 1, x, x2, x3,..., xn } trong V . Khi đó, S là một cơ sở trong V. Chứng minh: Ta chỉ cần chứng minh rằng các vector trong S là độc lập tuyến tính. Muốn vậy, cho α0, α1, α2,..., αn và xét tổ hợp tuyến tính : α0 + α1x +... + αn = 0 (1)
5 Ta cần chứng minh rằng khi đó αi = 0, đối với mọi i = 0,1, 2,...,n. Thật vậy, giả sử, n= 1, khi đó, lấy đạo hàm 2 vế của (1), ta có α1 = 0 và do đó, α0 = 0. Giả thiết đẳng thức (1) đúng cho n = k -1, ta sẽ chứng minh rằng đẳng thức (1) đúng cho cả n = k. Bằng cách lấy đạo hàm của đẳng thức (1) n-lần , ta suy ra αn = 0. Nhưng theo quy nạp ta đã có α0, α1,..., αn-1 = 0, vậy mệnh đề được chứng minh. 1.2 Độ phức tạp của thuật toán Định nghĩa 1: Cho và là hai hàm nhiều biến số xác định trong miền gồm tập hợp các bộ k số nguyên dương. Giả sử có tồn tại hai hằng số B và C thỏa mãn thì ta nói rằng f bị chặn bởi g và viết là Ví dụ 6: a. Cho f(n) là một đa thức cấp d mà các hệ số của nó dương. Khi đó ta có : . b. Cho ԑ là một số dương bé tùy ý ( no matter how small). Khi đó, chúng ta có thể chứng minh được rằng: c. Ký hiệu f(n) là số k thành phần (digits) nhị phân trong n ( ví dụ n = 10110 thì => f (n) = 5 ). Khi đó có thể dễ dàng thấy rằng f(n) = O(log n). Chú ý nếu viết f(n) = O(1) thì có nghĩa là f(n) bị chặn bởi một hằng số nào đó. Bây giờ, chúng ta trở lại bài toán ước lượng thời gian của chúng ta đối với phép nhân một số nguyên k_bit với một số nguyên khác l_bit. Ta có: Thời gian (k_bit x l_bit) = O(k.l).
6 Một cách tổng quát có: Thời gian(nxm) = O((log n)(log m)). Ví dụ 7: Hãy ước lượng thời gian cần thiết để đổi một số nguyên k_bit thành cơ số 10. Giải: Cho n là một số nguyên được viết dưới dạng cơ số nhị phân k_bit. Thuật tóan đổi như sau: Chia số n cho 10 = (1010)2 . Còn lại bằng một trong các số nguyên 0, 1, 10, 11, 100, 101, 110, 111, 1000 hoặc 1001. Thời gian chuyển số nhị phân n k_bit về một số nguyên cơ số 10 là: O( log2n). Định nghĩa 2: Một thuật toán để thực hiện giải trên máy tính các số nguyên n1, n2, …, nr có k1, k2, …, kr bít tương ứng được gọi là thuật toán thời gian đa thức nếu có tồn tại các số nguyên d1, d2, …, dr sao cho số các toán tử bít đòi hỏi để biểu diễn thuật toán là 1.3 Phép chia hết và thuật toán Euclidean Cho trước hai số nguyên a và b và một số nguyên dương ( m ≥ 1). Ta nói rằng a chia hết cho b theo modulo m nếu a – b = k.m với k = 0, 1, 2 , ... và ta viết a ≡ b mod m. Giả sử p là một số nguyên tố, α là một số nguyên không âm. Khi đó, chúng ta ký hiệu pα|| b để chỉ ra rằng pα là lũy thừa cao nhất α của p mà b chia hết cho pα, tức là b chia hết cho pα và b không chia hết cho pα+1. Và trong trường hợp đó, ta nói rằng pα là ước đúng của số b. Nếu ab chia hết cho số nguyên tố p khi đó, hoặc a chia hết cho b (ta ký hiệu p|a) hoặc b chia hết cho p( p|b).
7 Nếu m|a và n|a nếu m,n là số nguyên tố sao cho UCLN(m, n) = 1. Khi đó m.n|a. Chú ý! Ta dùng kí hiệu (a, b) để chỉ ước chung lớn nhất của a và b. Tức là thay vì viết UCLN(a, b) ta viết (a, b).  Thuật toán Euclidean và thuật toán Euclidean mở rộng. Trước hết, ta trình bày bổ đề sau: Bổ đề 1: Cho m,n là những số nguyên, ta giả sử m ≥ n. Ta chia m cho n và nhân được kết quả: khi đó Bổ đề 2: (m, 0) = m với mọi m nguyên. Từ bổ đề nêu trên, ta có thuật toán tìm (m, n) như sau: Input: Cho trước m và n ( già sử m ≥ n) là hai số nguyên. Output: Tìm (m, n). Thuật toán: Bước 1: Nếu n = 0, m là đáp số! Bước 2: và quay lại bước 1. Mệnh đề 1: Số các phép toán trong thuật toán Euclide không vượt quá 2log2n. Mệnh đề 2: Nếu (m, n) = d thì có tồn tại hai số nguyên x, y sao cho: mx + ny = d.
8 Từ mệnh đề 2, ta có thuật toán Euclide mở rộng tìm 3 số x, y, d sao cho: mx + ny = d sau đây: Input: m, n ( giá trị m ≥ n) Output: x, y, d: mx + ny = d. Thuật toán: Khởi tạo: Cho ( a1, a2, a3 ), ( b1, b2, b3), ( c1, c2, c3 ) là các vector. Bước 1: ( a1, a2, a3 ) ← ( 0, 1, m ); ( b1, b2, b3) ← ( 0, 1, n ); Bước 2: Nếu b3 = 0 thì dừng và ( a1, a2, a3 ) là đáp số bài toán. Bước 3: Đặt ; ( c1, c2, c3 ) ← ( a1, a2, a3 ) – q.( b1, b2, b3); ( a1, a2, a3 ) = ( b1, b2, b3); ( c1, c2, c3 ) = ( b1, b2, b3); và quay lại bước 2. Đáp số: a1 = x, a2 = y, a3 = d; 1.4 Phần tử nghịch đảo 1.4.1 Định nghĩa Cho m là một số nguyên dương và a là một số nguyên. Nếu tồn tại một số nguyên b sao cho ab ≡ 1 mod n thì b được gọi là phần tử nghịch đảo của a theo modulo m. Ta thấy rằng, nếu b là phần tử nghịch đảo của a theo modulo m thì mọi số nguyên có dạng b + km cũng là nghịch đảo của a, trong đó k = 0, ±1, ±2, ... Tuy nhiên trong các số có dạng b + km, có tồn tại duy nhất một số nguyên dương nằm giữa 0 và m và số đó được kí hiệu là a-1 mod m.
9 1.4.2 Thuật toán tìm nghịch đảo của a-1 mod m Cho a, m > 0, ta kí hiệu d = ( a, m). Khẳng định 1: Điều kiện cần và đủ để tồn tại nghịch đảo a-1 của số a là d =1. Chứng minh: Thật vậy, Giả sử d > 1, khi đó ta có: a = a1.d, m = m1.d với a1, m1 nguyên (dương ). Nếu tồn tại a-1 thì: Vì a1, a-1, k, m1 nguyên nên phải là số nguyên. Nhưng do d> 1 nên hệ thức (1) không thể xảy ra. Nó chỉ xảy ra khi và chỉ khi d = 1. Đó là điều ta cần chứng minh. Chú ý! Sử dụng thuật toán Euclide mở rộng ta có thể tìm được a-1, nếu d = 1 và khi đó giá trị a-1 nằm trong ô a2 của thuật toán. 1.5 Đa thức nguyên thủy Trước khi trình bày khái niệm đa thức nguyên thủy, chúng ta sẽ giới thiệu qua về phần tử nguyên thủy. 1.5.1 Bậc của một phần tử Định nghĩa 1: Cho a và m là 2 số nguyên dương tùy ý. Khi đó, nếu tồn tại một số nguyên dương bé nhất mà thỏa mãn điều kiện: thì số h được gọi là bậc của phần tử a theo modulo m và viết là:
10 Chú ý! Không phải với mọi cặp số nguyên dương a, m đều tồn tại số h thỏa mãn điều kiện (2). Cụ thể ta có mấy khẳng định sau đây: Khẳng định 1: Cho hai số nguyên dương a và m. Để tồn tại số guyên dương h có tính chất , điều kiện cần và đủ là (a, m) = 1 { (a, m) là kí hiệu ước số chung lớn nhất của a và m}. Chứng minh: Thật vậy, giả sử trái lại, (a, m) = d ≥ 2 và có tồn tại h nguyên dương mà ah ≡ 1 mod m. Nhưng do giả thiết phản chứng, ta có a = d.a1 , m = d.m1 với a1, m1 nguyên. Khi đó hay tương đương : (3) Do h, d, a1, k, m1 nguyên nên biểu thức phải là số nguyên (có thể âm ). Do đó đẳng thức (3) là vô lí, vì d ≥ 2. Vậy khẳng định được chứng minh. Khẳng định 2: Giả sử h = ordm(a) . Khi đó: + a, a2, ..., ah là những số khác nhau thuộc Zm*. + Nếu ak ≡ 1 mod m thì h phải là ước số của k, đặc biệt h là ước của hàm Φ(m). 1.5.2 Hàm – Euler Định nghĩa 2: Ta kí hiệu với m là số nguyên dương nào đó. Khi đó hàm (m) – Euler được định nghĩa là: (Lực lượng của tập hợp ). Như vậy hàm (m) – Euler chính là số phần tử mà nguyên tố với m ( trừ x = 0).
11 Các tính chất của hàm (m). - Tính chất 1: (1) = 0. - Tính chất 2: ) với p là ước số nguyên tố của m. - Tính chất 3: Nếu với p1, p2, ..., pk là các số nuyên tố khác nhau còn e1, e2, ..., ek ≥ 0 là các số nguyên nào đó. Khi đó: . - Tính chất 4: Nếu m, n là những số tự nhiên sao cho (m, n) = 1, khi đó, ϕ(m.n) = ϕ(m).ϕ(n) , đặc biệt nếu m là số nguyên tố m = p thì : ϕ(m) = ϕ(p) = p– 1. - Tính chất 5: Nếu m = p.q trong đó p, q là 2 số nguyên tố phân biệt thì : ϕ(m)= ϕ(p.q) = (p – 1)(q – 1). - Tính chất 6: Nếu n = pk với p là số nguyên tố còn k là số nguyên dương, thế thì: ϕ(n) = pk-1(p – 1). - Tính chất 7: Với mọi n ≥ 5, ta có: - Tính chất 8 ( Định lý Euler) : Nếu (a, m) = 1 thì aϕ(m) ≡ 1 mod m với a, m nguyên dương. - Tính chất 9: Cho n = p.q , trong đó, p,q là hai số nguyên tố phân biệt. Khi đó: . 1.5.3 Phần tử nguyên thủy Định nghĩa 3: Cho g là một số nguyên dương và m là một số nguyên (m≥ 2) sao cho (g, m) = 1. Nếu ϕ(m) là bậc của g theo modulo m thì g được gọi là phần tử nguyên thủy trong . Một số định lý quan trọng: