Как вы думаете: попытки генерировать истинно случайные числа вместо просто хороших псевдослучайных — это действительно жизненная необходимость или перестраховка?
И разрешима ли строго задача генерации истинно случайных чисел?
Здравствуйте, nikov, Вы писали:
N>И разрешима ли строго задача генерации истинно случайных чисел?
Где-то мне попадалась ссылка на сайт, где торговали случайными последовательностями. Правда брали они их, записывая то ли космическое излучение, то ли белый шум из какого-то другого физического источника.
Здравствуйте, nikov, Вы писали:
N>Как вы думаете: попытки генерировать истинно случайные числа вместо просто хороших псевдослучайных — это действительно жизненная необходимость или перестраховка?
N>И разрешима ли строго задача генерации истинно случайных чисел?
1. Необходимость (нафига бы столько народу этим заморачивались)
2. Разрешима (с привлечением аппаратных средств)
D>Где-то мне попадалась ссылка на сайт, где торговали случайными последовательностями. Правда брали они их, записывая то ли космическое излучение.
Да-да, помню, помню. Про этих товарищей еще Лем писал что-то в "Гласе господа"
Здравствуйте, nikov, Вы писали:
N>Как вы думаете: попытки генерировать истинно случайные числа вместо просто хороших псевдослучайных — это действительно жизненная необходимость или перестраховка?
Что точно можно сказать, нужны хорошие источники энтропии. Можно ли их называть в какой-то мере генераторами истинно случайных чисел, сказать не берусь.
N>И разрешима ли строго задача генерации истинно случайных чисел?
чисто физически — разрешима (по крайней мере, в текущей картине мира), но, вероятно, с некой конечной точностью.
Здравствуйте, nikov, Вы писали:
N>Как вы думаете: попытки генерировать истинно случайные числа вместо просто хороших псевдослучайных — это действительно жизненная необходимость или перестраховка?
Чисто из экономических соображений: какой суммой ты готов ответить за то, что написанный тобой генератор ПСЧ не ослабляет криптографию в системе ? А если систему все же поломают, как будешь доказывать что это не из за твоего генератора ?
Здравствуйте, Eugene Kilachkoff, Вы писали:
EK>Чисто из экономических соображений: какой суммой ты готов ответить за то, что написанный тобой генератор ПСЧ не ослабляет криптографию в системе ? А если систему все же поломают, как будешь доказывать что это не из за твоего генератора ?
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, Eugene Kilachkoff, Вы писали:
EK>>Чисто из экономических соображений: какой суммой ты готов ответить за то, что написанный тобой генератор ПСЧ не ослабляет криптографию в системе ? А если систему все же поломают, как будешь доказывать что это не из за твоего генератора ?
N>То есть, чистой воды перестраховка.
Нет, экономика. Аппаратный генератор стоит X баксов, плюс Y баксов его разработка. По идее, софтовый генератор не стоит ничего, но это только на первый взгляд. Софтовый генератор надо тоже написать и оттестировать, причем качества работы аппаратного генератора он не достигнет по определению. Софтовый генератор, кроме того, нужно кормить энтропией, в то время как аппаратный берет ее "из воздуха". Собственно, в этом случае софтовый генератор может выиграть только в одном случае -- если он будет капитально дешевле аппаратного, да и то для нетребовательных применений. Аппаратный же обычно весьма прост: это нечто шумящее (туннельный диод, например), усилитель, АЦП и все.
Здравствуйте, Eugene Kilachkoff, Вы писали:
EK>Нет, экономика. Аппаратный генератор стоит X баксов, плюс Y баксов его разработка. По идее, софтовый генератор не стоит ничего, но это только на первый взгляд. Софтовый генератор надо тоже написать и оттестировать, причем качества работы аппаратного генератора он не достигнет по определению. Софтовый генератор, кроме того, нужно кормить энтропией, в то время как аппаратный берет ее "из воздуха". Собственно, в этом случае софтовый генератор может выиграть только в одном случае -- если он будет капитально дешевле аппаратного, да и то для нетребовательных применений. Аппаратный же обычно весьма прост: это нечто шумящее (туннельный диод, например), усилитель, АЦП и все.
Я бы взглянул на вопрос по-иному. Когда я пишу программный генератор, то я знаю алторитм и могу оценить сложность его угадывания.
Если я использую аппаратный генератор, то алгоритма его работы я не знаю, я лишь знаю, что он сложен. Но насколько сложен —
Может быть, завтра кто-то угадает алгоритм.
То есть я меняю риск, который я могу оценить, на риск, который я оценить не могу.
Здравствуйте, nikov, Вы писали:
N>Как вы думаете: попытки генерировать истинно случайные числа вместо просто хороших псевдослучайных — это действительно жизненная необходимость или перестраховка?
N>И разрешима ли строго задача генерации истинно случайных чисел?
Знаки числа pi=3.1415926...; вполне случайные... но чем более случайными требуются числа, тем сложнее их получить.
А вообще-то в мире небыло бы войн, если бы можно было всё предсказать...
Здравствуйте, nikov, Вы писали:
N>Если я использую аппаратный генератор, то алгоритма его работы я не знаю, я лишь знаю, что он сложен.
Алгоритма в обычном понимании слова там ведь нет.
N>Может быть, завтра кто-то угадает алгоритм.
То есть научится предсказывать какой-либо физический шум, доказав тем самым его неслучайность? Это будет открытие, шуму ( ) будет много, узнаешь и поменяешь генератор.
Здравствуйте, igna, Вы писали:
N>>Может быть, завтра кто-то угадает алгоритм.
I>То есть научится предсказывать какой-либо физический шум, доказав тем самым его неслучайность? Это будет открытие, шуму ( ) будет много, узнаешь и поменяешь генератор.
А ОНИ узнали чуть раньше... И бабло уже ушло!
Проблема в том, что я не могу оценить риск такого события. Так стоит ли менять известный риск на неизвестный?
Здравствуйте, dotcode, Вы писали:
D>Знаки числа pi=3.1415926...; вполне случайные... но чем более случайными требуются числа, тем сложнее их получить.
Случайные они или нет, это похоже открытый вопрос:
The most pressing open question about π is whether it is a normal number -- whether any digit block occurs in the expansion of π just as often as one would statistically expect if the digits had been produced completely "randomly", and that this is true in every base, not just base 10. Current knowledge on this point is very weak; e.g., it is not even known which of the digits 0,…,9 occur infinitely often in the decimal expansion of π.
nikov wrote: > Может быть, завтра кто-то угадает алгоритм. > То есть я меняю риск, который я могу оценить, на риск, который я оценить > не могу.
Вообще-то, есть методики оценки "случайности" чисел.
А все нормальные аппаратные генераторы работают с естественными
процессами, так что за них можно не волноваться.
Здравствуйте, nikov, Вы писали:
N>Если я использую аппаратный генератор, то алгоритма его работы я не знаю, я лишь знаю, что он сложен. Но насколько сложен — N>Может быть, завтра кто-то угадает алгоритм.
Может быть завтра кто-то отменит принцип Гейзенберга?
Здравствуйте, Кодёнок, Вы писали:
N>>Может быть, завтра кто-то угадает алгоритм. Кё>Может быть завтра кто-то отменит принцип Гейзенберга?
Нет, речь не об этом. Просто любая физическая теория имеет ограниченную область применимости.
И лишь приблизительно отображает реальность.
Когда-то считали правильной классическую физику. И они были правы — она действительно точно описывала изученные на тот день явления.
Да, в текущей картине мира, единственное, что мы можем сказать — "это случайный процесс".
Но наука-то совершенствуется. А защищая свою систему, я хочу чтобы мое бабло было в сохранности не только сегодня, но и завтра, и послезавтра.
Выбирая аппаратные генераторы, мы априори принимаем гипотезу, что вероятность взлома "аппаратного" случайного процесса ниже взлома любого сколь угодно сложного программного.
Здравствуйте, nikov, Вы писали:
N>Как вы думаете: попытки генерировать истинно случайные числа вместо просто хороших псевдослучайных — это действительно жизненная необходимость или перестраховка?
N>И разрешима ли строго задача генерации истинно случайных чисел?
смотри... вот есть объект A и есть объект B; A может определить, что B не случаен, только 'опередив' B;
увы, это вечный процесс perpetum mobile...
Здравствуйте, dotcode, Вы писали:
N>>И разрешима ли строго задача генерации истинно случайных чисел?
D>смотри... вот есть объект A и есть объект B; A может определить, что B не случаен, только 'опередив' B;
Зачем "опередив"? Достаточно воспроизвести ту же последовательность позже.
Здравствуйте, nikov, Вы писали:
N>Да, в текущей картине мира, единственное, что мы можем сказать — "это случайный процесс". N>Но наука-то совершенствуется. А защищая свою систему, я хочу чтобы мое бабло было в сохранности не только сегодня, но и завтра, и послезавтра. N>Выбирая аппаратные генераторы, мы априори принимаем гипотезу, что вероятность взлома "аппаратного" случайного процесса ниже взлома любого сколь угодно сложного программного.
Да, принимаем. И по-моему эта гипотеза достаточно легко доказывается с помощью текущих знаний о мире.
Здравствуйте, nikov, Вы писали: N>Когда-то считали правильной классическую физику. И они были правы — она действительно точно описывала изученные на тот день явления.
N>Да, в текущей картине мира, единственное, что мы можем сказать — "это случайный процесс". N>Но наука-то совершенствуется.
Говорят же, если научиться предсказывать случайные кванттовые процессы (типа распада атомного ядра, или туннелирования электрона) -- это не то что развитие, это придется всю физику за последние сто лет на уши поставить. Тут не до криптографии уже...
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, nikov, Вы писали:
N>>И разрешима ли строго задача генерации истинно случайных чисел?
VD>Нет, так как все в воде Божей! Аминь.
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, igna, Вы писали:
N>>>Может быть, завтра кто-то угадает алгоритм.
I>>То есть научится предсказывать какой-либо физический шум, доказав тем самым его неслучайность? Это будет открытие, шуму ( :) ) будет много, узнаешь и поменяешь генератор.
N>А ОНИ узнали чуть раньше... И бабло уже ушло! :)) N>Проблема в том, что я не могу оценить риск такого события. Так стоит ли менять известный риск на неизвестный?
Это уже много раз анализировалось статистически: сравнивались гипотеза истинной случайности квантовых процессов и гипотеза скрытых параметров. Измерения показали, что или наблюдается действительно истинная случайность, или скрытых параметров столько, что не обнаруживается никаких признаков зависимости от них.
Подробности эксперимента — к спецам по матстатистике, им он хорошо известен.
N>Как вы думаете: попытки генерировать истинно случайные числа вместо просто хороших псевдослучайных — это действительно жизненная необходимость или перестраховка? N>И разрешима ли строго задача генерации истинно случайных чисел?
"Случайное число" — это абстракция. Любую последовательность можно оценивать как случайную.
Нужны какие-то критерии.
В крипторгафии есть свои критерии "хорошей" случайной последовательности, эти критерии вытекают из самих криптографических задач.
Для других задач критерии хорошести могут быть другими.
Аналогия — CRC-хеш хорош для обнаружения ошибок, но плох в качестве криптографического хеша. Те и другие разрабатывалсись по разным принципам, из разных задач.
В криптографии для случайной последовательности важно, чтобы никто, не знающий ключа, не мог с вероятностью, существенно отличающейся от 50% предсказать следующий бит последовательности. Или затратил бы на вычисление этого бита очень много сил.
Соответственно, криптографические генераторы строят, например, исходя из такого принципа (на пальцах): определение следующего бита эквивалентно по сложности решению NP-полной задачи, типа факторизации.
I>То есть научится предсказывать какой-либо физический шум, доказав тем самым его неслучайность? Это будет открытие, шуму ( ) будет много, узнаешь и поменяешь генератор.
Или научится наводить на твой генератор правильный, заранее известный шум Ну, это в предположении, что генератор относительно физически доступен...Банкомат какой-нибудь..
Здравствуйте, nikov, Вы писали:
VD>>Нет, так как все в воде Божей! Аминь.
N>А-аа, так "вода Божья" — это, оказыватся, "воля Божья"? N>А я целый день над этим голову ломал!
Здравствуйте, nikov, Вы писали:
N>Выбирая аппаратные генераторы, мы априори принимаем гипотезу, что вероятность взлома "аппаратного" случайного процесса ниже взлома любого сколь угодно сложного программного.
Вероятность взлома полным перебором равна 1 и не зависит от генератора. Фишка стойких алгоритмов в том, что на перебор уйдёт очень много времени. Вероятность взлома за одну попытку можно посчитать (зависит от разрядности). Понятно, что если генератор можно обратить, то полный перебор не потребуется. Да, наука совершенствуется, и возможно, завтра кто-то внезапно придумает эффективное решение для ряда NP-полных задач, а не только откроет новые закономерности в естествнных процессах.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
gear nuke wrote: > Да, наука совершенствуется, и возможно, завтра > кто-то внезапно придумает эффективное решение для ряда NP-полных задач, > а не только откроет новые закономерности в естествнных процессах.
Если кто-то найдет полиномиальное решение хотя бы одной NP-полной
задачи, то всем существующим шифрам можно будет сказать
"до-свидание".
Cyberax wrote: >> Да, наука совершенствуется, и возможно, завтра >> кто-то внезапно придумает эффективное решение для ряда NP-полных задач, >> а не только откроет новые закономерности в естествнных процессах. > Если кто-то найдет полиномиальное решение хотя бы одной NP-полной
Ну не так категорично, всё же.. > задачи, то *всем* существующим шифрам можно будет сказать > "до свидания".
Всего лишь "приготовиться на выход". Если даже решение NP-полной задачи
и будет найдено, некоторое время сотая степень, которая будет в
алгоритме, позволит продержаться. Правда, потом её, возможно, понизят до
приличной. Если всё это вообще случится...
raskin wrote: >> Если кто-то найдет полиномиальное решение хотя бы одной NP-полной > Ну не так категорично, всё же..
Именно так Доказано, что ВСЕ NP-полные задачи "равномощны".
Если научишься полиномиально решать любую из них — научишся решать все.
>> задачи, то *всем* существующим шифрам можно будет сказать >> "до свидания". > Всего лишь "приготовиться на выход". Если даже решение NP-полной задачи > и будет найдено, некоторое время сотая степень, которая будет в > алгоритме, позволит продержаться. Правда, потом её, возможно, понизят до > приличной. Если всё это вообще случится...
Ага.
Cyberax wrote: >>> Если кто-то найдет полиномиальное решение хотя бы одной NP-полной >> Ну не так категорично, всё же.. > Именно так Доказано, что *ВСЕ* NP-полные задачи "равномощны". > Если научишься полиномиально решать любую из них — научишся решать все.
Я в курсе. Но всё же вариант "полиномиально, степень — тысячная, и
константа — немножко больше, чем время жизни Вселенной, делённое на
время прохождения размера протона светом" вполне естественен. Я,
собственно, только об этом. В конце концов, говорят, что когда нашли
детерминированный полиномиальный алгоритм проверки простоты, сначала его
не могли реализовать — всего лишь седьмая степень, но памяти он ел
столько (ну разумеется полиномиально), что её быстро не хватало. Потом,
правда, степень понизили и вроде он теперь реализуется.
