2 weeks ago I did a school project on ECDSA (Elliptic Curve Digital Signature Algorithm). At HTX we have to do a project that goes beyond the curriculum, we must combine two subjects and do an individual project about something we find interesting. I decided to combine mathematics and programming in a project about ECDSA. Personally I think it was great fun, but perhaps I have a twisted sense of humor 🙂
Anyway, I’ve publish my report here, it’s in Danish though. But I did also write an implementation of ECDSA in C. The implementation is called SimpleECDSA, though I must admit it not very Simple anymore. It uses GMP as integer library, and uses the standardized curves cryptographic operations.
The comments in my source is in English, though I did translate them to Danish, before delivering my paper. Anyway, I still have the source with English comments, so I thought I’d post the source here.
As I had a little spare time this holiday I’ve configured the source with the GNU build system. It my first tarball created with Autotools, and it’s mostly hacked together of snippets from the automake and autoconf manual. But it works and the package compiles, and “./configure” complains if GMP isn’t present. I did also manage to get “make check” to run my internal tests, so I think it’s pretty good, considering the fact that is my first package build with autotools.
If you’ve any comments, bug-reports or questions to my packaging or SimpleECDSA, feel free to leave a comment. SimpleECDSA is ofcourse released under GNU GPLv3, and can be downloaded here:
I’m doing my graduation project,and find this article by google.Thanks,very useful!
BTW,do u major in cryptography? or just interested in it?
Comment by krisy — May 24, 2008 @ 11:39 am
I’m attending HTX (http://en.wikipedia.org/wiki/Higher_Technical_Examination_Programme_(HTX)) in Denmark. Actually graduating in a few weeks, so I’m just interested and played with cryptography as school project…
But I plan to study computer science next year, so who knows what I’ll get to play with…
Anyway, good luck with your project…
Comment by Jonas Finnemann Jensen — May 24, 2008 @ 4:19 pm
Hi Jonas,
Have you an idea, how many CPU instructions are required to execute your SimpleECDSA?
Best Regards,
Sergey Nemanov
Security System Architect,
Freescale Semiconductor
Comment by Sergey Nemanov — July 9, 2008 @ 4:14 pm
Hi Sergey,
No, I have no idea as to how many CPU instructions it takes… Though SimpleECDSA has some benchmarking features where execution time is measured using functions from time.h
However, I’ve got to say that SimpleECDSA is in no way an efficient implementation… It’s an implementation of ECDSA and it works to the extent that I’ve tested it with various test vectors… There’s still a lot of optimizations that can be applied, both to the code in general and in the sense of alternate algorithms for various calculations based on parameter properties.
Regards Jonas Finnemann Jensen.
Comment by Jonas Finnemann Jensen — July 10, 2008 @ 8:01 pm
I am working on cryptography and my back ground is SIGNAL PROCESSING and COMMUNICATION so i want to work on ECDSA and i want to use your source code so can i get it in C code and in the simpleecdsa gmp.h is not working so can you tell me how i can solve this problem.
thank you
kind regards
welekiros
Comment by welekiros gebrehowot — February 21, 2010 @ 8:29 pm
I just compiled SimpleECDSA on Ubuntu 9.10, so it still works 🙂
You need to install the libgmp3, libgmp3-dev and build-essential packages…
If your distro doesn’t have gmp in it’s package manager you can find it here: http://gmplib.org/
GMP is GNU Multi-Precision Library, it enables integers of arbitrary size… SimpleECDSA needs it…
Let me know if you have an problems building it…
Comment by Jonas Finnemann Jensen — February 21, 2010 @ 11:40 pm
Thank you very much for your fast reply.
to compile it i am using microsoft XP.
Basically i am going to implement it on FPGA using MicroBlaze processor or using EDK so can it be compliled on the xilinix compiler?
thank you
kind regards
welekiros
Comment by welekiros — February 25, 2010 @ 2:05 am
I have never played with FPGA development, so can’t help you there… and I seriously doubt SimpleECDSA can be of much use there…
Comment by Jonas Finnemann Jensen — February 25, 2010 @ 2:35 am
Dear Admin;
it is nothing else it is the C code that i am going to use it on the FPGA not VHDL code as FPGA has microBlaze processor which receive C codes.
thank you
kind regards
welekiros
Comment by welekiros — February 25, 2010 @ 2:46 am
Okay, then you might have a chance if you can get GMP to run on your target…
Comment by Jonas Finnemann Jensen — February 25, 2010 @ 3:45 am
Dear Jonas;
First i need to compile it on the Pc and it will be then on the FPGA so what additional files are required to simpleECDSA to compile it on Ubuntu?
by the way the xilinx compiler have GMP library but i have not used it yet.
Dear jonas can i get C code of ECDSA which can be compiled on windows?
thank you
welekiros
Comment by welekiros — February 25, 2010 @ 8:20 pm
Dear admin;
is it necessary to install libgmp3,limgmp3_dev and essential packages to Ubuntu 9.10?
thank you
kind regards
Comment by welekiros — February 25, 2010 @ 8:42 pm
I’ve never built it on Windows… but you’ll certainly need gmp which can be downloaded from gmplib.org, that is the ONLY extern dependency SimpleECDSA have…
On linux you can build SimpleECDSA using:
$gcc -lgmp -o ./SimpleECDSA ./src/*.c
Where ./src is the source folder of SimpleECDSA…
You can also choose to use ./configure and make, however, plain compiler commands are probably easier on Windows…
You can probably find something about installing gmp in its readme file or manual:
http://gmplib.org/manual-4.3.2/Notes-for-Particular-Systems.html
I my experience compiling C on Windows is rather difficult… But if you figure out how to build gmp for Windows, and what argument to give your compiler in order to link against gmp, SimpleECDSA should be fairly easy to build…
Comment by Jonas Finnemann Jensen — February 25, 2010 @ 11:47 pm
Dear Jonas;
while i use to compile on Linux it gives me the following message: “make[2]*** No rule to make target ‘LICENSE’ needed by ‘all_am’.stop” so what does is it mean?
thank you
Comment by welekiros — February 27, 2010 @ 9:07 pm
Hmm… sounds like autotools complains about bad stuff…
Try this:
http://jopsen.dk/downloads/SimpleECDSA-plainmakefile.tar.gz
It’s a plain make file, just run:
$ make
Then you should get a binary that can run…
Comment by Jonas Finnemann Jensen — February 28, 2010 @ 1:59 am
Dear Jonas;
sorry for being making you tired of this.
i am getting this problem and still i am unable to solve this problem. here is it:
“make all-recursive
make[1]: Entering directory `/home/student/Desktop/simpleECDSA’
Making all in src
make[2]: Entering directory `/home/student/Desktop/simpleECDSA/src’
gcc -lgmp -o ./SimpleECDSA ./src/*.c
gcc: ./src/*.c: No such file or directory
make[2]: *** [build] Error 1
make[2]: Leaving directory `/home/student/Desktop/simpleECDSA/src’
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/home/student/Desktop/simpleECDSA’
make: *** [all] Error 2”
thank you
Comment by welekiros — March 2, 2010 @ 3:40 am
Hmm… Try typing:
$ cd /home/student/Desktop/simpleECDSA/
$ gcc -lgmp -o SimpleECDSA -i src/*.c
That should do…
Then test using:
$ chmod +x SimpleECDSA
$ ./SimpleECDSA –test
Comment by Jonas Finnemann Jensen — March 3, 2010 @ 12:23 am
hello Jonas,
i am just a beginner….for Linux platform. Will Simple ECDSA work using Mathlab framework? Is there a program written for it? (Also can u tell me how do i install Linux(Ubuntu) on WindowsXp?
Is Ubuntu a free software?) Is there a java program for Simple ECDSA,can it run on Windows platform?(Do u know sumthin about Java carts?)
soon reply would be appreciated
thank you
Comment by ace1 — April 15, 2010 @ 10:46 am
@ace1
SimpleECDSA is an implementation of ECDSA in C programming language. SimpleECDSA is NOT a standard, but a toy implementation of ECDSA for educational purposes. Given your questions I’m not sure you understand that…
I recommend reading Wikipedia.org/wiki/Ubuntu for general information on what Ubuntu is…
For how to install Ubuntu on your PC or in a virtual machine under Windows ask on Ubuntuforums.com they are pretty good at helping out…
Comment by Jonas Finnemann Jensen — April 15, 2010 @ 12:30 pm
hello Jonas,
thank you for the quick response! I did install the following packages from the terminal(Ubuntu version 8.3):
libgmp3-dev, build essential packages by using the foll command ->
$root@desktop/home/kjsce# sudo apt-get install libgmp3-dev
$root@desktop/home/kjsce# sudo apt-get install build essential
then after installing packages
i get these messages->
$root@desktop/home/kjsce#
now how i should proceed, given that the folder named SimpleECDSA is stored on the desktop and how do i build the program?
Also i cant find gcc as the source path anywhere? plz help
where do i write the cmd->
$gcc -lgmp -o ./SimpleECDSA ./src/*.c
Comment by ace1 — April 16, 2010 @ 8:27 am
$root@desktop/home/kjsce#
is the command line… where you type commands… Not a message…
Learn to use a terminal and write a hello world program in C if you haven’t done that before…
There is plenty of C and terminal tutorials online, just google it…
You download the archive above, all you need to do is to extract it, open a terminal and navigate to it in the terminal… Then configure it using ./configure and build it using make
Alternately you can run gcc -lgmp -o ./SimpleECDSA ./src/*.c in the terminal, when you have extracted in the sources and changed directory to these sources…
By the way, there’s no Ubuntu 8.3 and “build essential” is written with a dash, e.g. “build-essential”…
Comment by Jonas Finnemann Jensen — April 17, 2010 @ 2:01 am
hello Jonas,
i am extremely sorry for interrupting you again.
i have downloaded the foll: libgmp3c2, libgmp3-dev, build-essential.
i hav saved the program: Filesystem->home->kjsce->desktop->simpleecdsa-1.0.0
i tried building the program in terminal:
kjsce@kjsce-desktop-22:~$ cd Desktop
kjsce@kjsce-desktop-22:~/Desktop$ cd simpleecdsa-1.0.0
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ cd src
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0/src$ cc *.c
after compiling, i am gettingfoll errors:
/tmp/ccmDmahe.o: In function `benchmark’:
benchmark.c:(.text+0x87): undefined reference to `__gmpz_init’
… Lots of undefined references (removed by Jonas for readability) …
test.c:(.text+0xce0): undefined reference to `__gmpz_clear’
/tmp/ccFgGuQ4.o:test.c:(.text+0xceb): more undefined references to `__gmpz_clear’ follow
collect2: ld returned 1 exit status
*—————————————————*
//Ubuntu version (8.04)
Will the packages that i hav downloaded satisfy the program?
and where do i store the packages or how do i retrieve them since i hav downloaded packages from internet?
Plz help.
thank you!!!!!!!
Comment by ace1 — April 17, 2010 @ 3:23 am
Okay, seems like you’re getting the picture, you only need to link against gmp now… Pass the -lgmp argument to the compiler…
E.g:
$ cd Desktop/simpleecdsa-1.0.0
$ gcc -lgmp src/*.c -o SimpleECDSA
That should compile it, then don’t forget to give it executable rights by running:
$ chmod +x SimpleECDSA
Alternately you can build it using autotools, just write:
$ cd Desktop/simpleecdsa-1.0.0
$ ./configure
$ make
And you that should be it… This is usually how you compile tarballs you download from random places… 🙂
Comment by Jonas Finnemann Jensen — April 17, 2010 @ 3:37 am
hello Jonas, thank you very much for the quick reply. I hav tried the following steps: and i got these errors>>>.plz help:
kjsce@kjsce-desktop-22:~$ cd Desktop
kjsce@kjsce-desktop-22:~/Desktop$ cd simpleecdsa-1.0.0
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ gcc -lgmp src/*.c -o SimplECDSA
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ chmod +x SimplECDSA
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -test
./SimplECDSA: Missing arguments.
Try ‘./SimplECDSA –help’ for further information.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$
Alternately, i tried this command also:
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./configure
bash: ./configure: /bin/sh^M: bad interpreter: No such file or directory
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ make
make: *** No targets specified and no makefile found. Stop.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$
Plz help.
Thanking you, awaiting response.
Comment by ace1 — April 18, 2010 @ 11:13 pm
i hav downloaded the following packages:
libgmp3c2, libgmp3-dev & build-essential packages.
I am unable to get libgmp3 package. So wat should i do?
Do i need to save the packages into the same folder ie (simpleecdsa-1.0.0) for linking?
Comment by ace1 — April 18, 2010 @ 11:20 pm
You did compile SimpleECDSA, so no need to try the alternate method…
try:
$ ./SimpleECDSA –help
$ ./SimpleECDSA –test
Or some of the other arguments. “-test” is not a correct argument, “-t” or “–test” is…
That’s it… if you want to know how it works I’d recommend Wikipedia and Handbook of Applied Cryptography, which can be found here:
http://www.cacr.math.uwaterloo.ca/hac/
Of course you can also read the source…
Comment by Jonas Finnemann Jensen — April 18, 2010 @ 11:33 pm
hello Jonas, thanks again for the quick reply.
I’m not able to understand the actual working of the program.
Please explain conceptually the working of the program and the commands used for it……..
I’m actually working for it as my college project.
And I got to show this prototype this week.
Please help!!!!!!
I hav tried the following steps:
kjsce@kjsce-desktop-22:~$ cd desktop
bash: cd: desktop: No such file or directory
kjsce@kjsce-desktop-22:~$ cd Desktop
kjsce@kjsce-desktop-22:~/Desktop$ ./SimplECDSA
bash: ./SimplECDSA: No such file or directory
kjsce@kjsce-desktop-22:~/Desktop$ cd simpleecdsa-1.0.0
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA
./SimplECDSA: Missing arguments.
Try ‘./SimplECDSA –help’ for further information.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –test
./SimplECDSA: Missing arguments.
Try ‘./SimplECDSA –help’ for further information.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –help
Usage: ./SimplECDSA [options]
Generate public key, sign and verify messages using the elliptic curve digital signature algorithm.
Commands:
-g [key] –generate [key] Generate public key
-s [key] –sign [key] Sign a message
–verify [key] Verify signature
-b [key] –benchmark [i] Run a benchmark
-t –test Run all tests
–test-generate Test public key generation
–test-verify Test signature verification
–test-compression Test point compression
–test-numbertheory Test point compression
–test-self Run self test
–crack [key] Try to crack a public key
-v –version Display version information
-h –help Display help.
Options:
-c –curve Curve [0-12], defaults to DEFAULT_CURVE = 3
-I –input Input file, defaults to stdin
-O –output Output file, defaults to stdout
-q –quite Quite mode
Return values:
0 Operation performed successfully
1 Verification or test failed, program ended without failure
2 File IO failure, see stderr
3 Out of memory error
4 Internal inconsistency
5 Not implemented yet
SimpleECDSA is a simple implementation of ECDSA, it’s NOT designed to solve security issues. It’s an educational toy, designed to play with performance and implementation issue of ECDSA.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g
Private key:
14
Public key:
0250b7d72699e59392753e3bd51be4556d47e8b952
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -s
Private key:
13
Message:
Hi Vijayshree
Hi
14
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -t
— Test public key generation —
Test completed successfully.
— Test signature verification —
Test completed successfully.
— Test algothrim integrity —
Test completed successfully.
— Test point compression —
secp112r1: Ok
secp128r1: Ok
secp160k1: Ok
secp160r1: Ok
secp160r2: Ok
secp192k1: Ok
secp192r1: Ok
secp224k1: Ok
secp224r1: Ok
secp256k1: Ok
secp256r1: Ok
secp384r1: Ok
secp521r1: Ok
Test completed successfully.
— Test number theory —
Modular explonentiation: Ok
Squaring modulo prime: Ok
Extended euclidean algorithm: Ok
Legendre symbol test: Ok
Number theory tests successfully completed 500 times.
All Test successfully completed in 1.2300 seconds.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g
Private key:
14
Public key:
0250b7d72699e59392753e3bd51be4556d47e8b952
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g -c
Private key:
4
Public key:
03b2e772a7ea91e88c1d6ea454de57aa19b5258bd1
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g
Private key:
4
Public key:
03b2e772a7ea91e88c1d6ea454de57aa19b5258bd1
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -v
./SimplECDSA (SimpleECDSA) 1.0.0
Copyright (C) 2007 Jonas F. Jensen.
This is free software. You may redistribute copies of it under the terms of
the GNU General Public License .
There is NO WARRANTY, to the extent permitted by law.
Written by Jonas F. Jensen .
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g
Private key:
7
Public key:
0270c95c6f287f2a5f9d971ffa82464b5885a9cd7b
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –test-generate
— Test public key generation —
Test completed successfully.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -I
./SimplECDSA: Missing arguments.
Try ‘./SimplECDSA –help’ for further information.
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g -I
Private key:
4
Public key:
03b2e772a7ea91e88c1d6ea454de57aa19b5258bd1
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g -O
Private key:
4
Public key:
03b2e772a7ea91e88c1d6ea454de57aa19b5258bd1
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –crack
Public key:
5
WARNING: You are running a brute force attack on the elliptic curve discrete logarithm problem. This might take a minor eternity, press ctrl+c to abort.
Factors checked: 91100
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g
Private key:
4
Public key:
03b2e772a7ea91e88c1d6ea454de57aa19b5258bd1
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –crack
Public key:
4
WARNING: You are running a brute force attack on the elliptic curve discrete logarithm problem. This might take a minor eternity, press ctrl+c to abort.
Factors checked: 72258
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -g
Private key:
4
Public key:
03b2e772a7ea91e88c1d6ea454de57aa19b5258bd1
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA -s
Private key:
4
Message:
Hi Vijayshree
hi kiran
hi rupalika
–verify
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –verify
Public key:
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –verify
Public key:
03b2e772a7ea91e88c1d6ea454de57aa19b5258bd1
Message:
hi
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$ ./SimplECDSA –verify
Public key:
4
Message:
Hi Vijayshree
hi kiran
hi rupalika
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$
kjsce@kjsce-desktop-22:~/Desktop/simpleecdsa-1.0.0$
Comment by ace1 — April 19, 2010 @ 11:51 pm
I honestly don’t remember how it works… I wrote this program as a highschool, 3 years ago… 🙂
I suggest you read the source, it has lots of comments…
But if you don’t use -I and -O parameters to specify input and output file…You will need to type CTRL+D twice inorder to stop typing data in…
I’d suggest that you learn to use a terminal if you don’t know how to pass arguments to programs.
Comment by Jonas Finnemann Jensen — April 20, 2010 @ 1:03 am
Hello Jonas,
We are very thankful for your patience and support in helping us out with the implementation. Finally, we are through with it. We hope for the future help also!
😉
Regards,
ace1 & group
Comment by ace1 — April 20, 2010 @ 3:17 am
hello Jonas,
i have chosen cryptography as the base for my project. i would like to know applications of cryptography. i mean… how can we use the ECDSA algorithms for real world applications?
Comment by maxtin — August 1, 2010 @ 11:13 am
@maxtin
Asymmetric key algorithms, such as ECDSA, are used many in places today. Whenever you need secure communication without use of shared secrets, algorithms such as ECDSA or RSA are used.
Asymmetric key algorithms are widely used for digital signatures, secure email (GPG) and secure internet (HTTPS).
Take a look at: http://en.wikipedia.org/wiki/Public-key_cryptography
Comment by Jonas Finnemann Jensen — August 2, 2010 @ 4:23 am
thank you Sir..
Comment by maxtin — August 11, 2010 @ 10:24 am
Hi Welekiros,
Were you able to use this code on FPGA? I am planning to implement the same on FPGA, I got it to work on ubuntu using terminal, though I would like to use it on FPGA,as I need to implement Signature generation and verification using ECC. I have the ECC module, but would like to know in case if this code can be helpful rather than re-inventing the wheel.Please let me know.
Comment by Hetal — October 3, 2010 @ 12:29 pm
Hi,
I tried to run your code on Windows XP(Turbo C++) but its not working.The program says that it is unable to open the header file “domain_parameters.h” .There are other syntactical errors too.Can you please help?
Comment by Amrita Datta Gupta — November 20, 2010 @ 9:52 pm
I haven’t used Turbo C++, but it might be possible. Anyway, this is written in C…
So you might want to try with mingw (a GCC port), if you download CodeBlocks, you’ll also get mingw with it.
If that doesn’t work, send me an email with more details, maybe I’ll have a clue (you can find my email on the “about page”).
Comment by Jonas Finnemann Jensen — November 21, 2010 @ 8:36 am
hai sir, i am doing my final year IT and i am doing my project(MABS IN MOBILE COMPUTING) i need coding for ECDSA in C# in DOTNET with expianation.plz help me for my project
Comment by james — March 22, 2011 @ 9:27 pm
Hi James,
There should be a big integer in .Net 4.0, otherwise you can easily find another integer library for .Net…
I would recommend that you read wikipedia about ECDSA and take a look at Handbook of Applied Cryptography for pseudo code (http://www.cacr.math.uwaterloo.ca/hac/).
You can also look at my source, an either use that as reference or look at the references it has to Handbook of Applied Cryptography…
If you have any concrete questions you’re also welcome to contact me… Best of luck with your project…
By the way, if you decide to release the source for your implementation, feel free to drop a link here, so others interested in it may find it…
Comment by Jonas Finnemann Jensen — March 23, 2011 @ 12:01 am
Sir,
i tried running your code in gcc.but i cudn understand 2 thngs.
1.the order in which the codes r to b run.as in which file to b run before which one.
2.mpz_t is giving some errors.does it need a header(mpz_t has bn used in domain_parameters.h and other files too)
Comment by Prithviraj Gupta — April 6, 2011 @ 12:50 pm
sir,
the customised headers are more or less working(.h files).but when i tried to run domain_parameters.c the following error resulted.can u pls help!!
$ gcc domain_parameters.c
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x1f): undefined reference to `__imp_
___gmpz_init’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x2f): undefined reference to `__imp_
___gmpz_init’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x3f): undefined reference to `__imp_
___gmpz_init’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x46): undefined reference to `_point
_init’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x5c): undefined reference to `__imp_
___gmpz_init’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x6c): undefined reference to `__imp_
___gmpz_init’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0xed): undefined reference to `__imp_
___gmpz_set_ui’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x104): undefined reference to `__imp
____gmpz_set_ui’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x11b): undefined reference to `__imp
____gmpz_set_ui’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x139): undefined reference to `_poin
t_set_ui’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x14e): undefined reference to `__imp
____gmpz_set_ui’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x165): undefined reference to `__imp
____gmpz_set_ui’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x19e): undefined reference to `__imp
____gmpz_set_str’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x1bd): undefined reference to `__imp
____gmpz_set_str’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x1dc): undefined reference to `__imp
____gmpz_set_str’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x1fa): undefined reference to `_poin
t_set_hex’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x217): undefined reference to `__imp
____gmpz_set_str’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x236): undefined reference to `__imp
____gmpz_set_str’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x24e): undefined reference to `__imp
____gmpz_clear’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x25e): undefined reference to `__imp
____gmpz_clear’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x26e): undefined reference to `__imp
____gmpz_clear’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x27e): undefined reference to `_poin
t_clear’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x28c): undefined reference to `__imp
____gmpz_clear’
/tmp/ccATeIwp.o:domain_parameters.c:(.text+0x29c): undefined reference to `__imp
____gmpz_clear’
/usr/lib/gcc/i686-pc-cygwin/4.3.4/../../../libcygwin.a(libcmain.o):(.text+0xa9):
undefined reference to `_WinMain@16′
collect2: ld returned 1 exit status
Comment by Prithviraj Gupta — April 6, 2011 @ 1:13 pm
@Prithviraj,
There’s no need to modify the headers…
SimpleECDSA depends upon GMP, see http://gmplib.org/
You’ll need to link against this, with:
$ gcc -lgmp *.c -o SimpleECDSA
Comment by Jonas Finnemann Jensen — April 6, 2011 @ 11:57 pm
the header problem is to some extent solved but i cant understand the error that arrived which i wrote in my last post.can u pls help!
Comment by Prithviraj Gupta — April 7, 2011 @ 4:45 am
You need to link against GMP…
See: http://gmplib.org/manual/Headers-and-Libraries.html#index-Linking-144
Comment by Jonas Finnemann Jensen — April 7, 2011 @ 5:14 am
can u please explain the implementation by taking a simple curve as example. I have to code the simple example in matlab pls pls help me….thanku
Comment by mounesh — May 21, 2012 @ 6:27 am
@mounesh,
It’s been about 5 years since I did this project, so I’m not sure I can easily improvise an example 🙁
I would need to refresh a lot about ECDSA, but I suppose it could be a fun exercise one day (just no today, I have a project due in 4 days, followed by exams).
Anyways, the implementation is well documented with a comment for almost every statement. And all the statements are written three-address code using GMP to do big int operations. So the SimpleECDSA sources gives you all the excruciatingly painful details of the implementation. I suppose that might be helpful.
If you’re looking for an introduction to ECDSA, I suggest you read one of the tutorials around, google suggests:
http://www.dkrypt.com/home/ecc
(But I’m sure there’s lots of other good sources out there too).
By the way, a lot of the algorithms used for computing legendre symbol, square roots under modulo, etc. can be found in the “Handbook of Applied Cryptography”, which can be downloaded here:
http://cacr.uwaterloo.ca/hac/
(It doesn’t cover ECDSA explicitly, but many of the required subroutines are covered).
– Good luck with your project…
Comment by Jonas Finnemann Jensen — May 21, 2012 @ 12:09 pm
Hello.
Can you tell me if we can test a simple example ALice and Bob in your application?
what I mean is.
Create a Public key, sign a messagem, and decrypt it to get the plain text back.
Because in your program you verify the message but you never output it again.
Thanks
Best Regards
Comment by Daniel — October 21, 2012 @ 11:05 pm
@Daniel,
ECDSA is a Digital Signature Algorithm. The signature doesn’t contain the entire message. The signature only contains SHA1 hash of the message.
To answer your question, you can create a public key, sign a message and verify the signature with SimpleECDSA.
But SimpleECDSA will not output the message, as you must input the message to verify the associated signature.
Comment by jonasfj — October 22, 2012 @ 9:12 am
Ok, thanks for the quick answer.
But is there anyway that I can make another function so that I can make that kind of verification ?
to decrypt the sign message and get the message in plain text?
Thanks
Comment by Daniel — October 22, 2012 @ 4:20 pm
@Daniel,
To verify a signature, you take an SHA1 hash of the message, public key, signature and curve parameters and use these to verify that the signature was generated with the associated private key.
When you use the term “decrypt”, I fear you might have misunderstood the concept of a digital signature algorithm.
You don’t “decrypt” the “sign message” (signature), it’s verified.
See signature.c: signature_verify().
I suppose one could print and visually verify that x->x is equal to sig->r (one of the two number making up the signature).
Comment by jonasfj — October 22, 2012 @ 6:46 pm
Yes I misunderstood the concept:s sorry for that.
I will have to implement the ECDSA in FPGA, but I also need to know the bottleneck of the software inplementations.
Did you use the Montgomery algorithm for the modular arithmetic?
Thanks
Best Regards
Comment by Daniel — October 22, 2012 @ 10:27 pm
@Daniel,
SimpleECDSA uses libgmp for modular arithmetics.
So all the low-level arithmetic operations are not implemented in SimpleECDSA.
As far as I know libgmp implements different algorithms depending on the size of the operands, underlying processor, etc.
It’s been a while since I wrote the software, so can’t tell you what the bottlenecks are.
I’d imagine that exponentiation, involving modular multiplication, is one of the heavy things.
Comment by jonasfj — October 23, 2012 @ 7:38 am
@jonasfj
Thanks for your answers.
I just would like to ask you, why do you call your implementation SimpleECDSA? does it misses something?
what are the curves that can be used? can I use the NIST curves ecdsa_nistp224 e ecdsa_nistp256
In the help what are the curve[0-12] that you specify?
Sorry for all these questions.
Thanks
Best regards
Comment by Daniel — October 30, 2012 @ 1:49 pm
@Daniel,
I don’t there anything significant missing. But it needed a name and it was “simple” ie. for educational purposes.
However, I don’t remember if message padding, formatting, etc. is done as specified in any standard, if there was any at the time.
So it probably needs a hack before the signatures can be verified elsewhere.
I don’t think NIST curves (FIPS 186-3) were published when I did this project. So it features the SECP-2 curves. But a quick look at the standard suggests that NIST P-224 is the same as SECP-224r1.
Anyway, curves are described in the source, take a look at curves.h and curves.c, to see what curves the numbers refers to.
As you can see it is also fairly trivial to add new curves, just make sure to use HEX encoding.
tip: To convert large decimals to hex use a python terminal 🙂
Regards Jonas Finnemann Jensen.
Comment by jonasfj — October 30, 2012 @ 2:14 pm
Ok, thanks.
I have checked the curves.c and I see the multiple curves defined. I just know don’t understand how these values appear. Do you have reference that I can understand how these values and what they mean in a easy way ?
Also I was checking the SHA-1 and you say in the commments that it outputs 160bit. But as far as I know some curves use sha with more bits, in case of NIST p224, it also uses 224bit SHA.
In the end you also use padding, this means that in case that in case that we need a 224bit SHA we would fill the 224bit SHA with zeros and then the 160bit SHA?
Sorry for all these questions, but I am trying to learn how this really works:s
Thanks
Best Regards
Comment by Daniel — October 31, 2012 @ 2:45 pm
The SEC curves are recommended in
http://www.secg.org/collateral/sec2_final.pdf
If you want to learn what the parameters mean and how ECDSA works, take a look at:
http://www.dkrypt.com/home/ecc
As well as some of the other resources recommended in the comments here.
A 160bit integer is also a 224bit integer, so yeah zero padding. There are standards for message and hash padding and formatting, but these are not necessary in a “simple” implementation 🙂
Comment by jonasfj — October 31, 2012 @ 5:03 pm
So what you mean is that the hash numbers over 160bits are not within the standards, because what you do when you need a sha bigger than 160bit is that you you the 0 padding right?
Also what this means is that the secp224r1 which needs a 224 SHA, is not according to the standard because it has 224bit but actually it’s 160bit SHA and zeros ? I am right?
And the 8 octet at the end which are 64bits, why are you getting them are for what purpose?
Thanks:)
I am printing the materials you sent me to read and understand more about it:)
Best Regards
Comment by Daniel — October 31, 2012 @ 5:42 pm
So if you want to learn ECDSA, don’t worry about standards. SimpleECDSA doesn’t follow any specific standard, it might take some inspiration.
The recommended curves from NIST and/or SEC are useful to have something fairly real. But message padding and hashing is quite boring if trying to learn ECDSA.
FYI, 224 bit SHA doesn’t exist. Bigger curve offers better security, even if the hash is of less bit.
Or you choose a different hash algorithm, as long as the same hash is used for signature generation and verification, things will be fine.
Comment by jonasfj — October 31, 2012 @ 5:57 pm
Ok,
The reason why I was asking was because I have to work with this in my project, to benchmark it on a raspberry pie and then do ECDSA in hardware. But the implementation I have to test is a ECDSA implementation with the NIST p224 and p256. As far as I got it the hashing for these too curves is respectively 224 and 256 bits, so that was why I was asking.
But I was checking and I think this uses SHA-1 with 160bit, with padding to the 224 or 256.
Thanks once more for all your time:)
Hope you don’t mind that I can come with some more questions:s
Comment by Daniel — October 31, 2012 @ 7:14 pm
ECDSA on raspberry pie sounds like an awesome idea. Please do a blog post about your results and post a link here 🙂
Anyways, best of luck with your project 🙂
Comment by jonasfj — November 2, 2012 @ 9:05 am
There is an error in the file signature.c. Specifically, in lines 139-141 the operator && is used but the operator || should be used instead.
Comment by Chris Dupilka — November 6, 2012 @ 5:08 pm
@Jonasfj
I have been reading some more stuff about ecdsa, and right now I am concerned about the key pair generation.
As far as I understand, I need to generate the keypair (r,s) public and private key.
This public and private key need to be related with the curve I choose to use right? And the prime numbers that need to be randomly generated need to be points on the chosen curve?
I am trying to understand this but maybe you can clarify my idea:)
Thanks
Best Regards
Comment by Daniel — November 13, 2012 @ 10:23 pm
@Daniel,
I don’t remember all the details anymore… But AFAIK, you can just pick any random number as private key and generate a corresponding public key.
I don’t think any of them have to be prime, that’s RSA you’re talking about.
The prime number needed for the field under which the elliptic curve exists should be part of the curve parameters.
But for details on ECDSA operations, I’d suggest reading a resource that explains this in detail. There’s lots around…
Comment by jonasfj — November 15, 2012 @ 11:35 am
@Chris,
Thanks for the bug report, I’ll be sure to fix it if I ever get around to pushing this code to github…
Comment by jonasfj — November 15, 2012 @ 2:08 pm
Hello,
I am getting errors while compiling code in ubuntu 12.10?
From where to download GMP PACKAGES?? and how to link it with programme??I am not getting what you said….
Please help me !!!
Comment by Swiss — September 12, 2013 @ 8:35 am
@Swiss,
GMP is the GNU Multi-Precision arithmetic library, project website: http://gmplib.org/
But it’s readily available on most platforms, for ubuntu/debian:
$ sudo apt-get install libgmp-dev
After that it’s just
$ ./configure
$ make
$ cd src/
$ ./SimpleECDSA –help
Have fun 🙂
Comment by jonasfj — September 12, 2013 @ 9:59 am
Hello,
You told about GMP but i am not getting what should i do and how to link this header file with programe?
gcc -lgmp -o ./SimpleECDSA ./src/*.c
./src/benchmark.c:1:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/curves.c:1:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/domain_parameters.c:1:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/main.c:1:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/numbertheory.c:3:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/point.c:3:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/random.c:3:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/signature.c:3:17: fatal error: gmp.h: No such file or directory
compilation terminated.
./src/test.c:3:17: fatal error: gmp.h: No such file or directory
compilation terminated.
make: *** [build] Error 1
Comment by swiss — September 12, 2013 @ 12:28 pm
@Swiss,
Nothing… usually 🙂 “gcc -lgmp …” will link with libgmp.so.xx as installed on your system.
Note: you don’t link with the header files, include headers.
The “gmp.h” header should be installed in /usr/include/ which is the default search path for header files.
So the command you typed should work, did you install libgmp-dev?
You need libgmp-dev and not just libgmp10, as libgmp-dev includes headers etc. necessary to build against the library and not just use it.
Note, I’d strongly recommend that you install GMP from package manager, and not from sources downloaded from gmplib.org.
Using the package manager will put headers and binaries in the right folders, which is a true joy 🙂
Comment by jonasfj — September 12, 2013 @ 1:54 pm
Hi Sir,
I am pleased with your contribution in developing the simple ECDSA. As per your guidance I have installed gmp.h library. But still I am getting problem running the ECDSA algorithm. Can you please help me how to run the ECDSA program. Please help me solving the problem.
Waiting eagerly for your reply.
Comment by SMITH KHARE — October 10, 2014 @ 11:11 am
hi sir,
I am eagerly waiting for your reply i have posted above. I have configure and tested but the making of file shows the error. Can you please help me out solving the problem. I have to show the result to the evaluators so can you please help me out with the problem. Sorry if my comments bothers and disturbs you. but i need it badly.
Thanks and regards
Comment by SMITH KHARE — October 11, 2014 @ 11:19 am
@smith Khare,
Sorry about the moderation delay..
Things have been piling up in my inbox recently…
Anyways, if compilation was successful. Try running it with –help, that should give you an idea of the commands. You should note that when entering multi-line messages you’ll need to terminate it with CTRL+D. Assuming you’re using a common terminal emulator.
Comment by jonasfj — October 14, 2014 @ 10:07 pm
@jonas
thanks for your reply.
i don’t know how to give input.
messages i am giving are not verifying i guess. i have given messages but how to deal with public key and private key is getting it difficult.
Comment by SMITH KHARE — October 14, 2014 @ 10:32 pm
When I give the command SimpleECDSA –verify im getting the following error:
*** glibc detected *** ./SimpleECDSA: free(): invalid next size (fast): 0x0000000000dcd3a0 ***
Segmentation fault (core dumped)
what does this mean ??
Comment by preethi — March 9, 2015 @ 4:11 am
@preethi,
My guess is that you need to check that all parameters are given. I don’t remember the command interface anymore.
Comment by jonasfj — March 12, 2015 @ 5:47 pm
SIR, please provide me the same code in java…
thank you sir
Comment by divya — April 9, 2016 @ 7:32 pm
> SIR, please provide me the same code in java…
Wow.. Not to be rude, but I don’t work you.
If you want to learn ECDSA there is a lot of resources out there:
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
https://www.certicom.com/index.php/ecc-tutorial
If you want a Java implementation, go find one, I’m sure there is a few implementations out there.
Just google “ECDSA Java”, have fun.
Comment by jonasfj — April 10, 2016 @ 6:33 pm