《信息安全导论（以问题为导向）》全套教学课件

信息安全导论（以问题为导向）01古典密码-第一部分02古典密码-第二部分03现代分组密码04公开密钥密码05报文鉴别与哈希函数06公钥基础设施PKI07身份认证08Web与电子商务安全09区块链1全套可编辑PPT课件

1古典密码（1）-ClassicalEncryptionTechniques2全套可编辑PPT课件

1.古典密码

1.1对称密钥密码模型

SymmetricCipherModel3本课件是可编辑的正常PPT课件要解决的问题：通信保密安全需求SecurityRequirements安全服务SecurityServices保密性Confidentiality完整性Integrity可用性Availability4本课件是可编辑的正常PPT课件三个古典密码系统羊皮传书藏头诗Caesar5本课件是可编辑的正常PPT课件羊皮传书古希腊的斯巴达人将一条1厘米宽、20厘米左右长的羊皮带，以螺旋状绕在一根特定粗细的木棍上…...6本课件是可编辑的正常PPT课件藏头诗明才子唐伯虎：我爱兰江水悠悠，爱晚亭上枫叶稠。秋月溶溶照佛寺，香烟袅袅绕经楼。明朝解缙祝某宰相寿辰进诗：真真宰相,老老元臣,乌纱戴顶,龟鹤遐林.粗看"密文”,浑然诗句,颂扬兼祝愿,福禄寿全有;细究则密语藏头,挖苦带讽刺,诅咒"真老乌龟”7本课件是可编辑的正常PPT课件CaesarCipherearliestknownsubstitutioncipherbyJuliusCaesar

firstattesteduseinmilitaryaffairsexample:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB8本课件是可编辑的正常PPT课件Terminologiesplaintext-theoriginalmessageciphertext-thecodedmessagekey-infousedincipherknownonlytosender/receiverencipher(encrypt)-convertingplaintexttociphertextdecipher(decrypt)-recoveringplaintextfromciphertextcipher-algorithmfortransformingplaintexttociphertext9SymmetricCipherModel10DefinitionAcryptosystemisa5-tuple

(E,D,p,K,C),wherepisthesetofplaintexts,Kthesetofkeys,Cisthesetofciphertexts,E:M×KCisthesetofEncryptionalgorithms,D:C×KMisthesetofDecryptionalgorithms.111.古典密码

1.2密码学的基础假设12三个古典系统的再讨论Caesar羊皮传书藏头诗13CaesarCiphermeetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWBp,C,K,E,D?14CaesarCiphercandefinetransformationas:abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCmathematicallygiveeachletteranumberabcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425thenhaveCaesarcipheras:C=E(p)=(p+k)mod(26)p=D(C)=(C–k)mod(26)15羊皮传书E,D,p,C,K?16藏头诗真真宰相,老老元臣,乌纱戴顶,龟鹤遐林.E,D,p,C,K?全诗为"密文”,其"密钥”是每句诗的首字,可串接成义,作者的真意就隐藏在诗句的首字串接文("明文”)中.Steganography，隐写术17RethinkingoftheModel18encipherdecipher(plaintextin-ciphertextout)ciphertextmsg(ciphertextin-plaintextout)(shouldunderstand

nothing

aboutthemsg)eavesdropperbla-blacmb-cmbbla-blaSharedKeyNeed

keyexchangeAliceandBobwanttoestablishasharedsecret(key)whenotherpeople(eavesdroppers)arelisteningHowto?inboundVs.outbound19AliceBobDiscursionsontheModel20Q1:Whyuseakey?Q2:Whichpartsshouldbekeptsecret?whichnot?Discussion模型合理吗？什么当保密；什么当公开？19世纪荷兰人A.Kerckhoffs就提出了一个在密码学界被公认为基础的假设，也就是著名的“Kerckhoffs假设”：秘密必须全寓于密钥。

OtherModels?2122Discussion“谁是我们的敌人，谁是我们的朋友，这个问题是革命的首要问题”——毛选易用性秘密全部寓于密钥≠算法当公开，要看应用环境(商用，军用，……)开放的系统更安全，??Terminologies(cont.)cryptography-studyofencryptionprinciples/methodscryptanalysis(codebreaking)-thestudyofprinciples/methodsofdecipheringciphertextwithoutknowingkeycryptology-thefieldofbothcryptographyandcryptanalysis23CryptographyCatalogThetypeofoperationsusedfortransforming

plaintexttociphertextSubstitution:eachelementintheplaintextismappedintoanotherelementTransposition:elementsintheplaintextarerearrangedProduct:multiplestagesofsubstitutionsandtranspositionsThenumberofthekeysusedSymmetric,single-key,secret-key,conventional

