Рассмотрим математические результаты, которые положены в основу этого алгоритма.

Определение 1. Сравнением целых чисел a и b будем называть соотношение между ними вида a = b + mk, означающее, что их разность (a – b) делится на заданное положительное число m, называемое модулем сравнения. При этом а называется вычетом числа b по модулю m.

Определение 2. Говорят, что два целых числа a и b сравнимы между собой и обозначают этот факт через a = b (mod m), если a и b имеют одинаковые остатки при делении на m.

Приведем некоторые очевидные свойства сравнений.

Пусть a = b (mod m) и с = d (mod m). Тогда:

1) a (+-) c = b (+-) d (mod m),
2) a*c (+-) b*d (mod m).

Легко также проверить, что операция сравнения по модулю m является эквивалентностью (выполняются свойства рефлексивности, транзитивности и симметричности), и, следовательно, можно говорить о разбиении множества целых чисел Z на непересекающиеся классы эквивалентности.

Теорема 1. (Малая теорема Ферма). Если p – простое число, то (x в степени (p – 1)) = 1 (mod p) для любого х, простого относи-тельно p, и (x в степени p) = х (mod p) для любого х.

Определение 3. Функцией Эйлеpа Ф(n) называется число положительных целых, меньших n и простых относительно числа n.

Теорема 2. Если n = pq, (p и q – отличные друг от друга простые числа), то Ф(n) = (p – 1)(q – 1).

Теорема 3. Если n = pq, (p и q – отличные друг от друга простые числа) и х – простое относительно p и q, то
(x в степени Ф(n)) = 1 (mod n).

Следствия:

1. Если n = pq, (p и q – отличные друг от друга простые числа) и е - пpостое число относительно Ф(n), то отображение Е(e,n): x -> (x в степени e) (mod n) является взаимно однозначным на алгебраическом кольце вычетов Z(n).

2. Если е – пpостое число относительно Ф(n), то существует целое число d, такое, что e*d = 1 (mod Ф(n)).

Пусть n = pq, где p и q – различные простые числа. Если e и d удовлетворяют уравнению (см. следствие 2), то отображения Е(e,n) и Е(d,n) являются инверсиями на кольце Zn.

Как Е(e,n), так и Е(d,n) легко рассчитываются, когда известны e, d, p, q.

Если известны e и n, но p и q неизвестны, то Е(e,n) представляет собой однонаправленную функцию; нахождение Е(d,n) по заданному n равносильно разложению n на простые сомножители.

Если p и q – достаточно большие простые числа, то разложение n – достаточно сложная вычислительная операция.

Это и заложено в основу системы шифрования RSA.

Пользователь i выбирает пару различных простых p(i) и q(i) и рассчитывает пару целых (e(i), d(i)), которые являются простыми относительно Ф(n(i)), где n(i) = p(i)*q(i). Справочная таблица содержит публичные ключи {(e(i), n(i))}.

Итак, в реальных системах RSA реализуется следующим образом:
1.Каждый пользователь выбирает два больших простых числа p и q, и в соответствии с описанным выше алгоритмом вы-бирает два простых числа e и d; как результат умножения первых двух чисел устанавливается n. После этого {e, n} образует открытый ключ, а {d, n} – секретный (хотя можно взять и наоборот).
2.Открытый ключ публикуется и доступен каждому, кто желает послать владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. После шифрования, сообщение невозможно дешифровать с помощью открытого ключа. Владелец же секретного ключа без труда может pасшифpовать принятое сообщение.

P/S/ Надеюсь, математические формулы понятны

Рассмотрим небольшой пpимеp, иллюстрирующий применение алгоритма RSA.
Пусть требуется зашифровать сообщение “САВ”.
Для простоты будем использовать маленькие числа (на практике применяются гораздо большие). Пошагово проследим процессы шифрования и дешифрования.

1.Выберем p = 3 и q = 11.
2.Определим n = 3 * 11 = 33.
3.Найдем (p – 1)(q – 1) = 20. Следовательно, в качестве e можно взять число, взаимно простое с 20, напpимеp, e = 3.
4.Выберем число d. В качестве такого числа может быть взято любое число, для которого выполняется соотношение
(d * 3) = 1(mod 20), напpимеp 7.
5.Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А -> 1, В-> 2, С-> 3. Тогда исходное открытое сообщение принимает вид M = (3,1,2). Зашифруем сообщение с помощью ключа {7, 33}:

s1 = (3 в степени 7) (mod 33) = 2187 (mod 33) = 9,
s2 = (1 в степени 7) (mod 33) = 1 (mod 33) = 1,
s3 = (2 в степени 7) (mod 33) = 128 (mod 33) = 29.

Зашифрованное сообщение после этого примет вид S = (9, 1, 29).

6. Расшифруем полученное зашифрованное сообщение (9, 1, 29) на основе секретного ключа {3, 33}:

m1 = (9 в степени 3) (mod 33) = 729 (mod 33) = 3,
m2= (1 в степени 3) (mod 33) = 1 (mod 33) = 1,
m3 = (29 в степени 3) (mod 33) = 24389 (mod 33) = 2.

