Cryptography-Digest Digest #578, Volume #11 Thu, 20 Apr 00 06:13:00 EDT
Contents:
Re: Key generation in smartcards (Julia Riesz)
Re: Should there be an AES for stream ciphers? (Quisquater)
Re: Inverse of Permutation polynomials (Tom St Denis)
Re: password generator (Tom St Denis)
Re: Very Large S-Boxes VLSB's (Tom St Denis)
Re: OAP-L3: Answer me these? (Tom St Denis)
Re: Why encrypt email... (Tom McCune)
Re: Just another idea... (Runu Knips)
Re: password generator (Runu Knips)
Re: ANN: Better optimized version of Serpent. (Runu Knips)
Re: AES-encryption (Runu Knips)
Re: $100 Code Challenge (Stephen Houchen)
Re: Inverse of Permutation polynomials ([EMAIL PROTECTED])
d (Gideon Samid)
Re: Inverse of Permutation polynomials ([EMAIL PROTECTED])
f (Gideon Samid)
----------------------------------------------------------------------------
From: Julia Riesz <[EMAIL PROTECTED]>
Subject: Re: Key generation in smartcards
Date: Wed, 19 Apr 2000 11:27:42 +0200
Here=B4s a method for producing a 1024 bit RSA keys that
you can break yourself, but nobody else can.
- Use a triple DES based pseudo random generator PRNG that depends on
a private key k and a 64 bit random seed s.
- Choose a random seed s, e.g. using hardware random.
- Generate a 512 bit prime p, using the PRNG
- Calculate x1 =3D s*2^(1024-64) / p and x2 =3D (s+1)*2^(1024-64) / p
- Generate a prime q between x1 and x2 using the PRNG.
- From p and q calculate the public and private key as usual. =
Now the first 64 bit of the public modulus will be the random
seed s, which you can use to reconstruct the Generation of p and q,
if you know k.
As long as the PNRG is cryptographically secure, this kind
of information leakage isn=B4t detectable.
Thus the only way to trust your smart card, is to trust
its vendor or, if the software is evaluated by a third party
(as it should be for cryptographic applications), to trust
the evaluator.
This is the reason, why I=B4d prefer a token running open source
software over a smart card for cryptographic applications such as
electronic signatures.
Marcin Jaskolski wrote:
> =
> Hi all,
> =
> I am doing some research for my Cryptography classes (I'm a computer
> science student). I'm looking for a specific methods of generating
> public keys (RSA, ElGamal), used mainly in smart cards, which allow
> the producer/someone else posessing some kind of key to break the ciphe=
r
> easily (to find the private key).
> I'm also looking for information how to find out if a given public key
> (or pair:public/private key) is weak in terms described above.
> =
> I'll be very happy if anyone can help me finding some info
> =
> Have a nice day,
> Marcin Jaskolski
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Should there be an AES for stream ciphers?
Date: Wed, 19 Apr 2000 12:07:26 +0200
See also the new European project NESSIE at
http://www.cryptonessie.org
========
Universit� de Louvain
UCL Crypto Group
see http://www.dice.ucl.ac.be/crypto or http://www.uclcrypto.org
t�l. 32.10.47.25.41 (connected to my voicebox and cellular phone)
fax: 32.2.358.55.83 (only for me)
SMS: send an email (only the subject will be transmitted) to
[EMAIL PROTECTED]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Inverse of Permutation polynomials
Date: Wed, 19 Apr 2000 10:43:05 GMT
[EMAIL PROTECTED] wrote:
>
> Reading all the messages from Tom about permutation polynomials mod
> (2^w), I couldn't help but get interested in the subject. He seemed to
> have so much fun with those polynomials. :-)
They are usefull as sboxes, but you have to rotate the output to avoid
linearity with the lower bits. :)
> Anyway, he had a question about the inverse of these polynomials. I
> suspect he doesn't need them anymore, but I've got a not-so-elegant
> solution, and I want to commit them to the net-memory before I throw
> away my notes. Who knows, someone may use them in the future.
Well you can make a very simple block cipher with it :) just do this
P(x) = p.poly
E(x) = P((P(x) <<< r1) <<< r2) ...
Where the perm poly is of a high enough degree and private.
> The first logical question to ask when trying to invert these
> polynomials is: is there an inverse permutation polynomial for all
> possible permutation polynomials. The inverse of the permutation
> polynomial is a permutation itself, so the quick (and lucky) answer is
> yes. Lucky, because although there is not a polynomial for each
> permutation, the inverse permutation of a permutation polynomial also
> satisfies the only (meaning the only one I could find) requirement P
> (x+m)=P(x)+m, for a permutation polynomial to exist.
Generally I would think if P(x) is a permutation polynomial and P'(x)
the inverse that P'(P(x)) = x is how you would start. So for the simple
quadratic you get
P'(P(x)) = P'(2x^2 + x)
= a(2x^2 + x)^2 + b(2x^2 + x)
= a(4x^4 + x^2 + 4x^3) + b(2x^2 + x)
= 4ax^4 + ax^2 + 4ax^3 + 2bx^2 + bx
= 4ax^4 + 4ax^3 + (2b + a)x^2 + bx
x + k2^w= x(4ax^3 + 4ax^2 + (2b + a)x + b)
= x(x(4ax^2 + 4ax + 2b + a) + b)
= x(x(x(4ax + 4a) + 2b + a) + b)
= x(x(x(a(4x + 4) + 2b + a) + b)
= x(x(x(a(4(x + 1) + 2b + a) + b)
= x(x(x(a(2(2(x + 1) + b) + a) + b)
...
Now just find (a, b, k) and you have an inverse right? Also not the
degree of the inverse is higher, it has upto x^4 whereas the input had
only x^2. If you look fifth line you have 4ax^4 + (2b + a)x^2, but the
quantities 4a + 2b + a have to be even. So we get 5a + 2b = z. But
then the quantity 4ax^3 (4a) must be even, simple enough it will always
be. So as long as 'z' is even and 'b' is odd we are in business.
> Now, how do we go about constructing our p.poly. inverses? More
> important, what do I mean by an inverse in the first place? The inverse
> I am going to construct is for the substitution operation. i.e. if P(Q
> (x)) == x for all 0<=x<2^w, for permutation polynomials P and Q, then P
> is the inverse of Q. P and Q normally do not commute, so it is a bit
> dangerous to say Q is also the inverse is P, but I suspect that it is,
> so I'll say it anyway. :-)
>
> In order to construct the inverses, I start with an inverse modulo 2,
> modify it to make it also an inverse modulo 2^2, and keep it modifying
> until I get the inverse modulo 2^w. So it is a w step process to
> construct the inverse.
>
> What we do is, given Qk(x) which is an inverse of P(x) mod 2^k, find a
> zero polynomial Zk(x) mod 2^k, and add it to Qk(x) so that Qk+1(x)=Qk(x)
> +Zk(x) is the inverse of P(x) mod 2^(k+1). Easy? Nope. It is usually a
> tedious process to construct these Zero polynomials, and find the right
> one. I will not go out and prove that this method will work (you can
> use the Lemmas in the Permutation Polynomials paper of Rivest to do so).
> Instead, I will explain the inversion with an example polynomial, P(x)
> =2*x^2+x mod 2^w.
>
> But before that, let me give a parametrized class of zero polynomials
> mod 2^n, which have been quite handy in the process of generating
> inverses.
> Z(x, a, n, q(x)) = q(x)*[2^(n-a)]*x*(x-1)*(x-2)*...*(x-2*a+1) = 0 mod
> (2^n).
> Why? for 0<=x<=2*a-1, Z is zero because each multiplier becomes zero at
> each x value. For 2*a-1<x, we have exactly a even terms, and a odd
> terms. The multiplication of 2^(n-a) and 2^a (coming from the even
> terms) gives us the much sought after 2^n, which is zero.
>
> OK. Back to the example:
> P(x) is our polynomial, and Qi(x) is the inverse of P(x) for modulo 2^i.
> * Since P(x) mod 2 is x, Q0(x)=x. [the only possible alternative for
> other polynomials is x+1]
> * Then P(Q1(x)) == 2*x^2+x mod (2^2), and Zi(x)=2*x=0 mod 0, so I can
> add that to Q1(x) to get Q2(x)=3*x, and
> P(Q1(x))=2*x^2+2*x+x==2*x*(x+1)+x==2*x*(x-1)+x==Z(x, 1, 2, 1)+x==x mod
> 4.
> * n=3: P(Q2(x))=2*9*x^2+3*x==2*x^2+3x=x+2*(x^2+x) mod 8. Add 2*x*(x+1)
> as the zero poly. to get Q3(x)=2*x^2+5*x
> As you gues, it gets harder, and harder to collect to terms as you
> increase the powers of 2. I calculated 2 more terms in this series to
> get:
> mod=2^4 => Q(x)=6*x^2+9*x [with Z(x)=4*x^2+4*x]
> mod=2^5 => Q(x)=14*x^2+17*x [with Z(x)=8*x^2+8*x]
>
> Well, that's all folks. If you are interested, and I messed something
> up above, just give me yell. I'll try to fix what I've got.
I don't quite get your method, but I will just read it ovr and over.
However let's try the mod 16 polynomila for the quadratic
P(x) = 2x^2 + x mod 16
Q(x) = 6x^2 + 9x mod 16
P(5) = 50 + 5 mod 16
= 55 mod 16
= 7
Q(7) = 6(49) + 9(7)
= 357 mod 16
= 5
Seems like your idea works :)
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: password generator
Date: Wed, 19 Apr 2000 10:45:02 GMT
[EMAIL PROTECTED] wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Tom St Denis wrote:
> > Got bored this afternoon so I wrote a password generator using the
> > windows timer rng idea.
> >
> > You can get the source at
> >
> > http://24.42.86.123/files/passwd.c
> >
> > The chars it outputs are a..z, A..Z, 0..9 and '{}'. So there are six
> > bits per character. For a decent password their should be at the very
> > least ten characters and more like 15 or so.
> > Tom
>
> you could put more characters(!@#%$...) in transtable[] and
> convert to char using:
> printf("%c", transtable[trng_byte() % sizeof(transtable)-1]);
Actually no I can't. if the size is not a power of two you will get a
bias towards the lower half of the symbols. Try this for a 65 symbols
for example. I would have to use seven bits, which gets you 127 % 65 =
62, which means the lower 62 symbols are more probable then the top
three.
Again I chose these chars for two reasons. Printable on almost all
computers :), and it's 64 chars, so it's 6 bits even.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Very Large S-Boxes VLSB's
Date: Wed, 19 Apr 2000 10:51:25 GMT
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> >
> > [EMAIL PROTECTED] wrote:
> > >
> > > I would like to konw, why are we still using small S-Boxes with 70's
> > > memory limitations..
> > >
> > > Has anyone designed a Block Cipher with VLSB (Very Large
> > > S-Box)...something like 128x128 -----> 1024x1024
> > >
> > > Memory is pretty cheap these days...Non Linear VLSB's would be very
> > > strong against Differential and Linear Attack....
> >
> > That's pretty silly actually. A 8x8 sbox takes 256 bytes of ram, a
> > 128x128 sbox would take 2^128 bytes of ram. Apparently your thinking
> is
> > quite flawed.
> >
> > You could built a 128x128 sbox out of some intermediate algebraic
> steps,
> > whoa, that's a block cipher... sorry.
>
> I'm not an expert on cryptography, and right now I'm struggling through
> the Schneier book, Applied Cryptography. I am however very familiar with
> various kinds of bit mangling issues. Note in the calculations I'm
> assuming a byte to be a bit octet.
That's ok, I am far from an 'expert' too. Just have fun learning :)
>
> From what I understood about the S-boxes of DES (for example), there are
> 8 S-boxes with 64 entries each (6-bit input). Since the S-boxes have
> 4-bit output it means the values inside the S-box go from 0..15 so you
> can represent this with a nibble. Thus an 8-bit number will hold two
> entries, in the upper and lower halves of the bit octet, since 4+4=8.
Actually des has 32 4x4 sboxes, the input is expanded where 2 of the 6
bits choose which of the four sboxes to use in each group. Then the
remaining 4 bits go thru a permutation (the sbox). Alot of ways to
speed DES up exist, which include pre-rotated sboxes etc... Try reading
some of the des source at the end of the book.
> Thus one S-box takes 64*4 bits of memory = 256 bits. Which is 64 bytes.
> So all 8 S-boxes will take 8 * 256 bits = 256 bytes. This is indeed what
> Schneier says on page 274.
>
> So much for that.
>
> What if we had an 128 x 128 S-box?
>
> Let's use the same reasoning.
Ok.
>
> The number of entries in the said S-box: 128 * 128 = 16384 = 2^14. (What
> is the number of output bits?) If you had 14 bits in each entry, you
> could fill the S-box with 0, 1, 2, 3, ... , 16383 in some order each
> number being in the table only once. I have a vague impression that this
> would be a permutation, perhaps? So I'll make the assumption that for an
> S-box you would want inputs to map into more than one output. So let's
> say (for the sake of argument) that each entry in the table is 13 bits
> (0..8191) instead of 14 bits.
No no no. In a mxn sbox (for m = n) there are 2^n entries. When I say
128x128 that means take 128 bits in and output 128 bits. There are
therefore 2^128 possible outputs. If for (m > n) you are doing a
compression of the input, if for (m < n) you are expanding (as in
Blowfish) the input.
> In this case the total memory requirement for ONE S-box would be 16384 *
> 13 bits = 212992 bits = 208 kb. Assume you have 8 S-boxes it would be 8
> * 212992 = 1703936 bits which is about 1.67 Mb. I think 8 S-boxes each
> mapping 14-bit inputs into 13-bit outputs would mean an 8 * 16384 bit =
> 131072 bit input block (in DES) going into the substitution operation
> (ie. into the S-boxes).
>
> But no matter how you twist the issue, I can't see where you people got
> 2^128.
Try to implement a 128x128 bit sbox :)
> Like I said, I'm not an expert but I think the original poster expressed
> a valid idea. Although it seems that Schneier mentions some extra issues
> about that on p. 349.
The 4x4 sboxes in des have 16 elements each, each taking 4 bits. There
are 32 of these so you get 32x16x4 = 2048 bits.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Answer me these?
Date: Wed, 19 Apr 2000 10:55:01 GMT
Anthony Stephen Szopa wrote:
> You don't need me for this.
>
> The software is available at http://www.ciphile.com
Arrg stop posting that address....
> A professor would give such a chore to one of his undergrad
> students. Any of you can do it. Why don't you?
Why don't you?
> As I stated before, if I give you the output of the random digit
> generator as currently implemented, tell you that the output begins
> with no rotation, that the usage is zero, that the length of the
> MixFiles is 3,628,800 arrays long, that the output begins with the
> first possible output digit (no offset), etc., basically giving you
> all but the the key itself, then you determine the array sequences,
> big deal: IT IS IMMATERIAL to the cracking of any OAP-L3 encrypted
> messages.
Yaddadaada, post a complete description of the algorithm.
Tom
------------------------------
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: Why encrypt email...
Date: Wed, 19 Apr 2000 11:27:46 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Dan Day)
wrote:
<snip>
>>There is no reason why you should not encrypt everything.
>
>Sure there is -- the fact that most of my intended recipients
>would not be able to read it!
That is why it "can't" be done, but has little to do with whether it "should"
be done.
<snip>
>It's simpler to just throw up your hands and send all but the
>most sensitive traffic (or traffic between you and your
>regular encryption-fan buddies) as plaintext.
>
>*That* is the biggest hurdle to "ubiquitous encryption".
Yes it is simpler, and so often does occur, but not necessarily the wise
thing to do.
>What's really needed for ubiquitous encryption (and what
>will probably never exist) is an email protocol that
>will TRANSPARENTLY query an intended recipient's email
>server for his public key, and then transparently either:
>
> 1. If a public key exists, encrypt the message and
> send it, and cache the public key for future
> use (tagged with a reasonable expiration date,
> *and* a way for messages sent with a cached but
> now expired public key to be auto-bounced back with
> an appropriate message), or
>
> 2. If no public key exists, prompt the sender whether
> he wants to send the message as plaintext, or
> abandon the attempt (this could be set to
> default to a desired yes/no action).
>
>And in any case, the receiving email system should
>decrypt "on-the-fly", with the recipient seeing nothing
>out of the ordinary except for a "this message was sent
>with encryption" flag on it so that he can know which
>incoming messages were potentially secure or not (similar
>to the little "lock" icon that a browser shows to indicate
>a secure web connection for the current page).
That sounds sort of like InvisiMail. I very briefly tried InvisiMail, but
quickly uninstalled it. I didn't like the lack of control (compared to PGP),
the lower level of encryption; and it does not take into account multiple
people using the same email program (my wife and I both use Pegasus, and would
never tolerate it - my use of PGP doesn't affect her).
I think what is probably needed is something of a combination of what you
describe (or InvisiMail like) for regular use, and additionally something like
PGP for real sensitive material.
Tom McCune
My PGP Page & FAQ:
http://www.McCune.cc/PGP.htm
------------------------------
Date: Wed, 19 Apr 2000 13:39:05 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Just another idea...
Runu Knips wrote:
> And the ROR and ROL could simply be stripped because they add not the
> slightest piece of security.
... that was wrong, because they depend a little bit on the
keyword. But there are only two possibilities for each input
byte therefore the improvement is not very big ...
------------------------------
Date: Wed, 19 Apr 2000 13:56:29 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: password generator
Tom St Denis wrote:
> Again I chose these chars for two reasons. Printable on almost all
> computers :), and it's 64 chars, so it's 6 bits even.
I would have prefered $ and _ instead of { and }. AFAIK there are
actually computers which can't handle { and }. Thats the reason why
ISO C introduced the trigraphs. Plus _ and $ are typical parts of
identifiers just like the rest of characters you use.
------------------------------
Date: Wed, 19 Apr 2000 14:00:41 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: ANN: Better optimized version of Serpent.
"Gisle S�lensminde" wrote:
> In article <[EMAIL PROTECTED]>, Gisle S�lensminde wrote:
> >
> >A new implementation of the Serpent AES candidate cipher written
> >is now available. This is the currently fastest available
> >implementation of Serpent, and encrypts with a speed of 32 Mbit/s
> >on a pentium pro 200. The formerly fastest algorithm encrypted
> >with a speed of 26 Mbit/s on the same computer. The implementation
> >is written in Ada.
> >
> >The improvement is based on the optimized sbox functions of
> >Dag Arne Osvik. A link to the source can be found at the Serpent
> >homepage.
> >
> >http://www.cl.cam.ac.uk/~rja14/serpent.html - serpent home page
> >http://www.ii.uib.no/~gisle/serpent.html - direct link
> >
> >Dag Arne Osvik's paper on s-box optimization presented at AES3:
> >
> >http://csrc.nist.gov/encryption/aes/round2/conf3/papers/26-daosvik.pdf
>
> I forgot to tell about the licence:
>
> The licence is the same as the GNU Ada compiler GNAT's runtime,
> which is GPL with the exception that it can be linked with commercial
> software. (See the source files for details about this)
You mean L-GPL ?
------------------------------
Date: Wed, 19 Apr 2000 14:28:45 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: AES-encryption
Tom St Denis wrote:
> [EMAIL PROTECTED] wrote:
> > And if you read what is IN HIS SITE...ITS pretty Original stuff..totally
> > outclass your school boy buggy crypto library or anything you will do in
> > the future...
A symmetric cipher which generates 64 KB/s on a PII 266, even if it
is implemented in assembly, outclasses nothing and is nothing usefull.
I want definitely faster encryption/decryption speeds than that.
And after I've seen that the slower ones of the AES candidates where
the ones which had the faults, while the fast ones succeeded, I don't
longer believe in the "but why don't you use the slower algorithm if
its more secure" argument.
A "school boy buggy cryto library" which implements many of the
wellknown algorithms in a portable way is far more usefull than a
superslow algorithm derived from DES, which is only useable from Delphi
[which I don't use anyway] and under i386-Windows (yes again with i386
I mean the architecture, not the processor) if you want to use the
assembly variant.
> Funny thing is my crypto library is not based on my own ciphers or rng's
> etc... I just put together something.
> Well I won't start a flamewar, either you like my library or you don't.
> If you are so concerned with it email me with what you think is wrong in
> it.
And IMHO the cryptobag is not buggier than any of the other free
libraries arround, especially if one remembers that its a very young
library. Okay, I didn't used it until now; I've just added it to the
other crypto libraries I've found in the net, checked a little bit
the sources and tried to compile them under Linux, but they look
really not that bad.
------------------------------
From: Stephen Houchen <[EMAIL PROTECTED]>
Subject: Re: $100 Code Challenge
Date: Wed, 19 Apr 2000 07:46:17 -0500
> >The following is a message encoded using a new routine I have designed.
> >The text is a written message in English. In order to test just how
> >strong the encryption is, I have posted it here for anyone interested
> >to try to crack it. The first person to successfully crack it will get
> >$100. Seriously, $100, no kidding.
>
> Okay, who besides me is reminded of Dr. Evil's line in Austin Powers,
> where he threatens to blow up the world unless he is paid the
> enormous sum of "one...million...dollars"?
I'm waiting for the $100 Billion Code Challenge, myself...
S
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Inverse of Permutation polynomials
Date: Wed, 19 Apr 2000 12:47:54 GMT
Oh dear! I must be getting old. Or simply stupid. Forgive the rubbish I
posted before. It was just a lucky polynomial. What I did was wrong.
OK. Let me start again. This time I'll be more careful. Promise.
The first thing I'll do is quite a no-no, but I'll do anyway. I'll
assume that inverse polynomials will commute without proof. i.e., if P
and Q are inverses of each other, then P(Q(x))==Q(P(x))==x (mod 2^w).
Let me start at step i of the process, and assume that I have:
P(Qi(x))==x mod (2^i)
In step i, if we have a look at the same polynomial, it will be:
P(Qi(x))==x+Zi(x) (2^(i+1)),
where Zi(x) can be either 0 or 2^i for different vlues of x, because
x+Zi(x)==x mod (2^i)
Zi(x)==0 mod (2^i)
from step i.
So far, so good. Now I'll do something not so obvious at the first
glance:
P(Qi(x)) - Zi(x) == x (mod 2^(i+1))
P(Qi(x)-Zi(x)) == x (mod 2^(i+1))
P(Q[i+1](x)) == x (mod 2^(i+1))
Since Zi(x) can only have the values 0 and 2^i, we can take it in P(x)
using one of the lemmas in Rivest's paper, which states that
P(x+m) == P(x) + m (mod 2*m)
In what I have done, instead of using a constant, I am using a
polynomial, Zi(x), which is 0 for some x, and m for others. So all in
all, I can move it inside P().
Now, the algorithm should be fairly obvious. Let me do the same example
to show you how fragile these polynomials can be:
P(x) = 2*x^2 + x
1. Q1(x) = x
2. P(Q1(x)) = 2*x^2 + x, Z1(x) = 2*x^2 ==> Q2(x) = -2*x^2 + x == 2*x^2+x
==> Q2(x)=2*x^2 - 2*x + 2*x + x = Z(x, 1, 2) + 3*x == 3*x (mod 2^2)
3. P(Q2(x)) = 2*9*x^2 + 3*x == 2*x^2 + 2*x + x (mod 2^3), Z2(x) = 2*x^2
+ 2*x
==> Q3(x)= -2*x^2+x == 6*x^2 + x (mod 2^3)
==> Q3(x)= 2*x^2 + 4*x^2 - 4*x + 4*x + x = Z(x, 1, 3) + 2x^2 + 5x
==> Q3(x)= 2*x^2 + 5*x [You do not need to do that, I'm just showing
the equality to show that they are the same as what we've got in the
previous post]
The good thing about this approach (apart from not being wrong like the
previous one) is that you do not need to do lots of work. You start
with Q1(x)=x or Q1(x)=x+1 for any given poly. Then substitute that one
in P in each step, and modify the Qi(x) by
Qi(x)=Q[i-1](x)-(P(Qi(x))-x)
But of course, if you do not get rid of the accumulating terms which
are zero polynomials, the order of the inverse will keep growing on you.
I hope what I said here makes more sense then what I had in the
previous one.
P.S: Anyway. Tom, I've seen your answer to my first post, but if I post
a reply from my home account it may never reach there (I've already
lost one message). So I'll wait until it appears in Deja to answer that.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Gideon Samid <[EMAIL PROTECTED]>
Subject: d
Date: Wed, 19 Apr 2000 13:18:32 GMT
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Inverse of Permutation polynomials
Date: Wed, 19 Apr 2000 13:07:33 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> > have so much fun with those polynomials. :-)
>
> They are usefull as sboxes, but you have to rotate the output to avoid
> linearity with the lower bits. :)
But somewhat slower than going out and doing your permutations by
tables, or swapping bits on some processors. :-) As this thread's
subject, they have the property of being invertible, which may be
undesirable in some situations.
> Well you can make a very simple block cipher with it :) just do this
>
> P(x) = p.poly
> E(x) = P((P(x) <<< r1) <<< r2) ...
>
> Where the perm poly is of a high enough degree and private.
Yep, but it's too much effort to find an inverse to the polynomial in
question. I guess... But thanks for not saying outright that what I've
been working on was useless. :-)
> Generally I would think if P(x) is a permutation polynomial and P'(x)
> the inverse that P'(P(x)) = x is how you would start. So for the
simple
> quadratic you get
>
> P'(P(x)) = P'(2x^2 + x)
> = a(2x^2 + x)^2 + b(2x^2 + x)
This was my first line of thought. The trouble is, you don't know that
the degree of P'(x) will be 2. As a matter of fact, The degree can be
as high as 2*w-1, if the inversion is done modulo 2^w (i do not have a
solution, but I think you can reduce the degree of all polynomials
using the zero polynomial Z(x, w, w)=x*(x-1)*...(x-2*w+1)==0 (2^w).
> = a(4x^4 + x^2 + 4x^3) + b(2x^2 + x)
> = 4ax^4 + ax^2 + 4ax^3 + 2bx^2 + bx
> = 4ax^4 + 4ax^3 + (2b + a)x^2 + bx
> x + k2^w= x(4ax^3 + 4ax^2 + (2b + a)x + b)
> = x(x(4ax^2 + 4ax + 2b + a) + b)
> = x(x(x(4ax + 4a) + 2b + a) + b)
> = x(x(x(a(4x + 4) + 2b + a) + b)
> = x(x(x(a(4(x + 1) + 2b + a) + b)
> = x(x(x(a(2(2(x + 1) + b) + a) + b)
I follow you, but x+kx^w is only a particular polynomial which is
equivlent to x. And it does not need to have any solution at all. What
you need to write on left hand side is x+Z(x), where Z(x) is a zero
polynomial mod 2^w, and there are lots of Z(x)'s that you can find, and
plug in there. So as w increases, your chances of finding one left hand
side which will provide an answer decreases (again, gut feeling coming
from past failures).
> ...
> I don't quite get your method, but I will just read it ovr and over.
> However let's try the mod 16 polynomila for the quadratic
>
> P(x) = 2x^2 + x mod 16
> Q(x) = 6x^2 + 9x mod 16
>
> P(5) = 50 + 5 mod 16
> = 55 mod 16
> = 7
>
> Q(7) = 6(49) + 9(7)
> = 357 mod 16
> = 5
>
> Seems like your idea works :)
Pure chance. First, sorry for wasting your time with incorrect
information. And secondly, sorry for not being more clear. I hope my
next post will be easier to follow. I have the disadvantage of not
having english as my native language, and sometimes what I write and
what I think I have written do not match. :-) But that's jst another
excuse. I have made the mistake of assuming others are also thinking
what I am thinking at the time I say things. My teachers kept saying
that it was one of my biggest failings.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Gideon Samid <[EMAIL PROTECTED]>
Subject: f
Date: Wed, 19 Apr 2000 13:46:45 GMT
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
