А что, если бы RSA ключи были бы не такими большими?
Всем привет! Прежде чем я начну, хочу поздравить от имени команды revers-pub всех кодеров с ДнЁм ПрОгРаММисТа! Всем добра!
Как-то я задумался, какую я выбрал бы себе сверхспособность, если бы поймал Гари Поттера и попросил бы его исполнить такое желание. На ум пришло сразу две вещи — проецирование радужных таблиц любого размера на жёсткий диск силой мысли и факторизация больших чисел в уме. Но это всё мечты. Сегодня я бы хотел поговорить о том, каким образом можно было бы «взломать» алгоритм RSA. Как мы знаем — его криптостойкость напрямую основана на том принципе, что по результату произведения двух простых чисел мы не можем догадаться какие при этом два сомножителя были использованы. Я не буду сейчас рассказывать принцип работы этого алгоритма, так как статья не об этом. Давайте представим себе следующую правдоподобную ситуацию: между двумя узлами сети была передана зашифрованная информация и открытый ключ. Попути, информация была перехвачена. Требуется расшифровать перехваченный файл. Чтобы это сделать, надо по открытому ключу, в котором передаётся публичная экспонента e и результат произведения p*q=N, получить закрытый. Как это сделать? Чтобы это сделать, нужно разложить на множители N, тем самым определив сомножители p и q. Когда я пытался разобраться со всем этим, в гугле нашёл хорошую статью, которая мне очень помогла. Хочу сразу уточнить то, что сертификаты бывают разных форматов — это DER формат, его чаще использует винда и PEM, его чаще всего используют никсы. Формат PEM создаётся по стандарту x.509. Отличия между ними на самом деле не существенные. В DER формате ключи пишутся в бинарном виде, а в PEM — в текстовом, закодированом в base64. Начало ключа обычно начинается с «——BEGIN RSA PRIVATE/PUBLIC KEY——». Мы будем использовать этот формат.
Чтобы смоделировать ситуацию максимально правдоподобно, давайте сконструируем сертификат с открытым ключом, зашифруем с его помощью наши данные и попробуем их потом расшифровать. Чтобы это сделать нужно сначала получить сертификат с секретными данными (закрытый ключ) по открытому. Приступим:
OpenSsl
Для создания сертификатов будем использовать специальную для этого тулзу — openssl. Она сама сгенерирует пары p и q, сосчитает все экспоненты и сконструирует сертификат. Итак, первым делом сгенерируем приватный ключ:
openssl genrsa -out priv.pem 256
Хочу заметить, что для теста, мы специально указываем число 256, чтобы N побыстрее разложилась на множители. В жизни чаще всего используется длина ключа — 2048 бит. После выполнения данной команды, openssl создаст нам секретный файл с закрытым ключом. Обычно его ещё тут же шифруют каким-нибудь симметричным алгоритмом, например, des. Чтобы это сделать сразу, можно было бы выполнить:
openssl genrsa -des3 -out priv.pem 256
Данная команда получит и зашифрует файл priv.pem. Перед шифрованием, программа запросит ввести ключ шифрования для алгоритма des.Файл priv.pem представляет из себя простой текстовой файл. В нём хранится открытый и закрытый ключ. В моём случае его содержание получилось таким:
-----BEGIN RSA PRIVATE KEY----- MIGsAgEAAiEAqnP8R6UcdQX7YMe2oZg211LIhdb9vQ6akBpeCYg+AV8CAwEAAQIh AKk5DTVzzpS/o5mprL8xhv8P4Yi4yeFNMky3WHWbq7rBAhEA1iTtWAlurhKfUZH9 4y3UbQIRAMvE5Uo4efnXAKRjvmJ8FXsCEQCgt4IyCpI4rt1HeQxVDjZZAhEApwsB IIgNzjdn6ltuLlQkUwIQEypbq/MV2u7cNQGXTvXqIw== -----END RSA PRIVATE KEY-----
Вторым шагом будет -экспорт публичного ключа из файла priv.pem. Как раз эту информацию мы и будем передавать вместе с зашифрованными данными.
openssl rsa -in priv.pem -outform PEM -pubout -out pub.pem
У меня файл pub.pem получился таким:
-----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAKpz/EelHHUF+2DHtqGYNtdSyIXW/b0O mpAaXgmIPgFfAgMBAAE= -----END PUBLIC KEY-----
Просмотреть подробную информацию о ключах вы можете так:
О секретном:
openssl rsa -in priv.pem -text -noout
У меня вот что получилось:
Private-Key: (256 bit)
modulus:
00:aa:73:fc:47:a5:1c:75:05:fb:60:c7:b6:a1:98:
36:d7:52:c8:85:d6:fd:bd:0e:9a:90:1a:5e:09:88:
3e:01:5f
publicExponent: 65537 (0x10001)
privateExponent:
00:a9:39:0d:35:73:ce:94:bf:a3:99:a9:ac:bf:31:
86:ff:0f:e1:88:b8:c9:e1:4d:32:4c:b7:58:75:9b:
ab:ba:c1
prime1:
00:d6:24:ed:58:09:6e:ae:12:9f:51:91:fd:e3:2d:
d4:6d
prime2:
00:cb:c4:e5:4a:38:79:f9:d7:00:a4:63:be:62:7c:
15:7b
exponent1:
00:a0:b7:82:32:0a:92:38:ae:dd:47:79:0c:55:0e:
36:59
exponent2:
00:a7:0b:01:20:88:0d:ce:37:67:ea:5b:6e:2e:54:
24:53
coefficient:
13:2a:5b:ab:f3:15:da:ee:dc:35:01:97:4e:f5:ea:
23
О публичном:
openssl rsa -noout -text -inform PEM -in pub.pem -pubin или сразу убрать двоеточия между байтами openssl rsa -noout -text -inform PEM -in pub.pem -pubin | sed -e 's/://g' | tr 'a-z' 'A-Z'
1 вариант:
Public-Key: (256 bit)
Modulus:
00:aa:73:fc:47:a5:1c:75:05:fb:60:c7:b6:a1:98:
36:d7:52:c8:85:d6:fd:bd:0e:9a:90:1a:5e:09:88:
3e:01:5f
Exponent: 65537 (0x10001)
2 вариант:
PUBLIC-KEY (256 BIT)
MODULUS
00AA73FC47A51C7505FB60C7B6A198
36D752C885D6FDBD0E9A901A5E0988
3E015F
EXPONENT 65537 (0X10001)
Всё, сертификаты готовы, осталось их применить и зашифровать какие-нибудь данные. Я создал файл file.txt с текстом «reverse-pub.ru».
Шифруем его открытым ключом:
openssl rsautl -encrypt -inkey pub.pem -pubin -in enc.txt -out file.ssl
Файл зашифровался и превратился в абсолютно нечитабельный вид:
Зашифрованный файл
Итак, допустим, в результате перехвата нам достался вот этот зашифрованный файл — file.ssl и файл открытого ключа. Попробуем восстановить по нему файл секретного ключа — private.pub.
Для этого нам нужно факторизовать число N. Это можно сделать с помощью утилиты yafu. Её мне посоветовал один классный вирусный аналитик, за что ему огромное спасибо! Итак, запускаем тулзу и пишем команду factor(N), где вместо N подставляем модуль- число, представляющее из себя произведение p и q. Оно берётся из открытого ключа.
factor(0xAA73FC47A51C7505FB60C7B6A19836D752C885D6FDBD0E9A901A5E09883E015F)
Факторизация модуля N с помощью yafu
Теперь остаётся ждать, пока числа факторизуются. Если бы N было бы размером в 2048 бит, то ждать бы пришлось и нашим внукам. Но у нас длина ключа маленькая и результат не заставляет себя так долго ждать! Смотрите, тулза факторизовала число N!
Результат работы yafu
У нас есть числа p и q! Это 284646527690952786261033237415816189037 и 270855623880772631112272052293700687227!
Самое сложное позади, осталось теперь на основании этих данных сгенерировать файл закрытого ключа. Для этого я написал простенький скрипт на python, который получает закрытый ключ d по открытому {e,N}. В него нужно вставить только значения p и q и он нам создаст файл private.cer. Исходный код скрипта такой:
# -*- coding: utf-8 -*-
# d = (k*f(n) +1) / e
# надо подобрать k так, чтобы результат деления был целым. Если не так, то инкрементируем k.
# Есть много разных k, при которых это условие выполнится. Причём, при валидных k ключ d может
# быть разный, но всё-равно валидный....
# функция Эйлера
# p и q находятся методом факторизации n - module
def getFn(p, q):
return (p-1)*(q-1)
# e - публичная экспонента
# Fn - F(n)
def get_k(e, Fn):
k = 1
while True:
if (k*Fn+1) % e == 0:
return k
k=k+1
# p*q = n
# Fn - функция Эйлера.
def get_d(k,Fn,e):
return (k*Fn+1) / e
#
# из публичного ключа берём e
# из публичного ключа берём module и факторизируем его, получаю p и q
#
#
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
# x = mulinv(b) mod n, (x * b) % n == 1
def mulinv(b, n):
g, x, _ = egcd(b, n)
print(g,x,_)
if g == 1:
return x % n
#Создаёт файл приватного ключа
def makePkey(fileName, n, e, d, p, q, e1, e2, coof):
fileContent = '''asn1=SEQUENCE:rsa_key\n
[rsa_key]
version=INTEGER:%d
modulus=INTEGER:%d
pubExp=INTEGER:%d
privExp=INTEGER:%d
p=INTEGER:%d
q=INTEGER:%d
e1=INTEGER:%d
e2=INTEGER:%d
coeff=INTEGER:%d ''' % (0, n, e, d, p, q, e1, e2, coof)
f = open(fileName,'w')
f.write(fileContent)
f.close()
###############################################################
###################### MAIN ###################################
###############################################################
######## Меняем на своё ############
# p > q
p = 284646527690952786261033237415816189037
q = 270855623880772631112272052293700687227
e = 65537
#p = 53
#q = 59
#e = 3
############################################################
n = p*q;
Fn = getFn(p, q)
k = get_k(e, Fn)
d = get_d(k, Fn, e)
#d = mulinv(e, Fn) !работает!
print "Public Key {e, n}: {%d, %d} {0x%X, 0x%X}" % (e, n, e, n)
print "Privet Key {d, n}: {%d, %d} {0x%X, 0x%X}" % (d, n, d, n)
#check
exampl = 123456789
enc = pow(exampl, e, n)
print "exampl orig %d, exampl enc %d " % (exampl, enc)
dec = pow(enc, d, n)
print "exampl orig %d, exampl dec %d " % (exampl, dec)
############################## Для восстановления privet key ##############
e1 = d % (p-1)
e2 = d % (q-1)
coof = mulinv(q, p)
print "e1: %d: 0x%x" % (e1, e1)
print "e2: %d: 0x%x" % (e2, e2)
print "coof: %d: 0x%x" % (coof, coof)
makePkey("private.txt", n, e, d, p, q, e1, e2, coof)
Скрипт нам сгенерил файл private.txt. У меня он получился таким:
asn1=SEQUENCE:rsa_key [rsa_key] version=INTEGER:0 modulus=INTEGER:77098112843228639517650688438017673180534198881664612785117758203279043330399 pubExp=INTEGER:65537 privExp=INTEGER:76541672857039965234545743511774751480570272121805447666126387908639206390465 p=INTEGER:284646527690952786261033237415816189037 q=INTEGER:270855623880772631112272052293700687227 e1=INTEGER:213629310328626634497080745464918062681 e2=INTEGER:222038213421342289187891054053116093523 coeff=INTEGER:25475267710492865297665627336843061795
Теперь нужно скормить эти данные openssl, чтобы она нам из них сделала файл сертификата.
Выполняем:
openssl asn1parse -genconf private.txt -out private.cer
Тулза нам сгенерит сертификат в DER формате. Прежде чем мы его переконвертируем в x.509, давайте проверим его на валидность. Делается это так:
openssl rsa -in private.cer -inform der -text -check
Вот что выдала тулза:
Private-Key: (256 bit)
modulus:
00:aa:73:fc:47:a5:1c:75:05:fb:60:c7:b6:a1:98:
36:d7:52:c8:85:d6:fd:bd:0e:9a:90:1a:5e:09:88:
3e:01:5f
publicExponent: 65537 (0x10001)
privateExponent:
00:a9:39:0d:35:73:ce:94:bf:a3:99:a9:ac:bf:31:
86:ff:0f:e1:88:b8:c9:e1:4d:32:4c:b7:58:75:9b:
ab:ba:c1
prime1:
00:d6:24:ed:58:09:6e:ae:12:9f:51:91:fd:e3:2d:
d4:6d
prime2:
00:cb:c4:e5:4a:38:79:f9:d7:00:a4:63:be:62:7c:
15:7b
exponent1:
00:a0:b7:82:32:0a:92:38:ae:dd:47:79:0c:55:0e:
36:59
exponent2:
00:a7:0b:01:20:88:0d:ce:37:67:ea:5b:6e:2e:54:
24:53
coefficient:
13:2a:5b:ab:f3:15:da:ee:dc:35:01:97:4e:f5:ea:
23
RSA key ok
-----BEGIN RSA PRIVATE KEY-----
MIGsAgEAAiEAqnP8R6UcdQX7YMe2oZg211LIhdb9vQ6akBpeCYg+AV8CAwEAAQIh
AKk5DTVzzpS/o5mprL8xhv8P4Yi4yeFNMky3WHWbq7rBAhEA1iTtWAlurhKfUZH9
4y3UbQIRAMvE5Uo4efnXAKRjvmJ8FXsCEQCgt4IyCpI4rt1HeQxVDjZZAhEApwsB
IIgNzjdn6ltuLlQkUwIQEypbq/MV2u7cNQGXTvXqIw==
-----END RSA PRIVATE KEY-----
Самое главное, чтобы в конце мы нашли строке RSA key ok. У нас всё окей, так что двигаемся дальше. Конвертируем его в PEM формат:
openssl rsa -inform DER -outform PEM -in private.cer -out private.pem
Дальше можно проверить и этот файл, но это совсем не обязательно. Если очень хочется, то можно сделать это так:
openssl rsa -in private.pem -inform PEM -text -check
Убедившись, что всё в порядке, давайте теперь расшифруем с помощью полученного нами private.pem файл file.ssl.
openssl rsa -in private.pem -inform PEM -text -check openssl rsautl -decrypt -inkey private.pem -in file.ssl -out decrypt.txt
В итоге имеем расшифрованный файл decrypt.txt:
Результат
Думаю, теперь вы на практике убедились, что использование коротких ключей может привести к плачевным результатам.
If you found an error, highlight it and press Shift + Enter or click here to inform us.
