kmackay / micro-ecc Goto Github PK

I have been able to run the C version of micro-ecc on my Arduino. However I get errors when
compiling the ASM procs. Please help. I don't know AVR ASM. I just would like to use the faster option. Thank you.
Dave Henderson

Compiler errors reported:

C:/Arduino/myArduinoLibs/Ecc/asm_avr.inc:137: error: can't find a register in class 'POINTER_Y_REGS' while reloading 'asm'
C:/Arduino/myArduinoLibs/Ecc/asm_avr.inc:137: error: can't find a register in class 'POINTER_Y_REGS' while reloading 'asm'
(repeats above line 6 times)
C:/Arduino/myArduinoLibs/Ecc/asm_avr.inc:137: error: 'asm' operand has impossible constraints
(repeats above line 6 times)

Code:

static uint8_t vli_add(uint8_t *p_result, uint8_t *p_left, uint8_t *p_right)
{
uint8_t i = uECC_BYTES;
uint8_t l_carry = 0;
uint8_t l_left;
uint8_t l_right;
asm volatile (
"clc \n\t"

    "1: \n\t"
    "ld %[left], x+ \n\t"  /* Load left byte. */
    "ld %[right], y+ \n\t" /* Load right byte. */
    "adc %[left], %[right] \n\t" /* Add. */
    "st z+, %[left] \n\t"  /* Store the result. */
    "dec %[i] \n\t"
    "brne 1b \n\t"

    "adc %[carry], %[carry] \n\t"    /* Store carry bit in l_carry. */

    "sbiw r28, " STR(uECC_BYTES) " \n\t" /* Restore Y */

    : "+z" (p_result), "+x" (p_left), [i] "+r" (i),
        [carry] "+r" (l_carry), [left] "=&r" (l_left), [right] "=&r" (l_right)
    : "y" (p_right)
    : "cc", "memory"
);

return l_carry;

}

I'm using this test power of different signature methods and for some reason the creation of 1020th signature fails every time, while 1019 before it work fine. What are the possible reasons for signature failure?

Compiling for atmega328p

lib/ecc/uECC.c: In function 'vli_modMult_fast':
lib/ecc/asm_avr.inc:15497: error: can't find a register in class 'POINTER_Y_REGS' while reloading 'asm'
lib/ecc/asm_avr.inc:130: error: can't find a register in class 'POINTER_Y_REGS' while reloading 'asm'
lib/ecc/asm_avr.inc:130: error: can't find a register in class 'POINTER_Y_REGS' while reloading 'asm'
lib/ecc/asm_avr.inc:130: error: can't find a register in class 'POINTER_Y_REGS' while reloading 'asm'
lib/ecc/asm_avr.inc:15497: error: 'asm' operand has impossible constraints
lib/ecc/asm_avr.inc:130: error: 'asm' operand has impossible constraints
lib/ecc/asm_avr.inc:130: error: 'asm' operand has impossible constraints
lib/ecc/asm_avr.inc:130: error: 'asm' operand has impossible constraints

TI CC2538 has hardware acceleration on ECC related operations. Is there any plan to implement that?

Hello!

Any chance to support compressed ECDSA signatures?
http://www.google.com/patents/WO2008058377A1?cl=en

Thanks

I want to use your wonderful library for message signing in Bitcoin. However, the standard bitcoin signature format includes 2 extra bits: "recid" or "recovery id". This value captures which of the four possible X values that (R, S) imply and allow the specific public key to be recovered from the signature itself. The process is nicely described in this answer on stackexchange.

The problem is uECC_sign_with_k does the right math, and makes valid signatures, but the values I need for recid are not exposed.

I am tempted to change/extend your code to capture these values during the signing process. However, it's a bit beyond my pay grade. What are your thoughts?

I'm trying to compile this for a nRF51 chip (contains a Cortex-M0). If I set these flags -O0 -fomit-frame-pointer then it only gives me warning

Compiling file: uECC.c
C:\Users\vahid\AppData\Local\Temp\ccL0nRJa.s: Assembler messages:
C:\Users\vahid\AppData\Local\Temp\ccL0nRJa.s:279: Warning: register range not in ascending order
C:\Users\vahid\AppData\Local\Temp\ccL0nRJa.s:279: Warning: register range not in ascending order
C:\Users\vahid\AppData\Local\Temp\ccL0nRJa.s:301: Warning: register range not in ascending order

But if I set the flag to -O, -O1 or -O2 then it results in an error.

