SCTF-crypto-wp

发布于 2021-12-28  544 次阅读






SCTFwp

SCTF crypto wp

这次比赛被X1c的大哥们带飞了,考完试一定认真学习提升水平

ciruit map

2021DiceCTF Garbled魔改,谷歌一下可以得到下面的脚本,得到四组key。

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

unsigned int SBoxes[6][16] = {{15, 1, 7, 0, 9, 6, 2, 14, 11, 8, 5, 3, 12, 13, 4, 10}, {3, 7, 8, 9, 11, 0, 15, 13, 4, 1, 10, 2, 14, 6, 12, 5}, {4, 12, 9, 8, 5, 13, 11, 7, 6, 3, 10, 14, 15, 1, 2, 0}, {2, 4, 10, 5, 7, 13, 1, 15, 0, 11, 3, 12, 14, 9, 8, 6}, {3, 8, 0, 2, 13, 14, 5, 11, 9, 1, 7, 12, 4, 6, 10, 15}, {14, 12, 7, 0, 11, 4, 13, 15, 10, 3, 8, 9, 2, 6, 1, 5}};
unsigned int SInvBoxes[6][16] = {{3, 1, 6, 11, 14, 10, 5, 2, 9, 4, 15, 8, 12, 13, 7, 0}, {5, 9, 11, 0, 8, 15, 13, 1, 2, 3, 10, 4, 14, 7, 12, 6}, {15, 13, 14, 9, 0, 4, 8, 7, 3, 2, 10, 6, 1, 5, 11, 12}, {8, 6, 0, 10, 1, 3, 15, 4, 14, 13, 2, 9, 11, 5, 12, 7}, {2, 9, 3, 0, 12, 6, 13, 10, 1, 8, 14, 7, 11, 4, 5, 15}, {3, 14, 12, 9, 5, 15, 13, 2, 10, 11, 8, 4, 1, 6, 0, 7}};
unsigned int PBox[] = {15, 22, 11, 20, 16, 8, 2, 3, 14, 19, 18, 1, 12, 4, 9, 13, 23, 21, 10, 17, 0, 5, 6, 7};
unsigned int PInvBox[] = {20, 11, 6, 7, 13, 21, 22, 23, 5, 14, 18, 2, 12, 15, 8, 0, 4, 19, 10, 9, 3, 17, 1, 16};

unordered_map<unsigned int, unsigned int>  middle_data;

unsigned int S(unsigned int block, unsigned int SBoxes[6][16]){
    unsigned int output = 0;
    for(int i = 0; i < 6; i++){
        output |= SBoxes[i][(block >> 4 * i) & 0b1111] << 4 * i;
    }
    return output;
}
    
unsigned int permute(unsigned int block, unsigned int pbox[]){
    unsigned int output = 0;
    unsigned int bit = 0;
    for(int i = 0; i < 24; i++){
        bit = (block >> pbox[i]) & 1;
        output |= (bit << i);
    }
    return output;
}

unsigned int encrypt_data(unsigned int block, unsigned int key){
    unsigned int res = block;
    for(int i = 0; i < 3; i++){
        res ^= key;
        res = S(res, SBoxes);
        res = permute(res,PBox);
    }
    res ^= key;
    return res;
}

unsigned int decrypt_data(unsigned int block, unsigned int key){
    unsigned int res = block;
    res ^= key;
    for(int i = 0; i < 3; i++){
        res = permute(res, PInvBox);
        res = S(res, SInvBoxes);
        res ^= key;
    }
    return res;
}

unsigned int encrypt(unsigned int block, unsigned int key1, unsigned int key2){
    unsigned int res = block;
    res = encrypt_data(res, key1);
    res = encrypt_data(res, key2);
    return res;
}

unsigned int decrypt(unsigned int block, unsigned int key1, unsigned int key2){
    unsigned int res = block;
    res = decrypt_data(res, key2);
    res = decrypt_data(res, key1);
    return res;
}

