攻防世界-新手练习-easy_RSA

冷不防 2023-01-11 03:37 191阅读 0赞

## 【题目描述】 ##

flag格式为cyberpeace\{小写的你解出的答案\}

## 【附件】 ##

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17，求解出d。

## 【思路】 ##

关于RSA的算法原理[阮一峰的博客![icon-default.png?t=L892][icon-default.png_t_L892]https://www.ruanyifeng.com/blog/2013/06/rsa\_algorithm\_part\_one.html][icon-default.png_t_L892_icon-default.png_t_L892_https_www.ruanyifeng.com_blog_2013_06_rsa_algorithm_part_one.html]这里有深入浅出的介绍，推荐前往观看。

这里我直接给出RSA密钥对生成具体的**计算规则**：

> 1.  选取两个安全大素数p和q（“大”指的是长度要长，目前推荐至少为1024比特）
> 2.  计算乘积n=p\*q，以及n的欧拉函数φ(n) = (p-1)(q-1)；
> 3.  随机选取整数e，要求1< e < φ(n)，且e与φ(n)互素；
> 4.  用欧几里得拓展算法（也叫辗转相除法）计算e对φ(n)的模反元素。
> 
> （所谓“模反元素”指的就是存在整数d，使得ed被φ(n)除的余数为1。）

举个例子，假设p=13，q=17，计算d。

*  n=p\*q=13\*17=221；则φ(n) = (p-1)(q-1)=192；
 *  选取公钥e=11（一般为素数），满足1< e < φ(n)，且e与φ(n)互素；
 *  通过欧几里得拓展算法求得满足公式d\*e=1(mod 192)的d=35。

**这里给出手算的过程，便于理解算法：**

辗转相处得，

192=17\*11+5

11 = 5\*2+1

2 = 2\*1

由上式逆推可得，

1 = 11-5\*2

5 = 192-17\*11

于是，

1 = 11-5\*2 = 11-(192-17\*11)\*2=11\***35** \+ 192\*(-1)

所以，得到公钥(e,n)为(11,221)，私钥d为**35**。

攻防世界的题由于数值较大手算困难，求逆元的代码如下：

#include <iostream>
    
    using namespace std;
    
    #define ll long long
    
    ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法 
    
    {
    
        if(b==0)
    
        {
    
            x=1,y=0;
    
            return a;
    
        }
    
        ll ret=exgcd(b,a%b,y,x);
    
        y-=a/b*x;
    
        return ret;
    
    }
    
    ll getInv(ll a,ll mod)//求a在mod下的逆元，不存在逆元返回-1 
    
    {
    
        ll x,y;
    
        ll d=exgcd(a,mod,x,y);
    
        return d==1?(x%mod+mod)%mod:-1;
    
    }
    
    int main()
    
    {
    
        ll p,q,n,mod,e;
    
        p=473398607161;
    
        q=4511491;
    
        e=17;
    
        n=p*q;//素数乘积
    
        mod=(p-1)*(q-1);//欧拉函数
    
        cout << getInv(e, mod) << endl;
    
        return 0;
    
    }

## 【答案】 ##

cyberpeace\{125631357777427553\}

**如果文章对你有帮助，麻烦动动手指点赞、喜欢、支持一下咖啡猫，谢谢！**

[icon-default.png_t_L892]: https://csdnimg.cn/release/blog_editor_html/release1.9.1/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=L892
[icon-default.png_t_L892_icon-default.png_t_L892_https_www.ruanyifeng.com_blog_2013_06_rsa_algorithm_part_one.html]: https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html