broken c port of Ec25519 key exchange
Posted: Sat Feb 20, 2010 7:19 am
I can't seem to find whats wrong with my port from the topic.
http://www.purebasic.fr/english/viewtop ... 12&t=41157
possibly my offset calculations, loop bounds or just plain dumb
c source below
http://www.purebasic.fr/english/viewtop ... 12&t=41157
possibly my offset calculations, loop bounds or just plain dumb
c source below
Code: Select all
Macro comment()
; /* Copyright 2008, Google Inc.
; * All rights reserved.
; *
; * Redistribution And use in source And binary forms, With Or without
; * modification, are permitted provided that the following conditions are
; * met:
; *
; * * Redistributions of source code must retain the above copyright
; * notice, this List of conditions And the following disclaimer.
; * * Redistributions in binary form must reproduce the above
; * copyright notice, this List of conditions And the following disclaimer
; * in the documentation And/Or other materials provided With the
; * distribution.
; * * Neither the name of Google Inc. nor the names of its
; * contributors may be used To endorse Or promote products derived from
; * this software without specific prior written permission.
; *
; * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS And CONTRIBUTORS
; * "AS IS" And ANY EXPRESS Or IMPLIED WARRANTIES, INCLUDING, BUT Not
; * LIMITED To, THE IMPLIED WARRANTIES OF MERCHANTABILITY And FITNESS For
; * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
; * OWNER Or CONTRIBUTORS BE LIABLE For ANY DIRECT, INDIRECT, INCIDENTAL,
; * SPECIAL, EXEMPLARY, Or CONSEQUENTIAL DAMAGES (INCLUDING, BUT Not
; * LIMITED To, PROCUREMENT OF SUBSTITUTE GOODS Or SERVICES; LOSS OF USE,
; * Data, Or PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
; * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, Or TORT
; * (INCLUDING NEGLIGENCE Or OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
; * OF THIS SOFTWARE, EVEN If ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
; *
; * curve25519-donna: Curve25519 elliptic curve, public key function
; *
; * http://code.google.com/p/curve25519-donna/
; *
; * Adam Langley <agl@imperialviolet.org>
; *
; * Derived from public domain C code by Daniel J. Bernstein <djb@cr.yp.To>
; *
; * More information about curve25519 can be found here
; * http://cr.yp.To/ecdh.html
; *
; * djb's sample implementation of curve25519 is written in a special assembly
; * language called qhasm And uses the floating point registers.
; *
; * This is, almost, a clean room reimplementation from the curve25519 paper. It
; * uses many of the tricks described therein. Only the crecip function is taken
; * from the sample implementation.
; */
EndMacro
;EnableExplicit
Global *tA = AllocateMemory(19*8)
Global *tB = AllocateMemory(19*8)
Global over.q,over2.q
Global *mysecret = AllocateMemory(32)
Global *mypublic = AllocateMemory(32)
Global *basepoint = AllocateMemory(32)
Global *hissecret = AllocateMemory(32)
Global *hispublic = AllocateMemory(32)
Global *myshared = AllocateMemory(32)
Global *hisshared = AllocateMemory(32)
Procedure dB(*mem,op.s)
Protected len,st.s
len = MemorySize(*mem)
st = op + " "
For a = 0 To len-1
st+RSet(Hex(PeekA(*mem+a),#PB_Byte),2,"0")
Next
Debug str$
EndProcedure
Macro fsum(out,in)
i=0
While i < 80
ii=i+8
PokeQ(out+i,(PeekQ(out+i) + PeekQ(in+i)))
PokeQ(out+ii,(PeekQ(out+ii) + PeekQ(in+ii)))
i+16
Wend
;db(*out,"Sum")
EndMacro
Macro fdifference(out,in)
i=0
While i < 80
PokeQ(out+i,(PeekQ(in+i) - PeekQ(out+i)));
i+8
Wend
;db(*out,"difference")
EndMacro
Macro fscalar_product(out,in,scalar)
i=0
While i < 80
PokeQ(out+i,(PeekQ(in+i) * scalar))
i+8
Wend
;db(*out,"scallar")
EndMacro
Macro fproduct(out,im,in)
PokeQ(*out+0, PeekQ(*im+0) * PeekQ(*in+0));
PokeQ(*out+8, PeekQ(*im+0) * PeekQ(*in+8) + PeekQ(*im+8) * PeekQ(*in+0));
PokeQ(*out+16, 2 * PeekQ(*im+8) * PeekQ(*in+8) + PeekQ(*im+0) * PeekQ(*in+16) + PeekQ(*im+16) * PeekQ(*in+0));
PokeQ(*out+24, PeekQ(*im+8) * PeekQ(*in+16) + PeekQ(*im+16) * PeekQ(*in+8) + PeekQ(*im+0) * PeekQ(*in+24) + PeekQ(*im+24) * PeekQ(*in+0));
PokeQ(*out+32, PeekQ(*im+16) * PeekQ(*in+16) + 2 * (PeekQ(*im+8) * PeekQ(*in+24) + PeekQ(*im+24) * PeekQ(*in+8)) + PeekQ(*im+0) * PeekQ(*in+32) + PeekQ(*im+32) * PeekQ(*in+0));
PokeQ(*out+40, PeekQ(*im+16) * PeekQ(*in+24) + PeekQ(*im+24) * PeekQ(*in+16) + PeekQ(*im+8) * PeekQ(*in+32) + PeekQ(*im+32) * PeekQ(*in+8) + PeekQ(*im+0) * PeekQ(*in+40) + PeekQ(*im+40) * PeekQ(*in+0));
PokeQ(*out+48, 2 * (PeekQ(*im+24) * PeekQ(*in+24) + PeekQ(*im+8) * PeekQ(*in+40) + PeekQ(*im+40) * PeekQ(*in+8)) + PeekQ(*im+16) * PeekQ(*in+32) + PeekQ(*im+32) * PeekQ(*in+16) + PeekQ(*im+0) * PeekQ(*in+48) + PeekQ(*im+48) * PeekQ(*in+0));
PokeQ(*out+56, PeekQ(*im+24) * PeekQ(*in+32) + PeekQ(*im+32) * PeekQ(*in+24) + PeekQ(*im+16) * PeekQ(*in+40) + PeekQ(*im+40) * PeekQ(*in+16) + PeekQ(*im+8) * PeekQ(*in+48) + PeekQ(*im+48) * PeekQ(*in+8) + PeekQ(*im+0) * PeekQ(*in+56) + PeekQ(*im+56) * PeekQ(*in+0));
PokeQ(*out+64, PeekQ(*im+32) * PeekQ(*in+32) + 2 * (PeekQ(*im+24) * PeekQ(*in+40) + PeekQ(*im+40) * PeekQ(*in+24) + PeekQ(*im+8) * PeekQ(*in+56) + PeekQ(*im+56) * PeekQ(*in+8)) + PeekQ(*im+16) * PeekQ(*in+48) + PeekQ(*im+48) * PeekQ(*in+16) + PeekQ(*im+0) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+0));
PokeQ(*out+72, PeekQ(*im+32) * PeekQ(*in+40) + PeekQ(*im+40) * PeekQ(*in+32) + PeekQ(*im+24) * PeekQ(*in+48) + PeekQ(*im+48) * PeekQ(*in+24) + PeekQ(*im+16) * PeekQ(*in+56) + PeekQ(*im+56) * PeekQ(*in+16) + PeekQ(*im+8) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+8) + PeekQ(*im+0) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+0));
PokeQ(*out+80, 2 * (PeekQ(*im+40) * PeekQ(*in+40) + PeekQ(*im+24) * PeekQ(*in+56) + PeekQ(*im+56) * PeekQ(*in+24) + PeekQ(*im+8) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+8)) + PeekQ(*im+32) * PeekQ(*in+48) + PeekQ(*im+48) * PeekQ(*in+32) + PeekQ(*im+16) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+16));
PokeQ(*out+88, PeekQ(*im+40) * PeekQ(*in+48) + PeekQ(*im+48) * PeekQ(*in+40) + PeekQ(*im+32) * PeekQ(*in+56) + PeekQ(*im+56) * PeekQ(*in+32) + PeekQ(*im+24) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+24) + PeekQ(*im+16) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+16));
PokeQ(*out+96, PeekQ(*im+48) * PeekQ(*in+48) + 2 * (PeekQ(*im+40) * PeekQ(*in+56) + PeekQ(*im+56) * PeekQ(*in+40) + PeekQ(*im+24) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+24)) + PeekQ(*im+32) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+32));
PokeQ(*out+104, PeekQ(*im+48) * PeekQ(*in+56) + PeekQ(*im+56) * PeekQ(*in+48) + PeekQ(*im+40) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+40) + PeekQ(*im+32) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+32));
PokeQ(*out+112, 2 * (PeekQ(*im+56) * PeekQ(*in+56) + PeekQ(*im+40) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+40)) + PeekQ(*im+48) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+48));
PokeQ(*out+120, PeekQ(*im+56) * PeekQ(*in+64) + PeekQ(*im+64) * PeekQ(*in+56) + PeekQ(*im+48) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+48));
PokeQ(*out+128, PeekQ(*im+64) * PeekQ(*in+64) + 2 * (PeekQ(*im+56) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+56)));
PokeQ(*out+136, PeekQ(*im+64) * PeekQ(*in+72) + PeekQ(*im+72) * PeekQ(*in+64));
PokeQ(*out+144, 2 * PeekQ(*im+72) * PeekQ(*in+72));
;db(*out,"product")
EndMacro
Macro freduce_degree(out)
PokeQ(*out+64,PeekQ(*out+64) + (19 * PeekQ(*out+144)));
PokeQ(*out+56,PeekQ(*out+56) + (19 * PeekQ(*out+136)));
PokeQ(*out+48,PeekQ(*out+48) + (19 * PeekQ(*out+128)));
PokeQ(*out+40,PeekQ(*out+40) + (19 * PeekQ(*out+120)));
PokeQ(*out+32,PeekQ(*out+32) + (19 * PeekQ(*out+112)));
PokeQ(*out+24,PeekQ(*out+24) + (19 * PeekQ(*out+104)));
PokeQ(*out+16,PeekQ(*out+16) + (19 * PeekQ(*out+96)));
PokeQ(*out+8,PeekQ(*out+8) + (19 * PeekQ(*out+88)));
PokeQ(*out+0,PeekQ(*out+0) + (19 * PeekQ(*out+80)));
;db(out,"degree")
EndMacro
Macro freduce_coefficients(out)
Repeat
PokeQ(*out+80,0);
i=0
While i < 80 ;Step 2
over = PeekQ(*out+i) / $2000000;
over2 = (over + ((over >> 63) * 2) + 1) / 2;
PokeQ(*out+i+8,((PeekQ(*out+i+8)) + over2));
PokeQ(*out+i,((PeekQ(*out+i)) - (over2 * $4000000)))
over = (PeekQ(*out+i+8)) / $2000000;
PokeQ(*out+i+16,(PeekQ(*out+i+16) + over));
PokeQ(*out+i+8,(PeekQ(*out+i+8)) - (over * $2000000));
i+16
Wend
PokeQ(*out+0,((PeekQ(*out+0)) + (19 * (PeekQ(*out+80)))));
Until Not PeekQ(*out+80) ;
;db(*out,"Coeff")
EndMacro
Macro fsquare_inner(out,in)
PokeQ(*out+0, PeekQ(*in+0) * PeekQ(*in+0));
PokeQ(*out+8, 2 * PeekQ(*in+0) * PeekQ(*in+8));
PokeQ(*out+16, 2 * (PeekQ(*in+8) * PeekQ(*in+8) + PeekQ(*in+0) * PeekQ(*in+16)));
PokeQ(*out+24, 2 * (PeekQ(*in+8) * PeekQ(*in+16) + PeekQ(*in+0) * PeekQ(*in+24)));
PokeQ(*out+32, PeekQ(*in+16) * PeekQ(*in+16) + 4 * PeekQ(*in+8) * PeekQ(*in+24) + 2 * PeekQ(*in+0) * PeekQ(*in+32));
PokeQ(*out+40, 2 * (PeekQ(*in+16) * PeekQ(*in+24) + PeekQ(*in+8) * PeekQ(*in+32) + PeekQ(*in+0) * PeekQ(*in+40)));
PokeQ(*out+48, 2 * (PeekQ(*in+24) * PeekQ(*in+24) + PeekQ(*in+16) * PeekQ(*in+32) + PeekQ(*in+0) * PeekQ(*in+48) + 2 * PeekQ(*in+8) * PeekQ(*in+40)));
PokeQ(*out+56, 2 * (PeekQ(*in+24) * PeekQ(*in+32) + PeekQ(*in+16) * PeekQ(*in+40) + PeekQ(*in+8) * PeekQ(*in+48) + PeekQ(*in+0) * PeekQ(*in+56)));
PokeQ(*out+64, PeekQ(*in+32) * PeekQ(*in+32) + 2 * (PeekQ(*in+16) * PeekQ(*in+48) + PeekQ(*in+0) * PeekQ(*in+64) + 2 * (PeekQ(*in+8) * PeekQ(*in+56) + PeekQ(*in+24) * PeekQ(*in+40))));
PokeQ(*out+72, 2 * (PeekQ(*in+32) * PeekQ(*in+40) + PeekQ(*in+24) * PeekQ(*in+48) + PeekQ(*in+16) * PeekQ(*in+56) + PeekQ(*in+8) * PeekQ(*in+64) + PeekQ(*in+0) * PeekQ(*in+72)));
PokeQ(*out+80, 2 * (PeekQ(*in+40) * PeekQ(*in+40) + PeekQ(*in+32) * PeekQ(*in+48) + PeekQ(*in+16) * PeekQ(*in+64) + 2 * (PeekQ(*in+24) * PeekQ(*in+56) + PeekQ(*in+8) * PeekQ(*in+72))));
PokeQ(*out+88, 2 * (PeekQ(*in+40) * PeekQ(*in+48) + PeekQ(*in+32) * PeekQ(*in+56) + PeekQ(*in+24) * PeekQ(*in+64) + PeekQ(*in+16) * PeekQ(*in+72)));
PokeQ(*out+96, PeekQ(*in+48) * PeekQ(*in+48) + 2 * (PeekQ(*in+32) * PeekQ(*in+64) + 2 * (PeekQ(*in+40) * PeekQ(*in+56) + PeekQ(*in+24) * PeekQ(*in+72))));
PokeQ(*out+104, 2 * (PeekQ(*in+48) * PeekQ(*in+56) + PeekQ(*in+40) * PeekQ(*in+64) + PeekQ(*in+32) * PeekQ(*in+72)));
PokeQ(*out+112, 2 * (PeekQ(*in+56) * PeekQ(*in+56) + PeekQ(*in+48) * PeekQ(*in+64) + 2 * PeekQ(*in+40) * PeekQ(*in+72)));
PokeQ(*out+120, 2 * (PeekQ(*in+56) * PeekQ(*in+64) + PeekQ(*in+48) * PeekQ(*in+72)));
PokeQ(*out+128, PeekQ(*in+64) * PeekQ(*in+64) + 4 * PeekQ(*in+56) * PeekQ(*in+72));
PokeQ(*out+136, 2 * PeekQ(*in+64) * PeekQ(*in+72));
PokeQ(*out+144, 2 * PeekQ(*in+72) * PeekQ(*in+72));
;db(*out,"square inner")
EndMacro
Macro fexpand(out,in) ;(quad,byte)
PokeQ(out+0,(((PeekA(in+0)) | (PeekA(in+1)) << 8 | (PeekA(in+2)) << 16 | (PeekA(in+3)) << 24)) & $3ffffff);
PokeQ(out+8,(((PeekA(in+3+0)) | (PeekA(in+3+1)) << 8 | (PeekA(in+3+2)) << 16 | (PeekA(in+3+3)) << 24) >> 2) & $1ffffff);
PokeQ(out+16,(((PeekA(in+6+0)) | (PeekA(in+6+1)) << 8 | (PeekA(in+6+2)) << 16 | (PeekA(in+6+3)) << 24) >> 3) & $3ffffff);
PokeQ(out+24,(((PeekA(in+9+0)) | (PeekA(in+9+1)) << 8 | (PeekA(in+9+2)) << 16 | (PeekA(in+9+3)) << 24) >> 5) & $1ffffff);
PokeQ(out+32,(((PeekA(in+12+0)) | (PeekA(in+12+1)) << 8 | (PeekA(in+12+2)) << 16 | (PeekA(in+12+3)) << 24) >> 6) & $3ffffff);
PokeQ(out+40,(((PeekA(in+16+0)) | (PeekA(in+16+1)) << 8 | (PeekA(in+16+2)) << 16 | (PeekA(in+16+3)) << 24)) & $1ffffff);
PokeQ(out+48,(((PeekA(in+19+0)) | (PeekA(in+19+1)) << 8 | (PeekA(in+19+2)) << 16 | (PeekA(in+19+3)) << 24) >> 1) & $3ffffff);
PokeQ(out+56,(((PeekA(in+22+0)) | (PeekA(in+22+1)) << 8 | (PeekA(in+22+2)) << 16 | (PeekA(in+22+3)) << 24) >> 3) & $1ffffff);
PokeQ(out+64,(((PeekA(in+25+0)) | (PeekA(in+25+1)) << 8 | (PeekA(in+25+2)) << 16 | (PeekA(in+25+3)) << 24) >> 4) & $3ffffff);
PokeQ(out+72,(((PeekA(in+28+0)) | (PeekA(in+28+1)) << 8 | (PeekA(in+28+2)) << 16 | (PeekA(in+28+3)) << 24) >> 6) & $1ffffff);
;db(*out,"Expand")
EndMacro
Macro FC(out,in,i,s)
PokeA(out+s+0,(PeekA(out+s+0) | PeekQ(in+(i*8))) & $ff);
PokeA(out+s+1,(PeekQ(in+(i*8)) >> 8) & $ff); \
PokeA(out+s+2,(PeekQ(in+(i*8)) >> 16) & $ff); \
PokeA(out+s+3,(PeekQ(in+(i*8)) >> 24) & $ff);
PokeA(out+0,0);
PokeA(out+16,0);
;db(*out,"FC")
EndMacro
Procedure fsquare(*out,*in)
Protected i.i
fsquare_inner(tB, in);
freduce_degree(tB);
freduce_coefficients(tB);
CopyMemory(*tB,*out,80);
FillMemory(*tb,19*8,0)
db(*out,"Square")
EndProcedure
Procedure fmul(*out,*in,*in2)
Protected i.i
fproduct(tA,in,in2);
freduce_degree(tA);
freduce_coefficients(tA);
CopyMemory(*tA,*out,80);
FillMemory(*TA,19*8,0)
;db(*out,"mul")
EndProcedure
Procedure fcontract(*out,*in)
Protected a,i
Repeat
For a = 0 To 8
If (a & 1)
While PeekQ(*in+i) < 0
PokeQ(*in+i,PeekQ(*in+i) + $2000000);
PokeQ(*in+i+8,PeekQ(*in+i+8)-1);
Wend
Else
While PeekQ(*in+i) < 0
PokeQ(*in+i,PeekQ(*in+i) + $4000000);
PokeQ(*in+i+8,PeekQ(*in+i+8)-1);
Wend
EndIf
i+8
Next
While PeekQ(*in+72) < 0
PokeQ(*in+72,PeekQ(*in+72) + $2000000);
PokeQ(*in+0,PeekQ(*in+0) - 19);
Wend
Debug PeekQ(*in+0)
Until PeekQ(*in+0) > 0;
PokeQ(*in+8,PeekQ(*in+8) << 2);
PokeQ(*in+16,PeekQ(*in+16) << 3);
PokeQ(*in+24,PeekQ(*in+24) << 5);
PokeQ(*in+32,PeekQ(*in+32) << 6);
PokeQ(*in+48,PeekQ(*in+48) << 1);
PokeQ(*in+56,PeekQ(*in+56) << 3);
PokeQ(*in+64,PeekQ(*in+64) << 4);
PokeQ(*in+72,PeekQ(*in+72) << 6);
FC(*out,*in,0,0);
FC(*out,*in,1,3);
FC(*out,*in,2,6);
FC(*out,*in,3,9);
FC(*out,*in,4,12);
FC(*out,*in,5,16);
FC(*out,*in,6,19);
FC(*out,*in,7,22);
FC(*out,*in,8,25);
FC(*out,*in,9,28);
db(*out,"Contract")
EndProcedure
Procedure fmonty(*x2,*z2,*x3,*z3,*x,*z,*xprime,*zprime,*qmqp)
Protected *origx = AllocateMemory(80)
Protected *origxprime = AllocateMemory(80)
Protected *zzz = AllocateMemory(8*19)
Protected *xx = AllocateMemory(8*19)
Protected *zz = AllocateMemory(8*19)
Protected *xxprime = AllocateMemory(8*19)
Protected *zzprime = AllocateMemory(8*19)
Protected *zzzprime = AllocateMemory(8*19)
Protected *xxxprime = AllocateMemory(8*19);
Protected i,ii
CopyMemory(*x,*origx,80) ;10 * SizeOf(felem));
fsum(*x,*z);
fdifference(*z,*origx); // does x - z
CopyMemory(*xprime,*origxprime,80); xprime, SizeOf(felem) * 10);
fsum(*xprime, *zprime);
fdifference(*zprime, *origxprime);
fproduct(xxprime, xprime, z);
fproduct(zzprime, x, zprime);
freduce_degree(xxprime);
freduce_coefficients(xxprime);
freduce_degree(zzprime);
freduce_coefficients(zzprime);
CopyMemory(*xxprime,*origxprime,80); xxprime, SizeOf(felem) * 10);
fsum(*xxprime, *zzprime);
fdifference(*zzprime, *origxprime);
fsquare(*xxxprime,*xxprime);
fsquare(*zzzprime,*zzprime);
fproduct(zzprime,zzzprime,qmqp);
freduce_degree(zzprime);
freduce_coefficients(zzprime);
CopyMemory(*xxxprime,*x3,80); xxxprime, SizeOf(felem) * 10);
CopyMemory(*zzprime,*z3,80); zzprime, SizeOf(felem) * 10);
fsquare(*xx,*x);
fsquare(*zz,*z);
fproduct(x2,xx,zz);
freduce_degree(x2);
freduce_coefficients(x2);
fdifference(*zz,*xx); // does zz = xx - zz
FillMemory(*zzz+80,72,0)
Protected scal.q = 121665
fscalar_product(*zzz,*zz,scal);
freduce_degree(zzz);
freduce_coefficients(zzz);
fsum(*zzz,*xx);
fproduct(z2,zz,zzz);
freduce_degree(z2);
freduce_coefficients(z2);
FreeMemory(*origx)
FreeMemory(*origxprime)
FreeMemory(*zzz)
FreeMemory(*xx)
FreeMemory(*zz)
FreeMemory(*xxprime)
FreeMemory(*zzprime)
FreeMemory(*zzzprime)
FreeMemory(*xxxprime)
; db(*x2,"fmonty x2")
; db(*z2,"fmonty z2")
EndProcedure
Procedure cmult(*resultx,*resultz,*n,*q)
Protected *a,*b,*c,*d,*e,*f,*g,*h,*t
Protected *nqpqx,*nqpqz,*nqx,*nqz
Protected *nqpqx2,*nqpqz2,*nqx2,*nqz2
Protected byte.i,i,j
*a = AllocateMemory(8*19)
*b = AllocateMemory(8*19)
*c = AllocateMemory(8*19)
*d = AllocateMemory(8*19)
PokeQ(*b,1) : PokeQ(*c,1)
*nqpqx = *a : *nqpqz = *b : *nqx = *c : *nqz =*d;
*a = AllocateMemory(8*19)
*b = AllocateMemory(8*19)
*c = AllocateMemory(8*19)
*d = AllocateMemory(8*19)
*e = AllocateMemory(8*19)
*f = AllocateMemory(8*19)
*g = AllocateMemory(8*19)
*h = AllocateMemory(8*19)
PokeQ(*f,1) : PokeQ(*h,1)
*nqpqx2 = *e : *nqpqz2 = *f : *nqx2 = *g : *nqz2 = *h;
CopyMemory(*q,*nqpqx,80)
db(*nqpqx,"nqpqx")
For i = 0 To 31
byte = PeekA(*n+(31-i)) & $FF
For j = 0 To 7
If (byte & $80)
fmonty(*nqpqx2,*nqpqz2,*nqx2,*nqz2,*nqpqx,*nqpqz,*nqx,*nqz,*q);
Else
fmonty(*nqx2,*nqz2,*nqpqx2,*nqpqz2,*nqx,*nqz,*nqpqx,*nqpqz,*q);
EndIf
*t = *nqx;
*nqx = *nqx2;
*nqx2 = *t;
*t = *nqz;
*nqz = *nqz2;
*nqz2 = *t;
*t = *nqpqx;
*nqpqx = *nqpqx2;
*nqpqx2 = *t;
*t = *nqpqz;
*nqpqz = *nqpqz2;
*nqpqz2 = *t;
byte << 1;
Next
Next
CopyMemory(*nqx,*resultx,80)
CopyMemory(*nqz,*resultz,80)
FreeMemory(*a)
FreeMemory(*b)
FreeMemory(*c)
FreeMemory(*d)
FreeMemory(*e)
FreeMemory(*f)
FreeMemory(*g)
db(*resultx,"cmult result x")
db(*resultx,"cmult result z")
EndProcedure
;// -----------------------------------------------------------------------------
;// Shamelessly copied from djb's code
;// -----------------------------------------------------------------------------
;Static void
Procedure crecip(*out,*z)
Protected *z2,*z9,*z11,*z2_5_0,*z2_10_0,*z2_20_0,*z2_50_0,*z2_100_0,*t0,*t1
Protected i
*z2 = AllocateMemory(80);
*z9 = AllocateMemory(80);
*z11 = AllocateMemory(80);
*z2_5_0 = AllocateMemory(80);
*z2_10_0 = AllocateMemory(80);
*z2_20_0 = AllocateMemory(80);
*z2_50_0 = AllocateMemory(80);
*z2_100_0 = AllocateMemory(80);
*t0 = AllocateMemory(80);
*t1 = AllocateMemory(80);
fsquare(*z2,*z);
fsquare(*t1,*z2);
fsquare(*t0,*t1);
fmul(*z9,*t0,*z);
fmul(*z11,*z9,*z2);
fsquare(*t0,*z11);
fmul(*z2_5_0,*t0,*z9);
fsquare(*t0,*z2_5_0);
fsquare(*t1,*t0);
fsquare(*t0,*t1);
fsquare(*t1,*t0);
fsquare(*t0,*t1);
fmul(*z2_10_0,*t0,*z2_5_0);
fsquare(*t0,*z2_10_0);
fsquare(*t1,*t0);
i=2
While i < 10
fsquare(*t0,*t1);
fsquare(*t1,*t0);
i+2
Wend
fmul(*z2_20_0,*t1,*z2_10_0);
fsquare(*t0,*z2_20_0);
fsquare(*t1,*t0);
i=2
While i < 20 ;Step 2
fsquare(*t0,*t1)
fsquare(*t1,*t0)
i+2
Wend
fmul(*t0,*t1,*z2_20_0);
fsquare(*t1,*t0);
fsquare(*t0,*t1);
i=2
While i < 10 ;Step 2
fsquare(*t1,*t0)
fsquare(*t0,*t1)
i+2
Wend
fmul(*z2_50_0,*t0,*z2_10_0);
fsquare(*t0,*z2_50_0);
fsquare(*t1,*t0);
i=2
While i < 50 ;Step 2
fsquare(*t0,*t1)
fsquare(*t1,*t0)
i+2
Wend
fmul(*z2_100_0,*t1,*z2_50_0);
fsquare(*t1,*z2_100_0);
fsquare(*t0,*t1);
i=2
While i < 100 ;Step 2
fsquare(*t1,*t0)
fsquare(*t0,*t1)
i+2
Wend
fmul(*t1,*t0,*z2_100_0);
fsquare(*t0,*t1);
fsquare(*t1,*t0);
i=2
While i < 50
fsquare(*t0,*t1)
fsquare(*t1,*t0)
i+2
Wend
fmul(*t0,*t1,*z2_50_0);
fsquare(*t1,*t0);
fsquare(*t0,*t1);
fsquare(*t1,*t0);
fsquare(*t0,*t1);
fsquare(*t1,*t0);
fmul(*out,*t1,*z11);
FreeMemory(*z2);
FreeMemory(*z9)
FreeMemory(*z11)
FreeMemory(*z2_5_0)
FreeMemory(*z2_10_0)
FreeMemory(*z2_20_0)
FreeMemory(*z2_50_0)
FreeMemory(*z2_100_0)
FreeMemory(*t0)
FreeMemory(*t1)
db(*out,"Crecip")
EndProcedure
Procedure curve(*mypublic.i,*secret.i,*basepoint.i)
Protected *bp,*x,*z,*zmone,*ee,i
*bp = AllocateMemory(80)
*x = AllocateMemory(80)
*z = AllocateMemory(80)
*zmone = AllocateMemory(80)
*ee = AllocateMemory(32);
i=0
While i < 32; ++i)
PokeA(*ee+i,PeekA(*secret+i));
Debug PeekA(*ee+i)
i+1
Wend
PokeA(*ee+0,(PeekA(*ee+0) & 248));
PokeA(*ee+31,(PeekA(*ee+31) & 127));
PokeA(*ee+31,(PeekA(*ee+31) | 64));
db(*ee,"secret")
fexpand(*bp,*basepoint);
cmult(*x, *z, *ee, *bp);
crecip(*zmone, *z);
fmul(*z, *x, *zmone);
fcontract(*mypublic,*z);
FreeMemory(*bp)
FreeMemory(*x)
FreeMemory(*z)
FreeMemory(*zmone)
FreeMemory(*ee)
EndProcedure
Define i
For i=0 To 31 : PokeA(*mysecret+i,42) : Next
PokeA(*mysecret+0, PeekA(*mysecret+0) & 248)
PokeA(*mysecret+31, PeekA(*mysecret+31) & 127)
PokeA(*mysecret+31, PeekA(*mysecret+31) | 64)
PokeA(*basepoint+0,9)
;-----
For i=0 To 31 : PokeA(*hissecret+i,11) : Next
PokeA(*hissecret+0, PeekA(*hissecret+0) & 248)
PokeA(*hissecret+31, PeekA(*hissecret+31) & 127)
PokeA(*hissecret+31, PeekA(*hissecret+31) | 64)
;---
OpenConsole()
ConsoleTitle("Curve25519 Test")
str$="": For i=0 To 31: str$+RSet(Hex(PeekA(*mysecret+i),#PB_Byte),2,"0"): Next : PrintN("mysecret : "+str$)
str$="": For i=0 To 31: str$+RSet(Hex(PeekA(*basepoint+i),#PB_Byte),2,"0"): Next : PrintN("basepoint: "+str$)
curve(*mypublic, *mysecret, *basepoint)
str$="": For i=0 To 31: str$+RSet(Hex(PeekA(*mypublic+i),#PB_Byte),2,"0"): Next : PrintN("mypublic : "+str$)
PrintN("")
str$="": For i=0 To 31: str$+RSet(Hex(PeekA(*hissecret+i),#PB_Byte),2,"0"): Next : PrintN("hissecret: "+str$)
str$="": For i=0 To 31: str$+RSet(Hex(PeekA(*basepoint+i),#PB_Byte),2,"0"): Next : PrintN("basepoint: "+str$)
curve(*hispublic, *hissecret, *basepoint)
str$="": For i=0 To 31: str$+RSet(Hex(PeekA(*hispublic+i),#PB_Byte),2,"0"): Next : PrintN("hispublic: "+str$)
PrintN("")
curve(*myshared, *mysecret, *hispublic)
curve(*hisshared, *hissecret, *mypublic)
str_myshared$="": For i=0 To 31: str_myshared$+RSet(Hex(PeekA(*myshared+i),#PB_Byte),2,"0"): Next : PrintN("myshared : "+str_myshared$)
str_hisshared$="": For i=0 To 31: str_hisshared$+RSet(Hex(PeekA(*hisshared+i),#PB_Byte),2,"0"): Next : PrintN("hisshared: "+str_hisshared$)
PrintN("")
If str_myshared$ = str_hisshared$
PrintN("myshared = hisshared")
Else
PrintN("myshared <> hisshared")
EndIf
PrintN("")
PrintN("")
PrintN("PRESS 'RETURN' TO QUIT.")
Input()
CloseConsole()
Code: Select all
/* Copyright 2008, Google Inc.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following disclaimer
* in the documentation and/or other materials provided with the
* distribution.
* * Neither the name of Google Inc. nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* curve25519-donna: Curve25519 elliptic curve, public key function
*
* http://code.google.com/p/curve25519-donna/
*
* Adam Langley <agl@imperialviolet.org>
*
* Derived from public domain C code by Daniel J. Bernstein <djb@cr.yp.to>
*
* More information about curve25519 can be found here
* http://cr.yp.to/ecdh.html
*
* djb's sample implementation of curve25519 is written in a special assembly
* language called qhasm and uses the floating point registers.
*
* This is, almost, a clean room reimplementation from the curve25519 paper. It
* uses many of the tricks described therein. Only the crecip function is taken
* from the sample implementation.
*/
#include <string.h>
#include <stdint.h>
typedef uint8_t u8;
typedef int64_t felem;
/* Sum two numbers: output += in */
static void fsum(felem *output, const felem *in) {
unsigned i;
for (i = 0; i < 10; i += 2) {
output[0+i] = (output[0+i] + in[0+i]);
output[1+i] = (output[1+i] + in[1+i]);
}
}
/* Find the difference of two numbers: output = in - output
* (note the order of the arguments!)
*/
static void fdifference(felem *output, const felem *in) {
unsigned i;
for (i = 0; i < 10; ++i) {
output[i] = (in[i] - output[i]);
}
}
/* Multiply a number my a scalar: output = in * scalar */
static void fscalar_product(felem *output, const felem *in, const felem scalar) {
unsigned i;
for (i = 0; i < 10; ++i) {
output[i] = in[i] * scalar;
}
}
/* Multiply two numbers: output = in2 * in
*
* output must be distinct to both inputs. The inputs are reduced coefficient
* form, the output is not.
*/
static void fproduct(felem *output, const felem *in2, const felem *in) {
output[0] = in2[0] * in[0];
output[1] = in2[0] * in[1] +
in2[1] * in[0];
output[2] = 2 * in2[1] * in[1] +
in2[0] * in[2] +
in2[2] * in[0];
output[3] = in2[1] * in[2] +
in2[2] * in[1] +
in2[0] * in[3] +
in2[3] * in[0];
output[4] = in2[2] * in[2] +
2 * (in2[1] * in[3] +
in2[3] * in[1]) +
in2[0] * in[4] +
in2[4] * in[0];
output[5] = in2[2] * in[3] +
in2[3] * in[2] +
in2[1] * in[4] +
in2[4] * in[1] +
in2[0] * in[5] +
in2[5] * in[0];
output[6] = 2 * (in2[3] * in[3] +
in2[1] * in[5] +
in2[5] * in[1]) +
in2[2] * in[4] +
in2[4] * in[2] +
in2[0] * in[6] +
in2[6] * in[0];
output[7] = in2[3] * in[4] +
in2[4] * in[3] +
in2[2] * in[5] +
in2[5] * in[2] +
in2[1] * in[6] +
in2[6] * in[1] +
in2[0] * in[7] +
in2[7] * in[0];
output[8] = in2[4] * in[4] +
2 * (in2[3] * in[5] +
in2[5] * in[3] +
in2[1] * in[7] +
in2[7] * in[1]) +
in2[2] * in[6] +
in2[6] * in[2] +
in2[0] * in[8] +
in2[8] * in[0];
output[9] = in2[4] * in[5] +
in2[5] * in[4] +
in2[3] * in[6] +
in2[6] * in[3] +
in2[2] * in[7] +
in2[7] * in[2] +
in2[1] * in[8] +
in2[8] * in[1] +
in2[0] * in[9] +
in2[9] * in[0];
output[10] = 2 * (in2[5] * in[5] +
in2[3] * in[7] +
in2[7] * in[3] +
in2[1] * in[9] +
in2[9] * in[1]) +
in2[4] * in[6] +
in2[6] * in[4] +
in2[2] * in[8] +
in2[8] * in[2];
output[11] = in2[5] * in[6] +
in2[6] * in[5] +
in2[4] * in[7] +
in2[7] * in[4] +
in2[3] * in[8] +
in2[8] * in[3] +
in2[2] * in[9] +
in2[9] * in[2];
output[12] = in2[6] * in[6] +
2 * (in2[5] * in[7] +
in2[7] * in[5] +
in2[3] * in[9] +
in2[9] * in[3]) +
in2[4] * in[8] +
in2[8] * in[4];
output[13] = in2[6] * in[7] +
in2[7] * in[6] +
in2[5] * in[8] +
in2[8] * in[5] +
in2[4] * in[9] +
in2[9] * in[4];
output[14] = 2 * (in2[7] * in[7] +
in2[5] * in[9] +
in2[9] * in[5]) +
in2[6] * in[8] +
in2[8] * in[6];
output[15] = in2[7] * in[8] +
in2[8] * in[7] +
in2[6] * in[9] +
in2[9] * in[6];
output[16] = in2[8] * in[8] +
2 * (in2[7] * in[9] +
in2[9] * in[7]);
output[17] = in2[8] * in[9] +
in2[9] * in[8];
output[18] = 2 * in2[9] * in[9];
}
/* Reduce a long form to a short form by taking the input mod 2^255 - 19. */
static void freduce_degree(felem *output) {
output[8] += 19 * output[18];
output[7] += 19 * output[17];
output[6] += 19 * output[16];
output[5] += 19 * output[15];
output[4] += 19 * output[14];
output[3] += 19 * output[13];
output[2] += 19 * output[12];
output[1] += 19 * output[11];
output[0] += 19 * output[10];
}
/* Reduce all coefficients of the short form input to be -2**25 <= x <= 2**25
*/
static void freduce_coefficients(felem *output) {
unsigned i;
do {
output[10] = 0;
for (i = 0; i < 10; i += 2) {
felem over = output[i] / 0x2000000l;
const felem over2 = (over + ((over >> 63) * 2) + 1) / 2;
output[i+1] += over2;
output[i] -= over2 * 0x4000000l;
over = output[i+1] / 0x2000000;
output[i+2] += over;
output[i+1] -= over * 0x2000000;
}
output[0] += 19 * output[10];
} while (output[10]);
}
/* A helpful wrapper around fproduct: output = in * in2.
*
* output must be distinct to both inputs. The output is reduced degree and
* reduced coefficient.
*/
static void
fmul(felem *output, const felem *in, const felem *in2) {
felem t[19];
fproduct(t, in, in2);
freduce_degree(t);
freduce_coefficients(t);
memcpy(output, t, sizeof(felem) * 10);
}
static void fsquare_inner(felem *output, const felem *in) {
output[0] = in[0] * in[0];
output[1] = 2 * in[0] * in[1];
output[2] = 2 * (in[1] * in[1] +
in[0] * in[2]);
output[3] = 2 * (in[1] * in[2] +
in[0] * in[3]);
output[4] = in[2] * in[2] +
4 * in[1] * in[3] +
2 * in[0] * in[4];
output[5] = 2 * (in[2] * in[3] +
in[1] * in[4] +
in[0] * in[5]);
output[6] = 2 * (in[3] * in[3] +
in[2] * in[4] +
in[0] * in[6] +
2 * in[1] * in[5]);
output[7] = 2 * (in[3] * in[4] +
in[2] * in[5] +
in[1] * in[6] +
in[0] * in[7]);
output[8] = in[4] * in[4] +
2 * (in[2] * in[6] +
in[0] * in[8] +
2 * (in[1] * in[7] +
in[3] * in[5]));
output[9] = 2 * (in[4] * in[5] +
in[3] * in[6] +
in[2] * in[7] +
in[1] * in[8] +
in[0] * in[9]);
output[10] = 2 * (in[5] * in[5] +
in[4] * in[6] +
in[2] * in[8] +
2 * (in[3] * in[7] +
in[1] * in[9]));
output[11] = 2 * (in[5] * in[6] +
in[4] * in[7] +
in[3] * in[8] +
in[2] * in[9]);
output[12] = in[6] * in[6] +
2 * (in[4] * in[8] +
2 * (in[5] * in[7] +
in[3] * in[9]));
output[13] = 2 * (in[6] * in[7] +
in[5] * in[8] +
in[4] * in[9]);
output[14] = 2 * (in[7] * in[7] +
in[6] * in[8] +
2 * in[5] * in[9]);
output[15] = 2 * (in[7] * in[8] +
in[6] * in[9]);
output[16] = in[8] * in[8] +
4 * in[7] * in[9];
output[17] = 2 * in[8] * in[9];
output[18] = 2 * in[9] * in[9];
}
static void
fsquare(felem *output, const felem *in) {
felem t[19];
fsquare_inner(t, in);
freduce_degree(t);
freduce_coefficients(t);
memcpy(output, t, sizeof(felem) * 10);
}
/* Take a little-endian, 32-byte number and expand it into polynomial form */
static void
fexpand(felem *output, const u8 *input) {
#define F(n,start,shift,mask) \
output[n] = ((((felem) input[start + 0]) | \
((felem) input[start + 1]) << 8 | \
((felem) input[start + 2]) << 16 | \
((felem) input[start + 3]) << 24) >> shift) & mask;
F(0, 0, 0, 0x3ffffff);
F(1, 3, 2, 0x1ffffff);
F(2, 6, 3, 0x3ffffff);
F(3, 9, 5, 0x1ffffff);
F(4, 12, 6, 0x3ffffff);
F(5, 16, 0, 0x1ffffff);
F(6, 19, 1, 0x3ffffff);
F(7, 22, 3, 0x1ffffff);
F(8, 25, 4, 0x3ffffff);
F(9, 28, 6, 0x1ffffff);
#undef F
}
/* Take a fully reduced polynomial form number and contract it into a
* little-endian, 32-byte array
*/
static void
fcontract(u8 *output, felem *input) {
int i;
do {
for (i = 0; i < 9; ++i) {
if ((i & 1) == 1) {
while (input[i] < 0) {
input[i] += 0x2000000;
input[i + 1]--;
}
} else {
while (input[i] < 0) {
input[i] += 0x4000000;
input[i + 1]--;
}
}
}
while (input[9] < 0) {
input[9] += 0x2000000;
input[0] -= 19;
}
} while (input[0] < 0);
input[1] <<= 2;
input[2] <<= 3;
input[3] <<= 5;
input[4] <<= 6;
input[6] <<= 1;
input[7] <<= 3;
input[8] <<= 4;
input[9] <<= 6;
#define F(i, s) \
output[s+0] |= input[i] & 0xff; \
output[s+1] = (input[i] >> 8) & 0xff; \
output[s+2] = (input[i] >> 16) & 0xff; \
output[s+3] = (input[i] >> 24) & 0xff;
output[0] = 0;
output[16] = 0;
F(0,0);
F(1,3);
F(2,6);
F(3,9);
F(4,12);
F(5,16);
F(6,19);
F(7,22);
F(8,25);
F(9,28);
#undef F
}
/* Input: Q, Q', Q-Q'
* Output: 2Q, Q+Q'
*
* x2 z3: long form
* x3 z3: long form
* x z: short form, destroyed
* xprime zprime: short form, destroyed
* qmqp: short form, preserved
*/
static void fmonty(felem *x2, felem *z2, /* output 2Q */
felem *x3, felem *z3, /* output Q + Q' */
felem *x, felem *z, /* input Q */
felem *xprime, felem *zprime, /* input Q' */
const felem *qmqp /* input Q - Q' */) {
felem origx[10], origxprime[10], zzz[19], xx[19], zz[19], xxprime[19],
zzprime[19], zzzprime[19], xxxprime[19];
memcpy(origx, x, 10 * sizeof(felem));
fsum(x, z);
fdifference(z, origx); // does x - z
memcpy(origxprime, xprime, sizeof(felem) * 10);
fsum(xprime, zprime);
fdifference(zprime, origxprime);
fproduct(xxprime, xprime, z);
fproduct(zzprime, x, zprime);
freduce_degree(xxprime);
freduce_coefficients(xxprime);
freduce_degree(zzprime);
freduce_coefficients(zzprime);
memcpy(origxprime, xxprime, sizeof(felem) * 10);
fsum(xxprime, zzprime);
fdifference(zzprime, origxprime);
fsquare(xxxprime, xxprime);
fsquare(zzzprime, zzprime);
fproduct(zzprime, zzzprime, qmqp);
freduce_degree(zzprime);
freduce_coefficients(zzprime);
memcpy(x3, xxxprime, sizeof(felem) * 10);
memcpy(z3, zzprime, sizeof(felem) * 10);
fsquare(xx, x);
fsquare(zz, z);
fproduct(x2, xx, zz);
freduce_degree(x2);
freduce_coefficients(x2);
fdifference(zz, xx); // does zz = xx - zz
memset(zzz + 10, 0, sizeof(felem) * 9);
fscalar_product(zzz, zz, 121665);
freduce_degree(zzz);
freduce_coefficients(zzz);
fsum(zzz, xx);
fproduct(z2, zz, zzz);
freduce_degree(z2);
freduce_coefficients(z2);
}
/* Calculates nQ where Q is the x-coordinate of a point on the curve
*
* resultx/resultz: the x coordinate of the resulting curve point (short form)
* n: a little endian, 32-byte number
* q: a point of the curve (short form)
*/
static void
cmult(felem *resultx, felem *resultz, const u8 *n, const felem *q) {
felem a[19] = {0}, b[19] = {1}, c[19] = {1}, d[19] = {0};
felem *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t;
felem e[19] = {0}, f[19] = {1}, g[19] = {0}, h[19] = {1};
felem *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h;
unsigned i, j;
memcpy(nqpqx, q, sizeof(felem) * 10);
for (i = 0; i < 32; ++i) {
u8 byte = n[31 - i];
for (j = 0; j < 8; ++j) {
if (byte & 0x80) {
fmonty(nqpqx2, nqpqz2,
nqx2, nqz2,
nqpqx, nqpqz,
nqx, nqz,
q);
} else {
fmonty(nqx2, nqz2,
nqpqx2, nqpqz2,
nqx, nqz,
nqpqx, nqpqz,
q);
}
t = nqx;
nqx = nqx2;
nqx2 = t;
t = nqz;
nqz = nqz2;
nqz2 = t;
t = nqpqx;
nqpqx = nqpqx2;
nqpqx2 = t;
t = nqpqz;
nqpqz = nqpqz2;
nqpqz2 = t;
byte <<= 1;
}
}
memcpy(resultx, nqx, sizeof(felem) * 10);
memcpy(resultz, nqz, sizeof(felem) * 10);
}
// -----------------------------------------------------------------------------
// Shamelessly copied from djb's code
// -----------------------------------------------------------------------------
static void
crecip(felem *out, const felem *z) {
felem z2[10];
felem z9[10];
felem z11[10];
felem z2_5_0[10];
felem z2_10_0[10];
felem z2_20_0[10];
felem z2_50_0[10];
felem z2_100_0[10];
felem t0[10];
felem t1[10];
int i;
/* 2 */ fsquare(z2,z);
/* 4 */ fsquare(t1,z2);
/* 8 */ fsquare(t0,t1);
/* 9 */ fmul(z9,t0,z);
/* 11 */ fmul(z11,z9,z2);
/* 22 */ fsquare(t0,z11);
/* 2^5 - 2^0 = 31 */ fmul(z2_5_0,t0,z9);
/* 2^6 - 2^1 */ fsquare(t0,z2_5_0);
/* 2^7 - 2^2 */ fsquare(t1,t0);
/* 2^8 - 2^3 */ fsquare(t0,t1);
/* 2^9 - 2^4 */ fsquare(t1,t0);
/* 2^10 - 2^5 */ fsquare(t0,t1);
/* 2^10 - 2^0 */ fmul(z2_10_0,t0,z2_5_0);
/* 2^11 - 2^1 */ fsquare(t0,z2_10_0);
/* 2^12 - 2^2 */ fsquare(t1,t0);
/* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
/* 2^20 - 2^0 */ fmul(z2_20_0,t1,z2_10_0);
/* 2^21 - 2^1 */ fsquare(t0,z2_20_0);
/* 2^22 - 2^2 */ fsquare(t1,t0);
/* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
/* 2^40 - 2^0 */ fmul(t0,t1,z2_20_0);
/* 2^41 - 2^1 */ fsquare(t1,t0);
/* 2^42 - 2^2 */ fsquare(t0,t1);
/* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t1,t0); fsquare(t0,t1); }
/* 2^50 - 2^0 */ fmul(z2_50_0,t0,z2_10_0);
/* 2^51 - 2^1 */ fsquare(t0,z2_50_0);
/* 2^52 - 2^2 */ fsquare(t1,t0);
/* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
/* 2^100 - 2^0 */ fmul(z2_100_0,t1,z2_50_0);
/* 2^101 - 2^1 */ fsquare(t1,z2_100_0);
/* 2^102 - 2^2 */ fsquare(t0,t1);
/* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fsquare(t1,t0); fsquare(t0,t1); }
/* 2^200 - 2^0 */ fmul(t1,t0,z2_100_0);
/* 2^201 - 2^1 */ fsquare(t0,t1);
/* 2^202 - 2^2 */ fsquare(t1,t0);
/* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
/* 2^250 - 2^0 */ fmul(t0,t1,z2_50_0);
/* 2^251 - 2^1 */ fsquare(t1,t0);
/* 2^252 - 2^2 */ fsquare(t0,t1);
/* 2^253 - 2^3 */ fsquare(t1,t0);
/* 2^254 - 2^4 */ fsquare(t0,t1);
/* 2^255 - 2^5 */ fsquare(t1,t0);
/* 2^255 - 21 */ fmul(out,t1,z11);
}
int
curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
felem bp[10], x[10], z[10], zmone[10];
uint8_t e[32];
int i;
for (i = 0; i < 32; ++i) e[i] = secret[i];
e[0] &= 248;
e[31] &= 127;
e[31] |= 64;
fexpand(bp, basepoint);
cmult(x, z, e, bp);
crecip(zmone, z);
fmul(z, x, zmone);
fcontract(mypublic, z);
return 0;
}
