Automne's Shadow.

ISITDTU CTF 2019 WriteUp Part2

fermat multi-primes prng
2019/07/05 Share

Crypto

Easy_RSA_2

题目给出的python脚本内容如下：

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

flag = '##################################'
p1 = getPrime(512)
p2 = gmpy2.next_prime(p1)
q1 = getPrime(512)
q2 = gmpy2.next_prime(q1)
n = p1*p2*q1*q2
e = 65537
phi = (p1-1)*(p2-1)*(q1-1)*(q2-1)
d = gmpy2.invert(e,phi)
c = pow(bytes_to_long(flag),e,n)

print pow(p1+q2,65537,n)
#5043622010330564722783560796388733110223192234657313797979729183216316602247790170027393145104828283812158304519218370476380897023249898720267053051908498011845198383126598688185743313040451851234309071530873683667360872515868401870834371902623509762498919172464493397284930232415029297203698778851121422456149280629701148108649396642433199634388011535777204188207597427548981195309015900421249473588077922607729093939587454170211363784480831197764238579460361668878037335596700513382133341370374840639374005225742007557272153800433699784092511039693877686425832957477808359462507401596842526527374816943302475357302
print pow(p2+q1,65537,n)
#7919283184559406259028604751155413696993375814336862337694645459367829841130544291770103966362177145582007048754925168845793555136985754996486596987205043932984314934297789456823769422776642272151478021108135062833657996366160688598742804847633068533451034898357435150319123770512604358033881809960916484049603490477616900480883862825416570459592254659007024761917196293369565486538943942938968226701375668351560376904094935919442322484791587819687743780031411339960372463937311578960714219580981945254129150844798674023932645363519148439092971133029751088847668041720574694350298717079140377388740434213791727288722
print n 
#8573641536164485111081609341110540574423426701587222458588002464807917555910942077276167528046769327390058096169685188870928286845342631974847171845103806710768418462668311621275704636581042137915505959767806384415314024549489538717607173007829067492516776714817262226691787436227002924225311861164296655909746846329870548266285498682510415418053656271623482202491805513797215793596385014264449282551352796096361524482384994633912515104414237252657058698433260597636367614328512751722615849959987780969423318207123668118325176544879335267439096589035064596631756303300860315257404427016819145298919974287174103934503
print c 
#8436043641135865531308468859210199431445831063674810351906331674115825605849862045115409554309732867926457428348729196827592921108183774070414343257409618631078896543782150761081732376735501920417229787663210936174854000594130785353102718054331606096192133481536724402629697019651921188121029927710787682993814748802295545306899075962041017278877203965796981792702098381465051289581518257202127401748725944229037078896857591660248467597356051123218945757343652461844056927461929195427880969904210166880623689090977714615839624798930450630919330253477634839161931755642681718034910946900928731231093352169252474939674

getPrime(512)表示随机返回一个512bit的prime number(质数)

gmpy2.next_prime(p1)表示返回下一个大于p1的质数

1
2
p1 = getPrime(512)
p2 = gmpy2.next_prime(p1)

由此可见，p1和p2比较接近

同理q1和q2也比较接近

又因为

1
n = p1*p2*q1*q2

可以理解为

1
2
n = (p1*q2)*(q1*p2)
  = (p1*q1)*(q2*p2)

那么n就可以使用fermat attack去分解

将RsaCtfTool里的fermat.py添加参数，就可以求出分解后的因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Source - http://stackoverflow.com/a/20465181
from gmpy2 import isqrt

def fermat(n):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)
    count = 0
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1
    p = a+b
    q = a-b
    assert n == p * q
    return p, q

n = 8573641536164485111081609341110540574423426701587222458588002464807917555910942077276167528046769327390058096169685188870928286845342631974847171845103806710768418462668311621275704636581042137915505959767806384415314024549489538717607173007829067492516776714817262226691787436227002924225311861164296655909746846329870548266285498682510415418053656271623482202491805513797215793596385014264449282551352796096361524482384994633912515104414237252657058698433260597636367614328512751722615849959987780969423318207123668118325176544879335267439096589035064596631756303300860315257404427016819145298919974287174103934503
print fermat(n)

运行结果如下

1
(mpz(92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135377198629507140256023102013131493810077402487620597574150419252484604398426042348936643985371724093575122287222535733709825807203222224632574777263054682547849L), mpz(92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135375408481531310003733935540422655297910944762679239039783193372674051452613244254750117673971732027355424665752849172881712190463569600293779394868475158854447L))

但是这里存在4个质数（multi-primes）

可以修改fermat的代码，尝试得到两组满足条件的质数

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
import gmpy2

def fermat_factorization(n):
    factor_list = []
    gmpy2.get_context().precision = 2048
    a = int(gmpy2.sqrt(n))

    a2 = a * a
    b2 = gmpy2.sub(a2, n)

    while True:
        a += 1
        b2 = a * a - n

        if gmpy2.is_square(b2):
            b2 = gmpy2.mpz(b2)
            gmpy2.get_context().precision = 2048
            b = int(gmpy2.sqrt(b2))
            factor_list.append([a + b, a - b])

        if len(factor_list) == 2:
            break

    return factor_list

n = 8573641536164485111081609341110540574423426701587222458588002464807917555910942077276167528046769327390058096169685188870928286845342631974847171845103806710768418462668311621275704636581042137915505959767806384415314024549489538717607173007829067492516776714817262226691787436227002924225311861164296655909746846329870548266285498682510415418053656271623482202491805513797215793596385014264449282551352796096361524482384994633912515104414237252657058698433260597636367614328512751722615849959987780969423318207123668118325176544879335267439096589035064596631756303300860315257404427016819145298919974287174103934503
print fermat_factorization(n)

运行得到结果，可以看到有2组数据，4个质数

1
2
[[92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135377198629507140256023102013131493810077402487620597574150419252484604398426042348936643985371724093575122287222535733709825807203222224632574777263054682547849L, 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135375408481531310003733935540422655297910944762679239039783193372674051452613244254750117673971732027355424665752849172881712190463569600293779394868475158854447L],
[92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135380738930065081697951287140042893321203653899791236620373028885001354525656928787903118347895059813547629304512431677110164891730095638508629167931628303931903L, 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135371868180973368561805750413511255786784693350508599993560583740157301325382357815783643311448396307382917648462953229481373105936696186417725004199901537674201L]]

标记为：[X1,Y1]，[X2,Y2]

又根据

1
2
3
n = p1*p2*q1*q2
  = p1*q1 * p2*q2 = X1 * Y1
  = p1*q2 * p2*q1 = X2 * Y2

那么通过

1
p1*q1 和 p1*q2

就可以使用最大公约数(GCD)求得p1，然后q1也可以求得

1
2
3
4
p1 = GCD(X1,X2)
q1 = X1/p1
p2 = GCD(Y1,Y2)
q2 = Y1/p2

代码参考https://github.com/pcw109550/write-up/tree/master/2019/ISITDTU/Easy_RSA_2

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from Crypto.Util.number import GCD, inverse, long_to_bytes as l2b
import gmpy2


def fermat_factorization(n):
    factor_list = []
    gmpy2.get_context().precision = 2048
    a = int(gmpy2.sqrt(n))

    a2 = a * a
    b2 = gmpy2.sub(a2, n)

    while True:
        a += 1
        b2 = a * a - n

        if gmpy2.is_square(b2):
            b2 = gmpy2.mpz(b2)
            gmpy2.get_context().precision = 2048
            b = int(gmpy2.sqrt(b2))
            factor_list.append([a + b, a - b])

        if len(factor_list) == 2:
            break

    return factor_list


def main():
    c = 8436043641135865531308468859210199431445831063674810351906331674115825605849862045115409554309732867926457428348729196827592921108183774070414343257409618631078896543782150761081732376735501920417229787663210936174854000594130785353102718054331606096192133481536724402629697019651921188121029927710787682993814748802295545306899075962041017278877203965796981792702098381465051289581518257202127401748725944229037078896857591660248467597356051123218945757343652461844056927461929195427880969904210166880623689090977714615839624798930450630919330253477634839161931755642681718034910946900928731231093352169252474939674
    e = 65537
    n =8573641536164485111081609341110540574423426701587222458588002464807917555910942077276167528046769327390058096169685188870928286845342631974847171845103806710768418462668311621275704636581042137915505959767806384415314024549489538717607173007829067492516776714817262226691787436227002924225311861164296655909746846329870548266285498682510415418053656271623482202491805513797215793596385014264449282551352796096361524482384994633912515104414237252657058698433260597636367614328512751722615849959987780969423318207123668118325176544879335267439096589035064596631756303300860315257404427016819145298919974287174103934503
    factor_list = fermat_factorization(n)
    print factor_list
    [X1, Y1] = factor_list[0]
    [X2, Y2] = factor_list[1]
    assert X1 * Y1 == n
    assert X2 * Y2 == n

    #p1 = GCD(X1, X2)
    #p2 = X1 / p1
    #q1 = GCD(Y1, Y2)
    #q2 = Y1 / q1

    p1 = GCD(X1,X2)
    q1 = X1/p1
    p2 = GCD(Y1,Y2)
    q2 = Y1/p2

    phi = (p1 - 1) * (q1 - 1) * (p2 - 1) * (q2 - 1)
    d = inverse(e, phi)
    flag = l2b(pow(c, d, n))

    print(flag)

if __name__ == "__main__":
    main()

运行后得到flag

automne

decrypt to me

题目源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import binascii
def generate_prg_bit(n):
    state = n
    while True:
        last_bit = state & 1
        yield last_bit
        middle_bit = state >> len(bin(n)[2:])//2 & 1
        state = (state >> 1) | ((last_bit ^ middle_bit) << (len(bin(n)[2:])-1))
flag = '###########'
enc = "OKQI+f9R+tHEJJGcfko7Ahy2AuL9c8hgtYT2k9Ig0QyXUvsj1B9VIGUZVPAP2EVD8VmJBZbF9e17"
flag_bin_text = bin(int(binascii.hexlify(flag), 16))[2:]
prg =  generate_prg_bit(len(flag_bin_text))
ctext = []
flag_bits = [int(i) for i in flag_bin_text]
for i in range(len(flag_bits)):
    ctext.append(flag_bits[i] ^ next(prg))  