Как можем видеть, дешифрование шифртекста S = (9, 1, 29) привело к исходному открытому тексту M = (3, 1, 2).

По тому же Керкхоффсу, криптоалгоритм должен удовлетворять следующим требованиям (выдержка из полного текста):
1) Должен обеспечивать достаточную стойкость ко взлому. Несмотря на то, что одиночное шифрованное сообщение может быть в принципе невзламываемым, часто бывает необходимо переслать сотни сообщений, зашифрованных в одной и той же системе. И хотя одиночное сообщение может быть трудно или невозможно расшифровать, большое число одинаково зашифрованных сообщений взломать куда проще. «Достаточная» стойкость ко взлому означает также, что разработчику шифра необходимо учитывать фактор времени: на взломку шифра должно требоваться время, достаточное для того, чтобы сообщения успевали потерять ценность для криптоаналитика. Обеспечение абсолютной стойкости шифра редко необходимо, и даже если оно возможно, обычно требует неоправданных затрат.
2) шифр должен быть прост в использовании
3) стойкость шифра ко взлому должна полностью зависеть от обеспечения секретности ключа, а не алгоритма

3 момента - залог успеза алгоритма .. Оно, в принипе, и понятно

-----------
Кстати, существуют же и невзламываемые шифры. Один из таких - шифр Вернама
Там на примере перфокарт со случайными дырками .. Анализу не поддается, потому как расстановка случайна
Почему не используется? Потому что процесс создания случайного ключа очень непростой и занимает кучу процессорного времени .. Возможно, в скором времени мы и сможем таковым шифровать, но пока .. ждем и играем в игрушки ..

Согласен полностью.

Во-первых, vitalyu и eXceed, спасибо за поддержание темы.

Во-вторых, vitalyu, я немного уточну указанное правило Керкхоффа (просто в дополнение к сказанному; это действительно интересно может быть для новичков, хотя и не по теме).

Правило Керкхоффа

Голландский криптограф Керкхофф (1835-1903) впервые сформулировал фундаментальное правило стойкости криптосистемы (шифра) – стойкость криптосистемы (шифра) должна определяться только секретностью ключа.

Иными словами, правило Керкхоффа состоит в том, что весь алгоритм шифрования, кроме значения секретного ключа, известен криптоаналитику. Это обусловлено тем, что криптосистема обычно рассматривается как открытая система.
Такой подход отражает очень важный принцип технологии защиты информации: защищенность системы не должна зависеть от секретности чего-либо такого, что невозможно быстро изменить в случае утечки секретной информации.
Предполагается, что все долговременные элементы системы известны криптоаналитику.

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

--
Здесь создал еще одну, преимущественно информационную, тему по видам криптосистем. Подключайтесь!

P.S. С появлением квантовых компьютеров можно будет использовать квантовую криптографию =)

P.P.S. Такая заинтересованность в теме заставляет задуматься либо о частоте посещения студентами пар по криптографии либо.. о подаче материала на самих лекциях.

..

А на лекции ходим. Цитирую Саббитова: "В государственной информационной безопасности все что теоретически возможно, считается возможным!".

З.Ы. Я тебя уже подкалываю, в ответ на твои уколы Да, у нас Берсенев не ведет, но голова у нас есть и учиться хочет. ИМХО, здесь я узнаю куда больше, чем на лекциях в универе! Спасибо еще раз за форум!

Выдержка из Вики по квантовым компьютерам:

+1

тоже не понял

Хе-хе, идеалисты

Абсолютной защиты НЕ БЫВАЕТ. Собственник информации определяет для себя приемлемый уровень рисков. Такой, при котором ущерб от нарушения доступности/целостности/конфиденциальности информации будет считаться допустимым и соответсвовать принимаемым мерам по защите. К тому же сумма средств, затраченных на обеспечение информационной безопасности НЕ ДОЛЖНА превышать потенциальный ущерб, который может понести собственник, иначе все превращается в фейк))))) Использование любых средств и методов защиты инфомации направлено лишь на снижение степени риска до необходимого уровня.

Сорри за оффтоп, а теперь ближе к теме:

Но все же здесь разговор не только о том, что делается, но и о том, что можно сделать (включая теорию). Выше я писал про шифр Вернама, и это подтверждение абсолютной защиты в узком спектре задач..

Я не знаю, к чему тут споры вообще, по-моему, спорить то не о чем .. 2 позиции, с которых можно подходить к этому вопросу - так и останутся, щас закидаем тут всю ветку доводами, а весы не сдвинутся ..

Та же ситуация и с Квантовыми ЭВМ, и Квантовой криптографией .. Если прочитать от и до по этому вопросу, то видно, что фундамент математики не меняется .. В этом случае в криптоалгоритмах используются расширенная математика и расчет через кубиты (2^N мерные пространства) .. В этом случае у математиков появится еще парочка идей .. но законы математики это не подорвет .. Почитай полностью, там даже с примерами .. Если разобраться - то ничего нетрадиционного в этом нет ..

Аналогично: Как для витой пары категории 5е смогли увеличить скорость передачи до 1Gb/s?? Просто ввели 5 потенциалов ..
А в нашем вопросе ввели несколько состояний ..