首页
社区
课程
招聘
[求助]看了那么长时间的RSA算法,仍然看不懂下面的这个代码
发表于: 2017-7-12 21:55 4198

[求助]看了那么长时间的RSA算法,仍然看不懂下面的这个代码

2017-7-12 21:55
4198

逆向得到一段注册程序的伪代码,请推算出注册码

{

int RSA(int message,int e,int N) {...}

bool checkSerial(char *szSerial) {

bool bResult=false;

while(1) {

if (RSA(Serial,3,0xC1594232E0C82877C7FBCF8FA1FEC2FAE9EF9FF8A60C057B891EB3B27AC60F7CB12144FA5C08C8AC64867DE4CB94CEA44E20002F488E4BA9B328BAE420D7F861) 

!= 0x8EB59040D88360FEBCF0F2808E5C1DD3A6A5D7AEAE2C780E5662319DD807692A106AD93142A9C98FDEE52EE5A3F70273B642BD8DA0FCFBD50C54E0CA666D6F42)

break;

if (RSA(Serial,3,0x8BE1C51518A608CD1A41D77418B3DF047017C9AEF2AF153AFC8112C68DD3F9924E6849B6FB38B887699F6687B166281D3B7C5F9E5A82582847558D11B07237A9) 

!= 0x17E5A0D31A661441265B4A2CACC205539646DF5EC9558B5D8A74A1B42B8647E7F9058228A37B19B01C5CBB513DD5C64B3EB90006308DC764A8B3404C7FA02E9A)

break;

if (RSA(Serial,3,0xDF343E4F83D0AE62E73BA0B6BC3342038E07961DFCA37906D89DE5E5B8BADCC84CAA438DD3FAE609A0E4F3931271E240CBEC62CCA95296776FEB0E92FEF7D671) 

!= 0x9AE829A0A5BA0E89F2626C5D3D2343F9F7DAAAEACB2487E19DAF81FE0C0B40C9F5AAD47C55257F671990D2B91D19EF3204C4EF973378550C5BB1C4CEDCE11E39)

break;

bResult = true;

break;

}

return bResult;

}

if checkSerial(注册码) MessageBox('注册成功');

else MessageBox('注册失败');

}


有大牛能指点迷津吗


[课程]Android-CTF解题方法汇总!

收藏
免费 0
支持
分享
最新回复 (5)
雪    币: 878
活跃值: (496)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
2

  三次RSA校验,  其中N和e值你可以认为是固定的RSA参, 至于推算出注册码, 假设是RSA标准算法, 其实就是用公钥和密文猜私钥, 十分困难.

2017-7-12 22:50
0
雪    币: 28972
活跃值: (7458)
能力值: ( LV15,RANK:3306 )
在线值:
发帖
回帖
粉丝
3

用中国剩余定理来解


from gmpy2 import *
from binascii import *
def chinese_remainder_theorem(items):
    M = 1
    for a, m in items:
        M *= m
    result = 0
    for a, m in items:
        Mi = M/m
        Mi_d=invert(Mi, m);
        result += a*Mi*Mi_d
    return result % M, M
def solve():
    m1 = 0xC1594232E0C82877C7FBCF8FA1FEC2FAE9EF9FF8A60C057B891EB3B27AC60F7CB12144FA5C08C8AC64867DE4CB94CEA44E20002F488E4BA9B328BAE420D7F861
    a1 = 0x8EB59040D88360FEBCF0F2808E5C1DD3A6A5D7AEAE2C780E5662319DD807692A106AD93142A9C98FDEE52EE5A3F70273B642BD8DA0FCFBD50C54E0CA666D6F42
    m2 = 0x8BE1C51518A608CD1A41D77418B3DF047017C9AEF2AF153AFC8112C68DD3F9924E6849B6FB38B887699F6687B166281D3B7C5F9E5A82582847558D11B07237A9
    a2 = 0x17E5A0D31A661441265B4A2CACC205539646DF5EC9558B5D8A74A1B42B8647E7F9058228A37B19B01C5CBB513DD5C64B3EB90006308DC764A8B3404C7FA02E9A
    m3 = 0xDF343E4F83D0AE62E73BA0B6BC3342038E07961DFCA37906D89DE5E5B8BADCC84CAA438DD3FAE609A0E4F3931271E240CBEC62CCA95296776FEB0E92FEF7D671
    a3 = 0x9AE829A0A5BA0E89F2626C5D3D2343F9F7DAAAEACB2487E19DAF81FE0C0B40C9F5AAD47C55257F671990D2B91D19EF3204C4EF973378550C5BB1C4CEDCE11E39
    data = []
    data.append([a1, m1])
    data.append([a2, m2])
    data.append([a3, m3])
    x, n = chinese_remainder_theorem(data)
    print a2b_hex(hex(iroot(x, 3)[0])[2:])
    return
