密码学(加解密)
- base64/32
Base64: 一个字符8bit, 将所有字符比特按照每3个字符分成一组(每组3*8=24bit), 再将每组(24bit) 按照6bit一个字符分成4个字符(4*6=24bit) (不满一组用0填充)(全0 为’=’) 总的来说就是将3个字节编码为4个字符
#换表base64/32/58可以用string.maketrans(charset, origin)设置字符映射关系
#换表flag
flag = 'a(>sb(93b3-s^!;;'
#原表
origin = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="
#变表
charset = "!:#$%&()+-*/`~_[]{}?<>,.@^abcdefghijklmnopqrstuvwxyz0123456789\\';"
#设置映射关系 charset到 origin
import string
t = string.maketrans(charset, origin)
#flag换成原表b64
flag = flag.translate(t)
#aGVsbG93b3JsZA==
#解base64
import base64 #import base58
flag = base64.b64decode(flag)
#helloworld
几种加密模式:
- ECB (电子密码本模式) 将明文分成64位(8字节)一组, 分别xor相同的一个密码本(一般是密钥) 再==进入加密流程==.每组密文解密后xor相同的一个密码本得到明文. //相当于每组分别加密互不影响(解密反之即可)
- CBC (密码分组链接模式) 加密: 先将明文分成64位一组(假设分成了n组), 第一组xor初始向量iv. ==进入加密流程==得到密文C1. 将得到的密文C1与第二组明文xor后==进入加密流程==得到密文C2. 将得到的密文C2与第三组…… ……明文xor后==进入加密流程==得到密文Cn C1C2…Cn即为最终得到的密文 解密: 第一块密文==进入解密流程==后xor初始向量iv得到P1 第二块密文==进入解密流程==后xor第一块密文得到P2 第三块密文==进入解密流程==后xor第二块密文得到P3 …… 第n块密文==进入解密流程==后xor第n-1块密文得到Pn P1P2P3…Pn为最终明文
- CFB (密码反馈模式)(无须解密函数) 加密: 先用初始化向量iv初始化移位寄存器然后寄存器==进入加密流程== 选出寄存器的前s位(s一般是8的倍数) 与明文的第一块xor(这里可以猜测s与明文的分块有关) 得到C1 寄存器左移s位, 空出的位用C1的高s位填充, 然后==进入加密流程== 选出寄存器的前s位 与明文的第二块xor, 得到C2 寄存器左移s位, 空出的位用C2的高s位填充,然后 ==进入加密流程== 选出寄存器的前s位 与明文的第三块xor…… ……空出的位用Cn的高s位填充,然后 ==进入加密流程== C1C2…Cn为最终密文 解密: 先用初始化向量iv初始化移位寄存器然后寄存器==进入加密流程== 选出寄存器的前s位 与密文第一块xor 得到P1 寄存器左移s位, 空出的位用第一块密文的高s位填充, 然后==进入加密流程== 选出寄存器的前s位 与密文的第二块xor, 得到P2 寄存器左移s位, 空出的位用第二块密文的高s位填充, 然后==进入加密流程== 选出寄存器的前s位 与密文的第三块xor…… ……空出的位用第n块密文的高s位填充, 然后==进入加密流程== P1P2…Pn为最终明文
- OFB (输出反馈模式) (与CFB相比, 用来填充的东西由密文变成了加密后的移位寄存器) 加密: 先用初始化向量iv初始化移位寄存器然后寄存器==进入加密流程== 选出寄存器的前s位与明文的第一块xor得到C1 寄存器左移s位, 空出的位用原寄存器的前s位填充, 然后==进入加密流程== 选出寄存器的前s位 与明文的第二块xor, 得到C2 寄存器左移s位, 空出的位用原寄存器的前s位填充, 然后 ==进入加密流程== 选出寄存器的前s位 与明文的第三块xor…… ……空出的位用原寄存器的前s位填充, 然后 ==进入加密流程== C1C2…Cn为最终密文 解密: 先用初始化向量iv初始化移位寄存器然后寄存器==进入加密流程== 选出寄存器的前s位 与密文第一块xor 得到P1 寄存器左移s位, 空出的位用原寄存器的前s位填充, 然后==进入加密流程== 选出寄存器的前s位 与密文的第二块xor, 得到P2 寄存器左移s位, 空出的位用原寄存器的前s位填充, 然后==进入加密流程== 选出寄存器的前s位 与密文的第三块xor…… ……空出的位用原寄存器的前s位填充, 然后==进入加密流程== P1P2…Pn为最终明文
- CTR (计数器模式) (计数器可用伪随机数实现) 加密: 计数器1==进入加密流程==, 与P1 xor 得到 C1 计数器2==进入加密流程==, 与P2 xor 得到 C2 计数器3==进入加密流程==, 与P3 xor 得到 C3 …… 计数器n==进入加密流程==, 与Pn xor 得到 Cn C1C2…Cn为最终密文 解密: 计数器1==进入加密流程==, 与C1 xor 得到 P1 计数器2==进入加密流程==, 与C2 xor 得到 P2 … 计数器n==进入加密流程==, 与Cn xor 得到 Pn P1P2…Pn为最终明文
S盒用于代换(狸猫换太子) P盒用于置换(换位置搓麻将)
- DES
DES的几个参数: 1.密钥64位(8个字节)(通过置换选择选出其中56位使用) 2.明文64位 3.密文64位 4.偏移量8字节(根据加密模式) 5.加密模式CBC/ECB/CFB/OFB/CTR 6.填充方式(将明文填充至8位对齐)
//明文先通过置换IP打乱(不一定) //一共16轮重复加密, 每轮两个xor、1个S盒(8个小S盒 6 * 8输入, 4 * 8输出)、1个P盒、1个扩展置换32位换成48位 //最后通过置换IP-1得到密文(不一定)
import base64
flag = '+p40NHJss7ntjSP5Y9wcKQ=='
flag = base64.b64decode(flag)
from Crypto.Cipher import DES
vi = '12345678'
key = 'abcdefgh'
cryptor=DES.new(key, DES.MODE_CBC, vi)
flag = cryptor.decrypt(flag)
print flag
#helloworld
密码对象是有状态的:
c.decrypt(a) + c.decrypt(b) <=> c.decrypt(a+b)
(https://www.dlitz.net/software/pycrypto/api/current/Crypto.Cipher.blockalgo.BlockAlgo-class.html#encrypt)
由于DES子密钥的运算规则(前后两部分循环左移),存在弱密钥。如果经过子密钥生成后得到的十六个子密钥相同$k_1=k_2=…=k_{16}$,则存在$E_k(E_k(m)) == m$ 与 $D_k(D_k(m)) == m$
//三重DES: //1. DES-EEE3模式(3key 3encode) //2. DES-EDE3模式(3key 2encod 1decod) //3. DES-EEE2模式(2key 3encod) //4. DES-EDE2模式(2key 2encode 1decode)
- AES
改进的DES
AES的几个参数:
- 密钥128/192/256位(16/24/32字节)(对应AES-128/AES-192/AES-256)
- 明文16*n个字节
- 密文16*n个字节
- 偏移量16字节
- 加密模式CBC/ECB/CFB/OFB/CTR
- 填充方式(将明文填充至16字节对齐)
//AES是面向字(每次选取两个字节)的加密变换(包括密钥与明文) //加密轮数不同16字节的密钥对应10轮(AES-128), 24字节对应12轮(AES-192), 32字节对应14轮(AES-256)
import base64
flag = 'ZoEkXmecjna+IeJ/lAWZ1g=='
flag = base64.b64decode(flag)
from Crypto.Cipher import AES
vi = '0123456789abcdef'
key = '0123456789ABCDEF'
cryptor=AES.new(key, AES.MODE_CBC, vi)
flag = cryptor.decrypt(flag)
print flag
#helloworld
- RC4 参数:
- 种子密钥(0~255共256位), 若密钥不足256位, 则将输入的密钥不断重复直到256位
- 通过对密钥的选取得到加密的密钥与明文xor
import base64
flag = '4BrK7KwMu1VYmw=='
flag = base64.b64decode(flag)
from Crypto.Cipher import ARC4
key = '0000000000000000000000000000000'
cryptor = ARC4.new(key)
flag = cryptor.decrypt(flag)
print flag
#helloworld
- RSA
RSA的安全性是建立在大数分解的困难性上的。 要构建一个RSA首先需要这几样东西:
- 大素数p
- 大素数q
- 随机选取的整数e( e满足1<e<(p-1)(q-1), 且e与(p-1)(q-1) 互素) //这里(p-1)(q-1) == $\varphi$(p * q)
然后计算 私钥(d,n):d $\equiv$ e -1(mod $\varphi$(p * q)) n = p * q //d也可以通过解 (d * e) mod [(p-1)(q-1)] == 1 得到
公钥(e,n):e = e n = p * q
计算后将两个大素数p,q销毁
//私钥相当于钥匙,用来解密 //公钥相当于锁🔒,用来加密 //加密前必须将明文数字化 //解密后再将数字转为明文
加密过程: 利用公钥(e,n),明文m 得到密文c = me mod n
解密过程: 利用私钥(d,n),密文c 得到明文m = cd mod n
攻击: 1.(暴力)通过分解公钥中的n,得到p,q,得到私钥,解密密文 RSA-ATTACK
2.由d,n,e计算出p,q
3.通过泄露的部分p或q和n得到私钥 理论支持:https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/lattice/lattice-reduction/
n = #p*q
p_ = #完整的p(包括泄露部分和未泄露部分)
pbits = 2048 #原p的位数
kbits = 900 #没泄露的位数
pbar = p_fake & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print x0 + pbar #计算出来的p
- ElGamal
安全性:离散对数问题
公私密钥对生成:
- 随机选取一个大素数p。要求p-1有大素数因子。
- 选取$Z_p^*$ 的生成元 g。($Z_p^*$中的元素都可表示成 gn mod p)(也有直接生成随机数g的版本)
- 随机选取一个整数x(1<x<p-1)。
- 计算y $\equiv$ gx(mod p) (离散对数问题) 得到公钥(y,g,p) 得到私钥(x,p)
加密明文m: 0. 明文m的长度L < log2p ,否则应分块加密。
- 随机选取整数r。(1<r<p-1)
- 计算c $\equiv$ gr (mod p),c’ $\equiv$ myr (mod p)
- 密文C = ( c , c’ )
解密密文C:
- 计算m $\equiv$ (c’ / cx) (mod p)
也可以写成
- 计算cx的逆元(cx)-1
- 计算m $\equiv$ (c’ * (cx)-1) (mod p)
- 椭圆曲线(ECC)
用更短的密钥达到更高的安全性
安全性:离散对数问题
公私密钥对生成:
- 选择一个椭圆曲线E: $y^2 \equiv x^3 + ax + b (mod p)$ ,构造一个椭圆群(点集)$E_p(a,b)$ (满足方程的a,b)
- 从$E_p(a,b)$ 中选择一个点$G=(x_0,y_0)$。G应该满足nG=O(无穷远点,相当于平行线的交点),其中n是满足条件的最小非常大素数。(这里nG=G+G+G… 点的相加,规则特有)
- 选择一个$n_b(n_b<n)$作为私钥,计算$P_B = n_BG$ ,则公钥为$(E,n,G,P_B)$
加密明文m:
- 在$E_p(a,b)$ 中选择一个点 $P_t = (x_t,y_t)$
- 在[1,n-1]内,随机选取一个整数k
- 计算$P_1 = (x_1,y_1) = kG$
- 根据公钥的$P_B$,计算$P_2 = (x_2,y_2) = kP_B$
- 计算密文$C = mx_t + y_t$
得到密文{$kG,P_t+kP_B,C$}
解密密文:
- 计算 $ P_t+kP_B-n_B(kG)=P_t+k(n_BG)-n_B(kG)=P_t$(点的加法)
- 计算 $m=(C-y_t)/x$,得到明文m
- Rabin
安全性:合数模下求解平方根
对同一密文,可能有多个明文。
密钥生成: 随机选取两个大素数p,q, 且$p\equiv3mod 4, q\equiv3mod 4$ 则p,q为私钥,n=pq为公钥
加密明文m: 0. 明文长度应<n,否则分块
- 计算$c=m^2 mod n$
解密密文c:
- 计算四个方程 关于p: $\begin{cases} m_1 = c^{(p+1)/4} mod p \ m_2 = (p-c^{(p+1)/4}) mod p \end{cases}$ 关于q: $\begin{cases} m_3 = c^{(q+1)/4} mod q \ m_4 = (q-c^{(q+1)/4}) mod q \end{cases}$
- 计算四个同余方程 (1) $\begin{cases} m \equiv m_1 (mod p)\ m \equiv m_3 (mod p) \end{cases}$ (2) $\begin{cases} m \equiv m_1 (mod p)\ m \equiv m_4 (mod p) \end{cases}$ (3) $\begin{cases} m \equiv m_2 (mod p)\ m \equiv m_3 (mod p) \end{cases}$ (4) $\begin{cases} m \equiv m_2 (mod p)\ m \equiv m_4 (mod p) \end{cases}$ 得到m的四个可能解(根据情况判断正解)
攻击:
- 大数分解。
- 选择密文攻击 假设拥有多个明文,则可计算$gcd(c_1+c_2,n)$(计算gcd是简单的) 可以得到p或q,从而分解n。