001 //#include "U8Set";
002 //https://martin.kleppmann.com/papers/curve25519.pdf
003 U0 Carry25519(I64 *elem) {
004   I64 i;
005   I64 carry;
006   for(i=0;i!=16;i++) {
007     carry=elem[i]>>16;
008     elem[i]-=carry<<16;
009     if(i<15) elem[i+1]=elem[i+1]+carry;
010     else elem[0]=elem[0]+38*carry;
011   }
012 }
013 U0 Unpack25519(I64 *out,U8 *in) {
014   I64 i;
015   for(i=0;i!=16;i++) out[i]=in[2*i](U16);
016   out[15]&=0x7fFF;
017 }
018 U0 fadd(I64 *out,I64 *a,I64 *b) {
019   I64 i;
020   for(i=0;i!=16;i++) {
021     out[i]=a[i]+b[i];
022   }
023 }
024 U0 fsub(I64 *out,I64 *a,I64 *b) {
025   I64 i;
026   for(i=0;i!=16;i++) {
027     out[i]=a[i]-b[i];
028   }
029 }
030 U0 fmul(I64 *out,I64 *a,I64 *b) {
031   I64 i,j,product[31];
032   MemSetU64(product,0,31);
033   for(i=0;i!=16;i++)
034     for(j=0;j!=16;j++) {
035        product[i+j]+=a[i]*b[j];
036     }
037   for(i=0;i!=15;i++) {
038     product[i]+=38*product[i+16];
039   }
040   MemCpy(out,product,16*8);
041   Carry25519(out);
042   Carry25519(out);
043 } 
044 U0 finverse(I64 *out,I64 *in) {
045   I64 c[16];
046   I64 i;
047   MemCpy(c,in,16*8);
048   for(i=253;i>=0;i--) {
049     fmul(c,c,c);
050     if(i!=2&&i!=4)
051       fmul(c,c,in);
052   }
053   MemCpy(out,c,16*8);
054 }
055 U0 Swap25519(I64 *p,I64 *q,I64 b) {
056   I64 t,i,c=~(b-1);
057   for(i=0;i!=16;i++) {
058     t=c&(p[i]^q[i]);
059     p[i]^=t;
060     q[i]^=t;
061   }
062 }
063 U0 Pack25519(U8 *out,I64 *in) {
064   I64 i,j,carry;
065   I64 m[16],t[16];
066   MemCpy(t,in,16*8);
067   Carry25519(t);
068   Carry25519(t);
069   Carry25519(t);
070   for(j=0;j!=2;j++) {
071     m[0]=t[0]-  0xffed;
072     for(i=1;i!=15;i++) {
073       m[i]=t[i]-0xffFF-(m[i-1]>>16&1);
074       m[i-1]&=0xffFF;
075     }
076     m[15]=t[15]-0x7fFF-(m[14]>>16&1);
077     carry=m[15]>>16&1;
078     m[14]&=0xffFF;
079     Swap25519(t,m,1-carry);
080   }
081   for(i=0;i!=16;i++) {
082     out[i*2](U16)=t[i](U16);
083   }
084 }
085 
086 //The Niravana Code,if you unserstand this then you may be a siddha.
087 U0 scalarmult(U8 *out,U8 *scalar,U8 *point,Bool clamp=FALSE) {
088   U8 clamped[32];
089   I64 bit, i;
090   I64 a[16], b[16], c[16], d[16], e[16], f[16], x[16];
091   static I64 _121665[16]={
092         0xDB41,1,0,0,
093         0,0,0,0,
094         0,0,0,0,
095         0,0,0,0
096         };
097   for (i = 0; i < 32; ++i) clamped[i] = scalar[i];
098   if(clamp)  {
099     clamped[0] &= 0xf8;
100     clamped[31] = (clamped[31] & 0x7f) | 0x40;
101   }
102   Unpack25519(x, point);
103   for (i = 0; i < 16; ++i) {
104     b[i] = x[i];
105     d[i] = a[i] = c[i] = 0;
106   }
107   a[0] = d[0] = 1;
108   for (i = 254; i >= 0; --i) {
109     bit = (clamped[i >> 3] >> (i & 7)) & 1;
110     Swap25519(a, b, bit);
111     Swap25519(c, d, bit);
112     fadd(e, a, c);
113     fsub(a, a, c);
114     fadd(c, b, d);
115     fsub(b, b, d);
116     fmul(d, e, e);
117     fmul(f, a, a);
118     fmul(a, c, a);
119     fmul(c, b, e);
120     fadd(e, a, c);
121     fsub(a, a, c);
122     fmul(b, a, a);
123     fsub(c, d, f);
124     fmul(a, c, _121665);
125     fadd(a, a, d);
126     fmul(c, c, a);
127     fmul(a, d, f);
128     fmul(d, b, x);
129     fmul(b, e, e);
130     Swap25519(a, b, bit);
131     Swap25519(c, d, bit);
132   }
133   finverse(c, c);
134   fmul(a, a, c);
135   Pack25519(out, a);
136 }
137 U0 GenPrivKey(U8 *out,U8 *data) {
138   static I64 _9[16]={
139         9,0,0,0,
140         0,0,0,0,
141         0,0,0,0,
142         0,0,0,0
143         };
144   scalarmult(out,data,_9);
145 }
146 U0 X25519(U8 * out,U8 *pk,U8 *sk) {
147  scalarmult(out, sk, pk);
148 }
149 #if __CMD_LINE__
150 DocMax;
151 U0 Test() {
152 //https://x25519.xargs.org/
153   I64 i=0;
154   U8 alice_priv[32];
155   U8 alice_pub[32];
156   U8 bob_priv[32];
157   U8 bob_pub[32];
158   U8 o[32];  
159 
160   for(i=0;i!=32;i++) {
161     alice_priv[i]=0;
162     bob_priv[i]=0;
163   }
164   alice_priv[0]=7;
165   bob_priv[0]=5;
166   GenPrivKey(alice_pub,alice_priv);
167   GenPrivKey(bob_pub,bob_priv);
168 "Alice Pub\n";
169   for(i=0;i!=32;i++)
170     "%02x\n",alice_pub[i];
171 "\nBob Pub\n";
172   for(i=0;i!=32;i++)
173     "%02x\n",bob_pub[i];
174 "\nThe Shared Pt.1\n";
175   X25519(o,bob_pub,alice_priv);
176   for(i=0;i!=32;i++)
177     "%02x\n",o[i];
178 "\nThe Shared Pt.2\n";
179   X25519(o,alice_pub,bob_priv);
180   for(i=0;i!=32;i++)
181     "%02x\n",o[i];
182 
183   DbgPrint("\n");
184 }
185 Test;
186 #endif