CHƯƠNG 1 MỘT SỐ KHÁI NIỆM CƠ BẢN 1. CÁC KHÁI NIỆM TRONG TOÁN HỌC 1. Số nguyên tố và nguyên tố cùng nhau Số nguyên tố là số nguyên dƣơng chỉ chia hết cho 1 và chính nó. Ví dụ: 2, 3, 5,… Các hệ mật mã thƣờng dùng các số nguyên tố cỡ 512 bit hoặc lớn hơn.
Hai số nguyên dƣơng m và n đƣợc gọi là nguyên tố cùng nhau, nếu ƣớc số chung lớn nhất của chúng bằng 1, ký hiệu gcd(m, n) = 1. Ví dụ: 8 và 17 là hai số nguyên tố cùng nhau. Đồng dƣ thức 1) Định nghĩa Cho a và b là các số nguyên, khi đó a đƣợc gọi là đồng dƣ với b theo modulo n, ký hiệu là a b mod n nếu a, b chia cho n có cùng số dƣ. Số nguyên n đƣợc gọi là modulo của đồng dƣ.
Ví dụ: 5 7 mod 2 vì: 5 mod 2 = 1 và 7 mod 2 = 1 2) Tính chất Cho a, a1, b, b1, c Z. Ta có các tính chất sau: + a b mod n nếu và chỉ nếu a và b có cùng số dƣ khi chia cho n + Tính phản xạ: a a mod n + Tính đối xứng: Nếu a b mod n thì b a mod n + Tính giao hoán: Nếu a b mod n và b c mod n thì a c mod n + Nếu a a1 mod n, b b1 mod n thì a+b a1+b1 mod n và ab a1b1 mod n 3) Lớp tương đương Lớp tƣơng đƣơng của một số nguyên a là tập hợp các số nguyên đồng dƣ với a theo modulo n. Cho n cố định đồng dƣ với n trong không gian Z vào các lớp tƣơng đƣơng. Nếu a=qn +r, trong đó 0 r n thì a r mod n.
Vì vậy mỗi số nguyên a là đồng dƣ theo modulo n với duy nhất một số nguyên trong khoảng từ 0 đến n-1 và đƣợc gọi là thặng dƣ nhỏ nhất của a theo modulo n. Cũng vì vậy, a và r cùng thuộc một lớp tƣơng đƣơng. Do đó r có thể đơn giản đƣợc sử dụng để thể hiện lớp tƣơng đƣơng.tu TIEU LUAN MOI download : skknchat@gmail. Không gian Zn và Zn* Không gian các số nguyên theo modulo n: Zn là tập hợp các số nguyên không âm nhỏ hơn n.
Tức là: Zn = {0, 1, 2,… n-1}. Tất cả các phép toán trong Zn đều đƣợc thực hiện theo modulo n. Trong Z25 : 12 + 20 = 7(mod 25) Không gian Zn* là tập hợp các số nguyên p thuộc Zn sao cho ƣớc chung lớn nhất của p và n là 1. Tức là, Zn* = {p thuộc Zn | gcd(n, p) = 1} Ví dụ: Z2 = { 0,1 }; Z*2 = {1} vì gcd(1, 2)=1 1.
Khái niệm phần tử nghịch đảo trong Zn 1) Định nghĩa Cho aZn. Nghịch đảo nhân của a theo modulo n là một số nguyên xZn sao cho a*x1 (mod n). Nếu tồn tại thì đó là giá trị duy nhất và a gọi là khả đảo, nghịch đảo của a ký hiệu là a-1. 2) Tính chất + Cho a,bZn.
Phép chia của a cho b theo modulo n là tích của a và b-1 theo modulo n, và chỉ đƣợc xác định khi b có nghịch đảo theo modulo n. + Giả sử d=gcd(a, n). Phƣơng trình đồng dƣ ax b (mod n) có nghiệm x nếu và chỉ nếu d chia hết cho b, trong trƣờng hợp các nghiệm d nằm trong khoảng 0 đến n-1 thì các nghiệm đồng dƣ theo modulo n/d.tu TIEU LUAN MOI download : skknchat@gmail. Khái niệm nhóm, nhóm con, nhóm Cyclic 1) Nhóm Nhóm là bộ các phần tử (G, *) thỏa mãn các tính chất sau: + Tính chất kết hợp: ( x * y ) * z = x * ( y * z ) + Tính chất tồn tại phần tử trung gian e G: e * x= x * e = x , x G + Tính chất tồn tại phần tử nghịch đảo x’ G: x’ * x = x * x’ = e 2) Nhóm con Nhóm con là bộ các phần tử ( S, * ) là nhóm thỏa mãn các tính chất sau: 1/ S G, phần tử trung gian e S 2/ x, y S => x * y S 3) Nhóm cylic Nhóm Cyclic là nhóm mà mọi phần tử x của nó đƣợc sinh ra từ một phần tử đặc biệt g G.
Phần tử này đƣợc gọi là phần tử nguyên thủy, tức là: Với x G: n N mà gn = x. Ví dụ: (Z+, *) là một nhóm cyclic có phần tử sinh là 1 1. Bộ phần tử sinh {g1, …, gk} đƣợc gọi là bộ phần tử sinh nếu mỗi gi là một phần tử sinh và những phần tử này khác nhau (gi gj nếu i j). Ví dụ: {3, 5} là bộ phần tử sinh của Z7*, bởi vì: 1 = 36 mod 7 = 56 mod 7 2 = 32 mod 7 = 54 mod 7 3 = 31 mod 7 = 55 mod 7 4 = 34 mod 7 = 52 mod 7 5 = 35 mod 7 = 51 mod 7 6 = 33 mod 7 = 53 mod 7 2 không phải là phần tử sinh của Z7*, bởi vì: {2, 22, 23, 24, 25, 26} = {1, 4, 1, 2, 4, 1} {1, 2, 4} Tuy nhiên {1, 2, 4} là tập con của {1, 2, 3, 4, 5, 6} = Z 7*, dó đó số 2 đƣợc gọi là “phần tử sinh của nhóm G(3)”, G(3) là nhóm có 3 thành phần {1, 2, 4}.tu TIEU LUAN MOI download : skknchat@gmail.7 Bài toán đại diện Gọi g là phần tử sinh của nhóm con G(q) thuộc Zn*.
Bài toán logarit rời rạc liên quan đến việc tìm số mũ a, sao cho: a = loggh mod n (với h G (q)). Bài toán đại diện là: cho h thuộc G(q), tìm {a1, …, ak}, của bộ phần tử sinh {g1, …, gk}, sao cho: h = g1a1 * g2a2 *… * gkak mod n. {a1, …, ak} đƣợc gọi là đại diện (presentation). Ví dụ: Cho tập Z23*, thì ta có thể tìm đƣợc: Nhóm con G (11) = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} với những phần tử sinh g i là: 2, 3, 4, 6, 8, 9, 12, 13, 16, 18.
{2, 3} là 2 phần tử sinh của nhóm con G (11) trong Z23*. Bài toán đại diện là với h = 13 G (11), tìm {a1, a2} sao cho: 13 = 2a1 * 3a2 mod 23 Logarit hai vế, có a1*log(2) + a2*log(3) = log(13) mod 23. Kết quả là: a1 = 2 và a2 =2, vì 22 * 32 = 4*9 = 36 = 13 mod 23. Hay a1 = 7 và a2 = 11, vì 27 * 311 = 128*177147 = 13 mod 23.
Hàm một phía và hàm một phía có cửa sập 1) Hàm một phía Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều, nhƣng rất khó để tính ngƣợc lại. Ví nhƣ biết x thì có thể dễ dàng tính ra f(x), nhƣng nếu biết f(x) thì rất khó tính ra đƣợc x. Trong trƣờng hợp này “khó” có nghĩa là để tính ra đƣợc kết quả thì phải mất rất nhiều thời gian để tính toán. Ví dụ: Tính y = f(x) = αx mod p là dễ nhƣng tính ngƣợc lại x = logα y là bài toán “khó” (bài toán logarit rời rạc) (LUAN.tu TIEU LUAN MOI download : skknchat@gmail.tu -17- 2) Hàm một phía có cửa sập F(x) đƣợc gọi là hàm một phía có cửa sập nếu tính xuôi y = f(x) thì dễ, nhƣng tính ngƣợc x = f-1(y) thì khó, tuy nhiên nếu có “cửa sập” thì vấn đề tính ngƣợc trở nên dễ dàng.
Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngƣợc. Nhƣng nếu biết cửa sập p, q thì ta tính (n) sau đó tính a trở nên dễ dàng. Độ phức tạp tính toán Độ phức tạp tính toán (về không gian hay thời gian) của một tiến trình tính toán là số ô nhớ đƣợc dùng hay số các phép toán sơ cấp đƣợc thực hiện trong tiến trình tính toán đó. Dữ liệu đầu vào đối với một thuật toán thƣờng đƣợc biểu diễn qua các từ trong một bảng ký tự nào đó.
Độ dài của một từ là số ký tự trong từ đó. Cho thuật toán A trên bảng ký tự Z ( tức là có các đầu vào là các từ trong Z). Độ phức tạp tính toán của thuật toán A đƣợc hiểu nhƣ một hàm số fa(n) sao cho với mỗi số n thì fa(n) là số ô nhớ, hay số phép toán sơ cấp tối đa mà A cần để thực hiện tiến trình tính toán của mình trên các dữ liệu vào có độ dài nhỏ hơn hoặc bằng n. Ta nói: thuật toán A có độ phức tạp thời gian đa thức, nếu có một đa thức p(n) sao cho với mọi n đủ lớn ta có: fa(n) p(n), trong đó fa(n) là độ phức tạp tính toán theo thời gian của A.
Bài toán P đƣợc gọi là “giải đƣợc” nếu tồn tại thuật toán để giải nó, tức là thuật toán làm việc có kết thúc trên mọi dữ liệu đầu vào của bài toán. Bài toán P đƣợc gọi là “giải đƣợc trong thời gian đa thức” nếu có thuật toán giải nó với độ phức tạp thời gian đa thức.tu TIEU LUAN MOI download : skknchat@gmail. TỔNG QUAN VỀ AN TOÀN THÔNG TIN 1. Tại sao phải đảm bảo an toàn thông tin Ngày nay, với sự phát triển mạnh mẽ của công nghệ thông tin thì việc ứng dụng các công nghệ mạng máy tính trở nên vô cùng phổ cập và cần thiết.
Công nghệ mạng máy tính đã mang lại những lợi ích to lớn. Sự xuất hiện mạng Internet cho phép mọi ngƣời có thể truy cập, chia sẻ và khai thác thông tin một cách dễ dàng và hiệu quả. Việc ứng dụng các mạng cục bộ trong các tổ chức, công ty hay trong quốc gia là rất phong phú. Các hệ thống chuyển tiền của các ngân hàng hàng ngày có thể chuyển hàng tỷ đôla qua hệ thống của mình.
Các thông tin về kinh tế, chính trị, khoa học xã hội đƣợc trao đổi rộng rãi. Nhất là trong quân sự và kinh tế, bí mật là yếu tố vô cùng quan trọng, do vậy các thông tin về quân sự và kinh tế đƣợc xem nhƣ là các thông tin tuyệt mật và cần đƣợc bảo vệ cẩn thận. Đó cũng là một quá trình tiến triển hợp logic, một yêu cầu thực tế tất yếu đặt ra cần phải đƣợc giải quyết. Những thông tin này khi bị lộ có thể làm thay đổi cục diện của một cuộc chiến tranh hay làm phá sản nhiều công ty và làm xáo động thị trƣờng.