Click here to Skip to main content
15,127,003 members
Articles / Desktop Programming / Win32
Article
Posted 26 Dec 2007

Stats

148.9K views
8.9K downloads
65 bookmarked

A simple C++ implementation of Elliptic Curve Cryptography

Rate me:
Please Sign up or sign in to vote.
4.92/5 (15 votes)
7 Jan 2008CPOL4 min read
A finite field EC and simple ECC scheme in C++ to help understand the principles.

Introduction

Elliptic Curve Cryptography is an exciting and promising method of encrypting data which achieves the same, or better, strength with far smaller key lengths than traditional encryption methods such as RSA. Elliptic Curves are themselves not rocket science, but the plethora of articles and mathematical background out there do leave it somewhat as "a non-trivial exercise to the causal reader" to actually see how the scheme can be implemented and used. Alas, I for one do not code for a living anymore and hence I always look for compact, to the point, implementations showing with code exactly how something works.

I hope that the source files you download with this article will provide one such source of compact, easy to understand, material to demystify and indeed realize how Elliptic Curves (notice the capitalization here...) can be coded in C++ and used to encrypt and decrypt messages between the ever present Alice and Bob...

Background

Yes, there is plenty of background. Firstly, you should understand the basics of Elliptic Curves, and I have found no better place to learn about them than here: Certicom's EC tutorial. It explains the math behind the ECs, and the important use of ECs over finite fields, i.e., over integers modulo some other integer (usually chosen to be a prime so that the period of any sequence of integers generated by multiplication or addition becomes "long enough").

Secondly, you should probably take some time to think relatively deeply about how finite fields actually work. Finding the inverse of a number in a finite field, for example, is not immediately trivial (unless you do this sort of thing for a living). And, since that is quite fundamental and used quite a lot in the code, I will outline this here:

Given a finite field Fp where p is a prime number (or more specifically a prime power) and a, b are elements of Fp, a is the multiplicative inverse of b if (and only if):

(a * b) mod p == 1

Which makes sense, as (in "real speak") a is the inverse of b if a*b == 1, i.e., a = 1/b.

To find a, given b and p, requires the use of the "Greatest Common Divisor" (GCD) which returns the largest integer less than (or equal to) a (or) and b that divides a and b evenly.

If this integer is 1, then a and b are relative prime, since only 1 can divide them both evenly. Now, given a and b and p, if b (the inverse of which we are looking for) and p are relative prime, then we can find an inverse. This also makes sense since since if b and p are relative prime, you can always write:

b*u + p*v == 1

since GCD(b,p) == 1 only if b and p have this relation. Now, if p is an actual prime number, then b always has an inverse modulo p...

Since pretty much *all* modern encryption schemes use prime numbers and modulo arithmetic one way or the other, it is a Good Thing to learn the basics.

Using the code

I hope the code is pretty much self explanatory. It was developed using DevCpp, MinGW, and GCC version 3.4.2, but has not been tested on other compilers. Although I do like my C++, I have not gone overboard with anything that could cause "ANSI compliance" issues, but please let me know if you find anything.

