附錄 密碼學基本觀

加密與解密 密碼系統是由明文、加密演算法、金鑰、解密演算法及密文所組成 當加密金鑰與解密金鑰為同一把時，此密碼系統為對稱式密碼系統 金鑰用來和加密演算法產生特定密文的符號字串 金鑰是一組具有相當長度的數字或符號字串，其長度通常以位元為單位 金鑰是演算法內的一個變數，不同的金鑰將產生不一樣的密文 就密碼學而言，金鑰的長度越長，密文越安全 當加密金鑰與解密金鑰為同一把時，此密碼系統為對稱式密碼系統 當加密金鑰與解密金鑰不同時，此密碼系統為非對稱式密碼系統

加密與解密 加密演算法 解密演算法 密文 明文 If K=K’, symmetric (對稱) cryp’tography If K≠K’, asymmetric (非對稱) cryptography 加密演算法 解密演算法 Message M (plaintext) Encrypt cyphertext Decrypt Message M 密文 明文 Key K Key K’

完整性驗證 (Integrity Check) 為偵測所傳送出的訊息是否遭竄改，可實行完整性驗證 傳送者和接收者共享一把完整性驗證金鑰(integrity key) 訊息傳送者使用一個公開的訊息驗證函數(message authentication function)及其私密的完整性驗證金鑰，為即將外送的訊息計算其訊息驗證碼(Message Authentication Code, MAC) 訊息的送方將訊息與訊息驗證碼傳給訊息接收者 訊息接收者將所收到的訊息，以訊息驗證函數及其私密的完整性驗證金鑰產生出訊息驗證碼 訊息接收者比對自行產生的訊息驗證碼與所收到的訊息驗證碼是否一致 倘若一致，則判定所收到的訊息並未經過竄改

「完整性驗證」的本質為數位簽章(digital signature)機制

何謂「數位簽章」？ An electronic signature that can be used to authenticate the identity of the sender of a message or the signer of a document, and possibly to ensure that the original content of the message or document that has been sent is unchanged. Easily transportable, cannot be imitated by someone else, and can be automatically time-stamped The originator of a message uses a signing key (Private Key) to sign the message and send the message and its digital signature to a recipient The recipient uses a verification key (Public Key) to verify the origin of the message and that it has not been tampered with while in transit

基本組成 (1/2) Digital signatures employ a type of asymmetric cryptography, typically consisting of 3 algorithms A key generation algorithm that selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key. A signing algorithm that, given a message and a private key, produces a signature. A signature verifying algorithm that, given a message, public key and a signature, either accepts or rejects the message's claim to authenticity Hash value of a message when encrypted with the private key of a person is his digital signature on that e-document

基本組成 (2/2) Each individual (個體) generates his own key pair [public key, private key] Public key is known to everyone, private key only to the owner Private Key – Used for making Digital Signature Public Key – Used to verify the Digital Signature

fe1188eecd44ee23e13c4b6655edc8cd5cdb6f25 數位簽章例 I agree efcc61c1c03db8d8ea8569545c073c814a0ed755 My place of birth is at Gwalior. fe1188eecd44ee23e13c4b6655edc8cd5cdb6f25 I am 62 years old. 0e6d7d56c4520756f59235b6ae981cdb5f9820a0 I am an Engineer. ea0ae29b3b2c20fc018aaca45c3746a057b893e7 I am a Engineer. 01f1d8abd9c2e6130870842055d97d315dff1ea3 These are digital signatures of same person on different documents Digital Signatures are numbers Same Length – 40 digits They are document content dependent

「訊息摘要」演算法(Message-Digest Algorithm)確保簽署者身分與訊息的完整性 訊息摘要演算法亦稱為「雜湊」 演算法 (hash algorithm) Secret key and message are hashed together Re-computation of digest verifies that a message actually originated from the correct peer and was not altered in transit 著名範例: HMAC-MD5, HMAC-SHA Google可找到各種程式語言的實作 “Secret Key” Hash Function A message digest algorithm reduces a message of any length via rounds of compression permutations, to a string of fixed length called the message digest. The hash function is called a one-way function and it’s goal is to produce unique results. Collisions occur when more than one message can hash to the same message digest. The longer the message digest result, the less chance of collisions. The original hash algorithms have been enhanced by the addition of the secret key that is shared between the communicating parties. This key is hashed with the message to help provide uniqueness and authentication. These newer variations are called HMAC (Hash Message Authentication Code) algorithms. The MD5 (Message Digest 5) algorithm produces a 128 bit message digest, the SHA (Secure Hash Algorithm) yields a 160 bit result. See RFC 1321 MD5 for more detail. Hash

