20220621现代密码学读书笔记

4.2 公钥密码体制基本概念

公钥密码之前的基础操作是代换和置换
公钥密码使用数学函数

4.2.1 原理

使用两个密钥分离加密和解密能力，一个公钥一个私钥
加密：公钥加密私钥解密
认证：私钥加密(签名)，公钥解密(验签)

4.2.2 算法要求

1.接收方B产生密钥对在计算上是容易的
2.发送方A用接收方B的公钥对消息m加密产生密文c=encrypt(pkb,m)在计算上是容易的,其中pkb为B的公钥
3.接收方B用私钥对c解密成m=decrypt(skb,c)在计算上是容易的,其中skb为B的私钥
4.敌人由pkb计算skb在计算上是不可行的
5.敌人由c和pkb恢复明文m在计算上是不可行的
6.加解密次序可交换 这条虽然有用但不是强制要求

单向陷门函数是一簇可逆函数y=fk(x)，满足:
1.当已知k和x时，计算y容易
2.当已知k和y时，计算x容易
3.当已知y但未知k时，求x是不可行的

4.2.3 攻击方法

穷举
可能字攻击：若传递数据长度可穷举则穷举明文对比密文

4.3 RSA 算法

4.3.1 算法描述

1.选取保密大质数p,q
2.计算n=q * q, f(n) = (p-1)(q-1) 其中fn是欧拉函数
3.选取整数e，满足1 < e < f(n)且gcd(f(n),e)=1
4.计算d, 满足d * e === 1 mod f(n),d是e在模f(n)下的逆元
5.{e,n}作为公钥,{d,n}作为私钥

加密过程为计算c === m^e mod n
解密过程为计算m === c^d mod n

因构造的e和d互质，且n为素数，由之前的数学铺垫可知在模n下有
c === m^e -> c^d === m ^ ed === m ^(k*f(n) + 1) === m
说实话最后一步略绕，但懒得分析了。。。总之这是数学规律

4.3.2 RSA的计算问题

加解密过程因大指数的幂次容易越界，因此可以用模运算性质缩小计算规模
平方和快速算法优化，x^16 == x^2 ^2 ^2 ^2，减小为4次乘法
pqed的计算均有技巧，此处略

4.3.3 中国剩余定理加速

通过中国剩余定理可代换中间结果，快速计算明文

4.3.4 RSA安全性

假定的是分解大质数是困难的问题，但随着算力的增强，这个速度在逐渐的被计算机暴力的解决
但密钥长度足够大的话目前的计算机还无法快速计算完成

4.4 背包密码

给出一组正整数ai，和一个整数s，求解ai中的子集的和为s
同理，已知ai子集好求s，但已知s难以反向求ai

4.5 Rabin密码

RSA的难度普遍认为和分解大质数相等，但实际上知识小于或等于大质数分解
而Rabin可被证明难度等价于分解大指数

1.对于同一密文可能有两个以上对应的明文
2.修改RSA中的e=2

密钥产生, 大质数p,q满足p===q===3mod4, n = p * q,n为公钥,pq为密钥
加密，c === m ^ 2 mod n
解密，求解x ^ 2 === c mod n ，套中国剩余定理的结论

4.6 NTRU公钥密码

基于整系数多项式的环，在环上的系数相关运算封闭且有数学规律

4.7 椭圆曲线

4.7.1 连续域

ECC是Elliptic Curve Cryptography的简写
定义在椭圆曲线方程上的运算
无穷远定义为O，定义为单位元
加法逆元定义为P2=-P1关于X轴对称，因此当P1P2共线时P1+P2==O
加法定义Q+R：QR为横坐标不同的两点，做直线QR交f(x)于P1(当切线时取P1=Q=R)
因Q+R+P1=O，因此Q+R=-P1，也就是关于P1沿x轴翻转后的点
切线特殊情况：也就是Q的倍数运算,直接取在Q的切线上的交点沿x轴翻转后的点

4.7.2 离散域

椭圆曲线方程的系数取于GF(p)，其中p为大质数

4.7.3 点数

计算离散域方程的线上有多少离散点，有公式

4.7.4 明文消息嵌入椭圆曲线

对任意m计算mk+j，直到x^3 + ax + bmodp是平方根，即得到(x,sqrt(x^3 + ax + b))
解密只需要x/30向下取整即可

4.7.5 椭圆曲线上的密码

椭圆曲线上的困难问题,群上的点和特殊运算构成Abel群Ep(a,b)
考虑Q=kP，已知k和P的情况下，也就算点P的切线与fx的交点关于x轴翻转易求，k是多次也迭代易求
反之已知PQ则难以确定k

注意：这个离散对数困难问题可应用于任何基于有限域离散对数原理的密码体制

DF密钥交换协议
GElGamal密码体制

4.8基于身份的密码体制

不是我关心的内容，略

明天不继续了。。。到此为止已经解决了我对ECC和RSA的疑惑了，后续内容有缘再见了hhhh
mark当前117页
实在是太南了，我宁愿去看概率论和AI基础也不想看离散数学了，因此离散数学那本书我放弃了
下一本书是编译原理。。。。

20220616现代密码学读书笔记

4.1.9 离散对数

如果a的阶m等于φ(n)，则称a为n的本原根（生成元）
若p是质数，a是p的本原根，则a, a*a, a*a*a,...a^(p-1)的结果是1~(p-1)之间互不相同的所有值，因此对任意的1<=b<=p-1都存在唯一的1<=i<=p-1使得b===a^i mod p。
称i为模p下以a为底的指标，记为i=ind(a,p,b)，也就是离散对数

性质 ind(a,p,1)=0, ind(a,p,a)=1
显然易证：a^0 mod p == 1 mod p == 1, a^1 mod p == a

若a^z === a^q mod p 则z===q mod φ(p)

4.1.10 平方剩余

n是正整数,a是整数,满足gcd(a,n)=1,称a是模n的平方剩余，反之若x * x === a mod n有解则称为非平方剩余

显然若p是质数则模p的平方剩余个数为(p-1)/2, 且与模p的非平凡剩余相等。
若a是模p的平方剩余则a的两个平方根0<=x1<=(p-1)/2, (p-1)/2+1<=x2<=(p-1),且x1或x2之一也是模p的平方剩余

legendre函数定义
p是质数,a是整数
若a被p整除,p|a则legendre(a,p)=0
若a是模p的平方剩余则legendre(a,p)=1
若a是模p的非平方剩余则legendre(a,p)=-1

公式 legendre(a,p) === a^((p-1)/2) mod p
性质,当p是奇素数且a,b都不能被p整除时
a === b mod p 则 legendre(a,p) = legendre(b,p)
legendre(a*b,p) = legendre(a,p) * legendre(b,p)
legendre(a*a,p) = 1
legendre(a+p,p) = legendre(a,p)

设n是正整数,当n表示为质因子的幂乘积的形式p1^a1 * p2^a2 * ... pk^ak时
定义Jacobi(a,n) = legendre(a,p1) ^ a1 * legendre(a,p2) ^ a2 * legendre(a,pk) ^ ak

jacobi性质如下
当n是正合数,a,b与n互质时
a === b mod n 则 jacobi(a,n) = jacobi(b,n)
jacobi(a*b,n) = jacobi(a,n) * jacobi(b,n)
jacobi(a*b*b,n) = jacobi(a,n)
jacobi(a+n,n) = jacobi(a,n)
jacobi(1,n)=1, jacobi(-1,n)=(-1)^((n-1)/2), jacobi(2,n)=(-1)^((n^2-1)/8)

当m,n为大于2的奇数时
jacobi(m,n) = -1 ^ (((m-1)(n-1))/4) * jacobi(n,m)
易得当m===n===3 mod 4时 jacobi(m,n) = -jacobi(n,m)
否则jacobi(m,n)=jacobi(n,m)

综上所述计算jacobi不需要质因式分解,所以当计算legendre时可以先当作jacobi计算，如果有必要，计算jacobi(m,n)时可以通过m mod n 代替m，利用mn交换位置可以减小其中的一个数

