黑盾杯 Writeup -星盟安全- 密码专题

from random import randbytesfrom hashlib import sha256from secret import FLAG
prime_q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351prime_p = 2 * prime_q + 1generator = 2
def generate_keys(prime_p:int, prime_q: int, generator: int):    private_key = int(randbytes(48).hex(), 16)    public_key = pow(generator, private_key, prime_p)    return private_key, public_key
def signature(m: str, private_key: int):    ephemeral_key = pow(int.from_bytes(m.encode(), "big"), -1, prime_q)    value_r = pow(generator, ephemeral_key, prime_p) % prime_q    hash_value = sha256(m.encode()).hexdigest()    value_s = pow(ephemeral_key, -1, prime_q) * (int(hash_value, 16) + private_key * value_r) % prime_q    return hash_value, value_r, value_s
def verification(message_hash: str, value_r: int, value_s: int, public_key: int):    message_hash = int(message_hash, 16)    inverse_s = pow(value_s, -1, prime_q)    u1 = message_hash * inverse_s % prime_q    u2 = value_r * inverse_s % prime_q    value_v = (pow(generator, u1, prime_p) * pow(public_key, u2, prime_p) % prime_p) % prime_q    return value_v == value_r
private_key, public_key = generate_keys(prime_p, prime_q, generator)print(f"prime_p = {prime_p}")print(f"prime_q = {prime_q}")print(f"generator = {generator}")print(f"public_key = {public_key}")hash_value, value_r, value_s = signature(FLAG, private_key)assert verification(hash_value, value_r, value_s, public_key)print("FLAG= *******************************")print(f"Here is your gift = {hash_value}")print(f"value_r = {value_r}")print(f"value_s = {value_s}")
"""prime_p = 254843759712120770192107797102254314236912507988317949449773952808056853528137124034192193635099026436082859359975257478069529928753465466553898924428657727410192480025664330547720267491593689914315716652925690802124634579341155119238992435231736067051804606192447508930100501670982605518547228404550199336703prime_q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351generator = 2public_key = 203067127960912832141683478285660048030359503470370454787601793943616785191379475478042780786586398613392124449107914485276391144619614524238733955000423462607587314297053793965792270827882515151687216333955022781961954655722031280839330387844465050108465655364799714778902062392884738636499384813673672979624FLAG= *******************************Here is your gift = 7cd5919ec33329f372861316bf138d4f1d8cef07cb7d96d2ba6b0407a26a4929value_r = 91987314907396190363776180658807815734396154127254468125016222097239986759962138961750386994896045832251677962872797517216549442387764502999401633664222670102801921262893879691513529363886967533622509081727218471077487171182237682873296913054723806168633411544528464087484863577372796531442329032019175510840value_s = 97172191167164014651733063606048384101523409706119431237978571240263228912279490520724056027791113786234169450262504051039148717021385896661445171735031388734202070256403738610458538277913368201481075618079318763946298733145161161413633716027675945768604484133854342359914555804404012533649786028255565020365"""

import libnum
p = 254843759712120770192107797102254314236912507988317949449773952808056853528137124034192193635099026436082859359975257478069529928753465466553898924428657727410192480025664330547720267491593689914315716652925690802124634579341155119238992435231736067051804606192447508930100501670982605518547228404550199336703q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351g = 2pub_key = 203067127960912832141683478285660048030359503470370454787601793943616785191379475478042780786586398613392124449107914485276391144619614524238733955000423462607587314297053793965792270827882515151687216333955022781961954655722031280839330387844465050108465655364799714778902062392884738636499384813673672979624Hash = '7cd5919ec33329f372861316bf138d4f1d8cef07cb7d96d2ba6b0407a26a4929'r = 91987314907396190363776180658807815734396154127254468125016222097239986759962138961750386994896045832251677962872797517216549442387764502999401633664222670102801921262893879691513529363886967533622509081727218471077487171182237682873296913054723806168633411544528464087484863577372796531442329032019175510840s = 97172191167164014651733063606048384101523409706119431237978571240263228912279490520724056027791113786234169450262504051039148717021385896661445171735031388734202070256403738610458538277913368201481075618079318763946298733145161161413633716027675945768604484133854342359914555804404012533649786028255565020365M = matrix([    [q*2^1024, 0, 0, 0],    [int(Hash, 16)*2^1024, 2^(48*8), 0,0],    [r*2^1024, 0, 1, 0],    [s*2^1024, 0, 0, 2^1024]])
m= abs(M.LLL()[-1][1])//2^(48*8)print(libnum.n2s(int(m)))

