Факультет ИСиТ Среда, 20.11.2019, 04:52
Приветствую Вас Гость | RSS
[ Персональный раздел · Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: lamama  
Факультет ИСиТ СыктГУ - Форум » Компьютеры / Интернет / Информационные системы и технологии » Информационная безопасность и криптология » Асимметричный алгоритм шифрования RSA (Информационная тема, но приветствуются вопросы/дополнения)
Асимметричный алгоритм шифрования RSA
Expert Дата: Четверг, 01.05.2008, 10:40 | Сообщение # 1
Главный
Группа: Администраторы
Сообщений: 6113
Награды: 1
Статус: Offline
В этой теме я буду создавать информационные сообщения по известному асимметричному криптоалгоритму RSA. Надеюсь, студентам специальности "комплексная защита объектов информатизации" и, может быть, другим посетителям, это будет интересно и полезно.

Начнем.
--
Краткая история появления.

Несмотря на достаточно большое число различных систем с открытыми ключами, одной из наиболее популярных остается криптосистема RSA, созданная в 1977 г. и названная в честь ее создателей Рона Ривеста, Ади Шамиpа и Леонарда Эйдельмана. Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, а разложение на множители произведения двух таких чисел – сложно.

В статье этих авторов, вышедшей в 1978 г., премия в сто долларов была назначена тому, кто первым расшифрует сообщение 68613754622061477140922254355882905759991125743198746951209308162982251457083569314766288398962801339199055182994515781515.

Метод шифрования был известен, единственное, что требовалось – разложить на два сомножителя 129-значное число, приведенное в этой статье.

Это было сделано только в 1994 г.

Задача была решена с помощью 600 человек и потребовала 220 дней и 1600 компьютеров, связанных через Internet.


Блог декана

Уведомление для прессы и всех пользователей сети интернет: администрация форума может не заметить вовремя нецензурных слов и других, возможно, оскорбительных выражений/картинок/прочих материалов. Если вы заметили косвенный либо прямой факт оскорбления кого бы то ни было, пожалуйста, сообщите об этом администратору форума для принятия решения об удалении/модерировании соответствующего сообщения. Полный текст уведомления см. здесь.
 
Expert Дата: Четверг, 01.05.2008, 10:51 | Сообщение # 2
Главный
Группа: Администраторы
Сообщений: 6113
Награды: 1
Статус: Offline
Теоретические основы алгоритма RSA

Рассмотрим математические результаты, которые положены в основу этого алгоритма.

Определение 1. Сравнением целых чисел a и b будем называть соотношение между ними вида a = b + mk, означающее, что их разность (a – b) делится на заданное положительное число m, называемое модулем сравнения. При этом а называется вычетом числа b по модулю m.

Определение 2. Говорят, что два целых числа a и b сравнимы между собой и обозначают этот факт через a = b (mod m), если a и b имеют одинаковые остатки при делении на m.

Приведем некоторые очевидные свойства сравнений.

Пусть a = b (mod m) и с = d (mod m). Тогда:

1) a (+-) c = b (+-) d (mod m),
2) a*c (+-) b*d (mod m).

Легко также проверить, что операция сравнения по модулю m является эквивалентностью (выполняются свойства рефлексивности, транзитивности и симметричности), и, следовательно, можно говорить о разбиении множества целых чисел Z на непересекающиеся классы эквивалентности.

Теорема 1. (Малая теорема Ферма). Если p – простое число, то (x в степени (p – 1)) = 1 (mod p) для любого х, простого относи-тельно p, и (x в степени p) = х (mod p) для любого х.

Определение 3. Функцией Эйлеpа Ф(n) называется число положительных целых, меньших n и простых относительно числа n.

Теорема 2. Если n = pq, (p и q – отличные друг от друга простые числа), то Ф(n) = (p – 1)(q – 1).

Теорема 3. Если n = pq, (p и q – отличные друг от друга простые числа) и х – простое относительно p и q, то
(x в степени Ф(n)) = 1 (mod n).

Следствия:

