20210626-GKCTF-CryptoSecPartWriteUp
Crypto
BUU已经上题
RRRRsa
题目代码
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
47from Crypto.Util.number import *
from gmpy2 import gcd
flag = b'xxxxxxxxxxxxx'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)
print('c={}'.format(c))
p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = 65537
assert gcd(e1,(p1-1)*(q1-1)) == 1
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(2020 * p1 + q1, 202020, n1)
hint2 = pow(2021 * p1 + 212121, q1, n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))
p2 = getPrime(512)
q2 = getPrime(512)
n2 = p2*q2
e2 = 65537
assert gcd(e1,(p2-1)*(q2-1)) == 1
c2 = pow(q,e2,n2)
hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))
print('hint4={}'.format(hint4))
#c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
#n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
#c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
#hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
#hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
#n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
#c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
#hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
#hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513已知
$c\equiv m^e\ (mod\ n)$
$c_1\equiv p^e\ (mod\ n_1)$
$hint_1\equiv (2020\cdot p_1+q_1)^{202020}\ (mod\ n_1)$
$hint_2\equiv (2021\cdot p_1+212121)^{q_1}\ (mod\ n_1)$
$c_2\equiv q^{e_1}\ (mod\ n_2)$
$hint_3\equiv (2020\cdot p_2+2021\cdot q_2)^{202020}\ (mod\ n_2)$
$hint_4\equiv (2021\cdot p_2+2020q_2)^{212121}\ (mod\ n_2)$
思路如下
这道题目，大致可以分成两个部分，分别分解$n_1$和$n_2$，求出$p$和$q$，就可以解密flag了
首先肯定会二项式展开，然后就是把各种定理给用起来，此外这类题目的特点就是数字对称，思路尽量往消元的方向走
推导
跟着官方WP推导一遍
$hint_1\equiv (2020\cdot p_1+q_1)^{202020}\equiv (2020\cdot p_1)^{202020}+q_1^{202020}\ (mod\ n_1)$
$\Rightarrow hint_1=(2020\cdot p_1)^{202020}+k_1q_1$
$hint_2\equiv (2021\cdot p_1+212121)^{q_1}\ (mod\ n_1)$
即$hint_2\equiv (2021\cdot p_1+212121)^{q_1}\ (mod\ q_1)$，结合费马小定理
$\Rightarrow hint_2=2021\cdot p_1+212121+k_2q_1$
$\Rightarrow (hint_2-212121)^{202020}\equiv (2021\cdot p_1+k_2q_1)^{202020}\equiv (2021\cdot p_1)^{202020}+(k_2q_1)^{202020}\ (mod\ n_1)$
$\Rightarrow (hint_2-212121)^{202020}=(2021\cdot p_1)^{202020}+kq_1$
算出下面两个式子
$$
hint_1\times 2021^{202020}\equiv [(2020\cdot p_1)^{202020}+k_1q_1]\times 2021^{202020}\ (mod\ n_1)
$$
$$
(hint_2-212121)^{202020}\times 2020^{202020}\equiv ((2021\cdot p_1)^{202020}+kq_1)\times 2020^{202020}\ (mod\ n_1)
$$
则可以分解$n_1$，求出$p$
$$
q_1=((2)-(1),\ n_1)\notag
$$
$hint_3\equiv (2020\cdot p_2+2021\cdot q_2)^{202020}\equiv (2020\cdot p_2)^{202020}+(2021\cdot q_2)^{202020}\ (mod\ n_2)$
$hint_4\equiv (2021\cdot p_2+2020\cdot q_2)^{212121}\equiv (2021\cdot p_2)^{212121}+(2020\cdot q_2)^{212121}\ (mod\ n_2)$
算出下面两个式子（先把指数凑成一样的，再把前面系数凑成一样的
$$
hint_3^{212121}\equiv (2020\cdot p_2)^{202020\times 212121}+(2021\cdot q_2)^{202020\times212121}\ (mod\ n_2)
$$
$$
hint_4^{202020}\equiv (2021\cdot p_2)^{202020\times 212121}+(2020\cdot q_2)^{202020\times 212121}\ (mod\ n_2)
$$
则可以分解$n_2$，求出$q$
$$
q_2=((4)\times 2020^{202020\times 212121}-(3)\times 2021^{202020\times 212121},\ n_2)\notag
$$
之后便是RSA常规步骤
exp
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#!/usr/bin/env python
# coding: utf-8
def gcd(n1, n2):
if n1 == 0:
return n2
elif n2 == 0:
return n1
t = n1
while n2 > 0:
n1 = n2
n2 = t % n2
t = n1
return n1
def xgcd(n1, n2):
l1 = [1, 0]
l2 = [0, 1]
if n1 == 0:
return l2
elif n2 == 0:
return l1
t = n1 # t表示每一次的n1
i = 0 # 用来标记一下
while n2 > 0:
q = n1 // n2
l1.append(l1[i] - l1[i + 1] * q)
l2.append(l2[i] - l2[i + 1] * q)
i += 1
n1 = n2
n2 = t % n2
t = n1
# 不是求逆元，负数也无妨
return l1[i], l2[i]
def inverse(e, phi):
if gcd(e, phi) != 1:
print("e和phi不互素呢")
return
else:
return xgcd(e, phi)[0] % phi
rsa_decrypt = lambda c, p, q: pow(c, inverse(0x10001, (p - 1) * (q - 1)), p * q)
c = 13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
n1 = 75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1 = 68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
hint1 = 23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2 = 52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n2 = 114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
c2 = 67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
hint3 = 25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4 = 104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513
q1 = gcd(pow((hint2-212121) * 2020, 202020, n1) - (hint1 * pow(2021, 202020, n1)) % n1, n1)
q2 = gcd((pow(hint4, 202020, n2) * pow(2020, 202020 * 212121, n2) - pow(hint3, 212121, n2) * pow(2021, 202020 * 212121, n2)) % n2, n2)
p = rsa_decrypt(c1, n1 // q1, q1)
q = rsa_decrypt(c2, n2 // q2, q2)
flag = rsa_decrypt(c, p, q)
print(bytes.fromhex(hex(flag)[2:]))![image-20220308193051999]()
random
题目描述
代码如下
1 | import random |
生成的文本文件如下，里面有312个随机数，分别是104个32、64、96位随机数
1 | 2584323193 |
解题思路
考伪随机数，而伪随机的算法一般是MT19937
简单来说，MT19937有624个状态，每个状态32位，也就是64、96位随机数分别使用了2个、3个32位的状态
题目刚好就提供了104+104*2+104*3=624个状态
脚本搜集
MT19937Predictor
直接使用现成的脚本
1 | from hashlib import md5 |
用到了mt19937predictor模块，其实就是恢复一般的MT19937，具体的推导可以参考2022DASCTF MAY 出题人挑战赛
1 | import random |
失败的思路
主要是想根据文件的修改时间来爆破种子
但是没看到Python random模块具体的库函数实现，缺少具体细节，最终失败
Reverse
QQQQT
拖入PEiD中查看exe格式
32位没有加任何保护，运行一下程序，GUI如下
然后放入ida里面静态分析，好多函数，可是没有看到熟悉的main函数，最多只有一个叫WinMain的函数，尝试分析；好样的，看不懂
然后放入OD里面分析，鼠标右键，选择Search for，点All referenced text strings，然后会看到
东西不多，一下就能看到flag的字样
记录下push后面的地址，直接追踪过去
回到IDA找到这个地址所在位置
终于找到关键函数，跳转过去shift+F12反编译一下，得到下面伪代码
1 | int __thiscall sub_4012F0(_DWORD *this){ int v1; // edi _BYTE *v2; // esi const char *v3; // edx _BYTE *v4; // esi int v5; // ecx int v6; // eax int v7; // ecx int v8; // edx int v9; // edi int v10; // esi _BYTE *v11; // ecx unsigned int v12; // ecx int v14; // [esp-8h] [ebp-A8h] char v16[4]; // [esp+10h] [ebp-90h] BYREF char v17[4]; // [esp+14h] [ebp-8Ch] BYREF _BYTE *v18; // [esp+18h] [ebp-88h] const char *v19; // [esp+1Ch] [ebp-84h] int v20; // [esp+20h] [ebp-80h] int v21; // [esp+24h] [ebp-7Ch] BYREF _BYTE *v22; // [esp+28h] [ebp-78h] BYREF char v23[60]; // [esp+2Ch] [ebp-74h] BYREF __int128 v24[2]; // [esp+68h] [ebp-38h] BYREF __int64 v25; // [esp+88h] [ebp-18h] int v26; // [esp+9Ch] [ebp-4h] MEMORY[0x5FF6](*(_DWORD *)(this[6] + 4), v16); v26 = 0; MEMORY[0x7C7C](v16, v17); LOBYTE(v26) = 1; v19 = (const char *)MEMORY[0x7C48](v17); v24[0] = 0i64; v24[1] = 0i64; v25 = 0i64; strcpy(v23, "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"); v21 = 138 * strlen(v19) / 0x64; v14 = v21 + 1; v1 = 0; v22 = (_BYTE *)MEMORY[0x8114](v21 + 1); v2 = v22; sub_402C08(v22, 0, v14); v3 = v19; v20 = (int)(v19 + 1); if ( strlen(v19) ) { v4 = &v2[v21]; v18 = v4; while ( 1 ) { v20 = ((char)*v4 << 8) + v3[v1]; v5 = v20 / 58; *v4 = v20 % 58; if ( v5 ) { do { v6 = (char)*--v4; v7 = (v6 << 8) + v5; v20 = v7 / 58; *v4 = v7 % 58; v5 = v20; } while ( v20 ); v4 = v18; } if ( ++v1 >= strlen(v19) ) break; v3 = v19; } v2 = v22; } v8 = 0; if ( !*v2 ) { do ++v8; while ( !v2[v8] ); } v9 = v21; if ( v8 <= v21 ) { v10 = v2 - (_BYTE *)v24; do { v11 = (char *)v24 + v8++; *v11 = v23[(char)v11[v10]]; } while ( v8 <= v9 ); } if ( !MEMORY[0x7C1A](v24, "56fkoP8KhwCf3v7CEz") ) { if ( v19 ) v12 = strlen(v19); else v12 = -1; v22 = (_BYTE *)MEMORY[0x7CCC](v19, v12); LOBYTE(v26) = 2; v21 = MEMORY[0x7CCC]("flag", 4); LOBYTE(v26) = 3; MEMORY[0x6124](this, &v21, &v22, 1024, 0); MEMORY[0x7C66](&v21); MEMORY[0x7C66](&v22); } MEMORY[0x7C30](v17); return MEMORY[0x7C66]();} |
很快便可以抓住要点
显然是Base58编码
也没有怎么分析源码啦，就是看到这里还有一个判断
然后我直接将这串进行Base58解密，然后套上flag提交，通过了
something else
其他战队的wp