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

В этой статье я решаю на языке 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. 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