英语原文共 9 页
基于Knapsack算法的椭圆加密解密
摘要
椭圆曲线密码提供了一种使用Diffie Hellman密钥交换算法在通信主机之间交换密钥的安全方法。还尝试了对文本和消息的加密和解密。本文介绍了ECC的实现，首先将消息转换为EC上的仿射点，然后在有限域GF（p）上对ECC加密消息应用背包算法。在ECC中，我们通常以称为Pm（x，y）的仿射点开始。这一点位于椭圆曲线上。在本文中，我们已经说明了加密/解密，其涉及构成消息的字符的ASCII值，然后使其受到背包算法的约束。我们将我们提出的算法与RSA算法进行比较，结果表明我们的算法由于高度复杂和复杂性而更好。尝试暴力攻击几乎是不可行的。此外，只有一个参数，即单独的背包矢量ai需要保密。相反，在RSA中，三个参数如模数n，其因子p和q需要保密。
关键词：离散对数，椭圆曲线密码（ECC），背包算法，公钥密码，RSA算法
1 引言
目前，使用公钥加密技术进行加密和数字签名的大多数产品和标准都使用RSA。最近，Elliptic Curve Cryptography开始挑战RSA。与RSA相比，ECC的主要吸引力在于它似乎可以为更小的密钥大小提供更好的安全性，从而减少处理开销。椭圆曲线密码学利用椭圆曲线，其中变量和系数都限于有限域的元素。在ECC中，我们通常以称为Pm（x，y）的仿射点开始。这些点可能是基点（G）本身或更接近基点的其他点。基点意味着它具有最小的x，y坐标，其满足EC。首先将消息中的字符转换为椭圆曲线的仿射点，将其用作Pm的乘数。也就是说，如果字符的ASCII值是A，那么我们确定P 0 m = A（Pm）。这是在加密过程中引入复杂性和复杂性的一步。新评估的P 0 m是EC上的一个点，通过应用ECC技术的加法和加倍策略确定。然后根据ECC算法，将P 0 m与kPB相加，其中k是随机选择的秘密整数，PB是用户B的公钥，以产生（P 0 m kPB）。这现在构成了加密版本消息的第二部分。另一部分，即kG，它是秘密整数和基点的乘积，构成第一部分。因此，加密的消息现在由两组坐标组成，即（kG，P 0 m kPB）。在本文中，我们分配了kG =（x1，y1）和（P 0 m kPB）=（x2，y2）。对确定加密所涉及的复杂性不满意，我们希望通过将Knapsack概念应用于加密版本来引入进一步的复杂性。这些严格的练习背后的整个想法是使解密完全不可能，即使基础点G，秘密整数k，仿射点Pm已知为隐窝分析师。现在要从加密版本中恢复信息，首先必须颠倒背包过程。然后我们通过在第一个元素（kG）上应用接收者的私钥（nB）来应用ECC的解密过程。从第二个元素中减去这个以恢复P 0 m。最后，通过使用离散对数概念，可以评估ASCII值，从而恢复明文。加密的内容可以存储在CD / DVD中或通过网络传输给受益人。这有望为入侵者和黑客提供最大的安全保障。
本文的独创性取决于以下几点。 1）将消息字符的ASCII值转换为EC上的仿射点。 2）背包算法在加密中引入了进一步的非线性。其他要点，例如应用ECC加密/解密，调用离散对数概念来恢复ASCII值已经存在并且有详细记录。就作者的知识而言，到目前为止似乎没有提出这样的尝试。为了比较基于背包的ECC加密/解密，使用另一种公钥算法，即RSA，来加密/解密相同的消息。与ECC过程不同，这对于消息的每个字符只产生一个整数。讨论和分析了两种方案的时间和空间影响。该论文证明，尽管ECC方法对时间和空间的要求更为严格，但由于其对任何暴力攻击的抵抗力，它都具有更好的优势。
这里引用了一些关于ECC应用的最新着作.Aydos等。 [1]讨论了在80 MHz，32位RAM微处理器上的GF（p）字段上实现ECC的结果。克里斯汀等人[8]概述了用于无线安全的ECC。它通过使用ECC而不是传统的RSA密码系统来关注无线环境中的性能优势。雷等人。 [3]解释了发生器的设计，它自动生成满足用户定义要求的定制ECC硬件.Cilardo等人。 [4]解释了ECC作为一个复杂的跨学科研究领域的工程，包括数学，计算机科学和电气工程等领域. McIvor等人。 [10]为GF（p）上的ECC引入了一种新颖的硬件架构。陈等人。 [2]提出了GF（p）上一般曲线的高性能EC加密过程。公钥加密的标准规范在[13]中定义。
将背包算法扩展到加密/解密的想法是由Diffie [5]推导出来的。 ECC概念由Williams Stallings [14]详细记录和说明。在[15]中，传感器网络中的访问控制用于授权和授予用户访问网络和传感器收集的数据的权限。本文描述了传感器网络中访问控制的公钥实现。凯文等人。 [6]，对UC Berkley用于无线传感器网络的Tiny OS操作系统实施的ECC进行了暴力攻击。该攻击利用密码系统使用的伪随机数生成器的短周期来生成私钥。文章Moon [11]提出了一种比现有的双重标量点乘法方法更有效和新颖的方法，并通过应用冗余重新编码来增加，这来自radix-4 Booths算法。 Hedabou [7]提出了一个关于Joye和Tymen技术安全性的启发式分析。论文李等人.[9]提出了3种算法，用于在更高特征有限域上定义的EC上执行标量乘法，例如OEA（最佳扩展域）。永良等[16]表明Aydos等人的协议容易受到任何攻击者的中间攻击，但不受内部攻击者的限制。他们提出了一种基于ECC的新型无线认证协议。
施等人[12]，研究在使用软件实现ECC时，某些架构参数（如字大小）是否会影响算法的选择。他们为低端处理器确定了一套用于ECC实现的算法。
2 提议的方法描述
对于qgt; 3，定义GF（p）上的椭圆曲线的Weiestrass方程如下：
其中x，y是GF（p）的元素，a，b是整数模p，满足
这里p被称为模块素数整数。 GF（p）上的椭圆曲线E由等式（1）和（2）定义的解（x，y）以及称为O的附加元素组成，其是EC在无穷远处的点。 该组点（x，y）被称为仿射坐标点表示。 基本的椭圆曲线运算是点加法和点加倍。 椭圆曲线加密基元[13]需要标量点乘法。 比如，给定EC上的点P（x，y），需要计算kP，其中k是正整数。 这是通过一系列的加倍和加法来实现的。假设k = 386，则需要以下操作序列（参见表1）。
让我们从P（xP，yP）开始。 为了确定2P，P加倍。 这应该是EC的一个关注点。 使用以下等式，它是点P处曲线的切线。
然后2P有仿射坐标xR，yR给出
现在确定3P，我们使用点P和2P的加法，处理2P = Q.这里P具有坐标（xP，yP）并且Q = 2P具有坐标（xQ，yQ）。 然后
因此，我们根据为k确定的一系列操作应用加倍和加法。 通过加倍或加法评估的每个点xR，yR是仿射点（椭圆曲线上的点）。 算法1中显示了所提出的算法。
我们根据为k确定的一系列操作应用加倍和加法。 通过加倍或加法评估的每个点xR，yR是仿射点（椭圆曲线上的点）。
算法1中显示了所提出的算法。
算法简介：
3我们提出的算法的实现细节
一旦知道了定义的EC，我们就可以选择一个叫做G的基点.G的[x，y]坐标满足方程y 2 = x 3 ax b。 基点具有满足EC的最小x，y值。
ECC方法要求我们选择随机整数k（k lt;p），这需要保密。 然后通过一系列添加和倍增来评估kG，如上所述。 出于讨论的目的，我们将源作为主机A，将目标称为主机B.我们选择主机B的私钥，称为nB。 k和nB可以由随机数生成器生成以提供可信度。 这将偏离主要讨论。 因此，我们对这两个参数做出了合适的假设。 B的公钥由以下评估：
假设A想要加密并将字符传送给B，他会做以下事情。假设主机A想要传输字符#39;S#39;。然后，字符“S”的ASCII值用于修改Pm，如下所示：P lsquo; m = SPm。我们说的是一个仿射点。选择的不同于基点G，以便保留它们的个体身份。 P lsquo; m是EC上的一个点。 P lsquo;m的坐标应适合EC。这种转换有两个目的。首先，将单值ASCII转换为EC的x，y坐标。其次，它完全被潜在的黑客所掩盖。这实际上是为了在根据ECC加密消息之前引入一定程度的复杂性。作为ECC的下一步，我们需要评估kPB，这里PB是用户B的公钥。确定该产品涉及一系列加倍和加法，具体取决于k的值。为了快速收敛结果，我们应该计划最佳的双打和增加数量。通过将P 0 m与kPB相加来导出加密消息，即P 0 m kPB。这产生一组x2，y2坐标。然后包含kG作为加密版本的第一个元素。 kG是另一组x1，y1坐标。因此，用于存储或传输的整个加密版本包括两组坐标，如下所示：
到目前为止，已经通过应用ECC方法对修改的明文进行了加密。 结合Pm修改明文是本文的一项新创新。 然而，通过提出背包程序的扩展，作者更进一步，使加密更加安全。 据我们所知，这可能是将Knapsack算法应用于ECC加密消息的第一次尝试。 这引入了彻底的扩散和混乱，以打破任何暴力攻击的企图。
背包需要我们生成一系列称为ai的向量。 有几种生成这些向量的方法。 为了便于说明，我们将第一个值作为1，后续值作为n Say的倍数
这里，n可以假设为小于10的某个随机整数，或者计算为涉及p和k整数。 这里p是模运算中使用的素数，k是秘密整数，m是二进制位串的长度。
接下来让我们探讨加密消息的坐标如何受到背包过程的影响。 比方说，xi是坐标点之一，可以用二进制形式表示为：
根据背包算法，我们计算累积和
在最终的加密版本中，坐标xi被其等价的S [x1]代替。 类似地，其他坐标如y1，x2，y2由背包算法转换，因此加密的消息现在应表示为
回想一下，这两对整数只代表一条消息中的一个字符。 根据消息中的字符数，将有尽可能多的这样的整数对。 这可以存储在CD / DVD等档案设备中，也可以通过网络传输给受益人。
收件人B具有用于反转背包程序和恢复坐标的位模式的所有相关信息。 例如，B知道ai系列，他自己的秘密密钥nB，EC的基点G，a，b，p值。 B接收加密消息，Cm =（（S [x1]，S [y1]），（S [x2]，S [y2]））。 我们举一个例子，讨论如何逆转背包过程。 考虑
这是x1的背包表示。 x1值以迭代方式恢复，如下所示：
如果该值为正，即S [x1] -n mgt; 0，则在第（m）位置分配二进制位1。 当前值为S [x1] = S [x1] - n m。 但是，如果该值为负，则分配0位并且S [x1]保持不变。
现在从当前S [x1]中减去n m-1。 根据是 ve还是-ve，在相关位位置指定1或0。 继续此减法，直到ai系列耗尽。 这将恢复x1的二进制位模式。 对y1，x2和y2重复这些过程。 回想一下，kG由x1，y1表示，并且P 0 m kPB由x2，y2表示。 为了从P lsquo;m kPB中拉出P lsquo;m，B应用他的秘密密钥nB并将kG相乘，这样，
从Prsquo;m kPB中减去此值，得到P 0 m，如下所示：
该减法是另一个涉及加倍和加法的ECC过程。 但唯一的区别是负面术语的y坐标前面会有一个减号。 通过这种微妙的变化，确定斜率的表达式，xR，yR的新值是相同的。 无论y在哪里，它都被替换为-y。 这将产生P 0 m。
使用离散对数概念，可以如下检索“S”的ASCII值，Prsquo;m = S Pm。
4提出的算法的实施
椭圆曲线是：
基点G被选择为（0,5）。 基点意味着它具有满足EC的最小x，y坐标。 Pm是另一个仿射点，它是从针对给定EC评估的一系列仿射点中挑选出来的。 我们可以为Pm保留G本身。 然而，出于个体身份的目的，我们选择Pm与G不同。让Pm =（1,316）。 Pm的选择本身就是一项涉及在给定的EC上细致地应用ECC过程的练习。 此外，我们需要生成秘密整数k和收件人B的私钥nB。我们可以使用一系列随机数生成器。 但那将是思想的主要思路。 因此，我们假设k = 225，并且nB = 277。
明文是“S”，其ASCII值为83.因此，
消息的加密版本是：（（99,253），（51,58）），其中x1 = 99，y1 = 253，x2 = 51，y2 = 58。
使用ai向量应用背包算法
所以
相似的
因此，发送的消息是（18756,82031），（3756,656）。 x99的位模式恢复如下：
因此，x99 = 1100011（从下往上阅读）。 类似地，通过应用反向背包算法来恢复其他坐标。 因此，我们能够恢复加密版本
从这个Pm应该使用B的私钥nB检索。
现在应用离散对数概念来获得“S”的ASCII值。
因此，S = 83.因此我们检索字符“S”。 其余字符的详细工作见附录A.
5讨论和结论
明文消息“SAVE”用于实现本文提出的算法。消息中的每个字符都由其ASCII值表示。通过使用称为Pm的起始点，将这些ASCII值中的每一个转换为EC上的仿射点。可以选择该Pm与基点G不同。通过使用仿射点来转换明文ASCII值是这项工作的贡献之一。这种转换的目的是双重的。首先，将字符的单个数字ASCII整数转换为一组坐标以适合EC。其次，变换在角色中引入了非线性，从而完全掩盖了它的身份。消息的这种转换
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
