复数域

XYCTF2025

Complex_signin

from Crypto.Util.number import *

from Crypto.Cipher import ChaCha20

import hashlib

from secret import flag

class Complex:

  def __init__(self, re, im):

    self.re = re

    self.im = im

  def __mul__(self, c):

    re_ = self.re * c.re - self.im * c.im

    im_ = self.re * c.im + self.im * c.re

    return Complex(re_, im_)

  def __eq__(self, c):

    return self.re == c.re and self.im == c.im

  def __rshift__(self, m):

    return Complex(self.re >> m, self.im >> m)

  def __lshift__(self, m):

    return Complex(self.re << m, self.im << m)

  def __str__(self):

    if self.im == 0:

      return str(self.re)

    elif self.re == 0:

      if abs(self.im) == 1:

        return f"{'-' if self.im < 0 else ''}i"

      else:

        return f"{self.im}i"

    else:

      return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

  def tolist(self):

    return [self.re, self.im]

def complex_pow(c, exp, n):

  result = Complex(1, 0)

  while exp > 0:

    if exp & 1:

      result = result * c

      result.re = result.re % n

      result.im = result.im % n

    c = c * c

    c.re = c.re % n

    c.im = c.im % n

    exp >>= 1

  return result

bits = 128

p = getPrime(1024)

q = getPrime(1024)

n = p * q

m = Complex(getRandomRange(1, n), getRandomRange(1, n))

e = 3

c = complex_pow(m, e, n)

print(f"n = {n}")

print(f"mh = {(m >> bits << bits).tolist()}")

print(f"C = {c.tolist()}")

print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

'''

n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753

mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]

C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]

enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'

'''

拿到题目我们先审计一波代码

想要恢复明文我们需要先获取到m的实部和虚部，然后解密ChaCha20加密，对于最后一步的解密是很简单的，关键就是恢复m的实部和虚部

m = Complex(getRandomRange(1, n), getRandomRange(1, n))

mh = {(m >> bits << bits).tolist()}

这里的m是个复数，而且这里很明显是m的高位泄露

那么接下来要干的事就很清晰了

既然是在复数域下，那我们就有 m = re + im * i 那么这里的高位泄露就可以表示为 $$ \begin{aligned} re &= mh\_re + x \\ im &= mh\_im + y \end{aligned} $$ 加密过程非常简单 c = m³ (mod  n) 那么这里就是复数的立方了 m³ = (re + im ⋅ i)³ = (re³ − 3 ⋅ re ⋅ im²) + (3 ⋅ re² ⋅ im − im³) ⋅ i 这里出题的预期是解结式然后cooper，但是二元cooper可以直接出了,那么我们只用利用实部来列方程就好

我们设re的低位是x,im的虚部是y，则有方程 c = (re + x)³ − 3 * （re + x） * (im + y)² 这里利用二元cooper解出x,y我们就可以成功恢复m了

接下来就是解ChaCha20了。这个没啥说的了

这里对系数稍微解释一下m是移位，也就是格的维度，d代表的是方程中最高系数的幂

对于128位的泄露，通常我们m=2或者3，这里最高次幂是3，毫无疑问的d=3

from sage.all import *

from Crypto.Cipher import ChaCha20

import hashlib

import itertools

def small_roots(f, bounds, m=1, d=None):

  if not d:

    d = f.degree()

  R = f.base_ring()

  N = R.cardinality()

  f /= f.coefficients().pop(0)

  f = f.change_ring(ZZ)

  G = Sequence([], f.parent())

  for i in range(m + 1):

    base = N ^ (m - i) * f ^ i

    for shifts in itertools.product(range(d), repeat=f.nvariables()):

      g = base * prod(map(power, f.variables(), shifts))

      G.append(g)

  B, monomials = G.coefficient_matrix()

  monomials = vector(monomials)

  factors = [monomial(*bounds) for monomial in monomials]

  for i, factor in enumerate(factors):

    B.rescale_col(i, factor)

  B = B.dense_matrix().LLL()

  B = B.change_ring(QQ)

  for i, factor in enumerate(factors):

    B.rescale_col(i, 1 / factor)

  H = Sequence([], f.parent().change_ring(QQ))

  for h in filter(None, B * monomials):

    H.append(h)

    I = H.ideal()

    if I.dimension() == -1:

      H.pop()

    elif I.dimension() == 0:

      roots = []

      for root in I.variety(ring=ZZ):

        root = tuple(R(root[var]) for var in f.variables())

        roots.append(root)

      return roots

  return []

