Читать книгу "Тайны чисел. Математическая одиссея - Маркус Дю Сотой"

На этот раз можно использовать компьютер.

Почему разложение чисел означает взлом кода?

Боб – администратор веб-сайта, продающего футболки в Англии. Элис живет в Сиднее, и она намеревается купить футболку на сайте и при этом послать данные своей кредитной карты так, чтобы никто другой не смог увидеть их. Боб размещает специальное кодовое число на своем веб-сайте, скажем 126 619. Это кодовое число чем-то напоминает ключ, который запирает сообщение Элис и делает его защищенным. Поэтому, когда Элис посещает веб-сайт, она получает копию кодирующего ключа, опубликованного Бобом, и использует его, чтобы «запереть» свою кредитную карту.

В реальности компьютер Элис совершает специальное математическое вычисление, использующее этот ключ, 126 619, и номер ее кредитной карты. Теперь этот номер зашифрован и может быть послан открытым образом через интернет на веб-сайт Боба. (Детали упомянутого вычисления приведены в следующем разделе.) Но постойте, разве при этом не возникнет проблема? Предположим, я хакер. Тогда что помешает мне посетить веб-сайт Боба, получить копию кодирующего ключа и расшифровать сообщение? Однако кодирование в интернете устроено довольно интригующе: вам нужен другой ключ, чтобы отпереть дверь, а этот отпирающий ключ хранится в большом секрете в офисе Боба.

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

Если я смогу найти два простых числа, которые при умножении дают 126 619, я сумею получить доступ к номерам кредитных карт, посылаемым на веб-сайт Боба. Но 126 619 – достаточно небольшое число, чтобы я мог делить его на одно число за другим. Так, потратив не слишком много времени, я нашел бы два простых числа 127 и 997. Однако вы не сможете воспользоваться этим приемом на настоящих веб-сайтах, потому что их ключи основаны на значительно бо́льших числах – они настолько велики, что найти пару простых чисел методом проб и ошибок почти невозможно. Математики, придумавшие эти коды, были настолько уверены в их надежности, что на протяжении многих лет предлагали приз $ 200 000 тому, кто сможет найти два простых множителя следующего числа из 617 цифр:

25 195 908 475 657 893 494 027 183 240 048 398 571 429

282 126 204 032 027 777 137 836 043 662 020 707 595 556

264 018 525 880 784 406 918 290 641 249 515 082 189 298

559 149 176 184 502 808 489 120 072 844 992 687 392 807

287 776 735 971 418 347 270 261 896 375 014 971 824 691

165 077 613 379 859 095 700 097 330 459 748 808 428 401

797 429 100 642 458 691 817 195 118 746 121 515 172 654

632 282 216 869 987 549 182 422 433 637 259 085 141 865

462 043 576 798 423 387 184 774 447 920 739 934 236 584

823 824 281 198 163 815 010 674 810 451 660 377 306 056

201 619 676 256 133 844 143 603 833 904 414 952 634 432

190 114 657 544 454 178 424 020 924 616 515 723 350 778

707 749 817 125 772 467 962 926 386 356 373 289 912 154

831 438 167 899 885 040 445 364 023 527 381 951 378 636

564 391 212 010 397 122 822 120 720 357.

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

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

Что такое часовой калькулятор?

Передовые коды, которые используются в интернете, на самом деле опираются на математическое изобретение, которому сотни лет, сделанному, когда никто и не мечтал об интернете. Я имею в виду часовой калькулятор. В следующем разделе мы узнаем, как часовые калькуляторы используются при кодировании в интернете, но сначала давайте познакомимся с принципом их работы. Сперва рассмотрим случай 12-часового циферблата. Мы все знакомы со сложением на таких часах – мы понимаем, что через четыре часа после 9 будет 1 час. Это то же самое, что сложение чисел с последующим нахождением остатка при делении суммы на 12. Данное действие можно записать так:

4 + 9 = 1 (modulo 12).

Мы пишем «modulo 12», потому что 12 – это модуль, точка, после которой числа стартуют снова. Мы можем находить подобные суммы и на часах с другим количеством часовых делений, не ограничиваясь двенадцатью. Так, в случае 10 часов на циферблате:

9 + 4 = 3 (modulo 10).

А как умножаются числа на часовом калькуляторе? Умножение сводится к прибавлению определенное количество раз. Например, 4 × 9 означает, что нужно взять четыре девятки и сложить их вместе. Где окажется стрелка на 12-часовом циферблате после сложения четырех девяток? 9 + 9 – то же самое, что 6 часов. Каждый раз, когда мы прибавляем последующую девятку, часовая стрелка движется назад на 3 часа. В конце она окажется на 12 часах. Поскольку 0 – крайне важное число в математике, мы далее будем называть это положение, которое заканчивает круг и начинает следующий, 0 часов. Итак, у нас получится странный на вид ответ:

4 × 9 = 0 (modulo 12).

А как будет происходить возведение какого-либо числа в степень? Давайте рассмотрим 94, что означает перемножение четырех девяток. Мы только что научились делать модульное умножение, поэтому должны легко справиться и с этим. Поскольку числа становятся большими, будет легче взять остаток от деления на 12, чем следить за числами на часах. Начнем с 9 × 9, что равняется 81. Каков будет остаток при делении на 12, другими словами, чему соответствует 81 час на циферблате? Оказывается, остаток равен снова 9. Сколько бы мы ни перемножали 9, всякий раз мы опять придем к 9: