Алгоритм RSA на Go

Перевод статьи “RSA - theory and implementation”

RSA - популярный метод криптографии с открытым ключом. Ему уже больше 40 лет, он все еще популярен и используется для некоторых задач в новейшем стандарте TLS 1.3. В этом посте описана математика и некоторые практики которые лежат в основе RSA. Все это применим на практике и реализуем генерацию RSA ключей на Go.

Алгоритм RSA

Красота алгоритма RSA в его простоте. Вам достаточно знакомства с элементарной теорией чисел, чтобы разобраться в сути за пару часов.

Договоримся, сто в этой статье M это сообщение, которое хотим зашифровать. C - уже зашифрованный текст. C и M большие целые числа. В разделе “Практические соображения” описано как можно представить любые данные в виде больших целых чисел.

Алгоритм RSA состоит из трех основных фаз: генерация ключа, шифрование и дешифрование.

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

Первое что нужно сделать при использовании RSA - сгенерировать приватный и публичный ключи. Это делается в несколько этапов.

Шаг 1: Выбираем два случайных больших числа p и q и вычисляем n=pq. Насколько большими должны быть эти числа? Рекомендуется выбирать размер для n не меньше 2048 бит, более 600 десятичных цифр. Предполагается, что сообщение M представлено числом меньше чем n(в разделе “Практические соображения” рассказывается что делать если сообщение слишком большое).

Шаг 2: Выбираем маленькое нечетное число e, которое будет относительно простым к общей функции Эйлера \(\phi(n)\), которая рассчитывается по формуле эйлера:

$$ \phi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right) $$

Для \(n=pq\) где p и q простые числа получаем:

$$ \phi(n)=n\frac{p-1}{p}\frac{q-1}{q}=(p-1)(q-1) $$

На практике рекомендуется выбирать e как одно из известных простых чисел, чаще всего это 65537. Выбор заранее известного числа никак не влияет на безопасность алгоритма, но дает плюсы в производительности [1].

Шаг 3: Вычисляем d как мультипликативного обратного по модулю e от \(\phi(n)\). Лемма 3 в этой статье гарантирует что d существует и будет уникальным(еще там объясняется что такое модуль мультипликативного обратного).

Сейчас у нас есть все для генерации приватного и публичного ключа. Публичный ключ это пара \([e,n]\), приватный это пара \([d,n]\). На практике, при расшифровке у нас уже есть доступ к n (из публичного ключа), поэтому действительно приватным будет только d.

Шифрование и дешифрование

Шифрование и дешифрование выполняются с помощью одной и той же модульной формулы возведения в степень. Меняются только значения x и y

$$ f(x)=x^y\pmod{n} $$

Для шифрования входное значение будет M, а показатель степени e:

$$ Enc(M)=M^e\pmod{n} $$

Для дешифровки входное значение это закодированный текст C, а степень будет d:

$$ Dec(C )=C^d\pmod{n} $$

Почему это работает?

Для шифрования сообщения M мы возводим его в степень e по модулю n. Этот процесс обратим. С помощью возведения в степень d по модулю n мы получим обратно наше сообщение M. Но почему это работает?

Доказательство:

$$ Dec(Enc(M))=M^{ed}\pmod{n} $$

Напомню, что e и d мультипликативно инверсные по модулю \(\phi(n)\). Это значит \(ed\equiv 1\pmod{\phi(n)}\). Отсюда следует, что для некоторых целых чисел k у нас есть \(ed=1+k\phi(n)\) или \(ed=1+k(p-1)(q-1)\).

Теперь посмотрим что такое \(M^{ed}\) по модулю p. Подставляем формулу для ed получим:

$$ M^{ed}\equiv M(M^{p-1})^{k(q-1)}\pmod{p} $$

Теперь модем использовать малую теорему Ферма, из которой следует что если M не делится на p то \(M^{p-1}\equiv 1\pmod{p}\). Эта теорема частный случай теоремы Эйлера, доказательство я приводил в этой статье.

