一般来说,RSA的公钥选取时,都会选择一个与$\phi(n)$互质的加密指数$e$,这样才能计算私钥中的揭秘指数$d$,满足$e*d\equiv1\pmod{\phi(n)}$,并用$d$来恢复明文。

$$ c^d\equiv m^{ed}\equiv m \pmod{n} $$

当$e$和$\phi(n)$不互质的时候,就不能直接计算$d=inv(e, \phi(n))$。然后不互质又可以分为两种情况,一是$e\mid\phi(n)$,二是$e\nmid\phi(n)$一

1. $e\nmid\phi(n)$

这种情况时比较好处理的,我们令$t=\gcd(e, \phi(n))$,那么$e//t$和$\phi(n)$时互质的,即$\gcd(e//t,\phi(n))=1$,这样就可以计算$d$,满足

$$ (e/t)*d\equiv1\pmod{\phi(n)} $$

然后将$m^t$看成一个整体

$$ c\equiv m^e\equiv (m^t)^{\frac{e}{t}}\pmod{n} $$

$$ c^d\equiv (m^t)^{\frac{e}{t}d}\pmod{n} $$

这个呢就是一个正常的RSA解密了,不过解出来的不是明文$m$,而是$m^t$,如何得到$m$呢?这就又要分两种情况考虑了

1) $m^t<n$

这就是最简单的了,直接开$t$次根,就直接得到$m$

from gmpy2 import iroot
from Crypto.Util.number import *
'''
p = 
q = 
c = 
n = p*q
e = 
'''
phi = (p - 1)*(q - 1)
t = GCD(e, phi)
d = inverse(e // t, phi)
_m = pow(c, d, n)
m = int(iroot(_m, t)[0])

2) $m^t>n$

  • 如果$m^t$没有比$n$大多少,那就可以爆破
from gmpy2 import iroot
'''
与上面的一致
'''
k = 0
while not iroot(_m + k*n, t)[1]:
	k += 1
m = iroot(_m + k*n, t)[0]

其实就相当于转换成了一个低加密指数的题

  • 也可以选择结合中国剩余定理

$$ x^e\equiv c\pmod{p} \\ x^e\equiv c\pmod{q} $$

在不同的域上开根,然后把得到的结果进行CRT组合

from Crypto.Util.number import *
import gmpy2
'''
p = 
q = 
c = 
n = 
e = 
phi = (p - 1) * (q - 1)
'''
R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()

R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()
for i in res1:
    for j in res2:
        ai = [i[0],j[0]]
        mi = [p,q]
        flag = CRT_list(ai,mi)
        flag = long_to_bytes(flag)
        if b'flag' in flag:
            print(flag)

2. $e \mid\phi(n)$

这个时候就不能用上面的类似RSA的方法解决了,我们就只能在有限域上开根了。

谈论有限域开根问题,AMM算法是绕不过的。AMM算法在RSA中适用于指数e整除phi的情况,也就是说phi % e == 0。其中有详细的论文,AMM算法具体的作用就是在有限域中开出一个根。具体实现论文也明确地给出了。

Untitled

代码实现:

# sage

def AMM(o, r, q):
  start = time.time()
  print('\n----------------------------------------------------------------------------------')
  print('Start to run Adleman-Manders-Miller Root Extraction Method')
  print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
  g = GF(q)
  o = g(o)
  p = g(random.randint(1, q))
	while p ^ ((q-1) // r) == 1:
		p = g(random.randint(1, q))
  print('[+] Find p:{}'.format(p))
  t = 0
  s = q - 1
	while s % r == 0:
	  t += 1
	  s = s // r
  print('[+] Find s:{}, t:{}'.format(s, t))
  k = 1
	while (k * s + 1) % r != 0:
	  k += 1
    alp = (k * s + 1) // r
  print('[+] Find alp:{}'.format(alp))
  a = p ^ (r**(t-1) * s)
  b = o ^ (r*alp - 1)
  c = p ^ s
  h = 1
	for i in range(1, t):
	  d = b ^ (r^(t-1-i))
		if d == 1:
	    j = 0
		else:
	    print('[+] Calculating DLP...')
	    j = - discrete_log(d, a)
      print('[+] Finish DLP...')
		b = b * (c^r)^j
		h = h * c^j
		c = c^r
	result = o^alp * h
	end = time.time()
  print("Finished in {} seconds.".format(end - start))
  print('Find one solution: {}'.format(result))
	return result

最近在刷题和看大佬们的wp的时候知道了一个方便的函数:

from sympy.ntheory.residue_ntheory import nthroot_mod
nthroot_mod(a,n,p)

Untitled