ECC密码的加密和解密（附带代码实现）

一、简要介绍

ECC，全称Elliptic Curve Cryptography，是椭圆曲线密码学。这是一种公钥加密技术，其安全性基于椭圆曲线离散对数问题，被广泛应用于信息安全领域。

ECC的主要优势在于，相较于RSA和DSA等其他传统的公钥密码体系，它能够在提供相同安全级别的情况下，使用更短的密钥，从而减少计算量和存储空间的需求。例如，一个256位的ECC密钥提供的安全性可以与3072位的RSA密钥或DSA密钥相媲美。

ECC的主要应用领域包括SSL安全证书、安全电子邮件、移动设备安全、物联网设备安全等。随着计算能力的提高和对信息安全需求的增加，ECC的应用将越来越广泛。

但是，ECC并不是万能的。它的一些缺点包括计算复杂度较高，需要专门的数学知识来理解和实现，以及潜在的专利问题等。因此，在选择使用ECC之前，需要根据具体的应用场景和需求进行权衡。

二、ECC的困难点

ECC（椭圆曲线密码学）虽然在很多方面具有优越性，但应用和实现上也确实存在一些困难点：

1. 高度的数学复杂性：ECC基于椭圆曲线上的离散对数问题，这需要深入理解抽象代数和数论等高级数学概念，对于没有相关背景的人来说，理解和实现ECC可能会比较困难。

2. 实施难度：正确和安全地实施ECC需要高度的专业知识。如果在实施过程中出现错误，可能会导致安全性大大降低，甚至完全丧失。

3. 专利问题：虽然大部分ECC技术都是公开的，但仍有一部分被专利保护。在商业应用中使用这些专利技术可能需要支付额外的费用。

4. 兼容性问题：虽然ECC逐渐得到广泛接受，但仍有很多系统和设备不支持ECC。这可能需要在设备和系统之间进行额外的兼容性处理。

5. 密钥管理和存储：相比于其他加密技术，ECC的密钥较短，但仍需要进行安全的密钥管理和存储。如果密钥管理不当，可能会导致密钥泄露，从而破坏整个系统的安全性。

6. 随机数生成：ECC的安全性部分依赖于随机数的生成。如果随机数生成不够随机，可能会导致安全性降低。因此，需要使用高质量的随机数生成器。

因此，尽管ECC在很多方面都优于其他类型的公钥加密算法，但在实际应用中还需要考虑到以上的一些问题和挑战。

三、一些重点部分讲解

1. 加密密钥的生成:

//选取私钥
int ka = int(CR[0]) % (n - 1) + 1;//选取使用的密钥
point pa = cal(generator, ka, a, p);//计算公钥
cout << "私钥：" << ka << endl;
cout << "公钥：（" << pa.x << "," << pa.y << "）" << endl;

这部分代码生成了椭圆曲线密码的私钥和公钥。私钥是随机生成的，而公钥是通过椭圆曲线的生成元和私钥的运算得到的。

2. 明文的加密:

//m嵌入到椭圆曲线
int t = rand() % num; //选择映射点
point Pt = P[t];
point P2 = cal(pa, k, a, p);
point Pm = add(Pt, P2, a, p);
cout << endl << "要发送的密文：" << endl;
cout << "kG=(" << C1.x << "," << C1.y << "),M+KY=(" << Pm.x << "," << Pm.y << ")";

这部分代码将明文嵌入到椭圆曲线上的一个点，然后通过椭圆曲线的运算进行加密。

3. 密文的解密:

//解密
point temp, temp1;
int m;
temp = cal(C1, ka, a, p);
temp.y = 0 - temp.y;
temp1 = add(Pm, temp, a, p);//求解Pt 
printf("\n解密结果：\n");
for (int i = 0; i < strlen(SE); i++)
{
    m = (C[i] - temp1.y) / temp1.x;
    printf("%c", char(m));//输出密文 
}

这部分代码通过椭圆曲线的运算将密文解密为明文。

四、代码实现

#include<iostream>

#include<math.h>

#include<time.h>

#include<stdlib.h>

#include<cstring>

using namespace std;

class point

{

public:

   int x;

   int y;

};

point P[100];

int num = 0;

//取模

int my_mod(int a, int p)

