/*
Example implementation of an Elliptic Curve over a Finite Field
By Jarl Ostensen, December 2007
jarl.ostensen@gmail.com
I wrote this because I wanted to understand more about Elliptic Curves and how they are
used in cryoptography. There's plenty of sources and articles out there but I didn't find anything that
condenced it all down to a "one pager" of code...
And as I completed this I thought others might want find it useful to help understand how ECC "works".
So, if you scroll all the way down to the bottom you'll find a symmmetric encryption example using
ECC that motivates pretty much all the code above it...
DISCLAIMERS:
* I obviously take no responsibility for any state secrets you might loose should
you actually *use* the code herein...
* I have written this as a fun little intellectual excercise - there might be mistakes, there might be bugs...
Main sources:
* Certicom: http://www.certicom.com/index.php?action=ecc,home
* Wikipedia
* Harry J. Smith's inverse-modulo implementation
http://www.geocities.com/hjsmithh/Numbers/InvMod.html
* Raju and Akbani: http://www.cs.utsa.edu/~rakbani/publications/Akbani-ECC-IEEESMC03.pdf
* Allardyce and Goyal: http://www.ece.tamu.edu/~reddy/ee689_04/pres_joel_nitesh.pdf
* Klaus Reinhard's ECC test page: http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.4.en.html
Developed using Dev-C++ version 4.9.9.2
http://www.bloodshed.net
*/
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
#include <math.h>
#include "FiniteFieldElement.hpp"
namespace Cryptography
{
/*
Elliptic Curve over a finite field of order P:
y^2 mod P = x^3 + ax + b mod P
NOTE: this implementation is simple and uses normal machine integers for its calculations.
No special "big integer" manipulation is supported so anything _big_ won't work.
However, it is a complete finite field EC implementation in that it can be used
to learn and understand the behaviour of these curves and in particular to experiment with them
for their use in cryptography
Template parameter P is the order of the finite field Fp over which this curve is defined
*/
template<int P>
class EllipticCurve
{
public:
// this curve is defined over the finite field (Galois field) Fp, this is the
// typedef of elements in it
typedef FiniteFieldElement<P> ffe_t;
/*
A point, or group element, on the EC, consisting of two elements of the field FP
Points can only created by the EC instance itself as they have to be
elements of the group generated by the EC
*/
class Point
{
friend class EllipticCurve<P>;
typedef FiniteFieldElement<P> ffe_t;
ffe_t x_;
ffe_t y_;
EllipticCurve *ec_;
// core of the doubling multiplier algorithm (see below)
// multiplies acc by m as a series of "2*acc's"
void addDouble(int m, Point& acc)
{
if ( m > 0 )
{
Point r = acc;
for ( int n=0; n < m; ++n )
{
r += r; // doubling step
}
acc = r;
}
}
// doubling multiplier algorithm
// multiplies a by k by expanding in multiplies by 2
// a is also an accumulator that stores the intermediate results
// between the "1s" of the binary form of the input scalar k
Point scalarMultiply(int k, const Point& a)
{
Point acc = a;
Point res = Point(0,0,*ec_);
int i = 0, j = 0;
int b = k;
while( b )
{
if ( b & 1 )
{
// bit is set; acc = 2^(i-j)*acc
addDouble(i-j,acc);
res += acc;
j = i; // last bit set
}
b >>= 1;
++i;
}
return res;
}
// adding two points on the curve
void add(ffe_t x1, ffe_t y1, ffe_t x2, ffe_t y2, ffe_t & xR, ffe_t & yR) const
{
// special cases involving the additive identity
if ( x1 == 0 && y1 == 0 )
{
xR = x2;
yR = y2;
return;
}
if ( x2 == 0 && y2 == 0 )
{
xR = x1;
yR = y1;
return;
}
if ( x1==x2&&y1 == -y2 )
{
xR = yR = 0;
return;
}
// the additions
ffe_t s;
if ( x1 == x2 && y1 == y2 )
{
//2P
s = (3*(x1.i()*x1.i()) + ec_->a()) / (2*y1);
xR = ((s*s) - 2*x1);
}
else
{
//P+Q
s = (y1 - y2) / (x1 - x2);
xR = ((s*s) - x1 - x2);
}
if ( s != 0 )
{
yR = (-y1 + s*(x1 - xR));
}
else
{
yR = (-y1 + s*(x1 - xR));
//xR = yR = 0;
}
}
Point(int x, int y)
: x_(x),
y_(y),
ec_(0)
{}
Point(int x, int y, EllipticCurve<P> & EllipticCurve)
: x_(x),
y_(y),
ec_(&EllipticCurve)
{}
Point(const ffe_t& x, const ffe_t& y, EllipticCurve<P> & EllipticCurve)
: x_(x),
y_(y),
ec_(&EllipticCurve)
{}
public:
static Point ONE;
Ecc.rar_Python 椭圆_antsftu_椭圆_椭圆曲线_椭圆曲线 python
版权申诉
138 浏览量
2022-09-24
08:40:56
上传
评论
收藏 7KB RAR 举报
小贝德罗
- 粉丝: 67
- 资源: 1万+
最新资源
- HandTrackingModule.py
- Python基于卷积神经网络的鸟类识别项目源代码,ipynb文件
- 批量将py编译为pyd文件.atbx
- Python项目-学生管理系统
- 图像处理基于matlab图像RGB三色合成分离【含Matlab源码第1发】
- verilog HDL硬件语法设计包括算术运算三人表决器Verilog的阻塞和非阻塞赋值源码例程quartus13.1工程合集
- 【文章话题分类论文】OpenAlex Topic Classification Whitepaper
- linux学习常用命令
- 功率拓扑快速参考指南-ti,TI官方出品
- 开源2023电赛国赛运动目标控制(E题)视觉部分
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