Jarvis OJ -- crypto题（下）

发表于 | 更新于 | 分类于
Jarvis OJ -- crypto题（下）

[61dctf]bbencode

题目给了一个py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
flag = open("flag", "r").read().strip()
assert len(flag) == 32
def str2num(s):
    return int(s.encode('hex'), 16)
def bbencode(n):
    a = 0
    for i in bin(n)[2:]:
        a = a << 1
        if (int(i)):
            a = a ^ n
        if a >> 256:
            a = a ^ 0x10000000000000000000000000000000000000000000000000000000000000223L
    return a

print bbencode(str2num(flag))

#result:61406787709715709430385495960238216763226399960658358000016620560764164045692

因为是异或，所以重复encode就能拿到flag了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def bbencode(n):
    a = 0
    for i in bin(n)[2:]:
        a = a << 1
        if (int(i)):
            a = a ^ n
        if a >> 256:
            a = a ^ 0x10000000000000000000000000000000000000000000000000000000000000223L
    return a


result = 61406787709715709430385495960238216763226399960658358000016620560764164045692
for i in range(3000):
    result = bbencode(result)
    if 'flag{'.encode('hex') in hex(result)[2:-1]:
        print hex(result)[2:-1].decode('hex')

flag{you_xian_yu_huan_leduo!!}

[61dctf]rsappend

1
2
3
4
➜  rsappend_101ghfuaori488hs9 ls -l
total 96
-rwxr-xr-x@ 1 ioot  staff  41140  4  3  2017 result
-rwxr-xr-x@ 1 ioot  staff    761  4  3  2017 rsappend.py

rsappend.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
flag = open("flag", "r").read().strip()
assert len(flag) == 32

import primefac
import random
from os import urandom
def genprime(l):
    l/=8
    big=1
    while(l):
        big=big<<8
        l-=1
    big-=1
    small=(big+1)>>4
    temp=random.randint(small,big)
    return primefac.nextprime(temp)
def str2num(s):
    return int(s.encode('hex'), 16)
def padding(s):
    return s+urandom(abs(256-len(s)))


def rsappend(m):
    p = genprime(2048)
    q = genprime(2048)
    n = p * q
    result=[str(n)+"\n"]
    pm=padding(flag)
    for i in range(32):
        e=genprime(32)
        c=pow(str2num(pm),e,n)
        result.append(str(e)+"###"+str(c)+"\n")
    return "".join(result)
open("result","w").write(rsappend(flag))

第一直觉是共模攻击，pm为256位，前32位是flag，后224位是随机填充值。但是又仔细一想，共模攻击的条件是加密同一明文，这里很明显不满足，但是如果不是共模攻击，这题除了往死里爆破p和q，就没办法了啊。先不管那么多，试试共模攻击

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
import gmpy2
from Crypto.Util.number import long_to_bytes

with open('rsappend/result', 'r') as file:
    rsas = file.readlines()

n = int(rsas[0].strip())
eandc = {}
for i in rsas[1:]:
    e = int(i.strip().split('###')[0])
    c = int(i.strip().split('###')[1])
    eandc[e] = c
e1 = eandc.keys()[0]
cipher1 = eandc[e1]
e2 = eandc.keys()[11]
cipher2 = eandc[e2]
gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
    s = -s
    cipher1 = gmpy2.invert(cipher1, n)
if t < 0:
    t = -t
    cipher2 = gmpy2.invert(cipher2, n)
plain = gmpy2.powmod(cipher1, s, n) * gmpy2.powmod(cipher2, t, n) % n
print long_to_bytes(plain)

另外在这里，我尝试取不同组的(e, c)，最后的结果居然一样，这就解释了为什么能进行共模攻击，因为他给的result文件并不是按他给的脚本加密出来的，应该是出题的意识到无解，然后悄悄把随机那里变成了固定的padding

