I got a message: 427, this message will be signed with RSA key, but only the public part of the RSA key is available so KeyPub:(N=3901, e = 3). To my knowledge 427 would get signed with d, so the multiplicative inverse of 3 modulo 3901 = 2601.
My solution is (calculated by Wolframalpha):
$427^{2601}(mod \thinspace 3901) = 1614$
BUT
$1614^3 mod \thinspace3901 = 853$ So if am not misstaken there must be an error, as I was expecting 427
Goal: To find a, the signed version of 427, y such that: $$y^e (mod \thinspace3901) = 427 (mod \thinspace 3901), \text{for} \space e =3$$
To solve I got my "basic" calculator and a table of the multiplicative inverses in mod 3901 like. Factoring the public key is not possible by the task description.
| x | x^(-1) |
|---|---|
| 3 | 2601 |
| 114 | 1403 |
| 427 | 3161 |
Thanks in advance!
The mistake is that you computed $d\equiv 3^{-1}\mod N$, but it should be modulo $\phi(N)$ instead, where $\phi$ is the Euler's Totient Function.
Here, we have $N = 3901 = 47\cdot 83$, so $\phi(N) = 46\cdot 82 = 3772$ and $d = 2515$. Checking, we have $(427^3)^{2515}\equiv 427\mod 3901$.
This is also why RSA was secure - you have to factor $N$ to compute the private key $d$, and factoring was hard.