Генератор ПСЧ

Здравствуйте. Я в этом мало чего понимаю, но есть желание понять. Читал, что можно сделать Вихрь Мерсенна на С++.

Помогите чайнику в этом вопросе. А именно нужно создать генератор псч в который можно будет вносить числа. а в зависимости от того какие числа внесены генератор бы выдавал последующие(в статье написано что для этого достаточно внести 624 цифры).


Вот может это поможет кому:

Вихрь Мерсенна состоит из двух частей: РСЛОС и закалки.
image
Регистр сдвига состоит из 624 элементов, каждый длиной 32 бита. Инициализация начального состояния описывается функцией:

function initialize_generator(int seed) {
index := 0
MT[0] := seed
for i from 1 to 623 { // loop over each other element
MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
}
}


На вход инициализационной функции подается некое значение seed, с помощью которого осуществляется заполнение всего регистра.

На первом и каждом последующем 624-м шаге происходит перемешивание внутреннего состояния регистра:

function generate_numbers() {
for i from 0 to 623 {
int y := (MT[i] & 0x80000000) // bit 31 (32nd bit) of MT[i]
+ (MT[(i+1) mod 624] & 0x7fffffff) // bits 0-30 (first 31 bits) of MT[...]
MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
if (y mod 2) != 0 { // y is odd
MT[i] := MT[i] xor (2567483615) // 0x9908b0df
}
}
}



На каждом шаге алгоритм возвращает следующее число из текущего состояния регистра и производит так называемую «закалку»:

function extract_number() {
if index == 0 {
generate_numbers()
}
int y := MT[index]
//закалка
y := y xor (right shift by 11 bits(y))
y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
y := y xor (right shift by 18 bits(y))

index := (index + 1) mod 624
return y
}



Для того чтобы получить доступ к внутреннему состоянию алгоритма атакующему достаточно получить последовательность состоящую из 624 чисел.
Все что нужно сделать это вернуть числа сгенерированные алгоритмом к состоянию, в котором они находились до этапа «закалки». Для этого необходимо проделать все шаги закалки в обратном направлении. Например, рассмотрим последний шаг закалки:
y := y ^ (y >>> 18)
Давайте посмотрим что происходит с двоичными данными при выполнении этой операции:
y        1011011101011110011111100111 0010
y >>> 18    0000000000000000001011011101011110011 1111001110010
y ^ (y >>> 18) 10110111010111100101001110100101
Как видите, первые 18 бит результата и исходного числа совпадают. Для того чтобы восстановить оставшиеся 14 бит нам нужно проделать следующее действие:
result ^ (result >>> 18)
Действуя аналогичным образом для всех шагов этапа закалки мы получим элемент начального состояния ГПСЧ:

private uint reverse(uint output)
{
uint tempout = output >> 18;
output = output ^ tempout;
tempout = output << 15;
output = (uint)(output ^ (tempout & 4022730752));
uint a = output << 7;
uint b = (uint)(output ^ (a & 2636928640));
uint c = b << 7;
uint d = (uint)(output ^ (c & 2636928640));
uint e = d << 7;
uint f = (uint)(output ^ (e & 2636928640));
uint g = f << 7;
uint h = (uint)(output ^ (g & 2636928640));
uint i = h << 7;
uint tempfinal = (uint)(output ^ (i & 2636928640));
uint k = tempfinal >> 11;
uint l = (uint)(tempfinal ^ k);
uint m = (uint)l >> 11;
uint final = (uint)(tempfinal ^ m);
return final;
}


Как я уже отмечал выше, если атакующий имеет 624 числа сгенерированных с помощью Вихря Мерсенна этого достаточно для того чтобы восстановить все внутреннее состояние и предугадывать с вероятностью 100% все генерируемые в последующем числа.

0

вот ещё нашёл

Взлом ГПСЧ Вихрь Мерсенна в PHP

Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. На этот раз будем анализировать реализацию алгоритма в исходном коде php версии 5.4.6.

Содержимое файла /ext/standard/basic_functions.h

#define MT_N (624)

/* rand.c */

php_uint32 state[MT_N+1]; /* state vector + 1 extra to not violate ANSI C */

