Subject: [Cfrg] ECC encryption

From: Robert Moskowitz <[email-masked]>
Date: Wed, 09 Jun 2010 07:30:09 -0400

I have been googling for a whole day without finding any information 
toward the following questions....

In ECC, is there an operation to encrypt with the 'private key' and 
decrypt with the public key? In otherwords is either key equally up to 
the task of encryption and decryption?

Or is the asymmetric nature of ECC really asymmetric in that one key 
only encrypts and the other only decrypts?   This is something I have 
always wondered about but could never find a definitive statement on.  
Always here is your private key, here is how to compute your public key, 
here is how to encrypt with the public and decrypt with the private...

How does ECC encryption get 'more expensive' as the string length (to 
encrypt) increases?  At what length is it better to encrypt a symmetric 
key and use say AES-CTR instead of ECC encryption over the whole 
string?  For this question, I did read section 11.4 in:

http://cseweb.ucsd.edu/users/mihir/cse207/w-asym.pdf

It seems that the general rule of asymmetric cost has lead to 'just do 
hybrid' behaviour.

---

From: David McGrew <[email-masked]>
Date: Wed, 9 Jun 2010 06:16:41 -0700

On Jun 9, 2010, at 4:30 AM, Robert Moskowitz wrote:

> decrypt with the public key? In otherwords is either key equally up  
> to the task of encryption and decryption?

I'm not sure what you mean here; I don't understand what encryption  
would mean if the decryption key was public.   I suspect that the  
short answer to your question is "no", and the longer answer is that  
if one wants a security service other than asymmetric encryption (such  
as digital signatures, say) then one should be using a crypto  
algorithm designed (and analyzed) with that particular security  
service in mind.

David

> only encrypts and the other only decrypts?   This is something I  
> have always wondered about but could never find a definitive  
> statement on.  Always here is your private key, here is how to  
> compute your public key, here is how to encrypt with the public and  
> decrypt with the private...
>
> How does ECC encryption get 'more expensive' as the string length  
> (to encrypt) increases?  At what length is it better to encrypt a  
> symmetric key and use say AES-CTR instead of ECC encryption over the  
> whole string?  For this question, I did read section 11.4 in:
>
> It seems that the general rule of asymmetric cost has lead to 'just  
> do hybrid' behaviour.
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Adam Back <[email-masked]>
Date: Wed, 9 Jun 2010 15:22:52 +0200

Yes and generally RSA is "special" in having the property that
signatures are even related to (and the inverse of) encryption.  Other
algorithms dont have this property.

Adam

On Wed, Jun 9, 2010 at 3:16 PM, David McGrew <[email-masked]> wrote:
>> decrypt with the public key? In otherwords is either key equally up to the
>> task of encryption and decryption?
>
> I'm not sure what you mean here; I don't understand what encryption would
> mean if the decryption key was public.   I suspect that the short answer to
> your question is "no", and the longer answer is that if one wants a security
> service other than asymmetric encryption (such as digital signatures, say)
> then one should be using a crypto algorithm designed (and analyzed) with
> that particular security service in mind.
>
> David
>
>>
>> Or is the asymmetric nature of ECC really asymmetric in that one key only
>> encrypts and the other only decrypts?   This is something I have always
>> wondered about but could never find a definitive statement on.  Always here
>> is your private key, here is how to compute your public key, here is how to
>> encrypt with the public and decrypt with the private...
>>
>> encrypt) increases?  At what length is it better to encrypt a symmetric key
>> and use say AES-CTR instead of ECC encryption over the whole string?  For
>> this question, I did read section 11.4 in:
>>

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 09 Jun 2010 09:47:24 -0400

On 06/09/2010 09:16 AM, David McGrew wrote:
> would mean if the decryption key was public.

One one level it is a general, theoretical question.  ECC offers an 
encyption/decryption 'service'.  Is the nature of ECC such that only one 
of the keys (derived, 'public' key) can encrypt and only the other 
('private' key) can decrypt?  Or can the 'private' key also be used for 
the encryption operation and the 'public' key decrypt those cypherbocks?

Is what we do (this key to encrypt and that to decrypt) simply a matter 
of convention or is it intrinsic in the underlying mathematics?

> I suspect that the short answer to your question is "no", and the 
> longer answer is that if one wants a security service other than 
> asymmetric encryption (such as digital signatures, say) then one 
> should be using a crypto algorithm designed (and analyzed) with that 
> particular security service in mind.

Then we can move on to a meta question.  What does it mean for a sender 
to encrypt a data stream that any holder of the public key can decrypt.  
How is this different, that is what services does it offer, that are 
different from 'digital signatures'.  I don't know.  I do know the meta 
question exists, provided that it can even be asked (that is the theory 
question can be answered with a yes, either can be used).

Why am I toying with this meta question?  Because digital signatures are 
built on hash functions.  Perhaps a different construct does not have 
this requirement.  It will have different issues and challenges.

We have just said, oh hash function.  We have that (or we have a few of 
them with varying costs and risks).  All of this with little regard for 
the cost.  It might work out that it IS the 'cheaper' to use over all 
anyway.  I have NOT been able to find any discussion on this.  Perhaps 
it has been lost in the ancient lore of asymmetric cryptography....

I will point out that 10 years ago we said, oh yes you symmetrically 
encrypt with one operation, then a separate operation does the 
authentication, what is the problem?  We now have 'duo modes of 
operation' that perform both functions as some of us presented the value 
in this and others worked it out.

>> always wondered about but could never find a definitive statement 
>> on.  Always here is your private key, here is how to compute your 
>> public key, here is how to encrypt with the public and decrypt with 
>> the private...
>>
>> encrypt) increases?  At what length is it better to encrypt a

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 09 Jun 2010 09:51:17 -0400

