I am working on a very resource-constrained environment. Using a standard peer reviewed library isn't possible because it won't fit within the RAM requirements of the device (~5K unused ram without crypto). The library I've modified is called microecdsa, and the way it chooses k is as follows.
for (;;) {
// generate random number k
for (i = 0; i < 8; i++) {
k.val[i] = random32() & 0x3FFFFFFF;
}
k.val[8] = random32() & 0xFFFF;
// if k is too big or too small, we don't like it
if (k.val[5] == 0x3FFFFFFF && k.val[6] == 0x3FFFFFFF && k.val[7] == 0x3FFFFFFF && k.val[8] == 0xFFFF) continue;
if (k.val[5] == 0x0 && k.val[6] == 0x0 && k.val[7] == 0x0 && k.val[8] == 0x0) continue;
// compute k*G
scalar_multiply(&k, &R);
// r = (rx mod n)
mod(&R.x, &order256k1);
// if r is zero, we try different k
for (i = 0; i < 9; i++) {
if (R.x.val[i] != 0) break;
}
if (i == 9) continue;
inverse(&k, &order256k1);
temp = 0;
for (i = 0; i < 8; i++) {
temp += (((uint64_t)read_be(priv_key + (7 - i) * 4)) << (2 * i));
da->val[i] = temp & 0x3FFFFFFF;
temp >>= 30;
}
da->val[8] = temp;
multiply(&R.x, da, &order256k1);
for (i = 0; i < 8; i++) {
da->val[i] += z.val[i];
da->val[i+1] += (da->val[i] >> 30);
da->val[i] &= 0x3FFFFFFF;
}
da->val[8] += z.val[8];
multiply(da, &k, &order256k1);
mod(&k, &order256k1);
for (i = 0; i < 9; i++) {
if (k.val[i] != 0) break;
}
if (i == 9) continue;
// we are done, R.x and k is the result signature
break;
}
The issue is, using this code above I can only generate legitimate signatures occationally. If I modify the first few lines to be the following the signatures always validate. Leaving the code unmodified leads to the signatures being invalid semi-regularly.
// generate random number k
for (i = 0; i < 8; i++) {
k.val[i] = 1;
if(i>0 && i <8){
k.val[i] = random32() & 0x3FFFFFFF;
}
}
k.val[8] = 1;
Is this a safe modification? Meaning that the I've only eliminated 48 bits of entropy and we still have 224 bits of entropy, or am I misguided. If an attacker knows the first four bytes and the last two bytes of k, can they compromise the security of the key.
Also as a side note if you know of any safe and low resources ecdsa secp256k1 implementation please let me know.
Thank you.
random32()
return cryptographically secure random numbers? $\endgroup$ – forest Apr 9 at 0:48