XSCTF crypto

XSCTF

[简单] 初识RSA

p和q藏起来了，你能帮我找到它们吗

from Crypto.Util.number import bytes_to_long, inverse, getPrime
from flag import flag

m = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p * q
print(n)
e = 65537

c = pow(m, e, n)

pq = p * (q - 1)
qp = q * (p - 1)

print("c=", c)
print("n=", n)
print("pq=", pq)
print("qp=", qp)

'''
c= 8722269075970644434253339592758512788160408912707387632591552130175707843950684315083250494010055435391879036285103810263591951437829414438640307561645721347859659807138051841516634704123100270651976676182059252251162982609391666023674158274992400910869692389001622774140191223807887675081808561012755545464977015973615407965906513878979919700065923364884766974187303774330319143647840846354404070430118235352622445115153298578370521811697710289716188726587743282814946239856766713516166990341116198180068191759095913957606379780234116317390622824096667107736103270907349927467971817639795094030622157581511033950777
n= 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003
pq= 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074488896197029704465200125337817646702009123916866455067019234171839614862660036737875747177391796376553159880972782837853473250804807544086701088829096838316550146794766718580877976153967582795248676367265069623900208276878140709691073369415161936376086988069213820933152601453587292943483693378833664901178324
qp= 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074475956379708898904933143429835002718457573266164923043251954374464149976302585916538814746811455883837138715445492053610047383292461097590195481556557381952895539341802954749542143253491617052100969586396996063822508764438280468492894012685918249843558593322831683872737943676955669923498182824352081785243246
'''

解題思路

$pq = p * (q - 1) qp = q * (p - 1) phi = (q - 1) * (p - 1) = pq * qp / n$

接下來就算出d，照RSA的常規解法來。

解答

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

c = 8722269075970644434253339592758512788160408912707387632591552130175707843950684315083250494010055435391879036285103810263591951437829414438640307561645721347859659807138051841516634704123100270651976676182059252251162982609391666023674158274992400910869692389001622774140191223807887675081808561012755545464977015973615407965906513878979919700065923364884766974187303774330319143647840846354404070430118235352622445115153298578370521811697710289716188726587743282814946239856766713516166990341116198180068191759095913957606379780234116317390622824096667107736103270907349927467971817639795094030622157581511033950777
n = 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003
pq = 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074488896197029704465200125337817646702009123916866455067019234171839614862660036737875747177391796376553159880972782837853473250804807544086701088829096838316550146794766718580877976153967582795248676367265069623900208276878140709691073369415161936376086988069213820933152601453587292943483693378833664901178324
qp = 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074475956379708898904933143429835002718457573266164923043251954374464149976302585916538814746811455883837138715445492053610047383292461097590195481556557381952895539341802954749542143253491617052100969586396996063822508764438280468492894012685918249843558593322831683872737943676955669923498182824352081785243246

phi = (pq * qp) // n
e = 65537

d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))

baigeiRSA

题目描述:
白给了，白给了，真白给！

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

size = 128
e = 65537
p = number.getPrime(size)
q = number.getPrime(size)
n = p*q

m = libnum.s2n(flag)
c = pow(m, e, n)

print('n = %d' % n)
print('c = %d' % c)

'''
n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257
'''

解答

基礎RSA，有手就行，n丟factordb就拆出p, q了，其他方式應該也能拆，位數不大很好爆破。

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

p = 274539690398523616505159415195049044439
q = 322368694010594584041053487661458382819
n = p * q
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257

phi = (p - 1) * (q - 1)
e = 65537

d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))

baigeiRSA2

题目描述:
既然白给，就多给一点吧！

import libnum
from Crypto.Util import number
from functools import reduce
from secret import flag

n = 5
size = 64
while True:
    ps = [number.getPrime(size) for _ in range(n)]
    if len(set(ps)) == n:
        break

e = 65537
n = reduce(lambda x, y: x*y, ps)
m = libnum.s2n(flag)
c = pow(m, e, n)

print('n = %d' % n)
print('c = %d' % c)

'''
n = 175797137276517400024170861198192089021253920489351812147043687817076482376379806063372376015921
c = 144009221781172353636339988896910912047726260759108847257566019412382083853598735817869933202168
'''

