这是两个容易被我忽视的trick
TRICK1: Factor N with knowing N % (p-1)
- 起因:闲逛github发现一道题,虽然很简单,但这里面的trick很容易被我忽视,以防下次再出现
1 | from Crypto.Util.number import getPrime, bytes_to_long |
注意到:$hint = n\,mod\,(q-1)$
第一种是我的做法,非常简单:注意到$p,q$都是balance的素数,那么$int(\frac{p}{q})=1$,也就说明了:
第二种做法就是利用费马小定理:
类似应用:巅峰极客crtrsa
题目给了$d_p$的范围,是可以爆破出来的,相当于直接给了$d_p$,那么我们要做的就是通过$d_p$分解$N$
我们知道:
那么我们可以随便选一个与$n$互素的数,比如233:
总结:当我们可以凑出如下形式:$x = 0\,mod\,(p-1)$,我们便可以分解$n$: $p=gcd(m, a^{x}-1)$
TRICK2: Find a pair of N such that gcd(N1, N2) > 1 over an array in a faster way
- 起因:RCTF出了一道有趣的密码学题目Uncommon Factors I
- 直接给题目给的400w个$N$两两乘起来,之后再反复这样,直到数据量下降到可以接受的范围内,之后再做gcd,这样就会省去很多做gcd的时间。