C++博客-bilicon

signaled 和 nonsignaled 在互斥对象中和事件对象中的应用

bilicon — Sat, 18 Apr 2009 02:12:00 GMT

signaled 和 nonsignaled 顾名思义就是有信号和无信号的对象了. 一个对象在有信号的状态下可以通过WaitForSingleObject函数来给它申请对象, 对象一旦申请, 线程就开始运作,对象变为无信号对象(nonsignaled)直到释放了对象,也就是变为有信号(signald)为止.

bilicon 2009-04-18 10:12 发表评论

Rijndael加密算法的介绍

bilicon — Mon, 06 Aug 2007 14:45:00 GMT

作者:林祝兴叶义雄杨国鸿

本文针对Rijndael加密算法的数学理论背景，算法的架构，回合的转换，金钥的产生，以及各种攻击破密法等等，做了一些简单的介绍。

一、简介

在AES ( Advanced Encryption Standard ) 的选拔中，从最初的十五个算法，到十个、五个，逐步筛选出适合用来作为下一代加密算法的标准。Rijndael在经过了一番时日的考验之后，也一直名列前矛。直至十月二日，Rijndael才脱颖而出，这篇文章便是针对Rijndael作简要的介绍。

Rijndael是一个反复运算的加密算法，它允许可变动的数据区块及金钥的长度。数据区块与金钥长度的变动是各自独立的。

在Rijndael算法中定义了几个名词，分述如下：

State：在运算过程中所产生的中间值，是一个4×Nb的矩阵，Nb可由数据长度除以32位求得，也就是把数据分割成Nb个区块。

Cipher Key：用来做加密运算的金钥，形式是一个4×Nk的矩阵，Nk可由金钥长度除以32位求得，也就是把金钥分割成Nk个32位的子金钥。

在Rijndael算法中，运算的回合数(Nr)是由Nb及Nk所决定的，回合数的变动定义如下表。

Nr	Nb=4	Nb=6	Nb=8
Nk=4	10	12	14
Nk=6	12	12	14
Nk=8	14	14	14

二、Rijndael的数学背景

在Rijndael中使用了许多字节层级的运算，而这些运算是以GF(2⁸)为基础架构。也有一些采用了4-byte的字组运算。在这部分，我们将介绍这些基本的数学原理。

(1) GF(2⁸)的定义

假设一个字节b由b₇b₆b₅b₄b₃b₂b₁b₀组成，我们可以把这些b_i想象成一个7次多项式的系数，而这些系数不是0就是1：

b₇ x⁷+ b₆ x⁶+ b₅ x⁵+ b₄ x⁴+ b₃ x³+ b₂ x²+ b₁ x + b₀，

例如，(57)₁₆的二进制表示法为(0101,0111)₂表示成多项式，则为：

x⁶+ x⁴+ x²+ x + 1 .

(2) 加法

两个多项式的加法，则是定义为相同指数项的系数和再模余2，简单的说就是作EXOR运算(i.e., 1+1=0)。例如：

(57)₁₆+(83)₁₆=(01010111)₂+(10000011)₂= (11010100)₂= (D4)₁₆

或是(x⁶+x⁴+x²+x+1) + (x⁷+x+1) = x⁷+x⁶+x⁴+x²

(3) 乘法

在乘法里面，多项式相乘之后的结果很容易造成溢位的问题，解决溢位的方式是把相乘的结果，再模余一个不可分解的多项式m(x)。在Rijndael中，定义一个这样子的多项式为

m(x)=x⁸+x⁴+x³+x+1或是(11B)₁₆

例如：

(57)₁₆‧(83)₁₆ = ( x⁶+ x⁴+ x²+ x + 1)‧ ( x⁷+ x + 1) = x¹³+ x¹¹+ x⁹+ x⁸+ x⁷+x⁷+ x⁵+ x³+ x²+x+x⁶+ x⁴+ x²+ x + 1

= (x¹³+ x¹¹+ x⁹+ x⁸+ x⁶+ x⁵+ x⁴+ x³+ 1+x¹³+ x¹¹+ x⁹+ x⁸+ x⁶+ x⁵+ x⁴+ x³+ 1) modulo (x⁸+ x⁴+ x³+ x + 1)

= x⁷+ x⁶+ 1=(C1)₁₆

(4) 乘以x

若把b(x)乘上x，得到b₇ x⁸+ b₆ x⁷+ b₅ x⁶+ b₄ x⁵+ b₃ x⁴+ b₂ x³+ b₁ x² + b₀x。若b₇=0，不会发生溢位问题，答案即是正确的；若b₇=1，发生溢位问题，必须减去m(x)。我们可以把这种运算表示为xtime(x)，其运算方式为left shift(若溢位则和(1B)₁₆做EXOR运算)，例如：‘57’ · ‘13’ = ‘FE’

‘57’ · ‘02’ = xtime(57) = ‘AE’

‘57’ · ‘04’ = xtime(AE) = ‘47’

‘57’ · ‘08’ = xtime(47) = ‘8E’

‘57’ · ‘10’ = xtime(8E) = ‘07’

‘57’ · ‘13’ = ‘57’ · (‘01’⊕‘02’⊕‘10’) = ‘57’ ⊕ ‘AE’ ⊕ ‘07’ = ‘FE’

三、Rijndael的加密架构

Rijndael加密算法是由一个initial Round Key addition，Nr-1个回合运算，及一个final round所组成。加密过程以C语言伪码叙述如下：

Rijndael(State, CipherKey)

//state表示输入的数据明文，

//CipherKey表示使用的加密金钥，

//ExpandedKey表示每个Round使用的子金钥。

