首页
社区
课程
招聘
请熟悉算法的兄弟帮忙看一下这是什么算法,多谢
发表于: 2010-11-10 16:18 13564

请熟悉算法的兄弟帮忙看一下这是什么算法,多谢

2010-11-10 16:18
13564

这个是在IDA中直接F5得到的,开始我以为是转辗相除法,但仔细一看,根本就不是的。
还请大牛指点一下。

__int64 someunknown(__int64 a1, __int64 a2, __int64 a3)
{
  __int64 v3;
  __int64 v4;
  __int64 v5;
  __int64 v7;

  if ( a2 == 1 ){
    v3 = a1 % a3;
  }else{
    if ( a2 & 1 ){
      LODWORD(v5) = someunknown(a1, (a2 - 1) / 2, a3);
      v4 = v5 * v5 % a3;
      v7 = a1;
    }else{
      LODWORD(v4) = someunknown(a1, a2 / 2, a3);
      v7 = v4;
    }
    v3 = v4 * v7 % a3;
  }
  return v3;
}


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 7
支持
分享
最新回复 (25)
雪    币: 678
活跃值: (101)
能力值: ( LV2,RANK:150 )
在线值:
发帖
回帖
粉丝
2
感觉有点像扩展的欧几里得算法。
2010-11-10 16:36
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
3
原先误解了LODWORD(v5)的含义,错误理解了算法
这个算法不可逆,具体也不知道是什么算法
设a1=2^40>a3代入得:
someunknown(a1, 1, a3)=2^40
someunknown(a1, 2, a3)=0
someunknown(a1, a2, a3)=0,其中a2>1。
2010-11-10 16:53
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
4
感觉好像有点像,但密码学的东西我已经看不懂了,汗ing。如果这个是求乘法逆元的,那么下面再有解密的过程,可能就是RSA了吧?
2010-11-10 21:21
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
5
多谢指出了取模有合并律。
不过,算法的中间量V4,V5都是只保存32位值,而a1,a2,a3都是64位的,这样实际上除了对a3取模外,还先对2^32取了模,不知道同时有2个不同的取模值时,合并律是否有效?

就是如下的
((a1 % a3) % (2^32)) * ((a1 % a3) % (2^32)) % a3 * a1 % a3
这个取模运算应该如何合并?
2010-11-10 22:21
0
雪    币: 193
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
难道是传说中的RSA加密算法?
2010-11-10 22:38
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
7
另外,关于效率的问题, 如果是a1^a2%a3,那么正常的算法不就要乘上a2次才行,那时间就很可怕了,应该是O(a2)。而这个算法仔细看一下,就知道最多只乘64次,就是乘法的次数是a2的最高有效位的序号值,取模的次数也是一样的,也是最多64次,就是O(64),基本上算是个常量了。而在一般情况下,a2是远远大于64的。我跟踪过的a2基本上都是9位的10进制数。
2010-11-10 22:50
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
8
a1^a2%a3,也只需计算log(a2)次,不会多于64次的。
((a1 % a3) % (2^32)) * ((a1 % a3) % (2^32)) % a3 * a1 % a3
不能再约化,不过可以根据a1,a2,a3的值分情况讨论
2010-11-10 23:48
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
9
a1, a2, a3 都是大数,实际的数据中,一般都是9位、10位的10进制数。a3是素数,a1,a2不是。
a2,a3是本地产生的,a1是接收来的。接收到的a1,我估计是用来产生密钥的,程序后来再次的send和recv,我看那个解密函数可能是DES的(因为能看到一个8位到8字节的映射关系),但昨天搜索到2003年论坛上的一个讨论扩展欧几里德算法的,说求乘法逆元是给后面的RSA做密钥的,可是密码学的东西我实在看不懂。
2010-11-11 09:54
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
10
写一下具体的过程。
客户端首先生成3个大数,S1,S2,S3,并在内存中给出其10进制字符串存储形式。其中,S1,S2都是素数。然后将这3个大数的10进制字符串发送给服务器。服务器返回一个大数R1的10进制字符串。下来计算 someunknow( a1, a2, a3 ),其中 a1=R1, a3=S2, a2也是客户端在recv之前自己生成的,但是内存中没有这个数的10进制字符串。
再有2组具体的值参考一下:
S1=843535321              prime
S2=a3=1429519807      prime
S3=1387999978
R1=a1=383574431              prime
a2=1185432916
RESULT=297473086

S1=1010133239              prime
S2=a3=1145723269      prime
S3=618234794
R1=a1=1134638003              NOT prime
a2=2005332635
RESULT=578739491

实际上接收到的R1绝大多数都不是素数,上面第一个样本是素数应该是偶然。
2010-11-11 11:18
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
11
问一下,想要了解什么呢?算法求逆,还是想知道这是什么算法?
2010-11-11 12:26
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
12
想知道是什么算法,知道了算法之后,应该就能求逆。

其实如果理解为 a_exp_b_mod_c 的话,就可以理解为是RSA的加解密函数,只是实际中的a和c都太小,虽然每次客户端都重新生成2个素数p和q,但那2个素数也都太小,同时在这个函数中的c竟然是素数q,而在RSA中的c=n=p*q,除非p=1。
另外,这个方向也是反的,如果要每次重新生成密钥,那么应该在服务器上生成p和q,然后把公钥发给客户端,这个程序则完全是相反的。

