[WP] cryptohack mathematics brainteasers-part-1

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

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

目录传送门:cryptohack 练习学习汇总(writeup index)

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 可以直接分解

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

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

则有

可视为一个一个二元一次方程组,可以求出 $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

易知

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

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

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