draft-ietf-tsvwg-tinymt32-01.txt		draft-ietf-tsvwg-tinymt32-02.txt
	TSVWG M. Saito		TSVWG M. Saito
	Internet-Draft M. Matsumoto		Internet-Draft M. Matsumoto
	Intended status: Standards Track Hiroshima University		Intended status: Standards Track Hiroshima University
	Expires: October 10, 2019 V. Roca (Ed.)		Expires: November 17, 2019 V. Roca (Ed.)
	E. Baccelli		E. Baccelli
	INRIA		INRIA
	April 8, 2019		May 16, 2019
	TinyMT32 Pseudo Random Number Generator (PRNG)		TinyMT32 Pseudo Random Number Generator (PRNG)
	draft-ietf-tsvwg-tinymt32-01		draft-ietf-tsvwg-tinymt32-02
	Abstract		Abstract
	This document describes the TinyMT32 Pseudo Random Number Generator		This document describes the TinyMT32 Pseudo Random Number Generator
	(PRNG) that produces 32-bit pseudo-random unsigned integers and aims		(PRNG) that produces 32-bit pseudo-random unsigned integers and aims
	at having a simple-to-use and deterministic solution. This PRNG is a		at having a simple-to-use and deterministic solution. This PRNG is a
	small-sized variant of Mersenne Twister (MT) PRNG, also designed by		small-sized variant of Mersenne Twister (MT) PRNG, also designed by
	M. Saito and M. Matsumoto. The main advantage of TinyMT32 over MT		M. Saito and M. Matsumoto. The main advantage of TinyMT32 over MT
	is the use of a small internal state, compatible with most target		is the use of a small internal state, compatible with most target
	platforms including embedded devices, while keeping a reasonably good		platforms including embedded devices, while keeping a reasonably good
	skipping to change at page 1, line 40 ¶		skipping to change at page 1, line 40 ¶
	Internet-Drafts are working documents of the Internet Engineering		Internet-Drafts are working documents of the Internet Engineering
	Task Force (IETF). Note that other groups may also distribute		Task Force (IETF). Note that other groups may also distribute
	working documents as Internet-Drafts. The list of current Internet-		working documents as Internet-Drafts. The list of current Internet-
	Drafts is at https://datatracker.ietf.org/drafts/current/.		Drafts is at https://datatracker.ietf.org/drafts/current/.
	Internet-Drafts are draft documents valid for a maximum of six months		Internet-Drafts are draft documents valid for a maximum of six months
	and may be updated, replaced, or obsoleted by other documents at any		and may be updated, replaced, or obsoleted by other documents at any
	time. It is inappropriate to use Internet-Drafts as reference		time. It is inappropriate to use Internet-Drafts as reference
	material or to cite them other than as "work in progress."		material or to cite them other than as "work in progress."
	This Internet-Draft will expire on October 10, 2019.		This Internet-Draft will expire on November 17, 2019.
	Copyright Notice		Copyright Notice
	Copyright (c) 2019 IETF Trust and the persons identified as the		Copyright (c) 2019 IETF Trust and the persons identified as the
	document authors. All rights reserved.		document authors. All rights reserved.
	This document is subject to BCP 78 and the IETF Trust's Legal		This document is subject to BCP 78 and the IETF Trust's Legal
	Provisions Relating to IETF Documents		Provisions Relating to IETF Documents
	(https://trustee.ietf.org/license-info) in effect on the date of		(https://trustee.ietf.org/license-info) in effect on the date of
	publication of this document. Please review these documents		publication of this document. Please review these documents
	skipping to change at page 2, line 48 ¶		skipping to change at page 2, line 48 ¶
	This specialisation aims at having a simple-to-use and deterministic		This specialisation aims at having a simple-to-use and deterministic
	PRNG, as explained below.		PRNG, as explained below.
	TinyMT is a new small-sized variant of Mersenne Twister (MT)		TinyMT is a new small-sized variant of Mersenne Twister (MT)
	introduced by Mutsuo Saito and Makoto Matsumoto in 2011. This		introduced by Mutsuo Saito and Makoto Matsumoto in 2011. This
	document focusses on the TinyMT32 variant (rather than TinyMT64) of		document focusses on the TinyMT32 variant (rather than TinyMT64) of
	the PRNG, which outputs 32-bit unsigned integers.		the PRNG, which outputs 32-bit unsigned integers.
	The purpose of TinyMT is not to replace Mersenne Twister: TinyMT has		The purpose of TinyMT is not to replace Mersenne Twister: TinyMT has
	a far shorter period than MT. The merit of TinyMT is in its small		a far shorter period (2^^127 - 1) than MT. The merit of TinyMT is in
	size of the internal state of 127 bits, far smaller than 19937 bits		its small size of the internal state of 127 bits, far smaller than
	of MT. According to statistical tests (BigCrush in TestU01		the 19937 bits of MT. According to statistical tests (BigCrush in
	<http://simul.iro.umontreal.ca/testu01/tu01.html> and AdaptiveCrush		TestU01 <http://simul.iro.umontreal.ca/testu01/tu01.html> and
	<http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ADAPTIVE/>) the		AdaptiveCrush <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/
	quality of the outputs of TinyMT seems pretty good, taking the small		ADAPTIVE/>) the quality of the outputs of TinyMT seems pretty good in
	size of the internal state into consideration. From this point of		terms of randomnes (in particular the uniformity of generated
	view, TinyMT32 represents a major improvement with respect to the		numbers), taking the small size of the internal state into
	Park-Miler Linear Congruential PRNG (e.g., as specified in		consideration (see <http://www.math.sci.hiroshima-u.ac.jp/~m-
	[RFC5170]).		mat/MT/TINYMT/index.html>). From this point of view, TinyMT32
			represents a major improvement with respect to the Park-Miler Linear
			Congruential PRNG (e.g., as specified in [RFC5170]) that suffers
			several known limitations. However, neither TinyMT nor MT are meant
			to be used for cryptographic applications.
	The TinyMT32 PRNG initialization depends, among other things, on a		The TinyMT32 PRNG initialization depends, among other things, on a
	parameter set -- namely (mat1, mat2, tmat) -- that needs to be well		parameter set -- namely (mat1, mat2, tmat) -- that needs to be well
	chosen (pre-calculated values are available in the official web		chosen (pre-calculated values are available in the official web
	site). In order to facilitate the use of this PRNG, and unlike the		site). In order to facilitate the use of this PRNG and make the
			sequence of pseudo-random numbers depend only on the seed value, this
			specification requires the use of a specific parameter set (see
			Section 3.1). This is a first difference with respect to the
	implementation version 1.1 (2015/04/24) by Mutsuo Saito and Makoto		implementation version 1.1 (2015/04/24) by Mutsuo Saito and Makoto
	Matsumoto, this specification requires the use of a specific		Matsumoto that leaves this parameter set unspecified. A second
	parameter set (see Section 3.1). The implementation version 1.1		difference is the removal of the tinymt32_init_by_array() alternative
	(2015/04/24) also proposes two initialisation functions that differ		initialization function, to only keep the simple initialisation
	on the approach to seed the PRNG. A second difference is the removal		through a seed value (see Section 3.2).
	of the tinymt32_init_by_array() function to keep only the simple
	initialisation through a single seed value (see Section 3.2).
	Finally, the determinism of this PRNG, for a given seed, has been		Finally, the determinism of this PRNG, for a given seed, has been
	carefully checked (see Section 3.3). Indeed, this determinism can be		carefully checked (see Section 3.3). It means that the same sequence
	a key requirement as it the case with [RLC-ID] that normatively		of pseudo-random numbers should be generated, no matter the target
	depends on this specification.		execution platform and compiler, for a given initial seed value.
			This determinism can be a key requirement as it the case with
			[RLC-ID] that normatively depends on this specification.
	2. Definitions		2. Definitions
	The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",		The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
	"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and		"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
	"OPTIONAL" in this document are to be interpreted as described in BCP		"OPTIONAL" in this document are to be interpreted as described in BCP
	14 [RFC2119] [RFC8174] when, and only when, they appear in all		14 [RFC2119] [RFC8174] when, and only when, they appear in all
	capitals, as shown here.		capitals, as shown here.
	3. TinyMT32 PRNG Specification		3. TinyMT32 PRNG Specification
	skipping to change at page 4, line 44 ¶		skipping to change at page 5, line 4 ¶
	/**		/**
	* tinymt32 internal state vector and parameters		* tinymt32 internal state vector and parameters
	*/		*/
	typedef struct {		typedef struct {
	uint32_t status[4];		uint32_t status[4];
	uint32_t mat1;		uint32_t mat1;
	uint32_t mat2;		uint32_t mat2;
	uint32_t tmat;		uint32_t tmat;
	} tinymt32_t;		} tinymt32_t;
			static void tinymt32_next_state (tinymt32_t* s);
	static void tinymt32_next_state (tinymt32_t * s);		static uint32_t tinymt32_temper (tinymt32_t* s);
	static uint32_t tinymt32_temper (tinymt32_t * s);
	/**		/**
	* Parameter set to use for this IETF specification. Don't change.		* Parameter set to use for this IETF specification. Don't change.
	* This parameter set is the first entry of the precalculated		* This parameter set is the first entry of the precalculated
	* parameter sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by		* parameter sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by
	* Kenji Rikitake, available at:		* Kenji Rikitake, available at:
	* https://github.com/jj1bdx/tinymtdc-longbatch/		* https://github.com/jj1bdx/tinymtdc-longbatch/
	* It is also the parameter set used:		* It is also the parameter set used:
	* Rikitake, K., "TinyMT Pseudo Random Number Generator for		* Rikitake, K., "TinyMT Pseudo Random Number Generator for
	* Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),		* Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
	* September, 2012.		* September, 2012.
	*/		*/
	const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);		const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);
	const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);		const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);
	const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);		const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);
	skipping to change at page 5, line 21 ¶		skipping to change at page 5, line 28 ¶
	const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);		const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);
	const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);		const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);
	const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);		const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);
	/**		/**
	* This function initializes the internal state array with a		* This function initializes the internal state array with a
	* 32-bit unsigned integer seed.		* 32-bit unsigned integer seed.
	* @param s pointer to tinymt internal state.		* @param s pointer to tinymt internal state.
	* @param seed a 32-bit unsigned integer used as a seed.		* @param seed a 32-bit unsigned integer used as a seed.
	*/		*/
	void tinymt32_init (tinymt32_t * s, uint32_t seed)		void tinymt32_init (tinymt32_t* s, uint32_t seed)
	{		{
	const uint32_t MIN_LOOP = 8;		const uint32_t MIN_LOOP = 8;
	const uint32_t PRE_LOOP = 8;		const uint32_t PRE_LOOP = 8;
	s->status[0] = seed;		s->status[0] = seed;
	s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;		s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
	s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;		s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
	s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;		s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
	for (int i = 1; i < MIN_LOOP; i++) {		for (int i = 1; i < MIN_LOOP; i++) {
	s->status[i & 3] ^= i + UINT32_C(1812433253)		s->status[i & 3] ^= i + UINT32_C(1812433253)
	* (s->status[(i - 1) & 3]		* (s->status[(i - 1) & 3]
	skipping to change at page 5, line 45 ¶		skipping to change at page 6, line 4 ¶
	* NB: the parameter set of this specification warrants		* NB: the parameter set of this specification warrants
	* that none of the possible 2^^32 seeds leads to an		* that none of the possible 2^^32 seeds leads to an
	* all-zero 127-bit internal state. Therefore, the		* all-zero 127-bit internal state. Therefore, the
	* period_certification() function of the original		* period_certification() function of the original
	* TinyMT32 source code has been safely removed. If		* TinyMT32 source code has been safely removed. If
	* another parameter set is used, this function will		* another parameter set is used, this function will
	* have to be re-introduced here.		* have to be re-introduced here.
	*/		*/
	for (int i = 0; i < PRE_LOOP; i++) {		for (int i = 0; i < PRE_LOOP; i++) {
	tinymt32_next_state(s);		tinymt32_next_state(s);
	}		}
	}		}
	/**		/**
	* This function outputs a 32-bit unsigned integer from		* This function outputs a 32-bit unsigned integer from
	* the internal state.		* the internal state.
	* @param s pointer to tinymt internal state.		* @param s pointer to tinymt internal state.
	* @return 32-bit unsigned integer r (0 <= r < 2^32).		* @return 32-bit unsigned integer r (0 <= r < 2^32).
	*/		*/
	uint32_t tinymt32_generate_uint32 (tinymt32_t * s)		uint32_t tinymt32_generate_uint32 (tinymt32_t* s)
	{		{
	tinymt32_next_state(s);		tinymt32_next_state(s);
	return tinymt32_temper(s);		return tinymt32_temper(s);
	}		}
	/**		/**
	* Internal tinymt32 constants and functions.		* Internal tinymt32 constants and functions.
	* Users should not call these functions directly.		* Users should not call these functions directly.
	*/		*/
	const uint32_t TINYMT32_SH0 = 1;		const uint32_t TINYMT32_SH0 = 1;
	const uint32_t TINYMT32_SH1 = 10;		const uint32_t TINYMT32_SH1 = 10;
	const uint32_t TINYMT32_SH8 = 8;		const uint32_t TINYMT32_SH8 = 8;
	const uint32_t TINYMT32_MASK = UINT32_C(0x7fffffff);		const uint32_t TINYMT32_MASK = UINT32_C(0x7fffffff);
	/**		/**
	* This function changes the internal state of tinymt32.		* This function changes the internal state of tinymt32.
	* @param s pointer to tinymt internal state.		* @param s pointer to tinymt internal state.
	*/		*/
	static void tinymt32_next_state (tinymt32_t * s)		static void tinymt32_next_state (tinymt32_t* s)
	{		{
	uint32_t x;		uint32_t x;
	uint32_t y;		uint32_t y;
	y = s->status[3];		y = s->status[3];
	x = (s->status[0] & TINYMT32_MASK)		x = (s->status[0] & TINYMT32_MASK)
	^ s->status[1]		^ s->status[1]
	^ s->status[2];		^ s->status[2];
	x ^= (x << TINYMT32_SH0);		x ^= (x << TINYMT32_SH0);
	y ^= (y >> TINYMT32_SH0) ^ x;		y ^= (y >> TINYMT32_SH0) ^ x;
	skipping to change at page 7, line 4 ¶		skipping to change at page 7, line 12 ¶
	* s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;		* s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;
	* The adopted code is equivalent to the original code		* The adopted code is equivalent to the original code
	* but does not depend on the representation of negative		* but does not depend on the representation of negative
	* integers by 2's complements. It is therefore more		* integers by 2's complements. It is therefore more
	* portable, but includes an if-branch which may slow		* portable, but includes an if-branch which may slow
	* down the generation speed.		* down the generation speed.
	*/		*/
	if (y & 1) {		if (y & 1) {
	s->status[1] ^= s->mat1;		s->status[1] ^= s->mat1;
	s->status[2] ^= s->mat2;		s->status[2] ^= s->mat2;
	}		}
	}		}
	/**		/**
	* This function outputs a 32-bit unsigned integer from		* This function outputs a 32-bit unsigned integer from
	* the internal state.		* the internal state.
	* @param s pointer to tinymt internal state.		* @param s pointer to tinymt internal state.
	* @return 32-bit unsigned pseudo-random number.		* @return 32-bit unsigned pseudo-random number.
	*/		*/
	static uint32_t tinymt32_temper (tinymt32_t * s)		static uint32_t tinymt32_temper (tinymt32_t* s)
	{		{
	uint32_t t0, t1;		uint32_t t0, t1;
	t0 = s->status[3];		t0 = s->status[3];
	t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);		t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);
	t0 ^= t1;		t0 ^= t1;
	t0 ^= -((int32_t)(t1 & 1)) & s->tmat;		t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
	return t0;		return t0;
	}		}
	<CODE ENDS>		<CODE ENDS>
	skipping to change at page 9, line 20 ¶		skipping to change at page 9, line 24 ¶
	specific security risks per se.		specific security risks per se.
	5. IANA Considerations		5. IANA Considerations
	This document does not require any IANA action.		This document does not require any IANA action.
	6. Acknowledgments		6. Acknowledgments
	The authors would like to thank Belkacem Teibi with whom we explored		The authors would like to thank Belkacem Teibi with whom we explored
	TinyMT32 specificities when looking to an alternative to the Park-		TinyMT32 specificities when looking to an alternative to the Park-
	Miler Linear Congruential PRNG. The authors would like to thank Greg		Miler Linear Congruential PRNG. The authors would like to thank
	Skinner, the three TSVWG chairs, Wesley Eddy, our shepherd, David		Stewart Bryant, Greg Skinner, the three TSVWG chairs, Wesley Eddy,
	Black and Gorry Fairhurst, as well as Spencer Dawkins and Mirja		our shepherd, David Black and Gorry Fairhurst, as well as Spencer
	Kuhlewind. Last but not least, the authors are really grateful to		Dawkins and Mirja Kuhlewind. Last but not least, the authors are
	the IESG members, in particular Benjamin Kaduk, Eric Rescorla, and		really grateful to the IESG members, in particular Benjamin Kaduk,
	Adam Roach for their highly valuable feedbacks that greatly		Eric Rescorla, and Adam Roach for their highly valuable feedbacks
	contributed to improve this specification.		that greatly contributed to improve this specification.
	7. References		7. References
	7.1. Normative References		7.1. Normative References
	[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate		[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
	Requirement Levels", BCP 14, RFC 2119,		Requirement Levels", BCP 14, RFC 2119,
	DOI 10.17487/RFC2119, March 1997,		DOI 10.17487/RFC2119, March 1997,
	<https://www.rfc-editor.org/info/rfc2119>.		<https://www.rfc-editor.org/info/rfc2119>.
End of changes. 18 change blocks.
	41 lines changed or deleted		45 lines changed or added
This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/