Статья 'Реконструкция и исследование датчика псевдослучайных чисел в VBA-подсистеме Microsoft Office' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Редакция и редакционный совет > Порядок рецензирования статей > Политика издания > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала

Публикация за 72 часа - теперь это реальность!
При необходимости издательство предоставляет авторам услугу сверхсрочной полноценной публикации. Уже через 72 часа статья появляется в числе опубликованных на сайте издательства с DOI и номерами страниц.
По первому требованию предоставляем все подтверждающие публикацию документы!
ГЛАВНАЯ > Вернуться к содержанию
Кибернетика и программирование
Правильная ссылка на статью:

Реконструкция и исследование датчика псевдослучайных чисел в VBA-подсистеме Microsoft Office

Бородин Андрей Викторович

кандидат экономических наук

профессор, кафедра информатики и системного программирования, ФГБОУ ВПО «Поволжский государственный технологический университет»

424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3

Borodin Andrey Viktorovich

PhD in Economics

Professor, Department of Computer Science and System Programming, Volga State University of Technology

424000, Russia, respublika Marii El, g. Ioshkar-Ola, pl. Lenina, 3

bor@mari-el.com
Другие публикации этого автора
 

 

DOI:

10.7256/2306-4196.2014.4.12648

Дата направления статьи в редакцию:

01-08-2014


Дата публикации:

15-08-2014


Аннотация.

В статье рассмотрены некоторые аспекты практического использования датчиков псевдослучайных чисел (ДПСЧ) в вычислительной математике и криптографии. В частности исследовано неадекватное поведение метода Монте-Карло при решении задачи оценки риска однородного кредитного портфеля с использованием штатного ДПСЧ системы программирования Microsoft Office. Выявлены ограничения штатного ДПСЧ. Проведена его реконструкция в терминах одномодульной арифметики вычетов и на этой основе показана нецелесообразность его использования в криптографических приложениях и объяснены отдельные аспекты неадекватного поведения метода Монте-Карло в модельном примере. Предложен вариант использования альтернативного ДПСЧ, основанного на идее "вихря Мерсенна", для решения сложных задач вычислительной математики. Приведены результаты соответствующих численных экспериментов. В основу работы положен ряд численных экспериментов, базирующихся на методе Монте-Карло. При реконструкции и исследовании ДПСЧ системы программирования Microsoft Office использованы теоретико-числовые методы. При постановке модельной задачи и интерпретации результатов ее решения используется теоретико-вероятностный формализм. В работе впервые проведено сравнение результатов оценки меры риска "Value at Risk" для однородного кредитного портфеля, полученных с использованием метода Монте-Карло, с точным значением, рассчитанным с использованием методов алгебраической теории риска. На этой основе выявлены ограничения подходов, основанных на методах Монте-Карло и связанных с конкретной реализацией штатного ДПСЧ системы программирования Microsoft Office. Предложено альтернативное решение и показана его адекватность в ходе соответствующего численного эксперимента.

Ключевые слова: риск, VBA, криптография, метод Монте-Карло, линейный конгруэнтный метод, псевдослучайное число, случайное число, мера риска, Value at Risk, вихрь Мерсенна

УДК:

004.421.5:519.245:336.77

Abstract.

The article reviews some aspects of practical use of the pseudo-random number sensors in computational mathematics and cryptography. In particular the author studied inappropriate behavior of the Monte Carlo method in solving the task of risk assessment of uniform credit portfolio using regular pseudo-random number sensor of the Microsoft Office programming system. The article identifies limits of the regular pseudo-random number sensor. The author reconstructs it in terms of single-module residue arithmetic and on that basis proves unreasonableness of its use in cryptographic applications and explained certain aspects of inadequate behavior of the Monte Carlo in the given example. The article proposes a solution as alternative pseudo-random number sensor based on the Mersenne twister for solving the complex tasks of computational mathematics. The article shows results of corresponding numerical experiments. The research is based on the numerical experiments based on the Monte Carlo method. The reconstruction and study of the pseudo-random number sensor of the Microsoft Office programming system involved number and theoretic methods. Probability theory formalism is used in formulating of the model problem and interpreting the results of its solution. The paper for the first time shows the comparison of the "Value at Risk" results for a task of risk assessment of uniform credit portfolio received using Monte Carlo method with exact values, calculated using the methods of the algebraic theory of risk. This comparison allowed to determine the limitations for Monte Carlo based methods and other methods using regular pseudo-random number sensor of the Microsoft Office programming system. The author proposes alternative solution for the problem and shows its adequacy in the corresponding numerical experiment.

Keywords:

risk, VBA, cryptography, Monte Carlo method , linear congruential method , pseudo-random number , random number, risk measure, Value at Risk , Mersenne twister

Введение

