0
$\begingroup$

Let K_rsa be a RSA genertor with associated security parameter k >= 1024. Let game OW-CCA_Krsa be as follows:

enter image description here

How can I build a O(k^3)-time adversary A making at most 2 queries to Invert and achieving advantage = 1.

Here is the idea that I have: if we query Invert(ya^e) then multiply that with a^{-1}, then in the end we get x:

$$\text{Adversary A:}\\z \leftarrow ya^e\\C \leftarrow Invert(z)\\return (a^{-1} \cdot C )$$

(sorry, don't know how to left justify this)

So, we want a call to invert that would equal x. When we call Invert giving it ya^e:

$$\text{Invert}(ya^e)\\w=(ya^e)^d\ mod\ N\ \\ w=(x^e\ a^e)^d\ mod\ N\ \\ \ \ =x^{ed}\ a^{ed} = xa\\\\$$

then when we multiply that with the inverse of a, we just get x. Is this correct? Are we allowed to just multiply this by a inverse?

Thanks in advance!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.