jacobi和legendre的本质区别就是jacobi不表示平方剩余方程是否有解

设n为两个大质数p * q的积
由上面的结论可知1 ~ p-1的一半是模p的平方剩余，集合记为P,另一半记为NP
由上面的结论可知1 ~ q-1的一半是模q的平方剩余，集合记为Q,另一半记为NQ
而n的平方剩余a必须同时满足n是模p的平方剩余且a是模q的平方剩余, a属于P∩Q
所以与n互质小于n的a，有一半满足jacobi(a,n)=1记为c，另一半满足jacobi(a,n)=-1记为d
c可能属于P∩Q或NP∩NQ，d可能属于P∩NQ或NP∩Q
同理c中也有一半满足jacobi(a,p)=jacobi(a,q)=1的 a属于P∩Q 这些a就是n的平方剩余
c中剩下一半满足jacobi(a,p)=jacobi(a,q)=-1的 a属于NP∩NQ 这些a不是n的平方剩余

综上当p===q===3 mod 4 时,
由中国剩余定理可快速求出 x === y,-y mod p, x === z, -z mod q
反过来若已知四个中两个不同的根，就可快速的分解大整数n
jacobi(y,n) = -jacobi(z,n) 证明略

4.1.11 计算复杂度

这个数据结构里提过了，这里不赘述
若算法时间复杂度为多项式复杂度，就说这个算法是有效的，反之如果是指数复杂度则称之为无效

若问题存在多项式复杂度的算法可解，则称问题为P问题，也称之为计算可行的
NP问题是指可在多项式复杂度是时间内验证问题的一个解
问题若可在多项式时间内求解则一定可在多项式时间内验证，反之不行，因此P是NP的子集
NP问题中有一部分可以证明比其他问题困难，称之为NPC问题

下周继续第四章公钥密码，数学铺垫终于结束了，后面是公钥密码体制。现在回想起来好像当时听蔡老师没讲多久，自己看居然要这么久Orz
mark当前92页

编译client

gradle\wrapper\gradle-wrapper.properties这里可以修改gradlew的依赖地址distributionUrl，改成速度快的url就行，注意冒号要转义

修改projector-client-web\src\main\kotlin\org\jetbrains\projector\client\web\window\WebWindowManager.kt

注释掉stateMachine.fire DeactivationEvent后可以让projector一直处于前台，避免命令行调用idea失败

projector-client的electron和web的依赖还好，一次成功了

修改/root/.config/JetBrains/IdeaIC2021.2/idea64.vmoptions，增加

-Djava.awt.headless=true

可以在projector中正常使用命令行/projector/ide/bin/idea.sh

/usr/local/bin/idea软链到/projector/ide/bin/idea.sh可简化为idea

编写可执行文件i放到path下，内容为idea ${PWD}，在项目根目录执行i可直接控制projector切换项目

projector-client-web\src\main\resources\manifest.webmanifest是静态的，当设置了连接密码后，edge默认的快捷方式会读取这个地址丢失query param，暂时通过–app参数代替–app-url可绕过。

TODO 考虑是否能动态生成start_url和manifest.webmanifest？

重新编译server

根目录新增local.properties，修改useLocalProjectorClient=true可使用本地的client依赖打包

projector-client必须和projector-server同级，程序默认使用../projector-client寻找上一步的产物

在projector-server-common\gradle.properties修改服务器版本

在projector-server根目录执行打包命令，不是第二层的projector-server

如果gradlew找不到正确的java11版本，手动修改脚本JAVA_HOME部分

projector-server的依赖不知道为啥有几率失败

待定位根本原因，基本是访问jetbrains服务器失败，在插件内部。debug显示jetbrans的依赖服务器不支持tlsv1.2和1.3，但curl手动测试是正常的，在根目录的gradle.properties里逐个尝试这几个版本直到所有依赖都下载成功后暂时绕过了问题

20220614现代密码学读书笔记
后面即将出现大量数学基础，看不懂的建议直接放弃或者先去复习下离散数学

4.1.3 模运算

若a===0(modn),则n|a，也就是a=mn
若n|(a-b)，则a===bmodn
简单理解,被n整除的部分都可以减去，所以如果差值都可以被整除了，所以a和b在模n下相等(同余)

证明，a===bmodn-->n|(a-b),d|n-->d|(a-b)-->a===bmodd
解释，d|n说明d是n的因子，a-b可以被n整除的话，也一定可以被n的因子整除，所以a和b在modd下也同余
a===bmodni,d=lcm(n1....nk),a===bmodd

模运算性质

4.1.4 模指数运算

给定m,n计算a^m%n
显然a=7,n=19时,a^3+j=a^3,从a^4就重复了，循环周期为3
定义这个最小的循环周期为模n下a的阶，记为ordn(a)

定理: a在模n下的阶是=m则a^k===1modn的充要条件是k为n的倍数

4.1.5 费马定理、欧拉定理、卡米歇尔定理

Fermat定理:若p是素数,a是正整数,gcd(a,p)=1即ap互质,则a^(p-1)===1modp
欧拉函数:小于n且与n互质的正整数的个数
性质：
若n为质数则fn=n-1，显然因为n无法被分解了，除了自己以为就是n-1
若n为两个质数qp乘积，fn=fq * fp = (q-1) * (p-1)
若n有标准分解式，则fn=n(1-1/p1)*...*(1-1/pn)

欧拉定理：若a和n互质,则a^fn===1modn,其中fn为n的欧拉函数
卡米歇尔Carmichael函数: 对满足所有gcd(a,n)==1的a使得a^m===1modn同时成立的最小的正整数m
卡米歇尔定理：若a和n互质,则a^fn===1modn,其中fn为n的卡米歇尔函数

4.1.6 素数校验

定理：若n为正整数，若所有满足p<=sqrt(n)的素数p都无法整除n，n为素数
基于上面的定理有Eratosthenes筛法，列出2-n后删掉小于等于sqrt(n)的素数的倍数剩下的都是素数
当n很大时要排除的数量很大，实际上是不可行的

若p为大于2的素数，则方程x*x === 1 mod p的解只有 x===1和x===-1
Miller-Rabin概率检测基于这个条件做反向判断，可以快速判定不是
反之则有概率是素数，对于足够大的尝试次数若总不返回非素数，则会加大是素数的概率

AKS算法由Agrawal Kayal Saxena三个人提出，完全看不懂。。。。。总之有确定性的公式可以大大降低计算量了

4.1.7 欧几里得算法

对任意非负整数a和正整数b有gcd(a,b) = gcd(b,a%b)
欧几里得算法可使当ab较大时逐渐缩小运算输入的大小

扩展的欧几里得算法可求模乘法逆元，当互输入的两数质时，利用倒数第二轮的变量可快速计算

4.1.8 中国剩余定理

今有物不知其数，三三数之有二，五五数之有七，七七数之有二，问物几何？
也就是求解x的一元一次同余方程组
结论:对两两互质的正整数序列mi,M为mi联乘乘积，一元一次同余方程组对模M有唯一解
公式略

作用，对模M下的大数运算因同余性质可使用小数运算代替

印象中这里有秘密分割的应用，利用的就是中国剩余定理，可使密钥分开存放后必须集齐才可完整解密
原则是互质数字序列分割为多个密钥，加密密钥把M中排除掉对应的质数再做加密运算

明天继续第四章公钥密码，学数学果然是催眠和消磨时间的好方法，就是有点费脑子
回想当年大学开学之前看国防科技大学的老师MOOC讲高数证明，每天都能睡的很香
mark当前87页，下一节离散对数

20220613现代密码学读书笔记
后面即将出现大量数学基础，看不懂的建议直接放弃或者先去复习下离散数学

4 公钥密码

4.1 密码学中亿些常用的数学知识

4.1.1 群 环 域

