1. Parallels and differences between digital signatures and “secret data
transfer”.
2. RSA-Algorithm: Compute the private key: the two primes p=11 and
q=17 and the public key e=21 is given.
3. Signing is a procedure that needs a lot of ressources. How we can
sign large message without having to sign the whole content of a message?
4. A possible attack on a RSA signature
5. The RSA signature scheme has the following multiplicative property,
sometimes referred to as the homomorphic property. If s1 = m1d mod n and s2 = m2d mod n are
signatures on messages m1 and m2, respectively (or
more properly on messages with redundancy added), then s = s1*s2 mod n has the
property that s = (m1*m2)d mod
n. How can we prevent that s is a valid signature for m = m1*m2?
1. Parallels: both can be realized with the same algorithm (e.g.
RSA).
Differences: A digital signature proofs that a message is >from a
certain signer and has not been changed. therefor he needs a private key known
only by him. His signed message can be read by all (or at least by persons
knowing the public keys). The origination entity only wants to tell us that he
(and no other) has written exactly this message.
If we „sign“ a message with the public key, no one except the owner of
the private key can recover the message. So in this case all owners of the
public keys can “sign” a message but afterwards only one can read it.
2. With p=11, q=17 we compute the other pulic key: n=p*q=11*17=187 and
a=(p-1)*(q-1)=10*16=160
So the given public key e=21 correspond to the conditions 1<e<a
and ggT(a, e)=1.
The private key d must solve e*d – y*a = 1 (y is an integer). We solve
this equation in two steps, first we compute gcd(a, e) with the Euclidean
algorithm and then we use the single steps of the algorithm the other way
round.
gcd(21, 160) : 160 = 7*21 + 13
21
= 1*13 + 8
13
= 1*8 + 5
8
= 1*5 + 3
5
= 1*3 + 2
3
= 1*2 + 1
2
= 2*1 + 0
1 = 3 – 2 = 3 – (5 -3) = 2*3
– 5 = 2*(8 - 5) – 5 = 2*8 – 3*5 = 2*8 – 3*(13 - 8) = 5*8 – 3*13 = 5*(21 – 13) –
3*13 = 5*21 – 8*13 = 5*21 – 8*(160 – 7*21) = 61*21 – 8*160
so d = 61
3. A possible solution is called „Digital Signature Scheme with Appendix“.
Instead of the message’s whole content we sign only a hash-value of the
message. The hash-functions is known by all.
What we send is the unsigned message and its signed hash-value. now the
receiver can recover the hash-value and compare it with the hash-value of the
meassge he has calculated by himself. If they are different he rejects the
message.
4. Integer factorization: If an adversary is able to factor the public
modulus n of some entity A, then the adversary can compute a and then, using
the extended Euclidean algorithm, deduce the private key d from a and the
public exponent e by solving e*d=1(mod a).This constitutes a total break of the
system. To guard against this, A must select p and q so that factoring n is a
computationally infeasible task.
5. If m = m1*m2 has the proper redundancy, then s
will be a valid signature for it. Hence, it is important that the redundancy
function R is not multiplicative, i.e., for essentially all pairs a, b element
of M, R(a*b) != R(a)*R(b).
6. Services of digital signatures:
-
Only the legitimated sender can originate the signature – Identification
and Authentication
-
The recipent has the possibility to check the signature non-ambiguously
– Conservation of evidence
-
The signature is only valid for the determined document
In the last few years digital signatures were considered to be absolutly
essential for e-Commerce. That is doubted today. It is not so sure that digital
signatures are still necessary at all in the field of e-Commerce. Companys
selling services via internet solved the identification of customers by other
means (e.g. usernames and password). Most of the companys do not have any
choice because for example Switzerland has still not constitued a legal order
on digital signatures. In other countries may exist laws concerning digital
signatures, but they do for instance only accept a few national certification
centers that are not accepted in other countries.
On the other side the whole communication by e-Mail would be graded up
by a substantial spread of digital signatures. It would be possible to signe
contracts online. But still today financial services are available on the web
and they are secured by other means than digital signatures.