嵌入式算法之DH秘钥交换算法

嵌入式系统 2023-03-28 原文

1 应用

关于加密，对称加密和非对称加密各有优劣，最佳方案是先使用非对称加密实现秘钥交换，后面再利用协商的结果作为对称加密的秘钥，具体可以参考《嵌入式算法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算法

3.1 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的复杂度。

3.2 DH原理说明范例

对上图的原理不太明晰的，可以直接看范例源码，通过简化版的算法来理解。


#include<stdio.h>
#include<math.h>

//(g^x)%p
unsigned int dh_mod(unsigned int g, unsigned int x, unsigned int p)
{
    return (((unsigned int)pow(g, x)) % p);
}

int main(void)
{
    unsigned int p, 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("Alice private key : %d\r\n", a);
    A = dh_mod(G, a, p);

    b = 7;
    printf("Bob private key : %d\r\n", b);
    B = dh_mod(G, b, p);

    //最终计算得出本次的协商的秘钥
    ka = dh_mod(B, a, p);
    kb = dh_mod(A, b, p);

    printf("Secret key ka : %d\r\n", ka);
    printf("Secret Key kb : %d\r\n", kb);

    return 0;
}

提高算法的安全性，最简单的就是加大p值，范例中107只是说明算法原理，该值太小实际不会被采用，一般取大素数，比如取1024位的素数，再低也不能少于128位。对于g则不需要很大，一般是2或5。对于大于32位或者64位的数据运算，不能使用C语言的基础数据类型，需要转为大数据，即采用数组来表示大数值，因此实际应用中采用下面的源码。

3.3 DH算法源码

主要是解决超大数值的运算。范例128位的数值计算结果，可作为AES128的秘钥，这里只是提供范例。基础算法dh.h和dh.c，并在main.c进行测试。可根据实际应用调整，比如素数p的位数，生成随机数的种子需要结合软件适配。其实这块算法是RSA的一部分，也可从RSA算法中挑选出。

dh.h

#ifndef _DH_H
#define _DH_H

typedef int int32_t;
typedef short int16_t;
typedef char int8_t;

typedef unsigned int uint32_t;
typedef unsigned short uint16_t;
typedef unsigned char uint8_t;


#define RSA_ENCODE_LEN  (2048/8)

#define BI_MAXLEN 130
#define DEC 10
#define HEX 16

#define CARRYOVER  0x10000
#define CARRYLAST  0xFFFF

typedef struct
{
    uint32_t m_nLength;    //大数长度
    uint16_t m_ulValue[BI_MAXLEN];    //用数组记录大数在0x100000000进制下每一位的值
} CBigInt;


int Cmp(CBigInt *N, CBigInt *A);
CBigInt* Mov_Big_Big(CBigInt *X, CBigInt *A);
CBigInt* Mov_Big_Long(CBigInt *N, uint32_t A);
CBigInt* Add_Big_Big(CBigInt *X, CBigInt *A);
CBigInt* Add_Big_Long(CBigInt *X, uint32_t A);
CBigInt* Sub_Big_Big(CBigInt *X, CBigInt *A);
CBigInt* Sub_Big_Long(CBigInt *X, uint32_t A);
CBigInt* Mul_Big_Big(CBigInt *X, CBigInt *A);
CBigInt* Mul_Big_Long(CBigInt *X, uint32_t A);
CBigInt* Div_Big_Big(CBigInt *X, CBigInt *A);
CBigInt* Div_Big_Long(CBigInt *X, uint32_t A);
CBigInt* Mod_Big_Big(CBigInt *X, CBigInt *A);
uint32_t Mod_Big_Long(CBigInt *N, uint32_t A);
CBigInt* Get(CBigInt *N, char *s, uint32_t system);
CBigInt* GetHex(CBigInt *N, unsigned char *s, unsigned short len, uint32_t system);
char* Put(CBigInt *N, uint32_t system);
void PutHex(CBigInt *N, uint8_t *out, uint16_t *len);
CBigInt* Euc(CBigInt *X, CBigInt *A);
CBigInt* RsaTrans(CBigInt *X, CBigInt *A, CBigInt *B);
int Rab(CBigInt *N);
CBigInt* GetPrime(CBigInt *N, int bits);
void entropy_poll(unsigned char *output, unsigned int len);

