这个库叫做CiperLib,是我暑假在密码学实验室作的作品。比较工程化的东西,不过比较实用,所以就公布了。
下面是他的简介,我直接从他的说明文档中复制了,如果你完全知道他的作用,那么直接去文章末尾的链接下载。
CipherLib是一个使用C++和汇编代码实现的用于多精度大整数运算和密码学领域素域基本运算的函数库。由陈士凯(CSK)开发。
这个函数库实现的操作有:
- 支持任意精度的大整数:精度可以通过代码设定,支持符号数
- 对大整数的四则运算和求模运算,以及2进制化的移位操作
- 使用类将大整数加以封装,支持直接用传统运算符进行大整数的运算代码编写
- 支持从文本串和系统内置整型数据中读取大整数,支持将大整数输出为2进制、8进制、10进制和16进制文本串
- 实现了Marsaglia & Zaman的长周期随机数(本机支持的整型格式)
- 支持模加、模乘、模幂计算
- 支持Rabin-Miller方法的素性验证
- 支持大素数产生
简单的说可以利用这个库实现一些高精度计算和密码算法,比如RSA。
项目 | 说明 |
运行环境 | 32位x86指令系统下的windows环境 |
开发环境 | VC++ 2005版本 |
是否多线程安全 | 否 |
函数库形式 | 静态链接库或者直接嵌入代码 |
第三方库依赖 | 需要C运行库 |
Benchmark
下面是我写的对于CipherLib和mircal的一个运行效率比较(不过不是很科学,但是基本可以说明问题):
对于乘法的实测情况
对于加法的实测情况
对于减法的实测情况
对于除法的实测情况
对于求大素数的实测情况
对于素域运算,使用了产生一个大素数的运算作为衡量指标,因为其中需要进行素性验证和模乘和模幂运算。本函数库效率较低,原因是没有针对素性验证是的模幂运算单独进行优化。
我用于求模幂的算法是Koch提出的Sliding Window法。但是对于求素性验证来说不是最优的。
使用范例
下面是用本函数库求解1000!的代码,从代码风格上可以看出他的易用性,具体代码和使用办法见文章末尾给出的文件中的操作手册。
下面很简单的说下实现的细节
大整数是采用2^32进制保存的,也就是用一个DWORD存储一个“位”。对于四则运算均使用汇编优化,其中算法参见Knuth的the Art of Computer Program 第二卷的多精度计算。
对于素域的计算,主要采用的就是窗口法求模幂,素性验证使用了Rabin-Miller法,并且进行了100次判断,可以确保相当高的正确概率。
注意的是,我不能保证潜在的bug,同时一些算法并不是最优的,所以使用时请自己注意。而且今后基本无法维护了。对于具体的实现,可以看代码注释以及我附在其中的实习报告
代码/Demo/文档的下载:
http://www.csksoft.net/data/legacyftp/Products/code_and_lib/CiperLib_release_by_csk.rar
教育网:ftp://great_csk:public@public.sjtu.edu.cn/public-files/CiperLib_release_by_csk.rar