📄 dsa算法的理论，实现，以及在破解中的应用1.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://www.chat001.com/forum/crackforum/269524.html -->
<HTML><HEAD><TITLE>Crack论坛</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<STYLE type=text/css>BODY {
FONT-SIZE: 9pt; FONT-FAMILY: "宋体"
}
A {
FONT-SIZE: 9pt; FONT-FAMILY: "宋体"
}
TD {
FONT-SIZE: 9pt; FONT-FAMILY: "宋体"
}
A {
TEXT-TRANSFORM: none; TEXT-DECORATION: none
}
A:hover {
COLOR: red; TEXT-DECORATION: underline
}
</STYLE>
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY text=#000000 vLink=#000000 aLink=#000000 link=#000000 bgColor=#ecedf4
leftMargin=0 background=DSA算法的理论，实现，以及在破解中的应用1.files/back.gif topMargin=0><!-- 以下为论坛的最上面的连接条 --><!-- 以下为论坛主体内容 -->
<DIV align=left><B><BR>Crack论坛</B> <A
href="http://www.chat001.com/forum/crackforum/index.html">返回首页 </A><BR><BR>
<TABLE cellSpacing=0 width="100%" bgColor=#a2cefb border=0>
<TBODY>
<TR>
<TD width="100%"
height=18>
<A href="http://www.chat001.com/userreg.html">新来的客人想发言必须注册！请点击此处！</A>
</TD></TR></TBODY></TABLE><BR></DIV><B>原有信息:</B><BR><FONT color=blue>序
号:</FONT>269524<BR><FONT color=blue>标 题:</FONT>DSA算法的理论，实现，以及在破解中的应用（一）
(4千字)<BR><FONT color=blue>发信人:</FONT>娃娃[CCG]<BR><FONT color=blue>时
间:</FONT>2003-8-12 12:27:21<BR><FONT color=blue>阅读次数:</FONT>502<BR><FONT
color=blue>详细信息:</FONT><BR>
<BLOCKQUOTE>DSA算法的理论，实现，以及在破解中的应用 <BR><BR><BR> [第一部分： 理论篇]
<BR><BR> 0. 前言 <BR> 我眼中的最有代表性的公匙密码算法 ECC，RSA，DSA。
其中前两种已经被国内众多 <BR> Cracker界前辈高人详细的解释并实现，使我等初学者获益匪浅，其中尤为具代表性
<BR> 的两篇如： <BR> ●ECC加密算法入门介绍 [作者：zmworm/CCG]
<BR> ●RSA与大数运算 [作者：afanty] <BR> 更是使我受益良多。 <BR>
唯独DSA算法 由于各种原因鲜有相关文章 国内的共享软件也很少有使用这种加密算 <BR> 法进行注册验证的，
其实DSA算法有许多它自己独特的地方 它比ECC算法更加便于理 <BR> 解和实现，
比RSA产生密匙的速度快很多，且安全性与RSA不相上下 但是DSA的一个 <BR>
重要特点是两个素数(P,Q)公开，这样，当使用别人的p和q时，即使不知道私钥，你 <BR>
也能确认它们是否是随机产生的，还是作了手脚。RSA算法却作不到。 <BR> 我用了一个礼拜时间四处搜集资料
其中包括应用密码学一书中DSA算法章节 DSATool <BR> 中的说明文件 看学学院中DSA算法的简单介绍 等诸多权威信息，
经过自己的整理， <BR> 翻译，理解写出本文，文中少有复杂的数论知识，重在应用和实践，旨在起到一个抛 <BR>
砖引玉的作用 希望这套算法被更多人接受，理解，并得到广泛的应用。不足之处在所 <BR> 难免
希望各位高人能不吝赐教加以指点 ：） <BR><BR> // 为免译文不准确 部分段落引用英文原文 英文好的朋友可以自行参考
<BR><BR> 1. General stuff / 常规资料 <BR> In
1991 the Digital Signature Algorithm(DSA) has
become the Digital <BR> Signature Standard(DSS). DSA is a
public-key signature scheme that uses a <BR> pair of
transformations to generate and verify a digital value
called <BR> signature. <BR> <BR> DSA
has been developed by the US National Security Agency(NSA)
and can <BR> -not- be used for encryption or key
distribution. DSA is some variant of <BR> the ElGamal
signature algorithm and, as defined in the standard, uses the <BR>
Secure Hash Algorithm(SHA/SHA-1) as one-way hash function. <BR>
// Digital Signature Algorithm (DSA)是Schnorr和ElGamal签名算法的变种，被美国
<BR> NIST(美国国家标准局)作为数字签名标准(DigitalSignature Standard)。同样属于
<BR> 公匙密码体系，并使用Secure Hash Algorithm(SHA/SHA-1)作为中间单向计算算法
<BR><BR> 2. Parameters / 参数 <BR> P = A prime number
in range 512 to 1024 bits which must be a multiple of 64 <BR> P =
一个范围在512至1024之间的素数 且必须为64的倍数 <BR> Q = A 160 bit prime factor of
P-1 <BR> Q = P - 1的160bits的素因子 <BR> G = H^((P-1)/Q)
mod P. H is any number < P-1 such that H^((P-1)/Q) mod P > 1 <BR>
G = h^((p-1)/q) mod P，H 必须 < p - 1, h^((p-1)/q) mod p > 1
<BR> X = A number < Q <BR> X = 小于Q的一个数 <BR>
Y = G^X mod P <BR><BR> Parameters P, Q, G and Y are
public where Y is the public key. X is the <BR>
private key and must be kept secret! To obtain X from Y one needs to solve
<BR> the Discrete Logarithm Problem
which is virtually impossible for <BR>
-properly- generated parameters of reasonable size. <BR> //
以上参数其中P, Q, G 以及 Y 为公匙， X为私匙必须保密！任何第三方用户想要从 <BR> Y解密成X
都必须解决整数有限域离散对数难题 <BR><BR> 3. Signing a message (M) / 签名部分
<BR> To sign M, carry through the following steps: <BR>
// 若需要对M进行数字签名 则需要进行下列运算： <BR> - Generate a -random-
number K < Q. NEVER use same K twice or more to sign <BR>
other messages! <BR> - 产生一个随机数 K (K <
Q),，永远不要将同样的K用于进行其他的签名运算！ <BR> - Compute R = (G^K mod P) mod Q
<BR> - 计算 R = (G^K mod P) mod Q <BR> - Compute S =
(K^-1*(SHA(M) + X*R)) mod Q <BR> - 计算 S = (K^-1*(SHA(M) + X*R))
mod Q <BR><BR> The number pair (R,S) is the signature of M.
<BR> // R以及S 为这次对M的数字签名结果 <BR><BR> 4. Verifying a
signature (R,S) of M / 验证部分 <BR> - Compute W = S^-1 mod Q
<BR> - 计算 W = S^-1 mod Q <BR> - Compute U1 = (SHA(M)
* W) mod Q <BR> - 计算 U1 = (SHA(M) * W) mod Q <BR> -
Compute U2 = (R*W) mod Q <BR> - 计算 U2 = (R*W) mod Q <BR>
- Compute V = ((G^U1 * Y^U2) mod P) mod Q <BR> - 计算 V =
((G^U1 * Y^U2) mod P) mod Q <BR><BR> If V == R the signature is
verified. <BR> // 若v = r，则认为签名有效。 <BR><BR> 5.
DSA的安全性 <BR> DSA主要依赖于整数有限域离散对数难题。素数 P 必须足够大，且p-1至少包含一个大
<BR> 素数因子以抵抗Pohlig & Hellman算法的攻击。M 一般都应采用信息的HASH值(官方推
<BR> 荐为SHA算法)。DSA的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对 <BR>
于p-1的大素数因子不可约。 个人观点DSA的安全性要次于ECC 与RSA不相上下。但是有 <BR> 一点，
就是DSA算法的验证过程 R，S 是以明文形式出现的， 这点很容易被利用，在 <BR> 第二篇中各位会体会到这一点。
<BR><BR> 6. Cracker眼中的DSA <BR>
DSA算法鲜有被用于国产共享软件的注册验证部分 即使在国外的共享软件中也远不如 <BR> RSA，Blowfish等算法应用广泛。
<BR> DSA算法在破解时 关键的参数就是X 根据 Y = G^X mod P 只要知道 P，G，Y，Q 且能
<BR> 分解出 X 就可以伪造R，S写出KeyGen了。 </BLOCKQUOTE>
<HR>
<B>相关信息:</B><BR>
<UL>
<LI><IMG src="DSA算法的理论，实现，以及在破解中的应用1.files/current.gif"><IMG
src="DSA算法的理论，实现，以及在破解中的应用1.files/prime.gif"><A
href="http://www.chat001.com/forum/crackforum/269524.html"><IMG
src="DSA算法的理论，实现，以及在破解中的应用1.files/25.gif" border=0>DSA算法的理论，实现，以及在破解中的应用（一）
(4千字)</A>(<SMALL><B></SMALL><A
href="http://www.chat001.com/fmmng/userstat?name=娃娃[CCG]">娃娃[CCG]</A>
</B><SMALL>8-12 12:27</SMALL> 阅读 502)
<UL>
<LI><IMG src="DSA算法的理论，实现，以及在破解中的应用1.files/prime.gif"><A
href="http://www.chat001.com/forum/crackforum/269525.html">(二)
(13千字)</A>(<SMALL><B></SMALL><A
href="http://www.chat001.com/fmmng/userstat?name=娃娃[CCG]">娃娃[CCG]</A>
</B><SMALL>8-12 12:27</SMALL> 阅读 274)
<UL>
<LI><IMG src="DSA算法的理论，实现，以及在破解中的应用1.files/prime.gif"><A
href="http://www.chat001.com/forum/crackforum/269526.html">(三)
(5千字)</A>(<SMALL><B></SMALL><A
href="http://www.chat001.com/fmmng/userstat?name=娃娃[CCG]">娃娃[CCG]</A>
</B><SMALL>8-12 12:28</SMALL> 阅读 193)
<UL>
<LI><IMG src="DSA算法的理论，实现，以及在破解中的应用1.files/prime.gif"><A
href="http://www.chat001.com/forum/crackforum/269527.html">(四)
(1千字)</A>(<SMALL><B></SMALL><A
href="http://www.chat001.com/fmmng/userstat?name=娃娃[CCG]">娃娃[CCG]</A>
</B><SMALL>8-12 12:29</SMALL> 阅读 201)
<UL>
<LI><A href="http://www.chat001.com/forum/crackforum/269540.html"><IMG
src="DSA算法的理论，实现，以及在破解中的应用1.files/44.gif"
border=0>娃娃不错，写了这么不错的文章，真是水平越来越好了，以后要多写多发 (空)</A>(<SMALL><B></SMALL><A
href="http://www.chat001.com/fmmng/userstat?name=xy2000">xy2000</A>
</B><SMALL>8-12 14:38</SMALL> 阅读 23)
<UL>
<LI><A href="http://www.chat001.com/forum/crackforum/269541.html">TT
的确不错 (空)</A>(<SMALL><B></SMALL><A
href="http://www.chat001.com/fmmng/userstat?name=yyxzz">yyxzz</A>
</B><SMALL>8-12 14:41</SMALL> 阅读 7)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -