You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by br...@apache.org on 2018/11/07 23:49:51 UTC
[14/51] [partial] incubator-milagro-crypto git commit: update code
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/swift/ecdh.swift
----------------------------------------------------------------------
diff --git a/swift/ecdh.swift b/swift/ecdh.swift
deleted file mode 100644
index 9f74372..0000000
--- a/swift/ecdh.swift
+++ /dev/null
@@ -1,531 +0,0 @@
-/*
-Licensed to the Apache Software Foundation (ASF) under one
-or more contributor license agreements. See the NOTICE file
-distributed with this work for additional information
-regarding copyright ownership. The ASF licenses this file
-to you under the Apache License, Version 2.0 (the
-"License"); you may not use this file except in compliance
-with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
-Unless required by applicable law or agreed to in writing,
-software distributed under the License is distributed on an
-"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-KIND, either express or implied. See the License for the
-specific language governing permissions and limitations
-under the License.
-*/
-//
-// ecdh.swift
-//
-//
-// Created by Michael Scott on 30/06/2015.
-// Copyright (c) 2015 Michael Scott. All rights reserved.
-//
-
-import Foundation
-
-/* Elliptic Curve API high-level functions */
-
-final public class ECDH
-{
- static let INVALID_PUBLIC_KEY:Int = -2
- static let ERROR:Int = -3
- static let INVALID:Int = -4
- static public let EFS=Int(ROM.MODBYTES);
- static public let EGS=Int(ROM.MODBYTES);
- static public let EAS=AES.KS;
- static public let EBS=AES.BS;
-
- /* Convert Integer to n-byte array */
- private static func inttoBytes(n: Int,_ len:Int) -> [UInt8]
- {
- var b=[UInt8](count:len,repeatedValue:0)
- var nn=n
-
- var i=len;
- while (nn>0 && i>0)
- {
- i--;
- b[i]=UInt8(nn&0xff);
- nn /= 256;
- }
- return b;
- }
-
- /* Key Derivation Functions */
- /* Input octet Z */
- /* Output key of length olen */
- static public func KDF1(Z: [UInt8],_ olen:Int) -> [UInt8]
- {
- /* NOTE: the parameter olen is the length of the output K in bytes */
- let H=HASH()
- let hlen=HASH.len
- var K=[UInt8](count:olen,repeatedValue:0)
- var B=[UInt8](count:hlen,repeatedValue:0)
-
- var k=0;
-
- var cthreshold=olen/hlen; if (olen%hlen) != 0 {cthreshold++}
-
- for var counter=0;counter<cthreshold;counter++
- {
- H.process_array(Z); if counter>0 {H.process_num(Int32(counter))}
- B=H.hash();
- if k+hlen>olen {for var i=0;i<olen%hlen;i++ {K[k++]=B[i]}}
- else {for var i=0;i<hlen;i++ {K[k++]=B[i]}}
- }
- return K;
- }
-
- static public func KDF2(Z:[UInt8],_ P:[UInt8],_ olen:Int) -> [UInt8]
- {
- /* NOTE: the parameter olen is the length of the output k in bytes */
- let H=HASH();
- let hlen=HASH.len;
- var K=[UInt8](count:olen,repeatedValue:0)
- var B=[UInt8](count:hlen,repeatedValue:0)
-
- var k=0;
-
- var cthreshold=olen/hlen; if (olen%hlen) != 0 {cthreshold++}
-
- for var counter=1;counter<=cthreshold;counter++
- {
- H.process_array(Z); H.process_num(Int32(counter)); H.process_array(P)
- B=H.hash();
- if k+hlen>olen {for var i=0;i<olen%hlen;i++ {K[k++]=B[i]}}
- else {for var i=0;i<hlen;i++ {K[k++]=B[i]}}
- }
- return K;
- }
-
- /* Password based Key Derivation Function */
- /* Input password p, salt s, and repeat count */
- /* Output key of length olen */
- static public func PBKDF2(Pass:[UInt8],_ Salt:[UInt8],_ rep:Int,_ olen:Int) -> [UInt8]
- {
- var d=olen/32;
- if (olen%32) != 0 {d++}
- var F=[UInt8](count:ECDH.EFS,repeatedValue:0)
- var U=[UInt8](count:ECDH.EFS,repeatedValue:0)
- var S=[UInt8](count:Salt.count+4,repeatedValue:0)
-
- var K=[UInt8](count:d*ECDH.EFS,repeatedValue:0)
-
- var opt=0;
-
- for var i=1;i<=d;i++
- {
- for var j=0;j<Salt.count;j++ {S[j]=Salt[j]}
- var N=ECDH.inttoBytes(i,4);
- for var j=0;j<4;j++ {S[Salt.count+j]=N[j]}
-
- ECDH.HMAC(S,Pass,&F);
-
- for var j=0;j<EFS;j++ {U[j]=F[j]}
- for var j=2;j<=rep;j++
- {
- ECDH.HMAC(U,Pass,&U);
- for var k=0;k<ECDH.EFS;k++ {F[k]^=U[k]}
- }
- for var j=0;j<EFS;j++ {K[opt++]=F[j]}
- }
- var key=[UInt8](count:olen,repeatedValue:0)
- for var i=0;i<olen;i++ {key[i]=K[i]}
- return key;
- }
-
- /* Calculate HMAC of m using key k. HMAC is tag of length olen */
- static public func HMAC(M:[UInt8],_ K:[UInt8],inout _ tag:[UInt8]) -> Int
- {
- /* Input is from an octet m *
- * olen is requested output length in bytes. k is the key *
- * The output is the calculated tag */
- var K0=[UInt8](count:64,repeatedValue:0)
- let olen=tag.count;
-
- let b=K0.count;
- if olen<4 || olen>HASH.len {return 0}
-
- let H=HASH();
-
- if (K.count > b)
- {
- H.process_array(K); var B=H.hash();
- for var i=0;i<32;i++ {K0[i]=B[i]}
- }
- else
- {
- for var i=0;i<K.count;i++ {K0[i]=K[i]}
- }
- for var i=0;i<b;i++ {K0[i]^=0x36}
- H.process_array(K0); H.process_array(M); var B=H.hash();
-
- for var i=0;i<b;i++ {K0[i]^=0x6a}
- H.process_array(K0); H.process_array(B); B=H.hash();
-
- for var i=0;i<olen;i++ {tag[i]=B[i]}
-
- return 1;
- }
- /* AES encryption/decryption. Encrypt byte array M using key K and returns ciphertext */
- static public func AES_CBC_IV0_ENCRYPT(K:[UInt8],_ M:[UInt8]) -> [UInt8]
- { /* AES CBC encryption, with Null IV and key K */
- /* Input is from an octet string M, output is to an octet string C */
- /* Input is padded as necessary to make up a full final block */
- let a=AES();
- var buff=[UInt8](count:16,repeatedValue:0)
- let clen=16+(M.count/16)*16;
-
- var C=[UInt8](count:clen,repeatedValue:0)
-
- a.init_it(AES.CBC,K,nil)
-
- var ipt=0; var opt=0;
- var fin=false;
- var i:Int=0
- while true
- {
- for i=0;i<16;i++
- {
- if (ipt<M.count) {buff[i]=M[ipt++]}
- else {fin=true; break;}
- }
- if fin {break}
- a.encrypt(&buff);
- for var i=0;i<16;i++
- {C[opt++]=buff[i]}
- }
-
- /* last block, filled up to i-th index */
-
- let padlen=16-i;
- for var j=i;j<16;j++ {buff[j]=UInt8(padlen&0xff)}
-
- a.encrypt(&buff);
-
- for var i=0;i<16;i++
- {C[opt++]=buff[i]}
- a.end();
- return C;
- }
-
- /* returns plaintext if all consistent, else returns null string */
- static public func AES_CBC_IV0_DECRYPT(K:[UInt8],_ C:[UInt8]) -> [UInt8]
- { /* padding is removed */
- let a=AES();
-
- var buff=[UInt8](count:16,repeatedValue:0)
- var MM=[UInt8](count:C.count,repeatedValue:0)
-
- var ipt=0; var opt=0;
-
- a.init_it(AES.CBC,K,nil);
-
- if C.count==0 {return [UInt8]()}
- var ch=C[ipt++];
-
- var fin=false;
- var i:Int=0
- while true
- {
- for i=0;i<16;i++
- {
- buff[i]=ch;
- if ipt>=C.count {fin=true; break;}
- else {ch=C[ipt++]}
- }
- a.decrypt(&buff);
- if fin {break}
- for var i=0;i<16;i++
- {MM[opt++]=buff[i]}
- }
-
- a.end();
- var bad=false;
- let padlen:Int=Int(buff[15]);
- if i != 15 || padlen<1 || padlen>16 {bad=true}
- if padlen>=2 && padlen<=16
- {
- for var i=16-padlen;i<16;i++ {if buff[i] != buff[15] {bad=true}}
- }
- if !bad
- {
- for var i=0;i<16-padlen;i++
- {MM[opt++]=buff[i]}
- }
-
- if bad {return [UInt8]()}
-
- var M=[UInt8](count:opt,repeatedValue:0)
- for var i=0;i<opt;i++ {M[i]=MM[i]}
-
- return M;
- }
-
- /* Calculate a public/private EC GF(p) key pair W,S where W=S.G mod EC(p),
- * where S is the secret key and W is the public key
- * and G is fixed generator.
- * If RNG is NULL then the private key is provided externally in S
- * otherwise it is generated randomly internally */
- static public func KEY_PAIR_GENERATE(RNG:RAND?,inout _ S:[UInt8],inout _ W:[UInt8]) -> Int
- {
- let res=0;
- var T=[UInt8](count:ECDH.EFS,repeatedValue:0)
- let gx=BIG(ROM.CURVE_Gx);
- var s:BIG
- var G:ECP
- if ROM.CURVETYPE != ROM.MONTGOMERY
- {
- let gy=BIG(ROM.CURVE_Gy)
- G=ECP(gx,gy)
- }
- else
- {G=ECP(gx)}
-
- let r=BIG(ROM.CURVE_Order);
-
- if (RNG==nil)
- {
- s=BIG.fromBytes(S);
- }
- else
- {
- s=BIG.randomnum(r,RNG!)
-
- s.toBytes(&T)
- for var i=0;i<EGS;i++ {S[i]=T[i]}
- }
-
- let WP=G.mul(s)
- WP.toBytes(&W)
-
- return res;
- }
-
- /* validate public key. Set full=true for fuller check */
- static public func PUBLIC_KEY_VALIDATE(full:Bool,_ W:[UInt8]) -> Int
- {
- var WP=ECP.fromBytes(W);
- var res=0;
-
- let r=BIG(ROM.CURVE_Order)
-
- if WP.is_infinity() {res=INVALID_PUBLIC_KEY}
-
- if res==0 && full
- {
- WP=WP.mul(r)
- if !WP.is_infinity() {res=INVALID_PUBLIC_KEY}
- }
- return res;
- }
- /* IEEE-1363 Diffie-Hellman online calculation Z=S.WD */
- static public func ECPSVDP_DH(S:[UInt8],_ WD:[UInt8],inout _ Z:[UInt8]) -> Int
- {
- var res=0
- var T=[UInt8](count:ECDH.EFS,repeatedValue:0)
-
- let s=BIG.fromBytes(S)
-
- var W=ECP.fromBytes(WD)
- if W.is_infinity() {res=ECDH.ERROR}
-
- if (res==0)
- {
- let r=BIG(ROM.CURVE_Order)
- s.mod(r)
-
- W=W.mul(s);
- if W.is_infinity() {res=ERROR}
- else
- {
- W.getX().toBytes(&T);
- for var i=0;i<ECDH.EFS;i++ {Z[i]=T[i]}
- }
- }
- return res;
- }
- /* IEEE ECDSA Signature, C and D are signature on F using private key S */
- static public func ECPSP_DSA(RNG:RAND,_ S:[UInt8],_ F:[UInt8],inout _ C:[UInt8],inout _ D:[UInt8]) -> Int
- {
- var T=[UInt8](count:ECDH.EFS,repeatedValue:0)
- let H=HASH()
- H.process_array(F)
- let B=H.hash()
-
- let gx=BIG(ROM.CURVE_Gx)
- let gy=BIG(ROM.CURVE_Gy)
-
- let G=ECP(gx,gy)
- let r=BIG(ROM.CURVE_Order)
-
- let s=BIG.fromBytes(S)
- let f=BIG.fromBytes(B)
-
- let c=BIG(0)
- let d=BIG(0)
- var V=ECP()
-
- repeat {
- let u=BIG.randomnum(r,RNG);
-
- V.copy(G)
- V=V.mul(u)
- let vx=V.getX()
- c.copy(vx)
- c.mod(r)
- if c.iszilch() {continue}
- u.invmodp(r)
- d.copy(BIG.modmul(s,c,r))
- d.add(f)
- d.copy(BIG.modmul(u,d,r))
- } while d.iszilch()
-
- c.toBytes(&T)
- for var i=0;i<ECDH.EFS;i++ {C[i]=T[i]}
- d.toBytes(&T)
- for var i=0;i<ECDH.EFS;i++ {D[i]=T[i]}
- return 0;
- }
-
- /* IEEE1363 ECDSA Signature Verification. Signature C and D on F is verified using public key W */
- static public func ECPVP_DSA(W:[UInt8],_ F:[UInt8],_ C:[UInt8],_ D:[UInt8]) -> Int
- {
- var res=0
-
- let H=HASH()
- H.process_array(F)
- let B=H.hash()
-
- let gx=BIG(ROM.CURVE_Gx)
- let gy=BIG(ROM.CURVE_Gy)
-
- let G=ECP(gx,gy)
- let r=BIG(ROM.CURVE_Order)
-
- let c=BIG.fromBytes(C)
- var d=BIG.fromBytes(D)
- let f=BIG.fromBytes(B)
-
- if c.iszilch() || BIG.comp(c,r)>=0 || d.iszilch() || BIG.comp(d,r)>=0
- {res=ECDH.INVALID}
-
- if res==0
- {
- d.invmodp(r);
- f.copy(BIG.modmul(f,d,r))
- let h2=BIG.modmul(c,d,r)
-
- let WP=ECP.fromBytes(W)
- if WP.is_infinity() {res=ECDH.ERROR}
- else
- {
- var P=ECP();
- P.copy(WP);
- P=P.mul2(h2,G,f);
- if P.is_infinity() {res=INVALID}
- else
- {
- d=P.getX();
- d.mod(r);
- if (BIG.comp(d,c) != 0) {res=ECDH.INVALID}
- }
- }
- }
-
- return res;
- }
-
- /* IEEE1363 ECIES encryption. Encryption of plaintext M uses public key W and produces ciphertext V,C,T */
- static public func ECIES_ENCRYPT(P1:[UInt8],_ P2:[UInt8],_ RNG:RAND,_ W:[UInt8],_ M:[UInt8],inout _ V:[UInt8],inout _ T:[UInt8]) -> [UInt8]
- {
- var Z=[UInt8](count:ECDH.EFS,repeatedValue:0)
- var VZ=[UInt8](count:3*ECDH.EFS+1,repeatedValue:0)
- var K1=[UInt8](count:ECDH.EAS,repeatedValue:0)
- var K2=[UInt8](count:ECDH.EAS,repeatedValue:0)
- var U=[UInt8](count:ECDH.EGS,repeatedValue:0)
-
- if ECDH.KEY_PAIR_GENERATE(RNG,&U,&V) != 0 {return [UInt8]()}
- if ECDH.ECPSVDP_DH(U,W,&Z) != 0 {return [UInt8]()}
-
- for var i=0;i<2*ECDH.EFS+1;i++ {VZ[i]=V[i]}
- for var i=0;i<ECDH.EFS;i++ {VZ[2*ECDH.EFS+1+i]=Z[i]}
-
-
- var K=KDF2(VZ,P1,ECDH.EFS)
-
- for var i=0;i<ECDH.EAS;i++ {K1[i]=K[i]; K2[i]=K[EAS+i];}
-
- var C=AES_CBC_IV0_ENCRYPT(K1,M)
-
- var L2=inttoBytes(P2.count,8)
-
- var AC=[UInt8](count:C.count+P2.count+8,repeatedValue:0)
-
- for var i=0;i<C.count;i++ {AC[i]=C[i]}
- for var i=0;i<P2.count;i++ {AC[C.count+i]=P2[i]}
- for var i=0;i<8;i++ {AC[C.count+P2.count+i]=L2[i]}
-
- ECDH.HMAC(AC,K2,&T)
-
- return C
- }
-
- /* IEEE1363 ECIES decryption. Decryption of ciphertext V,C,T using private key U outputs plaintext M */
- static public func ECIES_DECRYPT(P1:[UInt8],_ P2:[UInt8],_ V:[UInt8],_ C:[UInt8],_ T:[UInt8],_ U:[UInt8]) -> [UInt8]
- {
- var Z=[UInt8](count:ECDH.EFS,repeatedValue:0)
- var VZ=[UInt8](count:3*ECDH.EFS+1,repeatedValue:0)
- var K1=[UInt8](count:ECDH.EAS,repeatedValue:0)
- var K2=[UInt8](count:ECDH.EAS,repeatedValue:0)
-
- var TAG=[UInt8](count:T.count,repeatedValue:0)
-
- if ECPSVDP_DH(U,V,&Z) != 0 {return [UInt8]()}
-
- for var i=0;i<2*ECDH.EFS+1;i++ {VZ[i]=V[i]}
- for var i=0;i<ECDH.EFS;i++ {VZ[2*EFS+1+i]=Z[i]}
-
- var K=KDF2(VZ,P1,ECDH.EFS)
-
- for var i=0;i<ECDH.EAS;i++ {K1[i]=K[i]; K2[i]=K[ECDH.EAS+i]}
-
- let M=ECDH.AES_CBC_IV0_DECRYPT(K1,C)
-
- if M.count==0 {return M}
-
- var L2=inttoBytes(P2.count,8)
-
- var AC=[UInt8](count:C.count+P2.count+8,repeatedValue:0)
-
- for var i=0;i<C.count;i++ {AC[i]=C[i]}
- for var i=0;i<P2.count;i++ {AC[C.count+i]=P2[i]}
- for var i=0;i<8;i++ {AC[C.count+P2.count+i]=L2[i]}
-
- ECDH.HMAC(AC,K2,&TAG)
-
- var same=true
- for var i=0;i<T.count;i++
- {
- if T[i] != TAG[i] {same=false}
- }
- if !same {return [UInt8]()}
-
- return M;
-
- }
-
- static public func printBinary(array: [UInt8])
- {
- for var i=0;i<array.count;i++
- {
- let h=String(array[i],radix:16);
- print("\(h)", terminator: "")
- }
- print("");
- }
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/swift/ecp.swift
----------------------------------------------------------------------
diff --git a/swift/ecp.swift b/swift/ecp.swift
deleted file mode 100644
index f7d84f5..0000000
--- a/swift/ecp.swift
+++ /dev/null
@@ -1,923 +0,0 @@
-/*
-Licensed to the Apache Software Foundation (ASF) under one
-or more contributor license agreements. See the NOTICE file
-distributed with this work for additional information
-regarding copyright ownership. The ASF licenses this file
-to you under the Apache License, Version 2.0 (the
-"License"); you may not use this file except in compliance
-with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
-Unless required by applicable law or agreed to in writing,
-software distributed under the License is distributed on an
-"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-KIND, either express or implied. See the License for the
-specific language governing permissions and limitations
-under the License.
-*/
-//
-// ecp.swift
-//
-//
-// Created by Michael Scott on 30/06/2015.
-// Copyright (c) 2015 Michael Scott. All rights reserved.
-//
-
-final class ECP {
- private var x:FP
- private var y:FP
- private var z:FP
- private var INF:Bool
-
- /* Constructor - set to O */
- init()
- {
- x=FP(0)
- y=FP(0)
- z=FP(1)
- INF=true
- }
-
- /* test for O point-at-infinity */
- func is_infinity() -> Bool
- {
- if (ROM.CURVETYPE==ROM.EDWARDS)
- {
- x.reduce(); y.reduce(); z.reduce()
- return x.iszilch() && y.equals(z)
- }
- else {return INF}
- }
-
- /* Conditional swap of P and Q dependant on d */
- private func cswap(Q: ECP,_ d:Int32)
- {
- x.cswap(Q.x,d);
- if ROM.CURVETYPE != ROM.MONTGOMERY {y.cswap(Q.y,d)}
- z.cswap(Q.z,d);
- if (ROM.CURVETYPE != ROM.EDWARDS)
- {
- var bd:Bool
- if d==0 {bd=false}
- else {bd=true}
- bd=bd && (INF != Q.INF)
- INF = (INF != bd)
- Q.INF = (Q.INF != bd)
- }
- }
-
- /* Conditional move of Q to P dependant on d */
- private func cmove(Q: ECP,_ d:Int32)
- {
- x.cmove(Q.x,d);
- if ROM.CURVETYPE != ROM.MONTGOMERY {y.cmove(Q.y,d)}
- z.cmove(Q.z,d);
- if (ROM.CURVETYPE != ROM.EDWARDS)
- {
- var bd:Bool
- if d==0 {bd=false}
- else {bd=true}
- INF != (INF != Q.INF) && bd;
- }
- }
-
- /* return 1 if b==c, no branching */
- private static func teq(b: Int32,_ c:Int32) -> Int32
- {
- var x=b^c
- x-=1 // if x=0, x now -1
- return ((x>>31)&1)
- }
-
- /* self=P */
- func copy(P: ECP)
- {
- x.copy(P.x)
- if ROM.CURVETYPE != ROM.MONTGOMERY {y.copy(P.y)}
- z.copy(P.z)
- INF=P.INF
- }
- /* self=-self */
- func neg() {
- if is_infinity() {return}
- if (ROM.CURVETYPE==ROM.WEIERSTRASS)
- {
- y.neg(); y.norm();
- }
- if (ROM.CURVETYPE==ROM.EDWARDS)
- {
- x.neg(); x.norm();
- }
- return;
- }
-
- /* Constant time select from pre-computed table */
- private func select(W:[ECP],_ b:Int32)
- {
- let MP=ECP()
- let m=b>>31
- var babs=(b^m)-m
-
- babs=(babs-1)/2
-
- cmove(W[0],ECP.teq(babs,0)); // conditional move
- cmove(W[1],ECP.teq(babs,1))
- cmove(W[2],ECP.teq(babs,2))
- cmove(W[3],ECP.teq(babs,3))
- cmove(W[4],ECP.teq(babs,4))
- cmove(W[5],ECP.teq(babs,5))
- cmove(W[6],ECP.teq(babs,6))
- cmove(W[7],ECP.teq(babs,7))
-
- MP.copy(self)
- MP.neg()
- cmove(MP,(m&1))
- }
-
- /* Test P == Q */
- func equals(Q: ECP) -> Bool
- {
- if (is_infinity() && Q.is_infinity()) {return true}
- if (is_infinity() || Q.is_infinity()) {return false}
- if (ROM.CURVETYPE==ROM.WEIERSTRASS)
- {
- let zs2=FP(z); zs2.sqr()
- let zo2=FP(Q.z); zo2.sqr()
- let zs3=FP(zs2); zs3.mul(z)
- let zo3=FP(zo2); zo3.mul(Q.z)
- zs2.mul(Q.x)
- zo2.mul(x)
- if !zs2.equals(zo2) {return false}
- zs3.mul(Q.y)
- zo3.mul(y)
- if !zs3.equals(zo3) {return false}
- }
- else
- {
- let a=FP(0)
- let b=FP(0)
- a.copy(x); a.mul(Q.z); a.reduce()
- b.copy(Q.x); b.mul(z); b.reduce()
- if !a.equals(b) {return false}
- if ROM.CURVETYPE==ROM.EDWARDS
- {
- a.copy(y); a.mul(Q.z); a.reduce()
- b.copy(Q.y); b.mul(z); b.reduce()
- if !a.equals(b) {return false}
- }
- }
- return true
- }
-
-/* set self=O */
- func inf()
- {
- INF=true;
- x.zero()
- y.one()
- z.one()
- }
-
- /* Calculate RHS of curve equation */
- static func RHS(x: FP) -> FP
- {
- x.norm();
- let r=FP(x);
- r.sqr();
-
- if ROM.CURVETYPE==ROM.WEIERSTRASS
- { // x^3+Ax+B
- let b=FP(BIG(ROM.CURVE_B))
- r.mul(x)
- if (ROM.CURVE_A == -3)
- {
- let cx=FP(x)
- cx.imul(3)
- cx.neg(); cx.norm()
- r.add(cx)
- }
- r.add(b);
- }
- if (ROM.CURVETYPE==ROM.EDWARDS)
- { // (Ax^2-1)/(Bx^2-1)
- let b=FP(BIG(ROM.CURVE_B))
-
- let one=FP(1);
- b.mul(r);
- b.sub(one);
- if ROM.CURVE_A == -1 {r.neg()}
- r.sub(one)
- b.inverse()
- r.mul(b);
- }
- if ROM.CURVETYPE==ROM.MONTGOMERY
- { // x^3+Ax^2+x
- let x3=FP(0)
- x3.copy(r);
- x3.mul(x);
- r.imul(ROM.CURVE_A);
- r.add(x3);
- r.add(x);
- }
- r.reduce();
- return r;
- }
-
- /* set (x,y) from two BIGs */
- init(_ ix: BIG,_ iy: BIG)
- {
- x=FP(ix)
- y=FP(iy)
- z=FP(1)
- INF=true
- let rhs=ECP.RHS(x);
-
- if ROM.CURVETYPE==ROM.MONTGOMERY
- {
- if rhs.jacobi()==1 {INF=false}
- else {inf()}
- }
- else
- {
- let y2=FP(y)
- y2.sqr()
- if y2.equals(rhs) {INF=false}
- else {inf()}
- }
- }
-
- /* set (x,y) from BIG and a bit */
- init(_ ix: BIG,_ s:Int32)
- {
- x=FP(ix)
- let rhs=ECP.RHS(x)
- y=FP(0)
- z=FP(1)
- INF=true
- if rhs.jacobi()==1
- {
- let ny=rhs.sqrt()
- if (ny.redc().parity() != s) {ny.neg()}
- y.copy(ny)
- INF=false;
- }
- else {inf()}
- }
-
- /* set from x - calculate y from curve equation */
- init(_ ix:BIG)
- {
- x=FP(ix)
- let rhs=ECP.RHS(x)
- y=FP(0)
- z=FP(1)
- if rhs.jacobi()==1
- {
- if ROM.CURVETYPE != ROM.MONTGOMERY {y.copy(rhs.sqrt())}
- INF=false;
- }
- else {INF=true}
- }
-
- /* set to affine - from (x,y,z) to (x,y) */
- func affine()
- {
- if is_infinity() {return}
- let one=FP(1)
- if (z.equals(one)) {return}
- z.inverse()
- if ROM.CURVETYPE==ROM.WEIERSTRASS
- {
- let z2=FP(z)
- z2.sqr()
- x.mul(z2); x.reduce()
- y.mul(z2)
- y.mul(z); y.reduce()
- }
- if ROM.CURVETYPE==ROM.EDWARDS
- {
- x.mul(z); x.reduce()
- y.mul(z); y.reduce()
- }
- if ROM.CURVETYPE==ROM.MONTGOMERY
- {
- x.mul(z); x.reduce()
-
- }
- z.copy(one)
- }
- /* extract x as a BIG */
- func getX() -> BIG
- {
- affine()
- return x.redc()
- }
- /* extract y as a BIG */
- func getY() -> BIG
- {
- affine();
- return y.redc();
- }
-
- /* get sign of Y */
- func getS() -> Int32
- {
- affine()
- let y=getY()
- return y.parity()
- }
- /* extract x as an FP */
- func getx() -> FP
- {
- return x;
- }
- /* extract y as an FP */
- func gety() -> FP
- {
- return y;
- }
- /* extract z as an FP */
- func getz() -> FP
- {
- return z;
- }
- /* convert to byte array */
- func toBytes(inout b:[UInt8])
- {
- let RM=Int(ROM.MODBYTES)
- var t=[UInt8](count:RM,repeatedValue:0)
- if ROM.CURVETYPE != ROM.MONTGOMERY {b[0]=0x04}
- else {b[0]=0x02}
-
- affine()
- x.redc().toBytes(&t)
- for var i=0;i<RM;i++ {b[i+1]=t[i]}
- if ROM.CURVETYPE != ROM.MONTGOMERY
- {
- y.redc().toBytes(&t);
- for var i=0;i<RM;i++ {b[i+RM+1]=t[i]}
- }
- }
- /* convert from byte array to point */
- static func fromBytes(b: [UInt8]) -> ECP
- {
- let RM=Int(ROM.MODBYTES)
- var t=[UInt8](count:RM,repeatedValue:0)
- let p=BIG(ROM.Modulus);
-
- for var i=0;i<RM;i++ {t[i]=b[i+1]}
- let px=BIG.fromBytes(t)
- if BIG.comp(px,p)>=0 {return ECP()}
-
- if (b[0]==0x04)
- {
- for var i=0;i<RM;i++ {t[i]=b[i+RM+1]}
- let py=BIG.fromBytes(t)
- if BIG.comp(py,p)>=0 {return ECP()}
- return ECP(px,py)
- }
- else {return ECP(px)}
- }
- /* convert to hex string */
- func toString() -> String
- {
- if is_infinity() {return "infinity"}
- affine();
- if ROM.CURVETYPE==ROM.MONTGOMERY {return "("+x.redc().toString()+")"}
- else {return "("+x.redc().toString()+","+y.redc().toString()+")"}
- }
-
- /* self*=2 */
- func dbl()
- {
- if (ROM.CURVETYPE==ROM.WEIERSTRASS)
- {
- if INF {return}
- if y.iszilch()
- {
- inf()
- return
- }
-
- let w1=FP(x)
- let w6=FP(z)
- let w2=FP(0)
- let w3=FP(x)
- let w8=FP(x)
-
- if (ROM.CURVE_A == -3)
- {
- w6.sqr()
- w1.copy(w6)
- w1.neg()
- w3.add(w1)
- w8.add(w6)
- w3.mul(w8)
- w8.copy(w3)
- w8.imul(3)
- }
- else
- {
- w1.sqr()
- w8.copy(w1)
- w8.imul(3)
- }
-
- w2.copy(y); w2.sqr()
- w3.copy(x); w3.mul(w2)
- w3.imul(4)
- w1.copy(w3); w1.neg()
- w1.norm()
-
- x.copy(w8); x.sqr()
- x.add(w1)
- x.add(w1)
- x.norm()
-
- z.mul(y)
- z.add(z)
-
- w2.add(w2)
- w2.sqr()
- w2.add(w2)
- w3.sub(x)
- y.copy(w8); y.mul(w3)
- //w2.norm();
- y.sub(w2)
- y.norm()
- z.norm()
- }
- if ROM.CURVETYPE==ROM.EDWARDS
- {
- let C=FP(x)
- let D=FP(y)
- let H=FP(z)
- let J=FP(0)
-
- x.mul(y); x.add(x)
- C.sqr()
- D.sqr()
- if ROM.CURVE_A == -1 {C.neg()}
- y.copy(C); y.add(D)
- y.norm()
- H.sqr(); H.add(H)
- z.copy(y)
- J.copy(y); J.sub(H)
- x.mul(J)
- C.sub(D)
- y.mul(C)
- z.mul(J)
-
- x.norm();
- y.norm();
- z.norm();
- }
- if ROM.CURVETYPE==ROM.MONTGOMERY
- {
- let A=FP(x)
- let B=FP(x);
- let AA=FP(0);
- let BB=FP(0);
- let C=FP(0);
-
- if INF {return}
-
- A.add(z)
- AA.copy(A); AA.sqr()
- B.sub(z)
- BB.copy(B); BB.sqr()
- C.copy(AA); C.sub(BB)
- //C.norm();
-
- x.copy(AA); x.mul(BB)
-
- A.copy(C); A.imul((ROM.CURVE_A+2)/4)
-
- BB.add(A)
- z.copy(BB); z.mul(C)
- x.norm()
- z.norm()
- }
- return
- }
-
- /* self+=Q */
- func add(Q:ECP)
- {
- if ROM.CURVETYPE==ROM.WEIERSTRASS
- {
- if (INF)
- {
- copy(Q)
- return
- }
- if Q.INF {return}
-
- var aff=false;
-
- let one=FP(1);
- if Q.z.equals(one) {aff=true}
-
- var A:FP
- var C:FP
- let B=FP(z)
- let D=FP(z)
- if (!aff)
- {
- A=FP(Q.z)
- C=FP(Q.z)
-
- A.sqr(); B.sqr()
- C.mul(A); D.mul(B)
-
- A.mul(x)
- C.mul(y)
- }
- else
- {
- A=FP(x)
- C=FP(y)
-
- B.sqr()
- D.mul(B)
- }
-
- B.mul(Q.x); B.sub(A)
- D.mul(Q.y); D.sub(C)
-
- if B.iszilch()
- {
- if (D.iszilch())
- {
- dbl()
- return
- }
- else
- {
- INF=true
- return
- }
- }
-
- if !aff {z.mul(Q.z)}
- z.mul(B);
-
- let e=FP(B); e.sqr()
- B.mul(e)
- A.mul(e)
-
- e.copy(A)
- e.add(A); e.add(B)
- x.copy(D); x.sqr(); x.sub(e)
-
- A.sub(x)
- y.copy(A); y.mul(D)
- C.mul(B); y.sub(C)
-
- x.norm()
- y.norm()
- z.norm()
- }
- if ROM.CURVETYPE==ROM.EDWARDS
- {
- let b=FP(BIG(ROM.CURVE_B))
- let A=FP(z)
- let B=FP(0)
- let C=FP(x)
- let D=FP(y)
- let E=FP(0)
- let F=FP(0)
- let G=FP(0)
-
- A.mul(Q.z)
- B.copy(A); B.sqr()
- C.mul(Q.x)
- D.mul(Q.y)
-
- E.copy(C); E.mul(D); E.mul(b)
- F.copy(B); F.sub(E)
- G.copy(B); G.add(E)
- C.add(D)
-
- if ROM.CURVE_A==1
- {
- E.copy(D); D.sub(C)
- }
-
- B.copy(x); B.add(y)
- D.copy(Q.x); D.add(Q.y)
- B.mul(D)
- B.sub(C)
- B.mul(F)
- x.copy(A); x.mul(B)
-
- if ROM.CURVE_A==1
- {
- C.copy(E); C.mul(G)
- }
- if ROM.CURVE_A == -1
- {
- C.mul(G)
- }
- y.copy(A); y.mul(C)
- z.copy(F); z.mul(G)
- x.norm(); y.norm(); z.norm()
- }
- return;
- }
-
- /* Differential Add for Montgomery curves. self+=Q where W is self-Q and is affine. */
- func dadd(Q:ECP,_ W:ECP)
- {
- let A=FP(x)
- let B=FP(x)
- let C=FP(Q.x)
- let D=FP(Q.x)
- let DA=FP(0)
- let CB=FP(0)
-
- A.add(z)
- B.sub(z)
-
- C.add(Q.z)
- D.sub(Q.z)
-
- DA.copy(D); DA.mul(A)
- CB.copy(C); CB.mul(B)
-
- A.copy(DA); A.add(CB); A.sqr()
- B.copy(DA); B.sub(CB); B.sqr()
-
- x.copy(A)
- z.copy(W.x); z.mul(B)
-
- if z.iszilch() {inf()}
- else {INF=false}
-
- x.norm()
- }
- /* this-=Q */
- func sub(Q:ECP)
- {
- Q.neg()
- add(Q)
- Q.neg()
- }
- static func multiaffine(m: Int,_ P:[ECP])
- {
- let t1=FP(0)
- let t2=FP(0)
-
- var work=[FP]()
-
- for var i=0;i<m;i++
- {work.append(FP(0))}
-
- work[0].one()
- work[1].copy(P[0].z)
-
- for var i=2;i<m;i++
- {
- work[i].copy(work[i-1])
- work[i].mul(P[i-1].z)
- }
-
- t1.copy(work[m-1]);
- t1.mul(P[m-1].z);
- t1.inverse();
- t2.copy(P[m-1].z);
- work[m-1].mul(t1);
-
- for var i=m-2;;i--
- {
- if i==0
- {
- work[0].copy(t1)
- work[0].mul(t2)
- break
- }
- work[i].mul(t2);
- work[i].mul(t1);
- t2.mul(P[i].z);
- }
- /* now work[] contains inverses of all Z coordinates */
-
- for var i=0;i<m;i++
- {
- P[i].z.one();
- t1.copy(work[i]);
- t1.sqr();
- P[i].x.mul(t1);
- t1.mul(work[i]);
- P[i].y.mul(t1);
- }
- }
- /* constant time multiply by small integer of length bts - use ladder */
- func pinmul(e:Int32,_ bts:Int32) -> ECP
- {
- if ROM.CURVETYPE==ROM.MONTGOMERY
- {return self.mul(BIG(e))}
- else
- {
- let P=ECP()
- let R0=ECP()
- let R1=ECP(); R1.copy(self)
-
- for var i=bts-1;i>=0;i--
- {
- let b=(e>>i)&1;
- P.copy(R1);
- P.add(R0);
- R0.cswap(R1,b);
- R1.copy(P);
- R0.dbl();
- R0.cswap(R1,b);
- }
- P.copy(R0);
- P.affine();
- return P;
- }
- }
-
- /* return e.self */
-
- func mul(e:BIG) -> ECP
- {
- if (e.iszilch() || is_infinity()) {return ECP()}
-
- let P=ECP()
- if ROM.CURVETYPE==ROM.MONTGOMERY
- {
- /* use Ladder */
- let D=ECP()
- let R0=ECP(); R0.copy(self)
- let R1=ECP(); R1.copy(self)
- R1.dbl();
- D.copy(self); D.affine();
- let nb=e.nbits();
-
- for var i=nb-2;i>=0;i--
- {
- let b=e.bit(i)
- //print("\(b)")
- P.copy(R1)
- P.dadd(R0,D)
- R0.cswap(R1,b)
- R1.copy(P)
- R0.dbl()
- R0.cswap(R1,b)
- }
- P.copy(R0)
- }
- else
- {
- // fixed size windows
- let mt=BIG()
- let t=BIG()
- let Q=ECP()
- let C=ECP()
- var W=[ECP]()
- let n=1+(ROM.NLEN*Int(ROM.BASEBITS)+3)/4
- var w=[Int8](count:n,repeatedValue:0)
-
- affine();
-
- // precompute table
- Q.copy(self)
- Q.dbl()
- W.append(ECP())
-
- W[0].copy(self)
-
- for var i=1;i<8;i++
- {
- W.append(ECP())
- W[i].copy(W[i-1])
- W[i].add(Q)
- }
-
- // convert the table to affine
- if ROM.CURVETYPE==ROM.WEIERSTRASS
- {ECP.multiaffine(8,W)}
-
- // make exponent odd - add 2P if even, P if odd
- t.copy(e);
- let s=t.parity();
- t.inc(1); t.norm(); let ns=t.parity();
- mt.copy(t); mt.inc(1); mt.norm();
- t.cmove(mt,s);
- Q.cmove(self,ns);
- C.copy(Q);
-
- let nb=1+(t.nbits()+3)/4;
-
- // convert exponent to signed 4-bit window
- for var i=0;i<nb;i++
- {
- w[i]=Int8(t.lastbits(5)-16);
- t.dec(Int32(w[i])); t.norm();
- t.fshr(4);
- }
- w[nb]=Int8(t.lastbits(5))
-
- P.copy(W[Int((w[nb])-1)/2]);
- for var i=nb-1;i>=0;i--
- {
- Q.select(W,Int32(w[i]));
- P.dbl();
- P.dbl();
- P.dbl();
- P.dbl();
- P.add(Q);
- }
- P.sub(C); /* apply correction */
- }
- P.affine();
- return P;
- }
-
- /* Return e.this+f.Q */
-
- func mul2(e:BIG,_ Q:ECP,_ f:BIG) -> ECP
- {
- let te=BIG()
- let tf=BIG()
- let mt=BIG()
- let S=ECP()
- let T=ECP()
- let C=ECP()
- var W=[ECP]()
- let n=1+(ROM.NLEN*Int(ROM.BASEBITS)+1)/2
- var w=[Int8](count:n,repeatedValue:0);
-
- affine();
- Q.affine();
-
- te.copy(e);
- tf.copy(f);
-
- // precompute table
- for var i=0;i<8;i++ {W.append(ECP())}
- W[1].copy(self); W[1].sub(Q)
- W[2].copy(self); W[2].add(Q)
- S.copy(Q); S.dbl();
- W[0].copy(W[1]); W[0].sub(S)
- W[3].copy(W[2]); W[3].add(S)
- T.copy(self); T.dbl()
- W[5].copy(W[1]); W[5].add(T)
- W[6].copy(W[2]); W[6].add(T)
- W[4].copy(W[5]); W[4].sub(S)
- W[7].copy(W[6]); W[7].add(S)
-
- // convert the table to affine
- if ROM.CURVETYPE==ROM.WEIERSTRASS
- {ECP.multiaffine(8,W)}
-
- // if multiplier is odd, add 2, else add 1 to multiplier, and add 2P or P to correction
-
- var s=te.parity()
- te.inc(1); te.norm(); var ns=te.parity(); mt.copy(te); mt.inc(1); mt.norm()
- te.cmove(mt,s)
- T.cmove(self,ns)
- C.copy(T)
-
- s=tf.parity()
- tf.inc(1); tf.norm(); ns=tf.parity(); mt.copy(tf); mt.inc(1); mt.norm()
- tf.cmove(mt,s)
- S.cmove(Q,ns)
- C.add(S)
-
- mt.copy(te); mt.add(tf); mt.norm()
- let nb=1+(mt.nbits()+1)/2
-
- // convert exponent to signed 2-bit window
- for var i=0;i<nb;i++
- {
- let a=(te.lastbits(3)-4);
- te.dec(a); te.norm();
- te.fshr(2);
- let b=(tf.lastbits(3)-4);
- tf.dec(b); tf.norm();
- tf.fshr(2);
- w[i]=Int8(4*a+b);
- }
- w[nb]=Int8(4*te.lastbits(3)+tf.lastbits(3));
- S.copy(W[(w[nb]-1)/2]);
-
- for var i=nb-1;i>=0;i--
- {
- T.select(W,Int32(w[i]));
- S.dbl();
- S.dbl();
- S.add(T);
- }
- S.sub(C); /* apply correction */
- S.affine();
- return S;
- }
-
-
-
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/swift/ecp2.swift
----------------------------------------------------------------------
diff --git a/swift/ecp2.swift b/swift/ecp2.swift
deleted file mode 100644
index 058ff5f..0000000
--- a/swift/ecp2.swift
+++ /dev/null
@@ -1,614 +0,0 @@
-/*
-Licensed to the Apache Software Foundation (ASF) under one
-or more contributor license agreements. See the NOTICE file
-distributed with this work for additional information
-regarding copyright ownership. The ASF licenses this file
-to you under the Apache License, Version 2.0 (the
-"License"); you may not use this file except in compliance
-with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
-Unless required by applicable law or agreed to in writing,
-software distributed under the License is distributed on an
-"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-KIND, either express or implied. See the License for the
-specific language governing permissions and limitations
-under the License.
-*/
-//
-// ecp2.swift
-//
-//
-// Created by Michael Scott on 07/07/2015.
-// Copyright (c) 2015 Michael Scott. All rights reserved.
-//
-
-/* CLINT Weierstrass elliptic curve functions over FP2 */
-
-final class ECP2 {
- private var x:FP2
- private var y:FP2
- private var z:FP2
- private var INF:Bool
-
- /* Constructor - set self=O */
- init()
- {
- INF=true
- x=FP2(0)
- y=FP2(1)
- z=FP2(1)
- }
- /* Test self=O? */
- func is_infinity() -> Bool
- {
- return INF
- }
- /* copy self=P */
- func copy(P:ECP2)
- {
- x.copy(P.x)
- y.copy(P.y)
- z.copy(P.z)
- INF=P.INF
- }
- /* set self=O */
- func inf() {
- INF=true
- x.zero()
- y.zero()
- z.zero()
- }
- /* Conditional move of Q to P dependant on d */
- func cmove(Q:ECP2,_ d:Int32)
- {
- x.cmove(Q.x,d);
- y.cmove(Q.y,d);
- z.cmove(Q.z,d);
-
- var bd:Bool
- if d==0 {bd=false}
- else {bd=true}
- INF = (INF != ((INF != Q.INF) && bd))
- }
-
- /* return 1 if b==c, no branching */
- private static func teq(b:Int32,_ c:Int32) -> Int32
- {
- var x=b^c
- x-=1 // if x=0, x now -1
- return ((x>>31)&1)
- }
- /* Constant time select from pre-computed table */
- func select(W:[ECP2],_ b:Int32)
- {
- let MP=ECP2()
- let m=b>>31
- var babs=(b^m)-m
-
- babs=(babs-1)/2
-
- cmove(W[0],ECP2.teq(babs,0)) // conditional move
- cmove(W[1],ECP2.teq(babs,1))
- cmove(W[2],ECP2.teq(babs,2))
- cmove(W[3],ECP2.teq(babs,3))
- cmove(W[4],ECP2.teq(babs,4))
- cmove(W[5],ECP2.teq(babs,5))
- cmove(W[6],ECP2.teq(babs,6))
- cmove(W[7],ECP2.teq(babs,7))
-
- MP.copy(self)
- MP.neg()
- cmove(MP,(m&1))
- }
-
- /* Test if P == Q */
- func equals(Q:ECP2) -> Bool
- {
- if is_infinity() && Q.is_infinity() {return true}
- if is_infinity() || Q.is_infinity() {return false}
-
- let zs2=FP2(z); zs2.sqr()
- let zo2=FP2(Q.z); zo2.sqr()
- let zs3=FP2(zs2); zs3.mul(z)
- let zo3=FP2(zo2); zo3.mul(Q.z)
- zs2.mul(Q.x)
- zo2.mul(x)
- if !zs2.equals(zo2) {return false}
- zs3.mul(Q.y)
- zo3.mul(y)
- if !zs3.equals(zo3) {return false}
-
- return true;
- }
- /* set self=-self */
- func neg()
- {
- if is_infinity() {return}
- y.neg(); y.norm()
- return
- }
- /* set to Affine - (x,y,z) to (x,y) */
- func affine() {
- if is_infinity() {return}
- let one=FP2(1)
- if z.equals(one) {return}
- z.inverse()
-
- let z2=FP2(z)
- z2.sqr()
- x.mul(z2); x.reduce()
- y.mul(z2)
- y.mul(z); y.reduce()
- z.copy(one)
- }
- /* extract affine x as FP2 */
- func getX() -> FP2
- {
- affine()
- return x
- }
- /* extract affine y as FP2 */
- func getY() -> FP2
- {
- affine()
- return y
- }
- /* extract projective x */
- func getx() -> FP2
- {
- return x
- }
- /* extract projective y */
- func gety() -> FP2
- {
- return y
- }
- /* extract projective z */
- func getz() -> FP2
- {
- return z
- }
- /* convert to byte array */
- func toBytes(inout b:[UInt8])
- {
- let RM=Int(ROM.MODBYTES)
- var t=[UInt8](count:RM,repeatedValue:0)
-
- affine();
- x.getA().toBytes(&t)
- for var i=0;i<RM;i++
- {b[i]=t[i]}
- x.getB().toBytes(&t);
- for var i=0;i<RM;i++
- {b[i+RM]=t[i]}
-
- y.getA().toBytes(&t);
- for var i=0;i<RM;i++
- {b[i+2*RM]=t[i]}
- y.getB().toBytes(&t);
- for var i=0;i<RM;i++
- {b[i+3*RM]=t[i]}
- }
- /* convert from byte array to point */
- static func fromBytes(b:[UInt8]) -> ECP2
- {
- let RM=Int(ROM.MODBYTES)
- var t=[UInt8](count:RM,repeatedValue:0)
-
-
- for var i=0;i<RM;i++ {t[i]=b[i]}
- var ra=BIG.fromBytes(t);
- for var i=0;i<RM;i++ {t[i]=b[i+RM]}
- var rb=BIG.fromBytes(t);
- let rx=FP2(ra,rb)
-
- for var i=0;i<RM;i++ {t[i]=b[i+2*RM]}
- ra=BIG.fromBytes(t)
- for var i=0;i<RM;i++ {t[i]=b[i+3*RM]}
- rb=BIG.fromBytes(t)
- let ry=FP2(ra,rb)
-
- return ECP2(rx,ry)
- }
-/* convert self to hex string */
- func toString() -> String
- {
- if is_infinity() {return "infinity"}
- affine()
- return "("+x.toString()+","+y.toString()+")"
- }
-
-/* Calculate RHS of twisted curve equation x^3+B/i */
- static func RHS(x:FP2) -> FP2
- {
- x.norm()
- let r=FP2(x)
- r.sqr()
- let b=FP2(BIG(ROM.CURVE_B))
- b.div_ip();
- r.mul(x);
- r.add(b);
-
- r.reduce();
- return r;
- }
-/* construct self from (x,y) - but set to O if not on curve */
- init(_ ix:FP2,_ iy:FP2)
- {
- x=FP2(ix)
- y=FP2(iy)
- z=FP2(1)
- let rhs=ECP2.RHS(x)
- let y2=FP2(y)
- y2.sqr()
- if y2.equals(rhs) {INF=false}
- else {x.zero(); INF=true}
- }
- /* construct this from x - but set to O if not on curve */
- init(_ ix:FP2)
- {
- x=FP2(ix)
- y=FP2(1)
- z=FP2(1)
- let rhs=ECP2.RHS(x)
- if rhs.sqrt()
- {
- y.copy(rhs);
- INF=false;
- }
- else {x.zero(); INF=true;}
- }
-
- /* this+=this */
- func dbl() -> Int
- {
- if (INF) {return -1}
- if y.iszilch()
- {
- inf();
- return -1;
- }
-
- let w1=FP2(x)
- let w2=FP2(0)
- let w3=FP2(x)
- let w8=FP2(x)
-
- w1.sqr()
- w8.copy(w1)
- w8.imul(3)
-
- w2.copy(y); w2.sqr()
- w3.copy(x); w3.mul(w2)
- w3.imul(4)
- w1.copy(w3); w1.neg()
- w1.norm()
-
- x.copy(w8); x.sqr()
- x.add(w1)
- x.add(w1)
- x.norm()
-
- z.mul(y)
- z.add(z)
-
- w2.add(w2)
- w2.sqr()
- w2.add(w2)
- w3.sub(x)
- y.copy(w8); y.mul(w3)
- w2.norm()
- y.sub(w2)
- y.norm()
- z.norm()
-
- return 1
- }
-/* this+=Q - return 0 for add, 1 for double, -1 for O */
- func add(Q:ECP2) -> Int
- {
- if INF
- {
- copy(Q)
- return -1
- }
- if Q.INF {return -1}
-
- var aff=false
-
- if Q.z.isunity() {aff=true}
-
- var A:FP2
- var C:FP2
- let B=FP2(z)
- let D=FP2(z)
- if (!aff)
- {
- A=FP2(Q.z)
- C=FP2(Q.z)
-
- A.sqr(); B.sqr()
- C.mul(A); D.mul(B)
-
- A.mul(x)
- C.mul(y)
- }
- else
- {
- A=FP2(x)
- C=FP2(y)
-
- B.sqr()
- D.mul(B)
- }
-
- B.mul(Q.x); B.sub(A)
- D.mul(Q.y); D.sub(C)
-
- if B.iszilch()
- {
- if D.iszilch()
- {
- dbl()
- return 1
- }
- else
- {
- INF=true
- return -1
- }
- }
-
- if !aff {z.mul(Q.z)}
- z.mul(B)
-
- let e=FP2(B); e.sqr()
- B.mul(e)
- A.mul(e)
-
- e.copy(A)
- e.add(A); e.add(B)
- x.copy(D); x.sqr(); x.sub(e)
-
- A.sub(x)
- y.copy(A); y.mul(D)
- C.mul(B); y.sub(C)
-
- x.norm()
- y.norm()
- z.norm()
-
- return 0
- }
-
- /* set self-=Q */
- func sub(Q:ECP2) -> Int
- {
- Q.neg()
- let D=add(Q)
- Q.neg()
- return D
- }
-/* set self*=q, where q is Modulus, using Frobenius */
- func frob(X:FP2)
- {
- if INF {return}
- let X2=FP2(X)
- X2.sqr()
- x.conj()
- y.conj()
- z.conj()
- z.reduce()
- x.mul(X2)
- y.mul(X2)
- y.mul(X)
- }
- /* normalises m-array of ECP2 points. Requires work vector of m FP2s */
-
- private static func multiaffine(m:Int,_ P:[ECP2])
- {
- let t1=FP2(0)
- let t2=FP2(0)
-
- var work=[FP2]()
- for var i=0;i<m;i++
- {work.append(FP2(0))}
-
- work[0].one()
- work[1].copy(P[0].z)
-
- for var i=2;i<m;i++
- {
- work[i].copy(work[i-1])
- work[i].mul(P[i-1].z)
- }
-
- t1.copy(work[m-1]); t1.mul(P[m-1].z)
-
- t1.inverse()
-
- t2.copy(P[m-1].z)
- work[m-1].mul(t1)
-
- for var i=m-2;;i--
- {
- if (i==0)
- {
- work[0].copy(t1)
- work[0].mul(t2)
- break;
- }
- work[i].mul(t2)
- work[i].mul(t1)
- t2.mul(P[i].z)
- }
- /* now work[] contains inverses of all Z coordinates */
-
- for var i=0;i<m;i++
- {
- P[i].z.one()
- t1.copy(work[i]); t1.sqr()
- P[i].x.mul(t1)
- t1.mul(work[i])
- P[i].y.mul(t1)
- }
- }
-
- /* P*=e */
- func mul(e:BIG) -> ECP2
- {
- /* fixed size windows */
- let mt=BIG()
- let t=BIG()
- let P=ECP2()
- let Q=ECP2()
- let C=ECP2()
-
- var W=[ECP2]();
- for var i=0;i<8;i++ {W.append(ECP2())}
-
- var w=[Int8](count:1+(ROM.NLEN*Int(ROM.BASEBITS)+3)/4,repeatedValue:0)
-
- if is_infinity() {return ECP2()}
-
- affine()
-
- /* precompute table */
- Q.copy(self)
- Q.dbl()
- W[0].copy(self)
-
- for var i=1;i<8;i++
- {
- W[i].copy(W[i-1])
- W[i].add(Q)
- }
-
- /* convert the table to affine */
-
- ECP2.multiaffine(8,W);
-
- /* make exponent odd - add 2P if even, P if odd */
- t.copy(e)
- let s=t.parity()
- t.inc(1); t.norm(); let ns=t.parity(); mt.copy(t); mt.inc(1); mt.norm()
- t.cmove(mt,s)
- Q.cmove(self,ns)
- C.copy(Q)
-
- let nb=1+(t.nbits()+3)/4
- /* convert exponent to signed 4-bit window */
- for var i=0;i<nb;i++
- {
- w[i]=Int8(t.lastbits(5)-16)
- t.dec(Int32(w[i])); t.norm()
- t.fshr(4)
- }
- w[nb]=Int8(t.lastbits(5))
-
- P.copy(W[(w[nb]-1)/2])
- for var i=nb-1;i>=0;i--
- {
- Q.select(W,Int32(w[i]))
- P.dbl()
- P.dbl()
- P.dbl()
- P.dbl()
- P.add(Q)
- }
- P.sub(C);
- P.affine()
- return P;
- }
-
- /* P=u0.Q0+u1*Q1+u2*Q2+u3*Q3 */
- static func mul4(Q:[ECP2],_ u:[BIG]) -> ECP2
- {
- var a=[Int32](count:4,repeatedValue:0)
- let T=ECP2()
- let C=ECP2()
- let P=ECP2()
-
- var W=[ECP2]();
- for var i=0;i<8;i++ {W.append(ECP2())}
-
- let mt=BIG()
- var t=[BIG]()
-
- var w=[Int8](count:ROM.NLEN*Int(ROM.BASEBITS)+1,repeatedValue:0)
-
- for var i=0;i<4;i++
- {
- t.append(BIG(u[i]))
- Q[i].affine()
- }
-
- /* precompute table */
-
- W[0].copy(Q[0]); W[0].sub(Q[1])
- W[1].copy(W[0])
- W[2].copy(W[0])
- W[3].copy(W[0])
- W[4].copy(Q[0]); W[4].add(Q[1])
- W[5].copy(W[4])
- W[6].copy(W[4])
- W[7].copy(W[4])
- T.copy(Q[2]); T.sub(Q[3])
- W[1].sub(T)
- W[2].add(T)
- W[5].sub(T)
- W[6].add(T)
- T.copy(Q[2]); T.add(Q[3])
- W[0].sub(T)
- W[3].add(T)
- W[4].sub(T)
- W[7].add(T)
-
- ECP2.multiaffine(8,W);
-
- /* if multiplier is even add 1 to multiplier, and add P to correction */
- mt.zero(); C.inf()
- for var i=0;i<4;i++
- {
- if (t[i].parity()==0)
- {
- t[i].inc(1); t[i].norm()
- C.add(Q[i])
- }
- mt.add(t[i]); mt.norm()
- }
-
- let nb=1+mt.nbits();
-
- /* convert exponent to signed 1-bit window */
- for var j=0;j<nb;j++
- {
- for var i=0;i<4;i++
- {
- a[i]=(t[i].lastbits(2)-2)
- t[i].dec(a[i]); t[i].norm()
- t[i].fshr(1)
- }
- w[j]=Int8(8*a[0]+4*a[1]+2*a[2]+a[3])
- }
- w[nb]=Int8(8*t[0].lastbits(2)+4*t[1].lastbits(2))
- w[nb]+=Int8(2*t[2].lastbits(2)+t[3].lastbits(2))
-
- P.copy(W[(w[nb]-1)/2])
- for var i=nb-1;i>=0;i--
- {
- T.select(W,Int32(w[i]))
- P.dbl()
- P.add(T)
- }
- P.sub(C) /* apply correction */
-
- P.affine()
- return P
- }
-
-
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/swift/ff.swift
----------------------------------------------------------------------
diff --git a/swift/ff.swift b/swift/ff.swift
deleted file mode 100644
index 0491a77..0000000
--- a/swift/ff.swift
+++ /dev/null
@@ -1,918 +0,0 @@
-/*
-Licensed to the Apache Software Foundation (ASF) under one
-or more contributor license agreements. See the NOTICE file
-distributed with this work for additional information
-regarding copyright ownership. The ASF licenses this file
-to you under the Apache License, Version 2.0 (the
-"License"); you may not use this file except in compliance
-with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
-Unless required by applicable law or agreed to in writing,
-software distributed under the License is distributed on an
-"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-KIND, either express or implied. See the License for the
-specific language governing permissions and limitations
-under the License.
-*/
-//
-// ff.swift
-//
-//
-// Created by Michael Scott on 24/06/2015.
-// Copyright (c) 2015 Michael Scott. All rights reserved.
-//
-
-/* Large Finite Field arithmetic */
-/* CLINT mod p functions */
-
-final class FF {
- var v = [BIG]()
- var length:Int=1
-
- private static let P_MBITS:Int32=ROM.MODBYTES*8
- private static let P_MB=(P_MBITS%ROM.BASEBITS)
- private static let P_OMASK=(Int32(-1)<<(P_MBITS%ROM.BASEBITS))
- private static let P_FEXCESS=(Int32(1)<<(ROM.BASEBITS*Int32(ROM.NLEN)-P_MBITS))
- private static let P_TBITS=(P_MBITS%ROM.BASEBITS)
-
- func P_EXCESS() -> Int32
- {
- return ((v[length-1].w[ROM.NLEN-1]&FF.P_OMASK)>>FF.P_MB)
- }
- /* Constructors */
- init(_ n: Int)
- {
- for var i=0;i<n;i++
- {
- v.append(BIG(0));
- }
- length=n;
- }
-
- init(_ x: [[Int32]],n: Int)
- {
- for var i=0;i<n;i++
- {
- v.append(BIG(x[i]))
- }
- length=n;
- }
-
- func getlen() -> Int
- {
- return length;
- }
-
- /* set to zero */
- func zero()
- {
- for var i=0;i<length;i++
- {
- v[i].zero();
- }
- }
-
- /* set to integer */
- func set(m: Int32)
- {
- zero();
- v[0].set(0,(m&ROM.MASK));
- v[0].set(1,(m>>ROM.BASEBITS));
- }
-
- /* copy from FF b */
- func copy(b: FF)
- {
- for var i=0;i<length;i++
- {
- v[i].copy(b.v[i]);
- }
- }
-
- /* x=y<<n */
- func dsucopy(b: FF)
- {
- for var i=0;i<b.length;i++
- {
- v[b.length+i].copy(b.v[i]);
- v[i].zero();
- }
- }
- /* x=y */
- func dscopy(b: FF)
- {
- for var i=0;i<b.length;i++
- {
- v[i].copy(b.v[i]);
- v[b.length+i].zero();
- }
- }
- /* x=y>>n */
- func sducopy(b: FF)
- {
- for var i=0;i<length;i++
- {
- v[i].copy(b.v[length+i]);
- }
- }
- func one()
- {
- v[0].one();
- for var i=1;i<length;i++
- {
- v[i].zero();
- }
- }
- /* test equals 0 */
- func iszilch() -> Bool
- {
- for var i=0;i<length;i++
- {
- if (!v[i].iszilch()) {return false}
- }
- return true;
- }
- /* shift right by 256-bit words */
- func shrw(n: Int)
- {
- for var i=0;i<n;i++
- {
- v[i].copy(v[i+n]);
- v[i+n].zero();
- }
- }
-
- /* shift left by 256-bit words */
- func shlw(n: Int)
- {
- for var i=0;i<n;i++
- {
- v[n+i].copy(v[i]);
- v[i].zero();
- }
- }
-
- /* extract last bit */
- func parity() -> Int32
- {
- return v[0].parity()
- }
-
- func lastbits(m: Int) ->Int32
- {
- return v[0].lastbits(m);
- }
-
- /* compare x and y - must be normalised, and of same length */
- static func comp(a: FF,_ b:FF) -> Int
- {
- for var i=a.length-1;i>=0;i--
- {
- let j=BIG.comp(a.v[i],b.v[i])
- if j != 0 {return j}
- }
- return 0;
- }
- /* recursive add */
- func radd(vp: Int,_ x:FF,_ xp:Int,_ y:FF,_ yp:Int,_ n: Int)
- {
- for var i=0;i<n;i++
- {
- v[vp+i].copy(x.v[xp+i])
- v[vp+i].add(y.v[yp+i])
- }
- }
- /* recursive inc */
- func rinc(vp: Int,_ y: FF,_ yp: Int,_ n:Int)
- {
- for var i=0;i<n;i++
- {
- v[vp+i].add(y.v[yp+i])
- }
- }
- /* recursive add */
- func rsub(vp: Int,_ x:FF,_ xp:Int,_ y:FF,_ yp:Int,_ n: Int)
- {
- for var i=0;i<n;i++
- {
- v[vp+i].copy(x.v[xp+i])
- v[vp+i].sub(y.v[yp+i])
- }
- }
- /* recursive inc */
- func rdec(vp: Int,_ y: FF,_ yp: Int,_ n:Int)
- {
- for var i=0;i<n;i++
- {
- v[vp+i].sub(y.v[yp+i])
- }
- }
- /* simple add */
- func add(b: FF)
- {
- for var i=0;i<length;i++
- {v[i].add(b.v[i])}
- }
-
- /* simple sub */
- func sub(b: FF)
- {
- for var i=0;i<length;i++
- {v[i].sub(b.v[i])}
- }
- /* reverse sub */
- func revsub(b: FF)
- {
- for var i=0;i<length;i++
- {v[i].rsub(b.v[i])}
- }
- /* normalise - but hold any overflow in top part unless n<0 */
- private func rnorm(vp: Int,_ n: Int)
- {
- var trunc=false;
- var nn=n
-
- if (nn<0)
- { /* -v n signals to do truncation */
- nn = -nn
- trunc=true;
- }
- for var i=0;i<nn-1;i++
- {
- let carry=v[vp+i].norm();
- v[vp+i].xortop(carry<<FF.P_TBITS)
- v[vp+i+1].inc(carry)
- }
- let carry=v[vp+nn-1].norm();
- if (trunc)
- {v[vp+nn-1].xortop(carry<<FF.P_TBITS)}
- }
-
- func norm()
- {
- rnorm(0,length)
- }
-
- /* increment/decrement by a small integer */
- func inc(m: Int32)
- {
- v[0].inc(m);
- norm();
- }
-
- func dec(m: Int32)
- {
- v[0].dec(m);
- norm();
- }
-
- /* shift left by one bit */
- func shl()
- {
- var delay_carry:Int32=0;
- for var i=0;i<length-1;i++
- {
- let carry=v[i].fshl(1)
- v[i].inc(delay_carry);
- v[i].xortop(carry<<FF.P_TBITS);
- delay_carry=carry;
- }
- v[length-1].fshl(1)
- v[length-1].inc(delay_carry)
- }
-
- /* shift right by one bit */
- func shr()
- {
- for var i=length-1;i>0;i--
- {
- let carry=v[i].fshr(1);
- v[i-1].ortop(carry<<FF.P_TBITS);
- }
- v[0].fshr(1);
- }
-
- /* Convert to Hex String */
- func toString() -> String
- {
- norm();
- var s="";
- for var i=length-1;i>=0;i--
- {
- s+=v[i].toString();
- }
- return s;
- }
-
- /* Convert FFs to/from byte arrays */
- func toBytes(inout b: [UInt8])
- {
- for var i=0;i<length;i++
- {
- v[i].tobytearray(&b,(length-i-1)*Int(ROM.MODBYTES))
- }
- }
- static func fromBytes(x: FF,_ b:[UInt8])
- {
- for var i=0;i<x.length;i++
- {
- x.v[i]=BIG.frombytearray(b,(x.length-i-1)*Int(ROM.MODBYTES))
- }
- }
-
- /* in-place swapping using xor - side channel resistant - lengths must be the same */
- private static func cswap(a: FF,_ b:FF,_ d:Int32)
- {
- for var i=0;i<a.length;i++
- {
- a.v[i].cswap(b.v[i],d)
- }
- }
- /* z=x*y, t is workspace */
- private func karmul(vp: Int,_ x: FF,_ xp: Int,_ y:FF,_ yp: Int,_ t:FF,_ tp:Int,_ n:Int)
- {
- if (n==1)
- {
- let d=BIG.mul(x.v[xp],y.v[yp])
- v[vp+1]=d.split(8*ROM.MODBYTES)
- v[vp].copy(d)
- return
- }
- let nd2=n/2
- radd(vp,x,xp,x,xp+nd2,nd2)
- rnorm(vp,nd2)
- radd(vp+nd2,y,yp,y,yp+nd2,nd2)
- rnorm(vp+nd2,nd2)
-
- t.karmul(tp,self,vp,self,vp+nd2,t,tp+n,nd2)
- karmul(vp,x,xp,y,yp,t,tp+n,nd2)
- karmul(vp+n,x,xp+nd2,y,yp+nd2,t,tp+n,nd2)
- t.rdec(tp,self,vp,n)
- t.rdec(tp,self,vp+n,n)
- rinc(vp+nd2,t,tp,n)
- rnorm(vp,2*n)
- }
-
- private func karsqr(vp: Int,_ x: FF,_ xp:Int,_ t:FF,_ tp:Int,_ n:Int)
- {
- if (n==1)
- {
- let d=BIG.sqr(x.v[xp])
- v[vp+1].copy(d.split(8*ROM.MODBYTES))
- v[vp].copy(d);
- return;
- }
-
- let nd2=n/2
- karsqr(vp,x,xp,t,tp+n,nd2)
- karsqr(vp+n,x,xp+nd2,t,tp+n,nd2)
- t.karmul(tp,x,xp,x,xp+nd2,t,tp+n,nd2)
- rinc(vp+nd2,t,tp,n)
- rinc(vp+nd2,t,tp,n)
- rnorm(vp+nd2,n)
- }
- private func karmul_lower(vp:Int,_ x:FF,_ xp:Int,_ y:FF,_ yp:Int,_ t:FF,_ tp:Int,_ n: Int)
- { /* Calculates Least Significant bottom half of x*y */
- if (n==1)
- { /* only calculate bottom half of product */
- v[vp].copy(BIG.smul(x.v[xp],y.v[yp]))
- return
- }
- let nd2=n/2
-
- karmul(vp,x,xp,y,yp,t,tp+n,nd2)
- t.karmul_lower(tp,x,xp+nd2,y,yp,t,tp+n,nd2);
- rinc(vp+nd2,t,tp,nd2);
- t.karmul_lower(tp,x,xp,y,yp+nd2,t,tp+n,nd2);
- rinc(vp+nd2,t,tp,nd2);
- rnorm(vp+nd2,-nd2); /* truncate it */
- }
-
- private func karmul_upper(x: FF,_ y:FF,_ t:FF,_ n:Int)
- { /* Calculates Most Significant upper half of x*y, given lower part */
- let nd2=n/2;
- radd(n,x,0,x,nd2,nd2);
- radd(n+nd2,y,0,y,nd2,nd2);
-
- t.karmul(0,self,n+nd2,self,n,t,n,nd2); /* t = (a0+a1)(b0+b1) */
- karmul(n,x,nd2,y,nd2,t,n,nd2); /* z[n]= a1*b1 */
- /* z[0-nd2]=l(a0b0) z[nd2-n]= h(a0b0)+l(t)-l(a0b0)-l(a1b1) */
- t.rdec(0,self,n,n); /* t=t-a1b1 */
- rinc(nd2,self,0,nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */
- rdec(nd2,t,0,nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */
- rnorm(0,-n); /* a0b0 now in z - truncate it */
- t.rdec(0,self,0,n); /* (a0+a1)(b0+b1) - a0b0 */
- rinc(nd2,t,0,n);
-
- rnorm(nd2,n);
- }
- /* z=x*y. Assumes x and y are of same length. */
- static func mul(x: FF,_ y:FF) -> FF
- {
- let n=x.length
- let z=FF(2*n)
- let t=FF(2*n)
- z.karmul(0,x,0,y,0,t,0,n)
- return z
- }
-
- /* z=x^2 */
- static func sqr(x: FF) -> FF
- {
- let n=x.length
- let z=FF(2*n)
- let t=FF(2*n)
- z.karsqr(0,x,0,t,0,n)
- return z
- }
- /* return low part of product self*y */
- func lmul(y: FF)
- {
- let n=length;
- let t=FF(2*n);
- let x=FF(n); x.copy(self);
- karmul_lower(0,x,0,y,0,t,0,n);
- }
-
- /* Set b=b mod c */
- func mod(c: FF)
- {
- var k=0
-
- norm()
- if (FF.comp(self,c)<0)
- {return}
- repeat
- {
- c.shl()
- k++
- } while (FF.comp(self,c)>=0)
-
- while (k>0)
- {
- c.shr();
- if (FF.comp(self,c)>=0)
- {
- sub(c)
- norm()
- }
- k--
- }
- }
-
- /* return This mod modulus, N is modulus, ND is Montgomery Constant */
- func reduce(N: FF,_ ND:FF) -> FF
- { /* fast karatsuba Montgomery reduction */
- let n=N.length
- let t=FF(2*n)
- let r=FF(n)
- let m=FF(n)
-
- r.sducopy(self)
- m.karmul_lower(0,self,0,ND,0,t,0,n)
- karmul_upper(N,m,t,n)
- m.sducopy(self)
-
- r.add(N);
- r.sub(m);
- r.norm();
-
- return r;
- }
- /* Set r=this mod b */
- /* this is of length - 2*n */
- /* r,b is of length - n */
- func dmod(b: FF) -> FF
- {
- let n=b.length
- let m=FF(2*n)
- let x=FF(2*n)
- let r=FF(n)
-
- x.copy(self)
- x.norm()
- m.dsucopy(b)
- var k=256*n
-
- while (k>0)
- {
- m.shr()
-
- if (FF.comp(x,m)>=0)
- {
- x.sub(m);
- x.norm();
- }
- k--;
- }
-
- r.copy(x);
- r.mod(b);
- return r;
- }
- /* Set return=1/this mod p. Binary method - a<p on entry */
-
- func invmodp(p: FF)
- {
- let n=p.length;
-
- let u=FF(n)
- let v=FF(n)
- let x1=FF(n)
- let x2=FF(n)
- let t=FF(n)
- let one=FF(n)
-
- one.one()
- u.copy(self)
- v.copy(p)
- x1.copy(one)
- x2.zero()
-
- // reduce n in here as well!
- while (FF.comp(u,one) != 0 && FF.comp(v,one) != 0)
- {
- while (u.parity()==0)
- {
- u.shr()
- if (x1.parity() != 0)
- {
- x1.add(p)
- x1.norm()
- }
- x1.shr()
- }
- while (v.parity()==0)
- {
- v.shr()
- if (x2.parity() != 0)
- {
- x2.add(p)
- x2.norm()
- }
- x2.shr();
- }
- if (FF.comp(u,v)>=0)
- {
- u.sub(v)
- u.norm()
- if (FF.comp(x1,x2)>=0) {x1.sub(x2)}
- else
- {
- t.copy(p)
- t.sub(x2)
- x1.add(t)
- }
- x1.norm()
- }
- else
- {
- v.sub(u)
- v.norm()
- if (FF.comp(x2,x1)>=0) {x2.sub(x1)}
- else
- {
- t.copy(p)
- t.sub(x1)
- x2.add(t)
- }
- x2.norm()
- }
- }
- if FF.comp(u,one)==0
- {copy(x1)}
- else
- {copy(x2)}
- }
-
- /* nresidue mod m */
- func nres(m: FF)
- {
- let n=m.length
- let d=FF(2*n)
- d.dsucopy(self)
- copy(d.dmod(m))
- }
-
- func redc(m: FF,_ ND:FF)
- {
- let n=m.length
- let d=FF(2*n)
- mod(m)
- d.dscopy(self)
- copy(d.reduce(m,ND))
- mod(m)
- }
- private func mod2m(m: Int)
- {
- for var i=m;i<length;i++
- {v[i].zero()}
- }
- /* U=1/a mod 2^m - Arazi & Qi */
- private func invmod2m() -> FF
- {
- let n=length;
-
- let b=FF(n);
- let c=FF(n);
- let U=FF(n);
-
- U.zero();
- U.v[0].copy(v[0]);
- U.v[0].invmod2m();
-
- for var i=1;i<n;i<<=1
- {
- b.copy(self); b.mod2m(i);
- let t=FF.mul(U,b); t.shrw(i); b.copy(t);
- c.copy(self); c.shrw(i); c.mod2m(i);
- c.lmul(U); c.mod2m(i);
-
- b.add(c); b.norm();
- b.lmul(U); b.mod2m(i);
-
- c.one(); c.shlw(i); b.revsub(c); b.norm();
- b.shlw(i);
- U.add(b);
- }
- U.norm();
- return U;
- }
-
- func random(rng: RAND)
- {
- let n=length;
- for var i=0;i<n;i++
- {
- v[i].copy(BIG.random(rng));
- }
- /* make sure top bit is 1 */
- while (v[n-1].nbits()<Int(ROM.MODBYTES)*8) {v[n-1].copy(BIG.random(rng))}
- }
- /* generate random x */
- func randomnum(p: FF,_ rng: RAND)
- {
- let n=length;
- let d=FF(2*n);
-
- for var i=0;i<2*n;i++
- {
- d.v[i].copy(BIG.random(rng));
- }
- copy(d.dmod(p));
- }
- /* this*=y mod p */
- func modmul(y: FF,_ p:FF,_ nd: FF)
- {
- let ex=P_EXCESS();
- let ey=y.P_EXCESS();
- if ((ex+1)*(ey+1)+1>=FF.P_FEXCESS) {mod(p)}
- let d=FF.mul(self,y);
- copy(d.reduce(p,nd));
- }
-
- /* this*=y mod p */
- func modsqr(p: FF,_ nd:FF)
- {
- let ex=P_EXCESS();
- if ((ex+1)*(ex+1)+1>=FF.P_FEXCESS) {mod(p)}
- let d=FF.sqr(self);
- copy(d.reduce(p,nd));
- }
-
- /* self=self^e mod p using side-channel resistant Montgomery Ladder, for large e */
- func skpow(e: FF,_ p:FF)
- {
- let n=p.length
- let R0=FF(n)
- let R1=FF(n)
- let ND=p.invmod2m()
-
- mod(p)
- R0.one()
- R1.copy(self)
- R0.nres(p)
- R1.nres(p)
-
- for var i=8*Int(ROM.MODBYTES)*n-1;i>=0;i--
- {
- let b=Int32(e.v[i/256].bit(i%256))
- copy(R0)
- modmul(R1,p,ND)
-
- FF.cswap(R0,R1,b)
- R0.modsqr(p,ND)
-
- R1.copy(self)
- FF.cswap(R0,R1,b)
-
- }
-
- copy(R0)
- redc(p,ND)
- }
-
- /* this =this^e mod p using side-channel resistant Montgomery Ladder, for short e */
- func skpow(e: BIG,_ p:FF)
- {
- let n=p.length
- let R0=FF(n)
- let R1=FF(n)
- let ND=p.invmod2m()
-
- mod(p)
- R0.one()
- R1.copy(self)
- R0.nres(p)
- R1.nres(p)
-
- for var i=8*Int(ROM.MODBYTES)-1;i>=0;i--
- {
- let b=Int32(e.bit(i))
- copy(R0)
- modmul(R1,p,ND)
-
- FF.cswap(R0,R1,b)
- R0.modsqr(p,ND)
-
- R1.copy(self)
- FF.cswap(R0,R1,b)
- }
- copy(R0)
- redc(p,ND)
- }
-
- /* raise to an integer power - right-to-left method */
- func power(e:Int32,_ p:FF)
- {
- let n=p.length
- var f=true
- let w=FF(n)
- let ND=p.invmod2m()
- var ee=e;
-
- w.copy(self)
- w.nres(p)
-
- if (ee==2)
- {
- copy(w)
- modsqr(p,ND)
- }
- else
- {
- while true
- {
- if (ee%2==1)
- {
- if (f) {copy(w)}
- else {modmul(w,p,ND)}
- f=false;
- }
- ee>>=1;
- if (ee==0) {break}
- w.modsqr(p,ND)
- }
- }
- redc(p,ND)
- }
-
- /* this=this^e mod p, faster but not side channel resistant */
- func pow(e: FF,_ p:FF)
- {
- let n=p.length
- let w=FF(n)
- let ND=p.invmod2m()
-
- w.copy(self);
- one();
- nres(p);
- w.nres(p);
- for var i=8*Int(ROM.MODBYTES)*n-1;i>=0;i--
- {
- modsqr(p,ND)
- let b=e.v[i/256].bit(i%256)
- if (b==1) {modmul(w,p,ND)}
- }
- redc(p,ND);
- }
- /* double exponentiation r=x^e.y^f mod p */
- func pow2(e: BIG,_ y:FF,_ f:BIG,_ p:FF)
- {
- let n=p.length
- let xn=FF(n)
- let yn=FF(n)
- let xy=FF(n)
- let ND=p.invmod2m()
-
- xn.copy(self)
- yn.copy(y)
- xn.nres(p)
- yn.nres(p)
- xy.copy(xn); xy.modmul(yn,p,ND)
- one()
- nres(p)
-
- for var i=8*Int(ROM.MODBYTES)-1;i>=0;i--
- {
- let eb=e.bit(i)
- let fb=f.bit(i)
- modsqr(p,ND)
- if (eb==1)
- {
- if (fb==1) {modmul(xy,p,ND)}
- else {modmul(xn,p,ND)}
- }
- else
- {
- if (fb==1) {modmul(yn,p,ND)}
- }
- }
- redc(p,ND)
- }
- static func igcd(x:Int32,_ y:Int32) -> Int32
- { /* integer GCD, returns GCD of x and y */
- var xx=x;
- var yy=y;
- if (yy==0) {return xx}
- while true
- {
- let r=xx%yy; if r==0 {break}
- xx=yy; yy=r;
- }
- return yy;
- }
-
- /* quick and dirty check for common factor with n */
- func cfactor(s: Int32) -> Bool
- {
- let n=length;
- let x=FF(n);
- let y=FF(n);
- y.set(s);
-
- x.copy(self);
- x.norm();
-
- repeat
- {
- x.sub(y);
- x.norm();
- while ( (!x.iszilch()) && x.parity()==0) {x.shr()}
- } while (FF.comp(x,y)>0);
- let g=x.v[0].get(0);
- let r=FF.igcd(s,g);
-
- if (r>1) {return true}
- return false;
- }
-
- /* Miller-Rabin test for primality. Slow. */
- static func prime(p: FF,_ rng:RAND) -> Bool
- {
- var s=0
- let n=p.length
- var loop:Bool
-
- let d=FF(n)
- let x=FF(n)
- let unity=FF(n)
- let nm1=FF(n)
-
- let sf:Int32=4849845; /* 3*5*.. *19 */
- p.norm();
- if (p.cfactor(sf)) {return false}
- unity.one();
- nm1.copy(p);
- nm1.sub(unity);
- nm1.norm();
- d.copy(nm1);
-
- while (d.parity()==0)
- {
- d.shr();
- s++;
- }
-
- if (s==0) {return false}
- for var i=0;i<10;i++
- {
- x.randomnum(p,rng)
- x.pow(d,p)
- if (FF.comp(x,unity)==0 || FF.comp(x,nm1)==0) {continue}
- loop=false
- for var j=1;j<s;j++
- {
- x.power(2,p);
- if (FF.comp(x,unity)==0) {return false}
- if (FF.comp(x,nm1)==0) {loop=true; break;}
- }
- if (loop) {continue}
- return false;
- }
- return true;
- }
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/swift/fp.swift
----------------------------------------------------------------------
diff --git a/swift/fp.swift b/swift/fp.swift
deleted file mode 100644
index 0bd0f46..0000000
--- a/swift/fp.swift
+++ /dev/null
@@ -1,290 +0,0 @@
-/*
-Licensed to the Apache Software Foundation (ASF) under one
-or more contributor license agreements. See the NOTICE file
-distributed with this work for additional information
-regarding copyright ownership. The ASF licenses this file
-to you under the Apache License, Version 2.0 (the
-"License"); you may not use this file except in compliance
-with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
-Unless required by applicable law or agreed to in writing,
-software distributed under the License is distributed on an
-"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-KIND, either express or implied. See the License for the
-specific language governing permissions and limitations
-under the License.
-*/
-//
-// fp.swift
-//
-//
-// Created by Michael Scott on 20/06/2015.
-// Copyright (c) 2015 Michael Scott. All rights reserved.
-// Small Finite Field arithmetic
-// CLINT mod p functions
-//
-
-final class FP {
- var x:BIG
- static let p=BIG(ROM.Modulus)
-/* convert to Montgomery n-residue form */
- func nres()
- {
- if ROM.MODTYPE != ROM.PSEUDO_MERSENNE
- {
- let d=DBIG(x)
- d.shl(ROM.NLEN*Int(ROM.BASEBITS))
- x.copy(d.mod(FP.p))
- }
- }
-/* convert back to regular form */
- func redc() -> BIG
- {
- if ROM.MODTYPE != ROM.PSEUDO_MERSENNE
- {
- let d=DBIG(x)
- return BIG.mod(d)
- }
- else
- {
- let r=BIG(x)
- return r;
- }
- }
-
- init()
- {
- x=BIG(0)
- }
- init(_ a: Int32)
- {
- x=BIG(a)
- nres()
- }
- init(_ a: BIG)
- {
- x=BIG(a)
- nres()
- }
- init(_ a: FP)
- {
- x=BIG(a.x)
- }
- /* convert to string */
- func toString() -> String
- {
- let s=redc().toString();
- return s;
- }
-
- func toRawString() -> String
- {
- let s=x.toRawString();
- return s;
- }
-/* reduce this mod Modulus */
- func reduce()
- {
- x.mod(FP.p)
- }
-
-/* test this=0? */
- func iszilch() -> Bool
- {
- reduce();
- return x.iszilch()
- }
-
-/* copy from FP b */
- func copy(b: FP)
- {
- x.copy(b.x);
- }
-
-/* set this=0 */
- func zero()
- {
- x.zero();
- }
-
-/* set this=1 */
- func one()
- {
- x.one(); nres()
- }
-
-/* normalise this */
- func norm()
- {
- x.norm();
- }
-/* swap FPs depending on d */
- func cswap(b: FP,_ d: Int32)
- {
- x.cswap(b.x,d)
- }
-
-/* copy FPs depending on d */
- func cmove(b: FP,_ d:Int32)
- {
- x.cmove(b.x,d);
- }
-/* this*=b mod Modulus */
- func mul(b: FP)
- {
- let ea=BIG.EXCESS(x)
- let eb=BIG.EXCESS(b.x)
-
- if (ea+1)*(eb+1)+1>=ROM.FEXCESS {reduce()}
-
- let d=BIG.mul(x,b.x)
- x.copy(BIG.mod(d))
- }
-/* this = -this mod Modulus */
- func neg()
- {
- let m=BIG(FP.p);
-
- norm();
-
- var ov=BIG.EXCESS(x);
- var sb=1; while(ov != 0) {sb++;ov>>=1}
-
- m.fshl(sb)
- x.rsub(m)
-
- if BIG.EXCESS(x)>=ROM.FEXCESS {reduce()}
- }
- /* this*=c mod Modulus, where c is a small int */
- func imul(c: Int32)
- {
- var cc=c
- norm();
- var s=false
- if (cc<0)
- {
- cc = -cc
- s=true
- }
- let afx=(BIG.EXCESS(x)+1)*(cc+1)+1;
- if cc<ROM.NEXCESS && afx<ROM.FEXCESS
- {
- x.imul(cc);
- }
- else
- {
- if afx<ROM.FEXCESS {x.pmul(cc)}
- else
- {
- let d=x.pxmul(cc);
- x.copy(d.mod(FP.p));
- }
- }
- if s {neg()}
- norm();
- }
-
-/* this*=this mod Modulus */
- func sqr()
- {
- let ea=BIG.EXCESS(x);
- if (ea+1)*(ea+1)+1>=ROM.FEXCESS {reduce()}
-
- let d=BIG.sqr(x);
- x.copy(BIG.mod(d));
- }
-
-/* this+=b */
- func add(b: FP)
- {
- x.add(b.x);
- if BIG.EXCESS(x)+2>=ROM.FEXCESS {reduce()}
- }
-/* this-=b */
- func sub(b: FP)
- {
- let n=FP(b)
- n.neg()
- self.add(n)
- }
-/* this/=2 mod Modulus */
- func div2()
- {
- x.norm()
- if (x.parity()==0)
- {x.fshr(1)}
- else
- {
- x.add(FP.p)
- x.norm()
- x.fshr(1)
- }
- }
-/* this=1/this mod Modulus */
- func inverse()
- {
- let r=redc()
- r.invmodp(FP.p)
- x.copy(r)
- nres()
- }
-
-/* return TRUE if this==a */
- func equals(a: FP) -> Bool
- {
- a.reduce()
- reduce()
- if (BIG.comp(a.x,x)==0) {return true}
- return false;
- }
-/* return this^e mod Modulus */
- func pow(e: BIG) -> FP
- {
- let r=FP(1)
- e.norm()
- x.norm()
- let m=FP(self)
- while (true)
- {
- let bt=e.parity()
- e.fshr(1)
- if bt==1 {r.mul(m)}
- if e.iszilch() {break}
- m.sqr();
- }
- r.x.mod(FP.p);
- return r;
- }
-/* return sqrt(this) mod Modulus */
- func sqrt() -> FP
- {
- reduce();
- let b=BIG(FP.p)
- if (ROM.MOD8==5)
- {
- b.dec(5); b.norm(); b.shr(3)
- let i=FP(self); i.x.shl(1)
- let v=i.pow(b)
- i.mul(v); i.mul(v)
- i.x.dec(1)
- let r=FP(self)
- r.mul(v); r.mul(i)
- r.reduce()
- return r
- }
- else
- {
- b.inc(1); b.norm(); b.shr(2)
- return pow(b)
- }
- }
-/* return jacobi symbol (this/Modulus) */
- func jacobi() -> Int
- {
- let w=redc()
- return w.jacobi(FP.p)
- }
-
-}