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



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.

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.
>