В последнем выражении можно убрать 1 для \(M^{p-1}\) и возведение 1 в любую степень тоже дает 1:

$$ M^{ed}\equiv M\pmod{p} $$

Заметим, что малая теорема ферма работает когда M не делится на p. Мы можем утверждать это, потому что если \(M\equiv 0\pmod{p}\) то \(M^{ed}\equiv 0\pmod{p}\) и снова \(M^{ed}\equiv M\pmod{p}\)

Аналогично можем доказать что:

$$ M^{ed}\equiv M\pmod{q} $$

И так, получается \(M^{ed}\equiv M\) для простых множителей ed. Согласно следствию китайской теоремы об остатках, получается что

$$ M^{ed}\equiv M\pmod{n} $$

Так как изначально мы определили что M меньше n, то выполняется \(Dec(Enc(M))=M\)

Почему это безопасно?

Без приватного ключа, злоумышленник может вычислить только \(M^e\pmod {n}\) и значения n и e (как части публичного ключа). Может ли он получить значение M в этом случае?

Нет известных способов сделать это без факторизации n(оригинальная спецификация RSA, секция IX), а факторизация, как известно, сложная задача. В частности, предполагается что M и e достаточно большие что \(M^e > n\)(иначе дешифровка была бы очень простой)

Если бы факторинг был бы простым, то можно было бы разложить n на p и q, потом вычислить \(\phi(n)\) и в конце концов найти d из \(ed\equiv 1\pmod{\phi(n)}\) использую расширенный алгоритм Евклида.

Практические соображения

Алгоритм, описанный в этой статье, иногда называют “книжным” RSA(или алгоритмом из учебника). В нем идет речь только про цифры и игнорируются все практические вопросы. Фактически, такой “книжный” алгоритм неустойчив перед несколькими хитрыми атаками и должен усиливаться случайными схемами заполнения для практического использования.

Существует простая схема заполнения PKCS #1 v1.5. Она использовалась много лет определена в стандарте RFC 2313. Сейчас вместо нее рекомендуется использовать более продвинутые схемы, например OAEP. Но PKCS #1 v1.5 проще для понимания, поэтому я объясню принцип на ее примере.

Предположим, у нас есть некоторые двоичные данные D для шифрования. Описанный метод подходит для данных любого размера, но мы сосредоточимся на шифровании небольших фрагментов. На практике этого, как правило, достаточно - RSA обычно используется для шифрования только симметричного ключа, который намного меньше чем ключ RSA [2]. Но такая схема может работать с данными любого объема, достаточно просто разделить их на блоки с заранее известным размером.

Из данных D создаем блок для шифрования. Размер блока равен длине нашего RSA ключа:

PS - это заполнение которое занимает все байты не занятые заголовком и данными D в рамках блока. Оно должно быть не меньше 8 байт(если это не так, то данные могут быть разбиты на несколько блоков). Заполнение - это последовательность случайных не нулевых байт, которая генерируется отдельно для каждого шифрования. Как только мы сформируем этот блок данных, преобразовываем его в число используя big-endian кодировку [3]. В итоге у нас получается большое число, которое уже можно шифровать с помощью RSA \(Enc(x)=x^e\pmod{n}\). Результат кодируем в бинарный вид и отправляем по сети.

Дешифровка проходит в обратном порядке. Принятый поток байт превращаем в число, выполняем \(Dec(C)=C^d\pmod{n}\), удаляем все заполнения. В заполнении нет 0 байтов а разделяются они как раз 0 байтами, поэтому вырезать их просто. В итоге у нас получается наше исходное сообщение.

Случайное заполнение усиливает стойкость и атаки на “книжный” алгоритм RSA становятся непрактичными. Но в целом, в некоторых случаях схема все еще уязвима для более сложных атак. Поэтому на практике стоит использовать более современные схемы заполнения, такие как OAEP.

