Глава 111 Проблема Миллионера
Алгоритм RSA-шифрования использует в своей основе трудность разложения больших чисел на простые множители.
Например, мы знаем, что 17 × 13 = 221, но увидев число 221, сразу сказать, что оно равно 17 × 13, может быть не так просто.
А если эти числа становятся всё больше, то их разложение на простые множители становится всё сложнее.
Конечно, будучи специализированным методом факторизации больших чисел, он стал важным методом взлома такого шифрования.
Ведь принцип самого метода основан на постоянном умножении и исключении различных факторов.
Поэтому в отношении системы RSA-шифрования существует атака, называемая общим числовым методом фильтрации, которая считается наиболее эффективным способом взлома шифрования.
Конечно, та же проблема заключается в проблеме четности/нечетности, которая существует в методе фильтрации. Это делает обработку очень больших чисел довольно сложной. Современные алгоритмы RSA-шифрования используют именно такие большие числа. Поэтому при использовании метода фильтрации неизбежно возникают огромные отклонения в процессе взлома.
Однако в настоящее время...
- Да, раньше… при использовании метода фильтрации для взлома шифрования RSA возникали большие трудности. Ведь проблема четности и нечетности была очень серьезной.
Мэйнард рассмеялся, хлопнул Сяо И по плечу и сказал:
- Но сейчас всё иначе! Влияние проблемы четности/нечетности полностью подавлено твоим методом классификации. Те, кто занимается криптографией, теперь будут ломать себе голову
Теренс Тао тоже улыбнулся и сказал:
— Без сомнения, те, кто считают, что математика не имеет практического применения, теперь увидят на собственном опыте, как мы можем применить её к атаке на шифрование.
Увидев, как эти математики радуются такому повороту событий, соседний компьютерный ученый, профессор Кляйнрок, с недоумением спросил:
- Вы так думаете? Если банковские системы шифрования дадут сбой, то общественный порядок окажется под угрозой
— Не волнуйтесь, мы все понимаем, что это лишь теоретический риск. Чтобы действительно взломать систему, потребуется очень много времени, даже если использовать метод просеивания, — сказал Теренс Тао, невозмутимо махнув рукой. “Но то, что им теперь придется озаботиться этим вопросом, нас вполне устраивает.”
Как и многие другие исследователи в области чистой математики, они часто сталкивались с вопросом о практической применимости своей работы. Это неизменно вело к конфликтам между чисто математическим сообществом и другими научными дисциплинами.
Например, когда Итан Чжан добился прорыва в решении гипотезы о близнецах, Google пригласил его выступить с докладом. Но он отказался, боясь, что после выступления его будут расспрашивать об практическом применении его результатов.
То же самое произошло с Перельманом после того, как он доказал гипотезу Пуанкаре: его приглашали на лекции в разных университетах, чтобы объяснить свой метод доказательства.
В результате кто-то спросил его о практическом применении его метода. Услышав этот вопрос, Перельман мгновенно разгневался и заявил, что это глупый вопрос. Не выдержав, он уехал обратно в Россию.
В общем-то, те, кто занимается чистой математикой, и те, кто занимается прикладной, в основном не пересекаются.
Конечно, это породило у некоторых чистых математиков определённый склад характера: если что-то не может быть применено, они тем более гордятся этим, считая это истинно «чистой математикой».
Услышав обсуждение этих профессоров, Сяо И невольно покачал головой.
Это же не его вина, ведь он и не думал, что его разработка фильтрации может привести к риску взлома в криптографии.
Ну хватит уже ликовать, — сказал он. — Я тоже хочу узнать у вас, как решить эту проблему. В конце концов, это чисто математическая задача, и вам, математикам, придётся её решить.
Профессор Кляйнрок сказал.
Затем трое математиков тоже собрались с духом и ожидали объяснений от Кляйнрока.
— — Эм… Хочу объяснить, что такое многосторонние безопасные алгоритмы. Давайте начнём с классической проблемы.
- То есть, проблема миллионера. Вы ее знаете?
Теренс Тао кивнул. Он тоже занимался компьютерами, и лет пятнадцать назад разработал что-то под названием «теория руководства по получению информации». Проще говоря, это была технология цифровой компрессии изображений, которая в итоге широко использовалась в информационных областях и многих других сферах, что полностью продемонстрировало его сильные способности в прикладной математике.
Но Сяо И и Джеймс Мэйнард оказались в трудном положении.
Второму это не составило труда; он сказал, что слышал об этом:
— Я помню, кто задавал этот вопрос — лауреат премии Тьюринга.
Ха-ха, да. — Кляйнрок кивнул и сказал: —Кстати, этот лауреат премии Тьюринга, как и Сяо И, тоже из Китая. Его английское имя — Эндрю Яо, а китайское вроде как Яо Цичжи.
Проще говоря, проблема миллионеров заключается в следующем: предположим, есть два миллионера — Алиса и Боб — которые хотят сравнить, кто из них богаче, но не хотят показывать друг другу свои реальные состояния. В таком случае как им можно сравнить свое богатство?
Говоря об этом, — Кляйнрок написал на доске описание.
Предположим, что у Алисы и Боба есть имущество размером *i* и *j* соответственно, и значения *i* и *j* находятся в диапазоне от 1 миллиона до 10 миллионов. Как им сравнить размер своих состояний, не раскрывая друг другу точных значений *i* или *j*?
Глядя на эту задачу, Теренс Тао сразу понял, как её решить, но Мэйнард и Сяо И стали размышлять.
Задача, казалось бы, была довольно интересной.
Через некоторое время, оставив им немного времени для размышлений, Кляйнрок все же не рассчитывал, что они тут же найдут решение. Затем он продолжил:
— Хорошо, мы можем вернуться к этому вопросу позже…
Подожди.
Однако в этот момент Сяо И сказал:
— Думаю, эту проблему можно решить вот так.
После этого он подошёл к доске и, взяв мелок, начал писать.
Пусть M будет множеством всех элементов, являющихся N-битовыми неотрицательными целыми числами, а QN — группой перестановок из M в M.
— Если мой проект не содержит ошибок, то при сравнении по следующему протоколу они смогут сравнить свои активы, сохраняя конфиденциальность своей собственности.
— Алиса из группы QN сначала случайным образом выбирает элемент Ea в качестве своего открытого ключа и сообщает его Бобу, сохраняя для себя инверсию Da элемента Ea в качестве своего закрытого ключа.
— Затем Боб случайным образом выбирает N-битное целое число *x* и, используя открытый ключ Алисы, вычисляет *k* = Ea(*x*)…
— С началом рассказа Сяо И и те трое, что были рядом с ним, немного замолчали.
Они взглянули друг на друга, слегка ошеломленные происходящим.
Особенно Джеймс Мэйнард.
Хотя, если действительно внимательно изучить этот вопрос, то у него не должны возникнуть затруднения. Как задача по математическому моделированию, она вполне обычна в своей сложности.
Ведь вопрос уже полностью конкретизирован. Сравнивая его с абстрактностью проблем, которые изучает Мэйнард в области аналитической теории чисел, можно сказать, что это просто детская игра.
Но чтобы он так быстро понял и сразу же стал предлагать решения, этого нельзя сделать.
Увидев, что Сяо И уже написал половину доски, Мэйнард впервые испытал на себе, что такое «размерность».
Наверное, когда он раньше демонстрировал своим ученикам то, что такое «математическое мышление высшего уровня», они тоже испытывали подобные чувства?
Просто взрыв для мозга!
Реакция Кляйнрока была похожа на реакцию Мэйнарда. В принципе, он и не рассчитывал, что они смогут решить это сразу. Он оставил им несколько минут, чтобы просто ознакомиться с вопросом.
В результате, кто бы мог подумать, что всего через несколько минут этот молодой человек уже начнёт писать.
Простите его, как компьютерного ученого, математика у него не очень получается, по крайней мере, по сравнению с этими математиками. Ведь есть такая поговорка: только те, кто действительно хорошо разбирается в математике, могут всю жизнь заниматься чистой математикой, а те, кто плохо разбирается, рано или поздно меняют профессию.
Но вот что, способности Шэо И в математике превзошли все его ожидания.
Шаг 4: Алиса случайным образом генерирует N/2-битное простое число *p* и вычисляет Zu = yu mod *p*, где *u* = 1, 2, ..., 10.
Затем мы гарантируем, что среди всех Zu есть хотя бы два различных значения, в противном случае выбираем новое p и повторяем расчет.
Алиса перемаркирует простое число *p* и {*z1*, *z2*, ..., *zi*, *zi+1*}...
Боб проверяет, если zj` = x mod p, то i больше или равно j, иначе i меньше j.
На доске появилась последняя черта, после чего Сяо И повернулся и посмотрел всё с начала до конца. Он удовлетворенно кивнул, положил ручку и обратился к трем людям рядом.
Так, сравнение богатств Алисы и Боба завершено. Кроме случая, когда у обоих одинаковое состояние, они не раскрывали друг другу настоящих доходов.
— Профессор Кляйнрок, мой метод, я думаю, должен сработать. Но как именно его реализовать в программе, я не знаю.
Сяо И скромно сказал: — В программировании я совершенно ничего не понимаю."
Однако его удивило то, что в это мгновение трое профессоров немного замолчали.
Через мгновение Кляйнрок тихо спросил Теренса Тао: — Вы, математики, все такие? Решаете наши проблемы в области компьютерных наук так же легко, как будто бы это было сложением и вычитанием до ста?
Теренс Тао отмахнулся: — Э-э… Нет, не совсем так. Но вы же знаете, в этом мире всегда бывают какие-то исключения, редкие события. Сяо И — вот такой случай, понимаете?