Оценка статьи:

Поделиться с друзьями:

infoprotect.net

Шифрование RSA для первокурсников / Habr

В этой статье я решаю на языке MIT Scheme задачу шифрования и дешифрования методом RSA [1]. По ряду причин, которые рассматриваются в статье, реализация не может использоваться для криптографической защиты информации.

Первый этап генерации ключей — случайный выбор двух достаточно больших простых чисел 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].

Как и в группе целых чисел, умножение в кольце вычетов можно задать при помощи сложения, а возведение в степень — при помощи умножения. Как и в группе целых чисел, получившиеся операции сложения и умножения будут обладать ассоциативностью, то есть:
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))

(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)
  )

1. en.wikipedia.org/wiki/RSA
2. en.wikipedia.org/wiki/Integer_factorization
3. en.wikipedia.org/wiki/Euler%27s_totient_function
4. en.wikipedia.org/wiki/Euclidean_algorithm
5. en.wikipedia.org/wiki/Modular_arithmetic
6. en.wikipedia.org/wiki/Extended_Euclidean_algorithm
7. en.wikipedia.org/wiki/Exponentiation_by_squaring

habr.com

Выбор параметров шифра RSA и возможные последствия / Habr

Процитируем авторов учебного пособия «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001г., на странице 316:

«Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа n) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p, q или φ(n), можно легко найти секретный ключ RSA…».

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

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

Вначале приведем сам пример со стр. 313-315 из названного пособия.

Пример

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Поскольку –137≡343(mod480), то d=343.

Проверка: 7∙343=2401≡1(mod480).

Текстовое сообщение представляется в виде последовательности чисел, содержащихся в интервале [0, 526]. Для этого буквы R, S и A кодируются пятиразрядными двоичными числами. Используются порядковые номера этих букв в английском алфавите при их двоичном представлении:

R=18₁₀=(10010)₂, S=19₁₀=(10011)₂,
A=1₁₀=(00001)₂.

Тогда RSA=(100101001100001)₂. Разбиение текста на блоки ограниченной длины дает представление из двух блоков: RSA=(100101001), (100001)=(М₁=297, М₂=33).

Последовательно шифруются блоки исходного текста М₁=297, М₂=33:
y₁=Е_k(М₁)=М₁^e≡297⁷(mod527)=474.

Здесь воспользовались тем, что:

297⁷=((297²)³)297≡(mod527)=(200³(mod527)297)(mod527)=474,
y₂=Е_k(М₂)=M₂^e≡33⁷(mod527)=407.

Шифрованный текст, как и исходный, получаем в виде двух блоков: у₁=474; у₂=407.

Расшифрование представляется последовательностью действий D_k(y_i )=(y_i )^d=(y_i )³⁴³(mod 527), i=1,2.

Вычисления возведения в степень d более удобно проводить, предварительно представляя показатель степени суммой степеней числа 2, а именно: 343=256+64+16+4+2+1.

Используя это представление показателя степени d=343, получаем:

