极客时间

极客时间 - Web 漏洞挖掘实战 - 《加密失败：使用了加密算法也会被破解吗？》 笔记以及相关问题解答

最近学习极客时间专栏《Web 漏洞挖掘实战 - 《加密失败：使用了加密算法也会被破解吗？》》部分非常上头，就这部分的相关代码问题以及实现思路进行讲解；

在这部分最难得居然是使用SSH连接MiTuan的靶机.....

这里有些小Tips:

IP地址必须是公网地址，该信息可以在“靶机信息”部分可以获取到，不要使用host连接....

一定要等待状态检查完再连接，要么你会一直连接不上；

根目录下有一个extremelyHardRsa.zip 文件，需要用下方的命令执行：

>> unzip ./ex*

MiTuan靶机已经有Python3的运行环境了，你不需要重新配置Python3的运行环境了；

如果你想要将靶机的文件下载到本地方便进行研究，那么请使用scp命令，以下为MacOS运行环境的命令

(base) doheras@DoHerasdeMacBook-Pro ~ % scp -P 2222 root@[YOUR PUBLIC IP ADDRESS]:/root/extremelyHardRsa.zip ./

root@[YOUR PUBLIC IP ADDRESS]'s password:

extremelyHardRsa.zip 100% 3331 117.1KB/s 00:00

在这里我们必须搞清楚，怎么得到 n 和 e 的值；

通过Python - Crypto.PublicKey.RSA / base64 我们可以尝试复原以下怎么得到那一串长的数字；在这里需要Python的 PyCryptodome 进行支持，代码如下：

import rsa

from Crypto.PublicKey import RSA

from Crypto.Util import asn1

from base64 import b64decode

# 这部分内容是 pubkey.pem中读取的 PublicKey 部分

key_file = "MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY/Ix9fQO4LkCZUcGC85je4xBFgOe...tNIj3betive976mAm8iodJaoqktEkQUqAIf4MF0uYA+a7X6114YapRqFygHcPEkP0OHRGzM6yIiqWXMMLOSkCAQM="

keyDER = b64decode(key_file)

keyPub = RSA.importKey(keyDER)

print(keyPub)

# 这里得出输出的结果

RsaKey(n=72105952757214595949786607065724474654081829873524172138243589276727935457783182461...

1100841225147694940195217298482866496536787241, e=3)

对上边的代码解释一下：

b64decode 函数将文件pubkey.pem中的公钥(PublicKey)字符串(key_file)进行解码，解码后的数据为二进制数据；

RSA.importKey 函数将从文件中读取的公钥字符串(也就是解码之后的二进制字符串)转换成可以用的加密公钥，从而为接下来的暴力破解提供公钥计算 - n；

可以看到有一个e： 可以看到之前的指数信息，用于公钥加密的过程，我们知道暴力破解的原因就是这个e的数值过于低，反向暴力计算的复杂度较低，因此容易被破解；

那我们在这里破解RSA的目标是什么？-- 弄清楚这个很关键帮助我们理解代码的含义；

我们现在有：密文(y)，公钥(n)，明文的运算阶数(e)，我们需要知道明文是什么，那怎么实现逆向破解呢，我们需要知道k的是什么；

假设 密文(y)26, 公钥(n)33, 阶数(e)==3，需要破解的明文已知为5

5^3 (mod 33) == 26

那我们怎么知道 明文呢？两边的阶数同时乘以 1/3，之后下式：

明文 == (K*33 + 26)^(1/3)

其中：(K*33 + 26) 替代模运算;

我们需要判断的是：(K*33 + 26) 能不能是一个3阶的常数，即由一个常数的3阶；

而 gmpy2.iroot(A,B) 的作用就是判断常数A是不是一个B阶常数，如果是那么就会返回 True；

我们给一个例子来这个函数更直观： 27 是3的3阶数；

gmpy2.iroot(27,3)

# 返回结果为(mpz(3), True) - 是 3的3阶阶数

gmpy2.iroot(27,2)

# 返回结果为(mpz(5), False) - 不是一个2阶阶数

现在我们已经知道了怎么写破解代码的思路了；

Python 代码性能瓶颈分析：

运算速度可不可以提升，我们这段代码所有运行的问题是，因为做大量模运算，我们需要猜测K的值来构建一个3阶常数，因此需要大量的计算；