Случайные числа играют огромную роль как минимум в нескольких отраслях прикладной математики. В первую очередь – это криптография. Один из канонических классов случайности, равномерная случайность, в сочетании с определенными требованиями к процедуре шифрования, а именно совпадение или преобладание мощности алфавита ключа над мощностью алфавита сообщения в условиях использования одноразовых ключей, обеспечивают существование теоретически стойких криптосистем [23]. Трудно переоценить роль источников случайности и в проблематике криптографических протоколов [24]. Другое важнейшее приложение генераторов случайных чисел в прикладной математике – это широкий класс численных методов, который очень условно можно разделить на два подкласса: «методы случайного поиска» и «методы Монте-Карло». Методы случайного поиска на современном уровне развития вычислительной техники оказываются порой единственным эффективным способом решения некоторых высокоразмерных многоэкстремальных оптимизационных задач [5]. Ряд задач обучения нейронных сетей также может быть описан в терминах случайного поиска [14]. Класс методов, объединяемых термином «методы Монте-Карло», незаменим при решении задач нахождения значений интегралов высокой и сверхвысокой кратности. Это огромный диапазон различных приложений: от теории переноса до численных экспериментов в такой абстрактной области теоретической физики, как теория струн. Финансовый инжиниринг (портфельное моделирование, сценарный анализ, стресс-тестирование) – другой утилизатор методологии Монте-Карло [1, 4].

В то же время получение истинно случайных чисел в вычислительных устройствах с «чистой» архитектурой фон Неймана не возможно. Использование младших разрядов часов с осциллятором, независимым от тактового генератора процессора, или некоторой непредсказуемости взаимодействия человека с устройствами ввода информации (клавиатура, мышь и т. п.) в качестве источника случайности в названных выше приложениях не эффективно. Качество случайности здесь не велико, а быстродействие источников очень низкое. В связи с этим, для получения случайных чисел высокого качества используются, как правило, специальные аппаратные устройства, использующие физические случайные процессы с высокостабильными характеристиками случайности. Такие устройства дороги и стоимость их быстро возрастает с ростом быстродействия. Для преодоления этого неудобства широко используются генераторы псевдослучайных чисел (ГПСЧ). Практически все современные системы программирования содержат встроенные ГПСЧ. ГПСЧ порождают последовательности чисел, которые похожи на случайные по своим статистическим свойствам. Однако случайными эти последовательности не являются – они периодические, хотя период повторения может быть очень большим.

Каковы границы применимости того или иного ГПСЧ вместо источника истинно случайных чисел при решении той или иной задачи? Этот вопрос является вопросом номер один в отмеченных разделах прикладной математики.

Цель работы

Подсистема программирования Visual Basic for Application (VBA) системы автоматизации офисной деятельности Microsoft Office является основой огромного количества программных средств моделирования. Речь идет о программных продуктах в области финансового инжиниринга, в сфере оптимизации технических решений по критерию совокупной стоимости владения, в задачах конкурентного выбора дефицитного ресурса и т. п. Многие из этих продуктов используют методологию случайного поиска и методы Монте-Карло. С другой стороны, в документации на пакет Microsoft Office практически отсутствует информация о ГПСЧ, реализованном в соответствующей системе программирования. Не добавляют ясности в этот вопрос и статьи службы поддержки компании Microsoft, см., например, описание функции RAND [10], после прочтения которого остается больше вопросов, чем ответов. В связи с выше изложенным, в качестве цели данной работы было выбрано исследование практических аспектов использования ГПСЧ подсистемы VBA Microsoft Office в практике применения метода Монте-Карло в задачах финансового анализа. Другая цель работы – оценка допустимости применения обсуждаемого ГПСЧ для нужд элементарных криптографических приложений. Еще одной целью данной работы является реконструкция соответствующего ГПСЧ в терминах целочисленной арифметики. Последняя цель важна с позиций переноса огромного багажа теоретических знаний, накопленных в области линейных конгруэнтных методов генерации псевдослучайных чисел, на конкретную реализацию ГПСЧ.

Метод исследования

Исходя из поставленных целей, очевидно, что основными инструментами исследования будут различные численные эксперименты, базирующиеся на методе Монте-Карло, и прямые методы исследования ГПСЧ, основанные на теоретико-числовых методах. В качестве вспомогательного инструмента, несущего в основном описательную нагрузку, будет использован теоретико-вероятностный формализм.

Задача оценки риска розничного кредитного портфеля

Процесс управления кредитным риском включает в себя качественный и количественный аспекты [15]. Качественный аспект заключается в определении кредитоспособности (надежности) заемщика или контрагента. Современный подход к количественной оценке кредитного риска основывается на концепции «Value at Risk» [9, 16, 17], ставшей общепринятым стандартом для оценки рыночных рисков. Применение данного подхода к оценке риска на уровне кредитного портфеля предполагает построение распределения случайной величины финансового результата по портфелю на каком-либо горизонте планирования и вычисления соответствующего квантиля распределения. Вычисление квантиля и есть измерение риска, ассоциированного со случайностью величины финансового результата.

В основу подхода к моделированию кредитного портфеля банка традиционно была положена идея независимого создания сценарных моделей отдельных кредитных договоров с последующим совместным анализом произвольной совокупности таких моделей [2].

При анализе кредитного риска большинства ссудных портфелей удобно использовать модель типового кредитного договора, включающую следующие четыре сценария [11, 13]:

1) течение кредитного договора без осложнений;

2) однократное или многократное возникновение устраненной просроченной задолженности;

3) сценарий успеха процедуры реализации залога в случае неустраненной просроченной задолженности;

4) списание безнадежной ссудной задолженности.

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

Предположим, что на момент закрытия некоторой позиции по каждому из независимых активов приведенный платежный баланс представлен случайной величиной `X_i` , `i=1, 2, ... , n` . Эти случайные величины будем считать попарно независимыми. Суммарный приведенный платежный баланс на момент закрытия позиции в таком случае составит:

`S_n=sum_(i=1)^n X_i` .

