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

gq = 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 <> or (202) 639-7200. See:

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

Msv = 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 (x0, y0) and (x1, y1) on the line, the verifier can compute the slope of the line using the familiar "rise over the run" formula

m = y0 - y1 / x0 - x1 (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

(***)    gy = nx . c (mod p). [ = here is 3 bars]

11-03-96  22:55 EST

Hyper-linked Notes and References.

At equations, replaced phi with f.