域中求n次方根的学习笔记

稍微补一下之前留下来的AMM（Adleman-Manders-Miller）算法的坑，发现SageMath中有个叫nth_root的函数可以直接解，于是撸了新的脚本，比之前抄来的高效一点。

问题描述·

假设$\mathbb{F}$是一个域，现有$y \equiv x^n \text{ in } \mathbb{F}$，知道$y$和$n$，求所有符合条件的$x$。

如果这个域是实数域$\mathbb{R}$，问题就很好解决，直接对$y$开$n$次方即可。但如果$\mathbb{F}$是像$\mathbb{Z}_{p^k}$这样的域，直接对$y$开$n$次方会产生小数，而很明显小数不存在$\mathbb{Z}_{p^k}$，所以经典的实数域开$n$次方的解法并不能应用于所有的域。

另一个问题是，即使可以直接对$y$开$n$次方，那也只能得到一个解，而符合条件的$x$应当有$n$个（因为这是个$n$次方程，虽然$n$个解中可能会有相同的），所以还需要有一种方法，在得到其中一个解的情况下解出所有符合条件的$x$。

求y的一个n次方根·

可以用AMM（Adleman-Manders-Miller）算法，但SageMath已经集成了一个nth_root函数（不知道是不是用AMM的），所以先把这个坑留着（逃

给个栗子，令$\mathbb{F} = \mathbb{Z}_{p^k}$

#! Sage
p = random_prime(2^32)
k = randint(1, 5)
F = Zmod(p^k)
n = 5

y = F(randint(1, p^k))
#x = y.nth_root(n, all=True)
x = y.nth_root(n)
assert x^n == y
print(p, k, n)
print(x, y)

（会有不存在根的情况，多试几次就好了）

以上据说可以设个all=True，但试了一下好像并不能得到全部解

求1的所有n次方根·

既然已经有方法可以求出$y \equiv x^n \text{ in } \mathbb{F}$的一个解了，那么设$y = 1$（域中一定有单位元），就可以解出$1$的一个$n$次方根。

复习一下单位元的一些性质，单位元乘上任何数都等于这个数（$1 \cdot a \equiv a$），然后单位元自乘的话会得到单位元（$1 \cdot 1 \equiv 1$、$1^i \equiv 1$）。

姑且假设上面解出来的单位元的一个根为$u_0$，即$u_0^n \equiv 1 \text{ in } \mathbb{F}$。令$u_i = u_0^{i+1}$，对于$i = {0, 1, ..., n-1}$，就可以得到$u_0$~$u_{n-1}$的$n$个值。注意因为$u_{n-1} \equiv u_0^n \equiv 1$，所以$u_0 \equiv u_n$，形成一个循环，所以就不用考虑后面$i \ge n$的情况了。

接下来验证一下，$u_0$~$u_{n-1}$其实是单位元$1$的所有$n$次方根，

$$u_i^n \equiv (u_0^{i+1})^n \equiv (u_0^n)^{i+1} \equiv 1^{i+1} \equiv 1 \text{ (in $\mathbb{F}$)}$$

所以就可以解出$1$的所有$n$次方根。

求y的所有n次方根·

上面已经用nth_root解出了$y$的一个根，姑且令其为$x_0$。然后还解出了单位元的$n$个根$u_0$~$u_{n-1}$。

根据单位元$1 \cdot a \equiv a$的特性，$x_0 \cdot u_i$其实也是$y$的$n$次方根，因为

$$(x_0 u_i)^n \equiv x_0^n u_i^n \equiv y \cdot 1 \equiv y \text{ (in $\mathbb{F}$)}$$

于是令$x_i = x_0 \cdot u_i$，就可以得到y的所有n次方根$x_0$~$x_{n-1}$。

参考代码：

#! Sage
p = random_prime(2^32)
k = randint(1, 5)
F = Zmod(p^k)
n = randint(2, 10)
y = F(randint(1, p^k))

x = []
u = []
x0 = y.nth_root(n)
u0 = F(1).nth_root(n)
for i in range(n):
  u += [u0^(i+1)]
  x += [x0 * u[i]]

x = list(set(x))
for xi in x:
  assert xi^n == y

