两个容易被我忽视的trick

Lyutoon

cryptographyalgorithm

发布于：2021年9月13日

次浏览

这是两个容易被我忽视的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$，也就说明了：

  $$hint = pq\,mod\,(q-1)=p\,mod\,(q-1)\,=>\,hint + q-1 = p$$

• 第二种做法就是利用费马小定理:

  $$n - n\,mod\,(q-1) = 0 \,mod\,(q-1)=>gcd(n, 2^{n-hint}-1) = p$$

• 类似应用：巅峰极客crtrsa

  题目给了$d_p$的范围，是可以爆破出来的，相当于直接给了$d_p$，那么我们要做的就是通过$d_p$分解$N$

  我们知道：

  $$ed_p = 1\,mod\,(p-1)\\ =>ed_p-1 = 0\,mod\,(p-1)$$

  那么我们可以随便选一个与$n$互素的数，比如233：

  $$gcd(n, 233^{e*d_p-1}-1)=p$$

• 总结：当我们可以凑出如下形式：$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的时间。

更新于：2021年9月13日