4

I've done a lot of research on that TI-84 rand() function. It uses the L'Ecuyer's algorithm to generate pseudorandom numbers. I have an interesting case however.

If the rand() function is given the proper seed, it will always generate the same numbers. So, given the first random number that the rand() function generates, is it possible to find the seed of the function?

Let the variable X represent the unknown seed.

    X->rand
    rand->D
    Disp D

Output:

    0.114820491

Based off this information, is it possible to calculate the seed of the rand() function? Can you work backwards somehow from the TI-84's rand() algorithm?

Mattkx4
  • 199
  • 3
  • 16
  • [This](http://tibasicdev.wikidot.com/rand) claims "The factory default seed is 0." Which doesn't answer your question, but it does have some interesting information, particularly regarding the value "1". – JimD. May 23 '17 at 04:31
  • I understand that. @JimD. The program I typed was just an example for reference. In my situation, I'm trying to crack an encryption program. I'm given the first random number that is generated, but I don't know what the seed is. Is there a way to figure out what the seed of the rand() was, based off of the first random number it generates? Does my question make sense or should I rephrase it? – Mattkx4 May 23 '17 at 04:34
  • I'm not sure I know enough about the properties of the random number generator. If you do the thought experiment of running this algorithm backwards, I think you can get a lot of possible values for s1 and s2 that generate a specific output. But if it is the very first output, then s1 and s2 are derived from the seed n. I don't know that that will cut down the number of possibilities to exactly 1 though. So you may need more than 1. Note also that a displayed value may not show you enough to know the exact 32 bit float, which increases the number of possibilities there too. – JimD. May 23 '17 at 05:13
  • [This](https://stackoverflow.com/questions/32788122/ti-84-plus-random-number-generator-algorithm) is the algorithm I am referring to. – JimD. May 23 '17 at 05:19
  • 1
    I think there are only 2^32-1 effectively distinct seed values, so I exhaustively searched for your value and I found 4 seeds: 41817, 196206349, 392370881, and 588535413. And they all generate different sequences. So it looks like you can't get a unique seed from the first value, but that doesn't mean you won't be able to decrypt the message. – JimD. May 23 '17 at 06:55
  • @JimD. Wait, woah! 41817 was the seed!!!!! Could you elaborate on your solution in an answer to my question? So I can accept your answer and hopefully replicate your method for the future? – Mattkx4 May 23 '17 at 11:15
  • Can you confirm that the other seeds work too? If they do, I'll clean up the code and post it. – JimD. May 23 '17 at 13:18
  • @JimD. The other seeds did indeed produce the same number for the first random number. However, the seeds generated different numbers for all the numbers after the first, as expected. So for the sake of this encryption program, only the first seed successfully decrypted the text, but the other three seeds did satisfy the condition. – Mattkx4 May 23 '17 at 14:59
  • "The L'Ecuyer's algorithm". Well, he has some. Which one do you mean? – plasmacel May 23 '17 at 15:48
  • @plasmacel Take a look at the links posted by JimD. as well as the solution posted below. That is the algorithm. – Mattkx4 May 23 '17 at 16:14

2 Answers2

3

No, empirically it is not possible to calculate the seed based on just the first generated random number because it is not unique. The following code will do a brute force search for a seed given the first random number:

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <stdlib.h>

int64_t mod1  = 2147483563;
int64_t mod2  = 2147483399;
int64_t mult1 = 40014;
int64_t mult2 = 40692;
int64_t seed1,seed2;

void Seed(int64_t n){
  if(n<0) //Perform an abs
    n = -n;
  if(n==0){
    seed1 = 12345; //Gotta love these seed values!
    seed2 = 67890;
  } else {
    seed1 = (mult1*n)%mod1;
    seed2 = n%mod2;
  }
}

double Generate(){
  double result;
  seed1  = (seed1*mult1)%mod1;
  seed2  = (seed2*mult2)%mod2;
  result = (double)(seed1-seed2)/(double)mod1;
  if(result<0)
    result = result+1;
  return result;
}

int main(int argc, char **argv){
  double x = 0.114820491; // Mattkx4's value
  double r;
  int64_t n;
  int i;

  if (argc > 2) {
    printf("USAGE: %s <1st generated random number>\n", argv[0]);
    return 1;
  } else if (argc == 2) {
    x = atof(argv[1]);
    printf("[Looking for seed generating %.10f]\n", x);
  } else {
    printf("[Looking for seed generating default value of %.10f]\n", x);
  }

  for (n=0; n<= 2147483647; n++) {
    Seed(n);
    r = Generate();
    if (fabs(r-x) < 10e-10) {
      printf("HIT: seed is %ld; G()=%.10f, G()-x=%.12f\n", (long) n, r, r-x);
      for (i=0; i<5; i++) {
        printf("  G() = %.10f\n", Generate());
      }
    }
  }

  return 0;
}

In the case of the OPs first random number, it gives the following output:

$ time ./a.out
[Looking for seed generating default value of 0.1148204910]
HIT: seed is 41817; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.1928098124
  G() = 0.8785866698
  G() = 0.7541802051
  G() = 0.3236799652
  G() = 0.2698472063
HIT: seed is 196206349; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.7255189385
  G() = 0.3079613984
  G() = 0.8041985209
  G() = 0.0959226401
  G() = 0.7729820570
HIT: seed is 392370881; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.2582281409
  G() = 0.7373361269
  G() = 0.8542168367
  G() = 0.8681653150
  G() = 0.2761169842
HIT: seed is 588535413; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.7909372669
  G() = 0.1667108555
  G() = 0.9042350761
  G() = 0.6404079899
  G() = 0.7792519113
HIT: seed is 1869313916; G()=0.1148204919, G()-x=0.000000000876
  G() = 0.9421831845
  G() = 0.2660259263
  G() = 0.9001868100
  G() = 0.3563914254
  G() = 0.3884731955
HIT: seed is 2065478448; G()=0.1148204919, G()-x=0.000000000876
  G() = 0.4748923105
  G() = 0.6954006549
  G() = 0.9502050494
  G() = 0.1286341003
  G() = 0.8916080463

real    1m24.132s
user    1m24.179s
sys 0m0.000s

In answering this, I am standing on the shoulders of giants by using the code provided by @richard in an answer to this stackoverflow question. If there is a better way to provide attribution, please let me know or simply edit this answer.

JimD.
  • 2,323
  • 1
  • 13
  • 19
1

I found one solution, but I wouldn't consider it the most effective system. The following was the program I used to exhaustively search for a match to the rand number.

0→C

Repeat X=0.114820491
Disp C
C→rand
rand→X
C+1→C
End

Disp "Done!"

This program tests every seed for the rand function until it eventually finds the seed that produces the desired random number.

The problem with this system is that there is an insanely large number of possibilities. In this case, the program only had to run a little over 40,000 times, but in some cases this program would have be run millions and millions of times before finding a matching seed. However, this works if the seed is relatively small.

It's not the best solution, but it is a solution.

See @JimD.'s answer for a more precise method.

Mattkx4
  • 199
  • 3
  • 16