[数据结构与算法]【Educoder】密码学理论与实战 30+完整过题代码

超全内容(除了前面3个)都放一起了，方便看~
整理不易，如果对你有用，不妨滑下去给个三连😋

1 2 3暂时没布置，就没写~如果有需要可以评论区留言

1 古典密码学

1-1经典密码体制(上)

1-2经典密码体制(下)

2 Shannon理论

2-1Shannon理论

3 分组密码与高级加密标准

3-1分组密码与高级加密标准(一)

3-2分组密码与高级加密标准(二)

3-3分组密码与高级加密标准(三)

4 Hash函数

4-1Hash函数

第1关：Hash函数的安全性

任务描述

Hash，一般翻译为散列、杂凑，或音译为哈希，是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
本关任务：给定输入的_x_和_y_，输出线性函数的_Hash_值。

#include<bits/stdc++.h>
using namespace std;
int X1,Y1,f1;
int X2,Y2,f2;
int X3,Y3;
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    cin>>X1>>Y1>>f1;
    cin>>X2>>Y2>>f2;
    cin>>X3>>Y3;
    /*********** Begin ***********/
    int resB=(f1*X2-f2*X1)/(Y1*X2-Y2*X1);
    int resA=(f1*Y2-f2*Y1)/(Y2*X1-Y1*X2);
    cout<<resA*X3+resB*Y3<<endl;
    /*********** End ***********/
    return 0;
}

第2关：随机预言模型中的算法

任务描述

1993年，Bellare 和 Rogaway 两位学者正式提出了随机预言模型（Random OracleModel，ROM）方法论，使得过去纯做理论研究的可证明安全方法论迅速在实际应用领域取得重大进展，一大批快捷有效的安全方案相继提出，同时，还产生了“具体安全性（concrete security or exact security）”。其意义在于，我们不再仅仅满足安全性的渐近度，而且可以确切地得到较准确的安全度量。
本关任务：编写一个能计算碰撞成功率的程序。

#include<bits/stdc++.h>
using namespace std;
int M,q;
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    cin>>M>>q;
    /*********** Begin ***********/
    double E=1;
    for(int i=1; i<q; i++){
        E*=(M-i)*1.0/M;
    }
    printf("%.2f\n",1-E);
    /*********** End ***********/
    return 0;
}

第3关：Merkle-Damgard结构

任务描述

因为所需的安全散列长度越来越长，所以我们可以使用有限定义域上的散列函数（俗称压缩函数）通过迭代方式拓展为具有无限定义域的散列函数。而最为代表性的就是 Merkle-Damgard 结构。 本关任务：编写计算_compress_最多被计算的次数的程序。

#include<bits/stdc++.h>
using namespace std;
int n,t;
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
        cin>>n>>t;
        /*********** Begin ***********/
        int ans = -1;
        if(t>=2){
            ans = (1+(int)ceil(n/(t-1)));
        }else {
            ans = (2*n+2);
        }
        printf("%d\n",ans);
        /*********** End ***********/
    return 0;
}

5 RSA密码体制和整数因数分解

5-1 RSA的一些数论知识

第1关：欧几里得算法

任务描述

欧几里德算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里德在其著作《TheElements》中最早描述了这种算法，所以被命名为欧几里德算法。
本关任务：用扩展欧几里得算法求解逆元。

#include <bits/stdc++.h>
using namespace std;
/*********** Begin ***********/
int gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int ans=gcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
/*********** End ***********/
int a,b; //用欧几里得算法求解a关于b的逆元
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    cin>>a>>b;
    /*********** Begin ***********/
    int x,y;
    gcd(a, b, x, y);
    while(x<0)
        x+=b;
    cout<<x<<endl;
    /*********** End ***********/
    return 0;
}

第2关：中国剩余定理

#任务描述

中国剩余定理又叫孙子定理，孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元 5 世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下： 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。 本关任务：求解给定模方程组的解。

#include<bits/stdc++.h>
using namespace std;
/*********** Begin ***********/

