FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Email: Нажмите что бы посмотреть
Общий метод
решета числового поля
р – наименьший множитель числа N
и отсюда найти
С=M 3mod п1п2п3
M 3 < п1п2п3
Т.к.
Почему?
t2= (t1e1 -1)/e2
. . .
(2L/2 )еmod п
С·i -еmod п
≡
j emod n
M= i · j
М = Сk-1
ЦЕПНЫЕ (НЕПРЕРЫВНЫЕ) ДРОБИ
Любое действительное число х можно представить цепной дробью
x = [a0; a1, a2,…]
x0 = x – a0 ;
xi – 1
x = [a0; a1, a2,…]
p–1 = 1;
p0 = a0 ;
q0 = 1
q–1 = 0;
; i = 1,2,…
Пример. Найти подходящие дроби для цепной дроби
Решение.
[0; 2, 1, 10, 3]
a0 a1 a2 a3 a4
p–1 = 1;
p0 = 0 ;
q0 = 1
q–1 = 0;
p1 = 1;
q1 = 2;
p2 = 1;
q2 = 3;
Подходящие дроби:
p3 = 11;
q3 = 32;
p4 = 34;
q4 = 99
Если несократимая дробь удовлетворяет неравенству:
то дробь – одна из подходящих дробей в разложении числа х в цепную дробь.
это классическая аппроксимация с помощью цепных дробей;
число дробей , где , не больше log n
для некоторого k выполнится . Тогда так как НОД (k, d) =1, то p = k, q = d
d < n
п 0,292
M=С dmod п
Секретный ключ – экспонента d
Длина модуля RSA в битах
Время расшифрования (миллисекунды)
Pentium, 2 ГГц
http://security.stackexchange.com/questions/1833/encryption-decryption-time
Нужен алгоритм расшифрования
с минимальным числом операций
Mp≡С dmod p≡С d mod p-1mod p
Mq≡С dmod q≡С d mod q-1mod q
M ≡ Mp mod p
M ≡ Mq mod q
По китайской теореме об остатках
Одно возведение в степень по mod дл. 1024 бит c показателем 1024 бит
t
t
Асимметричные алгоритмы очень медленные
При передаче ключа он может быть перехвачен мошенником
Сk – RSA, Eоткр.(k)
Сm – AES, Ek(m)
Числовая упаковка сообщения