large case·

题目：https://paste.ubuntu.com/p/DcPKKSdT9y/

题目是个3-RSA，每个素数1024bits，即 $|n|=2^{1024*3}$ ； $e$ 未知，但可以知道是 $p-1$ 、 $q-1$ 和 $r-1$ 中各取一个因子做乘积（第一个assert）； $m$ 在pad前的长度为 $2^{1024}<m<2^{2048}$ （第二个assert）， $m$ 在pad后是 $|m|=2^{1024*3}$ （即与 $n$ 同量级，看pad函数）；flag里含SUSCTF（第三个assert）。

首先要解决的是 $e$ 的求值，先假设 $e$ 的三个分量为： $e=e_pe_qe_r$ ，假设 $e_pg_p=p-1$ ，推一下可得：

$e = e_pe_qe_r \\ e = \frac{p-1}{g_p}e_qe_r \\ eg_p = (p-1)e_qe_r \\ eg_p \equiv 0 \pmod {p-1} \\ c^{g_p} \equiv m^{e_pg_p} \equiv m^0 \equiv 1 \pmod p$

由于 $e_p$ 是 $p-1$ 的一个因子，那么就可以对于 $p-1$ 的每一个因子 $p_i$ ，先计算 $g_{pi}$ ，然后检测 $c^{g_{p_i}} \pmod p$ 是否为 $1$ ，若是的话则 $e_p=p_i$ ；当然，这样做的前提是 $p-1$ 可以分解，事实也确实可以分解（但其实接下来的做法需要 $e_p$ 是个较小的值，所以不用完全分解也行）； $q$ 和 $r$ 也是同样的操作，最终得出 $e_p=757$ 、 $e_q=66553$ 、 $e_r=5156273$ 。（其实解 $e_q$ 和 $e_r$ 时还有个 $2$ 的，但因为算 $e_p$ 时没有出现 $2$ ，且 $e$ 的三个分量都是素数，所以可以忽略，简单的逻辑推理-）