void init_middle_data(){
    cout << "Init middle data" << endl;
    unsigned int enc = 0;
    for(unsigned int i = 0; i < 0x1000000; i++){
        enc = encrypt_data(0,i);
        if(middle_data.find(enc) == middle_data.end()){
            middle_data.insert(pair<unsigned int, unsigned int>(enc,i));
        }
        else{
            unsigned int count = 0;
            unsigned int tmp = 0;
            do{
                count++;
                tmp = count << 24 | enc;
            }while(middle_data.find(tmp) != middle_data.end());
            middle_data.insert(pair<unsigned int, unsigned int>(tmp,i));
        }
    }
}

unordered_map<unsigned int, unsigned int> find_possible_key(unsigned int t){
    cout << "Find possible keys for " << t << endl;
    unordered_map<unsigned int, unsigned int> result;
    unsigned int dec = 0;
    for(unsigned int i = 0; i < 0x1000000; i++){
        unsigned int dec_count = 0;
        dec = decrypt_data(t,i);
        unsigned int dec_tmp = dec;
        while(middle_data.find(dec) != middle_data.end()){
            unsigned int key = i;
            if(result.find(key) == result.end()){
                result.insert(pair<unsigned int, unsigned int>(key,middle_data[dec]));
            }
            else{
                unsigned int count = 0;
                unsigned int tmp;
                do{
                    count++;
                    tmp = count << 24 | key;
                }while(result.find(tmp) != result.end());
                result.insert(pair<unsigned int, unsigned int>(tmp,middle_data[dec]));
            }
            dec_count++;
            dec = dec_count << 24 | dec_tmp;
        }
    }
    return result;
}

unsigned int recover_key_part2(vector< unordered_map<unsigned int, unsigned int> > possible_keys,vector<unsigned int>enc_labels,unsigned int a0,unsigned int b0,int idxi,int idxj){
    unordered_map<unsigned int, unsigned int> choice_keys;
    unsigned int c, c1, b1, a00;
    for(int i = 0; i < 4; i++){
        if(i == idxi || i == idxj) continue;
        choice_keys = possible_keys[i];
        c = enc_labels[i];
        c1 = enc_labels[idxi];
        for(auto iter = choice_keys.begin(); iter != choice_keys.end(); ++iter){
            b1 = iter->first;
            if(b1 > 0x1000000) continue;
            unsigned int dec_b1 = b1;
            unsigned int count = 0;
            while(choice_keys.find(b1) != choice_keys.end()){
                a00 = choice_keys[b1];
                if(a0 == a00 && decrypt(c,a0,dec_b1) == decrypt(c1,a0,b0)){
                    return dec_b1;
                }
                count++;
                b1 = count << 24 | dec_b1;
            }
        }
    }
    return 0;
}

bool recover_key(vector< unordered_map<unsigned int, unsigned int> > possible_keys,vector<unsigned int>enc_labels){
    unordered_map<unsigned int, unsigned int>  choice_keys, choice_keys2;
    unsigned int c1, b0, a0, p1, c2, a1, b1;
    for(int i = 0; i < 4; i++){
        cout << "Recover key " << i << endl;
        choice_keys = possible_keys[i];
        c1 = enc_labels[i];
        for(int j = 0; j < 4; j++){
            if(i == j) continue;
            choice_keys2 = possible_keys[j];
            c2 = enc_labels[j];
            for(auto iter = choice_keys.begin(); iter != choice_keys.end(); ++iter){
                b0 = iter->first;
                if(b0 >= 0x1000000) continue;
                unsigned int count = 0;
                unsigned int dec_b0 = b0;
                while(choice_keys.find(b0) != choice_keys.end()){
                    a0 = choice_keys[b0];
                    p1 = decrypt(c1, a0, dec_b0);
                    unsigned int b0_tmp = dec_b0;
                    unsigned int count_tmp = 0;
                    while(choice_keys2.find(b0_tmp) != choice_keys2.end()){
                        a1 = choice_keys2[b0_tmp];
                        if(p1 == decrypt(c2,a1,dec_b0)){
                            b1 = recover_key_part2(possible_keys,enc_labels,a0,dec_b0,i,j);
                            if(b1 != 0){
                                cout << "Find keys : " << a1 << ", " << a0 << endl;
								cout << "Find keys : " << b1 << ", " << b0 << endl;
                                return true;
                            }
                        }
                        count_tmp++;
                        b0_tmp = count_tmp << 24 | dec_b0;
                    }
                    count++;
                    b0 = count << 24 | dec_b0;
                }
            }
        }
    }
    return false;
}


