Программно предугадать значения Random

@Leooos · Регистрация: 24.12.2020

Студворк — интернет-сервис помощи студентам

Спустя столько времени у меня появился вопрос.
Возможно ли как-то предугадать программно значения Random для, допустим, отрезка в 100 чисел?
Или может перехватить эти цифры в процессе работы встроенной функции ?

@Leooos · 21.05.2022, 10:00 **[ТС]**

wizard41, Что же, весьма понятный пример.
А эти вот прерывания же по идее можно отслеживать, нет?

I can · 21.05.2022, 10:03

Сообщение от Leooos

можете подсказать название этого способа шифрования?

Не знаю, как называется, но задание было такое(для visual basic)

Задание: сформировать систему шифрования с помощью замены, с использованием случайного смещения протестировать ее.
Описание процессов шифрования и дешифрования
В работе используется шифрование сообщения за счет замены символа сообщения на другой. Этот символ формируется на основе символа из сообщения по некоторому правилу.
cod(ssi) = cod(si) +p1, где si – текущий исходный элемент, ssi - текущий зашифрованный элемент, p1 – число.
в этой работе используется случайное число. То есть текущий символ исходного сообщения изменяется формально так же в соответствии с выражением
Второй особенностью работы является то, что вместо арифметического сложения берется логическая операция XOR, которая инвертирует биты символа в соответствии со значением пароля.
m(i) = Int(Rnd(pass) * 32) Xor m(i), где m(i) – код символа сообщения, pass – пароль.
Датчик случайных чисел берет значения от 0 до 1, поэтому полученное значение умножаем на 32 (число букв в алфавите). Функция Int делает полученное число целым. Алгоритм получается компактным, а шифр более стойким. Криптоанализ, основанный на частоте появления символа в тексте, здесь не работает. Один и тот же символ исходного сообщения будет заменяться различными символами. Например, символ «а» исходного сообщения при повторении в тексте шифровки будет заменен на другой символ. Для проверки работы этого способа шифрования берут исходное сообщение из одинаковых знаков и получают шифровку из разных.
Функция XOR является симметричной. Двойное отрицание является утверждением. Для дешифрования используется такой же алгоритм, как и при шифровании. В отличие от первой лабораторной, где возможно превышение максимального значения кода символа, так как используется операция суммирования. Операция XOR не приводит к превышению максимального значения кода. Поэтому проверка выхода за границы не нужна.

@wizard41 · 21.05.2022, 10:05

Сообщение от Leooos

А эти вот прерывания же по идее можно отслеживать, нет?

Только путем конкретного вмешательства в АЛУ ЦПУ. Во всяком случае то был пример "вообще" Generic, т.е. применительно к отдельному одноядерному ЦП. В современных же многоядерных ситуация несколько сложнее, тем не менее не перестает носить такой характер. Разве что перераспределение нагрузок между ядрами происходит иначе.
Я эту тему разбирал еще в институтские годы, на примере i386 и КР586 процессорах. Много воды утекло с тех пор )

@Leooos · 21.05.2022, 10:11 **[ТС]**

I can, звучит интересно

Добавлено через 3 минуты
wizard41, значит, чисто в теории, возможно, это уже радует)

@OwenGlendower · 21.05.2022, 10:17

Сообщение от Leooos

Под перехватом, я предполагаю, по, допустим, первым 55 числам, предугадать оставшиеся 55, динамически отслеживая что-то

Чисто теоретически это возможно. НО! Это бы означало что в реализации класса или в алгоритме есть очень серьезная уязвимость. Несмотря на свою псевдослучайную природу значения которые он генерирует должны быть непредсказуемыми. Иначе это уже не генератор случайных чисел. Поэтому ответ на ваш вопрос - нет.

В тоже время у нас следующие варианты:

1. Если мы имеем доступ к памяти процесса и можем найти интересующий нас экземпляр Random, то создание его точной копии или перезапись его состоянии в нужное нам, даст нужный результат.

