Криптография решает проблему защиты информации от перехвата противником в момент ее передачи. Это необходимо не только спецслужбам и преступникам, но и сравнительно мирным организациям: фирмам, желающим сохранить коммерческую тайну, банкам, чтобы защититься от подделки отправителя...
В первой половине прошлого века и раньше невозможность расшифровать информацию часто была основана на сокрытии механизма шифрования. Сегодня считается, что это недостаточно эффективно, так как механизм шифрования можно разгадать, да и не очень-то удобно постоянно придумывать новые хитроумные алгоритмы шифрования, например, для банков с тысячами клиентов этот способ совсем уж не подходит. Да и будет ли доморощенный шифр надежным?
Как правило, в наше время механизм шифрования данных не скрывается, а безопасность основана на секретности ключа. Ключ – сравнительно маленький объем информации в виде числа, набора символов или пароля, который позволяет алгоритму шифрования кодировать и декодировать информацию.
Для того чтобы другая сторона могла расшифровать информацию, необходимо передать ей ключ. Передавать его по тому же каналу не имеет смысла, так как если ключ будет перехвачен противником, то он сможет раскодировать послание. Что же делать? Передавать ключ по другим каналам, например, из рук в руки на бумажке или дискете? Во второй половине двадцатого века решение было найдено.
Можно использовать для шифрования и расшифровки разные ключи, при этом ключ для шифрования должен быть бесполезен в плане расшифровки. Тогда получается, что даже тот, кто закодировал информацию, будет не в состоянии ее раскодировать, что уж тогда говорить о противнике? В криптографии это называется шифрованием с несимметричным ключом. Несимметричность здесь обозначает именно невозможность получить один ключ из другого.
Другое название этого метода – шифрование с открытым ключом – еще более понятно. Ключ для шифрования можно передавать по открытым каналам и даже класть на домашнюю страничку в Интернет – это ничего не даст для расшифровки. Что, в общем-то, с ключами и делается, и не с целью поиздеваться над врагами, а для корреспондентов – им публичный ключ нужен для отсылки сообщения. Об этом подробнее в «криптография и передача информации».
Для шифрования с несимметричным ключом требуется два ключа: открытый ключ (public key) и секретный (private key). Открытый ключ используется для шифрования, секретный – для дешифровки. Процедура обмена информацией выглядит так: А передает Б открытый ключ, Б шифрует им свое сообщение, передает шифровку А, А использует для дешифровки секретный ключ. Весь этот процесс можно производить по открытому каналу, размещать информацию в общедоступных местах и т.п. Главное – не допустить хищения секретного ключа.
Можно или нет расшифровать сообщение, обладая лишь публичным ключом? Теоретически - да, практически - нет. Теоретически, если текст вообще возможно расшифровать, то его может расшифровать и тот, кто его зашифровал (это касается любого кодирования, не только шифрования с несимметричным ключом). Практически, ему на это может потребоваться больше времени, чем он проживет. Значительно больше – это несколько миллиардов лет. Достигается это за счет алгоритмов, которые сложно заставить работать в обратную сторону. Другое использование шифрования с открытым ключом – доказательство подлинности отправителя – будет рассматриваться позднее.
В качестве примера возьмем RSA – древнейший, если так можно выразиться, алгоритм шифрования с несимметричным ключом (появился он в 60х годах XX века).
В случае RSA сложно обратимый алгоритм – возведение A в степень B по модулю C (т.е. число A возводится в степень B, а затем берется остаток от деления результата на C). На сегодняшний день не известно алгоритма, позволяющего произвести обратную операцию иначе, как полным перебором всех возможных вариантов, а их может быть сколько угодно много, в зависимости от длины ключа. Существуют более простые алгоритмы взлома RSA, чем полный перебор, но ни один из них не является достаточно эффективным. Все они имеют экспоненциальную вычислительную сложность, что означает, что при увеличении длины ключа время на его взлом значительно возрастает. Пока не доказано, что такого алгоритма нет. Однако за его нахождение обещана кругленькая сумма, и то, что за наградой до сих пор никто не пришел, говорит о многом.
Изначально RSA предназначен для шифрования чисел, но его можно легко приспособить и для шифрования любой другой информации (например, текста) – нужно лишь закодировать ее в числа. RSA использует тождество (равенство при всех значениях переменной а < n): (a^d mod n)^e mod n=a, т.е. а в степени d, а затем в степени e, дает остаток от деления на n, равный a. Числа d и e вычисляются по определенному алгоритму (ниже). Получатель генерирует числа d, e и n. Публичный ключ – пара чисел (d,n) – может быть передан отправителю. Этого достаточно, чтобы зашифровать текст, но недостаточно, чтобы его расшифровать. Отправитель берет число, которое хочет зашифровать, возводит его в степень d, берет остаток от деления на n и отправляет его в таком виде по открытому каналу. Получатель возводит полученное число в степень e, берет остаток от деления, и получает число a, которое и зашифровал отправитель. Как создаются числа d, e и n? Генерируются два простых числа, p и q. Числа должны быть большими, их суммарный размер и называется длиной RSA-ключа. Число e – любое взаимно простое, то есть не имеющее общих делителей с (p-1)*(q-1). d – модулярная инверсия e с модулем (p-1)*(q-1), то есть произведение d*e по модулю (p-1)*(q-1) равно 1. Можно доказать, что из сгенерированные таким образом d, e и n дают тождество, используемое RSA. Лучшим способом взломать RSA было бы найти p и q, для этого достаточно разложить число n на простые множители. Опять – просто теоретически, но сложно практически: подходящий алгоритм для этого не изобретен, и, возможно, его не существует вообще.