474²≡174(mod527),
474⁴≡237(mod527),
474⁸≡307(mod527),
474¹⁶≡443(mod527),
474³²≡205(mod527),
474⁶⁴≡392(mod527),
474¹²⁸≡307(mod527),
474²⁵⁶≡443(mod527),
и окончательно 474³⁴³(mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Аналогично вычисляется значение 407³⁴³(mod527)=33.

Переход к буквенному представлению расшифрованного сообщения дает: RSA.

После рассмотрения примера в пособии приводятся рассуждения о стойкости системы RSA. Подчеркивается необходимость соблюдения осторожности в выборе модуля шифра RSA (числа n) для каждого из корреспондентов сети. Указывается на недопустимость игнорирования требований к выбираемым характеристикам системы шифрования. Среди таких требований, к сожалению, не указано то, нарушение которого иллюстрирует приведенный пример.

Атака на шифр RSA

Неудачность (недопустимость) выбранных параметров системы в этом примере легко показывается вычислениями, реализующими атаку бесключевого чтения исходного текста. Сущность такой атаки состоит в следующем. Заданы открытый ключ шифра RSA (е=7, n=527) и шифрованный текст. В примере шифрованный текст представлен двумя блоками
у=(у₁=474, у₂=407).

Каждый шифрованный блок атакуется индивидуально, вначале атакуем у₁=474, после его дешифрования, атакуем другой блок у₂=407.

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

В алгоритме атаки на шифрованный текст определяется такой номер шага j, для которого y_i^ej(mod n)=(y_i^ej–1(mod n))^e(mod n)=y_i, i>1. Из последнего соотношения видим, что при возведении в степень е значения (y_i^ej–1(mod n)) получается начальный шифoртекст y_i = у₁.

Но это и означает, что на этом шаге шифровался открытый текст. Непосредственными вычислениями (их оказывается совсем немного) с использованием экранного калькулятора находим то значение j, при котором цикл шифрования завершается значением y₁, с которого цикл и был начат.

Атака на первый блок у₁=474 шифртекста.
Шаг 1: &nbsp 474⁷(mod527)=382;
Шаг 2: &nbsp 382⁷(mod527)=423;
Шаг 3: &nbsp 423⁷(mod527)=297;
Шаг 4: &nbsp на этом шаге шифруется уже найденный исходный текст, но его необходимо выполнить, так как атакующий исходного текста не знает. Признаком завершения атаки является совпадение начального значения шифртекста (474) и результата 4-го шага зашифрования. Именно такое совпадение и имеет место.

297⁷(mod527)=474 получили начальный (первый) блок шифртекста. Атака на первый блок завершена успешно у₁=474. Предшествующий результат шага 3 равен открытому тексту М₁=297.

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=297 по модулю n=527. Это записывается так y_i=у₁=297. Формируем степенные вычеты
(((297⁷(mod527))⁷(mod527))⁷(mod527))⁷=297.

Атака на второй блок у₂=407 шифртекста.
Шаг 1: &nbsp 407⁷(mod527)=16;
Шаг 2: &nbsp 16⁷(mod527)=101;
Шаг 3: &nbsp 101⁷(mod527)=33;
Шаг 4: &nbsp 33⁷(mod527)=407.

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

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=33 по модулю n=527. Это записывается так y_i=у₂=33.
Формируем степенные вычеты ((33⁷(mod527))⁷(mod527))⁷(mod527)=33.

Результат атаки (исходный текст М₁=297, М₂=33) получен трехкратным шифрованием заданного шифртекста. Больший успех для атакующего шифртекст трудно представить.

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

Ни на одном из заданных е не удается зашифровать исходные тексты, представляемые числами
187, 341, 154 и 373.

Пример (невозможность шифрования значений некоторых исходных текстов)

154²(mod527)=1;
154⁴(mod527)=1;
154⁷(mod527)=154;
154⁹(mod527)=154;
154¹⁷(mod527)=154;
154¹¹¹(mod527)=154;
187²(mod527)=187;
187⁴(mod527)=187;
187⁷(mod527)=187;
187⁹(mod527)=187;
187¹⁷(mod527)=187;
187¹¹¹(mod527)=187;
341²(mod527)=341;
341⁴(mod527)=1;
341⁷(mod527)=341;
341⁹(mod527)=341;
341¹⁷(mod527)=341;
341¹¹¹(mod527)=341;
373²(mod527)=1;
373⁴(mod527)=373;
373⁷(mod527)=373;
373⁹(mod527)=373;
373¹⁷(mod527)=373;
373¹¹¹(mod527)=373.

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

habr.com

Задача №3. Алгоритм шифрования rsa.

Сгенерируйте открытый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.

Решение

I.Генерация ключей.

Выберем два простых числа р = 17 и q = 23

Тогда модуль

n = p*q=17*23 = 391

и функция Эйлера

(n) = (p-1)*(q-1) = (17-1)*(23-1)=16*22=352.

Закрытый ключ d выбираем из условий d < (n) и d взаимно просто с (n), т.е. d и (n) не имеют общих делителей.

Пусть d = 41.

Открытый ключ e выбираем из условий e<(n) и de=1(mod (n)): e<352,

41e=1(mod 352).

Последнее условие означает, что число 41e-1 должно делиться на 352 без остатка.

Таким образом, для определения e нужно подобрать такое число k, что

41e-1 = 352 k.

При k=29 получаем 41e=10208+1 или

e=249.

Получаем

(249, 391) – открытый ключ (KU),

( 41, 391) – секретный ключ (KR).

II. Шифрование.

Представим шифруемое сообщение «ГИН» как последовательность целых чисел. Пусть буква «Г» соответствует числу 22, буква «И» — числу 4 и буква «Н» — числу 9.

Зашифруем сообщение, используя открытый ключ (249, 391):

С₁ = (22²⁴⁹) mod 391= 114

С₂ = (4²⁴⁹) mod 391=123

С₃ = (9²⁴⁹) mod 391= 349

Таким образом, исходному сообщению (22, 4, 9) соответствует криптограмма (114, 123, 349).

III. Расшифрование

Расшифруем сообщение (114, 123, 349), пользуясь секретным ключом (41, 391):

М₁ = ( 114⁴¹) mod 391=22

М₂ = (123⁴¹) mod 391= 4

М_З = ( 349⁴¹) mod 391=9

В результате расшифрования было получено исходное сообщение (22, 4, 9), то есть «ГИН».

Задача №4. Функция хеширования.

Найти хеш–образ своей Фамилии, используя хеш–функцию , гдеn = pq, p, q взять из Задачи №2.

Решение

Хешируемое сообщение «ГАЗИЗОВ». Возьмем два простых числа p=17, q=23. Определим n=p*q=17*23=391. Вектор инициализации выберем равным 9 (выбираем случайным образом). Слово«ГАЗИЗОВ» можно представить последовательностью чисел 4, 1, 11, 9, 21, 13, 13) по номерам букв в алфавите. Таким образом,

