Digital Signatures:
Mathematics
Zdeněk Říha

Data authentication
lData integrity + data origin
lDigital signature
lAsymmetric cryptography
lpublic and private key
l

Kerckhoffs' principle
lA cryptosystem should be secure even if everything about the system, except the key, is public
knowledge.
l
lI.e. only the key should be kept secret, not the algorithm.
l

Signature
 algorithm
Verification
algorithm
message
signed
message
Alice
Public key of Alice
Bob
Source: Network and
Internetwork Security (Stallings)
Digital signature scheme
verified
message
Private key of Alice

Digital signature – keys
lTwo keys per subject:
lPrivate key for signature generation;
lPublic key for signature verification.
lCorrect signatures can be generated only by those having the private key…
lTo verify the signature we need the public key of the signed subject.
lThe digital signature itself does not give any guarantees with respect to signing time.

Digital signature – algorithms
lFirst asymmetric cryptography algorithms appeared at the beginning of 1970s:
lBritish GCHQ (Clifford Cocks).
lPublic announcement in 1997.
lApplication of the asymmetric algorithms for authentication - signature “invented” later by the
academic community for their algorithms.
lFirst public algorithms at the end of 1970s (W. Diffie and M. Hellman influenced by R. Merkle).
lThe famous algorithm RSA (Rivest, Shamir, Adelman) published in 1977, patented in 1983 (patent has
already expired).
lDescribed in PKCS#1

Digital Signature Algorithm (DSA)
lProposed in 1991 by NIST
lIn 1994 the selection procedure for Digital Signature Standard (DSS) was concluded – DSA (Digital
Signature Algorithm) was selected.
lModified version of ElGamal algorithm, based on discrete logarithm in Zp.
lBecame FIPS standard FIPS 186 in 1993.
lSlightly modified in 1996 as FIPS 186-1.
lExtended in 2000 as FIPS 186-2.
lUpdated in 2009 as FIPS 186-3 (new key sizes).
l
lNow NIST FIPS 186-3 supports RSA & DSA & ECDSA.

Elliptic curve DSA (ECDSA)
lElliptic curves invented by Koblitz & Miller in 1985.
lECDSA proposed in 1992 by Vanstone
lBecame ISO standard (ISO 14888-3) in 1998
lBecame ANSI standard (ANSI X9.62) in 1999
l
lECDSA is a version of DSA based on elliptic curves.

RSA: mathematics
lPrime multiplication is simple & Factorization of integers is computationally intensive.
lWe choose randomly 2 primes and compute n and φ(n) :
lp, q
ln = p·q
lφ(n) = (p-1)(q-1).
l e is chosen such that gcd(e, φ(n)) = 1.
lWe compute d = e-1 (mod φ(n)).
lPublic key: n, e.
Private parameters: p, q, d.
Private key: d.
lDigital signature generation (decryption): s = md mod n
lSignature verification (encryption): m = se mod n.
l
lFor RSA with 1024 bit n, the signature will be 1024 bit long.

RSA: example
lIntentionally small numbers (such cryptosystem is not secure).
l
lWe generate parameters:
lp = 7927, q = 6997,
ln = pq = 55465219,
lφ(n) = 7926 ´ 6996 = 55450296.
lPublic exponent is selected e = 5, equation is solved
ed = 5d = 1 (mod 55450296) to have  d = 44360237.
lThe public key: (n = 55465219, e = 5),
The private key: d = 44360237.
lDigital signature generation:
lMessage m = 31229978
lSignature s = 3122997844360237 mod 55465219 = 30729435.
lSignature verification:
lMessage should be m = 307294355 mod 55465219 = 31229978.

RSA in practice: Padding
lm(M) = 6b bb … bb ba || Hash(M) || 3x cc
l where x = 3 for SHA-1, 1 for RIPEMD-160
lANSI X9.31
l
lm(M) = 00 01 ff … ff 00 || HashAlgID || Hash(M)
lPKCS #1 v1.5
l
lm(M) = 00 || H  || G(H) Å [salt || 00 … 00]
l where H = Hash(salt, M), salt is random, and G is a mask generation function
lProbabilistic Signature Scheme (PSS)

