You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@nuttx.apache.org by xi...@apache.org on 2023/10/18 04:23:19 UTC
[nuttx] branch master updated (48ca996ad7 -> 3dbe2d790e)
This is an automated email from the ASF dual-hosted git repository.
xiaoxiang pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/nuttx.git
from 48ca996ad7 arch: arm64 support smp function call
new 12935f2d33 crypto/bn: porting tiny-Bignum-C into nuttx crypto
new aeac109e50 crypto/bn:Add exponentiation algorithm in bignum
new 3dbe2d790e crypto/rsa_verify: export rsa verify via /dev/crypto
The 3 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
crypto/CMakeLists.txt | 1 +
crypto/Makefile | 1 +
crypto/bn.c | 796 ++++++++++++++++++++++++++++++++++++++++++++
crypto/cryptodev.c | 4 +
crypto/cryptosoft.c | 65 ++++
include/crypto/bn.h | 212 ++++++++++++
include/crypto/cryptodev.h | 26 +-
include/crypto/cryptosoft.h | 2 +
8 files changed, 1095 insertions(+), 12 deletions(-)
create mode 100644 crypto/bn.c
create mode 100644 include/crypto/bn.h
[nuttx] 02/03: crypto/bn:Add exponentiation algorithm in bignum
Posted by xi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
xiaoxiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit aeac109e5013a6e3aeb2d7f9a7149207a05b369e
Author: makejian <ma...@xiaomi.com>
AuthorDate: Sun Jun 25 20:35:21 2023 +0800
crypto/bn:Add exponentiation algorithm in bignum
add exponentiation algorithm: pow_mod_faster
Signed-off-by: makejian <ma...@xiaomi.com>
---
crypto/bn.c | 32 ++++++++++++++++++++++++++++++++
include/crypto/bn.h | 5 +++++
2 files changed, 37 insertions(+)
diff --git a/crypto/bn.c b/crypto/bn.c
index 3e3aead74d..e21368bab9 100644
--- a/crypto/bn.c
+++ b/crypto/bn.c
@@ -762,3 +762,35 @@ void bignum_assign(FAR struct bn *dst, FAR struct bn *src)
dst->array[i] = src->array[i];
}
}
+
+void pow_mod_faster(FAR struct bn *a, FAR struct bn *b,
+ FAR struct bn *n, FAR struct bn *res)
+{
+ struct bn tmpa;
+ struct bn tmpb;
+ struct bn tmp;
+ bignum_assign(&tmpa, a);
+ bignum_assign(&tmpb, b);
+
+ bignum_from_int(res, 1); /* r = 1 */
+
+ while (1)
+ {
+ if (tmpb.array[0] & 1) /* if (b % 2) */
+ {
+ bignum_mul(res, &tmpa, &tmp); /* r = r * a % m */
+ bignum_mod(&tmp, n, res);
+ }
+
+ bignum_rshift(&tmpb, &tmp, 1); /* b /= 2 */
+ bignum_assign(&tmpb, &tmp);
+
+ if (bignum_is_zero(&tmpb))
+ {
+ break;
+ }
+
+ bignum_mul(&tmpa, &tmpa, &tmp);
+ bignum_mod(&tmp, n, &tmpa);
+ }
+}
diff --git a/include/crypto/bn.h b/include/crypto/bn.h
index 722c318efe..4c0e69a41f 100644
--- a/include/crypto/bn.h
+++ b/include/crypto/bn.h
@@ -204,4 +204,9 @@ void bignum_isqrt(FAR struct bn *a, FAR struct bn *b);
void bignum_assign(FAR struct bn *dst, FAR struct bn *src);
+/* CRK_EXP_MOD algorithm */
+
+void pow_mod_faster(FAR struct bn *a, FAR struct bn *b,
+ FAR struct bn *n, FAR struct bn *res);
+
#endif /* __INCLUDE_CRYPTO_BIGNUM_H */
[nuttx] 03/03: crypto/rsa_verify: export rsa verify via /dev/crypto
Posted by xi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
xiaoxiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit 3dbe2d790ebb323cb27a03588e4b8e399a029fd1
Author: makejian <ma...@xiaomi.com>
AuthorDate: Wed Sep 20 22:22:39 2023 +0800
crypto/rsa_verify: export rsa verify via /dev/crypto
kernel supports asymmetric encryption RSA signature verification
Signed-off-by: makejian <ma...@xiaomi.com>
---
crypto/cryptodev.c | 4 +++
crypto/cryptosoft.c | 65 +++++++++++++++++++++++++++++++++++++++++++++
include/crypto/cryptodev.h | 26 +++++++++---------
include/crypto/cryptosoft.h | 2 ++
4 files changed, 85 insertions(+), 12 deletions(-)
diff --git a/crypto/cryptodev.c b/crypto/cryptodev.c
index aaa89a11ba..d810079008 100644
--- a/crypto/cryptodev.c
+++ b/crypto/cryptodev.c
@@ -588,6 +588,10 @@ int cryptodev_key(FAR struct crypt_kop *kop)
if (in == 3 && out == 1)
break;
return -EINVAL;
+ case CRK_RSA_PCKS15_VERIFY:
+ if (in == 5 && out == 0)
+ break;
+ return -EINVAL;
default:
return -EINVAL;
}
diff --git a/crypto/cryptosoft.c b/crypto/cryptosoft.c
index 1281e70281..fc007eb5cd 100644
--- a/crypto/cryptosoft.c
+++ b/crypto/cryptosoft.c
@@ -29,6 +29,7 @@
#include <errno.h>
#include <endian.h>
#include <nuttx/kmalloc.h>
+#include <crypto/bn.h>
#include <crypto/cryptodev.h>
#include <crypto/cryptosoft.h>
#include <crypto/xform.h>
@@ -1097,11 +1098,72 @@ done:
return 0;
}
+int swcr_rsa_verify(struct cryptkop *krp)
+{
+ uint8_t *exp = (uint8_t *)krp->krp_param[0].crp_p;
+ uint8_t *modulus = (uint8_t *)krp->krp_param[1].crp_p;
+ uint8_t *sig = (uint8_t *)krp->krp_param[2].crp_p;
+ uint8_t *hash = (uint8_t *)krp->krp_param[3].crp_p;
+ uint8_t *padding = (uint8_t *)krp->krp_param[4].crp_p;
+ int exp_len = krp->krp_param[0].crp_nbits / 8;
+ int modulus_len = krp->krp_param[1].crp_nbits / 8;
+ int sig_len = krp->krp_param[2].crp_nbits / 8;
+ int hash_len = krp->krp_param[3].crp_nbits / 8;
+ int padding_len = krp->krp_param[4].crp_nbits / 8;
+ struct bn a;
+ struct bn e;
+ struct bn n;
+ struct bn r;
+
+ bignum_init(&a);
+ bignum_init(&e);
+ bignum_init(&n);
+ bignum_init(&r);
+ memcpy(e.array, exp, exp_len);
+ memcpy(n.array, modulus, modulus_len);
+ memcpy(a.array, sig, sig_len);
+ pow_mod_faster(&a, &e, &n, &r);
+ return !!memcmp(r.array, hash, hash_len) +
+ !!memcmp(r.array + hash_len, padding, padding_len);
+}
+
+int swcr_kprocess(struct cryptkop *krp)
+{
+ /* Sanity check */
+
+ if (krp == NULL)
+ {
+ return -EINVAL;
+ }
+
+ /* Go through crypto descriptors, processing as we go */
+
+ switch (krp->krp_op)
+ {
+ case CRK_RSA_PCKS15_VERIFY:
+ if ((krp->krp_status = swcr_rsa_verify(krp)) != 0)
+ {
+ goto done;
+ }
+ break;
+ default:
+
+ /* Unknown/unsupported algorithm */
+
+ krp->krp_status = -EINVAL;
+ goto done;
+ }
+
+done:
+ return 0;
+}
+
/* Initialize the driver, called from the kernel main(). */
void swcr_init(void)
{
int algs[CRYPTO_ALGORITHM_MAX + 1];
+ int kalgs[CRK_ALGORITHM_MAX + 1];
int flags = CRYPTOCAP_F_SOFTWARE | CRYPTOCAP_F_ENCRYPT_MAC |
CRYPTOCAP_F_MAC_ENCRYPT;
@@ -1146,4 +1208,7 @@ void swcr_init(void)
crypto_register(swcr_id, algs, swcr_newsession,
swcr_freesession, swcr_process);
+
+ kalgs[CRK_RSA_PCKS15_VERIFY] = CRYPTO_ALG_FLAG_SUPPORTED;
+ crypto_kregister(swcr_id, kalgs, swcr_kprocess);
}
diff --git a/include/crypto/cryptodev.h b/include/crypto/cryptodev.h
index 9357669647..86c8e7e4dd 100644
--- a/include/crypto/cryptodev.h
+++ b/include/crypto/cryptodev.h
@@ -240,18 +240,20 @@ struct crypt_kop
struct crparam crk_param[CRK_MAXPARAM];
};
-#define CRK_MOD_EXP 0
-#define CRK_MOD_EXP_CRT 1
-#define CRK_DSA_SIGN 2
-#define CRK_DSA_VERIFY 3
-#define CRK_DH_COMPUTE_KEY 4
-#define CRK_ALGORITHM_MAX 4 /* Keep updated */
-
-#define CRF_MOD_EXP (1 << CRK_MOD_EXP)
-#define CRF_MOD_EXP_CRT (1 << CRK_MOD_EXP_CRT)
-#define CRF_DSA_SIGN (1 << CRK_DSA_SIGN)
-#define CRF_DSA_VERIFY (1 << CRK_DSA_VERIFY)
-#define CRF_DH_COMPUTE_KEY (1 << CRK_DH_COMPUTE_KEY)
+#define CRK_MOD_EXP 0
+#define CRK_MOD_EXP_CRT 1
+#define CRK_DSA_SIGN 2
+#define CRK_DSA_VERIFY 3
+#define CRK_DH_COMPUTE_KEY 4
+#define CRK_RSA_PCKS15_VERIFY 5
+#define CRK_ALGORITHM_MAX 5 /* Keep updated */
+
+#define CRF_MOD_EXP (1 << CRK_MOD_EXP)
+#define CRF_MOD_EXP_CRT (1 << CRK_MOD_EXP_CRT)
+#define CRF_DSA_SIGN (1 << CRK_DSA_SIGN)
+#define CRF_DSA_VERIFY (1 << CRK_DSA_VERIFY)
+#define CRF_DH_COMPUTE_KEY (1 << CRK_DH_COMPUTE_KEY)
+#define CRF_RSA_PCKS15_VERIFY (1 << CRK_RSA_PCKS15_VERIFY)
struct cryptkop
{
diff --git a/include/crypto/cryptosoft.h b/include/crypto/cryptosoft.h
index 36aca9a838..e28f935412 100644
--- a/include/crypto/cryptosoft.h
+++ b/include/crypto/cryptosoft.h
@@ -83,7 +83,9 @@ int swcr_authcompute(FAR struct cryptop *, FAR struct cryptodesc *,
int swcr_authenc(FAR struct cryptop *);
int swcr_compdec(FAR struct cryptodesc *, FAR struct swcr_data *,
caddr_t, int);
+int swcr_rsa_verify(FAR struct cryptkop *);
int swcr_process(FAR struct cryptop *);
+int swcr_kprocess(FAR struct cryptkop *);
int swcr_newsession(FAR uint32_t *, FAR struct cryptoini *);
int swcr_freesession(uint64_t);
void swcr_init(void);
[nuttx] 01/03: crypto/bn: porting tiny-Bignum-C into nuttx crypto
Posted by xi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
xiaoxiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit 12935f2d3300d6ce8e5542f82e279dabea96d793
Author: makejian <ma...@xiaomi.com>
AuthorDate: Sun Jun 25 10:03:32 2023 +0800
crypto/bn: porting tiny-Bignum-C into nuttx crypto
porting from https://github.com/kokke/tiny-bignum-c commit ac136565378c624365e0f5f556d386b3966bff32 and adapting to the nuttx
Signed-off-by: makejian <ma...@xiaomi.com>
---
crypto/CMakeLists.txt | 1 +
crypto/Makefile | 1 +
crypto/bn.c | 764 ++++++++++++++++++++++++++++++++++++++++++++++++++
include/crypto/bn.h | 207 ++++++++++++++
4 files changed, 973 insertions(+)
diff --git a/crypto/CMakeLists.txt b/crypto/CMakeLists.txt
index 744cfe8099..50bff44c21 100644
--- a/crypto/CMakeLists.txt
+++ b/crypto/CMakeLists.txt
@@ -60,6 +60,7 @@ if(CONFIG_CRYPTO)
list(APPEND SRCS siphash.c)
list(APPEND SRCS hmac_buff.c)
list(APPEND SRCS curve25519.c)
+ list(APPEND SRCS bn.c)
# Entropy pool random number generator
diff --git a/crypto/Makefile b/crypto/Makefile
index f666175b38..de41512f5e 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -64,6 +64,7 @@ CRYPTO_CSRCS += key_wrap.c
CRYPTO_CSRCS += siphash.c
CRYPTO_CSRCS += hmac_buff.c
CRYPTO_CSRCS += curve25519.c
+CRYPTO_CSRCS += bn.c
# Entropy pool random number generator
diff --git a/crypto/bn.c b/crypto/bn.c
new file mode 100644
index 0000000000..3e3aead74d
--- /dev/null
+++ b/crypto/bn.c
@@ -0,0 +1,764 @@
+/****************************************************************************
+ * crypto/bn.c
+ * This is free and unencumbered software released into the public domain.
+ * Anyone is free to copy, modify, publish, use, compile, sell, or
+ * distribute this software, either in source code form or as a compiled
+ * binary, for any purpose, commercial or non-commercial, and by any
+ * means.
+ * In jurisdictions that recognize copyright laws, the author or authors
+ * of this software dedicate any and all copyright interest in the
+ * software to the public domain. We make this dedication for the benefit
+ * of the public at large and to the detriment of our heirs and
+ * successors. We intend this dedication to be an overt act of
+ * relinquishment in perpetuity of all present and future rights to this
+ * software under copyright law.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ * For more information, please refer to <https://unlicense.org>
+ ****************************************************************************/
+
+/* Big number library - arithmetic on multiple-precision unsigned integers.
+ *
+ * This library is an implementation of arithmetic on arbitrarily large
+ * integers.
+ *
+ * The difference between this and other implementations, is that the data
+ * structure has optimal memory utilization (i.e. a 1024 bit integer takes up
+ * 128 bytes RAM), and all memory is allocated statically: no dynamic
+ * allocation for better or worse.
+ *
+ * Primary goals are correctness, clarity of code and clean, portable
+ * implementation. Secondary goal is a memory footprint small enough to make
+ * it suitable for use in embedded applications.
+ *
+ *
+ * The current state is correct functionality and adequate performance.
+ * There may well be room for performance-optimizations and improvements.
+ */
+
+/****************************************************************************
+ * Included Files
+ ****************************************************************************/
+
+#include <stdio.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <crypto/bn.h>
+
+/****************************************************************************
+ * Pre-processor Definitions
+ ****************************************************************************/
+
+/* Custom assert macro - easy to disable */
+
+#define require(p, msg) assert(p && msg)
+
+/****************************************************************************
+ * Private Functions Prototype
+ ****************************************************************************/
+
+/* Functions for shifting number in-place. */
+
+static void lshift_one_bit(FAR struct bn *a);
+static void rshift_one_bit(FAR struct bn *a);
+static void lshift_word(FAR struct bn *a, int nwords);
+static void rshift_word(FAR struct bn *a, int nwords);
+
+/****************************************************************************
+ * Private Functions
+ ****************************************************************************/
+
+/* Private / Static functions. */
+
+static void rshift_word(FAR struct bn *a, int nwords)
+{
+ /* Naive method: */
+
+ int i;
+
+ require(a, "a is null");
+ require(nwords >= 0, "no negative shifts");
+
+ if (nwords >= BN_ARRAY_SIZE)
+ {
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ a->array[i] = 0;
+ }
+
+ return;
+ }
+
+ for (i = 0; i < BN_ARRAY_SIZE - nwords; ++i)
+ {
+ a->array[i] = a->array[i + nwords];
+ }
+
+ for (; i < BN_ARRAY_SIZE; ++i)
+ {
+ a->array[i] = 0;
+ }
+}
+
+static void lshift_word(FAR struct bn *a, int nwords)
+{
+ int i;
+
+ require(a, "a is null");
+ require(nwords >= 0, "no negative shifts");
+
+ /* Shift whole words */
+
+ for (i = (BN_ARRAY_SIZE - 1); i >= nwords; --i)
+ {
+ a->array[i] = a->array[i - nwords];
+ }
+
+ /* Zero pad shifted words. */
+
+ for (; i >= 0; --i)
+ {
+ a->array[i] = 0;
+ }
+}
+
+static void lshift_one_bit(FAR struct bn *a)
+{
+ int i;
+
+ require(a, "a is null");
+
+ for (i = (BN_ARRAY_SIZE - 1); i > 0; --i)
+ {
+ a->array[i] = (a->array[i] << 1) |
+ (a->array[i - 1] >> ((8 * WORD_SIZE) - 1));
+ }
+
+ a->array[0] <<= 1;
+}
+
+static void rshift_one_bit(FAR struct bn *a)
+{
+ int i;
+
+ require(a, "a is null");
+
+ for (i = 0; i < (BN_ARRAY_SIZE - 1); ++i)
+ {
+ a->array[i] = (a->array[i] >> 1) |
+ (a->array[i + 1] << ((8 * WORD_SIZE) - 1));
+ }
+
+ a->array[BN_ARRAY_SIZE - 1] >>= 1;
+}
+
+/****************************************************************************
+ * Public Functions
+ ****************************************************************************/
+
+/* Public / Exported functions. */
+
+void bignum_init(FAR struct bn *n)
+{
+ int i;
+
+ require(n, "n is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ n->array[i] = 0;
+ }
+}
+
+void bignum_from_int(FAR struct bn *n, DTYPE_TMP i)
+{
+ require(n, "n is null");
+
+ bignum_init(n);
+
+ /* Endianness issue if machine is not little-endian? */
+
+#ifdef WORD_SIZE
+# if (WORD_SIZE == 1)
+ n->array[0] = (i & 0x000000ff);
+ n->array[1] = (i & 0x0000ff00) >> 8;
+ n->array[2] = (i & 0x00ff0000) >> 16;
+ n->array[3] = (i & 0xff000000) >> 24;
+# elif (WORD_SIZE == 2)
+ n->array[0] = (i & 0x0000ffff);
+ n->array[1] = (i & 0xffff0000) >> 16;
+# elif (WORD_SIZE == 4)
+ n->array[0] = i;
+ DTYPE_TMP num_32 = 32;
+ DTYPE_TMP tmp = i >> num_32; /* bit-shift with U64 operands to force
+ * 64-bit results */
+ n->array[1] = tmp;
+# endif
+#endif
+}
+
+int bignum_to_int(FAR struct bn *n)
+{
+ int ret = 0;
+
+ require(n, "n is null");
+
+ /* Endianness issue if machine is not little-endian? */
+
+#if (WORD_SIZE == 1)
+ ret += n->array[0];
+ ret += n->array[1] << 8;
+ ret += n->array[2] << 16;
+ ret += n->array[3] << 24;
+#elif (WORD_SIZE == 2)
+ ret += n->array[0];
+ ret += n->array[1] << 16;
+#elif (WORD_SIZE == 4)
+ ret += n->array[0];
+#endif
+
+ return ret;
+}
+
+void bignum_from_string(FAR struct bn *n, FAR char *str, int nbytes)
+{
+ DTYPE tmp; /* DTYPE is defined in bn.h -
+ * uint{8,16,32,64}_t */
+ int i = nbytes - (2 * WORD_SIZE); /* index into string */
+ int j = 0; /* index into array */
+
+ require(n, "n is null");
+ require(str, "str is null");
+ require(nbytes > 0, "nbytes must be positive");
+ require((nbytes & 1) == 0,
+ "string format must be in hex -> equal number of bytes");
+ require((nbytes % (sizeof(DTYPE) * 2)) == 0,
+ "string length must be a multiple of (sizeof(DTYPE) * 2) characters");
+
+ bignum_init(n);
+
+ /* reading last hex-byte "MSB" from string first -> big endian
+ * MSB ~= most significant byte / block ? :)
+ */
+
+ while (i >= 0)
+ {
+ tmp = 0;
+ sscanf(&str[i], SSCANF_FORMAT_STR, &tmp);
+ n->array[j] = tmp;
+ i -= (2 * WORD_SIZE); /* step WORD_SIZE hex-byte(s) back in
+ * the string. */
+ j += 1; /* step one element forward in the
+ * array. */
+ }
+}
+
+void bignum_to_string(FAR struct bn *n, FAR char *str, int nbytes)
+{
+ int j = BN_ARRAY_SIZE - 1; /* index into array - reading "MSB" first
+ * -> big-endian */
+ int i = 0; /* index into string representation. */
+
+ require(n, "n is null");
+ require(str, "str is null");
+ require(nbytes > 0, "nbytes must be positive");
+ require((nbytes & 1) == 0,
+ "string format must be in hex -> equal number of bytes");
+
+ /* reading last array-element "MSB" first -> big endian */
+
+ while ((j >= 0) && (nbytes > (i + 1)))
+ {
+ sprintf(&str[i], SPRINTF_FORMAT_STR, n->array[j]);
+ i += (2 * WORD_SIZE); /* step WORD_SIZE hex-byte(s) forward in the
+ * string. */
+ j -= 1; /* step one element back in the array. */
+ }
+
+ /* Count leading zeros: */
+
+ j = 0;
+ while (str[j] == '0')
+ {
+ j += 1;
+ }
+
+ /* Move string j places ahead, effectively skipping leading zeros */
+
+ for (i = 0; i < (nbytes - j); ++i)
+ {
+ str[i] = str[i + j];
+ }
+
+ /* Zero-terminate string */
+
+ str[i] = 0;
+}
+
+void bignum_dec(FAR struct bn *n)
+{
+ DTYPE tmp; /* copy of n */
+ DTYPE res;
+ int i;
+
+ require(n, "n is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ tmp = n->array[i];
+ res = tmp - 1;
+ n->array[i] = res;
+
+ if (!(res > tmp))
+ {
+ break;
+ }
+ }
+}
+
+void bignum_inc(FAR struct bn *n)
+{
+ DTYPE res;
+ DTYPE_TMP tmp; /* copy of n */
+ int i;
+
+ require(n, "n is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ tmp = n->array[i];
+ res = tmp + 1;
+ n->array[i] = res;
+
+ if (res > tmp)
+ {
+ break;
+ }
+ }
+}
+
+void bignum_add(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ DTYPE_TMP tmp;
+ int carry = 0;
+ int i;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ tmp = (DTYPE_TMP)a->array[i] + b->array[i] + carry;
+ carry = (tmp > MAX_VAL);
+ c->array[i] = (tmp & MAX_VAL);
+ }
+}
+
+void bignum_sub(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ DTYPE_TMP res;
+ DTYPE_TMP tmp1;
+ DTYPE_TMP tmp2;
+ int borrow = 0;
+ int i;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ tmp1 = (DTYPE_TMP)a->array[i] + (MAX_VAL + 1); /* + number_base */
+ tmp2 = (DTYPE_TMP)b->array[i] + borrow;
+ res = (tmp1 - tmp2);
+
+ /* "modulo number_base" == "% (number_base - 1)"
+ * if number_base is 2^N
+ */
+
+ c->array[i] = (DTYPE)(res & MAX_VAL);
+ borrow = (res <= MAX_VAL);
+ }
+}
+
+void bignum_mul(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ struct bn row;
+ struct bn tmp;
+ int i;
+ int j;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ bignum_init(c);
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ bignum_init(&row);
+
+ for (j = 0; j < BN_ARRAY_SIZE; ++j)
+ {
+ if (i + j < BN_ARRAY_SIZE)
+ {
+ bignum_init(&tmp);
+ DTYPE_TMP intermediate =
+ ((DTYPE_TMP)a->array[i] * (DTYPE_TMP)b->array[j]);
+ bignum_from_int(&tmp, intermediate);
+ lshift_word(&tmp, i + j);
+ bignum_add(&tmp, &row, &row);
+ }
+ }
+
+ bignum_add(c, &row, c);
+ }
+}
+
+void bignum_div(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ struct bn current;
+ struct bn denom;
+ struct bn tmp;
+ const DTYPE_TMP half_max = 1 + (DTYPE_TMP)(MAX_VAL / 2);
+ bool overflow = false;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ bignum_from_int(¤t, 1); /* int current = 1; */
+ bignum_assign(&denom, b); /* denom = b */
+ bignum_assign(&tmp, a); /* tmp = a */
+
+ while (bignum_cmp(&denom, a) != LARGER) /* while (denom <= a) { */
+ {
+ if (denom.array[BN_ARRAY_SIZE - 1] >= half_max)
+ {
+ overflow = true;
+ break;
+ }
+
+ lshift_one_bit(¤t); /* current <<= 1; */
+ lshift_one_bit(&denom); /* denom <<= 1; */
+ }
+
+ if (!overflow)
+ {
+ rshift_one_bit(&denom); /* denom >>= 1; */
+ rshift_one_bit(¤t); /* current >>= 1; */
+ }
+
+ bignum_init(c); /* int answer = 0; */
+
+ while (!bignum_is_zero(¤t)) /* while (current != 0) */
+ {
+ if (bignum_cmp(&tmp, &denom) != SMALLER) /* if (dividend >= denom) */
+ {
+ bignum_sub(&tmp, &denom, &tmp); /* dividend -= denom; */
+ bignum_or(c, ¤t, c); /* answer |= current; */
+ }
+
+ rshift_one_bit(¤t); /* current >>= 1; */
+ rshift_one_bit(&denom); /* denom >>= 1; */
+ }
+
+ /* return answer; */
+}
+
+void bignum_lshift(FAR struct bn *a, FAR struct bn *b, int nbits)
+{
+ const int nbits_pr_word = (WORD_SIZE * 8);
+ int nwords = nbits / nbits_pr_word;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(nbits >= 0, "no negative shifts");
+
+ bignum_assign(b, a);
+
+ /* Handle shift in multiples of word-size */
+
+ if (nwords != 0)
+ {
+ lshift_word(b, nwords);
+ nbits -= (nwords * nbits_pr_word);
+ }
+
+ if (nbits != 0)
+ {
+ int i;
+ for (i = (BN_ARRAY_SIZE - 1); i > 0; --i)
+ {
+ b->array[i] = (b->array[i] << nbits) |
+ (b->array[i - 1] >> ((8 * WORD_SIZE) - nbits));
+ }
+
+ b->array[i] <<= nbits;
+ }
+}
+
+void bignum_rshift(FAR struct bn *a, FAR struct bn *b, int nbits)
+{
+ const int nbits_pr_word = (WORD_SIZE * 8);
+ int nwords = nbits / nbits_pr_word;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(nbits >= 0, "no negative shifts");
+
+ bignum_assign(b, a);
+
+ /* Handle shift in multiples of word-size */
+
+ if (nwords != 0)
+ {
+ rshift_word(b, nwords);
+ nbits -= (nwords * nbits_pr_word);
+ }
+
+ if (nbits != 0)
+ {
+ int i;
+ for (i = 0; i < (BN_ARRAY_SIZE - 1); ++i)
+ {
+ b->array[i] = (b->array[i] >> nbits) |
+ (b->array[i + 1] << ((8 * WORD_SIZE) - nbits));
+ }
+
+ b->array[i] >>= nbits;
+ }
+}
+
+void bignum_mod(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ /* Take divmod and throw away div part */
+
+ struct bn tmp;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ bignum_divmod(a, b, &tmp, c);
+}
+
+void bignum_divmod(FAR struct bn *a, FAR struct bn *b,
+ FAR struct bn *c, FAR struct bn *d)
+{
+ /* Puts a%b in d
+ * and a/b in c
+ *
+ * mod(a,b) = a - ((a / b) * b)
+ *
+ * example:
+ * mod(8, 3) = 8 - ((8 / 3) * 3) = 2
+ */
+
+ struct bn tmp;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ /* c = (a / b) */
+
+ bignum_div(a, b, c);
+
+ /* tmp = (c * b) */
+
+ bignum_mul(c, b, &tmp);
+
+ /* c = a - tmp */
+
+ bignum_sub(a, &tmp, d);
+}
+
+void bignum_and(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ int i;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ c->array[i] = (a->array[i] & b->array[i]);
+ }
+}
+
+void bignum_or(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ int i;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ c->array[i] = (a->array[i] | b->array[i]);
+ }
+}
+
+void bignum_xor(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ int i;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ c->array[i] = (a->array[i] ^ b->array[i]);
+ }
+}
+
+int bignum_cmp(FAR struct bn *a, FAR struct bn *b)
+{
+ int i = BN_ARRAY_SIZE;
+
+ require(a, "a is null");
+ require(b, "b is null");
+
+ do
+ {
+ i -= 1; /* Decrement first, to start with last array element */
+ if (a->array[i] > b->array[i])
+ {
+ return LARGER;
+ }
+ else if (a->array[i] < b->array[i])
+ {
+ return SMALLER;
+ }
+ }
+ while (i != 0);
+
+ return EQUAL;
+}
+
+int bignum_is_zero(FAR struct bn *n)
+{
+ int i;
+
+ require(n, "n is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ if (n->array[i])
+ {
+ return 0;
+ }
+ }
+
+ return 1;
+}
+
+void bignum_pow(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c)
+{
+ struct bn tmp;
+
+ require(a, "a is null");
+ require(b, "b is null");
+ require(c, "c is null");
+
+ bignum_init(c);
+
+ if (bignum_cmp(b, c) == EQUAL)
+ {
+ /* Return 1 when exponent is 0 -- n^0 = 1 */
+
+ bignum_inc(c);
+ }
+ else
+ {
+ struct bn bcopy;
+ bignum_assign(&bcopy, b);
+
+ /* Copy a -> tmp */
+
+ bignum_assign(&tmp, a);
+
+ bignum_dec(&bcopy);
+
+ /* Begin summing products: */
+
+ while (!bignum_is_zero(&bcopy))
+ {
+ /* c = tmp * tmp */
+
+ bignum_mul(&tmp, a, c);
+
+ /* Decrement b by one */
+
+ bignum_dec(&bcopy);
+
+ bignum_assign(&tmp, c);
+ }
+
+ /* c = tmp */
+
+ bignum_assign(c, &tmp);
+ }
+}
+
+void bignum_isqrt(FAR struct bn *a, FAR struct bn *b)
+{
+ struct bn low;
+ struct bn high;
+ struct bn mid;
+ struct bn tmp;
+
+ require(a, "a is null");
+ require(b, "b is null");
+
+ bignum_init(&low);
+ bignum_assign(&high, a);
+ bignum_rshift(&high, &mid, 1);
+ bignum_inc(&mid);
+
+ while (bignum_cmp(&high, &low) > 0)
+ {
+ bignum_mul(&mid, &mid, &tmp);
+ if (bignum_cmp(&tmp, a) > 0)
+ {
+ bignum_assign(&high, &mid);
+ bignum_dec(&high);
+ }
+ else
+ {
+ bignum_assign(&low, &mid);
+ }
+
+ bignum_sub(&high, &low, &mid);
+ rshift_one_bit(&mid);
+ bignum_add(&low, &mid, &mid);
+ bignum_inc(&mid);
+ }
+
+ bignum_assign(b, &low);
+}
+
+void bignum_assign(FAR struct bn *dst, FAR struct bn *src)
+{
+ int i;
+
+ require(dst, "dst is null");
+ require(src, "src is null");
+
+ for (i = 0; i < BN_ARRAY_SIZE; ++i)
+ {
+ dst->array[i] = src->array[i];
+ }
+}
diff --git a/include/crypto/bn.h b/include/crypto/bn.h
new file mode 100644
index 0000000000..722c318efe
--- /dev/null
+++ b/include/crypto/bn.h
@@ -0,0 +1,207 @@
+/****************************************************************************
+ * include/crypto/bn.h
+ * This is free and unencumbered software released into the public domain.
+ * Anyone is free to copy, modify, publish, use, compile, sell, or
+ * distribute this software, either in source code form or as a compiled
+ * binary, for any purpose, commercial or non-commercial, and by any
+ * means.
+ * In jurisdictions that recognize copyright laws, the author or authors
+ * of this software dedicate any and all copyright interest in the
+ * software to the public domain. We make this dedication for the benefit
+ * of the public at large and to the detriment of our heirs and
+ * successors. We intend this dedication to be an overt act of
+ * relinquishment in perpetuity of all present and future rights to this
+ * software under copyright law.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ * For more information, please refer to <https://unlicense.org>
+ ****************************************************************************/
+
+#ifndef __INCLUDE_CRYPTO_BIGNUM_H
+#define __INCLUDE_CRYPTO_BIGNUM_H
+
+/* Big number library - arithmetic on multiple-precision unsigned integers.
+ *
+ * This library is an implementation of arithmetic on arbitrarily large
+ * integers.
+ *
+ * The difference between this and other implementations, is that the data
+ * structure
+ * has optimal memory utilization (i.e. a 1024 bit integer takes up 128 bytes
+ * RAM),
+ * and all memory is allocated statically: no dynamic allocation for better
+ * or worse.
+ *
+ * Primary goals are correctness, clarity of code and clean, portable
+ * implementation.
+ * Secondary goal is a memory footprint small enough to make it suitable for
+ * use in
+ * embedded applications.
+ *
+ *
+ * The current state is correct functionality and adequate performance.
+ * There may well be room for performance-optimizations and improvements.
+ */
+
+/****************************************************************************
+ * Included Files
+ ****************************************************************************/
+
+#include <stdint.h>
+
+/****************************************************************************
+ * Pre-processor Definitions
+ ****************************************************************************/
+
+/* This macro defines the word size in bytes of the array that constitues the
+ * big-number data structure.
+ */
+
+#define WORD_SIZE 1
+
+/* Size of big-numbers in bytes */
+
+#define BN_ARRAY_SIZE (256 / WORD_SIZE)
+
+/* Data type of array in structure */
+
+#define DTYPE uint8_t
+
+/* Data-type larger than DTYPE, for holding intermediate results of
+ * calculations
+ */
+
+#define DTYPE_TMP uint32_t
+
+/* bitmask for getting MSB */
+
+#define DTYPE_MSB ((DTYPE_TMP)(0x80))
+
+/* sprintf format string */
+
+#define SPRINTF_FORMAT_STR "%.02x"
+#define SSCANF_FORMAT_STR "%2hhx"
+
+/* Max value of integer type */
+
+#define MAX_VAL ((DTYPE_TMP)0xFF)
+
+/****************************************************************************
+ * Public Types
+ ****************************************************************************/
+
+/* Data-holding structure: array of DTYPEs */
+
+struct bn
+{
+ DTYPE array[BN_ARRAY_SIZE];
+};
+
+/* Tokens returned by bignum_cmp() for value comparison */
+
+enum
+{
+ SMALLER = -1,
+ EQUAL = 0,
+ LARGER = 1
+};
+
+/****************************************************************************
+ * Public Functions Prototype
+ ****************************************************************************/
+
+/* Initialization functions: */
+
+void bignum_init(FAR struct bn *n);
+void bignum_from_int(FAR struct bn *n, DTYPE_TMP i);
+int bignum_to_int(FAR struct bn *n);
+void bignum_from_string(FAR struct bn *n, FAR char *str, int nbytes);
+void bignum_to_string(FAR struct bn *n, FAR char *str, int maxsize);
+
+/* Basic arithmetic operations: */
+
+/* c = a + b */
+
+void bignum_add(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* c = a - b */
+
+void bignum_sub(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* c = a * b */
+
+void bignum_mul(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* c = a / b */
+
+void bignum_div(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* c = a % b */
+
+void bignum_mod(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* c = a / b, d = a % b */
+
+void bignum_divmod(FAR struct bn *a, FAR struct bn *b,
+ FAR struct bn *c, FAR struct bn *d);
+
+/* Bitwise operations: */
+
+/* c = a & b */
+
+void bignum_and(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* c = a | b */
+
+void bignum_or(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* c = a ^ b */
+
+void bignum_xor(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* b = a << nbits */
+
+void bignum_lshift(FAR struct bn *a, FAR struct bn *b, int nbits);
+
+/* b = a >> nbits */
+
+void bignum_rshift(FAR struct bn *a, FAR struct bn *b, int nbits);
+
+/* Special operators and comparison */
+
+/* Compare: returns LARGER, EQUAL or SMALLER */
+
+int bignum_cmp(FAR struct bn *a, FAR struct bn *b);
+
+/* For comparison with zero */
+
+int bignum_is_zero(FAR struct bn *n);
+
+/* Increment: add one to n */
+
+void bignum_inc(FAR struct bn *n);
+
+/* Decrement: subtract one from n */
+
+void bignum_dec(FAR struct bn *n);
+
+/* Calculate a^b -- e.g. 2^10 => 1024 */
+
+void bignum_pow(FAR struct bn *a, FAR struct bn *b, FAR struct bn *c);
+
+/* Integer square root -- e.g. isqrt(5) => 2 */
+
+void bignum_isqrt(FAR struct bn *a, FAR struct bn *b);
+
+/* Copy src into dst -- dst := src */
+
+void bignum_assign(FAR struct bn *dst, FAR struct bn *src);
+
+#endif /* __INCLUDE_CRYPTO_BIGNUM_H */