From: ichudov@algebra.com (Igor Chudov @ home)
Date: Sat, 30 Nov 1996 10:25:50 -0800 (PST)
To: ichudov@algebra.com
Subject: Re: Ignoramus Chewed-Off on IPG algorithm
In-Reply-To: <no.id>
Message-ID: <199611301803.MAA13859@manifold.algebra.com>
MIME-Version: 1.0
Content-Type: text


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.