Multiplicative inverse modulus p

JavaScript snippet that will implement this nicely.

Use approprite html elements that fits the script.

window.onload= initForm;

function initForm(){
document.getElementById("ok").onclick = calcInverse;
}

function calcInverse(){

var n= parseInt(document.getElementById("nn").value);
var p= parseInt(document.getElementById("pp").value);

var x = 1;
var y = 0;
var a=p;
var b=n;
var q,t;
var res;
while (b != 0) {
                t = b;
                q = Math.floor(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;
}

document.getElementById("r1").innerHTML="a^-1  er "+res;
return false;

}

The hunt for multiplicative inverses

The inverse of a, a^1=z mod m. Calculation aint easy for large m, this is where all the computing power goes.
a does have an inverse mod m if and only if a*z=1 mod m. Otherwice there is no inverse.
If our finite field is prime, then all members sport this property

We can find the inverse by using euclid. We know that in the Euclidean Algorithm you repeatedly divide the divisor by the remainder until the remainder is 0.
The gcd is then the last non-zero remainder.
We can write
za + mb = 1. This says that za = 1 + (-b)m, which means za=1 (mod m). We dont care about -b in this case of cause. So z is the inverse of a.

The extended version gives us z.
Nice tiny toy example here:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html

projective space and homogenous coordinates.

Guess I've got the projective space right now. Love the explanation at wiki.
http://en.wikipedia.org/wiki/Projective_space
But its urgent to really understand that and the homogeneous coordinates.
Projective space: really a projection! 3d space projected into a tiny 2d picture. A projection from 3d to 2d.

Quote:'the set of equivalence classes of R3\(0, 0, 0), i.e. 3-space without the origin, where two points P = (x, y, z) and Pˈ = (xˈ, yˈ, zˈ) are equivalent if there is a nonzero real number λ such that P = λ·Pˈ, i.e. x = λxˈ, y = λyˈ, z = λzˈ. The usual way to write an element of the projective plane, i.e. the equivalence class corresponding to an honest point (x, y, z) in R3, is

[x : y : z].

The last formula goes under the name of homogeneous coordinates'

You can homogenize like this: you add z until all parts of the equation have the same degree:

y^2=x^3 + Ax + B becomes y^2z=x^3 + Axz^2+Bz^3

Calculating in projective space gives us a way to work with the point at infinity without just panicking. The point at infinity just becomes a special plane i a 3 dimensional space, where parallel lines meet.
lucky bastards.

change of language

ok, I'll change the main language of this blog.
Today I found an indonesian girl doing exaclty the same as I, trying to focus and trying to study elliptic curves and implement some cryptography using EC. I was so happy she was not writing in whatever language - indonesian probably..

So if you read this blog, you'll have to deal with my not so perfect language skills.

Feel free to ask me translate any of my articles if some of them seems to be relevant for you.

Suitable curves

english summary:
Curves suitable for cryptography according to Rosing:
Elliptic Curves over Galois Fields.
Meaning curves over F2^n, meaning fields with characteristic 2 - and only nonsupersingular.
y^2 + xy = x^3 + a2x^2 + a6.
a6 cannot be zero
a2 can be zero.
.........
Ifølge Michael Rosing er de eneste kurver der er velegnede til kryptografisk brug kurver over Galois legemer. Dvs kurver på F2^n , med andre ord kurver med karakteristikken 2, og udvidelsesgraden n.- og det da kun hvis de ikke er supersingulære. Med andre ord skal de være af formen:

y^2 + xy = x^3 + a2x^2 + a6.
a6 må IKKE være nul.
a2 kan godt være nul.
Jeg tror fortsat polynominal basis er rarere at regne med end optinormal basis.

Hvordan mon denne klasse af anbefalede kurver matcher de i suite B angivne kurver. To be tested.

Punktaddition

Simpelt demonstationseksempel på R, med værdier max 'integer' størrelse:
Der konstrueres passende felter i html dokument der matcher id'erne i denne kode.
Denne meget lille primitive løsning tester IKKE for om punkterne overhovedet ligger på kurven - det er på eget ansvar. Det er kun i tilfældet P1=p2 hvor y1 er forskellig fra nul at kurvens koeficienter direkte indgår i additionsberegningen - og derfor der fejlkilden skal findes.
fgl placeres i eksternt javascript

window.onload= initForm;
function initForm(){
document.getElementById("ok").onclick = calcPoint;
}
function calcPoint(){
var x1= parseInt(document.getElementById("xx1").value);
var y1= parseInt(document.getElementById("yy1").value);

var x2= parseInt(document.getElementById("xx2").value);
var y2= parseInt(document.getElementById("yy2").value);
if((x2-x1) != 0 ){
var m = (y2-y1)/(x2-x1);
var x3 = (m*m)-x1-x2;
var y3= m*(x1-x3)-y1;
document.getElementById("r1").innerHTML="P3, (x3,y3) er "+x3+","+y3;
}
else if (((x2-x1) == 0) && ((y2-y1) != 0)){
alert("det er farligt at dividere med nul, P1 + P2 giver punktet i uendelig");}
else if ((x2-x1)==0 && (y2-y1)==0){
if(y2 != 0){
var A= parseInt(document.getElementById("AA").value);
var m = ((3*x1*x1)+A)/(2*y1);
var x3 = (m*m)-2*x1;
var y3= m*(x1-x3)-y1;
document.getElementById("r1").innerHTML="P3, (x3,y3) er "+x3+","+y3;
}
else{
alert("P1 + P2 giver punktet i uendelig");
document.getElementById("r1").innerHTML="eternal sunshine in a spotless mind";
}
}
else{
alert("noget gik helt galt");
document.getElementById("r1").innerHTML="42";
}

return false;
}

Litteraturliste

Så er der en relevant litteraturliste med links til bøgerne på Amazon.co.uk
Alle bøgerne står på min reol og omhandler enten talteori generelt, kryptering generelt eller specifikt matematik og kryptering med elliptiske kurver

support af Suite B i .NET

En stribe interessante muligheder for at få sat strøm i suite B:
Som sædvanlig byder Certicom sig til:
http://www.certicom.com/index.php/net

DOTNET, .NET har nu i version 3.5 fuld understøttelse af div suite B algoritmer
Læse her på MSDN:
http://msdn.microsoft.com/en-us/library/bb332048.aspx
cirka midt på siden.
To relevante klasser er beskrevet her:

Digital Signatur med EC: Elliptic Curve Digital Signature Algorithm (ECDSA).
http://msdn.microsoft.com/en-us/library/system.security.cryptography.ecdsacng.aspx

Diverse kryptografiske operationer med EC Diffie-Hellman
http://msdn.microsoft.com/en-us/library/system.security.cryptography.ecdiffiehellmancng.aspx

Måske trækker det op til lidt applied cryptography..

keyboard destruction

C i 21 days, C for total complete idiots, php for morons, C# fresh and crisp, Objective C in a tiny bucket the size of the moon, fast and furious keyboard destroyer.
Jo jeg blev istand til at programmere i en bunke forskellige underlige sprog, men lige meget hjælper det hvis man ikke sætter sig på sin dertil indrettede og beslutter sig for progression.

2 jobs senere, 3-4 sprog senere, adskillige keyboards senere viser det sig at det stadig er et spørgsmål om canvas og blikket stift rettet mod bog med spidset blyant.

Nuttet 3d visualisering af elliptisk kurve, med mulighed for selv at skrue på parametre

Meget meget nuttet tredimensionel demonstration af elliptiske kurver. Anvend i Mathematica følgende kode:
(eller se det online i linket under koden)

Manipulate[{F, G} = { x^3 - a y^2 + b x y^2 + c x^2 y, A x + B};
Plot3D[{F, G}, {x, -8, 10}, {y, -30, 30}, PlotRange -> All,
PlotStyle -> {LightBlue, Green},
MeshFunctions -> Function @@@ {{{x, y, z}, (F - G)}}, Mesh -> {{0}},
MeshStyle -> Directive[{Red, Thick}],
Epilog -> {Inset[
Graphics[
Text[Style[
Column[{"intersection curve",
Row[{a y^2, " = ", x^3 + b x y^2 + c x^2 y - A x - B}]},
Center], {12, 12}, Black]], ImageSize -> 240], {Center,
Top}], Inset[
Graphics[
Text[Style[
Column[{"surface", Row[{Style["z", Italic], " = ", F}]}], {12,
12}, Black]], ImageSize -> 200], {0.3, .1}],
Inset[Graphics[
Text[Style[
Column[{"plane", Row[{Style["z", Italic], " = ", G}]}], {12,
12}, Black]], ImageSize -> 150], {0.85, .1}]}, Axes -> None,
PlotPoints -> 45, Boxed -> False, ImageSize -> {375, 375},
SphericalRegion -> True, ViewAngle -> \[Pi]/6],
Style["parameters of the plane", Bold],
Style[Row[{"z = A x + B"}], Bold],
{{A, 11, "A (rotation)"}, -10, 25, 0.5, Appearance -> "Labeled",
ImageSize -> Tiny},
{{B, 12, "B (translation)"}, -20, 50, .01, Appearance -> "Labeled",
ImageSize -> Tiny},
Style["\nparameters of the surface", Bold],
Style["z = \!\(\*SuperscriptBox[\"x\", \"2\"]\)-a \
\!\(\*SuperscriptBox[\"y\", \"2\"]\)+b x \!\(\*SuperscriptBox[\"y\", \
\"2\"]\) + c \!\(\*SuperscriptBox[\"x\", \"2\"]\) y", Bold],
{{a, -1, "a"}, -2, 2, 0.01, Appearance -> "Labeled",
ImageSize -> Tiny},
{{b, 0, "b"}, -2, 2, 0.05, Appearance -> "Labeled",
ImageSize -> Tiny},
{{c, 0, "c"}, -5, 5, 0.2, Appearance -> "Labeled", ImageSize -> Tiny},
Delimiter, TrackedSymbols -> Manipulate, ControlPlacement -> Left,
SynchronousUpdating -> False]

http://demonstrations.wolfram.com/RealEllipticCurves/

at last

nu blev det her til en rigtig blog.
flytning en realitet og det må igen være tid til at fokusere HER

crash couse

Har de sidste dage været i kbh og fået et lyncrashcourse i C. Der er for meget der er hemmeligt i den nye bog hvis man ikke kan læse/skrive C. Det er IKKE ret tæt på hverken Java og C#. Men jeg VIL. Jeg vil kunne læse denne bog og lære noget deraf. Mere C bliver det måske til idag. Men børnene kommer hjem efter 14 dages ferie – så måske bliver det kun til en smule.
Pangel: installerede kubuntu på bærbar. Bærbar har iøvrigt fået ondt i skærmen og flipper engang imellem. Problemer md rettigheder på kubuntuinstallation. Ikke adgang til gcc compiler og det er meget bøvlet. Men heldigvis er .NET på XP ok at skrive og compilere C i.

YES!!

så er bogen her. Så er der dømt fordybelse.

Ingen bog idag.

Dagens gøremål var at modtage denne mail:
Hi List,

I just wanted to confirm that there will be a P1363 Working Group meeting in the Flying A Studio Room, University Center, University of California at Santa Barbara, on Thursday August 24th from 2-5 pm and on Friday August 25th from 9-5.
Full agenda will follow later. Hope to see you there!

Cheers,

William

================================

William Whyte,
Chair, IEEE P1363
NTRU Cryptosystems,

Jeg følger mig dog ikke overbevist om det er lige mig han gerne ser..

Pollards rho metode

Kurve haves over E(Fq) To punkter haves. Find et k så kP=Q
Random funktion anvendes. Visuelt Rho dannes og sammenfald nøjagtig der hvor cyklus begynder. Samme tidskomplexitet som Babiystep giant step- men fordel: very smal storage.


Update: english TRANSLATION:
Pollards rho method -this is how I understand it. I assume you have already been reading about it in general - this is an extract:

You have a curve E over a finie field Fq, E(Fq)
You have to points
Find a k so that kP=Q
Use random function.
Visualize a Rho ( the Greek letter) and you have a crosspoint exactly where the cycle begin.
Same complexity in time as Baby Step Giant Step - but advantage: very small storage

links:
Image:
http://commons.wikimedia.org/wiki/File:Rho-pollard.png
the math:
http://mathworld.wolfram.com/PollardRhoFactorizationMethod.html

SUPERsingulær

Udtryk: Hvis vi ser på E[3] så finder vi 9 punkter af ”orden 3”. Jf nedest s 74 Washington.
Hvis vi har med kurver at gøre E(Fq) når karakteristikken ikke ikke deler n eller er 0,
så gælder : E[n] isomorf med Zn X Zn
. Hvis karakteristikken p>0 deler n så er det en anelse anderledes. S 75 W.
En kurve kaldes ordinær hvis E[p] isomorf med Zp
Den er supersingulær hvis E[p] isomorf med 0. Altså en lidt anden vinkel end den i 2. Anførte forklaring.
Supersingulær her INTET med singulære punkter på kurver at gøre.

af orden 2

E[2]: torsionspunkter af orden 2.
Er vi i tilfældet F(Fq) kan E skrives som y^2 = (x-r1)(x-r2)(x-r3)
E[2] er altså de punkter P hvor der gælder at 2P=O. Lodret hældning. Det sker i rødderne og i punktet uendelig
E[2]={uendelig,(r1,0),(r2,0),(r3,0)}. Isomorft med Z2 X Z2
For E (F2^m) altså karakteristik 2 gælder at den elliptske kurve ser lidt anderledes ud og man får derfor to forskellige situationer.
E[2]={uendelig, (0,sqrt(a6))} isomorft med Z2 og E[2]={uendelig} isomorft med 0

I vote for Tanja

Den bliver altså sat på standby ind til jeg finder ud af om det er vigtigt. Tanja Lange kan ikke engang li dem. Hun er til Tate pairing i stedet.
Allan Bohnstedt Hansen har skrevet speciale (Generering af Frey-Rück Resistente Elliptiske kurver med Primtalsorden over Fp^2^c) hvor der er et helt kapitel om Weil pairing. En masse matematik, men den overordnede forståelse for det fik jeg vist ikke.

blob blob

Weil pairing er altså ikke helt trivielt..

Anormale kurver

s. 147 Washington. MOV attack virker fordi man kan bruge Weil pairing – for at undgå dette har man foreslået at man kunne anvende Anormalous Curves. Men ECDL problemet kan løses hurtigt på sådanne kurver. Men anvendes de over udvidelser af Fq kan de være brugbare da visse beregninger er hurtigere på anormale kurver.
Udvidelser af Fq – er det mon det samme som Fq^m ? Ja det er nok sådan udtrykket ”udvidelsesgraden” skal forståes.
Her har vi så årsagen til at man er interesseret i koblitskurver. Som netop er kurver på F2^m. Antså en bekræftelse på 4 og 8. Her må man så tro at MOV attacket så IKKE virker.
Hvad er det nu lige Weil pairing er?
MOV attack: weil pairing kan bruges til at konvertere DL i E(Fq) til et problem i Fq^m(*) – og DL på endelige legemer kan løses hurtigere end ECDL . hvis ikke Fq^m >> Fq . Indexmetoden kan anvendes.
Weil pairing er HELT central. Med venlig hilsen Washington s 82.