彩虹表:无法得到最后的减少

Question

在这个密码学员额里，它说

这条链可以长到你想要的时间，直到它到达原始输入。当它到达那个点时，它只会重复，它将是无用的。

所以我的出发点是12345，但是我不能得到终点，并且有一个无止境的循环，因为12345不会重复。我使用qt4.7 (lib版本: 4.7.3)来实现这一点。这是我的密码

rainbowTable::rainbowTable(QWidget *parent) :
QWidget(parent),
ui(new Ui::rainbowTable)
{
    ui->setupUi(this);
    passwordLength = 5;
    qDebug() << getLastReduction("12345",false);
}

QString rainbowTable::hashString(QString value)
{
    QString dataToReturn =  QString(QCryptographicHash::hash((value.toAscii()),QCryptographicHash::Md5).toHex());
    return dataToReturn;
}

QString rainbowTable::reductionOfString(QString hash)
{
    QString dataToReturn = "";
    int iterator = 0;

    while ( iterator < hash.count() )
    {
        if ( hash.at(iterator) == '0' ||
             hash.at(iterator) == '1' ||
             hash.at(iterator) == '2' ||
             hash.at(iterator) == '3' || 
             hash.at(iterator) == '4' ||
             hash.at(iterator) == '5' ||
             hash.at(iterator) == '6' ||
             hash.at(iterator) == '7' ||
             hash.at(iterator) == '8' ||
             hash.at(iterator) == '9' )
        {
            dataToReturn += hash.at(iterator);
            if( dataToReturn.count() == passwordLength )
                break;
        }

        iterator++;
    }

    return dataToReturn;
}

QString rainbowTable::getLastReduction(QString value,bool isHash)
{
    int flagToAvoidImmediateExit = 0;
    if( isHash )
    {
        QString startPoint = value;
        startPoint = reductionOfString(startPoint);

        QString endPoint = "";
        QString tempPoint = startPoint;
        while( startPoint != tempPoint  || flagToAvoidImmediateExit == 0 )
        {
            flagToAvoidImmediateExit = 1;

            endPoint = tempPoint;
            tempPoint = hashString(tempPoint);
            tempPoint = reductionOfString(tempPoint);

            qDebug() << tempPoint;
        }

        return endPoint;
    }
    else
    {
        QString startPoint = value;

        QString endPoint = "";
        QString tempPoint = startPoint;

        while( startPoint != tempPoint  || flagToAvoidImmediateExit == 0 )
        {
            flagToAvoidImmediateExit = 1;

            endPoint = tempPoint;
            tempPoint = hashString(tempPoint);
            tempPoint = reductionOfString(tempPoint);

            qDebug() << tempPoint;
        }

        return endPoint;
    }
}

下面是几秒钟的调试输出：

