对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。( E( \% V" x* g% Y

1 _0 u2 Y2 g# K/ b. f& [* M当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。6 T3 o+ M6 O# D' L# C$ z
3 w  B8 ?/ c2 e# B& z1 m. \$ ?1 I
可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。
4 x; ?% ]( Z6 l0 [4 r
, s9 _3 Z! d4 {0 |所以做了点功课，来把这个问题讲清楚。
  P. d7 Z1 S. L! t3 h+ K9 I4 Y+ p% k0 C" X3 R% Y% \
首先我们跳过ECC曲线是个啥这个话题。! ~3 Z$ Z. j- i9 n- B" F) K
1 `: n" F1 M' r5 C8 i) P, a: @" D
这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。5 i+ O( U$ P) p& N! l6 h

/ G. |& i, u( \' v( j; c因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。
6 H" T. y' ^$ x0 W( F3 A3 U
. J; h/ Z! b( V3 }% ?只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。7 L! W0 Y+ i: z8 N

# Y1 m# d3 M  PECC曲线加密核心原理  `) N% Q: \: j7 a: V' U
, p! u3 t4 A, F- R% O! v4 R( G
下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算
0 s1 Z# T3 r! I; P% D
0 x) `* o) J0 q0 |, g+ a设 Q 为曲线上一点
; [2 m$ B7 x, g3 c2 N/ M- S% i; t
若点R = Q * Q，也可以记为 R=2.Q& g- b! F) \; T. }1 Q" A) n
$ a; m8 W3 r# c
若点R =QQQ，可以记为 R =3.Q/ N' k3 ^3 n% A/ d: |
7 A( Y# h' g0 g$ F8 ^$ R. ?1 K: v
若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q; U  N5 {/ b5 e* Z
2 e% r8 j+ }9 O$ R
然后原理来了& X* X% A5 K8 q3 Q$ T7 Y' W" X
: E$ T4 F3 d# j! G" B
给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n
. q6 I3 E& E& J, ^% Z9 B6 M4 Z2 |6 G3 S5 O
就这一条原理，然后其他的都是证明出来的。& i# |: S! N2 m

* o" w* L) @' d) h+ P) c#公钥和私钥' {, r  t$ v/ s1 K
/ D5 d# f1 D& f5 U/ a) c
先复习一下原理
2 i! h# X0 x( X; W  ^: {# ]8 r+ P* _; C/ ^3 Y. N
设Q为曲线上一点，k为一个整数5 a- k1 e" a. c9 B/ F' P) R
' z- W/ E1 S4 {+ i+ C8 ~5 _. g5 L. Z
令点K = k.Q，若给定 k 和 Q，很容易求出 K% @8 L5 x3 c- d( K! ^& ^$ z
9 l% Q. `: o" W4 o) h  l# C
若给定 K 和 Q ，很难求出k8 z) _) Y4 [* y3 C

3 P8 p; J) Z9 r5 p我换个说法给你看
- c0 x% H8 F4 j7 {" ^2 u! \* H* @) O) S' @' U( _: Z7 h5 S
设G为曲线上一点，k为私钥( m3 u5 F& }$ v# Z
8 a# V6 I+ g4 h6 H" c
令公钥K=k.G, 若给定私钥和G，很容易求出公钥$ W- T8 U$ K( t' L6 h5 R
; w# k- F! G: f9 s. A1 m$ l7 ~
若给定公钥和G，很难求出私钥! N* [, i% f% r! u4 u, F- U8 m" t  n
$ U$ \9 [/ n' H  d* b
是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数  `; j# l  P1 ]  [
5 x( Q% v) r: W9 T! p! S& R2 `
而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）
2 a) B* E- M9 ^" U9 I
2 q" K; s4 u* g2 ]: ?ECC曲线有很多应用，最常用的是加密解密和签名验证
9 {. {: d) a5 M7 A4 F0 I! M7 q7 y0 J1 E1 m8 X- S) b2 N
#加密原理
- i$ p' c' |$ @. z* G4 j) A+ A% W  g
加密步骤" ]* w) g+ Y7 |) h! W

& c3 W6 h& t/ z1 M  V& F7 z  _先设 K=k.G，（公钥=约定点G阶乘私钥）。# M8 V. M# v# l& C9 K0 F

: A, |# r% h, u) P! ~8 V8 d/ y欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）2 g- q7 D, B8 O% }  O" G0 l: w/ e; N

. j+ H% j: _& `* B整个随机整数r. [3 g% ?! c; V$ g/ @6 \8 z" k
, ?  j( a5 U8 H3 i
计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M# q- `) p0 ^2 v5 e
  z; b, a+ }! {1 H6 t
计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数, t1 e7 t; V6 k. c
4 Y% X- L; ?+ ]1 m5 l6 \! d" }0 q
加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点1 V. C# w6 w/ w3 I6 ?6 x

