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

 Chương 4: Trường hữu hạnChapter 4 – Finite Fields Fourth Edition by William Stallings Lecture slides by Lawrie Brown Mở đầuIntroduction Giới thiệu về cấu trúc đại số - trường hữu hạn Đóng vai trò quan trọng trong lý thuyết mã – AES, đường cong Elip, IDEA, khoá công khai Liên quan đến các phép toán trên “số”: ở đây sẽ xét thế nào là “số” và nhiều kiểu phép toán khác nhau Bắt đầu từ khái niệm nhóm, vành, trường của đại số trừu tượng Nhóm - Group Cho một tập các phần tử hoặc “số” Và một phép toán, mà kết quả cũng là một phần tử của tập hợp đó (tính đóng) Thỏa mãn: Tính kết hợp (a.b).c = a.(b.c) Có đơn vị e: e.a = a.e = a Có nghịch đảo a-1: a.a-1 = e Nếu có tính giao hoán a.b = b.a, thì gọi là nhóm Aben Nhóm xiclic - Cyclic Group Định nghĩa lũy thừa như là việc áp dụng lặp phép toán: Ví dụ: a3 = a.a.a Và đơn vị e=a0 Nhóm được gọi là xiclic nếu mọi phần tử đều là lũy thừa của một phần tử cố định nào đó: Chẳng hạn b = ak đối với a và mỗi b trong nhóm Khi đó a được gọi là phần tử sinh của nhóm Vành - Ring Tập các “số” với hai phép toán được gọi là cộng và nhân, trong đó Với phép cộng là nhóm Aben Với phép nhân có tính đóng và tính giao hoán tính phân phối đối với phép cộng a(b+c) = ab + ac Nếu phép nhân có tính giao hoán thì tạo thành vành giao hoán Nếu phép nhân có nghịch đảo và không có thương 0, thì nó tạo thành miền nguyên Trường - Field Trường là một tập với hai phép toán Với phép cộng là nhóm Aben Với phép nhân là nhóm Aben, trừ phần tử 0 là vành Có thể nói là có các phép toán cộng, trừ, nhân, chia số khác 0 a – b = a + (-b) a / b = a.b-1 Số học trên moduleModular Arithmetic Định nghĩa phép toán Module: a mod n là phần dư khi chia a cho n Sử dụng quan hệ tương đương trên tập số nguyên a ≡ b mod n khi chia cho n, a và b có phần dư như nhau Ví dụ: 100 ≡ 34 mod 11 Số b được gọi là đại diện của a, nếu a ≡ b mod n (a = qn + b) và 0 <= b <= n-1. Module 7 -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7 ở đây 2 là đại diện của –12, -5, 2 và 9. ... -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ... Ước số - Divisors Số b không âm được gọi là ước số của a, nếu có số m sao cho a = mb với a, b, m đều nguyên. Tức là a chia hết cho b, ký hiệu b|a Ví dụ: 1, 2, 3, 4, 6, 8, 12, 24 là các ước số của 24 Các phép toán số học trên ModuleModular Arithmetic Operations Cho trước một số n Có thể thực hiện các phép toán trên các số nguyên Số học trên module là thực hiện các phép cộng, nhân thông thường sau đó rút gọn lại bằng phép lấy module Có thể rút gọn tại bất cứ thời điểm nào (a+b) mod n = [a mod n + b mod n] mod n (a.b) mod n = [a mod n . b mod n] mod n Số học trên module Modular Arithmetic Có thể thực hiện các phép toán trên các đại diện: Zn = { 0, 1, 2, 3, …, n-1 } Zn với các phép toán module tạo thành vành giao hoán có đơn vị Các chú ý: nếu (a+b)≡(a+c) mod n thì b≡c mod n Nhưng (ab)≡(ac) mod n thì b≡c mod n chỉ khi nếu a là nguyên tố cùng nhau với n Module 8 với phép cộng Modulo 8 Addition Example Ví dụ các phép toán trên module Áp dụng các tính chất của modulo: (11*19 + 1017) mod 7 = ((11*19) mod 7 + 1017 mod 7) mod 7 = ((11 mod 7* 19 mod 7) mod 7 + (10 mod 7)17 mod 7) mod 7= ((4.(-2)) mod 7 + (((32)2)2)2 * 3 mod 7)mod 7= ((-1) mod 7 + ((22)2)2 * 3 mod 7)mod 7 = (-1 + 5) mod 7 = 4 Ước số chung lớn nhấtGreatest Common Divisor (GCD) Là bài toán chung của lý thuyết số. GCD(a,b) là ước số chung dương lớn nhất của a và b. Ví dụ: GCD(60,24) = 12 Nếu hai số a, b nguyên tố cùng nhau thì GCD(a, b) = 1, Ví dụ GCD(8,15) = 1, 8 v à 15 là hai số nguyên tố cùng nhau Thuật toán Ơcơlit Euclidean Algorithm Tính chất GCD(a,b) = GCD(b, a mod b) Thuật toán Ơcơlit tìm GCD(a, b): EUCLID(a,b) 1. A = a; B = b 2. if B = 0 return A = gcd(a, b) 3. R = A mod B 4. A = B 5. B = R 6. goto 2 Example GCD(1970,1066) 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 162 = 1 x 94 + 68 gcd(94, 68) 94 = 1 x 68 + 26 gcd(68, 26) 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) 16 = 1 x 10 + 6 gcd(10, 6) 10 = 1 x 6 + 4 gcd(6, 4) 6 = 1 x 4 + 2 gcd(4, 2) 4 = 2 x 2 + 0 gcd(2, 0) Trường Galoa - Galois Fields Trường Galoa đóng vai trò quan trọng trong lý thuyết mã Có thể chứng minh được rằng số các phần tử của trường hữu hạn bằng lũy thừa của pn của sô nguyên tố p Được biết đến là trường Galoa, ký hiệu GL(pn) Thường sử dụng các trường: GF(p) GF(2n) Trường Galoa GL(p) Galois Fields GF(p) GL(p) gồm tập {0,1, … , p-1} Với các phép toán cộng và nhân module GL(p) tạo thành trường vì mọi a thuộc {0,1, … , p-1} đều có phần tử nghịch đảo a-1: a . a-1 = 1 Như vậy trên GL(p) ta có thể thực hiện các phép toán cộng, trừ, nhân, chia. GF(7) Multiplication Example Tìm số nghịch đảoFinding Inverses EXTENDED EUCLID(m, b) 1. (A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b) 2. if B3 = 0 return A3 = gcd(m, b); no inverse 3. if B3 = 1 return B3 = gcd(m, b); B2 = b–1 mod m 4. Q = A3 div B3 5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3) 6. (A1, A2, A3)=(B1, B2, B3) 7. (B1, B2, B3)=(T1, T2, T3) 8. goto 2 Giải thích Các quan hệ sau là bất biến: mT1 + bT2 = T3; mA1 + bA2 = A3; mB1+bB2=B3 Vì ban đầu: m.1 + b.0 = m; m.0 +b.1 = b Khi B3 = 1: mB1+bB2=1 bB2 = 1+ mB1 bB2 = 1 mod m Do đó: B2 = b-1 mod m Inverse of 550 in GF(1759) Số học đa thứcPolynomial Arithmetic Sử dụng các đa thức bậc nhỏ hơn hoặc bằng n f(x) = anxn + an-1xn-1 + … + a1x + a0 = ∑ aixi Có một số cách khác nhau Có thể thực hiện các phép toán thông thường trên đa thức Các phép toán trên đa thức với các hệ số trên module p Các phép toán trên đa thức với các hệ số trên mod p và sau đó lấy mod m(x) (modulo theo đa thức m(x)) Phép toán đa thức thông thườngOrdinary Polynomial Arithmetic Phép toán đa thức thông thường Cộng trừ các hệ số tương ứng Nhân mọi hệ số với cùng một số eg let f(x) = x3 + x2 + 2 and g(x) = x2 – x + 1 f(x) + g(x) = x3 + 2x2 – x + 3 f(x) – g(x) = x3 + x + 1 f(x) x g(x) = x5 + 3x2 – 2x + 2 Phép toán đa thức với module hệ số Cho số nguyên tố p tùy ý Tính các hệ số theo module p Tạo thành vành Quan tâm đến mod 2 là mọi hệ số là 0 hoặc 1 eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1 f(x) + g(x) = x3 + x + 1 f(x) x g(x) = x5 + x2 Phép toán đa thức với module đa thức Cho đa thức g(x) Viết f(x) dạng: f(x) = q(x) g(x) + r(x) Có thể coi r(x) là phần dư Ta viết: r(x) = f(x) mod g(x) Nếu không có phần dư ta nói g(x) là ước của f(x) hay g(x) chia hết f(x) Trong trường hợp g(x) không có ước ngoài 1 và chính nó, thì ta nói g(x) là đa thức nguyên tố hoặc không rút gọn được VD x3 + x + 1 là nguyên tố; x4 + 1 không nguyên tố (x4 + 1 = (x + 1)(x3 + x2 + x + 1) Số học đa thức theo module của đa thức nguyên tố tạo thành trường Đa thức ước chung lớn nhất c(x) = GCD(a(x), b(x)) nếu c(x) là đa thức bậc lớn nhất mà chia hết cả a(x), b(x) Có thể điều chỉnh thuật toán Euclid để tìm EUCLID[a(x), b(x)] 1. A(x) = a(x); B(x) = b(x) 2. if B(x) = 0 return A(x) = gcd[a(x), b(x)] 3. R(x) = A(x) mod B(x) 4. A(x) = B(x) 5. B(x) = R(x) 6. goto 2 Phép toán đa thức với module đa thức Có thể tính trên trường GF(2n) Đa thức với các hệ số module 2 và bậc nhỏ hơn bằng n, Có thể rút gọn theo module của đa thức nguyên tố bậc n (đối với phép nhân) Tạo thành trường hữu hạn Có thể tìm được nghịch đảo nhờ thuật toán Euclide mở rộng Example GF(23) Xét về mặt tính toán Vì các hệ số là 0, 1 nên các đa thức có thể biểu diễn như các xâu bit Phép cộng trở thành XOR trên các xâu bit đó Nhân trở thành Shift và XOR Phép tính module đa thức nguyên tố thực hiện bằng phép lặp thế bậc cao nhất với phần dư Computational Example in GF(23) have (x2+1) is 1012 & (x2+x+1) is 1112 so addition is (x2+1) + (x2+x+1) = x 101 XOR 111 = 0102 and multiplication is (x+1).(x2+1) = x.(x2+1) + 1.(x2+1) = x3+x+x2+1 = x3+x2+x+1 011.101 = (101)<<1 XOR (101)<<0 = 1010 XOR 101 = 11112 polynomial modulo reduction (get q(x) & r(x)) is (x3+x2+x+1 ) mod (x3+x+1) = 1.(x3+x+1) + (x2) = x2 1111 mod 1011 = 1111 XOR 1011 = 01002 Sử dụng phần tử sinhUsing a Generator Tương đương với trường hữu hạn Phần tử sinh là phần tử mà mọi lũy thừa của nó sinh ra mọi số khác 0 Trong F có 0, g0, g1, …, gq-2 Có thể tạo nên phần tử sinh bằng cách lấy căn của các đa thức nguyên tố Sau đó định nghĩa phép nhân bằng cách lấy tổng số mũ của cùng cơ số Summary have considered: concept of groups, rings, fields modular arithmetic with integers Euclid’s algorithm for GCD finite fields GF(p) polynomial arithmetic in general and in GF(2n)