Cryptography-Digest Digest #394, Volume #13 Wed, 27 Dec 00 14:13:00 EST
Contents:
Personally I have not been in this area of Finland yet, but because I am now here
after I was deported to Finland by the Secretary of State .. I may go and visit ..
they say that Vaasa is quite a beautiful city (Markku J. Saarelainen)
Re: ECDSA: adding the Point P with -P and restrictions of a & b (Doug Kuhlman)
Re: Distributing private keys on the internet (Benjamin Goldberg)
Re: ECDSA: adding the Point P with -P and restrictions of a & b ("Jesper Stocholm")
Re: Distributing private keys on the internet (Bob Silverman)
Forward-secure Signatures and Compatible Weak Keys (Ross Anderson)
Re: Distributing private keys on the internet (Bob Silverman)
Re: polynomial permutation cipher (Mok-Kong Shen)
Are the classical techniques so inferior? (Mok-Kong Shen)
Re: ___(WANTED) UPDATED performance figures of elliptic curve multiplications
("Michael Scott")
Re: Block or stream cipher ("John E. Gwyn")
Re: ECDSA: adding the Point P with -P and restrictions of a & b (Doug Kuhlman)
----------------------------------------------------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: soc.culture.polish,soc.culture.ukrainian,soc.culture.yugoslavian
Subject: Personally I have not been in this area of Finland yet, but because I am now
here after I was deported to Finland by the Secretary of State .. I may go and visit
.. they say that Vaasa is quite a beautiful city
Date: Wed, 27 Dec 2000 17:02:07 GMT
http://www.rotary.fi/1380.htm
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: ECDSA: adding the Point P with -P and restrictions of a & b
Date: Wed, 27 Dec 2000 10:52:55 -0600
Jesper Stocholm wrote:
>
> I am looking at the math defining ECDSA and there are a couple of things, I
> really don't get:
>
> 1.
> What causes the retriction of a and b to be 4a^3+27b*2 != 0 mod p ? What is
> the effect of this ?
>
This is required to make sure the resulting variety is not singular. If
4a^3+27b^2 = 0 mod p, then the variety is genus 0, is not an elliptic
curve.
> 2.
> When adding a point p with it's negative -p, ecdsa states, that
>
> P+ -P = (x,y)+(x,-y) = O ... but as far as I can see, this only holds for
> curves, that are symmetric arround the x-axis ... what if this wasn't the
> case ?
>
Well, your above question assumes the form y^2=x^2+ax+b (which only
works if the characteristic is not 2 or 3, BTW). Then it is symmetric
around the x-axis. If not, then P = (x,y) has -P = (x,-y-a_1x - a_3)
where the curve is given in the form
y^2 + a_1xy +a_3y = x^3 + a_2x^2 + a_4x + a_6
> Thanks.
>
> Jesper Stocholm
> Technical University of Denmark
No problem,
Doug
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Distributing private keys on the internet
Date: Wed, 27 Dec 2000 17:17:45 GMT
Bob wrote:
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Steve K) wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> >
> > On Wed, 27 Dec 2000 14:59:38 GMT, Bob <[EMAIL PROTECTED]>
> > wrote:
> >
> > >Is anyone in this newsgroup paranoid about distributing private
> > >keys over the Internet?
> >
> > Probably not. The whole point of asymmetric ciphers is that it's
> > safe to distribute public keys publicly. Unless someone has made a
> > completely unexpected breakthrough that allows them to factor the
> > product of two large (*very* large) prime numbers, public key crypto
> > is highly secure. The largest risk in public key encryption is that
> > the machines it is used on generally have network connections and
> > may be vulnerable to electronic break-ins.
> >
> > Knowing this gives the attacker no advantage, but allows anyone to
> > send plaintext down a one-way hole that only I can extract if from:
> >
>
> Well, I don't have a problem with public keys. Its the private keys.
>
> How do you send a private key securely over the Internet if a 3rd
> party is listening to everything you send and has your client software
> along with a good debugger that allows him to easily write a private
> key cracking program?
>
> I don't think private keys are safe to transmit over the Internet.
> Please, somebody tell me I'm wrong. I would love to be wrong...
Yup, you're wrong. If one uses a zero knowledge or asymmetric method to
encrypt the private keys first (SRP, DH, PK), then they can be sent
safely. Use SRP to establish an encrypted session, use it to send the
key. Use DH to establish an encrypted session, use it to send the key.
Send a public key, and have the other person use it to encrypt the
private key.
SRP or similar is best. I believe SRP has forward secrecy, so even if
an attacker later learns the short passphrase, a recording of the
session won't allow that attacker to get the longer shared secret.
SRP is only slightly less safe than having the client's private key sent
on a floppy through registered snail-mail. Of course, you still need to
securely send the password/passphrase, but this can be quite short,
especially since SRP need only during the very first communication
between client and server. SRP is not vulnerable to off-line attacks.
DH is ok, but is vulnerable to man-in-the-middle attacks.
If DH is used to encrypt, transfer, and decrypt the private key, this is
especially bad, since an active attack on the first session obtains the
private key, and after that, only passive attacks are needed.
If the DH generated shared secret is instead used as the private key,
that's slightly better, since a MITM attack will result in client and
server having different keys, and for an attacker to remain unobserved,
he MUST continue intercepting and modifying all future communications.
PK is vulnerable to MITM attacks, in the same manner as the first method
I mentioned for attacking DH. There are ways to thwart this, but even
then, it becomes like the second scenario I described for DH... still
vulnerable to MITM, but since client and server have different keys, the
attacker MUST continue intercepting and modifying all future
communications.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: "Jesper Stocholm" <[EMAIL PROTECTED]>
Subject: Re: ECDSA: adding the Point P with -P and restrictions of a & b
Date: Wed, 27 Dec 2000 18:23:34 +0100
Hi Doug,
"Doug Kuhlman" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Jesper Stocholm wrote:
> >
> > I am looking at the math defining ECDSA and there are a couple of
things, I
> > really don't get:
> >
> > 1.
> > What causes the retriction of a and b to be 4a^3+27b*2 != 0 mod p ? What
is
> > the effect of this ?
> >
> This is required to make sure the resulting variety is not singular. If
> 4a^3+27b^2 = 0 mod p, then the variety is genus 0, is not an elliptic
> curve.
>
> > 2.
> > When adding a point p with it's negative -p, ecdsa states, that
> >
> > P+ -P = (x,y)+(x,-y) = O ... but as far as I can see, this only holds
for
> > curves, that are symmetric arround the x-axis ... what if this wasn't
the
> > case ?
> >
> Well, your above question assumes the form y^2=x^2+ax+b (which only
^^^^^^^^^^^^
I assume, that you mean x^3, right ?
> works if the characteristic is not 2 or 3, BTW). Then it is symmetric
> around the x-axis. If not, then P = (x,y) has -P = (x,-y-a_1x - a_3)
> where the curve is given in the form
> y^2 + a_1xy +a_3y = x^3 + a_2x^2 + a_4x + a_6
>
this was exactly what I wanted ... and to Bob - I know, that my question was
a bit vague ... sorry about that ... :o)
/Jesper Stocholm
Technical University of Denmark
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Distributing private keys on the internet
Date: Wed, 27 Dec 2000 17:34:06 GMT
In article <92d04o$b9i$[EMAIL PROTECTED]>,
Bob <[EMAIL PROTECTED]> wrote:
> Is anyone in this newsgroup paranoid about distributing private keys
> over the Internet?
May I suggest that you do some reading before posting?
Look up "Diffie-Hellman". Look up "key transport" and "key agreement"
--
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: [EMAIL PROTECTED] (Ross Anderson)
Subject: Forward-secure Signatures and Compatible Weak Keys
Date: 27 Dec 2000 17:41:41 GMT
In some talks I gave in 1997-98, I put forward two observations on
public-key cryptology, concerning forward-secure signatures and
compatible weak keys. I did not publish a paper on either of them as
they appeared to be rather minor footnotes to public key cryptology.
But the work has been cited from time to time since (e.g., in Bellare
and Miner, ``A Forward-Secure Digital Signature Scheme'', in Crypto 99)
and I've been asked to write a permanent record.
I've finally got round to this. The note's on my web page, at
http://www.cl.cam.ac.uk/users/rja14/
Enjoy!
Ross Anderson
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Distributing private keys on the internet
Date: Wed, 27 Dec 2000 17:53:25 GMT
In article <92d5ie$fin$[EMAIL PROTECTED]>,
Bob <[EMAIL PROTECTED]> wrote:
<snip>
>
> Well, I don't have a problem with public keys. Its the private keys.
>
> How do you send a private key securely over the Internet if a 3rd
party
> is listening to everything you send and has your client software along
> with a good debugger that allows him to easily write a private key
> cracking program?
Huh? So he has written a private key cracking program. So what?
How does that help him recover a private key that has been sent in a
public key digital envelope?
>
> I don't think private keys are safe to transmit over the Internet.
Fortunately for the rest of us, what you think doesn't matter.
Go do some reading. You should especially do this reading before
posting again on this subject. Look up "key exchange protocols"
Public key methods may be used to transmit or agree upon private keys.
It doesn't matter if a 3rd party is listening. He can only get the
private key by breaking the public key.
Key agreement schemes are susceptible (without proper controls) to
impersonation/MITM attacks. You might think you are sending a key
to Bob, when in fact Bob is being impersonated by Carol. [and
variations on this theme]. The private key between Alice and Bob
does not get "compromised" because it never gets established. Instead,
Alice and Carol wind up sharing a private key and Alice winds up
thinking she is talking to Bob when she is really talking to Carol.
Such impersonation attacks are thwarted by proper
use of identity checking procedures (such as certificates) and
by key authentication techniques following the key exchange (i.e.
use of MacTags and keyed hashes). If properly followed, Alice
and Bob wind up sharing a private key, and either or both parties can
be certain that Carol has not stepped between them.
--
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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: polynomial permutation cipher
Date: Wed, 27 Dec 2000 18:59:01 +0100
Benjamin Goldberg wrote:
>
> Mok-Kong Shen wrote:
> >
> > Benjamin Goldberg wrote:
> > >
> > [snip]
> > > Here's a simple example:
> > > pt = a 128 bit value, or a poly of order at most 127
> > > ct[0..3] = each is a 32 bit value, or a poly of order at most 31
> > > py[0..3] = each is a different irreducible order-32 poly
> > > % = GF(2)[x] polynomial remainder (aka crc)
> > > * = GF(2)[x] polynomial multiplication
> > > + = GF(2)[x] polynomial addition (aka XOR)
> > >
> > > To encrypt, we take the crcs:
> > > for i in 0..3
> > > ct[i] = ( pt + x^128 ) % py[i];
> > >
> > > To decrypt, we use the CRT algorithm:
> > > pt = ct[0] * py[1] * py[2] * py[3] +
> > > ct[1] * py[0] * py[2] * py[3] +
> > > ct[2] * py[0] * py[1] * py[3] +
> > > ct[3] * py[0] * py[1] * py[2] +
> > > py[0] * py[1] * py[2] * py[3] + x^128;
> > >
> > > See? Lots of multiplications, but no inversions.
> >
> > I am certainly confused. But from the last equation,
> > one obtains
> >
> > ( pt + x^128) % py[0] =
> >
> > ct[0] * py[1] * py[2] * py[3] % py[0]
> >
> > How could one show that this is identical to ct[0]?
>
> Let t[0..3] be temp variables, and ignore for the moment the x^128 term.
> t[0] = ct[0] * py[1] * py[2] * py[3]
> Consider t[0] % py[1,2,3]. Since t[0] is a product of each poly, the
> remainder modulo any of them is 0. Now consider t[0] % py[0]. Since
> t[0] is a multiple of ct[0], t[0] % py[0] == ct[0] % py[0].
>
> These relationships hold true for all t[i].
But we have to show t[0] % py[0] == ct[0] !!
Please note in the equation I gave that the left hand side
is by definition ct[0] (according to your encrption part)
and the right hand side is computed using the equation you
gave in the decryption part, so this right hand side should
be identical to ct[0]. (Else please kindly point out which
point of my argument is erroneous.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Are the classical techniques so inferior?
Date: Wed, 27 Dec 2000 18:59:14 +0100
By the classical techniques I'll mean the prototypical ones,
namely the polyalphabetical substitution and the transposition,
which in our computer era will naturally be implemented as
substitution and permutation at the byte level, with the
the substitution table, the key stream that governs the
choice of the substitution columns and the permutation all
implemented with the help of a PRNG (which is generally only
statistically good but not crypto strong). There being no
block concepts, the entire message is treated as a whole,
i.e. the substitution pass goes from the beginning to the
end of the byte sequence being processed and the permutation
pass is also done on the whole file.
Are these oldy operations really inferior when compared to
what is done in the well-known modern block ciphers? It is
true that the classical techniques, at the time where the
unit of operations was the character of the normal English
alphabet, have been very well studied using techniques whose
names are often associated with famous cryptanalysts of the
past generation and the results have long since been
documented in a large number of classics of cryptology.
Probably as a direct consequence, these techniques are
generally only scantly treated in modern textbooks of
cryptography. However, we must notice that the majority of
modern block ciphers all have a fairly large number of
rounds and that it is evidently this repetition of operations
that essentially endow them with the claimed superior
performance. If one has a round consisting of a substitution
plus a transposition in the classical sense but implemented
in the modern version as delineated above and arranges to
have a sufficient number of rounds comparable (in magnitude)
to most of the modern block ciphers, would such a cipher be
inferior to the latter for any inherent reasons? I personally
don't yet see any concrete reasons for an affirmative answer
and hence should appreciate learning opinions from the
experts.
Thanks in advance.
M. K. Shen
===================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: ___(WANTED) UPDATED performance figures of elliptic curve
multiplications
Date: Wed, 27 Dec 2000 18:25:54 -0000
Have a look at the paper by Hankerson et al "Software Implementation of
Elliptic Curve Cryptography over Binary Fields" to be found at
http://cacr.uwaterloo.ca/tech_reports.html
Optimising the software for a particular bit-length of GF(2^m) curve, and
unrolling all the loops, certainly helps a lot. However there seems to be a
lot of fundemental disagreement as to the fastest way to implement. Some say
Affine co-ordinates are faster, others projective. Perhaps point-halving is
the way to go? Some say yes, others no. Karatsuba??
Maybe we need a competition...
BTW which Montgomery trick? - he has so many! I know of 2 which might be
relevant here - his representation of elliptic curves and a fast algorithm
for multiplication using same, and his fast method of using Affine
co-ordinates to add points on several curves simultaneously (by batching the
field inversions).
Mike Scott
"Robert Harley" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> kctang <[EMAIL PROTECTED]> writes:
> > I am looking for _UPDATED_ performance figures of elliptic curve
> > multiplications for bit lengths range from 150 bits to 300 bits.
> >
> > My primary interest is on _SOFTWARE_ EC multiplications, though
> > hardware results are also much desirable.
> >
> > It should be of value to have a list of _UPDATED_ EC multiplication
> > timings results over
> >
> > o GF(p),
> > o GF(2^n) using polynomial basis,
> > o GF(2^n) using optimal normal basis,
> > o GF(p^n),
>
> Stick to GF(p) and GF(2^n) with polynomial bases. Normal bases are
> slow. GF(p^n) may not be secure.
>
> Here are some times for field multiplications in GF(2^n) on a 750 MHz
> Alpha in microseconds:
>
> n time
> 163 0.48
> 193 0.64
> 239 0.92
>
> Who needs dedicated hardware with software this fast? =:^)
>
> In this case, an elliptic curve multiplication takes six field
> multiplications per bit (and some cheap stuff: four squares, three
> sums) using Peter Montgomery's trick. Count seven multiplications per
> bit and you won't be far off.
>
> Bye,
> Rob.
> .-. [EMAIL PROTECTED] .-.
> / \ .-. .-. /
\
> / \ / \ .-. _ .-. / \ /
\
> / \ / \ / \ / \ / \ / \ /
\
> / \ / \ / `-' `-' \ / \ /
\
> \ / `-' `-' \ /
> `-' http://www.xent.com/~harley/ `-'
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Block or stream cipher
Date: Wed, 27 Dec 2000 12:33:03 -0600
Wei Kok Ng wrote:
> I would like to know how you would decide whether to use a stream or
> a block cipher. In what situation would a stream cipher be more
> preferable than a block cipher and vice versa.
The choice should be obvious from considering system characteristics.
If data is transmitted (or stored) always in complete fixed-size
blocks, a block cipher is indicated, whereas if data is sent
asynchronously a bit, octet, or similar small unit at a time,
a stream cipher is indicated.
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: ECDSA: adding the Point P with -P and restrictions of a & b
Date: Wed, 27 Dec 2000 12:30:54 -0600
Jesper Stocholm wrote:
>
> Hi Doug,
>
> > Well, your above question assumes the form y^2=x^2+ax+b (which only
>
> ^^^^^^^^^^^^
> I assume, that you mean x^3, right ?
>
Yep. Typo. Sorry.
Doug
------------------------------
** 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
******************************
