# RSA - Compute signature

I have a question in (textbook) RSA. Suppose we have two public keys $$pk_1=(e_1,N)$$ and $$pk_2=(e_2,N)$$ (with $$\gcd(e_1,e_2) = 1$$). Assume that there are $$\sigma$$,$$\sigma'$$ such that $$\sigma$$ and $$\sigma'$$ are a valid signature on $$m_1$$ and $$m_2$$ under $$pk_1$$ and $$pk_2$$ respectively ($$m_1$$ and $$m_2$$ are messages in $$\mathbb{Z}_N$$ ). I am trying to compute the signature $$\sigma$$ from $$N,e_1,e_2,m_1,m_2$$.

Any help would be appreciated.

• Are you implying $\sigma = Sig_{sk1}(m1)= Sig_{sk2}(m2)$? If so you only have to compute a classical signature either for $m1$ given $sk1$ or $m2$ given $sk2$. Note that signatures are computed with private keys, not public keys (in the case of RSA, use the exponent d and the prime factors $p,q$ of N) – Binou Jan 5 at 8:53
• Sorry for that, i mean $\sigma = Sig_{sk1}(m1)$ and $\sigma'= Sig_{sk2}(m2)$ – user178592 Jan 5 at 9:03
• You are signing with public keys, are you aware this is not a proper way to peeform signatures? – Binou Jan 5 at 9:12
• I didn't mean that we sign with public keys. I mean that we sign with the private keys sk1,sk2 respectively, but these signatures are valid (under pk1,pk2). – user178592 Jan 5 at 9:22
• Is this a homework assignment? – kelalaka Jan 5 at 10:28

Let $$d_1, d_2$$ be inverses of $$e_1,e_2$$ respectively mod $$(p-1)(q-1)$$ where $$N=pq$$ with $$p,q$$ two large primes.
To sign the message $$m_1$$, you will compute $$s_1={m_1}^{d_1}\ [N]$$.
To verify the signature, provided $$m_1, s_1$$, one will compute $${s_1}^{e_1}\ [N]$$ and check whether this equals to the message $$m_1$$ or not.
• OK I see. Thank you for this. And if now we assume that there is σ such that σ is a valid signature on m1 and m2 under pk1 and pk2 respectively (m1 and m2 are messages in $Z_N$ ). Note : This time the signature is the same and i want to compute σ via N,e1,e2,m1,m2. – user178592 Jan 5 at 9:35
• You do exactly the same. A signature is actually a pair $s, m$, where you provide the message $m$ that has been signed in $s$. Note that in practice, this is not likely to happen. – Binou Jan 5 at 9:39