fp = [2, 7, 757, 1709, 85015583, 149105250954771885483776047, 339028665499, 1642463892686572578602085475101104723805585678675707586553009837707279291648160744722745420570786735582631019452016654157586623543454908938807521637550223579103317696104438456966780396624343550451096013730928292041667133825444056448136643704677066463120079]
for fpi in fp:
  if pow(cp, (p-1)//fpi, p) == 1:
    print(fpi)  # 757

fq = [2, 2, 3, 3, 66553, 84405986771, 81768440203, 38037107558208320033, 16137718604846030589135490851713, 14369576056311038198362075935199486201201115381094289671031774994452214307042971166730146897009438957078052300683916910041250723573953110349566216311685009675744215421971185909678546052934704709232060199286321405045769976194110037]
for fqi in fq:
  if pow(cq, (q-1)//fqi, q) == 1:
    print('fqi: %s' % fqi)  # 2, 66553

fr = [2, 11607389, 5156273, 10012111, 68872137169799749, 12030248809636768339, 9691125310820433463, 31518759824860728158228953]  # 547187028373506113438510511293209786101461141918516130626947626757753454448192055890412658699775890681515562519111190252566146302544199621791901997687741038739625529014337424946054655263007302018300326403871]
for fri in fr:
  if pow(cr, (r-1)//fri, r) == 1:
    print('fri: %s' % fri)  # 2, 5156273

然后要解决的第二个问题是， $gcd(e, \varphi(n)) \ne 1$ ，即 $e$ 与 $\varphi(n)$ 是不互素的，即不能使用通过求逆算出私钥 $d$ 的方法来解，之前做过Elgamal的话就知道是经典AMM解法了，类似的解法，先以 $p$ 作例子：由于AMM不能解太大的指数，所以要先降低指数的规模，由于 $e=e_pe_qe_r$ 中，只有 $e_p$ 与 $p-1$ 是不互素的，所以可以通过求 $m_p \equiv m^{e_p} \equiv c^{(e_qe_r)^{-1} \pmod {p-1}} \pmod p$ ，把指数降到 $e_p=757$ ； $q$ 和 $r$ 同理。

虽然上一步是把指数降下来了，但是 $e_r=5156273$ 还是太大了（反正我电脑跑了半天都还没出- -），需要优化一下，刚好题目里 $m$ 的大小的条件还没用。看一下pad函数，是在message后面pad\x00，用公式来说就是 $m_{pad} = m_{ori} * 2^{1024}$ ，如果能把 $2^{1024}$ 去掉的话刚好就不需要 $r$ 的分量，也就不用管 $e_r$ 了；去掉的方法就是RSA的CCA攻击：

$c \equiv m_{pad}^{e} \equiv (m_{ori}*2^{1024})^e \equiv m_{ori}^e (2^{1024})^e \pmod {n} \\ c' \equiv c*((2^{1024})^{-1})^e \equiv m_{ori}^e \pmod {n}$

另：这里”不需要 $r$ 的分量“的意思是，最后我是需要用CRT来合成 $m$ 的，如果只求了 $m_p$ 和 $m_q$ 的话，只能知道 $m_{pad} \pmod {pq}$ ，回损失数据；但是如果我用 $c'$ 求的话，由于 $m_{ori}$ 比 $pq$ 小，则不会损失数据。

最终代码（AMM抄了Arpe1s的代码）：

#sage
from Crypto.Util.number import *
import libnum
import random
import time

p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n = p*q*r
c = 2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
cp = c % p
cq = c % q
cr = c % r
    
ep = 757
eq = 66553
er = 5156273
e = ep*eq*er

L = 128

# AMM
def eth_root(x, e, p):
    assert isPrime(p)
    assert (p - 1) % e == 0
    assert (p - 1) % (e**2) != 0

    l = (p - 1) % (e**2) // e
    a = -libnum.invmod(l, e) % e
    return pow(x, (1 + a * (p - 1) // e) // e, p)

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p, e):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        #print('debug -> %d' % pow(root, e3, p))
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

pad = 1 << (L*8)
c = ( c * pow(libnum.invmod(pad, n), e, n) ) % n
cp = c % p
cq = c % q
cr = c % r

dqr = libnum.invmod(eq*er, p-1)
mpp = pow(cp, dqr, p)  # m ^ ep % p
mp0 = eth_root(mpp, ep, p)
assert pow(mp0, ep, p) == mpp
proot = findAllPRoot(p, ep)
mps = findAllSolutions(mp0, proot, mpp, p, ep)
# cp = mp ^ e % p

dpr = libnum.invmod(ep*er, q-1)
mqq = pow(cq, dpr, q)  # m ^ eq % q
mq0 = eth_root(mqq, eq, q)
assert pow(mq0, eq, q) == mqq
qroot = findAllPRoot(q, eq)
mqs = findAllSolutions(mq0, qroot, mqq, q, eq)
# cq = mq ^ e % q

for mp in mps:
  for mq in mqs:
    m = crt([int(mp), int(mq)], [p, q])
    flag = libnum.n2s(int(m))
    if b'SUSCTF' in flag:
      print(flag)

（渣机跑了大概半小时- -）

InverseProblem·

题目：https://paste.ubuntu.com/p/fNYd2zZH6c/

题目挺短的，简单来看就是 $Ax=b$ ， $x$ 是flag， $A$ 是已知矩阵（gravity跑一次就出来了）， $b$ 已知（b.txt），正常来说求个逆就可以拿 $x$ 了，但是，看一下b.txt的话， $b$ 是小数，输出是使用了科学计数法，有精度损失，所以问题转化为： $Ax+e=b$ ， $e$ 未知，经典LWE问题。

解的时候要注意 $A$ 和 $b$ 的元素都是小数，调LLL需要整数，所以需要乘上一个大的 $N$ ，然后取整，即转化为： $⌊NA⌋x + ⌊Ne⌋ = ⌊Nb⌋$ （大概这个意思，能看懂就好-）

最后代码（抄了之前博客写的代码）

# sage
import numpy as np

NN = 2^100
b = [3.657060500339054556, 3.832239212422502419, 4.006400878420690219, 4.178419900792603698, 4.347228858757071634, 4.511847676148433948, 4.671407458110251127, 4.825167947918074560, 4.972528090932780174, 5.113029695817293714, 5.246354631948004226, 5.372316391653928349, 5.490847173300799113, 5.601981891814167511, 5.705840667157972348, 5.802611340293560716, 5.892533389518160902, 5.975884263745526823, 6.052968650055386206, 6.124110630374365201, 6.189648165161182760, 6.249928981118596312, 6.305306816020913629, 6.356137112146116124, 6.402771610768811570, 6.445551788138646998, 6.484801562386791147, 6.520820067831411961, 6.553875449515115861, 6.584200543535777115, 6.611991006926840555, 6.637406026122149569, 6.660571276935107790, 6.681583443270599219, 6.700515409542964562, 6.717421256877905762, 6.732340393774057929, 6.745300469406174670, 6.756319058650934721, 6.765404381911505425, 6.772555468921494821, 6.777762178159265432, 6.781005372262200126, 6.782257385537030814, 6.781482768722584069, 6.778639205835502253, 6.773678481496929180, 6.766547414782241958, 6.757188729437999655, 6.745541865153842309, 6.731543734407333659, 6.715129401333222177, 6.696232624726493441, 6.674786187460366591, 6.650721936401939729, 6.623970470419692447, 6.594460419709976122, 6.562117241643640000, 6.526861416758931682, 6.488605883801759546, 6.447252539940367342, 6.402687687915280321, 6.354776457871529374, 6.303356463148024886, 6.248231231031890047, 6.189164222318630664, 6.125874450187269531, 6.058034773416537746, 5.985273843207024811, 5.907182434535461653, 5.823324532363482149, 5.733253130130134423, 5.636530294391988036, 5.532750701442269019, 5.421567579447032585, 5.302719786604150158, 5.176058598538473916, 5.041572643016256734, 4.899409301857818377, 4.749890824218749685, 4.593523418788242338, 4.430997787892412703, 4.263179996640761260, 4.091092256773656004, 3.915884105025300528]  
b = [int(NN * i * 1e+02) for i in b]
b = vector(ZZ, b)
n = len(b)

def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j] = int( NN * (d/n*(d**2+((i-j)/n)**2)**(-1.5)) )
    return A

A = gravity(n)
A = matrix(ZZ, A)
#Ai = A.inverse()
#print(Ai * b)
 
z = matrix(ZZ, [0 for _ in range(n)]).transpose()
beta = matrix(ZZ, [10])
T = block_matrix([[A, z], [matrix(b), beta]])


L = T.LLL()
print(L[0])
e = vector(ZZ, L[0][:n])
#print(e)

x = A.solve_right(b-e)
print(x)

m = ''.join(chr(i) for i in x)
print('m = %s' % m)

手速够快，有幸三血（

SpecialCurve3 （1/3）·

题目：https://paste.ubuntu.com/p/tSGwsxRVYx/

题目是一个魔改的椭圆曲线，解ECDLP问题，给了三种情况，最后只解了一种；论文都找到了，就是不会写代码（逃

首先恢复一下曲线（虽然恢复了还没用到），看problem函数里 $b$ 参数的选取可推曲线为： $y^2 = ax^2 - bx \pmod p$ ，还可以验算一下，add里面计算的 $t$ 大概率是斜率（参考正常的ECC加法），那么P1==P2情况下的 $t$ 就是通过求偏导得出的，验证一下曲线确实是 $y^2 = ax^2 - bx \pmod p$ ，然后加法的结果好像是直线 $ax-ty=b$ 与直线 $y=tx$ 的交点。

然后分别算下三条曲线下的群阶，在@Csome的帮助下得出了k=0时群阶恒为p的结论，然后瞎试了一下，最终得出：e1的群阶是 $p-1$ 、e2的群阶是 $p$ 、e3的群阶是 $p+1$ 。

对应的三种情况其实（应该）就是这篇文章第四章里的三种情况：阶为 $p-1$ 的话好像可以把群同态到 $\mathbb{Z}_p^*$ 上；阶为 $p$ 的话是Smart攻击；阶为 $p+1$ 的话好像是Supersingular的攻击，但这里的话 $p+1$ 刚好可以分解成一堆小素数，就可以Pohlig-Hellman求解。

前两个不会改代码，只搞了最后一个：

from Crypto.Util.number import *
import hashlib
import random

class SpecialCurve:
    def __init__(self,p,a,b):
        self.p=p
        self.a=a
        self.b=b

    def __str__(self):
        return f'SpecialCurve({self.p},{self.a},{self.b})'

    def add(self,P1,P2):
        x1,y1=P1
        x2,y2=P2
        if x1==0:
            return P2
        elif x2==0:
            return P1
        elif x1==x2 and (y1+y2)%self.p==0:
            return (0,0)
        if P1==P2:
            t=(2*self.a*x1-self.b)*inverse(2*y1,self.p)%self.p
        else:
            t=(y2-y1)*inverse(x2-x1,self.p)%self.p
        x3=self.b*inverse(self.a-t**2,self.p)%self.p
        y3=x3*t%self.p
        return (x3,y3)

    def mul(self,P,k):
        assert k>=0
        Q=(0,0)
        while k>0:
            if k%2:
                k-=1
                Q=self.add(P,Q)
            else:
                k//=2
                P=self.add(P,P)
        return Q

    def p(self):
        return self.p

curve3=SpecialCurve(52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051,28655236915186704327844312279364325861102737672471191366040478446302230316126579253163690638394777612892597409996413924040027276002261574013341150279408716,42416029226399083779760024372262489355327595236815424404537477696856946194575702884812426801334149232783155054432357826688204061261064100317825443760789993)
G3=(15928930551986151950313548861530582114536854007449249930339281771205424453985946290830967245733880747219865184207937142979512907006835750179101295088805979, 29726385672383966862722624018664799344530038744596171136235079529609085682764414035677068447708040589338778102975312549905710028842378574272316925268724240)
Q3=(38121552296651560305666865284721153617113944344833289618523344614838728589487183141203437711082603199613749216407692351802119887009907921660398772094998382, 26933444836972639216676645467487306576059428042654421228626400416790420281717654664520663525738892984862698457685902674487454159311739553538883303065780163)
enc=4161358072766336252252471282975567407131586510079023869994510082082055094259455767245295677764252219353961906640516887754903722158044643700643524839069337

assert curve3.mul(G3, curve3.p+1) == (0, 0)
factors = [2, 2, 2663, 5039, 14759, 18803, 21803, 22271, 22307, 23879, 26699, 35923, 42727, 48989, 52697, 57773, 58129, 60527, 66877, 69739, 74363, 75869, 79579, 80489, 81043, 81049, 82531, 84509, 85009, 91571, 96739, 98711, 102481, 103357, 103981]

n = curve3.p+1
e3s = []
for pi in factors:  # all primes
  print(pi)
  Gi = curve3.mul(G3, n//pi)
  Qi = curve3.mul(Q3, n//pi)
  for e3i in range(pi):
    if curve3.mul(Gi, e3i) == Qi:
      e3s.append(e3i)
      break
  else:
    print('ERROR')
    exit(-1)

e3 = crt(e3s, factors) % n
print(e3)

print(Q3 == curve3.mul(G3, e3))

补充·

原来是圆锥曲线不是椭圆曲线，难怪一直没找到（：

前两种情况都在这里有说了

https://www.jiamisoft.com/blog/4068-yuanzhuiquxianjiamisuanfa.html

总结·

菜（：