Недавно в журнале Quanta вышел материал, в котором автор рассказывал про удивительный с точки зрения неискушенных читателей феномен, доказанный математиками. Его суть в том, что почти все многочлены определенного типа — неприводимые, то есть не поддаются разложению. Это доказательство применяется во многих областях чистой математики. Но также это хорошая новость для одного из столпов современной жизни — цифрового шифрования.

Для надежного хранения цифровой информации широко используется шифрование с помощью алгоритма RSA. Это прокачанная версия схемы, которую может придумать даже семиклассник, чтобы обмениваться сообщениями с друзьями: каждой букве присваивается свой номер, который умножается на некий секретный, заранее оговоренный ключ. Чтобы расшифровать сообщение, достаточно просто поделить его на секретный ключ.

RSA-шифрование работает схожим образом. Приведем сильно упрощенное объяснение. Пользователь придумывает сообщение и выполняет над ним определенные математические операции, включающие в себя умножение на очень большое число (длиной в несколько сотен цифр). Единственный способ расшифровать сообщение — найти простые множители полученного результата*.
*
Простые множители какого-либо числа — это простые числа, которые необходимо перемножить, чтобы получилось это число. Так, для числа 12 это 2*2*3, а для числа 495 это 3, 3, 5 и 11.

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

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

Вот как это работает.

Шаг первый: Выбирается любое число, простые множители которого нужно узнать. Для простоты возьмем число 15.

Шаг второй: 15 переводится в двоичную систему:

1111.

Шаг третий: Это двоичное выражение превращается в многочлен путем перевода всех двоичных чисел в коэффициенты многочлена:



(Обратите внимание: этот многочлен равен 15, если x=2. Число 2 — основание двоичной системы.)

Шаг четвертый: Многочлен раскладывается на множители:



Шаг пятый: x=2 подставляется в каждый из этих множителей:



Заключение: 5 и 3 — простые множители числа 15.

Да, это излишне сложный способ поиска простых множителей небольшого числа вроде 15, которые легко вычислить в уме. Однако когда дело доходит до крупных чисел, состоящих из сотен цифр, этот многочленный метод дает удивительное преимущество. Для разложения простых чисел быстрых алгоритмов не существует. Но для разложения крупных многочленов такие алгоритмы есть. Поэтому как только удастся превратить большое число в большой многочлен, можно очень близко подобраться к поиску простых множителей числа.

Означает ли это, что RSA-шифрование находится под угрозой? На самом деле нет. И новая, недавно доказанная закономерность по поводу многочленов как раз связана с этим.

Математики Эммануэль Брулья и Петер Варью из Кембриджского университета доказали, что по мере удлинения многочленов с коэффициентами 0 и 1 вероятность того, что их вообще можно будет разложить, становится все ниже. А если многочлен не удастся разложить, значит, его нельзя будет использовать для поиска простых множителей числа, которое требуется вычислить.

Доказательство Брулья и Варью фактически говорит о том, что обходной путь для взлома RSA-шифрования ведет в никуда. Используемые в RSA очень большие числа соответствуют очень длинным многочленам. Кембриджские ученые утверждают, что практически невозможно найти многочлены такой длины, поддающиеся при этом разложению. Как криптографы, так и математики давно подозревали, что это так. Однако когда мировая кибербезопасность зависит от невозможности использования некоторого математического приема, всегда хорошо иметь доказательство, что этот прием действительно не работает.

image

