弘光技術學院 資訊管理系助理教授兼電算中心主任 丁德榮 博士 Chapter 1 Foundations 弘光技術學院 資訊管理系助理教授兼電算中心主任 丁德榮 博士

Outline Terminology Steganography Substitution Cipher and Transposition Ciphers Simple XOR Private Key and Public Key Cryptosystem One-time Pads Computer Algorithm Large Numbers

Terminology Sender and Receiver Plaintext （明文） or cleartext: message Encryption（加密）：the process of disguising a message in such a way as to hide its substance. Ciphertext（密文）: an encrypted message Decryption: The process of turning ciphertext into plaintext is decryption.

Terminology Cryptography: the art and science of keeping message secure. Cryptanalysis: the art and science of breaking ciphertext

明文在網路上傳輸的危險性 A B pw:天地玄黃 pw:天地玄黃 NetXray pw:天地玄黃 E eavesdropper

其他傳輸危險 Eavesdropping OS漏洞 Password的竊取 Spoofing Session Hijacking 特洛依木馬、virus、trapdoor Covert Channel

加密系統的應用 B A 解密 加密 eavesdropper E pw:天地玄黃 pw:天地玄黃 @#$%&* @#$%&* NetXray

加 密 與 解 密 Decryption Encryption M C 密文 明文

Cryptosystem Plaintext: M or P Ciphertext: C (same size or larger) a stream of bits, a text file, a stream of digitized voice, video image, ...(binary data) Ciphertext: C (same size or larger) Encryption function E: E(M)=C operate on M to produce C. Decryption function D: D(C)=M operate on C to produce M D(E(M))=M

The job of cryptography Authentication: It should be possible for the receiver of a message to ascertain its origin; an intruder should not be able to masquerade as someone else. Integrity: It should be possible for the receiver of a message to verify that it has not been modified in transit;an intruder should not be able to substitute a false message of a legitimate one. Nonrepudiation: A sender should not be able to falsely later that he sent a message.

Terminology cryptographic algorithm or cipher Restricted algorithm: the mathematical function used for encryption and decryption. Restricted algorithm: If the security of an algorithm is based on keeping the way that the algorithm works a secret. large or changing group can’t use them no quality control and standard can’t use off-the-shelf hardware or software products popular for low-security applications.

Key cryptosystem Ek(M)=C Ek1(M)=C Dk(C)=M Dk2(C)=M Dk(Ek(M))=M Key K Keyspace: the range of possible values of the key called the keyspace. All of the security in these algorithms is based in the key; none is based in the details of the algorithm. Ek(M)=C Dk(C)=M Dk(Ek(M))=M Ek1(M)=C Dk2(C)=M Dk2(Ek1(M))=M

Key cryptosystem Decryption Encryption M C e K d 密文 明文

Key based algorithms Symmetric algorithm Public-key algorithm

Symmetric algorithm conventional algorithm, single-key, one-key, secret-key algorithm encryption key can be calculated from the decryption key and vice versa. the same key The security of a symmetric algorithm resets in the keys. Two categories: block cipher: operate on the plaintext a single bit (or byte, work) at a time. stream cipher: operate on the plaintext in groups of bits, the groups of bits are called block. (block size =64 bits)

Public-key algorithm asymmetric algorithm encrypted key ≠decrypted key the decrypted key can’t be calculated from the encrypted key (at least in any reasonable amount of time) the encryption key can be made public: public key private key: decrypted key Can apply to digital signatures

Cryptanalysis The whole point of cryptography is to keep the plaintext (key) secret from eavesdroppers. Cryptanalysis is the science of recovering the plaintext of a message without access to the key. Attack: a attempted cryptanalysis is called an attack. Kerckhoffs assumes that the cryptanalyst has complete details of the cryptographic algorithm and implementation. So suggests that the secrecy must reside entirely in the key.

Cryptanalytic attacks Ciphertxt-only attack （密文攻擊法）:只有密文 Known-plaintext attack （以知明文攻擊法）：有明文及密文 Chosen-plaintext attack （選擇明文攻擊法）：有明文及密文外，選擇一些明文經加祕後之密文 Adaptive-chosen-plaintext attack：為chosen-plaintext attack （選擇明文攻擊法）的一特例，可修改其選擇。 Chosen-ciphertext attack （選擇密文攻擊法） Chosen-key attack （選擇鑰匙攻擊法）：已之一些keys間的關聯 Rubber-hose cryptanalysis（塑膠軟管的攻擊）：威脅，恐嚇，黑函，賄路（purchase-key attack）

Security of Algorithms Security of algorithms depends on “how hard they are break”. probably safe: If the cost required to break an algorithm is greater than the value of the encrypted data. If the time required to break an algorithm is longer than the time the encrypted data must remain secret. If the amount of data encrypted with a single key is less than the amount of data necessary to break the algorithm.

Breaking an algorithm Lars Knudsen classified these different categories of breaking an algorithm Total break: find KEY Global deduction: find an alternate algorithm A equivalent to Dk(C) without knowing K. Instance(or local)deduction: find the plaintext of an intercepted ciphertext. Information deduction: gains some information about the key or plaintext.

