[HNCTF 2022 WEEK4]square

题目

from flag import flag
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
flag = pad(flag,16)

m = int.from_bytes(flag,'big')
n = getPrime(2048)
e = 16
c = pow(m,e,n)


with open('output.txt','w') as f:
    f.write(f'n = {hex(n)}\n')
    f.write(f'e = {hex(e)}\n')
    f.write(f'c = {hex(c)}\n')

'''
n = 0xcaea4e2db0dc68029999cdad792fa1f9142117163af28f3230f7500ef748841554141ef35555ba23b95dc87f4c83f75dad14b6204dd4907fb75650fa7799def911f077b945f359e345bb9350c4a8268906c547e95e5819ef44ff124566a88fa2174ddfe3e895016df0036b59a50c6efb78724bde5d16a8a5cae45c918f329e462d10abe56ecdfae95bd13665260d0e8b648540d11f2447eef9aef3ea370faaecaab4c82ec1fe2bc83f2ce1b2793d95187eb2637e75700ba9745c253e928a4a603139dbf6b8bbf8111900a58be21a269992a9744c0284cf8f3ad7a3b95106d17af6baceac1acf543e425dc6317ab7f799a8ce19633b22e709eacb5d74ce4b56f9
e = 0x10
c = 0x2700a92e463d1c5da073b38d075a2da57c89ff9d658066c0bd38391cc60259a4fc992f1a6f1c5756d6e5934831fc0fbf7bfd85607f0d18781d30a4ab485e119af4f08b5fe7bf927aeaf7572b05dfec764d6ddda2b247b9f6b731300ece4209606d94c5708388d6e8efc1fa6e9c0cdda41cee95eb4a6b053b862fc43e55648973863f9874ee79ce4408277c9dc38fb26b44880e58f054b957c64fcf0d39c1fd496ad2fc5f5e5e70ba41422a4d945da299b5a695a4b7013a1f9ae1b629e395ffb0942d783d6e6be1f0888dfcb02d0aa1e9b7076e952a339bdc60f044f598afa2da28a4d7f094b959c8a8fefd5a11d10971cd681722f6868cf15a200cb910c591e1
'''

题解

#有限域开方，C=m^e(mod n)---->f(x)=x^e-c求出所有可能的根

wp

#sage
from Crypto.Util.number import long_to_bytes
import gmpy2