encryption:BothsenderandreceiverusethesamekeyAsymmetric,two-key,orpublic-key

encryption:thesenderandreceiveeachusesadifferentkey24CryptographyCatalogThewayinwhichtheplaintextisprocessedBlock:processestheinputoneblockofelementsatatime,producinganoutput

block

foreachinputblockStream:processestheinputelementscontinuously,producingoutputoneelementatatime,asitgoesalong.252.如何设计好的密码算法？

攻击->防御->改进->更好的密码算法->攻击…螺旋式上升过程中领会密码设计的关键问题262.如何设计好的密码算法？

2.1

Caesar密码与单字母表密码

攻击->防御->改进->更好的密码算法->攻击…螺旋式上升过程中领会密码设计的关键问题27SubstitutionTechniquesCaesarcipherEasytobreak!28CryptanalysisofCaesarCipherThereareonly25keystotryAmapstoA,B,..Zcouldsimplytryeachinturnabruteforcesearch

givenciphertext,justtryallshiftsoflettersThelanguageofPlaintextisknownandeasilyrecognizabledoneedtorecognizewhenhaveplaintexteg.breakciphertext"GCUAVQDTGCM"29MonoalphabeticCipherImprovementonCaesarCipherRatherthansubstitutingaccordingtoaregularpattern–anylettercanbesubstitutedforanyotherletter,aslongaseachletterhasauniquesubstituteletter,andviceversa.30MonoalphabeticCipherK: Plain:abcdefghijklmnopqrstuvwxyz Cipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA

hencekeyis26letterslong31MonoalphabeticCipherSecuritynowhaveatotalof26!=4x1026keyswithsomanykeys,mightthinkissecure

butwouldbe!!!WRONG!!!

problemislanguagecharacteristics32LanguageRedundancyandCryptanalysishumanlanguagesareredundant

lettersarenotequally

commonlyusedinEnglisheisbyfarthemostcommonletter,thenT,R,N,I,O,A,S

somelettersarefairlyrare,eg.Z,J,X,Qtablesofsingle,double&tripleletterfrequencies33FrequencyofLettersinEnglishText34UseinCryptanalysiskeyconcept-monoalphabeticsubstitutionciphersdonotchangerelativeletterfrequencies

discoveredbyArabianscientistsin9thcenturycalculateletterfrequenciesforciphertextcomparecounts/plotsagainstknownvaluesifCaesarcipherlookforcommonpeaks/troughspeaksat:A-E-Itriple,NOpair,RSTtripletroughsat:JK,X-Zformonoalphabeticmustidentifyeachlettertablesofcommondouble/triplelettershelp35CryptanalyticAttacks36对于对手而言最坏情况下，仍有一种攻击方法可用BruteForceSearch，穷举法BruteForceSearchalwayspossibletosimply

try

everykey

mostbasic

attack,proportionaltokeysizeassumeeitherknoworrecogniseplaintext37MoreDefinitionsunconditionalsecurity

nomatterhowmuch

computerpowerisavailable,theciphercannotbebrokensincetheciphertextprovidesinsufficientinformationtouniquelydeterminethecorrespondingplaintextcomputationalsecurity

givenlimited

computingresources(eg.timeneededforcalculationsisgreaterthanageofuniverse),theciphercannotbebroken

Unconditionalsecuritywouldbenice,buttheonlyknownsuchcipheristheone-timepad(later).Forallreasonable

encryptionalgorithms,havetoassumecomputationalsecuritywhereiteithertakestoolong,oristooexpensive,tobother

breakingthecipher.382.如何设计好的密码算法？

2.2

Playfair密码

攻击->防御->改进->更好的密码算法->攻击…螺旋式上升过程中领会密码设计的关键问题39MonoalphabeticCipherSecuritynowhaveatotalof26!=4x1026keyswithsomanykeys,mightthinkissecure

butwouldbe!!!WRONG!!!

problemislanguagecharacteristics40提高单字母表密码安全性两个角度“多”对“一”

Playfair“一”对“多”

Vigenère41PlayfairCiphernoteventhelargenumberofkeysinamonoalphabeticcipherprovidessecurity

oneapproachtoimprovingsecuritywastoencryptmultiplelettersthePlayfairCipherisanexampleinventedbyCharlesWheatstonein1854,butnamedafterhisfriendBaronPlayfair

4243PlayfairKeyMatrixa5X5matrixoflettersbasedonakeywordfillinlettersofkeyword(sansduplicates)fillrestofmatrixwithotherletterseg.usingthekeywordMONARCHYMONARCHYBDEFGIKLPQSTUVWXZ44EncryptingandDecryptingplaintextencryptedtwolettersatatime:ifapairisarepeatedletter,insertafillerlike'X', eg."balloon"encryptsas"balxloon"ifbothlettersfallinthesame

