Back to Homepage
VMPC One-Way Function P vs NP Project VMPC Encryption Technology VMPC-R CSPRNG VMPCrypt Application Permutu Game Publications About Author Contact


VMPC-R Cryptographically Secure Pseudo-Random Number Generator

1. VMPC-R CSPRNG general description
2. VMPC-R Algorithm
3. VMPC-R Key Scheduling Algorithm
4. Test output of VMPC-R


Download VMPC-R CSPRNG Implementation:
VMPC-R Implementation in C
VMPC-R Implementation in Pascal/Delphi
VMPC-R Implementation in Assembler

Download VMPC-R paper
VMPC-R.pdf (260 KB)

The paper is also available
at the IACR ePrint archive





1. VMPC-R Cryptographically Secure Pseudo-Random Number Generator

The VMPC-R CSPRNG was designed to produce a stream of values as close to the random model as possible and to have a large period. The algorithm's internal state for the common-in-practical-applications 8-bit word size is 256!2*2567=23424.

The main statistical test we used to analyse the algorithm:
  • Distinguished the output of the popular RC4 stream cipher from randomness after 216.6 3-bit outputs.
  • Did not distinguish the output of VMPC-R from randomness after 246.8 3-bit outputs.

For smaller than 3-bit word sizes VMPC-R produced undistinguishable from random output after exhausting:
  • 98% of the state-space (twelve 42-output-long cycles) operating on integers {0,1} (single-bit mode)
  • 62% of the state-space (longest cycle) operating on integers {0,1,2}.
  • 82% of the state-space (longest cycle) operating on integers {0,1,2,3} (2-bit mode).
  • 33% of the state-space (longest cycle) operating on integers {0,1,...,5}.
  • 78% of the state-space (longest cycle) operating on integers {0,1,...,6}.
  • 10% of the state-space (test limited by computational power, no cycle found) operating on integers {0,1,...,7}.
No statistical anomalies were found in the shorter cycles for the quoted above 2,3,4,5,6 word sizes, either.


We tested the output of the VMPC-R algorithm in many other statistical tests for many different word sizes and found no way of distinguishing it from a truly random source. For the detailed description of the tests please refer to the VMPC-R paper

The VMPC-R algorithm generates a stream of pseudorandom integers from two N-element permutations (usually N=256 and the generated integers are 8-bit). The initial state of the permutations is determined by the VMPC-R Key Scheduling Algorithm described in section 3.

The VMPC-R algorithm can be used either as a pseudo-random number generator and as a stream cipher where its outputs are xored with the consecutive plaintext bytes.


2. VMPC-R algorithm:

  N  :  word size; in most practical applications N=256
  P, S  :  N-element tables storing permutations of integers {0,1,...,N-1}
  a, b, c, d, e, f, n  :  integer variables
  L  :  number of pseudorandom integers to generate
  +     denotes addition modulo N


Table 1. VMPC-R CSPRNG pseudo code
repeat steps 1-10 L times:

   1. a = P[a + c + S[n]]
   2. b = P[b + a]
   3. c = P[c + b]

   4. d = S[d + f + P[n]]
   5. e = S[e + d]
   6. f = S[f + e]

   7. output S[S[S[c + d]] + 1]

   8. swap P[n] with P[f]
   9. swap S[n] with S[a]

  10. n = n + 1







3. VMPC-R Key Scheduling Algorithm

The VMPC-R Key Scheduling Algorithm transforms the seed (which could be a cryptographic key and an Initialization Vector) into the algorithm's internal state.

Notation: as in section 2, with:

  a, b, c, d, e, f, n  
  k  :  length of the seed or cryptographic key; k ∈ {1,2,...,N}
  K  :  k-element table storing the seed or cryptographic key
  v  :  length of the Initialization Vector; v ∈ {1,2,...,N}
  V  :  v-element table storing the Initialization Vector
  i  :  temporary integer variable
   R  =  N * Ceiling(k2/(6N))
  +     denotes addition modulo N

Table 2. VMPC-R Key Scheduling Algorithm pseudo code
0. a = b = c = d = e = f = n = 0
   P[i] = S[i] = i for i ∈ {0,1,...,N-1}

1. KSARound(K, k)
2. KSARound(V, v)
3. KSARound(K, k)
4. n = S[S[S[c + d]] + 1]
5. generate N outputs with VMPC-R CSPRNG (for L=N)


Function KSARound(M, m) definition:
  6. i = 0
  7. repeat steps 8-18 R times:
       8. a = P[a + f + M[i]] + i;   i = (i + 1) mod m
       9. b = S[b + a + M[i]] + i;   i = (i + 1) mod m
      10. c = P[c + b + M[i]] + i;   i = (i + 1) mod m
      11. d = S[d + c + M[i]] + i;   i = (i + 1) mod m
      12. e = P[e + d + M[i]] + i;   i = (i + 1) mod m
      13. f = S[f + e + M[i]] + i;   i = (i + 1) mod m

      14. swap P[n] with P[b]
      15. swap S[n] with S[e]
      16. swap P[d] with P[f]
      17. swap S[a] with S[c]

      18. n = n + 1


