【密码学基础】2

1.An Improved Attack on the Shift Cipher【对轮班密码的改进攻击】
Easy to automate【易于自动化】
As an exercise, please try to write a program to find the key used to generate the following ciphertext and the corresponding plaintext：

作为一个练习，请尝试编写一个程序来找到用于生成以下密文和相应的明文的密钥：

OVDTHUFWVZZPISLRLFZHYLAOLYL

DEFINITION 定义

An encryption scheme (Gen, Enc, Dec) over a message space M is perfectly secret if for every probability distribution over M, every message m ∈ M, and every ciphertext c ∈ C for which Pr [ C = c ]> 0 :

Pr[ M = m | C = c ] = Pr[ M = m ].

如果消息空间M上的每个概率分布、每个消息M∈C[C=C]>0：Pr[M=M|C=C]=Pr[M=M]的加密方案(Gen，Enc，Enc，Dec)是完全保密的。

LEMMA 引理

An encryption scheme (Gen, Enc, Dec) over a message space M is perfectly secret if and only if for every probability distribution over M, for every m, m′ ∈ M, and every c ∈ C,

Pr[ EncK(m) = c ] = Pr[ EncK(m′) = c ].

当且仅当对于M上的每个概率分布、对于每M、M‘∈M和每个∈，EncK(m)=]=∈[EncK(m’)=c]的加密方案(Enc(Dec)是完全保密的。

充分性证明：Pr[EncK（→）=]=Pr[EncK（=）=→]该方案完全保密(即Pr[M=m|=]=Pr[M=])。

修复了M、消息m和密文c，其中Pr[C=c]>0

如果Pr[M=m]=0，则Pr[M=m|C=c]=0=Pr[M=m]

Assume Pr[ M=m ]>0 :

∵ Pr[ C=c | M=m ]= Pr[ Enck(M)=c | M=m ]=Pr[ Enck(m)=c ] =δc ，

    Pr[ Enck(m) = c ] = Pr[ Enck(m′) = c ] （lemma condition）

∴ Pr[ Enck(m)=c ] = Pr[ Enck(m')=c ] = Pr[ Enck(M)=c | M=m' ] = δc

∴ The scheme is perfectly secret. Proof of necessity?