解答

題目眼花撩亂，直接先拆n，發現有五個質數，就建一個list來裝，水題。

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

n = 175797137276517400024170861198192089021253920489351812147043687817076482376379806063372376015921
c = 144009221781172353636339988896910912047726260759108847257566019412382083853598735817869933202168

'''
n = 9401433281508038261<19> · 10252499084912054759<20> · 11215197893925590897<20> · 11855687732085186571<20> · 13716847112310466417<20>
'''

p = [
    9401433281508038261,
    10252499084912054759,
    11215197893925590897,
    11855687732085186571,
    13716847112310466417
]

phi = 1
for i in p:
    phi = phi * (i - 1)
e = 65537

d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))

babyFibo

题目描述:
简单题，快做！

import os
import libnum
from secret import flag

def fibo(n):
    assert n >= 0
    if n < 2:
        return n
    return fibo(n-1) + fibo(n-2)

s = fibo(1000)
m = libnum.s2n(flag+os.urandom((len(bin(s))-2)//8-len(flag)))
c = m^s
print(c)

'''
c = 43104378128345818181217961835377190975779804452524643191544804229536124095677294719566215359919831933542699064892141754715180028183150724886016542388159082125737677224886528142312511700711365919689756090950704
'''

解答

把費波那契數列算出來做xor就好了，不過一開始很笨的以為^是次方，睡迷糊ㄌ好好笑。

import sys

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot, mpz

cache = {0: 0, 1: 1}

def fibo(n):
    if n in cache:  # Base case
        return cache[n]
    # Compute and cache the Fibonacci number
    cache[n] = fibo(n - 1) + fibo(n - 2)  # Recursive case
    return cache[n]


sys.setrecursionlimit(2000)
c = 43104378128345818181217961835377190975779804452524643191544804229536124095677294719566215359919831933542699064892141754715180028183150724886016542388159082125737677224886528142312511700711365919689756090950704
s = fibo(1000)
m = c ^ s
print(long_to_bytes(m))

Xor很心疼你

题目描述:
看了这么久题目了，Xor很心疼你，并打算考考你

# Python3
from secret import flag
import random
import base64

pool = 'qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM'
r = random.randint(2, 250)
assert flag.startswith('hsctf{')


def generate(length):
    return ''.join(random.choices(pool, k=length))


def f(x):
    random.seed(x)
    return random.getrandbits(8)


def encrypt(plaintext, key):
    plaintext = list(map(ord, plaintext))
    for _ in range(20):
        key = f(key)
        assert key != 0
    for i in range(len(plaintext)):
        key = f(key)
        tmp = (key * r) % 251
        assert tmp != 0 and key != 0
        plaintext[i] = plaintext[i] ^ tmp
    plaintext = bytes(plaintext)
    return base64.b64encode(plaintext)


m = generate(random.randint(200, 300)) + flag + generate(random.randint(200, 300))
c = encrypt(m, random.getrandbits(128))
print(c)
# b'8OcTbAfL6/kOMQnC9v8SNmmSzvQMeGTT8vANM1T+7vIce2fo0fc2RnScrNxTSmeSyuMjMF//w8BWaXX91dsGcnvmreg0NQTw96ceVVXj3sQ3Znn51OU1S0bOyaMtNHTj36AcWFqewN4zRUXD6agGbAPE+tQtd3XG0doAa1Ll9fhcQ1zk0McTM1bv8PIQOAnn3vQ3UgLD3PsONXLs4KkXMnjTyMEQOFn/0uYVUwOY1PsleEHCyNopRVDr+Kc0e2PH9v0XNXfprfIPU3nw7KYTNX/G7twLSkHoyaUlQHXi3v02UHmdy/4iNgme3Pc8bgPp+tYWV1+YzPkXYkXM4ulUc27DrM4SNUPT2fQlckj1qP4Fal+YoPYJMlyZ8qhXfF3Y0tUDdUXl3vg0dFTi++VVOFfH/dgMS1ru9N8WU0HF9cUCTgPe+qVdSn/u7Mkda0GTw/QDcWPZ9KYGN2jSzfk0OVrMzt0yRHD64KMrUgPF2sFWcmP56KZSTAD61PUGeXrd49MgU1bL8OsVNWj91vIsalXwqf0qaWbwzv0lWETA4eElS3L99cYmU1nv9dRQTWbDyclScQTN6NIhV2j//+ZWbH7Z68kwM3Dy4dcUc1PQy8kRTl/4zcU9WGWfoakOMXuf69MXZQTEz+kJT1Dar8UN'

解題思路

這題關鍵點感覺在於tmp，把tmp找出來就可以和密文xor找出明文，tmp由key和r組成，key會變動，r是介於2-250之間的隨機數。

所以我小改一下，變成一個爆破程式，但很遺憾的效果感覺並不好。

import random
import base64

pool = 'qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM'
flag = 'hsctf{test}'
r = 2
assert flag.startswith('hsctf{')


def generate(length):
    return ''.join(random.choices(pool, k=length))


def f(x):
    random.seed(x)
    return random.getrandbits(8)


def encrypt(plaintext, key):
    plaintext = list(plaintext)
    for _ in range(20):
        key = f(key)
        if key == 0:
            return b''
    for i in range(len(plaintext)):
        # print(key)
        key = f(key)  # key is 固定且循環的
        tmp = (key * r) % 251  # r 介於 2 ~ 250之間
        # print(key, r, tmp)
        plaintext[i] = plaintext[i] ^ tmp
    plaintext = bytes(plaintext)
    return plaintext


idx = 0
while True:
    idx += 1
    if idx % 10 == 0:
        print(idx)

    for i in range(2, 250):
        r = int(i)
        m = generate(random.randint(200, 300)) + flag + generate(random.randint(200, 300))
        m = b'8OcTbAfL6/kOMQnC9v8SNmmSzvQMeGTT8vANM1T+7vIce2fo0fc2RnScrNxTSmeSyuMjMF//w8BWaXX91dsGcnvmreg0NQTw96ceVVXj3sQ3Znn51OU1S0bOyaMtNHTj36AcWFqewN4zRUXD6agGbAPE+tQtd3XG0doAa1Ll9fhcQ1zk0McTM1bv8PIQOAnn3vQ3UgLD3PsONXLs4KkXMnjTyMEQOFn/0uYVUwOY1PsleEHCyNopRVDr+Kc0e2PH9v0XNXfprfIPU3nw7KYTNX/G7twLSkHoyaUlQHXi3v02UHmdy/4iNgme3Pc8bgPp+tYWV1+YzPkXYkXM4ulUc27DrM4SNUPT2fQlckj1qP4Fal+YoPYJMlyZ8qhXfF3Y0tUDdUXl3vg0dFTi++VVOFfH/dgMS1ru9N8WU0HF9cUCTgPe+qVdSn/u7Mkda0GTw/QDcWPZ9KYGN2jSzfk0OVrMzt0yRHD64KMrUgPF2sFWcmP56KZSTAD61PUGeXrd49MgU1bL8OsVNWj91vIsalXwqf0qaWbwzv0lWETA4eElS3L99cYmU1nv9dRQTWbDyclScQTN6NIhV2j//+ZWbH7Z68kwM3Dy4dcUc1PQy8kRTl/4zcU9WGWfoakOMXuf69MXZQTEz+kJT1Dar8UN'
        c = encrypt(m, random.getrandbits(128))
        if c.find(b'hsctf{') != -1:
            print(c)

結果我去洗完澡還沒有跑完，看起來是沒用，看來只能小範圍窮舉。

import random
import base64


def f(x):
    random.seed(x)
    return random.getrandbits(8)


c = b'8OcTbAfL6/kOMQnC9v8SNmmSzvQMeGTT8vANM1T+7vIce2fo0fc2RnScrNxTSmeSyuMjMF//w8BWaXX91dsGcnvmreg0NQTw96ceVVXj3sQ3Znn51OU1S0bOyaMtNHTj36AcWFqewN4zRUXD6agGbAPE+tQtd3XG0doAa1Ll9fhcQ1zk0McTM1bv8PIQOAnn3vQ3UgLD3PsONXLs4KkXMnjTyMEQOFn/0uYVUwOY1PsleEHCyNopRVDr+Kc0e2PH9v0XNXfprfIPU3nw7KYTNX/G7twLSkHoyaUlQHXi3v02UHmdy/4iNgme3Pc8bgPp+tYWV1+YzPkXYkXM4ulUc27DrM4SNUPT2fQlckj1qP4Fal+YoPYJMlyZ8qhXfF3Y0tUDdUXl3vg0dFTi++VVOFfH/dgMS1ru9N8WU0HF9cUCTgPe+qVdSn/u7Mkda0GTw/QDcWPZ9KYGN2jSzfk0OVrMzt0yRHD64KMrUgPF2sFWcmP56KZSTAD61PUGeXrd49MgU1bL8OsVNWj91vIsalXwqf0qaWbwzv0lWETA4eElS3L99cYmU1nv9dRQTWbDyclScQTN6NIhV2j//+ZWbH7Z68kwM3Dy4dcUc1PQy8kRTl/4zcU9WGWfoakOMXuf69MXZQTEz+kJT1Dar8UN'
plaintext = base64.b64decode(c)

flag = list(map(ord, 'hsctf{'))

for i in range(200, 289):
    for r in range(2, 251):
        for key in range(1, 256):
            if plaintext[i] == flag[0] ^ ((key * r) % 251) \
                    and plaintext[i + 1] == flag[1] ^ ((f(key) * r) % 251) \
                    and plaintext[i + 2] == flag[2] ^ ((f(f(key)) * r) % 251) \
                    and plaintext[i + 3] == flag[3] ^ ((f(f(f(key))) * r) % 251):
                print(f'i={i}, r={r}, key={key}')
# i=247, r=187, key=135

r = 187
key = 135
flag = ''
for i in range(247, 295):
    tmp = (key * r) % 251
    tmp = chr(plaintext[i] ^ tmp)
    flag += tmp
    if tmp == '}':
        break
    else:
        key = f(key)
print(flag)

二元一次方程组

题目描述:
签到题

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

size = 256
e = 65537
p = number.getPrime(size)
q = number.getPrime(size)
avg = (p + q) / 2
n = p * q

m = libnum.s2n(flag)
c = pow(m, e, n)

print('n = %d' % n)
print('avg = %d' % avg)
print('c = %d' % c)

'''
n = 5700102857084805454304483466349768960970728516788155745115335016563400814300152521175777999545445613444815936222559357974566843756936687078467221979584601
avg = 75635892913589759545076958131039534718834447688923830032758709253942408722875
c = 888629627089650993173073530112503758717074884215641346688043288414489462472394318700014742820213053802180975816089493243275025049174955385229062207064503
'''

答案

水題，已知$p+q$和$p*q$的情況下。

$(p+q)^2 = p^2 + 2pq + q^2 (p-q)^2 = p^2 - 2pq + q^2$

p, q國中生看到這裡都會算，就不寫詳細過程了。

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 5700102857084805454304483466349768960970728516788155745115335016563400814300152521175777999545445613444815936222559357974566843756936687078467221979584601
avg = 75635892913589759545076958131039534718834447688923830032758709253942408722875
c = 888629627089650993173073530112503758717074884215641346688043288414489462472394318700014742820213053802180975816089493243275025049174955385229062207064503

p_add_q = avg * 2
p_minus_q = gmpy2.iroot(p_add_q * p_add_q - 4 * n, 2)[0]

q = (p_add_q - p_minus_q) // 2
p = p_add_q - q

phi = (p - 1) * (q - 1)
e = 65537

d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))

简单的LFSR

这是一个生成随机数的算法，简单吧~

from secret import secret

for b in secret: assert (b == '0' or b == '1')
assert (len(secret) == 128)


# a 01 string with length 128
# your flag is flag{md5(secret).hexdigest()}

def string2bits(s):
    return [int(b) for b in s]


def lfsr(state, mask):
    assert (len(state) == 128)
    assert (len(mask) == 128)

    output = 0
    for i in range(128):
        output = output + (state[i] * mask[i])

    return output


if __name__ == '__main__':
    initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0,
                 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0,
                 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1,
                 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
    mask = string2bits(secret)

    for i in range(256):
        state = initState[i:]
        output = lfsr(state, mask)
        initState += [output]

    outputState = initState[128:]
    print('outputState =', outputState)
    # 太常只給前面
    # outputState = [31, 66, 128, 222, 385, 664, 1143, 2000, 3458, 6003, 10379, 17942, 31047, 53687, 92924, 160797, 278304, 481638, 833479, 1442422, 2496163, 4319845, 7475835, 12937561, 22389578, 38746915, 67054735, 116043520, 200822710, 347539886, 601445745, 1040850538, 1801275628, 3117252874, 5394657302, 9335889442, 16156509611, 27960142496, 48387281659, 83738092531, 144915522009, 250787996657, 434008851435, 751087316130, 1299817167363, 2249438425629, 3892834588915, 6736864173067, 11658686709797, 20176297502410, 34916709837729, 60426182042628, 104572380769600, 180970937597032, 313184800936842, 541991553121913, 937960088661442, 1623215570164618, 2809105439634215, 4861383488449105]