row,replaceeachwithlettertoright(wrappingbacktostartfromend), eg.“ar"encryptsas"RM"ifbothlettersfallinthesame

column,replaceeachwiththeletterbelowit(againwrappingtotopfrombottom),eg.“mu"encryptsto"CM"otherwiseeachletterisreplacedbytheoneinitsrowinthecolumnof

theotherletterofthepair,eg.“hs"encryptsto"BP",and“ea"to"IM"or"JM"(asdesired)45SecurityofthePlayfairCiphersecuritymuchimproved

overmonoalphabeticsincehave26x26=676digramswouldneeda676entryfrequencytabletoanalyse(verses26foramonoalphabetic)andcorrespondinglymoreciphertextwaswidelyusedformanyyears(eg.US&BritishmilitaryinWW1)itcanbebroken,givenafewhundredletterssincestillhasmuchofplaintextstructure462.如何设计好的密码算法？

2.3

Vigenère密码

攻击->防御->改进->更好的密码算法->攻击…螺旋式上升过程中领会密码设计的关键问题47PolyalphabeticCiphersanotherapproachtoimprovingsecurityistousemultiplecipheralphabets

calledpolyalphabetic

substitution

ciphers

makescryptanalysisharderwithmorealphabetstoguessandflatterfrequencydistributionuseakeytoselectwhichalphabetisusedforeachletterofthemessageuseeachalphabetinturnrepeatfromstartafterendofkeyisreached48VigenèreCiphersimplestpolyalphabeticsubstitutioncipheristheVigenèreCipher

effectivelymultiplecaesarcipherskeyismultipleletterslongK=k1k2...kdithletterspecifiesithalphabettouseuseeachalphabetinturnrepeatfromstartafterdlettersinmessagedecryptionsimplyworksinreverse49VigenèreCipher50PlaintextKeyExamplewritetheplaintextoutwritethekeywordrepeatedaboveituseeachkeyletterasacaesarcipherkeyencryptthecorrespondingplaintextletteregusingkeyworddeceptiveKey:deceptivedeceptivedeceptivePlaintext:wearediscoveredsaveyourselfCiphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

51ExamplewritetheplaintextoutwritethekeywordrepeatedaboveituseeachkeyletterasacaesarcipherkeyencryptthecorrespondingplaintextletteregusingkeyworddeceptiveKey:deceptivedeceptivedeceptivePlaintext:wearediscoveredsaveyourselfCiphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

52AutokeyCipherideallywantakeyaslongasthemessageVigenèreproposedtheautokeycipherwithkeywordisprefixedtomessageaskeyknowingkeywordcanrecoverthefirstfewlettersusetheseinturnontherestofthemessagebutstillhavefrequencycharacteristicstoattackeg.givenkeydeceptivekey:deceptivewearediscoveredsavPlaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA53SecurityofVigenèreCiphershavemultipleciphertextlettersforeachplaintextletterhenceletterfrequenciesareobscuredbutnottotallylostTheultimatedefenceagainstsuchacryptanalysisistochooseakeywordthatisaslongastheplaintextandhasno

statisticalrelationshiptoitAT&T,Vernamcipher542古典密码（2）-ClassicalEncryptionTechniques553.对称密钥密码的理论标杆

56回顾：Vigenère的安全性分析havemultipleciphertextlettersforeachplaintextletterhenceletterfrequenciesareobscuredbutnottotallylostTheultimatedefenceagainstsuchacryptanalysisistochooseakeywordthatisaslongastheplaintextandhasno

statisticalrelationshiptoitAT&T,Vernamcipher57一次一密，One-TimePad如果密钥和消息一样长，且真正随机，那么该密码无条件安全。1918年，GillbertVernam提出密钥与明文一样长并且没有统计关系的密钥内容，算法表述采用二进制数据:申请了专利Ci=Pi⊕KiPi=Ci⊕Ki58G.Vernam191859Ci=Pi⊕KiPi=Ci⊕KiShannon在他的1949年发表的经典论文中已经证明了一次一密的无条件安全性密钥的分发是大问题，实用价值较弱ClaudeShannon信息论之父,84高龄去世,2001年1948年发表《AMathematicalTheoryofCommunication》奠定了现代信息论的基础1949年，《CommunicationTheoryofSecrecySystems》(保密系统的通信理论)提出了保密系统的数学模型、随机密码、完善保密性等重要概念它的意义是使保密通信由艺术变成科学604.简单的置换密码

