Corrections for nsamint.htm:

Note: All corrections here have been made to the current version.

11-01-96 19:20 EST

**3.2** ... *The Schnorr Algorithms.* The Schnorr family of algorithms
includes an identification procedure and a signature with appendix. These
algorithms are based on a zero-knowledge proof of possession of a secret
key. Let *p* and *q* be large prime numbers with *q* dividing
*p - 1*. Let [replace "*q*" by
"*g*"] *g* be a generator; that
is, an integer between 1 and *p* such that

*g ^{q}* = 1 (mod

11-02-96 9:45 EST, Add credit and pointer at top of paper:

Anonymous: Fried, Frank got NSA's permission to make this report available. They have offered to make copies available by contacting them at <21stCen@ffhsj.com> or (202) 639-7200. See: http://www.ffhsj.com/bancmail/21starch/961017.htm

11-02-96 18:45 EST

**3.2** ... *RSA Signatures.* The most well-known signature with
message recovery is the RSA signature. Let *N* be a hard-to-factor integer.
The secret signature key *s* and the public verification key *v*
are exponents with the property that

*M ^{sv}* =

**3.2** ... *Schnorr proof of possession:*...

An important feature of this protocol is that it can be performed only once
per line. For if he knows any two points
(*x*_{0},
*y*_{0}) and (*x*_{1},
*y*_{1}) on the line, the verifier can compute the slope of
the line using the familiar "rise over the run" formula

*m* = *y*_{0}_{ -
}*y*_{1} / x_{0} -
x_{1} (mod *q*), [= here is 3 bars]

**3.2** ... Then *c* and *n* give us the "shadow" of the line
under *phi*. Knowing *c* and *n* doesn't give us the slope
or intercept of the line, but it does enable us to determine whether a given
point (*x, y*) is on the line. For if (*x, y*) satisfies (**),
then it must also satisfy the relation

(***) *g ^{y}* =

11-03-96 22:55 EST

Hyper-linked Notes and References.

At equations, replaced *phi* with
*f*.