对于RSA这套公私钥加密的思路，我以为我挺明白的，运用的娴熟自如。# A' X3 @3 v, ^6 m( n0 H) |

$ }; W# A6 d  \$ N当然现在RSA用的不多，而是基于ECC曲线来做签名验签，最大名鼎鼎的莫过于比特币。
8 E1 K8 F. h" t2 s. F$ f/ s( M! ]1 r8 a2 d9 ?3 M; L% s  l
可是前两天和别人讲代码，被问了ECC为什么可以用来做验签，发现自己讲不清楚。9 l( T4 ^$ {2 P) [/ K
7 ?, Q) U8 N) p4 L" ^
所以做了点功课，来把这个问题讲清楚。$ x0 H8 r" ^4 {1 c7 a* ^4 q# A3 Q

# G2 h$ `1 I7 C, L* a4 Q, N- y! o1 g首先我们跳过ECC曲线是个啥这个话题。1 P; @# A; B! t; E) n. e1 ?, i8 V5 T
% W, l8 U% t7 _9 l+ N3 g# \
这部分我觉得对理解这个逻辑，帮助并不大，黑盒掉就好了。, q9 D% q: U! H
# v  H' ~# O* ?, V& ?% f
因为我们是程序员，有类型这样的表述神器，非常清晰，你一点都不用害怕。
$ T1 R- C2 E( I2 ?/ h! L
' G$ X) E; Z) u4 |- P( i只说原理，非伪代码，比如关于曲线阶数不说不影响理解原理，我就不说了。
' x3 {! @" n1 c4 p6 U5 e& h9 ^* I$ m. R8 d, n3 t
ECC曲线加密核心原理; x6 z5 I3 k/ x( A# ]* y( N5 u. B
' j  K, @1 _8 P. S
下面我们讲的，都在同一条曲线上，这条曲线上的点支持一种乘法运算; F: Q; X9 p7 G+ o9 r( B2 t0 ^
9 G( |+ U  B: v: n  j5 O' b2 {- k
设 Q 为曲线上一点
) C( U& Q( g$ M1 W; m' V. O6 X4 W0 |6 s# p( A/ }! [
若点R = Q * Q，也可以记为 R=2.Q5 L7 {, Y! ~; I1 w% S; k8 B
& l6 m& }% E* S* x
若点R =QQQ，可以记为 R =3.Q
4 p) o% u# V$ z2 s8 g1 `7 Z
5 g$ [' O# R8 L# o! u2 P若点R =QQ……*Q ,一共n个Q，则可以记为R=n.Q# g3 v  H3 |! a* [7 @
6 W2 M; u. f5 p5 p0 m1 K; m. M
然后原理来了
: K5 W* @+ `7 j1 F$ O% x
; H0 u1 d6 X5 ^5 x3 i0 `给定n 和 Q 求 R 很容易，给定R 和 Q，则非常难求出n+ r! h5 Q# F. B8 R  g8 x
, D! X+ F. G8 o
就这一条原理，然后其他的都是证明出来的。
. N8 I% v, O2 Y( J( [+ |$ I) M# g* T/ H; h
#公钥和私钥7 W1 n, F3 n) ?: E9 G* g
) \4 f. `6 K' x9 [! `/ x7 c
先复习一下原理
+ N6 z) c' y  l! F% z2 x7 r8 ]9 f# ]2 a" I
设Q为曲线上一点，k为一个整数
9 x2 ^4 t+ Z  [6 Q6 j9 B2 W, A# d* ]7 |" a$ C( V; ?
令点K = k.Q，若给定 k 和 Q，很容易求出 K
7 \( ?. P0 w+ d  x$ j0 L4 z8 g  F, q  B: u2 y. z+ A
若给定 K 和 Q ，很难求出k' d: x0 R- D; R4 h
* o; |* Y+ C# r0 w: d; [$ b6 {
我换个说法给你看
# J& r* g6 X7 b8 ~: h" B3 ^  e  g, ^& s' ~2 c
设G为曲线上一点，k为私钥" ^% P0 a8 j1 V2 x/ R/ f! i- a

2 }9 r) v. t- }' f& T2 ]令公钥K=k.G, 若给定私钥和G，很容易求出公钥- P/ {( c0 T, C

$ \' P0 b# m3 T& a+ M6 f, t; ?若给定公钥和G，很难求出私钥: W: q) N8 i9 n. @

7 t1 g  N4 P, G: e4 q; X是不是有点意思了，从这里我们也可以看出，ECC的私钥就是一个整数，一个很大很大的整数，Int64 别提了，常用的ECC算法，私钥是一个256bit的整数9 N- J! l: p! b/ v, c0 [

9 M1 \) s4 M5 |. l- x而ECC的公钥是一个点，虽然平常看到他们不是字符串就是bytearray，但是私钥是整数，公钥是一个点（二维坐标）
% Y& r5 n& k8 b2 b$ P- t& D# P8 _# b# r$ C% ^, ~* b
ECC曲线有很多应用，最常用的是加密解密和签名验证6 [% J/ i& T, q$ q+ w

2 I. |* W2 i4 u- j* N#加密原理
- E3 j0 B! V% p4 t- @# z+ [# `
4 s* O, w! A7 H$ n: W加密步骤( m+ @' p' p) R$ Z9 J
- T* |, r7 P# y8 V% \' }, D  m( c. q
先设 K=k.G，（公钥=约定点G阶乘私钥）。* f$ f0 ]3 B( i

7 W# V% s  Y* A( Z2 b, t3 [$ i欲传递的数据m，先把他编码为一个坐标点M（怎么编码是你的事，比如一个字符串，你把他先bytes，然后变成大整数，当坐标的x坐标，纯属举例）
4 Q/ v; g! t4 F7 Q" I* \! I4 Z% R9 U; l' `$ c9 @& ?
整个随机整数r& B: ]4 p" d, u; }. U+ r# T
5 I+ x6 X/ F) [% Y5 B( a$ R
计算点 C1 = M+r.K看到这里肯定有点晕，这里出现了点的加法，还有r.K，r.K 就是 r 个 K相乘，K是公钥。就是 点C1 等于 r个公钥相乘加上坐标点M
# k! Y' v4 l% J7 ?/ T2 R: s5 U0 X. C( s( z# _4 n, [
计算点C2 = r.G G是曲线上面约定好的一点，就是k=k.G（公钥=约定点G阶乘私钥）那个G，r是前面的随机整数
8 Z. X7 M4 q% r) @# P
  F2 |( n+ l1 I: F. A) w加密完成，可以看出加密需要公钥，加密将坐标点M 加密为 C1 C2 两个坐标点; u( U- e" k: S5 ~) B5 G- ^
! m' s  I# Y1 w7 S! M
加密者只需发送C1 C2 给对方* F! R4 y  i* `4 I, \& N5 g

, A$ u  |1 r7 t解密步骤
- \* S" h' b2 I; _" N: X4 P  {/ J
由C1=M+r.K 可知 M =C1-r.K
7 Q# u: a  j9 }  b6 n6 Y& b: s4 U; D
+ v& G7 L; o3 O由K=k.G（公钥=私钥）将K代入上式可得 M=C1-r.k.G; F8 N0 ?0 ]9 ~
, ~! F  l5 Y+ l1 T
由C2=r.G 带入上式，可得 M=C1-k.(r.G)=C1-k.C20 m( Y8 g8 C! s+ \8 U8 I. G$ c

/ y* N1 t9 `8 q) r  ?5 J据上面推导的结论 M=C1-k.C2,则解密者根据收到的C1，C2，用自己的私钥，可以计算出加密坐标点M/ |# A% v0 u) \2 s$ E! L3 j

+ E$ C/ s+ @, W8 e#签名验证原理% f: k0 Y& i: O. z$ \3 ^' |9 O! s

/ g5 A# o$ J; W  `0 Y2 n9 A签名步骤
  [+ y; t3 C. r$ Y/ x+ s9 U  h, m7 J4 @" K. k
先设 K=k.G，（公钥=约定点G阶乘私钥），设欲签名数据为m，签名用私钥
5 R% I# k, }+ c6 H+ W1 t
3 b4 U1 O- p5 K对欲签名数据进行处理 e=hash(m)，e是一个巨大整数，Hash 算法不用解释了吧，m是必选，ECSDA实现中还把一个坐标放进去一起算hash，为了便于理解原理，我就不代入那些了，只说e9 A% t5 ^4 h* G3 P4 J( E

* V% ~" j7 ^- f( Q3 k整个随机整数r5 V( E8 f" ?( |+ [6 N0 z" r
* t! k5 L$ y+ {9 ]" p- I3 A
计算s=r-ek，这个式子纯粹是整数运算，结果s当然也是整数 ，s=随机数减去 hash私钥，就这个意思。
. l: Z3 J0 D7 E5 L
8 N. y$ W% d. e签名完成# B% n2 G' i8 F2 g4 R

  ?4 b. L" c) i/ V9 O+ z# ~通常说签名（signdata）就是指s和r两个整数。: J+ H6 W$ x3 u. r7 [

" [9 m& K! i1 y$ d签名者发送 s、r、公钥K，欲签名数据m，则任何人可以验签。
5 i" C" Z4 L. w# B5 \
1 s" \! m0 ]8 u9 R验签步骤，验签用公钥
7 f$ h7 r+ P- B$ o/ l+ ~/ k& t+ w  s! `" q% j2 h
对欲签名数据进行处理 e=hash(m)
0 b$ M5 m0 T4 q) X7 J
6 R1 U  Y9 r* j) z  Q- h" i/ s计算点V1=r.G（就是算公钥那个点G 阶乘随机数 r）
6 t2 W7 y" L1 E; {
6 j* t0 ]0 I, B" k3 W计算点V2=s.G+e.K ( 点G阶乘签名数据s 加上 公钥阶乘 )
4 F1 T% v% @( G. x, k4 k, C$ A7 `3 Q9 R. K7 k/ E4 z. u7 O
若V1=V2 则验签成功，接下来证明
5 Z1 l! {4 D8 |# f" @! L" n, c1 J) u. {! s
若数据都是对的，则s =r-e*k成立' t6 ]% \, C9 \7 V: k; N/ _8 p
' j. R) y8 z8 i  h; E3 Q! f
此时设s=r-ek，V2=s.G+e.K 将s展开 得 V2=(r-ek).G+e.K5 a# r: U( W, q
/ V8 I/ U- m8 M' a, L# Q: b( [; N
V2 =r.G-e.k.G+e.K4 b3 D6 z! S1 ]6 N1 y

( |% \6 M3 p# _因为K=k.G，代入上式，可得V2 = r.G – e.(k.G)+e.K = r.G -e.K+e.K
# y% ?& O( a: p0 o
2 _$ g9 Y4 k* a3 C6 X: D上式抵消e.K之后得V2=r.G，可知假设s=r-e*k时，V2=r.G =V1# R& ~4 r$ B1 ^5 Z

. B4 `  ?2 f* t反之，当V1=V2时，s=r-e*k成立，数据正确