背景：
前两天某个云盘直链下载的油猴脚本突然不可用之后（后来恢复了），想着依赖别人不如依赖自己，于是决定自己研究一下获取阿里云盘文件的直链。
阿里云的文档还是很全的，很快就找到了api接口，需要access_token鉴权（这个token是JWT格式的，里面的签名算法不出所料是RSA），想做一个token自动刷新的功能，于是抄了之前openai_token的代码。
重点来了，在检查token是否可用时，我突然意识到其实我并没有对应的公钥，那么只能简单的校验一下token中的过期时间，并不能使用公钥验签，虽然不影响使用，但这个情况令我感到不爽。想起来之前openai的access_token也是一样的场景，当时是始皇告诉我的公钥（感谢neo），目前好像并没有渠道获取这个公钥。那么回到本贴主题，这里分享一种根据RSA签名逆推公钥的方法。
正文开始：
关于RSA的原理在此就不再赘述了，有兴趣可以看这里
RSA密钥的参数包括p、q、e、d、n，为了方便描述，后续会延用这些名称。
RSA签名过程用一个公式表示:
signature = encode((hash(message))) ^ d mod n
验签：
encode((hash(message))) = signature ^ e mod n
其中，hash算法和encode编码方式可以从access_token的headers中得到，具体可以参考RFC文档，
签名时用到的d我们是不知道的，但是验签时的e不出意外一般是65537，只需要求出n我们就能构造公钥了。
先分析一下token结构，这是一个JWT格式的token：
eyJ0eXAiOiJKV1QiLCJhbGciOiJSUzI1NiJ9.eyJzdWIiOiJhNmRiMjJmZGQ4MWY0NTM0OTE0NzI0MmNhMzBmYzE3YyIsImF1ZCI6Ijc2OTE3Y2NjY2Q0NDQxYzM5NDU3YTA0ZjYwODRmYjJmIiwiZXhwIjoxNzIzODEyMjUwLCJpYXQiOjE3MTYwMzYyNTAsImp0aSI6Ijc1NzMyZGNhMGI3MTQyNzk4ZWM5YTY4ZjVlNDMxNjIxIn0.SwG-1qoCMaTnmugOnYBXA4w5QqveD_wxc3oSRxbU_i5qjLxX2SvUFJrqSPtO6nPeElWiqJfK3qeOap38Y1V79Q
JWT由header、payload、signature三部分组成，并用.间隔开，signature是对前面部分进行rsa签名之后再经过base64编码得到的；header、payload使用base64解码后，是json结构，其中header包含着签名相关的算法：
header:
{"typ":"JWT","alg":"RS256"}
RS256对应的hash算法是SHA256，填充编码方式是PKCS1-v1_5，签名对应的message是：
eyJ0eXAiOiJKV1QiLCJhbGciOiJSUzI1NiJ9.eyJzdWIiOiJhNmRiMjJmZGQ4MWY0NTM0OTE0NzI0MmNhMzBmYzE3YyIsImF1ZCI6Ijc2OTE3Y2NjY2Q0NDQxYzM5NDU3YTA0ZjYwODRmYjJmIiwiZXhwIjoxNzIzODEyMjUwLCJpYXQiOjE3MTYwMzYyNTAsImp0aSI6Ijc1NzMyZGNhMGI3MTQyNzk4ZWM5YTY4ZjVlNDMxNjIxIn0
那么对于公式：
encode((hash(message))) = signature ^ e mod n
可以简化表达成：
M = S mod n
其中M、S和token是对应的，唯一的未知数是n。
转化成小学二年级学过的表达方式：
S = a * n + M
其中多了一个未知系数a，这个二元一次方程貌似解不了，没事，咋多弄几个token，将其变成一组方程再说：
S1 = a1 * n + M1
S2 = a2 * n + M2
...
显然，形如 S - M 的表达式均为n的倍数，这些表达式显然是和token一一对应的，咱们只需要多弄几个token，只要运气不差，a1、a2、a3、a4...没有公共的质因子（懒得证明了，反正token数量越多概率越小就完事了），就能够通过计算 a1*n、a2*n、a3*n、a4*n... 的最大公约数（gcd）得到对应的n，实际上使用3个token既可以稳定计算出正确的n。
多说一句，a1、a2、a3、a4...的公共的质因子，大概率分布在质数序列首部（越往后概率越小，同样懒得证明），所以即使运气很差，得到的是n的一个倍数，只需要维护一个短的质数首部序列，在计算gcd时将其试除，即可在只有少量token的情况下（2个就行）计算出正确的n。
给个参考运行时间：
| RSA密钥长度 | 计算时间（单位：s) |
|---|---|
| 512 | 6 |
| 2048 | 30 |
最后贴个github项目地址：
觉得有用的话记得给我项目点个star 
，带佬伟大无需多盐 