#endif  /* _DH_H */

dh.c

注意适配随机数种子接口portable_rand_seed

//微信公众号：嵌入式系统
#include "dh.h"
#include "stdlib.h"

/******************* 适配API *******************/
//结合SDK平台设定随机数种子源
//例如系统tick，这里只是举例
uint32_t portable_rand_seed(void)
{
    time_t timestamp;
    time(&timestamp);
    return timestamp;
}

/******************* 适配API *******************/

/*****************************************************************
基本操作与运算
Init, 构造大数对象并初始化为零
Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”
Cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“<=”等
Add，加，求大数与大数或大数与普通整数的和，可重载为运算符“+”
Sub，减，求大数与大数或大数与普通整数的差，可重载为运算符“-”
Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“*”
Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“/”
Mod，模，求大数与大数或大数与普通整数的模，可重载为运算符“%”
*****************************************************************/
/*****************************************************************
输入输出
Get，从字符串按10进制或16进制格式输入到大数
Put，将大数按10进制或16进制格式输出到字符串
*****************************************************************/
//static CBigInt *Get(CBigInt *N, char *str, uint32_t system);
//static char *Put(CBigInt *N, uint32_t system);

/*****************************************************************
RSA相关运算
Rab，拉宾米勒算法进行素数测试
Euc，欧几里德算法求解同余方程
RsaTrans，反复平方算法进行幂模运算
GetPrime，产生指定长度的随机大素数
*****************************************************************/
//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);


/*****************************************************************
大数运算库源文件：BigInt.c
说明：适用于C，linux系统 1024位RSA运算
*****************************************************************/
//小素数表
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
};

/****************************************************************************************
大数比较
调用方式：Cmp(N,A)
返回值：若N<A返回-1；若N=A返回0；若N>A返回1
****************************************************************************************/
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;
}

/****************************************************************************************
大数赋值
调用方式：__Mov_Big_Big(A)
返回值：N,被赋值为A
****************************************************************************************/
CBigInt* Mov_Big_Big(CBigInt *X, CBigInt *A)
{
    memcpy(X, A, sizeof(CBigInt));
    return X;
}

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
****************************************************************************************/
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;
}

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
****************************************************************************************/
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;
    }
}

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

****************************************************************************************/
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;
    }
}

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;
}

/****************************************************************************************
大数相除
调用形式：Div_Big_Big(N,A)
返回值：X=N/A
****************************************************************************************/
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;
    }
}

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;
    }
}

/****************************************************************************************
大数求模
调用形式：Mod_Big_Big(N,A)
返回值：X=N%A
****************************************************************************************/
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;
}

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进制格式输入到大数
调用格式：Get(N,str,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
****************************************************************************************/
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;
}

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;
}
/****************************************************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：Put(N,str,sys)
返回值：无，参数str被赋值为N的sys进制字符串
sys暂时只能为10或16
****************************************************************************************/
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];
        }
    }
}

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
****************************************************************************************/
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
****************************************************************************************/
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;
}

/****************************************************************************************
拉宾米勒算法测试素数
调用方式：Rab(N)
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
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;
}

/****************************************************************************************
产生随机素数
调用方法：GetPrime(N,bits)
返回值：N,被赋值为一个bits位（0x100000000进制长度）的素数
****************************************************************************************/
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;
}

/***********************************************************************/
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;
        }
    }
}

main.c

微信公众号【嵌入式系统】测试DH流程的范例

//微信公众号：嵌入式系统
#include "stdio.h"
#include "dh.h"
#include <math.h>

//p大素数可以使用工具生成，例如mbedtls源码
//见 mbedtls\programs\pkey\dh_genprime.c
uint8_t G_hxe_array[]={5};
uint8_t p_hxe_array[]={0xB0 ,0xF9 ,0x89 ,0xE2 ,0xF2 ,0x5D ,0x12 ,0x53 ,0xBF ,0x92 ,0x99 ,0x3D ,0x19 ,0x29 ,0x0C ,0x0F};