The KSARound function performs R = N * Ceiling(k2/(6N)) iterations. This value ensures that each word of a k-word key updates the internal state at least k times. For N = 256 and key sizes k ∈ {2,3,...,39} (keys up to 312 bits) R = N. For N = 256 and key sizes k ∈ {40,41,...,55} (keys from 320 to 440 bits) R = 2N. And so on.





4. Test output of VMPC-R

Example output of the VMPC-R CSPRNG for a given key (K) and a given initialization vector (V) are shown in Tables 3,4 and 5.


Table 3. Example output of VMPC-R
K; k=9 {11, 22, 33, 144, 155, 166, 233, 244, 255}
V; v=8 {255, 250, 200, 150, 100, 50, 5, 1}
output of KSA:
P index 0 1 2 3 252 253 254 255
P value 97 218 106 125 139 86 36 126
S index 0 1 2 3 252 253 254 255
S value 152 143 19 154 92 25 24 157
output of CSPRNG:
Output index 0 1 2 3 254 255 256 257
Output value 49 161 79 69 85 237 96 243
Output index 1000   1001   10000   10001   100000 100001 1000000 1000001
Output value 181 184 136 99 67 27 253 231



Table 4. Example output of VMPC-R
K; k=32 {104, 9, 46, 231, 132, 149, 234, 147, 224, 97, 230, 127, 124, 109, 34, 171, 88, 185, 158, 23, 116, 69, 90, 195, 208, 17, 86, 175, 108, 29, 146, 219}
(X=123; repeat 32 times:{X=X*134775813+1; output=X mod 256})
V; v=32 {149, 234, 147, 224, 97, 230, 127, 124, 109, 34, 171, 88, 185, 158, 23, 116, 69, 90, 195, 208, 17, 86, 175, 108, 29, 146, 219, 72, 105, 14, 71, 100}
(X=132; repeat 32 times:{X=X*134775813+1; output=X mod 256})
output of KSA:
P index 0 1 2 3 252 253 254 255
P value 76 44 167 7 250 147 240 51
S index 0 1 2 3 252 253 254 255
S value 239 59 110 207 98 23 178 227
output of CSPRNG:
Output index 0 1 2 3 254 255 256 257
Output value 219 178 157 119 2 155 62 20
Output index 1000   1001   10000   10001   100000 100001 1000000 1000001
Output value 3 239 236 81 195 11 186 127



Table 5. Example output of VMPC-R
K; k=256 {147, 224, 97, 230, 127, 124, 109, 34, 171, 88, 185, 158, 23, 116, 69, 90, 195, 208, 17, 86, 175, 108, 29, 146, 219, 72, 105, 14, 71, 100, 245, 202, 243, 192, 193, 198, 223, 92, 205, 2, 11, 56, 25, 126, 119, 84, 165, 58, 35, 176, 113, 54, 15, 76, 125, 114, 59, 40, 201, 238, 167, 68, 85, 170, 83, 160, 33, 166, 63, 60, 45, 226, 107, 24, 121, 94, 215, 52, 5, 26, 131, 144, 209, 22, 111, 44, 221, 82, 155, 8, 41, 206, 7, 36, 181, 138, 179, 128, 129, 134, 159, 28, 141, 194, 203, 248, 217, 62, 55, 20, 101, 250, 227, 112, 49, 246, 207, 12, 61, 50, 251, 232, 137, 174, 103, 4, 21, 106, 19, 96, 225, 102, 255, 252, 237, 162, 43, 216, 57, 30, 151, 244, 197, 218, 67, 80, 145, 214, 47, 236, 157, 18, 91, 200, 233, 142, 199, 228, 117, 74, 115, 64, 65, 70, 95, 220, 77, 130, 139, 184, 153, 254, 247, 212, 37, 186, 163, 48, 241, 182, 143, 204, 253, 242, 187, 168, 73, 110, 39, 196, 213, 42, 211, 32, 161, 38, 191, 188, 173, 98, 235, 152, 249, 222, 87, 180, 133, 154, 3, 16, 81, 150, 239, 172, 93, 210, 27, 136, 169, 78, 135, 164, 53, 10, 51, 0, 1, 6, 31, 156, 13, 66, 75, 120, 89, 190, 183, 148, 229, 122, 99, 240, 177, 118, 79, 140, 189, 178, 123, 104, 9, 46, 231, 132, 149, 234}
(X=234; repeat 256 times:{X=X*134775813+1; output=X mod 256})
V; v=8 {255, 250, 200, 150, 100, 50, 5, 1}
output of KSA:
P index 0 1 2 3 252 253 254 255
P value 10 34 13 239 209 9 154 220
S index 0 1 2 3 252 253 254 255
S value 253 106 200 178 75 251 129 209
output of CSPRNG:
Output index 0 1 2 3 254 255 256 257
Output value 201 85 155 17 187 48 55 198
Output index 1000   1001   10000   10001   100000 100001 1000000 1000001
Output value 110 179 189 210 4 15 253 83


Home  |   VMPC Function  |   VMPC-R CSPRNG  |   VMPC Stream Cipher  |   VMPC-MAC scheme  |   VMPC KSA3 algorithm  |   Research  |   Inverting Challenge
P vs NP Project  |   VMPCrypt Application  |   Permutu Game  |   Publications  |   About Author  |   Contact

Copyright © 1999-2016 Bartosz Zoltak
Supported by OHTON EXPO Okna Wroc³aw