Квантовый криптоанализ


Квантовый криптоанализ


Криптография с открытым ключом

Математики очень долго старались решить проблему передачи ключа (смотри введение в квантовую криптографию). В 1970-х годах придумали хитрую идею - системы с открытым ключом. В таких системах, пользователем не надо договариваться заранее о ключе перед тем, как послать сообщение. Они работают на принципе сейфа с двумя ключами: один общий ключ для того, чтобы закрыть его, а другой, частный, для того, чтобы открыть его. У всех есть ключ для того, чтобы закрыть сейф, так что любой человек может оставить в нём сообщение. но только у одного человека есть ключ, чтобы забрать это сообщение. На практике, два ключа - это два больших целых числа. Можно легко получить общий ключ из частного, но не наоборот. Система использует тот факт, что определённые математические операции легче производить в одном направлении, а не в противоположном. Криптосистемы с открытым ключом избегают проблем с передачей ключа, но, к несчастью, их безопасность зависит от недоказанных математических допущений, таких, как трудности факторизации (разложении на составляющие) больших чисел (RSA - самая популярная криптосистема с открытым ключом, сильно зависит от факторизации больших чисел). Враг, которому известен общий ключ, может, в принципе, вычислить частный ключ, потому что эти два ключа математически связаны, однако, сложность вычислений частного ключа из соответствующего общего ключа полностью зависит от факторизации больших чисел.

Трудность факторизации быстро возрастает с размером, то есть, количеством цифр числа, которые мы хотим разложить. Для того, чтобы увидеть это, возьмите число N, состоящее из L десятичных цифр (N ~ 10^L), и попробуйте разложить его путём деления на 2, 3, ..., Sqrt(N) и проверки остатка от деления. В худшем случае, вам понадобится приблизительно Sqrt(N) = 10^(L/2) делений для того, чтобы решить проблему - экспоненциальное увеличение функции L. Теперь представьте компьютер, способный производить 10^10 делений в секунду. Компьютер способен разложить любое число N, используя алгоритм последовательного перебора, примерно за Sqrt(N)/10^10 секунд. Возьмите число N, состоящее из 100 цифр, N = 10^100. Компьютер разложит это число примерно за 10^40 секунд, что гораздо больше, нежели 3.8 * 10^17 секунд (12 миллиардов лет) - примерный возраст вселенной!




Начало    Вперед



Книжный магазин