Nghiên cứu, ứng dụng của hệ mật IEDA vào bảo mật thông tin

MỤC LỤC CHƯƠNG I. NÓI VỀ HỆ MẬT IDEA I. Thuật toán IDEA I.1. Những điểm chính I.1.2. Các phép toán sử dụng trong IDEA I.1.3. Mã hoá và giải mã trong IDEA a. Mã hoá b. Giải mã I.1.4 Quá trình làm việc của một modul CHƯƠNG II. MỘT SỐ ĐOẠN CHƯƠNG TRÌNH VÍ DỤ II.1. Nhân 2 số modulo(216+1) II.2. Tính số nhân đảo của số x modulo 65537 II.3. Tạo 52 khối subkey từ khoá 128 bit II.4. Tính khoá cho quá trình giải mã II.5. Chương trình mã CHƯƠNG III. THIẾT KẾ CHƯƠNG TRÌNH MÃ DỊCH BẰNG HỆ MẬT IDEA III. Mục đích và thiết kế III.1. Mục đích III.2. Cách thực hiện mã hoá và giải mã theo IDEA III.3. Các chức năng của phần mềm III.4. Chương trình mô tả của thuật toán IDEA

doc43 trang | Chia sẻ: lvcdongnoi | Ngày: 04/07/2013 | Lượt xem: 1537 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Nghiên cứu, ứng dụng của hệ mật IEDA vào bảo mật thông tin, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
LỜI NÓI ĐẦU Vấn đề bảo mật thông tin trong các hệ thống thông tin , tin học hoá, đã trở nên hết sức quan trọng , nó quyết định đến sự thành công và tính hữu hiệu của các hệ thống thông tin. Để thực hiện vấn đề này người ta áp dụng rất nhiều các biện pháp khác nhau từ những phương pháp thủ công với các quy tắc , quy ước đến những phương pháp hiện đại có sự trợ giúp của các phương tiện tính toán tiên tiến nhất. Trong mấy năm gần đây, trước sự phát triển của khoa học kỹ thuật đã cho ra đời nhiều thiết bị lưu trữ, thiết bị truyền thông có chất lượng cao, đặc biệt là sự phát triển nhanh như vũ bão của mạng lưới tin học đã và đang mang tính toàn cầu hoá. Với lượng thông tin lớn, dữ liệu tập trung, tốc độ truyền tin cao vì vậy việc bảo mật thông tin đã trở nên khó khăn hơn nhiều. Trước tình hình đó nhiều tổ chức, cá nhân trong và ngoài nước nói chung và ngành cơ yếu Việt Nam nói riêng đã rất quan tâm tới vấn đề này. Nhiều các biện pháp kỹ thuật được áp dụng như chống tiếp cận, sao chép trái phép, bảo vệ thông tin trên đường truyền ..vv. Để góp phần vào việc bảo đảm an toàn thông tin. Mục tiêu nghiên cứu đề tài này của em là : “ Nghiên cứu, ứng dụng của hệ mật IEDA vào bảo mật thông tin”.Đây là thuật toán mới và đang được áp dụng phổ biến trên thế giới trong việc mã hoá dữ liệu, theo đánh giá của các nhà phân tích chuyên môn thì IDEA có khả năng sẽ là một nhân tố tốt trong tương lai về việc mã hoá dữ liệu. Do thời gian làm đồ án có hạn và trình độ chuyên môn chưa nhiều nên không thể tránh được một số thiếu sót. Vì vậy em rất mong nhận được sự góp ý của các thầy và các bạn để đề tài này có thể phát triển và được đưa vào ứng dụng trong thực tế. Cuối cùng em xin chân thành cảm ơn thầy giáo TS : Lều Đức Tân đã tận tình giúp đỡ em hoàn thành đề tài này. Hà Nội ngày .../.../2000. MỤC LỤC CHƯƠNG I. NÓI VỀ HỆ MẬT IDEA Thuật toán IDEA I.1. Những điểm chính I.1.2. Các phép toán sử dụng trong IDEA I.1.3. Mã hoá và giải mã trong IDEA Mã hoá Giải mã I.1.4 Quá trình làm việc của một modul CHƯƠNG II. MỘT SỐ ĐOẠN CHƯƠNG TRÌNH VÍ DỤ II.1. Nhân 2 số modulo(216+1) II.2. Tính số nhân đảo của số x modulo 65537 II.3. Tạo 52 khối subkey từ khoá 128 bit II.4. Tính khoá cho quá trình giải mã II.5. Chương trình mã CHƯƠNG III. THIẾT KẾ CHƯƠNG TRÌNH MÃ DỊCH BẰNG HỆ MẬT IDEA III. Mục đích và thiết kế III.1. Mục đích III.2. Cách thực hiện mã hoá và giải mã theo IDEA III.3. Các chức năng của phần mềm III.4. Chương trình mô tả của thuật toán IDEA CHƯƠNG I. NÓI VỀ HỆ MẬT IDEA I. Thuật toán IDEA Thuật toán IDEA ( International Encryption Algorihm) được mô tả như sau: I.1 . Những điểm chính: IDEA là phương pháp mã khối sử dụng 128 bit khoá để mã khối dữ liệu 64 bit. IDEA được xây dựng nhằm mục đích kết hợp với nhiều yếu tố khác để tăng độ an toàn và khả năng thực hiện. Từ khi mới được công bố thì thuật toàn này đều là đối tượng quan tâm của các nhà phân tích mật mã(mã thám), và không ai có thể đảm bảo được mức độ chắc chắn, sự an toàn của thuật toán này cung cấp và cũng không ai có thể bảo đảm rằng việc tấn công hay đột phá vào thuật toán này là không thể thành công. Một ngày nào đó, cho dù có đột phá được thì người ta cũng không hề công bố. Tuy nhiên, với điều kiện kỹ thuật như hiện nay thì điếu đó vẫn khó có thể xảy ra. Độ an toàn: -Độ an toàn của khối: khối phải có độ dài đủ để chống lại các phương pháp phân tích thống kê và ngăn việc một số khối nào đó xuất hiện nhiều hơn các khối khác. Mặt khác sự phức tạp của thuật toán tăng theo hàm mũ với độ dài khối. Với khối có độ dài 64 bit là đủ độ an toàn. -Độ dài khoá: Khoá phải có độ dài đủ để chống lại các phương pháp vét cạn khoá ( Chống khả năng thử các khoá được sinh ra từ (N)bit khoá cho trước ). - Độ phức tạp: Bản mã phải phụ thuộc một cách phức tạp vào bản rõ và khoá. Mục tiêu đặt ra ở đây là phải phức tạp hoá sự phụ thuộc của bộ mặt thống kê của bản mã vào bản rõ. IDEA đạt được diều này nhờ sử dụng 3 phép toán sẽ trình bày sau đây: - Sự phân bố: IDEA đã đạt được việc mỗi bít của bản rõ phải có ảnh hưởng tới nhiều bit của bản mã và mỗi bit khoá cũng tác động đến nhiều bit của bản mã. Điều này làm cho cấu trúc của bản rõ sẽ bị phá vỡ trong bản mã. I.2. Các phép toán sử dụng trong IDEA Trong thuật toán IDEA gồm có 3 thuật toán sau: - Phép XOR theo bit. Kí hiệu là Å - Phép cộng 2 số nguyên lấy modulo 216 (65536)với đầu vào và các đầu ra là các số nguyên không dấu 16 bit. Kí hiệu là U . - Phép nhân hai số nguyên lấy modulo 216 +1 với đầu vào và đầu ra là các số nguyên không dấu 16 bit. Quy ước là khối toàn số 0 biểu thị cho 216 . Kí hiệu Ä. Cả ba phép toán này đều phải thoả mãn các tính chất sau: - Không có 2 phép toán nào thoả mãn luật phân phối : a U (b Ä c ) ¹ (a U b ) Ä ( a U c) - Không có 2 phép toán nào thoả mãn luật kết hợp : a U (b Ä c ) ¹ (a U b ) Ä c Việc sử dụng 3 phép toán này tạo ra một sự biến đổi phức tạp dữ liệu đầu vào làm cho việc mã thám trở nên khó khăn hơn so với việc chỉ sử dụng một phép toán đơn giản. Trong IDEA sự phân bố được tạo ra dựa trên khối thuật toán có cấu trúc như hình vẽ gọi là cấu trúc MA( Multiplication/Additio) trong hình sau: Ä Ä U U F1 F2 Z5 Z6 G1 G2 Hình 1: Cấu trúc Multiplication/Additio (MA) Khối này nhận 16 bit từ bản rõ và 16 bit được lấy từ khoá ra theo một quy tắc nào đó ( 16 bit này được gọi là subkey và quy tắc lấy subkey từ khoá sẽ được trình bày ở sau)để tạo ra 16 bit đầu ra. Một chương trình kiểm tra trên máy tính bằng phương pháp vét cạn xác định rằng mỗi bit ở đầu ra phụ thuộc vào các bít rõ và bit subkey đầu vào. Cấu trúc này được sử dụng lặp lại 8 lần trong thuật toán và tạo nên một sự phân bố có hiệu qủa. IDEA được xây dựng sao cho việc thực hiện nó được dễ dàng cả trên phần cứng và phần mềm . Việc thực hiện trên phần cứng, điển hình là trên vi mạch VLSI (VLSI: mạch tích hợp cao) , được thiết kế để đạt được tốc độ cao. Việc xây dựng trên phần mềm thì thuận tiện và giá thành thấp. Những điểm chủ yếu trong việc xây dựng phần mềm: + Sử dụng những khối nhỏ : những phép mã thực hiện trên những khối có độ dài 8,16,32 bit phù hợp với việc xử lý trên máy tính. + Sử dụng thuật toán giản đơn :Phép toán mã dễ dàng trong lập ttình như phép cộng , phép dịch chuyển (shift),..., Cả 3 phép toán của IDEA đều thoả mãn những yêu cầu này. Điểm khó khăn nhất là phép toán nhân modulo(216 +1) cũng có thể dễ dàng xây dựng từ những phép toán sẵn có . - Những điểm chủ yếu trong việc thực hiện trên phần cứng: + Sự tương tự trong mã hoá và giải mã : Mã hoá và giải mã chỉ nên khác nhau trong việc sử dụng khoá và nhờ đó một phương tiện có thể dùng cho cả mã hoá và giải mã. + Cấu trúc lặp lại : Phương pháp mã nên có cấu trúc modul lặp lại để các mạch VLSI có thể thực hiện được dễ dàng. IDEA được xây dựng từ 2 khối modulo đơn giản và sử dụng lặp lại nhiều lần. I.1.3 Mã hoá và giải mã trong IDEA: Mã hoá: Giống như các sơ đồ mã hoá khác, hàm mã hoá có 2 tham số ở đầu vào là Bản rõ cần mã và khoá. Trong trường hợp này là 64 bit rõ là 128 bit khoá . Từ đầu vào đến đầu ra, các bit rõ lần lượt đi qua 8 modul và một hàm biến đổi cuối cùng. Tám modul này có cấu trúc giống nhau và thực hiện các thao tác như nhau với dữ liệu đầu vào. Mỗi modul nhận 4 khối 16 bit rõ ở đầu vào cùng với các subkey và đưa ra 4 khối 16 bit đã được mã hoá. Do đó 64 bit rõ sẽ được chia thành 4 khối nhỏ gọi là các subblock, mỗi subblock là 16 bit. Cùng với các subblock này là 6 khối subkey cũng sẽ được đưa vào từng modul. Như vậy thêm 4 subkey cần thiết cho hàm biến đổi cuối cùng, ta cần tổng cộng 52 khối subkey cho một lần 64 bit rõ X1 X2 X3 X4 W11 W12 W13 W14 Modul 2 W21 W221 W23 W24 W71 W72 W73 W74 W81 W82 W83 W84 Modul 8 Hàm biến đổi Z1 Z52 Modul 1 Tạo Subkey từ khoá 128 bit khoá Z 16 ....................16 64 bit mã Hình 2: Cấu trúc IDEA Như đã nói ở trên, các modul có cấu trúc giống nhau và chỉ khác nhau ở dữ liệu đầu vào. Trừ modul đầu tiên nhận 64 bit rõ đưa từ ngoài vào, các modul đứng sau sẽ nhận 4 khối subblock 16 bit đầu ra của modul đứng trước nó làm các bit rõ đầu vào. Trong quá trình đầu tiên các modul kết hợp 4 subblock với 4 subkey bằng các phép toán U và Ä. Bốn khối đầu ra của quá trình này XOR với nhau như trong sơ đồ để tạo ra 2 khối đầu vào cho cấu trúc MA sẽ kết hợp chúng với 2 subkey còn lại để tạo ra 2 khối 16 bit mới. Cuối cùng, 4 khối được tạo ra từ quá trình đầu tiên sẽ được XOR với 2 khối đầu ra của cấu trúc MA để tạo ra 4 khối đầu ra của modul. Ta cũng cần chú ý một điều là 2 khối đầu vào X2 và X3 được hoán đổi cho nhau để tạo ra 2 khối W12 và W13 được đưa ra ngoài. Điều này làm tăng sự hoà trộn của các bit được xử lý và tăng khả năng chống lại các phương pháp mã thám. X1 X2 X3 X4 Hình 3: Cấu trúc một modul (Modul 1) Ä Ä Ä U Ä U Ä Å Å Å U Ä U U Å W11 W12 W13 W14 Z6 Z5 Z3 Z4 Z1 Z2 Hàm biến ở cuối cùng ta cũng có thể coi như một modul thứ 9. Hàm này có cấu trúc giống như cấu trúc đã thực hiện trong quá trình đầu tiên của một modul chỉ khác một điều là khối thứ 2 và thứ 3 ở đầu vào được đổi chỗ cho nhau trước khi được đưa tới đơn vị phép toán. Thực ra đây chỉ là việc trả lại thứ tự đã bị đổi sau modul thứ 8. Lý do của việc này là sự giống nhau về cấu trúc của quá trình giải mã và quá trình mã hoá. Ä Ä U U Z51 Z49 Z52 Z50 Y1 Y2 Y3 Y4 Hình 4: Hàm biến đổi của IDEA * Quy tắc tạo ra subkey: Như trên đã trình bày, cần thiết phải có 52 khối subkey 16 bit được tạo ra từ 128 bit khoá. Quy tắc tạo subkey như sau: 8 subkey đầu tiên , Z1...Z8, được lấy trực tiếp từ khoá với X1 là 16 bit đầu ( Bit có trọng số cao nhất ), Z2 là 16 bit tiếp theo và cứ tiếp tục như vậy - Sau đó khoá được quay trái 25 bit và 8 subkey tiếp theo được tạo ra theo quy tắc trên. Thao tác này được lặp lại cho đến khi có đủ 52 khối subkey. Quy tắc này là một phương pháp hiệu quả cho việc đa dạng hoá các bit khoá dùng cho các modul. Ta nhận thấy rằng những subkey đầu tiên dùng trong mỗi modul sử dụng những tập hợp bit khác nhau của khoá. Nếu như khoá 128 bit được ký hiệu là Z[ 1..128] thì subkey đầu tiên của modul sẽ là : Z1 = Z[ 1..16] Z25 = Z[76..91] Z7 = Z[97..112] Z31 = Z[44..59] Z13 = Z[90..105] Z37 = Z[37..52] Z19 = Z[83..98] Z43 = Z[30..45] Như vậy , 96 bit subkey sử dụng cho mỗi modul , trừ modul thứ nhất và modul thứ 8, là không liên tục. Do đó không có một mối liên hệ dịch chuyển đơn giản nào giữa các subkey của của một modul và giữa các modul với nhau. Nguyên nhân có được kết quả này là việc chỉ có 6 khối subkey được sử dụng trong khi có 8 khối subkeyđược tạo ra trong mỗi lần dịch chuyển khoá. Giải mã : Quá trình giải mã về cơ bản giống quá trình mã hoá, giải mã nhận bản mã ở đầu vào và cùng đi qua những cấu trúc như ở trên, chỉ khác ở sự lựa chọn các subkey. Các subkey để giải mã U1, U2,...U52 nhận được từ khoá mã theo quy tắc sau: Đối với modul giải mã i ta lấy 4 subkey đầu của modul mã hóa thứ (10 - i ), ở đây hàm biến đổi được coi như modul thứ 9. Sau đó lấy nhân đảo modulo (216+1) của subkey thứ 1 và thứ 4 để dùng cho subkey giải mã thứ 1 và thứ 4 tương ứng. Đối với các modul từ thứ 2 đến thứ 8, subkey giải mã thứ 2 và thứ 3 là cộng đảo modulo216 của subkey thứ 3 và thứ 2 tương ứng. Đối với các modul thứ 1 và thứ 9 , cho subkey giải mã thứ 2 và thứ 3 là cộng đảo modul216 của subkey thứ 3 và thứ 2 tương ứng. -Đối với 8 modul đầu tiên , 2 subkey cuối cùng của modul i là 2 subkey cuối cùng của modul mã hoá thứ ( 9 - i ). ở đây nhân đảo Zj-1 của Zj là: Zj Ä Zj-1 =1 Vì 216 + 1 là một số nguyên tố nên mỗi số nguyên Zj < 216 có một số nhân đảo modulo(216 + 1) duy nhất. Với cộng đảo hai modullo 216 ta có: -Zj U Zj = 0 Hình sau hiện quá trình mã hoá ( theo chiều đi xuống bên trái) và quá trình giải mã ( chiều đi lên bên phải) của thuật toán IDEA. X1 X2 X3 X4 Biến đổi I11 I12 I13 I14 Mã hoá W11 W12 W13 W14 Biến đổi I21 I22 I23 I24 Mã hoá W21 W22 W23 W24 W71 W72 W73 W74 Mã hoá I81 I82 I83 I84 W81 W82 W83 W84 Biến đổi đầu ra Y1 Y2 Y4 Y4 Y4 Y4 Y4 Y3 Biến đổi X1 X2 X3 X4 Biến đổi đầu ra Mã hoá V81 V82 V83 V84 Biến đổi J14 J13 J12 J11 J24 J23 J22 J21 J81 J82 J83 J84 V71 V72 V73 V74 Biến đổi Biến đổi V24 V23 V22 V21 V71 V14 V13 V12 V11 V21 Mã hoá Mã hoá Modul1 Modul2 Modul8 Modul8 Modul2 Modul1 Z1..Z4 Z5..Z6 Z11..Z12 Z7..Z10 Z1..Z4 Z42..Z46 Z47..Z48 Z49..Z52 Z5..Z6 U1..U4 U5..U6 U1..U10 U11..U12 U43..U46 U47..U48 U1..U4 U49..U52 Hình 5: Mã hoá và giải mã trong IDEA. Mỗi modul được chia thành 2 khối nhỏ: khối biến đổi và khối mã hoá. Khối biến đổi tương ứng với quá trình đầu tiên trong mỗi modul, còn khối mã hoá tương ứng với các quá trình còn lại. Ở phía cuối của sơ đồ, bên mã hoá ta nhận được các mối quan hệ giữa các đầu ra và đầu vào của hàm biến đổi: Y1 = W81 Ä Z49 Y3 = W82 U Z51 Y2 = W83 U Z50 Y4 = W82 Ä Z52 Tại khối biến đổi của modul thứ nhất trong quá trình giải mã, đầu ra và đầu vào có mối quan hệ sau: J11 = Y1 Ä U1 J13 = Y3U U3 J12 = Y2U U2 J14 = Y4 Ä U4 Ta có: J11 = Y1 Ä Z49 –1 = W81 Ä Z49 Ä Z49-1 =W81 J12 = Y2 U -Z50 = W83 U Z50 U -Z50 = W83 J13 = Y3 U -Z51 = W82 U Z51 U -Z51 = W82 J11 = Y4 Ä Z50 –1 = W84 Ä Z50 Ä Z50-1 =W84 Như vậy, kết quả thu được sau khối biến đổi thứ nhất của quá trình giải mã chính là dữ liệu rõ đưa vào khối mã hoá cuối cùng của quá trình mã hoá chỉ khác là khối dữ liệu thứ 2 và khối dữ liệu thứ 3 đã đổi chỗ cho nhau. Bây giờ ta sẽ xét đến mối quan hệ thu được theo Hình 3 W81 = I81 Å MAR( I81 Å I83 , I82 Å I84 ) W82 = I83 Å MAR( I81 Å I83 , I82 Å I84 ) W83 = I82 Å MAL( I81 Å I83 , I82 Å I84 ) W84 = I84 Å MAL( I81 Å I83 , I82 Å I84 ) Trong đó MAR(X,Y) là đầu ra phía bên phải còn MAL(X,Y) là đầu ra phía bên trái của cấu trúc MA trong hình 1 khi đầu vào là X và Y. Và: V11 = J11 Å MAR (J11 Å J13, J12 Å J14) = W81 Å MAR(W81 Å W82, W83 Å W84) = I81 Å MAR( I81 Å I83 , I82 Å I84 ) Å MAR[I81 Å MAR( I81 Å I83 , I82 Å I84 ) Å I83 Å MAR( I81 Å I83 , I82 Å I84 ), I82 Å MAL( I81 Å I83 , I82 Å I84 ) Å I84 Å MAL( I81 Å I83 , I82 Å I84 )] = I81 Å MAR( I81 Å I83 , I82 Å I84) Å MAR(W81 Å W82, W83 Å W84) =I81 Tương tự ta có : V12 = I82 V13 = I83 V14 = I84 Như vậy kết quả thu được sau khối mã hoá thứ nhất của quá trình giải mã lại là dữ liệu đưa vào khối biến đổi của modul cuối cùng của quá trình mã hoá chỉ khác là khối dữ liệu thứ 2 và khối dữ liệu thứ 3 đã đổi chỗ cho nhau. Cứ như vậy ta sẽ thu được: V81 = I11 V82 = I13 V83 = I12 V84 =I14 Vì hàm biến đổi cuối cùng của quá trình giải mã cũng giống như khối biến đổi trong modul đầu tiên của quá trình mã hoá chỉ khác là có đổi chỗ của khối dữ liệu thứ 2 và khối dữ liệu thứ 3 nên ta có bản rõ thu được sau bản mã giống bản rõ đưa vào mã hoá . I.1.4 Quá trình làm việc của một Modul Để dễ dàng nhìn thấy hơn về quá trình làm việc của 1 modul. Theo như hình 3 ( Cấu trúc của 1 modul). Ta thấy 4 khối được đưa vào là X1, X2, X3, X4 cùng với các khoá Z1, Z2, Z3, Z4, Z5, Z6 thì sau các quá trình biến đổi sẽ đưa ra các khối là W1, W2, W3, W4 . Giả sử ta quy ước các kết quả của mỗi phép toán là : K1, K2, K3, K4, K5, K6, K7, K8, K9, K10, K11, K12 thì ta có: X1 X2 X3 X4 Ä Ä Ä U Ä U Ä Å Å Å Å U Ä U U K2 K11 K1 K3 K9 K7 K10 K8 K4 K5 K6 K12 Z1 Z3 Z2 Z4 Z5 Z6 W11 W12 W13 W14 Hình 3: Cấu trúc một modul (Modul 1) Với W11: W11 = K1 Å K2 Trong đó : K1 = Z1 Ä X1 K2 = Z6 Ä K3 K3 = K4 U K5 K4 = Z5 Ä K6 K5 = K7 Å K8 K6 = K9 Å K10 K7 = Z4 Ä X4 K8 = Z2 U X2 K9 = Z3 U X3 K10 = Z1 Ä X1 Với W12 W12 = K2 Å K9 Trong đó: K2 = Z6 Ä K3 K3 = K4 U K5 K4 = Z5 Ä K6 K5 = K7 Å K8 K6 = K9 Å K10 K7 = Z4 Ä X4 K8 = Z2 U X2 K9 = Z3 U X3 K10 = Z1 Ä X1 Với W13: W13 = K8 Å K11 Trong đó: K11 = K2 U K4 K2 = Z6 Ä K3 K3 = K4 U K5 K4 = Z5 Ä K6 K5 = K7 Å K8 K6 = K9 Å K10 K7 = Z4 Ä X4 K8 = Z2 U X2 K9 = Z3 U X3 K10 = Z1 Ä X1 Với W14 W14 = K7 Å K12 Trong đó: K12 = K2 U K4 K7 = Z4 Ä X4 K2 = Z6 Ä K3 K3 = K4 U K5 K4 = Z5 Ä K6 K5 = K7 Å K8 K6 = K9 Å K10 K8 = Z2 U X2 K9 = Z3 U X3 K10 = Z1 Ä X1 CHƯƠNG II. MỘT SỐ ĐOẠN CHƯƠNG TRÌNH VÍ DỤ II.1 /* Nhân 2 số modulo(216 +1) */ Đây là đoạn chương trình ví dụ về một trong ba phép toán sử dụng trong thuật toán IDEA với đầu vào và đầu ra là các số nguyên không dấu 16 bit. Quy ước là khối toàn số 0 biểu thị cho 216. CONST static uint16 mol(register uint16 a, register uint16 b) { register word32 p; p = (word32) a*b; if(p) { b = low16(); a = p >>16; return (b-a) + (b<a); } else if (a) { return 1-a; } else { return 1 – b; } } II.2 Đoạn chương trình ví dụ về tính số nhân đảo của số x modulo 65537 CONST static unit16 mulInv(uint16 x) { uint16 t0,t1; uint16 p,y; if(x<=1) return x; /* 0 and 1 area self-inverse*/ t1 = 0x10001L/x; /*Since x>=2, this fist into 16 bits*/ y = 0x10001L % x; if (y==1) return low 16(1-t1) ; t0=1; do { q=x/y; x=x%y; t0 += q*t1; if (y==1) return t0; q =y/x; y = y%x; t1 += q*t0; } while(y! =1); return low16(1-t1); } II.3 /*Tạo 52 khối subkey từ khoá 128 bit */ Static void ideaExpandKey(byte const *userkey. word16 * EK) { int i,j; for (j =0;j < 8; j++) { EK[j] = (userkey[0] << 8) + userkey[1] ; userkey +=2; } for (i = 0; j < IDEAKEYLEN; j++) { i++; EK[i+7] = EK[i&7] > 7; EK +=i &8; i & =7; } } II.4 /* Tính khoá cho quá trình giải mã*/ Static void ideaInvaerKey(word16 const *EK, word16 DK[ IDEAKEYLEN] ) { int i; uint 16 t1,t2,t3; word16 temp[IDEAKEYLEN]; word16 *p = temp + IDEAKEYLEN; t1 = mulInv ( *EK ++); t2 = -*EK++; t3 ==-*EK++; *--p = mulInv(EK++) ; *--p = t2; *--p = t1; for (i = 0; i< IDEAROUNDS – 1; i++) { t1 = *EK++; *--p = *EK++; *--p = t1; t1 = mulInv ( *EK ++); t2 = -*EK++; t3 ==-*EK++; *--p = mulInv(EK++) ; *--p = t2; *--p = t3; *--p = t1; } t1 = -*EK++; *--p =-*EK++; *--p = t1; t1 = mulInv ( *EK ++); t2 = -*EK++; t3 ==-*EK++; *--p = mulInv(EK++) ; *--p = t3; *--p = t2; *--p = t1; memcpy(DK,temp,sizeof(temp)); burn(temp); } II.5 / * Chương trình mã */ Static void ideaClipher(byte const inbuf[8], byte outbuf[8], word 16 const *key) { register uint16 x1, x2, x3, x4, s2, s3; word16 *in, *out; #ifndef SMALL_CACHE register uint16 t16; register word32 t32; # endif int r = IDEAROUNDS; in = (word16*) inbuf; x1 = *in++; x2 = *in++; x3 = *in++; x4 = *in; #ifdef HIGHFIRST x1 = (x1>>8) | (x1<<8); x2 = (x2>>8) | (x2<<8); x3 = (x3>>8) | (x3<<8); x4 = (x4>>8) | (x4<<8); #endif do { MUL(x1,*key++); x2 +=*key++; x3 +=*key++; MUL(x4,*key++); s3 = x3; x3^ =x1; MUL(x3,*key++); s2 =x2; x2^ = x4; x2 +=x3; MUL(x2,*key++); x3 +=x2; x1^ =x2; x4^ =x3; x2^ =s3; x3^= s2; } while(--r); MUL(x1,*key++); x3 +=*key++; x2 +=*key++; MUL(x4,*key); out = (word16*) outbuf; #ifdef HIGHFIRST *out++ = x1; *out++ = x3; *out++ = x2; *out = x4; #else /* !HIGHFIRST*/ x1 =low16(x1); x2 =low16(x2); x3 =low16(x3); x4 =low16(x4); *out++ = (x1>>8) | (x1>>x8) *out++ = (x3>>8) | (x3>>x8) *out++ = (x2>>8) | (x2>>x8) *out = (x4>>8) | (x4>>x8) #endif } CHƯƠNG III. THIẾT KẾ CHƯƠNG TRÌNH MÃ DỊCH BẰNG HỆ MẬT IDEA * Giới thiệu về phần mềm mã dịch file bằng IDEA Mục đích và thiết kế: III.1. Mục đích: Phần mềm nhằm mục đích mã hoá một file cần được bảo vệ, file sau khi được mã hoá có thể để công khai trên máy(miễn là tài liệu riêng) hoặc được đưa lên đường truyền để gửi cho người khác (nếu là thông tin gửi cho họ). Nếu cần đọc tài liệu gốc ta có thể giải mã file trên. mã pháp được sử dụng là IDEA. Để có thể làm được việc trên chung ta cần một số việc làm như sau: a. Thoả thuận khoá: Cũng như mọi hệ mật khoá đối xứng khác thì hệ mật IDEA cần có một thao tác thoả thuận về khoá được dùng để mã hoá một văn bản. Công việc này là cần thiết vì nếu không dùng chung nhau một khoá thì ta không thể khôi phục lại bản gốc bằng mã pháp đã nêu, Trong trường hợp bảo vệ tài liệu riêng tư thì cần phải có sự lưu trữ và “đánh dấu” khoá nào được dùng để mã hoá tệp nào. Ngược lại để gửi cho người khác thì hai người phải có trùng nhau một khoá , do khoá này không thể truyền bằng đường công khai nên hai người có thể thoả thuận nhau trước bằng cánh trao tay nhau khoá đã dùng. Bài toán thoả thuận khoá từ khi ra đời các hệ mật khoá công khai như RSA hay ELGAMA đã có một lối thoát kì diệu đó là hai người chỉ cần công khai khóa mã dùng để mã hoá khoá đã dùng, thông tin về khoá sau khi mã có thể gửi trên kênh công khai để đến chủ của khoá đã công khai đó do đặc tính của loại hệ mật này thì chỉ có chủ của khoá đã công khai có thể dịch được bản mã. ở đây tôi không đi sâu vào việc nghiên cứu phương pháp thoả thuận khoá bằng hệ mật công khai vì không đủ điều kiện về thời gian và kiến thức mà chỉ muốn đưa ra một giải pháp có tính cổ điển trong việc làm này. Trong mạng liên lạc mật mà chúng tôi thiết kế, mỗi cá nhân đều có một tệp về các khoá sẽ được sử dụng, các tệp này được một nơi sản xuất và được phân phối đến từng người theo phương thức trao tay, tệp khoá trong mô hình của tôi là một file chứa trong một đĩa mềm . Việc thoả thuận khoá sẽ được tiến hành như sau: Trong file mã hoá chúng tôi tiến hành ghi địa chỉ của khoá đã dùng để mã hoá lên đầu một file mã (Header). Địa chỉ này gồm hai byte và như vậy trong mỗi tệp khoá sẽ chỉ chứa tối đa 216 = 65536 khoá khác nhau . Chú ý rằng mỗi khoá dùng trong hệ IDEA gồm 16 bytes (128 bit) do đó nếu tệp khoá chứa đủ 216 khoá thì kích thước của file khoá là 220 bytes> 1.4 MB không chứa đủ trong một dĩa thông dụng. Do chỉ để mô phỏng nên thực tế chúng tôi chỉ tạo tệp khoá có kích thước là 524 byte (chứa 33 khoá ) Ta có thể mô tả cấu tạo file mã qua hình sau: Địa chỉ = Random(K0) Lấy khoá thử “địa chỉ” File rõ Địa chỉ File mã Mã hoá IDEA Khi mã: Địa chỉ được hiểu là số thứ tự ghi trong tệp mã Khi dịch : Địa chỉ Đọc “địa chỉ” từ Header Lấy khoá thử “địa chỉ” Giải mã IDEA File dịch III.2. Cách thực hiện mã hoá và giải mã theo IDEA. Trong chương I chúng ta đã trình bày đến mã pháp IDEA tác động đến mỗi Buffer 4 từ 16 bit (hay 8 byte). Như vậy khi thực hiện mã hoá một file bất kì thì chúng ta phải chia file này thành các buffer theo tiêu chuẩn trên. Một vấn đề nảy sinh là không phải file nào cũng có thể chia thành các buffer đó , nói cách khác khi kích thước byte của file không chia hết cho 8 thì thì lượng byte chuẩn còn dư cuối cùng đó không đủ lấp kín một buffer trên các byte thiếu trong buffer cuối cùng bằng các byte định trước nào đó(chẳng hạn như các dấu cách ). Theo phương pháp này thì việc mã hoá sẽ trôi chảy nhưng khi giải mã chúng ta cần phải có thêm một thông tin giúp cho việc xoá đi những byte cuối cùng nhưng byte này vốn được chèn thêm vào như đã nói ở trên. Có làm được như vậy chúng ta mới khôi phục lại được hoàn toàn bản gốc. Ngoài phương pháp trên người ta còn dùng một phương pháp khắc phục khác gọi là bổ xung buffer lẻ bằng chính những byte đã mã hoá trước đó. Phương pháp này áp dụng cho việc mã dịch các file có độ dài ³ 8 byte và được mô tả như sau: Giả sử việc mã hoá buffer tiêu chuẩn cuối cùng ta được buffer mã là { C0, C1 , C2 , C3 , C4 , C5 , C6 , C7} , giả sử phần lể cuối buffer là {b0 , b1,...bi }ở đây i <7. Khi này ta tạo một buffer tiêu chuẩn { d0,...,d7 } bằng càch sau:1 dj = Ci + 1 + j với j > 7 –i dj = b7 –i +j với j ³ 7 -i Ta có thể minh hoạ theo hình vẽ sau: C0 .............. Ci Ci+1 ..................... C7 b0 ....................... bi d0 d7-i-1 d7-1 d7 Thực hiện mã hoá nốt buffer chuẩn vừa tạo được : Theo phương pháp trên thì tương ứng với nó ta phải có cách ghi các buffer mã vào file mã một cách phù hợp. Phương pháp này được mô tả như sau: Giả sử n0 = l div 8và i0 = l mod 8 với l là kích thước byte của file rõ . Đoạn trình sau ( Trong phần mềm) thể hiện việc ghi thông tin đã mã hoá vào file mã For (j:= 0; j < n0 –1; j++) { fread(& Buffer, 8,1,file_ro); } IDEA(Buffer); fwrite(&Buffer,8,1,file_ma); } fread(&Buffer , 8,1,file_ro); IDEA(Buffer); fread(&Buffer , i0,1,file_ro); memcpy(&buffer_le, buffer, 8-i ); fread(&(Buffer _le)+8-i, i, 1,file_ro); IDEA(buffer_le); Fwrite(buffer_le, 8,1,file_ma); } Qua đoạn trình trên chúng ta thấy rằng sau khi mã hoá mỗi buffer thứ j < n0-1 ta ghi toàn bộ buffer đã mã này vào file_ma còn đối với buffer thứ j =n0 –1(tính từ 0) thì sau khi mã hoá nó ta chỉ ghi vào file_ma i byte của buffer mã còn 8- i byte chưa ghi sẽ được dùng để tạo buffer_le cùng với i byte lẻ của file_ro. Cuối cùng ta ghi nốt buffer mã của buffer_le vào file_ma. Quá trình dịch sẽ được thực hiện theo trình tự ngược lại đối với buffer tiêu chuẩn cuối cùng và buffer_le. Cụ thể là sau khi đọc từ file_ma dịch n0-1 buffer đầu rồi ghi vào file_dịch thì tiếp theo ta đọc 8 byte của file_ma dịch nó rồi dùng 8 –i byet cuối cùng của buffer đã dịch này ghép với i byte áp 8 byte cuối của file_ma tạo ra buffer_le. Dịch buffer_le rồi ghi vào file_dịch , cuối cùng ghi nốt i byte cuối của buffer đã dịch ở trước vào file_dịch. Dễ dàng nhận ra rằng file_dịch và file_ro là trùng nhau. III.3. Các chức năng của phần mềm: Do điều kiện thời gian chúng tôi chỉ viết phần mềm trực tiếp bằng ngôn ngữ Boland-C và tương ứng chỉ thiết kế một giao diện Text. Phần mềm có hai chức năng chính là mã hoá và giải mã . Khi thực hiện chức năng mã hoá cần thực hiện thủ tục chọn tên file cần mã (file_ro) và đặt tên cho file đã mã hoá (file_ma). Quá trình chọn khoá dùng để mã hoá file này được thực hiện tự động bằng một hàm Random của C. Ngược lại việc thực hiện chức năng giải mã(dịch) thì cần thực hiện các thủ tục chọn tên file cần dịch (file_ma) và đặt tên cho file sau khi dịch (file_dịch). Chú ý cuối cùng: Phần mềm được viết chỉ một mô phỏng cho một cách dùng cụ thể của hệ mật IDEA dùng để bảo mật thông tin dưới dạng file (có thể dùng để lưu trữ hoặc truyền cho người khác ). Để có thể là một sản phẩm hoàn chỉnh thì cần phải hoàn thiện hơn nhiều đặc biệt là cần có sự bổ xung về quá trình phân phối khoá tự động và sau đó đến quá trình xác thực bằng chữ ký số mà công cụ phù hợp với các chức năng này là các hệ mật khoá công khai như đã nói ở trên . III.4. Chương trình mô tả của thuật toán IDEA /* Chuong trinh ma dich file bang he mat IDEA*/ #include #include #include #include #include #include #include typedef unsigned char BYTE; typedef unsigned int WORD; typedef unsigned long LONG; #define IDEA_max 0x10001 /* Dinh nghia gia tri x*y modulo 2^16+1 trong truong hop x>0 va y>0 */ #define IDEA_tich(x,y) ((x*y)%IDEA_max) #define do_dai_buff 0x8000 BYTE Buff[do_dai_buff]; WORD Block_vao[4],IDEA_khoa[52],IDEA_mam[8]; /* Ham tinh tich x*y (modulo 65537) */ WORD IDEA_nhan(WORD x,WORD y) {if ((x==0)&&(y==0)) return 1; else {if (x==0) return (WORD) (IDEA_max-y); else if (y==0) return (WORD) (IDEA_max-x); else { LONG u=x,v=y; return (WORD) IDEA_tich(u,v); } } } /* Ham tinh x=nghich dao cua x (modulo 65537) */ WORD IDEA_nghich_dao(WORD x) { if (x<2) return x; else {LONG a=IDEA_max;WORD q[200],r=x,b;BYTE i=0; while (r>1) { q[i]=a/r; b=r; r=a%r; a=b; i++; } WORD s=1,t;r=0; for (int j=i-1;j>=0;j--) { t=s; t*=q[j]; t+=r; r=s; s=t; } if (i&1) { a=IDEA_max-t; t=a; } return t; } } /* Thu tuc lay 8 word thu k trong tep "IDEA.key" lam mam khoa (IDEA_mam) */ char IDEA_lay_khoa(short k) { char b; FILE *f; f=fopen("IDEA.key","rb"); long l=filelength(fileno(f)),m=16; m*=k; if (l<=m) { b=0; gotoxy(36,12); printf(" Khong lay duoc khoa"); } else { b=1; fseek(f,m,SEEK_SET); fread(&IDEA_mam,16,1,f); } fclose(f); return b; } /* Thu tuc tinh 52 word khoa ma hoa tu 8 word mam */ void IDEA_khoa_ma() {WORD tam[8]; BYTE b,db,dw; for (int i=0;i<7;i++) {b=25*i; db=b&15; dw=b>>4; for (char j=0;j<8;j++) tam[j]=(IDEA_mam[(j+dw)&7]>>db)^(IDEA_mam[(j+dw+1)&7]<<(16-db)); if (i==6) memcpy(IDEA_khoa+(8*i),tam,8); else memcpy(IDEA_khoa+(8*i),tam,16); } } /* Thu tuc tinh 52 word khoa giai ma tu 8 word mam */ void IDEA_khoa_dich() { WORD tam[8],k1[52];BYTE a,b,db,dw; for (int i=0;i<7;i++) {b=25*i; db=b&15; dw=b>>4; for (char j=0;j<8;j++) tam[j]=(IDEA_mam[(j+dw)&7]>>db)^(IDEA_mam[(j+dw+1)&7]<<(16-db)); if (i==6) memcpy(k1+(8*i),tam,8); else memcpy(k1+(8*i),tam,16); } for (i=0;i<8;i++) {b=6*i;a=48-b; IDEA_khoa[b]=IDEA_nghich_dao(k1[a]); IDEA_khoa[b+3]=IDEA_nghich_dao(k1[a+3]); if (i) { IDEA_khoa[b+1]=0-k1[a+2]; IDEA_khoa[b+2]=0-k1[a+1]; } else { IDEA_khoa[b+1]=0-k1[a+1]; IDEA_khoa[b+2]=0-k1[a+2]; } b+=4;a=50-b; IDEA_khoa[b]=k1[a]; IDEA_khoa[b+1]=k1[a+1]; } b=6*i;a=48-b; IDEA_khoa[b]=IDEA_nghich_dao(k1[a]); IDEA_khoa[b+3]=IDEA_nghich_dao(k1[a+3]); IDEA_khoa[b+1]=0-k1[a+1]; IDEA_khoa[b+2]=0-k1[a+2]; } /* Thu tuc ma hoa hoac giai ma theo he IDEA mot BLOCK 4 word */ void idea(WORD r) {WORD x[4],y[4],a,b; memcpy(y,Buff+r,8); /* 8 vong dau */ for (int i=0;i<8;i++) {BYTE j=6*i; x[0]=IDEA_nhan(y[0],IDEA_khoa[j]); x[1]=y[1]+IDEA_khoa[j+1]; x[2]=y[2]+IDEA_khoa[j+2]; x[3]=IDEA_nhan(y[3],IDEA_khoa[j+3]); a=x[0]^x[2]; b=x[1]^x[3]; a=IDEA_nhan(a,IDEA_khoa[j+4]); b+=a; b=IDEA_nhan(b,IDEA_khoa[j+5]); a+=b; y[0]=x[0]^b; y[1]=x[2]^b; y[2]=x[1]^a; y[3]=x[3]^a; } /* vong cuoi */ x[0]=IDEA_nhan(y[0],IDEA_khoa[48]); x[1]=y[2]+IDEA_khoa[49]; x[2]=y[1]+IDEA_khoa[50]; x[3]=IDEA_nhan(y[3],IDEA_khoa[51]); memcpy((Buff+r),x,8); } /* Thu tuc ma hoa hoac giai ma theo he IDEA mot file */ /* Chu y ma hoa khi b=1 va giai ma khi b=0*/ void IDEA_ma_dich(char b,char file_in[50],char file_out[50]) { FILE *f_in,*f_out; LONG l,so_buff,so_byte_du; short ss; f_in=fopen(file_in,"rb"); l=filelength(fileno(f_in)); f_out=fopen(file_out,"wb"); if (b) { randomize(); ss=random(128); ss<<=8; ss^=random(256); IDEA_lay_khoa(ss); fwrite(&ss,2,1,f_out); IDEA_khoa_ma(); } else { fread(&ss,2,1,f_in); IDEA_lay_khoa(ss); IDEA_khoa_dich(); l-=2; } so_buff=l>>15; so_byte_du=l&0x7fff; LONG i,j,k; if (so_byte_du>7) { for (i=0;i<so_buff;i++) { fread(Buff,do_dai_buff,1,f_in); for (j=0;j<0x1000;j++) idea(8*j); fwrite(Buff,do_dai_buff,1,f_out); } fread(Buff,so_byte_du,1,f_in); k=so_byte_du>>3; if (b) { for (j=0;j<k;j++) idea(8*j); idea(so_byte_du-8); } else { for (j=0;j<k-1;j++) idea(8*j); idea(so_byte_du-8); idea(so_byte_du-8-(so_byte_du&7)); } fwrite(Buff,so_byte_du,1,f_out); } else { for (i=0;i<so_buff-1;i++) { fread(Buff,do_dai_buff,1,f_in); for (j=0;j<0x1000;j++) idea(8*j); fwrite(Buff,do_dai_buff,1,f_out); } fread(Buff,do_dai_buff-8,1,f_in); for (j=0;j<0x1000-1;j++) idea(8*j); fwrite(Buff,do_dai_buff-8,1,f_out); so_byte_du+=8; fread(Buff,so_byte_du,1,f_in); if (b) { idea(0); idea(so_byte_du-8); } else { idea(so_byte_du-8); idea(so_byte_du-8-(so_byte_du&7)); } fwrite(Buff,so_byte_du,1,f_out); } fcloseall(); } char nhan_dung(char x[50]) { char m0[10]="ma",m1[10]="MA",m2[10]="dich",m3[10]="DICH"; if ((!strncmp(x,m0,10))||(!strncmp(x,m1,10))) return 1; else if ((!strncmp(x,m2,10))||(!strncmp(x,m3,10))) return 0; else return 2; } void main() { textbackground(0);textcolor(15); clrscr(); short hd,td; float tt; long far *time=(long far *)MK_FP(0,0x46C); long time1,time2; char st[50],f_in[50],f_out[50],ma_dich[5]; gotoxy(20,2); textbackground(4);textcolor(14);clreol(); printf(" CHUONG TRINH MA DICH FILE THEO HE MA IDEA "); textbackground(0);clreol(); printf("\n"); printf("\n"); textbackground(1);textcolor(15);clreol(); printf(" Thuc hien MA hay DICH : "); textbackground(0);textcolor(10);clreol(); printf(" "); hd=wherex(); td=wherey(); scanf("%s",ma_dich); while (!((nhan_dung(ma_dich)==1)||(nhan_dung(ma_dich)==0))) { printf(" NHAP sai dieu kien, De nghi nhap lai "); gotoxy(hd,td); textcolor(10);clreol(); scanf("%s",ma_dich); } printf(" "); gotoxy(1,td+1); if (nhan_dung(ma_dich)==1) { textbackground(7);textcolor(1);clreol(); printf(" NHAP TEN FILE CAN MA: "); textbackground(0);textcolor(10);clreol(); printf(" "); scanf("%s",f_in); textbackground(7);textcolor(1);clreol(); printf(" DAT TEN CHO FILE MA : "); textbackground(0);textcolor(10);clreol(); printf(" "); scanf("%s",f_out); } else { textbackground(7);textcolor(1);clreol(); printf(" NHAP TEN FILE CAN DICH: "); textbackground(0);textcolor(10);clreol(); printf(" "); scanf("%s",f_in); textbackground(7);textcolor(1);clreol(); printf(" DAT TEN CHO FILE DICH : "); textbackground(0);textcolor(10);clreol(); printf(" "); scanf("%s",f_out); } time1=*time; IDEA_ma_dich(nhan_dung(ma_dich),f_in,f_out); time2=*time;tt=((time2-time1)/18.2); textbackground(4);textcolor(14);clreol(); if ((nhan_dung(ma_dich)==1)) printf(" Thoi gian ma hoa file la: %4.4f giay; ",tt); else printf(" Thoi gian dich file la: %4.4f giay; ",tt); textbackground(0);textcolor(15);clreol();printf("\n"); getch(); } TÀI LIỆU THAM KHẢO [1]. “ Mật mã lý thuyết và thực hành” – D.R. Stinton ( Người dịch: Nguyễn Bình ) [2]. Đề tài “ Nghiên cứu các Modulo được dùng trong mật mã ” ( Đề tài nghiên cứu khoa học – 11/1996 ) Chủ nhiệm: TS . Lều Đức Tân Ban cơ yếu chính phủ – Học viện kỹ thuật mật mã [3]. “ Cấu trúc dữ liệu và giải thuật ”. Đỗ Xuân Lôi NXB Khoa học và Kỹ thuật - 1995 [4]. “ An toàn thông tin và thương mại điện tử ”. Phan Đình Diệu. Tạp chí tin học Ngân hàng số 4/99. [5]. “ DISTRIBUTED SYSTEMS CONCEPTS AND DESIGN ” George Couloiris, Jean Dollimore, Tim Kindberg – [1994].

Các file đính kèm theo tài liệu này:

  • docNghiên cứu, ứng dụng của hệ mật IEDA vào bảo mật thông tin.DOC