ok - I just read part of the paper. I'm not a cryptographer but I am a
mathemetician and here are some trivial conclusions.
the algorithm is looking for a number: N where N=p*q for two primes p and
q of relatively the same size.
If you look at the _original_ equations developed by Pohlig-Hellman what
you have for the encryption operation is simply this:
C = M^e mod p for some message M and exponent e and _relatively large_
prime number p.
Now - there is no fundemental reason why the number "p" has to be prime or
even that it has to be large. But there are some things I'll speculate
about - and maybe check out when I have more time. And here are some
simple observations:
1) The number of bits in M must be less than in p... the reason is as
follows... since we are taking a modulo - if M is greater than p then any
additional bits will be lost... that is if M has one more bit than p, then
there will be two messages that map the same way, etc.
2) We end up with a number C (cypher) and this number as it turns out can
be viewed as the last digit of M expressed in base p. This is obvious.
Suppose p = 3. Then we have in base 3 numbers of the form a0 + a1*3 +
a2*3^2 + a3*3^3 + ... and since we're talking modulo it is obvious that
a1, a2, a3, ... drop off. In this sense - modulo arithmetic is sort of
like a base conversion.
3) ok, we're raising a number by a power. On each step we can throw away
the digits above the a0 digit. Again - this is obvious.
4) This gives us a mapping with a finite length. Suppose we start by
converting M to a "digit" in a numbering system of base p - I'll notate
each digit (which might be a rather large string) as #1, #2, #3, ...
So we get something like this. x * x yeilds #a0 + #a1*p + #a2*p^2 + ...
but everything after #a0 drops off so we get a series of jumps through the
possible digits that comprise the base.
Since there are "p" digits... no path through these digits can exceed the
number of digits (obvious).
Here's an example - base 10:
starting number: sequence... note the path length.
0) 0*0=0 we're done - path length is one.
1) 1*1=1 path length is 1
2) 2-4-8-6-2
3) 3-9-7-1-3
4) 4-6-4
5) 5-5 path length is one
6) 6-6 path length is one
7) 7-9-3-1-7
8) 8-4-2-6-8
9) 9-1-9
So, base 10 is made up of 2*5, both of which are prime and we have two
paths of length 4 and two paths of length 2 and four paths of length 1.
both paths of length >2 are traversed both ways.
This makes sense to me.
ok - here is the base 12 table.
0) 0-0
1) 1-1
2) 2-4-8-4-8
3) 3-9-3-9
4) 4-4
5) 5-1-5-1
6) 6-0-0
7) 7-1-7-1
8) 8-4-8-4
9) 9-9
a) a-4-4
b) b-1-b-1
This looks a lot like repeating fractions... hmm - and combinatorics.
what this means is knowing what the base is - which is the number we
start with - we can easily generate all message chains and simply search
using the cypher to find which one is which.
Now - the LONGEST chain is p steps long. I suspect this may occur when
the base is prime. But I haven't looked into it much.
If so - then the number of distinct circuits through the field of digits
might be related to the factors in the base... and if so - then whenever
the base is chosen to be "multiprime" - the encryption weakens.
Here is p=7:
0) 0-0
1) 1-1
2) 2-4-1-2
3) 3-2-6-4-5-1-3
4) 4-2-1-4
5) 5-4-6-2-3-1-5
6) 6-1-6
Another way of looking at this is as follows.
In Pohlig-Hellman they chose p in the equation to be prime. In RSA they
chose "p" to be a product of two primes. Presumably the product is easier
to crack - but has the wonderful benefit that we can use both private and
public parts.
But if this is extended I suspect that all that happens is that it gets
weaker. If one relaxes the minimization of the number of factors
comprising "P" then we can choose any old number.. who cares how many
factors...
Please don't stomp on me... I'm not a cryptographer and have done little
work in number theory.
On Thu, 4 May 2000, Lutz Jaenicke wrote:
> On Thu, May 04, 2000 at 10:39:05AM +0100, Mark J Cox wrote:
> > > Which is about to expire in a few months, if I remember correctly :-)
> >
> > Then we get into the new MultiPrimes patent instead. For details:
> > http://www.apacheweek.com/issues/00-04-21#rsa2000
>
> Well, but then, who cares?
>
> The MultiPrime patent does not cover the "old" RSA techniques. It will
> only hit me, when I want to use this new technique.
> It is not even part of the TLS standard, such that all products offering
> SSL ("old" techniques) or TLS (upcoming standard) will interoperate with
> old "unlicensed" software.
> As of today, with Netscape and InternetExplorer having nearly all of the
> market: as long as they support "old" RSA, we won't miss MultiPrime support.
> How long is SSLv2 outdated? It is still in these products...
>
> Best regards,
> Lutz
> * Even though it should be clear:
> - Every technique that is covered by the "old" RSA patent is covered by
> the old RSA patent :-) If that patent has expired there is no way to
> re-issue any patent on this old technique.
> - Hence RSA can file dozens of patents a week, they will never get back
> the actual protection. New patents only affect new developments. If it
> was already covered by the old patent, the "invention" was already
> published (in the old patent) and hence cannot (re-)gain protection.
> --
> Lutz Jaenicke [EMAIL PROTECTED]
> BTU Cottbus http://www.aet.TU-Cottbus.DE/personen/jaenicke/
> Lehrstuhl Allgemeine Elektrotechnik Tel. +49 355 69-4129
> Universitaetsplatz 3-4, D-03044 Cottbus Fax. +49 355 69-4153
> ______________________________________________________________________
> OpenSSL Project http://www.openssl.org
> User Support Mailing List [EMAIL PROTECTED]
> Automated List Manager [EMAIL PROTECTED]
>
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
