1996-12-11 - Re: Ignoramus Chewed-Off on IPG algorithm

Header Data

From: ichudov@algebra.com (Igor Chudov @ home)
To: wichita@cyberstation.net
Message Hash: 4b8e0122286c0e96cf5b751073a6cec7881cf7e84dba318b3efcdd9693808125
Message ID: <199612111543.JAA00732@manifold.algebra.com>
Reply To: <Pine.BSI.3.95.961211042446.5247B-100000@citrine.cyberstation.net>
UTC Datetime: 1996-12-11 15:46:56 UTC
Raw Date: Wed, 11 Dec 1996 07:46:56 -0800 (PST)

Raw message

From: ichudov@algebra.com (Igor Chudov @ home)
Date: Wed, 11 Dec 1996 07:46:56 -0800 (PST)
To: wichita@cyberstation.net
Subject: Re: Ignoramus Chewed-Off on IPG algorithm
In-Reply-To: <Pine.BSI.3.95.961211042446.5247B-100000@citrine.cyberstation.net>
Message-ID: <199612111543.JAA00732@manifold.algebra.com>
MIME-Version: 1.0
Content-Type: text


wichita@cyberstation.net wrote:
> 
> 
> Igor,
> 
> I greatly appreciate the fact that you are looking at the algorithm.
> You have the general idea but I do not believe that you have spent
> enough time with it to understand what all is going on.
> 
> 
> For instance, be advised that all Bs and Cs are not random numbers 
> at all, but rather they are randomly selected from a previously selected
> set of values, so that there are no repeats and all Bs are less than the
> smallest possible C, and the sum of B plus C is always < 32761.
> Furthermore, either B or C, one and sometimes both, are prime numbers.

See my another reply, your requirements to A, B, and C above are not
good to produce "good numbers".

If C is 2*B and B is prime as you require, the only output from the
triplet you will see is two numbers.

igor

> You might have an A(i) value of zero, and will have it 1 in C(i)
> iterations, but you can never have a b value of 0, or a C values or zero.
> Nor can any set of:
> 
>           A(JV)=A(JV)+B(JV) MOD C(JV)
> 
> generate a partial set set of the possible C values because either the B
> value or the C value is prime. 
> 
> 
> Furthermore, initial A values are chosen so that A+ Bmax + Cmax is less
> than 32761.
> 
> Accordingly the circumstances that you describe cannot occur. The
> randomness referred to in the As, Bs, and Cs, result from the selection
> process, not from the values themselves. It goes without saying that
> using random values would not work, for the reason that you mention
> plus other. 
> 
> For instance, there are no repeats between any of the As, Bs, and Cs which
> is one indication that they are not random. To the contrary, the pool of
> numbers are selected numbers, approximately 66% prime and 33% nonprime,
> which maximizes the covariance, in a LP sense, with the modulos 4096 and
> 256.
> 
> The selection process uses a key, generated by the user from the timing of
> keystrokes, to select the which As, Bs and Cs will actually be used. I
> tried to explain this in the detailed algorithm explanation. at the web
> site.
> 
>  	
> 
> 
> On Sat, 30 Nov 1996, Igor Chudov @ home wrote:
> 
> > Igor Chudov @ home wrote:
> > > 
> > > Hi,
> > > 
> > > I was sort of tired of endless talk that "IPG algorithm was not 
> > > peer-reviewed, blah blah blah, so we won't even look at it, 
> > > blah blah blah", and decided to look at what Don Wood writes and
> > > try to see how his program actually works. 
> > > 
> > > Of course, I am not an expert in cryptography, and will appreciate all
> > > corrections. The web page to look at is http://www.netprivacy.com/algo.html,
> > > and it describes IPG algorithm in some detail.
> > > 
> > > First of all, the description of the algorithm is extremely unclear. I
> > > understand that this may be Don Wood's writing style, but it is certainly 
> > > not the most efficient style for precise communications. I suggest that
> > > Don tries to rewrite his description to be more structured.
> > > 
> > > Second, I seriously suspect that his algorithm of "trimming" is NOT
> > > going to work right. Just to remind everyone, he generates pseudo-random
> > > A(JV), B(JV), C(JV) such that
> > > 
> > > 	16384 <  C < 20361
> > > 	         B < 12227
> > > 	A arbitrary (at least the web page contains no restrictions 
> > > 	  on the value of A).
> > > 
> > > and then goes on to "trimming" -- a process that obtains a new value
> > > of A that is LESS than 16384 through this algorithm: 
> > > 
> > >        DO
> > >          JV=JV+1
> > >          IF JV=53 THEN JV=0
> > >          A(JV)=(A(JV)+B(JV)) MOD C(JV)
> > >        UNTIL A(JV)<16384
> > > 
> > > We shall first note that THERE ARE CASES WHEN THIS ALGORITHM WILL NEVER
> > > STOP! For example, if all A values are _initially_ 16385 and all C
> > > values are 16386 and all B's are 0, it is obvious that the pseudocode 
> > > above will be stuck in endless loop.
> > > 
> > > No good for IPG algorithm.
> > > 
> > > in fact, if only some triplets of A, B, and C have B == 0 and 16384 < A < C,
> > > these triplets will always be ignored (skipped) by his trimming process.
> > 
> > Note also that if B(K) == 1, his algorithm will need to make C passes
> > through the loop for JV == k, in order to generate a new value of A(JV).
> > 
> > This is very inefficient and results in a bias for triplets with high
> > Bs -- because they will generate good A(JV) more frequently.
> > 
> > 	- Igor.
> > 
> 



	- Igor.





Thread