OberonCore

Тема выделена из viewtopic.php?f=30&t=7027

ну bjprng же! ;-)

А чем его инициализировать? Если уж обращаться к ОС, то сразу уж куда положено, к системному криптогенератору.

вроде бы вопрос был про простой генератор.

впрочем, инициализировать вполне можно u32-хэшем (брать опять у Боба) от `GetTickCount()`, например. для этого генератора вполне подойдёт, и значительно быстрее, чем криптоконтекст. можно даже без хэша.

кстати, в шинде вполне себе есть `RtlGenRandom()`. оно, правда, высунуто из `advapi32.dll` по хитрому имени, и m$ стращает, что устарело — но пофигу. удобно и сердито.

Даже если простой, то что GetTickCount, что RtlGenRandom вызывать - примерно одинаково по сложности кода (новые API чуть сложнее, но тоже не так сложно). И заодно ничего хешировать не надо, т.е. упрощение. А "медленность" системного криптогенератора на сидах будет неощутимой, а если так - то зачем на ПК микроконтроллерные оптимизации, когда можно делать сразу как положено? Кстати, для хеширования источников энтропии есть простая и качественная хеш-функция Blake2s.


Для JSF/ranval - точно можно, надо просто сделать Warmup, т.е. несколько холостых итераций. И оно само себя захеширует.

нет, это не так. `GetTickCount()` — одна строка. `RtlGenRandom()` — объявляем прототип, делаем `LoadLibrary()`, делаем `GetProcAddress()`. везде бережно проверяем на ошибки. десяток строчек влёгкую.

прошу прощения: кем положено? почему для сидирования bjprng положено использовать cprng? почему нельзя просто `GetTickCount()`? почему нельзя хэш от `GetTickCount()`, хэш от process id, и вычесть их друг из друга, если охота сделать вид, что это имеет хоть какое-то значение? каким образом это ослабит prng, который и без того не предендует на криптокачество?

давайте проведём эксперимент. BJ U32 hash (возьмём подлинее):

можно увидеть реализацию простого блэйк в семь строчек?

В принципе можно, но тогда придется задумываться, какое это даёт эффективное количество вариантов инициализации в битах. Если с момента включения компьютера прошло меньше суток, то это даст 10^5 * 10^3 = 10^8 вариантов. Т.е. мы укорачиваем сид JSF. Увеличение числа вариантов потребует вызова каких-то других функций (ещё какого-то системного времени, RDTSC и.т.п.), возможно, использование упоминаемого Вами хеша. Т.е. те же 10 строк. А если те же - то чего сразу системный криптогенератор не вызвать?


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

Дело было вечером . . . , делать было нечего . . . ???. Слепил небольшую демку по Вашим алгоритмам. Страдания в прошлом ))). Исходники в архиве, а web вариант запускается по ссылке: https://ormcode.ru/wasm/jkiss.html

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

Т.к. тема тут про компилятор языка программирования, и возможную библиотеку функций для него, то я тут склоняюсь к тому, что лучше делать "правильно". Даже если ChaCha20 и его инициализацию от системного криптогенератора используют для написания Тетриса, или какого-то платформера, пользователь не заметит накладных расходов на серьёзный ГПСЧ. "Недостаточным" "правильный" подход станет только в весьма специфичных случаях: для симуляций, в которых ГПСЧ - узкое место (это не так часто бывает), демосцены, ретрокомпьютинга, микроконтроллеров и т.п.

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

В 99.9 процентов случаев этого вполне достаточно и даже желательно. Иметь уникальное значение (хэш), однозначно сопоставимое с заданной последовательностью, как правило и является целью. Или в какой-то промежуток времени, обеспечить уникальность некоторого параметра, для однозначной идентификации чего либо.

Наверное, только одну область - криптографию не устраивает такое положение дел. Отсюда и все более сложные алгоритмы - попытки заставить результат выглядеть, как можно более случайным. Усложнить попытки ‘дизассемблирования’ исходных данных.

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

Итак: arisu - уникальность и однозначность
ScrollLock - уникальность и неоднозначность

Совершенно разные цели и подходы. Их нельзя сравнивать между собой. Или можно !!!


Было бы классно, и если ещё небольшую теоретическую часть, для таких же чайников, как я. Со своей стороны, мог бы попробовать написать демонстрационную часть, соответствующих алгоритмов библиотеки, примерно в таком варианте: https://ormcode.ru/wasm/jkiss.html ))).

для теоретической части надо знать много математики. модульная арифметика на эллиптических кривых, криптоанализ, вообще теория криптографии, s-box'ы, sponge construction, другие старшные маты.

чача, засидированая из системного cprng — пушка. не всегда нужна, но надёжно убьёт муху. вместе с домом. bjprng — рогатка. на двадцать метров стреляет нормально, но стену не пробьёт.

