Tài liệu Nghiên cứu những phương pháp tấn công giao thức yếu dùng hệ mật mã khoá công khai

Đ Ạ I H Ọ C Q U Ố C GIA H À N Ộ I KHOA CÔNG NGHÊ N g u y ễ n T h ị P h ư ơ n g Liên NGIỈIÊN CỨU NHỮNG PHƯƠNG PHÁP TẤN CÔNG GIAO THỨC YÉU s ử DỤNG HỆ MẬT MÃ KHOÁ CÔNG KHAI C huyên ngành: CÔNG N G H Ệ THÔNG TIN M ã sổ: 1.01.10 LUẬN VĂN THẠC s ĩ NGƯỜI HƯỚNG DẢN KHOA HỌC: TS. NGUYỄN NGỌC CƯƠNG Hà Nội - 2003 *■: :: V'U?/J31 Trang 2 2.2.5 Giao thức modal chung và các phương pháp tẩn công.....................25 2.2.6 Giao thức số mũ công khai nhỏ.... ........................................... 31 2.2.7 Giao thức sổ m ũ bí mật n h o .................... ............................... 33 2.2.8 Giao thức entropy thấp........... ............................................... 36 2.2.9 Giao thức khoủ đổi xứng...................................................... 38 2.2. ỉ 0 Tóm tắt và phản tích............................................................ 42 CHƯƠNG 3 - VỀ VIỆC LẬP TRÌNH MÔ PHỎNG PHƯƠNG PHÁP TÁN CÔNG GIAO THỨC s ử DỤNG HỆ MẬT MÃ KHOÁ CÔNG * ề ề KHAI RSA CÓ MODUL CHUNG...................................................... 44 3.1. YÊU CẦU TÍNH TOÁN SÓ CỠ LỚN.......................................... 44 3.2. BIÉƯ DIỄN SÓ CỠ LỚN............................................................ 45 3.3. CÁC THUẬT TOÁN TÍNH TOÁN SÓ CỠ LỚN............................ 47 3.3.1 Mội sổ khái niệm......................................................... ........ 47 3.3.2 So sảnh................................................................................. 48 3.3.3 Phép cộng........................... ................................................ 49 3.3.4 Phép trừ............................................................................... 50 3.3.5 Phép nhân...................................................................... ..... 50 3.3.6 Phép chia............................................................................. 5ì 3.3.7 Luỹ thừa.... .......................................................................... 52 3.3.8 Ước số chung lớn nhất............................................................53 3.3.9 Phép tỉnh nhân theo moduỉ p ...................................................54 3.3.10 Phép tính luỹ thừa theo moduỉ p............................................ 54 3.3.1 Ị Tìmphần tử nghịch đảo theo moduì p .....................................55 3.3. ỉ 2 Phép cộng có dấu................................................................ 56 3.3.13 Phép trừ có dấu....... ........................................................... 57 3.3. ì 4 Phép nhân có dấu................................................................57 3.4. MỘT SÓ NÉT VỀ LẬP TRÌNH TÍNH TOÁN SỐ CỠ LỚN.............. 58 3.5. GIÓI THIỆU CHƯƠNG TRÌNH TÁN CÔNG GIAO THÚC s ử DỤNG HỆ MẬTMẰ RSA Có MODUL c h u n g ........................................... 59 3.5. ỉ Bộ công cụ toán h ọ c ............ ........................................................................... 59 3.5.2 Trình minh hoạ thuật toán tấn công giao thức sư dụng hệ mật mã RSA cỏ modul chung....................................... ............................... 60 KÉT LUẬN......................................................................................... 64 TÀI LIỆU THAM KHẢO........................ ............................................6 6 PHỤ LỤC............................................... ............................................67 i ra na, 4 MỞ ĐẦU T rư ớ c đây, m ật mã h ầ u n h ư chỉ được quan tâm tron g lĩnh vực quân sự và n g o ại giao. T u y nhiên, tro n g thời đại m áy tính điện tử, đặc biệt khi m ạn g m áy tính trở nên phổ biến, các dịch vụ thư tín điện tử, th ư ơ ng mại điện tử, g iao d ịch tiền tệ., trên m ạ n g p h át triển, và những cơ sở dữ liệu k h ổ n g lồ chứ a các th ô n g tin riêng tư đư ợ c ỉưu g iữ tro n g nhừng chiếc m áv tính kết nối m ạng thì việc sử d ụ n g m ật m ã để đ ảm bảo an toàn m ạng, báo m ật và xác thực dữ liệu đã đ ư ợ c phổ b iến rộ n g rãi tro n g x ã hội, T ừ cuối n h ữ n g n ăm 70, các nhà lập mã đà phát triển các hệ m ật m ã có độ m ật đ ư ợ c bảo đảm b ằ n g đ ộ ph ứ c tạp tính toán. N h ữ n g th uật toán m ật m ã này yêu cầu khả n ăn g tính toán phức tạp khi tấn cô n g và đư ợc thiết kế để c h ố n g lại sự tấn cô n g c ủ a các đối thủ có thời gian giới hạn. Ý tư ở n g cơ bản ià xây d ự n g n h ữ n g hệ th ố n g sao cho biết phần khoá lập m ã và thuật toán lập m ã vẫn rất k h ó tìm đư ợc cách giải m ã và thư ờn g là khó tìm đ ư ợ c phần khoá giải mã. P h ần kho á lập m ã v à phần k h o á giải mà khác nhau, trong đó phần khoá lập m ã là c ô n g khai, p h ần k h o á giải m ã là bí mật. Và hệ thố ng này đư ợc gọi là hệ m ật m ã k h o á cô n g khai, ví dụ n h ư hệ mật mã R SA , R abin, E lG am al,.. Khi m ột thuật toán m ật m ã đ ư ợ c sử dụng để bảo m ật hay xác thự c dữ liệu, nó sẽ nằm tro n g k h u ô n khố m ột giao thức xác định, thích hợp để xử lý d ừ liệu. C h ính vì vậy, từ khi hệ m ật m ã khoố công khai ra đời đã có rất nhiều giao thứ c đư ợ c thiết kế đ ế n â n e cao độ tin cậy và xác thực. M ục đích của g iao Trang 5 thức là đàm bao thuật toán mật mà sê thực sự cung cấp sự báo mật hay xác thực mà hệ thống yêu cầu. C ó nhiều giao thức đ ứ n g v ừ n g và được đánh giá tôt sau một khoáng thời gian dài sử d ụ n g như giao thức X.509, Kerberos... Tuy nhiên cũ n g có nhiều giao thức n hanh ch ón g bộc lộ nhược điếm và bị tấn công mặc d ù thuật toán m ật m ã sử d ụ n g trone, đó được đánh giá là tốt. Vì vậy việc đánh giá độ an toàn cúa giao thức là rất quan trọng. Đ ộ an loàn của giao thức k h ô n g chỉ phụ thuộc v à o th uật toán m ật m ã m à còn phụ thuộc vào việc thiết kể giao thức và cho đến nay đã có m ột số chu yên n gành ra đời đê nghiên cứu về độ an toàn của g iao thức chẳng hạn Logic BAN, ch ứ n g minh tri thức không V.V.. về mặt thực tiễn, chúng ta cũng biết rằng trong nhiều mạng máy tính người ta sử d ụ n g giao thức để đảm bảo bảo mật và xác thực dữ liệu, chính vi vậy việc thiết kế m ột g iao thức đảm bảo độ an toàn và tin cậy là vấn đề quan trọng. Bên cạnh đó, đổi với người tấn cô ng thì việc tìm ra sơ hở của g iao thức cũ n g là m ột thành công. Vấn đ ề tẩn cô n g m ột giao thức yếu, trong đó nó yếu không phải do thuậl toán m ã hoá y ếu m à vì n h ữ n g thiểu sót trong việc thiết kế giao thức, đà được nghiên cứu và nhiều kết quả đã đư ợc công bố trên thế giới. Đối với m ột đơn vị n g h iên cứu về các hệ thố ng m ật mã, thì đây là một trong nhữ ng vấn đề cần thiết, làm cơ sở ch o n h ữ n g nghiên cứu tiếp theo về các hệ thống m ật mă. T ừ việc ph ân tích n h ữ n g th iếu sót trong thiết kế 2 ,iao thức m ật m ã sẽ rút ra n hừ n g chỉ dẫn cần thiết để phát triển các eiao thức tốt. Vì vậy, là người công tác ở một đơn vị nghiên cứu về các hệ thống mật mã tôi xin được đăng ký thực hiện đề tài: ’’Nghiên cứu những phương pháp tấn công giao thức yếu sử dụng mật mã khoá công khai" cho luận văn tốt nghiệp thạc sĩ của mình. Tran li 6 Mục tiêu của đề tài là nghiên cứu cơ sở lv thuyết và các phương pháp tấn công giao thức yếu, xảy dựng chương trình mô phỏng việc tân công giao thức sử dụng hệ mật mã khoá công khai RSA có modul chung (là một trong nhùng tấn công hay và bố ích). Tuy nhiên để tránh việc hiểu lầm ràng các hệ thống mật mâ khoá đổi xứng không có các điếm yếu trong sử dụng, trong luận văn còn nêu ra các giao thức sử dụng DES thất bại trong việc xác thực. Luận văn gồm phần mở đầu, phần kết luận, ba chương chính, tài liệu tham khao và phần phụ lục. Trong đó, Chương 1. NGHIÊN cứu HỆ MẬT KHOÁ CÔNG KHAI Chương 2. NGHIÊN cửu CÁC PHƯƠNG PHÁP TÁN CÔNG GIAO THỨC YÉU Chương 3. VỀ VIỆC LẬP TRÌNH MÔ PHONG PHƯƠNG PHÁP TÁN CÔNG GIAO THÚC sử' DỤNG HỆ MẬT MẢ KHOÁ CÔNG KHAI RSA c ó MODUL CHUNG Phụ lục là các chương trình mô phỏng phương pháp tấn công giao thức sứ dụng hệ mật mã khoá công khai RSA có modul chunR. Cuối cùng, tôi xin chân thành cảm ơn thầy giáo hướng dẫn TS. Nguyễn Ngọc Cương, người đã trực tiếp hướng dẫn tôi viết luận văn thạc sĩ này. Tôi cũng xin chân thành cảm ơn tất cả các thầv cô trong khoa Công nghệ thông tin, Viện Công nghệ thông tin đã trang bị cho tôi nhùng kiến thức cơ bản đế tôi có thế hoàn thành được luận văn. Xin chân thành cảm ơn các bạn bè, đồng nghiệp, những người đã có rất nhiều ý kiến đóng góp, giúp đờ tôi trong quá trình làm luận văn. Và tôi xin bày to lòng biết ơn đến nhừng naười thân trong gia đình đã luôn dành cho tôi sự quan tâm và động viên. Trang 7 CHƯƠNG 1 - HỆ MẬT MẢ KHOÁ CỒNG KHAI T ro n g mô hình m ật m ã cổ điển, người gửi và người nhận cùn g chọn m ột kh oá K bí mật, sau đó d ù n g K đê tạo thuật toán lập m ã e K và thuật toán giái m ã clK. C ác hệ m ật thuộc loại này còn được gọi là các hệ m ật khoá bí m ật vì việc đế lộ eK sẽ làm cho hệ th o n g m ất an toàn. N hư ợc điêm cùa hệ mật này là nó yêu cầu phải có th ô n g tin trước về khoá K giữa người gửi và người nhận qua m ộ t kênh an toàn trư ớ c khi gửi m ột bản mã bất kỳ. C hính vì vậy, náy sinh V tư ớ n g xây d ự n g m ột hệ mật m ã sao cho biết dược phần công khai củ a khoá K và thuật toán lập m ã ÜK vẫn rất khó giải mã, và ih ư ờng là khó tìm đư ợc phần khoá giải m ã K dù thuật toán giải m ã có thể dược biết. T ừ cuối nh ữ n g năm 70, các nhà lập m ã đà phát triển các hệ m ật mã có độ mật đ ư ợ c bảo đảm b àn g độ phức tạp tính toán. Nhừna, thuật toán mật mã này yêu cầu khả năng tính toán phức tạp khi tấn công và đư ợc thiết kế để chố ng lại sự tấn côn g củ a các đối thú có thời gian giới hạn. T ro n g các hệ mật m ã này, phần k h o á lập m ã và phần khoá giải m ã khác nhau, trong đó phần khoá lập m ã, thuật toán lập mã, thuật toán giải mã là cô n g khai còn phần khoá giải mã là bí mật. Và hệ th ố n g này được gọi là hệ mật mã k ho á côn g khai. N ăm 1977, Ron Rivest, Adi S ham ir và Len A dlem an[5] đã đề xuất hệ m ật mã k ho á công khai đ ầu tiên, đó là hệ mật m à R SA nổi tiếng. Kẻ từ đó đà có m ột số hệ m ật mã kh oá công khai được công bố, độ mật của c h ú n g dựa Tran a 8 trên các bài toán tính toán khác nhau. Trong đó, quan trọng nhất là các hệ mậl sau: - Hệ mật RSA: độ bảo mật của nó dựa trên độ khócủa việc phân tích ra thừa số nguyên tổ các số nguyên lớn. - Hệ mật McEliece: Hệ này dựa trên lý thuyết mã đại số và vẫn được coi là an toàn. Hệ mật McEliece dựa trên bài toán giải mã cho các mà tuyến tính (là bài toán NP - đầy đủ). - Hệ mật Elgamal: Hệ Elgamal dựa trên tính khó giải của bài toán logarit rời rạc trên các trường hữu hạn. - Hệ mật Chor - Rivest: Hệ Chor - Rivest thuộc vào hệ mật xếp balô, dựa trên tính khó giải của bài toán tổng các tập con (bài toán này là bài toán NP - đầy đủ - thuộc vào một lớp khá lớn các bàitoán không có các thuật giải được biết trong thời gian đa thức). - Hệ mật trên các đường cong Elliptic. Trong chương này, chúng ta sẽ đề cập đến hai hệ mật mã khoá công khai được sử dụng nhiều nhất là Hệ mật RSA và Hệ mật Elgamal. Theo cách đặt tên truyền thống, ta đặt Alice, Bob để chỉ 2 thành viên muốn truyền thông cho nhau còn Oscar hay Marvin đế chỉ kẻ tấn công muốn nghe trộm hoặc giả mạo trong quá trình truyền thông giữa Aỉice và Bob. Trang 9 1.1. H Ệ M Ậ T M Ã RSA Hệ mật mã RSA được sử dụng để cun» cấp sự báo mật và đảm bảo tính xác thực cua dừ liệu số. Hiện nay RSA được sư dụng trong nhiều hệ thong thương mại. Các dịch vụ web server và web browser sử dụng nó đê đảm bảo an toàn việc truyền thông web, nó được sử dụng để đám báo bảo mật và xác thực của Email, đảm báo an toàn cho các phiên truy nhập từ xa và là bộ phận quan trọng của các hệ tlìống thanh toán thẻ tín dụng điện tử. Tóm lại, RSA thường được sir dụng trong các ứne. dụng cần sự bảo đám an toàn và bảo mật dữ liệu số. 1.1.1 Mô tả hệ mật RSA Trước tiên, ta hãy nhắc lại định nghĩa hệ mật. Một hệ mật là một bộ 5 (p, c -K £, $) thoả màn các điều kiện sau: 1 . p là một tập hữu hạn các bàn rõ có thể. 2 . c\ằ tập hữu hạn các bản mã có thể. 3. .^(không gian khoá) là tập hữu hạn các khoá có thể. 4. Đối với mồi K e J(cò m ột quy tắc mà eK: p~> ỚVà một quy tắc giải mà tương ứng dK e 'ĩò. Mồi eK: p c và dK: c -> p\à những hàm mà dis(eK(x)) = Xvới mọi bản rõ X G p. Tra nụ 10 Hệ mật mà RSA[5] sừ dụng các tính toán t r o n g z,„ trong đó n là tích của hai số nguyên tố phân biệt p, q và (ị)(n) = (p-1 )(q-l ). Mô tả hình thức của hệ mật này như sau: Cho n = p.q trong đó p và q là các số nguyên tố khác nhau. Đặt p= c= znvà định nghĩa J(= {(n,p,q,a,b): ab = l(modệ(n))} Với K = (n,p,q,a,b) ta xác định: eK(x) = xbmod n dK(y) = y*1modn và trong đó ( x , y e z„). Các giá trị n, b c ô n g khai còn các giá trị p, q, a g iữ bí mật. Ta hãy kiếm tra xem các p hép m ã và giải m ã có phải là các phép toán nghịch đ ảo của nhau hay không. Vì ab = l(mod<Ị)(n)) nên ta có ab = t.ệ(n) + 1 với m ột số nguyên t > 1 nào đó. G iả s ử X € zn; a. T rư ờ n g hợp (x,n) =1 —> x ^ '1’ m o d n = 1. Khi đó ta có: ya m o d n = (x b)a m od n = x lệ(n)+l m od n = ((xộ 1 -» d = p hoặc d = q. G i á sir d = p , k h i đ ó X = h p v ớ i 0 < h < q v à ( h ,n ) = 1, s u y ra: ya modn = (xh)a mod n s (habmodn)( pahmodn) modn Do (h,n) = 1 nên h llh m o d n = h Bên cạnh đó, p“bmodn = pabmod(p.q) = pab mod q = p . p ^ ’m od q = p.p^^m od q = p .(p l|)(p,)ộíq)m od q Vậy yil modn = h.p = p modn = h.p = X. 1.1.2 Thục thi hệ RSA De thiết lập hệ thống, Bob sẽ tuân theo các bước sau: 1. Bob tạo hai số nguyên tố lớn p và q. 2. Bob tính n = p.q và ệ(n) = (p-l)(q-l) 3. Bob c h ọ n m ộ t số ngẫu n hiên b (0 < b < ệ(n)) sao cho UCLN (b, Ộ(n)) = 1 4. Bob tính a = b’ 1 mođ(Ị)(n) bằng cách dùn^ thuật toán Euclide và giữ bí mật. 5. Bob côn g bố n và b tron g m ột thư mục và dùng chúng làm khoá công khai. Trang 12 Sau đây là một ví dụ về cách thức thực hiện cua hệ RSA (tất nhiên không mật). Giả sử Bob chọn p = 101 và q = 113. Khi đó n = 11413 và <Ị)(n) = 100 X 112 =11200. Bob chọn ngẫu nhiên một số b và kiểm tra điều kiện ƯCLN (ệ(n), b) = 1 bằng thuật toán Euclide. Gia sir Bob chọn b = 3533, khi đó theo thuật toán Euclid mờ rộng: b' 1 = 6597 mod 11200. Bởi vậy, số 1 Ĩ 1 Ũ bí mật đề giải m ã cùa Bob là a —6597. Bob sẽ công bổ n = 11413 và b = 3533 trong một danh bạ khoá công khai. Bây giờ, giả sử Alice muốn gửi bản rõ X= 9726 tới Bob. Cô ta sẽ tính: 9726 3533 mod 11413 = 5761 rồi gửi bản mã 5761 trên kênh. Khi Bob nhận được bản mã 5761, anh ta sứ dụng số IĨ1Ũbí mật a đê tính ra x: 57616597mod 11413 = 9726. 1.1.3 Đô• an toàn của hê• RSA Độ an toàn cúa hệ RSA được dựa trên eiá thiết là hàm mã Ck(x) = xb mod n là hàm một chiều. Bởi vậy thám mã sẽ khôna, có khả năng về mặt tính toán đ ể giải m ã đ ư ợ c m ột bản mã. Cửa sập cho phép Bob giải m ã được chính là thông tin về phép phân tích thừa sổ n (n=p.q). Vì Bob biết phân tích này, anh ta có thế tính ệ(n) = (p-l).(q-l) và rồi tính số mũ giải mã a bằng cách sử dụng thuật toán Euclide mở rộng. Trang 13 Cách tấn công dề thấy nhất đối với hệ mật này là thám mã cô găng phân tích n ra các thừa số nguyên tố. Nếu thực hiện được phép phân tích này thì có thể dễ dàng tính được ệ(n) = (p-1 ).(q-l) rồi tính số mủ a từ b đúng như Bob làm. Vì thế để hệ RSA được coi là an toàn thì nhất thiết n = p.q phái là một số du lớn để việc phân tích nó sẽ không có kha năng về mặt tính toán. Các thuật toán phân tích hiện thời có khả nâng phân tích các số tới 130 chữ số thập phân. Vì vậy đế đảm báo an toàn nên chọn các số p và q có khoảng 100 chừ số, khi đó n sẽ có tới 200 chữ số. Ngoài ra các số p, q cần phải thoá mãn một sô yêu câu cụ thể nừa. 1.2. HỆ MẬT MÃ ELGAMA í .2.1 Mô tả hệ mật Elgamal Hệ mật Elgamal[5] được đề xuất từ năm 1985, dựa trên bài toán logarit rời rạc là bài toán được dùng nhiều trong nhiều thù tục mật mã. Chúng ta sẽ bắt điầi bằng việc mô tả bài toán này khi thiết lập một trường hữu hạn Zp, p là số ngu/ên tố. 3ài toán logarit rời rạc trong Zp: ỈĐic trưng của bài toán: I =(p, a, P) trong đó p là số nguyên tố, (Oie Zp là phần tử nguyên thuỷ, [3 e Zp\ ĩVục tiêu: Hãy tìm một số nguyên duy nhất a, 0 < a < p-2 sao cho a “ == 3 (m o d p) TT - Xem thêm -