see comments starting at https://bugs.libre-soc.org/show_bug.cgi?id=773#c1

if you want a known-good library to test against, you can use
python3-cryptography, which uses openssl internally, and is available in debian buster (you will want that rather than installing it through pip). iirc, one or more of our repos has it as a dependency somewhere, icr for sure.

https://cryptography.io/en/latest/hazmat/primitives/asymmetric/ed25519/

(In reply to Jacob Lifshay from comment #2)
> if you want a known-good library to test against, you can use
> python3-cryptography, which uses openssl internally,

no. absolutely not. that, when added to the unit tests,
becomes *yet another* dependency, including openssl.

cryptography has a de-facto standard way of dealing with this problem for
30+ years: the author of the algorithm *provides a reference implementation*
and in that reference implementation are included some "known examples".

given that the probability of being wrong even when running just one
single example is (2^128-1) / (2^128) for a 128-bit algorithm and
(2^256-1) / (2^256) for a 256-bit one it is an absolute no-brainer
to justify "success" on the basis of passing *even one* of the "known examples"
provided by a c reference implementation.  run two well-known examples
and that becomes a probability of (2^128-1)^2 / (2^128)^2

please *do not* add yet more software dependencies when it is
very simple to just find (and copy verbatim) the source code of
the reference implementation and drop it straight into the
crypto/ directory, exactly as konstantinos has *already done*
with chacha20:

    https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=crypto/chacha20/src/test.c;hb=HEAD

please let konstantinos get on with this task uninterrupted, and help review
when he has made commits.

(In reply to Luke Kenneth Casson Leighton from comment #3)
> given that the probability of being wrong even when running just one
> single example is (2^128-1) / (2^128) for a 128-bit algorithm and
> (2^256-1) / (2^256) for a 256-bit one it is an absolute no-brainer
> to justify "success" on the basis of passing *even one* of the "known
> examples"
> provided by a c reference implementation.  run two well-known examples
> and that becomes a probability of (2^128-1)^2 / (2^128)^2

that assumes the crypto primitive was implemented correctly, the probability is much higher than that that the primitive is wrong for only some inputs.

e.g. AES-128 uses at most 160 of the 256 S-box entries for any one encryption (each round has 16 S-box accesses, there are 10 rounds), so, assuming those are randomly distributed, for 2 AES-128 encryptions, only about 183 S-box entries are ever accessed, so if you have one wrong, you have about a 72% percent chance of detecting that.

my code:
import random
def count_accessed(c):
    sbox = [False] * 256
    for _ in range(c):
        sbox[random.randrange(256)] = True
    return sum(sbox)
def wrong_accessed(c, w):
    for _ in range(c):
        if random.randrange(256) < w:
            return True
    return False
# average number of S-box entries accessed for 2 encryptions:
c = 10000; print(sum(count_accessed(160*2) for _ in range(c)) / c)
# probability one wrong S-box entry will be accessed for 2 encryptions:
c = 10000; print(sum(wrong_accessed(160*2, 1) for _ in range(c)) / c)

(In reply to Jacob Lifshay from comment #4)

> that assumes the crypto primitive was implemented correctly, the probability
> is much higher than that that the primitive is wrong for only some inputs.

jacob! please do not interfere! Konstantinos has this covered and you are
distracting him. i will not warn you again.

https://libre-soc.org/irclog/%23libre-soc.2023-09-14.log.html#t2023-09-14T10:45:15

konstantinos it is only necessary to run one test (or two) - those of the
reference implementation's "known-good" values - just like with chacha20.

it was and will always remain completely unnecessary to run for 49 minutes,
the absolute maximum should be 3-5 minutes and even that is pushing it.

could you also take the opportunity to remove the dependency on openssl, cutting
back to the absolute bare-minimum stand-alone unit test, just like with
chacha20?

the project's requirements are that openpower-isa dependencies are kept to the
absolute minimum (gtest was a sensible strategic addition), and openssl as a
hard requirement is simply far too large and in this case unnecessary and
unjustifiable.

i appreciate that there is a desire to run the unit tests "as-is", however
it is well beyond the scope of what is required: a *stand-alone* and
bare-minimum demonstration

OpenSSL can be actually be removed easily, by using the builtin SHA512 hash function. Already fixed and will commit asap. That's the easy part.
Regarding the tests, I'm going to implement smaller unit tests for the curve/ed25519 code and have already started preparing a separate unit test that will do just a single iteration. This will still take a long time -no way this is going to end in 3-5 minutes, but at least it will be a complete demonstration of SVP64 implementation ed25519.

(In reply to Konstantinos Margaritis (markos) from comment #7)
> OpenSSL can be actually be removed easily, by using the builtin SHA512 hash
> function. Already fixed and will commit asap. That's the easy part.

fantastic (cf: git commit)
https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=8d1160cf5

> Regarding the tests, I'm going to implement smaller unit tests for the
> curve/ed25519 code and have already started preparing a separate unit test
> that will do just a single iteration.

brilliant. btw once we have the mdwn-to-c compiler in place and the
c-based decoder it becomes possibe to wrap those in python and
dramatically speed up ISACaller.

adding test function for curve25519_mul using barrett reduction / carry-save

https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=8051365d9b8c

working version of python curve25519_mul

https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=de10b86f7b3