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