Giáo trình bảo mật thông tin phần 2
➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạmNội dung chi tiết: Giáo trình bảo mật thông tin phần 2
Giáo trình bảo mật thông tin phần 2
Chương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2ng hữu hạn. phép tinh trên các so nguyên lớn và lý thuyèt phức tạp.5.1.PHÉP TÍNH MODULOLý (huyết số là một ngành cua toán học dà tồn lại và có lịch sử từ rất lâu đời. Lý thuyết số chu yếu nghiên cứu về các con số và tính chàt cùa chúng, dặc biệt là các so nguyên. Lý thuyết số tòn tại song song với m Giáo trình bảo mật thông tin phần 2ật mã học và dường như chúng không có nhiêu môi quan hệ với nhau. Đên nứa cuối thế ky 20. nhiều nghiên cửu khác nhau dà cho thấy mói quan hệ mật thiỗtGiáo trình bảo mật thông tin phần 2
giũa lý thuyct sô và mật mà học. Nhicu thuật toán mà hoá khoá công khai xây dựng vào thập niên 70 cua thế ky trước hoàn toàn dựa trên cơ sờ lý thuyêtChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2yết số là không thê tách lởi. Trong chương này, chúng ta SC kháo sát một số khái niệm và thuật toán cùa lý thuyết sô, làm cơ sờ nền táng trong xây dựng các thuật toán mật mà hiện đại sè được kháo sát ờ các chương sau như: RSA, AES ...Lý thuyết số chú yếu làm việc trôn tập các số nguyên rời rạc. Các Giáo trình bảo mật thông tin phần 2phép tinh sử dụng nhiêu trong lý thuyết số là phép cộng vả phép nhân. Các phcp tính khác như trừ, chia hay luỳ thừa được suy ra từ hai phcp tính cơ baGiáo trình bảo mật thông tin phần 2
n trên. Nếu không có chú thích gì đặc biệt thi khi nói là các sô ta sè hiêu là các sô nguyên. Trước tiên, chúng la se ôn lại một sỏ kiên thức CƯ bàn.TChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2 b. Ví dụ: các số 1,2. 3, 4,6. 8, 12, 24 chia hểt 24 và là ước số cùa 24.Số nguyên to là số mà chi có hai ước số: 1 và chính nó. Ví dụ các số nguyên tố: 1 (là sổ nguyên tố dặc biệt), 2, 3, 5. 7.... Tương tự, các đa thức có khái niệm tồi giàn. Da thức với hệ số nguyên X2 + X = X (x 4- 1) là không tối Giáo trình bảo mật thông tin phần 2 gian vì có thê phân tích thành lích cua hai da thức nguyên với bậc nho hơn. Còn da thức X3 4- X 4- 1 là tối giàn vì nó không thê phàn tích thành tíchGiáo trình bảo mật thông tin phần 2
cua hai đa thức nguyên khác.Phân tích một số là viết triển khai số đó dưới dạng tích của các số khác: 48 = 4 X 6 X 2. Ta thấy việc phán tích một số kChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2 tố (phân tích ngụyên tổ), ví dụ: 48 = 2 X 2 X 2 X 2 X 3 = 24 X 3. Hai số gọi là nguyên tố cùng nhau nếu chúng không có ước số chung nào khác ngoài số I. Ví dụ 48 và 25 là nguyên tố cùng nhau và ký hiệu: (48, 25) = 1.Hai số a và b gọi là dồng (hr (congruence) theo modulo n và ký hiệu a = b mod n, (n Giáo trình bảo mật thông tin phần 2 > 0) ncu phép chia a và b cho n có cùng sò dư.Ví dụ: 100 = 34 mod 11.Nếu 0 < b < n - I thì b là thặng (lư (residue) cùa a theo mod n. Vi dụ: -12 modGiáo trình bảo mật thông tin phần 2
7 = -5 mod 7 = 2 mod 7 = 9 mod 7. Các số -12, -5, 2, 9, là đồng dư theo mod 7 nhưng chi có giá trị 2 được gọi Là thặng dư vì 0 < 2 < 6.Chúng ta SC địnChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2X b) mod 11 đều được thực hiện theo trình tự như các phép tính sò học binh thường nhưng sau đó kêt quá phái rút gọn theo mod n và sê nằm trong khoang [0, 11-1]. Các phép tính này thực hiện dề dàng vì kết qua của chúng luôn nam trong tập các sô nguyên.Phép tính nghịch đào: số nguyên b 1 là nghịch đảo Giáo trình bảo mật thông tin phần 2 cùa b nếu b X b'1 = 1 mod n. Ví dụ: 2 là nghịch đào của 3 theo mod 5 vì 2 X 3 = 1 mod 5. Lúc đó ta ký hiệu: 2'1 = 3 mod 5. Tắt nhiên cùng có: 3'1 = 2Giáo trình bảo mật thông tin phần 2
mod 5. Giá trị nghịch đao không phai lúc nào cũng tồn tại. Ví dụ: không tồn tại 4’1 mod 6. Thật vậy. già sư tồn tại số m = 4'1 mod 6. Khi dó theo địnChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2ịch đào tôn tại? Người la dà chứng minh dưực răng diêu kiện cần và dũ dê tôn lại nghịch đao a 1 mod n là a vả n phai là hai sô nguyên tô cùng nhau: (a, n) = 1.Từ khái niệm sò nghịch đảo chúng ta SC định nghía phép chia theo modulo. Khi tinh: (a / b) mod n, nếu b|a thi tính binh thường. Trường hợp ng Giáo trình bảo mật thông tin phần 2ược lại, ta sè định nghĩa: (a / b) mod II - (a X b’) mod n. Ví dụ: 7/2 - (7 X 2’1) mod 5 = 7x3 = 21 mod 5=1.5.2.BÀI TOÁN RỦT GỌN LƯỸ THỪARút gọn một sGiáo trình bảo mật thông tin phần 2
ô theo modulo là phép toán tim thặng dư của sô dó. Vi dụ: đê rút gọn a mod n ta tính số dư r cùa phép chia a cho n: a = d X n + r ; với 0 < r < n-1. SChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2 na 4-b = b + a;axb = bxa(a + b) + c = a + (b 4- c); (a X b) X c = a X (b X c)(a + b) X c = (a X c) + (b X c)0 4- w = w; I X w = w(a X b) mod n = [(a mod n) X (b mod n)] mod nVí dụ, ta có thê dùng các quy tắc trên đề rút gọn (2'° 4- 2100) mod 26 như sau: 2”= (2s)'0 = 32*f= 6IO = (62)5 = 10s = 100 X Giáo trình bảo mật thông tin phần 21000 = (-4) X (-40) = 160 = 4 mod 26. Do đó: 2S0 + 2I(I“ = 250(l + 250) = 4 X (1 + 4) = 20 mod 26.Các luật cùa phép toán modulo gồm có: (tat cá theo mGiáo trình bảo mật thông tin phần 2
od n)Luật giao hoán:Luật kết hợp:Luật phân phôi:Luật bất biến:Nhiều thuật toán mà hỏa VCU cáu rút gọn theo lũy thừa: Ví dụ, rút gọn a11 mod n (a cơ sôChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2.Sử dụng thuật toán bình phương và nhãn chi cần O(log2in) phép tinh cho phép rút gọn lùy thừa. Y tường của thuật toán là lặp lại các lùy thừa cua cơ số. Ví dụ, rút gọn 2'° mod 26. Đầu tiên, ta phân tích số mù thành cơ số 2: 50 = 1 10010j. Như vậy: 250 = 2 2 X 2 6 X 22. Các số mũ 2, 16, 32 ứng với cá Giáo trình bảo mật thông tin phần 2c bit 1 trong triền khai trên. Lần lượt bình phương theo cơ sô 2 và rút gọn theo mod 26 ta sẽ được: 21=2->22 = 4->24= 16 —> 2S = 256 = 22 mod 26216 =Giáo trình bảo mật thông tin phần 2
484 = 16 -» 232 = 256 = 22. Như vậy: 250 = 232 X 216 X 22 = 22 X(16 X 4) = 22 X 64 = 22 X 12 = 264 = 4 mod 26. Khái quát lại, ta có thể trinh bày thuậChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườn Giáo trình bảo mật thông tin phần 2h lừ phái sang núi) cua sốmũChương 5 cơ SỜ LÝ THUYẾT SỐChương 5 giới thiệu cơ sò- nên từng cùa mật mà hiện đại là lý thuyêt sổ, hao gồm phép tinh modulo, phép tính trên các trườnGọi ngay
Chat zalo
Facebook