[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 的算法的说明
当 x^B mod A = c 时，应该有
x = c^r mod B

问题就是算出 r

rB mod ((p-1)(q-1)) = 1
其中 p,q 是两个质数，pq == 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 都是正整数
x^B mod A = c
(x^B 表示 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