Subject: [Cfrg] ECC Encryption questions

From: Robert Moskowitz <[email-masked]>
Date: Wed, 23 Jun 2010 17:08:34 -0400

Is there an ECC encryption algorithm similar to RSA Encryption?

       Alice generates her keypair and sends the public value to Bob.
       Bob uses the public value to encrypt cleartext C and transmits 
the cyphertext to Alice.
       Alice uses her private value to decrypt to recover C.

All I am finding is the ElGamal Encryption that uses keypairs from both 
Bob or Alice (or at least that is what I am reading at:  
http://en.wikipedia.org/wiki/ElGamal_encryption

The text I need to encrypt is short, typically 256 or 384 bits.

Is there a nice mnemonic for ElGamal Encryption using ECC?

Something like ECEGE?

It gets tiresome to write and read ECC ElGamal Encryption after it 
occurs more than once in a document...

---

From: "Andreasyan Ashot-C23793" <[email-masked]>
Date: Wed, 23 Jun 2010 17:16:48 -0400

As far as I know there is no similar algorithms to RSA but you can use
ElGamal technique.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Robert Moskowitz
Sent: Wednesday, June 23, 2010 2:09 PM
To: [email-masked]
Subject: [Cfrg] ECC Encryption questions

Something like ECEGE?

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 23 Jun 2010 17:27:16 -0400

> As far as I know there is no similar algorithms to RSA but you can use

Somebody asked me if just using ECDH would be more efficient. Generate 
the ECDH key and symmetrically encrypt the text. And I did not know then 
started looking more into ECEGE and saw that it was based on the 
Diffie-Hellman exchange. Gee, I missed that, not that I can't exchange 
keys, just thought I was getting an algorithm similar to RSA encryption. 
Tripped up again by reading too fast the 1st time through....

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 23 Jun 2010 19:02:30 -0400

On 06/23/2010 06:24 PM, Helger Lipmaa wrote:
> On Wed, 23 Jun 2010, Robert Moskowitz wrote:
>
>> Bob uses the public value to encrypt cleartext C and transmits the 
>> cyphertext to Alice.
> This is exactly what Elgamal (and every other PK cryptosystem) is doing.

This is NOT what I am reading at 
http://en.wikipedia.org/wiki/ElGamal_encryption and 
http://en.wikipedia.org/wiki/RSA

Help me out here a bit.

I am reading this that Bob is NOT using Alice's public value to encrypt 
the message, rather Bob also generates a keypair. He uses his private 
and Alice's public to encrypt the text. He sends his public and the 
cyphertext to Alice. Alice uses Bob's public value and her private value 
to decrypt the message. This is different from RSA where Bob does NOT 
generate a keypair to encrypt with Alice's public RSA value.

        Key generation

The key generator works as follows:

    * Alice generates an efficient description of a multiplicative
      cyclic group G\, of order q\, with generator
      <http://en.wikipedia.org/wiki/Generating_set_of_a_group> g\,. See
      below for a discussion on the required properties of this group.
    * Alice chooses a random x\, from \{0, \ldots, q-1\}.
    * Alice computes h = g^x\,.
    * Alice publishes h\,, along with the description of G, q, g\,, as
      her *public key <http://en.wikipedia.org/wiki/Public_key>*. Alice
      retains x\, as her *private key* which must be kept secret.

        [edit
        <http://en.wikipedia.org/w/index.php?title=ElGamal_encryption&action=edit&section=3>]
        Encryption

The encryption algorithm works as follows: to encrypt a message m\, to 
Alice under her public key (G,q,g,h)\,,

    * Bob chooses a random y\, from \{0, \ldots, q-1\}, then calculates
      c_1=g^y\,.
    * Bob calculates the shared secret s=h^y\,. Since a new s\, is
      computed for every message s\, is also called an ephemeral key
      <http://en.wikipedia.org/wiki/Ephemeral_key>.

The steps above can be computed ahead of time.

    * Bob converts his secret message m\, into an element m'\, of G\,.
    * Bob calculates c_2=m'\cdot s.
    * Bob sends the ciphertext (c_1,c_2)\, to Alice.

        [edit
        <http://en.wikipedia.org/w/index.php?title=ElGamal_encryption&action=edit&section=4>]
        Decryption

The decryption algorithm works as follows: to decrypt a ciphertext 
(c_1,c_2)\, with her private key x\,,

    * Alice calculates the shared secret s=c_1^x\,
    * and then computes m'=c_2 \cdot s^{-1}\, which she then converts
      back into the plaintext message m\,.

The decryption algorithm produces the intended message, since

    c_2 \cdot s^{-1} = m'\cdot h^y \cdot (g^{xy})^{-1} = m'\cdot g^{xy}
    \cdot g^{-xy} = m'.

Also it reads that if you want to encrypt a 256 bit value, you need to 
be using a 256 bit Elliptic Curve group. If you want to encrypt with a 
160 bit EC group, you are limited to a 160 bit string.

>
>>
>> All I am finding is the ElGamal Encryption that uses keypairs from 
>> both Bob or Alice (or at least that is what I am reading at:

---

From: Greg Rose <[email-masked]>
Date: Wed, 23 Jun 2010 18:02:57 -0700

Your detail is right, but your viewpoint is wrong. Yes, Bob  
effectively creates
a public key pair, but it is ephemeral, temporary, throw-away. All he  
has to do is generate a random number to be his secret key  
(effectively free), then exponentiate a couple of times to create the  
corresponding public key and message (similar in concept to the RSA  
exponentiation). Once he sends the message to Alice, he can (and  
should) throw away his ephemeral secret key. So don't think of it like  
that, think of it as some hoops Bob has to jump through to do  
encryption, just like (with RSA) he would have  to do random padding  
and stuff like that.

(I wrote exponentiation, but for ECC it's point multiplication, but I  
hope you've seen enough by now to know what I mean.)

Greg.

On 2010 Jun 23, at 16:02 , Robert Moskowitz wrote:

>>>      Bob uses the public value to encrypt cleartext C and  
>>> transmits the cyphertext to Alice.
> This is NOT what I am reading at http://en.wikipedia.org/wiki/ElGamal_encryption 
>  and http://en.wikipedia.org/wiki/RSA
>
> Help me out here a bit.
>
> I am reading this that Bob is NOT using Alice's public value to  
> encrypt the message, rather Bob also generates a keypair.  He uses  
> his private and Alice's public to encrypt the text.  He sends his  
> public and the cyphertext to Alice.  Alice uses Bob's public value  
> and her private value to decrypt the message.  This is different  
> from RSA where Bob does NOT generate a keypair to encrypt with  
> Alice's public RSA value.
>
> Key generation
> 	• Alice generates an efficient description of a multiplicative  
> cyclic group  of order  
>  with generator  
> . See below for a discussion  
> on the required properties of this group.
> 	• Alice chooses a random   
> from .
> 	• Alice computes .
> 	• Alice publishes , along  
> with the description of , as  
> her public key. Alice retains   
> as her private key which must be kept secret.
> [edit]Encryption
> The encryption algorithm works as follows: to encrypt a message  
>  to Alice under her public key  
> ,
>
> 	• Bob chooses a random  from  
> , then calculates  
> .
> 	• Bob calculates the shared secret  
> . Since a new  
>  is computed for every message  
>  is also called an ephemeral  
> key.
> 	• Bob converts his secret message  
>  into an element  
>  of  
> .
> 	• Bob calculates .
> 	• Bob sends the ciphertext   
> to Alice.
> [edit]Decryption
>  with her private key  
> ,
> 	• Alice calculates the shared secret  
> 	• and then computes  which  
> she then converts back into the plaintext message  
> .
> Also it reads that if you want to encrypt a 256 bit value, you need  
> to be using a 256 bit Elliptic Curve group.  If you want to encrypt  
> with a 160 bit EC group, you are limited to a 160 bit string.
>
>>
>>>
>>> both Bob or Alice (or at least that is what I am reading at: http://en.wikipedia.org/wiki/ElGamal_encryption
>>>
> <ATT00001..txt>

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 23 Jun 2010 21:27:35 -0400

On 06/23/2010 09:02 PM, Greg Rose wrote:
> a public key pair, but it is ephemeral, temporary, throw-away.

Thank you for this information.

> All he has to do is generate a random number to be his secret key 
> exponentiation).

I was under the impression that there is NOT a y for every x.  That Bob 
may have to choose a few secrets before one produces a valid point on 
the curve for his public key.

I got this impression from reading a number of ECC tutorials, many of 
which have tables of small values for x and y and the table is a bit sparce.

> Once he sends the message to Alice, he can (and should) throw away his 
> ephemeral secret key. So don't think of it like that, think of it as 
> some hoops Bob has to jump through to do encryption, just like (with 
> RSA) he would have  to do random padding and stuff like that.

So this is a static/ephemeral keying model.  What of a static/static 
model?  Why does Bob have to use an ephemeral pair?  If Bob uses an 
Ephemeral pair, he has to prove ownership if Alice wants to know the 
message came from Bob.  If he uses a static pair, that can be stored 
long-term (some definition of long) by Alice.

I can't see it as an attack against Bob's keypair unless there is 
something different from his versus Alice's.

> hope you've seen enough by now to know what I mean.)

Yes, I have figured that one out now.  :)

>> and her private value to decrypt the message.  This is different from 
>> RSA where Bob does NOT generate a keypair to encrypt with Alice's 
>> public RSA value.
>>
>> Key generation
>> . See below for a discussion on 
>> the required properties of this group.
>>     • Alice chooses a random  
>> from .
>>     • Alice computes .
>>     • Bob chooses a random  
>> from , then calculates 
>>  is also called an ephemeral key.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 23 Jun 2010 18:47:09 -0700

> Sent: Wednesday, June 23, 2010 9:28 PM
> To: Greg Rose
> Cc: Helger Lipmaa; [email-masked]
> Subject: Re: [Cfrg] ECC Encryption questions
> 

You misunderstand what ECDH does.  You don't try to pick a random value
for x, and see if it can be a part of a point (x, y).  As you point out,
about half the time, it won't work, and in any case, doesn't work as a
part of the larger protocol.

Instead, we have a well-known point G, and Bob picks a random integer n
(generally between 1 and the order of G), and computes the point nG
(using point multiplication).  This computation always succeeds (unless
n happens to be a multiple of the order of G, and if n is in the range I
recommended, that'll never happen).

n is the 'secret key' (and as all it is is a random integer within a
particular range, generating it is cheap)
nG is the 'public key' -- computing it involves point multiplication (or
as Greg calls it above, "exponentiation").

> something different from his versus Alice's.

The problem with both sides using static keys is that they'll always
derive the same shared secret.

> from
> >>     * Alice chooses a random 
> >>     * Alice computes .
> >>     * Alice publishes , along
> >>     * Bob chooses a random 
> >>     * Bob calculates the shared secret
> >> . Since a new
> >>  is computed for every
message
> >>     * Bob converts his secret message
> >>  into an element
> >>  of
> >> .
> >>     * Bob calculates .
> >>     * Bob sends the ciphertext
> >> to Alice.
> >> [edit]Decryption
> >>     * Alice calculates the shared secret
> >>     * and then computes 
which

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 23 Jun 2010 23:01:52 -0400

On 06/23/2010 09:47 PM, Scott Fluhrer (sfluhrer) wrote:
>> From: [email-masked] [mailto:[email-masked]] On Behalf
>>      
> Of
>    
>> Robert Moskowitz
>>> (effectively free), then exponentiate a couple of times to create
>>>        
> the
>    
>> I was under the impression that there is NOT a y for every x.  That
>>      
> Bob
>    

OH..... Now it is falling together.

> recommended, that'll never happen).

So if G is for a 256 bit Curves (eg Curve-ID: brainpoolP256r1 from RFC 
5639), n is 256 bits and the message, M is 256 bits, and the cyphertext 
is 512 bits.

If you use a static/static model, the shared secret is always the same. 
There is no way to introduce a nonce or such into the math to get a 
different key each time. If M is predictable, then S could be computed. 
If M is a nonce concatenated with a random number (the real session 
key), then I would think S cannot be computed.

More thought needed. And I need to go back are reread 800-56.

>>> Once he sends the message to Alice, he can (and should) throw away
>>>        
>> his
>>      
>>> (I wrote exponentiation, but for ECC it's point multiplication, but
>>>        
> I
>    
>>>>>>       Alice generates her keypair and sends the public value to
>>>>>>              
>> Bob.
>>      
>> transmits
>> on
>>>> from.
>>>>      * Alice computes.
>>>>      * Alice publishes, along
>>>> with the description of, as
>>>>   to Alice under her public
>>>>          
> key
>    
>>>> ,
>>>>
>>>>      * Bob chooses a random
>>>> from, then calculates
>>>> .
>>>>   is computed for every
>>>>      * Bob calculates.
>>>>>> All I am finding is the ElGamal Encryption that uses keypairs
>>>>>>              
> from
>    
>>>>>> It gets tiresome to write and read ECC ElGamal Encryption after
>>>>>>              
> it
>

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 23 Jun 2010 20:23:20 -0700 (PDT)

Hi Bob,

On Wed, June 23, 2010 8:01 pm, Robert Moskowitz wrote:
[snip]
> 5639), n is 256 bits and the message, M is 256 bits, and the cyphertext

  For the brainpoolP256r1 curve G is a point on the curve represented
by the x,y coordinates given in the domain parameter set for the curve
in section 3.4. The value n would be a number less than q (also in the
domain parameter set in section 3.4).

> key), then I would think S cannot be computed.

  El Gamal will use an ephemeral value to prevent the per-message
encryption key from being the same. So if Alice and (you) Bob have
static public keys you can still send each other encrypted messages
using the El Gamal cryptosystem and the per-message key will be unique.

  As a suggestion, and a plug, might I suggest using RFC 5297 to
protect your messages with the shared secret from an El Gamal-like
exchange? It will provide deterministic authenticated encryption with
associated data at a cost of another <block-size-of-cipher> bits of
ciphertext and it does not impose any unnatural restrictions on the
size of M.

  regards,

  Dan.

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 00:12:49 -0400

> domain parameter set in section 3.4).

And my reading of section 3.4 says this is a number less than 2^256-1.  
So I am calling it a 256 bit number for the sake of generality 
eventhough the number 19 is also within that range.  I suspose a 'smart' 
implementation would only select a large random number with few 
repeating bit strings?

> using the El Gamal cryptosystem and the per-message key will be unique.

So if there is one message per day, the encryption key is use 365 times 
in a year.  Let's call it 400 times for restart issues.  Each message 
has a known nonce with an unknown random session key.  The random value 
is much longer than the nonce.  What is the attack space?

> associated data at a cost of another<block-size-of-cipher>  bits of

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 23 Jun 2010 21:54:33 -0700 (PDT)

Hi Bob,

> implementation would only select a large random number with few

  Actually no, q is the number that starts A9FB57DBA....  A "smart"
implementation would ensure that 1 < private < q. To do this you can
derive a random number that's 256+64 bits long and then reduce it
modulo q.

> is much longer than the nonce.  What is the attack space?

  The security doesn't derive from secret components of the message.
Perhaps you're misreading the El Gamal definition. If "s" is the shared
secret and "M" is the message, then the wikipage you have referred to
shows C2 = M s and you can just do modular multiplication for that.
Decryption would be M = C2 s^(-1). The secret isn't part of the message,
it's just used to "encrypt" the message, if by "encrypt" you mean
multiply modulo a prime.

  But this is why I was suggesting SIV. The ciphertext sent would end up
being (C1, SIV(s,M,A)), where A is associated data (and may be NULL).
So now you have _authenticated_ encryption of a message of arbitrary
length and you can authenticate other stuff that's not encrypted. For
instance you could bind some state, or identities, to the message. Or
you could include your static shared key, derived from your static private
key and Alice's static public key, as associated data to provide some
authenticity to the sent message (to prove that it's really from you,
since anyone can send Alice an encrypted message). That seems much more
useful for a protocol than plain-jane El Gamal but I confess I am not
completely up to speed on your proposal.

  regards,

  Dan.

---

From: Dan Brown <[email-masked]>
Date: Thu, 24 Jun 2010 01:54:19 -0400

Why not use ECIES? It is standardized in SEC1, IEEE 1363A, ANSI X9.63, and ISO 18033-2.  It also has some provable security properties, which raw ElGamal lacks, yet is almost as efficient as ElGamal.

----- Original Message -----
From: Robert Moskowitz [mailto:[email-masked]]
Sent: Wednesday, June 23, 2010 05:08 PM
To: [email-masked] <[email-masked]>
Subject: [Cfrg] ECC Encryption questions

Something like ECEGE?

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 06:07:55 -0400

> Why not use ECIES? It is standardized in SEC1, IEEE 1363A, ANSI X9.63, and ISO 18033-2.  It also has some provable security properties, which raw ElGamal lacks, yet is almost as efficient as ElGama…

ECIES was mentioned to me in a private message.  I am trying to get 
access to some source that describes it.  Even though I am an IEEE 
member, that does not get me 1363A.  I am SUPPOSE to have access to ANSI 
as part of NIST CSWG review, but it is complex, but I got to try it 
today.  Where is SEC1?  And ISO, well I don't think I will be seeing an 
ISO document any time soon....

> To: [email-masked]<[email-masked]>

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 08:22:58 -0400

On 06/24/2010 01:54 AM, Dan Brown wrote:
> Why not use ECIES?

Back to needing a hash function.  At least that is what I see at

http://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

>   It is standardized in SEC1, IEEE 1363A, ANSI X9.63, and ISO 18033-2.  It also has some provable security properties, which raw ElGamal lacks, yet is almost as efficient as ElGamal.
>

---

From: Dan Brown <[email-masked]>
Date: Thu, 24 Jun 2010 10:20:25 -0400

For the SEC1 spec, see www.secg.org.  Use released version 2.0 of SEC1. 

As to a hashless requirement, SEC1 v 2.0 offers a substitute for HMAC for the integrity portion.  I think NIST is working on a special publication for KDF that includes a CMAC based version, so that may make possible a hashless ECIES, with SEC1 only needing minor updates.

How valuable is it to be "hash" free?  Should standardizers, eg IETF, be going out of their way to support such modes?

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 10:49:35 -0400

> As to a hashless requirement, SEC1 v 2.0 offers a substitute for HMAC for the integrity portion.  I think NIST is working on a special publication for KDF that includes a CMAC based version, so tha…

Thanks I will pursue this.  And I am working with a CMAC based KDF, 
using SP 800-108 and some ideas for the HKDF RFC.  But it requires a 
uniformly distributed key to feed into the KDF, or that is the claim in 
a number of documents.

> How valuable is it to be "hash" free?  Should standardizers, eg IETF, be going out of their way to support such modes?

There are these little devices, some of which are called sensors.  They 
pitch a fit for each 8K of code tossed on them and for each compute 
intense operation at a critical time.  They are often power limited as 
well as memory and processing limited.  How do we met the limitations of 
these devices and provide them with solid security solutions?  We have 
to strip out lots of what we use as a big hammer because one big hammer 
is easier for us to study then a couple of little hammers and screwdrivers.

So my goal has been to design a KMS with as little as possible and still 
meet as much of the claims as I have in HIP.  I mean I have HIP and with 
the revs in process it will be quite good for slightly limited systems 
like SmartMeters and such.  But even it has been called out as too much 
code and processing by the sensor vendors.

> Cc: [email-masked]'<[email-masked]>

---

From: Yoav Nir <[email-masked]>
Date: Thu, 24 Jun 2010 18:00:41 +0300

> is easier for us to study then a couple of little hammers and screwdrivers.

Strange, I thought that all PK operations, even the EC kind are so much more compute-intense than any symmetric key operations, that once you have to do them, a bit of hash function here and there doesn't matter.

> code and processing by the sensor vendors.

Yes, but hash functions are such useful screwdrivers. Can you actually do without them in any security-involved operation?

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 24 Jun 2010 11:23:31 -0400

> Strange, I thought that all PK operations, even the EC kind are so much more compute-intense than any symmetric key operations, that once you have to do them, a bit of hash function here and there…

I once thought that too. The hash function is still more. More code and 
more computing. And which PK operations? Just ECDH is much easier than 
ECDSA. And again if you need both, that is more code.

I hear some vendors say, that $1 per device to get it all. Others just 
cringe at such statements.

OK. I HAVE to have SOME PK operation, but what is the minimal code and 
usage scenario?

It has been quite a wakeup for me after years of going with the call to 
get some of that wonderful memory and processor growth for our use in 
security.