Есть несколько способов иметь размер короткой клавиши.
1. С RSA
Открытый ключ RSA состоит из большого числа n ("модуль") и (обычно небольшого) числа e (открытый показатель). e может быть всего 3, а в закрытом режиме (где вы управляете генерацией ключа) вы можете принудительно использовать обычный e , одинаковый для всех. Типичный размер для n составляет 1024 бита (то есть 128 байтов).
n - произведение двух простых чисел ( n = p * q ). Знание p и q достаточно для восстановления закрытого ключа (номинально значение d , которое является мультипликативным обратным значением e по модулю р-1 и q-1 ). Предполагая, что n известно, достаточно знания только p (если вы знаете n и p , вы можете вычислить q с простым делением). Для обеспечения надлежащей безопасности p и q должны иметь одинаковые размеры, поэтому даже если взять меньшее из двух, вам все равно нужно хранить около 512 бит или около того - это 64 байта) .
Также было предложено выбрать маленький d («частный показатель»). Но это делает e практически случайным, а следовательно, большим; Вы больше не можете использовать обычное маленькое значение для e . Это в основном удваивает размер открытого ключа. Кроме того, принудительное нажатие на d может ослабить ключ (это было показано в случае, когда размер d не превышает 29% от размера n , но это никоим образом не доказывает, что d 30% размера n является безопасным). Обычно это считается плохой идеей.
2. С DSA / Diffie-Hellman
DSA - это алгоритм цифровой подписи. Диффи-Хеллман - это алгоритм обмена ключами. Оба являются «асимметричными криптографическими алгоритмами», и вы будете использовать один или другой, или оба, в зависимости от ваших потребностей. В обоих случаях существует общедоступная математическая группа (числа по модулю большого простого числа p для базовых DSA и DH; варианты эллиптической кривой используют в качестве группы эллиптическую кривую); открытый ключ - это элемент группы, а закрытый ключ - это дискретный логарифм этого элемента относительно обычного генератора. Другими словами, задаются простое число p и число g по модулю p (они могут совместно использоваться всеми владельцами ключей, даже); закрытый ключ - это число x , соответствующее открытому ключу y = g x mod p . Закрытый ключ выбирается по модулю маленького простого числа q . q известен и должен быть достаточно большим, чтобы победить универсальные алгоритмы дискретного логарифма; на практике нам нужно 160 или более бит q .
Это означает, что закрытый ключ умещается примерно в 20 байтов. Это не 20 десятичных цифр, а ближе.
3. С ЛЮБЫМ криптографическим алгоритмом
Когда вы генерируете пару ключей, вы делаете это с помощью:
- детерминированная процедура;
- источник случайных битов.
Например, с RSA вы генерируете p и q , создавая случайные нечетные числа правильного размера и зацикливаясь, пока не будет найдено простое число. Для данного случайного источника весь процесс является детерминированным: при одинаковых случайных битах будут найдены одинаковые простые числа p и q .
Следовательно, вы можете разработать PRNG, засеянный секретным ключом K и использовать его в качестве случайного источника для процесса генерации ключа. Всякий раз, когда вам нужен закрытый ключ, вы снова запускаете процесс генерации ключа, используя K в качестве ввода. И вуаля! Ваш личный ключ, который вам нужно хранить, теперь K .
С RSA это делает использование закрытого ключа довольно дорогим (генерация ключа RSA не легка).Однако с DSA / Diffie-Hellman это было бы очень недорого: закрытый ключ - это только случайное число по модулю q (групповой порядок), которое может быть сгенерировано с гораздо меньшими затратами, чем использование закрытого ключа дляцифровая подпись или обмен асимметричным ключом.
Это приводит к следующей процедуре:
- "Закрытый ключ" в том виде, в котором он хранится, равен K .
- Параметры группы для DSA / Diffie-Hellman жестко заданы в приложении;все используют одну и ту же группу, и это не проблема.Порядок группы q , известное простое число не менее 160 бит.Если вы используете вариант эллиптической кривой, то q является свойством кривой, следовательно, является заданным.
- Когда вам нужно подписать или выполнить обмен ключами (обмен ключами используется дляэмулировать асимметричное шифрование), вы вычисляете SHA-512 ( K ), который дает 512-битную последовательность.Вы берете первую половину (256 бит), интерпретируете ее как число (с соглашением с прямым или обратным порядком байтов, если хотите, при условии, что вы всегда используете одно и то же соглашение), и уменьшаете его по модулю q чтобы получить закрытый ключ DSA.Точно так же вы используете вторую половину вывода SHA-512 для получения закрытого ключа DH.
Генерация ключа очень незначительна, но это не создает особых проблем с безопасностью.Обратите внимание, что если вам нужен ключ DSA и ключ DH, то вы можете использовать одну и ту же группу, но вы не должны использовать один и тот же закрытый ключ (следовательно, использование обеих половинВыход SHA-512).
Насколько большим должно быть K ?С хэш-функцией, такой как SHA-512, K может быть любой произвольной последовательностью битов.Тем не менее, K должно быть достаточно широким, чтобы победить исчерпывающий поиск.1024-битный ключ RSA или 1024-битный модуль DSA (модуль p для DSA) обеспечивают уровень безопасности, который очень приблизительно эквивалентен 80-битному симметричному ключу.Аналогично, 160-битный групповой порядок для DSA / DH обеспечивает тот же уровень.80 бит не так много;Вы не можете опускаться ниже этого уровня, если хотите, чтобы вас воспринимали всерьез.Это означает, что K следует выбирать среди пробелов, по крайней мере, 2 80 возможных ключей;другими словами, если K выбран как равномерно случайные байты, то он должен иметь длину не менее 10 байтов.С десятичными цифрами вам нужно минимум 24 цифры.Все, что ниже этого, является по сути слабым, и это неизбежно.
Стандартное предупреждение: Если что-то из вышеперечисленного не очевидно или неясно для вас, тогда даже не думайте о его реализации.Реализация криптографического алгоритма является сложной задачей, особенно из-за того, что самые опасные ошибки не могут быть проверены (это не потому, что программа работает и, кажется, работает должным образом, что она не содержит слабых мест безопасности).