下载文档原格式
回忆：Vigenère密码•加密消息：INDIVIDUAL CHARACTER密钥：HOSTm=I ND I V I DU ALCH ARAC TERk=HOST HOST HOST HOST HOSE k(m)=P BV B C W VN HZUA HFSV ASJ1One-Time Pad•用和明文一样长的随机密钥流K •加密:M = C = K = Z2nc i = mi⊕kiOTP: 安全性分析•定理:OTP is Unconditional Security3第五章流密码•流密码总览•伪随机序列发生器(Pseudorandom Number Generation)•PRNGs-Linear Feedback Shift Register (LFSR)-Blum Blum Shub(BBS)•流密码4流密码•一次一密(OTP): C=P⊕K ，K 是随机密钥流•流密码:–思想: 代替“随机”为“伪随机”–用Pseudorandom Number Generator (PRNG)–PRNG: {0,1}s→{0,1}n–种子是秘密密钥•C=M⊕PRNG(seed)56回忆分组密码•加密消息的方式–分组密码•c=(c 1c 2…)(c i c i+1…)... = e K (m 1m 2...) e K (c i c i+1…)…–流密码•c=c 1c 2…=e k1(m 1)e k2(m 2)…•密钥流(k 1,k 2,…)流密码：性质•数学性较好–OTP 绝对保密–伪随机有很长的研究历史•加密速度很快–基于“⊕”•密钥流只能用一次–已知明文攻击–PRNG的周期应该足够长•应用很广–Network, DVD,移动通信8第五章流密码•流密码总览•伪随机序列发生器(Pseudorandom Number Generation)•PRNGs-Linear Feedback Shift Register (LFSR)-Blum Blum Shub(BBS)•流密码9伪随机数应用•相互认证–使用一次性随机数来防止重放攻击•会话密钥的产生–用随机数作为会话密钥•公钥密码算法中密钥的产生–用随机数作为公钥密码算法中的密钥–以随机数来产生公钥密码算法中的密钥10密码学中对伪随机数的要求•随机性–均匀分布：数列中每个数出现的频率相等或近似相等•不可预测性–密码分析者很难从数列前边的数预测出后边的数11PRNG•定义:一个伪随机序列发生器G是一个确定的多项式算法，使得–∃l(n)>n, ∀x, |G(x)| = l(|x|)–伪随机性:{G(U n); n≥1} 同一个随机序列{U l(n);n≥1}是多项式不可区分的12伪随机性•定义:两个随机序列{X n; n≥1} 和{Y n; n≥1}是多项式不可区分的，如果:∀多项式布尔函数f: {0,1}*→{0,1}∀正的多项式p(x) 和n≥N|Pr(f(X n)=1) –Pr(f(Y n)=1)| < 1/p(n)•定义:两个随机序列{X n; n≥1} 和{Y n; n≥1}是统计不可区分的，如果:∆(n) = ½Σx∈{0,1}n|Pr(X n=x) -Pr(Y n=x)| < 1/p(n)13Golomb随机性检测1）在序列的一个周期内，0和1的个数相差至多为12）在序列的一个周期内，长为1的游程占总游程数的1/2，长为2的游程占总数的1/22，…长为i的游程占游程总数的1/2i，…，且在等长的游程中，0和1游程个数至多相差为13）异自相关函数是一个常数•满足以上三个条件的序列称为伪随机序列，也称为拟噪声序列(Pseudo Noise Sequence,PN序列)15举例•讨论序列：1010111011000111110011010010000 1010111011000111110011010010000...是否满足Golomb随机性检测的前2个条件？•周期：31•0的个数15；1的个数16•0和1的1-游程个数都为4；0和1的2-游程个数都为2；0和1的3-游程个数都为1；0的4-游程个数为1 1的4-游程个数为0；0的5-游程个数为0；1的5-游程个数为1•i-游程个数占游程总数的1/2i16第五章流密码•流密码总览•伪随机序列发生器(Pseudorandom Number Generation)•PRNGs-Linear Feedback Shift Register (LFSR)-Blum Blum Shub(BBS)•流密码17LFSR的最大长度•定理:LFSR的最大序列长度是2n-1, ( n 指寄存器个数)•Proof:–For K={k0, k1,…, k L}, there are 2L different states–The sequence for K is K1,K2,…,K2L,K i,…K i must be in K1,K2,…,K2L•So repeated–If bits in K are all zero, should be excluded–So 2L-125m-序列（m-sequence)•定义:由LFSR产生的最大长度序列是m-序列}说明:•m-序列{zi–{z} 的周期是：2n-1i–满足Golomb随机性检测•在一个周期内, 0和1的个数是2n-1-1及2n-1•其它…26m-序列内涵•定理：{ai } 是m-序列当且仅当它的特征多项式p(x)是本原多项式•定义：如果p(x)的次数是n，且其周期为2n-1，则称p(x)为本原多项式•定义：设p(x)为GF(2)上的多项式，使式子p(x)|x p-1成立的最小正整数p称为p(x)的周期2829线性复杂性•设{a i } 的线性复杂性是L •已知明文攻击:•复杂性:–L 已知: 用线性关系O(L)–L 未知:用Berlekamp-Massey 算法O(L 2)=L 21c .c c ..⎢⎢⎢⎣⎡⎢⎥⎥⎥⎥⎦⎤n+L-1n+1n a .a a ..⎢⎢⎢⎣⎡⎢⎥⎥⎥⎥⎦⎤n+L-2n n-1a .a a ..⎢⎢⎢⎣⎡⎢n+L-3n-1n-2a .a a ...…..n-1n-L +1n-L a .a a ..⎥⎥⎥⎥⎦⎤……实际应用中的非线性序列•对于非线性序列的研究还在初级阶段•实际应用中的非线性序列–用m-序列作为驱动序列–非线性混合序列–钟控序列31钟控序列•思想:用一些m-序列来驱动其它m-序列•Advantages:–Its linear complexity is exponential with the number of registers in LFSR–Its linear complexity can be controlled easily •Disadvantages:–Not good randomness–Many long runs33第五章流密码•流密码总览•伪随机序列发生器(Pseudorandom Number Generation)•PRNGs-Linear Feedback Shift Register (LFSR)-Blum Blum Shub(BBS)•流密码35Blum Blum Shub发生器•产生伪随机序列的另一种方法：基于数论中的难题•Shamir发生器–分解问题•BBS 发生器–二次剩余问题3637Blum Blum Shub 发生器1. 产生两个大的素数p 和q (p ≡q ≡3 mod 4)2. 计算n=pq3. 选择一个随机的整数x ，gcd(x,n)=14. BBS 的初始输入是: x 0≡x 2(mod n )5. 最后,BBS 通过如下过程产生一个随机的序列b 1 b 2 b 3…:a) x j ≡x j-12(mod n )b) b j 是x j 的最低有效比特BBS发生器：举例1. 产生：p=24672462467892469787q=3967368945678345898032. 则n=97884761408531107941688552174137157819613. 选择x=8732456478884783490134. 则初始输入就是：x≡x2(mod n)≡884529871047878009708991774601012286317238BBS发生器：举例5. 由公式x j≡x j-12(mod n)可得x1，x2，…，的值：x1 ≡7118894281131329522745962455498123822408 x2 ≡3145174608888893164151380152060704518227 x3 ≡4898007782307156233272233185574899430355 x4 ≡3935457818935112922347093546189672310309 x5 ≡675099511510097048901761303198740246040 ... ...b2 b3 b4 b5 …=01110…则产生的序列是b139BBS发生器分析•Fact:If there is a distinguisher D which tells BBS from random sequence, then D can be converted into a probabilistic polynomial-time algorithm A which guess the x-1mod 2 givenx0∈Z N Q+ (D⇒A)40第五章流密码•流密码总览•伪随机序列发生器(Pseudorandom Number Generation)•PRNGs-Linear Feedback Shift Register (LFSR)-Blum Blum Shub(BBS)•流密码41流密码设计目标•设计一个性能良好的流密码是一项困难的任务：–长周期–高线性复杂度–统计性能好–足够的“混乱”42A543A5 说明•钟控序列–由3个m-序列驱动–由3个LFSRs产生–主要函数是非线性的•应用–A5 可以在GSM中保护语音通信44了解RC4•Designed by Ron Rivest in 1987, public in 1994•Simple and effective design–Very fast and very easy to remember•Byte-oriented stream cipher–The internal states is a byte array S[0..255]–S[0..255] is a permutation of 0 to 255•Applications–In SSL to protect the Internet traffic–In WEP to protect the wireless links45RC4：初始化•Produce a initial permutation from the key K(K is divided into L bytes. In fact, this is a pad)•Initialisation:for i=0to 255 do S[i] = i;j =0;for i=0to 255 doj= (j +S[i] + K[I mod L]) mod 256;swap (S[i], S[j]);46RC4: 加密•Two indexes: i, j with i=j=0•Produce one byte of keystream Ks:i = (i + 1)mod 256;(Loop for next Ks)j = (j + S[i])mod256;swap (S[i], S[j]);t = (S[i] + S[j])mod256;Ks = S[t];•Encryption: C i= M i⊕S[t]47RC4安全•RC4的周期是：256! ≈21700•宣称可抵抗已知的所有攻击–有一些分析, 没有实践49总结•流密码总览•伪随机序列发生器(Pseudorandom Number Generation)•PRNGs-Linear Feedback Shift Register (LFSR)-Blum Blum Shub(BBS)•流密码-A5-RC450。
流密码0000目前关于流密码的理论和技术已取得长足的发展。
同时密码学家也提出了大量的流密码算法，有些算法已被广泛地应用于移动通信、军事外交等领域。
流密码的原理:在流密码中，明文按一定长度分组后被表示成一个序列，并称为明文流，序列中的一项称为一个明文字。
加密时，先由主密钥产生一个密钥流序列，该序列的每一项和明文字具有相同的比特长度，称为一个密钥字。
然后依次把明文流和密钥流中的对应项输入加密函数，产生相应的密文字，由密文字构成密文流输出。
即设明文流为:M=m1m2…mi…密钥流为:K=k1k2…ki…则加密算法为:C=c1c2…ci…=Ek1(m1)Ek2(m2)…Eki(mi)…解密算法为:M=m1m2…mi…=Dk1(c1)Dk2(c2)…Dki(ci)…流密码与分组密码在对明文的加密方式上是不同的。
分组密码对明文进行处理时，明文分组相对较大。
所有的明文分组都是用完全相同的函数和密钥来加密的。
而流密码对明文消息进行处理时，采用较小的分组长度(一个分组称为一个字或一个字符)，对明文流中的每个字用相同的函数和不同的密钥字来加密。
1.一次一密下面介绍一下一次一密密码体制。
以逐比特加密的一次一密为例，它要求对明文消息的每个比特做一次加密，而且加密每个明文比特时，都要独立随机地选取一个密钥比特。
无论明文的统计分布如何，一次一密都是无条件安全的，并且它使用的密钥量在所有无条件安全的密码体制中是最小的，因此，从这个意义上来说，一次一密无疑是最优的。
一次一密的一个明显缺点就是它要求密钥与明文具有相同长度，这增加了密钥分配与管理的困难，这一缺陷极大地限制了它在实际中的应用。
流密码采用了类似于一次一密的思想，但加密各明文字的密钥字不是独立随机选取的，而是由一个共同的较短的主密钥按一个算法产生的。
因此，它不具有一次一密的无条件安全性，但增加了实用性，只要算法设计得当，其安全性可以满足实际应用的需要。
流密码通常分为同步和自同步两类。
流密码中密码函数的设计与分析流密码中密码函数的设计与分析流密码是一种在加密和解密过程中，使用连续的密钥流与明文流进行按位异或操作的加密算法。
密码函数是流密码中的核心部分，它负责生成复杂的密钥流，以保证加密的安全性和强度。
本文将讨论流密码中密码函数的设计原则和分析方法，并以一些常用的密码函数为例进行深入讨论。
密码函数的设计原则有两个关键要素：复杂性和非线性。
复杂性要求密码函数设计要足够复杂，以保证生成的密钥流不可预测，从而增加破解的难度。
非线性则要求密码函数必须有足够的非线性特性，以避免产生线性关系，从而增强密码的强度。
常见的密码函数设计包括置换密码函数、混沌密码函数和伪随机数生成器（PRNG）密码函数等。
置换密码函数通过对原始数据进行块置换来生成密钥流，其原理是通过将输入数据的某些位进行调换来生成密钥流，使得生成的密钥流与明文流在位级上具有复杂的关系。
混沌密码函数则利用非线性动力学系统的混沌特性，通过陷入混沌运动的系统来生成密钥流。
伪随机数生成器（PRNG）密码函数则是基于随机数生成器的算法，通过伪随机数序列来生成密钥流。
这些密码函数设计的关键在于如何利用复杂性和非线性的特性来生成高强度的密钥流。
在密码函数设计中，分析密钥流的统计特性是非常重要的。
常见的统计特性包括平衡性、独立性和非相关性。
平衡性是指密钥流中0和1出现的概率应该接近于均等，以保证密钥流的统计性质。
独立性是指密钥流的各个位应该是独立的，即每一位的取值不会受到前一位或后一位的影响。
非相关性是指密钥流中各个位之间应该没有相关性，即每一位的取值不会受到其他位的影响。
通过分析这些统计特性，可以评估密码函数的安全性和强度。
为了提高密码函数的强度，设计者还可以采用一些增强技术。
一种常见的增强技术是使用密钥编排算法，即将初始密钥通过一系列的置换和替换操作得到更复杂的密钥流。
另一种增强技术是引入扩散机制，即通过复杂的运算使得输入的微小变化能够在输出中得到明显的扩散效果，增加密钥流的随机性。
分组密码与流密码的分析设计与比较1引言随着科技的发展，信息安全在现代电子通信等方面发挥着越来越重要的作用密码编码学是应对各种信息安全威胁的最有效的方法。
所谓密码编码学，是指生成高强度、有效的加密或认证算法。
欲传送的原始信息叫做明文，对其进行可逆的数字变换后的信息称为密文。
发送者通过加密算法对明文进行加密，得到密文，这个过程称为加密。
接收者收到经过处理的密文后，通过解密算法，还原成明文，这一过程称为解密。
密码系统所采取的基本工作模式叫做密码体制，主要分为两大类：对称密钥密码体制与非对称密钥密码体制。
对称密钥密码体制中的加密密钥与解密密钥相同，需要安全可靠的密钥传递信道，通信双方需保管好密钥。
非对称密钥密码体制中加密与解密分别有一个对应的密钥，发送者查询接收者公开的公钥对明文进行加密，接收者收到密文后再利用只有自己知道的私钥进行解密。
对称密钥密码体制又分为两大类，分别是分组密码与流密码。
所谓分组密码，就是按照算法设计者预先设定的长度把明文分割成块，再对每一分组进行加密解密的算法。
而对比特进行运算、采用"一次一密"的算法，则称为流密码。
2分组密码2.1 概论所谓分组密码，其明文分为若干个数据块，加密后得到的密文仅与给定的密钥算法和密钥有关，与被处理的明文数据块在整个明文中所处的位置无关。
较典型的分组密码算法有DES算法、IDEA算法、AES算法等。
算法设计者事先设定好分块的长度，算法将明文按照该长度进行分组，再在这些定长的分组上进行运算。
在分组密码的设计中，加密与解密的处理是建立在块的基础上。
算法把明文分成设定的大小，通常为64 bit或128 bit，再对每个块单独编码。
2.2 设计原则创立了经典信息论的数学家C.E.Shannon在1949年时发表了一篇名为"《保密系统的通信理论》的论文。
在这篇论文中，Shannon提出了如何设计分组加密的组合密码系统。
其中，设计分组密码需要依据两个一般原则，分别是混淆原则和扩散原则。
几类流密码基本部件的设计与分析几类流密码基本部件的设计与分析流密码是一种常见的加密算法，它利用伪随机数流与明文进行异或操作，从而实现数据的加密。
流密码基本部件是流密码算法中的关键因素，其设计和分析对流密码的安全性和效率至关重要。
本文将探讨几类流密码基本部件的设计与分析，包括线性反馈移位寄存器（LFSR）、非线性滤波器（NLFSR）、置换盒（S盒）和混合置换盒（SPN）。
首先，我们来看LFSR。
LFSR是流密码中最常用的基本部件之一，它是一种寄存器，具有线性反馈结构。
LFSR的设计与分析需要考虑多个因素，如寄存器长度、反馈函数和初始状态等。
寄存器长度决定了LFSR的周期长度，长度越长，密码的安全性提高。
反馈函数的选择也很重要，应该避免线性的反馈函数，以免导致密码易受线性攻击。
初始状态的选择则会影响LFSR的状态序列，应该选择一个具有较高复杂度的初始状态。
接下来，我们介绍NLFSR。
NLFSR是一种非线性反馈移位寄存器，它在LFSR的基础上引入了非线性变换。
对于NLFSR的设计与分析，关键在于非线性变换函数的选择。
合适的非线性变换函数能够增加密码的复杂度，提高密码的安全性。
常用的非线性变换函数包括布尔函数和S盒。
S盒是流密码算法中的重要组成部分，它用于将明文与密钥进行混淆。
S盒的设计与分析需要考虑多个方面，如非线性、混淆度和抗差分攻击性能等。
非线性是S盒的关键特性，通过引入非线性变换，可以增加密码的安全性。
混淆度是衡量S盒复杂度的指标，混淆度越高，密码越难破解。
抗差分攻击性能是指S盒在差分密码分析中的安全性，高抗差分攻击性能能够提高密码的安全强度。
最后，我们介绍SPN。
SPN是一种流密码结构，它将置换和混淆两个操作结合起来，加强加密的安全性。
SPN的设计与分析需要综合考虑置换函数和混淆函数的特性。
置换函数用于乱序明文，减少明文的结构特征。
混淆函数则通过对明文进行替换、替代和混淆操作，增加密码的复杂度和随机性。
分组密码与流密码的分析设计与比较1引言随着科技的发展，信息安全在现代电子通信等方面发挥着越来越重要的作用密码编码学是应对各种信息安全威胁的最有效的方法。
所谓密码编码学，是指生成高强度、有效的加密或认证算法。
欲传送的原始信息叫做明文，对其进行可逆的数字变换后的信息称为密文。
发送者通过加密算法对明文进行加密，得到密文，这个过程称为加密。
接收者收到经过处理的密文后，通过解密算法，还原成明文，这一过程称为解密。
密码系统所采取的基本工作模式叫做密码体制，主要分为两大类：对称密钥密码体制与非对称密钥密码体制。
对称密钥密码体制中的加密密钥与解密密钥相同，需要安全可靠的密钥传递信道，通信双方需保管好密钥。
非对称密钥密码体制中加密与解密分别有一个对应的密钥，发送者查询接收者公开的公钥对明文进行加密，接收者收到密文后再利用只有自己知道的私钥进行解密。
对称密钥密码体制又分为两大类，分别是分组密码与流密码。
所谓分组密码，就是按照算法设计者预先设定的长度把明文分割成块，再对每一分组进行加密解密的算法。
而对比特进行运算、采用"一次一密"的算法，则称为流密码。
2分组密码2.1 概论所谓分组密码，其明文分为若干个数据块，加密后得到的密文仅与给定的密钥算法和密钥有关，与被处理的明文数据块在整个明文中所处的位置无关。
较典型的分组密码算法有DES算法、IDEA算法、AES算法等。
算法设计者事先设定好分块的长度，算法将明文按照该长度进行分组，再在这些定长的分组上进行运算。
在分组密码的设计中，加密与解密的处理是建立在块的基础上。
算法把明文分成设定的大小，通常为64 bit或128 bit，再对每个块单独编码。
2.2 设计原则创立了经典信息论的数学家C.E.Shannon在1949年时发表了一篇名为"《保密系统的通信理论》的论文。
在这篇论文中，Shannon提出了如何设计分组加密的组合密码系统。
其中，设计分组密码需要依据两个一般原则，分别是混淆原则和扩散原则。
实验 2 流密码设计
成绩
专业班级信息111 学号201112030208 姓名王昕报告日期.
实验类型: ○验证性实验○综合性实验●设计性实验
实验目的：学会设计流密码，同时理解流密码生成的原理。
理解线性反馈移位寄存器的序列与本源多项式的关系。
实验要求：设计流密码，密码生成器包括两部分：包括驱动部分和线性组合部分。
驱动部分由LFSR实现，线性组合部分由相关原理实现。
用软件实现LFSR线性反馈移位寄存器，同时要按获取m序列。
线性组合部分，实现Geffe序列生成器，J-K触发器，Pless生成器。
实验内容：
对于流密码实验，我基本使用java开发。
自己设计了工具箱，然后实现LFSR，最后线性组合为相应密钥流生成器。
1，工具箱集中在Mathtools类中。
包括一些最基本的运算，比如模2加减乘除，包括单个数的模2加减乘除还有多位数的模2加减乘除。
模2加法：
模2乘法：
模2除法：
判断是否为本源多项式：
2，对于线性反馈移位寄存器的实现有两种初始值，一种是本源多项式，另一种是不确定是否为本源多项式。
初始值为本源多项式：
不确定是否为本源多项式：
3，基本工具设计完成后就开始实现线性组合部分，同时生成相应生成器。
不同生成器，采用不同的逻辑，但都会调用LfsrMax（初始值为本源多项式）或LFSR （初值不确定是否为本源多项式）函数。
在实现线性组合时，还是建了一个新类，StreamCode,线性组合分别用相应方法实现。
Geffe生成器:
JK触发器：
Pless生成器如下：
函数调用举例
结果如下：
实验总结：
流密码的基本思想是利用密钥k产生一个密钥流Z=Z0Z1...，并使用如下规则对明文串X=X0X1X2…加密：Y=Y0Y1Y2…=E Z0(X0)E Z1(X1)E Z2(X2)…。
密钥流由密钥流发生器f产生：z i=f(k,σi),这里σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数。
流密码是对称密码算法的一种。
序列密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点，因此在实际应用中，特别是专用或机密机构中保持着优势，典型的应用领域包括无线通信、外交通信。
