Prev: Is encrypting twice much more secure?
Next: Basics of encrypting
From: Mok-Kong Shen on 14 Jan 2010 19:02
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 at http://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
From: me13013 on 14 Jan 2010 19:43
On Jan 14, 7:02 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> me13013 wrote:
> > 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.

From the posts I've seen, I think you have the math knowledge
necessary to work through the example.

What I described in my earlier posts is not rocket science. I am not
in the same league as Rivest, Knuth, or Anashin.

Bob H
From: Maaartin on 14 Jan 2010 20:35
On Jan 15, 12:41 am, me13013 <me13...(a)gmail.com> wrote:
> On Jan 14, 6:20 pm, me13013 <me13...(a)gmail.com> wrote:
>
> > On Jan 14, 5:58 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> > > I am not aware of Anashin's work on non-polynomial permuations. If you
> > > have references, I should be very grateful to know them.
>
> > I will look for them.  I'm pretty sure that whatever I found was the
> > result of something posted in this newsgroup, but it was probably 5 to
> > 10 years ago.
>
> 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.

In general most probably not, as you can't IMHO simplify it for
integers (e.g., because the exponentiation grows faster than any
polynomial). It can be trivially simplified for Z/2, it's easy for any
small power of 2, and I think it's possible for every k, but not in
general.

The claim is that using any such function of a given form (even such a
monster) produces a complete cycle. This is a nice and general claim.

> I still think if you worked through my earlier example it would do you
> know harm.

So do I, he should try a bit harder. I enjoyed reading your
explanation.
From: me13013 on 14 Jan 2010 21:52
On Jan 14, 8:35 pm, Maaartin <grajc...(a)seznam.cz> wrote:
> On Jan 15, 12:41 am, me13013 <me13...(a)gmail.com> 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.

Let's call that reference [5].

> > 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.
>
> In general most probably not, as you can't  IMHO simplify it for
> integers (e.g., because the exponentiation grows faster than any
> polynomial). It can be trivially simplified for Z/2, it's easy for any
> small power of 2, and I think it's possible for every k, but not in
> general.
>
> The claim is that using any such function of a given form (even such a
> monster) produces a complete cycle. This is a nice and general claim.

For what I say in the next paragraph, possibly I am confusing [5] with
some other paper. Looking at the other stuff in the same directory
where I uncovered [5], it looks like I was briefly exploring T-
functions in the latter part of 2005, possibly for a presentation for
a crypto read group that never took place (that read group dissolved
after about 4 presentations). Was there some discussion of T-
functions in this group back in 2005?

Anyway, if I am remembering correctly, I think all the functions
discussed in [5] were such that if they produced a full cycle mod 2^w,
then they also produced a full cycle modulo all smaller powers of 2.
The same is true for the polynomial generators M-KS attributes to
reference [4]. So they're lacking any mixing from high bits to low,
and represent only a very small subset of all possible full-cycle
permutations. That's not to say they're worthless (they aren't!), but
the result is not as general as one might hope for.

Bob H
From: me13013 on 14 Jan 2010 22:34
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).

> ... for modulus not a power of 2, one needs also a method to get a P(x)
> to start with, right?

For prime modulus "seed" permutations are pretty easy to find. For
example, P(x) = x^7 mod 23 (ask yourself why that's invertible, and
why it is easy to find k s.t. x^k is invertible). And by composing
two permutations I can get others. E.g. Q(x) = P(x+u)+v must be a
permutation for any u and v (ask yourself why). And then I can
compose those with each other, and so on. You might to try figure out
which three easy-to-prove-invertible mod 23 polynomials I combined to
produce the permutation R(x) = x^21 + 7x^18 + 21x^15 + 12x^12 + 12x^9
+ 21x^6 + 7x^3 + 1, the table for which is

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22
R(x) 1 13 4 17 15 7 14 22 5 20 16 10 8 9 12 6 2 11 19 3 21
18 0

It turns out R is full-cycle, but that was a lucky accident
(seriously). That doesn't change the fact that H(x)=R(R'(x)+1) would
also be full-cycle.

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