毕业于中国科学技术大学自动控制专业,从事软件开发多年。在软件保护技术、加密算法方面有一些体验,编写了ECCTool椭圆曲线加密实用工具。
曾在北京多看科技从事电子阅读加密技术的研究,以及在小米安全团队从事IOT安全方面工作。
就方程本身而言,每个name有1个key。格式为 ( || 表示字符串相加 ):
经过分析,答案是肯定的,这样的模型存在。本题“完璧归赵”就是这个意思,也可以叫 “合二为一”。
本题方程是一个高度抽象的模同余方程, 题目验证:
h1 = hash(head)
h2 = hash(name)
h3 = hash(body)
h4 = hash(tail)
hash取sha160,
h1 = 9071232e6b170092668255303e5d824f2879ad56
h2 = 249ba36000029bbe97499c03db5a9001f6b734ec
h3 = c4b73cb0dd1d750c69e1755b06bbaffff44d2600
h4 = 6dc844c73b34d6e6b8de48da64ef92ab2b11f461
N = sha-256("完璧归赵完璧归赵") = sha256(CDEAE8B5B9E9D5D4CDEAE8B5B9E9D5D4)
3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
N只有256bit,因子分解大概1到2分钟,N=P1*P2*P3, 有三个不同的素因子:
P1:1F7BF
P2:F1059E73CFB296F8B
P3:2267D9CC91A552E23D284260B563CE490B0F7475F9D
验证过程
第1步,计算
程序里采用了先分割,然后合并的算法, 使得分析的难度加大了。
e1被切分为H,K, e1=H+K , H是某个hash,其实就是相当于一个伪随机数,H的值不重要。
V_m1h, U_m1h = lucas u,v (m0+h1, H, N)
V_m1k, U_m1k = lucas u,v (m0+h1, K, N)
利用公式合并 e1,
V_i+j = (V_i * V_j + D * U_i * U_j ) / 2, 其中 D = (m^2 - 4) mod N 是 lucas(m,1) mod N的判别式。
m1 = luc(m0 + h1, e1, N) = (Vm1h * Vm1k + D *Um1h * Um1k) /2
第2步, 计算
求解方法:
以下lcm是最小公倍数。
参照RSA, RSA的最小phi函数 为卡迈克尔函数 lcm(p-1,q-1) , 计算方便可取的phi函数为 欧拉函数(p-1)*(q-1) ,后者是前者的整数倍。
lucas的phi函数可以写作
N有3个素因子, N=p*q*r,即推广为
phi = lcm(p - 1,p + 1, q - 1, q + 1, r - 1, r + 1)。
比如:
phi = lcm(p1 - 1,p1 + 1,p2 - 1, p2 + 1,p3 - 1,p3 + 1)
phi = B492D4C14E9A74E225EC3FB39BD17C830072E04732255C87C350F579D51C03F8C130961AAD6C619EE804787627F4F2A31D71C1FA69474C51F1A1889DC8C0
e1= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133
e2= N =3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
d1 = 1/e1 mod phi
d2 = 1/e2 mod phi
d1=39027AEBF5B3D358B0075506CC37DF00393C5F191AA71B216F6F716A952206A55D9D3F81430FAE5E69E35AC4A58A98C51F472F18F347FBC300E0376DDBFB
d2=
8C7A26B58368185B65B10D3C6E9C0A6DEDAB758D3895F618A884127DCD5390470F2686B7F1771AFBE373E05DA70E382EE5DD75E71FFE1EE5BB1D63CC3CC1
按如下方程计算M0:
M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ] - h1 } mod N
最后得到:
M0=753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
从而:
key=usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83
彩蛋
如果进入彩蛋模式,额外赠送 ,可解锁用户名。
参考文档
文档:
lucas_paper.rar
cryptopp:
https://www.cryptopp.com/wiki/LUC_Cryptography
paper:
https://www.semanticscholar.org/paper/LUC%3A-A-New-Public-Key-System-Smith-Lennon/0ecfdb388bffbd623e536de70aee9ff811317cbc
LUC: A New Public Key System
Peter J. Smith, Michael J. J. LennonPublished in SEC 1993
中文文档:
int __cdecl sub_407F30(HWND hDlg)
{
CHAR *v1;
signed int v2;
signed int v3;
const CHAR *v4;
const char *v5;
CHAR *v6;
char v7;
const CHAR *v8;
_BYTE *v9;
char v10;
char v11;
_BYTE *v12;
char v13;
CHAR *v14;
char pe;
char *v17;
int v18;
int v19;
char un;
char *v21;
int v22;
int v23;
int kx;
char *v25;
int v26;
int v27;
char *input;
char *v29;
const CHAR *v30;
void (__thiscall *v31)(void *);
char v32;
char v33;
LPCSTR v34;
int v35;
int v36;
char v37;
int v38;
unsigned int v39;
int v40;
char v41;
int v42;
int v43;
int v44;
char v45;
const char *v46;
unsigned int v47;
char v48;
LPCSTR lpText;
int nIDDlgItem;
int v51;
int v52;
char *v53;
char *v54;
int *v55;
char **v56;
int v57[3];
CHAR String;
char v59;
char v60;
char v61;
__int16 v62;
char v63;
int v64;
String = 0;
memset(&v59, 0, 0x2FCu);
v62 = 0;
v63 = 0;
nIDDlgItem = 1005;
v51 = 1000;
v52 = 1001;
v1 = &String;
v2 = 0;
while ( 1 )
{
v3 = GetDlgItemTextA(hDlg, *(int *)((char *)&nIDDlgItem + v2 * 4), v1, 255);
v57[v2] = v3;
if ( v3 < 1 || v3 > 100 )
return 0;
++v2;
v1 += 256;
if ( v2 >= 3 )
{
`eh vector constructor iterator'(&v45, 0x10u, 2, sub_408360, sub_40B410);
v64 = 0;
v33 = v32;
newstring(&v33, 0);
strcpy(&v33, &String, strlen(&String));
v37 = v32;
LOBYTE(v64) = 1;
newstring(&v37, 0);
strcpy(&v37, &v60, strlen(&v60));
LOBYTE(v64) = 2;
v41 = v32;
newstring(&v41, 0);
strcpy(&v41, aKxctf19q3, strlen(aKxctf19q3));
LOBYTE(v64) = 3;
if ( !check1(&v61, (int)&v45, (int)&v48) )
{
v4 = lpText;
if ( !lpText )
v4 = (const CHAR *)&unk_419144;
v31 = 0;
v30 = aBadCode;
goto LABEL_15;
}
v5 = v46;
if ( !v46 )
v5 = (const char *)&unk_419144;
if ( !strcmp(&v37, 0, v39, v5, v47) )
{
v56 = &input;
LOBYTE(input) = v48;
newstring(&input, 0);
substr_0(&input, &v48, 0, 0xFFFFFFFF);
v55 = &kx;
LOBYTE(v64) = 4;
strmove(&kx, &v41);
v53 = &un;
LOBYTE(v64) = 5;
strmove(&un, &v37);
v54 = &pe;
LOBYTE(v64) = 6;
strmove(&pe, &v33);
LOBYTE(v64) = 3;
if ( !check2((int)hDlg, pe, v17, v18, v19, un, v21, v22, v23, kx, v25, v26, v27, (char)input, v29, (int)v30) )
{
v8 = v34;
if ( !v34 )
v8 = (const CHAR *)&unk_419144;
MessageBoxA(hDlg, v8, aBadCheck, 0);
if ( v42 )
{
v9 = (_BYTE *)(v42 - 1);
v10 = *(_BYTE *)(v42 - 1);
if ( v10 && v10 != -1 )
*v9 = v10 - 1;
else
sub_40DF24(v9);
}
v42 = 0;
v43 = 0;
v44 = 0;
if ( v38 )
{
v11 = *(_BYTE *)(v38 - 1);
v12 = (_BYTE *)(v38 - 1);
if ( v11 && v11 != -1 )
*v12 = v11 - 1;
else
sub_40DF24(v12);
}
v38 = 0;
v39 = 0;
v40 = 0;
if ( v34 )
{
v13 = *(v34 - 1);
v14 = (CHAR *)(v34 - 1);
if ( v13 && v13 != -1 )
*v14 = v13 - 1;
else
sub_40DF24(v14);
}
v34 = 0;
v35 = 0;
v36 = 0;
v64 = -1;
goto LABEL_41;
}
success(hDlg);
LOBYTE(v64) = 2;
newstring(&v41, 1);
LOBYTE(v64) = 1;
newstring(&v37, 1);
if ( v34 )
{
v6 = (CHAR *)(v34 - 1);
v7 = *(v34 - 1);
if ( v7 && v7 != -1 )
*v6 = v7 - 1;
else
sub_40DF24(v6);
}
v31 = sub_40B410;
v30 = (const CHAR *)2;
v29 = (char *)16;
v34 = 0;
v35 = 0;
v36 = 0;
v64 = -1;
input = &v45;
}
else
{
v4 = v46;
if ( !v46 )
v4 = (const CHAR *)&unk_419144;
v31 = 0;
v30 = aBadName;
LABEL_15:
MessageBoxA(hDlg, v4, v30, (UINT)v31);
LOBYTE(v64) = 2;
newstring(&v41, 1);
LOBYTE(v64) = 1;
newstring(&v37, 1);
LOBYTE(v64) = 0;
newstring(&v33, 1);
v64 = -1;
LABEL_41:
v31 = sub_40B410;
v30 = (const CHAR *)2;
v29 = (char *)16;
input = &v45;
}
`eh vector destructor iterator'(input, (unsigned int)v29, (int)v30, v31);
return 0;
}
}
}
N=0x3FBDAD083DBC11A52FA2AF1A0829C522C1492907F1B9523A17B7A8E65679BB01
message=0x9071232E6B170092668255303E5D824F2879AD56+inputnum
message2=LUCdecrypt(message,0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133,N)
message2+=0x249BA36000029BBE97499C03DB5A9001F6B734EC
(LUCdecrypt(message2,N,N)+0x6DC844C73B34D6E6B8DE48DA64EF92AB2B11F461) % N==0xC4B73CB0DD1D750C69E1755B06BBAFFFF44D2600
LUC(
v206,
v207,
big_Nadd1,
v209,
big_Index,
v211,
big_Ncp,
v213,
(int *)v214,
(int *)v215,
(int *)v216);
v169 = big_mul((int)&v263, (int *)v234, (int *)&v235);
LOBYTE(v362) = 122;
v170 = (int *)big_mul((int)&v258, (int *)&v243, (int *)v239);
LOBYTE(v362) = 123;
v171 = big_mul((int)&v256, v170, (int *)&v240);
LOBYTE(v362) = 124;
v172 = (int *)big_add((int)&v246, v171, v169);
LOBYTE(v362) = 125;
v173 = (int *)big_mod((int)&v237, v172, big_hash64);
LOBYTE(v362) = 126;
big_cpy((int *)&v251, v173);
LOBYTE(v362) = 125;
free(&v237);
LOBYTE(v362) = 124;
free(&v246);
LOBYTE(v362) = 123;
free(&v256);
LOBYTE(v362) = 122;
free(&v258);
LOBYTE(v362) = 18;
free(&v263);
big_num = (char *)&v215;
strmove_0((int *)&v215, big_hash64);
big_shr1((int *)&v251);
v174 = (int *)big_add((int)&v237, (int)&v251, (int)&v271);
详情请查看 录制你的专属视频,玩出CTF新花样!
往期赛题
* 看雪.纽盾 KCTF 2019 Q3 | 第一题点评及解题思路
* 看雪.纽盾 KCTF 2019 Q3 | 第二题点评及解题思路
* 看雪.纽盾 KCTF 2019 Q3 | 第三题点评及解题思路
* 看雪.纽盾 KCTF 2019 Q3 | 第四题点评及解题思路
* 看雪.纽盾 KCTF 2019 Q3 | 第五题点评及解题思路
* 看雪.纽盾 KCTF 2019 Q3 | 第七题点评及解题思路
合作伙伴