RSA double signature with additive splitting: $N = 91$, $e = 11$, $d = 59$. The secret exponent is split as $d \equiv T_1 + T_2 \pmod{\varphi(N)}$ with $T_1 = 126$. The hash is the digit sum of $m = 12345678$ taken mod 10, and party 1's partial signature is $h(m)^{T_1} \bmod N = 64$. Find $T_2$, party 2's partial signature and the full signature.

Question

Accepted Answer

$T_2 = 5$, party 2 signs $6^5 \equiv 41$, and the full signature is $s = 64 \cdot 41 \equiv 76 \pmod{91}$.
1. $\varphi(N)$: $91 = 7 \cdot 13$, so $\varphi(91) = 6 \cdot 12 = 72$.
2. The second share: $59 \equiv 126 + T_2 \pmod{72}$, so $T_2 \equiv 59 - 126 = -67 \equiv 5 \pmod{72}$. The shares live mod $\varphi(N)$, which is why $T_1$ may even be larger than $d$.
3. The hash: digit sum $1+2+\dots+8 = 36$, so $h(m) = 36 \bmod 10 = 6$.
4. Party 2's partial signature: $6^{5} = 7776 \equiv 41 \pmod{91}$.
5. Combine by multiplying: $s \equiv 64 \cdot 41 = 2624 \equiv 76 \pmod{91}$, because $h^{T_1} \cdot h^{T_2} = h^{T_1 + T_2} = h^{d}$.
Checks: directly $6^{59} \equiv 76 \pmod{91}$, and verification gives $76^{11} \equiv 6 = h(m)$.
Gotcha: additive shares are added mod $\varphi(N)$, but the partial signatures are multiplied mod $N$. With multiplicative splitting ($d \equiv T_1 \cdot T_2$) the second party would instead raise the first partial signature to $T_2$.