Chapter 4. Digital Signatures

Exercise (Câu 4.1)

Đáp án: \(d = 561517\), \(N = 661643\), \(sig = 206484\).

Exercise (Câu 4.3)

Đáp án \(p = 212081\), \(q=128311\) nên

\[d = 18408628619 \Rightarrow S = D^d \pmod N = 22054770669.\]

Exercise (Câu 4.4)

Đáp án: with \(c = m^{e_B} \pmod{N_B}\) and \(s = Hash(m)^{d_A} \pmod{N_A}\)

\[c^{d_B} = m^{e_B\cdot d_B} \pmod{N_B} = m, \ s^{e_A} = Hash(m)^{d_A \cdot e_A} \pmod{N_A} = Hash(m).\]

Hence this method works.

Exercise (Câu 4.5)

Đáp án: với \(A = g^a \pmod p = 2065\), ta tính

\[S_1 = g^k \pmod p = 3534, S_2 = (D-a\cdot S_1) k^{-1} \pmod{p-1} = 5888.\]

Hence signature is \((S_1, S_2) = (3534, 5888)\)

Exercise (Câu 4.6)

Đáp án: \(A^{S_1} \cdot S_1^{S_2} \equiv g^D \pmod p\), so \((S_1^", S_2^")\) is valid signature.

Exercise (Câu 4.8)

Đáp án: \(S_1 = S_1' = g^k \pmod p\), from here Eve can know at first glance that the same random element \(k\) is used

With \(S_2 = (D-a S_1) k^{-1} \pmod{p-1}\), \(S_2' = (D'-aS_1')k^{-1} \pmod{p-1}\), then

\[ \begin{align}\begin{aligned}S_2 - S_2' \equiv (D - D')k^{-1} \pmod{p-1}` (as :math:`aS_1 = aS_2`)\\k = (D-D')(S_2-S_2')^{-1} \pmod{p-1}.\end{aligned}\end{align} \]

Here we get \(D - aS_1 = S_2 k \pmod{p-1}\)

\[\begin{split}\Rightarrow \begin{cases} a = (D - S_2 k) S_1{-1} \pmod{p-1} \\ a = (D'-S_2' k) S_1^{-1} \pmod{p-1} \end{cases}.\end{split}\]

Exercise (Câu 4.9)

Đáp án: \(p \equiv 1 \pmod q\), \(1 \leqslant a \leqslant q-1\), \(A=g^a \pmod p\), \(S_1 = (g^k \bmod p) \bmod q\), \(S_2 = (D + aS_1) k^{-1} \pmod q\)

Verify: \(V_1 = D \cdot S_2^{-1} \pmod q\), \(V_2 = S_1 S_2^{-1} \pmod q\). We need to prove that \((g^{V_1} \cdot A^{V_2} \bmod p) \bmod q = S_1\)

Here we have

\[\begin{split}g^{V_1} \cdot A^{V_2} & \equiv g^{D \cdot S_2^{-1}} \cdot g^{aS_1 S_2^{-1}} \pmod p \\ & \equiv g^{(D+aS_1)S_2^{-1}} \pmod p \\ & \equiv g^k \pmod p\end{split}\]

Hence \((g^{V_1} A^{V_2} \bmod p) \bmod q = S_1\).

Exercise (Câu 4.10)

Đáp án: \((p, q, g) = (22531, 751, 4488)\). Public key \(A = 22476\) is not valid.

Exercise (Câu 4.11)

Đáp án: \(A = g^a \pmod p\). \(A = 31377\), \(g = 21947\), \(p = 103687\), then

\[a = 602, S_1 = (g^k \bmod p) \bmod q = 439, S_2 = (D + aS_1)k^{-1} \pmod q = 1259.\]