帕鲁杯

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.8k 阅读时长 ≈ 6 分钟

记录帕鲁杯Crypto题解

两元钱的铜匠

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from secret import flag
from Crypto.Util.number import *
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m, 65537, n)
N = getPrime(1024)
leak = (pow(9999, 66666)*p + pow(66666, 9999)*q) % N
print(f'n={n}')
print(f'c={c}')
print(f'N={N}')
print(f'leak={leak}')
"""
n=80916351132285136921336714166859402248518125673421944066690210363157948681543515675261790287954711843082802283188843248579293238274583917836325545166981149125711216316112644776403584036920878846575128588844980283888602402513345309524782526525838503856925567762860026353261868959895401646623045981393058164201
c=22730301930220955810132397809406485504430998883284247476890744759811759301470013143686059878014087921084402703884898661685430889812034497050189574640139435761526983415169973791743915648508955725713703906140316772231235038110678219688469930378177132307304731532134005576976892978381999976676034083329527911241
N=175887339574643371942360396913019735118423928391339797751049049816862344090324438786194807609356902331228801731590496587951642499325571035835790931895483345540104575533781585131558026624618308795381874809845454092562340943276838942273890971498308617974682097511232721650227206585474404895053411892392799799403
leak=161177488484579680503127298320874823539858895081858980450427298120182550612626953405092823674668208591844284619026441298155371399651438065337570099147890081125477609238234662000811899869636390550619251741676887565983189442613760093303841954633720778312454175652907352477365434215186845209831284593041581382419
"""

记$tmp_1 = 9999^{66666}$，$tmp_2 = 66666^{9999}$

有$leak \equiv tmp_1\times p + tmp_2 \times q \mod N$

两边同乘$p$，得到
$$
leak\times p \equiv tmp_1\times p^2 + tmp_2\times n \mod N
$$
只有$p$是未知的，解方程即可

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
import libnum

n=
c=
N=
leak=

tmp1 = 9999**66666
tmp2 = 66666**9999

R.<p> = PolynomialRing(Zmod(N))

f = tmp1*p**2 + tmp2*n - leak*p
root = f.roots()