61置换密码重新排列明文字母，达到信息加密的目的与替代密码不同的是，原来明文中的字母同样出现在密文中，顺序打乱。古典的置换密码例子：62RailFence密码明文：meetmeafterthetogaparty顺序打乱（本来应该从左向右横向写，现在是先纵向写两个字母，再横向写）:mematrhtgpryetefeteoaat密文：MEMATRHTGPRYETEFETEOAAT63行置换密码略复杂的例子Key:4312567Plaintext:attackpostponeduntiltwoamxyzCiphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ

64乘积密码单次替代或置换方法构造密码技术并不安全因此考虑连续多次使用简单的加密方法可以构造更强的密码：

两次替代构成一个更复杂的替代密码两次置换构成一个更复杂的置换密码替代与置换的叠加同样……通向现代密码技术的基本道路655.转子机（RotorMachines）

－代表古典密码最高峰的作品

66转子机现代密码出现前,转子机是一种典型的乘积密码-古典密码的高峰非常普遍应用于WW2德国Enigma,盟军Hagelin,日本Purple非常复杂的多轮替代技术3个转盘有：263=17576个密钥67Enigma68Enigma-Rotors69Enigma70古典隐写术藏头诗隐形墨水……特点：大量冗余的信息隐藏相对很少的信息量71现代隐写术的变迁数字化编码后的多媒体信息：如图像、声音、视频，甚至文本信息，对于人类的视觉、听觉感知系统，都或多或少存在着一些冗余空间，而利用这些冗余空间，就可以进行信息的秘密传递，同时不影响载体的视觉或听觉效果，因此就可以实现信息的隐蔽传递。72信息隐藏技术伪装式保密通信数字水印73伪装式保密通信目前在这一研究领域中主要研究在图像、视频、声音以及文本中隐藏信息。如：在一幅普通图像中隐藏一幅机密图像。在一段普通谈话中隐藏一段机密谈话或各种数据。在一段视频流中隐藏各种信息等。文本中的冗余空间比较小，但利用文本的一些特点也可以隐藏一些信息。74数字水印一种基本的数字版权标记手段数字水印是嵌入在数字作品中的一个版权信息，它可以给出作品的作者、所有者、发行者以及授权使用者等等版权信息。可以作为数字作品的序列码，用于跟踪盗版者。753现代分组密码-Modern

Block

Cipher以DES为例76本讲内容分组密码流密码77相对的概念本讲内容现代分组密码设计的一般性原则DES加密算法78回顾：对称密码模型AliceBob79本讲内容现代分组密码设计的一般性原则Shannon理论奠基Feistel结构DES加密算法80乘积密码单次替代或置换方法构造密码技术并不安全因此考虑连续多次使用简单的加密方法可以构造更强的密码：

两次替代构成一个更复杂的替代密码两次置换构成一个更复杂的置换密码替代与置换的叠加同样……通向现代密码技术的基本道路81Shannon理论奠基Shannon提出利用扰乱（Confusion）和扩散（Diffusion）交替的方法来构造乘积密码密码SPN：SubstitutionPermutationNetwork 替代-置换网络目的是：使基于统计的分析方法不易或者不能实现Shannon理论是现代分组密码算法的基础82SPN的基本操作83SPN84SPN的雪崩效应8586Feistel结构由HorstFeistel发明目的是构造可逆的乘积密码把输入的分组分成两个部分进行多轮的变换（替代和置换）轮函数是关键体现了Shannon的SPN理念87FeistelCipherStructure本讲内容现代分组密码设计的一般性原则DES加密算法8889分组密码以分组为加密/解密处理的最小单位-“多”对“一”分组：可以理解为连续的多个字母64-bits或更多分组密码非常广泛的应用于现代加密系统90DataEncryptionStandard(DES)最广泛使用的密码系统1977年，被NBS(nowNIST)选为标准asFIPSPUB46分组64-bit，使用56-bitkey它的安全性曾引起了广泛的争论NBS(NationalBureauofStandards)NIST(NationalInstituteofStandardsandTechnology)美国国家标准局91DES算法的历史1969年前后IBM的Feistel研究组的工作NIST1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告加密算法要达到的目的有四点高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改；具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握；DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础；实现经济，运行有效，并且适用于多种完全不同的应用92DES算法的原理DES算法的入口参数有三个：Key、Data、ModeKey为8个字节共64位，是DES算法的工作密钥Data分组也为8个字节64位，被加密或被解密的数据Mode为DES的工作方式有两种：加密或解密93DES算法概貌94DES算法的实现步骤DES算法实现加密需要三个步骤：第一步：变换明文。对给定的64位比特的明文x，首先通过一个置换IP表来重新排列x，从而构造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位第二步：按照规则迭代。规则为Li=Ri-1Ri=Li⊕F(Ri-1,Ki)（i=1,2,3…16）95DES算法的实现步骤第二步：经过第一步变换已经得到L0和R0的值，其中符号⊕表示的数学运算是异或，F函数表示一种密码变换，由S盒替代构成，Ki是一些由密钥编排函数产生的比特块F和Ki将在后面介绍第三步：对L16R16利用IP-1作逆置换，就得到了密文y96（1）IP置换表和IP-1逆置换表输入的64位数据按置换IP表进行重新组合，并把输出分为L0、R0两部分，每部分各长32位，其置换IP表如表：5850123426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315797逆置换表IP-1

