Prev: Is encrypting twice much more secure?
Next: Basics of encrypting
From: me13013 on 15 Jan 2010 08:44
On Jan 14, 10:34 pm, me13013 <me13...(a)gmail.com> wrote:
> On Jan 14, 6:46 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
>
> > O.k., but even a special more or less large class of H(x) for modulus
> > not a power of 2 could be interesing.
>
> I think results exist in the literature for polynomials modulo p, with
> p prime (but dammit don't ask me to find them).

The following is not from the literature, but was derived by using a
simple program to test all polynomials of a certain form and report
those that are permutations. Then I did a little human pattern
recognition.

Modulo 23, P(x) = x^5 + ux^3 + (14u^2)x is a permutation, for any a.
Modulo 17, P(x) = x^5 + ux^3 + (7u^2)x is a permutation, for any a.
Modulo 13, P(x) = x^5 + ux^3 + (8u^2)x is a permutation, for any a.
Modulo 7, P(x) = x^5 + ux^3 + (2u^2)x is a permutation, for any a.

I don't know why those are invertible.

Looking further at the mod 23 case. Obviously w*P(x+k) will also be a
permutation (as long as u is non-zero); those have the form
w x^5 + (w(5k)) x^4 + (w(10k^2+u)) x^3 + (w(10k^3+3ku)) x^2 + (w
(5k^4+3k^2u+14u^2)) x + f
where f is anything.

Equating that to ax^5 + bx^4 + cx^3 + dx^2 + ex + f, you could
probably come up with some criteria for invertibility (keeping in mind
that I haven't necessarily produced every permutation). For example,
k = b/5a (where division means multiplying by the inverse, mod 23).
Knowing that, I can probably figure out w and u from c and d (not
sure, I haven't tried it). That would mean that for any a,b,c,d, the
value of e is fixed.

Bob H


From: me13013 on 15 Jan 2010 09:31
On Jan 15, 8:44 am, me13013 <me13...(a)gmail.com> wrote:
> ... Knowing that, I can probably figure out w and u from c and d ...

Oops, w is already known (w=a). So u = (c/w)-(10k^2). Plugging in
the expressions for k,w,u in terms of a,b,c will give us criteria that
d and e must satisfy.

Bob H

From: WTShaw on 18 Jan 2010 14:43
On Jan 14, 6:02 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> me13013 wrote:
> > The document I have is V. Anashin, "Uniformly distrbuted sequences of
> > p-adic integers, II".  Note the "II".  Apparently it is a follow up to
> > your reference [3].  Originally in Russian, translated to English in
> > Discrete Math. Appl. vol. 12 (2002), no. 6, pp. 527–590. English
> > version available athttp://arxiv.org/abs/math/0209407.  In my copy
> > of it, there is a monstrous-looking function at the bottom of page 3,
> > involving logical AND, OR, XOR, division, and exponentiation with the
> > exponent being a function of x.  The claim is made that using this
> > function in a certain way produces a complete cycle.  Possibly this is
> > just a red herring and the monster is identical to a function with a
> > simpler description.
>
> > I still think if you worked through my earlier example it would do you
> > know harm.
>
> Certainly I'll try to capture your idea, but, since my math knowledge is
> very poor and you are the inventor of your techniques, you certainly
> have a much much higher chance of arriving at useful results. I like
> to say that in my view what one needs in practice (here for crypto)
> is what one can actually use in practice. Otherwise sophisticated math
> by itself may be valuable for math but means little for the practice
> in other braches of sciences. So if you could achieve a good result in
> the present context, that would be really great in my view.
>
> M. K. Shen

My efforts in these areas are from the functional crypto vantage
point, if it does not work in practice or has poor qualities, grade it
so and look for exceptions and better numbers that might be
realistically used with some advantages over the binaries and there
harmonic related forms.

All series follow four rules, either they almost overflow as they head
toward the top of allowed values, underflow as they head toward the
bottom of allowed values, present a series that is terminated in a
vortex of limited values, or simply are a repeating series. In
working with the latter, the qualities of series are of three types,
there is one series of all values, there are several equal length
exclusive series of many values, and there are different series of
several lengths which might include singleton series of length equals
one.

The length of a specific permutation, base, is significant in
determining the nature of series involved. Of course, the amount of
temporary content used in the series progression formula also is
important in that it should be adaptable to some useful cryptographic
purpose.

Some bases have surprises of a nature that are best empirically found
as the mathematical formulae seem generally underdeveloped in that
area having being concentrated on binary approaches which are too
limited to have serious applications in higher and inclusive of more
promising bases.
From: me13013 on 18 Jan 2010 18:40
Mok-Kong Shen wrote:
>> O.k., but even a special more or less large class of H(x) for modulus
>> not a power of 2 could be interesing.
and I replied:
> I think results exist in the literature for polynomials modulo p, with
> p prime.

Searching for "permutation polynomial" at google scholar produces a
wealth of literature about polynomials that are permutations. You'd
have to dig into those to see what they say about cycle lengths. The
most promising would probably be the ones by authors that publish
articles about coding theory.

Later I added:
> Modulo 23, P(x) = x^5 + ux^3 + (14u^2)x is a permutation, for any a.
> Modulo 17, P(x) = x^5 + ux^3 + (7u^2)x is a permutation, for any a.
> Modulo 13, P(x) = x^5 + ux^3 + (8u^2)x is a permutation, for any a.
> Modulo 7,   P(x) = x^5 + ux^3 + (2u^2)x is a permutation, for any a.
>
> I don't know why those are invertible.

Without too much googling, I found an established principal that
predicts those. See the wiki page for Dickson Polynomial. Each of
the polynomials above is the Dickson Polynomial D_5(x,-u/5), (where u/
5 is the number which, when multiplied by 5, produces u). Applying
the info near the bottom of the wiki page we discover that D_5(x,a)
(for any a) will be a permutation whenever our modulus is a prime
ending in 3 or 7.

To get a "special more or less large class of H(x) for modulus" 23,
it's pretty easy to expand the invertible quintics into the class of
all invertible mod-23 quintics. And from there (with the aid of a
package like Mathematica to do the grunt work) you could find the form
of a class of single cycle polynomials. The degree of most of these
will be pretty high, but no more than 22 (because of the x^23=x
reduction).

Or you can write a brute-force search to find, say, all full-cycle
quintics, and then see if you notice any patterns in the coefficients.

Bob H

From: Mok-Kong Shen on 19 Jan 2010 07:57
Am 19.01.2010 00:40, schrieb me13013:
> Mok-Kong Shen wrote:
>>> O.k., but even a special more or less large class of H(x) for modulus
>>> not a power of 2 could be interesing.
> and I replied:
>> I think results exist in the literature for polynomials modulo p, with
>> p prime.
>
> Searching for "permutation polynomial" at google scholar produces a
> wealth of literature about polynomials that are permutations. You'd
> have to dig into those to see what they say about cycle lengths. The
> most promising would probably be the ones by authors that publish
> articles about coding theory.
>
> Later I added:
>> Modulo 23, P(x) = x^5 + ux^3 + (14u^2)x is a permutation, for any a.
>> Modulo 17, P(x) = x^5 + ux^3 + (7u^2)x is a permutation, for any a.
>> Modulo 13, P(x) = x^5 + ux^3 + (8u^2)x is a permutation, for any a.
>> Modulo 7, P(x) = x^5 + ux^3 + (2u^2)x is a permutation, for any a.
>>
>> I don't know why those are invertible.
>
> Without too much googling, I found an established principal that
> predicts those. See the wiki page for Dickson Polynomial. Each of
> the polynomials above is the Dickson Polynomial D_5(x,-u/5), (where u/
> 5 is the number which, when multiplied by 5, produces u). Applying
> the info near the bottom of the wiki page we discover that D_5(x,a)
> (for any a) will be a permutation whenever our modulus is a prime
> ending in 3 or 7.

As said, I am afraid that my math knowledge is much much too weak to
be able to go far in direction of the goal you intend to achieve. But
just to indicate that I had not simply closed my eyes to what you
wrote, I have searched for a time in libraries accessible to me and
found the following article which incidentally also involves Dickson
polynomials. However, the article is too advanced for me to study
(anyway within affordable time for aquiring at first the background
knowledge necessary, since I, as you would certainly understaqnd, have
also many other tasks, scientific or non-scientific, with the latter
unfortunately predominating, to do on my priority queque). But the
reference might be of some interest to you:

R. Lidl, W. B. M�ller, Permutation Polynomials in RSA-Cryptosystems,
in D. Chaum (ed.) Advances in Cryptology, Proc. Crypto 83, Plenum
Press, 1983, p.293-301.

> To get a "special more or less large class of H(x) for modulus" 23,
> it's pretty easy to expand the invertible quintics into the class of
> all invertible mod-23 quintics. And from there (with the aid of a
> package like Mathematica to do the grunt work) you could find the form
> of a class of single cycle polynomials. The degree of most of these
> will be pretty high, but no more than 22 (because of the x^23=x
> reduction).

Excuse me that I have got somewhat lost. In the quote of you in the
above, what is 'a' in the phrase 'for any a'? Shouldn't that be
u and u can be any integer?

BTW, 'invertible' means only that the function is bijective. It is
an another (essential in practice) question whether 'computing' the
inverse is easy, which is a point that seems to have got some
considerations in the paper cited above.

> Or you can write a brute-force search to find, say, all full-cycle
> quintics, and then see if you notice any patterns in the coefficients.

I rather doubt that brute-force search is a fruitful way in the
present context, excepting its providing some meterials for eventually
aiding theoretical work, for the work would apparently be huge for
moduli that are of some interest for practical applications, I would
surmise.

BTW, as I indicated previously, it is my humble, maybe very incorrect,
impression that the materials you provided hithertofore are all
rather 'heuristic' in nature and one could hardly somehow attempt
to derive from them an efficient (not brute-force) procedure/algorithm
to automatically (with a computer program) obtain an H(x) desired. But I
can err, certainly.

Thanks.

M. K. Shen

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: Is encrypting twice much more secure?
Next: Basics of encrypting