Implement the ECDSA PKC algorithms

[HLRichardson-Git]

Implementation

Follow the FIPS 186-5 standard to implement ECDSA KeyGen, KeyVer, SigGen, SigVer and try to use the same naming convention of functions and variables as in 186-5. Also keep similar documentation as is in the standard.

Make sure you are working withing the constraints of the Message structure at the center of the Gestalt Library, i.e. data, iv, digest, etc are strings, and add algorithm to enum in src/lib.h. New variables in Message may need to be created like a pubKey, priKey, and signature. For your reference here is the current Message struct as of version 0.1:

As of Gestalt v0.2.0, Gestalt has moved from a single include library with a class based front end to a multiple include, function based library. See the v0.2.0 PR for more detail or the changes file.

So when you complete your implementation create a new file under src/ecdsa/ecdsa.cpp, along with any other files you need to implement ECDSA, and a new header in include/gestalt/ecdsa.h where the functions for a user to use ECDSA should be.

Testing

Don't forget to write a new tests/ecdsaTests.cpp file to test your implementation. I suggest following the AES implementation, of implementation structure (i.e. a ECDSA class, and a ECDSA testing friend class), and unit test structure. It will probably be better to first make a few Known Answer Tests, that you can get from here.

Let me know if you have any questions

[HLRichardson-Git]

I spent some time over the weekend trying to figure out a good way to include the GNU Multiple Precision Arithmetic Library (GMP). But it was more challenging than I expected. First I tried to do something similar to how we included the googletest library using the CMake FetchContent feature. But from first glance it doesn't seem like the GMP library is traditionally structured, so it would take more time to understand how it is setup.

I also tried to statically link the library by copying the GMP repo into a new directory external/gmp, but this was not a solution as I it is a more complex library that I can't just include a header for like other simpler libraries. So again this would take more research on my behalf to understand. I should note that this "solution" would be the least ideal in my opinion, as the GMP library is quite large, and would add some 2k+ files to the Gestalt library.

For now I decided to include a smaller library to Multiple Precision Arithmetic called InfInt. It is a simple one include header library, which I can understand. The only thing I fear is that it is not a widely used, tested, and trusted library like the GMP library is. Using this library will also require benching ideally to see how much slower it is to using the GMP library.

If anyone has any ideas on this topic or suggestions to incorporate the GMP library it would be much appreciated.

[HLRichardson-Git]

While looking into what curves I wanted to use for this, I found this database for them which I think will be useful.

https://neuromancer.sk/std/

Click on the little '>' next to the "curves" on the left and you can see what curves are in the database.

[HLRichardson-Git]

I made an initial commit with a bare bones implementation of the ECDSA algorithm here.

There are A LOT of problems with it, like I said this was a bare bones commit (but I think working, maybe, idk), here are just some of the problems:

1. I have integrated a multi precision library like I said in a prior comment here called InfInt. But I have not used it yet in the implementation. I wanted to see if I could get it working with just ints and it seems like I have.
2. It is just kind of expecting a hash as the input. I still am not sure if I want the user to give the message to be signed, or the hash of the message to be signed. I'm thinking the latter as it would give the user more options of what hashing algorithm to use.
3. There are A LOT of error cases that I am not catching. These must be added before this is merged into main.
4. My unit testing is very shallow. I literally coded this in one go and expected it to blow up, so I haven't had a chance to write any unit tests yet. This will probably need to wait till I use InfInt in the implementation.
5. I tried to make some foundation to add more standard ecc curves in src/ecc/eccResources.h, but it didn't work out that nicely and I had to define the test curve in ecdsa.cpp for now. This will have to be looked at so we can define the standard curves. On that point we will also need to implement a way for users to specify which curve they wish to use.

Like I said, this is not all of them, and I will add more concerns as they come up.

[HLRichardson-Git]

Previously I had implemented a lot of the ECC operations like add, multiplying, etc points in the ECDSA class. Now I expanded on ecc.h and created a ecc.cpp in ecc.h I created an ECC class that will be used by the ECDSA class in ecdsa.h and eventually ecdh.h. This will reduce needing to duplicate that functionality between these two implementations.

I also created a new file Gestalt/src/ecc/standardCurves.h which is where the standard curves will be defined. Also implemented a manager that can be used in the future for when a user wants to switch to another curve, to use it though we will need to implement setCurves and getCurves to change curves and see what curve they are using. I didn't do this yet because I honestly wasn't sure if I should just implement that in the ECDSA and ECDH class, or try to do that in the ECC class. But if I did the latter I would still need to make getter functions in ECDSA and ECDH to have a simple use case for users. So I am still contemplating that.

For now, ECDSA is still not working (with the induce failure test, it seems to be sigGen). I will do some debugging sometime soon, probably starting with making some unit cases for the ECC operations to make sure those are working first.

[HLRichardson-Git]

I created unit tests for ECC like I said I would last time, and fixed them so they are now working and passing.

I used online tools:

1. https://andrea.corbellini.name/ecc/interactive/modk-mul.html
2. http://www.christelbach.com/eccalculator.aspx

To compute the KAT tests for ECC algorithms like add, mul, etc. I also ran the ECDSA unit tests, and the sign/verify unit test are still not passing. At least now I know its not the ECC algorithms that are wrong. I think my next step will be to actually use the InfInt library and start using standard curves, and valid values for the algorithm. It could just be that the test curve that I found randomly from somewhere online doesn't work or something. IDK its just a thought.

[HLRichardson-Git]

I totally overlooked having to truncate the hash for sigGen. So I implemented that and to do that I had to create two new utility functions.

• std::string hexToBinary(const std::string& hexStr);
• int binaryToInt(const std::string& binStr);

But as of now without using InfInt, all ECDSA unit tests are passing!

[HLRichardson-Git]

Ah I learned about the cofactor, I noticed this in a few of the standard curves that they had an extra variable called 'h' for instance the Curve25519 has a cofactor `h=8' while P-256 has a cofactor of 'h=1'. This cryptography stack exchange post explains what this is used for well:

• https://crypto.stackexchange.com/questions/56344/what-is-an-elliptic-curve-cofactor

But basically when the cofactor for a curve is not 1, then that means not all points are in the subgroup. Thus we need to implement a way to ensure if a cofactor is not 1 then we need to multiply the point by the cofactor so we can ensure it is.