对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。
6 E* w, v. R% V0 {4 U* ?! r
7 y' ?, }- s' ]$ Y- m+ w! C当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。; P# t' Y  Y6 y( Q3 w

% T' S! [3 ]# m7 Y, U/ B7 a可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。
, n9 C% w, |" l1 {" g! ~) Y- E+ M% R% ~" }
所以做了点功课，来把这个问题讲清楚。
, }7 O; r+ y- ~5 c" h; h! N! I% Y* K; Y4 q9 w
首先我们跳过ECC曲线是个啥这个话题。
1 V' A7 S: A! i- a) L" e: n! s* H+ G6 u7 F2 H7 ^+ s
这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。
* D& S4 Z. t, N+ \$ m3 e. _3 X3 N; W+ J! |* B$ D2 j5 M
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。
. Q/ ?. f* ?. h' m  n" R, K% ?( e9 h, u* P2 d6 e
只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。
9 M5 d+ f! T0 G* I; Y  m. H! k: z4 v! z! g$ {# u
ECC曲线加密核心原理
2 I. ~% F: t# G4 z
0 ?  v) C/ W1 @6 B9 J下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算
) X8 U; Z; g/ Q8 y; T5 l) |+ f. B) L  n' I" j  j; m5 I
设 Q 为曲线上一点% o  U% I5 M# o' \. A4 R
, C5 f4 N+ U5 x- i% Q
若点R = Q * Q，也可以记为 R=2.Q
/ o6 Q' c% Z: \, c/ I! r
7 Q3 |- N3 x* C& g. V- b若点R =QQQ，可以记为 R =3.Q
) J* E0 w3 @1 u- e8 a7 o3 Z# N5 r3 e8 E3 E0 t9 T  a
若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q
" n! L& z2 H' B$ K: H
5 t# T: `$ C9 H+ W7 J然后原理来了+ [$ Q6 a5 g% L! a) S
9 n( c8 z+ f3 C* g9 c- l+ k
给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n
4 T" q' Z+ G3 t$ Q/ H& Y" t2 d) B. e
就这一条原理，然后其他的都是证明出来的。
! w* u4 h' Y# ?- E4 {3 |5 f
2 Y2 l2 Y1 ?" L( g& u: J#公钥和私钥
" a5 q; C" h+ V( n5 s
; @1 j! v  V) V  R2 v2 |9 |5 z先复习一下原理
. j9 b6 h9 K4 z4 o8 k$ M. h% D- I8 N7 I, K5 W
设Q为曲线上一点，k为一个整数
; Z: z2 k( [5 I; D; k3 f$ c- h1 r, {, J1 e. h. Z4 E* P% ~
令点K = k.Q，若给定 k 和 Q，很容易求出 K
$ n* @6 ?; f* W( L+ w/ k
( k7 z5 W6 d( P5 g若给定 K 和 Q ，很难求出k& c) B( X" q" d0 |) O* K
! T! L6 R. C% o7 V
我换个说法给你看
" a6 Q1 z% ]; n+ Y5 y/ _. @( V/ b) C% z
设G为曲线上一点，k为私钥( w- P0 B. I/ R* h; P, ^9 T
. C6 |, C8 I0 H' N
令公钥K=k.G, 若给定私钥和G，很容易求出公钥. }+ {  E/ E& {1 H& c

# c/ B4 Q7 o( Y! z若给定公钥和G，很难求出私钥2 E( ~, I# J, P% z5 h4 E
& c3 y8 i( h. a4 C
是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数
' t: `, T  q* W4 g3 a% j9 J) k6 s6 L) |2 h8 P+ _( U9 b( n
而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）0 D4 K( ?9 M2 L+ M8 Y
* B! V, G7 b9 |# }2 ?2 Z8 F; n
ECC曲线有很多应用，最常用的是加密解密和签名验证4 V. z0 t3 k) }/ A) c
( k6 ^. ~1 F0 E2 y9 M& w
#加密原理# j! O" u. V8 ]" _
" `8 U( m2 @- u' v
加密步骤0 G; Q7 l9 `2 n. L" ]5 ^

; V$ `1 P6 Y! @8 N+ p先设 K=k.G，（公钥=约定点G阶乘私钥）。
3 s7 X% ~' Y  ^/ o/ W" r* T) }6 Y  S/ S! l- Q5 Y6 u5 E3 U
欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）
) G( W2 Q7 `/ d$ d5 B
% Z  n; N9 r/ _4 ^5 y" ?8 G* R& ^  p整个随机整数r6 T/ R+ ?& D: i" j9 l; t
( G1 Z& L9 k% q$ u
计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M& L& o& n, a0 Z4 B- |% t& j2 N
1 }, {. B% N% ~3 k
计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数8 f9 i- z$ E- ]& Z: v, s

( m: B: n$ @9 w加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点, @5 N1 D, f7 `
7 ~# V8 f1 d' Q, ]4 B! P
加密者只需发送C1 C2 给对方
0 t( ]* Y( a/ R, T
, i' O1 N( X7 L, V0 p  n5 I. z# }* }解密步骤
8 u* W% o. ]8 D3 h  _1 w0 ]
$ m+ _$ m) k9 a! t/ e4 w+ V由C1=M+r.K 可知 M =C1-r.K
8 |) @4 o4 f8 X+ G$ G2 L9 V3 F4 _* B
由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G5 K" h7 E! Z  S- E5 Y% B+ o5 }
$ |" f: C$ G7 o0 m* K
由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C29 ?3 ~9 G4 |5 x  V+ V; k) M7 h, W

; }' T& B" @% E# I" r据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M
, d( V4 N% ]9 s4 S5 b# k6 P
7 L' _; P7 _# o* K' P5 Y% j#签名验证原理
2 }) T9 r/ r; r/ Y- D8 g4 l( n5 s+ G+ a0 [
签名步骤
4 q9 ]8 i. u8 b$ b9 T7 p0 A
3 h6 d. R& a- Z- W先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥
+ W, ]) G9 N# F6 \$ s- c% a8 C# z5 K5 v
对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e' M6 m4 c1 ?. ^1 O5 x2 J

, T* z4 k' b% V9 p整个随机整数r
6 y# V9 r  T6 B: l6 |0 Y* F9 X
1 {5 E4 Z: k8 z; o& Y8 L计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。. S  p8 C3 ?6 j& @8 F

  _: `6 W$ _( W! {8 ]! S8 u签名完成! i; ?" `  \: H% @/ b8 c

, W+ G9 ]. }/ y, q( x5 z通常说签名（signdata）就是指s和r两个整数。% Y4 V* F: y, `& g5 |

1 r' N3 J9 p7 Z/ ]! L签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。
% w% n8 j4 y! U0 M# @0 _2 M1 {8 b/ ?% R$ u0 i  ^4 ]4 X4 s
验签步骤，验签用公钥
- p' I  \0 y6 }- a( ]! i  K4 E# ?" V* n( R" H) a7 G6 g
对欲签名数据进行处理 e=hash(m)# ^# D$ X6 F& v- v" M

' j1 [  d+ X& i+ H% t( K计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
9 L; N! H, Q, v
" G; n! F! i4 a9 V/ N6 Y, o5 T+ d3 W计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )5 z7 l% W2 X! z. m6 k9 w! @- Y
; t. z" }$ e6 c2 H) |, X8 n: v2 [5 o
若V1=V2 则验签成功，接下来证明
2 X4 ]8 h+ l! _  Q
0 e/ g% T% @5 C8 k若数据都是对的，则s =r-e*k成立: [+ z0 Y, T3 h9 P- d8 Y
+ B5 i, }* |7 A' R7 g3 \2 t# @" I
此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K+ V$ S7 T" x7 ~! ]8 G: L
& z& y  y) D: P, T
V2 =r.G-e.k.G+e.K' T9 s4 H8 d5 _) e. B
/ B# @& _& Q+ G+ X+ H! y4 u
因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K
# w! g- S0 J1 s' n: h. Z
+ E1 ?: O* z( R% H上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1. K& w1 I6 }6 [, o7 r2 x+ H

4 r7 D% p1 u: X- C3 Z+ d反之，当V1=V2时，s=r-e*k成立，数据正确