Secure of algorithm parallel computer Unconditionally secure: No matter how much ciphertext a cryptanalyst has, there is not enough information to recover the plaintext. e.g. one-time pad brute-force attack Computationally secure: It cannot be broken with available resources,either current or future. Complexity of an attack Data complexity: the amount of data needed as input to the attack. Processing complexity: work factor, The time needed to perform the attack. Storage requirements: The amount of memory needed to do the attack. Complexities are expressed as orders of magnitude. 2128 parallel computer

Steganography Steganography serves to hide secret message in other messages, such that the secret’s very existence is concealed. invisible inks （隱藏式墨水） tiny punctures on selected characters (針刺小孔） minute differences between handwrite characters. pencil marks on selected characters etc. hiding secret message in graphic image (watermark).

Substitution Cipher and Transposition Ciphers each characters in the plaintext is substituted for another character in the ciphertext The receiver inverts the substitution on the ciphertext to recover the plaintext.

Substitution Ciphers(對稱性加密) 原始文字與加密文字對照表 那麼apple這個字就會變成bqqmf了 I love you 變成j mpwf zpv 加密時向右移一位, 解密時向左移一位 加解密的 Key 相同

Substitution Cipher Simple substitution cipher or monoalphabetic cipher homophonic substitution cipher polygram substitution cipher polyalphabetic substitution cipher

Caesar Cipher Each plaintext character is replaced by the character three to the right modulo 26

ROT13 Unix system Every letters is rotated 13 places Encrypting a file twice with ROT13 restores the original fie P=ROT13(ROT13(P))

Some substitution ciphers Homophonic substitution ciphers Playfair cipher Hill cipher Huffman coding polyalphabetic substitution ciphers Vigenere cipher running-key cipher

Transposition Cipher The plaintext remains the same, but the order of the characters is shuffled around. 這富額代能都一　 獸貴上表買能個　 又，打名賣夠人　 強奴印字。算。 迫隸記的這出這 所或。數裡獸數 有自這字需的字 的由印；要數是 人人記沒有字六 ，，就有智，百 無在是這慧因六 論他那印。為十 大們獸記凡這六 小的的的是數。 ，右右，聰字 貧手字就明代 窮和或不人表 這富額代能都一獸貴上表買能個又，打名賣夠人強奴印字。算。迫隸記的這出這所或。數裡獸數有自這字需的字的由印；要數是人人記沒有字六，，就有智，百無在是這慧因六論他那印。為十 大們獸記凡這六小的的的是數。，右右，聰字貧手字就明代窮和或不人表

Simple columnar transposition cipher

Rotor Machines

Private Key and Public Key Private Key Cryptosystem秘密金匙密碼系統： Ek：只有加密者知道 若知 Ek則知 Dk。(Ek=Dk) 又稱Symmetric Key Cryptosystem， Conventional Cryptosystem

Private Key Cryptosystem的優點 保護資訊機密 鑑定發送方之身分 Receiver選一亂數 r，送給Sender Sender 將r 加密成密文c，送給sender Sender將C 解密確認是否r。 確保資訊完整性 將加密後的密文附在明文的後方，供receiver檢查。

Private Key Cryptosystem的缺點 Key distribution Problem：需要有一個安全通道（secure channel） Key 的 數目太大： 無法達到不可否認性（Nonrepudiation）之服務

Motivation of Public Key Cryptosystem 1975 Diffe 是否從未謀面的兩個人，可以從事秘密通訊？ 是否有一種純是數位的message，可以向其他人證明此message確實是發送自某人。 1976 Public Key Cryptosystem 產生。

Public Key Cryptosystem Ek ≠Dk 從Ek 不能推出Dk， 反之亦然。 將Ek 公開，而Dk保密。 任何人可以用Ek加密，但只有擁有Dk者能解密。（秘密） 擁有者可以用Dk加密，所有人均可以用Dk解密。（認證） Tow-key Cryptosystem or Asymmetric Cryptosystem

Diffie and Hellman 1976 PKDS （public Key Distribution System）公開金匙分配系統 從未謀面的兩個人，可以從事秘密通訊？

Public-Key Cryptosystem的功能 保護資訊機密 簡化金匙分配及管理：公開PUBLIC KEY，保留Secure key。 達到不可否認性的功能：透過數位簽章（Digital Signature）的方式達到 用private key DK將Plaintext加密（簽署）成密文 任何人可Ek解密成明文，來確認明文

Digital Signature 數位簽章 A digital signature is a property private to a user or process that is used for signing message. Let B be the recipient of a message M signed by A. Then A’s signature must satisfy three requirements: B 要能從M中認出A的簽名 任何人都不可以偽造A的簽名 一但A否定他的簽章，則要有第三者或公證者來解決爭議。

Digital Signature 與 public key cryptosystem 差異 Dk2(C)=Dk2(Ek1(m))=m Digital Signature Ek1(S)=Ek1(Dk2(m))=m Note: 並非所有的Public-Key Cryptosystem均可同時作為加密與數位簽章之用。 少數可用：RSA system 條件：Dk2(Ek1(m))= Ek1(Dk2(m))

Public-Key Cryptosystem的缺點 加解密系統運算複雜 速度慢

混合型密碼系統 以public-key cryptosystem 作數位簽章以解決key distribution problem 以private-key cryptosystem 作加密（DES）

理論安全與實際安全

安全問題 如何證明CRYPTOSYSTEM是安全的 破密 v. s. 解密的交互攻防 密碼系統的安全性要考量哪些？ 當破密者有無限制的時間與計算能力來對密文加以分析時，一個密碼系統能有多大的安全性？ 當破密者在有限的時間及計算能力對密文的分析下，一個密碼系統是否夠安全？

理論安全 Theoretical Security 不管破密者截獲多少密文，並隊之加以分析，其結果是與直接猜明文一樣。 Perfect Security Shannon證明： 一個密碼系統要達到理論安全，必須 加密key的長度要大於或等於plaintext的長度。 key只能用一次，用後即丟。 此系統稱為： 一次活頁（One-time Pad) system

