对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。7 n& I, p) {/ l- Y( s
( V* O6 ], n4 }  K
当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。
0 B8 ?/ c% a" [
+ C* `6 j. D7 s- `可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。( r1 B' U! E  \$ G
6 ^- U5 ?, b# A* J
所以做了点功课，来把这个问题讲清楚。! y  Y5 M* Y2 r# a- s7 n

1 R( k: d( G4 ]首先我们跳过ECC曲线是个啥这个话题。
( K9 e- ]' Y0 r3 ]) D4 n2 v( i( e
这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。+ _5 H, \9 l& q8 C0 p4 }6 P+ W  Q

/ _$ S$ X! f1 f- Q; \5 ?因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。3 U4 R% \0 m/ r) {
: [; f( h9 |! K, M3 ]% W; n/ u
只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。- k, Y# G- Y' ^4 R7 t' J# O0 i1 ~

  E1 l# J0 A( G- |+ z8 ~ECC曲线加密核心原理$ }; ~  C: }8 g+ G
& F% P; h0 H% \3 q. t9 P9 p
下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算
% ~9 g6 G7 U. c) z
$ l8 B7 i1 I- j' j1 Q设 Q 为曲线上一点- x7 e! \; h( V7 L0 e$ a! \) H

+ X9 w) g4 Z3 H7 r& g& m; b$ G" l9 T# g若点R = Q * Q，也可以记为 R=2.Q
5 y$ H: W, Q; K9 I* N. `
! T7 ?5 i7 F- B1 R* }若点R =QQQ，可以记为 R =3.Q* l: L! W, K% p1 y& j4 T. B

9 g- K) E/ a5 f1 O若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q
' K3 X3 n" `$ |
1 t4 Z7 |; r- }4 Y) X" B然后原理来了
1 \/ }; x1 u9 x: S0 e& u8 G& |) S. d* T! E9 V& r
给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n- X4 ~2 G+ X3 ^/ t  u9 {
5 u' B  E6 f# F  }  t
就这一条原理，然后其他的都是证明出来的。
, d, a) f0 Y$ a9 T  s- d  h, @$ r7 M
#公钥和私钥3 |; ^6 `+ D6 U7 R, a$ G2 Y& q
6 y  w; O* _9 ^  f8 S! n9 ?* t0 C
先复习一下原理1 q, {( j. v) O! C( Q5 e  r

4 E( t4 S8 p3 I& [* M& J设Q为曲线上一点，k为一个整数! x( v8 Q1 |, K

; f6 J) V$ g6 j5 N( Y令点K = k.Q，若给定 k 和 Q，很容易求出 K. K' Z5 B5 i7 V: @/ X& \" W' z

8 }& E. D  R) |( |. x! J4 K若给定 K 和 Q ，很难求出k
7 B+ g- v: U& d+ \  K
. X3 ~% x" S7 ?( m& A我换个说法给你看( {& B% H, r+ b# ?. r7 N: r; s

9 \2 J  n) P1 E* }1 p3 [+ ]设G为曲线上一点，k为私钥
! A1 M; @" ]% b) k4 }4 t/ v% t) o% c  H  E" R4 Q2 U% U4 W
令公钥K=k.G, 若给定私钥和G，很容易求出公钥4 ~& A% B. P) r1 k; ?

( V. @3 C- @9 T3 N若给定公钥和G，很难求出私钥
  I" {) z: m* `% I, v. l) B- b! V9 K2 b+ I4 W1 ?4 O+ M
是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数
& O0 T+ L% V2 N9 u  k, m* |
% _  a( a2 s2 q. q4 s8 A而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）
3 r* s1 g. Q- [% F6 L% y. k4 J9 x& j
1 w- ~7 D- ?% m0 J$ Z( O. jECC曲线有很多应用，最常用的是加密解密和签名验证
" e* m" [4 ]5 p5 h  w- b' P9 ]% N
) }0 U9 P2 S7 Y#加密原理
0 s" ~6 n' b- K  f% V9 R- }6 R- y6 G
7 g9 w4 I0 H4 R; ?, @加密步骤
" {& K- ~. I. p! O* R1 d( T- W2 O: q4 ~5 _( b3 Q; o( _
先设 K=k.G，（公钥=约定点G阶乘私钥）。
- J5 D6 {1 w+ J$ w9 g3 }. k! n# T0 ~" F( v. G  ~
欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）* u" [4 r3 u* ^. X  ^3 ]
8 |9 |# a" F- K! ^6 r
整个随机整数r# D  y9 `0 V  I" z

  }& i$ z$ a( Q; r0 O. P计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M
3 v3 J0 k, I1 v& B5 Z1 \% t- w, N- `3 W2 ?" G/ b7 `3 M, {' k
计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数
3 l, K9 ^: H# r+ F
3 n7 b0 Y: F" y加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点: C7 ^  }7 z- n4 v

; g: e' o- q6 L' [加密者只需发送C1 C2 给对方' c' Y; ~; K3 c  h: l' c
% D6 O0 M: p! K. \7 _! r
解密步骤
; P. p- _0 R/ e
! Q# Y6 e" }2 p2 r/ Z由C1=M+r.K 可知 M =C1-r.K, i2 s. J7 V: o, H

  f: @) O, B! D( @由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G
4 F# A7 P' g: h7 `
, q. ?  B9 U. c$ O9 m由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2) f1 l- o' |# s; `  {3 O& }1 t

- x: ?9 u' N3 l) F2 X9 ?据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M
, w: |2 R, |: C3 J
' @/ o" n3 ]: ^1 Y#签名验证原理2 L/ i0 ]# @  B+ U
) s' C( I9 `& A6 Z, f
签名步骤& M- g  V: [7 R& P" [
. r/ j3 M( U8 Z% v7 y5 W
先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥
  z# U& Q8 _* B4 q0 G9 M( t0 @2 S) w( U* |0 K$ Q( m  f
对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e- {5 [% X9 ?: z! F
- B, h) H; f. D3 ?4 N% R, ~
整个随机整数r: E2 s- E2 J' B( F
! D6 a; j, r. [0 h; v
计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。
1 C, x9 g( V! b( l: k1 q/ ^+ K; n( e& i
签名完成3 Y' n# b( ^/ @9 k& [

! a* S! C$ c" ^# ^' G$ b通常说签名（signdata）就是指s和r两个整数。# X) F. t' k* M

9 v- ~) W7 J& J! r# E" m" [0 [签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。
' q' O% i0 |8 p$ l; D
, G3 j; ^$ S9 A3 p% F验签步骤，验签用公钥
% p. `- S  z* d7 y& Y( |$ ^( X0 v' b
  q3 ?# W9 m# ^对欲签名数据进行处理 e=hash(m)) o3 d. K- f. G/ j1 B3 G# ~
' c+ @  l' ]. Y* g! g3 t
计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
( w. d0 g3 H( q# A, {9 t4 H2 G
计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 ): u8 s% R/ v" u  u
6 ^& Z' A. A* H, b# y0 q* W
若V1=V2 则验签成功，接下来证明
$ x! N9 L+ I* S0 g) [- Z) p; l+ Q+ C; J6 v
若数据都是对的，则s =r-e*k成立
8 H* g3 G: ?' t" N
7 @6 G' q& P0 N5 f此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K- c/ l! P% _- I# P$ I# L
5 i) d; G% D6 y9 m
V2 =r.G-e.k.G+e.K1 B! u' Q* z! i4 z9 x

( Z4 X, p) j0 J; O因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K2 Z) J! s5 X2 D; s7 p% x

1 K) h0 _# f4 q1 D" {# o/ y, s上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
  S6 }* R7 x' `& ?: g* f
2 u3 x/ ?5 }0 H反之，当V1=V2时，s=r-e*k成立，数据正确