Luận văn Thạc sĩ An toàn thông tin: Nghiên cứu họ hệ mật WG trong mật mã hạng nhẹ

Chia sẻ: Yi Yi | Ngày: | Loại File: PDF | Số trang:57

Thêm vào BST

Báo xấu

45
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn đề cập đến việc nghiên cứu chuyên sâu họ hệ mật WG trong mật mã hạng nhẹ, đánh giá các tấn công đối với các phiên bản gần đây và phát triển ứng dụng vào các thẻ RFID. Phần lý thuyết trình bày các kiến thức liên quan về họ hệ mật WG, mật mã dòng WG-16 và WG-8. Phần thực nghiệm sử dụng cơ sở lý thuyết ở trên cài đặt mật mã WG-5 vào thẻ RFID nhằm đảm bảo an ninh trong thẻ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ An toàn thông tin: Nghiên cứu họ hệ mật WG trong mật mã hạng nhẹ

LỜI CẢM ƠN Lời đầu tiên tôi xin gửi lời cảm ơn sâu sắc nhất đến thầy TS. Hồ Văn Canh, đã tận tâm, tận lực hướng dẫn, định hướng cho tôi, đồng thời, cũng đã cung cấp nhiều tài liệu và tạo điều kiện thuận lợi trong suốt quá trình học tập và nghiên cứu để tôi có thể hoàn thành luận văn này. Tôi xin chân thành cảm ơn đến các thầy, cô trong Bộ môn Quản lý hệ thống thông tin và Khoa Công nghệ thông tin, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội cùng với ban lãnh đạo nhà trường đã nhiệt tình giảng dạy và truyền đạt những kiến thức, kinh nghiệm qúy giá trong suốt quá trình học tập rèn luyện tại trường. Tôi xin gửi lời cảm ơn đến các bạn học viên lớp K22-QLHTTT, nhóm bảo mật UET đã đồng hành cùng tôi trong suốt quá trình học tập. Cảm ơn gia đình, bạn bè đã quan tâm và động viên giúp tôi có nghị lực phấn đấu để hoàn thành tốt luận văn này. Do kiến thức và thời gian có hạn nên luận văn sẽ không tránh khỏi những thiếu sót nhất định. Tôi rất mong nhận được những sự góp ý quý báu của thầy cô, đồng nghiệp và bạn bè. Một lần nữa xin gửi lời cảm ơn chân thành và sâu sắc. Hà Nội, 27 tháng 12 năm 2017 Học viên thực hiện Nguyễn Thị Thuỳ Dung 1
LỜI CAM ĐOAN Tôi xin cam các kết quả đạt được trong luận văn “Nghiên cứu họ hệ mật WG trong mật mã hạng nhẹ” do tôi thực hiện dưới sự hướng dẫn của TS. Hồ Văn Canh. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của cá nhân tôi hoặc là trích dẫn các nguồn tài liệu và một số trang web đều được đưa ra ở phần Tài liệu tham khảo. Tôi xin cam đoan những lời trên là sự thật và chịu mọi trách nhiệm trước thầy cô và hội đồng bảo vệ luận văn thạc sĩ. Hà Nội, 27 tháng 12 năm 2017 Nguyễn Thị Thùy Dung 2
MỤC LỤC LỜI CẢM ƠN.............................................................................................................................................. 1 LỜI CAM ĐOAN ........................................................................................................................................ 2 MỤC LỤC.................................................................................................................................................... 3 DANH MỤC HÌNH VẼ .............................................................................................................................. 5 DANH MỤC BẢNG.................................................................................................................................... 6 DANH SÁCH CÁC TỪ VIẾT TẮT .......................................................................................................... 7 MỞ ĐẦU ...................................................................................................................................................... 9 CHƯƠNG 1 TỔNG QUAN VỀ HỌ HỆ MẬT WG ............................................................................... 11 1.1 Lịch sử mật mã dòng WG [2], [7] ..................................................................................................... 11 1.2 Cơ sở toán học [6] ............................................................................................................................. 12 1.2.1 Mô đun số học ............................................................................................................................ 12 1.2.2 Nhóm và trường ......................................................................................................................... 12 1.2.3 Trường hữu hạn.......................................................................................................................... 14 1.2.4 Lựa chọn cơ sở ........................................................................................................................... 16 1.2.5 Thanh ghi dịch phản hồi tuyến tính LFSR [6] ........................................................................... 17 1.3 Họ hệ mật WG [3],[5] ....................................................................................................................... 22 1.3.1 Cơ sở .......................................................................................................................................... 22 1.3.2 Nguyên tắc hoạt động của họ hệ mật WG.................................................................................. 23 1.3.3 Khởi tạo khóa và hoạt động của mật mã .................................................................................... 27 1.4 Phân tích họ hệ mật WG [3],[9] ........................................................................................................ 30 1.4.1 Các thuộc tính ngẫu nhiên của dòng khóa ................................................................................. 30 1.4.2 Chuyển đổi WG ......................................................................................................................... 31 1.4.3 An ninh chống lại các cuộc tấn công ......................................................................................... 31 1.5 Công nghệ RFID và họ hệ mật WG [6], [8]...................................................................................... 34 CHƯƠNG 2 CÁC HỆ MẬT WG-8 VÀ WG-16 ..................................................................................... 37 2.1 Tổng quan hệ mật WG-8 [8] ............................................................................................................. 37 2.1.1 Giới thiệu WG-8 ........................................................................................................................ 37 2.1.2 Thuật ngữ và ký hiệu ................................................................................................................. 37 2.1.3 Đặc tả cấu trúc mật mã dòng WG-8 ........................................................................................... 38 3
2.1.4 Đánh giá các tấn công mật mã dòng WG-8 ............................................................................... 40 2.2 Hệ mật WG-16 [1] ............................................................................................................................ 43 2.2.1 Giới thiệu WG-16 ...................................................................................................................... 43 2.1.2 Thuật ngữ và ký hiệu ................................................................................................................. 44 2.1.3 Đặc tả cấu trúc mật mã dòng WG-16 ......................................................................................... 45 2.1.4 Đánh giá các tấn công mật mã dòng WG-16 ............................................................................. 47 CHƯƠNG 3 ĐỀ XUẤT CẢI TIẾN HỆ MẬT WG – UET VÀ CHƯƠNG TRÌNH DEMO............... 50 3.1 Đề xuất cải tiến hệ mật WG-UET ..................................................................................................... 50 3.2 Bài toán và cài đặt chương trình ....................................................................................................... 53 KẾT LUẬN ................................................................................................................................................ 55 HƯỚNG NGHIÊN CỨU TIẾP THEO ................................................................................................... 56 TÀI LIỆU THAM KHẢO ........................................................................................................................ 57 4
DANH MỤC HÌNH VẼ Hình 1.1 Sơ đồ khối của LFSR ................................................................................................................... 17 Hình 1.2 LFSR 3 trạng thái ......................................................................................................................... 18 Hình 1.3 LFSR 4 trạng thái ......................................................................................................................... 19 Hình 1.4 Mạch LFSR 3 bít .......................................................................................................................... 20 Hình 1.5 Đa thức đặc trưng cài đặt LFSR................................................................................................... 20 Hình 1.6 Đa ứng dụng cài đặt LFSR........................................................................................................... 21 Hình 1.7 Cài đặt phép chia LFSR ............................................................................................................... 21 Hình 1.8 Sơ đồ mô tả mật mã WG .............................................................................................................. 23 Hình 1.9 Sơ đồ khối của chuyển đổi WG ................................................................................................... 24 Hình 1.10 Sơ đồ khối cài đặt chuyển đổi WG ........................................................................................... 25 Hình 1.11 Pha khởi tạo khóa của mật mã WG ............................................................................................ 28 Hình 1.12 Hệ thống RFID ........................................................................................................................... 35 Hình 2.1 Pha thực thi của mật mã WG-8 .................................................................................................... 40 Hình 2.2 Pha khởi tạo của mật mã dòng WG-16 ........................................................................................ 45 Hình 2.3 Pha thực thi của mật mã WG-16 .................................................................................................. 47 Hình 3.1 Sơ đồ giao thức xác thực lẫn nhau của RFID sử dụng WG-5 ...................................................... 53 5
DANH MỤC BẢNG Bảng 1.1 Bảng các tiên đề định nghĩa nhóm.............................................................................................. 13 Bảng 1.2 Bảng các tiên đề định nghĩa trường ............................................................................................ 13 Bảng 1.3 Bảng dải tần RFID ...................................................................................................................... 34 Bảng 3.1 Bảng biểu diễn vi phân trong 22 bước........................................................................................ 51 Bảng 3.2 Bảng tấn công WG với các cặp khoá/IV có kích thước lớn hơn 80 bít ...................................... 52 6
DANH SÁCH CÁC TỪ VIẾT TẮT TT TỪ VIẾT TIẾNG ANH THUẬT NGỮ MẬT MÃ TẮT 1 WG Welch Gong Thuật toán Welch Gong Linear Feedback Shift Register Thanh ghi dịch chuyển hồi 2 LFSR quy tuyến tính Time memory data Tấn công về các mặt thời 3 TMD gian, bộ nhớ, dữ liệu Maximum Likelihood Thuật toán giải mã Maximum 4 ML Likelihood 5 RF Radio Frequency Tần số vô tuyến Universal Mobile Hệ thống viễn thông di động 6 UMTS Telecommunications System toàn cầu Long Term Evolution Công nghệ Long Term 7 LTE Evolution 8 WGP Welch Gong Permutation Mô đun hoán vị Welch Gong Wech Gong Tranformation Mô đun chuyển đổi Welch 9 WGT Gong Maximum Likelihood Decoding Giải thuật Maximum 10 MLD Likelihood Decoding Radio Frequency Identification Công nghệ nhận dạng đối 11 RFID tượng bằng sóng vô tuyến Organization for Standardization Tiêu chuẩn Organization for 12 ISO Standardization International Electro-technical Tiêu chuẩn International 13 IEC Commission Electro-technical Commission 14 EPC Electronic Product Code Mã sản phẩm điện tử 15 DSS Digital Signature Standard Chuẩn chữ ký số 16 AES Advanced Encryption Standard Chuản mã hoá nâng cao Automated Identification and Công nghệ nhận dạng tự động 17 AIDC Data Capture không dây 18 PB Polynomial basis Cơ sở đa thức 19 NB Normal basis Cơ sở thông thường 20 LS Linear span Khoảng tuyến tính 7
21 AI Algebraic immunity Khả năng miễn dịch đại số Discrete Fourier Transform Tấn công Chuyển đổi Fourier 22 DFT rời rạc 23 LF Low frequency Tần số thấp 24 HF High frequency Tần số cao 25 UHF Ultra-high frequency Tần số cực cao 26 SHF Super-high frequency Tần số siêu cao 8
MỞ ĐẦU Ngày nay, hội nhập kinh tế sâu rộng đã mang đến cho đất nước Việt Nam cơ hội tiếp cận với những xu hướng hiện đại của thế giới. Con người dần chuyển sang sử dụng các dịch vụ thông minh hơn, tiện lợi hơn để đáp ứng các nhu cầu cuộc sống một cách hiện đại nhất, tối ưu nhất. Công nghệ RFID được hiểu là công nghệ nhận dạng tần số sóng vô tuyến. Công nghệ này được sử dụng ngày càng phổ biến với nhiều ứng dụng trong cuộc sống hàng ngày từ kiểm soát hàng hóa, quản lý và chấm công nhân trong các siêu thị, nhận dạng và kiểm soát tại những bãi gửi xe thông minh, các công ty bảo mật hàng đầu cũng đang sử dụng. Công nghệ này cho phép nhận biết các đối tượng thông qua hệ thống thu phát tần số sóng vô tuyến, từ đó con người có thể giám sát, quản lý hoặc lưu vết từng đối tượng. Đây là một phương pháp nhận dạng tự động dựa trên việc lưu trữ dữ liệu từ xa, sử dụng thiết bị thẻ RFID và một đầu đọc RFID. Khoảng cách “không tiếp xúc” để tần số sóng vô tuyến tiếp nhận dữ liệu có thể lên tới hơn 10m. Ngoài ra sự ưu việt của công nghệ này còn thể hiện ở khả năng đọc được thông tin xuyên qua các môi trường, vật liệu như: bê tông, tuyết, sương mù, băng đá, sơn và các điều kiện môi trường thách thức khác mà mã vạch và các công nghệ khác không thể phát huy hiệu quả. Công nghệ RFID được sử dụng rộng rãi trong nhiều ứng dụng nhưng mối quan tâm chính trong công nghệ RFID là bảo mật và riêng tư. Do sự giao tiếp giữa thẻ và đầu đọc diễn ra thông qua không dây, nghĩa là thông tin trao đổi giữa chúng diễn ra trên một kênh không an toàn. Nói chung, các kênh truyền thông không an toàn dễ bị phá bởi các loại tấn công khác nhau. Do đó, khi một người hoặc một đối tượng sở hữu thẻ cần phải được đảm bảo được sự riêng tư và an ninh dữ liệu trên thẻ. Để khắc phục những mối đe dọa này trong các thẻ RFID, một trong những giải pháp là triển khai các giải pháp mật mã trong các thẻ RFID. Vì cả hai vấn đề bảo mật và riêng tư trong các hệ thống RFID cần phải được giải quyết bằng các giải pháp mật mã. Đó là một nhiệm vụ đầy thách thức chủ yếu là do môi trường hạn chế về mặt tài nguyên và truyền thông, dẫn đến chi phí cao hơn. Do những yếu tố này, việc thiết kế các giải pháp mật mã trong các hệ thống RFID không phải là một nhiệm vụ dễ dàng. Do đó, việc thiết kế các thuật toán mật mã và các giao thức đã được đề xuất là mật mã học hạng nhẹ. Để tính đến các yêu cầu nghiêm ngặt của các thẻ RFID như khu vực, năng lượng và chi phí, việc thiết kế các hệ thống mã đối xứng và bất đối xứng hạng nhẹ cần phải nằm trong phạm vi hạn chế của RFID. Lợi thế của khoá đối xứng đối với hệ bất đối xứng là nó có tính toán toán học giới hạn. Cho phép thiết kế phần cứng của hệ thống khóa đối xứng hiệu quả về mặt diện tích và điện năng để thực hiện chúng trên bất kỳ nền tảng phần cứng nào. Các nghiên cứu gần đây cho thấy các mật mã dòng yêu cầu ít tài nguyên tính toán về diện tích, năng lượng và hiệu năng so với mật mã khối và các hàm 9
băm. Trong khi đó, các hệ thống khoá bất đối xứng hay khóa công khai có các phép tính số học có độ phức tạp trên các trường hữu hạn lớn hơn. Các phép toán này liên quan đến hàng trăm bit do đó cần một lượng lớn kích thước bộ nhớ để lưu trữ chúng. Do đó, không tận dụng thiết kế và điện năng tốn nhiều hơn so với các hệ mã hóa đối xứng. Vì vậy, các hệ mật khóa công khai không được ưa chuộng để sử dụng trong các hệ thống RFID trong những năm qua. Họ hệ mật WG được đánh giá là hệ mật có độ bảo mật an toàn cao và hiệu quả hơn nhiều so với hệ mật mã hạng nhẹ khác. Trong phạm vi luận văn này, tôi đặt ra vấn đề nghiên cứu ứng dụng mật mã dòng WG vào thẻ RFID nhằm đảm bảo an ninh cho các giao dịch trên các thẻ. Mục đích nghiên cứu: Luận văn đề cập đến việc nghiên cứu chuyên sâu họ hệ mật WG trong mật mã hạng nhẹ, đánh giá các tấn công đối với các phiên bản gần đây và phát triển ứng dụng vào các thẻ RFID. Phần lý thuyết trình bày các kiến thức liên quan về họ hệ mật WG, Mật mã dòng WG-16 và WG-8. Phần thực nghiệm sử dụng cơ sở lý thuyết ở trên cài đặt mật mã WG-5 vào thẻ RFID nhằm đảm bảo an ninh trong thẻ. 2. Nội dung của đề tài, các vấn đề cần giải quyết: a. Hướng nghiên cứu: - Thiết kế thuật toán mã hoá WG và đưa ra các đề xuất phù hợp cài đặt trong môi trường có tài nguyên hạn chế. - Nghiên cứu tấn công họ hệ mật mã WG. - Ứng dụng mật mã dòng WG-5 trong hệ thống RFID. b. Ngoài phần mở đầu, kết luận, nội dung luận văn gồm những chương sau: Chương 1: Tổng quan họ hệ mật WG Chương 2: Các hệ mật WG-16 và WG-8 Chương 3: Đề xuất cải tiến hệ mật WG-UET và chương trình demo. 10
CHƯƠNG 1 TỔNG QUAN VỀ HỌ HỆ MẬT WG 1.1 Lịch sử mật mã dòng WG [2], [7] Phiên bản đầu tiên của mật mã WG được Nawaz and Gong công bố năm 2005, được đệ trình lên dự án eSTREAM với tư cách như một mật mã được định hướng cứng hoá. Mật mã WG bao gồm một LFSR với 11 phần tử trên F2 . Cấu trúc của các phiên bản sau này 29 cũng cũng tương tự như vậy, ngoại trừ việc chuyển đổi WG được kết hợp với phần tử cuối cùng của thanh ghi (ban đầu là S0). Mặc dù kích thước của LFSR là cố định nhưng nó cho phép sử dụng các khóa có kích cỡ khác nhau (80, 69, 112 và 128 bit). Các vector IVs có thể có cùng kích thước như các khóa, nhưng vector IV cũng có thể ngắn hơn 64 hoặc 32 bit. Sự khác biệt duy nhất giữa các kích cỡ này là cách tải các khóa và các vector IV này vào LFSR . Chỉ sau 2 tháng đã có cuộc tấn công thành công vào phiên bản này, Wu và Preneel đã trình bày cuộc tấn công mật mã, cuộc tấn công này tập trung vào việc có thể khôi phục được khóa mà không cần quan tâm đến kích cỡ khóa/IV. Để đáp lại cuộc tấn công này, người tạo ra mật mã WG đã đề xuất ý kiến tăng gấp đôi hoặc thậm chí gấp bốn lần số chu kỳ cho pha khởi tạo. Phiên bản cuối cùng của mật mã WG (nay được gọi là họ hệ mật mã dòng) được công bố năm 2013. Nó chuyển sự chuyển đổi WG về cuối LFSR, chính sự thay đổi này làm cho mật mã có thể chống lại cuộc tấn công IV đã được đề cập ở trên mà không cần tăng thêm chu kỳ cho pha khởi tạo. Mật mã WG cuối cùng cũng bị loại khỏi dự án mã dòng - eSTREAM vào cuối giai đoạn 2, với 2 lý do chính: (1) Về vấn đề an ninh. Trong năm 2007, một cuộc tấn công vào máy sinh bộ lọc chung trên F2 đã được Rønjom và Helleseth trình bày. Cuộc tấn công nhằm khôi phục lại trạng m thái bên trong của mật mã WG. Tuy nhiên, đặc tả mật mã không cho phép có nhiều hơn 245 bít dòng khóa được tạo ra với cùng một cặp khóa/IV. Trong khi đó cuộc tấn công này cần ít nhất 245.0415 bit dòng khóa để cuộc tấn công có thể thành công. Mặc dù mật mã WG an toàn chống lại cuộc tấn công này nhưng nó đã rút khỏi eSTREAM với một nghi ngờ rằng mật mã rất có thể bị phá nếu chỉ một chút sơ xuất. (2) Phía eSTREAM cho rằng độ hiệu quả của mật mã khi cài đặt trong phần cứng chỉ tương đương với một số mật mã khác. Điều này chủ yếu là do WG-128 - phiên bản gốc của WG, có nhiều phép tính trong F2 yêu cầu nhiều không gian khi triển khai trong phần 29 cứng. Tất cả các thành phần của họ hệ mật WG sử dụng nhiều trường hữu hạn nhỏ hơn để giải quyết vấn đề này. 11
Mật mã WG-16: Năm 2013 Fan and Gong trình bày mật mã dòng WG-16. Nó được thiết kế dùng trong mạng 4G-LTE. Hai ông cũng chỉ ra các thuật toán bí mật và toàn vẹn sử dụng mật mã WG-16 của họ. Để chứng minh tính thực tiễn của mật mã WG-16, họ đưa ra các lý lẽ cho rằng các mật mã hiện tại trong chuẩn 4G-LTE rất khó để phân tích và những giải thuật hiện tại cũng dễ bị phá vỡ. WG-16 sử dụng các khóa và bộ mã hoá 128-bit cùng với LFSR có chứa 32 phần tử trên F2 .16 Mật mã WG-7: Mật mã WG-7 là tiền nhiệm của WG-8, cũng được thiết kế nhắm đến các thiết bị bị hạn chế tài nguyên. Nó được công bố bởi Luo et al năm 2010. Nó sử dụng các khóa 80-bit và vector IV 80-bit. LFSR chứa 23 phần tử trên F2 . Tuy nhiên, vào năm 2012 7 mật mã bị phá bởi Orumiehchiha et al. Mật mã WG-5: Aasgaard, Gong và Mota thảo luận về việc triển khai phần cứng và các vấn đề bảo mật của mật mã dòng WG-5. Mật mã này nhằm vào các thẻ RFID thụ động và chỉ cung cấp mức bảo mật thấp. Nó chỉ chống lại các cuộc tấn công chỉ khi dữ liệu được mã hóa với một cặp khóa/ IV không vượt quá 256 kilobyte, đây là một ràng buộc chấp nhận được đối với các thẻ RFID thụ động. 1.2 Cơ sở toán học [6] 1.2.1 Mô đun số học Modul số học đã và đang dần trở lên quan trọng trong lĩnh vực mật mã. Lý thuyết mô đun số học được sử dụng trong các thuật toán mã hoá khoá công khai như thuật toán RSA và Diffie-Hellman, các thuật toán khoá đối xứng như AES, IDEA và RC4. Ưu điểm chính của việc sử dụng mô đun số học là nó cho phép chúng ta thực hiện phép nhân nhanh hơn. Ví dụ với phép toán phức tạp, việc tính toán đa thức đó (nhân đa thức) với 1 lượng số nguyên lớn thì việc sử dụng mô đun số học sẽ làm giảm thời gian tính toán của các phép toán lớn này. Áp dụng vào ứng dụng sửa mã lỗi, bằng việc sử dụng lý thuyết mô đun số học mỗi chữ số của mã được liên kết đến các phần tử của trường hữu hạn. Toán tử modulo (mod n) ánh xạ tới tất cả các số nguyên trong tập {0, 1, 2, ... (n − 1)} và tất cả các phép toán số học được thực thi trong tập hợp này. Kỹ thuật này được gọi là mô đun số học. Tập các số nguyên và các số nguyên khác 0 của mod n được ký hiệu bởi Zn và Z*n. Ví dụ: cộng và nhân modul trên modulo 23 Giả sử, 12 + 20 = (12 + 20) mod 23 = 32 mod 23 = 9 vì 32 chia cho 23 dư 9. Tương tự, trong phép nhân; 8 × 9 = 72 mod 23 = 3, vì khi 72 chia cho 23 dư 3. 1.2.2 Nhóm và trường Trong đại số trừu tượng, chúng ta làm việc với các tập mà các phần tử được thao tác một cách đại số. Ví dụ, chúng ta có thể nói rằng bằng cách kết hợp hai phần tử của một tập theo nhiều cách khác nhau, ta có thể tạo ra được phần tử thứ ba của tập 12
hợp. Tất cả các phép toán sẽ tuân theo một số quy tắc cụ thể được định nghĩa trong tập. Một số định nghĩa: Nhóm: Định nghĩa 1: Một Nhóm (G) được định nghĩa như là 1 cặp (S, •), với S là tập khác rỗng, toán tử • sao cho tuân theo tiên đề từ A1-A4 được định nghĩa ở bảng bên dưới. Toán tử • có thể gọi là phép cộng, phép nhân hay 1 phép toán nào khác. Ở đây tập S là đại diện của nhóm G, i là phần tử định danh trong G. Tiên đề Ý nghĩa A1. Đóng kín Cho a, b thuộc G , a • b sẽ thuộc G A2. Kết hợp Cho tất cả a, b, c thuộc G, a •(b •c) = (a •b) •c A3. Định danh Tồn tại phần tử e thuộc G, cho a thuộc G với a •e = e •a = a hay đúng hơn ∃e ∈ G, ∀ a ∈ G, a • e = e • a = a A4. Nghịch đảo Với mọi a thuộc G tồn tại phần tử x thuộc G sao cho a•x = x•a = e hay nói cách khác ∀a ∈ G, ∃x ∈ G, a•x = x•a=e Bảng 1.0.1 Bảng các tiên đề định nghĩa nhóm Định nghĩa 2: (A5) Một nhóm được gọi là nhóm abel nếu nó thoả mãn điều kiện với mọi a, b thuộc G thì a •b = b •a Định nghĩa 3: Một nhóm được gọi là cyclic nếu có 1 hoặc nhiều phần tử mà có thể sinh ra tất cả các phần tử trong nhóm, hay có nói cách khác: ∃ g ∈ G, ∀ a ∈ G, ∃ k, a = gk. Ví dụ: p là số nguyên tố và ( * p , ) là nhóm cyclic. Nhóm cyclic ( * 7 , ) , với p = 7, số phần tử của nhóm là 6. Ta có, phần tử 3 và 5 là phần tử sinh của nhóm * 7  {1,2,3,4,5,6} , các luỹ thừa của 3 modulo 7 là: 1 = 36 , 2 = 32 , 3 = 3 1 , 4 = 3 4 , 5 = 35 , 6 = 3 3 Trường: Định nghĩa: Một trường F được định nghĩa là một tập các phần tử với 2 toán tử nhị phân ,  , được biểu diễn là ( F , , ) và tuân theo các tiên đề bên dưới: Tiên đề Ý nghĩa (A1-A5) F tạo thành 1 nhóm abel đối với phép cộng (A1-A3) và A5 F tạo thành một vị nhóm giao hoán A6. Phần tử Cho mỗi a thuộc F, nếu a  0 , tồn tại một phần tử x thuộc F, nghịch đảo sao cho a  x  x  a  1 , hay có thể nói ∀ a  0 ∈ F, ∃ x ∈ F, a x  xa 1 Bảng 1.0.2 Bảng các tiên đề định nghĩa trường 13
Ví dụ: Cho trường bất kỳ ( F , , ).( F * , ) tạo thành 1 nhóm abel. Với F * là tập con của F không bao gồm phần tử 0. 1.2.3 Trường hữu hạn Trường hữu hạn đóng một vai trò quan trọng trong lĩnh vực mật mã. Hầu hết các thuật toán mã hoá khoá công khai như DSS, mật mã khóa El Gamal, mật mã trên đường cong Elliptic phụ thuộc rất nhiều vào các thuộc tính của trường hữu hạn, ngoài ra nó cũng được sử dụng trong mật mã AES. Số phần tử của trường hữu hạn phải là một luỹ thừa của một số nguyên tố: pn, trong đó n là một số nguyên dương. Ở đây xuất hiện hai trường hợp: (1) Với n = 1, trường hữu hạn có dạng GF(p) trong đó GF là viết tắt của trường Galois. (2) Với n > 1, trường hữu hạn có dạng GF(pn). Trường hữu hạn GF(p) có cấu trúc khác so với trường hữu hạn GF(pn). Các loại trường hữu hạn: - Trường nguyên tố: Được định nghĩa là trường có dạng GF(p), với p là số nguyên tố. Tất cả các phần tử trong trường và các phép toán số học (, ) được thực thi theo modulo p. - Trường nhị phân: Được định nghĩa là một trường có dạng GF(pn), trong đó n là một số nguyên dương. Thông thường trường nhị phân được xây dựng từ trường nguyên tố. 1.2.3.1 Trường hữu hạn của GF(p) Cho số nguyên tố p bất kỳ, trường hữu hạn p phần tử, các phần tử của GF(p) được định nghĩa là tập {0, 1, 2, ... (p-1)}, cùng với các phép toán số học theo modulo p. GF(p) cũng có thể được ký hiệu bởi tập các số nguyên Zp. Ví dụ: Các phép toán số học trong trường hữu hạn đơn giản nhất của GF(p) Trường hữu hạn đơn giản nhất là GF(2), trong đó p = 2, và các phần tử là {0, 1}, đây là trường hợp đặc biệt mà các phép toán số học + và  tương đương với các phép toán XOR và AND. 1.2.3.2 Đa thức số học Các phần tử của GF(pn), với n > 1, có thể được biểu diễn dưới dạng đa thức, các hệ số của đa thức này thuộc GF(p) và có độ nên nhỏ hơn n. Khi p = 2, các phần tử của GF(pn) được biểu diễn dưới dạng số nhị phân {0, 1}. Điều này có nghĩa là mỗi ký tự trong một đa thức được biểu diễn bởi một bit trong biểu thức nhị phân tương ứng. Định nghĩa: Một đa thức được định nghĩa là một biểu thức toán học liên quan đến tổng của 1 hoặc nhiều biến nhân với các hằng số của chúng. Một đa thức với 1 biến và các hằng số của chúng được biểu diễn như sau: 14
n f(x) = anxn + an−1xn−1 + ..... + a2x2 + a1x + a0 = a xi 0 i i Với n (là số nguyên n ≥ 0) được gọi là độ của đa thức, và hằng số ai , 0 ≤ i ≤ n. F cũng được gọi là một tập hợp khi an  0 và có thể có nhiều đa thức được định nghĩa trên F. Có thể có nhiều luỹ thừa giống nhau của x khi so sánh 2 đa thức f ( x) và g ( x) trên F. n m Cho: f ( x)   ai xi và g ( x)   bi xi i 0 i 0 Phép cộng f ( x) và g ( x) : n f ( x)  g ( x)   (ai  bi ) xi , với n = m i 0 Phép nhân f ( x) và g ( x) :  n   m  nm f ( x)  g ( x)    ai xi     bi xi    ck x k  i 0   i 0  k 0 Với: ck   aibk i  a0bk  a1bk 1  ...  ak 1b1  ak b0. 0 i  k Phép chia m( x) và p( x) : Phép chia đa thức trên trường Galois được tính toán dựa trên phép nhân và phép cộng. Phép chia 2 đa thức m( x)  p( x) được tính bằng phép toán m( x)  q( x)  p( x)  r ( x) , với thương q( x) và số dư r ( x) là kết quả của phép chia. 1.2.3.3 Trường hữu hạn của GF(pn) Trường hữu hạn dưới dạng GF(p) với p phần tử, trong đó p là số nguyên tố. Các thành phần của GF(p) = Zp = {0, 1, 2, ... (p-1)}, với các phép toán số học (, ) được thực hiện cùng với phép toán modulo p. Chúng ta sử dụng khái niệm tương tự để xây dựng trường hữu hạn có dạng GF(pn), gồm q-1 phần tử, trong đó (q = pn) với phép toán mô đun pn-1. Một đa thức i( x) được gọi là một đa thức không giảm trên trường F, khi và chỉ khi i( x) không thể biến đổi thành 2 hoặc nhiều đa thức trên trường F. Một đa thức không giảm cũng được gọi là một đa thức nguyên tố. Một phần tử nguyên thủy của GF(pn) là phần tử mà nó là 1 phần tử sinh của nhóm cyclic GF(pn)*. Một đa thức không giảm trên GF(p) có 0 là phần tử nguyên thủy trên GF(pn) được gọi là đa thức nguyên thủy trên GF(p). Như vậy tất cả đa thức không giảm đều là đa thức nguyên thủy. Gốc của đa thức: Nếu p(x) là 1 đa thức trên F, thì phần tử α ∈ F sao cho p(α) = 0 được gọi là gốc của đa thức p(x). 15
Trường con: Nếu một tập con S có các phần tử thuộc trường F thỏa mãn các tiên đề trường cùng với các phép toán số học của F, thì S được gọi là trường con của F. GF(pm) là một trường con của GF(pn) khi và chỉ khi m là số chia hết của n ký hiệu là: GF(pm) ⊂ GF(pn). Ví dụ: GF(22) ⊂ GF(24) và GF(24) ⊂ GF(212). Trường mở rộng: Một trường F được gọi là trường mở rộng, nếu S là tập con nằm trong tập F, ta định nghĩa S là một trường con của F và F là một trường mở rộng của S. Chúng được ký hiệu F/S và đọc là "F trên S". Hàm lưu vết Giả sử, F = GF(pn) và K = GF(p), thì hàm lưu vết TrF/K (x) được định nghĩa như sau: n 1  xp , xF n1 i 1 Tr ( x)  TrF / K ( x)  x  x p  ...  x p i 0 Hàm lưu vết Tr(x), GF(p ) → GF(p). n Ví dụ: Cho trường hữu hạn GF(23) được định nghĩa bởi  3    1 . Tìm hàm lưu vết Tr ( ) và Tr ( 3 ) Từ hàm lưu vết Tr ( x) , với p = 2 và n = 3. Ta có, Tr ( )     2   4     2     2  0 . Tương tự ta có: Tr ( 3 )   3   6   5  (1   )  (1   2 )  (1     2 )  1 . 1.2.4 Lựa chọn cơ sở *Cơ sở đa thức Định nghĩa: Xét trường hữu hạn GF(pn) và cho α ∈ GF(pn) là gốc của một đa thức không giảm, độ n trên GF(p). Cơ sở đa thức đươc được biểu diễn là {1, α, α2 ... αn-1} của GF(pn) trên GF(p). Với α là phần tử nguyên thủy của GF(pn) Ví dụ: Nếu p = 3 và n = 2 thì GF(32) là một trường mở rộng của GF(3) với độ bằng 2. Cho α ∈ GF(32), là gốc của đa thức không giảm x2 + 1 trên GF (3), thì cơ sở đa thức là {1, α} của GF(32) trên GF(3). *Cơ sở thông thường Định nghĩa: Cho số nguyên dương n bất kỳ trên GF(pn), luôn luôn có một cơ sở thông thường cho trường hữu hạn GF(pn) trên GF(p). Nếu γ ∈ GF(pn) là một phần  tử thông thường, thì cơ sở thông thường được biểu diễn là  ,  2 ,  2 ... 2 1 2 n1 . Trong đó γ được gọi là phần tử sinh hoặc phần tử thông thường của GF(pn) trên GF(p), được biểu diễn dưới dạng ma trận n  m và được ký hiệu là M. 16
Ví dụ: Nếu p = 2 và n = 3, thì GF(23) là một trường mở rộng của GF(2) với độ bằng 3. Cho α ∈ GF(23), là gốc của đa thức không giảm x3 + x2 + 1 trên GF(2), thì cơ sở thông thường là {α, α2, 1 + α + α2} của GF(23) trên GF(2). Lựa chọn cơ sở cho việc cài đặt phần cứng: Trường hữu hạn đóng 1 vai trò quan trọng trong mật mã đặc biệt là trong các hệ thống mật mã đối xứng và bất đối xứng mà có các phép toán số học hữu hạn trường. Các phép toán số học thông thường trên GF(2n) được thực hiện theo modulo của đa thức không giảm f (x) trên GF (2). Các phép cộng và trừ số học được thực hiện theo modulo 2. Phép cộng 2 đa thức thì không có gì nhưng phép toán XOR của biểu diễn nhị phân trong phép toán nhân thì độ phức tạp tốn nhiều thời gian trên trường GF(2n). Độ phức tạp còn phụ thuộc vào việc lựa chọn đa thức không giảm và cơ sở được sử dụng để biểu diễn các phần tử hữu hạn. Cơ sở đa thức được xem là để tối ưu hóa phần cứng vì trong cơ sở đa thức phép nhân có thể được thực hiện đơn giản bằng phép toán dịch và phép toán XOR. Trong thực thi phần cứng lựa chọn cơ sở thông thường thì phép bình phương 1 phần tử đơn giản chỉ dịch chuyển đúng 1 vòng tròn của tọa độ. Do vậy, phép bình phương trong cơ sở thông thường rất dễ thực hiện nhưng phép nhân trong cơ sở thông thường thì lại phức tạp. 1.2.5 Thanh ghi dịch phản hồi tuyến tính LFSR [6] 1.2.5.1 LFSR và mô tả toán học Thanh ghi dịch phản hồi tuyến tính (LFSR) đã được sử dụng rộng rãi trong máy sinh dòng khóa của mật mã dòng, máy sinh số ngẫu nhiên trong hầu hết các thuật toán mã hoá. Mỗi khối vuông trong hình 1.1, là một đơn vị lưu trữ 2 trạng thái (0 hoặc 1). Các đơn vị lưu trữ nhị phân n được gọi là các trạng thái của thanh ghi dịch và nội dung của chúng ở dạng n bit chiều dài, được gọi là trạng thái nội bộ của thanh ghi dịch. Hình 1.1 Sơ đồ khối của LFSR Cho (a0, a1, a2, ..., an-1) ∈ GF (2n) là trạng thái ban đầu của LFSR và 17
f (x0, x1, x2, ..., xn-1) là hàm phản hồi hoặc đa thức thông tin phản hồi, như thể hiện trong hình 1.1. Nếu hàm phản hồi là một hàm tuyến tính thì nó có thể được biểu diễn bằng: f(x0, x1, x2, ..., xn−1) = c0x0 + c1x1 + c2x2 + ...... + cn−1xn−1, ci ∈ GF(2) Sau mỗi chu kỳ liên tiếp cộng với LFSR sẽ tạo ra một chuỗi nhị phân đầu ra là chuỗi nhị phân b có dạng b = a0, a1, ... Chuỗi đầu ra của LFSR thỏa mãn quan hệ đệ quy sau: n 1 ak  n   ci ak i , k  0,1,... (1) i 0 Đầu ra của LFSR được coi là một chuỗi đệ quy tuyến tính. Nếu hàm phản hồi là tuyến tính thì chuỗi đầu ra được gọi là chuỗi LFSR tuyến tính. Nếu không, nó được gọi là chuỗi phi tuyến tính (NLFSR). Lưu ý: Để b là chuỗi nhị phân. Phương trình hồi quy tuyến tính (1) được biểu diễn trong đa thức f (x) = xn + cn-1xn-1 + ... + c1x + c0, được xem là đa thức đặc trưng của LFSR. Ví dụ 1: Xét một LFSR 3 trạng thái như thể hiện trong hình 1.2 với hàm phản hồi tuyến tính f (x0, x1, x2) = x0 + x1 với trạng thái ban đầu là (1, 0, 0) tương đương với (a0, a1, a2). Dãy đầu ra sẽ là 10010111001011 ..... được lặp lại tuần hoàn với chu kỳ là 7. Hình 1.2 LFSR 3 trạng thái 1.2.5.2 Các loại chuỗi - Chuỗi nhị phân: b = bi, bi ∈ GF(2), là một dãy nhị phân trên GF(2). - Chuỗi - m: Chuỗi đầu ra được tạo ra bởi một LFSR n trạng thái với các giá trị ban đầu khác không và có chu kỳ cực đại là 2n - 1 được xem là chuỗi có chiều dài lớn nhất và được gọi tắt là chuỗi-m. 18
- Chuỗi De-Bruijn: Chuỗi De-Bruijn là đầu ra của một NLFSR n trạng thái. Từ chuỗi m bất kỳ với chu kỳ là 2n - 1, ta có thể tính được chuỗi de-Bruijin bằng cách chèn một bít 0 vào chuỗi m. Ví dụ 2: Xét một LFSR 4 trạng thái như trong hình 1.3 với đa thức f(x) = x4 + x + 1 và với trạng thái ban đầu là (0, 0, 0, 1) tương đương với (a0, a1, a2, a3, a4). Đầu ra là một chuỗi-m là 000100110101111000100 ..... được lặp lại định kỳ với một chu kỳ là 15. Hình 1.3 LFSR 4 trạng thái Thuộc tính của LFSR: Xét độ an toàn của máy sinh dòng khóa dựa trên LFSR khi thiết kế LFSR cần chú ý các thuộc tính sau: 1. Chu kỳ lớn. 2. Độ phức tạp tuyến tính lớn. 3. Đặc tính thống kê tốt. Nếu b là một chuỗi nhị phân, thì độ phức tạp tuyến tính của b là độ dài ngắn nhất của LFSR mà tạo ra b. Được ký hiệu là LS (b). Cho chuỗi b bất kỳ có độ dài N, ta có thể tính toán khoảng tuyến tính của dãy sử dụng thuật toán Berlekamp-Massey. 1.2.5.3 Cài đặt phần cứng LFSR trên trường Galios Trong việc cài đặt phần cứng, LFSR chứa N thanh ghi được kết nối với nhau để tạo ra một thanh ghi dịch. Nói chung, thanh ghi dịch là một dãy flip-flops, trong đó đầu ra của flip flop cuối cùng được nối (phản hồi) với các flip flops trước đó bằng một cổng XOR như thể hiện trong hình 1.4. Giả sử chiều dài của LFSR là N và nó bao gồm của N trạng thái flip-flops và các bit đã lưu được điều khiển bởi một đồng hồ đơn. Tại mỗi xung đồng hồ, các bit đã lưu sẽ được dịch chuyển 1 vị trí sang trạng thái tiếp theo, đồng nghĩa với việc là có sự chuyển tiếp từ trạng thái này sang trạng thái tiếp theo. 19
Hình 1.4 Mạch LFSR 3 bít Các thông số thiết kế cần quan tâm khi thiết kế LFSR là số flip flops, cổng XOR bên trong hoặc bên ngoài, các taps phản hồi (đầu vào cho XOR) và tín hiệu cài đặt lại. Khi thiết lập cài đặt lại, thanh ghi sẽ cài đặt tất cả 1s và với mục đích phân tích, ở đây ta sử dụng LFSRs với cổng XOR nội bộ vì mạch của chúng được kết hợp với các đa thức trên các trường Galois. LFSR tạo ra một chuỗi bit có độ dài tối đa 2n - 1, trong đó n là kích thước của trường hữu hạn. Các tap phản hồi trên LSFR sẽ được chọn dựa vào đa thức đã được lựa chọn trên trường hữu hạn. Các phép toán số học đa thức được thực thi liên quan tới các phép toán mod 2, tức là các hệ số của đa thức phải là 1 hoặc 0. Những đa thức này được gọi là đa thức đặc trưng hoặc phản hồi. Những đa thức đặc trưng này sẽ biểu diễn các chuỗi bít LFSR. Giả sử chuỗi bit là 110011 thì đa thức đặc trưng được biểu thị là x5 + x4 + x1 + 1. Ví dụ: biểu diễn LFSR cho đa thức đặc trưng x5 + x4 + x1 + 1. Hình 1.5 Đa thức đặc trưng cài đặt LFSR. Từ ví dụ trên, số mũ của đa thức được biểu diễn như sau: x0 là đầu vào của LFSR, x1 là đầu ra của flip flop đầu tiên và x2 là đầu ra thứ hai,….. Hơn nữa, số mũ tối đa của đa thức được thể hiện bằng số flip flops được sử dụng trong LFSR. 20