DSA Vulnerability in ECDSA

I have implemented a ruby code where i generate private and public keys as below.

However, I read few articles [1] on DSA and why it should not be used. I'm not good at cryptography. But still wanted to know whether my implementation is vulnerable to recover public/private key?

$group = ECDSA::Group::Secp256k1$private_key = 1 + SecureRandom.random_number($group.order - 1)$public_key = $group.generator.multiply_by_scalar($private_key)


Your confusion seems to be between DSA, the discrete signature algorithm and the Elliptic Curve variant ECDSA. The answers to the question you point to already seem to make a distinction between the two, which this answer won't re-iterate.

The key size of 256 bits is considered secure for Koblitz curves such as SECP256K1. So if used correctly the shown code is secure when it comes to the algorithms and key sizes used. Using a bad random number generator for ECDSA signatures is known to lead to catastrophic loss of key material.

Notes:

• using a single-person implementation of ECC is not recommended: there is a bigger chance of implementation mistakes or side channel attacks (e.g. during the multiplication to calculate the public key or signature generation);
• SECP256K1 provides somewhat less than 128 bits of security, which is currently not feasible to crack (although the bit size is slightly at the low side). But EC(DSA) is vulnerable against attacks from future quantum computers (and so is DSA).

The mathematical principle in the Ruby code is OK: it aims at generating a private key in range $[1\dots\mathtt{$group.order}-1]\$, then the corresponding public key, for the Elliptic Curve secp256k1 (used e.g. by Bitcoin's ECDSA signatures). This is believed to give near 128-bit security, good for a decade.

How secure that really is depends primarily on the integrity of the computer where the code is run, on how carefully the private key is used, and on the quality of SecureRandom.random_number.

The problem discussed in the linked question discuss DSA (not ECDSA) being deprecated in some contexts, because

• In many Linux distributions, DSA private keys used to be generated by a broken random number generator, making many of them easy to guess. Getting rid of DSA is a simple, sure, and acceptably annoying way to fix vulnerability to this issue.
• DSA often was used with 1024-bit base group, and that does not give adequate security margin by today's standards (although public attacks are far below that threshold).

The closest thing to a commonality between that and the question's code is that if SecureRandom.random_number was not secure, what's done would be unsafe.

• Wow. Thanks for the explanation. Even I was sure about the SecureRandom .. because, Java had Vulnerabilities in secure random implementation which came to light in 2013. Commented Jun 28, 2018 at 11:50
• ECDSA (standard, without rfc6979) also fails if bad RNG, and DSA can use larger groups (and subgroups) though that isn't required since rfc4253 references FIPS186-2 (before 2048 and 3072 were added in -3). However rfc4253 'bakes in' SHA1 for DSA, whereas rfc5656 for ECDSA uses SHA2; see crypto.stackexchange.com/questions/15051/… Commented Jun 29, 2018 at 6:26