Crypto

Ancient Recall

题目：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import random

Major_Arcana = [
    "The Fool",
    "The Magician",
    "The High Priestess",
    "The Empress",
    "The Emperor",
    "The Hierophant",
    "The Lovers",
    "The Chariot",
    "Strength",
    "The Hermit",
    "Wheel of Fortune",
    "Justice",
    "The Hanged Man",
    "Death",
    "Temperance",
    "The Devil",
    "The Tower",
    "The Star",
    "The Moon",
    "The Sun",
    "Judgement",
    "The World",
]
wands = [
    "Ace of Wands",
    "Two of Wands",
    "Three of Wands",
    "Four of Wands",
    "Five of Wands",
    "Six of Wands",
    "Seven of Wands",
    "Eight of Wands",
    "Nine of Wands",
    "Ten of Wands",
    "Page of Wands",
    "Knight of Wands",
    "Queen of Wands",
    "King of Wands",
]
cups = [
    "Ace of Cups",
    "Two of Cups",
    "Three of Cups",
    "Four of Cups",
    "Five of Cups",
    "Six of Cups",
    "Seven of Cups",
    "Eight of Cups",
    "Nine of Cups",
    "Ten of Cups",
    "Page of Cups",
    "Knight of Cups",
    "Queen of Cups",
    "King of Cups",
]
swords = [
    "Ace of Swords",
    "Two of Swords",
    "Three of Swords",
    "Four of Swords",
    "Five of Swords",
    "Six of Swords",
    "Seven of Swords",
    "Eight of Swords",
    "Nine of Swords",
    "Ten of Swords",
    "Page of Swords",
    "Knight of Swords",
    "Queen of Swords",
    "King of Swords",
]
pentacles = [
    "Ace of Pentacles",
    "Two of Pentacles",
    "Three of Pentacles",
    "Four of Pentacles",
    "Five of Pentacles",
    "Six of Pentacles",
    "Seven of Pentacles",
    "Eight of Pentacles",
    "Nine of Pentacles",
    "Ten of Pentacles",
    "Page of Pentacles",
    "Knight of Pentacles",
    "Queen of Pentacles",
    "King of Pentacles",
]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
reversals = [0, -1]

Value = []
cards = []
YOUR_initial_FATE = []
while len(YOUR_initial_FATE) < 5:
    card = random.choice(tarot)
    if card not in cards:
        cards.append(card)
        if card in Major_Arcana:
            k = random.choice(reversals)
            Value.append(tarot.index(card) ^ k)
            if k == -1:
                YOUR_initial_FATE.append("re-" + card)
            else:
                YOUR_initial_FATE.append(card)
        else:
            Value.append(tarot.index(card))
            YOUR_initial_FATE.append(card)
    else:
        continue
print("Oops!lets reverse 1T!")

FLAG = ("hgame{" + "&".join(YOUR_initial_FATE) + "}").replace(" ", "_")
print(FLAG)
YOUR_final_Value = Value


def Fortune_wheel(FATE):
    FATEd = [FATE[i] + FATE[(i + 1) % 5] for i in range(len(FATE))]
    return FATEd


for i in range(250):
    YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)
YOUR_final_FATE = []
for i in YOUR_final_Value:
    YOUR_final_FATE.append(tarot[i % 78])
print("Your destiny changed!\n", ",".join(YOUR_final_FATE))
print("oh,now you GET th3 GOOd lU>k,^^")
"""
Oops!lets reverse 1T!
[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
Your destiny changed!
 Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords
oh,now you GET th3 GOOd lU>k,^^
"""

一个模拟塔罗牌占卜的程序，VALUE经过了250次Fortune_wheel得到final_Value，把Fortune_wheel逆向就好了。

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
def Reverse_wheel(FATE):
    FATEd = [
        (FATE[0] - FATE[1] + FATE[2] - FATE[3] + FATE[4]) // 2,
        (FATE[0] + FATE[1] - FATE[2] + FATE[3] - FATE[4]) // 2,
        (-FATE[0] + FATE[1] + FATE[2] - FATE[3] + FATE[4]) // 2,
        (FATE[0] - FATE[1] + FATE[2] + FATE[3] - FATE[4]) // 2,
        (-FATE[0] + FATE[1] - FATE[2] + FATE[3] + FATE[4]) // 2,
    ]
    return FATEd


