# RSA: Is there a way to digitally sign a message without knowing the private key?

So, I am following an online course about cryptography these days, and I am stuck in an assignment. Here it is:

---------Known--------------

$$m_1$$: message 1

$$m_1$$ = 387

$$s_1$$: digital signature for $$m_1$$

$$s_1$$ = 104694095966994423550399840405679271451689287439740118881968798612714798360187905616965324945306116261186514828745033919423253353071142760352995900515279740753864505327750319034602409274084867637277266750899735986681083836544151016817569622466120342654469777762743360212628271549581658814852850038900877029382

$$m_2$$: message 2

$$m_2$$ = 2

$$s_2$$: digital signature for $$m_2$$

$$s_2$$ = 18269259493999292542402899855086766469838750310113238685472900147571691729574239379292239589580462883199555239659513821547589498977376834615709314449943085101697266417531578751311966354219681199183298006299399765358783274424349074040973733214578342738572625956971005052398172213596798751992841512724116639637

$$m_3$$: message 3

$$m_3$$ = 774

Signature scheme: Textbook

Public key

$$e$$ = 65537,

$$n$$ = 132177882185373774813945506243321607011510930684897434818595314234725602493934515403833460241072842788085178405842019124354553719616350676051289956113618487539608319422698056216887276531560386229271076862408823338669795520077783060068491144890490733649000321192437210365603856143989888494731654785043992278251

For a given $$m_3$$ create an $$s_3$$.

I tried to calculate $$\phi(n)$$ but because $$n$$ is too big I run out memory. So, any ideas?

• With just the information here, it's impossible, that's the whole point of a cryptographic signature. But it may be possible if there's additional information that leads to a flaw. For example: specific value of $n$ or $e$ that's bad in some way; digital signature scheme with a flaw (there are several different signature schemes based on RSA). – Gilles 'SO- stop being evil' Jun 22 at 12:51
• yes, I agree with you, that's why I am asking. Because it doesn't make sense. What would you consider bad values of n and e? This is what I have. e = 65537 n = 132177882185373774813945506243321607011510930684897434818595314234725602493934515403833460241072842788085178405842019124354553719616350676051289956113618487539608319422698056216887276531560386229271076862408823338669795520077783060068491144890490733649000321192437210365603856143989888494731654785043992278251 – John Jun 22 at 13:07
• And what's the task exactly? To calculate the signature of an arbitrary $m_3$? Or to calculate the signature of a specific $m_3$ whose value is given in the problem statement? Or to find a value $m_3 \notin \{m_1, m_2\}$ and its signature? What is the signature scheme (textbook, PKCS#1v1.5, PSS, something else)? – Gilles 'SO- stop being evil' Jun 22 at 13:29
• Yes sorry, my bad, $m_3$ is given. $m_3$: 774. Regarding the signature scheme, the course didn't introduce schemes yet but based on a quick search that I did, I think it is the textbook which seems to be the most naive way. – John Jun 22 at 13:39
• And what are the values of $m_1$, $m_2$ ? Maybe the task is to exploit the multiplicative property of textbook RSA? – Krystian Jun 22 at 13:52

The comment by @Krystian is spot on. Textbook RSA is multiplicative so since $$m_3=m_1 m_2,$$ then $$s_3=m_1^d m_2^d \pmod n=s_1 s_2 \pmod n.$$

Magma tells me that $$s_3$$ should be

5483355855153602627619220309939701891434212768777923480007006960005208299649205
6581008264568421280116806103922182738655624242961539966642663712352455540402732
9086686980626004891264773131893337185873828146733471102601951184587947342940793
37057046673879975457092965542603806917235403924230185514038638412396010

if I haven't typed incorrectly.

• yeap!! that's it!! – John Jun 22 at 14:38