并行计算 - 如果不能提高运算速度，可以尝试多进程，即一个进程负责一段K值的计算，当出现第一个可分解3阶数时就结束；

在这里有一个问题，就是代码21行：mod_num = c_num % n - mod_num 与 c_num 的结果相同，因此这一行是是不是多余？我认为也不需要进行模运算；

这里留作大家思考；

改进思路：

好像不能提升运算速度，我们不能依赖Python高性能计算库 - Numpy / Numba 等；

由于Python GIL的限制，我们可以尝试使用多进程来加速猜测K值；

Python 改进代码如下：

import os, time

import gmpy2

import multiprocessing

def show_info():

n = 721059527572145959497866070657244746540818298735241721382435892767279354577831824618770455583435147844630635953460258329387406192598509097375098935299515255208445013180388186216473913754107215551156731413550416051385656895153798495423962750773689964815342291306243827028882267935999927349370340823239030087548468521168519725061290069094595524921012137038227208900579645041589141405674545883465785472925889948455146449614776287566375730215127615312001651111977914327170496695481547965108836595145998046638495232893568434202438172004892803105333017726958632541897741726563336871452837359564555756166187509015523771005760534037559648199915268764998183410394036820824721644946933656264441126738697663216138624571035323231711566263476403936148535644088575960271071967700560360448191493328793704136810376879662623765917690163480410089565377528947433177653458111431603202302962218312038109342064899388130688144810901340648989107010954279327738671710906115976561154622625847780945535284376248111949506936128229494332806622251145622565895781480383025403043645862516504771643210000415216199272423542871886181906457361118669629044165861299560814450960273479900717138570739601887771447529543568822851100841225147694940195217298482866496536787241

c_path = os.getcwd()

fname = c_path + "/flag.enc"

print(fname)

f = open(fname, 'rb')

c = f.read()

c_num = int.from_bytes(c, byteorder='big')

print('c_num:' + str(c_num))

mod_num = c_num % n

print('n = ' + str(n))

print('mod = ' + str(mod_num))

def run_attack(start_k, end_k, queue):

start_time = 0

c_time = 0

n = 721059527572145959497866070657244746540818298735241721382435892767279354577831824618770455583435147844630635953460258329387406192598509097375098935299515255208445013180388186216473913754107215551156731413550416051385656895153798495423962750773689964815342291306243827028882267935999927349370340823239030087548468521168519725061290069094595524921012137038227208900579645041589141405674545883465785472925889948455146449614776287566375730215127615312001651111977914327170496695481547965108836595145998046638495232893568434202438172004892803105333017726958632541897741726563336871452837359564555756166187509015523771005760534037559648199915268764998183410394036820824721644946933656264441126738697663216138624571035323231711566263476403936148535644088575960271071967700560360448191493328793704136810376879662623765917690163480410089565377528947433177653458111431603202302962218312038109342064899388130688144810901340648989107010954279327738671710906115976561154622625847780945535284376248111949506936128229494332806622251145622565895781480383025403043645862516504771643210000415216199272423542871886181906457361118669629044165861299560814450960273479900717138570739601887771447529543568822851100841225147694940195217298482866496536787241

k = start_k

c_path = os.getcwd()

fname = c_path + "/flag.enc"

f = open(fname, 'rb')

c = f.read()

c_num = int.from_bytes(c, byteorder='big')

mod_num = c_num % n

start_time = int(time.time())

# 定义Queue，如果Queue有内容就结束所有进程

while (queue.empty()):

c_time = int(time.time())

time_pass = c_time-start_time

if (c_time - start_time) == 10:

print("current k: " + str(k))

start_time = c_time

y = k * n + mod_num

root_num, status = gmpy2.iroot(y,3)

if status == 1:

print('correct k:%d'%k)

print('plain_text = ' + str(root_num))

queue.put("End")

break

else:

k = k + 1

if k > end_k:

print('start_k:%d k:%d end_k:%d'%(start_k, k, end_k))

break

if __name__ == '__main__':

# 我们不需要重复显示多与的内容了

show_info()

process_list = list()

# 引入一个queue来判断终止条件

queue = multiprocessing.Queue()

for i in range(0, 150000000, 10000000):

process_list.append(multiprocessing.Process(target=run_attack, args=(i, i+10000000, queue)))

for process in process_list:

process.start()

for process in process_list:

process.join()