"""n = 0xcaea4e2db0dc68029999cdad792fa1f9142117163af28f3230f7500ef748841554141ef35555ba23b95dc87f4c83f75dad14b6204dd4907fb75650fa7799def911f077b945f359e345bb9350c4a8268906c547e95e5819ef44ff124566a88fa2174ddfe3e895016df0036b59a50c6efb78724bde5d16a8a5cae45c918f329e462d10abe56ecdfae95bd13665260d0e8b648540d11f2447eef9aef3ea370faaecaab4c82ec1fe2bc83f2ce1b2793d95187eb2637e75700ba9745c253e928a4a603139dbf6b8bbf8111900a58be21a269992a9744c0284cf8f3ad7a3b95106d17af6baceac1acf543e425dc6317ab7f799a8ce19633b22e709eacb5d74ce4b56f9
e = 0x10
c = 0x2700a92e463d1c5da073b38d075a2da57c89ff9d658066c0bd38391cc60259a4fc992f1a6f1c5756d6e5934831fc0fbf7bfd85607f0d18781d30a4ab485e119af4f08b5fe7bf927aeaf7572b05dfec764d6ddda2b247b9f6b731300ece4209606d94c5708388d6e8efc1fa6e9c0cdda41cee95eb4a6b053b862fc43e55648973863f9874ee79ce4408277c9dc38fb26b44880e58f054b957c64fcf0d39c1fd496ad2fc5f5e5e70ba41422a4d945da299b5a695a4b7013a1f9ae1b629e395ffb0942d783d6e6be1f0888dfcb02d0aa1e9b7076e952a339bdc60f044f598afa2da28a4d7f094b959c8a8fefd5a11d10971cd681722f6868cf15a200cb910c591e1
R.<x> = Zmod(n)[]#基于模 n 意义下的整数环的多项式环
f(x)=x^e-c
f=f.monic()
#归一化，使得系数为1，有限域上的除法运算和实数域上的除法运算有所不同，所以归一化后的多项式更容易处理。
mm = f.roots()
m=[]
for i in mm[0]:
    m.append(i)
print(m)"""
m=[25615677894578755047156343445844436265410029831929516816331615976442311723531561327119120421902137698702653352454485089340848821437391616202141872920071595012903043917129450415132281907851460389644978646684609345443875666422198491448869630433730250869349508030370580903892239207884756374806258109492943540694025256336359221536523445463701649424494112650847740223587312753305758484739299091282445005021428673424732397006712358416313791876278338631941370485282183820941394817190803527812730459595063525543676864011831621261546685501816080758863765608285760956408604370742317675113279260023090820056964546946448729327594, 24072367155045049121538350559452436123760625674850036887400917611963001043425277658590765669098038279032511209656766731851112555056082333560946068560958136635450354184400845466823159542498565735578284414677938847565345435268619941467830506642234170223615472540060479482250736366661339782825842222750498295373524349825492103059453842032165892523230350122381720065998495626851241149502139264262580869523661467741485311344845519374629180329037981137465862020038414285296394747359446242328488668743848790524262574489753290227188557314524093509983688354857005768464595599040661333002861275422817830930045336538934525600036, 22410284915869332915517353475405301781361874997511620014765307716896609134768752598582584704665037725485578318861190319579404022449775594129425860979978888272443446324093514666314685424695000601786686561006052411264877076748054463659902146625722029484456473027960815036305882742747518983542532772826030995019547403388699014520255435093536041121723793417289085198882108642039061716629900663673185654638085326455126099981185733763692003629409489559712215078372884665625160603972308815617077592138575143204160714378785745066118022886827674355196815158593721675680283188298853358878159695139190175292207533127255034143712, 19073979249275923038893403197873802702942330898221412935002649745044628810289760160906684289522634756719764289365141953863154441618860322921339033977398137618850126299000852728420859130729324165431279514548481361259733142809124530477420924010397665965873357195354849848588229804376977984636683366863855736325383167291647351033039353473600211555662607490573852684908975665488806129740839801624701017800394009286759153911158126133388953551250607486734408238163212404235716911901582709861984044176063401493384378563087390984887945676907220888380393998115118953005740848277298983697518540266717111840324178318373259180622, 6541698645302832008262940247970633562467698933708103881328966231397682913241801166212436132379502941982889063089343135477694379818531293280802838942673457394052917618128597686711422777122136224213699132136127984184142523613073960971448706423332584903476150835015731055304009403507778390169574742629087804368703460732998669837597738720119482937031238843681810088915673826941865000058898348157163412745731930147221176216054781442545666046969521342926260834211384338749444032842775055037996717706324772768300639435331444465728608728138351824860891626691575771833819130630414042360017020843812450263396637265856188996779, 3205392978709422131638989970439134484048154834417896801566308259545702588762808728536535717237099973217075033593294769761444798987616022072716011940092706740459597593035935748817596483156459787858292085678556934178998589674144027788967483808008221384893035002409765867586356465137237391263725336666912545674539224635947006350381657100183653370970052916966577574942540850391609413169837486108678775908040612978854230146027173812242615968810639269948453994001712077360000340772048949282903169743813031057524303619633090384498531518217898358044470466212973049159276790608859667179375865971339386811513282456974414033689, 1543310739533705925617992886392000141649404157079479928930698364479310680106283668528354752804099419670142142797718357489736266381309282641195804359113458377452689732728604948309122365352894654066694232006670497878530231153578549981039123791496080645734035490310101421641502841223416591980415886742445245320562278199153917811183250161553801969463496211873942707826153865579429980297598885519283561022464471692495018782367388201305439269182147692194807052336182457688766197384911522571492093138539383737422443508665545223427997090521479203257597269949688956374964379867051693054674285687711731173675479045294922577365, 61371688286799334113646730018045068199733683407922550237336739124912645060439058499419425524697266009247933120500549159620827721941790197719298587092412922043766127553554237087250302287324648718008153986587214189069868903229491954377520016520933768430955608165395350944256301087438742046756268637780718849807]