2. Если мы знаем что Random каждый раз создается заново и можем заставить чужой код использовать нужное нам значение seed, то мы получим необходимое.

@wizard41 · 21.05.2022, 12:23

Сообщение от OwenGlendower

Если мы знаем что Random каждый раз создается заново

Создание каждый раз нового экземпляра Random дороговато по ресурсам. Это как раз не рекомендуют делать.
Причем, именно пересоздание экземпляра при коротких сроках ведет к получению одинаковых (близких) к друг другу значений случайных чисел.

@Элд Хасп · 21.05.2022, 15:39

Сообщение от Leooos

чисто в теории, возможно, это уже радует)

Только если вы хакните систему и будете от неё получать это число.
Каким-то внешним (по отношении к системе) способом сделать это невозможно.

Но для вашей задачи это и не нужно: по, допустим, первым 55 числам, предугадать оставшиеся 55.

Для этого вам нужно получить полный список Random - он будет циклический.
И в этом списке найти ваши первые 55 чисел.

Добавлено через 1 минуту
Придётся только повозится с получением и хранением всего этого списка.

Добавлено через 57 секунд
Так же есть вероятность, что таких ключей в списке будет несколько.

Добавлено через 3 минуты
Leooos, и различайте генераторы случайный чисел и генераторы ПСЕВДОСЛУЧАЙНЫХ чисел.
Random относится ко вторым.
Для ГПСЧ, как отметил выше OwenGlendower, повторяемость последовательности ВАЖНАЯ и необходимая функция.
Она позволяет реализовывать, в том числе, повторяемость тестирования.
В целях безопасности (например, для шифрования) такие ГПСЧ не используются.

@wizard41 · 21.05.2022, 16:27

На деле же, вероятно сложно себе представить ситуацию, когда надо генерировать (псевдо)случайную последовательность и ее же детерминировать.
Как я ранее уже говорил, класс Random при инициализации принимает в качестве исходного состояния некоторое кол-во времени от старта системы, т.е. если мы заведем два или пять таких генераторов, то все они будут с одинаковым начальным состоянием.
В природе существуют более сложные генераторы, которые, все же являясь псевдо-сл, но предлагают более сильную непредсказуемость результатов.
Вопрос, на самом деле интересный; я об этом периодически задумывался, но до практики дело не дошло, в виду занятости. Например, мысли были такие: взять некий датчик, который щупает флуктуации питающей сети вторички (в ПК разумеется). На основании текущего шума генерировать seed - вот это уже будет более-менее настоящий ГСЧ.

@Элд Хасп · 21.05.2022, 17:22

Сообщение от wizard41

Например, мысли были такие: взять некий датчик, который щупает флуктуации питающей сети вторички

Зачем так сложно?
Типовая реализация основана на измерении теплового шума - использовалась в первых генераторах Intel.
Потом они заменили её на цифровые элементы с неопределённым состоянием - она быстрее и меньше потребляет.

@OwenGlendower · 21.05.2022, 18:14

Сообщение от Элд Хасп

Для этого вам нужно получить полный список Random - он будет циклический.

И очень длинный. У него же период повторения где-то 10^~50.

@wizard41 · 21.05.2022, 19:01

Сообщение от Элд Хасп

Для этого вам нужно получить полный список Random - он будет циклический.

Сообщение от OwenGlendower

И очень длинный. У него же период повторения где-то 10~50.

Интересное заявление. А если его ограничить какими-либо значениями, то почему он должен быть обязательно 10^50 ?

Добавлено через 4 минуты

Сообщение от Элд Хасп

основана на измерении теплового шума

Да да. Что-то в этом роде. Но если присмотреться, то это решение тоже не оригинальное. Тут будут наблюдаться тенденции

@OwenGlendower · 21.05.2022, 21:13

Сообщение от wizard41

Интересное заявление. А если его ограничить какими-либо значениями, то почему он должен быть обязательно 10^50 ?