unsigned int g_tables[2][4][2] = {{{13303835L, 2123830L},{2801785L, 11303723L},{13499998L, 248615L},{13892520L, 7462011L}},{{3244202L, 918053L},{3277177L, 6281266L},{1016382L, 7097624L},{10016472L, 13600867L}}};

int main(){
    init_middle_data();
    for(int i = 0; i < 2; i++){
        vector< unordered_map<unsigned int, unsigned int> > possible_keys(4);
        vector<unsigned int>enc_labels(4);
        for(int j = 0; j < 4; j++){
            possible_keys[j] = find_possible_key(g_tables[i][j][1]);
            enc_labels[j] = g_tables[i][j][0];
        }
        recover_key(possible_keys,enc_labels);
    }

}

有了4组key之后需要利用这四组key,求出剩下的4组key。这个过程利用了g_table中第二个元素使用

validation = encrypt(0, key0, key1)

根据public_data中keys的使用顺序,我们只需要逐个decrypt,和0这个已知量比较,就可以恢复所有的key

import hashlib
from Crypto.Util.number import long_to_bytes
from block_cipher import decrypt


def xor(A, B):
    return bytes(a ^ b for a, b in zip(A, B))


def re_and(g_table, labels0, labels1):
    key = [0, 0]

    for g in g_table:
        if decrypt(g[1], labels0[0], labels1[0]) == 0:
            key[0] = decrypt(g[0], labels0[0], labels1[0])

        if decrypt(g[1], labels0[0], labels1[1]) == 0:
            key[1] = decrypt(g[0], labels0[0], labels1[1])

        if decrypt(g[1], labels0[1], labels1[0]) == 0:
            key[1] = decrypt(g[0], labels0[1], labels1[0])

        if decrypt(g[1], labels0[1], labels1[1]) == 0:
            key[1] = decrypt(g[0], labels0[1], labels1[1])

    return key


def re_xor(g_table, labels0, labels1):
    key = [0, 0]

    for g in g_table:
        if decrypt(g[1], labels0[0], labels1[0]) == 0:
            key[1] = decrypt(g[0], labels0[0], labels1[0])

        if decrypt(g[1], labels0[0], labels1[1]) == 0:
            key[0] = decrypt(g[0], labels0[0], labels1[1])

        if decrypt(g[1], labels0[1], labels1[0]) == 0:
            key[0] = decrypt(g[0], labels0[1], labels1[0])

        if decrypt(g[1], labels0[1], labels1[1]) == 0:
            key[1] = decrypt(g[0], labels0[1], labels1[1])

    return key


keys = [
    [13675268, 8343801],
    [12870274, 10251687],
    [12490757, 6827786],
    [3391233, 2096572],
    [],
    [],
    [],
    []
]

G_Table = {5: [(13303835, 2123830),
               (2801785, 11303723),
               (13499998, 248615),
               (13892520, 7462011)],
           6: [(3244202, 918053),
               (3277177, 6281266),
               (1016382, 7097624),
               (10016472, 13600867)],
           7: [(5944875, 3442862),
               (7358369, 8423543),
               (6495696, 9927178),
               (13271900, 11855272)],
           9: [(5333988, 87113),
               (9375869, 11687470),
               (5011062, 14981756),
               (2509493, 12330305)]}