Simple XOR XOR is exclusive-or operation: ‘^’ in C or ⊕ in math. 0 ⊕0=0, 0 ⊕1=1, 1 ⊕0=1, 1 ⊕1=0. a ⊕a =0, a ⊕b ⊕b=a. simple-XOR algorithm = Vigenere polyalphabetic cipher. Symmetric algorithm P ⊕K=C and C ⊕K=P

Code for simple-XOR

One-time Pads perfect encryption scheme 1917 Major Joseph Mauborgne and Gilbert Vernam A one-time pad is noting more than a large nonrepeating set of truly random key letters, written on sheets of paper, and glued together in a pad. Each key letter is used exactly once, for only one message. The sender encrypts the message and then destroys the used pages of the pad. The receiver has an identical pad and uses each key on the pad, in turn, to decrypt.

Example of One-time Pad

Stream Cryptosystem串流密碼系統 key length =n 以亂數產生器產生2n位元的sequence of random numbers作key 猜對key之機率為： 非perfect security

Practical Security 實際安全 W(n): 每一密碼系統在給定n位元密文時，破解此系統的最少工作次數，稱為工作特徵（work characteristic）W(n)。 W(n): 所有破解此密碼系統的方法中，最佳的方法所需要的最少次數。 Practical Security 實際安全：若一個系統的W(n) 大到使的具有有限能計算能力及記憶體的破密者，無法再合理的時間內破解此系統。 or Computational Security 計算上安全

Time Complexity n5 2n n!

歷史工作特徵Historical Work Characteristic W(n)的最佳值無法以理論求出。 歷史工作特徵 Wh(n)：已知n位元密文時，人們所知最好的攻擊方法。 W(n) < Wh(n) 若 一個密碼系統的Wh(n)很小且又很容易被破密者找到其他破解法時，則此系統不安全。

單向函數與單向暗門函數 單向函數（One-Way Function） 對於所有屬於 f 之域(domain)的任一個x，很容易計算出 f(x)=y。 對於幾乎所有的(Almost all)屬於f 的範圍(Range) 的任一個y，則在計算上不可能（Computational Infeasible）求出x使的y=f(x)

單向暗門函數 One-way Trapdoor Function 對於所有屬於 f 之域(domain)的任一個x，很容易計算出 f(x)=y。 對於幾乎所有的(Almost all)屬於f 的範圍的任一個y，則在計算上除非獲得暗門，否則不可能（Computational Infeasible）求出x使的x=F-1(y)。但若有一資料z （暗門trapdoor），則可以容易求出x使的x=F-1(y)。 緊急出口

特性 若有單向按門函數存在，則可以用以設計Public-Key Cryptosystem Key : 暗門 1985: ElGamal 提出 若單向函數滿足交換性（Communication property），則單向函數亦可以用於設計Public-Key Cryptosystem。 交換性（Communication property） Fx(Fy(z))=Fy(Fz(x))

One-Way Function 多項式（Polynomial）: y=f(x)=xn+an-1xn-1+...+a1x+a0mod p 若給定an-1, ..., a, a0, p 則Y可利用Honer’s Rule計算須n次乘法及n-1次加法。 但若給定a0, a1, ..., an-1 及 y 要求 x則要n2(log2p)2

因數分解問題 Factorization Problem FAC 給一個奇數，欲判斷其是否為質數（prime number），約(log 2 p)4 512 bits 約 10 分鐘 若給定兩個大質數p, q，求乘績 1次乘法。 若給一大數n，求出確實的p, q，稱為 Factorization Problem，需要 exp{C(ln n ln (ln n ))1/2}

迷袋問題Knapsack Problem 已知有限個自然數列集合B=(b1, b2, ..., bn)，及二進位x=(x1, x2, ..., xn)，xi in {0,1}。要求出 只須 n-1次加法。 若給定B及S，要求出X則很難。 為NP-Complete Problem

姐離散數對問題Discrete Logarithm Problem DLP