To get started, go to look at int main(... at the bottom of main.cpp. FiniteFieldElement.hpp is the header file implementing modular arithmetic using normal integers. Warning: I have had to adjust for the modulus of negative numbers, and I assume (since the ANSI standard doesn't explicitly state anything about it) that it could be different on other compilers. Just be forewarned that if something doesn't look right, that could be the reason!

Also: this is implemented using bog standard machine integers, no special big-integer support here.

The example encrypts a message from Alice which is "1972", so if everything is running alright, you should see that Bob's decrypted message reads just that.

Points of interest

Great fun to implement this, in particular when it worked. I encourage anybody to expand on Elliptic Curve implementations to ensure that the understanding and knowledge of these powerful mathematical entities is spread out as much as possible. Security can't be secure enough.

History

First version written over Christmas in the south of not-so-sunny France.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jarl Ostensen
Program Manager Electronic Arts Inc
United Kingdom United Kingdom
Started working for Scala Multimedia Television A/S back in the early 90's and moved on from there to work for Bullfrog Productions Ltd in the UK, later Electronic Arts Inc, where I've stayed since...

Comments and Discussions

 
QuestionCan I run this code in Arduino IDE for arduino uno board? Pin
Ishanka Harshani1-May-20 4:05
MemberIshanka Harshani1-May-20 4:05 
QuestionThanks for your great code ! .How does one encrypt messages larger than the 2-byte Alice > Bob example you provide?? Pin
Member 1172068124-Jul-19 16:28
MemberMember 1172068124-Jul-19 16:28 
QuestionIsn't it strange, that "P += Q = (0, 0)" while point (0, 0) is not belongs to any of group elements? Pin
PiligrimJob1-Mar-18 3:45
MemberPiligrimJob1-Mar-18 3:45 
Thank you for your article and source code!


I have a question.
After I've compiled source code and run it I've got an output to the console window.
Here is a part of it:
(0, 1) (0, 262) (1, 23) (1, 240) (2, 96) (2, 167) 
(3, 89) (3, 174) (4, 73) (4, 190) (6, 111) (6, 152)
...
...
...
some point P  = (1, 23), 2P = (87, 61)
some point Q = (1, 240), P+Q = (0, 0)
P += Q = (0, 0)
P += P = 2P = (87, 61)

The question is following.
Isn't it strange, that "P += Q = (0, 0)" while point (0, 0) is not belongs to any of group elements?


Thank you!
QuestionNeed Algorithm Pin
Prashant211112-Mar-15 21:22
MemberPrashant211112-Mar-15 21:22 
Questionecc implementation in software Pin
Member 1035328123-Oct-13 9:02
MemberMember 1035328123-Oct-13 9:02 
Questionecc Pin
sangamkumar16-May-13 0:01
Membersangamkumar16-May-13 0:01 
GeneralHow to generate random Pin
Krishna Veer17-Jun-12 21:13
MemberKrishna Veer17-Jun-12 21:13 
QuestionBig Endian vs Little Endian Pin
Member 90770115-Jun-12 9:47
MemberMember 90770115-Jun-12 9:47 
Questionbigint? Pin
vixen1623-Feb-11 9:18
Membervixen1623-Feb-11 9:18 
AnswerRe: bigint? Pin
Jarl Ostensen31-Mar-11 7:36
MemberJarl Ostensen31-Mar-11 7:36 
GeneralRe: please help Pin
Jarl Ostensen16-Oct-10 5:46
MemberJarl Ostensen16-Oct-10 5:46 
Generalgreat work sir [modified] Pin
sangamkumar4-Oct-10 20:38
Membersangamkumar4-Oct-10 20:38 
GeneralRe: great work sir Pin
Jarl Ostensen4-Oct-10 23:58
MemberJarl Ostensen4-Oct-10 23:58 
Generalecc Pin
saauuraabh28-May-10 0:08
Membersaauuraabh28-May-10 0:08 
GeneralRe: ecc Pin
Jarl Ostensen29-May-10 1:22
MemberJarl Ostensen29-May-10 1:22 
Generalnotices Pin
adam syria7-Apr-10 4:04
Memberadam syria7-Apr-10 4:04 
GeneralRe: notices Pin
Jarl Ostensen8-Apr-10 2:19
MemberJarl Ostensen8-Apr-10 2:19 
GeneralPlease Help! Pin
HabibVaez22-Nov-09 8:26
MemberHabibVaez22-Nov-09 8:26 
GeneralRe: Please Help! Pin
Jarl Ostensen8-Apr-10 2:15
MemberJarl Ostensen8-Apr-10 2:15 
QuestionC# ECC encrypt/decrypt? Pin
adam syria28-Oct-09 4:34
Memberadam syria28-Oct-09 4:34 
GeneralRe:Help Pin
astra kevin19-Jul-09 22:04
Memberastra kevin19-Jul-09 22:04 
GeneralTo compile with GCC... Pin
Jarl Ostensen2-Apr-09 8:51
MemberJarl Ostensen2-Apr-09 8:51 
GeneralRE: to the point, implementation Pin
k0walski2k31-May-08 9:20
Memberk0walski2k31-May-08 9:20 
GeneralRe: RE: to the point, implementation Pin
Jarl Ostensen8-Jun-08 23:48
MemberJarl Ostensen8-Jun-08 23:48 
GeneralIs it really that secure? [modified] Pin
237419-Jan-08 5:52
Member237419-Jan-08 5:52 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.