diff mbox series

[U-Boot,v3,4/6] lib: rsa: generate additional parameters for public key

Message ID 20191113004730.30139-5-takahiro.akashi@linaro.org
State Superseded
Delegated to: Tom Rini
Headers show
Series rsa: extend rsa_verify() for UEFI secure boot | expand

Commit Message

Takahiro Akashi Nov. 13, 2019, 12:47 a.m. UTC
In the current implementation of FIT_SIGNATURE, five parameters for
a RSA public key are required while only two of them are essential.
(See rsa-mod-exp.h and uImage.FIT/signature.txt)
This is a result of considering relatively limited computer power
and resources on embedded systems, while such a assumption may not
be quite practical for other use cases.

In this patch, added is a function, rsa_gen_key_prop(), which will
generate additional parameters for other uses, in particular
UEFI secure boot, on the fly.

Note: the current code uses some "big number" routines from BearSSL
for the calculation.

Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 include/u-boot/rsa-mod-exp.h |  21 +
 lib/rsa/Kconfig              |   1 +
 lib/rsa/Makefile             |   1 +
 lib/rsa/rsa-keyprop.c        | 717 +++++++++++++++++++++++++++++++++++
 4 files changed, 740 insertions(+)
 create mode 100644 lib/rsa/rsa-keyprop.c

Comments

Simon Glass Nov. 20, 2019, 2:59 a.m. UTC | #1
Hi Takahiro,

On Tue, 12 Nov 2019 at 16:47, AKASHI Takahiro
<takahiro.akashi@linaro.org> wrote:
>
> In the current implementation of FIT_SIGNATURE, five parameters for
> a RSA public key are required while only two of them are essential.
> (See rsa-mod-exp.h and uImage.FIT/signature.txt)
> This is a result of considering relatively limited computer power
> and resources on embedded systems, while such a assumption may not
> be quite practical for other use cases.
>
> In this patch, added is a function, rsa_gen_key_prop(), which will
> generate additional parameters for other uses, in particular
> UEFI secure boot, on the fly.
>
> Note: the current code uses some "big number" routines from BearSSL
> for the calculation.
>
> Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
> ---
>  include/u-boot/rsa-mod-exp.h |  21 +
>  lib/rsa/Kconfig              |   1 +
>  lib/rsa/Makefile             |   1 +
>  lib/rsa/rsa-keyprop.c        | 717 +++++++++++++++++++++++++++++++++++
>  4 files changed, 740 insertions(+)
>  create mode 100644 lib/rsa/rsa-keyprop.c
>
> diff --git a/include/u-boot/rsa-mod-exp.h b/include/u-boot/rsa-mod-exp.h
> index 8a428c4b6a1a..374169b8304e 100644
> --- a/include/u-boot/rsa-mod-exp.h
> +++ b/include/u-boot/rsa-mod-exp.h
> @@ -26,6 +26,27 @@ struct key_prop {
>         uint32_t exp_len;       /* Exponent length in number of uint8_t */
>  };
>
> +/**
> + * rsa_gen_key_prop() - Generate key properties of RSA public key
> + * @key:       Specifies key data in DER format
> + * @keylen:    Length of @key
> + *
> + * This function takes a blob of encoded RSA public key data in DER
> + * format, parse it and generate all the relevant properties
> + * in key_prop structure.
> + *
> + * Return:     Pointer to struct key_prop on success, NULL on error
> + */
> +struct key_prop *rsa_gen_key_prop(const void *key, uint32_t keylen);
> +
> +/**
> + * rsa_free_key_prop() - Free key properties
> + * @prop:      Pointer to struct key_prop
> + *
> + * This function frees all the memories allocated by rsa_gen_key_prop().
> + */
> +void rsa_free_key_prop(struct key_prop *prop);
> +
>  /**
>   * rsa_mod_exp_sw() - Perform RSA Modular Exponentiation in sw
>   *
> diff --git a/lib/rsa/Kconfig b/lib/rsa/Kconfig
> index 71e4c06bf883..d1d6f6cf64a3 100644
> --- a/lib/rsa/Kconfig
> +++ b/lib/rsa/Kconfig
> @@ -33,6 +33,7 @@ config RSA_VERIFY
>  config RSA_VERIFY_WITH_PKEY
>         bool "Execute RSA verification without key parameters from FDT"
>         depends on RSA
> +       imply RSA_PUBLIC_KEY_PARSER
>         help
>           The standard RSA-signature verification code (FIT_SIGNATURE) uses
>           pre-calculated key properties, that are stored in fdt blob, in
> diff --git a/lib/rsa/Makefile b/lib/rsa/Makefile
> index c07305188e0c..14ed3cb4012b 100644
> --- a/lib/rsa/Makefile
> +++ b/lib/rsa/Makefile
> @@ -6,4 +6,5 @@
>  # Wolfgang Denk, DENX Software Engineering, wd@denx.de.
>
>  obj-$(CONFIG_$(SPL_)RSA_VERIFY) += rsa-verify.o rsa-checksum.o
> +obj-$(CONFIG_RSA_VERIFY_WITH_PKEY) += rsa-keyprop.o
>  obj-$(CONFIG_RSA_SOFTWARE_EXP) += rsa-mod-exp.o
> diff --git a/lib/rsa/rsa-keyprop.c b/lib/rsa/rsa-keyprop.c
> new file mode 100644
> index 000000000000..9458337cc608
> --- /dev/null
> +++ b/lib/rsa/rsa-keyprop.c
> @@ -0,0 +1,717 @@
> +// SPDX-License-Identifier: GPL-2.0+ and MIT
> +/*
> + * RSA library - generate parameters for a public key
> + *
> + * Copyright (c) 2019 Linaro Limited
> + * Author: AKASHI Takahiro
> + *
> + * Big number routines in this file come from BearSSL:

Can we put these in their own file if we expect to update them? Really
should be called by the original filename and go in lib/bearsll.

[..]

> +/**
> + * rsa_gen_key_prop() - Generate key properties of RSA public key
> + * @key:       Specifies key data in DER format
> + * @keylen:    Length of @key
> + *
> + * This function takes a blob of encoded RSA public key data in DER
> + * format, parse it and generate all the relevant properties
> + * in key_prop structure.
> + *
> + * Return:     Pointer to struct key_prop on success, NULL on error
> + */
> +struct key_prop *rsa_gen_key_prop(const void *key, uint32_t keylen)
> +{
> +       struct key_prop *prop;
> +       struct rsa_key rsa_key;
> +#define BR_MAX_RSA_SIZE 4096

const int?

> +       uint32_t *n, *rr, *rrtmp;
> +       int rlen, i, ret;
> +
> +       prop = calloc(sizeof(*prop), 1);
> +       if (!prop)
> +               return NULL;
> +       n = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
> +       rr = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
> +       rrtmp = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
> +       if (!n || !rr || !rrtmp)
> +               return NULL;

This can cause memory leak and will likely generate a coverity warning.

> +
> +       ret = rsa_parse_pub_key(&rsa_key, key, keylen);
> +       if (ret)
> +               goto err;
> +
> +       /* modulus */
> +       /* removing leading 0's */
> +       for (i = 0; i < rsa_key.n_sz && !rsa_key.n[i]; i++)
> +               ;
> +       prop->num_bits = (rsa_key.n_sz - i) * 8;
> +       prop->modulus = malloc(rsa_key.n_sz - i);
> +       if (!prop->modulus)
> +               goto err;
> +       memcpy((void *)prop->modulus, &rsa_key.n[i], rsa_key.n_sz - i);
> +
> +       /* exponent */
> +       prop->public_exponent = calloc(1, sizeof(uint64_t));
> +       if (!prop->public_exponent)
> +               goto err;
> +       memcpy((void *)prop->public_exponent + sizeof(uint64_t) - rsa_key.e_sz,
> +              rsa_key.e, rsa_key.e_sz);
> +       prop->exp_len = rsa_key.e_sz;
> +
> +       /* n0 inverse */
> +       br_i32_decode(n, &rsa_key.n[i], rsa_key.n_sz - i);
> +       prop->n0inv = br_i32_ninv32(n[1]);
> +
> +       /* R^2 mod n; R = 2^(num_bits) */
> +       rlen = prop->num_bits * 2; /* #bits of R^2 = (2^num_bits)^2 */
> +       rr[0] = 0;
> +       *(uint8_t *)&rr[0] = (1 << (rlen % 8));
> +       for (i = 1; i < (((rlen + 31) >> 5) + 1); i++)
> +               rr[i] = 0;
> +       br_i32_decode(rrtmp, rr, ((rlen + 7) >> 3) + 1);
> +       br_i32_reduce(rr, rrtmp, n);
> +
> +       rlen = (prop->num_bits + 7) >> 3; /* #bytes of R^2 mod n */
> +       prop->rr = malloc(rlen);
> +       if (!prop->rr)
> +               goto err;
> +       br_i32_encode((void *)prop->rr, rlen, rr);
> +
> +       return prop;
> +
> +err:
> +       free(n);
> +       free(rr);
> +       free(rrtmp);
> +       rsa_free_key_prop(prop);
> +       return NULL;

This should return -ENOMEM if we are out of memory. The caller cannot
divine what went wrong.

> +}
> --
> 2.21.0
>

Regards,
Simon
Takahiro Akashi Nov. 20, 2019, 5:53 a.m. UTC | #2
Simon,

On Tue, Nov 19, 2019 at 06:59:59PM -0800, Simon Glass wrote:
> Hi Takahiro,
> 
> On Tue, 12 Nov 2019 at 16:47, AKASHI Takahiro
> <takahiro.akashi@linaro.org> wrote:
> >
> > In the current implementation of FIT_SIGNATURE, five parameters for
> > a RSA public key are required while only two of them are essential.
> > (See rsa-mod-exp.h and uImage.FIT/signature.txt)
> > This is a result of considering relatively limited computer power
> > and resources on embedded systems, while such a assumption may not
> > be quite practical for other use cases.
> >
> > In this patch, added is a function, rsa_gen_key_prop(), which will
> > generate additional parameters for other uses, in particular
> > UEFI secure boot, on the fly.
> >
> > Note: the current code uses some "big number" routines from BearSSL
> > for the calculation.
> >
> > Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
> > ---
> >  include/u-boot/rsa-mod-exp.h |  21 +
> >  lib/rsa/Kconfig              |   1 +
> >  lib/rsa/Makefile             |   1 +
> >  lib/rsa/rsa-keyprop.c        | 717 +++++++++++++++++++++++++++++++++++
> >  4 files changed, 740 insertions(+)
> >  create mode 100644 lib/rsa/rsa-keyprop.c
> >
> > diff --git a/include/u-boot/rsa-mod-exp.h b/include/u-boot/rsa-mod-exp.h
> > index 8a428c4b6a1a..374169b8304e 100644
> > --- a/include/u-boot/rsa-mod-exp.h
> > +++ b/include/u-boot/rsa-mod-exp.h
> > @@ -26,6 +26,27 @@ struct key_prop {
> >         uint32_t exp_len;       /* Exponent length in number of uint8_t */
> >  };
> >
> > +/**
> > + * rsa_gen_key_prop() - Generate key properties of RSA public key
> > + * @key:       Specifies key data in DER format
> > + * @keylen:    Length of @key
> > + *
> > + * This function takes a blob of encoded RSA public key data in DER
> > + * format, parse it and generate all the relevant properties
> > + * in key_prop structure.
> > + *
> > + * Return:     Pointer to struct key_prop on success, NULL on error
> > + */
> > +struct key_prop *rsa_gen_key_prop(const void *key, uint32_t keylen);
> > +
> > +/**
> > + * rsa_free_key_prop() - Free key properties
> > + * @prop:      Pointer to struct key_prop
> > + *
> > + * This function frees all the memories allocated by rsa_gen_key_prop().
> > + */
> > +void rsa_free_key_prop(struct key_prop *prop);
> > +
> >  /**
> >   * rsa_mod_exp_sw() - Perform RSA Modular Exponentiation in sw
> >   *
> > diff --git a/lib/rsa/Kconfig b/lib/rsa/Kconfig
> > index 71e4c06bf883..d1d6f6cf64a3 100644
> > --- a/lib/rsa/Kconfig
> > +++ b/lib/rsa/Kconfig
> > @@ -33,6 +33,7 @@ config RSA_VERIFY
> >  config RSA_VERIFY_WITH_PKEY
> >         bool "Execute RSA verification without key parameters from FDT"
> >         depends on RSA
> > +       imply RSA_PUBLIC_KEY_PARSER
> >         help
> >           The standard RSA-signature verification code (FIT_SIGNATURE) uses
> >           pre-calculated key properties, that are stored in fdt blob, in
> > diff --git a/lib/rsa/Makefile b/lib/rsa/Makefile
> > index c07305188e0c..14ed3cb4012b 100644
> > --- a/lib/rsa/Makefile
> > +++ b/lib/rsa/Makefile
> > @@ -6,4 +6,5 @@
> >  # Wolfgang Denk, DENX Software Engineering, wd@denx.de.
> >
> >  obj-$(CONFIG_$(SPL_)RSA_VERIFY) += rsa-verify.o rsa-checksum.o
> > +obj-$(CONFIG_RSA_VERIFY_WITH_PKEY) += rsa-keyprop.o
> >  obj-$(CONFIG_RSA_SOFTWARE_EXP) += rsa-mod-exp.o
> > diff --git a/lib/rsa/rsa-keyprop.c b/lib/rsa/rsa-keyprop.c
> > new file mode 100644
> > index 000000000000..9458337cc608
> > --- /dev/null
> > +++ b/lib/rsa/rsa-keyprop.c
> > @@ -0,0 +1,717 @@
> > +// SPDX-License-Identifier: GPL-2.0+ and MIT
> > +/*
> > + * RSA library - generate parameters for a public key
> > + *
> > + * Copyright (c) 2019 Linaro Limited
> > + * Author: AKASHI Takahiro
> > + *
> > + * Big number routines in this file come from BearSSL:
> 
> Can we put these in their own file if we expect to update them? Really
> should be called by the original filename and go in lib/bearsll.

Honestly, I'd rather disagree with you because
* in the original code, each file has only a single function, then
  we will have to introduce bunch of small source files.
* it is quite unlikely for other components to re-use some of
  those functions in the future.
So splitting the file would practically make little use.

> [..]
> 
> > +/**
> > + * rsa_gen_key_prop() - Generate key properties of RSA public key
> > + * @key:       Specifies key data in DER format
> > + * @keylen:    Length of @key
> > + *
> > + * This function takes a blob of encoded RSA public key data in DER
> > + * format, parse it and generate all the relevant properties
> > + * in key_prop structure.
> > + *
> > + * Return:     Pointer to struct key_prop on success, NULL on error
> > + */
> > +struct key_prop *rsa_gen_key_prop(const void *key, uint32_t keylen)
> > +{
> > +       struct key_prop *prop;
> > +       struct rsa_key rsa_key;
> > +#define BR_MAX_RSA_SIZE 4096
> 
> const int?

Will change it to
        const int max_rsa_size = 4096;

> > +       uint32_t *n, *rr, *rrtmp;
> > +       int rlen, i, ret;
> > +
> > +       prop = calloc(sizeof(*prop), 1);
> > +       if (!prop)
> > +               return NULL;
> > +       n = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
> > +       rr = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
> > +       rrtmp = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
> > +       if (!n || !rr || !rrtmp)
> > +               return NULL;
> 
> This can cause memory leak and will likely generate a coverity warning.

Okay, will fix it.

> > +
> > +       ret = rsa_parse_pub_key(&rsa_key, key, keylen);
> > +       if (ret)
> > +               goto err;
> > +
> > +       /* modulus */
> > +       /* removing leading 0's */
> > +       for (i = 0; i < rsa_key.n_sz && !rsa_key.n[i]; i++)
> > +               ;
> > +       prop->num_bits = (rsa_key.n_sz - i) * 8;
> > +       prop->modulus = malloc(rsa_key.n_sz - i);
> > +       if (!prop->modulus)
> > +               goto err;
> > +       memcpy((void *)prop->modulus, &rsa_key.n[i], rsa_key.n_sz - i);
> > +
> > +       /* exponent */
> > +       prop->public_exponent = calloc(1, sizeof(uint64_t));
> > +       if (!prop->public_exponent)
> > +               goto err;
> > +       memcpy((void *)prop->public_exponent + sizeof(uint64_t) - rsa_key.e_sz,
> > +              rsa_key.e, rsa_key.e_sz);
> > +       prop->exp_len = rsa_key.e_sz;
> > +
> > +       /* n0 inverse */
> > +       br_i32_decode(n, &rsa_key.n[i], rsa_key.n_sz - i);
> > +       prop->n0inv = br_i32_ninv32(n[1]);
> > +
> > +       /* R^2 mod n; R = 2^(num_bits) */
> > +       rlen = prop->num_bits * 2; /* #bits of R^2 = (2^num_bits)^2 */
> > +       rr[0] = 0;
> > +       *(uint8_t *)&rr[0] = (1 << (rlen % 8));
> > +       for (i = 1; i < (((rlen + 31) >> 5) + 1); i++)
> > +               rr[i] = 0;
> > +       br_i32_decode(rrtmp, rr, ((rlen + 7) >> 3) + 1);
> > +       br_i32_reduce(rr, rrtmp, n);
> > +
> > +       rlen = (prop->num_bits + 7) >> 3; /* #bytes of R^2 mod n */
> > +       prop->rr = malloc(rlen);
> > +       if (!prop->rr)
> > +               goto err;
> > +       br_i32_encode((void *)prop->rr, rlen, rr);
> > +
> > +       return prop;
> > +
> > +err:
> > +       free(n);
> > +       free(rr);
> > +       free(rrtmp);
> > +       rsa_free_key_prop(prop);
> > +       return NULL;
> 
> This should return -ENOMEM if we are out of memory. The caller cannot
> divine what went wrong.

Agree.

Thank you for your review,
-Takahiro Akashi


> > +}
> > --
> > 2.21.0
> >
> 
> Regards,
> Simon
diff mbox series

