Haskell — 你应该学的一门语言


前沿

三月的时候立下一个flag, 说是在一个月内学会haskell,现在已经8月了,终于有时间坐下来好好地看看haskell,一直以来我都执着于各种语言,现在已经掌握的语言包括: go, python, php, c, java, javascript, shell, 这些语言在不同的领域都是神兵利器,能够帮我解决不同的问题,但是haskell不一样,是一种我完全凭借兴趣去学习的语言。

刚开始看趣学指南的时候,觉得这门语言语法太奇怪了,我看得很难受。慢慢发现这其实是一种思维定势,如果我的第一门入门语言是haskell的话,想必就不是这种态度了。 Haskell是一门非常迷人的语言,它的列表推导式真的很厉害,能够解决原来传统过程式语言需要写很多代码才能解决的问题。它给了你另外一种思考问题的方式,开阔视野。

我觉得既然是计算机从业者,都应该去学学python和haskell两门语言,python将教会你什么如何让世界变美好,Haskell将告诉你这个世界是多么奇妙。如果你现在被冯·诺依曼式的架构侵染太深的话,学学Haskell吧,它会告诉你这世界上还有这样写代码的方式。

书籍

最棒的haskell免费入门书 haskell趣学指南

视频

下面是两小时入门haskell的内容,视频我也贴在下面了,但直接访问不了,你懂的。

讲义

下面是我翻译过的视频随堂讲义内容:

-- Haskell 是一种函数式编程语言
-- 在Haskell 中所有的值都是immutable 的,所以一旦一个变量被赋值之后,它就不会改变了
-- 函数可以作为另一个函数的参数
-- 递归函数在hankell中很普遍
-- Haskell没有for.while,以及典型的变量,但是它拥有常量
-- Haskell试试一种惰性求值的语言,只有在真正需要的时候再进行求值,以及错误检查


-- 最佳的Best free book
-- http://learnyouahaskell.com/chapters


-- 输入 ghci 到你的terminal中


import Data.List
import System.IO

-- This is haskell comment single line

{-

muti-line comment
-}


-- --------DATA types ---------
-- Haskell 能够自己进行类型推定
-- Haskell 是一种静态类型语言,在编译之后无法改变类型
-- 值不可变(immutable)
-- 你可以在gchi 中使用 :t 来查看数据类型

-- Int : 所有的数字范围在 -2^63 ~ 2^63
-- :: Int 表示这个类型是一个Int类型的数据

maxInt = maxBound :: Int
minInt = minBount :: Int

-- Integer 无限制的number类型

-- Float: 单精度浮点数
-- Double: 双精度浮点数
bigFloat = 3.99999999999+0.00000000005 

-- Bool: True或者False
-- Char: 一个unicode字符,用单引号括起来
-- Tuple: 能够存储多种数据类型的一组数据 (11 pts 精度)

-- 你可以用这种方式声明一个常量

always5 :: Int
always5 = 5


-- ------MATH-----
-- 一些牛逼的操作
-- 求1到100的和

sumofValues = sum[1..1000]

addEx = 5 + 4
subEx = 5 - 4
multEx = 5 * 4
divEX = 5 / 4

-- mod 是前缀操作符

modEx = mod 5 4

-- 你可以通过反引号将前缀函数变为中缀形式
modEx2 = 5 `mod` 4

-- 负数必须要用括号括起来

negNumEx = 5 + (-4)

-- 如果你定义了一个Int类型的数,你必须要用fromIntegral 函数先处理之后才能够使用sqrt函数进行处理
num9 = 9 :: Int
sqrtof9 = sqrt (fromIntegral 9)

-- built in 的一些数学函数
piVal = pi
ePow9 = exp 9
logOf9 = log 9
squared9 = 9 ** 2
truncateVal = truncate 9.999
roundVal = round 9.999
ceilingVal = ceiling 9.999
floorVal = floor 9.999

-- 当然还有一些基本数学函数: sin cos tan asin acos sinh tanh cosh asinh atanh acosh

trueAndFalse =   True && False
trueOrFalse  = True || False
notTrue = not(True)

-- 记住你可以用 :t 在ghci得到数据的类型
-- 当然也可以在函数中用:t 判断数据的类型

-- :t(+) = Num => a -> a -> a
-- Type a 是一种 num的类型, 传入两个a 类型的数据,然后得到一个a类型的数据

-- :t truncate = (RealFrac a, Integral b) => a -> b

-- ------ LIST ------

-- List是一个单向链表,只能够在前面添加数据
-- List能够存储一系列相同类型的数据

primeNumbers = [3,5,7,11]

-- 在连接两个链表的时候会如果其中一个链表很大会导致连接速度很慢
morePrime = primeNumbers ++ [13,17,19,23,29]

-- 你可以使用冒号 : 进行数据和列表连接, 一定要有一个列表,哪怕是空列表

favNums = 2 : 7 : 21 : 66 : []

-- 你可以弄一个列表的列表

multiList [[3,5,7],[11,13,17]]

-- 在列表面快速添加一个元素 
morePrime2 = 2 : morePrime2

-- 得到列表的长度

length morePrime

-- 得到index 为1 的元素
morePrime !! 1

-- 得到第一个元素
head morePrime
-- 得到最后一个元素
last morePrime

-- 得到除了第一个元素之外的所有元素
tail morePrime

-- 得到除了最后一个元素之外的所有元素

init morePrime

-- 得到指定个数的列表前几个元素
take 3 morePrime

-- 删除前几个元素
drop 2 morePrime

-- 判断一个元素是否在列表中

3 `elem` morePrime

-- or 
 elem 3 morePrime

-- 列表中的最大值

 maximum morePrime
-- 列表中的最小值
 minimin morePrime


-- 列表求和

sum morePrime

-- 列表求积

product morePrime

-- 列表自动推导
zeroToten = [0..10]

-- 步进2列表自动推导

step2list =[2,4..20]

-- 字符列表自动推导
letterlist =['A'..'Z']

-- 字符列表步进2自动推导
letterlist =['A','C'..'Z']

--无限列表,Haskell只计算你所需要的值
infinPow10 = [10,20..]

-- repeat 可以得到一个重复值的列表

many2s = take 10 (repeat 2)

-- replicate 能够指定重复次数和值
-- 3 重复10次
many3s = replicate 10 3

-- 循环列表,无限循环

cyclelis = take 10 (cycle [1,2,3,4,5])

-- haskell 较为高级的列表推导式
-- haskell 可以通过列表推导式实现高级条件数据筛选

-- 将1..10 的元素都乘以2然后返回一个列表
 listtime2 = [x * 2 | x <- [1..10]]
-- 输出 [2,4,6,8,10,12,14,16,18,20]

-- 将1..20中 3*x 小于50的剔除,输出剩下的3*x的列表
 listtime3 = [x * 3 | x <- [1..20], x * 3 < 50]
-- 输出 [3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48]

-- 输出在 1..500中所有能够被 13和9整除的数

divisBy9N13 = [x | x <- [1..500],x `mod` 13 == 0, x `mod` 9 == 0]
-- 输出[117,234,351,468]

-- 列表排序
-- 需要import Data.List
sortedList = sort [9,8,1,2,3,4,7,6]

-- zipWith 可以合并两个列表
 sumOfLists = zipWith (+) [1,2,3,4,5] [6,7,8,9,10]
 -- 输出[7,9,11,13,15]

 --数据过滤,通过filter函数,能够保留满足条件的数据
listBiggerThan5 = filter (>5) sumOfLists

-- takeWhile 能够取出数据直到条件为false

evenUp20 =  takeWhile (<=20) [2,4..]

-- foldl 从左到右应用运算符
-- foldr 从右到左应用运算符
foldl (*) 1 [1,2,3,4]
-- 24


-- ------TUPLES ------
-- Tuple 能够存储多种类型,但是其大小是固定的
randTuple = (1,"Random tuple")

bobsSmith = ("Bob Smith",52)

-- Get the first value
bobsAge = fst bobsSmith
-- Get the second value
bobsAge = snd bobsSmith

-- zip函数能够将两个列表压缩为tuples

names =["Bob","Mary","Tom"]
address =["123 Main","234 North","567 south"]

nameNaddress = zip names address
-- 输出 [("Bob","123 Main"),("Mary","234 North"),("Tom","567 south")]

-- ------ FUNCTIONS -------
-- ghc --make haskelltut 将会编译你的程序并执行main函数

