1 /*-
2  * SPDX-License-Identifier: (BSD-3-Clause AND BSD-2-Clause)
34 /*-
39  * such a mathematical system to generate more random (yet non-repeating)
63  * $OpenBSD: ip6_id.c,v 1.3 2003/12/12 06:57:12 itojun Exp $
68  * seed = random (bits - 1) bit
70  * j = random so that gcd(j,n-1) == 1
71  * g = g0^j mod n will be a generator again.
74  * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
75  * with a = 7^(even random) mod m,
76  *      b = random with gcd(b,m) == 1
77  *      m = constant and a maximal period of m-1.
80  * id[n] = seed xor (g^X[n] mod n)
82  * Effectively the id is restricted to the lower (bits - 1) bits, thus
110 	const u_int32_t ru_n;	/* ru_n: prime, ru_n - 1: product of pfacts[] */
130 	2147483629,		/* RU_N-1 = 2^2*3^2*59652323 */
132 	1836660096,		/* RU_M = 2^7*3^15 - don't change */
141 	524269,			/* RU_N-1 = 2^2*3^2*14563 */
143 	279936,			/* RU_M = 2^7*3^7 - don't change */
153  * of 0 - (mod-1)
156 pmod(u_int32_t gen, u_int32_t expo, u_int32_t mod)  in pmod()  argument
166 			s = (s * t) % mod;  in pmod()
168 		t = (t * t) % mod;  in pmod()
187 	p->ru_x = arc4random() % p->ru_m;  in initid()
189 	/* (bits - 1) bits of random seed */  in initid()
190 	p->ru_seed = arc4random() & (~0U >> (32 - p->ru_bits + 1));  in initid()
191 	p->ru_seed2 = arc4random() & (~0U >> (32 - p->ru_bits + 1));  in initid()
194 	p->ru_b = (arc4random() & (~0U >> (32 - p->ru_bits))) | 1;  in initid()
195 	p->ru_a = pmod(p->ru_agen,  in initid()
196 	    (arc4random() & (~0U >> (32 - p->ru_bits))) & (~1U), p->ru_m);  in initid()
197 	while (p->ru_b % 3 == 0)  in initid()
198 		p->ru_b += 2;  in initid()
200 	j = arc4random() % p->ru_n;  in initid()
203 	 * Do a fast gcd(j, RU_N - 1), so we can find a j with  in initid()
204 	 * gcd(j, RU_N - 1) == 1, giving a new generator for  in initid()
205 	 * RU_GEN^j mod RU_N  in initid()
208 		for (i = 0; p->pfacts[i] > 0; i++)  in initid()
209 			if (j % p->pfacts[i] == 0)  in initid()
212 		if (p->pfacts[i] == 0)  in initid()
215 			j = (j + 1) % p->ru_n;  in initid()
218 	p->ru_g = pmod(p->ru_gen, j, p->ru_n);  in initid()
219 	p->ru_counter = 0;  in initid()
221 	p->ru_reseed = time_uptime + p->ru_out;  in initid()
222 	p->ru_msb = p->ru_msb ? 0 : (1U << (p->ru_bits - 1));  in initid()
230 	if (p->ru_counter >= p->ru_max || time_uptime > p->ru_reseed)  in randomid()
235 	if (p->ru_counter + n >= p->ru_max)  in randomid()
240 		p->ru_x = (u_int32_t)((u_int64_t)p->ru_a * p->ru_x + p->ru_b) % p->ru_m;  in randomid()
243 	p->ru_counter += i;  in randomid()
245 	return (p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 + p->ru_x, p->ru_n)) |  in randomid()
246 	    p->ru_msb;  in randomid()