2020-10-21

常见加密算法

古典加密算法/编码算法

凯撒加密

也叫移位密码

若a–1,b–2,c–3…，则对于明文中任意一个字符$\alpha$，有$\alpha=(\alpha+\beta)%26$，其中$\beta$是密钥

破解方式：穷举密钥，可以配合统计字母频率

仿射密码

quotaed-printable密码

$e(x)=ax+b$，其中$a$和字母数$m$互素

$d(x)=a^{-1}(x-b),a^{-1}a\equiv1\mod m$

凯撒加密升级版

单表代换密码：每一个字符被替换成不同的字符，偏移量不再像凯撒密码一样固定

破解方式：统计字母频率，然后把频率高的替换成实际情况下频率高的

维吉尼亚密码

参考：维吉尼亚密码的原理及破解 - ZCyu的文章 - 知乎
https://zhuanlan.zhihu.com/p/111611977

假设明文为$P=p_1p_2…p_n$，密钥为$K=k_1k_2…k_m$，密文为$C=c_1c_2…c_n$

则$c_i=(p_i+k_{i\mod m})\mod 26\p_i=(c_i-k_{i\mod m})\mod 26$

例子：明文ILOVEMIMAXUE,密钥 AWSL，密文 IHGGEIAXATMP

破解方式

由于维吉尼亚密码每一个字母的加密还与它在明文中的位置有关，所以简单的字母频率分析不起作用

Kasiski测试

由于密钥循环重复，知道密钥长度m后破解难度就会降低。使用Kasiski测试，将相同的字母组找出来，然后求距离差的最大公约数，猜测m

因为给定长度为m的密钥周期性地加密，当铭文中有两个相同的字母组(长度大于3)，在明文序列中相隔字符数为m地倍数时，加密出的密文必定相同。反过来，若密文中出现相同的组合，则对应的明文字母组未必相同，但是相同的可能性极大

重合指数法

设一门语言由n个字母组成，每个字母发生的概率为$P_i$，则重合指数指其中两个随机元素相同的概率的和$CI=\sum\limits_{i=1}^nP_i^2$

完全随机的英文文本$CI=26\left(\frac{1}{26}\right)^2=0.0385$，有意义的英文文本$CI=0.065$

实际使用的是$CI$的估计值$CI’$，$L$为密文长度，$f_i$为第$i$个字母发生的次数$CI’=\sum\limits_{i=1}^n\frac{f_i}L\cdot\frac{f_i-1}{L-1}$

如果密文重合指数较低，就是多表代换密码，如果结果接近0.065，则猜测正确

测试m=1,2,3,…

可以把明文分成m个一组，假设密钥长度为m，则每组的相同位置的密钥相同，可以基于这个特点检测重合指数，判断密钥长度

Chi测试(应该是卡方检验吧，测试统计样本和理论值的偏移程度)

用于确定密钥内容

某种语言由$n$个字母组成，$p_i$为字母$i$在维吉尼亚密文分布中发生的概率$q_i$表示在正常英文文本中发生的概率，拟重合指数定义为

$\chi=\sum\limits_{i=1}^np_iq_i$

对于一个移位密码

统计每个字母的频数$f_0,f_1,…,f_{26}$
令密文长度为$n’=\frac{n}m$，则字母的频率分布$p_i=\frac{f_i}{n’}$
通常文本概率分布$q_0,q_1,…,q_{26}$
对于每一列进行移位，得到每一位对应的偏移量i，得到$P_i=p_{26-i},…,p_{25},p_0,p_1,…,p_{25-i}$
对分布$P_i$和$Q$进行相关卷积计算$C(P_i,Q)=\sum\limits_{j=0}^26P_{(i+j)\mod 26\cdot q_j}$
得到最大相关值即为偏移量的估计值

hash算法

md5

填充

在消息后面先填充一个1，再填充0，直到消息长度mod 512=448，之后再将消息长度的低64位填充到消息结尾

定义几个运算

F(x,y,z)=(x&y)|(~x&z)

G(x,y,z)=(x&z)|(y&~z)

H(x,y,z)=x^y^z

I(x,y,z)=y^(x|~z)

ROL32(x,i) 左移32位

填充后的消息以512为一个分组，每个分组可以分成16个32位子分组$W_j(0<j<15)$

FF(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(F(b,c,d)+M_j+t_i),s)

GG(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(G(b,c,d)+M_j+t_i),s)

HH(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(H(b,c,d)+M_j+t_i),s)

II(a,b,c,d,M_j,s,t_i): a=b+ROL32(a+(I(b,c,d)+M_j+t_i),s)

定义初始化向量

A=0x01234567

B=0x89abcdef

C=0xfedcba98

D=0x76543210

