Transcript Cryptographic Security

Cryptographic Security
Aveek Chakraborty
CS5204 – Operating Systems
1
Cryptographic Security
Goals of Cryptography
 The most basic problem : ensure security of communication over in-secure medium
 Security Goals:
- privacy (secrecy, confidentiality)
only the intended recipient can see the communication
- authenticity (integrity)
the communication is generated by the intended sender
information is not altered or destroyed
- non-repudiation
party in a dispute cannot repudiate, or refute the validity of a statement
CS 5204 – Operating Systems
2
Cryptographic Security
Basic terminology in Cryptography








Plaintexts
Cipher texts
Keys
Encryption
Decryption
Cryptography
Cryptanalysis
Cryptology
Cryptographic Security
Cryptography
CA
public information
M
E
Encryption key
Ke
M’
C
D
Kd
M
Decryption key
Forms of attack:
ciphertextonly
knownplaintext
chosenplaintext
CS 5204 – Operating Systems
4
Cryptographic Security
Forms of Cryptosystems







Secret-key cryptography (a.k.a. symmetric cryptography)
– encryption & decryption use the same key
– key must be kept secret
– key distribution is very difficult
Public-key cryptography (a.k.a. asymmetric
cryptography)
– encryption key different from decryption key
– cannot derive decryption key from encryption key
Cryptographic Security
Combining Public/Private Key Systems
Public key encryption is more expensive than symmetric key encryption
For efficiency, combine the two approaches
(1)
A
B
(2)
(1) Use public key encryption for authentication; once authenticated,
transfer a shared secret symmetric key
(2) Use symmetric key for encrypting subsequent data transmissions
CS 5204 – Operating Systems
6
Cryptographic Security
Secure Communication - Public Key System
M
M
Alice
Ebob(M)
Dbob(C)
C
Bob
?
Ebob is the public key for Bob
Dbob is the private key for Bob
CS 5204 – Operating Systems
Eve
7
Cryptographic Security
RivestShamirAdelman (RSA) Method
M
M
Alice
Me mod n
C
Cd mod n
(e, n)
Bob
(d, n)
Encryption Key for Bob
Decryption Key for Bob
CS 5204 – Operating Systems
8
Cryptographic Security
RSA Method
1. Choose two large (100 digit) prime numbers, p and q, and set n = p x q
2. Choose any large integer, d, so that: GCD( d, ((p1)x(q1)) = 1
3. Find e so that: e x d = 1 (modulo (p1)x(q1))
Example:
1. p = 5, q = 11 and n = 55.
(p1)x(q1) = 4 x 10 = 40
2. A valid d is 23 since GCD(40, 23) = 1
3. Then e = 7 since:
23 x 7 = 161 modulo 40 = 1
CS 5204 – Operating Systems
9
Cryptographic Security
Encryption and Decryption using RSA method

Encryption
- Alice does the following:i) Obtains Bob’s public key (e, n).
ii) Represents the plaintext message as a positive integer m.
iii) Computes the ciphertext c = m^e mod n.
iv) Sends the ciphertext c to Bob.

Decryption
- Bob does the following:i) Uses his private key (d, n) to compute m = c^d mod n.
ii) Extracts the plaintext from the message representative m.
Cryptographic Security
(Large) Document Integrity
Digest properties:
File/
message
hash process
• fixed-length, condensation of the source
• efficient to compute
• irreversible - computationally infeasible for the
original source to be reconstructed from the digest
• unique - difficult to find two different sources that
map to the same digest (collision resistance)
Also know as: fingerprint
Examples: MD5 (128 bits), SHA-1 (160 bits)
digest
CS 5204 – Operating Systems
11
Cryptographic Security
(Large) Document Integrity
 Note that small differences in the input result in very
different digests
CS 5204 – Operating Systems
12
Cryptographic Security
Guaranteeing Integrity
digital envelope
file
file
hash process
decrypt with
sender’s public key
compare
digest
CS 5204 – Operating Systems
digest
13
Cryptographic Security
Digital Signatures (Public Key)
Requirements:
cannot be forged and unique
receiver: knows that a message came from the sender (authenticity)
sender: cannot deny authorship( non-repudiation)
message integrity
sender & receiver: message contents preserved (integrity)
(e.g., cannot cutandpaste a signature into a message)
Public Key System:
sender, Alice: (EAlice : public, DAlice : private)
receiver, Bob: (EBob : public, DBob : private)
sender(Alice) C= EBob (DAlice (M)) > receiver(Bob)
receiver(Bob) M = EAlice (DBob (C)) > M
CS 5204 – Operating Systems
14
Cryptographic Security
Digital Signature using RSA Method

Digital Signing
Bob does the following:i) Creates a message digest of the information to be sent.
ii) Represents this digest as an integer m between 0 and n-1.
iii) Uses her private key (d, n) to compute the signature s = m^d mod n.
iv) Sends this signature s to Bob.

Signature verification:Alice does the following:i) Uses Bob’s public key (e, n) to compute integer v = s^e mod n.
ii) Extracts the message digest from this integer.
iii) Independently computes the message digest of the information that
has been signed.
iv) If both message digests are identical, the signature is valid.
Cryptographic Security
Secure Communication (Public Key)

Handshaking
EPKB, (IA, A)
EPKA (IA, IB)
B
A
EPKB (IB)
IA, IB are “nonces”
nonces can be included in each subsequent message
PKB: public key of B; PKA: public key of A;