Thread: Stronger random number generator?

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    795

    Stronger random number generator?

    I've been working on a stronger "random" generator, but it's still pretty predictable. Does anyone have any suggestions for less static things that I could add into the algorithm?

    Code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <sys/sysinfo.h>
    #include <sys/time.h>
    #include <stdint.h>
    
    
    #define RP_POOL_MAX 10
    
    
    #define rp_ins_pool(v, p) 					\
    						while ( *p != 0) 	\
    							p++; 			\
    						*p = v;		
    
    
    struct rand_pool {
    
    
    	int64_t rp_mem_sum;
    	int64_t rp_ram_sum;
    	int32_t rp_sys_time;
    	
    	int64_t rp_top_limit;
    	int64_t rp_btm_limit;
    	
    	int64_t *rp_pool;
    };
    
    
    static int64_t rp_parse_time() {
    
    
    	struct timeval *tv = malloc(sizeof *tv);
    	gettimeofday(tv, NULL);
    	
    	int32_t l_s = (int32_t)(tv->tv_sec / 1000);
    	
    	int32_t l_u = (int32_t)(tv->tv_usec * 1000);
    	
    	int64_t l_r = (l_s + l_u);
    
    
    	free(tv);
    	return (l_r ? l_r : l_u * l_s);
    }
    
    
    static int64_t rp_parse_mem() {
    	
    	struct sysinfo *sf = malloc(sizeof *sf); 
    	sysinfo(sf);
    	
    	int32_t l_s = sf->loads[0] + sf->loads[1] + sf->loads[2];
    	
    	int16_t l_d = (l_s | (sf->procs % 2 ? 0x6 : 0x2));
    	
    	int64_t l_q = (int64_t)(sf->uptime * sf->freeram) / l_d;
    
    
    	int64_t l_r = (sf->totalswap << (l_q / 1000));
    	
    	free(sf);
    	return (l_r ? l_r : l_s * l_d);
    }
    
    
    static int64_t rp_parse_ram() {
    
    
    	struct sysinfo *sf = malloc(sizeof *sf);
    	sysinfo(sf);
    	
    	int64_t l_r = (sf->totalram * sf->bufferram) >> 32;
    
    
    	int64_t l_c = (int64_t)(int32_t)(l_r * sf->freeram);
    
    
    	free(sf);
    	return (l_c ? l_c : l_r * l_r);
    }
    
    
    static struct rand_pool *rp_init_pool() {
    
    
    	struct rand_pool *rp;
    	rp = calloc(1, sizeof *rp);
    
    
    	rp->rp_pool = calloc(1, RP_POOL_MAX + 1);
    
    
    	rp->rp_sys_time = rp_parse_time();
    
    
    	rp->rp_ram_sum = rp_parse_ram();
    
    
    	rp->rp_mem_sum = rp_parse_mem();
    
    
    	rp_ins_pool(rp->rp_sys_time, rp->rp_pool);
    	rp_ins_pool(rp->rp_ram_sum, rp->rp_pool);
    	rp_ins_pool(rp->rp_mem_sum, rp->rp_pool);
    	
    	return rp;
    }
    
    
    static int64_t rp_synth_pool(struct rand_pool *rp) {
    	
    	int64_t ret; 
    	
    	int64_t l_m = (rp->rp_mem_sum < rp->rp_ram_sum ? 
    					rp->rp_ram_sum : rp->rp_mem_sum);
    					
    	int64_t l_t = (l_m > 1073741824 ? 
    					l_m / 1073741824 :
    					(int64_t)((float)l_m * 1.25)); 
    	
    	int64_t l_f = (l_t * (rp->rp_sys_time / 1000));
    	
    	int64_t l_mod_top = rp->rp_top_limit - rp->rp_btm_limit;	
    	
    	int64_t l_ret = ( (l_f + rp->rp_btm_limit) % l_mod_top);	
    
    
    	if ((0 > rp->rp_btm_limit) && (l_ret % 2 || l_ret % 3)) 
    		return 0-l_ret;
    	else 
    		return l_ret;
    }
    
    
    static int64_t rp_rand(int64_t top, int64_t btm) {
    
    
    	struct rand_pool *rp;
    	
    	rp = rp_init_pool();
    	
    	rp->rp_top_limit = top;
    	rp->rp_btm_limit = btm;
    	
    	int64_t rp_final;
    	rp_final = rp_synth_pool(rp);
    		   
    	free(rp);
    	
    	return rp_final;
    
    
    }
    
    
    int main() {
    
    
    	int64_t prnt;
    	int64_t top = 10000000;
    	int64_t btm = -10000000;
    	
    	for (;;) {
    		prnt = rp_rand(top, btm);
    		printf("Random between %ld and %ld: %ld\n", btm, top, prnt);
    		sleep(1);
    	}
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by memcpy
    I've been working on a stronger "random" generator, but it's still pretty predictable. Does anyone have any suggestions for less static things that I could add into the algorithm?
    Have you considered using an existing well regarded PRNG like Mersenne Twister or an existing cryptographically secure PRNG like Blum Blum Shub?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Or if your programming for windows, the ideal random number generator is CryptGenRandom.
    It's even FIPS201 compliant, not that you'd probably know what that means.

    Bottom line: Don't waste time writing your own.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    I'm writing it for fun, not to actually have as a real number generator, so my original question still stands. What other variables can I input to make it more random?

    (ot) If I wanted to use an existing generator, I use arc4random() on mac/linux.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    If it were me, rather than guessing what might be useful, I'd do some research into what others have done first.

    You'll probably find that a real good random number generator achieves better randomness with less code, and more efficiency. In other words, the measure of how good it is, is not how much crap you put in it.
    For all you know, what you have already may actually be worse randomness than the implementation of rand that comes with your compiler.

    Without some kind of uinit tests to check the various randomness properties of the generator, you won't know when you've achieved your goal.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Make Fortran great again
    Join Date
    Sep 2009
    Posts
    1,413

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    One of the reasons that it is probably poorer than an ordinary call to rand() is that this generator has no internal state, and rather than beeing seeded once based on the time, it relies on a constant changing source of time to produce it's aparent randomness.
    That's just not good enough. A real program could make calls to the generator at any time, including a large number in quick succession, so you cannot rely on the time changing at all between calls. Take away that sleep(1), and take away the printf statement which might also cause sufficient time to pass between calls. Have a loop that does nothing but fills an array with 1 million random values. Then after that loop, have a loop which outputs the 1 million values. You'll probably see how non-random it is after that.

    The reason that it's best to use something provided by the OS is that it has access to real random sources such as the time between keypresses, the data arriving at your network card, the temperature of your CPU, and so on. But once again, you can't just rely on these things as they require time to change. You need to include a classical kind of generator as well; one that does have internal state and can provide the randomness based on the number of calls made to it, for when enough time has not passed, and your other random sources fail you.

    Every source of randomness you use needs to be pretty good on its own. If any of them are rather poor then they don't add anything of sufficient value to your code.

    You should also know how many bits of randomness you are throwing away by taking a 64-bit value, and doing a calculation that truncates this down to a 32-bit float, before storing this back into a 64-bit value.

    You should be able to to prove that every single line of code in your generator adds value to the result. Any line of code that you can't prove adds value to the result should be eliminated. Division is slow. Does every division in your code make it more random? No, several of them make it less random.
    Don't use calloc. You don't need it to waste time turning whatever random crap might be in that buffer initially into something nice and non-random like all zeros. If you're going to allocate memory at all, use malloc instead and take advantage of that random crap that it might give you.

    I suggest you start over and rather than trying to include the kitchen-sink from the get-go, have a very strict policy on what you will include, including only what you've found really makes a big difference.
    Last edited by iMalc; 12-20-2011 at 04:58 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    Quote Originally Posted by iMalc View Post
    use malloc instead and take advantage of that random crap that it might give you
    I'm wondering if something like this would be a good alternative for the entire program. It would iterate through a wide range of memory, extract the non-zero bytes, and whenever the function is called, it would select eight from the list, put them through an algorithm, and return it. Would this be a) random enough, and b) too easy to then use to exploit the system.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need a random number generator thats not compleatly random
    By thedodgeruk in forum C++ Programming
    Replies: 1
    Last Post: 06-05-2011, 06:48 AM
  2. Random number generator
    By jbone0881 in forum C Programming
    Replies: 3
    Last Post: 03-14-2011, 10:20 PM
  3. Random number generator
    By rehan in forum C++ Programming
    Replies: 1
    Last Post: 02-25-2008, 02:14 AM
  4. Random number generator
    By Labmouse in forum C++ Programming
    Replies: 6
    Last Post: 09-01-2007, 02:23 PM
  5. random number generator
    By Verbenaca in forum C++ Programming
    Replies: 4
    Last Post: 06-06-2005, 08:05 AM