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


$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?

  • 1
    $\begingroup$ 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). $\endgroup$ Commented Jun 22, 2020 at 12:51
  • $\begingroup$ 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 $\endgroup$
    – John
    Commented Jun 22, 2020 at 13:07
  • $\begingroup$ 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)? $\endgroup$ Commented Jun 22, 2020 at 13:29
  • $\begingroup$ 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. $\endgroup$
    – John
    Commented Jun 22, 2020 at 13:39
  • 4
    $\begingroup$ And what are the values of $m_1$, $m_2$ ? Maybe the task is to exploit the multiplicative property of textbook RSA? $\endgroup$
    – Kris
    Commented Jun 22, 2020 at 13:52

1 Answer 1


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


if I haven't typed incorrectly.

  • $\begingroup$ yeap!! that's it!! $\endgroup$
    – John
    Commented Jun 22, 2020 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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