2023-05-04

[WP] cryptohack mathematics brainteasers-part-1

突然发现数学这一节没有其他格相关内容了，可能后面的章节还有？反正先做着！

这一节名字叫脑筋急转弯，看样子是脑洞题巨多

Successive Powers

以下是数学方法（代码仅供计算使用）

注意到有这样连续的两个数： $4, 836$ 。我们断言， $\frac{836}{4}=209$ 即为 $x$

这是因为：不妨设 $0<x<p<1000$ （若不是，可以通过 $x'=x \bmod p$ 来使 $x$ 满足范围，且表现不变）
若 $\frac{836}{4}=209$ 不是 $x$ ，
因为有 $4x\equiv836\pmod p$ ，
则必有 $4x=836+pR(R\in Z_+)$
即 $x=209+\frac{pR}{4}$
考虑到 $x$ 为整数，必有 $4|pR$ 。因为 $p$ 是一个奇质数，故 $4|R$ ，故 $R\ge 4$
可以得到 $x\ge 209+p$
注意到给出的数列中含有 836，故 $p>836$ ，故 $x>1045$ 矛盾
综上， $x=209$

然后通过任意两个相邻的数可以求出某一个 $pR$ 的值，从而通过质因数分解很容易可以得到 $p$

代码: cryptohack/mathematics brainteasers-part-1 Successive-Powers.py

Adrien's Signs

这题很有意思啊
利用了一个性质：有二次剩余的数的乘方还是有二次剩余，且 $p\equiv 3\pmod 4$ 的时候一个有二次剩余的数的相反数没有二次剩余

恰好的是， $x$ 有二次剩余，且题目所给的 $p$ 确实是 $4x+3$ 型素数，因此直接判断一个数有无二次剩余即可

代码: cryptohack/mathematics brainteasers-part-1 Adriens-Signs.py

Modular Binomials

非预期：Factordb 可以直接分解

这题也太有意思了。首先考虑到指数不一样很难处理，变化为如下形式：

\begin{cases} c_1^{e_2}=(2p+3q)^{e_1e_2}\pmod N\\ c_2^{e_1}=(5p+7q)^{e_1e_2}\pmod N \end{cases}

注意到，二项式展开后，除了边缘两项之外，其他项均含 $pq$ 可以忽略

\begin{cases} c_1^{e_2}\equiv(2p)^{e_1e_2}+(3q)^{e_1e_2}\pmod N\\ c_2^{e_1}\equiv(5p)^{e_1e_2}+(7q)^{e_1e_2}\pmod N \end{cases}

记

\begin{cases} a\equiv2^{e_1e_2}\pmod N\\ b\equiv3^{e_1e_2}\pmod N\\ c\equiv5^{e_1e_2}\pmod N\\ d\equiv7^{e_1e_2}\pmod N\\ \end{cases}

则有

\begin{cases} a\cdot p^{e_1e_2}+b\cdot q^{e_1e_2}\equiv c_1^{e_2}\pmod N\\ c\cdot p^{e_1e_2}+d\cdot q^{e_1e_2}\equiv c_2^{e_1}\pmod N \end{cases}

可视为一个一个二元一次方程组，可以求出 $p^{e_1e_2}\bmod N$ 和 $q^{e_1e_2}\bmod N$
最后将结果与 N 求 gcd 即可得到 $p,q$

代码: cryptohack/mathematics brainteasers-part-1 Modular-Binomials.py

Broken RSA

虽然 $n$ 是素数， $e=16$ 导致 $\gcd(n-1,e)\not=1$ ，但是我们可以简单地开 4 次根号（求 4 次二次剩余）直接获取明文

代码: cryptohack/mathematics brainteasers-part-1 Broken-RSA.py

No Way Back Home

易知

v = \dfrac{vka\cdot vkb}{vkakb}

但是 $p|vka,vkb,vkakb$ ，因此 $vkakb$ 没有逆元
不过容易想到

v = \dfrac{\frac{vka}{p}\cdot \frac{vkb}{p}}{\frac{vkakb}{p}}\cdot p

其中前面的部分（ $\cdot p$ 前）在 $\bmod q$ 意义下进行
由此可以解得 $v$ 进而得到 flag

代码: cryptohack/mathematics brainteasers-part-1 No-Way-Back-Home.py