Это вопрос к математикам. В моем понимании период у алгоритма не должен меняться при ограничении диапазона.

@Элд Хасп · 21.05.2022, 21:24

Сообщение от OwenGlendower

И очень длинный.

Знаю.
Но вижу только два способа решить задачу:
1) Заранее создать список и относительно быстро искать в нём ключ - требует большого хранилища под список и однократно очень много времени для его создания;
2) Генерить числа, пока не выпадет ключ - потребует много времени для поиска каждого ключа.

Предложенные варианты попытки подбора зерна - бесперспективны, поскольку неизвестно в каких условиях генерился исходный ключ: количество тиков, сколько раз перед выдачей ключа у экземпляра уже запрашивалось число.

Добавлено через 2 минуты

Сообщение от wizard41

Интересное заявление. А если его ограничить какими-либо значениями, то почему он должен быть обязательно 10^50 ?

Не обязательно.
Это зависит от применённого алгоритма.
Но у любого ГПСЧ есть цикл после которого всеь ряд повторяется.
Конкретно по Random - надо поискать по документации или анализировать исходники.

Добавлено через 1 минуту
Цикл не будет зависеть от диапазона, так как диапазон получается приведением метода NexDouble().

@Элд Хасп · 21.05.2022, 21:25

wizard41, Исходники:

C#
160
161
162
163
164
165
166
167
168
169
170
171
172
173
      public virtual int Next(int minValue, int maxValue) {
          if (minValue>maxValue) {
              throw new ArgumentOutOfRangeException("minValue",Environment.GetResourceString("Argument_MinMaxValue", "minValue", "maxValue"));
          }
          Contract.EndContractBlock();
          
          long range = (long)maxValue-minValue;
          if( range <= (long)Int32.MaxValue) {  
              return ((int)(Sample() * range) + minValue);
          }          
          else { 
              return (int)((long)(GetSampleForLargeRange() * range) + minValue);
          }
      }

Sample() и GetSampleForLargeRange() - возвращают double.

@wizard41 · 21.05.2022, 22:00

Сообщение от Элд Хасп

цикл после которого всеь ряд повторяется.

Согласен, но я двигаюсь в сторону ГСЧ, не со стороны .NET

Сообщение от OwenGlendower

Это вопрос к математикам.

Правильно подмечено, почему собственно, я и обратил внимание на него )

Сообщение от OwenGlendower

В моем понимании период у алгоритма не должен меняться при ограничении диапазона.

OwenGlendower, если мы ограничим колебание маятника в несколько узком диапазоне - продолжит ли он колебаться дальше со своей интенсивностью? Наверное нет.

Добавлено через 3 минуты
Элд Хасп, я не очень вникал в суть рандома в нете, но почему-то уверен в том, что он организован так, как я предполагал ранее. Приведение исходников смысла не меняет.

Добавлено через 3 минуты

Сообщение от Элд Хасп

C#
1
Contract.EndContractBlock();

Интересный момент...

@OwenGlendower · 21.05.2022, 22:07

Сообщение от wizard41

если мы ограничим колебание маятника в несколько узком диапазоне - продолжит ли он колебаться дальше со своей интенсивностью? Наверное нет.

Не вижу связи.

@wizard41 · 21.05.2022, 23:03

Сообщение от OwenGlendower

Не вижу связи.

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

Добавлено через 20 минут
OwenGlendower, вы можете программно управлять задействованными ресурсами процессора, в частности кешем и скоростью загрузки стека?

Добавлено через 5 минут
Можно пойти и дальше - дизассемблируем метод Random буквально по частям, и посмотрим, как долго эти части будут выполняться за машинные такты конкретно взятого процесора.

Добавлено через 4 минуты
В принципе, это равносильно исследованию чисел числа Пи, что вроде бы подразумевает чистую природу случайностей.

@OwenGlendower · 21.05.2022, 23:11

Сообщение от wizard41

Да, на первый взгляд кажется что это не совместимые вещи. Но это только на первый взгляд...
Прецедент создан, надо на него отвечать. При оказии, попытаюсь привести свои выкладки по поводу вопроса.

