writeup
cryptopals解密之旅 (一)
2020-05-29 10:55

前言

本系列文章将带来cryptocals 这套密码学挑战的write-up.不同于通过上课或者看书的方式学习密码学,这些题目来自于现在生活中一些软件系统和密码构造中的缺陷。

本系列每一个题的wp基本是采用如下结构:题目解释、相关知识点讲解、代码实现及解释,运行测试。代码均采用python3实现,代码实现部分是参考国外大佬ricpacca的,结合自己的理解及成文需要进行部分修改。

第一套一共有八关。

0x01 先来看第一关

1.1

cryptopals解密之旅1-1257.png

第一题

cryptopals解密之旅1-1263.png

题目要求我们将十六进制转为base64, 将十六进制4927…,base64编码成SSdt…

我们知道,Base64是网络上最常见的用于传输 8bit 的编码方式之一,Base64就是一种基于64个可打印字符来表示二进制数据的方法

在一些网络传送渠道,有时候有些的字节字符不能被支持.比如图片的二进制流的每个字节不可能全部是可见字符,这种情况下传送不了.而Base64的机制就能很好解决这种问题,它不改变原来的协议,在原来的基础做一种扩展,基于64个可打印字符来表示二进制.

再者,有时候我们通过记事本去打开一些图片或者应用程序,会得到一大堆看不懂的乱码,因为二进制文件里面有很多无法显示和打印的字符.所以如果要让记事本能够处理二进制数据,就可以使用Base64来进行转码,将不可见的转成可见的.

我们先来学习base64编码的原理

我们拿到一串字符,比如 abcdef.

1.按ASCII码编码.

2.将字符串按字节数分开,每三个字节为一组. 3 byte * 8 bit === 24bit.

3.在这组中,将24位数据按照每6位为一组,再次分成4组.

4.然后将这四组的6位数的高位各补两个0,将其转为十进制数.

5.进行查表,得到对应的字符,就是对应的Base64转化的字符.

cryptopals解密之旅1-1811.png

 

一个简单的例子如下:

cryptopals解密之旅1-1825.png

那么问题来了,如果原始数据的位数不是3的整数倍怎么办?如果最后剩下两个输入数据,在编码结果后加1个“=”;如果最后剩下一个输入数据,编码结果后加2个“=”;如果没有剩下任何数据,就什么都不要加,这样才可以保证资料还原的正确性。或者说分成6位一组后,最后一组没有到6位怎么办?此时需要填充一个=或者两个=。具体情况我们会在代码实现部分分析。

可见,编码后的数据比原始数据略长,为原来的4/3

记下来是代码的实现

定义Status类,一个16进制占4位,因为是以6位为一组,所以读取1个16进制字符后的转换状态的可能情况有三种

cryptopals解密之旅1-11092.png

如果是新的一组,将一个16进制字符的4位放入,那么还需要两个bit进行填充。接着将status设置为填充2位的情况

cryptopals解密之旅1-11152.png

如果需要填充2位,则填充后该组就完整了,就可以通过编码表进行对应编码了,编码后将其附加到编码后字符串末尾。接着将status设置为填充4位的情况

cryptopals解密之旅1-11227.png

如果需要填充4位,则填充后该组就完整了,就可以通过编码表进行对应编码了,编码后将其附加到编码后字符串末尾。接着将status设置为处理新一组的情况

cryptopals解密之旅1-11303.png

如果6位一组的字符串还需要填充2个bit话,我们就在最后一组加上2个0,这种情况下在最后转为base64的时候需要填充=

以给aa进行base编码为例:

aa的二进制为:01100001 01100001

分成6位一组:011000 010110 000100(红色的是补上的0)

转为10进制:24 22 4

查表,转为base64,为:Y W E =(=是填充上的)

代码如下

cryptopals解密之旅1-11499.png

如果6位一组的字符串还需要填充4个bit话,我们就在最后一组加上4个0,这种情况下在最后转为base64的时候需要填充==

举个例子,以给a进行base64编码为例

cryptopals解密之旅1-11584.png

代码如下

cryptopals解密之旅1-11591.png

完整的代码如下以及执行结果如下:

cryptopals解密之旅1-11611.png

打印出了相应的信息

Python assert(断言)用于判断一个表达式,在表达式条件为 false 的时候触发异常。我们可以用断言来测试

cryptopals解密之旅1-11683.png

完整代码如下