1
2
3
4
5
6
7
➜  crypto python rsappend.py
flag{we_do_ctf_together_for_fun}\gK�m7����a�Ś3Ö�m+��3��'���R
                                                            ���
Po6��q�cMK	R�5�̱vRs�Q�2+�� �����N��!�HAy@����a.I�v\�����2���l
sȬܛ�$�"IH�,V-~�E����Y��UG��e�9gu�w�����Ӂ_1���=EiN���J(��
                                                        ;����x'pڽW���*�?�t
 ֚E�ɚ

[61dctf]rsa（not solved）

1
2
3
4
➜  ~ cd Downloads/rsa
➜  rsa ls
alice_public_key.py communication.py    send.bak
bob_public_key.py   keygen.sage

其中send.bak是128字节的乱码，然后分别看一下每一个文件的内容

keygen.sage

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
58
59
60
61
62
63
64
65
66
67
68
69
#!/usr/bin/env sage
# coding=utf-8

proof.arithmetic(False)

threshold = 21 << 1018 # just chosen arbitrarily:)

def genKey(n, nd):
    '''
    Designed with the awesome idea that generating two RSA key pairs
    that have the same public and private exponents to reduce the
    storage requirements!
    '''

    assert n/2 > nd
    tmp = n/2 - nd

    while True:
        while True:
            x1 = randrange(2^(nd-1), 2^nd)
            x2 = randrange(2^(tmp-1), 2^tmp)
            p1 = x1*x2 + 1
            if p1.is_prime():
                print '[+]bit length of p1:', int(p1).bit_length()
                break

        while True:
            y2 = randrange(2^(tmp-1), 2^tmp)
            p2 = x1*y2 + 1
            if p2.is_prime():
                print '[+]bit length of p2:', int(p2).bit_length()
                break

        while True:
            y1 = randrange(2^(nd-1), 2^nd)
            q1 = y1*y2 + 1
            if q1.is_prime():
                print '[+]bit length of q1:', int(q1).bit_length()
                break

        count = 0
        while True:
            d = randrange(2^(nd-1), 2^nd)
            if gcd(x1*x2*y1*y2, d) != 1:
                continue
            e = int(1/Mod(d, (p1-1)*(q1-1)))
            k1 = (e*d - 1) // ((p1-1)*(q1-1))
            assert e*d == (p1-1)*(q1-1)*k1 + 1
            q2 = k1*x2 + 1
            if q2.is_prime():
                print '[+]bit length of q2:', int(q2).bit_length()
                break
        n1 = p1 * q1
        n2 = p2 * q2
        n1, n2 = max([n1, n2]), min([n1, n2])
        if n1 <= threshold:
            print '[+]N for encryptions is too small!'
            continue
        if n2 >= threshold:
            print '[+]N for signatures is too large!'
            continue
        break

    assert int(pow(pow(0xdeadbeef, e, n1), d)) == 0xdeadbeef
    assert int(pow(pow(0xdeadbeef, e, n2), d)) == 0xdeadbeef
    return (e, d, n1, n2)

if __name__ == '__main__':
    print genKey(1024, 342)

communication.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
37
38
39
40
41
42
43
44
45
#!/usr/bin/env python
# coding=utf-8
from os import urandom
from secret_socket import socket_with_bob
import alice_private_key
import bob_public_key

def str2int(s):
    return int(s.encode('hex'), 16)

def int2str(i):
    tmp = hex(i)[2:].strip('L')
    tmp = ('0' if len(tmp)%2 else '') + tmp
    return tmp.decode('hex')

def sign_and_encrypt(m):
    m = urandom(126-len(m)) + '\x00' + m
    sig = pow(str2int(m), alice_private_key.d, alice_private_key.N2)
    assert sig < bob_public_key.N1
    sig_enc = pow(sig, bob_public_key.e, bob_public_key.N1)
    return int2str(sig_enc)

def decrypt_and_verify(c):
    sig = pow(str2int(c), alice_private_key.d, alice_private_key.N1)
    assert sig < bob_public_key.N2
    message = pow(sig, bob_public_key.e, bob_public_key.N2)
    message = int2str(message)
    message = message[message.rindex('\x00')+1:]
    return message

s = socket_with_bob()
recv_enc = s.recv()
recv_message = decrypt_and_verify(recv_enc)
assert recv_message == "Ooops, my flag have been encrypted by wannacry! Could you please send it to me again, Alice?"

with open('flag.txt') as f:
    flag = f.read()
send_message = "Well, OK... Here is what you what: {}".format(flag)
assert len(send_message) < 128
to_send = sign_and_encrypt(send_message)
s.send(to_send)
s.close()

with open('send.bak', 'wb') as f:
    f.write(to_send)

bob_public_key.py

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/env python
# coding=utf-8

# Generated by genKey(1024, 342) in keygen.sage

e = 57019382772166837488750427040015464490863175936396575556290232679668259683514801918298546850349718538222635977304361506235546587039055174992606638351023434322917005735910505716857963030159773221874370814472973319422853023944637626372539074831161749650232791256091117301145054914651557523038888181457290682237

N1 = 68253958478963934124300215757460723273691925280596309221863375905836387105252457670797482776100691909463871547306272253629697109054703333176926409544379734932863965587299902358818026560280727724874176607409038276642286734734838152097800253007709025880304435661500771500046972983240470823245360867996258239121

N2 = 58831168144192031952989136031836716698976227434725683505500936300434624499242689272670040374754049533739858144785202063762391111213777476380071324869525517503277889732429358219404717664025176836710995641523459333571168229803403205064106761733957455221168205091994936332421038092333687260644067187030525515969

alice_public_key.py

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/env python
# coding=utf-8

# Generated by genKey(1024, 342) in keygen.sage

e = 16140311304784625807971244520043756160102111440186500282911137675250199677022940503982292569233803572106227632954920805936151799049981849612210588147943318190599476331582153430089688143361226994947530603424082905816220548156412649246782363716825121201733242060234874574393149811078415952220812029904096645141

N1 = 73871864906066571406532457145607595847175670495017175565388132342574183187410380661917315431292987479576202710800243301821110154265031908769855345111418669574603508401169110155260587673272035301147668990301239964950207744512780378527326467318883681760821710529273075846801071296284930852211925448126134456371

N2 = 10548244241379959973012698997313565838321599691374783075397881482031959048170291643267402594849260277539547268187806692681844616430159988384126260317181183835757828333838579492655650376150221839149317599035426574857154820265992983356076281713571392012617269312376565128009638293040584673854656713040776519371

不难看出，要解密send.bak，我们需要先用bob的私钥对(bob.d, bob.n1)得到sig，然后再用alice的公钥对(alice.e, alice.n2)解密得到明文。alice的公钥我们直接从题目给的文件就能得到，那么我们要做的就是通过bob的(e, n1, n2)拿到bob的私钥d。

卡了两天，尽可能尝试了我已知的RSA攻击方法，都不能解出私钥d，毕竟500分的题。。。能力有限，此题日后在肝

[61dctf]cry

nc pwn2.jarvisoj.com 9891

下载得到一个py文件

cry.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import primefac
import random
from os import urandom
class Unbuffered(object):
   def __init__(self, stream):
       self.stream = stream
   def write(self, data):
       self.stream.write(data)
       self.stream.flush()
   def __getattr__(self, attr):
       return getattr(self.stream, attr)
import sys
from Crypto.Cipher import AES
def aes_cbc_encode(password,iv,m):
    cipher = AES.new(password, AES.MODE_CBC, iv)
    return cipher.encrypt(m)
def aes_cbc_decode(password,iv,c):
    cipher = AES.new(password, AES.MODE_CBC, iv)
    return cipher.decrypt(c)