//扩展欧几里得算法
void gcd(int a,int b,int &d,int &x,int &y)
{
    if(b==0)
    {
        d=a;
        x=1,y=0;
    }
    else //else不能省略
    {
        gcd(b,a%b,d,y,x);
        y-=(a/b)*x;
    }
}
//中国剩余定理
int China(int n,int *m,int *a)
{
    int M=1,d,y,x=0;
    for(int i=0; i<n; i++)
        M*=m[i];
    for(int i=0; i<n; i++)
    {
        int w=M/m[i];
        gcd(m[i],w,d,d,y);
        x=(x+y*w*a[i])%M;
    }
    return (x+M)%M;
}
/*********** End ***********/
//在下面Begin和End之间补全代码，输出相应的结果
int m[15],a[15];
int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>m[i]>>a[i];
    /*********** Begin ***********/
    cout<<China(n,m,a)<<endl;
    /*********** End ***********/
    return 0;
}

第3关：拉格朗日定理

任务描述

拉格朗日定理存在于多个学科领域中，分别为：微积分中的拉格朗日中值定理；数论中的四平方和定理；群论中的拉格朗日定理 (群论)，这里提出群论中的拉格朗日定理。
本关任务：计算一个素数 _p_的所有本原元素。

#include<bits/stdc++.h>
using namespace std;
int p;
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    cin>>p;
    /*********** Begin ***********/
    for(int i=2; i<p; i++)
    {
        if(__gcd(p-1,i)==1)
            cout<<i<<' ';
    }
    cout<<endl;
    /*********** End ***********/
    return 0;
}

5-2 RSA密码体制

第1关：RSA密码体制

任务描述

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的，当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
本关任务：对输入的明文进行 RSA 加密。

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
ll n,b,x;
/*********** Begin ***********/
ll solve(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y%2)
            ans*=x;
        y/=2;
        x*=x;
        while(ans>=n)
            ans-=n;
        while(x>=n)
            x-=n;
    }
    return ans%n;
}
/*********** End ***********/
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    cin>>n>>b>>x;
    /*********** Begin ***********/
    cout<<solve(x,b)<<endl;
    /*********** End ***********/
    return 0;
}

第2关：素性检测

任务描述

素数又称质数，是在大于 1 的整数中，只能被 1 和其自身整除的数。素性测试是检验一个给定的整数是否为素数的测试。
本关任务：计算并输出模一个奇素数的二次剩余。

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
int MAP[maxn];
vector<int>G;
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    int p;
    cin>>p;
    /*********** Begin ***********/
    for(int i=1; i<p; i++)
        if(!MAP[i*i%p]&&i*i%p!=0)
        {
            G.push_back(i*i%p);
            MAP[i*i%p]++;
        }
    sort(G.begin(),G.end());
    for(auto &it:G)
        cout<<it<<' ';
    cout<<endl;
    /*********** End ***********/
    return 0;
}

第3关：二次剩余

任务描述

二次剩余是数论基本概念之一。它是初等数论中非常重要的结果，不仅可用来判断二次同余式是否有解，还有很多用途。C.F.高斯称它为算术中的宝石，他一人先后给出多个证明。
本关任务：利用_Miller_?_Rabin_算法判断给定的数是否是素数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF_INT=0x3f3f3f3f;
const LL INF_LL=0x3f3f3f3f3f3f3f3f;
/*********** Begin ***********/
//防爆乘法
LL q_muti(LL a,LL b,LL p)
{
    LL res=0;
    a%=p;
    while(b)
    {
        if(b&1)
            res=(res+a)%p;
        a=(a<<1)%p;
        b>>=1;
    }
    return res;
}
LL q_power(LL a,LL b,LL p)
{
    LL res=1;
    a%=p;
    while(b)
    {
        if(b&1)
            res=q_muti(res,a,p);
        a=q_muti(a,a,p);
        b>>=1;
    }
    return res;
}
bool m_l(LL x,LL a)
{
    if(q_power(a,x-1,x)!=1)
        return false;
    LL q=x-1;
    while(!(q&1))
    {
        q>>=1;
        LL t=q_power(a,q,x);
        if(t==1)
            continue;
        if(t==x-1)
            break;
        return false;
    }
    return true;
}
bool is_prime(LL x)
{
    if(x==0||x==1)
        return false;
    if(x==2||x==3)
        return true;
    else
    {
        int k=10; //设置测试底数个数
        for(int i=0; i<k; i++)
        {
            LL a=rand()%(x-3)+2;
            if(!m_l(x,a))
                return false;
        }
        return true; //所有底数测试通过即可判为质数
    }
}
/*********** End ***********/
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    LL n;
    cin>>n;
    /*********** Begin ***********/
    if(is_prime(n))
        cout<<"YES\n";
    else
        cout<<"NO\n";
    /*********** End ***********/
    return 0;
}