-- Functions 必须由小写字母开始

-- 我们能够使用let关键字定义一个函数
-- let num7 = 7
-- let getTriple x = x * 3
-- getTriple num7 = 21

-- main 函数能够在terminal中被调用的main函数

main = do
    -- 在一行中打印
    putStrLn "What's your name"
    -- 获取用户的输入并将其存储到name中
    -- <- 运算符能从IO操作中取得数据并放入变量中
    name <- getLine

    putStrLn ("hello" ++ name)

-- 创建一个名为addMe 的函数
-- x 是一个参数,然后后面是类型签名
-- 传入的类型如果符合要求将会自动应用函数声明
-- 所有的函数都要求有返回值
-- 如果一个函数没有参数则称为一个定义或一个名称

--你可以通过如下的形式定义一个函数:
-- funcName :: param1 -> param2 -> returnType
addMe :: Int -> Int -> Int

-- funcName param1 param2 = operations (Returned Value)
-- 执行: addMe 4 5
addMe x y = x + y

-- 如果没有类型声明则该函数能够处理浮点数
sumMe x y = x + y


-- 当然你也可以定义一个tuple相加函数
addTuples :: (Int,Int) -> (Int,Int) -> (Int,Int)
addTuples (x1,y1) (x2,y2) = (x1 + x2, y1 +y2)

-- 你可以根据不同的值进行不同的操作 类似于switch case
whatAge :: Int -> String
whatAge 16 = "You can drive"
whatAge 18 = "You can vote"
whatAge 21 = "You are a adult"
-- default
whatAge x = "Nothing Import"

-- 定义一个我们期望输入以及输出的函数
factorial :: Int -> Int
-- 如果是0 则返回1 (递归函数)
factorial 0 = 1
factorial n = factorial(n -1)

-- 3 * factorial (2) : 6
-- 2 * factorial (1) : 2
-- 1 * factorial (0) : 1

-- 当然你也可以定义一个乘法的Factorial
productFactorial n = product [1..n]

-- 我们能够利用竖线来根据不同情况下的返回值
isOdd :: Int -> Bool

isOdd n
    -- if 如果是奇数
    | n `mod` 2 == 0 = False
    -- else
    | otherwise = True

-- 当然这个函数能够精简
isEven n = n `mod` 2 == 0

-- 多个条件的 if else 

    whatGrade :: Int -> String
    whatGrade age
        | (age >= 5) && (age <= 6) = "Kindergarten"
        | (age >= 6) && (age <= 10) = "Elementary school"
        | (age >= 10) && (age <= 14) = "Middle school"
        | (age >= 14) && (age <= 18) = "High school"
        |  otherwise "Go to college"

-- 使用where能够帮我们处理条件
batAvgRating :: Double -> Double -> String
batAvgRating hits atBats
    | avg <= 0.200 = "Terrible Batting Average"
    | avg <= 0.250 = "Average Player"
    | avg <= 0.280 = "Your doing pretty good"
    | otherwise = "You're a Superstar"
    where avg = hits / atBats

-- 多条件判断不同的list状态
getListItems :: [Int] -> String
getListItems [] = "Your list is empty"
getListItems (x:[]) = "Your list contains " ++ show x
getListItems (x:y:[]) = "Your list contains " ++ show x ++ " and " ++ show y
getListItems (x:xs) = "The first item is " ++ show x ++ " and the rest are " 
    ++ show xs

-- 我们也能够通过模式来定义一个函数
getFirstItem :: String -> String
getFirstItem [] = "Empty String"
getFirstItem [email protected](x:xs) = "The first letter in " ++ all ++ "is" ++ [x]



-- ------ 高阶函数 -------
-- 能够将一个函数像一个值一样传入到另一个函数中

times4 :: Int -> Int
times4 x = x * 4

-- map 能够将一个列表应用于另一个函数并求值

listTimes4 = map times4 [1,2,3,4,5]
-- [4,8,12,16,20]

-- 然后我们来定义一个map

multBy4 :: [Int] -> [Int]
multBy4 [] = []

-- 将一个列表中的某个值取出然后乘以4再存入到另一个列表中
-- 这里的xs 类型是 [Int], 这是一个递归写法 
multBy4 (x:xs) = times4 x : multBy4 xs

-- 判断两个字符串是否相等

areStringEq :: [Char] -> [Char] -> Bool
areStringEq [] [] = True
areStringEq (x:xs) (y:ys) = x == y && areStringEq xs ys
areStringEq _ _ = False

-- 将一个函数作为另一个函数的参数
-- (Int -> Int) 代表我们需要一个参数是Int 返回值是Int的函数作为参数传入

doMult :: (Int -> Int) -> Int
doMult func = func 3

num3Time4 = doMult times4

-- 返回一个函数
getAddFunc :: Int -> (Int -> Int)

-- 我们能够值传入
getAddFunc x y = x + y

-- 我们也能得到一个+3的函数

adds3 = getAddFunc 3
fourPlus3 = adds3 4

-- 我们也能够将这个函数用到map中

threePlusList = map adds3 [1,2,3,4,5]


-- ------ LAMBDA ------
-- 创建一个匿名函数 也称为lambda 用 \ 开始表示这是一个lambda (\arguments -> result)

db1To10 map (\x -> x * 2) [1..10]

-- ------- 条件 ------
-- 所有的if 都必须包含else

doubleEvenNumber y = 
    if (y `mod` 2 /= 0)
        then y
        else y * 2

-- 我们能够利用case表达式
getClass :: Int -> String
getClass n = case n of 
    5 -> "Go to kindergarten"
    6 -> "Go to elementary school"
    _ -> "Go to some place else"


-- ------ MODULES -------
-- 我们能够将一组函数组织起来,集合成一个module,通过import能加载一个模块
-- 那么如何创建一个模块呢?
-- 1. 创建一个文件
-- 2. 将所有需要使用的函数包含进去
-- TODO
-- 3.  在文件的顶部将所有需要导出的函数列出

-- ------ 枚举 ------

data BaseallPlayer = Pitcher
                    | Catcher
                    | Infield
                    | Outfield
                deriving Show

barryBonds :: BaseallPlayer -> Bool
barryBonds Outfield = True

barryInOf print(barryBonds Outfield)

-- ------ 自定义类型 ------

data Customer = Customer String String Double
    deriving Show

--定义自定义类型的变量
tomSmith :: Customer
tomSmith = Customer "Tom Smith" "123 Main st" 20.50

-- 定义一个需要使用该自定义类型的函数
getBalance :: Customer -> Double
getBalance (Customer _ _ b) = b

tomSmithBal print(getBalance tomSmith)


data RPS = Rock | Paper | Scissors

shoot :: RPS -> RPS -> String
shoot Paper Rock = "Paper Beats Rock"
shoot Rock Scissors= "Rock Beats Scissors"
shoot Scissors Paper= "Rock Beats Scissors"
shoot Scissors Rocks= "Scissors Lose to Rocks"
shoot Paper Scissors= "Paper Lose to Scissors"
shoot Rock Paper= "Rock Loses to Paper"
shoot _ _= "Error"

data Shape = Circle Float Float Float | Rectangle Float Float Float Float
    deriving (Show)

-- :t Circle = Float -> Float -> Float -> Float

area :: Shape -> Float
area (Circle _ _ r) = pi * r ^ 2 
area (Rectangle x y x2 y2) = (abs (x2 - x))  * (abs (y2 - y))

-- 使用 $ 符号可以把$后面的表达式作为一个参数传入到前面的函数中
-- 使用 . 可以作为一个管道符号,将后面一个函数的输出作为前一个函数的输入
putStrLn . show $ 1 + 2

-- Get area of shapes 
areaOfCircle = area (Circle 50 60 20)

areaOfRectangle = area $ Rectangle 10 10 100 100

