если мы смотрим на тест, который с вероятностью, допустим, не больше 2^(-1000) ошибается
А почему вы решили, что алгоритм ошибается с вероятностью 2^(-1000)? Но даже если принять вашу (некорректную) оценку, то любое доступное количество прогонов Миллера-Рабина никак не поможет против чисел Кармайкла, плюс нет гарантий от пропуска и других видов чисел. Поэтому нужно точнее оценивать вероятность ошибки, и при этом она будет на сотни порядков больше.
К тому же предоставленный Вами алгоритм обладает одним неприятным свойством: созданные случайные простые числа не совсем «случайны». Их можно легко воссоздать, если кто-то украдет список начальных простых чисел.
Ну это не проблема. Точнее эта проблема ни чуть не страшнее, чем проблема генерации простым перебором с проверкой, потому что выбор начала последовательности, которую мы проверяем, требует случайности того же порядка, что и генерируемое число, но если в наличии есть уже случайное число такого порядка, то ни что нам не мешает применить эту случайность к отсечению ветвей в дереве генерации, начиная от выбора начального набора простых, и далее по всем этапам. Если вы запустите предложенный код без ограничений, то увидите, что первое умножение сгенерированных чисел на единичные по модулю 3 простые из начального набора даёт нам десятки тысяч простых, которые, естественно, все так же могут участвовать в последующих этапах. То есть коэффициент размножения будет около 10, а количество этапов для 30-битных начальных значений — более 30. В целом одна тысяча простых грубо даст ~10^30 вариантов. Но простых в нашем распоряжении не тысяча, а очень большое количество. Так, простые числа до миллиарда уже дают нам 50 миллионов, а теперь прикиньте количество сочетаний из 50 миллионов по 1000, и умножьте потом на 10^30. И это всего лишь числа до миллиарда, но ни что не мешает нам взять и до триллиона (гененрировать их тем же решетом, например). Так что с этой стороны я не вижу проблем.
пока не найдено ни одного составного числа проходящего этот тест
Тест систематически прогонялся на числах до 2^64, а что там дальше — никто не знает.
Кроме того, в той же библиотеке Java, которая использовалась при написании генератора, реализованы лишь два теста — Миллера-Рабина и Люка-Лемера. То есть даже если предположить, что Baillie–PSW идеален, то как мы видим на примере Java — библиотеки далеко не идеальны. А выбирают их такие же неидеальные пользователи. В сумме вероятность проблемы получается отнюдь не нулевая. Ну и сами можете проверить — в Java переберите с миллион нечётных чисел с тестированием их стандартной библиотекой с небольшим коэффициентом certainity — получите сотни промахов.
Поэтому проблема есть, а раз она существует, то и решать её явно стоит, тем более, что решение по стоимости — копеечное.
Вы все же несколько лукавите, утверждая, будто вероятностные подходы такие плохие
Вероятностные подходы работоспособны, но их работоспособность зависит от ряда факторов, таких как грамотность использующего их человека, организационные моменты, очень важные в криптографии, а так же всё тот же очевидный факт — вероятность может оказаться не в пользу использующего такой подход.
Поэтому, если есть возможность в корне устранить саму причину возникновения проблемы (то есть избавиться от вероятности), то есть очевидный смысл воспользоваться предлагаемым подходом.
У вероятностных тестов есть доказанная верхняя граница вероятности ложноположительного результата, которая зависит от количества проведенных тестов. Так, допустим, проведите тест 1000 раз, и вероятность ошибки будет настолько мала, что мы ошибемся от силы лишь один раз, даже если б проверяли миллиарды случайных чисел ежесекундно, начиная с момента Большого Взрыва.
Не совсем так. Для больших чисел (порядка 1024) количество обязательных для гарантированной проверки оснований систем счисления, равно количеству простых, меньших, чем само число. Это количество столь велико, что не то что ежесекундно, но вообще за множество полных циклов от большого взрыва до очередного коллапса вселенной, вы не сможете перебрать все варианты.
Плюс вероятностные тесты очень простые и крайне шустрые. Не нужно ждать 20 минут, чтоб произвести какую-то сотню простых чисел длиной 1000 бит.
Как вы видели, я предложил работающий код, а значит немного представляю, сколько времени может потребоваться на различные задачи. Скажу конкретно — генерация 1024-битных чисел с вероятностной проверкой мною производилась, но без точного учёта времени (были другие цели), хотя знаю точно (ибо долго ждал) — несколько сотен чисел необходимого размера с использованием той же библиотеки, что и в коде для генерации перемножением, потребуют от вас ожидания как раз минут пять, а то и 10 (повторюсь — время оценивал субъективно, но оценка такая — долго).
Кроме того, время, пусть даже в 4 раза большее, но измеряемое минутами, и при этом гарантирующее отсутствие псевдопростых, есть просто ничтожная затрата по сравнению с потенциально устраняемым ущербом. Ну и вспомним, что ключи генерируют раз в год (иногда в два), значит потерять пусть полчаса раз в год ради устранения возможного ущерба в размере многих миллионов — ну разве это затраты?
Для симметричного шифрования нужен ключ и генерируемая на его основании последовательность. Так вот здесь ключом является просто число, система счисления (тоже просто число) и делимое, то есть последовательность, которую делим на выбранное число. Шифрующая последовательность же формируется из набора остатков, которые получаются именно последовательным делением уголком. Всё, далее можно применять стандартные схемы, вроде XOR-а или перемешивания.
Хотя для сдвига последовательности остатков можно использовать возведение в степень, но это нужно лишь один раз.
Просто вы в конце статьи предлагаете «подумать о шифровании». Так чего о нем думать если уже все придумано?
Шифрование всегда есть компромисс между сложностью процедуры, криптостойкостью и требованием к железу. Предлагаемый вариант очень экономен по части требований к железу, по сложности процедуры предполагает минимальный обмен — нужно передать лишь несколько чисел.
Сегодня для шифрования после асимметричного этапа используют алгоритмы, которые требовательны к железу, из-за чего эти алгоритмы включают в состав процессоров. Возможно, менее требовательный алгоритм позволит сделать процессоры дешевле из-за отказа от встроенного алгоритма шифрования. То есть взгляд был в сторону подобной, не требовательной к железу, ниши.
А насчет теории, если она будет, то зачем «думать о шифровании», если в таком случае никакого стойкого шифрования в принципе не получится?
Не получится только лишь шифрование, основанное на сложности разложения числа на его делители. Другие виды шифрования вполне сохранятся. А прогресс в математике позволит решать дополнительные задачи, которые до сих пор решались плохо.
Не знаю, зачем вы упираетесь, но весь ваш текст является лишь передёргиванием и выхватыванием из контекста. Вам с таким упорством стои написать всем авторам учебников по математике, в которых присутствует масса умолчаний и неочевидностей, дающих вам все карты в руки для смелого обличения их подхода.
Выиграть, наверное, реально, но нужно выбрать удачный путь. Удача, как вы возможно знаете, улыбается не каждому. Плюс в теории чисел желательно разбираться, что бы использовать накопленные знания.
Да, спасибо за уточнение. Правда в тексте было про получение периода из выражения 1/Х, поэтому там появилась цифра 81. Если разделить девятки на 123456789, то будет тоже 81, но с кучей цифр после запятой.
А почему вы решили, что алгоритм ошибается с вероятностью 2^(-1000)? Но даже если принять вашу (некорректную) оценку, то любое доступное количество прогонов Миллера-Рабина никак не поможет против чисел Кармайкла, плюс нет гарантий от пропуска и других видов чисел. Поэтому нужно точнее оценивать вероятность ошибки, и при этом она будет на сотни порядков больше.
Ну это не проблема. Точнее эта проблема ни чуть не страшнее, чем проблема генерации простым перебором с проверкой, потому что выбор начала последовательности, которую мы проверяем, требует случайности того же порядка, что и генерируемое число, но если в наличии есть уже случайное число такого порядка, то ни что нам не мешает применить эту случайность к отсечению ветвей в дереве генерации, начиная от выбора начального набора простых, и далее по всем этапам. Если вы запустите предложенный код без ограничений, то увидите, что первое умножение сгенерированных чисел на единичные по модулю 3 простые из начального набора даёт нам десятки тысяч простых, которые, естественно, все так же могут участвовать в последующих этапах. То есть коэффициент размножения будет около 10, а количество этапов для 30-битных начальных значений — более 30. В целом одна тысяча простых грубо даст ~10^30 вариантов. Но простых в нашем распоряжении не тысяча, а очень большое количество. Так, простые числа до миллиарда уже дают нам 50 миллионов, а теперь прикиньте количество сочетаний из 50 миллионов по 1000, и умножьте потом на 10^30. И это всего лишь числа до миллиарда, но ни что не мешает нам взять и до триллиона (гененрировать их тем же решетом, например). Так что с этой стороны я не вижу проблем.
Тест систематически прогонялся на числах до 2^64, а что там дальше — никто не знает.
Кроме того, в той же библиотеке Java, которая использовалась при написании генератора, реализованы лишь два теста — Миллера-Рабина и Люка-Лемера. То есть даже если предположить, что Baillie–PSW идеален, то как мы видим на примере Java — библиотеки далеко не идеальны. А выбирают их такие же неидеальные пользователи. В сумме вероятность проблемы получается отнюдь не нулевая. Ну и сами можете проверить — в Java переберите с миллион нечётных чисел с тестированием их стандартной библиотекой с небольшим коэффициентом certainity — получите сотни промахов.
Поэтому проблема есть, а раз она существует, то и решать её явно стоит, тем более, что решение по стоимости — копеечное.
Вероятностные подходы работоспособны, но их работоспособность зависит от ряда факторов, таких как грамотность использующего их человека, организационные моменты, очень важные в криптографии, а так же всё тот же очевидный факт — вероятность может оказаться не в пользу использующего такой подход.
Поэтому, если есть возможность в корне устранить саму причину возникновения проблемы (то есть избавиться от вероятности), то есть очевидный смысл воспользоваться предлагаемым подходом.
Не совсем так. Для больших чисел (порядка 1024) количество обязательных для гарантированной проверки оснований систем счисления, равно количеству простых, меньших, чем само число. Это количество столь велико, что не то что ежесекундно, но вообще за множество полных циклов от большого взрыва до очередного коллапса вселенной, вы не сможете перебрать все варианты.
Как вы видели, я предложил работающий код, а значит немного представляю, сколько времени может потребоваться на различные задачи. Скажу конкретно — генерация 1024-битных чисел с вероятностной проверкой мною производилась, но без точного учёта времени (были другие цели), хотя знаю точно (ибо долго ждал) — несколько сотен чисел необходимого размера с использованием той же библиотеки, что и в коде для генерации перемножением, потребуют от вас ожидания как раз минут пять, а то и 10 (повторюсь — время оценивал субъективно, но оценка такая — долго).
Кроме того, время, пусть даже в 4 раза большее, но измеряемое минутами, и при этом гарантирующее отсутствие псевдопростых, есть просто ничтожная затрата по сравнению с потенциально устраняемым ущербом. Ну и вспомним, что ключи генерируют раз в год (иногда в два), значит потерять пусть полчаса раз в год ради устранения возможного ущерба в размере многих миллионов — ну разве это затраты?
Решения там всё равно целочисленные, а это — теория чисел в полный рост. Простые же задают структуру в теории чисел.
Хотя для сдвига последовательности остатков можно использовать возведение в степень, но это нужно лишь один раз.
Не только к вычислению модуля через степень. В тексте много раз упоминается альтернативный и очень дешёвый способ (уголком).
Речь шла о чнижении требований к симметричному шифрованию. Например, по сравнению с AES.
Шифрование всегда есть компромисс между сложностью процедуры, криптостойкостью и требованием к железу. Предлагаемый вариант очень экономен по части требований к железу, по сложности процедуры предполагает минимальный обмен — нужно передать лишь несколько чисел.
Сегодня для шифрования после асимметричного этапа используют алгоритмы, которые требовательны к железу, из-за чего эти алгоритмы включают в состав процессоров. Возможно, менее требовательный алгоритм позволит сделать процессоры дешевле из-за отказа от встроенного алгоритма шифрования. То есть взгляд был в сторону подобной, не требовательной к железу, ниши.
Не получится только лишь шифрование, основанное на сложности разложения числа на его делители. Другие виды шифрования вполне сохранятся. А прогресс в математике позволит решать дополнительные задачи, которые до сих пор решались плохо.
Расскажите нам, как получить алгебраическое число без корней. Тогда будет о чём говорить.
Не знаю, зачем вы упираетесь, но весь ваш текст является лишь передёргиванием и выхватыванием из контекста. Вам с таким упорством стои написать всем авторам учебников по математике, в которых присутствует масса умолчаний и неочевидностей, дающих вам все карты в руки для смелого обличения их подхода.
Хорошо, возможно я зря ожидаю подвоха.
Наличие закономерности всегда чему-то помогает. Но некоторые вещи не входят в круг наших интересов, поэтому мы можем выражаться примерно как вы.
Да, вы успешно доказали наличие свойств тролля.
Все замечательными быть не могут. Хотя если есть желание хоть чем-то поддеть — вы выбрали подходящее направление.
256 тоже замечательное число