Читайте также: |
|
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 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Подмена шифра в режиме OFB | | | Свойства HASH - функций |