Giới thiệu về thuật toán mật mã chia sẻ bí mật của Shamir

Chia sẻ bí mật của Adi Shamir là một thuật toán mật mã cho phép các bên khác nhau cùng chia sẻ quyền sở hữu một bí mật duy nhất bằng cách nắm giữ cổ phần . Bí mật ban đầu chỉ có thể được tái tạo bằng cách sử dụng một số lượng cổ phần tối thiểu, cho phép các bên khác nhau hợp tác mà không cần phải hoàn toàn tin tưởng lẫn nhau.

Vấn đề ví dụ

Để minh họa, hãy tưởng tượng rằng một gia đình bốn người đều dùng chung một ví Bitcoin. Ví Bitcoin này chứa một khóa cá nhân duy nhất mà tất cả các thành viên trong gia đình đều đồng sở hữu. Vì có một khóa duy nhất nên bất kỳ thành viên nào trong gia đình đều có thể sử dụng khóa đó để chi tiêu tất cả Bitcoin.

Gia đình có một vấn đề: Nếu mỗi người giữ một bản sao, thì chỉ cần một bản sao của họ bị xâm phạm để có tất cả số tiền bị đánh cắp. Nếu chỉ có một người trong số họ giữ chìa khóa, thì người đó có thể làm mất nó hoặc quyết định qua mặt các thành viên khác trong gia đình.

May mắn thay, một trong những thành viên trong gia đình cũng là một nhà mật mã học. Thay vì chia sẻ khóa gốc một cách ngây thơ, họ sử dụng SSS (chia sẻ bí mật của Shamir). Gia đình tạo ra bốn cổ phiếu và đặt ngưỡng ba, với khóa Bitcoin là bí mật ban đầu. Bây giờ, kế hoạch của họ có các thuộc tính sau:

• Họ đã không lưu trữ khóa bitcoin ở một nơi nên khó bị đánh cắp hơn
• Các thành viên trong gia đình cần hợp tác để tiêu Bitcoin, một thành viên trong gia đình không thể phản bội những người khác
• Nếu một thành viên trong gia đình chết hoặc mất phần của họ, ba thành viên còn lại vẫn có thể tạo lại chìa khóa

Hiểu Ngưỡng

Mỗi kế hoạch chia sẻ Shamir đều có tổng số cổ phần và một ngưỡng. Ngưỡng là số lượng chia sẻ cần thiết để tạo lại bí mật ban đầu. Ví dụ: với năm cổ phiếu và ngưỡng là ba, bạn chỉ cần ba trong năm cổ phần để tính bí mật ban đầu.

Toán - Đường

Một trong những tính chất toán học cơ bản được sử dụng trong chia sẻ bí mật của Shamir là thực tế rằng cần k điểm để xác định một đa thức bậc k - 1. Ví dụ:

• Chỉ có thể vẽ một đường giữa hai điểm
• Chỉ có một parabol có thể đi qua ba điểm giống nhau
• Chỉ có một đường cong khối đi qua bốn điểm giống nhau
• Có thể vẽ vô số đường thẳng qua cùng một điểm
• Có thể vẽ vô số parabol qua hai điểm giống nhau

Toán học - Hướng dẫn

Hãy để chúng tôi xây dựng một kế hoạch chia sẻ bí mật 1954 ( S) của chúng tôi với 4 ( n) lượt chia sẻ và ngưỡng là 3 ( k) .

Đầu tiên, chúng ta chọn ngẫu nhiên k - 1 số nguyên dương, vì vậy trong trường hợp của chúng ta là 2 số nguyên dương. Ta chọn ngẫu nhiên 43 và 12.

Sau đó, chúng ta xây dựng một đa thức có dạng

 y = a0 + a1*x + a2*x^2

Trong đó a0 là bí mật, và a1 và a2 là các số nguyên được chọn ngẫu nhiên của chúng ta. Chúng tôi còn lại với:

 y = 1954 + 43x + 12x^2

Sau đó, chúng tôi sử dụng công thức này để tạo 4 điểm (chia sẻ) mà chúng tôi tặng cho mỗi người tham gia.

Chia sẻ 1

(x, y) trong đó x = 1

y = 1954 + 43 * 1 + 12 * 1 ^ 2 = 2009

(1, 2009)

Chia sẻ 2

(x, y) trong đó x = 2

y = 1954 + 43 * 2 + 12 * 2 ^ 2 = 2088

(2, 2088)

Chia sẻ 3

(x, y) trong đó x = 3

y = 1954 + 43 * 3 + 12 * 3 ^ 2 = 2191

(3, 2191)

Chia sẻ 4

(x, y) trong đó x = 4

y = 1954 + 43 * 4 + 12 * 4 ^ 2 = 2318

(4, 2318)

Tái thiết

Mỗi người tham gia trong chương trình của chúng tôi hiện sở hữu một (x,y) điểm, là một cổ phiếu duy nhất. Hãy nhớ rằng chúng tôi đặt ngưỡng của chúng tôi là 3 và 3 điểm xác định một parabol (đa thức bậc 2) một cách hoàn hảo. Điều đó có nghĩa là nếu chúng ta sử dụng ba điểm, chúng ta có thể vẽ một parabol và tính a0 (bí quyết). Giả sử chúng ta có quyền kiểm soát các cổ phiếu 1, 2 và 4.

Bước 1 - Vẽ biểu đồ các điểm (chia sẻ) mà chúng tôi kiểm soát

Bước 2 - Vẽ parabol tương ứng

Bước 3 - Tìm điểm tại đó x=0 . Giá trị y của nó là bí mật

Trong trường hợp của chúng tôi, bí mật là 1954 .

Nó không thực sự đơn giản. Chúng ta cần các trường hữu hạn.

Mặc dù ví dụ chúng tôi đã làm ở trên là rất tốt cho mục đích trình diễn, nhưng nó thực sự không an toàn cho lắm. Đối với mỗi chia sẻ mà kẻ tấn công có được, chúng thực sự đang thu được ngày càng nhiều thông tin về bí mật. Trong khi hai điểm không mô tả hoàn hảo một parabol, chúng vẫn làm rò rỉ thông tin quan trọng về parabol.

Lời giải nằm trong số học trường hữu hạn . Bằng cách vẽ biểu đồ của hàm trên một trường hữu hạn có kích thước đủ lớn, đồ thị của đa thức trở nên rời rạc và phân tán, điều đó có nghĩa là kẻ tấn công không thể đưa ra các phỏng đoán có học về sự thay đổi của hàm cơ bản.

Adi Shamir

Adi Shamir là một nhà mật mã học người Israel nổi tiếng với Chia sẻ bí mật của Shamir, nhưng ông cũng là người đồng phát minh ra thuật toán RSA được sử dụng rộng rãi mà phần lớn internet được xây dựng. Shamir sinh ra ở Tel Aviv và có bằng đại học toán của trường đại học ở đó. Sau đó, ông lấy bằng thạc sĩ và bằng Tiến sĩ. các bằng Khoa học Máy tính của Viện Weizmann lần lượt vào năm 1975 và 1977.