1
$\begingroup$

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

--------Task---------------

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?

$\endgroup$
  • 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$ – Gilles 'SO- stop being evil' Jun 22 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 Jun 22 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$ – Gilles 'SO- stop being evil' Jun 22 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 Jun 22 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$ – Krystian Jun 22 at 13:52
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ yeap!! that's it!! $\endgroup$ – John Jun 22 at 14:38

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.