UP | HOME

RSA总结

Table of Contents

1 rsa算法原理

rsa是非对称加密,分为私钥与公钥,公钥主要保持了两个数字n, e. 私钥也主要保持两个数字n, d.对于任一一个数字a满足(aed) mod n = a, 其中 ed mod (p-1)(q-1) = 1, n = pq. 这就保证了一个数字经过公钥加密后能被私钥解密. 

加密算法: c = a^e mod n
解密算法: a = c^d mod n

公钥跟私钥在原则上并没有什么不同，(只不过d一般是个很大的数, e一般相对较小)。所以私钥，公钥都可以加密，都可以解密.(私钥加密又叫做签名)

但是如果对于一个很小的数字a, 由于n很大，所以有可能出现ae < n 这时候就会出现 ae mod n = ae, 也就是说加密前后的数字是一样的，并没有起到加密的作用. 所以代码会填充随机字符,把数字的数量级提升到跟N一样。

1.1 公式推导

我们主要推导以下公式成立:
(a^ed) mod n = a

这里用到欧拉定理:
a^(f(n)) mod n = 1, f(n) 是一个函数，在这里只用到了其中一种特殊情况，
当p,q互质的时候,f(pq) = (p-1)(q-1)

由于: ed mod (p-1)(q-1) = 1
所以: ed = h(p-1)(q-1) + 1
所以我们要证明: a^(h(p-1)(q-1)+1) mod n = a
=> a*a^(h*(p-1)*(q-1)) mod n = a

2 ASN1格式

2.1 私有类型

  1. BOOLEAN
  2. INTEGER
  3. REAL
  4. NULL
  5. BIT STRING
  6. OCTET STRING
  7. Character Strings
  8. OBJECT IDENTIFIER
  9. Object Descriptor
  10. TIME TYPES

2.2 组合类型

  1. SEQUENCE
  2. SET
  3. CHOICE
  4. SET OF AND SEQUENCE OF
  5. ANY
  6. ANY DEFINED BY
  7. EXTERNAL
  8. EMBEDDED PDV
  9. CHARACTER STRING

3 PKCS#1 格式

//公钥
type public struct {
  n INTEGER // n
  e INTEGER // e
}

//私钥
type private struct {
  version Version
  n INTEGER
  e INTEGER
  d INTEGER
  p INTEGER
  q INTEGER
  e1 INTEGER
  e2 INTEGER
  c INTEGER
  other OtherInfo //可选
}

4 PKCS#8

由于PKCS#1不够通用，所以提出#8 

type AlgorithmIdentifier struct {
  algorithm OID // 用的哪种算法
  parameters //可选信息
}
//公钥
type public struct {
  algorithm AlgorithmIdentifier
  publicKey []byte // 具体公钥信息 
}


// 私钥
type private struct {
  version Version
  algorithm AlgorithmIdentifier
  privateKey []byte //具体私钥信息, rsa 的话就是上面的PKCS#1私钥的结构
}

5 go 中的rsa包

5.1 获取公钥或私钥

要使用rsa包，首先要得到公钥或者私钥,对于不同的格式有不同的方法调用。

  1. PKCS#1格式
//公钥:
//不知道为何公钥的PKCS#1格式golang没有提供专门的接口进行解析,或许这种格式已经很少人用了？（不过我恰好遇到过）
//由签名的格式我们知道PKCS#1其实就是golang中rsa.PublicKey结构的ASN1编码，所以我们可以使用asn1包接口进行解析
  k := new(rsa.PublicKey)
	_, err = asn1.Unmarshal(der, k)

//私钥:
  x509.ParsePKCS1PrivateKey(der []byte)
//der为私钥文件进行base64解码获得
  1. PKCS#8格式
//公钥:
	x509.ParsePKIXPublicKey(derBytes []byte)
//这里derBytes一般由公钥文件进行base64解码获得

//私钥:
  x509.ParsePKCS8PrivateKey(der []byte)
//der为私钥文件进行base64解码获得

5.2 签名与验签

对于rsa，我们最常做的操作就是签名与验签。

  1. 签名

一般来说签名之前我们需要对数据进行hash得到签名串，再对签名串进行加密.hash算法可以是md5,sha1等。这里我们使用md5 

d := "this is test" 
m := md5.New()
m.Write([]byte(d))
h := m.Sum(nil)
var b *rsa.PrivateKey //这里使用签名的方法获取
sign, err := b.Sign(rand.rander, h, crypto.MD5)
  1. 验证签名
sign := "xxxx" //这是我们的签名
hash := "xxx" // 对数据进行的hash
var pk *rsa.PublicKey //公钥
err := rsa.VerifyPKCS1v15(pk, crypto.MD5, hash, sign)
if err == nil {
  //sucess
}

6 资料

  1. ASN1编码规则
  2. rsa密钥文件格式
  3. 阮一峰{RSA算法原理-}
  4. 阮一峰{RSA算法原理二}