对于每一个分组，将上一次计算的A,B,C,D复制到a,b,c,d中，进行下面的4轮计算，然后将a,b,c,d分别加到A,B,C,D上，下一组继续运行此算法，最终输出就是A||B||C||D，||在这里代表拼接

# 第一轮
for i in range(0,16,4):
    FF(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
    FF(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
    FF(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
    FF(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])
# 第二轮
for i in range(0,16,4):
    GG(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
    GG(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
    GG(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
    GG(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])
# 第三轮
for i in range(0,16,4):
    HH(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
    HH(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
    HH(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
    HH(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])
# 第四轮
for i in range(0,16,4):
    II(a,b,c,d,M[pos[0][i]],s[0][0],t[0][i])
    II(d,a,b,c,M[pos[0][i+1]],s[0][1],t[0][i+1])
    II(d,a,b,c,M[pos[0][i+2]],s[0][2],t[0][i+2])
    II(d,a,b,c,M[pos[0][i+3]],s[0][3],t[0][i+3])

其中pos和t，s数组会在代码中体现

#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <inttypes.h>
#include <stdlib.h>

#define F(x,y,z) (((x)&(y))|(~(x)&(z)))
#define G(x,y,z) (((x)&(z))|((y)&~(z)))
#define H(x,y,z) ((x)^(y)^(z))
#define I(x,y,z) ((y)^((x)|~(z)))
#define ROL32(x,i) (((x)<<(i))|((x)>>(32-(i))))
#define FF(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(F(b,c,d)+(M_j)+(t_i)),s))
#define GG(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(G(b,c,d)+(M_j)+(t_i)),s))
#define HH(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(H(b,c,d)+(M_j)+(t_i)),s))
#define II(a,b,c,d,M_j,s,t_i) ((b)+ROL32((a)+(I(b,c,d)+(M_j)+(t_i)),s))

uint8_t s[] = {
    7,12,17,22,
    5,9,14,20,
    4,11,16,23,
    6,10,15,21
};
uint32_t t[] = {
    0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
    0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,
    0x698098d8,0x8b44f7af,0xffff5bb1,0x895cd7be,
    0x6b901122,0xfd987193,0xa679438e,0x49b40821,

    0xf61e2562,0xc040b340,0x265e5a51,0xe9b6c7aa,
    0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
    0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,
    0xa9e3e905,0xfcefa3f8,0x676f02d9,0x8d2a4c8a,

    0xfffa3942,0x8771f681,0x6d9d6122,0xfde5380c,
    0xa4beea44,0x4bdecfa9,0xf6bb4b60,0xbebfbc70,
    0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
    0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,

    0xf4292244,0x432aff97,0xab9423a7,0xfc93a039,
    0x655b59c3,0x8f0ccc92,0xffeff47d,0x85845dd1,
    0x6fa87e4f,0xfe2ce6e0,0xa3014314,0x4e0811a1,
    0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391
};
void printArray(char *name,uint8_t *data,size_t len){
    printf("===========%s==============\n",name);
    for(size_t i=0;i<len;i++){
        printf("%02x,",data[i]);
    }
    printf("\n");
}
void md5(uint8_t *data,size_t len,uint32_t res[4]){
    uint32_t iv[4] = {0x67452301,0xefcdab89,0x98badcfe,0x10325476};
    uint32_t a,b,c,d;
    size_t pos;
    // 消息填充
    size_t plen = ((len+1+63)>>5)<<5;
    uint8_t *pdata = alloca(plen);
    memcpy(pdata,data,len);
    pdata[len]=0x80;
    memset(&pdata[len+1],0,plen-len-1);
    memcpy(&pdata[plen-8],&plen,8);
    // printf("%lld\n",plen);
    // printArray("my",pdata,plen);
    // 进行计算
    
    for(size_t i=0;i<plen;i+=64){
        a = iv[0];
        b = iv[1];
        c = iv[2];
        d = iv[3];
        // printf("iv[%d]: %08x %08x %08x %08x\n",i/64,a,b,c,d);
        // 第一轮
        pos=0;
        for(size_t j=0;j<16;j+=4){
            a = FF(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[0],t[j]);
            // printf("%08x %08x %08x %08x\n",a,b,c,d);
            pos+=1;
            d = FF(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[1],t[j+1]);
            pos+=1;
            c = FF(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[2],t[j+2]);
            pos+=1;
            b = FF(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[3],t[j+3]);
            pos+=1;
        }
        // 第二轮
        pos=1;
        for(size_t j=0;j<16;j+=4){
            a = GG(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[4],t[16+j]);
            pos=(pos+5)&0xf;
            d = GG(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[5],t[16+j+1]);
            pos=(pos+5)&0xf;
            c = GG(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[6],t[16+j+2]);
            pos=(pos+5)&0xf;
            b = GG(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[7],t[16+j+3]);
            pos=(pos+5)&0xf;
        }
        // 第三轮
        pos=5;
        for(size_t j=0;j<16;j+=4){
            a = HH(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[8],t[32+j]);
            pos=(pos+3)&0xf;
            d = HH(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[9],t[32+j+1]);
            pos=(pos+3)&0xf;
            c = HH(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[10],t[32+j+2]);
            pos=(pos+3)&0xf;
            b = HH(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[11],t[32+j+3]);
            pos=(pos+3)&0xf;
            printf("%08x %08x %08x %08x\n",a,b,c,d);
        }
        // 第四轮
        pos=0;
        for(size_t j=0;j<16;j+=4){
            a = II(a,b,c,d,*(uint32_t*)&pdata[pos*4+i*64],s[12],t[48+j]);
            pos=(pos+7)&0xf;
            d = II(d,a,b,c,*(uint32_t*)&pdata[pos*4+i*64],s[13],t[48+j+1]);
            pos=(pos+7)&0xf;
            c = II(c,d,a,b,*(uint32_t*)&pdata[pos*4+i*64],s[14],t[48+j+2]);
            pos=(pos+7)&0xf;
            b = II(b,c,d,a,*(uint32_t*)&pdata[pos*4+i*64],s[15],t[48+j+3]);
            pos=(pos+7)&0xf;
        }
        iv[0]+=a;
        iv[1]+=b;
        iv[2]+=c;
        iv[3]+=d;
    }
    memcpy(res,iv,sizeof(uint32_t)*4);
}


int main(){
    uint32_t res[4];
    md5("deadbeef",8,res);
    printArray("mymd5",(uint8_t*)res,16);
    return 0;
}

参考资料

《应用密码学：协议、算法与C源程序》

对称加密算法

加密模式

设$c_i,p_i,iv,f$分别为第$i$个密文块，明文块，初始向量，加密函数。ECB模式无$iv$。

ECB

每个块自行加密

$c_0=f(p_0),c_1=f(p_1),…,c_n=f(p_n)$

CBC

当前块加密会影响到以后的块

$c_0=f(iv\oplus p_0),c_1=f(p_1\oplus c_0),…,c_n=f(c_{n-1}\oplus p_n)$

AES

参考自https://ctf-wiki.github.io/ctf-wiki/crypto/blockcipher/aes-zh/

https://bbs.pediy.com/thread-253884.htm#msg_header_h1_0

也叫Rijndael 128加密法。加密过程中，每一块都是128比特。

使用代换-置换网络

加密的单位为4*4字节共4步

AddRountKey

每一回合与该次密钥做xor运算，密钥通过Rijndael密钥生成方案产生
SubBytes

把每一个字节通过查找表(s盒)的方式替换成另一个
ShiftRows

可以理解为每个双字单位分散到其它双字

这里是不同双字的混合
MixColumns

使用线性变换在一个双字内部混合

这里是一个双字内部的混合

实现中表现为一个矩阵乘

第一轮加密之前需要进行“白化操作”，即首先异或密钥
最后一轮没有MixColumns操作，使用AddRountKey替代

#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <inttypes.h>
#include <stdlib.h>

#define BLOCK_SIZE 16
#define ROL32(x,i) (((x)<<i)|((x)>>(32-i)))
#define s2b(i,j) (((i))+((j)<<2)) // 将state坐标转化为block坐标

uint32_t k[44];
static uint8_t RC[] = {0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36};
static uint8_t SBOX[]= {0x63,0x7c,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,0xCA,0x82,0xc9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xcC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};
static uint8_t RSBOX[]={0x48,0x40,0x58,0xb5,0x08,0x24,0x29,0x76,0xf4,0x72,0x71,0xdf,0x91,0x7e,0x0d,0x63,0x01,0x4d,0x5b,0x11,0xe8,0x4e,0x7d,0xea,0x28,0xe6,0x64,0x86,0x88,0x9c,0xeb,0x59,0xfd,0x03,0xe7,0xa1,0xc5,0xa8,0x32,0x8b,0x99,0x5d,0xad,0x9e,0xf6,0x14,0x33,0xb6,0xbf,0xc3,0xf1,0xd3,0xee,0xe5,0xa6,0x3e,0x0f,0x57,0x1a,0xa4,0xb3,0xce,0x51,0xc2,0x1e,0xe1,0xd6,0x8c,0xdc,0xf7,0xe2,0xff,0x19,0x1d,0xa7,0x27,0x8d,0xbc,0x79,0x74,0xb8,0xd0,0xd4,0x6c,0x21,0x53,0xdb,0x7a,0x9d,0x2f,0x98,0xda,0x89,0xb4,0x75,0x4f,0x96,0x2d,0x0e,0x52,0xf0,0x78,0xa9,0xa3,0x26,0xae,0x5e,0x36,0x9a,0x4b,0x68,0xa5,0x60,0x42,0xe9,0x73,0x10,0x25,0xfb,0x6a,0xdd,0x1b,0xcd,0xd5,0x09,0x82,0xcf,0x05,0xa2,0xac,0xe3,0xf8,0x92,0x0a,0x93,0xbb,0x85,0x04,0x5f,0xec,0x17,0xc6,0xf5,0x8f,0x35,0xaa,0xca,0x94,0xb0,0x18,0xd9,0x67,0x3b,0x69,0xb2,0xc8,0xc4,0x3f,0xef,0x45,0x16,0x2b,0x43,0x2c,0xde,0x4c,0x07,0xf2,0x06,0x20,0xab,0xd7,0x62,0x34,0x5a,0x44,0x55,0xb9,0xd1,0xcc,0xc7,0x7f,0xaf,0x54,0x37,0x9f,0x1f,0x0c,0xc1,0x80,0x46,0xba,0xcb,0xc9,0x6f,0x66,0x97,0x38,0x31,0x2e,0x56,0x39,0x7c,0x15,0x3d,0x3a,0x83,0x84,0x90,0x70,0x6b,0xb7,0x8e,0xd2,0x5c,0xf3,0xfa,0x2a,0xbd,0x6e,0x22,0x12,0x1c,0x61,0x47,0xa0,0x49,0x65,0xbe,0x95,0x77,0xfc,0xb1,0x3c,0xfe,0x6d,0x41,0x50,0xf9,0xd8,0x87,0x0b,0x30,0x8a,0xc0,0x02,0x4a,0x23,0xe0,0xe4,0x9b,0x00,0xed,0x7b,0x81,0x13};
static uint8_t MIX_COL_MAT[] = {2,1,1,3,3,2,1,1,1,3,2,1,1,1,3,2};
static uint8_t RE_MIX_COL_MAT[] = {0xe,0x9,0xd,0xb,0xb,0xe,0x9,0xd,0xd,0xb,0xe,0x9,0x9,0xd,0xb,0xe};
void printArray(const char *name,uint8_t *v,size_t len){
    printf("========%s=========\n",name);
    for(size_t i=0;i<len;i++){
        printf("%02X,",v[i]);
    }
    printf("\n=================\n");
}
void subByte(uint8_t *x,size_t len,uint8_t *s){
    for(size_t i=0;i<len;i++){
        x[i]=s[x[i]];
    }
}
/*
 * @function 行移位
 * 行移位实际上是字节级置换，所以转化成置换问题处理
*/
void shiftRows(uint8_t x[BLOCK_SIZE]){
    uint8_t tmp[BLOCK_SIZE];
    static uint8_t tab[]={0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11};
    for(size_t i=0;i<BLOCK_SIZE;i++){
        tmp[i]=x[tab[i]];
    }
    memcpy(x,tmp,BLOCK_SIZE);
}
void addRoundKey(uint8_t x[BLOCK_SIZE],uint8_t rk[BLOCK_SIZE]){
    for(size_t i=0;i<BLOCK_SIZE/4;i++){
        for(size_t j=0;j<4;j++){
            x[s2b(i,j)]^=rk[s2b(i,j)];
        }
    }
}
void mixCols(uint8_t x[BLOCK_SIZE],uint8_t const mat[BLOCK_SIZE]){
    uint8_t tmp[BLOCK_SIZE];
    uint8_t sum;
    for(size_t i=0;i<4;i++){
        for(size_t j=0;j<4;j++){
            sum=0;
            for(size_t k=0;k<4;k++){
                if(mat[s2b(i,k)]==2&&(0x80&x[s2b(k,j)])){
                    sum^=0x1b^(x[s2b(k,j)]<<1);
                }else{
                    sum^=mat[s2b(i,k)]*x[s2b(k,j)];
                }
            }
            tmp[s2b(i,j)]=sum;
        }
    }
    memcpy(x,tmp,BLOCK_SIZE);
}
void encrypt(uint8_t x[BLOCK_SIZE]){
    addRoundKey(x,(uint8_t*)k);
    for(size_t i=0;i<10;i++){
        shiftRows(x);
        mixCols(x,MIX_COL_MAT);
        addRoundKey(x,(uint8_t*)k);
    }
}

void initKey(uint8_t key[16]){
    uint8_t *bk = (uint8_t*)k;
    for(size_t i=0;i<4;i++){
        for(size_t j=0;j<4;j++){
            bk[i*4+j]=key[s2b(i,j)];
        }
    }
    
    uint32_t g;
    for(size_t i=4;i<44;i++){
        if(!(i&3)){
            g = ROL32(k[i-1],8);
            subByte((uint8_t*)&g,4,SBOX);
            g^=RC[i/4]<<24;
            k[i]=k[i-4]^g;
        }else{
            k[i]=k[i-4]^k[i-1];
        }
    }
}
int main(){
    char key[] = "deadbeef20201231";
    initKey((uint8_t*)key);
    printArray("key",(uint8_t*)k,44*4);

    return 0;
}

特点

S盒，密钥生成中的常量

参考资料：[AES–wikipedia](高级加密标准 - 维基百科，自由的百科全书)

DES

Fiestel网络

16个相同的过程，块长度为64位，分成两个32位的半块v1,v2

总体过程：

进行一次置换，称为IP
进行16轮如下操作

s1=v1^F(v2)

v1=v2

v2=s1

其中F为Fiestel函数，包含扩张，与密钥混合，S盒，置换操作
进行一次置换，成为FP，FP为IP的逆函数

IP和FP是简化输入输出数据库的过程而被显式地包含在标准中

Fiestel函数

扩张

将32为半块扩展到48位，包含8个6位块，每块包含4位输出位，加上邻接块中紧邻的位
与密钥混合

用异或操作将扩张结果和子密钥混合，子密钥是通过密钥调度产生的
S盒

与子密钥混合后，分成6个8位的块，然后使用S盒置换处理
置换

32个输出位利用P置换进行重组

特点

S盒

参考资料：DES–wikipedia

tea

可以加密两个无符号整数

参考代码(来自wikipedia)

#include <stdint.h>

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);  
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;                                   
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

也有部分变种，大多是变了delta，或者delta使用v0=(0-(-delta))

xtea

参考代码(来自wikipedia)

#include <stdint.h>

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

相比tea，在使用密钥更不确定，特征值不变

xxtea

参考代码(来自wikipedia)

#define MX ((z>>5^y<<2) + (y>>3^z<<4) ^ (sum^y) + (k[p&3^e]^z))

  long btea(long* v, long n, long* k) {
    unsigned long z=v[n-1], y=v[0], sum=0, e, DELTA=0x9e3779b9;
    long p, q ;
    if (n > 1) {          /* Coding Part */
      q = 6 + 52/n;
      while (q-- > 0) {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) y = v[p+1], z = v[p] += MX;
        y = v[0];
        z = v[n-1] += MX;
      }
      return 0 ; 
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      q = 6 + 52/n;
      sum = q*DELTA ;
      while (sum != 0) {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
      }
      return 0;
    }
    return 1;
  }

n表示v的长度，正数表示加密，负数解密

SM4

密钥长度为128bits
加密算法和密钥扩展算法都是32位非线性迭代结构
加解密算法结构相同，轮密钥的使用顺序相反

定义运算

32位数$x$向左循环移动$i$位$:x<<<i,\oplus$为异或

1	#define ROL32(x,i) ((x)<<(i)\|(((unsigned int)x>>(32-(i)))))

定义参量

密钥长度位128bits $MK=(MK_0,MK_1,MK_2,MK_3)$

轮密钥为32*32bits $rk=(rk_0,rk_1,…,rk_{31})$

$FK=(FK_0,FK_1,…,FK_3)$为系统参数，$CK=(CK_0,CK_1,…,CK_{31})$为固定参数

$CK_{i,j}=(4i+j)*7\ mod\ 256$，其中$i$为双字编号，$j$为字节编号，$j$采用大端序

#define RK_SIZE 32
static uint32_t mk[4];    // 加密使用的密钥
static uint32_t rk[31];    // 轮密钥
static uint32_t fk[4]={0xA3B1BAC6,0x56AA3350,0x677D9197,0xB27022DC};
// ck会在密钥生成算法中体现

轮函数F

$F(X_0,X_1,X_2,X_3,rk)=X_0\oplus T(X_1\oplus X_2\oplus X_3\oplus rk)$

合成置换$T(.)=L(\tau(.))$

若输入为$A=(a_0,a_1,a_2,a_3)$，其中$a_i$为8字节无符号整数，则非线性置换$\tau(A)=(sbox[a_0],sbox[a_1],sbox[a_2],sbox[a_3])$

$sbox$为替换用s盒

若输入为$B$，其中$B$为32字节无符号整数，则线性变换$L(B)=B\oplus (B<<<2)\oplus(B<<<10)\oplus(B<<<18)\oplus(B<<<24)$

#define L(x) (x)^ROL32(x,2)^ROL32(x,10)^ROL32(x,18)^ROL32(x,24)

#define tau(x) (sbox[(x)>>24]<<24|sbox[((x)>>16)&0xFF]<<16|sbox[((x)>>8)&0xFF]<<8|sbox[x&0xFF])
#define T(x) (L(tau(x)))

uint8_t sbox[256]; // s盒，在最终代码中体现

// 轮函数F直接在加密过程中体现

加密算法

反序变换$R(a_0,a_1,a_2,a_3)=(a_3,a_2,a_1,a_0),a_i$为8位

设输入为$(X_0,X_1,X_2,X_3),X_i$为32位

输出为$(Y_0,Y_1,Y_2,Y_3)$

则$X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i)$

$(Y_0,Y_1,Y_2,Y_3)=R(X_{32},X_{33},X_{34},X_{35})$

解密过程和加密过程变换结构相同，不同的是轮密钥顺序

加密时$(rk_0,rk_1,…,rk_{31})$

解密时$rk_{31},rk_{30},…,rk_0$

void crypt(uint32_t p[4],uint32_t crk[31]){
    uint32_t c[36];
    c[0]=p[0];
    c[1]=p[1];
    c[2]=p[2];
    c[3]=p[3];
    for(size_t i=0;i<RK_SIZE;i++){
        c[i+4]=c[i]^T(c[i+1]^c[i+2]^c[i+3]^crk[i]);
    }
    p[0]=c[35];
    p[1]=c[34];
    p[2]=c[33];
    p[3]=c[32];
}
void encrypt(uint32_t p[4]){
    crypt(p,rk);
}
void decrypt(uint32_t c[4]){
    crypt(p,rrk); // rrk是rk的逆序
}

密钥扩展算法

密钥$MK=(MK_0,MK_1,MK_2,MK_3)$

$K=(K_0,K_1,…,K_{31})$

$(K_0,K_1,K_2,K_3)=(MK_0\oplus FK_0,MK_1\oplus FK_1,MK_2\oplus FK_2,MK_3\oplus FK_3)$

轮密钥为$rk,rk_i=K_{i+4}=K_i\oplus T’(K_{i+1}\oplus K_{i+2}\oplus K_{i+3}\oplus CK_i)$

$T’$和$T$基本相同，其中的$L’=B\oplus(B<<<13)\oplus(B<<<23)$

#define Lp(x) ((x)^ROL32(x,13)^ROL32(x,23))
#define Tp(x) Lp(tau(x))
#define ck(i) (((4*(i)*7)&0xFF)<<24|(((4*(i)+1)*7)&0xFF)<<16|(((4*(i)+2)*7)&0xFF)<<8|(4*(i)+3)&0xFF)
void initKey(uin32_t mk[4]){
    uint32_t k[36];
    k[0]=mk[0]^fk[0];

    for(size_t i=0;i<RK_SIZE;i++){
        k[i+4]=k[i]^Tp(k[i+1]^k[i+2]^k[i+3]^ck(i));
        rk[i]=k[i+4];
        rrk[RK_SIZE-i]=rk[i]
    }
}

完整代码

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <inttypes.h>

#define cha(x) ((((x)&0x3F)+24)%64)
#define ROL32(x,i) ((x)<<(i)|(((unsigned int)(x)>>(32-(i)))))
#define L(x) (x)^ROL32(x,2)^ROL32(x,10)^ROL32(x,18)^ROL32(x,24)
#define tau(x) (sbox[((x)>>24)&0xFF]<<24|sbox[((x)>>16)&0xFF]<<16|sbox[((x)>>8)&0xFF]<<8|sbox[x&0xFF])
#define T(x) (L(tau(x)))
#define Lp(x) ((x)^ROL32(x,13)^ROL32(x,23)) // L'
#define Tp(x) (Lp(tau(x))) // T'
#define ck(i) (((4*(i)*7)&0xFF)<<24|(((4*(i)+1)*7)&0xFF)<<16|(((4*(i)+2)*7)&0xFF)<<8|(4*(i)+3)*7&0xFF)
#define R(x) (((x)>>24)&0xFF|((x)>>8)&0xFF00|((x)<<8)&0xFF0000|((x)<<24))
#define RK_SIZE 32      // 密钥轮数
static uint32_t rk[32];    // 轮密钥
static uint32_t rrk[32];    // 逆序轮密钥
static uint32_t fk[4] = { 0xA3B1BAC6,0x56AA3350,0x677D9197,0xB27022DC };

static uint8_t sbox[256] = {
0xd6,0x90,0xe9,0xfe,0xcc,0xe1,0x3d,0xb7,0x16,0xb6,0x14,0xc2,0x28,0xfb,0x2c,0x05,
0x2b,0x67,0x9a,0x76,0x2a,0xbe,0x04,0xc3,0xaa,0x44,0x13,0x26,0x49,0x86,0x06,0x99,
0x9c,0x42,0x50,0xf4,0x91,0xef,0x98,0x7a,0x33,0x54,0x0b,0x43,0xed,0xcf,0xac,0x62,
0xe4,0xb3,0x1c,0xa9,0xc9,0x08,0xe8,0x95,0x80,0xdf,0x94,0xfa,0x75,0x8f,0x3f,0xa6,
0x47,0x07,0xa7,0xfc,0xf3,0x73,0x17,0xba,0x83,0x59,0x3c,0x19,0xe6,0x85,0x4f,0xa8,
0x68,0x6b,0x81,0xb2,0x71,0x64,0xda,0x8b,0xf8,0xeb,0x0f,0x4b,0x70,0x56,0x9d,0x35,
0x1e,0x24,0x0e,0x5e,0x63,0x58,0xd1,0xa2,0x25,0x22,0x7c,0x3b,0x01,0x21,0x78,0x87,
0xd4,0x00,0x46,0x57,0x9f,0xd3,0x27,0x52,0x4c,0x36,0x02,0xe7,0xa0,0xc4,0xc8,0x9e,
0xea,0xbf,0x8a,0xd2,0x40,0xc7,0x38,0xb5,0xa3,0xf7,0xf2,0xce,0xf9,0x61,0x15,0xa1,
0xe0,0xae,0x5d,0xa4,0x9b,0x34,0x1a,0x55,0xad,0x93,0x32,0x30,0xf5,0x8c,0xb1,0xe3,
0x1d,0xf6,0xe2,0x2e,0x82,0x66,0xca,0x60,0xc0,0x29,0x23,0xab,0x0d,0x53,0x4e,0x6f,
0xd5,0xdb,0x37,0x45,0xde,0xfd,0x8e,0x2f,0x03,0xff,0x6a,0x72,0x6d,0x6c,0x5b,0x51,
0x8d,0x1b,0xaf,0x92,0xbb,0xdd,0xbc,0x7f,0x11,0xd9,0x5c,0x41,0x1f,0x10,0x5a,0xd8,
0x0a,0xc1,0x31,0x88,0xa5,0xcd,0x7b,0xbd,0x2d,0x74,0xd0,0x12,0xb8,0xe5,0xb4,0xb0,
0x89,0x69,0x97,0x4a,0x0c,0x96,0x77,0x7e,0x65,0xb9,0xf1,0x09,0xc5,0x6e,0xc6,0x84,
0x18,0xf0,0x7d,0xec,0x3a,0xdc,0x4d,0x20,0x79,0xee,0x5f,0x3e,0xd7,0xcb,0x39,0x48
};
void crypt(uint32_t p[4], uint32_t crk[31]) {
    uint32_t c[36];
    c[0] = p[0];
    c[1] = p[1];
    c[2] = p[2];
    c[3] = p[3];
    uint32_t t;
    for (size_t i = 0; i < RK_SIZE; i++) {
        t = (c[i + 1] ^ c[i + 2] ^ c[i + 3] ^ crk[i]);
        c[i + 4] = c[i] ^ T(t);
        printf("%08x\n", c[i + 4]);
    }
    p[0] = c[35];
    p[1] = c[34];
    p[2] = c[33];
    p[3] = c[32];
}
void encrypt(uint32_t p[4]) {
    crypt(p, rk);
}
void decrypt(uint32_t c[4]) {
    crypt(c, rrk); // rrk是rk的逆序
}
void initKey(uint32_t mk[4]) {
    uint32_t k[36];
    k[0] = mk[0] ^ fk[0];
    k[1] = mk[1] ^ fk[1];
    k[2] = mk[2] ^ fk[2];
    k[3] = mk[3] ^ fk[3];

    uint32_t t;
    for (size_t i = 0; i < RK_SIZE; i++) {
        t = k[i + 1] ^ k[i + 2] ^ k[i + 3]^ck(i);
        k[i + 4] = k[i] ^ Tp(t);
        rk[i] = k[i + 4];
        rrk[RK_SIZE - i-1] = rk[i];
    }
}

void printArray(const char* name, uint32_t* d, size_t len) {
    printf("==============%s============\n", name);
    for (size_t i = 0; i < len; i++) {
        printf("0x%08X,", d[i]);
    }
    printf("\n============================\n");
}
int main() {
    uint8_t data[] = { 0x01,0x23,0x45,0x67,0x89,0xab,0xcd,0xef,0xfe,0xdc,0xba,0x98,0x76,0x54,0x32,0x10 };
    uint8_t key[] = { 0x01,0x23,0x45,0x67,0x89,0xab,0xcd,0xef,0xfe,0xdc,0xba,0x98,0x76,0x54,0x32,0x10 };
    uint32_t mk[4];
    uint32_t p[4];

    memcpy(p, data, 16);
    memcpy(mk, key, 16);
    for (size_t i = 0; i < 4; i++) {
        mk[i] = R(mk[i]);
        p[i] = R(p[i]);
    }
    initKey(mk);
    printArray("plain text", p, 4);
    encrypt(p);
    printArray("cipher", p, 4);
    decrypt(p);
    printArray("plain text(after decrypt)", p, 4);
    for (size_t i = 0; i < 4; i++) {
        p[i] = R(p[i]);
    }

    memcpy(data, p, 16);
    return 0;
}

参考资料

[1] SM4算法标准

公钥加密算法

rsa

费马小定理

$p$是质数，$a$不是$p$的倍数，$a^{p-1}mod\ p\equiv1$

那么对于数据$a$，加密后的数据为$c$，私钥为$e,p,q$，公钥为$d,n$

其中$n=pq$，$ed\equiv 1(\mod (p-1)(q-1))$

则加密

$$
c=a^{e}\mod n
$$

解密

$$
c^{d}\mod n\equiv (a^e)^d\mod n\equiv a^{ed}\mod n
$$

由于

$$
a^{ed}\equiv a^{1+t(p-1)(q-1)}\mod n=aa^{(p-1)(q-1)}\mod n
$$

又由于$n=pq,ab\mod n=(a\mod n)(b\mod n)\mod n$

得到

$$
a^{(p-1)(q-1)}\mod n
$$

从而

$$
(a^{p-1})^{q-1}\mod pq\equiv a^{p-1}\mod p\equiv 1
$$

从而解密出来为$a$

攻击方式

共模攻击

$c_1=a^{e_1}\mod n,c_2=a^{e_2}\mod n,gcd(e1,e2)=1$

则有辗转相除法有$xe_1+ye_2=1$

则$c_1^{x}+c_2{y}=a^{xe_1+ye_2}=a$

ElGamal

// TODO

其它加密算法

CRC32

用于校验数据

uint32_t CRC(uint32_t *v,size_t len){

    uint32_t crc32tab[256],crc,dwcrc=0xFFFFFFFF;
    for(size_t i=0;i<256;i++){
        crc=i;
        for(size_t j=0;j<8;j++){
            if(crc&1)crc=(crc>>1)^0xEDB88320;
            else crc>>1;
        }
        crc32tab[i]=crc;
    }


    for(size_t i=0;i<len;i++){
        dwcrc=crc32tab[(dwcrc^v[i])&0xFF]^(dwcrc>>8);
    }
    dwcrc=~dwcrc;
    return dwcrc;
}

CRC并不安全，只用于传输过程中完整性的校验

base系列

base64，base56，base32，base16

找到base表

差分密码分析

攻击者选取一部分明文并获取相应密文，运用若干对有着常量差异的明文，计算其中的差异$\Delta x=f(x_1,x_2)$，其中$f$可以自定义，比如异或操作。

然后攻击者计算相应密文的差异，尝试找出差异分布的统计特征。明文差异和密文差异所组成的差异叫做差分，统计特征由所使用的S盒所决定。

对于S盒$S$，攻击者分析差分$(\Delta x,\Delta y),\Delta y=S(x\oplus \Delta x)\oplus S(x)$。攻击者希望某个密文差异出现的频率非常高，这样就能将加密和随机过程区分开来。

最基本的差分密码分析密钥破解形式中，攻击者首先获取大量明文对的密文，并假设差分在至少r − 1轮后有效，r即加密算法的总轮数。攻击者在倒数第二轮与最后一轮之间差异固定的假设下，去推测可能的轮密钥。如果轮密钥比较短，那么只需举可能的轮密钥，直到最后一轮运算结果和差异的密文对一致即可。当一个轮密钥看起来明显比其他密钥常出现时，其会被假设是正确的轮密钥

还不是很懂，回头看英文版似乎有个简单的例子。

参考资料

[1] 差分密码分析–wikipedia

Kerberos认证流程

Kerberos用于服务器认证用户身份

Kerberos保存有所有人的密钥

过程

客户从Kerberos认证服务器请求一张票据，该票据用用户的密钥加密之后发送给用户。这个票据是TGS(票据许可服务)
客再从TGS请求一张票据，TGS将票据返回给用户
用户将此票据呈现给服务器，如果用户身份没问题，服务器便会提供服务

古典加密算法/编码算法

凯撒加密

仿射密码

凯撒加密升级版

维吉尼亚密码

破解方式

相关数论基础

辗转相除法

快速幂

中国剩余定理

证明

费马小定理

hash算法

md5

参考资料

对称加密算法

加密模式

ECB

CBC

AES

特点

DES

总体过程：

Fiestel函数

特点

tea

xtea

xxtea

SM4

定义运算

定义参量

轮函数F

加密算法

密钥扩展算法

完整代码

参考资料

公钥加密算法

rsa

攻击方式

ElGamal

其它加密算法

CRC32

base系列

差分密码分析

Kerberos认证流程