第四章     秘密分享

pages 000

例題01：M分散在三毛、四郎及五爺中。假設n=2110763。將M-r-s=1008369交三毛，將r=593647交四郎，最後將 s=631870交五爺。請重建原先的M。

Mod[1008369 + 593647 + 631870, 2110763]

例題02：(4,9)-門檻法，有九位參與只需其中任四位就可重建M, 但三位卻無法得M的任何資訊。假設M=20151600190503180520(對應英文的 top secret)。選質數p,  如p=123456 789012345678949。再選隨機 s_1=72877568505071533406, s_2= 21320565390661104 041,及 s_3= 51801043115268823024 mod{p} 且形成s(x)= M+s_1x+s_2x^2+s_3x^3 mod{p}。分配(x,s(x))給這九位。這些x值沒有必要隨機選取，所以我們就用x=1,2,3,...,9。

abc = " abcdefghijklmnopqrstuvwxyz";
\(\(no = "000102030405060708091011121314151617181920212223242526";\)\)
digitalize = 
        Table[StringTake[abc, {i}] -> 
            StringTake[no, {2*i - 1, 2*i}], {i, 1, 27}];
alphabetize = 
        Table[StringTake[no, {2*i - 1, 2*i}] -> 
            StringTake[abc, {i}], {i, 1, 27}];
Q[plaintext_] := 
        ToExpression[StringReplace[plaintext, digitalize]];

<< NumberTheory`NumberTheoryFunctions`

p = NextPrime[123456789012345678901]

M = Q["top secret"]; 
    s1 = 72877568505071533406;
s2 = 21320565390661104041; 
    s3 = 51801043115268823024;
s[x_] := M + s1*x + s2*x^2 + s3*x^3; M

c = Table[{x, s[x]}, {x, 9}] // ColumnForm

假設三、二、五、一等四位老爺彼此合作決定M。使用拉格蘭茲內插多項式，計算經過他們四點的多項式為：

InterpolatingPolynomial[{c[[1]][[3]], c[[1]][[2]], c[[1]][[5]], c[[1]][[1]]}, 
        x] // Simplify

n = {{1, 3, 9, 27}, {1, 2, 4, 8}, {1, 5, 25, 125}, {1, 1, 1, 1}}; 
    c = {{1829297558333925938755}, {665597343685441247688}, {7392683966890991326575}, {166150777201504640991}};
LinearSolve[n, c, Modulus -> p]

例題03：(5,8)-門檻法，質數p=987541, 其中五份(9853,853), (4421,4387), (6543,1234), (93293,78428),(12398,7563) 試求出其祕密。

\(\(\(PolynomialMod[
      InterpolatingPolynomial[{{9853, 853}, {4421, 4387}, {6543, 
            1234}, {93293, 78428}, {12398, 7563}}, x], 987541]\)\(
\)
    \)\)

p = 987541; x1 = 9853; x2 = 4421; x3 = 6543; x4 = 93293; 
    x5 = 12398;
m = {{1, x1, x1^2, x1^3, x1^4}, {1, x2, x2^2, x2^3, x2^4}, {1, x3, 
            x3^2, x3^3, x3^4}, {1, x4, x4^2, x4^3, x4^4}, {1, x5, x5^2, x5^3, 
            x5^4}};
b = {{853}, {4387}, {1234}, {78428}, {7563}};
LinearSolve[m, b, Modulus -> p]

Solve[{m . {{N}, {t1}, {t2}, {t3}, {t4}} == b, 
        Modulus == p}, Mode -> Modular]

例題04：令 p=73。假設分配給甲、乙、丙、丁、戊五人平面：
甲：z= 4x+19y+68 乙：z=52x+27y+10 丙：z=36x+65y+18 丁：z=57x+12y+16
戊：z=34x+19y+49 若甲、乙、丙三人要合作讓秘密重現，他們就得解方程式

Solve[{{{4, 19, -1}, {52, 27, -1}, {36, 
                65, -1}} . {{x0}, {y0}, {z0}} == {{-68}, {-10}, {-18}}, Modulus == 73}, Mode -> Modular]