5-3 整数因数分解方法

第1关：Pollard ρ方法

任务描述

波拉德的 ρ 算法是整数分解的一种算法，是约翰 · 波拉德在1975年发明的。它只占用了很少的空间，并且它的预期运行时间与被分解的合数的最小质因数大小的平方根成正比。 本关任务：编写一个程序计算给定 n 的“尾巴”和“圈”。

#include<bits/stdc++.h>
using namespace std;
map<int,int>MAP;
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    int n,p;
    cin>>n>>p;
    /*********** Begin ***********/
    int Y=1,i=1;
    MAP.clear();
    while(1)
    {
        if(MAP[Y])
        {
            cout<<i-MAP[Y]<<' '<<MAP[Y]<<endl;
            break;
        }
        MAP[Y]=i++;
        Y=(Y*Y+1)%p;
    }
    /*********** End ***********/
    return 0;
}

第2关：Dixon的随机平方算法

任务描述

_Dixon_的随机平方算法也是一种有效的因子分解方法。 本关任务：根据输入的_n_以及同余方程输出_n_的一个因子。

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    ll n,l=1,r=1;
    ll A,B;
    int m;
    cin>>n>>m;
    /*********** Begin ***********/
    for(int i=0; i<m; i++)
    {
        cin>>A>>B;
        l=l*A%n;
        r=r*B%n;
    }
    cout<<__gcd(l-(ll)sqrt(r),n)<<endl;
    /*********** End ***********/
    return 0;
}

第3关：二次筛法

任务描述

二次筛法是由_Pomerance_提出的一个非常著名的并在实际中广泛应用的算法。 本关任务：编写一个简单的素数筛法，求解小于等于_n_所有素数。

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long  long
int vis[1000];
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    int n;
    cin>>n;
    /*********** Begin ***********/
    memset(vis,0,sizeof(vis));
    for(int i=2; i<=n; i++)
    {
        if(vis[i])
            continue;
        for(int j=2*i; j<=n; j+=i)
            vis[j]=1;
    }
    for(int i=2; i<=n; i++)
        if(!vis[i])
            cout<<i<<' ';
    cout<<endl;
    /*********** End ***********/
    return 0;
}

6 对RSA的攻击

6-1对RSA的攻击

第1关：计算φ(n)

任务描述

在数论中，对给定的正整数_n_，欧拉函数是小于或等于_n_的正整数中与_n_互质的数的数目（因此_?_(1)=1）。
本关任务：根据输入的_n_和_?_(n)，求解两个因子。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    ll n,phi;
    cin>>n>>phi;
    /*********** Begin ***********/
    ll p=((n-phi+1)+sqrt((n-phi+1)*(n-phi+1)-4*n))/2;
    ll q=n/p;
    if(p>q)
        swap(p,q);
    cout<<p<<' '<<q<<endl;
    /*********** End ***********/
    return 0;
}

第2关：中国剩余定理

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    ll n,a,b,c,d;
    cin>>n;
    cin>>a>>b>>c>>d;
    /*********** Begin ***********/
    int p=__gcd(b+1,n);
    int q=__gcd(c+1,n);
    if(p>q)
        swap(p,q);
    cout<<p<<' '<<q<<endl;
    /*********** End ***********/
    return 0;
}

第3关：Wiener的低解密指数攻击

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    double a,b,c,d;
    cin>>a>>b>>c>>d;
    /*********** Begin ***********/
    if(abs(a/b-c/d)<1/(2*d*d))
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    /*********** End ***********/
    return 0;
}

6-2衍生密码体制

第1关：Rabin密码体制

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    int n,x;
    cin>>n>>x;
    /*********** Begin ***********/
    cout<<x*x%n<<endl;
    /*********** End ***********/
    return 0;
}

第2关：RSA的语义安全

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
char h[100];
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    int n;
    scanf("%s",h);
    scanf("%d",&n);
    /*********** Begin ***********/
    int s=strlen(h),x=0;
    double l=0,r=n,mid;
    while(x<s)
    {
        mid=(l+r)/2;
        if(h[x]=='1')
            l=mid;
        else
            r=mid;
        x++;
    }
    printf("%d\n",(int)floor(mid));
    /*********** End ***********/
    return 0;
}