php_uint32 *next; /* next random value is computed from here */

int left; /* can *next++ this many times before reloading */

unsigned int rand_seed; /* Seed for rand(), in ts version */

zend_bool rand_is_seeded; /* Whether rand() has been seeded */

zend_bool mt_rand_is_seeded; /* Whether mt_rand() has been seeded */

Содержимое файла /ext/standard/rand.c

#define N MT_N /* length of state vector */

#define M (397) /* a period parameter */

#define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */

#define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */

#define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */

#define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */

#define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))

/* {{{ php_mt_reload

*/

static inline void php_mt_reload(TSRMLS_D)


{

/* Generate N new values in state

Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
register php_uint32 *state = BG(state);

register php_uint32 *p = state;

register int i;
for (i = N - M; i--; ++p)

*p = twist(p[M], p[0], p[1]);

for (i = M; --i; ++p)

*p = twist(p[M-N], p[0], p[1]);

*p = twist(p[M-N], p[0], state[0]);

BG(left) = N;

BG(next) = state;

}

/* }}} */

/* {{{ php_mt_initialize

*/

static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state)


{

/* Initialize generator state with seed

See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.

In previous versions, most significant bits (MSBs) of the seed affect

only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
register php_uint32 *s = state;

register php_uint32 *r = state;

register int i = 1;
*s++ = seed & 0xffffffffU;

for( ; i < N; ++i ) {

*s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;

r++;

}

}

/* }}} */

/* {{{ php_mt_srand

*/

PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)


{

/* Seed the generator with a simple uint32 */

php_mt_initialize(seed, BG(state));

php_mt_reload(TSRMLS_C);

/* Seed only once */

BG(mt_rand_is_seeded) = 1;

}

/* }}} */

/* {{{ php_mt_rand

*/

PHPAPI php_uint32 php_mt_rand(TSRMLS_D)


{

/* Pull a 32-bit integer from the generator state

Every other access function simply transforms the numbers extracted here */

register php_uint32 s1;

if (BG(left) == 0) {

php_mt_reload(TSRMLS_C);

}

--BG(left);


s1 = *BG(next)++;

s1 ^= (s1 >> 11);

s1 ^= (s1 << 7) & 0x9d2c5680U;

s1 ^= (s1 << 15) & 0xefc60000U;

return ( s1 ^ (s1 >> 18) );

}
Можно заменить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)) в бинарном представление операция выглядит так


10110111010111100111111001110010 s1

0000000000000000001011011101011110011111 1001110010 s1 >> 18


10110111010111100101001110100101 s1 ^ (s1 >> 18)

Видно, что первые 18 бит (выделены жирным) остались без изменений.

Напишем две функции для инвертирования битового сдвига и xor
public static long unBitshiftRightXor(long value, long shift) {

// we part of the value we are up to (with a width of shift bits)


long i = 0;

// we accumulate the result here


long result = 0;

// iterate until we've done the full 32 bits


while (i * shift < 32) {

// create a mask for this part


long partMask = (-1 << (32 - shift)) >>> (shift * i);

// obtain the part


long part = value & partMask;

// unapply the xor from the next part of the integer

value ^= part >>> shift;

// add the part to the result

result |= part;

i++;

}

return result;

}
public static long unBitshiftLeftXor(long value, long shift, long mask) {

// we part of the value we are up to (with a width of shift bits)

long i = 0;

// we accumulate the result here


long result = 0;

// iterate until we've done the full 32 bits


while (i * shift < 32) {

// create a mask for this part


long partMask = (-1 >>> (32 - shift)) << (shift * i);

// obtain the part


long part = value & partMask;

// unapply the xor from the next part of the integer

value ^= (part << shift) & mask;

// add the part to the result

result |= part;

i++;

}

return result;

}
Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так


long value = output;

value = unBitshiftRightXor(value, 18);

value = unBitshiftLeftXor(value, 15, 0xefc60000);

value = unBitshiftLeftXor(value, 7, 0x9d2c5680);

value = unBitshiftRightXor(value, 11);
Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister , то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister, и сможем легко определить каждое последующее значение, запустив php_mt_reload для известного набора значений.

0