Криптография русского крестьянина +78



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

Должен сразу признаться, что статья не будет посвящена тому, как русским крестьянам удавалось обмениваться информацией втайне от своих помещиков.

Умножение методом русских крестьян


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

Общее описание метода просто, но не слишком информативно. Тем не менее, давайте начнём с него.

Если нам нужно перемножить два целых числа $m$ и $n$, то мы начертим две колонки, в заголовке одной напишем $m$, а в другой — $n$. Затем начнём постоянно добавлять новые ряды, получаемые делением пополам $m$ (остаток отбрасывается) и удвоением $n$, и остановимся, когда в колонке $m$ останется $1$. Наконец, сложим все элементы колонки $n$, где значение $m$ нечётно.

Гораздо понятнее всё станет, если привести пример. Так что давайте выполним умножение $13 \times 7$. Это даёт нам таблицу

$\begin{array}{|c|c|} \hline m & n \\ \hline 13 & 7\\ 6 & 14\\ 3 & 28\\ 1 & 56\\ \hline \end{array}$


Теперь мы складываем правые значения, у которых левые значения нечётны, что даёт нам

$7+28+56 = 91$


Что, как можно легко убедиться, является результатом $13 \times 7$.

Разумеется, интересно то, почему эта загадочная процедура работает?

Если посмотреть в левую колонку, и пройтись до самого верха, записывая $1$, когда мы увидим нечётное число и $0$, когда встретим чётное, то получим $1101$, что является $13$ в двоичной форме (и, конечно, это никакое не совпадение). На самом деле, это и есть стандартный алгоритм преобразования чисел в двоичную форму.

Затем, как мы видим, повторяющееся удвоение колонки $m$ вычисляет произведение $m$ с соответствующей степенью $2$, поэтому их сложение с соответствующим нечётным значением в колонке $n$ является сложением $m$, умноженного на эти степени $2$, что в сумме даёт $m$.

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

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

Возведение в степень методом русских крестьян


Мы внесём в алгоритм два небольших изменения; оба будут касаться только колонки $m$.

  • Вместо удвоения мы будем возводить в квадрат
  • Вместо сложения в конце мы будем умножать.

Для каждой строки в таблице вместо умножения $m$ на соответствующую степень $2$ мы будем возводить его в соответствующую степень $2$. Умножение всего этого даст нам $n^m$.

Давайте посмотрим, как это будет работать с теми же значениями $m$ и $n$.

$\begin{array}{|c|c|} \hline m & n \\ \hline 13 & 7\\ 6 & 49\\ 3 & 2401\\ 1 & 5764801\\ \hline \end{array}$


Умножение соответствующих членов даёт

$5764801 \times 2401 \times 7 = 96889010407$


Что на самом деле равно $7^{13}$.

Но в отличие от умножения, такой метод не просто достаточно эффективен: он очень эффективен.

Если мы хотим найти $n$ в степени $m$, то мы можем сделать это, перемножив $m$ раз число $n$. Это как вычислять $m \times n$ сложением $m$ раз числа $n$: можно сделать и так, но если $m$ больше $3$, то потраченным временем можно распорядиться и с большей пользой.

Но благодаря этому алгоритму количество необходимых возведений в квадрат максимум примерно в $3$ больше количества разрядов $n$ (потому что двоичное представление десятичного числа имеет примерно в $3$ раза больше бит, чем у десятичного числа разрядов), за которыми следует такое же количество умножений.

Разумеется, для этого мы должны уметь умножать, но это нас устраивает: алгоритм умножения позволяет нам умножать удвоением и сложением, а адаптированная версия позволяет возводить в степень возведением в квадрат и умножением. Это выгодная сделка.

Краткое знакомство с RSA


Смысл этого в том, что способ реализации криптографии с открытым ключом RSA (Rivest-Shamir-Adleman) (и некоторые другие) подразумевает, что для шифрования и расшифровки сообщений нам нужно вычислять степени.

Процедура работает следующим образом: мы выбираем закрытую пару простых чисел $p$ и $q$, и сообщаем миру значение $N=pq$. (Значения $p$ и $q$ мы храним в секрете: алгоритм основан на том, что задача разложения $N$ на множители сложна.)

Затем мы подбираем число $e$ и находим $d$ такое, что $ed$ на $1$ больше, чем произведение $(p-1)(q-1)$. Мы сообщаем всему миру $e$. (Число $d$ мы храним в секрете. Алгоритм основан на том, что нахождение $d$ без знания $p$ и $q$ является сложной задачей.)

Теперь мы представляем сообщение как целое число $M \lt N$. Зашифрованная форма сообщения $E$ является остатком от деления $M^e$ на $N$.

Благодаря магии теории чисел (на самом деле это не магия, а малая теорема Ферма) исходное сообщение будет являться остатком от деления $E^d$ на $N$.

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

И тут возникает одна проблема.

На практике значения $M$ и по крайней мере или $e$, или $d$ очень велики. Если нам придётся выполнять повторное умножение, то Вселенная умрёт раньше, чем мы закончим. Этот алгоритм уменьшает объём работы до вполне приемлемых пропорций. Умножения $e$ (или $d$) сокращаютя до числа умножений, являющегося являющегося малым делителем числа разрядов $e$ (или $d$).

Но это не единственная проблема.

Значение $M^N$ почти невероятно велико. Мы не сможем записать его, даже если бы использовали для хранения одной цифры каждую элементарную частицу в известной нам Вселенной. Как же это работает?

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

RSA русских крестьян


Итак, теперь мы видим, как вычислить зашифрованное сообщение. Можно использовать адаптированное умножение по методу русских крестьян, но теперь мы можем добавить последний штрих — когда квадрат числа превышает $N$), мы будем брать остаток от деления на $N$.

Давайте посмотрим, как это работает, на примере нахождения остатка от деления $7^{13}$ на $59$.

$\begin{array}{|c|c|} \hline m & n \\ \hline 13 & 7\\ 6 & 49\\ 3 & 2401 \rightarrow 41\\ 1 & 1681 \rightarrow 29\\ \hline \end{array}$


Что даёт нам

$29 \times 41 \times 7 = 8323 \rightarrow 4$


И это на самом деле (фух!) является остатком от деления $96889010407$ на $59$.

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

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

Благодарности


На MathsJam Gathering 2017 Элен Смит и Линда Голденберг выступили с докладом о техниках умножения, в том числе о методе русских крестьян. Именно тогда до меня наконец дошло, что алгоритм повторного возведения в квадрат является адаптацией умножения русских крестьян, и я понял, что стоит поделиться этим осознанием с читателями. Через двадцать минут Оливер Мастерс рассказал о матрице Фибоначчи и упомянул алгоритм повторного возведения в квадрат для возведения в степень матрицы. К счастью, он не связал его с алгоритмом умножения. Ещё через пять минут Колин Райт (@ColinTheMathmo) подвёл итог докладам и упомянул об этой связи. Но к тому моменту я уже всё равно принял решение написать эту статью, что и сделал.

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (18):

  1. rprokop
    /#10567414

    Я в молодости реализовывал RSA с нуля, в качестве упражнения.
    Использовал и сабжевые алгоритмы и ассемблерные вставки. На тогдашнем железе (2001г)
    шифрование работало минуту. Генерация ключей — полдня. Мораль — крестьянских алгоритмов недостаточно. Для возведения в степень по модулю используют алгоритм Монтгомери (насколько помню, в Монтгомери-представлении вычисления ведутся по модулю степени двойки, то есть отбрасыванием старших разрядов). Для умножения больших чисел используют алгоритм Карацубы.

  2. saipr
    /#10567480

    А почему RSA, а скажем, не ГОСТ Р 34.10-2012

    • domix32
      /#10567538

      Думаю потому что зарубежные буржуи не особо сведуют в российских ГОСТах. Или вы просто уровнем промахнулись? Хотя было бы странно в 2001 году читать ГОСТ из 2012.

      • saipr
        /#10567620

        сегодня в 15:39

        И почему 2001 год?


        Хотя было бы странно в 2001 году читать ГОСТ из 2012.

        Думаю потому что зарубежные буржуи не особо сведуют в российских ГОСТах.

        Но они прекрасно "сведуют" в EC, что фактически тот же ГОСТ (вернее наоборот).


        Или вы просто уровнем промахнулись?

        Не понял

        • domix32
          /#10567756

          Я просто думал вы промахнулись уровнем и написали вопрос предыдущем коментатору реализовавшему алгоритм RSA.
          Ну, а если найдете у EC стандарт с рекомендацией LCC, то буду рад почитать.

  3. Tiirl
    /#10567566

    в части «Возведение в степень методом русских крестьян» в самом начале:
    «Мы внесём в алгоритм два небольших изменения; оба будут касаться только колонки m.»
    похоже, изменения касаются как раз колонки n.
    То же самое в оригинале статьи.

  4. GlukKazan
    /#10567568

    Эх, эту бы статью лет на 30 раньше. У нас один фрукт на кафедре для диплома запилил программку, которая работала на всех кафедральных ПК во время их «простоя» и записочку писал с просьбой её запускать (до быстрого возведения в степень он не додумался). А мне, в те же года, пришлось в исходниках PGP разбираться.

  5. aryeh
    /#10567744

    На первой картинке ошибка? Направление стрелочек нужно изменить на обратное?

    • dobergroup
      /#10568066

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

    • vivlav
      /#10568362

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

    • Ogra
      /#10568390

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

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

  6. hdfan2
    /#10568072

    Должен сразу признаться, что статья не будет посвящена тому, как русским крестьянам удавалось обмениваться информацией втайне от своих помещиков.

    А жаль, я бы почитал. Но за статью всё равно спасибо.

  7. CryptoPirate
    /#10568428

    На практике значения M и по крайней мере или e, или d очень велики.

    Уточню про d и e: когдя генерируют ключи RSA для шифрования, то специально берут маленькое e (потом вычисляют d, которое выходит большим). Смысл в том чтобы шифровать можно было быстро быстро, шифровать будут все чтобы отправить сообщение мне, а расшифровывать буду только я (вычисления становятся проще для большего числа людей), плюс еще и открытый ключ чуть короче выходит. Для электронной подписи всё ровно наоборот.

  8. PavelMSTU
    /#10568492 / +2

    Для такого замечательного поста такая скучная картинка — преступление!
    PatientZero, замените хотя бы на знаменитую картину Богдана-Бельского!

    ''Устный счёт в народной школе С. А. Рачинского'' (1895)

    • Steed
      /#10568786

      Спасибо, размял мозг;)

  9. iboltaev
    /#10569208

    Если мы хотим найти n в степени m, то мы можем сделать это, перемножив m раз число n.


    А не сравнивали ваш подход с бинарным возведением в степень? Там число операций умножения не более чем в 2 раза больше числа бит в m.

    • rprokop
      /#10571238

      Это и есть бинарное возведение в степень.