对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。+ l* }8 t7 x9 U  }" G2 ?" G- v
2 y7 \2 c: N, ?4 v9 r' Y  O0 d
当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。
4 P( J3 Z$ l/ J' k9 `1 G" I" J1 E7 A% j8 \2 q
可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。
8 ^3 [) W+ V9 j3 s
% t" W, C/ `4 K# p! b所以做了点功课，来把这个问题讲清楚。" m# ?4 P, p2 _& @4 C3 G% k0 g

, ~- J: s, e; N" ]首先我们跳过ECC曲线是个啥这个话题。$ ]! z# q$ O  P+ X

- W7 z6 ?# W* ^% X这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。7 k, d- A* e0 x! B9 O# w
/ H7 C1 Y: j1 f. V0 g. F5 a
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。
9 V+ \3 i) Z8 e7 f, R- E  q/ p8 \0 F! B  C4 x( h% e" P
只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。3 N5 {+ Z8 }3 y3 q4 ~

; R0 ^) U, ^$ r8 V( d! hECC曲线加密核心原理
; g. `- ?4 w# m+ p  A8 j
+ F' Z' P" p# y/ y下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算
" H& P8 ?. j2 f$ F9 b% B
' h( {3 }4 o( M: B* G设 Q 为曲线上一点/ m2 v2 Q+ q4 V8 P" I, E
1 h" v& |( d' _8 k5 o
若点R = Q * Q，也可以记为 R=2.Q
, N7 f4 T, g1 l9 J6 t5 r. m
( n, }3 }( H5 ~; G. o) ]) L) K若点R =QQQ，可以记为 R =3.Q" F; q) d7 @# j: j& d! v
' f! b  v8 v: r  V' W) r
若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q
& y4 i- o3 F7 c1 d
3 m# l0 N  L' h: Z, l然后原理来了2 T2 k/ t0 S, x  [- Z' L! J
7 {7 D8 N1 T! S; O2 d) T: r: l
给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n
7 ?' ]7 `- q+ i, z1 w9 D* h# {2 ~7 o
! w$ h( t7 J+ w. D就这一条原理，然后其他的都是证明出来的。5 r+ B  ?. b( x7 x

3 d9 p  e8 k! [$ s# A" E* m#公钥和私钥
3 ]  [( }( |- s: a5 K- r. s; F- h5 u1 q3 z# }6 U" C, c
先复习一下原理. V. W4 k- V, a. k0 v4 Z/ h

  h# g; n  I- d3 h/ |3 q/ r5 E设Q为曲线上一点，k为一个整数4 r1 v) S8 W9 d) c/ p* ]4 M0 c* b! ~
) O8 @; e/ x& O$ q6 D6 v1 `* s
令点K = k.Q，若给定 k 和 Q，很容易求出 K
8 \: @9 a3 l1 F6 [0 G: ~* ^; p2 L& H
若给定 K 和 Q ，很难求出k6 j7 [6 p) t9 C! |+ I7 K: s$ h

/ V! @& W9 u" O. a2 k  q我换个说法给你看
6 E, R7 i& N- p  y
4 p: H3 T2 S; n# {% n设G为曲线上一点，k为私钥; Z5 J* L/ d& m, @
; A( S* ^' {' ]6 J9 _  D) B
令公钥K=k.G, 若给定私钥和G，很容易求出公钥
, ^4 r- J& y( u
; p3 P. t/ H* h) u+ h* p0 z1 k若给定公钥和G，很难求出私钥: ~3 X( u1 x" D' \% [
' _, M2 m# F, C7 D' A
是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数
' @. o# q1 s- h
9 n1 [  @+ V+ _7 u而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）4 ~1 h' p$ o3 H* U

$ A4 y4 u& y( r1 N: s$ {ECC曲线有很多应用，最常用的是加密解密和签名验证
1 v5 }9 `# V5 F1 W/ M" T/ `* ]1 o4 a8 U; h4 T+ w% \) p! h
#加密原理) |( ~) G& X8 P9 D5 M* z1 P

, t6 ~/ h; E" F0 E  o- I$ y加密步骤
, \' k! F! v) @; E! w5 j4 g5 Z
0 i% D. o: E- X先设 K=k.G，（公钥=约定点G阶乘私钥）。! I4 {+ g0 e2 E7 j' n6 j

) B' m) r: M5 k6 i1 W* S" h5 `, q欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）% ^  M( u/ n9 O/ X+ z
: u! v/ B) \) N
整个随机整数r
/ e! g9 {" c/ T
  C, E2 t3 X7 k. {计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M2 c& a- U" F. N4 a8 P: n2 D: z

! s" }1 Z* s& k# b. s* P计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数
& @. {/ w, D, d. m( Y" R9 j: Z0 B+ \2 x+ I/ W
加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点) H/ z' ?6 j' X. R$ |

; x+ A6 _' J- b( m7 s3 n2 h加密者只需发送C1 C2 给对方& v3 n/ C) J& V, w, [- B0 z

0 c; |! `, `& s6 R- V解密步骤& ^1 b4 {* X+ j. F7 R+ l, v6 o

- o' Z  K7 {3 V- |由C1=M+r.K 可知 M =C1-r.K
/ L8 w& G2 G, j+ X! r
' C6 N# z( u& q8 [由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G
3 I; z! c4 j% J1 i
( y- G; ~! G4 L5 m  }由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2# p6 {4 B% Q' V* M4 @2 _

/ z& L+ v' T9 p据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M  b$ c5 S+ ]4 Q, |* f8 [7 c1 u
2 F1 @# L# m. }- g0 q
#签名验证原理/ t+ h3 ~$ c2 s& S# H
" S9 b" [0 h/ i7 {0 r/ B% W. B; n
签名步骤0 Y+ M) _/ ^/ M4 R- O  p) a, l

4 q6 t0 p, x( V  U先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥# }; R0 S. ^, e: p" _/ ]
$ H" k3 O/ s7 f
对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e, D$ f' R/ T! j

, }' g0 r# z! K& n. X1 t: L2 [; s6 \整个随机整数r) M7 O! s$ J, z& b

6 B; s9 Z  P+ T' W4 Q  A  G# @6 _计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。8 `+ \0 f/ t. i. Z- C# ~
8 |# Y$ I9 L" n9 D; o
签名完成
9 z1 x( B% G, s4 A
4 {+ u9 O' _* V9 x$ ?通常说签名（signdata）就是指s和r两个整数。: g3 ~, m5 V7 f& F' u

3 T: k7 f8 e! }& d7 r: j签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。/ t; D8 @" P3 J% m
8 R, V3 o7 H2 ]6 g
验签步骤，验签用公钥
- r6 v& N4 ?* P+ N% [
- o" |8 K# e8 A" N9 v+ @9 W2 j对欲签名数据进行处理 e=hash(m)
  E3 _# }& S: b0 r# o
' K6 e5 @9 T4 a计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
# p- E- y6 p4 g) T
0 B9 i. l; Y5 t( K: S: ]计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )
/ J8 ~6 E8 [7 V& w0 {! b0 R; d' d
7 S+ G5 Z9 q% b; _1 `8 m若V1=V2 则验签成功，接下来证明
2 M. }3 X1 \) \1 [1 u0 t+ \( b+ X
& H1 V; Q" o2 }& q若数据都是对的，则s =r-e*k成立
6 \3 ~! N1 z0 d. \9 j! N/ C# O# B7 u) [* \
  Q" L# R" O5 k5 @9 q' r此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K% V. [& x; A% |

$ b) S% l( t& u" h# ?9 z$ o5 b% _0 MV2 =r.G-e.k.G+e.K! P. @" y5 c* {1 U! _1 d  R  l- `6 @

) V8 ?! f8 q" e# L/ ~因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K
8 A! T2 \+ }& F+ P) Q; P7 p1 M! s( [9 z/ K0 P! J
上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
! `/ R9 _! f+ \
7 S2 I) a0 r$ k1 d3 B3 I1 s反之，当V1=V2时，s=r-e*k成立，数据正确