1. Если n = pq, (p и q – отличные друг от друга простые числа) и е - пpостое число относительно Ф(n), то отображение Е(e,n): x -> (x в степени e) (mod n) является взаимно однозначным на алгебраическом кольце вычетов Z(n).

2. Если е – пpостое число относительно Ф(n), то существует целое число d, такое, что e*d = 1 (mod Ф(n)).

Пусть n = pq, где p и q – различные простые числа. Если e и d удовлетворяют уравнению (см. следствие 2), то отображения Е(e,n) и Е(d,n) являются инверсиями на кольце Zn.

Как Е(e,n), так и Е(d,n) легко рассчитываются, когда известны e, d, p, q.

Если известны e и n, но p и q неизвестны, то Е(e,n) представляет собой однонаправленную функцию; нахождение Е(d,n) по заданному n равносильно разложению n на простые сомножители.

Если p и q – достаточно большие простые числа, то разложение n – достаточно сложная вычислительная операция.

Это и заложено в основу системы шифрования RSA.

Пользователь i выбирает пару различных простых p(i) и q(i) и рассчитывает пару целых (e(i), d(i)), которые являются простыми относительно Ф(n(i)), где n(i) = p(i)*q(i). Справочная таблица содержит публичные ключи {(e(i), n(i))}.

Итак, в реальных системах RSA реализуется следующим образом:
1.Каждый пользователь выбирает два больших простых числа p и q, и в соответствии с описанным выше алгоритмом вы-бирает два простых числа e и d; как результат умножения первых двух чисел устанавливается n. После этого {e, n} образует открытый ключ, а {d, n} – секретный (хотя можно взять и наоборот).
2.Открытый ключ публикуется и доступен каждому, кто желает послать владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. После шифрования, сообщение невозможно дешифровать с помощью открытого ключа. Владелец же секретного ключа без труда может pасшифpовать принятое сообщение.

P/S/ Надеюсь, математические формулы понятны wink


Блог декана

Уведомление для прессы и всех пользователей сети интернет: администрация форума может не заметить вовремя нецензурных слов и других, возможно, оскорбительных выражений/картинок/прочих материалов. Если вы заметили косвенный либо прямой факт оскорбления кого бы то ни было, пожалуйста, сообщите об этом администратору форума для принятия решения об удалении/модерировании соответствующего сообщения. Полный текст уведомления см. здесь.
 
Expert Дата: Четверг, 01.05.2008, 10:58 | Сообщение # 3
Главный
Группа: Администраторы
Сообщений: 6113
Награды: 1
Статус: Offline
Практический пример работы RSA

Рассмотрим небольшой пpимеp, иллюстрирующий применение алгоритма RSA.
Пусть требуется зашифровать сообщение “САВ”.
Для простоты будем использовать маленькие числа (на практике применяются гораздо большие). Пошагово проследим процессы шифрования и дешифрования.

1.Выберем p = 3 и q = 11.
2.Определим n = 3 * 11 = 33.
3.Найдем (p – 1)(q – 1) = 20. Следовательно, в качестве e можно взять число, взаимно простое с 20, напpимеp, e = 3.
4.Выберем число d. В качестве такого числа может быть взято любое число, для которого выполняется соотношение
(d * 3) = 1(mod 20), напpимеp 7.
5.Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А -> 1, В-> 2, С-> 3. Тогда исходное открытое сообщение принимает вид M = (3,1,2). Зашифруем сообщение с помощью ключа {7, 33}:

s1 = (3 в степени 7) (mod 33) = 2187 (mod 33) = 9,
s2 = (1 в степени 7) (mod 33) = 1 (mod 33) = 1,
s3 = (2 в степени 7) (mod 33) = 128 (mod 33) = 29.

Зашифрованное сообщение после этого примет вид S = (9, 1, 29).

6. Расшифруем полученное зашифрованное сообщение (9, 1, 29) на основе секретного ключа {3, 33}:

m1 = (9 в степени 3) (mod 33) = 729 (mod 33) = 3,
m2= (1 в степени 3) (mod 33) = 1 (mod 33) = 1,
m3 = (29 в степени 3) (mod 33) = 24389 (mod 33) = 2.

Как можем видеть, дешифрование шифртекста S = (9, 1, 29) привело к исходному открытому тексту M = (3, 1, 2).


Блог декана

Уведомление для прессы и всех пользователей сети интернет: администрация форума может не заметить вовремя нецензурных слов и других, возможно, оскорбительных выражений/картинок/прочих материалов. Если вы заметили косвенный либо прямой факт оскорбления кого бы то ни было, пожалуйста, сообщите об этом администратору форума для принятия решения об удалении/модерировании соответствующего сообщения. Полный текст уведомления см. здесь.
 
eXceed Дата: Понедельник, 05.05.2008, 15:28 | Сообщение # 4
Профессор
Группа: СуперАктив
Сообщений: 5246
Награды: 0
Статус: Offline
Действительно интересная статья. Спасибо. Но хотелось бы сказать пару слов своих.
На сегодняшний день алгоритм RSA является достаточно стойким. Но только на сегодняшний день. Пройдет еще 5 - 6 лет и проблема факторизации больших чисел будет решена! Надеюсь Вы знакомы с алгоритмом квантовой факторизации Питера Шора. Алгоритм позволяет производить быстрое разложение на сомножители простые числа. На данный момент алгоритм жизнеспособен лишь только на квантовых компьютерах, либо компьютерных сетях имитирующих работу квантового компьютера.
Более подробно можно прочитать здесь


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.
 
vitalyu Дата: Понедельник, 05.05.2008, 17:52 | Сообщение # 5
Преподаватель
Группа: СуперАктив
Сообщений: 852
Награды: 0
Статус: Offline
Ну как же без того. Прогресс не стоит на месте .. Техника развивается, алгоритмы совершенствуются ..
Один из принципов Керкхоффса гласит, что любой шифр можно подобрать путем перебора .. Главное знать, что искать wink

По тому же Керкхоффсу, криптоалгоритм должен удовлетворять следующим требованиям (выдержка из полного текста):
1) Должен обеспечивать достаточную стойкость ко взлому. Несмотря на то, что одиночное шифрованное сообщение может быть в принципе невзламываемым, часто бывает необходимо переслать сотни сообщений, зашифрованных в одной и той же системе. И хотя одиночное сообщение может быть трудно или невозможно расшифровать, большое число одинаково зашифрованных сообщений взломать куда проще. «Достаточная» стойкость ко взлому означает также, что разработчику шифра необходимо учитывать фактор времени: на взломку шифра должно требоваться время, достаточное для того, чтобы сообщения успевали потерять ценность для криптоаналитика. Обеспечение абсолютной стойкости шифра редко необходимо, и даже если оно возможно, обычно требует неоправданных затрат.
2) шифр должен быть прост в использовании
3) стойкость шифра ко взлому должна полностью зависеть от обеспечения секретности ключа, а не алгоритма

3 момента - залог успеза алгоритма .. Оно, в принипе, и понятно smile

-----------
Кстати, существуют же и невзламываемые шифры. Один из таких - шифр Вернама
Там на примере перфокарт со случайными дырками .. Анализу не поддается, потому как расстановка случайна wink
Почему не используется? Потому что процесс создания случайного ключа очень непростой и занимает кучу процессорного времени .. Возможно, в скором времени мы и сможем таковым шифровать, но пока .. ждем и играем в игрушки ..


Бог сумел сотворить мир всего за 6 дней только потому, что ему не нужно было решать проблемы совместимости с предыдущей версией.
...
Автомат Калашникова - это средство для превращения стэка в очередь...


Сообщение отредактировал vitalyu - Понедельник, 05.05.2008, 17:59
 
Expert Дата: Понедельник, 05.05.2008, 22:45 | Сообщение # 6
Главный
Группа: Администраторы
Сообщений: 6113
Награды: 1
Статус: Offline
Quote (eXceed)
На сегодняшний день алгоритм RSA является достаточно стойким. Но только на сегодняшний день.

