[16469] in Athena Bugs
sun4 8.2.13: latex2html (in the infoagents locker)
daemon@ATHENA.MIT.EDU (Arthur E Housinger)
Wed Nov 4 21:38:59 1998
To: bugs@MIT.EDU
Date: Wed, 04 Nov 1998 21:38:55 EST
From: Arthur E Housinger <mouse@MIT.EDU>
System name: maleficent.mit.edu
Type and version: SPARC/4 8.2.13
Display type: tcx
What were you trying to do?
Run it on a file in a subdirectory called 6.857
What's wrong:
Instead of creating figures in the subdirectory that it creates, it
creates figures called 6.001, 6.002, etc... in the parent directory for
6.857
Please describe any relevant documentation references:
This is the file that I was working with. (Called ps5-1.tex file.) I
tried running latex2html on it when it was in /usr/tmp/6.857 and
/usr/tmp/6857. The latter was successful.
\documentstyle[12pt, fullpage]{article}
\title{Problem 5-1}
\author{Fu Korrinn; Ng Joyce; Wijeyekoon Arjuna}
\date{}
\begin{document}
\maketitle
In the original ElGamal works in the following way
Given : p, q
$y = g^x(mod p)$
$s = \frac {m-rx} {k}$ mod (p-1)
$r = g^k$ (mod p)
$sk + rx = m$ mod (p-1)
$g^{sk} g^{rx} = g^{m}$ (mod p)
Verification :
$r^sy^r ??=?? g^m$ (mod p)
\leftline {\bf Part A}
After modification:
$r = y^k = g^{kx}$ (mod p)
Original :
$s = \frac {m-rx} {k}$ mod (p-1)
New Modification :
$s = \frac{m-r}{k}$ mod (p-1)
According to the new verification (part b)
$r^sy^r ??=?? y^m$ (mod p)
$g^{skx}g^{rx} ??=?? g^{mx}$ (mod p)
Assume it's verified to be true,
Then
$skx + rx = mx$ (mod (p-1))
*Note that x is not proven to be relatively prime to (p-1) , no division
is allowed for x
$skx + rx - mx = 0$ (mod (p-1))
$x (sk + r -m) = 0$ (mod (p-1))
Therefore either one of the following is true
$x = 0$ (mod (p-1)) or
$sk+r-m = 0$ (mod (p-1))
However, the first option is not valid by our definition.
Thus
$s = /frac{m-r}{k}$ (mod (p-1))
*k is relatively prime to (p-1) , thus division is allowed here
\leftline {\bf Part B}
Original Verification:
$r^sy^r ??=?? g^m$
New Verification:
$r^sy^r ??=?? y^m$
\leftline {\bf Part C}
To show insecurity, we need to show how to come up with a $r$ without
the secret key $x$ in it
Given:
$r=y^k$
from our new signature:
$s = \frac{m-r}{k}$ mod (p-1)
$sk = m-r$ (mod (p-1))
$r = m-sk$ (mod (p-1))
\end{document}
