突然发现数学这一节没有其他格相关内容了,可能后面的章节还有?反正先做着!
这一节名字叫脑筋急转弯,看样子是脑洞题巨多
目录传送门: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