I'm trying to make a PRG using the Rabin function. The code (in Java) I wrote to implement the function is:

poublic static int rabinFunction(int m, int publicKey) {
    return (int) Math.pow(m, 2) % publicKey;

A trivial usage (using the numbers from the wikipedia link) would be:

int m = 20;
int pq = 7 * 11;

// output will be 15
int output = rabinFunction(20, 77);

I'm using this one way function to create a pseudo random generator. Basically, I run the Rabin function and use the least significant bit from the function output as part of my pseudorandom value. I use the return value from the previous execution as the seed for the next execution and I repeat this process until I've generated enough bits to encrypt my message. The issue I'm having is that the Rabin function returns the same values after 4 iterations:

rabinFunction(20, 77); //==> 15
rabinFunction(15, 77); //==> 71
rabinFunction(71, 77); //==> 36
rabinFunction(36, 77); //==> 64
rabinFunction(64, 77); //==> 15! Back to where we started, etc

I'm assuming that using the output from a previous execution of the Rabin function as the seed for a new one isn't correct. Can someone explain why this is wrong? Thanks in advance.

  • $\begingroup$ Might not cause your immediate problem, but should use a BigInteger class instead of Math.Pow and double. $\endgroup$ – CodesInChaos Apr 12 '13 at 17:09
  • $\begingroup$ Why double? The Rabin function can only return an integer. $\endgroup$ – William Seemann Apr 12 '13 at 17:11
  • $\begingroup$ Your immediate problem is the unfortunate choice of the modulus. $\endgroup$ – CodesInChaos Apr 12 '13 at 17:12
  • 2
    $\begingroup$ Math.pow calculates as and returns double, which you then round to an int, and reduce modulo your modulus. With bigger numbers this will get you into poblems. Actually, when squaring integers, simply writing x * x is the easiest way. $\endgroup$ – Paŭlo Ebermann Apr 12 '13 at 17:52
  • $\begingroup$ You might be interested in knowing that a rather similar PRNG called Blum Blum Shub already existed. $\endgroup$ – Dan D. Aug 19 '13 at 22:05

The modulus 77 leads to a short period.

  • $\begingroup$ Ok, so how would I increase the period? $\endgroup$ – William Seemann Apr 12 '13 at 17:16
  • 3
    $\begingroup$ A better choice of modulus. The product of two large primes (say 512 bits each) should do the job. $\endgroup$ – CodesInChaos Apr 12 '13 at 17:17
  • $\begingroup$ Ok, last question, is it ok that the original seed is small or is that somehow related to p and q? In other words, would a larger seed value also make a difference. $\endgroup$ – William Seemann Apr 12 '13 at 17:18
  • $\begingroup$ @CodesInChaos: actually, $x^{16} = x$ does not hold in general; it doesn't for $x=2$ with $x^{16} = 9$. However, $x^{32} = x^{2}$ does hold, hence you'll always end up with a cycle at most 4. This happens because $p-1=6$ and $q-1=10$ are both divisors of $32-2$ $\endgroup$ – poncho Apr 12 '13 at 17:23
  • 1
    $\begingroup$ @CodesInChaos: actually, it's $x^{\lambda(n)+1} = x \ (\bmod\ n)$ $\endgroup$ – poncho Apr 12 '13 at 17:57

Your Answer

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

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