easyecc

签到题?意义不明

题目文件名 file.py

from fastecdsa.curve import P521 as Curve
from fastecdsa.point import Point
from Crypto.Util.number import bytes_to_long, isPrime
from os import urandom
from random import getrandbits, randint
from flag import flag
import hashlib
from Crypto.Util.number import long_to_bytes


ecc_p = Curve.p
a = Curve.a
b = Curve.b

Gx = Curve.gx
Gy = Curve.gy
G = Point(Gx, Gy, curve=Curve)
s = 41231
g = s * G

assert (flag == 'HITCTF2020{' + hashlib.md5(long_to_bytes(g.x + g.y)).hexdigest() + '}')
print("P:" + hex(ecc_p) + "\n")
print("a:" + hex(a) + "\n")
print("b:" + hex(b) + "\n")
print("g:", hex(G.x), hex(G.y))

文件名 out

P:0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
a:-0x3
b:0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00

g:0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650

安装那个 fastecdsa 发现只有 g 是会变的,输出的这个 g 是文件里的大 G,那我直接把这个值贴进去,把 assert 改写成 print 语句不就能输出 flag 了?确实

ezRSA

体现了一个数学思想:把未解决的问题转化成已经解决的问题

题目:

#!/bin/bash python2
from flag import flag
from Crypto.Util.number import *
import os

flag = flag+os.urandom(32)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
phi = (p-1)*(q-1)
d = inverse(e, phi)

m1 = bytes_to_long(flag)
m2 = bytes_to_long(flag+os.urandom(8))

assert pow(m1,3) > n

c1 = pow(m1,e,n) # m1 ^3 (mod n)
c2 = pow(m2,e,n) # (m1 * (2 ** 64) + garbage64) ^3 (mod n)

print "c1 = %d"%c1
print "c2 = %d"%c2
print  "n = %d"%n

'''
c1 = 80653989110793139102855968265870741534421660712327094406252902072101613222389965470648960909763762225046314865847982289607336162281576790259047039000290839621007818742162307587677505606906923990312494483089046762906753345262127057162580025978324312642501118741099945205580088180943278903718853065363662232083
c2 = 5400424653941721880728309040044485787870754570249463205700803061685717472238274158687499478247752712211743180931379853481727502849946080245130393042405383007613277703993980940893569303012323853427216643473698166348237252515222556282004058588218846910754415888401275689026778751805826968590155607937830708498
n = 92782661709340169703868140576276816382956055756557631391697803785121887338308072309948803413610339884338861040226250478895118923994109662815448681629315227440953320952623296140315432654804940766553284237954507627610922864055435652884184926768295740697589798180602153344302964255974935777945481843144629875127
'''

可以转化成 Coppersmith short-pad attack,通过加密 2^64 乘进去相当于把 m1 后面垫了 8 个 \0。把这个 https://github.com/pcw109550/write-up/tree/master/2020/Defenit/Double_Message 解题脚本爆改一下得到以下:

#!/usr/bin/env python
# coding: utf-8

# In[1]:
c1 = 80653989110793139102855968265870741534421660712327094406252902072101613222389965470648960909763762225046314865847982289607336162281576790259047039000290839621007818742162307587677505606906923990312494483089046762906753345262127057162580025978324312642501118741099945205580088180943278903718853065363662232083
c2 = 5400424653941721880728309040044485787870754570249463205700803061685717472238274158687499478247752712211743180931379853481727502849946080245130393042405383007613277703993980940893569303012323853427216643473698166348237252515222556282004058588218846910754415888401275689026778751805826968590155607937830708498
n = 92782661709340169703868140576276816382956055756557631391697803785121887338308072309948803413610339884338861040226250478895118923994109662815448681629315227440953320952623296140315432654804940766553284237954507627610922864055435652884184926768295740697589798180602153344302964255974935777945481843144629875127

# In[2]:
e=3
N=n
PRxy.<x,y> = PolynomialRing(Zmod(N))
PRx.<xn> = PolynomialRing(Zmod(N))
PRZZ.<xz,yz> = PolynomialRing(Zmod(N))
cc1 = (c1 * pow(2 ^ 64, 3, n)) % n
g1 = x^e - cc1
g2 = (x + y)^e - c2
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)

# In[3]:
h = q2.resultant(q1)
h = h.univariate_polynomial()
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()

# In[4]:
roots = h.small_roots(X=2 ^ 64, beta=1/16)
print(roots)

# In[5]:
diff = roots[0]

# In[6]:
x = PRx.gen()
g1 = x^e-cc1
g2 = (x+diff)^e-c2
while g2:
    g1, g2 = g2, g1 % g2
g = g1.monic()

# In[7]:
g.degree()

# In[8]:
msg = -g[0]
print(bytes.fromhex(hex(msg)[2:]))

