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 ...
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.