Bài giảng An toàn và bảo mật thông tin - Chương 2: Cơ sở toán học của lý thuyết mật mã

Chương 2 cung cấp cho người học cơ sở toán học của lý thuyết mật mã. Các nội dung chính được trình bày trong chương này gồm có: Số học các số nguyên và thuật toán Euclide, đồng dư theo modular, định lý số dư trung hoa, hệ hai phương trình đồng dư, lũy thừa modulo. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng An toàn và bảo mật thông tin - Chương 2: Cơ sở toán học của lý thuyết mật mã Chương 2. Cơ sở toán học của lý  thuyết mật mã  2.1 Số học các số nguyên và thuật  toán Euclide Tính chia hết của số nguyên  Cho a, b≠0 là các số nguyên. Ta nói a chia hết cho b  nếu tồn tại 1 số c sao cho:  a=b.c  Ký hiệu b|a  a là bội số của b (divisor), b là ước số của a ( mutiple)  Ví dụ: 2| 6 Tính chia hết của các số nguyên  Với a, b, c, d, e ∈Z, ta có:  ­ Nếu a|b và b|c ⇒ a|c  ­ Nếu a|b, thì ac|bc ∀c  ­ Nếu c|a và c|b, thì c| da+ be ∀d, e  ­ Nếu a|b và b≠0, thì |a|≤|b|  ­ Nếu a|b và b|a, thì |a|=|b| Định lý phép chia của Euclid q Đối với mọi số n, d\{0}, luôn tồn tại duy nhất các số q,  r∈Z sao cho: n=qd+r    với 0Ước chung lớn nhất(greatest  common divisor­ gcd)  Cho hai số a, b ∈Z\{0}, c∈Z được gọi là ước chung của  a và b nếu c|a và c|b  C được gọi là ước chung lớn nhất, ký hiệu gcd(a, b),  nếu nó là số nguyên lớn nhất a, b chia hết.  Bội chung nhỏ nhất(Least  common multiple)  Cho hai số a, b ∈Z\{0}, c∈Z được gọi là bộichung của  a và b nếu a|c và b|c  C được gọi là bộichung nhỏ nhất, ký hiệu lcm(a, b),  nếu nó là số nguyên nhỏ nhất chia hết cho a, b.  Thuật toán Euclide tìm UCLN Ø Input: hai số không âm a, b, a>=b Ø Output: gcd(a, b). Trong khi b>=0  thực hiện:  r a mod b  a b  b r Cho kết quả (a) Thuật toán Euclid mở rộng  Thuật toán Euclid mở rộng dùng để tìm hai số x, y  thỏa mãn phương trình sau:  ax + by = gcd(a, b) Euclide mở rộng Ví dụ  Cho a=4864, b= 3458, tìm (d, x, y) (38, 32, ­45) Nguyên tố và hợp số  Số tự nhiên 11đều có thể viết dưới dạng: n=p1a1 .p2a2 …pkak    Lưu ý: số 1 không pải là ngto cũng không phải là hợp  số. Hàm đếm các số nguyên tố  Hàm đếm các số nguyên tố(prime counting function)  ∏(n) cho kết quả là các số nguyên tố nhỏ hơn hay  bằng n∈N ∏(n)=|{p∈P| p≤n}| Phân tích hợp số thành thừa số  nguyên tố  Mỗi số tự nhiên n ∈N đều có thể phân tích thành các  thừa số nguyên tố duy nhất  ep (n): là số mũ của p  Ví dụ: 4725=32 .53 . 7    Phân tích hợp số thành thừa số  nguyên tố  Ví dụ: tìm gcd và lcm của ( 143, 220)  143=11.13  220= 2^2. 5. 11  Gcd(143, 220)= 2min(2,0)  .5min(1,0) . 11. 13min(1, 0)  lcm(143, 220)= 2max(2,0)  .5max(1,0) . 11. 13max(1, 0) Euler’s Totient function  Dùng để đếm các số Euler’s Totient function  Với mọi số nguyên n có thể phân tích thành thừa số  nguyên tố thì  Ví dụ: ɸ(45)= ɸ(32 .5)=(3­1)2­1 .(5­1)1­1 =24 Euler’s Totient function  Từ ɸ(p.q)=(p­1)(q­1), ta có thể tính p khi biết ɸ(p.q)  theo công thức sau:  Công thức này được dùng trong mã hóa công khai  RSA 2.2. Đồng dư theo modular  Cho a, b∈Z, n∈N. a được gọi là đồng dư với b theo  modulo n nếu n|a­b( tức a­b chia hết cho n, hay a và b  chia cho n cùng số dư)  Ký hiệu:  a b(mod n)  Ví dụ:  7 12(mod 5)              4 ­1(mod 5) Tính chất đồng dư modular n Với mọi số n∈N, a, b,c ∈Z các tính chất sau luôn thỏa  mãn: 1. a a(mod n)­ tính chất phản xạ 2. Nếu a b(mod n) thì b a(mod n)­ tính đối xứng. 3. If a b(mod n) and b c(mod n) thì a c(mod n) (tính  bắc cầu) Quan hệ đồng dư theo modular n là quan hệ tương đương Các phép toán đồng dư  Có thể thực hiện các phép cộng và nhân phần dư  tương tự như cộng nhân các số nguyên. Rn (a b) Rn ( Rn (a ) Rn (b)) Rn (a.b) Rn ( Rn (a ).Rn (b))  Ví dụ:  R 7 (12 18) R7 ( R7 (12) R7 (18)) 2 R7 (12.18) R7 ( R7 (12).R7 (18)) R7 (4.5) 6