RSA Padding example (PKCS#1 v1.5)
lDocument
l“00 01 02 03 04 05 06 07 07 06 05 04 03 02 01”
lHash of the document (sha-1)
l“b3 39 90 4c d2 a0 10 e6 19 37 eb e5 b5 83 37 8c 5d 10 51 95”
lPadded hash to be signed
l“00 01 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 00 30 21 30
09 06 05 2b 0e 03 02 1a 05 00 04 14 b3 39 90 4c d2 a0 10 e6 19 37 eb e5 b5 83 37 8c 5d 10 51 95”

DSA: mathematics
lKey generation – domain parameters
lDecide on a key length L and N, e.g. (1024,160).
lN must be less than or equal to the hash output length
lChoose an N-bit prime q. [“order of g w.r.t p”]
lChoose an L-bit prime modulus p such that p–1 is a multiple of q.
lChoose g, a number whose multiplicative order modulo p is q, e.g. g = h(p–1)/q mod p for some
arbitrary h (1 < h < p-1). [“generator”]
lDomain parameters (p, q, g) may be shared between different users of the DSA system.
l

DSA: mathematics II
lKey generation
lChoose random x, such that 0 < x < q.
lCalculate y = gx mod p.
lPrivate key: x.
lPublic key: y & (p, q, g).

DSA: mathematics III
lSignature generation
lGenerate a random per-message value k such that 0 < k < q.
lCalculate r = (gk mod p) mod q
lCalculate s = (k−1(H(m) + x*r)) mod q
lThe signature is (r, s).
lSignature verification
lw = (s)−1 mod q
lu1 = (H(m)*w) mod q
lu2 = (r*w) mod q
lv = ((gu1*yu2) mod p) mod q
lThe signature is valid if v = r
lFor DSA (1024,160) the signature size will be 2x160 bits.

DSA: Padding
lDecide on lengths L and N, e.g. (1024,160).
lN must be less than or equal to the hash output length
lE.g. for (1024,160) sha-1 is typically used,
sha-256 would be ok as well and only first 160 bits would be used
ls = (k−1(H(m) + x*r)) mod q
l“It is recommended that the security strength of the (L, N) pair and the security strength of the
hash function used for the generation of digital signatures be the same unless an agreement has
been made between participating entities to use a stronger hash function. When the length of the
output of the hash function is greater than N (i.e., the bit length of q), then the leftmost N bits
of the hash function output block shall be used in any calculation using the hash function output
during the generation or verification of a digital signature. A hash function that provides a lower
security strength than the (L, N) pair ordinarily should not be used, since this would reduce the
security strength of the digital signature process to a level no greater than that provided by the
hash function.” [FIPS 186-3]
l

ECDSA: Elliptic curves
lElliptic curve
lPoints satisfying equation
ly2 = x3 + ax +b
lAnd a point in infinity (∞)
lSet of points & operations form an Abelian group
lIn ECC (elliptic curve cryptography) elliptic curves over finite fields are used
lPrime fields: Fp , p prime
lExtension fields of characteristics 2:  F2m
lFinding the discrete logarithm of a random elliptic curve element with respect to a publicly-known
base point is infeasible.

ECDSA: Elliptic curve domain parameters
l (field,a,b,G,n,h)
lFinite field
lp for Fp
lm, bases (trinomial, pentanomial) for F2m
lCoefficients a, b: y2 = x3 + ax +b
lGroup generator: G
lOrder of the G: n
lOptional cofactor: h
l(h = number of elements in field / order n)
lThe base point G generates a cyclic subgroup of order n in the field.

ECDSA: Keys
lGenerating key pair
lSelect a random integer d from [1,n − 1]
lCompute P = d*G;
lPrivate key: d
lPublic key: P
l
lFor 256-bit curve
lthe private key d will be approx. 256-bit long
lthe public key P is a point on the curve – will be approx 512-bit long
l

ECDSA: Signatures
lGenerate signature
lSelect a random integer k from [1,n − 1]
l(x1,y1) = k*G
lCalculate r = x1 (mod n)
lCalculate s = k−1(M + r*d) (mod n)
lSignature is (r,s).
lSignature verification
lCalculate w = s−1 (mod n)
lCalculate u1 = z*w (mod n) & u2 = r*w (mod n)
lCalculate (x1,y1) = u1*G + u2*P
lThe signature is valid if r = x1 (mod n).
lFor 256-bit curve the signature length will be approx. 512 bits

ECDSA: Padding
lRules are same as for DSA
l“It is recommended that the security strength associated with the bit length of n and the security
strength of the hash function be the same unless an agreement has been made between participating
entities to use a stronger hash function. When the length of the output of the hash function is
greater than the bit length of n, then the leftmost n bits of the hash function output block shall
be used in any calculation using the hash function output during the generation or verification of
a digital signature. A hash function that provides a lower security strength than the security
strength associated with the bit length of n ordinarily should not be used, since this would reduce
the security strength of the digital signature process to a level no greater than that provided by
the hash function.” [FIPS 186-3]

Hash function
lCryptographic hash function
lInput of arbitrary size
lOutput of fixed size: n bits (e.g. 256 bits).
lFunction is not injective (there are collisions).
lHash is a compact representative of input (also called imprint, (digital) fingerprint or message
digest).
lHash functions often used to protect integrity. First the has is computed and then only the has is
protected (e.g. digitally signed).

Hash function properties
lOne-way property
lIt is easy to calculate h(x) for arbitraty x.
lIn a reasonable time it is not possible for the fixed y to find x, such that h(x) = y.
lCollision resistance
l(weak): In a reasonable time it is not possible for a given x to find x’ (x ≠ x’) such that  h(x)
= h(x’).
l(strong): In a reasonable time it is not possible to find any x, x’ such that h(x) = h(x’).
l

Cryptographic hash functions
lMD4: output 128 bits
lnot used anymore, serious weaknesses found.
lMD5: output 128 bits
lStill used although not considered secure at all
lBroken: efficient algorithm for finding collisions available
l128-bit output not considered secure enough
lSHA-1 (Secure Hash Algorithm): output 160 bits
lNIST standard, used in DSS (Digital Signature Standard)
lNot recommended for longer term use.

Cryptographic hash functions
lRIPEMD
lOutput : 128, 160, 256 or 320 bits
lLess frequently used
lWhirlpool
lOutput: 512 bits
lBased on AES
lRecommended by NESSIE project
lStandardized by ISO

Cryptographic hash functions
lSHA-2
lSHA-256, SHA-384, SHA-512, SHA-224
lDefined in FIPS 180-2
lRecommended hash functions
lSHA-3
lSelection of the future standard hash function is currently in progress
lWinner expected in 2012
l

Hash functions - examples
lMD5
lInput: „Autentizace“.
lOutput: 2445b187f4224583037888511d5411c7 .
lOutput 128 bits, written in hexadecimal notation.
lInput: „Cutentizace“.
lOutput: cd99abbba3306584e90270bf015b36a7.
lA single bit changed in input → big change in output,
so called “Avalanche effect”
lSHA-1
lInput: „Autentizace“.
lOutput: 647315cd2a6c953cf5c29d36e0ad14e395ed1776
lSHA-256
lInput: „Autentizace“.
lOutput: a2eb4bc98a5f71a4db02ed4aed7f12c4ead1e7c98323fda8ecbb69282e4df584