-- ------ Type Class -------
-- Num, Eq 和 Show 是类型类
-- Type Class相当于面向对象的接口
-- 多态函数(具有多种参数,多种数据类型,通常用类型定义
-- 例如, + 运算符就是用Num 类型类定义的
-- :t (+) :: Num a => a -> a -> a
-- 这代表 a 是Num的一个实例,+ 能够处理两个a类型的数然后返回一个类型为Num的数

--自定义一个自定义类型类,并让其能够进行比较

data Emplyee = Emplyee {
    name :: String,
    position :: String,
    idNum :: Int,
} deriving (Eq,Show)

samSmith = Emplyee{name = "Sam Smith",position = "Manager",IdNum = 1000}
pamMax = Emplyee{name = "Pam Max",position = "Sales",IdNum = 1001}

isSamPam = smaSmith == pamMax

samSimithData = show smaSmith

-- 实现一个自己实现的Eq 和Show类型类的数据类型
data ShirtSize = S | M | L

instance Eq ShirtSize where
    S == S = True
    M == M = True
    L == L = True
    _ == _ = False

instance Show ShirtSize where
    show S = "Small"
    show M = "Medium"
    show L = "Large"

-- Check if S is in the list
-- 需要实现Eq才能够用elem 方法
smallAvail = S `elem` [S, M, L]

-- Get string value for ShirtSize
-- 需要实现Show 类型类
theSize = show S

-- 自定义类型类
class MyEq a where
    areEqual :: a -> a -> Bool


-- 实现自己定义的类型类

instance MyEq ShirtSize where
    areEqual S S = True
    areEqual M M = True
    areEqual L L = True
    areEqual _ _ = Fasle

newSize = areEqual M M




-- ------ I/O ------

sayHello = do
    putStrLn "What's your name: "
    name <- getLine

    putStrLn $ "Hello" ++ name

-- File I/O

writeToFile = do
    theFile <- openFile "test.txt" WriteMode

    hPutStrLn theFile ("Random line of text")

    hClose theFile

readFromFile = do
    theFile2 <- openFile "test.txt" ReadMode

    contents <- hGetContents theFile2
    putStr contents
    hClose theFile2


-- ------ EXAMPLE: FIBONACCI SEQUENCE ------
-- 1,1,2,3,5,8, ...

-- 1 : 1 : 代表函数的开始
-- | 表示对于每个 a,b 并将其相加
-- <- 存储 a + b 之和
-- tail : 得到除了第一个值之外的所有值
-- zip 将两个列表压缩,并得到一个tuple 列表

fib = 1 : 1: [a + b | (a , b) <- zip fib (tail fib)]
-- 对上式进行推演
-- 1. 首先 fib = 1 然后tail fib = 1
-- 2. 现在列表变成了 [1,1,2] 因为 a:1 + b:1 = 2
-- 3. 然后第二步, fib = 1 然后 (tail fib) = 2
-- 4. 现在列表变成了 [1,1,2,3] 因为 a: 1 + b: 2 = 3

matering sed —— 精通sed


mastering sed

我承认这是标题党,但是sed在平时工作中sed真的很有用,特别是像我这种需要写一些shell进行自动化工作的。

sed 快速入门

sed 作为流编辑神器,在写脚本的时候往往会发挥奇效,所以这里我将sed的一些关键用法介绍一下,目的在于实用,而不是全面。

-i 参数

常常会看到会有sed -i这样的命令,-i的意思就是直接在源文件上进行操作。

动作

sed动作是我们需要掌握的最为重要的内容 :
– a :新增, a 的后面可以接字串,而这些字串会在新的一行出现(目前的下一行);
– c :取代, c 的后面可以接字串,这些字串可以取代 n1,n2 之间的行;
– d :删除, d 后面通常不接任何字符;
– i :插入, i 的后面可以接字串,而这些字串会在新的一行出现(目前的上一行);
– p :列印,亦即将某个选择的数据印出。通常 p 会与参数 sed -n 一起运行;
– s :替换,可以直接进行取代的工作通常这个 s 的动作可以搭配正则语法,语法很像vim的替换。

样例

测试文件内容:

# cat song.txt
my name is zhangshan
his name is lisi
my dog name is doglas
today is good day
we sang a song:
lalalalala
hahahahaha

s 替换

sed "s/zhangshan/wangnima/g" song.txt

替换的方式和vim很像

输出

# sed "s/zhangshan/wangnima/g" song.txt
my name is wangnima
his name is lisi
my dog name is doglas
today is good day
we sang a song:
lalalalala
hahahahaha

这样只会将修改之后的文件输出到标准输出,如果需要修改原来的文件的话,加上-i参数:

sed -i "s/zhangshan/wangnima/g" song.txt

修改就会在源文件上生效

用正则武装sed
正则表达式是一件神兵利器,这里介绍一些较为简单的正则表达式:
^ 表示一行的开头,如:/^my/ 这就是以单词my为开头的匹配
$ 表示一行的结尾,如: /:$/ 就是以字符:为结尾的匹配
\< 表示一个词的开头,如\<s 就是以s开头的词
\> 表示一个词的结尾,如g\> 就是以g为结尾的词
. 表示任意单个字符
* 表示一个字符可以出现0次或者多次
? 表示一个字符可以出现1次或者多次
[] 集合,例如[abc]可以匹配a,或b,或c,经典例子:[a-zA-Z]匹配所有26个字母,^表示取反,如[^a]表示非a的字符。

只替换第一行的内容

sed "1s/name/nume/g"

输出

# sed "1s/name/nume/g" song.txt
my nume is wangnima
his name is lisi
my dog name is doglas
today is good day
we sang a song:
lalalalala
hahahahaha

指定行号范围

sed "1,2s/name/nume/g" song.txt

输出

# sed "1,2s/name/nume/g" song.txt
my nume is wangnima
his nume is lisi
my dog name is doglas
today is good day
we sang a song:
lalalalala
hahahahaha

只替换每行第一个s

sed "s/s/S/1" song.txt

输出

# sed "s/s/S/1" song.txt
my name iS wangnima
hiS name is lisi
my dog name iS doglas
today iS good day
we Sang a song:
lalalalala
hahahahaha

只替换每行第2个s

sed "s/s/S/2" song.txt

输出

# sed "s/s/S/2" song.txt
my name is wangnima
his name iS lisi
my dog name is doglaS
today is good day
we sang a Song:
lalalalala
hahahahaha

只替换每行第2个之后的s

sed "s/s/S/2g" song.txt

输出

# sed "s/s/S/2g" song.txt
my name is wangnima
his name iS liSi
my dog name is doglaS
today is good day
we sang a Song:
lalalalala
hahahahaha

多次匹配

将第一行的”wangnima”改成”zhangshan”然后把第二行的lisi改成”wangwu”

sed "1s/wangnima/zhangshan/g; 2s/lisi/wangwu/" song.txt

输出

# sed "1s/wangnima/zhangshan/g; 2s/lisi/wangwu/" song.txt
my name is zhangshan
his name is wangwu
my dog name is doglas
today is good day
we sang a song:
lalalalala
hahahahaha

等价命令

sed -e "1s/wangnima/zhangshan/g" -e "2s/lisi/wangwu/" song.txt

`&` 的妙用
可以用&表示被匹配到的字符,我们可以用这个trick 做一些事情:

sed "s/name/@&@/g" song.txt

输出:

my @[email protected] is wangnima
his @[email protected] is lisi
my dog @[email protected] is doglas
today is good day
we sang a song:
lalalalala
hahahahaha

圆括号匹配
在正则表达式中,圆括号括起来的正则部分可以作为变量使用,sed中用\1,\2…表示匹配到的值:

sed "s/\([a-z]*\) name is \([a-z]*\)/\1:\2/g" song.txt

输出

# sed "s/\([a-z]*\) name is \([a-z]*\)/\1:\2/g" song.txt
my:wangnima
his:lisi
my dog:doglas
today is good day
we sang a song:
lalalalala
hahahahaha

用gomock进行mock测试


在开发过程中往往需要配合单元测试,但是很多时候,单元测试需要依赖一些比较复杂的准备工作,比如需要依赖数据库环境,需要依赖网络环境,单元测试就变成了一件非常麻烦的事情。举例来说,比如我们需要请求一个网页,并将请求回来的数据进行处理。在刚开始的时候,我通常都会先启动一个简单的http服务,然后再运行我的单元测试。可是这个单元测试测起来似乎非常笨重。甚至在持续集成过程中,我还为了能够自动化测试,特意写了一个脚本自动启动相应的服务。事情似乎需要进行一些改变。

mock对象就是为了解决上面的问题而诞生的,mock(模拟)对象能够模拟实际依赖对象的功能,同时又不需要非常复杂的准备工作,你需要做的,仅仅就是定义对象接口,然后实现它,再交给测试对象去使用。

go-mock是专门为go语言开发的mock库,该库使用方式简单,支持自动生成代码,可以说是不可多得的好工具。下面我就简单地展示一下go-mock是如何工作的:

首先你需要做的是将依赖下载到本地:

go get github.com/golang/mock/gomock
go get github.com/golang/mock/mockgen

第一个是代码依赖,第二个是命令行工具(特别好用)。

下面用一个非常简单的例子来说明gomock是如何工作的:

我在$GOPATH/src目录下新建一个项目:hellomock,在$GOPATH/src/hellomock目录下新建hellomock.go,并定义一个接口Talker:

package hellomock

type Talker interface {
    SayHello(word string)(response string)
}

然后我们需要一个实现了Talker功能的结构体,假设我们有这样的场景,我们现在有一个迎宾的岗位,需要一个能够迎宾的迎宾员,当然这个迎宾员可以是一个人,或者是一只鹦鹉。那么我们需要做的是,定义一个Persion结构体(或者是鹦鹉或者是别的什么东西),并实现Talker接口:

person.go

package hellomock

import "fmt"

type Person struct{
  name string
}

func NewPerson(name string)*Person{
  return &Person{
      name:name,
  }
}


func (p *Person)SayHello(name string)(word string) {
  return fmt.Sprintf("Hello %s, welcome come to our company, my name is %s",name,p.name)    
}

现在我们的Person已经实现了Talker接口,现在我们让他发挥作用吧!

现在假设,我们有一个公司,公司有一个迎宾员,也就是我们的前台妹子,这个妹子实现了Talker接口.她能够自动向来的客人SayHello:

company.go

package hellomock

type Company struct {
  Usher Talker
}

func NewCompany(t Talker) *Company{
  return &Company{
    Usher:t,
  }
}

func ( c *Company) Meeting(gusetName string)string{
  return c.Usher.SayHello(gusetName)
}

我们的场景已经设计好了,那么我们传统的话,会如何实现单元测试呢?

company_test.go

package hellomock

import "testing"

func TestCompany_Meeting(t *testing.T) {
    person := NewPerson("王尼美")
    company := NewCompany(person)
    t.Log(company.Meeting("王尼玛"))
}

测试之:

/usr/local/go/bin/go test -v hellomock -run ^TestCompany_Meeting$

    company_test.go:8: Hello 王尼玛, welcome come to our company, my name is 王尼美

ok      hellomock   0.013s

现在我们构造一个王尼美还是很简单的,但是我们现在要用mock对象进行模拟,这时mockgen就登场了:

➜  hellomock> mkdir mock                                        
➜  hellomock> mockgen -source=hellomock.go > mock/mock_Talker.go

这个时候,将会生成mock/mock_Talker.go文件:

需要注意的是,自动生成的文件同源文件在不同的包下,需要新建一个目录存放

我们并不需要在意生成文件的内容,我们只需要知道如何去使用即可

mock_Talker.go

// Automatically generated by MockGen. DO NOT EDIT!
// Source: hellomock.go

package mock_hellomock

import (
    gomock "github.com/golang/mock/gomock"
)

// MockTalker is a mock of Talker interface
type MockTalker struct {
    ctrl     *gomock.Controller
    recorder *MockTalkerMockRecorder
}

// MockTalkerMockRecorder is the mock recorder for MockTalker
type MockTalkerMockRecorder struct {
    mock *MockTalker
}

// NewMockTalker creates a new mock instance
func NewMockTalker(ctrl *gomock.Controller) *MockTalker {
    mock := &MockTalker{ctrl: ctrl}
    mock.recorder = &MockTalkerMockRecorder{mock}
    return mock
}

// EXPECT returns an object that allows the caller to indicate expected use
func (_m *MockTalker) EXPECT() *MockTalkerMockRecorder {
    return _m.recorder
}

// SayHello mocks base method
func (_m *MockTalker) SayHello(name string) string {
    ret := _m.ctrl.Call(_m, "SayHello", name)
    ret0, _ := ret[0].(string)
    return ret0
}

// SayHello indicates an expected call of SayHello
func (_mr *MockTalkerMockRecorder) SayHello(arg0 interface{}) *gomock.Call {
    return _mr.mock.ctrl.RecordCall(_mr.mock, "SayHello", arg0)
}

接下来看看如何去使用这个mock对象,新建一个单元测试:

func TestCompany_Meeting2(t *testing.T) {
    ctl := gomock.NewController(t)
    mock_talker := mock_hellomock.NewMockTalker(ctl)
    mock_talker.EXPECT().SayHello(gomock.Eq("王尼玛")).Return("这是自定义的返回值,可以是任意类型。")

    company := NewCompany(mock_talker)
    t.Log(company.Meeting("王尼玛"))
    //t.Log(company.Meeting("张全蛋"))
}

测试之:

/usr/local/go/bin/go test -v hellomock -run ^TestCompany_Meeting2$
    company_test.go:21: 这是自定义的返回值,可以是任意类型。
ok      hellomock   0.015s

可以看到,返回的是我们在mock对象上定义的返回值。

需要说明的一点是,mock对象的SayHello可以接受的参数有gomock.Eq(x interface{})gomock.Any(),前一个要求测试用例入餐严格符合x,第二个允许传入任意参数。比如我们在注释掉的测试中传入了”张全蛋”,结果报错,测试失败:

/usr/local/go/bin/go test -v hellomock -run ^TestCompany_Meeting2$
    controller.go:113: no matching expected call: *mock_hellomock.MockTalker.SayHello([张全蛋])
exit status 1
FAIL    hellomock   0.007s

本文作为抛砖引玉,gomock还有很多高级用法,希望大家能够自行探索。

参考文章:

https://github.com/golang/mock/blob/master/README.md

https://github.com/grpc/grpc-go/blob/master/Documentation/gomock-example.md

转载请注明出处

Elliptic Curve Cryptography: a gentle introduction (4)


椭圆曲线加密:安全性以及RSA对比

原标题:Elliptic Curve Cryptography: breaking security and a comparison with RSA

这篇文章是ECC:优雅入门系列的第四篇文章,我们已经在前面的文章中知道了一个椭圆曲线上的离散对数离散对数问题是如何在保障加密安全的过程中扮演重要角色的。但是,如果你还记得的话,我们曾经提到说目前还没有严格的数学证明来证明计算离散对数的复杂性:我们相信这件事情是“困难”的,但是我们并不确定。在这篇文章的开篇,我们将尝试去解释在目前的技术能力下,完成这件事情是多么地“困难”。
然后,在这篇文章的第二部分,我们将尝试去回答这样的问题,为什么我们需要椭圆曲线?RSA(或者其他基于模运算的加密系统)不是也挺好的吗?

攻破离散对数问题

我们将会在下文中看到两个最为有效的用来计算椭圆曲线上的离散对数的算法:baby-step,giant-step算法,以及Pollard’s方法。

在开始之前,我还是简单提醒一下,所谓的离散对数问题就是给定两个点P和Q,找到这样的证书x使得满足式子 Q = xP。其中的点是椭圆曲线子群中的点,这个椭圆曲线应该拥有基点G和阶n。

Baby-step,giant-step

在描述这个算法的细节之前,我们先快速地看一下这个问题:我们始终能够写出这样的整数x使得x = am+b,其中a,m,b是三个任意整数。举例来说,我们可以写出 10 = 2\cdot 3+4

根据上面的规则,我们可以给出如下的等式来描述离散对数问题:

    \[Q = xP \ Q = (am +b)P \ Q = amP + bP \ Q - amp = bP\]

“baby-step,giant-step”其实是一个二分算法。不同于暴力破解( brute-force attack)(通过枚举所有有可能的点xP得到我们需要的Q),我们可以”稍微”地减少计算量,通过计算bP和Q-amP直到我们找到相似值。这个算法的具体步骤如下:
1. 计算 m = \lceil \sqrt{n} \rceil
2. 对于所有的b属于0,...,m计算bP并将结果存储到hash表中.
3. 对于所有的a属于0,...,m:
1. 计算amP
2. 计算Q - amP
3. 检查这个hash表并观察是否存在这样的点使得Q - amP = bP
4. 如果这样的点存在,那么我们就找到了这样的x 满足x = am +b

就像你看到的一样,我们计算点bP的时候步进非常小,就像baby走路一样,系数b慢慢增加(1P,2P,3P,...)。然后,在这个算法的第二部分,我们计算amP的时候步进又很大,因为系数am的变化规律是(1mP,2mP,3mP,...,其中m是一个大整数)。
baby-step-giant-step

baby-step,giant-step算法:通过小步进初始化一些点在hashmap中进行存储,然后我们计算大步进并比较新的点是否在hashmap中能够被找到,计算离散对数相当于是一个重新排序的事情。

为了能够理解这个算法是怎么工作的,首先我们先忘记点bP是如何缓存的,而是考虑等式 Q = amP + bP。看看如下的步骤:
– 当a=0的时候我们看看Q是否等于bP,其中b0m之间的某个整数。那么在实际上我们就是在比较Q0PmP之间是否相等。
– 当a = 1 时,我们检查Q是否等于mP + bP。其中这里的Q就相当于同 mP2mP之间的值比较。
– 当a=2我们需要比较Q2mP3mP之间的点。
– …
– 当 a = m-1,我们其实在比较Q同(n-1)mPm^2P = nP之间的点。
所以终上所述,我们其实是在检查所有的从0P变化到nP的点。(这么多就足够了,这已经是所有的可能情况了)这需要我们计算至多2m次加法和乘法(包括baby-step中的m和giant-step中的)。
当然我们知道在hash表中找一个元素需要花费O(1)的复杂度,所以我们可以轻易地知道,这个算法需要花费的时间和空间复杂度都是O(\sqrt{n})(或者是O(2^{\frac{k}{2}})),虽然这还是需要很多时间,但是比穷举是好多了。

Baby-step,giant-step实战

为了能够说明O(\sqrt{n})是有意义的,我们以标准曲线为例子:prime192v1(也叫做secp192r1,ansiX9p192r1),这个曲线拥有阶数n = 0xffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831。这个数的开根号大约是7.922816251426434 \cdot 10^{28}
想象一下为了在hash表中存储\sqrt{n}个点,假设每个点需要32byte,我们的hash表大约需要2.5\cdot 10^{30}byte的内存网上查了一下,将全世界的存储能力加起来以zettabyte(10^{21} byte)为单位来衡量,我们的hash表需要的存储空间这里还是大约相差10倍左右。就算我们的一个点只需要存储1 byte,还是无法存储这些点。

这非常的令人惊讶,但是更加令人惊讶的是,曲线prime192v1几乎是所有曲线中阶数最小的了。secp521r1(另一个NIST中规定的标准曲线)阶数大约是6.9 \cdot 10^{156}

亲自动手实践baby-step,giant-step

安装惯例,我写了一个python程序利用baby-step,giant step算法计算离散对数。明显这个脚本只对低阶的椭圆曲线有效,如果你想用曲线secp521r1那你就等着收到一个MemoryError吧。
脚本的输出结果应该如下:

Curve: y^2 = (x^3 + 1x - 1) mod 10177
Curve order: 10331
p = (0x1, 0x1)
q = (0x1a28, 0x8fb)
325 * p = q
log(p, q) = 325
Took 105 steps

Pollard’s \rho

Pollard’s \rho是另一个计算离散对数的算法。这个算法和babe-step,giant-step算法有相同的复杂度O(\sqrt{n}),但是它的空间复杂度只有O(1).如果baby-step,giant-step算法因为内存空间限制无法解决的问题,Pollard算法是否能解决呢?

在Pollard算法中,我们将会去解决稍稍不同的问题,给定PQ,找到这样的整数abAB满足aP+bQ = AP + BQ
一旦这四个整数都被找到了,我们可以用等式Q = xP来找到这个x:

    \[aP +bQ = AP + BQ \ aP+bxP = AP + BxP \ (a + bx)P = (A+Bx)P \ (a - A)P = (B - b)xP\]

限制我们可以得到P的值,但是在计算它的值之前,我们需要重新说明一下,我们的子群是循环的并且具有阶n因此,在计算的时候需要加上模n作为系数:

    \[a -A \equiv (B-b)x (\mod n) \ x = (a-A)(B - b)^{-1} \mod n\]

Pollard’s \rho算法的理论其实很简单,我们定义一个(a,b)的伪随机序列,这个序列产生的值可以用于产生点aP + bQ,因为PQ都是同一个循环子群中的元素,所以产生的一系列点aP+bQ也是循环的

上面的说明的意思就是只要我们遍历我们的伪随机序列(a,b),早晚我们就会发现这是一个换,所以我们可以肯定一定存在这样的值对(A,B)使得等式aP+bQ = AP+BQ
不同的值对代表同一个点,这点就在我们计算对数的时候起到作用。
问题是:我们如何高效地得到这样的环?

Tortoise and Hare(龟兔赛跑)

为了能够找出我们的换,我们可以尝试所的a和b的可能值,通过pairing funciton,但是这里却有n^2个可能的值对,那么我们的算法的复杂度就会是 O(n^2),比暴力穷举的复杂度还搞。
但是这里还是有稍微快点的算法的:龟兔算法(tortoise and hare algorithm)也叫Floyd’s cycle-finding algorithm。下面的图片展示了这个算法是怎么工作的,这就是Pollard’s rho算法的核心部分了。
tortoise-hare

我们现在用曲线y^2 \equiv x^3 + 2x+3 (\mod 97)以及点P = (3,6)Q = (80,87),这两个点都是属于这个5阶子群的。
我们用不同的速度遍历这个值对序列知道我们找到两个不同的值对(a,b)和(A,B)能够得出相同的但。在这个例子我们相同的值对是(3,3)和(2,0),通过这两个点我们可以算出x = (3-2)(0-3)^{-1} \mod 5 =3,而且这确实是正确的 Q = 3P.

基本地,我们将我们的随机数生成序列得到(a,b)值对,然后计算得到相应的点序列aP+bQ。这个值对序列可能是也可能不是循环的,但是点序列确实循环的,因为PQ都是由相同的基点产生的,从子群理论中我们知道仅仅在其上用加法和乘法我们是无法“逃出”子群的。

现在我们用两个小动物来做比喻,乌龟和兔子,乌龟和兔子将会找到两个相同的点,但是却是由不同的系数对产生的。更加详细地,乌龟将会找到值对(a,b)而兔子将会找到值对(A,B),最后会满足aP+bQ = AP+BQ

如果你的随机数序列是由某种算法(或者就是固定存储的),那么我们就可以简单地退出这个龟兔理论所需要的空间复杂度为 O(\log n),然而计算时间复杂度却没有那么简单,但是我们可以通过计算概率的方式得到时间复杂度就和我们前面说的一样是O(\sqrt{n})

与Pollard’s \rho亲密接触

我已经写了一个用于计算Pollard’s rho的python脚本,虽然这个脚本没有完整地实现Pollard’s rho算法,但是就是有稍稍的改进(我用了更加高效的随机数生成算法生成值对序列)。这个脚本包含了一些非常有用的注水,如果你对这个算法感兴趣的话,去阅读这些注释吧。
这个脚本和baby-step, giant step一样都只能工作在小规模的曲线上,而且和上面的输出结果是一样的。

与Pollard’s \rho实战

我们前面说到baby-step, giant step算法无法应用到实际当中,因为它需要巨大的内存空间,然而Pollard’s rho却不需要那么大的内存空间,那么实际上呢?

Certicom在1988年发起了一项挑战,计算比特位数为109到359的椭圆曲线的离散对数。到今天为止,也只有109bit长度的曲线被成功攻破,这次尝试是在2004年发起的,在维基百科上的评论是:

he prize was awarded on 8 April 2004 to a group of about 2600 people represented by Chris Monico. They also used a version of a parallelized Pollard rho method, taking 17 months of calendar time.

我们已经说过了,prime192v1是目前来说“最小”的椭圆曲线了,我们也说过Pollard’s rho 的时间复杂度是O(\sqrt{n}),如果我们用Chris Monico相同的技术(相同的算法,在相同的硬件和相同的机器上),我们需要花多久来计算一次在prime192v1上的离散对数呢?

    \[17\ months \times \frac{\sqrt{2^{192}}}{\sqrt{2^{109}}} \approx 5\cdot 10^{13} \  months\]

这个数字足以在某种程度上说明破解离散对数问题在目前的技术能力上的难度了。

对比一下Pollard’s rho 和Baby-step giant step算法

我决定将baby-step giant-stepPollard’s rho一起同暴力穷举算法合在一起放到第[四个脚本](fourth script)中做一个比较,看看它们之间的性能。
第四个脚本会在“小型”曲线上用不同的算法计算所有的点,并报告一共耗时多少:

Curve order: 10331
Using bruteforce
Computing all logarithms: 100.00% done
Took 2m 31s (5193 steps on average)
Using babygiantstep
Computing all logarithms: 100.00% done
Took 0m 6s (152 steps on average)
Using pollardsrho
Computing all logarithms: 100.00% done
Took 0m 21s (138 steps on average)

正如我们所期待的,暴力穷举同其它两个算法相比就非常地慢,Baby-step giant step算法是最快的,而Pollard’s rho算法比Baby-step giant step算法慢三倍(虽然看上去它用的内存空间最小且步数最小)。

当然我们在看看计算步数,暴力穷举平均花费了5193步,非常接近10331/2(曲线阶数的一半),Baby-step和Pollard’s rho花费了152步和138步两个步数都很接近10331的平方根(101.64)。

最终结论

我们讨论了很多算法,同时也给出了相当的数据。但是我们一直都有一个问题,就是:算法能够在很多方面加以提升,比如硬件,特殊针对于计算离散对数的硬件也会出现。

实际上在今天提升硬件的方法看上去是不实际的,并不是说这个方法不可行,而是我们又更加好的办法(记住,现在还没有严谨的证明离散对数的复杂性)。

##Shor’s algorithm
如果现在的技术不可行,那么未来的技术呢?好吧,现在有些事变得有些令人担忧:实际上存在一种量子算法能够在多项式时间内解出离散对数问题,这个算法的时间复杂度是O((log_n)^3),空间复杂度是O(log_n)

之所以量子算法能够有这么高的效率,得益于它的状态叠加。在传统的计算机中,内存单元(例如bit)只有两种状态1或者0,没有中间状态。但是相对的,量子计算机的内存单位(被称为qubit)的状态却是无法被确定的,这同薛定谔的猫理论类似,只要在其被测量的时候才能知道其具体状态,状态叠加并不是说这个qubit可以同时为0和1,而是我们可能发现0也可能发现1。而量子算法就是基于每个qubit的可能性构建的。

其实这隐含了一个qubit的特性,就是我们可以在同一时刻输入多个可能的输入值。举例来说我们可以告诉量子计算机这里有一个数x均匀地分布在0到n-1之间,这仅仅需要\log n个quebit而不是n\log n个bit。然后我们可以让量子计算机计算标量乘法得到xP。结果会在我们给定的0P到(n-1)P之间叠加——也就是说,我们如果现在测量我们的qubit们我们将会得到0P(n-1)P之间的某个值,而概率是1/n。

上面的只是让你知道状态叠加的强大力量,,但是Shor’s算法目前还是没有办法实现的,实际上其实更加复杂。其中比较复杂的一点是,当我们能够“模拟”同时有n种状态的时候,我们需要输出的是一个答案而不是一堆答案(即,我们需要知道单一的对数,而不是一堆可能错误的对数)。

ECC 和RSA

现在让我们忘了该死的量子计算,这个问题目前还不能作为一个严重的问题,现在我们需要讨论的问题是在RSA还不错的情况下,为什么要用椭圆曲线呢?

一个由NIST给出的快速答案,它给出了一个同等安全等级下的密钥大小对比表

RSA Key size (bits) ECC key size (bits)
1024 160
2048 224
3072 256
7680 384
15360 521

需要注意的是,RSA的key大小和ECC的key大小并没有相应的线性关系(换句话说,如果我们将RSA的密钥大小加倍,并不能相应地得到双倍的ECC的密钥)。这个表告诉我们ECC不仅仅需要较小的内存,而且公钥的生成和签名更快。
但是为什么是这样的呢?这是因为在椭圆曲线上的计算离散对数的最快的方法就是 Pollard’s rho and baby-step giant-step但是在RSA体系下我们却有更加快的算法。一个较为实用的算法是: general number field sieve,一个通过因式分解计算离散对数的算法。general number field sieve是目前整数因式分解最快的算法。

所有基于模运算的加密系统都有相同的问题,包括DSA, D-H 和ElGamal。

NSA的隐藏威胁

现在我们需要讨论一下更加难的部分。目前我们已经讨论了算法和数学的部分,现在我们讨论一下复杂的人和事。

如果你还记得的话,上一篇文章我们说到有一些椭圆曲线是很脆弱的,为了解决来着可疑来源的曲线的可信任问题,我们加入了一个随机种子到主要参数当中。而且我们可以看到那些NIST的标准曲线都是可验证的随机的。

如果我们阅读维基百科“nothing up my sleeve”我们可以看到如下内容:
– MD5的随机数是从正弦整数中产生的
– Blowfish的随机数是从\pi的第一个数字产生的
– RC5的随机数是从e和黄金比例中产生的
这些数字都是随机的因为这些数字都是非均匀分布的。这些都是毋庸置疑的,因为这些都是公开的。
但是现在的问题是:NIST曲线的随机数是从哪里来的呢?答案是我们不知道,而且这些随机种子也没有公开。

是否存在这样的可能:NIST已经发现了一类“足够大的”弱椭圆曲线,并尝试了一些可能的随机种子直到生成一个脆弱的曲线?我无法回答这个问题,但是这是一个正当的且重要的问题。我们知道NIST成功地规范化了一个” vulnerable random number generator “(一个奇怪的基于椭圆曲线的若随机数生成器)。可能他们也成功地规范化了一组弱椭圆曲线,但是是不是这样我们无从得知。

理解“可信随机”和“安全”是两码事,这个和对数问题的困难程度或者我们的密钥长度无关,如果我们的算法被攻破了,我们几乎什么都做不了。

考虑到这些,RSA是成功的,因为它不需要任何特殊的领域参数,而且这些领域参数也不会被篡改。RSA(和其他的模运算加密系统一样)在我们无法自己生成领域参数且无法信任授权方时,是一个很好的选择。值得一提的是,TLS用的也是椭圆曲线算法,它基于ECDHE和ECDSA算法,证书基于prime256v1(也称secp256p1)上。

That’s all

我希望你能够喜欢这个系列的文章。我的目标是让你能够对椭圆曲线加密系统有一个基本的了解,知道其术语代表的都是什么意思。如果我达成了我的目标,那么目前依旧能够理解现在的基于ECC的加密系统是怎么工作的,同时你也能够通过阅读一些“不怎么优雅”的文献来加深对这些知识的理解。当我在完成这个系列的文章的时候我跳过了很多细节,用了最简单的术语和知识为了是你能够快速理解。但是我比较担心的是你无法理解网络上的一些较为复杂的术语,我认为这系列的文章能够在简单性和完整性上做到了较好的均衡。

一定要注意仅仅阅读了这系列的文章并不能让你实现一个安全的ECC加密系统:这需要了解很多安全方面的重要细节。还记得requirements for Smart’s attackSony’s mistake——这些例子都告诉我们产生一个不安全的算法是多么简单,以及攻破这些算法是多么容易。

所以,如果你对ECC有着更深层次的兴趣,应该去看些什么呢?

首先,我们已经看到了素数域上的Weierstrass curves,但是你必须要知道其他的域和曲线,典型的有:

  • Koblitz curves over binary fields. 这些曲线定义在y^2 + xy = x^3 ax^2 +1()其中a 是0或1),它的有限域包括了2^m个元素(其中m是一个素数),这个曲线能够明显地提高加法和乘法的效率,标准的Koblitz曲线有nistk163, nistk283nistk571 (三个曲线分别定义在 163, 283 和 571 位的域上)。
  • Binary curves. 这个曲线和 Koblitz curves 很相似,形如 and are in the form x^2+xy=x63+x^2+b (其中b 是一个从随机数). 正如其名,binary curves 被限制到二进制域中。主要的标准曲线有 nistb163,nistb283nistb571。目前有观点认为 Koblitz 和 Binary curves不像 prime curves那么安全。
  • Edwards curves, 形如x^2+y^2=1+dx^2y^2 (其中 d 可以是 0 或 1). 它的特点除了其加法和标量乘法的速度都很快之外,还有它点加的公式都是相同的,在某些情况下可以描述为 (P≠Q,P=Q, P=−Q, ...)。这个特点能够抵御side-channel攻击,这个攻击通过零标量乘法的时间来猜测标量因子。( This feature leverages the possibility of side-channel attacks, where you measure the time used for scalar multiplication and try to guess the scalar coefficient based on the time it took to compute.) Edwards curves 相对来说比较新 ( 2007被发表) 目前还没有权威机构类似于Certicom 或者 NIST对其进行标准化。
  • Curve25519 and Ed25519 are two particular elliptic curves 是分别为ECDH和ECDSA专门设计的曲线,就像Edwards curves, 这两个曲线非常地快速,并能够抵御side-channel 攻击。 并且正如 Edwards curves,这两个曲线还没有被正式标准化,我们还不能够在典型的引用中找到他们的身影(除了OpenSSL,它在2014年支持了Ed25519曲线)。

