下载文档原格式
第二章流密码一、填空：1. 分组密码和流密码的根本区别在于_______________________________2. n-LFSR最大周期是 __________3. 已知一3-FSR，其反馈函数为f(a i,a2,a3)=a i 二a2a3，且当前的状态(a s,a2,a i)=(101)，则其前两个状态分别是____________ ，输出序列的周期是_____________4. n级m序列的异相自相关函数值为_____________________5. 序列｛a i｝为m序列的充要条件是___________________________________6. 已知｛a i｝为m序列，且在该序列中最大0游程为4,则该序列的周期是________7. 已知p(x)=x3+x+1,贝U其产生的非0序列的异相自相关函数值是_________8. n级M序列的周期是 ______________9. 已知一钟控生成器由LFSR1控制LFSR2,极小多项式分别为f1(x)=1+x+x3和f2(X)= 1+X2+X3，则产生序列的周期为 ___________________ 线性复杂度为10. 已知LFSR1为一10级m序列，LFSR2为以5级m序列，则构成的钟控序列的周期为_______ 线性复杂度为_______________11. n级m序列中长为i的1游程有多少 ______ ，长为n的1游程有多少______ ，长为n的0游程有几个___12. 至少知道_________ 连续的密钥流bit可以破译m序列13. RC4算法的最大密钥长度是___________14. 已知某一n级LFSR其非零状态的状态转移图为一个大圈，则其产生的非0序歹U的周期是______15. eSTREAM计划候选算法Grain v1的密钥长度________ 针对硬件还是软件开发的___________二、选择：每一项有1个或多个选项是正确的1. 下面哪些多项式可以作为非退化的5-LFSR的反馈函数(状态转移函数) _____4 5 4 5A. 1+x+xB. X1 二X2二X4x5C. 1+x+xD. x +x2•对于一个n-LFSR，设其序列生成函数为A(x)，特征多项式p(x)，全0状态除夕卜，则下面那个要素与其它要素不是--------- 对应的__________A.①(x),满足A(x)=①(x)/p(x)B.初始状态C. p(x)D. G(p(x))中的序列3. 一个LFSR的极小多项式为p(x)，其所生产的序列也都能由特征多项式为t(x)的LFSR 产生，则gcd(p(x),t(x))= _______A. p(x)B. t(x)C. 1D.次数大于1的某个g(x)，且不等于p(x)和t(x)4. 下面哪个选项不是Golomb对伪随机周期序列提出的随机性公设____________A.在一个周期内0和1个数至多差1B.长为i的游程占游程总数的1/2'C.异相自相关函数为常数D.任意比特的下一比特不可预测5. 哪些组合通常作为密钥流产生器的状态转移函数和输出转移函数_________A.线性的©和线性的书B.线性的©和非线性的书C.非线性的©和线性的书D.非线性的©和非线性的书三、判断：(正确的划””，错误的划””以下同)1. 在流密码中，只要被加密的明文长度小于密钥流序列的周期，就可以达到无条件安全了( ) 2. 只要LFSR产生的序列的周期足够大，就能够达到计算上安全的，可用于作为密钥流序列( )3. 流密码中如果第i个密钥比特与前i-1个明文有关则称为同步流密码()4. LFSR的初始状态对其产生序列的周期没有任何影响()5. 序列｛a'｝的生成函数为A(x)=©(x)/p(x)，p(x)的次数大于1，则必有G(p(x))中的一个序列，满足A(x)=x/p(x) ( )6. LFSR产生的序列中有一条序列是m序列，则所有非0序列都是m序列( )7. 钟控序列的线性复杂度是指产生钟控序列的密钥流产生器中包含的移位寄存器的总级数( )8. n级m序列中，存在两个0的n-1游程。
第二章流密码一、填空：1. 分组密码和流密码的根本区别在于____________________________2. n-LFSR最大周期是__________3. 已知一3-FSR，其反馈函数为f(a1,a2,a3)=a1⊕a2a3，且当前的状态(a3,a2,a1)=(101)，则其前两个状态分别是____________，输出序列的周期是____________4. n级m序列的异相自相关函数值为____________________5. 序列{a i}为m序列的充要条件是_________________________________6. 已知{a i}为m序列，且在该序列中最大0游程为4，则该序列的周期是_______7. 已知p(x)=x3+x+1, 则其产生的非0序列的异相自相关函数值是________8. n级M序列的周期是____________9. 已知一钟控生成器由LFSR1控制LFSR2，极小多项式分别为f1(x)=1+x+x3和f2(x)=1+x2+x3，则产生序列的周期为___________________，线性复杂度为______________________。
10. 已知LFSR1为一10级m序列，LFSR2为以5级m序列，则构成的钟控序列的周期为______,线性复杂度为______________11. n级m序列中长为i的1游程有多少_____，长为n的1游程有多少_____，长为n的0游程有几个___12. 至少知道_________个连续的密钥流bit可以破译m序列13. RC4算法的最大密钥长度是___________14. 已知某一n级LFSR其非零状态的状态转移图为一个大圈，则其产生的非0序列的周期是________15. eSTREAM计划候选算法Grain v1的密钥长度______是针对硬件还是软件开发的__________二、选择：每一项有1个或多个选项是正确的1. 下面哪些多项式可以作为非退化的5-LFSR的反馈函数(状态转移函数)_____A. 1+x+x4B. x1⊕x2⊕x4x5C. 1+x+x5D. x4+x52．对于一个n-LFSR，设其序列生成函数为A(x)，特征多项式p(x)，全0状态除外，则下面那个要素与其它要素不是一一对应的________A. Ф(x)，满足A(x)=Ф(x)/p(x)B. 初始状态C. p(x)D. G(p(x))中的序列3. 一个LFSR的极小多项式为p(x)，其所生产的序列也都能由特征多项式为t(x)的LFSR产生，则gcd(p(x),t(x))=_________A. p(x)B. t(x)C. 1D. 次数大于1的某个g(x)，且不等于p(x)和t(x)4. 下面哪个选项不是Golomb对伪随机周期序列提出的随机性公设_________A. 在一个周期内0和1个数至多差1B. 长为i的游程占游程总数的1/2iC. 异相自相关函数为常数D. 任意比特的下一比特不可预测5. 哪些组合通常作为密钥流产生器的状态转移函数和输出转移函数______A. 线性的φ和线性的ψB. 线性的φ和非线性的ψC. 非线性的φ和线性的ψD. 非线性的φ和非线性的ψ三、判断：(正确的划”√”，错误的划”⨯”，以下同)1. 在流密码中，只要被加密的明文长度小于密钥流序列的周期，就可以达到无条件安全了（）2. 只要LFSR产生的序列的周期足够大，就能够达到计算上安全的，可用于作为密钥流序列（）3. 流密码中如果第i个密钥比特与前i-1个明文有关则称为同步流密码( )4. LFSR的初始状态对其产生序列的周期没有任何影响( )5. 序列{a i}的生成函数为A(x)=Ф(x)/p(x)，p(x)的次数大于1，则必有G(p(x))中的一个序列，满足A(x)=x/p(x) ( )6. LFSR产生的序列中有一条序列是m序列，则所有非0序列都是m序列（）7. 钟控序列的线性复杂度是指产生钟控序列的密钥流产生器中包含的移位寄存器的总级数（）8. n级m序列中，存在两个0的n-1游程。
现代密码学第二讲-----密码学历史、序列密码郑东2.1.古典密码密码学的历史已有4000多年 古埃及人曾把象形文字写在石碑上2.1.1Caesar Cipher-恺撒密码 2千年前，Julius Ceasar 使用了一种简单的替换密码-——后被人称为恺撒密码（Caesar cipher ） 首先被应用于军事上(cf Gallic Wars ) 替换方法，每个字母用其后的第三个字母替换eg. L FDPH L VDZ L FRQTXHUHG -> I CAME I SAW I CONQUERED Caesar cipher 可以描述如下：Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC 练习解密"RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV"2.1.2.恺撒密码的一般形式 一般形式，可以把Caesar cipher 中字母移动的位数由3变为1-25中的任何一个可以指定一个密钥字母作为字母A 的密文。
例如：密钥字母F 表示：A F,B —G, ... Y —D, Z —E 即每个字母移动5位共有26种可能的密码算法（25种可用）2.1.3.混合单码替换密码 不仅仅是移位变换每个字母可以用其它任何一个字母替换（不能重复） 每个字母可以随机的映射到其它一个 因此密钥长度是26个字母单字母替换密码（Monoalphabetic Substitution Cipher ）例如：明文: ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: IFWEWISHTOREPLACELETTERS Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA2.1.4.简单的单码替换密码 混合单码密码有26个字母长的密钥 需要一种简单方法指定密钥有多种方法，一种简单方法是写没有重复字母的“密钥字”，其它字母按顺序写在密钥字最后字母后面例如，给定密钥字"JULIUSCAESAR" Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher:JULISCAERTVWXYZBDFGHKMNOPQ2.1.5单码替换密码历史 不同种类的替换密码用在政府和军事上 频率攻击方法由阿拉伯科学家提出 最早的攻击描述:"A Manuscript on Deciphering Cryptographic Messages", published in the 9th century2.1.6. Vigenère Cipher Blaise de Vigen ère 发明了多字母替换密码（polyalphabetic substitution cipher ） 使用多个单字母替换表因此一个字母可以被多个字母替换 方法，用一个密钥选择对每个字母使用哪个字母表密钥的第I 个字母表示使用第ith 个字母表 依次使用每个字母表当密钥的字母使用完后，在从头开始2.1.7. Vigenère Example 例：写出明文在明文下重复写出密钥字依次使用每个字母作为caesar cipher 的密钥 加密对应的明文字母PlaintextTHISPROCESSCANALSOBEEXPRESSED Keyword CIPHERCIPHERCIPHERCIPHERCIPHE Plaintext VPXZTIQKTZWTCVPSWFDMTETIGAHLH2.1.8 Vigenère Example （续） C -> CDEFGHIJKLMNOPQRSTUVWXYZAB I -> IJKLMNOPQRSTUVWXYZABCDEFGH P -> PQRSTUVWXYZABCDEFGHIJKLMNO H -> HIJKLMNOPQRSTUVWXYZABCDEFG E -> EFGHIJKLMNOPQRSTUVWXYZABCD R -> RSTUVWXYZABCDEFGHIJKLMNOPQ ABCDEFGHIJKLMNOPQRSTUVWXYZto map the above plaintext letters. ‘T' uses key 'C' maps to 'V' ‘H' uses key 'I' maps to 'P' ‘I' ises key 'P' maps to 'X'etc2.1.9 Vigenère Cipher 的历史 可以看出，越安全的密码使用起来越复杂 因此，在有些场合还可以看到单码替换密码 使得vigen ère cipher 逐渐被各国使用 1854年，首次被Charles Babbage 攻破，但没有公开Friedrich Kasiski 于1863年攻破并发表 此密码的各种变形被沿用到20世纪2.1.10 Ciphers Machines 1--1 为了简化加密/解密过程，导致密码设备出现 Jefferson cylinder , 1790s 被研制成功，包含36个圆盘，每个圆盘有个随机字母表1920年还被美国军队使用2.1.11 Ciphers Machines 1--2 Wheatstone disc , by Wadsworth in 18172.1.12. Ciphers Machines随着密码技术的提高，要求有更高级的密码装置高级密码装置可以实现更复杂的密码这些装置在二战时期广泛使用例：the German Enigma,the Swedish Hagelin (below)and the Japanese Purple2.1.1puters and Cryptography现代电子系统与计算机能够实现更复杂的密码系统70年代中期, 首次出现了现代分组密码—DES 70年代末, 公钥密码学问世直到今天,我们使用的密码学系统参考文献：《密码传奇-从军事隐语到电子芯片》上海译文出版社2.2 序列密码流密码(也称序列密码)：将被加密的消息m 分成连续的符号(一般为比特串)，m=m 1m 2m 3……；然后使用密钥流k=k 1k 2k 3……中的第i 个元素k i 对ｍ的第i 个元素m i 执行加密变换，i =1,2,3,……；所有的加密输出连接在一起就构成了对m 执行加密后的密文。
