Develop and Download Open Source Software

Tera Term

Browse Subversion Repository

/[ttssh2]/trunk/ttssh2/ttxssh/ed25519_ge25519.c

Diff of /trunk/ttssh2/ttxssh/ed25519_ge25519.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

branches/ssh_ed25519/ttssh2/ttxssh/sftp.h revision 5495 by yutakapon, Sun Mar 2 15:17:04 2014 UTC branches/ssh_ed25519/ttssh2/ttxssh/ed25519_ge25519.c revision 5496 by yutakapon, Mon Mar 3 06:59:21 2014 UTC
# Line 1  Line 1 
1  /*  /* $OpenBSD: ge25519.c,v 1.3 2013/12/09 11:03:45 markus Exp $ */
2  Copyright (c) 2008-2012 TeraTerm Project  
3  All rights reserved.  /*
4     * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange,
5  Redistribution and use in source and binary forms, with or without modification,   * Peter Schwabe, Bo-Yin Yang.
6  are permitted provided that the following conditions are met:   * Copied from supercop-20130419/crypto_sign/ed25519/ref/ge25519.c
7     */
8    1. Redistributions of source code must retain the above copyright notice,  
9       this list of conditions and the following disclaimer.  #include "includes.h"
10    2. Redistributions in binary form must reproduce the above copyright notice,  
11       this list of conditions and the following disclaimer in the documentation  #include "fe25519.h"
12       and/or other materials provided with the distribution.  #include "sc25519.h"
13    3. The name of the author may not be used to endorse or promote products derived  #include "ge25519.h"
14       from this software without specific prior written permission.  
15    /*
16  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,   * Arithmetic on the twisted Edwards curve -x^2 + y^2 = 1 + dx^2y^2
17  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR   * with d = -(121665/121666) = 37095705934669439343138083508754565189542113879843219016388785533085940283555
18  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY   * Base point: (15112221349535400772501151409588531511454012693041857206046113283949847762202,46316835694926478169428394003475163141307993866256225615783033603165251855960);
19  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,   */
20  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,  
21  OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,  /* d */
22  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)  static const fe25519 ge25519_ecd = {{0xA3, 0x78, 0x59, 0x13, 0xCA, 0x4D, 0xEB, 0x75, 0xAB, 0xD8, 0x41, 0x41, 0x4D, 0x0A, 0x70, 0x00,
23  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY                        0x98, 0xE8, 0x79, 0x77, 0x79, 0x40, 0xC7, 0x8C, 0x73, 0xFE, 0x6F, 0x2B, 0xEE, 0x6C, 0x03, 0x52}};
24  OF SUCH DAMAGE.  /* 2*d */
25  */  static const fe25519 ge25519_ec2d = {{0x59, 0xF1, 0xB2, 0x26, 0x94, 0x9B, 0xD6, 0xEB, 0x56, 0xB1, 0x83, 0x82, 0x9A, 0x14, 0xE0, 0x00,
26                           0x30, 0xD1, 0xF3, 0xEE, 0xF2, 0x80, 0x8E, 0x19, 0xE7, 0xFC, 0xDF, 0x56, 0xDC, 0xD9, 0x06, 0x24}};
27  #ifndef __SFTP_H  /* sqrt(-1) */
28  #define __SFTP_H  static const fe25519 ge25519_sqrtm1 = {{0xB0, 0xA0, 0x0E, 0x4A, 0x27, 0x1B, 0xEE, 0xC4, 0x78, 0xE4, 0x2F, 0xAD, 0x06, 0x18, 0x43, 0x2F,
29                             0xA7, 0xD7, 0xFB, 0x3D, 0x99, 0x00, 0x4D, 0x2B, 0x0B, 0xDF, 0xC1, 0x4F, 0x80, 0x24, 0x83, 0x2B}};
30  // for debug mode  
31  #ifdef _DEBUG  #define ge25519_p3 ge25519
32  #define SFTP_DEBUG  
33  #endif  typedef struct
34    {
35  /* version */    fe25519 x;
36  #define SSH2_FILEXFER_VERSION           3    fe25519 z;
37      fe25519 y;
38  /* client to server */    fe25519 t;
39  #define SSH2_FXP_INIT                   1  } ge25519_p1p1;
40  #define SSH2_FXP_OPEN                   3  
41  #define SSH2_FXP_CLOSE                  4  typedef struct
42  #define SSH2_FXP_READ                   5  {
43  #define SSH2_FXP_WRITE                  6    fe25519 x;
44  #define SSH2_FXP_LSTAT                  7    fe25519 y;
45  #define SSH2_FXP_STAT_VERSION_0         7    fe25519 z;
46  #define SSH2_FXP_FSTAT                  8  } ge25519_p2;
47  #define SSH2_FXP_SETSTAT                9  
48  #define SSH2_FXP_FSETSTAT               10  typedef struct
49  #define SSH2_FXP_OPENDIR                11  {
50  #define SSH2_FXP_READDIR                12    fe25519 x;
51  #define SSH2_FXP_REMOVE                 13    fe25519 y;
52  #define SSH2_FXP_MKDIR                  14  } ge25519_aff;
53  #define SSH2_FXP_RMDIR                  15  
54  #define SSH2_FXP_REALPATH               16  
55  #define SSH2_FXP_STAT                   17  /* Packed coordinates of the base point */
56  #define SSH2_FXP_RENAME                 18  const ge25519 ge25519_base = {{{0x1A, 0xD5, 0x25, 0x8F, 0x60, 0x2D, 0x56, 0xC9, 0xB2, 0xA7, 0x25, 0x95, 0x60, 0xC7, 0x2C, 0x69,
57  #define SSH2_FXP_READLINK               19                                  0x5C, 0xDC, 0xD6, 0xFD, 0x31, 0xE2, 0xA4, 0xC0, 0xFE, 0x53, 0x6E, 0xCD, 0xD3, 0x36, 0x69, 0x21}},
58  #define SSH2_FXP_SYMLINK                20                                {{0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
59                                    0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66}},
60  /* server to client */                                {{0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
61  #define SSH2_FXP_VERSION                2                                  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
62  #define SSH2_FXP_STATUS                 101                                {{0xA3, 0xDD, 0xB7, 0xA5, 0xB3, 0x8A, 0xDE, 0x6D, 0xF5, 0x52, 0x51, 0x77, 0x80, 0x9F, 0xF0, 0x20,
63  #define SSH2_FXP_HANDLE                 102                                  0x7D, 0xE3, 0xAB, 0x64, 0x8E, 0x4E, 0xEA, 0x66, 0x65, 0x76, 0x8B, 0xD7, 0x0F, 0x5F, 0x87, 0x67}}};
64  #define SSH2_FXP_DATA                   103  
65  #define SSH2_FXP_NAME                   104  /* Multiples of the base point in affine representation */
66  #define SSH2_FXP_ATTRS                  105  static const ge25519_aff ge25519_base_multiples_affine[425] = {
67    #include "ge25519_base.data"
68  #define SSH2_FXP_EXTENDED               200  };
69  #define SSH2_FXP_EXTENDED_REPLY         201  
70    static void p1p1_to_p2(ge25519_p2 *r, const ge25519_p1p1 *p)
71  /* attributes */  {
72  #define SSH2_FILEXFER_ATTR_SIZE         0x00000001    fe25519_mul(&r->x, &p->x, &p->t);
73  #define SSH2_FILEXFER_ATTR_UIDGID       0x00000002    fe25519_mul(&r->y, &p->y, &p->z);
74  #define SSH2_FILEXFER_ATTR_PERMISSIONS  0x00000004    fe25519_mul(&r->z, &p->z, &p->t);
75  #define SSH2_FILEXFER_ATTR_ACMODTIME    0x00000008  }
76  #define SSH2_FILEXFER_ATTR_EXTENDED     0x80000000  
77    static void p1p1_to_p3(ge25519_p3 *r, const ge25519_p1p1 *p)
78  /* portable open modes */  {
79  #define SSH2_FXF_READ                   0x00000001    p1p1_to_p2((ge25519_p2 *)r, p);
80  #define SSH2_FXF_WRITE                  0x00000002    fe25519_mul(&r->t, &p->x, &p->y);
81  #define SSH2_FXF_APPEND                 0x00000004  }
82  #define SSH2_FXF_CREAT                  0x00000008  
83  #define SSH2_FXF_TRUNC                  0x00000010  static void ge25519_mixadd2(ge25519_p3 *r, const ge25519_aff *q)
84  #define SSH2_FXF_EXCL                   0x00000020  {
85      fe25519 a,b,t1,t2,c,d,e,f,g,h,qt;
86  /* statvfs@openssh.com f_flag flags */    fe25519_mul(&qt, &q->x, &q->y);
87  #define SSH2_FXE_STATVFS_ST_RDONLY      0x00000001    fe25519_sub(&a, &r->y, &r->x); /* A = (Y1-X1)*(Y2-X2) */
88  #define SSH2_FXE_STATVFS_ST_NOSUID      0x00000002    fe25519_add(&b, &r->y, &r->x); /* B = (Y1+X1)*(Y2+X2) */
89      fe25519_sub(&t1, &q->y, &q->x);
90  /* status messages */    fe25519_add(&t2, &q->y, &q->x);
91  #define SSH2_FX_OK                      0    fe25519_mul(&a, &a, &t1);
92  #define SSH2_FX_EOF                     1    fe25519_mul(&b, &b, &t2);
93  #define SSH2_FX_NO_SUCH_FILE            2    fe25519_sub(&e, &b, &a); /* E = B-A */
94  #define SSH2_FX_PERMISSION_DENIED       3    fe25519_add(&h, &b, &a); /* H = B+A */
95  #define SSH2_FX_FAILURE                 4    fe25519_mul(&c, &r->t, &qt); /* C = T1*k*T2 */
96  #define SSH2_FX_BAD_MESSAGE             5    fe25519_mul(&c, &c, &ge25519_ec2d);
97  #define SSH2_FX_NO_CONNECTION           6    fe25519_add(&d, &r->z, &r->z); /* D = Z1*2 */
98  #define SSH2_FX_CONNECTION_LOST         7    fe25519_sub(&f, &d, &c); /* F = D-C */
99  #define SSH2_FX_OP_UNSUPPORTED          8    fe25519_add(&g, &d, &c); /* G = D+C */
100  #define SSH2_FX_MAX                     8    fe25519_mul(&r->x, &e, &f);
101      fe25519_mul(&r->y, &h, &g);
102  /* Maximum packet that we are willing to send/accept */    fe25519_mul(&r->z, &g, &f);
103  #define SFTP_MAX_MSG_LENGTH     (256 * 1024)    fe25519_mul(&r->t, &e, &h);
104    }
105  #define DEFAULT_COPY_BUFLEN 32768   /* Size of buffer for up/download */  
106  #define DEFAULT_NUM_REQUESTS    64  /* # concurrent outstanding requests */  static void add_p1p1(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_p3 *q)
107    {
108  void sftp_do_init(PTInstVar pvar, Channel_t *c);    fe25519 a, b, c, d, t;
109  void sftp_response(PTInstVar pvar, Channel_t *c, unsigned char *data, unsigned int buflen);    
110      fe25519_sub(&a, &p->y, &p->x); /* A = (Y1-X1)*(Y2-X2) */
111  #endif    fe25519_sub(&t, &q->y, &q->x);
112      fe25519_mul(&a, &a, &t);
113      fe25519_add(&b, &p->x, &p->y); /* B = (Y1+X1)*(Y2+X2) */
114      fe25519_add(&t, &q->x, &q->y);
115      fe25519_mul(&b, &b, &t);
116      fe25519_mul(&c, &p->t, &q->t); /* C = T1*k*T2 */
117      fe25519_mul(&c, &c, &ge25519_ec2d);
118      fe25519_mul(&d, &p->z, &q->z); /* D = Z1*2*Z2 */
119      fe25519_add(&d, &d, &d);
120      fe25519_sub(&r->x, &b, &a); /* E = B-A */
121      fe25519_sub(&r->t, &d, &c); /* F = D-C */
122      fe25519_add(&r->z, &d, &c); /* G = D+C */
123      fe25519_add(&r->y, &b, &a); /* H = B+A */
124    }
125    
126    /* See http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#doubling-dbl-2008-hwcd */
127    static void dbl_p1p1(ge25519_p1p1 *r, const ge25519_p2 *p)
128    {
129      fe25519 a,b,c,d;
130      fe25519_square(&a, &p->x);
131      fe25519_square(&b, &p->y);
132      fe25519_square(&c, &p->z);
133      fe25519_add(&c, &c, &c);
134      fe25519_neg(&d, &a);
135    
136      fe25519_add(&r->x, &p->x, &p->y);
137      fe25519_square(&r->x, &r->x);
138      fe25519_sub(&r->x, &r->x, &a);
139      fe25519_sub(&r->x, &r->x, &b);
140      fe25519_add(&r->z, &d, &b);
141      fe25519_sub(&r->t, &r->z, &c);
142      fe25519_sub(&r->y, &d, &b);
143    }
144    
145    /* Constant-time version of: if(b) r = p */
146    static void cmov_aff(ge25519_aff *r, const ge25519_aff *p, unsigned char b)
147    {
148      fe25519_cmov(&r->x, &p->x, b);
149      fe25519_cmov(&r->y, &p->y, b);
150    }
151    
152    static unsigned char equal(signed char b,signed char c)
153    {
154      unsigned char ub = b;
155      unsigned char uc = c;
156      unsigned char x = ub ^ uc; /* 0: yes; 1..255: no */
157      crypto_uint32 y = x; /* 0: yes; 1..255: no */
158      y -= 1; /* 4294967295: yes; 0..254: no */
159      y >>= 31; /* 1: yes; 0: no */
160      return y;
161    }
162    
163    static unsigned char negative(signed char b)
164    {
165      unsigned long long x = b; /* 18446744073709551361..18446744073709551615: yes; 0..255: no */
166      x >>= 63; /* 1: yes; 0: no */
167      return x;
168    }
169    
170    static void choose_t(ge25519_aff *t, unsigned long long pos, signed char b)
171    {
172      /* constant time */
173      fe25519 v;
174      *t = ge25519_base_multiples_affine[5*pos+0];
175      cmov_aff(t, &ge25519_base_multiples_affine[5*pos+1],equal(b,1) | equal(b,-1));
176      cmov_aff(t, &ge25519_base_multiples_affine[5*pos+2],equal(b,2) | equal(b,-2));
177      cmov_aff(t, &ge25519_base_multiples_affine[5*pos+3],equal(b,3) | equal(b,-3));
178      cmov_aff(t, &ge25519_base_multiples_affine[5*pos+4],equal(b,-4));
179      fe25519_neg(&v, &t->x);
180      fe25519_cmov(&t->x, &v, negative(b));
181    }
182    
183    static void setneutral(ge25519 *r)
184    {
185      fe25519_setzero(&r->x);
186      fe25519_setone(&r->y);
187      fe25519_setone(&r->z);
188      fe25519_setzero(&r->t);
189    }
190    
191    /* ********************************************************************
192     *                    EXPORTED FUNCTIONS
193     ******************************************************************** */
194    
195    /* return 0 on success, -1 otherwise */
196    int ge25519_unpackneg_vartime(ge25519_p3 *r, const unsigned char p[32])
197    {
198      unsigned char par;
199      fe25519 t, chk, num, den, den2, den4, den6;
200      fe25519_setone(&r->z);
201      par = p[31] >> 7;
202      fe25519_unpack(&r->y, p);
203      fe25519_square(&num, &r->y); /* x = y^2 */
204      fe25519_mul(&den, &num, &ge25519_ecd); /* den = dy^2 */
205      fe25519_sub(&num, &num, &r->z); /* x = y^2-1 */
206      fe25519_add(&den, &r->z, &den); /* den = dy^2+1 */
207    
208      /* Computation of sqrt(num/den) */
209      /* 1.: computation of num^((p-5)/8)*den^((7p-35)/8) = (num*den^7)^((p-5)/8) */
210      fe25519_square(&den2, &den);
211      fe25519_square(&den4, &den2);
212      fe25519_mul(&den6, &den4, &den2);
213      fe25519_mul(&t, &den6, &num);
214      fe25519_mul(&t, &t, &den);
215    
216      fe25519_pow2523(&t, &t);
217      /* 2. computation of r->x = t * num * den^3 */
218      fe25519_mul(&t, &t, &num);
219      fe25519_mul(&t, &t, &den);
220      fe25519_mul(&t, &t, &den);
221      fe25519_mul(&r->x, &t, &den);
222    
223      /* 3. Check whether sqrt computation gave correct result, multiply by sqrt(-1) if not: */
224      fe25519_square(&chk, &r->x);
225      fe25519_mul(&chk, &chk, &den);
226      if (!fe25519_iseq_vartime(&chk, &num))
227        fe25519_mul(&r->x, &r->x, &ge25519_sqrtm1);
228    
229      /* 4. Now we have one of the two square roots, except if input was not a square */
230      fe25519_square(&chk, &r->x);
231      fe25519_mul(&chk, &chk, &den);
232      if (!fe25519_iseq_vartime(&chk, &num))
233        return -1;
234    
235      /* 5. Choose the desired square root according to parity: */
236      if(fe25519_getparity(&r->x) != (1-par))
237        fe25519_neg(&r->x, &r->x);
238    
239      fe25519_mul(&r->t, &r->x, &r->y);
240      return 0;
241    }
242    
243    void ge25519_pack(unsigned char r[32], const ge25519_p3 *p)
244    {
245      fe25519 tx, ty, zi;
246      fe25519_invert(&zi, &p->z);
247      fe25519_mul(&tx, &p->x, &zi);
248      fe25519_mul(&ty, &p->y, &zi);
249      fe25519_pack(r, &ty);
250      r[31] ^= fe25519_getparity(&tx) << 7;
251    }
252    
253    int ge25519_isneutral_vartime(const ge25519_p3 *p)
254    {
255      int ret = 1;
256      if(!fe25519_iszero(&p->x)) ret = 0;
257      if(!fe25519_iseq_vartime(&p->y, &p->z)) ret = 0;
258      return ret;
259    }
260    
261    /* computes [s1]p1 + [s2]p2 */
262    void ge25519_double_scalarmult_vartime(ge25519_p3 *r, const ge25519_p3 *p1, const sc25519 *s1, const ge25519_p3 *p2, const sc25519 *s2)
263    {
264      ge25519_p1p1 tp1p1;
265      ge25519_p3 pre[16];
266      unsigned char b[127];
267      int i;
268    
269      /* precomputation                                                        s2 s1 */
270      setneutral(pre);                                                      /* 00 00 */
271      pre[1] = *p1;                                                         /* 00 01 */
272      dbl_p1p1(&tp1p1,(ge25519_p2 *)p1);      p1p1_to_p3( &pre[2], &tp1p1); /* 00 10 */
273      add_p1p1(&tp1p1,&pre[1], &pre[2]);      p1p1_to_p3( &pre[3], &tp1p1); /* 00 11 */
274      pre[4] = *p2;                                                         /* 01 00 */
275      add_p1p1(&tp1p1,&pre[1], &pre[4]);      p1p1_to_p3( &pre[5], &tp1p1); /* 01 01 */
276      add_p1p1(&tp1p1,&pre[2], &pre[4]);      p1p1_to_p3( &pre[6], &tp1p1); /* 01 10 */
277      add_p1p1(&tp1p1,&pre[3], &pre[4]);      p1p1_to_p3( &pre[7], &tp1p1); /* 01 11 */
278      dbl_p1p1(&tp1p1,(ge25519_p2 *)p2);      p1p1_to_p3( &pre[8], &tp1p1); /* 10 00 */
279      add_p1p1(&tp1p1,&pre[1], &pre[8]);      p1p1_to_p3( &pre[9], &tp1p1); /* 10 01 */
280      dbl_p1p1(&tp1p1,(ge25519_p2 *)&pre[5]); p1p1_to_p3(&pre[10], &tp1p1); /* 10 10 */
281      add_p1p1(&tp1p1,&pre[3], &pre[8]);      p1p1_to_p3(&pre[11], &tp1p1); /* 10 11 */
282      add_p1p1(&tp1p1,&pre[4], &pre[8]);      p1p1_to_p3(&pre[12], &tp1p1); /* 11 00 */
283      add_p1p1(&tp1p1,&pre[1],&pre[12]);      p1p1_to_p3(&pre[13], &tp1p1); /* 11 01 */
284      add_p1p1(&tp1p1,&pre[2],&pre[12]);      p1p1_to_p3(&pre[14], &tp1p1); /* 11 10 */
285      add_p1p1(&tp1p1,&pre[3],&pre[12]);      p1p1_to_p3(&pre[15], &tp1p1); /* 11 11 */
286    
287      sc25519_2interleave2(b,s1,s2);
288    
289      /* scalar multiplication */
290      *r = pre[b[126]];
291      for(i=125;i>=0;i--)
292      {
293        dbl_p1p1(&tp1p1, (ge25519_p2 *)r);
294        p1p1_to_p2((ge25519_p2 *) r, &tp1p1);
295        dbl_p1p1(&tp1p1, (ge25519_p2 *)r);
296        if(b[i]!=0)
297        {
298          p1p1_to_p3(r, &tp1p1);
299          add_p1p1(&tp1p1, r, &pre[b[i]]);
300        }
301        if(i != 0) p1p1_to_p2((ge25519_p2 *)r, &tp1p1);
302        else p1p1_to_p3(r, &tp1p1);
303      }
304    }
305    
306    void ge25519_scalarmult_base(ge25519_p3 *r, const sc25519 *s)
307    {
308      signed char b[85];
309      int i;
310      ge25519_aff t;
311      sc25519_window3(b,s);
312    
313      choose_t((ge25519_aff *)r, 0, b[0]);
314      fe25519_setone(&r->z);
315      fe25519_mul(&r->t, &r->x, &r->y);
316      for(i=1;i<85;i++)
317      {
318        choose_t(&t, (unsigned long long) i, b[i]);
319        ge25519_mixadd2(r, &t);
320      }
321    }
Legend:
Removed from v.5495  
changed lines
  Added in v.5496
Back to OSDN">Back to OSDN
 ViewVC Help
Powered by ViewVC 1.1.26  
About OSDN
Find Software
Develop Software
Help