лично мой совет — вообще не париться, и взять самый простой из возможных некриптографических генераторов. сидировать тиками, или хэшироваными тиками. для большинства встречающихся на практике применений этого достаточно. а кому надо что-то более крутое — тот всё равно будет глуп, если станет использовать стандартные библиотеки, а не самописный и хорошо оттестированый своими тестами код. bjprng хорошо инлайнится, помещаясь в регистры. вероятно имеет период 2^64, но экспериментально доказан 2^20. зато не требует умножений. я его везде использую и не парюсь.

p.s.: один фиг почти все режут диапазон генераторов при помощи MOD — и на этом месте уже неважно, какой там генератор изначально был.

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


В криптографии поточный шифр должен удовлетворять тесту на следующий бит, т.е. человечеству не должен быть известен способ восстановления его внутреннего состояния по его выходу ощутимо быстрее полного перебора. А состояния там большие, как минимум 128 бит, а то и 256. Некриптографические генераторы проверяют менее строго: требуют теоретических гарантий их периода и прогоняют эмпирические тесты на соответствие равномерному распределению на выборках порядка порядка десятков терабайт. И нет, не простые частотные тесты, а что-то вроде TestU01 и PractRand. При этом если знать алгоритм, то его состояние по выходу восстановить обычно куда проще, чем у некриптографических генераторов. Иногда достаточно чуть ли не одного значения.

Т.к. шифры нынче быстрые и простые, то я занимаю максималистскую позицию и считаю некриптографические генераторы скорее хакерскими трюками для весьма специфических случаев.


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


Просто это - дешёвая и быстрая пушка, в той же glibc ГПСЧ очень плохого качества устроен сложнее ChaCha. Ультрабыстрые некриптографические генераторы как "вторая линия" тоже нужны, и я такие коллекционирую, но необходим очень жёсткий отбор таких алгоритмов. Пихать абы что в стандартные библиотеки языков программирования - это полный бардак, доставшийся нам от хакерских трюков для ламповых машин. Даже для 8-битных компьютеров или IBM PC XT можно придумать более-менее сносные генераторы, проходящие современные статистические тесты. И даже для обероновской системы типов - можно, хотя и сложно.


Есть ещё одна скользкая тема - преобразование целочисленных значений в число с плавающей запятой. Есть по меньшей мере три способа, и только один из них - строгий, т.е. даже без теоретических изъянов.

z80, чо.

так это то же самое: получить целое в диапазоне мантиссы, из этого сконструировать плавающее. это если full range надо, конечо. если неполный — то там другое решение, да, которого я не помню в силу ненадобности. ;-)

и снова имею добавить личное мнение. вот такой подход:

и ведёт, я считаю, к распуханию софта да тормозам. потому что используется не минимально возможное, а «пофигу, техника быстрая». один случай роли не играет, а потом незаметно привычка — и софт на «электроне», помилуйгосподимягрешного. до железа тоже уже добралось — с 64битобесием.

хороший инженер — это всегда хакер. средний инженер — by the book. плохой инженер — вообще не инженер.

Ну для Спектрума не так плохо, период у него крошечный, около 2^32, но для Тетриса и визуальных эффектов пойдёт. Мне для 8-битных компьютеров пришла в голову чуть более сложная конструкция. Период у него небольшой: минимальный около 2^40, средний - около 2^55. Проходит TestU01, PractRand до 16 ТиБ, а также батареи SmokeRand. Насколько он устрашающе выглядит для реального 8-битного железа:





Я знаю три способа:
1) Умножить 32-битное или 64-битное целое на соответствующий множитель.
2) Запихнуть часть 64-битного целого в мантиссу, получить число от 1 до 2, вычесть 1. Младший бит мантиссы будет нулевым, а так неплохой способ.
3) Отдельно сгенерировать мантиссу и порядок. Для генерации порядка можно считать количество нулевых бит в начале числа. Этот способ - наиболее точный с математической точки зрения, но более сложный.


Если на машине больше 2 ГиБ памяти, то 64 бита выглядят вполне естественно. И иногда такие объёмы бывают всё же полезны. И насчёт "распухания" от шифра: упрощённая реализация ARX-шифра не сложнее какого-нибудь синуса или косинуса. И снова считаю, что статистическая корректность важнее микроконтроллерных оптимизаций. Кстати, позиция "везде шифр по умолчанию" могла бы вести и к упрощению кода:
1) В случае glibc - сокращение потребления памяти, резкое повышение качества, сокращение объёма кода в функции rand().
2) В одной из библиотек для BlackBox, рекомендованной в соседней теме: вместо коллекции генераторов, большинство из которых сомнительного свойства - достаточно одного шифра и одного очень быстрого и удовлетворяющего ряду специальных требований некриптографического ГПСЧ.
3) В стандартной библиотеке golang - сокращение потребления памяти.

И даже если останавливаться на некриптографических генераторах - то чем какой-нибудь xoroshiro-aox сложнее minstd? Оба совместимы с системой типов Оберона. Хотя xoroshiro со скремблерами - нормальный генератор, minstd - плохой.