7 基于离散对数的密码体制

7-1几种基于离散对数的密码体制

第1关：ElGamal密码体制

任务描述

在密码学中，ElGamal_加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法，它在1985年由塔希尔·盖莫尔提出 。 本关任务：对给定的明文_x，利用_ElGamal_密码体制进行加密。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
/*********** End ***********/
int main()
{
    ll p,alp,a,x,k;
    cin>>p>>alp>>a>>x>>k;
    /*********** Begin ***********/
    cout<<quick(alp,k,p)%p<<' '<<x*quick(quick(alp,a,p),k,p)%p<<endl;
    /*********** End ***********/
    return 0;
}

第2关： Shanks算法

任务描述

_Shanks_算法是一个求解离散对数的算法。
本关任务：给定相关参数，求解_Shanks_算法里面的表_L_1和表_L_2。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
/*********** End ***********/
int main()
{
    ll p,alp,beta;
    cin>>p>>alp>>beta;
    /*********** Begin ***********/
    ll s=ceil(sqrt(p-1));
    ll k=quick(alp,s,p);
    ll ans=1;
    for(int i=0; i<s; i++)
    {
        cout<<'('<<i<<' '<<ans<<')';
        if(i==s-1)
            cout<<'\n';
        else
            cout<<' ';
        ans=ans*k%p;
    }
    ans=1;
    for(int i=0; i<s; i++)
    {
        cout<<'('<<i<<' '<<beta*quick(ans,p-2,p)%p<<')';
        if(i==s-1)
            cout<<'\n';
        else
            cout<<' ';
        ans=ans*alp%p;
    }
    /*********** End ***********/
    return 0;
}

第3关：指数演算法

任务描述

指数演算法是一种计算离散对数的算法。 本关任务：给定_a_和_p_，求解_logab_ mod p。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
ll A[10];
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
/*********** End ***********/
int main()
{
    ll a,p,l2,l3,l5,l7,b;
    cin>>a>>p>>l2>>l3>>l5>>l7>>b;
    memset(A,0,sizeof(A));
    /*********** Begin ***********/
    ll s=7736;
    ll ans=b*quick(a,s,p)%p;
    for(int i=2;; i++)
    {
        while(ans%i==0)
        {
            A[i]++;
            ans/=i;
        }
        if(ans==1)
            break;
    }
    cout<<(A[2]*l2+A[3]*l3+A[5]*l5+A[7]*l7-s+p-1)%(p-1)<<endl;
    /*********** End ***********/
    return 0;
}

7-2椭圆曲线

第1关：实数上的椭圆曲线

任务描述

椭圆曲线被描述为一个二元方程解的集合。 本关任务：给定椭圆曲线上一点的_x_坐标，求出相应的_y_坐标。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    double a,b,x;
    scanf("%lf%lf%lf",&a,&b,&x);
    /*********** Begin ***********/
    double y=sqrt(x*x*x+a*x+b);
    printf("%.2f %.2f\n",-y,y);
    /*********** End ***********/
    return 0;
}

第2关：模素数的椭圆曲线

任务描述

椭圆曲线被描述为一个二元方程解的集合。模_p_定义的椭圆曲线在公钥密码中非常重要。 本关任务：求解椭圆曲线上两个点的和。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
/*********** End ***********/
int main()
{
    ll a,p,x1,y1,x2,y2,lam;
    cin>>a>>p>>x1>>y1>>x2>>y2;
    /*********** Begin ***********/
    if(x1==x2&&y1==y2)
        lam=(3*x1*x1+a)*quick(2*y1,p-2,p)%p;
    else
        lam=(y2-y1)*quick(x2-x1,p-2,p)%p;
    ll x3=((lam*lam-x1-x2)%p+p)%p;
    cout<<x3<<' '<<((lam*(x1-x3)-y1)%p+p)%p<<endl;
    /*********** End ***********/
    return 0;
}

第3关：点压缩与ECIES

任务描述

