Криптосистема без передачи ключей.

Пусть абоненты А. В. С... условились организовать между собой секретную переписку. Для этой цели они выбирают достаточно боль­шое простое число р такое, что р — 1 хорошо разлагается на не очень большие простые множители, а за тем каждый m абонентов независимо один от другого выбирает себе некоторое натуральное число, взаимно простое с р — 1, Пусть число абонента А п, абонента В Ь и т.д. Числа <ь Ь. ... составляют первые секретные ключи соответствующих абонентов. Вторые секретные ключи (а для .4, '3 для В и т,д,( нахо­дятся m уравнений: для A m па = 1 (mod rip ))- ^ < о. < р— 1: для В in Ы = 1 (mod у{р)). 0 < }3 < р — 1 и т.д. Пересылаемые сообще­ния, коды-числа, должны быть меньше р — I , В случае, когда сообщение больше или равно р—1. оно разбивается на части таким образом. чтобы каждая часть была числом, меньшим р — 1.

Предположим абонент А решил отправить сообщение т [т < р — 1) В. Для этого он сначала зашифровывает свое сообщение ключом а₁, по­лучая по формуле m ₁ ≡ m ⁰ (mod р) шифрованное сообщение m ₁ , кото­рое отправляется В. В, получив m _1, «зашифровывает его своим ключом b,получая по формуле т₂ ≡  (mod р) шифрованное сообщение т₂, которое отправляется обратно к А. А шифрует полученное сообщение ключом α по формуле  (mod p ) и окончательно отправляет m₃ к В. В, используя ключ β, сможет теперь расшифровать исходное сообщение m . Действительно, (mod p ), т.к. аαbβ ≡ 1 (modφ(р)),следовательно, аαbβ = kφ (р)+ 1 для некото­рого целого kи (mod p), т.к.  (mod р) по теореме Эйлера-Ферма.

Пример. Абоненты А и В вместе выбрали р = 23 (φ (23) = 22), А выбрал а = 5, a В  b= 7. Затем из уравнения 5α≡ 1 (mod φ (23)) А находит  α = 9, а В из подобного уравнения находит β= 19. При передаче сообщения т = 17 от А к В сначала А отправляет к В т₁ ≡ 17⁵ ≡ 21 (mod 23), из т₁ =21 В вычисляет т₂ ≡21⁷ ≡10 (mod 23) и отправляет его обратно А, из m₂ =10 А вычисляет для В m₃ ≡ 10⁹ ≡ 20 (mod 23), наконец, В может прочитать посланное ему сообщение 20¹⁹ ≡ 17 (mod 23).

 

Криптосистема с открытым ключом.

Первую и наиболее известную систему с открытым ключом разработали в 1978 году американцы Р. Ривест (Rivest R.), Э, Шамир (Shamir А.), иЛ. Адлеман (Adleman L.). По их именам эта система получила название RSA.

Пусть абоненты А и В решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа ( pa _1, p а₂ и р_β1, р_β2 ), находит их произведение (r_А и r_В), функцию Эйлера от этого произведения (φ(r_А) и φ(r_В))и случайное число (а и b ), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, А из уравнения aα ≡1 (mod φ(r_А))находит α (0 < α< φ(r_А)), а В из уравнения bβ≡1 (mod φ(r_В)) находит β(0 < β < φ(r_В)). Затем А и В печатают доступ­ную всем книгу паролей вида:

 

 

Теперь кто угодно может отправлять конфиденциальные сообще­ния А или В. Например, если пользователь книги паролей хочет от­править сообщение т для В (т должно быть меньшим r_В, или де­литься на куски, меньшие r_В), то он использует ключ b из книги паро­лей для получения шифрованного сообщения m ₁ по формуле т₁ = т^ь (mod r в), которое и отправляется В. В для дешифровки т₁ исполь­зует ключ β в формуле (mod r_В), т. К. bβ≡ 1 (mod φ(r_В)), следовательно, bβ= k φ(r_В)+ 1 для некоторого целого k и (mod r_В), т.к.  1 (mod r_В ) пo теореме Эйлера-Ферма. Доказано, что задача нахождения секрет­ного ключа β по данным аз книги паролей имеет ту же сложность, что и задача разложения числа r_Вна простые множители.

Пример, Пусть для А р_А1 = 7 и р _А2 = 23. тогда r_А = р_А1 р _А2 = 161, φ (161)= 6 *22 = 132, а = 7, α = 19 (из уравнения 7 α ≡1 (mod 132)). Следовательно, запись в книге паролей для А будет иметь вид А: 161, 7. Если кто-то захочет отправить А секретное сообщение m = 3, то он должен сначала превратить его в шифровку т₁ по формуле т₁≡3⁷ ≡ 94 (mod 161). Когда А получит т₁= 94 он дешифрует его по формуле m ≡94¹⁹ ≡3 (mod 161).

 

Электронная подпись.

Криптосистема с открытым ключом открыта для посылки сообще­ний для абонентов из книги паролей для любого желающего. В системе с электронной подписью сообщение необходимо "подписывать", т.е. яв­но указывать на отправителя из книги паролей.

Пусть W ₁ ,W ₂… W_n  абоненты системы с электронной подпи­сью. Все они независимо друг от друга выбирают и вычисляют ряд

чисел точно так же как и в системе с открытым ключом. Пусть i-ый абонент (1 ≠ i ≤n) выбирает два больших простых числа p_{i 1} и р _{i 2} , затем вычисляет их произведение r_i = p_{i 1} р _{i 2} и функцию Эйлера от него φ(r_i), затем выбирает первый ключ а_i из условия 0 < а_i , < φ(r_i), НОД(а_i, φ(r_i)) = 1 и, наконец, вычисляет второй ключ α_i из уравнения а_i α_i ≡ 1 (mod φ(r_i)). Записи в книге паролей будет иметь вид:

 

 

Если абонент W ₁ решает отправить секретное письмо m W ₂ то ему следует проделать следующую последовательность операций:

1) Если m > min(r_1,r₂). то m разбивается на части, каждая из кото­рых меньше меньшего из чисел r₁ и r₂ ;

