浅谈 python在密码学的应用

前言

在ctf比赛中，编码解码有时候也会作为题目的一部分，我们要掌握一些常见编码的转化技巧。

在学习web刷题的过程中，有些题木还是需要一些密码学的知识的。可以用python中hashlib库来碰撞出一些md5或者sha加密。因此写这篇文章浅浅记录一下可能会用到的编码及 md5的一些碰撞姿势。

(1) hex

注：下面都是python 2环境。

hex是常用编码的方式之一。这一点非常容易理解，就是将信息转化为十六进制。也叫base16

使用python来对字符串进行 hex的变换，代码如下：

s = "flag";
print s.encode("hex");
#666c6167

通过encode可以对一个字符串进行编码，这里使用的是hex，结果非常容易理解，就是每个字符ASCII 码的十六进制。

在 s 被hex编码时，可以利用 int 函数直接将hex编码后的字符串转换为对应的十进制数字，这样就可以进行数学运算。

print int("a".encode("hex"),10)
print ord("a")
结果如下：
97
97

使用 hex 作为字符串到十进制数字的中转时一个不错的方法，如果需要逐字节进行运算，ord是更方便的选择。

num=8922333133093133239960474404255406756030333
print hex(num)
print hex(num)[2:-1]
print hex(num)[2:-1].decode("hex")
结果如下:
0x666c61677b746869735f69735f666c61677dL
666c61677b746869735f69735f666c61677d
flag{this_is_flag}

出来 串.encode("hex")之外，还可以用hex函数。

使用hex函数可以将十进制数字转化为十六进制字符串。并且会自动补“0x”。如果是long型，则会在末尾自动补“L”，所以对于第二个print，我们将“0x”和“L”去掉后，得到了原字符串的hex编码，最后decode即可。但是这并不适合所有的情况，一，因为不是所有的数字在hex之后会加上L；二是因为 decode必须保证hex编码的字符串是偶数位，如果是奇数位，就要在前面补“0”，所以我们可以用下面这个函数来处理这些问题：

def num2str(num):
    tmp=hex(num)[2:].replace("L","") 
    //首先对num数字进行了hex操作，然后去掉了前面的"0x", 然后replace过滤了最后的“L”
    
    if len(tmp) $2 ==0:
        return tmp.decode("hex")
    else:
        return ("0"+tmp).decode("hex")
    //根据字符串的长度判断是否需要在最前面补“0”
 
print num2str(num)

了解上面的即可应对绝大多数hex的情况，在很多题目中。hex并不会被作为考点，因为比较简单，但是将其用于数据处理是很常见的。上面是原理，至于具体解题过程中，可以用PyCrypto库进行更为方便的转换.

(2) urlencode

url 顾名思义，这种编码可用于浏览器和网站之间的数据交换，主要功能是解决一些特殊字符在传输过程中造成的问题。这种编码非常容易理解，在特殊字符hex的基础上，每个字符前置一个“%”即可。

在url编码和解码的过程中，只需要关注“%”的内容，每当遇到“%”的时候，连带“%”的三个字符对应着明文一个字符。

(3) 哈希

hash，一般翻译为“哈希”，也称之为杂凑函数。把任意长度的输入，通过哈希算法，变成固定长度的输出，该输出值就是哈希值。这种转换是一种压缩映射，即哈希值的空间常远小于输入的空间，不同的输入可能会哈希成相同的输出，所以不可能从哈希值来唯一确定输入值。即哈希是一种将任意长度的消息压缩到某一固定长度的消息的摘要的函数。

哈希的函数有很多，常见的有MD5，sha1，sha256.

1.哈希碰撞

哈希函数H需要满足如下性质：

1）H能够应用到任何大小的数据块上；

2）H能够生成大小固定的输出；

3）对于任意给定的x，H(x)的计算很简单，但从H(x)逆推x是不可能的。

在python中一般是使用hashlib库中的函数。如果想要将 hash 变成字符串的话，还需要配合hexdigest 使用，示例代码如下：

import hashlib
print(hashlib.sha256("flag").hexdigest())
print(hashlib.sha1("flag").hexdigest())
print(hashlib.md5("flag").hexdigest())
结果如下：
807d0fbcae7c4b20518d4d85664f6820aafdf936104122c5073e7744c46c4b87
112f3a99b283a4e1788dedd8e0e5d35375c33747
327a6c4304ad5938eaf0efb6cc3e53dc

在PPC模式的CTF赛题中，经常会出现一个 proof your work的过程，其目的是防止选手大量交互占用服务器资源，所以在所有的交互之前会让选手消耗自身资源来计算一些东西，一般是来求一个hash，使hash满足某些特定的条件.例如下面的：

要满足：
salt="123456"
hashlib.sha256(salt+x).hexdigest()[0:6]=="123456"
 
通过程序爆破：
salt="123456"
import string
import hashlib
for i1 in string.printable:
    for i2 in string.printable:
        for i3 in string.printable:
            for i4 in string.printable:
                if hashlib.sha256(salt+i1+i2+i3+i4).hexdigest()[0:6]=="123456":
                    print("find it: ",salt+i1+i2+i3+i4)
结果如下：
find it:  1234562Z9J
find it:  123456j@K@

书上还提到：

        据王小云院士提出的密码哈希函数的碰撞攻击理论，可以在一个任意的prefix后面加上不同的padding使其串的MD5一样。详情可以参考fastcoll，参考地址为 http://www.win.tue.nl/hashclash/

        sha1也出现了碰撞，不同内容但是sha1相同的文件可以参考https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

        在碰撞完的两个不同内容得到串后面加入相同的字符后，两者的哈希还是相同的，这也是一个常见考点。

创建一个文件 init.txt,里面随意写入

运行fastcoll 输入以下参数。 -p 是源文件 -o 是输出文件

fastcoll_v1.0.0.5.exe -p init.txt -o 1.txt 2.txt

运行，几秒钟以后 我们的文件就生成好了 md5(urlencode(1.txt))===md5(urlencode(2.txt))