NotificationsYou must be signed in to change notification settings
Fork2.8k
Star6.3k

Added a function that decompresses EC public keys#521

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Jump to bottom

Closed

deade1e wants to merge2 commits intoMbed-TLS:developmentfromdeade1e:development

Closed

Added a function that decompresses EC public keys#521

deade1e wants to merge2 commits intoMbed-TLS:developmentfromdeade1e:development

Conversation

Copy link

deade1e commentedJun 27, 2016

I implemented what was discussed on this thread:https://crypto.stackexchange.com/questions/20627/point-decompression-on-an-elliptic-curve

Francesco Pompò added2 commits

June 27, 2016 21:04

added mbedtls_ecp_decompress_pubkey function

c614219

Added mbedtls_ecp_decompress_pubkey declaration

77cad20

simonbutcher added enhancement CLA valid labels

Jul 25, 2016

Copy link

Author

deade1e commentedNov 5, 2016

bump

dbedev mentioned this pull request

Apr 3, 2017

Does mbedtls support ec_point_format compressed?#861

Closed

Copy link

mwarning commentedJul 3, 2017•
edited
Loading

I was looking for this feature. :-)
But this code does not seem to work when grp->A.p == NULL (e.g. for SECP192R1), in this case, use A = -3. Maybe someone can shed some light why A is -3...

Some things I noticed:

check input[0] to be 0x03 or 0x02, rather to check for a single case what it should not be
only three mbedtls_mpi variables are needed
if grp->A.p == NULL use A = -3 (at least for secp192r1)
safe a multiplication by computing "x^2 + a" first and then multiply by x to get "x^3 + ax"
divide by 4 by using "mbedtls_mpi_shift_r(&zexp, 2);"; should be faster
"input[0] == 0x03 ? 1 : 0" => "input[0] & 1" - no if needed

@pfrankw I hope this helps somewhat. I'm not sure how the developers imagine how this feature should be included, if at all..

Copy link

Author

deade1e commentedJul 3, 2017•
edited
Loading

Hello :)

Sadly I am not a crypto expert so my interpretation of the problem may be a bit uncorrect.
I remember (it was an year ago) that the code worked with secp256k1, but of course was not properly tested with other scenarios.

Anyway thanks for the suggestions, I hope this feature will be added :)
EDIT: When I have some time I will try to fix it.

Copy link

mwarning commentedJul 3, 2017•
edited
Loading

@pfrankw: I am no crypto expert at all. :-) Anyway, I pushed my code herehttps://github.com/mwarning/mbedtls_ecp_compression, but in this new test environment, the code fails rather often. So there is definitely a (memory?) bug.

Copy link

mwarning commentedJul 3, 2017

@pfrankw do you know if mod P needs to be performed after every mpi operation?

Copy link

mwarning commentedJul 4, 2017•
edited
Loading

@pfrankw~~you probably also need to use the MOD_MUL/MOD_ADD/MOD_SUB macros (seeecp.c)~~
I was not able to get your code to work so far, and the version I wrote is only correct half the time. ;-(

Maybe some mbedtls dev can chime in.@mpg?

Copy link

mwarning commentedJul 5, 2017•
edited
Loading

Ok, I was able to fix my code :-)
@pfrankw setting the correct sign is wrong in your code, you need subtract y from p.

i = (first/marker byte of compressed point) mod 2y2 = (x ^ 3 + a*x + b) mod py_ = (y2 ^ ((p+1)/4)) mod pif both i and y_ have the same sign (odd/even)   y = y_else   y = p-y_

Copy link

Author

deade1e commentedJul 7, 2017•
edited
Loading

Thank you very much@mwarning !
EDIT: I hope to have enough time this weekend to view the code.

Copy link

mwarning commentedJul 7, 2017

@pfrankw that would be great. Anyway, the best location might be to implement this feature here:https://github.com/ARMmbed/mbedtls/blob/development/library/ecp.c#L522

