密码学
古典密码学
替换加密
单表替换加密
- 一种映射(基本是一一映射)
- 破解方法
- 密钥空间过小时 爆破！
- 分析网站
- 凯撒密码
- 移位
- 攻击 爆破
- 空间变大的凯撒密码？凯撒密码还要什么自行车，直接爆破
- 若不改变距离，简化方法，将乱码移位到可见空间内
- Atbash Cipher
- A -> Z Z -> A B -> Y Y -> B …
- Polybius
- 棋盘加密，二次坐标系编码，类似于有序数对
- 仿射密码
- 真·单表替换
- 字频分析
多表替换加密
- Vigenere
- 其实是26个凯撒
- 卡西斯基试验
- 一定间隔的相同字符串被加密成相同密文
- 弗里德曼试验
- 凯撒加密不改变所有字母的概率平方和
- Vigenere 3D
- Playfair
- 定义
- 顺序相反的字母会泄露信息
置换加密
- 栅栏加密
其他算法
- Hill
- 矩阵运算
- 达成了 difussion，按块加密
- 培根加密
- 其实就是一种编码
- BarinFuck
- JSFUck生成地址
- 猪圈密码
- base64
- 最后几位可以做隐写
- base32
- base16
流加密
- OTP 完善保密性
- 熵
- 不确定性的量度
- 如英语26个字母，每个字母讯息量为 -ln(1/26) = 4.7
- 伪随机数生成器
- 线性同余生成器
- LFSR(线性反馈移位寄存器)
- 为本原多项式时长度才为 2^n
- 需要一个非线性函数来确保安全
- 维基百科
块加密
- 混淆与扩散
- 迭代分组密码
- Feistel
分组密码加密模式 Link
ECB
- 一个很大的缺点，由于是分组，可以直接改变顺序，如将银行账户的收款人与付款人互换
- ECB加密代码 引用地址
#include <STRING.H>
#define IN
#define OUT
//假设加密分组为4字节一组
/**************************************************************************
*功 能: 加密算法 (与Key异或)
*参 数: lpszData 当前明文分组数据
* lpszKey Key
* lpszDeData 加密后的结果
*
*返回值:
**************************************************************************/
void Encrypt(IN const char *lpszData, IN const char *lpszKey, OUT char *lpszEnData)
{
int i = 0;
for (i = 0; i < 4; i++)
{
lpszEnData[i] = lpszData[i] ^ lpszKey[i];
}
}
/**************************************************************************
*功 能: 解密算法 (再次异或还原明文)
*参 数: lpszData 当前密文分组数据
* lpszKey Key
* lpszDeData 解密后的结果
*
*返回值:
**************************************************************************/
void Decrypt(IN const char *lpszData, IN const char *lpszKey, OUT char *lpszDeData)
{
int i = 0;
for (i = 0; i < 4; i++)
{
lpszDeData[i] = lpszData[i] ^ lpszKey[i];
}
}
int main(int argc, char* argv[])
{
char *lpszData = "Hello World!";
char szEnData[16] = {0};
char szDeData[16] = {0};
char *lpszKey = "1234";
int i = 0;
printf("原始数据: %s\r\n", lpszData);
while (true)
{
if (strlen(lpszData + i) == 0)
{
break;
}
Encrypt(lpszData + i, lpszKey, szEnData + i);
i += 4;
}
printf("加密后数据: %s\r\n", szEnData);
i = 0;
while (true)
{
if (strlen(szEnData + i) == 0)
{
break;
}
Decrypt(szEnData + i, lpszKey, szDeData + i);
i += 4;
}
printf("解密后数据: %s\r\n", szDeData);
return 0;
}
CBC(PCBC)
- CBC模式优点：
- 不容易主动攻击, 安全性好于ECB, 适合传输长度长的报文, 是SSL、IPSec的标准
- CBC模式缺点：
- 不利于并行计算
- 误差传递
- 需要初始化向量IV
- CBC加密解密代码 引用地址
#include <STRING.H>
#define IN
#define OUT
//假设加密分组为4字节一组
/**************************************************************************
*功 能: 加密算法 (与Key异或)
*参 数: lpszData 当前明文分组数据
* lpszKey Key
* lpszDeData 加密后的结果
*
*返回值:
**************************************************************************/
void Encrypt(IN const char *lpszData, IN const char *lpszKey, OUT char *lpszEnData)
{
int i = 0;
for (i = 0; i < 4; i++)
{
lpszEnData[i] = lpszData[i] ^ lpszKey[i];
}
}
/**************************************************************************
*功 能: 解密算法 (再次异或还原明文)
*参 数: lpszData 当前密文分组数据
* lpszKey Key
* lpszDeData 解密后的结果
*
*返回值:
**************************************************************************/
void Decrypt(IN const char *lpszData, IN const char *lpszKey, OUT char *lpszDeData)
{
int i = 0;
for (i = 0; i < 4; i++)
{
lpszDeData[i] = lpszData[i] ^ lpszKey[i];
}
}
/**************************************************************************
*功 能: 与前一个密文分组进行xor
*参 数: lpszData 当前明文分组数据
* lpszPreEnData 前一个密文分组
* lpszDeData 保存异或后的数据
*
*返回值:
**************************************************************************/
void XorEnGroup(IN const char *lpszData, IN const char *lpszPreEnData, OUT char *lpszDeData)
{
int i = 0;
for (i = 0; i < 4; i++)
{
lpszDeData[i] = lpszData[i] ^ lpszPreEnData[i];
}
}
int main(int argc, char* argv[])
{
char szData[] = "Hello World!";
char szEnData[16] = {0};
char szDeData[16] = {0};
char *lpszKey = "1234";
int i = 0;
char szIV[] = "9999";
printf("原始数据: %s\r\n", szData);
while (true)
{
if (strlen(szData + i) == 0)
{
break;
}
//首先需要与前一个密文分组进行xor
XorEnGroup(szData + i, szIV, szData + i);
//更新密文分组
Encrypt(szData + i, lpszKey, szIV);
memcpy(szEnData + i, szIV, 4);
i += 4;
}
printf("加密后数据: %s\r\n", szEnData);
memcpy(szIV, "9999", 4);
i = 0;
char szPreEnData[8] = {0};
while (true)
{
if (strlen(szEnData + i) == 0)
{
break;
}
memcpy(szPreEnData, szEnData + i, 4);
//先解密
Decrypt(szEnData + i, lpszKey, szEnData + i);
//再与前一个密文分组进行xor
XorEnGroup(szData + i, szIV, szDeData + i);
memcpy(szIV, szPreEnData, 4);
i += 4;
}
printf("解密后数据: %s\r\n", szDeData);
return 0;
}
Padding Oracle Attack
- 分组的填充Padding
- 分组密码Block Cipher需要在加载前确保每个每组的长度都是分组长度的整数倍。一般情况下，明文的最后一个分组很有可能会出现长度不足分组的长度
- 这个时候，普遍的做法是在最后一个分组后填充一个固定的值，这个值的大小为填充的字节总数。即假如最后还差3个字符，则填充0×03。
- 在Padding Oracle Attack攻击中，攻击者输入的参数是IV+Cipher，我们要通过对IV的”穷举”来请求服务器端对我们指定的Cipher进行解密，并对返回的结果进行判断。
- 和盲注一样，这种二值逻辑的推理关键是要找到一个”区分点”，即能被攻击者用来区分这个的输入是否达到了目的(在这里就是寻找正确的IV)。比如在web应用中，如果Padding不正确，则应用程序很可能会返回500的错误(程序执行错误)；如果Padding正确，但解密出来的内容不正确，则可能会返回200的自定义错误(这只是业务上的规定)，所以，这种区别就可以成为一个二值逻辑的”注入点”。
- 攻击成立的两个重要假设前提:
- 攻击者能够获得密文（Ciphertext），以及附带在密文前面的IV（初始化向量）
- 攻击者能够触发密文的解密过程，且能够知道密文的解密结果
公钥算法
- 存在意义
- 公钥算法存在的意义
- 公开信道上的通信
- 更灵活的协议设计
Discrete log problem(离散对数)
- CDH
-The Computational Diffie-Hellman Problem (CDH)
- A problem related to DLP is named after Whit Diffie and Martin Hellman who devised a way of two parties agreeing on a secret key over a public channel without revealing it:
- Alice and Bob publicly agree on a cyclic group G and generator g.
- Alice chooses a random secret integer a and Bob chooses a random secret integer b.
- Alice computes ga and publicly sends this to Bob. Bob computes gb and publicly sends this to Alice.
- Alice and Bob both compute gab=(ga)b=(gb)a by raising what they received from the other party to power of their own secret integer.
- Now gab is a secret key that can be used for symmetric encryption and decryption by Alice and Bob. But someone listening in to the exchange has in their possession G, g, ga and gb. So secrecy of the key gab depends on this problem, called the Computational Diffie-Hellman Problem (CDH):
- Given G, g, ga and gb, find gab.
- CDH is clearly related to DLP, but which is harder? Well, if I can solve DLP then I can efficiently compute the secret integer a from ga and then find gab by raising gb to the power a in the same way Alice does, therefore solving CDH. So anyone who can solve DLP can also solve CDH, meaning DLP is at least as hard as CDH.
- A problem related to DLP is named after Whit Diffie and Martin Hellman who devised a way of two parties agreeing on a secret key over a public channel without revealing it:
- DDH
- This is another ‘discrete logarithm’ style problem used to prove indistinguishability properties. Say Alice and Bob perform the Diffie-Hellman key agreement protocol as above so that G, g, ga and gb are all public and gab is the shared secret key. Intuitively, the Decisional Diffie-Hellman Problem (DDH) asks whether an adversary can distinguish Alice and Bob’s secret key gab from a random group element of G. Formally:
- Given G, g, ga, gb and Tx such that T0 is a random element of G, T1=gab and x is chosen uniformly at random from {0,1}, find x.
- If an adversary can solve DDH (i.e. output the correct value of x with probability greater than 12), then G, g, ga and gb must leak some information about the secret key gab that distinguishes it from a random group element, even if it can’t be computed directly. What should be clear is that if the adversary can solve the computational Diffie-Hellman problem, then they can actually compute gab and hence trivially distinguish this element from a random group element, thereby solving the decisional Diffie-Hellman problem. So anyone who can solve CDH can also solve DDH, meaning CDH is at least as hard as DDH.
- This is another ‘discrete logarithm’ style problem used to prove indistinguishability properties. Say Alice and Bob perform the Diffie-Hellman key agreement protocol as above so that G, g, ga and gb are all public and gab is the shared secret key. Intuitively, the Decisional Diffie-Hellman Problem (DDH) asks whether an adversary can distinguish Alice and Bob’s secret key gab from a random group element of G. Formally:
- Integer Factorization
- (哥德巴赫猜想?)
- RSA problem
- 背景
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。 这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
- 密钥生成过程
- 第一步，随机选择两个不相等的质数p和q。 爱丽丝选择了61和53。(实际应用中，这两个质数越大，就越难破解。)
- 第二步，计算p和q的乘积n。 爱丽丝就把61和53相乘。 n = 61×53 = 3233 n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
- 第三步，计算n的欧拉函数φ(n)。爱丽丝算出φ(3233)等于60×52，即3120。
- 第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。爱丽丝就在1到3120之间，随机选择了17。(实际应用中，常常选择65537。)
- 第五步，计算e对于φ(n)的逆元d。ed ≡ 1 (mod φ(n)) 这个式子等价于 ed - 1 = kφ(n) 于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。 ex + φ(n)y = 1 已知 e=17, φ(n)=3120， 17x + 3120y = 1 这个方程可以用”扩展欧几里得算法”求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。
- 第六步，将n和e封装成公钥，n和d封装成私钥。 在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
- ElGamal加密算法
- side-channel attack(通过中国剩余定理加速来攻击)
RSA使用中常见的错误
- 过小的N
- 过小的d
- 过小的e
- 重复使用p，q
- 不恰当的pq特征
- 广播同一段明文的不同密文
- 不同的e共用n
- 提供 Padding Oracle
数学算法要求
- 费马小定理
- 快速幂算法
- 优化复杂度，平均复杂度为 1.5 * O(log(n))
int FastExp(int a, int b, int N)
{
int ans = 1;
a = a % N;
while(b) {
if(b % 2 == 1) {
ans = (ans * a) % N;
}
b = b / 2;
a = (a * a) % N;
}
return ans;
}
- 中国剩余定理？
int CRT(int a[],int m[],int n)
{
int M = 1;
int ans = 0;
for(int i = 1; i <= n; i++)
M *= m[i];
for(int i = 1; i <= n; i++)
{
int x, y;
int Mi = M / m[i];
extend_Euclid(Mi, m[i], x, y);
ans = (ans + Mi * x * a[i]) % M;
}
if(ans < 0) ans += M;
return ans;
Hash 函数
- 任意长度的消息转化为固定长度的哈希值
- 哈希扩展攻击()
椭圆曲线
- 知乎上看到了一个比较有趣的回答
- ECC y^2 = X^3 + a*x +b mod p
- 加法计算方式
P(x1, y1), Q(x2, y2), R(x3, y3)
P+Q=R
x3 = s^2 - x1 - x2 mod p
y3 = s*(x1 - x3) - y1 mod p
s:斜率
(y2 - y1)/(x2 - x1)
(3*x1^2 + a)/(2*y1) mod p
数字签名 & MAC
- 俗名，消息认证码？
密钥分发
- 线性秘密切割方案(不知道这是什么)
- 树形权限切割(不知道这是什么)
