jeeq: ECDSA encryption

[jackjack]

Hey all
I read everywhere that ECDSA can't be used to encrypt
The fact is it can, I made a basic implementation: https://github.com/jackjack-jj/jeeq

It uses a kind of secret sharing and it looks like that works well
It's in python and requires no dependencies

Code:

> pubkey='0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'.decode('hex')
> print encrypt_message(pubkey,"goodbye world!")
amoAAAJQkgEDcToivOFhH0zhaytsAKbW9dKCmOJ25FMPaj/6WssXAQKsSJpnq1IlNOx7GZbg++x6ZRUXAb/3jxaxwPGqlcItmA==

Code:

> pvk = str_to_long('0000000000000000000000000000000000000000000000000000000000000001'.decode('hex'))
> print 'output:', decrypt_message(pvk, msg_to_decrypt, verbose=True)
Public header (size:2): 0x5092
  Version: 0
  Checksum of pubkey: 5092
Private header (size:6): 0x0000000e75f1
  Message size: 14
  Checksum: 75f1
Decrypted message: goodbye world!
  Hash: 75f1
  Corresponds: True
output: ['goodbye world!', True]

My concern is about the security, can a crypto-pro give it a quick look? I'm sure it's as sure as signing because breaking it would need the same discrete logarithm than in Bitcoin but well, you never know...



Edit: I'd be happy to receive some crypted messages, you can find my public key on blockchain.info

[1715554419]

1715554419

[1715554419]

1715554419

[1715554419]

1715554419

[1715554419]

1715554419

[etotheipi]

Did you look at ECIES?

[Zeilap]

You've come up with ElGamal encryption independently. Pretty impressive .

[jackjack]

Did you look at ECIES?

No, but as I understand the wikipedia article, it seems a bit more complicated (or maybe it's just because I'm not comfortable with KDFs and HMACs)
Can it be used with ECDSA private keys?

You've come up with ElGamal encryption independently. Pretty impressive .

