DSA Crack or Guess

[Author] vhly
[Data] 2007/02/13 My BirthDay!

Have a good Time for everyone!

    前一段时间一直在分析Nokia Developer's Suite，通过分析发现其序列号验证方法使用了
DSA数字签名，因此就像分析一下DSA的算法。

DSA算法参数

P: 大素数 P的位数在 512<=L<=1024
Q: (P-1)的素因子 Q<2^160
G: G = H^((P-1)/Q) mod P  首先 G > 1
X: 0 < X < Q
Y: Y = G^X mod P

由于 Y = G^X mod P，那么假设 M = N*P + Y
那么 M % P 恒等于 Y
也就是说 M的取值范围中必定包含 G^X

又因为，如果要求 M = G^X
那么 如果 M = G^X 那么 M % G = 0

求 N 与 G的关系
M = N*P + Y
D = M%G
(N*P + Y)%G = 0
(N*P)%G = G - Y%G
因此可以假定第一次使M%G=0的N-> N1的值用一下公式计算
B = G - Y%G
C = P%G
N1 = B/C

也就是说
(N1*P + Y)%G = 0

同时由于求G的模，因此N的取值会以G为周期

N = (A*G+N1)

可以推出

M = (A * G + N1) * P + Y 满足 M % P = Y 满足 M % G = 0

如果 M 为 G的幂 那么

M % (G^L) 永为0 1<=L<=X

求X

已知：M = G^X，X<Q，G(Q-1)
G^(Q-1)/G^X  G^D  D = (Q-1)-X
如果 D > X
G^D/G^X G^D  D=(D-X)
重复上述步骤，直到 D<X
交换D，X
那么
最终可以到 G,1
以上算法还未真正实现，求M%G=0可以正确进行

实例
P = 5
G = 3
Y = 1

N1 = (G-Y%G)/(P%G)
   = (3-1) / (5%3)
   = 1

M = (A * G + N1)*P +Y
  = (A * 3 + 1)*5+1

A=1   M = 21 M%G = 0 M%P = 1
A=2   M = 36 M%G = 0 M%P = 1
  3       81       0       1 

M%G M%G^2 M%G^3=1

即 求出 M = 21, 36, 81 之后判断 M 是否是 G的幂

完成

没想到这篇文章刚刚发布了1个小时就被设成精华了，太感谢了。
其实分析上述方法经历了至少3、4个晚上，通过针对DSA中 G的生成，进行了大量的实例演算，同时分析了G分别为奇数以及偶数时A的取值范围，经过各种判断，最终确立了 M = (A*G+N1)*P+Y的算法来生成数据

其实最初的算法我摄制成 M = N*P + Y 如果要求M%G=0，则N要便利大量的数值。因此又继续分析求模运算的周期，以及初始数值的关系，
才将 M = (A * G + N1) * P +Y 推算出来。

在此感谢大家的关注

当然，还有求 G^X = M 式子中的 X 也就是密钥呢，这才是关键，也将是
花费运算最多的地方

vhly[FR] GEN this topic at 2007/02/13

最新的关于DSA参数的简单分析

如果最开始的方法被称为特征方法1的话，那么下面的可以被称为特征方法2了吧。

特征方法2：

根据尾数乘法的特性来进行计算。

根据，比如S = 2 X N 中的N取值为1~10，那么 S的尾数值应该为下面的数值

N尾数：1  2  3  4  5  6  7  8  9  0
S尾数：2  4  6  8  0  2  4  6  8  0

那么不论N为何值，S的值得尾数永远在上面表中。

如果假设 S = Q X N 已知Q、已知S的尾数，那么可以推断出N的尾数情况。
这样就可以在循环中去除那些根本不可能的数值。

情况一：

假设DSA参数
P=113  G=16  Y=30  （X=2）
公式: M=N*P+Y

要求M%G=0，那么M值的尾数应该在如下范围：

6  2  8  4  0

由于G是偶数，所以范围为5个数，奇数为10个数字

已知Y的尾数为0，那么N*P的尾数范围应该在：
6  2  8  4  0

又因为P的尾数已知为3，那么N的尾数范围应该为
2  4  6  8  0

由于所有数字只使用了1位，那么先进行1为测试：

N = 2  M=N*P+Y=> 256   256%16=0

当找到为2时 表达式M=N*P+Y M%G=0

那么使用G为周期

N = 18  M=N*P+Y=>2064  M%G=0


情况二：

假设DSA参数
P=113  G=16  Y=109 （X=4）
公式: M=N*P+Y

要求M%G=0，那么M值的尾数应该在如下范围：

6  2  8  4  0

由于G是偶数，所以范围为5个数，奇数为10个数字

已知Y的尾数为9，那么N*P的尾数范围应该在：
7  3  9  5  1

又因为P的尾数已知为3，那么N的尾数范围应该为
9  1  3  5  7

由于所有数字只使用了1位，那么先进行1为测试：

N=9  M=1126 M%G!=0
N=3  M=448  M%G=0

那么N最小取值为3，之后以G为周期遍历，找出M=G^X
最终可以找到。


特征方法3：

关于幂的尾数取值

任意一个数的任意次幂的尾数，都可以推算，尾数以4为周期固定变换

比如求13^1997的尾数

底数为13  底数的尾数W(13)=3  W()为求尾数
指数 1997

1997%4=1

W(3^1)=3
W(3^2)=9
W(3^3)=7
W(3^4)=1

因此13^1997的尾数为3

可求出式子

S=A^B

D1 = W(A)
D2 = B%4

W(S)=W(W(D1^4) * W(A^D2))

待到DSA参数中，可以加快（筛选）公式M=N*P+Y中N的可能取值


幂底数表
                    指数
底数    1        2         3         4
1       1        1         1         1
2       2        4         8         6
3       3        9         7         1
4       4        6         4         6
5       5        5         5         5
6       6        6         6         6
7       7        9         3         1
8       8        4         2         6
9       9        1         9         1

如果底数尾数为6 那么指数任意尾数不变
              5                     

gen at 2007/03/03
by vhly[FR]