final_Value = [
    2532951952066291774890498369114195917240794704918210520571067085311474675019,
    2532951952066291774890327666074100357898023013105443178881294700381509795270,
    2532951952066291774890554459287276604903130315859258544173068376967072335730,
    2532951952066291774890865328241532885391510162611534514014409174284299139015,
    2532951952066291774890830662608134156017946376309989934175833913921142609334,
]

Value = final_Value
for i in range(250):
    Value = Reverse_wheel(Value)

initial_FATE = []
for i in Value:
    if i < 0:
        initial_FATE.append("re-" + tarot[(i ^ -1) % 78])
    else:
        initial_FATE.append(tarot[i % 78])

FLAG = ("hgame{" + "&".join(initial_FATE) + "}").replace(" ", "_")
print(FLAG)
# hgame{re-The_Moon&re-The_Sun&Judgement&re-Temperance&Six_of_Cups}

Intergalactic Bound

题目：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
import hashlib


def add_THCurve(P, Q):
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 - y1**2 * x2 * y2) * pow(a * x1 * y1 * x2**2 - y2, -1, p) % p
    y3 = (y1 * y2**2 - a * x1**2 * x2) * pow(a * x1 * y1 * x2**2 - y2, -1, p) % p
    return x3, y3


def mul_THCurve(n, P):
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_THCurve(R, P)
        P = add_THCurve(P, P)
        n = n // 2
    return R


flag = b"hgame{SPiCa_is_a_good_name_for_a_crypto_algorithm}"
p = getPrime(96)
a = randint(1, p)
G = (randint(1, p), randint(1, p))
d = (a * G[0] ** 3 + G[1] ** 3 + 1) % p * inverse(G[0] * G[1], p) % p
x = randint(1, p)
Q = mul_THCurve(x, G)
print(f"p = {p}")
print(f"G = {G}")
print(f"Q = {Q}")

key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag, 16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")
print(f"x = {x}, a = {a}, d = {d}")

"""
p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
"""

首先这是Twisted Hessian curves

1
a*x^3+y^3+1=dxy

方程代入P，Q两点联立消去d可以计算出a，再计算出d，这样参数就齐了。

然后用Pohlig_Hellman方法计算x即可

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
x1, y1 = G
x2, y2 = Q

a = (
    (y1 * y2 * (y2**2 * x1 - y1**2 * x2) + (x1 * y1 - x2 * y2))
    * inverse(x1 * x2 * (x1**2 * y2 - y1 * x2**2), p)
    % p
)
d = (a * G[0] ** 3 + G[1] ** 3 + 1) % p * inverse(G[0] * G[1], p) % p

ciphertext = b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"

R.<x,y,z> = Zmod(p)[]
cubic = a * x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
G = E(G)
Q = E(Q)
E_ord = G.order()

