【密码学】miracl大数库学习相关

45 阅读 0 评论 30 点赞

我是靠谱客的博主开放店员，最近开发中收集的这篇文章主要介绍【密码学】miracl大数库学习相关，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最近在做全国高校密码学的竞赛。各种算法的实现都需要用到大整数的相关运算。我们知道，C/C++的long long范围大概能到9E18，gcc支持的__int128大概能到1E38，能搞定一部分数据的运算了，但是真正的大数还是搞不掂。而python和Java虽然都有大整数库和密码学的库，但用Python开发有点担心效率问题，而Java自己还不是完全习惯（经历过后面的事情我才知道选择Java和Python的模块其实可能是更聪明的选择。Coding的节省的时间有时更宝贵）
我曾经实现过自己的高精度模板 https://blog.csdn.net/BUAA_Alchemist/article/details/84949216 ，以long long为基础压了9位数，高精度除法等等也是自己辛苦优化过的，各种运算符和各种情况基本都考虑到了。用于ICPC竞赛是没有任何问题了。然而解密的程序往往是需要运行昼夜的，这样的话自己模板的劣势就显现出来了。
我开始尝试寻找C++的第三方库。最知名的是gmp，它是gnu项目的一部分，更新和维护有有效的保证。因为gmp无法在vs的编译器下工作，所以我希望利用MSYS2，在Windows下能将它和Dev C++相整合。但是经历一系列操作之后，由于Dev C++自带gcc版本问题，库的link，没有研究出来解决方法（以后这种情况还是直接开Linux算了QwQ，谁叫我就是喜欢win呢）。无奈之下，我选择了另一个知名的大数库miracl，它支持大整数big和高精度浮点数flash，而且挺说提供了密码学问题包括椭圆曲线离散对数相关的一些函数支持，正好和我的课题不谋而合，而缺点是主要代码历史悠久，似乎缺乏很好的维护。
配置入vs2017的过程：首先从Github上下载miracl这个项目，解压之后我们可以看到里面文件vc2005.txt，再在lib文件夹中找到ms64doit.bat。严格按照前者的叙述步骤建立静态链接库的miracl工程，但因为我们是64位环境，所以导入的文件要看ms64doit.bat的内容，尤其是注意有两个文件需要用64位的版本替换掉。生成解决方案之后，工程下x64debug目录下会有两个文件miracl.lib，miracl.pdb，前者就是我们需要的链接库文件，因为是vs环境下生成的，所以这个lib文件也只能在vs下起作用。然后我们再按照vc2005.txt中叙述建立brent工程进行测试。如果没出什么差错，那么这个工程就能实现大整数质因数分解的功能
给我很大帮助的一篇博文：https://blog.csdn.net/leapoo/article/details/82786804 虽然我自己有一些差别，但总体差不多。
下载包的sourse源代码文件夹中还提供了大量的例子帮助学习，另外还有manual.doc帮助文档，记录了各种函数和定义，讲解了库内部的原理。另外，要注意miracl对C和对C++的文件包含方式有所不同，注意自己的代码是.c还是.cpp以及相应的头文件怎么写。这些具体也参看帮助文档。
直观感觉它的使用不是很自由，但是这么知名，效率和功能肯定不是盖的。以后我会尝试进行学习和测试。今天先写到这里。

补充：装这个包不是一件容易的事情，你成功了并不代表别人成功，大佬BZB按着差不多的方法不知道为什么失败了好多遍QwQ
一件重要的事情，C/C++编译生成lib文件时，一定要记住把优化开到最大，并且选取Release模式！否则包的速度会非常慢！一开始我发觉自己的包是python代码的十倍慢，很惊讶，然后在github上傻傻地咨询了开发者，感谢他百忙之中的回复：https://github.com/miracl/MIRACL/issues/70 大家也可以仔细看看。
重新编译完包之后，我就Big的运算作了效率比较，坦白而言，它比python自带的大数仍旧要慢3至4倍，根据miracl开发者的说法，python是用汇编严格优化过的语言，这样的效率差距可以理解。比我自己写的高精度要快2到3倍（我的高精度看来也不错）。当然，这个包重要的不只有大数库，更有一系列密码学相关的函数，用起来很是方便。
另外值得注意的是，miracl是一个c语言的库，c++的使用方面作者只给了一个不太彻底的封装，具体可以打开big.cpp zzn.cpp等文件查看，可以看到一堆友元函数的实现。有部分运算没有经过封装，需要自己进行封装或者直接调用。比如big的乘法，在整数比较大的时候fft_mult更快速，但是c++类Big的乘法重载只有multiply。这是使用的时候需要注意的地方。
今天先写到这里。