Crypto入门-流密码初探

基础知识

LCG

线性同余生成器,由线性函数生成随机数序列。标准的LCG的生成序列满足下列递推式:

xn+1=(Axn+B)(modM)

其中ABM为设定的常数,初始值x0为种子。

攻破Linux Glibc的rand()函数(TYPE_0

当使用TYPE_0时,采用的是标准LCG,生成公式为:

si=(1103515245si1+12345)(mod2147483648)

直接求逆元得:

si1=1857678181(si12345)(mod2147483648)

LFSR

线性反馈移位寄存器,由一个移位寄存器和一个反馈函数组成,反馈函数为一个线性函数。进行密钥流生成时,每次从移位寄存器中移出一位作为当前的结果,而移入的位由反馈函数对寄存器中的某些位进行计算来确定。

为使LFSR获得最大周期,即n位LFSR获得2n1的周期,那么选取反馈函数F方法:选取GF(2)上的一个n次的本原多项时,如当n=32时,选取:

x32+x7+x5+x3+x2+x+1

得到F函数为:

F=s32s7s5s3s2s1

这种周期最大的序列称为“m序列”。

设某LFSR长度为n位,当已知长度为2n的输出,且方程组有解时,可获得反馈函数。

例如4位未知LFSR,输出序列为“10001010”,从左向右输出,因异或等价于模2加法,可列出线性方程组:

{1a0+0a1+0a2+0a3=1(mod2)0a0+0a1+0a2+1a3=0(mod2)0a0+0a1+1a2+0a3=1(mod2)0a0+1aa+0a2+1a3=0(mod2)

解方程组得:

{a0=1a1=0a2=1a3=0

可求得反馈函数为:F=s0s2

攻破Linux Glibc的rand()函数(TYPE_3

随机数产生方法:状态数组buf中的fptrrptr指向的数字相加,再除以2。在TYPE_3的情况下,buf长度为34,且fptrrptr分别为当前下标减31和减3,线性反馈式为:

xi=si3+si312

但因移入状态数组中的数不是产生后的随机数,而是右移1位前的数,末位存在01两种情况。当获取32组随机数后,向下预测的下一个数会以25的概率存在1的误差,且随着预测数增多而增大。

简单Demo:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
int s[256]={0},i=0;
srand(time(0));
for(i=0;i<32;i++)
s[i]=rand()<<1;
for(i=32;i<64;i++){
s[i]=s[i-3]+s[i-31];
int xx=(unsigned int)s[i]>>1;
int yy=rand();
printf("predicted %d, actual %d\n",xx,yy);
if(yy-xx==1){
s[i-3]++;
s[i-31]++;
s[i]+=2;
};
};
return 0;
};

RC4

略。