sys.stdout = Unbuffered(sys.stdout)
def genprime(l):
    l /= 8
    big = 1
    while l:
        big = big << 8
        l -= 1
    big -= 1
    small = (big + 1) >> 4
    temp = random.randint(small, big)
    return primefac.nextprime(temp)
def rsa_gen():
    p = genprime(1024)
    q = genprime(1024)
    n = p * q
    e = 65537
    d = primefac.modinv(e,(p-1)*(q-1)) % ((p-1)*(q-1))
    return (p,q,n,e,d)
def num2str(num):
    h=hex(num)[2:].replace("L","")
    if len(h)%2 ==0 :
        return h.decode("hex")
    else:
        return ("0"+h).decode("hex")
def str2num(str):
    return int(str.encode("hex"),16)
def pad16(str):
    addl=16-(len(str)%16)
    return "a"*addl+str

def run():
    print "====welcome to cry system===="
    (p,q,n,e,d)=rsa_gen()
    print "give you the public key:"
    print "n:"+hex(n).replace("L","")
    print "e:"+hex(e).replace("L","")
    try:
        c=int(raw_input("give me the crypted message in hex:")[2:].strip(),16)
        m=pow(c,d,n)
    except:
        print "wrong input"
    print "your message is",num2str(m)

    flag=open("pathtoflag","r").read().strip()
    aes_key=urandom(16)
    iv=urandom(16)
    cf=aes_cbc_encode(aes_key,iv,pad16(flag))
    ck=pow(str2num(aes_key),e,n)
    civ = pow(str2num(iv), e, n)
    print "encrypted flag:"+cf.encode("base64")+'#'+hex(ck).replace("L","")+'#'+hex(civ).replace("L","")+'#'+hex(p).replace("L","")[2:182]+"##"
run()

