-
-
[原创]kctf2022秋季赛-参赛题 by lelfei
-
2022-11-9 16:07 14668
-
key: ZSxZerX4xb4-jyvP7x12lI7
说明:
一道简单的算法题,算法原型是:一个num范围内的数n,自我累加cnt次后,模num结果与原数相差1,问这个数是多少?解法为:累加cnt次后,为什么会出现模n与原数相差1呢,是因为累加cnt-1次时,结果应为num*x+1或num*x-1,由于n<num,累加cnt-1次时n*(cnt-1)<num*(cnt-1),可以得到x<=cnt-1,可以编程检测在范围(1,cnt)中的x,判断num*x+1或num*x-1能否被cnt-1整除,只需要检测cnt次:
sbase = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
def baseConv(a):
s = ''
l = len(sbase)
while(a > 0):
s += sbase[a % l]
a //= l
return s
def calc(num, cnt):
for x in range(1, cnt):
if (num * x + 1) % (cnt - 1) == 0:
n = (num * x + 1) // (cnt - 1)
print(n, x, "+1", baseConv(n))
if (num * x - 1) % (cnt - 1) == 0:
n = (num * x - 1) // (cnt - 1)
print(n, x, "-1", baseConv(n))
这里取num=10**19,cnt=32,计算calc(10**19, 32)结果为:
3870967741935483871 12 +1 ZSxZerX4xb4
6129032258064516129 19 -1 jyvP7x12lI7
故此题答案为ZSxZerX4xb4-jyvP7x12lI7。
程序实现时,获取用户输入的key并用“-”切分成二部分,按62进制转换成2个大数sn1和sn2,再指定一个初始化大数num=(b62)IRtzloZ6iuB=10**19,要求sn1<num、sn2<num、sn1<sn2,然后循环0x200000次对sn1和sn2累加,当出现模num结果与sn1、sn2相差1时flag值增加1,发现flag为10时注册成功。然后在大数计算的二个函数BigNumMul和BigNumDiv中,发现flag>0时,检测循环次数,当正好是31时再分别把flag增加4,达到注册成功条件。在大数计算的函数中有一些干扰计算,分析时跳过即可。
此题难点在于分析过程,由于范围num和累加次数cnt与注册码没有明显联系,需要分析数的特性并用脚本穷举。只需要分析出对于给定的num和cnt,符合累加模num结果与原数相差1的数可以简单计算出来,就可以轻松求解。
程序在VC6+WIN7中编译通过。
#pragma comment (linker,"/subsystem:\"console\"") //#pragma comment (linker,"/entry:\"MyEntry\"") #pragma comment (linker,"/align:4096") #pragma comment (linker,"/merge:.rdata=.text") //把rdata段合并到text段中 #include <stdio.h> #include <string.h> //#include <windows.h> //#define SHOW_DEBUG_INFO 1 //#define ROUND_TEST_MODE 1 #define BIG_NUM_BYTE_COUNT 0x20 typedef struct _BigNum { int nLen; unsigned char bData[BIG_NUM_BYTE_COUNT]; } BigNum; typedef struct _MyFlag { BigNum m0; BigNum n0; BigNum m1; BigNum n1; BigNum nn; int cnt; int flag; BigNum ms; BigNum ns; } MyFlag; MyFlag mf; char sbase[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; char nn[] = "IRtzloZ6iuB"; int BigNumInitStr(BigNum *num, char* s, int slen); int BigNumInitNum(BigNum* numOut, int n); int BigNumCopy(BigNum* numOut, BigNum* num); int BigNumCmp(BigNum *num1, BigNum *num2); int BigNumAdd(BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumSub(BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumAnd(BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumOr( BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumXor(BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumMul(BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumDiv(BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumMod(BigNum *numOut, BigNum *num1, BigNum *num2); int BigNumModInt(BigNum *num1, int num2); int BigNumShl(BigNum *numOut, BigNum *num1, int num2); int BigNumShr(BigNum *numOut, BigNum *num1, int num2); #ifdef SHOW_DEBUG_INFO void BigNumPrint(BigNum* t, bool bRev = false) { int i, l; l = t->nLen; printf("t[%d] = ", l); char c, d; if(bRev) { for(i = l - 1; i >= 0; i--) { c = t->bData[i] >> 4; c += (c < 10 ? 48 : 55); d = t->bData[i] & 0x0F; d += (d < 10 ? 48 : 55); printf("%c%c ", c, d); } } else { for(i = 0; i < l; i++) { c = t->bData[i] >> 4; c += (c < 10 ? 48 : 55); d = t->bData[i] & 0x0F; d += (d < 10 ? 48 : 55); printf("%c%c ", c, d); } } printf("\n"); } void BaseConv(BigNum *num, char* sbase) { int i, len, k; char cc[BIG_NUM_BYTE_COUNT] = {0}; int bb[BIG_NUM_BYTE_COUNT] = {0}; int ans[BIG_NUM_BYTE_COUNT] = {0}; int olds = 256, news = strlen(sbase); if (olds == news) return; len = num->nLen; k = 0; for(i = 0; i < len; i++) bb[i] = num->bData[i]; bb[len] = 0; //set high bit before to 0 while(len) { for(i = len; i >= 1; --i) { bb[i-1] += bb[i] % news * olds; bb[i] /= news; } ans[k++] = bb[0] % news; bb[0] /= news; while(len > 0 && !bb[len-1]) --len; } for(i = 0; i < k; i++) cc[i] = sbase[ans[i]]; printf("new str[%d] = %s\n", k, cc); } #endif // SHOW_DEBUG_INFO int BigNumInitStr(BigNum *num, char* s, int slen) { int i, k = 0; int bb[BIG_NUM_BYTE_COUNT] = {0}; char c; int n; for(i = 0; i < slen; i++){ c = s[i]; if(c >= 'A' && c <= 'F') n = c - 'A' + 10; else if (c >= '0' && c <= '9') n = c - '0'; else return -1; bb[i] = n; k++; } num->nLen = (k + 1) >> 1; if(k % 2 == 1) { num->bData[k >> 1] = bb[k - 1]; k--; } for(i = 0; i < k; i += 2) num->bData[i >> 1] = (bb[i + 1] << 4 | bb[i]); return num->nLen; } int BigNumInitBase(BigNum* num, char* s, int slen, char* sbase) { int i, j, k; int baselen; int bb[BIG_NUM_BYTE_COUNT] = {0}; unsigned char c; int news = 256; baselen = strlen(sbase); for(i = 0; i < slen; i++){ c = s[i]; k = -1; for(j = 0; j < baselen; j++){ if(sbase[j] == c){ k = j; break; } } if(k < 0) return -1; bb[i] = k; } if(bb[slen - 1] == 0) return 0; //high bit cannot set to 0 bb[slen] = 0; //set high bit before to 0 k = 0; while(slen) { for(i = slen; i >= 1; --i) { bb[i-1] += bb[i] % news * baselen; bb[i] /= news; } num->bData[k++] = bb[0] % news; bb[0] /= news; while(slen > 0 && !bb[slen-1]) --slen; } if(k >= BIG_NUM_BYTE_COUNT) return -1; num->nLen = k; return k; } int BigNumInitNum(BigNum* numOut, int n) { numOut->bData[sizeof(n)] = 0; memcpy(numOut->bData, &n, sizeof(n)); int i = sizeof(n); while(i > 0 && numOut->bData[i - 1] == 0) { i--; } numOut->nLen = i; return i; } int BigNumCopy(BigNum* numOut, BigNum* num) { numOut->nLen = num->nLen; memcpy(numOut->bData, num->bData, numOut->nLen); return numOut->nLen; } int BigNumCmp(BigNum *num1, BigNum *num2) { int i; if(num1->nLen > num2->nLen) return 1; if(num1->nLen < num2->nLen) return -1; for(i = num1->nLen - 1; i >=0; i--) { if(num1->bData[i] > num2->bData[i]) return 1; if(num1->bData[i] < num2->bData[i]) return -1; } if(BigNumModInt(&mf.n1, mf.cnt) == BigNumInitNum(&mf.m1, 4)){ BigNumShr(&mf.n1, &mf.m1, mf.cnt); BigNumModInt(&mf.m1, mf.flag); } return 0; } int BigNumAdd(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, ll; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT + 4] = {0}; if(num1->nLen >= num2->nLen) ll = num1->nLen; else ll = num2->nLen; for(i = 0; i < ll; i++) { if(i < num1->nLen) nn += num1->bData[i]; if(i < num2->nLen) nn += num2->bData[i]; bb[i] = nn & 0xFF; nn >>= 8; } while(nn) { bb[i++] = nn & 0xFF; nn >>= 8; } while(i > 0 && bb[i - 1] == 0) { i--; } numOut->nLen = i; memcpy(numOut->bData, bb, i); if(BigNumModInt(&mf.n1, mf.cnt) == 4){ BigNumShr(&mf.m1, &mf.m1, mf.cnt); BigNumModInt(&mf.m1, mf.flag); } return i; } int BigNumSub(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, ll; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT] = {0}; if(num1->nLen >= num2->nLen) ll = num1->nLen; else ll = num2->nLen; for(i = 0; i < ll; i++) { if(i < num1->nLen) nn += num1->bData[i]; if(i < num2->nLen) nn -= num2->bData[i]; bb[i] = nn & 0xFF; nn >>= 8; } while(nn && i < BIG_NUM_BYTE_COUNT) { bb[i++] = nn & 0xFF; nn >>= 8; } while(i > 0 && bb[i - 1] == 0) { i--; } numOut->nLen = i; memcpy(numOut->bData, bb, i); if(BigNumModInt(&mf.nn, mf.cnt) == 4){ BigNumModInt(&mf.n1, mf.flag); BigNumShr(&mf.n1, &mf.n1, mf.cnt); } return i; } int BigNumAnd(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, ll; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT] = {0}; if(num1->nLen >= num2->nLen) ll = num1->nLen; else ll = num2->nLen; for(i = 0; i < ll; i++) { if(i < num1->nLen) nn = num1->bData[i]; else nn = 0; if(i < num2->nLen) nn &= num2->bData[i]; bb[i] = nn & 0xFF; } while(i > 0 && bb[i - 1] == 0) { i--; } numOut->nLen = i; memcpy(numOut->bData, bb, i); BigNumOr(&mf.n1, &mf.ns, &mf.m0); if(mf.cnt % 2 == 1 && BigNumCmp(&mf.n1, &mf.m1) > 0){ BigNumShl(&mf.m1, &mf.m1, mf.cnt); BigNumModInt(&mf.m1, mf.flag); } if(BigNumModInt(&mf.n1, mf.cnt) == ll){ BigNumCopy(&mf.m1, &mf.ns); ll = BigNumModInt(&mf.m1, mf.flag); BigNumInitNum(&mf.m1, ll); } return i; } int BigNumOr(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, ll; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT] = {0}; if(num1->nLen >= num2->nLen) ll = num1->nLen; else ll = num2->nLen; for(i = 0; i < ll; i++) { if(i < num1->nLen) nn = num1->bData[i]; else nn = 0; if(i < num2->nLen) nn |= num2->bData[i]; bb[i] = nn & 0xFF; } while(i > 0 && bb[i - 1] == 0) { i--; } numOut->nLen = i; memcpy(numOut->bData, bb, i); BigNumXor(&mf.m1, &mf.ms, &mf.m0); if(mf.cnt % 2 == 0 && BigNumCmp(&mf.m1, &mf.n1) == 0){ i = BigNumModInt(&mf.m1, mf.cnt); BigNumShr(&mf.m1, &mf.m1, mf.flag); BigNumInitNum(&mf.n1, i); BigNumAnd(&mf.n1, &mf.n1, &mf.nn); } if(mf.flag > 0 && BigNumCmp(&mf.m1, &mf.n1) == 0){ BigNumShr(&mf.m1, &mf.m1, mf.cnt); BigNumModInt(&mf.m1, mf.flag); BigNumShl(&mf.m1, &mf.m1, mf.cnt); } return i; } int BigNumXor(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, ll; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT] = {0}; if(num1->nLen >= num2->nLen) ll = num1->nLen; else ll = num2->nLen; for(i = 0; i < ll; i++) { if(i < num1->nLen) nn = num1->bData[i]; else nn = 0; if(i < num2->nLen) nn ^= num2->bData[i]; else nn ^= 0; bb[i] = nn & 0xFF; } while(i > 0 && bb[i - 1] == 0) { i--; } numOut->nLen = i; memcpy(numOut->bData, bb, i); if(mf.flag > 0 && BigNumModInt(&mf.n1, mf.cnt) == BigNumInitNum(&mf.m1, 4)){ BigNumShr(&mf.n1, &mf.m1, mf.cnt); BigNumModInt(&mf.m1, mf.flag); } return i; } int BigNumMul(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, j, pi, pj; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT * 2] = {0}; if(num1->nLen + num2->nLen > BIG_NUM_BYTE_COUNT){ numOut->nLen = 0; numOut->bData[0] = 0; return num1->nLen + num2->nLen; } for(i = 0; i < num1->nLen + num2->nLen - 1; i++)//5:3:7 0-6 { if(i < num1->nLen) pi = i; //i:pi 0 1 2 3 4 5 6:0 1 2 3 4 4 4 i-pi:0 0 0 0 0 1 2 else pi = num1->nLen - 1; if(i < num2->nLen) pj = i; //i:pj 0 1 2 3 4 5 6:0 1 2 2 2 2 2 i-pj:0 0 0 1 2 3 4 else pj = num2->nLen - 1; for(j = i - pj; j <= pi; j++)//num1:j:0-0 0-1 0-2 1-3 2-4 3-4 4-4 { //num2: 0-0 1-0 2-0 2-0 2-0 2-1 2-2 nn += (int)num1->bData[j] * (int)num2->bData[i - j]; } //pi-j: 0-0 1-0 2-0 2-0 2-0 1-0 0-0 bb[i] = nn & 0xFF; //pi-j+i-pi: 0-0 1-0 2-0 2-0 2-0 2-1 2-2 nn >>= 8; } while(nn) { bb[i++] = nn & 0xFF; nn >>= 8; } while(i > 0 && bb[i - 1] == 0) { i--; } if(i > BIG_NUM_BYTE_COUNT){ numOut->nLen = 0; numOut->bData[0] = 0; } else{ memcpy(numOut->bData, bb, i); numOut->nLen = i; } BigNumAnd(&mf.m1, &mf.ms, &mf.ns); if(BigNumCmp(&mf.m1, &mf.n1) > 0 && mf.flag > 0){ BigNumShr(&mf.m1, &mf.m1, mf.cnt); BigNumAdd(&mf.n1, &mf.m0, &mf.n0); BigNumSub(&mf.m1, &mf.m1, &mf.n1); } BigNumInitNum(&mf.m1, 4); BigNumShl(&mf.n1, &mf.m1, 3); if(mf.flag > 0 && *(int*)&mf.nn.bData[mf.n1.bData[0]] == (int)mf.n1.bData[0]){ BigNumAdd(&mf.m1, &mf.m1, &mf.n1); nn = BigNumModInt(&mf.m1, mf.cnt); mf.nn.bData[mf.m1.bData[0]] += 4; BigNumShl(&mf.m1, &mf.m1, nn); BigNumSub(&mf.n1, &mf.m1, &mf.n1); } return i; } int BigNumDiv(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, c; unsigned char bb[BIG_NUM_BYTE_COUNT * 2] = {0}; BigNum tt; i = BigNumCmp(num1, num2); if(i < 0) { numOut->nLen = 0; numOut->bData[0] = 0; return 0; } if(i == 0) { numOut->nLen = 1; numOut->bData[0] = 1; return 1; } c = num1->nLen - num2->nLen; tt.nLen = num2->nLen; memcpy(&tt.bData[0], &num1->bData[c], num2->nLen); for(i = c; i >= 0; i--) { while(BigNumCmp(&tt, num2) >= 0) { bb[i]++; BigNumSub(&tt, &tt, num2); } if(i > 0) { BigNumShl(&tt, &tt, 8); tt.bData[0] = num1->bData[i - 1]; if(tt.nLen == 0 && tt.bData[0] > 0) tt.nLen = 1; } } i = c + 1; while(i > 0 && bb[i - 1] == 0) { i--; } memcpy(numOut->bData, bb, i); numOut->nLen = i; BigNumSub(&mf.n1, &mf.ns, &mf.n0); BigNumAdd(&mf.m1, &mf.ms, &mf.m0); if(BigNumCmp(&mf.m1, &mf.n1) == 0 || mf.flag > 0){ BigNumShr(&mf.m1, &mf.m1, mf.cnt); BigNumModInt(&mf.m1, mf.flag); } BigNumInitNum(&mf.m1, 4); BigNumShl(&mf.n1, &mf.m1, 3); if(mf.flag > 0 && *(int*)&mf.nn.bData[mf.n1.bData[0]] == (int)mf.n1.bData[0]){ BigNumAdd(&mf.m1, &mf.m1, &mf.n1); c = BigNumModInt(&mf.m1, mf.cnt); mf.nn.bData[mf.m1.bData[0]] += 4; BigNumShl(&mf.m1, &mf.m1, c); BigNumSub(&mf.n1, &mf.m1, &mf.n1); } return i; } int BigNumMod(BigNum *numOut, BigNum *num1, BigNum *num2) { int i, c; unsigned char bb[BIG_NUM_BYTE_COUNT * 2] = {0}; BigNum tt; i = BigNumCmp(num1, num2); if(i < 0) { numOut->nLen = num1->nLen; memcpy(&numOut->bData[0], &num1->bData[0], num1->nLen); return num2->nLen; } if(i == 0) { numOut->nLen = 0; numOut->bData[0] = 0; return 0; } c = num1->nLen - num2->nLen; tt.nLen = num2->nLen; memcpy(&tt.bData[0], &num1->bData[c], num2->nLen); for(i = c; i >= 0; i--) { while(BigNumCmp(&tt, num2) >= 0) { bb[i]++; BigNumSub(&tt, &tt, num2); } if(i > 0) { BigNumShl(&tt, &tt, 8); tt.bData[0] = num1->bData[i - 1]; if(tt.nLen == 0 && tt.bData[0] > 0) tt.nLen = 1; } } memcpy(numOut->bData, &tt.bData[0], tt.nLen); numOut->nLen = tt.nLen; BigNumAnd(&mf.m1, &mf.ms, &mf.ns); if(BigNumCmp(&mf.m1, &mf.n1) > 0 && mf.flag > 0){ BigNumShr(&mf.m1, &mf.m1, mf.cnt); BigNumAdd(&mf.n1, &mf.m0, &mf.n0); BigNumSub(&mf.m1, &mf.m1, &mf.n1); } return tt.nLen; } int BigNumModInt(BigNum *num1, int num2) { int i; int nn = 0; if(num2 <= 0) return 0; for(i = num1->nLen - 1; i >= 0; i--) { nn <<= 8; nn += num1->bData[i]; if (nn > num2) nn %= num2; } return nn; } int BigNumShl(BigNum *numOut, BigNum *num1, int num2) { int i, c, n; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT * 2] = {0}; c = num2 >> 3; n = num2 % 8; if(c + num1->nLen > BIG_NUM_BYTE_COUNT) { numOut->nLen = 0; numOut->bData[0] = 0; return c + num1->nLen; } for(i = 0; ; i++) { if(i < num1->nLen) nn += (num1->bData[i] << n); bb[i + c] = nn & 0xFF; nn >>= 8; if(i >= num1->nLen && nn == 0) break; } i = c + num1->nLen + 1; while(i > 0 && bb[i - 1] == 0) { i--; } if(i > BIG_NUM_BYTE_COUNT){ numOut->nLen = 0; numOut->bData[0] = 0; } else{ memcpy(numOut->bData, bb, i); numOut->nLen = i; } return i; } int BigNumShr(BigNum *numOut, BigNum *num1, int num2) { int i, c, n, b; int nn = 0; unsigned char bb[BIG_NUM_BYTE_COUNT * 2] = {0}; c = num2 >> 3; n = num2 % 8; b = (1 << n) - 1; for(i = num1->nLen - 1; i >= c; i--) { nn <<= 8; nn += num1->bData[i]; bb[i - c] = nn >> n; nn &= b; } if(num1->nLen - c > 0) i = num1->nLen - c; else i = 0; while(i > 0 && bb[i - 1] == 0) { i--; } if(i > BIG_NUM_BYTE_COUNT){ numOut->nLen = 0; numOut->bData[0] = 0; } else{ memcpy(numOut->bData, bb, i); numOut->nLen = i; } return i; } int main() { char tmp[0x40] = {0}; int len; int i; #ifdef SHOW_DEBUG_INFO ///test mode char sn[] = "ZSxZerX4xb4-jyvP7x12lI7"; memcpy(tmp, sn, strlen(sn) + 1); #else ///real mode printf("Input:"); gets(tmp); #endif // SHOW_DEBUG_INFO //cout << "**START:" << GetTickCount() << endl; i = -1; len = 0; while(tmp[len] != 0 && len < 0x40) { if(tmp[len] == '-') i = len; len++; } if(i > 0 && (len - i) > 0){ if(BigNumInitBase(&mf.m0, tmp, i, sbase) > 0 && BigNumInitBase(&mf.n0, &tmp[i + 1], len - i - 1, sbase) > 0){ BigNumInitBase(&mf.nn, nn, strlen(nn), sbase); #ifdef SHOW_DEBUG_INFO BigNumPrint(&mf.m0, true); BaseConv(&mf.m0, sbase); BigNumPrint(&mf.n0, true); BaseConv(&mf.n0, sbase); BigNumPrint(&mf.nn, true); BaseConv(&mf.nn, sbase); #endif // SHOW_DEBUG_INFO BigNumInitNum(&mf.ms, 0); BigNumInitNum(&mf.ns, 0); if(BigNumCmp(&mf.m0, &mf.n0) < 0 && BigNumCmp(&mf.m0, &mf.nn) < 0 && BigNumCmp(&mf.n0, &mf.nn) < 0){ mf.cnt = 0; while(mf.cnt < 0x200000){ mf.cnt++; BigNumAdd(&mf.ms, &mf.ms, &mf.m0); BigNumAdd(&mf.ns, &mf.ns, &mf.n0); BigNumMod(&mf.ms, &mf.ms, &mf.nn); BigNumMod(&mf.ns, &mf.ns, &mf.nn); BigNumInitNum(&mf.m1, 1); BigNumSub(&mf.m1, &mf.ms, &mf.m1); if(BigNumCmp(&mf.m1, &mf.m0) == 0){ mf.flag++; BigNumMul(&mf.m1, &mf.m1, &mf.m0); } BigNumInitNum(&mf.n1, 1); BigNumAdd(&mf.n1, &mf.ns, &mf.n1); if(BigNumCmp(&mf.n1, &mf.n0) == 0){ mf.flag++; BigNumDiv(&mf.n1, &mf.nn, &mf.n0); } if(mf.flag == 10){ printf("Success!\n"); return 0; } #ifdef SHOW_DEBUG_INFO printf("%d\n", mf.cnt); BigNumPrint(&mf.ms, true); BigNumPrint(&mf.ns, true); #endif // SHOW_DEBUG_INFO } } } } printf("Error.\n"); return 0; }
[培训]科锐软件逆向50期预科班报名即将截止,速来!!! 50期正式班报名火爆招生中!!!