數位簽章的實作方式 (1/2) Message One-way function (單向函數): Easy to produce hash from message, “impossible” to produce message from hash Hash Function Alice A digital signature is an application in which the signer, “signs” a message in such a way that anyone can verify that the message was signed byno one but the sender, and consequently that the message has not been modified since it was signed. A digital signature usually involves a message-digest algorithm and a public-key (asymmetric) algorithm for encrypting the message digest. The entire message need not be signed. By using a one-way function—such as a hash function—it is possible to digest the entire message into a small string. The hash of the message can produces the digest, but given a digest, it is impossible to determine what the message was. Minute changes in message—added white space, lowercase letter changed to uppercase—will have demonstrable impact on digest Digest is signed and transmitted with message Hash of Message s74hr7sh7040236fw 7sr7ewq7ytoj56o457 Sign Hash with Private Key Signature = Encrypted Hash of Message 54 21 54

數位簽章的實作方式 (2/2)：核驗是否相符 55 22 55 Decrypt the received signature Message Decrypt the received signature Signature Re-hash the received message Message with appended signature Message Signature Alice Hash Function Decrypt using Alice’s Public Key Upon receipt of a signed message, the digest is reproduced, and the signature is verified against this digest. Hash of Message Hash Message If hashes are equal, signature is authentic 55 22 55

RSA數位簽章演算法* 設h(M)代表訊息M的訊息指紋值，則RSA數位簽章的產生與檢驗可描述如下 (1) 產生RSA簽章：用私密金鑰d與公開金鑰n以下列公式計算簽章s (2) 檢驗RSA簽章：將收到的訊息M重新計算訊息指紋值h(M)。用私密金鑰e核驗，若且唯若下列公式成立則接受簽章，否則拒絕

可以OpenSSL實作數位簽章機制 OpenSSL is an open-source implementation of the SSL and TLS protocols Implements basic cryptographic functions and provides various utility functions Support various platforms (Unix/Linux/Windows) Can be invoked with command lines OpenSSL is mostly used on Unix. To use it on Windows, we need to install ActivePerl http://www.activestate.com/ActivePerl/ http://www.openssl.org Win32 OpenSSL (Windows version) http://www.slproweb.com/products/Win32OpenSSL.html