{

   //注意负数情况要加上一个p

   int i;

   i = a / p;

   int re = a - i * p;

   if (re >= 0)

   {

      return re;

   }

   else

   {

      return re + p;

   }

}

//幂次运算，含模运算，防止溢出

int my_pow(int a, int m, int p)

{

   int result = 1;

   for (int i = 0; i < m; i++)

   {

      result = (result * a) % p;

   }

   return result;

}

//用于求y,并判断平方根是否为整数

int my_sqrt(int s)

{

   int t;

   t = (int)sqrt(s);

   if (t * t == s)

   {

      return t;

   }

   else {

      return -1;

   }

}

void all_points(int a, int b, int p)

{

   for (int i = 0; i < p; i++)

   {

      int s = i * i * i + a * i + b;

      while (s < 0)

      {

         s += p;

      }

      s = my_mod(s, p);

      //判断是否为平方剩余

      //p为23，是奇素数

      //Euler准则

      int re = my_pow(s, (p - 1) / 2, p);

      if (re == 1)

      {

         //求y

         int n = 1, y;

         int f = my_sqrt(s);

         if (f != -1)

         {

            y = f;

         }

         else

         {

            for (; n <= p - 1;)

            {

               s = s + n * p;

               f = my_sqrt(s);

               if (f != -1)

               {

                  y = f;

                  break;

               }

               n++;

            }

         }

         y = my_mod(y, p);

         P[num].x = i;

         P[num].y = y;

         num++;

         if (y != 0)

         {

            P[num].x = i;

            P[num].y = (p - y) % p;

            num++;

         }

      }

   }

}

void show()

{

   for (int i = 0; i < num; i++)

   {

      cout << P[i].x << " " << P[i].y << endl;

   }

}

//扩展欧几里得法，递归法

int extend(int a, int b, int& x, int& y)

{

   if (b == 0)

   {

      x = 1;

      y = 0;

      return a;

   }

   int r = extend(b, a % b, x, y);

   int t = x;

   x = y;

   y = t - a / b * y;

   return r;

}

//借助递归扩展欧几里得求逆

int inv(int a, int b)

{

   int x, y;

   int r = extend(a, b, x, y);

   if (r != 1)

   {

      return 0;

   }

   x = x % b;

   if (x < 0)

   {

      x = x + b;

   }

   return x;

}

//两点的加法运算

point add(point p1, point p2, int a, int p)

{

   long t; int flag = 0;

   int x1 = p1.x; int y1 = p1.y;

   int x2 = p2.x; int y2 = p2.y;

   int tx, ty; int x3, y3;

   if ((x2 == x1) && (y2 == y1))

   {

      //相同点

      if (y1 == 0)

      {

         flag = 1;

      }

      else

      {

         t = (3 * x1 * x1 + a) * inv(2 * y1, p) % p;

      }

   }

   else

   {

      //不同点相加

      ty = y2 - y1;

      tx = x2 - x1;

      while (tx < 0)

      {

         tx = tx + p;

      }

      while (ty < 0)

      {

         ty = ty + p;

      }

      if (tx == 0 && ty != 0)

      {

         flag = 1;

      }

      else

      {

         //点不相等

         t = ty * inv(tx, p) % p;

      }

   }

   if (flag == 1)

   {

      //无限点

      p2.x = -1;

      p2.y = -1;

   }

   else

   {

      x3 = (t * t - x1 - x2) % p;

      y3 = (t * (x1 - x3) - y1) % p;

      while (x3 < 0)

      {

         x3 += p;

      }

      while (y3 < 0)

      {

         y3 += p;

      }

      p2.x = x3;

      p2.y = y3;

   }

   return p2;

}

//随机选取一个生成元并计算阶

int jie(point& pp, int a, int p)

{

   int ii = rand() % num;

   point P0 = P[ii];

   point p1, p2;

   int number = 1;

   p1.x = P0.x; p2.x = P0.x;

   p1.y = P0.y; p2.y = P0.y;

   while (true)

   {

      p2 = add(p1, p2, a, p);

      if (p2.x == -1 && p2.y == -1)

      {

         break;

      }

      number++;

      if (p2.x == p1.x)

      {

         break;

      }

   }

   pp.x = p1.x;

   pp.y = p1.y;

   int n = ++number;

   return n;

}

