miracl_core_ed25519/ed25519/
big.rs

1/*
2 * Copyright (c) 2012-2020 MIRACL UK Ltd.
3 *
4 * This file is part of MIRACL Core
5 * (see https://github.com/miracl/core).
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 *     http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20use crate::arch;
21use crate::arch::Chunk;
22
23use crate::arch::DChunk;
24
25use miracl_core_bls12381::rand::RAND;
26use crate::ed25519::dbig::DBIG;
27
28pub const MODBYTES: usize = 32;
29pub const BASEBITS: usize = 56;
30
31pub const NLEN: usize = 1 + ((8 * MODBYTES - 1) / BASEBITS);
32pub const DNLEN: usize = 2 * NLEN;
33pub const BMASK: Chunk = (1 << BASEBITS) - 1;
34pub const HBITS: usize = BASEBITS / 2;
35pub const HMASK: Chunk = (1 << HBITS) - 1;
36pub const NEXCESS: isize = 1 << ((arch::CHUNK) - BASEBITS - 1);
37pub const BIGBITS: usize = MODBYTES * 8;
38
39#[derive(Copy)]
40pub struct BIG {
41    pub w: [Chunk; NLEN],
42}
43
44impl Clone for BIG {
45    fn clone(&self) -> BIG {
46        *self
47    }
48}
49
50#[cfg(feature = "std")]
51impl std::fmt::Debug for BIG {
52    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
53        write!(formatter, "{}", self.tostring())
54    }
55}
56
57#[cfg(feature = "std")]
58impl std::fmt::Display for BIG {
59    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
60        write!(formatter, "{}", self.tostring())
61    }
62}
63
64impl BIG {
65    pub const fn new() -> BIG {
66        BIG { w: [0; NLEN] }
67    }
68
69    pub fn new_int(x: isize) -> BIG {
70        let mut s = BIG::new();
71        s.w[0] = x as Chunk;
72        s
73    }
74
75    pub fn new_ints(a: &[Chunk]) -> BIG {
76        let mut s = BIG::new();
77        for i in 0..NLEN {
78            s.w[i] = a[i]
79        }
80        s
81    }
82
83    pub fn new_copy(y: &BIG) -> BIG {
84        let mut s = BIG::new();
85        for i in 0..NLEN {
86            s.w[i] = y.w[i]
87        }
88        s
89    }
90
91    pub fn new_big(y: &BIG) -> BIG {
92        let mut s = BIG::new();
93        for i in 0..NLEN {
94            s.w[i] = y.w[i]
95        }
96        s
97    }
98
99    pub fn new_dcopy(y: &DBIG) -> BIG {
100        let mut s = BIG::new();
101        for i in 0..NLEN {
102            s.w[i] = y.w[i]
103        }
104        s
105    }
106
107    pub fn get(&self, i: usize) -> Chunk {
108        self.w[i]
109    }
110
111    pub fn set(&mut self, i: usize, x: Chunk) {
112        self.w[i] = x;
113    }
114
115    pub fn xortop(&mut self, x: Chunk) {
116        self.w[NLEN - 1] ^= x;
117    }
118
119    pub fn ortop(&mut self, x: Chunk) {
120        self.w[NLEN - 1] |= x;
121    }
122
123    /* test for zero */
124    pub fn iszilch(&self) -> bool {
125        let mut d = 0 as Chunk;
126        for i in 0..NLEN {
127            d |= self.w[i];
128        }
129        (1 & ((d-1)>>BASEBITS)) != 0
130    }
131
132    /* set to zero */
133    pub fn zero(&mut self) {
134        for i in 0..NLEN {
135            self.w[i] = 0
136        }
137    }
138
139    /* Test for equal to one */
140    pub fn isunity(&self) -> bool {
141        let mut d = 0 as Chunk;
142        for i in 1..NLEN {
143            d |= self.w[i];
144        }
145        (1 & ((d-1)>>BASEBITS) & (((self.w[0]^1)-1)>>BASEBITS)) != 0
146    }
147
148    /* set to one */
149    pub fn one(&mut self) {
150        self.w[0] = 1;
151        for i in 1..NLEN {
152            self.w[i] = 0;
153        }
154    }
155
156    /* Copy from another BIG */
157    pub fn copy(&mut self, x: &BIG) {
158        for i in 0..NLEN {
159            self.w[i] = x.w[i]
160        }
161    }
162
163    pub fn dcopy(&mut self, x: &DBIG) {
164        for i in 0..NLEN {
165            self.w[i] = x.w[i]
166        }
167    }
168
169    /* Get top and bottom half of =x*y+c+r */
170    pub fn muladd(a: Chunk, b: Chunk, c: Chunk, r: Chunk) -> (Chunk, Chunk) {
171        let prod: DChunk = (a as DChunk) * (b as DChunk) + (c as DChunk) + (r as DChunk);
172        let bot = (prod & (BMASK as DChunk)) as Chunk;
173        let top = (prod >> BASEBITS) as Chunk;
174        (top, bot)
175    }
176
177    /* normalise BIG - force all digits < 2^BASEBITS */
178    pub fn norm(&mut self) -> Chunk {
179        let mut carry = self.w[0]>>BASEBITS;
180        self.w[0] &= BMASK;
181        for i in 1..NLEN - 1 {
182            let d = self.w[i] + carry;
183            self.w[i] = d & BMASK;
184            carry = d >> BASEBITS;
185        }
186        self.w[NLEN - 1] += carry;
187        (self.w[NLEN - 1] >> ((8 * MODBYTES) % BASEBITS)) as Chunk
188    }
189
190    /* Conditional swap of two bigs depending on d using XOR - no branches */
191    pub fn cswap(&mut self, b: &mut BIG, d: isize) -> Chunk {
192        let c = -d as Chunk;
193        let mut w=0 as Chunk;
194        let r=self.w[0]^b.w[1];
195        let mut ra=r.wrapping_add(r); ra >>= 1;
196        for i in 0..NLEN {
197            let mut t = c & (self.w[i] ^ b.w[i]);
198            t^=r;
199            let mut e=self.w[i]^t; w^=e;
200            self.w[i]=e^ra; 
201            e=b.w[i]^t;  w^=e;
202            b.w[i]=e^ra;
203        }
204        return w;
205    }
206
207    pub fn cmove(&mut self, g: &BIG, d: isize)  -> Chunk {
208        let b = -d as Chunk;
209        let mut w=0 as Chunk;
210        let r=self.w[0]^g.w[1];
211        let mut ra=r.wrapping_add(r); ra >>= 1;
212        for i in 0..NLEN {
213            let mut t = b & (self.w[i] ^ g.w[i]);
214            t^=r;
215            let e=self.w[i]^t; w^=e;
216            self.w[i]=e^ra; 
217        }
218        return w;
219    }
220
221    /* Shift right by less than a word */
222    pub fn fshr(&mut self, k: usize) -> isize {
223        let n = k;
224        let w = self.w[0] & ((1 << n) - 1); /* shifted out part */
225        for i in 0..NLEN - 1 {
226            self.w[i] = (self.w[i] >> k) | ((self.w[i + 1] << (BASEBITS - n)) & BMASK);
227        }
228        self.w[NLEN - 1] >>= k;
229        w as isize
230    }
231
232    /* general shift right */
233    pub fn shr(&mut self, k: usize) {
234        let n = k % BASEBITS;
235        let m = k / BASEBITS;
236        for i in 0..NLEN - m - 1 {
237            self.w[i] = (self.w[m + i] >> n) | ((self.w[m + i + 1] << (BASEBITS - n)) & BMASK)
238        }
239        self.w[NLEN - m - 1] = self.w[NLEN - 1] >> n;
240        for i in NLEN - m..NLEN {
241            self.w[i] = 0
242        }
243    }
244
245    /* Shift right by less than a word */
246    pub fn fshl(&mut self, k: usize) -> isize {
247        let n = k;
248        self.w[NLEN - 1] = (self.w[NLEN - 1] << n) | (self.w[NLEN - 2] >> (BASEBITS - n));
249        for i in (1..NLEN - 1).rev() {
250            self.w[i] = ((self.w[i] << k) & BMASK) | (self.w[i - 1] >> (BASEBITS - n));
251        }
252        self.w[0] = (self.w[0] << n) & BMASK;
253        (self.w[NLEN - 1] >> ((8 * MODBYTES) % BASEBITS)) as isize /* return excess - only used in ff.c */
254    }
255
256    /* general shift left */
257    pub fn shl(&mut self, k: usize) {
258        let n = k % BASEBITS;
259        let m = k / BASEBITS;
260
261        self.w[NLEN - 1] = self.w[NLEN - 1 - m] << n;
262        if NLEN >= m + 2 {
263            self.w[NLEN - 1] |= self.w[NLEN - m - 2] >> (BASEBITS - n)
264        }
265        for i in (m + 1..NLEN - 1).rev() {
266            self.w[i] = ((self.w[i - m] << n) & BMASK) | (self.w[i - m - 1] >> (BASEBITS - n));
267        }
268        self.w[m] = (self.w[0] << n) & BMASK;
269        for i in 0..m {
270            self.w[i] = 0
271        }
272    }
273
274    /* return number of bits */
275    pub fn nbits(&self) -> usize {
276        let mut k = NLEN - 1;
277        let mut s = BIG::new_copy(&self);
278        s.norm();
279        while (k as isize) >= 0 && s.w[k] == 0 {
280            k = k.wrapping_sub(1)
281        }
282        if (k as isize) < 0 {
283            return 0;
284        }
285        let mut bts = BASEBITS * k;
286        let mut c = s.w[k];
287        while c != 0 {
288            c /= 2;
289            bts += 1;
290        }
291        bts
292    }
293
294    /* Convert to Hex String */
295//#[cfg(feature = "std")]
296#[cfg(not(feature = "no_std"))]
297    pub fn tostring(&self) -> String {
298        let mut s = String::new();
299        let mut len = self.nbits();
300
301        if len % 4 == 0 {
302            len /= 4;
303        } else {
304            len /= 4;
305            len += 1;
306        }
307        let mb = (MODBYTES * 2) as usize;
308        if len < mb {
309            len = mb
310        }
311
312        for i in (0..len).rev() {
313            let mut b = BIG::new_copy(&self);
314            b.shr(i * 4);
315            s = s + &format!("{:X}", b.w[0] & 15);
316        }
317        s
318    }
319
320#[cfg(feature = "std")]
321    pub fn fromstring(val: String) -> BIG {
322        let mut res = BIG::new();
323        let len = val.len();
324        let op = &val[0..1];
325        let n = u8::from_str_radix(op, 16).unwrap();
326        res.w[0] += n as Chunk;
327        for i in 1..len {
328            res.shl(4);
329            let op = &val[i..i+1];
330            let n = u8::from_str_radix(op, 16).unwrap();
331            res.w[0] += n as Chunk;
332        }
333        res
334    }
335
336    pub fn add(&mut self, r: &BIG) {
337        for i in 0..NLEN {
338            self.w[i] += r.w[i]
339        }
340    }
341
342    pub fn or(&mut self, r: &BIG) {
343        for i in 0..NLEN {
344            self.w[i] |= r.w[i]
345        }
346    }
347
348    pub fn dbl(&mut self) {
349        for i in 0..NLEN {
350            self.w[i] += self.w[i]
351        }
352    }
353
354    /* return this+x */
355    pub fn plus(&self, x: &BIG) -> BIG {
356        let mut s = BIG::new();
357        for i in 0..NLEN {
358            s.w[i] = self.w[i] + x.w[i];
359        }
360        s.norm();
361        s
362    }
363
364    pub fn inc(&mut self, x: isize) {
365        self.norm();
366        self.w[0] += x as Chunk;
367    }
368
369    /* return self-x */
370    pub fn minus(&self, x: &BIG) -> BIG {
371        let mut d = BIG::new();
372        for i in 0..NLEN {
373            d.w[i] = self.w[i] - x.w[i];
374        }
375        d
376    }
377
378    /* self-=x */
379    pub fn sub(&mut self, x: &BIG) {
380        for i in 0..NLEN {
381            self.w[i] -= x.w[i];
382        }
383    }
384
385    /* reverse subtract this=x-this */
386
387    pub fn rsub(&mut self, x: &BIG) {
388        for i in 0..NLEN {
389            self.w[i] = x.w[i] - self.w[i]
390        }
391    }
392
393    /* self-=x, where x is int */
394    pub fn dec(&mut self, x: isize) {
395        self.norm();
396        self.w[0] -= x as Chunk;
397    }
398
399    /* self*=x, where x is small int<NEXCESS */
400    pub fn imul(&mut self, c: isize) {
401        for i in 0..NLEN {
402            self.w[i] *= c as Chunk;
403        }
404    }
405
406    /* convert this BIG to byte array */
407    pub fn tobytearray(&self, b: &mut [u8], n: usize) {
408        let mut c = BIG::new_copy(self);
409        c.norm();
410
411        for i in (0..(MODBYTES as usize)).rev() {
412            b[i + n] = (c.w[0] & 0xff) as u8;
413            c.fshr(8);
414        }
415    }
416
417    /* convert from byte array to BIG */
418    pub fn frombytearray(b: &[u8], n: usize) -> BIG {
419        let mut m = BIG::new();
420        for i in 0..(MODBYTES as usize) {
421            m.fshl(8);
422            m.w[0] += b[i + n] as Chunk;
423        }
424        m
425    }
426
427    pub fn tobytes(&self, b: &mut [u8]) {
428        self.tobytearray(b, 0)
429    }
430
431    pub fn frombytes(b: &[u8]) -> BIG {
432       BIG::frombytearray(b, 0)
433    }
434
435    /* self*=x, where x is >NEXCESS */
436    pub fn pmul(&mut self, c: isize) -> Chunk {
437        let mut carry = 0 as Chunk;
438        for i in 0..NLEN {
439            let ak = self.w[i];
440            let tuple = BIG::muladd(ak, c as Chunk, carry, 0 as Chunk);
441            carry = tuple.0;
442            self.w[i] = tuple.1;
443        }
444        carry
445    }
446
447    /* self*=c and catch overflow in DBIG */
448    pub fn pxmul(&mut self, c: isize) -> DBIG {
449        let mut m = DBIG::new();
450        let mut carry = 0 as Chunk;
451        for j in 0..NLEN {
452            let tuple = BIG::muladd(self.w[j], c as Chunk, carry, m.w[j]);
453            carry = tuple.0;
454            m.w[j] = tuple.1;
455        }
456        m.w[NLEN] = carry;
457        m
458    }
459
460    /* divide by 3 */
461    pub fn div3(&mut self) -> Chunk {
462        let mut carry = 0 as Chunk;
463        self.norm();
464        let base = 1 << BASEBITS;
465        for i in (0..NLEN).rev() {
466            let ak = carry * base + self.w[i];
467            self.w[i] = ak / 3;
468            carry = ak % 3;
469        }
470        carry
471    }
472
473    /* return a*b where result fits in a BIG */
474    pub fn smul(a: &BIG, b: &BIG) -> BIG {
475        let mut c = BIG::new();
476        for i in 0..NLEN {
477            let mut carry = 0 as Chunk;
478            for j in 0..NLEN {
479                if i + j < NLEN {
480                    let tuple = BIG::muladd(a.w[i], b.w[j], carry, c.w[i + j]);
481                    carry = tuple.0;
482                    c.w[i + j] = tuple.1;
483                }
484            }
485        }
486        c
487    }
488
489    /* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */
490    pub fn comp(a: &BIG, b: &BIG) -> isize {
491        let mut gt = 0 as Chunk;
492        let mut eq = 1 as Chunk;
493        for i in (0..NLEN).rev() {
494 		    gt |= ((b.w[i]-a.w[i]) >> BASEBITS) & eq;
495		    eq &= ((b.w[i]^a.w[i])-1) >> BASEBITS;
496        }
497        (gt+gt+eq-1) as isize
498    }
499
500    /* set x = x mod 2^m */
501    pub fn mod2m(&mut self, m: usize) {
502        let wd = m / BASEBITS;
503        let bt = m % BASEBITS;
504        let msk = (1 << bt) - 1;
505        self.w[wd] &= msk;
506        for i in wd + 1..NLEN {
507            self.w[i] = 0
508        }
509    }
510
511    /* Arazi and Qi inversion mod 256 */
512    pub fn invmod256(a: isize) -> isize {
513        let mut t1: isize = 0;
514        let mut c = (a >> 1) & 1;
515        t1 += c;
516        t1 &= 1;
517        t1 = 2 - t1;
518        t1 <<= 1;
519        let mut u = t1 + 1;
520
521        // i=2
522        let mut b = a & 3;
523        t1 = u * b;
524        t1 >>= 2;
525        c = (a >> 2) & 3;
526        let mut t2 = (u * c) & 3;
527        t1 += t2;
528        t1 *= u;
529        t1 &= 3;
530        t1 = 4 - t1;
531        t1 <<= 2;
532        u += t1;
533
534        // i=4
535        b = a & 15;
536        t1 = u * b;
537        t1 >>= 4;
538        c = (a >> 4) & 15;
539        t2 = (u * c) & 15;
540        t1 += t2;
541        t1 *= u;
542        t1 &= 15;
543        t1 = 16 - t1;
544        t1 <<= 4;
545        u += t1;
546
547        u
548    }
549
550    /* return parity */
551    pub fn parity(&self) -> isize {
552        (self.w[0] % 2) as isize
553    }
554
555    /* return n-th bit */
556    pub fn bit(&self, n: usize) -> isize {
557        return ((self.w[n / (BASEBITS as usize)] & (1 << (n % BASEBITS))) >> (n%BASEBITS)) as isize;
558
559
560 //       if (self.w[n / (BASEBITS as usize)] & (1 << (n % BASEBITS))) > 0 {
561//            1
562//        } else {
563//            0
564//        }
565    }
566
567    /* return n last bits */
568    pub fn lastbits(&mut self, n: usize) -> isize {
569        let msk = ((1 << n) - 1) as Chunk;
570        self.norm();
571        (self.w[0] & msk) as isize
572    }
573
574    /* a=1/a mod 2^256. This is very fast! */
575    pub fn invmod2m(&mut self) {
576        let mut u = BIG::new();
577        let mut b = BIG::new();
578        let mut c = BIG::new();
579
580        u.inc(BIG::invmod256(self.lastbits(8)));
581
582        let mut i = 8;
583        while i < BIGBITS {
584            u.norm();
585            b.copy(self);
586            b.mod2m(i);
587            let mut t1 = BIG::smul(&u, &b);
588            t1.shr(i);
589            c.copy(self);
590            c.shr(i);
591            c.mod2m(i);
592
593            let mut t2 = BIG::smul(&u, &c);
594            t2.mod2m(i);
595            t1.add(&t2);
596            t1.norm();
597            b = BIG::smul(&t1, &u);
598            t1.copy(&b);
599            t1.mod2m(i);
600
601            t2.one();
602            t2.shl(i);
603            t1.rsub(&t2);
604            t1.norm();
605            t1.shl(i);
606            u.add(&t1);
607            i <<= 1;
608        }
609        u.mod2m(BIGBITS);
610        self.copy(&u);
611        self.norm();
612    }
613
614// Set self=self mod m in constant time (if bd is known at compile time)
615// bd is Max number of bits in b - Actual number of bits in m
616    pub fn ctmod(&mut self,m:&BIG,bd:usize) {
617        let mut k=bd;
618        let mut r=BIG::new();
619        let mut c=BIG::new_copy(m);
620        self.norm();
621
622        c.shl(k);
623        loop {
624            r.copy(self);
625            r.sub(&c);
626            r.norm();
627            self.cmove(&r,(1 - ((r.w[NLEN - 1] >> (arch::CHUNK - 1)) & 1)) as isize);
628            if k==0 {break;}
629            c.fshr(1);
630            k -= 1;  
631        }
632    }
633
634    /* reduce self mod m */
635    pub fn rmod(&mut self, m: &BIG) {
636        let ss=self.nbits() as isize;
637        let ms=m.nbits() as isize;
638        let mut k=(ss-ms) as usize;
639        if ss<ms {k=0;}
640        self.ctmod(m,k);
641    }
642
643    pub fn ctdiv(&mut self, m:&BIG, bd:usize) {
644        let mut k=bd; 
645        self.norm();
646        let mut e = BIG::new_int(1);
647        let mut a = BIG::new_copy(self);
648        let mut c = BIG::new_copy(m);
649        let mut r = BIG::new();
650        self.zero(); 
651        
652        c.shl(k);
653        e.shl(k);
654
655        loop {
656            r.copy(&a);
657            r.sub(&c);
658            r.norm();
659            let d = (1 - ((r.w[NLEN - 1] >> (arch::CHUNK - 1)) & 1)) as isize;
660            a.cmove(&r, d);
661            r.copy(self);
662            r.add(&e);
663            r.norm();
664            self.cmove(&r, d);
665            if k==0 {break;}
666            k -= 1;
667            c.fshr(1);
668            e.fshr(1);
669        }    
670    }
671
672    /* divide self by m */
673    pub fn div(&mut self, m: &BIG) {
674        let ss=self.nbits() as isize;
675        let ms=m.nbits() as isize;
676        let mut k=(ss-ms) as usize;
677        if ss<ms {k=0;}
678        self.ctdiv(m,k);
679    }
680
681    /* get 8*MODBYTES size random number */
682    pub fn random(rng: &mut impl RAND) -> BIG {
683        let mut m = BIG::new();
684        let mut j = 0;
685        let mut r: u8 = 0;
686        /* generate random BIG */
687
688        for _ in 0..8 * (MODBYTES as usize) {
689            if j == 0 {
690                r = rng.getbyte()
691            } else {
692                r >>= 1
693            }
694
695            let b = (r as Chunk) & 1;
696            m.shl(1);
697            m.w[0] += b;
698            j += 1;
699            j &= 7;
700        }
701        m
702    }
703
704    /* Create random BIG in portable way, one bit at a time */
705    pub fn randomnum(q: &BIG, rng: &mut impl RAND) -> BIG {
706        let mut d = DBIG::new();
707        let mut j = 0;
708        let mut r: u8 = 0;
709        let t = BIG::new_copy(q);
710        for _ in 0..2 * t.nbits() {
711            if j == 0 {
712                r = rng.getbyte();
713            } else {
714                r >>= 1
715            }
716
717            let b = (r as Chunk) & 1;
718            d.shl(1);
719            d.w[0] += b;
720            j += 1;
721            j &= 7;
722        }
723        d.dmod(q)
724    }
725
726/* create randum BIG less than r and less than trunc bits */
727    pub fn randtrunc(q: &BIG, trunc: usize, rng: &mut impl RAND) -> BIG {
728        let mut m=BIG::randomnum(q,rng);
729	    if q.nbits() > trunc {
730	        m.mod2m(trunc);
731	    }
732	    m
733    }
734
735    /* Jacobi Symbol (this/p). Returns 0, 1 or -1 */
736    pub fn jacobi(&mut self, p: &BIG) -> isize {
737        let mut m: usize = 0;
738        let mut t = BIG::new();
739        let mut x = BIG::new();
740        let mut n = BIG::new();
741        let zilch = BIG::new();
742        let one = BIG::new_int(1);
743        if p.parity() == 0 || BIG::comp(self, &zilch) == 0 || BIG::comp(p, &one) <= 0 {
744            return 0;
745        }
746        self.norm();
747
748        x.copy(self);
749        n.copy(p);
750        x.rmod(p);
751
752        while BIG::comp(&n, &one) > 0 {
753            if BIG::comp(&x, &zilch) == 0 {
754                return 0;
755            }
756            let n8 = n.lastbits(3) as usize;
757            let mut k = 0;
758            while x.parity() == 0 {
759                k += 1;
760                x.shr(1);
761            }
762            if k % 2 == 1 {
763                m += (n8 * n8 - 1) / 8
764            }
765            m += (n8 - 1) * ((x.lastbits(2) as usize) - 1) / 4;
766            t.copy(&n);
767            t.rmod(&x);
768            n.copy(&x);
769            x.copy(&t);
770            m %= 2;
771        }
772        if m == 0 {
773            1
774        } else {
775            -1
776        }
777    }
778
779// Set self=1/self mod p. Binary method 
780// NOTE: This function is NOT side-channel safe
781// If a is a secret then ALWAYS calculate 1/a = m*(1/am) mod p 
782// where m is a random masking value
783    pub fn invmodp(&mut self, p: &BIG) {
784        self.rmod(p);
785	    if self.iszilch() {return;}
786        let mut u = BIG::new_copy(self);
787        let mut v = BIG::new_copy(p);
788        let mut x1 = BIG::new_int(1);
789        let mut x2 = BIG::new();
790        let mut t = BIG::new();
791        let one = BIG::new_int(1);
792
793        while (BIG::comp(&u, &one) != 0) && (BIG::comp(&v, &one) != 0) {
794            while u.parity() == 0 {
795                u.fshr(1);
796                t.copy(&x1);
797                t.add(p);
798                x1.cmove(&t,x1.parity());
799                x1.norm();
800                x1.fshr(1);
801            }
802            while v.parity() == 0 {
803                v.fshr(1);
804                t.copy(&x2);
805                t.add(p);
806                x2.cmove(&t,x2.parity());
807                x2.norm();
808                x2.fshr(1);
809            }
810            if BIG::comp(&u, &v) >= 0 {
811                u.sub(&v);
812                u.norm();
813                t.copy(&x1);
814                t.add(p);
815                x1.cmove(&t,(BIG::comp(&x1,&x2)>>1)&1);
816                x1.sub(&x2);
817                x1.norm();
818            } else {
819                v.sub(&u);
820                v.norm();
821                t.copy(&x2);
822                t.add(p);
823                x2.cmove(&t,(BIG::comp(&x2,&x1)>>1)&1);
824                x2.sub(&x1);
825                x2.norm();
826            }
827        }
828        self.copy(&x1);
829        self.cmove(&x2,BIG::comp(&u,&one)&1);
830    }
831
832    /* return a*b as DBIG - Simple Karatsuba */
833    pub fn mul(a: &BIG, b: &BIG) -> DBIG {
834        let mut c = DBIG::new();
835        let rm = BMASK as DChunk;
836        let rb = BASEBITS;
837
838        let mut d: [DChunk; DNLEN] = [0; DNLEN];
839        for i in 0..NLEN {
840            d[i] = (a.w[i] as DChunk) * (b.w[i] as DChunk);
841        }
842        let mut s = d[0];
843        let mut t = s;
844        c.w[0] = (t & rm) as Chunk;
845        t >>= rb;
846        for k in 1..NLEN {
847            s += d[k];
848            t += s;
849            for i in 1 + k / 2..k + 1 {
850                t += ((a.w[i] - a.w[k - i]) as DChunk) * ((b.w[k - i] - b.w[i]) as DChunk)
851            }
852            c.w[k] = (t & rm) as Chunk;
853            t >>= rb;
854        }
855        for k in NLEN..2 * NLEN - 1 {
856            s -= d[k - NLEN];
857            t += s;
858            let mut i = 1 + k / 2;
859            while i < NLEN {
860                t += ((a.w[i] - a.w[k - i]) as DChunk) * ((b.w[k - i] - b.w[i]) as DChunk);
861                i += 1;
862            }
863
864            c.w[k] = (t & rm) as Chunk;
865            t >>= rb;
866        }
867        c.w[2 * NLEN - 1] = t as Chunk;
868        c
869    }
870
871    /* return a^2 as DBIG */
872    pub fn sqr(a: &BIG) -> DBIG {
873        let mut c = DBIG::new();
874        let rm = BMASK as DChunk;
875        let rb = BASEBITS;
876
877        let mut t = (a.w[0] as DChunk) * (a.w[0] as DChunk);
878        c.w[0] = (t & rm) as Chunk;
879        let mut co = t >> rb;
880
881        let mut j = 1;
882        while j < NLEN - 1 {
883            t = (a.w[j] as DChunk) * (a.w[0] as DChunk);
884            for i in 1..(j + 1) / 2 {
885                t += (a.w[j - i] as DChunk) * (a.w[i] as DChunk);
886            }
887            t += t;
888            t += co;
889            c.w[j] = (t & rm) as Chunk;
890            co = t >> rb;
891            j += 1;
892            t = (a.w[j] as DChunk) * (a.w[0] as DChunk);
893            for i in 1..(j + 1) / 2 {
894                t += (a.w[j - i] as DChunk) * (a.w[i] as DChunk);
895            }
896            t += t;
897            t += co;
898            t += (a.w[j / 2] as DChunk) * (a.w[j / 2] as DChunk);
899            c.w[j] = (t & rm) as Chunk;
900            co = t >> rb;
901            j += 1;
902        }
903
904        j = NLEN + (NLEN % 2) - 1;
905        while j < DNLEN - 3 {
906            t = (a.w[NLEN - 1] as DChunk) * (a.w[j + 1 - NLEN] as DChunk);
907            for i in j + 2 - NLEN..(j + 1) / 2 {
908                t += (a.w[j - i] as DChunk) * (a.w[i] as DChunk);
909            }
910            t += t;
911            t += co;
912            c.w[j] = (t & rm) as Chunk;
913            co = t >> rb;
914            j += 1;
915            t = (a.w[NLEN - 1] as DChunk) * (a.w[j + 1 - NLEN] as DChunk);
916            for i in j + 2 - NLEN..(j + 1) / 2 {
917                t += (a.w[j - i] as DChunk) * (a.w[i] as DChunk);
918            }
919            t += t;
920            t += co;
921            t += (a.w[j / 2] as DChunk) * (a.w[j / 2] as DChunk);
922            c.w[j] = (t & rm) as Chunk;
923            co = t >> rb;
924            j += 1;
925        }
926
927        t = (a.w[NLEN - 2] as DChunk) * (a.w[NLEN - 1] as DChunk);
928        t += t;
929        t += co;
930        c.w[DNLEN - 3] = (t & rm) as Chunk;
931        co = t >> rb;
932
933        t = (a.w[NLEN - 1] as DChunk) * (a.w[NLEN - 1] as DChunk) + co;
934        c.w[DNLEN - 2] = (t & rm) as Chunk;
935        co = t >> rb;
936        c.w[DNLEN - 1] = co as Chunk;
937
938        c
939    }
940
941    /* Montgomery reduction */
942    pub fn monty(md: &BIG, mc: Chunk, d: &mut DBIG) -> BIG {
943        let mut b = BIG::new();
944        let rm = BMASK as DChunk;
945        let rb = BASEBITS;
946
947        let mut dd: [DChunk; NLEN] = [0; NLEN];
948        let mut v: [Chunk; NLEN] = [0; NLEN];
949
950        b.zero();
951
952        let mut t = d.w[0] as DChunk;
953        v[0] = (((t & rm) as Chunk).wrapping_mul(mc)) & BMASK;
954        t += (v[0] as DChunk) * (md.w[0] as DChunk);
955        t = (d.w[1] as DChunk) + (t >> rb);
956        let mut s: DChunk = 0;
957        for k in 1..NLEN {
958            t = t + s + (v[0] as DChunk) * (md.w[k] as DChunk);
959            let mut i = 1 + k / 2;
960            while i < k {
961                t += ((v[k - i] - v[i]) as DChunk) * ((md.w[i] - md.w[k - i]) as DChunk);
962                i += 1;
963            }
964            v[k] = (((t & rm) as Chunk).wrapping_mul(mc)) & BMASK;
965            t += (v[k] as DChunk) * (md.w[0] as DChunk);
966            t = (d.w[k + 1] as DChunk) + (t >> rb);
967            dd[k] = (v[k] as DChunk) * (md.w[k] as DChunk);
968            s += dd[k];
969        }
970
971        for k in NLEN..2 * NLEN - 1 {
972            t += s;
973            let mut i = 1 + k / 2;
974            while i < NLEN {
975                t += ((v[k - i] - v[i]) as DChunk) * ((md.w[i] - md.w[k - i]) as DChunk);
976                i += 1;
977            }
978            b.w[k - NLEN] = (t & rm) as Chunk;
979            t = (d.w[k + 1] as DChunk) + (t >> rb);
980            s -= dd[k + 1 - NLEN];
981        }
982        b.w[NLEN - 1] = (t & rm) as Chunk;
983        b
984    }
985
986    /* Fast combined shift, subtract and norm. Return sign of result */
987    pub fn ssn(r: &mut BIG, a: &BIG, m: &mut BIG) -> isize {
988        let n = NLEN - 1;
989        m.w[0] = (m.w[0] >> 1) | ((m.w[1] << (BASEBITS - 1)) & BMASK);
990        r.w[0] = a.w[0] - m.w[0];
991        let mut carry = r.w[0] >> BASEBITS;
992        r.w[0] &= BMASK;
993        for i in 1..n {
994            m.w[i] = (m.w[i] >> 1) | ((m.w[i + 1] << (BASEBITS - 1)) & BMASK);
995            r.w[i] = a.w[i] - m.w[i] + carry;
996            carry = r.w[i] >> BASEBITS;
997            r.w[i] &= BMASK;
998        }
999        m.w[n] >>= 1;
1000        r.w[n] = a.w[n] - m.w[n] + carry;
1001        ((r.w[n] >> (arch::CHUNK - 1)) & 1) as isize
1002    }
1003
1004    /* return a*b mod m */
1005    pub fn modmul(a1: &BIG, b1: &BIG, m: &BIG) -> BIG {
1006        let mut a = BIG::new_copy(a1);
1007        let mut b = BIG::new_copy(b1);
1008        a.rmod(m);
1009        b.rmod(m);
1010        let mut d = BIG::mul(&a, &b);
1011        d.ctdmod(m,m.nbits())
1012    }
1013
1014    /* return a^2 mod m */
1015    pub fn modsqr(a1: &BIG, m: &BIG) -> BIG {
1016        let mut a = BIG::new_copy(a1);
1017        a.rmod(m);
1018        let mut d = BIG::sqr(&a);
1019        d.ctdmod(m,m.nbits())
1020    }
1021
1022    /* return -a mod m */
1023    pub fn modneg(a1: &BIG, m: &BIG) -> BIG {
1024        let mut a = BIG::new_copy(a1);
1025        a.rmod(m);
1026	    a.rsub(m);
1027	    a.norm();
1028        a
1029    }
1030
1031    /* return a+b mod m */
1032    pub fn modadd(a1: &BIG, b1: &BIG, m: &BIG) -> BIG {
1033        let mut a = BIG::new_copy(a1);
1034        let mut b = BIG::new_copy(b1);
1035        a.rmod(m);
1036        b.rmod(m);
1037        a.add(&b); a.norm();
1038        a.ctmod(m,1);
1039        a
1040    }
1041
1042    /* return this^e mod m */
1043    pub fn powmod(&mut self, e1: &BIG, m: &BIG) -> BIG {
1044        self.norm();
1045        let mut e = BIG::new_copy(e1);
1046        e.norm();
1047        let mut a = BIG::new_int(1);
1048        let mut z = BIG::new_copy(&e);
1049        let mut s = BIG::new_copy(self);
1050        loop {
1051            let bt = z.parity();
1052            z.fshr(1);
1053            if bt == 1 {
1054                a = BIG::modmul(&a, &s, m)
1055            }
1056            if z.iszilch() {
1057                break;
1058            }
1059            s = BIG::modsqr(&s, m);
1060        }
1061        a
1062    }
1063}
miracl_core_ed25519/ed25519/big.rs

miracl_core_ed25519/ed25519/
big.rs
