Lets say I want to tweak/alter the textbook RSA encryption function to create a pseudorandom function by pre-processing the input.

Suppose I do something simple like add 2 to the input before encrypting it:

$$c = (m+2)^e \bmod N$$

How do I know if this is not a secure pseudorandom function? Does this give any information about N?

I am aware that no tweak can make it a pseudo-random function. I am just trying to understand which values this setting cannot output so as to build a distinguisher. Sorry if I wasn't clear earlier. My question originally meant to ask which ciphertexts cannot be the output of this setting in order to distinguish it from a purely random function. I know 1 thing - This setting will never output 0 & 1 as the input is bounded $$0<=m<2^n$$

  • $\begingroup$ Didn't you answer your own question with the edit? This function can never output zero or one. If not, please clarify your question. $\endgroup$
    – user4549
    Commented Dec 18, 2012 at 11:38

1 Answer 1


This is not a secure pseudorandom function. No tweak is going to make this a pseudorandom function. After all, it is a public-key operation, so anyone who knows your algorithm can compute $f(m)$ given $m$. Consequently, it cannot possibly be pseudorandom: there will always be a trivial distinguisher.

What are you actually trying to accomplish? Why do you think you want a tweak to RSA that makes it a pseudorandom function -- what problem are you trying to solve? I think you may need to step back from the specific mechanism you have in mind and think through what are the broader requirements of your particular application. Once you've done that, we may be in a better position to help you solve your problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.