美女久久久久久,久久青青草原国产精品免费 ,国产精品久久国产精品99盘

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

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

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

Rijndael加密��法的介�l?

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

作�?林祝�?叶义�?杨国�?/span>

本文针对Rijndael加密��法的数学理��景，��法的架构，回合的�{换，金钥的��生，以及各种��d��破密法等�{�，做了一些简单的介绍�?/span>

一、简�?/span>

�?/span>AES ( Advanced Encryption Standard ) 的选拔中，从最初的十五个算法，到十个、五个，逐步�{�选出适合用来作�ؓ下一代加密算法的标准�?/span>Rijndael在经�q�了一番时日的考验之后�Q�也一直名列前矛。直�?st1:chsdate Year="2005" Month="10" Day="2" IsLunarDate="False" IsROCDate="False" w:st="on">十月二日�Q?/span>Rijndael才脱颖而出�Q�这��文章便是针�?/span>Rijndael作简要的介绍�?/span>

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

�?/span>Rijndael��法中定义了几个名词�Q�分�q�如下：

State�Q�在�q�算�q�程中所产生的中间��|��是一�?/span>4×Nb的矩阵，Nb可由数据长度除以32位求得，也就是把数据分割�?/span>Nb个区块�?/span>

Cipher Key�Q�用来做加密�q�算的金钥，形式是一�?/span>4×Nk的矩阵，Nk可由金钥长度除以32位求得，也就是把金钥分割�?/span>Nk�?/span>32位的子金钥�?/span>

�?/span>Rijndael��法中，�q�算的回合数(Nr)是由Nb�?/span>Nk所军_��的，回合数的变动定义如下表�?/span>

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

二�?/span>Rijndael的数学背�?/span>

�?/span>Rijndael中��用了许多字节层��的运��，而这些运��是�?/span>GF(2⁸)为基��架构。也有一些采用了4-byte的字�l�运��。在�q�部分，我们��介�l�这些基本的数学原理�?/span>

(1) GF(2⁸)的定�?/span>

假设一个字�?/span>b�?/span>b₇b₆b₅b₄b₃b₂b₁b₀�l�成�Q�我们可以把�q�些b_i惌��成一�?/span>7�ơ多��式的系敎ͼ�而这些系��C��?/span>0��是1�Q?/span>

b₇ x⁷+ b₆ x⁶+ b₅ x⁵+ b₄ x⁴+ b₃ x³+ b₂ x²+ b₁ x + b₀�Q?/span>

例如�Q?/span>(57)₁₆的二�q�制表示法�ؓ(0101,0111)₂表示成多��式�Q�则为：

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

(2) 加法

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

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

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

(3) 乘法

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

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

例如�Q?/span>

(57)₁₆�?/span>(83)₁₆ = ( x⁶+ x⁴+ x²+ x + 1)�?/span> ( 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�Q�得�?/span>b₇ x⁸+ b₆ x⁷+ b₅ x⁶+ b₄ x⁵+ b₃ x⁴+ b₂ x³+ b₁ x² + b₀x。若b₇=0�Q�不会发生溢位问题，�{�案��x��正确的；�?/span>b₇=1�Q�发生溢位问题，必须减去m(x)。我们可以把�q�种�q�算表示�?/span>xtime(x)�Q�其�q�算方式�?/span>left shift(若溢位则�?/span>(1B)₁₆�?/span>EXOR�q�算)�Q�例如：‘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’

三�?/span>Rijndael的加密架�?/span>

Rijndael加密��法是由一�?/span>initial Round Key addition�Q?/span>Nr-1个回合运��，及一�?/span>final round所�l�成。加密过�E�以C语言伪码叙述如下�Q?/span>

Rijndael(State, CipherKey)

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

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

//ExpandedKey表示每个Round使用的子金钥�?/span>

{

KeyExpansion(CipherKey, ExpandedKey);

AddRoundKey(State, ExpandedKey);

For ( i=1; i

Round(State, ExpandedKey+Nb×i);

FinalRound(State, ExpandedKey+Nb×Nr);

}

上述��法中的Key Expansion�Q�可以先行计��出来，所以加密过�E�可以简化�ؓ�Q?/span>

Rijndael(State,ExpandedKey)

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

//ExpandedKey表示每个Round使用的子金钥�?/span>

{

AddRoundKey(State,ExpandedKey);

For( i=1 ; i

{

Round(State,ExpandedKey + Nb×i) ;

}

FinalRound (State, ExpandedKey + Nb×Nr);

}

各个子运��介�l�如下�?/span>

回合转换(Round transformation)�Q?/span>

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

Round(State,RoundKey)

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

//RoundKey表示每个Round使用的子金钥�?/span>

{

ByteSub(State);

ShiftRow(State);

MixColumn(State);

AddRoundKey(State,RoundKey);

}

��法中的�l�止回合(Final round)包含下列工作��目�Q?/span>

FinalRound(State,RoundKey)

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

//RoundKey表示每个Round使用的子金钥�?/span>

{

ByteSub(State) ;

ShiftRow(State) ;

AddRoundKey(State,RoundKey);

}

以下针对每个回合转换的运��过�E�，作一个深入的介绍�Q�可以更清楚��法的过�E��?/span>

1. 字节取代转换(ByteSub transformation)�Q?/span>

字节转换是一个以字节为单位的非线性取代运��，取代�?/span>(S-Box)是经�q�两个运��过�E�而徏立，�q�且是可逆的�?/span>

首先扑և�每个字节�?/span>GF(2⁸)中的乘法反元素；

接着�l�过一个仿��?/span>(Affine)转换�q�算�Q�定义如下：

(本图摘录自参考文�?/span>[1])

字节取代(ByteSub)�q�算�?/span>State的媄响，如下图所�C�：

(本图摘录自参考文�?/span>[1])

字节取代(ByteSub)转换的反�q�算�Q?/span>

计算仿射对应之后的相反运��可得到S^-1-Box�Q�以�?/span>S^-1-Box做字节取�?/span>(ByteSub)卛_��?/span>

2. �U�d��转换( ShiftRow transformation )�Q?/span>

在这个�{换中�Q?/span>State的每一列以不同的偏�U�量做环状位�U�，�W?/span>0列不动，�W�一列位�U?/span>C1个字节，�W�二列位�U?/span>C2个字节，�W�三列位�U?/span>C3个字节。位�Uȝ��偏移�?/span>C1,C2,C3跟区块的数目(Nb)有关�Q�定义如下表�Q?/span>

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

�U�d��转换(ShiftRow)�q�算对于State的媄响，囄��如下�Q?/span>

(本图摘录自参考文�?/span>[1])

�U�d��转换(ShiftRow)的反�q�算�Q?/span>

对第二第三及�W�四列做Nb-C1,Nb-C2,Nb-C3个字节的环状位移卛_��?/span>

3. 淯��转换(MixColumn transformation)�Q?/span>

在这个�{换中�Q�把State当作一个存�?/span>GF(2⁸)中的多项式。�ƈ且对一个固定的多项�?/span>c(x)作乘法，如果发生溢位�Q�则再模�?/span>x⁴+1。表�C�如下：

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

c(x)�?/span>x⁴+1互质�Q��ob(x) = c(x) Ä a(x)�Q�以矩阵乘法表示如下�Q?/span>

(本图摘录自参考文�?/span>[1])

State�l�过淯��(MixColumn)�q�算之后的变化如下：

(本图摘录自参考文�?/span>[1])

淯��(MixColumn)转换的反�q�算�Q�则是乘上一个特�D�的多项�?/span>d(x)�Q?/span>

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

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

4. The Round Key Addition�Q?/span>

�q�个�q�算主要是把每一个回合金�?/span>(Round Key)透过��单的bitwise EXOR加入到每一�?/span>State中，以图�C�如下：

(本图摘录自参考文�?/span>[1])

四、金钥的排程(Key Schedule)

回合金钥(Round Key)是从加密金钥(Cipher Key)�l�过�q�算产生出来的。金钥排�E?/span>(Key Schedule)是由金钥扩充(Key Expansion)及回合金钥的选择(Round Key Selection)�l�成的，基本的理论如下：

所有回合金钥的��M��数是把区块长�?/span>(block length)乘上回合数加1�Q?/span>(�?/span>Nr-1个回合，加上一个终止回�?/span>(final round))�Q�例如，128个位的区块长度经�q?/span>10个回合运��，所需要用到的所有回合金钥的��M��Cؓ1408个位�?/span>

加密金钥(Cipher Key)必须扩充为扩充金�?/span>(Expanded Key)�?/span>

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

�W�一个回合金钥由�?/span>Nb个字�l�组成，�W�二个回合金钥由接下来的Nb个字�l�组成，余此�c�L��?/span>

(1) 金钥的扩�?/span>( Key Expansion )�Q?/span>

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

金钥扩充函式�?/span>Nk是息息相关的�Q�分��Z��U�情况运作，一是当Nk��于或等�?/span>6�Q�另外则是当Nk大于6�Q�以伪码叙述如下�Q?/span>

�?/span>Nk�?/span>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;

}

在上面的子程序中�Q?/span>SubByte(W)传回一�?/span>4-byte的字�l�，�q�些字组是输入的字组�l�过S-box的�{换所产生的相对字�l��?/span>RotByte(W)则是传回�l�过旋�{的字�l��?/span>

�?/span>Nk�Q?/span>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;

}

以上两种情况的相异处在于�?/span>Nk�?/span>6�Ӟ��(i-4)�?/span>Nk的倍数�Ӟ��对于W[i-1]先执�?/span>SubByte�Q�再执行EXOR�?/span>

上述回合常数定义如下�Q?/span>

Rcon[i] = (RC[i],‘00’,‘00’,‘00’)�Q�其�?/span>RC[0]=’01’�Q?/span>RC[i]=xtime(Rcon[i-1])�?/span>

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

�W?/span>i个回合金钥是指在存在回合金钥�~�冲区的字组W[Nb*i]�?/span>W[Nb*(i+1)]�Q�图�C�如下：

(本图摘录自参考文�?/span>[1])

五、安全性分�?/span>

我们针对以下已知的攻��L��?/span>Rijndael的安全性分析作一��要叙�q�ͼ�包括差分��d��?/span>(Differential Cryptanalysis)�Q�线性攻��L��(Linear Cryptanalysis)�Q��^�Ҏ��L��(The Square Attack)�Q�内插攻��L��(Interpolation attacks)�{�攻��L��式�?/span>

(1) 差分��d��?/span>( Differential Cryptanalysis )

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

(2) �U�性攻��L��( Linear Cryptanalysis )

�q�是一�U?/span>Known-plaintext��d��法，利用大量搜集到的明文/密文对的相关性，对加密法�q�行��d��。明�?/span>/密文对的相关性由�U�性轨�q?/span>(Linear trails)所�l�成�Q�由于线性轨�q�的相关�p�L��?/span>Round keys的值有密切关系�Q�透过相关�p�L��的正负号�Q�线性攻��L��可以找出金钥倹{��要�Ҏ��q�种��d��法，有一个必要条件就是�ɘq�种相关�p�L��大于2^n/2的线性轨�q�不存在。在Rijndael中，已经证明出当执行四个回合�Ӟ��不存在相关系数大�?/span>2^-75的线性轨�q�；在执行八个回合时�Q�其相关�p�L��大于2^-150的相关系��C��不存在。详�l�证明过�E�请参照参考文献�?/span>

(3) �q�x��d��?/span>( The Square attack )

�q�种��d��法是一�U?/span>chosen- plaintext attack�Q�而且和字节取�?/span>(ByteSub)�Q��؜�?/span>(MixColumn)时的多项式乘法，金钥的排�E?/span>(Key Schedule)�{�运��无兟뀂当Rijndael执行6个回合以上时�Q�此�U�方式比完全的金钥搜�?/span>(exhaustive key search)来的更有效率。关于此�U�攻��L��式的详尽描述�?/span>Rijndael如何延��此种��d��方式�Q�请参照参考文献�?/span>

(4) 内插��d��?/span>( Interpolation attacks )

在这�U�攻��L��中，��d��者利用加密的输入及输出配对，建立一些多��式。如果加密的�l��g有一个简�z�的代数展开式，�q�且和管理的复杂度结合在一��h��Q�这�U�攻��L��便是可行的。基本的��d��方式是如果攻击者徏立的代数展开式的阶度(degree)很小�Q�只需要一些加密法的输入及输出配对��可以得��C��数展开式的各项�p�L��。然而，�?/span>GF(2⁸)中的取代矩阵(S-box)�Q�它的展开式�ؓ�Q?/span>63+8fx¹²⁷+b5x¹⁹¹+01x²²³+f4x²³⁹+25x²⁴⁷+f9x²⁵¹+09x²⁵³+05x²⁵⁴。其余介�l�，请参照参考文献�?/span>

(5)、弱金钥(Weak keys)

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

六、结论：

以上�?/span>Rijndael作一��要介�l�之后，我们�?/span>Rijndael的优点与限制作�ؓ我们的结论�?/span>

(1)�?/span>Rijndael有以下优�?/span>�?/span>

以实作观点而言

1. Rijndael可以实作�?/span>Pentium ( Pro ) �{�计��机上，�q�已相当快的速度处理�q�算�Q�而在表格大小与效率之间是可以做取舍的�?/span>

2. Rijndael可以实作在智能卡(Smart Card)上，使用��量�?/span>RAM�Q�少量的�E�序代码�Q�在ROM与效率之间也是可以做取舍的�?/span>

3. 在设计上�Q�回合的转换是可�q��处理的�?/span>

4. 加密法不采用��术�q�算�Q�不会因��Z��同处理器架构而有所偏差�?/span>

设计��单化�Q?/span>

1. 设计上不引用其它加密�l��g�Q�如S-box�?/span>

2. 安全度不建立在一些分析不够明��的��术�q�算之上�?/span>

3. 加密法紧凑，不易藏入暗门�{�程序代码�?/span>

除此之外�Q?/span>Rijndael更允许可变动的区块长度及金钥长度�Q�其长度可由128位到256位之��_��所以回合数也是可变动的�?/span>

(2)Rijndael的限�Ӟ��

在解密过�E�中有以下限�?/span>

1. 实作在智慧卡�Ӟ��解密不如加密来的有效率，解密需要更多的�E�序代码�?/span>cycles�Q�但是跟其它��法比�v来，仍然是快速的�?/span>

2. 以��Y件而言�Q�加密和解密使用不同的程序和表格�?/span>

3. 以硬件而言�Q�解密只能重用部分加密的电�\�?/span>

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

�l�D��

    md5的全�U�是message-digest algorithm 5�Q�信�?摘要��法�Q�，�?0�q�代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest开发出来，�l�md2、md3和md4发展而来。它的作用是让大定w��信息在用数字�{�֐�软�g�{��v�U��h密匙前被"压羃"成一�U�保密的格式�Q�就是把一个�Q意长度的字节串变换成一定长的大整数�Q�。不��是md2、md4�q�是md5�Q�它们都需要获得一个随机长度的信息�q��生一�?28位的信息摘要。虽然这些算法的�l�构或多或少有些�怼��Q�但md2的设计与md4和md5完全不同�Q�那是因为md2是�ؓ8位机器做�q�设计优化的�Q�而md4和md5却是面向32位的电脑。这三个��法的描�q�和c语言源代码在internet rfcs 1321中有详细的描�q�ͼ�http://www.ietf.org/rfc/rfc1321.txt�Q�，�q�是一份最权威的文档，由ronald l. rivest�?992�q?月向ieft提交�?

    rivest�?989�q�开发出md2��法。在�q�个��法中，首先对信息进行数据补位，使信息的字节长度�?6的倍数。然后，以一�?6位的��验和�q�加��C��息末��。�ƈ且根据这个新产生的信息计��出散列倹{��后来，rogier和chauvaud发现如果忽略了检验和��生md2冲突。md2��法的加密后�l�果是唯一�?-既没有重复�?

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

    ��管md4��法在安全上有个�q�么大的漏洞�Q�但它对在其后才被开发出来的好几�U�信息安全加密算法的出现却有着不可忽视的引��g��用。除了md5以外�Q�其中比较有名的�q�有sha-1、ripe-md以及haval�{��?

    一�q�以后，�?991�q�_��rivest开发出技术上更�ؓ��近成熟的md5��法。它在md4的基��上增加了"安全-带子"�Q�safety-belts�Q�的概念。虽然md5比md4�E�微慢一些，但却更�ؓ安全。这个算法很明显的由四个和md4设计有少�怸�同的步骤�l�成。在md5��法中，信息-摘要的大��和填充的必要条件与md4完全相同。den boer和bosselaers曑֏�现md5��法中的假冲�H�（pseudo-collisions�Q�，但除此之外就没有其他被发现的加密后结果了�?

    van oorschot和wiener曄��考虑�q�一个在散列中暴力搜��d��H�的函数�Q�brute-force hash function�Q�，而且他们猜测一个被设计专门用来搜烦md5冲突的机器（�q�台机器�?994�q�的刉��成本大�U�是一百万��元�Q�可以��^均每24天就扑ֈ�一个冲�H�。但单从1991�q�到2001�q�这10�q�间�Q�竟没有出现替代md5��法的md6或被叫做其他什么名字的新算法这一点，我们��可以看��个瑕疵�ƈ没有太多的媄响md5的安全性。上面所有这些都不��以成为md5的在实际应用中的问题。�ƈ且，�׃��md5��法的��用不需要支付�Q何版权费用的�Q�所以在一般的情况下（非绝密应用领域。但即便是应用在�l�密领域内，md5也不�׃ؓ一�U�非�怼��U�的中间技术）�Q�md5怎么都应该算得上是非常安全的了�?nbsp;

��法的应�?/strong>

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

    md5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461

    �q�就是tanajiya.tar.gz文�g的数字签名。md5��整个文件当作一个大文本信息�Q�通过其不可逆的字符串变换算法，产生了这个唯一的md5信息摘要。如果在以后传播�q�个文�g的过�E�中�Q�无论文件的内容发生了�Q何�Ş式的改变�Q�包括�h��Z��Ҏ��者下载过�E�中�U��\不稳定引��L��传输错误�{�）�Q�只要你对这个文仉��新计��md5时就会发��C��息摘要不相同�Q�由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构，用md5�q�可以防止文件作者的"抵赖"�Q�这��是所谓的数字�{�֐�应用�?

    md5�q�广泛用于加密和解密技术上。比如在unix�pȝ��中用��L��密码��是以md5�Q�或其它�c�M��的算法）�l�加密后存储在文件系�l�中。当用户��d��的时候，�pȝ��把用戯��入的密码计算成md5��|��然后再去和保存在文�g�pȝ��中的md5��D��行比较，�q�而确定输入的密码是否正确。通过�q�样的步骤，�pȝ��在�ƈ不知道用户密码的明码的情况下��可以确定用��L��录系�l�的合法性。这不但可以避免用户的密码被��h��pȝ��理员权限的用户知道�Q�而且�q�在一定程度上增加了密码被破解的难度�?

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

��法描述

    对md5��法��要的叙述可以为：md5�?12位分�l�来处理输入的信息，且每一分组又被划分�?6�?2位子分组�Q�经�q�了一�p�d��的处理后�Q�算法的输出由四�?2位分�l�组成，��这四个32位分�l��联后��生成一�?28位散列倹{�?

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

    md5中有四个32位被�U�C��链接变量�Q�chaining variable�Q�的整数参数�Q�他们分别�ؓ�Q�a=0x01234567�Q�b=0x89abcdef�Q�c=0xfedcba98�Q�d=0x76543210�?

    当设�|�好�q�四个链接变量后�Q�就开始进入算法的四轮循环�q�算。��@环的�ơ数是信息中512位信息分�l�的数目�?

    ��上面四个链接变量复制到另外四个变量中：a到a�Q�b到b�Q�c到c�Q�d到d�?

    ��d�@环有四轮�Q�md4只有三轮�Q�，每轮循环都很�怼�。第一轮进�?6�ơ操作。每�ơ操作对a、b、c和d中的其中三个作一�ơ非�U�性函数运��，然后��所得结果加上第四个变量�Q�文本的一个子分组和一个常数。再��所得结果向右环�U�M��个不定的敎ͼ��q�加上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))
    �Q?amp;是与�Q�|是或�Q�~是非�Q�^是异或）

    �q�四个函数的说明�Q�如果x、y和z的对应位是独立和均匀的，那么�l�果的每一位也应是独立和均匀的�?
    f是一个逐位�q�算的函数。即�Q�如果x�Q�那么y�Q�否则z。函数h是逐位奇偶操作�W��?

    假设mj表示消息的第j个子分组�Q�从0�?5�Q�，<<
    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)<<
    �q�四轮（64步）是：

    �W�一�?

    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)

    �W�二�?

    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)

    �W�三�?

    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)

    �W�四�?

    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可以如下选择�Q?

    在第i步中�Q�ti�?294967296*abs(sin(i))的整数部分，i的单位是弧度�?4294967296�{�于2�?2�ơ方)
    所有这些完成之后，��a、b、c、d分别加上a、b、c、d。然后用下一分组数据�l�箋�q�行��法�Q�最后的输出是a、b、c和d的��联�?

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

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

    如果你用上面的信息分别对你做的md5��法实例做测试，最后得出的�l�论和标准答案完全一��P��那我��p��在这里象你道一声祝��Z��。要知道�Q�我的程序在�W�一�ơ编译成功的时候是没有得出和上面相同的�l�果的�?nbsp;


md5的安全�?/strong>

    md5相对md4所作的改进�Q?nbsp;
    1. 增加了第四轮�Q?nbsp;
    2. 每一步均有唯一的加法常敎ͼ�
    3. 为减��q��二轮中函数g的对�U�性从(x&y)|(x&z)|(y&z)变�ؓ(x&z)|(y&(~z))�Q?nbsp;
    4. �W�一步加上了上一步的�l�果�Q�这��引��h��快的雪崩效应�Q?nbsp;
    5. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不�怼��Q?nbsp;
    6. �q�似优化了每一轮中的��@环左�U�M��U�量以实现更快的雪崩效应。各轮的位移量互不相同�?nbsp;

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

[转]使用CPU旉��戌��行高�_�ֺ�计时

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

对关注性能的程序开发�h员而言�Q�一个好的计旉��件既是益友，也是良师。计时器既可以作为程序组件帮助程序员�_��的控制程序进�E�，又是一件有力的调试武器�Q�在有经验的�E�序员手里可以尽快的��定�E�序的性能瓉��Q�或者对不同的算法作出有说服力的性能比较�?/span>
�?/span>Windows�q�_��下，常用的计时器有两�U�，一�U�是timeGetTime多媒体计时器�Q�它可以提供毫秒�U�的计时。但�q�个�_�ֺ�对很多应用场合而言�q�是太粗�p�了。另一�U�是QueryPerformanceCount计数器，随系�l�的不同可以提供微秒�U�的计数。对于实时图形处理、多媒体数据��处理、或者实时系�l�构造的�E�序员，善用QueryPerformanceCount/QueryPerformanceFrequency是一��基本功�?/span>
本文要介�l�的�Q�是另一�U�直接利�?/span>Pentium CPU内部旉��戌��行计时的高精度计时手�D�c��以下讨��Z��要得益于�?/span>Windows囑�Ş�~�程》一书，�W?/span>15��－17��，有兴��的读者可以直接参考该书。关�?/span>RDTSC指��o的详�l�讨论，可以参�?/span>Intel产品手册。本文仅仅作抛砖之用�?/span>

�?/span>Intel Pentium以上�U�别�?/span>CPU中，有一个称�?/span>“旉��戻I��Time Stamp�Q?/span>”的部�Ӟ��它以64位无�W�号整型数的格式�Q�记录了�?/span>CPU上电以来所�l�过的时钟周期数。由于目前的CPU主频都非帔R��Q�因此这个部件可以达到纳�U��的计时精度。这个精��性是上述两种�Ҏ��所无法比拟的�?/span>
�?/span>Pentium以上�?/span>CPU中，提供了一条机器指�?/span>RDTSC�Q?/span>Read Time Stamp Counter�Q�来��d��q�个旉��戳的数字�Q��ƈ��其保存�?/span>EDX:EAX寄存器对中。由�?/span>EDX:EAX寄存器对恰好�?/span>Win32�q�_��?/span>C++语言保存函数�q�回值的寄存器，所以我们可以把�q�条指��o看成是一个普通的函数调用。像�q�样�Q?/span>

inline unsigned __int64 GetCycleCount()
{
__asm RDTSC
}

但是不行�Q�因�?/span>RDTSC不被C++的内嵌汇�~�器直接支持�Q�所以我们要�?/span>_emit伪指令直接嵌入该指��o的机器码形式0X0F�?/span>0X31�Q�如下：

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

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

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

�?/span>Windows囑�Ş�~�程》第15��늼�写了一个类�Q�把�q�个计数器封装�v来。有兴趣的读者可以去参考那个类的代码。作者�ؓ了更�_��的定�Ӟ��做了一点小��的改进�Q�把执行RDTSC指��o的时��_��通过�q�箋两次调用GetCycleCount函数计算出来�q�保存了��h��Q�以后每�ơ计时结束后�Q�都从实际得到的计数中减掉这一��段旉��Q�以得到更准��的计时数字。但我个��得这一点点改进意义不大。在我的机器上实��，�q�条指��o大概花掉了几十到100多个周期�Q�在Celeron 800MHz的机器上�Q�这不过是十分之一微秒的时间。对大多数应用来��_��q�点旉��完全可以忽略不计�Q�而对那些��实要精��到�U�秒数量�U�的应用来说�Q�这个补偿也�q�于�_�糙了�?/span>

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

�q�个�Ҏ��的缺�Ҏ��Q?/span>
1.现有�?/span>C/C++�~�译器多��C��直接支持使用RDTSC指��o�Q�需要用直接嵌入机器码的方式�~�程�Q�比较麻烦�?/span>
2.数据抖动比较厉害。其实对��M��计量手段而言�Q�精度和�E�_��性永�q�是一对矛盾。如果用低精度的timeGetTime来计�Ӟ��基本上每�ơ计时的�l�果都是相同的；�?/span>RDTSC指��o每次�l�果都不一��P��l�常有几癄��至上千的差距。这是这�U�方法高�_�ֺ�本��n固有的矛盾�?/span>

关于�q�个�Ҏ��计时的最大长度，我们可以��单的用下列公式计��：

�?/span>CPU上电以来的秒�?/span> = RDTSC��d��的周期数 / CPU主频速率�Q?/span>Hz�Q?/span>

64位无�W�号整数所能表辄��最大数字是1.8×10^19�Q�在我的Celeron 800上可以计时大�U?/span>700�q�_��书中说可以在200MHz�?/span>Pentium上计�?/span>117�q�_��q�个数字不知道是怎么得出来的�Q�与我的计算有出入）。无论如何，我们大可不必兛_��溢出的问题�?/span>

下面是几个小例子�Q�简要比较了三种计时�Ҏ��的用法与�_�ֺ�
//Timer1.cpp 使用�?/span>RDTSC指��o�?/span>Timer�c?/span>//KTimer�cȝ��定义可以参见�?/span>Windows囑�Ş�~�程�?/span>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 使用�?/span>timeGetTime函数
//需包含�Q�但�׃��Windows头文仉��l�复杂的关系
//��单包�?/span>比较��h��Q�）
//�~�译行：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 使用�?/span>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));
}

////////////////////////////////////////////////
//以上三个�C�Z��E�序都是��试1�U�钟休眠所耗费的时�?/span>

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

[zt]P2P之UDP�I�K��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�I�K��NAT的原理与实现(shootingstars)

文章说明:

关于UDP�I�K��NAT的中文资料在�|�络上是很少的，仅有<rs)>>�q�篇文章有实际的参考�h倹{��本��两年来也一直从事P2P斚w��的开发工作，比较有代表性的是个人开发的BitTorrent下蝲软�g - FlashBT(变态快�?. 对P2P下蝲或者P2P的开发感兴趣的朋友可以访问��Y件的官方主页: http://www.hwysoft.com/chs/ 下蝲看看�Q�说不定有收莗��写�q�篇文章的主要目的是懒的再每�ơ单独回�{�一些网友的提问, 一�ơ性写下来, 卌��省了自己的时��_��也方便了对于P2P的UDP�I�K��感兴趣的网�?wbr>阅读和理解。对此有兴趣和经验的朋友可以�l�我发邮件或者访问我的个人Blog留言: http://hwycheng.blogchina.com. 您可以自��p�{载此��文章，但是请保留此说明�?

再次感谢shootingstars�|�友的早期�A�? 表示谢意�?

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

NAT, 中文��译为网�l�地址转换。具体的详细信息可以讉K��RFC 1631 - http://www.faqs.org/rfcs/rfc1631.html, �q�是对于NAT的定义和解释的最权威的描�q�。网�l�术语都是很抽象�?wbr>艰�ӆ的，除非是专业�h士，否则很难从字面中来准��理解NAT的含�?wbr>�?

要想完全明白NAT 的作用，我们必须理解IP地址的两大分�c�，一�c�L��U�有IP地址�Q�在�q�里我们�U�C��内网IP地址。一�c�L��非私有的IP地址�Q�在�q�里我们�U�C��公网IP地址。关于IP地址的概念和作用的介�l�参见我的另一��文�? http://hwycheng.blogchina.com/2402121.html

内网IP地址: 是指使用A/B/C�c�M��的私有地址, 分配的IP地址在全球不惧有唯一性，也因此无法被其它外网��L��直接讉K��。公�|�IP地址: 是指��h��全球唯一的IP地址�Q�能够直接被其它��L��讉K��的�?

NAT 最初的目的是�ؓ使用内网IP地址的计��机提供通过��数几台��h��公网的IP地址的计��机讉K��外部�|�络的功能。NAT 负责��某些内�|�IP地址的计��机向外部网�l�发出的IP数据包的源IP地址转换为NAT自己的公�|�的IP地址�Q�目的IP地址不变, �q�将IP数据包�{发给路由器，最�l�到辑֤�部的计算�?wbr>。同时负责将外部的计��机�q�回的IP数据包的目的IP地址转换为内�|�的IP地址�Q�源IP地址不变�Q��ƈ最�l�送达到内�|�中的计��机�?

图一: NAT 实现了私有IP的计��机分��n几个公网IP地址讉K��Internet的功能�?

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

NAPT 负责��某些内�|�IP地址的计��机向外部网�l�发出的TCP/UDP数据包的源IP地址转换为NAPT自己的公�|�的IP地址�Q�源端口转�ؓNAPT自己的一个端口。目的IP地址和端口不�? �q�将IP数据包发�l��\由器�Q�最�l�到辑֤�部的计算�?wbr>。同时负责将外部的计��机�q�回的IP数据包的目的IP地址转换内网的IP地址�Q�目的端口�{为内�|�计��机的端口，源IP地址和源端口�?wbr>变，�q�最�l�送达到内�|�中的计��机�?

图二: NAPT 实现了私有IP的计��机分��n一个公�|�IP地址讉K��Internet的功能�?

在我们的工作和生�z�M��, NAPT的作用随处可见，�l�大部分公司的网�l�架�?wbr>�Q�都是通过1至N台支持NAPT的�\由器来实现公司的所有计��机�q?wbr>接外部的Internet�|�络的。包括本人在写这��文章的时�?wbr>�Q�也是在家中使用一台IBM�W�记本通过一台宽带连接的台式机来讉K��Internet的。我们本��文章主要讨论的NAPT的问题�?

NAPT(The IP Network Address/Port Translator) ��Z��ȝ��了P2P软�g的应�?

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

NAT(The IP Network Address Translator) �q�行UDP�I�K��的原理是什�?

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

图三: NAPT 是如何将�U�有IP地址的UDP数据包与公网��L��q�行透明传输的�?

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

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

囑֛�: NAPT ��内部发出的UDP协议包的源地址和源端口改变传输�l�公�|�IP��L��?

图五: NAPT ��收到的公网IP��L��q�回的UDP协议包的目的地址和目的端口改�?wbr>传输�l�内�|�IP计算机现在我们大概明白了NAPT如何实现内网计算机和外网��L��间的透明通讯。现在来看一下我们最兛_��的问�?wbr>�Q�就是NAPT是依据什么策略来判断是否要�ؓ一个请求发出的UDP数据包徏立Session的呢�Q�主要有一下几个策�?

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

D的情冉|��式我们关心和要讨论的问题。依据目的地址(公网IP地址)对于Session的徏立的军_��方式我们��NAPT讑֤�划分��Z��大类:

Symmetric NAPT: 对于到同一个IP地址�Q��Q意端口的�q�接分配使用同一个Session; 对于��C��同的IP地址, ��L��端口的连接��用不同的Session. 我们�U�此�U�NAPT�?Symmetric NAPT. 也就是只要本地绑定的UDP端口相同�Q?发出的目的IP地址不同�Q�则会徏立不同的Session.

囑օ�: Symmetric 的英文意思是对称。多个端口对应多个主机，�q��的，对称�?

Cone NAPT: 对于到同一个IP地址�Q��Q意端口的�q�接分配使用同一个Session; 对于��C��同的IP地址�Q��Q意端口的�q�接也��用同一个Session. 我们�U�此�U�NAPT�?Cone NAPT. 也就是只要本地绑定的UDP端口相同�Q?发出的目的地址不管是否相同�Q?都��用同一个Session.

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

现在�l�大多数的NAPT属于后者，即Cone NAT。本人在��试的过�E�中�Q�只好��用了一台日本的Symmetric NAT。还好不是自��q��买的�Q�我从不买日�? 希望看这��文章的朋友也自觉的不要购买日本的东�ѝ��Win9x/2K/XP/2003�pȝ��自带的NAPT也是属于 Cone NAT的。这是值的庆幸的，因�ؓ我们要做的UDP�I�K��只能在Cone NAT间进行，只要有一��C��是Cone NAT�Q�对不�v�Q�UDP�I�K��没有希望了�Q�服务器转发�?wbr>。后面会做详�l�分�?

下面我们再来分析一下NAPT 工作时的一些数据结构，在这里我们将真正说明UDP可以�I�K��Cone NAT的依据。这里描�q�的数据�l�构只是��Z��说明原理�Q�不��h��实际参考�h��|��真正感兴��可以阅读Linux的中关于NAT实现部分的源码。真正的NAT实现也没有利用数据库的，呵呵�Q��ؓ了速度�Q?

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

内网信息�?

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

PRIMARY KEY( [NAPT 分配端口] ) -> 表示依据[NAPT 分配端口]建立主键�Q�必��d��一且徏立烦引，加快查找. UNIQUE( [ 内网IP地址 ], [ 内网端口 ] ) -> 表示�q�两个字�D�联合�v来不能重�? UNIQUE( [ 内网IP地址 ], [ 内网端口 ], [ 外网IP地址 ] ) -> 表示�q�三个字�D�联合�v来不能重�?

映射�?

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

UNIQUE( [NAPT 分配端口], [ 外网端口 ] ) -> 表示�q�两个字�D�联合�v来不能重�?

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

内网信息�?

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

PRIMARY KEY( [NAPT 分配端口] ) -> 表示依据[NAPT 分配端口]建立主键�Q�必��d��一且徏立烦引，加快查找. UNIQUE( [ 内网IP地址 ], [ 内网端口 ] ) -> 表示�q�两个字�D�联合�v来不能重�?

外网信息�?

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

PRIMARY KEY( [ wid 主键标识 ] ) -> 表示依据[ wid 主键标识 ]建立主键�Q�必��d��一且徏立烦引，加快查找. UNIQUE( [ 外网IP地址 ], [ 外网端口 ] ) -> 表示�q�两个字�D�联合�v来不能重�?

映射�? 实现一对多�Q�的

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

UNIQUE( [NAPT 分配端口], [ wid 主键标识 ] ) -> 表示�q�两个字�D�联合�v来不能重�? UNIQUE( [ wid 主键标识 ] ) -> 标识此字�D�不能重�?

看完了上面的数据�l�构是更明白了还是更晕了�Q?呵呵! 多想一会儿��׃��明白了。通过NAT,内网计算��机向外�q�结是很�Ҏ��的，NAPT会自动处理，我们的应用程序根本不必关心它是如�?wbr>处理的。那么外部的计算机想讉K��内网中的计算机如何实现呢�Q�我们来看一下下面的��程�Q?

c 是一台在NAPT后面的内�|�计��机�Q�s是一台有外网IP地址的计��?wbr>机。c ��d��?s 发�v�q�接��h��Q�NAPT依据上面描述的规则在自己的数据结构中记录下来�Q�徏立一个Session. 然后 c �?s 之间��可以实现双向的透明的数据传输了。如下面所�C?

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]

由此可见�Q�一台外�|�IP地址的计��机惛_��NAPT后面的内�|�计��机通讯的条件就是要求NAPT后面的内�|�计��机��d��向外�|�IP地址�?wbr>计算机发起一个UDP数据包。外�|�IP地址的计��机利用收到的UDP数据包获取到NAPT的外�|�IP地址和映��的端口�Q�以后就可以和内�|�IP的计��机透明的进行通讯了�?

现在我们再来分析一下我们最兛_��的两个NAPT后面的内�|�计��机�?wbr>何实现直接通讯�? 两者都无法��d��发出�q�接��h��Q�谁也不知道�Ҏ��的NAPT的公�|�IP地址和NAPT上面映射的端口号。所以我们要靠一个公�|�IP地址�?wbr>服务器帮助两者来建立�q�接。当两个NAPT后面的内�|�计��机分别�q?wbr>接了公网IP地址的服务器后，服务器可以从收到的UDP数据包中�?wbr>取到�q�两个NAPT讑֤�的公�|�IP地址和这两个�q�接建立的Session的映��端口。两个内�|�计��机可以从服务器上获取到�Ҏ��的NAPT讑֤�公网IP地址和映��的端口了�?

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

NAPT(The IP Network Address/Port Translator) �q�行UDP�I�K��的具体情况分析!

首先明确的将NAPT讑֤�按照上面的说明分�? Symmetric NAPT �?Cone NAPT, Cone NAPT 是我们需要的。Win9x/2K/XP/2003 自带的NAPT也�ؓCone NAPT�?

�W�一�U�情�? 双方都是Symmetric NAPT:

此情况应�l�不存在什么问题，肯定是不支持UDP�I�K��?

�W�二�U�情�? 双方都是Cone NAPT:

此情冉|��我们需要的�Q�可以进行UDP�I�K��?

�W�三�U�情�? 一个是Symmetric NAPT, 一个是Cone NAPT:

此情冉|��较复杂，但我们按照上面的描述和数据机构进行一下分析也�?wbr>�Ҏ��׃��明白�? 分析如下,

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

1. A 惌��?B, A 从服务器那儿获取�?B 的NAT地址和映��端�? A 通知服务器，服务器告�?B A的NAT地址和映��端�? B �?A 发�v�q�接�Q�A 肯定无法接收到。此�?A �?B 发�v�q�接�Q?A 对应的NAT建立了一个新的Session�Q�分配了一个新的映��端口， B �?NAT 接收到UDP包后�Q�在自己的映��表中查询，无法扑ֈ�映射��?wbr>�Q�因此将包丢弃了�?

2. B 惌��?A, B 从服务器那儿获取�?A 的NAT地址和映��端�? B 通知服务�? 服务器告�?A B的NAT地址和映��端�?A �?B 发�v�q�接, A 对应的NAT建立了一个新的Session�Q�分配了一个新的映��端口B肯定无法接收到。此�?B �?A 发�v�q�接, �׃�� B 无法获取 A 建立的新的Session的映��端口，仍是使用服务器上获取的映��?wbr>端口�q�行�q�接�Q?因此 A 的NAT在接收到UDP包后�Q�在自己的映��表中查�?wbr>�Q�无法找到映��项, 因此��包丢弃了�?

�Ҏ��以上分析�Q�只有当�q�接的两端的NAT都�ؓCone NAT的情况下�Q�才能进行UDP的内�|�穿透互联�?

NAPT(The IP Network Address/Port Translator) �q�行UDP�I�K��如何进行现实的验证和分�?

需要的�|�络�l�构如下:

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

验证�Ҏ��:

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

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

美女久久久久久,久久青青草原国产精品免费 ,国产精品久久国产精品99盘

Rijndael加密���法的介�l?

C1

C2

C3

MD5~RFC 1321

[zt]MD5���法原理

[转]使用CPU旉���戌���行高�_�ֺ�计时

[zt]P2P之UDP�I�K��NAT的原理与实现(shootingstars)--增强��?附源代码)

Rijndael加密��法的介�l?

[zt]MD5��法原理

[转]使用CPU旉��戌��行高�_�ֺ�计时