互质
- 两个正整数，除了1以外，没有其他公因子
- 任意两个质数构成互质关系，比如13和61。
- 一个数是质数，另一个不是它的倍数，则互质，比如3和10。
- 较大的那个数是质数，则互质，比如97和57。
- 1和任意一个自然数是都是互质关系，比如1和99。
- p是大于1的整数，则p和p-1构成互质关系，比如57和56。
- p是大于1的奇数，则p和p-2构成互质关系，比如17和15
欧拉函数 ^次方
- 计算在小于等于n的正整数之中，有多少个与n构成互质关系的函数
- φ(1) = 1，1与任何数（包括自身）都构成互质关系
- 质数n，则 φ(n)=n-1，质数与小于它的每一个数互质
- n = p^k (p为质数，k>=1的整数)，φ(p^k) = p^k - p^(k-1) = p^k * (1-1/p),因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
- n = p1 × p2 (p1 p2 互质)，φ(n) = φ(p1p2) = φ(p1)φ(p2)
- 因为任意一个大于1的正整数，都可以写成一系列质数的积。根据上面的公式得φ(n)=φ(1-1/p1)φ(1-1/p2)…φ(1-1/pr)
欧拉定理 ^次方 % 取余
- 正整数a与n互质，则a^φ(n) % n = 1
模反元素 ^次方 % 取余
- 正整数a与n互质 则一定有整数b使 a*b % n = 1 从欧拉定理可证明，a^φ(n) = a * a^(φ(n)-1) 所以a^(φ(n)-1)就是一个b，但不止这一个
RSA ^次方 % 取余
- 选两个不等质数p、q，则n=p*q、φ(n)=(p-1)(q-1)
- 取e使 1<e<φ(n) 且与 φ(n) 互质 一般都是选 65537
- 计算模反元素d 即 ed % φ(n) = 1
- 公钥为{n e} 私钥为{n d}
- 信息m, m^e % n = c 则c为密文 m必须小于n
- c^d % n = m
加密是的填充规则
- RSA_PKCS1 原文比n少11字节，输出与n相同长度
- RSA_PKCS1_OAEP 比n少41字节，输出与n相同长度
RSA破解
- 通过{n e} 计算 {n d} 由于 ed % φ(n) = 1 因此需要计算φ(n)
- 由于 φ(n) = (p-1)(q-1) 只有知道p q才能知道φ(n)
- 由于 n = p * q 需要因数分解，但是大数很难
openssl
- ssh-keygen -y -f prikey.pem > pubkey.pub
- openssl genrsa -f4 -des -out prikey.pem -passout pass:123456 2048 生成密钥 -f4 指定公钥E为f4(-3 指定公钥E为3)、des指定加密方式(des3 aes128 aes192 aes256)、out指定输出文件、passout pass:指定密码、 2048指定位长度
- openssl genpkey -algorithm RSA -out keypair.der -pkeyopt rsa_keygen_bits:2048 -outform DER
- openssl req -x509 -days 365 -newkey rsa:2048 -keyout prikey.pem -out public.pem -nodes
- openssl rsa -in prikey.pem -pubout -out pubkey.pub 提取公钥
- openssl rsa -in keypair.der -inform DER -out keypair.pem DER转PEM
- openssl rsa -in privkey.pem -passin pass:123456 -des -out privkey.pem 去密码
- openssl pkcs8 -topk8 -inform PEM -outform DER -in rsa.key -out pkcs8.key -nocrypt PEM转DER
- ssh-keygen -i -m PKCS8 -f pubkey.pub > pubkey.pub 将PEM、PKCS8、RFC4716 转 openssh格式
- ssh-keygen -e -m PEM -f pubkey.pub > pubkey.pub 将openssh转PEM、PKCS8、RFC4716格式
- openssl req -x509 -new -days 365 -key key.pem -out cert0.crt 自签名证书生成