先nc看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
➜  rsa nc pwn2.jarvisoj.com 9891
====welcome to cry system====
give you the public key:
n:0xa42a850d5ce6b8f89183a6fe90dce4be0e7b60f7e8e98b8c8971961febf183ab7b384885a83296762d7e3acb1ecfe2e0eaf039e7305eef0bac54c645952dd8d0d94ec299dfb67d0425a5eeb548f91cec20a853409cddb66a1730bdb5d63258f01c32249cd4534d1968ba6eab99d13f18ab073662fff820b98307887fb5133e2b7652ff86275bd51fbbb15317b99725784c64b37e8baa5c5ae3dc06a8fec0e7816a81eb1892cc98f45a9d33bd0746c360d2fa8e3e0ff9e7c990a0b177c5f702731f352684285dab31c599ad5702ac4552cbec32732fb04382162d6aa6d50a4d970507e23b814501bb6eed1b92f7f40d13f547ba3157c73919f245e4d3689a4417
e:0x10001
give me the crypted message in hex:0x2
your message is ?�գ3�
I���}����Y-�
�b`"Ol!�.��oui,C�i��u
�~�;�j�gQ�����K�S��L�A�~�D��'�����;�
                                    7��H��!i��>��1k^�P��ab�%��t�e
                                                                  e�q�yo5?sbKց��ہ�%5��k�ʥ]��3�]���˰-MKČ"�f��Η+ݺ���?~i�ՅǛ �iG���,��R�W��vzZ
                                                          �6|#
                                                              �H���^s��^l�ll7ɼA�l�4�1�J�a-
encrypted flag:U3o7vRfdgI9i4ptERBRnN0X+FbmRhsItyAwbMOn3ZQI=
#0x366aa884d263c43350d82ee1ee398d6d0b36f311b6a4d4da3f735ffc675974483b515b094d8cac952602811aa6e97b69a75dfca1517197efc80e353a382731ec5ae8630049b5bcc094b337a31e8be4eb84a9b1315b71796476cf1ed85c925f4bd01b01b855d38b52dc329160e05f9107a193fa361193d8eb8bbac090fc2e1815bb4f456019a5ba95ff479ba21b8600b72c5295d968c6dbffa0c6e8c8f7ebbe81f58626dca746b60bbd5418aff1e1940002b7fe03c5e5ae3b593878d3cf31b7ae804bdf2f6cc7c595ef42647e16e493ad5f6e38c25d1e8f8c1faf23a880d52b4b1198863f2e70941ab52596bea9546a1f97d1916da7d34c040134897a2c77d7b9#0x861536e0a5f39072748bcceb04769508a3fdbd0bf928f440d393cba94b9f92bd26cb720ecaaf24ae6b9d034eef20d5dfa15caed87ad49ef37689e57f28cad3390123b29bd8d88ee073e10a5b2090413e1204e6aa3fcade64486ca54d0dc5c9346b69fb56b728a373ad0e7b50bbe9f74918045b0cf8012620a903feda7a939d42643e50dcba82e2d40d27b83bd08f9f3c610f32266d69ebd15849cd98802e2a93120cb0d92b677ea27164293da7f815cb4626c227f0dcd45b2070738256ccbfa5ce71ff6f65ae18ef5f425202e039ec483f30e01f39157bca0f94afcc183a6e008c1c32c5bd08f2bba790bbcc1196cf96dc8929b5040f66d93edae11587f7cb59#b14920e61a918e42650219cdcab669dad3cd1b985af6892a522b61bc2dc45cb15b33673c679ceaf10312cb9c7169e01e460afcba37c8917288e34bb5ad84a2ae9ed3256e7c3175c83b59e34180222576b18baa52e88948f728c7##

我们知道p的高180*4即720bit，p一共1024bit，所以采用Factoring with high bits known

原理及例子：
https://github.com/mimoo/RSA-and-LLL-attacks#factoring-with-high-bits-known

下面是我按照上面nc得到的结果写的sage脚本

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
# nc pwn2.jarvisoj.com 9891
from sage.all import *
import binascii
from Crypto.Cipher import AES
n = 0xa42a850d5ce6b8f89183a6fe90dce4be0e7b60f7e8e98b8c8971961febf183ab7b384885a83296762d7e3acb1ecfe2e0eaf039e7305eef0bac54c645952dd8d0d94ec299dfb67d0425a5eeb548f91cec20a853409cddb66a1730bdb5d63258f01c32249cd4534d1968ba6eab99d13f18ab073662fff820b98307887fb5133e2b7652ff86275bd51fbbb15317b99725784c64b37e8baa5c5ae3dc06a8fec0e7816a81eb1892cc98f45a9d33bd0746c360d2fa8e3e0ff9e7c990a0b177c5f702731f352684285dab31c599ad5702ac4552cbec32732fb04382162d6aa6d50a4d970507e23b814501bb6eed1b92f7f40d13f547ba3157c73919f245e4d3689a4417
e = 0x10001
flag = 'U3o7vRfdgI9i4ptERBRnN0X+FbmRhsItyAwbMOn3ZQI='
s = '#0x366aa884d263c43350d82ee1ee398d6d0b36f311b6a4d4da3f735ffc675974483b515b094d8cac952602811aa6e97b69a75dfca1517197efc80e353a382731ec5ae8630049b5bcc094b337a31e8be4eb84a9b1315b71796476cf1ed85c925f4bd01b01b855d38b52dc329160e05f9107a193fa361193d8eb8bbac090fc2e1815bb4f456019a5ba95ff479ba21b8600b72c5295d968c6dbffa0c6e8c8f7ebbe81f58626dca746b60bbd5418aff1e1940002b7fe03c5e5ae3b593878d3cf31b7ae804bdf2f6cc7c595ef42647e16e493ad5f6e38c25d1e8f8c1faf23a880d52b4b1198863f2e70941ab52596bea9546a1f97d1916da7d34c040134897a2c77d7b9#0x861536e0a5f39072748bcceb04769508a3fdbd0bf928f440d393cba94b9f92bd26cb720ecaaf24ae6b9d034eef20d5dfa15caed87ad49ef37689e57f28cad3390123b29bd8d88ee073e10a5b2090413e1204e6aa3fcade64486ca54d0dc5c9346b69fb56b728a373ad0e7b50bbe9f74918045b0cf8012620a903feda7a939d42643e50dcba82e2d40d27b83bd08f9f3c610f32266d69ebd15849cd98802e2a93120cb0d92b677ea27164293da7f815cb4626c227f0dcd45b2070738256ccbfa5ce71ff6f65ae18ef5f425202e039ec483f30e01f39157bca0f94afcc183a6e008c1c32c5bd08f2bba790bbcc1196cf96dc8929b5040f66d93edae11587f7cb59#b14920e61a918e42650219cdcab669dad3cd1b985af6892a522b61bc2dc45cb15b33673c679ceaf10312cb9c7169e01e460afcba37c8917288e34bb5ad84a2ae9ed3256e7c3175c83b59e34180222576b18baa52e88948f728c7##'
ck = int(s.strip('#').split('#')[0][2:], 16)
civ = int(s.strip('#').split('#')[1][2:], 16)
p = int(s.strip('#').split('#')[2], 16)

pbits = 1024
kbits = pbits - p.bit_length()
p = p << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    p = p+int(roots[0])
    print "p: ", hex(int(p))
    assert n % p == 0
    q = n/int(p)
    print "q: ", hex(int(q))
    phin = (p-1)*(q-1)
    d = inverse_mod(e,phin)
    print "d:", hex(int(d))

aes_key = hex(int(pow(ck, d, n)))[2: -1]
print "aes_key: ", aes_key
iv = hex(int(pow(civ, d, n)))[2: -1]
print "iv: ", iv
cipher = AES.new(aes_key.decode('hex'), AES.MODE_CBC, iv.decode('hex'))
print cipher.decrypt(flag.decode('base64'))

运行结果

1
2
3
4
5
6
7
➜  crypto sage cry.sage
p:  0xb14920e61a918e42650219cdcab669dad3cd1b985af6892a522b61bc2dc45cb15b33673c679ceaf10312cb9c7169e01e460afcba37c8917288e34bb5ad84a2ae9ed3256e7c3175c83b59e34180222576b18baa52e88948f728c74b83308bfdff9a36bfc3461523b43b0b7119372d0934561059a8afcb00e764a2948aed637767L
q:  0xed0e2d9fd3925db7bf7b43bd6cb1670699102bd1e83ae62fa6349b8a3ed3aab2cb69d9433b46b4d545cfb31b0f0e545ea4f39d32a16539d630b26a6bcf86ab003e548c6998a72cf1c79f2de12e25f167666c4c9fbd17e027e859c0daa2b6e1a7d307d90d2ff6fee08a9aa791086c2cfa856abad3d34cb6de850e784f2beb4fd1L
d: 0x3510897188560bf44d150125c82d9ec2d06b912c915cec7ec0eeb6581b2c362377f0f9803a9e1f8493aff9d12e648431afbf76f803eaabda5a1a0cfcf0fba0d9e1645402e90d53dbc34f9f9979bd0c5c473221b700fda9b92145e00ca6f01f4f7dcdb787fa19f31203883fbdb83aaaea8e5e067679c6faccfc4db31194b663a1a2eef887d9f6f8a5edfa1da50d6fbf28059900968dd688c58358d4afc80eee62874fa2d54cb741d46266b79cd1b672f9b842f8f6478032b672cc59f1ca20668e09cbcfaacfa470d84551252cc51a9ce99c4195fa36a62b2156c068b9b099862fac20a45ab585ec9bd29be194d80284f40922dd6d565264bb850a97c53e9c6801L
aes_key:  f3994b69889dc1e03688ac4f484afc64
iv:  7af904127a682278e8162e6ece5e73ad
aaaaaflag{ok_this_is_a_flag_rsa}