#res是f(x)的所有根,
#f.roots() 的返回值是一个长度为 n 的列表，其中每个元素是一个元组，表示 f 的一个根和其重数。
# 例如，如果 f 的一个根为 a，重数为 2，那么该元组的形式就是 (a, 2)。
for i in m:
    flag=long_to_bytes(i)
    if b'NSSCTF' in flag:
        print(flag)
        break

#b'Welcome to HNCTF, Hope you have a nice experience. This is your flag:\nNSSCTF{ore_wa_ningen_O_yameru_zo!!!JOJO!!!}\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'

[HZNUCTF2023] 决赛 signin

题目

#[HZNUCTF 2023 final]checkin
import os
from Crypto.Util.number import *
from secret import flag, hint
m = bytes_to_long(flag + os.urandom(50))
p = getPrime(512)
q = getPrime(500)
n = p * q
h = pow(2, (q - 2022) * (p + 2023), p)
assert h == pow(2, hint, p)
e = 1 << 24_000
c = pow(m, e, n)

print(f'{n = }')
print(f'{c = }')
print(f'{h = }')
print(f'{hint = }')

# n = 22114546923564420607945063747927422619774890007937503484905798897563036431278699718161460968350749338680452479484253816646632515078192048118109272532310403715802657061990320170724360874028667484527150185159662403573637809180151665727445208585725264186578429094937215068881079399747998551453944363665401263
# c = 7274219309267176700435453490636404568410293850833252412471984274955007037941820465929958008672185817002749418809077052781794306899476543760452010370102811167685901654480233874375880047900499814304539829706786470978714629827690730256369200773772396109793338097451559255985268375731804819829315168807228186
# h = 1463929459818798711929811606552273520156490689917243949474579232718301828387871678397965433435537694532920957475947201372279363554005600100100224291888130
# hint = 5610276127312766429915480651516095336201056367031530733662980757514427535721885723009367286870294772595629284861923351543396909892645845139050780691701736

题解

由hint可算出p,q

07c4b7302a8449722a99ffd7d4abe9c

求出p,q,发现

p%4=1 二次剩余，用Cipolla算法解，由于e = 1 << 24_000，进行24000次迭代二次剩余

q%4=3 rabin算法，24000次

将所求的的解（分别在模p,q下），利用中国剩余定理求线性同余方程

wp

from Crypto.Util.number import long_to_bytes
from Crypto.Util.number import *
from tqdm import tqdm

n = 22114546923564420607945063747927422619774890007937503484905798897563036431278699718161460968350749338680452479484253816646632515078192048118109272532310403715802657061990320170724360874028667484527150185159662403573637809180151665727445208585725264186578429094937215068881079399747998551453944363665401263
c = 7274219309267176700435453490636404568410293850833252412471984274955007037941820465929958008672185817002749418809077052781794306899476543760452010370102811167685901654480233874375880047900499814304539829706786470978714629827690730256369200773772396109793338097451559255985268375731804819829315168807228186
h = 1463929459818798711929811606552273520156490689917243949474579232718301828387871678397965433435537694532920957475947201372279363554005600100100224291888130
hint = 5610276127312766429915480651516095336201056367031530733662980757514427535721885723009367286870294772595629284861923351543396909892645845139050780691701736
e = 1<<24000


#求p,q
q=hint//2024+2022
p=n//q
print(p%4)
#1 二次剩余
print(q%4)
#3 rabin

def square_root_of_quadratic_residue(n, modulo):
    """Square root of quadratic residue

    Solve the square root of quadratic residue using Cipolla's algorithm with Legendre symbol
    Returns:
        int -- if n is a quadratic residue,
                   return x, such that x^{2} = n (mod modulo)
               otherwise, return -1
    """
    if modulo == 2:
        return 1
    if n % modulo == 0:
        return 0
    #定义勒让德符号
    Legendre = lambda n: pow(n, modulo - 1 >> 1, modulo)
    if Legendre(n) == modulo - 1:
        return -1
    t = 0
    #找到一个数t，使得(a^2-n)//p=-1
    while Legendre(t ** 2 - n) != modulo - 1:
        t += 1
    w = (t ** 2 - n) % modulo#求出方程的解
    return (generate_quadratic_field(w, modulo)(t, 1) ** (modulo + 1 >> 1)).x
    #generate_quadratic_field(w, modulo)表示返回一个二次域数类，然后通过 (t, 1) 生成一个二次域数类的实例，即 t + sqrt(w)
#二次域数类可以将一个数表示成 a + b*sqrt(d) 的形式，其中 a 和 b 是整数，sqrt(d) 表示一个不能化为整数的有理数，
# 也就是二次无理数，即在实数域中无法表示成有理数的数。
# 二次域数类实现了基本的算术运算，例如加法、乘法和幂运算，同时也支持在模意义下的运算
#定义一个二次域数类
def generate_quadratic_field(d, modulo=0):
    """Generate quadratic field number class

    Returns:
        class -- quadratic field number class
    """

    assert (isinstance(modulo, int) and modulo >= 0)

    class QuadraticFieldNumber:
        def __init__(self, x, y):
            self.x = x % modulo
            self.y = y % modulo
    #定义乘法运算
        def __mul__(self, another):
            x = self.x * another.x + d * self.y * another.y
            y = self.x * another.y + self.y * another.x
            return self.__class__(x, y)
    #定义幂运算
        def __pow__(self, exponent):
            result = self.__class__(1, 0)
            if exponent:
                temporary = self.__class__(self.x, self.y)
                while exponent:
                    if exponent & 1:
                        result *= temporary
                    temporary *= temporary
                    exponent >>= 1
            return result

        def __str__(self):
            return '({}, {} \\sqrt({}))'.format(self.x, self.y, d)
    return QuadraticFieldNumber
def ex_gcd(a: int, b: int) -> (int, int, int):
    """
    :return: gcd x y
    """
    if a == 0 and b == 0:
        return None
    else:
        x1, y1, x2, y2 = 1, 0, 0, 1  # 初始化x1,y1,x2,y2
        while b:
            q, r = divmod(a, b)
            a, b = b, r  # gcd(a,b)=gcd(b,a%b)
            x1, y1, x2, y2 = x2, y2, x1 - q * x2, y1 - q * y2
        # 返回一个三元组，依次是(gcd,x,y)，使得 xa+yb=gcd
        return (a, x1, y1) if a > 0 else (-a, -x1, -y1)


def crt(r_lst: list, m_lst: list):
    """
    :param r_lst: 余数列表
    :param m_lst: 模数列表
    :return: 同余式的解 x
    """
    r_lst = [r % m for (r, m) in zip(r_lst, m_lst)]  # 预先初始化
    M, res = 1, 0
    # M = m1*m2*...*mn
    for m in m_lst:
        M = M * m
    for r, m in zip(r_lst, m_lst):
        temp = r * M // m * ex_gcd(M // m, m)[1]
        res = (res + temp) % M
    return res

res1 = [c]#res储存上一轮循环中生成的二次剩余的平方根
total = []

for i in tqdm(range(24000)):
    tmp, res1 = res1, []#保存上一轮res1的值,作为该轮的c，并为本次迭代清空，寻找该轮的二次剩余的平方根
    for ct in tmp:
        mm = square_root_of_quadratic_residue(ct,p)
        if mm not in total:
            total.append(mm)
        else: continue

        if p-mm not in total:
            total.append(p-mm)
        else: continue

        if mm == 1 or mm == p - 1 or mm == -1: continue#满足费马定理无用解
        res1 += [mm,p-mm]
    res1 = list(set(res1))
