第九章數位簽署

pages 195 - 214

例題01

p = {874837070950970950705711, 
          874837070950970950706063};
q = {95493206520967097607601063, 95493206520967097607601007}; 
    n = p*q

e = {575857, 399750509}; 
    d = PowerMod[e, -1, (p - 1) (q - 1)]

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_] := StringReplace[plaintext, digitalize];
Qd[plaintext_] := ToExpression[Q[plaintext]];

m = Qd["hello"]

s = PowerMod[m, d[[1]], n[[1]]]

se = PowerMod[{m, s}, e[[2]], n[[2]]]

ms = PowerMod[se, d[[2]], n[[2]]]

PowerMod[ms[[2]], e[[1]], n[[1]]] == 
      ms[[1]] == m
Exit

例題02

a = 711;
<< NumberTheory`NumberTheoryFunctions`
findp[x_] := 
        Module[{q}, 
          q = x; 
While[PrimeQ[q*40320 + 1] == False, 
            q = NextPrime[q]]; 
p = q*40320 + 1; 
          p];

{p = findp[8864235901213661], q = (p - 1)/40320, 
      alp = PrimitiveRoot[p]}

bet = PowerMod[alp, a, p]

SeedRandom[711]
Random[Integer, {1, 10^8}]
k = NextPrime[%]

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_] := StringReplace[plaintext, digitalize];
Qd[plaintext_] := ToExpression[Q[plaintext]];

m = Qd["tunghai"]
r = PowerMod[alp, k, p]
s = Mod[PowerMod[k, -1, p - 1]*(m - a*r), p - 1]

verify[m_, r_, s_] := 
      Mod[PowerMod[bet, r, p]*PowerMod[r, s, p] - PowerMod[alp, m, p], 
          p] == 0

verify[m, r, s]

verify[0, r, s]
verify[022505, r, s]
Exit

例題03

<< NumberTheory`NumberTheoryFunctions`
p = 225119; alpha = PrimitiveRoot[p]

bet = 18191;
sig1 = {151405, 164130, 130777};
sig2 = {202315, 164130, 164899};

GCD[sig1[[3]] - sig2[[3]], p - 1]

Solve[{(sig1[[3]] - sig2[[3]])/2*
            k == (sig1[[1]] - sig2[[1]])/2, 
        Modulus == (p - 1)/2}, k, Mode -> Modular]

L = 
        Table[If[
            PowerMod[alpha, 239 + i*(p - 1)/2, p] == sig1[[2]], 
            1, 0], {i, 0, 1}];
k = 
      239 + (Position[L, Max[L]][[1]][[1]] - 
              1)*(p - 1)/2

Mod[sig1[[1]] - sig1[[3]]*k, p - 1]
GCD[sig1[[2]], p - 1]

Solve[{sig1[[2]]/2*a == (sig1[[1]] - sig1[[3]]*k)/
            2, Modulus == (p - 1)/2}, a, 
      Mode -> Modular]

L = 
        Table[If[PowerMod[alpha, 28862 + i*(p - 1)/2, p] == bet, 1, 
            0], {i, 0, 1}];
a =  
      28862 + (Position[L, Max[L]][[1]][[1]] - 
              1)*(p - 1)/2

生日攻擊法

1 - Product[1 - i/365, {i, 22}] // N
Exit

例題06 DSA 乃是 ElGamal演算法的一種修飾。質數p與q如例02(alp 為p下一原根)。

{p, q, alp} = {357405991536950536321, 8864235901214051, 
          13};

alp1 = PowerMod[alp, 40320, p]

a = 711; bet1 = PowerMod[alp1, a, p]

SeedRandom[711]
k1 = Random[Integer, {1, q - 1}]

r1 = Mod[PowerMod[alp1, k1, p], q]

m = 20211407080109;
s1 = Mod[PowerMod[k1, -1, q]*(m + a*r1), q]

verify1[m_, r1_, s1_] := 
      Module[{u1, u2}, 
        u1 = Mod[PowerMod[s1, -1, q]*m, q]; 
u2 = 
          Mod[PowerMod[s1, -1, q]*r1, q]; 
Mod[
            Mod[PowerMod[alp1, u1, p]*PowerMod[bet1, u2, p], p], q] == 
          r1]

verify1[m, r1, s1]