Environment Setup (1/2) Install ActivePerl (http://www.activestate.com/ActivePerl/)

Environment Setup (2/2) Install OpenSSL (http://www.openssl.org/) 下載、並利用WinRAR解壓縮至選定的目錄夾 (e.g. c:\openssl) 啟動MS-DOS視窗 之後，依序鍵入底 下命令 cd c:\openssl ms\bcb4

OpenSSL: 指令例 All the commands are placed in subdirectory OUT32 The following commands help familiarize yourself with common operations openssl des-ecb -e -in xxx.txt -out yyy.out -k password (DES encryption) openssl des-ecb -d -in yyy.out -out xxx.txt -k password (DES decryption) openssl aes-128-ecb -e -in xxx.txt -out yyy.out -k password (AES encryption) openssl aes-128-ecb -d -in yyy.out -out xxx.txt -k password (AES decryption) openssl genrsa -out rsa_privatekey.pem -passoutpass:password -des3 1024 (generate a RSA private key of 1024 bits) openssl rsa -in rsa_privatekey.pem -passinpass:password -pubout -out rsa_publickey.pem (generate the associated RSA public key) openssl rsautl -encrypt -pubin -inkeyrsa_publickey.pem -in xxx.txt -out yyy.txt (Encrypt file xxx.txt using a public key) openssl rsautl -decrypt -inkeyrsa_privatekey.pem -in yyy.txt -out xxx.txt (Decrypt file yyy.txt using a private key)

Key Generation, Signing Generate a file “privatekey.pem” to store the RSA private key and “publickey.pem” store the public key Private key generation openssl genrsa -out privatekey.pem Generate the public key associated with the given private key openssl rsa -in privatekey.pem -out publickey.pem -pubout -outform PEM Signing process To sign file “doc.txt”, compute the digest (hash) with the one-way hash function SHA-256 and then use “privatekey.pem” to generate the resulting signature. The output signature is stored in file “doc.sig” openssl dgst -sha256 -sign privatekey.pem -out doc.sig doc.txt PEM (Privacy Enhanced Email) is a special file format that accommodates cryptographic keys or certificates.

Signature Verification Anyone can verify the authenticity of the received message by checking if its signature is matched Provided file “doc.txt” and its associated signature file “doc.sig” , one can validate the signature using the public key stored in file “publickey.pem” and SHA256/RSA: openssl dgst -sha256 -verify publickey.pem -signature doc.sig doc.txt

Signature Verification Anyone can verify the authenticity of the received message by checking if its signature is matched What happens if we modify any content of file “doc.txt”? Suppose the text “This is a test” is changed to “That is a test” and then saved in another new file “doc2.txt”. Signature verification using “doc.sig” and “doc2.txt” fails!

參考資源 OpenSSL commands http://www.madboa.com/geek/openssl/ http://dsd.lbl.gov/~ksb/Scratch/openssl.html

How to Verify a Public Key? Two approaches: Before you use Alice’s public key, call her or meet her and check that you have the right one Fingerprint or hash of the key can be checked on the phone Find someone you already trust to certify that the key really belongs to Alice By checking for a trusted digital signature on the key Public key infrastructure

RSA (Rivest-Shamir-Adleman) Crypto Algorithms

Modulo Operations Let a,b  Z, m  Z+. Z+ = {n  Z | n > 0} = N−{0} Then a is congruent to b modulo m, written “a  b (mod m)”, iff m | ab Example ≡ 3 (mod 5) ≡ 2 (mod 5) ≡ 1 (mod 5) ≡ 0 (mod 5) ≡ 4 (mod 5) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Inverse An inverse of a, modulo m is any integer a′ such that a′a ≡ 1 (mod m) If we can find such an a′, notice that we can then solve ax≡b by multiplying through by it, giving a′ax≡a′b, thus 1·x≡a′b, thus x≡a′b Theorem: If gcd(a,m)=1 and m > 1, then a has a unique (modulo m) inverse a′

Chinese Remainder Theorem (CRT, 中國餘數定理) Theorem: Let m1,…,mn > 0 be relatively prime. Then the system of equations x ≡ ai (mod mi) (for i = 1 to n) has a unique solution modulo m = m1·…·mn Proof: (略) Let Mi = m/mi. (Thus gcd(mi, Mi)=1) By theorem 3, yi=Mi′ such that yiMi≡1 (mod mi) Now let x = ∑i aiyiMi. Since mi|Mk for k≠i, Mk≡0 (mod mi), so x≡aiyiMi≡ai (mod mi) Thus the congruences hold. (Uniqueness is an exercise.) □

中國餘數定理 中國餘數定理源出三國或晉朝的「孫子算經」，其中有一題：今有物不知其數，三三數之賸二，五五數之賸三，七七數之賸二，問物幾何? 以同餘式表之，即解 。孫子算經給出答案 x = 23 解: x 的齊次解為105t，假設特別解為x=15a+21b+35c, 代入j，則35c ≡ 2 (mod 3) 取c = 1，代入k，則 b ≡ 3 (mod 5) 取b = 3，代入l，則 a ≡ 2 (mod 7) 取a = 2，所以x=30+63+35=128=105+23,可取x = 23 此即原式的特別解 ∴x=105t+23

Fermat’s Little Theorem (費瑪小定理) Fermat generalized the ancient observation that 2p−1≡1 (mod p) for primes p to the following more general theorem: Theorem: (Fermat’s Little Theorem) If ¬(p|a), then ap−1≡1 (mod p) Further, if p is prime and a is any non-negative integer, then ap≡a (mod p)

Rivest-Shamir-Adleman (RSA) The public key <n,e> The product n = pq (but not p and q), and An exponent e that is relatively prime to (p−1)(q−1) The private key consists of: A pair p,q of large random prime numbers, and d, an inverse of e modulo (p−1)(q−1), but not e itself To encrypt a message encoded as an integer M < n Compute C = Me mod n To decrypt the encoded message C Compute M = Cd mod n

Correctness of RSA Encryption: C = Me mod n Decryption: M = Cd mod n Theorem: (Me)d ≡ M (mod n). 證明方式如下: By the definition of d, we know that de ≡ 1 [mod (p−1)(q−1)] Thus by the definition of modular congruence, k: de = 1 + k(p−1)(q−1) So, the result of decryption is Cd ≡ (Me)d = Mde = M1+k(p−1)(q−1) (mod n) Assuming that M is not divisible by either p or q, Which is nearly always the case when p and q are very large Fermat’s Little Theorem tells us that Mp−1≡1 (mod p) and Mq−1≡1 (mod q) Thus, the following two congruences hold: Cd ≡ M·(Mp−1)k(q−1) ≡ M·1k(q−1) ≡ M (mod p) Cd ≡ M·(Mq−1)k(p−1) ≡ M·1k(p−1) ≡ M (mod q) Since gcd(p,q)=1, we can use the Chinese Remainder Theorem to show that Cd≡M (mod pq) If Cd≡M (mod pq) then s: Cd=spq+M, so Cd≡M (mod p) and (mod q). Thus M is a solution to these two congruences, so (by CRT) it’s the only solution.■