Согласен полностью.

Quote (vitalyu)
По тому же Керкхоффсу

Во-первых, vitalyu и eXceed, спасибо за поддержание темы.

Во-вторых, vitalyu, я немного уточну указанное правило Керкхоффа (просто в дополнение к сказанному; это действительно интересно может быть для новичков, хотя и не по теме).

Правило Керкхоффа

Голландский криптограф Керкхофф (1835-1903) впервые сформулировал фундаментальное правило стойкости криптосистемы (шифра) – стойкость криптосистемы (шифра) должна определяться только секретностью ключа.

Иными словами, правило Керкхоффа состоит в том, что весь алгоритм шифрования, кроме значения секретного ключа, известен криптоаналитику. Это обусловлено тем, что криптосистема обычно рассматривается как открытая система.
Такой подход отражает очень важный принцип технологии защиты информации: защищенность системы не должна зависеть от секретности чего-либо такого, что невозможно быстро изменить в случае утечки секретной информации.
Предполагается, что все долговременные элементы системы известны криптоаналитику.

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

--
Здесь создал еще одну, преимущественно информационную, тему по видам криптосистем. Подключайтесь!


Блог декана

Уведомление для прессы и всех пользователей сети интернет: администрация форума может не заметить вовремя нецензурных слов и других, возможно, оскорбительных выражений/картинок/прочих материалов. Если вы заметили косвенный либо прямой факт оскорбления кого бы то ни было, пожалуйста, сообщите об этом администратору форума для принятия решения об удалении/модерировании соответствующего сообщения. Полный текст уведомления см. здесь.
 
BoSSurman Дата: Понедельник, 05.05.2008, 23:58 | Сообщение # 7
Корифей
Группа: Модераторы
Сообщений: 674
Награды: 0
Статус: Offline
Применение RSA с длиной ключа более 1024 бит уже дает приемлемый уровень защиты. Зачастую даже гарантия конфиденциальности информации в течение хотя бы 1 месяца является достаточной. Поэтому даже с развитием техники использование алгоритма не потеряет актуальность до тех пор, пока его нельзя будет расфишровывать на лету wink

P.S. С появлением квантовых компьютеров можно будет использовать квантовую криптографию =)

P.P.S. Такая заинтересованность в теме заставляет задуматься либо о частоте посещения студентами пар по криптографии wink либо.. о подаче материала на самих лекциях.


:-P

Сообщение отредактировал BoSSurman - Вторник, 06.05.2008, 23:47
 
vitalyu Дата: Вторник, 06.05.2008, 01:01 | Сообщение # 8
Преподаватель
Группа: СуперАктив
Сообщений: 852
Награды: 0
Статус: Offline
Quote (Expert)
Правило Керкхоффа

Спасибо за нормальное пояснение. Описано отлично и с итогом smile

..

Quote (BoSSurman)
P.P.S. Такая заинтересованность в тебе заставляет задуматься либо о частоте посещения студентами пар по криптографиилибо.. о подаче материала на самих лекциях.

Если со второй половиной сообщения понятно, то первая не ясно куда направлена wacko Требуется декодирование дампа твоего мозга ..

А на лекции ходим. Цитирую Саббитова: "В государственной информационной безопасности все что теоретически возможно, считается возможным!".

Quote (BoSSurman)
Применение RSA с длиной ключа более 1024 бит уже дает приемлемый уровень защиты.

Приемлемый, не значит абсолютный. Учись, студент wink

З.Ы. Я тебя уже подкалываю, в ответ на твои уколы wink Да, у нас Берсенев не ведет, но голова у нас есть и учиться хочет. ИМХО, здесь я узнаю куда больше, чем на лекциях в универе! Спасибо еще раз за форум!


Бог сумел сотворить мир всего за 6 дней только потому, что ему не нужно было решать проблемы совместимости с предыдущей версией.
...
Автомат Калашникова - это средство для превращения стэка в очередь...