Известно [7], что если `X_1` , `X_2` , … , `X_n` – случайные величины с конечными математическими ожиданиями, то математическое ожидание их суммы существует и равно сумме их математических ожиданий:

`E(sum_(i=1)^n X_i)=sum_(i=1)^n E(X_i)` . (1)

Отсюда сразу следует линейность зависимости математического ожидания, как одной из мер риска, от объема портфеля.

Также известно [7], что если `X_1` , `X_2` , … , `X_n` – случайные величины с конечными дисперсиями и при этом они попарно независимы, то дисперсия их суммы равна сумме их дисперсий (равенство Бьенэйме):

`D(sum_(i=1)^n X_i)=sum_(i=1)^n D(X_i)` . (2)

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

Для меры риска «Value at Risk», к сожалению, не известны простые соотношения, аналогичные (1) и (2). Один из традиционных подходов к оценке этой меры риска основан на использовании метода Монте-Карло [1]. Для случая, когда портфель однороден, иначе говоря состоит из (примерно) одинаковых инструментов, в последние годы разработан метод точной оценки меры риска «Value at Risk» [12]. Используя этот результат, можно объективно исследовать поведение метода Монте-Карло.

Использование метода Монте-Карло для моделирования кредитного портфеля в указанной постановке тривиально. Каждое испытание включает в себя генерацию одного равномерно распределенного на отрезке `[0, 1]` псевдослучайного числа на каждый договор. После чего осуществляется проверка попадания этого числа в один из интервалов постоянства кумулятивной вероятности для модели договора. Финансовым результатом считается платежный баланс по сценарию договора, соответствующему правому концу интервала (разрыву кумулянты). В ходе суммирования финансовых результатов по всем договорам вычисляется итоговый платежный баланс по всему портфелю. То есть формируется финансовый результат по одному испытанию метода Монте-Карло. Учитывая равномерность исходного распределения, испытания представляют выборочное распределение финансового результата по портфелю, по которому можно оценить любую меру риска, в том числе и «Value at Risk». Чем больше испытаний, тем ближе выборочное распределение к теоретическому.

В качестве примера будем исследовать однородный портфель кредитных договоров «На неотложные нужды». Средний объем одного кредита – 90 тыс. рублей. Годовая ставка – 19%. Система выплат по договору – аннуитетная постнумерандо. Вероятности реализации сценариев составляют 0.63, 0.12, 0.11 и 0.14 соответственно. Средние затраты, связанные с устранением просроченной задолженности по одному договору, составляют 5 тыс. рублей. При списании безнадежной ссудной задолженности по неисполненному кредитному договору наряду с потерями возникают дополнительные затраты, связанные с соответствующей операционной деятельностью. Эти затраты для такого договора составляют в среднем 18 тыс. рублей. Перечисленные исходные данные будем использовать во всех численных экспериментах, связанных с методом Монте-Карло.

Рассмотрим зависимость меры риска «Value at Risk» на уровне вероятности 0.01 от количества инструментов в этом портфеле на фоне испытаний метода Монте-Карло (см. рис. 1). Точные значения меры риска «Value at Risk» получены с использованием пакета прикладных программ «МультиМИР» [12]. По рисунку видно, что оценка квантиля на левом хвосте распределения – задача не тривиальная. Действительно, достаточно заметить, что существенно (в разы) преобладающая часть объема конуса носителей, расположенная ниже сосредоточения точек, соответствующих испытаниям, почти пуста. Это верный признак того, что для оценки меры риска «Value at Risk» с достаточной точностью понадобится весьма значительное количество испытаний.

ris1

Рис. 1. Зависимость меры риска «Value at Risk» от количества инструментов в портфеле (красная кривая) на фоне испытаний метода Монте-Карло (синие точки). Испытания ограничены конусом носителя. Конус носителя задан коричневым лучом снизу и зеленым сверху.

Рассмотрим однородный портфель, состоящий из 256 описанных выше кредитных договоров. Выбор числа 28 связан с желанием обострить проблемы, возникающие при использовании метода Монте-Карло с ГПСЧ системы программирования Microsoft Office. Почему этот выбор в указанном смысле эффективен будет ясно несколько позже. В результате первого численного эксперимента была получена зависимость оценки меры риска «Value at Risk» от количества испытаний метода Монте-Карло в диапазоне от 210 до 216, см. рис. 2.

ris2

Рис. 2. Зависимость оценки меры риска «Value at Risk» от количества испытаний метода Монте-Карло (синяя кривая) для модельного портфеля. Светло коричневая горизонтальная линия показывает точное значение оцениваемой меры риска. Наклонный красный отрезок прямой на второй половине графика показывает наличие очевидного тренда изменения оценки.

Если первая половина графика, представленного на рис. 2, не вызывает особых вопросов, то на второй половине графика происходит что-то странное: оценка целевой меры риска постепенно достигает точного значения, а затем примерно в том же темпе отдаляется от точного значения. Этот тренд линеен, его коэффициент детерминации `R^2=0.88` . Что происходит?

Для ответа на поставленный вопрос было решено провести второй численный эксперимент, в котором правая граница количества испытаний была отодвинута до величины 218. Данный вычислительный эксперимент потребовал существенно больший объем ресурса процессорного времени. Эта и последующие ресурсоемкие задачи, описанные в данной статье, относительно быстро были решены за счет распараллеливания на вычислительных мощностях специализированного учебного класса экономического факультета Поволжского государственного технологического университета, состоящего из 16 компьютеров с конфигурацией Core i7–2600/16Gb/1Tb/2 Gigabit Ethernet. Результаты второго численного эксперимента приведены на рис. 3.

