Как вскрыть линейный конгруэнтный генератор псевдослучайных чисел? В учебных целях, я хочу взломать самый простой ГПСЧ.
Здесь могут помочь даже те, кто не знает про линейный конгруэнтный генератор или про гпсч в принципе, т.к. вопрос в недопонимании английского текста и немного математики.
Для вас вкратце: Есть такая штука как генератор псевдослучайных чисел. т.е. рандом, если проще. "Псевдослучайные" они потому что они не случайны, но похожи на таковые. Одна из реализаций такого генератора:
Xn+1=(aXn+c) mod m
Где Xn – это n-ый член последовательности. Переменные a, c и m – постоянные: a – множитель, c – инкремент, m – модуль. X0 – начальное значение.
Мои условия взлома:
1. Мы знаем, что генератор основан на линейном конгруэнтном методе.
2. Мы не знаем a, c и m.
3. Мы можем получить любые члены последовательности.
Задача: определить a,c,m (с большей вероятностью).
Несколько способов нашел в английском варианте. Мне нужен любой из них или другой, который я не знаю.
На этом сайте решают это брутфорсом. Единственное, там дана не вся последовательность, а каждый второй член. Поэтому, насколько я понял, проделывать PowerMod не нужно. Вопросы по этому способу следующие:
1. Я правильно понял, что второй код реализован потому, что первый выдавал два результата, а нам нужен один?
2. Вопрос по модульной арифметике: Как получили, что c = X2 - ((X1 * a) % m) (в первом коде)?
3. Почему m
Как вскрыть линейный конгруэнтный генератор псевдослучайных чисел? В учебных целях, я хочу взломать самый простой ГПСЧ.
Здесь могут помочь даже те, кто не знает про линейный конгруэнтный генератор или про гпсч в принципе, т.к. вопрос в недопонимании английского текста и немного математики.
Для вас вкратце: Есть такая штука как генератор псевдослучайных чисел. т.е. рандом, если проще. "Псевдослучайные" они потому что они не случайны, но похожи на таковые. Одна из реализаций такого генератора:
Xn+1=(aXn+c) mod m
Где Xn – это n-ый член последовательности. Переменные a, c и m – постоянные: a – множитель, c – инкремент, m – модуль. X0 – начальное значение.
Мои условия взлома:
1. Мы знаем, что генератор основан на линейном конгруэнтном методе.
2. Мы не знаем a, c и m.
3. Мы можем получить любые члены последовательности.
Задача: определить a,c,m (с большей вероятностью).
Несколько способов нашел в английском варианте. Мне нужен любой из них или другой, который я не знаю.
На этом сайте решают это брутфорсом. Единственное, там дана не вся последовательность, а каждый второй член. Поэтому, насколько я понял, проделывать PowerMod не нужно. Вопросы по этому способу следующие:
1. Я правильно понял, что второй код реализован потому, что первый выдавал два результата, а нам нужен один?
2. Вопрос по модульной арифметике: Как получили, что c = X2 - ((X1 * a) % m) (в первом коде)?
3. Почему m
Здесь могут помочь даже те, кто не знает про линейный конгруэнтный генератор или про гпсч в принципе, т.к. вопрос в недопонимании английского текста и немного математики.
Для вас вкратце: Есть такая штука как генератор псевдослучайных чисел. т.е. рандом, если проще. "Псевдослучайные" они потому что они не случайны, но похожи на таковые. Одна из реализаций такого генератора:
Xn+1=(aXn+c) mod m
Где Xn – это n-ый член последовательности. Переменные a, c и m – постоянные: a – множитель, c – инкремент, m – модуль. X0 – начальное значение.
Мои условия взлома:
1. Мы знаем, что генератор основан на линейном конгруэнтном методе.
2. Мы не знаем a, c и m.
3. Мы можем получить любые члены последовательности.
Задача: определить a,c,m (с большей вероятностью).
Несколько способов нашел в английском варианте. Мне нужен любой из них или другой, который я не знаю.
На этом сайте решают это брутфорсом. Единственное, там дана не вся последовательность, а каждый второй член. Поэтому, насколько я понял, проделывать PowerMod не нужно. Вопросы по этому способу следующие:
1. Я правильно понял, что второй код реализован потому, что первый выдавал два результата, а нам нужен один?
2. Вопрос по модульной арифметике: Как получили, что c = X2 - ((X1 * a) % m) (в первом коде)?
3. Почему m
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
По ссылкам можно изучить дополнительные материалы по модульной арифметике и обоснованию использования определенных чисел в ГПСЧ.