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ã 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.cKý hiệu b|aa là bội số của b (divisor), b là ước số của a ( mutiple)Ví dụ: 2| 6Tính chia hết của số nguyên2.1 Số học các số nguyên và thuật toán EuclideVớ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|Tính chia hết của các số nguyênĐố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=bOutput: gcd(a, b).Trong khi b>=0 thực hiện: r a mod b a b b rCho kết quả (a)Thuật toán Euclide tìm UCLNThuậ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)Thuật toán Euclid mở rộngEuclide mở rộngCho a=4864, b= 3458, tìm (d, x, y)Ví dụ(38, 32, -45)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ố.Nguyên tố và hợp số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}|Hàm đếm các 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ấtep (n): là số mũ của pVí 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.13220= 2^2. 5. 11Gcd(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)Phân tích hợp số thành thừa số nguyên tốDùng để đếm các số 1 thì a không có nghịch đảo nhân modulo n.Cách tìm nghịch đảo nhân(tt)Ví dụPhép tính đồng dư mod m tách tập số nguyên ra m lớp, mỗi lớp là tập các số nguyên đồng dư với nhau theo mod m.Ký hiệu: ℤ/mℤMỗi số lớp ℤ/mℤ có đúng 1 số nằm trong đoạn [0, m-1], cho nên mỗi số nguyên a đại diện cho 1 lớp.Các phép tính trong lớp thông qua đại diện lớp.Lớp đồng dư2.3 Định lý số dư trung hoaLà hệ thống gồm k phương trình đồng dư với n1,, nk từng đôi một là nguyên tố cùng nhau. Hệ thống có 1 nghiệm duy nhất x ∈ZnĐặt mi =n/ni với i=1,2,,k yi =m-1i (mod ni ) yi là nghịch đảo nhân của mi modulo ni.Khi đó nghiệm x được tính như sau:Tìm số dư trung hoaCho hệ 3 pt đồng dư sau:Hãy tìm nghiệm x???Ví dụ n1=7, n2=11. n3=13 (tất cả đều nguyên tố cùng nhau).n=n1*n2*n3=1001 m1=n/n1=1001/7=143 m2=1001/11=91 m3=1001/13=77 Ví dụ(tt)Tính y: y1143-1 (mod 7)=5 y291-1 (mod 11)=4 y377-1 (mod 13)=12Tính x: x=a1*m1*y1+ a2*m2*y2+ a3*m3*y3 = 5*143*5+3*91*4+11*77*12 = 14831 Ví dụ(tt)Xét hệ hai phương trình: Với gcd(n1,n2)=1Tính t=n2-1 (mod n1)Khi đó u(a2-a1)t(mod n2)Giải thuật này được ứng dụng nhiều trong mật mã RSA x=a 1+un12.4 Hệ hai phương trình đồng dưTính ab (mod n)???Giải thuật đơn giản nhất là nhân a(mod n) b lần.Ví dụ:2.5. Lũy thừa moduloLũy thừa moduloSử dụng triển khai số mũ b thành các phép bình phương và phép nhân.The square-and-multiply algorithmTính 722 (mod 11)B1: b=(22)10  (10110)2 B2: áp dụng giải thuật trênVí dụChúng ta nói hàm: f: XY là hàm một chiều nếu f(x) có thể tính toán hiệu quả với mọi x∈X, nhưng f-1(y) không thể tính toán hiệu quả với mọi y∈RY.“tính toán hiệu quả” ở đây chúng ta nói tới độ phức tạp tính toánVí dụ: hàm RSA hàm bình phương modular hàm logarith rời rạcHàm một chiềuA one-way function f : X → Y is a trapdoor function if there is a trapdoor information t and a PPT algorithm I that can be used to efficiently compute x’= I(f(x),t) with f(x’)= f(x).Trapdoor functionQ&A