2) Если r₁ < r₂ то сообщение m сначала шифруется ключом α₁ (m₁≡m^α1)(mod r₁)), а затем ключом а₂ (m₂≡ )(mod r₂))? если же r₁ > r₂, то сообщение m сначала шифруется ключом а₂ (m₁≡ ) (mod r₂))  а затем ключом (mod r₁));

 3)Шифрованное сообщение m₂отправляется W ₂ .

W2для дешифровки сообщения m₂ должен знать, кто его отправил, поэтому к m₂ должна быть добавлена электронная подпись, указываю­щая на W ₁ . Если r₁ < r₂ то для расшифровки m₂ сначала применяется ключ α₂ ,а затем а₁ ,если же r₁ > r₂ то для расшифровки т₂ сна­чала применяется ключ а₁ ,а затем α₂ . Рассмотрим случай r₁ < r₂ :  (mod r₂ )и (mod r₂) по теореме Эйлера-Ферма.

Пример. Пусть W ₁ выбрал и вычислил следующие числа р₁₁= 7, р₁₂ =13, r₁ = р₁₁ р₁₂ =91, φ(91) = 72, а₁ = 5, α₁ = 29, а W ₂  следу­ющие р₂₁ = 11, р ₂₂ ⁼ 23, r₂ =253, φ(253) = 220, а₂ = 31, α₂ = 71. После занесения записей о W ₁ и W ₂ в открытую книгу паролей. W ₁ решает послать сообщение ш = 41 для W ₂. Т.к. /'2 > i ' i - го сообщение сначала шифруется ключом п\. а затем ключом oj: '»1 = 4Г¹ = () (mod 91). ш 2 = И'¹ = 04 (mod 2o3j. Сообщение т 2 отправляется U^ri. Получив /«2 = 94. W ₂. зная, что оно пришло от W ₁- дешифрует его сначала клю­чом <\< i . а затем ключом ai: 94'^il (mod 253) = fi. (i²ⁿ (mod Dl'i =41.

Если подписать сообщение открытым образом, например, именем отправителя, то такая "подпись" будет ничем не защищена от поддел­ки. Защита электронной подписи обычно реализуется с использованием таких же методов, что в криптосистеме с открытым ключом,

Электронная подпись генерируется отправителем по передаваемо­му сообщению и секретному ключу. Получатель сообщения может проверить его аутентичность по прилагаемой к нему электронной подписи и открытому ключу отправителя.

Стандартные системы электронной подписи считаются настолько надежными, что электронная подпись юридически приравнена к руко­писной. Электронная подпись часто используется с открытыми, незашифрованными электронными документами.

 

Стандарт шифрования данных.

В 1977 году в США был предложен стандарт для шифрования дан­ных DES (Data Encryption Standard), разработанный в IBM. В 1980 он был одобрен ведущей мировой организацией по стандартам AN­SI. В настоящее время алгоритм DES широко используется для защиты коммерческой информации.

DES это классическая криптосистема с открытым способом шифровки и дешифровки, секретность которой обеспечивается исклю­чительно ключом. Основные достоинства DES:

• используется только один ключ фиксированной длины 55 бит (в системах с открытым ключом длина ключа должна быть более 300 бит):

• зашифровав сообщение с помощью одной программы, для расшиф­ровки можно использовать другую:

• относительная простота алгоритма обеспечивает высокую ско­рость работы (как минимум, на порядок выше скорости работы алгоритма для криптосистемы с открытым ключом);

• достаточно высокая стойкость алгоритма (стойкость конкретного зашифрованного сообщения зависит от выбора ключа). Главный недостаток DES связан с его классической организацией, т.е. с необходимостью обеспечивать сверхнадежный канал для переда­чи ключей.

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

Примером программы, реализующей алгоритм DES. является про­грамма DISKREET из пакета Norton Utilities.

 

---

Дата добавления: 2022-01-22; просмотров: 34; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!