Cryptography-Digest Digest #935, Volume #10 Thu, 20 Jan 00 08:13:01 EST
Contents:
Forward secrecy for public key encryption, and identity-based crypto (David Hopwood)
Re: Forward secrecy for public key encryption (David Hopwood)
Re: LSFR ("Michael Darling" noral<dot>co<dot>uk>)
Re: NIST, AES at RSA conference (Terry Ritter)
Re: McDonald's claims Nobel peace fries (Idiot/Savant)
Re: McDonald's claims Nobel peace fries [off-topic] (David Hopwood)
elliptic curve ("Hank")
Re: Predicting Graphs. ([EMAIL PROTECTED])
Re: elliptic curve ([EMAIL PROTECTED])
----------------------------------------------------------------------------
Date: Thu, 20 Jan 2000 08:59:57 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Forward secrecy for public key encryption, and identity-based crypto
=====BEGIN PGP SIGNED MESSAGE=====
John Savard wrote:
>
> On Sat, 15 Jan 2000 07:47:49 +0000, David Hopwood
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Normally, I wouldn't trust an identity-based protocol, because
> >the identity-based model has several inherent security problems:
> > - the "trusted" authority has enough information to calculate
> > any user's private key, and therefore is a weak point of the
> > whole system (to a greater extent than root CAs in a CA-based
> > system).
> > - it's impossible for users to verify that their keys aren't
> > being "escrowed".
> > - private keys have to be sent from the authority to each user,
> > which is likely to be another weak point.
>
> >However, none of these objections apply to a forward-secure
> >scheme constructed using this method, because each user is their
> >own trusted authority.
>
> I am puzzled about how such a scheme is going to work. If the
> condition that must be fulfilled for an identity-based scheme is that
> to send messages to user X, all you need to know is user X's identity,
> and don't have to download a public key,
Yes (technically this is an "ideal" identity-based scheme, according
to the terminology in Handbook of Applied Cryptography Remark 13.27,
which is what we need for this construction).
> then if I can compute the key
> for sending messages to user X from that identity myself, and if user
> X can compute the key for reading those messages himself from his
> identity,
No, X is *given* his secret key (supposedly via a secure channel or in
person) by the trusted authority, who is the only one who can calculate
it from X's identity.
(It's the ideal set-up for covert key escrow, which is one reason why
I would never recommend using a identity-based scheme directly.)
In the forward-secrecy construction, we delete the "authority"'s
private information at the end of key pair generation, so that no-one
can recalculate private keys after that point. The authority cannot
cheat the user by failing to delete the information, because the
authority is the user. Also, the problem of how to securely transmit
the private key from the authority to the user doesn't arise.
> doesn't it follow that *everybody* who knows user X's
> identity can compute both keys, and read all the messages?
It would follow, but your premises are wrong.
> On the other hand, two users certainly can engage in ordinary
> public-key communication without the help of a trusted authority, and
> the identity can play some trivial additional role in complicating the
> protocol without changing its security.
I agree entirely. I don't think that identity-based schemes are secure
or particularly useful, except that they happen to be a neat way of
constructing a scheme that provides non-interactive forward secrecy,
which would be extremely useful.
If it isn't clear, it's worth stressing that the scheme resulting from
the construction is not identity-based. It would use conventional
means such as certificates, key servers, verification of hashes
over an authentic channel, etc., to ensure the authenticity of public
keys.
> I hope you can supply a simple explanation of how what you are trying
> to achieve differs from either of the two scenarios above, and can
> genuinely be thought of as being, in some sense, an identity-based
> scheme without a trusted authority (which would indeed be immensely
> useful if it were possible).
It isn't possible. There has to be something which distinguishes the
owner of an identity from anyone else who just knows the identity.
That "something" must be access to secret information (technically
if it was a real-world object that can be reliably recognised but is
difficult to forge, that might not apply, but real-world objects can't
be sent over communication channels).
The problem is therefore to associate an identity with an algorithm
that performs one side of a protocol (such as encryption or signature
verification), such that the other side of the protocol can only
be performed by someone possessing the secret.
[Here an "algorithm" includes any parameters, such as public keys,
that it uses.]
Suppose that an attacker may be computationally more powerful than
any party involved in the protocol (this is a basic assumption of
modern strong cryptography). If we start off with an identity
that has no a priori association with a secret (like an email
address or a name, for example), then everyone, including potential
attackers and potential trusted authorities, is in the same position
with regard to their ability to specify an association between
identities and the corresponding algorithms.
To resolve this situation, there are only three possibilities (for
two-party protocols):
- maintain the association yourself (in which case you need to
send some secret data to the other user over a secure channel;
this is just symmetric cryptography)
- trust the second party to maintain the association (in which
case they need to send you some secret data; this is also
symmetric cryptography)
- trust a separate third party.
[Of course, it would in principle be possible to start off with some
secret data for each user, and then assign "identities" dependent on
that data - for example you could adopt the convention that email
addresses always include a hash of an associated public key, or you
could generate a private key for people at birth and make the public
key part of their name (which would have to be changed in order to
revoke the key :-). But that wouldn't solve the "problem" (if it is
in fact a problem) that identity-based crypto set out to address,
which is to allow the identity to be something that is memorable,
and that would have to be known anyway in order to interact with the
given user.]
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOIbOfjkCAxeYt5gVAQGjFwf/U8aYlKGq28k6YgW0yiAqUg74DEI7hCuD
n9WZ0haAvkznP2kShAaVGeFj5UB18EQhD9I+4lE0EL2en7mkQYFA2TxmtkhxHHMs
4IWAOvJzK2g7C98dNbNeGo1R+9Gs/p38q1wNydxUaYCR4dRT01ynE7wN3M1uT8oM
Lj1ubt6dlOi4drFMO2GCMomxx6cb80TGx4vD+bBe+4To3LqoW7OA21XWwqTK2oVi
FJB0T3W4lUFowPB/CDkROFjvr5anljpE6HfX5HS8JtaUVLwDNTavNlS1iyZgZUAQ
KC6QL1EvEwd1h8+2VxjCFLhKdbeKWxgLa9zvHPP4ZZDm0RyuvGuTJA==
=/hJ/
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 20 Jan 2000 09:04:08 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Forward secrecy for public key encryption
=====BEGIN PGP SIGNED MESSAGE=====
John Savard wrote:
>
> On Sat, 15 Jan 2000 07:47:49 +0000, David Hopwood
> <[EMAIL PROTECTED]> wrote:
>
> >The security property I'm trying to achieve is this: The validity
> >period of each public key is split into several time periods,
> >numbered say 1..T. Each time the current period changes, the
> >holder of the private key applies a one-way "key evolution" function
> >to his/her current private key value, and deletes the old value. When
> >a message is encrypted, the current time period (say t) is specified
> >as input to the encryption algorithm. It should not be possible to
> >decrypt that message without having the private key value for
> >period t or earlier.
>
> Ah, so you're not trying to construct an identity-based encryption
> scheme, you are merely using one as a component.
Yes.
> >The alternative approach involves constructing a forward-secure
> >encryption scheme from an "ideal" identity-based encryption
> >scheme.
>
> >The basic idea is that the private key holder (Bob) takes on the
> >role of the trusted authority (Trent) at key generation time, and
> >then each of the users of the identity-based scheme in turn; each
> >"user" corresponds to a time period.
>
> In an identity-based scheme, Trent has to generate private keys
> whose corresponding public keys are unpredictable small numbers
> corresponding to the identities; the scheme is secure because the time
> required to do this is large, but doing this once for all users is
> acceptable, while doing it once to crack a single user's mail is not.
You must be thinking about some specific subclass of identity-based
schemes (which sound even less secure than the ones I'm thinking
of). Where did you get this description from?
In the class of schemes we're considering, the public key is related
to the private key by a trap-door one-way function (which happens to
be f(x) = g^x mod m). Trent has the trap-door information for f (in
this case the factorisation of m), and can therefore invert f, i.e.
compute private keys from public keys. In order for this to work, the
function used to calculate a public key from an identity must be
dependent on some information specific to Trent (i.e. his public key).
Note that this is separate from the trap-door one-way function used
for encryption/decryption (which for Elgamal would be the probabilistic
function E(M) = (g^k, M*y^k), where k is chosen at random; the trap-door
for E is a *specific* private key, log_g(y)). The two trap-doors must
be related to each other in such a way that one can be used to
calculate private keys for the other, which is quite tricky to
arrange.
> So in this type of method, both users, in order to communicate, have
> to spend as much time computing as a cracker would to read their
> messages! Unless one isn't using a totally "identity-based" scheme,
> but is also using "Trent's public key" to carry part of the load.
Yes, Trent's public key does have to be known to all users.
(I agree this is another disadvantage of the identity-based scheme,
but in the constructed scheme we aren't trying to avoid per-user
public keys, and so Trent's public key just becomes part of the
user, Bob's.)
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOIbPNDkCAxeYt5gVAQFAswf+L3QFLd2qOOxBJd/g5kjdMJ8gkkucUHqG
H2BrQmmaMJhUrhr9YlnbAI6PmEnezrah2nEYdYJGCpvekf5yD2OCM+zrVWGmSoII
9TwPc5f2FqH5tySBZmub3nMDtLUQGy1YO6ksFiJmA4Y2dGbI/S2xchdf3pugeMTK
2w/+yd/7rLVP2gY9ntG1OsC4juzdD0qpFtnQrirRih+v/N02ZTlPXC8HZEUc7V3O
GI1alnIJyFvTXQvYQSPPrlZR7s3rHkAJHuGYRXnPIVzOWS8AJrbQNhOm3zztVABG
l9QEgOOrcELzxLLwuFCcMLrODGQrGilCIrpxWjjebJt7LL7zkpdstg==
=fVyK
=====END PGP SIGNATURE=====
------------------------------
From: "Michael Darling" <michaeld<at>noral<dot>co<dot>uk>
Subject: Re: LSFR
Date: Thu, 20 Jan 2000 09:10:44 -0000
Thanks for this suggestion, I have passed it on to our electronics guys top
investigate.
Regards,
Mike.
Terje Mathisen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> (posted and emailed)
>
> "Michael Darling noralco" wrote:
> >
> > Hi Rob, Thanks for your reply.
> >
> > We could indeed use a binary counter - and that is what we will do if we
> > cannot solve this problem.
> > However the binary counters suffer from carry propagation delays whereas
an
> > LSFR wouldn't, this
> > gives us a big boost in speed which is what we need. I'll pass on the
log
> > array synchronous counter
> > info to our electronics bods and see what they think. Meanwhile thanks
for
> > the link.
>
> You have another quite simple approach:
>
> Use a carry-save adder!
>
> This doubles the amount of storage needed, but the electronics becomes
> dead simple:
>
> Each stage of the counter will have two inputs:
>
> carry_in and data_in
>
> and it will generate two outputs:
>
> carry_out and data_out
>
> The truth table is obvious:
>
> carry_in 0 0 1 1
> data_in 0 1 0 1
>
> carry_out 0 0 0 1
> data_out 0 1 1 0
>
> I.e. carry_out = data_in AND carry_in, data_out = data_in XOR carry_in
>
> To sample this counter, just read both the data and carry array, and add
> them together.
>
> To do this in sw for a 64-bit counter I'd use code like this:
>
> static u64 data, carry;
>
> void increment(void)
> {
> u64 temp_carry;
>
> // Generate the new carry array:
> temp_carry = data & carry;
>
> // Generate the next state of the data array:
> data = data ^ carry;
>
> // Shift up the carry array and set the bottom bit, ready for the next
> iteration:
> carry = (temp_carry << 1) | 1;
> }
>
> So, to generate this counter, you'll need to use a single two-input XOR
> and a similar two-input AND gate, with the bottom bit of the carry array
> hardwired to shift in '1' bits.
>
> The latches needed to be able to read out the current value of the
> counter will take more hardware than the counter itself, but this is
> true for the LFSR approach as well.
>
> Terje
>
> --
> - <[EMAIL PROTECTED]>
> Using self-discipline, see http://www.eiffel.com/discipline
> "almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: NIST, AES at RSA conference
Date: Thu, 20 Jan 2000 09:41:27 GMT
On Thu, 20 Jan 2000 07:41:14 GMT, in <866e6o$i0e$[EMAIL PROTECTED]>, in
sci.crypt Hammer <[EMAIL PROTECTED]> wrote:
>I attended a track at the RSA Conference today in which NIST spoke on
>the AES standard, the process, where it's at, etc.
>
>One of the interesting things I took from the talk was, in my opinion,
>they are nearly BEGGING for cryptanalysis of the AES finalists.
First of all, *OF* *COURSE* they are *begging* for cryptanalysis; they
certainly are not *paying* anything!
It was first of all wrong and secondly unwise to base the future of a
networked society on ciphers acquired by begging and contribution.
The lack of a direct financial consequence for cipher designers fails
to establish a for-profit industry of cipher construction, with
continuing -- read that as "paid" -- commercial research and
development. With no profit motive at all, we are simply not going to
have many experts in the field. Oh, what a surprise!
Now, I have endured a whole raft of semi-flame responses about how it
should be such a privilege to submit a cipher to NIST, even without
compensation, and how bad it is to patent cipher technology. Alas,
some of us have lives, and must somehow *fund* our research -- to say
nothing of dinner. Well, the situation is exactly the same for
cryptanalysts and indeed anyone else who is asked to simply
*contribute* serious effort while the guy next door is out making big
bucks.
In the end, no big-name cryptanalyst -- nor any set of such people --
can "certify" that a cipher is strong. Absent some new mathematical
proof of cipher strength, the very *best* we can get from this process
is a "maybe strong" cipher. But I am still waiting for NIST to make
it clear to the eventual AES customer what a fragile assurance that
might be.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Idiot/Savant)
Subject: Re: McDonald's claims Nobel peace fries
Date: Thu, 20 Jan 2000 10:26:21 GMT
On 19 Jan 2000 20:56:10 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
>Peace on Earth and Big Macs to all men
>
>by James Langton
[...]
>New research in America has uncovered a previously unrecognised
>fact of diplomacy: no country with a McDonald's has ever gone to
>war with another.
Wasn't there a McDonalds in Belgrade?
------------------------------
Date: Thu, 20 Jan 2000 10:03:07 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: McDonald's claims Nobel peace fries [off-topic]
=====BEGIN PGP SIGNED MESSAGE=====
Guy Macon wrote:
> New research in America has uncovered a previously unrecognised
> fact of diplomacy: no country with a McDonald's has ever gone to
> war with another.
Counterexamples:
- UK against Argentina.
- Western countries against Iraq,
- NATO countries against Serbia,
- Russia against Chechnya.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOIbcsDkCAxeYt5gVAQHIJQgAiQa63rdPULyCBD2TM19x+aVjntzAHr4w
yga2rhFvvikV7KFPj6u6pUBG53fdMgpO6+Tdo677ZSFPGpfmM0Rj5LtPk2LsZmAj
su2TtCtFIDGW9oXT0foF5kCDMccYpl1M/JS9FOyK0lvyHXDHrZNQ6zVXCGgh9c6G
vDTx79/HeK0/4o/kHmo0E3WMlqcOuEYbAv+nNpFkVrT17F/Fx7HGe5q71a0w5p00
qyh9n7+yKKP1bVY3Ts7Z0FHmSGlI+jdor29zEj4Wtc+olMeS5+LoLLo1xEeVScKs
eBRASS5u6Vet59I7fxibAuqUk5nnJGRPwP4u4FiRbZgEWKQcKOmbZA==
=V2ky
=====END PGP SIGNATURE=====
------------------------------
From: "Hank" <[EMAIL PROTECTED]>
Subject: elliptic curve
Date: Thu, 20 Jan 2000 18:45:10 +0800
What is 'elliptic curve' ? And how it is applied in cryptography ?
Can anyone answer me...or tell me where I can find information on this..
Thanks a lot.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Predicting Graphs.
Date: Thu, 20 Jan 2000 11:03:30 GMT
On Wed, 19 Jan 2000 22:03:47 GMT, [EMAIL PROTECTED] wrote:
>Is it possible to predict the course of a curved line graph with a
>computer? Could a computer simulate this graph up to numbers the size
>of 10^300?
No
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: elliptic curve
Date: Thu, 20 Jan 2000 12:43:02 GMT
On Thu, 20 Jan 2000 18:45:10 +0800, "Hank"
<[EMAIL PROTECTED]> wrote:
>What is 'elliptic curve' ? And how it is applied in cryptography ?
>Can anyone answer me...or tell me where I can find information on this..
>
>Thanks a lot.
---<begin excerpt from RSA Labs FAQ>---
Question 2.3.10. What are elliptic curves?
Elliptic curves are mathematical constructions from number theory and
algebraic geometry, which in recent years have found numerous
applications in cryptography.
An elliptic curve can be defined over any field (e.g., real, rational,
complex), though elliptic curves used in cryptography are mainly
defined over finite fields. An elliptic curve consists of elements (x,
y) satisfying the equation
y^2 = x^3 + ax + b
together with a single element denoted O called the �point at
infinity,� which can be visualized as the point at the top and bottom
of every vertical line. (The elliptic curve formula is slightly
different for some fields.)
Addition of two points on a elliptic curve is defined according to a
set of simple rules. The addition operation in an elliptic curve is
the counterpart to modular multiplication in common public-key
cryptosystems, and multiple addition is the counterpart to modular
exponentiation.
Elliptic curves are covered in more recent texts on cryptography,
including an informative text by Koblitz N. Elliptic curve
cryptosystems. Mathematics of Computation, 48: 203-209, 1987.
---<end excerpt>---
The full FAQ can be found at http://www.rsasecurity.com/rsalabs/faq/
See section above and also Section 3.5: Elliptic Curve Cryptosystems
------------------------------
** 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
******************************
