复旦大学：《密码学基础》课程教学资源（课件讲稿）06 Stream Cipher

密码学基础(06) Stream cipher 復大辱软件学院 LiJT

LiJT 1 gÉbXË06 Stream Cipher

Stream Cipher Simple Stream Ciphers Attacks on Stream Ciphers Random bit generation RC4 Algorithm 復大辱软件学院 LiST

LiJT 2 Stream Cipher • Simple Stream Ciphers • Attacks on Stream Ciphers • Random Bit Generation • RC4 Algorithm

A Simple Stream Cipher ·使用0-1串作为密钥 明文位流使用X○R加密后得到密文位流 ·使用同样的密钥由密文位流使用XOR解密得 到明文位流 plaintext plaintext XOR XOR Key stream Key stream 復大辱软件学院 LiJT

LiJT A Simple Stream Cipher • )¾0-1(g“ • •Ž%³)¾XORCgSxAgŽ%³ • )¾R¥Âg“¿gŽ%³)¾XORãgx A•Ž%³ plaintext Key stream XOR XOR Key stream plaintext

XOR Function XOR Operation,真值表: 模2加法(A+BMod2同样的真值表(本课不做区分) B F 0 A XOR B A0011 0 0110 A will be the plaintext and b the key 復大辱软件学院 LiJT

LiJT XOR Function • XOR Operation Æ-à • ¨2C± (A+B)Mod 2 R¥ÂÆ-à(œì/b<) A B F A B F 0 0 0 0 1 1 1 0 1 1 1 0 A will be the plaintext and B the key XOR

Bit stream Encryption and Decryption plaintext:1‖00 011001110101001 y o111101010011001100 ciphertext 0110011101100101 key:[oo山1101010011001100 p1 intext:1001011001110101001 Recall Vernam cipher: Ci=PieRi Pi=CioKi 復大辱软件学院 LiJT

LiJT Bit Stream • Encryption and Decryption: plaintext: 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 key: 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 ciphertext: 1 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 0 1 key: 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 plaintext: 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 Ci=Pi
Ki Pi=Ci
Ki Recall Vernam cipher:

存在问题 无限长、纯随机的密钥流无法实现 简单思路是:密钥流直接由初始密钥使用某种算 法变换得来 问题:如何生成一个随机位序列作为密钥流,要 求易于使用,但不能太短以至于不安全? 復大辱软件学院 LiJT

LiJT atĂĊ • Ą”׹Âg“³±f» • ÒFyïg“³Ä‰¿@_g“)¾£ÎÓ ±K‡xŸ • ĂĊ: ^&½| ą%r>(g“³ á °)¾ $Ý]ÈÞd3?

Definitions 前面研究的密码体制中,连续的明文元素是使用相同 的密钥K来加密的,y=y1y2…=ek(x1)e(x2)…,满足 这种特点的密码体制我们通常称为分组密码。 另一种被广泛使用的密码体制称为流密码,基本思想 是产生一个密钥流z=x1-2…,然后用它根据下述规则 加密明文串x=x1x2…;y=y1y2…=e21(x1)e2(x2) >如果密钥流和明文串是相互独立的,这种类型的流密 码称为“同步”流密码。 復大辱软件学院 LiJT

LiJT Definitions Ø M C!; Ø =E#089!;.> 1!;+$% *7 !L1 z = z1z2!48 .' JF !)( x = x1x2! y = y1 y2 ! = ez1 (x1 )ez2 (x2 )! Ø -!L1)(*:6@9H=A91! ;> /1!;

定义同步流密码为一六元组(P,C,K,L,E,D)和 函数g,并且满足如下条件: 1.P是所有可能明文构成的有限集 2.C是所有可能密文构成的有限集 3.密钥空间K为一有限集,由所有可能密钥构成 4.L是一称为密钥流字母表的有限集 5.g是一密钥流生成器。g使用密钥K做为输入,产生 无限的密钥流z==1二2…,这里∈L,i≥1 6.对任意的z∈L,都有一加密规则e∈E和相应的解密 规则d∈D。并且对每一明文x∈P,e2:P→C和 d2:C→>P是满足d2(e2(x))=x的函数。 復大辱软件学院 LiJT

LiJT "

25#JK /KL 9)/@#I1(  L .=#I5!3A:/KL  g .#I57( g 18#I K 2E4 7 ,K:#I5 z = z1z2! FH i z ÎL i ³ 1  $': z ÎL G/#B z e ÎE;&:C# B z d ÎD %$4-+ xÎP : z e P C ®  : z d C P ® .6D ( ( )) z z dex x = :6*

Example 设P=C=K=L=Z26,明文为x= abcdef 由初始密钥K经密钥流生成器g产生的密钥流为 z= chaac…,加密操作与 Caesar相同((x+z) mod26),即加密过程 x三 a bca e tz= b y=cccag g 类似地,Bob收到密文后,也产生相同的密钥流,逐位做 yz即可正确解密 Z2:26个字母的有限集 復大辱软件学院 LiJT

LiJT :P CKL == == Z26.- x abcdef = … 2()= K 8)=01*C g 13)=0 z cbaacb = …!)+  )  4$  +(
2"!);6 x abcdef z cbaacb y cccdgg = + = = 7'+ , )-B614$3)=0< y-z "#/59) Example Z26: 26`­ÂšĄĆ

剪 Vigenere Formulation 假设m为 Vigenere的密钥长度,定义K=(Z26) P=C=L=Z26;定义e(x)=(x+z)mod26,d2(y) =(y-z)mod26。再定义密钥流=1二2…如下: ∫k若1≤i≤m 若i≥m+1 上式中K=(k1k2,,kn),这样利用K可产生密钥流如下 k1k2…knk1k2…knkk2 復大辱软件学院 LiJT

LiJT  m   è "#  26 ( )m K = Z P CL === Z26ez (x) = (x + z)mod26 d (y) z = ( y - z)mod 26" z1z2! î í ì ³ + £ £ = - 1 1 z i m k i m z i m i i

 1 2 (, , , ) K kk k = m ! K " k1k2!kmk1k2!kmk1k2! Vigenère Formulation