西湖论剑2020中国杭州网络安全技能大赛部分题目WriteUp

def rational_to_contfrac (x, y):
    ''' 
    Converts a rational x/y fraction into
    a list of partial quotients [a0, ..., an] 
    '''
    a = x//y
    if a * y == x:
        return [a]
    else:
        pquotients = rational_to_contfrac(y, x - a * y)
        pquotients.insert(0, a)
        return pquotients
def convergents_from_contfrac(frac):    
    '''
    computes the list of convergents
    using the list of partial quotients 
    '''
    convs = [];
    for i in range(len(frac)):
        convs.append(contfrac_to_rational(frac[0:i]))
    return convs

def contfrac_to_rational (frac):
    '''Converts a finite continued fraction [a0, ..., an]
     to an x/y rational.
     '''
    if len(frac) == 0:
        return (0,1)
    elif len(frac) == 1:
        return (frac[0], 1)
    else:
        remainder = frac[1:len(frac)]
        (num, denom) = contfrac_to_rational(remainder)
        # fraction is now frac[0] + 1/(num/denom), which is 
        # frac[0] + denom/num.
        return (frac[0] * num + denom, num)

def egcd(a,b):
    '''
    Extended Euclidean Algorithm
    returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
    '''
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q = a // b
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, a - q * b
    return u, v, a

def gcd(a,b):
    '''
    2.8 times faster than egcd(a,b)[2]
    '''
    a,b=(b,a) if a<b else (a,b)
    while b:
        a,b=b,a%b
    return a

def modInverse(e,n):
    '''
    d such that de = 1 (mod n)
    e must be coprime to n
    this is assumed to be true
    '''
    return egcd(e,n)[0]%n

def totient(p,q):
    '''
    Calculates the totient of pq
    '''
    return (p-1)*(q-1)

def bitlength(x):
    '''
    Calculates the bitlength of x
    '''
    assert x >= 0
    n = 0
    while x > 0:
        n = n+1
        x = x>>1
    return n


def isqrt(n):
    '''
    Calculates the integer square root
    for arbitrary large nonnegative integers
    '''
    if n < 0:
        raise ValueError('square root not defined for negative numbers')

    if n == 0:
        return 0
    a, b = divmod(bitlength(n), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y


def is_perfect_square(n):
    '''
    If n is a perfect square it returns sqrt(n),

    otherwise returns -1
    '''
    h = n & 0xF; #last hexadecimal "digit"

    if h > 9:
        return -1 # return immediately in 6 cases out of 16.

    # Take advantage of Boolean short-circuit evaluation
    if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
        # take square root if you must
        t = isqrt(n)
        if t*t == n:
            return t
        else:
            return -1

    return -1

def hack_RSA(e,n):
    frac = rational_to_contfrac(e, n)
    convergents = convergents_from_contfrac(frac)

    for (k,d) in convergents:
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("\nHacked!")
                    return d

def main():
    n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
    d=hack_RSA(e,n)
    print ("d=")
    print (d)

if __name__ == '__main__':
    main()

import numpy as np
from PIL import Image
import math
import operator
import os
import time
import base64
import random

def load_horse():
    data = []
    p = Image.open('./horse.png').convert('L')
    p = np.array(p).reshape(-1)
    p = np.append(p,0)
    data.append(p)
    return np.array(data)

def load_deer():
    data = []
    p = Image.open('./deer.png').convert('L')
    p = np.array(p).reshape(-1)
    p = np.append(p,1)
    data.append(p)
    return np.array(data)

def load_test(pic):
    data = []
    p = Image.open(pic).convert('L')
    p = np.array(p).reshape(-1)
    p = np.append(p,1)
    data.append(p)
    return np.array(data)


def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)


def getNeighbors(trainingSet, testInstance, k):#k===1
    distances = []
    length = len(testInstance) - 1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    print('Eud: ', distances)
    neighbors = []
    for x in range(k):#(0,1)
        neighbors.append(distances[x][0])
        return neighbors


def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]


def getAccuracy(testSet, predictions):
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] == predictions[x]:
            correct += 1
    return (correct / float(len(testSet))) * 100.0

def check(pic):
    source_p = Image.open('deer.png')
    try:
        c_p = Image.open(pic)
    except:
        print("Please upload right picture.")
        exit()
    diff_pixel = 0
    a, b = source_p.size
    if c_p.size[0] != a and c_p.size[1] != b:
        print("Please upload right picture size("+str(a)+','+str(b)+')')
        exit()
    for y in range(b):
        for x in range(a):
            diff_pixel += abs(source_p.getpixel((x, y)) - c_p.getpixel((x, y)))
    print(diff_pixel)
    return diff_pixel

def main():
    while 1:
        print('-' * 134)
        print('''      ____       __            _          _   _                _                              _   _            _                         
     |  __ \     / _|          | |        | | | |              | |                            | | | |          | |                        
     | |__) |___| |_ ___ _ __  | |_ ___   | |_| |__   ___    __| | ___  ___ _ __    __ _ ___  | |_| |__   ___  | |__   ___  _ __ ___  ___ 
     |  _  // _ \  _/ _ \ '__| | __/ _ \  | __| '_ \ / _ \  / _` |/ _ \/ _ \ '__|  / _` / __| | __| '_ \ / _ \ | '_ \ / _ \| '__/ __|/ _ \\
     | | \ \  __/ ||  __/ |    | || (_) | | |_| | | |  __/ | (_| |  __/  __/ |    | (_| \__ \ | |_| | | |  __/ | | | | (_) | |  \__ \  __/
     |_|  \_\___|_| \___|_|     \__\___/   \__|_| |_|\___|  \__,_|\___|\___|_|     \__,_|___/  \__|_| |_|\___| |_| |_|\___/|_|  |___/\___|
    ''')
        print('-'*134)
        print('\t1.show source code')
        print('\t2.give me the source pictures')
        print('\t3.upload picture')
        print('\t4.exit')
        choose = input('>')
        print(choose)
        if choose == '1':
            w = open('run.py','r')
            print(w.read())
            continue
        elif choose == '2':
            print('this is horse`s picture:')
            h = base64.b64encode(open('horse.png','rb').read())
            print(h.decode())
            print('-'*134)
            print('this is deer`s picture:')
            d = base64.b64encode(open('deer.png', 'rb').read())
            print(d.decode())
            continue
        elif choose == '4':
            break
        elif choose == '3':
            print('Please input your deer picture`s base64(Preferably in png format)')
            pic = input('>')
            try:
                pic = base64.b64decode(pic)
            except:
                exit()
            if b"<?php" in pic or b'eval' in pic:
                print("Hacker!!This is not WEB,It`s Just a misc!!!")
                exit()
            salt = str(random.getrandbits(15))
            pic_name = 'tmp_'+salt+'.png'
            tmp_pic = open(pic_name,'wb')
            tmp_pic.write(pic)
            tmp_pic.close()
            #跟deer要相似
            if check(pic_name)>=100000:
                print('Don`t give me the horse source picture!!!')
                os.remove(pic_name)
                break
            ma = load_horse()
            print('ma:')
            print(ma)
            lu = load_deer()
            print('lu:')
            print(lu)
            k = 1
            trainingSet = np.append(ma, lu).reshape(2, 5185)
            print('train:', trainingSet)
            testSet = load_test(pic_name)
            print('test:', testSet, len(testSet[0]))
            neighbors = getNeighbors(trainingSet, testSet[0], k)
            print('neighbors:', neighbors)
            result = getResponse(neighbors)
            if repr(result) == '0':
                os.system('clear')
                print('Yes,I want this horse like deer,here is your flag encoded by base64')
                flag = base64.b64encode(open('flag','rb').read())
                print(flag.decode())
                os.remove(pic_name)
                break
            else:
                print('I want horse but not deer!!!')
                os.remove(pic_name)
                break
        else:
            print('wrong choose!!!')
            break
    exit()

if __name__=='__main__':
    main()