def Pohlig_Hellman(n,P,Q):
    factors, exponents = zip(*factor(n))
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
    print(primes)
    dlogs = []
    for fac in primes:
        t = int(int(P.order()) // int(fac))
        dlog = discrete_log(t*Q,t*P,operation="+")
        dlogs += [dlog]
        print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
    num2 = crt(dlogs,primes)
    return num2

x = Pohlig_Hellman(E_ord,G,Q)
print(f"x={x}")
# x=2633177798829352921583206736

key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
print(f"flag={flag}")
# flag=b'hgame{N0th1ng_bu7_up_Up_UP!}\x04\x04\x04\x04'

Reverse

SignUp

如图，程序将flag去掉hgame{后复制到Destination后用sub_140014D3检查

img

用sub_1400016EF加密后与byte_1400BB880比较，相关参数有unk_1409BB2A0 unk_1499BB889。

img

加密函数如图，已逆向（验证过了）

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
void encrypt(_DWORD *a1, __int64 a2, __int64 a3)
{
    unsigned int v4, v5, v6, v8;
    int v9, i;

    v6 = 0;
    for (v8 = 11; v8 > 0; v8--)
    {
        v6 += *(_DWORD *)(a3 + 4LL * (v8 % 4));
        v9 = (v6 >> 2) & 3;
        for (i = 0; i < 9; ++i)
        {
            v4 = a1[(i + 1) % 9];
            v5 = a1[(i + 8) % 9];
            a1[i] += ((v5 ^ *(_DWORD *)(a2 + 4LL * (v9 ^ i & 3))) + (v4 ^ v6)) ^ (((16 * v5) ^ (v4 >> 3)) + ((4 * v4) ^ (v5 >> 5)));
        }
    }
}

void decrypt(_DWORD *a1, __int64 a2, __int64 a3)
{
    unsigned int v4, v5, v6, v8;
    int v9, i;

    v6 = 0;
    for (v8 = 1; v8 < 12; v8++)
    {
        v6 -= *(_DWORD *)(a3 + 4LL * (v8 % 4));
        v9 = (v6 >> 2) & 3;
        for (i = 8; i >= 0; --i)
        {
            v4 = a1[(i + 1) % 9];
            v5 = a1[(i + 8) % 9];
            a1[i] -= ((v5 ^ *(_DWORD *)(a2 + 4LL * (v9 ^ i & 3))) + (v4 ^ v6)) ^ (((16 * v5) ^ (v4 >> 3)) + ((4 * v4) ^ (v5 >> 5)));
        }
    }
}

动态调试就能得到两个参数的值。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define _BYTE unsigned char
#define _DWORD unsigned int

void encrypt(_DWORD *a1, __int64 a2, __int64 a3)
{
    unsigned int v4, v5, v6, v8;
    int v9, i;

    v6 = 0;
    for (v8 = 11; v8 > 0; v8--)
    {
        v6 += *(_DWORD *)(a3 + 4LL * (v8 % 4));
        v9 = (v6 >> 2) & 3;
        for (i = 0; i < 9; ++i)
        {
            v4 = a1[(i + 1) % 9];
            v5 = a1[(i + 8) % 9];
            a1[i] += ((v5 ^ *(_DWORD *)(a2 + 4LL * (v9 ^ i & 3))) + (v4 ^ v6)) ^ (((16 * v5) ^ (v4 >> 3)) + ((4 * v4) ^ (v5 >> 5)));
        }
    }
}

void decrypt(_DWORD *a1, __int64 a2, __int64 a3)
{
    unsigned int v4, v5, v6, v8;
    int v9, i;

    v6 = 0;
    for (v8 = 1; v8 < 12; v8++)
    {
        v6 -= *(_DWORD *)(a3 + 4LL * (v8 % 4));
        v9 = (v6 >> 2) & 3;
        for (i = 8; i >= 0; --i)
        {
            v4 = a1[(i + 1) % 9];
            v5 = a1[(i + 8) % 9];
            a1[i] -= ((v5 ^ *(_DWORD *)(a2 + 4LL * (v9 ^ i & 3))) + (v4 ^ v6)) ^ (((16 * v5) ^ (v4 >> 3)) + ((4 * v4) ^ (v5 >> 5)));
        }
    }
}

int main()
{
    char s[] = {
        0x23, 0xEA, 0x50, 0x30, 0x00, 0x4C, 0x51, 0x47,
        0xEE, 0x9C, 0x76, 0x2B, 0xD5, 0xE6, 0x94, 0x17,
        0xED, 0x2B, 0xE4, 0xB3, 0xCB, 0x36, 0xD5, 0x61,
        0xC0, 0xC2, 0xA0, 0x7C, 0xFE, 0x67, 0xD7, 0x5E,
        0xAF, 0xE0, 0x79, 0xC5};

    _DWORD a2[4] = {2544000949, 3782569402, 2705540682, 1519331407};
    _DWORD a3[4] = {0, 0, 0, 0};

    decrypt((_DWORD *)s, (__int64)a2, (__int64)a3);
    printf("%s\n", s);
    // 3fe4722c-1dbf-43b7-8659-c1c4a0e42e4d
    // hgame{3fe4722c-1dbf-43b7-8659-c1c4a0e42e4d}

    return 0;
}