| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1383.1 | simple observation | CADSYS::COOPER | Topher Cooper | Thu Feb 07 1991 17:42 | 5 |
| I think I may have something on this somewhere, but I make no
guarentees. It is fairly obvious that a(0) adds nothing either
to the security or to the distribution so it may as well be 0.
Topher
|
| 1383.2 | ACM Algorithm 536 | ALLVAX::JROTH | The ships of state sail on mirage... | Thu Feb 07 1991 21:18 | 11 |
| 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
|
| 1383.3 | Did you said Fractal ? | SHIRE::ALAIND | Alain Debecker @GEO DTN 821-4912 | Fri Feb 08 1991 07:56 | 18 |
| 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
|
| 1383.4 | some counterexamples | HERON::BUCHANAN | Holdfast is the only dog, my duck. | Thu Feb 28 1991 17:18 | 72 |
| 1383.5 | | ALLVAX::JROTH | I know he moves along the piers | Fri Mar 01 1991 01:15 | 31 |
| 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
|
| 1383.6 | thanks for the Merkle, btw... | HERON::BUCHANAN | Holdfast is the only dog, my duck. | Fri Mar 01 1991 11:53 | 7 |
| > For cryptographic strength one doesn't need a bijection, especially
> if it makes it too easy to reverse the mapping.
Oh, absolutely, but the question of polynomials acting bijectively
on prime fields was an interesting issue to respond to.
Andrew.
|