对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。
* b8 `3 s& N3 b, c3 b# ~1 y' r* ~3 v
$ e3 \- v2 H* E" \4 e6 ~当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。$ s6 a1 j/ B& J
% x# r! s- S& G/ O: L
可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。. ~# a( u: A; Z1 A

8 z, h0 i, `2 v1 X所以做了点功课，来把这个问题讲清楚。! A) U- A0 U4 t- _
- m* y, T4 R2 Z- [. h" p  H
首先我们跳过ECC曲线是个啥这个话题。
( ^: I9 i- m1 _  y$ t2 p9 K
  ]: C9 X. W+ K这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。
  t; w% M# S5 G. `) Q5 d0 m0 A& Z4 U: R" K6 b( g( A5 R% g$ K. c
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。' q0 v1 Z( P$ ?. F1 E" n

' l0 x. g, b2 [# _" v* b只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。- g% ~( u% L: H! b

, j# g7 \% L8 P$ o- uECC曲线加密核心原理3 t5 M9 y$ n; l

3 f: j9 L& Q- u下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算+ D/ f& N) Z% W; E, B$ s' x

0 f  M5 w0 D- P! x( [设 Q 为曲线上一点
/ Y0 {8 k$ |/ }/ x# v! v3 u  [7 x$ O: [( \
若点R = Q * Q，也可以记为 R=2.Q! a$ F! s2 x8 m: S2 q
" {0 l# j. o6 I: t' n6 P% V
若点R =QQQ，可以记为 R =3.Q- X* s1 a4 X% M! |( `& t& X* o) i+ z" Z4 q
9 D) A$ v- I7 I+ J# p/ X, l
若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q5 K1 `. J8 `1 ]& Z2 l

* o* k* q7 R/ T$ m- k- d: y! g然后原理来了
, v: Y9 @/ L+ u, |0 m( y. k* g% G
- k7 O: _8 M$ m给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n
, Z4 P% o: }3 I8 O/ u- T
. C& S7 E$ Z3 U8 ^$ }就这一条原理，然后其他的都是证明出来的。
2 b( N" d: J3 v0 E
, G: V. y$ V: ~* C: j# p$ Q5 ]& w#公钥和私钥+ M' A) y6 E: T
" ^4 J: A3 }9 r, O8 d+ z; K4 ~
先复习一下原理& S2 _% B7 m+ V. @+ x! i8 m' r6 w
9 N+ `5 T) k/ f8 p
设Q为曲线上一点，k为一个整数
  n( t8 s. i9 Y$ h* v/ R" y2 a# L1 A
令点K = k.Q，若给定 k 和 Q，很容易求出 K
9 i# q. E* E2 r) ?2 a! `) Y5 d7 C
若给定 K 和 Q ，很难求出k
) b7 B5 K% R7 W% l7 C( e7 Y+ G9 S: l) g& ~/ e7 U
我换个说法给你看
4 O, ^- n- E  R- m
' X& \$ M" W* d6 z设G为曲线上一点，k为私钥+ |% t  W4 _2 ?0 g

0 `! E* D3 d2 g8 a2 l$ J* h令公钥K=k.G, 若给定私钥和G，很容易求出公钥) b! T6 c4 }( d  Q( Z
8 F; r$ C3 a) h* U6 d
若给定公钥和G，很难求出私钥; u3 N$ x; D9 S, l4 h

! R+ _" }+ w; t4 E是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数! q% Y* L& T% B# d$ `  P) h: }/ g

8 _+ \& Y# }: m! c: o# l/ t2 s$ v  Z; r而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）
% l, j9 x8 x1 p7 K- u8 t7 w
5 f* \: A* j) z+ v1 D9 o) l; n% @ECC曲线有很多应用，最常用的是加密解密和签名验证6 e# e: ~( n5 c; Y  B/ u: Z

8 l: H- d. L8 a#加密原理+ T! H+ R; h0 X1 G; W" c2 J) z

