Cryptography趣题记录

这里也记录一下，各种比赛零零散散的题目(觉得比较有意思的)

KalmarCTF2025 - basic sums

with open("flag.txt", "rb") as f:
    flag = f.read()

# I found this super cool function on stack overflow \o/ https://stackoverflow.com/questions/2267362/how-to-convert-an-integer-to-a-string-in-any-base
def numberToBase(n, b):
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    return digits[::-1]

assert len(flag) <= 45

flag = int.from_bytes(flag, 'big')

base = int(input("Give me a base! "))

if base < 2:
    print("Base is too small")
    quit()
if base > 256:
    print("Base is too big")
    quit()

print(f'Here you go! {sum(numberToBase(flag, base))}')

题目代码非常简单，我们会得到flag转换为n进制之后的数字之和，可以写成下面的形式

$flag=a_{n}b^{n}+a_{n-1}b^{n-1}+a_{n-2}b^{n-2}+...+a_{0}b^{0}$
$同时，不难看出有$
$flag\equiv sums\equiv a_{n}+a_{n-1}+a_{n-2}+...+a_{1}+a_{1}(mod\ b-1)$

上面是我们选择的进制之间的最小公倍数，下面是flag的近似大小(肯定要比这个大)

所以，当模数足够大的时候，flag模它才能得到本身，同时我们也有

$flag\equiv sums\ mod\ (b-1)$

$flag\equiv m\ mod\ lcm(n,b-1)$

在b不断增大的情况下，对m不断地进行crt结果的合并，当最小公倍数增大到模数大于flag的值时，我们才能获取到flag的唯一解

$flag=crt([m,sums],[lcm(n,b-1),b-1])$

# sage
from pwn import *
from tqdm import trange

context(os='linux', arch='amd64', log_level='debug')
m = 0
n = 1
for i in trange(2,256):
    p = remote('basic-sums.chal-kalmarc.tf', 2256)
    p.sendlineafter(b'Give me a base! ',str(i).encode())
    p.recvuntil(b'go! ')
    m0 = int(p.recvline())
    n0 = i-1
    m = crt([m,m0],[n,n0])
    n = lcm(n,n0)
    p.close()
print(long_to_bytes(int(m)))
# b'kalmar{At_least_it_wasnt_lattices_right???!?}'

这图片起到了一定的迷惑作用，我还以为要构造格才做的出来，我寻思着我这格构造的好像也不怎么行啊，而且这么多组数据，要怎么整呢，然后就看到春哥做出来了，牛批！！！

所以上面其实是我看了春哥写的文档之后，思考了一番(过程应该没问题)，觉得挺有意思的记录一下OvO

TPCTF2025 - randomized random

# FROM python:3
import random
with open("flag.txt","rb") as f:
    flag=f.read()
for i in range(2**64):
    print(random.getrandbits(32)+flag[random.getrandbits(32)%len(flag)])
    input()

看到getrandbits，可以立马想到MT19937，这里的话因为两个随机数“加”起来了，我们不好处理，但是可以看做是我们可以得到不连续的随机数中的高24位，但看了师傅们的wp都说了实际测试发现影响到了低20位，所以取得是高12位

然后就是不连续的MT19937

待我有空再钻研钻研

2024第四届长城杯 - RandomRSA

题目描述：A特工从敌方服务器获取到了一份带有hint的机密文件，请协助破解加密。

import gmpy2
import random
from secret import flag
from Crypto.Util.number import *


class LCG:
    def __init__(self, p, a, b):
        self.p = p
        self.a = a
        self.b = b
        self.x = random.randint(0, p-1)
        print(self.p, self.a, self.b)

    def next(self):
        self.x = (self.a*self.x+self.b) % self.p
        return self.x


def getPrimes(bits, k):
    p = getPrime(bits)
    a = random.randint(0, p-1)
    b = random.randint(0, p-1)
    l = LCG(p, a, b)
    return [gmpy2.next_prime(l.next()) for _ in range(k)]


p, q = getPrimes(1024, 2)
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(n, c)
'''
p = 170302223332374952785269454020752010235000449292324018706323228421794605831609342383813680059406887437726391567716617403068082252456126724116360291722050578106527815908837796377811535800753042840119867579793401648981916062128752925574017615120362457848369672169913701701169754804744410516724429370808383640129
a = 95647398016998994323232737206171888899957187357027939982909965407086383339418183844601496450055752805846840966207033179756334909869395071918100649183599056695688702272113280126999439574017728476367307673524762493771576155949866442317616306832252931038932232342396406623324967479959770751756551238647385191314
b = 122891504335833588148026640678812283515533067572514249355105863367413556242876686249628488512479399795117688641973272470884323873621143234628351006002398994272892177228185516130875243250912554684234982558913267007466946601210297176541861279902930860851219732696973412096603548467720104727887907369470758901838
n = 5593134172275186875590245131682192688778392004699750710462210806902340747682378400226605648011816039948262008066066650657006955703136928662067931212033472838067050429624395919771757949640517085036958623280188133965150285410609475158882527926240531113060812228408346482328419754802280082212250908375099979058307437751229421708615341486221424596128137575042934928922615832987202762651904056934292682021963290271144473446994958975487980146329697970484311863524622696562094720833240915154181032649358743041246023013296745195478603299127094103448698060367648192905729866897074234681844252549934531893172709301411995941527
c = 2185680728108057860427602387168654320024588536620246138642042133525937248576850574716324994222027251548743663286125769988360677327713281974075574656905916643746842819251899233266706138267250441832133068661277187507427787343897863339824140927640373352305007520681800240743854093190786046280731148485148774188448658663250731076739737801267702682463265663725900621375689684459894544169879873344003810307496162858318574830487480360419897453892053456993436452783099460908947258094434884954726862549670168954554640433833484822078996925040310316609425805351183165668893199137911145057639657709936762866208635582348932189646
'''

$x\equiv ax+b\%p$
$p'\equiv(x+k1)\%p$
$q'\equiv(ax+b+k2)\%p$
$p'*q'-n\equiv ax^{2}+(b+k2+ak1)x+bk1+k1k2-n\equiv0\%p$
abpn已知，k1k2是小数可爆破，那就解x的一元二次方程即可

这里得开多线程搞一手……

reference

https://tover.xyz/p/2024-ccb-RandomRSA/
http://www.andynoel.xyz/?p=904
https://blog.csdn.net/Jayjay___/article/details/142059111

TGCTF2025 - EZRSA

from secrets import flag, get_random_emojiiiiii
from Crypto.Util.number import *


def genarate_emojiiiiii_prime(nbits, base=0):
    while True:
        p = getPrime(base // 32 * 32) if base >= 3 else 0
        for i in range(nbits // 8 // 4 - base // 32):
            p = (p << 32) + get_random_emojiiiiii()  # 猜一猜
        if isPrime(p):
            return p


m = bytes_to_long(flag.encode(
) + "".join([long_to_bytes(get_random_emojiiiiii()).decode() for _ in range(5)]).encode())
p = genarate_emojiiiiii_prime(512, 224)
q = genarate_emojiiiiii_prime(512)

n = p * q
e = "💯"
c = pow(m, bytes_to_long(e.encode()), n)

print("p0 =", long_to_bytes(p % 2 ** 256).decode())
print("n =", n)
print("c =", c)
# p0 = 😘😾😂😋😶😾😳😷
# n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
# c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401

可以看到p相当于一个224位的素数拼接9个emoji符号而来，而get_random_emojiiiiii()这个函数我们未知

这里是p的低位泄露攻击，我们知道了p一半的位数，尝试后我们可以发现256位似乎不够我们进行攻击

(部分情况下，1024位需要知道576比特位，512位需要知道288比特位，有的又是需要256位再多一个字节，d的泄露需要知道至少1/4的比特位，视情况而定吧)

可以看到p的低8字节已经给出，而我们还可以再爆破出高一个字节，查阅emoji符号的范围，我们得到以下脚本

# sage
from Crypto.Util.number import *
from tqdm import trange

e = bytes_to_long("💯".encode())
p0 = bytes_to_long("😘😾😂😋😶😾😳😷".encode())
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
PR.<x> = PolynomialRing(Zmod(n))
for i in trange(0xf09f9880,0xf09f998f):
    p00 = i*2^256 + p0
    f = x*2^288+p00
    f = f.monic()
    roots = f.small_roots(X = 2**224,beta=0.4,epsilon=0.02)
    if roots:       
        p = int(roots[0])*2^288 + p00
        q = n // p
        print(f"{p = }")
        print(f"{q = }")
        break

然后就是$e与\phi 不互素$，上板子即可

# sage
from sage.all import *
from sage.parallel.multiprocessing_sage import parallel_iter    # TODO
import itertools
from tqdm import tqdm
from Crypto.Util.number import *
import string

def nth_p(y, n, p, k=1):
  assert is_pseudoprime(p)
  print('[LOG] Solving pi = %s^%d' % (hex(p), k))
  try:
    xs = Zmod(p**k)(y).nth_root(n, all=True)
  except:
    xs = GF(p**k)(y).nth_root(n, all=True)
  xs = list(set(xs))
  xs = [Integer(x) for x in xs]
  return xs

def nthRSA_p(c, e, p, k=1):
  assert is_pseudoprime(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] Doing crt.\nComplexity = %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 = long_to_bytes(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 = long_to_bytes(int(m)).decode()
      for fi in flag[:n]:
        if not fi in dict:
          return False
      print(flag)
      return True
    except:
      return False
  return checkStr

p = 12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311
q = 12602471198163266643743702664647336358595911975665358584258749238146841559843060594842063473155049870396568542257767865369797827796765830093256146584311989
e = bytes_to_long("💯".encode())
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401

ps = [p, q]
checker = genHeaderChecker('TGCTF')
res = nthRSA_n(c, e, ps, checker=checker)
for r in res:
  flag = long_to_bytes(int(r))
  print(flag.decode())
# TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢

LitCTF2025 - leak(dp高位泄露广义解法)

from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
p,q,e = getPrime(1024),getPrime(1024),getPrime(101)
n = p*q
temp = gmpy2.invert(e,p-1)
c = pow(m,e,n)
hint = temp>>180
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
print(f"hint = {hint}")
'''
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
'''

$e*dp\equiv 1(mod\ p-1)$
$e*(dp\_high+x)=k*(p-1)+1$
$e*(dp\_high+x)+k-1\equiv 0(mod\ p)$
因为这里e太大了，我们打不了一元copper，那就直接打二元copper

奇怪的是，m代表移位位数，d代表多项式的最高次幂，但这里只能为3才能跑出flag

$2^{e*dp}\equiv 2(mod\ p)$
$p=GCD(2^{e*dp}-2,n)$

# sage
from sage.all import *
from Crypto.Util.number import *
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 []

e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
leak = hint << 180
PR.<x,y>=PolynomialRing(Zmod(n))
f = e*(leak + x) + y -1
res = small_roots(f, (2^180,2^e.bit_length()),m=1,d=3)
for root in res:
    dp = leak + root[0]
    p = GCD(pow(2, e*dp, n) -2, n)
    q = n // p
    d = inverse(e, (p-1)*(q-1))
    m = pow(c, d, n)
    print(long_to_bytes(m).decode())