Почему при шифровании TLS используются именно простые числа?

#алгоритм #безопасность #ssl #шифрование #криптография

Почему при шифровании TLS, да и вообще в криптографии используются именно простые
числа? Почему бы не использовать любые? 
    

Ответы

Ответ 1

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

393050634124102232869567034555427371542904833 * 170141183460469231731687303715884105727


дает сразу

66874100049762646240147492397977579549553083399872470020691839934725993584071278591


(Python, < 0.2 секунд), no обратное сделать (разложить большое число на простые числа)
практически не возможно - нет общего достаточно быстрого алгоритма (см.  Алгоритмы
факторизации.)

Вообще это работа на несколько лет даже для супер компьютеров.


Ответ 2

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 накладываются соответствующие ограничения.


Ответ 3

На самом деле ничего суперсложного здесь нет. 

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

Кажется разобрался с этой темой. На примере Диффи-Хеллмана. Чтобы найти ключ K, нужно
решить уравнение K=g^a*b mod p, где "g", "p" - известно. Произведение простых чисел
(очень больших) действительно сложно подобрать. И нужно использовать именно простые
числа потому что нет базы данных среди больших простых чисел (а базы данных нет потому
что нереально перебрать такие большие цифры), иначе бы это сильно ускорило решение
задачи, как и со всеми числами. Но это в теории, а на практике серьезные взломщики
вряд ли будут перебирать произведение 2-ух простых чисел. Т.к. чтобы найти секретный
ключ K, можно решить и другое уравнение, которое тоже равно секретному ключу. K=B^a
mod p, где "p" известно, а "B" можно перехватить (т.к. эта информация в незащищенном
видео передается по сети). И тогда уже останется подобрать только "a". А если учесть,
что "a" - как минимум нечетное и огромное (порядка 10^100) - отбросить на конце четные
и диапазон слишком маленьких чисел. Хотя даже при всем при этом "a" замучаешься подбирать)


Ответ 5

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

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