[128487] in cryptography@c2.net mail archive
Looking through a modulo operation
daemon@ATHENA.MIT.EDU (Florian Weimer)
Sun Jul 20 14:16:24 2008
From: Florian Weimer <fw@deneb.enyo.de>
To: cryptography@metzdowd.com
Date: Sun, 20 Jul 2008 12:50:47 +0200
I've got a function f : S -> X x S where S = (Z/2Z)**96 and
X = (Z/2Z)**32. Suppose that s_0 is fixed and (x_i, s_i) = f(s_{i-1}).
(f implements a PRNG. The s_i are subsequent internal states and the
x_i are results.)
Now f happens to be linear. I know the values of x_i, x_{i+1}, ...,
x_{i+k} module N, for a fixed, known N. N is odd (but divisible by 9).
Is it possible to recover s_i with reasonable effort (better than brute
force, and k should be in the hundreds, not thousands)? And if yes, how?
Prediction of candidates for x_{i+k+1} with high probability would be
helpful, too.
(Obviously, using f as an unpredictable PRNG is not a good idea. But if
there's a real attack I can present, convincing the authors to replace
it would be so much easier.)
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