this is horse`s picture:
iVBORw0KGgoAAAANSUhEUgAAAEgAAABICAAAAABwhuybAAAFeElEQVR4nO2Xy28TVxTGvzN2ZpLYIY5dkgImIU4I2DFqQqiaqGpL2gXqv8AC2lUX/BFl032lSpWqblqpGyQ2LQhERQhUDSqk4ZnEtHnxCATn4TjP8fOeLmZszzPEUpeclefeM7/z3e/OfRh4G/9n+Dtk907v7jnKh42vc6690u5BTe/u1FsFyEPVgGoaqkAbw+pR5+m5689dq+5QxApSWjuO/DhbGoRgU6dcv7E7UH1472EUw2fuFDVS8e+UKblmX3JXoHBfiEKAOJjSClPOOpTOp2k3kCG19aN3IADA08habGyZk7nxRN2bFTWc8AuEWiWADtG8AIAF1ZLNrZ77SwynqIAa19cpHpMZgLddmcsTCpmwBACFZLGcFQ69TKoaivPragVKxl/9Z/YI/WlxRiVtoKC1qyoAtJzyAgAx66+LrWdPNu2KGL2n/el6vaFZntogzUBS8wCALXUPA2CQXl0KBPbdXtFfN5gdPxt68M210lNTNFj6mSxooJdWX5ibB3w20JEv9vLMqyeFUlJDtEX7pb4kSZIInFi3rTZuOWIdWuTLfUJiVNxjpUuZFwA8xwVAUzNYvTvgs03ZoYRqAsW+CgnAh3rDWL3t8tMCULMfAD0H8CxzbH+NQQ4A9jeYQF3fHR1LE/fXdHkMNaWD8kyGwAAKaQBIpkJBWRsf1YeCEgOSvmtqrW3fnxTp+2kiYov21alNAkDL1zLWQdW2xQMMcX1eKwoA9edPFjnQG2AWVg+CsSAA8LSNg8w/N1cq7ksA8P7nAuBAT4CJyDwz3HC0BcCLaRsHwModtZztBYC4XwDgpt6RJY/gBo+JVNslL6/N+f12Tl59PRczgXQsN937SRY43StM+d5ION9nx5DILSeWyqvQCwDjmz4GQBt/LQIYOqqYX5FqXTaPgz3p5flSEgDcveohgDyXRwFgctK2NbNzCA50HJYNoO2vL2xJ0uYv51UAyA5btyH3YBz4WPtEdXt8J7p5fGxbe1DO9QmXFx0i98NdA8gcvecUp2bnkB59m4XLSTsxUcUpye0H4AbKVeES2Bd2BWGyGklSozuoKknat+hSuSpJtAMod8NdkvPtxq1w4pFbD684XtuMZ78n3Fx+u7hWdKxMuZnNQFuNvcMI6vqk8h1yIzuBqHB58XgKDiTDAChSKyrheMJT4cpvOULqWX4nRZKX4Walzslf/bVAABw0WW9sBX222OFKTdlLV3Sj7SQLSEoOaQtfdMet0yalLo6UzmE7yaZoQ99BVItJxE8uJgCQv0ySjSm7u/kTide3bq0DQEenftmZHTvVZCC5ghjQ55S5sD1//552UwsNKAwAtPBHMnk2UCG5gho8QPbWGoGLanpxKau1Kv26iumRNYzCQLKCvB5NudzvFdL4BctqoN4IA6Dio9EMYCJZpka0HNNaYt0C6rB1VUXeAwBSR25rJ/joz6ul784AKqYBeD/o8QCQB+sgjScsnOCAAkBKDz0snYujQ6U+o6KHrwio6WsuCbppEaQMBBmgV9dmy84o7WScFz3SQwuE4sMlQD5ZB2li0syhnggDmP7d8D8i1i2gzllBSA0tiNGxAhCNOzjU3gOQeHBjzaBxsA7SZAKwzlrqRsu/RUAerBM2QcEBhUkdfVw0tEVjAupw1g7CygrgLEjpDzHSf84Zl4U8WCekSa2g0wfpKKgzwsgMvzC1RbvLghz3bEeH/B5QbtVaECVBTiD507KDO0c0LpC5mXUFxQyCDWG7XmqCJvQnu0dGBw2RXWPaNO1R0bhAplzQDup2FpSYZYhtW8GSIDtIcRaErBUdMwmyexSLOQqyhdkhh//9n/kEOQiyRfwYpKyhoA00PgU8frMg5C8JWp94c97bqMR/qKdMxhtIpukAAAAASUVORK5CYII=
--------------------------------------------------------------------------------------------------------------------------------------
this is deer`s picture:
iVBORw0KGgoAAAANSUhEUgAAAEgAAABICAAAAABwhuybAAAEXUlEQVR4nO2XS2xbRRSG/5l7b/xSb2wnDqbBSdU0FcQUmsRZVCAkorZJumkrFWEkWLJgyZINC5bsQQKEVAkhNRKJRKWqjUiFEAgUkYRQtYQ+ZCc4jzbk4dgkaWzfOSwSP+7D9r3Jtmc198ycz/+ZmTMzBp6Zc2N959wAXGdjDEDTxY6DggJfXT8FoOv7L/wArox/xG2FmUcpHsUNwKO4FYB3QNABQaCKyGi39pc9kKzT8p/Yb3pdfkhNSvTtpvu/2eLoQBfPfjkNAGh7+bTqlYIfs8aGha9XHYOkUyd7pgFAes/L8iIHldIzo4/scSpB2mPRpWYAwLtwK1EAINZW8jY5utQmzr8Uv5YB+MKnf9uNtwTdGbt8uWtW8tG4c44OVPiWBqJRiELSOUcHQvbqw4FjDR4qHBbU/mane0MJy+e2Z7VDgFj3W01ZhZFGL4bGx2wvVzG63IzF/TMjZwYYh0Dh1k2HpHKtxeIqJZcfaqRpRPLgkGI3cM9KqcXiKjHCfoWSPIiamviQd3KuspyL4FhcJcALLyuRampiJ4Y+OFMxL0VFvXGVAOpTTkg2NQktcGm5YsNxAGCxd/wAQIH+SElu3XkSgV6jotbXsptySNKfafXnCWGpvN1kANB+JzraLxnH1SVJFZMkA0BWcvlebTAfqSQPSjef1tJkAG0pA17F6mgm+XxoLCUseqxB9AveCO5lxhViABVjifd13vlzYctUepVZASiVCGsMKQAg2j8JCrDtmaelgYzl0umcEcQiR4jf/ax8TuzvI0qn9xrJxCsaoC3Pl9MjOdRiToUI5A8vlL6NJbP73bYQgrfplpCE2Qig1vejVUH46Z4EUIvfzrVIR989WRW0el0AcEdscADRfEmtBsKNJQ6g1WvrphYdxTIxgx7c5gCpYVuSwHtc1UDaaIYBUti4UayNwoFqIExMcQCyTZBbrQrKjhYA8cRWYQCSUhWEHxKySM7ZU1SqDdmiK/XNlfUnebsgVAfRyPNHWJljyJFZ/4IVCKnp/nK0K6iP3NmwDxK3OyNFkgi+rp/H3amUVYz123dlZL3UwbjevLE2+yDcu5ood+lTI48lyTI1ALPLvd3HJQBM7EqGsuOntUVTQI1FDn8YIIAt/2xYNmrpyUvB4pf2+d2aigAUCADY6o/GA7vVxRtEs8Fp74+G3hjn+X/WioDQwUEAWG5+bW9W+IXYYUBguflFAgBqjEftgaosB9u6NskAgPzHgZqTvR9Q5VnKVh4tsT4C9t9m9RSxjV+tSSKhZYcny3LrKGLp4T+sO9YXgcwwSk+kOorYxJTZ6eMAJXcAbN7IFDXVS23H7JLaGNjW3p2+W8r7AMvf/BwBqU2D9wCgdheQSxrvT+cgXwRgj1eMbuegVpUgEqY94RgkHeNg60smv2NQcwuB5syL6RjU7gLbmjP7nYJ8EQCpjLmjVokwTtxY+y80guUTpBtTD7Q95iF23+icBnb+1Y95UEPMM6uw/wEb7IPCRqC/gwAAAABJRU5ErkJggg==
--------------------------------------------------------------------------------------------------------------------------------------

