概念
1、互质关系: 两个数除了1,没有其他公因数,则两个数互质数
2、欧拉函数: 任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?
计算这个值的方式叫做欧拉函数;用𝞅(n)表示;
如 计算8的欧拉函数𝞅(8) 1、3、5、7,故𝞅(8) = 4, 计算7的欧拉函数𝞅(7) 1、2、3、4、 5、6故𝞅(7) = 6
计算56的欧拉函数𝞅(56) = 𝞅(8) * 𝞅(7) = 24
欧拉函数的特点:
1、当n为质数的时候,𝞅(n) = n-1
2、如果n可以分解成两个互质的整数之积,如n=A*B则:𝞅(n) = 𝞅(A) * 𝞅(B)
根据以上两点得到: 如果N是两个质数P1和P2的乘积则 𝞅(N) = (P1-1) * (P2-1)
欧拉定理:
如果两个正整数m和n互质,那么m的𝞅(n)次方减去1,可以被n整除. m**𝞅(n) % n = 1
例: m = 3、n = 5互质, (3**4 - 1) % 5 = 0
费马小定理:
欧拉定理的特殊情况:如果两个正整数m和n互质,而且n为质数!那么𝞅(n)结果就是n-1 . m**(n-1) % n = 1
模反元素:
如果两个正整数e和x互质,那么一定可以找到整数d,使得ed-1被x整除. (e*d - 1)% x = 0, 那么d就是e对于x的模反元素
RSA数学原理
上世纪70年代产生的一种加密算法.其加密方式比较特殊,需要两个密钥;公开密钥简称公钥(publickey),私有密钥简称私钥(privatekey),公钥加密,私钥解密;私钥加密,公钥解密;这个算法就是伟大的RSA;
m**5%n = c 加密 c**d%n = m 解密
公钥:n+e 私钥n+d 明文m 密文c
生成p1和p2两个质数 , n = p1*p2, 𝞅(n) = (p1-1)*(p2-1), 再由𝞅(n)算出e和d
用终端生成公私钥命令行
私钥: $openssl genrsa -out private.pem 1024
公钥: $openssl rsa -in private.pem -pubout -out public.pem
加密 : $openssl rsautl -encrypt -in msg.text -inkey public.pem -pubin -out enc.text
解密 : $openssl rsautl -decrypt -in enc.text -inkey private.pem -out dec.text
请求一个证书: $openssl req -new -key private.pem -out rsacert.csr
证书签名: $openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt
生成p12文件: $openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt
base64: 可以将任意的二进制数据进行编码. 0~9、a~z、A~Z、+、/、=(补空位)
RSA总结:
