Valentina Casola » 4.Asymmetric Cryptography

Public Key Cryptography

Two keys

• Private key known only to the owner;
• Public key available to anyone:
  • ePublic key, private key inverses.

Idea

• Confidentiality: encipher using public key, decipher using private key;
• Integrity/authentication: encipher using private key, decipher using public one.

Requirements

1. It must be computationally easy to encipher or decipher a message given the appropriate key;
2. It must be computationally infeasible to derive the private key from the public key;
3. It must be computationally infeasible to determine the private key from a chosen plaintext attack.

Exponentiation cipher

Relies on the difficulty of determining the number of numbers relatively prime to a large integer n.

Background

Totient function Φ(n)

• Number of positive integers less than n and relatively prime to:
  • Relatively prime means with no factors in common with n.

Example: φ(10) = 4

• 1, 3, 7, 9 are relatively prime to 10.

Example: Φ(21) = 12

• 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20 are relatively prime to 21.

Algorithm

Choose two large prime numbers p, q

• Let n = pq; then φ(n) = (p–1)(q–1)
• Choose e < n such that e is relatively prime to φ(n)
• Compute d such that ed mod φ(n) = 1

Public key: (e, n); private key: d
Encipher: c = m^e mod n
Decipher: m = c^d mod n

Example: Confidentiality

Take p = 7, q = 11, so n = 77 and φ(n) = 60
Alice chooses e = 17, making d = 53
Bob wants to send Alice secret message HELLO (07 04 11 11 14)

• 07¹⁷ mod 77 = 28
• 04¹⁷ mod 77 = 16
• 11¹⁷ mod 77 = 44
• 11¹⁷ mod 77 = 44
• 14¹⁷ mod 77 = 42

Bob sends 28 16 44 44 42.

Example

Alice receives 28 16 44 44 42
Alice uses private key, d = 53, to decrypt message:

• 28⁵³ mod 77 = 07
• 16⁵³ mod 77 = 04
• 44⁵³ mod 77 = 11
• 44⁵³ mod 77 = 11
• 42⁵³ mod 77 = 14

Alice translates message to letters to read HELLO.
No one else could read it, as only Alice knows her private key and that is needed for decryption.

Example: Integrity/Authentication

Take p = 7, q = 11, so n = 77 and φ(n) = 60
Alice chooses e = 17, making d = 53
Alice wants to send Bob message HELLO (07 04 11 11 14) so Bob knows it is what Alice sent (no changes in transit, and authenticated)

• 07⁵³ mod 77 = 35
• 04⁵³ mod 77 = 09
• 11⁵³ mod 77 = 44
• 11⁵³ mod 77 = 44
• 14⁵³ mod 77 = 49

Alice sends 35 09 44 44 49.

Example

Bob receives 35 09 44 44 49
Bob uses Alice’s public key, e = 17, n = 77, to decrypt message:

• 35¹⁷ mod 77 = 07
• 09¹⁷ mod 77 = 04
• 44¹⁷ mod 77 = 11
• 44¹⁷ mod 77 = 11
• 49¹⁷ mod 77 = 14

Bob translates message to letters to read HELLO

• Alice sent it as only she knows her private key, so no one else could have enciphered it;
• If (enciphered) message’s blocks (letters) altered in transit, would not decrypt properly.

Example (cont’d)

Example: Both

Alice wants to send Bob message HELLO both enciphered and authenticated (integrity-checked)
Alice’s keys: public (17, 77); private: 53
Bob’s keys: public: (37, 77); private: 13
Alice enciphers HELLO (07 04 11 11 14):

• (07⁵³ mod 77)37 mod 77 = 07
• (04⁵³ mod 77)37 mod 77 = 37
• (11⁵³ mod 77)37 mod 77 = 44
• (11⁵³ mod 77)37 mod 77 = 44
• (14⁵³ mod 77)37 mod 77 = 14

Alice sends 07 37 44 44 14.

Common Uses of Public-Key Cryptography

Secure E-mail and other communications

• Secure electronic communications between individuals
• S/MIME standard
• Lotus Notes, Entrust, PGP

Secure WWW transactions

• Consumer-merchant purchases
• On-line banking
• SSL, S-HTTP, SET
• OFX, Integrion

Business-to-business transactions

• Electronic Data Interchange
• Electronic Trading

Other e-commerce solutions.

Requirements for commercial applications

Confidentiality
Integrity
Authenticity
Non-repudiation

Traditional paper-based solutions

Electronic Threats

Confidentiality

• Eavesdropping

Integrity

• Modification of data, viruses

Authenticity

• “Spoofing”

Availability

• “SYN flooding”

Electronic Solutions

Note on integrity and secrecy

Integrity: attacker cannot tamper with message.
Encryption may not guarantee integrity!
Intuition: attacker may able to modify message under encryption without learning what it is.
Given one-time key K, be encrypt M as MK… Perfect secrecy, but can easily change M under encryption to MM’ for any M’.
“RSA encryption is intended primarily to provide confidentiality… It is not intended to provide integrity”.
Some encryption schemes provide secrecy AND integrity.

Integrity

Software manufacturer wants to ensure that the executable file is received by users without modification…

Sends out the file to users and publishes its hash in NY Times.

The goal is integrity, not secrecy.

Idea: given goodFile and hash(goodFile), very hard to find badFile such that hash(goodFile)=hash(badFile).

One way functions

Intuition: hash should be hard to invert

• Let h(x’)=y{0,1}n for a random x’

Given y, it should be hard to find any x such that h(x)=y

How much hard?

• Brute-force: try every possible x, see if h(x)=y;
• SHA-1 (common hash function) has 160-bit output;
• Suppose have hardware that’ll do 230 trials a pop, assuming 234 trials per second, can do 289 trials per year will take 271 years to invert SHA-1 on a random image.

Some hash functions

MD5

• 128-bit output;
• Designed by Ron Rivest, used very widely.

RIPEMD-160

• 160-bit variant of MD-5

SHA-1 (Secure Hash Algorithm)

• 160-bit output;
• US government (NIST) standard as of 1993-95;
• Also the hash algorithm for Digital Signature Standard (DSS).

Electronic and Digital Signatures

“Electronic Signature” and “Digital Signature” do not mean the same thing.

The term ”electronic signature” means an electronic sound, symbol, or process, attached to or logically associated with a contract or other record and executed or adopted by a person with the intent to sign the record.

(Electronic Signatures in Global and National Commerce Act, E-Sign)

Both are “electronic”, but Electronic Signature, as it is defined in US law, does not involve any cryptographic technique ensuring identity, integrity, etc…

Digital Signature

Type of Electronic Signature

• Combines one-way secure hash functions with public key cryptography;
• Hash function generates fixed length value;
• No two documents produce the same hash value;
• Secure Hash Algorithm 1 (SHA-1).

Characteristics:

• Data Integrity – hash value;
• Non-repudiation – encrypted with private key;
• Does NOT provide confidentiality.

Signature production

Signature validation