● 1 Golang中RSA加密算法实现
● 1.2.1 加密
● 1.2.2 解密
● 1.2.2.1 生成私钥
● 1.2.2.2 解密
● 1.1 RSA加密算法基础
● 1.2 算法优化
● 1.3 多素数
● 1.2 Golang中实现方式
● 2 Golang中Big包
● 2.1.1 Word (
src/math/big/arith.go
)
● 2.1.2 nat (
src/math/big/nat.go
)
● 2.1.3 Int (
src/math/big/int.go
)
● 2.1.4 Rat(
src/math/big/rat.go
)
● 2.1.4 Float(
src/math/big/rat.go
)
● 2.1 类型
1 Golang中RSA加密算法实现
1.1 RSA加密算法基础
RSA加密算法属于非对称加密算法，属于网络的基础安全算法。阮一峰的博文：RSA算法原理(一)和RSA算法原理(二)，非常通俗易懂。在这里简单的归纳总结一下，整个算法分为三个步骤，分别为：生成公钥和密钥；发送方使用公钥生成密文；接收方使用密钥解密。
生成公钥和私钥
● 选择两个较大的质数
p
和
q
;
● 计算
p
和
q
的乘积
n=p×q
；
● 随机选择整数
e
, 保证
1<e<φ(n)
并且
e,φ(n)
互质，其中
φ(n)
为
n
的欧拉函数值；
● 方程
e×d−1=k×φ(n)
的一组解：
(d,k)
；
● 公钥：
(n,e)
；私钥：
(n,d)
公钥加密
对于待加密的数值：m, 那么密文: c=memodn。
私钥解密通过(n,d)和密文c，计算得到密文: m=cdmodn。
1.2 算法优化
在解密的算法中，关键点在于计算cd和对于n取模，但是通常情况下，该数是非常大的，因此计算是非常耗时操作。所以对于RSA算法解密的过程有简化的方法。
中国剩余定理
在*孙子算经*中有下面这么一段话
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
换成RSA中就是这样描述：p和q是两个素数，n=p×q, 对于任意(m1,m2),(0≤m21<p,0≤m2<q), 必然存在唯一的整数m,(0≤m<n) 满足 m1=mmodq,m2=mmodp， 所以RSA解密算法中的m=cdmodn, 可以分解为m1=cdmodp,m2=cdmodq, 然后再求得m。对于cdmodp=…=crmodp, 其中r为d除p−1的余数， 即r=dmod(p−1), 令dp=dmod(p−1)，同理dq=dmod(q−1)。同时计算出qinv×q=1modp。在预先计算出结果后，就可快速的解密
● m1=cdpmodp
● m2=cdqmodq
● h=(qinv×((m1−m2)modp))modp
● m=m2+h∗q
1.3 多素数
之前讨论的都是两个素数生成加密算法，为了保证n的位数，可以选择超过两个的素数，p,q,r1,r2…,rn，生成公钥和私钥的过程和之前一样，加密和解密的直接算法也是同样的。同样可以使用算法的优化算法。
1.2 Golang中实现方式
在Golang中实现了RSA加密算法：src/crypto/rsa/rsa.go文件中实现了RSA算法。该算法实现上述讨论的内容，但是除此之外，还处理可能出来的问题。如果me的值比n还小，那么c=me，所以根据c很容易的计算出m，因此通常是增加m的值，使之与n接近，PKCS1和OAEP都是很好的方法，在这里不做重点讨论。
1.2.1 加密
公钥的数据结构：
1
type PublicKey
struct
{
2
N *big.Int
// modulus
3
E
int
// public exponent
包含了公钥必须n和e，但是两个是不同的数据类型big.Int和int两种。加密过程也是非常简单
1
func
encrypt
(
c
*
big
.Int
,
pub
*
PublicKey
,
m
*
big
.Int
) *
big
.Int
{
2
e
:= big.
NewInt
(int64(pub.E))
3
c.
Exp
(m, e, pub.N)
4
return c
其中Exp方法作用c=memodpub.N
1.2.2 解密
私钥的数据结构
1
type PrivateKey
struct
{
2
PublicKey
// public part.
3
D *big.Int
// private exponent
4
Primes []*big.Int
// prime factors of N, has >= 2 elements.
5
// Precomputed contains precomputed values that speed up private
6
// operations, if available.
7
Precomputed PrecomputedValues
私钥结构包含(
embed
)了公钥的结构，也可以知道使用了多素数的计算的方式，并使用
PrecomputedValues
结构保存加速解密计算的值，具体信息如下：
1
type PrecomputedValues struct {
2
Dp, Dq *big.
Int
// D mod (P-1) (or mod Q-1)
3
Qinv *big.
Int
// Q^-1 mod P
4
CRTValues []CRTValue
6
// 包含了中国余数定理的值
7
type CRTValue struct {
8
Exp *big.
Int
// D mod (prime-1).
9
Coeff *big.
Int
// R·Coeff ≡ 1 mod Prime.
10
R *big.
Int
// product of primes prior to this (inc p and q).
其中
Dp
,
Dq
和
Qinv
是之前算法描述的预先计算的值，而
CRTValue
切片包含了使用中国余数定理所需要的值。
1.2.2.1 生成私钥
1
func
GenerateKey
(random io.Reader, bits
int
)
(*PrivateKey, error)
{
2
// 生成只有两个2个素数的RSA
3
return
GenerateMultiPrimeKey(random,
2
, bits)
5
func
GenerateMultiPrimeKey
(random io.Reader, nprimes
int
, bits
int
)
(*PrivateKey, error)
{
6
// 设置E的默认值为65537
7
priv :=
new
(PrivateKey)
8
priv.E =
65537
9
NextSetOfPrimes:
10
for
{
11
// 确定设置还需要的剩余的bit位
12
todo := bits
13
//生成需要需要的bit位的素数
14
for
i :=
0
; i < nprimes; i++ {
15
var
err error
16
primes[i], err = rand.Prime(random, todo/(nprimes-i))
17
if
err !=
nil
{
18
return
nil
, err
20
todo -= primes[i].BitLen()
22
n :=
new
(big.Int).Set(bigOne)
23
// totient 保存 n 的欧拉函数值
24
totient :=
new
(big.Int).Set(bigOne)
25
pminus1 :=
new
(big.Int)
26
for
_, prime :=
range
primes {
27
n.Mul(n, prime)
28
pminus1.Sub(prime, bigOne)
29
totient.Mul(totient, pminus1)
31
priv.D =
new
(big.Int)
32
e := big.NewInt(
int64
(priv.E))
33
// 根据E值计算出D值
34
ok := priv.D.ModInverse(e, totient)
35
//...
37
// 为解密过程中预先计算
38
priv.Precompute()
39
return
priv,
nil
在RSA中，公钥中默认为：e=65537，按照所需的素数的个数和生成n的位数生成素数和d，最后进行预先计算操作，以加快解密过程。
1
func
(priv *PrivateKey)
Precompute
()
{
2
//....
3
priv.Precomputed.Dp =
new
(big.Int).Sub(priv.Primes[
0
], bigOne)
4
priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
6
priv.Precomputed.Dq =
new
(big.Int).Sub(priv.Primes[
1
], bigOne)
7
priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
9
priv.Precomputed.Qinv =
new
(big.Int).ModInverse(priv.Primes[
1
], priv.Primes[
0
])
10
//...
对于两个素数的提前计算比较直观，对私钥中的
Precomputed
中的
Dp
,
Dq
和
Qinv
分别计算。
1.2.2.2 解密
1
func
decrypt
(random io.Reader, priv *PrivateKey, c *big.Int)
(m *big.Int, err error)
{
2
//....
3
if
priv.Precomputed.Dp ==
nil
{
4
m =
new
(big.Int).Exp(c, priv.D, priv.N)
5
}
else
{
6
// We have the precalculated values needed for the CRT.
7
m =
new
(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[
0
])
8
m2 :=
new
(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[
1
])
9
m.Sub(m, m2)
10
if
m.Sign() <
0
{
11
m.Add(m, priv.Primes[
0
])
13
m.Mul(m, priv.Precomputed.Qinv)
14
m.Mod(m, priv.Primes[
0
])
15
m.Mul(m, priv.Primes[
1
])
16
m.Add(m, m2)
17
//...
20
//...
21
return
如果没有提前计算，那么直接使用公式计算；如果进行已经提前计算值，则按照优化的算法依次计算。
2 Golang中Big包
由于
RSA
算法在实现过程中需要很大（位数很多）的数据，所以没有使用
int
、
int32
、
int64
等数据类型，而是使用
math.big
包中提供的
Int
类型。除了
Int
类型，还定义了
Rat
,
Float
等相关类型，由于
Go
不支持操作符重载，所以基本上运算使用
Add
,
Sub
等形式定义的，在类型方法中，返回值通常也是
receiver
，所以在使用过程中，不需要定义一些变量保存结果，直接使用链式调用即可。
2.1 类型
在
src/math/big
中，实现了整数
Int
，浮点数
Float
和有理数
Rat
三种使用到的数据类型。除此之外还有一些辅助类型和针对大数处理的函数。
2.1.1 Word (
src/math/big/arith.go
)
1type Word uint
Word
类型是
uint
的别名，它代表了在
big
包中基本操作单元，其中包含了一些列基本的算术计算函数，除了
Word
之间的加减乘除计算；定义了
[]Word
和
Word
之间的加减乘除计算；定义了
[]Word
之间的加和减计算。
2.1.2 nat (
src/math/big/nat.go
)
1type nat []Word
nat
是
[]Word
的别名，和整数表示形式一样，
nat
中每一个元素表示一位数字位，所以对于任意
nat
表示的任意数值
x
，都有：x=x[n−1]×Bn−1+x[n−2]×Bn−2+…+x[1]×B+x[0]
其中
B
为
Word
表示值的基，通常为
1<<32
或者
1<<64
，取决于
uint
的类型是32位还是64位。除此之外，
nat
表示的值在最终的结果中，是不包含前面的零。定义了
nat
之间的加、减、乘、除等操作，还定义了区间内的连乘、平方根、取模；也提供了
nat
池，达到重复使用的目的。
2.1.3 Int (
src/math/big/int.go
)
1
type Int
struct
{
2
neg
bool
// sign
3
abs
nat
// absolute value of the integer
Int
类型定义包含了一个布尔型值
neg
，表示该值是正数还是负数；一个
nat
类型，表示该整数的绝对值。除了定义常规的整数之间运算，还定义了诸如
int32
,
int64
等和
Int
之间互相转换；字符串和
Int
类型相互转换；
And
,
OR
,
NOT
等运算；最大公约数
GCD
,取模
MODE
和素数等相关的计算方法。
2.1.4 Rat(
src/math/big/rat.go
)
1
type Rat
struct
{
2
a, b Int
有理数ab中的分子分母
a
和
b
为
Int
类型，提供了常规的算术运算；还有有
float32
,
float64
等相关转换操作。
2.1.4 Float(
src/math/big/rat.go
)
1
type
Float
struct
{
2
prec
uint32
3
mode RoundingMode
4
acc Accuracy
5
form form
6
neg
bool
7
mant nat
8
exp
int32
浮点型数据表示方式：
sign×mantissa×2exponent
其中 0.5≤mantissa≤1.0, 而且MinExp≤exponent≤MaxExp。除此之外还包含以下三个变量：
● 精度(
precision
): 表示
mantissa
比特位表示值的最大值；
● 取值模式(
mode
): 表示将浮点值转换为
mantissa
表示时候取值模式，一般有
ToNearestEven
,
ToNearestAway
,
ToZero
等等；
● 准确度(
accuracy
):表示取舍值与真正值之间的差值，取值有三种：
Below
,
Exact
和
Above
。
在
Float
类型中的
form
内部使用，用来表示该浮点值是零值，无穷值还是有穷值。
Float
定义的精度限制范围：
1
const
(
2
MaxExp = math.MaxInt32
// largest supported exponent
3
MinExp = math.MinInt32
// smallest supported exponent
4
MaxPrec = math.MaxUint32
// largest (theoretically) supported precision; likely memory-limited
与 IEEE-754 定义的浮点型方式稍微有点不同：
mant
是一个非零的有限值，
nat
切片通常保存
precision
要求的位数，但是如果后面都是
0
,那么
nat
舍弃这些零，如果
precision
不是
Word
长度的整数倍，那么就要在
mant[0]
后面补上
0
; 如果
x.mant=1
，也就是
mantissa=0.5
，将会做一些标准化，将
mantissa
进行左移操作，
exponent
部分会右移操作。统一的形式为
1
x form neg mant
exp
2
----------------------------------------------------------
3
±
0
zero sign - -
4
0
< |x| < +Inf finite sign mantissa exponent
5
±Inf inf sign - -
和其他类型一样，
Float
提供的大量计算的方法。
原文发布时间为：2018-11-25
本文作者：南瓜waniu
本文来自云栖社区合作伙伴“
Golang语言社区
”，了解相关信息可以关注“
Golang语言社区
”。
golang project 不显示文件夹 或者某个包明明能 import 但就是 import 不进来，提示Unresolved reference
golang project 不显示文件夹 或者某个包明明能 import 但就是 import 不进来，提示Unresolved reference
知识分享之Golang——使用embed包实现静态资源打包至二进制文件中
知识分享之Golang篇是我在日常使用Golang时学习到的各种各样的知识的记录，将其整理出来以文章的形式分享给大家，来进行共同学习。欢迎大家进行持续关注。
知识分享系列目前包含Java、Golang、Linux、Docker等等。
Go 语言是使用包来组织源代码的，包（package）是多个 Go 源码的集合，是一种高级的代码复用方案。Go 语言中为我们提供了很多内置包，如 fmt、os、io等。
任何源代码文件必须属于某个包，同时源码文件的第一行有效代码必须是package pacakgeName 语句，通过该语句声明自己所在的包。
Clean(),Dir(),ABS()配合Walk()使用的时候,由于前三个函数返回值的细微差别,会造成遍历目录的时候,得到的结果不一样.filepath.Abs("./myDoc")//返回所给路径的绝对路径这时候遍历没有问题,
2019/06/12 10:50:31 监控 : 1, D:\wo...
