rsa-mod-exp

compiler.h

/*
 * Keep all the ugly #ifdef for system stuff here
 */

#ifndef __COMPILER_H__
#define __COMPILER_H__

#include <stddef.h>

#ifdef USE_HOSTCC

#if defined(__BEOS__)	 || \
    defined(__NetBSD__)  || \
    defined(__FreeBSD__) || \
    defined(__sun__)	 || \
    defined(__APPLE__)
# include <inttypes.h>
#elif defined(__linux__) || defined(__WIN32__) || defined(__MINGW32__) || defined(__OpenBSD__)
# include <stdint.h>
#endif

#include <errno.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#if !defined(__WIN32__) && !defined(__MINGW32__)
# include <sys/mman.h>
#endif

/* Not all systems (like Windows) has this define, and yes
 * we do replace/emulate mmap() on those systems ...
 */
#ifndef MAP_FAILED
# define MAP_FAILED ((void *)-1)
#endif

#include <fcntl.h>
#ifndef O_BINARY		/* should be define'd on __WIN32__ */
#define O_BINARY	0
#endif

#ifdef __linux__
# include <endian.h>
# include <byteswap.h>
#elif defined(__MACH__) || defined(__FreeBSD__)
# include <machine/endian.h>
#endif
#ifdef __FreeBSD__
# include <sys/endian.h> /* htole32 and friends */
# define __BYTE_ORDER BYTE_ORDER
# define __LITTLE_ENDIAN LITTLE_ENDIAN
# define __BIG_ENDIAN BIG_ENDIAN
#elif defined(__OpenBSD__)
# include <endian.h>
# define __BYTE_ORDER BYTE_ORDER
# define __LITTLE_ENDIAN LITTLE_ENDIAN
# define __BIG_ENDIAN BIG_ENDIAN
#endif

#include <time.h>

typedef uint8_t __u8;
typedef uint16_t __u16;
typedef uint32_t __u32;
typedef unsigned int uint;
typedef unsigned long ulong;

#define uswap_16(x) \
	((((x) & 0xff00) >> 8) | \
	 (((x) & 0x00ff) << 8))
#define uswap_32(x) \
	((((x) & 0xff000000) >> 24) | \
	 (((x) & 0x00ff0000) >>  8) | \
	 (((x) & 0x0000ff00) <<  8) | \
	 (((x) & 0x000000ff) << 24))