Compiling file: uECC.c
C:\Users\vahid\AppData\Local\Temp\ccPQcEDS.s: Assembler messages:
C:\Users\vahid\AppData\Local\Temp\ccPQcEDS.s:121: Error: invalid immediate for address calculation (value = 0x0000000A)
make[1]: *** [_build/uECC.o] Fel 1

(Fel means error in Swedish)
The flag -O3 generates many errors of the above type.
By the way I sat the flags -O0 -S and then looked inside the generated uECC.o file. One of the push instructions on row 279 looked like this

3: 
push {r3, r7, r6, r5} 

I think this is the cause of the warning above.

Hi,

Have you checked if the micro-ecc implementation is compliant with NIST SP800-56A?
http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf

Since the new checkin I get warnings and an error. I can fix it with compiler flag I think but I wanted you to know.

uECC.c:1242:29: warning: passing argument 1 of 'hash_context->init_hash' discards 'const' qualifier from pointer target type
...
uECC.h:299:5: note: previous declaration of 'uECC_sign_deterministic' was here

I have a feature request. Is it possible that you change your library in the way that more than one curve can be used simultaneous. We have an application using different curves in runtime and would love to use your lib furthermore. I would be very thankful if you could make a statement about this, so that we could plan our project. Thank your very much!!

In the 'old' branch there was a function called ecc_valid_public_key() that checked to make sure a provided public key consisted of X,Y coordinates that weren't zero and evaluated to a point on the curve.

Was there a reason that it was removed in the master?

I guess this is more of a question or possibly feature request than an issue.

How hard would it be to implement the Koblitz curve secp256k1 instead of secp256r1?
I naively tried to replace the curves and constants straight of but that resulted in strangeness. I then delved a little deeper and realized there's some curve specifics in the code and would like to know if it's feasible to modify the code or if it'll be a rewrite all together.

Here's a description of the curve:
http://www.secg.org/collateral/sec2_final.pdf

Hello,
please, I come back to you Mr. I lost in optimization to run the mico-ecc in my environment, the issue when I run the ecc- signature generation it took more 19 seconds please, I lost more time (more than 4 months) to have results as you found less than 2 seconds.
I am working on "cortus aps 32 bits as platform". please I want to understand how you got the very good answers time results, I don't know If I need to write the assembly for the function that take time in calculation, if needed please help me.
Please, I would be very grateful if you could help me asap to resolved this issue.
Thank you so much

I try to use this library in a iPhone app. After I included uECC.c, uECC.h and asm_arm.inc into my project folder, I fail to build the project due to "Unknown register name in asm_arm.inc". The architecture of iOS app is arm64, armv7 and armv7s. So did I include a wrong .inc file? Thanks.

I was wondering what multiplication algorithm was used in asm_arm.inc inlines(static branch). I tried to improve it speed writing own asm multiplication inline using 'umaal' instruction, which accumulates two numbers along multiplication, but it was slower than yours asm inline (150ms vs 158ms on NucleoF401RE@48MHz signature computation time). My inline. Was there some reason not to use this instruction, but make additions separately?

Hi @kmackay ! Sorry about the unorthodox use of issues for this question.

I'm integrating uECC into my PhD project, on the CC2530 SoC. It's an 8051 processor, with a tiny stack, so I'm adjusting the way memory is used in uECC.

I'm trying to figure out what the difference between uECC_WORDS and uECC_N_WORDS is. Can you enlighten me?

Hi Ken,

I was looking over the implementation of ecdsa_sign() and was wondering about of the generation of the k value. The algorithm effectively performs a simple modulo of the supplied random value against the configured curve's order (n). This would appear to bias the generation of k towards lower values.

Now as I understand it (and I readily admit I may have it wrong), this sort of bias can lead to a leak of the private key provided an attacker can gather enough sample signatures. To this end, SEC1 and NIST SP800-90 specify a variety of algorithms to convert random bit strings into numbers while maintaining a uniform distribution. The ecc_make_key() function also uses a similar modulo approach to generating a private key, however the issue may not be as concerning in this situation as it is for ECDSA.

So my 'issue' is twofold: 1) Do I correctly understand the effect of the code in ecdsa_sign(); and 2) Was there a reason you didn't go with one of the algorithms from SEC1/SP800-90?

BTW, thanks for making this code available. It's great to have a simple yet compact implementation of ECC code that's open source.

Jay

In file ecc.c, in function EccPoint_mult, the type of the last parameter p_numBits is missing.

Using "unsigned" without any further type qualifiers implies 'unsigned short'. This should be explicitly defined with something more appropriate like uint8_t or uint16_t (and preferably the platform natural word size) instead of just "unsigned".

