|
发表于 2007-1-4 13:09:31
|
显示全部楼层
==============
Appendix
==============
函数注释:
[1]
void CChainWalkContext::IndexToPlain()
{
int i;
for (i = m_nPlainLenMax - 1; i >= m_nPlainLenMin - 1; i--)
{
if (m_nIndex >= m_nPlainSpaceUpToX)
{
m_nPlainLen = i + 1;
break;
}
}
// 根据 m_nIndex的大小来判断m_nPlainLen的大小
// m_nIndex 就是开始随机生成的, 和之后中间步骤
// m_nPlainSpaceUpToX 用来计算Pxx的
// 当i 时 P 应该有的大小.
// P的概率统计的东东.
uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1]
//此段密码长度应该有的偏移大小.
/*
// Slow version
for (i = m_nPlainLen - 1; i >= 0; i--)
{
m_Plain = m_PlainCharset[nIndexOfX % m_nPlainCharsetLen];
nIndexOfX /= m_nPlainCharsetLen;
}
*/
// 事实上完全可以用上面的那个慢速版本来完成
// 为了避免64位的除法运行
// 当数据还是32位时, 就截成32位来算
// Fast version
for (i = m_nPlainLen - 1; i >= 0; i--)
{
#ifdef _WIN32
if (nIndexOfX < 0x100000000I64)
break;
#else
if (nIndexOfX < 0x100000000llu)
break;
#endif
// m_Plain 的方式和16 进制差不多, 不过是明文字符长度进制
// 最先算出来的是最后一位.
m_Plain = m_PlainCharset[nIndexOfX % m_nPlainCharsetLen]; //根据明文字符的内容, 来取关于的大小
nIndexOfX /= m_nPlainCharsetLen;
}
// 算完了 64位, 为什么还要计算32位呢?(见上)
unsigned int nIndexOfX32 = (unsigned int)nIndexOfX;
for (; i >= 0; i--)
{
//m_Plain = m_PlainCharset[nIndexOfX32 % m_nPlainCharsetLen];
//nIndexOfX32 /= m_nPlainCharsetLen;
unsigned int nPlainCharsetLen = m_nPlainCharsetLen;
unsigned int nTemp;
#ifdef _WIN32
__asm
{
mov eax, nIndexOfX32
xor edx, edx
div nPlainCharsetLen
mov nIndexOfX32, eax
mov nTemp, edx
}
#else
__asm__ __volatile__ ( "mov %2, %%eax;"
"xor %%edx, %%edx;"
"divl %3;"
"mov %%eax, %0;"
"mov %%edx, %1;"
: "=m"(nIndexOfX32), "=m"(nTemp)
: "m"(nIndexOfX32), "m"(nPlainCharsetLen)
: "%eax", "%edx"
);
#endif
m_Plain = m_PlainCharset[nTemp];
}
}
[2]
void CChainWalkContext::HashToIndex(int nPos)
{
m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
// nPos 的目的就是要有所变化,每次有加1
// 这就是每个Reduce 函数不同的原因了
// m_nReduceOffset与RaombowTableIndex 相关 见[3]
// m_nReduceOffset = 65536 * nRainbowTableIndex;
// m_Hash是取HASH值的前8 个字节, 因为HASH可能会超过8 bytes
}
[3]
rtgen lm alpha 1 7 3 2100 8000000 all
bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex) <--------- argv[5] 即 3
{
if (nRainbowTableIndex < 0)
return false;
m_nRainbowTableIndex = nRainbowTableIndex; // 将所要计算的表分成几张表, 而最后all(argv[8]仅仅是生成表的名字罢了)
// 的重复则是为了增加成功率.
m_nReduceOffset = 65536 * nRainbowTableIndex;
return true;
}
[4]
void CCrackEngine::SearchTableChunk(RainbowChain* pChain, int nRainbowChainLen, int nRainbowChainCount, CHashSet& hs)
{
vector<string> vHash;
hs.GetLeftHashWithLen(vHash, CChainWalkContext::GetHashLen());
printf("searching for %d hash%s...\n", vHash.size(),vHash.size() > 1 ? "es" : "");
int nChainWalkStep = 0;
int nFalseAlarm = 0;
int nChainWalkStepDueToFalseAlarm = 0;
int nHashIndex;
for (nHashIndex = 0; nHashIndex < vHash.size(); nHashIndex++)// 针对每个HASH 进行验证
{
unsigned char TargetHash[MAX_HASH_LEN];
int nHashLen;
ParseHash(vHash[nHashIndex], TargetHash, nHashLen);// string -> binary
if (nHashLen != CChainWalkContext::GetHashLen())
printf("debug: nHashLen mismatch\n");
// Rqeuest ChainWalk
bool fNewlyGenerated;
uint64* pStartPosIndexE = m_cws.RequestWalk(TargetHash, // 一些结构的准备
nHashLen,
CChainWalkContext::GetHashRoutineName(),
CChainWalkContext::GetPlainCharsetName(),
CChainWalkContext::GetPlainLenMin(),
CChainWalkContext::GetPlainLenMax(),
CChainWalkContext::GetRainbowTableIndex(),
nRainbowChainLen,
fNewlyGenerated);
//printf("debug: using %s walk for %s\n", fNewlyGenerated ? "newly generated" : "existing",
// vHash[nHashIndex].c_str());
// Walk
int nPos;
for (nPos = nRainbowChainLen - 2; nPos >= 0; nPos--)
{
[4-1] if (fNewlyGenerated) // 是否是新建的. RequestWalk中返回相应的信息
{
CChainWalkContext cwc;
cwc.SetHash(TargetHash);
cwc.HashToIndex(nPos); // 这个就是R n-1 , 第二次 R n-2
int i;
for (i = nPos + 1; i <= nRainbowChainLen - 2; i++)
{
cwc.IndexToPlain(); // 三步为
cwc.PlainToHash(); // f n-1.
cwc.HashToIndex(i); //
}
pStartPosIndexE[nPos] = cwc.GetIndex(); // 得到的值将和pChain.nIndexE的所有项进行比较
nChainWalkStep += nRainbowChainLen - 2 - nPos; // 第几步了
}
uint64 nIndexEOfCurPos = pStartPosIndexE[nPos];
// Search matching nIndexE
int nMatchingIndexE = BinarySearch(pChain, nRainbowChainCount, nIndexEOfCurPos); // 二分查找
if (nMatchingIndexE != -1) //找到了
{
int nMatchingIndexEFrom, nMatchingIndexETo;
GetChainIndexRangeWithSameEndpoint(pChain, nRainbowChainCount,
nMatchingIndexE,
nMatchingIndexEFrom,
nMatchingIndexETo);
// 找到相同的区域, 因为完全有可能相同.
// 因为函数的收敛性的问题, 原始的HASH和reduce函数的解空间只有缩减的份
int i;
for (i = nMatchingIndexEFrom; i <= nMatchingIndexETo; i++)
{
// 原来相关的明文存放的是在CheckAlarm 函数中操作的
// 找到一个确实的, 就放入然后退出, 该HASH 的encryptanalysis
if (CheckAlarm(pChain + i, nPos, TargetHash, hs)) // 再进行判断一次. 再正向过程一次.
{
//printf("debug: discarding walk for %s\n", vHash[nHashIndex].c_str());
m_cws.DiscardWalk(pStartPosIndexE);
goto NEXT_HASH;
}
else // 如果不是则说明是一次误报, false alarm.
{
nChainWalkStepDueToFalseAlarm += nPos + 1;
nFalseAlarm++;
}
}
}
}
NEXT_HASH:;
}
//printf("debug: chain walk step: %d\n", nChainWalkStep);
//printf("debug: false alarm: %d\n", nFalseAlarm);
//printf("debug: chain walk step due to false alarm: %d\n", nChainWalkStepDueToFalseAlarm);
m_nTotalChainWalkStep += nChainWalkStep;
m_nTotalFalseAlarm += nFalseAlarm;
m_nTotalChainWalkStepDueToFalseAlarm += nChainWalkStepDueToFalseAlarm;
}
[5]
bool CCrackEngine::CheckAlarm(RainbowChain* pChain, int nGuessedPos, unsigned char* pHash, CHashSet& hs)
{
CChainWalkContext cwc;
cwc.SetIndex(pChain->nIndexS);
int nPos;
for (nPos = 0; nPos < nGuessedPos; nPos++) //根据猜测的位置从头nIndexS推到相应的位置
{
cwc.IndexToPlain();
cwc.PlainToHash();
cwc.HashToIndex(nPos);
}
cwc.IndexToPlain(); +-
cwc.PlainToHash(); \ 只作了一个HASH, 并没有什么Reduce函数(cwc.HashToIndex(nPos) ), 就是为了验证
if (cwc.CheckHash(pHash)) // 验证函数, 比较pHash和生成的函数
{
printf("plaintext of %s is %s\n", cwc.GetHash().c_str(), cwc.GetPlain().c_str());
hs.SetPlain(cwc.GetHash(), cwc.GetPlain(), cwc.GetBinary()); // 结果的放入
return true;
}
return false;
[6]
RequestWalk的目的是为某个需要破解的HASH, 生成一个存放用于匹配pChain.nIndexE的数组.
uint64* CChainWalkSet::RequestWalk(unsigned char* pHash, int nHashLen,
string sHashRoutineName,
string sPlainCharsetName, int nPlainLenMin,
int nPlainLenMax,
int nRainbowTableIndex,
int nRainbowChainLen,
bool& fNewlyGenerated)
{
if ( m_sHashRoutineName != sHashRoutineName // 如果相应的参数有所变化, 则所有的东东全部重新设置.
|| m_sPlainCharsetName != sPlainCharsetName
|| m_nPlainLenMin != nPlainLenMin
|| m_nPlainLenMax != nPlainLenMax
|| m_nRainbowTableIndex != nRainbowTableIndex
|| m_nRainbowChainLen != nRainbowChainLen)
{
DiscardAll(); // <----------- Here
m_sHashRoutineName = sHashRoutineName;
m_sPlainCharsetName = sPlainCharsetName;
m_nPlainLenMin = nPlainLenMin;
m_nPlainLenMax = nPlainLenMax;
m_nRainbowTableIndex = nRainbowTableIndex;
m_nRainbowChainLen = nRainbowChainLen;
ChainWalk cw;
memcpy(cw.Hash, pHash, nHashLen);
cw.pIndexE = new uint64[nRainbowChainLen - 1];
m_lChainWalk.push_back(cw);
fNewlyGenerated = true;
return cw.pIndexE;
}
list<ChainWalk>::iterator it;
for (it = m_lChainWalk.begin(); it != m_lChainWalk.end(); it++)
{
if (memcmp(it->Hash, pHash, nHashLen) == 0) // 判断这个HASH 是否是新,
{
fNewlyGenerated = false;
return it->pIndexE; // 如是, 则返回该 8字节数组的指针
}
}
ChainWalk cw; // ChainWalk 有两个结构 一个放hash值, 另一个放后面8 字节数组的指针
memcpy(cw.Hash, pHash, nHashLen);
cw.pIndexE = new uint64[nRainbowChainLen - 1]; // 一个存放用于匹配pChain.mIndexE的数组.
m_lChainWalk.push_back(cw); // 如没有整个HASH, 新建一个, 加入到ChainWalk结构的List
fNewlyGenerated = true;
return cw.pIndexE; //返回的是指向一个放8字节的数组指针
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=530746 |
评分
-
查看全部评分
|