Crypto

前言

有师傅想学习下本战队密码wp，战队成员表示很乐意，尽管鄙人近日考试面试繁忙，让各位等待良久，但仍不敢怠慢，经过精心的整理后公开如下，希望师傅们可以不计前嫌，鄙人顿首

LockByLock

考虑到 secureProcedure 中已经给出了 $c_1=m^{e_1}\bmod n$ 和 $c_2=m^{e_2}\bmod n$，并且很大概率满足 $\gcd(e_1,e_2)=1$，只要求出 $n,e_1,e_2$ 即可使用共模攻击得到 $m$

向两次 proxyProcedure 中传入 $2$ 和 $2^2=4$，则 $(2^{e_1}\bmod n)^2-((2^2)^{e_1}\bmod n)$ 和 $(2^{e_2}\bmod n)^2-((2^2)^{e_2}\bmod n)$ 是 $n$ 的倍数，求 $\gcd$ 再去掉小因子即可得到 $n$

求出 $n$ 后再 BSGS 即可得到 $e_1,e_2$

交互获得数据脚本

from pwn import *
import math

context.log_level = 'debug'
io = connect("tcp.cloud.dasctf.com",26050)

io.recvuntil(b"Alice: locked msg1 = ")
me1 = int(io.recvline())

io.recvuntil(b"Bob: locked msg2 = ")
me1e2 = int(io.recvline())

io.recvuntil(b"Alice: unlocked msg3 = ")
me2 = int(io.recvline())

print("c1 =",me1)
print("c2 =",me2)

io.sendline(str(2).encode())

io.recvuntil(b"Alice: locked msg1 = ")
m2e1 = int(io.recvline())

io.recvuntil(b"Bob: locked msg2 = ")
m2e1e2 = int(io.recvline())

io.recvuntil(b"Alice: unlocked msg3 = ")
m2e2 = int(io.recvline())

print(m2e1)
print(m2e2)

io.sendline(str(4).encode())

io.recvuntil(b"Alice: locked msg1 = ")
m4e1 = int(io.recvline())

io.recvuntil(b"Bob: locked msg2 = ")
m4e1e2 = int(io.recvline())

io.recvuntil(b"Alice: unlocked msg3 = ")
m4e2 = int(io.recvline())

print(math.gcd(m2e1 **2 -m4e1,m2e2 **2 -m4e2))

BSGS 和共模攻击的脚本

import gmpy2
from Crypto.Util.number import *

n = 22995627661568976068473175656721680983944969067496980846283721053080888036692954338447897131235552930387945538246692009669626778602458920650752149301370606882167416062454563238360436279955975280890348611988642331532555987926106050646000158798561704565454201725802642089436015649512007649781157301025240785527026882599573553326345786137955076785934272657678789519933779231738262248416232407419157234272519914696525458824877880216875048265157626938473898879083787972002938449279550009019849114083338622674088465121691273820985162720544115975606785613319285515424185607075596542657483152050424724459894441659231337116097

