http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/swift/ecdh.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ecdh.swift b/version22/swift/ecdh.swift deleted file mode 100644 index fd1d863..0000000 --- a/version22/swift/ecdh.swift +++ /dev/null @@ -1,587 +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 -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/1add7560/version22/swift/ecp.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ecp.swift b/version22/swift/ecp.swift deleted file mode 100644 index d4e5c37..0000000 --- a/version22/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: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/1add7560/version22/swift/ecp2.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ecp2.swift b/version22/swift/ecp2.swift deleted file mode 100644 index e1288d6..0000000 --- a/version22/swift/ecp2.swift +++ /dev/null @@ -1,618 +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. -// - -/* 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/1add7560/version22/swift/ff.swift ---------------------------------------------------------------------- diff --git a/version22/swift/ff.swift b/version22/swift/ff.swift deleted file mode 100644 index ab87c91..0000000 --- a/version22/swift/ff.swift +++ /dev/null @@ -1,927 +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 */ -/* 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/1add7560/version22/swift/fp.swift ---------------------------------------------------------------------- diff --git a/version22/swift/fp.swift b/version22/swift/fp.swift deleted file mode 100644 index b4c0ba0..0000000 --- a/version22/swift/fp.swift +++ /dev/null @@ -1,309 +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 -// 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) - } - -}