ris3

Рис. 3. Зависимость оценки меры риска «Value at Risk» от количества испытаний метода Монте-Карло (синяя кривая) для модельного портфеля на учетверенном интервале количеств испытаний. Светло коричневая горизонтальная линия показывает точное значение оцениваемой меры риска.

Рис. 3 проливает некоторый свет на возникшую ситуацию. Совместим отрезки `[2^16, 2^17]` , `[2^17, 2^17+2^16]` и `[2^17+2^16, 2^18]` домена зависимости оценки целевой меры риска от количества испытаний и посмотрим на соответствующие части графика этой зависимости из областей II, III и IV (рис. 4). Очевидно наличие автокорреляции в исследуемой зависимости. На основе полученных данных можно выдвинуть гипотезу: период последовательности чисел, порождаемых ГПСЧ системы программирования Microsoft Office, равен `2^8xx2^16=2^24` . Повтор периода легко объясняет неизменность оценки целевой меры риска в конце I, II, III и IV областей графика на рис. 3 (или, иначе, невозможность дальнейшего улучшения оценки в областях II, III и IV). Пока остаются не ясными причины возникновения тренда во второй части графика на рис.2.

ris4

Рис. 4. Совмещенные графики зависимости оценки меры риска «Value at Risk» от количества испытаний из областей II, III и IV рисунка 3. Для наглядности графики сдвинуты по оси ординат друг относительно друга на величину, равную 4 тыс. рублей.

Реконструкция ГПСЧ системы программирования Microsoft Office

На первом этапе исследования ГПСЧ попробуем определить период псевдослучайной последовательности. Одновременно с этим проверим, встречается ли в этой последовательности нулевой элемент. Для этого выполним простейший код на языке программирования VBA (см. листинг 1).

Листинг 1

Const nPrint = 5 ' Кол-во выводимых элементов

Dim Count As Long ' Счетчик периода

Dim a As Double, b As Double

Dim i As Integer

Debug.Print

Debug.Print "Определение длины периода последовательности "+_

"ПСЧ методом перебора:"

' Вывод первых nPrint элементов

a = Rnd: Debug.Print a; ", ";

For i = 2 To nPrint

b = Rnd: Debug.Print b; ", ";

Next i

Debug.Print "... ,"

' Измерение длины периода

Count = nPrint

While b <> a

b = Rnd: Count = Count + 1

If b = 0# Then ' Проверка появления 0-го элемента

Debug.Print "(Элемент"; Count; "нулевой!)"

End If

Wend

' Вывод nPrint элементов после обнаружения повтора

For i = 1 To nPrint - 1

Debug.Print b; ", ";: b = Rnd

Next i

Debug.Print b; "."

' Вывод результатов измерения длины периода

Debug.Print "Период последовательности: "; Count - 1

