C语言实现椭圆曲线加密算法(大数版)

1.头文件部分

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

2.大数比较

int big_num_cmp(unsigned long *a, unsigned long *b, int len)
{
    int i = 0;

    for(i=len-1; i>=0; i--)
    {
        if(a[i] > b[i]) return 1;
        else if(a[i] < b[i]) return -1;
    }

    return 0;
}

3.大数基本运算

参见《RSA算法》

4.椭圆曲线上的加法

int ecc_get_key_u(unsigned long *a, unsigned long *p, unsigned long *px, unsigned long *py, unsigned long *qx, unsigned long *qy, unsigned long *h, int len)
{
    unsigned long b[len];
    unsigned long c[len];
    unsigned long d[len];
    unsigned long e[len];
    unsigned long f[len];
    unsigned long g[len];
    unsigned long s[len];
    unsigned long t[len];
    int u = big_num_cmp(qy, py, len);
    int v = big_num_cmp(qx, px, len);

    memset(b, 0x00, sizeof(b));
    memset(c, 0x00, sizeof(c));
    memset(d, 0x00, sizeof(d));
    memset(e, 0x00, sizeof(e));
    memset(f, 0x00, sizeof(f));
    memset(g, 0x00, sizeof(g));
    memset(s, 0x00, sizeof(s));
    memset(t, 0x00, sizeof(t));

    if(u || v)
    {
        if(!v)
        {
            memcpy(h, f, 4*len);

            return -1;
        }

        if(!u)
        {
            memcpy(h, f, 4*len);

            return 0;
        }

        big_num_sub_mod(qy, py, p, b, len);
        big_num_sub_mod(qx, px, p, c, len);

        if(!big_num_is_one(c, len))
        {
            big_num_mod_inv(c, p, d, len);
        }
        else
        {
            memcpy(d, c, 4*len);
        }

        big_num_mul_mod(b, d, p, h, len);
    }
    else
    {
        memset(g, 0x00, sizeof(g));
        g[len-1] = 3;
        big_num_mul_mod(px, px, p, d, len);
        big_num_mul_mod(d, g, p, f, len);
        big_num_add_mod(f, a, p, b, len);
        g[len-1] = 2;
        big_num_mul_mod(py, g, p, c, len);

        if(big_num_is_zero(c, len))
        {
            memcpy(h, f, 4*len);

            return -1;
        }

        if(big_num_is_zero(b, len))
        {
            memcpy(h, f, 4*len);

            return 0;
        }

        memset(d, 0x00, sizeof(d));

        if(!big_num_is_one(c, len))
        {
            big_num_mod_inv(c, p, d, len);
        }
        else
        {
            memcpy(d, c, 4*len);
        }

        big_num_mul_mod(b, d, p, h, len);

        //printf("b[0]=[%d]\n", b[0]);
        //printf("c[0]=[%d]\n", c[0]);
        //printf("p[0]=[%d]\n", p[0]);
        //printf("d[0]=[%d]\n", d[0]);
        //printf("h[0]=[%d]\n", h[0]);
    }

    return 0;
}

int ecc_get_key_r(unsigned long *a, unsigned long *p, unsigned long *px, unsigned long *py, unsigned long *qx, unsigned long *qy, unsigned long *rx, unsigned long *ry, int len)
{
    unsigned long b[len];
    unsigned long c[len];
    unsigned long d[len];
    unsigned long e[len];
    unsigned long f[len];
    unsigned long g[len];
    unsigned long h[len];
    unsigned long s[len];
    unsigned long t[len];
    int u = 0;

    memset(b, 0x00, sizeof(b));
    memset(c, 0x00, sizeof(c));
    memset(d, 0x00, sizeof(d));
    memset(e, 0x00, sizeof(e));
    memset(f, 0x00, sizeof(f));
    memset(g, 0x00, sizeof(g));
    memset(s, 0x00, sizeof(s));
    memset(t, 0x00, sizeof(t));

    u = ecc_get_key_u(a, p, px, py, qx, qy, h, len);

    if(u < 0)
    {
        memset(rx, 0x00, sizeof(e));
        memset(ry, 0x00, sizeof(e));

        return -1;
    }

    big_num_mul_mod(h, h, p, c, len);
    big_num_add_mod(px, qx, p, d, len);

    big_num_sub_mod(c, d, p, rx, len);

    memset(c, 0x00, sizeof(c));
    memset(d, 0x00, sizeof(d));

    big_num_mul_mod(h, rx, p, e, len);
    big_num_add_mod(e, py, p, d, len);
    big_num_mul_mod(h, px, p, c, len);

    big_num_sub_mod(c, d, p, ry, len);

    return 0;
}

