复旦大学信息安全.pdf
复旦大学信息安全.pdf
信息安全（04） Introduction to Cryptography - Public Key Cryptography, RSA 1 LiJT Public Key Cryptography • Principles of Public-Key Cryptosystems • The RSA Algorithm 2 LiJT Review: Symmetric Cipher Model Bob Alice 3 LiJT Symmetric Cryptography • traditional symmetric/secret/single key cryptography uses one key • shared by both sender and receiver • if this key is disclosed communications are compromised • also is symmetric, parties are equal 4 LiJT Review: Symmetric Cipher Model Secure channel Bob Alice 5 LiJT Asymmetric Cipher Model • Every body have two keys – Public key —— 公开 – Private key —— 保密 Bob Alice 6 LiJT Asymmetric Cipher Model 公开 • Bob’s Public key Alice’s Public key • Bob’s Private key Alice’s Private key Bob Alice 7 LiJT Asymmetric Cipher Model 公开 • Bob’s Public key 保密 • Bob’s Private key Bob Alice’s Public key 保密 Alice’s Private key Alice 8 LiJT Asymmetric Cipher Model Bob Alice 9 LiJT Cryptography Catalog • The number of the keys used – Symmetric , single-key, secret-key, conventional encryption: Both sender and receiver use the same key – Asymmetric, two-key, or public-key encryption: the sender and receive each uses a different key 10 LiJT Public-Key Cryptography • probably most significant advance in the 3000 year history of cryptography • uses two keys – a public & a private key • asymmetric since parties are not equal • uses clever application of number theoretic concepts to function • complements rather than replaces private key crypto 11 LiJT History • public invention due to Whitfield Diffie & Martin Hellman at Stanford Uni in 1976 – known earlier in classified community. – note: now know that Williamson (UK CESG) secretly proposed the concept in 1970 • Diffie-Hellman Key Exchange 12 LiJT 公开密钥加密系统 一个公开密钥系统由六要素组成： 明文 公开和私有密钥 加密算法 密文 解密算法 LiJT 公开密钥加密 参与方B容易通过计算产生出一对密钥（公开密 钥KUb ，私有密钥KRb ） 发送方A很容易计算产生密文 接收方B通过计算解密密文 C EKUb (M ) M DKRb (C ) DKRb [ EKUb (M )] 敌对方即使知道公开密钥KUb ，要确定私有密钥 KRb 在计算上是不可行的 敌对方即使知道公开密钥KUb 和密文C，要确定 明文M在计算上是不可行的 密码对互相之间可以交换使用 M DKRb [ EKUb (M )] DKUb[ EKRb (M ) LiJT Public-Key Cryptography: The progress • developed to address two key issues: – key distribution – how to have secure communications in general without having to trust a KDC with your key – digital signatures – how to verify a message comes intact from the claimed sender (Authentication) • protect sender from receiver forging a message & claiming is sent by sender 15 LiJT Public-Key Cryptography: The progress 16 LiJT Public-Key Cryptography: The progress • public-key/two-key/asymmetric cryptography involves the use of two keys: – a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures – a private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures • is asymmetric because – those who encrypt messages or verify signatures cannot decrypt messages or create signatures 17 LiJT RSA Algorithm 1977年由MIT的Rivest, Shamir和Adleman 三人提出 是一个分组加密方法 目前被最广泛地采用 采用的单向函数是大素数相乘，相乘很容易，但因子 分解很困难 基于数论中的Fermat（小）定理实现 LiJT RSA Key Setup • each user generates a public/private key pair by: • selecting two large primes at random: p, q • computing their system modulus n=p.q – note ø(n)=(p-1)(q-1) • selecting at random the e where 1