hecc (empty) → 0.1
raw patch · 7 files changed
+344/−0 lines, 7 filesdep +basesetup-changed
Dependencies added: base
Files
- COPYING +22/−0
- README +26/−0
- Setup.hs +2/−0
- hecc.cabal +20/−0
- src/Codec/Encryption/ECC/Base.hs +220/−0
- src/Examples.hs +10/−0
- src/test.hs +44/−0
+ COPYING view
@@ -0,0 +1,22 @@+Copyright (c) 2009 Marcel Fourné++Permission is hereby granted, free of charge, to any person+obtaining a copy of this software and associated documentation+files (the "Software"), to deal in the Software without+restriction, including without limitation the rights to use,+copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the+Software is furnished to do so, subject to the following+conditions:++The above copyright notice and this permission notice shall be+included in all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES+OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT+HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,+WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR+OTHER DEALINGS IN THE SOFTWARE.
+ README view
@@ -0,0 +1,26 @@+ECC+---++RSA just doesn't cut it anymore for fast public-key crypto. Keys are large for reasonable security making it quite slow...+Enter elliptic curves: smaller numbers are necessary and everything is faster. Maybe this library is not for embedded system usage, but now people can experiment with ECC for those use-cases where otherwise some form of RSA would be chosen.+++Hecc.Base+-----------++This is the Haskell-Elliptic-Curve-Cryptography-library, or maybe more appropriately atm it is only the basic math for many ECC-algorithms the user of this library may wish to implement.+As an example the EC-variant of the Diffie-Hellman key-exchange is included which shows how the values can be computed with this library.+Also included is a basic speed-test (a point multiplication) for the NIST Curve P-256 (the author wants some usage results and performance-numbers... so...).+++The API+-------+...is _not_ stable right now! This is only some ECC-playground. If anybody wants to use the library in its current state for serious cryptographic uses, then by all means contact the author!++The Code began as a prototyped script and has since been polished, but this is best-effort work in progress!+++Plan+----++Some algorithms using these primitives will likely follow (also: better versions of the primitives).
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ hecc.cabal view
@@ -0,0 +1,20 @@+Name: hecc+Version: 0.1+Synopsis: Elliptic Curve Cryptography for Haskell+Description: Pure math & algorithms for Elliptic Curve Cryptography in Haskell+License: OtherLicense+License-file: COPYING+Copyright: (c) Marcel Fourné, 2009+Author: Marcel Fourné+Maintainer: Marcel Fourné (hecc@bitrot.dyndns.org)+Category: Cryptography+Stability: alpha+Build-Type: Simple+Cabal-Version: >=1.2+Data-Files: README+Extra-Source-Files: src/test.hs+ src/Examples.hs+hs-source-dirs: src+Build-Depends: base >= 3 && < 5+Exposed-modules: Codec.Encryption.ECC.Base+ghc-options: -Wall
+ src/Codec/Encryption/ECC/Base.hs view
@@ -0,0 +1,220 @@+{-# LANGUAGE PatternGuards #-}+-----------------------------------------------------------------------------+-- |+-- Module : Hecc.Base+-- Copyright : (c) Marcel Fourné 2009+-- License : MIT-X11-License+-- Maintainer : Marcel Fourné (hecc@bitrot.dyndns.org+--+-- ECC Base algorithms & point formats+--+-----------------------------------------------------------------------------++module Codec.Encryption.ECC.Base (ECInt(), + ECP(..),+ EC(..),+ modinv, + pmul, + ison,+ EPa(..), + EPp(..), + EPj(..), + EPmj(..))+ where ++-- |this may change in the future if the need arises+type ECInt = Integer++-- |extended euclidean algorithm, recursive variant+eeukl :: ECInt -> ECInt -> (ECInt, ECInt, ECInt)+eeukl a 0 = (a,1,0)+eeukl a b = let (d,s,t) = eeukl b (a `mod` b)+ in (d,t,s-(div a b)*t)++-- |computing the modular inverse+modinv :: ECInt -> ECInt -> ECInt+modinv a m = let (x,y,_) = eeukl a m+ in if x == 1 + then mod y m+ else undefined++-- |class of all Elliptic Curves+data EC = EC (ECInt, ECInt, ECInt)+ deriving (Eq)+instance Show EC where show (EC (a,b,p)) = "y^2=x^3+" ++ show a ++ "*x+" ++ show b ++ " mod " ++ show p++-- |class of all Elliptic Curve Points+class ECP a where+ -- |function returning the appropriate INF in the specific ECP-Format, for generic higher-level-algorithms+ inf :: a+ -- |generic getters+ getx :: a -> EC -> ECInt+ -- |generic getters+ gety :: a -> EC -> ECInt+ -- |add an elliptic point onto itself, base for padd a a c+ pdouble :: a -> EC -> a+ -- |add 2 elliptic points+ padd :: a -> a -> EC -> a++-- |Elliptic Point Affine coordinates+data EPa = EPa (ECInt, ECInt) + | Infa+ deriving (Eq)+instance Show EPa where show (EPa (a,b)) = show (a,b)+ show Infa = "Null"+instance ECP EPa where + inf = Infa+ getx (EPa (x,_)) _ = x+ getx Infa _ = undefined+ gety (EPa (_,y)) _ = y+ gety Infa _ = undefined+ pdouble (EPa (x1,y1)) (EC (alpha,_,p)) = + let lambda = ((3*x1^(2::Int)+alpha)*(modinv (2*y1) p)) `mod` p+ x3 = (lambda^(2::Int) - 2*x1) `mod` p+ y3 = (lambda*(x1-x3)-y1) `mod` p+ in EPa (x3,y3)+ pdouble Infa _ = Infa+ padd Infa a _ = a+ padd a Infa _ = a+ padd a@(EPa (x1,y1)) b@(EPa (x2,y2)) c@(EC (_,_,p)) + | x1==x2,y1==(-y2) = Infa+ | a==b = pdouble a c+ | otherwise = + let lambda = ((y2-y1)*(modinv (x2-x1) p)) `mod` p+ x3 = (lambda^(2::Int) - x1 - x2) `mod` p+ y3 = (lambda*(x1-x3)-y1) `mod` p+ in EPa (x3,y3)++-- |Elliptic Point Projective coordinates+data EPp = EPp (ECInt, ECInt, ECInt) + | Infp+ deriving (Eq)+instance Show EPp where show (EPp (a,b,c)) = show (a,b,c)+ show Infp = "Null"+instance ECP EPp where+ inf = Infp+ getx (EPp (x,_,z)) (EC (_,_,p))= (x * (modinv z p)) `mod` p+ getx Infp _ = undefined+ gety (EPp (_,y,z)) (EC (_,_,p))= (y * (modinv z p)) `mod` p+ gety Infp _ = undefined+ pdouble (EPp (x1,y1,z1)) (EC (alpha,_,p)) = + let a = (alpha*z1^(2::Int)+3*x1^(2::Int)) `mod` p+ b = (y1*z1) `mod` p+ c = (x1*y1*b) `mod` p+ d = (a^(2::Int)-8*c) `mod` p+ x3 = (2*b*d) `mod` p+ y3 = (a*(4*c-d)-8*y1^(2::Int)*b^(2::Int)) `mod` p+ z3 = (8*b^(3::Int)) `mod` p+ in EPp (x3,y3,z3)+ pdouble Infp _ = Infp+ padd Infp a _ = a+ padd a Infp _ = a+ padd p1@(EPp (x1,y1,z1)) p2@(EPp (x2,y2,z2)) curve@(EC (_,_,p)) + | x1==x2,y1==(-y2) = Infp+ | p1==p2 = pdouble p1 curve+ | otherwise = + let a = (y2*z1 - y1*z2) `mod` p+ b = (x2*z1 - x1*z2) `mod` p+ c = (a^(2::Int)*z1*z2 - b^(3::Int) - 2*b^(2::Int)*x1*z2) `mod` p+ x3 = (b*c) `mod` p+ y3 = (a*(b^(2::Int)*x1*z2-c)-b^(3::Int)*y1*z2) `mod` p+ z3 = (b^(3::Int)*z1*z2) `mod` p+ in EPp (x3,y3,z3)+ +-- |Elliptic Point Jacobian coordinates+data EPj = EPj (ECInt, ECInt, ECInt) + | Infj+ deriving (Eq)+instance Show EPj where show (EPj (a,b,c)) = show (a,b,c)+ show Infj = "Null"+instance ECP EPj where+ inf = Infj+ getx (EPj (x,_,z)) (EC (_,_,p)) = (x * (modinv (z^(2::Int)) p)) `mod` p+ getx Infj _ = undefined+ gety (EPj (_,y,z)) (EC (_,_,p)) = (y * (modinv (z^(3::Int)) p)) `mod` p+ gety Infj _ = undefined+ pdouble (EPj (x1,y1,z1)) (EC (alpha,_,p)) = + let a = 4*x1*y1^(2::Int) `mod` p+ b = (3*x1^(2::Int) + alpha*z1^(4::Int)) `mod` p+ x3 = (-2*a + b^(2::Int)) `mod` p+ y3 = (-8*y1^(4::Int) + b*(a-x3)) `mod` p+ z3 = 2*y1*z1 `mod` p+ in EPj (x3,y3,z3)+ pdouble Infj _ = Infj+ padd Infj a _ = a+ padd a Infj _ = a + padd p1@(EPj (x1,y1,z1)) p2@(EPj (x2,y2,z2)) curve@(EC (_,_,p)) + | x1==x2,y1==(-y2) = Infj+ | p1==p2 = pdouble p1 curve+ | otherwise = + let a = (x1*z2^(2::Int)) `mod` p+ b = (x2*z1^(2::Int)) `mod` p+ c = (y1*z2^(3::Int)) `mod` p+ d = (y2*z1^(3::Int)) `mod` p+ e = (b - a) `mod` p+ f = (d - c) `mod` p+ x3 = (-e^(3::Int) - 2*a*e^(2::Int) + f^(2::Int)) `mod` p+ y3 = (-c*e^(3::Int) + f*(a*e^(2::Int) - x3)) `mod` p+ z3 = (z1*z2*e) `mod` p+ in EPj (x3,y3,z3)++-- |Elliptic Point Modified Jacobian coordinates+data EPmj = EPmj (ECInt, ECInt, ECInt, ECInt) + | Infmj+ deriving (Eq)+instance Show EPmj where show (EPmj (a,b,c,d)) = show (a,b,c,d)+ show Infmj = "Null"+instance ECP EPmj where+ inf = Infmj+ getx (EPmj (x,_,z,_)) (EC (_,_,p)) = (x * (modinv (z^(2::Int)) p)) `mod` p+ getx Infmj _ = undefined+ gety (EPmj (_,y,z,_)) (EC (_,_,p)) = (y * (modinv (z^(3::Int)) p)) `mod` p+ gety Infmj _ = undefined+ pdouble (EPmj (x1,y1,z1,z1')) (EC (_,_,p)) = + let s = 4*x1*y1^(2::Int) `mod` p+ u = 8*y1^(4::Int) `mod` p+ m = (3*x1^(2::Int) + z1') `mod` p+ t = (-2*s + m^(2::Int)) `mod` p+ x3 = t+ y3 = (m*(s - t) - u) `mod` p+ z3 = 2*y1*z1 `mod` p+ z3' = 2*u*z1' `mod` p+ in EPmj (x3,y3,z3,z3')+ pdouble Infmj _ = Infmj+ padd Infmj a _ = a+ padd a Infmj _ = a + padd p1@(EPmj (x1,y1,z1,_)) p2@(EPmj (x2,y2,z2,_)) curve@(EC (alpha,_,p)) + | x1==x2,y1==(-y2) = Infmj+ | p1==p2 = pdouble p1 curve+ | otherwise = + let u1 = (x1*z2^(2::Int)) `mod` p+ u2 = (x2*z1^(2::Int)) `mod` p+ s1 = (y1*z2^(3::Int)) `mod` p+ s2 = (y2*z1^(3::Int)) `mod` p+ h = (u2 - u1) `mod` p+ r = (s2 - s1) `mod` p+ x3 = (-h^(3::Int) - 2*u1*h^(2::Int) + r^(2::Int)) `mod` p+ y3 = (-s1*h^(3::Int) + r*(u1*h^(2::Int) - x3)) `mod` p+ z3 = (z1*z2*h) `mod` p+ z3' = (alpha*z3^(4::Int)) `mod` p+ in EPmj (x3,y3,z3,z3')++-- |this is a generic handle for Point Multiplication. The implementation will likely change.+pmul :: (ECP a) => a -> ECInt -> EC -> a+pmul = dnadd++-- |double and add for generic ECP+dnadd :: (ECP a) => a -> ECInt -> EC -> a+dnadd b k' c@(EC (_,_,p)) = + let k'' = k' `mod` (p - 1)+ ex a k s+ | k == 0 = s+ | k `mod` 2 == 0 = ex (pdouble a c) (k `div` 2) s+ | otherwise = ex (pdouble a c) (k `div` 2) (padd a s c)+ in ex b k'' inf++-- |generic verify, if generic ECP is on EC via getx and gety+ison :: (ECP a) => a -> EC -> Bool+ison pt curve@(EC (alpha,beta,p)) = let x = getx pt curve+ y = gety pt curve+ in (y^(2::Int)) `mod` p == (x^(3::Int)+alpha*x+beta) `mod` p
+ src/Examples.hs view
@@ -0,0 +1,10 @@+module Examples (ecdh)+ where++import Codec.Encryption.ECC.Base++ecdh :: (ECP a) => EC -> a -> ECInt -> t -> ECInt+ecdh c a kprivA kprivB = let kpubA = pmul a kprivA c+ kpubB = pmul a kprivA c+ ergA = pmul kpubB kprivA c+ in getx ergA c
+ src/test.hs view
@@ -0,0 +1,44 @@+import Codec.Encryption.ECC.Base+import Examples+import System.CPUTime++main = do+ {-let p = 6277101735386680763835789423207666416083908700390324961279::ECInt+ a = 6277101735386680763835789423207666416083908700390324961276::ECInt+ b = 2455155546008943817740293915197451784769108058161191238065::ECInt+ c = EC (a,b,p)+ x = 602046282375688656758213480587526111916698976636884684818::ECInt+ y = 174050332293622031404857552280219410364023488927386650641::ECInt+ alpha = EPa (x,y)+ kprivA = 5114103500503308041454439524093827019673558354999860770782::ECInt+ kprivB = 1748161650263518407976227277807126651450677841379957675747::ECInt+ print [ (x,y)|x <-[1], y <- [(ecdh c alpha kprivA kprivB)]]+ -}+ let p = 115792089210356248762697446949407573530086143415290314195533631308867097853951+ a = 115792089210356248762697446949407573530086143415290314195533631308867097853948+ b = 41058363725152142129326129780047268409114441015993725554835256314039467401291+ c = EC (a,b,p)+ xp = 48439561293906451759052585252797914202762949526041747995844080717082404635286+ yp = 36134250956749795798585127919587881956611106672985015071877198253568414405109+ xq = 91120319633256209954638481795610364441930342474826146651283703640232629993874+ yq = 80764272623998874743522585409326200078679332703816718187804498579075161456710+ k' = 78260987815077071890976764339238653408132491773166348437934213365482899760747+ --pt = pmul (EPa (xp,yp)) k' c+ --pt = pmul (EPp (xp,yp,1)) k' c+ --pt = pmul (EPmj (xp,yp,1,a)) k' c+ prec = cpuTimePrecision+ + {-let p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151+ a = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057149+ b = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984+ c = EC (a,b,p)+ xp = 2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846+ yp = 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784+ k' = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984+ prec = cpuTimePrecision+ -}+ t1 <- getCPUTime+ print $ pmul (EPp (xp,yp,1)) k' c+ t2 <- getCPUTime+ putStrLn $ "Precision: " ++ (show (div prec (1000^2))) ++ " mikrosecs"+ putStrLn $ "Time used: " ++ (show (div (t2 - t1) (1000^2))) ++ " mikrosecs"