CS 6903 - Applied Cryptography Lecture 10: Lecture 10, slides 3-15
Speaker: Giovanni Di Crescenzo, Scribe: Chaitanya Bhorade December 13, 2014

Summary:
This document contains notes for Lecture 10, slides 3-15. These are the lecture notes with some additional information by the scribe, for Lecture 10 Slides 3- 15. The primary focus is on Digital Signatures and its constructions. Properties of a digital signature is then discussed. This is followed by some Digital Signature schemes. And finally Digital Signatures in practice are shown to conclude the notes.

1

Introduction

Digital Signatures is a concept derived form a normal signature which is used to confirm the origin of a received document. Asymmetric cryptographic technique is been implemented to ensure whether the received document is authenticated or not. With some factors, a digital signature offers more security than a real-life signature. Because it is difficult to convert a digital signature for message m which can be used as a sign a new message m’ A digital signature for a document would be bits which are derived from: the document and the secret key of the signer.The public key is available freely to anyone who wants to verify the signature. Whereas the other key, which is a secret key, is only known to the one that is authorized to generate the signatures which are associated with that public key.

2

Properties of Digital Signature
• Integrity: Recipients can be confident that the message has not been accidentally modified. 1

• Authentication: Recipients can be confident that a message is originated from the sender. • Publicly Verifiable: Along with the recipient, anyone who has a public key provided by the signer, can verify the signature validity. • Non-repudiation: The signer cannot deny having signed a message. • Non-repudiation: A signed document with any recipient can be transferred to anyone, who in turn can verify the original senders signature.

2.1

Additional properties of a Digital Signature

A signature cannot be used to validate any different document as a digital signature depends on that specific signed document. Someone who has a secret information can only create a signature. A documents signature can be validated without knowing the secret information used to create the digital signature. A signature wont be valid, when a document is produced that differs from an original document by one bit.

3

Example of Validating Data Integrity

Figure 1: Digital Signature Scheme used to validate data Integrity. The above figure 1 shows two items transferred to the recipient of some signed data (original data and the digital signature). The digital signature 2

would be the one way hash of the data which is encrypted with the signers private key. In order to validate the integrity of the data, the receiving side would use the public key to decrypt the hash. It then uses the same hashing algorithm which was used to generate a hash of the original data. Finally both the hashes are compared. If they do not match, then the data has been changed or the public key used for the second hash is faulty or doesnt have any relation with the original signed document. Basically Signer or sender uses public key and the secret key to compute a digital signature of the message, and the receiver or in digital signatures case, anyone who wants to verify validity uses the public key. Signer decides to reveal the public key upfront.

4

Syntax in signature scheme
• A digital signature scheme consists of three algorithms (G,S,V) such that: The key generation algorithm G is a randomized algorithm that returns a public key PK and a secret key SK, we can write it as R (P K, SK) ←− G(1n ). − • The signing algorithm S is a (possibly) randomized algorithm that takes the secret key SK and a message m and outputs a signature σ; we write R σ ←− SSK (m). − • The verification algorithm V is a deterministic algorithm that takes the public key PK, a message m, and a signature σ, and outputs VP K (m, σ) ∈ accept, reject.

We require VP K (m, SSK (m)) = accept for all (P K, SK) ←− G(1n ) and − m ∈ {0, 1}∗ .

R

Figure 2: Syntax of Digital Signature Scheme. Above figure 2 is a diagrammatic representation of the syntax of a digital signature scheme.

3

4.1

Digital Signatures: correctness and security

A. Correctness: • Vrfy would always output 1 on inputs returned by KG and Sign. B. Security: • Existential unforgeability under adaptive chosen message attack :A signature scheme (G,S,V) is secure if for every PPT A, there is a negligible function such that P r[ASSK (.) (P K)f orges] ≤ (k)
R

∀k,

where the probability is taken over (P K, SK) ←− G(1k ) and the − coin tosses of A.“Af orges” ≡ A produces a pair (m, σ) for which (a)VP K (m, σ) = accept, and (b) m is different from all of A’s queries to the SSK − oracle.

