首页
课程
问答
CTF
社区
招聘
看雪峰会
发现
排行榜
知识库
工具下载
看雪20年
看雪商城
证书查询
登录
注册
首页
社区
课程
招聘
发现
问答
CTF
排行榜
知识库
工具下载
看雪峰会
看雪商城
证书查询
看雪社区
编程技术
发新帖
3
7
[原创]我写的大整数和素域运算库
2007-9-5 19:44
10526
[原创]我写的大整数和素域运算库
greatcsk
4
2007-9-5 19:44
10526
好久没有来发贴了,下面这个是我暑期实习作的东西,用了汇编优化,效率比较高,所以就放出来了,用处很明显,可以实现相关密码算法,如RSA。
Blog原文:
http://www.csksoft.net/blog/post/CiperLib_release.html
代码/DEMO/文档/Benchmark程序:
ftp://FTP_Visitor:visitor@ftp.csksoft.net/Public/Products/code_and_lib/CiperLib_release_by_csk.rar
教育网:
ftp://great_csk:public@public.sjtu.edu.cn/public-files/CiperLib_release_by_csk.rar
------------------------------------------------------------------------------
CipherLib是一个使用C++和汇编代码实现的用于多精度大整数运算和密码学领域素域基本运算的函数库。由陈士凯(CSK)开发。
这个函数库实现的操作有:
●
支持任意精度的大整数:精度可以通过代码设定,支持符号数
对大整数的四则运算和求模运算,以及2进制化的移位操作
使用类将大整数加以封装,支持直接用传统运算符进行大整数的运算代码编写
支持从文本串和系统内置整型数据中读取大整数,支持将大整数输出为2进制、8进制、10进制和16进制文本串
实现了Marsaglia & Zaman的长周期随机数(本机支持的整型格式)
支持模加、模乘、模幂计算
支持Rabin-Miller方法的素性验证
支持大素数产生
简单的说可以利用这个库实现一些高精度计算和密码算法,比如RSA。
该函数库在设计上参考了mircal库,在核心的运算操作上使用了x86汇编语言和C语言2种版本代码编写。默认采用汇编语言执行。因而具有很高的运行效率(具体见Benchmark部分)
CipherLib的一些技术信息:
项目 说明
运行环境 32位x86指令系统下的windows环境
开发环境 VC++ 2005版本
是否多线程安全 否
函数库形式 静态链接库或者直接嵌入代码
第三方库依赖 需要C运行库
------------------------------------------------------
Benchmark
下面是我写的对于CipherLib和mircal的一个运行效率比较(不过不是很科学,但是基本可以说明问题):
使用附带的程序CiperBench进行测试。
测试程序在开发者电脑环境:Intel Pentium M 1.6G ,2G RAM,WinXP sp2环境中,对于静态库的本函数库和Mircal进行比较。
由于采用了timeGetTime() API获取时间,因此精度可能会受偶尔系统调度的影响。
下面是对1000次的四则运算的执行时间对比,本函数库表现较优:
对于乘法的实测情况
对于加法的实测情况
对于减法的实测情况
对于除法的实测情况
对于素域运算,使用了产生一个大素数的运算作为衡量指标,因为其中需要进行素性验证和模乘和模幂运算。本函数库效率较低,原因是没有针对素性验证是的模幂运算单独进行优化。
我用于求模幂的算法是Koch提出的Sliding Window法。但是对于求素性验证来说不是最优的。
不过从绝对时间看,还是开始接受的
-----------------------------------------------------
使用范例
下面是用本函数库求解1000!的代码,从代码风格上可以看出他的易用性,具体代码和使用办法见文章末尾给出的文件中的操作手册。
#include "CiperLib.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
Integer::Init(409600);
char output[20000];
Integer Base(1000),Ans(1);
while(!Base.isZero())
{
Ans *= Base;
Base -= 1;
}
Ans.toString(output,20000);
cout<<"Finished, Ans is:"<<endl<<output <<endl;
system("pause");
}
下面很简单的说下实现的细节
大整数是采用2^32进制保存的,也就是用一个DWORD存储一个“位”。对于四则运算均使用汇编优化,其中算法参见Knuth的the Art of Computer Program 第二卷的多精度计算。
对于素域的计算,主要采用的就是窗口法求模幂,素性验证使用了Rabin-Miller法,并且进行了100次判断,可以确保相当高的正确概率。
注意的是,我不能保证潜在的bug,同时一些算法并不是最优的,所以使用时请自己注意。而且今后基本无法维护了。对于具体的实现,可以看代码注释以及我附在其中的实习报告
代码/Demo/文档的下载:
ftp://FTP_Visitor:visitor@ftp.csksoft.net/Public/Products/code_and_lib/CiperLib_release_by_csk.rar
教育网:
ftp://great_csk:public@public.sjtu.edu.cn/public-files/CiperLib_release_by_csk.rar
好了,等会再发些前一阵的东西,希望对各位有帮助~
[培训]二进制漏洞攻防(第3期);满10人开班;模糊测试与工具使用二次开发;网络协议漏洞挖掘;Linux内核漏洞挖掘与利用;AOSP漏洞挖掘与利用;代码审计。
收藏
・
3
点赞
・
7
打赏
分享
分享到微信
分享到QQ
分享到微博
赞赏
×
1 雪花
5 雪花
10 雪花
20 雪花
50 雪花
80 雪花
100 雪花
150 雪花
200 雪花
支付方式:
微信支付
赞赏留言:
快捷留言
感谢分享~
精品文章~
原创内容~
精彩转帖~
助人为乐~
最新回复
(
13
)
kanxue
雪 币:
29412
活跃值:
(18685)
能力值:
(RANK:350 )
在线值:
发帖
1827
回帖
15214
粉丝
487
关注
私信
kanxue
8
2007-9-5 20:15
2
楼
0
没测试,纯支持一下,期待完善。;)
greatcsk
雪 币:
236
活跃值:
(35)
能力值:
( LV9,RANK:170 )
在线值:
发帖
6
回帖
23
粉丝
3
关注
私信
greatcsk
4
2007-9-5 20:22
3
楼
0
呵呵,多谢老大支持。
效率上市没有问题的,基本的运算我也大体测试过了。毕竟今后实验室要用这个做进一步算法实现
不过可能会有一些小bug在
forgot
雪 币:
6073
活跃值:
(2236)
能力值:
(RANK:1060 )
在线值:
发帖
155
回帖
3744
粉丝
15
关注
私信
forgot
26
2007-9-5 21:04
4
楼
0
蒙哥xx的好一些?
greatcsk
雪 币:
236
活跃值:
(35)
能力值:
( LV9,RANK:170 )
在线值:
发帖
6
回帖
23
粉丝
3
关注
私信
greatcsk
4
2007-9-5 21:10
5
楼
0
素性验证时候要求A^n (mod m)其中n是小整数,用窗口法就是杀鸡用牛刀,慢在这里
happytown
雪 币:
721
活跃值:
(350)
能力值:
( LV9,RANK:1250 )
在线值:
发帖
131
回帖
1014
粉丝
1
关注
私信
happytown
31
2007-9-5 21:13
6
楼
0
这个一定要支持。
happytown
雪 币:
721
活跃值:
(350)
能力值:
( LV9,RANK:1250 )
在线值:
发帖
131
回帖
1014
粉丝
1
关注
私信
happytown
31
2007-9-5 21:31
7
楼
0
发现这么句话:“国内著名破解组织看雪论坛”
呵呵
jsjcjsjc
雪 币:
178
活跃值:
(10)
能力值:
( LV2,RANK:10 )
在线值:
发帖
1
回帖
70
粉丝
0
关注
私信
jsjcjsjc
2007-9-5 21:54
8
楼
0
楼上的那句话不够味儿啊
坚持到底
雪 币:
538
活跃值:
(460)
能力值:
( LV9,RANK:290 )
在线值:
发帖
12
回帖
245
粉丝
2
关注
私信
坚持到底
7
2007-9-5 22:38
9
楼
0
支持一下。。。
slimyu
雪 币:
200
活跃值:
(10)
能力值:
( LV2,RANK:10 )
在线值:
发帖
0
回帖
7
粉丝
0
关注
私信
slimyu
2007-9-5 23:32
10
楼
0
不错,支持下,赞一个
ykzhujiang
雪 币:
107
活跃值:
(11)
能力值:
( LV4,RANK:50 )
在线值:
发帖
11
回帖
89
粉丝
0
关注
私信
ykzhujiang
1
2007-9-5 23:44
11
楼
0
赞一下大三的小学弟~
readyu
雪 币:
11704
活跃值:
(966)
能力值:
( LV12,RANK:779 )
在线值:
发帖
27
回帖
378
粉丝
40
关注
私信
readyu
12
2007-9-10 14:48
12
楼
0
timeGetTime(),GetTickCount(),返回值的单位是ms,但实际上它的精度只有10ms左右。
所以就有0ms这样的值出来了。
QueryPerformanceCounter()采用3.579545MHZ计时器,精度能达到us.
rdtsc取CPU内部time stamp counter,精度是ns级的。
你可以实测一下两段代码消耗的cpu周期数。
// Win32, C++ return an int64, is EDX:EAX
// rdtsc: 0F31
__inline unsigned __int64 cput_64bit(void)
{
__asm _emit 0x0F
__asm _emit 0x31
}
uint64 cpucnt_now;
CRITICAL_SECTION g_critical_cpu_cnt;
InitializeCriticalSection(&g_critical_cpu_cnt);
EnterCriticalSection(&g_critical_cpu_cnt);
cpucnt_now = cput_64bit();
// 待测代码段
cpucnt_now = cput_64bit() - cpucnt_now;
LeaveCriticalSection(&g_critical_cpu_cnt);
greatcsk
雪 币:
236
活跃值:
(35)
能力值:
( LV9,RANK:170 )
在线值:
发帖
6
回帖
23
粉丝
3
关注
私信
greatcsk
4
2007-9-10 18:20
13
楼
0
恩,这个问题当时因为只是想做验证性的测试所以就偷懒用timeGetTime()了。rdtsc其实也会因为windows线程调度造成不精确。
对于比较精确的benchmark还是需要列出histogram
给的代码不错,收藏了^_^
readyu
雪 币:
11704
活跃值:
(966)
能力值:
( LV12,RANK:779 )
在线值:
发帖
27
回帖
378
粉丝
40
关注
私信
readyu
12
2007-9-10 18:44
14
楼
0
函数不要太长就是,一般是没有问题的。1ms已经可以跑百万个时钟周期了。
长时间的性能比较,超过10ms被切换,直接加减时间的方法都不行了。则要用统计线程时间来算了。
那段是我计算CPU主频的一段代码。比如说
QueryPerformanceCounter() 消耗时钟周期;
每次是有变化的 6000-8000不等。多次测试就OK了。
游客
登录
|
注册
方可回帖
回帖
表情
雪币赚取及消费
高级回复
返回
greatcsk
4
6
发帖
23
回帖
170
RANK
关注
私信
他的文章
[原创]谈谈intel x86提供的Branch Trace Store的功能
62239
[原创]内核态进程管理器Intercessor和实现细节
24292
[原创]我写的大整数和素域运算库
10527
crack程序中mod背景音乐的创作和使用(看雪学院2006金秋读书季)
8840
[原创]通过修改系统函数创建"同名"文件的程序和代码
4088
关于我们
联系我们
企业服务
看雪公众号
专注于PC、移动、智能设备安全研究及逆向工程的开发者社区
看原图
返回
顶部