密碼學概論 Speaker:謝凱評

大綱 簡介 密碼系統 ( Cryptographic System ) 虛擬亂數產生器 ( Pseudo Random Number Generator, PRNG ) 簽章 ( Digital Signature ) 雜湊函數 ( Hash )

簡介

常見的密碼元件 密碼系統 ( Cryptographic System ) 虛擬亂數產生器 ( Pseudo Random Number Generator, PRNG ) 簽章 ( Digital Signature ) 雜湊函數 ( Hash )

密碼系統 symmetric encryption (Secret-Key) 秘密不被其他人所知道 asymmetric encryption (Public-Key) 收發雙方擁有一對不同的key 公鑰假設大家都知道

加密與解密 當K1=K2, 稱為對稱式密碼系統 當K1≠K2, 稱為非對稱式密碼系統或公開金鑰密碼系統, K1稱做公鑰, K2稱做私鑰

對稱式密碼系統 區塊加密器 ( Block Cipher ) 串流加密器 ( Stream Cipher ) 將 plain text 分成多個 block(區塊) 後，一次針對一個 block 進行加密處理。 例如DES, Triple DES, IDEA, AES 串流加密器 ( Stream Cipher ) 將 plain text 中的每一個 bit 逐一加密 例如RC4, eSTREAM portfolios

非對稱式密碼系統 基於數學難題，運算速度慢，但無須考慮金鑰分配的問題，用於較少量的資料加解密，例如保護對稱式金鑰 例如RSA (Rivest, Shamir, Adleman)

理論安全與實際安全 理論安全 假設密碼元件金鑰為k位元, 對n位元的明文加密, 破密得到明文的機率=直接猜對明文的機率, 稱為理論安全. 實際安全 雖無法到達理論安全, 但卻使破解系統所需的計算能力與時間在合理的範圍內達成, 稱為實際安全.

暴力攻擊的時間 Table 2.1 from the text shows how much time is involved for various key sizes. The table shows results for each key size, assuming that it takes 1 µs to perform a single decryption, a reasonable order of magnitude for today's computers. With the use of massively parallel organizations of microprocessors, it may be possible to achieve processing rates many orders of magnitude greater. The final column of the table considers the results for a system that can process 1 million keys per microsecond. At this performance level, a 56-bit key is no longer computationally secure. The assumption of one encryption per microsecond is overly conservative. The widely used encryption scheme, the Data Encryption Standard (DES) was finally and definitively proved insecure in July 1998, when the Electronic Frontier Foundation (EFF) announced that it had broken a DES encryption using a special-purpose "DES cracker" machine that was built for less than $250,000. The attack took less than three days. The EFF has published a detailed description of the machine, enabling others to build their own cracker [EFF98]. It is important to note that there is more to a key-search attack than simply running through all possible keys. Unless known plaintext is provided, the analyst must be able to recognize plaintext as plaintext. If the message is just plain text in English, then the result pops out easily. If the message is some more general type of data, such as a numerical file, and this has been compressed, the problem becomes even more difficult to automate. Thus, to supplement the brute-force approach, some degree of knowledge about the expected plaintext is needed, and some means of automatically distinguishing plaintext from garble is also needed. The EFF approach addresses this issue as well and introduces some automated techniques that would be effective in many contexts. Figure 2.2 shows how long it would take to crack a DES-style algorithm as a function of key size.

有名的區塊加密器

Block Cipher的結構

亂數產生器 真亂數產生器 虛擬亂數產生器 具不可複製之特性 例如電訊號產生的熱雜訊，樂透彩中使用的風壓器 具可複製之特性(透過Seed來達到複製的效果) 例如C語言的rand()函式

串流加密器與亂數產生器之關係 設計一個”串流加密器”，等同設計一個”虛擬亂數產生器”

串流加密器之加解密

虛擬亂數產生器 亂數產生器的目標在於產出一擬亂序列(金鑰串流), 其應具有 長週期 平均分布 不可預測性 大的線性複雜度 良好的線性複雜度剖繪

串流加密與區塊加密之比較 串流加密器主要優點在速度較快 一連串的資料適用於串流加密 整段的資料適用於區塊加密 即時影像、瀏覽器連結 電子郵件、檔案傳輸

使用公鑰系統加密與簽章技術 同時具有機密性與鑑別性 A先以自己的私有金鑰加密M，提供了鑑別性 再以B的公開金鑰加密M，提供了機密性

數位簽章( Signature )

雜湊函數( Hash function ) 功能 用途 常用的單向雜湊函數 輸入任意長度之x，可輸出固定長度h(x) 增加資料完整性 MD5, SHA-1

Message Authentic-ation Figure 2.6 illustrates three ways in which the message can be authenticated. The message digest can be encrypted using conventional encryption (part a); if it is assumed that only the sender and receiver share the encryption key, then authenticity is assured. The message can also be encrypted using public-key encryption (part b); this is explained later. The public-key approach has two advantages: it provides a digital signature as well as message authentication; and it does not require the distribution of keys to communicating parties. These two approaches have an advantage over approaches that encrypt the entire message in that less computation is required. Nevertheless, there has been interest in developing a technique that avoids encryption altogether. Part c shows a technique that uses a hash function but no encryption for message authentication. This technique assumes that two communicating parties, say A and B, share a common secret value SAB. When A has a message to send to B, it calculates the hash function over the concatenation of the secret value and the message: MDM = H(SAB||M). It then sends [M||MDM] to B. Because B possesses SAB, it can recompute H(SAB||M) and verify MDM. Because the secret value itself is not sent, it is not possible for an attacker to modify an intercepted message. As long as the secret value remains secret, it is also not possible for an attacker to generate a false message.

雜湊函數特性 Applied to any size data H produces a fixed-length output. H(x) is relatively easy to compute for any given x One-way property computationally infeasible to find x such that H(x) = h Collision resistance computationally infeasible to find y ≠ x such that H(y) = H(x)

作業 寫一份報告關於3-DES 作業寄到 ekaiping@hotmail.com Deadline 8/4