#define _uswap_64(x, sfx) \
	((((x) & 0xff00000000000000##sfx) >> 56) | \
	 (((x) & 0x00ff000000000000##sfx) >> 40) | \
	 (((x) & 0x0000ff0000000000##sfx) >> 24) | \
	 (((x) & 0x000000ff00000000##sfx) >>  8) | \
	 (((x) & 0x00000000ff000000##sfx) <<  8) | \
	 (((x) & 0x0000000000ff0000##sfx) << 24) | \
	 (((x) & 0x000000000000ff00##sfx) << 40) | \
	 (((x) & 0x00000000000000ff##sfx) << 56))
#if defined(__GNUC__)
# define uswap_64(x) _uswap_64(x, ull)
#else
# define uswap_64(x) _uswap_64(x, )
#endif

#if __BYTE_ORDER == __LITTLE_ENDIAN
# define cpu_to_le16(x)		(x)
# define cpu_to_le32(x)		(x)
# define cpu_to_le64(x)		(x)
# define le16_to_cpu(x)		(x)
# define le32_to_cpu(x)		(x)
# define le64_to_cpu(x)		(x)
# define cpu_to_be16(x)		uswap_16(x)
# define cpu_to_be32(x)		uswap_32(x)
# define cpu_to_be64(x)		uswap_64(x)
# define be16_to_cpu(x)		uswap_16(x)
# define be32_to_cpu(x)		uswap_32(x)
# define be64_to_cpu(x)		uswap_64(x)
#else
# define cpu_to_le16(x)		uswap_16(x)
# define cpu_to_le32(x)		uswap_32(x)
# define cpu_to_le64(x)		uswap_64(x)
# define le16_to_cpu(x)		uswap_16(x)
# define le32_to_cpu(x)		uswap_32(x)
# define le64_to_cpu(x)		uswap_64(x)
# define cpu_to_be16(x)		(x)
# define cpu_to_be32(x)		(x)
# define cpu_to_be64(x)		(x)
# define be16_to_cpu(x)		(x)
# define be32_to_cpu(x)		(x)
# define be64_to_cpu(x)		(x)
#endif

#else /* !USE_HOSTCC */

/* Type for `void *' pointers. */
typedef unsigned long int uintptr_t;

#include <linux/string.h>
#include <linux/types.h>
#include <asm/byteorder.h>

#if __SIZEOF_LONG__ == 8
# define __WORDSIZE	64
#elif __SIZEOF_LONG__ == 4
# define __WORDSIZE	32
#else
/*
 * Assume 32-bit for now - only newer toolchains support this feature and
 * this is only required for sandbox support at present.
 */
#define __WORDSIZE	32
#endif

#endif /* USE_HOSTCC */

#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

#ifdef __LP64__
#define MEM_SUPPORT_64BIT_DATA
#endif

#endif

dump_rsa.c

/* Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
/*
 * C port of DumpPublicKey.java from the Android Open source project with
 * support for additional RSA key sizes. (platform/system/core,git/libmincrypt
 * /tools/DumpPublicKey.java). Uses the OpenSSL X509 and BIGNUM library.
 */
#include <openssl/pem.h>
#include <openssl/rsa.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
/*
 * Command line tool to extract RSA public keys from X.509 certificates and
 * output a pre-processed version of keys for use by RSA verification routines.
 */
int check(RSA *key)
{
	int public_exponent = BN_get_word(RSA_get0_e(key));
	int modulus = BN_num_bits(RSA_get0_n(key));
	if (public_exponent != 65537 && public_exponent != 3) {
		fprintf(stderr, "WARNING: Non-standard public exponent %d.\n",
			public_exponent);
	}
	if (modulus != 1024 && modulus != 2048 && modulus != 3072 &&
	    modulus != 4096 && modulus != 8192) {
		fprintf(stderr, "WARNING: Non-standard modulus length = %d.\n",
			modulus);
	}
	return 1;
}
/**
 * Pre-processes and outputs RSA public key to standard output.
 */
void output(RSA *key)
{
	BIGNUM *N;
	BIGNUM *Big1 = NULL, *Big2 = NULL, *Big32 = NULL, *BigMinus1 = NULL;
	BIGNUM *B = NULL;
	BIGNUM *N0inv= NULL, *R = NULL, *RR = NULL, *RRTemp = NULL;
	BIGNUM *NnumBits = NULL;
	BIGNUM *n = NULL, *rr = NULL;
	BN_CTX *bn_ctx = BN_CTX_new();
	uint32_t n0invout;
	int nwords, i;
	N = BN_dup(RSA_get0_n(key));
	/* Output size of RSA key in 32-bit words */
	nwords = BN_num_bits(N) / 32;
	if (-1 == write(1, &nwords, sizeof(nwords)))
		goto failure;
	/* Initialize BIGNUMs */
	Big1 = BN_new();
	Big2 = BN_new();
	Big32 = BN_new();
	BigMinus1 = BN_new();
	N0inv= BN_new();
	R = BN_new();
	RR = BN_new();
	RRTemp = BN_new();
	NnumBits = BN_new();
	n = BN_new();
	rr = BN_new();
	BN_set_word(Big1, 1L);
	BN_set_word(Big2, 2L);
	BN_set_word(Big32, 32L);
	BN_sub(BigMinus1, Big1, Big2);
	B = BN_new();
	BN_exp(B, Big2, Big32, bn_ctx); /* B = 2^32 */
	/* Calculate and output N0inv = -1 / N[0] mod 2^32 */
	BN_mod_inverse(N0inv, N, B, bn_ctx);
	BN_sub(N0inv, B, N0inv);
	n0invout = BN_get_word(N0inv);
	if (-1 == write(1, &n0invout, sizeof(n0invout)))
		goto failure;
	/* Calculate R = 2^(# of key bits) */
	BN_set_word(NnumBits, BN_num_bits(N));
	BN_exp(R, Big2, NnumBits, bn_ctx);
	/* Calculate RR = R^2 mod N */
	BN_copy(RR, R);
	BN_mul(RRTemp, RR, R, bn_ctx);
	BN_mod(RR, RRTemp, N, bn_ctx);
	/* Write out modulus as little endian array of integers. */
	for (i = 0; i < nwords; ++i) {
		uint32_t nout;
		BN_mod(n, N, B, bn_ctx); /* n = N mod B */
		nout = BN_get_word(n);
		if (-1 == write(1, &nout, sizeof(nout)))
			goto failure;
		BN_rshift(N, N, 32); /*  N = N/B */
	}
	/* Write R^2 as little endian array of integers. */
	for (i = 0; i < nwords; ++i) {
		uint32_t rrout;
		BN_mod(rr, RR, B, bn_ctx); /* rr = RR mod B */
		rrout = BN_get_word(rr);
#if 0
		if (-1 == write(1, &rrout, sizeof(rrout)))
			goto failure;
#else
        printf("%u,", rrout);
#endif
		BN_rshift(RR, RR, 32); /* RR = RR/B */
	}
 failure:
	/* Free BIGNUMs. */
	BN_free(Big1);
	BN_free(Big2);
	BN_free(Big32);
	BN_free(BigMinus1);
	BN_free(N0inv);
	BN_free(R);
	BN_free(RRTemp);
	BN_free(NnumBits);
	BN_free(n);
	BN_free(rr);
}
int main(int argc, char* argv[]) {
	int cert_mode = 0;
	FILE* fp;
	X509* cert = NULL;
	RSA* pubkey = NULL;
	EVP_PKEY* key;
	char *progname;
	if (argc != 3 ||
	    (strcmp(argv[1], "-cert") && strcmp(argv[1], "-pub"))) {
		progname = strrchr(argv[0], '/');
		if (progname)
			progname++;
		else
			progname = argv[0];
		fprintf(stderr, "Usage: %s <-cert | -pub> <file>\n", progname);
		return -1;
	}
	if (!strcmp(argv[1], "-cert"))
		cert_mode = 1;
	fp = fopen(argv[2], "r");
	if (!fp) {
		fprintf(stderr, "Couldn't open file %s!\n", argv[2]);
		return -1;
	}
	if (cert_mode) {
		/* Read the certificate */
		if (!PEM_read_X509(fp, &cert, NULL, NULL)) {
			fprintf(stderr, "Couldn't read certificate.\n");
			goto fail;
		}
		/* Get the public key from the certificate. */
		key = X509_get_pubkey(cert);
		/* Convert to a RSA_style key. */
		if (!(pubkey = EVP_PKEY_get1_RSA(key))) {
			fprintf(stderr, "Couldn't convert to RSA style key.\n");
			goto fail;
		}
	} else {
		/* Read the pubkey in .PEM format. */
		if (!(pubkey = PEM_read_RSA_PUBKEY(fp, NULL, NULL, NULL))) {
			fprintf(stderr, "Couldn't read public key file.\n");
			goto fail;
		}
	}
	if (check(pubkey)) {
		output(pubkey);
	}
 fail:
	X509_free(cert);
	RSA_free(pubkey);
	fclose(fp);
	return 0;
}

main.c

#include "rsa-mod-exp.h"
#include <string.h>
#include <stdio.h>

const unsigned char sign[] = {
  0x45, 0x79, 0x47, 0x29, 0x44, 0x19, 0x99, 0x08,
  0x01, 0xec, 0x46, 0xad, 0x04, 0x0f, 0x2a, 0x9a,
  0x41, 0xa6, 0x16, 0x3f, 0xdc, 0xb4, 0x72, 0x85,
  0x69, 0x09, 0x47, 0x06, 0xc8, 0x10, 0x1e, 0xa1,
  0xe6, 0x75, 0x11, 0x8c, 0x36, 0x53, 0xbe, 0x46,
  0xf6, 0x40, 0xb3, 0xa0, 0xd7, 0xaa, 0xea, 0xaf,
  0x21, 0x62, 0x98, 0x6f, 0xfc, 0x3e, 0x1b, 0x5a,
  0x1d, 0x14, 0x6c, 0x22, 0x6e, 0x31, 0x00, 0x6c,
  0x08, 0x6a, 0x6a, 0x8d, 0x8e, 0xe3, 0x60, 0x29,
  0x63, 0x62, 0x32, 0x53, 0xc0, 0x8f, 0x96, 0xbe,
  0x36, 0xef, 0x25, 0x5f, 0xa2, 0x2a, 0x64, 0x33,
  0x34, 0xf4, 0x39, 0xde, 0x85, 0xac, 0x6f, 0xc7,
  0xe1, 0x44, 0x12, 0x19, 0xf4, 0x69, 0x08, 0xef,
  0x92, 0x4b, 0x58, 0xd2, 0xef, 0xb7, 0xf8, 0x47,
  0xf3, 0x52, 0x29, 0xf8, 0x9f, 0xc4, 0x89, 0x2a,
  0xc7, 0x11, 0xf4, 0x6d, 0xc4, 0x9a, 0x47, 0x27,
  0x2d, 0x02, 0x07, 0xa2, 0x7b, 0x90, 0x65, 0x3f,
  0x39, 0x20, 0x53, 0x2d, 0xff, 0x21, 0x3e, 0x74,
  0xfc, 0xe3, 0x6b, 0x14, 0xe7, 0x75, 0x53, 0x81,
  0xee, 0x79, 0xa3, 0x9a, 0xce, 0x3b, 0x4a, 0x5b,
  0xa6, 0x7a, 0x85, 0x1b, 0x89, 0x55, 0x83, 0x27,
  0xa4, 0x38, 0xca, 0x6f, 0x0b, 0x78, 0x16, 0x91,
  0x83, 0xe5, 0xe2, 0xb2, 0x1a, 0xd4, 0x9a, 0x81,
  0xe2, 0x32, 0xfc, 0x0e, 0xd0, 0xb3, 0xdd, 0x0f,
  0x5a, 0xf2, 0x3b, 0x07, 0x81, 0x3d, 0x7b, 0xde,
  0xe2, 0xc5, 0xff, 0xd1, 0xb9, 0xc9, 0x61, 0x13,
  0x1f, 0x26, 0x40, 0x37, 0x15, 0x4e, 0x56, 0xd5,
  0x12, 0xb5, 0x9a, 0xa2, 0x92, 0x70, 0x4e, 0xa6,
  0xbe, 0xd2, 0xe7, 0xc3, 0xd1, 0x4c, 0x40, 0x04,
  0x63, 0x0a, 0x23, 0x24, 0x54, 0x7e, 0x6c, 0x8a,
  0xe3, 0xf9, 0xd5, 0x7e, 0x37, 0x90, 0xd1, 0x44,
  0x7d, 0xcc, 0x21, 0x42, 0xc0, 0x43, 0x09, 0x63
};

const uint32_t N[] = { // modulus
    2269471451,2187526552,1754767354,2012232415,
    1443097090,585933314,1129635640,691306695,
    513814822,745501012,2622999283,3125741932,
    4023385752,12233706,1742168165,1913538019,
    808243439,3731732418,3337993786,2229120960,
    3569515041,3579220261,1654153106,119136473,
    4145445079,2623964957,3948316393,630635838,
    3611652049,3725879144,1593914391,3723712600,
    353419321,2773766488,4149762822,2865348182,
    1693260090,2081011569,4187128210,1138655390,
    1394984240,557568908,3946737309,380288486,
    1643259808,3254678826,191669029,2243074013,
    1125643126,2831901602,1107780072,1086140772,
    1868985292,2543982193,3839413065,3792128237,
    77438962,4232864170,4114710706,692633608,
    43469685,1513662601,1423023360,2614066905
  };

const uint32_t rr[] = { // r^2
0x07d88b5c,0xd68857ee,0xe2cf532c,0x455c49f0,
0x9e3ef032,0xc937eb30,0xaf04967b,0x950ff08d,
0x186ffd03,0x145d22ea,0x39cf822f,0xb98b8f64,
0x9bdcdf0f,0xbeee1d84,0x31b2748f,0x671bd3eb,
0x9dfd445e,0xe31f4f0a,0x2df65b68,0x6bd87b87,
0x6f2d5aa4,0xc9a255f0,0x57c46349,0xacf6f8a3,
0x4158540f,0xf966fe47,0xa9f471c3,0x0889b3f7,
0x606aa2b6,0xab9acfdf,0xb9b0ba30,0x5dfb08e6,
0x0fe4e203,0xacb6a8a7,0x6cc9f1be,0x04c197b0,
0x50bcab67,0x3f540d92,0x859d3ba9,0x449a6a27,
0xbaa09a2a,0xa9a3b831,0x00a9c19b,0xd93dbb40,
0x3c7488e7,0x0de321bf,0x1e613e5c,0x01f083de,
0xd1969bbc,0x5ffe194b,0xfc25ee47,0x80a6a88b,
0xad7fea1f,0x5f0670a3,0xcec15153,0xb6ca4f68,
0xb58e9f20,0xb387b338,0x7e075657,0xdcf19c44,
0x9791fa94,0xa2407bc9,0x129b10e7,0x35024e2e,
  };

void dump(const unsigned char *s, int size, int newline)
{
  for (int i = 0; i < size; i ++) {
    printf("%02x", s[i]);
    if (newline) {
      if (((i + 1) % 16) == 0) {
        printf("\n");
      }
    }
  }
}

int main() {
    struct key_prop prop;
    prop.rr = rr;
    prop.modulus = N;
    prop.public_exponent = NULL;
    prop.n0inv = 0xb06636ad;
    prop.num_bits = 2048;
    printf("sign size %ld\n", sizeof(sign)*8);
    unsigned char out[sizeof(sign)];
    memset(out, 0, sizeof(out));
    rsa_mod_exp_sw(sign, sizeof(sign), &prop, out);
    dump(out, sizeof(out), 1);
}

Makefile

SRC	= rsa-mod-exp.c main.c
OBJ = $(SRC:%.c=%.o)
TARGET = rsa
CFLAGS += -DUSE_HOSTCC

$(TARGET): $(OBJ)
	$(CC) -o $@ $^

%.o:%.c
	$(CC) $(CFLAGS) -o $@ -c $<

clean:
	rm -rf $(OBJ) $(TARGET)

openssl_rsa.c

#include <openssl/rsa.h>
#include <openssl/bn.h>

const unsigned char sign[] = {
  0x45, 0x79, 0x47, 0x29, 0x44, 0x19, 0x99, 0x08,
  0x01, 0xec, 0x46, 0xad, 0x04, 0x0f, 0x2a, 0x9a,
  0x41, 0xa6, 0x16, 0x3f, 0xdc, 0xb4, 0x72, 0x85,
  0x69, 0x09, 0x47, 0x06, 0xc8, 0x10, 0x1e, 0xa1,
  0xe6, 0x75, 0x11, 0x8c, 0x36, 0x53, 0xbe, 0x46,
  0xf6, 0x40, 0xb3, 0xa0, 0xd7, 0xaa, 0xea, 0xaf,
  0x21, 0x62, 0x98, 0x6f, 0xfc, 0x3e, 0x1b, 0x5a,
  0x1d, 0x14, 0x6c, 0x22, 0x6e, 0x31, 0x00, 0x6c,
  0x08, 0x6a, 0x6a, 0x8d, 0x8e, 0xe3, 0x60, 0x29,
  0x63, 0x62, 0x32, 0x53, 0xc0, 0x8f, 0x96, 0xbe,
  0x36, 0xef, 0x25, 0x5f, 0xa2, 0x2a, 0x64, 0x33,
  0x34, 0xf4, 0x39, 0xde, 0x85, 0xac, 0x6f, 0xc7,
  0xe1, 0x44, 0x12, 0x19, 0xf4, 0x69, 0x08, 0xef,
  0x92, 0x4b, 0x58, 0xd2, 0xef, 0xb7, 0xf8, 0x47,
  0xf3, 0x52, 0x29, 0xf8, 0x9f, 0xc4, 0x89, 0x2a,
  0xc7, 0x11, 0xf4, 0x6d, 0xc4, 0x9a, 0x47, 0x27,
  0x2d, 0x02, 0x07, 0xa2, 0x7b, 0x90, 0x65, 0x3f,
  0x39, 0x20, 0x53, 0x2d, 0xff, 0x21, 0x3e, 0x74,
  0xfc, 0xe3, 0x6b, 0x14, 0xe7, 0x75, 0x53, 0x81,
  0xee, 0x79, 0xa3, 0x9a, 0xce, 0x3b, 0x4a, 0x5b,
  0xa6, 0x7a, 0x85, 0x1b, 0x89, 0x55, 0x83, 0x27,
  0xa4, 0x38, 0xca, 0x6f, 0x0b, 0x78, 0x16, 0x91,
  0x83, 0xe5, 0xe2, 0xb2, 0x1a, 0xd4, 0x9a, 0x81,
  0xe2, 0x32, 0xfc, 0x0e, 0xd0, 0xb3, 0xdd, 0x0f,
  0x5a, 0xf2, 0x3b, 0x07, 0x81, 0x3d, 0x7b, 0xde,
  0xe2, 0xc5, 0xff, 0xd1, 0xb9, 0xc9, 0x61, 0x13,
  0x1f, 0x26, 0x40, 0x37, 0x15, 0x4e, 0x56, 0xd5,
  0x12, 0xb5, 0x9a, 0xa2, 0x92, 0x70, 0x4e, 0xa6,
  0xbe, 0xd2, 0xe7, 0xc3, 0xd1, 0x4c, 0x40, 0x04,
  0x63, 0x0a, 0x23, 0x24, 0x54, 0x7e, 0x6c, 0x8a,
  0xe3, 0xf9, 0xd5, 0x7e, 0x37, 0x90, 0xd1, 0x44,
  0x7d, 0xcc, 0x21, 0x42, 0xc0, 0x43, 0x09, 0x63
};


const unsigned char N[] = {
    0x00,0x9b,0xcf,0x7e,0xd9,0x54,0xd1,0x9d,0x00,0x5a,0x38,0xa8,0x89,0x02,0x97,
    0x4b,0x75,0x29,0x48,0xc0,0x08,0xf5,0x41,0x80,0xb2,0xfc,0x4c,0x61,0xaa,0x04,
    0x9d,0x9f,0xf2,0xe2,0x07,0x48,0xed,0xe4,0xd8,0xcb,0x49,0x97,0xa2,0x16,0x71,
    0x6f,0x66,0x73,0xcc,0x40,0xbd,0x31,0x64,0x42,0x07,0x61,0xe8,0xa8,0xcb,0x63,
    0xa2,0x43,0x17,0xf3,0x76,0x85,0xb2,0x97,0xdd,0x0b,0x6c,0xa3,0x25,0xc1,0xfe,
    0x75,0x2a,0x61,0xf2,0x27,0xa0,0x16,0xaa,0xbd,0xe6,0xeb,0x3e,0x6e,0x9d,0x21,
    0x3b,0xd3,0x8c,0x53,0x25,0xc5,0x30,0x43,0xde,0x80,0x9e,0xf9,0x92,0x81,0x92,
    0x7c,0x09,0xb7,0x71,0x64,0xed,0x19,0x3a,0xaa,0xc9,0xbe,0x56,0xf7,0x58,0x5b,
    0x06,0xa5,0x54,0x51,0x58,0x15,0x10,0xc0,0x39,0xdd,0xf3,0x58,0x58,0x5f,0x01,
    0x34,0x17,0xde,0x14,0x67,0x68,0xd7,0x45,0x6f,0xd1,0x25,0x96,0xbd,0x3e,0xeb,
    0x56,0x86,0xe9,0x9c,0x66,0x87,0x1d,0xf7,0x16,0x78,0xd7,0x07,0x19,0xe0,0xd9,
    0x62,0x98,0x5f,0x92,0xd5,0x56,0x91,0x25,0xd4,0xc2,0x7a,0x21,0x84,0xdd,0xaf,
    0xc0,0xc6,0xf5,0xbe,0x3a,0xde,0x6d,0xb7,0xc2,0x30,0x2c,0xd0,0xef,0x72,0x0e,
    0x45,0xe3,0x67,0xd7,0x60,0x65,0x00,0xba,0xab,0xea,0xef,0xcf,0xfe,0x98,0xba,
    0x4f,0x09,0x6c,0x9c,0x57,0xca,0xf3,0x2c,0x6f,0x71,0x54,0x1e,0xa0,0x31,0x26,
    0x29,0x34,0x80,0xc7,0x43,0x54,0xdf,0x38,0x22,0xec,0xa2,0x02,0x56,0x03,0xea,
    0x02,0x77,0xf0,0x3a,0xdf,0x68,0x97,0x9f,0xfa,0x82,0x63,0x01,0x98,0x87,0x45,
    0x62,0xdb
};


int main() {
    BIGNUM *r = BN_new();
    BIGNUM *a = BN_bin2bn(sign, sizeof(sign), NULL);
    BIGNUM *p = BN_new();
    BN_set_word(p, 65537);
    BIGNUM *m = BN_bin2bn(N, sizeof(N), NULL);;
    BN_CTX *ctx = BN_CTX_new();
    /* r=a^p % m */
    BN_mod_exp(r, a, p, m, ctx);
    printf("%s\n", BN_bn2hex(r));

    BIGNUM *inv = BN_new();
    /* (a*r)%n==1 */
    BIGNUM *b32 = BN_new();
    BN_set_bit(b32, 32);
    BN_mod_inverse(inv, m, b32, ctx);
    BN_sub(inv, b32, inv);
    printf("%s\n", BN_bn2hex(inv));
                        
    BIGNUM *rr = BN_new();
    //BN_mod_exp_mont(rr, a, p, m, ctx, NULL);
    BN_set_bit(rr, 2048);
    BN_mod_sqr(rr, rr, m, ctx);
    printf("%s\n", BN_bn2hex(rr));
}

rsa-mod-exp.c

// SPDX-License-Identifier: GPL-2.0+
/*
 * Copyright (c) 2013, Google Inc.
 */

/*
#ifndef USE_HOSTCC
#include <common.h>
#include <fdtdec.h>
#include <asm/types.h>
#include <asm/byteorder.h>
#include <linux/errno.h>
#include <asm/types.h>
#include <asm/unaligned.h>
#else
#include "fdt_host.h"
#include "mkimage.h"
#include <fdt_support.h>
#endif
*/
#include <stdio.h>
#include <string.h>
#include "rsa.h"
#include "rsa-mod-exp.h"
#include "compiler.h"

#define debug   printf

#define UINT64_MULT32(v, multby)  (((uint64_t)(v)) * ((uint32_t)(multby)))

#define get_unaligned_be32(a) be32_to_cpu(*(uint32_t *)a)
#define put_unaligned_be32(a, b) (*(uint32_t *)(b) = cpu_to_be32(a))

/* Default public exponent for backward compatibility */
#define RSA_DEFAULT_PUBEXP	65537

/**
 * subtract_modulus() - subtract modulus from the given value
 *
 * @key:	Key containing modulus to subtract
 * @num:	Number to subtract modulus from, as little endian word array
 */
static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[])
{
	int64_t acc = 0;
	uint i;

	for (i = 0; i < key->len; i++) {
		acc += (uint64_t)num[i] - key->modulus[i];
		num[i] = (uint32_t)acc;
		acc >>= 32;
	}
}

/**
 * greater_equal_modulus() - check if a value is >= modulus
 *
 * @key:	Key containing modulus to check
 * @num:	Number to check against modulus, as little endian word array
 * @return 0 if num < modulus, 1 if num >= modulus
 */
static int greater_equal_modulus(const struct rsa_public_key *key,
				 uint32_t num[])
{
	int i;

	for (i = (int)key->len - 1; i >= 0; i--) {
		if (num[i] < key->modulus[i])
			return 0;
		if (num[i] > key->modulus[i])
			return 1;
	}

	return 1;  /* equal */
}

/**
 * montgomery_mul_add_step() - Perform montgomery multiply-add step
 *
 * Operation: montgomery result[] += a * b[] / n0inv % modulus
 *
 * @key:	RSA key
 * @result:	Place to put result, as little endian word array
 * @a:		Multiplier
 * @b:		Multiplicand, as little endian word array
 */
static void montgomery_mul_add_step(const struct rsa_public_key *key,
		uint32_t result[], const uint32_t a, const uint32_t b[])
{
	uint64_t acc_a, acc_b;
	uint32_t d0;
	uint i;

	acc_a = (uint64_t)a * b[0] + result[0];
	d0 = (uint32_t)acc_a * key->n0inv;
	acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a;
	for (i = 1; i < key->len; i++) {
		acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i];
		acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] +
				(uint32_t)acc_a;
		result[i - 1] = (uint32_t)acc_b;
	}

	acc_a = (acc_a >> 32) + (acc_b >> 32);

	result[i - 1] = (uint32_t)acc_a;

	if (acc_a >> 32)
		subtract_modulus(key, result);
}

/**
 * montgomery_mul() - Perform montgomery mutitply
 *
 * Operation: montgomery result[] = a[] * b[] / n0inv % modulus
 *
 * @key:	RSA key
 * @result:	Place to put result, as little endian word array
 * @a:		Multiplier, as little endian word array
 * @b:		Multiplicand, as little endian word array
 */
static void montgomery_mul(const struct rsa_public_key *key,
		uint32_t result[], uint32_t a[], const uint32_t b[])
{
	uint i;

	for (i = 0; i < key->len; ++i)
		result[i] = 0;
	for (i = 0; i < key->len; ++i)
		montgomery_mul_add_step(key, result, a[i], b);
}

/**
 * num_pub_exponent_bits() - Number of bits in the public exponent
 *
 * @key:	RSA key
 * @num_bits:	Storage for the number of public exponent bits
 */
static int num_public_exponent_bits(const struct rsa_public_key *key,
		int *num_bits)
{
	uint64_t exponent;
	int exponent_bits;
	const uint max_bits = (sizeof(exponent) * 8);

	exponent = key->exponent;
	exponent_bits = 0;

	if (!exponent) {
		*num_bits = exponent_bits;
		return 0;
	}

	for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits)
		if (!(exponent >>= 1)) {
			*num_bits = exponent_bits;
			return 0;
		}

	return -EINVAL;
}

/**
 * is_public_exponent_bit_set() - Check if a bit in the public exponent is set
 *
 * @key:	RSA key
 * @pos:	The bit position to check
 */
static int is_public_exponent_bit_set(const struct rsa_public_key *key,
		int pos)
{
	return key->exponent & (1ULL << pos);
}

/**
 * pow_mod() - in-place public exponentiation
 *
 * @key:	RSA key
 * @inout:	Big-endian word array containing value and result
 */
static int pow_mod(const struct rsa_public_key *key, uint32_t *inout)
{
	uint32_t *result, *ptr;
	uint i;
	int j, k;

	/* Sanity check for stack size - key->len is in 32-bit words */
	if (key->len > RSA_MAX_KEY_BITS / 32) {
		debug("RSA key words %u exceeds maximum %d\n", key->len,
		      RSA_MAX_KEY_BITS / 32);
		return -EINVAL;
	}

	uint32_t val[key->len], acc[key->len], tmp[key->len];
	uint32_t a_scaled[key->len];
	result = tmp;  /* Re-use location. */

	/* Convert from big endian byte array to little endian word array. */
	for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--)
		val[i] = get_unaligned_be32(ptr);

	if (0 != num_public_exponent_bits(key, &k))
		return -EINVAL;

	if (k < 2) {
		debug("Public exponent is too short (%d bits, minimum 2)\n",
		      k);
		return -EINVAL;
	}

	if (!is_public_exponent_bit_set(key, 0)) {
		debug("LSB of RSA public exponent must be set.\n");
		return -EINVAL;
	}

	/* the bit at e[k-1] is 1 by definition, so start with: C := M */
	montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */
	/* retain scaled version for intermediate use */
	memcpy(a_scaled, acc, key->len * sizeof(a_scaled[0]));

	for (j = k - 2; j > 0; --j) {
		montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */

		if (is_public_exponent_bit_set(key, j)) {
			/* acc = tmp * val / R mod n */
			montgomery_mul(key, acc, tmp, a_scaled);
		} else {
			/* e[j] == 0, copy tmp back to acc for next operation */
			memcpy(acc, tmp, key->len * sizeof(acc[0]));
		}
	}

	/* the bit at e[0] is always 1 */
	montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
	montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */
	memcpy(result, acc, key->len * sizeof(result[0]));

	/* Make sure result < mod; result is at most 1x mod too large. */
	if (greater_equal_modulus(key, result))
		subtract_modulus(key, result);

	/* Convert to bigendian byte array */
	for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++)
		put_unaligned_be32(result[i], ptr);
	return 0;
}

static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len)
{
	int i;

	for (i = 0; i < len; i++)
		dst[i] = be32_to_cpu(src[len - 1 - i]);
}

int rsa_mod_exp_sw(const uint8_t *sig, uint32_t sig_len,
		struct key_prop *prop, uint8_t *out)
{
	struct rsa_public_key key;
	int ret;

	if (!prop) {
		debug("%s: Skipping invalid prop", __func__);
		return -EBADF;
	}
	key.n0inv = prop->n0inv;
	key.len = prop->num_bits;

	if (!prop->public_exponent)
		key.exponent = RSA_DEFAULT_PUBEXP;
	else
		key.exponent =
			be64_to_cpu(*((uint64_t *)(prop->public_exponent)));

	if (!key.len || !prop->modulus || !prop->rr) {
		debug("%s: Missing RSA key info", __func__);
		return -EFAULT;
	}

	/* Sanity check for stack size */
	if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) {
		debug("RSA key bits %u outside allowed range %d..%d\n",
		      key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS);
		return -EFAULT;
	}
	key.len /= sizeof(uint32_t) * 8;
	uint32_t key1[key.len], key2[key.len];

	key.modulus = key1;
	key.rr = key2;
	//rsa_convert_big_endian(key.modulus, (uint32_t *)prop->modulus, key.len);
	memcpy(key.modulus, (uint32_t *)prop->modulus, key.len*sizeof(uint32_t));
	//rsa_convert_big_endian(key.rr, (uint32_t *)prop->rr, key.len);
	memcpy(key.rr, (uint32_t *)prop->rr, key.len*sizeof(uint32_t));
	if (!key.modulus || !key.rr) {
		debug("%s: Out of memory", __func__);
		return -ENOMEM;
	}

	uint32_t buf[sig_len / sizeof(uint32_t)];

	memcpy(buf, sig, sig_len);

	ret = pow_mod(&key, buf);
	if (ret)
		return ret;

	memcpy(out, buf, sig_len);

	return 0;
}

rsa-mod-exp.h

/* SPDX-License-Identifier: GPL-2.0+ */
/*
 * Copyright 2014 Freescale Semiconductor, Inc.
 */

#ifndef _RSA_MOD_EXP_H
#define _RSA_MOD_EXP_H

#include <errno.h>
#include <stdint.h>

/**
 * struct key_prop - holder for a public key properties
 *
 * The struct has pointers to modulus (Typically called N),
 * The inverse, R^2, exponent. These can be typecasted and
 * used as byte arrays or converted to the required format
 * as per requirement of RSA implementation.
 */
struct key_prop {
	const void *rr;		/* R^2 can be treated as byte array */
	const void *modulus;	/* modulus as byte array */
	const void *public_exponent; /* public exponent as byte array */
	uint32_t n0inv;		/* -1 / modulus[0] mod 2^32 */
	int num_bits;		/* Key length in bits */
	uint32_t exp_len;	/* Exponent length in number of uint8_t */
};

/**
 * rsa_mod_exp_sw() - Perform RSA Modular Exponentiation in sw
 *
 * Operation: out[] = sig ^ exponent % modulus
 *
 * @sig:	RSA PKCS1.5 signature
 * @sig_len:	Length of signature in number of bytes
 * @node:	Node with RSA key elements like modulus, exponent, R^2, n0inv
 * @out:	Result in form of byte array of len equal to sig_len
 */
int rsa_mod_exp_sw(const uint8_t *sig, uint32_t sig_len,
		struct key_prop *node, uint8_t *out);

#endif

rsa.h

/* SPDX-License-Identifier: GPL-2.0+ */
/*
 * Copyright (c) 2013, Google Inc.
 *
 * (C) Copyright 2008 Semihalf
 *
 * (C) Copyright 2000-2006
 * Wolfgang Denk, DENX Software Engineering, wd@denx.de.
 */

#ifndef _RSA_H
#define _RSA_H

#include <errno.h>
#include <stdint.h>
#include "compiler.h"

/**
 * struct rsa_public_key - holder for a public key
 *
 * An RSA public key consists of a modulus (typically called N), the inverse
 * and R^2, where R is 2^(# key bits).
 */

struct rsa_public_key {
	uint len;		/* len of modulus[] in number of uint32_t */
	uint32_t n0inv;		/* -1 / modulus[0] mod 2^32 */
	uint32_t *modulus;	/* modulus as little endian array */
	uint32_t *rr;		/* R^2 as little endian array */
	uint64_t exponent;	/* public exponent */
};

#define RSA_DEFAULT_PADDING_NAME		"pkcs-1.5"

#define RSA2048_BYTES	(2048 / 8)
#define RSA4096_BYTES	(4096 / 8)

/* This is the minimum/maximum key size we support, in bits */
#define RSA_MIN_KEY_BITS	2048
#define RSA_MAX_KEY_BITS	4096

/* This is the maximum signature length that we support, in bits */
#define RSA_MAX_SIG_BITS	4096

#endif

sign and verify.bash

openssl genrsa -out rsa.key 2048
openssl rsa -in rsa.key -pubout -out pub.key
echo "hello world" > hello.txt
openssl dgst -sign rsa.key -sha256 -out sign.bin hello.txt
openssl dgst -verify -sha256 pub.key -signature sign.bin hello.txt