如果你对ECC的实现细节比较感兴趣,我建议你去阅读以下OpenSSL和GnuTLs的源代码。

最后如果你对ECC背后的数学细节感兴趣,而不是安全高效的算法,你需要知道如下知识:
– Elliptic curves are algebraic varieties with genus one.
– Points at infinity are studied in projective geometry and can be represented using homogeneous coordinates (although most of the features of projective geometry are not needed for elliptic curve cryptography).

以及不要忘记学习finite fieldsfield theory

这些就是你需要查询或者你会感兴趣的全部主题了。

现在,这个系列已经官方完结了。

Elliptic Curve Cryptography: a gentle introduction (3)


椭圆曲线加密算法:ECDH和ECDSA

这篇文章是系列文章ECC:优雅入门中的第三篇文章。

在之前的文章中我们知道了什么是椭圆曲线以及我们定义了一些群律为了能够在椭圆曲线上做一些数学运算。然后我们将椭圆曲线重新在一个素数的有限模整数域中进行描述。在这次重新描述过程中,我们知道了椭圆曲线是如何生成一个循环子群的,以及我们介绍了一些基本的概念:基点(base point)阶(order)辅因子(cofactor)

最后,我们了解了在有限域上的标量乘法是一个“简单”的问题,但是反过来的离散对数问题却是一个“困难”的问题。现在我们一起看看这些东西是如何应用到加密算法中的。

