logo资料库

密码学 模逆与模幂计算与应用 实验五报告.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.02M 资料格式：docx 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    四、设计概要：
    五、实验代码
    #include
    #include
    #include
    #include
    #define mn 200
    int mod_invese(int n, int d) //求d模n的逆，n 为正整数
    {
    int a,b,q,r,u=0,v=1,t;
    a=n;
    b=(d>=0)?(d%n):-(d%n);
    while(b!=0)
    {
    q=(int)a/b;
    r=a-b*q;
    a=b;
    b=r;
    t=v;
    v=u-q*v;
    u=t;
    }
    if(a!=1) return(-a);
    return((u<0)?u+n:u);
    }
    int mod_power(int k, int a, int n) //要求 n 为正整数
    //采用从右向左算法，从左向右
    {
    int x,y,t;
    y=a;
    t=k;
    if(t<0)
    {
    y=mod_invese(y, n);
    if(y<0) return(0);//没有模逆
    t=-t;
    }
    x=1;
    if(t==0) return(1);
    while(t>1)
    {
    if(t&0x00000001) x=(x*y)%n;
    y=(y*y)%n;
    t>>=1;
    }
    x=(x*y)%n;
    return(x);
    }
    int gcd(int a,int b)//判断a,b是否互素
    {
    int r;
    while(1)
    {
    r=a%b;
    if(r!=0)
    {
    a=b;
    b=r;}
    else break;
    }
    if(b==1) return 1;
    else return b;
    }
    int suiji(int t[mn])//随机生成200个小于2^16的正整数
    {
    int q;
    srand((unsigned)time(NULL));
    for(q=0;q
    {t[q]=rand()%65536+1;
    //printf("%7d",t[q]);
    //if(q%10==0)printf("\n");
    }
    return t[q];
    }
    int su(int n) //判断是否是素数
    {
    int j;
    for(j=2;j<=sqrt(n)-1;j++)
    {
    if((n%j)==0) break;
    }
    if(j>sqrt(n)-1)
    {
    printf("%8d",n);
    }
    return n;
    }
    void rsa()
    {
    printf("---------------------------------生成若干个素---
    int t[mn],i;
    suiji(t);
    printf("随机生成200个大整数,其中是素数的有：\n");
    for(i=0;i
    su(t[i]);
    printf("\n");
    int n,fn,e,d,m,c,p,q;
    printf("\n----------------------------------RSA算法-
    printf("请从上面的素数中选择两个分别作为p和q：");
    scanf("%d",&p);
    scanf("%d",&q);
    n=p*q;
    fn=(p-1)*(q-1);
    printf("\nfn=(p-1)*(q-1)=%d\n",fn);
    printf("\n");
    printf("请输入正整数e:");
    scanf("%d",&e);
    while(1)
    {
    if(gcd(fn,e)==1)
    break;
    else{
    printf("\n");
    printf("请重新输入，满足fn与e互素:");
    scanf("%d",&e);printf("\n");
    }
    }
    d=mod_invese(fn,e);
    if(d==0) printf("错误!\n");
    else{printf("\n公钥k1=(e,n)=(%d,%d)\n\n",e,n);
    printf("私钥k2=d=%d\n\n",d);
    printf("输入明文:");
    scanf("%d",&m);printf("\n");
    c=mod_power(e,m,n);
    printf("加密:c = %d的%d次方mod %d = %d\n\n",m,e,n,c);
    printf("解密:m=%d的%d次方mod %d = %d\n\n",c,d,n,mod_po
    }
    }
    void ElGama()
    {
    printf("----------------------------------EIGamal算
    int d,t,m,c1,c2,k,p,a,r,x,y,g;
    printf("请从上面生成的素数中选择一个素数（p）:");
    scanf("%d",&p);printf("\n");
    int h,w,s,sum=0;
    w=p-1;
    printf("为了节省空间，这里只给出%d的20个原根：\n",p);
    for(h=2;h
    {
    s=mod_power(w,h,p);
    if(s==1)
    {
    printf("%3d",h);
    sum=sum+1;
    if(sum==20)break;//如果想要全部的原根，去掉break做相应修改。
    }
    }
    printf("\n\n");
    printf("请从上面的原根中选择一个输入（a）:");
    scanf("%d",&a);
    printf("\n");
    printf("输入整数d:");
    scanf("%d",&d);
    printf("\n");
    t=mod_power(d,a,p);
    printf("t=a的d次方mod p=%d\n",t);printf("\n");
    printf("公钥:(p,a,t)=(%d,%d,%d)\n",p,a,t);
    printf("\n");
    printf("私钥:d=%d\n",d);
    printf("\n");
    printf("请输入明文m:");
    scanf("%d",&m);
    printf("\n");
    printf("请输入正整数k，其中(1
    scanf("%d",&k);
    printf("\n");
    c1=mod_power(k,a,p);
    c2=(m*mod_power(k,t,p))%p;
    printf("加密:c=(c1,c2)=(%d,%d)\n",c1,c2);
    printf("\n");
    m=mod_power(d,c1,p);
    m=mod_invese(p,m);
    m=m*c2%p;
    printf("解密:m=%d\n",m);
    printf("\n");
    printf("\n------------------------------------签名--
    printf("请输入大素数p:");
    scanf("%d",&p);
    printf("\n");
    printf("输入一个原根g:");
    scanf("%d",&g);
    printf("\n");
    printf("请输入正整数x(1<=x<=p-2):");
    scanf("%d",&x);
    printf("\n");
    y=mod_power(x,g,p);
    printf("y=%d是公开密钥，x=%d是保密密钥.\n",y,x);
    printf("\n");
    printf("秘密选取一随机数k其中(0
    scanf("%d",&k);
    printf("\n");
    printf("请输入要加密的消息m=");
    scanf("%d",&m);
    printf("\n");
    r=mod_power(k,g,p);
    d=mod_invese((p-1),k);
    d=d*((m-x*r)%(p-1))%(p-1)+p-1;
    printf("签名：(r,d)=(%d,%d)\n",r,d);
    printf("\n");
    printf("验证：");
    if(mod_power(r,y,p)*mod_power(d,r,p)%p==mod_power
    {printf("(r,d)为真.\n");printf("\n");}
    else
    printf("(r,d)为假.\n");
    }
    void main()
    {
    rsa();
    ElGama();
    }
    六、思考题
    本实验是一个综合性实验，你认为它都涉及到了你们学过的哪些知识？（不限于本课程去列举）
    七、实验体会
    实验报告 实验序号：五 实验名称：模逆与模幂计算与应用 一、实验目的 该实验为综合性实验。 通过本实验，使学生切实掌握作为大多数公钥密码计算基础的“模逆”与“模幂”算法， 并学会运用上述两个基本算法来实现诸如 RSA、ElGamal 等公钥密码的各主要需求和功能， 最终对“一个公钥密码体制如何应用”形成一定的认识和理解。 二、实验内容 1. 编写下列基本程序： i) 对于不超过 2 16 的两个正整数 a 与 n，计算 a -1 (mod n)； ii) 对于不超过 2 的三个正整数 a、e 与 n，计算 a 16 e (mod n)。 2.编写下列应用程序： i) 找到一个不超过 2 16 的随机素数（随机生成一个 2 16 以内奇数并检验其素性）； ii) RSA 体制公私密钥对生成、加密与签名； iii) ElGamal 体制公私密钥对生成、加密与签名。 三、 实验要求 1. 对较小正整数的模逆、模幂计算结果须与手工推算一致； 2. 在“用户界面”上对每一项应用要以算例给出示意，并都抓图显示出来（附页）。 四、设计概要： 主程序 生成素数 RSA 算法 EIGama 算法 签名 五、实验代码 #include #include #include #include #define mn 200 1
    int mod_invese(int n, int d) //求 d 模 n 的逆，n 为正整数 { int a,b,q,r,u=0,v=1,t; a=n; b=(d>=0)?(d%n):-(d%n); while(b!=0) { q=(int)a/b; r=a-b*q; a=b; b=r; t=v; v=u-q*v; u=t; } if(a!=1) return(-a); return((u<0)?u+n:u); } int mod_power(int k, int a, int n) //要求 n 为正整数 //采用从右向左算法，从左向右算法 { } int x,y,t; y=a; t=k; if(t<0) { y=mod_invese(y, n); if(y<0) return(0);//没有模逆 t=-t; } x=1; if(t==0) return(1); while(t>1) { if(t&0x00000001) x=(x*y)%n; y=(y*y)%n; t>>=1; } x=(x*y)%n; return(x); 2
    int gcd(int a,int b)//判断 a,b 是否互素 { int r; while(1) { r=a%b; if(r!=0) { a=b; b=r;} else break; } if(b==1) return 1; else return b; } int suiji(int t[mn])//随机生成 200 个小于 2^16 的正整数 { int q; srand((unsigned)time(NULL)); for(q=0;qsqrt(n)-1) { printf("%8d",n); } 3
    return n; } void rsa() { printf("---------------------------------生成若干个素---------------------------------\n"); int t[mn],i; suiji(t); printf("随机生成 200 个大整数,其中是素数的有：\n"); for(i=0;i
    } void ElGama() { printf("----------------------------------EIGamal 算法-------------------------------\n\n"); int d,t,m,c1,c2,k,p,a,r,x,y,g; printf("请从上面生成的素数中选择一个素数（p）:"); scanf("%d",&p);printf("\n"); int h,w,s,sum=0; w=p-1; printf("为了节省空间，这里只给出%d 的 20 个原根：\n",p); for(h=2;h
    printf("加密:c=(c1,c2)=(%d,%d)\n",c1,c2); printf("\n"); m=mod_power(d,c1,p); m=mod_invese(p,m); m=m*c2%p; printf("解密:m=%d\n",m); printf("\n"); printf("\n------------------------------------签名------------------------------------\n"); printf("请输入大素数 p:"); scanf("%d",&p); printf("\n"); printf("输入一个原根 g:"); scanf("%d",&g); printf("\n"); printf("请输入正整数 x(1<=x<=p-2):"); scanf("%d",&x); printf("\n"); y=mod_power(x,g,p); printf("y=%d 是公开密钥，x=%d 是保密密钥.\n",y,x); printf("\n"); printf("秘密选取一随机数 k 其中(0
    } 六、思考题 本实验是一个综合性实验，你认为它都涉及到了你们学过的哪些知识？（不限于本课程 去列举） 答：这次综合性实验，涉及到了产生随机数，模逆与模幂运算，RSA 算法，EIGama 算法， 签名等等。 七、实验体会 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料