1. easy-ecc supports secp128r1 but the project seems to be abandoned, do you plan to add support of this curve in micro-ecc?
2. Small question about public key, why is it ECC_BYTES + 1 in easy-ecc
   and uECC_BYTES*2 ins micro-ecc ?

Thanks in advance

The ecc.[ch] source files should have copyright and license notices, especially since you actually recommend copying those specific files into projects.

We use your library in our Cortex M0 hardware. We track the performance on each test build. Unfortunately the graphic shows that the performance has gone down noticeable since commit 0e249d9. Have you planned to work on this?
We use uECC_OPTIMIZATION_LEVEL=4 is this right or should I change it? Should I add other defines to get better performance? Thanks for your help!

Hi,

I'd like to use your uECC library for my master thesis. I need a function to do point addition on a curve (aG+bG, a and b are integers). So I wrote the following code at the end of uECC.c:

typedef struct key_pair{
  uECC_word_t d[uECC_BYTES];
  EccPoint Q;
} key_pair;

void print_bytearray(uint8_t *bytes, int length){
  int i = 0;
  for(i = 0; i < length; i++){
    printf("%x ", *(bytes+i));
  }

}
void print_point(EccPoint point){
  printf("(\n");
  print_bytearray(point.x, sizeof(point.x));
  printf(",\n");
  print_bytearray(point.y, sizeof(point.y));
  printf(")\n");
}


 void EccPoint_add(EccPoint *  p_P, EccPoint *  p_Q, EccPoint *  p_result){
    uECC_word_t P_x[uECC_WORDS];
    uECC_word_t P_y[uECC_WORDS];
    uECC_word_t Q_x[uECC_WORDS];
    uECC_word_t Q_y[uECC_WORDS];

    vli_set(P_x, p_P->x);
    vli_set(P_y, p_P->y);
    vli_set(Q_x, p_Q->x);
    vli_set(Q_y, p_Q->y);

    XYcZ_addC(P_x, P_y, Q_x, Q_y);

    vli_set(p_result->x, Q_x);
    vli_set(p_result->y, Q_y);
}

int main(){
  key_pair k_pair, test_pair;

  uECC_make_key(&k_pair.Q, k_pair.d);
  uECC_make_key(&test_pair.Q, test_pair.d);

  EccPoint p1, p2;

  EccPoint_add(&k_pair.Q, &test_pair.Q, &p1);
  printf("Get p1:\n");
  print_point(p1);

  uECC_word_t sum[uECC_BYTES];
  vli_modAdd(sum, k_pair.d, test_pair.d, curve_n);
  EccPoint_mult(&p2, &curve_G, sum, 0, vli_numBits(sum, uECC_WORDS));
  printf("Get P2:\n");
  print_point(p2);
  // FIXME p1 != p2

  return 1;
}

But I got two different points, when I compute aG+bG and (a+b)G. It will be very nice, if you can help me to debug my EccPoint_add function. Can you please tell me, if I have used the XYcZ_addC function there correctly, or if there is any better function for the point addition? Can you also explain me about the variable p_initialZ in the EccPoint_mult function. I'm sorry, but I do not understand the z value, which you have also written in comments.

Best regards,

Wenwen

When calling:
long v = random();
in the extern "C", it is well known that random routinely provides the same values on subsequent executions on Arduinos.

As per the Arduino reference:
"If it is important for a sequence of values generated by random() to differ, on subsequent executions of a sketch, use randomSeed() to initialize the random number generator with a fairly random input, such as analogRead() on an unconnected pin."

So, calling something like:
randomSeed(analogRead(0));
in setup() prior to uECC_set_rng() seems to get the job done, at least to the end of producing different values for things like signatures.

normally, something like:
srand(time(NULL));
would get the job done but as there is no reliable time in the AVR world it is abundantly apparent why this was not done.

This seems to be less of an issue when compiling for architectures like x86.

Is there any particular reason why random is not seeded in the example sketch?

I wonder how the parameter a and b are set in the old and new branch. I could only found P, N and the generator Point in the source.

As fare as I know to define a curve you have to set y^2 = x^3 +ax + b

a is assumed to be -3 but I could not found the value in the source of the "old branch" and new branch.