梦回离散数学抽象代数，主要描述数学对象的集合以及他们之间的运算，运算可以是一元或多元，可以有一个或多个
若是集合S上的运算，对任意a,b属于S，ab属于S，则称S对运算是封闭的
若是一元运算，对任意a属于S，a属于S，则称S对运算是封闭的
若对任意a,b,c属于S，有(ab)c=a(bc)，则称*满足结合律

若代数系统<G,*>同时满足封闭性和结合律，则称之为半群

在半群中，若对任意a,b属于S，有ea=ae，则称e为单位元，也叫幺元
对任意a属于S，存在a的逆（a^-1,公式不好输入后面写-a~a或者a逆都是这个意思）使得a * a逆 = a逆 * a = e，则称S内元素均可逆
在半群<G,>中，若G内任意元素均可逆，则称之为群
若G为有限集，则称<G,>是有限群，否则为无限群，其中G的元素个数称为群阶

若对任意a,b属于S，有ab=ba，则称满足交换律
若群<G,>的运算满足交换律则称之为交换群，也叫做Abel群，中文一般叫阿贝尔群
运算一般称之为乘法，对应的群为乘法群，若运算为+加法则称之为加法群

举例：
<I,+>是Abel群，I是整数集
<Q,*>是Abel群，Q是有理数集
设任意集合A，P为A上双射函数集，<P,+>是群, +表示函数合成，通常这个群不是Abel群
PS：既是单射又是满射的映射称为双射
<Zn,+n>是Abel群，其中Zn={0,1,2,…,n-1},
+n是模加a +n b == (a + b) % n
~x == n – x
<Zn,*n>不是群，因为0没有逆元。*n是模乘a *n b == (a * b) % n

若<G,*>是群，I是整数集合，存在元素g属于G，对任意元素a属于G，都有相应的i属于I，使得a==g^i。则称之为循环群，其中g称为生成元

对任意a,b,c属于S，若a*(b+c)==ab+ac且(b+c)a==ba+ca，则称乘法在加法上可分配
若代数系统<R,+,>的二元运算满足<R,+>是Abel群，<R,>是半群，乘法在加法上可分配，则称代数系统<R,+,>是环

若代数系统<F,+,>满足<F,+>是Abel群,<F-{0},>是Abel群,乘法在加法上可分配，则称之为域
同理，元素数量有限的集合对应的域称为有限域，元素个数称为域的阶
若q是素数的幂即q=p^r，其中p为素数r为自然数，则阶为q的域称为伽罗华(Galois)域，记为GF(q)或F(q)

所有实数作为系数的多项式集合R(x)在多项式加法和乘法运算下构成环
同理任意域F上的(系数属于F)多项式集合F(x)在多项式加法和乘法运算下构成环

F(x)中不可约多项式和整数中的素数类似，指的是F上仅能被非0常数或自身的倍数除尽，但不能被其他多项式除尽的多项式
两个多项式的最高公因式为1时,称他们之间互素

多项式系数取自以素数p为模的域F时，这样的多项式集合记为Fp[x]
若m(x)是Fp[x]上的n次不可约多项式，将Fp[x]上多项式加法和乘法改为以m(x)为模的加法和乘法，此时多项式集合Fp[x]/m(x)记为GF(p^n)，集合中元素个数为p^n，它是一个有限域

4.1.2 素数 互素

也就是质数和互质，这个相对简单，小学二年级学过
若a,b是两个整数，b不为0，存在另一个整数m使得a=mb，则称b整除a记为b|a，称b为a的因子
整数性质：
a|1 –> a=1 || a=-1
a|b && b|a –> a = b || a = -b
对任意b!=0，b|0
b|g, b|h –> b|(mg+nh), 其中m,n为任意整数
证明:显然存在g1,h1使得g=bg1,h=bh1
mg + nh == mbg1 + nbh1 == b(mg1 + nh1)
因此得证b|(mg+nh)

如果p的因子只有p,-p,1,-1称p为素数或质数，否则称之为合数。(p>1)
任意整数a都能唯一被分解为质数之间的乘积(a>1)，也就是小学学过的质因数分解（这个不是玩梗，是真的小学学的）

