页面加载中，请稍候
来源:嵌入式系统发布时间:2023-03-241447浏览
询问 AI关于加密，对称加密和非对称加密各有优劣，最佳方案是先使用非对称加密实现秘钥交换，后面再利用协商的结果作为对称加密的秘钥，具体可以参考 《嵌入式算法6---AES加密/解密算法》、《嵌入式算法18---RSA非对称加密算法》。
如果一定要在一条不安全的线路上交换秘钥，且交换的秘钥不能被中间人破解，则是本文关注的秘钥交换算法。
2 简易方案最原始的不涉及算法的，A需要向B发送信息（信息经过编码后都是数组，后续描述都是针对数值），双方协商将原始数据加1，即源信息为1实际发2，源信息为2实际发3，B收到数据后进行减1的逆运算，表面加1或减1的规则就是协商的秘钥。也可以复杂点，双方协商一组255字节的随机值数组，后续双方通信时，以需要发送的数据（转uint8_t数组）为序号（数组下标）查表得出对应密文，再发出去，有点类似Base64的原理。
或者A和B各生成一组随机值并发送给对方，按提前定义的规则将两组随机值转换成唯一的结果，后续以此为对称加密AES的秘钥进行通信，一旦规则泄露很容易被破解，这种是比较适合忽悠外行的加密方式。
3 DH算法DH算法即迪菲-赫尔曼密钥交换（Diffie–Hellman key exchange，缩写为D-H） 是一种安全协议，可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥，这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。
mod为求模运算，可以简单理解为求余，对应C语言的%运算符。
微信公众号：嵌入式系统
如上图，Alice和Bob需要协商秘钥，Alice选择一个随机自然数 a 并且将 g^a mod p 发送给Bob。Bob选择一个随机自然数 b 并且将 g^b mod p 发送给Alice。Alice计算 出g^{ba} mod p ，Bob计算出 g^{ab} mod p。因为在模p下 g^{ab} 和 g^{ba} 相等，最终Alice和Bob都得到了同样的值，即得出了公共秘密K。后续就可以把它用作对称密钥进行双方的加密通讯，因为这个密钥只有他们才能得到。
注意a, b 和 K=g^ab = g^ba mod p 是秘密的。其他所有的值 p, g, A=g^a mod p, 以及B= g^b mod p 都可以在公共信道上传输。一般情况下a,b是各自生成的随机值，A和B是根据随机值计算出的中间量，这个算法的破解难度就是增加从A和B逆运算出a和b的复杂度。
对上图的原理不太明晰的，可以直接看范例源码，通过简化版的算法来理解。
#include<stdio.h>
#include<math.h>
//(g^x)%p
unsignedintdh_mod(unsignedintg,unsignedintx,unsignedintp)
{
return(((unsignedint)pow(g,x))%p);
}
intmain(void)
{
unsignedintp,G,a,b,A,B,ka,kb;
p=107;
printf("p=%d\r\n",p);
G=5;
printf("G=%d\r\n",G);
//各自的私钥（正式版本a和b为随机值），以及计算出的公钥
a=5;
printf("Aliceprivatekey:%d\r\n",a);
A=dh_mod(G,a,p);
b=7;
printf("Bobprivatekey:%d\r\n",b);
B=dh_mod(G,b,p);
//最终计算得出本次的协商的秘钥
ka=dh_mod(B,a,p);
kb=dh_mod(A,b,p);
printf("Secretkeyka:%d\r\n",ka);
printf("SecretKeykb:%d\r\n",kb);
return0;
}
提高算法的安全性，最简单的就是加大p值，范例中107只是说明算法原理，该值太小实际不会被采用，一般取大素数，比如取1024位的素数，再低也不能少于128位。对于g则不需要很大，一般是2或5。
对于大于32位或者64位的数据运算，不能使用C语言的基础数据类型，需要转为大数据，即采用数组来表示大数值，因此实际应用中采用下面的源码。
主要是解决超大数值的运算。范例128位的数值计算结果，可作为AES128的秘钥，这里只是提供范例。基础算法dh.h和dh.c，并在main.c进行测试。可根据实际应用调整，比如素数p的位数，生成随机数的种子需要结合软件适配。其实这块算法是RSA的一部分，也可从RSA算法中挑选出。
dh.h
#ifndef_DH_H
#define_DH_H
typedefintint32_t;
typedefshortint16_t;
typedefcharint8_t;
typedefunsignedintuint32_t;
typedefunsignedshortuint16_t;
typedefunsignedcharuint8_t;
#defineRSA_ENCODE_LEN(2048/8)
#defineBI_MAXLEN130
#defineDEC10
#defineHEX16
#defineCARRYOVER0x10000
#defineCARRYLAST0xFFFF
typedefstruct
{
uint32_tm_nLength;//大数长度
uint16_tm_ulValue[BI_MAXLEN];//用数组记录大数在0x100000000进制下每一位的值
}CBigInt;
intCmp(CBigInt*N,CBigInt*A);
CBigInt*Mov_Big_Big(CBigInt*X,CBigInt*A);
CBigInt*Mov_Big_Long(CBigInt*N,uint32_tA);
CBigInt*Add_Big_Big(CBigInt*X,CBigInt*A);
CBigInt*Add_Big_Long(CBigInt*X,uint32_tA);
CBigInt*Sub_Big_Big(CBigInt*X,CBigInt*A);
CBigInt*Sub_Big_Long(CBigInt*X,uint32_tA);
CBigInt*Mul_Big_Big(CBigInt*X,CBigInt*A);
CBigInt*Mul_Big_Long(CBigInt*X,uint32_tA);
CBigInt*Div_Big_Big(CBigInt*X,CBigInt*A);
CBigInt*Div_Big_Long(CBigInt*X,uint32_tA);
CBigInt*Mod_Big_Big(CBigInt*X,CBigInt*A);
uint32_tMod_Big_Long(CBigInt*N,uint32_tA);
CBigInt*Get(CBigInt*N,char*s,uint32_tsystem);
CBigInt*GetHex(CBigInt*N,unsignedchar*s,unsignedshortlen,uint32_tsystem);
char*Put(CBigInt*N,uint32_tsystem);
voidPutHex(CBigInt*N,uint8_t*out,uint16_t*len);
CBigInt*Euc(CBigInt*X,CBigInt*A);
CBigInt*RsaTrans(CBigInt*X,CBigInt*A,CBigInt*B);
intRab(CBigInt*N);
CBigInt*GetPrime(CBigInt*N,intbits);
voidentropy_poll(unsignedchar*output,unsignedintlen);
#endif/*_DH_H*/
dh.c
注意适配随机数种子接口portable_rand_seed
//微信公众号：嵌入式系统
#include"dh.h"
#include"stdlib.h"
/*******************适配API*******************/
//结合SDK平台设定随机数种子源
//例如系统tick，这里只是举例
uint32_tportable_rand_seed(void)
{
time_ttimestamp;
time(timestamp);
returntimestamp;
}
/*******************适配API*******************/
/*****************************************************************
基本操作与运算
Init,构造大数对象并初始化为零
Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”
Cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“<=”等
Add，加，求大数与大数或大数与普通整数的和，可重载为运算符“+”
Sub，减，求大数与大数或大数与普通整数的差，可重载为运算符“-”
Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“*”
Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“/”
Mod，模，求大数与大数或大数与普通整数的模，可重载为运算符“%”
*****************************************************************/
/*****************************************************************
输入输出
Get，从字符串按10进制或16进制格式输入到大数
Put，将大数按10进制或16进制格式输出到字符串
*****************************************************************/
//staticCBigInt*Get(CBigInt*N,char*str,uint32_tsystem);
//staticchar*Put(CBigInt*N,uint32_tsystem);
/*****************************************************************
RSA相关运算
Rab，拉宾米勒算法进行素数测试
Euc，欧几里德算法求解同余方程
RsaTrans，反复平方算法进行幂模运算
GetPrime，产生指定长度的随机大素数
*****************************************************************/
//staticintRab(CBigInt*N);
//staticCBigInt*Euc(CBigInt*X,CBigInt*A);
//staticCBigInt*RsaTrans(CBigInt*X,CBigInt*A,CBigInt*B);
//staticCBigInt*GetPrime(CBigInt*X,intbits);
/*****************************************************************
大数运算库源文件：BigInt.c
说明：适用于C，linux系统1024位RSA运算
*****************************************************************/
//小素数表
conststaticintPrimeTable[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
};
/****************************************************************************************
大数比较
调用方式：Cmp(N,A)
返回值：若N<A返回-1；若N=A返回0；若N>A返回1
****************************************************************************************/
intCmp(CBigInt*N,CBigInt*A)
{
inti;
if(N->m_nLength>A->m_nLength)
{
return1;
}
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])
{
return1;
}
if(N->m_ulValue[i]<A->m_ulValue[i])
{
return-1;
}
}
return0;
}
/****************************************************************************************
大数赋值
调用方式：__Mov_Big_Big(A)
返回值：N,被赋值为A
****************************************************************************************/
CBigInt*Mov_Big_Big(CBigInt*X,CBigInt*A)
{
memcpy(X,A,sizeof(CBigInt));
returnX;
}
CBigInt*Mov_Big_Long(CBigInt*N,uint32_tA)
{
inti;
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((unsignedchar*)N->m_ulValue[N->m_nLength],0,sizeof(uint16_t)*(BI_MAXLEN-N->m_nLength));
returnN;
}
/****************************************************************************************
大数相加
调用形式：Add_Big_Big(X,A)
返回值：X=X+A
****************************************************************************************/
CBigInt*Add_Big_Big(CBigInt*X,CBigInt*A)
{
uint32_ti;
uint16_tcarry=0;
uint32_tsum=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;
returnX;
}
CBigInt*Add_Big_Long(CBigInt*X,uint32_tA)
{
uint32_tsum;
sum=X->m_ulValue[0];
sum+=A;
X->m_ulValue[0]=(uint16_t)sum;
if(sum>CARRYLAST)
{
uint32_ti=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++;
}
}
returnX;
}
/****************************************************************************************
大数相减
调用形式：Sub_Big_Big(X,A)
返回值：X=X-A
****************************************************************************************/
CBigInt*Sub_Big_Big(CBigInt*X,CBigInt*A)
{
if(Cmp(X,A)<=0)
{
memset(X,0,sizeof(CBigInt));
returnX;
}
else
{
uint16_tcarry=0;
uint32_tnum;
uint32_ti;
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--;
}
returnX;
}
}
CBigInt*Sub_Big_Long(CBigInt*X,uint32_tA)
{
if(X->m_ulValue[0]>=A)
{
X->m_ulValue[0]-=A;
returnX;
}
if(X->m_nLength==1)
{
memset(X,0,sizeof(CBigInt));
returnX;
}
else
{
uint32_tnum=CARRYOVER+X->m_ulValue[0];
inti=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--;
}
returnX;
}
}
/****************************************************************************************
大数相乘
调用形式：Mul_Big_Big(N,A)
返回值：X=N*A
Aa0
Ncd
0d*0
1c*0
d*a
2c*a
****************************************************************************************/
CBigInt*Mul_Big_Big(CBigInt*X,CBigInt*A)
{
if(A->m_nLength==1)
{
returnMul_Big_Long(X,A->m_ulValue[0]);
}
else
{
uint32_tsum,mul=0,carry=0;
uint32_ti,j;
CBigIntN={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=mulCARRYLAST;
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;
}
returnX;
}
}
CBigInt*Mul_Big_Long(CBigInt*X,uint32_tA)
{
uint32_tmul;
uint32_tcarry=0;
uint32_ti;
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;
}
returnX;
}
/****************************************************************************************
大数相除
调用形式：Div_Big_Big(N,A)
返回值：X=N/A
****************************************************************************************/
CBigInt*Div_Big_Big(CBigInt*X,CBigInt*A)
{
CBigIntY={0},Z={0},T;
if(A->m_nLength==1)
{
returnDiv_Big_Long(X,A->m_ulValue[0]);
}
else
{
uint32_ti,len;
uint32_tnum,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);
}
returnX;
}
}
CBigInt*Div_Big_Long(CBigInt*X,uint32_tA)
{
if(X->m_nLength==1)
{
X->m_ulValue[0]=X->m_ulValue[0]/A;
returnX;
}
else
{
uint32_tdiv,mul;
uint32_tcarry=0;
inti;
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--;
}
returnX;
}
}
/****************************************************************************************
大数求模
调用形式：Mod_Big_Big(N,A)
返回值：X=N%A
****************************************************************************************/
CBigInt*Mod_Big_Big(CBigInt*X,CBigInt*A)
{
CBigIntY={0},Z;
uint32_tdiv,num;
uint32_tcarry=0;
uint32_ti,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);
}
returnX;
}
uint32_tMod_Big_Long(CBigInt*N,uint32_tA)
{
if(N->m_nLength==1)
{
return(N->m_ulValue[0]%A);
}
else
{
uint32_tdiv;
uint32_tcarry=0;
inti;
for(i=N->m_nLength-1;i>=0;i--)
{
div=N->m_ulValue[i];
div+=carry*CARRYOVER;
carry=(uint16_t)(div%A);
}
returncarry;
}
}
/****************************************************************************************
从字符串按10进制或16进制格式输入到大数
调用格式：Get(N,str,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
****************************************************************************************/
CBigInt*Get(CBigInt*N,char*s,uint32_tsystem)
{
inti;
intlen=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;
}
elseif((s[i]>='A')(s[i]<='F'))
{
k=s[i]-55;
}
elseif((s[i]>='a')(s[i]<='f'))
{
k=s[i]-87;
}
else
{
k=0;
}
Add_Big_Long(N,k);
}
returnN;
}
CBigInt*GetHex(CBigInt*N,unsignedchar*s,unsignedshortlen,uint32_tsystem)
{
inti,j;
unsignedchar*p=(unsignedchar*)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;
}
returnN;
}
/****************************************************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：Put(N,str,sys)
返回值：无，参数str被赋值为N的sys进制字符串
sys暂时只能为10或16
****************************************************************************************/
char*Put(CBigInt*N,uint32_tsystem)
{
chart[17]="0123456789ABCDEF";
inti,a;
staticchars[2048];
if((N->m_nLength==1)(N->m_ulValue[0]==0))
{
returnNULL;
}
else
{
CBigIntX={0};
memcpy(X,N,sizeof(CBigInt));
memset(s,0,2048);
for(i=2046;X.m_ulValue[X.m_nLength-1]>0i>0;i--)
{
a=Mod_Big_Long(X,system);
s[i]=t[a];
Div_Big_Long(X,system);
}
if(i%2==0)
{
returns[i+1];
}
else
{
s[i]='0';
returns[i];
}
}
}
voidPutHex(CBigInt*N,uint8_t*out,uint16_t*len)
{
inti,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,满足：NXmodA=1
****************************************************************************************/
CBigInt*Euc(CBigInt*X,CBigInt*A)
{
CBigIntM={0},E={0},N={0},Y={0},I={0},J={0};
intx,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);
}
returnX;
}
/****************************************************************************************
求乘方的模
调用方式：RsaTrans(N,A,B)
返回值：X=N^AMODB
****************************************************************************************/
CBigInt*RsaTrans(CBigInt*X,CBigInt*A,CBigInt*B)
{
CBigIntN={0},Y={0},Z;
inti,j,k;
uint32_tn;
uint32_tnum;
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]>>(i15))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));
}
}
returnX;
}
/****************************************************************************************
拉宾米勒算法测试素数
调用方式：Rab(N)
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
intRab(CBigInt*N)
{
CBigIntS={0},A={0},I={0},K={0};
uint32_ti,j,pass;
for(i=0;i<550;i++)
{
if(Mod_Big_Long(N,PrimeTable[i])==0)
{
return0;
}
}
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)
{
return0;
}
}
return1;
}
/****************************************************************************************
产生随机素数
调用方法：GetPrime(N,bits)
返回值：N,被赋值为一个bits位（0x100000000进制长度）的素数
****************************************************************************************/
CBigInt*GetPrime(CBigInt*N,intbits)
{
uint32_ti;
CBigIntS={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)
{
gotobegin;
}
}
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))
{
gotobegin;
}
}
returnN;
}
/***********************************************************************/
voidentropy_poll(unsignedchar*output,unsignedintlen)
{
if(len>0)
{
inti;
srand(portable_rand_seed());//随机数种子
for(i=0;i<len;i++)
{
output[i]=rand()%0xff+1;
}
}
}
main.c
微信公众号【嵌入式系统】测试DH流程的范例
//微信公众号：嵌入式系统
#include"stdio.h"
#include"dh.h"
#include<math.h>
//p大素数可以使用工具生成，例如mbedtls源码
//见mbedtls\programs\pkey\dh_genprime.c
uint8_tG_hxe_array[]={5};
uint8_tp_hxe_array[]={0xB0,0xF9,0x89,0xE2,0xF2,0x5D,0x12,0x53,0xBF,0x92,0x99,0x3D,0x19,0x29,0x0C,0x0F};
//a和b，实际应用使用随机数生成，这里瞎写的范例
uint8_ta_hxe_array[]={0xAA,0xAA,0x89,0xE2,0xF2,0x5D,0x12,0x53,0xBF,0x92,0x99,0x3D,0x19,0x29,0xAA,0xAA};
uint8_tb_hxe_array[]={0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F};
staticCBigIntG;
staticCBigIntp;
staticCBigInta,A,ka;
staticCBigIntb,B,kb;
//协商的结果，最终的秘钥
uint8_tka_hxe_array[64]={0};
uint8_tkb_hxe_array[64]={0};
voidprint_BigInt(char*head,CBigInt*N)
{
uint8_tbuff[512]={0};
uint16_ti,len;
PutHex(N,buff,len);
printf("%s:%d>",head,len);
for(i=0;i<len;++i)
{
printf("%02X",(uint8_t)buff[i]);
}
printf("\r\n");
}
voidprint_hex(char*head,uint8_t*data,uint8_tsize)
{
uint8_ti;
printf("%s:",head);
for(i=0;i<size;++i)
{
printf("%02X",(uint8_t)data[i]);
}
printf("\r\n");
}
intmain(intargc,char*argv[])
{
uint16_tlen;
CBigInttmp;
printf("DHdemo\r\n");
GetHex(G,(uint8_t*)G_hxe_array,sizeof(G_hxe_array),16);
print_BigInt("G",G);
GetHex(p,(uint8_t*)p_hxe_array,sizeof(p_hxe_array),16);
print_BigInt("p",p);
GetHex(a,(uint8_t*)a_hxe_array,sizeof(a_hxe_array),16);
print_BigInt("a",a);
GetHex(b,(uint8_t*)b_hxe_array,sizeof(b_hxe_array),16);
print_BigInt("b",b);
//A=G^a%p
memcpy(tmp,G,sizeof(CBigInt));
RsaTrans(tmp,a,p);
memcpy(A,tmp,sizeof(CBigInt));
print_BigInt("A",A);
//B=G^b%p
memcpy(tmp,G,sizeof(CBigInt));
RsaTrans(tmp,b,p);
memcpy(B,tmp,sizeof(CBigInt));
print_BigInt("B",B);
//ka=B^a%p
memcpy(tmp,B,sizeof(CBigInt));
RsaTrans(tmp,a,p);
memcpy(ka,tmp,sizeof(CBigInt));
//kb=A^b%p
memcpy(tmp,A,sizeof(CBigInt));
RsaTrans(tmp,b,p);
memcpy(kb,tmp,sizeof(CBigInt));
printf("\r\nDHresult\r\n");
PutHex(ka,ka_hxe_array,len);
print_hex("[ka]",ka_hxe_array,len);
PutHex(kb,kb_hxe_array,len);
print_hex("[kb]",kb_hxe_array,len);
return0;
}
因为大数值的特殊存储，先将数组转为大数据格式，再进行指数幂求模，原理和前面的完全一样。随机数和素数的描述见代码注释。
运行输出：
//微信公众号：嵌入式系统
DHdemo
G:2>0005
p:16>B0F989E2F25D1253BF92993D19290C0F
a:16>AAAA89E2F25D1253BF92993D1929AAAA
b:16>000102030405060708090A0B0C0D0E0F
A:16>4C6678BA012264E1E7E7B8D5721EBE6C
B:16>A2F322AE5E0FC951A6887AA0FBCDCB2F
DHresult
[ka]:8ACC9389BBD2274C32396F287E4AAC0D
[kb]:8ACC9389BBD2274C32396F287E4AAC0D
4 ECDH算法EDCH是ECC和DH的结合，在DH交换密钥的基础上结合ECC椭圆曲线难题生成。使用ECC椭圆加密算法替换DH中的指数幂求模，安全性更高，但对资源要求也高。参考范例可在mbedtls的源码中找到，ECDH算法原理下次再提，可以先参看【嵌入式系统】的《算法合集》。
新闻来源：嵌入式系统，文中所述为作者独立观点，不代表icspec立场。更多精彩资讯请下载icspec App。如对本稿件有异议，请联系微信客服specltkj。
暂无评论哦，快来评论一下吧！
2026-07-07