http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/swift/ecdh.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ecdh.swift b/version22/swift/ecdh.swift new file mode 100644 index 0000000..fd1d863 --- /dev/null +++ b/version22/swift/ecdh.swift @@ -0,0 +1,587 @@ +/* + 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 +import Darwin + +/* 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=16; + static public let EBS=16; + static public let SHA256=32 + static public let SHA384=48 + static public let SHA512=64 + + static public let HASH_TYPE=SHA512 + + /* Convert Integer to n-byte array */ + private static func inttoBytes(_ n: Int,_ len:Int) -> [UInt8] + { + var b=[UInt8](repeating: 0,count: len) + var nn=n + + var i=len; + while (nn>0 && i>0) + { + i -= 1; + b[i]=UInt8(nn&0xff); + nn /= 256; + } + return b; + } + + private static func hashit(_ sha: Int,_ A:[UInt8],_ n: Int32,_ B:[UInt8]?,_ pad:Int) -> [UInt8] + { + var R=[UInt8]() + if sha==SHA256 + { + let H=HASH256() + H.process_array(A); if n>0 {H.process_num(n)} + if B != nil {H.process_array(B!)} + R=H.hash() + } + if sha==SHA384 + { + let H=HASH384() + H.process_array(A); if n>0 {H.process_num(n)} + if B != nil {H.process_array(B!)} + R=H.hash() + } + if sha==SHA512 + { + let H=HASH512() + H.process_array(A); if n>0 {H.process_num(n)} + if B != nil {H.process_array(B!)} + R=H.hash() + } + if R.isEmpty || pad==0 {return R} + var W=[UInt8](repeating: 0,count: pad) + if pad<=sha + { + for i in 0 ..< pad {W[i]=R[i]} + } + else + { + for i in 0 ..< sha {W[i]=R[i]} + } + return W + } + + /* Key Derivation Functions */ + /* Input octet Z */ + /* Output key of length olen */ + static public func KDF1(_ sha: Int,_ Z: [UInt8],_ olen:Int) -> [UInt8] + { + /* NOTE: the parameter olen is the length of the output K in bytes */ + let hlen=sha + var K=[UInt8](repeating: 0,count: olen) + var k=0; + + var cthreshold=olen/hlen; if (olen%hlen) != 0 {cthreshold += 1} + + for counter in 0 ..< cthreshold + { + let B=hashit(sha,Z,Int32(counter),nil,0) + if k+hlen>olen {for i in 0 ..< olen%hlen {K[k]=B[i]; k+=1}} + else {for i in 0 ..< hlen {K[k]=B[i]; k+=1}} + } + return K; + } + + static public func KDF2(_ sha:Int,_ Z:[UInt8],_ P:[UInt8]?,_ olen:Int) -> [UInt8] + { + /* NOTE: the parameter olen is the length of the output k in bytes */ + let hlen=sha + var K=[UInt8](repeating: 0,count: olen) + var k=0; + + var cthreshold=olen/hlen; if (olen%hlen) != 0 {cthreshold += 1} + + for counter in 1...cthreshold + { + let B=hashit(sha,Z,Int32(counter),P,0) + if k+hlen>olen {for i in 0 ..< olen%hlen {K[k]=B[i]; k+=1}} + else {for i in 0 ..< hlen {K[k]=B[i]; k+=1}} + } + return K; + } + + /* Password based Key Derivation Function */ + /* Input password p, salt s, and repeat count */ + /* Output key of length olen */ + static public func PBKDF2(_ sha:Int,_ Pass:[UInt8],_ Salt:[UInt8],_ rep:Int,_ olen:Int) -> [UInt8] + { + var d=olen/sha; + if (olen%sha) != 0 {d+=1} + var F=[UInt8](repeating: 0,count: sha) + var U=[UInt8](repeating: 0,count: sha) + var S=[UInt8](repeating: 0,count: Salt.count+4) + + var K=[UInt8](repeating: 0,count: d*sha) + + var opt=0; + + for i in 1...d + { + for j in 0 ..< Salt.count {S[j]=Salt[j]} + var N=ECDH.inttoBytes(i,4); + for j in 0 ..< 4 {S[Salt.count+j]=N[j]} + + printBinary(Pass); + + ECDH.HMAC(sha,S,Pass,&F); + + for j in 0 ..< sha {U[j]=F[j]} + for _ in 2...rep + { + ECDH.HMAC(sha,U,Pass,&U); + for k in 0 ..< sha {F[k]^=U[k]} + } + for j in 0 ..< sha {K[opt]=F[j]; opt+=1} + } + var key=[UInt8](repeating: 0,count: olen) + for i in 0 ..< olen {key[i]=K[i]} + return key; + } + + /* Calculate HMAC of m using key k. HMAC is tag of length olen */ + static public func HMAC(_ sha:Int,_ M:[UInt8],_ K:[UInt8],_ tag:inout [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 b=64 + if sha>32 {b=128} + + var K0=[UInt8](repeating: 0,count: b) + let olen=tag.count; + var B=[UInt8](); + + if olen<4 /*|| olen>HASH.len*/ {return 0} + + if (K.count > b) + { + //H.process_array(K); var B=H.hash(); + B=hashit(sha,K,0,nil,0) + for i in 0 ..< sha {K0[i]=B[i]} + } + else + { + for i in 0 ..< K.count {K0[i]=K[i]} + } + for i in 0 ..< b {K0[i]^=0x36} + + // printBinary(K0) + + B=hashit(sha,K0,0,M,0) + + // printBinary(B); + + for i in 0 ..< b {K0[i]^=0x6a} + B=hashit(sha,K0,0,B,olen) + + for i in 0 ..< olen {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](repeating: 0,count: 16) + let clen=16+(M.count/16)*16; + + var C=[UInt8](repeating: 0,count: clen) + + a.init_it(AES.CBC,K,nil) + + var ipt=0; var opt=0; + var fin=false; + var i:Int=0 + while true + { + i=0 + while i<16 + { + if (ipt<M.count) {buff[i]=M[ipt]; ipt+=1} + else {fin=true; break;} + i+=1 + } + if fin {break} + a.encrypt(&buff); + for j in 0 ..< 16 + {C[opt]=buff[j]; opt+=1} + } + + /* last block, filled up to i-th index */ + + let padlen=16-i; + for j in i ..< 16 {buff[j]=UInt8(padlen&0xff)} + + a.encrypt(&buff); + + for j in 0 ..< 16 + {C[opt]=buff[j]; opt+=1} + 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](repeating: 0,count: 16) + var MM=[UInt8](repeating: 0,count: C.count) + + var ipt=0; var opt=0; + + a.init_it(AES.CBC,K,nil); + + if C.count==0 {return [UInt8]()} + var ch=C[ipt]; ipt+=1 + + var fin=false; + var i:Int=0 + while true + { + i=0 + while i<16 + { + buff[i]=ch; + if ipt>=C.count {fin=true; break;} + else {ch=C[ipt]; ipt+=1} + i+=1 + } + a.decrypt(&buff); + if fin {break} + for j in 0 ..< 16 + {MM[opt]=buff[j]; opt+=1} + } + + 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 j in 16-padlen ..< 16 {if buff[j] != buff[15] {bad=true}} + } + if !bad + { + for j in 0 ..< 16-padlen + {MM[opt]=buff[j]; opt+=1} + } + + if bad {return [UInt8]()} + + var M=[UInt8](repeating: 0,count: opt) + for j in 0 ..< opt {M[j]=MM[j]} + + 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?,_ S:inout [UInt8],_ W:inout [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) + s.mod(r) + } + else + { + s=BIG.randomnum(r,RNG!) + + // s.toBytes(&T) + // for i in 0 ..< EGS {S[i]=T[i]} + } + + if (ROM.AES_S>0) + { + s.mod2m(2*ROM.AES_S) + } + s.toBytes(&S) + + 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],_ Z:inout [UInt8]) -> Int + { + var res=0 + var T=[UInt8](repeating: 0,count: ECDH.EFS) + + 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 i in 0 ..< ECDH.EFS {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(_ sha:Int,_ RNG:RAND,_ S:[UInt8],_ F:[UInt8],_ C:inout [UInt8],_ D:inout [UInt8]) -> Int + { + var T=[UInt8](repeating: 0,count: ECDH.EFS) + let B=hashit(sha,F,0,nil,Int(ROM.MODBYTES)) + + 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); + let w=BIG.randomnum(r,RNG); + if ROM.AES_S>0 + { + u.mod2m(2*ROM.AES_S) + } + V.copy(G) + V=V.mul(u) + let vx=V.getX() + c.copy(vx) + c.mod(r) + if c.iszilch() {continue} + u.copy(BIG.modmul(u,w,r)) + u.invmodp(r) + d.copy(BIG.modmul(s,c,r)) + d.add(f) + d.copy(BIG.modmul(d,w,r)) + d.copy(BIG.modmul(u,d,r)) + } while d.iszilch() + + c.toBytes(&T) + for i in 0 ..< ECDH.EFS {C[i]=T[i]} + d.toBytes(&T) + for i in 0 ..< ECDH.EFS {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(_ sha:Int,_ W:[UInt8],_ F:[UInt8],_ C:[UInt8],_ D:[UInt8]) -> Int + { + var res=0 + let B=hashit(sha,F,0,nil,Int(ROM.MODBYTES)) + + 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(_ sha:Int,_ P1:[UInt8],_ P2:[UInt8],_ RNG:RAND,_ W:[UInt8],_ M:[UInt8],_ V:inout [UInt8],_ T:inout [UInt8]) -> [UInt8] + { + var Z=[UInt8](repeating: 0,count: ECDH.EFS) + var VZ=[UInt8](repeating: 0,count: 3*ECDH.EFS+1) + var K1=[UInt8](repeating: 0,count: ECDH.EAS) + var K2=[UInt8](repeating: 0,count: ECDH.EAS) + var U=[UInt8](repeating: 0,count: ECDH.EGS) + + if ECDH.KEY_PAIR_GENERATE(RNG,&U,&V) != 0 {return [UInt8]()} + if ECDH.ECPSVDP_DH(U,W,&Z) != 0 {return [UInt8]()} + + for i in 0 ..< 2*ECDH.EFS+1 {VZ[i]=V[i]} + for i in 0 ..< ECDH.EFS {VZ[2*ECDH.EFS+1+i]=Z[i]} + + + var K=KDF2(sha,VZ,P1,ECDH.EFS) + + for i in 0 ..< ECDH.EAS {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](repeating: 0,count: C.count+P2.count+8) + + for i in 0 ..< C.count {AC[i]=C[i]} + for i in 0 ..< P2.count {AC[C.count+i]=P2[i]} + for i in 0 ..< 8 {AC[C.count+P2.count+i]=L2[i]} + + ECDH.HMAC(sha,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(_ sha:Int,_ P1:[UInt8],_ P2:[UInt8],_ V:[UInt8],_ C:[UInt8],_ T:[UInt8],_ U:[UInt8]) -> [UInt8] + { + var Z=[UInt8](repeating: 0,count: ECDH.EFS) + var VZ=[UInt8](repeating: 0,count: 3*ECDH.EFS+1) + var K1=[UInt8](repeating: 0,count: ECDH.EAS) + var K2=[UInt8](repeating: 0,count: ECDH.EAS) + + var TAG=[UInt8](repeating: 0,count: T.count) + + if ECPSVDP_DH(U,V,&Z) != 0 {return [UInt8]()} + + for i in 0 ..< 2*ECDH.EFS+1 {VZ[i]=V[i]} + for i in 0 ..< ECDH.EFS {VZ[2*EFS+1+i]=Z[i]} + + var K=KDF2(sha,VZ,P1,ECDH.EFS) + + for i in 0 ..< ECDH.EAS {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](repeating: 0,count: C.count+P2.count+8) + + for i in 0 ..< C.count {AC[i]=C[i]} + for i in 0 ..< P2.count {AC[C.count+i]=P2[i]} + for i in 0 ..< 8 {AC[C.count+P2.count+i]=L2[i]} + + ECDH.HMAC(sha,AC,K2,&TAG) + + var same=true + for i in 0 ..< T.count + { + if T[i] != TAG[i] {same=false} + } + if !same {return [UInt8]()} + + return M; + + } + + static public func printBinary(_ array: [UInt8]) + { + for i in 0 ..< array.count + { + let h=String(array[i],radix:16); + print("\(h)", terminator: "") + } + print(""); + } + +}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/swift/ecp.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ecp.swift b/version22/swift/ecp.swift new file mode 100644 index 0000000..d4e5c37 --- /dev/null +++ b/version22/swift/ecp.swift @@ -0,0 +1,923 @@ +/* + 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:Int) + { + 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:Int) + { + 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) -> Int + { + var x=b^c + x-=1 // if x=0, x now -1 + return Int((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,Int(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:Int) + { + 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() -> Int + { + 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(_ b:inout [UInt8]) + { + let RM=Int(ROM.MODBYTES) + var t=[UInt8](repeating: 0,count: RM) + if ROM.CURVETYPE != ROM.MONTGOMERY {b[0]=0x04} + else {b[0]=0x02} + + affine() + x.redc().toBytes(&t) + for i in 0 ..< RM {b[i+1]=t[i]} + if ROM.CURVETYPE != ROM.MONTGOMERY + { + y.redc().toBytes(&t); + for i in 0 ..< RM {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](repeating: 0,count: RM) + let p=BIG(ROM.Modulus); + + for i in 0 ..< RM {t[i]=b[i+1]} + let px=BIG.fromBytes(t) + if BIG.comp(px,p)>=0 {return ECP()} + + if (b[0]==0x04) + { + for i in 0 ..< RM {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) + + if ROM.CURVE_A==1 + { + E.copy(D); E.sub(C) + } + C.add(D) + + 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 _ in 0 ..< m + {work.append(FP(0))} + + work[0].one() + work[1].copy(P[0].z) + + for i in 2 ..< m + { + 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); + var i=m-2; + while (true) + { + 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); + i=i-1; + } + /* now work[] contains inverses of all Z coordinates */ + + for i in 0 ..< m + { + 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(Int(e)))} + else + { + let P=ECP() + let R0=ECP() + let R1=ECP(); R1.copy(self) + + for i in (0...bts-1).reversed() + { + let b=Int(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 i in (0...nb-2).reversed() + { + let b=e.bit(UInt(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](repeating: 0,count: n) + + affine(); + + // precompute table + Q.copy(self) + Q.dbl() + W.append(ECP()) + + W[0].copy(self) + + for i in 1 ..< 8 + { + 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 i in 0 ..< nb + { + w[i]=Int8(t.lastbits(5)-16); + t.dec(Int(w[i])); + t.norm(); + t.fshr(4); + } + w[nb]=Int8(t.lastbits(5)) + + P.copy(W[Int((w[nb])-1)/2]); + for i in (0...nb-1).reversed() + { + 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](repeating: 0,count: n); + + affine(); + Q.affine(); + + te.copy(e); + tf.copy(f); + + // precompute table + for _ in 0 ..< 8 {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 i in 0 ..< nb + { + 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[Int(w[nb]-1)/2]); + for i in (0...nb-1).reversed() + { + 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/c25f9e5c/version22/swift/ecp2.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ecp2.swift b/version22/swift/ecp2.swift new file mode 100644 index 0000000..e1288d6 --- /dev/null +++ b/version22/swift/ecp2.swift @@ -0,0 +1,618 @@ +/* + 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. +// + +/* AMCL 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:Int) + { + 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) -> Int + { + var x=b^c + x-=1 // if x=0, x now -1 + return Int((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,Int(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(_ b:inout [UInt8]) + { + let RM=Int(ROM.MODBYTES) + var t=[UInt8](repeating: 0,count: RM) + + affine(); + x.getA().toBytes(&t) + for i in 0 ..< RM + {b[i]=t[i]} + x.getB().toBytes(&t); + for i in 0 ..< RM + {b[i+RM]=t[i]} + + y.getA().toBytes(&t); + for i in 0 ..< RM + {b[i+2*RM]=t[i]} + y.getB().toBytes(&t); + for i in 0 ..< RM + {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](repeating: 0,count: RM) + + + for i in 0 ..< RM {t[i]=b[i]} + var ra=BIG.fromBytes(t); + for i in 0 ..< RM {t[i]=b[i+RM]} + var rb=BIG.fromBytes(t); + let rx=FP2(ra,rb) + + for i in 0 ..< RM {t[i]=b[i+2*RM]} + ra=BIG.fromBytes(t) + for i in 0 ..< RM {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 _ in 0 ..< m + {work.append(FP2(0))} + + work[0].one() + work[1].copy(P[0].z) + + for i in 2 ..< m + { + 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) + + var i=m-2 + while true + { + 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) + i-=1 + } + /* now work[] contains inverses of all Z coordinates */ + + for i in 0 ..< m + { + 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 _ in 0 ..< 8 {W.append(ECP2())} + + var w=[Int8](repeating: 0,count: 1+(ROM.NLEN*Int(ROM.BASEBITS)+3)/4) + + if is_infinity() {return ECP2()} + + affine() + + /* precompute table */ + Q.copy(self) + Q.dbl() + W[0].copy(self) + + for i in 1 ..< 8 + { + 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 i in 0 ..< nb + { + w[i]=Int8(t.lastbits(5)-16) + t.dec(Int(w[i])); t.norm() + t.fshr(4) + } + w[nb]=Int8(t.lastbits(5)) + + P.copy(W[Int(w[nb]-1)/2]) + for i in (0...nb-1).reversed() + //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](repeating: 0,count: 4) + let T=ECP2() + let C=ECP2() + let P=ECP2() + + var W=[ECP2](); + for _ in 0 ..< 8 {W.append(ECP2())} + + let mt=BIG() + var t=[BIG]() + + var w=[Int8](repeating: 0,count: ROM.NLEN*Int(ROM.BASEBITS)+1) + + for i in 0 ..< 4 + { + 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 i in 0 ..< 4 + { + 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 j in 0 ..< nb + { + for i in 0 ..< 4 { + a[i]=Int32(t[i].lastbits(2)-2) + + t[i].dec(Int(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[Int(w[nb]-1)/2]) + for i in (0...nb-1).reversed() + //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/c25f9e5c/version22/swift/ff.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ff.swift b/version22/swift/ff.swift new file mode 100644 index 0000000..ab87c91 --- /dev/null +++ b/version22/swift/ff.swift @@ -0,0 +1,927 @@ +/* + 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 */ +/* AMCL mod p functions */ + +final class FF { + var v = [BIG]() + var length:Int=1 + + /* func P_EXCESS() -> Int32 + { + return ((v[length-1].w[ROM.NLEN-1]&FF.P_OMASK)>>FF.P_TBITS) + } */ + /* Constructors */ + init(_ n: Int) + { + for _ in 0 ..< n + { + v.append(BIG(0)); + } + length=n; + } + + init(_ x: [[Chunk]],n: Int) + { + for i in 0 ..< n + { + v.append(BIG(x[i])) + } + length=n; + } + + func getlen() -> Int + { + return length; + } + + /* set to zero */ + func zero() + { + for i in 0 ..< length + { + v[i].zero(); + } + } + + /* set to integer */ + func set(_ m: Int) + { + zero(); + v[0].set(0,Chunk(m)); + } + + /* copy from FF b */ + func copy(_ b: FF) + { + for i in 0 ..< length + { + v[i].copy(b.v[i]); + } + } + + /* x=y<<n */ + func dsucopy(_ b: FF) + { + for i in 0 ..< b.length + { + v[b.length+i].copy(b.v[i]); + v[i].zero(); + } + } + /* x=y */ + func dscopy(_ b: FF) + { + for i in 0 ..< b.length + { + v[i].copy(b.v[i]); + v[b.length+i].zero(); + } + } + /* x=y>>n */ + func sducopy(_ b: FF) + { + for i in 0 ..< length + { + v[i].copy(b.v[length+i]); + } + } + func one() + { + v[0].one(); + for i in 1 ..< length + { + v[i].zero(); + } + } + /* test equals 0 */ + func iszilch() -> Bool + { + for i in 0 ..< length + { + if (!v[i].iszilch()) {return false} + } + return true; + } + /* shift right by BIGBITS-bit words */ + func shrw(_ n: Int) + { + for i in 0 ..< n + { + v[i].copy(v[i+n]); + v[i+n].zero(); + } + } + + /* shift left by BIGBITS-bit words */ + func shlw(_ n: Int) + { + for i in 0 ..< n + { + v[n+i].copy(v[i]); + v[i].zero(); + } + } + + /* extract last bit */ + func parity() -> Int + { + return v[0].parity() + } + + func lastbits(_ m: Int) ->Int + { + return v[0].lastbits(UInt(m)); + } + + /* compare x and y - must be normalised, and of same length */ + static func comp(_ a: FF,_ b:FF) -> Int + { + for i in (0...a.length-1).reversed() + // 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 i in 0 ..< n + { + 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 i in 0 ..< n + { + 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 i in 0 ..< n + { + 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 i in 0 ..< n + { + v[vp+i].sub(y.v[yp+i]) + } + } + /* simple add */ + func add(_ b: FF) + { + for i in 0 ..< length + {v[i].add(b.v[i])} + } + + /* simple sub */ + func sub(_ b: FF) + { + for i in 0 ..< length + {v[i].sub(b.v[i])} + } + /* reverse sub */ + func revsub(_ b: FF) + { + for i in 0 ..< length + {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 i in 0 ..< nn-1 + { + let carry=v[vp+i].norm(); + v[vp+i].xortop(carry<<Chunk(ROM.P_TBITS)) + v[vp+i+1].w[0]+=carry; //inc(carry) + } + let carry=v[vp+nn-1].norm(); + if (trunc) + {v[vp+nn-1].xortop(carry<<Chunk(ROM.P_TBITS))} + } + + func norm() + { + rnorm(0,length) + } + + /* increment/decrement by a small integer */ + func inc(_ m: Int) + { + v[0].inc(m); + norm(); + } + + func dec(_ m: Int) + { + v[0].dec(m); + norm(); + } + + /* shift left by one bit */ + func shl() + { + var delay_carry=0; + for i in 0 ..< length-1 + { + let carry=v[i].fshl(1) + v[i].inc(delay_carry); + v[i].xortop(Chunk(carry)<<Chunk(ROM.P_TBITS)); + delay_carry=carry; + } + v[length-1].fshl(1) + v[length-1].inc(delay_carry) + } + + /* shift right by one bit */ + func shr() + { + for i in (1...length-1).reversed() + { + let carry=v[i].fshr(1); + v[i-1].ortop(Chunk(carry)<<Chunk(ROM.P_TBITS)); + } + v[0].fshr(1); + } + + /* Convert to Hex String */ + func toString() -> String + { + norm(); + var s=""; + for i in (0...length-1).reversed() + { + s+=v[i].toString(); + } + return s; + } + + /* Convert FFs to/from byte arrays */ + func toBytes(_ b: inout [UInt8]) + { + for i in 0 ..< length + { + v[i].tobytearray(&b,(length-i-1)*Int(ROM.MODBYTES)) + } + } + static func fromBytes(_ x: FF,_ b:[UInt8]) + { + for i in 0 ..< x.length + { + 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:Int) + { + for i in 0 ..< a.length + { + 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); + rnorm(n,nd2); + rnorm(n+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+=1 + } while (FF.comp(self,c)>=0) + + while (k>0) + { + c.shr(); + if (FF.comp(self,c)>=0) + { + sub(c) + norm() + } + k-=1 + } + } + + /* 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=Int(ROM.BIGBITS)*n + + while (FF.comp(x,m)>=0) + { + x.sub(m); + x.norm(); + } + + while (k>0) + { + m.shr() + + if (FF.comp(x,m)>=0) + { + x.sub(m); + x.norm(); + } + k -= 1; + } + + 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 i in m ..< length + {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(); + + var i=1 + //for var i=1;i<n;i<<=1 + while (i<n) + { + 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); + i<<=1 + } + U.norm(); + return U; + } + + func random(_ rng: RAND) + { + let n=length; + for i in 0 ..< n + { + 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 i in 0 ..< 2*n + { + d.v[i].copy(BIG.random(rng)); + } + copy(d.dmod(p)); + } + /* this*=y mod p */ + func modmul(_ y: FF,_ p:FF,_ nd: FF) + { + if BIG.ff_pexceed(v[length-1],y.v[y.length-1]) {mod(p)} + // let ex=P_EXCESS(); + //let ey=y.P_EXCESS(); + // if ((ex+1)>=(FF.P_FEXCESS-1)/(ey+1)) {mod(p)} + let d=FF.mul(self,y); + copy(d.reduce(p,nd)); + } + + /* this*=y mod p */ + func modsqr(_ p: FF,_ nd:FF) + { + if BIG.ff_sexceed(v[length-1]) {mod(p)} + // let ex=P_EXCESS(); + // if ((ex+1)>=(FF.P_FEXCESS-1)/(ex+1)) {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 i in (0...8*Int(ROM.MODBYTES)*n-1).reversed() + { + let b=Int(e.v[i/Int(ROM.BIGBITS)].bit(UInt(i%Int(ROM.BIGBITS)))) + 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 i in (0...8*Int(ROM.MODBYTES)-1).reversed() + { + let b=(e.bit(UInt(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:Int,_ 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 i in (0...8*Int(ROM.MODBYTES)*n-1).reversed() + // for var i=8*Int(ROM.MODBYTES)*n-1;i>=0;i-- + { + modsqr(p,ND) + let b=e.v[i/Int(ROM.BIGBITS)].bit(UInt(i%Int(ROM.BIGBITS))) + 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 i in (0...8*Int(ROM.MODBYTES)-1).reversed() + // for var i=8*Int(ROM.MODBYTES)-1;i>=0;i-- + { + let eb=e.bit(UInt(i)) + let fb=f.bit(UInt(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:Int,_ y:Int) -> Int + { /* 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: Int) -> 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,Int(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:Int=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 += 1; + } + + if (s==0) {return false} + for _ in 0 ..< 10 + { + x.randomnum(p,rng) + x.pow(d,p) + if (FF.comp(x,unity)==0 || FF.comp(x,nm1)==0) {continue} + loop=false + for _ in 1 ..< s + { + 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/c25f9e5c/version22/swift/fp.swift ---------------------------------------------------------------------- diff --git a/version22/swift/fp.swift b/version22/swift/fp.swift new file mode 100644 index 0000000..b4c0ba0 --- /dev/null +++ b/version22/swift/fp.swift @@ -0,0 +1,309 @@ +/* + 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 +// AMCL 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 && ROM.MODTYPE != ROM.GENERALISED_MERSENNE + { + let d=DBIG(x) + d.shl(UInt(ROM.NLEN)*ROM.BASEBITS) + x.copy(d.mod(FP.p)) + } + } +/* convert back to regular form */ + func redc() -> BIG + { + if ROM.MODTYPE != ROM.PSEUDO_MERSENNE && ROM.MODTYPE != ROM.GENERALISED_MERSENNE + { + let d=DBIG(x) + return BIG.mod(d) + } + else + { + let r=BIG(x) + return r; + } + } + + init() + { + x=BIG(0) + } + init(_ a: Int) + { + 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: Int) + { + x.cswap(b.x,d) + } + +/* copy FPs depending on d */ + func cmove(_ b: FP,_ d:Int) + { + x.cmove(b.x,d); + } +/* this*=b mod Modulus */ + func mul(_ b: FP) + { + norm() + b.norm() + let ea=BIG.EXCESS(x) + let eb=BIG.EXCESS(b.x) + + if Int64(ea+1)*Int64(eb+1)>Int64(ROM.FEXCESS) {reduce()} + /*if (ea+1)>=(ROM.FEXCESS-1)/(eb+1) {reduce()}*/ + + let d=BIG.mul(x,b.x) + x.copy(BIG.mod(d)) + } + static func logb2(_ w: UInt32) -> Int + { + var v = w + v |= (v >> 1) + v |= (v >> 2) + v |= (v >> 4) + v |= (v >> 8) + v |= (v >> 16) + + v = v - ((v >> 1) & 0x55555555) + v = (v & 0x33333333) + ((v >> 2) & 0x33333333) + let r = Int(( ((v + (v >> 4)) & 0xF0F0F0F) &* 0x1010101) >> 24) + return (r+1) + } + /* this = -this mod Modulus */ + func neg() + { + let m=BIG(FP.p); + + norm(); + let sb=FP.logb2(UInt32(BIG.EXCESS(x))) + // var ov=BIG.EXCESS(x); + // var sb=1; while(ov != 0) {sb += 1;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: Int) + { + 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() + { + norm() + let ea=BIG.EXCESS(x); + + if Int64(ea+1)*Int64(ea+1)>Int64(ROM.FEXCESS) {reduce()} + /*if (ea+1)>=(ROM.FEXCESS-1)/(ea+1) {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) + } + +}
