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ã

Chia sẻ: You You | Ngày: | Loại File: PPTX | Số trang:39

Thêm vào BST

Báo xấu

114
lượt xem 29
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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)=(31)21 .(51)11 =24
Euler’s Totient function  Từ ɸ(p.q)=(p1)(q1), 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|ab( tức ab 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