主要参数(Domain parameters)

我们的椭圆曲线算法将会在一个定义在有限域上的的椭圆曲线的子群中运行。因此我们需要如下的几个参数:
素数P 描述了有限域的大小。
系数a和b 用于描述椭圆曲线的方程。
基点G用于生成我们的子群
n ,子群的阶
辅因子h ,子群的辅因子

一言以蔽之,我们算法中所需要的主要参数是一个6元组(p,a,b,G,n,h)。

随机曲线

当我们说离散对数问题是一个“困难的问题”时,其实并不完全正确。这里有一些椭圆曲线是非常脆弱的,这些椭圆曲线能够被一些具有特殊目的的算法快速解决。例如,所有的曲线满足 p = hn (这种曲线的有限域的阶和椭圆曲线的阶相同)能够被Smart’s attack轻而易举地攻破,这个攻击方式能够在多项式时间内将离散对数问题解决。

现在,假设我给你一些曲线的主要参数。这里就会存在一个问题,就是可能我已经发现了一些脆弱的能够被轻而易举地攻破的曲线,但是没有其它人知道,而且我能够建立一个“”快速”的算法,很快地得到我刚刚给你的离散对数的答案。那么我该如何说服你相信我,或者说我并不知道任何的弱点呢?也就是说我该如何证明,这个曲线是安全的(在某种意义上说,这不能被我以特殊的目的攻击)?

