8-900-374-94-44
Когда я учился программировать, меня всегда раздражало решать на практиках неинтересные задачи. Теперь я преподаю, и мне не хочется, чтобы студенты скучали на моих занятиях.
В этой статье я решаю на языке MIT Scheme задачу шифрования и дешифрования методом RSA [1]. По ряду причин, которые рассматриваются в статье, реализация не может использоваться для криптографической защиты информации.
RSA относится к ассиметричным алгоритмам шифрования: если для шифрования используется открытый ключ, то для дешифрования используется закрытый, и наоборот. Первое свойство позволяет кому угодно зашифровать сообщение открытым ключом в адрес владельца закрытого ключа и тем самым обеспечить его конфиденциальность. Второе свойство позволяет владельцу ключа зашифровать хэш сообщения закрытым ключом, чтобы кто угодно мог дешифровать зашифрованный хэш, сравнить его с хэшем сообщения и определить, было ли сообщение модифицровано.
Первый этап генерации ключей — случайный выбор двух достаточно больших простых чисел p и q. Натуральное число x называется простым, если у него есть ровно два различных делителя: 1 и x. Все другие делители числа располагаются на отрезке от 2 до квадратного корня из x, однако достаточно проверять на кратность только простые делители, принадлежащие этому отрезку.
(define (Primes n)
(define (prime? n primes)
(define (iter divisors)
(or (null? divisors)
(let ([divisor (car divisors)])
(or (> (* divisor divisor) n)
(and (< 0 (remainder n (car divisors))) (iter (cdr divisors))))))
)
(iter primes)
)
(define (iter primes i candidate)
(cond
((= i n) primes)
((prime? candidate (reverse primes)) (iter (cons candidate primes) (+ i 1) (+ candidate 1)))
(else (iter primes i (+ candidate 1)))
)
)
(iter '() 0 2)
)
(define primes (Primes 100))
(define p (car primes))
(define q (car (drop 10 primes))) Произведение найденных простых чисел является первым элементом открытого и закрытого ключей.
Приведённый алгоритм позволяет найти за разумное время только первые миллион простых чисел. В реализациях RSA, используемых для защиты информации, используются алгоритмы поиска простых чисел, позволяющие найти простые числа с большим числом разрядов; благодаря тому, что лучший известный алгоритм разложения числа на простые множители работает за время, пропорциональное экспоненте от количества разрядов, считается что восстановить пару простых чисел по рассматриваемому элементу открытого ключа невозможно [2].
(define n (* p q))
Для вычисления вторых элементов открытого и закрытого ключей используется величина fi, равная функции Эйлера [3], вычисленной на n. Функция Эйлера от x равна количеству натуральных чисел, не больших x и взаимно простых с ним. Для n это количество будет равно произведению p-1 и q-1.
(define fi (* (- p 1) (- q 1)))
Вторым элементом открытого ключа выбирается случайное число e в диапазоне от 1 до fi, являющееся взаимно простым с fi.
то есть таким, что наибольшим общим делителем чисел является 1.
(define (CoprimesLess n)
(define (iter accumulator candidate)
(cond
((= 1 candidate) accumulator)
((= 1 (gcd n candidate)) (iter (cons candidate accumulator) (- candidate 1)))
(else (iter accumulator (- candidate 1)))
)
)
(iter '() (- n 1))
)
(define e (car (drop 5 (CoprimesLess fi))))Для поиска наибольшего общего делителя можно использовать алгоритм Евклида [4].
Одним из объектов, изучаемых теорией чисел, является кольцо вычетов [5]. Кольцо вычетов по модулю k — это целые числа от 0 до k-1 и операции сложения и умножения на нём. Сложение в кольце вычетов (a + b mod k) отличается от сложения в группе целых чисел тем, что если результат сложения становится больше k, из него вычитается k, в результате чего этот результат снова оказывается в кольце. Интуитивно, кольцо получается из отрезка соединением его концов.
Как и в группе целых чисел, умножение в кольце вычетов можно задать при помощи сложения, а возведение в степень — при помощи умножения.
Как и в группе целых чисел, получившиеся операции сложения и умножения будут обладать ассоциативностью, то есть:
a + (b + c mod k) mod k = (a + b mod k) + c mod k
a * (b * c mod k) mod k = (a * b mod k) * c mod k
Вторым элементом открытого ключа должно быть число d такое, что его произведение с e в кольце вычетов по модулю n является 1, то есть мультипликативно обратный элемент. Привожу алгоритм поиска такого элемента при помощи расширенного алгоритма Евклида [6].
(define (MultInverseModN a n)
(define (iter a-prev a r-prev r)
(if (>= 1 r) a (let* ([r-next (remainder r-prev r)]
[q (quotient r-prev r)]
[a-next (- a-prev (* q a))])
(iter a a-next r r-next)))
)
(let ([result (iter 0 1 n a)]) (if (< 0 result) result (+ n result)))
)
(define d (MultInverseModN e fi))
При помощи алгоритма RSA можно шифровать сообщения, представленные серией чисел M в диапазоне от 0 до n-1.
Шифрование состоит в возведении M в степень e в кольце вычетов по модулю n, дешифрование — в степень d. Благодаря тому, что умножение является ассоциативным, мы можем возводить в степень x за log(x) операций [7].
(define (PowerModN a b n)
(define (iter accumulator multiplicator power)
(if
(= power 0)
accumulator
(let
((new_accumulator (if (even? power) accumulator (remainder (* accumulator multiplicator) n))))
(iter new_accumulator (* multiplicator multiplicator) (quotient power 2))
)
)
)
(iter 1 a b)
)В моём примере открытый ключ представляет собой пару (250483 31), закрытый — пару (250483 32191). Зашифрованное сообщение 123456 равно 133240.
Автор(ы): Короткова Дарья Алексеевна
Рубрика: Технические науки
Журнал: «Евразийский Научный Журнал №1 2017» (январь, 2017)
Количество просмотров статьи: 6699
Показать PDF версию Схема шифрования RSA и её программная реализация
Короткова Дарья Алексеевна,
студентка Ульяновский государственный университет
E-mail: [email protected]
Аннотация
Информация — это одна из самых ценных вещей в современной жизни. Появление глобальных компьютерных сетей сделало простым получение доступа к информации для людей и для организаций. А так же, доступ к личной информации при её передаче получают злоумышленники.
Чтобы обеспечить безопасность личных данных при передаче, необходимо зашифровывать информацию.
Шифрование — это метод защиты любой информации от неавторизованных лиц, с предоставлением, в это же время, авторизованным пользователям доступа к ней.
В данной статье я рассмотрю метод шифрования RSA и метод дополнительного шифрования OAEP, напишу его программную реализацию и сымитирую атаки на RSA.
Ключевые слова: шифр, C++, безопасность, RSA, OAEP.
RSA— криптографический алгоритм с открытым ключом, разработан учёными Ривестом, Шамиром и Адлеманом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.
Криптографическая система с открытым ключом — система шифрования, при которой открытый ключ передаётся по незащищенному каналу и используется для проверки электронных подписей и для шифрования сообщения.
Для генерации электронной подписи и расшифровки сообщений используется закрытый ключ.
Криптографические системы с открытым ключом используют односторонние функции, обладающие свойствами:
· Если известно x, то вычислить f(x) просто.
· Если известно y=f(x), то для вычисления x нет простого пути.
Алгоритм RSA:
1. Создание открытого и закрытого ключа.
1. Выбирается два простых числа u и v.
2. Вычисляется произведение p=u*v.
3. Вычисляется функция Эйлера φ(p)=(u-1)(v-1)
4. Выбираем открытую экспоненту e (1<e< φ(p))
5. Вычисляем закрытую экспоненту d, где (d*e) mod φ(p) =1
6. Получаем открытый ключ (e, p) и закрытый ключ (d, p).
2. Шифрование и дешифрование.
Посмотрим модель шифрования и дешифрования сообщения на конкретном примере.
Пусть Алиса хочет послать Бобу сообщение h.
У Алисы есть открытый ключ Боба. А Боб владеет своим закрытым ключом.
w=G(h)= he mod p h=Q(w)=wd mod p
Безопасность схемы шифрования RSA:
Я написала программу на языке высокого уровня С++, где каждый символ кодируется на основании таблицы ASCII, и затем осуществляется алгоритм RSA.
Например, берем символ I, по таблице ASCII его код равен 73. Генерация ключей такая же, как и в примере написанной программы.
w=G(h)= he mod p = 732075 mod 21823=8774; (посчитано на инженерном стандартном калькуляторе в операционной системе Windows)
h=Q(w)=wd mod p = 877483 mod 21823 = 73 = I
Надёжность шифрования обеспечивается тем, что третьему лицу (старающемуся взломать шифр) очень трудно вычислить закрытый ключ по открытому.
Оба ключа вычисляются из одной пары простых чисел (v и u). То есть ключи связаны между собой. Но установить эту связь очень сложно. Основной загвоздкой является декомпозиция модуля на простые сомножители v и u. Если число является произведением двух очень больших простых чисел, что его очень трудно разложить на множители.
Некоторые атаки на RSA.
1. Разложение на множители.
Реализуется на подборе простых чисел u, v, для надёжности числа должны быть большими.
2. Выборка шифрованного текста.
Пусть Ева перехватывает сообщение w от Алисы к Бобу w=ze (mod n), где z- открытый текст, е — открытый ключ; Ева выбирает число r, r<n и вычисляет с помощью открытого ключа x=re (mod n) ,y= x*c (mod n)
Ева передает Y бобу для дешифрования и получает g = yd mod n. Ева может легко найти z
g= yd mod n=(w*xe)d mod n = (wd*xed)mod n = (wd*x) mod n =(z*x)mod n
z= (z*x) mod n -> z=w*x-1 mod n
3.
Исходный текст.
Криптосистема RSA обладает низкой криптостойкостью при малой экспоненте на коротком сообщении. Действительно, при c = me < n открытый текст m может быть восстановлен по шифротексту © при помощи процедуры извлечения корня. Однако меры противодействия также очевидны, — либо открытый ключ e должен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого e обусловлен соображениями вычислительной эффективности шифрования и проверки подписи.
Это показывает, что применение на практике шифрования RSA обладает низкой криптостойкостью, поэтому пользуются схемой дополнительного шифрования OAEP.
Оптимальное асимметричное дополнение шифрования (OAEP — Optimal Assimetric Encryption Padding) — схема дополнения, обычно используемая совместно с какой-либо односторонней функцией с потайным входом (например RSA или функции Рабина) для повышения криптостойкости последней.
Шифрование.
Ниже показаны шаги процесса шифрования.
Дешифрование. Следующие шаги показывают процесс дешифрования:
Алгоритм OAEP применяется для предварительной обработки сообщения перед использованием RSA. Сначала сообщение дополняется до фиксированной длины с помощью OAEP, затем шифруется с помощью RSA.
Литература:
Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002.RSA является примером криптография с открытым ключом , которая иллюстрируется следующим примером: предположим, Алиса хочет послать Бобу ценный бриллиант, но драгоценность будет украдена, если будет отправлена незащищенной. И у Алисы, и у Боба есть разные замки, но они не владеют одинаковыми, а это означает, что их ключи не могут открыть замки друг друга.
Как Алиса отправила алмаз Бобу?
Решение:
- Сначала Боб отправляет Алисе незапертый замок.
Обратите внимание, что Боб дал бы кто-нибудь незапертый замок, так как единственное применение от него — отправить что-нибудь Бобу.
- Алиса добавляет замок Боба и отправляет пакет Бобу, а
- Боб снимает замок и открывает посылку.
Этот пример демонстрирует идеи, лежащие в основе криптографии с открытым ключом, хотя на самом деле концепция немного отличается. В криптографии с открытым ключом. Алиса шифрует свое сообщение с помощью открытого ключа Боба, который может быть расшифрован только закрытым ключом Боба.
В RSA открытый ключ генерируется путем умножения двух больших простых чисел \(p\) и \(q\) вместе, а закрытый ключ генерируется с помощью другого процесса, включающего \(p\) и \(q\). ). Затем пользователь может распространить свой открытый ключ \(pq\), и любой, кто пожелает отправить пользователю сообщение, зашифрует свое сообщение с помощью открытого ключа. Для всех практических целей даже компьютеры не могут разлагать большие числа на произведение двух простых чисел, точно так же, как разложить на множители такие числа, как 414863, вручную практически невозможно.
Однако умножить на два числа гораздо проще, поэтому потенциальную факторизацию можно быстро проверить, как показывает следующая задача с множественным выбором:
\[577 \times 709\] \[577 \раз 719\] \[587 \раз 709\] \[587 \times 719\]
Что из следующего является правильной простой факторизацией числа 414863?
Когда пользователь получает зашифрованное сообщение, он расшифровывает его с помощью закрытого ключа и может прочитать исходный текст. Более подробное и техническое объяснение следует в следующем разделе.
Реализация RSA широко использует модульную арифметику, теорему Эйлера и функцию Эйлера. Обратите внимание, что каждый шаг алгоритма включает в себя только умножение, поэтому компьютеру это легко сделать:
{16}+1=65537\), хотя в некоторых случаях оно может быть меньше \(3\). \(e\) будет второй половиной открытого ключа.Теперь, когда открытый и закрытый ключи сгенерированы, их можно повторно использовать столько раз, сколько потребуется. Чтобы передать сообщение, выполните следующие действия:
Сначала отправитель преобразует свое сообщение в число \(m\). В одном распространенном процессе преобразования используется алфавит ASCII:
| A | B | C | D | E | F | G | H | I | J | K | L | M | ||
| 65 | 66 | 67 | 68 | . 0075 | Q | R | S | T | U | V | W | X | Y | Z |
| 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
следующий → ← предыдущая Алгоритм шифрованияRSA — это тип алгоритма шифрования с открытым ключом. Чтобы лучше понять RSA, давайте сначала разберемся, что такое алгоритм шифрования с открытым ключом. Алгоритм шифрования с открытым ключом:Алгоритм шифрования с открытым ключом также называется асимметричным алгоритмом.
Открытый ключ используется для шифрования, а закрытый ключ используется для расшифровки. Расшифровка не может быть выполнена с использованием открытого ключа. Два ключа связаны, но закрытый ключ не может быть получен из открытого ключа. Открытый ключ хорошо известен, а закрытый ключ является секретным и известен только пользователю, владеющему ключом. Это означает, что каждый может отправить сообщение пользователю, используя открытый ключ пользователя. Но только пользователь может расшифровать сообщение, используя свой закрытый ключ. Алгоритм открытого ключа работает следующим образом:
Алгоритм шифрования RSA:RSA — наиболее распространенный алгоритм с открытым ключом, названный в честь его изобретателей Ривеста, Шамира и Адельмана (RSA). Алгоритм RSA использует следующую процедуру для создания открытых и закрытых ключей:
Давайте рассмотрим пример алгоритма шифрования RSA:Пример 1:В этом примере показано, как мы можем зашифровать открытый текст 9, используя алгоритм шифрования с открытым ключом RSA. В этом примере используются простые числа 7 и 11 для создания открытого и закрытого ключей. Объяснение: Шаг 1: Выберите два больших простых числа, p и q . р = 7 д = 11 Шаг 2: Умножьте эти числа, чтобы найти n = p x q, , где n называется модулем для шифрования и дешифрования. Сначала вычисляем n = п х кв n = 7 х 11 n = 77 Шаг 3: Выберите число e меньше n , такое, что n взаимно простое с (p — 1) x (q -1). Это означает, что e и (p — 1) x (q — 1) не имеют общего делителя, кроме 1. Во-вторых, мы вычисляем φ (n) = (p — 1) x (q-1) φ (n) = (7 — 1) x (11 — 1) φ (n) = 6 х 10 φ(n) = 60 Теперь выберем относительное простое число e числа 60 как 7. Таким образом, открытый ключ Шаг 4: Открытое текстовое сообщение m шифруется с использованием открытого ключа Чтобы найти зашифрованный текст из открытого текста, используется следующая формула для получения зашифрованного текста C. C = m e мод n С = 9 7 мод 77 С = 37 Шаг 5: Закрытый ключ D e mod {(p — 1) x (q — 1)} = 1 7d mod 60 = 1, что дает d = 43 Закрытый ключ Шаг 6: Зашифрованное сообщение c расшифровывается с помощью закрытого ключа м = с d мод п м = 37 43 мод 77 м = 9 В этом примере обычный текст = 9 и зашифрованный текст = 37 В криптосистеме RSA конкретный A использует два простых числа, 13 и 17, для генерации открытого и закрытого ключей. Если общедоступность A равна 35. Тогда закрытый ключ A равен ……………?. Объяснение: Шаг 1: на первом шаге выберите два больших простых числа, p и q . р = 13 q = 17 Шаг 2: Умножьте эти числа, чтобы найти n = p x q, , где n называется модулем для шифрования и дешифрования. Сначала вычисляем n = п х кв п = 13 х 17 n = 221 Шаг 3: Выберите число e меньше n , такое, что n взаимно простое с (p — 1) x (q -1). Во-вторых, мы вычисляем φ (n) = (p — 1) x (q-1) φ (n) = (13 — 1) x (17 — 1) φ (n) = 12 х 16 φ (n) = 192 г.к.д (35, 192) = 1 Шаг 3: Чтобы определить закрытый ключ, мы используем следующую формулу для вычисления d так, что: Вычислить d = d e mod φ (n) = 1 d = d x 35 mod 192 = 1 d = (1 + k.φ (n))/e [пусть k =0, 1, 2, 3………………] Положите k = 0 д = (1 + 0 х 192)/35 д = 1/35 Положите k = 1 д = (1 + 1 х 192)/35 д = 193/35 Положите k = 2 д = (1 + 2 х 192)/35 д = 385/35 д = 11 Закрытый ключ Следовательно, закрытый ключ, т. Криптосистема RSA использует два простых числа 3 и 13 для генерации открытого ключа = 3 и закрытого ключа = 7. Каково значение зашифрованного текста для обычного текста? Объяснение: Шаг 1: На первом этапе выберите два больших простых числа: p и q . р = 3 д = 13 Шаг 2: Умножьте эти числа, чтобы найти n = p x q, , где n называется модулем для шифрования и дешифрования. Сначала вычисляем n = п х кв п = 3 х 13 n = 39 Шаг 3: Если n = p x q, , тогда открытый ключ Чтобы найти зашифрованный текст из открытого текста, используется следующая формула для получения зашифрованного текста C. C = m e мод n С = 5 3 мод 39 С = 125 мод 39 С = 8 Следовательно, зашифрованный текст, сгенерированный из открытого текста, C = 8. Криптосистема RSA использует два простых числа, 3 и 11, для генерации закрытого ключа = 7. Каково значение зашифрованного текста для обычного текста 5 с использованием алгоритма шифрования с открытым ключом RSA? Объяснение: Шаг 1: на первом шаге выберите два больших простых числа, p и q . р = 3 д = 11 Шаг 2: Умножьте эти числа, чтобы найти n = p x q, , где n называется модулем для шифрования и дешифрования. Сначала вычисляем n = п х кв n = 3 х 11 n = 33 Шаг 3: Выберите число e меньше n , такое, что n взаимно простое с (p — 1) x (q -1). |
Обратите внимание, что Боб дал бы кто-нибудь незапертый замок, так как единственное применение от него — отправить что-нибудь Бобу.
\) 9{107} \equiv 72 \pmod{187}\), таким образом получая сообщение \(m=72\).
2016, 1024-битные (309 цифр) ключи считаются рискованными, а большинство вновь сгенерированных ключей имеют длину 4096 бит (1234 цифры).
Асимметричные алгоритмы — это алгоритмы, в которых отправитель и получатель используют разные ключи для шифрования и дешифрования. Каждому отправителю назначается пара ключей:
B отвечает A, шифруя свое сообщение, используя открытый ключ A.
Открытое текстовое сообщение m зашифровано с использованием открытого ключа 
Выберите «e» так, чтобы 1
Для вычисления открытого текста m из зашифрованного текста c используется следующая формула для получения открытого текста m.
Это означает, что e и (p — 1) x (q — 1) не имеют общего делителя, кроме 1. Выберите «e» так, чтобы 1
е. d = 11
