Re: More about MT19937 in crypto
From: Rob Warnock (rpw3@rpw3.org)
Date: 03/03/03
- Previous message: jim steuert: "Re: A public key authentication scheme based only on hash functions"
- In reply to: Benjamin Goldberg: "Re: More about MT19937 in crypto"
- Next in thread: Gregory G Rose: "Re: More about MT19937 in crypto"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
From: rpw3@rpw3.org (Rob Warnock) Date: Sun, 02 Mar 2003 22:55:00 -0600
Benjamin Goldberg <goldbb2@earthlink.net> wrote:
+---------------
| 2/ The time it takes to generate a bit of keystream should be O(N)
| with respect to the size of the state, though logarithmic or constant
| time would be better. In hardware, LFSRs (and MLS) operate in constant
| time wrt the size of the state.
+---------------
Close, but not quite. Having done some of this in the past, I know
that when you start doing stuff like CRC-32 "word at a time", you
end up dealing with XOR chains complex enough that you do have to
worry about propagation delays. But it's still not very bad, O(log N)
in fact, usually with fairly small constants.
In the case of CRCs (a specific subset, to be sure) of degree N+1,
one way to view the "shift left one" operation (other than the usual
shift-register view) is as a matrix multiplication of the current
N-bit CRC state by a constant "step once" NxN matrix, constructed
with a first row containing the low N bits of the generator polynomial
(with a 1 in every position that needs to be XOR'd to produce the
new bit to be shifted in) and the remaining rows containing single
off-diagonal 1's that perform simply a "shift" operation.
While excessively complex for describing the "shift one" case, this
representation has the advantage that successive powers of the matrix
correctly represent multiple shifts, so that the M^8 matrix can be used
for updating the CRC register for "byte at a time" CRCs, and so on.
That is, CRC' = M^8 * (CRC xor data), "data" 0-padded to N bits.
[This is also indirectly the basis of the common software "byte
at a time" CRC routines that use a 256-word lookup table.]
This straightforwardly extends to CRC'ing data N bits at a time,
giving CRC' = M^N * (CRC xor data) for inputs of N-bit data words.
Now when you get up to this many bits at a time, I have observed
[disclaimer: no proof] that "good" CRCs, like good hashes or crypto,
tend to change about half the output bits for any input bit change,
so that as you take higher & higher powers of M, the huge mess of
resulting XOR gates you end up with (1's in the matrix) tends to
converge close to (N^2)/2, with about N/2 input bits contributing
to each output bit (that is, a "fan-in" of ~N/2 per XOR). Done with
2-input XOR gates hooked together in the naive way, such chains take
lg(N/2) gate delays to propagate from the outputs of the CRC register
through the M^N matrix back to the input of the the CRC register again.
[Well, it's actually lg(N/2 + 1), since you always have to XOR in the
new input data, but you get the drift.]
For large N, some time may be saved by used chains of small lookup
tables (tiny ROMs, as it were) to provide more than 2 inputs per XOR
(and this is how it's sometimes done in FPGAs). But that just changes
the base of the logarithm, not the fact that it's O(log N).
-Rob
-----
Rob Warnock, PP-ASEL-IA <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
- Next message: Thinh Tran: "Re: FTL Quantum Comm. via 2-photon Interference?"
- Previous message: jim steuert: "Re: A public key authentication scheme based only on hash functions"
- In reply to: Benjamin Goldberg: "Re: More about MT19937 in crypto"
- Next in thread: Gregory G Rose: "Re: More about MT19937 in crypto"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
