not only RSA

题目描述：

这个模数好像很不安全，那你能解密出flag吗

from Crypto.Util.number import bytes_to_long
from secret import flag
import os

n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
m = bytes_to_long(flag)

flag = flag + os.urandom(n.bit_length() // 8 - len(flag) - 1)
m = bytes_to_long(flag)

c = pow(m, e, n)

with open('out.txt', 'w') as f:
    print(f"{n = }", file=f)
    print(f"{e = }", file=f)
    print(f"{c = }", file=f)

做题流程：

$n=p^5$
$\phi(n)=p^4(p-1)$
$ed\equiv 1(mod\ p^4(p-1))$
e和$\phi(n)$不互质，考虑AMM
$c\equiv m^e(mod\ n)$
同余性质转到：
$c\equiv m^e(mod\ p)$
用AMM得到：
$m_p\equiv m(mod\ p)$
考虑用Hensel将模p下结果提升到$p^5$

尝试用nth_roots直接开到$p^5$
exp:

from Crypto.Util.number import *

n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747

c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
p = 91027438112295439314606669837102361953591324472804851543344131406676387779969
r = p ** 5

K = Zmod(r)
funcp = K(c % r).nth_root(e, all = True )
#flag{c19c3ec0-d489-4bbb-83fc-bc0419a6822a}

discrete_log

题目描述：

离散对数分离

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
flag = 'flag{d3b07b0d416ebb}'

assert len(flag) <= 45
assert flag.startswith('flag{')
assert flag.endswith('}')

m = bytes_to_long(pad(flag.encode(), 128))

p = 0xf6e82946a9e7657cebcd14018a314a33c48b80552169f3069923d49c301f8dbfc6a1ca82902fc99a9e8aff92cef927e8695baeba694ad79b309af3b6a190514cb6bfa98bbda651f9dc8f80d8490a47e8b7b22ba32dd5f24fd7ee058b4f6659726b9ac50c8a7f97c3c4a48f830bc2767a15c16fe28a9b9f4ca3949ab6eb2e53c3
g = 5

assert m < (p - 1)

c = pow(g, m, p)

with open('out.txt', 'w') as f:
    print(f"{p = }", file=f)
    print(f"{g = }", file=f)
    print(f"{c = }", file=f)

做题流程:

比较离谱的一道题目，题目描述中的flag是小于45位，但实际只有去掉flag标识后只有12位。。。
flag = 'flag{'+m+'}'+pading
$flag=256^{k_1}num_{flag}+256^{k_2}m+256^{k_3}num_{pad}$
$g^{flag}=y\ (mod\ p)$
$g^{256^{k_1}num_{flag}+256^{k_2}m+256^{k_3}num_{pad}}=y\ (mod\ p)$
$g^{256^{k_1}num_{flag}}*g^{256^{k_2}m}*g^{256^{k_3}num_{pad}}=y\ (mod\ p)$
$g^{256^{k_2}m}=y'\ (mod\ p)$
由费马小定理：
$g^{\phi(p)}\equiv1\ (mod\ p)$
所以想到找到一个d满足：
$256^{k_2}d\equiv1(mod \phi(p))$
却发现$256^{k_2}$和$\phi(p)$不互质
而恰好我们可以发现这个p是个安全质数满足：$p=2q+1$
且g是一个阶为q的元，有：
$g^q\equiv1(mod\ p)$
所以我们可以转到在模$q$下找d：
$256^{k_2}d\equiv1(mod\ q)$
找到d后即可得：
$g^m\equiv (y')^d\ (mod\ p)$
然后可以用中间相遇攻击

from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from gmpy2 import *
import tqdm
import sys

p = 173383907346370188246634353442514171630882212643019826706575120637048836061602034776136960080336351252616860522273644431927909101923807914940397420063587913080793842100264484222211278105783220210128152062330954876427406484701993115395306434064667136148361558851998019806319799444970703714594938822660931343299
c = 105956730578629949992232286714779776923846577007389446302378719229216496867835280661431342821159505656015790792811649783966417989318584221840008436316642333656736724414761508478750342102083967959048112859470526771487533503436337125728018422740023680376681927932966058904269005466550073181194896860353202252854
g = 5

k1 = 256 ** (128 - 5)

for i in range(45):
    flag_mode = pad(b'flag{' + b'\x00' * i + b'}', 128)
    k2 = 256 ** (128 - 5 - i)
    flag = bytes_to_long(flag_mode)

    num_pad = powmod(g, bytes_to_long(flag_mode[i + 5:]), p) 

    num_flag = powmod(g, bytes_to_long(flag_mode[:5]) * k1, p)

    inv_pad = invert(num_pad, p)
    inv_flag = invert(num_flag, p)
    inv_m =  invert(k2, (p - 1) // 2)

    y = powmod(c * inv_pad * inv_flag  % p, inv_m, p)

    meet = i // 2
    list = {}
    k_former = 256 ** (i - meet)
    for j in tqdm.tqdm(range(16 ** meet)):
        flag_former = bytes_to_long(hex(j)[2:].rjust(meet, '0').encode()) * k_former
        flag_former = powmod(g, flag_former, p) 
        temp = invert(flag_former, p) * y % p
        list[temp] = j

    for j in tqdm.tqdm(range(16 ** (i - meet))):
        flag_latter = bytes_to_long(hex(j)[2:].rjust(i - meet, '0').encode()) 
        flag_latter = powmod(g, flag_latter, p) 
        if flag_latter in list.keys():
            print('flag{' + hex(list[flag_latter])[2:] + hex(j)[2:] + '}')
            sys.exit(0)

#flag{61e8007dd65f}

guess game

题目描述：

以下任一个均可
nc 47.97.69.130 22333

做题流程：

这题更是重量寄，被非预期了
根据审计代码可知
此题只需要在80轮中猜中56轮以上即可
根据概率估算，80轮猜中x轮大概满足一个标准二项分布，且猜中56轮以上的概率大概有万分之一
根据生日攻击理论，我们交互一万次的情况下，我们就有大概60%的概率能够赢56轮以上
所以我们只需要不断交互，给他发送数据

from pwn import *
import sys

while True:
    io = remote('47.97.69.130', 22333)
    io.recvuntil(b'team token:')
    io.sendline(b'1')
    io.recvuntil(b'>')
    io.sendline(b'2')
    for i in range(80):
        t = io.recvuntil('>')
        io.sendline(b'1')
    
    inf = io.recvall()
    print(inf)
    if b'Fail' not in inf:
        print(inf)
        io.interactive()
        sys.exit(0)
    io.close()
    print('over')