p = int(root[1][0])
q = n // p 
d = gmpy2.invert(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(libnum.n2s(int(m)))
# paluctf{6699669966996699669966996699}

01110

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import getPrime, getRandomRange, bytes_to_long
from random import randrange
from flag import flag

p = getPrime(512)
q = getPrime(512)
n = p * (q**2)
e = 65537

while True:
    z = randrange(1, n)
    if all(pow(z, (x - 1) // 2, x) == x - 1 for x in (p, q)):
        break


def encrypt_bit(m, n, z):
    secret = getRandomRange(1, n - 1)
    return (pow(secret, 2, n) * pow(z, m, n)) % n

m = int(bin(bytes_to_long(flag))[2:])
c = []
while m:
    bit = m % 10
    c.append(encrypt_bit(bit, n, z))
    m //= 10

print("n=", n)
print("gift1=", pow((p + q), e, n))
print("gift2=", pow((p - q), e, n))
print("z=", z)
print("c=", c)

if all(pow(z, (x - 1) // 2, x) == x - 1 for x in (p, q))这串代码保证了z是模p,q的二次非剩余

即勒让德符号$(\frac{z}{p})=(\frac{z}{q}) = -1$

加密的时候有$c_i \equiv secret^2 \times z^{m_{i}} \mod n$

当$m_i$是0的时候，雅可比符号$(\frac{c_i}{n}) = 1$

当$m_i$是1的时候，根据雅可比符号的积性，雅可比符号$(\frac{c_i}{n}) = 1\times (\frac{z}{p})\times (\frac{z}{q})\times (\frac{z}{q}) = -1$

通过雅可比符号的值来恢复m

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from libnum import *
from Crypto.Util.number import *

c = []
n = 390643660915400759356028673149168279560687093035302974183909784119138903637101610150171466601442693220550718178154721365461636077209566533154335718201358899342358662848545345180263124134588375803369006010468316238614932369094974862842683683363587543473163915923045398254122306762084945489324575516415794686273949909352344088141474136179402651003388916093283318052977257982248730053350207666237541564674407802737159850168950514444047006592253696165165211262564161

m = ""
for i in c:
    if jacobi(int(i),n) == 1:
        m += '0'
    else:
        m += '1' 
        
print(long_to_bytes(int(m[::-1],2)))
# paluctf{1_4m_th3_b0td_1n_t3st_1n_th3_r0w}

江枫渔火对愁眠

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
flag = b'paluctf{******************}'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p * q
e = 0x10001
c = pow(m, e, n)
leak1 = p & q
leak2 = p | q
print(n)
print(leak1)
print(leak2)
print(c)
# 116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
# 8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
# 13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
# 77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658

剪枝就行了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
sys.setrecursionlimit(3000)

leak1 = 8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
leak2 = 13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
N = 116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
c = 77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658

# 低位往高位爆

def findp(p,q):
    if len(p) == 512:
        pp = int(p,2)
        if N % pp == 0:
            print("p = ",pp)
            print("q = ",N // pp)

    else:
        l = len(p)
        pp = int(p,2)
        qq = int(q,2)
        if (pp & qq) % (2 ** l) == leak1 %(2**l) and pp * qq %(2 ** l) == N % (2**l) and (pp | qq) % (2 ** l) == leak2 % (2**l):
            findp('1' + p,'1' + q)
            findp('1' + p,'0' + q)
            findp('0' + p,'1' + q)
            findp('0' + p,'0' + q)
            
findp('1','1')

得到p,q，然后常规解就行

gcccd

task

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
python
from Crypto.Util.number import getStrongPrime, GCD, bytes_to_long
import os
from flag import flag

def long_to_bytes(long_int, block_size=None):
    """Convert a long integer to bytes, optionally right-justified to a given block size."""
    bytes_data = long_int.to_bytes((long_int.bit_length() + 7) // 8, 'big')
    return bytes_data if not block_size else bytes_data.rjust(block_size, b'\x00')

def gen_keys(bits=512, e=5331):
    """Generate RSA modulus n and public exponent e such that GCD((p-1)*(q-1), e) == 1."""
    while True:
        p, q = getStrongPrime(bits), getStrongPrime(bits)
        n = p * q
        if GCD((p-1) * (q-1), e) == 1:
            return n, e

def pad(m, n):
    """Pad the message m for RSA encryption under modulus n using PKCS#1 type 1."""
    mb, nb = long_to_bytes(m), long_to_bytes(n)
    assert len(mb) <= len(nb) - 11
    padding = os.urandom(len(nb) - len(mb) - 3).replace(b'\x01', b'')
    return bytes_to_long(b'\x00\x01' + padding + b'\x00' + mb)

def encrypt(m, e, n):
    """Encrypt message m with RSA public key (e, n)."""
    return pow(m, e, n)

n, e = gen_keys()
m = pad(bytes_to_long(flag), n)
c1, c2 = encrypt(m, e, n), encrypt(m // 2, e, n)

print(f"n = {n}\ne = {e}\nc1 = {c1}\nc2 = {c2}")

# n = 128134155200900363557361770121648236747559663738591418041443861545561451885335858854359771414605640612993903005548718875328893717909535447866152704351924465716196738696788273375424835753379386427253243854791810104120869379525507986270383750499650286106684249027984675067236382543612917882024145261815608895379
# e = 5331
# c1 = 60668946079423190709851484247433853783238381043211713258950336572392573192737047470465310272448083514859509629066647300714425946282732774440406261265802652068183263460022257056016974572472905555413226634497579807277440653563498768557112618320828785438180460624890479311538368514262550081582173264168580537990
# c2 = 43064371535146610786202813736674368618250034274768737857627872777051745883780468417199551751374395264039179171708712686651485125338422911633961121202567788447108712022481564453759980969777219700870458940189456782517037780321026907310930696608923940135664565796997158295530735831680955376342697203313901005151

相关消息攻击，这里需要注意的是m // 2，因为flag最后一位是”}”，所以m是奇数，在// 2 之后会把1抹去。

把m // 2设为x，则两个多项式分别是:
$$
f_1 = (2x+ 1)^e - c_1
$$

$$
f_2 = x^e - c_2
$$

e不是很大，就没用HGCD了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# sage
from Crypto.Util.number import *
import random
import gmpy2

n = 
e = 5331
c1 = 
c2 = 

def franklinReiter(n,e,c1,c2):
    PR.<m> = PolynomialRing(Zmod(n))
    g1 = (2*m + 1)^e - c1
    g2 = m^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]


m = franklinReiter(n,e,c1,c2)
flag = long_to_bytes(int(2*m+1))
print(flag)
# flag{6a096839-3ccb-46b4-9eb0-841ca85c0f63}

peeeq

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
python
import gmpy2
from Crypto.Util.number import *


def check(m, p, q):
    if m == 0: return True
    if m >= p and check(m-p, p, q) : return True
    if m >= q and check(m-q, p, q) : return True
    return False

flag = b"paluctf{***********************}"

p = getPrime(1024)
q = getPrime(1024)
e = getPrime(17)
n = p*q


leak = 20650913970072868759959272239604024297420806808659110564312051736808778949599012338389873196411652566474168134639876252857623310159737758732845898956842366935678501021994729279299799994075598575657211550223683499328614158165787416177094173112167115888930719187253398687736037116845083325669521670262760600243895871953940839864925909273175442587377607028910874730344252804963645659770898616148180806608083557249713184454706023876544328444568520666837841566163924062054001534893538655581481021600384148478571641075265311650046699619525464106135807483192890198614434965478741402348088647355476402189540171838712520668315
pinv_e = gmpy2.invert(p, q)*e
qinv_e = gmpy2.invert(q, p)*e
m = bytes_to_long(flag)
c = pow(m, e, n)
print(c)
print(pinv_e)
print(qinv_e)
m = 0
while True:
    assert m <= leak or check(m, p, q)
    m += 1
# 14656499683788461319601710088831412892194505254418064899761498679297764485273476341077222358310031603834624959088854557947176472443021560072783573052603773463734827298069959304747376040480522193600487999140388188743055733577433643210327070027972481119823973316743393323273128561824747871183252082782459568278265418266528855123687868624734106855360408027492126167597948385055908257193701028960507382053300960017612431744000472268868103779169759349652561826935960615964589526055579319224213399173783902104833907847546751649110661705034653912439791460180154034041113546810232929706136321281991114377628823527206109309013
# 12474140378771043865022148848078136936465079800066130234618983104385642778672967864991495110508733111980066517889153671507701349679185396054215439179349403857665966245686661757089470553109534987101888628107055364941617805783362125836104920292552457095662777743387917809524955960583091720618281570118299619677634759
# 1647206449953560407401595632741127506095799998014240087894866808907042944168674423038307995055460808040825182837354682801054048594394389801771888111156812819183105159993880849157459496014737241461466870906700457127028184554416373467332704931423207098246831148428600375416541264997943693621557486559170922000282251

参考(16 封私信 / 2 条消息) m、n互质，如何求最小正整数K，使得所有≥K的正整数都能用am+bn来表示，其中a、b为自然数？ - 知乎 (zhihu.com)

能知道leak就是$\phi(n) - 1$，然后是求p,q

已知$(p^{-1}\mod q)\times e$ 和$(q^{-1} \mod p)\times e$，取二者公因数便可以得到e,然后可以得到$p^{-1} \mod q$和$q^{-1} \mod p$

然后有$pp^{-1} = k_1q + 1$，$qq^{-1} = k_2p + 1$

移项得到$k_1q = pp^{-1} - 1$,$k_2p = qq^{-1} - 1$

相乘得$k_1k_2n = pp^{-1}qq^{-1} - (pp^{-1} + qq^{-1}) + 1$

化简得$(p^{-1}q^{-1} - k_1k_2)n = pp^{-1} + qq^{-1} - 1$

考虑到$p^{-1} < p$，$q^{-1} < q$，因此$(p^{-1}q^{-1} - k_1k_2)$必须为1

解方程即可

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import gmpy2

leak = 20650913970072868759959272239604024297420806808659110564312051736808778949599012338389873196411652566474168134639876252857623310159737758732845898956842366935678501021994729279299799994075598575657211550223683499328614158165787416177094173112167115888930719187253398687736037116845083325669521670262760600243895871953940839864925909273175442587377607028910874730344252804963645659770898616148180806608083557249713184454706023876544328444568520666837841566163924062054001534893538655581481021600384148478571641075265311650046699619525464106135807483192890198614434965478741402348088647355476402189540171838712520668315
c = 14656499683788461319601710088831412892194505254418064899761498679297764485273476341077222358310031603834624959088854557947176472443021560072783573052603773463734827298069959304747376040480522193600487999140388188743055733577433643210327070027972481119823973316743393323273128561824747871183252082782459568278265418266528855123687868624734106855360408027492126167597948385055908257193701028960507382053300960017612431744000472268868103779169759349652561826935960615964589526055579319224213399173783902104833907847546751649110661705034653912439791460180154034041113546810232929706136321281991114377628823527206109309013
pinv_e = 12474140378771043865022148848078136936465079800066130234618983104385642778672967864991495110508733111980066517889153671507701349679185396054215439179349403857665966245686661757089470553109534987101888628107055364941617805783362125836104920292552457095662777743387917809524955960583091720618281570118299619677634759
qinv_e = 1647206449953560407401595632741127506095799998014240087894866808907042944168674423038307995055460808040825182837354682801054048594394389801771888111156812819183105159993880849157459496014737241461466870906700457127028184554416373467332704931423207098246831148428600375416541264997943693621557486559170922000282251

t = gmpy2.gcd(pinv_e,qinv_e)
# 307689
e = 102563
phi = leak + 1

pinv = pinv_e // e
qinv = qinv_e // e

# var("p q")
# f1 = p*pinv + q*qinv - 1 == p*q
# f2 = (p-1)*(q-1) == phi
# res = solve([f1,f2],[p,q])
# print(res)

p = 151832619619952089992267716058068444251307600220706203871589765844990819175654042917774490787590849720202969240992246624166668570786235406779778934647681250166384828094778797880304323848041273713831052602978130708287523575488166230706021974231380611512371425017998262828486267505916086636495016213117818476079
q = 136011049679334940861511595857042329781653809853866436171389745534855895446196665892885140663304371230055953209984856118200410958041858815679721863717912611066674050454954534686280510303474769670492647228370259394337403855556056590338482704020086450814990436480639792318856245688841995452742464887239898730723
n = p*q
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(bytes.fromhex(hex(int(m))[2:]))
# paluctf{51b98a17-6843-4e3b-b06c-3cd956bc944c}

lcccg

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
python
import secrets
from Crypto.Util.number import bytes_to_long

flag = b'paluctf{***********}'
class LCG:
    def __init__(self):
        self.x = secrets.randbits(64)
        self.a = 2
        self.m = secrets.randbits(64)

        while self.m % 2 == 0:
            self.m = secrets.randbits(64)

        print("m =", self.m)
    
    def next(self):
        self.x = (self.x * self.a) % self.m
        return self.x

lcg = LCG()

assert b"paluctf" in flag
f = bytes_to_long(flag)

l = f.bit_length()
print("length =", l)

r = 0
for i in range(l + 50):
    r += (lcg.next() & 1) << i

print("cipher =", r ^ f)
# m = 7870528503754256659
# length = 311
# cipher = 3255815260238431584829132773479447408817850185229659648404208268001256903206776002292220185602856730646093869

很明显的思路是先把seed求出来，再求r

因为$seed_1 \equiv 2seed_0 \mod m$，并且r的每一位代表了当前seed的最低位是0还是1，即当前的seed是偶数还是奇数。

因为m是奇数，如果当前seed是奇数，那就说明$2seed_0 > m$

最后给出的结果如下图

1
2
3
|--------------------------r------------------------|
               |-----------------f------------------|
|----r(50bit)--|-----------------r^f----------------|

因为flag头是paluctf{，，所以我们可以得到更多信息，像下图这样

1
2
3
|--------------------------r------------------------|
               |paluctf{---------f------------------|
|----r(50bit)--|r(63bit)---------r^f----------------|

我们可以通过这113bit的r，通过二分法推断倒数113状态的seed，然后就可以得到最初的seed(比m小)

关于二分法，我讲不太明白

最后就是感谢鸡块师傅的exp

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from Crypto.Util.number import *

m = 7870528503754256659
length = 311
cipher = 3255815260238431584829132773479447408817850185229659648404208268001256903206776002292220185602856730646093869
prefix = bytes_to_long(b"paluctf{")


#################################################### part1 get seed
stream = (bin((cipher >> (length - len(bin(prefix)[2:]))) ^ prefix)[2:].zfill((50 + len(bin(prefix)[2:]))))[::-1]
# 注意这个逆序

l = 0
r = 2**64
lm = 0
rm = 1
for i in range(len(stream)):
    if(stream[i] == "1"):               # 增大下界
        lm = 2*lm + 1                   
        rm = 2*rm                       
        l = max(l,lm*m // 2**(i+1))
    elif(stream[i] == "0"):             # 减小上界
        lm = 2*lm                       
        rm = 2*rm - 1                   
        r = min(r,rm*m // 2**(i+1))
seed = r

#################################################### part2 get flag
for i in range(361 - len(stream)):
    seed = seed * inverse(2,m) % m

r = 0
for i in range(length + 50):
    seed = 2 * seed % m
    r += (seed & 1) << i

print(long_to_bytes(r ^ cipher))

#paluctf{1_am_a_l0ng_l3g1n_1s_n0t_a_l!!}
-------------已经到底啦！-------------