下意識爆破，然後寫完爆破之後去上廁所的同時按了一下計算機才發現$2^{128}=3.4028237e+38$，謝…謝了哦。

import numpy as np


def lfsr(state, mask):
    # print(len(state), len(mask))
    assert (len(state) == 128)
    assert (len(mask) == 128)

    output = 0
    for i in range(128):
        output = output + (state[i] * mask[i])
    return output

# 太長只提供前面
outputState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1,
               0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0,
               0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0,
               1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 31, 66, 128, 222, 385, 664, 1143,
               2000, 3458, 6003, 10379, 17942, 31047, 53687, 92924, 160797, 278304, 481638, 833479, 1442422, 2496163,
               4319845, 7475835, 12937561, 22389578, 38746915, 67054735, 116043520, 200822710, 347539886, 601445745]
mask = np.zeros(128, dtype=int)

cnt = 0
while mask[0] < 2:
    cnt += 1
    if cnt % 10000 == 0:
        print(cnt)

    mask[127] += 1
    for i in range(127, 0, -1):
        if mask[i] == 2:
            mask[i - 1] += 1
            mask[i] = 0

    for i in range(256):
        state = outputState[i:i + 128]
        # print(state)
        output = lfsr(state, mask)
        if output != i + 128:
            break
        if i == 255:
            print(mask)

以上的程式只要電腦夠強，理論上應該跑得出來，但很明顯我的電腦不夠，只好另尋方法，應該可以變成線性方程組求解，透過256條方程式求128個變數，但懶得找套件，就先這樣。

[中等偏下] 线性反馈移位寄存器

题目描述:
听说这玩意儿不太安全emmm hint1: 异或运算与模2的加法是等价的。 hint2: 与运算和模2的乘法是等价的。

from secret import secret

for b in secret: assert (b == '0' or b == '1')
assert (len(secret) == 128)


# a 01 string with length 128
# your flag is flag{md5(secret).hexdigest()}

def string2bits(s):
    return [int(b) for b in s]


def bits2string(bs):
    s = [str(b) for b in bs]
    return ''.join(s)


def lfsr(state, mask):
    assert (len(state) == 128)
    assert (len(mask) == 128)

    output = 0
    for i in range(128):
        output = output ^ (state[i] & mask[i])

    return output


if __name__ == '__main__':
    initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0,
                 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0,
                 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1,
                 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
    mask = string2bits(secret)

    for i in range(256):
        state = initState[i:]
        output = lfsr(state, mask)
        initState += [output]

    outputState = bits2string(initState[128:])
    print('outputState =', outputState)
    #
    # outputState = 1010100001001011101000000100100001101011010100101011010101011010100100001110010010110111010111110000000000011011001110100011000111110100110011011011100111000000001100001000001011010011011010110110111100110101001110001001001000001110111011110001111001111111

解答

稍微改寫了一下，但跟上一題一樣輸光。

Equation

低能破題，題目沒出好。

