3771
1、對稱加密算法
對稱加密算法是應用較早的加密算法，數(shù)據(jù)發(fā)送方將明文和密鑰經(jīng)加密算法處理，使其變成密文發(fā)送出去；接收方收到密文后，使用和加密算法相同的密鑰進行逆算法解密，還原出明文。在對稱加密算法中，使用的密鑰只有一個，收發(fā)雙方使用相同的密鑰對數(shù)據(jù)進行加密或解密。
雙方都必須保管好密鑰，任一方的密鑰泄露，都會導致加密信息不安全；尤其是雙方協(xié)商更換密鑰過程中，密鑰會出現(xiàn)在傳輸過程中，嚴重影響數(shù)據(jù)的安全性。
對稱加密算法常用的AES可以參考嵌入式算法6---AES加密/解密算法。
2、非對稱加密算法
和對稱加密算法最大的區(qū)別是，非對稱加密算法需要兩個密鑰，公開密鑰（public key 簡稱公鑰）和私有密鑰（private key 簡稱私鑰），且公鑰與私鑰是互相關(guān)聯(lián)的一對。使用公鑰對數(shù)據(jù)進行加密，只有用對應的私鑰才能解密，私鑰加密簽名也只有公鑰能解密驗簽。
非對稱加密算法實現(xiàn)機密信息交換的基本過程：
1、甲方生成一對密鑰并將公鑰公開，私鑰保密
2、乙方使用甲方的提供的公鑰，對機密信息加密后再發(fā)送給甲方；甲方使用自己私鑰對加密后的信息進行解密
3、甲方也可以使用自己的私鑰對機密信息進行簽名后再發(fā)送給乙方，乙方用甲方的提供公鑰對甲方發(fā)來的密文進行驗簽
非對稱加密算法的特點：
1、公鑰公開，私鑰私藏，無需雙方傳輸密鑰協(xié)商，所以安全性比對稱加密算法更高
2、非對稱加密的算法復雜，運算速度比對稱加密解密的速度慢很多
3、一般情況下使用非對稱加密保護對稱加密的密鑰，密鑰協(xié)商后使用對稱加密進行通信
4、最佳實現(xiàn)是雙方各自保存自己的私鑰，使用對方的公鑰加密數(shù)據(jù)傳輸
3、RSA算法與密鑰
非對稱加密算法中最常用的當屬 RSA ，其算法本身基于一個簡單的數(shù)論知識，給出兩個素數(shù)，很容易將它們相乘，然而給出它們的乘積，想得到這兩個素數(shù)就顯得尤為困難。具體的私鑰與公鑰生成原理和加密、解密過程，不是本文關(guān)注的重點。
私鑰和公鑰的生成，可以借助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、有些算法庫采用傳入指數(shù)、模數(shù)方式進行加解密，而前面生成的公私鑰是PEM格式，需要變成Exponent、Modulus形式，就可以使用以下工具在線轉(zhuǎn)換。
https://www.oren.net.cn/rsa/info.html
5、關(guān)于mbedtls應用，可以參考mbedtls 基礎(chǔ)及其應用，該開源庫適合嵌入式系統(tǒng)，且囊括了常用的各種算法。
4、源碼
以下是RSA2048的C源碼和驗證范例，基于Qt測試，也可以結(jié)合硬件性能改為RSA1024，移植時注意適配形如 portable_***的三個API。
/************************************/
//關(guān)注微信公眾號 嵌入式系統(tǒng)
/************************************/
//rsa.h
#include "stdlib.h"
#define RSA_ENCODE_LEN (2048/8) //RSA2048即256字節(jié)，可以視硬件情況改為1024
typedef 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 0xFFFF
typedef struct
{
uint32_t m_nLength; //大數(shù)在0x1 00 00 00 00進制下的長度
uint16_t m_ulValue[BI_MAXLEN]; //用數(shù)組記錄大數(shù)在0x100000000進制下每一位的值
} CBigInt;
//rsa.c
#include "rsa.h"
#include "time.h"
/******************* 適配API *******************/
#define portable_malloc malloc
#define portable_free free
//隨機數(shù)種子源
uint32_t portable_rand_seed(void)
{
time_t timestamp;
time(×tamp);
return timestamp;
}
/******************* 適配API *******************/
/*****************************************************************
基本操作與運算
Init, 構(gòu)造大數(shù)對象并初始化為零
Mov，賦值運算，可賦值為大數(shù)或普通整數(shù)，可重載為運算符“=”
Cmp，比較運算，可重載為運算符“==”、“!=”、“>=”、“<=”等
Add，加，求大數(shù)與大數(shù)或大數(shù)與普通整數(shù)的和，可重載為運算符“+”
Sub，減，求大數(shù)與大數(shù)或大數(shù)與普通整數(shù)的差，可重載為運算符“-”
Mul，乘，求大數(shù)與大數(shù)或大數(shù)與普通整數(shù)的積，可重載為運算符“*”
Div，除，求大數(shù)與大數(shù)或大數(shù)與普通整數(shù)的商，可重載為運算符“/”
Mod，模，求大數(shù)與大數(shù)或大數(shù)與普通整數(shù)的模，可重載為運算符“%”
*****************************************************************/
static CBigInt *Mov_Big_Long(CBigInt *X, uint32_t A);
static CBigInt *Mov_Big_Big(CBigInt *X, CBigInt *A);
static CBigInt *Add_Big_Big(CBigInt *X, CBigInt *A);
static CBigInt *Sub_Big_Big(CBigInt *X, CBigInt *A);
static CBigInt *Mul_Big_Big(CBigInt *X, CBigInt *A);
static CBigInt *Div_Big_Big(CBigInt *X, CBigInt *A);
static CBigInt *Mod_Big_Big(CBigInt *X, CBigInt *A);
static CBigInt *Add_Big_Long(CBigInt *X, uint32_t A);
static CBigInt *Sub_Big_Long(CBigInt *X, uint32_t A);
static CBigInt *Mul_Big_Long(CBigInt *X, uint32_t A);
static CBigInt *Div_Big_Long(CBigInt *X, uint32_t A);
static uint32_t Mod_Big_Long(CBigInt *N, uint32_t A);
static int Cmp(CBigInt *N, CBigInt *A);
/*****************************************************************
輸入輸出
Get，從字符串按10進制或16進制格式輸入到大數(shù)
Put，將大數(shù)按10進制或16進制格式輸出到字符串
*****************************************************************/
static CBigInt *Get(CBigInt *N, char *str, uint32_t system);
static char *Put(CBigInt *N, uint32_t system);
/*****************************************************************
RSA相關(guān)運算
Rab，拉賓米勒算法進行素數(shù)測試
Euc，歐幾里德算法求解同余方程
RsaTrans，反復平方算法進行冪模運算
GetPrime，產(chǎn)生指定長度的隨機大素數(shù)
*****************************************************************/
static int Rab(CBigInt *N);
static CBigInt *Euc(CBigInt *X, CBigInt *A);
static CBigInt *RsaTrans(CBigInt *X, CBigInt *A, CBigInt *B);
static CBigInt *GetPrime(CBigInt *X, int bits);
/*****************************************************************
大數(shù)運算庫源文件：BigInt.c
說明：適用于C，linux系統(tǒng) 1024位RSA運算
*****************************************************************/
//小素數(shù)表
const static int PrimeTable[550] =
{
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547,
557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229,
1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381,
1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663,
1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823,
1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993,
1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131,
2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621,
2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749,
2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909,
2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083,
3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259,
3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433,
3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581,
3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733,
3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911,
3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001
};
/****************************************************************************************
大數(shù)比較
調(diào)用方式：Cmp(N,A)
返回值：若N<A返回-1；若N=A返回0；若N>A返回1
****************************************************************************************/
static int Cmp(CBigInt *N, CBigInt *A)
{
int i;
if(N->m_nLength > A->m_nLength)
{
return 1;
}
if(N->m_nLength < A->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] < A->m_ulValue[i])
{
return -1;
}
}
return 0;
}
/****************************************************************************************
大數(shù)賦值
調(diào)用方式：__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;
}
/****************************************************************************************
大數(shù)相加
調(diào)用形式：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 < A->m_nLength)
{
X->m_nLength = A->m_nLength;
}
for(i = 0; i < X->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;
}
/****************************************************************************************
大數(shù)相減
調(diào)用形式：Sub_Big_Big(X,A)
返回值：X=X-A
****************************************************************************************/
static CBigInt *Sub_Big_Big(CBigInt *X, CBigInt *A)
{
if(Cmp(X, A) <= 0)
{
memset(X, 0, sizeof(CBigInt));
return X;
}
else
{
uint16_t carry = 0;
uint32_t num;
uint32_t i;
for(i = 0; i < X->m_nLength; i++)
{
if((X->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;
}
}
/****************************************************************************************
大數(shù)相乘
調(diào)用形式：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 < X->m_nLength; i++)
{
sum = carry;
carry = 0;
for(j = 0; j < A->m_nLength; j++)
{
if(((i - j) >= 0) && ((i - j) < N.m_nLength))
{
mul = N.m_ulValue[i - j];
mul *= A->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 < X->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;
}
/****************************************************************************************
大數(shù)相除
調(diào)用形式：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 << 16) + Y.m_ulValue[Y.m_nLength - 2];
}
div = div / (num + 1);
Mov_Big_Long(&Z, div);
if(len)
{
Z.m_nLength += len;
for(i = Z.m_nLength - 1; i >= len; i--)
{
Z.m_ulValue[i] = Z.m_ulValue[i - len];
}
for(i = 0; i < len; i++)
{
Z.m_ulValue[i] = 0;
}
}
Add_Big_Big(X, &Z);
memcpy(&T, A, sizeof(CBigInt));
Mul_Big_Big(&T, &Z);
Sub_Big_Big(&Y, &T);
}
return X;
}
}
static CBigInt *Div_Big_Long(CBigInt *X, uint32_t A)
{
if(X->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 << 16) + X->m_ulValue[i];
X->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;
}
}
/****************************************************************************************
大數(shù)求模
調(diào)用形式：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 << 16) + X->m_ulValue[X->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 < len; i++)
{
Y.m_ulValue[i] = 0;
}
}
Sub_Big_Big(X, &Y);
}
return X;
}
static uint32_t Mod_Big_Long(CBigInt *N, uint32_t A)
{
if(N->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進制格式輸入到大數(shù)
調(diào)用格式：Get(N,str,sys)
返回值：N被賦值為相應大數(shù)
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 < len; i++)
{
Mul_Big_Long(N, system);
if((s[i] >= '0') && (s[i] <= '9'))
{
k = s[i] - 48;
}
else if((s[i] >= 'A') && (s[i] <= 'F'))
{
k = s[i] - 55;
}
else if((s[i] >= 'a') && (s[i] <= 'f'))
{
k = s[i] - 87;
}
else
{
k = 0;
}
Add_Big_Long(N, k);
}
return N;
}
static CBigInt *GetHex(CBigInt *N, unsigned char *s, unsigned short len, uint32_t system)
{
int i, j;
unsigned char *p = (unsigned char*)N->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;
}
/****************************************************************************************
將大數(shù)按10進制或16進制格式輸出為字符串
調(diào)用格式：Put(N,str,sys)
返回值：無，參數(shù)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的最小整數(shù)解
調(diào)用方式：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;
}
/****************************************************************************************
求乘方的模
調(diào)用方式：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 < X->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 < X->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;
}
/****************************************************************************************
拉賓米勒算法測試素數(shù)
調(diào)用方式：Rab(N)
返回值：若N為素數(shù)，返回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 < S.m_nLength; j++)
{
S.m_ulValue[j] = S.m_ulValue[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;
}
/****************************************************************************************
產(chǎn)生隨機素數(shù)
調(diào)用方法：GetPrime(N,bits)
返回值：N,被賦值為一個bits位（0x100000000進制長度）的素數(shù)
****************************************************************************************/
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 < N->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] << 1;
if(N->m_ulValue[i - 1] & 0x8000)
{
N->m_ulValue[i]++;
}
}
N->m_ulValue[0] = N->m_ulValue[0] << 1;
N->m_ulValue[0]++;
for(i = 0; i < 550; i++)
{
if(Mod_Big_Long(N, PrimeTable[i]) == 0)
{
goto begin;
}
}
memcpy(&K, N, sizeof(CBigInt));
K.m_ulValue[0]--;
for(i = 0; i < 5; i++)
{
Mov_Big_Long(&A, rand()*rand());
memcpy(&S, &K, sizeof(CBigInt));
Div_Big_Long(&S, 2);
memcpy(&I, &A, sizeof(CBigInt));
RsaTrans(&I, &S, N);
if(((I.m_nLength != 1) || (I.m_ulValue[0] != 1)) && (Cmp(&I, &K) != 0))
{
goto begin;
}
}
return N;
}
/***********************************************************************/
static void entropy_poll(unsigned char *output, unsigned int len)
{
if(len > 0)
{
int i;
srand(portable_rand_seed);
for(i = 0; i < len; i++)
{
output[i] = rand() % 0xff + 1;
}
}
}
static char *del_PKCS1Padding(char *src)
{
int len = strlen(src);
if(len % 2 == 1)
{
src++;
}
while(*src != 0 && *(src + 1) != 0)
{
if(*src == '0' && *(src + 1) == '0')
{
src += 2;
break;
}
src += 2;
}
return src;
}
static int add_PKCS1Padding(unsigned char *src, unsigned int len, unsigned char *out)
{
if(len > RSA_ENCODE_LEN - 11)
{
return -1;
}
else
{
/*要加密的msg*/
memcpy(&out[RSA_ENCODE_LEN - len], src, len);
out[0] = 0;
out[1] = 2;
/*至少8字節(jié)的隨機數(shù)*/
entropy_poll(&out[2], RSA_ENCODE_LEN - 3 - len);
out[RSA_ENCODE_LEN - len - 1] = 0;
return 0;
}
}
static int PKCS1PKCS1PaddingHexRemove(unsigned char *input, unsigned short *len, unsigned char *output)
{
if(input[0] == 0 && (input[1] == 1 || input[1] == 2))
{
int i;
for(i = 2; i < *len; i++)
{
if(input[i] == 0)
{
*len -= (i + 1);
memcpy(output, &input[i + 1], *len);
return *len;
}
}
}
return -1;
}
int RSA2048_pri_PKCS1Padding_Encode(unsigned char *data, unsigned short len, unsigned char *out, char *publicKey, char *ModulusHex)
{
unsigned char buf[RSA_ENCODE_LEN];
CBigInt N, E;
CBigInt mw, mi, jm;
uint16_t outlen = RSA_ENCODE_LEN;
//Get(&N, Modulus, 16);//string
GetHex(&N, ModulusHex, RSA_ENCODE_LEN, 16);//hex array
Get(&E, publicKey, 16);
add_PKCS1Padding(data, len, buf);
GetHex(&mw, buf, RSA_ENCODE_LEN, 16);
RsaTrans(&mw, &E, &N);
PutHex(&mw, out, &outlen);
return outlen;
}
int RSA2048_pub_PKCS1Padding_Encode(unsigned char *data, unsigned short len, unsigned char *out, char *publicKey, unsigned char *ModulusHex)
{
unsigned char buf[RSA_ENCODE_LEN];
CBigInt N, E;
CBigInt mw, mi, jm;
uint16_t outlen = RSA_ENCODE_LEN;
GetHex(&N, ModulusHex, RSA_ENCODE_LEN, 16);//hex array
Get(&E, publicKey, 16);
add_PKCS1Padding(data, len, buf);
GetHex(&mw, buf, RSA_ENCODE_LEN, 16);
RsaTrans(&mw, &E, &N);
PutHex(&mw, out, &outlen);
return outlen;
}
int RSA2048_pri_PKCS1Padding_Decode(unsigned char *data, unsigned short *len, unsigned char *out, char *privateKey, char *ModulusHex)
{
unsigned char buf[RSA_ENCODE_LEN];
CBigInt N, D;
CBigInt mw, jm;
//Get(&N, Modulus, 16);//string
GetHex(&N, ModulusHex, RSA_ENCODE_LEN, 16);//hex array
Get(&D, privateKey, 16);
GetHex(&mw, data, *len, 16);
RsaTrans(&mw, &D, &N);
PutHex(&mw, buf, len);
PKCS1PKCS1PaddingHexRemove(buf, len, out);
return 0;
}
int RSA2048_pub_PKCS1Padding_Decode(unsigned char *data, unsigned short *len, unsigned char *out, char *privateKey, unsigned char *ModulusHex)
{
unsigned char buf[RSA_ENCODE_LEN];
CBigInt N, D;
CBigInt mw, jm;
int t_len = 0;
GetHex(&N, ModulusHex, RSA_ENCODE_LEN, 16);
Get(&D, privateKey, 16);
GetHex(&mw, data, *len, 16);
RsaTrans(&mw, &D, &N);
PutHex(&mw, buf, len);
t_len = PKCS1PKCS1PaddingHexRemove(buf, len, out);
return t_len;
}
//test
static const unsigned char base64_table[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
//需要釋放內(nèi)存
unsigned char * base64_encode(const unsigned char *src, size_t len, size_t *out_len)
{
unsigned char *out, *pos;
const unsigned char *end, *in;
size_t olen;
int line_len;
olen = len * 4 / 3 + 4; /* 3-byte blocks to 4-byte */
olen += olen / 72; /* line feeds */
olen++; /* nul termination */
if(olen < len)
{
return NULL; /* integer overflow */
}
out = portable_malloc(olen);
if(out == NULL)
{
return NULL;
}
end = src + len;
in = src;
pos = out;
line_len = 0;
while(end - in >= 3)
{
*pos++ = base64_table[in[0] >> 2];
*pos++ = base64_table[((in[0] & 0x03) << 4) | (in[1] >> 4)];
*pos++ = base64_table[((in[1] & 0x0f) << 2) | (in[2] >> 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) |
(in[1] >> 4)];
*pos++ = base64_table[(in[1] & 0x0f) << 2];
}
*pos++ = '=';
line_len += 4;
}
if(line_len)
{
*pos++ = 'n';
}
*pos = '