Пост «Свежие идеи в математике: неклассические арифметики и разнообразия» предложил читателям мысль использования наборов числовых алгебраических операций — арифметик, функций/уравнений на их основе, теперь называемых функциями/уравнениями разнообразия, и того, что является множествами/последовательностями значений функций разнообразия и множествами решений обозначенных уравнений — разнообразий. Конкретную неклассическую арифметику можно найти в препринте «Арифметика DR+», а неформально познакомиться с ней можно на видеопримерах.
Далее, КА – сокращение для классической арифметики, НКА – для неклассической, -их.
Одним из заявленных преимуществ идеи была возможность переноса (переиспользования) привычных конструкций классической арифметики на неклассические с целью экономии мышления. Здесь мы обозначим один теоретический пример, начинающийся с вопросов: "В данной арифметике A существует аналог простого числа относительно ее умножения или нет? Арифметика остатков в A существует? RSA-алгоритм реализуется в A?"
Очертим пунктирно интересующую нас арифметику A следующим образом: ее умножение — это алгоритм, принимающий на вход числовые операнды, конечную таблицу умножения i и конечную таблицу сложения j для цифр, наподобие классических операций. Это математически корректно утверждать, что в A столько умножений, сколько возможно пар «таблица умножения – таблица сложения». Аналогично со сложениями, вычитаниями, делениями.
Итак, у нас есть множество умножений, причем оно колоссально. Как только арифметика А такова, что в ней имеет смысл говорить о простых (относительно данного умножения) числах, то мы имеем следующее «простое запутывание взломщика»: если он не знает операцию умножения, т. е. не знает таблицы умножения и сложения, то неизвестно как факторизуется данное число. В самом деле, в одном умножении оно факторизуется на простые a, b, в другом — на простые c, d, e, f, в третьем оно само является простым.
Итак, RSA, реализованный в наборе Оt операций арифметики А, будет работать с секретными таблицами и будет иметь публичный ключ. Закрытость таблиц операций расшифровки влечет необходимость закрытости их и для зашифровки, поскольку, в отличие от RSA с классической арифметикой, сообщение Боба расшифруется Алисой, если им обоим известны операции: публичный ключ Алисы известен всем, им может зашифровывать любой, но какая таблица у получателя неизвестно. С другой стороны, по тем же причинам что в RSA, у нас нет необходимости менять таблицы в новом сеансе шифрования.
Предположим, RSA реализуется в Оt . Разумно предположить, что, при одинаково «длинных» числах, RSA, снабженный Оt, обладает большей криптоустойчивостью из-за секретности таблиц, нежели снабженный классической. Однако А может быть медленнее в машинном смысле. Тогда можно попробовать работать с более короткими числами. Это может несколько понизить стойкость, но, тем не менее, сохранить ее большей нежели RSA с КА. Или можно упростить алгоритм шифрования, оставаясь все равно в интервале высокой надежности.
P. S. Автор не является специалистом по шифрованию. Препринт «Арифметика DR+» не содержит по состоянию на 25 февраля 2022 года никаких подробностей по заданной теме.
Комментарии (10)
pohjalainen
26.02.2022 13:59Вы предлагаете чудовищно неэффективную. неработоспособную и нестойкую криптосистему с секретным ключом.
Для начала попробуйте предъявить такую арифметику, где будет работать функция RSA, я бы с интересом посмотрел.
diversiter Автор
26.02.2022 18:52Прямо сейчас предъявить арифметику не могу, но среди громадного числа алгебраических операций не так уж мала вероятность существования арифметики А в Z, такой что существует изоморфизм по RSA между Z с A и Z с КА (класс. арифм). Однако предъявить ее трудно.
Неэффективная? Может быть. Строго говоря, это надо будет доказывать оппоненту для предъявленной А. Чтобы было понятней: мне выгодно признать свою неправоту, если идея обнаружится нецелесообразной. Упорствовать — слишком дорогое удовольствие. Но правоте порадуюсь, не скрою.
pohjalainen
26.02.2022 19:35Не "может быть". а точно. У вас секретная таблица умножения будет размером O(n^2) элементов - как и где ее хранить, как передавать, если вы хотите, чтобы n не позволило вскрывать простым перебором?
diversiter Автор
26.02.2022 20:07Тут вообще все просто: я придумаю арифметику, а все остальное — вы. :)
Отвечать смогу через день-другой.
AndrewRo
26.02.2022 15:47+2Ну какбэ эллиптическая криптография примерно так и работает. Вместо чисел используются точки на эллиптической кривой, для которых определяются операции сложения, вычитания, умножения и т.д., а дальше на этой математике уже реализуется классическая криптография: RSA, DSA, DH key exchange и т. д.
pohjalainen
26.02.2022 15:59какбэ нет. Определение операций над точками ЭК - открытое и общеизвестное, в отличие от предлагаемого автором.
AndrewRo
26.02.2022 16:12Согласен, по описанию получается, что определение арифметики является частью ключа. Только не понятно, зачем, если в RSA ключ уже есть.
Travisw
27.02.2022 03:40Вот интересно сколько урана тратиться человечеством на шифрование. Как бы электричества если кто-то не понял
kipar
Если у Алисы и Боба есть общие секретные данные (таблицы умножения), то зачем им RSA? Ведь он нужен как раз когда таких данных нет.
diversiter Автор
Да, я помню эту сторону RSA. Мое короткое "по тем же причинам что в RSA, у нас нет необходимости менять таблицы в новом сеансе шифрования" следовало бы развернуть так:
RSA с другой арифметикой (подстановочной) в целях повышения стойкости, основанной на факторизации, следует снабжать общими для отправителя и получателя секретными таблицами умножения. Это уже будет модифицированным tlRSAWNCA (two-layer RSA With Non-Classical Arithmetics), т.е. не прямым аналогом RSA. Область применения тоже несколько изменилась — на ту, где сейчас требуется односеансовые ключи.
В самом деле, у нас отпадает необходимость менять ключи, поскольку даже ставшая известной таблица умножения (факторизации) не раскрывает автоматически зашифрованную информацию: взломщик попадает всего лишь туда, где действует законы стойкости классического RSA — все знают таблицу умножения, но все упираются в барьер сложности факторизации*.
Возможно, это должно поправлять мое "допустимое сокращение длины чисел/упрощение RSA" из предпоследнего абзаца поста. Возможно, сохранение таблиц секретными нас оставляет в старой проблеме симметричных ключей.
Другими словами, RSAWNCA — двухслойная система. Но, видимо, с двойными накладными расходами. Опять-таки, первые автомобили были медленнее лошадей: остановись мы перед этим барьером — до сих пор ездили бы на их скоростях. Дорогу осилит идущий! Если даже что-то из первоначальной задумки придется исключить, что-то полезное может остаться и быть дополненным.
В принципе, быть может, существует арифметика, такая, что Алиса будет иметь и публичное умножение, и приватное. При этом будет возможность каждому шифровать для Алисы сообщение, которое она успешно будет расшифровывать приватным ключом с приватным умножением. Задача отыскания такой арифметики звучит устрашающе сложно. Но как знать?!
________________
* (Заметим, что мы можем пользоваться olRSAWNCA (one-layer RSA With Non-Classical Arithmetics) без секретных таблиц. Не понятно, стоит ли?)