действительно ли это - корректный способ генерировать rsa ключи?
этот код собирается дать мне правильные значения для ключей RSA (предполагающий, что другие функции корректны)? Я испытываю затруднения, заставляя мою программу дешифровать правильно, поскольку в определенных блоках не дешифруют правильно
это находится в Python:
import random
def keygen(bits):
p = q = 3
while p == q:
p = random.randint(2**(bits/2-2),2**(bits/2))
q = random.randint(2**(bits/2-2),2**(bits/2))
p += not(p&1) # changes the values from
q += not(q&1) # even to odd
while MillerRabin(p) == False: # checks for primality
p -= 2
while MillerRabin(q) == False:
q -= 2
n = p * q
tot = (p-1) * (q-1)
e = tot
while gcd(tot,e) != 1:
e = random.randint(3,tot-1)
d = getd(tot,e) # gets the multiplicative inverse
while d<0: # i can probably replace this with mod
d = d + tot
return e,d,n
один набор ключей генерировал:
e = 3daf16a37799d3b2c951c9baab30ad2d
d = 16873c0dd2825b2e8e6c2c68da3a5e25
n = dc2a732d64b83816a99448a2c2077ced
2 ответа
Я предполагаю, что вы делаете это для развлечения и обучения, а не для чего-то, что нуждается в реальной безопасности.
Вот несколько вещей, которые я заметил (без особого порядка):
Вам не гарантировано, что n будет иметь длину
бит. Она может быть такой же короткой, какбит - 4.randomне является криптографически безопасным генератором случайных чисел.Обычно (и так же безопасно) выбирают публичную экспоненту,
e, равную 65537. Это простое число, поэтому проверку на сопряженность можно заменить проверкой на делитель.Немного странно искать
e, задаваяe = tot(проверка на сопряженность обязательно провалится).
В остальном все выглядит нормально. Ключ, похоже, тоже работает нормально. Есть ли у вас пример блока, который расшифровывается неправильно? Помните, что вы можете шифровать только те данные, которые меньше, чем n. Поэтому с 128-битным ключом (как в вашем примере) вы не можете зашифровать все 128-битные числа.
Математически ваши n , e и d , похоже, соответствуют правилам RSA. (т.е. для каждого простого числа r , которое делит n , r 2 не делит n , и d является инверсией e по модулю r-1 ). Однако RSA - это нечто большее; он также требует некоторых правил заполнения, которые определяют, как сообщение (последовательность байтов) должно быть преобразовано в целое число по модулю n и обратно. Стандартное заполнение (см. PKCS # 1 ) подразумевает, что к сообщению добавлено не менее 11 байтов, и результат все равно не должен быть больше n . Следовательно, при 128-битном модуле , подобном показанному вами, максимальная длина входного сообщения для шифрования будет 5 байтов.
Кроме того, некоторые реализации RSA отказываются работать с ключами RSA, которые слишком малы для безопасности. 128-битный модуль может быть разложен на множители за считанные секунды (см. на этой странице Java-апплет факторизации, который использует ECM и квадратное сито для разложения относительно небольших чисел, таких как ваше). Текущая запись факторизации - 768 бит; длина модуля не менее 1024 бит рекомендуется для краткосрочной безопасности. Типичная реализация RSA допускает использование 512-битных ключей, но многие отвергают все, что короче этого.
Другая возможная проблема заключается в относительном порядке p и q . Уравнения, изложенные в PKCS # 1, предполагают, что p> q (в противном случае требуется дополнительное вычитание в части CRT). Если у вас есть p , то некоторые реализации могут ошибаться (я столкнулся с этим в стандартной реализации Microsoft RSA в Windows). Просто сравните p с q и при необходимости поменяйте их местами.
По-прежнему на уровне практичности, некоторые широко распространенные реализации RSA будут отказываться от ключа RSA, так что публичная экспонента e не помещается в 32-битное целое число (это включает реализацию RSA, используемую в Windows, в в частности, с помощью Internet Explorer для подключения к веб-сайтам HTTPS - поэтому, когда я пишу «широко распространенный», я имею в виду именно это). На безопасность RSA, похоже, не влияет выбор e , поэтому обычно выбирают небольшой e , который ускоряет часть, использующую открытый ключ (т. Е.шифрование в отличие от дешифрования или проверка подписи в отличие от генерации подписи). e = 3 - это лучшее, что вы могли сделать, но по традиционным причинам (включая историческое недоразумение о предполагаемой слабости) часто используется e = 65537 . Вам просто нужно иметь e , относительно простое с p-1 и q-1 . На практике вы сначала выбираете e , а затем выполняете цикл в генерации для p и q , если они не соответствуют этому дополнительному правилу.
С точки зрения безопасности:
Ваш процесс генерации неоднороден, так как одни простые целые числа будут выбираться чаще, чем другие. В частности, простое число p такое, что p + 2 также является простым числом, почти никогда не будет выбрано. При правильном размере модуля, этот не должен быть проблемой (этот особый вид систематической ошибки был изучен и, как выяснилось, не представляет большой проблемы), но тем не менее это плохая связь с общественностью.
Ваш n может быть немного меньше, чем ваш целевой размер, в случае, если и p , и q близки к нижней границе своего диапазона генерации. Простой способ избежать этого - ограничить диапазон [sqrt (2) * 2 b-1 , 2 b ] для обоих p и q .
Я не могу поручиться за безопасность используемого вами модуля
random.Создать криптографически безопасный генератор случайных чисел - непростая задача.Вообще говоря, правильная реализация RSA без утечки конфиденциальной информации по различным побочным каналам (время, использование кэш-памяти ...) - непростая задача. Если вам нужна безопасность на практике,вам действительно следует действительно использовать существующий пакет. Я считаю, что у Python есть способы взаимодействия с OpenSSL .