Что такое RSA

RSA - один из первых и весьма популярный алгоритм шифрования с открытым ключом - разработан основателями фирмы RSA (Rivest, Shmir, Adleman) в конце 70-x годов и назван по первымбуквам их фамилий.

 

Cтепень устойчивости зашифрованной информации к взлому, а также невозможность по открытому ключу восстановить закрытый определяются трудностью факторизации больших чисел и зависят от длины ключа.

 

Cейчас ключи длиной 512 битов рассматриваются как недостаточно устойчивые, поэтому в криптографическом программном обеспечении

рекомендуются 768 или 1024 битные ключи.

 

Часто используют комбинированный подход: сначала сообщение кодируются с помощью некоторого ключа по алгоритму типа DES, а затем ключ зашифровывается с применением RSA и передается вместе с закодированным сообщением. Это позволяет достичь высокой скорости обработки информации и в то же время обеспечивает надежную ее защиту.

 

Краткие основы RSA:
1. Выбираются большие простые числа M и N;
2. Вычисляется их произведение: Q=MxN;
3. Выбирается число D, которое должно быть взаимно простым с результатом умножения (M-1)x(N-1), т.е. не должно иметь с ним общих делителей, отличных от единицы;
4. Вычисляется число A из выражения (AxD) mod [(M-1)x(N-1)]=1;

Таким образом, пара чисел (A,Q) будет твоим открытым ключом, а пара чисел (D,Q) -- закрытым ключом. Понятно, что открытым ключом можно только закодировать исходный текст, для того, чтобы его раскодировать, нужен закрытый ключ.

Кодирование числа P: C=M^A mod Q;

Обратная операция: P=C^D mod Q;

 

Так вот, для того, чтобы поломать PGP (сиречь RSA), необходимо и достаточно уметь разложить число Q (которое мы возьмем, понятно, из открытого ключа, помещенного человеком в бурные воды, скажем, Fido и/или Internet) на простые множители. Вот тут-то и начинается самое интересное.

 

Простые множители числа - летопись в теории чисел, над ними бились многие математики. о увы, так ничего толком и не добились. В математике не существует_ теорем, могущих надежно предсказать, является ли число простым.

 

Есть теоремы, которые могут быстро установить, что число составное, но если условия теоремы не выполняются, то это не значит, что число простое: это значит, что оно ВРОДЕ БЫ простое, и надо применять более сильные теоремы, которые, увы, на машине проверяются только перебором. Далее, нет теорем, которые помогают хотя бы оценить количество простых сомножителей числа и порядок их величины.

 

Так что реально число из, скажем, трехсот десятичных знаков разложить на простые множители (если они, правда не лежат близко к корню из числа и т.д. -- есть легкие случаи) за разумное время нереально.

 

 


 

 

 
15.12.2008

Отзывы и комментарии

 


 
Тема
Ваше имя
Почтовый адрес
Текст сообщения
Ключ защиты:
Защита от спама
 
 
 
 
10.12  .NET Reactor
15.11  n
15.11  C# ClickOnce
 
01.08  Task Context
01.08  XLSX в Mono