对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。
& k( i: u' N% e
5 Z2 j1 Q# l: @4 w( R; E当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。/ x+ H$ S/ V7 C- w1 T  R
5 i' l) }  q. _" P, ?. I! ^& u: h
可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。$ @% }5 w0 @2 d7 }; Z2 Q

" N5 H6 r+ C+ Y4 Y: O+ Z: ^所以做了点功课，来把这个问题讲清楚。
2 R% m# q3 @, [. c' }5 S1 G0 V+ K; z
首先我们跳过ECC曲线是个啥这个话题。$ X0 z4 }3 l+ \" r% G* H: A

% q6 x/ K" Y+ @6 m" l! Y这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。
$ D9 m1 A6 T, ~: g6 }+ [, ~/ t# R. n  B8 d3 v
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。  G) [; ]* |. m# ?; M, @
. H% J, f  q9 X7 a0 w
只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。' N8 U, H/ R6 t" U' A+ V' q
: r3 o" I9 C" j- f' t3 v: H
ECC曲线加密核心原理4 K6 h4 r# |2 W& ~$ M

1 C# `1 `1 N6 c7 _下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算# N" N, C) |0 E, A4 [: U- U7 ?, u
% _8 S! @4 |: X' D6 V. H
设 Q 为曲线上一点
1 k4 B$ @( X9 v, P, h5 d
' Y9 v7 z- c( v* ~3 O若点R = Q * Q，也可以记为 R=2.Q
! L4 r1 }3 s/ Z) r; q5 X% V# W3 M% t, Y6 d5 `3 E5 F. `2 Z
若点R =QQQ，可以记为 R =3.Q
8 P9 ^$ I# z% \+ L* q3 G) O1 i7 z# M
" I" S$ w/ g6 z; |% [. R若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q
- ]. D# i) X4 ^# g- e  Z) p2 R+ t# k, s# k5 X; N
然后原理来了  U- Y" U' H- u4 {

! o. s9 l0 s2 y9 h给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n
: L( c& c& A+ I, _- ^! B& Y% V* r: I  ~& ], m& F: Y& u: r
就这一条原理，然后其他的都是证明出来的。
+ K) p. l. ]1 g- z/ c3 X/ |; L4 z$ b/ N. a: P% ~- w* l
#公钥和私钥5 O$ P  d) B$ N5 @

( D" q8 }% C& l# r, N5 r$ R! i先复习一下原理
5 T9 }: J4 N- n( M' V
) \7 \$ Z1 v) X/ z) M, v设Q为曲线上一点，k为一个整数
4 h: c( ?9 W* B/ Q  _) b* V3 ^/ L1 q
3 G& e- V) z+ n0 i9 f令点K = k.Q，若给定 k 和 Q，很容易求出 K
: A7 G1 I! M- k! u
- Q, a1 J2 `8 s+ T若给定 K 和 Q ，很难求出k
; R2 X2 U, V3 A& S+ K% N; G& y5 K, W) W6 R/ p( W
我换个说法给你看
$ Q* ^7 V8 A& S2 o( B& v" B  b: y: j% U& Z. j
设G为曲线上一点，k为私钥, {" V% J! D0 ^7 r
6 F, ?& p: E" ]9 N$ w$ Y
令公钥K=k.G, 若给定私钥和G，很容易求出公钥( m: Z7 K8 ?) z8 G  Y; a+ G  b0 a% ?
. q+ }8 E( y7 c3 [3 q  _: U3 R
若给定公钥和G，很难求出私钥
/ i8 V! P0 C, G- i5 L  R
8 Y' }/ q- b; i/ n9 p- c是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数8 y1 u2 E9 t2 m0 X- w, t$ w3 w

6 s8 E1 }0 \3 o6 y而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）/ [( |  o0 h# W0 V  \3 n
: q- H2 U8 ~9 M7 E9 x' y  l
ECC曲线有很多应用，最常用的是加密解密和签名验证
: }$ t3 T1 Y0 u, p
2 G. r. K# S  g' T0 `- Y#加密原理% D. z# s- i) T9 Q

3 T+ z- D1 L1 g加密步骤
& K& D3 h3 [2 \/ z5 H" a
: h# {+ ]: |5 o4 J9 E4 H先设 K=k.G，（公钥=约定点G阶乘私钥）。  [2 D1 q: i4 b1 ?  H/ _
5 F2 Y: I4 m* y+ S. x& T9 N
欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）' K2 l! r' d2 J1 w, w: o9 H
" z; ^- \! @! Q2 h* Q0 y! `
整个随机整数r5 ^! m8 F1 s4 |" \
- t3 S! q# J4 N- S' X
计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M8 Q& _2 x7 P! \

- c3 T  k0 L) i计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数- K6 S  \+ c! D" f
7 H0 e; Z9 `& {" _; a, i! ?! s0 b& a
加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点- S, U& T$ L8 X* A$ I

; Y) y! G4 _3 |: S加密者只需发送C1 C2 给对方+ T% e2 y" }' {5 H3 i$ U3 o
6 n' M0 ]- E5 y/ ?! \
解密步骤4 c! J1 t- U2 h2 Z1 I: S0 _2 u( N

( J- l( Z9 F% D! \- r, G由C1=M+r.K 可知 M =C1-r.K5 h. l, D8 A5 F5 o4 ~1 @

* j# M( t' N7 m; u, n由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G3 M: U4 H5 L) W) i' L4 K& {* r

5 ~3 E8 K# A  U2 p- T/ {4 F' G) E. u由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2: C, K) Y+ M1 _" C% M
( D! E8 A& `* q/ B" a2 S
据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M
3 Y0 d$ x9 M9 d# J* z* ?/ M! v
& }- }5 Q2 I6 \5 P2 X#签名验证原理/ `7 i0 I; e3 ^* Y/ T0 |& S

2 t. o( h% \" U( C, p( O4 }签名步骤
& V, d& u6 ~) i& Z- U8 n
1 g* f% l" `2 g" h7 \先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥+ N: S% x0 o  @0 S4 j
2 a9 k: V; ]4 D
对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e
  ?( x) \, W8 P5 L/ W  K8 X) a+ ^! c; h" E' m1 E
整个随机整数r# \9 q/ S5 S5 [. T" {. f
8 W& P/ q5 k# Y  Q8 M1 c4 K6 z
计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。$ s+ c  ^  ?& Y. A1 b5 o

# F6 i; |* ^1 G签名完成3 }5 u7 O' l& E- k

* g+ B/ |: v( z2 c通常说签名（signdata）就是指s和r两个整数。
) l% g; H: @, H6 Q! R+ c# d# u, R, M
) N9 l" m/ h( s  e# b, i, ^7 C签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。
0 \7 q$ s& p8 k4 ^" l2 b& G- p: c. Y" `% {- m1 t! [
验签步骤，验签用公钥
4 W" t8 K: K1 R! h6 H1 @; Z- }( |. ^0 g9 c( L4 V' L  T
对欲签名数据进行处理 e=hash(m)1 c1 @7 k8 i0 I

' Y9 @/ D0 }7 N6 J9 ?" C计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
1 i2 D' [0 b; P) `7 i0 D
/ g; W6 d1 ^. p* Z! Q  G* D计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )
! ^& s$ u+ h' b/ z. J
/ r. S7 W& u3 J* }. [+ p若V1=V2 则验签成功，接下来证明$ F+ B8 |5 E$ i: v& ?6 @# |2 B
0 C* }+ D/ |, l  O1 U( c
若数据都是对的，则s =r-e*k成立
" ?, B; ]' {' T0 ?9 {# E
* y6 Q. Y6 L8 V6 R6 I; t此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K
* D4 g" d/ V% F2 F* b/ P4 o
* g1 o. F: c" [) BV2 =r.G-e.k.G+e.K
5 j* a; [+ z% Y/ z9 f8 D
$ w0 J) t* ^# v& t/ \+ u因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K
* ?/ U) K/ z9 q* ?$ D8 N( U/ |% y$ P/ O
上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
( e6 b" Y' T% O: S7 i
. c1 E) z' Q: r2 j反之，当V1=V2时，s=r-e*k成立，数据正确