res1 = res1[-2:]#找出模 p 意义下的最大二次剩余，即最后一轮的二次剩余的平方根

#rabin
res2 = c
for i in tqdm(range(24000)):
    res2 = pow(res2, (q + 1) // 4, q)
res2 = [res2, p - res2]

for i in res1:
    for j in res2:
        m = crt([i,j],[p,q])#利用中国剩余定理求线性同余方程
        print(m)
        m = long_to_bytes(m)
        if b'HZNU' in m:
            print(m)

#HZNUCTF{80f937af-6542-4142-b957-09534839da4d}

[NSSCTF ROUND11]ez_signin1

题目

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

p = getPrime(512)
q = getPrime(512)
assert p > q
n = p*q
e = 65536
m = bytes_to_long(flag)
num1 = (pow(p,e,n)-pow(q,e,n)) % n
num2 = pow(p-q,e,n)
c = pow(m,e,n)

print("num1=",num1)
print("num2=",num2)
print("n=",n)
print("c=",c)

题解

{num1=(pe%n−qe%n)%n−>(pe−qe)%nnum2=(p−q)e%n−−−−>(pe+qe)%n\begin{cases} num1=(p^e \% n-q^e\%n)\%n->(p^e-q^e)\%n\\ num2=(p-q)^e\%n---->(p^e+q^e)\%n \end{cases}

{num1+k1n=pe−qenum2+k2n=pe+qe\begin{cases} num1+k1n=p^e-q^e\\ num2+k2n=p^e+q^e\\ \end{cases}

num1+num2=2∗pe−(k1+k2)∗nnum1+num2≡2∗pe(modn)num1+num2=2*p^e-(k1+k2)*n\\num1+num2\equiv2*p^e(mod\quad n)

gcd(num1+num2,n)求出p，继而求出q ，phi,因p%4=3,用rabin,e为2^16,16次rabin ,找到flag

wp

from math import gcd
from Crypto.Util.number import *
import gmpy2
num1= 125840590309791843042942472454302309427902521609092255978098604598421904476504128795428038638958434640701151445562704932915890261048345155354271130081854732235475017614337853919731965277219907509305647787266522452615772631126275769024268070969091470146938424915366852517264759750301378534103489362861800810022
num2= 118406528288319388230227470004290601949254834713668964078645010603616773414702172944758544261570579725052821828652201587113154218442517611721124839436362032837148883717498050423716531048059705558316325394980254998270187812316191624277483798408056495011826590031502722438999314499417572813226192270193502542873
n= 144140637152927561878841058661326254132516863421085753653166712995292536662268292489238826351220756954544888101091680580454682564537342482868604164536901599672009013558797911432938065138548281881987687315400681649499161313266702303428486794442027697579445652817585974726048853787419009254509295595766411967061
c= 21702988354826355023098162614820215595773453371108009638486091165050573362393879263788989594321176598045809252543156717243926880903825424144135521110409333914517505087684419503076105354898495379828485066145995356836426089928802062373544548239600495045887996562801869682637318594583294484780968466003698900178
p = gmpy2.gcd(num1+num2,n)
#print(p)
q = n//p
#print(q)
#print(p%4)
#print(q%4)
#3用rabin

def rabin(c):
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    m1 = (mq * p * inverse(p, q) + mp * q * inverse(q, p)) % n
    m2 = n - m1
    m3 = (mq * p * inverse(p, q) - mp * q * inverse(q, p)) % n
    m4 = n - m3
    return [m1, m2, m3, m4]

t=rabin(c)
for i in range(15):
    #e为2^16,16次rabin,for外已经进行一次
    #初始化tt
    tt=[]
    #t为上一次的m1,m2,m3,m4
    for cc in t:
        #mx对应的四个解
        ttt=rabin(cc)
        for k in ttt:
            #删去重复解
            if k not in tt:
                tt.append(k)
    t=list(tt)


for m in tt:
    flag = long_to_bytes(m)
    if ((b"NSSCTF") or(b'nssctf')) in flag:
        print(flag)
        break