для восьмибиточки, где считаем каждый такт и байт — это отличный генератор.

случайные числа в том же плейсиме нужны в большом количестве. при бюджете ~70K т-стейтов на кадр. вышепроцитированый марсаглиевский генератор имеет прекрасный баланс между качеством, размером и скоростью. сложнее, конечно, можно — но бюджет на кадр же.

зачем? подавляющему большинству программ не надо столько памяти. а если надо — их авторы профнепригодны. для спецприменений же логично иметь спецжелезо. чтобы MMU мог управлять памятью больше 4 гб — 64бит процессор тоже не нужен.

зачем раздувать все структуры данных с указателями на лишние байты (которые, напомню, не бесплатны: процессорные кэши ограничены), если это надо только для очень специфических задач? я и говорю, что стиль мышления: «а давайте везде батарею пушек» — он вот к такому приводит в итоге.

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

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

Ну это скорее старая НЕдобрая классика (как и аддитивный генератор Фибоначчи без децимации из Кнута), почти в одном ряду с RANDU. И надо было бы в ObxRandom и в glibc добавить четкое указание "Warning! This generator is a toy that mustn't be used for any real work!". А уж LFSR в xoroshiro/xoshiro - это один из старейших и уважаемых методов, тоже почти что классика. Но уже добрая, т.к. эмпирическое качество хорошее.


Может, решили не повторять все эти пляски с бубном с сегментацией из 1980-х и сделали везде единообразно. В т.ч. чтобы одна и та же архитектура была и на рабочих станциях, и на суперкомпьютерах. И чтобы в графическом редакторе, видеоредакторе или компьютерной игре по сегменты не думать (эти программы как раз никогда не нажрутся памяти).


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


С ГПСЧ я наблюдаю обычно прямо противоположный стиль мышления - а давайте по умолчанию тащить всякую бяку.

3 гб плоской памяти процессу достаточно. 64 бита могут иметь какой-то смысл в системе типа AOS, где никаких изолированых процессов нет. а для оси, в которой есть понятие «изолированый процесс» — не просто не нужно, а категорически вредно. поощряет говнокодинг.

ну да, ровно то, о чём я постоянно говорю: один молоток для любых задач. в итоге он очень плохо подходит для всего.

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

зачем? это, кстати, кусок кода как раз из кросс-компилятора форта.

зачем?

калькурятор живёт в ROM, и RAM не занимает. впрочем, его почти никто и не использует.

отсутствие понимания не лечится «богатой стандартной библиотекой». и это одна из причин, по которой «стандартной библиотеки» быть не должно: не можешь сделать сам и то, что тебе надо — не делай вообще ничего никогда.

Каких-то серьёзных проблем 64-битная адресация не вызывает (а с 64-битными указателями жить в общем-то можно), при этом позволяет получить доступ к памяти единым куском. У меня, кстати, иногда бывают задачи, где 3 ГиБ на процесс было бы мало. Но это - не из-за излишеств нехороших, а скорее из-за самой специфики расчётов.


Чтобы обеспечить корректность расчётов с использованием генератора. А низкокачественные ГПСЧ бывают не только в Форте, но и много где ещё. Тот 8-битный LFSR с периодом 2^32-1 приемлем для игрушек и демо, но он недопустим в роли генератора общего назначения в языке высокого уровня. Как и minstd.


Даже если и так, то при работе с численными методами, в т.ч. с ГПСЧ, это требует довольно глубокого погружения в тему. Но ГПСЧ в учебниках объясняются куда хуже, чем многие другие численные методы. И если не пихать шифры везде, то при работе с ГПСЧ всё равно нужно чётко понимать, что "тест на следующий бит" на самом деле и есть настоящий критерий статистического качества генераторов. А любой некриптографический ГПСЧ - это компромисс. К сожалению, до учебников это обычно не доходит, хотя уже давно пора.

Но если "стандартной библиотеки" нет вообще - это означает, что и экспоненту, и степень, и тригонометрические функции надо "с нуля" писать? А это уже не так просто.

вызывает. замусоривание процессорного кэша. например, мой текстовый редактор на 64-бит машине с более быстрым процессором, чем у меня, расцвечивает текст медленней, чем на моей 32-битной. потому что там огромное количество кусочков с указателями во все стороны. проверено таймером — там медленней. хотя процессор быстрее, и регистров свободных больше.

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

есть огромная разница между «иногда бывают такие задачи» и «все задачи такие».

каких? ответ «любых» я не смогу принять: не знаю, что такое «любые расчёты».

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

повод чинить учебники, а не пытаться компенсировать недостаток знания «стандартной библиотекой». если человек не понимает, что он использует и почему — то не надо ему давать молоток с запиской: «ты теперь так гвозди забивай!» а то потом «боинги» падают.

ну, написать хотя бы один раз тот же cordic всяко будет полезно.