Blog. Just Blog

Генератор Mersenne Twister на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Mersenne Twister (Вихрь Мерсенна) - высокоэффективный генератор псевдослучайных чисел, разработанный Makoto Matsumoto и Takuji Nishimura. К математику Марену Мерсенну название имеет отношение потому, что период генерации равняется числу 219937-1, которое, в свою очередь, является числом Мерсенна. Несмотря на то, что Mersenne Twister является одним из наиболее тщательно протестированных генераторов ПСЧ из ныне существующих, а выдаваемые им последовательности проходят статистические тесты, использование Mersenne Twister в криптографии не рекомендуется без дополнительного шифрования.

Для работы генератора требуется достаточно объемная структура, в которой сохраняется текущее состояние каждого измерения.
  1. MT_SIZE = 624
  2. PERIOD  = 397
  3. DIFF    = MT_SIZE-PERIOD
  4.  
  5. struct MT_STATE
  6.         index       dd ?
  7.         mt          rd MT_SIZE
  8.         mt_tempered rd MT_SIZE
  9. ends
  10.  
  11. state MT_STATE
Сам генератор состоит из двух функций - инициализация и генерация. В принципе, можно добавить генерацию случайного числа в заданном интервале, но тут я этого делать не стал, можете посмотреть реализацию в других генераторах.

При инициализации надо передать начальный параметр, его можно получить, например, при помощи команды RDTSC, функции GetTickCount или чего-нибудь подобного.
  1. ;---------------------------------------------
  2. ; Инициализация генератора случайных чисел
  3. ; stdcall mt_srand,seed
  4. ;---------------------------------------------
  5. proc mt_srand dValue:DWORD
  6.         pusha
  7.         mov     [state.index],MT_SIZE
  8.  
  9.         mov     eax,[dValue]
  10.         mov     [state.mt],eax
  11.  
  12.         mov     ecx,1
  13. @@:
  14.         mov     eax,[state.mt+ecx*4-4]
  15.         mov     ebx,eax
  16.         shr     ebx,30
  17.         xor     eax,ebx
  18.         xor     edx,edx
  19.         mov     ebx,0x6C078965
  20.         mul     ebx
  21.         add     eax,ecx
  22.         mov     [state.mt+ecx*4],eax
  23.  
  24.         inc     ecx
  25.         cmp     ecx,MT_SIZE
  26.         jb      @b
  27.  
  28.         popa
  29.         ret
  30. endp
Следующая функция возвращает случайное число. Никаких входных параметров не предусмотрено, на выходе в регистре EAX сгенерированное число.
  1. ;---------------------------------------------
  2. ; Получить случайное число
  3. ; stdcall mt_rand
  4. ; на выходе EAX - случайное число
  5. ;---------------------------------------------
  6. proc mt_rand
  7.         pusha
  8.  
  9.         cmp     [state.index],MT_SIZE
  10.         jne     .loc_ret
  11.  
  12.         xor     ecx,ecx
  13. .loc_loop:
  14.         mov     eax,[state.mt+ecx*4]
  15.         and     eax,0x80000000
  16.         mov     ebx,[state.mt+ecx*4+4]
  17.         and     ebx,0x7FFFFFFF
  18.         or      eax,ebx
  19.  
  20.         mov     ebx,eax
  21.         shl     ebx,31
  22.         shr     ebx,31
  23.         and     ebx,0x9908B0DF
  24.  
  25.         shr     eax,1
  26.         xor     eax,ebx
  27.  
  28.         mov     ebx,[state.mt+ecx*4+PERIOD*4]
  29.         cmp     ecx,DIFF
  30.         jb      @f
  31.         mov     ebx,[state.mt+ecx*4-DIFF*4]
  32. @@:
  33.         xor     eax,ebx
  34.  
  35.         mov     [state.mt+ecx*4],eax
  36.  
  37.         inc     ecx
  38.         cmp     ecx,(MT_SIZE-1)
  39.         jb      .loc_loop
  40.  
  41.         mov     eax,[state.mt+(MT_SIZE-1)*4]
  42.         and     eax,0x80000000
  43.         mov     ebx,[state.mt]
  44.         and     ebx,0x7FFFFFFF
  45.         or      eax,ebx
  46.  
  47.         mov     ebx,eax
  48.         shl     ebx,31
  49.         shr     ebx,31
  50.         and     ebx,0x9908B0DF
  51.  
  52.         shr     eax,1
  53.         xor     eax,ebx
  54.         xor     eax,[state.mt+(PERIOD-1)*4]
  55.         mov     [state.mt+(MT_SIZE-1)*4],eax
  56.  
  57.         ; temper
  58.         xor     ecx,ecx
  59. .loc_temper:
  60.         mov     eax,[state.mt+ecx*4]
  61.  
  62.         mov     ebx,eax
  63.         shr     ebx,11
  64.         xor     eax,ebx
  65.  
  66.         mov     ebx,eax
  67.         shl     ebx,7
  68.         and     ebx,0x9D2C5680
  69.         xor     eax,ebx
  70.  
  71.         mov     ebx,eax
  72.         shl     ebx,15
  73.         and     ebx,0xEFC60000
  74.         xor     eax,ebx
  75.  
  76.         mov     ebx,eax
  77.         shr     ebx,18
  78.         xor     eax,ebx
  79.  
  80.         mov     [state.mt_tempered+ecx*4],eax
  81.  
  82.         inc     ecx
  83.         cmp     ecx,MT_SIZE
  84.         jb      .loc_temper
  85.  
  86.         mov     [state.index],0
  87. .loc_ret:
  88.         inc     [state.index]
  89.  
  90.         mov     eax,[state.index]
  91.         mov     eax,[state.mt_tempered+eax*4]
  92.         mov     [esp+28],eax
  93.  
  94.         popa
  95.         ret
  96. endp
В приложении пример программы с исходным текстом, которая генерирует псевдослучайные числа с использованием Mersenne Twister.

Пример программы с исходным текстом (FASM)Пример программы с исходным текстом (FASM)

Mersenne.Twister.Demo.zip (3,258 bytes)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 328 | Комментариев: 1

Комментарии

Отзывы посетителей сайта о статье
voffka (01.07.2021 в 09:13):
ГОСТ-а на алгоритм нету, потому все реализации выдают разные результаты.
Попалась когда-то игра на .net с обфускацией, гугление 0x6C078965 привело на Mersenne Twister, первая часть ключа была как init, а все последующие части ключа как word от random.next. Испытал более десятка реализаций на разных языках и нифига общего, результаты везде разные.

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2021
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 2 (0.0042 сек.) / Память: 5 Mb
Наверх