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 p). [= here is 3 bars]

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 = M (mod N) [= here is 3 bars]

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₀, y₀) and (x₁, y₁) on the line, the verifier can compute the slope of the line using the familiar "rise over the run" formula

m = y_{0 -} y₁ / x₀ - x₁ (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 = n^x . c (mod p). [ = here is 3 bars]

11-03-96  22:55 EST

Hyper-linked Notes and References.

At equations, replaced phi with f.