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

- It must be computationally easy to encipher or decipher a message given the appropriate key;
- It must be computationally infeasible to derive the private key from the public key;
- 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.

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.

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:

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
^{17 }mod 77 = 28 - 04
^{17}mod 77 = 16 - 11
^{17}mod 77 = 44 - 11
^{17}mod 77 = 44 - 14
^{17 }mod 77 = 42

Bob sends 28 16 44 44 42.

Alice receives 28 16 44 44 42

Alice uses private key,* d* = 53, to decrypt message:

- 28
^{53}mod 77 = 07 - 16
^{53}mod 77 = 04 - 44
^{53}mod 77 = 11 - 44
^{53}mod 77 = 11 - 42
^{53}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.

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
^{53}mod 77 = 35 - 04
^{53}mod 77 = 09 - 11
^{53}mod 77 = 44 - 11
^{53}mod 77 = 44 - 14
^{53}mod 77 = 49

Alice sends 35 09 44 44 49.

Bob receives 35 09 44 44 49

Bob uses Alice’s public key, *e = 17*, *n = 77*, to decrypt message:

- 35
^{17}mod 77 = 07 - 09
^{17}mod 77 = 04 - 44
^{17}mod 77 = 11 - 44
^{17}mod 77 = 11 - 49
^{17}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.

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
^{53}mod 77)37 mod 77 = 07 - (04
^{53}mod 77)37 mod 77 = 37 - (11
^{53}mod 77)37 mod 77 = 44 - (11
^{53}mod 77)37 mod 77 = 44 - (14
^{53}mod 77)37 mod 77 = 14

Alice sends 07 37 44 44 14.

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.

Confidentiality

Integrity

Authenticity

Non-repudiation

Confidentiality

- Eavesdropping

Integrity

- Modification of data, viruses

Authenticity

- “Spoofing”

Availability

- “SYN flooding”

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.

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

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…

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.

** 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 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…

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.

*1*. Course Introduction: Security basic concepts

*2*. Access Control models: Authentication and authorization mechanisms

*6*. Role Based Access Control standard (v3)

*7*. XACML: extensible Access Control Markup Language

*8*. Authentication Protocols in distributed system

*10*. Java Authentication and Authorization Service (JAAS)

*11*. Network security

*12*. Network security, security protocols: PGP, SSL

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