您好,登录后才能下订单哦!
请求超时!
请点击 重新获取二维码 对称加密中,加密和解密使用相同的密钥,因此必须向解密者配送密钥,即密钥配送问题。而非对称加密中,由于加密和解密分别使用公钥和私钥,而公钥是公开的,因此可以规避密钥配送问题。非对称加密算法,也称公钥加密算法。
1977年,Ron Rivest、Adi Shamir、Leonard Adleman三人在美国公布了一种公钥加密算法,即RSA公钥加密算法。RSA是目前最有影响力和最常用的公钥加密算法,可以说是公钥加密算法的事实标准。
使用M和C分别表示明文和密文,则RSA加密、解密过程如下:
其中e、n的组合(e, n)即为公钥,d、n的组合(d, n)即为私钥。当然e、d、n并非任意取值,需要符合一定条件,如下即为e、d、n的求解过程。
e、d、n的求解过程,也即生成密钥对的过程。涉及如下步骤:
1、取两个大质数(也称素数)p、q,n = pq。
2、取正整数e、d,使得ed mod (p-1)(q-1) = 1,也即:ed ≡ 1 mod (p-1)(q-1)。
e和d是模(p-1)(q-1)的乘法逆元,仅当e与(p-1)(q-1)互质时,存在d。
举例验证:
1、取p、q分别为13、17,n = pq = 221。
2、而(p-1)(q-1) = 12x16 = 192,取e、d分别为13、133,有13x133 mod 192 = 1
取明文M = 60,公钥加密、私钥解密,加密和解密过程分别如下:
ed mod (p-1)(q-1) = 1,已知e和(p-1)(q-1)求d,即求e对模(p-1)(q-1)的乘法逆元。
如上面例子中,p、q为13、17,(p-1)(q-1)=192,取e=13,求13d mod 192 = 1中的d。
13d ≡ 1 (mod 192),在右侧添加192的倍数,使计算结果可以被13整除。
13d ≡ 1 + 192x9 ≡ 13x133 (mod 192),因此d = 133
其他计算方法有:费马小定律、扩展欧几里得算法、欧拉定理。
由于公钥公开,即e、n公开。
因此破解RSA私钥,即为已知e、n情况下求d。
因ed mod (p-1)(q-1) = 1,且n=pq,因此该问题演变为:对n质因数分解求p、q。
目前已被证明,已知e、n求d和对n质因数分解求p、q两者是等价的。实际中n长度为2048位以上,而当n>200位时分解n是非常困难的,因此RSA算法目前仍被认为是安全实用的。
RSA解密的本质是模幂运算,即:
其中C为密文,(d,n)为私钥,均为超过1024位的大数运算,直接计算并不可行,因此最经典的算法为蒙哥马利算法。而这种计算是比较是耗时的,因此***者可以观察不同的输入对应的解密时间,通过分析推断私钥,称为计时***。而防范RSA计时***的办法,即在解密时加入随机因素,使得***者无法准确获取解密时间。
具体实现步骤如下:
go标准库中解密即实现了对计时***的防范,代码如下:
//加密
//m为明文
//(pub.E, pub.N)为公钥
//c为密文
func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
e := big.NewInt(int64(pub.E))
c.Exp(m, e, pub.N)
return c
}
//解密
//传入random支持防范计时***
func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
if c.Cmp(priv.N) > 0 {
err = ErrDecryption
return
}
if priv.N.Sign() == 0 {
return nil, ErrDecryption
}
var ir *big.Int
if random != nil {
var r *big.Int
for {
//步骤1产生0至n-1之间随机数r
r, err = rand.Int(random, priv.N)
if err != nil {
return
}
if r.Cmp(bigZero) == 0 {
r = bigOne
}
var ok bool
//r的模n的乘法逆元ir,步骤4中使用
ir, ok = modInverse(r, priv.N)
if ok {
break
}
}
bigE := big.NewInt(int64(priv.E))
//计算步骤2中C'
rpowe := new(big.Int).Exp(r, bigE, priv.N) // N != 0
cCopy := new(big.Int).Set(c)
cCopy.Mul(cCopy, rpowe)
cCopy.Mod(cCopy, priv.N)
c = cCopy
}
if priv.Precomputed.Dp == nil {
//步骤3,使用C'计算对应的M'
m = new(big.Int).Exp(c, priv.D, priv.N)
} else {
//略
}
if ir != nil {
//步骤4计算实际的M
m.Mul(m, ir)
m.Mod(m, priv.N)
}
return
}
//代码位置src/crypto/rsa/rsa.go
非对称加密算法,除支持加密外,还可以实现签名。原理如下:
签名:
1、提取消息摘要,使用发送方私钥对消息摘要加密,生成消息签名。
2、将消息签名和消息一起,使用接收方公钥加密,获得密文。
验签:
1、使用接收方私钥对密文解密,获得消息和消息签名。
2、使用发送方公钥解密消息签名,获得消息摘要。
3、使用相同办法重新提取消息摘要,与上一步中消息摘要对比,如相同则验签成功。
附示意图如下:
//签名
func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []byte) ([]byte, error) {
//哈希提取消息摘要
hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
if err != nil {
return nil, err
}
tLen := len(prefix) + hashLen
k := (priv.N.BitLen() + 7) / 8
if k < tLen+11 {
return nil, ErrMessageTooLong
}
// EM = 0x00 || 0x01 || PS || 0x00 || T
em := make([]byte, k)
em[1] = 1
for i := 2; i < k-tLen-1; i++ {
em[i] = 0xff
}
//整合消息摘要和消息体
copy(em[k-tLen:k-hashLen], prefix)
copy(em[k-hashLen:k], hashed)
m := new(big.Int).SetBytes(em)
//使用发送方私钥加密消息摘要和消息体,即为签名
c, err := decryptAndCheck(rand, priv, m)
if err != nil {
return nil, err
}
copyWithLeftPad(em, c.Bytes())
return em, nil
}
//验证签名
func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte) error {
//哈希提取消息摘要
hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
if err != nil {
return err
}
tLen := len(prefix) + hashLen
k := (pub.N.BitLen() + 7) / 8
if k < tLen+11 {
return ErrVerification
}
c := new(big.Int).SetBytes(sig)
//使用发送方公钥解密,提取消息体和消息签名
m := encrypt(new(big.Int), pub, c)
em := leftPad(m.Bytes(), k)
// EM = 0x00 || 0x01 || PS || 0x00 || T
//对比发送方和接收方消息体、以及消息签名
ok := subtle.ConstantTimeByteEq(em[0], 0)
ok &= subtle.ConstantTimeByteEq(em[1], 1)
ok &= subtle.ConstantTimeCompare(em[k-hashLen:k], hashed)
ok &= subtle.ConstantTimeCompare(em[k-tLen:k-hashLen], prefix)
ok &= subtle.ConstantTimeByteEq(em[k-tLen-1], 0)
for i := 2; i < k-tLen-1; i++ {
ok &= subtle.ConstantTimeByteEq(em[i], 0xff)
}
if ok != 1 {
return ErrVerification
}
return nil
}
//代码位置src/crypto/rsa/pkcs1v15.go
RSA算法中使用了大量数论知识,有关数论知识还有待学习。待续。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
资讯网色即是空2015电影天堂起字的取名丽水网站建设推广用旭字起名seo优化指导沙丁鱼软件大学网站制作课程关于川的网名大安网站制作餐饮商标多少类东养生重庆建设网站哪家好网站建设布局vi设计网站有啥茶叶种植合作协议命理财运测算周易起名算命风水吾家娇妻三生三世枕上电视剧吃什么养身药好网站优化公司报价周易测3d营销型网站建设专家荒岛余生观后感800字周易店铺名称测吉凶郑爽微博经典的情侣网名用父母的姓氏起名字啊琉璃演员表seo自然排名优化少年生前被连续抽血16次?多部门介入两大学生合买彩票中奖一人不认账让美丽中国“从细节出发”淀粉肠小王子日销售额涨超10倍高中生被打伤下体休学 邯郸通报单亲妈妈陷入热恋 14岁儿子报警何赛飞追着代拍打雅江山火三名扑火人员牺牲系谣言张家界的山上“长”满了韩国人?男孩8年未见母亲被告知被遗忘中国拥有亿元资产的家庭达13.3万户19岁小伙救下5人后溺亡 多方发声315晚会后胖东来又人满为患了张立群任西安交通大学校长“重生之我在北大当嫡校长”男子被猫抓伤后确诊“猫抓病”测试车高速逃费 小米:已补缴周杰伦一审败诉网易网友洛杉矶偶遇贾玲今日春分倪萍分享减重40斤方法七年后宇文玥被薅头发捞上岸许家印被限制高消费萧美琴窜访捷克 外交部回应联合利华开始重组专访95后高颜值猪保姆胖东来员工每周单休无小长假男子被流浪猫绊倒 投喂者赔24万小米汽车超级工厂正式揭幕黑马情侣提车了西双版纳热带植物园回应蜉蝣大爆发当地回应沈阳致3死车祸车主疑毒驾恒大被罚41.75亿到底怎么缴妈妈回应孩子在校撞护栏坠楼外国人感慨凌晨的中国很安全杨倩无缘巴黎奥运校方回应护栏损坏小学生课间坠楼房客欠租失踪 房东直发愁专家建议不必谈骨泥色变王树国卸任西安交大校长 师生送别手机成瘾是影响睡眠质量重要因素国产伟哥去年销售近13亿阿根廷将发行1万与2万面值的纸币兔狲“狲大娘”因病死亡遭遇山火的松茸之乡“开封王婆”爆火:促成四五十对奥巴马现身唐宁街 黑色着装引猜测考生莫言也上北大硕士复试名单了德国打算提及普京时仅用姓名天水麻辣烫把捣辣椒大爷累坏了