4.椭圆曲线上的减法

int ecc_get_key_ub(unsigned long *a, unsigned long *p, unsigned long *px, unsigned long *py, unsigned long *qx, unsigned long *qy, unsigned long *h, int len)
{
    unsigned long b[len];
    unsigned long c[len];
    unsigned long d[len];
    unsigned long e[len];
    unsigned long f[len];
    unsigned long g[len];
    unsigned long s[len];
    unsigned long t[len];
    int u = (!big_num_is_zero(qy, len) || !big_num_is_zero(py, len));
    int v = big_num_cmp(qx, px, len);

    memset(b, 0x00, sizeof(b));
    memset(c, 0x00, sizeof(c));
    memset(d, 0x00, sizeof(d));
    memset(e, 0x00, sizeof(e));
    memset(f, 0x00, sizeof(f));
    memset(g, 0x00, sizeof(g));
    memset(s, 0x00, sizeof(s));
    memset(t, 0x00, sizeof(t));

    if(u || v)
    {
        if(!v)
        {
            memcpy(h, f, 4*len);

            return -1;
        }

        if(!u)
        {
            memcpy(h, f, 4*len);

            return 0;
        }

        big_num_sub_mod(b, py, p, b, len);
        big_num_sub_mod(b, qy, p, b, len);
        big_num_sub_mod(qx, px, p, c, len);

        if(!big_num_is_one(c, len))
        {
            big_num_mod_inv(c, p, d, len);
        }
        else
        {
            memcpy(d, c, 4*len);
        }

        big_num_mul_mod(b, d, p, h, len);

        //printf("h[0]=[%d]\n", h[0]);
    }
    else
    {
        memset(g, 0x00, sizeof(g));
        g[len-1] = 3;
        big_num_mul_mod(px, px, p, d, len);
        big_num_mul_mod(d, g, p, f, len);
        big_num_add_mod(f, a, p, b, len);
        g[len-1] = 2;
        big_num_mul_mod(py, g, p, c, len);

        if(big_num_is_zero(c, len))
        {
            memcpy(h, f, 4*len);

            return -1;
        }

        if(big_num_is_zero(b, len))
        {
            memcpy(h, f, 4*len);

            return 0;
        }

        memset(d, 0x00, sizeof(d));

        if(!big_num_is_one(c, len))
        {
            big_num_mod_inv(c, p, d, len);
        }
        else
        {
            memcpy(d, c, 4*len);
        }

        big_num_mul_mod(b, d, p, h, len);
    }

    return 0;
}

