椭圆曲线密码学的简单C++实现

• 下载源代码 - 6.62 KB

引言

椭圆曲线密码学（ECC）是一种令人兴奋且有前途的数据加密方法，它以比RSA等传统加密方法小得多的密钥长度实现了相同甚至更好的安全性。椭圆曲线本身并非高深莫测，但大量的文章和数学背景资料让普通读者难以真正理解该方案如何实现和使用，这成为了一个“非平凡的练习”。唉，我已不再靠编码为生，因此我总是寻找简洁、切题的实现，用代码确切地展示某事是如何工作的。

我希望您随本文下载的源代码文件能够提供这样一种简洁易懂的材料来源，以揭开（注意这里的“E”和“C”大写！）椭圆曲线如何在C++中编码，并用于加密和解密永恒的Alice和Bob之间的消息。

背景

是的，有很多背景知识。首先，您应该了解椭圆曲线的基本原理，我发现没有比这里更好的学习场所了：Certicom的EC教程。它解释了EC背后的数学原理，以及在有限域上使用EC的重要性，即在模某个整数（通常选择一个素数，以便由乘法或加法生成的整数序列的周期“足够长”）的整数上。

其次，您应该花些时间相对深入地思考有限域到底是如何工作的。例如，在有限域中找到一个数的逆元并不那么直接（除非您以此为生）。由于这相当基础且在代码中使用了大量，我将在此概述。

给定一个有限域F_p，其中p是一个素数（或者更具体地说，一个素数幂），并且a、b是F_p的元素，a是b的乘法逆元，当且仅当

(a * b) mod p == 1

这很有意义，因为（用“俗话”说）如果a*b == 1，那么a就是b的逆元，即a = 1/b。

要找到a（给定b和p），需要使用“最大公约数”（GCD），它返回小于（或等于）a（或）和b的最大整数，该整数可以整除a和b。

如果这个整数是1，那么a和b就是互质的，因为只有1可以整除它们。现在，给定a和b以及p，如果b（我们要找其逆元）和p互质，那么我们就可以找到一个逆元。这也很有道理，因为如果b和p互质，您总可以写成

b*u + p*v == 1

因为GCD(b,p) == 1，仅当b和p具有这种关系时。现在，如果p是一个实际的素数，那么b总是有一个模p的逆元...

鉴于几乎所有现代加密方案或多或少都使用素数和模运算，学习基础知识是一件好事。

使用代码

我希望代码本身就具有很强的解释性。它是在DevCpp、MinGW和GCC 3.4.2版本下开发的，但在其他编译器上未经测试。虽然我喜欢我的C++，但我并没有过度使用可能导致“ANSI合规性”问题的特性，但如果您发现任何问题，请告诉我！

要开始，请查看main.cpp底部的int main(...。FiniteFieldElement.hpp是使用标准整数实现模运算的头文件。警告：我不得不处理负数的模数问题，我假设（由于ANSI标准没有明确说明）在其他编译器上可能会有所不同。请注意，如果某些地方看起来不对，这可能是原因！

另外：这是使用标准的机器整数实现的，没有特殊的“大整数”支持。

示例加密的是Alice的消息，即“1972”，所以如果一切正常运行，您应该会看到Bob解密的消息就是这个。

关注点

实现这个非常有趣，特别是当它成功工作的时候。我鼓励任何人扩展椭圆曲线的实现，以确保这些强大数学实体的理解和知识能够尽可能广泛地传播。安全永远不够安全。

历史

第一个版本是在圣诞节期间在法国南部（阳光不那么充足的地方）编写的。