ctf密码学学习笔记（1~5日更一次）

三体—夜航星

若非必要他人勿乱盖楼，有错误欢迎留言纠正。
楼主会持续更新楼层
2023.1.13
编码
base64：编码表字符串：大写字母A~Z，小写字母a~z，数字0~9以及"+"，"/"
长度为3的倍数，若不足会在后面有一两个等于号自动补齐。
base家族还有base16：编码表字符串：数字0~9 和 字母 A~F。位数刚好是4的倍数。base16其实就是hex编码。
base32：编码表字符串：大写字母A~Z 和 数字2~7。位数不齐会用＝补齐。
base100:表情编码。
base58，base91等等

uuencode，衍生至“unix to UNIX encoding”
UUENCODE将每三字节为单位进行编码，若不足3用0补齐。特征：特殊符号很多，若比赛遇到一大串奇怪符号（注意是符号）可考虑uuencode,jjencode,aaecode等。
xxencode：与base64相似，转换表不同，多了”-”，少了“/”，重点：若未满末尾用加号补齐。
其他编码
URL编码：特征：前面有百分号
jjencode和aaecode，特征：特殊符号很多，jjecode符号类似：$__()等
aaecode：常用网络表情，颜文字等等。

三体—夜航星

1.14
二，古典密码
古典密码属于密码学一个类型，大部分属于移项式或替换式密码。
凯撒密码
当前广为人知的加密方式之一，加密方式为按照固定数目向前或向后偏移成密文。
例如当偏移量为3时，A变成D，B变成E，以此类推。最大偏移量为25位。
因此通过穷举法可以轻易地进行破解。
维吉尼亚密码
维吉尼亚密码(Vigenère Cipher)是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的简单形式。在凯撒密码中，字母表中的每个字母都有一定的偏移，如偏移量为3时，A转换为了D、B转换为了E；而维吉尼亚密码由一些偏移量不同的凯撒密码组成。
其加密的过程非常简单,假设明文为:ATTACKATDAWN,密钥为LEMON。首先,循环密钥形成密钥流，使之与明文长度相同：
K=key1+key2+key3+⋯
即LEMONLEMONLE；然后根据每位秘钥对原文加密，如第1位密钥是L，对应第12个字母,那么偏移量则为12-1=11,对于第1位明文A,加密后的密文应为(A+11)mod26,即L;重复这个步骤,就可以得到密文LXFOPVEFRNHR。
一般，破解维吉尼亚密码有一些固定的套路：可以寻找密文中相同的连续字符串，则密钥长度一定为其间隔的因数，或者寻找“the”“Iam”之类的特殊单词。当然，现在已经有现成的工具可以使用( https://atomcated.github.io/Vigenere/), 遇到维吉尼亚密码可以直接使用在线工具求解。
固定替换
1.培根密码
培根密码(Bacon's Cipher)是由法兰西斯·培根发明的一种隐写术，加密时，明文中的每个字母都会转换成一组5个英文字母。
2，猪圈密码
以格子为基础的简单替代式密码。
其他古典密码：棋盘密码，密码棒密码，恩尼格码密码等等。
移位密码
1，栅栏密码。把明文分为n个一组，（n必须是明文的因数），然后把每组第1到n个字符依次连起来。如明文为abcdef,n=3，则先分为两组，每组三个字母：abc,def然后依次取字符，密文为adbecf。
2，曲路密码。
密钥：整个表格的曲路和路径。
古典密码总结：一般比赛不会把古典密码作为主考点，如果遇到不会可参考《ctf中那些脑洞大开的编码和加密》，以及使用百度。
三，分组密码
分组密码是将明文消息编码表示后的数字（简称明文数字）序列, 划分成长度为n的组（可看成长度为n的矢量）, 每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。

三体—夜航星

公钥密码（非对称加密）：最常见的就是rsa算法，也是每个学习crypto的人必备的知识，其最大特征是加密和解密不再使用相同的密钥，使用者会将一个密钥公开，而另一个密钥则是私人持有，以保证信息的机密性。

算法的安全性基于一个简单的事实：对于大素数p和q，计算p*q非常简单，但在已知n分解p*q很困难（要求pq足够大）。rsa算法常见攻击：因式分解。因为rsa算法生成过程中只用到了p,q,e，只要p,q被成功求出，可使用正常的方法算出私钥d，若p,q差值非常小，由于（）^2-pq=()^2即可通过暴力枚举p-q的值来分解p,q。

2，低加密指数小明文攻击。

3，共模攻击

4，广播攻击

5，低指数解密攻击（维纳攻击）

等等

三体—夜航星

rsa算法中n的特殊情况
φ(1) = 1， 1与任何数（包括自身）都构成互质关系

n是质数，则 φ(n) = n-1
因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

n是质数的某一个次方，即 n = p^kp
k
(p为质数，k为大于等于1整数)，则 \varphi(n)=\varphi(p^k)=p^k-p^{k-1}=p^k(1-p^{-1})φ(n)=φ(p
k
)=p
k
−p
k−1
=p
k
(1−p
−1
)
因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^{k-1}p
k−1
个，
即1×p、2×p、3×p、...、p^{k-1}p
k−1
×p，把它们去除，剩下的就是与n互质的数。
例 φ(8) = φ(2^32
3
) = 2^32
3
- 2^22
2
= 8 -4 = 4。