第九章一般習題

pages 214 - 215

9.1.1. 試證在艾爾給默簽署法當中，若有人發現其中的 k 值，則 a 值也可以被決定。

<< NumberTheory`NumberTheoryFunctions`
a = 711; p = Prime[3149]
alp = PrimitiveRoot[p]
bet = PowerMod[alp, a, p]

k = 59694043; m = 20211407080109; 
    r = PowerMod[alp, k, p]
s = Mod[PowerMod[k, -1, p - 1]*(m - a*r), p - 1]

Clear[a]
Solve[{r*a == m - k*s, Modulus == p - 1}, a, 
      Mode -> Modular]

9.1.2. (x,γ,δ) 是ElGamal簽署法所簽的信息, 其中gcd(γ,p-1)=1.選取 h 滿足 gcd(h,p-1)=1 \(TraditionalForm\`且\ γ\_1 = γ\^h\) mod p 令 (Subscript[δ, 1])=δγ\(TraditionalForm\`\_1\) (h^(-1)) (γ^(-1)) mod p-1 (a) 試求一有效簽署為 ((Subscript[x, 1]),(Subscript[γ, 1]),(Subscript[δ, 1])) 的信息 (Subscript[x, 1]) (b) 此法允准六姑在信息 (Subscript[x, 1]) 上偽造簽名。為什麼這不大可能會帶來問題？

{h = Prime[711], GCD[h, p - 1], GCD[r, p - 1]}

r1 = PowerMod[r, h, p]
m1 = 
      Mod[m*r1*PowerMod[r, -1, p - 1], p - 1]
s1 = 
      Mod[s*r1*PowerMod[h, -1, p - 1]*PowerMod[r, -1, p - 1], 
        p - 1]

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

verify[m, r, s]

verify[m1, r1, s1]

Exit

第九章電腦習題

page 215

9.2.1. 使用 ElGamal 簽署法來簽署信息，其中 p=499605121, α=13, β=78598520。兩簽署過的信息 (m, r, s)：(805121215,442935452,339082137)(=hello),
(22505, 442935452, 459999847)(=bye)。求 k 值並求 a 值使得 β = (α^a) mod p

<< NumberTheory`NumberTheoryFunctions`
p = 499605121; alp = PrimitiveRoot[p]

bet = 78598520;
sig1 = {805121215, 442935452, 339082137};
sig2 = {22505, 442935452, 459999847};

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

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

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

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

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

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

PowerMod[alp, a, p] == bet
Exit

9.2.2. 三毛與四郎有如下之 RSA 參數：
(Subscript[n, 3])=171024704183616109700818066925197841516671277, (Subscript[e, 3])=1571
(Subscript[n, 4])=839073542734369359260871355939062622747633109, (Subscript[e, 4])=87697
四郎知道 (Subscript[p, 4])=98763457697834568934613, (Subscript[q, 4])=8495789457893457345793,
此處 (Subscript[n, 4])=(Subscript[p, 4])(Subscript[q, 4])。三毛簽署了一份文件並將此文件及其簽署文 (m,s) 傳送給四郎，其中
s = (Subscript[(m^d), 3]) mod (Subscript[n, 3])。為保密，三毛使用四郎的公鑰將文件加密。四郎接到加密過的簽署文
((Subscript[m, 1]),(Subscript[s, 1]))=((Subscript[(m^e), 4]),(Subscript[(s^e), 4])) mod (Subscript[n, 4]), (Subscript[m, 1])=110441858365628787248100998144227065407226769,
(Subscript[s, 1])=194840406052113473755389604200021514790024826 求 m 並證明這來自於三毛。

n = {n3 = 171024704183616109700818066925197841516671277, 
          n4 = 839073542734369359260871355939062622747633109};

p4 = 98763457697834568934613; q4 = 8495789457893457345793; 
    n4 == p4*q4

e = {1571, 87697}; d = PowerMod[e, -1, EulerPhi[n]]

se = {m1 = 110441858365628787248100998144227065407226769, 
          s1 = 194840406052113473755389604200021514790024826};

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

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