< 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/