//a和b，实际应用使用随机数生成，这里瞎写的范例
uint8_t a_hxe_array[]={0xAA ,0xAA ,0x89 ,0xE2 ,0xF2 ,0x5D ,0x12 ,0x53 ,0xBF ,0x92 ,0x99 ,0x3D ,0x19 ,0x29 ,0xAA ,0xAA};
uint8_t b_hxe_array[]={0x00, 0x01 ,0x02 ,0x03 ,0x04 ,0x05 ,0x06 ,0x07 ,0x08 ,0x09 ,0x0A ,0x0B ,0x0C ,0x0D ,0x0E ,0x0F};

static CBigInt G;
static CBigInt p;
static CBigInt a,A,ka;
static CBigInt b,B,kb;

//协商的结果，最终的秘钥
uint8_t ka_hxe_array[64]={0};
uint8_t kb_hxe_array[64]={0};

void print_BigInt(char *head,CBigInt *N)
{
    uint8_t buff[512]={0};
    uint16_t i,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");
}

void print_hex(char *head,uint8_t *data, uint8_t size)
{
    uint8_t i;

    printf("%s:",head);

    for(i = 0; i < size; ++i)
    {
        printf("%02X ", (uint8_t)data[i]);
    }
    printf("\r\n");
}

int main(int argc, char *argv[])
{
    uint16_t len;
    CBigInt tmp;

    printf("DH demo\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\nDH result\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);

    return 0;
}

因为大数值的特殊存储，先将数组转为大数据格式，再进行指数幂求模，原理和前面的完全一样。随机数和素数的描述见代码注释。

运行输出：

//微信公众号：嵌入式系统
DH demo
G:2 > 00 05
p:16 > B0 F9 89 E2 F2 5D 12 53 BF 92 99 3D 19 29 0C 0F
a:16 > AA AA 89 E2 F2 5D 12 53 BF 92 99 3D 19 29 AA AA
b:16 > 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
A:16 > 4C 66 78 BA 01 22 64 E1 E7 E7 B8 D5 72 1E BE 6C
B:16 > A2 F3 22 AE 5E 0F C9 51 A6 88 7A A0 FB CD CB 2F

DH result
[ka] :8A CC 93 89 BB D2 27 4C 32 39 6F 28 7E 4A AC 0D
[kb] :8A CC 93 89 BB D2 27 4C 32 39 6F 28 7E 4A AC 0D

4 ECDH算法

EDCH是ECC和DH的结合，在DH交换密钥的基础上结合ECC椭圆曲线难题生成。使用ECC椭圆加密算法替换DH中的指数幂求模，安全性更高，但对资源要求也高。

算法嵌入式 span style color 开发前端 $嵌入式

有关嵌入式算法之DH秘钥交换算法的更多相关文章

区块链之加解密算法&数字证书 - 2
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
100个python算法超详细讲解：画直线 - 2
1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva
ruby - 在 Ruby 中实现 Luhn 算法 - 2
我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s
Ruby 斐波那契算法 - 2
下面是我写的一个计算斐波那契数列中的值的方法:deffib(n)ifn==0return0endifn==1return1endifn>=2returnfib(n-1)+(fib(n-2))endend它工作到n=14，但在那之后我收到一条消息说程序响应时间太长(我正在使用repl.it)。有人知道为什么会这样吗？最佳答案 Naivefibonacci进行了大量的重复计算-在fib(14)fib(4)中计算了很多次。您可以将内存添加到您的算法中以使其更快:deffib(n,memo={})ifn==0||n==1returnnen
ruby - Perl 和 Ruby 之间的 YAML 数据交换问题 - 2
我在通过YAML在Perl和Ruby之间交换数据时遇到问题。我有一些看起来像数字:数字的值，例如1:16。Perl的YAML库(Tiny和XS)将其编码为1:16，不带引号。Ruby的YAML库(Psych)不会将其解释为字符串，而是以某种方式变成Fixnum值4560。我不知道如何在任何一方解决这个转换问题。我用例的YAML中的每个值都应该是一个对象或字符串。因此，如果存在这样的选项，我可以告诉PerlYAML库引用所有值。或者有什么方法可以告诉RubyYAML库将所有值解释为字符串？有任何想法吗？从逻辑上讲，改变任何一方的语言都不是一种选择。Perl:useYAML::XSqw
ruby-on-rails - Rails add_index 算法 : :concurrently still causes database lock up during migration - 2
为了防止在迁移到生产站点期间出现数据库事务错误，我们遵循了https://github.com/LendingHome/zero_downtime_migrations中列出的建议。(具体由https://robots.thoughtbot.com/how-to-create-postgres-indexes-concurrently-in概述)，但在特别大的表上创建索引期间，即使是索引创建的“并发”方法也会锁定表并导致该表上的任何ActiveRecord创建或更新导致各自的事务失败有PG::InFailedSqlTransaction异常。下面是我们运行Rails4.2(使用Acti
ruby - 趋势算法 - 2
我正在开发一个类似微论坛的项目，其中一个特殊用户发布一条快速(接近推文大小)的主题消息，订阅者可以用他们自己的类似大小的消息来响应。直截了当，没有任何形式的“挖掘”或投票，只是每个主题消息的响应按时间顺序排列。但预计会有很高的流量。我们想根据它们引起的响应嗡嗡声来标记主题消息，使用0到10的等级。在谷歌上搜索了一段时间的趋势算法和开源社区应用示例，到目前为止已经收集到两个有趣的引用资料，但我还没有完全理解它们:Understandingalgorithmsformeasuringtrends，关于使用基线趋势算法比较维基百科页面浏览量的讨论，在SO上。TheBritneySpearsP
Ruby - 不支持的密码算法 (AES-256-GCM) - 2
我收到错误:unsupportedcipheralgorithm(AES-256-GCM)(RuntimeError)但我似乎具备所有要求:ruby版本:$ruby--versionruby2.1.2p95OpenSSL会列出gcm:$opensslenc-help2>&1|grepgcm-aes-128-ecb-aes-128-gcm-aes-128-ofb-aes-192-ecb-aes-192-gcm-aes-192-ofb-aes-256-ecb-aes-256-gcm-aes-256-ofbRuby解释器:$irb2.1.2:001>require'openssl';puts
java实现Dijkstra算法 - 2
文章目录一.Dijkstra算法想解决的问题二.Dijkstra算法理论三.java代码实现一.Dijkstra算法想解决的问题解决的问题:求解单源最短路径,即各个节点到达源点的最短路径或权值考察其他所有节点到源点的最短路径和长度局限性:无法解决权值为负数的情况二.Dijkstra算法理论参数:S记录当前已经处理过的源点到最短节点U记录还未处理的节点dist[]记录各个节点到起始节点的最短权值path[]记录各个节点的上一级节点(用来联系该节点到起始节点的路径)Dijkstra算法步骤:(1）初始化:顶点集S:节点A到自已的最短路径长度为0。只包含源点，即S={A}顶点集U:包含除A外的其他顶
对于体育新闻中文文本关键字提取有哪些关键字提取算法及其步骤 - 2
对于体育新闻中文文本的关键字提取，常用的算法包括TF-IDF、TextRank和LDA等。它们的基本步骤如下：1.TF-IDF算法： -将文本进行分词和词性标注处理。-统计每个词在文本中的词频（TF）。-计算每个词在整个语料库中出现的文档频率（DF）和逆文档频率（IDF）。-计算每个词的TF-IDF值，并按照值的大小进行排序，选择排名前几的词作为关键字。2.TextRank算法：-将文本进行分词和词性标注处理。-将分词结果转化成图模型，每个词语为节点，根据词语之间的共现关系建立边。-对图模型进行迭代计算，计算每个节点的PageRank值，表示该节点的重要性。-选择排名前几的节点作为关键字。3.