密码学基础知识

夫学须静也，才须学也，非学无以广才，非志无以成学。——诸葛亮概述密码学密码编码学密码分析学作用：机密性鉴别完整性抗抵赖密码学文献的发展历程：1918年，Friedman《重合指数及其在密码学中的应用》。1918年，Heberm的转轮机1949年，Shannon《保密系统的通信理论》1967年，Kahn《破译者》1971年，Feistel的Lucifer1975年，Diffie&Hellman提出公开密钥密码学，《密码学的新方向》1977年，DES成为联邦信息处理标准1978年，MIT的RSA算法。1985年，ElGamal体制（离散对数）；Koblitz&Miller提出椭圆曲线密码学•1995年，Hoffstein，Pipher，Siverman发明NTRU密码密码学之前，信息安全的保护主要是通过物理和行政手段实现的。密码学最早多用于外交情报和军事领域。现代密码学家通常是理论数学家。第一阶段：手工计算第二阶段：机械和电动机械第三阶段：电子和计算机内容1.保密与保密系统2.古典密码技术3.密码体制4.密码分析5.加密方式一、保密与保密系统保密学：研究信息系统安全保密的科学。1.保密系统模型图一个密码体制由五元组（P，C，K，E，D）构成。SymmetricCipherModelBasicTerminologyplaintext-theoriginalmessageciphertext-thecodedmessagecipher-algorithmfortransformingplaintexttociphertextkey-infousedincipherknownonlytosender/receiverencipher(encrypt)-convertingplaintexttociphertextdecipher(decrypt)-recoveringciphertextfromplaintextcryptography-studyofencryptionprinciples/methodscryptanalysis(codebreaking)-thestudyofprinciples/methodsofdecipheringciphertextwithoutknowingkeycryptology-thefieldofbothcryptographyandcryptanalysis2.密码设计准则保密系统抗击密码分析，应满足：1）系统即使达不到理论上是不可破的，也应当为实际上是不可破的。2）Kerckhoff原则。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。3）加密和解密算法适用于所有密钥空间中的元素。4）系统便于实现和使用方便。Kerckhoff六项准则在19世纪对军事密码体制提出六项准则：密码体制即便不是在理论上不可破，也应该是实际上不可破的。体制的泄露不应该给通信者带来麻烦。……3.保密系统的通信理论明文密码系统的熵惟一解距离UDPlaintext明文Entropy:一条信息的信息量通过熵来度量。是对信息或不确定性的数学度量，通过概率分布的函数来计算。语言信息率：r=H(M)/NN相当大时，标准英语的语言信息率在1.0-1.5/字母之间。语言绝对信息率：假定每一个字符串是等可能的，对每个字母编码的最大位数。英文R=logL=log26=4.7位/字母ThomasCover采用随机估算技术得到的信息率为1.3位/字符。自然语言具有高冗余度。D=R-r=3.4位/字母。英语语言是75%冗余。Huffman一条ASCII消息，每字节消息含有与英语相等的1.3位的消息，她的冗余信息为6.7位，相当于每位ASCII文本有0.84位冗余自然语言的高冗余度为密码分析提供了一个重要工具。它最重要也是最基本的特征：单个字母出现的频率。密码系统的熵由密钥空间大小来衡量H(K)=logK一般来说，熵越大，破译它越困难。密钥：尽量使密钥源为无记忆均匀分布源。密文的统计特征由明文和密钥的统计特征完全决定。收到的密文越长，分析者找到密钥或明文的可能性越大，为确信分析者可找到唯一的密钥，理论上S至少将要多长。惟一解距离UD在给定足够的计算时间下，分析者能唯一计算出密钥所需密文的平均值。惟一解距离UnicityDistance[码量]：使一个具有无限计算能力的攻击者能够恢复惟一的加密密钥所需要的最小密文量（字符数）。在达到惟一解距离时，密钥暧昧度趋近于零。临界值S=H(K)/[loge-H(m)]称为UD。UD定义为使得伪密钥的期望值等于零的n的值。当密文字符大于UD时，这种密码就存在一个解，而当密文字符小于UD时，就会出现多个可能的解。它利用信息论描述了被截获的密文量和成功攻击的可能性之间的关系。UDShannon指出：惟一解距离可以保证当其太小时，密码系统是不安全的，但并不保证当其较大时，密码系统就是安全的。惟一解距离不是对密码分析需要多少密文的度量，而是对存在唯一合理的密码分析所需密文数量的指标。惟一解距离与冗余度成反比，当冗余度接近于零时，一个普通的密码系统也可能是不可破的。UD一般而言，惟一解距离越长，密码系统越好。无穷大时为理想保密。密码分析利用自然语言的冗余度来减少可能的明文数目。语言的冗余度越大，它就越容易被攻击。最重要也是最基本的特征：单个字母出现的频率。一个好的加密算法是一种混合变换，它将有意义的小区域中的有意义的消息相当均匀地分布到在整个消息空间中。4.密码系统的安全性是密码学研究的一个重要课题有两种定义“安全性”的方法：基于信息论的方法（经典方法）基于计算复杂性理论的方法（现代方法）基于信息论的方法：用密文中是否蕴含明文的信息作为标准。基于计算复杂性理论的方法：是考虑信息是否能有效地被提取出来。现代密码学的基础传统的密码学和公钥密码学的基础是信息论和计算复杂性理论信息理论密码学计算复杂性理论密码学信息论告诉我们，所有的密码算法（OTP除外）都能被破译。复杂性理论告诉我们，何时能被破译。信息理论密码学Shannon用不确定性和惟一解距离度量了密码系统（体制）的安全性。密码系统的安全性：理论保密：完全保密理想保密实际保密：计算安全（可证明安全性）理论安全经典方法无条件安全性基于信息论的密码学信息理论密码学：用信息论的观点和方法研究密码系统模型的建立、密码的安全性及破译等，它所研究的安全性准则，假定密码分析者的计算资源，不受限制完全保密理论上不可破译的密码体制。必要条件：明文数、密钥数和密文数都相等的密码体制，将每个明文变换成每个密文都恰好有一个密钥，所有的密钥都是等可能的。Shannon从理论上证明：仅当可能的密钥数目至少与可能的消息数目一样多时，完全保密才是有可能的。完全保密仅有一次一密（OTP）乱码本的密码系统可获得完全保密。One-TimePad在要求无条件安全的军事和外交环境中有着很重要的作用。完全保密：（完善的或无条件的保密系统）给定密文y，明文为x的后验概率等于明文x的先验概率理想保密理论上不可译的，它的惟一解距离UD趋向于无穷大的密码体制。意味着语言的多余度趋向于零。当然消除语言中的全部多余度事实上不可能。它是不实用的，但它揭示我们设计密码体制（算法）时，应尽量缩小多余度。明文信息加密前先进行信源编码。一个完全保密的密码系统必须是一个理想保密的密码系统，但是一个理想保密的密码系统不一定是一个完全保密的密码系统。实际安全现代方法有条件安全性基于复杂性理论的密码学复杂性理论密码学：用复杂性理论的观点和方法研究密码系统模型的建立、密码的安全性分析及破译等。假定密码分析者的计算资源是有限的，受到限制实际安全实际安全性又称为计算上的安全性。计算安全性：涉及攻破密码体制所做的计算上的努力。可证明安全性：安全性归结为某个经过深入研究的数学难题。实际安全性主要考虑：计算能力（基本运算次数、存储量）破译算法的有效性算法：求解某一问题的、一步一步地执行的计算过程。计算复杂性问题的计算复杂性可解问题的最有效算法的计算复杂性算法的计算复杂性运行它所需的计算能力。常常用两个变量来度量：时间复杂性T和空间复杂性S（或所需存储空间）“计算上安全”：指利用已有的最好的方法破译该系统所需要的努力超过了敌手的破译能力（时间、空间、资金等）或破译该系统的难度等价于解数学上的某个已知难题（计算复杂性）。计算复杂性计算复杂性理论是密码系统安全性定义的理论基础。算法：函数1（常数）、对数、n（线性函数）、二次函数、三次函数、多项式函数、亚指数、指数函数问题：P、NP、NPC时间复杂性一个算法的计算复杂性或有效性可以用执行该算法所需的运行时间和内存空间来度量。时间复杂性有两种定义方法：1。用图灵机表示一个算法2。该算法的比特运算次数计算上保密：理论上可破，实际上难破，而不是不可破。密码体制安全性准则计算安全性：可证明安全性：无条件安全性：5.密码编码系统分类：密码编码系统分类：明文转换为密文操作的类型•替代•置换密钥数量•单钥•双钥明文处理方式•分组密码•序列密码Cryptographycancharacterizeby:typeofencryptionoperationsusedsubstitution/transposition/productnumberofkeysusedsingle-keyorprivate/two-keyorpublicwayinwhichplaintextisprocessedblock/stream“Purple”紫码1941.12.7日本偷袭珍珠港1942.1美成功破译JN-251942.4美轰炸日东京、神户等1942.5.7-8巴布亚新几内亚的莫尔兹比港PortMoresby（印尼）1942中途岛之战4.18“山本五十六”飞机降落时被击落二、古典密码技术1.代替密码：单表代替密码、Playfair、Hill、Vigenere、OTP2.置换密码：3.乘积密码：4.转轮机5.隐写术1.SubstitutionCipherswherelettersofplaintextarereplacedbyotherlettersorbynumbersorsymbolsorifplaintextisviewedasasequenceofbits,thensubstitutioninvolvesreplacingplaintextbitpatternswithciphertextbitpatterns代替密码单表代替密码多名码代替密码多字母代替密码多表代替密码1）单表代替密码单表代替密码例如“凯撒”密码古罗马军队用由JuliusCaesar发明明文字母ABCDEFGHIKLMNOPQRSTVXYZ密文字母DEFGHIKLMNOPQRSTVXYZABC注：拉丁文不用J，U，WCaesarCipherearliestknownsubstitutioncipherbyJuliusCaesarfirstattesteduseinmilitaryaffairsreplaceseachletterby3rdletteronexample:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWBCaesarCiphercandefinetransformationas:abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCmathematicallygiveeachletteranumberabcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425thenhaveCaesarcipher