首页
社区
课程
招聘
[求助]请大家看一下是什么算法
发表于: 2011-3-4 17:34 5460

[求助]请大家看一下是什么算法

2011-3-4 17:34
5460
正在分析一个软件,其中涉及大数运算。在该软件中,大数使用如下结构表示:
struct BigInt
{
        char Sign;                                /*表示符号。1为负;0为非负*/
        unsigned long Alloced;        /*为大整数数据所分配空间的元素数*/
        unsigned long Used;                /*实际使用空间的元素数*/
        int *Data[];                        /*大整数数据空间指针*/
}
该结构元素定位于四字节边界。
需要说明的是大整数的实际数据存放。大整数被转换成十六进制后,每十六位占据Data的一个元素,按低位在先的顺序存放。这样,软件中所使用的1024位的大整数所对应的实体数组就有64个元素。
在软件中,不论何时使用大整数,都去申请上述结构体以及数据实体所用的内存空间。
现在的问题是,当遇到其中一个函数的时候,我一时搞不清其算法,希望各位大牛指点一二。
传入该函数的共有三个大整数,即上述结构体的指针,其汇编代码如下,其中的n2就是第二个参数的实体数据的元素个数:
.text:10241C1E
.text:10241C1E ; =============== S U B R O U T I N E =======================================
.text:10241C1E
.text:10241C1E
.text:10241C1E ; int __usercall sub_10241C1E<eax>(struct BigInt *pBigInt1<eax>, struct BigInt *pBigInt2<edx>, struct BigInt *pBigInt3<ecx>)
.text:10241C1E sub_10241C1E    proc near               ; CODE XREF: sub_10241788+222
.text:10241C1E                                         ; sub_10241788+251 ...
.text:10241C1E
.text:10241C1E TmpBigInt       = BigInt ptr -20h
.text:10241C1E
.text:10241C1E                 push    edi
.text:10241C1F                 push    esi
.text:10241C20                 push    ebp
.text:10241C21                 push    ebx
.text:10241C22                 sub     esp, 1Ch
.text:10241C25                 mov     edi, ecx
.text:10241C27                 mov     ebp, edx
.text:10241C29                 mov     ebx, eax
.text:10241C2B                 lea     eax, [esp+2Ch+TmpBigInt]
.text:10241C2F                 push    ebx             ; pSrcBigInt
.text:10241C30                 push    eax             ; pDstBigInt
.text:10241C31                 mov     esi, [ebp+BigInt.Used]        ; ESI=BigInt2.Used
.text:10241C34                 call    BigIntInitCopy                ; TmpBigInt=BigInt1
.text:10241C39                 add     esp, 8
.text:10241C3C                 test    eax, eax
.text:10241C3E                 jz      short loc_10241C48
.text:10241C40                 add     esp, 1Ch
.text:10241C43                 pop     ebx
.text:10241C44                 pop     ebp
.text:10241C45                 pop     esi
.text:10241C46                 pop     edi
.text:10241C47                 retn
.text:10241C48 ; ---------------------------------------------------------------------------
.text:10241C48
.text:10241C48 loc_10241C48:                           ; CODE XREF: sub_10241C1E+20
.text:10241C48                 lea     eax, [esp+2Ch+TmpBigInt] ; pBigInt
.text:10241C4C                 lea     edx, [esi-1]    ; n
.text:10241C4F                 call    BigIntDiv_4nP2                ; TmpBigInt=TmpBigInt/(16^(n2-1))
.text:10241C54                 lea     eax, [esp+2Ch+TmpBigInt] ; pBigInt1
.text:10241C58                 mov     edx, edi        ; pBigInt2
.text:10241C5A                 call    BigIntUnsignedMul        ; TmpBigInt=TmpBigInt*BigInt3
.text:10241C5F                 lea     eax, [esp+2Ch+TmpBigInt] ; pBigInt
.text:10241C63                 add     esi, 1
.text:10241C66                 mov     edx, esi        ; n
.text:10241C68                 call    BigIntDiv_4nP2                ; TmpBigInt=TmpBigInt/(16^(n2+1))
.text:10241C6D                 mov     edi, esi
.text:10241C6F                 shl     edi, 4
.text:10241C72                 movzx   edi, di
.text:10241C75                 mov     eax, ebx        ; pBigInt
.text:10241C77                 mov     edx, edi        ; n
.text:10241C79                 call    BigIntMod_nP2                ; BigInt1=BigInt1 Mod (16^(n2+1))
.text:10241C7E                 lea     eax, [esp+2Ch+TmpBigInt] ; pBigInt1
.text:10241C82                 mov     edx, ebp        ; pBigInt2
.text:10241C84                 call    BigIntUnsignedMul        ; TmpBigInt=TmpBigInt*BigInt2
.text:10241C89                 lea     eax, [esp+2Ch+TmpBigInt] ; pBigInt
.text:10241C8D                 mov     edx, edi        ; n
.text:10241C8F                 call    BigIntMod_nP2                ; TmpBigInt=TmpBigInt Mod (16^(n2+1))
.text:10241C94                 lea     edx, [esp+2Ch+TmpBigInt] ; BigInt2
.text:10241C98                 mov     eax, ebx        ; BigInt1
.text:10241C9A                 mov     ecx, ebx        ; BigIntDiff
.text:10241C9C                 call    BigIntSignedSub                ; BigInt1=BigInt1-TmpBigInt
.text:10241CA1                 mov     edi, eax
.text:10241CA3                 test    edi, edi
.text:10241CA5                 jnz     short loc_10241CDB
.text:10241CA7                 mov     eax, ebx        ; pBigInt
.text:10241CA9                 call    BigIntSgn
.text:10241CAE                 test    eax, eax
.text:10241CB0                 jl      short loc_10241CEE        ; BigInt1<0则转
.text:10241CB2
.text:10241CB2 loc_10241CB2:                           ; CODE XREF: sub_10241C1E+109
.text:10241CB2                 mov     eax, ebx        ; BigInt1
.text:10241CB4                 mov     edx, ebp        ; BigInt2
.text:10241CB6                 call    BigIntSignedCmp                ; 比较BigInt1和BigInt2
.text:10241CBB                 test    eax, eax
.text:10241CBD                 jl      short loc_10241CDB        ; BigInt1<BigInt2则转
.text:10241CBF
.text:10241CBF loc_10241CBF:                           ; CODE XREF: sub_10241C1E+BB
.text:10241CBF                 mov     eax, ebx        ; pDstBigInt
.text:10241CC1                 mov     edx, ebp        ; pSrcBigInt
.text:10241CC3                 call    BigIntUnsignedSub        ; BigInt1=BigInt1-BigInt2
.text:10241CC8                 mov     edi, eax
.text:10241CCA                 test    edi, edi
.text:10241CCC                 jnz     short loc_10241CDB        ; 出错则转
.text:10241CCE                 mov     eax, ebx        ; BigInt1
.text:10241CD0                 mov     edx, ebp        ; BigInt2
.text:10241CD2                 call    BigIntSignedCmp        ; 比较BigInt1和BigInt2
.text:10241CD7                 test    eax, eax
.text:10241CD9                 jge     short loc_10241CBF        ; BigInt1<BigInt2则循环
.text:10241CDB
.text:10241CDB loc_10241CDB:                           ; CODE XREF: sub_10241C1E+87
.text:10241CDB                                         ; sub_10241C1E+9F ...
.text:10241CDB                 lea     eax, [esp+2Ch+TmpBigInt] ; pBigInt
.text:10241CDF                 call    UC_ReleaseBigInt                ; 释放TmpBigInt
.text:10241CE4                 mov     eax, edi
.text:10241CE6                 add     esp, 1Ch
.text:10241CE9                 pop     ebx
.text:10241CEA                 pop     ebp
.text:10241CEB                 pop     esi
.text:10241CEC                 pop     edi
.text:10241CED                 retn
.text:10241CEE ; ---------------------------------------------------------------------------
.text:10241CEE
.text:10241CEE loc_10241CEE:                           ; CODE XREF: sub_10241C1E+92
.text:10241CEE                 lea     eax, [esp+2Ch+TmpBigInt] ; pBigInt
.text:10241CF2                 call    BigIntSetZ                        ; TmpBigInt清零
.text:10241CF7                 mov     eax, [esp+2Ch+TmpBigInt.DataPtr]
.text:10241CFB                 mov     edi, 1
.text:10241D00                 mov     [eax], di                        ; TmpBigInt=1
.text:10241D03                 lea     eax, [esp+2Ch+TmpBigInt] ; SrcBigInt
.text:10241D07                 mov     edx, esi        ; n
.text:10241D09                 call    BigIntMul_4nP2                ; TmpBigInt=TmpBigInt*(16^(n2+1))
.text:10241D0E                 mov     edi, eax
.text:10241D10                 test    edi, edi
.text:10241D12                 jnz     short loc_10241CDB
.text:10241D14                 lea     edx, [esp+2Ch+TmpBigInt] ; BigInt2
.text:10241D18                 mov     eax, ebx        ; BigInt1
.text:10241D1A                 mov     ecx, ebx        ; BigIntSum
.text:10241D1C                 call    BigIntSignedAdd                ; BigInt1=BigInt1+TmpBigInt
.text:10241D21                 mov     edi, eax
.text:10241D23                 test    edi, edi
.text:10241D25                 jnz     short loc_10241CDB        ; 出错则转
.text:10241D27                 jmp     short loc_10241CB2
.text:10241D27 sub_10241C1E    endp
.text:10241D27
.text:10241D27 ; ---------------------------------------------------------------------------

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

收藏
免费 0
支持
分享
最新回复 (4)
雪    币: 324
活跃值: (1034)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
2
自己顶一顶。
2011-3-4 20:03
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
3
看不懂,不过感觉发到密码学版块应该有大牛懂的。
2011-3-4 23:15
0
雪    币: 6
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
兄弟,你搞清楚这个有用吗?只要是用到大数的加密算法无非是RSA,Elgama,ECC等变态的算法。以现在国内最高实力也还没有突破1024位(使用超级计算机),注意这里的1024位的意思是密钥是512位的。你这里这个上来就是1024位的,加密强度应该2048位……你可以用这个问题问问NSA,看他们有没有办法。而且对于用大数做密钥的算法(实用的),每一个都是天才级别的,一个公开的软件没理由自己研发一个基于大数运算的公钥算法。如果你非要搞清楚,可以自己对照那几种公开的公钥算法对比一下就知道了。
2011-3-5 10:57
0
雪    币: 324
活跃值: (1034)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
5
经多方查找资料,确认是求余运算的Barrett规约。
2011-3-10 09:08
0
游客
登录 | 注册 方可回帖
返回
//