Criticism of a proposed floating point (cs)prng requested.
in [Cryptography]
|
Prev: Criticism of a proposed stream cipher requested.
Next: Question about pass phrase cracking through brute force
From: Phoenix on 3 Jun 2010 14:24 The algorithm is: x_n+1 = FRAC( x_n ( x_n + b_n ) +c ) b=1,2,3 2048 c=(0;1) I ask criticism on the safety, randomness quality, speed performance, non linearity, crypto analisys, Discrete Logarithm Problem (DLP), etc. For more go to: http://www.number.com.pt/index.html Thanks
From: Maaartin on 3 Jun 2010 14:52 On Jun 3, 2:24 pm, Phoenix <ribeiroa...(a)gmail.com> wrote: > The algorithm is: > > x_n+1 = FRAC( x_n ( x_n + b_n ) +c ) > > b=1,2,3 2048 > c=(0;1) You define b=1,2,3 2048 and don't use it. You use b_n and don't define it. > I ask criticism on the safety, randomness quality, speed performance, > non linearity, crypto > analisys, Discrete Logarithm Problem (DLP), etc. > > For more go to:http://www.number.com.pt/index.html > > Thanks You wrote: + Simple and elegant, tiny and fast this algorithm offers no difficulties on + portability/implementation, in any system/platform or programming language. but it's not true at all: 1. It's compiler and system dependent: A C compiler may choose to use 80-bit representation for doubles as long as they stays in registers (this additional precision is for free), or not. 2. There are many important systems lacking floating point at all or using some strange sizes, e.g., 24 bits on some DSPs.
From: Mok-Kong Shen on 3 Jun 2010 15:38 Phoenix wrote: > x_n+1 = FRAC( x_n ( x_n + b_n ) +c ) > > b=1,2,3�2048 > c=(0;1) Do you intend to generate only 2048 values of x_i? One general problem of working in R is that with different hardware one may get different results due to different register sizes and eventually also the rounding methods, I am afraid. (Of course, partners may agree to use only compatible hardware.) M. K. Shen
From: Scott Fluhrer on 3 Jun 2010 15:52 "Phoenix" <ribeiroalvo(a)gmail.com> wrote in message news:23356e75-4613-43e2-8dc1-21531ba0e0e8(a)c33g2000yqm.googlegroups.com... > The algorithm is: > > x_n+1 = FRAC( x_n ( x_n + b_n ) +c ) > > b=1,2,3�2048 > c=(0;1) > > I ask criticism on the safety, randomness quality, speed performance, > non linearity, crypto > analisys, Discrete Logarithm Problem (DLP), etc. Unless I'm missing something, the attacker knows (or at least, can guess) the value b_n. From that, if we knows two adjacent output values (x_n and x_n+1), then he can compute: c = FRAC( x_n (x_n + b_n) - x_n+1 ) That lets him compute any later values of the sequence. In addition, Maaartin's comments on the portability of different floating point representations (even assuming IEEE 754 floating point) is quite accurate; an implementation that leaves everything in a long-double precision will have a different output than one that drops to a single precision somewhere during the algorithm. -- poncho
From: Phoenix on 3 Jun 2010 16:52
On 3 Jun, 18:52, Maaartin <grajc...(a)seznam.cz> wrote: > You define b=1,2,3 2048 and don't use it. You use b_n and don't define > it. b is a loop from 1 to 2048 integers. > + Simple and elegant, tiny and fast this algorithm offers no > difficulties on > + portability/implementation, in any system/platform or programming > language. > but it's not true at all: No, is very true. You only needs to define an acurate protocol i.e IEEE 754. I tested with some different machines, OS and compilers, and do not find any problem. > 2. There are many important systems lacking floating point at all or > using some strange sizes, e.g., 24 bits on some DSPs. This is the same problem with other algorithms wend we need to scale the integers to fp. M. K. Shen >Do you intend to generate only 2048 values of x_i? No. The algo can generate pseudo-random numbers with big values for n. >One general problem of working in R is that with different hardware one may get >different results due to different register sizes and eventually >also the rounding methods, I am afraid. (Of course, partners may >agree to use only compatible hardware.) Work with fp today, is more accurate and fast, then in the past. Poncho >Unless I'm missing something, the attacker knows (or at least, can guess) >the value b_n. From that, if we knows two adjacent output values (x_n and >x_n+1), then he can compute: c = FRAC( x_n (x_n + b_n) - x_n+1 ) No. Maybe you can compute: c= x_n (x_n + b_n ) - x_n+1 ) but not c = FRAC( x_n (x_n + b_n) - x_n+1 ) And another thing, the algorithm is combined with XOR in a stream cipher way, to encrypt/decrypt as explained in the page. |