Комментарии (35)


  1. usdglander
    16.01.2019 16:34
    +9

    Для разложения простых чисел быстрых алгоритмов не существует.

    Наверное потому что простое число и нельзя разложить на сомножители за исключением 1 и самого числа?


    1. khim
      16.01.2019 18:47

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

      Это кто-то пытался сказать «попроще», а получилось… как получилось.

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

      P.S. И как раз если бы быстро искать простые было бы нельзя RSA и не работал бы. Так что в результате упрощения фраза изменила свой смысл на, фактически, противоположную…


      1. staticlab
        16.01.2019 20:32

        Да это просто переводчик как всегда ошибся:


        There’s no fast algorithm for factoring large numbers.


      1. 9660
        17.01.2019 06:05

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

        Почему двух? Или вы частный случай берете?


        1. Sirion
          17.01.2019 08:17

          Потому что на этом случае основан шифр RSA.


  1. SUA
    16.01.2019 17:54
    +1

    >>что по мере удлинения многочленов с коэффициентами 0 и 1 вероятность того, что их вообще можно будет разложить, становится все ниже
    Странно…
    — Как минимум половина таких многочленов (любой длины) оканчивается на 0 и поэтому раскладывается (с ожидаемым корнем x=2)
    — И, с другой стороны, многочлен полученный из ключа RSA гарантированно раскладывается на ровно 2 множителя т.к. рассуждение описанное в (шаг четвертый) работает в обе стороны
    К сожалению, препринта нет…


    1. Mad__Max
      17.01.2019 06:43

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

      Первоисточник всей этой цепочки тут: Irreducibility of random polynomials of large degree


      1. SUA
        17.01.2019 14:45
        +1

        Спасибо!
        В очередной раз журналисты такие журналисты…
        " Suppose that the Riemann hypothesis holds… "
        т.е. вероятно (но исходное предположение не доказано), что многочлен с коэффициентами 0 и 1, полученный из открытого ключа RSA, статистически неразложим если рассматривать его как случайный многочлен (допустимость чего не доказывалось — или я этого не вижу в статье).


    1. qwez
      17.01.2019 11:30

      Как минимум половина таких многочленов (любой длины) оканчивается на 0 и поэтому раскладывается (с ожидаемым корнем x=2)

      У всех чисел, полученных перемножением двух больших простых чисел, не будет множителя 2. Значит все многочлены, полученные из ключей RSA будут оканчиваться на 1.


    1. mtivkov
      17.01.2019 13:34

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


      1. Sirion
        17.01.2019 13:39

        Между многочленами и числами — взаимно-однозначное соответствие. А вот между неприводимыми многочленами и простыми числами — нет. Неприводимый многочлен может соответствовать составному числу.


        1. soomrack
          17.01.2019 14:54

          > Неприводимый многочлен может соответствовать составному числу.

          Очевидно, что нет.


          1. Sirion
            17.01.2019 15:11

            15


            1. soomrack
              17.01.2019 15:20

              (x^2+1)(x+1)


            1. saluev
              17.01.2019 15:24

              Многочлен для 15 приводим, это даже в статье показано.


              1. Sirion
                17.01.2019 15:29
                +1

                Прошу пардона, я допустил опечатку в 50% символов своего сообщения.

                25.


                1. soomrack
                  17.01.2019 15:44

                  (x^2+1)(x^2+1)


                  1. Sirion
                    17.01.2019 15:46

                    25 — это x^4 + x^3 + 1. А не то, что написали вы.


                    1. soomrack
                      17.01.2019 15:56

                      Я почти правильно написал:

                      25 = 5 * 5 = (x^2+1)(x^2+1) [при x = 2] = x^4 + 2 x^2 + 1

                      но поскольку коэффициент 2 недопустим, то его надо заменить на x, и получаем

                      x^4 + x^3 + 1

                      этот многочлен, действительно неприводим над Z.

                      Sorry, затупил, забыл, что от коэффициентов неравных 0 и 1 надо будет избавляться.


        1. Cerberuser
          17.01.2019 15:00

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


          1. Sirion
            17.01.2019 15:12
            +1

            Ничему. Оно вообще не будет многочленом нужного вида.


  1. alex005
    16.01.2019 18:24
    -1

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


    1. alex005
      17.01.2019 12:22

      за что минусят?


      1. Sirion
        17.01.2019 12:45

        Я полагаю, за неуклюжее выражение очевидной мысли. Если что, я не минусовал.


  1. adeptoleg
    16.01.2019 18:56

    Многочлены нет а вот миллиард китайцев с паролем «маодзедун»…


  1. staticlab
    16.01.2019 20:34

    А если взять не двоичную систему, а, например, троичную или другую, то полученный многочлен можно будет быстро разложить?


    1. tbl
      17.01.2019 07:57

      Так как раз и ищут многочлен с коэффициентами 1 и 0, т.е. задача сводится к поиску системы счисления в котором число будет состоять только из 1 и 0. Вырожденный и очевидный вариант 2 не подходит из-за слишком большой длины многочлена.


    1. vlanko
      17.01.2019 15:12

      Наверное предполагалось, что многочлен с единичными коефициентами разложить проще. 1 на 1 всегда поделится.


  1. worldmind
    17.01.2019 09:54

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


    1. mk2
      17.01.2019 12:33

      Это точно. Для постквантовой криптографии RSA всё равно не годится, потому что существует алгоритм Шора.


  1. DoNotPanic
    17.01.2019 13:01

    На самом деле полином любой степени можно разложить на одночлены с в общем случае комплексными коэффициентами. То есть и разложение любого числа возможно — на комплексные множители. И вопрос в том, можно ли затем эти комплексные множители так свернуть перемножением части из них, чтобы получить целые множители…


    1. soomrack
      17.01.2019 15:01
      +1

      > На самом деле полином любой степени можно разложить на одночлены с в общем случае комплексными коэффициентами. То есть и разложение любого числа возможно — на комплексные множители. И вопрос в том, можно ли затем эти комплексные множители так свернуть перемножением части из них, чтобы получить целые множители…

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


      1. vlanko
        17.01.2019 15:18

        кстати да. стандартные алгоритмы проверки делимости многочленов (подбором) — как раз деление на число.


  1. Apache02
    17.01.2019 13:57

    И если зашифрованное сообщение предназначалось не вам, и у вас нет ключа для его расшифровки, то попытки найти этот ключ могут занять добрую тысячу лет.

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


  1. unC0Rr
    17.01.2019 15:25

    придумывает сообщение и выполняет над ним определенные математические операции, включающие в себя умножение на очень большое число

    Не умножение, а возведение в степень по модулю очень большого числа.
    Единственный способ расшифровать сообщение — найти простые множители полученного результата

    Не результата, а модуля, который известен из открытого ключа.