from PIL import Image
import numpy as np
from PIL import Image
import math
import os
import time
import base64
import random


def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)


def check(p1, p2):
    diff_pixel=0
    for x in range(len(p1)):
        diff_pixel += abs(p1[x] - p2[x])
    #print(diff_pixel)
    return diff_pixel
    


p1 = Image.open('./horse.png').convert('L')
p1 = np.array(p1).reshape(-1)
print('horse', p1)

p2 = Image.open('./deer.png').convert('L')
p2 = np.array(p2).reshape(-1)
print('deer', p2)

test = np.array(p2).reshape(-1)

for i in range(3000):
    test[i] = p1[i]

eud1 = euclideanDistance(p1, test, 5184)
print('Eu1: ', eud1)

eud2 = euclideanDistance(p2, test, 5184)
print('Eu2: ', eud2)

dif = check(test, p2)
print('Diff:', dif)

if(eud1 < eud2):
    print('Eud Good')
if dif < 100000:
    print('Diff Good')

img = test.reshape(72, 72)
#Image.save(img, 'test.png')
img = np.uint8(img)
im = Image.fromarray(img)
im.save("out.png", 'png')


 
with open("out.png", 'rb') as f:
    base64_data = base64.b64encode(f.read())
    s = base64_data.decode()
    print(s)