Quick Links: [Home] [Menu] [BASIC] [TEXT] [TELCOM] [Diff] [Tech Ref] [Files] [Links] [Y2K]
COMPUTER-GENERATED RANDOM NUMBERS WITH AN EYE
FOR CLASSICAL CRYPTOLOGY APPLICATIONS ON
THE NEC PC-8201A AND TANDY MODEL 100/102
---------------------------------------------
Compiled by: David J. Firth
djfirth@gcfn.org
The first thing to know regarding computer-generated random numbers: none
are truly random. The RND function produces number sequences that
approximate the spread of numbers in a random sequence but the numbers
aren't random. The computer uses a well known and easily reproduced
algorithm called linear congruence to produce the random number sequence.
For this reason, programmers often describe the RND function as "pseudorandom"
rather than random.
The algorithm depends upon generating an integer between 0 and some maximum
value. The ratio of the integer to the maximum value expressed as a floating
point number will be between 0 and 1.
According to Microsoft, the general algorithm for the RND function used in
interpreted BASIC is similar to (if not exactly) the following:
x1 = ( x0 * a + c ) MOD 2^24
x1=new number
x0=previous number
a=214013
c=2531011
This function, described in the Microsoft Knowledgebase article Q28150,
calculates a double precision intermediate result for (x0 * a + c). The
value between 0 and 1 is produced by the MOD function.
The values of a and c may vary with the version of BASIC and the computer
for which the RND function was written. The values of a and c given above
appear in some versions of Microsoft BASIC. Other documented values for
BASIC are a=17405, c=10395331; a=214013, c=13737667; and a=214013,
c=10395331 (Schnieder 497).
Since the value of x1 depends upon the previous value of x1 (designated
as x0 in the Microsoft example), the RND function must be given an initial
value for x0. This initial value is called the seed value. For the
NEC PC-8201A, invoking the RND function with a negative argument reseeds
the RND function. Other BASICs may be similar, though newer BASICs use
the RANDOMIZE command for reseeding. When first using the RND function,
the seed is set to 0. See Appendix B for an explanation of a design change
to the pseudorandom number generator for newer versions of MS BASIC.
For a given seed, the sequence of numbers will always be the same (see the
exception in Appendix B). On the NEC PC-8201A a seed value of 0 must be
avoided, since the RND function will return a single value repeatedly as
long as the user invokes RND(0). Thus, never allow a seed of 0 unless you
specifically want this effect.
Possible seed values may be user-entered numbers, though a time-honored
method is to seed the generator with the number of seconds since midnight.
This is simple, but a compromise. Using the number of seconds limits the
seed to a value between 0 and 18,599 (where most computer users will be
asleep for a large majority of the possible values thus narrowing the
probable range of values).
The exact algorithm for the Tandy TRS-80 Model 100, Model 102 and NEC
PC-8201A is not known to the author at this time, though the algorithm in
the system ROMs for these machines is likely similar to the above example.
Microsoft states that this algorithm dates back to versions of Microsoft
BASIC for CPM-80.
The algorithm is not new. D.H. Lahmer described it in 1948. The maximum
integer value (represented by 2^24) is limited by the maximum values of
integer arithmetic for the computer. The integer constant, a, is
approximately factor 2 less than the square root of the maximum integer
value. Lahmer did not use the integer constant, c (Bennett 291). Changing
the values of a and c without careful study and experimentation is not
recommended. Choosing the wrong values for a and c may compromise the
pseudorandom characteristics. Choosing the values of a and c may be
accomplished via specific algorithms, but often the choice of values is
"more of an art than a science" (Schildt 193).
This algorithm produces numbers which are surprisingly good quality if
one ignores repeatability and periodic characteristics. A true random
sequence is expected to produce a spread of numbers where 68% of the
values fall between +/- one standard deviation of the mean value. The
computer-generated sequence achieves only approximately 70% of the
expected data spread (Bennett 292)
Several characteristics work against this algorithm being useful for
high security cryptography on its own. First, the computer calculates the
sequence with limited precision. Thus, the sequence of numbers is limited
to a large though finite set. Second, the result of the function depends
upon the previous result. Thus, the sequence is periodic (Bennett 290).
USING RND FOR SIMPLE CRYPTOGRAPHY:
Without modification, a cipher based upon the Microsoft implementation of
RND is not secure. Given a limited maximum integer value, a brute force
attack using every possible value for integers a and c and x0 will eventually
produce readable plaintext. The speed of the attack depends upon the speed
of the computer performing the attack. With high-powered computers available
to the average consumer and with smart estimating of the initial values,
one could expect to break the cipher in a reasonable amount of time.
In order to strengthen the cipher, the RND sequence needs additional
randomizing elements. Two suggestions include skipping some number of
values in the sequence and changing the RND seed based upon the values
of the text. Although these suggestions do not exclude a brute force
attack, the additional randomizing elements do increase the time required
to break the cipher without the key. Since the vast majority of secret
messages are valuable for only a limited period of time, any increase of
time required for brute force decryption strengthens the temporary security
of the message.
---------------------------------------------------------------------
APPENDIX A: MICROSOFT'S EXPLANATION OF RANDOM NUMBERS
RND and RANDOMIZE Alternatives for Generating Random Numbers
Last reviewed: January 12, 1995
Article ID: Q28150 The information in this article applies to:
The Standard and Professional Editions of Microsoft Visual Basic for MS-DOS,
version 1.0; Microsoft Basic Compiler for MS-DOS and MS OS/2, versions 6.0
and 6.0b; Microsoft QuickBasic for MS-DOS, versions 1.0, 1.01, 1.02, 2.0,
2.01, 3.0, 4.0, 4.0b, and 4.5; Microsoft GW-Basic Interpreter for MS-DOS,
versions 3.2, 3.22 and 3.23; Microsoft QuickBasic Compiler for the Apple
Macintosh; Most other Microsoft Basic Interpreters and Compilers for the
Apple Macintosh, MS-DOS, MS OS/2, and CP/M-80
SUMMARY
If you want a substitute for RND and RANDOMIZE, you can use your own
equation to generate random numbers as shown below.
Microsoft Basic offers the RND function to return random single-precision
numbers between 0.000000 and 1.000000. The RANDOMIZE statement can be used
to reseed (or initially start) a given sequence returned by RND. Microsoft
Basic uses the linear-congruential method for random-number generation in
the RND function.
This information is also included with the Help file provided with the
Standard and Professional Editions of Microsoft Visual Basic for MS-DOS,
version 1.0.
MORE INFORMATION
Microsoft Basic uses the linear-congruential method for random-number
generation in the RND function. The following is an example of the
linear-congruential method formula, similar to that used by RND in
Microsoft Basic:
x1 = ( x0 * a + c ) MOD 2^24
In the above example, the variables equal the following:
x1=new number
x0=previous number
a=214013
c=2531011
(Note: the MOD operator in the formula above returns the integer remainder
after an integer division.)
The expression x1/(2^24) returns a floating-point number between 0.0 and
1.0. Please refer to Code Examples 1 and 2 below for an illustration.
For more random number generation algorithms, see pages 353-364 of
"Microsoft QuickBASIC Programmer's Toolbox," by John C. Craig, published
by Microsoft Press (1988). Seven random number subprograms are documented,
and a companion disk in MS-DOS format is also available from Microsoft Press.
The programs in Craig's book are written for Microsoft QuickBasic for
MS-DOS, version 4.0 for the IBM PC. Some programs, such as the random
number programs, are general and can easily be modified to run in Microsoft
QuickBasic for the Apple Macintosh. When you run these programs, you may
want to reseed the random number sequence regularly (such as every few
hundred invocations) for greater uniformity.
Code Example 1
The following is an example of the linear congruential method for generating
pseudo-random numbers:
' To try this example in VBDOS.EXE:
' 1. From the File menu, choose New Project.
' 2. Copy the code example to the Code window.
' 3. Press F5 to run the program.
DEFDBL A-Z ' Requires double-precision intermediate variables. a = 214013
c = 2531011 z = 2 ^ 24
INPUT "Input any seed value: ", x0
FOR count = 1 TO 25 ' print 25 random numbers between 0.0 and 1.0:
temp = x0 * a + c
' Calculate (temp MOD z) and assign to x1:
temp = temp / z
x1 = (temp - FIX(temp)) * z
' Print the result as value between 0.0000000 and 1.0000000:
result = x1 / z
PRINT result
' Reseed the calculation before the next iteration:
x0 = x1 ' x0 and x1 range from 0 to 16777216 (2^24)
NEXT
Code Example 2
The following is the same as Example 1, except the random numbers are
plotted to illustrate their uniform distribution:
' To try this example in VBDOS.EXE:
' 1. From the File menu, choose New Project.
' 2. Copy the code example to the Code window.
' 3. Press F5 to run the program.
DEFDBL A-Z ' Requires double-precision intermediate variables.
SCREEN 2 a = 214013 c = 2531011 z = 2 ^ 24
INPUT "Input seed value: ", x0
FOR count = 1 TO 5000
temp = x0 * a + c
' Calculate (temp MOD z) and assign to x1:
temp = temp / z
x1 = (temp - FIX(temp)) * z
result = x1 / z ' Result is between 0.000000 and 1.000000
GOSUB 100 ' Plot Result
x0 = x1 ' x0 and x1 range from 0 to 16777216 (2^24)
NEXT
END
' Plot the random points to see their uniform distribution:
100 y = y + 1
IF y > 200 THEN y = 0 ' Wrap plot at y=200 pixels.
x = result * 500 ' Assumes screen mode <= 500 pixels wide.
PSET (x, y) ' PSET requires a graphics screen mode.
RETURN
THE INFORMATION PROVIDED IN THE MICROSOFT KNOWLEDGE BASE IS PROVIDED "AS IS"
WITHOUT WARRANTY OF ANY KIND. MICROSOFT DISCLAIMS ALL WARRANTIES, EITHER
EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY AND FITNESS
FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL MICROSOFT CORPORATION OR ITS
SUPPLIERS BE LIABLE FOR ANY DAMAGES WHATSOEVER INCLUDING DIRECT, INDIRECT,
INCIDENTAL, CONSEQUENTIAL, LOSS OF BUSINESS PROFITS OR SPECIAL DAMAGES,
EVEN IF MICROSOFT CORPORATION OR ITS SUPPLIERS HAVE BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES. SOME STATES DO NOT ALLOW THE EXCLUSION OR
LIMITATION OF LIABILITY FOR CONSEQUENTIAL OR INCIDENTAL DAMAGES SO THE
FOREGOING LIMITATION MAY NOT APPLY.
Last reviewed: January 12, 1995
c1997 Microsoft Corporation. All rights reserved. Legal Notices.
---------------------------------------------------------------------
APPENDIX B: MICROSOFT EXPLANATION OF RANDOMIZE 0
RANDOMIZE Statements Reseed but Don't Restart RND Sequence
Last reviewed: January 12, 1995
Article ID: Q36736
SUMMARY
The first invocation of the RANDOMIZE statement determines a given set
of random numbers returned from successive calls to the RND function. Not
invoking the RANDOMIZE statement in a program is equivalent to invoking
RANDOMIZE 0 before invoking RND. Note that a second (or subsequent)
RANDOMIZE x statement does not restart the number sequence from the
beginning of the set for a given x, but it randomly changes (reseeds) the
sequence from what it would have been from that point on. This behavior is
by design.
Example 2 below illustrates this in detail.
If you want to return the same sequence of random numbers several times
within a given program run, you can invoke the RND function with the exact
same negative number argument followed by a sequence of RND invocations with
a positive argument or no argument. Invoking RND with a negative argument
eliminates the effect of a previous RANDOMIZE statement. Please see Example
1 below for further illustration.
MORE INFORMATION
This behavior of the RANDOMIZE statement and the RND function occurs in
most versions of Microsoft Basic, including the following:
Microsoft QuickBasic versions 1.0, 1.01, 1.02, 2.0, 2.01, 3.0, 4.0, 4.0b,
and 4.5 for the IBM PC; Microsoft Basic Compiler versions 5.35 and 5.36 for
MS-DOS; Microsoft Basic Compiler versions 6.0 and 6.0b for MS-DOS and
MS OS/2; Microsoft Basic PDS versions 7.0 and 7.1 for MS-DOS and MS OS/2;
Microsoft GW-Basic Interpreter versions 3.20, 3.22, and 3.23 for MS-DOS;
Microsoft QuickBasic version 1.0 for the Apple Macintosh; Microsoft Basic
Compiler version 1.0 for the Apple Macintosh; Microsoft Basic Interpreter
versions 1.0, 1.01, 2.0, 2.1, and 3.0 for the Apple Macintosh; Microsoft
Visual Basic programming system version 1.0 for Windows
Other versions of Basic may behave differently.
If you would like an alternative to this behavior of RND and RANDOMIZE, you
may use your own formula to generate random numbers as shown in a separate
article (query on the words RANDOM and EQUATION in this database for more
information).
Example 1
(This example of invoking RND once with a negative argument always returns
the same sequence of random numbers for subsequent invocations of RND.)
CLS
RANDOMIZE TIMER ' Ignored unless you remove RND(-1) below.
FOR j = 1 TO 2
' Passing a negative value to the RND function supersedes the effect
' of the previous RANDOMIZE TIMER statement:
PRINT RND(-1) ' Remove this line for a different sequence on every
' loop iteration. Otherwise, each j loop iteration
' (and separate program run) returns the same
' three-number sequence for the inner i loop.
FOR i = 1 TO 3
PRINT RND
NEXT I
PRINT
NEXT J
Example 2
FOR k = 1 TO 5
PRINT RND
NEXT k
Below is the default random number set output from the above program, when run with QB.EXE version 4.0 on an IBM PC. The following sequence of random numbers varies with different versions of Microsoft QuickBasic and Basic Compilers:
.7107346
.99058
.8523988
.3503776
4.363585E-02
The following code shows the effect of RANDOMIZE 0 at start-up:
PRINT "Set the seed to zero at startup"
RANDOMIZE 0
FOR k = 1 TO 5
PRINT RND
NEXT k
PRINT "Again, reset the seed to zero"
RANDOMIZE 0
FOR k = 1 TO 5
PRINT RND
NEXT k
The above program has the following output:
Set the seed to zero at startup
.7107346
.99058
.8523988
.3503776
4.363585E-02
Again, reset the seed to zero
.7987763
.6497337
.5426014
.9642789
8.590406E-02
Note: The second invocation of RANDOMIZE 0 does not restart the sequence
from the beginning. This is by design. If you remove the second RANDOMIZE 0
statement and run the program again, the sixth through tenth numbers are
different than above. This shows that multiple RANDOMIZE statements reseed
the sequence (and change the random number set displayed), but they do not
restart the sequence from the beginning.
THE INFORMATION PROVIDED IN THE MICROSOFT KNOWLEDGE BASE IS PROVIDED "AS IS"
WITHOUT WARRANTY OF ANY KIND. MICROSOFT DISCLAIMS ALL WARRANTIES, EITHER
EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY AND FITNESS
FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL MICROSOFT CORPORATION OR ITS
SUPPLIERS BE LIABLE FOR ANY DAMAGES WHATSOEVER INCLUDING DIRECT, INDIRECT,
INCIDENTAL, CONSEQUENTIAL, LOSS OF BUSINESS PROFITS OR SPECIAL DAMAGES, EVEN
IF MICROSOFT CORPORATION OR ITS SUPPLIERS HAVE BEEN ADVISED OF THE POSSIBILITY
OF SUCH DAMAGES. SOME STATES DO NOT ALLOW THE EXCLUSION OR LIMITATION OF
LIABILITY FOR CONSEQUENTIAL OR INCIDENTAL DAMAGES SO THE FOREGOING LIMITATION
MAY NOT APPLY.
Last reviewed: January 12, 1995
c1997 Microsoft Corporation. All rights reserved. Legal Notices.
---------------------------------------------------------------------
APPENDIX C: BIBLIOGRAPHY
A hallmark of good research is well documented sources and peer review. The
sources are contained in this appendix. The peer review is well-thought out
feedback and suggestions via electronic mail. I may be reached via:
djfirth@freenet.columbus.oh.us
Not all of the following works were cited, though all of the following were
consulted. They all contributed to the author's understanding of pseudorandom
numbers and basic cryptology for the Model T computer.
Bauer, F.L. "Decrypted Secrets: Methods and Maxims of Cryptology."
Berlin: Springer-Verlag Berlin Heidelberg, 1997.
Bennett, William Ralph Jr. "Scientific and Engineering Problem-
Solving with the Computer." Englewood Cliffs: Prentice-Hall, 1976.
Gaines, Helen Fouche. "Cryptanalysis: A Study of Ciphers and their
Solutions." New York: Dover Publications, 1939. Formerly
published as "Elementary Cryptanalysis."
Kennedy, James Main. "CFRN20.BA." Computer Program. Available from
Club 100 File Library: www.the-dock.com/club100.html, 1997.
Microsoft Corporation. "Q28150: RND and RANDOMIZE Alternatives for
Generating Random Numbers." Microsoft Knowledgebase. Available
via: www.asia.microsoft.com. Redmond: 1995.
Microsoft Corporation. "Q36736: RANDOMIZE Statements Reseed but Don't
Restart RND Sequence." Microsoft Knowledgebase. Available
via: www.asia.microsoft.com. Redmond: 1995.
Schildt, Herbert. "Advanced Turbo Pascal." Berkeley: Osborne McGraw
Hill, 1987.
Schnieder, David I. "Handbook of BASIC." 3rd Ed. New York: Parady
Publishing (Simon & Schuster), 1988.
Sinkov, Abraham. "Elementary Cryptanalysis: A Mathematical Approach."
New York: The Mathematical Association of America, 1966.
Stoll, Clifford. "Silicon Snake Oil." New York: Anchor Books, 1995.
Original author of this page: David Firth.
This page best viewed on ANY browser. This author strongly supports access by persons with limited-capability and text-only browsers. Content is better than flash & dazzle.