Erning.write()

Reloading

[SOLVED] Re: 一个数学问题

Subject: [SOLVED] Re: 一个数学问题
From: Zhang Erning (zhangern@china-channel.com)
Date: 8/8/2005 3:18 PM
To: tech@35.cn

hi,

多谢各位的回复。

是的,这个其实就是破解RSA的问题。只是当RSA的key很大的时候,破解需要的时 间是不可接受的。

我这个问题,A,B是常量,而且算是很小的。(可能提问的时候提示不够)

根据RSA的算法的说明
当 xB mod A = c 时,应该有
x = cr mod B

问题就是算出r

rB mod ((p-1)(q-1)) = 1
其中p,q是两个质数,p
q == A

问题就成了找p,q的,这也就是RSA里最直接的破解思路。因为A足够小。
A=179399505810976971998364784462504058921

通过Quadratic Sieve算出
p=9939430972488238699
q=18049273274048008379

B=65537
然后 modular inverse 算出
r=89126272330128007543578052027888001981

不停的google后,终于解决了。

[其实我是想写一个软件的序列号生成器,搞定了]

Zhang Erning

Hi,

有个数学问题,有数学比较好的帮我看看,或者问问,谢谢。

对下面的方程,A,B是常量, 给定一个c,求x。其中A,B,c,x都是正整数
xB mod A = c
(xB表示x的B次方,mod是模。)

A, B, c, x 都是个很大的整数,其中常亮
A=179399505810976971998364784462504058921
B=65537

其中一个解的例子是

c=316442568644203243198389073 时
x=162056862300807702758723198119182049115

这个c是通过x算出来的,我想知道,给定c能否算出x

另外,c是有特征的,c为12个bytes的integer。其中前10个bytes固定的。
比如 c = 0x 31 05 00 00 00 00 00 00 00 00 xx xx
对于给定的c,就后面两个bytes不同。

这个问题目前也可能没有好办法。就是不能在可接受的O()里通过c逆算出x。

Zhang Erning