能力值:
( LV2,RANK:150 )
|
-
-
2 楼
感觉有点像扩展的欧几里得算法。
|
能力值:
( 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。
|
能力值:
( LV3,RANK:20 )
|
-
-
4 楼
感觉好像有点像,但密码学的东西我已经看不懂了,汗ing。如果这个是求乘法逆元的,那么下面再有解密的过程,可能就是RSA了吧?
|
能力值:
( 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
这个取模运算应该如何合并?
|
能力值:
( LV2,RANK:10 )
|
-
-
6 楼
难道是传说中的RSA加密算法?
|
能力值:
( LV3,RANK:20 )
|
-
-
7 楼
另外,关于效率的问题, 如果是a1^a2%a3,那么正常的算法不就要乘上a2次才行,那时间就很可怕了,应该是O(a2)。而这个算法仔细看一下,就知道最多只乘64次,就是乘法的次数是a2的最高有效位的序号值,取模的次数也是一样的,也是最多64次,就是O(64),基本上算是个常量了。而在一般情况下,a2是远远大于64的。我跟踪过的a2基本上都是9位的10进制数。
|
能力值:
( LV4,RANK:50 )
|
-
-
8 楼
a1^a2%a3,也只需计算log(a2)次,不会多于64次的。
((a1 % a3) % (2^32)) * ((a1 % a3) % (2^32)) % a3 * a1 % a3
不能再约化,不过可以根据a1,a2,a3的值分情况讨论
|
能力值:
( LV3,RANK:20 )
|
-
-
9 楼
a1, a2, a3 都是大数,实际的数据中,一般都是9位、10位的10进制数。a3是素数,a1,a2不是。
a2,a3是本地产生的,a1是接收来的。接收到的a1,我估计是用来产生密钥的,程序后来再次的send和recv,我看那个解密函数可能是DES的(因为能看到一个8位到8字节的映射关系),但昨天搜索到2003年论坛上的一个讨论扩展欧几里德算法的,说求乘法逆元是给后面的RSA做密钥的,可是密码学的东西我实在看不懂。
|
能力值:
( 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绝大多数都不是素数,上面第一个样本是素数应该是偶然。
|
能力值:
( LV4,RANK:50 )
|
-
-
11 楼
问一下,想要了解什么呢?算法求逆,还是想知道这是什么算法?
|
能力值:
( 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,然后把公钥发给客户端,这个程序则完全是相反的。
觉得有点意思,但看的一头雾水,只是自己在瞎猜。
|
能力值:
( LV4,RANK:50 )
|
-
-
13 楼
求逆?这个函数是不可逆的,因为上面已经说明了
已知哪些参数求哪些呢?
|
能力值:
( LV3,RANK:20 )
|
-
-
14 楼
实际上不是要求这个函数的逆算法,是想知道这个函数在干什么,而知道第一个参数是含义,进而自己计算第一个参数,因为这个参数是由服务器上返回的。已知的情况包括:
1.客户端向服务器发送了3个10进制明文字符串,其中2个是素数。
2.服务器向客户端返回了一个10进制明文字符串,但响应的速度很慢,一般都是客户端把同一个明文包发送2次后,服务器才返回这个字符串。
3.客户端进行了类似 a_exp_b_mod_c 的计算,其中a是服务器返回的数,c是客户端发送的一个素数,b由客户端生成但并未发送到服务器上去。
4.上面3步完成后,客户端才开始对用户数据进行加密(根据我个人很不成熟的判断,是DES),提交给服务器。
能否通过这些描述猜测到服务器是如何生成那个10进制明文字符串的。
|
能力值:
( 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函数并没有对参数做任何约束。
|
能力值:
( LV3,RANK:20 )
|
-
-
16 楼
可能我是异想天开,或者是偷懒。因为我对密码学是一窍不通,我是刚才搞明白了 1 mod (p-1)(q-1)是什么意思。
其实就这个帖子里的内容,我好像也说了几个名词,但其实我根本就不明白那些是什么含义。
多谢版主的帮助,看来我还需要啃啃数学才行。
|
能力值:
( LV3,RANK:20 )
|
-
-
17 楼
再请教一下,关于求逆的问题。
上面版主分析不可逆是因为中间变量做了mod 2^32,这样就丧失了高32位的数据。但实际上所有输入的a1,a2,a3虽然定义是64位的,但实际的数据都是32位的,同时中间变量也都是经过mod后才赋值的,这样,那个LODWORD其实是没有作用的,因为经过mod a3之后,a3本身是32的,mod后的值肯定是32位的。这样,是否可以说这个函数在输入参数全部都是32位时是可逆的?
|
能力值:
( 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。
|
能力值:
(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 这步使用了递归.
|
能力值:
(RANK: )
|
-
-
20 楼
从你的描述来看, 你找找DSA或是Elgamal算法对照看看.
|
能力值:
( 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倍,从这一点来看,也不太象。
|
能力值:
( LV4,RANK:50 )
|
-
-
22 楼
LODWORD(v5) = someunknown(a1, (a2 - 1) / 2, a3);
对应的汇编代码是什么?
以前提供的这组数据是32位的:
S1=843535321 prime
……
你提供几组64位的看看
|
能力值:
( LV3,RANK:20 )
|
-
-
23 楼
所有记录下来的数据中,都没有64位的。另外那个a2随机生成后要and 0x7FFFFFFF,实际上只有31位。
那个LODWORD是我的错误造成了反编译的时候加上的,原因是我设置函数返回值类型的时候直接给了个int,实际上应该是__int64,因为返回值保存在edx和eax中。改为__int64后,再F5,就没有那2个LODWORD了。汗呵,误导了版主,怎么办啊.....
|
能力值:
( LV4,RANK:50 )
|
-
-
24 楼
以上两组数据中S3=S1^a2 mod S2
所以可以肯定是arab大哥说的Diffie-Hellman密钥交换算法,只不过只有32位,意义不明。
|
能力值:
(RANK: )
|
-
-
25 楼
按照这个描述, 那就是Diffie-Hellman key exchange算法了. 最终的 expmod(R, x, S2) 是双方协商后的加密Key.
参见 >> Diffie-Hellman密钥交换 <<
|
|
|