Debug.Print "Log2(Count-1) = "; Log(Count - 1) / Log(2#)

В результате выполнения этого кода получаем результаты, представленные в листинге 2.

Листинг 2

Определение длины периода последовательности ПСЧ методом перебора:

0.774740099906921 , 0.014017641544342 , 0.76072359085083 , 0.814490020275116 , 0.709037899971008 , ... ,

(Элемент 6488059 нулевой!)

0.774740099906921 , 0.014017641544342 , 0.76072359085083 , 0.814490020275116 , 0.709037899971008 .

Период последовательности: 16777216

Log2(Count-1) = 24

Таким образом, наша гипотеза подтвердилась: период последовательности чисел, порождаемых ГПСЧ системы программирования Microsoft Office, равен `2^24` .

Теперь можно выдвинуть следующую гипотезу. Можно предположить, что для генерации псевдослучайных чисел `r_i` , `i=0, 1, ...` , с носителем `[0, 1]` в VBA Microsoft Office используется линейный конгруэнтный метод (ЛКМ) [6], определяемый следующим реккурентным соотношением:

`X_(i+1) = | aX_i + c |_m` , `i=0, 1, ...` , (3)

где `X_o` – начальный элемент, `X_0inZZ`, `0<=X_0<m` ; `a` – множитель, `ainZZ`, `0<=a<m` ; `c` – приращение, `cinZZ`, `0<=c<m`; `m` – модуль, `m in ZZ`, `m>0`; `ZZ` – множество целых чисел; `| * |_m` – обозначение наименьшего неотрицательного вычета по модулю `m`. Числа `X_0` , `a` , `c` и `m` однозначно определяют период последовательности псевдослучайных чисел, то есть они являются параметрами ЛКМ. Далее предположим, что используется линейная конгруэнтная последовательность максимального периода с модулем

`m = 2^24` , (4)

то есть используется ЛКМ с параметрами, для которых выполняются следующие соотношения (см. условия теоремы A [6, с. 29], адаптированные под заданный модуль ЛКМ):

`| c |_2 = 1` , (5)

`| a |_4 = 1` . (6)

Предположим также, что для приведения последовательности `{X_i}` к последовательности `{r_i}` с носителем `[0, 1]` используется операция деления:

`r_i = X_i / m` , `i=0, 1, ...` . (7)

Как мы видели выше, легко может быть найдено нулевое псевдослучайное число `r_j = 0` , порядковым номером которого является некоторое целое неотрицательное число `j` . Этим числам соответствует элемент `X_j = 0` последовательности `{X_i}` . Теперь, используя следующее псевдослучайное число и соотношения (3) и (7), можно найти приращение:

`mr_(j+1) = X_(j+1) = | c |_m = c` . (8)

Для псевдослучайного числа `r_(j+2)` с учетом соотношений (3), (7) и (8) можно записать:

`mr_(j+2) = X_(j+2) = | ac + c |_m = | (a+1) c |_m` . (9)

Заметим, что из соотношений (4) и (5) следует взаимная простота чисел `c` и `m` , что означает существование для `c` мультипликативно обратного по модулю `m` числа `| c^-1 |_m` . Умножив левую и правую части соотношения (9) на `| c^-1 |_m` в соответствующем кольце вычетов, получим:

`| mr_(j+2) (|c^-1|_m)|_m = r_(j+2) |c^-1|_m =`

`= | |(a+1)c|_m (|c^-1|_m) |_m = | (a+1)c (|c^-1|_m) |_m = | a+1 |_m` . (10)

Поскольку `r_(j+2)!= 0` , то `| a+1 |_m = a+1` . Из этого равенства и из соотношения (10) следует, что

`a = r_(j+2) |c^-1|_m -1` . (11)

Используя для вычисления мультипликативно обратного по модулю числа обобщенный алгоритм Евклида [3] и применяя формулы (8) и (11) к ГПСЧ системы программирования Microsoft Office, получаем:

`c=12820163` , (12)

`a=16598013` . (13)

Нетрудно убедится, что число (12) удовлетворяет соотношению (5), а число (13) – соотношению (6). Прямые вычисления окончательно подтверждают нашу гипотезу: ГПСЧ системы программирования Microsoft Office может быть описан в терминах ЛКМ (3) с параметрами (4), (12) и (13) в сочетании с нормировочным соотношением (7).

Отметим, что ЛКМ с параметрами (4), (12) и (13) достаточно хорошо известен и всесторонне протестирован. Обычно в литературе этот датчик ассоциируют с ГПСЧ системы программирования Microsoft Visual Basic 6.0, см., например, [8, 18]. В то же время, ассоциации данного датчика с ГПСЧ системы программирования VBA в сети Internet найдено не было!

Криптографические свойства ГПСЧ системы программирования Microsoft Office

Идея использования ЛКМ для получения ключевых последовательностей в системах поточного шифрования возникла достаточно давно. Используя ЛКМ, можно сформировать последовательность, похожую на последовательность случайных равномерно распределенных чисел. Эту последовательность можно использовать для поточного шифрования в условиях приближенного соблюдения требований к теоретически стойким криптосистемам. В результате, казалось бы, можно ожидать относительно высокую стойкость такого шифра при кардинальном снижении емкости секретного канала. Ожидаемая стойкость здесь тем выше, чем больше период псевдослучайной последовательности, а емкость секретного канала снижается с величины, не меньшей суммарного объема всех шифротекстов, до объема хранения всего лишь нескольких параметров ГПСЧ. Однако, к сожалению, сегодня известен целый ряд эффективных атак на такие системы, в том числе, не зависящих от длины периода. В качестве примера можно указать атаки с известным фрагментом шифруемого сообщения [21, 22].

Тем не менее, в отдельных случаях линейные конгруэнтные последовательности могут использоваться в криптографических протоколах, требующих для своей работы периодическое, но не слишком частое, использование чисел, вносящих случайность во внутренние состояния участников протокола. Другая возможная сфера применения таких последовательностей – составные системы шифрования, ориентированные на использование в асинхронных каналах передачи данных с ошибками. В этом случае поточное шифрование на линейных конгруэнтных последовательностях является вспомогательным средством, необходимым для выравнивания частоты встречаемости символов алфавита в сообщениях перед основной процедурой блочного шифрования, функционирующей в режиме простой замены. В обоих случаях важны статистические свойства ГПСЧ.

Исследуем статистические свойства ГПСЧ системы программирования Microsoft Office. Известно [6], что если

`|m|_d = 0` (14)

и

`Y_i = | X_i |_d` , `i = 0, 1, ...` , (15)

где `dinZZ` , `d > 1` , а последовательность `{X_i}` определяется соотношением (3), то

`Y_(i+1) = | aY_i + c |_d` , `i=0, 1, ...` . (16)

Другими словами последовательность, определяемая соотношением (15), также является линейной конгруэнтной с модулем `d` . В случае, когда `m` является степенью двойки, это означает интересный факт: чем младше бит псевдослучайного числа, порожденного соотношением (3), тем он менее случаен, см. рис. 5. На этом рисунке четырьмя цветами выделены самые короткие периоды: красным – длины 2, синим – длины 4, фиолетовым – длины 8, зеленым – длины 16.

ris5

Рис. 5. Фрагмент последовательности `{r_i}` в десятичном формате и соответствующий ему фрагмент последовательности ` {X_i} ` в двоичном представлении. На рисунке выделены периоды для групп младших битов (от 1 до 4).

Вывод здесь очевиден: использование ЛКМ (3) с параметрами (4), (12) и (13) для любых криптографических приложений крайне не желательно ввиду негативного влияния коротких периодов на стойкость. В случае же невозможности отказа от использования такого ГПСЧ в криптографических приложениях следует ограничиться использованием лишь старших битов элементов последовательности `{X_i}` .

Другие следствия статистической несостоятельности ГПСЧ системы программирования Microsoft Office

Особенности ГПСЧ системы программирования Microsoft Office, описываемые соотношениями (14), (15) и (16), негативно влияют не только на криптографические свойства генератора, но и на практику его использования в методах типа Монте-Карло и случайного поиска.

В качестве примера рассмотрим более подробно процессы, происходящие в рассмотренной ранее задаче оценки меры риска «Value at Risk» однородного кредитного портфеля с использованием метода Монте-Карло. Принцип оценки этой меры риска в рассматриваемой задаче может быть сформулирован следующим образом: выбор испытания, разделяющего носитель риска (случайной величины доходности) на две части – левую и правую. При этом количества испытаний, оказавшихся в левой и правой частях носителя, соотносятся как пороговая вероятность оцениваемой меры риска и единица за минусом этой вероятности. Граничное испытание считается относящимся к правой части.

Рассмотрим процесс оценки меры риска, изображенный на рис. 2. Соответствующий псевдослучайный процесс сложился таким образом, что к концу первой половины графика избыток испытаний метода Монте-Карло сформировался в левой части носителя. Действительно, график оценочного значения меры риска пересекает серединную линию сетки заметно выше истинного значения. При этом вертикальная линия сетки на рисунке, разделяющая график на две части, соответствует числу испытаний `2^15` и, соответственно, числу `2^8xx 2^15 = 2^23` применений функции Rnd языка программирования VBA. Иначе говоря, слева и справа от этой линии сетки укладывается ровно по одному периоду последовательности , определяемой соотношением (15) при `d = 2^23` , то есть в целом процесс на рис. 2 использовал ровно весь период последовательности `{X_i}`.

Теперь заметим следующую особенность последовательности `{X_i}` . Младшие 23 бита элементов этой последовательности повторяются с периодом 223, а в связи с тем, что последовательность `{X_i}` – линейная конгруэнтная последовательность с максимальным периодом, то относительно старшего бита ее элемента можно говорить, что во второй половине последовательности он инвертирован по отношению к биту соответствующего элемента первой половины. Обратим внимание еще на один факт. Старший бит элемента последовательности `{X_i}` определяет: больше или меньше 0.5 соответствующий элемент последовательности `{r_i}` . Таким образом, если первая половина последовательности обеспечила избыток испытаний в левой части носителя и завышенную оценку меры риска, то вторая половина к концу процесса гарантированно обеспечит в левой части недостаток испытаний и, соответственно, заниженную оценку меры риска. Ввиду равномерности распределения элементов последовательности `{Y_i}` процесс перехода от избытка к недостатку будет в среднем линейным. Этим объясняется наличие убывающего линейного тренда, выделенного на второй половине рис. 2. Обратим внимание: с точки зрения решаемой задачи этот тренд не несет никакой полезной информации, более того, его наличие вредно.

Можно сформулировать очередной вывод: в некоторых случаях применения метода Монте-Карло на базе ГПСЧ, описываемого соотношениями (3), (5), (6), (7) в условиях модуля вида `m = 2^k` , k `inZZ` , `k > 1` , следует ограничиться использованием лишь части периода псевдослучайной последовательности, не превышающей половину этого периода.

Численный эксперимент с «вихрем Мерсена»

Численный эксперимент с «вихрем Мерсена». В ходе исследования мы убедились в ограниченности возможностей встроенного ГПСЧ системы программирования Microsoft Office при решении некоторых задач методом Монте-Карло. В связи с этим возникает задача подбора более перспективной альтернативы штатному ГПСЧ. При этом в качестве критериев выбора следует учесть как статистические свойства генератора, так и возможности эффективной реализации в соответствующей системе программирования.

В 1997 году японскими математиками Макото Мацумото и Такудзи Нисимурой был предложен ГПСЧ, основанный на свойствах простых чисел Мерсена и в связи с этим получивший название «вихрь Мерсенна» [19]. Один из вариантов этого ГПСЧ, называемый MT19937, имеет огромный период, равный числу Мерсенна `2^19937 - 1` , обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для лучших известных линейных конгруэнтных генераторов это число измерений не превышает четырех, см. таблицу II в работе [19]) и может быть относительно эффективно реализован на 32-разрядных компьютерах.