//素数判断

bool judge(int num)

{

   bool ret = true;

   int ubound = sqrt(num) + 1;

   for (int i = 2; i < ubound; i++)

   {

      if (num % i == 0)

      {

         ret = false;

         break;

      }

   }

   return ret;

}

//计算kG

point cal(point G, int k, int a, int p)

{

   point temp = G;

   for (int i = 0; i < k - 1; i++)

   {

      temp = add(temp, G, a, p);

   }

   return temp;

}

int main()

{

   srand(time(NULL));

   int a, b, p;

   point generator; int n;

   char SE[10];

   char CR[10];

   cout << "请输入椭圆曲线群（a,b,p）：";

   cin >> a >> b >> p;

   cout << "请输入明文：";

   cin >> SE;

   cout << "请输入密钥：";

   cin >> CR;

   //计算所有点

   all_points(a, b, p);

   //选取生成元，直到阶为素数

   do

   {

      n = jie(generator, a, p);

   } while (judge(n) == false);

   cout << endl << "选取生成元（" << generator.x << "," << generator.y << "）" << endl;

   //选取私钥

   int ka = int(CR[0]) % (n - 1) + 1;//选取使用的密钥

   point pa = cal(generator, ka, a, p);//计算公钥

   cout << "私钥：" << ka << endl;

   cout << "公钥：（" << pa.x << "," << pa.y << "）" << endl;

   //加密

   int k = 0;//随机数k

   k = rand() % (n - 2) + 1;

   point C1 = cal(generator, k, a, p);//计算C1

   //m嵌入到椭圆曲线

   int t = rand() % num; //选择映射点

   point Pt = P[t];

   point P2 = cal(pa, k, a, p);

   point Pm = add(Pt, P2, a, p);

   cout << endl << "要发送的密文：" << endl;

   cout << "kG=(" << C1.x << "," << C1.y << "),M+KY=(" << Pm.x << "," << Pm.y << ")";

   int C[100];

   cout << "C = { ("<< C1.x << "," << C1.y << "),(" << Pm.x << "," << Pm.y << ")}" << endl;;

   for (int i = 0; i < strlen(SE); i++)

   {

      C[i] = int(SE[i]) * Pt.x + Pt.y;//选取要加密的明文

   }

  

   //解密

   point temp, temp1;

   int m;

   temp = cal(C1, ka, a, p);

   temp.y = 0 - temp.y;

   temp1 = add(Pm, temp, a, p);//求解Pt

   printf("\n解密结果：\n");

   for (int i = 0; i < strlen(SE); i++)

   {

      m = (C[i] - temp1.y) / temp1.x;

      printf("%c", char(m));//输出密文

   }

   printf("\n");

   return 0;

}

五、总结

在本实验中，我们探索了椭圆曲线密码学的基本概念以及其在信息安全领域的应用。椭圆曲线密码学是一种基于椭圆曲线理论的公钥加密技术，它可以提供与传统RSA等非对称密码技术相同的安全性，但所需的关键长度却大大缩研，从而在很多情况下能更有效地提供安全保障。

在实验过程中，我们首先以指定的椭圆曲线群参数（a,b,p）为基础，计算出所有可能的点，然后选取一个生成元，并确保其阶为素数。通过将字符密钥转化为数字形式并计算其对应的公钥，我们进一步加深了对私钥和公钥在加密过程中作用的理解。

在实际的加密过程中，我们首先随机选择一个整数k，然后计算出相应的C1。然后，我们将明文嵌入到椭圆曲线中，并计算出其加密后的密文。这个过程中，我们熟悉了椭圆曲线上点的加法运算规则和倍点运算规则，更加深入地理解了椭圆曲线加密算法的工作原理。

最后，我们进行了解密操作，通过计算和比较，验证了我们的解密算法是否能正确地恢复出原始的明文。

总体来说，这次实验使我们对椭圆曲线密码学有了更深入的理解，我们掌握了如何使用椭圆曲线进行加密和解密，以及如何选择和计算私钥和公钥。这些知识不仅对我们理解现代密码学有着重要的意义，同时也为我们在未来的学习和研究中打下了坚实的基础。