【rsa算法基本讲解部分】

该部分大牛可以跳过 (`●__●ˊ) /

rsa里的n是两个大素数p和q的乘积,n的位数的多少很大程度上决定了该rsa的安全程度

(RSA安全依赖之一:大素数分解困难),根据欧拉函数φ(n)=(p-1)*(q-1)

φ(n)表示:在小于等于n的正整数之中,有多少个与n构成互质关系

而rsa的公私钥e和d就是关于φ(n)的乘法逆元,所谓乘法逆元就是e*d mod φ(n) =1

ps:e的选取需要与φ(n)互素,选出e再根据扩展欧几里得算法算出d

符合上述条件的e和d便能实现加解密↓

明文^e mod n = 密文

密文^d mod n = 明文

其中的数学推导,限于篇幅就不 一 一 证明了

(不然要被嫌弃啰嗦了西普CTF-RSAROLL-以夕阳落款

【解题部分:思路一】

题目说是RSA,打开txt看到首行{920139713,19},可知前者是n,后者是d或者e(一般较短的是公钥e,私钥d一般是较长的那个,防爆破嘛)这里安利个在线素数分解工具http://www.atool.org/quality_factor.php,不用下载挺方便

西普CTF-RSAROLL-以夕阳落款

如上图分解得到p和q,进而算的φ(n)=920071380

d可以通过求e关于φ(n)的逆元求得为96849619,python里的gmpy库里有相应的函数,详细见代码

西普CTF-RSAROLL-以夕阳落款

虽说是密文的96849619次方模920139713这样的大数运算

py运行起来还是蛮快的,但假如说"艾玛机子出现迷之卡顿算不了这么大的"

那也是有第二种思路可以走的

【解题部分:思路二】

既然密文的96849619次方,也就是密文^d难算,那明文^e次方呢

明文也就是ascii而已,128以内的数,而e也只有19而已,其运算量相对于密文^d来说要小得多

所以,思路就是,先把ascii中可见字符的ascii值经过ascii^19 mod n计算其加密后的值,并存到字典里

然后匹配密文,输出明文即可,这种方法好处在于不用计算逆元也不用进行素数分解(MD5的碰撞解密思路同理)

西普CTF-RSAROLL-以夕阳落款

也是差不多10行代码

-------END-------

C#版:

void Button1Click(object sender, EventArgs e)
{
	string p = "18443";
	string q = "49891";
	BigInteger pInteger = BigInteger.Parse(p);
	BigInteger qInteger = BigInteger.Parse(q);
	BigInteger nInteger = (pInteger - 1) * (qInteger - 1);
	BigInteger eInteger = 19;
	
	List<BigInteger> elist = new List<BigInteger>();
	List<BigInteger> nlist = new List<BigInteger>();
	elist.Add(eInteger);
	nlist.Add(nInteger);
	//辗转相除法
	while(eInteger != 1){
		nInteger = nInteger % eInteger;
		elist.Add(eInteger);
		nlist.Add(nInteger);
		eInteger = eInteger % nInteger;
		elist.Add(eInteger);
		nlist.Add(nInteger);
	}
	BigInteger dInteger = 1;
	BigInteger kInteger = 0;
	for(int i = elist.Count - 2; i >= 0; i = i - 2){
		kInteger = (elist[i] * dInteger - 1) / nlist[i];
		dInteger = (nlist[i - 1] * kInteger + 1) / elist[i - 1];
	}
	//MessageBox.Show(dInteger * elist[0] % nlist[0] + "");
	textBox1.Text += dInteger + "\r\n\r\n";
	
	string[] c = {"704796792", "752211152", "274704164", "18414022", "368270835", "483295235", "263072905", "459788476", "483295235", "459788476", "663551792", "475206804", "459788476", "428313374", "475206804", "459788476", "425392137", "704796792", "458265677", "341524652", "483295235", "534149509", "425392137", "428313374", "425392137", "341524652", "458265677", "263072905", "483295235", "828509797", "341524652", "425392137", "475206804", "428313374", "483295235", "475206804", "459788476", "306220148"};
	for(int i = 0; i < c.Length; i++){
		BigInteger cInteger = BigInteger.Parse(c[i]);
		textBox1.Text += (char)runFermatPow(cInteger, dInteger, pInteger * qInteger);
	}
}

BigInteger runFermatPow(BigInteger a, BigInteger b, BigInteger m){
	BigInteger result = 1;
	while (b > 0) {
		if ((b & 1) == 1)
		result = (result * a) % m;
		
		a = (a * a) % m;
		b >>= 1;
	}
	return result;
}

Flag:

温馨提示: 此处内容需要评论本文后刷新才能查看,支付2元即可直接查看所有Flag。

小广告:关于获取西普实验吧所有Flag请点击这里查看索引

查看所有Flag文章需要输入密码,需要获取文章密码的童鞋请扫描下面微信或支付宝二维码捐助至少2元(老哥,捐多捐少是个缘分)之后发送支付凭证号联系我获取,Flag大全地址:Flag大全

新功能:捐款的小伙伴请联系我把自己的注册邮箱加入网站白名单,可以免回复看到本站所有Flag

PS:本站不是实验吧的官方站点,纯粹是个人博客,收取Flag费用仅是维持服务器费用,做站不易,且行窃珍惜!

微信二维码:
支付宝二维码: