Cryptography-Digest Digest #582, Volume #13 Sun, 28 Jan 01 18:13:01 EST
Contents:
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
Re: William's P+1 (Mika R S Kojo)
proving x^ed mod n = x ("Michael G. Hansen")
Primality Test ("Adam Smith")
Re: Primality Test ("Scott Fluhrer")
Re: Primality Test (Tom St Denis)
Re: Primality Test (Splaat23)
Re: proving x^ed mod n = x (Tom St Denis)
Re: proving x^ed mod n = x (Bryan Olson)
Re: proving x^ed mod n = x (Bryan Olson)
Re: MIKE - alternative to SPEKE and PAK (Thomas Wu)
Re: proving x^ed mod n = x ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sun, 28 Jan 2001 19:16:39 GMT
On Sun, 28 Jan 2001 12:49:19 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>>
>> >[...]
>> >I suppose you have a different and problematical concept
>> >of the (THEORETICAL) OTP. The bit sequence of OTP is by
>> >definition/assumption unpredictable. If a 'claimed' OTP
>> >uses a predictable bit sequence and consequently is weak
>> >as you said, then it is by definition NOT an OTP, though
>> >snake-oil peddlers used to call that OTP.
>>
>> OK, then, in practice, there can be no OTP at all, since, in general,
>> it will be impossible to prove in practice that any bit sequence
>> actually is unpredictable.
>>
>> Clearly we can't compare a cipher which is designed to work in
>> practice to one which cannot. Yet that was exactly what you tried to
>> do.
>
>The last sentence is FALSE.
Really?
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 26 Jan 2001 23:26:55 +0100
Message-ID: <[EMAIL PROTECTED]>
"But the point is whether your DT is on a par with the
theoretical OTP or perhaps better than it. So it is a
'theoretical' question, not a technical question."
>It was you who made a comparison
>of your DT with the OTP and claimed even superiority over
>it.
>From the "Revisited" article:
"When every plaintext block is exactly bit-balanced, any
possible plaintext block is some valid bit-permutation of
any ciphertext block. So, even if an opponent could
exhaustively un-permute a ciphertext block, the result
would just be every possible plaintext block. No particular
plaintext block could be distinguished as the source of the
ciphertext. This is a form of balanced, nonlinear combining
of the confusion sequence and data block: as such, it is
related to XOR, Latin squares, Shannon "perfect secrecy,"
and the one-time-pad (OTP).
"The inability to distinguish a particular plaintext, even
when every possibility is tried, is basically the advantage
claimed for the OTP. It is also an advantage which the OTP
cannot justify in practice unless we can prove that the OTP
keying sequence is unpredictable, which generally cannot be
done. That makes the practical OTP exceedingly "brittle":
if the opponents ever do gain the ability to predict the
sequence, they may be able to attack many messages, both
future and past. That would occur in the context of a
system supposedly "proven" secure; as usual, the user would
have no indication of security failure.
"Dynamic Transposition does not need the assumption of
sequence unpredictability, because the sequence is hidden
behind a multitude of different sequences and permutations
which all produce the same result. And if the sequence
itself cannot be exposed, exploiting any predictability in
the sequence will be difficult. (This of course does not
mean that Dynamic Transposition cannot be attacked:
Brute-force attacks on the keys are still imaginable, which
is a good reason to use large random message keys.)"
So exactly what about "an advantage which the OTP cannot justify in
practice" do you not understand?
>John Savard first wrote some lines on that and came
>back to it in a recent follow-up. I suggest that you leave
>out everything in that direction in your writings about DT.
>No reasonable man would have any internal reaction, when a
>girl says she is pretty. Things only become different, when
>it concerns the most beautiful creature of the world.
It is your delusion that OTP is that "most beautiful creature." In
practice an OTP is nothing more than a stream cipher with a
particularly inconvenient key. It is only the *theoretical* OTP -- an
illusion which cannot protect real data -- which could be called
"beautiful" -- but that can't be used.
The reason people want to use -- in practice -- an OTP is to get a
mathematical proof of strength. Unfortunately, the OTP proof
*assumes* a random sequence. Now, surely there can be no debate about
whether or not an "OTP" is secure if the keying sequence is
predictable. Also there should be little if any debate about whether
or not we can, by testing, *prove* a keying sequence is not
predictable. (Note that even a complex and random-like sequence
produced by stepping a counter into the cipher of your choice is
predictable -- if someone can just reverse that cipher. And whether
or not we can do that is irrelevant; for a proof of strength, we need
to know that no opponent can do it, and that is something we cannot
know.) So the OTP proof simply does not apply in practice, unless we
have some way to *prove* sequence unpredictability to cryptographic
levels of assurance.
>> >Some people in
>> >crypto groups even object to use the term pseudo-OTP to
>> >designate that kind of stuff.
>>
>> Usually the objection is to using an obvious pseudo-RNG and calling
>> the result an OTP instead of a Stream Cipher.
>>
>> >(Once I got flames for having
>> >employed the term pseudo-OTP.) We should take care not to
>> >be contaminated in our terminology by the slangs of
>> >snake-oil peddlers. (Of course they could complain, because
>> >anything used 'one-time' is OT, but that's evidently outside
>> >our present concern.)
>> >
>> >BTW, my argumention in the previous follow-up could be
>> >simplified a bit. One does not have to use the big sequence
>> >S. It suffices to pick one arbitrary balanced block and
>> >feed repetitions of it to the algorithm. Basically, the
>> >argument boils down to the trivial fact that a PRNG has a
>> >finite period, while the theoretical OTP has, by definition,
>> >an infinite period. Hence there is no chance that the former
>> >can compete with the latter.
>>
>> Had you actually read my "Revisited" article, you would have found the
>> statement:
>>
>> "This of course does not
>> mean that Dynamic Transposition cannot be attacked:
>> Brute-force attacks on the keys are still imaginable, which
>> is a good reason to use large random message keys."
>>
>> I am discussing a cipher which functions in practice, not some
>> theoretical thing whose only use is to confuse and confound.
>>
>> You appear to be discussing perfection which can never occur in
>> practice.
>
>Ah, I admit that I haven't carefully read your revision
>(because of your previous comparion with OTP, which has
>unfortunately relaxed my attention somewhat). But you
>should have retracted your claim of superiority over OTP
>in the revision, I suppose, in order to avoid confusion
>of readers.
How about this:
Dynamic Transposition (a practical cipher) is arguably superior to the
OTP (when used in practice), because under known-plaintext attack an
OTP is immediately vulnerable to a predictable keying sequence, while
Dynamic Substitution hides predictability behind a vast number of
different permutations, each of which could have created the given
ciphertext block.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Mika R S Kojo <[EMAIL PROTECTED]>
Subject: Re: William's P+1
Date: 28 Jan 2001 21:55:45 +0200
"The Death" <[EMAIL PROTECTED]> writes:
>
> Seems there s no reason for me to use it then.
> Is it in any way better than Pollard's P-1 ?
In the trivial sense yes. It finds a factor p of N if p+1 has small
divisors, but Pollard's p-1 finds such that p-1 has small divisors :)
The basic idea of p-1, p+1 and ECM is that you take a certain group (a
simple mathematical object) and use it to find a small factor of
N. However, p-1 and p+1 have only one group (in a sense) that can be
used, where as with ECM you have large number of them (perhaps even
Sqrt(N) of different ones). However, testing one group with ECM takes
longer than checking with p-1 or p+1. At least in absolute time on one
machine, because the group operation is simpler to implement.
The point is that p-1 and p+1 are perhaps obsolete in the asymptotical
sense, but they may be useful if you wish to find some (small) factors
quickly. In many cases you should just try p-1 and p+1 first and then
jump into ECM, just like you should first try with Pollard rho and
trial division.
If you seriously try to factor something you might as well implement
them all. Although in a theoretical sense ECM alone is sufficient,
with perhaps GNFS taking over at some point.
Death, I suggest that you read the bible iff interested in explicit details
Henri Cohen, A Course in Computational Algebraic Number Theory, Springer.
-- Mika
> Bob Silverman <[EMAIL PROTECTED]> wrote in message
> news:94rr5t$hsm$[EMAIL PROTECTED]...
> > In article <94n6eq$lhj$[EMAIL PROTECTED]>,
> > "The Death" <[EMAIL PROTECTED]> wrote:
> > > I saw several websites, and they all mentioned this algorithm but
> > didn't
> > > have any info about it. Can any1 give me information about this
> > algorithm?
> >
> >
> > It finds a factor p dividing n if p+1 only has small prime
> > factors.
> >
> > It only works 1/2 the time even when p has the required property.
> > (you choose a Lucas sequence. It succeeeds iff the discriminant is a
> > non-residue mod p)
> >
> > It is obsolete.
> >
> > What more would you like?
> >
> > --
> > Bob Silverman
> > "You can lead a horse's ass to knowledge, but you can't make him think"
> >
> >
> > Sent via Deja.com
> > http://www.deja.com/
>
>
------------------------------
From: "Michael G. Hansen" <[EMAIL PROTECTED]>
Subject: proving x^ed mod n = x
Date: Sun, 28 Jan 2001 21:19:03 +0100
hi,
I'm doing a paper for school on RSA and I'm trying to derive RSA from
Fermat's little theorem:
x^(p-1)(q-1) mod n=1 if x and n are relatively prime to each other
you can continue this to:
x^((p-1)(q-1)+1) mod n =x, but that also works if x and n are not relatively
prime to each other. Is there any prove for that?
thanks
Michael
---
http://www.geocities.com/mghansen256.geo/index.htm
------------------------------
From: "Adam Smith" <[EMAIL PROTECTED]>
Subject: Primality Test
Date: Sun, 28 Jan 2001 20:56:36 GMT
Once again, this is for generating RSA keys...if all of my posts here are
getting annoying or are out-of-place, please say something....
I'm not having trouble generating random numbers with 150-200 digits, my
problem comes in testing to see if they're random...I'm using an
implementation of the Rabin-Miller primality test with even only one round
(if true then probability that the number is composite is < .25^(number of
rounds)), but it's taking an extremely long time to test...I had to force
close the app before it even tested one number (it's using a Pentium III 500
MHz chip)...
Any tips on generating 512 bit prime numbers?
Once again, thanks in advance!
Adam Smith
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Sun, 28 Jan 2001 13:31:29 -0800
Adam Smith <[EMAIL PROTECTED]> wrote in message
news:8I%c6.3988$[EMAIL PROTECTED]...
> Once again, this is for generating RSA keys...if all of my posts here are
> getting annoying or are out-of-place, please say something....
>
> I'm not having trouble generating random numbers with 150-200 digits, my
> problem comes in testing to see if they're random...I'm using an
> implementation of the Rabin-Miller primality test with even only one round
> (if true then probability that the number is composite is < .25^(number of
> rounds)), but it's taking an extremely long time to test...I had to force
> close the app before it even tested one number (it's using a Pentium III
500
> MHz chip)...
>
> Any tips on generating 512 bit prime numbers?
You might try a quick test for divisibility for small primes before running
the RM test. This will catch most composites, and is a lot faster. For
extra credit, you can run a 'seive' that will automatically skip numbers
which has small factors.
--
poncho
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Sun, 28 Jan 2001 21:30:03 GMT
In article <8I%c6.3988$[EMAIL PROTECTED]>,
"Adam Smith" <[EMAIL PROTECTED]> wrote:
> Once again, this is for generating RSA keys...if all of my posts here are
> getting annoying or are out-of-place, please say something....
>
> I'm not having trouble generating random numbers with 150-200 digits, my
> problem comes in testing to see if they're random...I'm using an
> implementation of the Rabin-Miller primality test with even only one round
> (if true then probability that the number is composite is < .25^(number of
> rounds)), but it's taking an extremely long time to test...I had to force
> close the app before it even tested one number (it's using a Pentium III 500
> MHz chip)...
>
> Any tips on generating 512 bit prime numbers?
Follow these steps, they're simple but can save trouble
1. Make sure you set the msb and lsb of the number to force it to be the
right size and to force it odd (even numbers are not prime except for 2).
2. Try dividing by the first 1000 small primes. This rules out about 90% of
all numbers you try.
3. Then perform 5 or more rounds of RM.
After that you should be sure it's most likely prime. The second step is
crucial since it filters out ALOT of numbers before you get to the long
steps.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Sun, 28 Jan 2001 21:28:12 GMT
Umm, written in native Python (an interpreted language), a single
Miller-Rabin round on a 512 bit condidate takes .05 seconds. You've
done something wrong with the algorithm, or your big number library is
REALLY slow.
One of the best ways to generate primes is to pick a random number of
the correct range, fix the most and least significant bit to 1, and
increment by 2 until you get a prime. Each candidate can be tested
first with trial division of the firxt X primes to screen obvious
composites, then with a couple of rounds of Miller-Rabin.
Your posts here are not getting annoying, but most of the answers _are_
available from other, better sources, such as books. I would recommend
getting the Handbook of Applied Cryptography. It's even available for
free on the Internet. Read it before asking a question and you'll be
guaranteed that the answer is not _completely_ obvious.
- Andrew
In article <8I%c6.3988$[EMAIL PROTECTED]>,
"Adam Smith" <[EMAIL PROTECTED]> wrote:
> Once again, this is for generating RSA keys...if all of my posts here
are
> getting annoying or are out-of-place, please say something....
>
> I'm not having trouble generating random numbers with 150-200 digits,
my
> problem comes in testing to see if they're random...I'm using an
> implementation of the Rabin-Miller primality test with even only one
round
> (if true then probability that the number is composite is < .25^
(number of
> rounds)), but it's taking an extremely long time to test...I had to
force
> close the app before it even tested one number (it's using a Pentium
III 500
> MHz chip)...
>
> Any tips on generating 512 bit prime numbers?
>
> Once again, thanks in advance!
> Adam Smith
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: proving x^ed mod n = x
Date: Sun, 28 Jan 2001 21:39:27 GMT
In article <[EMAIL PROTECTED]>,
"Michael G. Hansen" <[EMAIL PROTECTED]> wrote:
> hi,
> I'm doing a paper for school on RSA and I'm trying to derive RSA from
> Fermat's little theorem:
> x^(p-1)(q-1) mod n=1 if x and n are relatively prime to each other
> you can continue this to:
> x^((p-1)(q-1)+1) mod n =x, but that also works if x and n are not relatively
> prime to each other. Is there any prove for that?
> thanks
Simple: (p-1)(q-1) is a multiple of the order of the multiplicative group.
Thus x^(n) mod n = x^(n mod n) mod n = x^0 mod n = 1.
(p-1)(q-1) is just one above it.
Thus: x^(n+1) mod n = x^(n+1 mod n) mod n = x^1 mod n = x mod n
You know that a unit in the group can be multiplied by it self (a divisor of
(p-1)(q-1)) times before it comes back to one. This is guaranteed because
it's a group (if n is prime). Therefore it doesn't matter what x is because
(p-1)(q-1) is just a multiple of the divisor requried to get back to 1. i.e
x^(3n mod n) mod n = x^0 mod n = 1
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: proving x^ed mod n = x
Date: Sun, 28 Jan 2001 22:06:06 GMT
Michael G. Hansen wrote:
> I'm doing a paper for school on RSA and I'm trying to derive RSA from
> Fermat's little theorem:
> x^(p-1)(q-1) mod n=1 if x and n are relatively prime to each other
> you can continue this to:
> x^((p-1)(q-1)+1) mod n =x, but that also works if x and n are not
relatively
> prime to each other. Is there any prove for that?
Sure. Prove
x ^ ((p-1)(q-1)+1) is congruent to x mod p
x ^ ((p-1)(q-1)+1) is congruent to x mod q
The Chinese Remainder Theorem says that if p and q are
relatively prime, then there is exactly one integer in [0..p*q-1]
that is congruent to x mod p and congruent to x mod q. Since
x is such an integer, that's it.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: proving x^ed mod n = x
Date: Sun, 28 Jan 2001 22:23:38 GMT
Tom St Denis wrote:
> Michael G. Hansen wrote:
> > hi,
> > I'm doing a paper for school on RSA and I'm trying to derive RSA
from
> > Fermat's little theorem:
> > x^(p-1)(q-1) mod n=1 if x and n are relatively prime to each other
> > you can continue this to:
> > x^((p-1)(q-1)+1) mod n =x, but that also works if x and n are not
relatively
> > prime to each other. Is there any prove for that?
> > thanks
>
> Simple: (p-1)(q-1) is a multiple of the order of the
> multiplicative group.
And the question is about x that are not elements of
the multiplicative group.
> Thus x^(n) mod n = x^(n mod n) mod n = x^0 mod n = 1.
False.
> (p-1)(q-1) is just one above it.
(p-1)(q-1) = n - 2pq + 1. I don't see what "it" you mean.
> Thus: x^(n+1) mod n = x^(n+1 mod n) mod n = x^1 mod n = x mod n
False.
> You know that a unit in the group can be multiplied by it
> self (a divisor of (p-1)(q-1)) times before it comes back to
> one.
"Unit" is typically defined for rings, since all elements
of a group have inverses. But the x in the question is not
an element of the multiplicative group mod n.
> This is guaranteed because it's a group (if n is prime).
n is not prime. The question is about RSA; n = p*q.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: MIKE - alternative to SPEKE and PAK
Date: 28 Jan 2001 14:37:41 -0800
"Michael Scott" <[EMAIL PROTECTED]> writes:
> "Thomas Wu" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Michael Scott" <[EMAIL PROTECTED]> writes:
> >
> > > Some months ago I mentioned an idea I had concerning a new algorithm for
> a
> > > low-entropy password-authenticated key-exchange, along the lines of
> SPEKE,
> > > PAK and SRP. Tom Wu was kind enough to make a few comments.
> > >
> > > I have since written up the idea in more detail - it may be found at
> > > http://www.compapp.dcu.ie/CA_Working_Papers/wp00.html#1300
>
> > > The method is rather like PAK. The main novel idea is the use of two
> > > independent group generators. Its main advantage is that it works well
> in
> > > any type of group (e.g. Elliptic Curves - unlike SRP), also it avoids
> the
> >
> > That isn't really true - there is at least one published proposal for an
> > efficient way to do EC-SRP.
> >
>
> Can you point me at it? A neat idea in SRP is to mix both + and * operators,
> but you can't do this with EC.
See the "References" section on the SRP website.
> > > sub-group membership problems that arise with SPEKE and PAK. In a common
> > > context it is maybe 5 times faster.
> >
> > Could you elaborate on what these sub-group membership problems are?
> > My understanding was that using the parameters recommended for these
> > protocols (e.g. DH-1, safe prime p) would allow verifiable parameter
> > choices that were immune to subgroup confinement attacks.
> >
>
> The problem of getting the secret S into the sub-group. For both SPEKE and
> PAK this requires exponentiation by (p-1)/q, which is large for the DH-2
> scenario, and PAK is only presented in the DH-2 scenario. The DH-2 setting
> seems to have become more popular, as in the DSS for example, and is the
> method supported by standards like P1363, so MIKE may be an easier way of
> adding a low-entropy secret to an existing Diffie-Hellman implementation.
I suspect that the choice between DH-1 and DH-2 will vary between various
standards/protocols (e.g. IPSEC), so one could advocate, say, SRP or PAK
for DH-1 implementations, or MIKE for DH-2 implementations, if for some
reason the DH parameters are fixed. Does the PAK paper only discuss DH-2?
If so, that sounds like a pretty glaring omission, because it is inherently
better-suited for DH-1.
> Anyway the more of such protocols that are available, the better, specially
> non-patented ones.
>
> Its really quite magical to me that in the classic cryptographic setting of
> Alice and Bob trying to communicate in secret, it is possible to get strong
> cryptography with an easily remembered mutual secret like a four-digit PIN
> number.
Have you given any thought to how a verifier-based version of MIKE could
be derived? I can't think of any easy way other than by using the
existing, patented A- and B- extensions, and these also tend cripple the
performance of the protocol to below the level of existing verifier-based
protcols like SRP. MIKE would be much more interesting if an efficient
alternate verifier-based construction could be found.
> Mike Scott
Tom
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: proving x^ed mod n = x
Date: 28 Jan 2001 17:49:57 -0500
Michael G. Hansen <[EMAIL PROTECTED]> wrote:
> hi,
> I'm doing a paper for school on RSA and I'm trying to derive RSA from
> Fermat's little theorem:
> x^(p-1)(q-1) mod n=1 if x and n are relatively prime to each other
> you can continue this to:
> x^((p-1)(q-1)+1) mod n =x, but that also works if x and n are not relatively
> prime to each other. Is there any prove for that?
The important thing to note is that n is square free (not divisible by p^2
for some prime p).
Consider, not n, but p where p is one of the prime factors of n.
If n=pq you have a few cases.
If x is not divisible by p or q, then it's easy.
Suppose x is divisible by p but not q.
Then x^(ed)=x mod q (since x is relatively prime to q and ed-1 is
divisible by q-1=phi(q)) AND:
x^(ed)=x mod p since ... mod p BOTH SIDES ARE ZERO.
Well, if x^(ed)=x mod p and mod q and p and q are relatively prime, then
x^(ed)=x mod n (n=pq).
Similarly, one can handle the case of x divisible by q but not p.
If x is divisible by both p and q (so divisible by n) then
x^(ed)=x mod n ... because BOTH SIDES ARE ZERO.
The importance to having n square free is in the case of x divisible by p
and not q, for example.
x^(ed)=x mod p since both sides are zero.
But suppose p^2 is a factor of n.
It need not be true that x^(ed)=x mod p^2 (x may only have one factor of
p, but if ed>1, then x^(ed) will have two factors of p:
e.g. n=45=9*5: phi(n)=pi(9)*pi(5)=24 and x^(24)=x mod 45 if x is
relatively prime to 45 (actually x^(12)=x mod 45: one only use the
least common multiple of phi(9)=6 and phi(5)=4 instead of the
product) BUT 3^24<>3 mod 45 (if 3^24=3 mod 45, then 3^45=3 mod 9 but
3^45=0 mod 9 and 3<>0 mod 9).
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
