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.

  • $\begingroup$ 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) $\endgroup$ – Binou Jan 5 at 8:53
  • $\begingroup$ Sorry for that, i mean $\sigma = Sig_{sk1}(m1)$ and $\sigma'= Sig_{sk2}(m2)$ $\endgroup$ – user178592 Jan 5 at 9:03
  • $\begingroup$ You are signing with public keys, are you aware this is not a proper way to peeform signatures? $\endgroup$ – Binou Jan 5 at 9:12
  • $\begingroup$ 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). $\endgroup$ – user178592 Jan 5 at 9:22
  • $\begingroup$ Is this a homework assignment? $\endgroup$ – 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.

| improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – user178592 Jan 5 at 9:35
  • $\begingroup$ 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. $\endgroup$ – Binou Jan 5 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.