4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572598每一轮做什么99F函数详解100子密钥Ki的生成假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。K的下标i的取值范围是1到16，用16轮来构造101子密钥Ki的生成102DES算法的安全性1993年R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案它基于并行的密钥搜索芯片每个芯片每秒测试5×107个密钥当时这种芯片的造价是10.5美元5760个这样的芯片组成的系统需要10万美元系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时103DES算法的安全性1997年1月28日，RSA公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56比特密钥加密的DES密文一位名叫RockeVerser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为DESHALL的搜索行动，成千上万的志愿者加入在行动实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司的职员MichaelSanders成功地找到了密钥，在计算机上显示了明文：“Theunknownmessageis:Strongcryptographymakestheworldasaferplace”104AES,AdvancedEncryptionStandard需要DES的替代品理论上实践上，穷举法攻击的成功3重-DES，但速度慢NIST发布新的密码征求令，1997最终，2000年10月，Rijndael被选中成为AES2001年11月成为FIPSPUB197标准

128-bitdata,128/192/256-bitkeys105Quiz试总结设计一个好的对称分组加密算法应当遵循哪些原则？请默写画出DES加密算法的流程图。DES的加密算法与解密算法是一致的，因为算法的结构本身保证了算法的可逆性，与F函数无关，请试着说明上述结论。1064公开密钥密码

PublicKeyCryptography107内容提要对称密钥密码的密钥交换问题公钥密码模型提出设计公钥密码的基本要求数字签名RSA算法公钥密码的特征总结Diffie-Hellman密钥交换算法108内容提要1、对称密钥密码的密钥交换问题109回顾：对称密钥密码对称的,单密钥,秘密密钥,传统密码:发送方加密和接收方解密使用同一个的密钥该密钥需要事先由发送方和接收方实现共享，是发送方和接收方共同的秘密如果密钥泄露，则不安全（无法提供保密性服务）对称：通信双方是对等的110回顾：对称密钥密码模型双方共享的秘密：KeyAliceBob发送方接收方安全的信道

加密容易实现，但密钥交换是个问题111内容提要2、公钥密码模型提出112BobAlice每个人有两个密钥公钥，Publickey——公开私钥，Privatekey——保密公开密钥(非对称)密码模型113BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非对称密码模型公开114BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非对称密码模型公开保密保密115用非对称密码实现“保密通信”BobAlice提供“保密通信”安全服务攻击者116两种密码体制据使用的密钥数量对称的,单密钥,秘密密钥,传统密码技术:发送方和接收方使用同一个的密钥非对称的,双密钥,公钥密码技术:发送方和接收方使用不同的密钥加密密钥和解密密钥分割开来,且无法由一个推出另一个,使得不仅可以公开密码算法,而且加密密钥也可公开（公告牌、号码簿）117公开密钥密码人类文明史3000年以来，密码技术一个新的篇章两个密钥–apublic&aprivatekey非对称：通信双方的地位不平等往往应用数论的一些函数精心构造补充而非取代对称密钥密码技术缺点：公钥密码的主要弱点是加密和解密速度慢118历史1976年，Diffie和Hellman在论文“密码学新方向（NewDirectioninCryptography）”中首次提出了公开密钥密码体制的思想；Diffie和Hellman提出了第一个基于公开密钥思想的密码算法，称为DH算法，此算法可以用于实现密钥交换。1977年，Rivest、Shamir和Adleman三个人实现了公开密钥密码体制，现在称为RSA算法，它是第一个既能用于密钥交换、也能用于数据加密和数字签名的算法。119内容提要3、设计公钥密码的基本要求一个公开密钥系统由六要素组成：明文公开密钥（记作：PU或KU）私有密钥（记作：KR或PR）加密算法密文解密算法公开密钥加密系统参与方B容易通过计算产生出一对密钥（公开密钥KUb

，私有密钥KRb

）发送方A很容易计算产生密文接收方B通过计算解密密文敌对方即使知道公开密钥KUb

，要确定私有密钥KRb

在计算上是不可行的敌对方即使知道公开密钥KUb

