Ở 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 Lagrnội suy Lagrangeange, 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
Mỗi phần chia (Share) là một cặp giá trị \((x,y)\)
Các bước thực hiện
Thiết lập bí mật
Chọn số nguyên tố \(p\) lớn để làm modulo cho đa thức
Chọn ngẫu nhiên \(a_1, a_2,\dots,a_{t-1} \le p\)
Lập đa thức \(P(x) = s+a_1x+a_2x^2+\dots+a_{t-1}x^{t-1} \mod p\)
Chọn ngẫu nhiên \(x_1,x_2, ... x_n\) với \(n>t\), rồi tính \(P(x_i)\)
Chia làm \(n\) phần, mỗi phần là một cặp giá trị \((x_i, P(x_i))\)
Khôi phục bí mật
Dùng nội suy Lagrange để khôi phục bí mật với \(t\) phần chia \(\displaystyle P(x) = \sum_{i=0}^ny_i.\ell_i(x)\) với \(\displaystyle \ell_i(x) = \prod_{j=0, j \ne i}^n \frac {x-x_j}{x_i-x_j}\)
Ví dụ
Bí mật \(s = 5\), các hệ số \(a_1=3, a_2=2\) với \(p=17\), nhúng vào đa thức \(P(x) = s + a_1x+a_2x^2 \mod p = 5 + 3x + 2x^2 \mod 17\)
Tính:
\(x_1=1, P(x_1)=P(1) = 5 + 3.1 + 2.1^2 = 10 (\mod 17)\)
\(x_2=2, P(x_2)=P(2) = 5 + 3.2 + 2.2^2 = 19 = 2 (\mod 17)\)
\(x_3=3, P(x_3)=P(3) = 5 + 3.3 + 2.3^2 = 32=15 (\mod 17)\)
Khôi phục lại từ các phần share \((1,10),(2,2),(3,15)\):
\(\displaystyle \ell_1(x) = \prod_{j=1, j \ne i}^3 \frac {x-x_j}{x_1-x_j} = \frac {x-2}{1-2} \frac {x-3}{1-3} = \frac {x^2-5x+6} 2\)
\(\displaystyle \ell_2(x) = \prod_{j=1, j \ne i}^3 \frac {x-x_j}{x_2-x_j} = \frac {x-1}{2-1} \frac {x-3}{2-3} = \frac {x^2-4x+3} {-1}\)
\(\displaystyle \ell_3(x) = \prod_{j=1, j \ne i}^3 \frac {x-x_j}{x_3-x_j} = \frac {x-1}{3-1} \frac {x-2}{3-2} = \frac {x^2-3x+2} 2\)
Tính \(\displaystyle P(x) = \sum_{i=0}^ny_i.\ell_i(x)=10\frac {x^2-5x+6} 2+2\frac {x^2-4x+3} {-1}+15\frac {x^2-3x+2} 2 (\mod 17)\)
Với modulo \(p=17\) thì phép tính chia lànghịch đảo của phép nhân, số âm là nghịch đảo của phép cộng nên: \(\displaystyle \frac 1 2 = 2^{-1} = 9, -1=16 \Rightarrow \frac 1 {16} =16^{-1} =16\), vậy:
$$\begin{align*} P(x)&=10.(x^2-5x+6).9+2.(x^2-4x+3).16+15.(x^2-3x+2).9 (\mod 17)\\ &=90(x^2-5x+6)+32(x^2-4x+3)+135(x^2-3x+2) (\mod 17)\\ &=257x^2-983x+906 (\mod 17) \\ &= \boxed{2x^2+3x + 5 (\mod 17)} \end{align*}$$
Như vậy, ta đã khôi phục lại được đa thức \(P(x)\) thông qua 3 phần share \((1,10),(2,2),(3,15)\) và từ đó biết được bí mật \(s=5\).