Используя реализацию MT19937 на VBA [20] был проведен численный эксперимент по решению нашей задачи оценки меры риска портфеля. Результаты этого численного эксперимента приведены на рис. 6.

ris6

Рис. 6. Зависимость оценки меры риска «Value at Risk» от количества испытаний метода Монте-Карло с ГПСЧ MT19937 (синяя кривая) для модельного портфеля. Светло коричневая горизонтальная линия показывает точное значение оцениваемой меры риска.

Процесс Монте-Карло, представленный на рис. 6, вполне соответствует теоретическим представлениям о функционировании исследуемого метода и, таким образом, демонстрирует целесообразность использования ГПСЧ MT19937 вместо ГПСЧ, реализованного в VBA Microsoft Office, при решении задач, по крайней мере, рассматриваемого класса.

Выводы

В ходе исследования, представленного в данной статье, были получены следующие основные результаты:

1) выявлено некорректное поведение метода Монте-Карло при решении задач портфельного анализа высокой размерности, связанное с использованием штатного ГПСЧ Microsoft Office;

2) выполнена реконструкция штатного ГПСЧ Microsoft Office в терминах одномодульной арифметики вычетов;

3) исследованы механизмы возникновения проблем в работе метода Монте-Карло, связанные с выявленными ограничениями штатного ГПСЧ;