为了能够解决这类问题,我们常常会增加一个主要参数:种子S(seed S)。这是一个随机数用来生成系数a和b,或者是基点G,或者两者。这些参数通过对S计算hash生成。Hash,众所周知,非常容易计算,但是逆运算是非常”困难”的。
random-parameters-generation

通过种子生成一个随机曲线的示意图:一个随机数的hash是用来计算曲线的不同参数的。
seed-inversion
如果我们想要作弊,通过主要参数中得到随机种子,我们需要解决一个”hard”问题:hash逆推
一个通过种子生成的曲线被称为通过随机验证。这个利用hash生成参数的理论被称为”nothing up mu sleeve“,这个理论被广泛应用在密码学中。

这个技巧能够提供一些保障,保证这个曲线不是被作者精心设计的隐藏的脆弱的。实际上,如果我给你一个曲线和以和种子,它就意味着我不能够任意地选择参数a和b,而你也相对的可以肯定这个曲线不能够被我利用特定的目的攻击。而这个“相对的”的原因我将在下一篇文章中进行解释。

一个用于生成和检查随机曲线的标准算法已经在ANSI X.9.62中进行描述,这个算法是基于SHA-1。如果你对这个感兴趣,你可以阅读a specification by SECG了解生成可信的随机曲线算法(搜索 “Verifiably Random Curves and Base Point Generators”)。