和密文C，要确定明文M在计算上是不可行的密钥对互相之间可以交换使用公开密钥算法的基本要求公钥密码构建在计算复杂性理论基础之上122往往让敌方求解目前仍未找到多项式时间算法的NP完全问题123内容提要4、数字签名124密钥对互相之间可以交换使用：125数字签名BobAlice提供“数字签名”安全服务126公钥密码能提供的安全服务保密通信本课程最初提出的安全需求，先前讲解的密码方案主要用于解决这个问题密钥交换数字签名能够检验加密数据的来源（认证）能够抗抵赖127公钥密码原理总结公开密钥密码技术涉及两个密钥:公钥：

公开，任何人可以知道,用于加密明文，验证签名私钥,仅有接收者/拥有者自己知道，用于解密，签名非对称的含义：密钥的不对称：加／解密的密钥不同用于加密的不能解密，用于解密的不能加密128本讲内容5、RSA算法5.1密钥生成1977年由MIT的Rivest,Shamir和Adleman

三人提出是一个分组加密方法目前被最广泛地采用理论基础是数论中的下述论断:要求得两个大素数的乘积是容易的,但要分解一个合数为两个大素数的乘积,则在计算上几乎是不可能的。RSA算法130RSA密钥生成每个用户执行：（1）生成两个大素数p和q。（2）计算这两个素数的乘积n=p×q。（3）计算小于n并且与n互质的整数的个数，即欧拉函数φ(n)=(p-1)(q-1)。（4）选择一个随机数e满足1<e<φ(n)，并且e和φ(n)互质，即gcd(e,φ(n))=1。（5）解方程e·d

≡1modφ(n)，求出d131RSA密钥（6）保密d，p和q（销毁），公开n和e。公钥公开:PU={e,n}私钥保密:PR={d,n}密钥生成的计算量如何得到足够大的随机素数如何求解方程e·d

≡1modφ(n)132如何得到足够大的随机素数实际应用所采用的方法是：首先，产生一个足够大的随机数，然后，通过采用一个概率多项式时间算法来检测该随机数是否为素数（即是否具有素性）。常用的两个素性测试算法：Solovay-Strassen素性测试；Miller-Rabin素性测试。索洛维-斯特拉森求解方程e·d

≡1modφ(n)扩展的欧几里德算法（辗转相除法）134当e＝1001，ø(n)＝3837时

方程为x*1001=1(mod3837)

求解过程：

3837=3*1001+834

1001=1*834+167

834=4*167+166

167=166+1

所以

1=167-166

=167-(834-4*167)

=5*167-834

=5*(1001-834)-834

=5*1001-6*834

=5*1001-6*(3837-3*1001)

=23*1001-6*3837135本讲内容5、RSA算法5.2加解密算法136RSA使用公钥公开:PU={e,n}私钥保密:PR={d,n}加密一个报文M，发送方:获取接收方的公钥

PU={e,n}

计算:C=Memodn,where0≤M<n解密

密文C，接收方:用自己的私钥

PR={d,n}

计算:M=Cdmodn

137RSA例子–密钥挑选质数:p=17&q=11计算

n=?138RSA例子–密钥挑选质数:p=17&q=11计算

n=pq=17x11=187计算ø(n)=(p–1)(q-1)=16x10=160选择e:

gcd(e,160)=1;不妨选e=7求解d:

ed=1mod160

且d

<160

d=23，显然

23x7=161=10x160+1PublickeyPU={7,187}PrivatekeyPR={23,187}139RSA例子–加密/解密RSA加密/解密:M=88(注意:

88<187)加密:C=887mod187=11

解密:M=1123mod187=88

模指数运算简化140在RSA密码体制中，加密和解密运算都是模指数运算，即C=Memodn可以通过e-1次模乘来实现计算，然而，如果e非常大，其效率会很低下平方-乘算法可以把计算所需的模乘的次数降低1123mod187=[(111mod187)*(112mod187)*(114mod187)*(118mod187)*(118mod187)]mod187111mod187=11112mod187=121114mod187=14641mod187=55118mod187=214358881mod187=331123mod187=(11*121*55*33*33)mod187=79720245mod187=88求模指数实例142RSA注意RSA加密时，明文以分组的方式加密：每一个分组的比特数应该小于log2n比特，即：M<n选取的素数p和q要足够大，从而乘积n足够大，在事先不知道p和q的情况下分解n是计算上不可行的。143本讲内容5、RSA算法5.3