solve()


>>> KEY{wgQzWssdsPdRVOo2e6j6}

2017-7-13 11:51
0
雪    币: 11705
活跃值: (970)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
4

孙子定理(中国剩余定理, CRT) 的典型应用场景.


用miracl , 带有CRT (Chinese Remainder Thereom) Class, 调用即出结果.

Crt get m =
681DEE98E3541ECAF1233A49B10A5766FF1CFE5F292DD2D4172871EF0E921AC89ECB67882EF70F49
D86D6EF8700AC724EE058AA775376B7D31F1E1A9CDD52A04A5D80E82C5AB7F9677F65

x =
4B45597B7767517A5773736473506452564F6F3265366A367D


X =>

KEY{wgQzWssdsPdRVOo2e6j6}


test.cpp:

-------------------------------------------------------


#include "big.h"
#include "crt.h"
#include "miracl.h"

using namespace std;

Miracl precision(2048, 2);

int main(int , char **)
{
    Big r[3], n[3];
    Big m , x;
    int e = 3;

    get_mip()->IOBASE=16;   
    
    n[0] = "C1594232E0C82877C7FBCF8FA1FEC2FAE9EF9FF8A60C057B891EB3B27AC60F7CB12144FA5C08C8AC64867DE4CB94CEA44E20002F488E4BA9B328BAE420D7F861" ;
    n[1] = "8BE1C51518A608CD1A41D77418B3DF047017C9AEF2AF153AFC8112C68DD3F9924E6849B6FB38B887699F6687B166281D3B7C5F9E5A82582847558D11B07237A9" ;
    n[2] = "DF343E4F83D0AE62E73BA0B6BC3342038E07961DFCA37906D89DE5E5B8BADCC84CAA438DD3FAE609A0E4F3931271E240CBEC62CCA95296776FEB0E92FEF7D671" ;

    r[0] = "8EB59040D88360FEBCF0F2808E5C1DD3A6A5D7AEAE2C780E5662319DD807692A106AD93142A9C98FDEE52EE5A3F70273B642BD8DA0FCFBD50C54E0CA666D6F42";
    r[1] = "17E5A0D31A661441265B4A2CACC205539646DF5EC9558B5D8A74A1B42B8647E7F9058228A37B19B01C5CBB513DD5C64B3EB90006308DC764A8B3404C7FA02E9A";
    r[2] = "9AE829A0A5BA0E89F2626C5D3D2343F9F7DAAAEACB2487E19DAF81FE0C0B40C9F5AAD47C55257F671990D2B91D19EF3204C4EF973378550C5BB1C4CEDCE11E39";

    
    Crt c(3, n);
    
    m = c.eval(r);
    x = root(m , e);


    cout << "Crt get m =\n" << m << "\n\n";
    cout << "x =\n" << x << "\n\n";

    return 0;
}


2017-7-13 12:13
0
雪    币: 220
活跃值: (17)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
谢谢大牛的分享,又学到了一个新知识,中国剩余定理
2017-7-13 19:34
0
雪    币: 34
活跃值: (95)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
没弄明白,是那个“3”把RSA带沟里了?
2017-7-16 00:34
0
游客
登录 | 注册 方可回帖
返回
//