import random
import libnum
from Crypto.Util import number
from gmpy2 import gcd
from secret import flag
assert len(flag) == 43
flag = [flag[(43//3)*i:(43//3)*(i+1)] for i in range(3)]

print('--- Part. 0 ---')
x0 = libnum.s2n(flag[0][:len(flag[0])//2])
y0 = libnum.s2n(flag[0][len(flag[0])//2:])
print('Hint: %d' % gcd(x0, y0))
l0 = len(bin(y0))-2
while True:
    a0 = random.randint(2, 2**(l0*3))
    b0 = random.randint(2, 2**(l0*3))
    if a0*x0 == b0*y0:
        break
# 2000/3 years later ...
print('a0 = %d' % a0)
print('b0 = %d' % b0)

print('--- Part. 1 ---')
x1 = libnum.s2n(flag[1][:len(flag[1])//2])
y1 = libnum.s2n(flag[1][len(flag[1])//2:])
print('Hint: %d' % gcd(x1, y1))
l1 = len(bin(y1))-2
while True:
    a1 = random.randint(2, 2**(l1*3))
    b1 = random.randint(2, 2**(l1*3))
    if a1*x1 - b1*y1 == 1:
        break
# 2000/3 years later ...
print('a1 = %d' % a1)
print('b1 = %d' % b1)

print('--- Part. 2 ---')
x2 = libnum.s2n(flag[2][:len(flag[2])//2])
y2 = libnum.s2n(flag[2][len(flag[2])//2:])
print('Hint: %s' % 'nicai')
l2 = len(bin(y2))-2
while True:
    a2 = random.randint(2, 2**(l2*3))
    b2 = random.randint(2, 2**(l2*3))
    if a2*x2 - b2*y2 <= y2:
        break
# 2000/3 years later ...
print('a2 = %d' % a2)
print('b2 = %d' % b2)

解答

第一階段是找出$a0*x0 == b0*y0$的數，所以把a0, b0對調除以gcd。

第二階段是透過連分數展開進行求解，此時可以得到

HSCTF{1e8d38ef-a949-4117-8ec

然後第三階段他的條件是$a2*x2 - b2*y2 <= y2$，隨便代入都會過，三小破題目，完全不該寫那麼久。

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

a0 = 30188147721117215781129100297502653147720244598096
b0 = 21570432690338300962113223428601821765217196091704

a1 = 2644612157538919571387894485245174170571484040764
b1 = 2439650961154362725659337213967574551053744888261

a2 = 3549540394738386267390659328154240007562582898045
b2 = 3396047733146044072945509494632282291396398974799

# 第一階段
print(long_to_bytes(b0 // gcd(a0, b0)), long_to_bytes(a0 // gcd(a0, b0)))


# 第二階段
# a1*x1 - b1*y1 == 1

# from https://github.com/pablocelayes/rsa-wiener-attack/blob/master/ContinuedFractions.py


def rational_to_contfrac(x, y):
    '''
    Converts a rational x/y fraction into
    a list of partial quotients [a0, ..., an]
    '''
    a = x // y
    pquotients = [a]
    while a * y != x:
        x, y = y, x - a * y
        a = x // y
        pquotients.append(a)
    return pquotients


def contfrac_to_rational(frac):
    '''Converts a finite continued fraction [a0, ..., an]
     to an x/y rational.
     '''
    if len(frac) == 0:
        return (0, 1)
    num = frac[-1]
    denom = 1
    for _ in range(-2, -len(frac) - 1, -1):
        num, denom = frac[_] * num + denom, num
    return (num, denom)


def convergents_from_contfrac(frac):
    '''
    computes the list of convergents
    using the list of partial quotients
    '''
    convs = [];
    for i in range(len(frac)):
        convs.append(contfrac_to_rational(frac[0:i]))
    return convs


frac = rational_to_contfrac(b1, a1)
convergents = convergents_from_contfrac(frac)
for x1, y1 in convergents:
    # print(x1, y1)
    try:
        if a1 * x1 - b1 * y1 == 1:
            print(long_to_bytes(x1), long_to_bytes(y1))
    except:
        pass