33634

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman)

Доклад

Информатика, кибернетика и программирование

Алгоритм RS состоит из следующих пунктов: Выбрать простые числа p и q заданного размера например 512 битов каждое. Вычислить n = p q Вычисляется значение функции Эйлера от числа n: m = p 1 q 1 Выбрать число d взаимно простое с m Два целых числа называются взаимно простыми если они не имеют никаких общих делителей кроме 1. Выбрать число e так чтобы e d = 1 mod m Числа e и d являются ключами. Шифруемые данные необходимо разбить на блоки числа от 0 до n 1.

Русский

2013-09-06

92.5 KB

10 чел.

53. RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) - криптографический алгоритм с открытым ключом. RSA стал первым алгоритмом такого типа, пригодным и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений.

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (public key), так и секретным ключом (secret key). Каждый ключ - это часть информации. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и секретный ключ самостоятельно. Секретный ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и секретный ключи каждого участника обмена сообщениями образуют «согласованную пару» в том смысле, что они являются взаимно обратными.

Алгоритм RSA состоит из следующих пунктов:

  1.   Выбрать простые числа p и q заданного размера (например, 512 битов каждое).

В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов k, на алгоритм генерации которого накладываются определенные ограничения.

  1.   Вычислить n = p * q 
  2.   Вычисляется значение функции Эйлера от числа n:

 m = (p - 1) * (q - 1)

  1.   Выбрать число d взаимно простое с m 

Два целых числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1. Примеры: 14 и 25 взаимно просты, а 15 и 25 не взаимно просты (у них имеется общий делитель 5).

  1.   Выбрать число e так, чтобы e * d = 1 (mod m)

Числа e и d являются ключами. Шифруемые данные необходимо разбить на блоки - числа от 0 до n - 1.

Шифрование и дешифровка данных производятся следующим образом:

Шифрование: P(M) = Me mod n

Дешифровка: S(C) = Cd mod n

Следует также отметить, что ключи e и d равноправны, т.е. сообщение можно шифровать как ключом e, так и ключом d, при этом расшифровка должна быть произведена с помощью другого ключа.

Схема шифрования и дешифрования RSA представлена на рис.4. Предположим, сторона B хочет послать стороне А сообщение М. Сообщением являются целые числа от 0 до n-1.



Рис.4 – Схема шифрования/дешифрования RSA

Размер ключа в алгоритме RSA связан с размером модуля n. Два числа p  и q,  произведением  которых  является  модуль,  должны  иметь  приблизительно одинаковую  длину,  поскольку  в  этом  случае  найти  сомножители  (факторы) сложнее, чем в случае, когда длина чисел значительно  различается.  Например, если предполагается использовать 768-битный модуль, то каждое  число  должно иметь длину приблизительно 384 бита. Обратите внимание, что если  два  числа чрезвычайно близки  друг  к  другу  или  их  разность  близка  к  некоторому предопределенному значению, то возникает потенциальная угроза  безопасности, однако  такая  вероятность  –  близость  двух  случайно  выбранных  чисел  – незначительна.

Оптимальный  размер  модуля  определяется  требованиями   безопасности: модуль большего размера обеспечивает большую безопасность,  но  и  замедляет работу  алгоритма RSA. Длина модуля выбирается в  первую  очередь  на  основе значимости защищаемых данных и необходимой стойкости защищенных данных и  во вторую очередь – на основе оценки возможных угроз.

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера n = p * q  в 1024 бита. В Более подробную информацию о данном алгоритме шифрования и конкретные примеры можно получить из справки, а также из источников, указанных в литературе.

Данный алгоритм обладает высокой криптостойкость и низкой помехоутойчивостью, также скорость дешифровании файла ниже скорости шифрования файла.


 

А также другие работы, которые могут Вас заинтересовать

69319. Аналіз похибок розв’язування СЛАР 336 KB
  Аналіз похибок через число обумовленості матриці Нехай обчислене значення x помилка розв’язку ε = b відхил або нев’язка розв’язку системи рівнянь x = b. Нев’язка може бути малим а помилка розв’язку великою. 52 cond = 1 число обумовленості матриці що дорівнює максимально...
69320. Ітераційні методи розв’язування СЛАР 307.5 KB
  Метод простої ітерації умови збіжності Для розріджених великих систем рівнянь досить добрі результати можна отримати як це було показано в попередньому параграфі застосуванням методу визначальних величин.
69321. Властивості власних значень і власних векторів матриці 115 KB
  Метод характеристичного рівняння матриці Коли на деякий вектор х діє матриця А то в загальному випадку отримується новий вектор у = Ах який відрізняється від вектора х як своїм модулем розміром так і орієнтацією в багатовимірному просторі.
69322. Степеневий метод обчислення власних значень 149.5 KB
  Для оцінки окремих власних значень матриці можна використовувати теорему Гершгоріна яка стверджує що матриця А порядку nxn має n власних значень кожне з яких лежить в межах круга: 4. Якщо λ власне значення матриці то завжди можна вибрати відповідний йому...
69323. Власні значення симетричних матриць 174 KB
  Остаточно маємо формули алгоритму Ланцош довільний нормований вектор; При цьому вважається, що Якщо то було випадково взято ортогональним одному з власних векторів. Тоді Т розпадається на дві тридіагональної матриці; характеристичний поліном – на добуток двох поліномів...
69324. LR-та QR-алгоритми обчислення власних значень 325.5 KB
  Цей метод базується на перетворенні подібності матриці А таким чином щоб власні значення матриці отриманої внаслідок перетворення знаходилися простіше чим для початкової матриці. Найбільш просто обчислювати власні значення трикутної матриці для якої...
69325. Інтерполяція алгебраїчними поліномами. Інтерполяційні поліноми Лагранжа та Ньютона 213 KB
  Таку заміну називають наближенням функції fx. Тоді при вирішенні задачі замість функції fx оперують з функцією φx а задача побудови функції φx називається задачею наближення. Такий спосіб наближення базується на теоремі Вейерштраса про наближення неперервної функції...
69326. Кусково-поліноміальна інтерполяція. Інтерполяція сплайнами 507 KB
  Поліном 3-го ступеня будемо називати кубічним сплайном Sx що відповідає вихідної функції fx і заданий на сітці впорядкованих вузлів =x0 x1 xn=b якщо задовольняютьсянаступні умови: а. Будемо виводити формулу для рівновіддалених вузлів коли: xi xi 1 = h Знайдемо значення функції...
69327. Збіжність і точність процесу інтерполяції. Середньоквадратичне наближення 297 KB
  Похибки інтерполяційної формули Лагранжа Різницю між функцією fx і її інтерполяційним наближенням Lnx називають залишковим членом інтерполяційноїформули або похибкою інтерполяції. 8 зрозуміло що у вузлах інтерполяції ця похибка дорівнює нулю тому похибку...