draft-ietf-tsvwg-tinymt32-06.txt | rfc8682.txt | |||
---|---|---|---|---|

TSVWG M. Saito | Internet Engineering Task Force (IETF) M. Saito | |||

Internet-Draft M. Matsumoto | Request for Comments: 8682 M. Matsumoto | |||

Intended status: Standards Track Hiroshima University | Category: Standards Track Hiroshima University | |||

Expires: December 19, 2019 V. Roca (Ed.) | ISSN: 2070-1721 V. Roca, Ed. | |||

E. Baccelli | E. Baccelli | |||

INRIA | INRIA | |||

June 17, 2019 | January 2020 | |||

TinyMT32 Pseudo Random Number Generator (PRNG) | TinyMT32 Pseudorandom Number Generator (PRNG) | |||

draft-ietf-tsvwg-tinymt32-06 | ||||

Abstract | Abstract | |||

This document describes the TinyMT32 Pseudo Random Number Generator | This document describes the TinyMT32 Pseudorandom Number Generator | |||

(PRNG) that produces 32-bit pseudo-random unsigned integers and aims | (PRNG), which produces 32-bit pseudorandom 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. The main | small-sized variant of the Mersenne Twister (MT) PRNG. The main | |||

advantage of TinyMT32 over MT is the use of a small internal state, | advantage of TinyMT32 over MT is the use of a small internal state, | |||

compatible with most target platforms that include embedded devices, | compatible with most target platforms that include embedded devices, | |||

while keeping a reasonably good randomness that represents a | while keeping reasonably good randomness that represents a | |||

sigificant improvement compared to the Park-Miller Linear | significant improvement compared to the Park-Miller Linear | |||

Congruential PRNG. However, neither the TinyMT nor MT PRNG are meant | Congruential PRNG. However, neither the TinyMT nor MT PRNG is meant | |||

to be used for cryptographic applications. | to be used for cryptographic applications. | |||

Status of This Memo | Status of This Memo | |||

This Internet-Draft is submitted in full conformance with the | This is an Internet Standards Track document. | |||

provisions of BCP 78 and BCP 79. | ||||

Internet-Drafts are working documents of the Internet Engineering | ||||

Task Force (IETF). Note that other groups may also distribute | ||||

working documents as Internet-Drafts. The list of current Internet- | ||||

Drafts is at https://datatracker.ietf.org/drafts/current/. | ||||

Internet-Drafts are draft documents valid for a maximum of six months | This document is a product of the Internet Engineering Task Force | |||

and may be updated, replaced, or obsoleted by other documents at any | (IETF). It represents the consensus of the IETF community. It has | |||

time. It is inappropriate to use Internet-Drafts as reference | received public review and has been approved for publication by the | |||

material or to cite them other than as "work in progress." | Internet Engineering Steering Group (IESG). Further information on | |||

Internet Standards is available in Section 2 of RFC 7841. | ||||

This Internet-Draft will expire on December 19, 2019. | Information about the current status of this document, any errata, | |||

and how to provide feedback on it may be obtained at | ||||

https://www.rfc-editor.org/info/rfc8682. | ||||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2019 IETF Trust and the persons identified as the | Copyright (c) 2020 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 | |||

carefully, as they describe your rights and restrictions with respect | carefully, as they describe your rights and restrictions with respect | |||

to this document. Code Components extracted from this document must | to this document. Code Components extracted from this document must | |||

include Simplified BSD License text as described in Section 4.e of | include Simplified BSD License text as described in Section 4.e of | |||

the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||

described in the Simplified BSD License. | described in the Simplified BSD License. | |||

Table of Contents | Table of Contents | |||

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 | 1. Introduction | |||

2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1.1. Requirements Language | |||

3. TinyMT32 PRNG Specification . . . . . . . . . . . . . . . . . 3 | 2. TinyMT32 PRNG Specification | |||

3.1. TinyMT32 Source Code . . . . . . . . . . . . . . . . . . 3 | 2.1. TinyMT32 Source Code | |||

3.2. TinyMT32 Usage . . . . . . . . . . . . . . . . . . . . . 7 | 2.2. TinyMT32 Usage | |||