点压缩与 ECIES 是优化椭圆曲线上_ElGamal_密码体制的有利工具。
本关任务：实现_PointDecompress_ 函数。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
int vis[20];
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
void  PointDec(ll x,ll i)
{
    ll z=(x*x*x+x+6)%11;
    if(vis[z])
        cout<<"failure"<<endl;
    else
    {
        ll y=(ll)(sqrt(z))%11;
        if(i%2==y)
            cout<<x<<' '<<y<<endl;
        else
            cout<<x<<' '<<11-y<<endl;
    }
};
/*********** End ***********/
int main()
{
    vis[2]=vis[3]=vis[5]=vis[7]=vis[8]=vis[10]=1;
    ll x,i;
    cin>>x>>i;
    /*********** Begin ***********/
    PointDec(x,i);
    /*********** End ***********/
    return 0;
}

第4关：椭圆曲线上点的乘积

任务描述

我们可以利用平方-乘算法在乘法群中有效地计算幂_αa_。 本关任务：把一个十进制的数变成_NAF_表示。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
int bit[100];
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    ll x;
    cin>>x;
    /*********** Begin ***********/
    for(ll i=0; i<63; i++)
    {
        bit[i]=(x&(1LL<<i))?1:0;
    }
    for(int i=0; i<63;)
        if(bit[i]==1&&bit[i+1]==1)
        {
            bit[i]=-1;
            i++;
            while(bit[i]==1)
            {
                bit[i]=0;
                i++;
            }
            bit[i]=1;
        }
        else
            i++;
    int i=62;
    for( ; i>=0; i--)
        if(bit[i]!=0)
            break;
    while(i>=0)
    {
        if(i!=0)
            cout<<bit[i]<<' ';
        else
            cout<<bit[i]<<endl;
        i--;
    }
    /*********** End ***********/
    return 0;
}

8 签名方案

8-1一些签名方案(一)

第1关：RSA签名方案

任务描述

本关任务：计算消息_x_的_RSA_签名。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
ll eular(ll n)
{
    ll ans = n;
    for(int i=2; i*i <= n; ++i)
    {
        if(n%i == 0)
        {
            ans = ans/i*(i-1);
            while(n%i == 0)
                n/=i;
        }
    }
    if(n > 1)
        ans = ans/n*(n-1);
    return ans;
}
/*********** End ***********/
int main()
{
    ll p,q,a,b,x;
    cin>>p>>q>>b>>x;
    /*********** Begin ***********/
    a=quick(b,eular((p-1)*(q-1))-1,(p-1)*(q-1));
//        cout<<a<<endl;
    cout<<quick(x,a,p*q)<<endl;
    /*********** End ***********/
    return 0;
}

第2关：ElGamal签名方案

任务描述

_ElGamal_公钥密码算法是在密码协议中有着重要应用的一类公钥密码算法，其安全性是基于有限域上离散对数学问题的难解性。它至今仍是一个安全性良好的公钥密码算法。它是一个既可用于加密又可用于数字签名的公钥密码体制。
本关任务：计算消息_x_的_ElGamal_签名。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
ll eular(ll n)
{
    ll ans = n;
    for(int i=2; i*i <= n; ++i)
    {
        if(n%i == 0)
        {
            ans = ans/i*(i-1);
            while(n%i == 0)
                n/=i;
        }
    }
    if(n > 1)
        ans = ans/n*(n-1);
    return ans;
}
/*********** End ***********/
int main()
{
    ll p,alp,a,k,x;
    cin>>p>>alp>>a>>k>>x;
    /*********** Begin ***********/
    ll beta=quick(alp,a,p)%p;
    ll gamma=quick(alp,k,p)%p;
    ll delta=(((x-a*gamma)*quick(k,eular(p-1)-1,p-1)%(p-1))+p-1)%(p-1);
    cout<<gamma<<' '<<delta<<endl;
    /*********** End ***********/
    return 0;
}

第3关：Schnorr签名方案

任务描述

Schnorr 签名算法最初是由德国密码学家 _ClausSchnorr_于 2008年提出的。
本关任务：实现_Schnorr_签名方案。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    ll k,a,q,h;
    cin>>k>>a>>q>>h;
    /*********** Begin ***********/
    cout<<(k+a*h)%q<<endl;
    /*********** End ***********/
    return 0;
}

8-2一些签名方案(二)

第1关：数字签名算法

任务描述

