CTF-密码学基础

概述

• 密码学(Cryptolopy)：是研究信息系统安全保密的科学

• 密码学研究的两个方向：

  • 密码编码学(Cryptography)：主要研究对信息进行编码，实现对信息的隐蔽
  • 密码分析学(Cryptanalytics)：主要研究加密信息的破译或消息的伪造

• 具体作用：

  • 提供保密性——密码技术可用于加解密
  • 用于鉴别——解决身份冒充的问题
    • 消息的接收者能够确认消息的来源，发送者不可能伪装成他人
    • 发送者也要能够确认接收者是否是自称的，接收者不可能伪装成他人
  • 提供完整性——解决篡改问题
    • 消息的接收者应该能够验证在传递过程中消息没有被修改
  • 抗抵赖
    • 发送者或接收者事后不可虚假地否认其发送或接收到的信息

古典密码

• 古典密码体制比较简单，容易破解，但了解它们的设计原理对理解、设计和分析现代密码体制十分重要
• 古典密码体制的核心思想：代替和置换
  • 代替：将明文中的每一个字符替换成另一个字符从而形成密文
  • 置换：重新排列明文消息中元素的位置而不改变元素本身从而形成密文

单表代换密码

• 明文中所有字母的加密都使用同一个映射关系：
  • 设$S_p$是明文字母空间，$S_c$是密文字母空间
  • 映射关系 $f:S_p->S_c$
  • 一般情况下，f是一一映射，即对相同的明文字母映射为相同的密文字母

棋盘密码

——这只是其中一个例子，这里棋盘排列是可以随意按加密人的想法进行排列

移位密码

当key=3时的移位密码，又称为“凯撒密码”

代换密码

仿射密码

• $k_1$与$k_2$是后续需要选定的值

多表代换密码

维吉尼亚密码

1. 先得到密钥字和对应的key
2. 明文按密钥字长度进行划分
3. 明文本身的数字＋密钥对应数字 mod 26得到对应的字母

由于引入的密钥字，因此同一个明文字母可以被映射为不同的密文字母

希尔密码

• 一种基于矩阵运算的加密算法

比较分析

• 单表代换密码体制中，明文中单字母出现的频率分布与密文中相同。这会带来密码的安全性问题，比如我们就可以通过频率分布来推测对应的字母是什么
• 在维吉尼亚密码和希尔密码体制中，将明文进行分组，对每组成组进行替换，使得同一个明文字母可以对应不同的密文，改变了单表代换密码中密文的唯一性

置换密码

• 在代换密码中，可以认为明文中各字母的相对顺序在加密成密文后仍保持不变，只是将它们用其他符号代替
• 置换密码是，通过改变明文中各元素的相对位置来进行加密，但元素本身的取值或内容形式不变

1. 按m个数，将明文分组，每组m个字符
2. 然后按照pai的位置放置，比如i放3号位，n放1号位，f放4号位，o放2号位，依次得到密文

密码学抽象概念

• 香农在论文《保密系统的通信理论》中提出的保密通信模型：

• 通信中的参与者

  • 发送者：在双方交互中合法的信息发送实体
  • 接收者：在双方交互中合法的信息接收实体
  • 分析者：破坏通信接收和发送双方正常安全通信的其他实体

• 明文和密文

  • 明文或消息(plaintext,message):
    • 尚未隐藏或未被加密的信息，用P或M表示
    • 明文的集合称为明文信息空间，用$S_p$表示
  • 密文(ciphertext):
    • 被加密(encryption)后的消息称为密文，用C表示
    • 所有密文构成密文信息空间，用$S_c$表示

• 密钥

  • 明文到密文的转换由一些特殊函数完成，控制这些函数的参数称为密钥key，用K表示
  • 一般是由用户事先选定的较短的字符或数字序列
  • 所有的密钥集合构成密钥空间，用$S_k$表示
  • 密钥空间中不相同密钥的个数称为密钥体制的密钥量，它是衡量密码体制安全性的一个重要指标
  • 一般情况下，密钥长度越大，密文越安全，但是加密速度越慢

• 加密

  • 在密钥K的作用下，把明文P从Sp对应到Sc的一种变换
    $$E_k:S_p->S_c$$

  • 则明文和密文的关系可表示为
    $$C=E_k(P)$$

• 解密

  • 加密变换的逆变换，把密文C从Sc对应到Sp
    $$\begin{gathered} D_k:S_c->S_p \\ P=D_k(C)=D_k(E_k(P)) \end{gathered}$$

  • 信息的保密性依赖于密钥K的保密性

• 密码体制：

  一个完整的密码体制(cryptosystem)由5部分组成

  • 明文信息空间Sp
  • 密文信息空间Sc
  • 密钥空间Sk
  • 加密变换族Ek
  • 解密变换族Dk

• 信道：

  从一个实体向另一个实体传递信息的通路

  • 安全信道：分析者没有能力对其上的信息进行阅读、删除、修改、添加的信道
  • 公共信道：分析者可以任意对其上的信息进行阅读、删除、修改、添加的信道

攻击手段

现代密码

• 古典密码：数据的安全基于算法的保密
• 现代密码：数据的安全基于密钥，算法公开
• 判断现代密码的标准：加密算法应建立在算法公开不影响明文和密钥安全的基础上

现代密码体制的一种分类方法

根据对明文的处理方法不同分为分组密码和流密码：

