phần mở đầu, kết luận và 3 chƣơng với các nội dung chính sau: - Chƣơng 1: Cơ sở lý thuyết về toán học. - Chƣơng 2: Nói về vấn đề mã hóa bao gồm giới thiệu về mật mã, các khái niệm về mã hóa, các phƣơng pháp mã hóa, chữ ký số và hàm băm. - Chƣơng 3: Tìm hiểu thuật toán Rijndael và mô phỏng chƣơng trình ứng dụng. 9 CHƢƠNG 1: CƠ SỞ TOÁN HỌC 1.1 Các khái niệm toán học 1.
Số nguyên tố và số nguyên tố cùng nhau. - Số nguyên tố là số nguyên dƣơng lớn hơn 1chỉ chia hết cho 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, … là những số nguyên tố. - Hệ mật mã thƣờng sử dụng các số nguyên tố ít nhất là lớn hơn 10150.
- Hai số 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. Ví dụ: 11 và 13 là nguyên tố cùng nhau. Định lý số nguyên tố: Với mọi n>=2 đều có thể phân tích thành lũy thừa cơ số nguyên tố n = p1e1p2e2p3e3. , với pi : số nguyên tố, ei Z+.
Hệ quả: Giả sử a = p1e1.pkfk thì gcd(a,b) = p1min(e1,f1).19 ta đƣợc : gcd(a,b)=2.1 Khái niệm đồng dƣ Cho n là một số nguyên dƣơng. Nếu a và b là hai số nguyên, khi đó a đƣợc gọi là đồng dƣ với b theo modulo n, đƣợc viết a ≡ b (mod n) nếu n│(a – b), và n đƣợc gọi là modulo của đồng dƣ. Ví dụ: 24 ≡ 9 (mod 5), 17 ≡ 5 (mod 3) Tính chất: (i) a ≡ b (mod n), nếu và chỉ nếu a và b đều trả số dƣ nhƣ nhau khi đem chia chúng cho n.2 Định nghĩa Phi Euler Với n ≥ 1, đặt (n) là số các số nguyên trong khoảng [1, n] và nguyên tố cùng nhau với n. Hàm nhƣ thế đƣợc gọi là hàm phi-Euler.
Tính chất: - Nếu p là số nguyên tố thì (p) = p-1 (1.p2e2…pkek, dạng khai triển chính tắc của n, thì (n) = (1.3 Thuật toán Euclide Thuật toán: Thuật toán Euclide, tính ƣớc số chung lớn nhất của hai số. INPUT: Hai số nguyên không âm a và b sao cho a ≥ b. OUTPUT: Ƣớc số chung lớn nhất của a và b. Trong khi b ≠ 0, thực hiện Đặt r ← a mod b, a ← b, b ← r.
11 Thuật toán Euclidean có thể đƣợc mở rộng để không chỉ tính đƣợc ƣớc số chung d của hai số nguyên a và b, mà còn có thể tính đƣợc hai số nguyên x, y thoả mãn: ax + by = d *Thuật toán Euclidean mở rộng INPUT: Hai số nguyên không âm a và b với a ≥ b. OUTPUT: d = gcd(a, b) và hai số x, y thoả mãn ax + by = d. Nếu b = 0, đặt d←a , x←1, y←0, Kết_quả(d, x, y). Trong khi còn b > 0, thực hiện: 3.
Đặt d←a, x←x2 , y←y2 , Kết_quả(d, x, y).4 Không gian Zn và Zn* 1.1 Không gian Zn (các số nguyên theo modulo n) Là tập hợp các số nguyên {0, 1, 2, …, n-1}. Các phép toán trong Zn như cộng, trừ, nhân, chia đều đƣợc thực hiện theo module n.2 Không gian Zn* Là tập hợp các số nguyên a Zn, nguyên tố cùng n. Tức là: Zn* = {a Zn | gcd (n, a) =1}, (n) là số phần tử của Zn*. Nếu n là một số nguyên tố thì: Zn* = {a Zn |1 ≤ a ≤ n-1} (1.6) Ví dụ: Z3 = {0, 1,2} thì Z3* = {1,2} vì gcd(1, 3) = 1và gcd(2,3) = 1.5 Định nghĩa cấp của một số a Zn* Cho α Zn*, khi đó cấp của a, kí hiệu ord(a) là số nguyên dƣơng nhỏ nhất sao cho at 1(mod n) trong Zn*.6 Khái niệm Nhóm, Nhóm con, Nhóm Cyclic 1.1 Khái niệm Nhóm Nhóm là một bội (G, *), trong đó G , * là phép toán hai ngôi trên G thỏa mãn ba tính chất sau: + Phép toán có tính kết hợp: (x*y)*z = x*(y*z) với mọi x, y, z G.7) + Có phần tử trung lập e G: x*e = e*x = x với mọi x G.8) + Với mọi x G, có phần tử nghịch đảo x’ G: x*x’ = x’*x = e.9) Cấp của nhóm G đƣợc hiểu là số phần tử của nhóm, ký hiệu là |G|.
Cấp của nhóm có thể là nếu G có vô hạn phần tử. Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán. Tính chất: Nếu a*b = a*c, thì b = c. Ví dụ: +) Tập hợp các số nguyên Z cùng với phép cộng (+) thông thƣờng là nhóm giao hoán, có phần tử đơn vị là số 0.
Gọi là nhóm cộng các số nguyên. +)Tập Q * các số hữu tỷ khác 0 (hay tập R * các số thực khác 0), cùng với phép nhân (*) thông thƣờng là nhóm giao hoán. Gọi là nhóm nhân các số hữu tỷ (số thực). +)Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán.2 Nhóm con của nhóm (G, *) Nhóm con của G là tập S G, S , và thỏa mãn các tính chất sau: + Phần tử trung lập e của G nằm trong S.
+ S khép kín đối với phép tính (*) trong G, tức là x*y S với mọi x, y S. + S khép kín đối với phép lấy nghịch đảo trong G, tức x 1 S với mọi x S.3 Nhóm Cyclic Cho α Zn*, nếu cấp của α là (n), khi đó α đƣợc gọi là phần tử sinh hay phần tử nguyên thủy của Zn*. Nếu Zn* có một phần tử sinh, thì Zn* đƣợc gọi là nhóm Cyclic. Và sau đó nếu Zn* là nhóm Cyclic thì số phàn tử sinh sẽ là ((n)).
-α Zn* là phần tử sinh của Zn* khi và chỉ khi α (n)/p ! (mod n) với mỗi số chia nguyên tố của (n). - Zn* có phần tử sinh khi và chỉ khi n = 2, 4, pk hay 2pk khi p là số nguyên tố lẻ và k Còn nếu p là số nguyên tố thì chắc chắn Zp* có phần tử sinh. Ví dụ: Z21* không phải là nhóm Cyclic vì không phần tử nào của Z21* có cấp là φ(21) = 12, chú ý là 21 không thỏa mãn điều kiện nào theo tính chất của phần tử sinh trên. Trong khi đó Z13* là nhóm Cyclic và có phần tử sinh α = 2 Thật vậy: 20 mod 13 = 1 21 mod 13 = 2 22 mod 13 = 4 23 mod 13 = 8 24 mod 13 = 3 25 mod 13 = 6 26 mod 13 = 12 27 mod 13 = 11 28 mod 13 = 9 29 mod 13 = 5 210 mod 13 = 10 211 mod 13 = 7 Phần tử 2i là sinh khi và chỉ khi gcd(i, 12) = 1 nghĩa là khi và chỉ khi i =1, 5, 7 hoặc 11.
Vậy các phần tử sinh của Z13* là 2, 6, 7 và 11.7 Tập thặng dƣ bậc hai theo modulo Định nghĩa: Cho a Z*n, a đƣợc gọi là thặng dƣ bậc hai theo modulo n nếu tồn tại một x Z*n sao cho , và nếu không tồn tại x nhƣ vậy thì a đƣợc gọi là bất thặng dƣ bậc hai theo modulo n. Tập hợp các thặng dƣ bậc hai đƣợc kí hiệu là Qn và tập các bất thặng dƣ bậc hai ký hiệu là. Ví dụ: α = 6 là phần tử sinh của Z*13 ta có: .8 Phần tử nghịch đảo Định nghĩa: Cho a Zn, số nghịch đảo của a theo modulo n là một số nguyên x Zn, nếu a. Nếu tồn tại x nhƣ vậy, thì nó là duy nhất và a đƣợc gọi là khả nghịch, nghịch đảo của a đƣợc kí hiệu là a-1.
Tính chất: a Zn, a là khả nghịch khi và chỉ khi gcd(a, n) = 1. Ví dụ: Các phần tử khả nghịch trong Z9 là 1, 2, 4, 5, 7 và 8. Thuật toán tính nghịch đảo trên Zn Input: a Zn. Output: a-1 mod n, nếu tồn tại, 1.
Sử dụng thuật toán Euclidean mở rộng, tìm x và y để ax + ny = d, trong đó d = gcd(a, n). Nếu d >1, thì a-1 mod n không tồn tại, Ngƣợc lại, kết quả(x).2 Khái niệm Độ phức tạp của thuật toán 1.1 Khái niệm Thuật toán Thuật toán là một dãy hữu hạn các quy tắc ( chỉ thị, mệnh lệnh) mô tả chính xác một quá trình tính toán. Theo đó với mỗi bộ dữ liệu vào sẽ cho một kết quả ( Yêu cầu của bài toán ).[1] Các đặc trƣng của Thuật toán đơn định: - Tính đơn định: Thực hiện đúng các bƣớc của thuật toán với một dữ liệu vào thì chỉ cho duy nhất một kết quả nghĩa là ở mỗi bƣớc của thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lộn xộn, đa nghĩa. - Tính dừng: Thuật toán phải dừng và cho ra kết quả sau một số hữu hạn các bƣớc.
- Tính đúng: Cho ra kết quả phù hợp yêu cầu bài toán với những dữ liệu vào đúng đắn. 15 - Tính phổ dụng: Thuật toán phải giải quyết đƣợc một lớp rộng các bài toán. - Tính khả thi: Thuật toán phải đƣợc máy tính thực hiện trong khoảng thời gian và điều kiện ( bộ nhớ ) cho phép.2 Độ phức tạp của thuật toán Thông thƣờng để đánh giá thuật toán ngƣời ta dựa trên hai tiêu chuẩn sau: Tiêu chuẩn 1: Độ đơn giản, dễ hiểu, dễ cài đặt ( viết chƣơng trình ). Tiêu chuẩn 2: Sử dụng tiết kiệm tài nguyên hệ thống và với thời gian ngắn nhất.
Độ phức tạp của thuật toán là phƣơng pháp đánh giá thuật toán theo hƣớng xấp xỉ tiệm cận qua các khái niệm toán học O lớn O(); o nhỏ o(); (); (). Hầu hết tất cả các thuật toán có thời gian chạy tiệm cận tới một trong các hàm sau: a. Hằng số: Hầu hết các chỉ thị của các chƣơng trình đều đƣợc thực hiện một lần hay nhiều nhất chỉ một vài lần. Nếu tất cả các chỉ thị của cùng một chƣơng trình có tính chất này thì chúng ta sẽ nói rằng thời gian chạy của nó là hằng số.
Điều này hiển nhiên là điều mà ta phấn đấu để đạt đƣợc trong việc thiết kế thuật toán. LogN: Khi thời gian chạy của chƣơng trình là logarit tức là thời gian chạy chƣơng trình tiến chậm khi N lớn dần. Thời gian chạy thuộc loại này xuất hiện trong các chƣơng trình mà giải một bài toán lớn bằng cách chuyển nó thành một bài toán nhỏ hơn, bằng cách cắt bớt kích thƣớc một hằng số nào đó. Với mục đích của chúng ta, thời gian chạy có đƣợc xem nhƣ nhỏ hơn một hằng số ―lớn―.
Cơ số của logarit làm thay đổi hằng số đó nhƣng không nhiều: Khi N là 1000 thì logN là 3 nếu cơ số là 10, là 10 nếu cơ số là 2; khi N là một triệu, logN đƣợc nhân gấp đôi.