Радужный стол: невозможно получить последнюю скидку

В этом сообщении о криптографии говорится

Цепочка может продолжаться сколько угодно, пока не попадет на первоначальный ввод. Когда он достигнет этой точки, он просто повторится и будет бесполезен.

Таким образом, моя начальная точка — 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 не повторяется, но другие числа повторяются и имеют бесконечный цикл. Моя отправная точка неверна?

c++ qt cryptography rainbowtable qt4 qt4.7

reggie 09.07.2014 источник

Ответы (1)

arrow_upward
24
arrow_downward

Цепочка не гарантирует, что когда-либо снова достигнет начального значения. Чаще всего вы, вероятно, обнаружите, что он входит в такой цикл:

1 ->2 -> 3 -> 4 -> 2 -> 3 -> 4 -> 2 -> .. .

Если ввод больше, чем вывод хэша, невозможно по определению когда-либо снова попасть в начальное входное значение. Однако, даже если входные данные имеют одинаковую длину с выходными, не гарантируется, что хэш покроет все возможные значения в выходном пространстве перед циклом. На самом деле это зависит от характеристик и качества хэша. Хэш может иметь один большой цикл, охватывающий каждое возможное выходное значение в своем цикле. Другие хэши могут входить в несколько различных возможных циклов, каждый из которых охватывает свое подмножество выходного пространства. Другие хэши могут никогда не охватывать все возможные выходные значения.

deceze♦ 09.07.2014

comment

Почему изображение, которое вы добавляете, не найдено? Я еще не до конца понимаю ваш ответ. Означает ли это, что принятый ответ по ссылке, которую я публикую, неверен? - reggie; 09.07.2014

comment

Изображение загружается нормально для меня. Связанный ответ сам по себе не является неверным, я бы сказал, что ему просто нужно небольшое дополнительное разъяснение. Общая идея объяснена правильно, отсутствует небольшая оговорка, что не каждая цепочка всегда снова достигает своего входного значения. - deceze♦; 09.07.2014

comment

Это ссылка на картинку да? i.stack.imgur.com/sh0F4.png пишет, что 404 не найдено. m с помощью Linux и попытался открыть это в Windows, но все еще не нашел. Во всяком случае, в коде, который я сделал, что я должен изменить? или невозможно достичь моей цели, потому что я использую md5 в качестве примера? - reggie; 09.07.2014

comment

Картинка взята отсюда, так лучше? security.stackexchange.com/a/10661 - deceze♦; 09.07.2014

comment

Это просто означает, что ваша функция редукции неравномерно распределяет результаты по всему возможному спектру. Вам придется использовать другую функцию хеширования/редукции. Я не эксперт в этой области, чтобы предложить вам какую-либо конкретную функцию, которая, вероятно, требует отдельного вопроса. - deceze♦; 09.07.2014

comment

Теперь я мог видеть изображение на домашнем компьютере. Значит, я должен изменить функцию редукции, например, преобразовать 2-е число в 6-е вместо 1-го в 5-е число? Я думал, что функция сокращения всегда получает первую цифру до угаданной длины пароля. (Если пароль содержит только цифры. - reggie; 09.07.2014

comment

Хеш-функция имеет определенный выходной диапазон. В вашем случае вывод может быть 00000, или 00001, или 00002 и так далее до 99999. Это 10000 возможных выходных значений. То, что вы ожидаете, - это цикл в этих выходных значениях. Когда вы вводите 00000, выводится 00001. Когда вы вводите 00001, он выводит 00002 и так далее, пока вы снова не зациклитесь на 99999 → 00000 (на самом деле вы ожидаете, что путь будет более случайным, но принцип тот же). (продолжение...) - deceze♦; 09.07.2014

comment

... Ну, этого не происходит. Он идет 00000 → 00001 → 00002 → 00001 → 00002... Когда вы вводите 00002, он не переходит к следующему ожидаемому шагу 00003, он возвращается к 00001, откуда вы, очевидно, попадаете в бесконечный цикл. Вам придется изменить основные характеристики вашей функции редукции, чтобы она гарантированно зацикливалась и не пропускала значения. Речь идет не о какой-то проблеме, связанной с отклонением от единицы, а о фундаментальном принципе, согласно которому ничто в вашей функции редукции не гарантирует полный цикл. - deceze♦; 09.07.2014

comment

@abi Ой, опечатка 0... Премия Педант недели тебе. ;) - deceze♦; 09.07.2014

Радужный стол: невозможно получить последнюю скидку

Ответы (1)

Похожие вопросы