Привет,
У меня есть вопрос относительно временной сложности атаки «встреча посередине» на шифрование учебника RSA. Предположим, я пытаюсь зашифровать симметричные ключи разной длины без заполнения с помощью алгоритма RSA. Примеры ключей:
- 56-битный ключ DES (с битами четности): DA13511CAB329E32 (без битов четности можно факторизовать: BC6AF11Ã12864009)
- 80-битный ключ Skipjack: 54C22E82E4E2F5FD9A5D (можно разложить на множители: 3537Ã197BF2D963817B70B)
- 128-битный ключ AES: CF15C540E2E43F764B1F995E30BBE883 (можно разложить на: BBC80693039D7291Ã11A51051306064BD3)
Теперь каждый симметричный ключ будет зашифрован открытым ключом RSA:
показатель степени: 65537, модуль: случайный и разный для каждого шифрования
Я знаю: c (зашифрованный текст RSA), e (показатель степени), n (модуль) из следующего уравнения:
$c=k^e\bmod n$
и я пытаюсь найти k (симметричный ключ)
Чтобы выполнить встречу посередине, я должен сделать следующее:
Для симметричного ключа с пространством ключей, равным n (для DES $n=2^{56}$, для Скипджека $n=2^{80}$, для АЕС $n=2^{128}$) Я должен сгенерировать ассоциативный массив A (псевдокод):
Теперь пытаюсь найти два множителя k, один уже где-то в массиве A, другой будем искать в цикле (псевдокод):