3.3. Specific Implementation Validation and Deterministic | 2.3. Specific Implementation Validation and Deterministic | |||

Behavior . . . . . . . . . . . . . . . . . . . . . . . . 8 | Behavior | |||

4. Security Considerations . . . . . . . . . . . . . . . . . . . 9 | 3. Security Considerations | |||

5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 | 4. IANA Considerations | |||

6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9 | 5. References | |||

7. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 | 5.1. Normative References | |||

7.1. Normative References . . . . . . . . . . . . . . . . . . 10 | 5.2. Informative References | |||

7.2. Informative References . . . . . . . . . . . . . . . . . 10 | Acknowledgments | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 | Authors' Addresses | |||

1. Introduction | 1. Introduction | |||

This document specifies the TinyMT32 PRNG, as a specialization of the | This document specifies the TinyMT32 PRNG as a specialization of the | |||

reference implementation version 1.1 (2015/04/24) by Mutsuo Saito and | reference implementation version 1.1 (2015/04/24) by Mutsuo Saito and | |||

Makoto Matsumoto, from Hiroshima University, that can be found at | Makoto Matsumoto from Hiroshima University, which can be found at | |||

[TinyMT-web] (TinyMT web site) and [TinyMT-dev] (Github site). This | [TinyMT-web] (the TinyMT website) and [TinyMT-dev] (the GitHub site). | |||

specialisation aims at having a simple-to-use and deterministic PRNG, | This specialization aims at having a simple-to-use and deterministic | |||

as explained below. However, the TinyMT32 PRNG is not meant to be | PRNG, as explained below. However, the TinyMT32 PRNG is not meant to | |||

used for cryptographic applications. | be used for cryptographic applications. | |||

TinyMT is a new small-sized variant introduced in 2011 of the | TinyMT is a new, small-sized variant of the Mersenne Twister (MT) | |||

Mersenne Twister (MT) PRNG [MT98]. This document focusses on the | PRNG introduced in 2011 [MT98]. This document focuses on the | |||

TinyMT32 variant (rather than TinyMT64) of the TinyMT PRNG, which | TinyMT32 variant (rather than TinyMT64) of the TinyMT PRNG, which | |||

outputs 32-bit unsigned integers. | 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 the Mersenne Twister: TinyMT | |||

a far shorter period (2^^127 - 1) than MT. The merit of TinyMT is in | has a far shorter period (2^(127) - 1) than MT. The merit of TinyMT | |||

the small size of the internal state of 127 bits, far smaller than | is in the small size of the 127-bit internal state, far smaller than | |||

the 19937 bits of MT. The outputs of TinyMT satisfy several | the 19937 bits of MT. The outputs of TinyMT satisfy several | |||

statistical tests for non-cryptographic randomness, including | statistical tests for non-cryptographic randomness, including | |||

BigCrush in TestU01 [TestU01] and AdaptiveCrush [AdaptiveCrush], | BigCrush in TestU01 [TestU01] and AdaptiveCrush [AdaptiveCrush], | |||

leaving it well-placed for non-cryptographic usage, especially given | leaving it well placed for non-cryptographic usage, especially given | |||

the small size of its internal state (see [TinyMT-web]). From this | the small size of its internal state (see [TinyMT-web]). From this | |||

point of view, TinyMT32 represents a major improvement with respect | point of view, TinyMT32 represents a major improvement with respect | |||

to the Park-Miller Linear Congruential PRNG (e.g., as specified in | to the Park-Miller Linear Congruential PRNG (e.g., as specified in | |||

[RFC5170]) that suffers several known limitations (see for instance | [RFC5170]), which suffers from several known limitations (see, for | |||

[PTVF92], section 7.1, p. 279, and [RLC-ID], Appendix B). | instance, [PTVF92], Section 7.1, p. 279 and [RFC8681], Appendix B). | |||

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). In order to facilitate the | parameter set, namely (mat1, mat2, tmat). In order to facilitate the | |||

use of this PRNG and make the sequence of pseudo-random numbers | use of this PRNG and to make the sequence of pseudorandom numbers | |||

depend only on the seed value, this specification requires the use of | depend only on the seed value, this specification requires the use of | |||

a specific parameter set (see Section 3.1). This is a major | a specific parameter set (see Section 2.1). This is a major | |||