n=391, H₀=9, M₁=22, M₂=1, M₃=11, M₄=9, M₅=21, M₆=13.

Используя формулу

,

получим хеш-образ сообщения «ГАЗИЗОВ»:

H₁ = (H₀+M₁)² mod n = (9 + 22)² mod 391 = 961 mod 391=179

H₂ = (H₁+M₂)² mod n = (179 + 1)² mod 391 = 32400 mod 391= 338

H₃ = (H₂+M₃)² mod n = (338 + 11)² mod 391 = 121801 mod 391= 200

H₄ = (H₃+M₄)² mod n = (200 + 9)² mod 391 = 43681 mod 391= 280

H₅ = (H₄+M₅)² mod n = (280 + 21)² mod 391 = 90601 mod 391= 280

H₆ = (H₅+M₆)² mod n = (280 + 13)² mod 391 = 85849 mod 391= 220

H₇ = (H₆+M₇)² mod n = (220 + 13)² mod 391 = 54289 mod 391= 331

В итоге получаем хеш-образ сообщения «ГАЗИЗОВ», равный 361.

Задача №5. Электронная цифровая подпись.

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

Решение

Хеш-образ Фамилии равен 361, а закрытый ключ алгоритма RSA равен (41, 391). Тогда электронная цифровая подпись сообщения, состоящего из Фамилии, вычисляется по правилу

s = 361 ⁴¹ mod 391 = 242.

Для проверки ЭЦП, используя открытый ключ (249, 391), найдем

H = 242 ²⁴⁹ mod 391 = 361.

Поскольку хеш-образ сообщения совпадает с найденным значением H, то подпись признается подлинной.

studfiles.net