Yeah that's true it's really similar! Not being a crypto guy (even though I'm rather good at maths) I can't imagine I'm the only one who tried that kind of things, so why is it not used?

Also, as I understand the article my implementation seems secure

[Shevek]

Did you look at ECIES?

No, but as I understand the wikipedia article, it seems a bit more complicated (or maybe it's just because I'm not comfortable with KDFs and HMACs)
Can it be used with ECDSA private keys?

AFIK, HMAC is needed only when you use a non self-authenticate symmetric encryption. For example, CTR mode must be used with external authentication (HMAC). But, in principle, CBC does not need HMAC (and so don't KDF, because the shared secret can be used as the single key).

[archaeopteryx]

Did you look at ECIES?

No, but as I understand the wikipedia article, it seems a bit more complicated (or maybe it's just because I'm not comfortable with KDFs and HMACs)
Can it be used with ECDSA private keys?

You've come up with ElGamal encryption independently. Pretty impressive .

Yeah that's true it's really similar! Not being a crypto guy (even though I'm rather good at maths) I can't imagine I'm the only one who tried that kind of things, so why is it not used?

Also, as I understand the article my implementation seems secure

I'm not a crypto expert, but if your implementation is truly the same as ElGamal, well it is being used. For example, Pretty Good Privacy implementations use ElGamal as one of the options.

[jackjack]

AFIK, HMAC is needed only when you use a non self-authenticate symmetric encryption. For example, CTR mode must be used with external authentication (HMAC). But, in principle, CBC does not need HMAC (and so don't KDF, because the shared secret can be used as the single key).

Hmm ok I think I get it, I'll look into an ECIES implementation to see how they handle that

I'm not a crypto expert, but if your implementation is truly the same as ElGamal, well it is being used. For example, Pretty Good Privacy implementations use ElGamal as one of the options.

I meant ElGamal with ECDSA. ElGamal is only with DSA, doesn't it?

[jackjack]

I just pushed a new version
You no more need to mess with the code, -i, -k and -o options handle files and data

Example:

Code:

#ENCRYPTION (-e)
python jeeq.py -e                                                 #Will ask for the text to encrypt, the recipient's public key and will print the output
python jeeq.py -e -i secretkeys.txt                               #Will ask the recipient's public key, will encrypt secretkeys.txt and will print the output
python jeeq.py -e -i secretkeys.txt -o encryptedsk                #Will ask the recipient's public key, will encrypt secretkeys.txt and will write the output to the file encryptedsk
python jeeq.py -e -k 0499a6037487a0ea0ae4867f7e60a6c4ac477103b4d3ed9ce8c84804a32f53ff802633de6e8ccd6a9b13fab97a29b0bda794576613f5abc17b40d993629c457aae
               #Will ask for the text to encrypt, will use the given recipient's public key and will print the output

#DECRYPTION (-d)
python jeeq.py -d                                                 #Will ask for the text to decrypt, the recipient's private key and will print the output
python jeeq.py -d -i encryptedsk                                  #Will ask the recipient's private key, will decrypt encryptedsk and will print the output
python jeeq.py -d -i encryptedsk -o secretkeys-decrypted.txt      #Will ask the recipient's private key, will decrypt encryptedsk and will write the output to the file secretkeys-decrypted.txt
python jeeq.py -d -k 0000000000000000000000000000000000000000000000000000000000000001
               #Will ask for the text to decrypt, will use the given recipient's private key and will print the output

The options are of course mixable

[Qwedcxza1]

I'm not a programmer so it's difficult to understand this without seeing a proper mathematical description of the encryption and decryption methods.
If it uses elliptic curves then I doubt if you have reinvented EIGamal crypto system.
There are hybrid cryptosystems based on elliptic curves such as ECIES but the plain text is not required to be a point on the curve.
 The problems of using elliptic curve implementations of EIGamal rather than discrete logarithm implementations relate to message expansion factors and difficulties of deterministically generating points on the curve which is why hybrid solution such as ECIES are used.
 Generally I would say that home made crypto systems should be approached with caution. There are plenty of good crypto systems out there.

[jackjack]

I'm not a programmer so it's difficult to understand this without seeing a proper mathematical description of the encryption and decryption methods.
If it uses elliptic curves then I doubt if you have reinvented EIGamal crypto system.
There are hybrid cryptosystems based on elliptic curves such as ECIES but the plain text is not required to be a point on the curve.
 The problems of using elliptic curve implementations of EIGamal rather than discrete logarithm implementations relate to message expansion factors and difficulties of deterministically generating points on the curve which is why hybrid solution such as ECIES are used.
 Generally I would say that home made crypto systems should be approached with caution. There are plenty of good crypto systems out there.

Let's say I want to encrypt 'hello' to your address

pubkey: your public key
privkey: your private key

I split my message in 32-char long chunks and put "0x00"s at the end of the last one to make it 32-char long too. That gives here only one chunk: 'hello---------------------------'. ('-' represents one 0x00)

Now each chunk is used as an X. Let's call the correponding point M (Two M's are possible but it doesn't matter as I never use Y)
Then I take a random N and calculate:

• G*N
• pubkey*N + M

Those points are the encrypted data to be sent to the recipient. As pubkey=privkey*G, M is easily calculated.



Note: Not all X values leads to a point on the EC. In such cases I just use offsets.

[oleganza]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

[Qwedcxza1]

I'm not a programmer so it's difficult to understand this without seeing a proper mathematical description of the encryption and decryption methods.
If it uses elliptic curves then I doubt if you have reinvented EIGamal crypto system.
There are hybrid cryptosystems based on elliptic curves such as ECIES but the plain text is not required to be a point on the curve.
 The problems of using elliptic curve implementations of EIGamal rather than discrete logarithm implementations relate to message expansion factors and difficulties of deterministically generating points on the curve which is why hybrid solution such as ECIES are used.
 Generally I would say that home made crypto systems should be approached with caution. There are plenty of good crypto systems out there.

Let's say I want to encrypt 'hello' to your address

pubkey: your public key
privkey: your private key

I split my message in 32-char long chunks and put "0x00"s at the end of the last one to make it 32-char long too. That gives here only one chunk: 'hello---------------------------'. ('-' represents one 0x00)

Now each chunk is used as an X. Let's call the correponding point M (Two M's are possible but it doesn't matter as I never use Y)
Then I take a random N and calculate:

• G*N
• pubkey*N + M

Those points are the encrypted data to be sent to the recipient. As pubkey=privkey*G, M is easily calculated.



Note: Not all X values leads to a point on the EC. In such cases I just use offsets.

To be honest with you, I'm a bit busy and I haven't got time to study all of this. I'm really not knowledgeable enough to be properly commenting on this stuff anyway so I hope it does work and I'm going to retire and let you find some real experts.

[jackjack]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's indeed much more efficient
Just out of curiosity, is it possible to tweak this a bit to make the sender unable to read the crypted message?

[oleganza]

How about using ECC point multiplication and AES:

[...]

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's indeed much more efficient
Just out of curiosity, is it possible to tweak this a bit to make the sender unable to read the crypted message?

What do you mean? Sender must know the message it is about to send.

[jackjack]

How about using ECC point multiplication and AES:

[...]

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's indeed much more efficient
Just out of curiosity, is it possible to tweak this a bit to make the sender unable to read the crypted message?

What do you mean? Sender must know the message it is about to send.

I was thinking about the private key s. The computer I'm using everyday should be safe but I wouldn't trust it for something risky.
If I use your method, the computer may keep s somewhere (HDD, RAM, bash history, etc) and if it's compromised the attacker might be able to retrieve it and decrypt the message.

Now that I'm writing it I realize that the same goes for the message and the random N...

[Shevek]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's OK but:

1) There is no need of doubling SHA256 to obtain the symmetric key. SHA256^2 is a bitcoinish thing that does not improve the security of SHA256. In fact, there is no need of SHA256. Take "Kx" as symmetric key and it's ok.
2) It is better to use "S" as the shared secret and send "K" to the recipient. She can get the secret "S" as S = r^(-1) * K. This way, you can send the same encrypted message to many recipients: just create the K1, K2, K3, etc, pubkeys for de recipient's keys R1, R2, R3, etc

[jackjack]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's OK but:

1) There is no need of doubling SHA256 to obtain the symmetric key. SHA256^2 is a bitcoinish thing that does not improve the security of SHA256. In fact, there is no need of SHA256. Take "Kx" as symmetric key and it's ok.
2) It is better to use "S" as the shared secret and send "K" to the recipient. She can get the secret "S" as S = r^(-1) * K. This way, you can send the same encrypted message to many recipients: just create the K1, K2, K3, etc, pubkeys for de recipient's keys R1, R2, R3, etc

2. Indeed!
1. Wouldn't you lose one bit of entropy? (As only half of x values between 0 and n-1 leads to a pair of points)
Using Kx+(Ky&1) should make it a bit better right?

[Shevek]

1. Wouldn't you lose one bit of entropy? (As only half of x values between 0 and n-1 leads to a pair of points)
Using Kx+(Ky&1) should make it a bit better right?

Uhmm... if you don't want to leak even a single entropy bit, I think it's better SHA256(K)

[oleganza]

2) It is better to use "S" as the shared secret and send "K" to the recipient. She can get the secret "S" as S = r^(-1) * K. This way, you can send the same encrypted message to many recipients: just create the K1, K2, K3, etc, pubkeys for de recipient's keys R1, R2, R3, etc

This is smart. Thanks for suggestion.

[oleganza]

I was thinking about the private key s. The computer I'm using everyday should be safe but I wouldn't trust it for something risky.
If I use your method, the computer may keep s somewhere (HDD, RAM, bash history, etc) and if it's compromised the attacker might be able to retrieve it and decrypt the message.

Now that I'm writing it I realize that the same goes for the message and the random N...

If you are trusting your computer with your message, you can trust it to hold a secret for a fraction of a second. Once you send out a message, simply clear the secret from memory, so it's not swapped on disk or otherwise extracted due to some corruption later on (it's a standard security practice, btw: put some secret in memory, use it, then zero it out ASAP).

[crypto_trader#43xzEXrP]

Just leave here my implementation of Elliptic-Curve-Cryptography (ECC): https://github.com/username1565/mini_ecdsa/commit/54d2ba23973819806e85456941c3c1a099434bc7
Encrypt-decrypt messages, using elliptic curve bitcoin secp256k1. Draft code. Tests added, and working.

[gmaxwell]

Just leave here my implementation of Elliptic-Curve-Cryptography (ECC):

The above posters archive implements a similar totally cryptographically busted technique as was originally discussed in this thread.

No one should ever use it, unless like.. you're trying to trick your enemies into using something insecure.

[See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-March/004720.html and following posts.]

[crypto_trader#43xzEXrP]

Just leave here my implementation of Elliptic-Curve-Cryptography (ECC):

The above posters archive implements a similar totally cryptographically busted technique as was originally discussed in this thread.

No one should ever use it, unless like.. you're trying to trick your enemies into using something insecure.

[See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-March/004720.html and following posts.]

Hm, I see the in text, the link on which you did provided,
there is info about ECIES, KDF-function, and some oracle value.

But the script which I'd posted earlier, there is not using any KDF-function and oracle.
There is using the multiplication of points (for encrypt) and division (to decrypt),
and this multiplication and division is making to secret skalar (priv_key),
which can be a long number (up to n, - the number of unique points on elliptic curve in finite field).
But, if the same value will be used to multiply many points,
in this case, maybe, there is some frequency analysis vulnerability,
if some values of original points will be known for attacker...

So I think will be better using some Key Derive Function (KDF) - to derive the key for each block...
For example, encrypt by next way:

Code:

encrypted_point = ( current_point * (priv_key XOR (hash( the coordinates from next not encrypted point) )
or NUL no any next point) ).

In this case:

Code:

decrypted point = ( current_point / (priv_key XOR (NULL if no privious point,
or hash( the coordinates from previous  decrypted point) ) ).

But, if attacker will know the original point, and know encrypted point,
he cann't get key, because point cann't be divided to the point, on elliptic curve in finite field:
Else:

Code:

Q = k*G; Q/G = k; where Q = pubkey, G - generator point (predefined for EC), k - privkey for bitcoin address;

And, as you can see, the second operation is impossible easy, because ECDLP.
But... For many points, with the same key, maybe, it will be mush easier.
That I meaning, with "frequency analysis vulnerability", so regullary changing the key will be not superfluous.

Also, as you can see, when message is encoding, the information redundancy appears.
This is probably why elliptic cryptography is not used anywhere and not developed,
because it is easier to use symmetric ciphers,
which have a ciphertext length equal to the length of the message.
Nevertheless, here is the code, you can research it, conduct an audit, start test, optimize and develop it.