| See
H. D. Knoble, C. Forney, F. S. Bader
"An efficient one-way enciphering algorithm",
ACM TOMS Vol 5 No. 1, March 1979 pp 97-107
This is the same type of hash function used by the VMS password
checker. Algorithm 536 is available from NETLIB, in FORTRAN
which you can use as a basis. The VMS HPWD routine is in assembler.
- Jim
|
| Christian,
If n=1 and a(1) prime with p, i.e. not a multiple of p, then f is
one to one.
If n=2 and f(x) = x^2 + ax + b, then f(x)=f(y) iff x=y or x+y+a=0 [mod p].
Thus, there is allway two possible sources for the same enciphered message.
For higher values of n the situation become even worse.
If fact, when iterated, that non reversibility is the foundation of chaos.
What you are looking for is the fractal dimension of the image of f(x).
This should open the door to ample documentation.
About enchiphering/dechiphering algorithm, I know that Patrick Hudelot
worked on the subject. He is based in FYO, and has an added-value: he
speaks French.
Alain
|
| Contrary to .3, polynomials of degree > 1 *can* be bijective from
Z_p to Z_p. It is true that quadratics cannot be bijective, for p > 2,
but this behaviour does not extend to higher powers.
Remark: In producing a canonical set of polynomials of degree n to explore
over a field Z_p, it has been said that we can assume the poly is monic, and
has no constant term. We can also use a Tschirnhaus transformation to remove
the term of order n-1, in the obvious way that one standardly uses to solve
quadratic equations. We exploit this in the following.
Remark: We can always assume that p > n, since x^p = x.
Example 1: exponentiation
For instance f(x) = x^k mod p, where gcd(k,p-1) = 1, will
certainly do the trick. This will be the Frobenius map when k = p, which
in this case is the identity. But when k coprime to (p-1) can be selected
such that 1 < k < p-1, then the map is a non-trivial automorphism.
Instance: p = 5. f(x) = x^3 maps [0,1,2,3,4] to [0,1,3,2,4]
Example 2: cubic functions
Suppose that we are dealing with a cubic polynomial, of general form:
f(x) = x^3 + a*x
Note: a <> 0, since we have already covered a = 0 above. This means
we do not need to consider the case where f(x) has a triple root.
then f(x) = y(x) when (x=y or):
x� + xy + y� + a == 0 (mod p)
=> y� + xy + x�+a == 0 (mod p)
=> y == [ -x � sqrt( x� - 4(x�+a) ) ] / 2 (mod p)
=> y == [-x � sqrt(- 3x� - a) ] / 2 (mod p)
Now, for f to be a bijection, we require that for all x:
-3x�-a is not a square mod p
Now there are (p+1)/2 numbers which will be of the form -3x�-a. But
only (p-1)/2 are non-squares. So at least one of the numbers -3x�-a (we
don't know which) *is* a square. Therefore there is no canonical cubic
except x� itself (and then only when p == 2 mod 3) which induces a bijection.
Example 3: quartics
Canonical form:
f(x) = x^4 + ax� + bx
Instance: p = 7. f(x) = x^4 + 3x maps [0,1,2,3,4,5,6]
to [0,4,1,6,2,3,5]
When I try to solve the general quartic, in the way that I solved
the general cubic, I find that my expressions become rapidly more
complicated than I started with. This is not the way forwards, I figure!
This problem reminds me of the Ceboratov/Kummer analysis refered to by
the ubiquitous usenetter and fellow French resident F.Morain in 881.x. Does
anyone know more about or have references for these techniques, or should
I mail him?
Regards,
Andrew.
|
| For cryptographic strength one doesn't need a bijection, especially
if it makes it too easy to reverse the mapping.
Instead one needs low degeneracy, so that the search space for
either brute force factorization or more number-theoretic techniques
will not be practical.
For example, an n-th degree polynomial modulo a prime will have
n roots. If we choose our prime p large enough (say, a little less
than a quadword), and n large but << p (say, near 2^24),
then it is impractical to search blindly but also the great number of
factorizations makes it impractical to use a number theoretical tricks.
The polynomial used by VMS is of the form
n0 n1 3 2
x + cn1 x + c3 x + c2 x + c1 x + c0 MOD 2^64-59
n0 = 2^24 - 3, n1 = 2^24 - 63, the constants are large primes a little
less than 2^64.
The netlib version uses a larger prime, near 2^72.
There are other kinds of one-way hash functions that are useful such
as Merkle's Khufu, Khafre, and Snefru functions (named after Egyptian
Pharoahs it seems.)
It is not too important if it takes time to evaluate this high degree
polynomial - in fact it's a selling point.
- Jim
|