能力值：
( 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密钥交换 <<
|
|
|
|
