Взлом RSA (или других алгоритмов) вручную ученым

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

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

Является ли это настоящей заботой при разработке криптографических шифров? Может ли злая организация нанять одного из этих людей для взлома криптографических ключей (для любого современного шифра)? Может быть есть какой-то пример из жизни?

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

Человеческий мозг и нейроны внутри оперируют скалярными состояниями. Хотя можно спорить о том, является ли мозговой процесс детерминированным или вероятностным, он не обладает способностью создавать суперпозиции состояний, как это могут делать квантовые компьютеры. Таким образом, он не имеет преимуществ перед классическими суперкомпьютерами при целочисленной факторизации или дискретном логарифмировании (алгоритм Шора), а также при поиске в несортированной базе данных (алгоритм Гровера).

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

Оригинальный пост @derjack имеет длину почти 700 символов. Вот 2048-битное число, записанное 617 десятичными знаками (почти столько же, сколько вопрос):

32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448280710318450446268407511633591722075539194702809692695116208601753153385228164358637425253452063124531982403270024154882788029124087013649227429510942494747262878176328960795460204004486651813356499189783184670257748061985168288109350852763136493356212118910302261417784227884243069534873234110239729827362916848850208533176280055919120540762635115410724871087269605319201076899957787049604743491139956908133927452563472712188255099007744935013999050172650250829825

Вы можете поверить мне на слово, что это составное число (то есть не простое).

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

Давайте установим нижнюю границу времени, в течение которого существующий человек сможет это взломать. Мои ссылки здесь шаткие¹, но кажется правдоподобным 3850 слов в минуту в качестве верхней границы скорости чтения человека. В преобразованном виде это 302 символа в секунду (со средней длиной слова 4,7 на английском языке²). Я также экстраполирую эту цифру на длинные числа; Итак, мы прибываем на стадион 300 цифр в секунду скорость чтения.

>>> 617 / 301.6
2.045755968169761

самый быстрый читатель в мире будет нужно не менее чем 2045 миллисекунд только для того, чтобы загрузить число в свою память. Для более обычных читателей, таких как я и вы, есть фактор 17¹; так просто читаю номер займет 35 секунд не меньше.Обратите внимание, что для оценки нижней границы, которую мы делаем здесь, мы должны предположить бесконечный целочисленная производительность мозга. 35 секунд будут вводом-выводом перед вычислением.

¹: https://www.brainread.com/en/the-fastest-reader-in-the-world/

²: https://norvig.com/mayzner.html

Теперь я рекомендую вам повторить упражнение самостоятельно, т.е. для 4096 бит. Это не в два раза больше! Неправильный уровень абстракции, если вы так думаете. 4096-bit numbers are on average 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times larger than 2048-bit numbers, in absolute value.

Упражнение может помочь вам осознать, как обманчиво легко услышать что-то о «N-битных» вычислениях и вообразить, что вы что-то поняли. Это путь сложнее, чем кажется — если посчитать.

Любой человек, который может разложить в уме 2048-битные числа быстрее, чем компьютер, почти наверняка является человеком, который, по сути, открыл новый алгоритм разложения чисел на множители. Что, если бы реализовать на компьютере, было бы еще быстрее.

Но это не исключает этого.

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

Мы не знаем, насколько труден факторинг чисел на самом деле. Мы знаем, что это класс сложности BQP, который для классических компьютеров (или человека, запускающего в голове классический алгоритм) находится в NP.

Проблема в NP, если относительно дешево проверять вы получили правильный ответ. Пример здесь: если кто-то утверждает, что делители некоторого числа равны A и B, вы можете проверить это,... вычислив A * B и посмотрев, совпадают ли они.

Но там нет никаких доказательств того, что NP не то же самое, что P. Если NP=P, то любая проблема, решение которой может быть проверено быстро может быть решено быстрый. (Это очень условно, но верно в этих пределах). А если NP=P, то BQP, находящийся в NP, также находится в P.

Для проблем в NP мы не знаем классического алгоритма, который был бы намного быстрее, чем «просто попробовать все возможности» здесь для щедрых определений «всего этого». (самые быстрые алгоритмы факторинга строго субэкспоненциальны; например, O (e ^ (k + биты ^ (1/3) * ln (биты) ^ (2/3)) если я скопировал это правильно).

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

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

Ученый смог найти быструю факторизацию без показывая NP=P или даже то, что BQP=P; например, может случиться так, что разложить на множители определенные типы простых чисел, которые мы используем для криптографии, проще, чем общую проблему, или, может быть, большой процент таких составных чисел легко разложить на множители (но не все из них), или что существует какой-то другой «угловой случай», который позволяет ему работать (даже иногда) намного быстрее, чем «попробовать каждый случай». Такой результат был бы мощным, но не был бы революционным в масштабах переписывания большей части того, что мы считаем интересной математикой (что, честно говоря, сделал бы эффективный P-алгоритм для задач NP).

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

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

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

2048-битное 617-значное десятичное число @ulidtko, опубликованное выше, может быть учтено в часы или меньше и, возможно, ученым с большим целочисленным калькулятором. Я факторизовал это и нашел специальную форму факторов. Маленькие множители просты, а большие множители — нет, если вы не найдете особая форма.

Необходимая способность ученого — это способность находить закономерности в двоичном коде. представление меньших множителей 2048-битного числа.

Вот десятичные и двоичные значения самых низких факторов: 3 - 11, 5 - 101, 7 - 111, 13 - 1101, 17 - 10001, 97 - 1100001, 193 - 11000001, 241 - 11110001, 257 - 100000001

Можете ли вы увидеть образец? Есть 3 узора. Первый образец все 1 11 111 2-й шаблон 101,10001, 100000001 3-й образец другой 1101, 1100001, 11110001

Второй шаблон — 2^k+1. Первый шаблон 2^k-1. Если вы выберете 2-й шаблон и разделите его на 2 ^ k + 1 фактора, это уменьшит факторизация.

Факторы: 3 ^ 3 х 5 ^ 2 х 7 х 13 х 17 х (2 ^ 768 + 1)(2^384+1)(2^256+1)(2^192+1)(2^128+1)(2^96+1)(2^64+1)(2^48+1)(2^32+1)(2^24+1)(2^16+1)(2^12+1)(2^8+1)

После разделения больших множителей 2 ^ k + 1 у вас останется 1044225 = 3 ^ 3 x 5 ^ 2 x 7 x 13 x 17. учитывать.

История: Алан Тьюринг и взлом машины Enigma. Таким образом:

Является ли это настоящей заботой при разработке криптографических шифров? Может ли злая организация нанять одного из этих людей для взлома криптографических ключей (для любого современного шифра)?

Да, если вы сможете найти своего Алана Тьюринга и предоставить то, что необходимо (или построить его с нуля, как это было в случае с машинными «бомбами» Enigma).

Нет, если вы думаете, что ваш Алан Тьюринг сделает это с помощью бумаги и карандаша.

На самом деле, если бы вы смогли найти специалиста по факторингу, это стало бы доказательством того, что p = np (или того, что за ваш счет проводилось масштабное мошенничество). Я ставлю на последнее крупную сумму.