mở đầu về ATBM Thông tin HUT-2000 Độ dư thừa có thể coi là một thước đo của tính cấu trúc và tính “dễ đoán” (predictability) của ngôn ngữ. Độ dư thừa cao hơn chứng tỏ tính cấu trúc và tính “dễ đoán” cao hơn. Một nguồn phát tin thực sự ngẫu nhiên sẽ không có dư thừa. Trong tiếng Anh, độ dư thừa nằm trong khoảng từ 3.7 bits (gây nên bời biểu đó tần xuất “lồi lõm”, các mẫu tự 2-chữ, 3-chữ - bigrams và trigrams - phổ biến) Sử dụng Unicity distance ta có thể so sánh độ an toàn của các thuật toán mã hóa khác nhau.
Với mã 1-bảng thế, ta quan sát thấy E= |Z| = 26! P(Z) =1/26! log2E = log2(26!) 88.9 ký tự Như vậy các MÃ chứa 24 ký tự trở lên sẽ có thể bị giải mã một cách duy nhất. Với mã one-time-pad: X = không gian khóa = {tập hợp các đoạn văn bản tiếng Anh có độ dài k} Z = không gian khóa = {tập các chuỗi chữ độ dài k trông bảng chữ cái tiếng Anh} Giả thiết các khóa được chọn một cách ngẫu nhiên với xác xuất đồng nhất N0 = log2E/d E= 26k log2(26k) = k log2264.37k Do đó, thậm chí nếu E nghe trộm toàn bộ tất cả các chữ cái của đoạn MÃ, cô ta vẫn không thể giải phá mã (tìm được TIN tương ứng duy nhất). Ta có thể “tăng” tính mật của một hệ mã cho trước hay không? 1. Tăng độ lớn không gian khóa 2.
Giảm tính dư thừa của ngôn ngữ văn bản TIN: tiền xử lý qua 1 bước thuật toán nén Chú ý: một thuật toán nén lý tưởng có thể đem lại độ dư thừa 0, do đó N0 0 3. Có thể chèn thêm một đoạn văn bản ngẫu nhiên để “phẳng hóa“ độ thị tần xuất của văn bản TIN. Ta sẽ xét cụ thể biện pháp này dưới đây M L Văn bản TIN gốc Chuỗi ngẫu nhiên chèn Công thức sau cho biết độ dư thừa của văn bản mới (sau khi chèn thêm chuỗi ký tự ngẫu nhiên) ~ M d d LM Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000 HỆ THỐNG MÃ VỚI KHÓA CÔNG KHAI PUBLIC KEY CRYPTOSYSTEMS 1976, Diffie & Hellman. Khái niệm Các hệ thống mã đã nghiên cứu trong chương trước có thể gọi là các hệ mã khóa đối xứng (Symmtric Key Cryptosystems) do hai bên gửi và nhận tin đều thống nhất chung một khoá bí mật.
Các hệ này còn có các tên gọi khác là: Hệ mã với khóa sở hữu riêng (Private Key Cryptosystems) Hệ mã với khóa bí mật (Secret Key Cryptosystems) Hệ mã truyền thống (Conventional Cryptosystems) -- tuỳ theo các ngữ cảnh khác nhau. B KAB A KCD KAD KAC KBC C D KCD Điểm yếu của hệ mã đối xứng là: Vấn đề quản lý khoá (Tạo, lưu mật, trao chuyển .) là rất phức tạp và càng ngày càng khó khi sử dụng trong môi trường trao đổi tin giữa rất nhiều người dùng. Với số lượng user là n thì số lượng khoá cần tạo lập là n(n-1)/2. Mỗi người dùng phải tạo và lưu n-1 khoá bí mật để làm việc với n-1 người khác trên mạng.
Như vậy rất khó khăn và không an toàn khi n tăng lớn. Vấn đề thứ hai là trên cơ sở mã đối xứng, không thể thiết lập được khái niệm chữ ký điện tử (mà thể hiện được các chức năng của chữ ký tay trong thực tế) và cũng do đó không có dịch vụ non-repudiation 1 (không thể phủ nhận được) cho các giao dịch thương mại trên mạng. Vấn đề là ở chỗ trong mã hoá với khoá bí mật, thông tin mật đều được chia sẻ chung bởi cả hai bên Alice và Bob, do đó Alice có thể làm được bất kỳ cái gì mà Bob làm và ngược lại (chữ ký ở đây là mã hoá của tài liệu theo khoá đối xứng và do đó cả hai bên đều có thể tạo được, tức là không thoả mãn tính một chủ duy nhất như chữ ký tay thường). Giải pháp duy nhất cho vấn đề này là phải có thêm một thành phần thứ ba trong bất cứ giao dịch nào giữa 1 Dịch vụ non-repudiation cho phép trong mọi trường hợp của một quá trình giao dịch giữa hai bên Alice (A và B(Bob), mỗi bên đều có bằng chứng để chứng gian những trường hợp phía bên kia chối bỏ một giao dịch nào đó, chẳng hạn như Alice có thể cãi lấy cớ là một kẻ nào khác mạo nhận là mình để tiến hành giao dịch x nào đó với Bob từ trước.
Chương III - 1 - Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000 Alice và Bob, được gọi là trusted authorty, tức là một người có thẩm quyền mà cả Alice và Bob đều tin tưởng là trung thực. Người này sẽ làm chứng và trọng tài trong trường hợp xảy ra tranh cãi giữa hai bên trung thực. Người này sẽ làm chứng và trọng tài trong trường hợp xảy ra tranh cãi giữa hai bên Alice và Bob. Tuy nhiên theo sơ đồ thì công việc của người trọng tài này sẽ rất nặng vì phải tham gia vào tất cả các giao dịch của các bên, và sớm muộn cũng sẽ trở thành điểm quá tải về giao thông truyền tin cũng như tốc độ xử lý - bottleneck).
Diffie & Hellman trong các công trình của mình (1975-76) đã đề xuất những tư tưởng về một loại hệ mã với nguyên tắc mới, trong đó hệ mã được gắn với một user (người sử dụng) nhất định chứ không phải là gắn với một cuộc truyền tin giữa một cặp user. Trong hệ thống mới này, mỗi user có hai khoá, một được gọi là khoá bí mật (secret key hay private key) và một được gọi là khoá công khai (public key). Khoá thứ nhất chỉ mình user biết và giữ bí mật, còn khoá thứ hai thì anh ta có thể tự do phổ biến công khai. Khoá thứ nhất thường đi liền với thuật toán giải mã, còn khoá thứ hai thường đi liền với thuật toán sinh mã, tuy nhiên điều đó không phải là bắt buộc.
Ta hãy ký hiệu chúng là z (khóa riêng) và Z (khóa công khai) Hoạt động của chúng là đối xứng X = D(z, E(Z, X)) (1) và X = E(Z, D(z, X)) (2) Trong đó (1) được sử dụng cho truyền tin mật: B,C,D muốn gửi tin cho A chỉ việc mã hoá thông tin với khoá CK (ZA) của A rồi gửi đi. Chỉ có A mới có thể khoá riêng để giải mã (zA) và đọc được tin, E dù có nghe trộm cũng không thể giải mã để lấy được tin vì không có khoá zA. Hệ mã theo nguyên tắc nói trên được gọi là hệ mã với khoá công khai (public key cryptosystems - PKC) hay còn được gọi là mã phi đối xứng (asymmetric key cryptosystems). Nguyên tắc cấu tạo một hệ PK (trapdoor) Một hệ mã PKC có thể được tạo dựng trên cơ sở sử dụng một hàm kiểu one - way (1 chiều).
Một hàm f được gọi là one-way nếu: 1. Đối với mọi X tính ra Y = f(X) là dễ dàng. Khi biết Y rất khó để tính ra X. Cho n số nguyên tố p1, p2, .pn ta có thể dễ dàng tính được N = p1 * p2 *.
* pn, tuy nhiên khi biết N, việc tìm các thừa số nguyên tố của nó là khó khăn hơn rất nhiều, đặc biệt là khi N lớn và các thừa số nguyên tố của nó cũng lớn. Chương III - 2 - Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000 Chúng ta cần một hàm one-way đặc biệt mà có trạng bị một trap door (cửa bẫy), sao cho nếu biết trap- door này thì việc tính X khi biết f(X)( tức là đi tìm nghịch đào của f) là dễ dàng, còn ngược lại thì vẫn khó như thường. Một hàm one-way có trap door như thế có thể dùng để tạo ra một hệ mã PKC. Lấy Ez (hàm sinh mã) là hàm one- way có trap-door.
Trap- door chính khoá mật, mà nếu biết nó thì có thể dễ dàng tính được cái nghịch đảo của Ez tức là biết Dz, còn nếu không biét thì rất khó tính được. Sau đây chúng ta sẽ khảo sát hai ví dụ về việc xây dựng trap-door cho một hàm one-way. Ví dụ đầu tiên là một cố gắng nhưng thất bại, hệ Trapdoor Knapsack. Ví dụ thứ hai là một hệ đã thành công và rất nổi tiếng, đó là hệ RSA.
Trapdoor Knapsack dựa trên bài toán đóng thùng 1978, hai ông Merkle - Hellman đã đề xuất một thuật toán mã hoá theo mô hình PKC dựa trên bài toán ĐÓNG THÙNG như sau: Cho 1 tập hợp các số dương ai, 1≤i≤n và 1 số T dương. Hãy tìm 1 tập hợp chỉ số S ⊂ {1,2,.,n } sao cho: ∑ ai = T i∈S Bài toán này là một bài toán khó, theo nghĩa là chưa tìm được thuật toán nào tốt hơn là thuật toán thử-vét cạn và như vậy thời gian xử lý sẽ được tính theo luỹ thừa với số mũ là số lượng n số dương cho trước. Như vậy ta có 2 đáp số S = (1, 3) và S = (4). Từ bài toán đóng thùng này chúng ta sẽ khảo sát các khả năng vận dụng để tạo ra thuật toán mã khối PKC.
Sơ đồ đầu tiên như sau: Chọn một vector a = (a1, a2,. , an) - được gọi là vector mang (cargo vector) Với một khối tin X = (X1,X2,X3 ., Xn), ta thực hiện phép mã hoá như sau: T= ∑ aiXi (*) i=1,n Việc giải mã là: Cho mã T, vector mang a, tìm các Xi sao cho thoả mãn (*). Trong sơ đồ này thể hiện một hàm one-way với việc sinh mã rất dễ dàng nhưng việc giải mã là rất khó. Bây giờ ta phải tìm cách xây dựng một trapdoor để việc giải mã có thể làm được dễ dàng.
Merkle sử dụng một mẹo là áp dụng một vector mang đặc biệt là vector siêu tăng (super- increasing), trong đó thành phần i+1 là lớn hơn tổng giá trị của các thành phần đứng trước nó (1÷i). Khi đó việc giải mã có thể diễn ra dễ dàng như ví dụ bằng số sau: Ví dụ: Chương III - 3 - Nguyễn Khanh Văn Mật mã và An toàn Thông tin ĐHBKHN-2000 Vector mang siêu tăng: a=(1,2,4,8) Cho T=14, ta sẽ thấy việc tìm X=(X1,X2,X3,X4) sao cho T= ∑ aiXi là dễ dàng: Đặt T=T0 X4=1 T1=T0-X4=6 Î (X1 X2 X3 1) X3=1 T2=T1-X3=2 Î (X1 X2 1 1) X2=1 T3=T2-2=0 Î (X1 1 1 1) X1= 0 Î (0 1 1 1) Bài toán được giải quyết dần qua các bước. Ở bước i, tổng đích là Ti (tức là phải tìm các aj để tổng bằng Ti). Ta đem so sánh Ti với thành phần lớn nhất trong phần còn lại của vector, nếu lớn hơn thì thành phần này được chọn tức là Xi tương ứng bằng 1, còn ngược lại thì Xi tương ứng bằng 0.