觉得有点意思,但看的一头雾水,只是自己在瞎猜。
2010-11-11 13:04
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
13
求逆?这个函数是不可逆的,因为上面已经说明了
已知哪些参数求哪些呢?
2010-11-11 14:20
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
14
实际上不是要求这个函数的逆算法,是想知道这个函数在干什么,而知道第一个参数是含义,进而自己计算第一个参数,因为这个参数是由服务器上返回的。已知的情况包括:
1.客户端向服务器发送了3个10进制明文字符串,其中2个是素数。
2.服务器向客户端返回了一个10进制明文字符串,但响应的速度很慢,一般都是客户端把同一个明文包发送2次后,服务器才返回这个字符串。
3.客户端进行了类似 a_exp_b_mod_c 的计算,其中a是服务器返回的数,c是客户端发送的一个素数,b由客户端生成但并未发送到服务器上去。
4.上面3步完成后,客户端才开始对用户数据进行加密(根据我个人很不成熟的判断,是DES),提交给服务器。

能否通过这些描述猜测到服务器是如何生成那个10进制明文字符串的。
2010-11-11 14:47
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
15
根据你以上描述,客户端并没有发送a2给服务端对不对?
但a2未知是不能计算someunknow( a1, a2, a3 )的。
因为someunknow函数中a1,a2,a3三个参数没有任何约束,所以服务端可以计算出a1,a2,a3。
猜测服务端是根据S1,S2,S3,来计算a2的
服务器返回的10进制明文字符串,也就是a1?
如果是的话,这个a1可以是随机数,同样因为someunknow函数并没有对参数做任何约束。
2010-11-11 15:25
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
16
可能我是异想天开,或者是偷懒。因为我对密码学是一窍不通,我是刚才搞明白了 1 mod (p-1)(q-1)是什么意思。
其实就这个帖子里的内容,我好像也说了几个名词,但其实我根本就不明白那些是什么含义。
多谢版主的帮助,看来我还需要啃啃数学才行。
2010-11-11 16:05
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
17
再请教一下,关于求逆的问题。
上面版主分析不可逆是因为中间变量做了mod 2^32,这样就丧失了高32位的数据。但实际上所有输入的a1,a2,a3虽然定义是64位的,但实际的数据都是32位的,同时中间变量也都是经过mod后才赋值的,这样,那个LODWORD其实是没有作用的,因为经过mod a3之后,a3本身是32的,mod后的值肯定是32位的。这样,是否可以说这个函数在输入参数全部都是32位时是可逆的?
2010-11-11 16:57
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
18
为方便叙述,把someunknown简称为s。
如果函数参数都是32位的或没有mod 2^32运算,则
s(a1,a2,a3)=a1^a2 mod a3,函数可逆指的是:
y=s(a1,a2,a3),(1)若其中只有a1未知,则可以根据已知的参数y,a2,a3计算出a1。
(2)若其中只有a2未知,则可以根据已知的参数y,a1,a3计算出a2。
(3)若其中只有a3未知,则可以根据足够多的参数y,a1,a2,可以计算出可能的a3。
2010-11-11 18:35
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
19
这段代码只是在计算 base ^ exp % mod 而已.
函数原型为:
__int64 expmod(__int64 base, __int64 exp, __int64 mod)
算法如下:
1. 如果 exp = 1, 则 result = base ^ 1  % mod
2. 如果 exp = 2n, 则 result = ((base ^ n  % mod) ^ 2) % mod
3. 如果 exp = 2n + 1, 则 result = ((base ^ n % mod) ^ 2 * base) % mod
base ^ n % mod 这步使用了递归.
2010-11-11 19:39
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
20
从你的描述来看, 你找找DSA或是Elgamal算法对照看看.
2010-11-11 19:53
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
21
经过对代码的跟踪,搞清楚了发送的明文之间的关系。
客户端先生成2个素数S1,S2,再生成一个随机数x,然后计算S3为
S3 = expmod( S1, x, S2);
下来客户端将S1,S2,S3发送给服务器。
服务器返回数R,然后再计算 expmod(R, x, S2);

根据这个过程,感觉有点象ElGamal算法的密钥产生和签名的过程,只是这里的随机数都是x,而ElGamal算法密钥产生时随机数是x,签名时的随机数是k,而且取值不一样。
另外,后面的数据加解密算法是等位算法,就是密文有多长,明文就有多长。而ElGamal算法的密文长度是明文长度的2倍,从这一点来看,也不太象。
2010-11-11 22:34
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
22
LODWORD(v5) = someunknown(a1, (a2 - 1) / 2, a3);
对应的汇编代码是什么?
以前提供的这组数据是32位的:
S1=843535321              prime
……
你提供几组64位的看看
2010-11-11 22:56
0
雪    币: 208
活跃值: (40)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
23
所有记录下来的数据中,都没有64位的。另外那个a2随机生成后要and 0x7FFFFFFF,实际上只有31位。

那个LODWORD是我的错误造成了反编译的时候加上的,原因是我设置函数返回值类型的时候直接给了个int,实际上应该是__int64,因为返回值保存在edx和eax中。改为__int64后,再F5,就没有那2个LODWORD了。汗呵,误导了版主,怎么办啊.....
2010-11-11 23:49
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
24
以上两组数据中S3=S1^a2 mod S2
所以可以肯定是arab大哥说的Diffie-Hellman密钥交换算法,只不过只有32位,意义不明。
2010-11-12 00:13
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
25
按照这个描述, 那就是Diffie-Hellman key exchange算法了. 最终的 expmod(R, x, S2) 是双方协商后的加密Key.
参见 >> Diffie-Hellman密钥交换 <<
2010-11-15 19:50
0
游客
登录 | 注册 方可回帖
返回
//