From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Tue, 19 Oct 93 21:22:30 PDT
To: cypherpunks@toad.com
Subject: Re: crypto technique
In-Reply-To: <9310181535.AA27722@great-gray.owlnet.rice.edu>
Message-ID: <sgl=lQO00VpQAcdXEw@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


Karl Lui Barrus wrote:

> We know the magnitude of the constants must be less than P, which is
> public.  But can they be negative - will the decoding process still
> work?  Or, will you obtain the correct decoding for the correct choice
> and an incorrect decoding for the incorrect choice?  If it turns out
> that either choice will decode a number to the same value, or if the
> decoding won't work with negative numbers, then this method is too
> easy to invert.
>
> If the constants can't be negative, or if they can be but it doesn't
> make a difference in the decoding, then taking the modulus doesn't
> obscure anything at all.

Moduli are always positive.

It is interesting to note that since x^2 mod y = (-x)^2 mod y, then
x^2 mod y = (y-x)^2 mod y.  So whenever you have a square root modulus,
you have at least two numbers in the domain which will produce the same
outcome.