Signatures
\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\G{\mathrm{G}} \gdef\H{\mathtt{H}} \gdef\HP{\mathtt{H}_{\mathrm{P}}}
Take \G a generator of a group in which discrete logarithm is hard. Capital letters denote group elements, lower case are field elements in the groups multiplicative order, and bold are vectors of either. Take \H, \HP hash functions mapping their inputs to a field element and a group element respectively.
The verification steps can all be checked using basic algebra. This is a useful exercise for the reader.
Warning. These formulas are just to clarify the basic schemes and omit many security critical checks.
Schnorr Signatures
Bob wants to authenticate a message m to Alice. Bob generates a random number 'private key' b and computes 'public key' B = b ⋅\G. Bob securely shares B with Alice. Bob computes
\begin{aligned} R &= \H(b, m) ⋅ \G & e &= \H(R, m) & s &= \H(b, m) - e ⋅ b \end{aligned}
Bob sends the message m and signature (e, s) to Alice. Alice verifies by recovering R and checking \H(R, m) = e using
\begin{aligned} R &= s ⋅ \G + e ⋅ B & \end{aligned}
Note: sometimes \H(R, B, m) is used instead of \H(R, m).
As a variant, the signature is (R, s) which is verified by recovering B using
B = \frac{R - s ⋅ G}{\H(R, m)}
ElGamal / DSA Signatures
Bob wants to authenticate a message m to Alice. Bob generates a random number 'private key' b and computes 'public key' B = b ⋅\G. Bob securely shares B with Alice. Bob computes
\begin{aligned} R &= \H(b, m) ⋅ \G & s &= \frac{\H(m) + \H(R) ⋅ b}{\H(b, m)} \end{aligned}
Bob sends the message m and signature (R, s) to Alice. Alice verifies by checking
\H(m) ⋅ \G + \H(R) ⋅ B - s ⋅ R = 0
Alternatively, Alice verifies by recovering B using
B = \frac{s ⋅ R - \H(m) ⋅ \G}{\H(R)}
It is common to take \H(R) to be the x-coordinate of R. This is not a good hash since \H(-R) = \H(R). In this case (-R, -s) would also a valid signature.
If instead of \H(b,m) an arbitrary non-trivial value k is used this also results in a valid signature. However, if the same k is used to sign multiple messages m_1, m_2 with signatures (R_1, s_1), (R_2, s_2) then R_1 = R_2 and we can recover k and b by
\begin{aligned} k &= \frac{\H(m_1) - \H(m_2)}{s_1 - s_2} & b &= \frac{k ⋅ s_1 - \H(m_1)}{\H(R)} \end{aligned}
As a variant, the signature can be (\H(R), s) which is then verified using
\H\p{\frac{\H(m)}{s} ⋅ \G + \frac{\H(R)}{s} ⋅ B} = \H(R)
Again, if \H(R) is simply the x-coordinate, \H(-R) = \H(R) and (\H(R), -s) is also a valid signature.
Blind Signatures
Alice and Bob want Bob to sign m without revealing m to Bob. For example, Bob is notary that verifies Alice's passport to authenticates Alice's messages. Alice does not want Bob to know their content. Bob has a key pair b, B. Bob generates a random number k, computes R' = k ⋅ \G and sends R' to Alice. Alice generates random numbers u, v and computes
\begin{aligned} R &= u ⋅ R' + v ⋅\G & m' &= \frac{\H(R, m)}{u} \end{aligned}
Alice sends m' to Bob. Bob computes s' = k - m' ⋅ b and sends s' to Alice. Alice computes s = u ⋅ s' + v The signature is (R, s). Verification is as in Schnorr by recovering Bob's key:
B = \frac{R - s ⋅ \G}{\H(R, m)}
Ring Signatures
There are many Bob's all with key pairs b_i, B_i. Alice has public keys \vec B = B_1, \dots B_n. Bob number s wants to send a message to Alice without revealing s. Bob generates random numbers k and \vec r except r_s. Bob computes the recursion (with indices wrapping around) and completes \vec r
\begin{aligned} c_s &= \H(\vec B, m, k ⋅ \G) & c_i &= \H(\vec B, m, r_i ⋅ \G + c_{i - 1} ⋅ B_i) & r_s &= k - c_{s - 1} ⋅ b_s \end{aligned}
Bob sends m and the signature (c_1, \vec r) to Alice. Alice verifies by reconstruct \vec c using c_1 and the above recursion step. If this circles around and produces c_1 again then the signature is correct.
Linkable Ring Signatures
Same as ring signatures, but Alice can also determine if two messages came from the same Bob. Bob number s now computes
\begin{aligned} K &= b_s ⋅ \HP(B_s) \\ c_s &= \H(\vec B, m, k ⋅ \G, k ⋅ \HP(B_s)) \\ c_i &= \H(\vec B, m, r_i ⋅ \G + c_{i - 1} ⋅ B_i, r_i ⋅ \HP(B_i) + c_{i - 1} ⋅ K) \\ r_s &= k - c_{s - 1} ⋅ b_s \end{aligned}
Bob sends m and the signature (K, c_1, \vec r) to Alice. Alice verifies by reconstruct \vec c using c_1 and the above recursion step. If this circles around and produces c_1 again then the signature is correct. Two signatures are by the same Bob iff the K values are the same.
Stealth Addresses
Alice wants to mention Bob without identifying him. Bob creates two keypairs (a, A) and (b, B) and sends (A, B) ('stealth address') to Alice. To mention Bob, Alice picks a random number r and computes
\begin{aligned} R &= r ⋅ \G & P &= \H(r ⋅ A) ⋅ \G + B \end{aligned}
Alice mentions (P, R). Bob looks through all mentions and for each checks
P = \H(a ⋅ R) ⋅ \G + B
If this holds, then it was Bob who was mentioned and he can compute p such that P = p ⋅ \G.
p = \H(a ⋅ R) + b
Bob proceeds with a signature algorithm using (p, P) as the keypair to sign messages as the person mentioned without revealing his identity.
Note that (a, B) ('scanning key') is sufficient to recognize mentions of Bob, but (a, b) ('signing key') is required to sign.
Hierarchical Deterministic Wallets
Bob has private key b and public key B = b ⋅ \G. Bob wants to derive more key pairs. Both in a way that Alice can follow using the public key and not.
Bob creates a random 'chain code' c and shares it with Alice. Bob's 'extended private key' is (b, c) and Alice has the 'extended public key' (B, c).
To create the i-th new key pair such that Alice can follow, compute
\begin{aligned} b' &= b + \H(c, B, i, 0) & c' &= \H(c, B, i, 1) \end{aligned}
The new extended private key is (b', c') and Alice can derive the i-th new extended public key
\begin{aligned} B' &= B + \H(c, B, i, 0) ⋅ \G & c' &= \H(c, B, i, 1) \end{aligned}
To derive the i-th key pair that Alice can not follow, compute
\begin{aligned} b' &= b + \H(c, b, i, 0) & c' &= \H(c, b, i, 1) \end{aligned}
