X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/6606ff41fcf6918d7aee5d4da006e57dffee35c9..56c48de4fa0f5e92773fe5b7c0989005a4426218:/auth-sig.tex

diff --git a/auth-sig.tex b/auth-sig.tex
index 8faff1e..17f0bad 100644
--- a/auth-sig.tex
+++ b/auth-sig.tex
@@ -130,7 +130,7 @@
   \begin{itemize}
   \item It allows key-only existential forgery.  Suppose we're given a public
     key $(n, e)$.  Choose a signature $\sigma \in \Z/n\Z$.  Compute $m =
-    \sigma$.  Then $(m, \sigma)$ is a valid signed message.
+    \sigma^e$.  Then $(m, \sigma)$ is a valid signed message.
   \item It allows universal forgery under chosen message attack.  Suppose
     we're given a public key $(n, e)$, and asked to forge a signature for
     message $m$.  Choose $k \inr (\Z/n\Z)^*$, and request a signature
@@ -174,8 +174,8 @@
   \item $|\hat{m}| = 8k$, i.e., $\hat{m}$ is a $k$-byte string;
   \item $0^8$ is the string of 8 zero-bits;
   \item $T = 00000001$ is an 8-bit \emph{type} code;
-  \item $1^z$ is a padding string of one-bits (\PKCS1 requires $z \ge 64$);
-    and
+  \item $1^z$ is a padding string of one-bits (with $z$ chosen so that
+    $\hat{m}$ has the right length; \PKCS1 requires $z \ge 64$); and
   \item $I_H$ is an identifier for the chosen hash function $H$.
   \end{itemize}
   This bit string is then converted into an integer, using a big-endian
@@ -201,10 +201,10 @@
   
   In \cite{Brier:2001:CRS}, Brier, Clavier, Coron and Naccache analyse
   general affine padding schemes, of which the \PKCS1 scheme is an example,
-  and show that if the `message' -- the hash -- is more than a third the size
-  of the modulus.  In particular, existential forgery is possible in
-  polynomial time, and selective forgery in subexponential time (though much
-  faster than factoring the modulus).
+  and show that the schemes can be broken if the `message' -- the hash -- is
+  more than a third the size of the modulus.  In particular, existential
+  forgery is possible in polynomial time, and selective forgery in
+  subexponential time (though much faster than factoring the modulus).
 \end{slide}
 
 \xcalways\subsection{Full-domain hashing}\x
@@ -370,15 +370,15 @@
     $\Xid{S}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}(K, m)$: \+ \\
       $r \getsr \{0, 1\}^k$; \\
       $h \gets H(m \cat r)$; \\
-      $h' \gets (r \cat 0^{8n-2k}) \xor H'(x)$; \\
+      $h' \gets (r \cat 0^{8n-2k}) \xor H'(h)$; \\
       $y \gets 0^8 \cat h \cat h'$; \\
       \RETURN $T_K(y)$;
   \next
     $\Xid{V}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}
       (P, m, \sigma)$: \+ \\
       $y \gets f_P(\sigma)$; \\
-      \PARSE $y$ \AS $z \cat k\colon h \cat 8n - k\colon h'$; \\
-      \PARSE $h' \xor H'(h)$ \AS $k\colon r \cat z$; \\
+      \PARSE $y$ \AS $z, k\colon h, 8n - k\colon h'$; \\
+      \PARSE $h' \xor H'(h)$ \AS $k\colon r, z$; \\
       \IF $z = 0 \land z' = 0 \land h = H(m \cat r)$
       \THEN \RETURN $1$; \\
       \ELSE \RETURN $0$;
@@ -495,8 +495,8 @@
       $(m, \sigma) \gets A^{\id{sign}(\cdot), H(\cdot), H'(\cdot)}(P)$; \\
       \IF $m \in \Xid{m}{list}$ \THEN \ABORT; \\
       $y' \gets f_P(\sigma)$; \\
-      \PARSE $y'$ \AS $z \cat k\colon h \cat 8n - k\colon g$; \\
-      \PARSE $g \xor H'(h)$ \AS $k\colon r \cat z'$; \\
+      \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\
+      \PARSE $g \xor H'(h)$ \AS $k\colon r, z'$; \\
       $x \gets m \cat r$; \\
       \IF $z \ne 0 \lor z' \ne 0$ \THEN \ABORT; \\
       \IF $h \ne H(x)$ \THEN \ABORT; \\
@@ -511,8 +511,8 @@
         $\sigma' \getsr \ran f_P$; \\
         $y' \gets f_P(\sigma')$; \- \\
       \UNTIL $y' < 2^{8n}$; \\
-      \PARSE $y'$ \AS $z \cat k\colon h \cat 8n - k\colon g$; \\
-      \PARSE $g$ \AS $k\colon r' \cat g'$; \\
+      \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\
+      \PARSE $g$ \AS $k\colon r', g'$; \\
       $h' \gets (r \xor r') \cat g'$; \\
       \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\
       $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\
@@ -524,10 +524,10 @@
       \IF $x \in \dom \Xid{H}{map}$ \THEN \RETURN $\Xid{H}{map}(x)$; \\
       \REPEAT \\ \quad\=\+\kill
         $(s, y') \gets \id{sr-choose}(P, y)$; \\
-        \PARSE $x$ \AS $m \cat k\colon r$; \- \\
+        \PARSE $x$ \AS $m, k\colon r$; \- \\
       \UNTIL $y' < 2^{8n}$; \\
-      \PARSE $y'$ \AS $z \cat k\colon h \cat 8n - k\colon g$; \\
-      \PARSE $g$ \AS $k\colon r' \cat g'$; \\
+      \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\
+      \PARSE $g$ \AS $k\colon r', g'$; \\
       $h' \gets (r \xor r') \cat g'$; \\
       \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\
       $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\