1 files changed, 194 insertions, 0 deletions

diff --git a/ss2017/cryptography/Notes17.txt b/ss2017/cryptography/Notes17.txt
new file mode 100644
index 0000000..6a15827
--- /dev/null
+++ b/ss2017/cryptography/Notes17.txt
@@ -0,0 +1,194 @@
+17 Digital signatures
+---------------------
+
+Digital signatures are the public key analogues of message
+authentication schemes (MAC). They allow a *signer* to authenticate a
+message with their *private key* by producing a tag that can
+subsequently be verified by anyone who has the corresponding public
+key. Just as with MACs the tags are specific to the message being
+signed. Changing the message in any way should invalidate the tag,
+thus the "signature". Also no-one who is not in the possession of the
+private key corresponding to the public key used for verification
+should be able to produce a valid signature.
+
+Definition: a signature scheme is a triple Pi=(Gen,Sign,Vrfy) of ppt
+algorithms where
+
+1. Gen(n) produces a public/private key-pair (pk,sk) 
+
+2. The signing algorithm Sign takes a secret key and a message m and
+produces a signature sigma<-Sign_sk(m).
+
+3. The (deterministic) verification algorithm Vrfy takes a public key,
+a message m, and a signature sigma, and answers 1 or 0. If
+sigma<-Sign_sk(m) then Vrfy_pk(m,sigma) must return 1.
+
+If Sign_pk is defined only for messages of length l(n) for some
+function l() then we speak of a *fixed length* signature scheme.
+
+The signature scheme Pi=(Gen,Sign,Vrfy) is *secure* if the
+success probability of the following experiment is negligible for any
+ppt adversary A:
+
+Experiment Sig-forge_{A,Pi}(n):
+
+1. (pk,sk)<-Gen(n)
+
+2. A gets n, pk, and oracle access to Sign_sk(). The adversary then
+outputs (sigma,m). Let Q be the sequence of questions to the oracle
+posed so far, i.e. messages for which a signature has been requested.
+
+3. The outcome of the experiment is 1 iff Vrfy_pk(m,sigma)=1 and m is not in Q.
+
+End of definition.
+
+In KL our "secure" is called "existentially unforgeable under an adaptive
+chosen-message attack" to differentiate from other, weaker notions of
+security.
+
+
+Insecure signature based on textbook RSA
+- - - - - - - - - - - - - - - - - - - - -
+
+A naive attempt at defining a signature scheme based on RSA goes as
+follows:
+
+Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d)
+   output (pk,sk)
+
+Sign_{(N,d)}(m):
+   output m^d mod N
+
+Vrfy_{(N,e)}(m,sigma):
+   output 1 iff sigma^e = m (mod N)
+
+Clearly, verification of a valid signature succeeds but the scheme is
+insecure for several reasons. First, if an adversary can choose an
+arbitrary signature sigma first and then fabricate a corresponding
+"message" as m=sigma^e mod N. Notice that Vrfy_{(N,e)}(m,sigma)
+succeeds, so this adversary will win the experiment with certainty. 
+
+Second, and perhaps more realistically, if the adversary would like to
+get a signature on a previously fixed message m it could request
+signatures sigma1 for random m1 and sigma2 for m2:=m/m1 (mod N). It is
+then clear that sigma1*sigma2 mod N is a valid signature for the
+original m.
+
+
+Secure signatures with random oracles
+- - - - - - - - - - - - - - - - - - -
+
+It is possible, but rather inefficient, to construct secure signature
+schemes based on the RSA assumption and a collision-resistant hash
+function, see KL12.6. In practice, one uses signature schemes based on
+cryptographic hash functions which can only be proved secure in the
+random oracle model. We thus modify our definition of secure signature
+scheme to the effect that both parties now have access to a function
+H:{0,1}^n->{0,1}^n which is selected uniformly at random at the
+beginning of the experiment.
+
+In this situation we have the following signature scheme RSA-FDH
+("full domain hash").
+
+RSA-FDH:
+
+Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d)
+   output (pk,sk)
+
+Sign_{(N,d)}(m):
+   output H(m)^d mod N
+
+Vrfy_{(N,e)}(m,sigma):
+   output 1 iff sigma^e = H(m) (mod N)
+
+In practice, the random oracle H() will be replaced by a cryptographic
+hash function such as SHA-2 and the scheme is just like the
+abovedescribed insecure one with the exception that the message is
+hashed prior to signing.
+
+Let us see how this prevents the previous two attacks. Firstly, if the
+attacker starts with arbitrary sigma then in order to fabricate a
+corresponding message it would have to find m such that sigma^e=H(m)
+(mod N) and thus for a given H()-value which it *can* compute, namely
+sigma^e, find an inverse image, which is infeasible.
+
+Similarly, in order to perpetrate the other attack it would have to
+fabricate for given m two values x and y so that H(x)*H(y)=H(m).
+While this is infeasible for truly random H() and not possible with
+current knowledge for SHA-2 it is not prevented by mere
+collision-resistance.
+
+Theorem: If GenRSA() fulfills the RSA assumption then RSA-FDA is
+secure in the random oracle model.
+
+Proof: Let A be an attacker in the Sig-forge_{A,RSA-FDA}
+experiment. We may fix a polynomial q(n) bounding the queries of A to
+H() and also assume that A first queries H(m) for any message for
+which it requests a signature or which it finally outputs. We also
+assume that A makes exactly q(n) queries. All this is done in order to
+save a few case distinctions in the argument.  We now build from A an
+attacker A' against GenRSA() in the RSA-inv(n) experiment from Chapter
+12 as follows.
+
+Attacker A' against GenRSA:
+
+Given N, e, y* = x^e mod N we (assuming the role of A') choose
+j<-{1..q(n)} and forward the public key pk=(N,e) to A.
+
+When A makes its i-th query m_i to H() we answer as follows:
+
+If i=j we return y*.  If m_i has been asked previously, i.e., if
+m_i=m_j for some j<i, then we answer consistently using a table to
+store earlier answers.  Otherwise, we choose sigma_i <-Z_N^* uniformly
+at random, answer y_i=sigma_i^e mod N and remember both y_i and
+sigma_i in our table.
+
+As a result, for all the H()-values that A has access to we know their
+e-th root modulo N.
+
+When A requests a signature on message m then, since H(m) has been
+queried before, we have stored in our table sigma so that sigma^e=H(m)
+and can thus return that very sigma which clearly is a valid
+signature.
+
+The only one message for which we do not have an e-th root is the j-th
+one. Should the adversary A request a signature for the latter we
+abort the experiment, i.e. return an arbitrary guess.
+
+Finally, A will output a pair (m,sigma). If m=m_j and sigma^e=y* (mod
+N) then we can output sigma (and we will win the RSA-inv experiment).
+
+This concludes the description of the adversary A' against GenRSA().
+
+We first note that even though we prepare the answers to A's
+H()-queries using a table and case distinctions the resulting function
+looks uniformly random from A's perspective. So, it, i.e. A, will work
+just as in the standard Sign-forge experiment.
+
+Now, A' wins the RSA-inv experiment if A produces a valid forgery
+(m,sigma) and m = m_j.  If epsilon(n) is A's winning probability in
+the Sig-forge experiment then this happens with probability
+epsilon(n)*1/q(n). But by the RSA hardness assumption the latter
+quantity is negligible and therefore, since q(n) is polynomial in n,
+so is epsilon(n). QED 
+
+We remark that a similar scheme based on discrete logarithms is known
+as the Schnorr signature. 
+
+Hash-and-sign
+- - - - - - -
+
+We note that if the hash function used here is arbitrary length then
+the above scheme allows for the signing of messages of arbitrary
+length. The security proof can be generalised to this, but becomes
+somewhat awkward since arbitrary length random oracles have not been
+properly defined.
+
+Alternatively, one can turn any secure fixed length signature scheme
+into an arbitrary length one by first hashing the message to be signed
+with an arbitrary length collision-resistant hash function and then
+signing the hash. The proof of security is analogous to the one for
+the Hash-and-MAC paradigm given in Chapter 11. This is known as
+"Hash-and-sign".
+
+