FLEXLM ECC问答 (3)
说明： 本篇讲述ECDSA的一般原理， 与flexlm没有任何关系。但是flexlm ecc算法上属于ECDSA。理解了ECDSA就理解了flexlm ecc的基本原理。
11. ECDSA的一些参考读物？
前面说到，flexlm ecc的签名算法是ECDSA(The Elliptic Curve Digital Signature Algorithm). ECDSA 已经成为世界标准。ECDSA was accepted in 1999 as an ANSI standard, and was accepted in 2000 as IEEE and NIST standards. It was also accepted in 1998 as an ISO standard.
ECDSA是一个比较复杂的数字签名算法。其详细内容不是三言两语能说完的。
详细内容可以
《SEC 1: Elliptic Curve Cryptography》，Certicom Corp.，2000
《IEEE P1363a 》，2001
ECDSA并不是一个从无到有的构思。它的思想来自于DSA（Digital Signature Algorithm），是把DSA推广到椭圆曲线上。
从这个角度讲，叫它DSAEC(Digital Signature Algorithm over Elliptic Curve )未尝不可。
DSA的主要思想来自于离散对数问题（DLP， Discrete Logarithm Problem）。 把DLP推广到椭圆曲线上，就成为ECDLP。
离散对数问题与因子分解（Integer Factorization Problem）问题是公钥密码学中两个典型的难题。
因子分解问题产出了RSA，Rabin等公钥加密、签名算法；离散对数问题产生了DSS/DSA，ElGamal等公钥加密、签名算法。
在椭圆曲线上，离散对数模型大放光彩，产生了ECDSA，ECNR，ECElGamal等一大批算法。
椭圆曲线比常见的数学问题要复杂，因为它需要一些初等数论的知识作为铺垫。大学低年级的普通数学基础是必须的。如果忘光了，还得重新翻翻教材。有些人可能学习几个月就能够理解椭圆曲线，那已经是相当不错的了。
在理解ECDSA之前，需要理解离散对数和椭圆曲线这两个东西。这里面内容太多了，有许多未知的东西。我的文章没有可能比教材写得更清晰易懂，也没有可能写得那么严谨。
11.1
离散对数本身的内容很多，常见的密码学教材中都有介绍。
11.2
椭圆曲线也是一个复杂的数学对象。它不是椭圆，它是由Weierstrass方程来描述的一类曲线，
具体是否牵涉到椭圆周长积分，我已经记不得了。椭圆周长积分不是初等函数，是无穷级数。
密码学里的椭圆曲线，跟几何上的椭圆和曲线完全不相同。
这里的椭圆曲线更特殊一些，它是一个有限域，每一个点 G（x，y）都是一个整数点。
一条椭圆曲线上的点数是确定的。
12. 请给出一条椭圆曲线上做ECDSA的例子？
12.1 描述一条Fp上的椭圆曲线的六个参量
密码学中，描述一条Fp上的椭圆曲线，常用到六个参量：
(p,a,b,G,n,h)。
p， a，b 用来确定一条椭圆曲线的方程，
G为基点，口头上也叫G点，或者 (Base point)，
n为点G的阶(Order)，也可以叫模或者周期，
h = E/n, 叫co-factor。 其中E是椭圆曲线上所有点的个数.
我们用乘法来表示椭圆曲线上点的倍加，那么，能找到一个n，
对于任何一个点G(x,y), n * G = 0 因此， 它具有循环的性质。
这个循环周期就是n。
对于密码学的应用上，为了抵御Pohlig-Hellman攻击（利用中国剩余定理），
采用的椭圆曲线有严格的限制。它要求E具有一个大素数因子，或者E本身就是素数。
有一个算法Schoof-Elkies-Atkin 用来计算椭圆曲线的点数E(Fp)。
需要用到中国剩余定理，具体的算法比较复杂。
n = E/h , h称之为co-factor.
常见的h=1 或者h=2.
E为什么不是一个参量？ 因为E可以由P,A,B计算出来的。计算完毕以后，E就没用了。
有用的是n， 而且E=h*n是一目了然的事。
附：一段题外话，关于中国剩余定理
Pohlig-Hellman算法和Schoof-Elkies-Atkin算法都要用到初等到数论里一个重要的定理，
也就是一次同余方程组的解法定理。称为中国剩余定理(CRT， Chinese Remainder Thereom)。
或称孙子定理，在数学史上，这个发现归根于中国古代的数学家们。
在这个帝国，两千年来文科生治国，数学毫无地位，剩余定理的发现很了不起。
类似于勾股定理一样，中国古代数学家发现此定理，但并没有严格的证明剩余定理。
剩余定理最早见于《孙子算经》，成书于约公元300年-400年，作者生平都无法考证了。
南宋数学家秦九韶编写《算术九章》，总结出“大衍求一术”。
和秦九韶同时代的意大利数学家裴波那契（1170—1250），他在《算法之书》中给出了
两个一次同余问题，但是没有一般的算法。相当于《孙子算经》的水准。
德国大数学家高斯（1777—1855）于公元1801年给出了剩余定理的严格证明。
中国古代的数学书里，剩余定理只有最简单的应用，相当于小学数学奥赛里面的模同余问题。
剩余定理在数论里用的比较多，初等数论教科书基本上都会提到她。
很多密码学库都有一个单独的crt.cpp,crt.c。
12.2 以NIST-P192为例， 讲述ECDSA
我们以NIST-P192 , GF (p-192)这条椭圆曲线来说，这是NIST推荐的一条曲线。
这是最简单的一类椭圆曲线。称之为GF(p)，P是一个素数。
GF(2^m)曲线更复杂，不再举例。
曲线方程：y^2 = x^3 + A*x + B (mod P)
这里：
A = -3
B = 64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1
P = ( 2^192 - 2^64 - 1 )
= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
P是一个素数。
对于NIST-P192，
E = FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
h = 1
n = FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
n是一个素数。
下面用公式简单描述一下ECDSA签名和验证的步骤：
大写字母代表椭圆曲线上的点 Point(x,y)， 小写字母代表一个数。
注意：这里的乘法是椭圆曲线上点的倍加；除法是整数的模逆运算，可用欧几里得算法。
mod是整数求余。
(1) 签名, Sign：
G为基点。h为要签名的hash。私钥为d。 公钥R = d*G（签名时只用到私钥）。
取随机数k , k是一个密码学意义上的随机数，范围在(1, n)。
r = k * G mod n ... (1)
s = (h + rd)/k mod n ... (2)
(2) 验证, Verify:
G为基点， r, s为签名， h为要验证的hash。 公钥为R。（验证时只用到公钥）
u = h/s
w = r/s
v = u * G + w * R mod n
验证(v == r)。
证明，为什么签名可以被验证？ 我们参照DSA的证明。可得:
v = u *G + w *R = (h/s) *G + (r/s) * ( d *G)
= (h/s + rd/s) *G
= ((h + rd)/s) *G
从（2） 得出， k*s = (h + rd) mod n => k = (h + rd)/s
从而 v = k *G， 所以签名和验证能一一对应上。
为什么说它安全：
由于 R = d*G是一个椭圆曲线离散对数问题，无法直接求的私钥x；
由于 r = k*G也是一个椭圆曲线离散对数问题，所以随机数k是也没有办法恢复的。
也就是说，在未知x或者k， 无法给出以下方程的一个解(r, s)：
h/s *G + r/s *R = r mod n
如果给出一个解，则表示， sign (r,s)可以被伪造。
这里面，对hash的强度也是有要求的。最基本的要求是sha 160 bit的hash。
严谨的证明， 见《IEEE P1363a 》等文档。
例子, NIST-P192 签名。
y^2 = x^3 - 3x + 64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1 mod FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
n=FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
G(x,y):
Gx=188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012
Gy=07192B95FFC8DA78631011ED6B24CDD573F977A11E794811
取
d=16fdbb3f3e4d7d253c421ae5a09f1ce500d973c04ae91564
那么公钥
R(x,y) = d * G(x,y)
Rx=2B443533CFBECB00ABE1F9D0F3A8FFD871EFDDAB4FF93B0C
Ry=6EFF3D69042B58F7C726BDB6B495AE75BD09D762259013DB
签名 "123".
h = hash(sha-160)=40bd001563085fc35165329ea1ff5c5ecbdbbeef
取
k=CADDC27FEFC3040C1CCA194542218E002F58D504A639B668
得
Sign(用ECCTool计算):
sig.r=5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4
sig.s=C0DFFC8E4BA4A91EBFFBCE7FE07E202AAF567DC10D69D5E8
Verify (用ECCTool 和 BigIntCal计算):
u = h/s mod n = BBBBED787373E2407BA720D7851CE0895222B5B5DF81BECB
w = r/s mod n = 2BBC84EA2E318FC5666B50CEE41845F3EB1DF40C838FA86C
V(x,y) = u *G + w *R mod n =
V.x = 5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4
V.y = 70360EEEC1C42D5AC10226B8BE0EA507E3FF54290737B02C
So,
v = V mod n = 5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4
v==r 验证完毕。
打个最简单的比方，如果有一个软件，采用NIST-P192 ECDSA验证，其算法逻辑为：
sign = ecdsa(sha-160（name)）， 并且它的公钥，私钥如上所描述：
那么：
name:
123
sn:
5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4
C0DFFC8E4BA4A91EBFFBCE7FE07E202AAF567DC10D69D5E8
就是一对可用的注册码。
mybase的算法是标准ECDSA( GF (2^233)，跟这个很相似。只是曲线不同，私钥不同。
如果你理解了ECDSA，那么，写mybase的kg是很容易的事情了。
当然，它的私钥不是那么好计算的。 你可能需要几年的功底。