doc: crypto_sign: fix memcmp() instead of memcpy() in example

doc: crypto_sign: fat -> composite

It's a matter of taste ("fat pointer" is a term, too),
but I feel like that's not a term fitting the rest of the manual style.

doc: crypto_sign: fix wording nits, grammar

In particular:

- clarify NULL goes in public_key (not secret_key)
- add parenthetical note to define the term "fat public key" inline
- fix commas (I actually had to look up the rules for comma-before-but)
- avoid colloquial "we"

doc: fix crypto_sign metadata to reflect 8697f2ffd

Document EdDSA API misuse

Partially addresses #240

We may want to write a safer API on top of the low-level one, that
bundles the seed and public key together as a single 64 bytes blob.

makefile: fix cross-compilation

Document MONOCYPHER_CPP_NAMESPACE

Fixed CHANGELOG

Changelog for version 3.1.3

Restore simple fe_frombytes()

Though I think the option of choosing how many bits we mask off at the
end is useful, it made the code more confusing. Better leave it for the
one case where we really need it: parsing Elligator representatives,
which are represented with one less bit than usual.

This does cost us 4 lines of code, but I think they're worth it. The
previous code was too much like code golf for my comfort.

Fixed Elligator reverse map comments

Also took the opportunity to fix the Python inverse map when the point
is zero (it used to fail, now it returns the all zero representative).

Removed redundant Valgrind tests

I think we don't need to test both -O2 and -O3. We're checking memory
error here, they should not be much different under different
optimisation settings (though maybe -O3 can trigger more bugs).

Also did not add myself to the list of authors, I think this trivial
change is not copyrightable.

Only Christ Fogelklou wrote ci.yml

Squashed commit of the following:

commit 41cd7c9a3270c5a3c94d379dee2e4242ec69fc25
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 06:20:14 2022 +0100

    Remove some extraneous lines.

commit b0a7dddc5a3bf03a7bec2621cce5dd1c2620753e
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 06:10:01 2022 +0100

    Add crashy builds.

commit 3a6b343df68f074aa626f619d7ac9c8fe860e23a
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 06:09:09 2022 +0100

    One more test - crashy flags

commit 2c399f4fd42488f6aae205b369ea10d91b824050
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 06:05:14 2022 +0100

    Install valgrind before using it.

commit a57a7abd526934f5d90ad2a20c651bc832ea3047
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 06:02:39 2022 +0100

    Try GCC and Clang, build with different varieties of compiler and cflags

commit 07f435959c6cfc10f4d6a46d9ba5048bbe30a410
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 05:58:41 2022 +0100

    Try slightly better optimization.

commit d5d8b6ba7eb453a2fe8e5aca7715477443135b64
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 05:55:45 2022 +0100

    Missed the make clean command.

commit cf60bc603ce28eb6671414edb5e003f9bf4a6e87
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 05:52:07 2022 +0100

    Try with optimization level 0

commit 630b0a957555adb0b22af9eb720fb25bee56f728
Author: Chris Fogelklou <chris.fogelklou@gmail.com>
Date:   Fri Mar 11 05:41:30 2022 +0100

    Start a new PR so as to not keep working in the old one.

