целочисленная факторизация и криптография

Question

я знаю, что криптография с открытым ключом использует простые числа, также знаю, что два больших (например, 100-значный) простых числа (P, Q) используются в качестве закрытого ключа, продукт представляет собой открытый ключ N = P * Q, ииспользование простых чисел объясняется тем, что факторизация N для получения P, Q слишком сложна и занимает много времени, я в порядке, но я озадачен, почему бы просто не использовать обычные большие не простые числа для P, Q итаким образом, факторизация N будет все еще трудной, потому что будет, потому что теперь возможны не только 2 фактора, но даже больше.

спасибо ....

Answer 1

Я не специалист по криптографии.

почему бы просто не использовать обычные большие не простые числа для P, Q

Потому что было бы больше факторов. Целочисленная факторизация - это атака на шифрование с использованием открытого личного ключа. Эта атака использует именно это отношение.

Можно было бы легче найти связь и возможные значения с более общими факторами. Все сводится к алгебре.

N = P * Q

если P и Q оба простые, то N имеет 4 фактора {N P Q 1}

Тем не менее! если P и Q оба имеют коэффициент 2

N / 4 = P / 2 * Q / 2

Если бы N могло быть 0..2 ^ 4096, то теперь это 0..2 ^ 4094, и так как 2 было фактором, другое большое число также было фактором.

Это означает, что я мог бы найти скалярное кратное, P ', Q' из P, Q S.T. P ', Q'

Я сам не до конца понимаю концепцию, но я верю, что это показывает, куда я иду с этим.

Вам придется искать место поменьше, пока вы не нажмете клавишу.

Answer 2

Вполне возможно использовать RSA с модулем N, который состоит из более чем двух простых факторов P и Q, но следует отметить две вещи:

1. Вы должны знать точное значение всех этих факторов, иначе вы не сможете получить закрытый ключ из открытого ключа при генерации ключа. Уравнение для двух простых RSA: 1 = D * E (мод LCM (P-1, Q-1)). Если вы действительно знаете эти основные факторы, вы можете выполнить расчет. Если вы не знаете основные факторы, вы не можете выполнить этот расчет, поэтому, кстати, поэтому безопасно сделать открытый ключ E, N открытым - вы не можете получить закрытый ключ D, если у вас есть только та информация, которую легко получить из открытого ключа, если только вы не можете использовать коэффициент N.

2. Безопасность RSA эффективно ограничена величиной второго по величине простого множителя модуля RSA N. Поиск небольших простых множителей, которые меньше 2 ^ 32, может быть сделан за доли секунды на современный компьютер, просто пытаясь разделить модуль N на каждое такое простое число и проверить, равен ли остаток нулю (означает, что N делится на это число) или нет (имеется в виду, что число не является фактором N). Если N состоит только из таких малых простых множителей, умноженных на один большой простой фактор Q, было бы тривиально также найти этот Q, просто разделив N на все маленькие факторы, чтобы получить N 'и проверить N' на простоту. Если N '- простое число, это последний простой множитель Q.

Answer 3

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