int ecc_get_key_s(unsigned long *a, unsigned long *p, unsigned long *px, unsigned long *py, unsigned long *qx, unsigned long *qy, unsigned long *rx, unsigned long *ry, int len)
{
    unsigned long b[len];
    unsigned long c[len];
    unsigned long d[len];
    unsigned long e[len];
    unsigned long f[len];
    unsigned long g[len];
    unsigned long h[len];
    unsigned long s[len];
    unsigned long t[len];
    int u = 0;

    memset(b, 0x00, sizeof(b));
    memset(c, 0x00, sizeof(c));
    memset(d, 0x00, sizeof(d));
    memset(e, 0x00, sizeof(e));
    memset(f, 0x00, sizeof(f));
    memset(g, 0x00, sizeof(g));
    memset(s, 0x00, sizeof(s));
    memset(t, 0x00, sizeof(t));

    u = ecc_get_key_ub(a, p, px, py, qx, qy, h, len);

    if(u < 0)
    {
        memset(rx, 0x00, sizeof(e));
        memset(ry, 0x00, sizeof(e));

        return -1;
    }

    big_num_mul_mod(h, h, p, c, len);
    big_num_add_mod(px, qx, p, d, len);

    big_num_sub_mod(c, d, p, rx, len);

    big_num_mul_mod(h, rx, p, e, len);
    big_num_add_mod(e, py, p, c, len);
    big_num_mul_mod(h, px, p, d, len);

    big_num_sub_mod(d, c, p, ry, len);

    return 0;
}

5.椭圆曲线上的乘法

int big_num_to_bits(unsigned long *a, unsigned char *b, int len)
{
    unsigned long x;
    unsigned long w;
    int i = 0;
    int j = 0;

    for(i=0; i<len; i++)
    {
        x = a[i];
        //printf("x=[%d]\n", x);

        for(j=31; j>=0; j--)
        {
            w = ((x >> j) & 1);
            b[32*i+31-j] = w + '0';
            //printf("w=[%d], b[%d]=[%c]\n", w, 31-j, b[32*i+31-j]);
        }
    }

    return 0;
}

int ecc_get_pow_2_g(unsigned long *a, unsigned long *p, unsigned long *px, unsigned long *py, int n, unsigned long *rx, unsigned long *ry, int len)
{
    unsigned long b[2*len];
    unsigned long c[2*len];
    unsigned long d[2*len];
    int u = 0;
    int i = 0;

    memset(b, 0x00, sizeof(b));
    memset(c, 0x00, sizeof(c));
    memset(d, 0x00, sizeof(d));

    memcpy(b, px, 4*len);
    memcpy(b+len, py, 4*len);

    memcpy(d, b, 8*len);

    //printf("n=[%d]\n", n);

    for(i=0; i<n; i++)
    {
        //printf("pow: b[0]=[%d], b[1]=[%d]\n", b[0], b[1]);
        //printf("pow: d[0]=[%d], d[1]=[%d]\n", d[0], d[1]);
        u = ecc_get_key_r(a, p, b, b+len, d, d+len, c, c+len, len);
        //printf("pow: c[0]=[%d], c[1]=[%d]\n", c[0], c[1]);
        if(u) break;
        memcpy(b, c, 8*len);
        memcpy(d, c, 8*len);
        memset(c, 0x00, sizeof(c));
    }

    if(!u)
    {
        memcpy(rx, b, 4*len);
        memcpy(ry, b+len, 4*len);
    }

    return u;
}

int ecc_cons_mul(unsigned long *a, unsigned long *p, unsigned long *w, unsigned long *px, unsigned long *py, unsigned long *rx, unsigned long *ry, int len)
{
    unsigned long c[2*len];
    unsigned long d[2*len];
    unsigned long e[2*len];
    unsigned char b[32*len+1];
    int m = 32*len;
    int u = 0;
    int flag = 0;
    int i = 0;

    memset(b, 0x00, sizeof(b));
    memset(c, 0x00, sizeof(c));
    memset(d, 0x00, sizeof(d));
    memset(e, 0x00, sizeof(e));

    big_num_to_bits(w, b, len);

    //printf("b=[%s]\n", b);

    for(i=0; i<m; i++)
    {
        if(b[i] == '1')
        {
            //printf("i=[%d]\n", i);

            u = ecc_get_pow_2_g(a, p, px, py, m-1-i, c, c+len, len);

            //printf("c[0]=%d, c[1]=%d\n", c[0], c[1]);

            if(u)
            {
                memset(rx, 0x00, 4*len);
                memset(ry, 0x00, 4*len);

                return -1;
            }

            if(flag)
            {
                //printf("xq=[%d], yq=[%d]\n", xq, yq);
                u = ecc_get_key_r(a, p, d, d+len, c, c+len, e, e+len, len);

                if(u)
                {
                    memset(rx, 0x00, 4*len);
                    memset(ry, 0x00, 4*len);

                    return -1;
                }

                memcpy(d, e, 8*len);
                memset(e, 0x00, sizeof(e));
            }
            else
            {
                memcpy(d, c, 8*len);

                flag = 1;
            }
        }
    }

    memcpy(rx, d, 4*len);
    memcpy(ry, d+len, 4*len);

    return 0;
}

6.计算公钥

int ecc_get_pub(unsigned long *a, unsigned long *p, unsigned long *k, unsigned long *gx, unsigned long *gy, unsigned long *kx, unsigned long *ky, int len)
{
    return ecc_cons_mul(a, p, k, gx, gy, kx, ky, len);
}

7.加密算法

int ecc_cxt_enc(unsigned long *a, unsigned long *p, unsigned long *r, unsigned long *mx, unsigned long *my, unsigned long *kx, unsigned long *ky, unsigned long *gx, unsigned long *gy, unsigned long *sx, unsigned long *sy, unsigned long *tx, unsigned long *ty, int len)
{
    unsigned long ex[len];
    unsigned long ey[len];

    memset(ex, 0x00, sizeof(ex));
    memset(ey, 0x00, sizeof(ey));

    ecc_cons_mul(a, p, r, gx, gy, tx, ty, len);

    ecc_cons_mul(a, p, r, kx, ky, ex, ey, len);

    ecc_get_key_r(a, p, mx, my, ex, ey, sx, sy, len);

    return 0;
}

8.解密算法

int ecc_cxt_dec(unsigned long *a, unsigned long *p, unsigned long *k, unsigned long *sx, unsigned long *sy, unsigned long *tx, unsigned long *ty, unsigned long *mx, unsigned long *my, int len)
{
    unsigned long ex[len];
    unsigned long ey[len];

    memset(ex, 0x00, sizeof(ex));
    memset(ey, 0x00, sizeof(ey));

    ecc_cons_mul(a, p, k, tx, ty, ex, ey, len);

    ecc_get_key_s(a, p, sx, sy, ex, ey, mx, my, len);

    return 0;
}

9.主函数部分

int main()
{
    unsigned long b[12] = {0};
    unsigned long a = 0;
    unsigned long p = 199;
    unsigned long k = 119;
    unsigned long r = 100;
    int i = 0;

    b[0] = 2;
    b[1] = 2;

    b[4] = 67;
    b[5] = 217;

    ecc_get_pub(&a, &p, &k, b, b+1, b+2, b+3, 1);

    printf("K=(%d,%d)\n", *(b+2), *(b+3));

    ecc_cxt_enc(&a, &p, &r, b+4, b+5, b+2, b+3, b, b+1, b+6, b+7, b+8, b+9, 1);

    printf("C1=(%d,%d)\n", *(b+6), *(b+7));

    printf("C2=(%d,%d)\n", *(b+8), *(b+9));

    ecc_cxt_dec(&a, &p, &k, b+6, b+7, b+8, b+9, b+10, b+11, 1);

    printf("M=(%d,%d)\n", *(b+10), *(b+11));

    return 0;
}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,172评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,346评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,788评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,299评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,409评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,467评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,476评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,262评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,699评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,994评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,167评论 1赞 343
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,827评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,499评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,149评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,387评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,028评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,055评论 2赞 352

C语言实现椭圆曲线加密算法(大数版)

1.头文件部分

2.大数比较

3.大数基本运算

4.椭圆曲线上的加法

4.椭圆曲线上的减法

5.椭圆曲线上的乘法

6.计算公钥

7.加密算法

8.解密算法

9.主函数部分

推荐阅读更多精彩内容