difference with respect to the implementation version 1.1 | difference with respect to the implementation version 1.1 | |||

(2015/04/24) that leaves this parameter set unspecified. | (2015/04/24), which leaves this parameter set unspecified. | |||

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). It means that the same sequence | carefully checked (see Section 2.3). This means that the same | |||

of pseudo-random numbers should be generated, no matter the target | sequence of pseudorandom numbers should be generated, no matter the | |||

execution platform and compiler, for a given initial seed value. | target execution platform and compiler, for a given initial seed | |||

This determinism can be a key requirement as it the case with | value. This determinism can be a key requirement, as is the case | |||

[RLC-ID] that normatively depends on this specification. | with [RFC8681], which normatively depends on this specification. | |||

2. Definitions | 1.1. Requirements Language | |||

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

14 [RFC2119] [RFC8174] when, and only when, they appear in all | BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all | |||

capitals, as shown here. | capitals, as shown here. | |||

3. TinyMT32 PRNG Specification | 2. TinyMT32 PRNG Specification | |||

3.1. TinyMT32 Source Code | 2.1. TinyMT32 Source Code | |||

The TinyMT32 PRNG requires to be initialized with a parameter set | The TinyMT32 PRNG must be initialized with a parameter set that needs | |||

that needs to be well chosen. In this specification, for the sake of | to be well chosen. In this specification, for the sake of | |||

simplicity, the following parameter set MUST be used: | simplicity, the following parameter set MUST be used: | |||

o mat1 = 0x8f7011ee = 2406486510 | * mat1 = 0x8f7011ee = 2406486510 | |||

o mat2 = 0xfc78ff1f = 4235788063 | ||||

o tmat = 0x3793fdff = 932445695 | * mat2 = 0xfc78ff1f = 4235788063 | |||

* tmat = 0x3793fdff = 932445695 | ||||

This parameter set is the first entry of the precalculated parameter | This parameter set is the first entry of the precalculated parameter | |||

sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by Kenji Rikitake, | sets in tinymt32dc/tinymt32dc.0.1048576.txt by Kenji Rikitake, | |||

and available at [TinyMT-params]. This is also the parameter set | available at [TinyMT-params]. This is also the parameter set used in | |||

used in [KR12]. | [KR12]. | |||

The TinyMT32 PRNG reference implementation is reproduced in Figure 1. | The TinyMT32 PRNG reference implementation is reproduced in Figure 1. | |||

This is a C language implementation, written for C99 [C99]. This | This is a C language implementation written for C99 [C99]. This | |||

reference implementation differs from the original source code as | reference implementation differs from the original source code as | |||

follows: | follows: | |||

o the original copyright and license have been removed by the | * The original authors, who are coauthors of this document, have | |||

original authors who are now authors of this document, in | granted IETF the rights to publish this version with a license and | |||

accordance with BCP 78 and the IETF Trust's Legal Provisions | copyright that are in accordance with BCP 78 and the IETF Trust's | |||