Сообщение отредактировал vitalyu - Вторник, 06.05.2008, 01:27
 
eXceed Дата: Вторник, 06.05.2008, 01:28 | Сообщение # 9
Профессор
Группа: СуперАктив
Сообщений: 5246
Награды: 0
Статус: Offline
BoSSurman
Видимо ты так хорошо учил криптографию. Квантовая криптография ничем не отличается по сути от классической. Математика в квантовом компьютере точно такая же как и на бумаге wink Мощности квантовых компьютеров будут рости с огромными темпами. В ближайшем будущем множество алгоритмов будут взламываться если не на лету, то за приемлимое время. Даже RSA с 4096 битным ключем. Для алгоритма Питера Шора длина ключа особой роли не играет(в случае реализации на квантовом компьютере).
Возник вопрос.
Сколько времени занимает генерация пары закрытый/открытый ключ длинной от 4096 бит? И как влияет длинна ключа на скорость шифрования/расшифровки?


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.

Сообщение отредактировал eXceed - Вторник, 06.05.2008, 01:37
 
vitalyu Дата: Вторник, 06.05.2008, 01:36 | Сообщение # 10
Преподаватель
Группа: СуперАктив
Сообщений: 852
Награды: 0
Статус: Offline
АА! Пашко тут biggrin +1 за скорость )

Выдержка из Вики по квантовым компьютерам:

Quote
Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае, система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2n базовых состояний одновременно.

Т.е. принципы те же, что и для классических ЭВМ ..


Бог сумел сотворить мир всего за 6 дней только потому, что ему не нужно было решать проблемы совместимости с предыдущей версией.
...
Автомат Калашникова - это средство для превращения стэка в очередь...


Сообщение отредактировал vitalyu - Вторник, 06.05.2008, 01:42
 
Expert Дата: Вторник, 06.05.2008, 06:36 | Сообщение # 11
Главный
Группа: Администраторы
Сообщений: 6113
Награды: 1
Статус: Offline
Quote (vitalyu)
"В государственной информационной безопасности все что теоретически возможно, считается возможным!"

+1

Quote (BoSSurman)
P.P.S. Такая заинтересованность в тебе заставляет задуматься либо о частоте посещения студентами пар по криптографиилибо.. о подаче материала на самих лекциях.

тоже не понял biggrin


Блог декана

Уведомление для прессы и всех пользователей сети интернет: администрация форума может не заметить вовремя нецензурных слов и других, возможно, оскорбительных выражений/картинок/прочих материалов. Если вы заметили косвенный либо прямой факт оскорбления кого бы то ни было, пожалуйста, сообщите об этом администратору форума для принятия решения об удалении/модерировании соответствующего сообщения. Полный текст уведомления см. здесь.
 
BoSSurman Дата: Вторник, 06.05.2008, 20:23 | Сообщение # 12
Корифей
Группа: Модераторы
Сообщений: 674
Награды: 0
Статус: Offline
Quote (vitalyu)
Приемлемый, не значит абсолютный. Учись, студент

Хе-хе, идеалисты wink

Абсолютной защиты НЕ БЫВАЕТ. Собственник информации определяет для себя приемлемый уровень рисков. Такой, при котором ущерб от нарушения доступности/целостности/конфиденциальности информации будет считаться допустимым и соответсвовать принимаемым мерам по защите. К тому же сумма средств, затраченных на обеспечение информационной безопасности НЕ ДОЛЖНА превышать потенциальный ущерб, который может понести собственник, иначе все превращается в фейк))))) Использование любых средств и методов защиты инфомации направлено лишь на снижение степени риска до необходимого уровня.

Quote (eXceed)
Видимо ты так хорошо учил криптографию. Квантовая криптография ничем не отличается по сути от классической.

Да ну?)
Ваша любимая вика:
Quote