c1 = 5856351049993156163555331002452035907676332589745452879501013054774973986671789992183459318084674864610939600510845424022931986015203866461165071633903626403095160181332893975206867473585926987726261007321000830402715716148216483801377177102866632385702151118389309047898230747880083817382363511598449885700550802297442108623114570956049973230140300984993726077350524454422751592301107491571726412532016695621722286689058992256060301336228576929277175979526682114134875162678371457347698946074982734057340640016465753600725361177491491503868636831775644824306589745639596074380401733082679674514857186642641268284457
c2 = 18075222667420434513915572466414576989746003019914599039176842357287521172392226474855946630181509262758954145596480236442546977600029183481526282995412214044995600615217928568889327361959081581071682414216796221709524628788551132075445936046532029103141593439831667598337910755908178647406045208337344214371150958635592568335692709913832933594811604446263830097222782755054988520727945758284003469889709134846580792320552934728610637200875828336363118625532402173365483086247954856624667536819659218697888906187725372800143091759313498360032810052740756734825423328078164417463424217678637008843661081436296679454476
m2e1 = 11850314947410898168742835343257224608644293281976542227703899839655737114747437775446330559056708116752369638988034199469431340843041793133985723094099444176547686223414669899323553850030680875300890154786405934636802365928995895755919449811582871483815104162493051991168415396343127986463181069648991579132389021511555450545733004571531047237460529514831708261399469636617555397320114965168381001793922137119150784358527865384256845983930127276007420288897608392532155246180280887750859543940256743170590992267657299446373928639521513492118906670753231757562634074225031000535447391192019266209387091238705922670878
m2e2 = 15580320344630684338407100214614349256515140217978169436920992096402748792895845139890394701342675364812418645507681838800921185360727995434883501201864927529294319069486433501701263837796921128474032958367521903711632477527528321043175313991795419693015635681667319463858862161720349437947697375592869685277750572798957230884286001310783431961476251141206400387453813472488612988479426409248785039276874812400917340194640569001798862629854311935762817216278618373542774443654922927585547677166684951713503008700828796972581906805530457899805709278890504322921156020707861174959332752969729596749427052911454490012986

def baby_step_giant_step(step, modulo, ct1, ct2, pt):
    known_small_powers = {1: 0}
    prev = 1
    for i in range(1, step):
        curr = (prev * pt) % modulo
        known_small_powers[curr] = i
        prev = curr
        if i % 100000 == 0:
            print(i)
    subtractor = pow(pow(pt, step, modulo), -1, modulo)

    x = ct1
    i = 0
    while x not in known_small_powers:
        i += 1
        x = (x * subtractor) % modulo
        if i % 100000 == 0:
            print(i)
    res1 = step * i + known_small_powers[x]
    print('res1:', res1)

    x = ct2
    i = 0
    while x not in known_small_powers:
        i += 1
        x = (x * subtractor) % modulo
        if i % 100000 == 0:
            print(i)
    res2 = step * i + known_small_powers[x]
    print('res2:', res2)
    return res1, res2

g = gmpy2.mpz(2)
m2e1 = gmpy2.mpz(m2e1)
m2e2 = gmpy2.mpz(m2e2)
#e1, e2 = baby_step_giant_step((3 * 10 ** 7), n, m2e1, m2e2, g)
#print(e1, e2)

e1 = 256069535521247
e2 = 557388553011601

g, r, s = gmpy2.gcdext(e1, e2)
m = pow(c1, r, n) * pow(c2, s, n) % n
print(long_to_bytes(int(m)))

MyErrorLearn

在两组数据上消去 secret 得到关于两组 getPrime(246) 的方程，多元 coppersmith 求解再带回即可得到 secret

# sage
from pwn import *

import itertools
from random import randint

context.log_level = 'debug'

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 []

io = connect("tcp.cloud.dasctf.com", "22818")

io.recvuntil(b"> mod = ")
p = int(io.recvline())

sleep(1)
io.sendline(b"1")
io.recvuntil(b"> r = ")
r1 = int(io.recvline())

io.recvuntil(b"> d = ")
d1 = int(io.recvline())

io.sendline(b"1")
io.recvuntil(b"> r = ")
r2 = int(io.recvline())

io.recvuntil(b"> d = ")
d2 = int(io.recvline())

P = PolynomialRing(Zmod(p), names=('c1', 'c2'))
(c1, c2) = P.gens()

f = (c1 + d1) - (c2 + d2) + (c1 + d1) * (c2 + d2) * (r1 - r2)

bounds = (2 ^ 246, 2 ^ 246)
c1, c2 = small_roots(f, bounds)[0]

secret = 1/(c1+d1)-r1

io.sendline(b"2")
io.sendline(str(secret).encode())

print(io.recvline())

结语

据战队密码手介绍，出题人视频wp也可以借鉴
https://www.bilibili.com/video/BV1UA411z78Z

道路漫长，共勉！