首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 软件逆向
    3. 发新帖
初涉RSA，不知道下面的P、Q该如何计算，e 又如何得到？
发表于: 2004-10-28 21:44 8358

初涉RSA，不知道下面的P、Q该如何计算，e 又如何得到？

moonese 活跃值
2004-10-28 21:44
8358
现在碰到一个软件，是JAVA写的，反编译以后，
发现其解密算法很简单，如下：
public static final BigInteger d = new BigInteger("3");
public static final BigInteger n = new BigInteger("8906903129577952276746908515698640503231635991540376980783671268045406211849974445483080921650302672167490495264490128543118907938111626019977184581076859175345474365729002665435415606416258210992506640138821527940283618012370680028201515994542530228905893145734354457208590016638464983949993650401054435054516895627363958843019152344583195167174687882057052771189508616868586808039000248830107987375404448730214478948741777790686435427083594448761475479158580802447874497702846873");

BigInteger regData = new BigInteger(encryptedLicense, 36);
BigInteger decoded = regData.modPow(d, n); // 主要的加密算法
byte decodedBytes[] = decoded.toByteArray();
String realData;
try
{
realData = new String(decodedBytes, "US-ASCII");
}
catch(UnsupportedEncodingException e)
{
}

明显就是RSA算法了
可是用 RSATool生成的P,Q好像用不起来
可以帮帮我吗？

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)

收藏
免费 ・1
支持
分享
最新回复 (20)
风云剑
雪    币： 231
活跃值： (115)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
2 楼
常规做法是分解n，但这不现实。
不过它的d很小，才3，看看能不能从这里突破。
2004-10-29 08:44
0
moonese
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
3 楼
昨晚没关机，分解N算了一晚
今天早上一看，程序不知道什么时候退出了
谁有BigInt Caculator?
我想试试那个程序是不是要好一点
可以发到我的邮箱吗？
[email]moonese@126.com[/email]

谢谢！
2004-10-29 08:51
0
cnbragon
雪    币： 3686
活跃值： (1036)
能力值： (RANK：760 )
在线值：
发帖
回帖
粉丝
私信
4 楼
很明显你的N是10进制
d=3??
关键还是N太大
2004-10-29 10:12
0
evileast
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
5 楼
RSA就是建立在得到两个大质数的乘积容易,求反则难的数学难题上的.你说的RSAtool应该只能分解一些小质数的乘积.正规的加密n是最少200位的,你给的n是400多位,当然算不出来了.
ps,你说的d=3应该是e=3吧,e加密,d解密,d如果知道的话,就不用在分解n了,拿到密文X后直接X^d (mod n)就可以直接得到原文了!: )
2004-10-29 11:08
0
cnbragon
雪    币： 3686
活跃值： (1036)
能力值： (RANK：760 )
在线值：
发帖
回帖
粉丝
私信
6 楼
楼上的，RSATool可以算出来的，只是需要时间
这里是用e作为密钥，d作为公钥,反用了一下
2004-10-29 11:20
0
evileast
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
7 楼
最初由 cnbragon 发布
楼上的，RSATool可以算出来的，只是需要时间
这里是用e作为密钥，d作为公钥,反用了一下


我看了这个软件的帮助文件
...Factor a Number ?
1) Select the correct number base for the number you want to factor.
2) Type in or Paste the number in the Editbox for the Modulus (N). This enables the 'Factor' button.
3) Press the Factor N button. Note that factoring numbers > 240 Bits can take a LOT of time and memory !
    Even smaller ones can take several hours. If you dont believe me try to factor a 240 Bit N generated by
    this tool. If the multiple polynomial quadratic sieve (MPQS) Algorithm is needed to factor your number, a huge
    amount of memory is needed. Reason for that is the design of the algorithm, not a sloppy implementation ;-)
2004-10-29 12:05
0
moonese
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
8 楼
看上面写的的确是这样的
但是我在网上搜到的文章也有说几分钟就分解出来了的

请问 evileast ，你有用过 RSATool吗？
成功分解出 q 和 p 过？  一般都要花多长时间？
有没有碰到过执行时间一长程序就退出的现象？

谢谢！
2004-10-29 15:29
0
evileast
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
9 楼
最初由 moonese 发布
看上面写的的确是这样的
但是我在网上搜到的文章也有说几分钟就分解出来了的

