MẬT MÃ CỔ ĐIỂN
KHÁI NIỆM VÀ ĐỊNH NGHĨA VỀ MẬT MÃ
Mật mã có chức năng cơ bản là đảm bảo khả năng liên lạc an toàn giữa hai người sử dụng, được gọi là A và B, trên một kênh không bảo mật, nhằm ngăn chặn bên thứ ba, tạm gọi là C, hiểu được thông tin được truyền tải.
Kênh liên lạc có thể là điện thoại hoặc mạng máy tính, cho phép A gửi thông tin rõ ràng cho B Thông tin này có thể là văn bản tiếng Anh, dữ liệu số, hoặc bất kỳ tài liệu nào có cấu trúc tùy ý.
A sẽ sử dụng một khóa mã hóa đã được xác định trước để mã hóa bản rõ và gửi bản mã qua kênh Mặc dù C có được bản mã nhưng không thể xác định nội dung bản rõ, trong khi B, người biết khóa mã, có khả năng giải mã và thu được bản rõ.
Ta sẽ mô tả hình thức nội dung bằng cách dùng khái niệm toán học nhƣ sau:
Một hệ mật mã là một bộ 5 ( P, C, K, E,D ) thỏa mãn các điều kiện sau:
1 P là một tập hữu hạn các bản rõ có thể
2 C là một tập hữu hạn các bản mã có thể
3 K (không gian khóa) là tập hữu hạn các khóa có thể
4 Đối với mỗi k є K có một quy tắc mã e k : P→ C và một quy tắc giải mã tương ứng d k є D Mỗi e k : P→ C và d k : C→ P là những hàm sao cho: d k (e k (x)) = x với mọi bản rõ x є P
Nội dung quan trọng cần lưu ý là nếu một bản rõ x được mã hóa bằng khóa e k và bản mã nhận được sau đó được giải mã bằng khóa d k, thì kết quả cuối cùng phải là bản rõ ban đầu x.
Giả sử chúng ta có một bản rõ cần truyền đi là x = x1, x2, …, xn với n là số nguyên lớn hơn hoặc bằng 1 Mỗi ký hiệu x i thuộc tập P, với 1 ≤ i ≤ n, sẽ được mã hóa theo quy tắc mã e k sử dụng một khóa k đã được xác định trước.
Bản mã thu được là y = y1, y2,…,yn, trong đó yk = ek(xi) với i = 1, 2,…,n và k thuộc tập K Khi Bob nhận y1, y2,…,yn, anh sẽ sử dụng hàm giải mã dk để khôi phục bản rõ gốc x = x1, x2,…,xn.
Hình 1.1 là một ví dụ về một kênh liên lạc x y x k k k k
Rõ ràng là trong trường hợp này hàm mã hóa phải là hàm đơn ánh( tức là ánh xạ 1-
1), nếu không việc giải mã sẽ không thực hiện được một cách tường minh
Ví dụ y= e k (x 1 )= e k (x 2 ) trong đó x1 ≠ x 2, B sẽ không có cách nào đẻ biết liệu bản rõ là x 1 hay x 2
MỘT SỐ MÃ HÓA ĐƠN GIẢN
Bộ mã hóa Bộ giải mã
CHUẨN MÃ DỮ LIỆU (DES)
Mô tả DES ( Data Encryption Standard)
DES mã hóa một xâu bít x:
Bản rõ x độ dài 64 bít
Bản mã y nhận đƣợc cũng là một xâu bit có độ dài 64 bit
Thuật toán tiến hành theo 3 giai đoạn:
1 Với bản rõ cho trước x, một xâu bit x 0 sẽ được tạo ra bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP
Ta viết : x 0 =IP(X)=L 0 R 0 , trong đó L0 gồm 32 bit đầu và R 0 là 32 bit cuối
2 Sau đó tính toán 16 lần lặp theo một hàm xác định Ta sẽ tính đƣợc LiR i , 1 ≤ i ≤ 16 theo qui tắc sau:
Kí hiệu cộng theo modulo 2 của hai xâu bit được sử dụng trong hàm f, với R i-1 và k i được mô tả như sau: k i là các xâu bit dài 48 bit, được tính toán từ khóa k Thực tế, mỗi k i là một phép chọn hoán vị bit trong khóa k.
3 Áp dụng phép hoán vị ngƣợc IP -1 cho xâu bit R 16 L 16 ta thu đƣợc bản mã y.Tức là y = IP -1 (R 16 L 16 )
Hình 2.1 Một vòng ( vòng thứ i ) của DES.
Các bước thực hiện
Hoán vị biến x theo phép hoán vi ban đầu IP(X) x 0 = IP(X) = L 0 R 0
Theo bảng 2.1, bit thứ 58 của x tương ứng với bit đầu tiên của IP(x), bit thứ 50 là bit thứ hai của IP(x), và bit ở vị trí thứ 7 là bit cuối cùng của IP(x).
2.2.2 Cách tính L i R i : Để tính LiR i trước hết ta phải xác định hàm f
Biến thứ nhất R i-1 là xâu bit độ dài 32
Biến thứ hai J là xâu bít độ dài 48
Đầu ra của f là một xâu bit độ dài 32 bít Hàm f thực hiện qua các bước sau:
Bước 1: Xác định biến thứ nhất (biến A):
Xâu bit của R i-1 đƣợc mở rộng thành một xâu bit có độ dài 48 theo một hàm mở rộng cố định E
E(R i-1) là một chuỗi 32 bit được tạo ra từ R i-1, trong đó 16 bit xuất hiện hai lần theo cách hoán vị cố định Cụ thể, bảng E bit xác định rằng bit đầu tiên của E(R i-1) nằm ở vị trí thứ 32, trong khi bit thứ hai và bit cuối cùng của E(R i-1) lần lượt nằm ở vị trí thứ nhất.
Bước 2: Xác định biến thứ hai (biến J)
Biến J thực chất là phép hoán vị và dịch vòng của xâu bit khóa k
Thuật toán tạo 16 khóa con k1, k2,…k 16
Hình 2.2 Sơ đồ tạo khóa k
Theo sơ đồ hình 2.2 trên việc xác định ki đƣợc thực hiện nhƣ sau:
Với khóa k 64 bit cho trước hoán vị thực chất chỉ có 56 bit dùng để tạo k i với i từ
1 đến 16.Tránh các bit ở vị trí 8,16,24,32,40,48,56,64
Theo phép hoán vị cố định PC-1 ta viết:
PC-1(K) = C 0 D 0 Trong đó C 0 là28 bit đầu và D 0 là 28 bit cuối
Mỗi phần sẽ đƣợc xử lí một cách độc lập
Phép dịch bit vòng sang trái được biểu diễn bằng LS i, với số lượng bit dịch phụ thuộc vào giá trị của i Cụ thể, nếu i bằng 1, 2, 9, 16, bit sẽ được dịch sang trái 1 vị trí; còn nếu i thuộc các giá trị khác, bit sẽ được dịch sang trái 2 vị trí Công thức tính k i là PC-2(C i - D i ).
PC-2 là hoán vị cố định sẽ hoán vị chuỗi C i - D i 56 bit thành chuỗi 48 bit
Hình 2.3.Sơ đồ hoạt động của hàm f(R i-1 ,k i ):
Sau khi mở rộng R i-1 bởi hàm mở rộng E để chuyên R i-1 gồm 32 bit thành E(R i-1 ) gồm 48 bit, E(R i-1 ) cộng XOR với khóa k i cho ra là:
B gồm 48 bit đƣợc phân thành 8 khối (block) nhƣ nhau và mỗi block B i , i =1,8 có độ dài 6 bit
Sau đó mỗi Bi đƣợcđƣa vào hộp Si, i = 1,8 và biến đổi để cho đầu ra là C i gồm 4 bit (i = 1,8) Sự biến đổi này đƣợc thực hiện nhƣ sau:
Giả sử B i gồm 6 bit là B i = b i1 b i2 …bi6 Khi đó bi1b i6 đƣợc nhập thành cặp, b i1 b i6 đƣợc chuyển thành số thập phân từ 1 đến 3 Ví dụ: b i1 b i6 = 00→0 b i1 b i6 →1 b i1 b i6 →2 b i1 b i6 →3
Còn b i2 b i3 b i4 b i5 của B i đƣợc chuyển thành số thập phân từ 0 đến 15 nhƣ sau:
Bảng 2.3 Bảng chuyển đổi giá trị b i2 b i3 b i4 b i5 Số tự nhiên
Số nguyên dương r i = b i1 b i6 và s i = b i2 b i3 b i4 b i5 chính là tọa độ (hoành tung) của ma trận S i từ t i chuyển thành C i = C i1 C i2 C i3 C i4 với C ij є{0,1} i= i =1,8 , j =1,4
Vậy đầu ra của hộp S là:
Mỗi khối C gồm 8 phần C1 đến C8, mỗi phần chứa 4 bit, tạo thành tổng cộng 32 bit Các bit này được đưa vào ma trận chuyển vị P, và đầu ra cũng là 32 bit, là kết quả của hàm f(Ri-1, Ki).
Ta có thể trình bày cụ thể cách tính hàm f nhƣ sau:
Với xâu bit dài 6 bit (ký hiệu B i = b 1 b 2 …b6), ta có thể tính Sj(B j ) bằng cách xác định hai bit b i và b 6 để biểu diễn nhị phân hàng r của S j (0 ≤ r ≤ 3) và 4 bit b 2 b 3 b 4 b 5 để biểu diễn nhị phân cột c của S j (0 ≤ c ≤ 15) Do đó, S j (B j ) sẽ xác định phần tử S j (r,c), và phần tử này được biểu diễn dưới dạng nhị phân với độ dài 4 bit Mỗi S j có thể được coi là một hàm mã với đầu vào là một xâu bit dài 6 bit.
2 và một xâu bit độ dài 4, còn đầu ra là một xâu bit cố độ dài 4) Bằng cách tương tự tính các C j = S j (B j ), 1≤ j ≤ 8
Mỗi chuỗi B là một chuỗi 6 bit, trong đó bit đầu và bit cuối xác định vị trí hàng từ 0 đến 3 (hoặc từ 00 đến 11), trong khi bốn bit giữa xác định vị trí cột từ 0 đến 15 (hoặc từ 0000 đến 1111) Sau khi xác định vị trí hàng và cột, ta đối chiếu trong bảng S để có được một số thập phân, sau đó quy đổi số thập phân đó ra giá trị nhị phân để thu được C j.
Ví dụ: Bit đầu vào của B là B = 100110
Bit đầu và cuối là “10”, cho biết thứ tự hàng là 2, trong khi bốn bit giữa là “0011”, xác định thứ tự cột là 4 Khi đối chiếu với hộp S, ta thấy số 14 xuất hiện, và chuyển đổi 14 sang nhị phân cho ra 1110 Do đó, S(B) = S(100110) = 1110.
Sau khi thực hiện các phép đối chiếu hộp S ta đƣợc các giá trị S i B i
Tính hàm f = P(S 1 (B 1 )) = S 2 (B 2 )…… S 8 (B 8 ) thực hiện theo phép hoán vị P
Phép hoán vị P có dạng:
Theo bảng 2.4 thì bit thứ 16 và bit thứ 7 của xâu bit S j B j lần lƣợt là bít thứ nhất và bit thứ 2 của hàm f…
L ỉ R i đƣợc xác định theo công thức sau:
Sau khi xác định đƣợc L ỉ R i ta thu đƣợc L 16 R 16 , vậy bản mã y đƣợc xác định theo công thức: y= IP -1 (R 16, L 16 )
Ví dụ: Ta có bản rõ M= 0123456789ABCDEF
Thực hiện phép hoán vị IP
Hoán vị khóa k theo phép hoán vị PC-1 ta thu đƣợc PC-1(k):
D i = S i (D i-1 ) Trong đó: Si là sự dịch chuyển C i-1 , D i-1 đi 1 sang trái với i= 1,2,9,16 và dịch 2 với các i còn lại
Cuối cùng các khóa con K i thu được từ C i ,D i qua hoán vị PC-2 cho trước
Bit đầu và bit cuối là “00” cho ta hàng 0
Bốn bit giữa “1100” cho ta cột 12
Chiếu hàng 0 cột 12 vào bảng S 1 cho ta giá trị là 5= “0101”
Tính S 2 (B 2 ) = S 2 (010001) thực hiện hoán vị S 1 (B 1 ) theo phép hoán vị S 1
Bit đầu và bit cuối là “01” cho ta hàng 1
Bốn bit giữa “1000”=8 cho ta cột 8
Chiếu hàng 1 cột 8 vào bảng S 2 cho ta giá trị là 12=”1100”
Tính tương tự ta có S 1 (B 1 ) = S 2 (B 2 ) = S 3 (B 3 ) = S 4 (B 4 ) = S 5 (B 5 ) = S 6 (B 6 ) = S 7 (B 7 )
Tính hàm f= P S 1 (B 1 ) = S 2 (B 2 ) ……… S8(B 8 ) thực hiện theo phép hoán vị P
Ta thực hiện 16 lần vòng lặp thu đƣợc R 16 L 16
Thực hiện phép hoán vị ngƣợc IP(IP -1 )
10110100 00000101 Chuyển IP -1 sang dạng hexa ta thu đƣợc bản mã : 85E823540F0AB405
Giải mã DES
Để giải mã một chuỗi kí tự đã bị mã hóa, chúng ta thực hiện các bước tương tự như mã hóa, nhưng với hệ thống khóa được tạo theo chiều ngược lại.
Có bản mã y y 0 = IP(y) = IP(IP -1 (R 16 L 16 )) = R 16 L 16 = L‟ 0 R‟ 0
Hình 2.4 Sơ đồ giải mã DES y
Thuật toán giải mã chỉ khác thuật toán mã hóa ở hệ thống khóa Cụ thể, trong mã hóa, khóa được tạo ra theo thứ tự từ k1 đến k16, trong khi đó, trong giải mã, hệ thống khóa được tạo ra theo thứ tự ngược lại từ k16 đến k1 Điều này được minh họa rõ ràng trong hình 2.4 của sơ đồ giải mã DES.
Các vấn đề xung quanh DES
Khi DES được đề xuất làm tiêu chuẩn, đã có nhiều phản hồi liên quan đến các hộp S, thành phần phi tuyến quan trọng cho sự an toàn của hệ thống Mặc dù các tính toán trong DES hầu hết là tuyến tính, nhưng thiết kế của các hộp S chưa được hiểu rõ Một số ý kiến cho rằng các hộp S có thể chứa đựng những cửa sập ẩn, cho phép cục an ninh quốc gia giải mã thông điệp mà người dùng vẫn tin rằng hệ thống an toàn Tuy nhiên, chưa có bằng chứng cụ thể nào chứng minh sự tồn tại của các cửa sập trong DES.
1976, cục an ninh quốc gia Hoa kỳ tuyên bố rằng những thuộc tính của hộp S là tiêu chuẩn thiết kế:
- Mỗi một dòng của một hộp S là sự lặp lại của các số nguyên từ 0 đến 15
- Không có hộp S nào có tuyến tính hay là hàm Affine của các đầu vào
- Thay đổi một bit đầu vào của hộp S gây ra ít nhất 2 bit đầu rat hay đổi
- Đối với bất kì một hộp S và bất kì đầu vào x, S(x) và S(x^001100) gây ra sự khác biệt ở ít nhất hai bit 9x ở dây là một chuỗi có độ dài 6
Hai đặc tính khác của hộp S đƣợc thiết kế nhƣ là đƣợc điều khiển bởi các tiêu chuẩn thiết kế của cục An ninh Quốc gia
- Đối cới bất kì hộp S nào, bất kì x đầu vào và đối với e, f {0,1}, S(x)≠ S(x + 1 lef00 )
Đối với bất kỳ hộp S nào, nếu một bit đầu vào được cố định và giá trị của một bit đầu ra cũng cố định, số lượng đầu vào tạo ra đầu ra bằng 0 sẽ gần bằng số lượng đầu vào tạo ra đầu ra bằng 1 Cụ thể, nếu cố định giá trị của bit 1 và bit 16, sẽ có 16 đầu vào cho mỗi bit đầu ra cụ thể bằng 0 và 16 đầu vào cho giá trị bằng 1 Mặc dù điều này không hoàn toàn đúng cho các bit đầu vào thứ 5, nhưng vẫn gần đúng Thêm vào đó, với bất kỳ hộp S nào, nếu giá trị của bất kỳ bit đầu vào nào được cố định, số đầu vào tạo ra bất kỳ bit đầu ra cố định nào có giá trị 0 hoặc 1 sẽ luôn nằm trong khoảng từ 13 đến 19 Một trong những chỉ trích chính về DES là kích thước không gian khóa 2^56 quá nhỏ để đảm bảo an toàn Các máy tính với mục đích đặc biệt có thể tấn công vào bản rõ bằng cách tìm kiếm khóa, với mỗi khóa có thể lớn hơn một khóa k sao cho E_k(x) = y được tìm thấy.
Vào đầu năm 1977, Diffie và Hellman đã đề xuất việc phát triển một chip VLSI có khả năng kiểm tra 1 triệu khóa mỗi giây Với tốc độ này, máy có thể tìm kiếm toàn bộ không gian khóa chỉ trong một ngày, và họ ước tính chi phí sản xuất máy này khoảng 20 USD.
Tại hội nghị CRYPTO'93, Michael Wiener đã giới thiệu một thiết kế chi tiết về máy dò khóa dựa trên chip dò khóa nối tiếp, cho phép 16 mã hóa diễn ra đồng thời Chip này có khả năng kiểm tra 5.10^7 khóa mỗi giây và có thể được sản xuất với chi phí 10,5 USD mỗi chip Một khung gồm 5760 chip có thể được xây dựng với giá 1 triệu USD, giúp giảm thời gian dò trung bình xuống còn 3,5 giờ.
DES, mặc dù có mô tả dài dòng, vẫn hoạt động hiệu quả cả trên phần cứng lẫn phần mềm, với các phép toán chủ yếu là phép XOR giữa các chuỗi bit Các bước như mở rộng hàm E, hoán vị IP và P, cùng với việc tính toán các khóa k1, k2,…, k16 đều được thực hiện nhanh chóng nhờ vào bảng tìm kiếm trong phần mềm hoặc qua kết nối dây cứng Hiện nay, các thiết bị phần cứng có thể mã hóa với tốc độ rất cao; một chip mới được phát triển tại CRYPTO'92 có 50k transistor, đạt tốc độ mã hóa 1GB/s với đồng hồ 250MHz, có giá khoảng 300 USD Tính đến năm 1991, có 45 phần cứng và chương trình cài sẵn thực thi DES đã được ủy ban tiêu chuẩn quốc gia Mỹ phê chuẩn.
Một ứng dụng quan trọng của DES là trong giao dịch ngân hàng, theo các tiêu chuẩn của Hiệp hội Ngân hàng Mỹ DES được sử dụng để mã hóa các con số, mã PIN và trao đổi tài khoản qua máy ATM Ngoài ra, DES cũng được Clearing House Interbank Payments System (CHIPS) áp dụng cho các giao dịch liên quan đến hơn 1,5 triệu tỷ USD mỗi tuần.
DES cũng đƣợc sử dụng rộng rãi trong các tổ chức chính phủ nhƣ: Bộ năng lƣợng, Bộ tƣ pháo và hệ thống phản chứng liên bang
2.4.3 Một vài kết luận về mã DES
Có nhiều phương pháp mã hóa để bảo vệ dữ liệu an toàn Để đánh giá hiệu quả của một thuật toán mã hóa, cần xem xét các yếu tố như tính bảo mật, độ phức tạp, tốc độ thực hiện và khả năng phân khóa trong môi trường đa người dùng.
Phương pháp mã hóa DES hiện nay được sử dụng rộng rãi, với các chip chuyên dụng được thiết kế để tăng tốc độ xử lý Nhiều nhà toán học và tin học đã nghiên cứu trong nhiều năm để tìm cách phá vỡ DES, nhưng cho đến nay chỉ có 4 khóa yếu và 12 khóa tương đối yếu được phát hiện Việc phá vỡ DES bằng phương pháp "vét cạn" yêu cầu một khoản chi phí lớn và thời gian dài, vì chưa có thông báo nào về việc tìm ra cách giải mã hiệu quả hơn.
Nhược điểm của DES là nó sử dụng thuật toán mã hóa đối xứng với độ dài khóa 56 bit Mặc dù vào thời điểm phát minh, việc thực hiện 50.000 tỷ phép mã hóa để phá vỡ DES bằng cách thử các khóa có vẻ khó khăn, nhưng với sự tiến bộ của phần cứng hiện nay, độ dài 56 bit có còn đủ an toàn? Hơn nữa, mức độ phức tạp của các phép thay thế trong DES có đủ để bảo đảm an toàn thông tin như mong đợi hay không vẫn là một vấn đề đang được tranh luận.
DES đã được phân tích kỹ lưỡng và được công nhận là một phương pháp mã hóa vững chắc Những hạn chế của nó đã được hiểu rõ và được xem xét trong quá trình thiết kế để nâng cao độ an toàn Hiện nay, hệ thống mã hóa sử dụng DES mở rộng (3DES) đang được ứng dụng rộng rãi, với chiều dài khóa lên đến 128 bit và kích thước khối cũng đạt 128 bit Do đó, độ an toàn của DES mở rộng cao hơn rất nhiều so với phiên bản ban đầu.
CÁC SƠ ĐỒ CHIA SẺ BÍ MẬT
Khái niệm về chia sẻ bí mật
Thông tin cần giữ bí mật được phân chia thành nhiều phần và giao cho nhiều cá nhân, mỗi người nắm giữ một phần Những thông tin này có thể được xem lại khi tất cả các cá nhân đồng ý Khi các phần được kết hợp lại, chúng sẽ tạo thành thông tin gốc.
- Thông tin cần giữ bí mật đƣợc chia thành nhiều mảnh 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
- Khi các mảnh đƣợc khớp lại sẽ cho ta thông tin gốc
Các mảnh đƣợc chia Thông tin bí mật
Sơ đồ chia sẻ bí mật
Trong một ngân hàng, để mở một két hàng ngày, cần thiết kế một hệ thống bảo mật cho phép chỉ hai thủ quỹ lâu năm có thể mở két, trong khi một mình mỗi người không thể thực hiện điều này Vấn đề này có thể được giải quyết hiệu quả thông qua lược đồ chia sẻ bí mật, đảm bảo an toàn và tin cậy cho ngân hàng.
3.2.1 Khái niệm “ sơ đồ chia sẻ bí mật”:
Sơ đồ chia sẻ bí mật là phương pháp phân chia một bí mật thành nhiều phần và phân phối cho một nhóm người tham gia Các tập con trong nhóm này được chỉ định để có thể khôi phục lại bí mật bằng cách kết hợp dữ liệu mà họ sở hữu.
Một sơ đồ chia sẻ bí mật lý tưởng đảm bảo rằng bất kỳ nhóm người tham gia nào không được chỉ định đều không thể truy cập thông tin bí mật.
Sơ đồ ngưỡng A(t,w) là một phương pháp phân chia khóa k cho một tập hợp w thành viên (ký hiệu là P), trong đó bất kỳ t thành viên nào có thể tính toán được khóa k, nhưng không có nhóm nào gồm (t-1) thành viên có khả năng thực hiện điều đó.
Giá trị k được chọn bởi một thành viên đặc biệt được gọi là ngươi phân phối (D) D P
D phân chia khóa k cho từng thành viên trong tập P bằng cách cung cấp cho mỗi người một thông tin cục bộ gọi là mảnh Các mảnh này được phân phát một cách bí mật, đảm bảo rằng không thành viên nào biết được mảnh của người khác Một tập con các thành viên B trong P sẽ kết hợp các mảnh của họ để tính toán khóa k, hoặc có thể ủy quyền cho một người đáng tin cậy để thực hiện việc này.
Nếu |B| ≥ t thì họ có khả năng tính đƣợc k
Nếu |B| ≤ t thì không thể tính đƣợc k
Gọi P là tập các giá trị đƣợc phân phối khóa K: P = { p i : 1≤ i≤ w}
K là tập khóa: tập tất cả các khóa có thể
S tập mảnh: tập tất cả các mảnh có thể
Sau đây ta trình bày một sơ đồ ngƣỡng đƣợc gọi là sơ đồ ngƣỡng Shamir
1 D chọn w phần tử khác nhau và khác 0 trong Zp và kí hiệu chúng là: x i , 1≤ i ≤ w (w ≥ p+1)
Với 1≤ i ≤ w, D cho giá trị x i cho p i Các giá trị x i là công khai
2 Giả sử D muốn phân chia khóa k Zp D sẽ chọn một cách bí mật (nhẫu nhiên và độc lập) t-1 phần tử Zp, a i …… a i-1
4 Với 1 ≤ i ≤ w, D sẽ trao mảnh y i cho p i
Hình 3.1 : Sơ đồ ngƣỡng Shamir
Trong sơ đồ 3.1 D, một đa thức ngẫu nhiên a(x) được xây dựng với bậc tối đa là t-1, trong đó hằng số đóng vai trò là khóa k Mỗi thành viên p i sẽ tương ứng với một điểm (x i, y i).
Ta xét một tập con B gồm t thành viên tạo lại khóa k bằng 2 phương pháp:
Phép nội suy đa thức
Công thức nội suy Lagrange
Tạo lại khóa k bằng phương pháp sử dụng phép nội suy đa thức:
Giả sử các thành viên p i , muốn xác định khóa k
Ta biết rằng: y ti = a(x i ) trong đó a(xi) là một đa thức bí mật đƣợc D chọn Vì a(x) có bậc lớn nhất là t-1 nên ta có thể viết nhƣ sau: a(x) = a 0 + a 1 x+……+a i-1 x i-1
Ta có hệ các phương trình tuyến tính (trong Zp) như sau: a 0 + a 1 x i1 +a 2 x………+a t-1 x it1 t-1 = y i1 a 0 + a 1 x i2 +a 2 x i2 ………+at-1x it t-1 = y i2
Trong đó hệ số a 0, a 1 ,… a t-1 là các phần tử chƣa biết của Z p , còn a 0 = K là khóa
Vì y i = a(x i ) nên B có thể thu được t phương trình tuyến tính t ẩn (a 0 , a1,….a t-1 ), ở đây tất cả các phép tính số học đều đƣợc thực hiện trên Z p
Nếu các phương trình này độc lập tuyến tính thì sẽ cho ta nghệm duy nhất và thu đƣợc giá trị khóa a 0
Sau đây chúng tôi trình bày một thủ tục (protocol) chia sẻ bí mật dựa trên ý tưởng của Languange:
Giá sử ta có n thực thể A 1 ,A 2 ,… A n và có một người ủy quyền B biết được toàn bộ khóa bí mật SєN
Người được ủy quyền B thực hiện các bước sau đây:
1 B chọn 1 số nguyên tố P đủ lớn sao cho: n