Квантовая криптография — метод защиты коммуникаций, основанный на определенных явлениях квантовой физики. В отличие от традиционной криптографии, которая использует математические методы, чтобы обеспечить секретность информации, квантовая криптография сосредоточена на физике информации. Процесс отправки и приема информации всегда выполняется физическими средствами, например при помощи электронов в электрическом токе, или фотонов в линиях волоконно-оптической связи. А подслушивание может рассматриваться, как измерение физических объектов — в нашем случае, переносчиков информации.

Технология квантовой криптографии опирается на принципиальную неопределенность поведения квантовой системы — невозможно одновременно получить координаты и импульс частицы, невозможно измерить один параметр фотона, не исказив другой. Это фундаментальное свойство природы в физике известно как принцип неопределенности Гейзенберга, сформулированный в 1927 г.

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

Сорри за оффтоп, а теперь ближе к теме:

Quote (eXceed)
Сколько времени занимает генерация пары закрытый/открытый ключ длинной от 4096 бит? И как влияет длинна ключа на скорость шифрования/расшифровки?

Если мне не изменяет память, то 1024 генерится около минуты, 4096 - минут 20-30) Все зависит от мощности компа и реализации алгоритма. Чем длиннее ключ, тем дольше реализуется шафрование/расшифровка.

Quote (Expert)
тоже не понял

Quote (vitalyu)
Да, у нас Берсенев не ведет, но голова у нас есть и учиться хочет. ИМХО, здесь я узнаю куда больше, чем на лекциях в универе! Спасибо еще раз за форум!


:-P

Сообщение отредактировал BoSSurman - Вторник, 06.05.2008, 20:24
 
vitalyu Дата: Вторник, 06.05.2008, 23:12 | Сообщение # 13
Преподаватель
Группа: СуперАктив
Сообщений: 852
Награды: 0
Статус: Offline
Quote (BoSSurman)
Абсолютной защиты НЕ БЫВАЕТ. Собственник информации определяет для себя приемлемый уровень рисков. ... Использование любых средств и методов защиты инфомации направлено лишь на снижение степени риска до необходимого уровня.

Об этом говорят на самых первых занятиях по ИБ. Тогда же говорится, что абсолютная защита - это компьютер, отключенный от всех сетей (электрических, ЛВС и т.д.), помещенный в стальной бункер на клубине 100 метров. И при этом не гарантируется полный уровень защиты. Смешно, однако вполне логично и понятно ..

Но все же здесь разговор не только о том, что делается, но и о том, что можно сделать (включая теорию). Выше я писал про шифр Вернама, и это подтверждение абсолютной защиты в узком спектре задач..

Я не знаю, к чему тут споры вообще, по-моему, спорить то не о чем .. 2 позиции, с которых можно подходить к этому вопросу - так и останутся, щас закидаем тут всю ветку доводами, а весы не сдвинутся ..

Та же ситуация и с Квантовыми ЭВМ, и Квантовой криптографией .. Если прочитать от и до по этому вопросу, то видно, что фундамент математики не меняется .. В этом случае в криптоалгоритмах используются расширенная математика и расчет через кубиты (2^N мерные пространства) .. В этом случае у математиков появится еще парочка идей .. но законы математики это не подорвет .. Почитай полностью, там даже с примерами .. Если разобраться - то ничего нетрадиционного в этом нет ..

Аналогично: Как для витой пары категории 5е смогли увеличить скорость передачи до 1Gb/s?? Просто ввели 5 потенциалов ..
А в нашем вопросе ввели несколько состояний .. wink


Бог сумел сотворить мир всего за 6 дней только потому, что ему не нужно было решать проблемы совместимости с предыдущей версией.
...
Автомат Калашникова - это средство для превращения стэка в очередь...


Сообщение отредактировал vitalyu - Вторник, 06.05.2008, 23:15
 
Факультет ИСиТ СыктГУ - Форум » Компьютеры / Интернет / Информационные системы и технологии » Информационная безопасность и криптология » Асимметричный алгоритм шифрования RSA (Информационная тема, но приветствуются вопросы/дополнения)
  • Страница 1 из 1
  • 1
Поиск:



Copyright bda-expert.ru © 2008-2019Хостинг от uCoz