from pwn import *
sh = remote('39.104.54.154', 33196)context.log_level = 'debug't = 0# sh.interactive()
for i in range(2):    t += 1    print(t)    s = sh.recvuntil(b'Input your answer in 3 seconds:').split(b'n')    if i == 0:        exec(s[1])        print(s[2])        sh.sendline(str(eval((s[2][:-3]).replace(b'X', b"*"))).encode())    else:        print(s[4])        sh.sendline(str(eval((s[4][:-3]).replace(b'X', b"*"))).encode())    sh.sendafter(b'I will answer your question(example:2X2+2-1):n', b'open("./flag.txt").read()')

from secrets import *
a = 3154360777410506828246987116345256890184577383710274549100253493102602370771512079662661389298064379349297671822832361451806819324117030877860973333011340b = 8900107603684880848823856015698573019396167226852451507348909846939656375296450863804117308625379057367448138177656005285817843532255952396258070802639631
def genkey(secret):    c = []    m = ''.join([bin(i)[2:].zfill(8) for i in secret])    for i in m:        e = randint(1, b)        n = pow(a, e, b)        if i == '1':            c.append(n)        else:            c.append(-n % b)    return c
def write2file(s:str,name:str):    with open(f"{name}.txt",'w') as f:        f.write(s)        f.close()

write2file(str(genkey(key)),'key')

from Crypto.Util.number import *
para = 5def content2file(c:str,name:str):    with open(name,'w') as f:        f.write(c)    f.close()
def myVault(primeInput, arraySize):  nbitLen = primeInput.bit_length()  while True:    randomCoefficients = [getRandomRange(-1, 1) for _ in '_' * arraySize]    randomPowers = [getRandomRange(3, nbitLen - 3) for _ in '_' * arraySize]    additionalValue = sum([randomCoefficients[_] * 2 ** randomPowers[_] for _ in range(0, arraySize)])    calculatedPrime = primeInput + additionalValue    if isPrime(calculatedPrime) * additionalValue != 0:      return calculatedPrime
p = getPrime(512)q = myVault(p, para)e = 65537n = p * qm = bytes_to_long(flag)c = pow(m, e, n)content = f"n = {n}"+'n'+f'c = {c}'content2file(content,'output.txt')"""n = 48987035266621570140500934158858469620652835271063616519590308851385164518812176119432534420734277362711792614791426200799757611807348629322492530155834607900572623099776762149434109471388050773769939238534778764654212836597317471500184403294922913039713899744399761233554012047484398858823558893408196807033c = 693909607850188675261359248783950968733272320668635843434595630676499018450648340514019367315972407940651562028697048971462221049402273630628220856691302688729211290030474876308280832203342641870897948093276586900984306145890597215601814018695147806669836298644708893223604707150805438780680758909628673559"""

hs = []# 取“阶”部分因子求解离散对数import hashlib
# c = pow(m, secret, n)# h = g^x mod pdef r(h, g, N, p, qi):    Zp = Zmod(p)    h = pow(h, N//qi, p)    g = pow(g, N//qi, p)    ri = discrete_log(Zp(h), Zp(g))    return int(ri)a = 3154360777410506828246987116345256890184577383710274549100253493102602370771512079662661389298064379349297671822832361451806819324117030877860973333011340b = 8900107603684880848823856015698573019396167226852451507348909846939656375296450863804117308625379057367448138177656005285817843532255952396258070802639631tmp_list = [2]r_list = []key = ''for h in hs:    try:        for qi in tmp_list:            tmp = r(h,a,b-1,b,qi)            key += '1'    except:        key += '0'    print(key)key = bytes([int(key[i*8:(i+1)*8],2) for i in range(len(key)//8)])print(key)

from isqrt import isqrt

def fermat(n):    a = isqrt(n)    b2 = a * a - n    b = isqrt(n)    count = 0    while b * b != b2:        a = a + 1        b2 = a * a - n        b = isqrt(b2)        count += 1    p = a + b    q = a - b    assert n == p * q    return p, q

if __name__ == '__main__':    import libnum    N = 48987035266621570140500934158858469620652835271063616519590308851385164518812176119432534420734277362711792614791426200799757611807348629322492530155834607900572623099776762149434109471388050773769939238534778764654212836597317471500184403294922913039713899744399761233554012047484398858823558893408196807033    c = 693909607850188675261359248783950968733272320668635843434595630676499018450648340514019367315972407940651562028697048971462221049402273630628220856691302688729211290030474876308280832203342641870897948093276586900984306145890597215601814018695147806669836298644708893223604707150805438780680758909628673559    e = 65537
    p, q = fermat(N)    print("p:", p)    print("q:", q)
    # 根据p,q求phi_n也即N的欧拉函数值    phi_n = (p - 1) * (q - 1)    # 求d    d = libnum.invmod(e, phi_n)
    # 用d解密    flag = libnum.n2s(pow(c, d, N))    print(flag)