请问 evileast ，你有用过 RSATool吗？
成功分解出 q 和 p 过？ 一般都要花多长时间？
........


我只分解出来了200bitN的数,用了两分钟
250bit,和300bit花了20分钟都没有分解出来,不是我没有耐心,是
软件后来基本上没有什么进度了.
分解大质数的乘积的时间是按位成指数上升的.更何况现在的工业标准已经在1024bit左右了.: (
就象我说的,这不是破解的问题,而是数学目前的难题:没有一种好的算法分解N.

个人认为有些人能够分解N,是因为他们的N是随机键入的,而不是按操作生成地.
因为这样的N,可能会是很多小指数的乘积.
合法的N,应该是只能由唯一的一对大质数生成的.

如果对RSA感兴趣的话,还是建议把时间花在学习一下如何生成一个大质数和如何求d,使得gcd(e,d)=1 (mod N) 这要比在一台电脑前等待rsatool的结果要有意思的多
2004-10-29 17:53
0
moonese
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
10 楼
第一个骨头就这么难啃
2004-10-30 09:25
0
风云剑
雪    币： 231
活跃值： (115)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
11 楼
老大，你的N有1600bits，RSATools根本不可能分解出来。还是从d=3上想办法吧。
上面有人说d和e弄反了，其实这是无所谓的，从RSA原理来看，d和e是对等的。
2004-10-30 10:49
0
风云剑
雪    币： 231
活跃值： (115)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
12 楼
有没有碰到过执行时间一长程序就退出的现象？
根据我的试验来看，这是由于内存不够造成的。
2004-10-30 10:51
0
moonese
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
13 楼
thx all
2004-10-31 11:22
0
moonese
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
14 楼
很弱  可是始终想不通
大家看上面：
BigInteger regData = new BigInteger(encryptedLicense, 36);
是把密文转成36进制的数以后再进行解密的

如果我现在要加密一个字符串
是不是应该也把原字符串先加密，
然后转化成36进制表示的字符串
就是合法的密文了？

哪里有进行RSA运算的程序吗？
我用了RsaKit，
不过不能处理256位以上的N
不能加密 非数字或是字符

谁有BigInteger calculator，
发一份给我好吗？

[email]moonese@126.com[/email]
谢谢！
2004-11-3 22:44
0
moonese
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
15 楼
rt
2004-11-3 22:58
0
风云剑
雪    币： 231
活跃值： (115)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
16 楼
RSA加密是要分段的，而且必须是对数字加密，非数字要先转换成数字再加密。还有就是被加密的数字不能超过模数，否则会有不唯一现象。好像是这样的，我也记不清了。
至于字符串转换成数字，其实很容易。比如一个字符串一共有10000bits，而n是1024bits，那可以每512bits为一段，每一段转换为一个512bits的大数，再加密。转换的方法很多，只要是可逆的就可以。
2004-11-4 08:51
0
moonese
雪    币： 202
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
17 楼
而是像下面这样的字符串：
aa2\b1b\3cc\ddd

这样的字符串该如何转换成 “36进制” 的数呢？
2004-11-4 10:51
0
evileast
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
18 楼
最初由 moonese 发布
而是像下面这样的字符串：
aa2\b1b\3cc\ddd

这样的字符串该如何转换成 “36进制” 的数呢？


那就直接运算呀,RSA不是分组密码(block cipher),不用补够位数
我没有听说过字符串是要转换成36进制,不过不管转换成多少进制,
在计算机内部都是用二进制表示的.至于实际转换,字符串转换是按
各个字符的ASCII码进行计算的.譬如说"\"的ascii码值用十进制表
示是92.
2004-11-4 19:27
0
seamew
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
19 楼
:o
2004-11-5 13:14
0
seamew
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
20 楼
:(
2004-11-5 13:17
0
ForEver
雪    币： 343
活跃值： (611)
能力值： ( LV9，RANK：810 )
在线值：
发帖
回帖
粉丝
私信
21 楼
要转成36进制? strtol就可以
long strtol( const char *nptr, char **endptr, int base );
unsigned long strtoul( const char *nptr, char **endptr, int base );
2004-11-8 13:37
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//