如91=713,11011=711^2*13
11011可表示为{a7=1,a11=2,a13=1}，其中an是素数n的指数

若c同时是a,b的因子，则c是a,b的公因子。
若同时a,b的任意公因子均是c的因子，则称c为a,b的最大公因子，记为c=gcd(a,b)
因最大公因子为整数，因此定义gcd(a,b) == gcd(a,-b) == gcd(-a,b) == gcd(-a, -b)
一般gcd(a,b)==gcd(|a|,|b|)。
因a|0可得gcd(a,0)=|a|，其中a!=0

300 = 2^2 * 3^1 * 5^2
18 = 2^1 * 3^2
gcd(18 * 300) == 2^1 * 3^1 * 5^0 == 6

若gcd(a,b)=1则称a,b互素或互质
如果d是a的倍数也是b的倍数，则称之为公倍数
a和b的任意公倍数若都是d的倍数，则称之为最小公倍数，记为d=lcm(a,b)

若a,b互素，则lcm(a,b) = a * b

4.1.3 模运算

也是小学学过的除法相关的运算
若a == qn + r，其中a是整数，n是正整数，若用n/a，商q余r（其中0<=r<n, q=floor(a/n)）
floor是像负无穷方向取整
若 a % n == b % n 称a和b模n同余，记为 a===b mod n，[a]为同余类集合,a为代表元素

明天继续第四章公钥密码，一个小时才看了4页，可见这节的信息量密度极大。横穿高数和离散大量的内容
mark当前73页

20220609现代密码学读书笔记

3 分组密码

3.1 概述

将明文以长度n分组，各组用独立密钥加密，加密结果长度为m
特性：
1.分组长度n要足够大防止明文穷举攻击，当n=64时用2^32成功率为1/2存储需要2^15MB，无法穷举
2.密钥空间要足够大，防止穷举密钥攻击。但不能太长不便于管理
书上认为30-40年内80bit足够安全，还是低估了硬件性能的发展hhhh
3.由密钥确定的置换算法要足够复杂，充分实现扩散和混淆，没有简单的关系。使对手除了穷举以外无捷径
4.加解密运算简单易于软硬件实现
5.数据扩展尽可能小。一般无扩展，使用同态置换和随机化加密技术时可引入
6.差错传播尽可能小

代换
分组代换如果太小则等价于古典密码，容易通过统计暴露规律。所以分组长度n要大一些，但这样带来的问题就是密钥需要很长。所以需要把n再分段做子代换，每个子代换称之为代换盒，简称S盒。
例如DES种将48bit->32bit的代换用8个S盒实现，每个S盒输入6输出4

扩散和混淆
打乱统计规律，扩散是将明文的统计规律散布到密文中，让密文的1位由明文的多位产生。
混淆是指将密文和明文之间的统计关系变得尽可能复杂

Feistel加密结构
利用乘积密码可获得简单的代换密码，也就是连续执行多个基本密码系统使得结果的强度高于单独的密码系统
Feistel网络中每轮结构都相同，每轮右半数据被作用于函数F后与左半做异或(置换)后交换左右两半数据(代换)，这种结构是Shannon提出的SPN(Substitution-Permutation NetWork)的特有形式

3.2 数据加密标准(DES)

DES分组长度64bit，密钥长度56bit。加密过程如下
1.初始置换IP
2.16轮相同的变换，每轮包含置换和代换。每轮密钥使用初始密钥移位产生子密钥
3.执行IP的逆置换
除了1、3之外DES结构和Feistel密码结构完全一致

S盒有8个，这个S盒和IP置换表的来源没有任何理由，传说它们是有隐藏规律的，但貌似至今无人发现hhhh 需要查查文献才知道最新的进展了

DES一轮不够可以搞多轮继续复杂这个加密过程

3.3 差分密码分析与线性密码分析

差分密码分析是至今为止对迭代密码已知的攻击中最有效的方法，通过分析明文对儿的插值对密文对儿的插值的影响来恢复某些密钥bit