6 R; I5 j: [, [) A( S加密步骤4 z6 a( k1 f9 X$ h" P

6 T. s# W& W( u+ U  p* g. q8 O* Y. S) H先设 K=k.G，（公钥=约定点G阶乘私钥）。
6 X5 A8 B/ C" z
. m# {! ]/ L' Z5 }+ w1 ]% h" J欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）. U# s' t2 @! b

4 H# U3 t: \! {0 n. k" E1 W& d% c* g整个随机整数r
, a7 F3 x0 D7 r! [0 X9 x* M
! ?7 r" ^; d3 G: d( N$ H3 W6 V+ L计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M
* E0 t" \9 J9 q7 L# c
; M+ ?% b4 ?" _5 a# y( F计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数$ u3 V5 Z; m0 }7 N" q9 j7 }
" z0 l  y+ P2 I  M2 C
加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点; \0 X" b' [) O# Q* p. Z9 p. g
3 Q) a1 r; b) w8 B' {7 Q$ S+ _: [
加密者只需发送C1 C2 给对方# q6 U7 ?/ d9 o* Y. c

! H1 _! {7 `$ w" h* Q4 P解密步骤0 Z+ }4 z6 G! g# |+ u
. r4 a; t+ P* h
由C1=M+r.K 可知 M =C1-r.K
/ t4 y9 [3 L+ T' m
  E  w( n# K+ i( h由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G( ~* P9 Q1 V& T1 ?9 g

1 D0 {( T; b; j) q! R9 i) }由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2
2 S  X) E- m* A+ n" ~6 M+ I; V
  R3 N: c9 u8 I据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M
  y2 {5 n( m2 z; ]" b7 s( _+ p/ c9 X  e: T
#签名验证原理
" W6 ?3 q* }! M5 G5 Z" ?& q) A2 w1 J4 t3 z. Q
签名步骤
$ V% J6 \3 D/ F2 n, G* s
. q2 a# R( ]% I+ E先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥
" k! h0 `2 G* K' M- C7 R
5 A9 Y7 K( {$ H/ B3 {. y对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e3 I2 ^$ l* S9 a& {6 D: S8 u

8 F# {5 }) b6 N% ^整个随机整数r' z6 J$ B: s" P: ^3 k4 T- K
( p" h2 V9 B  n+ i/ a" L
计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。
+ {9 z% r4 H. M, ~- o9 }3 p5 ?& N* A( X
签名完成
( W# x/ V) E6 O0 i
( z( u9 t$ W' w) a通常说签名（signdata）就是指s和r两个整数。% j& F3 M; C' @; ?* t7 |% K
' t6 x; g. {7 T- y) V# I, a( P
签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。' q- `8 K4 c% A4 \7 R* U/ q- s

; E/ o% ~" R* {- k  S5 e" @验签步骤，验签用公钥1 |* i, }+ S5 v% h

. K/ s! k$ {. i2 \  M5 c9 e. c对欲签名数据进行处理 e=hash(m)& Q, h% g0 ^5 M* y- Y6 a9 Q6 L% |8 d+ q

, f. G6 Y% a. w+ K( x计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）, I8 Y, j1 Y' p3 i5 G$ t* z0 V
& {9 o3 c3 A6 J2 J- X) u; i
计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )
2 N, |1 q5 _+ G5 X% l% w9 V; D9 }3 x9 o: z' A6 d9 f  G
若V1=V2 则验签成功，接下来证明
) t5 _, k- J% w! x! T0 M5 q, Q* w3 F% _* W8 e3 {  n/ p" H2 P$ [8 V! v3 b
若数据都是对的，则s =r-e*k成立
1 Y" L, G) D5 T: X$ S( ~
! G" w! Z7 C2 n1 z* P$ D此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K8 d/ d- _! q! ^* _+ g
# d  v( \6 ]" |6 k0 j- d
V2 =r.G-e.k.G+e.K
. [& t0 E+ s3 i1 j. s
; e# F' i. r/ n$ H$ j- A1 v( }4 w因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K
/ b8 E8 H( D# }8 Q" n% P% [! U6 |# h* S8 n
上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
4 [+ B. A# U) N3 M0 M& ~9 o4 A+ Y: G, F4 f4 g
反之，当V1=V2时，s=r-e*k成立，数据正确