Collaborative RSA Signatures

The cosign tool allows multiple cooperating parties to generate an RSA key and split the private key into shards between themselves, and then perform partial signatures of a message that can be combined into a single valid RSA signature of that message, without any of the parties having a complete copy of the private key after the initial key generation stage. It has both a unanimous mode with an unbounded number of shares, and a 2-of-3 threshold mode. The signatures produced are valid PKCS#1 v1.5 padded SHA256 hashes of the input, which makes them suitable for code signing and other applications.

Source code: github.com/osresearch/cosign

RSA

As a quick refresher, RSA finds a public key $(n, e)$ and a private key $(d)$ such that for any non-negative integer $M$ less than $n$:

$$\begin{align} (M^e)^d &= (M^d)^e \\ &= M^{(d*e)} \\ &= M \mod n \end{align}$$

The holder of the private key can compute a signature $C$ on a message $M$ by evaluating:

$$C = M^d \mod n$$

This signature can be validated by using the public exponent and modulus:

$$\begin{align} C^e\mod n & = (M^d)^e \mod n \\ & = M^{(d*e)} \mod n \\ & = M \end{align}$$

Additive key splitting

For a 2-of-2 threshold the private exponent $d$ can be split into two random parts by a trusted dealer such that:

$$d = d_a + d_b$$

Alice receives $d_a$ and Bob receives $d_b$ from the trusted dealer, who discards $d$ so that no one has access to the private exponent anymore.

When Alice and Bob want to sign a message $M$, they each compute a partial signature and send it to an outside party:

$$\begin{align} C_a & = M^{d_a} & \mod n \\ C_b & = M^{d_b} & \mod n \end{align}$$

This party can merge the two signatures to produce a valid signature on the message with only knowledge of the public modulus $n$:

$$\begin{align} C & = (C_a * C_b) & \mod n \\ & = (M^{d_a} * M^{d_b}) & \mod n \\ & = (M^{(d_a + d_b)}) & \mod n \\ & = (M^d) & \mod n \end{align}$$

This signature can be validated by the party doing the merge if they know the original message $M$ by using the public key.

Threshold signatures

For the 2-of-3 threshold signatures it is necessary to split the private exponent $d$ three times for the three pairwise combinations of Alice-Bob, Alice-Carol, and Bob-Carol. Given the private exponent $d$, the trusted dealer picks six random values such that:

$$\begin{align} d & = d_{ab} + d_{ba} & \textrm{(Alice + Bob)} \\ d & = d_{ac} + d_{ca} & \textrm{(Alice + Carol)} \\ d & = d_{bc} + d_{cb} & \textrm{(Bob + Carol)} \end{align}$$

Alice receives the components $(d_{ab},d_{ac})$, Bob receives $(d_{ba},d_{bc})$, and Carol receives $(d_{ca},d_{cb})$. Since none of these pairs add to $d$, they do not learn the actual private exponent and they do not necessarily know which component is shared with the other parties.

Without loss of generality, Alice and Bob are signing the message $m$ this time; Carol is on holiday somewhere out of reach. Since the padding mechanism is deterministic, both Alice and Bob can compute the PKCS#1v1.5 padded SHA256 hash of the message to produce the block to be signed M=PKCS(SHA256(m))

Alice computes her two partial signature with her two components of the private exponent and publishes:

$$(S_{a0},S_{a1}) = ( M^{d_{ab}}, M^{d_{ac}} ) \mod n$$

While Bob computes and publishes his two partial signatures:

$$(S_{b0},S_{b1}) = ( M^{d_{ba}}, M^{d_{bc}} ) \mod n$$

Anyone with the public exponent and modulus can now perform four trial signature merges with the partial signature from Alice and Bob. The merging parties computes all values are $\mod n$:

$$\begin{align} S_0 & = S_{a0} * S_{b0} = M^{d_{ab}}*M^{d_{ba}} = M^{(d_{ab} + d_{ba})} \\ S_1 & = S_{a1} * S_{b0} = M^{d_{ac}}*M^{d_{ba}} = M^{(d_{ac} + d_{ba})} \\ S_2 & = S_{a0} * S_{b1} = M^{d_{ab}}*M^{d_{bc}} = M^{(d_{ab} + d_{bc})} \\ S_3 & = S_{a1} * S_{b1} = M^{d_{ac}}*M^{d_{bc}} = M^{(d_{ac} + d_{bc})} \end{align}$$

The merging party now needs to try validating each of these trial signatures with the public exponent and modulus $(e,n)$ to determine which one is the proper combination of key pairs for the valid signature:

$$\begin{align} M_0 & = (S_0)^e = (M^{(d_{ba} + d_{ab})})^e \mod n \\ M_1 & = (S_1)^e = (M^{(d_{bc} + d_{ab})})^e \mod n \\ M_2 & = (S_2)^e = (M^{(d_{ba} + d_{ac})})^e \mod n \\ M_3 & = (S_3)^e = (M^{(d_{bc} + d_{ac})})^e \mod n \end{align}$$

Only one of these trial verifications will result in a proper PKCS#1v1.5 padded message. In this case message $S_0$ is the correct combination of partial signatures that results in a valid signature:

$$\begin{align} M_0 &= (S_0)^e & \mod n \\ &= (M^{(d_{ba} + d_{ab})})^e & \mod n \\ &= (M^d)^e & \mod n \\ &= M^{(d*e)} & \mod n \\ &= M & \mod n \end{align}$$

The signature merging party can select $S_0$ as the one to publish as the valid signature on the message $m$, without knowledge of $m$ since only the SHA256 hash of $m$ is contained in the PKCS#1 v1.5 padding $M$, and also without any knowledge of the private exponent $d$ since only the public modulus and exponent $(n,e)$ are required to validate the signature.

Cryptography Security 2020

---

Last update: November 9, 2020