Having looked at hash functions, can now consider how to use them to create a digital signature, used to confirm message integrity (actaully integrity of the hash - but that should be good enough). With public key signatures, can also get non-repudiation of the origin.
S = M^{d}(mod R)
M = S^{e}(mod R) = M^{e.d}(mod R) = M(mod R)
RSA can be used both for encryption and digital signatures, simply by reversing the order in which the exponents are used: the secret exponent (d) to create the signature, the public exponent (e) for anyone to verify the signature. Everything else is identical.
Noting the obvious here that when both encrypting and authenticating (signing) that two public keys are involved, the recipients and senders. Need to decide how these are used. If use public key on the "entire" message (not common due to speed), then have to be careful of which modulus is larger. Otherwise separate out the encryption (using of a session key then used to encrypt the message with a block cipher) from authentication (signing the hash of the message), and send each component separately.
p
, public primitive root a
x
y = a^{x} mod p
(y,a,p)
(x)
Another signature scheme is based on the ElGamal encryption algorithm. Unlike RSA, ElGamal is not commutative, however a variant exists for computing and verifying signatures. As with ElGamal encryption, its security is based on the difficulty of computing discrete logarithms. Key generation is the same as for ElGamal encryption.
k, GCD(k,p-1)=1
K = a^{k}(mod p)
S
:M = x.K + k.S mod (p-1)
; that is findS = k^{-1}(M - x.K) mod (p-1)
(K,S)
k
should be destroyed after use
(K,S)
on message M
confirm that:
y^{K}.K^{S}mod p = a^{M}mod p
When signing a message, again create and "protect" a temporary signing key, then use it to solve the specified equation to create the signature. Note that M here is usually the hash of the actual message. Verification consists of confirming the validation equation that relates the signature to the (hash of the) message.
p=11, g=2
x=8
y = a^{x} mod p = 2^{8} mod 11 = 3
y=3,g=2,p=11
M=5
k=9
gcd(10,9)=1
K = a^{k} mod p = 2^{9} mod 11 = 6
5 = 8.6+9.S mod 10; nb 9^{-1} = 9 mod 10;
hence S = 9.(5-8.6) = 3 mod 10
(K=6,S=3)
3^{6.}6^{3} = 2^{5} mod 11
3.7 = 32 = 10 mod 11
DSA is the US Govt approved signature scheme - designed to provide strong signatures without allowing easy use for encryption (they don't mind people having authenticated messages ... as long as they can read 'em!!) Needless to say, loopholes round have been found to do encryption. However the signature schmeme has advantages, being both smaller (320 vs 1024bit) and faster (much of the computation is done modulo a 160 bit number) than RSA.
(p,q,g)
are chosen:
p = 2^{L}
q
, a 160 bit prime factor of p-1
g = h^{(p-1)/q}
h<p-1
, h^{(p-1)/q}(mod p)>1
x<q
y = g^{x}(mod p)
DSA key generation is related to, but somewhat more complex than El Gamal. Mostly because of the use of the secondary 160-bit modulus q used to help speed up calculations and reduce the size of the resulting signature.
k, k<q
r = (g^{k}(mod p))(mod q)
s = k^{-1.}SHA(M)+ x.r (mod q)
(r,s)
with message
w = s^{-1}(mod q)
u1= (SHA(M).w)(mod q)
u2= r.w(mod q)
^{}^{} v = (gu1.yu2(mod p))(mod q)
Signature creation is again similar to ElGamal with the use of a per message temporary signature key k, but doing calc first mod p, then mod q to reduce the size of the result. Note that the use of the hash function SHA is explicit here. Verification also consists of comparing two computations, again being a bit more complex than, but related to El Gamal. See Stallings 10A for proof of why verification works (its messy). Note that nearly all the calculations are mod q, and hence are much faster.
Security of DSA is regarded as high (basically as good as RSA or ElGamal with same sized modulus), but its more efficient. Hence its now a popular choice. The US Govt attempt to have a signature-only scheme is problematic, as most implementations fail to check the size of modulii supllied, and hence can be coerced into computing general public key algs. The presence of a subliminal channel exists in many schemes (any that need a random number to be chosen), not just DSA. It emphasises the need for "system security", not just a good algorithm.
The patents on these algs have their use problematical, however these patents should soon expire. More generally, the ideas have been superceeded by DSA.
KeyedHash = Hash(Key|Message)
KeyedHash = Hash(Key1|Hash(Key2|Message))
Idea is to derive a private key authentication scheme based on a hash function, rather than having the "overhead" of a public key scheme when its not required (ie when private keys are available). This has evolved through several iterations as problems were found with the original, simplest variants.
HMAC_{K} = Hash((K+ XOR opad)||Hash((K+ XOR ipad)||M))
K+
is the key padded out to size
opad, ipad
are specified padding values
The idea of a keyed hash evolved into HMAC, designed to overcome some problems with the original proposals. Further have a design that has been shown to have the same security as the underlying hash alg. The hash function need only be used on 3 more blocks than when hashing just the original message (for the two keys + inner hash). Choose hash alg to use based on speed/security concerns.
prime p=31
prim root a=3
M=7
.
prime p=31
prim root a=12
M=19
.