Cơ sở dữ liệu - Mã hoá thông tin

72 trang vanle 3150

Download

Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Mã hoá thông tin", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

co_so_du_lieu_ma_hoa_thong_tin.doc

Nội dung text: Cơ sở dữ liệu - Mã hoá thông tin

Mục Lục Mở đầu Chương i Cơ sở tốn học 1.Lý thuyết thơng tin 6 1.1 Entropy 6 1.2 Tốc độ của ngơn ngữ. (Rate of Language) 7 1.3 An tồn của hệ thống mã hố 8 2.Lý thuyết độ phức tạp 10 3.Lý thuyết tốn học. 11 3.1 Modular số học. 11 3.2 Số nguyên tố 12 3.3 Ước số chung lớn nhất 12 3.4 Số nghịch đảo Modulo 14 3.5 Ký hiệu La grăng (Legendre Symboy) 16 3.6 Ký hiệu Jacobi (Jacobi Symboy) 16 3.7 Định lý phần dư trung hoa 18 3.8 Định lý Fermat 19 4. Các phép kiểm tra số nguyên tố. 19 4.1 Soloway-Strassen 20 4.2 Rabin-Miller 20 4.3 Lehmann. 21 4.4 Strong Primes 21 Chương II Mật mã 1. Khái niệm cơ bản. 23 2. Protocol 25 2.1 Giới thiệu Protocol 25 2.2 Protocol mật mã 26
Khoa C«ng NghƯ Th«ng Tin 2.3 Mục đích của Protocol. 26 2.4 Truyền thơng sử dụng hệ mật mã đối xứng. 27 2.5 Truyền thơng sử dụng hệ mật mã cơng khai 83 3. Khố 91 3.1 Độ dài khố 91 3.2 Quản lý khố cơng khai 96 4. Mã dịng, mã khối (CFB, CBC) 102 4.1 Mơ hình mã hố khối 102 4.1.1 Mơ hình dây truyền khối mã hố 102 4.1.2 Mơ hình mã hố với thơng tin phản hồi 107 4.2 Mơ hình mã hố dịng 108 5. Các hệ mật mã đối xứng và cơng khai 113 5.1 Hệ mật mã đối xứng 113 5.2 Hệ mật mã cơng khai 118 6. Các cách thám mã 123 Chương III Hệ mã hố RSA 1. Khái niệm hệ mật mã RSA 136 2. Độ an tồn của hệ RSA 142 3. Một số tính chất của hệ RSA 145 Chương IV Mơ hình Client/Server 1.Mơ hình Client/Server 151 2. Mã hố trong mơ hình Client/Server. 155 Chương V Xây dựng hàm thư viện 1.Xây dựng thư viện liên kết động CRYPTO.DLL 160 2.Chương trình Demo thư viện CRYPTO.DLL 207 2 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Mở đầu Thế kỷ XXI thế kỷ cơng nghệ thơng tin, thơng tin đã và đang tác động trực tiếp đến mọi mặt hoạt động kinh tế xã hội của hầu hết các quốc gia trên thế giới. Thơng tin cĩ một vai trị hết sức quan trọng, bởi vậy chúng ta phải làm sao đảm bảo được tính trong suốt của thơng tin nghĩa là thơng tin khơng bị sai lệch, bị thay đổi, bị lộ trong quá trình truyền từ nơi gửi đến nơi nhận. Với sự phát triển rất nhanh của cơng nghệ mạng máy tính đặc biệt là mạng INTERNET thì khối lượng thơng tin ngày càng chuyển tải nhiều hơn. Những tập đồn cơng nghiệp, những cơng ty đa quốc gia, thị trường chứng khốn tiến hành xử lý và truyền nhận những thơng tin đắt giá, những phiên giao dịch hay mua bán cổ phiếu, trái phiếu đều được tiến hành qua mạng. Giờ đây với sự tăng trưởng nhanh của các siêu thị điện tử, thương mại điện tử thì hàng ngày cĩ một khối lượng tiền rất lớn được lưu chuyển trên mạng tồn cầu INTERNET, vấn đề khĩ khăn đặt ra là làm sao giữ được thơng tin bí mật và giữ cho tiền đến đúng được địa chỉ cần đến. Bạn sẽ ra sao nếu như bạn gửi thư cho một người bạn nhưng lại bị một kẻ lạ mặt nào đĩ xem trộm và sửa đổi nội dung bức thư trái với chủ ý của bạn, tệ hại hơn nữa là khi bạn ký một hợp đồng, gửi thơng qua mạng và lại bị kẻ xấu sửa đổi những điều khoản trong đĩ, và sẽ cịn nhiều điều tương tự như vậy nữa Hậu quả sẽ như thế nào nhỉ ? Bạn bị người khác hiểu nhầm vì nội dung bức thư bị thay đổi, cịn hợp đồng bị phá vỡ bởi những điều khoản đã khơng cịn nguyên vẹn. Như vậy là cả tình cảm, tiền bạc của bạn và nĩi rộng hơn là cả sự nghiệp của bạn đều bị đe dọa nếu như những thơng tin mà bạn gửi đi khơng đảm bảo được tính nguyên vẹn của chúng. Mã hố thơng tin là một trong các phương pháp đảm bảo 3 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin được tính trong suốt của thơng tin. Nĩ cĩ thể giải quyết các vấn rắc rối ở trên giúp bạn, một khi thơng tin đã được mã hố và gửi đi thì kẻ xấu rất khĩ hoặc khơng thể giải mã được. Một số khái niệm cơ bản về mã hố thơng tin, phương pháp mã hố thơng tin RSA và xây dựng một thư viện các hàm mã hố phục vụ trao đổi thơng tin trong mơ hình Client/Server. Chương I Cơ sở tốn học Chương II Mật mã Chương III Hệ mã hố RSA. Chương IV Mơ hình Client/Server Chương V Xây dựng hàm thư viện 4 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Chương i Cơ sở tốn học Để cĩ những thuật tốn mã hố tốt, chúng ta phải cĩ những kiến thức cơ bản về tốn học đáp ứng cho yêu cầu, chương này mơ tả những khái niệm cơ bản về lý thuyết thơng tin như Entropy, tốc độ của ngơn ngữ, hiểu biết về độ phức tạp của thuật tốn, độ an tồn của thuật tốn, cùng với những kiến thức tốn học: modulo số học, số nguyên tố, định lý phần dư trung hoa, định lý Fermat . . . và các phương pháp kiểm tra xem một số cĩ phải là nguyên tố hay khơng. Những vấn đề chính sẽ được trình bày trong chương này gồm :  Lý thuyết thơng tin  Lý thuyết độ phức tạp  Lý thuyết số học. 1.Lý thuyết thơng tin Mơ hình lý thuyết thơng tin được định nghĩa lần đầu tiên vào năm 1948 bởi Claude Elmwood Shannon. Trong phần này chúng ta chỉ đề cập tới một số chủ đề quan trọng của lý thuyết thơng tin. 1.1 Entropy Lý thuyết thơng tin được định nghĩa là khối lượng thơng tin trong một thơng báo như là số bít nhỏ nhất cần thiết để mã hố tất cả những nghĩa cĩ thể của thơng báo đĩ. Ví dụ, trường ngay_thang trong một cơ sở dữ liệu chứa khơng quá 3 bít thơng tin, bởi vì thơng tin tại đây cĩ thể mã hố với 3 bít. 000 = Sunday 001 = Monday 010 = Tuesday 011 = Wednesday 5 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 100 = Thursday 101 = Friday 110 = Saturday 111 is unused Nếu thơng tin này được biểu diễn bởi chuỗi ký tự ASCII tương ứng, nĩ sẽ chiếm nhiều khơng gian nhớ hơn, nhưng cũng khơng chứa nhiều thơng tin hơn. Tương tự như trường gioi_tinh của một cơ sở dữ liệu chứa chỉ 1 bít thơng tin, nĩ cĩ thể lưu trữ như một trong hai xâu ký tự ASCII : Nam, Nữ. Khối lượng thơng tin trong một thơng báo M là đo bởi Entropy của thơng báo đĩ, ký hiệu bởi H(M). Entropy của thơng báo gioi_tinh chỉ ra là 1 bít, ký hiệu H(gioi_tinh) = 1, Entropy của thơng báo số ngày trong tuần là nhỏ hơn 3bits. Trong trường hợp tổng quát, Entropy của một thơng báo là log 2n, với n là số khả năng cĩ thể. H(M) = log2n 1.2 Tốc độ của ngơn ngữ. (Rate of Language) Đối với một ngơn ngữ, tốc độ của ngơn ngữ là r = H(M)/N trong trường hợp này N là độ dài của thơng báo. Tốc độ của tiếng Anh bình thường cĩ một vài giá trị giữa 1.0 bits/chữ cái và 1.5 bits/chữ cái, áp dụng với giá trị N rất lớn. Tốc độ tuyệt đối của ngơn ngữ là số bits lớn nhất, chúng cĩ thể mã hố trong mỗi ký tự. Nếu cĩ L ký tự trong một ngơn ngữ, thì tốc độ tuyệt đối là : R = log2L 6 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Đây là số Entropy lớn nhất của mỗi ký tự đơn lẻ. Đối với tiếng Anh gồm 26 chữ cái, tốc độ tuyệt đối là log 226 = 4.7bits/chữ cái. Sẽ khơng cĩ điều gì là ngạc nhiên đối với tất cả mọi người rằng thực tế tốc độ của tiếng Anh nhỏ hơn nhiều so với tốc độ tuyệt đối. 1.3 An tồn của hệ thống mã hố Shannon định nghĩa rất rõ ràng, tỉ mỉ các mơ hình tốn học, điều đĩ cĩ nghĩa là hệ thống mã hố là an tồn. Mục đích của người phân tích là phát hiện ra khố k, bản rõ p, hoặc cả hai thứ đĩ. Hơn nữa họ cĩ thể hài lịng với một vài thơng tin cĩ khả năng về bản rõ p nếu đĩ là âm thanh số, nếu nĩ là văn bản tiếng Đức, nếu nĩ là bảng tính dữ liệu, v. v . . . Trong hầu hết các lần phân tích mã, người phân tích cĩ một vài thơng tin cĩ khả năng về bản rõ p trước khi bắt đầu phân tích. Họ cĩ thể biết ngơn ngữ đã được mã hố. Ngơn ngữ này chắc chắn cĩ sự dư thừa kết hợp với chính ngơn ngữ đĩ. Nếu nĩ là một thơng báo gửi tới Bob, nĩ cĩ thể bắt đầu với "Dear Bob". Chắc chắn là "Dear Bob " sẽ là một khả năng cĩ thể hơn là chuỗi khơng mang ý nghĩa gì chẳng hạn "tm*h&rf". Mục đích của việc thám mã là sửa những tập hợp khả năng cĩ thể cĩ của bản mã với mỗi khả năng cĩ thể của bản rõ. Cĩ một điều giống như hệ thống mã hố, chúng đạt được sự bí mật tuyệt đối. Hệ thống mã hố này trong đĩ bản mã khơng mang lại thơng tin cĩ thể để tìm lại bản rõ. Shannon phát triển lý thuyết cho rằng, hệ thống mã hố chỉ an tồn tuyệt đối nếu nếu số khố cĩ thể ít nhất là nhiều bằng số thơng báo cĩ thể. Hiểu theo một nghĩa khác, khố tối thiểu dài bằng thơng báo của chính nĩ. Ngoại trừ an tồn tuyệt đối, bản mã mang lại một vài thơng tin đúng với bản rõ, điều này là khơng thể tránh được. Một thuật tốn mật mã tốt giữ 7 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin cho thơng tin ở mức nhỏ nhất, một người thám mã tốt khai thác những thơng tin này để phát hiện ra bản rõ. Người phân tích mã sử dụng sự dư thừa tự nhiên của ngơn ngữ để làm giảm số khả năng cĩ thể của bản rõ. Nhiều thơng tin dư thừa của ngơn ngữ, sẽ dễ dàng hơn cho sự phân tích mật mã. Chính vì lý do này mà nhiều sự thực hiện mã hố sử dụng chương trình nén bản rõ để giảm kích thước văn bản trước khi mã hố chúng. Bởi vậy quá trình nén làm giảm sự dư thừa của thơng báo. Entropy của hệ thống mã hố là đo kích thước của khơng gian khố (keyspace). H(K) = log2(number of keys ) 1.4 Sự lộn xộn và sự rườm rà. (Confusion and Diffusion) Theo nhà khoa học Shannon, cĩ hai kỹ thuật cơ bản để che dấu sự dư thừa thơng tin trong thơng báo gốc đĩ là : sự lộn xộn và sự rườm rà. Kỹ thuật lộn xộn (Confusion) che dấu mối quan hệ giữa bản rõ và bản gốc. Kỹ thuật này làm thất bại sự cố gắng nghiên cứu bản mã tìm kiếm thơng tin dư thừa và thống kê mẫu. Phương pháp dễ nhất để thực hiện điều này là thơng qua kỹ thuật thay thế. Một hệ mã hố thay thế đơn giản, chẳng hạn hệ mã dịch vịng Caesar, dựa trên nền tảng của sự thay thế các chữ cái, nghĩa là chữ cái này được thay thế bằng chữ cái khác. Sự tồn tại của một chữ cái trong bản mã, là do việc dịch chuyển đi k vị trí của chữ cái trong bản rõ. Kỹ thuật rườm rà (Diffusion) làm mất đi sự dư thừa của bản rõ bằng bề rộng của nĩ vượt quá bản mã (nghĩa là bản mã kích thước nhỏ hơn bản rõ). Một người phân tích tìm kiếm sự dư thừa đĩ sẽ cĩ một thời gian rất khĩ khăn để tìm ra chúng. Cách đơn giản nhất tạo ra sự rườm rà là thơng qua việc đổi chỗ (hay cịn gọi là hốn vị). 8 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 2.Lý thuyết độ phức tạp. Lý thuyết độ phức tạp cung cấp một phương pháp để phân tích độ phức tạp tính tốn của thuật tốn và các kỹ thuật mã hố khác nhau. Nĩ so sánh các thuật tốn mã hố, kỹ thuật và phát hiện ra độ an tồn của các thuật tốn đĩ. Lý thuyết thơng tin đã cho chúng ta biết rằng một thuật tốn mã hố cĩ thể bị bại lộ. Cịn lý thuyết độ phức tạp cho biết nếu liệu chúng cĩ thể bị bại lộ trước khi vũ trụ xụp đổ hay khơng. Độ phức tạp thời gian của thuật tốn là hàm số với độ dài đầu vào. Thuật tốn cĩ độ phức tạp thời gian f(n) đối với mọi n và độ dài đầu vào n, nghĩa là sự thực hiện của thuật tốn lớn hơn f(n) bước. Độ phức tạp thời gian thuật tốn phụ thuộc vào mơ hình của các thuật tốn, số các bước nhỏ hơn nếu các hoạt động được tập chung nhiều trong một bước. Các lớp của thuật tốn, thời gian chạy được chỉ rõ như hàm số mũ của đầu vào là "khơng cĩ khả năng thực hiện được". Các thuật tốn cĩ độ phức tạp giống nhau được phân loại vào trong các lớp tương đương. Ví dụ tất cả các thuật tốn cĩ độ phức tạp là n 3 được phân vào trong lớp n3 và ký hiệu bởi O(n3). Cĩ hai lớp tổng quát sẽ được chỉ dẫn là lớp P và lớp NP. Các thuật tốn thuộc lớp P cĩ độ phức tạp là hàm đa thức của đầu vào. Nếu mỗi bước tiếp theo của thuật tốn là duy nhất thì thuật tốn gọi là đơn định. Tất cả thuật tốn thuộc lớp P đơn định cĩ thời gian giới hạn là P_time, điều này cho biết chúng sẽ thực hiện trong thời gian đa thức, tương đương với độ phức tạp đa thức trong độ dài đầu vào. Thuật tốn mà ở bước tiếp theo sự tính tốn phải lựa chọn giải pháp từ những giới hạn giá trị của hoạt động gọi là khơng đơn định. Lý thuyết độ phức tạp sử dụng các máy đặc biệt mơ tả đặc điểm bằng cách đưa ra kết 9 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin luận bởi các chuẩn. Máy Turinglà một máy đặc biệt, máy hoạt động trong thời gian rời rạc, tại một thời điểm nĩ nằm trong khoảng trạng thái đầy đủ số của tất cả các trạng thái cĩ thể là hữu hạn. Chúng ta cĩ thể định nghĩa hàm độ phức tạp thời gian kết hợp với máy Turing A. 3 fA(n) = max{m/A kết thúc sau m bước với đầu vào w = n } Chúng ta giả sử rằng A là trạng thái kết thúc đối với tất cả các đầu vào, vấn đề sẽ trở nên khĩ khăn hơn nếu các trạng thái khơng nằm trong P . Máy Turing khơng đơn định hoạt động trong thuật tốn NP. Máy Turing khơng đơn định cĩ thể cĩ một vài trạng thái chính xác. S(w) là trạng thái đo sự thành cơng ngắn nhất của thuật tốn, (Nghĩa là sự tính tốn dẫn đến trạng thái cuối cùng) Hàm số độ phức tạp thời gian của máy Turing khơng đơn định A được định nghĩa : fA(n)=max{1,m/s(w) cĩ m bước đối với w/w=n}, ở mỗi bước máy Turing khơng đơn định bố trí nhiều bản sao của chính nĩ như cĩ một vài giải pháp và tính tốn độc lập với mọi lời giải. Các thuật tốn thuộc lớp NP là khơng đơn định và cĩ thể tính tốn trên máy Turing khơng đơn định trong thời gian P. 3.Lý thuyết tốn học. 3.1 Modular số học. Về cơ bản a  b(mod n) nếu a = b+kn trong đĩ k là một số nguyên. Nếu a và b dương và a nhỏ hơn n, bạn cĩ thể nghĩ rằng a là phần dư của b khi chia cho n. Nĩi chung a và b đều là phần dư khi chia cho n. Đơi khi b gọi là thặng dư của a, modulo n, đơi khi a gọi là đồng dư của b, modulo n. 10 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Tập hợp các số nguyên từ 0 đến n-1 cịn được gọi là tập hợp thặng dư hồn tồn modulo n. Điều này cĩ nghĩa là, với mỗi số nguyên a, thì thặng dư modulo n là một số từ 0 đến n-1. Modulo số học cũng giống như số học bình thường, bao gồm các phép giao hốn, kết hợp và phân phối. Mặt khác giảm mỗi giá trị trung gian trong suốt quá trình tính tốn. (a+b) mod n = ((a mod n) + (b mod n)) mod n (a- b) mod n = ((a mod n) - (b mod n)) mod n (a b) mod n = ((a mod n) (b mod n)) mod n (a (b + c)) mod n = (((a b) mod n) + ((a c) mod n)) mod n Hệ thống mã hố sự dụng nhiều sự tính tốn modulo n, bởi vì vấn đề này giống như tính tốn logarithm rời rạc và diện tích hình vuơng là khĩ khăn. Mặt khác nĩ làm việc dễ hơn, bởi vì nĩ bị giới hạn trong tất cả giá trị trung gian và kết quả. Ví dụ : a là một số k bits, n là kết quả trung gian của phép cộng, trừ, nhân sẽ khơng vượt quá 24 bits. Như vậy chúng ta cĩ thể thực hiện hàm mũ trong modulo số học mà khơng cần sinh ra kết quả trung gian đồ sộ. 3.2 Số nguyên tố. Số nguyên tố là một số lớn hơn 1, nhưng chỉ chia hết cho 1 và chính nĩ, ngồi ra khơng cịn số nào nĩ cĩ thể chia hết nữa. Số 2 là một số nguyên tố. Do vậy 7, 17, 53, 73, 2521, 2365347734339 cũng là số nguyên tố. Số lượng số nguyên tố là vơ tận. Hệ mật mã thường sử dụng số nguyên tố lớn cỡ 512 bits và thậm chí lớn hơn như vậy. 11 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 3.3 Ước số chung lớn nhất. Hai số gọi là cặp số nguyên tố khi mà chúng khơng cĩ thừa số chung nào khác 1, hay nĩi một cách khác, nếu ước số chung lớn nhất của a và n là bằng 1. Chúng ta cĩ thể viết như sau : gcd(a,n)=1 Số 15 và 28 là một cặp số nguyên tố, nhưng 15 và 27 thì khơng phải cặp số nguyên tố do cĩ ước số chung là 1 và 3, dễ dàng thấy 13 và 500 cũng là một cặp số nguyên tố. Một số nguyên tố là một cặp số nguyên tố với tất cả những số khác loại trừ những số là bội số. Một cách dễ nhất để tính tốn ra ước số chung lớn nhất của hai số là nhờ vào thuật tốn Euclid. Knuth mơ tả thuật tốn và một vài mơ hình của thuật tốn đã được sửa đổi. Dưới đây là đoạn mã nguồn trong ngơn ngữ C. /* Thuật tốn tìm ước số chung lớn nhất của x và y, giả sử x,y>0 */ int gcd(int x, int y) { int g; if(x 0){ g=x; x=y%x; y=g; } return g; } 12 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Thuật tốn sau đây cĩ thể sinh ra và trả lại ước số chung lớn nhất của một mảng m số. int multiple gcd ( int m, int *x) { size t, i ; int g; if(m<1) return(0); g = x[0]; for(i=1;i<m;++i){ g=gcd(g,x[i]); if(g==1) return 1; } return g; } 3.4 Số nghịch đảo Modulo. Số nghịch đảo của 10 là 1/10, bởi vì 10 1/10=1. Trong số học modulo thì vấn đề nghịch đảo phức tạp hơn. 4 x  1 mod 7 Phương trình trên tương đương với tìm x và k sao cho 4x = 7k+1 với điều kiện là cả x và k đều là số nguyên. Vấn đề chung đặt ra tại đây là tìm x sao cho 1 = (a x) mod n cĩ thể viết lại như sau : a-1  x(mod n ) 13 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Sự thu nhỏ vấn đề Modulo là rất khĩ giải quyết. Đơi khi nĩ là một vấn đề, nhưng đơi khi lại khơng phải vậy. Ví dụ : nghịch đảo của 5 modulo 14 là 3 bởi 5 3 = 15  1 (mod 14). Trong trường hợp chung a -1  x (mod n) chỉ cĩ duy nhất một giải pháp nếu a và n là một cặp số nguyên tố. Nếu a và n khơng phải là cặp số nguyên tố, thì a-1  x (mod n) khơng cĩ giải pháp nào. Thuật tốn Euclid cĩ thể tính ra được số nghịch đảo của số Modulo n, đơi khi thuật tốn này cịn gọi là thuật tốn Euclid mở rộng. Sau đây thuật tốn được mơ tả trong ngơn ngữ C. static void Update(int *un,int *vn, int q) { int tn; tn = *un-vn*q; *un = *vn; *vn = tn; } int extended euclidian(int u,int v,int u1_out,int u2_out) { int u1=1; int u3=u; int v1=0; int v3=v; int q; while(v3>0){ q=u3/v3; 14 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Update(&u1,&v1,q); Update(&u3,&v,q); } *u1_out=u1; *u2_out=(u3-u1*u)/v; return u3; } 3.5 Ký hiệu La grăng (Legendre Symboy) Ký hiệu L(a,p) được định nghĩa khi a là một số nguyên và p là một số nguyên tố lớn hơn 2. Nĩ nhận ba giá trị 0, 1, -1 : L(a,p) = 0 nếu a chia hết cho p. L(a,p) = 1 nếu a là thặng dư bậc 2 mod p. L(a,p) = -1 nếu a khơng thặng dư mod p. Một phương pháp dễ dàng để tính tốn ra L(a,p) là : L(a,p) = a (p-1)/2 mod p 3.6 Ký hiệu Jacobi (Jacobi Symboy) Ký hiệu Jacobi được viết J(a,n), nĩ là sự khái quát hố của ký hiệu Lagrăng, nĩ định nghĩa cho bất kỳ cặp số nguyên a và n. Ký hiệu Jacobi là một chức năng trên tập hợp số thặng dư thấp của ước số n và cĩ thể tính tốn theo cơng thức sau: Nếu n là số nguyên tố, thì J(a,n) = 1 với điều kiện a là thặng dư bậc hai modulo n . Nếu n là số nguyên tố, thì J(a,n) = -1 với điều kiện a khơng là thặng dư bậc hai modulo n . Nếu n khơng phải là số nguyên tố thì Jacobi J(a,n)=J(h,p1) J(h,p2) . . . J(h,pm) 15 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin với p1,p2. . .,pm là các thừa số lớn nhất của n. Thuật tốn này tính ra số Jacobi tuần hồn theo cơng thức sau : 1. J(1,k) = 1 2. J(a b,k) = J(a,k) J(b,k) 3. J(2,k) =1 Nếu (k2-1)/8 là chia hết J(2,k) =-1 trong các trường hợp khác. 4. J(b,a) = J((b mod a),a) 5. Nếu GCD(a,b)=1 : a. J(a,b) J(b,a) = 1 nếu (a-1)(b-1)/4 là chia hết. b. J(a,b) J(b,a) = -1 nếu (a-1)(b-1)/4 là cịn dư. Sau đây là thuật tốn trong ngơn ngữ C : int jacobi(int a,int b) { int a1,a2; if(a>=b) a%=b; if(a==0) return 0; if(a==1) return 1; if(a==2) if(((b*b-1)/8)%2==0) return 1; else return -1; if(a&b&1) (cả a và b đều là số dư) if(((a-1)*(b-1)/4)%2==0) return +jacobi(b,a); 16 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin else return -jacobi(b,a); if(gcd(a,b)==1) if(((a-1)*(b-1)/4)%2==0) return +jacobi(b,a); else return -jacobi(b,a); factor2(a,&a1,&a2); return jacobi(a1,b) * jacobi(a2,b); } Nếu p là số nguyên tố cĩ cách tốt hơn để tính số Jacobi như dưới đây : 1. Nếu a=1 thì J(a/p)=1 2. Nếu a là số chai hết, thì J(a,p)=J(a/2,p) (-1)(p^2 –1)/8 3. Nếu a là số dư khác 1 thì J(a,p)=J(p mod a, a) (-1)(a-1) (p-1)/4 3.7 Định lý phần dư trung hoa. Nếu bạn biết cách tìm thừa số nguyên tố của một số n, thì bạn cĩ thể đã sử dụng, một số điều gọi là định lý phần dư trung hoa để giải quyết trong suốt hệ phương trình. Bản dịch cơ bản của đinh lý này được khám phá bởi tốn học Trung Hoa vào thế kỷ thứ nhất. Giả sử, sự phân tích thừa số của n=p1 p2 . . . pt thì hệ phương trình (X mod pi) = ai , với i=1,2,. . .t cĩ duy nhất một cách giải, tại đĩ x nhỏ hơn n. Bởi vậy, với a,b tuỳ ý sao cho a < p và b < q (p,q là số nguyên tố) thì tồn tại duy nhất a,x ,khi x nhỏ hơn p q thì x  a (mod p), và x  b (mod q) Để tìm ra x đầu tiên sử dụng thuật tốn Euclid để tìm u, ví dụ : u q  1 (mod p) Khi đĩ cần tính tốn : 17 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin x=((( a-b) u) mod p ) q + b Dưới đây là đoạn mã định lý phần dư trung hoa trong ngơn ngữ C : Int chinese remainder(size t r, int *m, int *u) { size t i; int modulus; int n; modulus = 1; for ( i=0; i<r:++i ) modulus *=m[i]; n=0; for ( i=0; i<r:++i ) { n+=u[i]*modexp(modulus/m[i],totient(m[i]),m[i]); n%=modulus; } return n; } 3.8 Định lý Fermat. Nếu m là số nguyên tố, và a khơng phải là bội số của m thì định lý Fermat phát biểu : am-1  1(mod m) 4. Các phép kiểm tra số nguyên tố. Hàm một phía là một khái niệm cơ bản của mã hố cơng khai, việc nhân hai số nguyên tố được phỏng đốn như là hàm một phía, nĩ rất dễ dàng nhân các số để tạo ra một số lớn, nhưng rất khĩ khăn để phân tích số lớn đĩ ra thành các thừa số là hai số nguyên tố lớn. 18 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Thuật tốn mã hố cơng khai cần thiết tới những số nguyên tố. Bất kỳ mạng kích thước thế nào cũng cần một số lượng lớn số nguyên tố. Cĩ một vài phương pháp để sinh ra số nguyên tố. Tuy nhiên cĩ một số vấn đề được đặt ra đối với số nguyên tố như sau : Nếu mọi người cần đến những số nguyên tố khác nhau, chúng ta sẽ khơng đạt được điều đĩ đúng khơng. Khơng đúng, bởi vì trong thực tế cĩ tới 10150 số nguyên tố cĩ độ dài 512 bits hoặc nhỏ hơn. Điều gì sẽ xảy ra nếu cĩ hai người ngẫu nhiên chọn cùng một số nguyên tố?. Với sự chọn lựa từ số lượng 10 150 số nguyên tố, điều kỳ quặc này xảy ra là xác xuất nhỏ hơn so với sự tự bốc cháy của máy tính. Vậy nĩ khơng cĩ gì là đáng lo ngại cho bạn hết. 4.1 Soloway-Strassen Soloway và Strassen đã phát triển thuật tốn cĩ thể kiểm tra số nguyên tố. Thuật tốn này sử dụng hàm Jacobi. Thuật tốn kiểm tra số p là số nguyên tố : 1. Chọn ngẫu nhiên một số a nhỏ hơn p. 2. Nếu ước số chung lớn nhất gcd(a,p) 1 thì p là hợp số. 3. Tính j = a(p-1)/2 mod p. 4. Tính số Jacobi J(a,p). 5. Nếu j J(a,p), thì p khơng phải là số nguyên tố. 6. Nếu j = J(a,p) thì nĩi p cĩ thể là số nguyên tố với chắc chắn 50%. Lặp lại các bước này n lần, với những n là giá trị ngẫu nhiên khác nhau của a. Phần dư của hợp số với n phép thử là khơng quá 2n. Thực tế khi thực hiện chương trình, thuật tốn chạy với tốc độ nhanh. 19 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 4.2 Rabin-Miller Thuật tốn này được phát triển bởi Rabin, dựa trên một phần ý tưởng của Miller. Thực tế những phiên bản của thuật tốn đã được giới thiệu tại NIST. (National Institute of Standards and Technology). Đầu tiên là chọn ngẫu nhiên một số p để kiểm tra. Tính b, với b là số mũ của 2 chia cho p-1. Tiếp theo tính m tương tự như n = 1+2bm. Sau đây là thuật tốn : 1. Chọn một sơ ngẫu nhiên a, và giả sử a nhỏ hơn p. 2. Đặt j=0 và z=am mod p. 3. Nếu z=1, hoặc z=p-1 thì p đã qua bước kiểm tra và cĩ thể là số nguyên tố. 4. Nếu j > 0 và z=1 thì p khơng phải là số nguyên tố. 5. Đặt j = j+1. Nếu j < b và z p-1 thì đặt z=z 2 mod p và trở lại bước 4. 6. Nếu j = b và z p-1, thì p khơng phải là số nguyên tố. 4.3 Lehmann. Một phương pháp đơn giản hơn kiểm tra số nguyên tố được phát triển độc lập bởi Lehmann. Sau đây là thuật tốn với số bước lặp là 100. 1. Chọn ngẫu nhiên một số n để kiểm tra. 2. Chắc chắn rằng n khơng chia hết cho các số nguyên tố nhỏ như 2,3,5,7 và 11. 3. Chọn ngẫu nhiên 100 số a1, a2, . . . , a100 giữa 1 và n-1. (n-1)/2 4. Tính ai (mod n) cho tất cả ai = a1. . . a100 . Dừng lại nếu bạn tìm thấy ai sao cho phép kiểm tra là sai. 5. Nếu ai(n-1)/2 = 1 (mod n) với mọi i, thì n cĩ thể là hợp số. Nếu ai(n-1)/2 1 hoặc -1 (mod n) với i bất kỳ, thì n là hợp số. 20 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Nếu ai(n-1)/2 = 1 hoặc -1 (mod n) với mọi i 1, thì n là số nguyên tố. 4.4 Strong Primes. Strong Primes thường được sử dụng cho hai số p và q, chúng là hai số nguyên tố với các thuộc tính chắc chắn rằng cĩ thể tìm được thừa số bằng phương pháp phân tích thừa số. Trong số các thuộc tính đạt được bao gồm + Ước số chung lớn nhất của p-1 và q-1 là nhỏ. + Hai số p-1 và q-1 nên cĩ thừa số nguyên tố lớn, đạo hàm riêng p' và q' + Hai số p'-1 và q'-1 nên cĩ thừa số nguyên tố lớn, đạo hàm riêng p'' và q'' + Cả (p-1)/2 và (q-1)/2 nên là số nguyên tố. Trong bất cứ trường hợp nào Strong Primes rất cần thiết là đối tượng trong các buổi tranh luận. Những thuộc tính đã được thiết kế cản trở một vài thuật tốn phân tích thừa số. Hơn nữa, những thuật tốn phân tích thừa số nhanh nhất cĩ cơ hội tốt để đạt các tiêu chuẩn. 21 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Chương II Mật mã Trong chương trước chúng ta đã nêu ra các khái niệm cơ bản về lý thuyết thơng tin, về độ phức tạp của thuật tốn, và những khái niệm cơ bản về tốn học cần thiết. Chương này sẽ mơ tả một cách tổng quan về mã hố, bao gồm những khái niệm về mã hố thơng tin, một hệ thống mã hố bao gồm những thành phần nào, khái niệm protocol, các loại protocol. Mã hố dịng là gì, mã hố khối là gì, thế nào là hệ thống mã hố cổ điển, thế nào là hệ thống mã hố cơng khai. Và cuối cùng là bằng những cách nào kẻ địch tấn cơng hệ thống mã hố. Những vấn đề sẽ được đề cập trong chương này:  Khái niệm cơ bản của mã hố.  Protocol  Mã dịng , mã khối (CFB, CBC)  Các hệ mật mã đối xứng và cơng khai  Các cách thám mã 1. Khái niệm cơ bản. -Bản rõ (plaintext or cleartext) Chứa các xâu ký tự gốc, thơng tin trong bản rõ là thơng tin cần mã hố để giữ bí mật. -Bản mã (ciphertext) Chứa các ký tự sau khi đã được mã hố, mà nội dung được giữ bí mật. -Mật mã học (Crytography) Là nghệ thuật và khoa học để giữ thơng tin được an tồn. -Sự mã hố (Encryption) Quá trình che dấu thơng tin bằng phương pháp nào đĩ để làm ẩn nội dung bên trong gọi là sự mã hố. 22 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin -Sự giải mã (Decryption) Quá trình biến đổi trả lại bản mã bản thành bản rõ gọi là giải mã. Quá trình mã hố và giải mã được thể hiện trong sơ đồ sau: Bản rõ Bản Bản rõ Mã hố mã Giải mã gảc -Hệ mật mã : là một hệ bao gồm 5 thành phần (P, C, K, E, D) thoả mãn các tính chất sau P (Plaintext) là tập hợp hữu hạn các bản rõ cĩ thể. C (Ciphertext) là tập hợp hữu hạn các bản mã cĩ thể. K (Key) là tập hợp các bản khố cĩ thể. E (Encrytion) là tập hợp các qui tắc mã hố cĩ thể. D (Decrytion) là tập hợp các qui tắc giải mã cĩ thể. Chúng ta đã biết một thơng báo thường được tổ chức dưới dạng bản rõ. Người gửi sẽ làm nhiệm vụ mã hố bản rõ, kết quả thu được gọi là bản mã. Bản mã này được gửi đi trên một đường truyền tới người nhận sau khi nhận được bản mã người nhận giải mã nĩ để tìm hiểu nội dung. Dễ dàng thấy được cơng việc trên khi sử dụng định nghĩa hệ mật mã : EK( P) = C và DK( C ) = P 23 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 2. Protocol 2.1 Giới thiệu Protocol Trong suốt cả quá trình của hệ thống mật mã là giải quyết các vấn đề, những vấn đề của hệ bao gồm: giải quyết cơng việc xung quanh sự bí mật, tính khơng tin cậy và những kẻ bất lương. Bạn cĩ thể học mọi điều về thuật tốn cũng như các kỹ thuật, nhưng cĩ một điều rất đáng quan tâm đĩ là Protocol. Protocol là một loạt các bước, bao gồm hai hoặc nhiều người, thiết kế để hồn thành nhiệm vụ . “Một loạt các bước” nghĩa là Protocol thực hiện theo một tuần tự, từ khi bắt đầu cho tới lúc kết thúc. Mỗi bước phải được thực hiện tuần tự và khơng cĩ bước nào được thực hiện trước khi bước trước đĩ đã hồn thành. “Bao gồm hai hay nhiều người” nghĩa là cần ít nhất hai người hồn thành protocol, một người khơng thể tạo ra được một Protocol. Và chắc chắn rằng một người cĩ thể thực hiện một loạt các bước để hồn thành nhiệm vụ, nhưng đĩ khơng phải là Protocol. Cuối cùng “thiết kế để hồn thành nhiệm vụ” nghĩa là mỗi Protocol phải làm một vài điều gì đĩ. Protocol cĩ một vài thuộc tính khác như sau : 1. Mọi người cần phải trong một Protocol, phải biết protocol đĩ và tuân theo tất cả mọi bước trong sự phát triển. 2. Mọi người cần phải trong một Protocol, và phải đồng ý tuân theo nĩ. 3. Một Protocol phải rõ ràng, mỗi bước phải được định nghĩa tốt và phải khơng cĩ cơ hội hiểu nhầm. 4. Protocol phải được hồn thành, phải cĩ những hành động chỉ rõ cho mỗi trường hợp cĩ thể. 24 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 2.2 Protocol mật mã. Protocol mật mã là protocol sử dụng cho hệ thống mật mã. Một nhĩm cĩ thể gồm những người bạn bè và những người hồn tồn tin cậy khác hoặc họ cĩ thể là địch thủ hoặc những người khơng tin cậy một chút nào hết. Một điều hiển nhiên là protocol mã hố phải bao gồm một số thuật tốn mã hố, nhưng mục đích chung của protocol là một điều gì đĩ xa hơn là điều bí mật đơn giản. 2.3 Mục đích của Protocol. Trong cuộc sống hàng ngày, cĩ rất nhiều nghi thức thân mật cho hầu hết tất cả mọi điều như gọi điện thoại, chơi bài, bầu cử. Khơng cĩ gì trong số chúng lại khơng cĩ protocol, chúng tiến triển theo thời gian, mọi người đều biết sử dụng chúng như thế nào và làm việc với chúng. Hơn nữa bây giờ mọi người giao tiếp với nhau qua mạng máy tính thay cho sự gặp mặt thơng thường. Máy tính cần thiết một nghi thức chuẩn để làm những việc giống nhau như con người khơng phải suy nghĩ. Nếu bạn đi từ một địa điểm này tới địa điểm khác, thậm chí từ quốc gia này tới quốc gia khác, bạn thấy một trạm điện thoại cơng cộng khác hồn tồn so với cái bạn đã sử dụng, bạn dễ dàng đáp ứng. Nhưng máy tính thì khơng mềm dẻo như vậy. Thật ngây thơ khi bạn tin rằng mọi người trên mạng máy tính là chân thật, và cũng thật ngây thơ khi tin tưởng rằng người quản trị mạng, người thiết kế mạng là chân thật. Hầu hết sẽ là chân thật, nhưng nĩ sẽ là khơng chân khi bạn cần đến sự an tồn tiếp theo. Bằng những protocol chính thức, chúng ta cĩ thể nghiên cứu những cách mà những kẻ khơng trung thực cĩ thể lừa đảo và phát triển protocol để đánh bại những kẻ lừa đảo đĩ. Protocol rất hữa ích bởi vì họ trừu tượng hố tiến trình hồn thành nhiệm vụ từ kỹ thuật, như vậy nhiệm vụ đã được hồn thành. 25 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Sự giao tiếp giữa hai máy tính giống như một máy tính là IBM PC, máy kia là VAX hoặc loại máy tương tự. Khái niệm trừu tượng này cho phép chúng ta nghiên cứu những đặc tính tốt của protocol mà khơng bị xa lầy vào sự thực hiện chi tiết. Khi chúng ta tin rằng chúng ta cĩ một protocol tốt, thì chúng ta cĩ thể thực hiện nĩ trong mọi điều từ một máy tính đến điện thoại, hay đến một lị nướng bánh thơng minh. 2.4 Truyền thơng sử dụng hệ mật mã đối xứng. Hai máy thực hiện việc truyền thơng an tồn như thế nào ? Chúng sẽ mã hố sự truyền thơng đĩ, đương nhiên rồi. Để hồn thành một protocol là phức tạp hơn việc truyền thơng. Chúng ta hãy cùng xem xét điều gì sẽ xảy ra nếu máy Client muốn gửi thơng báo mã hố tới cho Server. 1. Client và Server đồng ý sử dụng một hệ mã hĩa. 2. Client và Server thống nhất khố với nhau. 3. Client lấy bản rõ và mã hố sử dụng thuật tốn mã hố và khố. Sau đĩ bản mã đã được tạo ra. 4. Client gửi bản mã tới cho Server. 5. Server giải mã bản mã đĩ với cùng một thuật tốn và khố, sau đĩ đọc được bản rõ. Điều gì sẽ xảy ra đối với kẻ nghe trộm cuộc truyền thơng giữa Client và Server trong protocol trên. Nếu như kẻ nghe trộm chỉ nghe được sự truyền đi bản mã trong bước 4, chúng sẽ cố gắng phân tích bản mã. Những kẻ nghe trộm chúng khơng ngu rốt, chúng biết rằng nếu cĩ thể nghe trộm từ bước 1 đến bước 4 thì chắc chắn sẽ thành cơng. Chúng sẽ biết được thuật tốn và khố như vậy chúng sẽ biết được nhiều như Server. Khi mà thơng báo được truyền đi trên kênh truyền thơng trong bước thứ 4, thì kẻ nghe trộm sẽ giải mã bằng chính những điều đã biết. 26 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Đây là lý do tại sao quản lý khố lại là vấn đề quan trọng trong hệ thống mã hố. Một hệ thống mã hố tốt là mọi sự an tồn phụ thuộc vào khố và khơng phụ thuộc vào thuật tốn. Với thuật tốn đối xứng, Client và Server cĩ thể thực hiện bước 1 là cơng khai, nhưng phải thực hiện bước 2 bí mật. Khố phải được giữ bí mật trước, trong khi, và sau protocol, mặt khác thơng báo sẽ khơng giữ an tồn trong thời gian dài. Tĩm lại, hệ mật mã đối xứng cĩ một vài vấn đề như sau : Nếu khố bị tổn thương (do đánh cắp, dự đốn ra, khám phá, hối lộ) thì đối thủ là người cĩ khố, anh ta cĩ thể giải mã tất cả thơng báo với khố đĩ. Một điều rất quan trọng là thay đổi khố tuần tự để giảm thiểu vấn đề này. Những khố phải được thảo luận bí mật. Chúng cĩ thể cĩ giá trị hơn bất kỳ thơng báo nào đã được mã hố, từ sự hiểu biết về khố cĩ nghĩa là hiểu biết về thơng báo. Sử dụng khố riêng biệt cho mỗi cặp người dùng trên mạng vậy thì tổng số khố tăng lên rất nhanh giống như sự tăng lên của số người dùng. Điều này cĩ thể giải quyết bằng cách giữ số người dùng ở mức nhỏ, nhưng điều này khơng phải là luơn luơn cĩ thể. 2.5 Truyền thơng sử dụng hệ mật mã cơng khai.  Hàm một phía (one way function) Khái niệm hàm một phía là trung tâm của hệ mã hố cơng khai. Khơng cĩ một Protocol cho chính nĩ, hàm một phía là khối xây dựng cơ bản cho hầu hết các mơ tả protocol. Một hàm một phía là hàm mà dễ dàng tính tốn ra quan hệ một chiều nhưng rất khĩ để tính ngược lại. Ví như : 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 27 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin trường hợp này “khĩ” cĩ nghĩa là để tính ra được kết quả thì phải mất hàng triệu năm để tính tốn, thậm chí tất cả máy tính trên thế giới này đều tính tốn cơng việc đĩ. Vậy thì hàm một phía tốt ở những gì ? Chúng ta khơng thể sử dụng chúng cho sự mã hố. Một thơng báo mã hố với hàm một phía là khơng hữu ích, bất kỳ ai cũng khơng giải mã được. Đối với mã hố chúng ta cần một vài điều gọi là cửa sập hàm một phía. Cửa sập hàm một phía là một kiểu đặc biệt của hàm một phía với cửa sập bí mật. Nĩ dễ dàng tính tốn từ một điều kiện này nhưng khĩ khăn để tính tốn từ một điều kiện khác. Nhưng nếu bạn biết điều bí mật, bạn cĩ thể dễ dàng tính tốn ra hàm từ điều kiện khác. Ví dụ : tính f(x) dễ dàng từ x, rất khĩ khăn để tính tốn x ra f(x). Hơn nữa cĩ một vài thơng tin bí mật, y giống như f(x) và y nĩ cĩ thể tính tốn dễ dàng ra x. Như vậy vấn đề cĩ thể đã được giải quyết. Hộp thư là một ví dụ rất tuyệt về cửa sập hàm một phía. 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à khĩ khăn, bạn sẽ cần đến mỏ hàn để phá hoặc những cơng cụ khác. Hơn nữa nếu bạn cĩ điều bí mật (chìa khố), nĩ thật dễ dàng mở hộp thư. Hệ mã hố cơng khai cĩ rất nhiều điều giống như vậy.  Hàm băm một phía. Hàm băm một phía là một khối xây dựng khác cho nhiều loại protocol. Hàm băm một phía đã từng được sử dụng cho khoa học tính tốn trong một thời gian dài. Hàm băm là một hàm tốn học hoặc loại khác, nĩ lấy chuỗi đầu vào và chuyển đổi thành kích thước cố định cho chuỗi đầu ra. 28 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Hàm băm một phía là một hàm băm nĩ sử dụng hàm một phía. Nĩ rất dễ dàng tính tốn giá trị băm từ xâu ký tự vào, nhưng rất khĩ tính ra một chuỗi từ giá trị đơn lẻ đưa vào. Cĩ hai kiểu chính của hàm băm một phía, hàm băm với khố và khơng khố. Hàm băm một phía khơng khố cĩ thể tính tốn bởi mọi người giá trị băm là hàm chỉ cĩ đơn độc chuỗi đưa vào. Hàm băm một phía với khố là hàm cả hai thứ chuỗi vào và khố, chỉ một vài người cĩ khố mới cĩ thể tính tốn giá trị băm.  Hệ mã hố sử dụng khố cơng khai. Với những sự mơ tả ở trên cĩ thể nghĩ rằng thuật tốn đối xứng là an tồn. Khố là sự kết hợp, một vài người nào đĩ với sự kết hợp cĩ thể mở sự an tồn này, đưa thêm tài liệu vào, và đĩng nĩ lại. Một người nào đĩ khác với sự kết hợp cĩ thể mở được và lấy đi tài liệu đĩ. Năm 1976 Whitfied và Martin Hellman đã thay đổi vĩnh viễn mơ hình của hệ thống mã hố. Chúng được mơ tả là hệ mã hố sử dụng khố cơng khai. Thay cho một khố như trước, hệ bao gồm hai khố khác nhau, một khố là cơng khai và một khố kia là khố bí mật. Bất kỳ ai với khố cơng khai cũng cĩ thể mã hố thơng báo nhưng khơng thể giải mã nĩ. Chỉ một người với khố bí mật mới cĩ thể giải mã được. Trên cơ sở tốn học, tiến trình này phụ thuộc vào cửa sập hàm một phía đã được trình bày ở trên. Sự mã hố là chỉ thị dễ dàng. Lời chỉ dẫn cho sự mã hố là khố cơng khai, bất kỳ ai cũng cĩ thể mã hố. Sự giải mã là một chỉ thị khĩ khăn. Nĩ tạo ra khĩ khăn đủ để một người sử dụng máy tính Cray phải mất hàng ngàn năm mới cĩ thể giải mã. Sự bí mật hay cửa sập chính là khố riêng. Với sự bí mật, sự giải mã sẽ dễ dàng như sự mã hố. 29 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Chúng ta hãy cùng xem xét khi máy Client gửi thơng báo tới Server sử dụng hệ mã hố cơng khai. 1. Client và Server nhất trí sử dụng hệ mã hĩa cơng khai. 2. Server gửi cho Client khố cơng khai của Server. 3. Client lấy bản rõ và mã hố sử dụng khố cơng khai của Server. Sau đĩ gửi bản mã tới cho Server. 4. Server giải mã bản mã đĩ sử dụng khố riêng của mình. Chú ý rằng hệ thống mã hố cơng khai giải quyết vấn đề chính của hệ mã hố đối xứng, bằng cách phân phối khố. Với hệ thống mã hố đối xứng đã qui ước, Client và Server phải nhất trí với cùng một khố. Client cĩ thể chọn ngẫu nhiên một khố, nhưng nĩ vẫn phải thơng báo khố đĩ tới Server, điều này gây lãng phí thời gian. Đối với hệ thống mã hố cơng khai, thì đây khơng phải là vấn đề. 3. Khố 3.1 Độ dài khố. Độ an tồn của thuật tốn mã hố cổ điển phụ thuộc vào hai điều đĩ là độ dài của thuật tốn và độ dài của khố. Nhưng độ dài của khố dễ bị lộ hơn. Giả sử rằng độ dài của thuật tốn là lý tưởng, khĩ khăn lớn lao này cĩ thể đạt được trong thực hành. Hồn tồn cĩ nghĩa là khơng cĩ cách nào bẻ gãy được hệ thống mã hố trừ khi cố gắng thử với mỗi khố. Nếu khố dài 8 bits thì cĩ 28 = 256 khố cĩ thể. Nếu khố dài 56 bits, thì cĩ 256 khố cĩ thể. Giả sử rằng siêu máy tính cĩ thể thực hiện 1 triệu phép tính một giây, nĩ cũng sẽ cần tới 2000 năm để tìm ra khố thích hợp. Nếu khố dài 64 bits, thì với máy tính tương tự cũng cần tới xấp xỉ 600,000 năm để tìm ra khố trong số 2 64 khố cĩ thể. Nếu khố dài 128 bits, nĩ cần tới 10 25 30 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin năm , trong khi vũ trụ của chúng ta chỉ tồn tại cỡ 10 10 năm. Như vậy với 1025 năm cĩ thể là đủ dài. Trước khi bạn gửi đi phát minh hệ mã hố với 8 Kbyte độ dài khố, bạn nên nhớ rằng một nửa khác cũng khơng kém phần quan trọng đĩ là thuật tốn phải an tồn nghĩa là khơng cĩ cách nào bẻ gãy trừ khi tìm được khố thích hợp. Điều này khơng dễ dàng nhìn thấy được, hệ thống mã hố nĩ như một nghệ thuật huyền ảo. Một điểm quan trọng khác là độ an tồn của hệ thống mã hố nên phụ thuộc vào khố, khơng nên phụ thuộc vào chi tiết của thuật tốn. Nếu độ dài của hệ thống mã hố mới tin rằng trong thực tế kẻ tấn cơng khơng thể biết nội dung bên trong của thuật tốn. Nếu bạn tin rằng giữ bí mật nội dung của thuật tốn, tận dụng độ an tồn của hệ thống hơn là phân tích những lý thuyết sở hữu chung thì bạn đã nhầm. Và thật ngây thơ hơn khi nghĩ rằng một ai đĩ khơng thể gỡ tung mã nguồn của bạn hoặc đảo ngược lại thuật tốn. Giả sử rằng một vài kẻ thám mã cĩ thể biết hết tất cả chi tiết về thuật tốn của bạn. Giả sử rằng họ cĩ rất nhiều bản mã, như họ mong muốn. Giả sử họ cĩ một khối lượng bản rõ tấn cơng với rất nhiều dữ liệu cần thiết. Thậm chí giả sử rằng họ cĩ thể lựa chọn bản rõ tấn cơng. Nếu như hệ thống mã hố của cĩ thể dư thừa độ an tồn trong tất cả mọi mặt, thì bạn đã cĩ đủ độ an tồn bạn cần. Tĩm lại câu hỏi đặt ra trong mục này là : Khố nên dài bao nhiêu. Trả lời câu hỏi này phụ thuộc vào chính những ứng dụng cụ thể của bạn. Dữ liệu cần an tồn của bạn dài bao nhiêu ? Dữ liệu của bạn trị giá bao nhiêu ? Thậm chí bạn cĩ thể chỉ chỉ rõ những an tồn cần thiết theo cách sau. 31 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Độ dài khố phải là một trong 2 32 khố để tương ứng với nĩ là kẻ tấn cơng phải trả 100.000.000 $ để bẻ gãy hệ thống. 3.2 Quản lý khố cơng khai. Trong thực tế, quản lý khố là vấn đề khĩ nhất của an tồn hệ mã hố. Để thiết kế an tồn thuật tốn mã hố và protocol là một việc là khơng phải là dễ dàng nhưng để tạo và lưu trữ khố bí mật là một điều khĩ hơn. Kẻ thám mã thường tấn cơng cả hai hệ mã hố đối xứng và cơng khai thơng qua hệ quản lý khố của chúng. Đối với hệ mã hố cơng khai việc quản lý khố dễ hơn đối với hệ mã hố đối xứng, nhưng nĩ cĩ một vấn đề riêng duy nhất. Mối người chỉ cĩ một khố cơng khai, bất kể số người ở trên mạng là bao nhiêu. Nếu Eva muốn gửi thơng báo đến cho Bob, thì cơ ấy cần cĩ khố cơng khai của Bob. Cĩ một vài phương pháp mà Eva cĩ thể lấy khố cơng khai của Bob :  Eva cĩ thể lấy nĩ từ Bob.  Eva cĩ thể lấy từ trung tâm cơ sở dữ liệu.  Eva cĩ thể lấy từ cơ sở dữ liệu riêng của cơ ấy. Chứng nhận khố cơng khai : Chứng nhận khố cơng khai là xác định khố thuộc về một ai đĩ, được quản lý bởi một người đáng tin cậy. Chứng nhận để sử dụng vào việc cản trở sự cống gắng thay thế một khố này bằng một khố khác. Chứng nhận của Bob, trong sơ sở dữ liệu khố cơng khai, lưu trữ nhiều thơng tin hơn chứ khơng chỉ là khố cơng khai. Nĩ lưu trữ thơng tin về Bob như tên, địa chỉ, và nĩ được viết bởi ai đĩ mà Eva tin tưởng, người đĩ thường gọi là CA(certifying authority). Bằng cách xác nhận cả khố và thơng tin về Bob. CA xác nhận thơng tin về Bob là đúng và khố cơng khai thuộc quyền sở hữu của Bob. Eva kiểm tra lại các dấu hiệu và sau đĩ cơ ấy cĩ 32 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin thể sử dụng khố cơng khai, sự an tồn cho Bob và khơng một ai khác biết. Chứng nhận đĩng một vai trị rất quan trọng trong protocol của khố cơng khai. Quản lý khố phân phối : Trong một vài trường hợp, trung tâm quản lý khố cĩ thể khơng làm việc. Cĩ lẽ khơng cĩ một CA (certifying authority) nào mà Eva và Bob tin tưởng. Cĩ lẽ họ chỉ tin tưởng bạn bè thân thiết hoặc họ khơng tin tưởng bất cứ ai. Quản lý khố phân phối, sử dụng trong những chương trình miền cơng khai, giải quyết vấn đề này với người giới thiệu (introducers). Người giới thiệu là một trong những người dùng khác của hệ thống anh ta là người nhận ra khố cơng khai của bạn anh ta. Ví dụ : Khi Bob sinh ra khố cơng khai, anh ta đưa bản copy cho bạn anh ấy là Bin và Dave. Họ đều biết Bob, vì vậy họ cĩ khố của Bob và đưa cho các dấu hiệu của anh ta. Bây giờ Bob đưa ra khố cơng khai của anh ta cho người lạ, giả sử đĩ là Eva, Bob đưa ra khố cùng với các dấu hiệu của hai người giới thiệu. Mặt khác nếu Eva đã biết Bin hoặc Dave, khi đĩ cơ ta cĩ lý do tin rằng khố của Bob là đúng. Nếu Eva khơng biết Bin hoặc Dave thì cơ ấy khơng cĩ lý do tin tưởng khố của Bob là đúng. Theo thời gian, Bob sẽ tập hợp được nhiều người giới thiệu như vậy khố của anh ta sẽ được biết đến rộng rãi hơn. Lợi ích của kỹ thuật này là khơng cần tới trung tâm phân phối khố, mọi người đều cĩ sự tín nhiệm, khi mà Eva nhận khố cơng khai của Bob, sẽ khơng cĩ sự bảo đảm nào rằng cơ ấy sẽ biết bất kỳ điều gì của người giới thiệu và hơn nữa khơng cĩ sự đảm bảo nào là cơ ấy sẽ tin vào sự đúng đắn của khố. 33 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 4. Mã dịng, mã khối (CFB, CBC) 4.1 Mơ hình mã hố khối. Mã hố sử dụng các thuật tốn khối gọi đĩ là mã hố khối, thơng thường kích thước của khối là 64 bits. Một số thuật tốn mã hố khối sẽ được trình bày sau đây. 4.1.1 Mơ hình dây truyền khối mã hố. Dây truyền sử dụng kỹ thuật thơng tin phản hồi, bởi vì kết quả của khối mã hố trước lại đưa vào khối mã hố hiện thời. Nĩi một cách khác khối trước đĩ sử dụng để sửa đổi sự mã hố của khối tiếp theo. Mỗi khối mã hố khơng phụ thuộc hồn tồn vào khối của bản rõ. Trong dây truyền khối mã hố (Cipher Block Chaining Mode), bản rõ đã được XOR với khối mã hố kế trước đĩ trước khi nĩ được mã hố. Hình 4.1.1 thể hiện các bước trong dây truyền khối mã hố. Sau khi khối bản rõ được mã hố, kết quả của sự mã hố được lưu trữ trong thanh ghi thơng tin phản hồi. Trước khi khối tiếp theo của bản rõ được mã hố, nĩ sẽ XOR với thanh ghi thơng tin phản hồi để trở thành đầu vào cho tuyến mã hố tiếp theo. Kết quả của sự mã hố tiếp tục được lưu trữ trong thanh ghi thơng tin phản hồi, và tiếp tục XOR với khối bản rõ tiếp theo, tiếp tục như vậy cho tới kết thúc thơng báo. Sự mã hố của mỗi khối phụ thuộc vào tất cả các khối trước đĩ. 34 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin IO P1 Mã hố E(P1  I0) = C1 K Mã hố E(P2  C1) = C2 1 K P3 Mã hố E(P3  C2) = C3 1 K Hình 4.1.1 Sơ đồ mơ hình dây chuyền khối mã hố . Sự giải mã là cân đối rõ ràng. Một khối mã hố giải mã bình thường và mặt khác được cất giữ trong thanh ghi thơng tin phản hồi. Sau khi khối tiếp theo được giải mã nĩ XOR với kết quả của thanh ghi phản hồi. Như vậy khối mã hố tiếp theo được lưa trữ trong thanh ghi thơng tin phản hồi, tiếp tục như vậy cho tới khi kết thúc thơng báo. Cơng thức tốn học của quá trình trên như sau : Ci = EK(Pi XOR Ci-1) Pi = Ci-1 XOR DK(Ci) 4.1.2 Mơ hình mã hố với thơng tin phản hồi. Trong mơ hình dây truyền khối mã hố(CBC_Cipher Block Chaining Mode), sự mã hĩa khơng thể bắt đầu cho tới khi hồn thành nhận được một khối dữ liệu. Đây thực sự là vấn đề trong một vài mạng ứng dụng. Ví 35 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin dụ, trong mơi trường mạng an tồn, một thiết bị đầu cuối phải truyền mỗi ký tự tới máy trạm như nĩ đã được đưa vào. Khi dữ liệu phải xử lý như một khúc kích thước byte, thì mơ hình dây truyền khối mã hố là khơng thoả đáng. Tại mơ hình CFB dữ liệu là được mã hĩa trong một đơn vị nhỏ hơn là kích thước của khối. Ví dụ sẽ mã hố một ký tự ASCII tại một thời điểm (cịn gọi là mơ hình 8 bits CFB) nhưng khơng cĩ gì là bất khả kháng về số 8. Bạn cĩ thể mã hố 1 bit dữ liệu tại một thời điểm, sử dụng thuật tốn 1 bit CFB. 4.2 Mơ hình mã hố dịng. Mã hĩa dịng là thuật tốn, chuyển đổi bản rõ sang bản mã là 1 bit tại mỗi thời điểm. Sự thực hiện đơn giản nhất của mã hố dịng được thể hiện trong hình 4.2 Bả sinh Bả sinh khốBả dịng sinh khốBả dịngsinh khố dịng khố dịng Khố dịng Ki Khố dịng Ki Khố dịng Ki Khố dịng Bản rõ Bản mã Bản rõ Bản rõ Bản mã gảcBản rõ gảc Ci Pi Pi Mã hố Giải Ci Pi Mã hố mãGiải mã 36 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Hình 4.2 Mã hố dịng. Bộ sinh khố dịng là đầu ra một dịng các bits : k 1, k2, k3, . . . ki. Đây là khố dịng đã được XOR với một dịng bits của bản rõ, p 1, p2, p3, . . pi, để đưa ra dịng bits mã hố. ci = pi XOR ki Tại điểm kết thúc của sự giải mã, các bits mã hố được XOR với khố dịng để trả lại các bits bản rõ. pi = ci XOR ki Từ lúc pi XOR ki XOR ki = pi là một cơng việc tỉ mỉ. Độ an tồn của hệ thống phụ thuộc hồn tồn vào bên trong bộ sinh khố dịng. Nếu đầu ra bộ sinh khố dịng vơ tận bằng 0, thì khi đĩ bản rõ bằng bản mã và cả quá trình hoạt động sẽ là vơ dụng. Nếu bộ sinh khố dịng sinh ra sự lặp lại 16 bits mẫu, thì thuật tốn sẽ là đơn giản với độ an tồn khơng đáng kể. Nếu bộ sinh khố dịng là vơ tận của dịng ngẫu nhiên các bits, bạn sẽ cĩ một vùng đệm (one time-pad) và độ an tồn tuyệt đối. Thực tế mã hố dịng nĩ nằm đâu đĩ giữa XOR đơn giản và một vùng đệm. Bộ sinh khố dịng sinh ra một dịng bits ngẫu nhiên, thực tế điều này quyết định thuật tốn cĩ thể hồn thiện tại thời điểm giải mã. Đầu ra của bộ sinh khố dịng là ngẫu nhiên, như vậy người phân tích mã sẽ khĩ khăn hơn khi bẻ gãy khố. Như bạn đã đốn ra được rằng, tạo một bộ sinh khố dịng mà sản phẩm đầu ra ngẫu nhiên là một vấn đề khơng dễ dàng. 5. Các hệ mật mã đối xứng và cơng khai 5.1 Hệ mật mã đối xứng Thuật tốn đối xứng hay cịn gọi thuật tốn mã hố cổ điển là thuật tốn mà tại đĩ khố mã hố cĩ thể tính tốn ra được từ khố giải mã. Trong rất nhiều trường hợp, khố mã hố và khố giải mã là giống nhau. Thuật tốn 37 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin này cịn cĩ nhiều tên gọi khác như thuật tốn khố bí mật, thuật tốn khố đơn giản, thuật tốn một khố. Thuật tốn này yêu cầu người gửi và người nhận phải thoả thuận một khố trước khi thơng báo được gửi đi, và khố này phải được cất giữ bí mật. Độ an tồn của thuật tốn này vẫn phụ thuộc và khố, nếu để lộ ra khố này nghĩa là bất kỳ người nào cũng cĩ thể mã hố và giải mã thơng báo trong hệ thống mã hố. Sự mã hố và giải mã của thuật tốn đối xứng biểu thị bởi : EK( P ) = C DK( C ) = P K1 K2 Bản rõ Bản Bản rõ Mã hố mã Mã hố gảc Hình 5.1 Mã hố và giải mã với khố đối xứng . Trong hình vẽ trên thì : K1cĩ thể trùng K2, hoặc K1 cĩ thể tính tốn từ K2, hoặc K2 cĩ thể tính tốn từ K1. Một số nhược điểm của hệ mã hố cổ điển Các phương mã hố cổ điển địi hỏi người mã hố và người giải mã phải cùng chung một khố. Khi đĩ khố phải được giữ bí mật tuyệt đối, do vậy ta dễ dàng xác định một khố nếu biết khố kia. 38 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Hệ mã hố đối xứng khơng bảo vệ được sự an tồn nếu cĩ xác suất cao khố người gửi bị lộ. Trong hệ khố phải được gửi đi trên kênh an tồn nếu kẻ địch tấn cơng trên kênh này cĩ thể phát hiện ra khố. Vấn đề quản lý và phân phối khố là khĩ khăn và phức tạp khi sử dụng hệ mã hố cổ điển. Người gửi và người nhận luơn luơn thơng nhất với nhau về vấn đề khố. Việc thay đổi khố là rất khĩ và dễ bị lộ. Khuynh hướng cung cấp khố dài mà nĩ phải được thay đổi thường xuyên cho mọi người trong khi vẫn duy trì cả tính an tồn lẫn hiệu quả chi phí sẽ cản trở rất nhiều tới việc phát triển hệ mật mã cổ điển. 5.2 Hệ mật mã cơng khai Vào những năm 1970 Diffie và Hellman đã phát minh ra một hệ mã hố mới được gọi là hệ mã hố cơng khai hay hệ mã hố phi đối xứng. Thuật tốn mã hố cơng khai là khác biệt so với thuật tốn đối xứng. Chúng được thiết kế sao cho khố sử dụng vào việc mã hố là khác so K1 K2 Bản rõ Bản Bản rõ Mã hố mã Giải mã gảc với khố giải mã. Hơn nữa khố giải mã khơng thể tính tốn được từ khố mã hố. Chúng được gọi với tên hệ thống mã hố cơng khai bởi vì khố để mã hố cĩ thể cơng khai, một người bất kỳ cĩ thể sử dụng khố cơng khai để mã hố thơng báo, nhưng chỉ một vài người cĩ đúng khố giải mã thì mới cĩ khả năng giải mã. Trong nhiều hệ thống, khố mã hố gọi là khố cơng khai (public key), khố giải mã thường được gọi là khố riêng (private key). 39 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Hình 5.2 Mã hố và giải mã với hai khố . Trong hình vẽ trên thì : K1 khơng thể trùng K2, hoặc K2 khơng thể tính tốn từ K1. Đặc trưng nổi bật của hệ mã hố cơng khai là cả khố cơng khai(public key) và bản tin mã hố (ciphertext) đều cĩ thể gửi đi trên một kênh thơng tin khơng an tồn. Diffie và Hellman đã xác đinh rõ các điều kiện của một hệ mã hố cơng khai như sau : 1. Việc tính tốn ra cặp khố cơng khai KB và bí mật kB dựa trên cơ sở các điều kiện ban đầu phải được thực hiện một cách dễ dàng, nghĩa là thực hiện trong thời gian đa thức. 2. Người gửi A cĩ được khố cơng khai của người nhận B và cĩ bản tin P cần gửi đi thì cĩ thể dễ dàng tạo ra được bản mã C. C = EKB (P) = EB (P) Cơng việc này cũng trong thời gian đa thức. 3. Người nhận B khi nhận được bản tin mã hĩa C với khố bí mật kB thì cĩ thể giải mã bản tin trong thời gian đa thức. P = DkB (C) = DB[EB(M)] 4. Nếu kẻ địch biết khố cơng khai K B cố gắng tính tốn khố bí mật thì khi đĩ chúng phải đương đầu với trường hợp nan giải, trường hợp này địi hỏi nhiều yêu cầu khơng khả thi về thời gian. 40 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 5. Nếu kẻ địch biết được cặp (K B,C) và cố gắng tính tốn ra bản rõ P thì giải quyết bài tốn khĩ với số phép thử là vơ cùng lớn, do đĩ khơng khả thi. 6. Các cách thám mã Cĩ sáu phương pháp chung để phân tích tấn cơng, dưới đây là danh sách theo thứ tự khả năng của từng phương pháp. Mỗi phương pháp trong số chúng giả sử rằng kẻ thám mã hồn tồn cĩ hiểu biết về thuật tốn mã hố được sử dụng. 1. Chỉ cĩ bản mã. Trong trường hợp này, người phân tích chỉ cĩ một vài bản tin của bản mã, tất cả trong số chúng đều đã được mã hố và cùng sử dụng chung một thuật tốn. Cơng việc của người phân tích là tìm lại được bản rõ của nhiều bản mã cĩ thể hoặc tốt hơn nữa là suy luận ra được khố sử dụng mã hố, và sử dụng để giải mã những bản mã khác với cùng khố này. Giả thiết : C1 = Ek(P1), C2= Ek(P2), . . .Ci = Ek(Pi) Suy luận : Mỗi P1,P2, . . Pi, k hoặc thuật tốn kết luận Pi+1 từ Ci+1 = Ek(Pi+1) 2. Biết bản rõ. Người phân tích khơng chỉ truy cập được một vài bản mã mặt khác cịn biết được bản rõ. Cơng việc là suy luận ra khố để sử dụng giải mã hoặc thuật tốn giải mã để giải mã cho bất kỳ bản mã nào khác với cùng khố như vậy. Giả thiết : P1, C1 = Ek(P1), P2, C2= Ek(P2), . . . Pi, Ci = Ek(Pi) Suy luận : Mỗi k hoặc thuật tốn kết luận Pi+1 từ Ci+1 = Ek(Pi+1) 3. Lựa chọn bản rõ. Người phân tích khơng chỉ truy cập được bản mã và kết hợp bản rõ cho một vài bản tin, nhưng mặt khác lựa chọn bản rõ đã mã hố. Phương pháp này tỏ ra cĩ khả năng hơn 41 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin phương pháp biết bản rõ bởi vì người phân tích cĩ thể chọn cụ thể khối bản rõ cho mã hố, một điều khác cĩ thể là sản lượng thơng tin về khố nhiều hơn. Giả thiết : P1, C1 = Ek(P1), P2, C2= Ek(P2), . . . Pi, Ci = Ek(Pi) tại đây người phân tích chọn P1, P2,. . . Pi Suy luận : Mỗi k hoặc thuật tốn kết luận Pi+1 từ Ci+1 = Ek(Pi+1) 4. Mơ phỏng lựa chọn bản rõ. Đây là trường hợp đặc biệt của lựa chọn bản rõ. Khơng chỉ cĩ thể lựa chọn bản rõ đã mã hố, nhưng họ cịn cĩ thể sửa đổi sự lựa chọn cơ bản kết quả của sự mã hố lần trước. Trong trường lựa chọn bản mã người phân tích cĩ thể đã chọn một khối lớn bản rõ đã mã hố, nhưng trong trường hợp này cĩ thể chọn một khối nhỏ hơn và chọn căn cứ khác trên kết quả của lần đầu tiên. 5. Lựa chọn bản mã. Người phân tích cĩ thể chọn bản mã khác nhau đã được mã hố và truy cập bản rõ đã giải mã. Trong ví dụ khi một người phân tích cĩ một hộp chứng cớ xáo chộn khơng thể tự động giải mã, cơng việc là suy luận ra khố. Giả thiết : C1, P1 = Dk(C1), C2, P2= Dk(C2), . . . Ci, Pi = Dk(Ci) tại Suy luận : k 6. Lựa chọn khố. Đây khơng phải là một cách tấn cơng khi mà bạn đã cĩ khố. Nĩ khơng phải là thực hành thám mã mà chỉ là sự giải mã thơng thường, bạn chỉ cần lựa chọn khố cho phù hợp với bản mã. Một điểm đáng chú ý khác là đa số các kỹ thuật thám mã đều dùng phương pháp thống kê tần suất xuất hiện của các từ, các ký tự trong bản mã. Sau đĩ thực hiện việc thử thay thế với các chữ cái cĩ tần suất xuất 42 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin hiện tương đồng trong ngơn ngữ tự nhiên. Tại đây chúng ta chỉ xem xét đối với ngơn ngữ thơng dụng nhất hiện nay đĩ là tiếng Anh. Việc thống kê tần suất xuất hiện của các ký tự trong trường hợp này được tiến hành dựa trên các bài báo, sách, tạp chí và các văn bản cùng với một số loại khác Sau đây là bảng thống kê tần suất xuất hiện của 26 chữ cái trong bảng chữ cái tiếng Anh theo tài liệu của Beker và Piper. Ký tự Xác Suất Ký tự Xác suất Ký tự Xác suất A 0.082 J 0.002 S 0.063 B 0.015 K 0.008 T 0.091 C 0.028 L 0.040 U 0.028 D 0.043 M 0.024 V 0.010 E 0.127 N 0.067 W 0.023 F 0.022 O 0.075 X 0.001 G 0.020 P 0.019 Y 0.020 H 0.061 Q 0.001 Z 0.001 I 0.070 R 0.060 Cùng với việc thống kê các tần xuất của các ký tự trong tiếng Anh, việc thống kê tần suất xuất hiện thường xuyên của các dãy gồm 2 hoặc 3 ký tự liên tiếp nhau cũng cĩ một vai trị quan trọng trong cơng việc thám mã. Sysu Deck đưa ra 30 bộ đơi xuất hiện thường xuyên của tiếng Anh được sắp theo thứ tự giảm dần như sau : Tính hữu dụng của các phép thống kê ký tự và các dãy ký tự được người phân tích mã khai thác triệt để trong những lần thám mã. Khi thực hiện việc thám mã người phân tích thống kê các ký tự trong bản mã, từ đĩ so 43 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin sánh với bản thống kê mẫu và đưa ra các ký tự phỏng đốn tương tự. Phương pháp này được sử dụng thường xuyên và đem lại hiệu quả khá cao. 44 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Cặp chữ Tần suất Cặp chữ Tần suất Cặp chữ Tần suất TH 10.00 ED 4.12 OF 3.38 HE 9.50 TE 4.04 IT 3.26 IN 7.17 TI 4.00 AL 3.15 ER 6.65 OR 3.98 AS 3.00 RE 5.92 ST 3.81 HA 3.00 ON 5.70 AR 3.54 NG 2.92 AN 5.63 ND 3.52 CO 2.80 EN 4.76 TO 3.50 SE 2.75 AT 4.72 NT 3.44 ME 2.65 ES 4.24 IS 3.43 DE 2.65 45 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Chương III Hệ mã hố RSA. Với đề tài xây dựng thư viện các hàm mã hố dùng cho việc bảo mật thơng tin trao đổi trong mơ hình Client/Server, thì cần thiết một phương pháp mã hố để áp dụng, thuật tốn mã hố cơng khai RSA đã được lựa chọn cho giải pháp này. Phương pháp này cĩ những ưu điểm, nhược điểm, đặc tính gì đĩ là phần sẽ trình bày trong chương này  Khái niệm hệ mật mã RSA  Phân phối khố cơng kkai trong RSA  Độ an tồn của hệ RSA  Một số tính chất của hệ RSA 1. Khái niệm hệ mật mã RSA Khái niệm hệ mật mã RSA đã được ra đời năm 1976 bởi các tác giả R.Rivets, A.Shamir, và L.Adleman. Hệ mã hố này dựa trên cơ sở của hai bài tốn : + Bài tốn Logarithm rời rạc (Discrete logarith) + Bài tốn phân tích thành thừa số. Trong hệ mã hố RSA các bản rõ, các bản mã và các khố (public key và private key) là thuộc tập số nguyên Z N = {1, . . . , N-1}. Trong đĩ tập Z N với N=p q là các số nguyên tố khác nhau cùng với phép cộng và phép nhân Modulo N tạo ra modulo số học N. Khố mã hố EKB là cặp số nguyên (N,K B) và khố giải mã Dkb là cặp số nguyên (N,kB), các số là rất lớn, số N cĩ thể lên tới hàng trăm chữ số. Các phương pháp mã hố và giải mã là rất dễ dàng. Cơng việc mã hố là sự biến đổi bản rõ P (Plaintext) thành bản mã C (Ciphertext) dựa trên cặp khố cơng khai K B và bản rõ P theo cơng thức sau đây : 46 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin KB C = EKB(P) = EB(P) = P (mod N) . (1) Cơng việc giải mã là sự biến đổi ngược lại bản mã C thành bản rõ P dựa trên cặp khố bí mật kB , modulo N theo cơng thức sau : kB P = DkB(C) = DB(C) = C (mod N) . (2) Dễ thấy rằng, bản rõ ban đầu cần được biến đổi một cách thích hợp thành bản mã, sau đĩ để cĩ thể tái tạo lại bản rõ ban đầu từ chính bản mã đĩ : P = DB(EB(P)) (3) Thay thế (1) vào (2) ta cĩ : (PKB)kB = P (mod N ) (4) Trong tốn học đã chứng minh được rằng, nếu N là số nguyên tố thì cơng thức (4) sẽ cĩ lời giải khi và chỉ khi K B.kB = 1 (mod N-1), áp dụng thuật tốn ta thấy N=p q với p, q là số nguyên tố, do vậy (4) sẽ cĩ lời giải khi và chỉ khi : KB.kB  1 (mod (N)) (5) trong đĩ (N) = LCM(p-1,q-1) . LCM (Lest Common Multiple) là bội số chung nhỏ nhất. Nĩi một cách khác, đầu tiên người nhận B lựa chọn một khố cơng khai KB một cách ngẫu nhiên. Khi đĩ khố bí mật k B được tính ra bằng cơng thức (5). Điều này hồn tồn tính được vì khi B biết được cặp số nguyên tố (p,q) thì sẽ tính được (N). 47 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Chản p và q Tính N=p q Tính (N) Bản rõ P KB KB Chản khố KB C = P (mod N) Bản mã C kB P = CkB ( mod N ) Chản khố KB Bản rõ gảc P Hình 1.1 Sơ đồ các bước thực hiện mã hố theo thuật tốn RSA. 2. Độ an tồn của hệ RSA Một nhận định chung là tất cả các cuộc tấn cơng giải mã đều mang mục đích khơng tốt. Trong phần độ an tồn của hệ mã hố RSA sẽ đề cập đến một vài phương thức tấn cơng điển hình của kẻ địch nhằm giải mã trong thuật tốn này. Chúng ta xét đến trường hợp khi kẻ địch nào đĩ biết được modulo N, khố cơng khai KB và bản tin mã hố C, khi đĩ kẻ địch sẽ tìm ra bản tin gốc (Plaintext) như thế nào. Để làm được điều đĩ kẻ địch thường tấn vào hệ thống mật mã bằng hai phương thức sau đây: 48 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Phương thức thứ nhất : Trước tiên dựa vào phân tích thừa số modulo N. Tiếp theo sau chúng sẽ tìm cách tính tốn ra hai số nguyên tố p và q, và cĩ khả năng thành cơng khi đĩ sẽ tính được (N) và khố bí mật k B. Ta thấy N cần phải là tích của hai số nguyên tố, vì nếu N là tích của hai số nguyên tố thì thuật tốn phân tích thừa số đơn giản cần tối đa N bước, bởi vì cĩ một số nguyên tố nhỏ hơn N . Mặt khác, nếu N là tích của n số nguyên tố, thì thuật tốn phân tích thừa số đơn giản cần tối đa N1/n bước. Một thuật tốn phân tích thừa số cĩ thể thành phức tạp hơn, cho phép phân tích một số N ra thành thừa số trong O(P ) bước, trong đĩ p là số chia nhỏ nhất của N, việc chọn hai số nguyên tố là cho thuật tốn tăng hiệu quả. Phương thức thứ hai : Phương thức tấn cơng thứ hai vào hệ mã hố RSA là cĩ thể khởi đầu bằng cách giải quyết trường hợp thích hợp của bài tốn logarit rời rạc. Trường hợp này kẻ địch đã cĩ trong tay bản mã C và khố cơng khai K B tức là cĩ cặp (KB,C) Cả hai phương thức tấn cơng đều cần một số bước cơ bản, đĩ là : O(exp lnNln(lnN) ), trong đĩ N là số modulo. 3. Một số tính chất của hệ RSA Trong các hệ mật mã RSA, một bản tin cĩ thể được mã hố trong thời gian tuyến tính. Đối với các bản tin dài, độ dài của các số được dùng cho các khố cĩ thể được coi như là hằng. Tương tự như vậy, nâng một số lên luỹ thừa được thực hiện trong thời gian hằng, các số khơng được phép dài hơn một độ dài hằng. Thực ra tham số này che dấu nhiều chi tiết cài đặt cĩ liên quan đến việc tính tốn với các con số dài, chi phí của các phép tốn thực sự là 49 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin một yếu tố ngăn cản sự phổ biến ứng dụng của phương pháp này. Phần quan trọng nhất của việc tính tốn cĩ liên quan đến việc mã hố bản tin. Nhưng chắc chắn là sẽ khơng cĩ hệ mã hố nào hết nếu khơng tính ra được các khố của chúng là các số lớn. Các khố cho hệ mã hố RSA cĩ thể được tạo ra mà khơng phải tính tốn quá nhiều. Một lần nữa, ta lại nĩi đến các phương pháp kiểm tra số nguyên tố. Mỗi số nguyên tố lớn cĩ thể được phát sinh bằng cách đầu tiên tạo ra một số ngẫu nhiên lớn, sau đĩ kiểm tra các số kế tiếp cho tới khi tìm được một số nguyên tố. Một phương pháp đơn giản thực hiện một phép tính trên một con số ngấu nhiên, với xác suất 1/2 sẽ chứng minh rằng số được kiểm tra khơng phải nguyên tố. Bước cuối cùng là tính p dựa vào thuật tốn Euclid. Như phần trên đã trình bày trong hệ mã hố cơng khai thì khố giải mã (private key) kB và các thừa số p,q là được giữ bí mật và sự thành cơng của phương pháp là tuỳ thuộc vào kẻ địch cĩ khả năng tìm ra được giá trị của kB hay khơng nếu cho trước N và KB. Rất khĩ cĩ thể tìm ra được kB từ KB cần biết về p và q, như vậy cần phân tích N ra thành thừa số để tính p và q. Nhưng việc phân tích ra thừa số là một việc làm tốn rất nhiều thời gian, với kỹ thuật hiện đại ngày nay thì cần tới hàng triệu năm để phân tích một số cĩ 200 chữ số ra thừa số. Độ an tồn của thuật tốn RSA dựa trên cơ sở những khĩ khăn của việc xác định các thừa số nguyên tố của một số lớn. Bảng dưới đây cho biết các thời gian dự đốn, giả sử rằng mỗi phép tốn thực hiện trong một micro giây. 50 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Số các chữ số trong Thời gian phân tích số được phân tích 50 4 giờ 75 104 giờ 100 74 năm 200 4.000.000 năm 300 5 1015 năm 500 4 1025 năm 51 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Chương IV Mơ hình Client/Server Trong thực tế, mơ hình Client/Server đã trở nên rất phổ biến trong hệ thống mạng điểm tới điểm, và chúng được áp dụng hầu hết cho những máy tính truyền thơng ngày nay. Kiến trúc mơ hình Client/Server và khi nào cần mã hố thơng tin truyền trong Client/Server là chủ đề sẽ được trình bày trong chương này. 1.Mơ hình Client/Server Nĩi chung, một ứng dụng khởi tạo truyền thơng từ điểm tới điểm được gọi là client. Người dùng cuối thường xuyên gọi phần mềm client khi họ cần tới những dịch vụ trên mạng. Mơ hình Client/Server cố gắng tổ chức lại các máy PC, trên mạng cụ bộ, để thích hợp với các máy tính lớn mainframe, tăng tính thích ứng, tính hiệu quả của hệ thống. Mặc dù cĩ sự thay đổi rất lớn các quan điểm về mơ hình Client/Server, nhưng chúng cĩ một vài đặc tính dưới đây.  Máy Client là các máy PC hay là các workstations, truy cập vào mạng và sử dụng các tài nguyên trên mạng.  Giao diện người sử dụng với Client, nĩi chung sử dụng giao diện người dùng đồ hoạ (GUI), ví như Microsoft Windowns  Trong hệ thống Client/Server cĩ một vài Client, với mỗi Client sử dụng giao diện riêng của mình. Các Client sử dụng các tài nguyên được chia sẻ bởi Server.  Server cĩ thể là một workstation lớn, như mainframe, minicomputer, hoặc các thiết bị mạng LAN.  Client cĩ thể gửi các truy vấn hoặc các lệnh tới Server, nhưng thực hiện tiến trình này khơng phải là Client.  Server trả lại kết quả trên màn hình của Client. 52 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin  Các loại Server thơng thường là : database server, file server, print server, image-processing server, computing server và communication server.  Server khơng thể khởi tạo bất kỳ cơng việc nào, nhưng nĩ thực hiện các yêu cầu to lớn của Client.  Nhiệm vụ chia là hai phần : phần mặt trước thực hiện bởi client, và phần mặt sau thực hiện bởi Server.  Server thực hiện việc chia sẻ File, lưu trữ và tìm ra các thơng tin, mạng và quản lý tài liệu, quản lý thư điện tử, bảng thơng báo và văn bản video. 2. Mã hố trong mơ hình Client/Server. Trong mơ hình Client/Server việc trao đổi thơng tin diễn ra thường xuyên nên rất dễ bị kẻ xấu lợi dụng, bởi vậy bảo vệ thơng tin trên đường truyền là vơ cùng quan trọng, chúng đảm bảo thơng tin trên đường truyền là đúng đắn. Tại mơ hình này mỗi khi những yêu cầu được gửi từ Client đến Server hoặc khi Server gửi trả lại kết quả cho Client thì những thơng tin này đều được mã hố trong khi truyền. 53 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Chương V Xây dựng hàm thư viện Xu hướng trên thế giới hiện nay là phần mềm được bán và phân phối ở dạng các modul phần mềm. Các hình thức của modul phụ thuộc vào các gĩi phần mềm cụ thể và các ngơn ngữ mà người sử dụng dùng. Ví dụ bạn cĩ thể tạo các thư viện tĩnh với các file cĩ phần mở rộng .LIB hoặc bạn cĩ thể tạo một điều khiển ActiveX với phần mở rộng OCX, hoặc hơn nữa bạn cĩ thể tạo các thư viện liên kết động với các file .DLL . Các ngơn ngữ lập trình hiện nay cĩ tính modul độc lập rất cao, nghĩa là bạn cĩ thể tạo ra các ứng dụng bằng cách kết hợp nhiều modul phần mềm độc lập nhau thành một ứng dụng cụ thể. Thơng thường khi thiết kế một phần mềm ứng dụng thuộc loại phức tạp, bạn sẽ tìm kiếm các modul cĩ thể sử dụng được để giảm chi phí, giảm thời gian thiết kế và tập chung nhiều hơn cho những phần ứng dụng tự bạn viết ra. Một câu hỏi đặt ra tại đây là vì sao chúng ta lại khơng tạo ra các hàm thực hiện các cơng việc chuyên biệt và phân phối nĩ cho người sử dụng, cĩ một vài lý do sau đây khơng cho phép thực hiện điều này : Người dùng cĩ thể vơ tình thay đổi làm xáo trộn các lệnh trong chương trình. Bạn khơng muốn người dùng biết "bí quyết" của bạn mà chỉ muốn họ sử dụng kết quả bạn tạo ra. Trong chương này của cuốn luận văn trình bày thư viện liên kết động là gì, và chúng thực hiện như thế nào. Thư viện liên kết động DLL (Dynamic Link Library) là một tập tin thư viện chứa các hàm. Người lập trình cĩ thể gọi một tập tin DLL vào trong chương trình của họ và sử dụng các hàm trong DLL đĩ. DLL là một thư viện liên kết động với các chương trình sử dụng nĩ, nghĩa là khi bạn tạo ra tập tin EXE của chương trình mà khơng cần liên kết tập 54 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin tin DLL với chương trình của bạn. Tập tin DLL sẽ được liên kết động với chương trình trong thời gian thi hành chương trình. Bởi vậy khi viết một ứng dụng cĩ sử dụng DLL, bạn phải phân phối tập tin DLL cùng với tập tin EXE của chương trình bạn viết. 1.Xây dựng thư viện liên kết động CRYPTO.DLL Thư viện crypto.dll được xây dựng dới đây cung cấp cho các bạn các hàm cần thiết phục vụ cho việc mã hố thơng tin, chúng bao gồm int enciph(char *, char *) : hàm mã hố. int deciph(char *, char *) : hàm giải mã. Hàm Enciph.c Các bạn cĩ thể sử dụng hàm này để thực hiện các thao tác mã hố với xâu kí tự, bằng cách đưa vào một xâu ký tự (bản rõ) ở đầu ra bạn sẽ nhận được một xâu ký tự đã được mã hố (bản mã). Với bản mã này các bạn cĩ thể yên tâm về nội dụng thơng tin sẽ rất khĩ bị lộ. Hàm thực hiện cĩ sử dụng khố cơng khai lấy vào từ File PUBLIC.KEY. //=== // Ham Enciph.c #include #include #include #include #include /* #define RSA */ int enciph(char *sin,char *sout) { /* encipher using public key */ 55 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin big x,ke; FILE *ifile; int ch,i,leng; long seed; miracl *mip=mirsys(100,0); x=mirvar(0); ke=mirvar(0); mip->IOBASE=60; if ((ifile=fopen("public.key","r"))==NULL) { return 1; } cinnum(ke,ifile); fclose(ifile); seed=123456789; irand(seed); bigrand(ke,x); leng=strlen(sin); for(i=0; i <= (leng-1); i++) { /* encipher character by character */ #ifdef RSA power(x,3,ke,x); #else mad(x,x,x,ke,ke,x); #endif ch=*(sin+i); ch^=x[1]; /* XOR with last byte of x */ sout[i]=ch; } return 0; } 56 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin //=== miracl *mirsys(int nd,mr_small nb) { /* Initialize MIRACL system to * * use numbers to base nb, and * * nd digits or (-nd) bytes long */ int i; mr_small b; mr_mip=(miracl *)mr_alloc(1,sizeof(miracl)); mr_mip->depth=0; mr_mip->trace[0]=0; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=25; if (MIRACL>=MR_IBITS) mr_mip->TOOBIG =(1 TOOBIG =(1 BTS=MIRACL/2; if (mr_mip->BTS==MR_IBITS) mr_mip->MSK=(-1); else mr_mip->MSK=(1 BTS))-1; #endif #ifdef MR_NO_STANDARD_IO mr_mip->ERCON=TRUE; #else mr_mip->ERCON=FALSE; #endif mr_mip->N=0; mr_mip->MSBIT=((mr_small)1 OBITS=mr_mip->MSBIT-1; mr_mip->user=NULL; mr_set_align(0); 57 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin #ifdef MR_NOFULLWIDTH if (nb==0) { mr_berror(MR_ERR_BAD_BASE); mr_mip->depth ; return mr_mip; } #endif if (nb==1 || nb>MAXBASE) { mr_berror(MR_ERR_BAD_BASE); mr_mip->depth ; return mr_mip; } mr_setbase(nb); b=mr_mip->base; mr_mip->lg2b=0; mr_mip->base2=1; if (b==0) { mr_mip->lg2b=MIRACL; mr_mip->base2=0; } else while (b>1) { b/=2; mr_mip->lg2b++; mr_mip->base2*=2; } if (nd>0) mr_mip->nib=(nd-1)/mr_mip->pack+1; 58 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin else mr_mip->nib=(mr_mip->lg2b-8*nd-1)/mr_mip->lg2b; if (mr_mip->nib nib=2; #ifdef MR_FLASH mr_mip->workprec=mr_mip->nib; mr_mip->stprec=mr_mip->nib; while(mr_mip->stprec>2 && mr_mip->stprec> MR_FLASH/ mr_mip->lg2b) mr_mip->stprec=(mr_mip->stprec+1)/2; if (mr_mip->stprec stprec=2; mr_mip->pi=NULL; #endif mr_mip->check=ON; mr_mip->IOBASE=10; mr_mip->ERNUM=0; mr_mip->RPOINT=OFF; mr_mip->NTRY=6; mr_mip->EXACT=TRUE; mr_mip->TRACER=OFF; mr_mip->INPLEN=0; mr_mip->PRIMES=NULL; mr_mip->IOBUFF=mr_alloc(MR_IOBSIZ+1,1); for (i=0;i ira[i]=0L; irand(0L); mr_mip->nib=2*mr_mip->nib+1; #ifdef MR_FLASH if (mr_mip->nib!=(mr_mip->nib&(mr_mip->MSK)) || mr_mip->nib > mr_mip- >TOOBIG) #else if(mr_mip->nib!=(mr_mip->nib&(mr_mip->OBITS)) || mr_mip->nib>mr_mip- >TOOBIG) #endif { mr_berror(MR_ERR_TOO_BIG); 59 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin mr_mip->nib=(mr_mip->nib-1)/2; mr_mip->depth ; return mr_mip; } mr_mip->modulus=NULL; mr_mip->A=NULL; mr_mip->B=NULL; mr_mip->fin=FALSE; mr_mip->fout=FALSE; mr_mip->active=ON; mr_mip->w0=mirvar(0); /* w0 is double length */ mr_mip->nib=(mr_mip->nib-1)/2; #ifdef MR_KCM mr_mip->big_ndash=NULL; mr_mip->ws=mirvar(0); #endif mr_mip->w1=mirvar(0); /* initialize workspace */ mr_mip->w2=mirvar(0); mr_mip->w3=mirvar(0); mr_mip->w4=mirvar(0); mr_mip->nib=2*mr_mip->nib+1; mr_mip->w5=mirvar(0); mr_mip->w6=mirvar(0); mr_mip->w7=mirvar(0); mr_mip->nib=(mr_mip->nib-1)/2; mr_mip->w5d=&(mr_mip->w5[mr_mip->nib+1]); mr_mip->w6d=&(mr_mip->w6[mr_mip->nib+1]); mr_mip->w7d=&(mr_mip->w7[mr_mip->nib+1]); mr_mip->w8=mirvar(0); mr_mip->w9=mirvar(0); mr_mip->w10=mirvar(0); 60 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin mr_mip->w11=mirvar(0); mr_mip->w12=mirvar(0); mr_mip->w13=mirvar(0); mr_mip->w14=mirvar(0); mr_mip->w15=mirvar(0); mr_mip->depth ; return mr_mip; } //=== flash mirvar(int iv) { /* initialize big/flash number */ flash x; if (mr_mip->ERNUM) return NULL; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=23; if (mr_mip->TRACER) mr_track(); if (!(mr_mip->active)) { mr_berror(MR_ERR_NO_MIRSYS); mr_mip->depth ; return NULL; } x=(mr_small *)mr_alloc(mr_mip->nib+1,sizeof(mr_small)); if (x==NULL) { mr_berror(MR_ERR_OUT_OF_MEMORY); mr_mip->depth ; return x; } convert(iv,x); mr_mip->depth ; return x; 61 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin } //=== int cinnum(flash x,FILE *filep) { /* convert from string to flash x */ int n; if (mr_mip->ERNUM) return 0; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=14; if (mr_mip->TRACER) mr_track(); mr_mip->infile=filep; mr_mip->fin=TRUE; n=cinstr(x,NULL); mr_mip->fin=FALSE; mr_mip->depth ; return n; } //=== void power(flash x,int n,flash w) { copy(x,mr_mip->w8); zero(w); if (mr_mip->ERNUM || size(mr_mip->w8)==0) return; convert(1,w); if (n==0) return; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=51; if (mr_mip->TRACER) mr_track(); if (n w8,mr_mip->w8); } 62 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin if (n==1) { copy(mr_mip->w8,w); mr_mip->depth ; return; } forever { if (n%2!=0) fmul(w,mr_mip->w8,w); n/=2; if (mr_mip->ERNUM || n==0) break; fmul(mr_mip->w8,mr_mip->w8,mr_mip->w8); } mr_mip->depth ; } //=== void mad(big x,big y,big z,big w,big q,big r) { if (mr_mip->ERNUM) return; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=24; if (mr_mip->TRACER) mr_track(); mr_mip->check=OFF; if (w==r) { mr_berror(MR_ERR_BAD_PARAMETERS); mr_mip->depth ; return; } multiply(x,y,mr_mip->w0); if (x!=z && y!=z)add(mr_mip->w0,z,mr_mip->w0); 63 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin divide(mr_mip->w0,w,q); if (q!=r) copy(mr_mip->w0,r); mr_mip->check=ON; mr_mip->depth ; } //=== Hàm Deciph.c Hàm sử dụng để thực hiện các thao tác giải mã hố với xâu kí tự đã được mã hố bằng hàm enciph.c ở trên, bằng cách đa vào một xâu ký tự đã mã hố (bản mã) ở đầu ra bạn sẽ nhận lại một xâu ký tự ban đầu (bản rõ gốc). Hàm thực hiện cĩ sử dụng khố bí mật lấy vào từ File PRIVATE.KEY. Hai File PUBLIC.KEY và PRIVATE.KEY chúng cùng được sinh ra do chương trình genkey, chúng cĩ quan hệ mật thiết với nhau và khơng thể tách rời, nếu cĩ khố cơng khai mà khơng cĩ khố bí mật thì cũng khơng thể giải mã được, cịn nếu cĩ khố bí mật mà khơng cĩ khố cơng khai thì cũng chẳng ích lợi gì. //=== //Deciph.c #include #include #include #include int deciph(char *strinputde, char *stroutputde) { /* decipher using private key */ big x,y,ke,p,q,n,a,b,alpha,beta,t; FILE *ifile; 64 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin int ch,i,leng; long ipt; miracl *mip=mirsys(100,0); x=mirvar(0); ke=mirvar(0); p=mirvar(0); q=mirvar(0); n=mirvar(0); y=mirvar(0); alpha=mirvar(0); beta=mirvar(0); a=mirvar(0); b=mirvar(0); t=mirvar(0); mip->IOBASE=60; if ((ifile=fopen("private.key","r"))==NULL) { return 1; } cinnum(p,ifile); cinnum(q,ifile); fclose(ifile); multiply(p,q,ke); leng=strlen(strinputde); cinstr(x,strinputde); xgcd(p,q,a,b,t); lgconv(leng,n); /* first recover "one-time pad" */ #ifdef RSA decr(p,1,alpha); premult(alpha,2,alpha); incr(alpha,1,alpha); 65 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin subdiv(alpha,3,alpha); #else incr(p,1,alpha); subdiv(alpha,4,alpha); #endif decr(p,1,y); powmod(alpha,n,y,alpha); #ifdef RSA decr(q,1,beta); premult(beta,2,beta); incr(beta,1,beta); subdiv(beta,3,beta); #else incr(q,1,beta); subdiv(beta,4,beta); #endif decr(q,1,y); powmod(beta,n,y,beta); copy(x,y); divide(x,p,p); divide(y,q,q); powmod(x,alpha,p,x); powmod(y,beta,q,y); mad(x,q,q,ke,ke,t); mad(t,b,b,ke,ke,t); mad(y,p,p,ke,ke,x); mad(x,a,a,ke,ke,x); add(x,t,x); divide(x,ke,ke); if (size(x)<0) add(x,ke,x); for (i=0;i<leng;i++) 66 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin { /* decipher character by character */ ch=*(strinputde+i); ch^=x[1]; /* XOR with last byte of x */ stroutputde[i]=ch; #ifdef RSA power(x,3,ke,x); #else mad(x,x,x,ke,ke,x); #endif } return 0; } //=== void multiply(big x,big y,big z) { /* multiply two big numbers: z=x.y */ int i,xl,yl,j,ti; mr_small carry,sz; big w0; #ifdef MR_NOASM mr_large dble; #endif if (mr_mip->ERNUM) return; if (y[0]==0 || x[0]==0) { zero(z); return; } w0=mr_mip->w0; /* local pointer */ mr_mip->depth++; mr_mip->trace[mr_mip->depth]=5; if (mr_mip->TRACER) mr_track(); #ifdef MR_FLASH 67 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin if (mr_notint(x) || mr_notint(y)) { mr_berror(MR_ERR_INT_OP); mr_mip->depth ; return; } #endif sz=((x[0]&mr_mip->MSBIT)^(y[0]&mr_mip->MSBIT)); xl=(int)(x[0]&mr_mip->OBITS); yl=(int)(y[0]&mr_mip->OBITS); zero(w0); if (mr_mip->check && xl+yl>mr_mip->nib) { mr_berror(MR_ERR_OVERFLOW); mr_mip->depth ; return; } //=== void mad(big x,big y,big z,big w,big q,big r) { if (mr_mip->ERNUM) return; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=24; if (mr_mip->TRACER) mr_track(); mr_mip->check=OFF; if (w==r) { mr_berror(MR_ERR_BAD_PARAMETERS); mr_mip->depth ; return; } 68 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin multiply(x,y,mr_mip->w0); if (x!=z && y!=z)add(mr_mip->w0,z,mr_mip->w0); divide(mr_mip->w0,w,q); if (q!=r) copy(mr_mip->w0,r); mr_mip->check=ON; mr_mip->depth ; } //=== int cinstr(flash x,unsigned char *string) { /* input big number in base IOBASE */ mr_small newb,oldb,b,lx; int ipt; if (mr_mip->ERNUM) return 0; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=78; if (mr_mip->TRACER) mr_track(); newb=mr_mip->IOBASE; oldb=mr_mip->apbase; mr_setbase(newb); /* temporarily change base */ b=mr_mip->base; mr_mip->check=OFF; ipt=instr(mr_mip->w5,string); /* and get number */ mr_mip->check=ON; lx=(mr_mip->w5[0]&mr_mip->OBITS); #ifdef MR_FLASH if ((int)(lx&mr_mip->MSK)>mr_mip->nib || (int)((lx>>mr_mip->BTS)&mr_mip- >MSK)>mr_mip->nib) #else if ((int)lx>mr_mip->nib) #endif { /* numerator or denominator too big */ 69 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin mr_berror(MR_ERR_OVERFLOW); mr_mip->depth ; return 0; } mr_setbase(oldb); /* restore original base */ cbase(mr_mip->w5,b,x); mr_mip->depth ; return ipt; } //=== void incr(big x,int n,big z) { /* add int to big number: z=x+n */ if (mr_mip->ERNUM) return; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=7; if (mr_mip->TRACER) mr_track(); convert(n,mr_mip->w0); select(x,PLUS,mr_mip->w0,z); mr_mip->depth ; } //=== void decr(big x,int n,big z) { /* subtract int from big number: z=x-n */ if (mr_mip->ERNUM) return; mr_mip->depth++; mr_mip->trace[mr_mip->depth]=8; if (mr_mip->TRACER) mr_track(); convert(n,mr_mip->w0); select(x,MINUS,mr_mip->w0,z); mr_mip->depth ; } 70 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin 2.Chương trình Demo thư viện CRYPTO.DLL Phần này xây dựng một ứng dụng đơn giản để Demo thư viện CRYPTO.DLL, chương trình xây dựng nhập vào một xâu rồi mã hố, giải mã và trả lại kết quả ban đầu. 71 X©y dùng th viƯn c¸c hµm m· ho¸.
Khoa C«ng NghƯ Th«ng Tin Tài liệu tham khảo : BRASSARD, Modern Cryptology. Lecture Notes in Computer Science, Vol. 325. Springer-Verlag 1988. BRUCE SCHNEIER, APPLIED CRYPTOGRAPHY, Protocol, Algorithms, and Source Code in C, John Wiley & Sons 1994 COMBA, Exponentiation Cryptosystems on the IBM PC. IBM Phạm Văn ất, Kỹ thuật lập trình C, cơ sở và nâng cao Nhà xuất bản giáo dục 1997. Xuân Nguyệt và Phùng Kim Hồng, học Visual C++ 5 trong 21 ngày. Nhà xuất bản Mũi cà mau 1998. P2 72 X©y dùng th viƯn c¸c hµm m· ho¸.