DGK_Crypto

网上关于这个 DGK cryptosystem 的介绍少之又少,找到一个 https://yuyingwai.cn/2020/11/16/DGK%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6/

上面这篇可以说是原论文(10.1007/978-3-540-73458-1_30)的一个子集,基本知道是怎么回事

文件名 task.sage

#! /usr/bin/env sage
from secret import FLAG

class DGK(object):
    def __init__(self, nbits, lbits):
        self.nbits = nbits
        self.lbits = 2 * lbits
        self.pubkey, self.prikey = self.keygen()
        self.n, self.u, self.g, self.h = self.pubkey
        self.vp, self.vq, self.p, self.q = self.prikey
        
    def keygen(self):
        vpq_bits = 160
        vp = random_prime(2**vpq_bits,False,2**(vpq_bits-1))
        vq = random_prime(2**vpq_bits,False,2**(vpq_bits-1))
        u = 1 << self.lbits
        
        r1bits = self.nbits / 2 - vpq_bits - self.lbits
        flag = 0
        while not flag:
            r1 = random_prime(2**r1bits,False,2**(r1bits-1))
            p = (u*vp*r1) + 1
            flag = is_prime(p)
            
        r2bits = self.nbits / 2 - vpq_bits - 1 - self.lbits
        flag = 0
        while not flag:
            r2 = random_prime(2**r2bits,False,2**(r2bits-1))
            q = (u*vq*r2) + 1
            flag = is_prime(q)
        
        n = p * q
        
        xp = randint(0, p)
        
        e1 = (u >> 1) * vp * r1
        e2 = u * vp
        e3 = u * r1
        
        while not (pow(xp, e1, p)!=1 and pow(xp, e2, p)!=1 and pow(xp, e3, p)!=1):
            xp = randint(0, p)
            
        xq = randint(0, q)
        e1 = (u >> 1) * vq * r2
        e2 = u * vq
        e3 = u * r2
    
        while not (pow(xq, e1, q)!=1 and pow(xq, e2, q)!=1 and pow(xq, e3, q)!=1):
            xq = randint(0, q)

        qinv = inverse_mod(q, p)
        pinv = inverse_mod(p, q)
        g = (qinv * q * xp + pinv * p * vq) % n
        g = pow(g, r1*r2, n)
        h = pow(g, r1*r2*u, n)

        return (n, u, g, h), (vp, vq, p, q)

    def encrypt(self, pt):
        assert int(pt).bit_length() <= self.lbits
        r = randint(0, 2**400)
        r = pow(self.h, r, self.n)
        ct = pow(self.g, pt, self.n)
        ct = Integer((ct * r) % self.n)
        return ct
            
    
if __name__ == "__main__":
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    assert len(FLAG)  == 72
    dgk = DGK(1024, 32)
    chunks, chunk_size = len(FLAG), 8
    flag_num = [bytes_to_long(FLAG[i:i+chunk_size]) for i in range(0, chunks, chunk_size)]
    cts = [dgk.encrypt(i) for i in flag_num]
    encs = []
    acc = 1
    for ct in cts:
        acc = (acc * ct) % dgk.n
        encs.append(acc)
        
    vp, vq, p, q = dgk.prikey
    with open("public.txt", "w+") as f:
        f.write(str(dgk.pubkey))
    with open("hint.txt", "w+") as f:
        f.write(str(vp*vq) + "\n")
        f.write(str((p+q)>>100))
    with open("encs.txt", "w") as f:
        f.write(str(encs))

通过给的两个 hint 可以得到私钥,先导入这个 https://github.com/ubuntor/coppersmith-algorithm 代码

# In[2]:
n = 21188841931691524901076573605187290891011021005265268821329407004076842588970263355746365272765678529460219551975772284806921642745939436948384819822845523128208236685849251571302763385064674292860255333374683533873779357474377772256798227528027008615030263468072711088566519479346252137119710626911719784449
u = 2 ^ 64
hpq = 7370081827144744025027729605466327358037482023043764824311394927402566682144007483592423176449199911128420893084007669920155
vv = 779847951253040881087724809801668297471494866526007425579051102141483035699083390357616416323093

# In[53]:
P.<x, y> = PolynomialRing(ZZ)
X, Y = 2^448, 2^100
hhpq = hpq << 100
pol = (u * x + 1) * (hhpq - u * x + y) - n
results = coron(pol, X, Y)

# In[54]:
x, y = results[0]

# In[58]:
p = u * x + 1
q = n // p
vp = gcd(x, vv)
vq = vv // vp

嗯,之后我就不会了…… 也没人讲,就这样

就算不分解也可以验证 encs[0]HITCTF20

def cmp(plain, cipher):
    reduced = pow(cipher, vv, n)
    return reduced == pow(g, plain * vv, n)