/ A; r0 n0 N7 a5 z' V; L2 T加密者只需发送C1 C2 给对方
1 d0 s0 P9 X% W, p0 v3 ^1 u4 z+ M
. v( m7 G4 G: |0 ~4 g  S解密步骤) M7 g0 m# s/ M: J8 @
  Y( y( s! d: u  [9 N
由C1=M+r.K 可知 M =C1-r.K
5 {7 l9 M! ]5 `1 _2 e
- o$ m# b+ l6 h7 ~) `6 Z由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G; I  ?3 R. n: F- \
9 f. Q+ y, a' M* t1 J7 y- ]$ v1 q
由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2
6 J# m: X; b% x& @. [, @8 o) N6 d' c* W& B- h* z6 c
据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M  ?4 K" |$ j, I. i8 U

/ G% Q4 d  @- t& Y) m* O# X) m#签名验证原理3 r1 y5 L: @- [5 A0 c. T
" T7 ~0 [! R# c% ?  T
签名步骤
* l2 s1 {$ ]$ \1 `+ J: C! t3 Y" M& Z) z4 r7 q- c# N
先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥
. T+ w1 }. O6 W# H
3 P* A0 b% p- c对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e5 _+ M2 j4 ?0 K' _

1 I2 Y/ O" `* B* i$ c' ~. Z整个随机整数r- |0 M/ G+ w1 o6 R
7 A) Y4 M' D0 \0 g4 R6 N
计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。
9 s8 c, a+ g) o* N- c) `
, l2 l3 L6 ~! [, h9 k, \3 _, Z, ^  x签名完成
3 D# ^: t& d1 }, Y+ P8 h' w4 Q9 y
9 Q" V  n, B7 w0 W  w# X通常说签名（signdata）就是指s和r两个整数。& t: A$ @  T, \! ^
+ @1 \; w3 ~8 G* a) Q
签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。% g6 a2 Q) E6 X, D" F+ M' u  _
( A5 [5 G- V, a* R/ G8 @6 F
验签步骤，验签用公钥
$ h) K( B  \/ Y- d) N( {9 r8 x1 x- c% q8 ?
对欲签名数据进行处理 e=hash(m)
+ O) d  a8 i8 N& @3 z* N+ ?# A4 x( K* X, C2 Z8 S* U( [) P  N  N
计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
+ {( y  I- W/ R5 y3 ~% t. g& v( s$ c4 Y0 {
计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )/ b4 d) v+ Y0 ?7 a& e( o

2 s/ X: y9 R& n7 L若V1=V2 则验签成功，接下来证明4 V- \1 H% d0 U/ C0 j+ ^  y6 j  z) x

  L+ w  ]1 X8 f/ t2 ]# d若数据都是对的，则s =r-e*k成立
: T9 z) r5 @4 a/ Z& j0 E9 R5 _" x" W5 y! \$ r- p
此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K, e: P3 s: r4 W0 c  U4 I

* Q; }/ i; D5 u; sV2 =r.G-e.k.G+e.K
) Z( r0 y! z' L$ r7 F  y. q6 }& g5 u' j. i: ~4 U( [3 d6 K6 m/ q$ u
因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K& J/ m; p% }5 Q1 k+ [

0 D& Z* V9 n  R5 b8 D上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
1 q+ A* J) \. _( j
) p  n- A8 P; E& ~反之，当V1=V2时，s=r-e*k成立，数据正确