对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。& x% |6 ~# \# t1 l6 s
3 M: @9 \8 F( ?( l) o/ V- }
当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。/ e" U4 h4 p8 U+ t, N& Q6 W

, V9 g9 C' t2 K3 l9 z5 Z可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。
# _7 g6 m4 @8 Y* x- F. l9 i/ k0 x5 ^
所以做了点功课，来把这个问题讲清楚。7 }! a( N' J( N5 x/ f8 m
/ ?) e5 p* j& W+ v9 \
首先我们跳过ECC曲线是个啥这个话题。1 J6 m4 [5 {5 Q, x6 c# h7 r& e7 Q, b

6 y! a/ N. {; t( e4 K. a, R这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。
7 t: U1 _/ |' \( b0 {. C9 s( L% |7 n. ]* s1 @
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。* g( N+ P" ~7 S5 N" t% m
5 l2 ^: K6 D' z3 ?( K& L
只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。
& e6 ~2 N/ Z9 c9 V/ c' l/ b1 @$ N5 G* Z' R! X8 `& |$ P
ECC曲线加密核心原理
1 |* x8 H  X# Z' L; z- l( y& G/ s& S4 m, f8 b2 E
下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算( R  h$ }& }" M6 r3 x4 O$ @

5 w" \5 G# ?9 G7 ^. S. G- J设 Q 为曲线上一点
1 x. g  y8 d$ [, K& [9 d$ Y+ t+ e4 a  M+ h" F; ^, E, v8 D0 q
若点R = Q * Q，也可以记为 R=2.Q
0 }1 W3 T2 B" l. }9 ^& I% \( C
  W3 }& y( d' \9 K若点R =QQQ，可以记为 R =3.Q
  l1 h7 Q. \6 k: ^8 Z
8 D' A, n+ w3 {& F) S& h, V# p若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q
/ s5 j2 r1 B! F6 t* z9 a3 O3 g) i3 C
然后原理来了; Y% S. o+ U3 J0 }0 R9 n

# `2 I! b+ R3 C0 @给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n$ A' O7 q: j' t7 ]6 Q4 N

6 V3 i9 k; `+ V/ {. Q* h0 u; [( D* |. I就这一条原理，然后其他的都是证明出来的。
- E( C8 ^% n& l" a7 t% y* u; g8 W: l9 h+ n  {4 ^1 R( ~. {. m% B
#公钥和私钥" t% a! U. b2 G( d% E' y

; Z5 h( Q7 E& ?% x% W2 D% R6 R先复习一下原理" O" D0 \# i+ I4 c( A- P0 r
3 M2 }$ @: O4 ^6 ?! c
设Q为曲线上一点，k为一个整数
- w0 W1 M$ j: f+ f& V3 m; s
0 V4 L! i/ A) R8 |4 P令点K = k.Q，若给定 k 和 Q，很容易求出 K
' I+ ^+ Z, ]- |. J; w
: W* J0 P! x( W; L) p  E6 @若给定 K 和 Q ，很难求出k
/ V/ ^% ?) @$ a8 o$ r: {
9 u# g  S5 u* [: [我换个说法给你看$ v3 t7 w0 R. Q5 F) ~  X) z; S
* }. Z! M% }8 \1 h/ W0 z
设G为曲线上一点，k为私钥! F" I) ~. ~4 ~; {4 F2 V
& {4 O& ?) `2 j% Q+ O
令公钥K=k.G, 若给定私钥和G，很容易求出公钥
( @: Y; v5 n0 z4 d9 K( J# _1 w5 {- F, O' i8 }) ^9 O  n6 o! d
若给定公钥和G，很难求出私钥6 `, i5 s% w  j, L- K6 {
  D& \( t% t7 k/ u& e) E
是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数
* ]" G. \% ?! q) t& e* F& W% L0 @: j, d- \! d
而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）
2 }3 N9 }2 p/ {( z8 D" I) e6 q( i! l" S5 I& P; G% E
ECC曲线有很多应用，最常用的是加密解密和签名验证
3 S- _8 ~7 s. u0 I8 i9 H' `0 z5 @# Z4 n! U: D7 j" ]
#加密原理$ ~% o! g3 N" I" ^! P: N# C

- w  A. I3 I6 G  B加密步骤
4 X  |( y9 O/ m: n8 a" }' s4 U  K/ T  M9 B
先设 K=k.G，（公钥=约定点G阶乘私钥）。. z2 C9 }  d% |$ [
: r3 h+ U9 h* i4 T1 j
欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）) H0 k, W: n* @% Q
# B2 Y* B8 G: V1 }$ _
整个随机整数r, j( p8 \* A- Z% j9 S; i

( m8 [9 f5 ?; t计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M; F9 P9 `3 }6 y- _3 }5 y' F4 f

1 r  `+ ^" [1 L+ n& P2 H2 j% R计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数
' q1 h# X9 f7 m( ^9 v3 F* F& R+ B2 [
加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点
- A9 `* x9 l6 h" L$ x2 V) D* w) c' f* l4 e% x5 O
加密者只需发送C1 C2 给对方% |; {- Q; h! {) D/ g! \$ r
) ^  _0 ~+ {$ f- W% g
解密步骤+ Z- U, d; N  A( K! Z2 ?% K

0 N. @4 y9 _4 j! \, K- `+ `+ B, ]  G由C1=M+r.K 可知 M =C1-r.K
( t) z% p$ u" [+ H9 J% U7 c1 e4 j1 H+ |; L5 l, P
由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G+ V# q$ y0 ]1 R3 l
/ a" o  ~, r; [6 S
由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2
! Z% P2 X8 \7 h3 n4 |
9 ?( J5 h& [" d据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M
4 D; `# Q6 J3 L8 N# q0 A+ D
8 j0 S% ?' b1 c' i+ w#签名验证原理- Z% E6 l0 n. r" W5 Y7 y

  a, H& f# W4 X3 s6 P. _签名步骤0 [. X" K3 }* H

+ @5 n9 T! t+ D/ _5 D) `先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥
# @' E3 P2 m7 z2 z& o/ I/ T# A1 t8 J
对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e1 I, b" {' i0 J1 k) A6 v) `, Q) i
5 V. ]( |" E! E# d4 d
整个随机整数r
* u& _! {5 Y0 a+ H
% t, `( s  k1 w8 r" d. g计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。0 ]% |+ @4 G/ l) `9 Q! ~

* {% p" ]2 @5 N. P( G, O签名完成
. ]& o9 Y1 W) T6 G" b* m
& q' X9 c: t4 P- V5 ^* \通常说签名（signdata）就是指s和r两个整数。8 c: K- j& M- a" y

- g1 n1 M& X3 h4 s% _' e签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。* ~' C# H( q& \% c* E" F
( S3 @" z+ k8 p0 _& |! R
验签步骤，验签用公钥
0 ?3 ]6 h8 I9 b
) P. G0 h& D; ~. U" B: ]7 L对欲签名数据进行处理 e=hash(m)* g5 B& J% x9 C- i$ O

2 q5 T5 q1 P6 o; [& `# B5 \计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）7 t5 }, z) Q# N2 a* O& S

' Y% u& a) ~! n( @) T4 p; C计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )
) J- t4 W2 q* q( F- h; J" H8 w5 ?0 C1 J; R, w# W
若V1=V2 则验签成功，接下来证明
* K8 a0 s$ o* _+ \
. s& I9 T" k* ?- W! j若数据都是对的，则s =r-e*k成立9 ~+ Z( r( D+ j0 T# k

9 Z$ Z  o2 ^2 \7 y% R此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K
% f& A, N: }1 Z; X. p
0 j; t; `6 B' H* KV2 =r.G-e.k.G+e.K6 W8 Z, G! @: G& N6 J5 \9 e* a8 N& R

  [+ t" E9 @* X) q) J; l$ u因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K( y+ G- P4 l9 Q) h% P: x
( o! d/ x& ]- {+ E) Q6 ]8 @
上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
5 u& y0 f1 j" a9 s* l; D+ n. a6 w) k/ m0 v3 z, @+ i7 l; k& c
反之，当V1=V2时，s=r-e*k成立，数据正确