首页
社区
课程
招聘
[原创] CTF2019 readyu crackme (青梅竹马)设计思路
发表于: 2019-3-3 18:53 7391

[原创] CTF2019 readyu crackme (青梅竹马)设计思路

2019-3-3 18:53
7391

readyu's crackme CTF2019 Q1

readyu@pediy

正确提示:       yes, correct sn!

crackme 取名 青梅竹马 ,意指代 小素数的组合, 字面隐含谜底 "两小无猜" (方程右边为2) 。

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

最后于 2019-3-25 10:34 被readyu编辑 ,原因: FIX: 修正了在前面添零的多解问题, 比如: AAAAPVEDIy9V102dreadyu
上传的附件:
收藏
免费 3
支持
分享
最新回复 (5)
雪    币: 11147
活跃值: (3339)
能力值: (RANK:520 )
在线值:
发帖
回帖
粉丝
2
初步检查没有问题
2019-3-3 19:35
0
雪    币: 11705
活跃值: (975)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
3
自己测试发现了可构造多解的bug, 修正一下,重新上传了附件。
FIX:  修正了在前面添零的多解问题, 比如:   AAAAPVEDIy9V102dreadyu
最后于 2019-3-3 21:47 被readyu编辑 ,原因:
2019-3-3 21:44
0
雪    币: 11147
活跃值: (3339)
能力值: (RANK:520 )
在线值:
发帖
回帖
粉丝
4
readyu 自己测试发现了可构造多解的bug, 修正一下,重新上传了附件。FIX:  修正了在前面添零的多解问题, 比如:&nbsp ...
对修复后的程序检测没有发现问题
2019-3-5 18:44
0
雪    币: 4836
活跃值: (61)
能力值: ( LV4,RANK:45 )
在线值:
发帖
回帖
粉丝
5
请问前辈能发一下源码嘛,对程序一些部分的实现比较好奇
2019-3-26 23:46
0
雪    币: 11705
活跃值: (975)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
6
验证流程的主要源代码:

// 小整数求平方根,牛顿法迭代10次
int newton_root(int n)
{
    int k;
    int i;
    int n100;
    int root;

    n100 = n*100;
    k = 2;
    for(i = 0; i < 10; i++)
    {
        k = (k + n100/k) >> 1;
    }
    root = k/10;
    return root;
 }

// 筛法256以内的小素数
#define   NMAX  256
int prime_table(unsigned int n, unsigned int out[])
{      
    char mark[NMAX+1] = {0};  //有没有遍历过
    unsigned int prime[NMAX+1] = {0};  
    unsigned int primeSize;
    unsigned int rootn;
    unsigned int i;
    unsigned int j;
        
    primeSize = 0;
    if(n > NMAX)
        n = NMAX;
    rootn = newton_root(n);

    for (i = 2; i <= n; i++) 
    {
        if (mark[i] == 1)  // 已标记为合数
            continue;

        prime[primeSize] = i;
        primeSize++;
        
        if (i >= rootn)
            continue; //终止条件
        
        for (j = i * i; j <= n; j += i)
             {  
                    mark[j] = 1;  
             }  
    }

    // copy the primes
    for(i = 0; i < primeSize; i++)
    {
        out[i] = prime[i];
    }

    return primeSize;
}  


// n=100
// key=79
// N =  3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73 =
// 20364840299624512075310661735
// 41CD66ACC237B22681A18067
// exp = e=83
int check_sn(int n, unsigned int p79, unsigned char *sn, unsigned int len)
{
    int i;
    unsigned int primes[100] = {0};
    unsigned int primesize = 0;
    unsigned int e;
    unsigned int retn;
    mpi X, M, N;
    mpi P2;
    
    primesize = prime_table(n, primes);

    mpi_init(&X, &M, &N, NULL);
    mpi_init(&P2, NULL);
    
    mpi_lset(&X, 0);
    mpi_lset(&M, 0);
    mpi_lset(&N, 1);
    mpi_lset(&P2, (int)primes[0]);
    mpi_read_binary(&M, sn, len);

    // retn 置0
    retn = mpi_lget(&X);

    for(i = 1; i < (int)primesize; i++)
    {
        if(primes[i] == p79)
        {
            e = primes[i+1];
            break;
        }

        if(primes[i] != 0)
            mpi_mul_int(&N, &N, primes[i]);
    }

    //    2  <= M  <= N
    if( ( mpi_cmp_mpi(&M, &P2)>=0 ) && ( mpi_cmp_mpi(&M, &N)<=0 ) )
    {        
        // now, we get M, e, N,  calc X=M^e mod N
        
        mpi_exp_int_mod(&X, &M, e, &N);
        
        if( ( mpi_cmp_mpi(&X, &P2)>=0 ) && ( mpi_cmp_mpi(&X, &N)<=0 ) )
        {
            retn = mpi_lget(&X);
        }
    }
    
    mpi_free(&X, &M, &N, NULL);
    mpi_free(&P2, NULL);

    return retn;
}
最后于 2019-3-27 09:25 被readyu编辑 ,原因:
2019-3-27 09:21
0
游客
登录 | 注册 方可回帖
返回
//