RSA安全性讨论144RSA算法的安全性在理论上,RSA的安全性取决于模n分解的困难性。若n被分解成功,则RSA被攻破。目前最快的分解因子算法其时间复杂性为并没有证明分解大整数就是NP问题,并不能排除存在尚未发现的多项式时间算法。也没有证明对RSA的攻击的难度与分解n等价因此对RSA的攻击的困难程度不比大数分解难目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在人们已能分解多个十进制位的大素数，因此，模数n必须选大一些。145RSA因数分解挑战分解挑战奖金于2007终止ChallengeNumber Prize($US) StatusRSA-576(174Digits) $10,000 Factored(Dec2003)RSA-640(193Digits) $20,000 Factored(Nov2005)RSA-704(212Digits) $30,000 Factored(July2012)RSA-768(232Digits) $50,000 Factored(Dec2009)RSA-896(270Digits) $75,000 NotFactoredRSA-1024(309Digits) $100,000 NotFactoredRSA-1536(463Digits) $150,000 NotFactoredRSA-2048(617Digits) $200,000 NotFactoredRSA-704 DecimalDigits:212

74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359146RSA-232(768bits)hasnotbeenfactoredsofar.1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079147RSA算法的速度由于都是大数计算，RSA最快的情况也比DES慢许多倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA是被研究得最广泛的公钥算法，提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一148本讲内容6、公钥密码的特征总结公开密钥算法设计需要有以下基本要求：加密与解密由不同的密钥完成；知道加密算法，从加密密钥得到解密密钥在计算上是不可行的；两个密钥中任何一个都可以作为加密而另一个用作解密。公钥密码的特征公钥密码算法基础单向函数

对于一个函数，如果对于其定义域上的任意x，都容易计算，同时，对于其值域中几乎所有的取值

y

，计算其逆函数都是不可行的，则函数被称为单向函数。

可以提供单向函数的三大数学难题大整数分解问题（简称IFP）；离散对数问题（简称DLP）；椭圆曲线离散对数问题（简称ECDLP）。

对于一个单向函数，如果其逆函数在已知某些辅助信息的情况下容易求解得出，则称该单向函数为单向陷门函数。构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“陷门”。单向陷门函数公钥密码算法除RSA算法以外，建立在不同计算难题上的其他公钥密码算法有：基于因子分解问题的Rabin算法；椭圆曲线公钥算法；基于有限域中离散对数难题的ElGamal公钥密码算法基于“子集和”难题的Merkle-HellmanKnapsack（背包）公钥密码算法；等等153本讲内容7、Diffie-Hellman密钥交换算法

Diffie-Hellman密钥交换是第一个公钥方案使用在一些常用安全协议或产品（例如SSH等）密钥交换方案不能用于交换任意信息允许两个用户可以安全地建立一个共享的秘密信息，用于后续的通讯过程该秘密信息仅为两个参与者知道算法的安全性依赖于有限域上计算离散对数的问题Diffie-Hellman密钥交换算法：通信双方/多方

选择大素数p，以及p的一个原根a用户A选择一个随机数Xa<p，计算Ya=aXamodp用户B选择一个随机数Xb<p，计算Yb=aXbmodp每一方保密X值，而将Y值交换给对方即：X是私钥，Y是公钥Diffie-Hellman密钥交换双方获得一个共享密钥K＝aXaXbmodp对于用户A，计算出K=YbXamodp用户B，可计算出K=YaXbmodp攻击者要获得K，需要求解离散对数实际使用中，素数p以及p的原根a可由一方选择后发给对方1575报文鉴别与哈希函数内容提要安全服务与安全需求报文鉴别的安全需求对报文加密来实现报文鉴别报文鉴别码哈希函数生日攻击158内容提要1、安全服务与安全需求159160复习：安全服务/安全需求我们的故事从哪里开始？

通信保密

：较早期的安全需求公开密钥密码对称密钥密码提炼：安全服务/安全需求“通信保密”可以概括所有的安全需求吗？

答：不能。信息安全需求有许多种，通信保密只是一种安全需求，我们对现实世界的安全需求提炼和归类，用以下抽象名词来概括典型的安全需求保密性（Confidentiality）完整性（Integrity）可用性（Availability）可认证（Authentication）抗抵赖/抗否认（Non-repudiation）161内容提要2、报文鉴别的安全需求162安全需求分析的例子泄密流量分析修改内容破坏数据包收到的先后顺序不承认发送过某个报文冒名顶替浏览器访问网银Web服务器应用的安全需求163164报文鉴别的安全需求报文鉴别的三重含义（安全需求）:1）保护报文的完整性2）验证发送者的身份3）抗抵赖：防止报文发送者抵赖

（解决争议）将尝试以下三种方案实现报文鉴别:报文加密报文鉴别码(MAC)HASH（哈希）函数165报文鉴别的含义注意：不是所有的方案都能够完整实现上述报文鉴别所包括的三个安全需求：1）需要仔细甄别2）训练密码学思维；3）分析过程比结论重要：将尝试以下三种方案实现报文鉴别:报文加密报文鉴别码(MAC)HASH（哈希）函数166一些名词的含意

报文vs.

明文

我们有时候不考虑保密性.报文鉴别（Message

