intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài báo cáo: Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell

Chia sẻ: Le Thuy Duong | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST
Báo xấu
175
lượt xem 39
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Sơ đồ chia sẻ bí mật không phải là một lĩnh vực mới mẻ của an toàn bảo mật thông tin, nhưng hứa hẹn sẽ mang đến nhứng ứng dụng rộng khắp, quan trọng nhất là ứng dụng bỏ phiếu điện tử. Sơ đồ chia sẻ bí mật chính là phương thức dùng đề chia một bí mật ra làm nhiều phần riêng biệt sau đó phân phối tới những người tham gia. Trong đó chỉ những người được chỉ định trước mới có khả năng khôi phục bí mật bằng cách gộp những phần thông tin của họ,...

Chủ đề:

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

Lưu

Nội dung Text: Bài báo cáo: Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell

  1. ------ Bài báo cáo Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell
  2. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell LỜI GIỚI THIỆU 1. Bỏ phiếu điện tử - thực trạng Trong suốt nhiều thế kỷ gần đây trong lịch sử thế giới, các cuộc bầu cử đã giữ một vai trò quan trọng trong việc xác lập các thể chế chính trị của các quốc gia từ lớn đến nhỏ. Trong thế giới hiện đại, việc bỏ phiếu bầu quốc hội (ở Anh, Mỹ là Hạ Nghị Viện, ở Nga là Duma quốc gia ) là một trong số những sự kiện quan trọng nhất của đất nước. từ những năm 1990, khi internet bùng nổ, một câu hỏi đã được quan tâm là: liệu một ngày nào đó, có thể thực hiện việc bỏ phiếu qua internet? Nhiều nước ở châu Âu đã chuẩn bị nghiên cứu với nhiều dự án cùng nhiều chiến lược khác nhau, dưới nhiều góc độ: Kỹ thuật, Luật, Chính sách, Xã hội. Ngoài ra, bỏ phiếu điện tử cũng được nghiên cứu ở các nước khác như Mỹ, Braxin, Mêhicô, Nga, Ấn Độ. Người ta đã bỏ ra rất nhiều công sức vào việc cải tiến các phương thức bầu cử, khiến cho các cuộc bầu cử ngày càng trở lên tốt hơn. Các phương thức này được thay đổi theo từng thời kỳ, theo sự tiến bộ của xã hội. Trong xu thế thực hiện “chính phủ điện tử” thì việc số hóa cuộc bầu cử để thay thế cho phương thức truyền thống là điều sẽ phải diễn ra trong tương lai gần. Trong các ứng dụng an toàn thông tin, thì bỏ phiếu điện tử (E-Voting) là ứng dụng đòi hỏi tính bảo mật cao nhất. Vì chính sự thành công hay thất bại của nó có ảnh hưởng nhiều nhất đến bộ mặt chính trị, xã hội của tổ chức, quốc gia đó. 2. Bỏ phiếu điện tử và sơ đồ chia sẻ bí mật Sơ đồ chia sẻ bí mật không phải là một lĩnh vực mới mẻ của an toàn bảo mật thông tin, nhưng hứa hẹn sẽ mang đến nhứng ứng dụng rộng khắp, quan trọng nhất là ứng dụng bỏ phiếu điện tử. Sơ đồ chia sẻ bí mật chính là phương thức dùng đề chia một bí mật ra làm nhiều phần riêng biệt sau đó phân phối tới những người tham gia. Trong đó chỉ những người được chỉ định trước mới có khả năng khôi phục bí mật bằng cách gộp những phần thông tin của họ, những người không được chỉ định sẽ không thu được bất kỳ thông tin gì về bí mật. Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 1
  3. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell CHƢƠNG 1 KIẾN THỨC CƠ BẢN 1.1. Cơ sở toán học 1.1.1.Ước số - Bội số 1.1.2.Số nguyên tố 1.1.3.Phép chia hết và không chia hết 1.1.4.Phi Euler 1.1.5.Đồng dư 1.1.6.Số nghịch đảo 1.1.7.Thặng dư bậc hai 1.1.8.Nhóm 1.1.9.Nhóm nhân 1.1.10.Nhóm Cylic 1.1.11.Không gian vectơ 1.1.1.12.Trường hữu hạn 1.1.1.13.Các thuật toán trong trường hữu hạn 1.1.1.14.Độ phức tạp của thuật toán 1.2. Các hệ mật mã Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 2
  4. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell Sơ đồ khối một hệ truyền tin mật Thám mã Bản rõ Bản mã Bản mã Bản rõ Kênh mở Nguồn tin Bộ mã hóa Bộ giải mã Nhận tin (không an toàn) KD KE A B Kênh an toàn Nguồn khóa Định nghĩa : Một hệ mật mã là một bộ năm (P, C, K, E, D) trong đó :  P là tập hữu hạn các bản rõ (có thể có)  C là tập hữu hạn các bản mã (có thể có)  K là tập hữu hạn các khóa  Với mỗi k  K, có một hàm lập mã ek  E: ek: P → C và một hàm giải mã dk  D: dk: C → P sao cho dk(ek(x)) = x với mọi x  P 1.2.1.Mã cổ điển Bản tin gốc Bản tin mật mã Bộ mã Bộ giải hoá mã Kênh công cộng A B Kênh an toàn Hinh 1.1 Sơ đồ truyền tin trong hệ mật khoá đối xứng Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 3
  5. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell Hệ mã cổ điển (hệ mã đối xứng) là hệ mật mã mà khóa mã hóa có thể dễ dàng tìm được từ khóa giải mã và ngược lại. Trong nhiều trường hợp, khóa mã hóa và khóa giải mã là giống nhau. Hệ mật mã cổ điển yêu cầu người gửi và người nhận phải thỏa thuận một mã trước khi tin tức được gửi đi, khóa này phải được cất giữ bí mật. Độ an toàn của hệ này phụ thuộc vào khóa. Nếu để lộ khóa, thì bất kỳ người nào cũng có thể mã hóa và giải mã thông điệp đó. Ƣu điểm: - Thủ tục mã hóa và giải mã đơn giản, dễ cài đặt. - Tốc độ tính toán nhanh Nhƣợc điểm: - Độ an toàn không cao - Yêu cầu một kênh truyền riêng để trao đổi khóa Ứng dụng: Do ưu điểm về tốc độ lập mã cũng như giải mã, Các hệ mã cổ điển thường được dùng để mã hóa những dữ liệu có khối lượng thông tin lớn nhưng không quá quan trọng về mặt đảm bảo bí mật. 1.2.1.1. Mã dịch chuyển Định nghĩa : Mã dịch chuyển: (P, C, K, E, D) P = C = K = Z với k  K, định nghĩa e (x) = (x + k) mod 26 26 k d (y) = (y – k) mod 26 k (x, y  Z ) 26 1.2.1.2. Mã thay thế Định nghĩa Mã thay thế: (P, C, K, E, D) P = C = Z , K = S (Z ) Với mỗi π є K, tức là một hoán vị trên Z , ta xác định 26 26 26 e (x) = π (x) π -1 d (y) = π (y) π -1 với x, y є Z , π là nghịch đảo của π 26 1.2.1.3. Mã Affine Định nghĩa Mã Affine: (P, C, K, E, D) P = C = Z , K = { (a, b) є Z x Z : (a, 26) = 1 } 26 26 26 với mỗi k = (a, b) є K ta định nghĩa: e (x) = ax + b mod 26 k -1 d (y) = a (y – b) mod 26 , trong đó x, y  Z k 26 Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 4
  6. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell 1.2.1.4. Mã Vingenere Định nghĩa Mã Vingenere: (P, C, K, E, D) Cho m là số nguyên dương. P = C = K = (Z 26 )m với mỗi khoá k = (k , k ,…,k )  K có: 1 2 m e (x , x ,…, x ) = (x + k , x + k ,…, x + k ) k 1 2 m 1 1 2 2 m m d (y , y ,…, y ) = (y – k , y – k ,…, y – k ) k 1 2 m 1 1 2 2 m m các phép cộng phép trừ đều lấy theo modulo 26 1.2.1.5. Mã Hill Định nghĩa Mã Hill: (P, C, K, E, D) Cho m là số nguyên dương. P = C = (Z 26 )m K = { k  (Z 26 )mxm mxm : det(k), 26 = 1 } với mỗi k  K định nghĩa: e (x , x ,…, x ) = (x , x ,…, x ).k k 1 2 m 1 2 m -1 d (y , y ,…, y ) = (y , y ,…,y ).k k 1 2 m 1 2 m 1.2.1.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=Z ,K=S ek x1 , x2 , ..., xm  = x 1 , x 2  , ..., x m   26 m   dk y1 , y2 , ..., ym  = y 1 1 , y 1 2  , ..., y 1 m  với mỗi k = π  S , ta có m -1 Trong đó π là hoán vị nghịch đảo của π Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 5
  7. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell 1.2.2. Mã hóa khóa công khai Bản tin gốc Bản tin gốc (1) Public key Bộ lâp mã Bộ giải mã (2) Bản mã (public key) (public key) A B Kênh công cộng Hinh 1.2 Sơ đồ truyền tin trong hệ mật mã khoá công khai Là loại mã hóa trong đó quá trình lập mã và giải mã dùng hai khóa khác nhau(một bí mật và một công khai). A muốn gửi một bản tin cho B, A sẽ dùng khóa công khai cua B để lập mã, sau đó gửi bản mã cho B. B với khóa bí mật của mình có thể dẽ dàng giải mã bản tin mã hóa để thu được bản tin gốc. Ƣu điểm: -Độ an toàn của các hệ mã này là rất cao -Bản mã và khóa công khai có thể truyền trên kênh truyền chung Nhƣợc Điểm: -Tốc độ mã hóa và giải mã chậm Ứng dụng Sử dụng chủ yếu trên các mạng công khai như Internet, khi mà việc trao chuyển khóa bí mật tương đối khó khăn. Ứng dụng để mã hóa những dữ liệu không quá lớn và yêu cầu bí mật cao. 1.2.2.1. 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 (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 (n)} Với K = (n, p, q, a, b) ta xác định: eK (x) = xb mod n dK (y) = ya mod n và (x, y  Zn) Các giá trị n và b được công khai và các giá trị p, q, a được giữ kín 1.2.2.2. Mã Elgamal Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 6
  8. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell 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, , ) trong đó p là số nguyên tố,   Z p là phần tử nguyên thuỷ (hay phần tử sinh),   Z * p Mục tiêu: Hãy tìm một số nguyên duy nhất a, 0  a  p – 2 sao cho: a   (mod p) Ta sẽ xác định số nguyên a bằng log  . Định nghĩa mã hoá công khai Elgamal trong Z * : p Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Z p là khó giải. Cho   Z * là phần tử nguyên thuỷ. Giả sử P = Z * , C = Z * x Z * . Ta định p p p p nghĩa: K = {(p, , a, ):   a (mod p)} Các giá trị p, ,  được công khai, còn a giữ kín. Với K =(p, , a, ) và một số ngẫu nhiên bí mật k  Z p 1 , ta xác định: eK(x, k) = (y1, y2). y1 = k mod p Trong đó: y2 = x. k mod p với y1, y2  Z * ta xác định: p dK(y1, y2) = y2(y1a) – 1 mod p CHƢƠNG 2 Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 7
  9. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell CHỮ KÝ ĐIỆN TỬ 2.1. Chữ ký điện tử là gì ? Về căn bản, khái niệm chữ ký điện tử (electronic signature) cũng giống như chữ viết tay. Bạn dùng nó để xác nhận lời hứa hay cam kết của mình và sau đó không thể rút lại được. Chữ ký điện tử không đòi hỏi phải sử dụng giấy mực, nó gắn đặc điểm nhận dạng của người ký vào một bản cam kết nào đó,nó là đoạn dữ liệu ngắn đính kèm với văn bản gốc để chứng thực tác giả của văn bản và giúp người nhận kiểm tra tính toàn vẹn của nội dung văn bản gốc.Chữ ký điện tử được tạo ra bằng cách áp dụng thuật toán băm một chiều trên văn bản gốc để tạo ra bản phân tích văn bản (message digest) hay còn gọi là fingerprint, sau đó mã hóa bằng private key tạo ra chữ ký số đính kèm với văn bản gốc để gửi đi. khi nhận, văn bản được tách làm 2 phần, phần văn bản gốc được tính lại fingerprint để so sánh với fingerprint cũ cũng được phục hồi từ việc giải mã chữ ký số. So sánh chữ ký thông thƣờng và chữ ký diện tử Chữ ký thông thƣờng Chữ ký điện tử Vấn đề ký một tài liệu Vấn đề ký một tài liệu Chữ ký chỉ là một phần vật lý của tài Chữ ký điện tử không gắn kiểu vật lý liệu vào bức thông điệp nên thuật toán được dùng phải “không nhìn thấy” theo một cách nào đó trên bức thông điệp Vấn đề về kiểm tra Vấn đề về kiểm tra Chữ ký được kiểm tra bằng cách so Chữ ký điện tử có thể kiểm tra nhờ sánh nó với chữ ký xác thực khác. Tuy dùng một thuật toán “kiểm tra công nhiên, đây không phải là một phương khai”. Như vậy, bất kì ai cũng có thể pháp an toàn vì nó dễ bị giả mạo. kiểm tra được chữ ký điện tử. Việc dùng chữ ký điện tử an toàn có thể chặn được giả mạo. Bản copy thông điệp được ký bằng Bản copy thông điệp được ký bằng chữ ký thông thường lại có thể khác với chữ ký điện tử thì đồng nhất với bản bản gốc. gốc, điều này có nghĩa là cần phải ngăn chặn một bức thông điệp ký số không bị dùng lại. 2.2.Định nghĩa về sơ đồ ký điện tử Một sơ đồ chữ ký S là một bộ năm S = (P , A , K , S , V) Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 8
  10. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell trong đó: P là một tập hữu hạn các thông báo có thể có, A là một tập hữu hạn các chữ ký có thể có, K là một tập hữu hạn các khoá, mỗi khoá K  K gồm có hai phần K=(K’,K''), K' là khoá bí mật dành cho việc ký, còn K'' là khoá công khai dành cho việc kiểm thử chữ ký. Với mỗi K =(K’,K''), trong S có một thuật toán ký sigk’ : P → A, và trong V có một thuật toán kiểm thử verk” : PxA → {đúng,sai} thoả mãn điều kiện sau đây đối với mọi thông báo x  P và mọi chữ ký y  A : verk” (x, y) = đúng ↔ y = sigk’ (x ) Với sơ đồ trên, mỗi chủ thể sở hữu một bộ khoá K =(K’,K''), công bố công khai khoá K'' để mọi người có thể kiểm thử chữ ký của mình, và giữ bí mật khoá K’ để thực hiện chữ ký trên các thông báo mà mình muốn gửi đi. Các hàm verk” và sigk’ (khi biết K’) phải tính được một cách dễ dàng (trong thời gian đa thức), tuy nhiên hàm y = sigk’ (x ) là khó tính được nếu không biết K’ - điều đó bảo đảm bí mật cho việc ký, cũng tức là bảo đảm chống giả mạo chữ ký. 2.3. Sơ đồ chữ ký RSA Sơ đồ chữ ký RSA được cho bởi bộ năm S = (P , A , K , S , V) trong đó P = A =Zn , với n =p.q là tích của hai số nguyên tố lớn p,q, K là tập các cặp khoá K =(K’,K''), với K’ = a và K'' = (n,b), a và b là hai số thuộc Z* n thoả mãn a.b ≡ 1(mod (n)). Các hàm sigk’ và verk” được xác định như sau: sigk’ (x) = x a modn , verk” (x,y ) = đúng ↔ x ≡ y b (modn). Dễ chứng minh được rằng sơ đồ được định nghĩa như vậy là hợp thức, tức là với mọi x  P và mọi chữ ký y  A: verk” (x,y ) = đúng ↔ y = sigk’ (x) Chú ý rằng tuy hai vấn đề xác nhận và bảo mật theo sơ đồ RSA là có bề ngoài giống nhau, nhưng nội dung của chúng là hoàn toàn khác nhau: Khi A gửi thông báo x cho B, để B có căn cứ xác nhận đó đúng thực là thông báo do A gửi, A phi gửi kèm theo chữ k ý sigk’ (x), tức là A gửi cho B (x, sigk’ (x)), trong các thông tin gửi đi đó, thông báo x hoàn toàn không được giữ bí mật. Cũng tương tự như vậy, nếu dùng sơ đồ mật mã RSA, khi một chủ thể A nhận được một bản mật mã ek’(x) từ B thì A chỉ biết rằng thông báo x được bảo mật, chứ không có gì để xác nhận x là của B. Nếu ta muốn hệ truyền tin của ta vừa có tính bảo mật vừa có tính xác nhận, thì ta phải sử dụng đồng thời cả hai hệ mật mã và xác nhận (bằng chữ ký). Giả sử trên mạng truyền tin công cộng, ta có cả hai hệ mật mã khoá công khai S1 và hệ xác nhận bằng chữ ký S2. Gi sử B có bộ khoá mật mã K = (K', K'') với K' = (n, e) và K'' = d trong hệ S1, và A Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 702 9
  11. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell có bộ khoá chữ ký Ks = (K’s , K''s) với K’s = a và K''s = (n,b) trong hệ S2. A có thể gửi đến B một thông báo vừa bảo mật vừa có chữ ký để xác nhận như sau: A ký trên thông báo x trước, rồi thay cho việc gửi đến B văn bản cùng chữ ký (x,sigk’s(x)) thì A sẽ gửi cho B bản mật mã của văn bản đó được lập theo khoá công khai của B, tức là gửi cho B ek’((x, sigk’s (x)). Nhận được văn bản mật mã đó B sẽ dùng thuật toán giải mã dk’’ của mình để thu được (x, sigk’s (x)), sau đó dùng thuật toán kiểm thử chữ ký công khai verk”s của A để xác nhận chữ ký sigk’s(x) đúng là của A trên x. 2.4.Sơ đồ chữ ký Elgamal Sơ đồ chữ ký ElGamal được đề xuất năm 1985, gần như đồng thời với sơ đồ hệ mật mã ElGamal, cũng dựa trên độ khó của bài toán lôgarit rời rạc. Sơ đồ được thiết kế đặc biệt cho mục đích ký trên các văn bản điện tử, được mô tả như một hệ: S = (P , A , K , S , V) trong đó P = Z*p , A = Z*p x Zp-1, với p là một số nguyên tố sao cho bài toán tính lôgarit rời rạc trong Z*p là rất khó. Tập hợp K gồm các cặp khoá K=(K’,K''), với K’=a là một số thuộc Z*p , K'' =(p, α , β), α là một phần tử nguyên thuỷ của Z*p , và β=αamodp. K’ là khoá bí mật dùng để ký, và K'' là khoá công khai dùng để kiểm thử chữ ký. Các thuật toán ký và kiểm thử chữ ký được xác định như sau: Với mỗi thông báo x, để tạo chữ ký trên x ta chọn thêm môt số ngẫu nhiên k  Z*p-1 , rồi tính : sig k’ (x,k ) = (γ , δ) với γ = α k modp, δ = (x – a.γ). k-1 mod(p -1). Thuật toán kiểm thử được định nghĩa bởi: verk” (x,(γ , δ)) = đúng ↔ β γ . γ δ ≡ α x (modp). Dễ thấy rằng sơ đồ chữ ký được định nghĩa như trên là hợp thức. Thực vậy, nếu sigk’(x,k ) = (γ , δ) thì ta có : β γ . γ δ ≡ α aγ. α kδ modp ≡ α x modp, vì k.δ +a.γ ≡ x mod(p -1). Do đó, verk” (x,(γ , δ)) = đúng. CHƢƠNG 3 SƠ ĐỒ CHIA SẺ BÍ MẬT 3.0. Định nghĩa : 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 Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 10 702
  12. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell 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 gì về bí mật. 3.1 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 (Participant) ký hiệu P Nhóm có khả năng khôi phục bí mật (Acess structure): 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. 3.2 Một số sơ đồ chia sẻ bí mật: 3.2.1 Sơ đồ chia sẻ bí mật sơ khai: Một sơ đồ chia sẻ bí mật đảm bảo tính bảo mật là sơ đồ trong đó bất kỳ người nào có ít hơn t phần dữ liệu (là số lượng đủ để khôi phục bí mật) không có nhiều thông tin hơn một người không có dữ liệu. Xem xét sơ đồ chia sẻ bí mật sơ khai trong đó cụm từ bí mật “password” được chia thành các phần “pa…”,”ss…”,”wo…”và ”rd…”. Một người không có một trong các phần bí mật đó chỉ biết mật khẩu có 8 chữ cái. Anh ta sẽ phải đoán mật khẩu đó từ 226=8 tỷ khả năng có thể xảy ra. Một người có một phần trong số 6 phần của mật khẩu đó sẽ phải đoán 6 chữ cái tương đương với 226 khả năng. Hệ thống này không phải là một sơ đồ chia sẻ bí mật bảo mật bởi vì một người tham gia có ít hơn t phần dữ liệu thu được một phần đáng kể thông tin về bí mật.Trong một sơ đồ bảo mật, mặc dù một người tham gia chỉ thiếu một phần dữ liệu cũng có thể sẽ đối mặt với 268 = 208 tỷ khả năng. 3.2.2 Sơ đồ chia sẻ bí mật tầm thường Có một vài sơ đồ chia sẻ bí mật trong đó yêu cầu tất cả những người tham gia phải cùng nhau khôi phục lại bí mật :  Mã hóa bí mật thành một số nguyên S. Đưa cho mỗi người tham gia i một số ngẫu nhiên ri (trừ một người). Đưa cho người cuối cùng một số (S- r1 - r2 -…- rn-1). Bí mật chính là tổng của các số của tất cả những người tham gia vào sơ đồ.  Mã hóa bí mật bằng 1 byte S. Đưa cho mỗi người tham gia i một byte bi (trừ một người), đưa cho người cuối cùng byte (S XOR b1XOR b2 …XOR bn-1) 3.2.3 Sơ đồ chia sẻ bí mật có ngưỡng giới hạn (Threshold secret sharing schemes) Mục tiêu của sơ đồ dạng này là chia một ít dữ liệu D ra thành nhiều phần D1,D2,…,Dn sao cho : Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 11 702
  13. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell  Nếu biết k hoặc nhiều hơn các phần Di có thể dễ dàng suy ngược lại D  Nếu biết k-1 hoặc ít hơn các phần Di không thể suy ngược lại D Sơ đồ này được gọi là sơ đồ ngưỡng giới hạn (k,n). Nếu k = n thì tất cả mọi thành viên phải cùng nhau mới có thể suy ngược lại bí mật. Dưới đây là 2 sơ đồ bí mật dạng (k,n). 3.2.3.1 Sơ đồ chia sẻ bí mật Blakley Hai đường thẳng không song song nằm trong cùng một mặt phẳng cắt nhau tại một điểm duy nhất. Ba mặt phẳng không song song trong không gian cắt nhau tại một điểm duy nhất.Tổng quát hơn, bất kỳ n mặt siêu phẳng nào cũng cắt nhau tại một điểm cụ thể. Bí mật có thể được mã hóa là một đơn tọa độ của giao điểm đó. Nếu bí mật được mã hóa bằng cách sử dụng tất cả các tọa độ, mặc dù chúng là ngẫu nhiên, khi đó một người tham gia (ai đó sở hữu một hoặc nhiều các siêu mặt n chiều) thu được thông tin về bí mật do anh ta biết nó nhất định phải nằm trên mặt mà anh ta sở hữu. Nếu một người trong cuộc mà thu được nhiều thông tin hơn một người ngoài cuộc về bí mật, khi đó hệ thống này không còn bảo mật nữa. Nếu chỉ có một trong số các tọa độ được sử dụng, khi đó một người trong cuộc không biết về bí mật hơn một người ngoài cuộc (thí dụ:Bí mật phải nằm trên trục x trong hệ trục tọa đồ Decac). Mỗi người tham gia được đưa đủ thông tin để định nghĩa một siêu mặt; bí mật được khôi phục bằng cách tính toán điểm giao nhau của các mặt và lấy một tọa độ cố định của giao điểm đó. Sơ đồ của Blakley trong hệ tọa độ không gian 3 chiều: Thông tin của mỗi người tham gia là một mặt phẳng và bí mật chính là giao điểm của 3 mặt phẳng đó. Thông tin của 2 người không đủ để chỉ ra được bí mật mặc dù chúng đã thu hẹp được phạm vi của bí mật là 1 điểm nằm trên giao tuyến của 2 mặt phẳng đã biết. Sơ đồ của Blakley có hiệu quả không gian ít hơn sơ đồ của Shamir dưới đây; trong khi với sơ đồ của Shamir, mỗi một phần chia chỉ lớn bằng bí mật ban đầu. Các phần chia của Blakley lớn hơn t lần, với t là số người tham gia vừa đủ thu được bí mật. Sơ đồ của Blakley có thể được thu gọn bằng cách giới hạn mặt nào có thể sử dụng làm phần chia. Kết quả thu được sẽ là một sơ đồ tương đương với sơ đồ của Shamir. Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 12 702
  14. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell 3.2.3.2 Sơ đồ chia sẻ bí mật Shamir Ý tưởng về sơ đồ ngưỡng giới hạn của Shamir dựa trên tính chất: Hai điểm có thể định nghĩa một đường thẳng, 3 điểm định nghĩa được 1 parabol, 4 điểm định nghĩa được một hình lập phương, cứ như thế một cách tổng quát cần n+1 điểm để định nghĩa một đa thức bậc n. Giả sử chúng ta muốn sử dụng sơ đồ ngưỡng (k,n) để chia sẻ bí mật S với k < n. Sự lựa chọn giá trị của k và n quyết định sức mạnh của hệ thống. Chọn ngẫu nhiên (k-1) hệ số a1,…, ak-1 và đặt a0 = S. Xây dựng đa thức f(x)=a0 + a1x + a2x2 +…+ak-1xk-1 Chúng ta sẽ vẽ n điểm bất kỳ ví dụ tập i = 1,2,..,n tính được (i, f(i)). Mỗi người sẽ nhận được một cặp tọa độ thỏa mãn điều kiện là đầu vào và đầu ra của đa thức trên. Đưa bất kỳ một tập k các cặp tọa độ trên, chúng ta có thể dễ dàng các hệ số của đa thức bằng phép nội suy và tính được a0 là bí mật. Ví dụ: Bƣớc 1: Chia sẻ bí mật Giả sử bí mật của chúng ta là một mã số ATM :1234 (S = 1234) Chúng ta muốn chia bí mật thành 6 phần (n=6), với bất kỳ 3 phần trong đó (k=3) có đủ khả năng suy ngược lại bí mật. Một cách ngẫu nhiên chúng ta thu được 2 số 166,94 (a1=166;a2=94) Đa thức của chúng ta do đó sẽ là f(x)=1234 + 166x + 94x2 Chúng ta lấy 6 điểm thỏa mãn là nghiệm của đa thức đó (1,1494);(2,1942);(3,2578);(4,3402);(5,4414);(6,5614) Chúng ta đưa cho mỗi người tham gia trong sơ đồ một điểm khác nhau (cả x và f(x)) Bƣớc 2: Khôi phục bí mật Chúng ta hãy coi (x0,y0)=(2,1942); (x1,y1)=(4,3402); (x2,y2)=(5,4414) Chúng ta sẽ tính toán hệ số Lagrange Do đó : Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 13 702
  15. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell Bí mật của chúng ta chính là hệ số tự do của đa thức. Nghĩa là S=1234 3.3.Sơ đồ chia sẻ bí mật dựa trên không gian vector Brickell 3.3.1.Sơ đồ chia sẻ bí mật cơ bản Điều bí mật là 1 phần tử trong trong trường giới hạn GF(q). Người phân phối chọn một vectơ a = (a0,…, at) với t bất kỳ, mà aj GF(q) và a0 là bí mật. Đánh dấu những người tham gia bằng Pi với 1 ≤ i ≤ n. Với mỗi Pi, người phân phối sẽ lấy 1 vectơ đơn vị vi trên GF(q). Tất cả các vectơ vi , 1 ≤ i ≤ n sẽ được công khai. Phần chia mà nguời phân phối đưa cho Pi sẽ là si = vi .a Ký hiệu ei là vectơ đơn vị t chiều thứ i (ví du e1=(1,0,…,0)) Định lý 1: Đặt γ = (Pi1,…,Pik) là tập những người tham gia (1)Những người tham gia trong γ có thể chỉ ra được bí mật nếu tập ‹ vi1,…,vik › chứa e1 (2)Những người tham gia trong γ không nhận được một ít thông tin nào về bí mật nếu tập ‹ vi1,…,vik › không chứa e1 Chứng minh: Đặt M là ma trận với các hàng vi1,…,vik. Đặt s = (si1,…,sik). Để chứng minh (1), đặt w là vectơ sao cho wM = e1. Khi đó wMa = a0 . Do đó w.s = a0. Để chứng minh (2), đặt w0 ,…, wt là cột của vectơ M. Nếu w0  khi đó tồn tại d sao cho d.wi = 0 với 1≤ i ≤ t và d.w0 = 1. Do đó dM = e1 nhưng điều này trái với giả thiết e  (vi1,…, vik). Do đó w0  (w1,…, wt). Vì vậy tồn tại b sao cho Mb = 0 và b0 ≠ 0. Thông tin duy nhất mà những người tham gia trong γ biết về a0 là Ma = s . Nhưng s = Ma = M(a + αb) với tất cả α  GF(q). Bởi vậy cho trước bất kỳ c0  GF(q), tồn tại c = (c0,…,ct) với ci  GF(q), 1 ≤ i ≤ t sao cho Mc = s. Do đó những người tham gia trong γ không thể loại bỏ bất kỳ phần tử nào trong GF(q) có khả năng là a0 3.3.2.Sơ đồ chia sẻ bí mật đa cấp Trong phần này chúng ta sẽ đưa ra một chứng mính có sẵn là bất kỳ cấu trúc truy Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 14 702
  16. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell cập đa mức (multilevel access structure) nào cũng có thể tìm được trong một sơ đồ chia sẻ bí mật hoàn hảo. Sau đó chúng ta sẽ đưa ra 1 cấu trúc khác yêu cầu khối lượng tính toán ít hơn cho c ông việc của người phân phối. Sơ đồ đa cấp cơ bản: Đặt Γ là một cấu trúc truy cập đa mức với các mức l 1< l2
  17. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell  Lh 1 Khi đó wi x i =0 có nhiều nhất L h-1 nghiệm trên GF(q) i 1 Giả sử rằng k người tham gia P i1,…,Pik của mức cao nhất k cố gắng tìm lại bí mật và giả sử không có tập con nào của tập này chứa l người tham gia của mức cao nhất l với bất kỳ l < k. Các vector vi1,…,vik là độc lập và được chứa trong một khoảng kích thước k tạo bởi bởi e1,….,ek. Do vậy e1 (vi1,…,vik) và do đó theo định lý 1, những người tham gia có thể chỉ ra được điều bí mật. Bây giờ giả sử rằng 1 tập γ  Γ của những người tham gia thử tìm lại bí mật Đặt γ = {Pi1,…,Pik}. Do các vectơ e1,vi1,…,vik là độc lập. Theo Định lý 1, những người tham gia này không thu được bất kỳ thông tin nào về a 0. Sơ đồ của Blakley cũng có thể chỉnh sửa để bổ sung một cấu trúc truy cập đa mức. Dealer lại một lần nữa chọn g là trục tọa độ thứ nhất và một dãy c ác mặt phẳng Fi sao cho: F1  F2  ...  FR , F1  g là không rỗng và G không là tập con của FR. Điều bí mật là P = F 1  g. Một người ở mức r sẽ được cho trước một điểm trên F r-1. Các điểm phải được chọn sao cho bất kỳ r người tham gia nào của mức cao nhất r có thể chỉ ra điểm P và mặt phẳng F, được tạo ra bởi một nhóm của những người tham gia trong đó với bất kỳ r không có một tập con nào của r người tham gia mà tất cả có mức cao nhất r, F  G phải là rỗng. Công thức này cũng được Simmons tìm ra [6]. Một vấn đề đáng quan tâm khác là khối lượng tính toán cần thiết để cho Dealer xây dựng lên h ệ thống.Với hệ thống ban đầu của Blakley thì Dealer phải làm phép kiểm tra để chắc chắn rằng các điểm là nằm trong vùng chung, phương pháp rõ ràng để n làm việc này yêu cầu   lần nhưng nếu các điểm đã được chọn cẩn thận thì không k   phép kiểm tra nào là cần thiết. Cũng vậy không phép kiểm tra nào là cần thiết cho sơ đồ của Shamir. Thật không may là thuộc tính này lại không nằm trong cấu trúc với sơ đồ đa mức trên. Cách thông thường để thự c thi sơ đồ trình bày trong Định lý 1 sẽ yêu cầu rất nhiều phép kiểm tra để chắc chắn rằng các điểm nằm trong vị trí chung. Tuy nhiên chúng ta cũng đã tìm ra một cách xây dựng không yêu cầu kiểm tra . Mô hình đầu tiên mà chúng ta đề cập đến chỉ khả thi nếu không có quá nhiều mức trong đó. Chúng ta sẽ sử dụn g sơ đồ đa mức cơ bản và vì thế chúng ta sẽ dễ dàng miêu tả cách mà Dealer chon xi. Để minh họa, giả sử rằng chúng ta muốn cho phép mức 2 hoặc 3. Chọn q = p 2. Đặt α là một đại số bậc 2 (algebraic of degree 2) trên GF(p) (Ví dụ α thỏa mãn một đa thức bậc 2 tối giản trên GF(p) ). Dealer lấy 1 phần tử yi trong GF(p) với mỗi người tham gia P i sao cho nếu i ≠ j và L i = Lj , khi đó yi ≠ yj Với một người tham gia ở mức 3, Dealer sẽ đặt xi = yi. Với một người tham gia ở mức Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 16 702
  18. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell 2, anh ta sử dụng x i = αyi. Hệ thống này sẽ có các thuộc tính mong muốn. Để thấy rằng 3 người tham gia P i 1 , Pi 2 , Pi 3 với Li 1 = 2, Li 2 = Li 3 = 3 có thể chỉ ra bí mật. Coi như ma trận M tạo thành bởi v i1, vi2, vi3. Định thức của ma trận này là một đa thức với α có bậc cao nhất là l . Có thể chỉ ra rằng giới hạn trong đa thức này là khác 0. Do α là một số đại số bậc 2, giá trị của đa thức đó phải khác 0. Trong công thức chung hơn, với các mức l 1
  19. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell thức là tổng các phép nhân sơ cấp của M mà mỗi phép nhân sơ cấp là phép nhân của các số hạng m1,c1 ,…,mk,ck với dấu thích hợp mà c 1,…,ck là một phép hoán vị của 1,…, k. Mọi phép nhân khác 0 cơ b ản sẽ thỏa mãn ci ≤ Li với 1≤ i ≤ k Số mũ lớn nhất của α trong hàng i của M là (R-ρ(i))(Li-1). Do đó số mũ lớn nhất của α trong phép nhân sơ cấp  r 1 R  r l r  1nr  Rl R r 1 nr  Rl R R 1 R 1 2  j Đặt T-1 =0 và đặt Tj = ni với 0 ≤ j ≤ R. Số mũ của α trong kết quả của một i 0  c  1R   i  . Phép tính tổng này thu được kết quả nhỏ k phép nhân khác 0 sẽ là i 0 i nhất khi {CTr-1+1,…, CTr} = { Tr-1+1,…, Tr} với 0 ≤ r ≤ R Đặt Dr là ma trận con n r x nr của M được tạo bởi các hàng và các cột Tr-1+1,…, Tr Đặt z là số mũ nhỏ nhấ t của α trong định thức của M. Khi đó số hạng θα2 với θ  GF(q) trong định thức cuả M thỏa mãn  R θα2 = |Dr| r 1 Khi đó mỗi Dr là một phép nhân của ma trận Van der Monde, |Dr| ≠0. Do vậy hệ số của αz là khác không. Như vậy, bởi vì M(γ) không phải là số ít, những người tham gia trong γ có thể chỉ ra a 0. Giả sử bây giờ γ là 1 tập của k -1 người tham gia mỗi người có mức tối đa là k và không có tập con γ’ chứa nh iều hơn l người tham gia c ủa mức tối đa l với bất kỳ l
  20. Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell nhất ti trong Ci với i=1,…,u và tổng số ít nhất t người tham gia. Đặt n là tổng số những người tham gia. Định lý 3: Đặt Γ là cấu trúc truy cập riêng phần (compartmented access structure). Nếu q>   , khi đó có một sơ đồ chia sẻ bí mật với Γ trên GF(q) t  n  u Chứng minh : chúng ta có thể thừa nhận rằng T = t- t ≥ 0. Dealer chọn 1 i 1 i a = (a0,…,at-1) với a0 là bí mật. Đặt T0 = T, đặt Ti = T+  u vectơ t với 1≤ i ≤ u. i 1 i Đánh dấu những người tham gia bằng P r,i với Pr,i nằm trong phần C r. Với người tham gia P i Dealer sẽ lấy 1 vector t thành phần trên GF(q) theo dạng : Với vài vr,i  GF(q). Như trong Định lý 1, Dealer sẽ phải cẩn thận để chọn ra x r,i Đặt đánh dấu theo thứ tự từ điển sắp xếp các cặp. Ví dụ : (r,i) (s,j) nếu r < s hoăc (r = s và i   , có thể thấy rằng điều đó là có khả năng bằng cách sử dụng lý luận N t tương tự với chúng như trong Định lý 1 Một tập của những người tham gia trong Γ có thể chỉ ra bí mật vì vectơ v r,i là độc lập. Ngược lại giả sử một tập γ = Pr,i ,|(r,i) Є I} của những người tham gia không có trong Γ Giả sử có Cs sao cho γ không chứa ít nhất t s những người tham gia trong C s. Đặt M là ma trận với các hàng v r,i với (r,i)  I. Đặt M’ là ma trận bao gồm các cột 1,T s +1,…,Ts + ts của M. Có mỗi ts hàng phân biệt trong M’, chúng tương ứng với các vectơ vr,i với r = s và (r,i)  I, và vectơ (1,1,…,1). Đặt {i1,…, its-1} = {i|(s,i)  I}. Đặt M’’ là ma trận bao gồm các hàng e1, vs,i1,….,vs,i t 1 . s Khi đó |M’’| = |M’’11| với M’’11 là ma trận M’’ với hàng thứ nhất và cột đã bị loại bỏ. Nhưng M’’ lại là một ma trận Van de Monde với hàng i j nhân với xTs,ij với 1≤ j ≤ ts-1. Sinh viên thực hiện: Trần Trung Hiếu Lớp CT 19 702
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.09: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Quản Trị Kinh Doanh
81 tài liệu
1643 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2