0CTF rsa quine

Posted by rk700 on April 3, 2015

这道题是一道密码学(其实是数学)的题目,因为对相关理论还是不够熟练,在比赛的时候没有能够做出来:( 这两天读了读别人的writeup,基本上明白解法了,在这里记录下具体的思路。

题目的要求是求”quine number”,即:已知RSA公钥,求,使得。规则很清晰,但实际解决起来还是需要一定的数学知识。

Ok. Now welcome to the world of math!

我当时犯的一个错误是,误以为。满足这样的当然符合条件,然而试了下就发现,所有这样的还是不够题目要求的quine的数目。事实上,这样做的前提是存在的逆,而是一个合数,是环而不是域,逆不一定存在的。

于是,我们首先分解。因为互素,所以题目就可以化为:求使得

是素数,所以就是有限域了,必然存在逆。所以,如果记,题目可以进一步转化为:求使得

一旦得到了,就可以根据中国剩余定理得到

下面来看怎样求存在作为乘法群的generator的primitive element,记为。它具有如下性质:

当然可以为0;如果其非0,那么就可以被生成。假设,那么,从而一定是的倍数。因此,我们有:

为了求所有的,我们只需要先求出,那么。有了这些,我们可以计算出相应的一系列。注意这里是有限域,所以所有的,除了0,其实也构成了一个cyclic group。

上述的就是如何求。同样的道理我们可以求出所有的。两两组合,每一对使用中国剩余定理,就得到了满足题意的