4) предложен вариант использования современного ГПСЧ MT19937 вместо штатного ГПСЧ, способный обеспечить корректное применение метода Монте-Карло в портфельном анализе при больших размерностях задач.

Кроме того, реконструкция штатного ГПСЧ Microsoft Office в терминах одномодульной арифметики вычетов, позволила исследовать некоторые аспекты (ограничения) применения его в криптографических приложениях. Знание арифметической структуры, представленной соотношениями (3), (4), (7), (12) и (13), позволит в дальнейшем исследовать возможности и ограничения использования этого ГПСЧ в любых других приложениях теоретико-числовыми методами.

Библиография
1.
Алескеров, Ф. Т. Анализ математических моделей Базель II / Ф. Т. Алескеров, И. К. Андриевская, Г. И. Пеникас, В. М. Солодков. – М.: ФИЗМАТЛИТ, 2013. – 296 с.
2.
Бородин, А. В. Математические модели управления кредитным портфелем коммерческого банка / А. В. Бородин. – Йошкар-Ола: МарГТУ, 1998. – 168 с.
3.
Грегори, Р. Безошибочные вычисления. Методы и приближения / Р. Грегори, Е. Кришнамурти. – М.: Мир, 1988. – 208 с.
4.
Джекел, П. Применение методов Монте-Карло в финансах / П. Джекел. – М.: Интернет-трейдинг, 2004 – 263 с.
5.
Жиглявский, А. А. Методы поиска глобального экстремума / А. А. Жиглявский, А. Г. Жилинскас. – М.: Наука, 1991. – 248 с.
6.
Кнут, Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. – М.: Мир, 1977. – 727 с.
7.
Лоэв, М. Теория вероятностей / М. Лоэв. – М.: Изд-во иностранной литературы, 1962. – 719 с.
8.
Миненко, А. И. Экспериментальное исследование эффективности тестов для проверки генераторов случайных чисел / А. И. Миненко // Вестник СибГУТИ. – 2010. – №4. – С. 36-46.
9.
Мурзаев, С. В. Проблема выбора метода при оценке риска портфеля финансовых активов / С. В. Мурзаев // Тренды и управление. – 2013. – №1. – C. 72-77.
10.
Описание функции RAND в Excel 2007 и в Excel 2003 // Microsoft. Поддержка. – URL: http://support.microsoft.com/kb/828795/ru. Дата обращения: 04.07.2014.
11.
Уразаева, Т. А. Алгебраическая система рисков и ее приложения в сфере кредитования / Т. А. Уразаева // Вестник Поволжского государственного технологического университета. Серия: Экономика и управление. – 2012. – №1(15). – С. 24-31.
12.
Уразаева, Т. А. Алгебра рисков / Т. А. Уразаева. – Йошкар-Ола: Поволжский государственный технологический университет, 2013. – 209 с.
13.
Уразаева, Т. А. Пакет прикладных программ «МультиМир» в практике анализа кредитного риска / Т. А. Уразаева // VIII Международная научно-методическая конференция «Совершенствование подготовки IT-специалистов по направлению «Прикладная информатика» для инновационной экономики»: Сборник научных трудов. – М.: Московский государственный университет экономики, статистики и информатики, 2012. – С. 182-186.
14.
Хайкин, С. Нейронные сети: полный курс / С. Хайкин. – М.: Издательский дом «Вильямс», 2006. – 1104 с.
15.
Энциклопедия финансового риск-менеджмента / под ред. А. А. Лобанова и А. В. Чугунова. – М.: Альпина Паблишер, 2003. – 786 с.
16.
Holton, G. A. Value-at-Risk: Theory and Practice / G. A. Holton. – Academic Press, 2003. – 405 p.
17.
Jorion, P. Value at Risk: The New Benchmark for Managing Financial Risk / P. Jorion. – McGraw-Hill, 2006. – 543 p.
18.
Lomont, C. Random Number Generation / C. Lomont. – URL: http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf. Дата обращения: 18.07.2014.
19.
Matsumoto, M. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator / M. Matsumoto, T. Nishimura // ACM Transactions on Modeling and Computer Simulation (TOMACS). Special issue on uniform random number generation. – 1998. – Vol. 8. – Iss. 1. – P. 3-30. – DOI:10.1145/272991.272995.
20.
Mersenne Twister VBA Class // Directory of Open Source for Quan-titative Finance and Trading. – URL: http://www.quantcode.com/modules/mydownloads/singlefile.php?cid=9&lid=610/. Дата обращения: 18.07.2014.
21.
Reeds, J. Cracking a multiplicative congruential encryption algorithm / J. Reeds // Information Linkage Between Applied Mathematics and Industry (Proc. First Annual Workshop, Naval Postgraduate School, Monterey, Calif., 1978). – New York: Academic Press, 1979. – P. 467-472.
22.
Reeds, J. "Cracking" a Random Number Generator / J. Reeds // Cryptologia. – 1977. – Vol. 1. – No. 1. – P. 20-26.
23.
Shannon, C. E. Communication Theory of Secrecy Systems / C. E. Shannon // Bell Systems Technical Journal. – 1949. – Vol. 28. – P. 656-715.
24.
Vaudenay, S. A Classical Introduction to Cryptography: Applications for Communications Security / S. Vaudenay. – New York: Springer, 2006. – 335 p.
References (transliterated)
1.
Aleskerov, F. T. Analiz matematicheskikh modelei Bazel' II / F. T. Aleskerov, I. K. Andrievskaya, G. I. Penikas, V. M. Solodkov. – M.: FIZMATLIT, 2013. – 296 s.
2.
Borodin, A. V. Matematicheskie modeli upravleniya kreditnym portfelem kommercheskogo banka / A. V. Borodin. – Ioshkar-Ola: MarGTU, 1998. – 168 s.
3.
Gregori, R. Bezoshibochnye vychisleniya. Metody i priblizheniya / R. Gregori, E. Krishnamurti. – M.: Mir, 1988. – 208 s.
4.
Dzhekel, P. Primenenie metodov Monte-Karlo v finansakh / P. Dzhekel. – M.: Internet-treiding, 2004 – 263 s.
5.
Zhiglyavskii, A. A. Metody poiska global'nogo ekstremuma / A. A. Zhiglyavskii, A. G. Zhilinskas. – M.: Nauka, 1991. – 248 s.
6.
Knut, D. Iskusstvo programmirovaniya dlya EVM. T. 2. Poluchislennye algoritmy. – M.: Mir, 1977. – 727 s.
7.
Loev, M. Teoriya veroyatnostei / M. Loev. – M.: Izd-vo inostrannoi literatury, 1962. – 719 s.
8.
Minenko, A. I. Eksperimental'noe issledovanie effektivnosti testov dlya proverki generatorov sluchainykh chisel / A. I. Minenko // Vestnik SibGUTI. – 2010. – №4. – S. 36-46.
9.
Murzaev, S. V. Problema vybora metoda pri otsenke riska portfelya finansovykh aktivov / S. V. Murzaev // Trendy i upravlenie. – 2013. – №1. – C. 72-77.
10.
Opisanie funktsii RAND v Excel 2007 i v Excel 2003 // Microsoft. Podderzhka. – URL: http://support.microsoft.com/kb/828795/ru. Data obrashcheniya: 04.07.2014.
11.
Urazaeva, T. A. Algebraicheskaya sistema riskov i ee prilozheniya v sfere kreditovaniya / T. A. Urazaeva // Vestnik Povolzhskogo gosudarstvennogo tekhnologicheskogo universiteta. Seriya: Ekonomika i upravlenie. – 2012. – №1(15). – S. 24-31.
12.
Urazaeva, T. A. Algebra riskov / T. A. Urazaeva. – Ioshkar-Ola: Povolzhskii gosudarstvennyi tekhnologicheskii universitet, 2013. – 209 s.
13.
Urazaeva, T. A. Paket prikladnykh programm «Mul'tiMir» v praktike analiza kreditnogo riska / T. A. Urazaeva // VIII Mezhdunarodnaya nauchno-metodicheskaya konferentsiya «Sovershenstvovanie podgotovki IT-spetsialistov po napravleniyu «Prikladnaya informatika» dlya innovatsionnoi ekonomiki»: Sbornik nauchnykh trudov. – M.: Moskovskii gosudarstvennyi universitet ekonomiki, statistiki i informatiki, 2012. – S. 182-186.
14.
Khaikin, S. Neironnye seti: polnyi kurs / S. Khaikin. – M.: Izdatel'skii dom «Vil'yams», 2006. – 1104 s.
15.
Entsiklopediya finansovogo risk-menedzhmenta / pod red. A. A. Lobanova i A. V. Chugunova. – M.: Al'pina Pablisher, 2003. – 786 s.
16.
Holton, G. A. Value-at-Risk: Theory and Practice / G. A. Holton. – Academic Press, 2003. – 405 p.
17.
Jorion, P. Value at Risk: The New Benchmark for Managing Financial Risk / P. Jorion. – McGraw-Hill, 2006. – 543 p.
18.
Lomont, C. Random Number Generation / C. Lomont. – URL: http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf. Data obrashcheniya: 18.07.2014.
19.
Matsumoto, M. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator / M. Matsumoto, T. Nishimura // ACM Transactions on Modeling and Computer Simulation (TOMACS). Special issue on uniform random number generation. – 1998. – Vol. 8. – Iss. 1. – P. 3-30. – DOI:10.1145/272991.272995.
20.
Mersenne Twister VBA Class // Directory of Open Source for Quan-titative Finance and Trading. – URL: http://www.quantcode.com/modules/mydownloads/singlefile.php?cid=9&lid=610/. Data obrashcheniya: 18.07.2014.
21.
Reeds, J. Cracking a multiplicative congruential encryption algorithm / J. Reeds // Information Linkage Between Applied Mathematics and Industry (Proc. First Annual Workshop, Naval Postgraduate School, Monterey, Calif., 1978). – New York: Academic Press, 1979. – P. 467-472.
22.
Reeds, J. "Cracking" a Random Number Generator / J. Reeds // Cryptologia. – 1977. – Vol. 1. – No. 1. – P. 20-26.
23.
Shannon, C. E. Communication Theory of Secrecy Systems / C. E. Shannon // Bell Systems Technical Journal. – 1949. – Vol. 28. – P. 656-715.
24.
Vaudenay, S. A Classical Introduction to Cryptography: Applications for Communications Security / S. Vaudenay. – New York: Springer, 2006. – 335 p.
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.
Сайт исторического журнала "History Illustrated"