I also did a test with the examples given in (https://www.nsa.gov/ia/_files/nist-routines.pdf 4.3.2.)

Scalar multiply R = dS:

d = c51e4753 afdec1e6 b6c6a5b9 92f43f8d d0c7a893 3072708b
6522468b 2ffb06fd

xS = de2444be bc8d36e6 82edd27e 0f271508 617519b3 221a8fa0
b77cab39 89da97c9
yS = c093ae7f f36e5380 fc01a5aa d1e66659 702de80f 53cec576
b6350b24 3042a256

xR = 51d08d5f 2d427888 2946d88d 83c97d11 e62becc3 cfc18bed
acc89ba3 4eeca03f
yR = 75ee68eb 8bf626aa 5b673ab5 1f6e744e 06f8fcf8 a6c0cf30
35beca95 6a7b41d5

And if got:
public_x:
c9 97 da 89 39 ab 7c b7 a0 8f 1a 22 b3 19 75 61
08 15 27 0f 7e d2 ed 82 e6 36 8d bc be 44 24 de
public_y:
56 a2 42 30 24 0b 35 b6 76 c5 ce 53 0f e8 2d 70
59 66 e6 d1 aa a5 01 fc 80 53 6e f3 7f ae 93 c0
scalar:
fd 06 fb 2f 8b 46 22 65 8b 70 72 30 93 a8 c7 d0
8d 3f f4 92 b9 a5 c6 b6 e6 c1 de af 53 47 1e c5
result:
c9 97 da 89 39 ab 7c b7 a0 8f 1a 22 b3 19 75 61
08 15 27 0f 7e d2 ed 82 e6 36 8d bc be 44 24 de

as we can se result != xR

Have anyone a clue?

Thx

I've started looking at the code but it's not obvious how easily support for this curve could be added, is it just a matter of adding that curve's constants?

I was wondering if you were thinking of implementing deterministic signing (http://tools.ietf.org/html/rfc6979)? If not, I am planning to, and was wondering if you would be interested in a pull request.

I would introduce it as a new function int uECC_sign_deterministic(...) so one could still choose a non-deterministic signature.

Hi Kenneth,

I need to verify on Cortex M0 the signature of only 4 bytes.

I have the data to verify the signature : 0x11223344 (4 bytes)
I have also the signature 20 bytes (use curve uECC_secp160r1)

Is it possible to use your lib to make this verification ?

If not, do you have an easy solution to do this ?

Thanks in advance

Best regards

So this is a pedantic request, but, IMHO, it's more customary to return 0 to indicate success and not zero for an error. I was a bit surprised that this not the case. EXIT_SUCCESS, for example, is defined in C99 as 0.

If you don't want to change it, maybe define macros like #define uECC_SUCCESS 1? Feel free to tell me to STFU, but I figured I'd at least bring this up.

vli_mmod_fast accesses beyond the end of the vli array (in secp192r1).

The line in question is ecc.c:539 (as of commit ac0d7a3). Link: https://github.com/kmackay/micro-ecc/blob/master/ecc.c#L539

This could lead to accessing inappropriate memory as well as incorrect algorithm results if the copied memory is non-zero. I suggest rewriting this as a for loop, copying only the top NUM_ECC_DIGITS-6 words, manually zeroing the rest.

hello,
please I detect a bug in the function:
EccPoint_mult(EccPoint * RESTRICT p_result, EccPoint * RESTRICT p_point,
const uECC_word_t * RESTRICT p_scalar, const uECC_word_t * RESTRICT p_initialZ, bitcount_t p_numBits),

the issue are, missed an initialization for Rx[0] and Ry[0] :
the solution proposed is to add the Rx[0] initial value:
vli_set(Rx[0], p_point->x);//Rx[0]
vli_set(Ry[0], p_point->y); //Rx[0]
we should add a test for p_numBits because there as an 2_P are added in the result , please find the code modified below, now it work fine and the result compared with others calculators now we can compute the multiplication points successfully.
code corrected:
static void EccPoint_mult(EccPoint * RESTRICT p_result, EccPoint * RESTRICT p_point,
const uECC_word_t * RESTRICT p_scalar, const uECC_word_t * RESTRICT p_initialZ, bitcount_t p_numBits)
{
/_ R0 and R1 */
uECC_word_t Rx[2][uECC_WORDS];
uECC_word_t Ry[2][uECC_WORDS];
uECC_word_t A[1][uECC_WORDS];
uECC_word_t t;
uECC_word_t z[uECC_WORDS];

bitcount_t i;
uECC_word_t nb;

vli_set(Rx[1], p_point->x);//Rx[1]
vli_set(Ry[1], p_point->y); //Rx[1]
vli_set(Rx[0], p_point->x);//Rx[0]
vli_set(Ry[0], p_point->y); //Rx[0]
if((p_numBits)>=2)
{
    XYcZ_initial_double(Rx[1], Ry[1], Rx[0], Ry[0], p_initialZ);
    for(i = p_numBits - 2; i > 0; --i)
    {
        nb =! vli_testBit(p_scalar, i);//=! 
        XYcZ_addC(Rx[1-nb], Ry[1-nb], Rx[nb], Ry[nb]);
        XYcZ_add(Rx[nb], Ry[nb], Rx[1-nb], Ry[1-nb]);
    }
nb =! vli_testBit(p_scalar, 0);//=! 
XYcZ_addC(Rx[1-nb], Ry[1-nb], Rx[nb], Ry[nb]);
vli_modSub_fast(z, Rx[1], Rx[0]); /* X1 - X0 */
vli_modMult_fast(z, z, Ry[1-nb]);     /* Yb * (X1 - X0) */
vli_modMult_fast(z, z, p_point->x);   /* xP * Yb * (X1 - X0) */
vli_modInv(z, z, curve_p);            /* 1 / (xP * Yb * (X1 - X0)) */
vli_modMult_fast(z, z, p_point->y);   /* yP / (xP * Yb * (X1 - X0)) */
vli_modMult_fast(z, z, Rx[1-nb]);     /* Xb * yP / (xP * Yb * (X1 - X0)) */
/* End 1/Z calculation */

XYcZ_add(Rx[nb], Ry[nb], Rx[1-nb], Ry[1-nb]);    
apply_z(Rx[0], Ry[0], z);

/* Find final 1/Z value. */

}

vli_set(p_result->x, Rx[0]);
vli_set(p_result->y, Ry[0]);

}

good luck

I'm using micro-ecc on an embedded platform where every bit counts, and it would be nice to have point compression. Would it be possible to add it?

I am trying to use uECC_verify with a hash of size of 7 bytes and verification fails. Must hash always be of uECC_BYTES length or can it be smaller.

The web page at http://kmackay.ca/micro-ecc/ indicates secp384r1 is supported, and shows performance results for this, but it doesn't appear that the GitHub repo (nor the tarball) has implemented it. Would it be possible to add support for secp384r1?

Hi kmackay
Im trying to replicate the following python code using micro-ecc and struggling to get it to generate the same signature. I even tried to using the same K values generated using k = deterministic_generate_k(msghash, priv) and plug that into uECC_sign_with_k but the signature i received was completely different. Can you point me in the right direction. Thanks!

def deterministic_generate_k(msghash, priv):
v = b'\x01' * 32
k = b'\x00' * 32
priv = encode_privkey(priv, 'bin')
msghash = encode(hash_to_int(msghash), 256, 32)
k = hmac.new(k, v+b'\x00'+priv+msghash, hashlib.sha256).digest()
v = hmac.new(k, v, hashlib.sha256).digest()
k = hmac.new(k, v+b'\x01'+priv+msghash, hashlib.sha256).digest()
v = hmac.new(k, v, hashlib.sha256).digest()
return decode(hmac.new(k, v, hashlib.sha256).digest(), 256)

def ecdsa_raw_sign(msghash, priv):
z = hash_to_int(msghash)
k = deterministic_generate_k(msghash, priv)
r, y = fast_multiply(G, k)
s = inv(k, N) * (z + r*decode_privkey(priv)) % N
v, r, s = 27+((y % 2) ^ (0 if s * 2 < N else 1)), r, s if s * 2 < N else N - s
if 'compressed' in get_privkey_format(priv):
v += 4
return v, r, s

I was using version 98e1f20 of microecc and after an update to 73db5bf or newer I can not verify any more.

The bug comes with version 400b453. Versions before are working fine.

I tried different uECC_ASM with uECC_secp256r1.

The code is looping in block /* Calculate sum = G + Q. / in XYcZ_add(tx, ty, sum.x, sum.y); and there in die vli_modSquare_fast(t5, t5); / t5 = (x2 - x1)^2 = A */

I hope we find a fix, because we would love to uns the new 224 curve.

Thanks!

Hi,
I am testing with OpenSSL ECDSA signature. The test procedure is to create a ECDSA a signature in OpenSSL, then verify this signature using micro-ecc (publickey and hash is taken from OpenSSL output). I found that except for "secp160r1" curve, the signature verification fails in micro-ecc for the other supported curves. Is this expected?

I'm trying to use this library with ecc_asm_thumb on an cortex-m0 (namely an nrf51822). However compilation fails with:

micro-ecc/ecc.c: In function 'vli_mult':
micro-ecc/ecc.c:450:1: error: r7 cannot be used in asm here
}
^

ecc_asm_none works fine though!

hello.

I signing a data on micro-ecc and verify with Java system(Android).
but verify result is any time "false"

what should I do?
please help.

It looks like this library builds only on a Mac? For example, on a 64 bit Ubuntu machine I'm trying emk arch=rpi and I get the following errors. Maybe I'm not building it correctly?

emk (info): Using 12 threads
emk (info): Could not import 'config' from ['/home/jbd/.emk']
emk (info): Entering directory /home/jbd/repos/micro-ecc
emk (info): Entering directory /home/jbd/repos/micro-ecc/test

Build error: Could not call '/Volumes/xtools/arm-none-linux-gnueabi/bin/arm-none-linux-gnueabi-gcc -Wp,-MMD,/home/jbd/repos/micro-ecc/__build__/rpi/dbg/uECC.o.dep -I/home/jbd/repos/micro-ecc -DTARGET_ARCH_RPI=1 -fvisibility=hidden -Wall -Wextra -Wshadow -Werror -Wno-missing-field-initializers -Wno-unused-parameter -Wno-comment -Wno-unused -Wno-unknown-pragmas -g -fomit-frame-pointer -std=c99 -o /home/jbd/repos/micro-ecc/__build__/rpi/dbg/uECC.o -c /home/jbd/repos/micro-ecc/uECC.c' as a subprocess: [Errno 2] No such file or directory

When compiling with fast_asm on either of the 256 curves throws errors.

Environment:
Arduino IDE 1.5.8 Beta - Required for the board
OSX

Target Board:
Arduino Due (AT91SAM3X8E: Atmel Arm Cortex-M3) - http://arduino.cc/en/Main/ArduinoBoardDue

Defines set by me:
uECC_CURVE uECC_secp256k1
uECC_ASM uECC_asm_fast

Defines set during compilation:
thumb2
uECC_PLATFORM uECC_arm_thumb2
uECC_WORD_SIZE 4
uECC_WORDS 8

Compiler output:
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s: Assembler messages:
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1131: Error: thumb conditional instruction should be in IT block -- adchi r12,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1144: Error: thumb conditional instruction should be in IT block --adchi r10,#0'
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1151: Error: thumb conditional instruction should be in IT block -- adchi r10,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1161: Error: thumb conditional instruction should be in IT block --adchi r12,#0'
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1165: Error: thumb conditional instruction should be in IT block -- adchi r12,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1179: Error: thumb conditional instruction should be in IT block --adchi r10,#0'
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1190: Error: thumb conditional instruction should be in IT block -- adchi r10,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1200: Error: thumb conditional instruction should be in IT block --adchi r12,#0'
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1204: Error: thumb conditional instruction should be in IT block -- adchi r12,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1222: Error: thumb conditional instruction should be in IT block --adchi r10,#0'
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1233: Error: thumb conditional instruction should be in IT block -- adchi r10,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1243: Error: thumb conditional instruction should be in IT block --adchi r12,#0'
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1247: Error: thumb conditional instruction should be in IT block -- adchi r12,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1264: Error: thumb conditional instruction should be in IT block --adchi r10,#0'
/var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1271: Error: thumb conditional instruction should be in IT block -- adchi r10,#0' /var/folders/9h/8c6p8qg52s3_r5l39g0_r58n611hts/T//ccVfTMR0.s:1281: Error: thumb conditional instruction should be in IT block --adchi r12,#0'
Error compiling.

I believe all of these errors occur in vli_square in asm_arm.h while performing any adchi assembly instruction.

I'm working with the uECC_secp256r1 curve and am seeing a case where a public key that is compressed then decompressed no longer seems to be correct. The actual byte array is different and any attempts to verify with it will also fail.

For example, the original public key I'm currently using is:
00: 15 1d af e7 69 47 22 9c
08: 34 c1 6b 1b ff af 1b f5
10: 9a e2 ec 61 17 75 35 90
18: 43 5d 0e 3f 35 56 25 b5
20: 7c 27 f6 52 82 c5 64 a4
28: 28 df c1 8d 7f 8c 80 41
30: 45 33 cf 61 92 92 1d ba
38: 12 e6 b4 79 f2 29 6b 36

This compresses to:
00: 02 15 1d af e7 69 47 22
08: 9c 34 c1 6b 1b ff af 1b
10: f5 9a e2 ec 61 17 75 35
18: 90 43 5d 0e 3f 35 56 25

And then decompresses to:
00: 15 1d af e7 69 47 22 9c
08: 34 c1 6b 1b ff af 1b f5
10: 9a e2 ec 61 17 75 35 90
18: 43 5d 0e 3f 35 56 25 45
20: 95 76 37 3c 5b 38 6a dd
28: f8 e8 6a 83 4e 12 1c bb
30: d5 67 2e d7 61 65 c3 6b
38: 7a ce 9c 2a bc b8 b4 c8

At this point attempts to verify with that key will fail.

Should I be able to compress/decompress keys generated with this curve? Thank you for any help!

Hi,

would it be possible to port uECC to an 16 port processor (a MSP430)?

What must be changed in order to achieve this?

For a complete implementation of ECDSA signature scheme, I think the signing functions can be changed to accept a private_key pointer to a buffer of length uECC_N_BYTES (a newly defined macro for the byte length of curve_n) instead of uECC_BYTES, because in some cases the bit length of curve_n (for curves like secp160r1, secp224k1, and secp521r1) is not in the set { 80, 96, 112, 128, 192, 256 }. We can not represent all possible private keys if we only use uECC_BYTES octets. That means, some users of a valid private key cannot even use this C library to generate ECDSA signatures.

For a similar reason, I think the functions may accept an additional argument indicating the length of the buffer pointed by message_hash. Otherwise, by forcing the message digest to be uECC_BYTES octets long, users cannot use this library directly to produce an ECDSA signature on secp192r1 curve with SHA-256 in the standard way.

int uECC_sign(const uint8_t private_key[uECC_BYTES], // cannot represent all keys
              const uint8_t message_hash[uECC_BYTES], // may need to be truncated by the user
              uint8_t signature[uECC_BYTES*2]);

int uECC_sign_deterministic(const uint8_t private_key[uECC_BYTES], // cannot represent all keys
                            const uint8_t message_hash[uECC_BYTES], // may need to be truncated by the user
                            uECC_HashContext *hash_context,
                            uint8_t signature[uECC_BYTES*2]);

int uECC_verify(const uint8_t public_key[uECC_BYTES*2],
                const uint8_t hash[uECC_BYTES], // may need to be truncated by the user
                const uint8_t signature[uECC_BYTES*2]);

This is some sort of a design choice. By not supporting all possible combinations of inputs, the library codebase can be a little bit simpler and easier to maintain.

When I add an ECC curve to micro-ecc, I found that EccPoint_mult got a wrong result.

curve params is:
p=fffffffe ffffffff ffffffff ffffffff ffffffff 00000000 ffffffff ffffffff
a=fffffffe ffffffff ffffffff ffffffff ffffffff 00000000 ffffffff fffffffc
b=28e9fa9e 9d9f5e34 4d5a9e4b cf6509a7 f39789f5 15ab8f92 ddbcbd41 4d940e93
n=fffffffe ffffffff ffffffff ffffffff 7203df6b 21c6052b 53bbf409 39d54123
gx=32c4ae2c 1f198119 5f990446 6a39c994 8fe30bbf f2660be1 715a4589 334c74c7
gy=bc3736a2 f4f6779c 59bdcee3 6b692153 d0a9877c c62a4740 02df32e5 2139f0a0

I have implemented “vli_mmod_fast” function myself, and i have tested it by OPENSSL, it's correct.

Could you please tell me what should I do next?

The variable declarations:

static uECC_word_t curve_p[uECC_WORDS] = uECC_CONCAT(Curve_P_, uECC_CURVE);
static uECC_word_t curve_b[uECC_WORDS] = uECC_CONCAT(Curve_B_, uECC_CURVE);
static EccPoint curve_G = uECC_CONCAT(Curve_G_, uECC_CURVE);
static uECC_word_t curve_n[uECC_N_WORDS] = uECC_CONCAT(Curve_N_, uECC_CURVE);

Should be modified with a const qualifier to avoid unnecessary RAM memory allocation when they can be suitably stored in ROM. This also requires the EccPoint_mult function to be modified accordingly.

 uECC.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/uECC.c b/uECC.c
index 04308ac..3ac9819 100644
--- a/uECC.c
+++ b/uECC.c
@@ -297,10 +297,10 @@ typedef struct EccPoint
     uECC_word_t y[uECC_WORDS];
 } EccPoint;

