And it all works with big Integers.
Be sure that you only use valid numbers (prime for Fp and points that acctually ARE on the curve)
Next version will contain valid curves generated from startpoint and startvalues , plus it will contain an implementation of the double and add algorithm.
Sorry for the horrible buggy primitive spaghetti code without validation and exception handling for now - but I just made it and it works! - tested against a huge amount of numeric examples calculated by hand + toy examples provided by Hoffman, Pipher and Silverman.
It will not handle input of point at infinity. But you already know that P + Ø = P so... here we go.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Numerics;
namespace WindowsFormsApplication2
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
}
private void button2_Click(object sender, EventArgs e)
{
calcPoints();
}
private BigInteger calcLambda1(BigInteger y2, BigInteger y1, BigInteger x2, BigInteger x1, BigInteger modspace) {
BigInteger lam1 = (y2 - y1) * CalcInverse((x2 - x1), modspace);
return lam1;
}
private BigInteger calcLambda2(BigInteger x1, BigInteger y1, BigInteger A, BigInteger modspace)
{
BigInteger lam2= (3 * x1 * x1 + A)*CalcInverse((2 * y1), modspace);
return lam2;
}
private BigInteger calcXFinal(BigInteger Lambda, BigInteger x1, BigInteger x2, BigInteger modspace) {
BigInteger bigX= (Lambda*Lambda - x1 - x2)%modspace;
if (bigX < 0) { bigX = bigX + modspace; }
return bigX;
}
private BigInteger calcYFinal(BigInteger Lambda, BigInteger x1, BigInteger x3, BigInteger y1, BigInteger modspace)
{
BigInteger bigY= (Lambda*(x1-x3) - y1)%modspace;
if (bigY < 0) { bigY = bigY + modspace; }
return bigY;
}
private BigInteger CalcInverse(BigInteger n, BigInteger p)
{
BigInteger x = 1;
BigInteger y = 0;
BigInteger a = p;
BigInteger b = n;
BigInteger q, t;
BigInteger res;
while (b != 0)
{
t = b;
//q2 = Math.floor(a/t);
q = BigInteger.Divide(a, t);
b = a - q * t;
a = t;
t = x;
x = y - q * t;
y = t;
}
if (y < 0)
{
res = y + p;
}
else
{
res = y;
}
return res;
}
private void calcPoints() {
BigInteger inputA = BigInteger.Parse(paramA.Text);
BigInteger inputB = BigInteger.Parse(paramB.Text);
BigInteger inputx1 = BigInteger.Parse(paramx1.Text);
BigInteger inputy1 = BigInteger.Parse(paramy1.Text);
BigInteger inputx2 = BigInteger.Parse(paramx2.Text);
BigInteger inputy2 = BigInteger.Parse(paramy2.Text);
BigInteger modp = BigInteger.Parse(paramp.Text);
if ((inputx1 == inputx2) && (inputy1 != inputy2) )
{
resultx3.Text = "point at infinity";
resulty3.Text = "point at infinity";
}
else {
if ((inputx1 == inputx2) && (inputy1 == inputy2))
{
BigInteger l2 = (calcLambda2(inputx1,inputy1,inputA, modp))%modp;
dontpanic.Text = l2.ToString();
BigInteger resl2x3 = (calcXFinal(l2, inputx1, inputx2, modp))%modp;
BigInteger resl2y3 = (calcYFinal(l2, inputx1, resl2x3, inputy1, modp))%modp;
resultx3.Text = resl2x3.ToString();
resulty3.Text = resl2y3.ToString();
}
else {
BigInteger l1 = (calcLambda1(inputy2,inputy1, inputx2,inputx1, modp))%modp;
dontpanic.Text = l1.ToString();
BigInteger resl1x3 = (calcXFinal(l1, inputx1, inputx2, modp))%modp;
BigInteger resl1y3 = (calcYFinal(l1, inputx1, resl1x3, inputy1, modp))%modp;
resultx3.Text = resl1x3.ToString();
resulty3.Text = resl1y3.ToString();
}
}
}
}
The BigInteger is a part of the brand new package System.Numerics in .NET 4.0
more about that one here -->
http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx
For some reason the System.Numerics is not automatically added to projects - select menu project/Add Reference../ select tab: .NET and find System. Numerics.
