RSA算法原理

参考:http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
分解质因数计算器:http://www.99cankao.com/numbers/prime-factor.php

先通过两个质数a和b得到c,c为a与b的乘积
设a=19,b=23,则c=437
c的互质数个数d(欧拉函数)(a-1)*(b-1)=18*22 = 396

随机选择一个整数e,条件是1< e < φ(c),且e与φ(c) 互质。
比如可设e=611<61

根据 ef ≡ 1 (mod φ(c))
计算e对于φ(c)的模反元素f
61*f + 396*k = 1
61*13 + 396*-2 = 1
所以f=13,到此c=437,d=396,e=61,f=13

如果把e c 当成公钥,那f c就是私钥

加密过程:
x=12
x^e%c=y
x的e次方与c求余得到的余数即为密文
12^61%437=354
y=354
解密过程:
y=354
y^f%c=x
354^13%437=12
x=12

发表评论

电子邮件地址不会被公开。 必填项已用*标注