-static uECC_word_t curve_p[uECC_WORDS] = uECC_CONCAT(Curve_P_, uECC_CURVE);
-static uECC_word_t curve_b[uECC_WORDS] = uECC_CONCAT(Curve_B_, uECC_CURVE);
-static EccPoint curve_G = uECC_CONCAT(Curve_G_, uECC_CURVE);
-static uECC_word_t curve_n[uECC_N_WORDS] = uECC_CONCAT(Curve_N_, uECC_CURVE);
+static const uECC_word_t curve_p[uECC_WORDS] = uECC_CONCAT(Curve_P_, uECC_CURVE);
+static const uECC_word_t curve_b[uECC_WORDS] = uECC_CONCAT(Curve_B_, uECC_CURVE);
+static const EccPoint curve_G = uECC_CONCAT(Curve_G_, uECC_CURVE);
+static const uECC_word_t curve_n[uECC_N_WORDS] = uECC_CONCAT(Curve_N_, uECC_CURVE);

 static void vli_clear(uECC_word_t *p_vli);
 static uECC_word_t vli_isZero(const uECC_word_t *p_vli);
@@ -1653,7 +1653,7 @@ static void XYcZ_addC(uECC_word_t * RESTRICT X1, uECC_word_t * RESTRICT Y1, uECC
     vli_set(X1, t7);
 }