I do not know if the mbedtls devs prefer to have this feature. Afaik, TLS itself does not need it. So it would be nice to have a decision here. :-)

Also, consider to implement a general square root algorithm, as this only works for this special kind of curve.

have fun :-)

Copy link

mwarning commentedJul 7, 2017

Relevant:#861

Copy link

Author

deade1e commentedJul 8, 2017

I have seen the code and made a pull request (mwarning/mbedtls-ecp-compression#1) about one superfluous operation.
I have not checked for bugs but your code is much more optimized than mine!

simonbutcher added the component-cryptoCrypto primitives and low-level interfaces label

Oct 26, 2018

RonEld assignedmpg

Jan 24, 2019

mpg reviewed

Feb 7, 2019

View reviewed changes

Copy link

Contributor

mpg left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thanks for your contribution. Unfortunately the chosen computation method doesn't work with all curves supported by Mbed TLS, and also some unit tests would be required (which would have caught that).

library/ecp.c

		MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&zexp,&grp->P) );// Z exponent
		MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&zexp,&zexp,1 ) );// Z exponent + 1
		MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(&zexp,0,&zexp,4 ) );// Z exponent / 4
		MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&y,&z,&zexp,&grp->P,0 ) );// Z^Zexp % P

Copy link

Contributor

mpgFeb 7, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

This way of extracting square roots mod P only works for some Ps (those that are congruent to 3 mod 4), but will not work for all curves supported by Mbed TLS.

Copy link

mwarningFeb 7, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

@mpg what curves use Ps that are congruent to 3 mod 4? I would like to add that to my readme here:https://github.com/mwarning/mbedtls_ecp_compression

Copy link

Contributor

mpgFeb 7, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

It's easy to check:

#include"mbedtls/ecp.h"#include<stdio.h>intmain(void){constmbedtls_ecp_curve_info*info;mbedtls_ecp_groupgrp;mbedtls_mpi_uintr;for(info=mbedtls_ecp_curve_list();info->name!=NULL;info++ )    {mbedtls_ecp_group_init(&grp );mbedtls_ecp_group_load(&grp,info->grp_id );mbedtls_mpi_mod_int(&r,&grp.P,4 );printf("%s: p = %u mod 4\n",info->name, (unsigned)r );mbedtls_ecp_group_free(&grp );    }}

then

% make lib && gcc -Iinclude p-mod-4.c library/libmbedcrypto.a -o p-mod-4 && ./p-mod-4                                                                  git|development|secp521r1: p = 3 mod 4brainpoolP512r1: p = 3 mod 4secp384r1: p = 3 mod 4brainpoolP384r1: p = 3 mod 4secp256r1: p = 3 mod 4secp256k1: p = 3 mod 4brainpoolP256r1: p = 3 mod 4secp224r1: p = 1 mod 4secp224k1: p = 1 mod 4secp192r1: p = 3 mod 4secp192k1: p = 3 mod 4

library/ecp.c

		/*
		* Decompresses an EC Public Key
		*/
		intmbedtls_ecp_decompress_pubkey(constmbedtls_ecp_groupgrp,constunsignedcharinput,size_tilen,unsignedcharoutput,size_tolen,size_tosize ){

Copy link

Contributor

mpgFeb 7, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

This line length and the following indentation don't match our coding style.

Copy link

Contributor

mpg commentedFeb 7, 2019

Support for compressed format has been deprecated by RFC 8422 in the context of TLS, which reflects a more general sentiment in the ECC community to prefer uncompressed format. Also, implementing it correctly for all supported curves would require substantial code, impacting our footprint - and the present PR would require non-trivial rework (values of P not congruent to 3 mod 4, unit tests) before if would be ready for merge.

At this point, we're unlikely to want to add that amount of code for a feature that's formally deprecated in TLS and being abandoned more generally, so I'm closing this PR.

Thanks for your contribution and interest in Mbed TLS anyway.