Реализация RSA на Go

Я реализовал на Go описанный в этой статье простой вариант шифрования и дешифрования RSA. Реализация на Go таких криптографических алгоритмов довольно простое дело из-за возможности работы с большими числами произвольной точности. Для этого используется пакет bid из стандартной библиотеки. В этом пакете поддерживаются не только основные манипуляции с числами, но и есть несколько примитивов специально для криптографии. Например метод Exp используется для эффективного возведения в степень, а метод ModInverse позволяет искать мультипликативно обратных по модулю. А в модуле crypto/rand есть примитивы специально предназначенные для использования в криптографии.

Кстати, в Go уже есть реализация RSA в пакете crypto/rsa. Для реальных проектов лучше использовать его[4], чем писать свой велосипед. Код ниже стоит использовать только для учебных целей.

Весь код целиком доступен на GitHub.

Начинаем с определения структур для публичного и приватного ключа:

1type PublicKey struct {
2  N *big.Int
3  E *big.Int
4}
5
6type PrivateKey struct {
7  N *big.Int
8  D *big.Int
9}

В коде есть функция GenerateKeys, которая случайным образом генерирует эти ключи с заданной длинной.

Имея публичный ключ, шифрование будет очень простым:

1func encrypt(pub *PublicKey, m *big.Int) *big.Int {
2  c := new(big.Int)
3  c.Exp(m, pub.E, pub.N)
4  return c
5}

А дешифрование

1func decrypt(priv *PrivateKey, c *big.Int) *big.Int {
2  m := new(big.Int)
3  m.Exp(c, priv.D, priv.N)
4  return m
5}

Логика в этих функциях одинаковая и очень простая. Это просто типизированные обертки над Exp.

В конце нам нужно добавить реализацию PKCS #1 v1.5:

 1// EncryptRSA encrypts the message m using public key pub and returns the
 2// encrypted bytes. The length of m must be <= size_in_bytes(pub.N) - 11,
 3// otherwise an error is returned. The encryption block format is based on
 4// PKCS #1 v1.5 (RFC 2313).
 5func EncryptRSA(pub *PublicKey, m []byte) ([]byte, error) {
 6  // Compute length of key in bytes, rounding up.
 7  keyLen := (pub.N.BitLen() + 7) / 8
 8  if len(m) > keyLen-11 {
 9    return nil, fmt.Errorf("len(m)=%v, too long", len(m))
10  }
11
12  // Following RFC 2313, using block type 02 as recommended for encryption:
13  // EB = 00 || 02 || PS || 00 || D
14  psLen := keyLen - len(m) - 3
15  eb := make([]byte, keyLen)
16  eb[0] = 0x00
17  eb[1] = 0x02
18
19  // Fill PS with random non-zero bytes.
20  for i := 2; i < 2+psLen; {
21    _, err := rand.Read(eb[i : i+1])
22    if err != nil {
23      return nil, err
24    }
25    if eb[i] != 0x00 {
26      i++
27    }
28  }
29  eb[2+psLen] = 0x00
30
31  // Copy the message m into the rest of the encryption block.
32  copy(eb[3+psLen:], m)
33
34  // Now the encryption block is complete; we take it as a m-byte big.Int and
35  // RSA-encrypt it with the public key.
36  mnum := new(big.Int).SetBytes(eb)
37  c := encrypt(pub, mnum)
38
39  // The result is a big.Int, which we want to convert to a byte slice of
40  // length keyLen. It's highly likely that the size of c in bytes is keyLen,
41  // but in rare cases we may need to pad it on the left with zeros (this only
42  // happens if the whole MSB of c is zeros, meaning that it's more than 256
43  // times smaller than the modulus).
44  padLen := keyLen - len(c.Bytes())
45  for i := 0; i < padLen; i++ {
46    eb[i] = 0x00
47  }
48  copy(eb[padLen:], c.Bytes())
49  return eb, nil
50}