ciphertext = '0b' + ''.join(map(str, ctext))
n = int(ciphertext, 2)
print binascii.unhexlify('%x' % n).encode('base64')

经过测试发现，len(flag_bin_text)和len(ciphertext)-2的值一样

于是可以由密文推导出伪随机数生成器 generate_prg_bit(n)的种子n

在测试过程中，可以发现需要在二进制数据前添加0才能保证前后长度一致

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
import binascii

def generate_prg_bit(n):
    state = n
    while True:
        last_bit = state & 1
        #print last_bit
        yield last_bit
        middle_bit = state >> len(bin(n)[2:])//2 & 1
        state = (state >> 1) | ((last_bit ^ middle_bit) << (len(bin(n)[2:])-1))
flag = 'ISITDTU{B'
print len(flag)
enc = "OK9yn2BczcGa"
flag_bin_text = bin(int(binascii.hexlify(flag), 16))[2:]
print len(flag_bin_text)
prg =  generate_prg_bit(len(flag_bin_text))
ctext = []
flag_bits = [int(i) for i in flag_bin_text]
for i in range(len(flag_bits)):
    ctext.append(flag_bits[i] ^ next(prg))  
ciphertext = '0b' + ''.join(map(str, ctext))
n = int(ciphertext, 2)
print ciphertext
print len(ciphertext)-2
print binascii.unhexlify('%x' % n).encode('base64')

print bin(int(binascii.hexlify(enc.decode('base64')), 16))
ciphertext2 = bin(int(binascii.hexlify(enc.decode('base64')), 16))[2:]
print len(ciphertext2)
n2 = int(ciphertext2, 2)
print binascii.unhexlify('%x' % n2).encode('base64')

运行效果如下图，可以看得比较直观

automne

由此可以得到准确的长度值

最终的脚本，参考https://github.com/pcw109550/write-up/blob/master/2019/ISITDTU/decrypt_to_me/solve.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
import binascii
from Crypto.Util.number import long_to_bytes as l2b, bytes_to_long as b2l

def generate_prg_bit(n):
    state = n
    while True:
        last_bit = state & 1
        yield last_bit
        middle_bit = state >> len(bin(n)[2:])//2 & 1
        state = (state >> 1) | ((last_bit ^ middle_bit) << (len(bin(n)[2:])-1))
flag = '###########'
enc = "OKQI+f9R+tHEJJGcfko7Ahy2AuL9c8hgtYT2k9Ig0QyXUvsj1B9VIGUZVPAP2EVD8VmJBZbF9e17"
flag_bin_text = bin(int(binascii.hexlify(flag), 16))[2:]
prg =  generate_prg_bit(len(flag_bin_text))
ctext = []
flag_bits = [int(i) for i in flag_bin_text]
for i in range(len(flag_bits)):
    ctext.append(flag_bits[i] ^ next(prg))  
ciphertext = '0b' + ''.join(map(str, ctext))
n = int(ciphertext, 2)

print bin(int(binascii.hexlify(enc.decode('base64')), 16))
ciphertext2 = bin(int(binascii.hexlify(enc.decode('base64')), 16))[2:]
print len(ciphertext2)
n2 = int(ciphertext2, 2)
print binascii.unhexlify('%x' % n2).encode('base64')
ciphertext3 = '0'+ciphertext2
print ciphertext3
prg = generate_prg_bit(len(ciphertext3))
pt = ""
for e in ciphertext3:
    pt += str(next(prg) ^ int(e))
flag =  l2b(int(pt,2))
print flag

运行得到flag

automne

原文作者: Automne

原文链接: https://ce-automne.github.io/2019/07/05/ISITDTU-CTF-2019-WriteUp-Part2/

发表日期: July 5th 2019, 11:00:00 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Easy_RSA_2
  2. 2. decrypt to me
Total : 62
2021
2020
2019
2018
2017
lfsr z3 python reverse fat git broadcastreceiver sha-1 cbc sqli sqlite golang race condition luks hashcat photorec MAC sso oauth 2.0 padding oracle csp xss abe vdex ransomware frida ndk pwntools hashpumpy sourceleakhacker ecb socat fastjson JdbcRowsetImpl idea servlet volatility inet_aton boneh durfee lcg rabin egcd cipolla's algorithm spi snakeyaml ScriptEngineManager malware codereflect mysql yara plugin deserialization log4j rsa binary javascript prototype pollution nodejs shiro ysoserial primefac rsatool ssl AES tshark gmpy2 RsaCtfTool Hex flask ssti ecc Modular operation WebGoat8 order by tomcat nim game .iso gpg outguess sage google cloud sdk zsteg base58 fermat multi-primes prng rmi jndi Paillier Cryptosystem rsa lsb oracle SQL Injection ping delay xor CAS 单点登录 渗透测试 weblogic xxe reflect 010 editor gcd
Crypto Android Web Forensics Misc