{

KeyExpansion(CipherKey, ExpandedKey);

AddRoundKey(State, ExpandedKey);

For ( i=1; i

Round(State, ExpandedKey+Nb×i);

FinalRound(State, ExpandedKey+Nb×Nr);

}

上述算法中的Key Expansion，可以先行计算出来，所以加密过程可以简化为：

Rijndael(State,ExpandedKey)

//State表示输入的数据明文，

//ExpandedKey表示每个Round使用的子金钥。

{

AddRoundKey(State,ExpandedKey);

For( i=1 ; i

{

Round(State,ExpandedKey + Nb×i) ;

}

FinalRound (State, ExpandedKey + Nb×Nr);

}

各个子运算介绍如下。

回合转换(Round transformation)：

回合转换包含四个不同的工作，其算法如下：

Round(State,RoundKey)

//State表示输入的数据明文，

//RoundKey表示每个Round使用的子金钥。

{

ByteSub(State);

ShiftRow(State);

MixColumn(State);

AddRoundKey(State,RoundKey);

}

算法中的终止回合(Final round)包含下列工作项目：

FinalRound(State,RoundKey)

//State表示输入的数据明文，

//RoundKey表示每个Round使用的子金钥。

{

ByteSub(State) ;

ShiftRow(State) ;

AddRoundKey(State,RoundKey);

}

以下针对每个回合转换的运算过程，作一个深入的介绍，可以更清楚算法的过程。

1. 字节取代转换(ByteSub transformation)：

字节转换是一个以字节为单位的非线性取代运算，取代表(S-Box)是经过两个运算过程而建立，并且是可逆的。

首先找出每个字节在GF(2⁸)中的乘法反元素；

接着经过一个仿射(Affine)转换运算，定义如下：

(本图摘录自参考文献[1])

字节取代(ByteSub)运算对State的影响，如下图所示：

(本图摘录自参考文献[1])

字节取代(ByteSub)转换的反运算：

计算仿射对应之后的相反运算可得到S^-1-Box，以此S^-1-Box做字节取代(ByteSub)即可。

2. 移列转换( ShiftRow transformation )：

在这个转换中，State的每一列以不同的偏移量做环状位移，第0列不动，第一列位移C1个字节，第二列位移C2个字节，第三列位移C3个字节。位移的偏移量C1,C2,C3跟区块的数目(Nb)有关，定义如下表：

Nb	C1	C2	C3
4	1	2	3
6	1	2	3
8	1	3	4

移列转换(ShiftRow)运算对于State的影响，图示如下：

(本图摘录自参考文献[1])

移列转换(ShiftRow)的反运算：

对第二第三及第四列做Nb-C1,Nb-C2,Nb-C3个字节的环状位移即可。

3. 混行转换(MixColumn transformation)：

在这个转换中，把State当作一个存在GF(2⁸)中的多项式。并且对一个固定的多项式c(x)作乘法，如果发生溢位，则再模余x⁴+1。表示如下：

c(x) = ‘03’ x³ + ‘01’ x² + ‘01’ x + ‘02’ .

c(x)与x⁴+1互质，令b(x) = c(x) Ä a(x)，以矩阵乘法表示如下：

(本图摘录自参考文献[1])

State经过混行(MixColumn)运算之后的变化如下：

(本图摘录自参考文献[1])

混行(MixColumn)转换的反运算，则是乘上一个特殊的多项式d(x)，

(‘03’x³ + ‘01’x² + ‘01’x + ‘02’ ) Ä d(x) = ‘01’,

d(x) = ‘0B’x³ + ‘0D’x² + ‘09’x + ‘0E’ .

4. The Round Key Addition：

这个运算主要是把每一个回合金钥(Round Key)透过简单的bitwise EXOR加入到每一个State中，以图示如下：

(本图摘录自参考文献[1])

四、金钥的排程(Key Schedule)

回合金钥(Round Key)是从加密金钥(Cipher Key)经过运算产生出来的。金钥排程(Key Schedule)是由金钥扩充(Key Expansion)及回合金钥的选择(Round Key Selection)组成的，基本的理论如下：

所有回合金钥的总位数是把区块长度(block length)乘上回合数加1，(有Nr-1个回合，加上一个终止回合(final round))，例如，128个位的区块长度经过10个回合运算，所需要用到的所有回合金钥的总位数为1408个位。

加密金钥(Cipher Key)必须扩充为扩充金钥(Expanded Key)。

回合金钥是从扩充金钥中选出来的，选择的方式如下：

第一个回合金钥由前Nb个字组组成，第二个回合金钥由接下来的Nb个字组组成，余此类推。

(1) 金钥的扩充( Key Expansion )：

扩充后的金钥是一个4-byte的线性数组，表示为W[Nb×(Nr+1)]。前Nk个字组包含了加密金钥(Cipher Key)。

金钥扩充函式和Nk是息息相关的，分为两种情况运作，一是当Nk小于或等于6，另外则是当Nk大于6，以伪码叙述如下：

当Nk≦6时，

KeyExpansion(byte Key[4×Nk] word W[Nb×(Nr+1)])

{

for(i = 0; i < Nk; i++)

W[i] = (Key[4×i], Key[4×i+1], Key[4×i+2], Key[4×i+3] );

for(i = Nk; i < Nb×(Nr + 1); i++)

{

temp = W[i - 1];

if (i % Nk == 0)

temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];

W[i] = W[i - Nk] ^ temp;

}

在上面的子程序中，SubByte(W)传回一个4-byte的字组，这些字组是输入的字组经过S-box的转换所产生的相对字组。RotByte(W)则是传回经过旋转的字组。

当Nk＞6时，

KeyExpansion(byte Key[4×Nk] word W[Nb×(Nr+1)])

{

for(i = 0; i < Nk; i++)

W[i] = (key[4×i],key[4×i+1], key[4×i+2], key[4×i+3] );

for(i = Nk; i < Nb×(Nr + 1); i++)

{

temp = W[i - 1];

if (i % Nk == 0)

temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];

else if (i % Nk == 4)

temp = SubByte(temp);

W[i] = W[i - Nk] ^ temp;

}

以上两种情况的相异处在于当Nk≦6时，(i-4)是Nk的倍数时，对于W[i-1]先执行SubByte，再执行EXOR。

上述回合常数定义如下：

Rcon[i] = (RC[i],‘00’,‘00’,‘00’)，其中RC[0]=’01’，RC[i]=xtime(Rcon[i-1])。

(2) 选择回合金钥(Round Key Selection)

第i个回合金钥是指在存在回合金钥缓冲区的字组W[Nb*i]到W[Nb*(i+1)]，图示如下：

(本图摘录自参考文献[1])

五、安全性分析

我们针对以下已知的攻击法对Rijndael的安全性分析作一简要叙述，包括差分攻击法(Differential Cryptanalysis)，线性攻击法(Linear Cryptanalysis)，平方攻击法(The Square Attack)，内插攻击法(Interpolation attacks)等攻击方式。

(1) 差分攻击法( Differential Cryptanalysis )

此攻击法是一种Chosen-plaintext attack，利用大量已知的明文/密文对之间的差异，据以推测出金钥的位值。在大部分的回合运算中(回合数超过3)，若存在超过2^1-n(n指的是区块长度)比例的可预测性的差异，这个攻击法就可以推测出金钥的位值。在Rijndael中，已经证明在经过Rijndael四个回合的运算后，存在不超过2^-150比例的可预测性差异，在八个回合运算中不超过2^-300。详细证明过程，请参照参考文献。

(2) 线性攻击法( Linear Cryptanalysis )

这是一种Known-plaintext攻击法，利用大量搜集到的明文/密文对的相关性，对加密法进行攻击。明文/密文对的相关性由线性轨迹(Linear trails)所组成，由于线性轨迹的相关系数与Round keys的值有密切关系，透过相关系数的正负号，线性攻击法就可以找出金钥值。要对抗这种攻击法，有一个必要条件就是使这种相关系数大于2^n/2的线性轨迹不存在。在Rijndael中，已经证明出当执行四个回合时，不存在相关系数大于2^-75的线性轨迹；在执行八个回合时，其相关系数大于2^-150的相关系数亦不存在。详细证明过程请参照参考文献。

(3) 平方攻击法( The Square attack )

这种攻击法是一种chosen- plaintext attack，而且和字节取代(ByteSub)，混行(MixColumn)时的多项式乘法，金钥的排程(Key Schedule)等运算无关。当Rijndael执行6个回合以上时，此种方式比完全的金钥搜寻(exhaustive key search)来的更有效率。关于此种攻击方式的详尽描述及Rijndael如何延伸此种攻击方式，请参照参考文献。

(4) 内插攻击法( Interpolation attacks )

在这种攻击法中，攻击者利用加密的输入及输出配对，建立一些多项式。如果加密的组件有一个简洁的代数展开式，并且和管理的复杂度结合在一起时，这种攻击法便是可行的。基本的攻击方式是如果攻击者建立的代数展开式的阶度(degree)很小，只需要一些加密法的输入及输出配对就可以得到代数展开式的各项系数。然而，在GF(2⁸)中的取代矩阵(S-box)，它的展开式为：63+8fx¹²⁷+b5x¹⁹¹+01x²²³+f4x²³⁹+25x²⁴⁷+f9x²⁵¹+09x²⁵³+05x²⁵⁴。其余介绍，请参照参考文献。

(5)、弱金钥(Weak keys)

关于弱金钥的发生，基本上是因为加密法的非线性运算与实际金钥值有密切关系。而这种问题不存在于Rijndael之中，因为在Rijndael中，金钥是以EXOR运算，而所有的非线性运算都定义在取代矩阵(S-box)中。在Rijndael中，对金钥的选择，是没有限制的。

六、结论：

以上对Rijndael作一简要介绍之后，我们以Rijndael的优点与限制作为我们的结论。

(1)、Rijndael有以下优点—

以实作观点而言

1. Rijndael可以实作在Pentium ( Pro ) 等计算机上，并已相当快的速度处理运算；而在表格大小与效率之间是可以做取舍的。

2. Rijndael可以实作在智能卡(Smart Card)上，使用少量的RAM，少量的程序代码；在ROM与效率之间也是可以做取舍的。

3. 在设计上，回合的转换是可平行处理的。

4. 加密法不采用算术运算，不会因为不同处理器架构而有所偏差。

设计简单化：

1. 设计上不引用其它加密组件，如S-box。

2. 安全度不建立在一些分析不够明确的算术运算之上。

3. 加密法紧凑，不易藏入暗门等程序代码。

除此之外，Rijndael更允许可变动的区块长度及金钥长度，其长度可由128位到256位之间；所以回合数也是可变动的。

(2)Rijndael的限制：

在解密过程中有以下限制

1. 实作在智慧卡时，解密不如加密来的有效率，解密需要更多的程序代码及cycles，但是跟其它算法比起来，仍然是快速的。

2. 以软件而言，加密和解密使用不同的程序和表格。

3. 以硬件而言，解密只能重用部分加密的电路。

bilicon 2007-08-06 22:45 发表评论

MD5~RFC 1321

bilicon — Fri, 03 Aug 2007 04:35:00 GMT

Network Working Group                                          R. Rivest
Request for Comments: 1321           MIT Laboratory for Computer Science
and RSA Data Security, Inc.
April 1992
The MD5 Message-Digest Algorithm
Status of this Memo
This memo provides information for the Internet community.  It does
not specify an Internet standard.  Distribution of this memo is
unlimited.
Acknowlegements
We would like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle,
David Chaum, and Noam Nisan for numerous helpful comments and
suggestions.
Table of Contents
1. Executive Summary                                                1
2. Terminology and Notation                                         2
3. MD5 Algorithm Description                                        3
4. Summary                                                          6
5. Differences Between MD4 and MD5                                  6
References                                                          7
APPENDIX A - Reference Implementation                               7
Security Considerations                                            21
Author's Address                                                   21
1. Executive Summary
This document describes the MD5 message-digest algorithm. The
algorithm takes as input a message of arbitrary length and produces
as output a 128-bit "fingerprint" or "message digest" of the input.
It is conjectured that it is computationally infeasible to produce
two messages having the same message digest, or to produce any
message having a given prespecified target message digest. The MD5
algorithm is intended for digital signature applications, where a
large file must be "compressed" in a secure manner before being
encrypted with a private (secret) key under a public-key cryptosystem
such as RSA.
Rivest                                                          [Page 1]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
The MD5 algorithm is designed to be quite fast on 32-bit machines. In
addition, the MD5 algorithm does not require any large substitution
tables; the algorithm can be coded quite compactly.
The MD5 algorithm is an extension of the MD4 message-digest algorithm
1,2]. MD5 is slightly slower than MD4, but is more "conservative" in
design. MD5 was designed because it was felt that MD4 was perhaps
being adopted for use more quickly than justified by the existing
critical review; because MD4 was designed to be exceptionally fast,
it is "at the edge" in terms of risking successful cryptanalytic
attack. MD5 backs off a bit, giving up a little in speed for a much
greater likelihood of ultimate security. It incorporates some
suggestions made by various reviewers, and contains additional
optimizations. The MD5 algorithm is being placed in the public domain
for review and possible adoption as a standard.
For OSI-based applications, MD5's object identifier is
md5 OBJECT IDENTIFIER ::=
iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5}
In the X.509 type AlgorithmIdentifier [3], the parameters for MD5
should have type NULL.
2. Terminology and Notation
In this document a "word" is a 32-bit quantity and a "byte" is an
eight-bit quantity. A sequence of bits can be interpreted in a
natural manner as a sequence of bytes, where each consecutive group
of eight bits is interpreted as a byte with the high-order (most
significant) bit of each byte listed first. Similarly, a sequence of
bytes can be interpreted as a sequence of 32-bit words, where each
consecutive group of four bytes is interpreted as a word with the
low-order (least significant) byte given first.
Let x_i denote "x sub i". If the subscript is an expression, we
surround it in braces, as in x_{i+1}. Similarly, we use ^ for
superscripts (exponentiation), so that x^i denotes x to the i-th
power.
Let the symbol "+" denote addition of words (i.e., modulo-2^32
addition). Let X <<< s denote the 32-bit value obtained by circularly
shifting (rotating) X left by s bit positions. Let not(X) denote the
bit-wise complement of X, and let X v Y denote the bit-wise OR of X
and Y. Let X xor Y denote the bit-wise XOR of X and Y, and let XY
denote the bit-wise AND of X and Y.
Rivest                                                          [Page 2]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
3. MD5 Algorithm Description
We begin by supposing that we have a b-bit message as input, and that
we wish to find its message digest. Here b is an arbitrary
nonnegative integer; b may be zero, it need not be a multiple of
eight, and it may be arbitrarily large. We imagine the bits of the
message written down as follows:
m_0 m_1 ... m_{b-1}
The following five steps are performed to compute the message digest
of the message.
3.1 Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is
congruent to 448, modulo 512. That is, the message is extended so
that it is just 64 bits shy of being a multiple of 512 bits long.
Padding is always performed, even if the length of the message is
already congruent to 448, modulo 512.
Padding is performed as follows: a single "1" bit is appended to the
message, and then "0" bits are appended so that the length in bits of
the padded message becomes congruent to 448, modulo 512. In all, at
least one bit and at most 512 bits are appended.
3.2 Step 2. Append Length
A 64-bit representation of b (the length of the message before the
padding bits were added) is appended to the result of the previous
step. In the unlikely event that b is greater than 2^64, then only
the low-order 64 bits of b are used. (These bits are appended as two
32-bit words and appended low-order word first in accordance with the
previous conventions.)
At this point the resulting message (after padding with bits and with
b) has a length that is an exact multiple of 512 bits. Equivalently,
this message has a length that is an exact multiple of 16 (32-bit)
words. Let M[0 ... N-1] denote the words of the resulting message,
where N is a multiple of 16.
3.3 Step 3. Initialize MD Buffer
A four-word buffer (A,B,C,D) is used to compute the message digest.
Here each of A, B, C, D is a 32-bit register. These registers are
initialized to the following values in hexadecimal, low-order bytes
first):
Rivest                                                          [Page 3]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
3.4 Step 4. Process Message in 16-Word Blocks
We first define four auxiliary functions that each take as input
three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
In each bit position F acts as a conditional: if X then Y else Z.
The function F could have been defined using + instead of v since XY
and not(X)Z will never have 1's in the same bit position.) It is
interesting to note that if the bits of X, Y, and Z are independent
and unbiased, the each bit of F(X,Y,Z) will be independent and
unbiased.
The functions G, H, and I are similar to the function F, in that they
act in "bitwise parallel" to produce their output from the bits of X,
Y, and Z, in such a manner that if the corresponding bits of X, Y,
and Z are independent and unbiased, then each bit of G(X,Y,Z),
H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that
the function H is the bit-wise "xor" or "parity" function of its
inputs.
This step uses a 64-element table T[1 ... 64] constructed from the
sine function. Let T[i] denote the i-th element of the table, which
is equal to the integer part of 4294967296 times abs(sin(i)), where i
is in radians. The elements of the table are given in the appendix.
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */
/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B
Rivest                                                          [Page 4]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
CC = C
DD = D
/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
[ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
[ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
[ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]
/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
[ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
[ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
[ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]
/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
[ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
[ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
[ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]
/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
[ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
[ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
[ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]
/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /* of loop on i */
Rivest                                                          [Page 5]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
3.5 Step 5. Output
The message digest produced as output is A, B, C, D. That is, we
begin with the low-order byte of A, and end with the high-order byte
of D.
This completes the description of MD5. A reference implementation in
C is given in the appendix.
4. Summary
The MD5 message-digest algorithm is simple to implement, and provides
a "fingerprint" or message digest of a message of arbitrary length.
It is conjectured that the difficulty of coming up with two messages
having the same message digest is on the order of 2^64 operations,
and that the difficulty of coming up with any message having a given
message digest is on the order of 2^128 operations. The MD5 algorithm
has been carefully scrutinized for weaknesses. It is, however, a
relatively new algorithm and further security analysis is of course
justified, as is the case with any new proposal of this sort.
5. Differences Between MD4 and MD5
The following are the differences between MD4 and MD5:
1.   A fourth round has been added.
2.   Each step now has a unique additive constant.
3.   The function g in round 2 was changed from (XY v XZ v YZ) to
(XZ v Y not(Z)) to make g less symmetric.
4.   Each step now adds in the result of the previous step.  This
promotes a faster "avalanche effect".
5.   The order in which input words are accessed in rounds 2 and
3 is changed, to make these patterns less like each other.
6.   The shift amounts in each round have been approximately
optimized, to yield a faster "avalanche effect." The shifts in
different rounds are distinct.
Rivest                                                          [Page 6]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
References
[1] Rivest, R., "The MD4 Message Digest Algorithm", RFC 1320, MIT and
RSA Data Security, Inc., April 1992.
[2] Rivest, R., "The MD4 message digest algorithm", in A.J.  Menezes
and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO '90
Proceedings, pages 303-311, Springer-Verlag, 1991.
[3] CCITT Recommendation X.509 (1988), "The Directory -
Authentication Framework."
APPENDIX A - Reference Implementation
This appendix contains the following files taken from RSAREF: A
Cryptographic Toolkit for Privacy-Enhanced Mail:
global.h -- global header file
md5.h -- header file for MD5
md5c.c -- source code for MD5
For more information on RSAREF, send email to .
The appendix also includes the following file:
mddriver.c -- test driver for MD2, MD4 and MD5
The driver compiles for MD5 by default but can compile for MD2 or MD4
if the symbol MD is defined on the C compiler command line as 2 or 4.
The implementation is portable and should work on many different
plaforms. However, it is not difficult to optimize the implementation
on particular platforms, an exercise left to the reader. For example,
on "little-endian" platforms where the lowest-addressed byte in a 32-
bit word is the least significant and there are no alignment
restrictions, the call to Decode in MD5Transform can be replaced with
a typecast.
A.1 global.h
/* GLOBAL.H - RSAREF types and constants
*/
/* PROTOTYPES should be set to one if and only if the compiler supports
function argument prototyping.
The following makes PROTOTYPES default to 0 if it has not already
Rivest                                                          [Page 7]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
been defined with C compiler flags.
*/
#ifndef PROTOTYPES
#define PROTOTYPES 0
#endif
/* POINTER defines a generic pointer type */
typedef unsigned char *POINTER;
/* UINT2 defines a two byte word */
typedef unsigned short int UINT2;
/* UINT4 defines a four byte word */
typedef unsigned long int UINT4;
/* PROTO_LIST is defined depending on how PROTOTYPES is defined above.
If using PROTOTYPES, then PROTO_LIST returns the list, otherwise it
returns an empty list.
*/
#if PROTOTYPES
#define PROTO_LIST(list) list
#else
#define PROTO_LIST(list) ()
#endif
A.2 md5.h
/* MD5.H - header file for MD5C.C
*/
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.
License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.
License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.
RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.
Rivest                                                          [Page 8]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
These notices must be retained in any copies of any part of this
documentation and/or software.
*/
/* MD5 context. */
typedef struct {
UINT4 state[4];                                   /* state (ABCD) */
UINT4 count[2];        /* number of bits, modulo 2^64 (lsb first) */
unsigned char buffer[64];                         /* input buffer */
} MD5_CTX;
void MD5Init PROTO_LIST ((MD5_CTX *));
void MD5Update PROTO_LIST
((MD5_CTX *, unsigned char *, unsigned int));
void MD5Final PROTO_LIST ((unsigned char [16], MD5_CTX *));
A.3 md5c.c
/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
*/
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.
License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.
License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.
RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.
These notices must be retained in any copies of any part of this
documentation and/or software.
*/
#include "global.h"
#include "md5.h"
/* Constants for MD5Transform routine.
*/
Rivest                                                          [Page 9]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
#define S11 7
#define S12 12
#define S13 17
#define S14 22
#define S21 5
#define S22 9
#define S23 14
#define S24 20
#define S31 4
#define S32 11
#define S33 16
#define S34 23
#define S41 6
#define S42 10
#define S43 15
#define S44 21
static void MD5Transform PROTO_LIST ((UINT4 [4], unsigned char [64]));
static void Encode PROTO_LIST
((unsigned char *, UINT4 *, unsigned int));
static void Decode PROTO_LIST
((UINT4 *, unsigned char *, unsigned int));
static void MD5_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));
static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int));
static unsigned char PADDING[64] = {
0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
/* F, G, H and I are basic MD5 functions.
*/
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
/* ROTATE_LEFT rotates x left n bits.
*/
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
Rotation is separate from addition to prevent recomputation.
*/
#define FF(a, b, c, d, x, s, ac) { \
(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
Rivest                                                         [Page 10]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
(a) += (b); \
}
#define GG(a, b, c, d, x, s, ac) { \
(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}
#define HH(a, b, c, d, x, s, ac) { \
(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}
#define II(a, b, c, d, x, s, ac) { \
(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}
/* MD5 initialization. Begins an MD5 operation, writing a new context.
*/
void MD5Init (context)
MD5_CTX *context;                                        /* context */
{
context->count[0] = context->count[1] = 0;
/* Load magic initialization constants.
*/
context->state[0] = 0x67452301;
context->state[1] = 0xefcdab89;
context->state[2] = 0x98badcfe;
context->state[3] = 0x10325476;
}
/* MD5 block update operation. Continues an MD5 message-digest
operation, processing another message block, and updating the
context.
*/
void MD5Update (context, input, inputLen)
MD5_CTX *context;                                        /* context */
unsigned char *input;                                /* input block */
unsigned int inputLen;                     /* length of input block */
{
unsigned int i, index, partLen;
/* Compute number of bytes mod 64 */
index = (unsigned int)((context->count[0] >> 3) & 0x3F);
/* Update number of bits */
if ((context->count[0] += ((UINT4)inputLen << 3))
Rivest                                                         [Page 11]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
< ((UINT4)inputLen << 3))
context->count[1]++;
context->count[1] += ((UINT4)inputLen >> 29);
partLen = 64 - index;
/* Transform as many times as possible.
*/
if (inputLen >= partLen) {
MD5_memcpy
((POINTER)&context->buffer[index], (POINTER)input, partLen);
MD5Transform (context->state, context->buffer);
for (i = partLen; i + 63 < inputLen; i += 64)
MD5Transform (context->state, &input[i]);
index = 0;
}
else
i = 0;
/* Buffer remaining input */
MD5_memcpy
((POINTER)&context->buffer[index], (POINTER)&input[i],
inputLen-i);
}
/* MD5 finalization. Ends an MD5 message-digest operation, writing the
the message digest and zeroizing the context.
*/
void MD5Final (digest, context)
unsigned char digest[16];                         /* message digest */
MD5_CTX *context;                                       /* context */
{
unsigned char bits[8];
unsigned int index, padLen;
/* Save number of bits */
Encode (bits, context->count, 8);
/* Pad out to 56 mod 64.
*/
index = (unsigned int)((context->count[0] >> 3) & 0x3f);
padLen = (index < 56) ? (56 - index) : (120 - index);
MD5Update (context, PADDING, padLen);
/* Append length (before padding) */
MD5Update (context, bits, 8);
Rivest                                                         [Page 12]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
/* Store state in digest */
Encode (digest, context->state, 16);
/* Zeroize sensitive information.
*/
MD5_memset ((POINTER)context, 0, sizeof (*context));
}
/* MD5 basic transformation. Transforms state based on block.
*/
static void MD5Transform (state, block)
UINT4 state[4];
unsigned char block[64];
{
UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
Decode (x, block, 64);
/* Round 1 */
FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
/* Round 2 */
GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
Rivest                                                         [Page 13]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
/* Round 3 */
HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
/* Round 4 */
II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
/* Zeroize sensitive information.
Rivest                                                         [Page 14]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
*/
MD5_memset ((POINTER)x, 0, sizeof (x));
}
/* Encodes input (UINT4) into output (unsigned char). Assumes len is
a multiple of 4.
*/
static void Encode (output, input, len)
unsigned char *output;
UINT4 *input;
unsigned int len;
{
unsigned int i, j;
for (i = 0, j = 0; j < len; i++, j += 4) {
output[j] = (unsigned char)(input[i] & 0xff);
output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
}
}
/* Decodes input (unsigned char) into output (UINT4). Assumes len is
a multiple of 4.
*/
static void Decode (output, input, len)
UINT4 *output;
unsigned char *input;
unsigned int len;
{
unsigned int i, j;
for (i = 0, j = 0; j < len; i++, j += 4)
output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
(((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
}
/* Note: Replace "for loop" with standard memcpy if possible.
*/
static void MD5_memcpy (output, input, len)
POINTER output;
POINTER input;
unsigned int len;
{
unsigned int i;
for (i = 0; i < len; i++)
Rivest                                                         [Page 15]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
output[i] = input[i];
}
/* Note: Replace "for loop" with standard memset if possible.
*/
static void MD5_memset (output, value, len)
POINTER output;
int value;
unsigned int len;
{
unsigned int i;
for (i = 0; i < len; i++)
((char *)output)[i] = (char)value;
}
A.4 mddriver.c
/* MDDRIVER.C - test driver for MD2, MD4 and MD5
*/
/* Copyright (C) 1990-2, RSA Data Security, Inc. Created 1990. All
rights reserved.
RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.
These notices must be retained in any copies of any part of this
documentation and/or software.
*/
/* The following makes MD default to MD5 if it has not already been
defined with C compiler flags.
*/
#ifndef MD
#define MD MD5
#endif
#include 
#include 
#include 
#include "global.h"
#if MD == 2
#include "md2.h"
#endif
#if MD == 4
Rivest                                                         [Page 16]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
#include "md4.h"
#endif
#if MD == 5
#include "md5.h"
#endif
/* Length of test block, number of test blocks.
*/
#define TEST_BLOCK_LEN 1000
#define TEST_BLOCK_COUNT 1000
static void MDString PROTO_LIST ((char *));
static void MDTimeTrial PROTO_LIST ((void));
static void MDTestSuite PROTO_LIST ((void));
static void MDFile PROTO_LIST ((char *));
static void MDFilter PROTO_LIST ((void));
static void MDPrint PROTO_LIST ((unsigned char [16]));
#if MD == 2
#define MD_CTX MD2_CTX
#define MDInit MD2Init
#define MDUpdate MD2Update
#define MDFinal MD2Final
#endif
#if MD == 4
#define MD_CTX MD4_CTX
#define MDInit MD4Init
#define MDUpdate MD4Update
#define MDFinal MD4Final
#endif
#if MD == 5
#define MD_CTX MD5_CTX
#define MDInit MD5Init
#define MDUpdate MD5Update
#define MDFinal MD5Final
#endif
/* Main driver.
Arguments (may be any combination):
-sstring - digests string
-t       - runs time trial
-x       - runs test script
filename - digests file
(none)   - digests standard input
*/
int main (argc, argv)
int argc;
Rivest                                                         [Page 17]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
char *argv[];
{
int i;
if (argc > 1)
for (i = 1; i < argc; i++)
if (argv[i][0] == '-' && argv[i][1] == 's')
MDString (argv[i] + 2);
else if (strcmp (argv[i], "-t") == 0)
MDTimeTrial ();
else if (strcmp (argv[i], "-x") == 0)
MDTestSuite ();
else
MDFile (argv[i]);
else
MDFilter ();
return (0);
}
/* Digests a string and prints the result.
*/
static void MDString (string)
char *string;
{
MD_CTX context;
unsigned char digest[16];
unsigned int len = strlen (string);
MDInit (&context);
MDUpdate (&context, string, len);
MDFinal (digest, &context);
printf ("MD%d (\"%s\") = ", MD, string);
MDPrint (digest);
printf ("\n");
}
/* Measures the time to digest TEST_BLOCK_COUNT TEST_BLOCK_LEN-byte
blocks.
*/
static void MDTimeTrial ()
{
MD_CTX context;
time_t endTime, startTime;
unsigned char block[TEST_BLOCK_LEN], digest[16];
unsigned int i;
Rivest                                                         [Page 18]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
printf
("MD%d time trial. Digesting %d %d-byte blocks ...", MD,
TEST_BLOCK_LEN, TEST_BLOCK_COUNT);
/* Initialize block */
for (i = 0; i < TEST_BLOCK_LEN; i++)
block[i] = (unsigned char)(i & 0xff);
/* Start timer */
time (&startTime);
/* Digest blocks */
MDInit (&context);
for (i = 0; i < TEST_BLOCK_COUNT; i++)
MDUpdate (&context, block, TEST_BLOCK_LEN);
MDFinal (digest, &context);
/* Stop timer */
time (&endTime);
printf (" done\n");
printf ("Digest = ");
MDPrint (digest);
printf ("\nTime = %ld seconds\n", (long)(endTime-startTime));
printf
("Speed = %ld bytes/second\n",
(long)TEST_BLOCK_LEN * (long)TEST_BLOCK_COUNT/(endTime-startTime));
}
/* Digests a reference suite of strings and prints the results.
*/
static void MDTestSuite ()
{
printf ("MD%d test suite:\n", MD);
MDString ("");
MDString ("a");
MDString ("abc");
MDString ("message digest");
MDString ("abcdefghijklmnopqrstuvwxyz");
MDString
("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
MDString
("1234567890123456789012345678901234567890\
1234567890123456789012345678901234567890");
}
/* Digests a file and prints the result.
Rivest                                                         [Page 19]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
*/
static void MDFile (filename)
char *filename;
{
FILE *file;
MD_CTX context;
int len;
unsigned char buffer[1024], digest[16];
if ((file = fopen (filename, "rb")) == NULL)
printf ("%s can't be opened\n", filename);
else {
MDInit (&context);
while (len = fread (buffer, 1, 1024, file))
MDUpdate (&context, buffer, len);
MDFinal (digest, &context);
fclose (file);
printf ("MD%d (%s) = ", MD, filename);
MDPrint (digest);
printf ("\n");
}
}
/* Digests the standard input and prints the result.
*/
static void MDFilter ()
{
MD_CTX context;
int len;
unsigned char buffer[16], digest[16];
MDInit (&context);
while (len = fread (buffer, 1, 16, stdin))
MDUpdate (&context, buffer, len);
MDFinal (digest, &context);
MDPrint (digest);
printf ("\n");
}
/* Prints a message digest in hexadecimal.
*/
static void MDPrint (digest)
unsigned char digest[16];
{
Rivest                                                         [Page 20]
RFC 1321              MD5 Message-Digest Algorithm            April 1992
unsigned int i;
for (i = 0; i < 16; i++)
printf ("%02x", digest[i]);
}
A.5 Test suite
The MD5 test suite (driver option "-x") should print the following
results:
MD5 test suite:
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("123456789012345678901234567890123456789012345678901234567890123456
78901234567890") = 57edf4a22be3c955ac49da2e2107b67a
Security Considerations
The level of security discussed in this memo is considered to be
sufficient for implementing very high security hybrid digital-
signature schemes based on MD5 and a public-key cryptosystem.
Author's Address
Ronald L. Rivest
Massachusetts Institute of Technology
Laboratory for Computer Science
NE43-324
545 Technology Square
Cambridge, MA  02139-1986
Phone: (617) 253-5880
EMail: rivest@theory.lcs.mit.edu
Rivest                                                         [Page 21]

bilicon 2007-08-03 12:35 发表评论

[zt]MD5算法原理

bilicon — Fri, 03 Aug 2007 04:34:00 GMT

综述

    md5的全称是message-digest algorithm 5（信息-摘要算法），在90年代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest开发出来，经md2、md3和md4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被"压缩"成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。不管是md2、md4还是md5，它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似，但md2的设计与md4和md5完全不同，那是因为md2是为8位机器做过设计优化的，而md4和md5却是面向32位的电脑。这三个算法的描述和c语言源代码在internet rfcs 1321中有详细的描述（http://www.ietf.org/rfc/rfc1321.txt），这是一份最权威的文档，由ronald l. rivest在1992年8月向ieft提交。

    rivest在1989年开发出md2算法。在这个算法中，首先对信息进行数据补位，使信息的字节长度是16的倍数。然后，以一个16位的检验和追加到信息末尾。并且根据这个新产生的信息计算出散列值。后来，rogier和chauvaud发现如果忽略了检验和将产生md2冲突。md2算法的加密后结果是唯一的--既没有重复。

    为了加强算法的安全性，rivest在1990年又开发出md4算法。md4算法同样需要填补信息以确保信息的字节长度加上448后能被512整除（信息字节长度mod 512 = 448）。然后，一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位damg?rd/merkle迭代结构的区块，而且每个区块要通过三个不同步骤的处理。den boer和bosselaers以及其他人很快的发现了攻击md4版本中第一步和第三步的漏洞。dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到md4完整版本中的冲突（这个冲突实际上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后结果）。毫无疑问，md4就此被淘汰掉了。

    尽管md4算法在安全上有个这么大的漏洞，但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了md5以外，其中比较有名的还有sha-1、ripe-md以及haval等。

    一年以后，即1991年，rivest开发出技术上更为趋近成熟的md5算法。它在md4的基础上增加了"安全-带子"（safety-belts）的概念。虽然md5比md4稍微慢一些，但却更为安全。这个算法很明显的由四个和md4设计有少许不同的步骤组成。在md5算法中，信息-摘要的大小和填充的必要条件与md4完全相同。den boer和bosselaers曾发现md5算法中的假冲突（pseudo-collisions），但除此之外就没有其他被发现的加密后结果了。

    van oorschot和wiener曾经考虑过一个在散列中暴力搜寻冲突的函数（brute-force hash function），而且他们猜测一个被设计专门用来搜索md5冲突的机器（这台机器在1994年的制造成本大约是一百万美元）可以平均每24天就找到一个冲突。但单从1991年到2001年这10年间，竟没有出现替代md5算法的md6或被叫做其他什么名字的新算法这一点，我们就可以看出这个瑕疵并没有太多的影响md5的安全性。上面所有这些都不足以成为md5的在实际应用中的问题。并且，由于md5算法的使用不需要支付任何版权费用的，所以在一般的情况下（非绝密应用领域。但即便是应用在绝密领域内，md5也不失为一种非常优秀的中间技术），md5怎么都应该算得上是非常安全的了。

算法的应用

    md5的典型应用是对一段信息（message）产生信息摘要（message-digest），以防止被篡改。比如，在unix下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：

    md5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461

    这就是tanajiya.tar.gz文件的数字签名。md5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的md5信息摘要。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改或者下载过程中线路不稳定引起的传输错误等），只要你对这个文件重新计算md5时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构，用md5还可以防止文件作者的"抵赖"，这就是所谓的数字签名应用。

    md5还广泛用于加密和解密技术上。比如在unix系统中用户的密码就是以md5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成md5值，然后再去和保存在文件系统中的md5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。

    正是因为这个原因，现在被黑客使用最多的一种破译密码的方法就是一种被称为"跑字典"的方法。有两种方法得到字典，一种是日常搜集的用做密码的字符串表，另一种是用排列组合方法生成的，先用md5程序计算出这些字典项的md5值，然后再用目标的md5值在这个字典中检索。我们假设密码的最大长度为8位字节（8 bytes），同时密码只能是字母和数字，共26+26+10=62个字符，排列组合出的字典的项数则是p(62,1)+p(62,2)….+p(62,8)，那也已经是一个很天文的数字了，存储这个字典就需要tb级的磁盘阵列，而且这种方法还有一个前提，就是能获得目标账户的密码md5值的情况下才可以。这种加密技术被广泛的应用于unix系统中，这也是为什么unix系统比一般操作系统更为坚固一个重要原因。

算法描述

    对md5算法简要的叙述可以为：md5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

    在md5算法中，首先需要对信息进行填充，使其字节长度对512求余的结果等于448。因此，信息的字节长度（bits length）将被扩展至n*512+448，即n*64+56个字节（bytes），n为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，现在的信息字节长度=n*512+448+64=(n+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。

    md5中有四个32位被称作链接变量（chaining variable）的整数参数，他们分别为：a=0x01234567，b=0x89abcdef，c=0xfedcba98，d=0x76543210。

    当设置好这四个链接变量后，就开始进入算法的四轮循环运算。循环的次数是信息中512位信息分组的数目。

    将上面四个链接变量复制到另外四个变量中：a到a，b到b，c到c，d到d。

    主循环有四轮（md4只有三轮），每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。
    以一下是每次操作中用到的四个非线性函数（每轮一个）。

    f(x,y,z) =(x&y)|((~x)&z)
    g(x,y,z) =(x&z)|(y&(~z))
    h(x,y,z) =x^y^z
    i(x,y,z)=y^(x|(~z))
    （&是与，|是或，~是非，^是异或）

    这四个函数的说明：如果x、y和z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。
    f是一个逐位运算的函数。即，如果x，那么y，否则z。函数h是逐位奇偶操作符。

    假设mj表示消息的第j个子分组（从0到15），<<
    ff(a,b,c,d,mj,s,ti)表示a=b+((a+(f(b,c,d)+mj+ti)<< gg(a,b,c,d,mj,s,ti)表示a=b+((a+(g(b,c,d)+mj+ti)<< hh(a,b,c,d,mj,s,ti)表示a=b+((a+(h(b,c,d)+mj+ti)<< ii(a,b,c,d,mj,s,ti)表示a=b+((a+(i(b,c,d)+mj+ti)<<
    这四轮（64步）是：

    第一轮

    ff(a,b,c,d,m0,7,0xd76aa478)
    ff(d,a,b,c,m1,12,0xe8c7b756)
    ff(c,d,a,b,m2,17,0x242070db)
    ff(b,c,d,a,m3,22,0xc1bdceee)
    ff(a,b,c,d,m4,7,0xf57c0faf)
    ff(d,a,b,c,m5,12,0x4787c62a)
    ff(c,d,a,b,m6,17,0xa8304613)
    ff(b,c,d,a,m7,22,0xfd469501)
    ff(a,b,c,d,m8,7,0x698098d8)
    ff(d,a,b,c,m9,12,0x8b44f7af)
    ff(c,d,a,b,m10,17,0xffff5bb1)
    ff(b,c,d,a,m11,22,0x895cd7be)
    ff(a,b,c,d,m12,7,0x6b901122)
    ff(d,a,b,c,m13,12,0xfd987193)
    ff(c,d,a,b,m14,17,0xa679438e)
    ff(b,c,d,a,m15,22,0x49b40821)

    第二轮

    gg(a,b,c,d,m1,5,0xf61e2562)
    gg(d,a,b,c,m6,9,0xc040b340)
    gg(c,d,a,b,m11,14,0x265e5a51)
    gg(b,c,d,a,m0,20,0xe9b6c7aa)
    gg(a,b,c,d,m5,5,0xd62f105d)
    gg(d,a,b,c,m10,9,0x02441453)
    gg(c,d,a,b,m15,14,0xd8a1e681)
    gg(b,c,d,a,m4,20,0xe7d3fbc8)
    gg(a,b,c,d,m9,5,0x21e1cde6)
    gg(d,a,b,c,m14,9,0xc33707d6)
    gg(c,d,a,b,m3,14,0xf4d50d87)
    gg(b,c,d,a,m8,20,0x455a14ed)
    gg(a,b,c,d,m13,5,0xa9e3e905)
    gg(d,a,b,c,m2,9,0xfcefa3f8)
    gg(c,d,a,b,m7,14,0x676f02d9)
    gg(b,c,d,a,m12,20,0x8d2a4c8a)

    第三轮

    hh(a,b,c,d,m5,4,0xfffa3942)
    hh(d,a,b,c,m8,11,0x8771f681)
    hh(c,d,a,b,m11,16,0x6d9d6122)
    hh(b,c,d,a,m14,23,0xfde5380c)
    hh(a,b,c,d,m1,4,0xa4beea44)
    hh(d,a,b,c,m4,11,0x4bdecfa9)
    hh(c,d,a,b,m7,16,0xf6bb4b60)
    hh(b,c,d,a,m10,23,0xbebfbc70)
    hh(a,b,c,d,m13,4,0x289b7ec6)
    hh(d,a,b,c,m0,11,0xeaa127fa)
    hh(c,d,a,b,m3,16,0xd4ef3085)
    hh(b,c,d,a,m6,23,0x04881d05)
    hh(a,b,c,d,m9,4,0xd9d4d039)
    hh(d,a,b,c,m12,11,0xe6db99e5)
    hh(c,d,a,b,m15,16,0x1fa27cf8)
    hh(b,c,d,a,m2,23,0xc4ac5665)

    第四轮

    ii(a,b,c,d,m0,6,0xf4292244)
    ii(d,a,b,c,m7,10,0x432aff97)
    ii(c,d,a,b,m14,15,0xab9423a7)
    ii(b,c,d,a,m5,21,0xfc93a039)
    ii(a,b,c,d,m12,6,0x655b59c3)
    ii(d,a,b,c,m3,10,0x8f0ccc92)
    ii(c,d,a,b,m10,15,0xffeff47d)
    ii(b,c,d,a,m1,21,0x85845dd1)
    ii(a,b,c,d,m8,6,0x6fa87e4f)
    ii(d,a,b,c,m15,10,0xfe2ce6e0)
    ii(c,d,a,b,m6,15,0xa3014314)
    ii(b,c,d,a,m13,21,0x4e0811a1)
    ii(a,b,c,d,m4,6,0xf7537e82)
    ii(d,a,b,c,m11,10,0xbd3af235)
    ii(c,d,a,b,m2,15,0x2ad7d2bb)
    ii(b,c,d,a,m9,21,0xeb86d391)

    常数ti可以如下选择：

    在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度。(4294967296等于2的32次方)
    所有这些完成之后，将a、b、c、d分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是a、b、c和d的级联。

    当你按照我上面所说的方法实现md5算法以后，你可以用以下几个信息对你做出来的程序作一个简单的测试，看看程序有没有错误。

    md5 ("") = d41d8cd98f00b204e9800998ecf8427e
    md5 ("a") = 0cc175b9c0f1b6a831c399e269772661
    md5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
    md5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
    md5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
    md5 ("abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789") =
    d174ab98d277d9f5a5611c2c9f419d9f
    md5 ("123456789012345678901234567890123456789012345678901234567890123456789
    01234567890") = 57edf4a22be3c955ac49da2e2107b67a

    如果你用上面的信息分别对你做的md5算法实例做测试，最后得出的结论和标准答案完全一样，那我就要在这里象你道一声祝贺了。要知道，我的程序在第一次编译成功的时候是没有得出和上面相同的结果的。


md5的安全性

    md5相对md4所作的改进：
    1. 增加了第四轮；
    2. 每一步均有唯一的加法常数；
    3. 为减弱第二轮中函数g的对称性从(x&y)|(x&z)|(y&z)变为(x&z)|(y&(~z))；
    4. 第一步加上了上一步的结果，这将引起更快的雪崩效应；
    5. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不相似；
    6. 近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应。各轮的位移量互不相同。

bilicon 2007-08-03 12:34 发表评论

[转]使用CPU时间戳进行高精度计时

bilicon — Thu, 26 Jul 2007 02:57:00 GMT

对关注性能的程序开发人员而言，一个好的计时部件既是益友，也是良师。计时器既可以作为程序组件帮助程序员精确的控制程序进程，又是一件有力的调试武器，在有经验的程序员手里可以尽快的确定程序的性能瓶颈，或者对不同的算法作出有说服力的性能比较。
在Windows平台下，常用的计时器有两种，一种是timeGetTime多媒体计时器，它可以提供毫秒级的计时。但这个精度对很多应用场合而言还是太粗糙了。另一种是QueryPerformanceCount计数器，随系统的不同可以提供微秒级的计数。对于实时图形处理、多媒体数据流处理、或者实时系统构造的程序员，善用QueryPerformanceCount/QueryPerformanceFrequency是一项基本功。
本文要介绍的，是另一种直接利用Pentium CPU内部时间戳进行计时的高精度计时手段。以下讨论主要得益于《Windows图形编程》一书，第15页－17页，有兴趣的读者可以直接参考该书。关于RDTSC指令的详细讨论，可以参考Intel产品手册。本文仅仅作抛砖之用。

在Intel Pentium以上级别的CPU中，有一个称为“时间戳（Time Stamp）”的部件，它以64位无符号整型数的格式，记录了自CPU上电以来所经过的时钟周期数。由于目前的CPU主频都非常高，因此这个部件可以达到纳秒级的计时精度。这个精确性是上述两种方法所无法比拟的。
在Pentium以上的CPU中，提供了一条机器指令RDTSC（Read Time Stamp Counter）来读取这个时间戳的数字，并将其保存在EDX:EAX寄存器对中。由于EDX:EAX寄存器对恰好是Win32平台下C++语言保存函数返回值的寄存器，所以我们可以把这条指令看成是一个普通的函数调用。像这样：

inline unsigned __int64 GetCycleCount()
{
__asm RDTSC
}

但是不行，因为RDTSC不被C++的内嵌汇编器直接支持，所以我们要用_emit伪指令直接嵌入该指令的机器码形式0X0F、0X31，如下：

inline unsigned __int64 GetCycleCount()
{
__asm _emit 0x0F
__asm _emit 0x31
}

以后在需要计数器的场合，可以像使用普通的Win32 API一样，调用两次GetCycleCount函数，比较两个返回值的差，像这样：

unsigned long t;
t = (unsigned long)GetCycleCount();
//Do Something time-intensive ...
t -= (unsigned long)GetCycleCount();

《Windows图形编程》第15页编写了一个类，把这个计数器封装起来。有兴趣的读者可以去参考那个类的代码。作者为了更精确的定时，做了一点小小的改进，把执行RDTSC指令的时间，通过连续两次调用GetCycleCount函数计算出来并保存了起来，以后每次计时结束后，都从实际得到的计数中减掉这一小段时间，以得到更准确的计时数字。但我个人觉得这一点点改进意义不大。在我的机器上实测，这条指令大概花掉了几十到100多个周期，在Celeron 800MHz的机器上，这不过是十分之一微秒的时间。对大多数应用来说，这点时间完全可以忽略不计；而对那些确实要精确到纳秒数量级的应用来说，这个补偿也过于粗糙了。

这个方法的优点是：
1.高精度。可以直接达到纳秒级的计时精度（在1GHz的CPU上每个时钟周期就是一纳秒），这是其他计时方法所难以企及的。
2.成本低。timeGetTime 函数需要链接多媒体库winmm.lib，QueryPerformance* 函数根据MSDN的说明，需要硬件的支持（虽然我还没有见过不支持的机器）和KERNEL库的支持，所以二者都只能在Windows平台下使用（关于DOS平台下的高精度计时问题，可以参考《图形程序开发人员指南》，里面有关于控制定时器8253的详细说明）。但RDTSC指令是一条CPU指令，凡是i386平台下Pentium以上的机器均支持，甚至没有平台的限制（我相信i386版本UNIX和Linux下这个方法同样适用，但没有条件试验），而且函数调用的开销是最小的。
3.具有和CPU主频直接对应的速率关系。一个计数相当于1/(CPU主频Hz数)秒，这样只要知道了CPU的主频，可以直接计算出时间。这和QueryPerformanceCount不同，后者需要通过QueryPerformanceFrequency获取当前计数器每秒的计数次数才能换算成时间。

这个方法的缺点是：
1.现有的C/C++编译器多数不直接支持使用RDTSC指令，需要用直接嵌入机器码的方式编程，比较麻烦。
2.数据抖动比较厉害。其实对任何计量手段而言，精度和稳定性永远是一对矛盾。如果用低精度的timeGetTime来计时，基本上每次计时的结果都是相同的；而RDTSC指令每次结果都不一样，经常有几百甚至上千的差距。这是这种方法高精度本身固有的矛盾。

关于这个方法计时的最大长度，我们可以简单的用下列公式计算：

自CPU上电以来的秒数 = RDTSC读出的周期数 / CPU主频速率（Hz）

64位无符号整数所能表达的最大数字是1.8×10^19，在我的Celeron 800上可以计时大约700年（书中说可以在200MHz的Pentium上计时117年，这个数字不知道是怎么得出来的，与我的计算有出入）。无论如何，我们大可不必关心溢出的问题。

下面是几个小例子，简要比较了三种计时方法的用法与精度
//Timer1.cpp 使用了RDTSC指令的Timer类//KTimer类的定义可以参见《Windows图形编程》P15
//编译行：CL Timer1.cpp /link USER32.lib
#include
#include "KTimer.h"
main()
{
unsigned t;
KTimer timer;
timer.Start();
Sleep(1000);
t = timer.Stop();
printf("Lasting Time: %d\n",t);
}

//Timer2.cpp 使用了timeGetTime函数
//需包含，但由于Windows头文件错综复杂的关系
//简单包含比较偷懒：）
//编译行：CL timer2.cpp /link winmm.lib
#include
#include

main()
{
DWORD t1, t2;
t1 = timeGetTime();
Sleep(1000);
t2 = timeGetTime();
printf("Begin Time: %u\n", t1);
printf("End Time: %u\n", t2);
printf("Lasting Time: %u\n",(t2-t1));
}

//Timer3.cpp 使用了QueryPerformanceCounter函数
//编译行：CL timer3.cpp /link KERNEl32.lib
#include
#include

main()
{
LARGE_INTEGER t1, t2, tc;
QueryPerformanceFrequency(&tc);
printf("Frequency: %u\n", tc.QuadPart);
QueryPerformanceCounter(&t1);
Sleep(1000);
QueryPerformanceCounter(&t2);
printf("Begin Time: %u\n", t1.QuadPart);
printf("End Time: %u\n", t2.QuadPart);
printf("Lasting Time: %u\n",( t2.QuadPart- t1.QuadPart));
}

////////////////////////////////////////////////
//以上三个示例程序都是测试1秒钟休眠所耗费的时间

bilicon 2007-07-26 10:57 发表评论

[zt]P2P之UDP穿透NAT的原理与实现(shootingstars)--增强篇(附源代码)

bilicon — Fri, 13 Apr 2007 04:00:00 GMT

源码下载: http://www.ppcn.net/upload/2005_08/05080112299104.rar 参考： http://midcom-p2p.sourceforge.net/draft-ford-midcom-p2p-01.txt

P2P之UDP穿透NAT的原理与实现(shootingstars)

文章说明:

关于UDP穿透NAT的中文资料在网络上是很少的，仅有<rs)>>这篇文章有实际的参考价值。本人近两年来也一直从事P2P方面的开发工作，比较有代表性的是个人开发的BitTorrent下载软件 - FlashBT(变态快车). 对P2P下载或者P2P的开发感兴趣的朋友可以访问软件的官方主页: http://www.hwysoft.com/chs/ 下载看看，说不定有收获。写这篇文章的主要目的是懒的再每次单独回答一些网友的提问, 一次性写下来, 即节省了自己的时间，也方便了对于P2P的UDP穿透感兴趣的网友阅读和理解。对此有兴趣和经验的朋友可以给我发邮件或者访问我的个人Blog留言: http://hwycheng.blogchina.com. 您可以自由转载此篇文章，但是请保留此说明。

再次感谢shootingstars网友的早期贡献. 表示谢意。

NAT(The IP Network Address Translator) 的概念和意义是什么?

NAT, 中文翻译为网络地址转换。具体的详细信息可以访问RFC 1631 - http://www.faqs.org/rfcs/rfc1631.html, 这是对于NAT的定义和解释的最权威的描述。网络术语都是很抽象和艰涩的，除非是专业人士，否则很难从字面中来准确理解NAT的含义。

要想完全明白NAT 的作用，我们必须理解IP地址的两大分类，一类是私有IP地址，在这里我们称作内网IP地址。一类是非私有的IP地址，在这里我们称作公网IP地址。关于IP地址的概念和作用的介绍参见我的另一篇文章: http://hwycheng.blogchina.com/2402121.html

内网IP地址: 是指使用A/B/C类中的私有地址, 分配的IP地址在全球不惧有唯一性，也因此无法被其它外网主机直接访问。公网IP地址: 是指具有全球唯一的IP地址，能够直接被其它主机访问的。

NAT 最初的目的是为使用内网IP地址的计算机提供通过少数几台具有公网的IP地址的计算机访问外部网络的功能。NAT 负责将某些内网IP地址的计算机向外部网络发出的IP数据包的源IP地址转换为NAT自己的公网的IP地址，目的IP地址不变, 并将IP数据包转发给路由器，最终到达外部的计算机。同时负责将外部的计算机返回的IP数据包的目的IP地址转换为内网的IP地址，源IP地址不变，并最终送达到内网中的计算机。

图一: NAT 实现了私有IP的计算机分享几个公网IP地址访问Internet的功能。

随着网络的普及，IPv4的局限性暴露出来。公网IP地址成为一种稀缺的资源，此时NAT 的功能局限也暴露出来，同一个公网的IP地址，某个时间只能由一台私有IP地址的计算机使用。于是NAPT(The IP Network Address/Port Translator)应运而生，NAPT实现了多台私有IP地址的计算机可以同时通过一个公网IP地址来访问Internet的功能。这在很大程度上暂时缓解了IPv4地址资源的紧张。

NAPT 负责将某些内网IP地址的计算机向外部网络发出的TCP/UDP数据包的源IP地址转换为NAPT自己的公网的IP地址，源端口转为NAPT自己的一个端口。目的IP地址和端口不变, 并将IP数据包发给路由器，最终到达外部的计算机。同时负责将外部的计算机返回的IP数据包的目的IP地址转换内网的IP地址，目的端口转为内网计算机的端口，源IP地址和源端口不变，并最终送达到内网中的计算机。

图二: NAPT 实现了私有IP的计算机分享一个公网IP地址访问Internet的功能。

在我们的工作和生活中, NAPT的作用随处可见，绝大部分公司的网络架构，都是通过1至N台支持NAPT的路由器来实现公司的所有计算机连接外部的Internet网络的。包括本人在写这篇文章的时候，也是在家中使用一台IBM笔记本通过一台宽带连接的台式机来访问Internet的。我们本篇文章主要讨论的NAPT的问题。

NAPT(The IP Network Address/Port Translator) 为何阻碍了P2P软件的应用?

通过NAPT 上网的特点决定了只能由NAPT内的计算机主动向NAPT外部的主机发起连接，外部的主机想直接和NAPT内的计算机直接建立连接是不被允许的。IM(即时通讯)而言，这意味着由于NAPT内的计算机和NAPT外的计算机只能通过服务器中转数据来进行通讯。对于P2P方式的下载程序而言，意味着NAPT内的计算机不能接收到NAPT外部的连接，导致连接数用过少，下载速度很难上去。因此P2P软件必须要解决的一个问题就是要能够在一定的程度上解决NAPT内的计算机不能被外部连接的问题。

NAT(The IP Network Address Translator) 进行UDP穿透的原理是什么?

TCP/IP传输时主要用到TCP和UDP协议。TCP协议是可靠的，面向连接的传输协议。UDP是不可靠的，无连接的协议。根据TCP和UDP协议的实现原理，对于NAPT来进行穿透，主要是指的UDP协议。TCP协议也有可能，但是可行性非常小，要求更高，我们此处不作讨论，如果感兴趣可以到Google上搜索，有些文章对这个问题做了探讨性的描述。下面我们来看看利用UDP协议来穿透NAPT的原理是什么:

图三: NAPT 是如何将私有IP地址的UDP数据包与公网主机进行透明传输的。

UDP协议包经NAPT透明传输的说明:

NAPT为每一个Session分配一个NAPT自己的端口号，依据此端口号来判断将收到的公网IP主机返回的TCP/IP数据包转发给那台内网IP地址的计算机。在这里Session是虚拟的，UDP通讯并不需要建立连接，但是对于NAPT而言，的确要有一个Session的概念存在。NAPT对于UDP协议包的透明传输面临的一个重要的问题就是如何处理这个虚拟的Session。我们都知道TCP连接的Session以SYN包开始，以FIN包结束，NAPT可以很容易的获取到TCP Session的生命周期，并进行处理。但是对于UDP而言，就麻烦了，NAPT并不知道转发出去的UDP协议包是否到达了目的主机，也没有办法知道。而且鉴于UDP协议的特点，可靠很差，因此NAPT必须强制维持Session的存在，以便等待将外部送回来的数据并转发给曾经发起请求的内网IP地址的计算机。NAPT具体如何处理UDP Session的超时呢？不同的厂商提供的设备对于NAPT的实现不近相同，也许几分钟，也许几个小时，些NAPT的实现还会根据设备的忙碌状态进行智能计算超时时间的长短。

图四: NAPT 将内部发出的UDP协议包的源地址和源端口改变传输给公网IP主机。

图五: NAPT 将收到的公网IP主机返回的UDP协议包的目的地址和目的端口改变传输给内网IP计算机现在我们大概明白了NAPT如何实现内网计算机和外网主机间的透明通讯。现在来看一下我们最关心的问题，就是NAPT是依据什么策略来判断是否要为一个请求发出的UDP数据包建立Session的呢？主要有一下几个策略:

A. 源地址(内网IP地址)不同，忽略其它因素, 在NAPT上肯定对应不同的Session B. 源地址(内网IP地址)相同，源端口不同，忽略其它的因素，则在NAPT上也肯定对应不同的Session C. 源地址(内网IP地址)相同，源端口相同，目的地址(公网IP地址)相同，目的端口不同，则在NAPT上肯定对应同一个Session D. 源地址(内网IP地址)相同，源端口相同，目的地址(公网IP地址)不同，忽略目的端口，则在NAPT上是如何处理Session的呢？

D的情况正式我们关心和要讨论的问题。依据目的地址(公网IP地址)对于Session的建立的决定方式我们将NAPT设备划分为两大类:

Symmetric NAPT: 对于到同一个IP地址，任意端口的连接分配使用同一个Session; 对于到不同的IP地址, 任意端口的连接使用不同的Session. 我们称此种NAPT为 Symmetric NAPT. 也就是只要本地绑定的UDP端口相同，发出的目的IP地址不同，则会建立不同的Session.

图六: Symmetric 的英文意思是对称。多个端口对应多个主机，平行的，对称的!

Cone NAPT: 对于到同一个IP地址，任意端口的连接分配使用同一个Session; 对于到不同的IP地址，任意端口的连接也使用同一个Session. 我们称此种NAPT为 Cone NAPT. 也就是只要本地绑定的UDP端口相同，发出的目的地址不管是否相同，都使用同一个Session.

图七: Cone 的英文意思是锥。一个端口对应多个主机，是不是像个锥子?

现在绝大多数的NAPT属于后者，即Cone NAT。本人在测试的过程中，只好使用了一台日本的Symmetric NAT。还好不是自己的买的，我从不买日货, 希望看这篇文章的朋友也自觉的不要购买日本的东西。Win9x/2K/XP/2003系统自带的NAPT也是属于 Cone NAT的。这是值的庆幸的，因为我们要做的UDP穿透只能在Cone NAT间进行，只要有一台不是Cone NAT，对不起，UDP穿透没有希望了，服务器转发吧。后面会做详细分析!

下面我们再来分析一下NAPT 工作时的一些数据结构，在这里我们将真正说明UDP可以穿透Cone NAT的依据。这里描述的数据结构只是为了说明原理，不具有实际参考价值，真正感兴趣可以阅读Linux的中关于NAT实现部分的源码。真正的NAT实现也没有利用数据库的，呵呵，为了速度！

Symmetric NAPT 工作时的端口映射数据结构如下:

内网信息表:

[NAPT 分配端口] [ 内网IP地址 ] [ 内网端口 ] [ 外网IP地址 ] [ SessionTime 开始时间 ]

PRIMARY KEY( [NAPT 分配端口] ) -> 表示依据[NAPT 分配端口]建立主键，必须唯一且建立索引，加快查找. UNIQUE( [ 内网IP地址 ], [ 内网端口 ] ) -> 表示这两个字段联合起来不能重复. UNIQUE( [ 内网IP地址 ], [ 内网端口 ], [ 外网IP地址 ] ) -> 表示这三个字段联合起来不能重复.

映射表:

[NAPT 分配端口] [ 外网端口 ]

UNIQUE( [NAPT 分配端口], [ 外网端口 ] ) -> 表示这两个字段联合起来不能重复.

Cone NAPT 工作时的端口映射数据结构如下:

内网信息表:

[NAPT 分配端口] [ 内网IP地址 ] [ 内网端口 ] [ SessionTime 开始时间 ]

PRIMARY KEY( [NAPT 分配端口] ) -> 表示依据[NAPT 分配端口]建立主键，必须唯一且建立索引，加快查找. UNIQUE( [ 内网IP地址 ], [ 内网端口 ] ) -> 表示这两个字段联合起来不能重复.

外网信息表:

[ wid 主键标识 ] [ 外网IP地址 ] [ 外网端口 ]

PRIMARY KEY( [ wid 主键标识 ] ) -> 表示依据[ wid 主键标识 ]建立主键，必须唯一且建立索引，加快查找. UNIQUE( [ 外网IP地址 ], [ 外网端口 ] ) -> 表示这两个字段联合起来不能重复.

映射表: 实现一对多，的

[NAPT 分配端口] [ wid 主键标识 ]

UNIQUE( [NAPT 分配端口], [ wid 主键标识 ] ) -> 表示这两个字段联合起来不能重复. UNIQUE( [ wid 主键标识 ] ) -> 标识此字段不能重复.

看完了上面的数据结构是更明白了还是更晕了？呵呵! 多想一会儿就会明白了。通过NAT,内网计算机计算机向外连结是很容易的，NAPT会自动处理，我们的应用程序根本不必关心它是如何处理的。那么外部的计算机想访问内网中的计算机如何实现呢？我们来看一下下面的流程：

c 是一台在NAPT后面的内网计算机，s是一台有外网IP地址的计算机。c 主动向 s 发起连接请求，NAPT依据上面描述的规则在自己的数据结构中记录下来，建立一个Session. 然后 c 和 s 之间就可以实现双向的透明的数据传输了。如下面所示:

  c[192.168.0.6:1827] <-> [priv ip: 
192.168.0.1]NAPT[pub ip: 61.51.99.86:9881] <-> s[61.51.76.102:8098]

由此可见，一台外网IP地址的计算机想和NAPT后面的内网计算机通讯的条件就是要求NAPT后面的内网计算机主动向外网IP地址的计算机发起一个UDP数据包。外网IP地址的计算机利用收到的UDP数据包获取到NAPT的外网IP地址和映射的端口，以后就可以和内网IP的计算机透明的进行通讯了。

现在我们再来分析一下我们最关心的两个NAPT后面的内网计算机如何实现直接通讯呢? 两者都无法主动发出连接请求，谁也不知道对方的NAPT的公网IP地址和NAPT上面映射的端口号。所以我们要靠一个公网IP地址的服务器帮助两者来建立连接。当两个NAPT后面的内网计算机分别连接了公网IP地址的服务器后，服务器可以从收到的UDP数据包中获取到这两个NAPT设备的公网IP地址和这两个连接建立的Session的映射端口。两个内网计算机可以从服务器上获取到对方的NAPT设备公网IP地址和映射的端口了。

我们假设两个内网计算机分别为A和B，对应的NAPT分别为AN和 BN，如果A在获取到B对应的BN的IP地址和映射的端口后，迫不急待的向这个IP 地址和映射的端口发送了个UDP数据包，会有什么情况发生呢？依据上面的原理和数据结构我们会知道，AN会在自己的数据结构中生成一条记录，标识一个新Session的存在。BN在收到数据包后，从自己的数据结构中查询，没有找到相关记录，因此将包丢弃。B是个慢性子，此时才慢吞吞的向着AN的IP地址和映射的端口发送了一个UDP数据包，结果如何呢？当然是我们期望的结构了，AN在收到数据包后，从自己的数据结构中查找到了记录，所以将数据包进行处理发送给了A。A 再次向B发送数据包时，一切都时畅通无阻了。OK, 大工告成！且慢，这时对于Cone NAPT而言，对于Symmetric NAPT呢？呵呵，自己分析一下吧...

NAPT(The IP Network Address/Port Translator) 进行UDP穿透的具体情况分析!

首先明确的将NAPT设备按照上面的说明分为: Symmetric NAPT 和 Cone NAPT, Cone NAPT 是我们需要的。Win9x/2K/XP/2003 自带的NAPT也为Cone NAPT。

第一种情况, 双方都是Symmetric NAPT:

此情况应给不存在什么问题，肯定是不支持UDP穿透。

第二种情况, 双方都是Cone NAPT:

此情况是我们需要的，可以进行UDP穿透。

第三种情况, 一个是Symmetric NAPT, 一个是Cone NAPT:

此情况比较复杂，但我们按照上面的描述和数据机构进行一下分析也很容易就会明白了, 分析如下,

假设: A -> Symmetric NAT, B -> Cone NAT

1. A 想连接 B, A 从服务器那儿获取到 B 的NAT地址和映射端口, A 通知服务器，服务器告知 B A的NAT地址和映射端口, B 向 A 发起连接，A 肯定无法接收到。此时 A 向 B 发起连接， A 对应的NAT建立了一个新的Session，分配了一个新的映射端口， B 的 NAT 接收到UDP包后，在自己的映射表中查询，无法找到映射项，因此将包丢弃了。

2. B 想连接 A, B 从服务器那儿获取到 A 的NAT地址和映射端口, B 通知服务器, 服务器告知 A B的NAT地址和映射端口,A 向 B 发起连接, A 对应的NAT建立了一个新的Session，分配了一个新的映射端口B肯定无法接收到。此时 B 向 A 发起连接, 由于 B 无法获取 A 建立的新的Session的映射端口，仍是使用服务器上获取的映射端口进行连接，因此 A 的NAT在接收到UDP包后，在自己的映射表中查询，无法找到映射项, 因此将包丢弃了。

根据以上分析，只有当连接的两端的NAT都为Cone NAT的情况下，才能进行UDP的内网穿透互联。

NAPT(The IP Network Address/Port Translator) 进行UDP穿透如何进行现实的验证和分析!

需要的网络结构如下:

三个NAT后面的内网机器，两个外网服务器。其中两台Cone NAPT，一台 Symmetric NAPT。

验证方法:

可以使用本程序提供的源码，编译，然后分别运行服务器程序和客户端。修改过后的源码增加了客户端之间直接通过IP地址和端口发送消息的命令，利用此命令，你可以手动的验证NAPT的穿透情况。为了方便操作，推荐你使用一个远程登陆软件，可以直接在一台机器上操作所有的相关的计算机，这样很方便，一个人就可以完成所有的工作了。呵呵，本人就是这么完成的。欢迎有兴趣和经验的朋友来信批评指正，共同进步。

bilicon 2007-04-13 12:00 发表评论