c语言getprime是什么意思

c语言getprime是什么意思

CTF中的RSA前言 getprime(512)

本文对RSA中常用的模逆运算、欧几里得、拓展欧几里得、中国剩余定理等算法不展开作详细介绍，仅对遇到的CTF题的攻击方式，以及使用到的这些算法的python实现进行介绍。目的是让大家能轻松解决RSA在CTF中的套路题目。

RSA介绍 getprime(512)

首先，我这边就不放冗长的百度百科的东西了，我概括一下我自己对RSA的看法。

RSA是一种算法，并且广泛应用于现代，用于保密通信。

RSA算法涉及三个参数,n,e,d，其中分为私钥和公钥，私钥是n,d，公钥是n,e

n是两个素数的乘积，一般这两个素数在RSA中用字母p,q表示

e是一个素数

d是e模 varphi(n) 的逆元，CTF的角度看就是，d是由e,p,q可以求解出的

一般CTF就是把我们想要获得的flag作为明文，RSA中表示为m。然后通过RSA加密，得到密文，RSA中表示为C。

加密过程

c=m^e mod n

c=pow(m,e,n)

1

解密过程

m=c^d mod n

m=pow(c,d,n)

1

求解私钥d

d = gmpy2.invert(e, (p-1)*(q-1))

1

一般来说࿰

文章知识点与官方知识档案匹配

算法技能树首页概览

30677 人正在系统学习中

直接到C++的密码库里面下载即可！你所需要的密码算法都有。看下面的网站：

http://www.cryptopp.com/

http://csrc.nist.gov/groups/STM/index.html

同学，你可以先自己下载下来看看，改改，就成为了你需要的，都是基于字符界面的，很好理解的。

上学期交的作业，已通过老师在运行时间上的测试

#include <stdio.h>

#include <stdlib.h>

unsigned long prime1,prime2,ee

unsigned long *kzojld(unsigned long p,unsigned long q) //扩展欧几里得算法求模逆

{

unsigned long i=0,a=1,b=0,c=0,d=1,temp,mid,ni[2]

mid=p

while(mid!=1)

{

while(p>q)

{p=p-q mid=pi++}

a=c*(-1)*i+ab=d*(-1)*i+b

temp=aa=cc=temp

temp=bb=dd=temp

temp=pp=qq=temp

i=0

}

ni[0]=cni[1]=d

return(ni)

}

unsigned long momi(unsigned long a,unsigned long b,unsigned long p) //模幂算法

{

unsigned long c

c=1

if(a>p) a=a%p

if(b>p) b=b%(p-1)

while(b!=0)

{

while(b%2==0)

{

b=b/2

a=(a*a)%p

}

b=b-1

c=(a*c)%p

}

return(c)

}

void RSAjiami() //RSA加密函数

{

unsigned long c1,c2

unsigned long m,n,c

n=prime1*prime2

system("cls")

printf("Please input the message：\n")

scanf("%lu",&m)getchar()

c=momi(m,ee,n)

printf("The cipher is：%lu",c)

return

}

void RSAjiemi() //RSA解密函数

{

unsigned long m1,m2,e,d,*ni

unsigned long c,n,m,o

o=(prime1-1)*(prime2-1)

n=prime1*prime2

system("cls")

printf("Please input the cipher：\n")

scanf("%lu",&c)getchar()

ni=kzojld(ee,o)

d=ni[0]

m=momi(c,d,n)

printf("The original message is：%lu",m)

return

}

void main()

{ unsigned long m

char cho

printf("Please input the two prime you want to use:\n")

printf("P=")scanf("%lu",&prime1)getchar()

printf("Q=")scanf("%lu",&prime2)getchar()

printf("E=")scanf("%lu",&ee)getchar()

if(prime1<prime2)

{m=prime1prime1=prime2prime2=m}

while(1)

{

system("cls")

printf("\t*******RSA密码系统*******\n")

printf("Please select what do you want to do:\n")

printf("1.Encrpt.\n")

printf("2.Decrpt.\n")

printf("3.Exit.\n")

printf("Your choice:")

scanf("%c",&cho)getchar()

switch(cho)

{ case '1':RSAjiami()break

case '2':RSAjiemi()break

case '3':exit(0)

default:printf("Error input.\n")break

}

getchar()

}

}

---