Elliptic Curve Cryptography - Simple question about encrypting a message

AARRRGH

Hello

I hope someone can help me with this.

This is how I am encrypting via elliptic curve cryptography -

1. Alice and Bob are both using the same curve, field size, type of maths and base point.
2. Alice and Bob both generate a public and private key.
3. The following algorithm is used by Bob to encrypt a message for Alice -

c = {bobPrivate * (basePointX, basePointY), (mx, my) + (bobPrivate * (alicePublicX, alicePublicY))}

- where (mx, my) is the message I am encrypting. It is a geometric point.

Question: if I wanted to encrypt the letter "a", how would I convert it into a geometric point (i.e. mx, my) so it can be encrypted?

Apologies if this is a dumb question.

Any help greatly appreciated!

Thanks

Steve

sobriquet

I've no experience of ECC at all, so sorry if this is a dumb suggestion: perhaps you could take the integer representation of a given character and use that? (That is, 'a' being 97.) You could get its' two highest factors and use those. That way the entire ASCII table is covered. You could xor (or another operation, mathematical or bitwise) the value with a magic number to modify it to something less predictable. Not that it'd make any odds.

Alternately you could take the bit representation of 97 (or whatever) and manipulate and recombine it into two numbers. Say, X from the highest 16 bits and the reversed lowest 16 bits, some other transform for Y.

Actually, thinking about it, all of this would be redundant, you might as well just create a lookup table for character/(x,y) coord pairs. If the operation has to be two way then this'd work, but if it must only be one way then you'd need some kind of hashing algorithm and take say the 32 highest bits for X, lowest for Y. (Assuming int32_t, 64 for doubles.)

Is this kind of thing what you mean? I would have thought that the ECC spec provided for it. No idea whether they'd introduce any problems or insecurity.

AARRRGH

Thanks Sobriquet. You have some good ideas there.

None of the books on the subject explain the relationship between the message/geometric point. Not sure why they chose to skip that part...

I'll continue to investigate. Maybe I do need to do something, like select the two highest factors, as you suggest.

Thanks.

DublinDilbert

sobriquet wrote: »

I've no experience of ECC at all, so sorry if this is a dumb suggestion: perhaps you could take the integer representation of a given character and use that? (That is, 'a' being 97.) You could get its' two highest factors and use those. That way the entire ASCII table is covered. You could xor (or another operation, mathematical or bitwise) the value with a magic number to modify it to something less predictable. Not that it'd make any odds.

Alternately you could take the bit representation of 97 (or whatever) and manipulate and recombine it into two numbers. Say, X from the highest 16 bits and the reversed lowest 16 bits, some other transform for Y.

Actually, thinking about it, all of this would be redundant, you might as well just create a lookup table for character/(x,y) coord pairs. If the operation has to be two way then this'd work, but if it must only be one way then you'd need some kind of hashing algorithm and take say the 32 highest bits for X, lowest for Y. (Assuming int32_t, 64 for doubles.)

Is this kind of thing what you mean? I would have thought that the ECC spec provided for it. No idea whether they'd introduce any problems or insecurity.

Surely you could not use this approach as the letter "a" would always map to the same piece of cipher text, hence it would be very easy to break, based on simple statistical approaches, eg "t" is the most common letter in the English language.

One of the ways symmetric encryption over comes this problem by "or'ing" the message with a counter before encryption. I'm not sure if this is required in ECE. The whole idea of ECE is that it can asymmetrically encrypt a message, unlike say RSA that could only be used to asymmetrical encrypt a key.....

sobriquet

dublindude wrote: »

Maybe I do need to do something, like select the two highest factors, as you suggest.

If so, like I said, you might be as well to just use a fixed lookup table for values and pick some arbitrarily given that they'll compute the same every time anyway. Doesn't OpenSSL implement ECC crypto? Maybe have a look at what they do.

DublinDilbert wrote: »

Surely you could not use this approach as the letter "a" would always map to the same piece of cipher text, hence it would be very easy to break, based on simple statistical approaches, eg "t" is the most common letter in the English language.

I mentioned that in the last sentence, I've no idea whether that presents a problem or not - I've no idea of how ECC works as distinct from traditional PK crypto.

My understanding from dublindudes post is that it's the X, Y coords that are encrypted, not the plaintext, so (X, Y) becomes the ciphertext, not 'a'. Decrypting gives you (X, Y) which must then be transformed back to a given character. Am I mistaken? I'll try to read up about it this evening.

AARRRGH

sobriquet wrote: »

My understanding from dublindudes post is that it's the X, Y coords that are encrypted, not the plaintext, so (X, Y) becomes the ciphertext, not 'a'. Decrypting gives you (X, Y) which must then be transformed back to a given character.

That seems to be the case. The books on ECC are pretty bad, so it's hard to find readable information on the subject.

There must be a simple way of doing this...

sobriquet

It may be redundant, but have you seen this? Standards for Efficient Cryptography 1: Elliptic Curve Cryptography.

Section 2.3 covers Data Types and Conversions seems to cover the methods of converting bit strings (your ASCII text, I assume) to octet strings (padded for byte alignment), and octet strings to EC Points, which looks pretty gnarly. If this is the right reference it's probably what OpenSSL and the likes implement.

AARRRGH

Ah, good find! I will have a read of that tonight. It might be just what I need. Hopefully it's not too tricky.

Thank you for your help.

AARRRGH

Right, I figured this out. I'm not sure if this is of interest to you guys, but maybe it'll save one of you some hassle in the future:

How to convert a message into a point on the curve:

1. The field I am using has twenty-three field elements. This means I can embed two bytes on the curve, with seven bits spare. (Note: I suspect my figures might be wrong. Does a field size of twenty-three mean twenty-three bits? I need to research this.)
2. My message is the letter “a”. This is decimal 97 or 01100001.
3. I will represent my message as two bytes: one byte for the message and one byte as extra bits. The extra bits are used to ensure the message will fit on the curve.
4. The two bytes will be treated as the x value.
5. Assume my curve is as follows: y2 = x3 + 3x + 5.
6. The points on this curve are:
   (1, 3), (1, 20), (3, 8), (3, 15), (4, 9), (4, 14), (6, 3), (6, 20), (7, 1), (7, 22), (8, 9), (8, 14), (9, 5), (9, 18), (10, 0), (11, 9), (11, 14), (14, 10), (14, 13), (16, 3), (16, 20), (17, 1), (17, 22), (18, 7), (18, 16), (22, 1), (22, 22)
7. Does 01100001 00000000 fit on the curve? (Is this decimal 256 + 8192 + 16384 = 24832?)
8. y2 mod 23 = 248323 + 3 * 24832 + 5 mod 23
   y2 mod 23 = 15312112132869 mod 23
   y2 mod 23 = 21
9. There is no point on the curve with an x value of twenty-one, so I must increment the message by one.
10. Does 01100001 00000001 fit on the curve? (Is this decimal 1+ 256 + 8192 + 16384 = 24833?)
11. y2 mod 23 = 248333 + 3 * 24833 + 5 mod 23
    y2 mod 23 = 15313962092041 mod 23
    y2 mod 23 = 9
12. There is a point on the curve with an x value of nine, so y is either five or eighteen.

As you can see, I chose to use one byte as the extra bits; I could have used any number of bits up to a limit of fifteen (i.e. 8 + 15 = 23). As the message receiver will not know how many extra bits I used, he must use the same ECC implementation (i.e. the exact same code) as me. This will ensure he knows how many extra bits were used during encryption.