Khóa luận Nghiên cứu một số giao thức chia sẻ bí mật và ứng dụng

à một hàm giải mã dk є D dk: C → P sao cho dk(ek(x)) = x với mọi x є P Trong thực tế, P và C thường là bảng chữ cái (hoặc tập các dãy chữ cái). * Các loại mã hóa: có 2 loại: - Mã khóa đối xứng bao gồm: + Mã cổ điển. + Mã hiện đại. - Mã khóa công khai. 1.2.2. Mã cổ điển 1.2.2.1. Mã dịch chuyển Định nghĩa: Mã dịch chuyển: (P, C, K, E, D) P = C = K = Z26 với k є K, định nghĩa ek(x) = (x + k) mod 26 , dk(y) = (y – k) mod 26 (x, y є Z26) 1.2.2.2. Mã thay thế Định nghĩa: Mã thay thế: (P, C, K, E, D) P = C = Z26, K = S (Z26) Với mỗi π є K, tức là một hoán vị trên Z26, ta xác định eπ(x) = π(x) dπ(y) = π -1(y) với x, y є Z26, π -1 là nghịch đảo của π 1.2.2.3. Mã Affine Định nghĩa: Mã Affine: (P, C, K, E, D) P = C = Z26, K = { (a, b) є Z26 x Z26 : (a, 26) = 1 } với mỗi k = (a, b) є K ta định nghĩa: ek(x) = ax + b mod 26 dk(y) = a-1(y – b) mod 26 trong đó x, y є Z26 Với mã Affine, số các khoá có thể có bằng (số các số ≤ 26 và nguyên tố với 26) × 26, tức là 12 × 26 = 312. Việc thử tất cả các khoá để thám mã trong trường hợp này tuy khá mất thì giờ nếu tính bằng tay, nhưng không khó khăn gì nếu dùng máy tính. Do vậy, mã Affine cũng không phải là mã an toàn. 1.2.2.4. Mã Vingenere Định nghĩa: Mã Vigenere: (P, C, K, E, D) Cho m là số nguyên dương. P = C = K = (Z26)m với mỗi khoá k = (k1, k2,,km) є K có: ek(x1, x2,, xm) = (x1 + k1, x2 + k2,, xm + km) dk(y1, y2,, ym) = (y1 – k1, y2 – k2,, ym – km) các phép cộng phép trừ đều lấy theo modulo 26 Chú ý: Mã Vigenere với m = 1 sẽ trở thành mã Dịch chuyển. Tập hợp các khoá trong mã Vigenere mới m ≥ 1 có tất cả là 26m khoá có thể có. duyệt toàn bộ chừng ấy khoá để thám mã bằng tính tay thì khó, nhưng với máy tính thì vẫn là điều dễ dàng. 1.2.2.5. Mã Hill Định nghĩa: Mã Hill: (P, C, K, E, D) Cho m là số nguyên dương. P = C = (Z26)m K = { k є (Z26) m x m : (det(k), 26) = 1 } với mỗi k є K định nghĩa: ek(x1, x2,, xm) = (x1, x2,, xm).k dk(y1, y2,, ym) = (y1, y2,,ym).k-1 1.2.2.6. Mã hoán vị Định nghĩa: Mã hoán vị: (P, C, K, E, D) Cho m là số nguyên dương. P = C = Z26 , K = Sm với mỗi k = π є Sm , ta có trong đó π-1 là hoán vị nghịch đảo của π 1.2.3. Hệ mã khóa công khai 1.2.3.1. Hệ mã RSA Hệ mật này sử dụng tính toán trong Zn, trong đó n là tích của 2 số nguyên tố phân biệt p và q. Ta thấy rằng f(n) = (p – 1).(q – 1). Định nghĩa Cho n = p.q trong đó p và q là các số nguyên tố. Đặt P = C = Zn và định nghĩa: K = {(n, p, q, a, b): n = p.q, p, q là các số nguyên tố, a.b º 1 mod f(n)} Với K = (n, p, q, a, b) ta xác định: eK = xb mod n và dK = ya mod n (x, y Î Zn). Các giá trị n và b được công khai và các gia trị p, q, a được giữ kín. 1.2.3.2. Mã Elgamal Mô tả hệ mã Elgamal Hệ mật mã ElGamal được T. ElGamal đề xuất năm 1985, dựa vào độ phức tạp của bài toán tính lôgarit rời rạc, và sau đó đã nhanh chóng được sử dụng rộng rãi không những trong vấn đề bảo mật truyền tin mà còn trong các vấn đề xác nhận và chữ ký điện tử. Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ thể là không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời rạc. Để gây khó khăn cho các phương pháp tấn công đã biết, p phải có ít nhất 150 chữ số và (p – 1) phải có ít nhất một thừa số nguyên tố lớn. Hệ mật Elgamal là một hệ mật không tất định vì bản mã phụ thuộc vào cả bản rõ x lẫn giá trị ngẫu nhiên k do G chọn. Bởi vậy sẽ có nhiều bản mã được mã từ cùng một bản rõ. Bài toán logarithm rời rạc trong Zp: Đặc trưng của bài toán: I = (p, a, b) trong đó p là số nguyên tố, a Î Zp là phần tử nguyên thuỷ (hay phần tử sinh), b Î Zp* Mục tiêu: Hãy tìm một số nguyên duy nhất a, 0 £ a £ p – 2 sao cho: aa º b (mod p) Ta sẽ xác định số nguyên a bằng log a b. Định nghĩa mã hoá công khai Elgamal trong Zp*: Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Cho a Î Zp* là phần tử nguyên thuỷ. Giả sử P = Zp*, C = Zp* x Zp*. Ta định nghĩa: K = {(p, a, a, b): b º aa (mod p)} Các giá trị p, a, b được công khai, còn a giữ kín. Với K =(p, a, a, b) và một số ngẫu nhiên bí mật k Î Zp – 1, ta xác định: eK(x, k) = (y1, y2). Trong đó: y1 = ak mod p y2 = x. bk mod p với y1, y2 Î Zp* ta xác định: dK(y1, y2) = y2(y1a) – 1 mod p Chương 2. VẤN ĐỀ “CHIA SẺ BÍ MẬT” 2.1. KHÁI NIỆM “CHIA SẺ BÍ MẬT”. Thông tin cần giữ bí mật (tin gốc: TG) được chia thành nhiều mảnh (TM) và trao cho mỗi người giữ một hay một số mảnh. Thông tin này có thể được xem lại, khi mọi nguời giữ các mảnh đều nhất trí. Các mảnh TM được khớp lại để được tin gốc TG. - Thông tin cần giữ bí mật (tin gốc: TG) được chia thành nhiều mảnh (TM) và trao cho mỗi thành viên tham gia nắm giữ. Thông tin bí mật các mảnh được chia - Thông tin bí mật được xem lại, khi các mảnh TM được khớp lại sẽ được tin gốc TG. Các mảnh được chia Thông tin bí mật Ví dụ: Có một khóa bí mật, nó quy định truy cập tới một file quan trọng, nếu khóa bí mật bị mất (có thể do người giữ khóa không đáng tin cậy, hoặc máy tính có bộ nhớ lưu giữ khóa bị phá hủy), thì file quan trọng trở thành không truy cập được. Một câu hỏi đặt ra là làm thế nào để khôi phục lại thông tin bí mật, vì vậy thông tin bí mật không nên do một người duy nhất nắm giữ. Có các cách sau để chia sẻ thông tin mật: + Chia khóa bí mật thành các phần và phân phối các phần đến từng người là khác nhau, vì vậy nó phải chắc chắn tập con của những người này có thể cùng nhau tìm lại được khóa. + Chia dữ liệu thành vài đoạn dữ liệu và đưa cho nhiều người, vì vậy khôi phục lại đầy đủ dữ liệu dựa vào các đoạn này. Ví dụ, dữ liệu là file có tên là X và các đoạn dữ liệu là X1,X2,X3, XOR của chúng sẽ khôi phục lại X, phương thức này đạt được an toàn. Tuy nhiên, chúng ta cần tất cả 3 đoạn để khôi phục lại file. Phương pháp “chia sẻ bí mật” được thể hiện bằng “sơ đồ ”, chỉ rõ cách thức “chia sẻ bí mật” và cách thức “khớp lại ” các mảnh bí mật. 2.2. SƠ ĐỒ CHIA SẺ BÍ MẬT 2.2.1. Khái niệm “sơ đồ chia sẻ bí mật”. Sơ đồ “chia sẻ bí mật” là một phương thức để chia sẻ một bí mật ra nhiều phần, sau đó phân phối cho một tập hợp những người tham gia, sao cho các tập con nào đó trong số những người này được chỉ định, có khả năng khôi phục lại bí mật bằng cách kết hợp dữ liệu của họ. Một sơ đồ chia sẻ bí mật là hoàn hảo, nếu bất kì một tập hợp những người tham gia mà không được chỉ định, sẽ tuyệt đối không thu được thông tin về bí mật. Ví dụ: Khi một cá nhân hoặc một tổ chức đáng tin cậy được ủy quyền phân phối khóa cho một tập các thành viên, họ phải đáp ứng yêu cầu: có một khóa bí mật, làm sao mỗi người giữ một bộ phận của khóa, khi những thành viên được chỉ định trước có thể tính ra khóa, những tập con thành viên khác thì không thể tính ra khóa được. Một sơ đồ phân phối khóa thỏa mãn yêu cầu trên là một sơ đồ chia sẻ bí mật. - Mô hình của sơ đồ chia sẻ bí mật là: 2.2.2. Các thành phần của sơ đồ chia sẻ bí mật: + Người phân phối bí mật (Dealer): là người trực tiếp chia bí mật ra thành nhiều phần. + Những người tham gia nhận dữ liệu từ Dealer, kí hiệu P. + Nhóm có khả năng nhận dữ liệu, sau đó khôi phục được bí mật: là tập con của P, trong đó có các tập con có khả năng khôi phục bí mật. Ví dụ: Trong bỏ phiếu điện tử thì mỗi cử tri sẽ đóng vai trò là một Dealer, trong khi mỗi người kiểm phiếu sẽ đóng vai trò là người tham gia. 2.2.3. Giao thức trong sơ đồ chia sẻ bí mật. Mọi sơ đồ “chia sẻ bí mật” đều tồn tại ít nhất 2 giao thức. Đó là: + Giao thức phân phối thông tin bí mật: Bí mật được Dealer phân phối tới tập những người tham gia. + Giao thức khôi phục thông tin bí mật: Trong đó thông tin bí mật được khôi phục lại bằng các gộp thông tin của những người tham gia nằm trong một tập hợp được chỉ định trước. 2.3. MỘT SỐ ỨNG DỤNG CỦA “CHIA SẺ BÍ MẬT” . “Chia sẻ bí mật” được sử dụng trong trường hợp cần giữ bí mật các thông tin quan trọng và không thể tin tưởng bất kì người nào cả. Một vài ứng dụng phổ biến của “chia sẻ bí mật” là: - Mật khẩu (passwords) tốt là khó có thể ghi nhớ. Một người sử dụng thông minh sẽ sử dụng 1 sơ đồ chia sẻ bí mật để sinh ra 1 tập hợp của các phần để chuyển thành mật khẩu và lưu từng phần trong quyển địa chỉ của anh ta hoặc gửi các phần ở nơi khác nhau. Mật khẩu đó có thể là khóa để lấy tiền trong ngân hàng của anh ta, Nếu một ngày anh ấy quên mật khẩu, anh ta có thể khôi phục 1 cách dễ dàng. Dĩ nhiên, nếu viết mật khẩu ngay trong sổ nhật ký sẽ đưa ra 1 sự đảm bảo nguy hiểm, như vậy sẽ bị kẻ thù ăn cắp. Nếu một sơ đồ chia sẻ bí mật được sử dụng, kẻ tấn công sẽ phải lấy trộm nhiều phần từ nhiều nơi khác nhau. -Một ứng dụng tiêu biểu của “chia sẻ bí mật” là sử dụng trong hệ thống lập mã. Khóa mật mã được công khai, trong khi khóa khôi phục được giữ bí mật và được bảo vệ theo đường chia sẻ bí mật. - Một Dealer có thể gửi t phần, tất cả những phần đó là cần thiết để khôi phục lại nguyên bản bí mật, tới từng người nhận, sử dụng t kênh truyền khác nhau. Một kẻ tấn công có thể chặn tất cả t phần để khôi phục lại bí mật, một tác vụ này khó hơn nhiều so với chặn từng thông điệp. - “chìa khóa” mở két bạc là “chìa khóa số”. Chìa khóa mở két được chia thành 3 mảnh khóa đưa cho 3 người quan trọng, mỗi người giữ một mảnh khóa. Mảnh khóa này không thể mở được két, chỉ mở được khi 2 trong 3 người nhất trí mở, họ khớp 2 mảnh khóa lại với nhau, sẽ nhận được chìa khóa gốc để mở két. - Dùng phương pháp “chia sẻ bí mật” để chia nhỏ lá phiếu trong bỏ phiếu điện tử. Trên thực tế nhiều khi người ta chưa thật tin vào một nhóm ít người trong ban kiểm phiếu, người bỏ phiếu được phép chia lá phiếu thành nhiều mảnh phiếu, sau đó gửi cho mỗi người trong ban kiểm phiếu một mảnh. Như vậy từng thành viên trong ban kiểm phiếu khó thể đọc được nội dung lá phiếu. Khi mọi thành viên trong ban kiểm phiếu nhất trí xem nội dung lá phiếu, thì các mảnh phiếu mới được khớp lại để có được lá phiếu ban đầu của người bỏ phiếu. Chia nhỏ lá phiếu có thể hiểu theo nhiều nghĩa: Có thể là chia khóa bí mật để giải mã nội dung lá phiếu; Có thể chính là nội dung lá phiếu (tên, mã số ứng cử viên, ý kiến đồng ý hay không đồng ý,) được chia thành các mảnh tin (trên thực tế bản thân mỗi mảnh tin đều không có nghĩa). 2.4. MỘT SỐ PHƯƠNG PHÁP “CHIA SẺ BÍ MẬT” 2.4.1. Giao thức “chia sẻ bí mật” Shamir. 2.4.1.1. Khái niệm sơ đồ ngưỡng A(t, m). Cho t, m là các số nguyên dương, t m. Sơ đồ ngưỡng A(t, m) là phương pháp phân chia khóa K cho một tập P gồm m thành viên Pi, sao cho t thành viên bất kỳ có thể tính được giá trị K, nhưng không một nhóm gồm (t-1) thành viên nào có thể làm được điều đó. Ví dụ: Có 3 thủ quỹ giữ két bạc. Hãy xây dựng sơ đồ “chia sẻ bí mật”, sao cho t=2 thủ quỹ nào cũng có thể mở được két bạc, nhưng từng người một riêng rẽ thì khó có thể. Đó là sơ đồ ngưỡng A(2, 3). Cho đơn giản ta xem người phân phối khóa D không thuộc nhóm P. Khi D muốn phân chia khóa K cho các thành viên trong P, người đó sẽ cho mỗi thành viên một thông tin “cục bộ” nào đó về K, được gọi là các “mảnh khóa”. Các mảnh khóa được phân phát một cách bí mật, để không một thành viên nào biết được mảnh khóa của thành viên khác. Sơ đồ ngưỡng của Sharmir được đưa vào năm 1979. Sơ đồ ngưỡng A(t, t) trong Zm là một trường hợp đặc biệt khi t=m. Tức là tất cả mọi thành viên phải cùng nhau, thì mới suy ngược lại được bí mật. * Chia sẻ khóa bí mật K. - D chọn một cách bí mật (độc lập và ngẫu nhiên) (t-1) phần tử của Zm: y1, , y t-1 - D tính yi = K - yj với 1 i t, trao mảnh yi cho Pi. * Khôi phục khóa bí mật K. t thành viên cùng hợp tác, có thể tính K theo công thức: K = yi - yj * Hạn chế của giao thức: “chia sẻ bí mật” Sharmir. Giao thức “chia sẻ bí mật” Sharmir giải quyết vấn đề an toàn trong trường hợp tất cả những người tham gia trong sơ đồ là trung thực. Trong trường hợp một hoặc nhiều người trong sơ đồ không trung thực thì sơ đồ không còn tác dụng nữa. Những người trong sơ đồ không trung thực có thể là: - Dealer gửi thông tin sai đến cho một hoặc nhiều người trong sơ đồ. - Người tham gia cung cấp sai thông tỉn trong thủ tục khôi phục bí mật. 2.4.1.2. Giao thức “chia sẻ bí mật” Sharmir. Sơ đồ chia sẻ bí mật của Shamir là một sơ đồ ngưỡng cơ bản dựa trên đa thức nội suy. Nó cho phép một “người phân phối” D (dealer) phân phối một bí mật K cho m người. Và tối thiểu t<n người là cần thiết để khôi phục lại bí mật. Giao thức chia sẻ bí mật của Shamir đảm bảo bí mật được an toàn. Tức là, ít hơn t người không thể thu được thông tin về bí mật. - Mô hình sơ đồ chia sẻ bí mật của Shamir: +Chia sẻ khóa bí mật: Kết qua sau khi chia khóa + Khôi phục khóa bí mật: a/. Chia sẻ khóa bí mật K. * Mục đích: để chia sẻ bí mật K cho mỗi thành viên tham gia P1,P2,..,Pm, và t thành viên là cần thiết để khôi phục lại bí mật. - D chọn số nguyên tố P và m phần tử xi (1≤ i ≤m) khác nhau – khác 0 trong Zp, xi là công khai. D trao giá trị xi cho mỗi thành viên Pi. - Để chia mảnh khóa K є Zp, D chọn bí mật, ngẫu nhiên t-1 phần tử của Zp là a1,,at-1, lập đa thức trong Zp là P(x)=K + với 1≤i≤m, D tính yi =P(xi), và trao mảnh yi cho Pi. Chú ý đa thức P(x) có bậc tối đa là t-1, thành phần hằng số là khóa bí mật K. Mỗi thành viên Pi sẽ có một điểm (xi,yi) trên đa thức. Ví dụ : Chia mảnh khóa bí mật K=11 Khóa K=11 cần chia thành 4 mảnh cho 4 người P1,P2,P3,P4. Khi kết hợp 3 trong 4 mảnh khóa này thì có thể khôi phục được bí mật. - Chọn số nguyên tố P=13, chon m=4, phần tử xi=i trong Zp, i=1,2,3,4. D trao giá trị công khai xi cho Pi. - D chọn bí mật t-1=2 phần tử trong Zp: a1=6, a2=2. Lập đa thức P(x)=K + = 11 + a1x + a2x2 D tính yi = P(xi), 1≤i≤m, trao mảnh yi cho Pi. y1 = P(x1) = P(1) = 11 + a1.1+a2.12 = 11 + 6.1 +2.12 =19 y2 = P(x2) = P(2) = 11 + a1.2+a2.22 = 11 + 6.2 +2.22 = 31 y3 = P(x3) = P(3) = 11 + a1.3+a2.32 = 11 + 6.3 +2.32 = 47 y4 = P(x4) = P(4) = 11 + a1.4+a2.42 = 11 + 6.4 +2.42 = 67 b/. Khôi phục khóa bí mật K. * Mục đích: khôi phục lại bí mật từ các mảnh khóa đã trao cho tập con các thành viên t . Có 2 phương pháp: Giải hệ phương trình tuyến tính và dùng công thức nội suy Lagrangre. * Phương pháp 1: Giải hệ phương trình tuyến tính khôi phục K. Giải hệ phương trình tuyến tính t ẩn số, t phương trình. Giả sử các thành viên Pi1,,Pit muốn xác định khóa K. Biết yij = P(xij), 1≤j≤t, trong đó P(x) Zp[x] là đa thức do phân phối khóa D chọn Vì P(x) có bậc lớn nhất là (t-1) nên có thể viết: P(x) = a0 + a1x ++ at-1 xt-1 Trong đó các hệ số a0,a1,,at-1 là chưa biết của Zp, còn a0=K là khóa Vì yij = P(xij) nên ta có hệ phương trình tuyến tính t ẩn số, t phương trình Chú ý ở đây các phép tính số học đều thực hiện trên Zp. Nếu các phương trình độc lập tuyến tính, thì sẽ có nghiệm duy nhất, trong đó giá trị khóa a0=K. Ví dụ: Khôi phục khóa bí mật K. Biết số nguyên tố P=13, phần tử xi=i trong Zp, i=1,2,3 D trao giá trị công khai xi cho pi. Giả sử nhóm thành viên giữ các “mảnh khóa” sẽ kết hợp các mảnh của họ tương ứng là y1=19, y2=31, y3=47. Có P(x)=K + = 11 + a1x + a2x2 Các phương trình cụ thể trong Z13 là: a0 + a1 + a2 = 19 a0 + 2a1 + 4a2 = 31 a0 + 3a1 + 9a2 =47 Hệ này có nghiệm duy nhất trong Z13 là: a0 = 11, a1 = 6, a2 = 2. Như vậy, khóa được khôi phục lại là: K = a0 = 11. * Phương pháp 2: Dùng công thức nội suy Lagrangre khôi phục K. P(x)=yij ∏1≤ k ≤t, k ≠ j ( x – xik) / ( xij – xik ). Mà yij = P(xij), 1≤j≤t Nên K = P(0) = yij ∏1≤ k ≤t, k ≠ j ( 0 – xik ) / (xij – xik ) Ta đặt: bj= ∏1≤ k ≤t, k ≠ j ( – xik ) / (xij – xik ) Khi đó: K= yij bj Ví dụ : Khôi phục khóa bí mật K=11. B={P1, P2, P3} cần kết hợp các mảnh khóa của họ y1 = 19, y2 = 31, y3 = 47 Để khôi phục lại khóa K, ta tính: bj= ∏1≤ k ≤t, k ≠ j ( – xik ) / (xij – xik ) Ta có: x2 x3 2 3 b1 = ---------- * --------- = -------- * --------- = 3 (x2 – x1) (x4 – x1) 2 – 1 3 – 1 x1 x3 1 3 b2 = ---------- * --------- = -------- * --------- = -3 (x1 – x2) (x3 – x2) 1 – 2 3 – 2 x1 x2 1 2 b3 = ---------- * --------- = -------- * --------- = 1 (x1 – x3) (x2 – x3) 1 – 3 2 – 3 Ta có: K = 19 * 3 + 31 * (-3) + 47 * 1 = 11 Vậy khóa K cần tìm là 11. 2.4.1.3. Ưu điểm của giao thức chia sẻ bí mật của Shamir. 1/. Giao thức “chia sẻ bí mật” Shamir đảm bảo an toàn cho thông tin cần giữ bí mật: +Căn cứ vào các mảnh khóa đã trao cho tập con t thành viên ta có thể khôi phục được bí mật. Tuy nhiên, nếu căn cứ vào các mảnh khóa đã trao t-1 thành viên hoặc ít hơn t-1 thành viên, thì bí mật có thể là bất cứ số nào trong giới hạn, và như vậy khi kết hợp t-1 mảnh khóa không dẫn tới việc thêm bất cứ thông tin nào về bí mật. Điều này sẽ giúp cho khi mà t-1 các mảnh khóa đã bị tiết lộ, nhưng chỉ cần mảnh khóa thứ t không bị tiết lộ thì thông tin bí mật vẫn an toàn. + Giả sử khi gặp rủi ro bị phá hủy một phần các mảnh khóa, nhưng chỉ cần số mảnh khóa còn lại không nhỏ hơn t, thì bí mật vẫn có thể khôi phục lại dược. 2/. Các mảnh khóa nhờ một cách đơn giản có thể đễ dàng được tạo ra, bởi do có đa thức tính toán tốt trong kết hợp các giá trị. 3/. Có thể linh hoạt trong chia sẻ khóa bí mật. Tức là, có thể chọn ngẫu nhiên các hệ số a1,,at-1, trong các phần tử của Zp, và có thể chia các mảnh khóa khác nhau cho những người khác nhau. 4/. Thuận tiện khi sử dụng: Nếu không sử dụng sơ đồ thì khóa là khóa đơn, phải được đặt ở vị trí an toàn nhất và bảo vệ tốt nhất,nếu gặp một sự rủi ro (như máy tính hỏng, người giữ khóa bị mất, hoặc gặp sự phá hoại) thì thông tin không thể truy cập vào được, do đó phải lưu trữ nhiều bản sao của khóa ở nhiều nơi, như vậy rất tốn nhiều công sức để bảo vệ khóa, nhưng với “chia sẻ bí mật” thì không cần phải làm điều này. 2.4.2. Giao thức chia sẻ bí mật bằng mạch đơn điệu. 2.4.2.1. Khái niệm mạch đơn điệu. Giả sử ta không muốn tất cả các tập con t thành viên bất kỳ đều có khả năng tính được khóa K, mà chỉ một số tập con thành viên chỉ định trước có thể làm được điều đó. Ví dụ : “chìa khóa” mở két bạc là “chìa khóa số”, được chia thành 3 mảnh khóa, có 3 thủ quỹ kinh nghiệm là P1, P2, P3. Mỗi thủ quỹ chỉ được giữ một mảnh khóa. Chỉ có thủ quỹ P1 và P2 hoặc P2 và P3 khi khớp 2 mảnh khóa của họ với nhau thì sẽ nhận được chìa khóa gốc để mở két bạc. Cấu trúc mạch đơn điệu là một giải pháp cho yêu cầu trên. - Ký hiệu: +P là tập gồm m thành viên được chia mảnh công khai xi. Tập con các thành viên có thể tính được khóa K gọi là tập con hợp thức. +Ґ là một họ các tập con hợp thức, Ґ được gọi là một cấu trúc truy nhập. Ґ là họ các tập con của P, mà mỗi tập con cá thành viên này có khả năng tính K. Ví dụ : Từ ví dụ 1 ta có : Tập các thành viên là: {P1, P2, P3} chỉ có các tập con sau có thể mở khóa là: {P1, P2},{P2, P3} thì đó là tập con hợp thức. Ở đây Ґ là: {P1, P2},{P2, P3}. Định nghĩa: Một sơ đồ chia sẻ bí mật được gọi là hoàn thiện nếu thỏa mãn điều kiện: +Nếu một tập con hợp thức các thành viên B P góp chung ác mảnh khóa của họ , thì có thể xác định được khóa K. +Nếu một tập con không hợp thức các thành viên B P góp chung các mảnh khá của họ, thì khó thể xác định được khóa K. Ví dụ: Sơ đồ Shamir A(t, m) thể hiện “ cấu trúc truy nhập” sau: Ґ={B P: /B/t} Như vậy sơ đồ Shamir là sơ đồ chia sẻ bí mật “hoàn thiện”. Chú ý: “Tập trên” của “tập hợp thức” sẽ lại là “tập hợp thức”. Tức là: Nếu B Ґ, và B C P, thì C Ґ. Điều trên nói rằng “cấu trúc truy nhập” Ґ phải thỏa mãn tính chất đơn điệu. Định nghĩa B Ґ được gọi là “tập hợp thức” tối thiểu nếu C B, CB thì C Ґ. Nói cách khác B là “tập hợp thức ” nhỏ nhất trong Ґ. Tập mọi tập con “tập hợp thức” tối thiểu của Ґ được gọi là tập cơ sở,ký hiệu là Ґ0. Như vậy có thể biểu diễn Ґ={ B P / C B , C Ґ 0 } Ví dụ: Trong sơ đồ A(t, m), tập cơ sở gồm tất cả các tập con chứa đúng t thành viên. Định nghĩa (Mạch đơn điệu): Cho C là mạch Boolean (Công thức logic) với m đầu vào (biến logic). X1, X2, , Xm (tương ứng với m thành viên P1, P2, ,Pm) và 1 đầu ra (biến logic) Y. Mạch này chỉ gồm các cổng “hoặc” và các cổng “và”. Mạch C như trên được gọi là mạch đơn điệu. *Xây dựng mạch đơn điệu: Cho Ґ là tập đơn điệu các tập con của P, trong đó Ґ0 là tập cơ sở của Ґ.Khi đó ta xây dựng công thức Boolean dạng tuyển hội sau: C=Pi (B là tập hợp thức tối thiểu) Đó là mạch đơn điệu. Ví dụ : Nếu trong tập các thành viên {P1,P2,P3} có tập cơ sở Ґ0 = {{P1, P2},{P2, P3}} Vậy công thức Boolean sau là mạch đơn điệu: C = (P1 ^ P2) ‏۷ (P2 ‏۷P3) 2.4.2.2. Chia sẻ khóa bí mật K dựa vào “mạch đơn điệu” Thuật toán thực hiện phép gán một giá trị f(W) є K cho mỗi dây W trong mạch C. + Đầu tiên, dây ra Wout của mạch sẽ được gán giá trị khóa K. + Thuật toán sẽ lặp lại một số lần cho đến khi mỗi dây có một giá trị gán vào nó. + Cuối cùng, mỗi thành viên Pi sẽ được một danh sánh các giá trị f(W) sao cho W là một dây vào của mạch có đầu vào xi. Thuật toán “chia sẻ” khóa K 1/. f(Wout) = K 2/. WHILE tồn tại một dây W sao cho f(W) không được xác định DO Begin 3/. Tìm cổng G của C sao cho f(Wg) được xác định, Wg là dây ra của G nhưng f(W) không được xác định với bất kỳ dây nào của G. 4/. If G là cổng “hoặc” Then f(W) = f(Wg) với mỗi dây vào W của G Else (tl: G là cổng “và”) Cho các dây vào của G là W1,, Wt Chọn độc lập , ngẫu nhiên t-1 phần tử của Zm và ký hiệu chúng là: Yg,1,,Yg,t-1 Tính Yg,t = f(Wg) - Yg,I End; 5/. For 1≤i≤m Do f(Wi) = Yg, Ví dụ : Dựa vào ví dụ 1 -Chia sẻ khóa bí mật K = 11, ta có mạch đơn điệu như sau: ‏۷ ^ ^ X1 X2 X3 K=11 K K 2 K-2=9 K-8=3 8 Căn cứ vào mạch đơn điệu trên ta có: P1 nhận 2 làm “mảnh khóa” của mình (Ứng với X1). P2 nhận 9,8 làm “mảnh khóa” của mình (Ứng với X2). P3 nhận 3 làm “mảnh khóa” của mình (Ứng với X3). - Khôi phục khóa bí mật K: Khi đa biết P1 nhận 2 làm mảnh khóa, P2 nhận9,8 làm mảnh khóa, P3 nhận 3 làm mảnh khóa . + Tập con {P1,P2} có thể tính khóa K = 2+9=11 + Tập con {P2,P3} có thể tính khóa K = 8+3=11 Nhận xét: Sơ đồ trong ví dụ trên là hoàn thiện: +Ta thấy mỗi tập con hợp thức có thể tính được khóa K. Đó là tập {P1,P2},{P2,P3} +Trong khi tập con không hợp thức tối đa không tính được K. Đó là tập {P1,P3} 2.4.2.3. Ưu điểm của giao thức “chia sẻ bí mật” bằng “mạch đơn điệu”. - Giao thức “chia sẻ bí mật” bằng mạch đơn điệu đảm bảo an toàn cho các thông tin cần giữ bí mật: + Trong giao thức “chia sẻ bí mật” bằng “mạch đơn điệu” thì chỉ một số tập con các thành viên chị định trước mới có thể khôi phục được khóa. Do đó khi một số mảnh khóa được tiết lộ, thì cũng chưa chắc đã thu được khóa, và rất khó có thể đoán ra,vì vậy bí mật có thể là bất cứ số nguyên tố nào trong giới hạn, và như vậy các mảnh khóa trên không dẫn tới việc thêm bất cứ thông tin nào về bí mật. Chương 3. THỬ NGHIỆM LẬP TRÌNH “CHIA SẺ BÍ MẬT” 3.1. CÔNG NGHỆ Ngôn ngữ lập trình là ngôn ngữ C, theo phương pháp lập trình hướng đối tượng. Chạy trên máy tính cài hệ điều hành (Window, Linux,) có cài trình duyệt. 3.2. CÁC THÀNH PHẦN CỦA CHƯƠNG TRÌNH. Chương trình gồm có 5 phần: 1/. Chia sẻ khóa bí mật theo giao thức “chia sẻ bí mật” Shamir. void giaothuc::chiakhoa() { int h; cout>k; cout>p; cout>m; cout>t; cout<<"\n Nhap gia tri xi de chao cho moi thanh vien P:"; for (i=1;i<=m;i++) { cout>x[i]; } cout<<"\n Nhap bi mat t-1 phan tu trong Zp"; for (j=1;j<t;j++) { cout>a[j]; } for (i=1;i<=m;i++) { l=0; for (j=1;j<t;j++) { h=pow(x[i],j); l=l+a[j]*h; } y=k+l; cout<<"\n Manh y"<<i<<" trao cho thanh vien P"<<i<<" la:"<<y; } } 2/. Khôi phục khóa bí mật bằng giải hệ phương trình tuyến tính. void giaothuc::giaihekhoiphuckhoa() { int n,m,v,b; float mx=0,g,e,c,gt,h; float G[max][max],H[max][max],A[max][max],B[max][max],M[max][max]; cout>p; cout>n; cout<<"\n Nhap gia tri xi da chao cho moi thanh vien P:"; for (j=0;j<n;j++) { cout>x[j]; } cout<<"\n Nhap cac manh khoa da chao cho moi thanh vien P:"; for (l=0;l<n;l++) { cout>B[l][0]; } for (i=0;i<n;i++) { for (j=0;j<n;j++) { A[i][j]=pow(x[i],j); } } cout<<"\n He phuong trinh tuyen tinh la:\n"; for (i=0;i<n;i++) { for (j=0;j<n;j++) { if (j<n-1) { cout<<A[i][j]<<"a"<<j<<"+"; } if (j==n-1) { cout<<A[i][j]<<"a"<<j; } } cout<<"="<<B[i][0]; cout<<"\n"; } cout<<"\n Vay nghiem cua he phuong trinh la:"; for (e=0;e<=n;e++) { for (i=0;i<n;i++) { for (j=0;j<n;j++) { G[i][j]=A[i][j]; } } for (j=0;j<n;j++) { if (j==e-1) { for (i=0;i<n;i++) { G[i][j] =B[i][0]; } } } i=0;t=0; while (t<n-1) { if (G[i][i]==0) { for (j=1;j<n;j++) if (G[j][i]>mx) { mx=G[j][i]; v=j; } for (j=0;j<n;j++) { g=G[i][j]; G[i][j]=-G[v][j]; G[v][j]=g; } } if (G[i][i]!=0) { for (k=i+1;k<n;k++) { c=G[k][i]/G[i][i]; h=c+(G[k][i]-c*G[i][i])/G[i][i]; for (j=0;j<n;j++) { G[k][j]=G[k][j]-G[i][