5
5.1

Digital Signature Schemes
Textbook and Hashed RSA Schemes

Correctness holds in Textbook RSA scheme as e ∗ d = 1 mod φ(n) which implies that se mod n = (med ) mod n = m1 mod n = m. Textbook RSA scheme violates existential unforgeability without a chosen message attack and also violates universal unforgeability using a chosen message attack. Hashed RSA scheme is used by replacing m with H(m), for a collisionintractable function H. Because of which Textbook RSA scheme attacks do not work.

5.2

Lamports scheme (for 1/n-bit messages)

Theorem: If one-way functions exist, this is a one-time digital signature scheme for 1-bit messages. Proof: Assume this is not a one-time signature scheme; then there exists an adversary A that queries signing oracle with bit m, thus obtaining signature s, and then returns pair (m’,s’) such that m’=m and s’ is a valid signature of 4

m’ with some not negligible probability. Note that because m’=m, s’ satisfies f(s’)=y(1-m). This can be used to invert f with the same probability using a proof by reduction. Theorem: If one-way functions exist, this is a one-time signature scheme for n-bit messages. Proof: Assume that this is not a one-time signature scheme; then there exists an efficient adversary A that makes 1 query m to the signing oracle, thus obtaining signature s, and then returns a pair (m’,s’) such that m’=m and s’ is a valid signature of m’ with some not negligible probability

5.3

The Hash and Sign paradigm

Theorem: If H is a collision-intractable hash function and (KG,Sign,Vrfy) is a signature scheme for fixed-length messages, then (KG’,Sign’,Vrfy’) is a signature scheme for arbitrary-length messages. Proof: A forgery must involve either a forgery of the scheme for fixed-length messages or finding a collision in H.

5.4

El Gamal digital signature schemes

It is based on the difficulty of computing Discrete Logarithms and a collisionintractable hash function H. Here, an attacker can forge signatures by finding the secret key.

5.5

The DSA digital signature schemes

In 1991, NIST proposed DSA for use in their Digital Signature Standard (DSS). It was adopted in 1994. There were several criticisms against DSA: DSA is slower than RSA. RSA is the de facto standard. The DSA selection process was not public. DSA cannot be used for encryption or key distribution. DSA was developed by the NSA, and there may be a trapdoor in the algorithm.

5

The key size (512 bits) is too small. In response to this criticism, NIST made the key size variable, from 512 to 1024 bits.

6
6.1

Digital Signatures in Practice
Hash-then-sign with plain RSA

PK =(N, e), SK =(N, d) s.t. e*d ≡1 (mod φ(N)). SSK (m)=(H(m))d mod N where H is SHA-1 or MD5. Intuition: adversary has “no control” over H(m), so cannot forge by choosing signature first, or by exploiting special inputs on which RSA is easy to invert. RSA PKCS 1: H(m) = 001FF FF00.. SHA-1(m).

∗ No justification. ∗ Doesn’t seem related to one-wayness of RSA since H(m) is always of very special form.

6.2

El Gamal signatures

PK = (p, g, x), SK = (p, g, x) where x = g x mod p. ˆ ˆ SSK (m): 1. Choose y←− Zp−1 ; let y = g y mod p. − ˆ m xˆ y 2. Find s.s.t. g ≡ g . y s (mod p). ˆ 3. Output σ = (ˆ, s). y How does the signer compute s? We have m≡ xˆ + ys (mod (p-1)) and y the signer knows X, y, y ,m so he can compute (m − xˆ)y −1 modulo (p-1). ˆ y y VP K (m, (y, s)) : Check that g m ≡ g xˆ . y s (mod p). ˆ R

Not secure! (Similar attacks as plain trapdoor functions.) Digital Signature Standard (1991, NIST+NSA): hash-then-sign, using SHA1 and DSA (variant of El Gamal).

6

References: • https : //access.redhat.com/documentation • http : //www.mccurley.org • http : //en.wikipedia.org/wiki/Digitals ignature • seas.harvard.edu

7