Cryptography-Digest Digest #936, Volume #11 Sun, 4 Jun 00 09:13:00 EDT
Contents:
Re: Cipher design a fading field? (Mok-Kong Shen)
Re: No-Key Encryption (Mok-Kong Shen)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Alan Pascoe)
Re: XTR independent benchmarks ("Eric Verheul")
Re: XTR independent benchmarks ("Eric Verheul")
Re: No-Key Encryption (David Formosa (aka ? the Platypus))
Re: Rivest's Multi-Grade Crypto (Mark Wooding)
Re: Solovay-Strassen primality test (Mark Wooding)
Re: Rivest's Multi-Grade Crypto (tomstd)
Re: slfsr.c (tomstd)
Re: Good ways to test. (tomstd)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sun, 04 Jun 2000 11:44:52 +0200
John Savard wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
>
> >(a) It has not been demonstrated that a group of amateurs can
> >in fact design a truly "strong" cipher.
>
> I wouldn't want to try decrypting something enciphered using Blowfish.
>
> But you are right, although what 'has not been demonstrated' is very
> nearly inherently impossible to demonstrate.
I think that the question is ill-defined and can't be properly argued. In
fact, if an amateur succeeds to design a strong cipher (we put aside the
issue of 'strong'), then he is thereafter counted as a professional. Thus
the proposition that no amateur has designed a strong cipher is sort of
tautology.
> >(b) I wish that the amateurs would quit inventing a plethora
> >of new encryption schemes until they have figured out how to
> >defeat the existing ones. This may be relevant to your thesis.
>
> But just because _they_ don't know how to crack the existing ones
> doesn't mean...
I don't think that there is any professional who has done the excercise
of cracking all ciphers that exist, before he attains the status of being
professional. On the other hand, cryptanalysis knowledge is evidently
required for a good design. However, I doubt that cryptanalysis of
lots of very old ciphers are unconditionally advantageous (from a
economical point of view) for would-be designers. For, if too much
time is spent on these, one will never finish to be able to learn the
more modern stuffs. (I believe that what wtshaw once expressed as
'climbing the fool's hill' is related to this issue. BTW, there might be
certain people wishing to sponsor that sport, because that can be fun.)
> >> Will AES be the -final- cipher?
>
> >Of course not. It won't even be the final encipherment
> >scheme that somebody eventually figures out how to crack.
>
> that someone else might not. So, people who want security *now* might
> well need something that has a chance of being better than what
> exists.
For those who are conservative and believe (whether justified or
not) to be in need of higher security, the way of multiple encryptions
is always open.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Sun, 04 Jun 2000 13:07:13 +0200
David Hopwood wrote:
> What identity? '*' was not stated to form a group [1], so A/A is not
> necessarily the same for all A. Even if it were, (A/A)*A is not
> necessarily equal to A (note that this is *not* implied by (A*A)/A = A),
> and certainly (A/A)*B is not necessarily equal to B, which your argument
> implicitly relies on.
Sorry for a dumb question: '/' is the inverse of '*', isn't it? What does
'inverse' mean? Could you give a tiny easily comprehensible example?
Thanks.
M. K. Shen
------------------------------
From: Alan Pascoe <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Sun, 04 Jun 2000 13:00:39 +0100
David Boothroyd wrote:
>
<snip>
> The proposals in the Bill are exactly the same as the ones Labour suggested
> before the election so there really isn't anything for anyone to get
> worked up about. The Conservatives were planning mandatory key escrow.
Is what this government is doing basically different? It seems that in
practice, users of PGP will have to retain their private keys and make
them available to government agencies on demand. I can see little
difference between this and Trusted Third Party arrangements.
--
Alan Pascoe PGP Key: 0xD5B1715B
Keep your files and e-mail private! http://www.pgpi.com
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Sun, 4 Jun 2000 13:43:43 +0200
> > First of all, the hard part of parameter generation in
LUCDIF consists of
> > generation a
> > primenumber p of 512 bits and (and if you're smart a prime
number q of about
> > 170 bits, such that
> > q divides p+1, if you want to be both safe and be able to
use subgroups).
> > The hard part of
> > parameter generation in XTR consists of generation of two
prime numbers of
> > about 170 bits.
> > No way, that LUCDIF parameter is faster! It should
(theoretically) be about
> > 3^4=81 times slower!
>
> Yes, LUCDIF parameter generation is almost certainly slower
(although I didn't
> test it), but how often do you generate new paramemters?
*Almost* certainly?? Do you have shares in LUCDIF, or something?
Generating a strong prime (as you do) of about 512 bits is a lot
slower than generating 2 of 170 bits!
According to your posting you seem to believe that generation of
a strong prime number of 512 bit (as with your LUCDIF) costs
5.21 msec, while the generation of two prime numbers of 170 bits
(as with XTRDIF) costs 8.35 msec! It seems that you believe
more in the output of your software, than in Math.
The point is that you said: "XTR is actually slower than
LUCDIF", and I'm disproving that.
Period. Moreover, when generating parameters for a public key
for digital signatures, this
typically needs to be done on a trusted device, like a
smartcard. If this takes too long,
users will pull out the smartcard of the reader: generation time
is crucial. Where your LUCDIF parameter generation on a
smartcard (!) takes the time of generation of a 1024 RSA key,
i.e. up to 10 minutes, XTR's parameter generation takes seconds.
And yes, if you precompute the LUCDIF parameters the actual
public key generation will take seconds, but then a lot of users
will share the same parameters
(like with ECC): this is not advisable.
> > Secondly, if I look at the orginal Asiacrypt94 paper of
Smith and Skinner,
> > then the elements
> > in the group of order p+1 in GF(p^2) are represented as U_n
and V_n in GF(p)
> > where
> > p is of size 512 bits, and:
> > V_2n = ((V_n)^2 + D (U_n)^2)/2 en
> > U_2n = Un*V*n
> >
> > V_n+1 = (Vn*U_1 + D*U_n * U_1)/2
> > U_n+1 = (Un*V_1 + V_n * U1)/2
> >
> > So if one uses a repeated squaring technique then:
> > - a "squaring" will cost 2 squarings in GF(p) and 1 mult in
GF(p);
> > - a "mult" will cost 5 mults in GF(p).
> > Assuming you use some trick to get rid of the division by 2.
>
> You don't need the U_n, and V_n can be computed with 2 mults
in GF(p) per bit
> of n. See http://www.eskimo.com/~weidai/lucas.html.
That's nice. What you're doing there is using
V_n and V_n+1 instead of U_n and V_m. Dispite this speed up, an
LUCDIF
exponentiation will take (theoretically) 2*3^2*log(q)= 18 *
log(q) multiplications in GF(p), i.e.
XTR-DIF is more than twice as fast as LUC-DIF.
Of course appliance of this advantage depends on the specific
hardware/software used. Also remember that LUCDIFs keys are 512
bits and XTRDIFS are 340
bits. Both from a computational and a communicational point,
XTRDIF is
superior to LUCDIF. Moreover, XTR's parameter and key generation
is (theoretically) upto 3^4 = 81 faster than LUC's.
> > Typically, you will need log(q) "squarings" en log(q)/2
"mults" for a
> > exponenation.
> > That is: 2log(q) squarings en (1 + 2.5)*log(q) mults in
GF(p). Now, as the
> > size of
> > the basis field in LUCDIF is 3 times larger than in XTR, it
reasonable, to
> > assume that
> > mults and squarings in the LUCDIF basic field is 3^2 = 9
times slower than
> > in XTR's basic
> > field.
>
> As I explained, in my test XTR 171 was actually doing 256-bit
arithmetic. Also
> all efficient multiplication implementations show less than
quadratic scaling
> at the bit lengths we are talking about whether they implement
classical or
> Karatsuba algorithms. See Michael Scott's paper at
> ftp://ftp.compapp.dcu.ie/pub/crypto/timings.doc. So
multiplications in the
> LUCDIF base field was actually just 3 times slower. XTR
requires 4 times more
> multiplications which made it slower overall.
This seems like an implementational issue to me. By choosing the
right optimalizations, XTRDIF can be made a lot faster than
LUCDIF.
Your optimalizations are just more optimal for LUCDIF.
As a final note: in your comparison you mandate a group
membership validation for XTR, while in LUCDIF you use (without
saying
that) short exponents.
There are several practical ways to avoid such a group member
valdiation in XTR and using short exponents are theoretically
risky as you don't get security from a genuine
DL problem anymore. That is to say: your comparison is not fair.
Eric
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Sun, 4 Jun 2000 13:52:04 +0200
> > First of all, the hard part of parameter generation in
LUCDIF consists of
> > generation a
> > primenumber p of 512 bits and (and if you're smart a prime
number q of about
> > 170 bits, such that
> > q divides p+1, if you want to be both safe and be able to
use subgroups).
> > The hard part of
> > parameter generation in XTR consists of generation of two
prime numbers of
> > about 170 bits.
> > No way, that LUCDIF parameter is faster! It should
(theoretically) be about
> > 3^4=81 times slower!
>
> Yes, LUCDIF parameter generation is almost certainly slower
(although I didn't
> test it), but how often do you generate new paramemters?
*Almost* certainly?? Do you have shares in LUCDIF, or something?
Generating a strong prime (as you do) of about 512 bits is a lot
slower than generating 2 of 170 bits!
According to your posting you seem to believe that generation of
a strong prime number of 512 bit (as with your LUCDIF) costs
5.21 msec, while the generation of two prime numbers of 170 bits
(as with XTRDIF) costs 8.35 msec! It seems that you believe
more in the output of your software, than in Math.
The point is that you said: "XTR is actually slower than
LUCDIF", and I'm disproving that.
Period. Moreover, when generating parameters for a public key
for digital signatures, this
typically needs to be done on a trusted device, like a
smartcard. If this takes too long,
users will pull out the smartcard of the reader: generation time
is crucial. Where your LUCDIF parameter generation on a
smartcard (!) takes the time of generation of a 1024 RSA key,
i.e. up to 10 minutes, XTR's parameter generation takes seconds.
And yes, if you precompute the LUCDIF parameters the actual
public key generation will take seconds, but then a lot of users
will share the same parameters
(like with ECC): this is not advisable.
> > Secondly, if I look at the orginal Asiacrypt94 paper of
Smith and Skinner,
> > then the elements
> > in the group of order p+1 in GF(p^2) are represented as U_n
and V_n in GF(p)
> > where
> > p is of size 512 bits, and:
> > V_2n = ((V_n)^2 + D (U_n)^2)/2 en
> > U_2n = Un*V*n
> >
> > V_n+1 = (Vn*U_1 + D*U_n * U_1)/2
> > U_n+1 = (Un*V_1 + V_n * U1)/2
> >
> > So if one uses a repeated squaring technique then:
> > - a "squaring" will cost 2 squarings in GF(p) and 1 mult in
GF(p);
> > - a "mult" will cost 5 mults in GF(p).
> > Assuming you use some trick to get rid of the division by 2.
>
> You don't need the U_n, and V_n can be computed with 2 mults
in GF(p) per bit
> of n. See http://www.eskimo.com/~weidai/lucas.html.
That's nice. What you're doing there is using
V_n and V_n+1 instead of U_n and V_m. Dispite this speed up, an
LUCDIF
exponentiation will take (theoretically) 2*3^2*log(q)= 18 *
log(q) multiplications in GF(p), i.e.
XTR-DIF is more than twice as fast as LUC-DIF.
Of course appliance of this advantage depends on the specific
hardware/software used. Also remember that LUCDIFs keys are 512
bits and XTRDIFS are 340
bits. Both from a computational and a communicational point,
XTRDIF is
superior to LUCDIF. Moreover, XTR's parameter and key generation
is (theoretically) upto 3^4 = 81 faster than LUC's.
> > Typically, you will need log(q) "squarings" en log(q)/2
"mults" for a
> > exponenation.
> > That is: 2log(q) squarings en (1 + 2.5)*log(q) mults in
GF(p). Now, as the
> > size of
> > the basis field in LUCDIF is 3 times larger than in XTR, it
reasonable, to
> > assume that
> > mults and squarings in the LUCDIF basic field is 3^2 = 9
times slower than
> > in XTR's basic
> > field.
>
> As I explained, in my test XTR 171 was actually doing 256-bit
arithmetic. Also
> all efficient multiplication implementations show less than
quadratic scaling
> at the bit lengths we are talking about whether they implement
classical or
> Karatsuba algorithms. See Michael Scott's paper at
> ftp://ftp.compapp.dcu.ie/pub/crypto/timings.doc. So
multiplications in the
> LUCDIF base field was actually just 3 times slower. XTR
requires 4 times more
> multiplications which made it slower overall.
This seems like an implementational issue to me. By choosing the
right optimalizations, XTRDIF can be made a lot faster than
LUCDIF.
Your optimalizations are just more optimal for LUCDIF.
As a final note: in your comparison you mandate a group
membership validation for XTR, while in LUCDIF you use (without
saying
that) short exponents.
There are several practical ways to avoid such a group member
valdiation in XTR and using short exponents are theoretically
risky as you don't get security from a genuine
DL problem anymore. That is to say: your comparison is not fair.
Eric
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: No-Key Encryption
Date: 4 Jun 2000 12:19:54 GMT
Reply-To: dformosa@[202.7.69.25]
On Sun, 04 Jun 2000 13:07:13 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>David Hopwood wrote:
>
>> What identity? '*' was not stated to form a group [1], so A/A is not
>> necessarily the same for all A. Even if it were, (A/A)*A is not
>> necessarily equal to A (note that this is *not* implied by (A*A)/A = A),
>> and certainly (A/A)*B is not necessarily equal to B, which your argument
>> implicitly relies on.
>
>Sorry for a dumb question: '/' is the inverse of '*', isn't it? What does
>'inverse' mean? Could you give a tiny easily comprehensible example?
>Thanks.
Inverse means the function that gose backwards, so if
f(a) = b then
f^-1(b) = a is the inverse.
So '-' is the inverse of +
/ is the inverse of * (if * is times)
square root is the inverse of squaring ect ect.
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Interested in drawing platypie for money? Email me.
Crack my Hash win$200 http://dformosa.zeta.org.au/~dformosa/PlatyMAC.txt
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Rivest's Multi-Grade Crypto
Date: 4 Jun 2000 10:58:44 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> In [1] Rivest presents an alternative to key escrow called
> "Multi-Grade" Cryptography where each key is composed of two parts,
> essentially K = (n0, n1). The symmetric key has an effective length
> of n = n0 + n1. 'n1' is considered fixed for a specific time, and n0
> changes per message. In his paper he describes a 68/48 scheme where
> n0=48,n1=68 and the total key size is 116 bits.
No. You've read it wrong. In a 68/48-bit system, n = 68, and n_0 =
48. Thus, n_1 = 20.
> Each message has a fixed header composed of C=Ek1(P) (for a known P)
> where k1 is the n1-bit key.
Where did you find that? I didn't notice any such statement in the
paper.
> The idea is that law enforcement could brute force k1 and then find k0
> for each message with under 2^116 work.
You must have been reading a different paper from me. Rivest's idea was
to require a two-stage process for breaking a user's messages:
* The first message takes 2^n time to break, because the adversary
(whoever that might be) has to guess the entire key.
* Subsequent messages take 2^{n_0} time to break, because k_1 is now
known from the previous break.
Rivest opines that this is a more acceptable compromise over key lengths
than what used to be a straightforward 2^{n_0} time for all messages.
He raises the barrier to snooping on a new user, while keeping down the
cost of continuing to decrypt messages of an already-targeted user.
> [1] "Multi-Grade Cryptography", Ronald L. Rivest
Where possible, it's useful to provide some sort of link to the
reference. For the benefit of other readers, it's at
http://theory.lcs.mit.edu/~rivest/Rivest-multigrade.ps
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Solovay-Strassen primality test
Date: 4 Jun 2000 11:02:12 GMT
Axel Lindholm <[EMAIL PROTECTED]> wrote:
> A number, 'n', is a pseudoprime with base 'a' if, and only if: a^n mod
> n = a, 'n' is a composite number and 'a' > 0. Say that n = x * y, then
> we can refrase the above definition to: 'n' is a pseudoprime with base
> 'a' if, and only if: a^x mod x = a, a^y mod y = a, 'n' is a composite
> number and 'a' > 0. Now, x and y can't be more than n/2 because the
> smallest factor avalible is 2!
This analysis unfortunately applies to the Fermat test, rather than the
Solovay-Strassen test as requested.
-- [mdw]
------------------------------
Subject: Re: Rivest's Multi-Grade Crypto
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 04 Jun 2000 05:23:01 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> In [1] Rivest presents an alternative to key escrow called
>> "Multi-Grade" Cryptography where each key is composed of two
parts,
>> essentially K = (n0, n1). The symmetric key has an effective
length
>> of n = n0 + n1. 'n1' is considered fixed for a specific
time, and n0
>> changes per message. In his paper he describes a 68/48 scheme
where
>> n0=48,n1=68 and the total key size is 116 bits.
>
>No. You've read it wrong. In a 68/48-bit system, n = 68, and
n_0 =
>48. Thus, n_1 = 20.
I was guessing I read it wrong.
>> Each message has a fixed header composed of C=Ek1(P) (for a
known P)
>> where k1 is the n1-bit key.
>
>Where did you find that? I didn't notice any such statement in
the
>paper.
>
>> The idea is that law enforcement could brute force k1 and
then find k0
>> for each message with under 2^116 work.
>
>You must have been reading a different paper from me. Rivest's
idea was
>to require a two-stage process for breaking a user's messages:
>
> * The first message takes 2^n time to break, because the
adversary
> (whoever that might be) has to guess the entire key.
>
> * Subsequent messages take 2^{n_0} time to break, because k_1
is now
> known from the previous break.
>
So 2^n = 2^68 in his system, then subsequent messages take 2^20
time? Even still my observation is correct. What if the wrong
people could perform the initial hard work?
tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: slfsr.c
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 04 Jun 2000 05:24:44 -0700
In article <8hd0sq$po8$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
wrote:
>thanks tomstd for this program and
>your contribution in crypto
>
>your prog pass diehard test ...
I actually did test my slfsr with ENT and Diehard and it
performs very well.
>slfsr 64 bits is easy to crack
>(predict) the sequence ???
Assuming the period of the polynomial I chose is maximal length
it's reasonably secure.
>same question for more bit 128 etc...
Yeah I would pick the same design with a +96bit LFSR. But they
are just a tad slow which makes them less then usefull...
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Good ways to test.
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 04 Jun 2000 05:29:15 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>tomstd wrote:
>
>> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>
>> >tomstd wrote:
>> >
>> >> Freedom of thought has nothing todo with this. I am not
>> trying
>> >> to force my will on ya, I am telling you the truth.
>> >>
>> >
>> >So you are the greatest philosopher of all time. What you
say IS
>> >truth. Philosophers of the past are apparently more humble.
>>
>> Oh stop being an idiot.
>>
>> Are you trying to tell me that no drug ever released as 'safe'
>> has ever had a adverse side effect?
>
>You are answering presently out of context. Did the lines quoted
>above ever contain the word 'drug'??? Yes, previously you (not
>I!) started to argue based on the issue of drugs and I answered
to
>your arguments. You employed those numerical figures. I said
>these were not appropriate as materials for an analogy, because
>there are not corresponding numerical measures in my opinion.
>Anyway, you may be right or I may be right. Since, however, the
>follow-up thereafter of yous started to go outside of the proper
>stytle of scientific discussion in my personal view, I have
attempted
>to terminate that line of discussion in that I expressed my
wish that
>your arguments would be accepted by many people but that I
>remain unconvinced. Wasn't that polite and fair enough on my
part
>to stop the dispute??? Now answer to the above: It was YOU
>who wanted to TELL me something about drugs, not the reverse!!!
This is pointless babbling. The arguement was that Cryptography
is a black art science and that we should not trust it.
My point was that essentially medicine is the same thing, where
we base all 'facts' on observed activities. We say eat lettuce
because it promotes beta-carotene (I am making this up) storage
in the retina, just like we say to use Blowfish because it is
resistant to Diff/Linear Attacks.
Of course this says nothing of the possibility that lettuce
having any other 'effect' on the body or that Blowfish could be
broken faster then we think.
The irony is that we trust medicine and not cryptography, when
in my view, they are on the say 'boat of trust'.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
** 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
******************************
