复旦大学：《密码学基础》课程教学资源（课件讲稿）02 Introduction to Cryptography -Classical Encryption Techniques（cont.）

密码学基础(02) Introduction to Cryptography Classical Encryption Techniques(cont 復大辱软件学院 LiJT

LiJT 1 密码学基础（02） Introduction to Cryptography -Classical Encryption Techniques (cont.)

o Symmetric Cipher Model Secret key shared by Secret key shared by sender and recipient sender and recipient Transmitted ciphertext Plaintext Plaintext Encrvption algorithm Decryption algorithm Input output (e.g, DES) (reverse of encryption algorithm) 復大辱软件学院 LiST

LiJT 2 Symmetric Cipher Model

Discussion 模型合理吗? 什么当保密;什么当公开? 19世纪荷兰人 A Kerckhoffs就提出了一个在密 码学界被公认为基础的假设,也就是著名的 “ Kerckhoffs假设”:秘密必须全寓于密钥。 Other models? 復大辱软件学院 LiST

LiJT 3 Discussion • 模型合理吗？ • 什么当保密；什么当公开？ – 19世纪荷兰人A.Kerckhoffs就提出了一个在密 码学界被公认为基础的假设，也就是著名的 “Kerckhoffs假设” ：秘密必须全寓于密钥。 • Other Models?

Discussion 谁是我们的敌人,谁是我们的朋友,这个 问题是革命的首要问题”—毛选 易用性 ·秘密全部寓于密钥≠算法当公开,要看应用 环境(商用,军用,……) ·开放的系统更安全,?? 復大辱软件学院 LiJT

LiJT 4 Discussion • “谁是我们的敌人，谁是我们的朋友，这个 问题是革命的首要问题”——毛选 • 易用性 • 秘密全部寓于密钥≠算法当公开，要看应用 环境(商用，军用，……) • 开放的系统更安全，??

o Cryptanalytic Attacks ·对于对手而言 最坏情况下,仍有一种攻击方法可用 Brute force search,穷举法 復大辱软件学院 LiJT

LiJT 5 Cryptanalytic Attacks • 对于对手而言 – 最坏情况下，仍有一种攻击方法可用 • Brute Force Search，穷举法

Brute Force Search always possible to simply try every key most basic attack, proportional to key size assume either know or recognise plaintext Number of Alternative Time required at 10 Key Size(bits) Ke eys Time required at I encryption/us encryptions 232=43x10° 23I Hs =35.8 minutes 2. 15 milliseconds 26⑧ 2=72x1010 2sps =114] years 10.01 hours 212=34x103 2127 Hs =54 1024years 5.4 x 108 years 2108=37x10 2167s=59×10ycas 59 x 100years 26 characters 26!=4xl026 (permutation) 2x1030ps=64x102yes 64xl0° years 6 復大辱软件学院 LiJT

LiJT 6 Brute Force Search • always possible to simply try every key • most basic attack, proportional to key size • assume either know or recognise plaintext

er Monoalphabetic Cipher Security now have a total of 26! 4 x 1026 keys with so many keys, might think is secure but would be ! wrong!!! problem is language characteristics 復大辱软件学院 LiJT

LiJT 7 Monoalphabetic Cipher Security • now have a total of 26! = 4 x 1026 keys • with so many keys, might think is secure • • but would be !!!WRONG!!! • problem is language characteristics

o Example Cryptanalysis given ciphertext UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZ SHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ count relative letter frequencies(see text) guess P&z are e and t guess ZW is th and hence ZWP is the proceeding with trial and error finally get it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong in moscow 8 復大辱软件学院 LiJT

LiJT 8 Example Cryptanalysis • given ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ • count relative letter frequencies (see text) • guess P & Z are e and t • guess ZW is th and hence ZWP is the • proceeding with trial and error finally get: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong in moscow

2 Use in Cryptanalysis key concept-monoalphabetic substitution ciphers do not change relative letter frequencies discovered by Arabian scientists in gtn century calculate letter frequencies for ciphertext compare counts/plots against known values if Caesar cipher look for common peaks/troughs peaks at: A-E-I triple, No pair, RST triple troughs at: JK, X-Z for monoalphabetic must identify each letter tables of common double/triple letters help 復大辱软件学院 LiJT

LiJT 9 Use in Cryptanalysis • key concept - monoalphabetic substitution ciphers do not change relative letter frequencies • discovered by Arabian scientists in 9th century • calculate letter frequencies for ciphertext • compare counts/plots against known values • if Caesar cipher look for common peaks/troughs – peaks at: A-E-I triple, NO pair, RST triple – troughs at: JK, X-Z • for monoalphabetic must identify each letter – tables of common double/triple letters help

More Definitions unconditional security no matter how much computer power is available, the cipher cannot be broken since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext computational security given limited computing resources(eg time needed for calculations is greater than age of universe), the cipher cannot be broken Unconditional security would be nice, but the only known such cipher is the one-time pad (later) For all reasonable encryption algorithms, have to assume computational security where it either takes too long, or is too expensive, to bother breaking the cipher. 復大辱软件学院 LiST

LiJT 10 More Definitions • unconditional security – no matter how much computer power is available, the cipher cannot be broken since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext • computational security – given limited computing resources (eg. time needed for calculations is greater than age of universe), the cipher cannot be broken • Unconditional security would be nice, but the only known such cipher is the one-time pad (later). – For all reasonable encryption algorithms, have to assume computational security where it either takes too long, or is too expensive, to bother breaking the cipher