И обратные преобразования:

 1// DecryptRSA decrypts the message c using private key priv and returns the
 2// decrypted bytes, based on block 02 from PKCS #1 v1.5 (RCS 2313).
 3// It expects the length in bytes of the private key modulo to be len(eb).
 4// Important: this is a simple implementation not designed to be resilient to
 5// timing attacks.
 6func DecryptRSA(priv *PrivateKey, c []byte) ([]byte, error) {
 7  keyLen := (priv.N.BitLen() + 7) / 8
 8  if len(c) != keyLen {
 9    return nil, fmt.Errorf("len(c)=%v, want keyLen=%v", len(c), keyLen)
10  }
11
12  // Convert c into a bit.Int and decrypt it using the private key.
13  cnum := new(big.Int).SetBytes(c)
14  mnum := decrypt(priv, cnum)
15
16  // Write the bytes of mnum into m, left-padding if needed.
17  m := make([]byte, keyLen)
18  copy(m[keyLen-len(mnum.Bytes()):], mnum.Bytes())
19
20  // Expect proper block 02 beginning.
21  if m[0] != 0x00 {
22    return nil, fmt.Errorf("m[0]=%v, want 0x00", m[0])
23  }
24  if m[1] != 0x02 {
25    return nil, fmt.Errorf("m[1]=%v, want 0x02", m[1])
26  }
27
28  // Skip over random padding until a 0x00 byte is reached. +2 adjusts the index
29  // back to the full slice.
30  endPad := bytes.IndexByte(m[2:], 0x00) + 2
31  if endPad < 2 {
32    return nil, fmt.Errorf("end of padding not found")
33  }
34
35  return m[endPad+1:], nil
36}

RSA для цифровой подписи

RSA можно использовать для цифровой подписи. Как это работает:

1. Генерируются и распространяются ключи также. У Алисы есть открытый и закрытый ключи. Она публикует свой открытый ключ в интернете.
2. Когда Алиса захочет отправить сообщение Бобу, ей нужно убедить его, что это она отправляет сообщение. Для этого она шифрует сообщение своим секретным ключем \(S=Sign(M)=M^d\pmod{n}\). Подпись добавляется к сообщению.
3. Когда Боб получает сообщение, он может расшифровать подпись с помощью публичного ключа Алисы: \(Check(S)=S^e\pmod{n}\) и если получится восстановить исходное сообщение, от подпись верна.

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

Это тоже “книжный” алгоритм подписи. В реальных алгоритмах подписи тоже используется механизм заполнения. Для подписи рекомендуют использовать PSS [5]. Я не буду в этой статье реализовывать алгоритм подписи, в стандартной библиотеке Go уже есть отличные реализации, например rsa.SignPKCS1v15 и rsa.SignPSS.

Примечания

• 1. Под двум причинам: во-первых, не нужно находить другое случайное большое число и это экономит время, во-вторых 65537 имеет только два выставленных бита в двоичном представлении, а это делает алгоритм возведения в степень быстрее.
• 2. Сильный AES ключ это 256 бит. RSA, как правило, 2048. RSA работает достаточно медленно, поэтому для потоковых данных часто используют гибридную схему, когда с помощью RSA шифруется только сильные AES ключ. Ёто основополагающая идея работы TLS и похожих протоколов.
• 3. Обратите внимание, что первые 8 бит блока данных равны 0. Это позволяет гарантировать, что число, которое мы шифруем, меньше n
• 4. Реализация в стандартной библиотеке устойчива к атакам типа стороннего канала. Использует алгоритмы время выполнения которых не зависит от характеристик входных данных - это делает атаки основанные на временны'х эффектах менее осуществимыми.
• 5. Причина в различных алгоритмах заполнения для подписи и шифрования в том, что атаки тоже различаются. Если при шифровании злоумышленник ничего не знает о тексте сообщения, то в случае с подписью это не так.