对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。
1 |( p/ m8 L8 O# m: X# w0 |9 U& @2 ^7 F
当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。# E7 y# e/ q- s  Q; L

/ i# g2 \7 X3 M可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。
9 l, r% G! o: f: a$ c5 R! P, k, S2 z$ F; [
所以做了点功课，来把这个问题讲清楚。
1 F) w5 @- a$ G" U9 I1 A6 w  `- y( n% u: b
首先我们跳过ECC曲线是个啥这个话题。4 c  d( a9 b7 `

& y# K1 m+ b7 p# i. B4 B这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。6 k  v3 }, y  b& p
9 U5 ^  A- S) E0 p! z' s
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。
: u/ ]. M. R, S8 F" J$ i( ]! m* O3 D+ d
只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。
8 W6 Y6 ]$ p- |
. e9 V0 _7 o5 l  R/ lECC曲线加密核心原理
4 J1 Y1 h" G$ B1 r8 S+ b
8 U$ ]% D( }6 G$ T下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算
4 I0 B+ U: ^- m
- c1 e7 m2 `% w4 L  U/ v& e设 Q 为曲线上一点
; n7 @8 E7 ~4 v; y8 x# q$ l/ C. ?/ J" T
若点R = Q * Q，也可以记为 R=2.Q
7 `0 Z  D" }/ i0 x& a
& _" C) g8 b# v7 \8 S若点R =QQQ，可以记为 R =3.Q/ t# b. U: \# |: Z

) Z5 E  m* |! w若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q9 {  r9 q0 s% f, _4 P4 z

+ c4 N: z% s2 U! ?- m5 n7 e" }# o$ W然后原理来了* x1 o" N; @+ m' ?* r. @, b8 V/ l

7 p: ]8 z: B7 x0 t. ?给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n
+ r$ Y8 m' b4 X3 L& }: m0 Y9 v. y- h  p% H* J1 @5 g% N. T
就这一条原理，然后其他的都是证明出来的。
3 \9 H2 [) h" J2 [9 t
1 O4 f  j$ t* a7 D% Z2 d- s, P. z#公钥和私钥: J" ?: |* a8 D! r4 a: T5 m

  Z3 @, D/ e: s: S4 ~* c先复习一下原理
; c1 U8 h3 [. ]) \8 S. r, I( b: W: L' d! W/ w( ?) ~
设Q为曲线上一点，k为一个整数
6 ~; Q: d5 a% R  m! H: j9 M- Z% c% R  Z8 Q# u
令点K = k.Q，若给定 k 和 Q，很容易求出 K
8 n& T& ?* q& l; P1 g% i% f1 _6 l6 q
若给定 K 和 Q ，很难求出k/ v0 a* Z7 S( B  V0 q) f. Y
6 F, T+ j( d8 n6 N. s; G
我换个说法给你看
+ K. D( ^* ~2 }2 _6 t; W) [0 r1 q* {  E; e2 _/ H
设G为曲线上一点，k为私钥0 c( P2 K, \  A- S; D' `! X
( J" I- A6 i& _; }! I$ x; K5 W
令公钥K=k.G, 若给定私钥和G，很容易求出公钥$ v& H6 }/ ]& ?6 N; H% ]
/ r/ R3 U6 @: f5 _
若给定公钥和G，很难求出私钥
  B) X9 w6 \7 V- J