我写了一个简单的python脚本用于验证所有的随机曲线,这个脚本是基于OpenSSL的。我非常建议你去看看。

椭圆曲线加密(Elliptic Curve Cryptography)

我们在前面花了很多时间,但是最后我们还是到这一节了!废话不多说,简单粗暴:
1. 私钥是一个随机的整数,从{1,...,n-1}中选择(其中n 是子群的阶)。
2. 公钥是一个点H满足条件H = dG(其中G是这个子群的基点)

看到了嘛?如果我们知道d和G(以及其他的主要参数),找到最终的H是很”简单”的。但是如果我们知道H和G,找到私钥d是困难的,因为这需要我们解决一个离散对数问题

现在我们将介绍两个基于上述条件的公钥加密算法:ECDH(Elliptic curve Diffie-Hellman)用于加密,另一个是ECDSA(Elliptic Curve Digital Signature Algorithm)用于数字签名。

利用ECDH加密

ECDH 是Diffie-Hellman算法。这实际上是一个密钥交换协议,而不仅仅是一个加密算法。简而言之,ECDH定义了密钥应该如何生成,以及在双方之间如何交换。至于如何用这个密钥加密数据由我们自己决定。

那么我们简单地描述一下这个如何解决这个问题的过程(通常我们用Alice and Bob描述)。当Alice和Bob之间需要安全地交换信息,但是第三者(中间人)威胁到他们,他可能截获消息,但是无法解密这些信息。这是TLS底层的一个基本理论,这里仅仅给你一个例子:

这里是整个密钥交换的过程:

  1. 首先,Alice和Bob生成他们各自的公钥和私钥,我们假设私钥d_A和公钥H_A = d_AG是Alice的,以及私钥d_B和公钥H_B = d_BG是Bob的。需要说明的是,Alice和Bob都使用相同的主要参数,在相同的有限域上的相同椭圆曲线的相同基点G。
  2. Alice 和Bob再不安全的网络上交换各自的公钥H_A 和H_B,中间人将会截获H_AH_B,但是无法得到d_Ad_B,除非它能够解决离散对数问题。
  3. Alice 计算S=d_A\cdot H_B(用她自己的私钥和Bob的公钥),然后Bob计算S = d_B\cdot HA(用他自己的私钥和Alice的公钥),这里需要说明的是Alice和Bob来说都是算出来的S都是相同的,因为:

    \[S = d_AH_B = d_A(d_BG) = d_B(d_AG) = d_BH_A\]

中间人虽然知道H_AH_B(当然也可能知道所有的主要参数),但是仍然无法得到共享密钥S,这被称为 Diffie-Hellman问题,它可以被如下问题描述:

给定三个点 P , aP 和bP, abP的答案是什么?
或者等价的:
给定三个整数k,k^x,k^yk^{xy}的答案是什么?
(后面的这个问题是在原始的Diffie-Hellman算法中被采用,基于模运算)
ecdh
Diffie-Hellman密钥交换,Alice和Bob能够“轻易”地计算出共享密钥,但是中间人需要解决一个“困难”的问题。
在Diffie-Hellman问题背后的理论在可汗学院有一个超棒的介绍,但这个仅仅是在模运算的体系上的介绍,(而不是在椭圆曲线上的介绍)。

椭圆曲线上的Diffie-Hellman问题被认为是一个”hard”的问题,他被认为其难度和离散对数相同,尽管没有有效的证明。我们知道的是这个问题没有办法”harder”了,因为解决这个问题相当于解决Diffie-Hellman问题。

现在,Alice和Bob已经得到对称密钥的,他们可以通过对称加密交换密钥了。

举例来说,他们可以用S的x坐标值作为AES或者3DES对称加密的密钥。这就和TLS的做法差不多,区别是TLS将x坐标加上了一些连接的标识码并做了一次hash。

接触一下ECDH

