Ноя
10

То для чего создавался журнал или первый пост




  • Заметка о счастье)))))))))))

  • Чем примечательна зима в Японии-1


  • Часть 1

    Итак подкинул мне друг задачи со своего ЖЖ. Первую из них почти сделал, но в одном месте лоханулся. До 2-ой руки не дошли - да и черт с ней. А вот 3-ая показалась мне очень интересной. Условия можно почитать у [info]sharpc. Итак, нужно пойти по пути m1k1ta и найти эту последовательность. Сначала я думал что наш хакер имеет для взлома изначально лучшие в отличие от нас условия. Ну скажем, очевидно, что использовался генератор случайных чисел. Из того, что писал студент аграрного (простите за каламбур - ничего против них не имею - однако автор задачи наверняка имел в виду вероятную некомпетентность этого студента) следует, что использовался стандартный генератор C/С++. О том, как он работает можно почитать на Википедии LCG. И вот тут и возникло подозрение на то, что у нас худшие условия работы - инициализация генератора обычно производится так:
    srand(time(0)) ; // то есть в зависимости от текущего времени
    Но мы то его не знаем! Время можно получить брутом - у меня даже были попытки. Но все попытки закончились тем, что я доказал (не очень строго - подробности ниже) отсутствие в периоде 2003-2009 возможного времени, которым инициализировали генератор случайных чисел. Итак, ближе к делу. Как вообще можно было получить 10-значный идентификатор? Если внимательно посмотреть на числа m1k1ta, то можно заметить что они состоят из двух int'ов, стоящих рядом.То есть два числа меньшие 32768, но это и есть результат работы функции rand(). Имеем формулу ID=rand()*100000+rand() (в последствии я понял что на самом деле надо так: ID=rand()+rand()*100000). Стас (один из моих друзей) предложил сдвиг - то есть формулу вида ID=(rand() << 16)+rand(). Эта формула была отброшена по причине того, что для 2172605447 у меня получилось (33151 << 16) + 21511 и первое число не входит в диапазон int.

    Самая главная (единственная?) проблема в задаче - нет уверенности, что формула верна. Но если она верна, генератор должен вернуть нам последовательность для которой числа m1k1ta являются ее подпоследовательностью. Иными словами, числа m1k1ta не обязательно будут выдаваться подряд, но очередность их следования должна остаться той же.

    Итак. Вот наш брут:

    #include "stdafx.h"
    #include <stdlib.h>
    bool verify_sequence(unsigned long seed)
    {
        int    hacking [] = {21726,5447,19912,1869,
                        26299,25667,9894,17035,23811,28703} ;
        int    size = sizeof ( hacking ) / sizeof ( hacking [0] ) ;
        const unsigned long upit = 4294967295 ;
        unsigned long   rand1 ;
        int    rand2 ;
        rand1 = seed ;
        for(unsigned long i = 0; i < upit; i++){
            rand1 = rand1*214013+2531011 ;
            rand2 = ((unsigned int)(rand1/65536))%32768 ;
            if(rand2 == hacking[3]){
                rand1 = rand1*214013+2531011 ;
                rand2 = ((unsigned int)(rand1/65536))%32768 ;
                i++ ;
                if(rand2==hacking[2]){
                    printf("Successful i=%i; now=%i; next=%i\n",i,hacking[3],rand2) ;
                    return true ;
                }
            }
        }
        return false ;
    }

    int main(void)
    {
    unsigned long   random1 ;
    const int       MAX_int = 65535 ;
    unsigned long   random2 ;
    bool            resver ;

    for (unsigned int i = 0; i<=MAX_int; i++) // Поиск стартового числа seed
        {
            random2 = 5447*65536 + i ; // перебор по всем возможным
            random1 = random2*214013+2531011 ;
            random1 = ((unsigned int)(random1/65536))%32768 ;
            if (random1==21726){
                printf("i=%i random2=%u\n",i,random2) ;
                resver = verify_sequence(random2) ;
            }
        }
    return 0 ;
    }

    Чтобы понять почему цикл в main именно такой, надо увидеть алгоритм LCG. Программа вызывалась два раза. Первый раз она выглядела по-другому:

    if(rand2 == hacking[2]){
    ...
    if(rand2==hacking[3]){
    printf("Successful i=%i; now=%i; next=%i\n",i,hacking[2],rand2) ;
    ...
    random2 = 21726*65536 + i ; // перебор по всем возможным
    ...
    if (random1==5447){

    Разница я думаю понятна - проверяем обе формулы ID=rand()*100000+rand() и ID=rand()+rand()*100000. Верной оказалась 2-ая (реализация брута - верхняя).
    Результат:
    i=24502 random2=356999094
    Successful i=4; now=1869; next=19912
    i=54605 random2=357029197
    Successful i=1354647431; now=1869; next=19912

    2-ое число мне не очень понравилось... А вот 1-ое в виду того, что наши числа стоят рядом друг с другом (i=4) фактически означает правильность решения...
    А теперь генератор (нет ведущих нулей - допишите их слева сами, чтобы получилось 10-значное число, лень было довести до ума):

    srand(356999094) ; // Congratulations...
    unsigned long a1;

    a1 = 5447+rand()*100000 ;
    printf("Id=%u\n",a1);
    for(int j=0; j<20; j++){
        a1 = rand()+rand()*100000 ;
        printf("Id=%u\n",a1);
    }

    Результат:
    Id=2172605447
    Id=1153814771
    Id=1991201869
    Id=2629925667
    Id=989417035
    Id=2381128703

    Id=3033331322
    Id=466417673
    Id=771115141
    Id=686828253
    Id=2764425547
    Id=3275732662
    Id=1285920037
    Id=974108723
    Id=77827529
    Id=303512316
    Wed 2008-04-09 12:28:25
    1-ое, 3-ье, 4-ое, 5-ое и 6-ое числа - числа m1k1ta.

    Часть 2

    Все же мне не нравится, что нули спереди не дописываются. И решил я сделать вот что:

    const int max_number=21 ;
    for(int j=0; j<max_number; j++){
            printf("%010d\n", rand()+100000*rand()) ;
    }

    После того, как [info]sharpc признал решение не слишком правильным, пришлось над ним поработать. В частности, откуда следует, что ID-шники, выданные сервером Миките обязательно были первыми? Нужно найти действительно стартовый seed, а не тот, который доказывает нам, что мы правильно разгадали структуру ID. Поэтому вообще не делая srand, запускаем программу с кодом, показанным выше. Вот результат:
    1846700041
    2650006334
    1572419169
    2935811478
    2446426962
    2814505705
    1682723281
    0049109961
    1194202995
    0543604827
    1460432391
    0015303902
    1238200292
    1871617421
    1989519718
    2172605447
    1153814771
    1991201869
    2629925667
    0989417035
    2381128703

    А вот некое подобие варианта от [info]sharpc:

    const int max_number=21 ;
    for(int j=0; j<max_number; j++){
            printf("%05d%05d", rand(), rand()) ;
    }

    Выглядит более адекватно чем мое. Конкатенация вместо умножения.
    Продолжение следует...




















































































































  • Заметка о счастье)))))))))))

  • Чем примечательна зима в Японии-1



  • Социальные сети

    Рубрики

    Последние записи