Mã hóa và an ninh mạng ( Chapter 8)

Chương 8: Giới thiệu Lý thuyết số Fourth Edition by William Stallings Lecture slides by Lawrie Brown Các số nguyên tốPrime Numbers Là các số nguyên dương chỉ có ước số là 1 và chính nó. Chúng không thể được viết dưới dạng tích của các số khác 1 là số nguyên tố, nhưng không quan tâm đến nó 2, 3, 5, 7 là số nguyên tố; 4, 6, 8, 9, 10 không phải là số nguyên tố Các số nguyên tố là trung tâm của lý thuyết số Danh sách các số nguyên tố nhỏ hơn 200 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 Phân tích ra thừa số nguyên tốPrime Factorisation Phân tích ra thừa số nguyên tố số N tức là viết nó dưới dạng tích của các số nguyên tố: n=a x b x c Lưu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán nhân các số để nhận được tích eg. 91=7x13 ; 3600=24x32x52 Các số nguyên tố cùng nhau và GCD Hai số a và b không có ước chung nào ngoài 1, được gọi là nguyên tố cùng nhau Ví dụ: 8 và 15 là nguyên tố cùng nhau, vì ước của 8 là 1, 2, 4, 8, còn ước của 15 là 1, 3, 5, 15. Chỉ có 1 là ước chung Ngược lại có thể xác định ước chung lớn nhất bằng cách trong các phân tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và lấy bậc lũy thừa nhỏ nhất. eg. 300=22x31x52 18=21x32 hence GCD(18,300)=21x31x50=6 Định lý Ferma Fermat's Theorem ap-1 = 1 (mod p) trong đó p là số nguyên tố và GCD(a, p) = 1 Hay ap = a (mod p) Được dùng trong khoá công khai và kiểm tra tính nguyên tố Ví dụ: 27-1 mod 7 = 26 mod 7 = 64 mod 7 = 1 35-1 mod 5 = 34 mod 5 = 81 mod 5 = 1 Hàm OleEuler Totient Function ø(n) Khi thực hiện phép tính đồng dư n Tập đầy đủ các phần dư: 0, 1, 2, …, n-1 Xét tập rút gọn của tập phần dư trên bao gồm các số nguyên tố cùng nhau với n Ví dụ với n = 10 Tập đầy đủ các phần dư là {0,1,2,3,4,5,6,7,8,9} Tập rút gọn các phần dư nguyên tố với 10 là {1,3,7,9} Số các phần tử của tập rút gọn trên là giá trị của hàm Ole ø(n) Euler Totient Function ø(n) Muốn tính ø(n) việc đếm số các số ngưyên tố cùng nhau với n và nhỏ hơn n được loại bỏ vì đây là bài toán tốn nhiều công sức Nói chung cần biểu thức phân tích ra thừa số Nếu p là số nguyên tố ø(p) = p-1 Nếu p và q là hai số nguyên tố khác nhau ø(p.q) = (p-1)(q-1) Vidụ ø(37) = 36 ø(21) = (3–1)×(7–1) = 2×6 = 12 Tính ø(n) Ví dụ: ø(72) = ø(8.9) = ø(8). ø(9) = ø(23).ø(32) = = (23-22)(32-31) = 4.6 = 24 Định lý OleEuler's Theorem Tổng quát hoá của Định lý Ferma aø(n) = 1 (mod n) với mọi a,n trong đó gcd(a,n)=1 eg. a=3;n=10; ø(10)=4; hence 34 = 81 = 1 mod 10 a=2;n=11; ø(11)=10; hence 210 = 1024 = 1 mod 11 Kiểm tra tính nguyên tố Primality Testing Giả sử cần phải tìm một số nguyên tố rất lớn Lấy một số đủ lớn. Phương pháp truyền thống là thử bằng phép chia Chia cho tất cả các số (chỉ cần nguyên tố) nhỏ hơn hoặc bằng căn bậc hai của số đó. Chỉ hiệu quả khi các số nhỏ Có phương pháp khác sử dụng các phép kiểm tra tính nguyên tố thống kê dựa trên các tính chất Mà mọi số nguyên tố phải thỏa mãn Nhưng có một số số không nguyên tố, gọi là giả nguyên tố cũng thoả mãn tính chất đó. Thuật toán Miller - Rabin Là phép kiểm tra dựa trên Định lý Ferma Thuật toán như sau:TEST (n) is: 1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq 2. Select a random integer a, 1 0.99999 Phân bố nguyên tố Prime Distribution Định lý về số nguyên tố khẳng định số nguyên tố xuất hiện sau mỗi khoảng ln n số nguyên (xét các sô trong kích thước n) Như vậy bỏ qua số chẵn và các bội số của 5, ta cần kiểm tra 0.4 ln n số trong kích thước n để tìm được 1 số nguyên tố. Lưu ý đây chỉ là trung bình, vì có lúc các số nguyên rất gần nhau và có lúc lại rất xa nhau. Định lý phần dư Trung HoaChinese Remainder Theorem Sử dụng để tăng tốc độ tính toán Modulo Tính toán trên modulo của một tích các số mod M với M= m1m2..mk Định lý phần dư Trung Hoa cho phép làm việc trên từng Modulo mi riêng biệt Vì thời gian tính toán tỷ lệ với kích thước nên điều đó sẽ nhanh hơn tính toán trên toàn bộ M Chinese Remainder Theorem Có thể triển khai Định lý Trung Hoa theo một số cách Để tính A mod M Trước hết ta cần tính tất cả ai = A mod mi Tính Ci theo công thức sau với Mi = M/mi Sau đó sử dụng công thức Ví dụ Định lý phần dư Trung Hoa Tính toán trên Modulo lớn Giả sử ta phải tính: A = 17130 mod 35 Ta thấy 35 = 5.7 Ta tính 17130 mod 5 và 17130 mod 7 17130 mod 5 = 2130 mod 5 = 2128 22 mod 5 = 24.32 22 mod 5 = 24.32 mod 5 22 mod 5 = 4 17130 mod 7 = 3130 mod 7 = 33.43 .3 mod 7 = 33.43 mod 7. 3 mod 7 = (-1).3 mod 7 = 4 7-1 mod 5 = 3; 5-1 mod 7 = 3 A = (4.7.3 + 4.5.3) mod 35 = (84 + 60) mod 35 = (14 + 25) mod 35 = 4 Căn nguyên tốPrimitive Roots Từ Định lý Ole ta có aø(n) mod n=1 Xét m để am mod n = 1, GCD(a,n)=1 Có m = ø(n) thỏa mãn nhưng có thể có giá trị nhỏ hơn Khi đạt được m như vậy sẽ có vòng lặp Nếu giá trị m = ø(n) là số dương nhỏ nhất thoả mãn công thức trên thì a được gọi là căn nguyên tố của n. Nếu p là số nguyên tố, thì các luỹ thừa thích hợp của a: a0, a1, …sẽ sinh ra nhóm modulo p. Điều này có ích nhưng tương đối khó tìm Ví dụ căn nguyên tố Xét số nguyên tố p = 5 và xét xem a = 2 có phải là căn nguyên tố của 5 không? 2 mod 5 = 2; 22 mod 5 = 4; 23 mod 5 = 3; 24 mod 5 = 1 Rõ ràng m= 4= ø(5) l à số mũ nhỏ nhất có t ính chất 2m mod 5 = 1, nên 2 là căn nguyên tố của 5. Xét số n = 8 và xét xem a = 3 có phải là căn nguyên tố của 8 không? 3 mod 8 = 3; 32 mod 8 = 1; 33 mod 8 = 3; 34 mod 8 = 1 Rõ ràng m= 2 < 4 = ø(8) l à số mũ nhỏ nhất có tính chất 3m mod 8 = 1, nên 3 không là căn nguyên tố của 8. Logarit rời rạcDiscrete Logarithms Bài toán ngược của bài toán lũy thừa là tìm logarit rời rạc của một sô modulo p Tức là tìm x sao cho ax = b mod p Hay còn được viết là x = loga b mod p or x= inda,p(b) Nếu a là căn nguyên tố thì luôn luôn tồn tại, ngược lại thì có thể không x = log2 3 mod 13 = 4 bằng cách thử lần lượt x = log3 4 mod 13 (tìm x: 3x = 4 mod 13) không có lời giải Trong khi lũy thừa là bài toán dễ dàng, thì bài toán logarit rời rạc là bài toán khó. Summary have considered: prime numbers Fermat’s and Euler’s Theorems & ø(n) Primality Testing Chinese Remainder Theorem Discrete Logarithms