Demo entry 6780234

py

   

Submitted by huang on Dec 24, 2018 at 00:54
Language: C++. Code size: 2.0 kB.

#include <iostream>
#include<stdlib.h>
#include <cmath>
using namespace std;

int exEuclidean(int a,int b,int &x,int &y)
{
    ////扩展的欧几里得算法,存在整数对 x,y ,使得 gcd(a,b)=ax+by
    if (b==0)
    {
        x=1,y=0;
        return a;
    }
    int q=exEuclidean(b,a%b,y,x);
    y-=a/b*x;
    return q;
}

int modOFmi(int x,int r,int n)
{
    //x^r mod n快速幂
    int a=x,b=r,c=1;
    while(b)
    {
        if(b&1)
            c=a*c%n;
        a=a*a%n;
        b=b>>1;
    }
    return c;
}

int IsPrime(int iNumber)
{
    //检测iNumber是否为素数,是返回1,否返回0
    int iCount;
    iCount=2;
    if(iNumber<2)
        return 0;
    while(iCount<=(iNumber/2))
    {
        if(iNumber%iCount==0)
            return 0;
        iCount++;
    }
    return 1;
}

int computeBYY(int p)
{
    //计算p的本原元//这里求的是最小的一个
    for(int a=2; a<p; a++)
    {
        if(modOFmi(a,p-1,p) == 1)
            return a;
    }
    return 0;
}

int main()
{
    int p;//素数
    int Plain_text;//明文
    int pri_root;//素数p的一个原根
    int pri_k;//私钥
    int pub_k;//公钥
    int k;//过程随机数k
    int c1,c2;//密文
    cout<<endl<<"输入素数p:";
    cin>>p;
    while(!IsPrime(p))
    {
        cout<<"p不是素数!"<<endl;
        cout<<endl<<"输入素数p:";
        cin>>p;
    }
    cout<<"输入小于素数p的明文:";
    cin>>Plain_text;

    pri_root=computeBYY(p);
    cout<<"找出p的一个原根为:"<<pri_root<<endl;

    pri_k=rand()%(p-1)+1;//私钥 1≤a≤p-2
    cout<<endl<<"输入完成,开始计算密文!"<<endl<<endl;

    pub_k=modOFmi(pri_root,pri_k,p);
    cout<<"公钥为:"<<pub_k<<endl;
    k=rand()%(p-1)+1;	//随机数k 1≤k≤p-2
    c1 = modOFmi(pri_root,k,p);
    c2 = ( Plain_text%p*modOFmi(pub_k,k,p) )%p;
    cout<<"密文Dk(c1,c2)为("<<c1<<","<<c2<<")"<<endl;
    cout<<"密文完成,开始计算明文!"<<endl<<endl;

    int x,y;//存在整数对 x,y ,使得 gcd(a,b)=ax+by
    exEuclidean(modOFmi(c1,pri_k,p),p,x,y);
    x=(x+p)%p;
    Plain_text=(c2*x)%p;
    cout<<"计算出的明文为:"<<Plain_text<<endl;
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).