Будет интересно увидеть. Я же не говорю что связи нет, а только что я её не вижу.

Сообщение от wizard41

OwenGlendower, вы можете программно управлять задействованными ресурсами процессора, в частности кешем и скоростью загрузки стека?

Не могу, а зачем мне это? Чтобы влиять на Environment.TickCount?

@wizard41 · 21.05.2022, 23:17

Сообщение от OwenGlendower

Чтобы влиять на Environment.TickCount?

Вот! Мы подошли к корневому элементу вопроса - что хотел контролировать ТС. Он не сможет это сделать, пока не будет на уровне системы.

Добавлено через 1 минуту
Выполняемая инструкция в ЦПУ в данный момент не подвластна его программе...

@OwenGlendower · 21.05.2022, 23:33

Сообщение от wizard41

Мы подошли к корневому элементу вопроса - что хотел контролировать ТС.

ТС интересуется можно ли предугадать значения Random. Возможность повлиять на Environment.TickCount или угадать его значение может оказаться полезной в этом смысле. Но ведь это не единственный способ атаки. И даже не факт что самый главный т.к. Environment.TickCount не используется в новых реализациях .NET. В случае с .NET FW я не знаю сколько приложений полагаются на конструктор по умолчанию. Мы например не полагаемся. У нас затравка генерируется с помощью RNGCryptoServiceProvider. Поэтому я бы скорее делал ставку на статический анализ или попытки украсть/испортить состояние генератора с помощью какой-нибудь Remote Code Execution атаки.

Сообщение от wizard41

Он не сможет это сделать, пока не будет на уровне системы.

Согласен. Но ТС не указал рамки своей задачи в плане где выполняется код Random - в нашем процессе? в другом процессе на локальной машине? На удаленной машине? Способы атак в этих случаях будут отличаться. И мне кажется что мы говорим о разных вещах, именно потому что имеем в виду разные сценарии.

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.

@Leooos 13 / 9 / 4 Регистрация: 24.12.2020 Сообщений: 153

	Программно предугадать значения Random 20.05.2022, 23:05. Показов 3234. Ответов 59 Метки нет (Все метки) Спустя столько времени у меня появился вопрос. Возможно ли как-то предугадать программно значения Random для, допустим, отрезка в 100 чисел? Или может перехватить эти цифры в процессе работы встроенной функции ? 0

@Leooos 13 / 9 / 4 Регистрация: 24.12.2020 Сообщений: 153
	21.05.2022, 10:00 [ТС]
	wizard41, Что же, весьма понятный пример. А эти вот прерывания же по идее можно отслеживать, нет? 0

@Leooos 13 / 9 / 4 Регистрация: 24.12.2020 Сообщений: 153
	21.05.2022, 10:11 [ТС]
	I can, звучит интересно Добавлено через 3 минуты wizard41, значит, чисто в теории, возможно, это уже радует) 0

@wizard41 3460 / 2781 / 575 Регистрация: 04.09.2018 Сообщений: 8,743 Записей в блоге: 3
	21.05.2022, 16:27
	На деле же, вероятно сложно себе представить ситуацию, когда надо генерировать (псевдо)случайную последовательность и ее же детерминировать. Как я ранее уже говорил, класс Random при инициализации принимает в качестве исходного состояния некоторое кол-во времени от старта системы, т.е. если мы заведем два или пять таких генераторов, то все они будут с одинаковым начальным состоянием. В природе существуют более сложные генераторы, которые, все же являясь псевдо-сл, но предлагают более сильную непредсказуемость результатов. Вопрос, на самом деле интересный; я об этом периодически задумывался, но до практики дело не дошло, в виду занятости. Например, мысли были такие: взять некий датчик, который щупает флуктуации питающей сети вторички (в ПК разумеется). На основании текущего шума генерировать seed - вот это уже будет более-менее настоящий ГСЧ. 0