print('p = %d' % p)
print('k = %d' % k)
print('n = %d' % n)
print('y = %d' % y)
print('x = %s' % x)

Zn中的情况·

如果$N$不是素数的幂，$\mathbb{Z}_N$就不是一个域，所以需要转化成域（）。

首先要把$N$分解成$N = \sum p_i^{k_i}$的情况，然后分别解出域$\mathbb{Z}_{p_i^{k_i}}$中的根，再用这些根的笛卡尔积做一次CRT获得所有$\mathbb{Z}_N$上的根。

理论上是这样，但我发现nth_root可以直接解。。。

原理未明，有空逆一下（逃

好像是分解了N，试了一下大的N等很久都解不出来。

模板·

（2023.09.07更新）

有了上面思路就可以总结出几个函数，在比赛中就可以直接套模板，不用重新写一遍了。

下面我总结了几个函数

• root1用于求单位元的$n$次方，因为测试了一下有些数据用F(1).nth_root(n)会报NotImplementedError。大概原理是，先找一个生成元$g$（虽然好像不用生成元也可以），然后计算$u_0 \equiv g^{\varphi(p)/n} \pmod p$即可，简单验证一下是

  $$u_0^n \equiv g^{\frac{\varphi(p)}{n} \cdot n} \equiv g^{\varphi(p)} \equiv 1 \pmod p$$

• nth_p就是把上面思路整理成函数。

• nthRSA_p用于解模数是RSA的一个素因子的情况，因为常见的这种类型题目都是RSA，所以单独整理出一个模板。大概原理是，先提出$e$和$\varphi(p)$的公因子$r$，然后用$(\frac{e}{r})^{-1} \pmod {\varphi(p)}$作私钥解密一次得$c^r \pmod p$，再调用nth_p求出$r$个根。但是一些比较恶心的题目会给出$\text{GCD}(e/r, \varphi(p)) \ne 1$的情况，这就需要把这些不互素的$r_i$全部提取出来，再传进nth_p求根。

• nthRSA_n就是解RSA中$e$与$\varphi$不互素的模板，求解时需要先分解$N$。大概原理是凋nthRSA_p求出两个素数下$m$的可能，再做一次CRT。其中，可以从checker传进一个侦测器，这样的话只有在checker(m)为True时才会把m作为结果返回，否则返回所有的$m$，由调用者自己对结果进行处理，这样的话就需要所有的CRT做完，效率较低。ret1用于指示函数只返回符合checker的第一个结果，还是等待所有结果计算完毕再返回，如果确定你的checker只能check出唯一解，而且后面代码急着用这个结果的话就设为True吧。

• 后面给了两个参考的checker，checkHeader是在知道flag头的情况下检测$m$中是否含flag头，checkStr是检测$m$解码后是否全可见字符（也可自定义字典），如果输入n的话就是检测前n个是否是字典中字符，适合有padding的情况。但这两个侦测器都需要flag头或字典作为输入，为了方便我用生成器的方式生成侦测器（genHeaderChecker和genStrChecker），参考test中的样例生成即可。

#sage10
import itertools
from tqdm import tqdm
import libnum
import string

# TODO: not work for gcd(e//r, phi) \ne 1
def root1(n, p, k=1):
  F = Zmod(p^k)
  P = Integer(pow(p, k))
  phi = euler_phi(P)
  assert phi % n == 0
  
  while True:
    g = F.random_element()
    u0 = Integer(pow(g, phi//n, P))
    if pow(u0, n, P) == 1:
      return u0

def nth_p(y, n, p, k=1):
  assert is_prime(p)
  F = Zmod(p^k)
  x0 = F(y).nth_root(n)
  try:
    u0 = F(1).nth_root(n) 
  except: # if NotImplementedError...
    u0 = root1(n, p, k)
  x = []
  u = []
  for i in range(n):
    u += [u0^(i+1)]
    x += [Integer(x0 * u[i])]
  return list(set(x))

def nthRSA_p(c, e, p, k=1):
  assert is_prime(p)
  P = Integer(pow(p, k))
  phi = euler_phi(P)

  rs = []
  ei = e
  while True:
    r = gcd(phi, ei)
    if r == 1:
      break
    rs += [r]
    ei //= r
  r = product(rs)
  dr = (e // r).inverse_mod(phi)
  cr = pow(c, dr, P)
  return nth_p(cr, r, p, k)

def nthRSA_n(c, e, ps, ks=None, checker=None, ret1=False):
  # ps: p, q, ...
  assert isinstance(ps, list)
  if ks == None:
    ks = [1] * len(ps)
  else:
    assert len(ps) == len(ks)
  ms = [] 
  for i in range(len(ps)):
    mp = nthRSA_p(c, e, ps[i], ks[i]) 
    ms += [mp]
  total = product([len(x) for x in ms])
  print('[Log] Complexity = %d: %s' % (total, str([len(x) for x in ms])))

  res = []
  Ps = [ps[i]^ks[i] for i in range(len(ps))]
  for msi in tqdm(itertools.product(*ms), total=total):
    m = crt(list(msi), Ps)
    if checker == None:
      res += [m]
      continue
    if checker(m):
      if not ret1:
        res += [m]
        continue
      return m
  return res

def genHeaderChecker(hd):
  if isinstance(hd, str):
    hd = hd.encode() 
  assert isinstance(hd, bytes)
  def checkHeader(m):
    try:
      flag = libnum.n2s(int(m))
      if hd in flag:
        print(flag)
        return True
      return False
    except:
      return False
  return checkHeader

def genStrChecker(dict, n=65537):
  def checkStr(m):
    try:
      flag = libnum.n2s(int(m)).decode()
      for fi in flag[:n]:
        if not fi in dict:
          return False
      print(flag)
      return True
    except:
      return False
  return checkStr

def test(t):
  if t == 0:	# 2019 NCTF easyRSA
    e = 0x1337
    p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
    q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
    c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
    ps = [p, q]
    checker = genStrChecker(string.printable)
    res = nthRSA_n(c, e, ps, checker=checker)  # 11215150it
    print(res)
    for r in res:
      flag = libnum.n2s(int(r))
      print(flag)
  elif t == 1:  # 2023 YCB Danger_RSA
    e = 11079917583
    p = 5213351003420231819415242686664610206224730148063270274863722096379841592931572096469136339538500817713355302889731144789372844731378975059329731297860686270736540109105854515590165681366189003405833252270606896051264517339339578167231093908235856718285980689179840159807651185918046198419707669304960745217
    q = 3891889986375336330559716098591764128742918441309724777337583126578227827768865619689858547513951476952436981068109005313431255086775128227872912287517417948310766208005723508039484956447166240210962374423348694952997002274647622939970550008327647559433222317977926773242269276334110863262269534189811138319  
    c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766
    ps = [p, q]
    checker = genHeaderChecker('DASCTF')
    res = nthRSA_n(c, e, ps, checker=checker)
    print(res)
    for r in res:
      flag = libnum.n2s(int(r))
      print(flag)
  elif t == 2:  # 2022 QWB ASR
    e = 3
    c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
    ps = [
      218566259296037866647273372633238739089,
      223213222467584072959434495118689164399,
      225933944608558304529179430753170813347,
      260594583349478633632570848336184053653
    ]
    ks = [2] * 4
    checker = genStrChecker(string.printable, 48)
    res = nthRSA_n(c, e, ps, ks, checker=checker)    
    print(res)
    for r in res:
      flag = libnum.n2s(int(r))
      print(flag)
  elif t == 3:  # 2023 HWS random
    pr = [47890485652059026823698344598447161988085597568251161, 47890485652059026823698344598447161988085597568297951, 47890485652059026823698344598447161988085597568338059, 47890485652059026823698344598447161988085597568363667, 47890485652059026823698344598447161988085597568398337, 47890485652059026823698344598447161988085597568433917, 47890485652059026823698344598447161988085597568484111, 47890485652059026823698344598447161988085597568667099, 47890485652059026823698344598447161988085597568729849]
    upper = [5, 4, 3, 4, 3, 5, 1, 2, 3]
    n = 255550794734774347335455038653204099810524562323968101081052744238324333979282590769066826059535810339765419405089707653972316828518446466787073982991340735273047955757161722774546888128720663627716647123110956021905275918358574092054477588935546729192812379266210918802470144452212508255209922150559524376661512464064852413804511191503030046546647554981646983220695416838829085308878177824361071544916728725428437436959573167863053126718594118224053088660739173865895266537548733106779437480905737491231720771570860988017959907437998012442781279100256862684919251885437194156545435396952798548033193683684362049646718627530076461463826459504520525895649547513376441325848313193080013281816762156916219271109726593135112626577858906494025788770088106285316571255392298608980679161123528759865796345121056864973189231253364595956642612401745212207858555858704724770456899071144650909246822311039572915447866615638976747716646382091135281119109866295649034560378368202797914202112090339159898226929176034503535419893300159083361891627300767030933209665917744361038219820997348160094737332979677839131999258559999565207302339242257832022939036526481610130970477187338439181123984340269665409009894192138483254592729253191096427332283419085864095600303323775372526431524911842065699875575955728772820558157791292247976982470646890930951250598649964200733076634093613078091713383782021194766013790646324780327618195433827227105459480409797466859653960886570869469172506894631937612508518886406112758352094014377947728184352908630672750330561369500089138179794848896959683336195170519521
    c = 29259244746260903447574448389058952310000390135231599667104954615635954705912759181552349897154663199516384757779582324312559110410628822220097857204989378367616522573650610718867075518776621505865327181301059226036067398269476892575801933638458560523584293063843890012581096233699743704556897984235725492806550009731913445801481786988321848320254380607620726887530437151238556482879159888862341096974129499878601309077513908335631417136332585391767849651968095851808312565329858938394084369711172343300695636449663297542069122814607488273607842533010193498547579501368165500427762712900139188279259336486273788664239339542187191374015805659616093967428577968683677885747775540903578723024681500272919689849253480672194507905399890280339044782040395397922973935735424691828624724029439840506402735626398047317544972966643810550593849196291833043243448655939654884418027006572740130515844853007135331296523599052132266288322473865775521953742444721612389547052020839760259179074124960827686670217980159612966767064088131176654212504654177367329044762238432531402899949096987765334061101859346928585114984440559379578507872401025874782849854603895110182401204202962118890563473961321104811452539667609870771280348801335004559132482743318366689808669972965573335905879806817618597010442262336079838039317609336210571773187461470707420797827741277982208089496339300646565067740673242728353659143107970717482392927903021102141779217003523105389389513154792904745687959335115429159530013641777064904216646895961910784920181748841104318013067029395394948190384737300533803009402182800702
    e = 57564
    assert product([pr[i]^upper[i] for i in range(len(pr))]) == n
    checker = genHeaderChecker('flag')
    res = nthRSA_n(c, e, pr, upper, checker=checker)  # 825403/5971968
    print(res)
    for r in res:
      flag = libnum.n2s(int(r))
      print(flag)

 
if __name__ == '__main__':
  t = 2
  print('Testing: %d' % t)
  test(t)

不过模板还是有一些问题：

1. 需要SageMath10，不然会卡在F = Zmod(p^k)那里，SageMath10的安装方法可以参考我的SageMath 10.1 安装记录
2. root1并不能计算$\text{GCD}(e/r, \varphi(p)) \ne 1$的情况，如果遇到F(1).nth_root(n)报错且$\text{GCD}(e/r, \varphi(p)) \ne 1$的题目我再想想怎么编一个吧，能用就行（如果你实在想修的话可以参考春乎上的思路）

最后用了2019NCTF的easyRSA、2023羊城杯的Danger_RSA、2022强网杯的ASR和2023HWS冬令营的random做测试，

• easyRSA是F(1).nth_root(n)报错的情况，但没有$\text{GCD}(e/r, \varphi(p)) \ne 1$
• Danger_RSA是$\text{GCD}(e/r, \varphi(p)) \ne 1$，但F(1).nth_root(n)没有报错，凑合用了（虽然这题是抄Crypto CTF的Risk，但我懒得把Risk再做一遍了，抄个数据而已，）
• ASR是多素数RSA
• random也是多素数，多种次方

PS：另，在$m<p, q$的情况下，其实只需要对$p$或$q$求一次根，而不用做CRT，从而提高效率。

总结·

如果只是比赛的话上面的代码应该够用了，

坑还是没填啊喂（