, o7 m' o: K/ r& h. E是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数
4 P. n0 \- o; U( Y: U4 v
# y  _5 \* ^. g而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）
; {2 s7 [9 O" J. ?! B2 l9 P- Q) U
: c2 e# |% H& t( m* O3 m+ d% H6 AECC曲线有很多应用，最常用的是加密解密和签名验证0 x5 t4 v' U& k  y

# j) C! y& g  Y4 F6 ^5 K#加密原理
  }4 |2 h5 B) f0 c: P
9 O1 ~+ E1 i' [/ s) K2 v7 h加密步骤9 b7 e7 R- h* n" y2 e1 x

; P# w- E& f( _' n3 |先设 K=k.G，（公钥=约定点G阶乘私钥）。1 Q) r  n8 U- P$ E5 E5 q0 F- L5 `
- {2 B. t' h$ x- C& V
欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）
1 P. }/ G& v4 y
8 M9 Q+ o  t: \8 ]整个随机整数r
, f8 f: ^* M+ b' @/ d, z8 x8 b! i: [* p7 Q
计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M
3 [* o' F/ D3 [  V. M0 {  Y' o- L
" w5 s- d% `' T6 L! |5 d计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数
. ^* n& K# j5 b6 A# Q' L
/ E! S7 b# a) v) g+ f& ~, Z$ A加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点
5 S( c: `0 B/ N; _: r, J$ B: W+ C3 s3 z* n
加密者只需发送C1 C2 给对方3 `( {- J. |+ l. B9 T$ b

0 U8 M3 p' R# V# A$ q3 K" Q解密步骤: o, Z- I! G0 N6 T" |  c2 B

7 ^( g) B8 p" R. |9 t$ c. P8 S由C1=M+r.K 可知 M =C1-r.K! d- y) h9 E+ S3 U1 b/ ~7 \

1 j+ q$ p; D6 z2 |8 l由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G, U" E0 j" \3 q; h$ j! o, p/ a0 A$ t
. f& O" w2 O5 z. z* u% D+ U% ]
由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2
- F" u5 y- L, Z- D# ?( L0 X! d2 n; z8 Y1 T# {  K6 W6 G( l0 o1 ]: E
据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M7 g: S  s1 |& Q' R6 ?, \" `
( M7 h  ?# |2 i0 O
#签名验证原理+ Z" v- s) q$ z8 q

  r$ M' {% s; y, _, @$ c& r签名步骤
7 a4 ?' v4 ~& }) c# J* }0 H  L) x$ f! g( N
先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥8 g1 L2 J7 T: Y

6 k) E$ d; m, I7 H6 e; p+ l对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e( ?- d) \- p8 Y

# d- L2 B) h* h整个随机整数r5 i4 U4 q& J$ f7 I$ s
1 G! L* ^: |7 e
计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。
3 h* O" r5 ]# m1 r
- A) i5 K2 @1 w! k1 j签名完成9 k7 p- [! l/ H
& H# r' L! q2 ?$ ?
通常说签名（signdata）就是指s和r两个整数。9 m! Q; h7 h( ~) q& ^! _

  K9 I4 T5 K6 }& o; v  p4 }签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。
) }& p  n0 U/ t4 F8 X9 ?: w5 S
" H- l, u2 f  ?  L! `1 M6 B验签步骤，验签用公钥
9 s; ]8 L6 }, L" E. o% m* ^8 o  H2 z1 ~, F
对欲签名数据进行处理 e=hash(m)9 D* _  e5 g3 E/ D3 Q- s
" h3 l& K, D# i' }/ u' V* {- ~" P& V
计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
* m3 u( H! j' L' z6 {" x/ }- X( {( e* b2 B3 Q) Y: o! s
计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )
1 {  K2 T. M& C6 ]$ P
# R% L2 E& |. w7 g( T: O若V1=V2 则验签成功，接下来证明
, _$ C' ?4 T* Y) @- Z: \# X
& `6 I" J- {  ]: W$ U若数据都是对的，则s =r-e*k成立
2 j3 {( u9 u6 m2 F0 r' L( d3 z9 d/ I% G1 c7 Y( R- i4 A9 ?
此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K
4 N0 H2 J5 @& z2 F7 w3 Q, t8 h+ v/ K5 |. i/ K2 ^
V2 =r.G-e.k.G+e.K' B, j6 O# W' T6 z8 _, V/ m
4 E- d7 m* E9 A0 K6 F
因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K
" L0 o$ Z5 {& d  L$ J" o. t& @( I9 g. y3 a/ ^; s, b% B
上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
& n8 Y5 @7 [, t8 |( z1 C$ j6 U. O: i5 w5 T" ?( X. P; j
反之，当V1=V2时，s=r-e*k成立，数据正确