"38064" 
"37923" 
"59636" 
"14842" 
"81105" 
"83011" 
"84978" 
"72903" 
"28301" 
"59067" 
"94222" 
"35329" 
"75907" 
"52980" 
"64297" 
"36654" 
"12207" 
"83738" 
"03523" 
"79083" 
"15597" 
"32652" 
"13934" 
"88497" 
"75435" 
"79791" 
"58265" 
"09856" 
"18041" 
"43966" 
"65978" 
"64242" 
"52739" 
"55704" 
"56811" 
"58183" 
"68597" 
"84064" 
"85717" 
"46438" 
"18042" 
"71321" 
"88067" 
"70648" 
"83580" 
"11878" 
"32297" 
"52376" 
"41289" 
"07909" 
"50439" 
"03819" 
"50325" 
"82736" 
"41621" 
"05497" 
"15546" 
"64017" 
"90503" 
"13150" 
"30287" 
"01749" 
"81308" 
"12036" 
"37241" 
"35850" 
"97225" 
"80539" 
"17472" 
"63098" 
"85818" 
"18438" 
"26139" 
"09545" 
"97042" 
"63672" 
"37406" 
"41180" 
"14910" 
"28900" 
"29729" 
"56861" 
"16208" 
"83565" 
"30912" 
"95541" 
"08468" 
"29539" 
"93679" 
"42487" 
"95833" 
"42793" 
"97064" 
"18087" 
"75623" 
"13910" 
"60404" 
"52557" 
"95932" 
"65477" 
"28304" 
"08456" 
"27849" 
"11429" 
"38896" 
"08634" 
"97107" 
"96385" 
"44159" 
"32875" 
"17063" 
"86213" 
"85052" 
"46852" 
"97541" 
"81412" 
"31199" 
"96618" 
"16178" 
"56100" 
"50394" 
"42087" 
"90552" 
"51966" 
"13598" 
"28757" 
"38715" 
"71025" 
"61334" 
"43686" 
"74633" 
"50360" 
"99883" 
"01361" 
"49662" 
"62929" 
"07280" 
"59161" 
"32509" 
"93670" 
"95649" 
"15206" 
"99927" 
"93692" 
"37748" 
"23350" 
"74680" 
"68259" 
"04819" 
"26627" 
"65968" 
"06919" 
"09194" 
"50084" 
"74452" 
"23763" 
"17953" 
"35026" 
"86691" 
"67542" 
"95634" 
"00793" 
"20270" 
"24386" 
"35606" 
"76055" 
"00010" 
"00798" 
"30867" 
"20697" 
"02143" 
"12044" 
"05098" 
"52828" 
"98446" 
"54039" 
"08778" 
"98405" 
"92267" 
"71783" 
"61953" 
"87447" 
"66505" 
"66535" 
"01776" 
"90120" 
"51497" 
"56082" 
"18253" 
"15222" 
"74769" 
"19614" 
"86376" 
"65391" 
"43365" 
"90484" 
"32717" 
"75052" 
"16186" 
"89444" 
"15439" 
"65166" 
"75785" 
"72462" 
"75920" 
"91383" 
"41678" 
"94123" 
"61751" 
"47976" 
"67798" 
"59438" 
"10180" 
"65854" 
"40218" 
"77990" 
"44843" 
"84554" 
"52350" 
"73347" 
"51901" 
"61155" 
"30316" 
"83096" 
"64946" 
"05985" 
"24208" 
"28718" 
"02241" 
"22303" 
"23331" 
"18410" 
"54868" 
"51723" 
"06401" 
"49554" 
"65577" 
"28105" 
"42319" 
"34167" 
"85036" 
"98679" 
"08594" 
"31075" 
"80514" 
"11517" 
"66780" 
"33411" 
"83180" 
"61910" 
"70423" 
"16885" 
"09107" 
"83702" 
"81842" 
"88430" 
"59146" 
"29140" 
"47236" 
"29625" 
"03078" 
"26540" 
"79321" 
"41649" 
"10210" 
"75702" 
"12020" 
"36877" 
"57307" 
"03222" 
"46603" 
"58449" 
"94709" 
"01436" 
"84975" 
"39385" 
"15952" 
"67607" 
"91666" 
"34456" 
"53385" 
"21512" 
"06712" 
"42073" 
"61343" 
"66825" 
"70199" 
"73203" 
"60216" 
"39469" 
"84324" 
"47850" 
"84825" 
"52471" 
"92397" 
"86051" 
"33676" 
"04221" 
"79740" 
"11573" 
"26304" 
"52510" 
"12679" 
"05930" 
"49607" 
"10880" 
"99174" 
"53967" 
"06397" 
"25700" 
"96721" 
"94694" 
"96566" 
"31746" 
"57359" 
"84870" 
"06236" 
"10673" 
"45914" 
"19209" 
"32478" 
"38824" 
"71178" 
"22983" 
"36320" 
"46594" 
"66538" 
"80495" 
"35645" 
"38064" 
"37923" 
"59636" 
"14842" 
"81105" 
"83011" 
"84978" 
"72903" 
"28301" 
"59067" 
"94222" 
"35329" 
"75907" 
"52980" 
"64297" 
"36654" 
"12207" 
"83738" 
"03523" 
"79083" 
"15597" 
"32652" 
"13934" 
"88497" 
"75435" 
"79791" 
"58265" 
"09856" 
"18041" 
"43966" 
"65978" 
"64242" 
"52739" 
"55704" 
"56811" 
"58183" 
"68597" 
"84064" 
"85717" 
"46438" 
"18042" 
"71321" 
"88067" 
"70648" 
"83580" 
"11878" 
"32297" 
"52376" 
"41289" 
"07909" 
"50439" 
"03819" 
"50325" 
"82736" 
"41621" 
"05497" 
"15546" 
"64017" 
"90503" 
"13150" 
"30287" 
"01749" 
"81308" 
"12036" 
"37241" 
"35850" 
"97225" 
"80539" 
"17472" 
"63098" 
"85818" 
"18438" 
"26139" 
"09545" 
"97042" 
"63672" 
"37406" 
"41180" 
"14910" 
"28900" 
"29729" 
"56861" 
"16208" 
"83565" 
"30912" 
"95541" 
"08468" 
"29539" 
"93679" 
"42487" 
"95833" 
"42793" 
"97064" 
"18087" 
"75623" 
"13910" 
"60404" 
"52557" 
"95932" 
"65477" 
"28304" 
"08456" 
"27849" 
"11429" 
"38896" 
"08634" 
"97107" 
"96385" 
"44159" 
"32875" 
"17063" 
"86213" 
"85052" 
"46852" 
"97541" 
"81412" 
"31199" 
"96618" 
"16178" 
"56100" 
"50394" 
"42087" 
"90552" 
"51966" 
"13598" 
"28757" 
"38715" 
"71025" 
"61334" 
"43686" 
"74633" 
"50360" 
"99883" 
"01361" 
"49662" 
"62929" 
"07280" 
"59161" 
"32509" 
"93670" 
"95649" 
"15206" 
"99927" 
"93692" 
"37748" 
"23350" 
"74680" 
"68259" 
"04819" 
"26627" 
"65968" 
"06919" 
"09194" 
"50084" 
"74452" 
"23763" 
"17953" 
"35026" 
"86691" 
"67542" 
"95634" 
"00793" 
"20270" 
"24386" 
"35606" 
"76055" 
"00010" 
"00798" 
"30867" 
"20697" 
"02143" 
"12044" 
"05098" 
"52828" 
"98446" 
"54039" 
"08778" 
"98405" 
"92267" 
"71783" 
"61953" 
"87447" 
"66505" 
"66535" 
"01776" 
"90120" 
"51497" 
"56082" 
"18253" 
"15222" 
"74769" 
"19614" 
"86376" 
"65391" 
"43365" 
"90484"

正如您所看到的，12345不重复，但其他数字是重复的，并有无休止的循环。是我的出发点错了吗？

Answer 1

链不能保证再次命中初始值。通常情况下，您可能会发现它进入这样的循环：

​

​

如果输入大于哈希输出，根据定义，不可能再次命中初始输入值。但是，即使输入与输出长度相等，也不能保证哈希在循环之前覆盖输出空间中的每个可能值。这实际上取决于哈希的特性和质量。散列可能有一个大周期，覆盖其循环中的每一个可能的输出值。其他散列可以进入若干不同的可能循环，每个循环覆盖输出空间的不同子集。其他散列可能永远不会覆盖所有可能的输出值。