Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции_20115_01.docx
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆

6.2.4 Сравнение некоторых симметричных алгоритмов шифрования

DES

3DES

ГОСТ

AES

Размер ключа бит

64

128

256

128,192,256

Размер блока бит

64

64

64

128

Стандарт AES (Advanced Encryption Standard) является стандартом шифрования США, принятым в 2000-ом году. Он специфицирует алгоритм Rijndael http://www.nist.gov/CryptoToolkit (смотри также http://csrc.nist.gov/ publications/fips/fips197/fips-197.pdf). Этот алгоритм представляет собой симметричный блочный шифр, который работает с блоками данных длиной 128 бит и использует ключи длиной 128, 192 и 256 бит (версии AES-28; AES-192 и AES-256). Сам алгоритм может работать и с другими длинами блоков данных и ключей, но эта возможность в стандарт не вошла. При использовании 128-битного ключа для взлома шифрования по заявлению правительства США потребуется 149 триллионов лет.

6.3 Ассиметричныеалгоритмы

Ehrsametal.Jun. 08 1976 DES

Hellman-Diffie-MerkleApr. 29 1980 Diffie-Hellmanagreement

Hellman-Merkle Aug. 19 1980 public-key systems

Merkle Jan. 05 1982 tree authentication

Rivest-Shamir-Adleman Sep. 20 1983 RSA system

6.3.1 Алгоритм rsa. Генерация ключей и функция шифрования

1. Выбираем два очень больших простых числа p и q.

2. Определяем M=(p-1)*(q-1) и N=p*q.

3. Определяем D взаимопростое с M. (DM). (Расширенный алгоритм Евклида). Заметим, что любое простое число Dявляется и взаимопростым с M, если оно не является делителем M.

4. Определяем E такое, что (E*D)modM=1

5. Назовем (D, N)-открытым ключом, (E,N)-закрытым ключом.

Процедура шифрования/расшифрования выполняется по формуле, где ti и si блоки открытого и шифртекста соответственно.

Пример. Выполним последовательно п. 1-5 генерации ключей.

1. Выберем p=3, q=11.

2. Определим M=20, N=33.

3. Определим D=7.

4. Определим E=3

5. (7,33)-открытый ключ, (3,33)-закрытый ключ.

Пусть открытый текст представлен последовательностью цифр T= 1, 2, 3. Тогда процесс шифрования выглядит следующим образом:

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 USD. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

Основная операция этого алгоритма - возведение в степень по модулю, для реализации которой предлагается рекурсивный алгоритм, построенный по следующему правилу: (a+b) mod c=((a mod c)+(b mod c))mod c

ae mod n==f(a, e, n),

f(a, e, n)==f(k, a, e, n), гдеk=1.

e=0k mod n, exit; 1

k<nf(k*a, a, e-1, n); 2

f(k-n, a, e, n) 3

Номер итерации

Функция

Правило

1

f( 1, 2, 7, 33)

2

2

f( 2, 2, 6, 33)

2

3

f( 4, 2, 5, 33)

2

4

f( 8, 2, 4, 33)

2

5

f(16, 2, 3, 33)

2

6

f(32, 2, 2, 33)

2

7

f(64, 2, 1, 33)

3

8

f(31, 2, 1, 33)

2

9

f(62, 2, 0, 33)

1

10

62 mod 33=29

Результат

Примердругого метода возведения в степень по модулю [Menezes p.71, 72]

akmod n =5596 mod 1234=1013

, k=4+16+64+512=596.

2.143 Algorithm Repeated square-and-multiply algorithm for exponentiation in Zn

INPUT: a  Zn, and integer 0  k < n whose binary representation is

OUTPUT: ak mod n.

1. Set b1. If k = 0 then return(b).

2. Set Aa.

3. If k0 = 1 then set ba.

4. For i from 1 to t do the following:

4.1 Set AA2 mod n.

4.2 If ki = 1 then set bA*b mod n.

5. Return(b).

i

0

1

2

3

4

5

6

7

8

9

ki

0

0

1

0

1

0

1

0

0

1

2i

4

16

64

512

A

5

25

625

681

1011

369

421

779

947

925

b

1

1

625

625

67

67

1059

1059

1059

1013

Пояснения:

k9=1 тогда 1013=10592 mod1234

k8=0тогда 1059=1059

925=9472mod 1234

Дляпоискапростыхчиселиспользуетсяалгоритмназываемый «РешетоЭратосфена». Пример алгоритма показан на рисунке ниже.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 234 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 24

1 2 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Таким образом, в данном примере после трех шагов алгоритма мы получили после последовательность простых чисел: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23.

Пример[Menezes p.287]

8.4 Example (RSA encryption with artificially small parameters)

Key generation. Entity A chooses the primes p = 2357, q = 2551, and computes n =pq =6012707 and M= (p−1)(q−1) = 6007800. A chooses e =3674911and, using theextended Euclidean algorithm, finds d= 422191 such that ed == 1 (mod M). A’s public key is the pair (n=6012707; e=3674911), while A’s private key is d = 422191.

Encryption. To encrypt a message m=5234673, B uses an algorithm for modular exponentiation (e.g., Algorithm 2.143) to compute c = me mod n=52346733674911 mod 6012707 = 3650502; and sends this to A.

Decryption. To decrypt c, A computescd mod n = 3650502422191 mod 6012707=5234673: