draft-ietf-tsvwg-tinymt32-02.txt   draft-ietf-tsvwg-tinymt32-03.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: November 17, 2019 V. Roca (Ed.) Expires: November 28, 2019 V. Roca (Ed.)
E. Baccelli E. Baccelli
INRIA INRIA
May 16, 2019 May 27, 2019
TinyMT32 Pseudo Random Number Generator (PRNG) TinyMT32 Pseudo Random Number Generator (PRNG)
draft-ietf-tsvwg-tinymt32-02 draft-ietf-tsvwg-tinymt32-03
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 [MT98]. The main
M. Saito and M. Matsumoto. The main advantage of TinyMT32 over MT advantage of TinyMT32 over MT is the use of a small internal state,
is the use of a small internal state, compatible with most target compatible with most target platforms including embedded devices,
platforms including embedded devices, while keeping a reasonably good while keeping a reasonably good randomness.
randomness.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
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 November 17, 2019. This Internet-Draft will expire on November 28, 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 34 skipping to change at page 2, line 33
7.1. Normative References . . . . . . . . . . . . . . . . . . 9 7.1. Normative References . . . . . . . . . . . . . . . . . . 9
7.2. Informative References . . . . . . . . . . . . . . . . . 9 7.2. Informative References . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10
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: Makoto Matsumoto, from Hiroshima University:
o Official web site: <http://www.math.sci.hiroshima-u.ac.jp/~m- o Official web site [TinyMT-web]
mat/MT/TINYMT/> o Official github site and reference implementation [TinyMT-dev]
o Official github site and reference implementation:
<https://github.com/MersenneTwister-Lab/TinyMT>
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 introduced by Mutsuo Saito and
introduced by Mutsuo Saito and Makoto Matsumoto in 2011. This Makoto Matsumoto in 2011 of the Mersenne Twister (MT) PRNG [MT98].
document focusses on the TinyMT32 variant (rather than TinyMT64) of This document focusses on the TinyMT32 variant (rather than TinyMT64)
the PRNG, which outputs 32-bit unsigned integers. of the TinyMT 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 (2^^127 - 1) than MT. The merit of TinyMT is in a far shorter period (2^^127 - 1) than MT. The merit of TinyMT is in
its small size of the internal state of 127 bits, far smaller than its small size of the internal state of 127 bits, far smaller than
the 19937 bits of MT. According to statistical tests (BigCrush in the 19937 bits of MT. According to statistical tests (BigCrush in
TestU01 <http://simul.iro.umontreal.ca/testu01/tu01.html> and TestU01 and AdaptiveCrush), the quality of the outputs of TinyMT
AdaptiveCrush <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ seems pretty good in terms of randomnes (in particular the uniformity
ADAPTIVE/>) the quality of the outputs of TinyMT seems pretty good in of generated numbers), taking the small size of the internal state
terms of randomnes (in particular the uniformity of generated into consideration (see [TinyMT-web]). From this point of view,
numbers), taking the small size of the internal state into TinyMT32 represents a major improvement with respect to the Park-
consideration (see <http://www.math.sci.hiroshima-u.ac.jp/~m- Miler Linear Congruential PRNG (e.g., as specified in [RFC5170]) that
mat/MT/TINYMT/index.html>). From this point of view, TinyMT32 suffers several known limitations (see for instance [PTVF92], section
represents a major improvement with respect to the Park-Miler Linear 7.1, p. 279, and [RLC-ID], Appendix B). However, neither the TinyMT
Congruential PRNG (e.g., as specified in [RFC5170]) that suffers nor MT PRNG are meant to be used for cryptographic applications.
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 make 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 sequence of pseudo-random numbers depend only on the seed value, this
specification requires the use of a specific parameter set (see specification requires the use of a specific parameter set (see
Section 3.1). This is a first difference with respect to the 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 that leaves this parameter set unspecified. A second Matsumoto that leaves this parameter set unspecified. A second
skipping to change at page 4, line 9 skipping to change at page 4, line 4
The TinyMT32 PRNG requires to be initialized with a parameter set The TinyMT32 PRNG requires to be initialized with a parameter set
that needs to be well chosen. In this specification, for the sake of that needs 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 o mat1 = 0x8f7011ee = 2406486510
o mat2 = 0xfc78ff1f = 4235788063 o mat2 = 0xfc78ff1f = 4235788063
o tmat = 0x3793fdff = 932445695 o 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 file tinymt32dc/tinymt32dc.0.1048576.txt, by Kenji Rikitake,
and available at <https://github.com/jj1bdx/tinymtdc-longbatch/>. and available at [TinyMT-params]. This is also the parameter set
This is also the parameter set used in [KR12]. used in [KR12].
The TinyMT32 PRNG reference implementation is reproduced in Figure 1, The TinyMT32 PRNG reference implementation is reproduced in Figure 1,
with the following differences with respect to the original source with the following differences with respect to the original source
code: code:
o the original copyright and licence have been removed, in o the original copyright and licence have been removed, in
accordance with BCP 78 and the IETF Trust's Legal Provisions accordance with BCP 78 and the IETF Trust's Legal Provisions
Relating to IETF Documents (http://trustee.ietf.org/license-info); Relating to IETF Documents (http://trustee.ietf.org/license-info);
o the source code initially spread over the tinymt32.h and o the source code initially spread over the tinymt32.h and
tinymt32.c files has been merged; tinymt32.c files has been merged;
skipping to change at page 9, line 14 skipping to change at page 9, line 10
avoided, these calculations leading potentially to different rounding avoided, these calculations leading potentially 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 put on not introducing biases in the randomness of the mapped output
(it may be the case with some mapping algorithms) incompatible with (it may be the case with some mapping algorithms) incompatible with
the use-case requirements. The details of how to perform such a 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 4. 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. specific security risks per se. However, neither the TinyMT nor MT
PRNG are meant to be used for cryptographic applications.
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 Miler Linear Congruential PRNG. The authors would like to thank Carl
Stewart Bryant, Greg Skinner, the three TSVWG chairs, Wesley Eddy, Wallace, Stewart Bryant, Greg Skinner, the three TSVWG chairs, Wesley
our shepherd, David Black and Gorry Fairhurst, as well as Spencer Eddy, our shepherd, David Black and Gorry Fairhurst, as well as
Dawkins and Mirja Kuhlewind. Last but not least, the authors are Spencer Dawkins and Mirja Kuhlewind. Last but not least, the authors
really grateful to the IESG members, in particular Benjamin Kaduk, are really grateful to the IESG members, in particular Benjamin
Eric Rescorla, and Adam Roach for their highly valuable feedbacks Kaduk, Eric Rescorla, and Adam Roach for their highly valuable
that greatly contributed to improve this specification. feedbacks 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>.
skipping to change at page 10, line 18 skipping to change at page 10, line 10
M. Wahlisch, "RIOT: An Open Source Operating System for M. Wahlisch, "RIOT: An Open Source Operating System for
Low-End Embedded Devices in the IoT", IEEE Internet of Low-End Embedded Devices in the IoT", IEEE Internet of
Things Journal (Volume 5, Issue 6), DOI: Things Journal (Volume 5, Issue 6), DOI:
10.1109/JIOT.2018.2815038, December 2018. 10.1109/JIOT.2018.2815038, December 2018.
[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", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
September 14, 2012, Copenhagen, Denmark, DOI: September 14, 2012, Copenhagen, Denmark, DOI:
http://dx.doi.org/10.1145/2364489.2364504, September 2012. http://dx.doi.org/10.1145/2364489.2364504, September 2012.
[MT98] Matsumoto, M. and T. Nishimura, "Mersenne Twister: A
623-dimensionally equidistributed uniform pseudorandom
number generator", ACM Transactions on Modeling and
Computer Simulation (TOMACS), Volume 8 Issue 1, Jan. 1998,
pp.3-30, January 1998, DOI:10.1145/272991.272995, January
1998.
[PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery,
"Numerical Recipies in C; Second Edition", 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 [RLC-ID] Roca, V. and B. Teibi, "Sliding Window Random Linear Code
(RLC) Forward Erasure Correction (FEC) Scheme for (RLC) Forward Erasure Correction (FEC) Scheme for
FECFRAME", Work in Progress, Transport Area Working Group FECFRAME", Work in Progress, Transport Area Working Group
(TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in (TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in
Progress), February 2019, <https://tools.ietf.org/html/ Progress), February 2019, <https://tools.ietf.org/html/
draft-ietf-tsvwg-rlc-fec-scheme>. draft-ietf-tsvwg-rlc-fec-scheme>.
Authors' Addresses [TinyMT-dev]
Saito, M. and M. Matsumoto, "Tiny Mersenne Twister
(TinyMT) github site",
<https://github.com/MersenneTwister-Lab/TinyMT>.
[TinyMT-params]
Rikitake, K., "TinyMT pre-calculated parameter list github
site", <https://github.com/jj1bdx/tinymtdc-longbatch/>.
[TinyMT-web]
Saito, M. and M. Matsumoto, "Tiny Mersenne Twister
(TinyMT) web site",
<http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/>.
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
 End of changes. 14 change blocks. 
39 lines changed or deleted 59 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/