Authentication）vs.身份认证（Authentication）内容提要3、对报文加密来实现报文鉴别3.1用对称密钥167168报文加密-对称密钥报文加密在提供保密性的同时，本身也能提供了某些报文鉴别的安全服务如果发送者使用对称密钥加密报文:接收者知道发送者创建了它（前提：接收者自己没有创建过）因为现在只有发送者和接收者知道这个对称密钥知道报文内容在通信过程中没有被篡改发送者（Source）A接收者（Destination）B169报文加密-对称密钥接收到的密文可以解密为明文，但可能难以自动确定报文是否被篡改报文应具有合适的结构，冗余信息或校验和来检测报文是否被更改发送者（Source）A接收者（Destination）B170报文加密-对称密钥AB:

E(K,M)，或记作EK(M)保密性——只有A和B知道K一定程度的报文鉴别——只能来自于A——传输过程中没被篡改 —需要有特定的格式/冗余不提供抗抵赖——接受者不能伪造报文——发送者不能否认报文发送者（Source）A接收者（Destination）B内容提要3、对报文加密来实现报文鉴别3.2用公开密钥密码171172报文加密-公钥加密如果使用公钥加密:无法实现报文鉴别所包括的任何一项安全服务因为任何人都知道公钥仅能提供“保密性”发送者（Source）A接收者（Destination）B173报文加密-私钥加密(签名)如果使用私钥加密:如果发送者使用私钥加密，则不具有保密性因为任何人都知道公钥然而可以实现报文鉴别所有的安全需求仍然需要冗余信息确认报文是否被篡改发送者（Source）A接收者（Destination）B174报文加密-先私钥后公钥发送者用私钥对报文签名，然后使用接收者的公钥加密同时提供保密性和报文鉴别的所有三种安全服务代价是需要使用两个公钥发送者（Source）A接收者（Destination）B175报文加密－公开密钥总结

公钥加密：仅提供保密性176报文加密－公开密钥总结

私钥加密：报文鉴别所有的三种安全服务177报文加密-私钥加密(签名)

发送者（Source）A接收者（Destination）B178报文加密－公开密钥总结

先私钥后公钥加密：保密性、报文鉴别的所有三种服务内容提要4、报文鉴别码4.1报文鉴别码的定义179180用加密实现报文鉴别的缺点Q:报文加密的缺点?开销

加密整个报文，相当于用整个报文作文报文鉴别码较难实现自动的181报文鉴别码(MAC)报文鉴别码：固定长度的比特串（例如128个bit,等）由报文鉴别码算法生成算法的输入包括：报文和密钥算法设计类似于对称密钥算法，但不可逆附加到报文上用于报文鉴别接收者对报文执行相同方向的计算并检查它是否与收到的MAC匹配确保报文来自声称的发送者且传输过程中没被篡改182报文鉴别码如图所示MAC提供报文鉴别的完整性、发送者身份验证两种安全服务183报文鉴别码为什么用MAC?有时候只需要报文鉴别有时需要长时间保存数据的完整性(例如：档案)注意MAC不是数字签名内容提要4、报文鉴别码4.2报文鉴别码的用法184185报文鉴别码的用法

(a)报文鉴别的1，2两项安全服务发送者（Source）A接收者（Destination）B186报文鉴别码的用法发送者（Source）A接收者（Destination）B

(b)保密性和报文鉴别的第1和2项服务明文加报文鉴别码187报文鉴别码的用法发送者（Source）A接收者（Destination）B

(b)保密性和报文鉴别的第1和2项服务密文加报文鉴别码内容提要4、报文鉴别码4.3报文鉴别码的性质188189MAC的性质MAC是密码性质校验和

MAC=CK(M)压缩可变长度的报文M使用秘钥K输出固定长度的报文鉴别码是一个多对一的函数可能许多报文有相同的MAC但是找到这些MAC值相同的报文是非常困难的190MAC的要求攻击：能够找到M’≠M,但CK(M’)＝CK(M)需要MAC满足以下要求:不能通过一个报文和它的MAC，找到另一条有相同MAC的报文MAC应该是均匀分布的MAC应该取决于报文的每一位191可以使用分组密码的CBC（CipherBlockChaining）模式将最后一个密文块作为MACDataAuthenticationAlgorithm(DAA)

报文鉴别码算法就是基于DES-CBC，是一个早期的MAC生成算法令IV=0并用比特0填充最后一个明文块在CBC模式下使用DES加密报文将最后一个密文块作为MAC值或者最后一个块的最左边的M位(16≤M≤64)这个算法最终得到的MAC太短，不够安全简单的构造MAC算法的方法192DAA算法内容提要5、哈希函数5.1哈希函数的定义与性质193194哈希函数（Hash）将任意长度的报文压缩到固定长度的二进制串：