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) - } - -}
