首页
社区
课程
招聘
[求助]大数高次幂取模后的反求
发表于: 2010-10-31 20:02 11526

[求助]大数高次幂取模后的反求

uuk 活跃值
3
2010-10-31 20:02
11526

(x^a) mod b = c ,其中 a=65537、b、c 已知, x<b , b、c、x 都是大数整数,
请问这能不能解?如果 c 是一个范围,能不能快速求解? 要求的是 x

这是 Sandboxie 激活码的验证过程,得到 Reg 后验证里面的一些值。


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 7
支持
分享
最新回复 (5)
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
2
估计是RSA算法
x=c^(a^(-1)modφ(b)) mod b
求φ(b)需要分解b,如果已知足够的部分x,可以用格的方法求解
2010-10-31 23:04
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
3
1)
请问你是想求 x 还是...?

2)
c 的范围一定是落在  1< c < b

3)
若是想求 x, 则请看  http://bbs.pediy.com/showpost.php?p=622018&postcount=91http://bbs.pediy.com/showpost.php?p=622030&postcount=92,里面有详细的说明。
2010-11-1 12:59
0
雪    币: 379
活跃值: (233)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
4
先谢谢楼上两位!

现在正在看 同余方程 和 RSA 算法,短期内可能搞不清楚,先问问我这是属于哪个?(b不是素数)
2010-11-1 22:50
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
6
2048bit的RSA,构造 Reg 然后反求 Key 是不可行的
如果能够提交Reg,然后让服务器计算Key的话,
可以通过构造Reg来得到一些信息,否则都是徒劳。
2010-11-2 09:49
0
雪    币: 379
活跃值: (233)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
7
看出来了,哎!

不过总算没白忙活,学到新的知识。
2010-11-2 17:40
0
游客
登录 | 注册 方可回帖
返回
//