Crack RSA by using user signatures

Question

Lets say I have a secret $s$ that is encrypted with a public key $(N,e)$. We know $e=35567$. However we don't know $N$.

We can ask the user to sign any message $m$ with his private key $(N,d)$ _ of course $d=e^{-1}\mod{\phi(N)}$ _

However the user is smart, if we tell him to sign $s$, he just won't do it.

How can I decrypt $s$ using this ?

My Attempts

What I tried to do is telling the user to sign $s\times2^e$ and then dividing the returned signed message by 2. However this fails because I did not reduce $s\times2^e$ modulo $N$ because I don't know $N$.

I tried getting $N$ by sending many message for the user to sign then compute some GCD of the messages but the calculations become so big that everything fails ...

some libraries accept larger values to encrypt and decrypt with RSA. — kelalaka, May 24 '22 at 20:46

score 1 · Answer 1 · answered May 23 '22 at 20:35

1

Why don't you know $N$? This is part of the public key. The attacker doesn't know the prime factors of $N$, but $N$ itself should be public.

You are asking for a chosen plaintext attack against RSA. This is well known (though only against textbook RSA - it won't work if the message is padded properly).

If you want the user to sign $s$, you can choose any random $x$ and form $sx^e \mod N$ then if you can trick the user into signing it you get $s^d x \mod N$. Your signature is $s^d$ and you can get it by dividing by your chosen value $x$.

I think this attack was originally due to Davida, if you want to look it up.

answered May 23 '22 at 20:35

Robin Balean

678

Without N, the attack sadly does not work, I send the user m and he does $m^d\mod{N}$ and that's it, no need for me to know $N$ – rudeus123 May 23 '22 at 21:27
rudeus123 The signature $m^d\mod N$ is not much use without $N$ because you also need $N$ to verify the signature. – Robin Balean May 24 '22 at 17:59
I know it is just how the problem is asked sadly :-( – rudeus123 May 24 '22 at 20:12

Crack RSA by using user signatures

1 Answers1