• 分组密码：将明文分成固定长度的组，用同一密钥和算法对每一组加密，输出也是固定长度的密文
• 流密码：每次加密一位或一字节的明文

散列哈希函数

MD算法家族

• MD5目前主要的用途：
  1. 一致性验证
  2. 数字签名
  3. 安全访问认证
  4. ……

SHA家族

• 与MD5类似
• 美国国家标准密码体系
• 主要应用领域：
  • 主要用于SSL\TTL等证书数字签名，用于可信第三方签发身份验证信息

SM家族

• 中国国家标准密码体系
• SM1是对称加密。其加密强度与AES相当。该算法不公开，调用该算法时，需要通过加密芯片的接口进行调用
• SM2是非对称加密，基于ECC
• SM3信息摘要，可以用MD5作为对比理解，算法已公开，校验结果为256位
• SM4无线局域网标准的分组数据算法。对称加密，密钥长度和分组长度均为128位

MD5算法详解

雪崩效应

• 虽然Hash函数的散列值空间远小于输入空间，但是哈希函数对于数据的改变具有极高的敏感性
• 1Bit数据的改变会造成散列值极大的改变

具体流程

1. 处理原文，对原文进行数据填充，使得消息长度对512取模得到448
   $$设消息长度为X，即满足Xmod512=448$$
   填充方法在原文后面进行填充，填充第一位为1，其余为0

2. 添加消息长度，在第一步结果之后再填充上原消息的长度，可用来进行存储的长度为64位（512-448）

   如果消息长度大于$2^{64}$，则只使用其低64位的值，即消息长度对2^64取模

   在此步骤进行完毕后，最终消息长度就是512的整数倍

3. 设置初始值，MD5的散列值长度位为128位，按每32位分成一组，一共4组

   这4组的结果是由4个初始值A/B/C/D经过多轮（轮数由输入的信息长度决定）不断演变得到

4. 循环运算(MD5算法核心)

   

   

   

对称加密算法

• 分组密码就是对称密码体制的一种形式，加解密的密钥相同

n是输出块的长度，m是输入块的长度

1. 若n>m，则为有数据扩展的分组密码
2. 若n<m，则为有数据压缩的分组密码
3. 若n=m，则为无数据扩展也无压缩的分组密码

DES密码

• 总体结构
  • 分组长度为64位
  • 循环次数位16
  • 密钥长度位64位（包括8位奇偶校验位）

• 总体描述
  • 初始置换IP，将64位明文分为两个部分
  • 之后进行16轮加密运算，称为函数f
  • 最后进行末尾置换$I{P}^{-1}$为初始置换的逆运算

非对称加密算法

RSA算法

先阐述几个概念

• 质数：只能被1和他本身整除的自然数
• 互质数：公约数只有1的两个数
• 同余运算：给定正整数m，如果两个整数a和b满足a-b能被m整除，即$(a-b)modm=0$，那么就称整数a与b对模m同余

加密示例

解密示例

密钥生成算法

CTF常见编码

BASE家族

Base16编码之后的特征：还有字符A~F还有数字0~9

Base32编码之后的特征：有数字A~Z，还有数字2~7，还有＝号

URL编码

• URL编码是一种浏览器用来打包表单输入的格式

• URL编码就是一个字符ASCII码的十六进制。需要前面加上%

  比如”\“，它的ASCII码是92，92的十六进制是5c，所以”\“的URL编码是%5c

• URL编码的特征就是”%“加上2位16进制数

Unicode编码

• Unicode是计算机科学领域里的一项业界标准，包括字符集、编码方案等
• 你好 ——>\u4f60\u597d
• Unicode编码的特征就是”\u“加上4位16进制数

莫斯密码

• 具体内容可以查看隐写术中涉及的音频隐写部分

  CTF-隐写术-CSDN博客

CTF密码学实战

编码题解题思路

• 一般没有密钥的就是编码题
• 编码题对密文的特征进行分析
• 通常不会作为单独的考题出现，一般是出现在其中的某一步

因为密文中有大写字母，小写字母，因此第一反应可以通过Base64进行解码，最后得到flag

根据题目回旋13的提示，移位算法rot13解码，即可得到答案

RSA算法解题

• 压缩包文件有两个，一个flag.enc是密文的二进制文件，一个是pubkey.pem是公钥
• 通过公钥来获取私钥，来解密这个加密之后的二进制文件

1. 私钥第一步要解决的是，如何求到p和q

   我们先用openssl工具把公钥文件进行解析

   

2. 获取到了16进制的相乘的值，我们可以利用python等工具，将十进制转换出来

   

3. 获取到十进制数后，我们利用工具yafu来寻找p和q，这一步一般需要比较长的时间

   GitHub - bbuhrow/yafu: Automated integer factorization

   .\yafu-Win32.exe factor(放入十进制数)
   

   

4. 然后我们知道了p,q,n,e 现在求解d——可以在网上找，也可以自己写脚本文件

   import gmpy2
   import rsa
   p=
   q=
   n=相乘的大n数
   e=65537
   d=int(gmpy2.invert(e,(p-1)*(q-1)))
   privatekey=rsa.PrivateKey(n,e,d,p,q)
   with open("密文二进制文件地址","rb") as f:print(rsa.decrypt(f.read(),privatekey).decode())
   

未知编码方式解题思路

1. 使用搜索引擎搜索部分密文，可能能够搜索到编码方式（抽象）