turing.py

   1 # Turing PRNG for Python, v1.3
   2 # Copyright 2013 William McBrine
   3 # Based on material Copyright 2002 Qualcomm Inc., written by Greg Rose
   4 #
   5 # License from original C version:
   6 # --------------------------------
   7 #
   8 # This software is free for commercial and non-commercial use subject to
   9 # the following conditions:
  10 #
  11 # 1.  Copyright remains vested in QUALCOMM Incorporated, and Copyright
  12 # notices in the code are not to be removed.  If this package is used in
  13 # a product, QUALCOMM should be given attribution as the author of the
  14 # Turing encryption algorithm. This can be in the form of a textual
  15 # message at program startup or in documentation (online or textual)
  16 # provided with the package.
  17 #
  18 # 2.  Redistribution and use in source and binary forms, with or without
  19 # modification, are permitted provided that the following conditions are
  20 # met:
  21 #
  22 # a. Redistributions of source code must retain the copyright notice,
  23 #    this list of conditions and the following disclaimer.
  24 #
  25 # b. Redistributions in binary form must reproduce the above copyright
  26 #    notice, this list of conditions and the following disclaimer in the
  27 #    documentation and/or other materials provided with the
  28 #    distribution.
  29 #
  30 # c. All advertising materials mentioning features or use of this
  31 #    software must display the following acknowledgement: This product
  32 #    includes software developed by QUALCOMM Incorporated.
  33 #
  34 # 3.  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
  35 # WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  36 # MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE AND AGAINST
  37 # INFRINGEMENT ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR
  38 # CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  39 # EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  40 # PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  41 # PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  42 # LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  43 # NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  44 # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  45 #
  46 # 4.  The license and distribution terms for any publically available
  47 # version or derivative of this code cannot be changed, that is, this
  48 # code cannot simply be copied and put under another distribution
  49 # license including the GNU Public License.
  50 #
  51 # 5.  The Turing family of encryption algorithms are covered by patents
  52 # in the United States of America and other countries. A free and
  53 # irrevocable license is hereby granted for the use of such patents to
  54 # the extent required to utilize the Turing family of encryption
  55 # algorithms for any purpose, subject to the condition that any
  56 # commercial product utilising any of the Turing family of encryption
  57 # algorithms should show the words "Encryption by QUALCOMM" either on
  58 # the product or in the associated documentation.
  59
  60 """ Turing PRNG for Python
  61
  62     A Python implementation of Qualcomm's Turing pseudo-random number
  63     generator. Loosely based on Greg Rose's TuringFast.c et al. This is
  64     immensely slower than the C version, but useful for some limited
  65     purposes. For Python 2.5 through 2.7.
  66
  67 """
  68
  69 __author__ = 'William McBrine <wmcbrine@gmail.com>'
  70 __version__ = '1.3'
  71
  72 import struct
  73 from itertools import izip
  74
  75 # 8->32 _SBOX generated by Millan et. al. at Queensland University of
  76 # Technology. See: E. Dawson, W. Millan, L. Burnett, G. Carter, "On the
  77 # Design of 8*32 S-boxes". Unpublished report, by the Information
  78 # Systems Research Centre, Queensland University of Technology, 1999.
  79
  80 _QBOX = [
  81     0x1faa1887, 0x4e5e435c, 0x9165c042, 0x250e6ef4, 0x5957ee20, 0xd484fed3,
  82     0xa666c502, 0x7e54e8ae, 0xd12ee9d9, 0xfc1f38d4, 0x49829b5d, 0x1b5cdf3c,
  83     0x74864249, 0xda2e3963, 0x28f4429f, 0xc8432c35, 0x4af40325, 0x9fc0dd70,
  84     0xd8973ded, 0x1a02dc5e, 0xcd175b42, 0xf10012bf, 0x6694d78c, 0xacaab26b,
  85     0x4ec11b9a, 0x3f168146, 0xc0ea8ec5, 0xb38ac28f, 0x1fed5c0f, 0xaab4101c,
  86     0xea2db082, 0x470929e1, 0xe71843de, 0x508299fc, 0xe72fbc4b, 0x2e3915dd,
  87     0x9fa803fa, 0x9546b2de, 0x3c233342, 0x0fcee7c3, 0x24d607ef, 0x8f97ebab,
  88     0xf37f859b, 0xcd1f2e2f, 0xc25b71da, 0x75e2269a, 0x1e39c3d1, 0xeda56b36,
  89     0xf8c9def2, 0x46c9fc5f, 0x1827b3a3, 0x70a56ddf, 0x0d25b510, 0x000f85a7,
  90     0xb2e82e71, 0x68cb8816, 0x8f951e2a, 0x72f5f6af, 0xe4cbc2b3, 0xd34ff55d,
  91     0x2e6b6214, 0x220b83e3, 0xd39ea6f5, 0x6fe041af, 0x6b2f1f17, 0xad3b99ee,
  92     0x16a65ec0, 0x757016c6, 0xba7709a4, 0xb0326e01, 0xf4b280d9, 0x4bfb1418,
  93     0xd6aff227, 0xfd548203, 0xf56b9d96, 0x6717a8c0, 0x00d5bf6e, 0x10ee7888,
  94     0xedfcfe64, 0x1ba193cd, 0x4b0d0184, 0x89ae4930, 0x1c014f36, 0x82a87088,
  95     0x5ead6c2a, 0xef22c678, 0x31204de7, 0xc9c2e759, 0xd200248e, 0x303b446b,
  96     0xb00d9fc2, 0x9914a895, 0x906cc3a1, 0x54fef170, 0x34c19155, 0xe27b8a66,
  97     0x131b5e69, 0xc3a8623e, 0x27bdfa35, 0x97f068cc, 0xca3a6acd, 0x4b55e936,
  98     0x86602db9, 0x51df13c1, 0x390bb16d, 0x5a80b83c, 0x22b23763, 0x39d8a911,
  99     0x2cb6bc13, 0xbf5579d7, 0x6c5c2fa8, 0xa8f4196e, 0xbcdb5476, 0x6864a866,
 100     0x416e16ad, 0x897fc515, 0x956feb3c, 0xf6c8a306, 0x216799d9, 0x171a9133,
 101     0x6c2466dd, 0x75eb5dcd, 0xdf118f50, 0xe4afb226, 0x26b9cef3, 0xadb36189,
 102     0x8a7a19b1, 0xe2c73084, 0xf77ded5c, 0x8b8bc58f, 0x06dde421, 0xb41e47fb,
 103     0xb1cc715e, 0x68c0ff99, 0x5d122f0f, 0xa4d25184, 0x097a5e6c, 0x0cbf18bc,
 104     0xc2d7c6e0, 0x8bb7e420, 0xa11f523f, 0x35d9b8a2, 0x03da1a6b, 0x06888c02,
 105     0x7dd1e354, 0x6bba7d79, 0x32cc7753, 0xe52d9655, 0xa9829da1, 0x301590a7,
 106     0x9bc1c149, 0x13537f1c, 0xd3779b69, 0x2d71f2b7, 0x183c58fa, 0xacdc4418,
 107     0x8d8c8c76, 0x2620d9f0, 0x71a80d4d, 0x7a74c473, 0x449410e9, 0xa20e4211,
 108     0xf9c8082b, 0x0a6b334a, 0xb5f68ed2, 0x8243cc1b, 0x453c0ff3, 0x9be564a0,
 109     0x4ff55a4f, 0x8740f8e7, 0xcca7f15f, 0xe300fe21, 0x786d37d6, 0xdfd506f1,
 110     0x8ee00973, 0x17bbde36, 0x7a670fa8, 0x5c31ab9e, 0xd4dab618, 0xcc1f52f5,
 111     0xe358eb4f, 0x19b9e343, 0x3a8d77dd, 0xcdb93da6, 0x140fd52d, 0x395412f8,
 112     0x2ba63360, 0x37e53ad0, 0x80700f1c, 0x7624ed0b, 0x703dc1ec, 0xb7366795,
 113     0xd6549d15, 0x66ce46d7, 0xd17abe76, 0xa448e0a0, 0x28f07c02, 0xc31249b7,
 114     0x6e9ed6ba, 0xeaa47f78, 0xbbcfffbd, 0xc507ca84, 0xe965f4da, 0x8e9f35da,
 115     0x6ad2aa44, 0x577452ac, 0xb5d674a7, 0x5461a46a, 0x6763152a, 0x9c12b7aa,
 116     0x12615927, 0x7b4fb118, 0xc351758d, 0x7e81687b, 0x5f52f0b3, 0x2d4254ed,
 117     0xd4c77271, 0x0431acab, 0xbef94aec, 0xfee994cd, 0x9c4d9e81, 0xed623730,
 118     0xcf8a21e8, 0x51917f0b, 0xa7a9b5d6, 0xb297adf8, 0xeed30431, 0x68cac921,
 119     0xf1b35d46, 0x7a430a36, 0x51194022, 0x9abca65e, 0x85ec70ba, 0x39aea8cc,
 120     0x737bae8b, 0x582924d5, 0x03098a5a, 0x92396b81, 0x18de2522, 0x745c1cb8,
 121     0xa1b8fe1d, 0x5db3c697, 0x29164f83, 0x97c16376, 0x8419224c, 0x21203b35,
 122     0x833ac0fe, 0xd966a19a, 0xaaf0b24f, 0x40fda998, 0xe7d52d71, 0x390896a8,
 123     0xcee6053f, 0xd0b0d300, 0xff99cbcc, 0x065e3d40
 124 ]
 125
 126 # Multiplication table for Turing using 0xd02b4367
 127
 128 _MULTAB = [
 129     0x00000000, 0xd02b4367, 0xed5686ce, 0x3d7dc5a9, 0x97ac41d1, 0x478702b6,
 130     0x7afac71f, 0xaad18478, 0x631582ef, 0xb33ec188, 0x8e430421, 0x5e684746,
 131     0xf4b9c33e, 0x24928059, 0x19ef45f0, 0xc9c40697, 0xc62a4993, 0x16010af4,
 132     0x2b7ccf5d, 0xfb578c3a, 0x51860842, 0x81ad4b25, 0xbcd08e8c, 0x6cfbcdeb,
 133     0xa53fcb7c, 0x7514881b, 0x48694db2, 0x98420ed5, 0x32938aad, 0xe2b8c9ca,
 134     0xdfc50c63, 0x0fee4f04, 0xc154926b, 0x117fd10c, 0x2c0214a5, 0xfc2957c2,
 135     0x56f8d3ba, 0x86d390dd, 0xbbae5574, 0x6b851613, 0xa2411084, 0x726a53e3,
 136     0x4f17964a, 0x9f3cd52d, 0x35ed5155, 0xe5c61232, 0xd8bbd79b, 0x089094fc,
 137     0x077edbf8, 0xd755989f, 0xea285d36, 0x3a031e51, 0x90d29a29, 0x40f9d94e,
 138     0x7d841ce7, 0xadaf5f80, 0x646b5917, 0xb4401a70, 0x893ddfd9, 0x59169cbe,
 139     0xf3c718c6, 0x23ec5ba1, 0x1e919e08, 0xcebadd6f, 0xcfa869d6, 0x1f832ab1,
 140     0x22feef18, 0xf2d5ac7f, 0x58042807, 0x882f6b60, 0xb552aec9, 0x6579edae,
 141     0xacbdeb39, 0x7c96a85e, 0x41eb6df7, 0x91c02e90, 0x3b11aae8, 0xeb3ae98f,
 142     0xd6472c26, 0x066c6f41, 0x09822045, 0xd9a96322, 0xe4d4a68b, 0x34ffe5ec,
 143     0x9e2e6194, 0x4e0522f3, 0x7378e75a, 0xa353a43d, 0x6a97a2aa, 0xbabce1cd,
 144     0x87c12464, 0x57ea6703, 0xfd3be37b, 0x2d10a01c, 0x106d65b5, 0xc04626d2,
 145     0x0efcfbbd, 0xded7b8da, 0xe3aa7d73, 0x33813e14, 0x9950ba6c, 0x497bf90b,
 146     0x74063ca2, 0xa42d7fc5, 0x6de97952, 0xbdc23a35, 0x80bfff9c, 0x5094bcfb,
 147     0xfa453883, 0x2a6e7be4, 0x1713be4d, 0xc738fd2a, 0xc8d6b22e, 0x18fdf149,
 148     0x258034e0, 0xf5ab7787, 0x5f7af3ff, 0x8f51b098, 0xb22c7531, 0x62073656,
 149     0xabc330c1, 0x7be873a6, 0x4695b60f, 0x96bef568, 0x3c6f7110, 0xec443277,
 150     0xd139f7de, 0x0112b4b9, 0xd31dd2e1, 0x03369186, 0x3e4b542f, 0xee601748,
 151     0x44b19330, 0x949ad057, 0xa9e715fe, 0x79cc5699, 0xb008500e, 0x60231369,
 152     0x5d5ed6c0, 0x8d7595a7, 0x27a411df, 0xf78f52b8, 0xcaf29711, 0x1ad9d476,
 153     0x15379b72, 0xc51cd815, 0xf8611dbc, 0x284a5edb, 0x829bdaa3, 0x52b099c4,
 154     0x6fcd5c6d, 0xbfe61f0a, 0x7622199d, 0xa6095afa, 0x9b749f53, 0x4b5fdc34,
 155     0xe18e584c, 0x31a51b2b, 0x0cd8de82, 0xdcf39de5, 0x1249408a, 0xc26203ed,
 156     0xff1fc644, 0x2f348523, 0x85e5015b, 0x55ce423c, 0x68b38795, 0xb898c4f2,
 157     0x715cc265, 0xa1778102, 0x9c0a44ab, 0x4c2107cc, 0xe6f083b4, 0x36dbc0d3,
 158     0x0ba6057a, 0xdb8d461d, 0xd4630919, 0x04484a7e, 0x39358fd7, 0xe91eccb0,
 159     0x43cf48c8, 0x93e40baf, 0xae99ce06, 0x7eb28d61, 0xb7768bf6, 0x675dc891,
 160     0x5a200d38, 0x8a0b4e5f, 0x20daca27, 0xf0f18940, 0xcd8c4ce9, 0x1da70f8e,
 161     0x1cb5bb37, 0xcc9ef850, 0xf1e33df9, 0x21c87e9e, 0x8b19fae6, 0x5b32b981,
 162     0x664f7c28, 0xb6643f4f, 0x7fa039d8, 0xaf8b7abf, 0x92f6bf16, 0x42ddfc71,
 163     0xe80c7809, 0x38273b6e, 0x055afec7, 0xd571bda0, 0xda9ff2a4, 0x0ab4b1c3,
 164     0x37c9746a, 0xe7e2370d, 0x4d33b375, 0x9d18f012, 0xa06535bb, 0x704e76dc,
 165     0xb98a704b, 0x69a1332c, 0x54dcf685, 0x84f7b5e2, 0x2e26319a, 0xfe0d72fd,
 166     0xc370b754, 0x135bf433, 0xdde1295c, 0x0dca6a3b, 0x30b7af92, 0xe09cecf5,
 167     0x4a4d688d, 0x9a662bea, 0xa71bee43, 0x7730ad24, 0xbef4abb3, 0x6edfe8d4,
 168     0x53a22d7d, 0x83896e1a, 0x2958ea62, 0xf973a905, 0xc40e6cac, 0x14252fcb,
 169     0x1bcb60cf, 0xcbe023a8, 0xf69de601, 0x26b6a566, 0x8c67211e, 0x5c4c6279,
 170     0x6131a7d0, 0xb11ae4b7, 0x78dee220, 0xa8f5a147, 0x958864ee, 0x45a32789,
 171     0xef72a3f1, 0x3f59e096, 0x0224253f, 0xd20f6658
 172 ]
 173
 174 # Basic _SBOX for Turing.
 175
 176 # This was generated by keying RC4 with the 11-character string "Alan
 177 # Turing", and then ignoring 256 generated bytes. Then the current
 178 # permutation was tested for nonlinearity, another byte generated, etc.,
 179 # until a total of 10000 bytes had been generated. The best observed min
 180 # nonlinearity was 104, which first occurred after 736 bytes had been
 181 # generated. The corresponding state table is used in Turing. By happy
 182 # coincidence it also has no fixed points (ie. _SBOX[x] != x for all x).
 183
 184 _SBOX = [
 185     0x61, 0x51, 0xeb, 0x19, 0xb9, 0x5d, 0x60, 0x38, 0x7c, 0xb2, 0x06, 0x12,
 186     0xc4, 0x5b, 0x16, 0x3b, 0x2b, 0x18, 0x83, 0xb0, 0x7f, 0x75, 0xfa, 0xa0,
 187     0xe9, 0xdd, 0x6d, 0x7a, 0x6b, 0x68, 0x2d, 0x49, 0xb5, 0x1c, 0x90, 0xf7,
 188     0xed, 0x9f, 0xe8, 0xce, 0xae, 0x77, 0xc2, 0x13, 0xfd, 0xcd, 0x3e, 0xcf,
 189     0x37, 0x6a, 0xd4, 0xdb, 0x8e, 0x65, 0x1f, 0x1a, 0x87, 0xcb, 0x40, 0x15,
 190     0x88, 0x0d, 0x35, 0xb3, 0x11, 0x0f, 0xd0, 0x30, 0x48, 0xf9, 0xa8, 0xac,
 191     0x85, 0x27, 0x0e, 0x8a, 0xe0, 0x50, 0x64, 0xa7, 0xcc, 0xe4, 0xf1, 0x98,
 192     0xff, 0xa1, 0x04, 0xda, 0xd5, 0xbc, 0x1b, 0xbb, 0xd1, 0xfe, 0x31, 0xca,
 193     0xba, 0xd9, 0x2e, 0xf3, 0x1d, 0x47, 0x4a, 0x3d, 0x71, 0x4c, 0xab, 0x7d,
 194     0x8d, 0xc7, 0x59, 0xb8, 0xc1, 0x96, 0x1e, 0xfc, 0x44, 0xc8, 0x7b, 0xdc,
 195     0x5c, 0x78, 0x2a, 0x9d, 0xa5, 0xf0, 0x73, 0x22, 0x89, 0x05, 0xf4, 0x07,
 196     0x21, 0x52, 0xa6, 0x28, 0x9a, 0x92, 0x69, 0x8f, 0xc5, 0xc3, 0xf5, 0xe1,
 197     0xde, 0xec, 0x09, 0xf2, 0xd3, 0xaf, 0x34, 0x23, 0xaa, 0xdf, 0x7e, 0x82,
 198     0x29, 0xc0, 0x24, 0x14, 0x03, 0x32, 0x4e, 0x39, 0x6f, 0xc6, 0xb1, 0x9b,
 199     0xea, 0x72, 0x79, 0x41, 0xd8, 0x26, 0x6c, 0x5e, 0x2c, 0xb4, 0xa2, 0x53,
 200     0x57, 0xe2, 0x9c, 0x86, 0x54, 0x95, 0xb6, 0x80, 0x8c, 0x36, 0x67, 0xbd,
 201     0x08, 0x93, 0x2f, 0x99, 0x5a, 0xf8, 0x3a, 0xd7, 0x56, 0x84, 0xd2, 0x01,
 202     0xf6, 0x66, 0x4d, 0x55, 0x8b, 0x0c, 0x0b, 0x46, 0xb7, 0x3c, 0x45, 0x91,
 203     0xa4, 0xe3, 0x70, 0xd6, 0xfb, 0xe6, 0x10, 0xa9, 0xc9, 0x00, 0x9e, 0xe7,
 204     0x4f, 0x76, 0x25, 0x3f, 0x5f, 0xa3, 0x33, 0x20, 0x02, 0xef, 0x62, 0x74,
 205     0xee, 0x17, 0x81, 0x42, 0x58, 0x0a, 0x4b, 0x63, 0xe5, 0xbe, 0x6e, 0xad,
 206     0xbf, 0x43, 0x94, 0x97
 207 ]
 208
 209 _MAXKEY = 32      # bytes
 210 _MAXKIV = 48      # bytes
 211 _LFSRLEN = 17     # words
 212
 213 def _getbyte(x, i):
 214     """ The ith byte of x """
 215     return (x >> (24 - 8 * i)) & 0xff
 216
 217 def _rotl(w, x):
 218     """ Rotate w left x bits """
 219     return (w << x) | (w >> (32 - x))
 220
 221 def _fixed_strans(w):
 222     """ Reversible transformation of a word, based on the S-boxes """
 223     b = _SBOX[_getbyte(w, 0)]
 224     w = ((w ^       _QBOX[b])      & 0x00ffffff) | (b << 24)
 225     b = _SBOX[_getbyte(w, 1)]
 226     w = ((w ^ _rotl(_QBOX[b], 8))  & 0xff00ffff) | (b << 16)
 227     b = _SBOX[_getbyte(w, 2)]
 228     w = ((w ^ _rotl(_QBOX[b], 16)) & 0xffff00ff) | (b << 8)
 229     b = _SBOX[_getbyte(w, 3)]
 230     w = ((w ^ _rotl(_QBOX[b], 24)) & 0xffffff00) | b
 231     return w
 232
 233 def _mixwords(w):
 234     """ Pseudo-Hadamard Transform """
 235     total = sum(w)
 236     return [(i + total) & 0xffffffff for i in w[:-1] + [0]]
 237
 238 class KeyLengthError(Exception):
 239     pass
 240
 241 class IVLengthError(Exception):
 242     pass
 243
 244 class Turing(object):
 245     def __init__(self, key=None, iv=None):
 246         self.sbox = [[], [], [], []]  # precalculated S-boxes
 247         self.index = 0
 248
 249         if key:
 250             self.setkey(key)
 251             if iv:
 252                 self.loadiv(iv)
 253
 254     def _strans(self, w, b):
 255         """ Push a word through the keyed S-boxes """
 256         return (self.sbox[0][_getbyte(w, b)] ^
 257                 self.sbox[1][_getbyte(w, (1 + b) & 3)] ^
 258                 self.sbox[2][_getbyte(w, (2 + b) & 3)] ^
 259                 self.sbox[3][_getbyte(w, (3 + b) & 3)])
 260
 261     def setkey(self, key):
 262         """ Key the cipher.
 263             Table version; gathers words, mixes them, saves them.
 264             Then compiles lookup tables for the keyed S-boxes.
 265
 266         """
 267         keylength = len(key)
 268         if keylength & 3 or keylength > _MAXKEY:
 269             raise KeyLengthError
 270         fmt = '>%dL' % (keylength / 4)
 271         self.mkey = _mixwords([_fixed_strans(n)
 272                                for n in struct.unpack(fmt, key)])
 273
 274         # build S-box lookup tables
 275         for l, m in enumerate(self.sbox):
 276             sh1 = 8 * l
 277             sh2 = 24 - sh1
 278             mask = (0xff << sh2) ^ 0xffffffff
 279             for j in xrange(256):
 280                 w = 0
 281                 k = j
 282                 for i, key in enumerate(self.mkey):
 283                     k = _SBOX[_getbyte(key, l) ^ k]
 284                     w ^= _rotl(_QBOX[k], i + sh1)
 285                 m.append( (w & mask) | (k << sh2) )
 286
 287     def loadiv(self, iv):
 288         """ Load the Initialization Vector.
 289             Actually, this fills the LFSR, with IV, key, length, and
 290             more. IV goes through the fixed S-box, key is premixed, the
 291             rest go through the keyed S-boxes.
 292
 293         """
 294         ivlength, klength = len(iv), len(self.mkey)
 295         # check args
 296         if ivlength & 3 or (ivlength + 4 * klength) > _MAXKIV:
 297             raise IVLengthError
 298         # first copy in the IV, mixing as we go
 299         fmt = '>%dL' % (ivlength / 4)
 300         lfsr = [_fixed_strans(n) for n in struct.unpack(fmt, iv)]
 301         # now continue with the premixed key
 302         lfsr.extend(self.mkey)
 303         # now the length-dependent word
 304         lfsr.append( (klength << 4) | (ivlength >> 2) | 0x01020300 )
 305         # ... and fill the rest of the register
 306         j = 0
 307         while len(lfsr) < _LFSRLEN:
 308             lfsr.append(self._strans(lfsr[j] + lfsr[-1], 0))
 309             j += 1
 310         # finally mix all the words
 311         self.lfsr = _mixwords(lfsr)
 312
 313     def _step(self, n=1):
 314         """ Step the LFSR """
 315         while n:
 316             z = self.index % _LFSRLEN
 317             self.lfsr[z] = (self.lfsr[(z + 15) % _LFSRLEN] ^
 318                             self.lfsr[(z + 4) % _LFSRLEN] ^
 319                           ((self.lfsr[z] & 0xffffff) << 8) ^
 320                    _MULTAB[(self.lfsr[z] >> 24)])
 321             self.index += 1
 322             n -= 1
 323
 324     def _round(self):
 325         """ A single round """
 326         self._step()
 327         things = _mixwords([self.lfsr[(self.index + n) % _LFSRLEN]
 328                             for n in (16, 13, 6, 1, 0)])
 329         things = _mixwords([self._strans(i, n)
 330                             for i, n in izip(things, (0, 1, 2, 3, 0))])
 331         self._step(3)
 332         things = [(i + self.lfsr[(self.index + n) % _LFSRLEN]) & 0xffffffff
 333                   for i, n in izip(things, (14, 12, 8, 1, 0))]
 334         self._step()
 335         return struct.pack('>5L', *things)
 336
 337     def gen(self, skip, length):
 338         """ Generate length characters of output, skipping the first
 339             skip characters.
 340
 341         """
 342         while skip > 20:
 343             self._step(5)
 344             skip -= 20
 345         buf = ''
 346         while len(buf) < length + skip:
 347             buf += self._round()
 348         return buf[skip:length + skip]