keys[4] = re_and(G_Table[5], keys[0], keys[1])
keys[5] = re_and(G_Table[6], keys[2], keys[3])
keys[6] = re_and(G_Table[7], keys[4], keys[5])
keys[7] = re_xor(G_Table[9], keys[6], keys[3])
the_chaos = b''
for i in keys:
    tmp = sum(i)
    the_chaos += bytes(long_to_bytes(tmp))
mask = hashlib.md5(the_chaos).digest()
c = long_to_bytes(0x1661fe85c7b01b3db1d432ad3c5ac83a)
print(xor(mask, c))

cubic

这题比赛的时候因为一些玄学问题没出,第二天起床重新拿数据就解出来了,就离谱。

题目定义了一个很奇怪的点加法,和上次西湖论剑类似,都是需要得到阶的表达式,这题不太容易通过证明或猜想的方式得到,就自己用较小的数枚举了一下p和phi,然后用excel作图,就可以得到阶的表达式。

import random
from Crypto.Util.number import *

def add(P, Q, mod):
    x1, y1 = P
    x2, y2 = Q

    if x2 is None:
        return P
    if x1 is None:
        return Q

    if y1 is None and y2 is None:
        x = x1 * x2 % mod
        y = (x1 + x2) % mod
        return (x, y)

    if y1 is None and y2 is not None:
        x1, y1, x2, y2 = x2, y2, x1, y1

    if y2 is None:
        if (y1 + x2) % mod != 0:
            x = (x1 * x2 + 2) * inverse(y1 + x2, mod) % mod
            y = (x1 + y1 * x2) * inverse(y1 + x2, mod) % mod
            return (x, y)
        elif (x1 - y1 ** 2) % mod != 0:
            x = (x1 * x2 + 2) * inverse(x1 - y1 ** 2, mod) % mod
            return (x, None)
        else:
            return (None, None)
    else:
        if (x1 + x2 + y1 * y2) % mod != 0:
            x = (x1 * x2 + (y1 + y2) * 2) * inverse(x1 + x2 + y1 * y2, mod) % mod
            y = (y1 * x2 + x1 * y2 + 2) * inverse(x1 + x2 + y1 * y2, mod) % mod
            return (x, y)
        elif (y1 * x2 + x1 * y2 + 2) % mod != 0:
            x = (x1 * x2 + (y1 + y2) * 2) * inverse(y1 * x2 + x1 * y2 + 2, mod) % mod
            return (x, None)
        else:
            return (None, None)


def myPower(P, a, mod):
    target = (None, None)
    t = P
    while a > 0:
        if a % 2:
            target = add(target, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return target


def genPrime():
    while True:
        a = random.getrandbits(5)
        b = random.getrandbits(5)

        if b % 3 == 0:
            continue

        p = a ** 2 + 3 * b ** 2
        if p.bit_length() == 10 and p % 3 == 1 and isPrime(p):
            return p

p = genPrime()
# q = genPrime()
print(p)
P = (20, 7)
e = 4
c = myPower(P, e, p)
print(c)
l = []
for i in range(10000000):
    if myPower(c, i, p) == P:
        l.append(i)
    if len(l) == 2:
        break
print(l)
print(GCD(e*l[0]-1,e*l[1]-1))
print(inverse(e,p**2+p+1))

测试脚本如上,拟合图如下

于是就得到phi的表达式为

回到题目,题目给了n和pad,其中n由于e和d的比特差距过大,所以用维纳攻击,就可以得到n的分解,然后就可以正常解了。

from __future__ import print_function
import libnum


def continued_fractions_expansion(numerator, denominator):  # (e,N)
    result = []
    divident = numerator % denominator
    quotient = numerator // denominator
    result.append(quotient)
    while divident != 0:
        numerator = numerator - quotient * denominator
        tmp = denominator
        denominator = numerator
        numerator = tmp
        divident = numerator % denominator
        quotient = numerator // denominator
        result.append(quotient)
    return result


def convergents(expansion):
    convergents = [(expansion[0], 1)]
    for i in range(1, len(expansion)):
        numerator = 1
        denominator = expansion[i]
        for j in range(i - 1, -1, -1):
            numerator += expansion[j] * denominator
            if j == 0:
                break
            tmp = denominator
            denominator = numerator
            numerator = tmp
        convergents.append((numerator, denominator))  # (k,d)
    return convergents


def newtonSqrt(n):
    approx = n // 2
    better = (approx + n // approx) // 2
    while better != approx:
        approx = better
        better = (approx + n // approx) // 2
    return approx


def wiener_attack(cons, e, N):
    for cs in cons:
        k, d = cs
        if k == 0:
            continue
        phi_N = (e * d - 1) // k
        # x**2 - ((N - phi_N) + 1) * x + N = 0
        a = 1
        b = -((N - phi_N) + 1)
        c = N
        delta = b * b - 4 * a * c
        if delta <= 0:
            continue
        x1 = (newtonSqrt(delta) - b) // (2 * a)
        x2 = -(newtonSqrt(delta) + b) // (2 * a)
        if x1 * x2 == N:
            return [x1, x2, k, d]


if __name__ == "__main__":
    e=819382037399064442327978233656373948301292440392316505787667920472342355866515320546353963575191866559117867875436149437491650016798518960266827689696998476411177553972337903956522093695435483057967766651334328727772117869946740753334389831295569836728543386027836227765809805814005059350679560883065398638057899008268552924567444832930473556770766411086076067484715488954807701070180806264914625227962425895071440659710142687256796009136554764117636432836684905199819830002591589801112752367150058111798497915007007568169222343993343559273651773897397584298269477365416052915189832380459899365614864354424463935173
    n=29830376216290305772143399822451411181159931342323089750256832184463773450846659179800098516100313293194466198824774533048611833718986346020299668517967176123766918840668341963002295583905137788439078345993390231810559348913549984052484710848427791949792383413567985645852875861414337362756908044975051907974837287861105996683061895986430680678672447178762109444722504511411944468814554615604421791817956323131662839822319577152787120723629290655590836345972614300010987773127432610179392081053665393593352506900936273416034928676482659144707573092389584041876538290807149995336848272169641338831453246655318294608251
    expansion = continued_fractions_expansion(e, n)
    cons = convergents(expansion)
    p, q, k, d = wiener_attack(cons, e, n)
    print(p)
    print(q)
    print(d)

from Crypto.Util.number import *


def add(P, Q, mod):
    x1, y1 = P
    x2, y2 = Q

    if x2 is None:
        return P
    if x1 is None:
        return Q

    if y1 is None and y2 is None:
        x = x1 * x2 % mod
        y = (x1 + x2) % mod
        return (x, y)

    if y1 is None and y2 is not None:
        x1, y1, x2, y2 = x2, y2, x1, y1

    if y2 is None:
        if (y1 + x2) % mod != 0:
            x = (x1 * x2 + 2) * inverse(y1 + x2, mod) % mod
            y = (x1 + y1 * x2) * inverse(y1 + x2, mod) % mod
            return (x, y)
        elif (x1 - y1 ** 2) % mod != 0:
            x = (x1 * x2 + 2) * inverse(x1 - y1 ** 2, mod) % mod
            return (x, None)
        else:
            return (None, None)
    else:
        if (x1 + x2 + y1 * y2) % mod != 0:
            x = (x1 * x2 + (y1 + y2) * 2) * inverse(x1 + x2 + y1 * y2, mod) % mod
            y = (y1 * x2 + x1 * y2 + 2) * inverse(x1 + x2 + y1 * y2, mod) % mod
            return (x, y)
        elif (y1 * x2 + x1 * y2 + 2) % mod != 0:
            x = (x1 * x2 + (y1 + y2) * 2) * inverse(y1 * x2 + x1 * y2 + 2, mod) % mod
            return (x, None)
        else:
            return (None, None)


def myPower(P, a, mod):
    target = (None, None)
    t = P
    while a > 0:
        if a % 2:
            target = add(target, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return target


p=177877314328202368047334433208932033082600812649455949174038023395254369214323559898012518633872210053488564169305797936734897374420295588977052096336571953361952547738526477533616932175985492321305173971478988281661712528617986323848567403481646347123926542294702076846041687699873778013896918100087598394667
q=167701971040838416023837245658094784818637629718420795029562055677443763023445703228249476611537720563436294287586910872661304031017558062974075630573158702693854348321595560164080298650150394261868370613523194095042941320399161726749026836702679463083007703490166530540436137651742778694524586638372062272753
e = 819382037399064442327978233656373948301292440392316505787667920472342355866515320546353963575191866559117867875436149437491650016798518960266827689696998476411177553972337903956522093695435483057967766651334328727772117869946740753334389831295569836728543386027836227765809805814005059350679560883065398638057899008268552924567444832930473556770766411086076067484715488954807701070180806264914625227962425895071440659710142687256796009136554764117636432836684905199819830002591589801112752367150058111798497915007007568169222343993343559273651773897397584298269477365416052915189832380459899365614864354424463935173
n = 29830376216290305772143399822451411181159931342323089750256832184463773450846659179800098516100313293194466198824774533048611833718986346020299668517967176123766918840668341963002295583905137788439078345993390231810559348913549984052484710848427791949792383413567985645852875861414337362756908044975051907974837287861105996683061895986430680678672447178762109444722504511411944468814554615604421791817956323131662839822319577152787120723629290655590836345972614300010987773127432610179392081053665393593352506900936273416034928676482659144707573092389584041876538290807149995336848272169641338831453246655318294608251

cipher=(2570683862795585322045899302316339948651008507983538897428594019004630732004228428229982113440686747216601296768794200611368050119263077128264283368117412693082007043717436894109091274009254816500719762418472869412736769145534764652909971597753554645255920984093938983352487314929351829423776878281865238233152735861097766639158518697800126259299700114985313410394935932124246946773860512526043711876623637689401386373390402048781693139643493692108829894226137805081046157476275575559338295042254148309426680835257095185970199498682769558441274116208901987105271895508103655186703323189927773352684823837638306052254998032594559523700473466019938946204606418876140027443404283520095474837996105724823876876184385517944833921281075238934321420791748336379792426973480701720019962877110158693469510875190947347426364160465560247327327627070522568186231648125780311614436961671787443022918337864453468560991914401823866709325050, 2795930849701372741373366116017698387458701348648379443584838301255041912648743814606873505005280860882713412892360318700348419631743613508264798348109961492771786543649722575856890188340154983197817870180695955563222476088343126809999505801584958898829114548081286777736974578049247916537358640655972318902941105905770915006605747904164571310672512982873962587187026282451672336723448867513212746338667320142837039996539755909644421647675343232214161793600377232771095065145278018715078742220385716015073314308240643379080709091531424212532559556686745684169896161737543254713251636968498038384905471657006725308442607983308666458421235787797059052523915784107412256760877602002239690194105596120293925131390037653668274026879339366760625466702130264840394683277801241021410039466281135646846483908595727925316063031233236417110283327857164457410895664311081980330277811357142346516413217835118599879780695122202976956400086)
padding=110440859357531161449318496236102245640494989086835166501415627645164673379790287188126608450009259967723565995910419811345977510540090384530950841382570169005652560944473648969061795754749839510413475127727022422683307512396166841523596254281025387762724447628989754856990692021655320071968894679711115123151
d = inverse(e, (p*p+p+1)*(q*q+q+1)*(padding*padding+padding+1))
assert n == p * q
flag1, flag2 = myPower(cipher, d, n*padding)
print(long_to_bytes(flag1)+long_to_bytes(flag2))

ChristmasZone

没时间看了,等期末预习完再复现