Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
Didn't you answer your own question with the edit? This function can never output zero or one. If not, please clarify your question. – user4549 Dec 18 '12 at 11:38

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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