椭圆曲线密码学的基本解释？

#1 楼

有一些广泛使用的密码算法，它们需要一个有限的循环组（具有满足一些特征的组成定律的一组有限元素），例如DSA或Diffie-Hellman。组必须具有以下特征：


组元素必须可以用相对较少的内存表示。
组的大小必须是已知的并且是质数（或倍数）大小合适的已知素数（对于传统的“ 80位安全性”安全级别，至少为160位）。
组定律必须易于计算。
它应该很难（即计算上不可行，至少要达到目标安全级别）才能解决组中的离散对数。

DSA，DH，ElGamal ...主要定义在以大为模的非零整数组中素数p，具有模乘法作为群律。只要p足够大，就可以达到我们寻找的特性。至少1024位（这是在这样的组中很难实现的离散对数的最小大小）。

椭圆曲线是另一种类型的组，适用于基于组的密码算法。椭圆曲线定义为：



一个有限域，通常由对某些质数p取模的整数组成（也可以使用其他域）。 ，通常$ y ^ 2 = x ^ 3 + ax + b $，其中$ a $和$ b $是有限域中的常数。

曲线是值对的集合$与等式匹配的（x，y）$，以及称为“无穷大点”的常规额外元素。由于椭圆曲线最初来自图形表示形式（当字段包含实数$ \ mathbb {R} $时），因此曲线元素称为“点”，两个值$ x $和$ y $是它们的“坐标” “。

然后，我们定义一个组定律，称为点加法，并用“ $ + $”符号表示。该定义看起来非常人为，涉及到跟踪一条线并计算该线与曲线的交点的所有工作；但最重要的是，它具有群律所要求的特征，并且易于计算（有几种方法；作为粗略的近似，它在基本字段中的成本约为10倍）。曲线阶数（曲线上的点数）接近$ p $（有限域的大小）：对于某些整数$ t $，曲线阶数等于$ p + 1-t $，使得$ | t | \ leq 2 \ sqrt {p} $。

与传统的乘法群以大素数为模的比较，密码算法的椭圆曲线变体具有以下实用功能：



它们又小又快。除了适用于每个组的通用算法以外，没有已知的有效的椭圆曲线离散对数求解算法。因此，只要$ p $接近160位，我们就会获得适当的安全性。计算组法则需要进行十次现场操作，但是要小6倍。由于有限域中的乘法运算具有二次方代价，因此最终会产生明显的加速效果。

创建新曲线并不容易。使用基本PC生成新的主要质素仅需不到一秒钟的时间，但是制作新曲线的成本要高得多（困难的部分是弄清楚曲线的顺序）。由于将同一组用于几个不同的密钥对不存在安全性问题，因此对于椭圆曲线，习惯上依赖于已创建的少数标准曲线，以使其顺序适当（较大的素数或足够大的原始值的倍数）；请参阅FIPS 186-3。因此，针对这些特定曲线对实现进行了专门化和优化，这又大大加快了处理速度。

椭圆曲线可用于分解整数。 Lenstra的椭圆曲线分解方法可以在不使用椭圆曲线的情况下找到大整数中的某些因子。这不是最广为人知的分解算法，除了要在一个大的非素数整数中查找中等大小的因子时。

一些椭圆曲线允许配对。配对是一种双线性运算，可以将两组中的元素链接到第三组中的元素。密码学配对要求所有三个组都“合适”（尤其是难解的离散对数）。配对是一个活跃的研究主题，因为配对可用于与三个参与者（例如，在电子现金系统中，与买家，卖方和银行一起都在数学上涉及系统的参与者）实施协议。唯一已知的密码学实用配对使用一些特殊的椭圆曲线。

椭圆曲线通常被认为是下一代密码算法，以取代RSA。 EC计算的性能是这些算法的主要兴趣，尤其是在小型嵌入式系统（例如智能卡）（尤其是二进制字段上的Koblitz曲线）上；最大的问题是使用基于组的算法的公钥操作有点慢（RSA签名验证或非对称加密相对于签名生成和非对称解密分别非常快，而基于组的类似操作算法就快了）。另外，涉及的数学要比RSA难一些，并且已经有了专利，因此实施者要谨慎一些。但是椭圆曲线越来越普遍。