n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753

mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]

C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]

enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'

mh_re,mh_im=mh

R.<x,y> = PolynomialRing(Zmod(n))

f = (mh_re+x)^3-3*(mh_re+x)*(mh_im+y)^2 - C[0]

res=small_roots(f,(2^128,2^128),m=2,d=3)   

print(res)

m_re=mh_re+int(res[0][0])

m_im=mh_im+int(res[0][1])

flag = ChaCha20.new(key=hashlib.sha256(str(m_re + m_im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc).decode()

print(flag)
#[(200140573956551184845123803212115015633, 62109784561410747979732334460991877433)]
#XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}

XYCTF2025

Complex_dlp

from Crypto.Util.number import *

from secrets import flag

class Complex:

  def __init__(self, re, im):

    self.re = re

    self.im = im

  def __mul__(self, c):

    re_ = self.re * c.re - self.im * c.im

    im_ = self.re * c.im + self.im * c.re

    return Complex(re_, im_)

  def __str__(self):

    if self.im == 0:

      return str(self.re)

    elif self.re == 0:

      if abs(self.im) == 1:

        return f"{'-' if self.im < 0 else ''}i"

      else:

        return f"{self.im}i"

    else:

      return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

def complex_pow(c, exp, n):

  result = Complex(1, 0)

  while exp > 0:

    if exp & 1:

      result = result * c

      result.re = result.re % n

      result.im = result.im % n

    c = c * c

    c.re = c.re % n

    c.im = c.im % n

    exp >>= 1

  return result

flag = flag.strip(b"XYCTF{").strip(b"}")

p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027

g = Complex(3, 7)

x = bytes_to_long(flag)

print(complex_pow(g, x, p))

\# 5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908i

先来看一个性质

对于一个复数来说 c = a + b ⋅ i 它的模长是 $$ \left |c \right |=\sqrt{a^{2}+b^{2}} $$ 那么对于它的平方也就是 c² = (a² − b²) + 2ab ⋅ i 它模长是 $$ \left |c^{2} \right |=\sqrt{(a^{2}-b^{2})^{2}+4a^{2}b^{2}}=a^{2}+b^{2} $$ 这里我们可以看复数平方的模长就是复数模长的平方，那么对于其他次幂能否满足这一条件呢,那当然也是满足的，这里就不在证明了，回到这道题 (3 + 7 ⋅ i)^x ≡ (c_re + c_im) mod  p 这里利用上面的性质 |3 + 7 ⋅ i|^x ≡ |(c_re + c_im)| mod  p 那么这里还有一个问题模长的根号内部不是二次剩余，所以我选择把模长平方掉 |(3 + 7 ⋅ i)²|^x ≡ |(c_re + c_im)²| mod  p

p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027

g = 3^2 + 7^2
a = 5699996596230726507553778181714315375600519769517892864468100565238657988087817 
b = 198037503897625840198829901785272602849546728822078622977599179234202360717671908
c = (a^2 + b^2) % p

x = discrete_log(mod(c,p),mod(g,p))
flag = b"XYCTF{" + bytes.fromhex(hex(int(x))[2:]) + b"}"
print(flag)

# XYCTF{___c0mp13x_d1p_15_3@5y_f0r_y0u___}

这个写法好理解一点，这是Dexter师傅的

这个是我的

p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027

re=5699996596230726507553778181714315375600519769517892864468100565238657988087817

im=198037503897625840198829901785272602849546728822078622977599179234202360717671908

G=GF(p^2)

g=G(3^2+7^2)

c=G(re^2+im^2)

x = discrete_log(c,g)

flag = b"XYCTF{" + bytes.fromhex(hex(int(x))[2:]) + b"}"

print(x)

print(flag)