嵌入式的RSA非对称加密算法
1、对称加密算法对称加密算法是应用较早的加密算法，数据发送方将明文和密钥经加密算法处理，使其变成密文发送出去；接收方收到密文后，使用和加密算法相同的密钥进行逆算法解密，还原出明文。在对称加密算法中，使用的密钥只有一个，收发双方使用相同的密钥对数据进行加密或解密。
双方都必须保管好密钥，任一方的密钥泄露，都会导致加密信息不安全；尤其是双方协商更换密钥过程中，密钥会出现在传输过程中，严重影响数据的安全性。
对称加密算法常用的aes可以参考[ 嵌入式算法6---aes加密/解密算法 ]
2、非对称加密算法和对称加密算法最大的区别是，非对称加密算法需要两个密钥，公开密钥（public key 简称公钥）和私有密钥（private key 简称私钥），且公钥与私钥是互相关联的一对。使用公钥对数据进行加密，只有用对应的私钥才能解密，私钥加密签名也只有公钥能解密验签。
非对称加密算法实现机密信息交换的基本过程：
1、甲方生成一对密钥并将公钥公开，私钥保密
2、乙方使用甲方的提供的公钥，对机密信息加密后再发送给甲方；甲方使用自己私钥对加密后的信息进行解密
3、甲方也可以使用自己的私钥对机密信息进行签名后再发送给乙方，乙方用甲方的提供公钥对甲方发来的密文进行验签
非对称加密算法的特点：
1、公钥公开，私钥私藏，无需双方传输密钥协商，所以安全性比对称加密算法更高
2、非对称加密的算法复杂，运算速度比对称加密解密的速度慢很多
3、一般情况下使用非对称加密保护对称加密的密钥，密钥协商后使用对称加密进行通信
4、最佳实现是双方各自保存自己的私钥，使用对方的公钥加密数据传输
3、rsa算法与密钥非对称加密算法中最常用的当属 rsa ，其算法本身基于一个简单的数论知识，给出两个素数，很容易将它们相乘，然而给出它们的乘积，想得到这两个素数就显得尤为困难。具体的私钥与公钥生成原理和加密、解密过程，不是本文关注的重点。
私钥和公钥的生成，可以借助mbedtls源码或openssl工具生成，举例如下：
1、安装openssl，下载地址
https://www.openssl.org/
2、安装后进入openssl命令行界面，使用命令生成rsa2048的私钥，存入private.key文件
openssl>genrsa -out private.key 2048
3、基于公钥生成私钥，存入文件public.key
openssl> rsa -in private.key -pubout -out public.key
4、有些算法库采用传入指数、模数方式进行加解密，而前面生成的公私钥是pem格式，需要变成exponent、modulus形式，就可以使用以下工具在线转换。
https://www.oren.net.cn/rsa/info.html
5、关于mbedtls应用，可以参考[ mbedtls 基础及其应用 ]，该开源库针对嵌入式系统，且囊括了很多常用的算法。
4、源码以下是rsa2048的c源码和验证范例，基于qt测试，也可以结合硬件性能改为rsa1024，移植时注意适配形如 portable_***的三个api。
/************************************///关注微信公众号 嵌入式系统/************************************///rsa.h#include stdlib.h#define rsa_encode_len (2048/8) //rsa2048即256字节，可以视硬件情况改为1024typedef unsigned char uint8_t;typedef unsigned short int uint16_t;typedef unsigned int uint32_t;#define bi_maxlen 130#define dec 10#define hex 16#define carryover 0x10000#define carrylast 0xfffftypedef struct{ uint32_t m_nlength; //大数在0x1 00 00 00 00进制下的长度 uint16_t m_ulvalue[bi_maxlen]; //用数组记录大数在0x100000000进制下每一位的值} cbigint;//rsa.c#include rsa.h#include time.h/******************* 适配api *******************/#define portable_malloc malloc#define portable_free free//随机数种子源uint32_t portable_rand_seed(void){ time_t timestamp; time(×tamp); return timestamp;}/******************* 适配api *******************//*****************************************************************基本操作与运算init, 构造大数对象并初始化为零mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“m_nlength > a->m_nlength) { return 1; } if(n->m_nlength m_nlength) { return -1; } for(i = n->m_nlength - 1; i >= 0; i--) { if(n->m_ulvalue[i] > a->m_ulvalue[i]) { return 1; } if(n->m_ulvalue[i] m_ulvalue[i]) { return -1; } } return 0;}/****************************************************************************************大数赋值调用方式：__mov_big_big(a)返回值：n,被赋值为a****************************************************************************************/static cbigint *mov_big_big(cbigint *x, cbigint *a){ memcpy(x, a, sizeof(cbigint)); return x;}static cbigint *mov_big_long(cbigint *n, uint32_t a){ int i; if(a > carrylast) { n->m_nlength = 2; n->m_ulvalue[1] = (uint16_t)(a >> 16); n->m_ulvalue[0] = (uint16_t)a; } else { n->m_nlength = 1; n->m_ulvalue[0] = (uint16_t)a; } memset((unsigned char*)&n->m_ulvalue[n->m_nlength], 0, sizeof(uint16_t) * (bi_maxlen - n->m_nlength)); return n;}/****************************************************************************************大数相加调用形式：add_big_big(x,a)返回值：x=x+a****************************************************************************************/static cbigint *add_big_big(cbigint *x, cbigint *a){ uint32_t i; uint16_t carry = 0; uint32_t sum = 0; if(x->m_nlength m_nlength) { x->m_nlength = a->m_nlength; } for(i = 0; i m_nlength; i++) { sum = a->m_ulvalue[i]; sum = sum + x->m_ulvalue[i] + carry; x->m_ulvalue[i] = (uint16_t)sum; carry = (uint16_t)(sum >> 16); } x->m_ulvalue[x->m_nlength] = carry; x->m_nlength += carry; return x;}static cbigint *add_big_long(cbigint *x, uint32_t a){ uint32_t sum; sum = x->m_ulvalue[0]; sum += a; x->m_ulvalue[0] = (uint16_t)sum; if(sum > carrylast) { uint32_t i = 1; while(x->m_ulvalue[i] == carrylast) { x->m_ulvalue[i] = 0; i++; } x->m_ulvalue[i]++; if(x->m_nlength == i) { x->m_nlength++; } } return x;}/****************************************************************************************大数相减调用形式：sub_big_big(x,a)返回值：x=x-a****************************************************************************************/static cbigint *sub_big_big(cbigint *x, cbigint *a){ if(cmp(x, a) m_ulvalue[i] > a->m_ulvalue[i]) || ((x->m_ulvalue[i] == a->m_ulvalue[i]) && (carry == 0))) { x->m_ulvalue[i] = x->m_ulvalue[i] - carry - a->m_ulvalue[i]; carry = 0; } else { num = carryover + x->m_ulvalue[i]; x->m_ulvalue[i] = (uint32_t)(num - carry - a->m_ulvalue[i]); carry = 1; } } while(x->m_ulvalue[x->m_nlength - 1] == 0) { x->m_nlength--; } return x; }}static cbigint *sub_big_long(cbigint *x, uint32_t a){ if(x->m_ulvalue[0] >= a) { x->m_ulvalue[0] -= a; return x; } if(x->m_nlength == 1) { memset(x, 0, sizeof(cbigint)); return x; } else { uint32_t num = carryover + x->m_ulvalue[0]; int i = 1; x->m_ulvalue[0] = (uint16_t)(num - a); while(x->m_ulvalue[i] == 0) { x->m_ulvalue[i] = carrylast; i++; } x->m_ulvalue[i]--; if(x->m_ulvalue[i] == 0) { x->m_nlength--; } return x; }}/****************************************************************************************大数相乘调用形式：mul_big_big(n,a)返回值：x=n*a a a 0 n c d 0 d*0 1 c*0 d*a 2 c*a****************************************************************************************/static cbigint *mul_big_big(cbigint *x, cbigint *a){ if(a->m_nlength == 1) { return mul_big_long(x, a->m_ulvalue[0]); } else { uint32_t sum, mul = 0, carry = 0; uint32_t i, j; cbigint n = {0}; memcpy(&n, x, sizeof(cbigint)); memset(x, 0, sizeof(cbigint)); x->m_nlength = n.m_nlength + a->m_nlength - 1; for(i = 0; i m_nlength; i++) { sum = carry; carry = 0; for(j = 0; j m_nlength; j++) { if(((i - j) >= 0) && ((i - j) m_ulvalue[j]; carry += mul >> 16; mul = mul & carrylast; sum += mul; } } carry += sum >> 16; x->m_ulvalue[i] = (uint16_t)sum; } if(carry) { x->m_nlength++; x->m_ulvalue[x->m_nlength - 1] = (uint16_t)carry; } return x; }}static cbigint *mul_big_long(cbigint *x, uint32_t a){ uint32_t mul; uint32_t carry = 0; uint32_t i; for(i = 0; i m_nlength; i++) { mul = x->m_ulvalue[i]; mul = mul * a + carry; x->m_ulvalue[i] = (uint16_t)mul; carry = (uint16_t)(mul >> 16); } if(carry) { x->m_nlength++; x->m_ulvalue[x->m_nlength - 1] = carry; } return x;}/****************************************************************************************大数相除调用形式：div_big_big(n,a)返回值：x=n/a****************************************************************************************/static cbigint *div_big_big(cbigint *x, cbigint *a){ cbigint y = {0}, z = {0}, t; if(a->m_nlength == 1) { return div_big_long(x, a->m_ulvalue[0]); } else { uint32_t i, len; uint32_t num, div; memcpy(&y, x, sizeof(cbigint)); while(cmp(&y, a) >= 0) { div = y.m_ulvalue[y.m_nlength - 1]; num = a->m_ulvalue[a->m_nlength - 1]; len = y.m_nlength - a->m_nlength; if((div == num) && (len == 0)) { add_big_long(x, 1); break; } if((div <= num) && len) { len--; div = (div <= len; i--) { z.m_ulvalue[i] = z.m_ulvalue[i - len]; } for(i = 0; i m_nlength == 1) { x->m_ulvalue[0] = x->m_ulvalue[0] / a; return x; } else { uint32_t div, mul; uint32_t carry = 0; int i; for(i = x->m_nlength - 1; i >= 0; i--) { div = carry; div = (div m_ulvalue[i] = (uint16_t)(div / a); mul = (div / a) * a; carry = (uint16_t)(div - mul); } if(x->m_ulvalue[x->m_nlength - 1] == 0) { x->m_nlength--; } return x; }}/****************************************************************************************大数求模调用形式：mod_big_big(n,a)返回值：x=n%a****************************************************************************************/static cbigint *mod_big_big(cbigint *x, cbigint *a){ cbigint y = {0}, z; uint32_t div, num; uint32_t carry = 0; uint32_t i, len; while(cmp(x, a) >= 0) { div = x->m_ulvalue[x->m_nlength - 1]; num = a->m_ulvalue[a->m_nlength - 1]; len = x->m_nlength - a->m_nlength; if((div == num) && (len == 0)) { sub_big_big(x, a); break; } if((div <= num) && len) { len--; div = (div m_nlength - 2]; } div = div / (num + 1); mov_big_long(&y, div); memcpy(&z, a, sizeof(cbigint)); mul_big_big(&z, &y); memcpy(&y, &z, sizeof(cbigint)); if(len) { y.m_nlength += len; for(i = y.m_nlength - 1; i >= len; i--) { y.m_ulvalue[i] = y.m_ulvalue[i - len]; } for(i = 0; i m_nlength == 1) { return(n->m_ulvalue[0] % a); } else { uint32_t div; uint32_t carry = 0; int i; for(i = n->m_nlength - 1; i >= 0; i--) { div = n->m_ulvalue[i]; div += carry * carryover; carry = (uint16_t)(div % a); } return carry; }}/****************************************************************************************从字符串按10进制或16进制格式输入到大数调用格式：get(n,str,sys)返回值：n被赋值为相应大数sys暂时只能为10或16****************************************************************************************/static cbigint *get(cbigint *n, char *s, uint32_t system){ int i; int len = strlen(s), k; memset(n, 0, sizeof(cbigint)); n->m_nlength = 1; for(i = 0; i = '0') && (s[i] = 'a') && (s[i] = 'a') && (s[i] m_ulvalue; memset(n, 0, sizeof(cbigint)); n->m_nlength = 1; for(i = len - 1, j = 0; i >= 0; i--, j++) { p[j] = s[i]; } i = len % 2; if(i > 0) { n->m_nlength = len / 2 + 1; } else { n->m_nlength = len / 2; } return n;}/****************************************************************************************将大数按10进制或16进制格式输出为字符串调用格式：put(n,str,sys)返回值：无，参数str被赋值为n的sys进制字符串sys暂时只能为10或16****************************************************************************************/static char *put(cbigint *n, uint32_t system){ char t[17] = 0123456789abcdef; int i, a; static char s[2048]; if((n->m_nlength == 1) && (n->m_ulvalue[0] == 0)) { return null; } else { cbigint x = {0}; memcpy(&x, n, sizeof(cbigint)); memset(s, 0, 2048); for(i = 2046; x.m_ulvalue[x.m_nlength - 1] > 0 && i > 0; i--) { a = mod_big_long(&x, system); s[i] = t[a]; div_big_long(&x, system); } if(i % 2 == 0) { return &s[i + 1]; } else { s[i] = '0'; return &s[i]; } }}static void puthex(cbigint *n, uint8_t *out, uint16_t *len){ int i, j, size; if((n->m_nlength == 1) && (n->m_ulvalue[0] == 0)) { return; } size = n->m_nlength * sizeof(n->m_ulvalue[0]); for(i = size - 1, j = 0; i >= 0; i--, j++) { out[j] = ((uint8_t*)n->m_ulvalue)[i]; } *len = size;}/****************************************************************************************求不定方程ax-by=1的最小整数解调用方式：euc(n,a)返回值：x,满足：nx mod a=1****************************************************************************************/static cbigint *euc(cbigint *x, cbigint *a){ cbigint m = {0}, e = {0}, n = {0}, y = {0}, i = {0}, j = {0}; int x, y; memcpy(&e, x, sizeof(cbigint)); memcpy(&m, a, sizeof(cbigint)); mov_big_long(x, 0); mov_big_long(&y, 1); x = y = 1; while((e.m_nlength != 1) || (e.m_ulvalue[0] != 0)) { memcpy(&i, &m, sizeof(cbigint)); div_big_big(&i, &e); memcpy(&j, &m, sizeof(cbigint)); mod_big_big(&j, &e); memcpy(&m, &e, sizeof(cbigint)); memcpy(&e, &j, sizeof(cbigint)); memcpy(&j, &y, sizeof(cbigint)); mul_big_big(&y, &i); if(x == y) { if(cmp(x, &y) >= 0) { sub_big_big(&y, x); } else { sub_big_big(&y, x); y = 0; } } else { add_big_big(&y, x); x = 1 - x; y = 1 - y; } memcpy(x, &j, sizeof(cbigint)); } if(x == 0) { sub_big_big(x, a); } return x;}/****************************************************************************************求乘方的模调用方式：rsatrans(n,a,b)返回值：x=n^a mod b****************************************************************************************/static cbigint *rsatrans(cbigint *x, cbigint *a, cbigint *b){ cbigint n = {0}, y = {0}, z; int i, j, k; uint32_t n; uint32_t num; k = a->m_nlength * 16 - 16; num = a->m_ulvalue[a->m_nlength - 1]; while(num) { num = num >> 1; k++; } memcpy(&n, x, sizeof(cbigint)); for(i = k - 2; i >= 0; i--) { memcpy(&y, x, sizeof(cbigint)); mul_big_long(&y, x->m_ulvalue[x->m_nlength - 1]); mod_big_big(&y, b); for(n = 1; n m_nlength; n++) { for(j = y.m_nlength; j > 0; j--) { y.m_ulvalue[j] = y.m_ulvalue[j - 1]; } y.m_ulvalue[0] = 0; y.m_nlength++; memcpy(&z, x, sizeof(cbigint)); mul_big_long(&z, x->m_ulvalue[x->m_nlength - n - 1]); add_big_big(&y, &z); mod_big_big(&y, b); } memcpy(x, &y, sizeof(cbigint)); if((a->m_ulvalue[i >> 4] >> (i & 15)) & 1) { memcpy(&y, &n, sizeof(cbigint)); mul_big_long(&y, x->m_ulvalue[x->m_nlength - 1]); mod_big_big(&y, b); for(n = 1; n m_nlength; n++) { for(j = y.m_nlength; j > 0; j--) { y.m_ulvalue[j] = y.m_ulvalue[j - 1]; } y.m_ulvalue[0] = 0; y.m_nlength++; memcpy(&z, &n, sizeof(cbigint)); mul_big_long(&z, x->m_ulvalue[x->m_nlength - n - 1]); add_big_big(&y, &z); mod_big_big(&y, b); } memcpy(x, &y, sizeof(cbigint)); } } return x;}/****************************************************************************************拉宾米勒算法测试素数调用方式：rab(n)返回值：若n为素数，返回1，否则返回0****************************************************************************************/static int rab(cbigint *n){ cbigint s = {0}, a = {0}, i = {0}, k = {0}; uint32_t i, j, pass; for(i = 0; i < 550; i++) { if(mod_big_long(n, primetable[i]) == 0) { return 0; } } memcpy(&k, n, sizeof(cbigint)); k.m_ulvalue[0]--; for(i = 0; i < 5; i++) { pass = 0; mov_big_long(&a, rand()*rand()); memcpy(&s, &k, sizeof(cbigint)); while((s.m_ulvalue[0] & 1) == 0) { for(j = 0; j > 1; if(s.m_ulvalue[j + 1] & 1) { s.m_ulvalue[j] = s.m_ulvalue[j] | 0x8000; } } if(s.m_ulvalue[s.m_nlength - 1] == 0) { s.m_nlength--; } memcpy(&i, &a, sizeof(cbigint)); rsatrans(&i, &s, n); if(cmp(&i, &k) == 0) { pass = 1; break; } } if((i.m_nlength == 1) && (i.m_ulvalue[0] == 1)) { pass = 1; } if(pass == 0) { return 0; } } return 1;}/****************************************************************************************产生随机素数调用方法：getprime(n,bits)返回值：n,被赋值为一个bits位（0x100000000进制长度）的素数****************************************************************************************/static cbigint *getprime(cbigint *n, int bits){ uint32_t i; cbigint s = {0}, a = {0}, i = {0}, k = {0}; memset(n, 0, sizeof(cbigint)); n->m_nlength = bits;begin: srand(portable_rand_seed()); for(i = 0; i m_nlength; i++) { n->m_ulvalue[i] = rand() * 0x100 + rand(); } n->m_ulvalue[0] = n->m_ulvalue[0] | 1; for(i = n->m_nlength - 1; i > 0; i--) { n->m_ulvalue[i] = n->m_ulvalue[i] m_ulvalue[i]++; } } n->m_ulvalue[0] = n->m_ulvalue[0]> 2]; *pos++ = base64_table[((in[0] & 0x03) 4)]; *pos++ = base64_table[((in[1] & 0x0f) 6)]; *pos++ = base64_table[in[2] & 0x3f]; in += 3; line_len += 4; if(line_len >= 72) { *pos++ = '\\n'; line_len = 0; } } if(end - in) { *pos++ = base64_table[in[0] >> 2]; if(end - in == 1) { *pos++ = base64_table[(in[0] & 0x03) << 4]; *pos++ = '='; } else { *pos++ = base64_table[((in[0] & 0x03) 4)]; *pos++ = base64_table[(in[1] & 0x0f) << 2]; } *pos++ = '='; line_len += 4; } if(line_len) { *pos++ = '\\n'; } *pos = '\\0'; if(out_len) { *out_len = pos - out; } return out;}//需要释放内存unsigned char * base64_decode(const unsigned char *src, size_t len, size_t *out_len){ unsigned char dtable[256], *out, *pos, block[4], tmp; size_t i, count, olen; int pad = 0; memset(dtable, 0x80, 256); for(i = 0; i < sizeof(base64_table) - 1; i++) { dtable[base64_table[i]] = (unsigned char) i; } dtable['='] = 0; count = 0; for(i = 0; i < len; i++) { if(dtable[src[i]] != 0x80) { count++; } } if(count == 0 || count % 4) { return null; } olen = count / 4 * 3; pos = out = portable_malloc(olen); if(out == null) { return null; } count = 0; for(i = 0; i < len; i++) { tmp = dtable[src[i]]; if(tmp == 0x80) { continue; } if(src[i] == '=') { pad++; } block[count] = tmp; count++; if(count == 4) { *pos++ = (block[0] 4); *pos++ = (block[1] 2); *pos++ = (block[2] <模数+指数 char *publickey_exponent = 10001; char *privatekey_exponent = 1271146b0d38ef95697ac52c484334a59cbd2777ca220fc41d08d2dfe440aeedc6721d08f1a57780fa459a208bf6e867c8210a5e95b3e206a8472093c2a52d11adac04eb054d101df54a1d73f62806047a3e7fb3c10963dc7f2c9fcaa78d90e2e70071fe4b06c4d2a0b635c3ea88505e6f05fe16c1a5de87909889881af5a35fdae0ace1f4bd4ea58552e5017410dde274d92df75d6f7e303e6ea0575e301ff481ef8ab43619e08dce61f2831891840580922d9f9b4a466ca15401fa3eb20b433d3da3ac0e2b8521c6e2632bf08581a6bd3cd9a28d9eceee8f14fd9dd0429743e9ede7cf3424f8fb3a9fc95001eb1dab621b574ea47bc2c0123087d22f3ca821; //hex array ,faster than string //直接使用16进制数据可略微提高速度，软件也支持传入字符串 // 具体看代码中 gethex 和 get static unsigned char modulushex[rsa_encode_len] = { 0xc2, 0x67, 0xa3, 0x46, 0x1c, 0x3f, 0x48, 0x1d, 0xb1, 0x07, 0x7a, 0xe0, 0x25, 0x88, 0x60, 0x39, 0x60, 0x43, 0x5f, 0xf0, 0xe9, 0xa2, 0x70, 0xd5, 0x54, 0xfc, 0xd3, 0x5a, 0x19, 0xf7, 0x27, 0x82, 0x0d, 0xbf, 0xa8, 0xd4, 0x6b, 0xd1, 0xc3, 0x91, 0xe1, 0xe1, 0xca, 0xce, 0x0e, 0x39, 0x94, 0xcd, 0x6a, 0x3a, 0xfc, 0x91, 0x1c, 0xb8, 0x4c, 0x87, 0xa6, 0xa2, 0xd9, 0xc8, 0x60, 0xe3, 0x49, 0x9e, 0x85, 0xbb, 0x57, 0x22, 0x10, 0x10, 0x09, 0x04, 0xcb, 0x17, 0x0c, 0x7a, 0xdb, 0x79, 0x9a, 0xa4, 0x4f, 0x04, 0xbb, 0xb2, 0x73, 0xc1, 0x72, 0x82, 0x7e, 0x21, 0xa3, 0xfa, 0xdd, 0xf4, 0x92, 0x1d, 0xe3, 0xe3, 0xe0, 0x28, 0xb9, 0xab, 0xe8, 0xd5, 0x5c, 0xb9, 0x90, 0xa9, 0x55, 0x73, 0xde, 0x83, 0x2a, 0x8d, 0xc7, 0x49, 0xd1, 0xfd, 0x4a, 0x23, 0x21, 0x26, 0xea, 0xfc, 0x1b, 0xbe, 0x36, 0x57, 0x12, 0xb6, 0x68, 0x9c, 0x65, 0x4b, 0x80, 0x79, 0x56, 0xe4, 0x18, 0x65, 0x0e, 0x96, 0xfb, 0x4c, 0xcc, 0x57, 0xa1, 0x90, 0x13, 0xf0, 0x13, 0x7d, 0x44, 0x76, 0x96, 0x14, 0xab, 0xef, 0xf3, 0x2e, 0xe2, 0x7c, 0x39, 0xac, 0x42, 0xfb, 0x39, 0xb9, 0x3c, 0x5a, 0x36, 0x01, 0x92, 0x5f, 0x23, 0x91, 0xb3, 0xe6, 0x58, 0x1b, 0xd6, 0x0e, 0x6e, 0x77, 0x44, 0xc6, 0xd4, 0x95, 0x2b, 0x9b, 0xd0, 0xe5, 0xe7, 0xf2, 0x52, 0x35, 0x22, 0xf7, 0x49, 0x70, 0x44, 0x0b, 0xbe, 0xe6, 0x75, 0xf7, 0x74, 0x04, 0x0e, 0x55, 0x16, 0x5f, 0x25, 0x57, 0xb2, 0x1f, 0x4d, 0xf4, 0x93, 0x50, 0x4f, 0x48, 0x2a, 0x83, 0x1e, 0xbe, 0xa6, 0x71, 0xa1, 0xa1, 0xa9, 0xc8, 0xdf, 0x99, 0x70, 0x16, 0xf2, 0xe4, 0xd8, 0x2c, 0xa2, 0xa2, 0x49, 0xea, 0xf9, 0x9c, 0x25, 0x11, 0x63, 0x23, 0xdd, 0x94, 0xac, 0x51, 0xd5, 0xd7 }; unsigned char encode_str[rsa_encode_len] = {0}; unsigned char decode_str[rsa_encode_len] = {0}; int outlen = 0; unsigned char * base64_str = null; unsigned int base64_str_len = null; uint8_t* decode_base64 = null; char pub_source_string[] = embedded-system > public key to rsa encode,hehe; char pri_source_string[] = embedded-system > private key to rsa encode,haha; printf(rsa demo); //--------------------------------------------------- memset(encode_str, 0, sizeof(encode_str)); memset(decode_str, 0, sizeof(decode_str)); //公钥加密 outlen = rsa2048_pub_pkcs1padding_encode(pub_source_string, strlen(pub_source_string), encode_str, publickey_exponent, modulushex); //密文转base64方便显示，和在线工具对比结果 // https://the-x.cn/cryptography/rsa.aspx //base64_str = base64_encode(encode_str, outlen, &base64_str_len); //printf(public encode %d\\r\\n%s\\r\\n, base64_str_len, base64_str); //portable_free(base64_str); //私钥解密 rsa2048_pri_pkcs1padding_decode(encode_str, &outlen, decode_str, privatekey_exponent, modulushex); printf(private decode %d\\r\\n%s\\r\\n, outlen, decode_str); //--------------------------------------------------- memset(encode_str, 0, sizeof(encode_str)); memset(decode_str, 0, sizeof(decode_str)); //私钥签名 outlen = rsa2048_pri_pkcs1padding_encode(pri_source_string, strlen(pri_source_string), encode_str, privatekey_exponent, modulushex); //公钥验签 rsa2048_pub_pkcs1padding_decode(encode_str, &outlen, decode_str, publickey_exponent, modulushex); printf(public decode %d\\r\\n%s\\r\\n, outlen, decode_str); //--------------------------------------------------- printf(rsa demo done); return 0;}5、应用和aes一样，rsa也是块加密算法（ block cipher algorithm），只针对固定长度数据块，如rsa2048其加密的数据长度需要填充后是2048位即256字节，如果明文长度大于244字节则需要拆分。当然最简单的办法是应用层分配多个244字节缓存，有效数据以外以0x00填充。
rsa算法虽然安全，但其计算量非常大，效率较低，尤其在嵌入式系统中，硬件资源有限的情况下加密、解密时间以秒为单位。而对称加密算法aes算法效率高，但其在密钥协商时，在网络传输中有被拦截的风险，或者任一方保存不当导致密钥泄露，其密钥存在很大的安全隐患。
所以，考虑到安全性和高效性，一般采用多种算法组合加密的方式。使用rsa来加密aes的密钥，密钥协商后，使用aes来对后续数据进行加密。
更多信息，请关注微信公众号 嵌入式系统
尔必地获天剑智能首批1000台机器人订单
RA2快速设计指南 [2] MCU工作模式和选项设置存储器
索尼发布两款新Crystal LED显示屏
IT6523D宽范围大功率可编程直流电源
小米6Plus什么时候上市？小米6Plus最新消息：屏幕5.7英寸大，依然骁龙835！对比小米6变化有哪些
嵌入式的RSA非对称加密算法
搜狗AI持续以“语言”为核心 围绕着智能交互和知识计算进行尝试
无“芯”可用，华为手机业务可能真的要被困死了
快递送上门却不在家？或许你可以试试这款沃尔玛的智能锁
2019年大数据市场新趋势 AI成为主流
宽输入并联均流升功率模块电源——FB-1254YMDG系列
大数据和人工智能与云计算如何为各地应对疫情新措施
TDA8945J各引脚功能及电压
云主机对比物理服务器，云主机的性价比更高
千元机市场的领军者荣耀9X，发布的29天时间里突破300万
安全锁具上锁挂牌上市七个流程的详细介绍
纯电动车的真实市场需求究竟在哪
一文了解阻塞赋值与非阻塞赋值
LG 电子正在研发下一代汽车智能前照灯
胶水粘接工艺及UL94-V0密封粘接胶水
双方都必须保管好密钥，任一方的密钥泄露，都会导致加密信息不安全；尤其是双方协商更换密钥过程中，密钥会出现在传输过程中，严重影响数据的安全性。
对称加密算法常用的aes可以参考[ 嵌入式算法6---aes加密/解密算法 ]
2、非对称加密算法和对称加密算法最大的区别是，非对称加密算法需要两个密钥，公开密钥（public key 简称公钥）和私有密钥（private key 简称私钥），且公钥与私钥是互相关联的一对。使用公钥对数据进行加密，只有用对应的私钥才能解密，私钥加密签名也只有公钥能解密验签。
非对称加密算法实现机密信息交换的基本过程：
1、甲方生成一对密钥并将公钥公开，私钥保密
2、乙方使用甲方的提供的公钥，对机密信息加密后再发送给甲方；甲方使用自己私钥对加密后的信息进行解密
3、甲方也可以使用自己的私钥对机密信息进行签名后再发送给乙方，乙方用甲方的提供公钥对甲方发来的密文进行验签
非对称加密算法的特点：
1、公钥公开，私钥私藏，无需双方传输密钥协商，所以安全性比对称加密算法更高
2、非对称加密的算法复杂，运算速度比对称加密解密的速度慢很多
3、一般情况下使用非对称加密保护对称加密的密钥，密钥协商后使用对称加密进行通信
4、最佳实现是双方各自保存自己的私钥，使用对方的公钥加密数据传输
3、rsa算法与密钥非对称加密算法中最常用的当属 rsa ，其算法本身基于一个简单的数论知识，给出两个素数，很容易将它们相乘，然而给出它们的乘积，想得到这两个素数就显得尤为困难。具体的私钥与公钥生成原理和加密、解密过程，不是本文关注的重点。
私钥和公钥的生成，可以借助mbedtls源码或openssl工具生成，举例如下：
1、安装openssl，下载地址
https://www.openssl.org/
2、安装后进入openssl命令行界面，使用命令生成rsa2048的私钥，存入private.key文件
openssl>genrsa -out private.key 2048
3、基于公钥生成私钥，存入文件public.key
openssl> rsa -in private.key -pubout -out public.key
4、有些算法库采用传入指数、模数方式进行加解密，而前面生成的公私钥是pem格式，需要变成exponent、modulus形式，就可以使用以下工具在线转换。
https://www.oren.net.cn/rsa/info.html
5、关于mbedtls应用，可以参考[ mbedtls 基础及其应用 ]，该开源库针对嵌入式系统，且囊括了很多常用的算法。
4、源码以下是rsa2048的c源码和验证范例，基于qt测试，也可以结合硬件性能改为rsa1024，移植时注意适配形如 portable_***的三个api。
/************************************///关注微信公众号 嵌入式系统/************************************///rsa.h#include stdlib.h#define rsa_encode_len (2048/8) //rsa2048即256字节，可以视硬件情况改为1024typedef unsigned char uint8_t;typedef unsigned short int uint16_t;typedef unsigned int uint32_t;#define bi_maxlen 130#define dec 10#define hex 16#define carryover 0x10000#define carrylast 0xfffftypedef struct{ uint32_t m_nlength; //大数在0x1 00 00 00 00进制下的长度 uint16_t m_ulvalue[bi_maxlen]; //用数组记录大数在0x100000000进制下每一位的值} cbigint;//rsa.c#include rsa.h#include time.h/******************* 适配api *******************/#define portable_malloc malloc#define portable_free free//随机数种子源uint32_t portable_rand_seed(void){ time_t timestamp; time(×tamp); return timestamp;}/******************* 适配api *******************//*****************************************************************基本操作与运算init, 构造大数对象并初始化为零mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“m_nlength > a->m_nlength) { return 1; } if(n->m_nlength m_nlength) { return -1; } for(i = n->m_nlength - 1; i >= 0; i--) { if(n->m_ulvalue[i] > a->m_ulvalue[i]) { return 1; } if(n->m_ulvalue[i] m_ulvalue[i]) { return -1; } } return 0;}/****************************************************************************************大数赋值调用方式：__mov_big_big(a)返回值：n,被赋值为a****************************************************************************************/static cbigint *mov_big_big(cbigint *x, cbigint *a){ memcpy(x, a, sizeof(cbigint)); return x;}static cbigint *mov_big_long(cbigint *n, uint32_t a){ int i; if(a > carrylast) { n->m_nlength = 2; n->m_ulvalue[1] = (uint16_t)(a >> 16); n->m_ulvalue[0] = (uint16_t)a; } else { n->m_nlength = 1; n->m_ulvalue[0] = (uint16_t)a; } memset((unsigned char*)&n->m_ulvalue[n->m_nlength], 0, sizeof(uint16_t) * (bi_maxlen - n->m_nlength)); return n;}/****************************************************************************************大数相加调用形式：add_big_big(x,a)返回值：x=x+a****************************************************************************************/static cbigint *add_big_big(cbigint *x, cbigint *a){ uint32_t i; uint16_t carry = 0; uint32_t sum = 0; if(x->m_nlength m_nlength) { x->m_nlength = a->m_nlength; } for(i = 0; i m_nlength; i++) { sum = a->m_ulvalue[i]; sum = sum + x->m_ulvalue[i] + carry; x->m_ulvalue[i] = (uint16_t)sum; carry = (uint16_t)(sum >> 16); } x->m_ulvalue[x->m_nlength] = carry; x->m_nlength += carry; return x;}static cbigint *add_big_long(cbigint *x, uint32_t a){ uint32_t sum; sum = x->m_ulvalue[0]; sum += a; x->m_ulvalue[0] = (uint16_t)sum; if(sum > carrylast) { uint32_t i = 1; while(x->m_ulvalue[i] == carrylast) { x->m_ulvalue[i] = 0; i++; } x->m_ulvalue[i]++; if(x->m_nlength == i) { x->m_nlength++; } } return x;}/****************************************************************************************大数相减调用形式：sub_big_big(x,a)返回值：x=x-a****************************************************************************************/static cbigint *sub_big_big(cbigint *x, cbigint *a){ if(cmp(x, a) m_ulvalue[i] > a->m_ulvalue[i]) || ((x->m_ulvalue[i] == a->m_ulvalue[i]) && (carry == 0))) { x->m_ulvalue[i] = x->m_ulvalue[i] - carry - a->m_ulvalue[i]; carry = 0; } else { num = carryover + x->m_ulvalue[i]; x->m_ulvalue[i] = (uint32_t)(num - carry - a->m_ulvalue[i]); carry = 1; } } while(x->m_ulvalue[x->m_nlength - 1] == 0) { x->m_nlength--; } return x; }}static cbigint *sub_big_long(cbigint *x, uint32_t a){ if(x->m_ulvalue[0] >= a) { x->m_ulvalue[0] -= a; return x; } if(x->m_nlength == 1) { memset(x, 0, sizeof(cbigint)); return x; } else { uint32_t num = carryover + x->m_ulvalue[0]; int i = 1; x->m_ulvalue[0] = (uint16_t)(num - a); while(x->m_ulvalue[i] == 0) { x->m_ulvalue[i] = carrylast; i++; } x->m_ulvalue[i]--; if(x->m_ulvalue[i] == 0) { x->m_nlength--; } return x; }}/****************************************************************************************大数相乘调用形式：mul_big_big(n,a)返回值：x=n*a a a 0 n c d 0 d*0 1 c*0 d*a 2 c*a****************************************************************************************/static cbigint *mul_big_big(cbigint *x, cbigint *a){ if(a->m_nlength == 1) { return mul_big_long(x, a->m_ulvalue[0]); } else { uint32_t sum, mul = 0, carry = 0; uint32_t i, j; cbigint n = {0}; memcpy(&n, x, sizeof(cbigint)); memset(x, 0, sizeof(cbigint)); x->m_nlength = n.m_nlength + a->m_nlength - 1; for(i = 0; i m_nlength; i++) { sum = carry; carry = 0; for(j = 0; j m_nlength; j++) { if(((i - j) >= 0) && ((i - j) m_ulvalue[j]; carry += mul >> 16; mul = mul & carrylast; sum += mul; } } carry += sum >> 16; x->m_ulvalue[i] = (uint16_t)sum; } if(carry) { x->m_nlength++; x->m_ulvalue[x->m_nlength - 1] = (uint16_t)carry; } return x; }}static cbigint *mul_big_long(cbigint *x, uint32_t a){ uint32_t mul; uint32_t carry = 0; uint32_t i; for(i = 0; i m_nlength; i++) { mul = x->m_ulvalue[i]; mul = mul * a + carry; x->m_ulvalue[i] = (uint16_t)mul; carry = (uint16_t)(mul >> 16); } if(carry) { x->m_nlength++; x->m_ulvalue[x->m_nlength - 1] = carry; } return x;}/****************************************************************************************大数相除调用形式：div_big_big(n,a)返回值：x=n/a****************************************************************************************/static cbigint *div_big_big(cbigint *x, cbigint *a){ cbigint y = {0}, z = {0}, t; if(a->m_nlength == 1) { return div_big_long(x, a->m_ulvalue[0]); } else { uint32_t i, len; uint32_t num, div; memcpy(&y, x, sizeof(cbigint)); while(cmp(&y, a) >= 0) { div = y.m_ulvalue[y.m_nlength - 1]; num = a->m_ulvalue[a->m_nlength - 1]; len = y.m_nlength - a->m_nlength; if((div == num) && (len == 0)) { add_big_long(x, 1); break; } if((div <= num) && len) { len--; div = (div <= len; i--) { z.m_ulvalue[i] = z.m_ulvalue[i - len]; } for(i = 0; i m_nlength == 1) { x->m_ulvalue[0] = x->m_ulvalue[0] / a; return x; } else { uint32_t div, mul; uint32_t carry = 0; int i; for(i = x->m_nlength - 1; i >= 0; i--) { div = carry; div = (div m_ulvalue[i] = (uint16_t)(div / a); mul = (div / a) * a; carry = (uint16_t)(div - mul); } if(x->m_ulvalue[x->m_nlength - 1] == 0) { x->m_nlength--; } return x; }}/****************************************************************************************大数求模调用形式：mod_big_big(n,a)返回值：x=n%a****************************************************************************************/static cbigint *mod_big_big(cbigint *x, cbigint *a){ cbigint y = {0}, z; uint32_t div, num; uint32_t carry = 0; uint32_t i, len; while(cmp(x, a) >= 0) { div = x->m_ulvalue[x->m_nlength - 1]; num = a->m_ulvalue[a->m_nlength - 1]; len = x->m_nlength - a->m_nlength; if((div == num) && (len == 0)) { sub_big_big(x, a); break; } if((div <= num) && len) { len--; div = (div m_nlength - 2]; } div = div / (num + 1); mov_big_long(&y, div); memcpy(&z, a, sizeof(cbigint)); mul_big_big(&z, &y); memcpy(&y, &z, sizeof(cbigint)); if(len) { y.m_nlength += len; for(i = y.m_nlength - 1; i >= len; i--) { y.m_ulvalue[i] = y.m_ulvalue[i - len]; } for(i = 0; i m_nlength == 1) { return(n->m_ulvalue[0] % a); } else { uint32_t div; uint32_t carry = 0; int i; for(i = n->m_nlength - 1; i >= 0; i--) { div = n->m_ulvalue[i]; div += carry * carryover; carry = (uint16_t)(div % a); } return carry; }}/****************************************************************************************从字符串按10进制或16进制格式输入到大数调用格式：get(n,str,sys)返回值：n被赋值为相应大数sys暂时只能为10或16****************************************************************************************/static cbigint *get(cbigint *n, char *s, uint32_t system){ int i; int len = strlen(s), k; memset(n, 0, sizeof(cbigint)); n->m_nlength = 1; for(i = 0; i = '0') && (s[i] = 'a') && (s[i] = 'a') && (s[i] m_ulvalue; memset(n, 0, sizeof(cbigint)); n->m_nlength = 1; for(i = len - 1, j = 0; i >= 0; i--, j++) { p[j] = s[i]; } i = len % 2; if(i > 0) { n->m_nlength = len / 2 + 1; } else { n->m_nlength = len / 2; } return n;}/****************************************************************************************将大数按10进制或16进制格式输出为字符串调用格式：put(n,str,sys)返回值：无，参数str被赋值为n的sys进制字符串sys暂时只能为10或16****************************************************************************************/static char *put(cbigint *n, uint32_t system){ char t[17] = 0123456789abcdef; int i, a; static char s[2048]; if((n->m_nlength == 1) && (n->m_ulvalue[0] == 0)) { return null; } else { cbigint x = {0}; memcpy(&x, n, sizeof(cbigint)); memset(s, 0, 2048); for(i = 2046; x.m_ulvalue[x.m_nlength - 1] > 0 && i > 0; i--) { a = mod_big_long(&x, system); s[i] = t[a]; div_big_long(&x, system); } if(i % 2 == 0) { return &s[i + 1]; } else { s[i] = '0'; return &s[i]; } }}static void puthex(cbigint *n, uint8_t *out, uint16_t *len){ int i, j, size; if((n->m_nlength == 1) && (n->m_ulvalue[0] == 0)) { return; } size = n->m_nlength * sizeof(n->m_ulvalue[0]); for(i = size - 1, j = 0; i >= 0; i--, j++) { out[j] = ((uint8_t*)n->m_ulvalue)[i]; } *len = size;}/****************************************************************************************求不定方程ax-by=1的最小整数解调用方式：euc(n,a)返回值：x,满足：nx mod a=1****************************************************************************************/static cbigint *euc(cbigint *x, cbigint *a){ cbigint m = {0}, e = {0}, n = {0}, y = {0}, i = {0}, j = {0}; int x, y; memcpy(&e, x, sizeof(cbigint)); memcpy(&m, a, sizeof(cbigint)); mov_big_long(x, 0); mov_big_long(&y, 1); x = y = 1; while((e.m_nlength != 1) || (e.m_ulvalue[0] != 0)) { memcpy(&i, &m, sizeof(cbigint)); div_big_big(&i, &e); memcpy(&j, &m, sizeof(cbigint)); mod_big_big(&j, &e); memcpy(&m, &e, sizeof(cbigint)); memcpy(&e, &j, sizeof(cbigint)); memcpy(&j, &y, sizeof(cbigint)); mul_big_big(&y, &i); if(x == y) { if(cmp(x, &y) >= 0) { sub_big_big(&y, x); } else { sub_big_big(&y, x); y = 0; } } else { add_big_big(&y, x); x = 1 - x; y = 1 - y; } memcpy(x, &j, sizeof(cbigint)); } if(x == 0) { sub_big_big(x, a); } return x;}/****************************************************************************************求乘方的模调用方式：rsatrans(n,a,b)返回值：x=n^a mod b****************************************************************************************/static cbigint *rsatrans(cbigint *x, cbigint *a, cbigint *b){ cbigint n = {0}, y = {0}, z; int i, j, k; uint32_t n; uint32_t num; k = a->m_nlength * 16 - 16; num = a->m_ulvalue[a->m_nlength - 1]; while(num) { num = num >> 1; k++; } memcpy(&n, x, sizeof(cbigint)); for(i = k - 2; i >= 0; i--) { memcpy(&y, x, sizeof(cbigint)); mul_big_long(&y, x->m_ulvalue[x->m_nlength - 1]); mod_big_big(&y, b); for(n = 1; n m_nlength; n++) { for(j = y.m_nlength; j > 0; j--) { y.m_ulvalue[j] = y.m_ulvalue[j - 1]; } y.m_ulvalue[0] = 0; y.m_nlength++; memcpy(&z, x, sizeof(cbigint)); mul_big_long(&z, x->m_ulvalue[x->m_nlength - n - 1]); add_big_big(&y, &z); mod_big_big(&y, b); } memcpy(x, &y, sizeof(cbigint)); if((a->m_ulvalue[i >> 4] >> (i & 15)) & 1) { memcpy(&y, &n, sizeof(cbigint)); mul_big_long(&y, x->m_ulvalue[x->m_nlength - 1]); mod_big_big(&y, b); for(n = 1; n m_nlength; n++) { for(j = y.m_nlength; j > 0; j--) { y.m_ulvalue[j] = y.m_ulvalue[j - 1]; } y.m_ulvalue[0] = 0; y.m_nlength++; memcpy(&z, &n, sizeof(cbigint)); mul_big_long(&z, x->m_ulvalue[x->m_nlength - n - 1]); add_big_big(&y, &z); mod_big_big(&y, b); } memcpy(x, &y, sizeof(cbigint)); } } return x;}/****************************************************************************************拉宾米勒算法测试素数调用方式：rab(n)返回值：若n为素数，返回1，否则返回0****************************************************************************************/static int rab(cbigint *n){ cbigint s = {0}, a = {0}, i = {0}, k = {0}; uint32_t i, j, pass; for(i = 0; i < 550; i++) { if(mod_big_long(n, primetable[i]) == 0) { return 0; } } memcpy(&k, n, sizeof(cbigint)); k.m_ulvalue[0]--; for(i = 0; i < 5; i++) { pass = 0; mov_big_long(&a, rand()*rand()); memcpy(&s, &k, sizeof(cbigint)); while((s.m_ulvalue[0] & 1) == 0) { for(j = 0; j > 1; if(s.m_ulvalue[j + 1] & 1) { s.m_ulvalue[j] = s.m_ulvalue[j] | 0x8000; } } if(s.m_ulvalue[s.m_nlength - 1] == 0) { s.m_nlength--; } memcpy(&i, &a, sizeof(cbigint)); rsatrans(&i, &s, n); if(cmp(&i, &k) == 0) { pass = 1; break; } } if((i.m_nlength == 1) && (i.m_ulvalue[0] == 1)) { pass = 1; } if(pass == 0) { return 0; } } return 1;}/****************************************************************************************产生随机素数调用方法：getprime(n,bits)返回值：n,被赋值为一个bits位（0x100000000进制长度）的素数****************************************************************************************/static cbigint *getprime(cbigint *n, int bits){ uint32_t i; cbigint s = {0}, a = {0}, i = {0}, k = {0}; memset(n, 0, sizeof(cbigint)); n->m_nlength = bits;begin: srand(portable_rand_seed()); for(i = 0; i m_nlength; i++) { n->m_ulvalue[i] = rand() * 0x100 + rand(); } n->m_ulvalue[0] = n->m_ulvalue[0] | 1; for(i = n->m_nlength - 1; i > 0; i--) { n->m_ulvalue[i] = n->m_ulvalue[i] m_ulvalue[i]++; } } n->m_ulvalue[0] = n->m_ulvalue[0]
rsa算法虽然安全，但其计算量非常大，效率较低，尤其在嵌入式系统中，硬件资源有限的情况下加密、解密时间以秒为单位。而对称加密算法aes算法效率高，但其在密钥协商时，在网络传输中有被拦截的风险，或者任一方保存不当导致密钥泄露，其密钥存在很大的安全隐患。
所以，考虑到安全性和高效性，一般采用多种算法组合加密的方式。使用rsa来加密aes的密钥，密钥协商后，使用aes来对后续数据进行加密。
更多信息，请关注微信公众号 嵌入式系统
尔必地获天剑智能首批1000台机器人订单
RA2快速设计指南 [2] MCU工作模式和选项设置存储器
索尼发布两款新Crystal LED显示屏
IT6523D宽范围大功率可编程直流电源
小米6Plus什么时候上市？小米6Plus最新消息：屏幕5.7英寸大，依然骁龙835！对比小米6变化有哪些
嵌入式的RSA非对称加密算法
搜狗AI持续以“语言”为核心 围绕着智能交互和知识计算进行尝试
无“芯”可用，华为手机业务可能真的要被困死了
快递送上门却不在家？或许你可以试试这款沃尔玛的智能锁
2019年大数据市场新趋势 AI成为主流
宽输入并联均流升功率模块电源——FB-1254YMDG系列
大数据和人工智能与云计算如何为各地应对疫情新措施
TDA8945J各引脚功能及电压
云主机对比物理服务器，云主机的性价比更高
千元机市场的领军者荣耀9X，发布的29天时间里突破300万
安全锁具上锁挂牌上市七个流程的详细介绍
纯电动车的真实市场需求究竟在哪
一文了解阻塞赋值与非阻塞赋值
LG 电子正在研发下一代汽车智能前照灯
胶水粘接工艺及UL94-V0密封粘接胶水