526互联

NSSCTF Round#11 Basic 密码个人赛复盘

发布时间 2023-11-06 23:36:02作者: Kicky_Mu

[NSSRound#11 Basic]ez_enc

ABAABBBAABABAABBABABAABBABAAAABBABABABAAABAAABBAABBBBABBABBABBABABABAABBAABBABAAABBAABBBABABABAAAABBAAABABAABABBABBBABBAAABBBAABABAABBAAAABBBAAAABAABBBAABBABABAABABAAAAABBBBABAABBBBAAAABBBBBAB

第一眼培根密码试了试但不对，观察长度发现应该是换01

010011100101001101010011010000110101010001000110011110110110110101010011001101000110011101010100001100010100101101110110001110010100110000111000010011100110101001010000011110100111100001111101

[NSSRound#11 Basic]MyMessage

from Crypto.Util.number import *
import os

flag = os.getenv('FLAG')

e = 127

def sign():
    msg = input("Input message：")
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    c = pow(bytes_to_long((msg + flag).encode()), e, n)
    print(f"n: {n}")
    print(f"Token: {hex(c)}")

def main():
    while True:
        sign()

main()

连接靶机经测试发现每次的n不同，属于是低加密指数广播攻击

exp:

from pwn import *
import re
import binascii,gmpy2
from functools import reduce
import libnum

host = 'node4.anna.nssctf.cn'
port = 28337
conn = remote(host, port)

def interact_with_server(conn):
    
    conn.recvuntil("Input message：")
    conn.sendline("")

    data1 = conn.recvline().decode()
    data2 = conn.recvline().decode()

    n = int(re.findall(r'n: (\d+)', data1)[0])
    c = int(re.findall(r'Token: 0x(\w+)', data2)[0], 16)

    return n, c



n_values = []
c_values = []

for i in range(127):
    n, c = interact_with_server(conn)
    n_values.append(n)
    c_values.append(c)

e = 127

def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

e= 127
n= n_values
c= c_values
m=gmpy2.iroot(CRT(n, c), e)[0]
print(m)
print(libnum.n2s(int(m)))
#NSSCTF{ab4e6712-c303-49bf-bf69-15b63852f0fb}

[NSSRound#11 Basic]ez_fac

from Crypto.Util.number import *
import random
from secret import flag,a0,a1,b0,b1

p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n = p*q
assert pow(a0,2) + e * pow(b0,2) == n
assert pow(a1,2) + e * pow(b1,2) == n
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c=",c)
print("n=",n)
print("a0=",a0)
print("a1=",a1)
print("b0=",b0)
print("b1=",b1)

连接靶机得到数据

c= 23536565456973585925821480486531886900867618042905017091181644227166750695677032390105725026121710199474760086941793818752546752630579692306627810337178325882348625662416875543131435163081880101341737092990661886699991449272573089794096851407848493532746401019236866684742523832513485059759781782817773718319
n= 101847819158638807796385272712315657513722216027141846150620286576441986088855287217943376201247413650395823768367405321849959847831651395385886225787374109865241138833643004743073479545335842120519840781619004009202003362950072706394215985332168239944752979674415156373479328704263213685776588831534007394397
a0= 10091968051804306410439426120644760359275202526124183037370203002893541728950097099878158854471246101468063670217830079708458195958240567745751286739891067
a1= 10091968051804306410439425549470968686578160693834731445249564074989956308972478377505177681650128922327978522363494450122685135172311895747410357042379045
b0= 76921346105205855056326448723241745579160170821098269935410084167324102373308149158920152629979738631056590311415187462866
b1= 237597736695041079174174902515816602524518828326371435351740465954852955585394208747730242596494780978513831977050534842498

简单来分析一下：

本题是关于的问题，最后可以转化得到  p = gcd(N,a0*b1-a1*b0)

可以把N与右边两个式子试一试取gcd，找到p,q。

exp:

c= 23536565456973585925821480486531886900867618042905017091181644227166750695677032390105725026121710199474760086941793818752546752630579692306627810337178325882348625662416875543131435163081880101341737092990661886699991449272573089794096851407848493532746401019236866684742523832513485059759781782817773718319
n= 101847819158638807796385272712315657513722216027141846150620286576441986088855287217943376201247413650395823768367405321849959847831651395385886225787374109865241138833643004743073479545335842120519840781619004009202003362950072706394215985332168239944752979674415156373479328704263213685776588831534007394397
a0= 10091968051804306410439426120644760359275202526124183037370203002893541728950097099878158854471246101468063670217830079708458195958240567745751286739891067
a1= 10091968051804306410439425549470968686578160693834731445249564074989956308972478377505177681650128922327978522363494450122685135172311895747410357042379045
b0= 76921346105205855056326448723241745579160170821098269935410084167324102373308149158920152629979738631056590311415187462866
b1= 237597736695041079174174902515816602524518828326371435351740465954852955585394208747730242596494780978513831977050534842498

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

e = (n - a0*a0)//b0//b0

'''
当 N = m*a^2 + n*b^2  时有 p = gcd(N, a0*b1 - a1*b0)
'''
p = gmpy2.gcd(n, a0*b1 - a1*b0)
d = gmpy2.invert(e, (p-1)*(n//p-1))
m = pow(c,d,n)
print(long_to_bytes(m))
#NSSCTF{1e725ebb-1e43-42d3-9cbf-047b9420816a}

[NSSRound#11 Basic]ez_signin

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= 13695685572182054510723155409550656919372247685999134593727088627368822142347445450912577481962446903686002330010675385809316696539197376190631895713791375000930423007963613360009058057305733880631432746007990577143304780020571261093007651390660908346884365161606383870479152190997704260146433287300740742717
num2= 14042488628163483801268003968107803057135434253017787093262589276563601674303488893157116089054916600156331515371672235997586645669826780458583612636069161147700877612919579917129146756095959733855581085806378499013395675228303251543910910499953252038073869109857103077875020930686902640313956552783801462289
n= 84807581559535898806718685483231542490590638241243480686867695057833785909333533672054772163284313700373761394458877258753508193220594649646742567605075390602876096397560805328822327856673173427884733655107194875947262473943899396306576245151917990651739124745017357095173941331731411020436350996569160376697
c= 17910050343606529006727453217055136218567927573616381892608606684715021621280477922904617533086893142442472583138414774147521558784762554617927046708855162378600500202118410428117435148784891184762016943793458870917754347869975420723090154156368257080228826161823560409191207393826608819013685474500206578752

简单分析：

由于 e=65536是rabin加密,16轮rabin，因此直接套模板

exp:

from math import gcd
from Crypto.Util.number import *
import gmpy2
num1= 13695685572182054510723155409550656919372247685999134593727088627368822142347445450912577481962446903686002330010675385809316696539197376190631895713791375000930423007963613360009058057305733880631432746007990577143304780020571261093007651390660908346884365161606383870479152190997704260146433287300740742717
num2= 14042488628163483801268003968107803057135434253017787093262589276563601674303488893157116089054916600156331515371672235997586645669826780458583612636069161147700877612919579917129146756095959733855581085806378499013395675228303251543910910499953252038073869109857103077875020930686902640313956552783801462289
n= 84807581559535898806718685483231542490590638241243480686867695057833785909333533672054772163284313700373761394458877258753508193220594649646742567605075390602876096397560805328822327856673173427884733655107194875947262473943899396306576245151917990651739124745017357095173941331731411020436350996569160376697
c= 17910050343606529006727453217055136218567927573616381892608606684715021621280477922904617533086893142442472583138414774147521558784762554617927046708855162378600500202118410428117435148784891184762016943793458870917754347869975420723090154156368257080228826161823560409191207393826608819013685474500206578752
e=65536
p=gcd((num1+num2)//2,n)
q=n//p
def s(c):
    # 计算解密参数
    mp = pow(c, (p+1)//4, p)
    mq = pow(c, (q+1)//4, q)
    # 计算四个可能的明文
    d1 = (mq * p * inverse(p, q) + mp * q * inverse(q, p)) % n
    d2 = n - d1
    d3 = (mq * p * inverse(p, q) - mp * q * inverse(q, p)) % n
    d4 = n - d3
    return [d1,d2,d3,d4]
res=s(c)
r=[]
for j in res:
    r.extend(s(j))
rr=[]
for i in range(14):
    for j in r:
        rr.extend(s(j))
    r=list(set(rr))
    rr=[]
for i in r:
    # assert i**65536 %n==c
    print(long_to_bytes(i))
#NSSCTF{a6411a56-7155-48e5-bea2-c4a6744462f3}

[NSSRound#11 Basic]MyGame

from Crypto.Util.number import *
import os
import random
import string

flag = os.getenv('FLAG')

def menu():
    print('''=---menu---=
1. Guess
2. Encrypt
''')

p = getPrime(512)
q = getPrime(512)
n = p*q

def randommsg():
    return ''.join(random.choices(string.ascii_lowercase+string.digits, k=30))

mymsg = randommsg()
def guess():
    global mymsg
    msg = input()

    if msg == mymsg:
        print(flag)
    else:
        print(mymsg)
        mymsg = randommsg()

def encrypt():
    e = random.getrandbits(8)
    c = pow(bytes_to_long(mymsg.encode()), e, n)
    print(f'Cipher_{e}: {c}')

def main():
    print(f'n: {n}')
    while True:
        opt = int(input())

        if opt == 1:
            guess()
        elif opt == 2:
            encrypt()

main()

共模攻击：

from gmpy2 import *
from Crypto.Util.number import *
from pwn import *
import re
import binascii,gmpy2
from functools import reduce
import libnum

# ------------ 交互部分 ------------
host = 'node4.anna.nssctf.cn'
port = 28540
conn = remote(host, port)
data1 = conn.recvline().decode()
n = int(re.findall(r'n: (\d+)', data1)[0])

def interact_with_server(conn):
    conn.sendline("2")
    data1 = conn.recvline().decode()
    print(data1)
    e,c = re.findall(r'Cipher_(\d+): (\d+)', data1)[0]
    e = int(e)
    c = int(c)
    
    return e, c
# ------------ 共模攻击 ------------
def attack():
    e1,c1 = interact_with_server(conn)
    e2,c2 = interact_with_server(conn)

    g,x,y = gcdext(e1,e2)

    m= pow(c1,x,n)*pow(c2,y,n)%n

    m = iroot(m,2)[0]

    return long_to_bytes(m)

def get_flag():
    m = attack()
    print(m)
    conn.sendline("1")
    conn.sendline(m)
    return conn.recvline().decode()

while True:
    flag = get_flag()
    if "NSS" in flag:
        print(flag)
        break
#NSSCTF{5b284b6d-a43e-4e9f-b0b0-0efb57f404e5}

法二：爆破就好了e<=3，直接开根号解密

 

from pwn import *
from Crypto.Util.number import long_to_bytes
import gmpy2
p=remote('node4.anna.nssctf.cn',28540)
p.recv()
for i in range(1111):
    p.sendline(b'2')
    p.recvuntil(b'Cipher_')
    res=int(p.recvuntil(b':',drop=True))
    # print(res)
    if 1<=res<=3:
        r=gmpy2.iroot(int(p.recv().replace(b'\n',b'')),res)[0]
        p.sendline(b'1')
        print(long_to_bytes(r))
        p.sendline(long_to_bytes(r))
        print(p.recv())
        break
    p.sendline(b'1')
    p.sendline(b'a')
#NSSCTF{5b284b6d-a43e-4e9f-b0b0-0efb57f404e5}

[NSSRound#11 Basic]NTR

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

def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)

def encrypt(cipher, p, z):
    message = bytes_to_long(cipher)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    return c

p, x, y, z = init()
c = encrypt(flag, p, z)
with open("cipher.txt", "w") as f:
    f.write("binz = " + str(bin(z)) + "\n")
    f.write("binp = " + str(bin(p)) + "\n")
    f.write("binc = " + str(bin(c)) + "\n")

连接靶机得到

binz = 0b11010111011011011110110100000101111000110001011101010110001001010011101010010110101101101111101101001011111011000000100100001001010011100111111100110100111100000110111001100010111000010101000001001101010001001010000111010000010011110010111100011110100010101010110010111001011000010110001011000010111001110010100001110010110001111001010011100101111010001111100111111101100100010010000010101010111001110011111010101000101010110011011111000100100001011010010101010101111110110111011000100101001111100110101001100000100111100100111100100101100001110000100110011011011010111001010010111011111100100000010000010111011101111010010011000110011101001010110111000011010101001110100111111010111101000111011110100101101010110111101101101011000110010010111000110101111000010011111110010001010100101110100011001100001111001110101010000010111010100110010101011001101010000011100001101001110111011111111011000111001100101010010111101011100011100110000000011000111111111001011110010111001010010101010010111100010111010101101010010011001011111011111010011100111011001000000010000100101101101110110010000000111011110001111001000100000100111011000000010011001010110111100111110110100001011001110000001101011001111000111010111101111110100101111111001111010111110110011011011111101100011101110011110000010001001000101100000101010011001000101100111101001011110100001001100101001000011000111111100100011000101010101101110010011011010000110001111100111110000000001011110010101001101011100011111100111000000111010111010011011011011110001010011010111010100111010001111100110000010010000101111110000011101100001001101101001010011000100001001011100101000110011100010100101001000010011001000000000001010001111000110011001011110111000010111111100110101011000000001011011011001000110101010100101010110010110111011110000001100110110011001000011111101011011000000010000111001100110101100110000111011110001101010001111001111001100011000110110111010010111111011110101000110110000001111100110101111110100111100001010111110000011100000010011111011100111000101111110101010111100110010111

binp = 0b11011110110101111001010000100110001010011100100010001111010001010111000001000100010100100100001000001001100111111000110000101000010101001001100000001111111000000011110110100111001000100010001101100001111101011001001011010111011010101110110010111001100001111011001100110110010001111001011000010011110010101100010000011001000011110110011111000110001011111001001110111000010001001011010010000100111001110000111101101000110001111111011011100001001011100111000000000011011100100101110001011010000001101101011000100001010011010100111010011010110101000010100100011000010011110000000110000010100001110011001101011000011100111100101110101101101000100010001100001101100100011100011010011001010000000010001101000100111100101011100001010001100100111101100101001011000011101011100001100100101001111000111100110101110100000100110100110010011110000101110101110011010010000001110010110000010110111110000110011111000001011110101111010000010100011100100001101000100000010011111111111010101100010101010100001101000001001001001011101010011011110110100010110100001010011000100000100000001110111110001111111010000001000011011110110001001100001110001110000111110100101100010000001010001110001111110011010001110100000000000001111100100110000110100011101101000110010100111001100110100111010110010000101000101011101001111011000000011100110100001011000110000000100000010010111000111100111010011110011110101011111001100010011000101101000100010100110011010110011101010101100000110100010000011011001110101001111010001001111010110010101010001101000100100101101010010100101011000101110101111100100011110010011011110000011001111110101101011101111101101101100111000100011010111001100101100000100101000011101100111101011100110011001110100110001000001110101011110110000001100001100010001101011110000001000101001010011100100110100001111110111011110010110110110000011011110001011001000101100111011000010110101111011001110000000011000101001011111101000101001101000001010111101001101010010100000100011001000001100100011100010000001111010011011101101000100111110110001000110001111001000001

binc = 0b11011101101010000110111011001100101000100010110000011000010001110110010101000001100010000000001111101000111100010001000111101110111001011011001111000001000001001010000110111100100011100010110000110100000110111000100011101110111110011111000100111001011111100000111110111000000011001010010101001111001111001010010010011000011001101010011001101011100000000110110000100001101001001000100010001001001011010101101101010010111111000111100011001001010001110101000000011011101001101111000000001111011110001011101111010101011100111100011010010000010011101111110101101010100011110101100010001101011000010011101000111100010101111011010100011011101110001000111111111001110000001110011110000100110110000111100100010100111001010101100001101111000010000000010111001000111000000101101110101000010011110111000011101111111000010010010110111001101001010011001000110111101011101001110101001000011000001001000100110010101101011111101010110001100100110001001000101101100110010101101001010111101001000000100110011100110001100011010110100100001011000011000110111111100000000111101000100111001111101110010011100100000000001101011000110101001001100001100101110000000100010110101111000000101111000101100011000110000001110010111110100011101110110110010011111011100110001100000011111011001010011100100100101111001000001010001001111111101101101001011000000001001100011010011101011001010101100111010000000111111000111100011101110100111010011100001000011011001000001111110111110111000100111010001010111000011000110011001000001000111010101101000010101101011111000000101001111111101111101101000010111010101100001001100001000010100110100000110010101100100111001101011110110110011000010001100111000101000001111001000010000000000000100101000100000011111100100100001000011100010011011100111011111100001011111101010011100100110011101000010001011001000000011111011010011001100001001101110110010101011000000011111101010010101001001111100100011101011100000001010101001011100110111100110011110001100110101111110101011010100011110010001111111111000110011001010111010111001111100000011101101010

参考：https://www.cnblogs.com/L00kback/p/17445967.html

exp:

#sage
binz = '0b11010111011011011110110100000101111000110001011101010110001001010011101010010110101101101111101101001011111011000000100100001001010011100111111100110100111100000110111001100010111000010101000001001101010001001010000111010000010011110010111100011110100010101010110010111001011000010110001011000010111001110010100001110010110001111001010011100101111010001111100111111101100100010010000010101010111001110011111010101000101010110011011111000100100001011010010101010101111110110111011000100101001111100110101001100000100111100100111100100101100001110000100110011011011010111001010010111011111100100000010000010111011101111010010011000110011101001010110111000011010101001110100111111010111101000111011110100101101010110111101101101011000110010010111000110101111000010011111110010001010100101110100011001100001111001110101010000010111010100110010101011001101010000011100001101001110111011111111011000111001100101010010111101011100011100110000000011000111111111001011110010111001010010101010010111100010111010101101010010011001011111011111010011100111011001000000010000100101101101110110010000000111011110001111001000100000100111011000000010011001010110111100111110110100001011001110000001101011001111000111010111101111110100101111111001111010111110110011011011111101100011101110011110000010001001000101100000101010011001000101100111101001011110100001001100101001000011000111111100100011000101010101101110010011011010000110001111100111110000000001011110010101001101011100011111100111000000111010111010011011011011110001010011010111010100111010001111100110000010010000101111110000011101100001001101101001010011000100001001011100101000110011100010100101001000010011001000000000001010001111000110011001011110111000010111111100110101011000000001011011011001000110101010100101010110010110111011110000001100110110011001000011111101011011000000010000111001100110101100110000111011110001101010001111001111001100011000110110111010010111111011110101000110110000001111100110101111110100111100001010111110000011100000010011111011100111000101111110101010111100110010111'

binp = '0b11011110110101111001010000100110001010011100100010001111010001010111000001000100010100100100001000001001100111111000110000101000010101001001100000001111111000000011110110100111001000100010001101100001111101011001001011010111011010101110110010111001100001111011001100110110010001111001011000010011110010101100010000011001000011110110011111000110001011111001001110111000010001001011010010000100111001110000111101101000110001111111011011100001001011100111000000000011011100100101110001011010000001101101011000100001010011010100111010011010110101000010100100011000010011110000000110000010100001110011001101011000011100111100101110101101101000100010001100001101100100011100011010011001010000000010001101000100111100101011100001010001100100111101100101001011000011101011100001100100101001111000111100110101110100000100110100110010011110000101110101110011010010000001110010110000010110111110000110011111000001011110101111010000010100011100100001101000100000010011111111111010101100010101010100001101000001001001001011101010011011110110100010110100001010011000100000100000001110111110001111111010000001000011011110110001001100001110001110000111110100101100010000001010001110001111110011010001110100000000000001111100100110000110100011101101000110010100111001100110100111010110010000101000101011101001111011000000011100110100001011000110000000100000010010111000111100111010011110011110101011111001100010011000101101000100010100110011010110011101010101100000110100010000011011001110101001111010001001111010110010101010001101000100100101101010010100101011000101110101111100100011110010011011110000011001111110101101011101111101101101100111000100011010111001100101100000100101000011101100111101011100110011001110100110001000001110101011110110000001100001100010001101011110000001000101001010011100100110100001111110111011110010110110110000011011110001011001000101100111011000010110101111011001110000000011000101001011111101000101001101000001010111101001101010010100000100011001000001100100011100010000001111010011011101101000100111110110001000110001111001000001'

binc = '0b11011101101010000110111011001100101000100010110000011000010001110110010101000001100010000000001111101000111100010001000111101110111001011011001111000001000001001010000110111100100011100010110000110100000110111000100011101110111110011111000100111001011111100000111110111000000011001010010101001111001111001010010010011000011001101010011001101011100000000110110000100001101001001000100010001001001011010101101101010010111111000111100011001001010001110101000000011011101001101111000000001111011110001011101111010101011100111100011010010000010011101111110101101010100011110101100010001101011000010011101000111100010101111011010100011011101110001000111111111001110000001110011110000100110110000111100100010100111001010101100001101111000010000000010111001000111000000101101110101000010011110111000011101111111000010010010110111001101001010011001000110111101011101001110101001000011000001001000100110010101101011111101010110001100100110001001000101101100110010101101001010111101001000000100110011100110001100011010110100100001011000011000110111111100000000111101000100111001111101110010011100100000000001101011000110101001001100001100101110000000100010110101111000000101111000101100011000110000001110010111110100011101110110110010011111011100110001100000011111011001010011100100100101111001000001010001001111111101101101001011000000001001100011010011101011001010101100111010000000111111000111100011101110100111010011100001000011011001000001111110111110111000100111010001010111000011000110011001000001000111010101101000010101101011111000000101001111111101111101101000010111010101100001001100001000010100110100000110010101100100111001101011110110110011000010001100111000101000001111001000010000000000000100101000100000011111100100100001000011100010011011100111011111100001011111101010011100100110011101000010001011001000000011111011010011001100001001101110110010101011000000011111101010010101001001111100100011101011100000001010101001011100110111100110011110001100110101111110101011010100011110010001111111111000110011001010111010111001111100000011101101010'
z = int(binz,2)
p = int(binp,2)
c = int(binc,2)
M = Matrix(ZZ,[[1,z],
			   [0,p]])
res = M.LLL()
x,y = res[0]
x = abs(x)
y = abs(y)
m = ((c*x)%p*inverse_mod(x,y))%y
flag = bytes.fromhex(hex(m)[2:])
print(flag)
#NSSCTF{bc940c7b-32c3-4258-a324-1d799f2bde24}