-static void EccPoint_mult(EccPoint * RESTRICT p_result, EccPoint * RESTRICT p_point,
+static void EccPoint_mult(EccPoint * RESTRICT p_result, const EccPoint * RESTRICT p_point,
     const uECC_word_t * RESTRICT p_scalar, const uECC_word_t * RESTRICT p_initialZ, bitcount_t p_numBits)
 {
     /* R0 and R1 */
@@ -2338,10 +2338,10 @@ int uECC_verify(const uint8_t p_publicKey[uECC_BYTES*2], const uint8_t p_hash[uE
     apply_z(l_sum.x, l_sum.y, z);

     /* Use Shamir's trick to calculate u1*G + u2*Q */
-    EccPoint *l_points[4] = {0, &curve_G, &l_public, &l_sum};
+    const EccPoint *l_points[4] = {0, &curve_G, &l_public, &l_sum};
     bitcount_t l_numBits = smax(vli_numBits(u1, uECC_N_WORDS), vli_numBits(u2, uECC_N_WORDS));

-    EccPoint *l_point = l_points[(!!vli_testBit(u1, l_numBits-1)) | ((!!vli_testBit(u2, l_numBits-1)) << 1)];
+    const EccPoint *l_point = l_points[(!!vli_testBit(u1, l_numBits-1)) | ((!!vli_testBit(u2, l_numBits-1)) << 1)];
     vli_set(rx, l_point->x);
     vli_set(ry, l_point->y);
     vli_clear(z);

Hi Ken,

thanks for this great piece of software.

At the moment I am trying to integrate the library into a ppc processor with e200 core. My first tests show, that it works! So YAY!!!

Still the performance could be better. On arm (Arduino Due) I can see, that the asm optimization reduce the time needed significantly. Do you know of any ppc asm optimization for your library?

Thanks,
gitroem

One useful thing to help debug and pin point issues in new implementations is the use of a specific typedef to differentiate the different byte strings that are being passed in to/out of the interface function calls. This allows many issues to be found at compile time.

eg.

instead of this:
func( const uint8_t public_key[ECC_BYTES_2], const uint8_t private_key[ECC_BYTES], uint8_t signature[ECC_BYTES_2] );

this:
typedef uint8_t ECC_PrivateKey_t[ECC_BYTES];
typedef uint8_t ECC_Signature_t[ECC_BYTES_2];
typedef uint8_t ECC_PublicKey_t[ECC_BYTES_2];
typedef uint8_t ECC_CompressedPublicKey_t[1+ECC_BYTES];

func( ECC_PublicKey_t* const p_public_key, ECC_PrivateKey_t* const p_private_key, ECC_Signature_t* p_signature );

Obviously this means lots of typecasting or a typecast intermediary local var within uECC. And it means existing implementations need to change their interface vars, but IMO a type defined external interface would assist newcomers with finding problems where they've transposed a public key, private key, or signature.

Not a real problem, as it was simple enough to add inlined casting wrappers to translate the functional interface differences without impacting the final compiled code.

eg.
inline ECC_BoolRet_t x_uECC_MakeKey( ECC_PublicKey_t *pxPublicKey, ECC_PrivateKey_t *pxPrivateKey )
{
return (ECC_BoolRet_t) uECC_make_key( (uint8_t *)pxPublicKey, (uint8_t *)pxPrivateKey );
}