线性密码分析是对迭代密码的一种已知明文攻击，利用密码算法中的不平衡的线性逼近

3.4 分组密码的运行模式

ECB(Electronic CodeBook) 每个明文组独立的用同一个密钥加密
CBC(Cipher Block Chaining) 加密算法的输入是当前明文组与前一密文组的异或运算
CFB(Cipher FeedBack) 每次只处理输入的j比特位，将上一次的密文用作加密算法的输入来产生干扰值，以此干扰值与当前明文异或作为密文输出
OFB(Output FeedBack) 与CFB类似，输入的是前一次加密算法的输出

3.5 IDEA(International Data Encryption Algorithm)

明文密文都是64bit,密钥128bit
过程比Feistel更加复杂
64bit拆分为16bit4
进行8轮迭代，每轮使用16bit6个子密钥
输出变换使用16bit*4个子密钥

3.6 AES(Advanced Encryption Standard)

Rijndael最终获选，设计策略为Wide Trail Strategy，针对差分分析和线性分析的抵抗
数学基础是GF(2^8)域内的运算，还是抽象代数的概念，在这个域上定义了几种常用运算
设计思想
1.抵抗所有已知攻击
2.多个平台上速度快，编码紧凑
3.设计简单

使用3个不同的可逆均匀变换，每个变换完成自己的目标
1.线性混合层确保多轮之上的高度扩散
2.非线性层确保输出在最坏情况下具有非线性特征，并行使用满足这个特性的S盒
3.密钥加层，单轮的子密钥异或到中间状态上

明天继续第四章公钥密码
mark当前69页

20220608现代密码学读书笔记

2 流密码

2.1 基础概念

分组密码的滚动密钥无状态，不受输入明文的影响
流密码的滚动密钥有状态，会受输入过明文影响

根据密钥流发生器的状态是否依赖于输入的明文，可分为同步和自同步。
GF域为也就是伽罗华域(Galois Field)
域的概念欢迎复习下离散数学和抽象代数…

2.2 线性反馈移位寄存器(LFSR)

一种逻辑结构可用硬件实现，输出的内容受之前输入的影响
因状态最多有2^n个，寻找合适的反馈函数可使状态周期最大，此时的序列称之为m序列

2.3 线性移位寄存器的一元多项式表示

为了找到m，进行数学表达后求证，证明过程看不懂。。。

2.4 m序列的为随机性

因为总状态空间是有穷的，因此一定有周期，但只要周期足够长，相对的小范围内看不出规律就可以，这种序列称为伪随机

若01序列{ai}=(a1a2a3)为00110111,前两个0称之为0的2游程，后面是1的2游程，0的1游程和1的3游程

期望良好的特性
1.01出现概率基本相同
2.01出现的位置概率相同
3.对序列和平移后的序列比较不能得出任何信息
4.序列的周期要足够大
5.序列的计算要容易
6.由密文和相应的明文部分信息，无法确定整个随机序列

这里外个楼，之前某游戏公司数据库出问题回档后，有人发现抽卡结果没有任何变化hhhhh。也就是说随机种子和账号是强相关的，一个账号是非还是欧都已命中注定

2.5 m序列密码的破译

列多元方程，使用矩阵求逆可反推寄存器连续的n+1个状态。条件要求比较多，所以理论上可行

2.6 非线性序列

既然线性序列可能被攻破，那组合多个线性生成器的结果让最终输入的线性特征被破坏就ok了
Geffe序列生成器：使用三个LFSR组合实现输出
J-K触发器：使用J-K触发器输出的特性打乱输出规律。输出依赖于前一个输入
Pless生成器：组合使用LFSR和J-K触发器
钟控序列生成器：组合两个LFSR和时钟的脉冲，第一个LFSR的输出会和脉冲信号作为第二个LFSR的输入，打乱第二个的输出

密钥流生成器的不可预测性基本原则
1.周期长
2.高线性复杂度
3.统计性能良好
4.足够“混乱”
5.足够“扩散”
6.抵抗不同形式的攻击

明天继续第三章分组密码
mark当前30页