#2 楼

从前，在一个遥远的土地上，住着两个名叫尼尔·科布利茨（Neal Koblitz）和维克多·米勒（Victor S. Miller）的人。他们彼此之间并不了解，但是在1985年，他们都建议在有限域上使用椭圆曲线来加密/解密数据。有限域。大部分来自DW建议的Wiki链接

椭圆曲线密码术（ECC）是基于有限域上椭圆曲线的代数结构的公钥密码方法。

公钥密码学基于某些数学问题的难处理性。早期的公钥系统（例如RSA算法）是安全的，前提是很难分解由两个或多个大素数组成的大整数。

对于基于椭圆曲线的协议，假设找到相对于公知基点的随机椭圆曲线元素的离散对数是不可行的。椭圆曲线的大小决定了问题的难度。可以相信，使用椭圆模数组要小得多的基于RSA的系统具有的大模量，可以达到相同的安全性。使用小组减少存储和传输要求。

对于当前的加密目的，椭圆曲线是平面曲线，由满足等式的点组成

$ y ^ 2 = x ^ 3 + ax + b $，

以及无穷大点。 （此处的坐标是从特性不等于2或3的固定有限域中选择的，否则曲线方程会更加复杂。）此集合与椭圆群理论的群运算一起构成一个Abelian群，以无穷大的点作为标识元素。该组的结构继承自基础代数变种的除数组。

它的工作方式取决于您对其应用的加密方案。例如，可以将其应用于Diffie-Hellman密钥交换，该交换通常称为椭圆曲线Diffie-Hellman（ECDH）密钥协商协议。

假设Alice想要建立共享的与Bob一起使用，但第三方可能窃听了唯一可用的频道。最初，域参数（即素数情况下的$（p，a，b，G，n，h）$或$（m，f（x），a，b，G，n，h）$二进制情况）必须达成共识。而且，每一方都必须有一个适合椭圆曲线密码的密钥对，包括一对私钥d（在区间[[n，1-1] $中随机选择的整数）和一个公钥$ Q $（其中$ Q = dG $）。假设Alice的密钥对为$（d_A，Q_A）$，而Bob的密钥对为$（d_B，Q_B）$。每一方都必须具有另一方的公钥（必须进行交换）。

爱丽丝计算$（x_k，y_k）= d_AQ_B $。鲍勃计算$ k = d_BQ_A $。共享密钥为$ x_k $（该点的$ x $坐标）。

双方计算的数字相等，因为$ d_AQ_B = d_Ad_BG = d_Bd_AG = d_BQ_A $。

该协议是安全的，因为没有公开任何信息（除了不是秘密的公共密钥），任何一方都不能导出对方的私钥，除非它能解决椭圆曲线离散对数问题。 >

#3 楼

我建议您先阅读Wikipedia中的椭圆曲线密码学说明，然后让我们知道您想知道的内容：您不了解什么？您想了解的内容没有涵盖什么吗？

单句版本是椭圆曲线加密是一种公钥加密形式，比大多数竞争对手都更有效（例如RSA）。

对于您已经知道的每个公钥密码系统，都有基于椭圆曲线密码学（ECC）的替代方法。 ECC方案可能更快。因此，ECC特别适用于性能非常重要的嵌入式设备和其他系统。另一方面，ECC比其他一些知名的替代方案要新，并且在某些椭圆曲线密码学周围有一些专利雷区，因此ECC的部署程度不如传统的RSA / DSA / El Gamal-但是ECC在某些系统中被广泛使用。

#4 楼

我想添加一些非常方便的参考资料。

首先，有一个广受赞誉的椭圆曲线加密博客（不是我的，今天没有自我插入功能）。但是我链接到的确切页面恰好有很多参考文献，供您学习加密技术，尤其是椭圆曲线密码学（包括我目前的研究生顾问写的书，我还没有真正阅读过）。

但是其中之一是Smart的密码学，其中有一些很好的快速概述部分，可以在此处免费获得（并且合法（顺便说一句-由作者本人分发））。