我写了另一个简单的pyhton脚本用来计算椭圆曲线上的公/私钥对和共享密钥。

不同于我们之前提到的任何例子,这和脚本用了一个标准的曲线,而不是我们前面用的在很小的域中的简单曲线。这个曲线是 secp256k1,来自SECG(the “Standards for Efficient Cryptography Group”, founded by Certicom),这和比特币数字签名用的曲线是同一个,这里是这个曲线的一些主要参数:
p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
a = 0
b = 7
x_G = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
y_G = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
h = 1
(这些值是我从OpenSSL 的源代码中找到的)

当然,你可以随意地修改脚本,改成你需要的曲线和相应的参数,但需要记住曲线需要满足素数域,和非尖锐(Weierstrass normal form)的形式,否则这个脚本将不会工作。

这个脚本虽然简单,但是却包含了所有我们前面提到的算法:点加(point addition ), double and add,ECDH,我推荐你阅读并且运行它,运行结果将如下形式:

Curve: secp256k1
Alice's private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alice's public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bob's private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342
Bob's public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a, 0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd, 0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)

短暂ECDH (Ephemeral ECDH)

你可能在有些地方看到ECDHE而不是ECDH,这里在ECDHE中的”E”代表”Ephemeral”,表示这次密钥交换是临时的而不是永久的。

ECDHE在实际中的应用也很广泛。在TLS中,客户端和服务器在连接建立的时候快速生成公私钥对。这些密钥都是经过TLS证书签名(为了授权)的,然后在双方交换。

##用ECDSA签名(Signing with ECDSA)
我们现在又有一个新的剧本:Alice 需要用她的私钥(d_A)签名一个消息,然后Bob需要用Alice的公钥(H_A)验证这个消息是否真实。除了Alice没有人能够创建一个合法的签名,但是所有的人都能够验证这个消息的真实性。

再一次地,Alice和Bob利用相同的主要参数,现在我们来研究新的算法——ECDSA,利用椭圆曲线实现的一种数字签名算法的变体。

ECDSA利用消息的hash工作,而不是消息本身。hash算法的选择取决于我们自身,但是明显地,我们需要选择一个密码学安全的hash算法消息的hash应该缩短到其bit位数和n(子群的阶)的bit位数相同,被缩短之后的hash应该是一个整数,我们用z来表示

对Alice来说这个算法主要有以下几步:
1. 选择一个随机整数k,这个整数k{1,...,n - 1 }中选择(其中 n是子群的阶)
2. 计算点P = kG(其中G是子群的基点)
3. 计算数r = x_p \mod n 其中x_p是点P的横坐标。
4. 如果r=0,从新选择一个k然后再试验一次。
5. 计算 s = k^{-1}(z + rd_A) mod n 其中d_A是Alice的私钥同时k^-1是k模nd的相反幂(where d_A is Alice’s private key and k^{−1} is the multiplicative inverse of k modulo n)
6. 如果s = 0,选择一个新的k然后再试一次。

这里的(r,s)对就是签名了。

ecdsa

Alice 用自己的私钥d_A和一个随机数k对hash进行签名。Bob利用Alice的公钥H_A验证消息的合法性。
需要强调的是,可以通过(r,s)对得到公钥。

用简洁明了的话总结,这个算法首先生成了一个密钥(k)。这个密钥隐藏到r当中了,这点是利用点乘得到的(我们知道点乘是”easy”的,但是反过来却是”困难”的)。r 通过公式s = k^{-1}(z + rd_A) \mod n同消息的摘要绑定到一起了。

再说明一下,为了计算s,我们需要计算 k \mod n的相反幂,我们在前面的文章中有做解释,只有当n是素数的时候才能够奏效。如果子群拥有一个非素数阶,ECDSA算法将不可用。几乎所有的标准曲线拥有素数阶并不是偶然,而是因为非素数阶的曲线不能够适用于ECSDA算法。

验证签名(Verifying signatures)

为了验证签名,我们需要Alice的公钥H_A,hash(被缩短)z和签名(r,s)。

  1. 计算第一个整数u_1 = s^{-1}z \mod n
  2. 计算第二个整数u_2 = s^{-1}r \mod n
  3. 计算点 P= u_1G + u_2\cdot H_A

如果式子r = x_P \mod n成立,则验签通过

算法的正确性

第一眼我们没有办法看出这个算法的正确性,所以我们把所有的等式重新分析一下,将会豁然开朗。

让我们从P = u_1G + u_2H_A开始,从公钥的定义可知,H_A = d_AG(其中d_A是 私钥)。我们可以得到:

    \[P = u_1G + u_2G \ = u_1G  + u2d_AG \ = (u_1 + u_2d_A)G\]

利用u_1u_2的定义,我们可以得到:

    \[P = (u_1 + u_2d_A)G \ = (s^{-1}z + s^{-1}rd_A)G \ = s^{-1}(z +rd_A)G\]

这里为了简洁起见我们忽略了 “mod n”,因为G生成的循环子群都拥有阶n,因此“mod n”是多余的。

之前我们定义s = k^{-1}(z + rd_A) \mod n.两边都乘以一个k并除以一个s,我们可以得到一个新的等式 k = s^{-1}(z+rd_A) \mod n.将这个结果替换到我们先前得到P的等式中,我们得到:

    \[P = s^{-1}(z + rd_A)G \ =kG\]

** 这个结果同我们在步骤2中生成签名的算法一样!当生成签名并且验证它们之时,我们都需要计算相同的点P**,并且用的是不同的公式集。这就是为什么这个算法能够work的原因。

###接触一下ECDSA
当然,我也写了一个简单的[python脚本]来演示签名的生成和验证。这个脚本有一些代码同ECDH的脚本相同,具体来说就是有关主要参数和公私钥对生成的部分。

这里是这个脚本输出的内容:

Curve: secp256k1
Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e
Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a, 0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)

Message: b'Hello!'
Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478, 0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)
Verification: signature matches

Message: b'Hi there!'
Verification: invalid signature

Message: b'Hello!'
Public key: (0xc40572bb38dec72b82b3efb1efc8552588b8774149a32e546fb703021cf3b78a, 0x8c6e5c5a9c1ea4cad778072fe955ed1c6a2a92f516f02cab57e0ba7d0765f8bb)
Verification: invalid signature

正如你看到的,这个脚本首先将消息进行签名(”Hello!”的byte串),然后验证了这个签名,然后它尝试用同一个签名和不同的消息(“Hi there”)进行验证,然后失败了。最后它用相同的消息但是采用了另一个随机的公钥进行验签,再一次失败了。

k的重要性

当生成ECDSA的签名的时候,保持密钥k的保密性是非常重要的,如果我们在所有的签名中使用相同的k,过着我们的随机数生成器是可以预测的,那么攻击者就能够到私钥!

这是sony前几年犯的一个错误,简单地说,那时候的PS3本来只能运行Sony用ECDSA算法签名的游戏,本来就算我写了一个PS3上的游戏我们没有办法将其发布,除非我得到了Sony的签名,但是这个过程的问题是,这个签名Sony是用相同的k生成的。
(Apparently, Sony’s random number generator was inspired by either XKCD or Dilbert.)

在这种情况下,我们能够轻易地通过两个签名过的游戏恢复得到Sony的私钥,我们提取出这两个游戏的hash(z_1z_2)以及他们的签名(r_1,s_1)(r_2,s_2),以及他们的主要参数:
– 首先,我们可以得到 r_1 = r_2(因为 r = x_P \mod nP = kG 对于两个签名而言是相同的)。
– 得到 s_1 - s_2 \mod n = k^{-1} (z_1 - z_2) \ mod n (这个结论是从s的公式中推出的)
– 现在在等式两边都乘以k:k(s_1 - s_2) \mod n = (z_1 - z_2) \mod n
– 两边同时除以(s_1-s_2)来得到k = (z_1 -z_2)(s_1 - s_2)-1 \mod n

最后一个等会能够让我们通过两个hash和其对应的签名计算出k,现在我们可以通过下面的共识计算出s:

    \[s = k^{-1}(z + rd_s) \mod n \Rightarrow d_s = r^{1}(sk -z) \mod n\]

就算k不是固定的但是是可预测的话,用类似的技术也能够得到私钥。

未完待续

接下来,我将会发布这个细节的第四篇文章,它将讨论如何解决离散对数问题,以及一些在椭圆曲线加密中较为重要的问题,以及ECC和RSA算法的区别,不要错过!