Relating to IETF Documents (http://trustee.ietf.org/license-info); | Legal Provisions Relating to IETF Documents | |||

o the source code initially spread over the tinymt32.h and | (http://trustee.ietf.org/license-info). | |||

tinymt32.c files has been merged; | ||||

o the unused parts of the original source code have been removed. | * The source code initially spread over the tinymt32.h and | |||

tinymt32.c files has been merged. | ||||

* The unused parts of the original source code have been removed. | ||||

This is the case of the tinymt32_init_by_array() alternative | This is the case of the tinymt32_init_by_array() alternative | |||

initialisation function. This is also the case of the | initialization function. This is also the case of the | |||

period_certification() function after having checked it is not | period_certification() function after having checked it is not | |||

required with the chosen parameter set; | required with the chosen parameter set. | |||

o the unused constants TINYMT32_MEXP and TINYMT32_MUL have been | ||||

removed; | * The unused constants TINYMT32_MEXP and TINYMT32_MUL have been | |||

o the appropriate parameter set has been added to the initialization | removed. | |||

function; | ||||

o the function order has been changed; | * The appropriate parameter set has been added to the initialization | |||

o certain internal variables have been renamed for compactness | function. | |||

purposes; | ||||

o the const qualifier has been added to the constant definitions; | * The function order has been changed. | |||

o the code that was dependant on the representation of negative | ||||

* Certain internal variables have been renamed for compactness | ||||

purposes. | ||||

* The const qualifier has been added to the constant definitions. | ||||

* The code that was dependent on the representation of negative | ||||

integers by 2's complements has been replaced by a more portable | integers by 2's complements has been replaced by a more portable | |||

version; | version. | |||

<CODE BEGINS> | <CODE BEGINS> | |||

/** | /** | |||

* Tiny Mersenne Twister only 127 bit internal state. | * Tiny Mersenne Twister: only 127-bit internal state. | |||

* Derived from the reference implementation version 1.1 (2015/04/24) | * Derived from the reference implementation version 1.1 (2015/04/24) | |||

* by Mutsuo Saito (Hiroshima University) and Makoto Matsumoto | * by Mutsuo Saito (Hiroshima University) and Makoto Matsumoto | |||

* (Hiroshima University). | * (Hiroshima University). | |||

*/ | */ | |||

#include <stdint.h> | #include <stdint.h> | |||

/** | /** | |||

* tinymt32 internal state vector and parameters | * tinymt32 internal state vector and parameters | |||

*/ | */ | |||

typedef struct { | typedef struct { | |||

skipping to change at page 5, line 9 ¶ | skipping to change at line 203 ¶ | |||

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 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 in: | |||

* 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", Proceedings of the 11th ACM SIGPLAN Erlang Workshop, | |||

* 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); | |||

/** | /** | |||

* 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. | |||

skipping to change at page 5, line 41 ¶ | skipping to change at line 235 ¶ | |||

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

^ (s->status[(i - 1) & 3] >> 30)); | ^ (s->status[(i - 1) & 3] >> 30)); | |||

} | } | |||

/* | /* | |||

* 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 reintroduced 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) | |||

{ | { | |||

skipping to change at page 7, line 5 ¶ | skipping to change at line 295 ¶ | |||

s->status[1] = s->status[2]; | s->status[1] = s->status[2]; | |||

s->status[2] = x ^ (y << TINYMT32_SH1); | s->status[2] = x ^ (y << TINYMT32_SH1); | |||

s->status[3] = y; | s->status[3] = y; | |||

/* | /* | |||

* The if (y & 1) {...} block below replaces: | * The if (y & 1) {...} block below replaces: | |||

* s->status[1] ^= -((int32_t)(y & 1)) & s->mat1; | * s->status[1] ^= -((int32_t)(y & 1)) & s->mat1; | |||

* 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 pseudorandom 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; | |||

/* | /* | |||

* The if (t1 & 1) {...} block below replaces: | * The if (t1 & 1) {...} block below replaces: | |||

* t0 ^= -((int32_t)(t1 & 1)) & s->tmat; | * t0 ^= -((int32_t)(t1 & 1)) & s->tmat; | |||

* 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 (t1 & 1) { | if (t1 & 1) { | |||

t0 ^= s->tmat; | t0 ^= s->tmat; | |||

} | } | |||

return t0; | return t0; | |||

} | } | |||

<CODE ENDS> | <CODE ENDS> | |||

Figure 1: TinyMT32 Reference Implementation | Figure 1: TinyMT32 Reference Implementation | |||

3.2. TinyMT32 Usage | 2.2. TinyMT32 Usage | |||

This PRNG MUST first be initialized with the following function: | This PRNG MUST first be initialized with the following function: | |||

void tinymt32_init (tinymt32_t* s, uint32_t seed); | void tinymt32_init (tinymt32_t* s, uint32_t seed); | |||

It takes as input a 32-bit unsigned integer used as a seed (note that | It takes as input a 32-bit unsigned integer used as a seed (note that | |||

value 0 is permitted by TinyMT32). This function also takes as input | value 0 is permitted by TinyMT32). This function also takes as input | |||

a pointer to an instance of a tinymt32_t structure that needs to be | a pointer to an instance of a tinymt32_t structure that needs to be | |||

allocated by the caller but left uninitialized. This structure will | allocated by the caller but is left uninitialized. This structure | |||

then be updated by the various TinyMT32 functions in order to keep | will then be updated by the various TinyMT32 functions in order to | |||

the internal state of the PRNG. The use of this structure admits | keep the internal state of the PRNG. The use of this structure | |||

several instances of this PRNG to be used in parallel, each of them | admits several instances of this PRNG to be used in parallel, each of | |||

having its own instance of the structure. | them having its own instance of the structure. | |||

Then, each time a new 32-bit pseudo-random unsigned integer between 0 | Then, each time a new 32-bit pseudorandom unsigned integer between 0 | |||

and 2^32 - 1 inclusive is needed, the following function is used: | and 2^(32) - 1 inclusive is needed, the following function is used: | |||

uint32_t tinymt32_generate_uint32 (tinymt32_t * s); | uint32_t tinymt32_generate_uint32 (tinymt32_t * s); | |||

Of course, the tinymt32_t structure must be left unchanged by the | Of course, the tinymt32_t structure must be left unchanged by the | |||

caller between successive calls to this function. | caller between successive calls to this function. | |||

3.3. Specific Implementation Validation and Deterministic Behavior | 2.3. Specific Implementation Validation and Deterministic Behavior | |||

PRNG determinism, for a given seed, can be a requirement (e.g., with | For a given seed, PRNG determinism can be a requirement (e.g., with | |||

[RLC-ID]). Consequently, any implementation of the TinyMT32 PRNG in | [RFC8681]). Consequently, any implementation of the TinyMT32 PRNG in | |||

line with this specification MUST have the same output as that | line with this specification MUST have the same output as that | |||

provided by the reference implementation of Figure 1. In order to | provided by the reference implementation of Figure 1. In order to | |||

increase the compliancy confidence, this document proposes the | increase the compliancy confidence, this document proposes the | |||

following criteria. Using a seed value of 1, the first 50 values | following criteria. Using a seed value of 1, the first 50 values | |||

returned by tinymt32_generate_uint32(s) as 32-bit unsigned integers | returned by tinymt32_generate_uint32(s) as 32-bit unsigned integers | |||

are equal to values provided in Figure 2, to be read line by line. | are equal to the values provided in Figure 2, which are to be read | |||

Note that these values come from the tinymt/check32.out.txt file | line by line. Note that these values come from the tinymt/ | |||

provided by the PRNG authors to validate implementations of TinyMT32, | check32.out.txt file provided by the PRNG authors to validate | |||

as part of the MersenneTwister-Lab/TinyMT Github repository. | implementations of TinyMT32 as part of the MersenneTwister-Lab/TinyMT | |||

GitHub repository. | ||||

2545341989 981918433 3715302833 2387538352 3591001365 | 2545341989 981918433 3715302833 2387538352 3591001365 | |||

3820442102 2114400566 2196103051 2783359912 764534509 | 3820442102 2114400566 2196103051 2783359912 764534509 | |||

643179475 1822416315 881558334 4207026366 3690273640 | 643179475 1822416315 881558334 4207026366 3690273640 | |||

3240535687 2921447122 3984931427 4092394160 44209675 | 3240535687 2921447122 3984931427 4092394160 44209675 | |||

2188315343 2908663843 1834519336 3774670961 3019990707 | 2188315343 2908663843 1834519336 3774670961 3019990707 | |||

4065554902 1239765502 4035716197 3412127188 552822483 | 4065554902 1239765502 4035716197 3412127188 552822483 | |||

161364450 353727785 140085994 149132008 2547770827 | 161364450 353727785 140085994 149132008 2547770827 | |||

4064042525 4078297538 2057335507 622384752 2041665899 | 4064042525 4078297538 2057335507 622384752 2041665899 | |||

2193913817 1080849512 33160901 662956935 642999063 | 2193913817 1080849512 33160901 662956935 642999063 | |||

3384709977 1723175122 3866752252 521822317 2292524454 | 3384709977 1723175122 3866752252 521822317 2292524454 | |||

Figure 2: First 50 decimal values (to be read per line) returned by | Figure 2: First 50 decimal values (to be read per line) returned by | |||

tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a seed | tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a seed | |||

value of 1. | value of 1 | |||

In particular, the deterministic behavior of the Figure 1 source code | In particular, the deterministic behavior of the Figure 1 source code | |||

has been checked across several platforms: high-end laptops running | has been checked across several platforms: high-end laptops running | |||

64-bits Mac OSX and Linux/Ubuntu; a board featuring a 32-bits ARM | 64-bit Mac OS X and Linux/Ubuntu; a board featuring a 32-bit ARM | |||

Cortex-A15 and running 32-bit Linux/Ubuntu; several embedded cards | Cortex-A15 and running 32-bit Linux/Ubuntu; several embedded cards | |||

featuring either an ARM Cortex-M0+, a Cortex-M3 or a Cortex-M4 32-bit | featuring either an ARM Cortex-M0+, a Cortex-M3, or a Cortex-M4 | |||

microcontroller, all of them running RIOT [Baccelli18]; two low-end | 32-bit microcontroller, all of them running RIOT [Baccelli18]; two | |||

embedded cards featuring either a 16-bit microcontroller (TI MSP430) | low-end embedded cards featuring either a 16-bit microcontroller (TI | |||

or a 8-bit microcontroller (Arduino ATMEGA2560), both of them running | MSP430) or an 8-bit microcontroller (Arduino ATMEGA2560), both of | |||

RIOT. | them running RIOT. | |||

This specification only outputs 32-bit unsigned pseudo-random numbers | This specification only outputs 32-bit unsigned pseudorandom numbers | |||

and does not try to map this output to a smaller integer range (e.g., | and does not try to map this output to a smaller integer range (e.g., | |||

between 10 and 49 inclusive). If a specific use-case needs such a | between 10 and 49 inclusive). If a specific use case needs such a | |||

mapping, it will have to provide its own function. In that case, if | mapping, it will have to provide its own function. In that case, if | |||

PRNG determinism is also required, the use of floating point (single | PRNG determinism is also required, the use of a floating point | |||

or double precision) to perform this mapping should probably be | (single or double precision) to perform this mapping should probably | |||

avoided, these calculations leading potentially to different rounding | be avoided, as these calculations may lead to different rounding | |||

errors across different target platforms. Great care should also be | errors across different target platforms. Great care should also be | |||

put on not introducing biases in the randomness of the mapped output | taken to not introduce biases in the randomness of the mapped output | |||

(it may be the case with some mapping algorithms) incompatible with | (which may be the case with some mapping algorithms) incompatible | |||

the use-case requirements. The details of how to perform such a | with the use-case requirements. The details of how to perform such a | |||

mapping are out-of-scope of this document. | mapping are out of scope of this document. | |||

4. Security Considerations | 3. Security Considerations | |||

The authors do not believe the present specification generates | The authors do not believe the present specification generates | |||

specific security risks per se. However, neither the TinyMT nor MT | specific security risks per se. However, the TinyMT and MT PRNG must | |||

PRNG are meant to be used for cryptographic applications. | not be used for cryptographic applications. | |||

5. IANA Considerations | ||||

This document does not require any IANA action. | 4. IANA Considerations | |||

6. Acknowledgments | This document has no IANA actions. | |||

The authors would like to thank Belkacem Teibi with whom we explored | 5. References | |||

TinyMT32 specificities when looking to an alternative to the Park- | ||||

Miller Linear Congruential PRNG. The authors would like to thank | ||||

Carl Wallace, Stewart Bryant, Greg Skinner, Mike Heard, the three | ||||

TSVWG chairs, Wesley Eddy, our shepherd, David Black and Gorry | ||||

Fairhurst, as well as Spencer Dawkins and Mirja Kuhlewind. Last but | ||||

not least, the authors are really grateful to the IESG members, in | ||||

particular Benjamin Kaduk, Eric Rescorla, Adam Roach, Roman Danyliw, | ||||

Barry Leiba, Martin Vigoureux, Eric Vyncke for their highly valuable | ||||

feedbacks that greatly contributed to improve this specification. | ||||

7. References | 5.1. Normative References | |||

7.1. Normative References | ||||

[C99] "Programming languages - C: C99, correction 3:2007", | [C99] International Organization for Standardization, | |||

International Organization for Standardization, ISO/IEC | "Programming languages - C: C99, correction 3:2007", ISO/ | |||

9899:1999/Cor 3:2007, November 2007. | IEC 9899:1999/Cor 3:2007, November 2007. | |||

[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>. | |||

[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | |||

2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | |||

May 2017, <https://www.rfc-editor.org/info/rfc8174>. | May 2017, <https://www.rfc-editor.org/info/rfc8174>. | |||

7.2. Informative References | 5.2. Informative References | |||

[AdaptiveCrush] | [AdaptiveCrush] | |||

Haramoto, H., "Automation of statistical tests on | Haramoto, H., "Automation of Statistical Tests on | |||

randomness to obtain clearer conclusion", Monte Carlo and | Randomness to Obtain Clearer Conclusion", Monte Carlo and | |||

Quasi-Monte Carlo Methods 2008, | Quasi-Monte Carlo Methods 2008, | |||

DOI:10.1007/978-3-642-04107-5_26, November 2009, | DOI 10.1007/978-3-642-04107-5_26, November 2009, | |||

<http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ | <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ | |||

ADAPTIVE/>. | ADAPTIVE>. | |||

[Baccelli18] | [Baccelli18] | |||

Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P., | Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P., | |||

Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and | Lenders, M. S., Petersen, H., Schleiser, K., Schmidt, T. | |||

M. Wahlisch, "RIOT: An Open Source Operating System for | C., and M. Wahlisch, "RIOT: An Open Source Operating | |||

Low-End Embedded Devices in the IoT", IEEE Internet of | System for Low-End Embedded Devices in the IoT", IEEE | |||

Things Journal (Volume 5, Issue 6), DOI: | Internet of Things Journal, Volume 5, Issue 6, | |||

10.1109/JIOT.2018.2815038, December 2018. | DOI 10.1109/JIOT.2018.2815038, December 2018, | |||

<https://doi.org/10.1109/JIOT.2018.2815038>. | ||||

[KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for | [KR12] Rikitake, K., "TinyMT pseudo random number generator for | |||

Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), | Erlang", Proceedings of the 11th ACM SIGPLAN Erlang | |||

September 14, 2012, Copenhagen, Denmark, DOI: | Workshop, pp. 67-72, DOI 10.1145/2364489.2364504, | |||

http://dx.doi.org/10.1145/2364489.2364504, September 2012. | September 2012, <https://doi.org/10.1145/2364489.2364504>. | |||

[MT98] Matsumoto, M. and T. Nishimura, "Mersenne Twister: A | [MT98] Matsumoto, M. and T. Nishimura, "Mersenne twister: A | |||

623-dimensionally equidistributed uniform pseudorandom | 623-dimensionally equidistributed uniform pseudo-random | |||

number generator", ACM Transactions on Modeling and | number generator", ACM Transactions on Modeling and | |||

Computer Simulation (TOMACS), Volume 8 Issue 1, Jan. 1998, | Computer Simulation (TOMACS), Volume 8, Issue 1, pp. 3-30, | |||

pp.3-30, January 1998, DOI:10.1145/272991.272995, January | DOI 10.1145/272991.272995, January 1998, | |||

1998. | <https://doi.org/10.1145/272991.272995>. | |||

[PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, | [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, | |||

"Numerical Recipies in C; Second Edition", Cambridge | "Numerical recipes in C (2nd ed.): the art of scientific | |||

University Press, ISBN: 0-521-43108-5, 1992. | computing", Cambridge University Press, | |||

ISBN 0-521-43108-5, 1992. | ||||

[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | |||

Check (LDPC) Staircase and Triangle Forward Error | Check (LDPC) Staircase and Triangle Forward Error | |||

Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, | Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, | |||

June 2008, <https://www.rfc-editor.org/info/rfc5170>. | June 2008, <https://www.rfc-editor.org/info/rfc5170>. | |||

[RLC-ID] Roca, V. and B. Teibi, "Sliding Window Random Linear Code | [RFC8681] Roca, V. and B. Teibi, "Sliding Window Random Linear Code | |||

(RLC) Forward Erasure Correction (FEC) Scheme for | (RLC) Forward Erasure Correction (FEC) Schemes for | |||

FECFRAME", Work in Progress, Transport Area Working Group | FECFRAME", RFC 8681, DOI 10.17487/RFC8681, January 2020, | |||

(TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in | <https://www.rfc-editor.org/info/rfc8681>. | |||

Progress), February 2019, <https://tools.ietf.org/html/ | ||||

draft-ietf-tsvwg-rlc-fec-scheme>. | ||||

[TestU01] L'Ecuyer, P. and R. Simard, "TestU01: A C Library for | [TestU01] L'Ecuyer, P. and R. Simard, "TestU01: A C library for | |||

Empirical Testing of Random Number Generators", ACM | empirical testing of random number generators", ACM | |||

Transactions on Mathematical Software, Vol. 33, article | Transactions on Mathematical Software (TOMS), Volume 33, | |||

22, 2007, 2007, | Issue 4, Article 22, DOI 10.1145/1268776.1268777, August | |||

<http://simul.iro.umontreal.ca/testu01/tu01.html>. | 2007, <http://simul.iro.umontreal.ca/testu01/tu01.html>. | |||

[TinyMT-dev] | [TinyMT-dev] | |||

Saito, M. and M. Matsumoto, "Tiny Mersenne Twister | "Tiny Mersenne Twister (TinyMT)", commit 9d7ca3c, March | |||

(TinyMT) github site", | 2018, <https://github.com/MersenneTwister-Lab/TinyMT>. | |||

<https://github.com/MersenneTwister-Lab/TinyMT>. | ||||

[TinyMT-params] | [TinyMT-params] | |||

Rikitake, K., "TinyMT pre-calculated parameter list github | "TinyMT pre-calculated parameter list", commit 30079eb, | |||

site", <https://github.com/jj1bdx/tinymtdc-longbatch/>. | March 2013, | |||

<https://github.com/jj1bdx/tinymtdc-longbatch>. | ||||

[TinyMT-web] | [TinyMT-web] | |||

Saito, M. and M. Matsumoto, "Tiny Mersenne Twister | Saito, M. and M. Matsumoto, "Tiny Mersenne Twister | |||

(TinyMT) web site", | (TinyMT)", | |||

<http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/>. | <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/>. | |||

Acknowledgments | ||||

The authors would like to thank Belkacem Teibi, with whom we explored | ||||

TinyMT32 specificities when looking to an alternative to the Park- | ||||

Miller Linear Congruential PRNG. The authors would also like to | ||||

thank Carl Wallace; Stewart Bryant; Greg Skinner; Mike Heard; the | ||||

three TSVWG chairs, Wesley Eddy (our shepherd), David Black, and | ||||

Gorry Fairhurst; as well as Spencer Dawkins and Mirja Kuehlewind. | ||||

Last but not least, the authors are really grateful to the IESG | ||||

members, in particular Benjamin Kaduk, Eric Rescorla, Adam Roach, | ||||

Roman Danyliw, Barry Leiba, Martin Vigoureux, and Eric Vyncke for | ||||

their highly valuable feedback that greatly contributed to improving | ||||

this specification. | ||||

Authors' Addresses | Authors' Addresses | |||

Mutsuo Saito | Mutsuo Saito | |||

Hiroshima University | Hiroshima University | |||

Japan | Japan | |||

EMail: saito@math.sci.hiroshima-u.ac.jp | Email: saito@math.sci.hiroshima-u.ac.jp | |||

Makoto Matsumoto | Makoto Matsumoto | |||

Hiroshima University | Hiroshima University | |||

Japan | Japan | |||

EMail: m-mat@math.sci.hiroshima-u.ac.jp | Email: m-mat@math.sci.hiroshima-u.ac.jp | |||

Vincent Roca | ||||

Vincent Roca (editor) | ||||

INRIA | INRIA | |||

Univ. Grenoble Alpes | Univ. Grenoble Alpes | |||

France | France | |||

EMail: vincent.roca@inria.fr | Email: vincent.roca@inria.fr | |||

Emmanuel Baccelli | Emmanuel Baccelli | |||

INRIA | INRIA | |||

France | France | |||

EMail: emmanuel.baccelli@inria.fr | Email: emmanuel.baccelli@inria.fr | |||

End of changes. 80 change blocks. | ||||

206 lines changed or deleted | | 216 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/ |