aiQG's Blog

Happy hacking. Happy developing.

aiQG's GitHub ⛓Links P
Other CTF Swift Developing&Reversing

密码学(加解密)

11 March 2019

by aiQG_

python pycryptodome 密码库官方文档

#换表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

几种加密模式:

  1. ECB (电子密码本模式) 将明文分成64位(8字节)一组, 分别xor相同的一个密码本(一般是密钥) 再==进入加密流程==.每组密文解密后xor相同的一个密码本得到明文. //相当于每组分别加密互不影响(解密反之即可)
  2. 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为最终明文
  3. 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为最终明文
  4. 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为最终明文
  5. 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的几个参数: 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)


改进的DES

AES的几个参数:

  1. 密钥128/192/256位(16/24/32字节)(对应AES-128/AES-192/AES-256)
  2. 明文16*n个字节
  3. 密文16*n个字节
  4. 偏移量16字节
  5. 加密模式CBC/ECB/CFB/OFB/CTR
  6. 填充方式(将明文填充至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


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首先需要这几样东西:

  1. 大素数p
  2. 大素数q
  3. 随机选取的整数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

安全性:离散对数问题

公私密钥对生成:

  1. 随机选取一个大素数p。要求p-1有大素数因子。
  2. 选取$Z_p^$ 的生成元 g。($Z_p^​$中的元素都可表示成 gn mod p)(也有直接生成随机数g的版本)
  3. 随机选取一个整数x(1<x<p-1)。
  4. 计算y $\equiv​$ gx(mod p) (离散对数问题) 得到公钥(y,g,p) 得到私钥(x,p)

加密明文m:

  1. 明文m的长度L < log2p ,否则应分块加密。
  2. 随机选取整数r。(1<r<p-1)
  3. 计算c $\equiv$ gr (mod p),c’ $\equiv​$ myr (mod p)
  4. 密文C = ( c , c’ )

解密密文C:

  1. 计算m $\equiv​$ (c’ / cx) (mod p)

也可以写成

  1. 计算cx的逆元(cx)-1
  2. 计算m $\equiv​$ (c’ * (cx)-1) (mod p)

用更短的密钥达到更高的安全性

安全性:离散对数问题

公私密钥对生成:

  1. 选择一个椭圆曲线E: $y^2 \equiv x^3 + ax + b (mod p)$ ,构造一个椭圆群(点集)$E_p(a,b)​$ (满足方程的a,b)
  2. 从$E_p(a,b)$ 中选择一个点$G=(x_0,y_0)$。G应该满足nG=O(无穷远点,相当于平行线的交点),其中n是满足条件的最小非常大素数。(这里nG=G+G+G… 点的相加,规则特有)
  3. 选择一个$n_b(n_b<n)$作为私钥,计算$P_B = n_BG$ ,则公钥为$(E,n,G,P_B)​$

加密明文m:

  1. 在$E_p(a,b)​$ 中选择一个点 $P_t = (x_t,y_t)$
  2. 在[1,n-1]内,随机选取一个整数k
  3. 计算$P_1 = (x_1,y_1) = kG$
  4. 根据公钥的$P_B$,计算$P_2 = (x_2,y_2) = kP_B​$
  5. 计算密文$C = mx_t + y_t$

得到密文{$kG,P_t+kP_B,C​$}

解密密文:

  1. 计算 $ P_t+kP_B-n_B(kG)=P_t+k(n_BG)-n_B(kG)=P_t$(点的加法)
  2. 计算 $m=(C-y_t)/x​$,得到明文m

CTFwiki


安全性:合数模下求解平方根

对同一密文,可能有多个明文。

密钥生成: 随机选取两个大素数p,q, 且$p\equiv3mod 4, q\equiv3mod 4​$ 则p,q为私钥,n=pq为公钥

加密明文m:

  1. 明文长度应<n,否则分块
  2. 计算$c=m^2 mod n​$

解密密文c:

  1. 计算四个方程 关于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}$
  2. 计算四个同余方程 (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的四个可能解(根据情况判断正解)

攻击:

  1. 大数分解。
  2. 选择密文攻击 假设拥有多个明文,则可计算$gcd(c_1+c_2,n)$(计算gcd是简单的) 可以得到p或q,从而分解n。
CTF

return

email:nrxxmzlrovqw4z3fgeztcncaozuxaltroexgg33n

桂ICP备18011144号-1 (点击访问安全的工信部网站)