Patch

diff --git a/include/u-boot/rsa-mod-exp.h b/include/u-boot/rsa-mod-exp.h
index 8a428c4b6a1a..374169b8304e 100644
--- a/include/u-boot/rsa-mod-exp.h
+++ b/include/u-boot/rsa-mod-exp.h
@@ -26,6 +26,27 @@  struct key_prop {
 	uint32_t exp_len;	/* Exponent length in number of uint8_t */
 };
 
+/**
+ * rsa_gen_key_prop() - Generate key properties of RSA public key
+ * @key:	Specifies key data in DER format
+ * @keylen:	Length of @key
+ *
+ * This function takes a blob of encoded RSA public key data in DER
+ * format, parse it and generate all the relevant properties
+ * in key_prop structure.
+ *
+ * Return:	Pointer to struct key_prop on success, NULL on error
+ */
+struct key_prop *rsa_gen_key_prop(const void *key, uint32_t keylen);
+
+/**
+ * rsa_free_key_prop() - Free key properties
+ * @prop:	Pointer to struct key_prop
+ *
+ * This function frees all the memories allocated by rsa_gen_key_prop().
+ */
+void rsa_free_key_prop(struct key_prop *prop);
+
 /**
  * rsa_mod_exp_sw() - Perform RSA Modular Exponentiation in sw
  *
diff --git a/lib/rsa/Kconfig b/lib/rsa/Kconfig
index 71e4c06bf883..d1d6f6cf64a3 100644
--- a/lib/rsa/Kconfig
+++ b/lib/rsa/Kconfig
@@ -33,6 +33,7 @@  config RSA_VERIFY
 config RSA_VERIFY_WITH_PKEY
 	bool "Execute RSA verification without key parameters from FDT"
 	depends on RSA
+	imply RSA_PUBLIC_KEY_PARSER
 	help
 	  The standard RSA-signature verification code (FIT_SIGNATURE) uses
 	  pre-calculated key properties, that are stored in fdt blob, in
diff --git a/lib/rsa/Makefile b/lib/rsa/Makefile
index c07305188e0c..14ed3cb4012b 100644
--- a/lib/rsa/Makefile
+++ b/lib/rsa/Makefile
@@ -6,4 +6,5 @@ 
 # Wolfgang Denk, DENX Software Engineering, wd@denx.de.
 
 obj-$(CONFIG_$(SPL_)RSA_VERIFY) += rsa-verify.o rsa-checksum.o
+obj-$(CONFIG_RSA_VERIFY_WITH_PKEY) += rsa-keyprop.o
 obj-$(CONFIG_RSA_SOFTWARE_EXP) += rsa-mod-exp.o
diff --git a/lib/rsa/rsa-keyprop.c b/lib/rsa/rsa-keyprop.c
new file mode 100644
index 000000000000..9458337cc608
--- /dev/null
+++ b/lib/rsa/rsa-keyprop.c
@@ -0,0 +1,717 @@ 
+// SPDX-License-Identifier: GPL-2.0+ and MIT
+/*
+ * RSA library - generate parameters for a public key
+ *
+ * Copyright (c) 2019 Linaro Limited
+ * Author: AKASHI Takahiro
+ *
+ * Big number routines in this file come from BearSSL:
+ * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
+ */
+
+#include <common.h>
+#include <image.h>
+#include <malloc.h>
+#include <asm/byteorder.h>
+#include <crypto/internal/rsa.h>
+#include <u-boot/rsa-mod-exp.h>
+
+/**
+ * br_dec16be() - Convert 16-bit big-endian integer to native
+ * @src:	Pointer to data
+ * Return:	Native-endian integer
+ */
+static unsigned br_dec16be(const void *src)
+{
+	return be16_to_cpup(src);
+}
+
+/**
+ * br_dec32be() - Convert 32-bit big-endian integer to native
+ * @src:	Pointer to data
+ * Return:	Native-endian integer
+ */
+static uint32_t br_dec32be(const void *src)
+{
+	return be32_to_cpup(src);
+}
+
+/**
+ * br_enc32be() - Convert native 32-bit integer to big-endian
+ * @dst:	Pointer to buffer to store big-endian integer in
+ * @x:		Native 32-bit integer
+ */
+static void br_enc32be(void *dst, uint32_t x)
+{
+	__be32 tmp;
+
+	tmp = cpu_to_be32(x);
+	memcpy(dst, &tmp, sizeof(tmp));
+}
+
+/* from BearSSL's src/inner.h */
+
+/*
+ * Negate a boolean.
+ */
+static uint32_t NOT(uint32_t ctl)
+{
+	return ctl ^ 1;
+}
+
+/*
+ * Multiplexer: returns x if ctl == 1, y if ctl == 0.
+ */
+static uint32_t MUX(uint32_t ctl, uint32_t x, uint32_t y)
+{
+	return y ^ (-ctl & (x ^ y));
+}
+
+/*
+ * Equality check: returns 1 if x == y, 0 otherwise.
+ */
+static uint32_t EQ(uint32_t x, uint32_t y)
+{
+	uint32_t q;
+
+	q = x ^ y;
+	return NOT((q | -q) >> 31);
+}
+
+/*
+ * Inequality check: returns 1 if x != y, 0 otherwise.
+ */
+static uint32_t NEQ(uint32_t x, uint32_t y)
+{
+	uint32_t q;
+
+	q = x ^ y;
+	return (q | -q) >> 31;
+}
+
+/*
+ * Comparison: returns 1 if x > y, 0 otherwise.
+ */
+static uint32_t GT(uint32_t x, uint32_t y)
+{
+	/*
+	 * If both x < 2^31 and y < 2^31, then y-x will have its high
+	 * bit set if x > y, cleared otherwise.
+	 *
+	 * If either x >= 2^31 or y >= 2^31 (but not both), then the
+	 * result is the high bit of x.
+	 *
+	 * If both x >= 2^31 and y >= 2^31, then we can virtually
+	 * subtract 2^31 from both, and we are back to the first case.
+	 * Since (y-2^31)-(x-2^31) = y-x, the subtraction is already
+	 * fine.
+	 */
+	uint32_t z;
+
+	z = y - x;
+	return (z ^ ((x ^ y) & (x ^ z))) >> 31;
+}
+
+/*
+ * Compute the bit length of a 32-bit integer. Returned value is between 0
+ * and 32 (inclusive).
+ */
+static uint32_t BIT_LENGTH(uint32_t x)
+{
+	uint32_t k, c;
+
+	k = NEQ(x, 0);
+	c = GT(x, 0xFFFF); x = MUX(c, x >> 16, x); k += c << 4;
+	c = GT(x, 0x00FF); x = MUX(c, x >>  8, x); k += c << 3;
+	c = GT(x, 0x000F); x = MUX(c, x >>  4, x); k += c << 2;
+	c = GT(x, 0x0003); x = MUX(c, x >>  2, x); k += c << 1;
+	k += GT(x, 0x0001);
+	return k;
+}
+
+#define GE(x, y)   NOT(GT(y, x))
+#define LT(x, y)   GT(y, x)
+#define MUL(x, y)   ((uint64_t)(x) * (uint64_t)(y))
+
+/*
+ * Integers 'i32'
+ * --------------
+ *
+ * The 'i32' functions implement computations on big integers using
+ * an internal representation as an array of 32-bit integers. For
+ * an array x[]:
+ *  -- x[0] contains the "announced bit length" of the integer
+ *  -- x[1], x[2]... contain the value in little-endian order (x[1]
+ *     contains the least significant 32 bits)
+ *
+ * Multiplications rely on the elementary 32x32->64 multiplication.
+ *
+ * The announced bit length specifies the number of bits that are
+ * significant in the subsequent 32-bit words. Unused bits in the
+ * last (most significant) word are set to 0; subsequent words are
+ * uninitialized and need not exist at all.
+ *
+ * The execution time and memory access patterns of all computations
+ * depend on the announced bit length, but not on the actual word
+ * values. For modular integers, the announced bit length of any integer
+ * modulo n is equal to the actual bit length of n; thus, computations
+ * on modular integers are "constant-time" (only the modulus length may
+ * leak).
+ */
+
+/*
+ * Extract one word from an integer. The offset is counted in bits.
+ * The word MUST entirely fit within the word elements corresponding
+ * to the announced bit length of a[].
+ */
+static uint32_t br_i32_word(const uint32_t *a, uint32_t off)
+{
+	size_t u;
+	unsigned j;
+
+	u = (size_t)(off >> 5) + 1;
+	j = (unsigned)off & 31;
+	if (j == 0) {
+		return a[u];
+	} else {
+		return (a[u] >> j) | (a[u + 1] << (32 - j));
+	}
+}
+
+/* from BearSSL's src/int/i32_bitlen.c */
+
+/*
+ * Compute the actual bit length of an integer. The argument x should
+ * point to the first (least significant) value word of the integer.
+ * The len 'xlen' contains the number of 32-bit words to access.
+ *
+ * CT: value or length of x does not leak.
+ */
+static uint32_t br_i32_bit_length(uint32_t *x, size_t xlen)
+{
+	uint32_t tw, twk;
+
+	tw = 0;
+	twk = 0;
+	while (xlen -- > 0) {
+		uint32_t w, c;
+
+		c = EQ(tw, 0);
+		w = x[xlen];
+		tw = MUX(c, w, tw);
+		twk = MUX(c, (uint32_t)xlen, twk);
+	}
+	return (twk << 5) + BIT_LENGTH(tw);
+}
+
+/* from BearSSL's src/int/i32_decode.c */
+
+/*
+ * Decode an integer from its big-endian unsigned representation. The
+ * "true" bit length of the integer is computed, but all words of x[]
+ * corresponding to the full 'len' bytes of the source are set.
+ *
+ * CT: value or length of x does not leak.
+ */
+static void br_i32_decode(uint32_t *x, const void *src, size_t len)
+{
+	const unsigned char *buf;
+	size_t u, v;
+
+	buf = src;
+	u = len;
+	v = 1;
+	for (;;) {
+		if (u < 4) {
+			uint32_t w;
+
+			if (u < 2) {
+				if (u == 0) {
+					break;
+				} else {
+					w = buf[0];
+				}
+			} else {
+				if (u == 2) {
+					w = br_dec16be(buf);
+				} else {
+					w = ((uint32_t)buf[0] << 16)
+						| br_dec16be(buf + 1);
+				}
+			}
+			x[v ++] = w;
+			break;
+		} else {
+			u -= 4;
+			x[v ++] = br_dec32be(buf + u);
+		}
+	}
+	x[0] = br_i32_bit_length(x + 1, v - 1);
+}
+
+/* from BearSSL's src/int/i32_encode.c */
+
+/*
+ * Encode an integer into its big-endian unsigned representation. The
+ * output length in bytes is provided (parameter 'len'); if the length
+ * is too short then the integer is appropriately truncated; if it is
+ * too long then the extra bytes are set to 0.
+ */
+static void br_i32_encode(void *dst, size_t len, const uint32_t *x)
+{
+	unsigned char *buf;
+	size_t k;
+
+	buf = dst;
+
+	/*
+	 * Compute the announced size of x in bytes; extra bytes are
+	 * filled with zeros.
+	 */
+	k = (x[0] + 7) >> 3;
+	while (len > k) {
+		*buf ++ = 0;
+		len --;
+	}
+
+	/*
+	 * Now we use k as index within x[]. That index starts at 1;
+	 * we initialize it to the topmost complete word, and process
+	 * any remaining incomplete word.
+	 */
+	k = (len + 3) >> 2;
+	switch (len & 3) {
+	case 3:
+		*buf ++ = x[k] >> 16;
+		/* fall through */
+	case 2:
+		*buf ++ = x[k] >> 8;
+		/* fall through */
+	case 1:
+		*buf ++ = x[k];
+		k --;
+	}
+
+	/*
+	 * Encode all complete words.
+	 */
+	while (k > 0) {
+		br_enc32be(buf, x[k]);
+		k --;
+		buf += 4;
+	}
+}
+
+/* from BearSSL's src/int/i32_ninv32.c */
+
+/*
+ * Compute -(1/x) mod 2^32. If x is even, then this function returns 0.
+ */
+static uint32_t br_i32_ninv32(uint32_t x)
+{
+	uint32_t y;
+
+	y = 2 - x;
+	y *= 2 - y * x;
+	y *= 2 - y * x;
+	y *= 2 - y * x;
+	y *= 2 - y * x;
+	return MUX(x & 1, -y, 0);
+}
+
+/* from BearSSL's src/int/i32_add.c */
+
+/*
+ * Add b[] to a[] and return the carry (0 or 1). If ctl is 0, then a[]
+ * is unmodified, but the carry is still computed and returned. The
+ * arrays a[] and b[] MUST have the same announced bit length.
+ *
+ * a[] and b[] MAY be the same array, but partial overlap is not allowed.
+ */
+static uint32_t br_i32_add(uint32_t *a, const uint32_t *b, uint32_t ctl)
+{
+	uint32_t cc;
+	size_t u, m;
+
+	cc = 0;
+	m = (a[0] + 63) >> 5;
+	for (u = 1; u < m; u ++) {
+		uint32_t aw, bw, naw;
+
+		aw = a[u];
+		bw = b[u];
+		naw = aw + bw + cc;
+
+		/*
+		 * Carry is 1 if naw < aw. Carry is also 1 if naw == aw
+		 * AND the carry was already 1.
+		 */
+		cc = (cc & EQ(naw, aw)) | LT(naw, aw);
+		a[u] = MUX(ctl, naw, aw);
+	}
+	return cc;
+}
+
+/* from BearSSL's src/int/i32_sub.c */
+
+/*
+ * Subtract b[] from a[] and return the carry (0 or 1). If ctl is 0,
+ * then a[] is unmodified, but the carry is still computed and returned.
+ * The arrays a[] and b[] MUST have the same announced bit length.
+ *
+ * a[] and b[] MAY be the same array, but partial overlap is not allowed.
+ */
+static uint32_t br_i32_sub(uint32_t *a, const uint32_t *b, uint32_t ctl)
+{
+	uint32_t cc;
+	size_t u, m;
+
+	cc = 0;
+	m = (a[0] + 63) >> 5;
+	for (u = 1; u < m; u ++) {
+		uint32_t aw, bw, naw;
+
+		aw = a[u];
+		bw = b[u];
+		naw = aw - bw - cc;
+
+		/*
+		 * Carry is 1 if naw > aw. Carry is 1 also if naw == aw
+		 * AND the carry was already 1.
+		 */
+		cc = (cc & EQ(naw, aw)) | GT(naw, aw);
+		a[u] = MUX(ctl, naw, aw);
+	}
+	return cc;
+}
+
+/* from BearSSL's src/int/i32_div32.c */
+
+/*
+ * Constant-time division. The dividend hi:lo is divided by the
+ * divisor d; the quotient is returned and the remainder is written
+ * in *r. If hi == d, then the quotient does not fit on 32 bits;
+ * returned value is thus truncated. If hi > d, returned values are
+ * indeterminate.
+ */
+static uint32_t br_divrem(uint32_t hi, uint32_t lo, uint32_t d, uint32_t *r)
+{
+	/* TODO: optimize this */
+	uint32_t q;
+	uint32_t ch, cf;
+	int k;
+
+	q = 0;
+	ch = EQ(hi, d);
+	hi = MUX(ch, 0, hi);
+	for (k = 31; k > 0; k --) {
+		int j;
+		uint32_t w, ctl, hi2, lo2;
+
+		j = 32 - k;
+		w = (hi << j) | (lo >> k);
+		ctl = GE(w, d) | (hi >> k);
+		hi2 = (w - d) >> j;
+		lo2 = lo - (d << k);
+		hi = MUX(ctl, hi2, hi);
+		lo = MUX(ctl, lo2, lo);
+		q |= ctl << k;
+	}
+	cf = GE(lo, d) | hi;
+	q |= cf;
+	*r = MUX(cf, lo - d, lo);
+	return q;
+}
+
+/*
+ * Wrapper for br_divrem(); the remainder is returned, and the quotient
+ * is discarded.
+ */
+static uint32_t br_rem(uint32_t hi, uint32_t lo, uint32_t d)
+{
+	uint32_t r;
+
+	br_divrem(hi, lo, d, &r);
+	return r;
+}
+
+/*
+ * Wrapper for br_divrem(); the quotient is returned, and the remainder
+ * is discarded.
+ */
+static uint32_t br_div(uint32_t hi, uint32_t lo, uint32_t d)
+{
+	uint32_t r;
+
+	return br_divrem(hi, lo, d, &r);
+}
+
+/* from BearSSL's src/int/i32_muladd.c */
+
+/*
+ * Multiply x[] by 2^32 and then add integer z, modulo m[]. This
+ * function assumes that x[] and m[] have the same announced bit
+ * length, and the announced bit length of m[] matches its true
+ * bit length.
+ *
+ * x[] and m[] MUST be distinct arrays.
+ *
+ * CT: only the common announced bit length of x and m leaks, not
+ * the values of x, z or m.
+ */
+static void br_i32_muladd_small(uint32_t *x, uint32_t z, const uint32_t *m)
+{
+	uint32_t m_bitlen;
+	size_t u, mlen;
+	uint32_t a0, a1, b0, hi, g, q, tb;
+	uint32_t chf, clow, under, over;
+	uint64_t cc;
+
+	/*
+	 * We can test on the modulus bit length since we accept to
+	 * leak that length.
+	 */
+	m_bitlen = m[0];
+	if (m_bitlen == 0) {
+		return;
+	}
+	if (m_bitlen <= 32) {
+		x[1] = br_rem(x[1], z, m[1]);
+		return;
+	}
+	mlen = (m_bitlen + 31) >> 5;
+
+	/*
+	 * Principle: we estimate the quotient (x*2^32+z)/m by
+	 * doing a 64/32 division with the high words.
+	 *
+	 * Let:
+	 *   w = 2^32
+	 *   a = (w*a0 + a1) * w^N + a2
+	 *   b = b0 * w^N + b2
+	 * such that:
+	 *   0 <= a0 < w
+	 *   0 <= a1 < w
+	 *   0 <= a2 < w^N
+	 *   w/2 <= b0 < w
+	 *   0 <= b2 < w^N
+	 *   a < w*b
+	 * I.e. the two top words of a are a0:a1, the top word of b is
+	 * b0, we ensured that b0 is "full" (high bit set), and a is
+	 * such that the quotient q = a/b fits on one word (0 <= q < w).
+	 *
+	 * If a = b*q + r (with 0 <= r < q), we can estimate q by
+	 * doing an Euclidean division on the top words:
+	 *   a0*w+a1 = b0*u + v  (with 0 <= v < w)
+	 * Then the following holds:
+	 *   0 <= u <= w
+	 *   u-2 <= q <= u
+	 */
+	a0 = br_i32_word(x, m_bitlen - 32);
+	hi = x[mlen];
+	memmove(x + 2, x + 1, (mlen - 1) * sizeof *x);
+	x[1] = z;
+	a1 = br_i32_word(x, m_bitlen - 32);
+	b0 = br_i32_word(m, m_bitlen - 32);
+
+	/*
+	 * We estimate a divisor q. If the quotient returned by br_div()
+	 * is g:
+	 * -- If a0 == b0 then g == 0; we want q = 0xFFFFFFFF.
+	 * -- Otherwise:
+	 *    -- if g == 0 then we set q = 0;
+	 *    -- otherwise, we set q = g - 1.
+	 * The properties described above then ensure that the true
+	 * quotient is q-1, q or q+1.
+	 */
+	g = br_div(a0, a1, b0);
+	q = MUX(EQ(a0, b0), 0xFFFFFFFF, MUX(EQ(g, 0), 0, g - 1));
+
+	/*
+	 * We subtract q*m from x (with the extra high word of value 'hi').
+	 * Since q may be off by 1 (in either direction), we may have to
+	 * add or subtract m afterwards.
+	 *
+	 * The 'tb' flag will be true (1) at the end of the loop if the
+	 * result is greater than or equal to the modulus (not counting
+	 * 'hi' or the carry).
+	 */
+	cc = 0;
+	tb = 1;
+	for (u = 1; u <= mlen; u ++) {
+		uint32_t mw, zw, xw, nxw;
+		uint64_t zl;
+
+		mw = m[u];
+		zl = MUL(mw, q) + cc;
+		cc = (uint32_t)(zl >> 32);
+		zw = (uint32_t)zl;
+		xw = x[u];
+		nxw = xw - zw;
+		cc += (uint64_t)GT(nxw, xw);
+		x[u] = nxw;
+		tb = MUX(EQ(nxw, mw), tb, GT(nxw, mw));
+	}
+
+	/*
+	 * If we underestimated q, then either cc < hi (one extra bit
+	 * beyond the top array word), or cc == hi and tb is true (no
+	 * extra bit, but the result is not lower than the modulus). In
+	 * these cases we must subtract m once.
+	 *
+	 * Otherwise, we may have overestimated, which will show as
+	 * cc > hi (thus a negative result). Correction is adding m once.
+	 */
+	chf = (uint32_t)(cc >> 32);
+	clow = (uint32_t)cc;
+	over = chf | GT(clow, hi);
+	under = ~over & (tb | (~chf & LT(clow, hi)));
+	br_i32_add(x, m, over);
+	br_i32_sub(x, m, under);
+}
+
+/* from BearSSL's src/int/i32_reduce.c */
+
+/*
+ * Reduce an integer (a[]) modulo another (m[]). The result is written
+ * in x[] and its announced bit length is set to be equal to that of m[].
+ *
+ * x[] MUST be distinct from a[] and m[].
+ *
+ * CT: only announced bit lengths leak, not values of x, a or m.
+ */
+static void br_i32_reduce(uint32_t *x, const uint32_t *a, const uint32_t *m)
+{
+	uint32_t m_bitlen, a_bitlen;
+	size_t mlen, alen, u;
+
+	m_bitlen = m[0];
+	mlen = (m_bitlen + 31) >> 5;
+
+	x[0] = m_bitlen;
+	if (m_bitlen == 0) {
+		return;
+	}
+
+	/*
+	 * If the source is shorter, then simply copy all words from a[]
+	 * and zero out the upper words.
+	 */
+	a_bitlen = a[0];
+	alen = (a_bitlen + 31) >> 5;
+	if (a_bitlen < m_bitlen) {
+		memcpy(x + 1, a + 1, alen * sizeof *a);
+		for (u = alen; u < mlen; u ++) {
+			x[u + 1] = 0;
+		}
+		return;
+	}
+
+	/*
+	 * The source length is at least equal to that of the modulus.
+	 * We must thus copy N-1 words, and input the remaining words
+	 * one by one.
+	 */
+	memcpy(x + 1, a + 2 + (alen - mlen), (mlen - 1) * sizeof *a);
+	x[mlen] = 0;
+	for (u = 1 + alen - mlen; u > 0; u --) {
+		br_i32_muladd_small(x, a[u], m);
+	}
+}
+
+/**
+ * rsa_free_key_prop() - Free key properties
+ * @prop:	Pointer to struct key_prop
+ *
+ * This function frees all the memories allocated by rsa_gen_key_prop().
+ */
+void rsa_free_key_prop(struct key_prop *prop)
+{
+	if (!prop)
+		return;
+
+	free((void *)prop->modulus);
+	free((void *)prop->public_exponent);
+	free((void *)prop->rr);
+
+	free(prop);
+}
+
+/**
+ * rsa_gen_key_prop() - Generate key properties of RSA public key
+ * @key:	Specifies key data in DER format
+ * @keylen:	Length of @key
+ *
+ * This function takes a blob of encoded RSA public key data in DER
+ * format, parse it and generate all the relevant properties
+ * in key_prop structure.
+ *
+ * Return:	Pointer to struct key_prop on success, NULL on error
+ */
+struct key_prop *rsa_gen_key_prop(const void *key, uint32_t keylen)
+{
+	struct key_prop *prop;
+	struct rsa_key rsa_key;
+#define BR_MAX_RSA_SIZE 4096
+	uint32_t *n, *rr, *rrtmp;
+	int rlen, i, ret;
+
+	prop = calloc(sizeof(*prop), 1);
+	if (!prop)
+		return NULL;
+	n = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
+	rr = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
+	rrtmp = calloc(sizeof(uint32_t), 1 + (BR_MAX_RSA_SIZE >> 5));
+	if (!n || !rr || !rrtmp)
+		return NULL;
+
+	ret = rsa_parse_pub_key(&rsa_key, key, keylen);
+	if (ret)
+		goto err;
+
+	/* modulus */
+	/* removing leading 0's */
+	for (i = 0; i < rsa_key.n_sz && !rsa_key.n[i]; i++)
+		;
+	prop->num_bits = (rsa_key.n_sz - i) * 8;
+	prop->modulus = malloc(rsa_key.n_sz - i);
+	if (!prop->modulus)
+		goto err;
+	memcpy((void *)prop->modulus, &rsa_key.n[i], rsa_key.n_sz - i);
+
+	/* exponent */
+	prop->public_exponent = calloc(1, sizeof(uint64_t));
+	if (!prop->public_exponent)
+		goto err;
+	memcpy((void *)prop->public_exponent + sizeof(uint64_t) - rsa_key.e_sz,
+	       rsa_key.e, rsa_key.e_sz);
+	prop->exp_len = rsa_key.e_sz;
+
+	/* n0 inverse */
+	br_i32_decode(n, &rsa_key.n[i], rsa_key.n_sz - i);
+	prop->n0inv = br_i32_ninv32(n[1]);
+
+	/* R^2 mod n; R = 2^(num_bits) */
+	rlen = prop->num_bits * 2; /* #bits of R^2 = (2^num_bits)^2 */
+	rr[0] = 0;
+	*(uint8_t *)&rr[0] = (1 << (rlen % 8));
+	for (i = 1; i < (((rlen + 31) >> 5) + 1); i++)
+		rr[i] = 0;
+	br_i32_decode(rrtmp, rr, ((rlen + 7) >> 3) + 1);
+	br_i32_reduce(rr, rrtmp, n);
+
+	rlen = (prop->num_bits + 7) >> 3; /* #bytes of R^2 mod n */
+	prop->rr = malloc(rlen);
+	if (!prop->rr)
+		goto err;
+	br_i32_encode((void *)prop->rr, rlen, rr);
+
+	return prop;
+
+err:
+	free(n);
+	free(rr);
+	free(rrtmp);
+	rsa_free_key_prop(prop);
+	return NULL;
+}