cryptopals解密之旅1-11692.png

 运行如图

cryptopals解密之旅1-11699.png

没有错误。

如果将hex_to_base64的字符串的第一个4删去,再次执行

cryptopals解密之旅1-11740.png

则会报AssertionError

说明我们成功手动实现了base64编码的算法

实验推荐:Base64编码原理与应用(Base64是网络上最常见的用于传输8Bit字节码的编码方式之一,Base64就是一种基于64个可打印字符来表示二进制数据的方法)

0x02第二关

cryptopals解密之旅1-11793.png

要求写一个函数对两个16进制字符串进行异或,这个很简单,直接看代码

cryptopals解密之旅1-11830.png

用int函数将输入的两个16进制字符串转为整型

关于int函数的说明如下

cryptopals解密之旅1-11869.png

然后进行异或,再将结果转为16进制。测试如下

cryptopals解密之旅1-11894.png

直接返回函数的结果会看到结果前还有0x,所以需要使用[2:]进行截取

完整代码及测试如下

cryptopals解密之旅1-11941.png

打印出了异或的结果,用断言测试如下

cryptopals解密之旅1-11961.png

0x03第三关

cryptopals解密之旅1-11973.png

给定一个十六进制字符串hexString,它是某个字符串与一个单字符key异或进行加密之后得到的结果。现在已知hexString,我们需要找到key,来解密字符串。

这里给了个提示,为了验证解密结果的正确,我们可以查看解密后的文本的字符频率,来对解密结果进行评估。如果为正常的英文文本,那么它的字符频率应该尽可能的大,选择其中得分最高的key,即有很大概率为正确的key

这个原理不难理解,出现频率最高的是””(空格),第二高是’e’,如果一段文本,将其每个字符按照频率表的数值相加,得分越高,则越有可能是正常的文本。

举个不太恰当的例子(因为频率表是基于海量的正常文本得出的,而我这里只是用简单的一句话)。比如一段密码,解密后有两个结果:

I am fine

A bc defg

第一个结果的分值应为:0.06+0.07+0.02+0.02+0.06+0.06+0.10=0.39

第二个结果的分值应为:0.07+0.01+0.02+0.03+0.10+0.02+0.02=0.18

则第一个结果应该才是正确解密的结果。

接下来的代码就是根据这个原理写出来的。

字符频率表

cryptopals解密之旅1-12466.png

计算输入文本的分值:该分值是所有在输入字符串中出现的字符对应在字符频率表中的频率相加

cryptopals解密之旅1-12511.png

对字符串中的每个字符与key进行异或

cryptopals解密之旅1-12532.png

key_value是256个字符中的一个,暴力尝试,用每个可能的字节对密码异或解密,计算得出的明文的分数,得分越高,越可能是正确的密文,所用的key就是题目要求我们找出来的key

cryptopals解密之旅1-12624.png

打印出解密后的明文,分数及key

cryptopals解密之旅1-12643.png

完整的代码及执行结果如下所示

cryptopals解密之旅1-12660.png

成功解密了字符串,使用断言测试如下

cryptopals解密之旅1-12680.png

0x04第四个题目

cryptopals解密之旅1-12694.png

给了一个文件,该文件内容是和某个字符异或得到的,我们需要找到明文和key文件内容如下

cryptopals解密之旅1-12740.png

这里在编码时可以用到我们上个实验写过的函数,就不用重复造轮子了

cryptopals解密之旅1-12774.png

对密文的每一个字符都进行暴力尝试,与所有可能的key取值进行异或,最后组成明文,然后计算分数,返回分数最高的结果

cryptopals解密之旅1-12833.png

完整代码及运行结果如下所示

cryptopals解密之旅1-12849.png

拿到了明文和key,使用断言测试如下

cryptopals解密之旅1-12870.png

参考及实验推荐

1. https://cryptopals.com/sets/1

2. https://github.com/ricpacca/cryptopals

摩尔斯电码和栅栏密码 ( 摩尔斯电码(又译为摩斯密码,Morse code)是一种时通时断的信号代码,通过不同的排列顺序来表达不同的英文字母、数字和标点符号)


上一篇:Zer0pts CTF 2020的web赛后记录+复现环境
下一篇:cryptopals解密之旅 (二)
版权所有 合天智汇信息技术有限公司 2013-2020 湘ICP备14001562号-6
Copyright © 2013-2020 Heetian Corporation, All rights reserved
4006-123-731