DASCTF X BUUOJ 之密码题：Fibonacci

Posted on

DASCTF X BUUOJ 五月大联动的比赛里，出现一道有趣的密码题。

之前各大CTF中的RSA相关的题目，基本都是Twenty Years of Attacks on RSA Cryptosystem这篇论文中的攻击方法的复现，看过几次之后就会觉得很无聊，毫无新意。而这次比赛中，引入了一个新的、我没见过的大数分解定理，值得记录一下。

题目很短很简单，直接贴在这里：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from gmpy2 import *
flag='flag{*************************}'
m=bytes_to_long(flag)

def F(n): # 斐波那契数列的第n项
    if n == 1 or n == 2:
        return 1
    return F(n - 1) + F(n - 2)

for _ in range(3):
    p=getPrime(8)
    q=getPrime(1024)
    n=p*q
    F=F(n)
    c=pow(m,65537,F)
    print ('n = %d'%(n))
    print ('F(n) = %d'%(F))
    print ('c = %d'%(c))

先简化一下加密过程，如下（\(F_n\)为斐波那契数列第\(n\)项）： \[ n = p \cdot q \] \[ c = m^{65537} \bmod F_n \] 其中，斐波那契数列这个特殊条件在以往的题目中没出现过，所以需要先了解一遍大数分解和斐波那契数列的关系。于是就找到了这篇文章：The Mathematical Magic of the Fibonacci Numbers，其中最重要的是下面的公式： \[ \gcd(F_m, F_n) = F_{\gcd(m, n)} \] 因此，可以得到如下式子： \[ \gcd(F_n, F_p) = F_{\gcd(n, p)} = F_p \implies F_n = F_p \cdot F_q \] \[ c = m^{65537} \bmod F_n \implies \begin{cases} c = m^{65537} \bmod F_p\\ c = m^{65537} \bmod F_q \end{cases} \] 由于素数\(p\)很小，可以先分解\(n\)得到\(p\)和\(q\)，进而得到\(F_p\)。题目中给出了三组密文，所以我们可以得到三条式子： \[ \begin{equation}\label{eqs} \begin{cases} c_1 = m^{65537} \bmod F_{p_1}\\ c_2 = m^{65537} \bmod F_{p_2}\\ c_3 = m^{65537} \bmod F_{p_3} \end{cases} \end{equation} \] 这里选择\(F_p\)的式子组成方程组，是考虑到\(F_p\)数值较小，容易分解质因数，便于后续求解方程组的解，如果使用\(F_q\)则无法求解。上述方程组可以用中国剩余定理求解，得到解\(m'\)满足如下式子： \[ m' = m \bmod (F_{p_1} \cdot F_{p_2} \cdot F_{p_3}) \] 最后再利用上一个条件：明文（flag）对应的整数很小。也就是说，\(m\)很小，我们可以猜测它不会超过\(F_{p_1} \cdot F_{p_2} \cdot F_{p_3}\)的值，那么我们求出来的\(m'\)就是flag了。其实，如果不是flag，可以再加上\(F_{p_1} \cdot F_{p_2} \cdot F_{p_3}\)的整数倍，判断是不是flag即可，一般CTF题目的flag都不会太长的。

最后补充一点：求斐波那契数列第\(n\)项可以直接在上面的斐波那契数的文章里的表查一下。表中还有第\(n\)项的分解式，这个在求解方程组\((\ref{eqs})\)的时候可以直接用。如果自己写程序求解，就太慢了。