对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。& b5 d) X$ l. l& q) ^8 }

0 u& w  N# v& a/ a当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。
" `0 w2 K7 g% d( B6 e2 j2 m7 M/ O+ X$ t4 }$ n2 P, f
可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。, \( w6 w- Y7 S  b6 X

# ]* q0 a  h# Z1 B所以做了点功课，来把这个问题讲清楚。( ^; B& M/ r8 P8 x

# t$ e: v) g, y7 X首先我们跳过ECC曲线是个啥这个话题。
3 U! D% n! ~3 Z6 N
2 q# {- f1 x3 x, Z$ G! ]# s* ^这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。
& [/ C) r8 G; W. x  h: f, Z% j# l: X: w
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。
) V/ I) D, _' V; N1 f: s5 {6 _! n) w- A5 h
只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。; y  _) K+ ]# t2 W8 @
4 _  m. ?2 ?: s# H8 B  f" F. H
ECC曲线加密核心原理) O3 R, G, X1 _! I- L: N

6 g( ?  f; A& x( l% b下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算1 I6 Z( O, e9 c9 R

3 V3 y6 {( l+ ~$ z* f* M) l( C+ ~设 Q 为曲线上一点
0 [% g) u8 i, Z+ ~; ?) Q
. ~6 O6 R' X' n* r" M) m$ Y若点R = Q * Q，也可以记为 R=2.Q
8 p  t% D( F& {, i7 ?; V- d/ A: d
若点R =QQQ，可以记为 R =3.Q
1 u" y- u: }% z7 Y  b
4 x! s  I' {, z. u  y7 a/ @% _若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q4 h! n0 p8 P; l! n+ [
5 o0 V" I7 q3 \! g
然后原理来了1 z) i* E: Y& j
5 W* V5 u- i/ Q7 j2 ], O" Z+ x2 T
给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n
! r, Z* @. V8 Q1 H4 \/ b( R! V3 H* ~$ V8 C* [4 s8 P! N
就这一条原理，然后其他的都是证明出来的。
! A+ k6 y3 M& Y- l5 W+ j
# S2 |6 f/ R! O6 A  L4 @#公钥和私钥# N! ]& L7 q% g( b

; d" Q) M" W& U% z先复习一下原理
! S2 I6 b9 @2 {/ Q; s+ b- j$ I6 D: V# k  K7 L
设Q为曲线上一点，k为一个整数
& ]( I/ c! v2 C, f" e1 [: [4 p+ t1 ]2 O6 z- O$ T+ B( c
令点K = k.Q，若给定 k 和 Q，很容易求出 K
7 ]: N" |) _5 J/ P. J* I
/ d4 {. g: ]8 n- n# a  r若给定 K 和 Q ，很难求出k4 k4 D" F% n, J6 B( G
! S/ w6 C8 x3 S4 \# `0 i- t
我换个说法给你看
1 d: P$ h0 O; w' O6 g# J2 P
+ o' y6 E7 X: o! S! Y- j5 C设G为曲线上一点，k为私钥8 E4 _: h5 |4 w+ c0 D: p# E. s  m

# G; V1 Q5 _% \6 k令公钥K=k.G, 若给定私钥和G，很容易求出公钥# e2 r/ R! r1 r' ^$ R
2 Q% h: m& E8 h- N/ B
若给定公钥和G，很难求出私钥
+ N  M2 S* k. v6 K. e
6 j+ h+ f* V. a* R7 a8 s% ^是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数# A6 R5 n2 Z: e/ o+ e% T8 E. b7 Y! }

& P2 F1 j. H% I) Z) @而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）8 T+ c: O8 \+ Q& ^# ^
' Y# a) s0 @; F) g
ECC曲线有很多应用，最常用的是加密解密和签名验证
0 K! j0 \2 `+ u0 g" d
9 \2 F* \$ D& z" j( _0 Y" X9 Y#加密原理2 ~2 J* e, E. u6 h  _

2 G9 o% x1 V2 ^: h加密步骤3 D7 G/ a7 u3 i2 X4 v1 c. s3 v

! s- f$ g: T, F! I# e' Z2 g- V先设 K=k.G，（公钥=约定点G阶乘私钥）。
' L6 ~, t0 w3 _4 r* D% W- c( O) Q2 X' |
欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）# d, f1 |2 n, N3 t! Z2 ?. \
) q$ K) h2 m$ L; g* g
整个随机整数r- {- w. W2 [0 H/ Y* K

. p" T- ~6 z+ b* o计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M! \4 x( V& x0 `* s9 ^

7 v* J# m( f, k6 @! ]9 P7 j计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数
( D4 k" Y3 `5 x, V2 H6 d+ Y6 e0 K3 v+ Z* ~) V$ X2 u9 Y
加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点! K9 b' o( J% t* {2 T" |9 ~
0 W9 {) `/ X+ W* ]( |* f' b
加密者只需发送C1 C2 给对方, ~% z6 w) N- L: t+ A: a

, B) Q8 j8 G9 e2 [0 e3 h1 J- L% O. V解密步骤9 j, p" r  `2 Y6 z; d
5 O, J! {7 l6 ]/ j, p
由C1=M+r.K 可知 M =C1-r.K4 Z) Q" a! O1 i+ e( a
+ B1 ~! O% `: m' L5 ~# e
由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G
' {* L6 }2 O0 [3 @+ w% c, s% C1 u- c8 Q
由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C2  y- K( ~6 C" g* e

5 ]0 d- O4 P6 r& q) l' F- f7 \据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M  m3 Q8 a6 L5 j  v$ J, P. q

' |6 ~/ ]7 |3 p# b: }& M! A#签名验证原理( Y, C  G- o5 m3 _7 G

' z5 i1 Z8 J  @0 I签名步骤3 k! i( C1 g/ y4 f, z4 a
% q3 Y. u* p  ?6 K2 q
先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥' f# c: s. v" s$ _% s

6 I) I1 I8 v. V: H0 C对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e
& D: Q* L: \# A3 v+ F- ]; \; L  H
" s" ?/ Q5 n7 m- q6 h& g/ p9 u6 U整个随机整数r
, A1 f) u! L* }- t" A
* @4 T/ ?% u6 T4 i9 W" l1 |8 X) n计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。
  H) V1 k/ I' @( @: y& g/ A
/ R, {8 V! e* m2 s! |# ?4 v签名完成
6 x+ H6 j7 m. J) n9 T5 n/ ^6 S% j
通常说签名（signdata）就是指s和r两个整数。% y! u' u3 l' i: l
( g  u/ w" W! {, y+ p- ?2 \
签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。
- w" Y# B2 e% Z' i! B
" H. N5 ^1 q1 x8 s& o% n验签步骤，验签用公钥
+ H1 H% r  o& X- c) P1 S; k1 }/ z' K6 U7 D  O& @. U
对欲签名数据进行处理 e=hash(m)
* Y% P2 l) T8 G! ^/ T6 @2 ?( p2 l
计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
' R8 i8 G, f1 W, N' O6 Q6 T% ^) X& K
计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )
* F# A3 j' g; [# q0 I4 O; p; f* k% h4 k; }; {2 e+ {  Y
若V1=V2 则验签成功，接下来证明9 d) }# w+ d5 ~, q6 M6 h

" K+ i+ T7 L8 b, v6 G若数据都是对的，则s =r-e*k成立. W3 X' t* s# {6 R. R, S* t

' Z, F: A4 `1 H, V' H! {此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K4 \6 t/ x5 s, f6 F8 G
1 W' d" t7 Z- F! n
V2 =r.G-e.k.G+e.K7 u2 T3 S+ L( J

" N0 N9 @! s# T因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K
1 N7 R- O- ^. s! |. U+ W8 D5 C' y
5 N- q4 N# H' i: D) ~上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1
$ s* i# `# e- L: {) T- c, ^5 y) N
反之，当V1=V2时，s=r-e*k成立，数据正确