rsa
数论事实
两个大质数相乘，只需要最多两个数字长度的乘积的复杂度，而把两个质数乘积进行拆分可能要 其中较小数字的时间复杂度。也就是易于验证，难于破解。
假设两个长度为2048(二进制下)的质数相乘，最多只需要 2048 x 2048的时间，而枚举拆分需要2^2048的时间, 目前最快的？gnfs算法的复杂度也是
$O(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}})$
加解密
加密
$C=M^e \bmod n$
n=pq,其中p和q为大质数
M 要加密的信息 (需要 和n互质也就是至少p,q其中一个互质,1/pq 当质数足够大时碰撞概率极小，其实因为公钥信息里已经有n了，也不会碰撞)
e 和 (p-1)(q-1)互质，简单些 e直接取小于 (p-1)(q-1)的质数
公钥(e,n), 所有人都知道
解密
私钥匙$(e,p,q)$
$de = 1 \bmod ((p-1)(q-1))$,计算d,d是e关于(p-1)(q-1)的乘法模逆元 log 级别复杂度
$ C^d = (M^e)^d = M^{ed} = M^{1+k(p-1)(q-1)} (\bmod n)$
费马小定理:p质数,a和p互质,$a^{p-1} = 1 (\bmod p)$
如果 M 和p 互素, 有 $C^d = M\cdot (M^{p-1})^{k(q-1)} = M \cdot 1^{k(q-1)} = M \cdot 1 = M (mod p)$ 即是 $ C^d - M = 0 (mod p) $
否则 $ M = 0 \bmod p$, $ C^d = (M^e \bmod n)^d = (0^e)^d = 0 (\bmod p) $,也有 $C^d - M = 0(\bmod p)$
同理 有$C^d - M = 0 (\bmod q)$
因此 $C^d - M = 0 (\bmod (n=pq))$即$C^d = M (\bmod n)$
也就是 我们通过幂次直接拿到 M在$\bmod n$的意义下
安全
也就是公钥里只有(e,n), 计算不出p和q, 就意味着计算不出(p-1)(q-1),也就计算不出d，也就无法直接d的幂次。
另一个问题就是 模运算 是否有办法开e次根。
在就是历史信息，如果有人（机器）能拆解n，那么所有用到相应公私钥的信息都能被破解了。
所以据说 现在512位的似乎已经被认为不安全了。可以类似NFS, GNFS,SIQS, 和ECM 定向爆破。https://blog.csdn.net/tigerisland45/article/details/51348854
穷举自己可以按(10^10) 需要1台计算机一秒来估计，是不可能的。例如枚举需要 2**512//(10**10)//60//60//24//365 = 42515880041674902015392012297710065092210064119077858250011293263957902175524946019792853558367907875729426237273230754863501657825807236 台计算机 年
而好处是，如果始终拆解质数乘积是难的，那么只需要单纯的增加位数即可，这样在实现上的额外代价就是生成代价，对应的拆解代价是按照幂次增长。
而生成的代价,解密的代价较大，注定了它用在少量数据，而剩余的数据加密，还是要靠对称加密。
使用
产生3072 bits的私钥(不要分享)
openssl genrsa -out private.pem 3072
通过私钥产生公钥(可以给任何人)
openssl rsa -in private.pem -out public.pem -outform PEM -pubout
产生原始消息(模拟要给你发信息的人)
echo 'too many secrets' > file.txt
通过你提供的公钥加密(并把加密后的信息发给你)
openssl rsautl -encrypt -inkey public.pem -pubin -in file.txt -out file.ssl
你通过私钥解密
openssl rsautl -decrypt -inkey private.pem -in file.ssl -out decrypted.txt
查看消息
cat decrypted.txt
如何使用ssh-keygen 生成的公私钥
众所周知，一般上个git之类都会用openssh提供的 ssh-keygen生成公私钥。但是公钥不能像上面那样直接用
方法是用id_rsa.pub 转换，生成一个openssl能使用的PEM格式再用
ssh-keygen -f ~/.ssh/id_rsa.pub -e -m PKCS8 > id_rsa.pem.pub
剩余的操作和上面一样
contact
加密联系我
id_rsa.pub
1 | ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABgQDgFNXLxLccaE5w6GBHwg+sqXXphmEDgxjTQj6UYgu1et0yIqY2NU6ouAp91SnQAsW6htF1g6X7SjVuW4cgN+3R4nCociNBwvzPIiUbInhn1J5oaI3wRktWLOlxqUO1ykvsCjoZty+wfMvy5zFnG6+bjkn3i0WfCNoEOiHuaOJd+dt0l0Kha6+QdIHj6zLPH65y/oW5WJWe4iZoOjmBKJ+Ps9oGVMJxOZDCTWCUJQV1DFZgo7WAkT2/Thfz390sNiuclDE6rpmLPAqCGjtOO4zhoUpwq35QmTNjlg5PutM6s+SQZMnX2ZKgkUV/QWNenC40yS/L0Sj57ZCHvbEenh8v4YC4YRcW2BrdSloaPmhne1tH5xpw/By7UKAG/S3liebb5B3tjLpvjI0EU8l6/I6JxAtYe19tKpDPC/J1Z1L1nQ//rjDiVayg0u4Ti1grngTcTogTU9ttvwGFgdBCBkI/4xQB8kkSXllMLf2AmocFjyU/TFa1fgw+PBv8Ydi+T48= yexiaorain@gmail.com |