数字签名算法是数字签名标准的一个子集，表示了只用作数字签名的一个特定的公钥算法。 本关任务：计算消息_x_的数字签名。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
/*********** End ***********/
int main()
{
    ll a,q,alp,p,k,sha;
    cin>>a>>q>>alp>>p>>k>>sha;
    /*********** Begin ***********/
    ll beta=quick( alp,k, p)%q;
    cout<<beta<<' '<<(sha+a*beta)*quick( k,q-2, q)%q<<endl;
    /*********** End ***********/
    return 0;
}

第2关：椭圆曲线DSA(ECDSA)

任务描述

椭圆曲线数字签名算法是一种基于椭圆曲线的数字签名算法。
本关任务：计算消息_x_的椭圆曲线_DSA_。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
/*********** End ***********/
int main()
{
    ll u,v,q,k,SHA,m;
    cin>>u>>v>>q>>k>>SHA>>m;
    /*********** Begin ***********/
    ll r=u%q;
    cout<<r<<' '<<quick(3,q-2,q)*(SHA+m*r)%q<<endl;
    /*********** End ***********/
    return 0;
}

第3关：一次签名

任务描述

如果一个签名方案仅给一则消息签名时是安全的，则该签名方案是一次签名方案。 本关任务：计算消息_x_的一次签名原像。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
/*********** End ***********/
ll y[1000][3];
char s[1000+10];
int main()
{
    ll q,c,k;
    scanf("%lld%lld%lld",&q,&c,&k);
    for(int i=0; i<k; i++)
        scanf("%lld%lld",&y[i][0],&y[i][1]);
    scanf("%s",s);
    /*********** Begin ***********/
    for(int i=0; i<strlen(s); i++)
    {
        if(s[i]=='0')
            printf("%lld",quick(c,y[i][0],q));
        else
            printf("%lld",quick(c,y[i][1],q));
        if(i==strlen(s)-1)
            printf("\n");
        else
            printf(" ");
    }
    /*********** End ***********/
    return 0;
}

8-3一些签名方案以及相关技术

第1关：全域Hash

任务描述

全域_Hash_签名方案的名字来自该方案要求随机预言的值域与陷门单向置换的定义域相同。
本关任务：计算找到随机元素的逆的概率。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
int main()
{
    double epsilon,q;
    int k;
    scanf("%lf%d%lf",&epsilon,&k,&q);
    /*********** Begin ***********/
    printf("%.6f\n",(epsilon-1.0/(1LL<<k)/q));
    /*********** End ***********/
    return 0;
}

第2关：不可否认的签名

任务描述

不可否认的签名是由_Chaum_和_vanAntwerpen_在1989年提出来的。 本关任务：计算消息x的_Chaum_?_vanAntwerpen_签名。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
/*********** End ***********/
int main()
{
    ll x,q,a;
    cin>>x>>q>>a;
    /*********** Begin ***********/
    cout<<quick(x,a, q)<<endl;
    /*********** End ***********/
    return 0;
}

第3关：fail-stop签名

任务描述

_fail_?_stop_签名属于一次签名方案。
本关任务：计算秘密离散对数_α_0。

#include<bits/stdc++.h>
using namespace std;
#define ll  long  long
//在下面Begin和End之间补全代码，输出相应的结果
/*********** Begin ***********/
ll quick(ll a,ll b, ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
ll eular(ll n)
{
    ll ans = n;
    for(int i=2; i*i <= n; ++i)
    {
        if(n%i == 0)
        {
            ans = ans/i*(i-1);
            while(n%i == 0)
                n/=i;
        }
    }
    if(n > 1)
        ans = ans/n*(n-1);
    return ans;
}
/*********** End ***********/
int main()
{
    ll alpha,p,k,beta,a_1,a_2,b_1,b_2,x,x_1,x_2;
    cin>>alpha>>p>>k>>beta>>a_1>>a_2>>b_1>>b_2>>x>>x_1>>x_2;
    /*********** Begin ***********/
    ll gamma_1=quick(alpha,a_1,p)*quick(beta,a_2,p)%p;
    ll gamma_2=quick(alpha,b_1,p)*quick(beta,b_2,p)%p;
    ll _x1=(a_1+x*b_1)%k;
    ll _x2=(a_2+x*b_2)%k;
    ll a_0=((x_1-_x1)*quick(_x2-x_2,eular(k)-1,k)%k+k)%k;
    cout<<a_0<<endl;
    /*********** End ***********/
    return 0;
}