Đăng ký Đăng nhập
Trang chủ Tìm hiểu một số kỹ thuật tấn công hệ mật RSA...

Tài liệu Tìm hiểu một số kỹ thuật tấn công hệ mật RSA

.PDF
83
275
79

Mô tả:

Ngày nay, thuật ngữ “thời đại thông tin” đã trở nên quá phổ biến đối với nhiều người. Có thể nói, chưa bao giờ công nghệ thông tin lại phát triển bùng nổ như hiện nay. Tin học có mặt tại hầu hết trong các lĩnh vực của đời sống xã hội, đã, đang và sẽ còn tiếp tục đem lại những ứng dụng và lợi ích vô cùng to lớn cho con người. Tại hầu khắp các nước trên thế giới, tin học phát triển vượt bậc. Những hệ thống tin học không còn nhỏ lẻ, cục bộ, mà trái lại, chúng không ngừng phát triển trở thành những hệ thống kiến trúc tin học lớn, đồ sộ và mang tính toàn cầu, đặc biệt là các hệ thống mạng truyền tin và các hệ thống thương mại điện tử. Các hệ thống này ngày càng đóng vai trò thiết yếu trong mọi lĩnh vực, mọi hoạt động của toàn xã hội. Điều này cũng đồng nghĩa với việc, nhu cầu đảm bảo an toàn và bảo mật thông tin phải được đặt lên hàng đầu và có tầm quan trọng thời sự. Cũng chính vì vậy mà công nghệ mã hóa thông tin ngay từ khi ra đời đã phát triển nhanh chóng vượt bậc và đạt được rất nhiều kết quả ứng dụng sâu sắc. Một trong những công nghệ mã hoá hiện đại và có ứng dụng phong phú là công nghệ mã hóa khóa công khai, mà đại diện là hệ mật mã RSA. Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir và Len Adleman, công bố lần đầu vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ. Hệ mật được sử dụng trong lĩnh vực đảm bảo tính riêng tư và cung cấp cơ chế xác thực dữ liệu số. Ngày nay, RSA đã đư ợc phát triển ứng dụng rộng rãi trong thương mại điện tử. Nó được sử dụng trên Web servers và trên các Browsers nhằm đảm bảo an ninh đường truyền, được sử dụng trong việc tạo khóa và xác thực của mail, trong truy cập từ xa…. Tóm lại, RSA được ứng dụng trong các lĩnh vực nơi mà an ninh an toàn thông tin được đòi hỏi.
MỤC LỤC MỤC LỤC ..............................................................................................................1 MỞ ĐẦU ................................................................................................................4 CHƯƠNG I. CÁC KHÁI NIỆM CƠ BẢN ..............................................................6 1.1. Một số khái niệm toán học.............................................................................6 1.1.1. Số nguyên tố và số nguyên tố cùng nhau .................................................6 1.1.2. Đồng dư thức ..........................................................................................8 1.1.3. Không gian Zn và Zn*...........................................................................10 1.1.4. Phần tử nghịch đảo................................................................................10 1.1.5. Khái niệm nhóm, nhóm con, nhóm Cyclic.............................................11 1.1.6. Hàm Ф Euler .........................................................................................11 1.1.7. Các phép toán cơ bản trong không gian modulo ....................................12 1.1.8. Hàm một phía và hàm một phía có cửa sập............................................13 1.1.9. Hàm Euler, định lý Euler và định lý Fermat ..........................................14 1.1.10. Bậc và căn nguyên thủy.......................................................................15 CHƯƠNG II. HỆ MẬT MÃ KHÓA CÔNG KHAI ...............................................17 2.1. Tổng quan về các hệ mật mã .......................................................................17 2.1.1. Hệ mã hóa đối xứng ..............................................................................17 2.1.2. Hệ mật khóa công khai ..........................................................................26 2.2. Hệ mật khóa công khai RSA........................................................................33 2.2.1. Giới thiệu ..............................................................................................33 2.2.2. Phương pháp lập mã và giải mã của hệ mật RSA ..................................34 2.2.3. Độ an toàn của RSA ..............................................................................35 2.2.4. Quản lý khóa của hệ mật RSA...............................................................38 CHƯƠNG III. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG RSA ..............................50 1 3.1. Thám mã RSA.............................................................................................50 3.1.1. Một số giả thiết ngầm định .......................................................................52 3.1.2. Phân tích các số nguyên lớn......................................................................53 3.2. Các tấn công cơ bản ....................................................................................54 3.2.1. Modul chung .........................................................................................54 3.2.2. Mù (Blinding) .......................................................................................55 3.3. Số mũ riêng bé (Low private Exponent) ......................................................56 3.3.1. Độ lớn e ................................................................................................57 3.3.2. Sử dụng CRT ........................................................................................58 3.4. Số mũ công khai bé (Low public Exponent) ................................................58 3.4.1. Hastad's Broadcast Attack .....................................................................59 3.4.2. Franklin-Reiter Related Message Attack ...............................................59 3.5. Thành phần công khai bé.............................................................................60 3.5.1. Coppersmith's Short Pad Attack ............................................................60 3.5.2. Tấn công bằng khóa riêng .....................................................................61 3.6. Một số tấn công bằng nhân tử hóa số N với số N lớn ...................................63 3.6.1. Tìm nhân tử lớn nhất thứ nhất ≤ N .....................................................63 3.6.2. Phân tích thứ hai ...................................................................................64 3.6.3. Phân tích thứ ba.....................................................................................65 3.6.4. Thuật toán Pollard (p-1) ........................................................................66 3.7. Một số phương pháp gài bẫy mới trong RSA...............................................68 3.7.1. Phương pháp gài bẫy cặp bí mật (SP) ....................................................68 3.7.2. Phương pháp gài bẫy nhân độc lập (IS) .................................................70 3.8. Cài đặt các tấn công.....................................................................................73 3.8.1. Tấn công dựa trên thời gian...................................................................73 3.8.2. Tấn công dựa trên các lỗi ngẫu nhiên ....................................................75 3.9. Phương pháp tấn công bằng nhân tử hóa số N sử dụng định lý Fermat ........76 3.9.1. Bổ đề 1..................................................................................................76 2 3.9.2. Định lý Fermat ......................................................................................77 3.9.3. Xây dựng chương trình..........................................................................79 KẾT LUẬN...........................................................................................................81 TÀI LIỆU THAM KHẢO .....................................................................................82 3 MỞ ĐẦU Ngày nay, thuật ngữ “thời đại thông tin” đã tr ở nên quá phổ biến đối với nhiều người. Có thể nói, chưa bao giờ công nghệ thông tin lại phát triển bùng nổ như hiện nay. Tin học có mặt tại hầu hết trong các lĩnh vực của đời sống xã hội, đã, đang và sẽ còn tiếp tục đem lại những ứng dụng và lợi ích vô cùng to lớn cho con người. Tại hầu khắp các nước trên thế giới, tin học phát triển vượt bậc. Những hệ thống tin học không còn nhỏ lẻ, cục bộ, mà trái lại, chúng không ngừng phát triển trở thành những hệ thống kiến trúc tin học lớn, đồ sộ và mang tính toàn cầu, đặc biệt là các hệ thống mạng truyền tin và các hệ thống thương mại điện tử. Các hệ thống này ngày càng đóng vai trò thiết yếu trong mọi lĩnh vực, mọi hoạt động của toàn xã hội. Điều này cũng đ ồng nghĩa với việc, nhu cầu đảm bảo an toàn và bảo mật thông tin phải được đặt lên hàng đầu và có tầm quan trọng thời sự. Cũng chính vì vậy mà công nghệ mã hóa thông tin ngay từ khi ra đời đã phát tri ển nhanh chóng vượt bậc và đạt được rất nhiều kết quả ứng dụng sâu sắc. Một trong những công nghệ mã hoá hiện đại và có ứng dụng phong phú là công nghệ mã hóa khóa công khai, mà đại diện là hệ mật mã RSA. Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir và Len Adleman, công bố lần đầu vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ. Hệ mật được sử dụng trong lĩnh v ực đảm bảo tính riêng tư và cung cấp cơ chế xác thực dữ liệu số. Ngày nay, RSA đã đư ợc phát triển ứng dụng rộng rãi trong thương m ại điện tử. Nó được sử dụng trên Web servers và trên các Browsers nhằm đảm bảo an ninh đường truyền, được sử dụng trong việc tạo khóa và xác thực của mail, trong truy cập từ xa…. Tóm lại, RSA được ứng dụng trong các lĩnh v ực nơi mà an ninh an toàn thông tin được đòi hỏi. Ngay từ khi được công bố, hệ RSA đã đư ợc phân tích hệ số an toàn bởi nhiều nhà nghiên cứu. Thực tế, vấn đề thám mã đối với hệ mật RSA hiện tại đang được các nhà nghiên cứu tập trung khai thác các sơ hở của RSA như: tấn công vào 4 số mũ công khai hoặc số mũ bí mật thấp, tấn công vào các tham số nguyên tố p, q bé hoặc cách xa nhau lớn, hoặc họ tập trung vào việc phân tích nhân tử số n (modul của RSA). Từ những vấn đề trên, tôi chọn đề tài nghiên cứu “Tìm hiểu một số kỹ thuật tấn công hệ mật RSA”. Đề tài cung cấp các kiến thức về phương pháp bảo vệ an toàn thông tin dữ liệu có tính an toàn cao nhất hiện nay là dùng hệ mã khoá công khai RSA, các kiến thức cơ bản về các hệ mật mã. Đồng thời trình bày một số phương pháp tấn công RSA . Luận văn gồm 3 chương với các nội dung sau: Chương I: Trình bày một số cơ sở toán học được dùng để xây dựng hệ mật mã công khai RSA và là công cụ để mô tả, phân tích các điểm yếu, phương pháp tấn công hệ mật RSA được đề cập ở các chương tiếp theo. Chương II: Giới thiệu về một số hệ mật đang được ứng dụng gồm các hệ mật cổ điển và hệ mật khóa công khai. Nghiên cứu các vấn đề về hệ mật khóa công khai và đi sâu tìm hiểu hệ mật RSA: Phương pháp mã hóa và giải mã, độ an toàn của RSA, vấn đề quản lý khóa. Chương III: Trình bày về một số phương pháp tấn công hệ mật RSA. Cài đặt ứng dụng về phương pháp tấn công RSA bằng nhân tử hóa số N sử dụng định lý Fermat. Luận văn đã được kiểm tra kỹ nhưng cũng không tránh khỏi những sai sót, rất mong nhận được sự đóng góp ý kiến của quý thầy cô, bạn bè và các đồng nghiệp để hoàn thiện hơn nữa. 5 CHƯƠNG I. CÁC KHÁI NIỆM CƠ BẢN Chương này trình bày một số khái niệm cơ sở toán học, lý thuyết số liên quan được dùng để xây dựng hệ mật mã công khai RSA và là công cụ để mô tả, phân tích các điểm yếu, phương pháp tấn công hệ mật RSA. 1.1. Một số khái niệm toán học 1.1.1. Số nguyên tố và số nguyên tố cùng nhau 1.1.1.1. Các ước số Nói rằng, b (một số khác 0) là ước số của a nếu a=mb, với một giá trị m nào đó. Ở đây a, b, m là các số nguyên. Như vậy, b là ước số của a, nếu như chia a cho b không còn lại số dư. Để ký hiệu b là ước số của a thường sử dụng cách viết ba. Có các quan hệ sau: o Nếu a1, thì a =  1. o Nếu ba và ab, thì a = ±b. o Số b bất kỳ khác 0 là ước số của 0. o Nếu bg và bh, thì b(mg + nh) đối với bất kì số nguyên m, n. Để chứng minh khẳng định cuối cùng, cần chú ý như sau: nếu bg thì g có dạng g = b * g1, đối với số nguyên g1 nào đó, nếu bh thì h có dạng h = b * h1, đối với giá trị nguyên h1 nào đó, Vì vậy: mg + nh = mbg1 + nbh1 = b * (mg1+ nh1) Cuối cùng, b là ước số của mg + nh. Ví dụ: Các số 1, 2, 3, 4, 6, 8, 12 và 24 là các ước số của 24. 1.1.1.2. Các số nguyên tố Số nguyên dương p lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có các ước số dương là 1 và p. 6 Ví dụ: 2, 3, 5, 7, 11, 13, … Một số nguyên bất kỳ a > 1 có thể phân tích thành các thừa số và được trình bày dưới dạng: a = p11 p2 2 ... pt t , ở đây: p1 0. Ví dụ: 91 = 7 * 13; 11011 = 7 * 112 * 13. Nếu P là kí hiệu tập hợp tất cả các số nguyên tố, thì đối với một số nguyên dương bất kì được viết duy nhất dưới dạng: a = ∏ p p, a ở đây tất cả các ap ≥ 0 P Ví dụ: 3600 = 24 * 32 * 52. 1.1.1.3. Các số nguyên tố cùng nhau Chúng ta sẽ sử dụng ký hiệu gcd( a, b) để chỉ ước số chung lớn nhất (UCLN) của số a và b. Nói rằng, một số nguyên dương c là UCLN của a và b, nếu: o c là ước số của a và b. o Ước số bất kỳ của a và b đều là ước số của c. Có thể định nghĩa tương đương như sau: gcd(a, b) = max [k, khi ka và kb]. Bởi vì, đòi hỏi rằng UCLN là một số dương, chúng ta có gcd(a, b) = gcd(a, –b ) = gcd(–a, b) = gcd(–a, –b ). Nói chung, gcd(a, b) = gcd(|a|, |b|). Ví dụ: gcd(60, 24 ) = gcd(60, –24 ) = 12. 7 Bởi vì tất cả các số nguyên khác không đều là ước số của số 0, chúng ta luôn luôn có: gcd(a, 0 ) = |a|. Dễ dàng xác định được UCLN của hai số nguyên dương, nếu các số này được trình bày dưới dạng tích của các thừa số nguyên tố. Ví dụ: 300 = 22 * 31 * 52, 18 = 21 * 32. gcd(18, 300) = 21× 31× 50 = 6. Trong trường hợp chung: k = gcd(a, b)  kp = min (ap, bp), đối với tất cả các p. Các số nguyên a và b là nguyên tố cùng nhau, nếu chúng không có ước số nguyên tố chung, hay ước số chung duy nhất của chúng là 1. Nói một cách khác a và b là hai số nguyên tố cùng nhau nếu gcd(a, b) = 1. Ví dụ: Số 8 và số 15 là các số nguyên tố cùng nhau, bởi vì ư ớc số của 8 là 1, 2, 4 và 8, còn các ư ớc số của 15 là 1, 3, 5 và 15. Như vậy, 1 là ước số chung duy nhất của hai số này. 1.1.2. Đồng dư thức Định nghĩa 1: Cho a là một số nguyên và m là một số nguyên dương. Khi đó ta ký hiệu a mod m là số dư khi chia a cho m. Từ định nghĩa số dư, ta suy ra rằng a mod m là số nguyên r sao cho: a=qm + r và 0≤ r < m. Ví dụ: Ta thấy: 17 mod 5 =2, -133 mod 9 =2 và 2001 mod 101 = 82. 8 Định nghĩa 2 (Đồng dư): Nếu a và b là hai số nguyên và m là một số nguyên dương, thì a được gọi là đồng dư với b theo modulo m nếu a-b chia hết cho m và được ký hiệu a≡b (mod m). Chú ý rằng a ≡ b (mod m) nếu và chỉ nếu a mod m = b mod m. Ví dụ: 5≡7 (mod 2) vì 5 mod 2 =1 và 7 mod 2 =1. Một số tính chất quan trọng của đồng dư: Tính chất 1: Nếu a1 ≡ b1 mod m và a 2 ≡ b2 mod m thì a1 + a 2 ≡ b1 + b2 mod m Chứng minh: Từ giả thuyết ta có a1 = mt1 + b1 và a 2 = mt 2 + b2 , suy ra a1 + a 2 =b1 +b2 + (t1 + t 2 )m , điều này có nghĩa là a1 + a 2 ≡ b1 + b2 mod m . Tính chất 2: Nếu a1 ≡ b1 mod m và a 2 ≡ b2 mod m thì a1 *a 2 ≡ b1 * b2 mod m Chứng minh: Từ giả thuyết ta có a1 = mt1 + b1 và a 2 = mt 2 + b2 , suy ra a1 * a 2 =b1 * b2 + (b1t 2 + b2 t1 + mt1t 2 )n , điều này có nghĩa là a1 *a 2 ≡ b1 * b2 mod m Tính chất 3: Nếu như gcd(d , m) = 1, a ≡ b mod m, a = a1d , b = b1d , thì a1 ≡ b1 mod m Chứng minh: Từ giả thuyết ta có (a1 − b1 )d | n , mà gcd( d , m) = 1 , nên suy ra (a1 − b1 ) | m , hay a1 ≡ b1 mod m . Ví dụ: Chứng minh rằng 37n+2+16n+1+23n chia hết cho 7. Giải: Rõ ràng chúng ta thấy rằng 37 ≡ 2 mod 7 , 16 ≡ 2 mod 7 và 23 ≡ 7 mod 7 , từ tính chất 2 có: 37 n+ 2 ≡ 2 n+ 2 mod 7 , 16 n+1 ≡ 2 n+1 mod 7 , 23 n ≡ 7 n mod 7 . Từ tính chất 1 có: 37n+2+16n+1+23n ≡ 7.2 n mod 7 , và từ tính chất 3 suy ra điều phải chứng minh. 9 1.1.3. Không gian Zn và Zn* Không gian Zn (các số nguyên theo modulo n) Không gian các số nguyên theo modulon là tập hợp các số nguyên {0, 1,…, n-1} bao gồm hai phép toán cộng và nhân. Việc cộng và nhân trong Zn được thực hiện như trong phép cộng và nhân các số nguyên, ngoại trừ một điểm là các kết quả sẽ được rút gọn theo modulon. Ví dụ: Tính 11 * 13 trong Z16 . Tương tự như với các số nguyên ta có 11 * 13 = 143 . Để rút gọn 143 theo modulo 16, ta thực hiện phép chia bình thường: 143 = 8 × 16 + 15 , bởi vậy 143 mod16 = 15 . Do đó 11 × 13 = 15 trong Z16 . Không gian Zn*: Là tập hợp các số nguyên p ϵ Zn, nguyên tố cùng nhau. Tức là Zn* ={ p ϵ Zn | gcd(n, p)=1}, Ф(n) là số phần tử của Zn*. Nếu n là một số nguyên tố thì Zn* ={ p ϵ Zn | 1≤ p ≤ n -1} Ví dụ: Z2 = {0, 1} thì Z2* = {1} vì gcd(1, 2) =1. 1.1.4. Phần tử nghịch đảo Định nghĩa: Cho a ∈ Z n . Phần tử nghịch đảo của a là phần tử b ∈ Z n sao cho a * b ≡ b * a ≡ 1 mod n . Kí hiệu phần tử nghịch đảo của a là a-1. Tính chất: • Cho a, b ϵ Zn. Phép chia a cho b theo modulo n là tích của a và b theo modulo n, và chỉ được xác định khi b có nghịch đảo theo modulo n. • Cho a ϵ Zn, a là khả nghịch khi và chỉ khi gcd(a, n) =1. • 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. Ví dụ: 4-1 ≡ 7 (mod 9) vì 4×7 ≡ 1 ( mod 9) 10 1.1.5. Khái niệm nhóm, nhóm con, nhóm Cyclic Định nghĩa: Nhóm là bộ đôi (G, * ), trong đó G là tập khác Ф, và * là một phép toán hai ngôi trong G thỏa mãn ba tiên đ ề sau: 1. Phép toán nhóm kết hợp a * (b * c) = (a * b) * c ∀a, b, c ϵ G 2. Có một phần tử 0 ϵ G được gọi là phần tử đơn vị thỏa mãn ∀a ϵ G a*0=0*a 3. Với mỗi a ϵ G, tồn tại một phần tử a-1 ϵ G được gọi là nghịch đảo a * a-1 = a-1 * a =0 Nhóm con: Bộ đôi (S, *) được gọi là nhóm con của (G, *) nếu: 1. S ⊂ G, phần tử trung gian e ϵ S 2. x, y ϵ S ⇒ x * y ϵ S. Nhóm Cyclic: Nhóm G được gọi là nhóm Cyclic nếu tồn tại một phần tử α ϵ G sao cho với mỗi b ϵ G có một số nguyên i sao cho b = αi . Phần tử α như v ậy được gọi là phần tử sinh của G. Nếu G là một nhóm và a ϵ G thì tập tất cả các lũy thừa của a sẽ tạo nên một nhóm con Cyclic của G. Nhóm này được gọi là nhóm con sinh bởi a và được ký hiệu là . Ví dụ: (Z+, *) là một nhóm Cyclic có phần tử sinh là 1. 1.1.6. Hàm Ф Euler Định nghĩa: Với n ≥ 1 chúng ta gọi φ(n) là tập các số nguyên tố cùng nhau với n nằm trong khoảng [1, n]. Tính chất: 1. Nếu p là số nguyên t ố → φ(p) = p-1 2. Nếu p = m.n, gcd(m, n) =1 → φ(p) = φ(m). φ(n) 11 3. Nếu n = là thừa số nguyên tố của n thì → φ(n) = n … 1.1.7. Các phép toán cơ bản trong không gian modulo Cho n là một số nguyên dương. Các phần tử của Zn sẽ được biểu thị bởi các số nguyên { 0, 1, 2, …, n-1}. Ta thấy rằng, nếu a, b ϵ Zn thì (a+b)modn= Vì vậy, phép cộng (và trừ) theo modulo có thể thực hiện được mà không cần thực hiện các phép chia. Phép nhân modulo của a và b có thể được thực hiện bằng cách nhân các số nguyên thông thường rồi lấy phần dư của kết quả sau khi chia cho n. Các phần tử nghịch đảo trong Zn có thể được tính bằng cách dùng thuật toán Euclie mở rộng được mô tả dưới đây: Thuật toán (Tính các nghịch đảo trong Zn) VÀO: a ϵ Zn RA: a-1 mod n (nếu tồn tại) 1. Dùng thuật toán Euclide mở rộng để tìm các số nguyên x và y sao cho ax + ny = d trong đó d = gcd(a, n) 2. Nếu d > 1 thì a-1 mod n không tồn tại. Ngược lại return (x). Phép lũy thừa theo modulo có thể được thực hiện có hiệu quả bằng thuật toán nhân và bình phương có lặp. Đây là một thuật toán rất quan trọng trong nhiều thủ tục mật mã. 12 Cho biểu diễn nhị phân của a là: trong đó mỗi ki ϵ {0, 1} khi đó Thuật toán nhân và bình phương có lặp để lấy lũy thừa trong Zn VÀO: a ϵ Zn và số nguyên k, ( 0 ≤ k < n) có biểu diễn nhị phân: k= RA: ak mod n 1. Đặt b ← l. Nếu k = 0 thì return (b) 2. Đặt A ← a 3. Nếu k0 = 1 thì đặt b ← a 4. For i from l to t do 1. Đặt A ← A2 mod n 2. Nếu ki = l thì đặt b ← A*b mod n 5. Return (b). 1.1.8. Hàm một phía và hàm một phía có cửa sập 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í dụ: Biết giả thiế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. 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. 13 Ví dụ: y = f(x) = xb mod n, tính xuôi thì dễ nhưng tính ngược x=ya mod n thì khó vì phải biết a với a*b ≡ 1 (mod (φ(n))) trong đó φ(n) = (p-1)(q-1). Nhưng nếu biết cửa sập p, q thì việc tính n = p*q và tính a trở nên dễ dàng. Hộp thư là một ví dụ về hàm một phía có cửa sập. Bất kỳ ai cũng có thể bỏ thư vào thùng. Bỏ thư vào thùng là một hành động công cộng. Mở thùng thư không phải là hành động công cộng. Nó là việc khó khăn, bạn sẽ cần đến mỏ hàn để phá hoặc những công cụ khác. Tuy nhiên nếu bạn có “cửa sập” (Trong trường hợp này là chìa khóa của hòm thư) thì công việc mở hòm thư thật dễ dàng. 1.1.9. Hàm Euler, định lý Euler và định lý Fermat Định nghĩa (Hàm Euler) Cho n là số nguyên dương, đặt  (n) là số các phần tử của tập hợp, mà tập này là các số nguyên trong khoảng [1, n] và nguyên tố cùng nhau với n, thì  (n) gọi là hàm Euler. Ta công nhận một số tính chất quan trọng của hàm Euler: 1.  (1) = 1 2. Nếu p là số nguyên tố thì  ( p) = p − 1 3. Nếu như p và q là hai số nguyên tố cùng nhau thì  ( pq) =  ( p) *  (q) 4.  ( p s ) = p s −1 ( p − 1) 5. Nếu như n = p1e p2e ... pke , ở đây p1 , p 2 , …, pk là số nguyên tố, thì 1   (n) = n1 −  1 p1 2 k  1   1   1 − ...1 −    p2   pk   Định lý Euler: Cho n > 1, gcd(a, n) = 1 và  (n) là hàm Euler. Khi đó ta có: a  ( n ) ≡ 1 mod n Ví dụ: a = 3, n = 10, (10) = 4, 34 = 81 ≡ 1 mod 10, 14 a = 2, n = 11, (11) = 10, 210 = 1024 ≡ 1 mod 11. Các hệ quả của định lý Euler: Hệ quả 1: nếu gcd(c, n)=1 và a≡b (mod  (n) ) với a, b là 2 số tự nhiên, thì Hệ quả 2: nếu e, d là các số nguyên thỏa mãn thì với mọi số c nguyên tố cùng nhau với n, ta có Định lý Fermat (bé): Cho p là số nguyên tố, a là số nguyên dương không chia hết cho p. Khi đó ta có: Từ định lý Fermat chúng ta có các hệ quả quan trọng sau: Hệ quả 1: Cho a ∈ Z , p là số nguyên tố, thì ta có: Hệ quả 2: Cho a, b ∈ Z , p là số nguyên tố (a + b) n ≡ a n + b n mod p Ví dụ: Chứng mình rằng 118 +218 +318 +418 +518 +618 ≡ –1 mod 7 Giải: Các số 1, 2, 3, 4, 5, 6 là số nguyên tố cùng nhau với 7. Nên theo định lý Fermat chúng ta có các phương trình sau: 16 ≡ 1 mod 7 ; 2 6 ≡ 1 mod 7 ; 36 ≡ 1 mod 7 ; 4 6 ≡ 1 mod 7 ; 56 ≡ 1 mod 7 ; 6 6 ≡ 1 mod 7 Lấy bậc ba hai vế từng phương trình và cộng lại ta được: 118 +218 +318 +418 +518 +618 ≡ 6 mod 7 = −1 mod 7 1.1.10. Bậc và căn nguyên thủy Định nghĩa 1 (Bậc) 15 Cho gcd(a, n) = 1. Bậc a mod n là số nguyên dương nhỏ nhất  thỏa mãn phương trình đ ồng dư thức: a ≡ 1 mod n , Kí hiệu bậc là Ordn(a). Ví dụ: Tìm bậc của 2 mod 5 Giải: 21 mod 5 = 2; 22 mod 5 = 4; 23 mod 5 = 3; 24 mod 5 = 1; vậy Ord5(2) = 4. Định nghĩa 2 (Căn nguyên thủy) Nếu như bậc của a modulo n bằng giá trị của hàm Euler của n. Thì a gọi là căn nguyên thủy của n. Ví dụ: Số 2 là căn nguyên thủy của 5. Vì Ord5(2) =  (5) = 4. 16 CHƯƠNG II. HỆ MẬT MÃ KHÓA CÔNG KHAI Chương này giới thiệu và phân biệt các hệ mật mã khóa bí mật và hệ mật mã khóa công khai. Tiếp theo, ta trình bày về hệ mật khóa công khai RSA: phương pháp mã hóa và giải mã, độ an toàn của RSA, vấn đề quản lý khóa. 2.1. Tổng quan về các hệ mật mã 2.1.1. Hệ mã hóa đối xứng Định nghĩa: Hệ mã hóa khóa đối xứng là hệ mã hóa mà biết được khóa lập mã thì có thể “dễ” tính được khóa giải mã và ngược lại. Đặc biệt một số hệ mã hóa có khóa lập mã và khóa giải mã trùng nhau (ke=kd), như hệ mã hóa “dịch chuyển” hay DES. Hệ mã hóa khóa đối xứng còn gọi là Hệ mã hóa khóa bí mật, hay khóa riêng, vì phải giữ bí mật cả 2 khóa. Trước khi dùng hệ mã hóa khóa đối xứng, người gửi và người nhận phải thỏa thuận thuật toán mã hóa và khóa chung (lập mã hay giải mã), khóa phải được bí mật. Độ an toàn của hệ mã hóa loại này phụ thuộc vào khóa, nếu để lộ ra khóa này nghĩa là b ất kỳ người nào cũng có thể mã hóa và giải mã thông báo trong hệ thống mã hóa. Sự mã hóa và giải mã của hệ thống mã hóa khóa đối xứng biểu thị bởi: và . Hình 2.1: Mô hình hệ thống mã hóa đối xứng 17 Hệ mã hóa khóa đối xứng thường được sử dụng trong môi trường mà khóa chung có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ. Hệ mã hóa khóa đối xứng thường dùng để mã hóa nh ững bản tin lớn, vì tốc độ mã hóa và giải mã nhanh hơn hệ mã hóa công khai. 2.1.1.1. Mã dịch Hãy xét R = C = K = Z26; x, y ϵ Z26. Với mỗi 0 ≤ K ≤ 26, ta định nghĩa: Và Hệ mật sử dụng Z26 vì trong bảng chữ cái tiếng Anh có 26 chữ cái. Chúng ta có thể sử dụng mã dịch để mã hóa văn bản tiếng Anh bằng cách thiết lập tương ứng giữa các ký tự trong bảng chữ cái với thặng dư 26 như sau: A↔0, B↔1,…, Z↔25 . Cụ thể như sau: A 0 B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9 K 10 L 11 M 12 N 13 O 14 P 15 Q 16 R 17 S 18 T 19 U 20 V 21 W 22 X 23 Y 24 Z 25 Ví dụ: Với K=11. Chúng ta cần mã hóa bản rõ sau: BACHKHOAHANOI Chúng ta sẽ chuyển bản rõ thành một chuỗi số nguyên dựa vào bảng chuyển đổi ở trên thu được chuỗi: 1 0 2 7 10 7 Sau đó áp dụng hàm mã hóa 14 0 7 0 13 được chuỗi số nguyên sau: 18 14 8 12 11 13 18 21 18 25 11 18 11 24 25 19 Sau đó ta chuyển chuỗi số nguyên này trở lại các ký tự, ta được: MLNSVSZLSLYZT Để giải mã bản đã mã hóa, đầu tiên chúng ta phải chuyển bản mã thành chuỗi số nguyên, sau đó trừ mỗi số đi 11 (rút gọn mod 26), và cuối cùng chuyển chuỗi số nguyên về thành các ký tự. Chú ý: Chúng ta có thể thấy hệ mật mã dịch (modulo 26) là không an toàn do nó có thể bị giải mã bằng phương pháp vét cạn khóa. Do không gian khóa chỉ có 26 cho tới khi thu được một bản rõ có giá trị nên rất dễ dàng để kiểm thử các giá trị ý nghĩa xác định. Ví dụ: Giả sử có xâu bản mã sau: XKEXKURZKMZYQURKS Chúng ta lần lượt thử các giá trị khóa sau: VIDVJTQYJLYXPTQJR UICUISPXIKXVOSPIQ THBTHROVHJVUNROHP SGASGQNUGIUTMQNGO RFZRFPMTFHTSLPMFN QEYQEOLSEGSRKOLEM PDXPDNKRDFRQJNKDL OCVOCMJQCEQPIMJCK 19 , ,… thu được các bản rõ có thể có NBUNBLIPBDOHLIBJ MATMAKHOACONGKHAI Tại điểm này ta xác định được bản rõ và có thể dừng lại. Khóa tìm được là K=9. Trung bình có thể tìm ra bản rõ sau khi thử 26/2 = 13 quy tắc giải mã. Như vậy, để đảm bảo một hệ mật có độ an toàn thì không thể xảy ra việc vét cạn khóa. Có thể khắc phục bằng cách chọn không gian khóa lớn hơn. Tuy nhiên, không gian khóa lớn cũng chưa đủ để đảm bảo độ an toàn của hệ mật. 2.1.1.2. Hệ mật mã thay thế Cho R = C = Z26. K gồm tất cả các hoán vị có thể có của 26 ký tự: 0, 1, 2, …, 25. Với mỗi hoán vị π ϵ K ta định nghĩa: , với Và là hàm ngược của π. Trong hệ mã này, R và C tương ứng với 26 chữ cái trong bảng chữ cái tiếng Anh. Ví dụ một hoán vị ngẫu nhiên π sau (các ký tự của bản rõ viết bằng chữ thường, bản mã viết bằng chữ hoa): a b c d e f g h i j k l m X N Y A H P O G Z Q W B T n o p q r s t u v w x y z S F L R C V M U E K J D I 20
- Xem thêm -

Tài liệu liên quan