Почему при шифровании TLS, да и вообще в криптографии используются именно простые числа? Почему бы не использовать любые?
-
4математика того требует :) Всякие там теоремы Ферма и иже с ними...– HarryCommented 3 нояб. 2017 в 19:38
-
1А конкретнее можно ,т.к. сообщение не информативно?– Павел ИгоревCommented 3 нояб. 2017 в 19:42
-
3@ПавелИгорев, мне кажется вы скорее сможете получить информативный ответ на каком-нибудь форуме по математике. Только учтите, понять его может быть сложно, поскольку большинство математиков будут объяснять его, считая, что вы владеете математикой в той же степени, что и они– avpCommented 3 нояб. 2017 в 20:26
-
1@ПавелИгорев, ОК, не буду давать "бессмысленные ответы" - удачи вам в ваших нелегких поисках ;-)– MaxU - stand with UkraineCommented 3 нояб. 2017 в 21:04
-
1@MaxU Разумное решение– Павел ИгоревCommented 3 нояб. 2017 в 21:05
5 ответов
TLS допускает использование различных протоколов шифрования и обмена ключей. Разные протоколы используют простые числа по совершенно различным причинам:
RSA
Один из самых популярных протоколов шифрования, RSA, основывается на том, что задача факторизации числа - разложение составного числа на простые множители (скорее всего), не разрешима с полиномиальной сложностью на обычных компьютерах (но разрешима за полиномиальное время на квантовых, криптоапокалипсис грядет).
Т.е. если у вас есть два огромных простых числа p и q, то тот, кто знает только n = p * q, проведет достаточно много времени, пытаясь разложить n обратно на p и q. Естественно, есть оговорки, позволяющие отсечь известные субэкспоненциальные алгоритмы, например, p и q должны отличатся порядком хотя бы на пару разрядов, но в общем случае можно считать что большие p и q сделают решение задачи факторизации n дико долгим.
При этом, найти два больших простых числа - достаточно легко.
Так что использование больших простых чисел - это способ получить огромное и тяжело факторизируемое составное число.
RSA описывает подбор/генерацию чисел e, d, n, таких, что для любого значения m будет справедливо:
Способ генерации предполагает выбор n = p * q, e = 65,537 (или любому другому небольшому числу). Т.е. они находятся быстро. Пара (n, e) - это публичный ключ.
Доказано, что если взять в качесте d результат решения уравнения ed = 1(mod ϕ(n)), то тройка (e, d, n) будет отвечать требованию выше.
ϕ(n) - это функция Эйлера - равная количеству натуральных чисел, меньших n и взаимно простых с ним. Для ее нахождения нужно факторизовать n. Т.е. если вы знаете только (n, e), то поиск d решением этого уравнения займет вечность.
Но при этом φ(p) = p − 1, φ(q) = q − 1. И для простых p и q:
φ(n) = φ(pq) = (p − 1) * (q − 1).
Так что вы берете два больших простых числа, быстро вычисляете φ(n) и n, получаете d из уравнения выше. Простые числа и φ(n) выбрасываете и никому не показываете. (n, d) - это ваш приватный ключ, и узнать его, зная только (n, e), ни у кого не получится за разумное время.
После этого любой, у кого есть ваш публичный ключ может зашифровать для вас сообщение:
А вот расшифровать его можете только вы:
Из взаимозаменяемости e и d и одинаковости для шагов для шифрации/дешифрации следует второй способ применения RSA - только вы можете зашифровать известный текст так, что расшифровать его можно будет только с помощью публичного ключа.
Если вы допишете к концу сообщения его чексумму, зашифрованную приватным ключом (получив при этом "электронную подпись"), то любой может посчитать ту же чексумму, "расшифровать" подпись, и сравнить два значения. Если они совпадут - значит сообщение дошло без изменений, и отправили его именно вы.
Diffie-Hellman
Протокол обмена ключами DH полагается не на сложность факторизации, а на сложность решения задачи дискретного логарифмирования. Он основан на том, что нельзя быстро вычислить ключ
зная только ga, gb, g и p.
Но при этом он легко позволяет сторонам вычислить этот общий ключ, переслав по открытому каналу ga, gb, если одна сторона придумает свое секретное a, а вторая - свое секретное b.
Elliptic Curve Diffie-Hellman
Даже основы эллиптической криптографии в один пост SO не влезут, так что стоит только упомянуть, что ECDHE так же полагается не на сложность факторизации, а на сложность решения задачи дискретного логарифмирования.
Для задачи дискретного логарифмирования есть субэкспоненциальный алгоритм Полига-Хеллмана, позволяющий свести решение проблемы для n точек к подзадачам для множителей n - p1, p2, p3, p4. Соответственно, количество точек кривой выбирают таким, чтобы оно делилось на какое-то большое простое число p, сравнимое по длине с n. Т.е. простые числа в ECDHE используются только косвенно, в качестве "ограничителя простоты". Из этих же соображений значения p, g в DH накладываются соответствующие ограничения.
-
2стоит заметить, что вопрос не является чисто теоретическим (вот commit, который в DH составной p в socat добавляет). Составные числа на месте простых можно использовать в качестве [NOBUS] backdoor. How does a non-prime modulus for Diffie-Hellman allow for a backdoor?.– jfsCommented 4 нояб. 2017 в 7:03
-
Паш, ну твой ответ также не блещет простотой - тоже отсылка к загадочной суперматематике, так что мы квиты– BarmaleyCommented 5 нояб. 2017 в 16:43
-
@Barmaley он и не должен блистать простотой :) но вся суперматематика в нем ограничивается основами теории чисел. Это обычно преподают вместе с теорией графов и операциями над матрицами, примерно на 2-м курсе любого хорошего универа.– user177221Commented 5 нояб. 2017 в 19:03
На самом деле ничего суперсложного здесь нет.
1) TLS базируется на асимметричной криптографии, в каковой есть понятие приватного и публичного ключей
2) Если не вдаваться в математические тонкости асимметричной криптографии, навроде теоремы Эйлера, Ферма, Галуа и проч. мастодонтов то эти ключи (например, в алгоритме RSA) вычисляется на основе целых числе p, q
(необязательно кстати и простых):
PublicKey={e(p,q), p*q} //e(p,q) - некая целочисленная функция (публичная экспонента)
PrivateKey={d(p,q), p*q) //d(p,q) - также некая целочисленная функция (приватная экспонента)
грубо говоря, если знать эти 2 числа p, q
то можно вычислить ключи. Теперь внимание, атакующему всегда известно их произведение p*q
- из публичного ключа, который как явствует из его названия известен всем.
3) То есть чтобы дешифровать надо просто разложить некое число n
на 2 множителя p, q
. Задача называется факторизацией - алгоритмов масса, но в целом все очень печально (с точки зрения скорости).
4) Подходим к самому главному - ради чего весь цирк с конями и затевался: зачем требуется, чтобы p, q
были простыми? Здесь есть 2 ответа:
- Функции
e(p, q)
иd(p, q)
- работают не со всеми числами, то есть если подать им на вход непростое число, то функции могут не дать ничего. Зато еслиp, q
простые то функции работают безупречно. - Для усложнения факторизации
n
: разложение большого числа на простые сомножители усложняется с ростом длины числа какn*log(n)
, то есть вы раскладываете 1024 битовое число, то сложность грубо говоря будет1024*2^1024
, но если число вдруг окажется четным то его сложность составит уже512*2^1023
- то есть вычислительная сложность упадет в 4 раза - соответственно простота гарантирует увеличение вычислительной сложности.
-
4Если сократить ответ - то получится "используются простые числа....есть какие-то функции, e(p, q) и d(p, q), которые безупречно работают только с простыми числами, ". Т.е. используются простые числа потому что на составных шифрование может не работать. Отлично обоснованный ответ, но по сути - не намного информативнее "математика того требует" из комментариев к вопросу :)– user177221Commented 3 нояб. 2017 в 23:29
-
А точно ли будет усложнение факторизации, ведь если разложить на множители непростое число для примера 60 (6*10, 3*20, 12*5, 4*15) - по сути 4 варианта подходящие. И простое число 57 (3*19) - всего один вариант и сразу подходящий (с первой попытки взломщик гипотетически его бы определил). Вроде бы в 4 раза сложнее подобрать, но имея библиотеку простых чисел, взломщики же будут оперировать только с простыми числами коих меньше нежели непростых (т.е. и перебирать нужно будет намного меньше). А если использовались бы все числа - в случае простых вероятность попадания выше, но и перебора больше Commented 4 нояб. 2017 в 11:17
Кажется разобрался с этой темой. На примере Диффи-Хеллмана. Чтобы найти ключ K, нужно решить уравнение K=g^a*b mod p, где "g", "p" - известно. Произведение простых чисел (очень больших) действительно сложно подобрать. И нужно использовать именно простые числа потому что нет базы данных среди больших простых чисел (а базы данных нет потому что нереально перебрать такие большие цифры), иначе бы это сильно ускорило решение задачи, как и со всеми числами. Но это в теории, а на практике серьезные взломщики вряд ли будут перебирать произведение 2-ух простых чисел. Т.к. чтобы найти секретный ключ K, можно решить и другое уравнение, которое тоже равно секретному ключу. K=B^a mod p, где "p" известно, а "B" можно перехватить (т.к. эта информация в незащищенном видео передается по сети). И тогда уже останется подобрать только "a". А если учесть, что "a" - как минимум нечетное и огромное (порядка 10^100) - отбросить на конце четные и диапазон слишком маленьких чисел. Хотя даже при всем при этом "a" замучаешься подбирать)
Одна причина в том, что легко умножить 2 большие простые числа, например
393050634124102232869567034555427371542904833 * 170141183460469231731687303715884105727
дает сразу
66874100049762646240147492397977579549553083399872470020691839934725993584071278591
(Python
, < 0.2 секунд), no обратное сделать (разложить большое число на простые числа) практически не возможно - нет общего достаточно быстрого алгоритма (см. Алгоритмы факторизации.)
Вообще это работа на несколько лет даже для супер компьютеров.
-
1Какой вы ожидаете увидеть здесь ответ? За всем этим стоит очень сложная математическая теория. Вы думаете, вам здесь кто-то в ответе на 5 строчек объяснит эту все теорию, и вам сразу станет все понятно? Так не бывает. Невозможно объяснить человеку, который не умеет умножать числа, что такое интеграл и производная, и зачем они нужны.– ZergatulCommented 3 нояб. 2017 в 20:15
-
1
-
1@ПавелИгорев, если вы перемножаете два простых числа, то обратная операция даст так же только эти два числа. Если вы перемножаете два "непростых" числа, то обратная операция уже дает не один вариант.– user239133Commented 3 нояб. 2017 в 20:22
-
2Смотрите,
120 = 2 * 60 = 3 * 20 = 4 * 15 = 5 * 24 = 6 * 20 = 8 * 15 = 10 * 12
. Когда я даю вам число120
, вы узнаете, какие 2 числа я перемножил? Но когда я даю вам например число77
, это совсем другое.– MarianDCommented 3 нояб. 2017 в 21:25 -
1
В TLS для генерации ключей чаще всего используется криптоалгоритм RSA. В его основе лежит предположение, что факторизация произведения простых чисел является вычислительно сложной операцией.
Легко умножить два простых числа, но очень сложно имея только произведение получить исходные числа. На сегоднешний день не существует эффективного алгоритма, который позволяет это сделать быстро.
-
Неправильно говорить, что в TLS используется RSA. Он может использоваться, а может и не использоваться. Может использоваться для генерации ключей, а может и для подписи.– ZergatulCommented 3 нояб. 2017 в 23:41