这是两个容易被我忽视的trick

TRICK1: Factor N with knowing N % (p-1)

  • 起因:闲逛github发现一道题,虽然很简单,但这里面的trick很容易被我忽视,以防下次再出现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import getPrime, bytes_to_long

flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())

def genkey():
e = 0x10001
p, q = getPrime(256), getPrime(256)
if p <= q:
p, q = q, p
n = p * q
pubkey = (e, n)
privkey = (p, q)
return pubkey, privkey

def encrypt(m, pubkey):
e, n = pubkey
c = pow(m, e, n)
return c

pubkey, privkey = genkey()
c = encrypt(flag, pubkey)

hint = pubkey[1] % (privkey[1] - 1)
print('pubkey:', pubkey)
print('hint:', hint)
print('c:', c)

​ 注意到:$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的时间。

评论