> algorithms dont have this property.

I lost what the 'yes' is answering.

Yes, only the private can encrypt and only the public decrypt?  And 
signatures (public undoes what private did) is a totally different set 
of operations?

thank you.

> Adam
>
> On Wed, Jun 9, 2010 at 3:16 PM, David McGrew<[email-masked]>  wrote:
>

---

From: Adam Back <[email-masked]>
Date: Wed, 9 Jun 2010 16:00:42 +0200

So with RSA encrypt with public, decrypt with private is raw RSA
encryption, and encrypt with private, decrypt with public is raw RSA
signature.

But take other algorithms: DSA it can only sign.  There is a private
key, but there is no encrypt/decrypt concept.

Take Elgamal encryption it can only encrypt.  There is no
signature/verify concept.

(Well Elgamal also invented a signature scheme related to DSA, but
that is not the same algorithm as Elgamal encryption).

The EC stuff is discrete log (just over more complex groups), and so
there are strong analogs with DSA and Elgamal-encryption and variants.
 ie as I said there is no signature/encryption inverse relationship.

(And in the case of DSA over EC its quite a direct analog - ECDSA!)

I was always curious if you could do RSA over EC, and I think you
could it just doesnt make sense as the short-key size advantage coming
from harder (per key size) discrete log on EC no longer holds for
"ECRSA".

Adam

On Wed, Jun 9, 2010 at 3:51 PM, Robert Moskowitz
<[email-masked]> wrote:
> signatures (public undoes what private did) is a totally different set of
> operations?
>
> thank you.
>
>> Adam
>>
>>>> only
>>>> key

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 9 Jun 2010 07:02:26 -0700 (PDT)

Hi Bob,

  ECC is just another type of discrete logarithm -style cryptography,
like finite field cryptography (exponentiation modulo a prime). It
doesn't have a special encrypt/decrypt capability. You have to use
ECC El Gamal to get that.

  regards,

  Dan.

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 09 Jun 2010 10:31:15 -0400

> signature/verify concept.

Adam, and others....

Thank you for your time to clearify this for me.

I see a 'crypto notes for semi-literates' coming out of this!  :)

> from harder (per key size) discrete log on EC no longer holds for

And thus the meta question (prior e-missive) need not be asked.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 10 Jun 2010 18:56:49 +1200

>would mean if the decryption key was public. 

My guess is that he's confusing ECC with RSA, or at least any time I've seen 
peculiar references to "encrypt with the private key" (and that's a fair 
number of times) it's come from someone reading about RSA signing in a 
textbook and then trying to apply that to things that aren't RSA.

Peter.

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 10 Jun 2010 05:48:54 -0400

On 06/10/2010 02:56 AM, Peter Gutmann wrote:
> David McGrew<[email-masked]>  writes:
>    

Peter,

Rather, coming for working with RSA for a long time and reading ECC in 
text books, you never come away feeling that the text books are clear on 
ECC mechanisms.  Note that one responder on the list said you could feed 
the numbers either way into the algorithm.

And now I am remembering conversations I was in back at IETF meetings 
while the RSA patent was still enforce about ElGamal encryption as an 
alternative...

I am good now, and am working within the parameters.

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 11 Jun 2010 00:17:58 +1200

Robert Moskowitz <[email-masked]> writes:

>Rather, coming for working with RSA for a long time and reading ECC in text
>books, you never come away feeling that the text books are clear on ECC
>mechanisms.

I've always blamed the books that describe RSA signing as "encrypt with the
private key" rather than signing, possibly drifting a bit off-topic here but I
think the problem is that once you've planted this meme into people's minds it
becomes dominant, and everthing else doesn't stand a chance.  So it's not so
much ECDSA (or DSA, or Elgamal, or ...) being explained badly as RSA being
explained inappropriately.

(To book authors and educaters everywhere, please, please talk about "signing"
and not "encrypt with the private key", the number of times I've had to
reverse-engineer what someone is trying to do based on multiple rounds of
emailed descriptions of an RSA private-key operation... sigh).

Peter.

---

From: David McGrew <[email-masked]>
Date: Thu, 10 Jun 2010 05:32:40 -0700

+1

---

From: Adam Back <[email-masked]>
Date: Thu, 10 Jun 2010 14:32:59 +0200

And then there are times when the implementor accidentally swaps the
private and public key.  (Which I've seen, the perpetrator shall
remain nameless).

Its a feature if the algorithm outright fails if you swap public and
private the keys.

Adam

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 10 Jun 2010 10:27:19 -0400

On 06/10/2010 08:17 AM, Peter Gutmann wrote:
> Robert Moskowitz<[email-masked]>  writes:
>
>    

All the more incentive for me to take the 'refresher course' I have had 
here this past couple weeks and turn it into some crypto notes and get 
it posted somewhere.  Look for some text next week

---

From: Gé Weijers <[email-masked]>
Date: Fri, 11 Jun 2010 11:36:37 -0700

> emailed descriptions of an RSA private-key operation... sigh).

Add patent attorneys to that group. Lots of patents "encrypt with the 
private key" when they're attempting to describe a digital signature. Which 
makes it questionable whether they apply to anything using a discrete log 
based signature.

Gé

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 12 Jun 2010 17:22:49 +1200

=?UTF-8?Q?G=C3=A9_Weijers?= <[email-masked]> writes:

>Add patent attorneys to that group. Lots of patents "encrypt with the private
>key" when they're attempting to describe a digital signature. Which makes it
>questionable whether they apply to anything using a discrete log based
>signature.

I see this as a feature, not a bug :-).

Peter.