А что, если бы 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.