Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. F(x) Функция
  2. II. Функция "холокоста в мире после 1945 г
  3. V. Если жизнь излишне деловая,функция слабеет половая.
  4. а. Морфология и функция BBB
  5. Активационная функция.
  6. Алгоритм

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<nàf(k*a, a, e-1, n); 2

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

 

Номер итерации Функция Правило
f( 1, 2, 7, 33)
f( 2, 2, 6, 33)
f( 4, 2, 5, 33)
f( 8, 2, 4, 33)
f(16, 2, 3, 33)
f(32, 2, 2, 33)
f(64, 2, 1, 33)
f(31, 2, 1, 33)
f(62, 2, 0, 33)
62 mod 33=29 Результат

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

akmod n =5596 mod 1234=1013

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

2.143 AlgorithmRepeated 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 b1. 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
ki
2i            
A
b

Пояснения:

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:


Дата добавления: 2015-07-07; просмотров: 437 | Нарушение авторских прав


Читайте в этой же книге: ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ ПОСТАНОВЛЕНИЕот 16 апреля 2012 г. N 313 | Порядок классификации | Секретные системы. Основы информационной теории Шеннона. | Сеть Файстеля | Специальные криптографические протоколы | Разновидности атак на протоколы | Неосознанная передача информации | Депонирование ключей | Алгоритмы шифрования | Режимы работы алгоритма DES, 3DES. |
<== предыдущая страница | следующая страница ==>
Подмена шифра в режиме OFB| Свойства HASH - функций

mybiblioteka.su - 2015-2021 год. (0.009 сек.)