Add badge pointing to LoupVaillant Github Actions (#2)

* Add a comment to the ci.yml file about also running on macos.
* Add a link to the new CI badge using Github Actions.

Run basic tests taken from the readme.md file using Github Actions.

* Add a github workflow which follows the basic install flow in the readme.md.
* Add installation of libsodium.
* Add valgrind as a dependency.
* Add llvm to list of dependencies.

doc/x25519: Mention hashing the public keys

#232 but for crypto_x25519.

Manual: hash shared secret *and* public keys

Adjust man2html.sh to deprecated crypto_key_exchange

crypto_hchacha20: Remove reference to deprecated crypto_chacha20_encrypt

Addresses @LoupVaillant's comment in #233.

Deprecate crypto_key_exchange

See #230.
In summary:
The way crypto_key_exchange() works was not optimal.
Several combinations of (private, public) key pairs produce the same
shared secret (see 54a7ef551078dda001f94f1045e142af0fc1008a);
crypto_key_exchange() did nothing to mitigate that.

Since this is a high-level function that cannot be saved even with
documentation because it is so fundamentally misguided,
it is now deprecated (see #232).
Users are encouraged to either adopt the function into their own code
if and only if they require it for backwards compatibility,
starting with the release that removes it,
or preferably migrate to implementing an existing protocol,
such as instantiating a Noise protocol pattern or a protocol like X3DH.

doc: Mention hashing the public keys (#232)

Mention hashing the public keys

Closes #230.

Fix invsqrt() boolean return

The invsqrt() function used to return true when its operand was a
non-zero square.  Thing is, it was used to determine whether it was a
square, *period*.  If the operand was zero, we had the wrong answer.

This introduced two "errors" visible by the end user:

* The all-zero X25519 point could not be mapped back to an Elligator 2
  representative.  In practice that point is never used, but that does
  not comply with the original paper.

* The (0, 1) EdDSa public key could not be serialised, causing any
  signature verification associated with it to fail. This one we really
  don't care, because even though it is on the curve, that point has low
  order, and legitimate public keys all have prime order.

Fixes #231

Rephrased awkward sentence in documentation

Readability nitpick

Reverted 'log in' back into 'login'

Turns out even though many dictionaries don't recognise it,
'login' was correct.

Fixed typo in AUTHORS.md

Fixed many typos

Found by Samuel Lucas, applied at my discretion

Use global constant L instead of duplicating it

Renamed 'Sha512' to 'SHA-512'

Rename 'Blake2' to 'BLAKE2'

Allow headers to declare a C++ namespace

If the preprocessor symbol `MONOCYPHER_CPP_NAMESPACE` is defined,
the Monocypher headers will be wrapped in a C++ namespace instead of
in `extern "C"`. The name of the namespace is the value of the symbol.

This requires also compiling Monocypher's .c files as C++, either by:
- Using a compiler option like `--x c++`;
- Using an IDE setting, like the Identity & Type inspector in Xcode;
- Putting `#include "monocypher.c" in a C++ file

Added a script that renames the 'crypto_' prefix

Fixes #224

This is not a perfect fix (hard to have one without proper namespaces),
but at least users now an easy way to avoid name clashes.

Fixed Python 3.10 deprecation warning

The randrange function will soon only accept integer arguments,
so I switched to integer division.

Fixed example in HMAC documentation

Spelled libsodium with lowercase

Just conforming to the original documentation.

doc: Argon2 now has an RFC, not just a draft

Inlined ge_r_check()

This saves 9 lines of code.

ge_r_check() was once separated to enhance readability, but it turns out
that inlining it saves more lines of code than expected. The code is
almost more readable now, though the comments are still needed.

EdDSA: parsing public key negate it right away

This saves 2 lines of code, without hurting readability.

ge_frombytes_vartime() does not parse (0, 1)

But that's okay, because that point has low order.

Fixed MSVC warnings

Fixes #215

MSVC doesn't like when we expand unsigned integers after a bitwise
negation.  A fair distaste, except this time it's wrong. Writing
`(~x & 0xffffffff)` instead of just `~x` shows MSVC the error of its ways.

Also made a potentially lossy conversion to `int` explicit (and
explained in a comment why there is no actual loss).

Poly1305: simplified input loading

The trick is to parse the input bytes into words at the last moment.
This simplifies incremental loading, and saves around 10 lines of code.
The performance impact is barely measurable.

Blake2b, Poly1305: fixed undefined behaviour

Caugth by TIS-CI and the latest Clang's UBSan.
Incrementing a NULL pointer, even by a NULL offset, is not permitted.
This was caused by the removal of a conditional that exited early if the
message was empty.
The fix was to move the increment inside the alignment loop.

It may be tiny bit slower, but this was the slow path already.
Users can avoid it by aligning their increments to block boundaries.

Comments: typo & clarification

EdDSA: defined ge_msub() in terms of ge_madd()

Previous changes caused ge_msub() to only be used for signature
verification (it was previously used for signature generation as well,
but this hurted readability).  It thus became reasonable to use
temporary buffers, since we no longer have to wipe them (at a sizeable
performance cost).

The trick is the same as how ge_sub() is defined in terms of ge_add().
This saves 9 lines of code, and the performance cost is negligible.

EdDSA: Inlined fe_sq2()

This function was used only once and was one more function to worry
about with respect to carry propagation.
Plus, inlining it saves 4 lines.

Argon2: Inlined g_copy(), g_xor(), and unary_g()

This saved 16 lines of code. It is not clear how readability is impacted
(the calling code is a bit more complex, but it is also more local).
Overall, I believe it's a win.

Streamlined Blake2b

- Moved   blake2b_incr() inside of blake2b_compress()
- Inlined blake2b_end_block()
- Inlined blake2b_update()

This removed some redundancy and saved 11 lines of code.

Inlined poly_clear_c() and poly_update()

And gained quite a few lines of code in the process.
crypto_poly1305_update() may be a bit clearer as a result.

Rearranged Chacha20 initialisation

The init_key function was too short to justify itself.
It was used only twice, so I inlined it, and saved 2 SLoC.

This also had the effect of making the init code more systematic,
and I believe more readable as well.

Simplified crypto_x25519_dirty_fast()

I noticed a pattern that I didn't exploit optimally.  The current code
is a bit simpler.

Also, I couldn't reverse engineer my own code, so I've expanded the
comments to explain the trick in more detail.

Avoid wiping buffers in two places

More generic fe_frombytes()

This simplifies crypto_hidden_to_curve() a bit

Factored out redundant squaring in Elligator

Merge pull request #213 from fscoto/master+canonical-names

Canonicalize spellings of algorithms

doc: Use canonical spelling of BLAKE2(b)

Spelling according to Jean-Philippe Aumasson, Samuel Neves, Zooko
Wilcox-O’Hearn, Christian Winnerlein. "BLAKE2: Simpler, Smaller, Fast as
MD5." ACNS 2013. Lecture Notes in Computer Science, vol 7954,
and also https://twitter.com/veorq/status/1396728032883322884

doc: Use canonical spelling of ChaCha20

Spelled with two capital Cs according to Daniel J. Bernstein. "ChaCha,
a variant of Salsa20." Workshop Record of SASC 2008: The State of the
Art of Stream Ciphers.

Advertise public key cryptography in the manual

Followup on the modifications of the README: if users can't make the
connection between public key cryptography and key exchange there, they
won't make it either when reading the manual (which by the way is
automatically copied to the website).

Fixed local variable shadowing

In crypto_x25519_inverse(), line 2949 and 2953, we use the ZERO macro in
a context where the enclosing scope already defines the varible `i`.

Turns out ZERO defines `i` for internal use in an enclosed scope. This
trigger a warning in some compilers about variable shadowing: declaring
a local variable with the same name as an enclosing local variable. This
warning is especially annoying when combined with -Werror.

To prevent this, the macros COPY and ZERO have been modified so they use
a variable name that is unlikely to be used anywhere else (`i__`).

Advertise Monocypher's features more clearly

For the second time, I've stumbled upon a user that believed Monocypher
did not support public key cryptography, despite the presence of a
fairly high-level key exchange API.

Looking at the README and website, I noticed that while key exchange is
fairly well publicised, "public key cryptography" is not.  I suspect
many users simply don't know that key exchange is a valid way to do
public key cryptography.  In hindsihght, we should not expected them to.

Let's not dwell on how many potential users we may have lost to this
oversight.  Hopefully, writing "Public key cryptography" directly will
help people notice.

Define fe_invert() in terms of invsqrt()

Pros:
- The code is a couple lines shorter.
- Stack usage may be lowered a tiny little bit (we saved two temporary
  field elements).

Cons:
- Inversion is one field multiplication slower.

Note that fully optimised inversion can be 6 field multiplications
faster than the current version. It would cost quite a bit of code
though (we'd need a dedicated addition chain).

Merge pull request #211 from fscoto/master+doc-incremental

doc: Compute secret/public key in some examples

Install advanced man pages

Note that deprecated man pages are omitted.
I believe we should not clutter man pages with them.
Advanced functions however should have their place in the user manual.

Clarified wording in incremental signatures man page

Thanks Fabio for suggestions on this patch.
(Any error is still mine, though.)

doc: Compute secret/public key in some examples

crypto_sign_init_first_pass(3monocypher) gets two initializations of sk
and pk.
They're long-lived keys, but at least now it's possible to run the
example without wondering why nothing works.

Simplified crypto_x25519_dirty_small() a tiny bit

To give the same results as crypto_x25519_dirty_fast(), we originally
multiplied the cofactor by 5 before we multiplied it by L. I noticed
however that this multiplication by 5 could be baked in the base point
itself, and simplifies the computation a little bit.

This also saves a single MUL instruction.

Expand Blake2b tests to full length keys and hashes

Typo

Test many combinations of input lengths for blake2b

Use official Blake2b test vectors

Should have done this years ago. The test vectors we had were pretty
good, but the official ones are, well, official.

Note that we kept a good deal of our own vectors: while the official
test vectors tested all possible key sizes, they did not test all
possible hash sizes or all possible key sizes.

Added tests vectors for Blake2b

- We tested with no key, and an empty message.
- We tested with no key, and a non-empty message.
- We tested with a key, and a non-empty message.
- We did *not* test with a key and an empty message.

Well, now we do. Libsodium seems to agree with us. Phew.

Speed benchmark: fixed buffer overflow

Argon2i: remove useless intermediate block

Tests suite: fixed C++ compatibility

Updated CHANGELOG

Merge pull request #203 from fscoto/master+chacha20-doc

crypto_ietf_chacha20: note nonce overflow handling

crypto_ietf_chacha20: note nonce overflow handling

IETF ChaCha20 has a 32-bit counter.
This means a practical limit of 256 GiB of data for each nonce.
Additionally, IETF QUIC seems to require being able to handle
0xffffffff (I-D.draft-ietf-quic-tls-33 § 5.4.4),
thus getting very close to the overflow,
though not triggering it.

Unlike libsodium and other libraries, we do not have the option to
panic and take down whatever process is running the code and triggering
the overflow condition because Monocypher is neither allowed to use the C
standard library nor allowed to invoke undefined behavior to cause a
crash;
the applicable RFC provides no guidance what to do in this case, either.

Therefore, staying within the (nonce, counter) limits is necessarily
application responsibility;
it is an invariant that, when voided, Monocypher is allowed to do
anything,
similar to the non-guarantee we make for the crypto_blake2b family
and the crypto_argon2i family.

While already here, fix the wrong function prototype in the synopsis.

Defined IETF Chacha20 in terms of DJB Chacha20

- It's simpler.
- It makes clear that only the initialisation differ.
- It allows us to inline chacha20_core() and gain a few more lines.

Tests: fixed array size mismatch warning

Fix dead store

Fixes #201

Removed spurious comment

Restricted TIS-CI to the most different platforms

We don't care about floating points & such, so we only need to select
a few platforms among all proposed.  This change cuts the number of
platforms by half.

Tweaked EdDSA signature pre-computed table

Moved from a single 5-bit comb to a dual 4-bit comb.  The size of the
comb is unchanged, but we perform fewer operations.

Before:
- 50 doublings, 51 additions (101 operations)
- 51 16-way constant time lookups
After:
- 30 doublings, 62 additions (92 operations)
- 62 8-way constant time lookups

Note: I hoped for a 6% speedup, barely observed 3.5%. I suspect this is
because additions, even from pre-computed tables, cost a little more
than doublings.

Note: we could save an additional addition by assuming scalars modulo L
all fit in 252 bits.  They do not, but if we pick one at random, they
will in practice (with 2^-128 probability of being wrong, i.e. never).

This would work well in EdDSA, where the scalar is a hash of the private
key.  Finding a private key that makes the scalar overflow 252 bits is
about as hard as breaking a 128-bit key, which we can safely assume will
never happen by accident.

However, this scalar multiplication is also used in the dirty public key
generation, which we use to create hidden X25519 keys with Elligator
(from Edwards, because it's twice as fast as the Montgomery ladder).
Here, users provide the scalar directly. Overflowing 252 bits *can*
happen by accident, if users shoot themselves in the foot with a
non-random scalar.

The risk is small, but a measly 1% performance is not worth leaving
ourselves open to subtle corner cases like that.

Faster reduction modulo L

Replaced TweetNaCl's code by Barrett reduction.

- mod_l(), reduce(), and mul_add() use less stack.
- mod_l(), reduce(), and mul_add() are now much faster.
- Signature generation is noticeably faster (~7% on my Skylake laptop).
- Now I understand all the code. No more black boxes.

The change cost a total of 8 lines of code.

Added speed benchmark for ed25519-donna

s/Monocypher/Libsodium in a string

Update CHANGELOG for next version

Remove TIS-CI from the tarball

More uniform TIS-CI file names

Merge pull request #200 from fscoto/master+fix-elligator-comment-typo

elligator.py: fix comment typo

Typos

elligator.py: fix comment typo

Streamlined TIS-CI dirty X25519 test

Moved fe constant with the others

Added test vectors from Kleshni

Fixes #181

The MON-01-004 issue from Cure53's audit noted that Monocypher did not
compare to <https://github.com/Kleshni/Elligator-2>, which I didn't know
of at the time.  Some test vectors were added back then, but full
interoperability was not yet ascertained.  (Moreover, I though I'd added
vectors for the reverse map, and somehow didn't. This is now fixed.)

Now I have been able to generate decoding (direct map) test vectors from
Kleshni's implementation, that Monocypher matches perfectly.  For the
inverse map however, I was not so lucky: Monocypher and Kleshni disagree
on quite a few points, including those used in Kleshni's test vectors.

Some investigation revealed that currently, Kleshni's encoding (inverse
map) is not reliable.  In some cases, the round trip fails to yield the
same point we started with (and it's not just a matter of chopping off
the most significant bit).

However, Monocypher and Kleshni *do* agree on some points, which I have
added (and *checked* I have added) to the list of test vectors.  There's
just one divergence left: Monocypher fails to encode the zero point,
which is a departure from the standard (we're supposed to output the
zero representative instead).

Documented 2^255-19 carry propagation

Fixes #185

Carry propagation is now justified, in a way that I can personally vouch
for (I used to rely on SUPERCOP's ref10 code and proofs).

The use of arithmetic right shifts is also documented, and a workaround
has been devised in case someone somewhere uses a platforms that does
not perform sign extension. (That will never happen.)

Fixed assumption in 2^255-19 carry propagation

Careful re-examination of the carry propagation code revealed that
SUPERCOP's invariants for fe_tobytes() were not respected: there is a
possibility that the inputs slightly outrange the set of input for which
SUPERCOP's original proof was intended.

This happens in invsqrt(), used for EdDSA verification And Elligator,
and the reverse map of Elligator.  X25519 is unaffected.

Note that we were unable to produce a set of input that actually
triggers this range overflow.  Moreover, careful mathematical analysis
(and tests with SAGE) showed that fe_tobytes() is actually much more
tolerant than SUPERCOP's proof let on.  As far as I can tell, this
slight overflow cannot trigger any observable bug.

Still, I figured it would be a good idea to abide those invariants
anyway, if only to facilitate future audits.  To this end, I made sure
the inputs of fe_tobytes() came directly from either multiplications
(which perform a carry propagation), or constants (where carry
propagation has been pre-computed).

TIS-CI: ensure results are correct

Lighter TIS-CI tests

Overhauled TIS-CI test suite