Cryptography
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Cryptography as PDF for free.
More details
- Words: 987
- Pages:
Cryptography
Last Class
Security problems/issues Categories of security attacks “Conventional” (symmetric) cryptography
Some techniques used in cryptography Steganography Permutation (various types) Substitution
Mono-alphabetic Poly-alphabetic
Today
Issues with symmetric encryption Public-Key (asymmetric) encryption Algorithms lab solution
Symmetric Key Encryption Alice
Bob transmit key
Encrypt plaintext
Decrypt ciphertext
plaintext
Symmetric Key Encryption
Goal: confidentiality Issues/problems:
Key must be kept secret Key distribution technique is critical Many communicating pairs… in a network with 1000 nodes (communicating computers), may require more than half million keys
Based on permutation and substitution
Symmetric Key Risks
How are the keys distributed? Through mail? Stolen/copied in the mail?
If key is stolen/copied, all communications are (unknowingly) compromised
All participants must synchronize and get a new key
Asymmetric Encryption
Asymmetric Cryptosystem
aka Public-key cryptosystem
Uses 2 different keys: Public key – encryption Private key – decryption
Properties Based on mathematical functions (not permutation or substitution) Given crypto algorithm and encryption key, computationally infeasible to determine decryption key
Asymmetric Cryptosystem: Encryption/Decryption Alice Bob 1. transmit public key
1. Decrypt
plaintext
1. Encrypt
ciphertext
plaintext
Confidentiality
Alice has two keys (strings of letters) Public key that she freely shares with the world Private key that only she knows
Messages encrypted with Alice’s public key are only decipherable by Alice’s private key
Asymmetric Cryptosystem: Authentication Alice Bob 1. transmit public key
1. Encrypt
plaintext
1. Encrypt
ciphertext
plaintext
Authentication: Digital Signature
Alice can send message encrypted using her private key Bob can decode message using Alice’s public key Bob is assured message he reads was authored by Alice (digital signature)
Uses for Public-Key Cryptosystems
Encryption/decryption Digital signature Key exchange
Advantages of Asymmetric Public Key
No need to send keys to one another Third party cannot copy key while in transit One stolen key only compromises part of the communication
RSA Algorithm
Rivest, Shamir, Adleman (1977, MIT) Block cipher (plaintext encrypted in blocks) C = Me mod n M = Cd mod n (Me)d mod n
M mod n
Public key (e, n) Private key (d, n) n = p * q (p and q, private, chosen primes) d = e-1 mod φ (n)
RSA Example
Message M=4 Parameter values: p, q = 5, 7 (chosen primes) n = p * q = 35 (calculated) e=5 d = e-1 mod ((p-1)(q-1)) = 5
Encryption: C = 45 mod 35 = 9 Decryption: M = 95 mod 35 = 59049 mod 35 = 4
Is Public Key Crypto Secure?
A 128 bit key would be a number between 1 and 340,282,366,920,938,000,000,000,000,000,000,000,000 How many prime numbers are between 1 and this number?
approximately n / ln(n) which is about 2^128 / ln( 2^128 ) =
3,835,341,275,459,350,000,000,000,000,000,000,000
How long would it take to find all of these prime numbers if you could calculate one trillion of these numbers per second?
More than 121,617,874,031,562,000 years (i.e., about 10 million times longer than the universe has existed so far.)
Reference: http://www.livinginternet.com/?i/is_crypt_pkc_inv.htm
Answer – Yes, but know its limitations (e.g. plaintext attacks, block sizes, etc.)
Weakness of Public-key System
Man-in-the-middle Attack Communication of Alice’s public key is intercepted and changed to a new public key that matches interceptors private key Interceptor decodes the message to read it and re-encodes it using Alice’s public key before sending on to her
Trusted key distribution
Trusted Key Distribution
Companies exist to manage key distribution
Microsoft “offered” to do this with a system called Passport
Business model… Microsoft creates a standard for secure communication and sets prices at monopolist levels
Trusted Key Distribution
US Government Do you trust them? They are very interested in having the power to control keys so they can listen to any message
Trusted Key Distribution
RSA: Rivest, Shamir, Adelman Verisign PGP: Pretty Good Privacy
Breaking RSA
RSA inventors offered $100 reward for finding a plaintext sentence enciphered via RSA public key had 129 decimal digits ( ~ 428 bits) RSA predicted 40 quadrillion years was needed 1994 -- a group claimed the prize after 8 months of work (1600 computers used)
Security and the Web
HTTPS Uses port 443 (not 80) Security protocol is determined by your browser and the server Online vendors may establish contract with Verisign to handle security
A form of public-key encryption secures the transaction
Symmetric vs. Asymmetric 1.
2.
Needed to Work Same algorithm, 1. One algorithm, pair same key for of keys (one for encryption AND encryption, one for decryption decryption) Sender and receiver 2. Sender and receiver must share must have one set of algorithm and key matched par of keys (not the same one)
Symmetric vs. Asymmetric Needed for Security
1. 2.
3.
Key must be secret Must be impossible (or impractical) to decipher message with no other info Knowledge of algorithm + sample ciphertext will not allow determination of key
1.
2.
3.
One of the 2 keys must be kept secret Must be impossible to decipher message if no other info available Knowledge of algorithm, one of keys, sample ciphertext insufficient to determine other key
Symmetric vs. Asymmetric Computational Complexity
software encryption using DES (symmetric key algorithm) is 100 times faster than software encryption using RSA (asymmetric key algorithm) - estimate provided by RSA Data Securities hardware encryption using DES (symmetric key algorithm) is anywhere from 1,000 to 10,000 times faster than hardware encryption using RSA (asymmetric key algorithm)
Algorithms Lab Sample Solution
Start: End: Assumptions: Procedure:
Remember to be precise in the procedure! Goal is unambiguity of interpretation
Last Class
Security problems/issues Categories of security attacks “Conventional” (symmetric) cryptography
Some techniques used in cryptography Steganography Permutation (various types) Substitution
Mono-alphabetic Poly-alphabetic
Today
Issues with symmetric encryption Public-Key (asymmetric) encryption Algorithms lab solution
Symmetric Key Encryption Alice
Bob transmit key
Encrypt plaintext
Decrypt ciphertext
plaintext
Symmetric Key Encryption
Goal: confidentiality Issues/problems:
Key must be kept secret Key distribution technique is critical Many communicating pairs… in a network with 1000 nodes (communicating computers), may require more than half million keys
Based on permutation and substitution
Symmetric Key Risks
How are the keys distributed? Through mail? Stolen/copied in the mail?
If key is stolen/copied, all communications are (unknowingly) compromised
All participants must synchronize and get a new key
Asymmetric Encryption
Asymmetric Cryptosystem
aka Public-key cryptosystem
Uses 2 different keys: Public key – encryption Private key – decryption
Properties Based on mathematical functions (not permutation or substitution) Given crypto algorithm and encryption key, computationally infeasible to determine decryption key
Asymmetric Cryptosystem: Encryption/Decryption Alice Bob 1. transmit public key
1. Decrypt
plaintext
1. Encrypt
ciphertext
plaintext
Confidentiality
Alice has two keys (strings of letters) Public key that she freely shares with the world Private key that only she knows
Messages encrypted with Alice’s public key are only decipherable by Alice’s private key
Asymmetric Cryptosystem: Authentication Alice Bob 1. transmit public key
1. Encrypt
plaintext
1. Encrypt
ciphertext
plaintext
Authentication: Digital Signature
Alice can send message encrypted using her private key Bob can decode message using Alice’s public key Bob is assured message he reads was authored by Alice (digital signature)
Uses for Public-Key Cryptosystems
Encryption/decryption Digital signature Key exchange
Advantages of Asymmetric Public Key
No need to send keys to one another Third party cannot copy key while in transit One stolen key only compromises part of the communication
RSA Algorithm
Rivest, Shamir, Adleman (1977, MIT) Block cipher (plaintext encrypted in blocks) C = Me mod n M = Cd mod n (Me)d mod n
M mod n
Public key (e, n) Private key (d, n) n = p * q (p and q, private, chosen primes) d = e-1 mod φ (n)
RSA Example
Message M=4 Parameter values: p, q = 5, 7 (chosen primes) n = p * q = 35 (calculated) e=5 d = e-1 mod ((p-1)(q-1)) = 5
Encryption: C = 45 mod 35 = 9 Decryption: M = 95 mod 35 = 59049 mod 35 = 4
Is Public Key Crypto Secure?
A 128 bit key would be a number between 1 and 340,282,366,920,938,000,000,000,000,000,000,000,000 How many prime numbers are between 1 and this number?
approximately n / ln(n) which is about 2^128 / ln( 2^128 ) =
3,835,341,275,459,350,000,000,000,000,000,000,000
How long would it take to find all of these prime numbers if you could calculate one trillion of these numbers per second?
More than 121,617,874,031,562,000 years (i.e., about 10 million times longer than the universe has existed so far.)
Reference: http://www.livinginternet.com/?i/is_crypt_pkc_inv.htm
Answer – Yes, but know its limitations (e.g. plaintext attacks, block sizes, etc.)
Weakness of Public-key System
Man-in-the-middle Attack Communication of Alice’s public key is intercepted and changed to a new public key that matches interceptors private key Interceptor decodes the message to read it and re-encodes it using Alice’s public key before sending on to her
Trusted key distribution
Trusted Key Distribution
Companies exist to manage key distribution
Microsoft “offered” to do this with a system called Passport
Business model… Microsoft creates a standard for secure communication and sets prices at monopolist levels
Trusted Key Distribution
US Government Do you trust them? They are very interested in having the power to control keys so they can listen to any message
Trusted Key Distribution
RSA: Rivest, Shamir, Adelman Verisign PGP: Pretty Good Privacy
Breaking RSA
RSA inventors offered $100 reward for finding a plaintext sentence enciphered via RSA public key had 129 decimal digits ( ~ 428 bits) RSA predicted 40 quadrillion years was needed 1994 -- a group claimed the prize after 8 months of work (1600 computers used)
Security and the Web
HTTPS Uses port 443 (not 80) Security protocol is determined by your browser and the server Online vendors may establish contract with Verisign to handle security
A form of public-key encryption secures the transaction
Symmetric vs. Asymmetric 1.
2.
Needed to Work Same algorithm, 1. One algorithm, pair same key for of keys (one for encryption AND encryption, one for decryption decryption) Sender and receiver 2. Sender and receiver must share must have one set of algorithm and key matched par of keys (not the same one)
Symmetric vs. Asymmetric Needed for Security
1. 2.
3.
Key must be secret Must be impossible (or impractical) to decipher message with no other info Knowledge of algorithm + sample ciphertext will not allow determination of key
1.
2.
3.
One of the 2 keys must be kept secret Must be impossible to decipher message if no other info available Knowledge of algorithm, one of keys, sample ciphertext insufficient to determine other key
Symmetric vs. Asymmetric Computational Complexity
software encryption using DES (symmetric key algorithm) is 100 times faster than software encryption using RSA (asymmetric key algorithm) - estimate provided by RSA Data Securities hardware encryption using DES (symmetric key algorithm) is anywhere from 1,000 to 10,000 times faster than hardware encryption using RSA (asymmetric key algorithm)
Algorithms Lab Sample Solution
Start: End: Assumptions: Procedure:
Remember to be precise in the procedure! Goal is unambiguity of interpretation
Related Documents
Cryptography
November 2019 40
Cryptography
May 2020 19
Cryptography
May 2020 12
Cryptography
October 2019 30
Cryptography
June 2020 22