# 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 = me mod n
Decipher: m = cd 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)

• 0717 mod 77 = 28
• 0417 mod 77 = 16
• 1117 mod 77 = 44
• 1117 mod 77 = 44
• 1417 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:

• 2853 mod 77 = 07
• 1653 mod 77 = 04
• 4453 mod 77 = 11
• 4453 mod 77 = 11
• 4253 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)

• 0753 mod 77 = 35
• 0453 mod 77 = 09
• 1153 mod 77 = 44
• 1153 mod 77 = 44
• 1453 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:

• 3517 mod 77 = 07
• 0917 mod 77 = 04
• 4417 mod 77 = 11
• 4417 mod 77 = 11
• 4917 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: 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):

• (0753 mod 77)37 mod 77 = 07
• (0453 mod 77)37 mod 77 = 37
• (1153 mod 77)37 mod 77 = 44
• (1153 mod 77)37 mod 77 = 44
• (1453 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

• Electronic Data Interchange

Other e-commerce solutions.

Confidentiality
Integrity
Authenticity
Non-repudiation

### Electronic Threats

Confidentiality

• Eavesdropping

Integrity

• Modification of data, viruses

Authenticity

• “Spoofing”

Availability

• “SYN flooding”

### 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).

### Hash functions

H is a lossy compression function

• Collisions: h(x)=h(x) for some inputs x, x‘;
• Result of hashing should “look random” (make this precise later).

Cryptographic hash function needs a few properties…

### 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.

### I materiali di supporto della lezione

M. Bishop, Standards: DES and RSA, Cap. 9

T. Cormen et al, Mc Graw Hill, Teoria dei numeri: Introduzione agli algoritmi e strutture dati, Cap. 31

Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion

Fatal error: Call to undefined function federicaDebug() in /usr/local/apache/htdocs/html/footer.php on line 93