Basic Cryptography
Basic Cryptography
1
What is cryptography?
•
Cryptography is a mathematical method of
protecting information
–
Cryptography is part of, but not equal to,
security
–
Predated modern computing
•
In modern computing, crypto is used to
remediate deficiencies in the cyber space
.
2
Cryptographic Primitives
•
In this course, we do not study the math part
of crypto; rather, we use cryptography
primitives as
“
black boxes.
”
–
Need to understand the fundamental properties of
the crypto primitives
•
Four primitives:
–
Cryptographic hash
–
Symmetric encryption
–
Asymmetric encryption
–
Digital signatures
3
Using the crypto primitives
•
Build security protocols
–
e.g.
SSL/TLS
•
Build more complex security systems
using the primitives
–
e.g.
PKI
4
Cryptographic Hash
Hash function: H(m) = c
Variable-length messages, fixed-length checksum
Examples: MD5, SHA-1
Properties:
1.
Given m, easy to compute H(m)
2.
Given c, hard to find m
(preimage resistance)
3.
Given m, hard to find another m
’
s.t. H(m
’
) = H(m)
(second-preimage
resistance)
4.
Hard to find m and m
’
s.t. H(m) = H(m
’
)
(collision resistance)
5
Applications of Hash Function
•
Provides integrity guarantee
–
If the message content is changed, the hash
will
be different.
•
Hide information
–
Knowing the hash
does not
reveal the input
message.
•
N.B. Hash is NOT encryption!
6
A simple application
•
A
Commitment Scheme
–
We are having an online “sealed first-price
auction”
–
Everyone submits a bid in a chat-room
–
There is no trusted third party
–
Bids may be submitted at different times
•
Requirements:
–
The bids need to be secret before opening
–
The bids need to be binding after opening
–
Use cryptographic hash function to implement
such a scheme
7
Using Salt with Hash
•
A salt is a message that is typically
concatenated to the Hash function’s input.
–
Used to increase the input space of the hash
–
Increase the difficulty of brute-force attacks
8
c =enc(m,
K
)
m=dec(c,
K
)
Properties:
1. Given ciphertext, hard to infer plaintext
(ciphertext only attack)
2. Ciphertext and plaintext known, hard to infer key
(known-plaintext attack)
3. Access to encryption oracle, hard to infer key
(chosen-plaintext attack)
4. Access to decryption oracle, hard to infer key
(chosen-ciphertext attack)
Symmetric Encryption
(Secret-key Encryption)
Encryption and decryption use the same key
secret key
Examples: DES, AES
9
ciphertext
plaintext
The key management problem
•
Every pair of communicating parties need
to establish a shared key
•
Leads to keys for
N
parties
•
Typically requires a key-management/key
agreement scheme to be used in practice
10
Diffie-Hellman Key Agreement
(1976)
Alice
Bob
Asymmetric Encryption
(Public-key Encryption)
Encryption and decryption use two different keys:
c = enc(m, K
pub
)
m = dec(c, K
priv
)
Public key:
announce to
everyone
Private key:
known to the
owner only
Examples: RSA, El-Gamal
12
Every party has a pair of keys: <K
pub
, K
priv
>
It is hard to infer private key from the public key
Asymmetric Encryption
(Public-key Encryption)
Properties:
1.
Given ciphertext, hard to infer plaintext
(ciphertext only attack)
2.
Ciphertext and plaintext known, hard to infer
private key
(known-plaintext attack)
3. Encryption oracle given, hard to infer private key
(chosen-plaintext attack)
4. Decryption oracle given, hard to infer private key
(chosen-ciphertext attack)
13
By definition
of public-key
encryption
Using Public-key Crypto
•
Key generation
–
Creates the <public, private> key pair
–
Typically involves pseudo-random number
generation
•
Encryption using public-key crypto
–
Does not need to share keys
–
Does not need a secure channel to transmit
the public key
–
Much slower than symmetric-key encryption
14
Challenge: how to ensure the
correct public key is used?
Using Public Key to Establish a
Shared Secret
Alice
Bob
C=E(PK
B
, s)
s
PK
B
s=D(SK
B
, C)
Pick a random
secret s
Digital Signature
Based on public-key crypto.
Signing:
sig= Sign(m, K
priv
)
Verification:
Verify(sig, K
pub,
m) = True
Properties:
1.
Verification of the validity of a digital signature needs only
the public key.
2.
Only the owner of the corresponding private key can
produce a valid signature
Examples: RSA, DSA, El-Gamal
16
Applications of Digital Signature
•
Ensuring data authenticity
–
Sender signs the message, receiver verifies
the signature
•
Providing non-repudiation
–
Digital signature serves as proof that the
message is generated by the private-key
holder
17
Message Authentication Code
18
Hash with a shared key.
tag= MAC(m, K)
Properties:
1.
Only the holder of the key K can generate a valid MAC
tag.
Examples: HMAC
Exercise after class
•
Set up public-key based authentication
using SSH
•
Play with the various crypto primitives
using OpenSSL (
http://www.openssl.org/
)
–
The command-line tool documentation can be
found at
http://www.openssl.org/docs/apps/openssl.ht
ml
–
Openssl should be installed at most Unix
systems.
19
Cryptography is a mathematical method used to protect information in modern computing. This course covers cryptographic primitives such as hash functions, symmetric and asymmetric encryption, digital signatures, and their applications. Learn about the importance of cryptographic hash functions, using salts to enhance security, and practical applications like commitment schemes in online auctions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
What is cryptography? Cryptography is a mathematical method of protecting information Cryptography is part of, but not equal to, security Predated modern computing In modern computing, crypto is used to remediate deficiencies in the cyber space. 2
Cryptographic Primitives In this course, we do not study the math part of crypto; rather, we use cryptography primitives as black boxes. Need to understand the fundamental properties of the crypto primitives Four primitives: Cryptographic hash Symmetric encryption Asymmetric encryption Digital signatures 3
Using the crypto primitives Build security protocols e.g. SSL/TLS Build more complex security systems using the primitives e.g. PKI 4
Cryptographic Hash Hash function: H(m) = c Variable-length messages, fixed-length checksum Properties: 1. Given m, easy to compute H(m) 2. Given c, hard to find m (preimage resistance) 3. Given m, hard to find another m s.t. H(m ) = H(m) (second-preimage resistance) 4. Hard to find m and m s.t. H(m) = H(m ) (collision resistance) Examples: MD5, SHA-1 5
Applications of Hash Function Provides integrity guarantee If the message content is changed, the hash will be different. Hide information Knowing the hash does not reveal the input message. N.B. Hash is NOT encryption! 6
A simple application A Commitment Scheme We are having an online sealed first-price auction Everyone submits a bid in a chat-room There is no trusted third party Bids may be submitted at different times Requirements: The bids need to be secret before opening The bids need to be binding after opening Use cryptographic hash function to implement such a scheme 7
Using Salt with Hash A salt is a message that is typically concatenated to the Hash function s input. Used to increase the input space of the hash Increase the difficulty of brute-force attacks 8
Symmetric Encryption (Secret-key Encryption) c =enc(m, K) m=dec(c, K) ciphertext secret key plaintext Encryption and decryption use the same key Properties: 1. Given ciphertext, hard to infer plaintext (ciphertext only attack) 2. Ciphertext and plaintext known, hard to infer key (known-plaintext attack) 3. Access to encryption oracle, hard to infer key (chosen-plaintext attack) 4. Access to decryption oracle, hard to infer key (chosen-ciphertext attack) Examples: DES, AES 9
The key management problem Every pair of communicating parties need to establish a shared key Leads to keys for N parties Typically requires a key-management/key agreement scheme to be used in practice 10
Diffie-Hellman Key Agreement (1976) Bob Alice
Asymmetric Encryption (Public-key Encryption) Every party has a pair of keys: <Kpub , Kpriv> Public key: announce to everyone Private key: known to the owner only Encryption and decryption use two different keys: c = enc(m, Kpub) m = dec(c, Kpriv) It is hard to infer private key from the public key Examples: RSA, El-Gamal 12
Asymmetric Encryption (Public-key Encryption) Properties: By definition of public-key encryption 1.Given ciphertext, hard to infer plaintext (ciphertext only attack) 2.Ciphertext and plaintext known, hard to infer private key (known-plaintext attack) 3. Encryption oracle given, hard to infer private key (chosen-plaintext attack) 4. Decryption oracle given, hard to infer private key (chosen-ciphertext attack) 13
Using Public-key Crypto Key generation Creates the <public, private> key pair Typically involves pseudo-random number generation Encryption using public-key crypto Does not need to share keys Does not need a secure channel to transmit the public key Much slower than symmetric-key encryption Challenge: how to ensure the correct public key is used? 14
Using Public Key to Establish a Shared Secret PKB C=E(PKB , s) Alice Bob s=D(SKB, C) Pick a random secret s s
Digital Signature Based on public-key crypto. Signing: sig= Sign(m, Kpriv) Verification: Verify(sig, Kpub, m) = True Properties: 1. Verification of the validity of a digital signature needs only the public key. 2. Only the owner of the corresponding private key can produce a valid signature Examples: RSA, DSA, El-Gamal 16
Applications of Digital Signature Ensuring data authenticity Sender signs the message, receiver verifies the signature Providing non-repudiation Digital signature serves as proof that the message is generated by the private-key holder 17
Message Authentication Code Hash with a shared key. tag= MAC(m, K) Properties: 1. Only the holder of the key K can generate a valid MAC tag. Examples: HMAC 18
Exercise after class Set up public-key based authentication using SSH Play with the various crypto primitives using OpenSSL (http://www.openssl.org/) The command-line tool documentation can be found at http://www.openssl.org/docs/apps/openssl.ht ml Openssl should be installed at most Unix systems. 19
