Shamir's Secret Sharing: Kho báu của tên cướp và Alibaba

Một buổi tối khuya trong sa mạc Ả Rập...

Sau khi Ali Baba vô tình phát hiện ra câu thần chú “Vừng ơi, hãy mở ra!” và cuỗm mất một phần kho báu khổng lồ, tên trùm của bốn mươi tên cướp nổi cơn thịnh nộ. Hắn nhận ra một sự thật phũ phàng: bí mật chỉ an toàn khi không ai có toàn bộ nó. Nếu chỉ một tên cướp phản bội, bị bắt, hoặc say rượu buột miệng, cả hang động và kho báu còn lại sẽ tiêu tan.

Vì vậy, hắn triệu tập bốn mươi tên cướp lại trong hang đá tối om. Hắn không còn tin tưởng bất kỳ ai giữ toàn bộ câu thần chú nữa. Thay vào đó, hắn chia bí mật thành 40 mảnh – mỗi tên cướp được giao đúng một mảnh giấy nhỏ, được viết bằng mực vô hình và những con số kỳ lạ mà chỉ hắn mới hiểu. Lần này, hắn đã làm một việc cực kỳ thông minh: Hắn thiết kế sao cho chỉ cần đủ 10 mảnh là có thể ghép lại thành câu thần chú hoàn chỉnh. Còn nếu chỉ có 9 mảnh thì dù các tên cướp có cố gắng ghép thế nào, chúng cũng chỉ là một mớ chữ cái và con số lộn xộn, vô nghĩa hoàn toàn.

Hắn cười lớn trong bóng tối: “Các ngươi nghe rõ đây! Một mình ta không mở được cửa. Chín tên các ngươi cũng không mở được. Chỉ khi ít nhất có mười tên trong chúng ta cùng đứng chung một chỗ và ghép mảnh lại… lúc đó, ‘Vừng ơi, hãy mở ra!’ sẽ vang lên lần nữa!”

Từ đó, kho báu mới được giấu ở một hang động bí mật khác. Mỗi tên cướp chỉ giữ một mảnh nhỏ của bản đồ và một phần của câu thần chú. Chúng không dám phản bội nhau, vì một mình không làm được gì. Nhưng cũng không tên nào có thể độc chiếm kho báu, vì phải cần đúng 10 tên cướp hợp tác mới mở được cửa.

Ở trên là một câu chuyện mình tự “sáng tác” ra dẫn đề cho bài viết về kỹ thuật Shamir’s Secret Sharing (SSS) - giấu một bí mật bằng cách chia nhỏ thành nhiều phần sao cho phải tổng hợp được ít nhất một số phần chia mới khôi phục được. Kỹ thuật này do Adi Shamir đề xuất vào năm 1979.

Ý tưởng

Lợi dụng vào kỹ thuật nội suy Lagrange, ta có thể giấu bí mật vào trong một (hoặc nhiều) hệ số của đa thức bí mật $P(x)$ bậc $t-1$ . Sau đó, chọn các điểm ngẫu nhiên $x_i \ne 0$ với $i = \{1,2,\dots,n\}, \quad n \gt t$ rồi tính $P(x_i)$. Mỗi phần chia sẽ là một cặp giá trị $\left(x_i, P(x_i)\right)$. Như vậy để nội suy ngược lại đa thức $P(x)$, bắt buộc phải tập hợp đủ $t$ phần chia.

Một số setup cơ bản cho trường hợp đơn giản

Bí mật (Secret) là một số nguyên $s$. Ngưỡng khôi phục (Threshold $t$) là số lượng phần chia tối thiểu cần để khôi phục lại bí mật. Số lượng phần chia (shares) là $n$.

Bước 1: Xây dựng đa thức bí mật $P(x)$

Trong đó:

• Hằng số tự do $f(0)=s$ chính là bí mật bị cất giấu

• $p$ là một số nguyên tố lớn để đảm bảo tính bảo mật

• Các hệ số $a_1, a_2, \dots, a_{t-1}$ được chọn ngẫu nhiên sao cho $a_i \in [0, p-1]$

Bước 2: Tạo $n$ phần chia (shares)

Tính toán $n$ điểm khác nhau trên đa thức $P(x)$:

Mỗi người nhận được đúng một cặp số $(x_i,y_i)$.

Bước 3: Khôi phục bí mật

Khi có đủ $t$ phần chia bất kỳ, ta có thể dùng công thức nội suy Lagrange để tính lại giá trị $f(0)=s$:

với

Như vậy, chỉ cần $t$ mảnh là đủ để tính ra $s$ một cách chính xác 100%. Nhưng nếu chỉ có $t – 1$ mảnh, thì dù có bao nhiêu phép tính, đa thức bậc $t – 1$ vẫn có vô số nghiệm khác nhau, nên không thể xác định được $s$. Bí mật vẫn hoàn toàn an toàn.

Ví dụ minh họa

Đa thức bậc 2:

Tính 5 mảnh chia sẻ (với $x_i=i$ cho đơn giản):

• Share 1: $(x=1, y=7918)$

• Share 2: $(x=2, y=46596)$

• Share 3: $(x=3,y=62842)$

• Share 4: $(x=4,y=56656)$

• Share 5: $(x=5,y=28038)$

Giả sử, ta khôi phục lại:

Từ các phần share $(x=2, y=46596), (x=4,y=56656), (x=5,y=28038)$, ta tính hệ số Lagrange $\ell_i(0)$ cho từng điểm:

• Với $x=2$: $\displaystyle \ell_1(0) = \left( \frac{0-4}{2-4} \right) \times \left( \frac{0-5}{2-5} \right) = 21849$

• Với $x=4$: $\displaystyle \ell_2(0) = \left( \frac{0-2}{4-2} \right) \times \left( \frac{0-5}{4-5} \right) = 65532$

• Với $x=5$: $\displaystyle \ell_3(0) = \left( \frac{0-2}{5-2} \right) \times \left( \frac{0-4}{5-4} \right) = 43694$

Tính tổng để khôi phục $s$:

Ta có:

• Term 1: $46596 \times 21849 \equiv 24246 \pmod{65537}$

• Term 2: $56656 \times 65532 \equiv 44405 \pmod{65537}$

• Term 3: $28038 \times 43694 \equiv 9231 \pmod{65537}$

Cộng lại:

Vậy ta đã khôi phục thành công bí mật $s=12345$.